# Stochastic Optimization under Distributional Drift

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 59 references that are in the map.
- First posted on arXiv 16 Aug 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Stochastic Optimization for Performative Prediction](https://mlsanity.com/paper/2006.06887/) (2020)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Stochastic optimization with decision-dependent distributions](https://mlsanity.com/paper/2011.11173/) (2020)
- [Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions](https://mlsanity.com/paper/2006.05876/) (2020)
- [Online Projected Gradient Descent for Stochastic Optimization with Decision-Dependent Distributions](https://mlsanity.com/paper/2107.09721/) (2021)
- [Gaming Helps! Learning from Strategic Interactions in Natural Dynamics](https://mlsanity.com/paper/2002.07024/) (2020)
- [Using Statistics to Automate Stochastic Optimization](https://mlsanity.com/paper/1909.09785/) (2019)
- [Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise](https://mlsanity.com/paper/1901.08788/) (2019)
- [Adaptive Sequential Stochastic Optimization](https://mlsanity.com/paper/1610.01970/) (2016)
- [Bounds for the tracking error of first-order online optimization methods](https://mlsanity.com/paper/2003.02400/) (2020)

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

- [Making Decisions under Outcome Performativity](https://mlsanity.com/paper/2210.01745/) (2022)
- [Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality](https://mlsanity.com/paper/2207.04173/) (2022)
- [Performative Prediction with Bandit Feedback: Learning through Reparameterization](https://mlsanity.com/paper/2305.01094/) (2023)
- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2409.19212/) (2024)
- [A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2412.20017/) (2024)
- [Decision-Dependent Stochastic Optimization: The Role of Distribution Dynamics](https://mlsanity.com/paper/2503.07324/) (2025)
- [Online Covariance Estimation in Nonsmooth Stochastic Approximation](https://mlsanity.com/paper/2502.05305/) (2025)
- [Explaining and Preventing Alignment Collapse in Iterative RLHF](https://mlsanity.com/paper/2605.04266/) (2026)
- [Distributionally Time-Varying Online Stochastic Optimization under Polyak-Lojasiewicz Condition with Application in Conditional Value-at-Risk Statistical Learning](https://mlsanity.com/paper/2309.09411/) (2023)
- [On the Convergence of Adam-Type Algorithm for Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2503.03908/) (2025)
- [Adapt or Forget: Provable Tradeoffs Between Adam and SGD in Nonstationary Optimization](https://mlsanity.com/paper/2605.04269/) (2026)
- [Distributional Drift Detection in Medical Imaging with Sketching and Fine-Tuned Transformer](https://mlsanity.com/paper/2408.08456/) (2024)
- [Beyond Aggregate Drift: Optimal Client-Specific Windows in Federated Learning](https://mlsanity.com/paper/2610.15543/) (2026)
- [Minimax Optimality of Shampoo for Nonstationary Stochastic Optimization](https://mlsanity.com/paper/2610.16923/) (2026)

## Abstract (arXiv)

We consider the problem of minimizing a convex function that is evolving according to unknown and possibly stochastic dynamics, which may depend jointly on time and on the decision variable itself. Such problems abound in the machine learning and signal processing literature, under the names of concept drift, stochastic tracking, and performative prediction. We provide novel non-asymptotic convergence guarantees for stochastic algorithms with iterate averaging, focusing on bounds valid both in expectation and with high probability. The efficiency estimates we obtain clearly decouple the contributions of optimization error, gradient noise, and time drift. Notably, we identify a low drift-to-noise regime in which the tracking efficiency of the proximal stochastic gradient method benefits significantly from a step decay schedule. Numerical experiments illustrate our results.