mlsanityData to 7 Oct 2026

Non-stationary Stochastic Optimization

arXiv 1307.5449 ↗First posted 20 Jul 2013math.PR cs.LG stat.MLcited by 173

Not on the map. Why?

Abstract (arXiv)

We consider a non-stationary variant of a sequential stochastic optimization problem, in which the underlying cost functions may change along the horizon. We propose a measure, termed variation budget, that controls the extent of said change, and study how restrictions on this budget impact achievable performance. We identify sharp conditions under which it is possible to achieve long-run-average optimality and more refined performance measures such as rate optimality that fully characterize the complexity of such problems. In doing so, we also establish a strong connection between two rather disparate strands of literature: adversarial online convex optimization; and the more traditional stochastic approximation paradigm (couched in a non-stationary setting). This connection is the key to deriving well performing policies in the latter, by leveraging structure of optimal policies in the former. Finally, tight bounds on the minimax regret allow us to quantify the "price of non-stationarity," which mathematically captures the added complexity embedded in a temporally changing environment versus a stationary one.

Key facts. Cited by 173 papers in the map (data through 7 Oct 2026). First posted on arXiv 20 Jul 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 27; 2022: 30; 2023: 32; 2024: 28; 2025: 22; 2026: 33.

173 papers.

Sort:

By area:

  1. 2023Improved Online Conformal Prediction via Strongly Adaptive Online Learningcited by 76
  2. 2021How to Learn when Data Reacts to Your Model: Performative Gradient Descentcited by 70
  3. 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
  4. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  5. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 39
  6. 2022No-Regret Learning in Time-Varying Zero-Sum Gamescited by 36
  7. 2021Non-stationary Online Learning with Memory and Non-stochastic Controlcited by 33
  8. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  9. 2021Revisiting Smoothed Online Learningcited by 29
  10. 2022Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyondcited by 27
  11. 2022Adapting to Online Label Shift with Provable Guaranteescited by 26
  12. 2022Non-stationary Bandits with Knapsackscited by 25
38 more
  1. 2021The Pareto Frontier of model selection for general Contextual Banditscited by 24
  2. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  3. 2022The Best Decisions Are Not the Best Advice: Making Adherence-Aware Recommendationscited by 16
  4. 2023Adapting to Continuous Covariate Shift via Online Density Ratio Estimationcited by 15
  5. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  6. 2022Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methodscited by 14
  7. 2021A closer look at temporal variability in dynamic online learningcited by 13
  8. 2021Stochastic Optimization under Distributional Driftcited by 13
  9. 2022Online Weak-form Sparse Identification of Partial Differential Equationscited by 13
  10. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  11. 2023Smooth Non-Stationary Banditscited by 13
  12. 2023Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guaranteescited by 13
  13. 2024A CMDP-within-online framework for Meta-Safe Reinforcement Learningcited by 12
  14. 2024Optimizing Backward Policies in GFlowNets via Trajectory Likelihood Maximizationcited by 12
  15. 2022On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedbackcited by 11
  16. 2023Unconstrained Dynamic Regret via Sparse Codingcited by 11
  17. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  18. 2023Online Label Shift: Optimal Dynamic Regret meets Practical Algorithmscited by 11
  19. 2021Learning User Preferences in Non-Stationary Environmentscited by 10
  20. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  21. 2024Model Assessment and Selection under Temporal Distribution Shiftcited by 10
  22. 2024Online Linear Regression in Dynamic Environments via Discountingcited by 10
  23. 2021An Optimal Reduction of TV-Denoising to Adaptive Online Learningcited by 9
  24. 2021Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizescited by 9
  25. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  26. 2023A Stability Principle for Learning under Non-Stationaritycited by 9
  27. 2024An Equivalence Between Static and Dynamic Regret Minimizationcited by 9
  28. 2024An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothnesscited by 9
  29. 2021Learning and Information in Stochastic Networks and Queuescited by 8
  30. 2021Online Continual Adaptation with Active Self-Trainingcited by 8
  31. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  32. 2023Improved Dynamic Regret for Online Frank-Wolfecited by 8
  33. 2023Non-Convex Bilevel Optimization with Time-Varying Objective Functionscited by 8
  34. 2024From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimizationcited by 8
  35. 2024Multi-model Ensemble Conformal Prediction in Dynamic Environmentscited by 8
  36. 2021Fairness-aware Online Price Discrimination with Nonparametric Demand Modelscited by 7
  37. 2022Adaptive Experimentation in the Presence of Exogenous Nonstationary Variationcited by 7
  38. 2022Second Order Path Variationals in Non-Stationary Online Learningcited by 7

50 most cited of 173 All 173 (JSON)