Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches
In this paper we revisit the DP stochastic convex optimization (SCO) problem. For convex smooth losses, it is well-known that the canonical DP-SGD (stochastic gradient descent) achieves the optimal rate of $O\left(\frac{LR}{\sqrt{n}} + \frac{LR \sqrt{p \log(1/δ)}}{εn}\right)$ under $(ε, δ)$-DP, and...
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Articolo |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2406.02716 http://arxiv.org/abs/2406.02716 |
| Tags: |
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1879176162255568896 |
|---|---|
| author | Choquette-Choo, Christopher A. Ganesh, Arun Thakurta, Abhradeep |
| author_browse | Choquette-Choo, Christopher A. Ganesh, Arun Thakurta, Abhradeep |
| author_facet | Choquette-Choo, Christopher A. Ganesh, Arun Thakurta, Abhradeep |
| author_sort | Choquette-Choo, Christopher A. |
| building | arXiv |
| collection | Acceso abierto |
| description | In this paper we revisit the DP stochastic convex optimization (SCO) problem. For convex smooth losses, it is well-known that the canonical DP-SGD (stochastic gradient descent) achieves the optimal rate of $O\left(\frac{LR}{\sqrt{n}} + \frac{LR \sqrt{p \log(1/δ)}}{εn}\right)$ under $(ε, δ)$-DP, and also well-known that variants of DP-SGD can achieve the optimal rate in a single epoch. However, the batch gradient complexity (i.e., number of adaptive optimization steps), which is important in applications like federated learning, is less well-understood. In particular, all prior work on DP-SCO requires $Ω(n)$ batch gradient steps, multiple epochs, or convexity for privacy.
We propose an algorithm, Accelerated-DP-SRGD (stochastic recursive gradient descent), which bypasses the limitations of past work: it achieves the optimal rate for DP-SCO (up to polylog factors), in a single epoch using $\sqrt{n}$ batch gradient steps with batch size $\sqrt{n}$, and can be made private for arbitrary (non-convex) losses via clipping. If the global minimizer is in the constraint set, we can further improve this to $n^{1/4}$ batch gradient steps with batch size $n^{3/4}$. To achieve this, our algorithm combines three key ingredients, a variant of stochastic recursive gradients (SRG), accelerated gradient descent, and correlated noise generation from DP continual counting. |
| first_indexed | 2026-10-16T00:40:37Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2406.02716</identifier><datestamp>2024-10-04</datestamp>
<dc:title>Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches</dc:title>
<dc:creator>Choquette-Choo, Christopher A.</dc:creator>
<dc:creator>Ganesh, Arun</dc:creator>
<dc:creator>Thakurta, Abhradeep</dc:creator>
<dc:subject>Machine Learning</dc:subject>
<dc:subject>Cryptography and Security</dc:subject>
<dc:description>In this paper we revisit the DP stochastic convex optimization (SCO) problem. For convex smooth losses, it is well-known that the canonical DP-SGD (stochastic gradient descent) achieves the optimal rate of $O\left(\frac{LR}{\sqrt{n}} + \frac{LR \sqrt{p \log(1/δ)}}{εn}\right)$ under $(ε, δ)$-DP, and also well-known that variants of DP-SGD can achieve the optimal rate in a single epoch. However, the batch gradient complexity (i.e., number of adaptive optimization steps), which is important in applications like federated learning, is less well-understood. In particular, all prior work on DP-SCO requires $Ω(n)$ batch gradient steps, multiple epochs, or convexity for privacy.
We propose an algorithm, Accelerated-DP-SRGD (stochastic recursive gradient descent), which bypasses the limitations of past work: it achieves the optimal rate for DP-SCO (up to polylog factors), in a single epoch using $\sqrt{n}$ batch gradient steps with batch size $\sqrt{n}$, and can be made private for arbitrary (non-convex) losses via clipping. If the global minimizer is in the constraint set, we can further improve this to $n^{1/4}$ batch gradient steps with batch size $n^{3/4}$. To achieve this, our algorithm combines three key ingredients, a variant of stochastic recursive gradients (SRG), accelerated gradient descent, and correlated noise generation from DP continual counting. </dc:description>
<dc:description>Differences from v1: Stronger results assuming global minimizer in constraint set, more detailed comparison to past work, cut empirical section</dc:description>
<dc:date>2024-06-04</dc:date>
<dc:date>2024-10-02</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2406.02716</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2406.02716</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2406.02716 |
| institution | arXiv |
| last_indexed | 2026-10-16T00:40:37Z |
| publishDate | 2024 |
| publishDateRange | 2024 |
| publishDateSort | 2024 |
| record_format | oai_dc |
| spelling | arxiv-2406.027162024-10-04 Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches Choquette-Choo, Christopher A. Ganesh, Arun Thakurta, Abhradeep Machine Learning Cryptography and Security In this paper we revisit the DP stochastic convex optimization (SCO) problem. For convex smooth losses, it is well-known that the canonical DP-SGD (stochastic gradient descent) achieves the optimal rate of $O\left(\frac{LR}{\sqrt{n}} + \frac{LR \sqrt{p \log(1/δ)}}{εn}\right)$ under $(ε, δ)$-DP, and also well-known that variants of DP-SGD can achieve the optimal rate in a single epoch. However, the batch gradient complexity (i.e., number of adaptive optimization steps), which is important in applications like federated learning, is less well-understood. In particular, all prior work on DP-SCO requires $Ω(n)$ batch gradient steps, multiple epochs, or convexity for privacy. We propose an algorithm, Accelerated-DP-SRGD (stochastic recursive gradient descent), which bypasses the limitations of past work: it achieves the optimal rate for DP-SCO (up to polylog factors), in a single epoch using $\sqrt{n}$ batch gradient steps with batch size $\sqrt{n}$, and can be made private for arbitrary (non-convex) losses via clipping. If the global minimizer is in the constraint set, we can further improve this to $n^{1/4}$ batch gradient steps with batch size $n^{3/4}$. To achieve this, our algorithm combines three key ingredients, a variant of stochastic recursive gradients (SRG), accelerated gradient descent, and correlated noise generation from DP continual counting. Differences from v1: Stronger results assuming global minimizer in constraint set, more detailed comparison to past work, cut empirical section 2024-06-04 2024-10-02 text https://arxiv.org/abs/2406.02716 http://arxiv.org/abs/2406.02716 |
| spellingShingle | Machine Learning Cryptography and Security Choquette-Choo, Christopher A. Ganesh, Arun Thakurta, Abhradeep Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches |
| title | Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches |
| title_full | Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches |
| title_fullStr | Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches |
| title_full_unstemmed | Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches |
| title_short | Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches |
| title_sort | optimal rates for o 1 smooth dp sco with a single epoch and large batches |
| topic | Machine Learning Cryptography and Security |
| url | https://arxiv.org/abs/2406.02716 http://arxiv.org/abs/2406.02716 |
| work_keys_str_mv | AT choquettechoochristophera optimalratesforo1smoothdpscowithasingleepochandlargebatches AT ganesharun optimalratesforo1smoothdpscowithasingleepochandlargebatches AT thakurtaabhradeep optimalratesforo1smoothdpscowithasingleepochandlargebatches |