Stacey : Promoting Stochastic Steepest Descent via Accelerated ℓ p \ell_{p} -Smooth Nonconvex Optimization
Xinyu Luo, Cedar Site Bai, Bolian Li, Petros Drineas, Ruqi Zhang, Brian Bullins · 2025
Read Stacey : Promoting Stochastic Steepest Descent via Accelerated ℓ p \ell_{p} -Smooth Nonconvex Optimization by Xinyu Luo, Cedar Site Bai, Bolian Li, Petros Drineas, Ruqi Zhang, Brian Bullins (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-2506-06606.txt.
Introduction
Xinyu Luo and co-authors present a training optimiser built for the non-Euclidean geometry of deep networks, in a 2025 paper. Popular methods such as SGD, AdamW, and Lion all follow steepest descent measured in one of two standard norms. Real network loss surfaces, though, bend in ways those norms miss. Their method, Stacey, performs accelerated steepest descent under a tunable family of norms between the two extremes.
The algorithm runs interpolated primal-dual sequences of iterates to keep its speed in that geometry. Theory backs the design with fresh guarantees for smooth but non-convex problems. In practice it beat the popular rivals on image classification and on language model pretraining, converging faster and landing at higher final accuracy. Trying several values of the norm parameter across models and data sets showed the choice matters. The authors argue non-Euclidean updates should be a default tool, not an afterthought.
Catalog record
| CREATOR | Xinyu Luo, Cedar Site Bai, Bolian Li, Petros Drineas, Ruqi Zhang, Brian Bullins |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06606
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stacey : Promoting Stochastic Steepest Descent via Accelerated ℓ p \ell_{p} -Smooth Nonconvex Optimization Xinyu Luo, Cedar Site Bai, Bolian Li, Petros Drineas, Ruqi Zhang, Brian Bullins Abstract While popular optimization methods such as SGD, AdamW, and Lion depend on steepest descent updates in either ℓ 2 \ell_{2} or ℓ ∞ \ell_{\infty} norms, there remains a critical gap in handling the non-Euclidean structure observed in modern deep networks training. In this work, we address this need by introducing a new accelerated ℓ p \ell_{p} steepest descent algorithm, called Stacey , which uses interpolated primal-dual iterate sequences to effectively navigate non-Euclidean smooth optimization tasks. In addition to providing novel theoretical guarantees for the foundations of our algorithm, we empirically compare our approach against these popular methods on tasks including image classification and language model (LLM) pretraining, demonstrating both faster convergence and higher final accuracy. We further evaluate different values of p p across various models and datasets, underscoring the importance and efficiency of non-Euclidean approaches over standard Euclidean methods. Code can be found at https://github.com/xinyuluo8561/Stacey . † † affiliationnotice: Equal contribution 1 Introduction Stochastic first-order methods have proven essential for efficiently training modern deep learning models. Beyond the basic stochastic gradient descent (SGD) algorithm ( Robbins & Monro 1951 ) and its momentum-based variants ( Nesterov 1983 ; Polyak 1964 ) , a variety of adaptive methods have been developed, such as AdaGrad ( Duchi et al. 2011a ) , Adam ( Kingma & Ba 2015 ) , and AdamW ( Loshchilov & Hutter 2019 ) , which incorporate second-moment gradient information to provide per-coordinate scaling. Meanwhile, more recent methods like signSGD ( Bernstein et al. 2018 ) and Lion ( Chen et al. 2023 ) focus on using the sign of the (stochastic) gradient. Although these algorithms have shown impressive empirical performance (sometimes exceeding that of standard adaptive methods), their theoretical analyses typically rely on Euclidean (i.e., \ell_{2} ) or \ell_{\infty} -based assumptions. Specifically, crucial to guarantees of finding \epsilon -approximate stationary points ( Carmon et al. 2017 ; Ghadimi & Lan 2013 ; Jin et al. 2017 ) are two related choices: (i) the norm used to define stationarity, and (ii) the corresponding notion of smoothness. Classical analyses in deep learning often adopt Euclidean smoothness ( Ghadimi & Lan 2013 ) , while signSGD relies on \ell_{\infty} -based assumptions ( Bernstein et al. 2018 ; Balles et al. 2020 ) . Yet, there is mounting evidence—both theoretical and empirical—suggesting that a more flexible \ell_{p} perspective can capture the geometric structure of complex deep network objectives far better than either p=2 or p=\infty alone ( Adolphs et al. 2019 ; Cohen et al. 2021 ; Ghorbani et al. 2019 ; Jiang et al. 2024 ; Li et al. 2020a ; Papyan 2018 ) . For instance, depending on the shape of the loss surface and the distribution of gradients across coordinates, certain \ell_{p} norms with 2<p<\infty may lead to faster descent or improved generalization. This leaves open a significant gap: How can we develop and analyze optimizers in alternative non-Euclidean regimes, namely those with general \ell_{p} norms where p\in(2,\infty) ? To address this question, we propose a novel approach that we term Stacey ( St ochastic St eepest Descent with Ac c e leration). Our development builds on insights from both \ell_{p} -steepest descent and non-Euclidean acceleration techniques ( Allen-Zhu & Orecchia 2017 ; Diakonikolas & Guzmán 2024 ; Nemirovskii & Nesterov 1985 ; Nesterov 2005 ) , combining primal-dual ( Diakonikolas & Orecchia 2019 ) iterates with an interpolation scheme designed specifically for \ell_{p} -based smoothness. While the notion of acceleration is well understood in the classical (Euclidean) setting ( Nesterov 1983 ) , extending it to arbitrary \ell_{p} norms introduces a fundamental trade-off: although we may attain improved geometry dependence (and thus potentially faster practical convergence in certain regimes), the theoretical “acceleration exponent” necessarily decreases from 2 toward 1 as p grows large ( Guzmán & Nemirovski 2015 ; Nemirovskii & Nesterov 1985 ) . Nonetheless, by situating Stacey within this continuum of non-Euclidean optimizers, we can reap meaningful benefits over purely Euclidean (e.g., SGD) and purely sign-based (e.g., signSGD) methods on modern, large-scale tasks. Our Contributions: • Accelerated \ell_{p} -based method. Drawing inspiration from primal-dual interpolation techniques in the convex setting ( Allen-Zhu & Orecchia 2017 ; Nesterov 2005 ; Diakonikolas & Guzmán 2024 ) , we design Stacey , an accelerated \ell_{p} descent algorithm specifically tailored to non-Euclidean smooth optimization (Section 4 ). • General \ell_{p} convergence guarantees for non-convex problems. We first establish stochastic \ell_{p} steepest descent guarantees \mathbb{E}\left[\|\nabla f(\hat{x})\|_{p^{*}}^{p^{*}}\right]\leq{\epsilon} at a rate of O(\epsilon^{-4}) , under standard variance-bounded and \ell_{p} -smoothness assumptions, where we let p^{*}:=\frac{p}{p-1} (Section 4.1 ). Our results strictly generalize previous guarantees for signSGD ( p=\infty ). • Practical performance on large-scale tasks. We compare Stacey against popular optimizers such as SGD, Adam, AdamW, and Lion on tasks ranging from image classification to pretraining large language models (Section 5 ). Our experiments show that Stacey can converge faster and achieve higher accuracy than these baselines, particularly when the geometry of the objective departs significantly from the Euclidean setting. • Flexible norm choices. We further evaluate different values of p\in(2,\infty) across various model architectures and datasets, illustrating the potential advantages of tailoring the choice of norm to the problem geometry. Taken together, our results highlight the importance of non-Euclidean perspectives for contemporary machine learning tasks, offering both theoretical insight and practical improvement over classical ( \ell_{2} -based) and sign-based ( \ell_{\infty} -based) optimizers. 2 Related Work Methods for non-Euclidean geometries. A significant line of research has studied sign-based methods, which can be viewed as (stochastic) steepest descent under the \ell_{\infty} norm. For instance, Bernstein et al. 2018 introduced signSGD and analyzed its convergence properties through an \ell_{2} majorization-based smoothness condition, 1 1 1 We provide a comparison of \ell_{2} majorization and \ell_{p} smoothness conditions in Appendix B . showing that in expectation, \|\nabla f(\hat{x})\|_{1} can be driven below a prescribed threshold. Similarly, Balles et al. 2020 investigated the geometric underpinnings of sign-based updates, highlighting how they relate to \ell_{\infty} steepest descent. Recent work on Lion ( Chen et al. 2023 ) and its generalization Lion- \mathcal{K} ( Chen et al. 2024 ) further underscores the empirical benefits of sign-driven coordinates in large-scale tasks. However, sign-based approaches ( p=\infty ) represent just one extreme of non-Euclidean geometry. The other well-studied example is the classical \ell_{2} -based regime (e.g., vanilla SGD) ( Ghadimi & Lan 2013 ; Robbins & Monro 1951 ) , where standard notions of Euclidean smoothness and approximate stationarity \|\nabla f(\hat{x})\|_{2}\leq\epsilon underpin core theoretical results. Interpolating between these extremes ( \ell_{2} and \ell_{\infty} ) by considering \ell_{p} norms for 2<p<\infty has remained comparatively underexplored in the stochastic, non-convex setting. One challenge is that, unlike in the Euclidean case, the coordinate-scaling in an \ell_{p} steepest-descent update is not merely a straightforward unbiased estimator of the full-batch direction, making a standard “SGD-style” analysis more involved. Methods for curvature-aware optimization. Another line of work exploits local geometry by incorporating second-order information, such as the Hessian or Fisher information matrix, and develops techniques for their efficient approximation. K-FAC ( Martens & Grosse 2015 ) approximates