Learning Decision-Focused Uncertainty Sets in Robust Optimization
math.OC
Submitted: 2023-05-30
Updated: 2026-11-01
Code: https://github.com/stellatogrp/cvxro_experiments
License: http://creativecommons.org/licenses/by/4.0/
The gist: We propose a data-driven technique to automatically learn tractable contextual uncertainty sets in robust optimization, for a family of problems with both objective and constraint uncertainty.
Abstract
We propose a data-driven technique to automatically learn tractable contextual uncertainty sets in robust optimization, for a family of problems with both objective and constraint uncertainty. This decision-focused method reshapes the uncertainty sets by optimizing for both worst-case and average-case performance while guaranteeing constraint satisfaction with high probability via a conditional value-at-risk constraint. We solve the resultant constrained learning problem using a stochastic augmented Lagrangian method that relies on differentiating the solutions of the robust optimization problems with respect to the parameters of the uncertainty set. Due to the nonsmooth and nonconvex nature of the augmented Lagrangian function, we apply the nonsmooth conservative implicit function theorem to establish that, under regularity and boundedness assumptions, the accumulation points of the resulting algorithm are feasible solutions of the constrained learning problem when the penalty parameters remain bounded, and stationary points of the constraint violation otherwise. Using a covering argument with Hoeffding's inequality, we show both marginal and conditional finite-sample probabilistic guarantees of constraint satisfaction for any approximately feasible solution. We also characterize when a decision-focused set is worth learning. In the proposed settings, numerical experiments show that our method outperforms traditional approaches in data-driven robust optimization in terms of out-of-sample performance.
Sources
- End-to-end Conditional Robust Optimization
- A Survey of Contextual Optimization Methods for Decision Making under Uncertainty
- Analysis of k-Nearest Neighbor Distances with Application to Entropy Estimation
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise