28 citations · 130 across the 32 of their papers we have counts for
35 papers
Higher-Order Cheeger Inequality for Partitioning with Buffers
Konstantin Makarychev, Yury Makarychev, Liren Shan +1
We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph . The buffered expansion of a set with…
Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan
We study the problem of finding elements in the intersection of an arbitrary conic variety in with a given linear subspace (where can be the real or com…
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…
A Complete Hierarchy of Linear Systems for Certifying Quantum Entanglement of Subspaces
Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan
We introduce a hierarchy of linear systems for showing that a given subspace of pure quantum states is entangled (i.e., contains no product states). This hierarchy outperforms know…
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…
Agnostic Learning of General ReLU Activation Using Gradient Descent
Pranjal Awasthi, Alex Tang, Aravindan Vijayaraghavan
We provide a convergence analysis of gradient descent for the problem of agnostically learning a single ReLU function with moderate bias under Gaussian distributions. Unlike prior…
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…
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…
Adversarial robustness via robust low rank representations
Pranjal Awasthi, Himanshu Jain, Ankit Singh Rawat +1
Adversarial robustness measures the susceptibility of a classifier to imperceptible perturbations made to the inputs at test time. In this work we highlight the benefits of natural…
Efficient Tensor Decomposition
Aravindan Vijayaraghavan
This chapter studies the problem of decomposing a tensor into a sum of constituent rank one tensors. While tensor decompositions are very useful in designing learning algorithms an…
Estimating Principal Components under Adversarial Perturbations
Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan
Robustness is a key requirement for widespread deployment of machine learning algorithms, and has received much attention in both statistics and computer science. We study a natura…
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa +2
We consider the problem of scheduling precedence-constrained jobs on uniformly-related machines in the presence of an arbitrary, fixed communication delay . We consider…
On Robustness to Adversarial Examples and Polynomial Optimization
Pranjal Awasthi, Abhratanu Dutta, Aravindan Vijayaraghavan
We study the design of computationally efficient algorithms with provable guarantees, that are robust to adversarial (test time) perturbations. While there has been an proliferatio…
Adversarially Robust Low Dimensional Representations
Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen +1
Many machine learning systems are vulnerable to small perturbations made to inputs either at test time or at training time. This has received much recent interest on the empirical…
Smoothed Analysis in Unsupervised Learning via Decoupling
Aditya Bhaskara, Aidao Chen, Aidan Perreault +1
Smoothed analysis is a powerful paradigm in overcoming worst-case intractability in unsupervised learning and high-dimensional data analysis. While polynomial time smoothed analysi…
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…
Towards Learning Sparsely Used Dictionaries with Arbitrary Supports
Pranjal Awasthi, Aravindan Vijayaraghavan
Dictionary learning is a popular approach for inferring a hidden basis or dictionary in which data has a sparse representation. Data generated from the dictionary A (an n by m matr…
Clustering Stable Instances of Euclidean k-means
Abhratanu Dutta, Aravindan Vijayaraghavan, Alex Wang
The Euclidean k-means problem is arguably the most widely-studied clustering problem in machine learning. While the k-means objective is NP-hard in the worst-case, practitioners ha…
Clustering Semi-Random Mixtures of Gaussians
Pranjal Awasthi, Aravindan Vijayaraghavan
Gaussian mixture models (GMM) are the most widely used statistical model for the -means clustering problem and form a popular framework for clustering in machine learning and da…
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…
On Learning Mixtures of Well-Separated Gaussians
Oded Regev, Aravindan Vijayaraghavan
We consider the problem of efficiently learning mixtures of a large number of spherical Gaussians, when the components of the mixture are well separated. In the most basic form of…