論文の概要: On the Complexity of Finding Small Subgradients in Nonsmooth
Optimization
- arxiv url: http://arxiv.org/abs/2209.10346v1
- Date: Wed, 21 Sep 2022 13:30:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-22 17:30:16.242847
- Title: On the Complexity of Finding Small Subgradients in Nonsmooth
Optimization
- Title(参考訳): 非平滑最適化における小次数探索の複雑さについて
- Authors: Guy Kornowski, Ohad Shamir
- Abstract要約: 決定論的アルゴリズムにより次元自由度を達成できないことを示す。
関数が凸である場合に、$(delta,epsilon)$-定常点を見つける収束率をどのように改善できるかを示す。
- 参考スコア(独自算出の注目度): 31.714928102950584
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the oracle complexity of producing $(\delta,\epsilon)$-stationary
points of Lipschitz functions, in the sense proposed by Zhang et al. [2020].
While there exist dimension-free randomized algorithms for producing such
points within $\widetilde{O}(1/\delta\epsilon^3)$ first-order oracle calls, we
show that no dimension-free rate can be achieved by a deterministic algorithm.
On the other hand, we point out that this rate can be derandomized for smooth
functions with merely a logarithmic dependence on the smoothness parameter.
Moreover, we establish several lower bounds for this task which hold for any
randomized algorithm, with or without convexity. Finally, we show how the
convergence rate of finding $(\delta,\epsilon)$-stationary points can be
improved in case the function is convex, a setting which we motivate by proving
that in general no finite time algorithm can produce points with small
subgradients even for convex functions.
- Abstract(参考訳): 我々は、zhangらによって提案された意味で、リプシッツ関数の(\delta,\epsilon)$-stationary pointを生成するoracleの複雑さを研究した。
[2020].
そのような点を生成するための次元自由ランダム化アルゴリズムは、$\widetilde{O}(1/\delta\epsilon^3)$ 1次オラクル呼び出しでは存在するが、決定論的アルゴリズムでは次元自由度は達成できない。
一方, この速度は, 滑らか性パラメータの対数依存性だけで, 滑らかな関数に対して分散可能であることを指摘した。
さらに、任意のランダム化アルゴリズムに対して凸性の有無にかかわらず、このタスクのいくつかの下限を設定する。
最後に、関数が凸である場合に、(\delta,\epsilon)$-定常点を求める収束率がいかに改善されるかを示す。
関連論文リスト
- An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth
Nonconvex Stochastic Optimization [44.065130483176944]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
我々の分析は、最近の進歩を活用できる単純だが強力な集合に基づいている。
論文 参考訳(メタデータ) (2023-07-10T11:56:04Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳(メタデータ) (2023-06-03T17:05:13Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳(メタデータ) (2023-02-16T13:57:19Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - 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) - Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。
本稿では,最適化と平滑化次元とのトレードオフを実証する。
論文 参考訳(メタデータ) (2021-04-14T10:42:45Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z) - Randomized Bregman Coordinate Descent Methods for Non-Lipschitz
Optimization [31.474280642125734]
そこで本研究では,新しいテクステンラン化ブレグマン座標降下法(CD)を提案する。
提案手法は$O(epsilon-2n)$であり,$n$は座標のブロック数であることを示す。
論文 参考訳(メタデータ) (2020-01-15T09:57:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。