Joint seminar of the Optimization team of CERMICS (Ecole des Ponts

Paristech) and the Tropical team (INRIA Saclay & CMAP, Ecole

Polytechnique)

## Forthcoming sessions

## Gabriel Peyré (CNRS & Ecole Normale Supérieure, Paris)

### July 2nd, 10:30, Ecole Polytechnique (CMAP Seminar room)

The seminar will also be accessible online

## Scaling Optimal Transport for High dimensional Learning

Abstract:

Optimal transport (OT) has recently gained lot of interest in machine learning. It is a natural tool to compare in a geometrically faithful way probability distributions. It finds applications in both supervised learning (using geometric loss functions) and unsupervised learning (to perform generative model fitting). OT is however plagued by the curse of dimensionality, since it might require a number of samples which grows exponentially with the dimension. In this talk, I will explain how to leverage entropic regularization methods to define computationally efficient loss functions, approximating OT with a better sample complexity. More information and references can be found on the website of our book “Computational Optimal Transport”

## Eloise Berthier (INRIA & Ecole Normale Supérieure, Paris)

### July 2nd, 14:00, Ecole Polytechnique (Seminar room of CMAP)

## Max-Plus Linear Approximations for Deterministic Continuous-State Markov

Abstract :

We consider deterministic continuous-state Markov decision processes

(MDPs). We apply a max-plus linear method to approximate the value function

with a specific dictionary of functions that leads to an adequate

state-discretization of the MDP. This is more efficient than a direct

discretization of the state space, typically intractable in high dimension. We

propose a simple strategy to adapt the discretization to a problem instance,

thus mitigating the curse of dimensionality. We provide numerical examples

showing that the method works well on simple MDPs.

## Maël Forcier (CERMICS, Ecole des Ponts)

### July 2nd, 14:45, Ecole Polytechnique (CMAP Seminar room)

## Multistage Stochastic Linear Programming and Polyhedral Geometry

Abstract:

We show that the multistage linear problem (MSLP) with an arbitrary cost distribution is equivalent to a MSLP on a finite scenario tree.

Indeed, be studying the polyhedral structure of MSLP, we show that the cost distribution can be replaced by a discrete cost distribution, taking the expected value of the cost at each cone of a normal fan.

In particular, we show that the expected cost-to-go functions are polyhedral and affine on the cells of a chamber complex, which is independent

of the cost distribution. This leads to new complexity results, showing that MSLP is fixed-parameter tractable.

A dual approach in terms of fiber polyhedron is eventually presented to derive algorithms for two-time scale MSLP.

## Past sessions

## Kazuo Murota (The Institute of Statistical Mathematics, Tokyo)

### May 20th, 10:00, Online

## Multiple exchange property of gross substitutes valuations

with a proof by discrete convex analysis (Slides)

Abstract:

Discrete convex analysis (DCA) offers a general framework of discrete optimization,

combining the ideas from matroid theory and convex analysis. It has found applications

in many different areas including operations research, mathematical economics, and game

theory. The interaction between DCA and mathematical economics was initiated by

Danilov, Koshevoy, and Murota (2001), and accelerated by the crucial observation of Fujishige

and Yang (2003) that M-natural-concavity is equivalent to the gross substitutes (GS) property

of Kelso and Crawford (1982).

In this talk we show how an old question in economics was settled with

the DCA machinery. More concretely, we explain how the equivalence of the gross substitutes

condition to the strong no complementarities (SNC) condition of Gul and Stacchetti

(1999) can be proved with the use of the Fenchel-type duality theorem and the conjugacy

theorem in DCA.

The SNC condition means the multiple exchange property of a set function

f, saying that, for two subsets X and Y and a subset I of X-Y, there exists a subset J

of Y-X such that f((X-I)+J) +f((Y-J)+I) is not smaller than f(X) + f(Y).

This talk is intended to offer a glimpse at a technical interaction

between DCA and economics.

No preliminary knowledge of DCA is required.

## Guillaume Vigeral (Ceremade, Paris Dauphine)

### April 8th, 10:30, Online

## Structure of the sets of Nash equilibria of finite games; applications

to the complexity of some decision problems in game theory (Slides)

Abstract:

The set of Nash equilibrium payoffs of a finite game is always non

empty, compact and semialgebraic. We show that, for 3 players or more,

the reverse also holds: given E a subset of R^N that is non empty,

compact and semialgebraic, one constructs a finite N player game such

that E is its set of equilibrium payoffs. Related results also holds

when one consider only games with integral payoffs, or when the focus is

on equilibria instead of equilibrium payoffs.

We apply this result to understand the complexity class of some natural

decision problems on finite games.