論文の概要: Boosting Frank-Wolfe by Chasing Gradients

• arxiv url: http://arxiv.org/abs/2003.06369v2
• Date: Tue, 23 Jun 2020 19:24:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-24 02:16:06.114062
• Title: Boosting Frank-Wolfe by Chasing Gradients
• Title（参考訳）: Chasing GradientsによるFrank-Wolfeのブースティング
• Authors: Cyrille W. Combettes and Sebastian Pokutta
• Abstract要約: 本稿では,降下方向をサブルーチンによる負勾配に整合させることにより,Frank-Wolfeアルゴリズムの高速化を提案する。 我々は、一連の計算実験において、反復時間とCPU時間の両方において、その競争上の優位性を実証する。
• 参考スコア（独自算出の注目度）: 26.042029798821375
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Frank-Wolfe algorithm has become a popular first-order optimization algorithm for it is simple and projection-free, and it has been successfully applied to a variety of real-world problems. Its main drawback however lies in its convergence rate, which can be excessively slow due to naive descent directions. We propose to speed up the Frank-Wolfe algorithm by better aligning the descent direction with that of the negative gradient via a subroutine. This subroutine chases the negative gradient direction in a matching pursuit-style while still preserving the projection-free property. Although the approach is reasonably natural, it produces very significant results. We derive convergence rates $\mathcal{O}(1/t)$ to $\mathcal{O}(e^{-\omega t})$ of our method and we demonstrate its competitive advantage both per iteration and in CPU time over the state-of-the-art in a series of computational experiments.
• Abstract（参考訳）: Frank-Wolfeアルゴリズムは、単純かつプロジェクションフリーな一階最適化アルゴリズムとして人気があり、様々な実世界の問題に適用されている。 しかし、その主な欠点は収束速度であり、ナイーブ降下方向のため過度に遅い可能性がある。 本稿では,降下方向をサブルーチンによる負勾配に整合させることにより,Frank-Wolfeアルゴリズムの高速化を提案する。 このサブルーチンは、投影のない特性を維持しながら、一致する追従スタイルの負の勾配方向を追いかける。 アプローチは当然自然だが、非常に重要な結果をもたらす。 我々は,本手法の収束率$\mathcal{o}(1/t)$から$\mathcal{o}(e^{-\omega t})$を導出し,一連の計算実験において,反復とcpu時間の両方において,その競争上の優位性を示す。

関連論文リスト

• Gradient Methods with Online Scaling [19.218484733179356]
  オンライン学習による勾配に基づく手法の収束を加速する枠組みを提案する。 広範に使用される過勾配降下は勾配降下の収束により改善されることを示す。
  論文  参考訳（メタデータ） (2024-11-04T05:04:18Z)
• ELRA: Exponential learning rate adaption gradient descent optimization method [83.88591755871734]
  我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。 本手法の主な考え方は,状況認識による$alphaの適応である。 これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
  論文  参考訳（メタデータ） (2023-09-12T14:36:13Z)
• Reducing Discretization Error in the Frank-Wolfe Method [2.806911268410107]
  Frank-Wolfeアルゴリズムは、構造的に制約された機械学習アプリケーションで一般的な方法である。 この手法の1つの大きな制限は、不安定なジグザグングステップの方向のために加速が難しい収束速度の遅いことである。 最適化された高次離散化スキームを直接適用するマルチステップFrank-Wolfe法と、離散化誤差を低減したLMO-averagingスキームの2つの改善を提案する。
  論文  参考訳（メタデータ） (2023-04-04T00:43:05Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Frank Wolfe Meets Metric Entropy [0.0]
  フランク=ウルフの領域固有かつ容易に推定できる下界を確立する手法を提案する。 次元自由線型上界は、最悪の場合だけでなく、Emph平均の場合も失敗しなければならないことを示す。 また、核標準球にもこの現象が成立する。
  論文  参考訳（メタデータ） (2022-05-17T21:23:36Z)
• Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
  このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。 我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。 数値シミュレーションはアルゴリズムの効率を実証する。
  論文  参考訳（メタデータ） (2022-02-07T21:23:17Z)
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization [111.24899593052851]
  条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。 ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。 1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
  論文  参考訳（メタデータ） (2021-09-18T07:08:11Z)
• Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes [7.734726150561089]
  離散的視点と連続的な視点の両方を用いて投影の計算を高速化するツールキットを開発した。 基数に基づく部分モジュラーポリトープの特別の場合、あるブレグマン射影の計算ランタイムを$Omega(n/log(n))$の係数で改善する。
  論文  参考訳（メタデータ） (2021-06-22T17:29:24Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• 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)

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

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