Matching the Lower Bounds: Stochastic Contracting Cubic Newton and Its Optimal Acceleration

Artem Agafonov, Aslan Ashabokov, Dmitry Kamzolov, Alexander D'yakonov, Alexander Gasnikov, Martin Takáč

arXivarxiv/2610.11693Oct 8, 2026math.OCscore 0

We study second-order methods for convex stochastic optimization, where gradients and Hessians are available only through stochastic estimates with variances $σ_1^2$ and $σ_2^2$, respectively. First, we propose the Stochastic Contracting Cubic Newton method. At each iteration, it minimizes a cubic model with additional quadratic regularization and then contracts the step toward the current point. After $T$ iterations, the method achieves the expected convergence rate $\mathcal{O}(σ_1/\sqrt{T}+σ_2/T+1/T^2)$. Building on this construction, we develop an accelerated variant achieving…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.11693
curl -X POST /api/v1/records/arxiv/2610.11693/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.11693/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'