Understand
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$.
Built on
Y. Nesterov, A method of solving a convex programming problem with convergence rate O(1/
1983
Earlier work this paper cites.
P. Tseng, Descent methods for convex essentially smooth minimization, J. Optim. Theory Appl., 71 (1991), pp. 425-463
1991
Earlier work this paper cites.
Y. Nesterov, Introductory lectures on convex optimization: A basic course, Kluwer Academic Publishers, 2004
2004
Earlier work this paper cites.
Y. Nesterov, Smooth minimization of non-smooth functions, Mathematical programming, Series A, 103(2005), pp. 127-152
2005
Earlier work this paper cites.
Y. Nesterov, Gradient methods for minimizing composite objective function, CORE discussion paper, 2007
2007
Earlier work this paper cites.
Similar
P. Tseng, On accelerated proximal gradient methods for convex-concave optimization, submitted to SIAM J. Optim., 2008
2008
Cited alongside, same era.
A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sciences, 2 (2009), pp. 183-202
2009
Cited alongside, same era.
K. Scheinberg, D. Goldfarb, and X Bai, Fast first-order methods for composite convex optimization with line search, submitted, 2011
2011
Cited alongside, same era.
A. Agarwal, S. Negahban, and M. J. Wainwright, Fast global convergence of gradient methods for high-dimensional statistical recovery, To appear in Annals of Statistics, 2012
2012
Cited alongside, same era.
Then
S. Negahban, P. Ravikumar, M. J. Wainwright and B. Yu, A unified framework for the analysis of regularized
2012
Later among the works it cites.
B. Huang, S. Q. Ma, and D. Goldfarb, Accelerated Linearized Bregman Method. Journal of Scientific Computation, 54(2013), pp. 428-453
2013
Closest in time.
M.J. Lai and W. Yin, Augmented
2013
Closest in time.
2013
Closest in time.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…