論文の概要: Accelerated Message Passing for Entropy-Regularized MAP Inference

• arxiv url: http://arxiv.org/abs/2007.00699v1
• Date: Wed, 1 Jul 2020 18:43:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-14 22:43:44.847964
• Title: Accelerated Message Passing for Entropy-Regularized MAP Inference
• Title（参考訳）: エントロピー規則化MAP推論のための高速化メッセージパッシング
• Authors: Jonathan N. Lee, Aldo Pacchiano, Peter Bartlett, Michael I. Jordan
• Abstract要約: 離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
• 参考スコア（独自算出の注目度）: 89.15658822319928
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Maximum a posteriori (MAP) inference in discrete-valued Markov random fields is a fundamental problem in machine learning that involves identifying the most likely configuration of random variables given a distribution. Due to the difficulty of this combinatorial problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms that are often interpreted as coordinate descent on the dual LP. To achieve more desirable computational properties, a number of methods regularize the LP with an entropy term, leading to a class of smooth message passing algorithms with convergence guarantees. In this paper, we present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient methods. The proposed algorithms incorporate the familiar steps of standard smooth message passing algorithms, which can be viewed as coordinate minimization steps. We show that these accelerated variants achieve faster rates for finding $\epsilon$-optimal points of the unregularized problem, and, when the LP is tight, we prove that the proposed algorithms recover the true MAP solution in fewer iterations than standard message passing algorithms.
• Abstract（参考訳）: 離散値マルコフ確率場における最大後続推定(MAP)は、分布が与えられた確率変数の最も可能性の高い構成を特定することを含む機械学習の基本的な問題である。 この組合せ問題の難しさから、線形プログラミング(LP)緩和は、双対LP上の座標降下としてしばしば解釈される特殊なメッセージパッシングアルゴリズムを導出するために一般的に用いられる。 より望ましい計算特性を達成するために、多くの手法がエントロピー項でLPを正規化し、収束保証付きスムーズなメッセージパッシングアルゴリズムのクラスを導いた。 本稿では,古典的加速度勾配法に基づく手法を用いて,これらのアルゴリズムを高速化するためのランダム化手法を提案する。 提案するアルゴリズムは、座標最小化ステップと見なすことができる標準スムースメッセージパッシングアルゴリズムの親しみやすいステップを取り入れている。 これらの高速化された変種は、非正規化問題の最適点$\epsilon$-optimal点を求めるためにより高速な速度を達成できることを示し、LPがきつい場合には、提案アルゴリズムが標準メッセージパッシングアルゴリズムよりも少ないイテレーションで真のMAP解を復元できることを証明した。

関連論文リスト

• From Optimization to Control: Quasi Policy Iteration [3.4376560669160394]
  準政治反復(QPI)と呼ばれる新しい制御アルゴリズムを提案する。 QPIは、政策反復アルゴリズムにおける「ヘシアン」行列の新たな近似に基づいて、MDPに特有の2つの線形構造制約を利用する。 これは、割引係数に対する感度が極めて低い政策反復と同様の実証的な収束挙動を示す。
  論文  参考訳（メタデータ） (2023-11-18T21:00:14Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。 特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
  論文  参考訳（メタデータ） (2023-02-13T19:57:17Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Learning Sparse Graphs via Majorization-Minimization for Smooth Node Signals [8.140698535149042]
  本稿では,その隣接行列を推定することにより,スパース重み付きグラフを学習するアルゴリズムを提案する。 提案アルゴリズムは,本論文におけるいくつかの既存手法よりも,平均反復回数の観点から,より高速に収束することを示す。
  論文  参考訳（メタデータ） (2022-02-06T17:06:13Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• SONIA: A Symmetric Blockwise Truncated Optimization Algorithm [2.9923891863939938]
  本研究は, 経験的リスクに対する新しいアルゴリズムを提案する。 このアルゴリズムは、一部分空間における二階探索型更新を計算し、1階探索法と2階探索法の間のギャップを埋める。
  論文  参考訳（メタデータ） (2020-06-06T19:28:14Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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