Sparse Updates Generalize Better Than Optimization: Stability Analysis for Randomized Subspace Descent

Large-scale learning increasingly relies on updating only a coordinate, a block, or a low-dimensional subspace per iteration to reduce memory and communication costs, yet the statistical consequence of such reduced update coverage, beyond the well-understood optimization slowdown, remains open. Available stability analyses are restricted to coordinate-level projectors whose orthogonality drives the argument, deterministic-output assumptions incompatible with randomized updates, or uniform step sizes that ignore curvature-adaptive blockwise schedules; none explains how general subspace coverage controls population risk. We analyze this question through randomized subspace descent (RSD), a framework that recovers GD, RCD, BCD, and isotropic SSD as special cases: under joint isotropy the expected projection energy reduces to a single coverage parameter~$\alpha$, enabling unified stability analysis without coordinate-level structure. The convex excess risk scales as $O(\alpha^{-1/4}N^{-1/2})$, improving to $O((N\sqrt{\alpha})^{-1})$ under low noise, substantially gentler than the $O(1/\alpha)$ optimization slowdown, while in the nonconvex Polyak--{\L}ojasiewicz setting $\alpha$ lengthens the early-stopping horizon without entering the excess-risk bound as an explicit penalty. The analysis extends to the canonical blockwise step size~$1/L_i$ through a curvature-matched Lyapunov geometry that exposes a balance condition for exact block updates, and to nonconvex objectives by decoupling gradient and curvature moments via H\"older's inequality so that stability is controlled without an almost-sure curvature lower bound. Experiments on convex and nonconvex benchmarks confirm the predicted trade-off.