論文の概要: First Order Methods take Exponential Time to Converge to Global
Minimizers of Non-Convex Functions
- arxiv url: http://arxiv.org/abs/2002.12911v2
- Date: Mon, 8 Feb 2021 04:04:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-28 01:37:42.173225
- Title: First Order Methods take Exponential Time to Converge to Global
Minimizers of Non-Convex Functions
- Title(参考訳): 非凸関数の大域最小化器に収束するには指数時間を要する1次法
- Authors: Krishna Reddy Kesari and Jean Honorio
- Abstract要約: 本研究では、非凸函数の基本硬度に関する境界を与える。
パラメータ推定問題は家族識別の問題と等価であることを示す。
- 参考スコア(独自算出の注目度): 28.776950569604026
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Machine learning algorithms typically perform optimization over a class of
non-convex functions. In this work, we provide bounds on the fundamental
hardness of identifying the global minimizer of a non convex function.
Specifically, we design a family of parametrized non-convex functions and
employ statistical lower bounds for parameter estimation. We show that the
parameter estimation problem is equivalent to the problem of function
identification in the given family. We then claim that non convex optimization
is at least as hard as function identification. Jointly, we prove that any
first order method can take exponential time to converge to a global minimizer.
- Abstract(参考訳): 機械学習アルゴリズムは通常、非凸関数のクラスに対して最適化を行う。
本研究では,非凸関数の大域的最小化器を同定する基本的硬さの限界を与える。
具体的には、パラメトリズド非凸関数の族をデザインし、パラメータ推定に統計的下限を用いる。
パラメータ推定問題は与えられた族における関数識別問題と同値であることを示す。
そして、非凸最適化は少なくとも関数識別と同じくらい難しいと主張する。
共同で、任意の一階法が指数関数時間で大域最小化器に収束できることを証明する。
関連論文リスト
- Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳(メタデータ) (2023-01-16T02:57:37Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳(メタデータ) (2022-11-03T12:40:24Z) - Super-Universal Regularized Newton Method [14.670197265564196]
第二導関数あるいは第三導関数のH"古い連続性によって特徴づけられる問題クラスの族を導入する。
本稿では,問題クラスに最適な大域的複雑性境界を持つ自動調整を行うための,簡単な適応探索手法を提案する。
論文 参考訳(メタデータ) (2022-08-11T15:44:56Z) - Coordinate Descent Methods for DC Minimization [12.284934135116515]
差分凸(英: difference-of-Convex、DC)とは、2つの凸関数の差を最小化する問題である。
本稿では,非次元の1次元サブプロブレムを世界規模で提案し,座標の定常点に収束することが保証される。
論文 参考訳(メタデータ) (2021-09-09T12:44:06Z) - Minimax Kernel Machine Learning for a Class of Doubly Robust Functionals [16.768606469968113]
もともと導入された二重頑健なモーメント関数のクラスを考える(Robins et al., 2008)。
このモーメント関数は、ニュアンス関数の推定方程式の構築に使用できることを実証する。
ニュアンス関数の収束速度は、統計学習理論の現代的な手法を用いて解析される。
論文 参考訳(メタデータ) (2021-04-07T05:52:15Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳(メタデータ) (2020-12-22T12:59:30Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳(メタデータ) (2020-12-11T08:28:51Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。