論文の概要: A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic
- arxiv url: http://arxiv.org/abs/2007.05170v4
- Date: Wed, 8 Jun 2022 05:49:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-11 22:45:10.009769
- Title: A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic
- Title（参考訳）: 2段階最適化のための2時間フレームワーク:複雑度解析とアクタクリティカルへの応用
- Authors: Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang
- Abstract要約: 双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
- 参考スコア（独自算出の注目度）: 142.1492359556374
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper analyzes a two-timescale stochastic algorithm framework for
bilevel optimization. Bilevel optimization is a class of problems which exhibit
a two-level structure, and its goal is to minimize an outer objective function
with variables which are constrained to be the optimal solution to an (inner)
optimization problem. We consider the case when the inner problem is
unconstrained and strongly convex, while the outer problem is constrained and
has a smooth objective function. We propose a two-timescale stochastic
approximation (TTSA) algorithm for tackling such a bilevel problem. In the
algorithm, a stochastic gradient update with a larger step size is used for the
inner problem, while a projected stochastic gradient update with a smaller step
size is used for the outer problem. We analyze the convergence rates for the
TTSA algorithm under various settings: when the outer problem is strongly
convex (resp.~weakly convex), the TTSA algorithm finds an
$\mathcal{O}(K^{-2/3})$-optimal (resp.~$\mathcal{O}(K^{-2/5})$-stationary)
solution, where $K$ is the total iteration number. As an application, we show
that a two-timescale natural actor-critic proximal policy optimization
algorithm can be viewed as a special case of our TTSA framework. Importantly,
the natural actor-critic algorithm is shown to converge at a rate of
$\mathcal{O}(K^{-1/4})$ in terms of the gap in expected discounted reward
compared to a global optimal policy.
- Abstract（参考訳）: 本稿では,2段階最適化のための2段階確率アルゴリズムフレームワークを解析する。
双レベル最適化は、2レベル構造を示す問題のクラスであり、その目標は、(内)最適化問題の最適解となるよう制約された変数を持つ外部目的関数を最小化することである。
内問題に制約がなく,強い凸がある場合,外問題に制約があり,目的関数が滑らかな場合を考える。
このような二段階問題に対処するための2段階確率近似(TTSA)アルゴリズムを提案する。
このアルゴリズムでは、内側の問題にはより大きなステップサイズを持つ確率的勾配更新を用い、外側問題にはより小さなステップサイズで投影された確率的勾配更新を用いる。
TTSAアルゴリズムは,外部問題が強い凸(resp.〜weakly convex)の場合,$\mathcal{O}(K^{-2/3})$-optimal(resp.〜weakly convex)を求める。
~$\mathcal{o}(k^{-2/5})$-stationary)解、ここでは$k$は総イテレーション数である。
アプリケーションとして,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカル・ポリシー最適化アルゴリズムが利用できることを示す。
重要なことに、自然なアクター批判アルゴリズムは、大域的最適ポリシーと比較して、期待される割引報酬のギャップの観点から$\mathcal{O}(K^{-1/4})$で収束することが示されている。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - Functional Constrained Optimization for Risk Aversion and Sparsity
Control [7.561780884831967]
リスクとスパーシリティの要件は、ポートフォリオ最適化、アソート計画、放射線計画など、多くのアプリケーションで同時に実施する必要がある。
本稿では,これらの課題に対して凸あるいはスパース軌道を生成するレベル条件勾配(LCG)法を提案する。
提案手法は,極小勾配を解くための内部条件近似(CGO)を最適値のレベル1セット投影することを示す。
論文 参考訳（メタデータ） (2022-10-11T02:51:51Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。