Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing
Bogdan Savchynskyy, Stefan Schmidt, Joerg Kappes, Christoph Schnoerr
We consider the linear programming relaxation of an energy minimization problem for Markov Random Fields. The dual objective of this problem can be treated as a concave and unconstrained, but non-smooth function. The idea of smoothing the objective prior to optimization was recently proposed in a series of papers. Some of them suggested the idea to decrease the amount of smoothing (so called temperature) while getting closer to the optimum. However, no theoretical substantiation was provided. We propose an adaptive smoothing diminishing algorithm based on the duality gap between relaxed primal and dual objectives and demonstrate the efficiency of our approach with a smoothed version of Sequential Tree-Reweighted Message Passing (TRW-S) algorithm. The strategy is applicable to other algorithms as well, avoids adhoc tuning of the smoothing during iterations, and provably guarantees convergence to the optimum.
PDF Link: /papers/12/p746-savchynskyy.pdf
AUTHOR = "Bogdan Savchynskyy
and Stefan Schmidt and Joerg Kappes and Christoph Schnoerr",
TITLE = "Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing",
BOOKTITLE = "Proceedings of the Twenty-Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-12)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2012",
PAGES = "746--755"