mlsanityData to 14 Oct 2026

From error bounds to the complexity of first-order descent methods for convex functions

arXiv 1510.08234 ↗First posted 28 Oct 2015math.OCcited by 43

Not on the map. Why?

Abstract (arXiv)

This paper shows that error bounds can be used as effective tools for deriving complexity results for first-order descent methods in convex minimization. In a first stage, this objective led us to revisit the interplay between error bounds and the Kurdyka-L ojasiewicz (KL) inequality. One can show the equivalence between the two concepts for convex functions having a moderately flat profile near the set of minimizers (as those of functions with H"olderian growth). A counterexample shows that the equivalence is no longer true for extremely flat functions. This fact reveals the relevance of an approach based on KL inequality. In a second stage, we show how KL inequalities can in turn be employed to compute new complexity bounds for a wealth of descent methods for convex problems. Our approach is completely original and makes use of a one-dimensional worst-case proximal sequence in the spirit of the famous majorant method of Kantorovich. Our result applies to a very simple abstract scheme that covers a wide class of descent methods. As a byproduct of our study, we also provide new results for the globalization of KL inequalities in the convex framework. Our main results inaugurate a simple methodology: derive an error bound, compute the desingularizing function whenever possible, identify essential constants in the descent method and finally compute the complexity using the one-dimensional worst case proximal sequence. Our method is illustrated through projection methods for feasibility problems, and through the famous iterative shrinkage thresholding algorithm (ISTA), for which we show that the complexity bound is of the form O(qk) where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with ℓ1 regularization.

Key facts. Cited by 43 papers in the map (data through 14 Oct 2026). First posted on arXiv 28 Oct 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

43 papers.

Sort:

By area:

  1. 2021Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problemcited by 53
  2. 2021Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descentcited by 32
  3. 2021Subquadratic Overparameterization for Shallow Neural Networkscited by 26
  4. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 20
  5. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  6. 2022A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problemcited by 17
  7. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  8. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  9. 2021An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learningcited by 10
  10. 2024Loss Landscape Characterization of Neural Networks without Over-Parametrizationcited by 8
  11. 2025Direct Prediction Set Minimization via Bilevel Conformal Classifier Trainingcited by 8
  12. 2021Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descentcited by 5
31 more
  1. 2022Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decompositioncited by 5
  2. 2022Optimizing the Performative Risk under Weak Convexity Assumptionscited by 5
  3. 2022Differentiating Nonsmooth Solutions to Parametric Monotone Inclusion Problemscited by 5
  4. 2021First-Order Methods for Convex Optimizationcited by 4
  5. 2021Local and Global Uniform Convexity Conditionscited by 4
  6. 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
  7. 2023A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimizationcited by 4
  8. 2024An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimizationcited by 4
  9. 2024A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processescited by 4
  10. 2023Gradient is All You Need? How Consensus-Based Optimization can be Interpreted as a Stochastic Relaxation of Gradient Descentcited by 3
  11. 2023Variance reduction techniques for stochastic proximal point algorithmscited by 3
  12. 2023Convergence and Recovery Guarantees of Unsupervised Neural Networks for Inverse Problemscited by 3
  13. 2024Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequalitycited by 3
  14. 2025Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularizationcited by 3
  15. 2025Diffusion Generative Models Meet Compressed Sensing, with Applications to Imaging and Financecited by 3
  16. 2023Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methodscited by 2
  17. 2025Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysiscited by 2
  18. 2021WARPd: A linearly convergent first-order method for inverse problems with approximate sharpness conditionscited by 1
  19. 2022An Exponentially Increasing Step-size for Parameter Estimation in Statistical Modelscited by 1
  20. 2024Recovery Guarantees of Unsupervised Neural Networks for Inverse Problems trained with Gradient Descentcited by 1
  21. 2024Inexact subgradient methods for semialgebraic functionscited by 1
  22. 2026Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality Constraintscited by 1
  23. 2021Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growthcited by 0
  24. 2022Iterative regularization in classification via hinge loss diagonal descentcited by 0
  25. 2023An inexact LPA for DC composite optimization and application to matrix completions with outlierscited by 0
  26. 2024Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimizationcited by 0
  27. 2024Learning Massive-scale Partial Correlation Networks in Clinical Multi-omics Studies with HP-ACCORDcited by 0
  28. 2026Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergencecited by 0
  29. 2026Leveraging Extragradient for Effective Sharpness-Aware Minimization in Deep Learningcited by 0
  30. 2026Constrained Path Reasoning: Measuring When Committed Stages Earn Their Costcited by 0
  31. 2026Memory-Computation Tradeoffs in Semi Amortized Parametric Optimizationcited by 0