Convergence of Some Convex Message Passing Algorithms to a Fixed Point
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00380162" target="_blank" >RIV/68407700:21230/24:00380162 - isvavai.cz</a>
Result on the web
<a href="https://proceedings.mlr.press/v235/voracek24a.html" target="_blank" >https://proceedings.mlr.press/v235/voracek24a.html</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Convergence of Some Convex Message Passing Algorithms to a Fixed Point
Original language description
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 O(1/ε) 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of Machine Learning Research
ISBN
—
ISSN
2640-3498
e-ISSN
2640-3498
Number of pages
10
Pages from-to
49688-49697
Publisher name
Proceedings of Machine Learning Research
Place of publication
—
Event location
Vienna
Event date
Jul 21, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—