論文の概要: A Fully First-Order Method for Stochastic Bilevel Optimization

• arxiv url: http://arxiv.org/abs/2301.10945v1
• Date: Thu, 26 Jan 2023 05:34:21 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-27 14:21:44.547858
• Title: A Fully First-Order Method for Stochastic Bilevel Optimization
• Title（参考訳）: 確率的二階最適化のための完全一階法
• Authors: Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, Robert Nowak
• Abstract要約: 一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。 完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。 MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
• 参考スコア（独自算出の注目度）: 8.663726907303303
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider stochastic unconstrained bilevel optimization problems when only the first-order gradient oracles are available. While numerous optimization methods have been proposed for tackling bilevel problems, existing methods either tend to require possibly expensive calculations regarding Hessians of lower-level objectives, or lack rigorous finite-time performance guarantees. In this work, we propose a Fully First-order Stochastic Approximation (F2SA) method, and study its non-asymptotic convergence properties. Specifically, we show that F2SA converges to an $\epsilon$-stationary solution of the bilevel problem after $\epsilon^{-7/2}, \epsilon^{-5/2}$, and $\epsilon^{-3/2}$ iterations (each iteration using $O(1)$ samples) when stochastic noises are in both level objectives, only in the upper-level objective, and not present (deterministic settings), respectively. We further show that if we employ momentum-assisted gradient estimators, the iteration complexities can be improved to $\epsilon^{-5/2}, \epsilon^{-4/2}$, and $\epsilon^{-3/2}$, respectively. We demonstrate even superior practical performance of the proposed method over existing second-order based approaches on MNIST data-hypercleaning experiments.
• Abstract（参考訳）: 一階勾配オラクルのみが利用できる場合の確率的非制約二値最適化問題を考える。 両レベル問題に対処するための多くの最適化手法が提案されているが、既存の手法では、より低レベルな目的のヘッセンについて、あるいは厳密な有限時間性能保証が欠如している場合が多い。 本研究では,完全一階確率近似(f2sa)法を提案し,非漸近収束特性について検討する。 具体的には、F2SA が 2 レベル問題の $\epsilon^{-7/2} と \epsilon^{-5/2} と $\epsilon^{-3/2} の反復(それぞれ$O(1)$サンプルを用いた反復)に収束することを示す。 さらに, 運動量支援勾配推定器を用いる場合, 反復複雑性をそれぞれ$\epsilon^{-5/2}, \epsilon^{-4/2}$, $\epsilon^{-3/2}$に改善できることを示した。 MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。

関連論文リスト

• Adaptive Mirror Descent Bilevel Optimization [25.438298531555468]
  非二段階最適化のためのミラー降下に基づく適応的二段階最適化手法のクラスを提案する。 いくつかの条件下でメソッドを解析し、メソッドが高速なイテレーション数を持つことを証明します。
  論文  参考訳（メタデータ） (2023-11-08T08:17:09Z)
• On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation [13.813242559935732]
  両レベル最適化問題の1次解法について述べる。 特に,ペナルティ関数と超目的物との間に強い関連性を示す。 その結果,O(epsilon-3)$とO(epsilon-5)$が改良された。
  論文  参考訳（メタデータ） (2023-09-04T18:25:43Z)
• 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)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• 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)
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization [94.19177623349947]
  非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。 2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。 GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
  論文  参考訳（メタデータ） (2022-09-12T06:53:24Z)
• Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient [0.0]
  まず,Lipschitz連続勾配 (LLCG) を用いた非拘束凸最適化について検討し,それを解決するための加速近位勾配 (APG) 法を提案する。 提案手法は検証可能な終端基準を備えており、演算複雑性は$cal O(varepsilon-1/2log varepsilon-1)$である。 提案手法の性能を実証するために,予備的な数値計算結果を示す。
  論文  参考訳（メタデータ） (2022-06-02T10:34:26Z)
• 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)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

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

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