Conjugate Gradients and Accelerated Methods Unified: The Approximate Duality Gap View
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions
Performance of optimization on quadratic problems sensitively depends on the low-lying part of the spectrum. For large (effectively infinite-dimensional) problems, this part of the spectrum can often be naturally represe…
Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradients
We propose a lower bound on the log marginal likelihood of Gaussian process regression models that can be computed without matrix factorisation of the full kernel matrix. We show that approximate maximum likelihood learn…
Gaussian ProcessesregressionA modified limited memory Nesterov's accelerated quasi-Newton
The Nesterov's accelerated quasi-Newton (L)NAQ method has shown to accelerate the conventional (L)BFGS quasi-Newton method using the Nesterov's accelerated gradient in several neural network (NN) applications. However, t…
Joint State Estimation and Noise Identification Based on Variational Optimization
In this article, the state estimation problems with unknown process noise and measurement noise covariances for both linear and nonlinear systems are considered. By formulating the joint estimation of system state and no…
State EstimationVariational InferenceNatural Gradients in Practice: Non-Conjugate Variational Inference in Gaussian Process Models
The natural gradient method has been used effectively in conjugate Gaussian process models, but the non-conjugate case has been largely unexplored. We examine how natural gradients can be used in non-conjugate stochastic…
Variational Inference