論文の概要: Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis
- arxiv url: http://arxiv.org/abs/2108.00330v1
- Date: Sat, 31 Jul 2021 22:05:47 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-03 15:29:47.534232
- Title: Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis
- Title（参考訳）: 機械学習のためのバイレベル最適化:アルゴリズム設計と収束解析
- Authors: Kaiyi Ji
- Abstract要約: この論文は、2レベル最適化アルゴリズムに対する総合収束率解析を提供する。
問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。
そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 12.680169619392695
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization has become a powerful framework in various machine
learning applications including meta-learning, hyperparameter optimization, and
network architecture search. There are generally two classes of bilevel
optimization formulations for machine learning: 1) problem-based bilevel
optimization, whose inner-level problem is formulated as finding a minimizer of
a given loss function; and 2) algorithm-based bilevel optimization, whose
inner-level solution is an output of a fixed algorithm. For the first class,
two popular types of gradient-based algorithms have been proposed for
hypergradient estimation via approximate implicit differentiation (AID) and
iterative differentiation (ITD). Algorithms for the second class include the
popular model-agnostic meta-learning (MAML) and almost no inner loop (ANIL).
However, the convergence rate and fundamental limitations of bilevel
optimization algorithms have not been well explored.
This thesis provides a comprehensive convergence rate analysis for bilevel
algorithms in the aforementioned two classes. We further propose principled
algorithm designs for bilevel optimization with higher efficiency and
scalability. For the problem-based formulation, we provide a convergence rate
analysis for AID- and ITD-based bilevel algorithms. We then develop
acceleration bilevel algorithms, for which we provide shaper convergence
analysis with relaxed assumptions. We also provide the first lower bounds for
bilevel optimization, and establish the optimality by providing matching upper
bounds under certain conditions. We finally propose new stochastic bilevel
optimization algorithms with lower complexity and higher efficiency in
practice. For the algorithm-based formulation, we develop a theoretical
convergence for general multi-step MAML and ANIL, and characterize the impact
of parameter selections and loss geometries on the their complexities.
- Abstract（参考訳）: バイレベル最適化は、メタラーニング、ハイパーパラメータ最適化、ネットワークアーキテクチャ検索など、さまざまな機械学習アプリケーションにおいて強力なフレームワークとなっている。
1 問題に基づく二段階最適化は、与えられた損失関数の最小値を見つけるために内部レベルの問題を定式化し、2) アルゴリズムに基づく二段階最適化は、内部レベルの解が固定アルゴリズムの出力である。
最初のクラスでは、近似的暗黙的微分 (AID) と反復的微分 (ITD) による過次推定のために2種類の勾配に基づくアルゴリズムが提案されている。
第2クラスのアルゴリズムには、一般的なモデルに依存しないメタラーニング(MAML)や、ほとんど内部ループ(ANIL)がない。
しかし、二値最適化アルゴリズムの収束率と基本的限界はよく研究されていない。
この論文は、上記の2つのクラスにおける双レベルアルゴリズムの総合収束速度解析を提供する。
さらに,効率とスケーラビリティを向上した二段階最適化のためのアルゴリズム設計を提案する。
問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。
そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
また,二値最適化のための最初の下限を提供し,一定の条件下での上限を一致させることで最適性を確立する。
最後に, 複雑性が低く, 効率が向上した新しい確率的二段階最適化アルゴリズムを提案する。
アルゴリズムに基づく定式化のために,多段階mamlとanilの理論的収束法を開発し,それらの複雑度に対するパラメータ選択と損失ジオメトリの影響を特徴付ける。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - A Single-Loop Algorithm for Decentralized Bilevel Optimization [11.67135350286933]
そこで本研究では,分散化された二段階最適化を低レベルに凸した問題で解くための新しい単一ループアルゴリズムを提案する。
提案手法は,反復毎に2つの行列ベクトル乗算のみを用いることで,過勾配を近似する完全単ループ法である。
解析により,提案アルゴリズムは二段階最適化アルゴリズムにおいて最もよく知られた収束率を実現することを示す。
論文 参考訳（メタデータ） (2023-11-15T13:29:49Z) - Fast Adaptive Federated Bilevel Optimization [14.579475552088692]
本稿では,分散二レベル最適化問題の解法として,適応型二レベル最適化アルゴリズム(AdaFBiO)を提案する。
AdaFBiOは、統一適応行列を用いて、様々な適応学習率を柔軟に組み込んで、ULおよびLL問題の変数を更新する。
AdaFBiOアルゴリズムの収束解析フレームワークを提供し、$tildeO(epsilon-3)$の複雑さと$tildeO(epsilon-2)$のコミュニケーション複雑さのサンプルが必要であることを証明した。
論文 参考訳（メタデータ） (2022-11-02T13:55:47Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。