論文の概要: Alternating Implicit Projected SGD and Its Efficient Variants for
Equality-constrained Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2211.07096v1
- Date: Mon, 14 Nov 2022 03:47:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 17:14:50.611950
- Title: Alternating Implicit Projected SGD and Its Efficient Variants for
Equality-constrained Bilevel Optimization
- Title（参考訳）: 等級制約二値最適化のための交互入射影SGDとその効率的な変数
- Authors: Quan Xiao, Han Shen, Wotao Yin, Tianyi Chen
- Abstract要約: 本稿では、等式制約と制約付き上層問題の両方において、二段階最適化問題を考察する。
等式制約アプローチを活用することにより、第一に、制約のない二段階問題に対して、暗黙射影SGDアプローチを交互に使用する。
- 参考スコア（独自算出の注目度）: 41.10094500516342
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic bilevel optimization, which captures the inherent nested structure
of machine learning problems, is gaining popularity in many recent
applications. Existing works on bilevel optimization mostly consider either
unconstrained problems or constrained upper-level problems. This paper
considers the stochastic bilevel optimization problems with equality
constraints both in the upper and lower levels. By leveraging the special
structure of the equality constraints problem, the paper first presents an
alternating implicit projected SGD approach and establishes the $\tilde{\cal
O}(\epsilon^{-2})$ sample complexity that matches the state-of-the-art
complexity of ALSET \citep{chen2021closing} for unconstrained bilevel problems.
To further save the cost of projection, the paper presents two alternating
implicit projection-efficient SGD approaches, where one algorithm enjoys the
$\tilde{\cal O}(\epsilon^{-2}/T)$ upper-level and ${\cal
O}(\epsilon^{-1.5}/T^{\frac{3}{4}})$ lower-level projection complexity with
${\cal O}(T)$ lower-level batch size, and the other one enjoys $\tilde{\cal
O}(\epsilon^{-1.5})$ upper-level and lower-level projection complexity with
${\cal O}(1)$ batch size. Application to federated bilevel optimization has
been presented to showcase the empirical performance of our algorithms. Our
results demonstrate that equality-constrained bilevel optimization with
strongly-convex lower-level problems can be solved as efficiently as stochastic
single-level optimization problems.
- Abstract（参考訳）: 機械学習問題の固有のネスト構造を捉える確率的二段階最適化は、最近の多くのアプリケーションで人気を集めている。
既存の二段階最適化の研究は、主に制約のない問題や制約された上層問題を考える。
本稿では,上層と下層の両方で等式制約を持つ確率的二段階最適化問題を考察する。
等式制約問題の特殊構造を利用して、まず暗黙的射影SGD法を交互に提示し、非制約双レベル問題に対するALSET \citep{chen2021closing}の最先端複雑さに一致する$\tilde{\cal O}(\epsilon^{-2})$サンプル複雑性を確立する。
プロジェクションのコストをさらに節約するために、この論文は2つの代替的な暗黙的プロジェクション効率のsgdアプローチを提示している。1つのアルゴリズムは、$\tilde{\cal o}(\epsilon^{-2}/t)$ upper-levelと${\cal o}(\epsilon^{-1.5}/t^{\frac{3}{4}})$ low-level projection complexity with ${\cal o}(t)$ lower-level batch size、もう1つは$\tilde{\cal o}(\epsilon^{-1.5})$ upper-level and lower-level projection complexity with ${\cal o}(1)$ batch sizeである。
アルゴリズムの実証的な性能を示すために,フェデレートされた二レベル最適化への応用が提案されている。
この結果から, 強凸低レベル問題による等式制約付き二レベル最適化は, 確率的単一レベル最適化問題と同じくらい効率的に解けることを示した。
関連論文リスト
- Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization [25.438298531555468]
双レベル最適化は、ハイパーラーニング、メタラーニング、強化ラーニングなど、多くの機械学習タスクに広く適用されている。
最適収束$frac1TT(Hessian/BiO法)を軽度条件下で提案する。
バイレベルゲーム超定常数値収束に関するいくつかの実験を行う。
論文 参考訳（メタデータ） (2024-07-25T07:25:06Z) - On Momentum-Based Gradient Methods for Bilevel Optimization with
Nonconvex Lower-Level [25.438298531555468]
バイレベル最適化は機械学習タスクで一般的なプロセスである。
本稿では,両レベルPLゲームにおける非表現問題について検討する。
我々は,既存の最良の結果を$tO(Enabla F(x)leq epsilon$)の係数で改善することを示す。
論文 参考訳（メタデータ） (2023-03-07T14:55:05Z) - On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis [18.08351275534193]
双レベル最適化は、そうでなければ斜め最適化問題の内部構造を明らかにする。
双レベル最適化における共通のゴールは、パラメータの集合の解に暗黙的に依存する超対象である。
論文 参考訳（メタデータ） (2023-01-02T15:09:12Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - 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 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。