論文の概要: Oracle Complexity in Nonsmooth Nonconvex Optimization

• arxiv url: http://arxiv.org/abs/2104.06763v1
• Date: Wed, 14 Apr 2021 10:42:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-15 13:05:58.795259
• Title: Oracle Complexity in Nonsmooth Nonconvex Optimization
• Title（参考訳）: 非滑らかな非凸最適化におけるOracleの複雑さ
• Authors: Guy Kornowski, Ohad Shamir
• Abstract要約: 円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。 本稿では,最適化と平滑化次元とのトレードオフを実証する。
• 参考スコア（独自算出の注目度）: 49.088972349825085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is well-known that given a smooth, bounded-from-below, and possibly nonconvex function, standard gradient-based methods can find $\epsilon$-stationary points (with gradient norm less than $\epsilon$) in $\mathcal{O}(1/\epsilon^2)$ iterations. However, many important nonconvex optimization problems, such as those associated with training modern neural networks, are inherently not smooth, making these results inapplicable. In this paper, we study nonsmooth nonconvex optimization from an oracle complexity viewpoint, where the algorithm is assumed to be given access only to local information about the function at various points. We provide two main results (under mild assumptions): First, we consider the problem of getting near $\epsilon$-stationary points. This is perhaps the most natural relaxation of finding $\epsilon$-stationary points, which is impossible in the nonsmooth nonconvex case. We prove that this relaxed goal cannot be achieved efficiently, for any distance and $\epsilon$ smaller than some constants. Our second result deals with the possibility of tackling nonsmooth nonconvex optimization by reduction to smooth optimization: Namely, applying smooth optimization methods on a smooth approximation of the objective function. For this approach, we prove an inherent trade-off between oracle complexity and smoothness: On the one hand, smoothing a nonsmooth nonconvex function can be done very efficiently (e.g., by randomized smoothing), but with dimension-dependent factors in the smoothness parameter, which can strongly affect iteration complexity when plugging into standard smooth optimization methods. On the other hand, these dimension factors can be eliminated with suitable smoothing methods, but only by making the oracle complexity of the smoothing process exponentially large.
• Abstract（参考訳）: 滑らかで有界かつ非凸な関数が与えられたとき、標準勾配法は$\epsilon$-定常点(勾配ノルムが$\epsilon$より小さい)を$\mathcal{O}(1/\epsilon^2)$反復で見つけることができる。 しかし、現代のニューラルネットワークのトレーニングなど、多くの重要な非凸最適化問題は本質的に滑らかではないため、これらの結果は適用できない。 本稿では,非滑らかな非凸最適化をオラクル複雑性の観点から検討し,アルゴリズムが様々な点における関数の局所情報のみにアクセスできると仮定する。 まず、$\epsilon$-stationary point に近い問題を考える。 これはおそらく$\epsilon$-定常点を求める最も自然な緩和であり、非滑らかな非凸の場合では不可能である。 この緩和された目標が、任意の距離といくつかの定数より小さい$\epsilon$に対して、効率的に達成できないことを証明します。 第2の結果は,非滑らかな非凸最適化をスムーズな最適化に還元することで,対象関数のスムーズな近似にスムーズな最適化手法を適用する可能性を扱う。 一方、非滑らかな非凸関数の滑らか化は(例えば、ランダムな滑らか化によって)非常に効率的に行うことができるが、スムースネスパラメータの次元依存因子は、標準的な滑らかな最適化手法に接続する際の反復複雑性に強く影響を与える。 一方、これらの次元因子は適切な平滑化法で排除できるが、平滑化過程のオラクルの複雑さを指数関数的に大きくすることでのみ除去できる。

関連論文リスト

• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
  下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。 我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
  論文  参考訳（メタデータ） (2024-02-12T22:34:53Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [14.413404128420352]
  本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。 提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
  論文  参考訳（メタデータ） (2023-11-18T23:06:33Z)
• 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)
• 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)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [56.92236659731376]
  本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。 決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
  論文  参考訳（メタデータ） (2023-02-07T22:09:20Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Optimal Algorithms for Convex Nested Stochastic Composite Optimization [13.200502573462712]
  凸ネスト複合最適化 (NSCO) は、強化学習およびリスク-逆最適化におけるその応用に多大な注目を集めている。 現在の NSCO アルゴリズムは、ネスト構造を持たない単純な合成最適化問題よりも、桁違いに、オラクルの複雑さが悪化している。 我々は、滑らかで構造化された非滑らかで一般の非滑らかな層関数からなる任意の構成から構成した凸 NSCO 問題に対する順序最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-11-19T19:22:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。