論文の概要: Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
- arxiv url: http://arxiv.org/abs/2002.04130v3
- Date: Mon, 29 Jun 2020 14:53:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 09:49:14.681917
- Title: Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
- Title（参考訳）: 非滑らかな非凸関数の定常点を求める複雑さ
- Authors: Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Ali Jadbabaie, Suvrit
Sra
- Abstract要約: 非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
- 参考スコア（独自算出の注目度）: 84.49087114959872
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide the first non-asymptotic analysis for finding stationary points of
nonsmooth, nonconvex functions. In particular, we study the class of Hadamard
semi-differentiable functions, perhaps the largest class of nonsmooth functions
for which the chain rule of calculus holds. This class contains examples such
as ReLU neural networks and others with non-differentiable activation
functions. We first show that finding an $\epsilon$-stationary point with
first-order methods is impossible in finite time. We then introduce the notion
of $(\delta, \epsilon)$-stationarity, which allows for an
$\epsilon$-approximate gradient to be the convex combination of generalized
gradients evaluated at points within distance $\delta$ to the solution. We
propose a series of randomized first-order methods and analyze their complexity
of finding a $(\delta, \epsilon)$-stationary point. Furthermore, we provide a
lower bound and show that our stochastic algorithm has min-max optimal
dependence on $\delta$. Empirically, our methods perform well for training ReLU
neural networks.
- Abstract（参考訳）: 非滑らかな非凸関数の定常点を求める最初の非漸近解析を提供する。
特に、アダマール半微分可能関数のクラス、おそらくは計算の連鎖則が持つ最大の非滑らかな関数のクラスについて研究する。
このクラスは、ReLUニューラルネットワークや他の非微分可能活性化関数を含む例を含む。
まず、一階法で$\epsilon$-stationary 点を求めることは有限時間で不可能であることを示す。
次に、$(\delta, \epsilon)$-stationarityという概念を導入し、$\epsilon$-approximate gradient を、解との距離$\delta$の点で評価された一般化された勾配の凸結合となるようにする。
ランダム化された一階法の一連の方法を提案し、$(\delta, \epsilon)$-stationary point を求める複雑性を解析する。
さらに、下限を提供し、確率的アルゴリズムが$\delta$にmin-maxの最適依存性を持つことを示す。
この手法は,ReLUニューラルネットワークのトレーニングに有効である。
関連論文リスト
- 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) - Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions [41.43895948769255]
非滑らかな非漸近公正問題のクラスを$min_x[yin Yphi(x, y) - max_zin Zpsix(x, z)]$の形で示す。
本稿では,これらの問題を解く最初の方法であるエンベロープ近似勾配SMAGを提案する。
論文 参考訳（メタデータ） (2024-05-28T20:52:46Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - 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) - On the Complexity of Finding Small Subgradients in Nonsmooth
Optimization [31.714928102950584]
決定論的アルゴリズムにより次元自由度を達成できないことを示す。
関数が凸である場合に、$(delta,epsilon)$-定常点を見つける収束率をどのように改善できるかを示す。
論文 参考訳（メタデータ） (2022-09-21T13:30:00Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Escaping Saddle Points for Nonsmooth Weakly Convex Functions via
Perturbed Proximal Algorithms [0.0]
主な結果は、非滑らか関数に対する$epsilon$-approximate Local minimumの新たな特徴に基づいている。
標準的な仮定では、摂動近位点、摂動近位勾配、摂動近位線形アルゴリズムは非滑らかな凸関数に対して$epsilon$-approximate局所最小値を求める。
論文 参考訳（メタデータ） (2021-02-04T19:17:13Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex
Functions? [31.714928102950584]
有界で滑らかな非函数が与えられたとき、標準勾配法は特定の点を見つけることができることはよく知られている。
おそらく最も自然な緩和は、そのような$ilon$点である点を見つけることである。
論文 参考訳（メタデータ） (2020-02-27T08:26:34Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。