Fast Rates for Contextual Linear Optimization
- URL: http://arxiv.org/abs/2011.03030v3
- Date: Tue, 31 Aug 2021 17:39:57 GMT
- Title: Fast Rates for Contextual Linear Optimization
- Authors: Yichun Hu, Nathan Kallus, Xiaojie Mao
- Abstract summary: We show that a naive plug-in approach achieves regret convergence rates that are significantly faster than methods that directly optimize downstream decision performance.
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.
- Score: 52.39202699484225
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- From Function to Distribution Modeling: A PAC-Generative Approach to
Offline Optimization [30.689032197123755]
This paper considers the problem of offline optimization, where the objective function is unknown except for a collection of offline" data examples.
Instead of learning and then optimizing the unknown objective function, we take on a less intuitive but more direct view that optimization can be thought of as a process of sampling from a generative model.
arXiv Detail & Related papers (2024-01-04T01:32:50Z) - Decision-focused predictions via pessimistic bilevel optimization: a computational study [0.7499722271664147]
Uncertainty in optimization parameters is an important and longstanding challenge.
We build predictive models that measure a emphregret measure on decisions taken with them.
We show various computational techniques to achieve tractability.
arXiv Detail & Related papers (2023-12-29T15:05:00Z) - Predict-Then-Optimize by Proxy: Learning Joint Models of Prediction and
Optimization [59.386153202037086]
Predict-Then- framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving.
This approach can be inefficient and requires handcrafted, problem-specific rules for backpropagation through the optimization step.
This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by predictive models.
arXiv Detail & Related papers (2023-11-22T01:32:06Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks.
One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver.
This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
arXiv Detail & Related papers (2023-01-28T01:50:42Z) - A Note on Task-Aware Loss via Reweighing Prediction Loss by
Decision-Regret [11.57423546614283]
We propose a decision-aware version of predict-then-optimize.
We reweigh the prediction error by the decision regret incurred by an (unweighted) pilot estimator of costs.
We show that this approach can lead to improvements over a "predict-then-optimize" framework.
arXiv Detail & Related papers (2022-11-09T18:59:35Z) - Careful! Training Relevance is Real [0.7742297876120561]
We propose constraints designed to enforce training relevance.
We show through a collection of experimental results that adding the suggested constraints significantly improves the quality of solutions.
arXiv Detail & Related papers (2022-01-12T11:54:31Z) - The Perils of Learning Before Optimizing [16.97597806975415]
We show how prediction models can be learned end-to-end by differentiating through the optimization task.
We show that the performance gap between a two-stage and end-to-end approach is closely related to the emphprice of correlation concept in optimization.
arXiv Detail & Related papers (2021-06-18T20:43:47Z) - Automatically Learning Compact Quality-aware Surrogates for Optimization
Problems [55.94450542785096]
Solving optimization problems with unknown parameters requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values.
Recent work has shown that including the optimization problem as a layer in a complex training model pipeline results in predictions of iteration of unobserved decision making.
We show that we can improve solution quality by learning a low-dimensional surrogate model of a large optimization problem.
arXiv Detail & Related papers (2020-06-18T19:11:54Z) - Global Optimization of Gaussian processes [52.77024349608834]
We propose a reduced-space formulation with trained Gaussian processes trained on few data points.
The approach also leads to significantly smaller and computationally cheaper sub solver for lower bounding.
In total, we reduce time convergence by orders of orders of the proposed method.
arXiv Detail & Related papers (2020-05-21T20:59:11Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
We propose a systematic method to transform operations into operations that are differentiable and never locally constant.
Our approach relies on perturbeds, and can be used readily together with existing solvers.
We show how this framework can be connected to a family of losses developed in structured prediction, and give theoretical guarantees for their use in learning tasks.
arXiv Detail & Related papers (2020-02-20T11:11:32Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.