SGD with low-dimensional gradients with applications to private and distributed learning

Shiva Prasad KasiviswanathanUAI 2021 · OpenReview

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:

  1. Communication Costs: In distributed training, transmitting $d$-dimensional gradients between nodes consumes excessive bandwidth, often becoming the primary bottleneck in scaling training across clusters.
  2. 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:

  1. Low-Dimensional Step: Perform a gradient update in the $m$-dimensional projected space.
  2. Projected Constraint: Map the update onto a compressed version of the constraint set $\mathcal{C}$.
  3. 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.

Test accuracy of COMPSGD vs. standard SGD across MNIST, Reuters, and IMDB datasets.

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: COMPSGD achieves 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

Abstract

In this paper, we consider constrained optimization problems subject to a convex set C Stochastic gradient descent (SGD) is a simple and popular stochastic optimization algorithm that has been the workhorse of machine learning for many years. We show a new and surprising fact about SGD, in that depending on the constraint set C, one can operate SGD with much lower-dimensional stochastic gradients without affecting its performance. In particular, we design an optimization algorithm that operates with the lower-dimensional (compressed) stochastic gradients, and establish that with the right set of parameters it has the exact same dimension-free convergence guarantees as that of regular SGD for popular convex and nonconvex optimization settings. We also present two applications of these bounds, one for improving the empirical risk minimization bounds in differentially private nonconvex optimization, and other for reducing communication costs with distributed SGD. Additionally, we also show that this connection between constraint set structure and gradient compression also extends beyond SGD to the conditional gradient (Frank-Wolfe) method. The geometry of the constraint set, captured by its Gaussian width, plays an important role in all our results.
BibTeX
@inproceedings{kasiviswanathan2021sgd,
  author = {Shiva Prasad Kasiviswanathan},
  title = {{SGD with low-dimensional gradients with applications to private and distributed learning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=Oq3RTsCc1R},
}
Figure