#### 論文の概要: An MCMC Method to Sample from Lattice Distributions

• arxiv url: http://arxiv.org/abs/2101.06453v2
• Date: Tue, 26 Jan 2021 12:23:37 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-28 04:27:21.095248
• Title: An MCMC Method to Sample from Lattice Distributions
• Title（参考訳）: 格子分布からサンプルを得るためのmcmc法
• Authors: Anand Jerry George, Navin Kashyap
• Abstract要約: 我々はMarkov Chain Monte Carloアルゴリズムを導入し、$d$-dimensional lattice $Lambdaでサポートされている確率分布からサンプルを生成する。 提案する分布として$pi$を使用し、適切な目標分布に対するメトロポリス・ハスティングの受け入れ比率を算出する。 • 参考スコア（独自算出の注目度）: 4.4044968357361745 • License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/ • Abstract: We introduce a Markov Chain Monte Carlo (MCMC) algorithm to generate samples from probability distributions supported on a$d$-dimensional lattice$\Lambda = \mathbf{B}\mathbb{Z}^d$, where$\mathbf{B}$is a full-rank matrix. Specifically, we consider lattice distributions$P_\Lambda$in which the probability at a lattice point is proportional to a given probability density function,$f$, evaluated at that point. To generate samples from$P_\Lambda$, it suffices to draw samples from a pull-back measure$P_{\mathbb{Z}^d}$defined on the integer lattice. The probability of an integer lattice point under$P_{\mathbb{Z}^d}$is proportional to the density function$\pi = |\det(\mathbf{B})|f\circ \mathbf{B}$. The algorithm we present in this paper for sampling from$P_{\mathbb{Z}^d}$is based on the Metropolis-Hastings framework. In particular, we use$\pi$as the proposal distribution and calculate the Metropolis-Hastings acceptance ratio for a well-chosen target distribution. We can use any method, denoted by ALG, that ideally draws samples from the probability density$\pi$, to generate a proposed state. The target distribution is a piecewise sigmoidal distribution, chosen such that the coordinate-wise rounding of a sample drawn from the target distribution gives a sample from$P_{\mathbb{Z}^d}$. When ALG is ideal, we show that our algorithm is uniformly ergodic if$-\log(\pi)$satisfies a gradient Lipschitz condition. • Abstract（参考訳）: 我々はMarkov Chain Monte Carlo (MCMC)アルゴリズムを導入し、$d$次元格子$\Lambda = \mathbf{B}\mathbb{Z}^d$でサポートされている確率分布からサンプルを生成する。 特に、格子分布$p_\lambda$を考えると、格子点の確率は与えられた確率密度関数$f$に比例する。 P_\Lambda$からサンプルを生成するには、整数格子上で定義されたプルバック測度$P_{\mathbb{Z}^d}$からサンプルを引き出すだけでよい。 P_{\mathbb{Z}^d}$の整数格子点の確率は、密度関数$\pi = |\det(\mathbf{B})|f\circ \mathbf{B}$に比例する。 The algorithm present in this paper for sample from$P_{\mathbb{Z}^d}$is based on the Metropolis-Hastings framework。 特に,提案分布として$\pi$を用い,高利率の目標分布に対するメトロポリス・ヘイスティングの受容率を計算する。 alg で表される任意の方法で、理想的には確率密度$\pi$からサンプルを引き出して提案状態を生成することができる。 対象分布は、対象分布から引き出されたサンプルの座標方向の丸めが、$P_{\mathbb{Z}^d}$のサンプルを与えるように選択された一方向のシグモダル分布である。 ALGが理想であるとき、我々のアルゴリズムが一様エルゴディックであることを示し、$-\log(\pi)$が勾配リプシッツ条件を満たす。 #### 関連論文リスト • Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332] 誤差を$sqrtvarepsilon k + rho + dO(1)tildeO(n-1/k)$で有界な有限サンプルアルゴリズムを開発する。 我々は、ワッサーシュタインの分布的ロバストな最適化において、次元性の呪いを克服する新しい方法を発見した。 論文 参考訳（メタデータ） (2024-06-10T17:48:36Z) • A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123] 非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。 論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) • Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493] 大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。 この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。 我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。 論文 参考訳（メタデータ） (2023-02-21T17:52:23Z) • Stochastic Approximation Approaches to Group Distributionally Robust Optimization [96.26317627118912] 群分散ロバスト最適化(GDRO) オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。 分布依存収束率を導出できる重み付きGDROの新規な定式化。 論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) • Perfect Sampling from Pairwise Comparisons [26.396901523831534] 分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。 固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。 論文 参考訳（メタデータ） (2022-11-23T11:20:30Z) • Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps [0.0] Hamiltonian Monte Carlo (HMC) は密度$e-f(x)$の高次元分布からサンプリングするマルコフ連鎖アルゴリズムである。 HMCは,$widetildeO(sqrtkappa d1/4 log(1/varepsilon)$グラデーションクエリを用いて,全変動距離で$varepsilon$-closeの分布からサンプリングできることを示す。 論文 参考訳（メタデータ） (2022-09-26T15:29:29Z) • Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585] モノトン活性化に対する$mathbfxmapstosigma(mathbfwcdotmathbfx)$の関数について検討する。 学習者の目標は仮説ベクトル$mathbfw$that$F(mathbbw)=C, epsilon$を高い確率で出力することである。 論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) • Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence [3.9586758145580014] 強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計する。 グラフ$G=(V, E)$に対して、$G$in$widetildeO(lvert Vrvert)$time per sample から一様にランダムに散らばる木を概算する方法を示す。$n$要素の基底集合の$k$のサブセット上の決定的点プロセスに対して、$widetildeO(komega)$time の最初の$widetildeO(nk) の後に、$widetildeO(komega)$ time のサンプルを概算する方法を示す。
論文  参考訳（メタデータ） (2022-04-06T04:11:26Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and \$gamma であることを証明します。
論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)