165 citations · 329 across the 17 of their papers we have counts for
11 papers · 1 filter
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…
Empirical Study of the Benefits of Overparameterization in Learning Latent Variable Models
Rares-Darius Buhai, Yoni Halpern, Yoon Kim +2
One of the most surprising and exciting discoveries in supervised learning was the benefit of overparameterization (i.e. training a very large model) to improving the optimization…
Support and Invertibility in Domain-Invariant Representations
Fredrik D. Johansson, David Sontag, Rajesh Ranganath
Learning domain-invariant representations has become a popular approach to unsupervised domain adaptation and is often justified by invoking a particular suite of theoretical resul…
Overcomplete Independent Component Analysis via SDP
Anastasia Podosinnikova, Amelia Perry, Alexander Wein +3
We present a novel algorithm for overcomplete independent components analysis (ICA), where the number of latent sources k exceeds the dimension p of observed variables. Previous al…
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…