論文の概要: Bilevel Optimization: Convergence Analysis and Enhanced Design
- arxiv url: http://arxiv.org/abs/2010.07962v3
- Date: Fri, 27 Aug 2021 17:32:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-07 03:44:03.851657
- Title: Bilevel Optimization: Convergence Analysis and Enhanced Design
- Title（参考訳）: 両レベル最適化:収束解析と拡張設計
- Authors: Kaiyi Ji, Junjie Yang and Yingbin Liang
- Abstract要約: バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
- 参考スコア（独自算出の注目度）: 63.64636047748605
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization has arisen as a powerful tool for many machine learning
problems such as meta-learning, hyperparameter optimization, and reinforcement
learning. In this paper, we investigate the nonconvex-strongly-convex bilevel
optimization problem. For deterministic bilevel optimization, we provide a
comprehensive convergence rate analysis for two popular algorithms respectively
based on approximate implicit differentiation (AID) and iterative
differentiation (ITD). For the AID-based method, we orderwisely improve the
previous convergence rate analysis due to a more practical parameter selection
as well as a warm start strategy, and for the ITD-based method we establish the
first theoretical convergence rate. Our analysis also provides a quantitative
comparison between ITD and AID based approaches. For stochastic bilevel
optimization, we propose a novel algorithm named stocBiO, which features a
sample-efficient hypergradient estimator using efficient Jacobian- and
Hessian-vector product computations. We provide the convergence rate guarantee
for stocBiO, and show that stocBiO outperforms the best known computational
complexities orderwisely with respect to the condition number $\kappa$ and the
target accuracy $\epsilon$. We further validate our theoretical results and
demonstrate the efficiency of bilevel optimization algorithms by the
experiments on meta-learning and hyperparameter optimization.
- Abstract（参考訳）: バイレベル最適化は、メタ学習、ハイパーパラメータ最適化、強化学習など、多くの機械学習問題の強力なツールとして生まれました。
本稿では,非凸強凸二レベル最適化問題について検討する。
決定論的二段階最適化のために,近似暗黙的微分 (aid) と反復的微分 (itd) に基づく2つの一般的なアルゴリズムの包括的収束率解析を行う。
AIDに基づく手法では、より実用的なパラメータ選択と温かいスタート戦略により、事前収束率分析を順番に改善し、ITDベースの手法では、最初の理論的収束率を確立する。
分析はまた、ITDとAIDに基づくアプローチの定量的比較も提供する。
確率的二段階最適化のために,効率的なジャコビアンおよびヘシアンベクトル積計算を用いた標本効率の高い過勾配推定器を特徴とする,StocBiOというアルゴリズムを提案する。
stocbio の収束率保証を提供し,条件数 $\kappa$ と目標精度 $\epsilon$ に対して,stocbio が最もよく知られた計算複雑性を順に上回っていることを示す。
さらに, メタラーニングおよびハイパーパラメータ最適化実験により, 理論結果を検証し, バイレベル最適化アルゴリズムの効率を示す。
関連論文リスト
- 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) - Federated Conditional Stochastic Optimization [110.513884892319]
条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。
本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-04T01:47:37Z) - Decentralized Multi-Level Compositional Optimization Algorithms with Level-Independent Convergence Rate [26.676582181833584]
分散化されたマルチレベル最適化は、マルチレベル構造と分散通信のために困難である。
マルチレベル構成問題を最適化する2つの新しい分散最適化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-06-06T00:23:28Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis [12.680169619392695]
この論文は、2レベル最適化アルゴリズムに対する総合収束率解析を提供する。
問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。
そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-07-31T22:05:47Z) - Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。
また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。