Achieving First-Order Statistical Improvements in Data-Driven Optimization: From No-Free-Lunch to Amplified Decision Perturbation
Henry Lam, Tianyu Wang
math.OC, stat.ML
Submitted: 2026-08-05
Code: https://github.com/opimwue/ddop
License: http://creativecommons.org/licenses/by/4.0/
The gist: Recent proliferation of data-optimization integration has led to a range of methods that aim to improve the statistical performance of data-driven optimization decisions.
Terminology
Abstract
Recent proliferation of data-optimization integration has led to a range of methods that aim to improve the statistical performance of data-driven optimization decisions. However, while many of these methods are motivated intuitively from a robustness or regularization perspective, their resulting statistical benefits are often unclear and, even if available, are established on a case-by-case basis. We provide a systematic dissection of data-driven optimization formulations using the view of "directionally perturbed" empirical optimization (EO). Specifically, this umbrella of formulations, which we call "EO+", covers many existing data-driven optimization methods, including regularization, distributionally robust optimization, transfer learning, and analogous methods for contextual optimization. On the one hand, we argue that without additional, correctly specified, side information, any EO+ method can result in at most second-order improvements. This provides a negative conclusion, namely ``no free lunch is possible", on the statistical power of EO+. On the other hand, we show that when leveraging side information that is geometrically effective, achieving first-order improvements is possible by choosing hyperparameters that are significantly larger than what is typically suggested in the literature. Moreover, we construct a principled methodology based on excess risk estimation, via either system knowledge or bootstrap resampling, to maximize the first-order gain. We demonstrate how this gain connects to the control-variate principle, a variance reduction technique in the Monte Carlo simulation literature, which helps explain why geometrically effective side information is necessary.
Sources
- Post-estimation Adjustments in Data-driven Decision-making with Applications in Pricing
- Invariant Risk Minimization
- Dissecting the Impact of Model Misspecification in Data-driven Optimization
- Distributionally Robust Optimization
- Learning from a Biased Sample
- A Pareto Dominance Principle for Data-Driven Optimization
- Regularization for Adversarial Robust Learning
- Rethinking Distribution Shifts: Empirical Analysis and Modeling for Tabular Data
Related papers
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
- Incremental Learning in Mirror Flows
- Beyond Aggregate Drift: Optimal Client-Specific Windows in Federated Learning
- Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
- Second-Order Optimization with Asynchronous Curvature