論文の概要: Convergence Rates for Stochastic Approximation on a Boundary

• arxiv url: http://arxiv.org/abs/2208.07243v2
• Date: Thu, 18 Aug 2022 09:03:46 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-19 11:20:22.981950
• Title: Convergence Rates for Stochastic Approximation on a Boundary
• Title（参考訳）: 境界上の確率近似に対する収束率
• Authors: Kody Law and Neil Walton and Shangda Yang
• Abstract要約: 本研究では,制約セットの境界に最適な場合に着目した投影勾配勾配勾配の挙動を解析する。 この結果が線形プログラミングや強化学習にどのように当てはまるかを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze the behavior of projected stochastic gradient descent focusing on the case where the optimum is on the boundary of the constraint set and the gradient does not vanish at the optimum. Here iterates may in expectation make progress against the objective at each step. When this and an appropriate moment condition on noise holds, we prove that the convergence rate to the optimum of the constrained stochastic gradient descent will be different and typically be faster than the unconstrained stochastic gradient descent algorithm. Our results argue that the concentration around the optimum is exponentially distributed rather than normally distributed, which typically determines the limiting convergence in the unconstrained case. The methods that we develop rely on a geometric ergodicity proof. This extends a result on Markov chains by Hajek (1982) to the area of stochastic approximation algorithms. As examples, we show how the results apply to linear programming and tabular reinforcement learning.
• Abstract（参考訳）: 我々は、制約セットの境界に最適が配置され、最適に勾配が消えない場合に焦点をあてた確率勾配勾配の挙動を解析する。 ここでは、各ステップで目的に対して進捗を期待する。 これと雑音に対する適切なモーメント条件が成立すると、制約付き確率勾配勾配の最適値への収束速度は、制約なし確率勾配勾配のアルゴリズムと異なり、典型的には高速であることを示す。 その結果, 最適値周辺の濃度は通常分布するよりも指数関数的に分布し, 非拘束の場合の限界収束を決定する。 私たちが開発する手法は幾何学的エルゴディディティ証明に依存している。 これはHajek (1982) によるマルコフ連鎖上の結果を確率近似アルゴリズムの領域にまで拡張する。 例えば、結果は線形プログラミングや表型強化学習にどのように適用されるかを示す。

関連論文リスト

• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Generalization in Supervised Learning Through Riemannian Contraction [4.3604518673788135]
  教師付き学習環境では、計量 0 がアセシアンレート $lambda で収縮している場合、それは一様に$math であることを示す。 結果は、連続および安定な $-time において、勾配と決定論的損失曲面を保っている。 それらは、Descent$凸面や強い凸損失面など、ある種の線形な設定で最適であることを示すことができる。
  論文  参考訳（メタデータ） (2022-01-17T23:08:47Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Convergence of Gradient Algorithms for Nonconvex $C^{1+\alpha}$ Cost Functions [2.538209532048867]
  勾配が収束する副生成物を示し、収束率に明示的な上限を与える。 これにより、ドオブマルティンの超ガレ収束定理によるほぼ確実な収束を証明できる。
  論文  参考訳（メタデータ） (2020-12-01T16:48:59Z)
• Asymptotic Analysis of Conditioned Stochastic Gradient Descent [0.0]
  本研究では、勾配方向の事前条件付けに基づいて、条件付きSGDと呼ばれる勾配降下法(SGD)アルゴリズムのクラスについて検討する。 条件行列が逆 Hessian の推定値である場合、アルゴリズムは概して最適であることが証明される。
  論文  参考訳（メタデータ） (2020-06-04T10:08:05Z)
• Non-asymptotic bounds for stochastic optimization with biased noisy gradient oracles [8.655294504286635]
  関数の測定値が推定誤差を持つ設定を捉えるために,バイアス付き勾配オラクルを導入する。 提案するオラクルは,例えば,独立分散シミュレーションと同一分散シミュレーションのバッチによるリスク計測推定の実践的な状況にある。
  論文  参考訳（メタデータ） (2020-02-26T12:53:04Z)

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

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