論文の概要: An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness

• arxiv url: http://arxiv.org/abs/2409.19212v2
• Date: Wed, 30 Oct 2024 19:05:17 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-06 04:01:11.096993
• Title: An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness
• Title（参考訳）: 非有界な滑らかさ下での確率的二値最適化のための高速化アルゴリズム
• Authors: Xiaochuan Gong, Jie Hao, Mingrui Liu,
• Abstract要約: 本稿では,上層関数が非非有界な滑らかさであり,下層関数が強く凸であるような二層最適化問題のクラスについて検討する。 これらの問題は、ニューラルネットワークを用いたテキスト分類など、データ学習に大きな応用がある。
• 参考スコア（独自算出の注目度）: 15.656614304616006
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper investigates a class of stochastic bilevel optimization problems where the upper-level function is nonconvex with potentially unbounded smoothness and the lower-level problem is strongly convex. These problems have significant applications in sequential data learning, such as text classification using recurrent neural networks. The unbounded smoothness is characterized by the smoothness constant of the upper-level function scaling linearly with the gradient norm, lacking a uniform upper bound. Existing state-of-the-art algorithms require $\widetilde{O}(1/\epsilon^4)$ oracle calls of stochastic gradient or Hessian/Jacobian-vector product to find an $\epsilon$-stationary point. However, it remains unclear if we can further improve the convergence rate when the assumptions for the function in the population level also hold for each random realization almost surely (e.g., Lipschitzness of each realization of the stochastic gradient). To address this issue, we propose a new Accelerated Bilevel Optimization algorithm named AccBO. The algorithm updates the upper-level variable by normalized stochastic gradient descent with recursive momentum and the lower-level variable by the stochastic Nesterov accelerated gradient descent algorithm with averaging. We prove that our algorithm achieves an oracle complexity of $\widetilde{O}(1/\epsilon^3)$ to find an $\epsilon$-stationary point. Our proof relies on a novel lemma characterizing the dynamics of stochastic Nesterov accelerated gradient descent algorithm under distribution drift with high probability for the lower-level variable, which is of independent interest and also plays a crucial role in analyzing the hypergradient estimation error over time. Experimental results on various tasks confirm that our proposed algorithm achieves the predicted theoretical acceleration and significantly outperforms baselines in bilevel optimization.
• Abstract（参考訳）: 本稿では,上層関数が非凸であり,潜在的に非有界な滑らかさを持ち,下層関数が強凸である確率的二段階最適化問題のクラスについて検討する。 これらの問題は、リカレントニューラルネットワークを用いたテキスト分類など、シーケンシャルなデータ学習に重要な応用がある。 非有界な滑らかさは、勾配ノルムと線形にスケーリングする上層関数の滑らかさ定数が特徴であり、一様の上界が欠如している。 既存の最先端アルゴリズムでは、$\widetilde{O}(1/\epsilon^4)$ oracle call of stochastic gradient or Hessian/Jacobian-vector product to find $\epsilon$-stationary point。 しかし、集団レベルの函数の仮定が各ランダムな実現に対してほぼ確実に成り立つ場合(例えば、確率的勾配の各実現のリプシッツ性)、収束率をさらに改善できるかどうかは不明である。 この問題に対処するため,AccBO というアルゴリズムを新たに提案する。 アルゴリズムは、正規化確率勾配降下法と再帰運動量による上層変数と、平均化を伴う確率ネステロフ加速勾配降下法により下層変数を更新する。 我々は,このアルゴリズムが$\widetilde{O}(1/\epsilon^3)$のオラクル複雑性を達成し,$\epsilon$-定常点を求めることを証明した。 我々の証明は,確率論的ネステロフ加速勾配降下アルゴリズムの分布流下での力学を特徴付ける新しい補題に依拠するが,これは独立性があり,時間とともに過次推定誤差を分析する上でも重要な役割を担っている。 実験結果から,提案アルゴリズムが予測された理論的加速度を達成し,二段階最適化のベースラインを著しく上回ったことが確認された。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis [17.596465452814883]
  現在の双レベル最適化アルゴリズムは、上層関数の反復が非有界な滑らかであると仮定する。 最近の研究では、あるニューラルネットワークがそのような非有界な滑らかさを示すことが示されている。
  論文  参考訳（メタデータ） (2024-01-17T20:28:15Z)
• Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions [9.518010235273785]
  両レベル最適化のための完全リリップループ・ヘシアン・インバージョンフリーなアルゴリズム・フレームワークを提案する。 我々は、我々のアプローチを少し修正することで、より汎用的な多目的ロバストな双レベル最適化問題に対処できることを示した。
  論文  参考訳（メタデータ） (2023-06-21T07:32:29Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and Nonsmooth Bi-level Optimization [26.68351521813062]
  既存のバイレベルアルゴリズムは、非滑らかまたは超滑らかな正規化器を扱えない。 本稿では,包括的機械学習アプリケーションを高速化するために,暗黙差分法(AID)が有効であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T18:53:04Z)
• 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)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  バイレベル最適化は、機械学習における問題の1つだ。 双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
  論文  参考訳（メタデータ） (2022-02-08T07:10:06Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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