Differentially Private Empirical Risk Minimization

2009/12/01 by Kamalika Chaudhuri, Chaudhuri, Kamalika, Claire Monteleoni +3 · 37 citations
Computer Science · Decision Sciences · Mathematics · #Artificial Intelligence (cs.AI) #Cryptography and Security (cs.CR) #Databases (cs.DB) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data #Probability and Risk Models #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.0912.0071

openalex publication_date 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Privacy-preserving machine learning algorithms are crucial for the increasingly common setting in which personal data, such as medical or financial records, are analyzed. We provide general techniques to produce privacy-preserving approximations of classifiers learned via (regularized) empirical risk minimization (ERM). These algorithms are private under the ε-differential privacy definition due to Dwork et al. (2006). First we apply the output perturbation ideas of Dwork et al. (2006), to ERM classification. Then we propose a new method, objective perturbation, for privacy-preserving machine learning algorithm design. This method entails perturbing the objective function before optimizing over classifiers. If the loss and regularizer satisfy certain convexity and differentiability criteria, we prove theoretical results showing that our algorithms preserve privacy, and provide generalization bounds for linear and nonlinear kernels. We further present a privacy-preserving technique for tuning the parameters in general machine learning algorithms, thereby providing end-to-end privacy guarantees for the training process. We apply these results to produce privacy-preserving analogues of regularized logistic regression and support vector machines. We obtain encouraging results from evaluating their performance on real demographic and benchmark data sets. Our results show that both theoretically and empirically, objective perturbation is superior to the previous state-of-the-art, output perturbation, in managing the inherent tradeoff between privacy and learning performance.

Citations

• Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning

Cited by

• DPSR: Differentially Private Sparse Reconstruction via Multi-Stage Denoising for Recommender Systems
• A Systems-Theoretic View on the Convergence of Algorithms under Disturbances
• Privacy Blur: Quantifying Privacy and Utility for Image Data Release
• Privacy Loss of Noise Perturbation via Concentration Analysis of A Product Measure
• Towards Understanding Generalization in DP-GD: A Case Study in Training Two-Layer CNNs
• Trustless Federated Learning at Edge-Scale: A Compositional Architecture for Decentralized, Verifiable, and Incentive-Aligned Coordination
• Fairness Meets Privacy: Integrating Differential Privacy and Demographic Parity in Multi-class Classification
• Understanding Private Learning From Feature Perspective
• Rényi Differential Privacy for Heavy-Tailed SDEs via Fractional Poincaré Inequalities
• On the Gradient Complexity of Private Optimization with Private Oracles
• Private Zeroth-Order Optimization with Public Data
• Black-Box Differentially Private Nonparametric Confidence Intervals Under Minimal Assumptions
• Beyond Uniform Deletion: A Data Value-Weighted Framework for Certified Machine Unlearning
• Multi-Class Support Vector Machine with Differential Privacy
• Differentially Private Two-Stage Gradient Descent for Instrumental Variable Regression
• No Prior, No Leakage: Revisiting Reconstruction Attacks in Trained Neural Networks
• Quadratic Objective Perturbation: Curvature-Based Differential Privacy
• Private Queries with Sigma-Counting
• Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition
• Enhancing Differentially Private Linear Regression via Public Second-Moment
• Towards Reliable and Generalizable Differentially Private Machine Learning (Extended Version)
• Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approach
• The Fair Game: Auditing & Debiasing AI Algorithms Over Time
• Graph Structure Learning with Privacy Guarantees for Open Graph Data
• Characterizing Linear Alignment Across Language Models
• Striking the Perfect Balance: Preserving Privacy While Boosting Utility in Collaborative Medical Prediction Platforms
• Optimal Debiased Inference on Privatized Data via Indirect Estimation and Parametric Bootstrap
• Optimal Differentially Private Ranking from Pairwise Comparisons
• AdaDPIGU: Differentially Private SGD with Adaptive Clipping and Importance-Based Gradient Updates for Deep Neural Networks
• On the Inherent Privacy of Zeroth Order Projected Gradient Descent
• Embodied AI Agents: Modeling the World
• Enhancing One-run Privacy Auditing with Quantile Regression-Based Membership Inference
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning
• Differential Privacy in Machine Learning: From Symbolic AI to LLMs
• Differentially Private Sparse Linear Regression with Heavy-tailed Responses
• System-Aware Unlearning Algorithms: Use Lesser, Forget Faster
• Privacy Amplification Through Synthetic Data: Insights from Linear Regression

Related

• Noise-Augmented Privacy-Preserving Empirical Risk Minimization with Dual-purpose Regularizer and Privacy Budget Retrieval and Recycling
• Differential Privacy and Machine Learning: a Survey and Review
• Differentially Private Confidence Intervals for Empirical Risk Minimization
• Stability Enhanced Privacy and Applications in Private Stochastic Gradient Descent
• Accuracy First: Selecting a Differential Privacy Level for\n Accuracy-Constrained ERM