論文の概要: Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations

• arxiv url: http://arxiv.org/abs/2006.13476v1
• Date: Wed, 24 Jun 2020 04:41:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 09:49:31.598472
• Title: Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• Title（参考訳）: 非凸確率最適化における2次情報:パワーと限界
• Authors: Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, Karthik Sridharan
• Abstract要約: 私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
• 参考スコア（独自算出の注目度）: 54.42518331209581
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We design an algorithm which finds an $\epsilon$-approximate stationary point (with $\|\nabla F(x)\|\le \epsilon$) using $O(\epsilon^{-3})$ stochastic gradient and Hessian-vector products, matching guarantees that were previously available only under a stronger assumption of access to multiple queries with the same random seed. We prove a lower bound which establishes that this rate is optimal and---surprisingly---that it cannot be improved using stochastic $p$th order methods for any $p\ge 2$, even when the first $p$ derivatives of the objective are Lipschitz. Together, these results characterize the complexity of non-convex stochastic optimization with second-order methods and beyond. Expanding our scope to the oracle complexity of finding $(\epsilon,\gamma)$-approximate second-order stationary points, we establish nearly matching upper and lower bounds for stochastic second-order methods. Our lower bounds here are novel even in the noiseless case.
• Abstract（参考訳）: 我々は,$o(\epsilon^{-3})$確率勾配とhessian-vector積を用いて,$\|\nabla f(x)\|\le \epsilon$)の定常点を求めるアルゴリズムを設計した。 この値は任意の$p\ge 2$に対して確率的な$p$thの順序法では改善できないが、目的の最初の$p$微分がLipschitzである場合でも、この値は最適であることを示す下界を証明する。 これらの結果は、非凸確率最適化の複雑さを二階法以下で特徴づける。 スコープを拡大して、$(\epsilon,\gamma)$-approximate second-order stationary pointを見つけるというoracleの複雑さに拡張し、確率的な二階法に対してほぼ一致する上下境界を確立します。 ここでの私たちの下限は、ノイズのないケースでも新規です。

関連論文リスト

• 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)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• 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)
• An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum Optimization [25.21457349137344]
  私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• 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 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 Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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