CG versus MINRES in Non-linear Optimization

The celebrated conjugate gradient (CG) method is a very well-known and an indispensable method for solving linear systems involving positive definite matrices. CG has also been classically the dominant solver in most non-linear second-order methods for unconstrained optimization. In this talk, we consider replacing CG with a less known alternative, knows as the minimum residual method (MINRES), which is often used for symmetric but possibly indefinite linear systems. We show that MINRES enjoys many advantageous properties that can be beneficial in designing efficient non-linear optimization algorithms. Equipped with these advantages, we discuss algorithms, under the general name of Newton-MR, which can be used for optimization of general non-convex objectives, and that come with favourable convergence guarantees. We also give numerical examples demonstrating the performance of these methods for large-scale non-convex machine learning problems.