論文の概要: Towards Extremely Fast Bilevel Optimization with Self-governed
Convergence Guarantees
- arxiv url: http://arxiv.org/abs/2205.10054v1
- Date: Fri, 20 May 2022 09:46:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-24 01:08:00.925548
- Title: Towards Extremely Fast Bilevel Optimization with Self-governed
Convergence Guarantees
- Title(参考訳): 自己統治型収束保証による超高速二値最適化に向けて
- Authors: Risheng Liu, Xuan Liu, Wei Yao, Shangzhi Zeng, Jin Zhang
- Abstract要約: 既存の明示的かつ暗黙的なグラディエントベースのBLOを均一に理解するための単一レベル定式化を提案する。
我々の収束結果の顕著な特徴は、元の非加速GBLOバージョンと比較して、高速なBAGDCは定常性に対する非漸近収束理論を統一的に認めることである。
- 参考スコア(独自算出の注目度): 42.514612465664605
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Gradient methods have become mainstream techniques for Bi-Level Optimization
(BLO) in learning and vision fields. The validity of existing works heavily
relies on solving a series of approximation subproblems with extraordinarily
high accuracy. Unfortunately, to achieve the approximation accuracy requires
executing a large quantity of time-consuming iterations and computational
burden is naturally caused. This paper is thus devoted to address this critical
computational issue. In particular, we propose a single-level formulation to
uniformly understand existing explicit and implicit Gradient-based BLOs
(GBLOs). This together with our designed counter-example can clearly illustrate
the fundamental numerical and theoretical issues of GBLOs and their naive
accelerations. By introducing the dual multipliers as a new variable, we then
establish Bilevel Alternating Gradient with Dual Correction (BAGDC), a general
framework, which significantly accelerates different categories of existing
methods by taking specific settings. A striking feature of our convergence
result is that, compared to those original unaccelerated GBLO versions, the
fast BAGDC admits a unified non-asymptotic convergence theory towards
stationarity. A variety of numerical experiments have also been conducted to
demonstrate the superiority of the proposed algorithmic framework.
- Abstract(参考訳): グラデーション手法は、学習および視覚分野におけるbi-level optimization(blo)の主流技術となっている。
既存の作品の妥当性は、非常に高い精度で一連の近似部分問題を解くことに大きく依存している。
残念ながら、近似精度を達成するには、大量の時間を要するイテレーションを実行し、計算負荷を自然に発生させる必要がある。
そこで本研究では,この重要な計算問題に対処する。
特に,既存の明示的で暗黙的なGradient-based BLO(GBLO)を均一に理解するための単一レベル定式化を提案する。
これは我々の設計した反例とともに、gbloとそれらのナイーブ加速度の基本的な数値的および理論的問題を明確に示すことができる。
二値乗算器を新しい変数として導入することにより、二値補正による二値交互勾配(BAGDC)を確立する。
我々の収束結果の顕著な特徴は、元の非加速GBLOバージョンと比較して、高速なBAGDCは定常性に対する非漸近収束理論を統一的に認めることである。
提案するアルゴリズムフレームワークの優位性を示すために,様々な数値実験も行われている。
関連論文リスト
- 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) - On the Communication Complexity of Decentralized Bilevel Optimization [40.45379954138305]
本稿では,更新戦略の同時および交互化に基づく2つの新しい分散二段階勾配勾配アルゴリズムを提案する。
我々のアルゴリズムは既存の手法よりも高速な収束率と通信コストを抑えることができる。
このような理論的な結果は、不均一な環境での軽微な仮定で達成されたのはこれが初めてである。
論文 参考訳(メタデータ) (2023-11-19T14:56:26Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳(メタデータ) (2023-06-10T08:25:16Z) - Averaged Method of Multipliers for Bi-Level Optimization without
Lower-Level Strong Convexity [43.092883358935545]
単ループ二値乗算器 (sl-BAMM) を両レベル最適化 (BLO) のために提案する。
我々は, sl-BAMMのKKT定常点への非漸近収束解析を行い, 解析の利点は強い勾配有界性仮定の欠如にある。
論文 参考訳(メタデータ) (2023-02-07T11:29:05Z) - Value-Function-based Sequential Minimization for Bi-level Optimization [52.39882976848064]
勾配に基づくBi-Level Optimization (BLO)法は、現代の学習課題に広く応用されている。
機能的制約のあるBLOや悲観的なBLOなど、難解なシナリオでBLOを解くことができる勾配ベースの方法はほとんどない。
上記の問題に対処するために,BVFSM(Bi-level Value-Function-based Sequential Minimization)を提案する。
論文 参考訳(メタデータ) (2021-10-11T03:13:39Z) - A Generic Descent Aggregation Framework for Gradient-based Bi-level
Optimization [41.894281911990554]
両レベル学習タスクのための新しいBDA(Bi-level Descent Aggregation)フレームワークを開発した。
BDAは上層と下層の両方の階層的目的を集約する。
従来の勾配に基づくbiレベル法の収束結果を改善するための新しい証明法を提案する。
論文 参考訳(メタデータ) (2021-02-16T06:58:12Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳(メタデータ) (2020-06-16T13:41:54Z) - A Generic First-Order Algorithmic Framework for Bi-Level Programming
Beyond Lower-Level Singleton [49.23948907229656]
Bi-level Descent Aggregationは、汎用的な双方向最適化のためのフレキシブルでモジュール化されたアルゴリズムフレームワークである。
LLS条件なしでBDAの収束を証明する新しい手法を導出する。
我々の研究は、BDAが特定の一階計算モジュールの検証と互換性があることも示している。
論文 参考訳(メタデータ) (2020-06-07T05:18:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。