Conjugate Gradients and Accelerated Methods Unified: The Approximate Duality Gap View

Abstract

This note provides a novel, simple analysis of the method of conjugate gradients for the minimization of convex quadratic functions. In contrast with standard arguments, our proof is entirely self-contained and does not rely on the existence of Chebyshev polynomials. Another advantage of our development is that it clarifies the relation between the method of conjugate gradients and general accelerated methods for smooth minimization by unifying their analyses within the framework of the Approximate Duality Gap Technique that was introduced by the authors.

arXiv comment8 pages. v1 -> v2: corrected a reference to the paper with Nemirovski acceleration with line search. v2 -> v3: updated affiliations, corrected a few typos on p.7 and added an acknowledgement

References in corpus (8)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• A geometric alternative to Nesterov's accelerated gradient descent
• From Averaging to Acceleration, There is Only a Step-size
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• On Acceleration with Noise-Corrupted Gradients
• Integration Methods and Accelerated Optimization Algorithms
• Generalized Framework for Nonlinear Acceleration