EUROPT 2025
Abstract Submission

276. Scalable Second-Order Optimization Algorithms for Minimizing Low-Rank Functions

Invited abstract in session TB-5: Randomized Optimization algorithms I, stream Optimization for machine learning.

Tuesday, 10:30-12:30
Room: B100/4013

Authors (first author is the speaker)

1. Edward Tansley
Mathematical Institute, University of Oxford
2. Coralia Cartis
Mathematical Institute, University of Oxford
3. Zhen Shao
University of Oxford

Abstract

Second-order optimization algorithms, such as Adaptive Regularization framework using Cubics (ARC), often have faster convergence rates than first-order algorithms that only rely on gradient information. However, for high-dimensional problems, the computational cost of these methods can be a barrier to their use in practice.
We present R-ARC-D, a random subspace variant of ARC that chooses the size of the subspace adaptively, based on the rank of the projected second derivative matrix. At each iteration, our variant only requires access to (low-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 to an approximate first-order minimizer of (full-dimensional) cubic regularization, while showing improved scalability both theoretically and numerically, particularly when applied to low-rank functions (i.e., functions that vary in only a low-dimensional linear subspace of dimension r).
When applied to these low-rank functions, our algorithm naturally adapts the subspace size to the true rank of the function, without knowing it a priori. We observe this behaviour through numerical experiments, which confirm that R-ARC-D effectively adapts to the function’s true rank. Additionally, we demonstrate its strong performance and improved scalability compared to the full-dimensional ARC on high-dimensional problems.

Keywords

Status: accepted

Back to the list of papers