論文の概要: Recursive Frank-Wolfe algorithms
- arxiv url: http://arxiv.org/abs/2010.09567v3
- Date: Tue, 19 Jan 2021 15:15:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-05 21:31:30.038832
- Title: Recursive Frank-Wolfe algorithms
- Title（参考訳）: 再帰的フランクウルフアルゴリズム
- Authors: Vladimir Kolmogorov
- Abstract要約: 過去10年間で、ポリトープ上の滑らかな凸関数を最適化するフランク・ウルフ(FW)スタイルの手法への関心が復活した。
最近開発された手法の例としては、 Em Decomposition-invariant Gradient (DiCG)、 em Blended Condition Gradient (BCG)、 em Frank-Wolfe with in-face direction (IF-FW) がある。
まず、エムの作業セット戦略でDiCGを強化し、エムのシャドウを用いた作業セットの最適化方法を示す。
- 参考スコア（独自算出の注目度）: 9.683269364766428
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the last decade there has been a resurgence of interest in Frank-Wolfe
(FW) style methods for optimizing a smooth convex function over a polytope.
Examples of recently developed techniques include {\em Decomposition-invariant
Conditional Gradient} (DiCG), {\em Blended Condition Gradient} (BCG), and {\em
Frank-Wolfe with in-face directions} (IF-FW) methods. We introduce two
extensions of these techniques. First, we augment DiCG with the {\em working
set} strategy, and show how to optimize over the working set using {\em shadow
simplex steps}. Second, we generalize in-face Frank-Wolfe directions to
polytopes in which faces cannot be efficiently computed, and also describe a
generic recursive procedure that can be used in conjunction with several
FW-style techniques. Experimental results indicate that these extensions are
capable of speeding up original algorithms by orders of magnitude for certain
applications.
- Abstract（参考訳）: 過去10年間で、ポリトープ上の滑らかな凸関数を最適化するフランク・ウルフ(FW)スタイルの手法への関心が復活した。
近年開発された手法としては、"em decomposition-invariant conditional gradient} (dicg)、"em blended condition gradient} (bcg)、"em frank-wolfe with in-face directions} (if-fw) などがある。
これらの手法の2つの拡張を紹介する。
まず, dcg を {\em working set} 戦略で拡張し, {\em shadow simplex steps} を用いて作業集合を最適化する方法を示す。
第2に,面を効率的に計算できない多面体に対して面内フランクウルフ方向を一般化し,複数のfwスタイルの手法と併用できる汎用再帰手順を記述する。
実験の結果、これらの拡張は特定の用途で元のアルゴリズムを桁違いに高速化できることが示された。
関連論文リスト
- Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - Sparse Optimization for Unsupervised Extractive Summarization of Long
Documents with the Frank-Wolfe Algorithm [4.786337974720721]
本稿では,特に長い文書について,教師なし抽出文書要約の問題に対処する。
我々は、教師なし問題をスパース自己回帰問題としてモデル化し、凸ノルム制約問題を用いて結果の問題を近似する。
k$文で要約を生成するには、$approx k$を実行すればよいため、非常に効率的である。
論文 参考訳（メタデータ） (2022-08-19T17:17:43Z) - Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and
Beyond [19.544213396776268]
我々は,高次条件場に対する汎用的で効果的なCNNベースライン推論である正規化Frank-Wolfeを導入する。
新しいアルゴリズム、新しいアルゴリズム、新しいデータセット、強力なニューラルネットワークの大幅な改善が示されています。
論文 参考訳（メタデータ） (2021-10-27T20:44:47Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - 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) - Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and
Sparsity [19.24470467199451]
フランク=ウルフのアルゴリズムは最適面の次元にのみ依存する速度で線形に収束することを示す。
ノイズに対する最適解の疎結合性を示すことを証明して、厳密な相補性を動機づける。
論文 参考訳（メタデータ） (2020-05-31T16:48:10Z) - Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization [30.980431848476925]
線形予測・構造を一般化した制約付き有限滑らかサム最小化アルゴリズムを提案する。
提案手法は実装が簡単で,ステップサイズチューニングを必要としない。
オープンソースパッケージで検討されたすべてのメソッドの実装を提供する。
論文 参考訳（メタデータ） (2020-02-27T00:47:21Z) - A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization [60.90222082871258]
本稿では,制約集合上の線形最小化オラクル(LMO)を用いて,制約付き自己調和最小化問題のクラスをカラフルに解く方法を示す。
L-smoothの場合、我々の手法のLMO呼び出し数はFrank-Wolfe法とほぼ同じであることを示す。
論文 参考訳（メタデータ） (2020-02-17T15:28:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。