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

• arxiv url: http://arxiv.org/abs/2403.07004v1
• Date: Thu, 7 Mar 2024 13:14:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-14 00:26:44.579400
• Title: Convergence of Some Convex Message Passing Algorithms to a Fixed Point
• Title（参考訳）: 凸メッセージパッシングアルゴリズムの固定点への収束
• Authors: Vaclav Voracek, Tomas Werner
• Abstract要約: グラフィカルモデルにおけるMAP推論問題に対する一般的なアプローチは、双対線型計画法や(ブロック座標)降下によるラグランジュ緩和から得られる上限を最小化することである。 より強い結果(これは以前予想されたが、決して証明されなかった)を証明します。 本研究の主な結果とは対照的に,制約付き最適化問題に適用された座標降下の類似バージョンは収束しないことを示す。
• 参考スコア（独自算出の注目度）: 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. Examples of such algorithms are max-sum diffusion and sequential tree-reweighted message passing. 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 single point). We prove a stronger result (which was conjectured before but never proved): the iterates converge to a fixed point of the algorithm. Moreover, we show that they achieve precision $\varepsilon>0$ in $\mathcal{O}(1/\varepsilon)$ iterations. We first prove this for a version of coordinate descent applied to a general piecewise-affine convex objective, using a novel proof technique. Then we demonstrate the generality of this approach by reducing some popular coordinate-descent algorithms to this problem. Finally we show that, in contrast to our main result, a similar version of coordinate descent applied to a constrained optimization problem need not converge.
• Abstract（参考訳）: グラフィカルモデルにおけるMAP推論問題に対する一般的なアプローチは、双対線形計画法や(ブロック-)座標降下によるラグランジュ緩和から得られる上限を最小化することである。 そのようなアルゴリズムの例としては、最大拡散と逐次木重み付きメッセージパッシングがある。 これらの手法の収束性は現在完全には理解されていない。 それらは、活性制約の局所的な一貫性と未知の収束率によって特徴づけられる集合に収束することが証明されているが、イテレートが(任意の単一点へ)完全に収束するかどうかは明らかではない。 より強い結果(以前は予想されていたが、証明されなかった):イテレートはアルゴリズムの不動点に収束する。 さらに、精度$\varepsilon>0$ in $\mathcal{O}(1/\varepsilon)$ iterations が得られることを示す。 まず, 一般のファイン凸対象物に適用した座標降下法を, 新規な証明手法を用いて検証する。 次に,本手法の汎用性を示すために,一般的な座標拡散アルゴリズムをこの問題に還元する。 最後に、我々の主な結果とは対照的に、制約付き最適化問題に適用された座標降下の類似バージョンは収束する必要はないことを示す。

関連論文リスト

• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
  次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの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)

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

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