Affine-invariant Cubic Newton with Weak Learners
Abstract
Modern gradient boosting algorithms are based on Newton's method, which excels empirically but lacks global convergence guarantees. While recent work on Gradient-Regularized Newton (GRN) boosting achieved a global 𝒪(1/γ12k2) rate, its analysis was not able to exploit the natural Hessian geometry and suffers from a heavy γ12 dependence on a worst-case `weak gradient edge' γ. In this paper, we tackle these theoretical drawbacks by generalizing the Affine-Invariant Cubic Newton (AICN) scheme to convex optimization with weak learners. Our analysis is based on average cosine values Θ̅k along the optimization path and directional improvements δk in the Hessian-induced norm. We show that the weak-AICN update reduces to a damped weak-Newton step with an explicit stepsize determined by δk. Under semi-strong self-concordance, we establish a global 𝒪(1/Θ̅k4 k2) rate, significantly improving upon the weak-GRN bound. We further prove a local linear rate, global linear convergence for Hessian-dominated losses, cosine angle lower bounds, and present weak-AdaAICN, which adaptively tunes the cubic regularization. Finally, we demonstrate the broader applicability of this framework beyond gradient boosting by showing that Newton coordinate descent emerges naturally as a special case of optimization with weak learners.
Related
- Deriving Newton's Canonical Forms of Cubic Curves via the Center of Polynomials
- Matching the Lower Bounds: Stochastic Contracting Cubic Newton and Its Optimal Acceleration
- Envelope Cubic Regularized Newton Method for Nonconvex-Strongly-Concave Minimax Optimization
- A Regularized Newton-Type Method for Manifold--Affine Intersection Problems under Intrinsic Transversality
- Geometric Invariant Theory for Affine Superschemes
BibTeX
@misc{zozoulenko2026affineinvariant,
title = {{Affine-invariant Cubic Newton with Weak Learners}},
author = {Nikita Zozoulenko and Daniel Falkowski and Thomas Cass and Lukas Gonon},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33516},
eprint = {2610.33516},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33516},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Affine-invariant Cubic Newton with Weak Learners
AU - Nikita Zozoulenko
AU - Daniel Falkowski
AU - Thomas Cass
AU - Lukas Gonon
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33516
UR - https://arxiv.org/abs/2610.33516
AB - Modern gradient boosting algorithms are based on Newton's method, which excels empirically but lacks global convergence guarantees. While recent work on Gradient-Regularized Newton (GRN) boosting achieved a global 𝒪(1/γ^12k^2) rate, its analysis was not able to exploit the natural Hessian geometry and suffers from a heavy γ^12 dependence on a worst-case `weak gradient edge' γ. In this paper, we tackle these theoretical drawbacks by generalizing the Affine-Invariant Cubic Newton (AICN) scheme to convex optimization with weak learners. Our analysis is based on average cosine values Θ̅_k along the optimization path and directional improvements δ_k in the Hessian-induced norm. We show that the weak-AICN update reduces to a damped weak-Newton step with an explicit stepsize determined by δ_k. Under semi-strong self-concordance, we establish a global 𝒪(1/Θ̅_k^4 k^2) rate, significantly improving upon the weak-GRN bound. We further prove a local linear rate, global linear convergence for Hessian-dominated losses, cosine angle lower bounds, and present weak-AdaAICN, which adaptively tunes the cubic regularization. Finally, we demonstrate the broader applicability of this framework beyond gradient boosting by showing that Newton coordinate descent emerges naturally as a special case of optimization with weak learners.
ER -