Frugality in second-order optimization: floating-point approximations for Newton's Method

Minimizing loss functions is at the core of Machine Learning training. While first-order methods dominate in practice, higher-order approaches such as Newton’s method offer higher accuracy and faster convergence, but are often avoided due to their high computational cost. In our work, we analyze the finite-precision errors propagation in Newton’s step, proposing a convergence theorem for mixed-precision Newton optimizers, including “Quasi” and “Inexact” variants. The theorem not only guarantees convergence for not too ill-conditioned problems, but also allows predicting in advance the accuracy achievable by the optimizers. Experiments on logistic regression demonstrate that our method outperforms Adam on the Australian dataset, while being less computationally expensive than the classical Newton method. Additionally, a generalization of the Gauss-Newton method, namely GN_k, is presented, formalizing the idea of using a subset of the second-order residual derivatives during Gauss-Newton step computation, instead of discarding them all, to reduce computational cost without sacrificing accuracy. To solve the linear system of GN_k, a variant of the CGLS iterative solver, called CGLS_k, is presented. Both the linear and non-linear solvers have been tested on a set of problems, showing the soundness of their implementation and theoretical foundation.