Private Stochastic Convex Optimization: Optimal Rates in 𝓁1 Geometry

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

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 Feldman et al. (2020) 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.

Introduction

In Stochastic Convex Optimization (SCO), the objective is to minimize a population loss—the average error over an entire distribution—using a finite set of $n$ samples. When incorporating Differential Privacy (DP), the challenge is to ensure the resulting model does not compromise individual data points. While DP-SCO is well-studied in $\ell_2$ (Euclidean) geometry, many high-dimensional sparse learning problems, such as LASSO or learning over probability simplexes, naturally reside in $\ell_1$ geometry.

In high-dimensional settings where the feature dimension $d$ greatly exceeds the sample size $n$, $\ell_1$ methods are significantly more efficient. However, standard DP techniques for $\ell_2$ often fail in $\ell_1$ because the noise required for privacy typically scales linearly with $d$, potentially overwhelming the signal. This research establishes the first optimal rates for DP-SCO in $\ell_1$ geometry, solving a long-standing open problem in the field.

Algorithmic Frameworks

The researchers introduced two novel algorithmic frameworks tailored to different loss function characteristics:

1. Iterative Localization for Non-Smooth Functions

For general convex functions, the authors adapt an "iterative localization" framework. The optimization is divided into logarithmic phases, where each phase solves a regularized version of the problem using a Noisy Mirror Descent algorithm. By carefully scaling noise and regularization, the solution localizes toward the true minimum without privacy noise explosion. This approach requires $O(n^{3/2})$ gradient queries, a significant improvement over the $O(n^2)$ queries required by previous state-of-the-art algorithms for the simpler $\ell_2$ case.

2. Dyadic Variance-Reduced Frank-Wolfe for Smooth Functions

For smooth functions, the authors developed a variance-reduced Frank-Wolfe algorithm. Frank-Wolfe is advantageous in $\ell_1$ settings because its updates are dimension-independent. To maintain privacy and efficiency, the algorithm utilizes a binary-tree (dyadic) structure for sample reuse. This allows for variance reduction—using historical gradients to refine new ones—while strictly controlling the privacy budget for each sample. This algorithm runs in linear time relative to $n$, making it highly practical for large-scale data.

Key Results and Theoretical Insights

The paper establishes minimax optimal rates, proving that no $(\varepsilon, \delta)$-DP algorithm can achieve better performance than the following:

  • Non-Smooth Functions: The optimal excess loss is $\tilde{O}\left(\sqrt{\frac{\log d}{n}} + \frac{\sqrt{d}}{\epsilon n}\right)$.
  • Smooth Functions: The optimal excess loss is $\tilde{O}\left(\sqrt{\frac{\log d}{n}} + \left( rac{\log d}{\epsilon n}\right)^{2/3}\right)$.

Insights on Smoothness and Dimension

A striking finding is that for smooth functions, the cost of privacy is remarkably low. When the privacy parameter $\epsilon$ is sufficiently large, the private algorithm performs nearly as well as the best non-private algorithm. Furthermore, while smoothness does not significantly impact rates in $\ell_2$ geometry, it is transformative in $\ell_1$: it allows the error to depend only logarithmically on the dimension ($\log d$), whereas non-smooth functions suffer a harsher $\sqrt{d}$ penalty.

Conclusion and Future Work

This work provides a definitive theoretical foundation for private optimization in $\ell_1$ geometry. While it establishes optimal rates for $\ell_p$ geometries where $p \in [1, 2]$, several avenues for future research remain. The benefits for smooth functions are most pronounced when $\epsilon \ge \Omega(n^{-1/4})$; for stricter privacy requirements, the rates for smooth and non-smooth functions converge. Future work may also explore extending these optimal rates to more complex constraint sets or non-convex objectives, as well as optimizing the constants for practical implementation in real-world sparse regression tasks.

Summary updated

BibTeX
@inproceedings{asi2021private,
  author = {Hilal Asi and Vitaly Feldman and Tomer Koren and Kunal Talwar},
  title = {{Private Stochastic Convex Optimization: Optimal Rates in 𝓁1 Geometry}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=irvI5Iy8mL},
}
Figure