論文の概要: Achieving ${O}(\epsilon^{-1.5})$ Complexity in Hessian/Jacobian-free
Stochastic Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2312.03807v2
- Date: Wed, 20 Dec 2023 15:21:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-21 21:25:00.263091
- Title: Achieving ${O}(\epsilon^{-1.5})$ Complexity in Hessian/Jacobian-free
Stochastic Bilevel Optimization
- Title（参考訳）: hessian/jacobian-free確率的二値最適化における${o}(\epsilon^{-1.5})$の複雑性を達成する
- Authors: Yifan Yang, Peiyao Xiao, Kaiyi Ji
- Abstract要約: 我々は,非精度な定常点勾配二値最適化のために,$O(epsilon1.5)$サンプル複雑性を実現する方法を示す。
私たちが知る限り、これは非精度な定常点勾配最適化のために$O(epsilon1.5)$サンプル複雑性を持つ最初のヘッセン/ヤコビアン自由法である。
- 参考スコア（独自算出の注目度）: 21.661676550609876
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we revisit the bilevel optimization problem, in which the
upper-level objective function is generally nonconvex and the lower-level
objective function is strongly convex. Although this type of problem has been
studied extensively, it still remains an open question how to achieve an
${O}(\epsilon^{-1.5})$ sample complexity in Hessian/Jacobian-free stochastic
bilevel optimization without any second-order derivative computation. To fill
this gap, we propose a novel Hessian/Jacobian-free bilevel optimizer named
FdeHBO, which features a simple fully single-loop structure, a projection-aided
finite-difference Hessian/Jacobian-vector approximation, and momentum-based
updates. Theoretically, we show that FdeHBO requires ${O}(\epsilon^{-1.5})$
iterations (each using ${O}(1)$ samples and only first-order gradient
information) to find an $\epsilon$-accurate stationary point. As far as we
know, this is the first Hessian/Jacobian-free method with an
${O}(\epsilon^{-1.5})$ sample complexity for nonconvex-strongly-convex
stochastic bilevel optimization.
- Abstract（参考訳）: 本稿では,上層目標関数が一般に非凸であり,下層目標関数が強凸である二層最適化問題を再検討する。
この種の問題は広く研究されているが、ヘッセン・ヤコビアン自由確率二段階最適化における${O}(\epsilon^{-1.5})$サンプル複雑性を二階微分計算なしでどうやって達成するかは、まだ未解決のままである。
このギャップを埋めるために,単純な完全単一ループ構造,投影支援有限差分ヘッセン/ジャコビアンベクトル近似,運動量に基づく更新を特徴とする,新しいヘッセン/ジャコビアンフリー二レベル最適化器fdehboを提案する。
理論的には、FdeHBO は ${O}(\epsilon^{-1.5})$ iterations (それぞれ ${O}(1)$ sample と 1次勾配情報のみ) を必要とし、$\epsilon$-正確な定常点を求める。
我々が知る限り、これは非凸強凸確率的二値最適化のための${o}(\epsilon^{-1.5})$サンプル複雑性を持つ最初のヘッセン/ヤコビアンフリー法である。
関連論文リスト
- Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - 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) - Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully
First-Order Oracles [14.697733592222658]
1次法は2次法として最適に近い$tilde MathcalO(epsilon-2)$レートで収束可能であることを示す。
さらに,2次定常点を求めるために,類似の収束率を求める単純な1次アルゴリズムを導出する。
論文 参考訳（メタデータ） (2023-06-26T17:07:54Z) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳（メタデータ） (2023-01-26T05:34:21Z) - 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) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - A Newton-CG based barrier method for finding a second-order stationary
point of nonconvex conic optimization with complexity guarantees [0.5922488908114022]
2つの微分可能な関数の交叉を最小限に抑える2階定常点(SOSP)の発見を検討する。
我々の方法は反復であるだけでなく、最もよく知られた複雑性にマッチする$mincal O(epsilon/2)を達成する。
論文 参考訳（メタデータ） (2022-07-12T17:21:45Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。