Convergence Rate Analysis of MAP Coordinate Minimization Algorithms
Finding maximum a posteriori (MAP) assignments in graphical models is an important task in many applications. Since the problem is generally hard, linear programming (LP) relaxations are often used. Solving these relaxations efficiently is thus an important practical problem. In recent years, severa...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137615 |
| _version_ | 1811094793094168576 |
|---|---|
| author | Meshi, Ofer Jaakkola, Tommi Globerson, Amir |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Meshi, Ofer Jaakkola, Tommi Globerson, Amir |
| author_sort | Meshi, Ofer |
| collection | MIT |
| description | Finding maximum a posteriori (MAP) assignments in graphical models is an important task in many applications. Since the problem is generally hard, linear programming (LP) relaxations are often used. Solving these relaxations efficiently is thus an important practical problem. In recent years, several authors have proposed message passing updates corresponding to coordinate descent in the dual LP. However, these are generally not guaranteed to converge to a global optimum. One approach to remedy this is to smooth the LP, and perform coordinate descent on the smoothed dual. However, little is known about the convergence rate of this procedure. Here we perform a thorough rate analysis of such schemes and derive primal and dual convergence rates. We also provide a simple dual to primal mapping that yields feasible primal solutions with a guaranteed rate of convergence. Empirical evaluation supports our theoretical claims and shows that the method is highly competitive with state of the art approaches that yield global optima. |
| first_indexed | 2024-09-23T16:05:12Z |
| format | Article |
| id | mit-1721.1/137615 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:05:12Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1376152021-11-06T03:03:20Z Convergence Rate Analysis of MAP Coordinate Minimization Algorithms Meshi, Ofer Jaakkola, Tommi Globerson, Amir Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Finding maximum a posteriori (MAP) assignments in graphical models is an important task in many applications. Since the problem is generally hard, linear programming (LP) relaxations are often used. Solving these relaxations efficiently is thus an important practical problem. In recent years, several authors have proposed message passing updates corresponding to coordinate descent in the dual LP. However, these are generally not guaranteed to converge to a global optimum. One approach to remedy this is to smooth the LP, and perform coordinate descent on the smoothed dual. However, little is known about the convergence rate of this procedure. Here we perform a thorough rate analysis of such schemes and derive primal and dual convergence rates. We also provide a simple dual to primal mapping that yields feasible primal solutions with a guaranteed rate of convergence. Empirical evaluation supports our theoretical claims and shows that the method is highly competitive with state of the art approaches that yield global optima. 2021-11-05T20:26:56Z 2021-11-05T20:26:56Z 2012 2019-05-31T16:11:22Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137615 Meshi, Ofer, Jaakkola, Tommi and Globerson, Amir. 2012. "Convergence Rate Analysis of MAP Coordinate Minimization Algorithms." en https://papers.nips.cc/paper/4754-convergence-rate-analysis-of-map-coordinate-minimization-algorithms Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Neural Information Processing Systems (NIPS) |
| spellingShingle | Meshi, Ofer Jaakkola, Tommi Globerson, Amir Convergence Rate Analysis of MAP Coordinate Minimization Algorithms |
| title | Convergence Rate Analysis of MAP Coordinate Minimization Algorithms |
| title_full | Convergence Rate Analysis of MAP Coordinate Minimization Algorithms |
| title_fullStr | Convergence Rate Analysis of MAP Coordinate Minimization Algorithms |
| title_full_unstemmed | Convergence Rate Analysis of MAP Coordinate Minimization Algorithms |
| title_short | Convergence Rate Analysis of MAP Coordinate Minimization Algorithms |
| title_sort | convergence rate analysis of map coordinate minimization algorithms |
| url | https://hdl.handle.net/1721.1/137615 |
| work_keys_str_mv | AT meshiofer convergencerateanalysisofmapcoordinateminimizationalgorithms AT jaakkolatommi convergencerateanalysisofmapcoordinateminimizationalgorithms AT globersonamir convergencerateanalysisofmapcoordinateminimizationalgorithms |