ABSTRACT. L’apprentissage statistique se formule naturellement comme un problème d’optimisation, qui cherche à minimiser le taux d’erreur sur les données observées, typiquement de grande taille. Si pour les modèles linéaires, la fonction objectif est convexe, elle ne l’est pas pour des modèles non-linéaires comme les réseaux de neurones. Dans cet exposé, je présenterai certains développements récents liés à ces deux situations.

ABSTRACT. We will introduce in this presentation an extension the formulation of Sinkhorn divergences to the unbalanced setting of arbitrary positive measures, providing both theoretical and algorithmic advances. Sinkhorn divergences, introduced in [1], leverage the entropic regularization of Optimal Transport (OT) to define geometric loss functions. They are differentiable, cheap to compute and do not suffer from the curse of dimensionality, while maintaining the geometric properties of OT, in particular they metrize the weak ∗ convergence. Extending these divergences to the unbalanced setting is of utmost importance since most applications in data sciences require to handle both transportation and creation/destruction of mass. This includes for instance problems as diverse as shape registration in medical imaging, density fitting in statistics, generative modeling in machine learning, and particles flows involving birth/death dynamics. Our first set of contributions is the definition and the theoretical analysis of the unbalanced Sinkhorn divergences. They enjoy the same properties as the balanced divergences (classical OT), which are obtained as a special case. Indeed, we show that they are convex, differentiable and metrize the weak ∗ convergence. Our second set of contributions studies generalized Sinkhorn iterations, which enable a fast, stable and massively parallelizable algorithm to compute these divergences. We show, under mild assumptions, a linear rate of convergence, independent of the number of samples, i.e. which can cope with arbitrary input measures. We also highlight the versatility of this method, which takes benefit from the latest advances in term of GPU computing, for instance through the KeOps library for fast and scalable kernel operations.

ABSTRACT. Comparing data defined over space and time is notoriously hard. It involves quantifying both spatial and temporal variability while taking into account the chronological structure of the data. Dynamic Time Warping (DTW) computes a minimal cost alignment between time series that preserves the chronological order but is inherently blind to spatio-temporal shifts. In this paper, we propose Spatio-Temporal Alignments (STA), a new differentiable formulation of DTW that captures spatial and temporal variability. Spatial differences between time samples are captured using regularized Optimal transport. While temporal alignment cost exploits a smooth variant of DTW called soft-DTW. We show how smoothing DTW leads to alignment costs that increase quadratically with time shifts. The costs are expressed using an unbalanced Wasserstein distance to cope with observations that are not probabilities. Experiments on handwritten letters and brain imaging data confirm our theoretical findings and illustrate the effectiveness of STA as a dissimilarity for spatio-temporal data.

ABSTRACT. In this work, we aim at extending reinforcement learning (RL) methods to some state-constrained nonlinear optimal control problems. An important feature of these methods is that they do not need to discretize the state space and their complexity do not grow with the dimension of the state vector. In [2, 3], the RL methods have been analysed for control problems without state constraints. In our work, we extend the RL to control problems in presence of ponctual state constraints. For these problems, it is known that the value function may be discontinuous. However, following [1], one can describe precisely the value function and its epigraph by using an auxiliary control problem whose value function is Lipschitz continuous. We first extend the optimistic planning algorithm to solve the auxiliary control problem. Then we use this approach to get an approximation of the original control problem with state-constraints and without any controllability assumption. Furthermore, we establish some convergence guarantees and complexity results for our proposed optimistic planning algorithm similar to those presented in [2, 3]. Finally we illustrate our method on some nonlinear optimal control problems.

ABSTRACT. We introduce a deflated version of value iteration, which allows one to solve mean-payoff problems, including both Markov decision processes and perfect information zero-sum stochastic games. This method requires the existence of a distinguished state which is accessible from all initial states and for all policies; it differs from the classical relative value iteration algorithm for mean payoff problems in that it does not need any primitivity or geometric ergodicity condition. Our method is based on a reduction from the mean payoff problem to a discounted problem by a Doob h-transform, combined with a deflation technique and non-linear spectral theory results (Collatz-Wielandt characterization of the eigenvalue), inspired by~\cite{AG13}. In this way, we provide a new method {\em Deflated Value Iteration} that allows to extend complexity results from the discounted to the mean payoff case. In particular, Sidford, Wang, Wu and Ye~\cite{SWWY18} developed recently an algorithm combining value iteration with variance reduction techniques to solve discounted Markov decision processes in sublinear time when the discount factor is fixed. We combine deflated value iteration with variance reduction techniques to obtain sublinear algorithms for mean payoff stochastic games in which the first hitting times of a distinguished state are bounded a priori.

A first account of the present work can be found in~\cite{CDCpaper/arxiv}.

ABSTRACT. We discuss the solution of nonconvex mixed integer quadratic optimization problems. The approach that Gurobi takes on solving such problems to global optimality is based on the McCormick relaxation of bilinear constraints: Each quadratic constraint is reformulated as a set of bilinear constraints, and their McCormick relaxations are then used within a branch-and-bound algorithm. We outline the key algorithmic components that are involved: Reformulations, branching rules and cutting planes.

ABSTRACT. Chance constraints are a valuable tool for the design of safe and robust decisions in uncertain environments. In this talk, we propose an exact reformulation of a general chance constrained problem as a convex bilevel program. We then derive a tractable penalty approach for such problems. We finally release an open-source python toolbox with fast computational procedures.

ABSTRACT. Many problems in machine learning or linear inverse problems are formulated as composite non-smooth optimization problems. The non-smoothness is chosen to enforce some desirable structure on the solution, but it also affects the iterates produced by optimization methods. In this talk, we discuss the conditions under which the Proximal Gradient algorithm and its accelerated counterpart are able to collect this structure and how they do so.

ABSTRACT. Variational inequalities (VIs) offer a flexible framework for modeling equilibrium problems, with applications ranging from economics, game theory to machine learning, among others. In this setting, the optimal O(1/t) rate is achieved by the Extra-Gradient (EG) algorithm of Korpelevich when the involved operator is monotone. However, EG requires two oracle calls per iteration, incurring an extra cost that can be significant in some applications. Aiming to alleviate this cost, several algorithms have been proposed as surrogates of EG with only a single oracle call per iteration, with notably the example of Popov’s modified Arrow-Hurwicz method.

In this talk, we (i) develop a synthetic view of such Single-call Extra-Gradient (1-EG) algorithms, and (ii) show that they enjoy similar convergence guarantees as the standard EG algorithm for both deterministic and stochastic problems. Most importantly, we prove that the last iterate of 1-EG methods enjoys O(1/t) local convergence to solutions of stochastic, non-monotone problems satisfying a second-order sufficient condition. The algorithms that are covered include the optimistic gradient method, the reflected gradient method and naturally Popov’s modified Arrow-Hurwicz method.

ABSTRACT. We introduce a model of dynamic routing games under symmetric incomplete information. It consists in a routing game, played repeatedly in discrete time, in which cost functions are determined by an unknown state of the world. At each stage, a new mass of players routes over the network, publicly revealing its realized equilibrium costs. Our objective is to study how information aggregates according to the equilibrium dynamics and to which extent a centralized information system can learn about the state of the world. We define several forms of learning -- whether agents eventually learn the state of the world or act as in full information -- and provide simple examples showing that in the general case, with a non-atomic set of players, learning may fail and routing may be inefficient even in the looser sense. This contrasts with the atomic case, in which a folk theorem ensures players can learn the game parameters. In a non-atomic setup, learning cannot be ensured unless there is an additional source of randomness to incentivize exploration of the network. We show that this role can be fulfilled by an exogenous source of randomness in the game. We first explore the case of a variable and unbounded demand size. Our main result proves that under some network topology condition and costs unboundedness, a variable and unbounded demand is sufficient to ensure learning. This theorem can be adapted whether costs are observed edge by edge or path by path. We further extend this result to infinite state spaces. We additionally provide examples to show these conditions are tight. In a second variant of our model, we connect our work with the behavioural learning and cascade literature à la Smith and Sorensen and show that if instead of having random demand size, costs are observed with some unbounded noise, then learning may occur under some conditions on the distribution of noises.

ABSTRACT. Costly-signaling games have a remarkably wide range of applications, from education as a costly signal in the job market over handicaps as a signal for fitness in mate selection to politeness in language. While the use of game-theoretic equilibrium analysis in such models is often justified by some intuitive dynamic argument, the formal analysis of evolutionary dynamics in costly-signaling games has only recently gained more attention. In this paper, we study evolutionary dynamics in two basic classes of games with two states of nature, two signals, and two possible reactions in response to signals: a discrete version of Spence's (1973) model and a discrete version of Grafen's (1990) formalization of the handicap principle. We first use index theory to give a rough account of the dynamic stability properties of the equilibria in these games. Then, we study in more detail the replicator dynamics and to some extent the best-response dynamics. We relate our findings to equilibrium analysis based on classical, rationality-oriented methods of equilibrium refinement in signaling games.

ABSTRACT. We consider the problem of finding optimal classifiers in an adversarial setting where the class-1 data is generated by an attacker whose objective is not known to the defender---an aspects that are key to realistic applications but have so far been overlooked in the literature. To model this situation, we propose a Bayesian game framework where the defender chooses a classifier with no \emph{a priori} restriction on the set of possible classifiers. The key difficulty in the proposed framework is that the set of possible classifiers is exponential in the number of possible attacks. To counter this, we first show that Bayesian equilibria can be characterized completely via functional threshold classifiers with a small number of parameters that can be computed exactly in polynomial time. Given that the number of possible attacks can itself be exponentially large (relative to the number of features used for classification), we further develop a training method to compute provably approximately optimal classifiers in a scalable manner.

ABSTRACT. Gale and Shapley defined in 1962 a matching problem between two sets of distinct agents M and W (men and women, workers and firms, students and universities, nurses and hospitals, kidneys and patients, etc) who should be paired in a stable way, taking into account that each agent has a strict order of preference over those members of the opposite set. A matching u is stable if no unmatched couple can strictly improve its utility by being together compared to their utility in u. They constructed, thanks to an algorithm, a stable matching for every instance. In 1971, Shapley and Shubik considered an extension in which agents can do monetary transfers that can change their quasi-linear utility. A solution to this new problem is a pair (u,p) with u a matching between buyers and sellers and p a vector of monetary transfers. A solution is stable if no pair of unpaired agents can find a transfer which improves their utility compared with (u,p). In 2005, Milgrom and Hatfield extended this model to Matching with contracts in which agents define partners and bilateral contracts, from a set of possible options. They provide sufficient conditions on the set of contracts under which a stable allocation exists. Our article proposes a new extension by assuming that each couple (i,j) in M-W obtains its utility as the outcome of a strategic game G(i,j). In this approach, agents, beside choosing partners, play a strategic game in which they try to maximize their outcome under the constraint that the partner is satisfied and does not want to quit the relationship. A matching u is externally stable if no unmatched couple can deviate, i.e. to match together and play a strategy profile which provides them higher payoffs than the ones they have in u. This corresponds to the classical pairwise stability notion. The matching is internally stable if no player can, by changing her strategy inside the couple, increases her payoff without breaking the external stability of the couple. Mathematically, internal stability is simply a Nash equilibrium condition with outside option constraints. We provide a sufficient condition on a strategic game (called feasibility) under which there exists matching profiles that are externally and internally stable. We prove that the class of feasible games includes zero-sum games, potential games, infinitely repeated games and finite perfect information games. We also provide a 3 by 3 game in mixed strategies which is not feasible. Since monetary transfers can be interpreted as zero sum games, our model strictly includes Shapley-Shubik’s extension. Similarly, we also extend Milgrom-Hatfield’s model because any stable allocation can be mapped into a externally stable matching and conversely.

ABSTRACT. With the emergence of new renewable energies (as wind or solar generation), the electrical system is evolving from a situation based on controllable power plants (thermal, gas, hydro, etc.) connected to the transmission network to a new setting, where substantial uncontrollable generation facilities are connected to the distribution network, closer to the consumers. To contribute to this transformation, new local actors are rapidly multiplying potentially involving a great variety of devices: uncontrollable renewable generations; storage devices (batteries, Electric Vehicles smart charging systems, …); conventional plants (such as gas turbines or hydro plants); possibilities to adjust some consumers load (e.g. demand response, or direct control). In this new context, energy utilities are facing new practical issues requiring to develop suitable mathematical optimization tools.

ABSTRACT. Alternative Current Optimal Power Flow (ACOPF) is naturally formulated as a non-convex problem. In that context, solving (ACOPF) to global optimality remains a challenge when classic convex relaxations are not exact. We use semidefinite programming to build a quadratic convex relaxation of (ACOPF). We show that this quadratic convex relaxation has the same optimal value as the classical semidefinite relaxation of (ACOPF) which is known to be tight. In that context, we build a spatial branch-and-bound algorithm to solve (ACOPF) to global optimality that is based on a quadratic convex programming bound. An advantage of our approach is that we capture the strength of semidefinite programming bounds into a quadratic convex program that is known to be faster to solve.

ABSTRACT. Online Advertising heavily relies on auctions to sell advertising space. In this context, sellers (Ad Exchanges) and buyers (advertisers) repeatedly play one against each other at the rate of billions of auctions a day. In order to learn policies to play this game, not only the players (bidders and seller) need to formalize well the behavior of their opponents, but also face complex optimization problems: adversarial by definition, online by constraint.

ABSTRACT. It is well known that primal-dual interior-point algorithms for linear optimization can easily be extended to the case of symmetric conic optimization, as shown by Nesterov and Todd (NT) in their 1997 paper about self-scaled barriers. Although many convex optimization problems can be expressed using symmetric cones then models involving for instance exponential functions do not belong to the class of symmetric conic optimization problems. Therefore, several authors have suggested generalizations of the NT primal-dual interior-point algorithm to handle nonsymmetric cones such as the exponential cone. Based on this work we will present a generalization of the NT algorithm to the case of nonsymmetric conic optimization. Although we have no polynomial complexity proof for the suggested algorithm then it performs extremely well in practice as will be documented with computational results.

To summarize, this presentation should be interesting for users of convex optimization.