論文の概要: 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乗な滑らかさを伴わずに、対数的因子まで、最先端の複雑さの結果と一致する。
この証明は、周期的に更新される低レベル変数に対する新しい技術的補題に依存している。
テキスト分類タスクにおけるハイパー表現学習,ハイパーパラメータ最適化,データハイパークリーニングの実験により,提案アルゴリズムの有効性が示された。
関連論文リスト
- 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) - Fast Adaptive Federated Bilevel Optimization [14.579475552088692]
本稿では,分散二レベル最適化問題の解法として,適応型二レベル最適化アルゴリズム(AdaFBiO)を提案する。
AdaFBiOは、統一適応行列を用いて、様々な適応学習率を柔軟に組み込んで、ULおよびLL問題の変数を更新する。
AdaFBiOアルゴリズムの収束解析フレームワークを提供し、$tildeO(epsilon-3)$の複雑さと$tildeO(epsilon-2)$のコミュニケーション複雑さのサンプルが必要であることを証明した。
論文 参考訳(メタデータ) (2022-11-02T13:55:47Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。