論文の概要: Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence

• arxiv url: http://arxiv.org/abs/2204.02570v1
• Date: Wed, 6 Apr 2022 04:11:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-07 14:18:49.201161
• Title: Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
• Title（参考訳）: 平均ケースエントロピー独立性によるスパンディングツリーの最適部分線形サンプリングと行列点過程
• Authors: Nima Anari, Yang P. Liu, Thuy-Duong Vuong
• Abstract要約: 強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計する。 グラフ $G=(V, E)$ に対して、$G$ in $widetildeO(lvert Vrvert)$ time per sample から一様にランダムに散らばる木を概算する方法を示す。 $n$要素の基底集合の$k$のサブセット上の決定的点プロセスに対して、$widetildeO(komega)$ time の最初の $widetildeO(nk) の後に、$widetildeO(komega)$ time のサンプルを概算する方法を示す。
• 参考スコア（独自算出の注目度）: 3.9586758145580014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We design fast algorithms for repeatedly sampling from strongly Rayleigh distributions, which include random spanning tree distributions and determinantal point processes. For a graph $G=(V, E)$, we show how to approximately sample uniformly random spanning trees from $G$ in $\widetilde{O}(\lvert V\rvert)$ time per sample after an initial $\widetilde{O}(\lvert E\rvert)$ time preprocessing. For a determinantal point process on subsets of size $k$ of a ground set of $n$ elements, we show how to approximately sample in $\widetilde{O}(k^\omega)$ time after an initial $\widetilde{O}(nk^{\omega-1})$ time preprocessing, where $\omega<2.372864$ is the matrix multiplication exponent. We even improve the state of the art for obtaining a single sample from determinantal point processes, from the prior runtime of $\widetilde{O}(\min\{nk^2, n^\omega\})$ to $\widetilde{O}(nk^{\omega-1})$. In our main technical result, we achieve the optimal limit on domain sparsification for strongly Rayleigh distributions. In domain sparsification, sampling from a distribution $\mu$ on $\binom{[n]}{k}$ is reduced to sampling from related distributions on $\binom{[t]}{k}$ for $t\ll n$. We show that for strongly Rayleigh distributions, we can can achieve the optimal $t=\widetilde{O}(k)$. Our reduction involves sampling from $\widetilde{O}(1)$ domain-sparsified distributions, all of which can be produced efficiently assuming convenient access to approximate overestimates for marginals of $\mu$. Having access to marginals is analogous to having access to the mean and covariance of a continuous distribution, or knowing "isotropy" for the distribution, the key assumption behind the Kannan-Lov\'asz-Simonovits (KLS) conjecture and optimal samplers based on it. We view our result as a moral analog of the KLS conjecture and its consequences for sampling, for discrete strongly Rayleigh measures.
• Abstract（参考訳）: 我々は,ランダムスパンディングツリー分布と行列点過程を含む強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計した。 グラフ $G=(V, E)$ に対して、$G$ in $\widetilde{O}(\lvert V\rvert)$ サンプル当たりの時間と初期 $\widetilde{O}(\lvert E\rvert)$ 時間前処理の後に、一様にランダムに散らばる木を概算する方法を示す。 n$ 要素の基底集合の $k$ の部分集合上の決定論的点過程に対して、最初の $\widetilde{o}(nk^{\omega-1})$ 時間前処理の後に $\widetilde{o}(k^\omega)$ で概ねサンプルする方法を示し、ここで $\omega<2.372864$ を行列乗算指数とする。 行列点過程から1つのサンプルを得るための art の状態を、以前の $\widetilde{o}(\min\{nk^2, n^\omega\})$ から $\widetilde{o}(nk^{\omega-1})$ まで改善する。 主な技術的結果として、強いレイリー分布に対する領域スペーシフィケーションの最適限界が達成される。 ドメインスペーシングでは、$\mu$ on $\binom{[n]}{k}$からのサンプリングは、$\binom{[t]}{k}$ for $t\ll n$の関連するディストリビューションからのサンプリングに還元される。 強いレイリー分布に対して、最適な $t=\widetilde{O}(k)$ が得られることを示す。 我々の削減には、$\widetilde{O}(1)$の領域分離分布のサンプリングが伴う。 境界点へのアクセスは、連続分布の平均と共分散にアクセスすることや、分布の「異方性」を知ることと似ており、カンナン・ロフ・アシュ・シモノヴィッツ(KLS)予想とそれに基づく最適なサンプリング器の背景にある重要な仮定である。 我々は, 離散的強レイリー測度に対するkls予想とそのサンプリング結果のモラル類似性として, 本結果を考察する。

関連論文リスト

• On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
  密度$p(x)propto e-f(x)$を持つ$d$次元分布からサンプリングする問題を、必ずしも良好な等尺条件を満たすとは限らない。 広い範囲のパラメータに対して、サンプリングは$d$の超指数係数による最適化よりも厳密に容易であることを示す。
  論文  参考訳（メタデータ） (2025-02-10T06:54:16Z)
• On the sampling complexity of coherent superpositions [0.4972323953932129]
  重ね合わせにPOVMを適用する際に測定結果の分布からサンプリングする問題を考察する。 我々は、$-$$$$O(chi |c|2 log1/delta)$そのようなサンプルを与えられたアルゴリズムを与え、確率密度関数を評価するためにオラクルを呼び出す。
  論文  参考訳（メタデータ） (2025-01-28T16:56:49Z)
• Polynomial time sampling from log-smooth distributions in fixed dimension under semi-log-concavity of the forward diffusion with application to strongly dissipative distributions [9.48556659249574]
  固定次元の複雑なサンプリングアルゴリズムを提案する。 我々は,提案アルゴリズムが予測される$epsilon$誤差を$KL$ばらつきで達成することを証明する。 応用として、$L$-log-smooth分布からサンプリングする問題に対する指数関数的複雑性の改善を導出する。
  論文  参考訳（メタデータ） (2024-12-31T17:51:39Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。 これは密度推定のための新しい統計計算トレードオフである。
  論文  参考訳（メタデータ） (2024-10-30T15:03:33Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
  大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。 この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。 我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
  論文  参考訳（メタデータ） (2023-02-21T17:52:23Z)
• 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)
• Perfect Sampling from Pairwise Comparisons [26.396901523831534]
  分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。 固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-11-23T11:20:30Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。 本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。 スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
  論文  参考訳（メタデータ） (2020-11-21T01:33:15Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。