Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910296895913984 |
|---|---|
| author | Koloskova, Anastasia McKenna, Ryan Charles, Zachary Rush, Keith McMahan, Brendan |
| author_facet | Koloskova, Anastasia McKenna, Ryan Charles, Zachary Rush, Keith McMahan, Brendan |
| contents | We study gradient descent under linearly correlated noise. Our work is motivated by recent practical methods for optimization with differential privacy (DP), such as DP-FTRL, which achieve strong performance in settings where privacy amplification techniques are infeasible (such as in federated learning). These methods inject privacy noise through a matrix factorization mechanism, making the noise linearly correlated over iterations. We propose a simplified setting that distills key facets of these methods and isolates the impact of linearly correlated noise. We analyze the behavior of gradient descent in this setting, for both convex and non-convex functions. Our analysis is demonstrably tighter than prior work and recovers multiple important special cases exactly (including anticorrelated perturbed gradient descent). We use our results to develop new, effective matrix factorizations for differentially private optimization, and highlight the benefits of these factorizations theoretically and empirically. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_01463 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy Koloskova, Anastasia McKenna, Ryan Charles, Zachary Rush, Keith McMahan, Brendan Machine Learning We study gradient descent under linearly correlated noise. Our work is motivated by recent practical methods for optimization with differential privacy (DP), such as DP-FTRL, which achieve strong performance in settings where privacy amplification techniques are infeasible (such as in federated learning). These methods inject privacy noise through a matrix factorization mechanism, making the noise linearly correlated over iterations. We propose a simplified setting that distills key facets of these methods and isolates the impact of linearly correlated noise. We analyze the behavior of gradient descent in this setting, for both convex and non-convex functions. Our analysis is demonstrably tighter than prior work and recovers multiple important special cases exactly (including anticorrelated perturbed gradient descent). We use our results to develop new, effective matrix factorizations for differentially private optimization, and highlight the benefits of these factorizations theoretically and empirically. |
| title | Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2302.01463 |