# Differentially Private Coordinate Descent for Composite Empirical Risk Minimization

arXiv: https://arxiv.org/abs/2110.11688 · HTML: https://mlsanity.com/paper/2110.11688/

## 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 (most cited first, 30 of 33)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Differentially Private Learning with Adaptive Clipping](https://mlsanity.com/paper/1905.03871/) (2019)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification](https://mlsanity.com/paper/2007.03813/) (2020)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [AdaCliP: Adaptive Clipping for Private SGD](https://mlsanity.com/paper/1908.07643/) (2019)
- [Personalized and Private Peer-to-Peer Machine Learning](https://mlsanity.com/paper/1705.08435/) (2017)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015)
- [Celer: a Fast Solver for the Lasso with Dual Extrapolation](https://mlsanity.com/paper/1802.07481/) (2018)
- [SEGA: Variance Reduction via Gradient Sketching](https://mlsanity.com/paper/1809.03054/) (2018)
- [Accelerated, Parallel and Proximal Coordinate Descent](https://mlsanity.com/paper/1312.5799/) (2013)
- [Differentially Private SGD with Non-Smooth Losses](https://mlsanity.com/paper/2101.08925/) (2021)
- [A Primer on Coordinate Descent Algorithms](https://mlsanity.com/paper/1610.00040/) (2016)
- [Inexact Coordinate Descent: Complexity and Preconditioning](https://mlsanity.com/paper/1304.5530/) (2013)
- [Efficient Greedy Coordinate Descent for Composite Problems](https://mlsanity.com/paper/1810.06999/) (2018)

## Built on by (most cited first, 10 of 10)

- [Toward Understanding Why Adam Converges Faster Than SGD for Transformers](https://mlsanity.com/paper/2306.00204/) (2023)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Differentially Private Learning with Per-Sample Adaptive Clipping](https://mlsanity.com/paper/2212.00328/) (2022)
- [Improving Differentially Private SGD via Randomly Sparsified Gradients](https://mlsanity.com/paper/2112.00845/) (2021)
- [From Noisy Fixed-Point Iterations to Private ADMM for Centralized and Federated Learning](https://mlsanity.com/paper/2302.12559/) (2023)
- [High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent](https://mlsanity.com/paper/2207.01560/) (2022)
- [Differential Privacy via Distributionally Robust Optimization](https://mlsanity.com/paper/2304.12681/) (2023)
- [Purifying Approximate Differential Privacy with Randomized Post-processing](https://mlsanity.com/paper/2503.21071/) (2025)
- [Enhancing DP-SGD through Non-monotonous Adaptive Scaling Gradient Weight](https://mlsanity.com/paper/2411.03059/) (2024)
- [Differentially Private and Federated Structure Learning in Bayesian Networks](https://mlsanity.com/paper/2512.01708/) (2025)

## 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.