mlsanityData to 7 Oct 2026

Dealing with unbounded gradients in stochastic saddle-point optimization

arXiv 2402.13903 ↗First posted 21 Feb 2024cs.LG math.OC stat.MLcited by 15

Not on the map. Why?

Abstract (arXiv)

We study the performance of stochastic first-order methods for finding saddle points of convex-concave functions. A notorious challenge faced by such methods is that the gradients can grow arbitrarily large during optimization, which may result in instability and divergence. In this paper, we propose a simple and effective regularization technique that stabilizes the iterates and yields meaningful performance guarantees even if the domain and the gradient noise scales linearly with the size of the iterates (and is thus potentially unbounded). Besides providing a set of general results, we also apply our algorithm to a specific problem in reinforcement learning, where it leads to performance guarantees for finding near-optimal policies in an average-reward MDP without prior knowledge of the bias span.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 28 of its 55 references that are in the map. First posted on arXiv 21 Feb 2024.

Builds on

28 of 55 references.

References · 28

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  3. 2016NIPS 2016 Tutorial: Generative Adversarial Networkscited by 284
  4. 2017Training GANs with Optimismcited by 217
  5. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  6. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  7. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  8. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  9. 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 60
  10. 2020Lipschitz and Comparator-Norm Adaptivity in Online Learningcited by 57
  11. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  12. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
16 more
  1. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  2. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  3. 2019Revisiting Stochastic Extragradientcited by 35
  4. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 32
  5. 2014Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learningcited by 27
  6. 2015On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalitiescited by 27
  7. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
  8. 2018Faster Rates for Convex-Concave Gamescited by 23
  9. 2018Acceleration through Optimistic No-Regret Dynamicscited by 22
  10. 2020Online mirror descent and dual averaging: keeping pace in the dynamic casecited by 21
  11. 2021No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimizationcited by 20
  12. 2017Online Convex Optimization with Unconstrained Domains and Lossescited by 14
  13. 2018Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescited by 14
  14. 2013Minimax Optimal Algorithms for Unconstrained Linear Optimizationcited by 12
  15. 2019A Reduction from Reinforcement Learning to No-Regret Online Learningcited by 10
  16. 2021On the Initialization for Convex-Concave Min-max Problemscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 5; 2026: 9.

15 papers.

Sort:

By area:

  1. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 13
  2. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 3
  3. 2026Solving Stochastic Variational Inequalities without the Bounded Variance Assumptioncited by 3
  4. 2024Offline RL via Feature-Occupancy Gradient Ascentcited by 2
  5. 2025Distances for Markov chains from sample streamscited by 2
  6. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RLcited by 2
  7. 2026Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variancecited by 2
  8. 2026How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyondcited by 1
  9. 2025A Study of Hybrid and Evolutionary Metaheuristics for Single Hidden Layer Feedforward Neural Network Architecturecited by 0
  10. 2026Convergence Rate of the Last Iterate of Stochastic Proximal Algorithmscited by 0
  11. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0
  12. 2026A Perturbation Approach to Unconstrained Linear Banditscited by 0
3 more
  1. 2026SGD for Variational Inference: Tackling Unbounded Variance via Preconditioning and Dynamic Batchingcited by 0
  2. 2026On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalitiescited by 0
  3. 2026Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalitiescited by 0