論文の概要: $k$FW: A Frank-Wolfe style algorithm with stronger subproblem oracles

• arxiv url: http://arxiv.org/abs/2006.16142v2
• Date: Mon, 15 Nov 2021 19:34:49 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-15 15:15:14.330652
• Title: $k$FW: A Frank-Wolfe style algorithm with stronger subproblem oracles
• Title（参考訳）: k$fw:より強力なサブプログレムオラクルを持つフランクウルフスタイルのアルゴリズム
• Authors: Lijun Ding, Jicong Fan, and Madeleine Udell
• Abstract要約: 本稿では,FW(Frank-Wolfe)の新たな変種である$k$FWを提案する。 標準FWは緩やかな収束に苦しむ: 更新方向が制約セットの極端な点の周りを振動するにつれて、しばしばジグザグを繰り返す。 新しい変種である$k$FWは、各イテレーションで2つのより強いサブプロブレムオラクルを使用することでこの問題を克服する。
• 参考スコア（独自算出の注目度）: 34.53447188447357
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper proposes a new variant of Frank-Wolfe (FW), called $k$FW. Standard FW suffers from slow convergence: iterates often zig-zag as update directions oscillate around extreme points of the constraint set. The new variant, $k$FW, overcomes this problem by using two stronger subproblem oracles in each iteration. The first is a $k$ linear optimization oracle ($k$LOO) that computes the $k$ best update directions (rather than just one). The second is a $k$ direction search ($k$DS) that minimizes the objective over a constraint set represented by the $k$ best update directions and the previous iterate. When the problem solution admits a sparse representation, both oracles are easy to compute, and $k$FW converges quickly for smooth convex objectives and several interesting constraint sets: $k$FW achieves finite $\frac{4L_f^3D^4}{\gamma\delta^2}$ convergence on polytopes and group norm balls, and linear convergence on spectrahedra and nuclear norm balls. Numerical experiments validate the effectiveness of $k$FW and demonstrate an order-of-magnitude speedup over existing approaches.
• Abstract（参考訳）: 本稿では,FW(Frank-Wolfe)の新たな変種である$k$FWを提案する。 標準fwは、しばしばzig-zagを反復し、更新方向が制約集合の極端点の周りで振動する。 新しい変種である$k$FWは、各イテレーションで2つのより強いサブプロブレムオラクルを使用することでこの問題を克服する。 1つは$k$線形最適化オラクル($k$LOO)で、$k$最高の更新方向(単に1つではなく)を計算する。 2つ目は$k$の方向検索($k$DS)で、$k$の最良の更新方向と以前の繰り返しで表される制約セットに対する目的を最小化する。 問題解がスパース表現を許容すると、両オラクルは計算しやすく、$k$FWは滑らかな凸対象といくつかの興味深い制約集合に対して素早く収束する: $k$FW は有限$\frac{4L_f^3D^4}{\gamma\delta^2}$ポリトープおよび群ノルム球への収束、スペクトルと核ノルム球への線型収束。 数値実験は、$k$fwの有効性を検証し、既存のアプローチに対して桁違いのスピードアップを示す。

関連論文リスト

• Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
  そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。 我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman [66.23316415757456]
  近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。 しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。 我々は、任意の同変集合をすべてのノードの代わりに隣人と考える拡張、$(k,t)$-FWLを提案する。 N$2-GNN は ZINC-Subset (0.059) で記録破りの結果を達成し、以前の SOTA の成績を 10.6% 上回った。
  論文  参考訳（メタデータ） (2023-06-05T21:35:32Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods [57.050204432302195]
  本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。 我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
  論文  参考訳（メタデータ） (2022-11-03T14:12:51Z)
• Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization [7.197233473373693]
  2つの凸関数の和を最小化する問題を考える。 1つはリプシッツ連続勾配を持ち、オークルを介してアクセスでき、もう1つは「単純」である。 我々は、$tildeO (1/ sqrtepsilon)$ iterationsで$epsilon$prialdual gap(期待して)を達成することができることを示す。
  論文  参考訳（メタデータ） (2022-05-25T13:01:09Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets [27.913569257545554]
  2つの一般的な近似仮定(textitadditive と textitmultiplicative gap error)は、我々の問題には有効ではない。 DMO(textitapproximate dual Oracle)が提案され、ギャップではなく内部積を近似する。 実験結果から,これらの改良された境界でさえ悲観的であり,グラフ構造を持つ実世界の画像に顕著な改善が認められたことが示唆された。
  論文  参考訳（メタデータ） (2021-06-29T19:39:43Z)
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method [54.93433440034386]
  実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。 提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
  論文  参考訳（メタデータ） (2020-10-05T08:16:56Z)

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

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