Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

Introduction

Stochastic Convex Optimization (SCO) serves as the backbone of modern machine learning, aiming to minimize a "population loss" based on a finite set of samples. When these samples contain sensitive information, Differential Privacy (DP) is applied to ensure the output doesn't leak individual data points.

While DP-SCO is well-understood for $\ell_2$ (Euclidean) geometry, many important problems—like sparse regression (LASSO) or optimization over the probability simplex—naturally live in $\ell_1$ geometry. In high-dimensional spaces, the "cost of privacy" in $\ell_2$ scales poorly with the dimension $d$. Prior work in $\ell_1$ geometry either focused only on empirical loss (rather than the more important population loss) or provided suboptimal rates that didn't fully exploit the geometry's potential for high-dimensional efficiency.

This paper closes that gap by establishing the fundamental limits and optimal rates for differentially private stochastic convex optimization (DP-SCO) within $\ell_1$ geometry. The authors introduce two novel algorithms that achieve matching upper and lower bounds, proving that privacy can be "essentially free" even in high-dimensional $\ell_1$ settings.

Methodology

The authors tackle two distinct optimization scenarios, introducing tailored algorithms for each:

1. Non-Smooth Functions

Standard DP techniques often add Gaussian noise to the output. However, in $\ell_1$ geometry, the $\ell_1$-norm of Gaussian noise grows linearly with $\sqrt{d}$, which quickly overwhelms the signal.

  • Iterative Localization: Instead of one-shot noise addition, the authors use a multi-phase approach. In each phase, they solve a regularized version of the problem to shrink the search domain.
  • Private Mirror Descent: Rather than simple output perturbation, they use a private version of mirror descent within each phase. This allows them to reduce the distance to the minimizer by a multiplicative factor in every step, eventually reaching the optimal rate.

2. Smooth Functions

For smooth functions, the authors adapt the Frank-Wolfe (Conditional Gradient) algorithm. Frank-Wolfe is attractive for $\ell_1$ because its updates are often sparse and only require a linear optimization oracle.

  • Dyadic Variance Reduction: To achieve optimal rates, the algorithm needs to reuse samples to reduce gradient variance. Doing this privately is hard because sample reuse compounds privacy loss. The authors solve this using a binary tree (dyadic) structure to allocate samples.
  • Sample Allocation: Vertices closer to the root of the tree are assigned larger batches of samples because they are reused in more steps of the algorithm. This careful accounting, combined with "amplification by shuffling," allows the algorithm to maintain a tight privacy budget while achieving high accuracy.
The dyadic tree structure used in the Private Variance Reduced Frank-Wolfe algorithm, illustrating gradient estimate updates for efficient sample reuse.

Key Insights

  • Privacy is "Free" in High Dimensions: For smooth functions in $\ell_1$ geometry, the privacy cost depends only logarithmically on the dimension $d$. This means you can train models on massive feature sets with almost no loss in accuracy compared to non-private training, provided the dataset is sufficiently large.
  • Smoothness Matters: In $\ell_2$ geometry, smoothness doesn't typically improve the optimal DP-SCO rate. In $\ell_1$ geometry, it does. The authors show that smoothness allows for a significantly better rate: $(\frac{\log d}{n\epsilon})^{2/3}$ vs $\frac{\sqrt{d}}{n\epsilon}$.
  • The Failure of Contractivity: A common trick to prove DP-SCO bounds is showing that optimization steps are "contractive" (they bring points closer together). The authors demonstrate that mirror descent—the standard tool for $\ell_1$ optimization—is not necessarily contractive, necessitating their new iterative localization analysis.

Key Results

The paper provides tight bounds for the excess population loss (how much worse the private solution is compared to the true minimum):

  • Non-Smooth Rate: $\tilde{O}\left(\sqrt{\frac{\log d}{n}} + \frac{\sqrt{d}}{n\epsilon}\right)$. This matches the lower bound and improves the gradient complexity from $O(n^2)$ in prior $\ell_2$ work to $O(n^{3/2})$.
  • Smooth Rate: $\tilde{O}\left(\sqrt{\frac{\log d}{n}} + \left(\frac{\log d}{n\epsilon}\right)^{2/3}\right)$. This rate is achieved in linear time ($O(n)$) and shows that the dependence on $d$ is only logarithmic.
  • Optimality: The authors provide matching lower bounds, proving that no $(\epsilon, \delta)$-DP algorithm can do better than the rates they achieved.

Limitations and Future Work

While establishing fundamental limits, the paper notes a few areas for future exploration:

  • High-Dimensional Requirement for Smooth Lower Bounds: The lower bound for smooth functions requires the dimension $d$ to be relatively large ($d \ge \tilde{O}((n\epsilon)^{2/3})$). The behavior in lower-dimensional regimes could be explored further.
  • Gradient Complexity: While $O(n^{3/2})$ for the non-smooth case is an improvement, it is still not linear time. Finding a linear-time optimal algorithm for non-smooth $\ell_1$ DP-SCO remains an open challenge.
  • General $\ell_p$ Geometries: The paper touches on extensions to $1 < p < 2$, but a comprehensive treatment of all $\ell_p$ geometries could provide a more unified theory of private optimization.

Summary updated

Abstract

Stochastic convex optimization over an $\ell_1$-bounded domain is ubiquitous in machine learning applications such as LASSO but remains poorly understood when learning with differential privacy. We show that, up to logarithmic factors the optimal excess population loss of any $(\varepsilon,\delta)$-differentially private optimizer is $\sqrt{\log(d)/n} + \sqrt{d}/\varepsilon n.$ The upper bound is based on a new algorithm that combines the iterative localization approach of~\citet{FeldmanKoTa20} with a new analysis of private regularized mirror descent. It applies to $\ell_p$ bounded domains for $p\in [1,2]$ and queries at most $n^{3/2}$ gradients improving over the best previously known algorithm for the $\ell_2$ case which needs $n^2$ gradients. Further, we show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $\sqrt{\log(d)/n} + (\log(d)/\varepsilon n)^{2/3}.$ This bound is achieved by a new variance-reduced version of the Frank-Wolfe algorithm that requires just a single pass over the data. We also show that the lower bound in this case is the minimum of the two rates mentioned above.
BibTeX
@inproceedings{asi2021private,
  author = {Hilal Asi and Vitaly Feldman and Tomer Koren and Kunal Talwar},
  title = {{Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=irvI5Iy8mL},
}
Figure