  Linear programming relaxations are central to {\sc map} inference in discrete
Markov Random Fields. The ability to properly solve the Lagrangian dual is a
critical component of such methods. In this paper, we study the benefit of
using Newton-type methods to solve the Lagrangian dual of a smooth version of
the problem. We investigate their ability to achieve superior convergence
behavior and to better handle the ill-conditioned nature of the formulation, as
compared to first order methods. We show that it is indeed possible to
efficiently apply a trust region Newton method for a broad range of {\sc map}
inference problems. In this paper we propose a provably convergent and
efficient framework that includes (i) excellent compromise between
computational complexity and precision concerning the Hessian matrix
construction, (ii) a damping strategy that aids efficient optimization, (iii) a
truncation strategy coupled with a generic pre-conditioner for Conjugate
Gradients, (iv) efficient sum-product computation for sparse clique potentials.
Results for higher-order Markov Random Fields demonstrate the potential of this
approach.
