論文の概要: Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis

• arxiv url: http://arxiv.org/abs/2401.09587v1
• Date: Wed, 17 Jan 2024 20:28:15 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-19 18:32:28.331647
• Title: Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis
• Title（参考訳）: 非有界な平滑な二段階最適化:新しいアルゴリズムと収束解析
• Authors: Jie Hao, Xiaochuan Gong, Mingrui Liu
• Abstract要約: 現在の双レベル最適化アルゴリズムは、上層関数の反復が非有界な滑らかであると仮定する。 最近の研究では、あるニューラルネットワークがそのような非有界な滑らかさを示すことが示されている。
• 参考スコア（独自算出の注目度）: 17.596465452814883
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization is an important formulation for many machine learning problems. Current bilevel optimization algorithms assume that the gradient of the upper-level function is Lipschitz. However, recent studies reveal that certain neural networks such as recurrent neural networks (RNNs) and long-short-term memory networks (LSTMs) exhibit potential unbounded smoothness, rendering conventional bilevel optimization algorithms unsuitable. In this paper, we design a new bilevel optimization algorithm, namely BO-REP, to address this challenge. This algorithm updates the upper-level variable using normalized momentum and incorporates two novel techniques for updating the lower-level variable: \textit{initialization refinement} and \textit{periodic updates}. Specifically, once the upper-level variable is initialized, a subroutine is invoked to obtain a refined estimate of the corresponding optimal lower-level variable, and the lower-level variable is updated only after every specific period instead of each iteration. When the upper-level problem is nonconvex and unbounded smooth, and the lower-level problem is strongly convex, we prove that our algorithm requires $\widetilde{\mathcal{O}}(1/\epsilon^4)$ iterations to find an $\epsilon$-stationary point in the stochastic setting, where each iteration involves calling a stochastic gradient or Hessian-vector product oracle. Notably, this result matches the state-of-the-art complexity results under the bounded smoothness setting and without mean-squared smoothness of the stochastic gradient, up to logarithmic factors. Our proof relies on novel technical lemmas for the periodically updated lower-level variable, which are of independent interest. Our experiments on hyper-representation learning, hyperparameter optimization, and data hyper-cleaning for text classification tasks demonstrate the effectiveness of our proposed algorithm.
• Abstract（参考訳）: バイレベル最適化は多くの機械学習問題にとって重要な定式化である。 現在の双レベル最適化アルゴリズムは、上層関数の勾配がリプシッツであると仮定する。 しかし、最近の研究では、リカレントニューラルネットワーク(RNN)や長期記憶ネットワーク(LSTM)のような特定のニューラルネットワークが潜在的に非有界な滑らかさを示し、従来の双レベル最適化アルゴリズムが適さないことが示されている。 本稿では,この課題に対処するため,新しい二段階最適化アルゴリズムBO-REPを設計する。 このアルゴリズムは、正規化モーメントを用いて上層変数を更新し、下層変数を更新する2つの新しいテクニックを組み込んだ: \textit{initialization refinement} と \textit{ periodic updates}。 具体的には、上層変数が初期化されると、サブルーチンが起動され、対応する最適下層変数の洗練された推定値が得られ、下層変数は各イテレーションの代わりに特定の期間後にのみ更新される。 上階の問題は非凸で無界な滑らかであり、下階の問題は強い凸であるとき、我々のアルゴリズムは確率的設定において$\epsilon$定常点を見つけるために$\widetilde{\mathcal{o}}(1/\epsilon^4)$の反復が必要であることを証明します。 特に、この結果は、有界な滑らかさと確率勾配の平均2乗な滑らかさを伴わずに、対数的因子まで、最先端の複雑さの結果と一致する。 この証明は、周期的に更新される低レベル変数に対する新しい技術的補題に依存している。 テキスト分類タスクにおけるハイパー表現学習,ハイパーパラメータ最適化,データハイパークリーニングの実験により,提案アルゴリズムの有効性が示された。

関連論文リスト

• A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
  本稿では、上層関数が非定常で、潜在的に非有界な滑らかさを持ち、下層関数が凸であるような二層最適化の問題を考察する。 既存のアルゴリズムはネストループに依存しており、これは重要なチューニング作業を必要とし、実用的ではない。
  論文  参考訳（メタデータ） (2024-12-28T04:40:27Z)
• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [None]
  本稿では,上層関数が非非有界な滑らかさであり,下層関数が強く凸であるような二層最適化問題のクラスについて検討する。 これらの問題は、ニューラルネットワークを用いたテキスト分類など、データ学習に大きな応用がある。
  論文  参考訳（メタデータ） (2024-09-28T02:30:44Z)
• Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions [9.518010235273785]
  両レベル最適化のための完全リリップループ・ヘシアン・インバージョンフリーなアルゴリズム・フレームワークを提案する。 我々は、我々のアプローチを少し修正することで、より汎用的な多目的ロバストな双レベル最適化問題に対処できることを示した。
  論文  参考訳（メタデータ） (2023-06-21T07:32:29Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  バイレベル最適化は、機械学習における問題の1つだ。 双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
  論文  参考訳（メタデータ） (2022-02-08T07:10:06Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。 また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
  論文  参考訳（メタデータ） (2021-07-26T16:18:43Z)
• 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)

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

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