Show simple item record

dc.contributor.authorWeller, Adrian
dc.contributor.authorRowland, Mark
dc.contributor.authorSontag, David
dc.date.accessioned2016-05-10T09:25:53Z
dc.date.available2016-05-10T09:25:53Z
dc.date.issued2016-05-02
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/255938
dc.descriptionThis is the author accepted manuscript. The final version is available from MIcrotome Publishing via http://www.jmlr.org/proceedings/papers/v51/weller16b.html.en
dc.description.abstractLinear 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.en
dc.description.sponsorshipMR 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.en
dc.language.isoenen
dc.publisherMicrotome Publishingen
dc.titleTightness of LP Relaxations for Almost Balanced Modelsen
dc.typeArticleen
dc.type.versionaccepted versionen
prism.endingPage55
prism.publicationDate2016
prism.publicationNameProceedings of the 19th International Conference on Artificial Intelligence and Statistics
prism.startingPage47
dc.rioxxterms.funderEPSRC
dc.rioxxterms.funderNSF
dc.rioxxterms.projectidEP/L016516/1
dc.rioxxterms.projectid1350965
pubs.declined2017-10-11T13:54:41.42+0100
dc.publisher.urlhttp://www.jmlr.org/proceedings/papers/v51/weller16b.html


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record