28 citations · 130 across the 32 of their papers we have counts for
5 papers · 1 filter
Training Subset Selection for Weak Supervision
Hunter Lang, Aravindan Vijayaraghavan, David Sontag
Existing weak supervision approaches use all the data covered by weak signals to train a classifier. We show both theoretically and empirically that this is not always optimal. Int…
Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances
Hunter Lang, Aravind Reddy, David Sontag +1
Several works have shown that perturbation stable instances of the MAP inference problem in Potts models can be solved exactly using a natural linear programming (LP) relaxation. H…
Graph cuts always find a global optimum for Potts models (with a catch)
Hunter Lang, David Sontag, Aravindan Vijayaraghavan
We prove that the -expansion algorithm for MAP inference always returns a globally optimal assignment for Markov Random Fields with Potts pairwise potentials, with a catch: the…
Block Stability for MAP Inference
Hunter Lang, David Sontag, Aravindan Vijayaraghavan
To understand the empirical success of approximate MAP inference, recent work (Lang et al., 2018) has shown that some popular approximation algorithms perform very well when the in…
Optimality of Approximate Inference Algorithms on Stable Instances
Hunter Lang, David Sontag, Aravindan Vijayaraghavan
Approximate algorithms for structured prediction problems---such as LP relaxations and the popular alpha-expansion algorithm (Boykov et al. 2001)---typically far exceed their theor…