Differentially Private Optimization with Sparse Gradients
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916462733557760 |
|---|---|
| author | Ghazi, Badih Guzmán, Cristóbal Kamath, Pritish Kumar, Ravi Manurangsi, Pasin |
| author_facet | Ghazi, Badih Guzmán, Cristóbal Kamath, Pritish Kumar, Ravi Manurangsi, Pasin |
| contents | Motivated by applications of large embedding models, we study differentially private (DP) optimization problems under sparsity of individual gradients. We start with new near-optimal bounds for the classic mean estimation problem but with sparse data, improving upon existing algorithms particularly for the high-dimensional regime. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for stochastic convex optimization with sparse gradients; the former represents the first nearly dimension-independent rates for this problem. Finally, we study the approximation of stationary points for the empirical loss in approximate-DP optimization and obtain rates that depend on sparsity instead of dimension, modulo polylogarithmic factors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_10881 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Differentially Private Optimization with Sparse Gradients Ghazi, Badih Guzmán, Cristóbal Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Machine Learning Optimization and Control Motivated by applications of large embedding models, we study differentially private (DP) optimization problems under sparsity of individual gradients. We start with new near-optimal bounds for the classic mean estimation problem but with sparse data, improving upon existing algorithms particularly for the high-dimensional regime. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for stochastic convex optimization with sparse gradients; the former represents the first nearly dimension-independent rates for this problem. Finally, we study the approximation of stationary points for the empirical loss in approximate-DP optimization and obtain rates that depend on sparsity instead of dimension, modulo polylogarithmic factors. |
| title | Differentially Private Optimization with Sparse Gradients |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2404.10881 |