論文の概要: Provably Faster Algorithms for Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2106.04692v1
- Date: Tue, 8 Jun 2021 21:05:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-10 15:18:04.017082
- Title: Provably Faster Algorithms for Bilevel Optimization
- Title(参考訳): バイレベル最適化のためのより高速なアルゴリズム
- Authors: Junjie Yang, Kaiyi Ji, Yingbin Liang
- Abstract要約: バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
- 参考スコア(独自算出の注目度): 54.83583213812667
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization has been widely applied in many important machine
learning applications such as hyperparameter optimization and meta-learning.
Recently, several momentum-based algorithms have been proposed to solve bilevel
optimization problems faster. However, those momentum-based algorithms do not
achieve provably better computational complexity than
$\mathcal{O}(\epsilon^{-2})$ of the SGD-based algorithm. In this paper, we
propose two new algorithms for bilevel optimization, where the first algorithm
adopts momentum-based recursive iterations, and the second algorithm adopts
recursive gradient estimations in nested loops to decrease the variance. We
show that both algorithms achieve the complexity of
$\mathcal{O}(\epsilon^{-1.5})$, which outperforms all existing algorithms by
the order of magnitude. Our experiments validate our theoretical results and
demonstrate the superior empirical performance of our algorithms in
hyperparameter applications. Our codes for MRBO, VRBO and other benchmarks are
available $\text{online}^1$.
- Abstract(参考訳): 双レベル最適化は、ハイパーパラメータ最適化やメタラーニングなど、多くの重要な機械学習アプリケーションに広く応用されている。
近年,二段階最適化問題を高速に解くために,モーメントに基づくアルゴリズムがいくつか提案されている。
しかし、これらの運動量に基づくアルゴリズムは、SGDベースのアルゴリズムの$\mathcal{O}(\epsilon^{-2})$よりも証明可能な計算複雑性を達成できない。
本稿では,二段階最適化のための2つの新しいアルゴリズムを提案する。第1のアルゴリズムはモーメントに基づく再帰的反復を適用し,第2のアルゴリズムはネストループにおける再帰的勾配推定を適用し,分散を減少させる。
両アルゴリズムが$\mathcal{O}(\epsilon^{-1.5})$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
実験は理論結果の検証を行い,ハイパーパラメータ応用におけるアルゴリズムの優れた経験的性能を示す。
MRBO、VRBO、その他のベンチマーク用のコードは、$\text{online}^1$で利用可能です。
関連論文リスト
- Replicable Learning of Large-Margin Halfspaces [50.330457600322084]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。
Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文 参考訳(メタデータ) (2024-02-21T15:06:51Z) - A Single-Loop Algorithm for Decentralized Bilevel Optimization [12.75011523756594]
そこで本研究では,分散化された二段階最適化を低レベルに凸した単一ループアルゴリズムを提案する。
我々のアルゴリズムは完全に単ループであり、過次勾配を近似する際に重い行列ベクトル乗法を必要としない。
解析の結果,提案アルゴリズムはサブ線形収束率が得られることがわかった。
論文 参考訳(メタデータ) (2023-11-15T13:29:49Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Efficient Convex Algorithms for Universal Kernel Learning [50.877957471649395]
カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。
従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。
本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-15T04:57:37Z) - Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。
そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。
我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
論文 参考訳(メタデータ) (2023-01-23T19:13:25Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳(メタデータ) (2021-12-09T02:27:52Z) - Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis [12.680169619392695]
この論文は、2レベル最適化アルゴリズムに対する総合収束率解析を提供する。
問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。
そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-07-31T22:05:47Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Optimal and Practical Algorithms for Smooth and Strongly Convex
Decentralized Optimization [21.555331273873175]
ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。
本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
論文 参考訳(メタデータ) (2020-06-21T11:23:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。