Minimizing Submodular Discrete Energies by Integer Re-parameterizations - Dr. Tomas Werner

Yandex School of Data Analysis Conference Machine Learning: Prospects and Applications For minimizing discrete energy functions (or MAP inference in graphical models with discrete variables), a successful and widely used approach is the linear programming (LP) relaxation, first proposed by Schlesinger in the 1970s. We typically solve the dual LP, which maximizes a concave lower bound on the true minimum over reparameterizations of the problem. Unfortunately, no algo