CaCuTe: Casual Cubic-Model Technique for Faster Optimization

2025/09/23 by Nazarii Tupitsa, Tupitsa, Nazarii
Computer Science · Engineering · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2509.18508

Abstract

We establish a local O(k^-2) rate for the gradient update x^k+1=x^k-∇ f(x^k)/√(H‖∇ f(x^k)‖) under a 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 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 O(k^-2) rates. Finally, we generalize the technique to the stochastic setting.

Citations

• Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
• First-ish Order Methods: Hessian-aware Scalings of Gradient Descent
• Global non-asymptotic super-linear convergence rates of regularized proximal quasi-Newton methods on non-smooth composite problems
• Complexity of Minimizing Regularized Convex Quadratic Functions
• Non-asymptotic Global Convergence Rates of BFGS with Exact Line Search
• Directional Smoothness and Gradient Methods: Convergence and Adaptivity
• Adaptive Proximal Gradient Method for Convex Optimization
• Prodigy: An Expeditiously Adaptive Parameter-Free Learner
• Adaptive Quasi-Newton and Anderson Acceleration Framework with Explicit Global (Accelerated) Convergence Rates
• DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method
• Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization
• Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods
• Cubic Regularization is the Key! The First Accelerated Quasi-Newton Method with a Global Convergence Rate of O(k^-2) for Convex Functions
• DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule
• Learning-Rate-Free Learning by D-Adaptation
• Sharpened Quasi-Newton Methods: Faster Superlinear Rate and Larger Local Convergence Neighborhood
• Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information
• Improved Analysis of Clipping Algorithms for Non-convex Optimization
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and\n Coordinate Descent
• Quasi-Newton Methods for Machine Learning: Forget the Past, Just Sample
• Proximal Quasi-Newton Methods for Regularized Convex Optimization with\n Linear and Accelerated Sublinear Convergence Rates
• Practical Inexact Proximal Quasi-Newton Method with Global Complexity Analysis

Related

• A Unified Scheme to Accelerate Adaptive Cubic Regularization and Gradient Methods for Convex Optimization
• Stochastic Cubic Regularization for Fast Nonconvex Optimization
• Accelerating Adaptive Cubic Regularization of Newton's Method via Random Sampling
• Cubic Regularization is the Key! The First Accelerated Quasi-Newton Method with a Global Convergence Rate of O(k^-2) for Convex Functions
• Regularized Newton Method with Global O(1/k²) Convergence