Smooth and strong: MAP inference with linear convergence
Ofer Meshi, Mehrdad Mahdavi, Alexander Gerhard Schwing · 2015
Maximum a-posteriori (MAP) inference is an important task for many applica-tions. Although the standard formulation gives rise to a hard combinatorial opti-mization problem, several effective approximations have been proposed and stud-ied in recent years. We focus on linear programming (LP) relaxations, which have achieved state-of-the-art performance in many applications. However, optimiza-tion of the resulting program is in general challenging due to non-smoothness and complex non-separable constraints. Therefore, in this work we study the benefits of augmenting the objective function of the relaxation with strong convexity. Specifically, we introduce strong convex-ity by adding a quadratic term to the LP relaxation objective. We provide theoret-ical guarantees for the resulting programs, bounding the difference between their optimal value and the original optimum. Further, we propose suitable optimization algorithms and analyze their convergence. 1