論文の概要: Double Momentum Method for Lower-Level Constrained Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2406.17386v1
- Date: Tue, 25 Jun 2024 09:05:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-26 15:01:42.294036
- Title: Double Momentum Method for Lower-Level Constrained Bilevel Optimization
- Title（参考訳）: 低レベル制約二レベル最適化のための二重モーメント法
- Authors: Wanli Shi, Yi Chang, Bin Gu,
- Abstract要約: 再帰的仮定を使わずに,非滑らかな暗黙関数定理を応用したLCBOの新しい過次関数を提案する。
さらに,2重モーメント法と適応ステップサイズ法に基づいて,テキスト入力ループのシングルタイムスケール反復アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 31.28781889710351
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Bilevel optimization (BO) has recently gained prominence in many machine learning applications due to its ability to capture the nested structure inherent in these problems. Recently, many hypergradient methods have been proposed as effective solutions for solving large-scale problems. However, current hypergradient methods for the lower-level constrained bilevel optimization (LCBO) problems need very restrictive assumptions, namely, where optimality conditions satisfy the differentiability and invertibility conditions and lack a solid analysis of the convergence rate. What's worse, existing methods require either double-loop updates, which are sometimes less efficient. To solve this problem, in this paper, we propose a new hypergradient of LCBO leveraging the theory of nonsmooth implicit function theorem instead of using the restrive assumptions. In addition, we propose a \textit{single-loop single-timescale} algorithm based on the double-momentum method and adaptive step size method and prove it can return a $(\delta, \epsilon)$-stationary point with $\tilde{\mathcal{O}}(d_2^2\epsilon^{-4})$ iterations. Experiments on two applications demonstrate the effectiveness of our proposed method.
- Abstract（参考訳）: 双レベル最適化(BO)は、最近、これらの問題に固有のネスト構造をキャプチャできるため、多くの機械学習アプリケーションで注目されている。
近年,大規模問題の解法として多くの超勾配法が提案されている。
しかしながら、LCBO問題に対する現在の過次的手法は、最適条件が微分可能性および可逆性条件を満たし、収束率のしっかりとした解析が欠如している場合に、非常に制限的な仮定を必要とする。
さらに悪いことに、既存のメソッドではダブルループの更新が必要です。
そこで本研究では,再帰的仮定を使わずに,非滑らかな暗黙的関数定理(nonsmooth implicit function theorem)の理論を活用するLCBOの新しい過次関数を提案する。
さらに,double-momentum法とAdaptive Step size法を併用した \textit{single-loop single-timescale} アルゴリズムを提案し,$(\delta, \epsilon)$-stationary point with $\tilde{\mathcal{O}}(d_2^2\epsilon^{-4})$ iterations を返却できることを証明した。
提案手法の有効性を示す2つの応用実験を行った。
関連論文リスト
- Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization [25.438298531555468]
双レベル最適化は、ハイパーラーニング、メタラーニング、強化ラーニングなど、多くの機械学習タスクに広く適用されている。
最適収束$frac1TT(Hessian/BiO法)を軽度条件下で提案する。
バイレベルゲーム超定常数値収束に関するいくつかの実験を行う。
論文 参考訳（メタデータ） (2024-07-25T07:25:06Z) - An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - Adaptive Mirror Descent Bilevel Optimization [25.438298531555468]
非二段階最適化のためのミラー降下に基づく適応的二段階最適化手法のクラスを提案する。
いくつかの条件下でメソッドを解析し、メソッドが高速なイテレーション数を持つことを証明します。
論文 参考訳（メタデータ） (2023-11-08T08:17:09Z) - A Conditional Gradient-based Method for Simple Bilevel Optimization with
Convex Lower-level Problem [18.15207779559351]
そこで本稿では, 切削平面による下層問題の解集合を局所的に近似する二段階最適化手法を提案する。
本手法は,二段階問題のクラスについて,最もよく知られた仮定を導出する。
論文 参考訳（メタデータ） (2022-06-17T16:12:47Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳（メタデータ） (2021-06-21T20:16:40Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。