Abstract
In this paper, we initiate a systematic investigation of differentially private algorithms for convex empirical risk minimization. Various instantiations of this problem have been studied before. We provide new algorithms and matching lower bounds for private ERM assuming only that each data point's contribution to the loss function is Lipschitz bounded and that the domain of optimization is bounded. We provide a separate set of algorithms and matching lower bounds for the setting in which the loss functions are known to also be strongly convex. Our algorithms run in polynomial time, and in some cases even match the optimal non-private running time (as measured by oracle complexity). We give separate algorithms (and lower bounds) for $(\epsilon,0)$- and $(\epsilon,\delta)$-differential privacy; perhaps surprisingly, the techniques used for designing optimal algorithms in the two cases are completely different. Our lower bounds apply even to very simple, smooth function families, such as linear and quadratic functions. This implies that algorithms from previous work can be used to obtain optimal error rates, under the additional assumption that the contributions of each data point to the loss function is smooth. We show that simple approaches to smoothing arbitrary loss functions (in order to apply previous techniques) do not yield optimal error rates. In particular, optimal algorithms were not previously known for problems such as training support vector machines and the high-dimensional median.
Introduction
Empirical Risk Minimization (ERM) is a cornerstone of machine learning, serving as the standard framework for finding model parameters that minimize a loss function over a dataset. However, standard ERM algorithms can inadvertently leak sensitive information. For instance, the parameters of a Support Vector Machine (SVM) are often defined by specific "support vectors"—individual data points from the training set—effectively publishing parts of the raw data.
Differential Privacy (DP) provides a rigorous mathematical framework to mitigate such leaks. While prior research addressed "smooth" (differentiable) loss functions, many practical applications involve "non-smooth" functions, such as the hinge loss in SVMs or absolute error in high-dimensional medians. Before the work of Bassily, Smith, and Thakurta, the fundamental limits of error for these non-smooth private models were unknown, and existing algorithms were often inefficient or yielded suboptimal accuracy.
Algorithmic Approaches
The authors develop two distinct methodologies tailored to the specific requirements of the privacy model:
1. Approximate Privacy: $(\epsilon, \delta)$-DP
For $(\epsilon, \delta)$-DP, the paper introduces a refined Noisy Stochastic Gradient Descent (SGD). The innovation lies in the use of "privacy amplification via sampling." By executing the algorithm for a large number of steps ($n^2$) and selecting a random data point at each iteration, the privacy cost per step is significantly reduced. This allows for more iterations and better convergence without exceeding the total privacy budget.
2. Pure Privacy: $(\epsilon, 0)$-DP
The approach for pure $(\epsilon, 0)$-DP shifts to the Exponential Mechanism, which samples a solution from a specific probability distribution. To overcome the computational difficulty of sampling from high-dimensional distributions, the authors implement an efficient grid-walk algorithm designed to sample from log-concave distributions over convex sets.
3. Localization for Strong Convexity
For functions that are "strongly convex"—those with a sharp, well-defined minimum—the authors employ a "localization" technique. This involves obtaining an initial coarse private estimate and then refining the search within a small neighborhood of that estimate. This strategy drastically reduces the final error rate.
Key Insights and Theoretical Bounds
A central contribution of this work is the demonstration that for non-smooth functions, the "excess risk" (the difference in performance between a private and a non-private model) can be improved by a factor of $\sqrt{n}$ over previous benchmarks.
The authors also demonstrate that simple "smoothing" techniques—approximating a non-smooth function with a smooth one—are fundamentally limited and cannot achieve optimal error rates. Furthermore, they prove that the optimal techniques for pure DP and approximate DP are fundamentally different, requiring noisy gradients in one case and sophisticated sampling in the other.
As shown in the table above, the authors provide matching upper and lower bounds, proving that their algorithms reach the fundamental limits of what is possible under differential privacy. For general convex functions under $(\epsilon, \delta)$-DP, they achieve an excess risk of $\tilde{O}(\frac{\sqrt{p}}{\epsilon n})$. For strongly convex functions, the improvement is even more dramatic, reaching $\tilde{O}(\frac{p}{\epsilon^2 n^2})$, a significant leap over previous $1/\sqrt{n}$ scaling.
Conclusion and Future Directions
This research establishes the first set of algorithms for convex ERM that achieve mathematically optimal error rates. By providing matching lower bounds using cryptographic tools like fingerprinting codes, the authors define the theoretical boundaries of private learning.
Despite these advances, some challenges remain. There is still a small polynomial gap in the dimension $p$ regarding generalization error (performance on unseen data versus the training set). Additionally, while the grid-walk algorithm for pure DP is polynomial-time, it remains computationally intensive compared to standard SGD. Future work may focus on narrowing these gaps and further optimizing the computational efficiency of these private sampling techniques.
This summary is based on "Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds" by Raef Bassily, Adam Smith, and Abhradeep Thakurta.
Summary updated