2023/11/13 by Quentin Rebjock, Nicolas Boumal, Rebjock, Quentin +1 · 1 citation
Computer Science · #Distributed Control Multi-Agent Systems #FOS: Mathematics #Matrix Theory and Algorithms #Neural Networks and Reservoir Computing #Numerical Analysis (math.NA) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2311.07404
openalex publication_date 2023/11/13 · openalex created_date 2023/11/15 · openalex updated_date 2026/07/28
Trust-region methods (TR) can converge quadratically to minima where the Hessian is positive definite. However, if the minima are not isolated, then the Hessian there cannot be positive definite. The weaker Polyak\unicodex2013Łojasiewicz (PŁ) condition is compatible with non-isolated minima, and it is enough for many algorithms to preserve good local behavior. Yet, TR with an exact subproblem solver lacks even basic features such as a capture theorem under PŁ. In practice, a popular inexact subproblem solver is the truncated conjugate gradient method (tCG). Empirically, TR-tCG exhibits super-linear convergence under PŁ. We confirm this theoretically. The main mathematical obstacle is that, under PŁ, at points arbitrarily close to minima, the Hessian has vanishingly small, possibly negative eigenvalues. Thus, tCG is applied to ill-conditioned, indefinite systems. Yet, the core theory underlying tCG is that of CG, which assumes a positive definite operator. Accordingly, we develop new tools to analyze the dynamics of CG in the presence of small eigenvalues of any sign, for the regime of interest to TR-tCG.