論文の概要: An Accelerated Gradient Method for Simple Bilevel Optimization with
Convex Lower-level Problem
- arxiv url: http://arxiv.org/abs/2402.08097v1
- Date: Mon, 12 Feb 2024 22:34:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 17:17:56.625344
- Title: An Accelerated Gradient Method for Simple Bilevel Optimization with
Convex Lower-level Problem
- Title（参考訳）: 凸低レベル問題を用いた単純二値最適化のための加速勾配法
- Authors: Jincheng Cao, Ruichen Jiang, Erfan Yazdandoost Hamedani, Aryan
Mokhtari
- Abstract要約: 下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
- 参考スコア（独自算出の注目度）: 17.926211159845224
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we focus on simple bilevel optimization problems, where we
minimize a convex smooth objective function over the optimal solution set of
another convex smooth constrained optimization problem. We present a novel
bilevel optimization method that locally approximates the solution set of the
lower-level problem using a cutting plane approach and employs an accelerated
gradient-based update to reduce the upper-level objective function over the
approximated solution set. We measure the performance of our method in terms of
suboptimality and infeasibility errors and provide non-asymptotic convergence
guarantees for both error criteria. Specifically, when the feasible set is
compact, we show that our method requires at most
$\mathcal{O}(\max\{1/\sqrt{\epsilon_{f}}, 1/\epsilon_g\})$ iterations to find a
solution that is $\epsilon_f$-suboptimal and $\epsilon_g$-infeasible. Moreover,
under the additional assumption that the lower-level objective satisfies the
$r$-th H\"olderian error bound, we show that our method achieves an iteration
complexity of
$\mathcal{O}(\max\{\epsilon_{f}^{-\frac{2r-1}{2r}},\epsilon_{g}^{-\frac{2r-1}{2r}}\})$,
which matches the optimal complexity of single-level convex constrained
optimization when $r=1$.
- Abstract（参考訳）: 本稿では,他方の凸滑らかな制約付き最適化問題の最適解集合上の凸滑らかな対象関数を最小化する,単純二値最適化問題に着目する。
そこで本稿では, カット平面アプローチを用いて, 下層問題の解集合を局所的に近似し, 高速化された勾配に基づく更新を用いて, 近似された解集合上の上層目標関数を減少させる手法を提案する。
提案手法の性能を最適化性および実現不可能性の観点から測定し,両誤差基準に対する非漸近収束保証を提供する。
具体的には、実現可能な集合がコンパクトであるとき、この方法では最大で$\mathcal{o}(\max\{1/\sqrt{\epsilon_{f}}, 1/\epsilon_g\})$の反復が必要であり、$\epsilon_f$-suboptimalと$\epsilon_g$-infeasibleである解を見つける。
さらに、下層の目的が$r$-th H\"olderian の誤差境界を満たすという仮定の下で、我々の手法は$r=1$のときの単一レベルの凸制約最適化の最適複雑さと一致する$\mathcal{O}(\max\{\epsilon_{f}^{-\frac{2r-1}{2r}},\epsilon_{g}^{-\frac{2r-1}{2r}}\})$の反復複雑性を達成することを示す。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Adaptive Mirror Descent Bilevel Optimization [25.438298531555468]
非二段階最適化のためのミラー降下に基づく適応的二段階最適化手法のクラスを提案する。
いくつかの条件下でメソッドを解析し、メソッドが高速なイテレーション数を持つことを証明します。
論文 参考訳（メタデータ） (2023-11-08T08:17:09Z) - Projection-Free Methods for Stochastic Simple Bilevel Optimization with
Convex Lower-level Problem [16.9187409976238]
凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。
低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
論文 参考訳（メタデータ） (2023-08-15T02:37:11Z) - On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis [18.08351275534193]
双レベル最適化は、そうでなければ斜め最適化問題の内部構造を明らかにする。
双レベル最適化における共通のゴールは、パラメータの集合の解に暗黙的に依存する超対象である。
論文 参考訳（メタデータ） (2023-01-02T15:09:12Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - A Conditional Gradient-based Method for Simple Bilevel Optimization with
Convex Lower-level Problem [18.15207779559351]
そこで本稿では, 切削平面による下層問題の解集合を局所的に近似する二段階最適化手法を提案する。
本手法は,二段階問題のクラスについて,最もよく知られた仮定を導出する。
論文 参考訳（メタデータ） (2022-06-17T16:12:47Z) - Optimal Algorithms for Stochastic Multi-Level Compositional Optimization [46.77664277596764]
目的関数が複数の最適でない関数の制限である多段階合成最適化の問題を解く。
また,適応型多レベル分散低減法 (SMVR) を用いることで,同じ複雑性を実現するが,実際はより高速に収束する。
論文 参考訳（メタデータ） (2022-02-15T16:02:32Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。