Private Zeroth-Order Nonsmooth Nonconvex Optimization
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_ | 1866909232880680960 |
|---|---|
| author | Zhang, Qinzi Tran, Hoang Cutkosky, Ashok |
| author_facet | Zhang, Qinzi Tran, Hoang Cutkosky, Ashok |
| contents | We introduce a new zeroth-order algorithm for private stochastic optimization on nonconvex and nonsmooth objectives. Given a dataset of size $M$, our algorithm ensures $(α,αρ^2/2)$-Rényi differential privacy and finds a $(δ,ε)$-stationary point so long as $M=\tildeΩ\left(\frac{d}{δε^3} + \frac{d^{3/2}}{ρδε^2}\right)$. This matches the optimal complexity of its non-private zeroth-order analog. Notably, although the objective is not smooth, we have privacy ``for free'' whenever $ρ\ge \sqrt{d}ε$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_19579 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Private Zeroth-Order Nonsmooth Nonconvex Optimization Zhang, Qinzi Tran, Hoang Cutkosky, Ashok Optimization and Control Cryptography and Security Machine Learning We introduce a new zeroth-order algorithm for private stochastic optimization on nonconvex and nonsmooth objectives. Given a dataset of size $M$, our algorithm ensures $(α,αρ^2/2)$-Rényi differential privacy and finds a $(δ,ε)$-stationary point so long as $M=\tildeΩ\left(\frac{d}{δε^3} + \frac{d^{3/2}}{ρδε^2}\right)$. This matches the optimal complexity of its non-private zeroth-order analog. Notably, although the objective is not smooth, we have privacy ``for free'' whenever $ρ\ge \sqrt{d}ε$. |
| title | Private Zeroth-Order Nonsmooth Nonconvex Optimization |
| topic | Optimization and Control Cryptography and Security Machine Learning |
| url | https://arxiv.org/abs/2406.19579 |