Tightness of LP Relaxations for Almost Balanced Models
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics
MetadataShow full item record
Weller, A., Rowland, M., & Sontag, D. (2016). Tightness of LP Relaxations for Almost Balanced Models. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 47-55. https://www.repository.cam.ac.uk/handle/1810/255938
This is the author accepted manuscript. The final version is available from MIcrotome Publishing via http://www.jmlr.org/proceedings/papers/v51/weller16b.html.
Linear programming (LP) relaxations are widely used to attempt to identify a most likely configuration of a discrete graphical model. In some cases, the LP relaxation attains an optimum vertex at an integral location and thus guarantees an exact solution to the original optimization problem. When this occurs, we say that the LP relaxation is tight. Here we consider binary pairwise models and derive sufficient conditions for guaranteed tightness of (i) the standard LP relaxation on the local polytope LP+LOC, and (ii) the LP relaxation on the triplet-consistent polytope LP+TRI (the next level in the Sherali-Adams hierarchy). We provide simple new proofs of earlier results and derive significant novel results including that LP+TRI is tight for any model where each block is balanced or almost balanced, and a decomposition theorem that may be used to break apart complex models into smaller pieces. An almost balanced (sub-)model is one that contains no frustrated cycles except through one privileged variable.
MR acknowledges support by the UK Engineering and Physical Sciences Research Council (EPSRC) grant EP/L016516/1 for the University of Cambridge Centre for Doctoral Training, the Cambridge Centre for Analysis. DS was supported by NSF CAREER award #1350965.
This record's URL: https://www.repository.cam.ac.uk/handle/1810/255938