# Gradient methods for convex minimization: better rates under weaker conditions

arXiv: https://arxiv.org/abs/1303.4645 · HTML: https://mlsanity.com/paper/1303.4645/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2013.

## Built on by (most cited first, 23 of 23)

- [Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing](https://mlsanity.com/paper/2301.11500/) (2023)
- [Convergence of gradient descent for deep neural networks](https://mlsanity.com/paper/2203.16462/) (2022)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [On the Local Linear Rate of Consensus on the Stiefel Manifold](https://mlsanity.com/paper/2101.09346/) (2021)
- [Why Do Local Methods Solve Nonconvex Problems?](https://mlsanity.com/paper/2103.13462/) (2021)
- [Loss Landscape Characterization of Neural Networks without Over-Parametrization](https://mlsanity.com/paper/2410.12455/) (2024)
- [No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths](https://mlsanity.com/paper/2306.11922/) (2023)
- [Locally Differentially Private Online Federated Learning With Correlated Noise](https://mlsanity.com/paper/2411.18752/) (2024)
- [Sampling Attacks on Meta Reinforcement Learning: A Minimax Formulation and Complexity Analysis](https://mlsanity.com/paper/2208.00081/) (2022)
- [Optimizing the Performative Risk under Weak Convexity Assumptions](https://mlsanity.com/paper/2209.00771/) (2022)
- [Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates](https://mlsanity.com/paper/2311.13447/) (2023)
- [From Inverse Optimization to Feasibility to ERM](https://mlsanity.com/paper/2402.17890/) (2024)
- [Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms](https://mlsanity.com/paper/2508.00775/) (2025)
- [Glocal Smoothness: Line search and adaptive step sizes can help in theory too!](https://mlsanity.com/paper/2506.12648/) (2025)
- [Spectral Regularization Allows Data-frugal Learning over Combinatorial Spaces](https://mlsanity.com/paper/2210.02604/) (2022)
- [Convergence of Steepest Descent and Adam under Non-Uniform Smoothness](https://mlsanity.com/paper/2605.30648/) (2026)
- [A Local Convergence Theory for the Stochastic Gradient Descent Method in Non-Convex Optimization With Non-isolated Local Minima](https://mlsanity.com/paper/2203.10973/) (2022)
- [A Homogenization Approach for Gradient-Dominated Stochastic Optimization](https://mlsanity.com/paper/2308.10630/) (2023)
- [Differentially Private Online Federated Learning with Correlated Noise](https://mlsanity.com/paper/2403.16542/) (2024)
- [Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation](https://mlsanity.com/paper/2404.02378/) (2024)
- [Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport](https://mlsanity.com/paper/2510.27340/) (2025)
- [Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time](https://mlsanity.com/paper/2606.17260/) (2026)
- [Retraction-Free Optimization over the Stiefel Manifold for the LoRA Fine-Tuning](https://mlsanity.com/paper/2607.25299/) (2026)

## Abstract (arXiv)

The convergence behavior of gradient methods for minimizing convex differentiable functions is one of the core questions in convex optimization. This paper shows that their well-known complexities can be achieved under conditions weaker than the commonly accepted ones. We relax the common gradient Lipschitz-continuity condition and strong convexity condition to ones that hold only over certain line segments. Specifically, we establish complexities O(fracRε) and O(√fracRε) for the ordinary and accelerate gradient methods, respectively, assuming that nabla f is Lipschitz continuous with constant R over the line segment joining x and x-frac1Rnabla f for each x∈dom f. Then we improve them to O(fracRnulog(frac1ε)) and O(√fracRnulog(frac1ε)) for function f that also satisfies the secant inequality  < nabla f(x), x- x^* > ≥ nu|x-x^*|2 for each x∈ dom f and its projection x^* to the minimizer set of f. The secant condition is also shown to be necessary for the geometric decay of solution error. Not only are the relaxed conditions met by more functions, the restrictions give smaller R and larger nu than they are without the restrictions and thus lead to better complexity bounds. We apply these results to sparse optimization and demonstrate a faster algorithm.