High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent

Paul Mangold, Aurélien Bellet, Joseph Salmon, Marc Tommasi
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:4894-4916, 2023.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-mangold23a, title = {High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent}, author = {Mangold, Paul and Bellet, Aur\'elien and Salmon, Joseph and Tommasi, Marc}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {4894--4916}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/mangold23a/mangold23a.pdf}, url = {https://proceedings.mlr.press/v206/mangold23a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent %A Paul Mangold %A Aurélien Bellet %A Joseph Salmon %A Marc Tommasi %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-mangold23a %I PMLR %P 4894--4916 %U https://proceedings.mlr.press/v206/mangold23a.html %V 206 %X 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.
APA
Mangold, P., Bellet, A., Salmon, J. & Tommasi, M.. (2023). High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:4894-4916 Available from https://proceedings.mlr.press/v206/mangold23a.html.

Related Material