論文の概要: Convergence of Momentum-Based Heavy Ball Method with Batch Updating
and/or Approximate Gradients
- arxiv url: http://arxiv.org/abs/2303.16241v2
- Date: Sat, 10 Jun 2023 16:26:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-14 00:43:06.643703
- Title: Convergence of Momentum-Based Heavy Ball Method with Batch Updating
and/or Approximate Gradients
- Title（参考訳）: Batch Updating および/または Approximate Gradients を用いたモーメントベースヘビーボール法の収束性
- Authors: Tadipatri Uday Kiran Reddy and Mathukumalli Vidyasagar
- Abstract要約: 我々は1964年にPolyakによって導入された凸と非最適化のためのよく知られた「ヘビーボール」法を確立した。
我々はこの論文を記憶における「バッチ更新」と呼んでいる。
目的関数の定常点への反復のほぼ確実な収束を適切な条件下で確立する。
- 参考スコア（独自算出の注目度）: 1.9544213396776275
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study the well-known "Heavy Ball" method for convex and
nonconvex optimization introduced by Polyak in 1964, and establish its
convergence under a variety of situations. Traditionally, most algorithms use
"full-coordinate update," that is, at each step, every component of the
argument is updated. However, when the dimension of the argument is very high,
it is more efficient to update some but not all components of the argument at
each iteration. We refer to this as "batch updating" in this paper. When
gradient-based algorithms are used together with batch updating, in principle
it is sufficient to compute only those components of the gradient for which the
argument is to be updated. However, if a method such as backpropagation is used
to compute these components, computing only some components of gradient does
not offer much savings over computing the entire gradient. Therefore, to
achieve a noticeable reduction in CPU usage at each step, one can use
first-order differences to approximate the gradient. The resulting estimates
are biased, and also have unbounded variance. Thus some delicate analysis is
required to ensure that the HB algorithm converge when batch updating is used
instead of full-coordinate updating, and/or approximate gradients are used
instead of true gradients. In this paper, we establish the almost sure
convergence of the iterations to the stationary point(s) of the objective
function under suitable conditions; in addition, we also derive upper bounds on
the rate of convergence. To the best of our knowledge, there is no other paper
that combines all of these features. This paper is dedicated to the memory of
Boris Teodorovich Polyak
- Abstract（参考訳）: 本稿では,1964年に polyak が導入した凸および非凸最適化のための有名な "heavy ball" 法について検討し,その収束を様々な状況下で確立する。
従来、ほとんどのアルゴリズムは "full-coordinate update" を使用しており、各ステップで引数のすべてのコンポーネントが更新される。
しかし、引数の次元が非常に高い場合、各イテレーションで引数のすべてのコンポーネントを更新するよりも効率的である。
本論文では,これを"バッチ更新"と呼ぶ。
勾配に基づくアルゴリズムがバッチ更新と共に使用される場合、原則として、引数が更新される勾配のコンポーネントのみを計算するのに十分である。
しかしながら、これらの成分を計算するためにバックプロパゲーションのような方法を使用する場合、勾配のいくつかのコンポーネントしか計算しないため、勾配全体の計算よりも多くの節約が得られない。
したがって、各ステップにおけるCPU使用量の顕著な削減を実現するため、勾配を近似するために一階差を用いることができる。
結果の見積もりは偏りがあり、非有界な分散も持つ。
したがって、完全座標更新の代わりにバッチ更新を使用する場合、hbアルゴリズムが収束することを保証するには、いくつかの微妙な解析が必要であり、真の勾配の代わりに近似勾配を用いる。
本稿では,目的関数の定常点への反復のほぼ確実収束を適切な条件下で定め,また収束率の上界も導出する。
私たちの知る限りでは、これらの機能をすべて組み合わせた論文は他にありません。
この論文はBoris Teodorovich Polyakの記憶に捧げられている。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。