論文の概要: A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima
- arxiv url: http://arxiv.org/abs/2203.01123v1
- Date: Tue, 1 Mar 2022 18:20:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-03 14:18:14.068765
- Title: A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima
- Title（参考訳）: マルチインナーミニマを用いた二値最適化のための制約付き最適化手法
- Authors: Daouda Sow, Kaiyi Ji, Ziwei Guan, Yingbin Liang
- Abstract要約: そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
- 参考スコア（独自算出の注目度）: 49.320758794766185
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization has found extensive applications in modern machine
learning problems such as hyperparameter optimization, neural architecture
search, meta-learning, etc. While bilevel problems with a unique inner minimal
point (e.g., where the inner function is strongly convex) are well understood,
bilevel problems with multiple inner minimal points remains to be a challenging
and open problem. Existing algorithms designed for such a problem were
applicable to restricted situations and do not come with the full guarantee of
convergence. In this paper, we propose a new approach, which convert the
bilevel problem to an equivalent constrained optimization, and then the
primal-dual algorithm can be used to solve the problem. Such an approach enjoys
a few advantages including (a) addresses the multiple inner minima challenge;
(b) features fully first-order efficiency without involving second-order
Hessian and Jacobian computations, as opposed to most existing gradient-based
bilevel algorithms; (c) admits the convergence guarantee via constrained
nonconvex optimization. Our experiments further demonstrate the desired
performance of the proposed approach.
- Abstract（参考訳）: 双レベル最適化は、ハイパーパラメータ最適化、ニューラルアーキテクチャ探索、メタラーニングなど、現代の機械学習問題に広く応用されている。
特異な内極小点を持つ双レベル問題(例えば、内関数が強凸であるような)はよく理解されているが、複数の内極小点を持つ双レベル問題は困難でオープンな問題である。
このような問題のために設計された既存のアルゴリズムは制限された状況に適用可能であり、収束の完全な保証は得られなかった。
本稿では,二レベル問題を等価制約付き最適化に変換し,その解法としてプライマル・デュアルアルゴリズムを提案する。
このようなアプローチにはいくつかの利点がある。
a) 多重内因性ミニマ課題に対処すること。
b) 既存の勾配に基づく二値アルゴリズムとは対照的に,2次ヘシアンおよびヤコビアン計算を伴わない完全一階効率を特徴とする。
c) 制約付き非凸最適化により収束保証を受ける。
また,提案手法の望ましい性能を示す実験を行った。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。
2つのよく知られた実世界のアプリケーションでその効果を実証する。
論文 参考訳（メタデータ） (2024-06-14T15:59:36Z) - A Single-Loop Algorithm for Decentralized Bilevel Optimization [11.67135350286933]
そこで本研究では,分散化された二段階最適化を低レベルに凸した問題で解くための新しい単一ループアルゴリズムを提案する。
提案手法は,反復毎に2つの行列ベクトル乗算のみを用いることで,過勾配を近似する完全単ループ法である。
解析により,提案アルゴリズムは二段階最適化アルゴリズムにおいて最もよく知られた収束率を実現することを示す。
論文 参考訳（メタデータ） (2023-11-15T13:29:49Z) - Effective Bilevel Optimization via Minimax Reformulation [23.5093932552053]
ミニマックス問題としてバイレベル最適化の再構成を提案する。
穏やかな条件下では、これらの2つの問題が等価であることを示す。
提案手法は, 計算コストを大幅に削減しつつ, 最先端の2段階法より優れる。
論文 参考訳（メタデータ） (2023-05-22T15:41:33Z) - Efficient Gradient Approximation Method for Constrained Bilevel
Optimization [2.0305676256390934]
大規模高次元データを用いたバイレベル最適化が開発されている。
本稿では凸と微分不可能な近似を伴う制約付き二値問題について考察する。
論文 参考訳（メタデータ） (2023-02-03T19:34:56Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - On Implicit Bias in Overparameterized Bilevel Optimization [38.11483853830913]
双レベル問題は、それぞれ外問題と内問題と呼ばれる、ネストした2つのサブプロブレムから構成される。
本稿では,2レベル最適化のための勾配に基づくアルゴリズムの暗黙バイアスについて検討する。
ウォームスタートBLOによって得られる内部解は、外的目的に関する驚くべき量の情報を符号化できることを示す。
論文 参考訳（メタデータ） (2022-12-28T18:57:46Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。