Symmetric Rank-One Quasi-Newton Methods for Deep Learning Using Cubic Regularization
Aditya Ranganath, Mukesh Singhal, Roummel Marcia · 2025
Read Symmetric Rank-One Quasi-Newton Methods for Deep Learning Using Cubic Regularization by Aditya Ranganath, Mukesh Singhal, Roummel Marcia (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-2502-12298.txt.
Introduction
Aditya Ranganath, Mukesh Singhal, and Roummel Marcia present a 2025 paper on training deep networks. First-order methods like Adam are cheap and popular. They ignore curvature, the bend of the loss surface. Ignoring bend can strand training at saddle points or poor valleys. Quasi-Newton methods estimate curvature from past steps at like cost. The most used update forces a safe, bowl-like estimate, which suits line searches.
Deep network losses are not bowl-shaped, so forced-safe estimates can mislead. The team proposes a limited-memory rank-one update paired with cubic control. Rank-one updates can follow true bend, including negative bend. Cubic control keeps steps sane when bend is wild. ML engineers get a curvature-aware trainer that fits deep learning's messy surfaces. The work speaks to readers who tune large models and want faster, surer convergence than plain gradient steps give.
Catalog record
| CREATOR | Aditya Ranganath, Mukesh Singhal, Roummel Marcia |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-12298
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Symmetric Rank-One Quasi-Newton Methods for Deep Learning Using Cubic Regularization Aditya Ranganath, Mukesh Singhal, Roummel Marcia Abstract Stochastic gradient descent and other first-order variants, such as Adam and AdaGrad, are commonly used in the field of deep learning due to their computational efficiency and low-storage memory requirements. However, these methods do not exploit curvature information. Consequently, iterates can converge to saddle points or poor local minima. On the other hand, Quasi-Newton methods compute Hessian approximations which exploit this information with a comparable computational budget. Quasi-Newton methods re-use previously computed iterates and gradients to compute a low-rank structured update. The most widely used quasi-Newton update is the L-BFGS, which guarantees a positive semi-definite Hessian approximation, making it suitable in a line search setting. However, the loss functions in DNNs are non-convex, where the Hessian is potentially non-positive definite. In this paper, we propose using a limited-memory symmetric rank-one quasi-Newton approach which allows for indefinite Hessian approximations, enabling directions of negative curvature to be exploited. Furthermore, we use a modified adaptive regularized cubics approach, which generates a sequence of cubic subproblems that have closed-form solutions with suitable regularization choices. We investigate the performance of our proposed method on autoencoders and feed-forward neural network models and compare our approach to state-of-the-art first-order adaptive stochastic methods as well as other quasi-Newton methods. 1 Introduction Deep learning problems often involve training deep neural networks (DNN) by minimizing an empirical risk of estimation, given by \underset{\Theta\in\mathbb{R}^{n}}{\text{minimize}}\ f(\Theta)=\frac{1}{N}\sum_{i=1}^{N}f_{i}(x_{i},y_{i};\Theta) (1) where \Theta is the vector of weights and each f_{i} is a scalar-valued loss function that depends on a vector of data inputs, x_{i}\in\mathbb{R}^{n_{1}} , and outputs, y_{i}\in\mathbb{R}^{n_{2}} . Here, N corresponds to the cardinality of the data set \mathcal{D}=\{x_{i},y_{i}\} . In this paper, we assume that f is continuously differentiable. Gradient and adaptive gradient methods are the most widely used methods for solving ( 1 ). In particular, stochastic gradient descent (SGD), despite its simplicity, performs well over a wide range of applications. However, in a sparse training data setting, SGD performs poorly due to limited training speed ( Luo et al., 2019 ) . To address this problem, adaptive methods such as AdaGrad ( Duchi et al., 2011 ) , AdaDelta ( Zeiler, 2012 ) , RMSProp ( Hinton et al., 2012 ) and Adam ( Kingma & Ba, 2014 ) have been proposed. These methods take the root mean square of the past gradients to influence the current step. In contrast, Newton’s method has the potential to exploit curvature information from the second-order derivative (Hessian) matrix (see e.g., Gould et al. (2000) ). Generally, the iterates are defined by \Theta_{k+1}=\Theta_{k}-\alpha_{k}\nabla^{2}f(\Theta_{k})^{-1}\nabla f(\Theta_{k}) , where \alpha_{k}>0 is a steplength defined by a linesearch criterion ( Nocedal & Wright, 2006 ) . In a DNN setting, the number of parameters ( n ) can be of the order of millions. Thus, full Hessians are rarely ever computed. Instead, Hessian-vector products and Hessian-free methods are used (see e.g., Martens et al. (2010) , Ranganath et al. (2021) ) which reduce the cost of storing the Hessian and inverting it. Quasi-Newton methods compute Hessian approximations, \mathbf{B}_{k}\approx\nabla^{2}f(\Theta_{k}) , that satisfy the secant condition given by \mathbf{y}_{k-1}=\mathbf{B}_{k}\mathbf{s}_{k-1} , where \mathbf{s}_{k-1}=\Theta_{k}-\Theta_{k-1}\quad\text{and}\quad\mathbf{y}_{k-1}=\nabla f(\Theta_{k})-\nabla f(\Theta_{k-1}). The most commonly used quasi-Newton method, including in the realm of deep learning, is the limited-memory BFGS update, or L-BFGS (see e.g., Liu & Nocedal (1989) ), where the Hessian approximation is given by \mathbf{B}_{k}=\mathbf{B}_{k-1}+\frac{\mathbf{y}_{k-1}\mathbf{y}_{k-1}^{\top}}{\mathbf{y}_{k-1}^{\top}\mathbf{s}_{k-1}}-\frac{\mathbf{B}_{k-1}\mathbf{s}_{k-1}\mathbf{s}_{k-1}\mathbf{B}_{k-1}^{\top}}{\mathbf{s}_{k-1}^{\top}\mathbf{B}_{k-1}\mathbf{s}_{k-1}}. (2) One advantage of using an L-BFGS update is that the Hessian approximation can be guaranteed to be positive definite. This is highly suitable in line-search settings because the update \mathbf{s}_{k} is guaranteed to be a descent direction. This means there is some step length along this direction that results in a decrease in the objective function (see Nocedal & Wright (2006) , Algorithm 6.1). Because the L-BFGS update is positive definite, it does not readily detect directions of negative curvature for avoiding saddle points. In contrast, the Symmetric Rank-One (SR1) quasi-Newton update is not guarateed to be positive definite and can result in ascent directions for line-search methods. However, in trust-region settings where indefinite Hessian approximations are an advantage because they can capture directions of negative curvature, the limited-memory SR1 (L-SR1) has been shown to outperform L-BFGS in DNNs for classification (see Erway et al. (2020) ). We discuss this in more detail in Section 2 but in the context of adaptive regularization using cubics (see e.g., Nesterov & Polyak (2006) ). Contributions. The main contributions of this paper are as follows: (1) The use of the L-SR1 update to model potentially indefinite Hessians of the non-convex loss function; (2) The use of adaptive regularization using cubics (ARCs) approach as an alternative to line-search and trust-region optimization methods; (3) The use of a shape-changing norm to define the cubic regularization term, which allows us to compute the closed form solution to the cubic subproblem in the ARCs approach; (4) Convergence proof of the proposed ARCs approach with L-SR1 Hessian approximations. To the knowledge of the authors, this is the first time a quasi-Newton approach has been used in an adaptive regularized cubics setting. 2 Proposed approach In this section, we describe our proposed approach by first discussing the L-SR1 update. Limited-memory symmetric rank-one updates. Unlike the BFGS update ( 2 ), which is a rank-two update, the SR1 update is a rank-one update, which is given by \mathbf{B}_{k+1}=\mathbf{B}_{k}+\frac{(\mathbf{y}_{k}-\mathbf{B}_{k}\mathbf{s}_{k})(\mathbf{y}_{k}-\mathbf{B}_{k}\mathbf{s}_{k})^{\top}}{\mathbf{s}_{k}^{\top}(\mathbf{y}_{k}-\mathbf{B}_{k}\mathbf{s}_{k})} (3) (see Khalfan et al. (1993) ). As previously mentioned, \mathbf{B}_{k+1} in ( 3 ) is not guaranteed to be definite. However, it can be shown that the SR1 matrices can converge to the true Hessian (see Conn et al. (1991) for details). We note that the pair (\mathbf{s}_{k},\mathbf{y}_{k}) is accepted only when |\mathbf{s}_{k}^{\top}(\mathbf{y}_{k}-\mathbf{B}_{k}\mathbf{s}_{k})|>\varepsilon\|\mathbf{s}_{k}\|_{2}\|\mathbf{y}_{k}-\mathbf{B}_{k}\mathbf{s}_{k}\|_{2}, (4) for some constant \varepsilon>0 (see Nocedal & Wright (2006) , Sec. 6.2, for details). The SR1 update can be defined recursively as \mathbf{B}_{k+1}=\mathbf{B}_{0}+\sum_{j=0}^{k}\frac{(\mathbf{y}_{j}-\mathbf{B}_{j}\mathbf{s}_{j})(\mathbf{y}_{j}-\mathbf{B}_{j}\mathbf{s}_{j})^{\top}}{\mathbf{s}_{j}^{\top}(\mathbf{y}_{j}-\mathbf{B}_{j}\mathbf{s}_{j})}. (5) In limited-memory settings, only the last m\ll n pairs of (\mathbf{s}_{j},\mathbf{y}_{j}) are stored and used. For ease of presentation, here we choose k<m . We define \mathbf{S}_{k}=[\ \mathbf{s}_{0}\ \ \mathbf{s}_{1}\ \ \cdots\ \ \mathbf{s}_{k-1}\ ]\quad\text{and}\quad\mathbf{Y}_{k}=[\ \mathbf{y}_{0}\ \ \mathbf{y}_{1}\ \ \cdots\ \ \mathbf{y}_{k-1}\ ]. Then \mathbf{B}_{k} admits a compact representation of the form \mathbf{B}_{k}\ =\ \mathbf{B}_{0}+\begin{bmatrix}\\ \mathbf{\Psi}_{k}\\ \phantom{t}\end{bmatrix}\hskip-8.5359pt\begin{array}[]{c}\left[\ \mathbf{M}_{k}^{\phantom{h}}\right]\\ \\ \\ \end{array}\hskip-8.5359pt\begin{array}[]{c}\left[\ \quad\mathbf{\Psi}_{k}^{\top}\quad\ \right]\\ \\ \\ \end{array}, (6) where \mathbf{\Psi}_{k}=\mathbf{Y}_{k}-\mathbf{B}_{0}\mathbf{S}_{k} and \mathbf{M}_{k}=(\mathbf{D}_{k}\!+\!\mathbf{L}_{k}\!+\!\mathbf{L}_{k}^{\top}\!-\!\mathbf{S}_{k}^{\top}\!\mathbf{B}_{0}\mathbf{S}_{k})^{-1}\!, where \mathbf{L}_{k} is the strictly lower triangular part, \mathbf{V}_{k} is the strictly upper triangular part, and \mathbf{D}_{k} is the diagonal part of \mathbf{S}_{k}^{\top}\mathbf{Y}_{k}=\mathbf{L}_{k}+\mathbf{D}_{k}+\mathbf{V}_{k} (see Byrd et al. (1994) for further details). Because of the compact representation of \mathbf{B}_{k} , its partial eigendecomposition can be computed (see Erway & Marcia (2015) ). In particular, if we compute the QR decomposition of \mathbf{\Psi}_{k}=\mathbf{QR} and the eigendecomposition \mathbf{RMR}^{\top}=\mathbf{P}\hat{\mathbf{\Lambda}}_{k}\mathbf{P}^{\top} , then we can write \mathbf{B}_{k}=\mathbf{B}_{0}+\mathbf{U}_{\parallel}\hat{\mathbf{\Lambda}}_{k}\mathbf{U}_{\parallel}^{\top}, where \mathbf{U}_{\parallel}=\mathbf{QP}\in\mathbb{R}^{n\times k} has orthonormal columns and \hat{\mathbf{\Lambda}}_{k}\in\mathbb{R}^{k\times k} is a diagonal matrix. If \mathbf{B}_{0}=\delta_{k}\mathbf{I} (see e.g., Lemma 2.4 in Erway et al. (2020) ), where 0<\delta_{k}<\delta_{\max} is some scalar and \mathbf{I} is the identity matrix, then we obtain the eigendecomposition \mathbf{B}_{k}=\mathbf{U}_{k}\mathbf{\Lambda}_{k}\mathbf{U}_{k}^{\top}=\bigg[\ \mathbf{U}_{\parallel}\ \ \ \mathbf{U}_{\perp}\bigg]\begin{bmatrix}\hat{\mathbf{\Lambda}}_{k}+\delta_{k}\mathbf{I}&0\\ 0&\delta_{k}\mathbf{I}\end{bmatrix}\begin{bmatrix}\ \mathbf{U}_{\parallel}^{\top}\ \\[5.69046pt] \mathbf{U}_{\perp}^{\top}\end{bmatrix} (7) where \mathbf{U}_{k}=[\ \mathbf{U}_{\parallel}\ \ \mathbf{U}_{\perp}\ ] is an orthogonal matrix and \mathbf{U}_{\perp}\in\mathbb{R}^{n\times(n-k)} is a matrix whose columns form an orthonormal basis orthogonal to the range space of \mathbf{U}_{\parallel} . Here, (\mathbf{\Lambda}_{k})_{i}=\begin{cases}\delta_{k}+\hat{\lambda}_{i}&\text{ if $i\leq k$}\\