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

Hunter Lang, Aravind Reddy, David Sontag, Aravindan Vijayaraghavan
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:3043-3051, 2021.

Abstract

Several works have shown that perturbation stable instances of the MAP inference problem 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-lang21a, title = { Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances }, author = {Lang, Hunter and Reddy, Aravind and Sontag, David and Vijayaraghavan, Aravindan}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {3043--3051}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/lang21a/lang21a.pdf}, url = {https://proceedings.mlr.press/v130/lang21a.html}, abstract = { Several works have shown that perturbation stable instances of the MAP inference problem 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. } }
Endnote
%0 Conference Paper %T Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances %A Hunter Lang %A Aravind Reddy %A David Sontag %A Aravindan Vijayaraghavan %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-lang21a %I PMLR %P 3043--3051 %U https://proceedings.mlr.press/v130/lang21a.html %V 130 %X Several works have shown that perturbation stable instances of the MAP inference problem 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.
APA
Lang, H., Reddy, A., Sontag, D. & Vijayaraghavan, A.. (2021). Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:3043-3051 Available from https://proceedings.mlr.press/v130/lang21a.html.

Related Material