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.
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