論文の概要: Enhancing Parameter-Free Frank Wolfe with an Extra Subproblem
- arxiv url: http://arxiv.org/abs/2012.05284v1
- Date: Wed, 9 Dec 2020 19:47:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-16 01:50:46.196364
- Title: Enhancing Parameter-Free Frank Wolfe with an Extra Subproblem
- Title（参考訳）: 余剰サブプロブレムを用いたパラメータフリーフランクウルフのエンハンシング
- Authors: Bingcong Li, Lingda Wang, Georgios B. Giannakis, Zhizhen Zhao
- Abstract要約: この研究では、ExtraFWと呼ばれるFrank Wolfe(FW)アルゴリズムの変種を導入し、分析する。
ExtraFWは、予測補正(PC)フォーマットで決定変数が更新されるため、イテレーション毎に活用される勾配のペアである。
他のパラメータフリーなFW変種と比較すると、同じ問題でより高速なレートを持つが、ExtraFWはPCのアップデートによって速度ときめ細かい分析を改善している。
- 参考スコア（独自算出の注目度）: 75.83472151564185
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Aiming at convex optimization under structural constraints, this work
introduces and analyzes a variant of the Frank Wolfe (FW) algorithm termed
ExtraFW. The distinct feature of ExtraFW is the pair of gradients leveraged per
iteration, thanks to which the decision variable is updated in a
prediction-correction (PC) format. Relying on no problem dependent parameters
in the step sizes, the convergence rate of ExtraFW for general convex problems
is shown to be ${\cal O}(\frac{1}{k})$, which is optimal in the sense of
matching the lower bound on the number of solved FW subproblems. However, the
merit of ExtraFW is its faster rate ${\cal O}\big(\frac{1}{k^2} \big)$ on a
class of machine learning problems. Compared with other parameter-free FW
variants that have faster rates on the same problems, ExtraFW has improved
rates and fine-grained analysis thanks to its PC update. Numerical tests on
binary classification with different sparsity-promoting constraints demonstrate
that the empirical performance of ExtraFW is significantly better than FW, and
even faster than Nesterov's accelerated gradient on certain datasets. For
matrix completion, ExtraFW enjoys smaller optimality gap, and lower rank than
FW.
- Abstract（参考訳）: 構造制約下での凸最適化を目指して,frank wolfe (fw) アルゴリズムの変種である extrafw を導入し,解析する。
extrafwの特徴は、決定変数が予測修正(prediction-correction, pc)形式で更新されるため、イテレーション毎に利用される勾配のペアである。
ステップサイズに問題依存パラメータが存在しないことから、一般凸問題に対するExtraFWの収束率は${\cal O}(\frac{1}{k})$と示される。
しかし、ExtraFWの利点は、機械学習問題のクラスにおいてより高速な${\cal O}\big(\frac{1}{k^2} \big)$である。
他のパラメータフリーなFW変種と比較すると、同じ問題でより高速なレートを持つが、ExtraFWはPCのアップデートによって速度ときめ細かい分析を改善している。
空間的制約の異なるバイナリ分類の数値実験により、ExtraFWの実証性能はFWよりも著しく優れており、Nesterovの加速度勾配よりも高速であることが示された。
行列完備化のために、ExtraFWはFWよりも小さい最適性ギャップと低いランクを享受する。
関連論文リスト
- Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文 参考訳（メタデータ） (2023-02-11T07:19:51Z) - Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator [19.24470467199451]
1つの変種はフランク=ウルフの標準的なステップを使用し、もう1つはテキスト・ウェイ・ステップ(AFW)も考慮している。
3つ目は AFW (GAFW) のテキストジオデシック版である
論文 参考訳（メタデータ） (2022-06-19T10:24:12Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Heavy Ball Momentum for Conditional Gradient [67.58002120548566]
条件勾配、別名フランク・ウルフ(FW)アルゴリズムは、機械学習と信号処理の応用において、十分に文書化された利点がある。
この研究は、重い球運動量と、そのFWへの影響を扱う。
FWにおける重い球運動量の有用性を数値解析により実証した。
論文 参考訳（メタデータ） (2021-10-08T16:50:00Z) - Scalable Projection-Free Optimization [7.170441928038049]
プロジェクションフリーのアルゴリズムとして、FW(Frank-Wolfe)は機械学習コミュニティで注目されている。
まず、イテレーションごとに1つのサンプルのみを必要とするスケーラブルなプロジェクションフリー最適化方法を提案します。
次に、凸関数と非客観的関数の両方に対応する分散Frank-Wolfe(FW)フレームワークを開発します。
論文 参考訳（メタデータ） (2021-05-07T22:27:18Z) - $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) - How Does Momentum Help Frank Wolfe? [81.95857252228537]
加速勾配法(AGM)におけるFW型アルゴリズムと運動量との関係を明らかにする。
負の面において、これらの接続は、なぜモーメントがFW型アルゴリズムに効果を示さないのかを示している。
一方、このリンクの背後にある励ましのメッセージは、一連の問題において、FWにとってモーメントが有用であるということだ。
論文 参考訳（メタデータ） (2020-06-19T13:06:00Z) - Self-Concordant Analysis of Frank-Wolfe Algorithms [3.3598755777055374]
ポアソン逆問題 (Poisson inverse problem) や量子状態トモグラフィー (quantum state tomography) など、多くの応用において、損失は非有界曲率を持つ自己協和関数 (SC) によって与えられる。
SC関数の理論を用いて、FW法の新たな適応ステップサイズを提供し、k反復後の大域収束率 O(1/k) を証明する。
論文 参考訳（メタデータ） (2020-02-11T11:30:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。