論文の概要: 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 が得られることを示す。
まず, 一般のファイン凸対象物に適用した座標降下法を, 新規な証明手法を用いて検証する。
次に,本手法の汎用性を示すために,一般的な座標拡散アルゴリズムをこの問題に還元する。
最後に、我々の主な結果とは対照的に、制約付き最適化問題に適用された座標降下の類似バージョンは収束する必要はないことを示す。
関連論文リスト
- On the Convergence of Semi Unsupervised Calibration through Prior
Adaptation Algorithm [33.54107934148996]
Semi Unsupervised through Prior Adaptation (SUCPA)は、大規模言語モデルで使用される校正アルゴリズムである。
我々はこのアルゴリズムのいくつかの収束特性を力学系の観点から証明する。
論文 参考訳(メタデータ) (2024-01-05T20:04:40Z) - Invex Programs: First Order Algorithms and Their Convergence [66.40124280146863]
Invexプログラムは、固定点ごとに世界最小値が得られる特別な非制約問題である。
そこで我々は,超凸問題における一般収束率を解くために,新しい一階法アルゴリズムを提案する。
提案アルゴリズムは,制約付き凸プログラムを解く最初のアルゴリズムである。
論文 参考訳(メタデータ) (2023-07-10T10:11:01Z) - Non-asymptotic convergence bounds for Sinkhorn iterates and their
gradients: a coupling approach [10.568851068989972]
本稿では,アルゴリズムの効率的な解法を実現するために,元のOT問題であるエントロピックOT問題の緩和に焦点をあてる。
この定式化はSchr"odinger Bridge問題としても知られ、特に最適制御(SOC)と結びつき、人気のあるシンクホーンアルゴリズムで解くことができる。
論文 参考訳(メタデータ) (2023-04-13T13:58:25Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-01-19T04:24:23Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳(メタデータ) (2020-06-24T07:40:31Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
論文 参考訳(メタデータ) (2020-05-15T21:14:22Z) - Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
ランダム化された双対座標の上昇に基づくランダム化されたDykstraスタイルのアルゴリズムを提案する。
座標降下を高速化するために、補間系における既存の勾配法よりも収束特性がよい新しいアルゴリズムを得る。
論文 参考訳(メタデータ) (2020-03-30T20:44:56Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳(メタデータ) (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。