research
∙
08/20/2023
Higher-Order Cheeger Inequality for Partitioning with Buffers
We prove a new generalization of the higher-order Cheeger inequality for...
share
research
∙
12/07/2022
Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
We study the problem of finding elements in the intersection of an arbit...
research
∙
11/22/2022
The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound
The most widely used technique for solving large-scale semidefinite prog...
research
∙
09/06/2022
Classification Protocols with Minimal Disclosure
We consider multi-party protocols for classification that are motivated ...
research
∙
08/04/2022
Agnostic Learning of General ReLU Activation Using Gradient Descent
We provide a convergence analysis of gradient descent for the problem of...
research
∙
06/06/2022
Training Subset Selection for Weak Supervision
Existing weak supervision approaches use all the data covered by weak si...
research
∙
07/21/2021
Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations
We present polynomial time and sample efficient algorithms for learning ...
research
∙
02/26/2021
Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances
Several works have shown that perturbation stable instances of the MAP i...
research
∙
11/07/2020
Graph cuts always find a global optimum (with a catch)
We prove that the alpha-expansion algorithm for MAP inference always ret...
research
∙
10/06/2020
Learning a mixture of two subspaces over finite fields
We study the problem of learning a mixture of two subspaces over 𝔽_2^n. ...
research
∙
07/30/2020
Efficient Tensor Decomposition
This chapter studies the problem of decomposing a tensor into a sum of c...
research
∙
05/31/2020
Estimating Principal Components under Adversarial Perturbations
Robustness is a key requirement for widespread deployment of machine lea...
research
∙
04/22/2020
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
We consider the problem of scheduling n precedence-constrained jobs on m...
research
∙
11/29/2019
Adversarially Robust Low Dimensional Representations
Adversarial or test time robustness measures the susceptibility of a mac...
research
∙
11/12/2019
On Robustness to Adversarial Examples and Polynomial Optimization
We study the design of computationally efficient algorithms with provabl...
research
∙
11/29/2018
Smoothed Analysis in Unsupervised Learning via Decoupling
Smoothed analysis is a powerful paradigm in overcoming worst-case intrac...
research
∙
10/12/2018
Block Stability for MAP Inference
To understand the empirical success of approximate MAP inference, recent...
research
∙
04/23/2018
Towards Learning Sparsely Used Dictionaries with Arbitrary Supports
Dictionary learning is a popular approach for inferring a hidden basis o...
research
∙
12/04/2017
Clustering Stable Instances of Euclidean k-means
The Euclidean k-means problem is arguably the most widely-studied cluste...
research
∙
11/23/2017
Clustering Semi-Random Mixtures of Gaussians
Gaussian mixture models (GMM) are the most widely used statistical model...
research
∙
11/06/2017
Alpha-expansion is Exact on Stable Instances
Approximate algorithms for structured prediction problems---such as the ...
research
∙
10/31/2017
On Learning Mixtures of Well-Separated Gaussians
We consider the problem of efficiently learning mixtures of a large numb...
research
∙
11/14/2013