論文の概要: A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithms

• arxiv url: http://arxiv.org/abs/2602.05304v1
• Date: Thu, 05 Feb 2026 04:57:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-06 18:49:08.763507
• Title: A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithms
• Title（参考訳）: SAG, SAGA, IAGアルゴリズムの短時間・統一収束解析
• Authors: Feng Zhu, Robert W. Heath, Aritra Mitra,
• Abstract要約: 我々は,SAGA, IAGの3つのアルゴリズムすべてに適用可能な単一統一解析法を開発した。 これらのアルゴリズムのそれぞれに対して、最初の高確率および非確率境界を提供する。 IAG副生成物について最もよく知られた率を得る。
• 参考スコア（独自算出の注目度）: 4.862625283098196
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic variance-reduced algorithms such as Stochastic Average Gradient (SAG) and SAGA, and their deterministic counterparts like the Incremental Aggregated Gradient (IAG) method, have been extensively studied in large-scale machine learning. Despite their popularity, existing analyses for these algorithms are disparate, relying on different proof techniques tailored to each method. Furthermore, the original proof of SAG is known to be notoriously involved, requiring computer-aided analysis. Focusing on finite-sum optimization with smooth and strongly convex objective functions, our main contribution is to develop a single unified convergence analysis that applies to all three algorithms: SAG, SAGA, and IAG. Our analysis features two key steps: (i) establishing a bound on delays due to stochastic sub-sampling using simple concentration tools, and (ii) carefully designing a novel Lyapunov function that accounts for such delays. The resulting proof is short and modular, providing the first high-probability bounds for SAG and SAGA that can be seamlessly extended to non-convex objectives and Markov sampling. As an immediate byproduct of our new analysis technique, we obtain the best known rates for the IAG algorithm, significantly improving upon prior bounds.
• Abstract（参考訳）: 確率的平均勾配(SAG)やSAGA(SAGA)のような確率的分散還元アルゴリズムや,その決定論的手法であるIAG(Incrmental Aggregated Gradient)法は,大規模機械学習において広く研究されている。 それらの人気にもかかわらず、これらのアルゴリズムの既存の分析は異なっており、それぞれの手法に合わせて異なる証明技術に依存している。 さらに、SAGの元々の証明は、コンピュータ支援分析を必要とすることで悪名高いことが知られている。 SAG, SAGA, IAGの3つのアルゴリズムすべてに適用可能な1つの統合収束解析を開発することが主目的である。 分析には2つの重要なステップがある。 一 簡易集束工具を用いた確率的サブサンプリングによる遅延制限の設定、及び (II)そのような遅延を考慮に入れた新しいリャプノフ関数を慎重に設計する。 結果として得られた証明は短くモジュラーであり、SAGとSAGAが非凸対象にシームレスに拡張できる最初の高確率境界とマルコフサンプリングを提供する。 新しい解析手法の即時副産物として, IAGアルゴリズムの最もよく知られた速度を求め, 先行値の大幅な改善を図った。

関連論文リスト

• Stochastic Average Gradient : A Simple Empirical Investigation [0.0]
  平均勾配 (SAG) は有限個の滑らかな関数の和を最適化する手法である。 SAGは、単純な玩具問題において、他のイテレーションよりも早く収束し、単純な機械学習問題において、他の多くのイテレーションよりも優れたパフォーマンスを発揮する。 また,運動量アルゴリズムとAdamを組み合わせたSAGを提案する。
  論文  参考訳（メタデータ） (2023-07-27T17:34:26Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  本稿では,テクスト幾何学的強単調ゲームに対する新たな収束結果を確立する。 我々のキーとなる結果は、RGDがテクスト幾何学的手法で最終定位線形収束を実現することを示しています。 全体として、ユークリッド設定を超えるゲームに対して、幾何学的に非依存な最終点収束解析を初めて提示する。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning [40.636276521022474]
  近似(英: Approximation、SA)は、初期から信号処理に大きな影響を与えてきた古典的なアルゴリズムである。 本稿では,SAの非確率的・漸進的な視点を信号処理と機械学習のオーディエンスに紹介する。 我々は、様々な穏やかな条件を満たすリャプノフ関数のクラスに基づいて分析フレームワークを構築した。
  論文  参考訳（メタデータ） (2023-02-22T05:00:51Z)
• NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizer [45.47667026025716]
  2つの重要な要素に依存した、新しく、堅牢で、加速された反復を提案する。 NAG-GSと呼ばれる手法の収束と安定性は、まず広範に研究されている。 我々は、NAG-arityが、重量減衰を伴う運動量SGDや機械学習モデルのトレーニングのためのAdamWといった最先端の手法と競合していることを示す。
  論文  参考訳（メタデータ） (2022-09-29T16:54:53Z)
• Stochastic Reweighted Gradient Descent [4.355567556995855]
  SRG(stochastic reweighted gradient)と呼ばれる重要サンプリングに基づくアルゴリズムを提案する。 我々は、提案手法の時間とメモリオーバーヘッドに特に注意を払っています。 我々はこの発見を裏付ける実験結果を示す。
  論文  参考訳（メタデータ） (2021-03-23T04:09:43Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。 本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。 高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-23T01:34:18Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise [23.62008807533706]
  本稿では,Greedy-GQアルゴリズムの最初の有限サンプル解析法を提案する。 本稿では,2つの時間スケール強化学習アルゴリズムの有限サンプル解析を拡張した。
  論文  参考訳（メタデータ） (2020-05-20T16:35:19Z)

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

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