論文の概要: A Newton-CG based barrier method for finding a second-order stationary
point of nonconvex conic optimization with complexity guarantees
- arxiv url: http://arxiv.org/abs/2207.05697v1
- Date: Tue, 12 Jul 2022 17:21:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-13 13:57:36.014996
- Title: A Newton-CG based barrier method for finding a second-order stationary
point of nonconvex conic optimization with complexity guarantees
- Title（参考訳）: 複雑性保証付き非凸円錐最適化の2次定常点を求めるNewton-CGに基づく障壁法
- Authors: Chuan He and Zhaosong Lu
- Abstract要約: 2つの微分可能な関数の交叉を最小限に抑える2階定常点(SOSP)の発見を検討する。
我々の方法は反復であるだけでなく、最もよく知られた複雑性にマッチする$mincal O(epsilon/2)を達成する。
- 参考スコア（独自算出の注目度）: 0.5922488908114022
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we consider finding an approximate second-order stationary
point (SOSP) of nonconvex conic optimization that minimizes a twice
differentiable function over the intersection of an affine subspace and a
convex cone. In particular, we propose a Newton-conjugate gradient (Newton-CG)
based barrier method for finding an $(\epsilon,\sqrt{\epsilon})$-SOSP of this
problem. Our method is not only implementable, but also achieves an iteration
complexity of ${\cal O}(\epsilon^{-3/2})$, which matches the best known
iteration complexity of second-order methods for finding an
$(\epsilon,\sqrt{\epsilon})$-SOSP of unconstrained nonconvex optimization. The
operation complexity of $\widetilde{\cal
O}(\epsilon^{-3/2}\min\{n,\epsilon^{-1/4}\})$, measured by the amount of
fundamental operations, is also established for our method.
- Abstract（参考訳）: 本稿では、アフィン部分空間と凸錐の交叉上の2つの微分可能な関数を最小化する非凸錐最適化の近似二階定常点(SOSP)を求める。
特に、この問題の$(\epsilon,\sqrt{\epsilon})$-SOSPを求めるためのニュートン共役勾配(Newton-CG)に基づく障壁法を提案する。
我々の方法は実装可能であるだけでなく、制約のない非凸最適化の$(\epsilon,\sqrt{\epsilon})$-SOSPを見つけるための2階法の最もよく知られた反復複雑性と一致する${\cal O}(\epsilon^{-3/2})$の反復複雑性を達成する。
基本演算量によって測定された$\widetilde{\cal O}(\epsilon^{-3/2}\min\{n,\epsilon^{-1/4}\})$の演算複雑性も本手法のために確立した。
関連論文リスト
- Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。
我々のアルゴリズムは距離を使って複雑さを見積もることができる。
MathO (log d) / EuM4。
DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
論文 参考訳（メタデータ） (2024-06-27T18:38:42Z) - 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) - A Newton-CG based augmented Lagrangian method for finding a second-order
stationary point of nonconvex equality constrained optimization with
complexity guarantees [0.5013248430919224]
まず,制約なし最適化の近似SOSPを求めるNewton-CG法を提案する。
次に,非等式制約最適化のラグランジアン近似SOSPを提案する。
また,本論文では提案手法の優位性を実証した。
論文 参考訳（メタデータ） (2023-01-09T01:39:46Z) - 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 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) - 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) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。