PreprintCC BY 4.0arXiv
Matching the Lower Bounds: Stochastic Contracting Cubic Newton and Its Optimal Acceleration
Abstract
We study second-order methods for convex stochastic optimization, where gradients and Hessians are available only through stochastic estimates with variances σ12 and σ22, 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 𝒪(σ1/√T+σ2/T+1/T2). Building on this construction, we develop an accelerated variant achieving 𝒪(σ1/√T+σ2/T2+1/T7/2), matching the known lower bounds of Agafonov et al. (2024) in all three terms.
Related
- Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding
- Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity
- Optimal Guidance with Terminal Intercept-Angle Constraints and Acceleration Bounds
- Pfaffian Positivity for Convex Kernels and Optimal Matching Bounds
- Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
BibTeX
@misc{agafonov2026matching,
title = {{Matching the Lower Bounds: Stochastic Contracting Cubic Newton and Its Optimal Acceleration}},
author = {Artem Agafonov and Aslan Ashabokov and Dmitry Kamzolov and Alexander D'yakonov and Alexander Gasnikov and Martin Takáč},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11693},
eprint = {2610.11693},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11693},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Matching the Lower Bounds: Stochastic Contracting Cubic Newton and Its Optimal Acceleration
AU - Artem Agafonov
AU - Aslan Ashabokov
AU - Dmitry Kamzolov
AU - Alexander D'yakonov
AU - Alexander Gasnikov
AU - Martin Takáč
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.11693
UR - https://arxiv.org/abs/2610.11693
AB - 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 𝒪(σ_1/√T+σ_2/T+1/T^2). Building on this construction, we develop an accelerated variant achieving 𝒪(σ_1/√T+σ_2/T^2+1/T^7/2), matching the known lower bounds of Agafonov et al. (2024) in all three terms.
ER -