Balls-and-Bins Sampling for DP-SGD
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915220259078144 |
|---|---|
| author | Chua, Lynn Ghazi, Badih Harrison, Charlie Leeman, Ethan Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Sinha, Amer Zhang, Chiyuan |
| author_facet | Chua, Lynn Ghazi, Badih Harrison, Charlie Leeman, Ethan Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Sinha, Amer Zhang, Chiyuan |
| contents | We introduce the Balls-and-Bins sampling for differentially private (DP) optimization methods such as DP-SGD. While it has been common practice to use some form of shuffling in DP-SGD implementations, privacy accounting algorithms have typically assumed that Poisson subsampling is used instead. Recent work by Chua et al. (ICML 2024), however, pointed out that shuffling based DP-SGD can have a much larger privacy cost in practical regimes of parameters. In this work we show that the Balls-and-Bins sampling achieves the "best-of-both" samplers, namely, the implementation of Balls-and-Bins sampling is similar to that of Shuffling and models trained using DP-SGD with Balls-and-Bins sampling achieve utility comparable to those trained using DP-SGD with Shuffling at the same noise multiplier, and yet, Balls-and-Bins sampling enjoys similar-or-better privacy amplification as compared to Poisson subsampling in practical regimes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_16802 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Balls-and-Bins Sampling for DP-SGD Chua, Lynn Ghazi, Badih Harrison, Charlie Leeman, Ethan Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Sinha, Amer Zhang, Chiyuan Machine Learning Cryptography and Security Data Structures and Algorithms We introduce the Balls-and-Bins sampling for differentially private (DP) optimization methods such as DP-SGD. While it has been common practice to use some form of shuffling in DP-SGD implementations, privacy accounting algorithms have typically assumed that Poisson subsampling is used instead. Recent work by Chua et al. (ICML 2024), however, pointed out that shuffling based DP-SGD can have a much larger privacy cost in practical regimes of parameters. In this work we show that the Balls-and-Bins sampling achieves the "best-of-both" samplers, namely, the implementation of Balls-and-Bins sampling is similar to that of Shuffling and models trained using DP-SGD with Balls-and-Bins sampling achieve utility comparable to those trained using DP-SGD with Shuffling at the same noise multiplier, and yet, Balls-and-Bins sampling enjoys similar-or-better privacy amplification as compared to Poisson subsampling in practical regimes. |
| title | Balls-and-Bins Sampling for DP-SGD |
| topic | Machine Learning Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.16802 |