Optimality of approximate inference algorithms on stable instances

Hunter Lang; David Sontag; Aravindan Vijayaraghavan

Optimality of approximate inference algorithms on stable instances

Hunter Lang, David Sontag, Aravindan Vijayaraghavan

Computer Science

Research output: Contribution to conference › Paper › peer-review

7 Scopus citations

Abstract

Approximate algorithms for structured prediction problems—such as LP relaxations and the popular α-expansion algorithm (Boykov et al. 2001)—typically far exceed their theoretical performance guarantees on real-world instances. These algorithms often find solutions that are very close to optimal. The goal of this paper is to partially explain the performance of α-expansion and an LP relaxation algorithm on MAP inference in Ferromagnetic Potts models (FPMs). Our main results give stability conditions under which these two algorithms provably recover the optimal MAP solution. These theoretical results complement numerous empirical observations of good performance.

Original language	English (US)
Pages	1157-1166
Number of pages	10
State	Published - Jan 1 2018
Event	21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018 - Playa Blanca, Lanzarote, Canary Islands, Spain Duration: Apr 9 2018 → Apr 11 2018

Conference

Conference	21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018
Country/Territory	Spain
City	Playa Blanca, Lanzarote, Canary Islands
Period	4/9/18 → 4/11/18

ASJC Scopus subject areas

Statistics and Probability
Artificial Intelligence

Cite this

@conference{c7dbf6d4c34c4857862a1e596a4d0b52,

title = "Optimality of approximate inference algorithms on stable instances",

abstract = "Approximate algorithms for structured prediction problems—such as LP relaxations and the popular α-expansion algorithm (Boykov et al. 2001)—typically far exceed their theoretical performance guarantees on real-world instances. These algorithms often find solutions that are very close to optimal. The goal of this paper is to partially explain the performance of α-expansion and an LP relaxation algorithm on MAP inference in Ferromagnetic Potts models (FPMs). Our main results give stability conditions under which these two algorithms provably recover the optimal MAP solution. These theoretical results complement numerous empirical observations of good performance.",

author = "Hunter Lang and David Sontag and Aravindan Vijayaraghavan",

year = "2018",

month = jan,

day = "1",

language = "English (US)",

pages = "1157--1166",

note = "21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018 ; Conference date: 09-04-2018 Through 11-04-2018",

}

TY - CONF

T1 - Optimality of approximate inference algorithms on stable instances

AU - Lang, Hunter

AU - Sontag, David

AU - Vijayaraghavan, Aravindan

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Approximate algorithms for structured prediction problems—such as LP relaxations and the popular α-expansion algorithm (Boykov et al. 2001)—typically far exceed their theoretical performance guarantees on real-world instances. These algorithms often find solutions that are very close to optimal. The goal of this paper is to partially explain the performance of α-expansion and an LP relaxation algorithm on MAP inference in Ferromagnetic Potts models (FPMs). Our main results give stability conditions under which these two algorithms provably recover the optimal MAP solution. These theoretical results complement numerous empirical observations of good performance.

AB - Approximate algorithms for structured prediction problems—such as LP relaxations and the popular α-expansion algorithm (Boykov et al. 2001)—typically far exceed their theoretical performance guarantees on real-world instances. These algorithms often find solutions that are very close to optimal. The goal of this paper is to partially explain the performance of α-expansion and an LP relaxation algorithm on MAP inference in Ferromagnetic Potts models (FPMs). Our main results give stability conditions under which these two algorithms provably recover the optimal MAP solution. These theoretical results complement numerous empirical observations of good performance.

UR - http://www.scopus.com/inward/record.url?scp=85067811308&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85067811308&partnerID=8YFLogxK

M3 - Paper

SP - 1157

EP - 1166

T2 - 21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018

Y2 - 9 April 2018 through 11 April 2018

ER -

Optimality of approximate inference algorithms on stable instances

Abstract

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this