Random Subspace Cubic-Regularization Methods, with Applications to Low-Rank Functions
Coralia Cartis, Zhen Shao, and, Edward Tansley · 2025
Read Random Subspace Cubic-Regularization Methods, with Applications to Low-Rank Functions by Coralia Cartis, Zhen Shao, and, Edward Tansley (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-09734.txt.
Introduction
Coralia Cartis, Zhen Shao, and Edward Tansley present faster methods for minimizing functions in very high dimensions by working in small random subspaces. Their base method builds a local cubic model of the function and steps to its low point. In full dimensions, that step needs costly derivative data at every round.
The new variants restrict each round to a randomly chosen small slice of the full space. Only the derivatives inside that slice are needed, so each step is cheap. The authors prove the variants keep the best known speed guarantees of the full method. On functions with low-rank structure, the method adjusts its slice size to match the hidden rank on its own. Tests back up the theory.
Catalog record
| CREATOR | Coralia Cartis, Zhen Shao, and, Edward Tansley |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 119 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-09734
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Random Subspace Cubic-Regularization Methods, with Applications to Low-Rank Functions Coralia Cartis, Zhen Shao, and, Edward Tansley Abstract 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. 1 Introduction Second-order optimization algorithms for the unconstrained optimization problem \min_{x\in\mathbb{R}^{d}}f(x), where f:\mathbb{R}^{d}\rightarrow\mathbb{R} is a sufficiently smooth, bounded-below function, use gradient and curvature information to determine iterates and thus, may have faster convergence than first-order algorithms that only rely on gradient information. However, for high-dimensional problems, when d is large, the computational cost of these methods can be a barrier to their use in practice. We are concerned with the task of scaling up second-order optimization algorithms so that they are a practical option for high-dimensional problems. An alternative to linesearch and trust-region techniques, Adaptive Regularization framework using Cubics (ARC) [ 57 , 14 ] determines the change s_{k} between the current iterate x_{k} and x_{k+1} by (approximately) solving a cubically-regularized local quadratic model: \argmin_{s\in\mathbb{R}^{d}}m_{k}(s)=f(x_{k})+\langle\nabla f(x_{k}),\ s\rangle+\frac{1}{2}\langle s,\ \nabla^{2}f(x_{k})s\rangle+\frac{1}{3\alpha_{k}}||s||_{2}^{3} (1.1) where \nabla f and \nabla^{2}f denote the gradient and Hessian of f and \sigma_{k}=1/{\alpha_{k}}>0 is the regularization parameter 1 1 1 The scaling of the regularization factor \frac{1}{3\alpha_{k}} may equivalently vary as \frac{\sigma_{k}}{3} or \frac{\sigma_{k}}{3!} . . Assuming Lipschitz continuity of the Hessian on the iterates’ path, ARC requires at most \mathcal{O}\left(\epsilon^{-\frac{3}{2}}\right) iterations and function and (first- and second-) derivative evaluations to attain an \epsilon -approximate first-order critical point; this convergence rate is optimal over a large class of second-order methods [ 15 ] . Dimensionality reduction in the parameter space Approximately minimizing the local model given by ( 1.1 ) to find a search step, is computationally expensive as it requires iteratively solving \mathcal{O}(d) -dimensional linear systems involving \nabla^{2}f(x_{k}) and \nabla f(x_{k}) (using factorization-based approaches or iterative, Krylov-type ones [ 15 ] ). Furthermore, the memory cost of (full-dimensional) problem information such as \nabla^{2}f(x_{k}) and \nabla f(x_{k}) may also be prohibitively expensive in some applications. These computational costs involved in the step calculation motivate us to consider dimensionality reduction techniques that access/store reduced problem information of smaller dimensions, and so operate in (random) subspaces of the variables rather than in the full space. Random subspace variants of ARC At every iteration of a random subspace method, the search space is restricted to some smaller-dimensional subspace of the functional domain (here, \mathbb{R}^{d} ), and then the search step is computed in this subspace. In particular, the random subspace at the k th iteration is the row span of a sketching matrix S_{k}\in\mathbb{R}^{l\times d} [ 74 , 53 ] with entries drawn, for example, from a (scaled) Gaussian distribution (or other useful distributions); this is advantageous as such random matrices have length-preserving properties according to Johnson-Lindenstrauss (JL) Lemma [ 44 ] , which helps essentially preserve the length of gradients through the subspace projection. Thus, Random Subspace ARC (R-ARC) replaces s\in\mathbb{R}^{d} in ( 1.1 ) by s=S_{k}^{\top}\hat{s} , where \hat{s}\in\mathbb{R}^{l} , l\ll d , which leads to the reduced model ( 3.1 ) which employs only the reduced gradient S_{k}\nabla f(x_{k}) and reduced Hessian S_{k}\nabla^{2}f(x_{k})S_{k}^{\top} , of a sketched objective \hat{f}(y)=f(S^{T}_{k}y) , y\in\mathbb{R}^{l} . As such, R-ARC only requires these projected, low(er)-dimensional problem information, S_{k}\nabla f(x_{k}) and S_{k}\nabla^{2}f(x_{k})S_{k}^{\top} , rather than their full-dimensional counterparts, allowing application of these methods to problems where full information is not available/too expensive. The former can be calculated efficiently without evaluation of full gradients and Hessians, by requiring gradient inner products and Hessian-vector products with a small subset of (random) directions; for example, S_{k}\nabla f(x_{k}) requires only l directional derivatives of f corresponding to the rows of S_{k} . These directional derivatives can be calculated by a small number of finite differences or by using automatic differentiation, requiring only the tangent model application without complete calculation and storage of an adjoint. The main focus here is on presenting a random subspace algorithm and associated analysis that recovers, with high probability, the optimal global rate of convergence of cubic regularization, namely, \mathcal{O}(\epsilon^{-3/2}) to drive the gradient of the objective below \epsilon ; and to provide also, a global rate of convergence to second-order critical points, which is novel. To achieve these strong global rate guarantees while also ensuring high scalability, our random subspace variant of cubic regularization, R-ARC, can take advantage/benefits when special problem structure is present, namely, low rank, as we explain below. Then, arbitrarily small subspace dimensions can be chosen, even adaptively (as our R-ARC-D variant proposes), while the optimal worst-case complexity bound of order \mathcal{O}(\epsilon^{-3/2}) is guaranteed. We note that under mild(er) assumptions and for general objectives (without special structure), a worst-case complexity bound of order \mathcal{O}(\epsilon^{-2}) is guaranteed for R-ARC by the results in [ 13 ] . The challenge here is to find sufficient conditions on the algorithm and the problem that ensure that the random subspace ARC variant satisfies the optimal complexity bound of full-dimensional ARC and then to assess which of these conditions also achieve scalable variants. Existing literature As an example, when the sketching matrix S_{k} is a (uniform) sampling matrix, random subspace methods are random block coordinate variants, which in their first-order instantiations and only require a subset of partial derivatives to calculate an approximate gradient direction [ 56 , 65 ] . Despite documented failures of (deterministic) coordinate techniques on some problems [ 62 ] , the challenges of large-scale applications have brought these methods to the forefront of research in the last decade; see [ 75 ] for a survey of this active area, particularly for convex optimization. Developments of these methods for nonconvex optimization can be found, for example, in [ 64 , 60 , 51 ] and more recently, [ 78 ] ; with extensions to constrained problems [ 8 , 2 ] , and distributed strategies [ 27 , 33 ] . Subspace methods can be seen as an extension of (block) coordinate methods by allowing the reduced variables to vary in (possibly randomly chosen) subspaces that are not necessarily aligned with coordinate directions. (Deterministic) subspace and decomposition methods have been of steadfast interest in the optimization community for decades. In particular, Krylov subspace methods can be applied to calculate – at typically lower computational cost and in a matrix free way – an approximate Newton-type search direction over increasing and nested subspaces; see [ 58 ] for Newton-CG techniques (and further references), [ 36 , 24 ] for initial trust-region variants and [ 15 ] for cubic regularization variants. However, these methods still require that the full gradient vector is calculated/available at each iteration, as well as (full) Hessian matrix actions. The requirements of large-scale