論文の概要: Effective Bilevel Optimization via Minimax Reformulation
- arxiv url: http://arxiv.org/abs/2305.13153v4
- Date: Mon, 04 Nov 2024 02:09:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-05 21:26:12.667010
- Title: Effective Bilevel Optimization via Minimax Reformulation
- Title（参考訳）: ミニマックス修正による効果的な二値最適化
- Authors: Xiaoyu Wang, Rui Pan, Renjie Pi, Jipeng Zhang,
- Abstract要約: ミニマックス問題としてバイレベル最適化の再構成を提案する。
穏やかな条件下では、これらの2つの問題が等価であることを示す。
提案手法は, 計算コストを大幅に削減しつつ, 最先端の2段階法より優れる。
- 参考スコア（独自算出の注目度）: 23.5093932552053
- License:
- Abstract: Bilevel optimization has found successful applications in various machine learning problems, including hyper-parameter optimization, data cleaning, and meta-learning. However, its huge computational cost presents a significant challenge for its utilization in large-scale problems. This challenge arises due to the nested structure of the bilevel formulation, where each hyper-gradient computation necessitates a costly inner optimization procedure. To address this issue, we propose a reformulation of bilevel optimization as a minimax problem, effectively decoupling the outer-inner dependency. Under mild conditions, we show these two problems are equivalent. Furthermore, we introduce a multi-stage gradient descent and ascent (GDA) algorithm to solve the resulting minimax problem with convergence guarantees. Extensive experimental results demonstrate that our method outperforms state-of-the-art bilevel methods while significantly reducing the computational cost.
- Abstract（参考訳）: バイレベル最適化は、ハイパーパラメータ最適化、データクリーニング、メタラーニングなど、さまざまな機械学習問題に成功している。
しかし、その膨大な計算コストは、大規模問題におけるその利用に大きな課題をもたらす。
この課題は、二段階の定式化のネスト構造が原因であり、各超勾配計算はコストのかかる内部最適化手順を必要とする。
この問題に対処するために,2レベル最適化をミニマックス問題として再検討し,外部インナー依存性を効果的に分離する手法を提案する。
穏やかな条件下では、これらの2つの問題が等価であることを示す。
さらに,収束保証付きミニマックス問題の解法として,多段勾配降下法(GDA)アルゴリズムを導入する。
その結果,提案手法は計算コストを大幅に削減しつつ,最先端の2段階法よりも優れていた。
関連論文リスト
- Towards Differentiable Multilevel Optimization: A Gradient-Based Approach [1.6114012813668932]
本稿では,多レベル最適化のための新しい勾配に基づくアプローチを提案する。
本手法は解の精度と収束速度を両立させながら計算複雑性を著しく低減する。
私たちの知る限りでは、これは暗黙の微分の一般的なバージョンを提供する最初のアルゴリズムの1つである。
論文 参考訳（メタデータ） (2024-10-15T06:17:59Z) - 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) - Contextual Stochastic Bilevel Optimization [50.36775806399861]
文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。
メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
論文 参考訳（メタデータ） (2023-10-27T23:24:37Z) - Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。
我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。
実験結果から,アルゴリズムの性能が向上した。
論文 参考訳（メタデータ） (2023-02-13T21:28:53Z) - Efficient Gradient Approximation Method for Constrained Bilevel
Optimization [2.0305676256390934]
大規模高次元データを用いたバイレベル最適化が開発されている。
本稿では凸と微分不可能な近似を伴う制約付き二値問題について考察する。
論文 参考訳（メタデータ） (2023-02-03T19:34:56Z) - Versatile Single-Loop Method for Gradient Estimator: First and Second
Order Optimality, and its Application to Federated Learning [45.78238792836363]
本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。
既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
論文 参考訳（メタデータ） (2022-09-01T11:05:26Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。