# Stochastic Saddle Point Problems with Decision-Dependent Distributions

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 72 references that are in the map.
- First posted on arXiv 7 Jan 2022.

## Builds on (most cited first, 27 of 27)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [Outside the Echo Chamber: Optimizing the Performative Risk](https://mlsanity.com/paper/2102.08570/) (2021)
- [Stochastic Optimization for Performative Prediction](https://mlsanity.com/paper/2006.06887/) (2020)
- [Performative Prediction in a Stateful World](https://mlsanity.com/paper/2011.03885/) (2020)
- [Stochastic optimization with decision-dependent distributions](https://mlsanity.com/paper/2011.11173/) (2020)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression](https://mlsanity.com/paper/1804.02605/) (2018)
- [Bandit learning in concave N-person games](https://mlsanity.com/paper/1810.01925/) (2018)
- [Generalization Bounds for Stochastic Saddle Point Problems](https://mlsanity.com/paper/2006.02067/) (2020)
- [Online Projected Gradient Descent for Stochastic Optimization with Decision-Dependent Distributions](https://mlsanity.com/paper/2107.09721/) (2021)
- [Optimization and Learning with Information Streams: Time-varying Algorithms and Applications](https://mlsanity.com/paper/1910.08123/) (2019)
- [Online Proximal-ADMM For Time-varying Constrained Convex Optimization](https://mlsanity.com/paper/2005.03267/) (2020)
- [Robust Accelerated Primal-Dual Methods for Computing Saddle Points](https://mlsanity.com/paper/2111.12743/) (2021)
- [Online Primal-Dual Methods with Measurement Feedback for Time-Varying Convex Optimization](https://mlsanity.com/paper/1804.05159/) (2018)
- [Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization](https://mlsanity.com/paper/1912.01698/) (2019)
- [Bounds for the tracking error of first-order online optimization methods](https://mlsanity.com/paper/2003.02400/) (2020)
- [Asynchronous Multi-Agent Primal-Dual Optimization](https://mlsanity.com/paper/1606.01993/) (2016)
- [Nash and Wardrop equilibria in aggregative games with coupling constraints](https://mlsanity.com/paper/1702.08789/) (2017)
- [Online Stochastic Optimization for Unknown Linear Systems: Data-Driven Synthesis and Controller Analysis](https://mlsanity.com/paper/2108.13040/) (2021)
- [Adaptive Sequential Optimization with Applications to Machine Learning](https://mlsanity.com/paper/1509.07422/) (2015)
- [Adaptive Sequential Machine Learning](https://mlsanity.com/paper/1904.02773/) (2019)

## Built on by (most cited first, 6 of 6)

- [Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality](https://mlsanity.com/paper/2207.04173/) (2022)
- [Zero-Regret Performative Prediction Under Inequality Constraints](https://mlsanity.com/paper/2309.12618/) (2023)
- [General Tail Bounds for Non-Smooth Stochastic Mirror Descent](https://mlsanity.com/paper/2312.07142/) (2023)
- [Decision-Dependent Stochastic Optimization: The Role of Distribution Dynamics](https://mlsanity.com/paper/2503.07324/) (2025)
- [Emergent specialization from participation dynamics and multi-learner retraining](https://mlsanity.com/paper/2206.02667/) (2022)
- [Strategic Usage in a Multi-Learner Setting](https://mlsanity.com/paper/2401.16422/) (2024)

## Abstract (arXiv)

This paper focuses on stochastic saddle point problems with decision-dependent distributions. These are problems whose objective is the expected value of a stochastic payoff function and whose data distribution drifts in response to decision variables--a phenomenon represented by a distributional map. A common approach to accommodating distributional shift is to retrain optimal decisions once a new distribution is revealed, or repeated retraining. We introduce the notion of equilibrium points, which are the fixed points of this repeated retraining procedure, and provide sufficient conditions for their existence and uniqueness. To find equilibrium points, we develop deterministic and stochastic primal-dual algorithms and demonstrate their convergence with constant step-size in the former and polynomial decay step-size schedule in the latter. By modeling errors emerging from a stochastic gradient estimator as sub-Weibull random variables, we provide error bounds in expectation and in high probability that hold for each iteration. Without additional knowledge of the distributional map, computing saddle points is intractable. Thus we propose a condition on the distributional map--which we call opposing mixture dominance--that ensures that the objective is strongly-convex-strongly-concave. Finally, we demonstrate that derivative-free algorithms with a single function evaluation are capable of approximating saddle points