論文の概要: Fisher information lower bounds for sampling

• arxiv url: http://arxiv.org/abs/2210.02482v1
• Date: Wed, 5 Oct 2022 18:03:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-07 16:01:46.730185
• Title: Fisher information lower bounds for sampling
• Title（参考訳）: サンプリングのための漁業情報低域化
• Authors: Sinho Chewi, Patrik Gerber, Holden Lee, Chen Lu
• Abstract要約: バラスラマニアンの枠組みの中で、非log-conサンプリングの複雑さの2つの下限を証明した。 第二に、少なくとも小さな境界の状態では、ターゲットのディストリビューションからFI FIを取得するには、$textpoly (1/)$クエリが必要です。
• 参考スコア（独自算出の注目度）: 9.52971726233605
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove two lower bounds for the complexity of non-log-concave sampling within the framework of Balasubramanian et al. (2022), who introduced the use of Fisher information (FI) bounds as a notion of approximate first-order stationarity in sampling. Our first lower bound shows that averaged LMC is optimal for the regime of large FI by reducing the problem of finding stationary points in non-convex optimization to sampling. Our second lower bound shows that in the regime of small FI, obtaining a FI of at most $\varepsilon^2$ from the target distribution requires $\text{poly}(1/\varepsilon)$ queries, which is surprising as it rules out the existence of high-accuracy algorithms (e.g., algorithms using Metropolis-Hastings filters) in this context.
• Abstract（参考訳）: バラシュラマニアンら (2022) のフレームワークにおける非対数サンプリングの複雑さに対する2つの下界を証明し、サンプリングにおける近似一階定常性の概念としてフィッシャー情報(FI)境界を導入した。 第1の下位境界は,非凸最適化における定常点の探索問題を減らし,LMCの平均値が大規模FIの整合性に最適であることを示している。 我々の2番目の下限は、小さなFIの体制において、ターゲット分布から少なくとも$\varepsilon^2$のFIを得るには$\text{poly}(1/\varepsilon)$クエリが必要であることを示している。

関連論文リスト

• High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm [12.405427902037971]
  本稿では,$mathbbRd$の適切な凸部分集合である対象分布から近似サンプリングを行う1次サンプリング法を提案する。 提案手法は,事前条件付きLangevinアルゴリズムの単一ステップで生成したマルコフ連鎖にメトロポリス・ハスティングスフィルタを適用した結果である。
  論文  参考訳（メタデータ） (2024-12-24T23:21:23Z)
• 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)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization [12.794526174053134]
  滑らかな有限サム最小値最適化のための勾配アルゴリズムの収束速度を解析する。 このようなアルゴリズムの多くは、置換のないサンプリングポイントが、置換したサンプリングよりも高速な収束をもたらすことを示している。
  論文  参考訳（メタデータ） (2022-06-07T00:37:37Z)
• 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)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms [39.746670539407084]
  我々は、$bbRd$の強い対数凹密度からサンプリングする問題を考察する。 必要なログ密度の勾配クエリ数に基づいて,情報理論の下界を証明した。
  論文  参考訳（メタデータ） (2020-02-01T23:46:35Z)

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

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