Stochastic Optimization with Decision-Dependent Distributions
From MaRDI portal
Abstract: Stochastic optimization problems often involve data distributions that change in reaction to the decision variables. This is the case for example when members of the population respond to a deployed classifier by manipulating their features so as to improve the likelihood of being positively labeled. Recent works on performative prediction have identified an intriguing solution concept for such problems: find the decision that is optimal with respect to the static distribution that the decision induces. Continuing this line of work, we show that typical stochastic algorithms -- originally designed for static problems -- can be applied directly for finding such equilibria with little loss in efficiency. The reason is simple to explain: the main consequence of the distributional shift is that it corrupts algorithms with a bias that decays linearly with the distance to the solution. Using this perspective, we obtain sharp convergence guarantees for popular algorithms, such as stochastic gradient, clipped gradient, proximal point, and dual averaging methods, along with their accelerated and proximal variants. In realistic applications, deployment of a decision rule is often much more expensive than sampling. We show how to modify the aforementioned algorithms so as to maintain their sample efficiency while performing only logarithmically many deployments.
Recommendations
- Stochastic Saddle Point Problems with Decision-Dependent Distributions
- Bayesian Stochastic Gradient Descent for Stochastic Optimization with Streaming Input Data
- A Pareto dominance principle for data-driven optimization
- Robust sample average approximation
- Distribution-free algorithms for predictive stochastic programming in the presence of streaming data
Cited in
(7)- Accelerated gradient methods with absolute and relative noise in the gradient
- Stochastic monotone inclusion with closed loop distributions
- Performative prediction: past and future
- Intermediate gradient methods with relative inexactness
- Holdout sets for safe predictive model updating
- A novel arctic fox survival strategy inspired optimization algorithm
- Numerical methods for stochastic optimization problems with decision-dependent distributions under large delays
This page was built for publication: Stochastic Optimization with Decision-Dependent Distributions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199279)
