Fast convergence of trust-regions for non-isolated minima via analysis of CG on indefinite matrices
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910617011486720 |
|---|---|
| author | Rebjock, Quentin Boumal, Nicolas |
| author_facet | Rebjock, Quentin Boumal, Nicolas |
| contents | 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$\unicode{x2013}$Ł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 $\textit{exact}$ subproblem solver lacks even basic features such as a capture theorem under PŁ.
In practice, a popular $\textit{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_07404 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fast convergence of trust-regions for non-isolated minima via analysis of CG on indefinite matrices Rebjock, Quentin Boumal, Nicolas Optimization and Control Numerical Analysis 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$\unicode{x2013}$Ł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 $\textit{exact}$ subproblem solver lacks even basic features such as a capture theorem under PŁ. In practice, a popular $\textit{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. |
| title | Fast convergence of trust-regions for non-isolated minima via analysis of CG on indefinite matrices |
| topic | Optimization and Control Numerical Analysis |
| url | https://arxiv.org/abs/2311.07404 |