Published July 17, 2022
| Version v1
Conference paper
Differentially Private Coordinate Descent for Composite Empirical Risk Minimization
Contributors
Others:
- Machine Learning in Information Networks (MAGNET) ; Centre Inria de l'Université de Lille ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL) ; Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
- Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL) ; Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
- Institut Montpelliérain Alexander Grothendieck (IMAG) ; Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)
- Institut universitaire de France (IUF) ; Ministère de l'Education nationale, de l'Enseignement supérieur et de la Recherche (M.E.N.E.S.R.)
- Scientific Data Management (ZENITH) ; Centre Inria d'Université Côte d'Azur (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) ; Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)
- This work was supported in part by the Inria Exploratory Action FLAMED
- Kamalika Chaudhuri
- Stefanie Jegelka
- Le Song
- Csaba Szepesvari
- Gang Niu
- Sivan Sabato
- ANR-20-CE23-0015,PRIDE,Apprentissage automatique décentralisé et préservant la vie privée(2020)
- ANR-20-CHIA-0001,CAMELOT,Apprentissage automatique et optimisation coopératifs.(2020)
Description
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.
Abstract
International audienceAdditional details
Identifiers
- URL
- https://inria.hal.science/hal-03424974
- URN
- urn:oai:HAL:hal-03424974v3
Origin repository
- Origin repository
- UNICA