Random Subspace Cubic-Regularization Methods, with Applications to Low-Rank Functions
This work addresses scalability challenges in optimization for machine learning and scientific computing, offering an incremental improvement by adapting existing methods to random subspaces.
The authors tackled the scalability issue of second-order optimization methods by proposing random subspace variants of the Adaptive Regularization using Cubics (ARC) algorithm, which maintain optimal convergence rates while reducing computational costs, particularly for low-rank functions where the method adapts subspace size to the true rank without prior knowledge.
We propose and analyze random subspace variants of the second-order Adaptive Regularization using Cubics (ARC) algorithm. These methods iteratively restrict the search space to some random subspace of the parameters, constructing and minimizing a local model only within this subspace. Thus, our variants only require access to (small-dimensional) projections of first- and second-order problem derivatives and calculate a reduced step inexpensively. Under suitable assumptions, the ensuing methods maintain the optimal first-order, and second-order, global rates 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 adaptive variant naturally adapts the subspace size to the true rank of the function, without knowing it a priori.