Randomized Subspace Nesterov Accelerated Gradient

Randomized-subspace methods use only low-dimensional projected-gradient information, offering potential savings in directional-derivative queries and communication volume. Designing Nesterov-accelerated methods for general randomized subspaces that preserve this low-dimensional information structure while allowing improvements over full-gradient 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. A key technical ingredient is a three-sequence formulation tailored to matrix smoothness. The resulting theory establishes accelerated convergence guarantees and makes explicit how matrix smoothness and the sketch distribution jointly determine the complexity. In oracle complexity, the dimension factor $d$ of full-dimensional Nesterov acceleration is replaced by the sketch-dependent factor $r\sqrt{\omega \ell }$, where $r$ is the subspace dimension and $\omega$ and $\ell$ are sketch moment parameters, identifying regimes in which randomized-subspace acceleration improves over full-dimensional Nesterov acceleration. For standard sketch families, we derive explicit complexity factors that enable direct comparison across sketch distributions.