論文の概要: Information-Theoretic Lower Bounds for Zero-Order Stochastic Gradient Estimation

• arxiv url: http://arxiv.org/abs/2003.13881v2
• Date: Tue, 27 Oct 2020 16:00:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-18 00:11:33.767924
• Title: Information-Theoretic Lower Bounds for Zero-Order Stochastic Gradient Estimation
• Title（参考訳）: ゼロ階確率勾配推定のための情報理論下界
• Authors: Abdulrahman Alabdulkareem and Jean Honorio
• Abstract要約: ゼロ階オラクルモデルにおける任意の多次元滑らか関数の勾配を推定するために必要なサンプル数を解析する。 有界分散オラクルに対する有限差分法は、ゼロ第三高微分を持つ函数に対して$O(d4/3/sqrtT)$を持つことを示す。
• 参考スコア（独自算出の注目度）: 28.776950569604026
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we analyze the necessary number of samples to estimate the gradient of any multidimensional smooth (possibly non-convex) function in a zero-order stochastic oracle model. In this model, an estimator has access to noisy values of the function, in order to produce the estimate of the gradient. We also provide an analysis on the sufficient number of samples for the finite difference method, a classical technique in numerical linear algebra. For $T$ samples and $d$ dimensions, our information-theoretic lower bound is $\Omega(\sqrt{d/T})$. We show that the finite difference method for a bounded-variance oracle has rate $O(d^{4/3}/\sqrt{T})$ for functions with zero third and higher order derivatives. These rates are tight for Gaussian oracles. Thus, the finite difference method is not minimax optimal, and therefore there is space for the development of better gradient estimation methods.
• Abstract（参考訳）: 本稿では,ゼロ階確率オラクルモデルにおける多次元滑らかな(おそらくは非凸)関数の勾配を推定するために必要なサンプル数を分析する。 このモデルでは、推定者は勾配の推定を生成するために関数のノイズ値にアクセスすることができる。 また,数値線形代数における古典的手法である有限差分法について,十分なサンプル数の解析を行う。 T$サンプルと$d$次元の場合、情報理論の下限は$\Omega(\sqrt{d/T})$である。 有界分散オラクルに対する有限差分法は、三階および高階微分が 0 である関数に対して $o(d^{4/3}/\sqrt{t})$ を持つことを示す。 これらの率はガウスのオラクルにとって厳密である。 したがって、有限差分法は最小限最適ではなく、より良い勾配推定法を開発するための空間が存在する。

関連論文リスト

• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。 i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。 その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
  論文  参考訳（メタデータ） (2024-04-18T16:46:08Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。 任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
  論文  参考訳（メタデータ） (2023-01-16T02:57:37Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• Generalization Bounds for Gradient Methods via Discrete and Continuous Prior [8.76346911214414]
  次数$O(frac1n + fracL2nsum_t=1T(gamma_t/varepsilon_t)2)$の新たな高確率一般化境界を示す。 また、あるSGDの変種に対する新しい境界を得ることもできる。
  論文  参考訳（メタデータ） (2022-05-27T07:23:01Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。 我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
  論文  参考訳（メタデータ） (2020-10-19T15:23:18Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model [0.0]
  このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。 特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
  論文  参考訳（メタデータ） (2020-06-15T08:25:50Z)
• Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling [29.600975900977343]
  我々はZOROと呼ばれる新しい$textbfZ$eroth-$textbfO$rder $textbfR$egularized $textbfO$ptimization法を提案する。 基礎となる勾配がイテレートでほぼスパースである場合、ZOROは目的関数を減少させる新しいイテレートを得るために、非常に少数の客観的関数評価を必要とする。
  論文  参考訳（メタデータ） (2020-03-29T11:01:17Z)
• A Sub-sampled Tensor Method for Non-convex Optimization [0.0]
  有限サム構造を持つ滑らかで潜在的に有意な関数の局所最小値を求めるために, 4階正則化モデルを用いる手法を提案する。
  論文  参考訳（メタデータ） (2019-11-23T13:46:39Z)

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

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