High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent

Abstract

In this paper, we study differentially private empirical risk minimization (DP-ERM). It has been shown that the worst-case utility of DP-ERM reduces polynomially as the dimension increases. This is a major obstacle to privately learning large machine learning models. In high dimension, it is common for some model's parameters to carry more information than others. To exploit this, we propose a differentially private greedy coordinate descent (DP-GCD) algorithm. At each iteration, DP-GCD privately performs a coordinate-wise gradient step along the gradients' (approximately) greatest entry. We show theoretically that DP-GCD can achieve a logarithmic dependence on the dimension for a wide range of problems by naturally exploiting their structural properties (such as quasi-sparse solutions). We illustrate this behavior numerically, both on synthetic and real datasets.

References in corpus (18)

• Scikit-learn: Machine Learning in Python
• Deep Learning with Differential Privacy
• Renyi Differential Privacy
• Differentially Private Empirical Risk Minimization
• Train faster, generalize better: Stability of stochastic gradient descent
• Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
• Rényi Differential Privacy of the Sampled Gaussian Mechanism
• Private Stochastic Convex Optimization with Optimal Rates
• Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
• Personalized and Private Peer-to-Peer Machine Learning
• A Primer on Coordinate Descent Algorithms
• SEGA: Variance Reduction via Gradient Sketching
• Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry
• Approximate Steepest Coordinate Descent
• Efficient Greedy Coordinate Descent for Composite Problems
• From safe screening rules to working sets for faster Lasso-type solvers
• High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data
• Differentially Private Coordinate Descent for Composite Empirical Risk Minimization