論文の概要: Solving relaxations of MAP-MRF problems: Combinatorial in-face
Frank-Wolfe directions
- arxiv url: http://arxiv.org/abs/2010.09567v5
- Date: Tue, 25 Apr 2023 03:33:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-27 01:12:36.559616
- Title: Solving relaxations of MAP-MRF problems: Combinatorial in-face
Frank-Wolfe directions
- Title（参考訳）: MAP-MRF問題の緩和:F-Wolfe方向の組合せ
- Authors: Vladimir Kolmogorov
- Abstract要約: MAP-MRF推論問題のLP緩和を解く問題を考察する。
鍵となる計算サブルーチンとして、ポリトープ上の滑らかな凸関数を最小化するためにフランク・ウルフ法(FW)の変種を用いる。
本稿では,このサブルーチンを,面内フランク=ウルフ方向に基づいて効率的に実装することを提案する。
- 参考スコア（独自算出の注目度）: 9.683269364766428
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of solving LP relaxations of MAP-MRF inference
problems, and in particular the method proposed recently in (Swoboda,
Kolmogorov 2019; Kolmogorov, Pock 2021). As a key computational subroutine, it
uses a variant of the Frank-Wolfe (FW) method to minimize a smooth convex
function over a combinatorial polytope. We propose an efficient implementation
of this subproutine based on in-face Frank-Wolfe directions, introduced in
(Freund et al. 2017) in a different context. More generally, we define an
abstract data structure for a combinatorial subproblem that enables in-face FW
directions, and describe its specialization for tree-structured MAP-MRF
inference subproblems. Experimental results indicate that the resulting method
is the current state-of-art LP solver for some classes of problems. Our code is
available at https://pub.ist.ac.at/~vnk/papers/IN-FACE-FW.html.
- Abstract（参考訳）: MAP-MRF推論問題のLP緩和問題,特に最近提案された手法について考察する(Swoboda, Kolmogorov 2019; Kolmogorov, Pock 2021)。
重要な計算サブルーチンとして、FW(Frank-Wolfe)法の変種を用いて、組合せポリトープ上の滑らかな凸関数を最小化する。
本稿では, (freund et al. 2017) において異なる文脈で導入された, 内面的frank-wolfe方向に基づくこのサブプルーチンの効率的な実装を提案する。
より一般的には、合成サブプロブレムの抽象データ構造を定義し、FW方向を表わし、木構造MAP-MRF推論サブプロブレムの特殊化を記述する。
実験の結果,本手法は問題のあるクラスに対する現状のlpソルバであることが判明した。
私たちのコードはhttps://pub.ist.ac.at/~vnk/papers/IN-FACE-FW.htmlで利用可能です。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。