Differentially Private Coordinate Descent for Composite Empirical Risk Minimization

Paul Mangold (1, 2) , Aurélien Bellet (1, 2) , Joseph Salmon (3, 4, 5) , Marc Tommasi (1, 2)

1 MAGNET - Machine Learning in Information Networks
2 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
3 IMAG - Institut Montpelliérain Alexander Grothendieck
4 IUF - Institut universitaire de France
5 ZENITH - Scientific Data Management

Machine learning models can leak information about the data used to train them. To mitigate this issue, Differentially Private (DP) variants of optimization algorithms like Stochastic Gradient Descent (DP-SGD) have been designed to trade-off utility for privacy in Empirical Risk Minimization (ERM) problems. In this paper, we propose Differentially Private proximal Coordinate Descent (DP-CD), a new method to solve composite DP-ERM problems. We derive utility guarantees through a novel theoretical analysis of inexact coordinate descent. Our results show that, thanks to larger step sizes, DP-CD can exploit imbalance in gradient coordinates to outperform DP-SGD. We also prove new lower bounds for composite DP-ERM under coordinate-wise regularity assumptions, that are nearly matched by DP-CD. For practical implementations, we propose to clip gradients using coordinate-wise thresholds that emerge from our theory, avoiding costly hyperparameter tuning. Experiments on real and synthetic data support our results, and show that DP-CD compares favorably with DP-SGD.

Domaines: Apprentissage [cs.LG]; Machine Learning [stat.ML]

Paul Mangold, Aurélien Bellet, Joseph Salmon, Marc Tommasi. Differentially Private Coordinate Descent for Composite Empirical Risk Minimization. ICML 2022 - 39th International Conference on Machine Learning, Jul 2022, Baltimore, United States. pp.14948-14978. ⟨hal-03424974v3⟩