Scalable Second-Order Optimization Algorithms for Minimizing Low-rank Functions

2025/01/07 by Edward Tansley, Coralia Cartis, Tansley, Edward +1 · 1 citation
Computer Science · Engineering · #Advanced Image Processing Techniques #FOS: Mathematics #Image and Signal Denoising Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2501.03718

openalex publication_date 2025/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a random-subspace variant of cubic regularization algorithm that chooses the size of the subspace adaptively, based on the rank of the projected second derivative matrix. Iteratively, our variant only requires access to (small-dimensional) projections of first- and second-order problem derivatives and calculates a reduced step inexpensively. The ensuing method maintains the optimal global rate of convergence of (full-dimensional) cubic regularization, while showing improved scalability both theoretically and numerically, particularly when applied to low-rank functions. When applied to the latter, our algorithm naturally adapts the subspace size to the true rank of the function, without knowing it a priori.

Cited by

• Model-Driven Subspaces for Large-Scale Optimization with Local Approximation Strategy

Related

• Random Subspace Cubic-Regularization Methods, with Applications to Low-Rank Functions
• Cubic regularized subspace Newton for non-convex optimization
• Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
• Regularized methods via cubic model subspace minimization for nonconvex optimization
• Stochastic Subspace Cubic Newton Method