論文の概要: Enhanced Bilevel Optimization via Bregman Distance
- arxiv url: http://arxiv.org/abs/2107.12301v1
- Date: Mon, 26 Jul 2021 16:18:43 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-27 15:48:31.399427
- Title: Enhanced Bilevel Optimization via Bregman Distance
- Title（参考訳）: Bregman Distanceによる二レベル最適化
- Authors: Feihu Huang and Heng Huang
- Abstract要約: 本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
- 参考スコア（独自算出の注目度）: 104.96004056928474
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Bilevel optimization has been widely applied many machine learning problems
such as hyperparameter optimization, policy optimization and meta learning.
Although many bilevel optimization methods more recently have been proposed to
solve the bilevel optimization problems, they still suffer from high
computational complexities and do not consider the more general bilevel
problems with nonsmooth regularization. In the paper, thus, we propose a class
of efficient bilevel optimization methods based on Bregman distance. In our
methods, we use the mirror decent iteration to solve the outer subproblem of
the bilevel problem by using strongly-convex Bregman functions. Specifically,
we propose a bilevel optimization method based on Bregman distance (BiO-BreD)
for solving deterministic bilevel problems, which reaches the lower
computational complexities than the best known results. We also propose a
stochastic bilevel optimization method (SBiO-BreD) for solving stochastic
bilevel problems based on the stochastic approximated gradients and Bregman
distance. Further, we propose an accelerated version of SBiO-BreD method
(ASBiO-BreD) by using the variance-reduced technique. Moreover, we prove that
the ASBiO-BreD outperforms the best known computational complexities with
respect to the condition number $\kappa$ and the target accuracy $\epsilon$ for
finding an $\epsilon$-stationary point of nonconvex-strongly-convex bilevel
problems. In particular, our methods can solve the bilevel optimization
problems with nonsmooth regularization with a lower computational complexity.
- Abstract（参考訳）: バイレベル最適化は、ハイパーパラメータ最適化、ポリシー最適化、メタ学習など、多くの機械学習問題に広く適用されている。
より最近の二段階最適化法は二段階最適化問題を解くために提案されているが、それらは依然として高い計算複雑性に悩まされており、非滑らかな正則化に関するより一般的な二段階の問題を考慮していない。
そこで本稿では,ブレグマン距離に基づく効率的な二段階最適化手法のクラスを提案する。
提案手法では, 強凸ブレグマン関数を用いて, 両レベル問題の外的部分確率を解くために, ミラーリーな反復法を用いる。
具体的には,最もよく知られた結果よりも計算複雑度の低い決定論的双レベル問題を解くために,ブレグマン距離(bio-bred)に基づく二値最適化手法を提案する。
また,確率的近似勾配とブレグマン距離に基づく確率的二段階問題の解法として,確率的二段階最適化法(SBiO-BreD)を提案する。
さらに, 分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版を提案する。
さらに、asbio-bred は条件数 $\kappa$ と目標精度 $\epsilon$ に対して最もよく知られた計算複雑性を上回っており、非凸強凸双レベル問題の $\epsilon$-stationary point を見つけることができる。
特に,非滑らかな正規化と計算複雑性の低い二段階最適化問題を解くことができる。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization [25.438298531555468]
双レベル最適化は、ハイパーラーニング、メタラーニング、強化ラーニングなど、多くの機械学習タスクに広く適用されている。
最適収束$frac1TT(Hessian/BiO法)を軽度条件下で提案する。
バイレベルゲーム超定常数値収束に関するいくつかの実験を行う。
論文 参考訳（メタデータ） (2024-07-25T07:25:06Z) - A Single-Loop Algorithm for Decentralized Bilevel Optimization [11.67135350286933]
そこで本研究では,分散化された二段階最適化を低レベルに凸した問題で解くための新しい単一ループアルゴリズムを提案する。
提案手法は,反復毎に2つの行列ベクトル乗算のみを用いることで,過勾配を近似する完全単ループ法である。
解析により,提案アルゴリズムは二段階最適化アルゴリズムにおいて最もよく知られた収束率を実現することを示す。
論文 参考訳（メタデータ） (2023-11-15T13:29:49Z) - Contextual Stochastic Bilevel Optimization [50.36775806399861]
文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。
メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
論文 参考訳（メタデータ） (2023-10-27T23:24:37Z) - 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) - Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis [12.680169619392695]
この論文は、2レベル最適化アルゴリズムに対する総合収束率解析を提供する。
問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。
そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-07-31T22:05:47Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳（メタデータ） (2021-06-21T20:16:40Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。