mlsanityData to 14 Oct 2026

Differentially Private Coordinate Descent for Composite Empirical Risk Minimization

arXiv 2110.11688 ↗First posted 22 Oct 2021cs.LG cs.CR stat.MLcited by 10

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 33 of its 71 references that are in the map. First posted on arXiv 22 Oct 2021.

Builds on

33 of 71 references.

References · 33

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2016Membership Inference Attacks against Machine Learning Modelscited by 2,281
  3. 2017Renyi Differential Privacycited by 650
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  5. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  6. 2018Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergencescited by 242
  7. 2019Differentially Private Learning with Adaptive Clippingcited by 220
  8. 2015Coordinate Descent Algorithmscited by 219
  9. 2019R'enyi Differential Privacy of the Sampled Gaussian Mechanismcited by 204
  10. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  11. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  12. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
21 more
  1. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  2. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 103
  3. 2020Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identificationcited by 90
  4. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  5. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  6. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 82
  7. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  8. 2019AdaCliP: Adaptive Clipping for Private SGDcited by 77
  9. 2017Personalized and Private Peer-to-Peer Machine Learningcited by 54
  10. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  11. 2015Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selectioncited by 39
  12. 2018Celer: a Fast Solver for the Lasso with Dual Extrapolationcited by 31
  13. 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
  14. 2013Accelerated, Parallel and Proximal Coordinate Descentcited by 25
  15. 2021Differentially Private SGD with Non-Smooth Lossescited by 22
  16. 2016A Primer on Coordinate Descent Algorithmscited by 17
  17. 2013Inexact Coordinate Descent: Complexity and Preconditioningcited by 8
  18. 2018Efficient Greedy Coordinate Descent for Composite Problemscited by 8
  19. 2020Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problemscited by 8
  20. 2020Differentially Private Stochastic Coordinate Descentcited by 8
  21. 2014A Fast Active Set Block Coordinate Descent Algorithm for ℓ1-regularized least squarescited by 2

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 3; 2023: 3; 2024: 1; 2025: 2.

10 papers.

  1. 2023Toward Understanding Why Adam Converges Faster Than SGD for Transformerscited by 53
  2. 2022Private Convex Optimization via Exponential Mechanismcited by 49
  3. 2022Differentially Private Learning with Per-Sample Adaptive Clippingcited by 21
  4. 2021Improving Differentially Private SGD via Randomly Sparsified Gradientscited by 8
  5. 2023From Noisy Fixed-Point Iterations to Private ADMM for Centralized and Federated Learningcited by 5
  6. 2022High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descentcited by 4
  7. 2023Differential Privacy via Distributionally Robust Optimizationcited by 2
  8. 2025Purifying Approximate Differential Privacy with Randomized Post-processingcited by 2
  9. 2024Enhancing DP-SGD through Non-monotonous Adaptive Scaling Gradient Weightcited by 1
  10. 2025Differentially Private and Federated Structure Learning in Bayesian Networkscited by 1