論文の概要: Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms

• arxiv url: http://arxiv.org/abs/2002.00291v3
• Date: Sat, 3 Jul 2021 04:12:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-05 00:45:21.523565
• Title: Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms
• Title（参考訳）: オラクルの確率的勾配サンプリングアルゴリズムの下限
• Authors: Niladri S. Chatterji, Peter L. Bartlett, Philip M. Long
• Abstract要約: 我々は、$bbRd$の強い対数凹密度からサンプリングする問題を考察する。 必要なログ密度の勾配クエリ数に基づいて,情報理論の下界を証明した。
• 参考スコア（独自算出の注目度）: 39.746670539407084
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of sampling from a strongly log-concave density in $\mathbb{R}^d$, and prove an information theoretic lower bound on the number of stochastic gradient queries of the log density needed. Several popular sampling algorithms (including many Markov chain Monte Carlo methods) operate by using stochastic gradients of the log density to generate a sample; our results establish an information theoretic limit for all these algorithms. We show that for every algorithm, there exists a well-conditioned strongly log-concave target density for which the distribution of points generated by the algorithm would be at least $\varepsilon$ away from the target in total variation distance if the number of gradient queries is less than $\Omega(\sigma^2 d/\varepsilon^2)$, where $\sigma^2 d$ is the variance of the stochastic gradient. Our lower bound follows by combining the ideas of Le Cam deficiency routinely used in the comparison of statistical experiments along with standard information theoretic tools used in lower bounding Bayes risk functions. To the best of our knowledge our results provide the first nontrivial dimension-dependent lower bound for this problem.
• Abstract（参考訳）: 我々は,$\mathbb{r}^d$ の強い対数対数密度からサンプリングする問題を考察し,必要な対数密度の確率的勾配クエリ数に対する情報理論的下限を証明した。 いくつかの一般的なサンプリングアルゴリズム(多くのマルコフ連鎖モンテカルロ法を含む)は、ログ密度の確率的勾配を用いてサンプルを生成する。 各アルゴリズムに対して、勾配クエリ数が$\omega(\sigma^2 d/\varepsilon^2)$ 以下であれば、アルゴリズムが生成する点の分布が最大変動距離で少なくとも$\varepsilon$を目標から離すような、十分条件の強いlog-concaveターゲット密度が存在することを示し、ここで$\sigma^2 d$ は確率勾配の分散である。 下限は,統計的実験で日常的に使用されるle cam欠損の考え方と,下限ベイズリスク関数で使用される標準情報理論ツールを組み合わせたものである。 我々の知る限り、我々の結果はこの問題に対する最初の非自明な次元依存下界を与える。

関連論文リスト

• Generalization Bounds for Label Noise Stochastic Gradient Descent [0.0]
  非測定条件でのラベルノイズを伴う勾配降下(SGD)の一般化誤差境界について検討する。 我々の分析はラベルノイズの影響についての洞察を与える。
  論文  参考訳（メタデータ） (2023-11-01T03:51:46Z)
• Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
  グラディエントDescent(SGD)のための量子クリッピング戦略を導入する。 通常のクリッピングチェーンとして、グラデーション・ニュー・アウトリージを使用します。 本稿では,Huberiles を用いたアルゴリズムの実装を提案する。
  論文  参考訳（メタデータ） (2023-09-29T15:24:48Z)
• Sobolev Space Regularised Pre Density Models [51.558848491038916]
  本研究では,ソボレフ法則の正則化に基づく非パラメトリック密度推定法を提案する。 この方法は統計的に一貫したものであり、帰納的検証モデルを明確かつ一貫したものにしている。
  論文  参考訳（メタデータ） (2023-07-25T18:47:53Z)
• Kinetic Langevin MCMC Sampling Without Gradient Lipschitz Continuity -- the Strongly Convex Case [0.0]
  目的がグローバルリプシッツであると仮定することなく,ハミルトン条件下での対数凹面分布からのサンプリングを検討する。 本稿では,多角勾配(テード)オイラースキームに基づく2つのアルゴリズムを提案し,各アルゴリズムのプロセスの法則と対象測度との間の非漸近的な2-ワッサーシュタイン距離を求める。
  論文  参考訳（メタデータ） (2023-01-19T12:32:41Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning [0.0]
  ランジュバンアルゴリズムは付加ノイズを持つ手法である。 ランジュバンアルゴリズムは何十年もチェーンカルロ(ミロン)で使われてきた 学習にとって、それはそれがそれが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それがそれが事実であるということであり、それがそれがそれが事実であるということであるということであるということが、それが事実であるということであるということが、それが事実であるということであることを示している。
  論文  参考訳（メタデータ） (2020-12-22T16:19:20Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。 我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
  論文  参考訳（メタデータ） (2020-10-19T15:23:18Z)
• Carath\'eodory Sampling for Stochastic Gradient Descent [79.55586575988292]
  本稿では,Tchakaloff と Carath'eodory の古典的な結果から着想を得た手法を提案する。 我々は、測定値の低減を行う降下ステップを適応的に選択する。 これをBlock Coordinate Descentと組み合わせることで、測定の削減を極めて安価に行えるようにします。
  論文  参考訳（メタデータ） (2020-06-02T17:52:59Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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