  


A single potential governing convergence of conjugate gradient, accelerated gradient and geometric descent
Sahar Karimi(sahar.karimigmail.com) Abstract: Nesterov's accelerated gradient (AG) method for minimizing a smooth strongly convex function $f$ is known to reduce $f({\bf x}_k)f({\bf x}^*)$ by a factor of $\epsilon\in(0,1)$ after $k=O(\sqrt{L/\ell}\log(1/\epsilon))$ iterations, where $\ell,L$ are the two parameters of smooth strong convexity. Furthermore, it is known that this is the best possible complexity in the functiongradient oracle model of computation. Modulo a line search, the geometric descent (GD) method of Bubeck, Lee and Singh has the same bound for this class of functions. The method of linear conjugate gradients (CG) also satisfies the same complexity bound in the special case of strongly convex quadratic functions, but in this special case it can be faster than the AG and GD methods. Despite similarities in the algorithms and their asymptotic convergence rates, the conventional analysis of the running time of CG is mostly disjoint from that of AG and GD. The analyses of the AG and GD methods are also rather distinct. Our main result is analyses of the three methods that share several common threads: all three analyses show a relationship to a certain ``idealized algorithm'', all three establish the convergence rate through the use of the BubeckLeeSingh geometric lemma, and all three have the same potential that is computable at runtime and exhibits decrease by a factor of $1\sqrt{\ell/L}$ or better per iteration. One application of these analyses is that they open the possibility of hybrid or intermediate algorithms. One such algorithm is proposed herein and is shown to perform well in computational tests. Keywords: accelerated gradient, conjugate gradient, geometric descent, strongly convex Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Download: [PDF] Entry Submitted: 12/30/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  