History-Aware Adaptive High-Order Tensor Regularization

2025/11/08 by He, Chang, Jiang, Bo, Jiang, Yuntian +2 · 1 citation
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications

paper · doi:10.48550/arxiv.2511.05788

openalex publication_date 2025/11/08 · openalex created_date 2025/11/12 · openalex updated_date 2026/07/28

Abstract

In this paper, we develop a new adaptive regularization method for minimizing a composite function, which is the sum of a pth-order (p ≥ 1) Lipschitz continuous function and a simple, convex, and possibly nonsmooth function. We use a history of local Lipschitz estimates to adaptively select the current regularization parameter, an approach we shall term the \it history-aware adaptive regularization method. We explore how the selection of an appropriate volume of historical information affects both the theoretical and practical performance. By using all the historical information, our method matches the complexity guarantees of the standard pth-order tensor methods that require a known Lipschitz constant, for both convex and nonconvex objectives. In the nonconvex case, the number of iterations required to find an (ε_g,ε_H)-approximate second-order stationary point is bounded by O(max\ε_g^-(p+1)/p, ε_H^-(p+1)/(p-1)\). For convex functions, we establish an O(ε^-1/p) iteration complexity for finding an ε-approximate optimal point and further propose an accelerated variant attaining an iteration complexity of O(ε^-1/(p+1)). For practical consideration, we propose several variants of this method with only part of historical information. We introduce cyclic and sliding-window strategies for choosing historical Lipschitz estimates, which mitigate the limitation of overly conservative updates. As long as a rough upper bound of the Lipschitz constant is known, these two variants achieve the same iteration complexity guarantees in terms of the input accuracy as the method using full historical information. Finally, extensive numerical experiments are conducted to demonstrate the effectiveness of our adaptive approach.

Citations

• High-order Accumulative Regularization for Gradient Minimization in Convex Programming
• Accelerating Trust-Region Methods: An Attempt to Balance Global and Local Efficiency
• A Simple Adaptive Proximal Gradient Method for Nonconvex Optimization
• Stochastic Adaptive Gradient Descent Without Descent
• Simple linesearch-free first-order methods for nonconvex optimization
• An Adaptive and Parameter-Free Nesterov's Accelerated Gradient Method for Convex Optimization
• Global Optimality Characterizations and Algorithms for Minimizing Quartically-Regularized Third-Order Taylor Polynomials
• Efficient Implementation of Third-Order Tensor Methods with Adaptive Regularization for Unconstrained Optimization
• Projected gradient methods for nonconvex and stochastic optimization: new complexities and auto-conditioned stepsizes
• Gradient Methods with Online Scaling
• Inexact and Implementable Accelerated Newton Proximal Extragradient Method for Convex Optimization
• Adaptive proximal gradient methods are universal without approximation
• AdaBB: Adaptive Barzilai-Borwein Method for Convex Optimization
• Cubic-quartic regularization models for solving polynomial subproblems in third-order tensor methods
• Newton-CG methods for nonconvex unconstrained optimization with Hölder continuous Hessian
• Beyond Nonconvexity: A Universal Trust-Region Method with New Analyses
• A simple uniformly optimal method without line search for convex optimization
• Second-order methods for quartically-regularised cubic polynomials, with applications to high-order tensor methods
• Adaptive Proximal Gradient Method for Convex Optimization
• Homogeneous Second-Order Descent Framework: A Fast Alternative to Newton-Type Methods
• Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient
• A homogeneous second-order descent method for nonconvex optimization
• Super-Universal Regularized Newton Method
• Optimal and Adaptive Monteiro-Svaiter Acceleration
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
• Gradient Regularization of Newton Method with Bregman Distances
• Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
• Inexact Newton-CG Algorithms With Complexity Guarantees
• Stochastic Subspace Cubic Newton Method
• Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization
• A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization
• A Newton-CG Algorithm with Complexity Guarantees for Smooth\n Unconstrained Optimization
• Accelerating Adaptive Cubic Regularization of Newton's Method via Random Sampling
• CUTEst: a Constrained and Unconstrained Testing Environment with safe threads for mathematical optimization

Cited by

• New Results on the Polyak Stepsize: Tight Convergence Analysis and Universal Function Classes

Related

• A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization
• Local Convergence of Adaptively Regularized Tensor Methods
• On the Complexity of Lower-Order Implementations of Higher-Order Methods
• Global Convergence of High-Order Regularization Methods with Sums-of-Squares Taylor Models
• Efficient Implementation of Third-Order Tensor Methods with Adaptive Regularization for Unconstrained Optimization