Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing
This work addresses the problem of efficient optimization in computer vision and machine learning, offering a theoretically grounded method for smoothing in MRF energy minimization, though it is incremental as it builds on prior smoothing ideas.
The paper tackles the non-smoothness in energy minimization for Markov Random Fields by proposing an adaptive smoothing diminishing algorithm based on the duality gap, which avoids ad-hoc tuning and provably converges to the optimum, as demonstrated with a smoothed TRW-S algorithm.
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.