2023/02/13 by Sivakanth Gopi, Gopi, Sivakanth, Yin Tat Lee +7 · 3 citations
Computer Science · Engineering · Mathematics · #Computation (stat.CO) #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Probability (math.PR) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2302.06085
openalex publication_date 2023/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℓp and Schatten-p norms for p ∈ [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.