Papers › Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the...
Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry
Kunal Talwar, Abhradeep Thakurta, Li Zhang
Empirical Risk Minimization (ERM) is a standard technique in machine learning, where a model is selected by minimizing a loss function over constraint set. When the training dataset consists of private information, it is natural to use a differentially private ERM algorithm, and this problem has been the subject of a long line of work started with Chaudhuri and Monteleoni 2008. A private ERM algorithm outputs an approximate minimizer of the loss function and its error can be measured as the difference from the optimal value of the loss function. When the constraint set is arbitrary, the required error bounds are fairly well understood \cite{BassilyST14}. In this work, we show that the geometric properties of the constraint set can be used to derive significantly better results. Specifically, we show that a differentially private version of Mirror Descent leads to error bounds of the form Õ(G_𝒞/n) for a lipschitz loss function, improving on the Õ(√(p)/n) bounds in Bassily, Smith and Thakurta 2014. Here p is the dimensionality of the problem, n is the number of data points in the training set, and G_𝒞 denotes the Gaussian width of the constraint set that we optimize over. We show similar improvements for strongly convex functions, and for smooth functions. In addition, we show that when the loss function is Lipschitz with respect to the ℓ₁ norm and 𝒞 is ℓ₁-bounded, a differentially private version of the Frank-Wolfe algorithm gives error bounds of the form Õ(n^(-2/3)). This captures the important and common case of sparse linear regression (LASSO), when the data xᵢ satisfies |xᵢ|_∞ ≤1 and we optimize over the ℓ₁ ball. We show new lower bounds for this setting, that together with known bounds, imply that all our upper bounds are tight.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections