17 citations · 30 across the 11 of their papers we have counts for
17 papers
The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound
Liam O'Carroll, Vaidehi Srinivas, Aravindan Vijayaraghavan
The most widely used technique for solving large-scale semidefinite programs (SDPs) in practice is the non-convex Burer-Monteiro method, which explicitly maintains a low-rank SDP s…
Classification Protocols with Minimal Disclosure
Jinshuo Dong, Jason Hartline, Aravindan Vijayaraghavan
We consider multi-party protocols for classification that are motivated by applications such as e-discovery in court proceedings. We identify a protocol that guarantees that the re…
Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations
Pranjal Awasthi, Alex Tang, Aravindan Vijayaraghavan
We present polynomial time and sample efficient algorithms for learning an unknown depth-2 feedforward neural network with general ReLU activations, under mild non-degeneracy assum…
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…
Learning a mixture of two subspaces over finite fields
Aidao Chen, Anindya De, Aravindan Vijayaraghavan
We study the problem of learning a mixture of two subspaces over . The goal is to recover the individual subspaces, given samples from a (weighted) mixture of sampl…