Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems
Not on the map. Why?
Abstract (arXiv)
We propose a new class of fast Krasnoselkii--Mann methods with variance reduction to solve a finite-sum co-coercive equation Gx = 0. Our algorithm is single-loop and leverages a new family of unbiased variance-reduced estimators specifically designed for a wider class of root-finding algorithms. Our method achieves both O(1/k2) and o(1/k2) last-iterate convergence rates in terms of mathbbE[| Gxk|2], where k is the iteration counter and mathbbE[·] is the total expectation. We also establish almost sure o(1/k2) convergence rates and the almost sure convergence of iterates xk to a solution of Gx=0. We instantiate our framework for two prominent estimators: SVRG and SAGA. By an appropriate choice of parameters, both variants attain an oracle complexity of O(n + n2/3ε-1) to reach an ε-solution, where n represents the number of summands in the finite-sum operator G. Furthermore, under σ-strong quasi-monotonicity, our method achieves a linear convergence rate and an oracle complexity of O(n+ maxn, n2/3kappa log(frac1ε)), where kappa := L/σ. We extend our approach to solve a class of finite-sum inclusions (possibly nonmonotone), demonstrating that our schemes retain the same theoretical guarantees as in the equation setting. Finally, numerical experiments validate our algorithms and demonstrate their promising performance compared to state-of-the-art methods.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 49 of its 93 references that are in the map. First posted on arXiv 4 Jun 2024.
Builds on
49 of 93 references.
References · 49
- 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
- 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
- 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
- 2017Training GANs with Optimismcited by 217
- 2019SGD: General Analysis and Improved Ratescited by 207
- 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
- 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
- 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
- 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
- 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
- 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 62
- 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
37 more
- 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
- 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
- 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 47
- 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
- 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
- 2019Variance Reduction for Matrix Gamescited by 38
- 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
- 2020Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimizationcited by 36
- 2019Revisiting Stochastic Extragradientcited by 35
- 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
- 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
- 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
- 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
- 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
- 2014Accelerated Schemes For A Class of Variational Inequalitiescited by 30
- 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
- 2019On Lower Iteration Complexity Bounds for the Saddle Point Problemscited by 28
- 2019Generalized monotone operators and their averaged resolventscited by 27
- 2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 25
- 2015ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updatescited by 21
- 2021Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusionscited by 21
- 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
- 2022From Halpern's Fixed-Point Iterations to Nesterov's Accelerated Interpretations for Root-Finding Problemscited by 20
- 2014Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variantscited by 19
- 2021Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimizationcited by 19
- 2015The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k2cited by 15
- 2022Beyond the Golden Ratio for Variational Inequality Algorithmscited by 12
- 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 11
- 2019Accelerating Variance-Reduced Stochastic Gradient Methodscited by 10
- 2022From the Ravine method to the Nesterov method and vice versa: a dynamical system perspectivecited by 9
- 2020Two steps at a time -- taking GAN training in stride with Tseng's methodcited by 8
- 2016On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemescited by 5
- 2019Forward-backward-forward methods with variance reduction for stochastic variational inequalitiescited by 5
- 2017Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operatorscited by 4
- 2022An Accelerated Variance Reduced Extra-Point Approach to Finite-Sum VI and Optimizationcited by 4
- 2022Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problemscited by 3
- 2016SMART: The Stochastic Monotone Aggregated Root-Finding Algorithmcited by 2
Built on by
Citing papers per year: 2025: 1; 2026: 2.
3 papers.