論文の概要: Last Iterate Convergence of Incremental Methods and Applications in
Continual Learning
- arxiv url: http://arxiv.org/abs/2403.06873v1
- Date: Mon, 11 Mar 2024 16:24:26 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-12 18:15:31.068082
- Title: Last Iterate Convergence of Incremental Methods and Applications in
Continual Learning
- Title（参考訳）: 逐次学習におけるインクリメンタル手法と応用の最後の反復収束
- Authors: Xufeng Cai, Jelena Diakonikolas
- Abstract要約: 連続学習における応用により、漸進的勾配法と漸進的近位法の両方の最後の繰り返しに対する収束保証を得る。
以上の結果から, 段階的手法の繰り返し保証を, 最先端技術と比較して一般化した。
- 参考スコア（独自算出の注目度）: 12.772632966631623
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Incremental gradient methods and incremental proximal methods are a
fundamental class of optimization algorithms used for solving finite sum
problems, broadly studied in the literature. Yet, when it comes to their
convergence guarantees, nonasymptotic (first-order or proximal) oracle
complexity bounds have been obtained fairly recently, almost exclusively
applying to the average iterate. Motivated by applications in continual
learning, we obtain the first convergence guarantees for the last iterate of
both incremental gradient and incremental proximal methods, in general convex
smooth (for both) and convex Lipschitz (for the proximal variants) settings.
Our oracle complexity bounds for the last iterate nearly match (i.e., match up
to a square-root-log or a log factor) the best known oracle complexity bounds
for the average iterate, for both classes of methods. We further obtain
generalizations of our results to weighted averaging of the iterates with
increasing weights, which can be seen as interpolating between the last iterate
and the average iterate guarantees. Additionally, we discuss how our results
can be generalized to variants of studied incremental methods with permuted
ordering of updates. Our results generalize last iterate guarantees for
incremental methods compared to state of the art, as such results were
previously known only for overparameterized linear models, which correspond to
convex quadratic problems with infinitely many solutions.
- Abstract（参考訳）: 増分勾配法と漸進近法は有限和問題を解くために用いられる最適化アルゴリズムの基本クラスであり、文献で広く研究されている。
しかし、収束の保証に関して言えば、一階または近位でないオラクルの複雑性境界は比較的最近まで得られており、概して平均的な反復にのみ適用される。
連続学習の応用に動機づけられ、漸進的勾配法と漸進的近位法の両方の反復法について、一般凸滑らか法と凸リプシッツ法(近位変型法)において、最初の収束保証が得られる。
私たちのoracleの複雑性境界は、メソッドの両クラスにおいて、oracleの複雑さ境界として最もよく知られているもの(つまり、正方形ルートログやログファクタに匹敵する)とほぼ一致します。
さらに,本研究の結果を,最終イテレーションと平均イテレーション保証の補間とみなすことができる重み付きイテレートの加重平均化に一般化する。
さらに,更新の順序を置換した漸進的手法の変種に対して,我々の結果を一般化する方法についても論じる。
これらの結果は, 無限に多くの解を持つ凸二次問題に対応する超パラメータ線形モデルに対してのみ知られていたため, インクリメンタルな手法に対する最後の反復的保証を一般化する。
関連論文リスト
- On the Last-Iterate Convergence of Shuffling Gradient Methods [21.865728815935665]
対象値に関して勾配法をシャッフルする際の最終点収束率を初めて証明する。
我々の結果は、(ほぼ)既存のラストイテレートの下限と一致するか、あるいは、平均的なイテレートの前の最高の上限と同速である。
論文 参考訳（メタデータ） (2024-03-12T15:01:17Z) - Almost-sure convergence of iterates and multipliers in stochastic
sequential quadratic optimization [21.022322975077653]
等式制約付き連続最適化問題の解法が近年注目されている。
収束保証は、ゼロを測定するための勾配の期待値に制限されている。
また,SQPアルゴリズムにより生成した予備値,ラグランジュ測度,ステーション測度に対する新たなほぼ収束保証を証明した。
論文 参考訳（メタデータ） (2023-08-07T16:03:40Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Robust empirical risk minimization via Newton's method [9.797319790710711]
実験的リスク最小化のためのニュートン法の新しい変種について検討した。
目的関数の勾配と Hessian は、ロバストな推定器に置き換えられる。
また,共役勾配法に基づくニュートン方向のロバストな解を求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T18:54:54Z) - Sharp global convergence guarantees for iterative nonconvex
optimization: A Gaussian process perspective [30.524043513721168]
回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。
決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。
我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
論文 参考訳（メタデータ） (2021-09-20T21:48:19Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳（メタデータ） (2020-12-09T20:19:32Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。