Output Perturbation for Differentially Private Convex Optimization with Improved Population Loss Bounds, Runtimes and Applications to Private Adversarial Training

Andrew Lowy, Meisam Razaviyayn

Introduction

Differential Privacy (DP) has become the gold standard for protecting individual data privacy in machine learning. However, implementing DP often introduces a "trilemma" between privacy guarantees, model utility (accuracy), and computational efficiency. While much of the recent literature focuses on $(\epsilon, \delta)$-DP (approximate privacy), which allows for a small probability of privacy failure, $(\epsilon, 0)$-DP (pure privacy) offers a more robust mathematical guarantee. Historically, achieving pure DP has been associated with significantly higher error rates or prohibitive computational costs.

In the paper "Output Perturbation for Differentially Private Convex Optimization with Improved Population Loss Bounds, Runtimes and Applications to Private Adversarial Training," the authors demonstrate that one of the simplest DP mechanisms—output perturbation—is far more powerful than previously realized. By adding noise only to the final parameters of a model, they achieve state-of-the-art utility and runtime bounds for a wide class of convex optimization problems.

The Methodology: Simplicity as a Strength

Most modern DP algorithms, such as DP-SGD, inject noise into every step of the optimization process. While effective, this "internal" noise can slow down convergence and complicate the use of accelerated optimization techniques.

In contrast, the authors focus on Output Perturbation, a "black-box" approach that follows two simple steps:

  1. Non-Private Training: Run a standard, non-private optimization algorithm (such as Gradient Descent or the accelerated "Katyusha" algorithm) to find an approximate minimizer of the objective function.
  2. Perturbation: Add a single, carefully calibrated volume of noise to the final model parameters.

The success of this approach hinges on the concept of uniform stability. If an algorithm is stable—meaning its output does not change significantly when a single data point in the training set is replaced—the "sensitivity" of the model is low. Lower sensitivity allows for the addition of less noise to achieve the same level of privacy, thereby preserving more of the model's accuracy.

Theoretical Contributions and Generalization

This research provides the tightest known population loss bounds for $(\epsilon, 0)$-DP in the context of convex optimization. A significant advantage of this framework is its flexibility; because the privacy mechanism is applied at the end, researchers can utilize the fastest available non-private optimizers. This allows the authors to achieve linear-time algorithms ($O(n)$), a substantial improvement over previous state-of-the-art pure DP methods that often required quadratic time ($O(n^2)$).

Beyond standard Empirical Risk Minimization (ERM), the paper extends these benefits to two critical modern frameworks:

  • Tilted ERM (TERM): A framework used to address fairness and outliers by prioritizing "hard" examples. The authors provide the first known DP bounds for TERM, enabling private models that are also more equitable.
  • Adversarial Training: This involves minimizing the "worst-case" loss to protect against malicious input perturbations. The paper establishes the first explicit excess risk and runtime bounds for DP Adversarial Training, quantifying the trade-offs between robustness, privacy, and speed.

Key Results and Insights

  • Optimal Utility: For smooth and strongly convex functions, the authors achieve near-optimal excess risk. In certain regimes, the error added by the privacy mechanism is smaller than the inherent statistical error of the model, effectively providing "privacy for free."
  • Computational Efficiency: By leveraging accelerated gradient methods, the proposed algorithms are significantly faster than prior iterative DP methods.
  • Pure DP Dominance: The results suggest that for pure $(\epsilon, 0)$-DP, output perturbation is superior to alternative methods like objective perturbation or gradient perturbation in terms of both implementation simplicity and performance.

Conclusion and Future Directions

This work breathes new life into output perturbation, proving that simple, stable algorithms can outperform complex iterative ones. While the current analysis is limited to convex optimization—covering models like Logistic Regression and SVMs—it sets a new benchmark for private machine learning. The authors identify the extension of these fast, stable "black-box" methods to non-convex landscapes, such as deep neural networks, as a primary challenge for future research. By bridging the gap between privacy, robustness, and efficiency, this research provides a vital toolkit for building trustworthy machine learning systems.

Summary updated

Abstract

Finding efficient, easily implementable differentially private (DP) algorithms that offer strong excess risk bounds is an important problem in modern machine learning. To date, most work has focused on private empirical risk minimization (ERM) or private population loss minimization. However, there are often other objectives--such as fairness, adversarial robustness, or sensitivity to outliers--besides average performance that are not captured in the classical ERM setup. To this end, we study a completely general family of convex, Lipschitz loss functions and establish the first known DP excess risk and runtime bounds for optimizing this broad class. We provide similar bounds under additional assumptions of smoothness and/or strong convexity. We also address private stochastic convex optimization (SCO). While $(\epsilon, \delta)$-DP ($\delta > 0$) has been the focus of much recent work in private SCO, proving tight population loss bounds and runtime bounds for $(\epsilon, 0)$-DP remains a challenging open problem. We provide the tightest known $(\epsilon, 0)$-DP population loss bounds and fastest runtimes under the presence of (or lack of) smoothness and strong convexity. Our methods extend to the $\delta > 0$ setting, where we offer the unique benefit of ensuring differential privacy for arbitrary $\epsilon > 0$ by incorporating a new form of Gaussian noise. Finally, we apply our theory to two learning frameworks: tilted ERM and adversarial learning. In particular, our theory quantifies tradeoffs between adversarial robustness, privacy, and runtime. Our results are achieved using perhaps the simplest DP algorithm: output perturbation. Although this method is not novel conceptually, our novel implementation scheme and analysis show that the power of this method to achieve strong privacy, utility, and runtime guarantees has not been fully appreciated in prior works.
BibTeX
@misc{lowy2021output,
  author = {Andrew Lowy and Meisam Razaviyayn},
  title = {{Output Perturbation for Differentially Private Convex Optimization with Improved Population Loss Bounds, Runtimes and Applications to Private Adversarial Training}},
  year = {2021},
  eprint = {2102.04704},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.04704},
}
Figure