論文の概要: Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles

• arxiv url: http://arxiv.org/abs/2306.14853v2
• Date: Mon, 28 Aug 2023 04:46:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-29 23:11:50.453516
• Title: Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles
• Title（参考訳）: 完全一階オラクルによる非凸強凸二階最適化
• Authors: Lesi Chen, Yaohua Ma, Jingzhao Zhang
• Abstract要約: 1次法は2次法として最適に近い$tilde MathcalO(epsilon-2)$レートで収束可能であることを示す。 さらに,2次定常点を求めるために,類似の収束率を求める単純な1次アルゴリズムを導出する。
• 参考スコア（独自算出の注目度）: 14.697733592222658
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Bilevel optimization has wide applications such as hyperparameter tuning, neural architecture search, and meta-learning. Designing efficient algorithms for bilevel optimization is challenging because the lower-level problem defines a feasibility set implicitly via another optimization problem. In this work, we consider one tractable case when the lower-level problem is strongly convex. Recent works show that with a Hessian-vector product oracle, one can provably find an $\epsilon$-first-order stationary point within $\tilde{\mathcal{O}}(\epsilon^{-2})$ oracle calls. However, Hessian-vector product may be inaccessible or expensive in practice. Kwon et al. (ICML 2023) addressed this issue by proposing a first-order method that can achieve the same goal at a slower rate of $\tilde{\mathcal{O}}(\epsilon^{-3})$. In this work, we provide a tighter analysis demonstrating that this method can converge at the near-optimal $\tilde {\mathcal{O}}(\epsilon^{-2})$ rate as second-order methods. Our analysis further leads to simple first-order algorithms that achieve similar convergence rates for finding second-order stationary points and for distributed bilevel problems.
• Abstract（参考訳）: 双レベル最適化は、ハイパーパラメータチューニング、ニューラルアーキテクチャサーチ、メタラーニングといった幅広い応用がある。 双レベル最適化のための効率的なアルゴリズムの設計は、低レベル問題が他の最適化問題を通して暗黙的に実現可能性を定義するため、難しい。 本研究では,下級問題が強い凸である場合,一つの扱いやすい場合を考える。 最近の研究によると、ヘッセン・ベクター製品oracleでは、$\tilde{\mathcal{o}}(\epsilon^{-2})$ oracleコール内に$\epsilon$-first-order stationary pointが確実に見つかる。 しかし、ヘシアンベクターの製品は実際には到達できないか高価である。 Kwon et al. (ICML 2023) は、$\tilde{\mathcal{O}}(\epsilon^{-3})$の遅い速度で同じ目標を達成する一階法を提案し、この問題に対処した。 本研究では,この手法が二次法として最適に近い$\tilde {\mathcal{o}}(\epsilon^{-2})$率で収束することを示す,より厳密な解析を行う。 さらに,2次定常点の探索と分散二段階問題に対する類似の収束率を実現するための単純な一階法アルゴリズムを導出する。

関連論文リスト

• First-Order Methods for Linearly Constrained Bilevel Optimization [38.19659447295665]
  本稿では,高次ヘッセン計算に対する一階線形制約最適化手法を提案する。 線形不等式制約に対しては、$widetildeO(ddelta-1 epsilon-3)$ gradient oracle callにおいて$(delta,epsilon)$-Goldstein固定性を得る。
  論文  参考訳（メタデータ） (2024-06-18T16:41:21Z)
• Achieving ${O}(\epsilon^{-1.5})$ Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization [21.661676550609876]
  我々は,非精度な定常点勾配二値最適化のために,$O(epsilon1.5)$サンプル複雑性を実現する方法を示す。 私たちが知る限り、これは非精度な定常点勾配最適化のために$O(epsilon1.5)$サンプル複雑性を持つ最初のヘッセン/ヤコビアン自由法である。
  論文  参考訳（メタデータ） (2023-12-06T16:34:58Z)
• Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem [16.9187409976238]
  凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。 低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
  論文  参考訳（メタデータ） (2023-08-15T02:37:11Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• 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)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。 この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。 我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-19T16:04:40Z)
• 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)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)

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

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