# Fast Rates for Contextual Linear Optimization

arXiv: https://arxiv.org/abs/2011.03030 · HTML: https://mlsanity.com/paper/2011.03030/

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2020.

## Built on by (most cited first, 30 of 43)

- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [Provable Offline Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.14816/) (2023)
- [Risk Bounds and Calibration for a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2108.08887/) (2021)
- [Fast Rates for the Regret of Offline Reinforcement Learning](https://mlsanity.com/paper/2102.00479/) (2021)
- [Integrated Conditional Estimation-Optimization](https://mlsanity.com/paper/2110.12351/) (2021)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Estimate-Then-Optimize versus Integrated-Estimation-Optimization versus Sample Average Approximation: A Stochastic Dominance Perspective](https://mlsanity.com/paper/2304.06833/) (2023)
- [Decision-Focused Learning with Directional Gradients](https://mlsanity.com/paper/2402.03256/) (2024)
- [Data-Driven Sample Average Approximation with Covariate Information](https://mlsanity.com/paper/2207.13554/) (2022)
- [Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming](https://mlsanity.com/paper/2301.11260/) (2023)
- [Online Contextual Decision-Making with a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2206.07316/) (2022)
- [Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning](https://mlsanity.com/paper/2106.01723/) (2021)
- [Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage](https://mlsanity.com/paper/2302.02392/) (2023)
- [Dissecting the Impact of Model Misspecification in Data-driven Optimization](https://mlsanity.com/paper/2503.00626/) (2025)
- [What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization](https://mlsanity.com/paper/2505.21692/) (2025)
- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [The Central Role of the Loss Function in Reinforcement Learning](https://mlsanity.com/paper/2409.12799/) (2024)
- [Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel-Young Loss Perspective and Gap-Dependent Regret Analysis](https://mlsanity.com/paper/2501.13648/) (2025)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [Contextual Online Uncertainty-Aware Preference Learning for Human Feedback](https://mlsanity.com/paper/2504.19342/) (2025)
- [Optimizer's Information Criterion: Dissecting and Correcting Bias in Data-Driven Optimization](https://mlsanity.com/paper/2306.10081/) (2023)
- [The Bias-Variance Tradeoff in Data-Driven Optimization: A Local Misspecification Perspective](https://mlsanity.com/paper/2510.18215/) (2025)
- [Decision-Focused Bias Correction for Fluid Approximation](https://mlsanity.com/paper/2512.15726/) (2025)
- [Decision-Focused Sequential Experimental Design: A Directional Uncertainty-Guided Approach](https://mlsanity.com/paper/2602.05340/) (2026)
- [A Solver-Free Training Method for Predict-then-Optimize](https://mlsanity.com/paper/2606.19587/) (2026)
- [Regret Bounds and Experimental Design for Estimate-then-Optimize](https://mlsanity.com/paper/2210.15576/) (2022)
- [DFF: Decision-Focused Fine-tuning for Smarter Predict-then-Optimize with Limited Data](https://mlsanity.com/paper/2501.01874/) (2025)
- [Solve Smart, Not Often: Policy Learning for Costly MILP Re-solving](https://mlsanity.com/paper/2509.23470/) (2025)
- [Functional Natural Policy Gradients](https://mlsanity.com/paper/2603.28681/) (2026)
- [Decision-Focused Learning: When and Why Traditional Prediction Models Fail](https://mlsanity.com/paper/2606.21773/) (2026)

## Abstract (arXiv)

Incorporating side observations in decision making can reduce uncertainty and boost performance, but it also requires we tackle a potentially complex predictive relationship. While one may use off-the-shelf machine learning methods to separately learn a predictive model and plug it in, a variety of recent methods instead integrate estimation and optimization by fitting the model to directly optimize downstream decision performance. Surprisingly, in the case of contextual linear optimization, we show that the naive plug-in approach actually achieves regret convergence rates that are significantly faster than methods that directly optimize downstream decision performance. We show this by leveraging the fact that specific problem instances do not have arbitrarily bad near-dual-degeneracy. While there are other pros and cons to consider as we discuss and illustrate numerically, our results highlight a nuanced landscape for the enterprise to integrate estimation and optimization. Our results are overall positive for practice: predictive models are easy and fast to train using existing tools, simple to interpret, and, as we show, lead to decisions that perform very well.