Block cubic Newton with greedy selection
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918158845083648 |
|---|---|
| author | Cristofari, Andrea |
| author_facet | Cristofari, Andrea |
| contents | A second-order block coordinate descent method is proposed for the unconstrained minimization of an objective function with a Lipschitz continuous Hessian. At each iteration, a block of variables is selected by means of a greedy (Gauss-Southwell) rule which considers the amount of first-order stationarity violation, then an approximate minimizer of a cubic model is computed for the block update. In the proposed scheme, blocks are not required to have a predetermined structure and their size may change during the iterations. For non-convex objective functions, global convergence to stationary points is proved and a worst-case iteration complexity analysis is provided. In particular, given a tolerance $ε$, we show that at most ${\cal O(ε^{-3/2})}$ iterations are needed to drive the stationarity violation with respect to a selected block of variables below $ε$, while at most ${\cal O(ε^{-2})}$ iterations are needed to drive the stationarity violation with respect to all variables below $ε$. Numerical results are finally given, comparing the proposed approach with other second-order methods and block selection rules. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_18150 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Block cubic Newton with greedy selection Cristofari, Andrea Optimization and Control A second-order block coordinate descent method is proposed for the unconstrained minimization of an objective function with a Lipschitz continuous Hessian. At each iteration, a block of variables is selected by means of a greedy (Gauss-Southwell) rule which considers the amount of first-order stationarity violation, then an approximate minimizer of a cubic model is computed for the block update. In the proposed scheme, blocks are not required to have a predetermined structure and their size may change during the iterations. For non-convex objective functions, global convergence to stationary points is proved and a worst-case iteration complexity analysis is provided. In particular, given a tolerance $ε$, we show that at most ${\cal O(ε^{-3/2})}$ iterations are needed to drive the stationarity violation with respect to a selected block of variables below $ε$, while at most ${\cal O(ε^{-2})}$ iterations are needed to drive the stationarity violation with respect to all variables below $ε$. Numerical results are finally given, comparing the proposed approach with other second-order methods and block selection rules. |
| title | Block cubic Newton with greedy selection |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2407.18150 |