論文の概要: Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods

• arxiv url: http://arxiv.org/abs/2302.11962v4
• Date: Thu, 5 Sep 2024 13:42:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-07 07:10:38.199880
• Title: Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods
• Title（参考訳）: 確率および分散誘導立方体ニュートン法の統一収束理論
• Authors: El Mahdi Chayti, Nikita Doikov, Martin Jaggi,
• Abstract要約: 我々はヘルパーフレームワークと呼ばれる新しいフレームワークを提案する。 グローバルな複雑性保証を備えた分散アルゴリズムと二階アルゴリズムの統一的なビューを提供する。
• 参考スコア（独自算出の注目度）: 37.1630298053787
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study stochastic Cubic Newton methods for solving general possibly non-convex minimization problems. We propose a new framework, which we call the helper framework, that provides a unified view of the stochastic and variance-reduced second-order algorithms equipped with global complexity guarantees. It can also be applied to learning with auxiliary information. Our helper framework offers the algorithm designer high flexibility for constructing and analyzing the stochastic Cubic Newton methods, allowing arbitrary size batches, and the use of noisy and possibly biased estimates of the gradients and Hessians, incorporating both the variance reduction and the lazy Hessian updates. We recover the best-known complexities for the stochastic and variance-reduced Cubic Newton, under weak assumptions on the noise. A direct consequence of our theory is the new lazy stochastic second-order method, which significantly improves the arithmetic complexity for large dimension problems. We also establish complexity bounds for the classes of gradient-dominated objectives, that include convex and strongly convex problems. For Auxiliary Learning, we show that using a helper (auxiliary function) can outperform training alone if a given similarity measure is small.
• Abstract（参考訳）: 一般の非凸最小化問題を解くための確率的立方ニュートン法について検討する。 我々は,大域的な複雑性保証を備えた確率的・分散還元2次アルゴリズムの統一的なビューを提供するヘルパフレームワークを,ヘルパフレームワークと呼ぶ新しいフレームワークを提案する。 補助情報による学習にも応用できる。 我々のヘルパーフレームワークは、確率的キュービックニュートン法の構築と解析に高い柔軟性を提供し、任意の大きさのバッチを可能にし、勾配とヘッセンの雑音や偏りのある推定値を使用することで、分散の低減と遅延ヘッセンの更新の両方を取り入れている。 我々は雑音の弱い仮定の下で確率的および分散還元されたキュービックニュートンの最もよく知られた複雑さを回復する。 我々の理論の直接の結果は、大きな次元問題に対する算術的複雑性を大幅に改善する新しい遅延確率的二階法である。 また、凸問題や強凸問題を含む勾配支配対象のクラスに対する複雑性境界も確立する。 Auxiliary Learningでは、与えられた類似度が小さい場合、ヘルパー(補助関数)を使用することで、単独でのトレーニングより優れることを示す。

関連論文リスト

• Improving Stochastic Cubic Newton with Momentum [37.1630298053787]
  モーメントが推定値の分散を確実に安定化させることを示す。 グローバリゼーション手法を用いて収束点を証明した。 また、運動量を持つ凸ニュートン法を示す。
  論文  参考訳（メタデータ） (2024-10-25T15:49:16Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches [22.925108493465363]
  本稿では,二階法の利点をすべて享受する有限サム最小化アルゴリズムを提案する。 本稿では,SVRNが最小二乗解法(Subsampled Newtonなど)や反復最小二乗解法を高速化できることを示す。
  論文  参考訳（メタデータ） (2022-06-06T16:00:18Z)
• A framework for bilevel optimization that enables stochastic and global variance reduction algorithms [17.12280360174073]
  双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。 本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。 我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
  論文  参考訳（メタデータ） (2022-01-31T18:17:25Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems [71.60601421935844]
  多くの機械学習問題は、GAN(Generative Adversarial Networks)のようなミニマックス問題として定式化できる。 ミニマックス問題に対するトレーニング勾配法から例を包括的に一般化解析する。
  論文  参考訳（メタデータ） (2021-05-08T22:38:00Z)
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems [26.24895953952318]
  我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。 また、単一または2つのミニバッチ誘導体でも機能する。
  論文  参考訳（メタデータ） (2020-06-27T03:05:18Z)

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

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