Yilun Chen

Title: Beating the curse of dimensionality in data-driven online decision-making

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.

Benjamin Grimmer

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.