Curiosities and counterexamples in smooth convex optimization

• Edouard Pauwels (Toulouse School of Economics (TSE))

Room: Salle des Thèses We present a list of counterexamples to conjectures in smooth convex coercive optimization. We will detail two extensions of the gradient descent method, of interest in machine learning: gradient descent with exact line search, and Bregman descent (also known as mirror descent). We show that both are non convergent in general. These examples are based on general smooth convex interpolation results. Given a decreasing sequence of convex compact sets in the plane, whose boundaries are Ck curves (k > 1, arbitrary) with positive curvature, there exists a Ck convex function for which each set of the sequence is a sublevel set. The talk will provide proof arguments for this results and detail how it can be used to construct the announced counterexamples.

Conjectures in Real Algebra and Polynomial Optimization through High Precision Semidefinite Programming

• Michal Kočvara (University of Birmingham)

Room: Salle des Thèses We study degree bounds for the denominator-free Positivstellens »atze in real algebra, based on sums of squares (SOS), or equivalently the convergence rate for the moment-sums of squares hierarchy in polynomial optimization, from a numerical point of view. As standard semidefinite programming (SDP) solvers do not provide reliable answers in many important instances, we use a new high-precision SDP solver, Loraine.jl, to support our investigation. We study small instances (low-degree, small number of variables) of one-parameter families of examples, and propose several conjectures for the asymptotic behavior of the degree bounds. Our objective is twofold: first, to raise awareness on the bad performance of standard SDP solvers in such examples, and then to guide future research on the Effective Positivstellensätze. Joint work with Lorenzo Baldi.

Weak optimal transport with moment constraints: constraint qualification, dual attainment and entropic regularization

• Guillaume Carlier (Université Paris Dauphine)

Room: Salle des Thèses Weak optimal transport is a nonlinear version of the classical mass transport of Monge and Kantorovich which has received a lot of attention since its introduction by Gozlan Roberto, Samson and Tetali, ten years ago. In this talk, I will address weak optimal problems (possibly entropically penalized) incorporating both soft and hard (including the case of the martingale condition) moment constraints. Even in the special case of the martingale optimal transport problem, existence of Lagrange multipliers corresponding to the martingale constraint is notoriously hard (and may fail unless some specific additional assumptions are made). We identify a condition of qualification of the hard moment constraints (which in the martingale case is implied by well-known conditions in the literature) under which general dual attainment results are established. We also analyze the convergence of entropically regularized schemes combined with penalization of the moment constraint and illustrate our theoretical findings by numerically solving in dimension one, the Brenier-Strassen problem of Gozlan and Juillet and a family of problems which interpolates between monotone transport and left-curtain martingale coupling of Beiglböck and Juillet. This talk is based on a recent joint work with Hugo Malamut and Maxime Sylvestre.

The Moment-SOS hierarchy for computing: I: Mixtures of Gaussians closest (in W_2-Wasserstein distance) to a given measure. II: The total variation distance between two given probability measures

• Jean-Bernard Lasserre (CNRS)

Room: Salle des Thèses We present two recent applications of the Moment-SOS hierarchy. I. We first consider an optimal transport formulation for computing mixtures of Gaussians that minimize the W_2-Wasserstein distance to a given measure. II. We next consider the problem of computing the total variation between two given measures. For each problem we provide an associated hierarchy of semidefinite relaxations that converges to the desired result. Importantly, in both cases the support of the input measures is not assumed to be compact. Finally, the approach for problem II can also be used to solve problem I with the TV distance rather than the W_2 Wasserstein distance.