{"ID":2858385,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.08714","arxiv_id":"2510.08714","title":"Cubic Regularized Newton Method with Variance Reduction for Finite-sum Non-convex Problems","abstract":"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.","short_abstract":"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 r...","url_abs":"https://arxiv.org/abs/2510.08714","url_pdf":"https://arxiv.org/pdf/2510.08714v2","authors":"[\"Dmitry Pasechnyuk-Vilensky\",\"Dmitry Kamzolov\",\"Martin Takáč\"]","published":"2025-10-09T18:19:12Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}