論文の概要: Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed
Smoothness Conditions
- arxiv url: http://arxiv.org/abs/2306.12067v1
- Date: Wed, 21 Jun 2023 07:32:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-22 14:39:17.956232
- Title: Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed
Smoothness Conditions
- Title(参考訳): 滑らかな緩和条件下での確率的二値最適化のための最適アルゴリズム
- Authors: Xuxing Chen, Tesi Xiao, Krishnakumar Balasubramanian
- Abstract要約: 両レベル最適化のための完全リリップループ・ヘシアン・インバージョンフリーなアルゴリズム・フレームワークを提案する。
我々は、我々のアプローチを少し修正することで、より汎用的な多目的ロバストな双レベル最適化問題に対処できることを示した。
- 参考スコア(独自算出の注目度): 9.518010235273785
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic Bilevel optimization usually involves minimizing an upper-level
(UL) function that is dependent on the arg-min of a strongly-convex lower-level
(LL) function. Several algorithms utilize Neumann series to approximate certain
matrix inverses involved in estimating the implicit gradient of the UL function
(hypergradient). The state-of-the-art StOchastic Bilevel Algorithm (SOBA) [16]
instead uses stochastic gradient descent steps to solve the linear system
associated with the explicit matrix inversion. This modification enables SOBA
to match the lower bound of sample complexity for the single-level counterpart
in non-convex settings. Unfortunately, the current analysis of SOBA relies on
the assumption of higher-order smoothness for the UL and LL functions to
achieve optimality. In this paper, we introduce a novel fully single-loop and
Hessian-inversion-free algorithmic framework for stochastic bilevel
optimization and present a tighter analysis under standard smoothness
assumptions (first-order Lipschitzness of the UL function and second-order
Lipschitzness of the LL function). Furthermore, we show that by a slight
modification of our approach, our algorithm can handle a more general
multi-objective robust bilevel optimization problem. For this case, we obtain
the state-of-the-art oracle complexity results demonstrating the generality of
both the proposed algorithmic and analytic frameworks. Numerical experiments
demonstrate the performance gain of the proposed algorithms over existing ones.
- Abstract(参考訳): 確率的双レベル最適化は通常、強凸下層(LL)関数のarg-minに依存する上層(UL)関数を最小化する。
いくつかのアルゴリズムはノイマン級数を用いて、UL関数の暗黙的勾配(ハイパーグラディエント)の推定に関与する行列逆を近似する。
最先端のStOchastic Bilevel Algorithm (SOBA) [16] は、代わりに確率勾配降下ステップを用いて、明示的行列の逆変換に関連する線形系を解く。
この修正により、ソバは非凸設定の単一レベルのサンプル複雑性の下限にマッチすることができる。
残念ながら、SOBA の現在の解析は、最適性を達成するために UL と LL 関数の高次滑らかさの仮定に依存する。
本稿では,確率的二レベル最適化のための完全単ループおよびヘシアン反転自由アルゴリズムフレームワークを導入し,標準滑らか性仮定(UL関数の1次リプシッツネスとLL関数の2次リプシッツネス)の下でより厳密な解析を行う。
さらに,提案手法を微調整することで,より汎用的な多目的ロバストな2レベル最適化問題に対処できることを示す。
本稿では,提案したアルゴリズムおよび解析フレームワークの汎用性を示す,最先端のオラクル複雑性結果を得る。
数値実験により,提案手法の性能向上が実証された。
関連論文リスト
- Constrained Bi-Level Optimization: Proximal Lagrangian Value function
Approach and Hessian-free Algorithm [8.479947546216131]
We developed a Hessian-free gradient-based algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA)
LV-HBAは特に機械学習アプリケーションに適している。
論文 参考訳(メタデータ) (2024-01-29T13:50:56Z) - Bilevel Optimization under Unbounded Smoothness: A New Algorithm and
Convergence Analysis [17.596465452814883]
現在の双レベル最適化アルゴリズムは、上層関数の反復が非有界な滑らかであると仮定する。
最近の研究では、あるニューラルネットワークがそのような非有界な滑らかさを示すことが示されている。
論文 参考訳(メタデータ) (2024-01-17T20:28:15Z) - 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) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳(メタデータ) (2021-11-29T15:10:09Z) - Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis [12.680169619392695]
この論文は、2レベル最適化アルゴリズムに対する総合収束率解析を提供する。
問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。
そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-07-31T22:05:47Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳(メタデータ) (2021-07-26T16:18:43Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳(メタデータ) (2020-10-15T18:09:48Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。