論文の概要: Deterministic Nonsmooth Nonconvex Optimization
- arxiv url: http://arxiv.org/abs/2302.08300v1
- Date: Thu, 16 Feb 2023 13:57:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-17 13:50:59.485329
- Title: Deterministic Nonsmooth Nonconvex Optimization
- Title（参考訳）: 決定論的非平滑非凸最適化
- Authors: Michael I. Jordan, Guy Kornowski, Tianyi Lin, Ohad Shamir, Manolis
Zampetakis
- Abstract要約: 次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
- 参考スコア（独自算出の注目度）: 94.01526844386977
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the complexity of optimizing nonsmooth nonconvex Lipschitz functions
by producing $(\delta,\epsilon)$-stationary points. Several recent works have
presented randomized algorithms that produce such points using $\tilde
O(\delta^{-1}\epsilon^{-3})$ first-order oracle calls, independent of the
dimension $d$. It has been an open problem as to whether a similar result can
be obtained via a deterministic algorithm. We resolve this open problem,
showing that randomization is necessary to obtain a dimension-free rate. In
particular, we prove a lower bound of $\Omega(d)$ for any deterministic
algorithm. Moreover, we show that unlike smooth or convex optimization, access
to function values is required for any deterministic algorithm to halt within
any finite time.
On the other hand, we prove that if the function is even slightly smooth,
then the dimension-free rate of $\tilde O(\delta^{-1}\epsilon^{-3})$ can be
obtained by a deterministic algorithm with merely a logarithmic dependence on
the smoothness parameter. Motivated by these findings, we turn to study the
complexity of deterministically smoothing Lipschitz functions. Though there are
efficient black-box randomized smoothings, we start by showing that no such
deterministic procedure can smooth functions in a meaningful manner, resolving
an open question. We then bypass this impossibility result for the structured
case of ReLU neural networks. To that end, in a practical white-box setting in
which the optimizer is granted access to the network's architecture, we propose
a simple, dimension-free, deterministic smoothing that provably preserves
$(\delta,\epsilon)$-stationary points. Our method applies to a variety of
architectures of arbitrary depth, including ResNets and ConvNets. Combined with
our algorithm, this yields the first deterministic dimension-free algorithm for
optimizing ReLU networks, circumventing our lower bound.
- Abstract（参考訳）: 非滑らかな非凸リプシッツ関数を$(\delta,\epsilon)$定常点を生成することで最適化する複雑さについて検討する。
いくつかの最近の研究は、$\tilde O(\delta^{-1}\epsilon^{-3})$ 1次オラクル呼び出しを用いて、次元$d$とは独立にそのような点を生成するランダム化アルゴリズムを提示している。
同様の結果が決定論的アルゴリズムで得られるかどうかについては、未解決の問題である。
そこで,自由度を得るにはランダム化が必要であることを示した。
特に、任意の決定論的アルゴリズムに対して$\Omega(d)$の低い境界を証明する。
さらに,スムーズあるいは凸最適化とは異なり,任意の決定論的アルゴリズムが有限時間以内に停止するためには,関数値へのアクセスが必要であることを示す。
一方、関数が少し滑らかであれば、$\tilde O(\delta^{-1}\epsilon^{-3})$の次元自由率は、単に滑らか度パラメータに対数依存した決定論的アルゴリズムによって得られることを証明している。
これらの知見により、決定論的に滑らかなリプシッツ関数の複雑さについて研究する。
効率的なブラックボックスのランダム化平滑化はあるが、そのような決定論的手続きが意味のある方法で機能を円滑にすることができず、オープンな問題を解き明かすことから始める。
そして、reluニューラルネットワークの構造化の場合、この不可能性を回避します。
そこで,ネットワークアーキテクチャへのオプティマイザのアクセスを許可する実用的なホワイトボックス設定では,$(\delta,\epsilon)$-定常点を確実に保存する,単純で次元自由な決定論的スムージングを提案する。
本手法はresnetsやconvnetsを含む任意の深さの様々なアーキテクチャに適用できる。
我々のアルゴリズムと組み合わせることで、ReLUネットワークを最適化し、下界を回避できる最初の決定論的次元自由アルゴリズムが得られる。
関連論文リスト
- Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - On the Complexity of Finding Small Subgradients in Nonsmooth
Optimization [31.714928102950584]
決定論的アルゴリズムにより次元自由度を達成できないことを示す。
関数が凸である場合に、$(delta,epsilon)$-定常点を見つける収束率をどのように改善できるかを示す。
論文 参考訳（メタデータ） (2022-09-21T13:30:00Z) - Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness [26.71898403195793]
非常に滑らかな凸関数を最適化する複雑性について検討する。
正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。
我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
論文 参考訳（メタデータ） (2021-12-02T10:51:43Z) - Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。
本稿では,最適化と平滑化次元とのトレードオフを実証する。
論文 参考訳（メタデータ） (2021-04-14T10:42:45Z) - No quantum speedup over gradient descent for non-smooth convex
optimization [22.16973542453584]
ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。
私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。
下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
論文 参考訳（メタデータ） (2020-10-05T06:32:47Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。