論文の概要: MGDA Converges under Generalized Smoothness, Provably
- arxiv url: http://arxiv.org/abs/2405.19440v4
- Date: Wed, 02 Oct 2024 18:51:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-05 03:34:35.696468
- Title: MGDA Converges under Generalized Smoothness, Provably
- Title(参考訳): MGDAが一般化したスムースネスで収束、おそらく
- Authors: Qi Zhang, Peiyao Xiao, Shaofeng Zou, Kaiyi Ji,
- Abstract要約: 多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。
最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。
一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
- 参考スコア(独自算出の注目度): 27.87166415148172
- License:
- Abstract: Multi-objective optimization (MOO) is receiving more attention in various fields such as multi-task learning. Recent works provide some effective algorithms with theoretical analysis but they are limited by the standard $L$-smooth or bounded-gradient assumptions, which typically do not hold for neural networks, such as Long short-term memory (LSTM) models and Transformers. In this paper, we study a more general and realistic class of generalized $\ell$-smooth loss functions, where $\ell$ is a general non-decreasing function of gradient norm. We revisit and analyze the fundamental multiple gradient descent algorithm (MGDA) and its stochastic version with double sampling for solving the generalized $\ell$-smooth MOO problems, which approximate the conflict-avoidant (CA) direction that maximizes the minimum improvement among objectives. We provide a comprehensive convergence analysis of these algorithms and show that they converge to an $\epsilon$-accurate Pareto stationary point with a guaranteed $\epsilon$-level average CA distance (i.e., the gap between the updating direction and the CA direction) over all iterations, where totally $\mathcal{O}(\epsilon^{-2})$ and $\mathcal{O}(\epsilon^{-4})$ samples are needed for deterministic and stochastic settings, respectively. We prove that they can also guarantee a tighter $\epsilon$-level CA distance in each iteration using more samples. Moreover, we analyze an efficient variant of MGDA named MGDA-FA using only $\mathcal{O}(1)$ time and space, while achieving the same performance guarantee as MGDA.
- Abstract(参考訳): 多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。
最近の研究は、理論解析で有効なアルゴリズムを提供しているが、Long short-term memory(LSTM)モデルやTransformerのようなニューラルネットワークには適用されない標準の$L$-smoothやbounded-gradientの仮定によって制限されている。
本稿では、より一般的で現実的な一般化された$\ell$-smooth損失関数の研究を行い、$\ell$は勾配ノルムの一般非減少関数である。
我々は、目的物間の最小改善を最大化する競合回避方向(CA)を近似する一般化された$\ell$-smooth MOO問題の解法として、基本的な多重勾配勾配アルゴリズム(MGDA)とその確率版を二重サンプリングで再検討し、解析する。
これらのアルゴリズムの総合収束解析を行い、全ての反復に対して、$\epsilon$-accurate Pareto 定常点(平均 CA 距離)$\epsilon$-level 平均 CA 距離(すなわち、更新方向と CA 方向のギャップ)を保証し、完全な$\mathcal{O}(\epsilon^{-2})$と$\mathcal{O}(\epsilon^{-4})$サンプルをそれぞれ決定論的および確率的設定のために必要であることを示す。
より厳密な$\epsilon$レベルのCA距離を各イテレーションで、より多くのサンプルを使って保証することも証明しています。
さらに,MGDA と同じ性能保証を達成しつつ,MGDA-FA という MGDA の効率的な変種を $\mathcal{O}(1)$ 時間と空間のみを用いて解析する。
関連論文リスト
- Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
我々は,ラゲールセル推定と密度支持推定の類似性を用いて,OTマップに対して$mathcalO(t-1)$の低いバウンダリレートを証明した。
所望の速さをほぼ達成するために,サンプル数に応じて減少するエントロピー正規化スキームを設計する。
論文 参考訳(メタデータ) (2024-05-23T11:46:03Z) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳(メタデータ) (2023-05-30T17:47:27Z) - Gauss-Newton Temporal Difference Learning with Nonlinear Function Approximation [11.925232472331494]
非線形関数近似を用いたQラーニング問題を解くため,ガウスニュートン時間差分法(GNTD)学習法を提案する。
各イテレーションにおいて、我々の手法は1つのガウスニュートン(GN)ステップを踏んで平均二乗ベルマン誤差(MSBE)の変種を最適化する。
いくつかのRLベンチマークにおいて、GNTDはTD型よりも高い報酬と高速な収束を示す。
論文 参考訳(メタデータ) (2023-02-25T14:14:01Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳(メタデータ) (2022-03-30T11:39:00Z) - DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample
Complexity [25.775517797956237]
本稿では,Douubly Compressed Momentum-assisted tracking algorithm $ttDoCoM$ for communicationを提案する。
我々のアルゴリズムは、実際にいくつかの最先端のアルゴリズムより優れていることを示す。
論文 参考訳(メタデータ) (2022-02-01T07:27:34Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳(メタデータ) (2020-12-28T17:19:32Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳(メタデータ) (2020-07-10T05:20:02Z) - Convergence of Online Adaptive and Recurrent Optimization Algorithms [0.0]
我々は、機械学習で使用されるいくつかの顕著な降下アルゴリズムの局所収束を証明した。
我々は確率的視点ではなく「エルゴディック」を採用し、確率分布の代わりに経験的な時間平均で作業する。
論文 参考訳(メタデータ) (2020-05-12T09:48:52Z) - Stochastic Proximal Gradient Algorithm with Minibatches. Application to
Large Scale Learning Models [2.384873896423002]
非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。
我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
論文 参考訳(メタデータ) (2020-03-30T10:43:56Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。