A split preconditioning scheme for nonlinear underdetermined least squares problems

The convergence of preconditioned gradient methods for nonlinear underdetermined least squares problems arising in, for example, supervised learning of overparameterized neural networks is investigated. In this general setting, conditions are given that guarantee the existence of global minimizers that correspond to zero residuals and a proof of the convergence of a gradient method to these global minima is presented. In order to accelerate convergence of the gradient method, different preconditioning strategies are developed and analyzed. In particular, a left randomized preconditioner and a right coarse-level correction preconditioner are combined and investigated. It is demonstrated that the resulting split preconditioned two-level gradient method incorporates the advantages of both approaches and performs very efficiently.