Timezone: »

 
Poster
Smooth and Strong: MAP Inference with Linear Convergence
Ofer Meshi · Mehrdad Mahdavi · Alex Schwing

Mon Dec 07 04:00 PM -- 08:59 PM (PST) @ 210 C #78
in Poster Session »

Maximum a-posteriori (MAP) inference is an important task for many applications. Although the standard formulation gives rise to a hard combinatorial optimization problem, several effective approximations have been proposed and studied in recent years. We focus on linear programming (LP) relaxations, which have achieved state-of-the-art performance in many applications. However, optimization 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 convexity by adding a quadratic term to the LP relaxation objective. We provide theoretical 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.

[ PDF] 

Author Information

Ofer Meshi (TTI Chicago)
Mehrdad Mahdavi (TTI Chicago)
Alex Schwing (University of Toronto)

More from the Same Authors