論文の概要: Convergence of Some Convex Message Passing Algorithms to a Fixed Point

• arxiv url: http://arxiv.org/abs/2403.07004v2
• Date: Wed, 5 Jun 2024 12:20:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-07 00:40:47.897105
• Title: Convergence of Some Convex Message Passing Algorithms to a Fixed Point
• Title（参考訳）: 凸メッセージパッシングアルゴリズムの固定点への収束
• Authors: Vaclav Voracek, Tomas Werner,
• Abstract要約: グラフィカルモデルにおけるMAP推論問題に対する一般的なアプローチは、双対線型計画法や(ブロック座標)降下によるラグランジュ緩和から得られる上限を最小化することである。 これは凸/収束メッセージパッシング(convex/convergent message passing)とも呼ばれる。 アルゴリズムは$mathcalO (1/varepsilon)$ iterationsで終了することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A popular approach to the MAP inference problem in graphical models is to minimize an upper bound obtained from a dual linear programming or Lagrangian relaxation by (block-)coordinate descent. This is also known as convex/convergent message passing; examples are max-sum diffusion and sequential tree-reweighted message passing (TRW-S). Convergence properties of these methods are currently not fully understood. They have been proved to converge to the set characterized by local consistency of active constraints, with unknown convergence rate; however, it was not clear if the iterates converge at all (to any point). We prove a stronger result (conjectured before but never proved): the iterates converge to a fixed point of the method. Moreover, we show that the algorithm terminates within $\mathcal{O}(1/\varepsilon)$ iterations. We first prove this for a version of coordinate descent applied to a general piecewise-affine convex objective. Then we show that several convex message passing methods are special cases of this method. Finally, we show that a slightly different version of coordinate descent can cycle.
• Abstract（参考訳）: グラフィカルモデルにおけるMAP推論問題に対する一般的なアプローチは、双対線形計画法や(ブロック-)座標降下によるラグランジュ緩和から得られる上限を最小化することである。 これは凸/収束メッセージパッシング(convex/convergent message passing)とも呼ばれる。 これらの手法の収束特性は、現時点では完全には理解されていない。 それらは、活性制約の局所的な一貫性と未知の収束率によって特徴づけられる集合に収束することが証明された。 より強い結果(先述するが証明されない)を証明し、反復はメソッドの固定点に収束する。 さらに、このアルゴリズムは $\mathcal{O}(1/\varepsilon)$ iterations で終了することを示す。 まず、これを一般のピースワイズ・アフィン凸対象に適用した座標降下のバージョンとして証明する。 次に,複数の凸メッセージパッシング手法が特別な場合であることを示す。 最後に、座標降下のわずかに異なるバージョンがサイクル可能であることを示す。

関連論文リスト

• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [29.56022052936922]
  次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。 本研究ではまず, 次進法における典型的な複雑性を, 対物関数の凸度と弱凸度に拡張する。 ステップサイズの適切な減少規則を用いて,非Lipschitz凸および弱凸目的関数に対する収束結果を提供する。
  論文  参考訳（メタデータ） (2023-05-23T15:26:36Z)
• Convex optimization over a probability simplex [0.0]
  そこで我々は,確率的単純度よりも凸問題を最適化するために,新しい反復スキームCauchy-Simplexを提案する。 Cauchy-Simplex の各イテレーションは単純な操作で構成されており、高次元問題に適している。
  論文  参考訳（メタデータ） (2023-05-15T22:14:22Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
  この楽観的な手法は凸凹点問題の解法として人気が高まっている。 我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
  論文  参考訳（メタデータ） (2022-02-19T20:31:05Z)
• Coordinate Descent Methods for Fractional Minimization [7.716156977428555]
  数値部の対象が微分可能凸非線型関数の和であるような構成された分数凸問題のクラスを考える。 この問題は非滑らか収束であるため難しい。 この問題を解決するための2つの方法を提案する。
  論文  参考訳（メタデータ） (2022-01-30T00:47:04Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
  目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる 新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
  論文  参考訳（メタデータ） (2021-05-13T04:23:07Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Random extrapolation for primal-dual coordinate descent [61.55967255151027]
  本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。 一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
  論文  参考訳（メタデータ） (2020-07-13T17:39:35Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
  ランダム化された双対座標の上昇に基づくランダム化されたDykstraスタイルのアルゴリズムを提案する。 座標降下を高速化するために、補間系における既存の勾配法よりも収束特性がよい新しいアルゴリズムを得る。
  論文  参考訳（メタデータ） (2020-03-30T20:44:56Z)

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

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