Optimal Parameter-Free Second-order Acceleration with Inexact Hessians under Generalized Smoothness
Abstract
We study second-order convex optimization under generalized Hessian smoothness, where the local Hessian Lipschitz constant may grow linearly with the gradient norm. For inexact Hessians, we develop adaptive algorithms, including an accelerated Monteiro-Svaiter-type method whose complexity matches the lower bound for second-order methods with δ-inexact Hessians in the classical Lipschitz-Hessian setting. Our methods are parameter-free in the sense that they require no problem-specific parameters as input, including the Hessian inexactness level δ and smoothness constants. Instead, their backtracking adapts a single regularization parameter that jointly captures Hessian inexactness and local Hessian smoothness. The resulting rates split into two regimes. Far from the solution, the gradient-dependent smoothness term yields geometric convergence. Near the solution, the rate is governed by the ordinary Hessian smoothness and the inexactness level δ, recovering the classical Lipschitz-Hessian guarantees.
Related
- Acceleration Survives Heavy Tails and Generalized Smoothness
- Parameter Dependence of Weighted Bergman Kernels Beyond Smoothness
- Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
- An Optimal Second-Order Algorithm for Finite-Sum Optimization under Average Smoothness and Convexity
- Localize, Restart, Accelerate: Stochastic Optimization under Generalized Smoothness
BibTeX
@misc{agafonov2026optimal,
title = {{Optimal Parameter-Free Second-order Acceleration with Inexact Hessians under Generalized Smoothness}},
author = {Artem Agafonov and Aslan Ashabokov and Alexander D'yakonov and Martin Takáč and Alexander Gasnikov and Dmitry Kamzolov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32977},
eprint = {2609.32977},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32977},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Parameter-Free Second-order Acceleration with Inexact Hessians under Generalized Smoothness
AU - Artem Agafonov
AU - Aslan Ashabokov
AU - Alexander D'yakonov
AU - Martin Takáč
AU - Alexander Gasnikov
AU - Dmitry Kamzolov
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32977
UR - https://arxiv.org/abs/2609.32977
AB - We study second-order convex optimization under generalized Hessian smoothness, where the local Hessian Lipschitz constant may grow linearly with the gradient norm. For inexact Hessians, we develop adaptive algorithms, including an accelerated Monteiro-Svaiter-type method whose complexity matches the lower bound for second-order methods with δ-inexact Hessians in the classical Lipschitz-Hessian setting. Our methods are parameter-free in the sense that they require no problem-specific parameters as input, including the Hessian inexactness level δ and smoothness constants. Instead, their backtracking adapts a single regularization parameter that jointly captures Hessian inexactness and local Hessian smoothness. The resulting rates split into two regimes. Far from the solution, the gradient-dependent smoothness term yields geometric convergence. Near the solution, the rate is governed by the ordinary Hessian smoothness and the inexactness level δ, recovering the classical Lipschitz-Hessian guarantees.
ER -