論文の概要: On the query complexity of sampling from non-log-concave distributions
- arxiv url: http://arxiv.org/abs/2502.06200v2
- Date: Wed, 12 Feb 2025 03:10:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-13 13:49:26.604129
- Title: On the query complexity of sampling from non-log-concave distributions
- Title（参考訳）: 非log-concave分布からのサンプリングのクエリ複雑性について
- Authors: Yuchen He, Chihao Zhang,
- Abstract要約: 密度$p(x)propto e-f(x)$を持つ$d$次元分布からサンプリングする問題を、必ずしも良好な等尺条件を満たすとは限らない。
広い範囲のパラメータに対して、サンプリングは$d$の超指数係数による最適化よりも厳密に容易であることを示す。
- 参考スコア（独自算出の注目度）: 2.4253233571593547
- License:
- Abstract: We study the problem of sampling from a $d$-dimensional distribution with density $p(x)\propto e^{-f(x)}$, which does not necessarily satisfy good isoperimetric conditions. Specifically, we show that for any $L,M$ satisfying $LM\ge d\ge 5$, $\epsilon\in \left(0,\frac{1}{32}\right)$, and any algorithm with query accesses to the value of $f(x)$ and $\nabla f(x)$, there exists an $L$-log-smooth distribution with second moment at most $M$ such that the algorithm requires $\left(\frac{LM}{d\epsilon}\right)^{\Omega(d)}$ queries to compute a sample whose distribution is within $\epsilon$ in total variation distance to the target distribution. We complement the lower bound with an algorithm requiring $\left(\frac{LM}{d\epsilon}\right)^{\mathcal O(d)}$ queries, thereby characterizing the tight (up to the constant in the exponent) query complexity for sampling from the family of non-log-concave distributions. Our results are in sharp contrast with the recent work of Huang et al. (COLT'24), where an algorithm with quasi-polynomial query complexity was proposed for sampling from a non-log-concave distribution when $M=\mathtt{poly}(d)$. Their algorithm works under the stronger condition that all distributions along the trajectory of the Ornstein-Uhlenbeck process, starting from the target distribution, are $\mathcal O(1)$-log-smooth. We investigate this condition and prove that it is strictly stronger than requiring the target distribution to be $\mathcal O(1)$-log-smooth. Additionally, we study this condition in the context of mixtures of Gaussians. Finally, we place our results within the broader theme of ``sampling versus optimization'', as studied in Ma et al. (PNAS'19). We show that for a wide range of parameters, sampling is strictly easier than optimization by a super-exponential factor in the dimension $d$.
- Abstract（参考訳）: 密度$p(x)\propto e^{-f(x)}$を持つ$d$次元分布からサンプリングする問題を、必ずしも良好な等尺条件を満たすとは限らない。
具体的には、$L,M$ が $LM\ge d\ge 5$, $\epsilon\in \left(0,\frac{1}{32}\right)$ と、$f(x)$ と $\nabla f(x)$ の値へのクエリアクセスを持つアルゴリズムは、$L$-log-smooth 分布が存在し、そのアルゴリズムは $\left(\frac{LM}{d\epsilon}\right)^{\Omega(d)}$ をターゲット分布に全変動距離で計算する。
下界は$\left(\frac{LM}{d\epsilon}\right)^{\mathcal O(d)}$クエリを必要とするアルゴリズムで補う。
本研究は,Huang et al (COLT'24) の最近の研究と対照的に,$M=\mathtt{poly}(d)$のとき,非log-concave分布からのサンプリングに準ポリノミカルなクエリ複雑性を持つアルゴリズムを提案した。
彼らのアルゴリズムは、オルンシュタイン・ウレンベック過程の軌道に沿った全ての分布がターゲット分布から始まり、$\mathcal O(1)$-log-smoothであるという強い条件の下で機能する。
この条件を検証し、ターゲット分布を$\mathcal O(1)$-log-smooth でなければならないよりも厳密であることを示す。
さらに、この条件をガウスの混合の文脈で研究する。
最後に、この結果について、Ma et al (PNAS'19) で研究した 'sampling vs Optimization' というより広いテーマに配置する。
広い範囲のパラメータに対して、サンプリングは$d$の超指数係数による最適化よりも厳密に容易であることを示す。
関連論文リスト
- 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) - 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) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Perfect Sampling from Pairwise Comparisons [26.396901523831534]
分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。
固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-11-23T11:20:30Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
仮説選択問題に対する最適2ドルの近似学習戦略を導出する。
これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2021-08-17T21:11:20Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。