CaCuTe Meets SESOP: Better Theory and Practice with Lipschitz Hessians
Abstract
We combine CaCuTe with sequential subspace optimization (SESOP) for smooth convex minimization under Lipschitz continuity of the Hessian. The resulting method, CaCuSESOP, achieves the global rate O(k−2) with a fixed number of Hessian--vector products per iteration, while removing key limitations of classical SESOP. In particular, exact minimization of the original objective is replaced by minimization of a low-dimensional cubic upper model, which needs only be solved to a computable accuracy. The cubic regularization parameter is selected by backtracking. If the Hessian at the minimizer is positive definite, CaCuSESOP automatically attains an accelerated local linear rate with complexity O(√(κ⋆)log(1/ε)). Neither the local strong-convexity parameter, the condition number κ⋆, nor the optimal value is supplied to the algorithm. We give finite bounds for entering this regime and adapting the restart schedule. Finally, we prove that the global O(k−2) rate is optimal for the considered fixed-budget gradient/Hessian--vector-product linear-span oracle class, even with momentum and unrestricted memory.
Related
- Limit theory for Lipschitz-localized statistics in random geometric models
- Optimal Parameter-Free Second-order Acceleration with Inexact Hessians under Generalized Smoothness
- Gauss-Newton Accuracy and Indefinite Hessians: Uniform Coexistence in Low-Cost Sets
- Sparsity by Default: The Theory and Practice of ARD in Gaussian Process Regression for Variable Selection
- Low regularity maps on Lipschitz manifolds: lifting, pullback of forms, and approximation
BibTeX
@misc{tupitsa2026cacute,
title = {{CaCuTe Meets SESOP: Better Theory and Practice with Lipschitz Hessians}},
author = {Nazarii Tupitsa},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06557},
eprint = {2610.06557},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06557},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - CaCuTe Meets SESOP: Better Theory and Practice with Lipschitz Hessians
AU - Nazarii Tupitsa
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06557
UR - https://arxiv.org/abs/2610.06557
AB - We combine CaCuTe with sequential subspace optimization (SESOP) for smooth convex minimization under Lipschitz continuity of the Hessian. The resulting method, CaCuSESOP, achieves the global rate O(k^−2) with a fixed number of Hessian--vector products per iteration, while removing key limitations of classical SESOP. In particular, exact minimization of the original objective is replaced by minimization of a low-dimensional cubic upper model, which needs only be solved to a computable accuracy. The cubic regularization parameter is selected by backtracking. If the Hessian at the minimizer is positive definite, CaCuSESOP automatically attains an accelerated local linear rate with complexity O(√(κ_⋆)log(1/ε)). Neither the local strong-convexity parameter, the condition number κ_⋆, nor the optimal value is supplied to the algorithm. We give finite bounds for entering this regime and adapting the restart schedule. Finally, we prove that the global O(k^−2) rate is optimal for the considered fixed-budget gradient/Hessian--vector-product linear-span oracle class, even with momentum and unrestricted memory.
ER -