Timezone: »
Poster
Sampling from Log-Concave Distributions with Infinity-Distance Guarantees
Oren Mangoubi · Nisheeth Vishnoi
For a $d$-dimensional log-concave distribution $\pi(\theta) \propto e^{-f(\theta)}$ constrained to a convex body $K$, the problem of outputting samples from a distribution $\nu$ which is $\varepsilon$-close in infinity-distance $\sup_{\theta \in K} |\log \frac{\nu(\theta)}{\pi(\theta)}|$ to $\pi$ arises in differentially private optimization. While sampling within total-variation distance $\varepsilon$ of $\pi$ can be done by algorithms whose runtime depends polylogarithmically on $\frac{1}{\varepsilon}$, prior algorithms for sampling in $\varepsilon$ infinity distance have runtime bounds that depend polynomially on $\frac{1}{\varepsilon}$. We bridge this gap by presenting an algorithm that outputs a point $\varepsilon$-close to $\pi$ in infinity distance that requires at most $\mathrm{poly}(\log \frac{1}{\varepsilon}, d)$ calls to a membership oracle for $K$ and evaluation oracle for $f$, when $f$ is Lipschitz. Our approach departs from prior works that construct Markov chains on a $\frac{1}{\varepsilon^2}$-discretization of $K$ to achieve a sample with $\varepsilon$ infinity-distance error, and present a method to directly convert continuous samples from $K$ with total-variation bounds to samples with infinity bounds. This approach also allows us to obtain an improvement on the dimension $d$ in the running time for the problem of sampling from a log-concave distribution on polytopes $K$ with infinity distance $\varepsilon$, by plugging in TV-distance running time bounds for the Dikin Walk Markov chain.
Author Information
Oren Mangoubi (Worcester Polytechnic Institute)
Nisheeth Vishnoi (Yale University)
More from the Same Authors
-
2021 Spotlight: Coresets for Time Series Clustering »
Lingxiao Huang · K Sudhir · Nisheeth Vishnoi -
2023 Poster: Sampling from Structured Log-Concave Distributions via a Soft-Threshold Dikin Walk »
Oren Mangoubi · Nisheeth Vishnoi -
2023 Poster: Bias in Evaluation Processes: An Optimization-Based Model »
L. Elisa Celis · Amit Kumar · Anay Mehrotra · Nisheeth Vishnoi -
2022 Spotlight: Lightning Talks 2A-2 »
Harikrishnan N B · Jianhao Ding · Juha Harviainen · Yizhen Wang · Lue Tao · Oren Mangoubi · Tong Bu · Nisheeth Vishnoi · Mohannad Alhanahnah · Mikko Koivisto · Aditi Kathpalia · Lei Feng · Nithin Nagaraj · Hongxin Wei · Xiaozhu Meng · Petteri Kaski · Zhaofei Yu · Tiejun Huang · Ke Wang · Jinfeng Yi · Jian Liu · Sheng-Jun Huang · Mihai Christodorescu · Songcan Chen · Somesh Jha -
2022 Spotlight: Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion »
Oren Mangoubi · Nisheeth Vishnoi -
2022 Spotlight: Sampling from Log-Concave Distributions with Infinity-Distance Guarantees »
Oren Mangoubi · Nisheeth Vishnoi -
2022 Spotlight: Lightning Talks 2A-1 »
Caio Kalil Lauand · Ryan Strauss · Yasong Feng · lingyu gu · Alireza Fathollah Pour · Oren Mangoubi · Jianhao Ma · Binghui Li · Hassan Ashtiani · Yongqi Du · Salar Fattahi · Sean Meyn · Jikai Jin · Nisheeth Vishnoi · zengfeng Huang · Junier B Oliva · yuan zhang · Han Zhong · Tianyu Wang · John Hopcroft · Di Xie · Shiliang Pu · Liwei Wang · Robert Qiu · Zhenyu Liao -
2022 Poster: Fair Ranking with Noisy Protected Attributes »
Anay Mehrotra · Nisheeth Vishnoi -
2022 Poster: Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion »
Oren Mangoubi · Nisheeth Vishnoi -
2021 Poster: Fair Classification with Adversarial Perturbations »
L. Elisa Celis · Anay Mehrotra · Nisheeth Vishnoi -
2021 Poster: Coresets for Time Series Clustering »
Lingxiao Huang · K Sudhir · Nisheeth Vishnoi -
2020 Poster: Coresets for Regressions with Panel Data »
Lingxiao Huang · K Sudhir · Nisheeth Vishnoi -
2019 Poster: Online sampling from log-concave distributions »
Holden Lee · Oren Mangoubi · Nisheeth Vishnoi -
2019 Poster: Coresets for Clustering with Fairness Constraints »
Lingxiao Huang · Shaofeng Jiang · Nisheeth Vishnoi -
2018 Poster: Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo »
Oren Mangoubi · Nisheeth Vishnoi