論文の概要: Convergence of Online Adaptive and Recurrent Optimization Algorithms

• arxiv url: http://arxiv.org/abs/2005.05645v2
• Date: Fri, 8 Jan 2021 09:11:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-03 19:43:34.595436
• Title: Convergence of Online Adaptive and Recurrent Optimization Algorithms
• Title（参考訳）: オンライン適応・再帰最適化アルゴリズムの収束
• Authors: Pierre-Yves Mass\'e (CTU), Yann Ollivier (FAIR)
• Abstract要約: 我々は、機械学習で使用されるいくつかの顕著な降下アルゴリズムの局所収束を証明した。 我々は確率的視点ではなく「エルゴディック」を採用し、確率分布の代わりに経験的な時間平均で作業する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove local convergence of several notable gradient descent algorithms used in machine learning, for which standard stochastic gradient descent theory does not apply directly. This includes, first, online algorithms for recurrent models and dynamical systems, such as \emph{Real-time recurrent learning} (RTRL) and its computationally lighter approximations NoBackTrack and UORO; second, several adaptive algorithms such as RMSProp, online natural gradient, and Adam with $\beta^2\to 1$.Despite local convergence being a relatively weak requirement for a new optimization algorithm, no local analysis was available for these algorithms, as far as we knew. Analysis of these algorithms does not immediately follow from standard stochastic gradient (SGD) theory. In fact, Adam has been proved to lack local convergence in some simple situations \citep{j.2018on}. For recurrent models, online algorithms modify the parameter while the model is running, which further complicates the analysis with respect to simple SGD.Local convergence for these various algorithms results from a single, more general set of assumptions, in the setup of learning dynamical systems online. Thus, these results can cover other variants of the algorithms considered.We adopt an "ergodic" rather than probabilistic viewpoint, working with empirical time averages instead of probability distributions. This is more data-agnostic and creates differences with respect to standard SGD theory, especially for the range of possible learning rates. For instance, with cycling or per-epoch reshuffling over a finite dataset instead of pure i.i.d.\ sampling with replacement, empirical averages of gradients converge at rate $1/T$ instead of $1/\sqrt{T}$ (cycling acts as a variance reduction method), theoretically allowing for larger learning rates than in SGD.
• Abstract（参考訳）: 機械学習で使用されるいくつかの顕著な勾配降下アルゴリズムの局所収束を証明し、標準的な確率勾配降下理論は直接適用しない。 これはまず、リカレントモデルと動的システムのためのオンラインアルゴリズム、例えば \emph{Real-time recurrent learning} (RTRL) や計算的に軽量な近似 NoBackTrack や UORO、RMSProp、オンライン自然勾配、および$\beta^2\to 1$のAdamを含む。 局所収束は、新しい最適化アルゴリズムの比較的弱い要件であるにもかかわらず、我々が知る限り、これらのアルゴリズムの局所解析は利用できなかった。 これらのアルゴリズムの分析は、標準確率勾配(SGD)理論からすぐには従わない。 実際、アダムはいくつかの単純な状況において局所収束を欠いていることが証明されている。 オンラインアルゴリズムは、モデルの実行中にパラメータを変更し、単純なSGDに関する解析をさらに複雑化する。これらのアルゴリズムの局所収束は、オンラインの動的システム学習のセットアップにおいて、単一のより一般的な仮定セットから得られる。 このように、これらの結果は考慮されたアルゴリズムの他の変種をカバーすることが可能であり、確率分布の代わりに経験的な時間平均を扱うことにより、確率論的視点ではなく「エルゴディック」を採用する。 これはよりデータに依存しないものであり、標準のSGD理論、特に学習率の範囲において違いを生み出す。 例えば、純粋なi.i.d.\サンプリングではなく有限データセットをサイクリングまたは1回ごとの再シャッフルで置き換えると、経験的な勾配平均は、1/\sqrt{t}$(サイクリングは分散還元法として作用する)の代わりに1/t$で収束し、理論的にはsgdよりも大きな学習率を可能にする。

関連論文リスト

• Online Learning Under A Separable Stochastic Approximation Framework [20.26530917721778]
  分離可能な近似フレームワークを用いて,機械学習モデルのクラスに対するオンライン学習アルゴリズムを提案する。 提案アルゴリズムは,他の一般的な学習アルゴリズムと比較して,より堅牢でテスト性能が高いことを示す。
  論文  参考訳（メタデータ） (2023-05-12T13:53:03Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。 本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
  論文  参考訳（メタデータ） (2020-11-10T11:36:30Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models [2.384873896423002]
  非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。 我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
  論文  参考訳（メタデータ） (2020-03-30T10:43:56Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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