# Newton-type Methods for Inference in Higher-Order Markov Random Fields

arXiv: https://arxiv.org/abs/1709.01237 · HTML: https://mlsanity.com/paper/1709.01237/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2017.

## Built on by (most cited first, 1 of 1)

- [Spiking Neural Networks: The Future of Brain-Inspired Computing](https://mlsanity.com/paper/2510.27379/) (2025)

## Abstract (arXiv)

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.