Session: Data-driven Methods for Optimization under Uncertainty
Chair: Meng Qi
Cluster: Optimization Under Uncertainty and Data-driven Optimization
Talk 1: Beyond Discretization: Learning the Optimal Solution Map
Speaker: Paul Grigas
Abstract: Many applications require minimizing a family of optimization problems, indexed by some hyperparameter vector, to obtain an entire solution map (or solution path). Traditional approaches proceed by discretizing and solving a series of optimization problems. We propose an alternative approach that parametrizes the solution map within a given function class and solves a single stochastic optimization problem to learn the entire solution map. Our method offers substantial complexity improvements over discretization. When using constant-step size SGD, the uniform error of our learned solution map relative to the true map exhibits linear convergence to a constant that diminishes as the expressiveness of the function class increases. In the case of a one-dimensional hyperparameter, we prove stronger results that demonstrate complexity improvements over the best known results for uniform discretization whenever the solution map is sufficiently smooth. Finally, we discuss other extensions including an adaptive variant of our method that sequentially adds basis functions, and we demonstrate strong numerical performance through experiments on imbalanced binary classification and portfolio optimization examples.
Talk 2: Decision-Focused Learning with Directional Gradients
Speaker: Michael Huang
Abstract: We propose a novel family of decision-aware surrogate losses, called Perturbation Gradient (PG) losses, for the predict-then-optimize framework. The key idea is to connect the expected downstream decision loss with the directional derivative of a particular plug-in objective, and then approximate this derivative using zeroth order gradient techniques. Unlike the original decision loss which is typically piecewise constant and discontinuous, our new PG losses is a Lipschitz continuous, difference of concave functions that can be optimized using off-the-shelf gradient-based methods. Most importantly, unlike existing surrogate losses, the approximation error of our PG losses vanishes as the number of samples grows. Hence, optimizing our surrogate loss yields a best-in-class policy asymptotically, even in misspecified settings. This is the first such result in misspecified settings, and we provide numerical evidence confirming our PG losses substantively outperform existing proposals when the underlying model is misspecified.
Talk 3: Norm-Free Exact Regularization and Applications in Data-Driven Optimization
Speaker: Meng Qi
Abstract: This paper revisits the theory of \textit{exact regularization} – where optimal solutions of a regularized convex optimization problem exhibit a phase transition phenomenon and eventually coincide with those of the original unregularized problem (under certain conditions).We examine this phenomenon from a norm-free perspective – instead of adopting norm-related assumptions, our results are established on conditions only involving Bregman divergence and convexity. We proved two key results: (1) a norm-free version of Lipschitz continuity of the regularized optimal solution, and (2) a phase-transition threshold for the exact regularization to hold that depends solely on intrinsic problem parameters. Notably, our norm-free framework generalizes classical norm-dependent conditions, such as strong convexity of the regularization function, and broadens applicability. Our theoretical results have applications in many data-driven optimization problems, for example to integrated prediction-optimization, inverse optimization, and decentralized optimization. Our results for exact regularization potentially lead to faster convergence or tighter error bounds in these settings.
