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

• arxiv url: http://arxiv.org/abs/2303.16241v4
• Date: Fri, 25 Apr 2025 05:03:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:51.479496
• 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: http://creativecommons.org/licenses/by/4.0/
• 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)
• On the Last-Iterate Convergence of Shuffling Gradient Methods [21.865728815935665]
  対象値に関して勾配法をシャッフルする際の最終点収束率を初めて証明する。 我々の結果は、(ほぼ)既存のラストイテレートの下限と一致するか、あるいは、平均的なイテレートの前の最高の上限と同速である。
  論文  参考訳（メタデータ） (2024-03-12T15:01:17Z)
• Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
  目的関数 $J(cdot)$ の定常点を求めるグラディエント・Descent (SGD) 法の収束特性について検討した。 この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
  論文  参考訳（メタデータ） (2023-12-05T15:22:39Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。 最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
  論文  参考訳（メタデータ） (2023-06-02T04:21:59Z)
• Optimization using Parallel Gradient Evaluations on Multiple Parameters [51.64614793990665]
  本稿では,複数のパラメータからの勾配を勾配降下の各ステップで利用することができる凸最適化の一階法を提案する。 本手法では,複数のパラメータからの勾配を用いて,これらのパラメータを最適方向に更新する。
  論文  参考訳（メタデータ） (2023-02-06T23:39:13Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• 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)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• 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)
• On Almost Sure Convergence Rates of Stochastic Gradient Methods [11.367487348673793]
  勾配法で得られるほぼ確実な収束速度が、可能な限り最適な収束速度に任意に近づくことを示す。 非客観的関数に対しては、二乗勾配ノルムの重み付き平均がほぼ確実に収束するだけでなく、ほぼ確実に0となることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:30Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Cyclic Coordinate Dual Averaging with Extrapolation [22.234715500748074]
  単調作用素を用いた変分不等式(VI)問題の一般クラスに適用可能な新しいブロック座標法を提案する。 得られた収束境界は、全勾配法の最適収束境界と一致する。 座標ブロックが$m$の場合、我々の境界における勾配リプシッツ定数は、従来のユークリッドのリプシッツ定数と比較して$sqrtm$よりも大きくなることはない。
  論文  参考訳（メタデータ） (2021-02-26T00:28:58Z)
• Convergence of Gradient Algorithms for Nonconvex $C^{1+\alpha}$ Cost Functions [2.538209532048867]
  勾配が収束する副生成物を示し、収束率に明示的な上限を与える。 これにより、ドオブマルティンの超ガレ収束定理によるほぼ確実な収束を証明できる。
  論文  参考訳（メタデータ） (2020-12-01T16:48:59Z)
• 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)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。 一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
  論文  参考訳（メタデータ） (2020-04-09T17:54:18Z)
• Variance Reduction with Sparse Gradients [82.41780420431205]
  SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。 我々は、新しい空間演算子:ランダムトップk演算子を導入する。 我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
  論文  参考訳（メタデータ） (2020-01-27T08:23:58Z)

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

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