論文の概要: Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updating

• arxiv url: http://arxiv.org/abs/2303.16241v3
• Date: Sat, 12 Apr 2025 14:51:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-15 16:45:08.592185
• Title: Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updating
• Title（参考訳）: 近似勾配および/またはブロック更新による確率重ボール法の収束性
• Authors: Uday Kiran Reddy Tadipatri, Mathukumalli Vidyasagar,
• Abstract要約: 我々は,より一般的な条件下でのヘビーボール (SHB) アルゴリズムの収束を確立する。 我々の解析は凸関数だけでなく、PL(Polyak-Lojasiewicz)およびKL(Kurdyka-Lojasiewicz)条件を満たすより一般的な関数も受け入れている。
• 参考スコア（独自算出の注目度）: 0.6445605125467572
• License:
• Abstract: In this paper, we establish the convergence of the stochastic Heavy Ball (SHB) algorithm under more general conditions than in the current literature. Specifically, (i) The stochastic gradient is permitted to be biased, and also, to have conditional variance that grows over time (or iteration number). This feature is essential when applying SHB with zeroth-order methods, which use only two function evaluations to approximate the gradient. In contrast, all existing papers assume that the stochastic gradient is unbiased and/or has bounded conditional variance. (ii) The step sizes are permitted to be random, which is essential when applying SHB with block updating. The sufficient conditions for convergence are stochastic analogs of the well-known Robbins-Monro conditions. This is in contrast to existing papers where more restrictive conditions are imposed on the step size sequence. (iii) Our analysis embraces not only convex functions, but also more general functions that satisfy the PL (Polyak-{\L}ojasiewicz) and KL (Kurdyka-{\L}ojasiewicz) conditions. (iv) If the stochastic gradient is unbiased and has bounded variance, and the objective function satisfies (PL), then the iterations of SHB match the known best rates for convex functions. (v) We establish the almost-sure convergence of the iterations, as opposed to convergence in the mean or convergence in probability, which is the case in much of the literature. (vi) Each of the above convergence results continue to hold if full-coordinate updating is replaced by any one of three widely-used updating methods. In addition, numerical computations are carried out to illustrate the above points.
• Abstract（参考訳）: 本稿では,より一般的な条件下での確率重ボール(SHB)アルゴリズムの収束性を確立する。 具体的には (i)確率勾配は偏りを許容し、また時間とともに増加する条件分散(または反復数)を持つ。 この特徴は、勾配を近似するために2つの関数評価のみを使用するゼロ階法でSHBを適用する場合に必須である。 対照的に、既存のすべての論文は確率勾配が不偏あるいは/または有界な条件分散を持つと仮定している。 (ii) ブロック更新にSHBを適用する場合、ステップサイズはランダムであることが許される。 収束の十分な条件は、よく知られたロビンス・モンロ条件の確率的類似である。 これは、ステップサイズシーケンスにより制限的な条件が課される既存の論文とは対照的である。 3) この解析は凸関数だけでなく, PL (Polyak-{\L}ojasiewicz) と KL (Kurdyka-{\L}ojasiewicz) の条件を満たす一般関数も受け入れる。 (4)確率勾配が偏りがなく、有界な分散を持ち、目的関数がPLを満たすならば、SHBの反復は凸関数の既知の最高速度と一致する。 (v)多くの文献において、平均収束や確率収束とは対照的に、反復のほぼ完全収束を確立する。 (vi) 完全コーディネート更新が3つの広く使用されている更新方法のいずれかに置き換わる場合、上記の収束結果は引き続き維持される。 また、上記の点を説明するために数値計算を行った。

関連論文リスト

• An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes [17.804065824245402]
  機械学習の応用では、各損失関数は非負であり、平方根とその実数値平方根の構成として表すことができる。 本稿では, ガウス・ニュートン法やレフスカルト法を適用して, 滑らかだが非負な関数の平均を最小化する方法を示す。
  論文  参考訳（メタデータ） (2024-07-05T08:53:06Z)
• Optimization using Parallel Gradient Evaluations on Multiple Parameters [51.64614793990665]
  本稿では,複数のパラメータからの勾配を勾配降下の各ステップで利用することができる凸最適化の一階法を提案する。 本手法では,複数のパラメータからの勾配を用いて,これらのパラメータを最適方向に更新する。
  論文  参考訳（メタデータ） (2023-02-06T23:39:13Z)
• SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
  我々は、ツリー検索をポリシー勾配に統合する最初のアプローチであるSoftTreeMaxを紹介します。 Atariでは、SoftTreeMaxが分散PPOと比較して、実行時のパフォーマンスを最大5倍向上させる。
  論文  参考訳（メタデータ） (2022-09-28T09:55:47Z)
• Convergence of Batch Stochastic Gradient Descent Methods with Approximate Gradients and/or Noisy Measurements: Theory and Computational Results [0.9900482274337404]
  BSGD(Block Gradient Descent)と呼ばれる非常に一般的な定式化を用いた凸最適化の研究 我々は近似理論に基づいて,BSGDが世界最小値に収束する条件を確立する。 近似勾配を用いると、BSGDは収束し、運動量に基づく手法は分岐できることを示す。
  論文  参考訳（メタデータ） (2022-09-12T16:23:15Z)
• Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
  ガウスのプロセスはデータセットのサイズとともに違法にスケールする。 多くの近似法が開発されており、必然的に近似誤差を導入している。 この余分な不確実性の原因は、計算が限られているため、近似後部を使用すると完全に無視される。 本研究では,観測された有限個のデータと有限個の計算量の両方から生じる組合せ不確実性を一貫した推定を行う手法の開発を行う。
  論文  参考訳（メタデータ） (2022-05-30T22:16:25Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Reparametrizing gradient descent [0.0]
  本稿では,ノルム適応勾配勾配という最適化アルゴリズムを提案する。 我々のアルゴリズムは準ニュートン法と比較することもできるが、定常点ではなく根を求める。
  論文  参考訳（メタデータ） (2020-10-09T20:22:29Z)
• Multi-kernel Passive Stochastic Gradient Algorithms and Transfer Learning [21.796874356469644]
  勾配アルゴリズムはコスト関数のノイズ勾配が評価される位置を制御できない。 このアルゴリズムは高次元問題において著しく優れており、分散還元を取り入れている。
  論文  参考訳（メタデータ） (2020-08-23T11:55:19Z)
• Variance Reduction with Sparse Gradients [82.41780420431205]
  SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。 我々は、新しい空間演算子:ランダムトップk演算子を導入する。 我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
  論文  参考訳（メタデータ） (2020-01-27T08:23:58Z)

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

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