Parameter-Free Accelerated Quasi-Newton Method for Nonconvex Optimization
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908704207536128 |
|---|---|
| author | Marumo, Naoki |
| author_facet | Marumo, Naoki |
| contents | We propose a quasi-Newton-type method for nonconvex optimization with Lipschitz continuous gradients and Hessians. The algorithm finds an $\varepsilon$-stationary point within $\tilde{\mathrm{O}}(d^{1/4} \varepsilon^{-13/8})$ gradient evaluations, where $d$ is the problem dimension. Although this bound includes an additional logarithmic factor compared with the best known complexity, our method is parameter-free in the sense that it requires no prior knowledge of problem-dependent parameters such as Lipschitz constants or the optimal value. Moreover, it does not need the target accuracy $\varepsilon$ or the total number of iterations to be specified in advance. The result is achieved by combining several key ideas: momentum-based acceleration, quartic regularization for subproblems, and a scaled variant of the Powell-symmetric-Broyden (PSB) update. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_09439 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parameter-Free Accelerated Quasi-Newton Method for Nonconvex Optimization Marumo, Naoki Optimization and Control 65K05, 65K10, 90C26, 90C30, 90C53 We propose a quasi-Newton-type method for nonconvex optimization with Lipschitz continuous gradients and Hessians. The algorithm finds an $\varepsilon$-stationary point within $\tilde{\mathrm{O}}(d^{1/4} \varepsilon^{-13/8})$ gradient evaluations, where $d$ is the problem dimension. Although this bound includes an additional logarithmic factor compared with the best known complexity, our method is parameter-free in the sense that it requires no prior knowledge of problem-dependent parameters such as Lipschitz constants or the optimal value. Moreover, it does not need the target accuracy $\varepsilon$ or the total number of iterations to be specified in advance. The result is achieved by combining several key ideas: momentum-based acceleration, quartic regularization for subproblems, and a scaled variant of the Powell-symmetric-Broyden (PSB) update. |
| title | Parameter-Free Accelerated Quasi-Newton Method for Nonconvex Optimization |
| topic | Optimization and Control 65K05, 65K10, 90C26, 90C30, 90C53 |
| url | https://arxiv.org/abs/2512.09439 |