mlsanityData to 7 Oct 2026

Error bounds, quadratic growth, and linear convergence of proximal methods

arXiv 1602.06661 ↗First posted 22 Feb 2016math.OCcited by 59

Not on the map. Why?

Abstract (arXiv)

The proximal gradient algorithm for minimizing the sum of a smooth and a nonsmooth convex function often converges linearly even without strong convexity. One common reason is that a multiple of the step length at each iteration may linearly bound the "error" -- the distance to the solution set. We explain the observed linear convergence intuitively by proving the equivalence of such an error bound to a natural quadratic growth condition. Our approach generalizes to linear convergence analysis for proximal methods (of Gauss-Newton type) for minimizing compositions of nonsmooth functions with smooth mappings. We observe incidentally that short step-lengths in the algorithm indicate near-stationarity, suggesting a reliable termination criterion.

Key facts. Cited by 59 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Feb 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 14; 2023: 16; 2024: 5; 2025: 10; 2026: 8.

59 papers.

Sort:

By area:

  1. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  2. 2021Revisiting Smoothed Online Learningcited by 29
  3. 2023Aiming towards the minimizers: fast convergence of SGD for overparametrized problemscited by 22
  4. 2022Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-startcited by 17
  5. 2022A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problemcited by 17
  6. 2023A Stochastic Proximal Polyak Step Sizecited by 15
  7. 2022A Unified Convergence Theorem for Stochastic Optimization Methodscited by 12
  8. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  9. 2024A CMDP-within-online framework for Meta-Safe Reinforcement Learningcited by 12
  10. 2021An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learningcited by 10
  11. 2021Complementary Composite Minimization, Small Gradients in General Norms, and Applicationscited by 9
  12. 2023Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problemscited by 9
38 more
  1. 2024FERERO: A Flexible Framework for Preference-Guided Multi-Objective Learningcited by 9
  2. 2021On the Local Linear Rate of Consensus on the Stiefel Manifoldcited by 8
  3. 2022Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Datacited by 7
  4. 2023No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Pathscited by 7
  5. 2024A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraintscited by 7
  6. 2022On Solution Functions of Optimization: Universal Approximation and Covering Number Boundscited by 6
  7. 2023Connecting NTK and NNGP: A Unified Theoretical Framework for Wide Neural Network Learning Dynamicscited by 6
  8. 2025Adaptive Context Length Optimization with Low-Frequency Truncation for Multi-Agent Reinforcement Learningcited by 6
  9. 2022A Semismooth Newton Stochastic Proximal Point Algorithm with Variance Reductioncited by 5
  10. 2023Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimizationcited by 5
  11. 2023A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Propertiescited by 5
  12. 2022Optimizing the Performative Risk under Weak Convexity Assumptionscited by 4
  13. 2023Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviationcited by 4
  14. 2023A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimizationcited by 4
  15. 2024An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimizationcited by 4
  16. 2022Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problemscited by 3
  17. 2023Variance reduction techniques for stochastic proximal point algorithmscited by 3
  18. 2025Beyond Scores: Proximal Diffusion Modelscited by 3
  19. 2023Theoretical Analysis of Offline Imitation With Supplementary Datasetcited by 2
  20. 2023Linearization Algorithms for Fully Composite Optimizationcited by 2
  21. 2023Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problemscited by 2
  22. 2023Distributionally Time-Varying Online Stochastic Optimization under Polyak-Lojasiewicz Condition with Application in Conditional Value-at-Risk Statistical Learningcited by 2
  23. 2021OpReg-Boost: Learning to Accelerate Online Algorithms with Operator Regressioncited by 1
  24. 2022Gradient Descent-Type Methods: Background and Simple Unified Convergence Analysiscited by 1
  25. 2025Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networkscited by 1
  26. 2026Stochastic variance reduced extragradient methods for solving hierarchical variational inequalitiescited by 1
  27. 2021Robust Regression via Model Based Methodscited by 0
  28. 2022Consistent Approximations in Composite Optimizationcited by 0
  29. 2022Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementaritycited by 0
  30. 2022Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problemscited by 0
  31. 2022Iterative Minimax Games with Coupled Linear Constraintscited by 0
  32. 2023A Linearly Convergent GAN Inversion-based Algorithm for Reverse Engineering of Deceptionscited by 0
  33. 2024Accelerated Fully First-Order Methods for Bilevel and Minimax Optimizationcited by 0
  34. 2025A Regularized Online Newton Method for Stochastic Convex Bandits with Linear Vanishing Noisecited by 0
  35. 2025A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedroncited by 0
  36. 2025Learning Over Dirty Data with Minimal Repairscited by 0
  37. 2025Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappingscited by 0
  38. 2025Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Piecescited by 0

50 most cited of 59 All 59 (JSON)