English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

For a $d$-dimensional log-concave distribution $\pi(\theta) \proptoe^{-f(\theta)}$ constrained to a convex body $K$, the problem of outputtingsamples from a distribution $\nu$ which is $\varepsilon$-close ininfinity-distance $\sup_{\theta \in K} |\log \frac{\nu(\theta)}{\pi(\theta)}|$to $\pi$ arises in differentially private optimization. While sampling withintotal-variation distance $\varepsilon$ of $\pi$ can be done by algorithms whoseruntime depends polylogarithmically on $\frac{1}{\varepsilon}$, prioralgorithms for sampling in $\varepsilon$ infinity distance have runtime boundsthat depend polynomially on $\frac{1}{\varepsilon}$. We bridge this gap bypresenting an algorithm that outputs a point $\varepsilon$-close to $\pi$ ininfinity distance that requires at most $\mathrm{poly}(\log\frac{1}{\varepsilon}, d)$ calls to a membership oracle for $K$ and evaluationoracle for $f$, when $f$ is Lipschitz. Our approach departs from prior worksthat construct Markov chains on a $\frac{1}{\varepsilon^2}$-discretization of$K$ to achieve a sample with $\varepsilon$ infinity-distance error, and presenta method to directly convert continuous samples from $K$ with total-variationbounds to samples with infinity bounds. This approach also allows us to obtainan improvement on the dimension $d$ in the running time for the problem ofsampling from a log-concave distribution on polytopes $K$ with infinitydistance $\varepsilon$, by plugging in TV-distance running time bounds for theDikin Walk Markov chain.

Sampling from Log-Concave Distributions with Infinity-Distance Guarantees