mlsanityData to 7 Oct 2026

High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent

arXiv 2207.01560 ↗First posted 4 Jul 2022cs.LG cs.CR stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 34 of its 63 references that are in the map. First posted on arXiv 4 Jul 2022.

Builds on

34 of 63 references.

References · 34

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2021Convex optimizationcited by 2,479
  3. 2016Membership Inference Attacks against Machine Learning Modelscited by 2,221
  4. 2017Renyi Differential Privacycited by 643
  5. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  6. 2014OpenML: networked science in machine learningcited by 523
  7. 2015Coordinate Descent Algorithmscited by 218
  8. 2019R'enyi Differential Privacy of the Sampled Gaussian Mechanismcited by 199
  9. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  10. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  11. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  12. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 127
22 more
  1. 2014Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Boundscited by 104
  2. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
  3. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  4. 2020Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identificationcited by 88
  5. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  6. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  7. 2017Personalized and Private Peer-to-Peer Machine Learningcited by 54
  8. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  9. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  10. 2015Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selectioncited by 39
  11. 2019A New Analysis of Differential Privacy's Generalization Guaranteescited by 36
  12. 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
  13. 2013Accelerated, Parallel and Proximal Coordinate Descentcited by 25
  14. 2014Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometrycited by 24
  15. 2021Differentially Private SGD with Non-Smooth Lossescited by 22
  16. 2016A Primer on Coordinate Descent Algorithmscited by 16
  17. 2021Differentially Private Coordinate Descent for Composite Empirical Risk Minimizationcited by 10
  18. 2013Inexact Coordinate Descent: Complexity and Preconditioningcited by 8
  19. 2018Efficient Greedy Coordinate Descent for Composite Problemscited by 8
  20. 2020Differentially Private Stochastic Coordinate Descentcited by 8
  21. 2017From safe screening rules to working sets for faster Lasso-type solverscited by 3
  22. 2017Approximate Steepest Coordinate Descentcited by 2

Built on by

Cited by year

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

4 papers.

  1. 2023Toward Understanding Why Adam Converges Faster Than SGD for Transformerscited by 50
  2. 2024SoK: A Review of Differentially Private Linear Models For High-Dimensional Datacited by 5
  3. 2025Differentially Private and Federated Structure Learning in Bayesian Networkscited by 1
  4. 2024SPriFed-OMP: A Differentially Private Federated Learning Algorithm for Sparse Basis Recoverycited by 0