Gradient methods for convex minimization: better rates under weaker conditions

Abstract

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(\frac{R}{\epsilon })$ and $O(\sqrt{\frac{R}{\epsilon }})$ 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-\frac{1}{R}\nabla f$ for each $x\in\dom f$. Then we improve them to $O(\frac{R}{\nu }\log (\frac{1}{\epsilon }))$ and $O(\sqrt{\frac{R}{\nu }}\log (\frac{1}{\epsilon }))$ for function $f$ that also satisfies the secant inequality $<\nabla f(x),x-x^{\ast }>\ge \nu \Vert x-x^{\ast }{\Vert }^2$ for each $x\in \dom f$ and its projection $x^{\ast }$ 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.

20 pages, 4 figures, typos are corrected, Theorem 2 is new

References in corpus (1)

• Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm

Cited by in corpus (22)

• On exponential convergence of SGD in non-convex over-parametrized learning
• On the Convergence of Decentralized Gradient Descent
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
• The Physical Systems Behind Optimization Algorithms
• New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditions
• Accelerate Stochastic Subgradient Method by Leveraging Local Growth Condition
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation
• Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
• Training Neural Networks for and by Interpolation
• The restricted strong convexity revisited: Analysis of equivalence to error bound and quadratic growth
• Improved Learning Rates for Stochastic Optimization
• A dual algorithm for a class of augmented convex models
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
• A Study of Condition Numbers for First-Order Optimization
• Continuous-time Models for Stochastic Optimization Algorithms
• Mirror frameworks for relatively Lipschitz and monotone-like variational inequalities
• Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales
• On the Linear Convergence of the Cauchy Algorithm for a Class of Restricted Strongly Convex Functions
• Projected shrinkage algorithm for box-constrained L1-minimization