Distributed Non-convex ADMM-based inference in large-scale random fields

Ondrej Miksik, Vibhav Vineet, Patrick Pérez and Phillip Torr

In Proceedings British Machine Vision Conference 2014
http://dx.doi.org/10.5244/C.28.4

Abstract

We propose a parallel and distributed algorithm for solving discrete maximum \emph{a posteriori} (MAP) problems in large scale random fields. Our approach is motivated by the following observations: i) very large scale image and video processing problems, such as labeling dozens of million pixels with thousands of labels, are routinely faced in many application domains; ii) The computational complexity of the current state-of-the-art inference algorithms makes them impractical to solve such large scale problems; iii) Modern parallel and distributed systems provide high computation power at low cost. At the core of our algorithm is a tree-based decomposition of the original optimization problem within the alternating direction method of multipliers (ADMM), which allows efficient parallel solving of resulting sub-problems. Additionally, convergence to the global optimum of the linear programming (LP) relaxation of the original discrete problem is theoretically guaranteed. We evaluate the efficiency and accuracy offered by our algorithm on several benchmark low-level vision problems, on both CPU and Nvidia GPU. We consistently achieve a factor of speed-up compared to dual decomposition (DD) approach and other ADMM-based approaches.

Session

Machine Learning

Files

Extended Abstract (PDF, 1 page, 118K)

Paper (PDF, 12 pages, 261K)

Bibtex File

Presentation

Citation

Ondrej Miksik, Vibhav Vineet, Patrick Pérez, and Phillip Torr. Distributed Non-convex ADMM-based inference in large-scale random fields. Proceedings of the British Machine Vision Conference. BMVA Press, September 2014.

BibTex

@inproceedings{BMVC.28.4
	title = {Distributed Non-convex ADMM-based inference in large-scale random fields},
	author = {Miksik, Ondrej and Vineet, Vibhav and Pérez, Patrick and Torr, Phillip},
	year = {2014},
	booktitle = {Proceedings of the British Machine Vision Conference},
	publisher = {BMVA Press},
	editors = {Valstar, Michel and French, Andrew and Pridmore, Tony}
	doi = { http://dx.doi.org/10.5244/C.28.4 }
}