Cubic Regularized Newton Method with Variance Reduction for Finite-sum Non-convex Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914508553846784 |
|---|---|
| author | Pasechnyuk-Vilensky, Dmitry Kamzolov, Dmitry Takáč, Martin |
| author_facet | Pasechnyuk-Vilensky, Dmitry Kamzolov, Dmitry Takáč, Martin |
| contents | We study finite-sum non-convex optimization $\min_{x\in\mathbb{R}^d} F(x) \;=\; \frac{1}{n}\sum_{i=1}^n f_i(x)$ and analyze a variance-reduced cubic Newton method based on EMA-smoothed SARAH estimators for both gradient and Hessian information. The method combines a coarse stochastic backbone with a terminal homotopy refinement: once the iterates enter a certified small-step regime, the algorithm decreases the regularization level geometrically, shortens the stage length, and increases the mini-batch size at the reciprocal rate while restarting exact finite-sum snapshots at each stage. We work under average squared gradient smoothness and average mean-cubed Hessian smoothness, thereby avoiding the trajectory-wise Hessian boundedness assumption that is often used in related analyses. Under these assumptions and a standard inexact cubic-subproblem certificate, we establish that the method returns an $(\varepsilon,\sqrt{L_2\varepsilon})$-second-order stationary point with total finite-sum oracle complexity $n+\widetilde{\mathcal O}\!\left(n^{1/2}\varepsilon^{-3/2}\right)$. The analysis separates into a coarse progress phase, which yields the $n^{1/2}$-scaled stochastic backbone, and a terminal local bootstrap, which supplies the pointwise accuracy needed to turn the model step certificate into a true second-order certificate. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_08714 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cubic Regularized Newton Method with Variance Reduction for Finite-sum Non-convex Problems Pasechnyuk-Vilensky, Dmitry Kamzolov, Dmitry Takáč, Martin Optimization and Control 65K10 G.1.6 We study finite-sum non-convex optimization $\min_{x\in\mathbb{R}^d} F(x) \;=\; \frac{1}{n}\sum_{i=1}^n f_i(x)$ and analyze a variance-reduced cubic Newton method based on EMA-smoothed SARAH estimators for both gradient and Hessian information. The method combines a coarse stochastic backbone with a terminal homotopy refinement: once the iterates enter a certified small-step regime, the algorithm decreases the regularization level geometrically, shortens the stage length, and increases the mini-batch size at the reciprocal rate while restarting exact finite-sum snapshots at each stage. We work under average squared gradient smoothness and average mean-cubed Hessian smoothness, thereby avoiding the trajectory-wise Hessian boundedness assumption that is often used in related analyses. Under these assumptions and a standard inexact cubic-subproblem certificate, we establish that the method returns an $(\varepsilon,\sqrt{L_2\varepsilon})$-second-order stationary point with total finite-sum oracle complexity $n+\widetilde{\mathcal O}\!\left(n^{1/2}\varepsilon^{-3/2}\right)$. The analysis separates into a coarse progress phase, which yields the $n^{1/2}$-scaled stochastic backbone, and a terminal local bootstrap, which supplies the pointwise accuracy needed to turn the model step certificate into a true second-order certificate. |
| title | Cubic Regularized Newton Method with Variance Reduction for Finite-sum Non-convex Problems |
| topic | Optimization and Control 65K10 G.1.6 |
| url | https://arxiv.org/abs/2510.08714 |