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