# Randomized Subspace Nesterov Accelerated Gradient

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 41 references that are in the map.
- First posted on arXiv 1 May 2026.

## Builds on (most cited first, 20 of 20)

- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization](https://mlsanity.com/paper/2002.11364/) (2020)
- [Accelerated, Parallel and Proximal Coordinate Descent](https://mlsanity.com/paper/1312.5799/) (2013)
- [Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling](https://mlsanity.com/paper/1512.09103/) (2015)
- [On the Complexity Analysis of Randomized Block-Coordinate Descent Methods](https://mlsanity.com/paper/1305.4723/) (2013)
- [Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization](https://mlsanity.com/paper/2102.07245/) (2021)
- [Zeroth order optimization with orthogonal random directions](https://mlsanity.com/paper/2107.03941/) (2021)
- [GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity](https://mlsanity.com/paper/2210.16402/) (2022)
- [A stochastic subspace approach to gradient-free optimization in high dimensions](https://mlsanity.com/paper/2003.02684/) (2020)
- [Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity](https://mlsanity.com/paper/1412.8060/) (2014)
- [Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches](https://mlsanity.com/paper/1809.09354/) (2018)
- [Scalable Subspace Methods for Derivative-Free Nonlinear Least-Squares Optimization](https://mlsanity.com/paper/2102.12016/) (2021)
- [Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques](https://mlsanity.com/paper/2106.03524/) (2021)
- [Direct search based on probabilistic descent in reduced spaces](https://mlsanity.com/paper/2204.01275/) (2022)
- [Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization](https://mlsanity.com/paper/2305.12568/) (2023)
- [Problem-dependent convergence bounds for randomized linear gradient compression](https://mlsanity.com/paper/2411.12898/) (2024)
- [Randomized subspace gradient method for constrained optimization](https://mlsanity.com/paper/2307.03335/) (2023)
- [Expected decrease for derivative-free algorithms using random subspaces](https://mlsanity.com/paper/2308.04734/) (2023)
- [Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2601.20399/) (2026)

## Abstract (arXiv)

Randomized-subspace methods reduce the cost of first-order optimization by using only low-dimensional projected-gradient information, a feature that is attractive in forward-mode automatic differentiation and communication-limited settings. While Nesterov acceleration is well understood for full-gradient and coordinate-based methods, obtaining accelerated methods for general subspace sketches that use only projected-gradient information and can improve over full-dimensional Nesterov acceleration in oracle complexity is technically nontrivial. We develop randomized-subspace Nesterov accelerated gradient methods for smooth convex and smooth strongly convex optimization under matrix smoothness and generic sketch moment assumptions. The key technical ingredient is a three-sequence formulation tailored to matrix smoothness, which recovers the corresponding classical Nesterov methods in the full-dimensional case. The resulting theory establishes accelerated oracle-complexity guarantees and makes explicit how matrix smoothness and the sketch distribution enter the complexity. It also provides a unified basis for comparing sketch families and identifying when randomized-subspace acceleration improves over full-dimensional Nesterov acceleration in oracle complexity.