Let's consider smooth and convex minimization problem, i.e. $min f(x)$, where $f$ is not necessarily a quadratic function. If measured by iterations,

  1. Accelerated Gradient Descend (AGD) has $O(1/T^2)$ rate for weak convex case and linear rate with strong convexity.
  2. Nonlinear Conjugate Gradient descent (Nonlinear-CGD) has not explicit rate (I got this from Section 5.2 at Numerical Optimization).

But, in quadratic case CGD works much better than APG, i.e. much less iterations are needed to achieve desired precision.

Therefore, is it the same when apply APG and Nonlinear-CGD on above $min f(x)$?

  • $\begingroup$ Besides, what's the dependency of Nonlinear-CGD on conditional number (c)? I know it is sqrt(c) for APG, then how about Nonlinear-CGD? $\endgroup$ – Quanming Jul 1 '15 at 16:11
  • $\begingroup$ I've done a detailed comparison on this task. I use matrix completion problem as testing seedbed. In a word, for general case, though AGD works better, there is no absolute win between them. For me, I prefer trying AGD first, since it is simpler to implement and can handle other constrains more easily. Code and PDF: github.com/quanmingyao/NCG-vs-AGD. $\endgroup$ – Quanming Jul 9 '15 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.