No description available.

No description available.

This thesis studies how the Douglas–Rachford splitting technique can be leveraged for scalable computational optimal transport (OT). By carefully splitting the problem, we derive an algorithm with several advantages. First, the algorithm enjoys global convergence rates comparable to the state-of-the-art while benefiting from accelerated local rates. In contrast to other methods, it does not depend on hyperparameters that can cause numerical instability. This feature is particularly advantageous when low-precision floating points are used or if the data is noisy. Moreover, the updates can efficiently be carried out on GPUs and, therefore, benefit from the high degree of parallelization achieved via GPU computations. Furthermore, we show that the algorithm can be extended to handle a broad family of regularizers and constraints while enjoying the same theoretical and numerical properties. These factors combined result in a fast algorithm that can be applied to large-scale OT problems and regularized versions thereof, which we illustrate in several numerical experiments. In the first part of the main body of the thesis, we present how Douglas-Rachford splitting can be adapted for the unregularized OT problem to derive a fast algorithm. We present two global convergence guarantees for the resulting algorithm: a 1/k-ergodic rate and a linear rate. We also show that the stopping criteria of the algorithm can be computed on the fly with virtually no extra costs. Further, we specify how a GPU kernel can be efficiently implemented to carry out the operations needed for the algorithm. To show that the algorithm is fast, accurate, and robust, we run a series of numerical benchmarks that demonstrate the advantages of our algorithm. We then extend the algorithm to handle regularized OT using sparsity-promoting regularizers. The generalized algorithm will enjoy the same sublinear rate derived for the unregularized formulation. We also complement the global rate with local guarantees, establishing that, under non-degeneracy assumptions on the solution, the algorithm will identify the correct sparsity pattern of the solution in finitely many iterations. When the sparsity pattern is identified, a faster linear rate typically dominates. We also specify how to extend to the GPU implementation and the stopping criteria to handle regularized OT, and we subsequently specify how to backpropagate through the solver. We end this part of the thesis by presenting some numerical results, including performance on quadratically regularized OT and group Lasso regularized OT for domain adaptation, showing a substantial improvement compared to the state-of-the-art. In the last part of the thesis, we provide a more detailed analysis of the local behavior of the algorithm when applied to unregularized OT and quadratically regularized OT. We subsequently outline how to extend this analysis to several other sparsity-promoting regularizers. In the former two cases, we show that the update that constitutes the algorithm converges to a linear operator in finitely many iterations. By analyzing the spectral properties of these linear operators, we gain insights into the local behavior of the algorithm, and specifically, these results suggest how to tune stepsizes to obtain better local rates. / Denna avhandling behandlar hur Douglas–Rachford-splittning kan tillämpas för skalbara beräkningar av optimal transport (OT). Genom en noggrann splittning av problemet härleder vi en algoritm med flera fördelar. För det första åtnjuter algoritmen en global konvergenshastighet som är jämförbara med populära OT-lösare, samtidigt som den drar nytta av accelererade lokalahastigheter. Till skillnad från andra metoder är den inte beroende av hyperparametrar som kan orsaka numerisk instabilitet. Den här egenskapen är särskilt fördelaktig när lågprecisionsaritmetik används eller när data innehåller mycket brus. Uppdateringarna som algoritmen baseras på kan effektivt utföras på GPU:er och dra nytta av dess parallellberäkningar. Vi visar också att algoritmen kan utökas för att hantera en rad regulariseriseringar och bivillkor samtidigt som den åtnjuter liknande teoretiska och numeriska egenskaper. Tillsammans resulterar dessa faktorer i en snabb algoritm som kan tillämpas på storskaliga OT-problem samt flera av dess regulariserade varianter, vilket vi visar i flera numeriska experiment. I den första delen av avhandlingen presenterar vi hur Douglas-Rachford-splittning kan anpassas för det oregulariserade OT-problemet för att härleda en snabb algoritm. För den resulterande algoritmen presenterar vi två globala konvergensgarantier: en 1/k-ergodisk och en linjär konvergenshastighet. Vi presenterar också hur stoppkriterierna för algoritmen kan beräknas utan vidare extra kostnader. Dessutom specificerar vi hur en GPU-kärna kan implementeras för att effektivt utföra de operationer som algoritmen baseras på. För att visa att algoritmen är snabb, exakt och robust utför vi ett flertal numeriska experiment som påvisar flera fördelar över jämförbara algoritmer. Därefter utökar vi algoritmen för att hantera regulariserad OT med s.k. sparsity-promoting regularizers. Den generaliserade algoritmen åtnjuter samma sublinjära konvergenshastighet som härleddes för den oregulariserade fallet. Vi kompletterar också garantierna genom att tillhandahålla lokala garantier genom att fastställa att givet svaga antaganden om lösningen kommer algoritmen att identifiera den korrekta lösningens gleshetsstuktur inom ett begränsat antal iterationer. När glesheten identifierats dominerar typiskt sett en snabbare linjär konvergenshastighet. Vi specificerar också hur man utökar till GPU-kärnan och resultaten av stoppkriterierna för att hantera regulariserad OT, och vi specificerar sedan hur man differentiera genom lösaren. Vi avslutar den här delen av avhandlingen genom att presentera några numeriska resultat för kvadratiskt reglerad OT och group Lasso-reglerad OT för domänanpassning, vilket visar en betydande förbättring jämfört med de mest populära metoderna för dessa tillämpningar. I den sista delen av avhandlingen ger vi en mer detaljerad analys av algoritmens lokala beteende när den tillämpas på oregulerisad OT och kvadratiskt reglerad OT. Vi föreslår även sätt att studera flera andra fallet. I de två första fallen visar vi att uppdateringen som utgör algoritmen konvergerar till en linjär operator inom ett begränsat antal iterationer. Genom att analysera de spektrala egenskaperna hos dessa linjära operatorer får vi ytterligare insikter i algoritmens lokala beteende, och specifikt indikerar dessa resultat hur man kan justera steglängden för att uppnå ännu bättre konvergenshastigheter. / <p>QC 20231123</p>

The goal of optimal transport is to map a source probability measure to a destination one with the minimum possible cost. However, the optimal mapping might not be feasible under some practical constraints. One such example is to realize a transport mapping through an information bottleneck. As the optimal mapping may induce infinite mutual information between the source and the destination, the existence of an information bottleneck forces one to resort to some suboptimal mappings. Investigating this type of constrained optimal transport problems is clearly of both theoretical significance and practical interest. In this work, we substantiate a particular form of constrained optimal transport in the context of quantum-to-classical systems by establishing an Output-Constrained Rate-Distortion Theorem similar to the classical case introduced by Yuksel et al. This theorem develops a noiseless communication channel and finds the least required transmission rate R and common randomness Rc to transport a sufficiently large block of n i.i.d. source quantum states, to samples forming a perfectly i.i.d. classical destination distribution, while maintaining the distortion between them. The coding theorem provides operational meanings to the problem of Rate-Limited Optimal Transport, which finds the optimal transportation from source to destination subject to the rate constraints on transmission and common randomness. We further provide an analytical evaluation of the quantum-to-classical rate-limited optimal transportation cost for the case of qubit source state and Bernoulli output distributions with unlimited common randomness. The evaluation results in a transcendental system of equations whose solution provides the rate-distortion curve of the transportation protocol. We further extend this theorem to continuous-variable quantum systems by employing a clipping and quantization argument and using our discrete coding theorem. Moreover, we derive an analytical solution for rate-limited Wasserstein distance of 2nd order for Gaussian quantum systems with Gaussian output distribution. We also provide a Gaussian optimality theorem for the case of unlimited common randomness, showing that Gaussian measurement optimizes the rate in a system with Gaussian source and destination. / Thesis / Doctor of Philosophy (PhD) / We establish a coding theorem for rate-limited quantum-classical optimal transport systems with limited classical common randomness. The coding theorem, referred to as the output-constrained rate-distortion theorem, characterizes the rate region of measurement protocols on a product quantum source state for faithful construction of a given classical destination distribution while maintaining the source-destination distortion below a prescribed threshold with respect to a general distortion observable. This theorem provides a solution to the problem of rate-limited optimal transport, which aims to find the optimal cost of transforming a source quantum state to a destination distribution via a measurement channel with a limited classical communication rate. The coding theorem is further extended to cover Bosonic continuous-variable quantum systems. The analytical evaluation is provided for the case of a qubit measurement system with unlimited common randomness, as well as the case of Gaussian quantum systems.

We study a nonlinear kinetic model describing the interactions of particles in a granular medium, i.e. inelastic systems where kinetic energy is not conserved due to internal friction. Examples of particles that fall into this category are sand, ground coffee and many others. Originally studied by Benedetto, Caglioti and Pulvirenti in the one-dimensional setting (RAIRO Model. Math. Anal. Numer, 31(5): 615-641, (1997)) the original model contained inconsistencies later accounted for and corrected by invoking a mollifier (Modelisation Mathematique et Analyse Numerique, M2AN, Vol. 33, No 2, pp. 439–441 (1999)). This thesis approximates the generalized model presented by Agueh (Arch. Rational Mech., Anal. 221, pp. 917-959 (2016)) with the added assumption of a spatial mollifier present in the kinetic equation. In dimension d ≥ 1 this model reads as ∂tf + v · ∇xf = divv(f([ηα∇W] ∗(x,v) f)) where f is a non-negative particle density function, W is a radially symmetric class C2 velocity interaction potential, and and ηα is a mollifier. A physical interpretation of this approximation is that the particles are spheres of radius α > 0 as opposed to the original assumption of being point-masses. Properties lost by this approximation and macroscopic quantities that remain conserved are discussed in greater detail and contrasted. The main result of this thesis is a proof of the weak global existence and uniqueness. An argument utilizing the tools of Optimal Transport allows simple construction of a weak solution to the kinetic model by transporting an initial measure under the characteristic flow curves. Concluding regularity arguments and restrictions on the velocity interaction potential ascertain that global classical solutions are obtained. / Graduate

The Schrödinger equations have had a profound impact on a wide range of fields of modern science, including quantum mechanics, superfluidity, geometrical optics, Bose-Einstein condensates, and the analysis of dispersive phenomena in the theory of PDE. The main purpose of this thesis is to explore two Schrödinger-type equations appearing in the so-called Bohmian formulation of quantum mechanics and in the study of exciton-polariton condensates. For the first topic, the linear Schrödinger equation is the starting point in the formulation of a phase-space model proposed in [1] for the Bohmian interpretation of quantum mechanics. We analyze this model, a nonlinear Vlasov-type equation, as a Hamiltonian system defined on an appropriate Poisson manifold built on Wasserstein spaces, the aim being to establish its existence theory. For this purpose, we employ results from the theory of PDE, optimal transportation, differential geometry and algebraic topology. The second topic of the thesis is the study of a nonlinear Schrödinger equation, called the complex Gross-Pitaevskii equation, appearing in the context of Bose-Einstein condensation of exciton-polaritons. This model can be roughly described as a driven-damped Gross-Pitaevskii equation which shares some similarities with the complex Ginzburg-Landau equation. The difficulties in the analysis of this equation stem from the fact that, unlike the complex Ginzburg-Landau equation, the complex Gross-Pitaevskii equation does not include a viscous dissipation term. Our approach to this equation will be in the framework of numerical computations, using two main tools: collocation methods and numerical continuation for the stationary solutions and a time-splitting spectral method for the dynamics. After performing a linear stability analysis on the computed stationary solutions, we are led to postulate the existence of radially symmetric stationary ground state solutions only for certain values of the parameters in the equation; these parameters represent the “strength” of the driving and damping terms. Moreover, numerical continuation allows us to show, for fixed parameters, the ground and some of the excited state solutions of this equation. Finally, for the values of the parameters that do not produce a stable radially symmetric solution, our dynamical computations show the emergence of rotating vortex lattices.

This thesis is a survey of the mathematical theory of Generative Adversarial Networks (GANs). The relevant theories discussed are game theory, information theory and optimal transport theory.

Une première partie de cette thèse est dédiée à l’étude de la régularité de la densité de transport sigma dans le problème de Monge entre deux mesures f^+ et f^- sur un domaine Omega. Tout d’abord, on étudie la question de la sommabilité L^p de cette densité de transport entre une mesure f^+ et sa projection sur le bord (P)# f^+, qui ne découle pas en fait des résultats connus (dus à De Pascale - Evans - Pratelli - Santambrogio) sur la densité de transport entre deux densités L^p, comme dans notre cas la mesure cible est singulière. Par une méthode de symétrisation, dès que Omega est convexe ou satisfait une condition de boule uniforme extérieure, nous prouvons les estimations L^p (si f^+ in L^p, alors sigma in L^p). En plus, nous analysons le cas où on paye des coûts supplémentaires g^± sur le bord, en prouvant que la densité de transport est dans L^p dès que f^± in L^p, Omega satisfait une condition de boule uniforme extérieure et, g^± sont lambda^± Lipschitiziens avec lambda^± < 1 et semi-concaves. Ensuite, on s’attaque à la régularité d’ordre supérieur (W^{1,p}, C^{0,alpha}, BV · · ·) de la densité de transport sigma entre deux densités régulières f^+ et f^-. Plus précisément, nous fournissons une famille de contre-exemples à la régularité supérieure: nous prouvons que la régularité W^{1,p} des mesures source et cible, f^+ et f^-, n’implique pas que la densité de transport est W^{1,p}, de même pour la régularité BV, et même f^± in C^infty n’implique pas que sigma est dans W^{1,p}, pour p grand. Ensuite, nous étudions la sommabilité L^p de la densité de transport entre deux mesures f^+ et f^- concentrées sur le bord. Plus précisément, nous prouvons que si f^+ et f^- sont dans L^p(partialOmega), alors la densité de transport sigma entre eux est dans L^p(Omega) dès que Omega est uniformément convexe et p leq 2; de plus, nous introduisons un contre-exemple montrant que ce résultat n’est plus vrai si p > 2. Cela fournit des résultats de régularité W^{1,p} sur la solution u du problème de gradient minimal avec donnée au bord g dans des domaines uniformément convexes (si g in W^{1,p}(partialOmega) alors u in W^{1,p}(Omega)).Dans une deuxième partie, nous étudions un problème de contrôle optimal motivé par un modèle de jeux à champ moyen. D’abord, nous montrons des résultats de différentiabilité et semi-concavité sur la fonction valeur associée au problème de contrôle (le résultat de semi-concavité est optimal en ce qui concerne les hypothèses sur la régularité en temps). Ensuite, nous démontrons que la densité des agents rho_t, dans le modèle MFG considéré, est dans L^p dès que la densité initiale rho_0 in L^p. En plus, nous arrivons à prouver l’existence d’un équilibre pour le problème MFG considéré dans un cas où la dynamique n’est pas régulière.Dernièrement, nous considérons le problème stationnaire associé au problème MFG. Nous montrons que la densité d’équilibre n’est rien d’autre que la densité de transport entre une densité source f et sa projection sur le bord en utilisant une métrique Riemannienne non-uniforme comme coût de transport. Cela nous permet de démontrer que la densité d’équilibre rho est dans L^p dès que la densité source f in L^p. Par conséquent, nous arrivons à prouver aussi l’existence d’un équilibre stationnaire dans un cas où la dynamique n’est pas régulière. / A first part of this thesis is dedicated to the study of the regularity of the transport density sigma in the Monge problem between two measures f^+ and f^- on a domain Omega. First, we study the question of L^p summability of this transport density between a measure f^+ and its projection on the boundary (P)# f^+, which does not actually follow from the known results (due to De Pascale, Evans, Pratelli, Santambrogio) on the transport density between two L^p densities, as in our case the target measure is singular. By a symmetrization trick, if Omega is convex or satisfies a uniform exterior ball condition, we prove the L^p estimates (if f^+ in L^p, then sigma in L^p). In addition, we analyze the case where we pay additional costs g^± on the boundary, proving that the transport density sigma is in L^p as soon as f^± in L^p, Omega satisfies a uniform exterior ball condition and, g^± are lambda^± Lip with lambda^± < 1 and semi-concave. Then we attack the higher-order regularity (W^{1,p}, C^{0,alpha}, BV · · ·) of the transport density sigma between two regular densities f^+ and f^-. More precisely, we provide a family of counter-examples to the higher regularity: we prove that the W^{1,p} regularity of the source and target measures, f^+ and f^-, does not imply that the transport density is in W^{1,p}, the same for the BV regularity, and even f^± in C^infty does not imply that sigma is in W^{1,p}, for large p. Next, we study the L^p summability of the transport density between two measures, f^+ and f^-, concentrated on the boundary. More precisely, we prove that if f^+ and f^- are in L^p(partialOmega), then the transport density sigma between them is in L^p(Omega) as soon as Omega is uniformly convex and p leq 2; moreover, we introduce a counter-example showing that this result is no longer true if p > 2. This provides W^{1,p} regularity results on the solution u of the least gradient problem with boundary datum g in uniformly convex domains (if g in W^{1,p}(partialOmega) then u in W^{1,p}(Omega)).In a second part, we study an optimal control problem motivated by a model of mean field games. First, we show differentiability and semi-concavity results on the value function associated with the control problem (the semi-concavity result will be sharp in regards to the hypotheses on the regularity in time). Then we show that the density of agents rho_t, in the considered MFG model, is in L^p as soon as the initial density rho_0 in L^p. In addition, we prove existence of an equilibrium for the considered MFG problem in a case where the dynamic is non-regular.Lastly, we consider the stationary problem associated with the MFG model. We show that the equilibrium density is nothing but the transport density between a source density f and its projection on the boundary using a non-uniform Riemannian metric as a transport cost. This allows us to show that the equilibrium density rho is in L^p as soon as the source density f in L^p. Therefore, we also prove existence of a stationary equilibrium in a case where the dynamic is non-regular.

Le Transport Optimal régularisé par l’Entropie (TOE) permet de définir les Divergences de Sinkhorn (DS), une nouvelle classe de distance entre mesures de probabilités basées sur le TOE. Celles-ci permettentd’interpolerentredeuxautresdistancesconnues: leTransport Optimal(TO)etl’EcartMoyenMaximal(EMM).LesDSpeuventêtre utilisées pour apprendre des modèles probabilistes avec de meilleures performances que les algorithmes existants pour une régularisation adéquate. Ceci est justifié par un théorème sur l’approximation des SDpardeséchantillons, prouvantqu’unerégularisationsusantepermet de se débarrasser de la malédiction de la dimension du TO, et l’on retrouve à l’infini le taux de convergence des EMM. Enfin, nous présentons de nouveaux algorithmes de résolution pour le TOE basés surl’optimisationstochastique‘en-ligne’qui,contrairementàl’étatde l’art, ne se restreignent pas aux mesures discrètes et s’adaptent bien aux problèmes de grande dimension. / This thesis proposes theoretical and numerical contributions to use Entropy-regularized Optimal Transport (EOT) for machine learning. We introduce Sinkhorn Divergences (SD), a class of discrepancies betweenprobabilitymeasuresbasedonEOTwhichinterpolatesbetween two other well-known discrepancies: Optimal Transport (OT) and Maximum Mean Discrepancies (MMD). We develop an ecient numerical method to use SD for density fitting tasks, showing that a suitable choice of regularization can improve performance over existing methods. We derive a sample complexity theorem for SD which proves that choosing a large enough regularization parameter allows to break the curse of dimensionality from OT, and recover asymptotic ratessimilartoMMD.Weproposeandanalyzestochasticoptimization solvers for EOT, which yield online methods that can cope with arbitrary measures and are well suited to large scale problems, contrarily to existing discrete batch solvers.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第21318号 / 情博第675号 / 新制||情||117(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 山本 章博, 教授 山下 信雄, 教授 田中 利幸, 上田 修功 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM