ORIE Colloquium - Yilun Chen/Benjamin Grimmer (Cornell University), February 16, 2021
From Henry Lam on February 16th, 2021
Abstract: Data-driven online decision-making tasks arise frequently in various practical settings in OR/OM, finance, healthcare, etc. Such tasks often boil down to solving certain stochastic dynamic programs (DPs) with prohibitively large state space, suffering from the curse of dimensionality. Most existing approaches (e.g. ADP, deep learning) either scale poorly (i.e. exponentially in the time horizon T and/or the underlying dimension), or have limited performance guarantee. We overcome this fundamental computational obstacle for the celebrated problem of high-dimensional optimal stopping, an important special case of online decision-making, proving its theoretical tractability. We propose a simulation-based algorithm that can output epsilon-optimal stopping policies and value function approximations, with sample and computational complexity polynomial in T and effectively independent of the underlying state space. Our algorithm builds on a novel expansion representation (as an infinite sum) of the optimal stopping value, which is fundamentally different from the standard backward-induction-based formula, and enjoys the following properties: 1. each term in the expansion is the expectation of an elegant recursively defined infimum; 2. the first k terms only require T^k samples to approximate; and 3. Truncating at the first k terms yields a (normalized) error of 1/k. Our approach also draws a novel connection between network flow theory in combinatorial optimization and the classical martingale duality theory for stopping problems. Furthermore, building on this approach, we devise efficient and provably near-optimal algorithms for online decision-making problems with more complicated decision structures, including those arising in dynamic pricing and online combinatorial optimization.
Title: The Landscape of the Proximal Point Method for Nonconvex-Nonconcave Minimax Optimization
Abstract: Minimax optimization has become a central tool for modern machine learning with applications in generative adversarial networks, robust training, etc. These applications are often nonconvex-nonconcave, but the existing theory is unable to identify and deal with the fundamental difficulties this poses.
In this talk, we will
overcome these limitations, describing the convergence landscape of the classic
proximal point method on nonconvex-nonconcave minimax problems. Our key
theoretical insight lies in identifying a modified objective, generalizing the
Moreau envelope, that smooths the original objective and convexifies and
concavifies it based on the interaction between the minimizing and maximizing
variables. When interaction is sufficiently strong, we derive global linear
convergence guarantees. When interaction is weak, we derive local linear
convergence guarantees under proper initialization. Between these two settings,
we show undesirable behaviors like divergence and cycling can occur.