論文の概要: How Does Momentum Help Frank Wolfe?

• arxiv url: http://arxiv.org/abs/2006.11116v1
• Date: Fri, 19 Jun 2020 13:06:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-19 04:24:39.700914
• Title: How Does Momentum Help Frank Wolfe?
• Title（参考訳）: MomentumはどのようにFrank Wolfe氏を助けるのか?
• Authors: Bingcong Li, Mario Coutino, Georgios B. Giannakis, Geert Leus
• Abstract要約: 加速勾配法(AGM)におけるFW型アルゴリズムと運動量との関係を明らかにする。 負の面において、これらの接続は、なぜモーメントがFW型アルゴリズムに効果を示さないのかを示している。 一方、このリンクの背後にある励ましのメッセージは、一連の問題において、FWにとってモーメントが有用であるということだ。
• 参考スコア（独自算出の注目度）: 81.95857252228537
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We unveil the connections between Frank Wolfe (FW) type algorithms and the momentum in Accelerated Gradient Methods (AGM). On the negative side, these connections illustrate why momentum is unlikely to be effective for FW type algorithms. The encouraging message behind this link, on the other hand, is that momentum is useful for FW on a class of problems. In particular, we prove that a momentum variant of FW, that we term accelerated Frank Wolfe (AFW), converges with a faster rate $\tilde{\cal O}(\frac{1}{k^2})$ on certain constraint sets despite the same ${\cal O}(\frac{1}{k})$ rate as FW on general cases. Given the possible acceleration of AFW at almost no extra cost, it is thus a competitive alternative to FW. Numerical experiments on benchmarked machine learning tasks further validate our theoretical findings.
• Abstract（参考訳）: 我々はfrank wolfe(fw)型アルゴリズムと加速度勾配法(agm)における運動量との関係を明らかにする。 負の面では、これらの接続は、モメンタムがfw型アルゴリズムに効果がない理由を示している。 一方、このリンクの背後にある励ましのメッセージは、一連の問題においてFWにとってモーメントが有用であるということだ。 特に、フランク・ウルフ (AFW) と呼ばれる FW の運動量不変量は、一般の場合において FW と同じ${\cal O}(\frac{1}{k})$ であるにもかかわらず、ある制約集合上ではより高速な$\tilde{\cal O}(\frac{1}{k^2})$ に収束する。 AFWがほぼ余分なコストで加速できることを考えると、これはFWの代替となる。 ベンチマーク機械学習タスクの数値実験は、理論的な知見をさらに検証する。

関連論文リスト

• Federated Frank-Wolfe Algorithm [7.124736158080938]
  制約付き機械学習問題に対するFedFW(Federated FrankWolfe Algorithm)を提案する。 FedFWは、データのプライバシ、イット当たりのコストの低減、疎通信、イテレーションを備えている。 We show that FedFW finds a solution within $O(varepsilon-3)$ in the convex set。
  論文  参考訳（メタデータ） (2024-08-19T15:31:06Z)
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
  Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。 有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
  論文  参考訳（メタデータ） (2023-04-23T20:05:09Z)
• Efficient $\Phi$-Regret Minimization in Extensive-Form Games via Online Mirror Descent [49.93548413166884]
  $Phi$-Hedgeは、正規形式ゲーム(NFG)のための大規模な平衡を学習できる汎用アルゴリズムである。 EFGにおけるNash Equilibria(ゼロサム設定)、Normal-Form Coarse Correlated Equilibria(NFCCE)、Extensive-Form Correlated Equilibria(EFCE)の学習に$Phi$-Hedgeが直接利用できることを示す。 それらの設定において、emph$Phi$-Hedgeアルゴリズムは標準ミラーDescent(OMD)アルゴリズムと等価であることを示す。
  論文  参考訳（メタデータ） (2022-05-30T17:58:06Z)
• Heavy Ball Momentum for Conditional Gradient [67.58002120548566]
  条件勾配、別名フランク・ウルフ(FW)アルゴリズムは、機械学習と信号処理の応用において、十分に文書化された利点がある。 この研究は、重い球運動量と、そのFWへの影響を扱う。 FWにおける重い球運動量の有用性を数値解析により実証した。
  論文  参考訳（メタデータ） (2021-10-08T16:50:00Z)
• Enhancing Parameter-Free Frank Wolfe with an Extra Subproblem [75.83472151564185]
  この研究では、ExtraFWと呼ばれるFrank Wolfe(FW)アルゴリズムの変種を導入し、分析する。 ExtraFWは、予測補正(PC)フォーマットで決定変数が更新されるため、イテレーション毎に活用される勾配のペアである。 他のパラメータフリーなFW変種と比較すると、同じ問題でより高速なレートを持つが、ExtraFWはPCのアップデートによって速度ときめ細かい分析を改善している。
  論文  参考訳（メタデータ） (2020-12-09T19:47:24Z)
• Accelerated Stochastic Gradient-free and Projection-free Methods [37.15461647823691]
  本稿では,STORMの新たな分散化手法に基づいて,ゼロオーダーのFrank-Wolfe (Acc-SZOFW) を提案する。 Acc-SZOFWで必要とされる大きなバッチを緩和するために、新しいSTORMの分散化技術に基づいて、ゼロ階のフランク・ウルフ(Acc-SZOFW*)を高速化する手法を提案する。
  論文  参考訳（メタデータ） (2020-07-16T20:50:15Z)
• $k$FW: A Frank-Wolfe style algorithm with stronger subproblem oracles [34.53447188447357]
  本稿では,FW(Frank-Wolfe)の新たな変種である$k$FWを提案する。 標準FWは緩やかな収束に苦しむ: 更新方向が制約セットの極端な点の周りを振動するにつれて、しばしばジグザグを繰り返す。 新しい変種である$k$FWは、各イテレーションで2つのより強いサブプロブレムオラクルを使用することでこの問題を克服する。
  論文  参考訳（メタデータ） (2020-06-29T16:02:48Z)
• A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization [60.90222082871258]
  本稿では,制約集合上の線形最小化オラクル(LMO)を用いて,制約付き自己調和最小化問題のクラスをカラフルに解く方法を示す。 L-smoothの場合、我々の手法のLMO呼び出し数はFrank-Wolfe法とほぼ同じであることを示す。
  論文  参考訳（メタデータ） (2020-02-17T15:28:31Z)

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

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