論文の概要: 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)の訓練対象関数はクエーサー凸性を満たすことが判明し, 関連するアルゴリズムの適用性が高まる一方で, 非凸学習におけるクエーサー凸性の実例が文献に乏しい。
また, 平滑かつ一点強凸, ポリアク・ロジャシェヴィチ, あるいは二次成長関数がクエーサー凸性を満たす場合, ある種の条件下では, 関数を最小化するための加速線形速度が得られるが, 加速度は一般には分かっていない。
関連論文リスト
- A simple uniformly optimal method without line search for convex
optimization [10.963511172615158]
パラメータが優先されていない凸最適化問題の解法として最適収束率を得るには,線探索が過剰であることを示す。
滑らかな凸最適化のために最適な$mathcalO (1/k2)$収束率を達成できるAC-FGMと呼ばれる新しい勾配降下型アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-10-16T05:26:03Z) - 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) - 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) - A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained
Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。
本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。
我々は,新しい数値スケール問題の有効性を実証する。
論文 参考訳(メタデータ) (2020-10-23T05:24:05Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。