mlsanityData to 14 Oct 2026

Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler

arXiv 2302.06085 ↗First posted 13 Feb 2023cs.DS cs.CR cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 39 of its 107 references that are in the map. First posted on arXiv 13 Feb 2023.

Builds on

39 of 107 references.

References · 39

  1. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 208
  2. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  3. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  4. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  5. 2016High-dimensional Bayesian inference via the Unadjusted Langevin Algorithmcited by 146
  6. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 133
  7. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  8. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 127
  9. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 118
  10. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 86
  11. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  12. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 78
27 more
  1. 2022Improved analysis for a proximal algorithm for samplingcited by 73
  2. 2018Mirrored Langevin Dynamicscited by 61
  3. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
  4. 2020Wasserstein Control of Mirror Langevin Monte Carlocited by 55
  5. 2020Efficient constrained sampling via the mirror-Langevin algorithmcited by 55
  6. 2019Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradientscited by 51
  7. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  8. 2022Private Convex Optimization via Exponential Mechanismcited by 49
  9. 2013Proximal Markov chain Monte Carlo algorithmscited by 46
  10. 2017Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlocited by 43
  11. 2021The Mirror Langevin Algorithm Converges with Vanishing Biascited by 37
  12. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  13. 2019Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetrycited by 34
  14. 2017Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computationcited by 32
  15. 2019Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributionscited by 28
  16. 2022Convergence of the Riemannian Langevin Algorithmcited by 25
  17. 2021A Proximal Algorithm for Sampling from Non-smooth Potentialscited by 24
  18. 2018Acceleration through Optimistic No-Regret Dynamicscited by 22
  19. 2020Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlocited by 22
  20. 2019An Efficient Sampling Algorithm for Non-smooth Composite Potentialscited by 19
  21. 2021Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributionscited by 19
  22. 2020Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Accelerationcited by 18
  23. 2022Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chainscited by 16
  24. 2022Private Convex Optimization in General Normscited by 13
  25. 2022A Slightly Improved Bound for the KLS Constantcited by 10
  26. 2022Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integratorscited by 10
  27. 2021The entropic barrier is n-self-concordantcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 2; 2025: 2; 2026: 3.

10 papers.

  1. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 45
  2. 2024In-and-Out: Algorithmic Diffusion for Sampling Convex Bodiescited by 19
  3. 2023Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithmcited by 11
  4. 2024A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplerscited by 6
  5. 2023Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithmscited by 4
  6. 2025Mirror Mean-Field Langevin Dynamicscited by 3
  7. 2025Oracle-based Uniform Sampling from Convex Bodiescited by 3
  8. 2026High-accuracy log-concave sampling with stochastic queriescited by 2
  9. 2026Functional Stochastic Localizationcited by 0
  10. 2026Reflected Proximal Dynamics for Accelerated High-Accuracy Log-Concave Samplingcited by 0