論文の概要: Generalized Frank-Wolfe Algorithm for Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2206.08868v1
- Date: Fri, 17 Jun 2022 16:12:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-20 13:37:00.639843
- Title: Generalized Frank-Wolfe Algorithm for Bilevel Optimization
- Title（参考訳）: 2レベル最適化のための一般化Frank-Wolfeアルゴリズム
- Authors: Ruichen Jiang, Nazanin Abolfazli, Aryan Mokhtari, Erfan Yazdandoost
Hamedani
- Abstract要約: 本稿では,フランク・ウルフ法(FW)を一般化して検討した。
提案手法は,二段階問題に対して最もよく知られた繰り返しを実現する。
- 参考スコア（独自算出の注目度）: 18.15207779559351
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study a class of bilevel optimization problems, also known
as simple bilevel optimization, where we minimize a smooth objective function
over the optimal solution set of another convex constrained optimization
problem. Several iterative methods have been developed for tackling this class
of problems. Alas, their convergence guarantees are not satisfactory as they
are either asymptotic for the upper-level objective, or the convergence rates
are slow and sub-optimal. To address this issue, in this paper, we introduce a
generalization of the Frank-Wolfe (FW) method to solve the considered problem.
The main idea of our method is to locally approximate the solution set of the
lower-level problem via a cutting plane, and then run a FW-type update to
decrease the upper-level objective. When the upper-level objective is convex,
we show that our method requires
${\mathcal{O}}(\max\{1/\epsilon_f,1/\epsilon_g\})$ iterations to find a
solution that is $\epsilon_f$-optimal for the upper-level objective and
$\epsilon_g$-optimal for the lower-level objective. Moreover, when the
upper-level objective is non-convex, our method requires
${\mathcal{O}}(\max\{1/\epsilon_f^2,1/(\epsilon_f\epsilon_g)\})$ iterations to
find an $(\epsilon_f,\epsilon_g)$-optimal solution. We further prove stronger
convergence guarantees under the H\"olderian error bound assumption on the
lower-level problem. To the best of our knowledge, our method achieves the
best-known iteration complexity for the considered bilevel problem. We also
present numerical experiments to showcase the superior performance of our
method compared with state-of-the-art methods.
- Abstract（参考訳）: 本稿では,他の凸制約最適化問題の最適解集合上の滑らかな目的関数を最小化する,単純二値最適化(Simple bilevel optimization)のクラスについて検討する。
この問題に対処するための反復的な手法がいくつか開発されている。
残念なことに、それらの収束保証は上層目標に漸近的であるか、収束速度が遅く、準最適であるため満足できない。
この問題に対処するため,本稿ではフランク・ウルフ法(FW)の一般化を導入し,この問題を解決した。
提案手法の主な考え方は,低レベル問題の解集合を切削面を通して局所的に近似し,fw型更新を行い,上位レベルの目標を減少させることである。
上層目標が凸である場合、上層目標に対して$\epsilon_f$-optimal、下層目標に対して$\epsilon_g$-optimalの解を見つけるためには${\mathcal{O}}(\max\{1/\epsilon_f,1/\epsilon_g\})$反復が必要である。
さらに、上層目標が非凸である場合、我々の方法は${\mathcal{O}}(\max\{1/\epsilon_f^2,1/(\epsilon_f\epsilon_g)\})$の反復を必要とする。
さらに、下層問題に対するH\"olderian error bound assumptionの下で、より強い収束を保証する。
我々の知識を最大限に活用するため,本手法は2レベル問題の最もよく知られた反復複雑性を実現する。
また,現状の手法と比較して,提案手法の優れた性能を示す数値実験を行った。
関連論文リスト
- 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) - Projection-Free Methods for Stochastic Simple Bilevel Optimization with
Convex Lower-level Problem [16.9187409976238]
凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。
低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
論文 参考訳（メタデータ） (2023-08-15T02:37:11Z) - A Generalized Alternating Method for Bilevel Learning under the
Polyak-{\L}ojasiewicz Condition [63.66516306205932]
バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。
最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
論文 参考訳（メタデータ） (2023-06-04T17:54:11Z) - On Momentum-Based Gradient Methods for Bilevel Optimization with
Nonconvex Lower-Level [25.438298531555468]
バイレベル最適化は機械学習タスクで一般的なプロセスである。
本稿では,両レベルPLゲームにおける非表現問題について検討する。
我々は,既存の最良の結果を$tO(Enabla F(x)leq epsilon$)の係数で改善することを示す。
論文 参考訳（メタデータ） (2023-03-07T14:55:05Z) - On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis [18.08351275534193]
双レベル最適化は、そうでなければ斜め最適化問題の内部構造を明らかにする。
双レベル最適化における共通のゴールは、パラメータの集合の解に暗黙的に依存する超対象である。
論文 参考訳（メタデータ） (2023-01-02T15:09:12Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - 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) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。