# Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 35 references that are in the map.
- First posted on arXiv 26 Feb 2021.

## Builds on (most cited first, 6 of 6)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Community detection in sparse networks via Grothendieck's inequality](https://mlsanity.com/paper/1411.4686/) (2014)
- [Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut](https://mlsanity.com/paper/1305.1681/) (2013)
- [Partial Optimality by Pruning for MAP-Inference with General Graphical Models](https://mlsanity.com/paper/1410.6641/) (2014)
- [Train and Test Tightness of LP Relaxations in Structured Prediction](https://mlsanity.com/paper/1511.01419/) (2015)
- [Block Stability for MAP Inference](https://mlsanity.com/paper/1810.05305/) (2018)

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

- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)

## Abstract (arXiv)

Several works have shown that perturbation stable instances of the MAP inference problem in Potts models can be solved exactly using a natural linear programming (LP) relaxation. However, most of these works give few (or no) guarantees for the LP solutions on instances that do not satisfy the relatively strict perturbation stability definitions. In this work, we go beyond these stability results by showing that the LP approximately recovers the MAP solution of a stable instance even after the instance is corrupted by noise. This "noisy stable" model realistically fits with practical MAP inference problems: we design an algorithm for finding "close" stable instances, and show that several real-world instances from computer vision have nearby instances that are perturbation stable. These results suggest a new theoretical explanation for the excellent performance of this LP relaxation in practice.