Abstract
We propose and analyze random subspace variants of the second-order AdaptiveRegularization using Cubics (ARC) algorithm. These methods iteratively restrictthe search space to some random subspace of the parameters, constructing andminimizing a local model only within this subspace. Thus, our variants onlyrequire access to (small-dimensional) projections of first- and second-orderproblem derivatives and calculate a reduced step inexpensively. Under suitableassumptions, the ensuing methods maintain the optimal first-order, andsecond-order, global rates of convergence of (full-dimensional) cubicregularization, while showing improved scalability both theoretically andnumerically, particularly when applied to low-rank functions. When applied tothe latter, our adaptive variant naturally adapts the subspace size to the truerank of the function, without knowing it a priori.