論文の概要: A Single-Timescale Stochastic Bilevel Optimization Method
- arxiv url: http://arxiv.org/abs/2102.04671v1
- Date: Tue, 9 Feb 2021 06:35:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-10 15:10:15.717341
- Title: A Single-Timescale Stochastic Bilevel Optimization Method
- Title（参考訳）: 単時間確率二値最適化法
- Authors: Tianyi Chen, Yuejiao Sun, Wotao Yin
- Abstract要約: 本稿では,Single-Timescale stochAstic BiEl Optimization (STABLE) と呼ばれる二段階問題に対する新しい手法を提案する。
双レベル問題において、$epsilon$-stationaryポイントを達成するためには、合計$cal O(epsilon-2)$サンプルが必要であり、強凸の場合、$epsilon$-Optimalソリューションを達成するには$cal O(epsilon-1)$サンプルが必要である。
- 参考スコア（独自算出の注目度）: 34.868681953242934
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic bilevel optimization generalizes the classic stochastic
optimization from the minimization of a single objective to the minimization of
an objective function that depends the solution of another optimization
problem. Recently, stochastic bilevel optimization is regaining popularity in
emerging machine learning applications such as hyper-parameter optimization and
model-agnostic meta learning. To solve this class of stochastic optimization
problems, existing methods require either double-loop or two-timescale updates,
which are sometimes less efficient. This paper develops a new optimization
method for a class of stochastic bilevel problems that we term Single-Timescale
stochAstic BiLevEl optimization (STABLE) method. STABLE runs in a single loop
fashion, and uses a single-timescale update with a fixed batch size. To achieve
an $\epsilon$-stationary point of the bilevel problem, STABLE requires ${\cal
O}(\epsilon^{-2})$ samples in total; and to achieve an $\epsilon$-optimal
solution in the strongly convex case, STABLE requires ${\cal O}(\epsilon^{-1})$
samples. To the best of our knowledge, this is the first bilevel optimization
algorithm achieving the same order of sample complexity as the stochastic
gradient descent method for the single-level stochastic optimization.
- Abstract（参考訳）: 確率的双レベル最適化は古典的確率的最適化を1つの目的の最小化から別の最適化問題の解に依存する目的関数の最小化に一般化する。
近年,ハイパーパラメータ最適化やモデル非依存なメタ学習といった新興機械学習アプリケーションでは,確率的二段階最適化が人気を回復している。
確率最適化のこのクラスを解決するには、既存のメソッドは二重ループまたは2時間スケールの更新が必要です。
本稿では,Single-Timescale stochAstic BiLevEl optimization (STABLE) と呼ばれる確率的二段階問題に対する新たな最適化手法を提案する。
STABLEは単一のループ形式で動作し、バッチサイズを固定した単一タイムスケール更新を使用する。
双レベル問題の$\epsilon$-定常点を達成するためには、STABLEは${\cal O}(\epsilon^{-2})$サンプルを合計で要求し、強凸の場合において$\epsilon$-optimalソリューションを達成するためには、${\cal O}(\epsilon^{-1})$サンプルを必要とする。
我々の知る限りでは、これは単階確率最適化における確率勾配降下法と同一量のサンプル複雑性を達成する最初の二段階最適化アルゴリズムである。
関連論文リスト
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - Contextual Stochastic Bilevel Optimization [50.36775806399861]
文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。
メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
論文 参考訳（メタデータ） (2023-10-27T23:24:37Z) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳（メタデータ） (2023-01-26T05:34:21Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳（メタデータ） (2021-06-21T20:16:40Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。