論文の概要: 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で出力する。
本研究の結果はガウス対安定オラクルに基づく近位サンプルに適用された。
本研究は,ガウス神託に基づく近位サンプリング器が,重尾ターゲット群からのサンプリングにおいて,必ずしも低精度保証しか達成できないという根本的な障壁があることを示唆する。
対照的に、安定オラクルに基づく近位サンプリング器は高い精度の保証を示し、上記の制限を克服する。
また、安定なオラクルの下でのサンプル値の低い境界を証明し、上界が根本的に改善できないことを示す。
関連論文リスト
- Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
静止測度から少数のサンプルを与えられたマルコフ連鎖を用いて多重モーダル分布をサンプリングする問題を考察する。
マルコフ連鎖が$k$dのスペクトルギャップを持つ場合、静止分布からのサンプルは、静止測度からテレビ距離において$varepsilon$-closeの条件法則を持つサンプルを効率よく生成する。
論文 参考訳（メタデータ） (2024-11-14T01:37:02Z) - Controllable Generation via Locally Constrained Resampling [77.48624621592523]
本研究では, ベイズ条件付けを行い, 制約条件下でサンプルを描画する, トラクタブルな確率的手法を提案する。
提案手法はシーケンス全体を考慮し,現行のグリード法よりも大域的に最適に制約された生成を導出する。
提案手法は, 有害な世代からモデル出力を分離し, 脱毒化に対する同様のアプローチより優れていることを示す。
論文 参考訳（メタデータ） (2024-10-17T00:49:53Z) - 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) - Mini-batch Submodular Maximization [5.439020425819001]
単調デコンポーザブルな部分モジュラ関数,$F=sum_i=1N fi$ を制約の下で最大化する,最初のミニバッチアルゴリズムを提案する。
我々は、一様と重み付けの2つのサンプリング手法を検討する。
意外なことに, 実験結果から, 均一サンプリングは加重サンプリングよりも優れていることが示された。
論文 参考訳（メタデータ） (2024-01-23T04:16:58Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。