論文の概要: Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields

• arxiv url: http://arxiv.org/abs/2107.06028v1
• Date: Tue, 13 Jul 2021 12:31:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-14 20:44:26.295976
• Title: Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields
• Title（参考訳）: ラグランジュ緩和における凸共役の持ち上げ:連続マルコフ確率場に対する扱い可能なアプローチ
• Authors: Hartmut Bauermeister and Emanuel Laude and Thomas M\"ollenhoff and Michael Moeller and Daniel Cremers
• Abstract要約: 断片的な離散化は既存の離散化問題と矛盾しないことを示す。 この理論を2つの画像のマッチング問題に適用する。
• 参考スコア（独自算出の注目度）: 53.31927549039624
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dual decomposition approaches in nonconvex optimization may suffer from a duality gap. This poses a challenge when applying them directly to nonconvex problems such as MAP-inference in a Markov random field (MRF) with continuous state spaces. To eliminate such gaps, this paper considers a reformulation of the original nonconvex task in the space of measures. This infinite-dimensional reformulation is then approximated by a semi-infinite one, which is obtained via a piecewise polynomial discretization in the dual. We provide a geometric intuition behind the primal problem induced by the dual discretization and draw connections to optimization over moment spaces. In contrast to existing discretizations which suffer from a grid bias, we show that a piecewise polynomial discretization better preserves the continuous nature of our problem. Invoking results from optimal transport theory and convex algebraic geometry we reduce the semi-infinite program to a finite one and provide a practical implementation based on semidefinite programming. We show, experimentally and in theory, that the approach successfully reduces the duality gap. To showcase the scalability of our approach, we apply it to the stereo matching problem between two images.
• Abstract（参考訳）: 非凸最適化における双対分解アプローチは双対性ギャップに悩まされる。 これは、連続状態空間を持つマルコフ確率場(MRF)におけるMAP推論のような非凸問題に直接適用する場合に問題となる。 このようなギャップをなくすために,測度空間における元の非凸タスクの再構成を検討する。 この無限次元の再構成は半無限で近似され、双対の多項式離散化によって得られる。 双対離散化によって引き起こされる原始問題の裏にある幾何学的直観を提供し、モーメント空間上の最適化への接続を引き出す。 グリッドバイアスに苦しむ既存の離散化とは対照的に、分割多項式の離散化は問題の連続的性質をよりよく保存することを示す。 最適輸送理論と凸代数幾何学から結果を導き、半無限プログラムを有限プログラムに減らし、半無限計画に基づく実践的な実装を提供する。 実験的および理論的に、このアプローチが双対性ギャップを減少させることを示した。 提案手法のスケーラビリティを示すために,2つの画像間のステレオマッチング問題に適用する。

関連論文リスト

• Performative Reinforcement Learning with Linear Markov Decision Process [14.75815792682734]
  提案手法がマルコフ決定過程の報酬と遷移の両方に影響を及ぼすような表現的強化学習の設定について検討する。 大規模MDPの主要な理論モデルであるEmphlinear Markov決定過程を一般化する。
  論文  参考訳（メタデータ） (2024-11-07T23:04:48Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
  本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。 交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
  論文  参考訳（メタデータ） (2021-09-13T16:13:13Z)
• A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
  深層強化学習のための線形プログラミング(LP)の定式化について検討する。 拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。 深層パラメタライズされたラグランジアン法を提案する。
  論文  参考訳（メタデータ） (2021-05-20T13:08:06Z)
• Non-Convex Exact Community Recovery in Stochastic Block Model [31.221745716673546]
  近年,対称ブロックモデル(SBM)に基づくグラフのコミュニティ検出が注目されている。 この問題の対数的疎度構造において、提案した2段階法は、$mathcalO(nlog2n/loglog n)$ timeにおいて、情報理論の限界まで正確に2つのコミュニティを復元できることを示す。 また, 提案手法の有効性を実証し, 理論的発展を補完するために, 合成データセットと実データセットの両方で数値実験を行った。
  論文  参考訳（メタデータ） (2020-06-29T07:03:27Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)

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

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