Abstract
Recent work (Lang et al., 2018) has shown that some popular approximate MAP inference algorithms perform very well when the input instance is stable. The simplest stability condition assumes that the MAP solution does not change at all when some of the pairwise potentials are adversarially perturbed. Unfortunately, this strong condition does not seem to hold in practice. We introduce a significantly more relaxed condition that only requires portions of an input instance to be stable. Under this block stability condition, we prove that the pairwise LP relaxation is persistent on the stable blocks. We complement our theoretical results with an evaluation of real-world examples from computer vision, and we find that these instances have large stable regions.
Original language | English (US) |
---|---|
State | Published - 2020 |
Event | 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019 - Naha, Japan Duration: Apr 16 2019 → Apr 18 2019 |
Conference
Conference | 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019 |
---|---|
Country/Territory | Japan |
City | Naha |
Period | 4/16/19 → 4/18/19 |
ASJC Scopus subject areas
- Artificial Intelligence
- Statistics and Probability