On Coordinate Minimization of Convex Piecewise-Affine Functions
This work addresses a foundational issue in optimization for graphical models, but it is incremental as it builds on existing coordinate minimization approaches without guaranteeing global convergence.
The paper tackles the problem of optimizing convex piecewise-affine functions, which underlies algorithms like max-sum diffusion used in MAP inference, by generalizing max-sum diffusion to a coordinate minimization method that converges to a local consistency condition, serving as a sign relaxation of global optimality.
A popular class of algorithms to optimize the dual LP relaxation of the discrete energy minimization problem (a.k.a.\ MAP inference in graphical models or valued constraint satisfaction) are convergent message-passing algorithms, such as max-sum diffusion, TRW-S, MPLP and SRMP. These algorithms are successful in practice, despite the fact that they are a version of coordinate minimization applied to a convex piecewise-affine function, which is not guaranteed to converge to a global minimizer. These algorithms converge only to a local minimizer, characterized by local consistency known from constraint programming. We generalize max-sum diffusion to a version of coordinate minimization applicable to an arbitrary convex piecewise-affine function, which converges to a local consistency condition. This condition can be seen as the sign relaxation of the global optimality condition.