論文の概要: Continuized Acceleration for Quasar Convex Functions in Non-Convex
Optimization
- arxiv url: http://arxiv.org/abs/2302.07851v1
- Date: Wed, 15 Feb 2023 18:35:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-16 14:14:07.313749
- Title: Continuized Acceleration for Quasar Convex Functions in Non-Convex
Optimization
- Title(参考訳): 非凸最適化における準凸関数の連続加速
- Authors: Jun-Kun Wang and Andre Wibisono
- Abstract要約: クエーサー凸性(英: Quasar convexity)とは、風景が最適でない場合でも、ある一階述語を効率的に関数にすることができる条件である。
クエーサー凸性は特定の条件下では可能であるが、これらの関数のクラスでは加速度は一般には知られていない。
- 参考スコア(独自算出の注目度): 13.427128424538502
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quasar convexity is a condition that allows some first-order methods to
efficiently minimize a function even when the optimization landscape is
non-convex. Previous works develop near-optimal accelerated algorithms for
minimizing this class of functions, however, they require a subroutine of
binary search which results in multiple calls to gradient evaluations in each
iteration, and consequently the total number of gradient evaluations does not
match a known lower bound. In this work, we show that a recently proposed
continuized Nesterov acceleration can be applied to minimizing quasar convex
functions and achieves the optimal bound with a high probability. Furthermore,
we find that the objective functions of training generalized linear models
(GLMs) satisfy quasar convexity, which broadens the applicability of the
relevant algorithms, while known practical examples of quasar convexity in
non-convex learning are sparse in the literature. We also show that if a smooth
and one-point strongly convex, Polyak-Lojasiewicz, or quadratic-growth function
satisfies quasar convexity, then attaining an accelerated linear rate for
minimizing the function is possible under certain conditions, while
acceleration is not known in general for these classes of functions.
- Abstract(参考訳): 擬似凸性 ( Quasar convexity) は、最適化ランドスケープが凸でない場合でも、いくつかの一階法で関数を効率的に最小化できる条件である。
従来の研究では、このクラスの関数を最小化するための近似加速アルゴリズムが開発されていたが、各繰り返しにおける勾配評価を複数呼び出すバイナリサーチのサブルーチンが必要であり、結果として、勾配評価の総数は既知の下界と一致しない。
本研究では,最近提案された連続ネステロフ加速度を準凸関数の最小化に適用し,高い確率で最適境界を達成することを示す。
さらに, 一般化線形モデル(glm)の訓練対象関数はクエーサー凸性を満たすことが判明し, 関連するアルゴリズムの適用性が高まる一方で, 非凸学習におけるクエーサー凸性の実例が文献に乏しい。
また, 平滑かつ一点強凸, ポリアク・ロジャシェヴィチ, あるいは二次成長関数がクエーサー凸性を満たす場合, ある種の条件下では, 関数を最小化するための加速線形速度が得られるが, 加速度は一般には分かっていない。
関連論文リスト
- An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes [17.804065824245402]
機械学習の応用では、各損失関数は非負であり、平方根とその実数値平方根の構成として表すことができる。
本稿では, ガウス・ニュートン法やレフスカルト法を適用して, 滑らかだが非負な関数の平均を最小化する方法を示す。
論文 参考訳(メタデータ) (2024-07-05T08:53:06Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳(メタデータ) (2024-06-28T02:56:22Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳(メタデータ) (2023-06-02T04:21:59Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳(メタデータ) (2023-02-02T10:37:23Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints [3.1044138971639734]
強い凸関数制約を受ける凸関数を最小化するために,高速化された原始双対アルゴリズムを導入する。
特にGoogleのパーソナライズされたPageRank問題では、スパシティ誘導最適化におけるメソッドのパフォーマンスが優れています。
論文 参考訳(メタデータ) (2022-12-21T16:04:53Z) - Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast
Evasion of Non-Degenerate Saddle Points [8.452349885923507]
グラディエントベースの1次凸最適化アルゴリズムは、機械学習タスクを含むさまざまな領域で広く適用可能である。
最適時間の固定時間理論の最近の進歩に触発されて,高速化最適化アルゴリズムを設計するための枠組みを導入する。
非ド・サドル点を許容する関数に対しては、これらのサドル点を避けるのに必要な時間は初期条件すべてに一様有界であることを示す。
論文 参考訳(メタデータ) (2022-12-07T16:36:23Z) - Proximal Subgradient Norm Minimization of ISTA and FISTA [8.261388753972234]
反復収縮保持アルゴリズムのクラスに対する2乗近位次数ノルムは逆2乗率で収束することを示す。
また、高速反復収縮保持アルゴリズム (FISTA) のクラスに対する2乗次次数次ノルムが、逆立方レートで収束するように加速されることも示している。
論文 参考訳(メタデータ) (2022-11-03T06:50:19Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。