論文の概要: A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2102.07367v1
- Date: Mon, 15 Feb 2021 07:10:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-16 15:55:58.332660
- Title: A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization
- Title（参考訳）: 2レベル最適化のためのモーメンタム支援シングルタイムスケール確率近似アルゴリズム
- Authors: Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang
and Zhuoran Yang
- Abstract要約: 問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
- 参考スコア（独自算出の注目度）: 112.59170319105971
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper proposes a new algorithm -- the Momentum-assisted Single-timescale
Stochastic Approximation (MSTSA) -- for tackling unconstrained bilevel
optimization problems. We focus on bilevel problems where the lower level
subproblem is strongly-convex. Unlike prior works which rely on two timescale
or double loop techniques that track the optimal solution to the lower level
subproblem, we design a stochastic momentum assisted gradient estimator for the
upper level subproblem's updates. The latter allows us to gradually control the
error in stochastic gradient updates due to inaccurate solution to the lower
level subproblem. We show that if the upper objective function is smooth but
possibly non-convex (resp. strongly-convex), MSTSA requires
$\mathcal{O}(\epsilon^{-2})$ (resp. $\mathcal{O}(\epsilon^{-1})$) iterations
(each using constant samples) to find an $\epsilon$-stationary (resp.
$\epsilon$-optimal) solution. This achieves the best-known guarantees for
stochastic bilevel problems. We validate our theoretical results by showing the
efficiency of the MSTSA algorithm on hyperparameter optimization and data
hyper-cleaning problems.
- Abstract（参考訳）: 本稿では、制約のない二段階最適化問題に対処するための新しいアルゴリズム、Momentum-assisted Single-timescale Stochastic Approximation (MSTSA)を提案する。
低レベルサブプロブレムが強凸である2レベル問題に焦点を当てる。
下層サブプロブレムに対する最適解を追跡する2つの時間スケールまたは2重ループ技術に依存する先行研究とは異なり、上層サブプロブレム更新のための確率運動量補助勾配推定器を設計する。
後者は、低レベル部分問題に対する不正確な解のために確率的勾配更新の誤りを徐々に制御できる。
上目的関数が滑らかであるが,非凸(resp)であることを示す。
強凸) MSTSA は $\mathcal{O}(\epsilon^{-2})$ (resp) を必要とする。
$\mathcal{o}(\epsilon^{-1})$) 反復(それぞれ定数サンプルを使用する)は、$\epsilon$-stationary (resp.) を見つける。
$\epsilon$-optimal) ソリューション。
これにより、確率的双レベル問題に対する最もよく知られた保証が得られる。
MSTSAアルゴリズムのハイパーパラメータ最適化およびデータハイパークリーニング問題に対する効率性を示すことにより、理論結果を検証する。
関連論文リスト
- A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
本稿では、上層関数が非定常で、潜在的に非有界な滑らかさを持ち、下層関数が凸であるような二層最適化の問題を考察する。
既存のアルゴリズムはネストループに依存しており、これは重要なチューニング作業を必要とし、実用的ではない。
論文 参考訳（メタデータ） (2024-12-28T04:40:27Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - 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) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - A Single-Timescale Stochastic Bilevel Optimization Method [34.868681953242934]
本稿では,Single-Timescale stochAstic BiEl Optimization (STABLE) と呼ばれる二段階問題に対する新しい手法を提案する。
双レベル問題において、$epsilon$-stationaryポイントを達成するためには、合計$cal O(epsilon-2)$サンプルが必要であり、強凸の場合、$epsilon$-Optimalソリューションを達成するには$cal O(epsilon-1)$サンプルが必要である。
論文 参考訳（メタデータ） (2021-02-09T06:35:30Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - 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) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。