Title :
A study of Nesterov´s scheme for Lagrangian decomposition and MAP labeling
Author :
Savchynskyy, Bogdan ; Schmidt, Stefan ; Kappes, Jörg ; Schnörr, Christoph
Author_Institution :
HCI, Heidelberg Univ., Heidelberg, Germany
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.
Keywords :
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; Algorithm design and analysis; Approximation algorithms; Complexity theory; Convergence; Labeling; Optimization; Smoothing methods;
Conference_Titel :
Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on
Conference_Location :
Providence, RI
Print_ISBN :
978-1-4577-0394-2
DOI :
10.1109/CVPR.2011.5995652