mlsanityData to 14 Oct 2026

A regret minimization approach to fixed-point iterations

arXiv 2509.21653 ↗First posted 25 Sep 2025math.OC cs.LG cs.NAcited by 0

Not on the map. Why?

Abstract (arXiv)

We propose a conversion scheme that turns regret minimizing algorithms into fixed point iterations, with convergence guarantees following from regret bounds. The resulting iterations can be seen as a grand extension of the classical Krasnoselskii--Mann iterations, as the latter are recovered by converting the Online Gradient Descent algorithm. This approach yields new simple iterations for finding fixed points of non-self operators. We also focus on converting algorithms from the AdaGrad family of regret minimizers, and thus obtain fixed point iterations with adaptive guarantees of a new kind. Numerical experiments on various problems demonstrate faster convergence of AdaGrad-based fixed point iterations over Krasnoselskii--Mann iterations.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 48 of its 139 references that are in the map. First posted on arXiv 25 Sep 2025.

Builds on

48 of 139 references.

References · 48

  1. 2019On the Convergence of Adam and Beyondcited by 841
  2. 2019Introduction to Online Convex Optimizationcited by 803
  3. 2019On the Variance of the Adaptive Learning Rate and Beyondcited by 772
  4. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  5. 2020AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradientscited by 283
  6. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  7. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  8. 2020A Simple Convergence Proof of Adam and Adagradcited by 171
  9. 2024The Road Less Scheduledcited by 163
  10. 2016Coin Betting and Parameter-Free Online Learningcited by 133
  11. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 125
  12. 2023Learning-Rate-Free Learning by D-Adaptationcited by 113
36 more
  1. 2016Scale-Free Online Learningcited by 85
  2. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  3. 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
  4. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  5. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 61
  6. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 57
  7. 2019UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimizationcited by 56
  8. 2018Online Adaptive Methods, Universality and Accelerationcited by 51
  9. 2014Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximationscited by 46
  10. 2022Parameter-free Mirror Descentcited by 45
  11. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  12. 2017Online to Offline Conversions, Universality and Adaptive Minibatch Sizescited by 39
  13. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  14. 2018Golden Ratio Algorithms for Variational Inequalitiescited by 38
  15. 2023DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Methodcited by 35
  16. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  17. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  18. 2019Linear Convergence of Adaptive Stochastic Gradient Descentcited by 29
  19. 2019A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noisecited by 26
  20. 2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 24
  21. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  22. 2013Approachability, Regret and Calibration; implications and equivalencescited by 19
  23. 2024Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimizationcited by 16
  24. 2022On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Accelerationcited by 13
  25. 2020Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergencecited by 12
  26. 2024Fully Unconstrained Online Learningcited by 10
  27. 2018Distributed Stochastic Optimization via Adaptive SGDcited by 7
  28. 2024Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methodscited by 7
  29. 2020Sequential convergence of AdaGrad algorithm for smooth convex optimizationcited by 5
  30. 2025Pushing the Complexity Boundaries of Fixed-Point Equations: Adaptation to Contraction and Controlled Expansioncited by 5
  31. 2016SuperMann: a superlinearly convergent algorithm for finding fixed points of nonexpansive operatorscited by 4
  32. 2022Adaptive Accelerated (Extra-)Gradient Methods with Variance Reductioncited by 4
  33. 2016Line Search for Averaged Operator Iterationcited by 3
  34. 2023Generalized Implicit Follow-The-Regularized-Leadercited by 3
  35. 2023The Geometry of Monotone Operator Splitting Methodscited by 1
  36. 2024Tracking solutions of time-varying variational inequalitiescited by 1

Built on by

Not cited yet.