# Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓp-Smooth Nonconvex Optimization

arXiv: https://arxiv.org/abs/2506.06606 · HTML: https://mlsanity.com/paper/2506.06606/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 58 references that are in the map.
- First posted on arXiv 7 Jun 2025.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Symbolic Discovery of Optimization Algorithms](https://mlsanity.com/paper/2302.06675/) (2023)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [An Investigation into Neural Net Optimization via Hessian Eigenvalue Density](https://mlsanity.com/paper/1901.10159/) (2019)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training](https://mlsanity.com/paper/2305.14342/) (2023)
- [The Road Less Scheduled](https://mlsanity.com/paper/2405.15682/) (2024)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [A New Perspective on Shampoo's Preconditioner](https://mlsanity.com/paper/2406.17748/) (2024)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [Lion Secretly Solves Constrained Optimization: As Lyapunov Predicts](https://mlsanity.com/paper/2310.05898/) (2023)
- [Federated Composite Optimization](https://mlsanity.com/paper/2011.08474/) (2020)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [The Geometry of Sign Gradient Descent](https://mlsanity.com/paper/2002.08056/) (2020)
- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Hessian based analysis of SGD for Deep Nets: Dynamics and Generalization](https://mlsanity.com/paper/1907.10732/) (2019)
- [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017)
- [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013)
- [How Does Adaptive Optimization Impact Local Neural Network Geometry?](https://mlsanity.com/paper/2211.02254/) (2022)
- [An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations](https://mlsanity.com/paper/1304.2338/) (2013)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Adaptive norms for deep learning with regularized Newton methods](https://mlsanity.com/paper/1905.09201/) (2019)
- [Convex optimization with p-norm oracles](https://mlsanity.com/paper/2410.24158/) (2024)
- [Tight Lower Bounds under Asymmetric High-Order H"older Smoothness and Uniform Convexity](https://mlsanity.com/paper/2409.10773/) (2024)

## Built on by (most cited first, 3 of 3)

- [PowerStep: Memory-Efficient Adaptive Optimization via ℓp-Norm Steepest Descent](https://mlsanity.com/paper/2605.10335/) (2026)
- [Can Entry-Wise Clipping Give Spectral Control of Stochastic Gradients?](https://mlsanity.com/paper/2605.27733/) (2026)
- [Beyond ℓ2-norm and ℓ_∞-norm: A Curvature-Inspired ℓp-Norm Scheme for Deep Neural Networks](https://mlsanity.com/paper/2606.02078/) (2026)

## Abstract (arXiv)

While popular optimization methods such as SGD, AdamW, and Lion depend on steepest descent updates in either ℓ2 or ℓ_∞ 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 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 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 .