論文の概要: A Sub-sampled Tensor Method for Non-convex Optimization
- arxiv url: http://arxiv.org/abs/1911.10367v3
- Date: Sat, 15 Jul 2023 18:21:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-19 01:15:50.603483
- Title: A Sub-sampled Tensor Method for Non-convex Optimization
- Title(参考訳): 非凸最適化のための部分サンプリングテンソル法
- Authors: Aurelien Lucchi and Jonas Kohler
- Abstract要約: 有限サム構造を持つ滑らかで潜在的に有意な関数の局所最小値を求めるために, 4階正則化モデルを用いる手法を提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a stochastic optimization method that uses a fourth-order
regularized model to find local minima of smooth and potentially non-convex
objective functions with a finite-sum structure. This algorithm uses
sub-sampled derivatives instead of exact quantities. The proposed approach is
shown to find an $(\epsilon_1,\epsilon_2,\epsilon_3)$-third-order critical
point in at most $\bigO\left(\max\left(\epsilon_1^{-4/3}, \epsilon_2^{-2},
\epsilon_3^{-4}\right)\right)$ iterations, thereby matching the rate of
deterministic approaches. In order to prove this result, we derive a novel
tensor concentration inequality for sums of tensors of any order that makes
explicit use of the finite-sum structure of the objective function.
- Abstract(参考訳): 本研究では, 4階正規化モデルを用いて, 有限サム構造を持つ滑らかで非凸な対象関数の局所最小値を求める確率最適化手法を提案する。
このアルゴリズムは正確な量ではなく、サブサンプリングされた微分を用いる。
提案手法は,最大で$\bigo\left(\max\left(\epsilon_1^{-4/3}, \epsilon_2^{-2}, \epsilon_3^{-4}\right)\right)$の3次臨界点を見いだし,決定論的アプローチの速度に一致することを示した。
この結果を証明するために、対象関数の有限サム構造を明示的に利用する任意の順序のテンソルの和に対して、新しいテンソル濃度不等式を導出する。
関連論文リスト
- An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth
Nonconvex Stochastic Optimization [44.065130483176944]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
我々の分析は、最近の進歩を活用できる単純だが強力な集合に基づいている。
論文 参考訳(メタデータ) (2023-07-10T11:56:04Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳(メタデータ) (2023-02-16T13:57:19Z) - 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 [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (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) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - 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) - Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms [21.904012114713428]
第一のFが滑らかで第二のFが非滑らかで近似可能な3つの凸函数の和を考える。
このテンプレート問題には、画像処理や機械学習など、多くの応用がある。
この問題に対して PDDY と呼ぶ新しい原始双対アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-04-03T10:48:01Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。