Optimization Letters · 2016 · 62 citations · 5 references
ComputingComputer ScienceAlgorithmsOptimizationTheory Of ComputationAlgorithm AnalysisConvex AnalysisConvex OptimizationGradient-based OptimizationOptimization TheoryQuadratic ProgrammingConvex FunctionsConvex Quadratic ProgrammingGradient DescentLipschitz ContinuitySemidefinite ProgrammingSteepest DescentStrong ConvexityWorst-case Complexity
We consider the gradient (or steepest) descent method with exact line search applied to a strongly convex function with Lipschitz continuous gradient. We establish the exact worst-case rate of convergence of this scheme, and show that this worst-case behavior is exhibited by a certain convex quadratic function. We also give the tight worst-case complexity bound for a noisy variant of gradient descent method, where exact line-search is performed in a search direction that differs from negative gradient by at most a prescribed relative tolerance. The proofs are computer-assisted, and rely on the resolutions of semidefinite programming performance estimation problems as introduced in the paper (Drori and Teboulle, Math Progr 145(1–2):451–482, 2014).
5
Choice Reviews Online · 1989 · 1.8K citations
Adding Gradient Noise Improves Learning for Very Deep Networks
Arvind Neelakantan, Luke Vilnis, Quoc V. Le et al. · arXiv (Cornell University) · 2015 · 267 citations · Full text