PGMODays 2018
November20th and 21th, 2018
Invited speakers :
- Noureddine EL KAROUI, Criteo AI Lab & UC, Berkeley
- Damien ERNST, University of Liège
- Brigitte JAUMARD, Concordia University Montreal
- Daniel KUHN, Ecole Polytechnique Fédérale de Lausanne
- Rekha THOMAS, University of Washington
Program PGMODays
Noureddine EL KAROUI - Criteo Al Lab & UC, Berkeley
Auction theory from the bidder standpoint
Most classical auction theory has been developed from the standpoint of the seller, trying to understand how to optimize auctions to maximize seller revenue for instance. Billions of auctions are now run on the internet everyday and this creates a need to better understand auctions from the bidder perspective. In this talk I will present some recent results on this question, showing for instance that auctions that are reputed to be truthful are not truthful anymore when the seller optimizes the auction format based on bidders' past bids, provide explicit (and simple to implement) shading strategies that improve bidders' utility and discuss various equilibrium questions. No prior knowledge of auction theory is assumed and the talk will be self-contained. Based on joint works with Thomas Nedelec, Marc Abeille, Clément Calauzènes, Benjamin Heymann and Vianney Perchet while doing research at Criteo.
Damien ERNST - University of Liège
Reinforcement learning, energy systems and deep neural nets
Reinforcement leaning is a highly-successful subfield of artificial intelligence where an agent is ought to interact with its environment to maximize a sum of rewards. In this talk, Damien Ernst will argue that this learning paradigm can be very powerful to solve many decision-making problems in the energy sector, as for example investment problems, the design of bidding strategies for playing with the intraday electricity market or problems related to the control of microgrids. He will also describe some very recent progresses in the field on deep reinforcement learning that could be used to foster the performances of reinforcement learning agents when confronted with environments that can exhibit sudden changes in their dynamics, as it is often the case with energy systems.
Brigitte JAUMARD, Concordia University Montreal
Optimization Models and Algorithms for Network Reconfiguration
In future cognitive networks, thanks to Software Defined Networking (SDN), network reconfiguration and traffic migration will be triggered by intelligent software tools. This requires efficient algorithms, but also clear objectives in order to know went trigger and how to conduct network reconfiguration. In this talk, we will discuss seamless network reconfiguration, as well as various minimum disruption objectives, when a seamless reconfiguration cannot be conducted, i.e., minimize \textit{(i)} the number of disruptions, \textit{(ii)} the maximum number of concurrent disruptions, \textit{(iii)} the overall duration of the disruptions, and \textit{(iv)} the maximum disruption duration. We survey these four different minimum disruption objectives for the RWA (Routing and Wavelength Assignment) and RSA (Routing and Spectrum Assignment) lightpath migration in optical networks. For each of them, the defragmentation problem can be reduced to a graph theory problem (Minimum Feedback Vertex, Vertex Separation, Graph Bandwidth, Minimum Sum Cut) or formulated as an Integer Linear Program. We investigate the most efficient available exact algorithms. For seamless reconfiguration, we will discuss a nested decomposition scheme. Extensive numerical experiments are conducted on different traffic and network instances, in order to compare the level of disruption entailed by the different objectives.
Daniel KUHN - Ecole Polytechnique Fédérale de Lausanne
Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations
We consider stochastic programs where the distribution of the uncertain parameters is only observable through a finite training dataset. Using the Wasserstein metric, we construct a ball in the space of (multivariate and non-discrete) probability distributions centered at the uniform distribution on the training samples, and we seek decisions that perform best in view of the worst-case distribution within this Wasserstein ball. The state-of-the-art methods for solving the resulting distributionally robust optimization problems rely on global optimization techniques, which quickly become computationally excruciating. In this paper we demonstrate that, under mild assumptions, the distributionally robust optimization problems over Wasserstein balls can in fact be reformulated as finite convex programs - in many interesting cases even as tractable linear programs. Leveraging recent measure concentration results, we also show that their solutions enjoy powerful finite-sample performance guarantees. Our theoretical results are exemplified in mean-risk portfolio optimization, uncertainty quantification and machine learning.
Rekha THOMAS - University of Washington
Algebraic Vision
Algebraic Vision is an emerging viewpoint of problems in computer vision that aims to examine polynomial models in vision through the lens of algebra. A key problem in computer vision is the estimation of the three-dimensional shape of a world scene from images and the parameters (position, orientation, etc.) of the cameras that captured them. This problem, studied under the name structure-from-motion or multi-view geometry, has its origins in photogrammetry and perspective drawings. The modeling language for these problems is projective geometry, which naturally leads to polynomial models with rich and beautiful structure that beg for algebraic tools. In this talk I will show some of the surprising structure, properties, and algorithmic successes that have emerged from this algebraic viewpoint.