論文の概要: Faster Sampling from Log-Concave Distributions over Polytopes via a
Soft-Threshold Dikin Walk
- arxiv url: http://arxiv.org/abs/2206.09384v1
- Date: Sun, 19 Jun 2022 11:33:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-22 15:21:37.500208
- Title: Faster Sampling from Log-Concave Distributions over Polytopes via a
Soft-Threshold Dikin Walk
- Title（参考訳）: 軟弱ダイキンウォークによるポリトープ上の対数凹分布からの高速サンプリング
- Authors: Oren Mangoubi, Nisheeth K. Vishnoi
- Abstract要約: 我々は、$d$-dimensional log-concave distribution $pi(theta) propto e-f(theta)$からポリトープ$K$に制約された$m$不等式をサンプリングする問題を考える。
我々の主な成果は、少なくとも$O((md + d L2 R2) times MDomega-1) log(fracwdelta)$ arithmetic operation to sample from $pi$ の "soft-warm' variant of the Dikin walk Markov chain" である。
- 参考スコア（独自算出の注目度）: 28.431572772564518
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of sampling from a $d$-dimensional log-concave
distribution $\pi(\theta) \propto e^{-f(\theta)}$ constrained to a polytope $K$
defined by $m$ inequalities. Our main result is a "soft-threshold'' variant of
the Dikin walk Markov chain that requires at most $O((md + d L^2 R^2) \times
md^{\omega-1}) \log(\frac{w}{\delta}))$ arithmetic operations to sample from
$\pi$ within error $\delta>0$ in the total variation distance from a $w$-warm
start, where $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 $\omega$ is the
matrix-multiplication constant. When a warm start is not available, it implies
an improvement of $\tilde{O}(d^{3.5-\omega})$ arithmetic operations on the
previous best bound for sampling from $\pi$ within total variation error
$\delta$, which was obtained with the hit-and-run algorithm, in the setting
where $K$ is a polytope given by $m=O(d)$ inequalities and $LR = O(\sqrt{d})$.
When a warm start is available, our algorithm improves by a factor of $d^2$
arithmetic operations on the best previous bound in this setting, which was
obtained for a different version of the Dikin walk algorithm. Plugging our
Dikin walk Markov chain into the post-processing algorithm of Mangoubi and
Vishnoi (2021), we achieve further improvements in the dependence of the
running time for the problem of generating samples from $\pi$ with infinity
distance bounds in the special case when $K$ is a polytope.
- Abstract（参考訳）: 我々は、$m$不等式で定義されるポリトープ $k$ に制約された$d$-次元対数分布 $\pi(\theta) \propto e^{-f(\theta)} からサンプリングする問題を考える。
我々の主な成果はダイキン・ウォーク・マルコフ・チェーンの「ソフトスレッショルド」変種であり、最大$O((md + d L^2 R^2) \times md^{\omega-1}) \log(\frac{w}{\delta})$算術演算により、$\pi$ in error $\delta>0$から$w$-warm startまでの総変量距離、$L$は$f$のリプシッツ・コンスタント、$K$は半径$R$のボールに含まれ、$\omega$は小半径$r$のボールを含み、$\omega$は行列乗算定数である。
ウォームスタートが利用できない場合、$k$が$m=o(d)$不等式と$lr = o(\sqrt{d})$で与えられるポリトープである設定において、全変動誤差で$\pi$からサンプリングするための最善の条件で$\tilde{o}(d^{3.5-\omega})$演算が改善されることを意味する。
ウォームスタートが利用可能になった場合、この設定において、このアルゴリズムは、ディキンウォークアルゴリズムの異なるバージョンで得られた最も前の最良境界における$d^2$算術演算によって改善される。
ダイキンウォークマルコフ連鎖をmangoubi と vishnoi の処理後アルゴリズムに差し込む(2021年)ことで、k$ がポリトープである特別な場合において、$\pi$ から無限距離境界を持つサンプルを生成する問題に対する実行時間の依存性がさらに改善される。
関連論文リスト
- Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。
目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
論文 参考訳（メタデータ） (2024-03-14T15:04:45Z) - Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space [10.292118864147097]
ワッサーシュタイン空間上の有限次元多面体部分集合の理論を開発し、一階法による函数の最適化を行う。
我々の主な応用は平均場変動推論の問題であり、これは分布の$pi$ over $mathbbRd$を製品測度$pistar$で近似しようとするものである。
論文 参考訳（メタデータ） (2023-12-05T16:02:04Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文 参考訳（メタデータ） (2021-11-07T13:44:50Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。
これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
論文 参考訳（メタデータ） (2020-04-13T08:06:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。