CaCuTe: Casual Cubic-Model Technique for Faster Optimization

Nazarii Tupitsa · 2025

Read CaCuTe: Casual Cubic-Model Technique for Faster Optimization by Nazarii Tupitsa (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-18508.txt.

Introduction

Optimization routines hunt for the lowest point of a cost curve, and speed near the goal matters. Nazarii Tupitsa presents CaCuTe, a casual cubic-model technique for faster optimization, in this 2025 paper. The core is a plain gradient step with a step size set by the gradient's size and a curvature bound. He proves it converges at a fast local rate.

A check based on cheap curvature probes tells the method when that fast regime holds, with no full curvature matrix needed. That check plugs into cubic-regularized Newton methods, letting each step switch between cubic and gradient moves while keeping global guarantees. A first-order version stays monotone, adapts on its own, and needs no tuned parameters. In tests it posted the lowest run times among rivals. The paper extends the idea to noisy, stochastic settings and to looser smoothness rules.

Catalog record

CREATORNazarii Tupitsa
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-18508

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

CaCuTe: Casual Cubic-Model Technique for Faster Optimization Nazarii Tupitsa Abstract We establish a local 𝒪 ⁡ ( k − 2 ) \mathcal{O}(k^{-2}) rate for the gradient update x k + 1 = x k − ∇ f ​ ( x k ) / H ​ ‖ ∇ f ​ ( x k ) ‖ x^{k+1}=x^{k}-\nabla f(x^{k})/\sqrt{H\|\nabla f(x^{k})\|} under a 2 ​ H 2H -Hessian–Lipschitz assumption. Regime detection relies on Hessian–vector products, avoiding Hessian formation or factorization. Incorporating this certificate into cubic-regularized Newton (CRN) and an accelerated variant enables per-iterate switching between the cubic and gradient steps while preserving CRN’s global guarantees. The technique achieves the lowest wall-clock time among compared baselines in our experiments. In the first-order setting, the technique yields a monotone, adaptive, parameter-free method that inherits the local 𝒪 ⁡ ( k − 2 ) \mathcal{O}(k^{-2}) rate. Despite backtracking, the method shows superior wall-clock performance. Additionally, we cover smoothness relaxations beyond classical gradient–Lipschitzness, enabling tighter bounds, including global 𝒪 ⁡ ( k − 2 ) \mathcal{O}(k^{-2}) rates. Finally, we generalize the technique to the stochastic setting. \MHInternalSyntaxOn \MHInternalSyntaxOff 1 Introduction In this work, we are interested in solving the unconstrained minimization problem \min_{x\in\mathbb{R}^{d}}f(x) where f\colon\mathbb{R}^{d}\to\mathbb{R} is a twice-differentiable function with Lipschitz Hessian. 1.1 Motivation The cubic regularized Newton ( CRN ) method [ Griewank, 1981 ] naturally follows from the Lipschitz–Hessian assumption [ Nesterov and Polyak, 2006 ] . Its update can be written implicitly as H\|x^{k+1}-x^{k}\|(x^{k+1}-x^{k})=-\nabla f(x^{k})-\nabla^{2}f(x^{k})(x^{k+1}-x^{k}) where H>0 is a constant, {\bf I} is the identity matrix. When the quadratic term is negligible, i.e. H\|x^{k+1}-x^{k}\|^{3}\gg\langle\nabla^{2}f(x^{k})(x^{k+1}-x^{k}),x^{k+1}-x^{k}\rangle an approximate update formula reads as H\|x^{k+1}-x^{k}\|^{3}\approx-\langle\nabla f(x^{k}),x^{k+1}-x^{k}\rangle\quad\text{or}\quad x^{k+1}\approx x^{k}-\frac{\nabla f(x^{k})}{\sqrt{H\|\nabla f(x^{k})\|}} and raises a natural question: Can we provably avoid Hessian evaluation and matrix inversion while retaining an {\cal O}(k^{-2}) rate? This affirmative result shows that the convergence is achievable with a first-order method and naturally leads to the next question. How to utilize Hessian smoothness for the first order methods? This question is central, since exact second-order steps are often infeasible in modern high-dimensional problems even when Hessian smoothness holds. Our approach leverages smoothness without forming or inverting Hessians. We also extend the framework to stochastic optimization, yielding practical algorithms for large-scale applications. 1.2 Related works Cubic Regularization. Beyond advances in Quasi-Newton methods [ Scheinberg and Tang, 2016 , Ghanbari and Scheinberg, 2018 , Rodomanov and Nesterov, 2021a , Rodomanov and Nesterov, 2021b , Jin et al., 2022 , Berahas et al., 2022 , Kamzolov et al., 2023 , Jin et al., 2024 , Scieur, 2024 , Wang et al., 2024 ] , global convergence guarantees in the convex enhances by cubic regularization [ Kamzolov et al., 2023 , Scieur, 2024 , Wang et al., 2024 ] . However, those methods result in implicit (explicit for [ Mishchenko, 2023 ] ) update formula requiring additional line search in each iteration, involving matrix inversions. Our approach enables occasional skipping of these costly operations. We also obtain a result similar to [ Agafonov et al., 2025 ] , which establishes global {\cal O}(k^{-1}) rate while having {\cal O}(k^{-2}) at the first iterates. Adaptive Gradient Methods. Gradient descent is attractive for its simplicity and low per-iteration cost, the only hyperparameter is the step size: classical Lipschitz-based analyses pick a constant step to ensure monotone decrease, but this requires the (unknown) Lipschitz constant and is typically overly conservative in practice [ Malitsky and Mishchenko, 2020 ] . Backtracking line search [ Nocedal and Wright, 2006 ] , which gives theoretical convergence guarantee, is a parameter-free adaptive alternative to constant step sizes. However its try-increase nature can be avoided while keeping adaptivity without any extra computations under convexity and Lipschitz gradients [ Malitsky and Mishchenko, 2020 , Malitsky and Mishchenko, 2024 ] . Alternative adaptive methods with Polyak-stepsize [ Polyak, 1987 ] , requires a knowledge of a value of the objective’s minimum. Smoothness. Smoothness relaxations recently draw significant attention recently. One of such assumptions is (L_{0},L_{1}) -smoothness originally introduced by [ Zhang et al., 2020b ] for twice differentiable functions, and extended to the class of differentiable but not necessarily twice differentiable functions [ Zhang et al., 2020a , Chen et al., 2023 ] . We introduce the assumption that the Hessian eigenvalue in the gradient direction grow linearly with the square root of the optimality gap instead gradient norm . Another closely related work [ Mishkin et al., 2024 ] also study directional smoothness, but based on a quadratic model, in contrast to ours cubic one. Adaptive methods [ Defazio and Mishchenko, 2023 , Mishchenko and Defazio, 2024 , Ivgi et al., 2023 , Khaled et al., 2023 ] avoid smoothness assumption in their analysis in the convex setting as well as any line search. HVP Methods. To the best of our knowledge Hessian vector products are used only for Hessian approximation [ Jahani and Rusakov, 2022 , Yao et al., 2021 , Yao et al., 2018 , Sen and Mohan, 2023 ] i.e. based on [ Bekas et al., 2007 ] . Except the closest work [ Smee et al., 2025 ] , which studies similar idea for non-convex deterministic setup. Also, a similar step size appears in [ Thomsen and Doikov, 2024 ] , which studies quadratic functions. 1.3 Our Contribution • Certificate for Cubic-Model Decrease. We introduces an Hessian–vector product (HVP 1 1 1 The cost of computing Hessian–vector products is of the same order as that of gradients [ Agarwal et al., 2016 ] . )-based certificate to decide when the gradient step ( x^{k+1}=x^{k}-{\nabla f(x^{k})}/{\sqrt{H_{k}\|\nabla f(x^{k})\|}} , where H_{k} is a local estimate of the Hessian–Lipschitz constant) decrease (corresponds coincides aligns) with the cubic-model i.e. CRN step decrease. Cubic-model decrease holds under vanishing directional curvature (see ( 12 )) and yields {\cal O}(k^{-2}) global rate for i.e logistic loss function. • Ca sual Cu bic N ewton ( CaCuN ). The certificate enables provable obviating the second order work (Hessian computation and factorization) for CRN [ Nesterov and Polyak, 2006 ] type methods retaining global {\cal O}(k^{-2}) rate. • Acc elerated Ca sual Cu bic N ewton ( AccCaCuN ). Same argument applies for accelerated CRN retaining AccCaCuN ’s global {\cal O}(k^{-3}) rate. The method obviates the second order work under vanishing directional curvature . • Ca sual Cu bic Ad aptive G radient D escent ( CaCuAdGD ). The central contribution of our work addresses the infeasibility of directly applying second-order methods. Our technique exploits Hessian smoothness through backtracking on directional curvature (see ( 16 )), which requires only Hessian–vector products. When the cubic-model decrease does not apply, the method falls back to the standard quadratic-model decrease. The method is monotone, parameter-free and shows superior wall-clock performance in experiments compared to, e.g., AdGD [ Malitsky and Mishchenko, 2020 ] . • Gradient-Directional Smoothness Relaxation. We propose an assumption allowing the Hessian eigenvalue in the gradient direction to grow linearly with the square root of the optimality gap. It enables tighter convergence rates and, in particular, a global cubic-model decrease rate, e.g., for logistic regression under separability. • Ca sual Cu bic S tochastic G radient D escent ( CaCuSGD ). Under standard assumptions, having the mini-batch gradient and the batched Hessian–gradient estimator, our analysis recovers either

Read the complete text