論文の概要: An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm
for First-order and Zeroth-order Optimization
- arxiv url: http://arxiv.org/abs/2109.08858v1
- Date: Sat, 18 Sep 2021 07:08:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-23 11:45:39.157086
- Title: An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm
for First-order and Zeroth-order Optimization
- Title（参考訳）: 1次・0次最適化のための高速可変誘導条件勾配スライディングアルゴリズム
- Authors: Xiyuan Wei, Bin Gu and Heng Huang
- Abstract要約: 条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。
ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。
1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
- 参考スコア（独自算出の注目度）: 111.24899593052851
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The conditional gradient algorithm (also known as the Frank-Wolfe algorithm)
has recently regained popularity in the machine learning community due to its
projection-free property to solve constrained problems. Although many variants
of the conditional gradient algorithm have been proposed to improve
performance, they depend on first-order information (gradient) to optimize.
Naturally, these algorithms are unable to function properly in the field of
increasingly popular zeroth-order optimization, where only zeroth-order
information (function value) is available. To fill in this gap, we propose a
novel Accelerated variance-Reduced Conditional gradient Sliding (ARCS)
algorithm for finite-sum problems, which can use either first-order or
zeroth-order information to optimize. To the best of our knowledge, ARCS is the
first zeroth-order conditional gradient sliding type algorithms solving convex
problems in zeroth-order optimization. In first-order optimization, the
convergence results of ARCS substantially outperform previous algorithms in
terms of the number of gradient query oracle. Finally we validated the
superiority of ARCS by experiments on real-world datasets.
- Abstract（参考訳）: 条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、制約された問題を解くためにプロジェクションフリーな性質のため、機械学習コミュニティで最近人気を取り戻している。
条件勾配アルゴリズムの多くの変種は性能向上のために提案されているが、最適化には1次情報(勾配)に依存する。
当然、これらのアルゴリズムは、ゼロ階情報(関数値)のみが利用可能な、人気の高いゼロ階最適化の分野で適切に機能することができない。
このギャップを埋めるために、有限サム問題に対して、一階情報またはゼロ階情報を用いて最適化できる新しいARCS(Accelerated variance-Reduced Conditional Gradient Sliding)アルゴリズムを提案する。
我々の知る限り、ARCSはゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。
1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
最後に,実世界のデータセットを用いた実験によりARCSの優位性を検証した。
関連論文リスト
- ELRA: Exponential learning rate adaption gradient descent optimization
method [83.88591755871734]
我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。
本手法の主な考え方は,状況認識による$alphaの適応である。
これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
論文 参考訳（メタデータ） (2023-09-12T14:36:13Z) - Ordering for Non-Replacement SGD [7.11967773739707]
我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。
我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。
さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
論文 参考訳（メタデータ） (2023-06-28T00:46:58Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - An Algebraically Converging Stochastic Gradient Descent Algorithm for
Global Optimization [14.336473214524663]
アルゴリズムの主要な構成要素は、目的関数の値に基づくランダム性である。
アルゴリズムの収束を代数学で証明し、パラメータ空間でチューニングする。
アルゴリズムの効率性とロバスト性を示す数値的な例をいくつか提示する。
論文 参考訳（メタデータ） (2022-04-12T16:27:49Z) - Optimal and Practical Algorithms for Smooth and Strongly Convex
Decentralized Optimization [21.555331273873175]
ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。
本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
論文 参考訳（メタデータ） (2020-06-21T11:23:20Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。