Introduction
Stochastic Gradient Descent (SGD) is the foundational algorithm for training modern machine learning models. However, its efficiency is often hampered in high-dimensional settings where the parameter space $d$ is vast. This dimensionality creates significant overhead in distributed systems due to communication bottlenecks and complicates Differentially Private (DP) learning, where noise scales with the ambient dimension. This paper introduces COMPSGD, a method that leverages the geometric structure of constraint sets to perform "lossless" gradient compression.
Problem Formulation
In high-dimensional optimization, two primary challenges arise:
- Communication Costs: In distributed training, transmitting $d$-dimensional gradients between nodes consumes excessive bandwidth, often becoming the primary bottleneck in scaling training across clusters.
- Privacy Constraints: In Differentially Private Empirical Risk Minimization (DP-ERM), the noise added to gradients to ensure privacy typically scales with $\sqrt{d}$. This necessitates exponentially larger datasets to maintain utility as dimensionality increases.
The authors address a fundamental question: Can we compress gradients to a lower dimension without losing the standard, dimension-free convergence guarantees of SGD?
The COMPSGD Algorithm
The core of the proposed approach is the Compressed Stochastic First-order Oracle (CSFO). Instead of the full $d$-dimensional gradient, the algorithm utilizes a compressed gradient $g_t = \Phi_t \nabla f(x_t, \xi_t)$, where $\Phi_t \in \mathbb{R}^{m \times d}$ is a random projection matrix (e.g., a sparse Johnson-Lindenstrauss matrix).
The COMPSGD update involves three critical steps:
- Low-Dimensional Step: Perform a gradient update in the $m$-dimensional projected space.
- Projected Constraint: Map the update onto a compressed version of the constraint set $\mathcal{C}$.
- Lifting: Reconstruct the $d$-dimensional iterate by solving a convex optimization problem based on the Minkowski functional of the constraint set. For common constraints like $\ell_1$-sparsity, this lifting step is a standard, easily solvable basis-pursuit linear program.
Geometric Insights
The feasibility of this compression is governed by the Gaussian width $\omega(\mathcal{C})$ of the constraint set. The authors prove that if the projection dimension $m$ is proportional to $\omega(\mathcal{C})^2$, the compression is essentially "lossless"—the convergence rate remains dimension-free. For $\ell_1$-balls, where $\omega(\mathcal{C}) = O(\sqrt{\log d})$, the gradient can be compressed from $d$ dimensions down to just $O(\log d)$ dimensions without slowing down convergence.
Empirical Evaluation
The authors validated COMPSGD on standard benchmarks including MNIST, Reuters, and IMDB datasets using Multi-Layer Perceptrons (MLPs) and logistic regression models.
As shown in the figure above, COMPSGD tracks the performance of standard SGD almost perfectly across all benchmarks. In these experiments, gradients were compressed by factors of 10x to 19x. Furthermore, the computational overhead of the "lifting" step was found to be minimal, adding only about 6.3% to the per-epoch training time on the IMDB dataset, a negligible cost for the massive reduction in communication volume.
Key Results and Implications
- Theoretical Convergence:
COMPSGDachieves standard dimension-free convergence rates across convex, strongly convex, and smooth non-convex settings. - Privacy Gains: For non-convex DP-ERM, the required sample size to reach a stationary point drops from scaling with $\sqrt{d}$ to scaling with the Gaussian width $\omega(\mathcal{C})$. For $\ell_1$-constrained problems, this is a massive improvement from $\sqrt{d}$ to $\sqrt{\log d}$.
- Synergy: This dimensionality reduction is orthogonal to existing quantization schemes. Random projection can be applied first to shrink the vector, followed by quantization for multiplicative communication savings.
Conclusion
COMPSGD provides a theoretically grounded and empirically robust framework for high-dimensional optimization. By exploiting the intrinsic geometry of constraints, it enables massive communication savings and improved privacy guarantees without the variance inflation typical of standard compression schemes. Future work may extend these principles to second-order methods and explore interactions with biased gradient encoding schemes.
Summary updated