Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing

Bogdan Savchynskyy, Stefan Schmidt, Joerg Kappes, Christoph Schnoerr
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:745-754, 2012.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-savchynskyy12a, title = {Efficient {MRF} Energy Minimization via Adaptive Diminishing Smoothing}, author = {Savchynskyy, Bogdan and Schmidt, Stefan and Kappes, Joerg and Schnoerr, Christoph}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {745--754}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/savchynskyy12a/savchynskyy12a.pdf}, url = {https://proceedings.mlr.press/r10/savchynskyy12a.html}, abstract = {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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing %A Bogdan Savchynskyy %A Stefan Schmidt %A Joerg Kappes %A Christoph Schnoerr %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-savchynskyy12a %I PMLR %P 745--754 %U https://proceedings.mlr.press/r10/savchynskyy12a.html %V R10 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Savchynskyy, B., Schmidt, S., Kappes, J. & Schnoerr, C.. (2012). Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:745-754 Available from https://proceedings.mlr.press/r10/savchynskyy12a.html. Reissued by PMLR on 04 October 2026.

Related Material