论文标题
通过软阈值Dikin Walk从log-concave分布在多面体上进行采样
Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk
论文作者
论文摘要
给定一个有限的polytope $ k \ subseteq \ subseteq \ mathbb {r}^d $由$ m $不等式定义的有限的polytope $ k \ subseteq \ subseteq \ subseteq \ subseteq \ subseteq \ subseteq \ mathbb {r} $的lipschitz或平滑凸功能$ \，f：k \ to \ mathbb {r} $ $ k $。对此问题的兴趣来自其对贝叶斯推论和差异私人学习的应用。我们的主要结果是将Dikin Walk Markov链的概括到这种设置中，最多需要$ O（（（Md + D l^2 r^2）\ times md^{ω-1}）\ log（\ frac {w} w}δ）$ arithmetic操作以从$ uliate $ uliate $ gue $ usue $ upuiriation variriation varriation vartiriation Varriairia niriation Varriatiate $ niriation varriation $ niriation varriation a $ sharm a a $ niriation $ - 这里的$ l $是$ f $的Lipschitz-contant，$ k $包含在半径$ r $的球中，其中包含一个较小的半径$ r $，$ω$是矩阵 - multiplication常数。我们的算法在对上述学习应用程序重要的一系列参数设置的先前工作时间上有所改善。从技术上讲，我们通过添加$ f $ $ f $的“软阈值”正规剂的“软阈值”正规剂偏离了以前的步行，以$ k $的登录级函数为$ k $的对数栏功能，该版本允许我们的dikin Walk版本提议更新，该更新具有$ f $的高大都市接受率，同时又在polytope $ k $ k $ k $ k $ k $ k $中。
Given a Lipschitz or smooth convex function $\, f:K \to \mathbb{R}$ for a bounded polytope $K \subseteq \mathbb{R}^d$ defined by $m$ inequalities, we consider the problem of sampling from the log-concave distribution $π(θ) \propto e^{-f(θ)}$ constrained to $K$. Interest in this problem derives from its applications to Bayesian inference and differentially private learning. Our main result is a generalization of the Dikin walk Markov chain to this setting that requires at most $O((md + d L^2 R^2) \times md^{ω-1}) \log(\frac{w}δ))$ arithmetic operations to sample from $π$ within error $δ>0$ in the total variation distance from a $w$-warm start. Here $L$ is the Lipschitz-constant of $f$, $K$ is contained in a ball of radius $R$ and contains a ball of smaller radius $r$, and $ω$ is the matrix-multiplication constant. Our algorithm improves on the running time of prior works for a range of parameter settings important for the aforementioned learning applications. Technically, we depart from previous Dikin walks by adding a "soft-threshold" regularizer derived from the Lipschitz or smoothness properties of $f$ to the log-barrier function for $K$ that allows our version of the Dikin walk to propose updates that have a high Metropolis acceptance ratio for $f$, while at the same time remaining inside the polytope $K$.
