論文の概要: A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers
- arxiv url: http://arxiv.org/abs/2405.16736v1
- Date: Mon, 27 May 2024 01:04:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-28 19:25:57.292804
- Title: A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers
- Title（参考訳）: 重り付きサンプリングの分離:近位サンプリングのためのガウス対安定オラクル
- Authors: Ye He, Alireza Mousavi-Hosseini, Krishnakumar Balasubramanian, Murat A. Erdogdu,
- Abstract要約: 重み付きサンプリングの複雑さについて検討し,高い精度と低い精度の保証を得るという観点から分離結果を示す。
本研究は,ガウス神託に基づく近位サンプリング器が,重尾ターゲット群からのサンプリングにおいて,必ずしも低精度保証しか達成できないという根本的な障壁があることを示唆する。
対照的に、安定オラクルに基づく近位サンプリング器は高い精度の保証を示し、上記の制限を克服する。
- 参考スコア（独自算出の注目度）: 27.09810365086649
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the complexity of heavy-tailed sampling and present a separation result in terms of obtaining high-accuracy versus low-accuracy guarantees i.e., samplers that require only $O(\log(1/\varepsilon))$ versus $\Omega(\text{poly}(1/\varepsilon))$ iterations to output a sample which is $\varepsilon$-close to the target in $\chi^2$-divergence. Our results are presented for proximal samplers that are based on Gaussian versus stable oracles. We show that proximal samplers based on the Gaussian oracle have a fundamental barrier in that they necessarily achieve only low-accuracy guarantees when sampling from a class of heavy-tailed targets. In contrast, proximal samplers based on the stable oracle exhibit high-accuracy guarantees, thereby overcoming the aforementioned limitation. We also prove lower bounds for samplers under the stable oracle and show that our upper bounds cannot be fundamentally improved.
- Abstract（参考訳）: 重み付きサンプリングの複雑さについて検討し、高い精度と低い精度の保証を得るための分離結果を示す。すなわち、$O(\log(1/\varepsilon)$と$Omega(\text{poly}(1/\varepsilon))$と$Omega(\text{poly}(1/\varepsilon))$と$Omega(\text{poly}(1/\varepsilon))$だけを必要とするサンプルを目標に対して$\varepsilon$-closeで出力する。
本研究の結果はガウス対安定オラクルに基づく近位サンプルに適用された。
本研究は,ガウス神託に基づく近位サンプリング器が,重尾ターゲット群からのサンプリングにおいて,必ずしも低精度保証しか達成できないという根本的な障壁があることを示唆する。
対照的に、安定オラクルに基づく近位サンプリング器は高い精度の保証を示し、上記の制限を克服する。
また、安定なオラクルの下でのサンプル値の低い境界を証明し、上界が根本的に改善できないことを示す。
関連論文リスト
- Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。
対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。
我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
論文 参考訳（メタデータ） (2024-05-27T00:53:18Z) - Log-Concave Sampling on Compact Supports: A Versatile Proximal Framework [6.555157647688725]
本稿では,凸およびコンパクトな支持体上に定義された強対数凹分布のサンプリングについて検討する。
本稿では,制約セットへの射影を包含する一般近位フレームワークを提案する。
本分析は,制約サンプリングの文脈におけるLangevin型サンプリングアルゴリズムに着目した。
論文 参考訳（メタデータ） (2024-05-24T09:24:21Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - Improved analysis for a proximal algorithm for sampling [21.21963121603413]
We study the proximal sampler of Lee, Shen, and Tian (2021) and obtain new convergence guarantees under weaker assumptions than strong log-concavity。
その結果,(1) 対数対数対数対数,(2) 非対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数
論文 参考訳（メタデータ） (2022-02-13T19:04:28Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - 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) - Revisiting the Sample Complexity of Sparse Spectrum Approximation of
Gaussian Processes [60.479499225746295]
本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。
我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
論文 参考訳（メタデータ） (2020-11-17T05:41:50Z) - Composite Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
dpi(x) propto exp(-f(x) - g(x)dx)$ for well-conditioned $f$ and convex (しかし、おそらくは非滑らか) $g$ である。
for $f$ with condition number $kappa$, our algorithm run in $O left(kappa2 d log2tfrackappa depsilonright)$, each querying a gradient of $f$
論文 参考訳（メタデータ） (2020-06-10T17:43:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。