Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908782861221888 |
|---|---|
| author | Chen, Lesi Liu, Chengchang Luo, Luo Zhang, Jingzhao |
| author_facet | Chen, Lesi Liu, Chengchang Luo, Luo Zhang, Jingzhao |
| contents | Second-order optimization methods are computationally expensive for large-scale problems. Recently, Doikov, Chayti, and Jaggi (ICML 2023) proposed the LazyCRN method that reduces computation by studying the gradient complexity of second-order methods. Their method can achieve a gradient complexity of $\mathcal{O}( d + d^{1/2} ε^{-3/2})$ and $\mathcal{O}( d + d^{1/2} ε^{-1/2})$ for nonconvex and convex optimization, respectively, where $d$ is the effective dimension and $ε$ is the target precision. Very recently, Adil, Bullins, Sidford, and Zhang (NeurIPS 2025) improved the gradient complexity to $\mathcal{O}( d + d^{1/3} ε^{-3/2} \ln^{18} ε^{-1})$ for nonconvex optimization. However, the tightness of these methods remains open. In this work, we propose new methods that achieve an improved complexity of $\mathcal{O}( d + d^{1/3} ε^{-3/2})$ and $\mathcal{O}( (d + d^{13/21} ε^{-2/7}) \ln d)$ for nonconvex and convex optimization, respectively, improving best-known results for both setups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_17488 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity Chen, Lesi Liu, Chengchang Luo, Luo Zhang, Jingzhao Optimization and Control Second-order optimization methods are computationally expensive for large-scale problems. Recently, Doikov, Chayti, and Jaggi (ICML 2023) proposed the LazyCRN method that reduces computation by studying the gradient complexity of second-order methods. Their method can achieve a gradient complexity of $\mathcal{O}( d + d^{1/2} ε^{-3/2})$ and $\mathcal{O}( d + d^{1/2} ε^{-1/2})$ for nonconvex and convex optimization, respectively, where $d$ is the effective dimension and $ε$ is the target precision. Very recently, Adil, Bullins, Sidford, and Zhang (NeurIPS 2025) improved the gradient complexity to $\mathcal{O}( d + d^{1/3} ε^{-3/2} \ln^{18} ε^{-1})$ for nonconvex optimization. However, the tightness of these methods remains open. In this work, we propose new methods that achieve an improved complexity of $\mathcal{O}( d + d^{1/3} ε^{-3/2})$ and $\mathcal{O}( (d + d^{13/21} ε^{-2/7}) \ln d)$ for nonconvex and convex optimization, respectively, improving best-known results for both setups. |
| title | Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.17488 |