Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912783192293376 |
|---|---|
| author | Gopi, Sivakanth Lee, Yin Tat Liu, Daogao Shen, Ruoqi Tian, Kevin |
| author_facet | Gopi, Sivakanth Lee, Yin Tat Liu, Daogao Shen, Ruoqi Tian, Kevin |
| contents | The development of efficient sampling algorithms catering to non-Euclidean geometries has been a challenging endeavor, as discretization techniques which succeed in the Euclidean setting do not readily carry over to more general settings. We develop a non-Euclidean analog of the recent proximal sampler of [LST21], which naturally induces regularization by an object known as the log-Laplace transform (LLT) of a density. We prove new mathematical properties (with an algorithmic flavor) of the LLT, such as strong convexity-smoothness duality and an isoperimetric inequality, which are used to prove a mixing time on our proximal sampler matching [LST21] under a warm start. As our main application, we show our warm-started sampler improves the value oracle complexity of differentially private convex optimization in $\ell_p$ and Schatten-$p$ norms for $p \in [1, 2]$ to match the Euclidean setting [GLL22], while retaining state-of-the-art excess risk bounds [GLLST23]. We find our investigation of the LLT to be a promising proof-of-concept of its utility as a tool for designing samplers, and outline directions for future exploration. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_06085 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler Gopi, Sivakanth Lee, Yin Tat Liu, Daogao Shen, Ruoqi Tian, Kevin Data Structures and Algorithms Cryptography and Security Machine Learning Probability Computation The development of efficient sampling algorithms catering to non-Euclidean geometries has been a challenging endeavor, as discretization techniques which succeed in the Euclidean setting do not readily carry over to more general settings. We develop a non-Euclidean analog of the recent proximal sampler of [LST21], which naturally induces regularization by an object known as the log-Laplace transform (LLT) of a density. We prove new mathematical properties (with an algorithmic flavor) of the LLT, such as strong convexity-smoothness duality and an isoperimetric inequality, which are used to prove a mixing time on our proximal sampler matching [LST21] under a warm start. As our main application, we show our warm-started sampler improves the value oracle complexity of differentially private convex optimization in $\ell_p$ and Schatten-$p$ norms for $p \in [1, 2]$ to match the Euclidean setting [GLL22], while retaining state-of-the-art excess risk bounds [GLLST23]. We find our investigation of the LLT to be a promising proof-of-concept of its utility as a tool for designing samplers, and outline directions for future exploration. |
| title | Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler |
| topic | Data Structures and Algorithms Cryptography and Security Machine Learning Probability Computation |
| url | https://arxiv.org/abs/2302.06085 |