Name
Abstract | ||
|---|---|---|
We study the MAP-labeling problem for graphical models by optimizing a dual problem obtained by Lagrangian decomposition. In this paper, we focus specifically on Nes-terov's optimal first-order optimization scheme for non-smooth convex programs, that has been studied for a range of other problems in computer vision and machine learning in recent years. We show that in order to obtain an efficiently convergent iteration, this approach should be augmented with a dynamic estimation of a corresponding Lip-schitz constant, leading to a runtime complexity of O(1/?) in terms of the desired precision ?. Additionally, we devise a stopping criterion based on a duality gap as a sound basis for competitive comparison and show how to compute it efficiently. We evaluate our results using the publicly available Middlebury database and a set of computer generated graphical models that highlight specific aspects, along with other state-of-the-art methods for MAP-inference. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/CVPR.2011.5995652 | CVPR |
Keywords | Field | DocType |
computational complexity,computer vision,convex programming,learning (artificial intelligence),Lagrangian decomposition,MAP-labeling problem,Middlebury database,computer generated graphical models,computer vision,duality gap,machine learning,nonsmooth convex programs,optimal first-order optimization scheme,runtime complexity,stopping criterion | Convergence (routing),Approximation algorithm,Mathematical optimization,Duality gap,Algorithm design,Computer science,Duality (optimization),Graphical model,Convex optimization,Computational complexity theory | Conference |
Volume | Issue | ISSN |
2011 | 1 | 1063-6919 |
Citations | PageRank | References |
16 | 0.62 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bogdan Savchynskyy | 1 | 175 | 11.05 |
| Stefan Schmidt | 2 | 154 | 10.01 |
| Jorg Kappes | 3 | 16 | 0.62 |
| Christoph Schnörr | 4 | 3025 | 219.34 |