Gradient methods for convex minimization: better rates under weaker conditions

By Hui Zhang, Wotao Yin. 2013

97 citations recorded by the source corpus.

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 $\ \ge \nu\|x-x^*\|^2$ for each $x\in \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.

Subfields: Artificial Intelligence, Computational Mechanics, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Mathematical Physics

Citations in the corpus

On the Convergence of Decentralized Gradient Descent (2013, background): “Restricted strongly convex functions are studied as they appear in the applications of sparse optimization and statistical regression; see [37] for some examples.”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, background): “We suspect that the assumption of strong convexity can be wea ken d torestricted strong convexity [17, 39] without changing any of the results of this paper; we leave this analysis to future work.”
On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “One such condition is Restricted secant inequality (RSI) proposed in [15].”
Linear convergence of first order methods under weak nondegeneracy assumptions for convex programming (2015, background): “In [7] the authors show that their restricted secant inequality for the unconstrained problem (P) (i.”
The Physical Systems Behind Optimization Algorithms (2016, background): “…conditions have been shown to hold for many optimization problems in machine learning and faster convergence rates have been established (e.g. Luo and Tseng (1993); Liu and Wright (2015); Necoara et al. (2015); Zhang and Yin (2013); Liu and Wright (2015); Gong and Ye (2014); Karimi et al. (2016)).”
Linear Convergence of Randomized Feasible Descent Methods Under the Weak Strong Convexity Assumption (2016, background): “This improves upon the result obtained in Shalev-Shwartz and Zhang (2013); Takáč et al. (2015); Takáč et al. (2013), where only a sublinear rate was derived.”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, background): “…[2016], PL condition is weaker, or not stronger, than other well-known conditions that guarantee linear convergence for gradient descent, such as error bounds (EB) [Luo and Tseng, 1993], weak strong convexity (WSC) [Necoara et al., 2018] and restricted secant inequality (RSI) [Zhang and Yin, 2013].”
Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning (2018, methodology): “Proof We follow the proof technique in Zhang and Yin (2013). We have”
The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth (2015, background): “Almost parallel to work [19], the authors of [18, 11] deﬁned the global error bound (GEB) property in the spirit of Hoﬀman’s celebrated result on error bounds for systems of linear inequalities [7, 10].”
Linear convergence of first order methods for non-strongly convex optimization (2015, background): “e.g. [5,6,10]). Finally, we can conclude that the following chain of inclusions hold: F1,1 L f,σ f (X) ⊆ E1,1 L f,ξ f (X) ⊆ W1,1 L f,κ f (X) ⊆ F1,1 L f (X), for appropriate constants σf,ξf and κf. In [9] the authors show that their restricted secant inequality for the unconstrained problem (P) (i.e.”