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

2025/06/07 by X. L. Luo, Luo, Xinyu, Site Bai +9
Computer Science · #Stochastic Gradient Optimization Techniques #Advanced Neural Network Applications #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.2506.06606

Abstract

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

Citations

• Non-Euclidean High-Order Smooth Convex Optimization
• Convex optimization with p-norm oracles
• Faster Acceleration for Steepest Descent
• Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity
• A New Perspective on Shampoo's Preconditioner
• The Road Less Scheduled
• Lion Secretly Solves Constrained Optimization: As Lyapunov Predicts
• A Guide Through the Zoo of Biased SGD
• Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training
• Symbolic Discovery of Optimization Algorithms
• How Does Adaptive Optimization Impact Local Neural Network Geometry?
• Parameter-free Mirror Descent
• Gradient Descent on Neural Networks Typically Occurs at the Edge of\n Stability
• Complementary Composite Minimization, Small Gradients in General Norms, and Applications
• Federated Composite Optimization
• The Geometry of Sign Gradient Descent
• Lower Bounds for Non-Convex Stochastic Optimization
• On the Convergence of FedAvg on Non-IID Data
• Hessian based analysis of SGD for Deep Nets: Dynamics and Generalization
• Adaptive norms for deep learning with regularized Newton methods
• An Investigation into Neural Net Optimization via Hessian Eigenvalue\n Density
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient\n Descent on Non-Convex Functions
• How to Escape Saddle Points Efficiently
• Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
• Deep Residual Learning for Image Recognition
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions
• Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
• On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected\n Graphs, and its Multicommodity Generalizations
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• Smooth minimization of non-smooth functions
• A Stochastic Approximation Method

Related

• Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates
• Generalized Gradient Norm Clipping & Non-Euclidean (L₀,L₁)-Smoothness
• An Optimistic Acceleration of AMSGrad for Nonconvex Optimization
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Drop-Muon: Update Less, Converge Faster