論文の概要: Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-start

• arxiv url: http://arxiv.org/abs/2202.03397v4
• Date: Thu, 16 Nov 2023 11:13:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-17 23:11:01.423969
• Title: Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-start
• Title（参考訳）: 低レベル契約による二レベル最適化:ウォームスタートなしの最適サンプル複雑度
• Authors: Riccardo Grazzi, Massimiliano Pontil, Saverio Salzo
• Abstract要約: 目的関数の反復が上層問題であり、下層問題は滑らかな写像の固定点を見つけることである。 いくつかの最近の研究で、下層の問題を温めるアルゴリズムが提案されている。 ウォームスタートなしでは、オーダーワイズ最適サンプルの複雑さを達成できることが示される。
• 参考スコア（独自算出の注目度）: 39.13249645102326
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyse a general class of bilevel problems, in which the upper-level problem consists in the minimization of a smooth objective function and the lower-level problem is to find the fixed point of a smooth contraction map. This type of problems include instances of meta-learning, equilibrium models, hyperparameter optimization and data poisoning adversarial attacks. Several recent works have proposed algorithms which warm-start the lower-level problem, i.e.~they use the previous lower-level approximate solution as a staring point for the lower-level solver. This warm-start procedure allows one to improve the sample complexity in both the stochastic and deterministic settings, achieving in some cases the order-wise optimal sample complexity. However, there are situations, e.g., meta learning and equilibrium models, in which the warm-start procedure is not well-suited or ineffective. In this work we show that without warm-start, it is still possible to achieve order-wise (near) optimal sample complexity. In particular, we propose a simple method which uses (stochastic) fixed point iterations at the lower-level and projected inexact gradient descent at the upper-level, that reaches an $\epsilon$-stationary point using $O(\epsilon^{-2})$ and $\tilde{O}(\epsilon^{-1})$ samples for the stochastic and the deterministic setting, respectively. Finally, compared to methods using warm-start, our approach yields a simpler analysis that does not need to study the coupled interactions between the upper-level and lower-level iterates.
• Abstract（参考訳）: 両レベル問題の一般的なクラスを解析し、上層問題は滑らかな対象関数の最小化であり、下層問題は滑らかな縮約写像の固定点を見つけることである。 この種の問題には、メタラーニング、平衡モデル、ハイパーパラメータ最適化、データ中毒攻撃などがある。 低レベル問題を暖かく開始するアルゴリズム、すなわち、以前の低レベル近似解を低レベル解の凝視点として使用するアルゴリズムが提案されている。 このウォームスタート手順により、確率的および決定論的設定の両方においてサンプル複雑性を改善でき、場合によってはオーダーワイズ最適サンプル複雑性を達成することができる。 しかし、例えばメタラーニングや平衡モデルのような状況があり、ウォームスタート手順が適さないか非効率である。 この研究で、ウォームスタートなしでは、オーダーワイズ(ほぼ)の最適なサンプル複雑性を達成できることが示される。 特に,下層での(確率的な)不動点反復と上層での射影不動勾配勾配を用いた簡単な手法を提案する。これは,確率的および決定論的設定に対してそれぞれ$O(\epsilon^{-2})$および$\tilde{O}(\epsilon^{-1})$サンプルを用いて,$\epsilon$-定常点に達する。 最後に,ウォームスタートを用いた手法と比較して,上層レベルと下層レベルのイテレートの結合相互作用を研究する必要のない,より単純な分析手法を提案する。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
  下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。 我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
  論文  参考訳（メタデータ） (2024-02-12T22:34:53Z)
• A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem [18.15207779559351]
  そこで本稿では, 切削平面による下層問題の解集合を局所的に近似する二段階最適化手法を提案する。 本手法は,二段階問題のクラスについて,最もよく知られた仮定を導出する。
  論文  参考訳（メタデータ） (2022-06-17T16:12:47Z)
• 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 Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates [12.783783498844022]
  目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。 citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。 これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
  論文  参考訳（メタデータ） (2020-08-24T15:57:50Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。