research
∙
02/10/2020
Random Smoothing Might be Unable to Certify ℓ_∞ Robustness for High-Dimensional Images
We show a hardness result for random smoothing to achieve certified adve...
share
research
∙
11/30/2019
Design and Interpretation of Universal Adversarial Patches in Face Detection
We consider universal adversarial patches for faces - small visual eleme...
research
∙
10/30/2019
Optimal Analysis of Subset-Selection Based L_p Low Rank Approximation
We study the low rank approximation problem of any given matrix A over R...
research
∙
10/04/2019
Efficient Symmetric Norm Regression via Linear Sketching
We provide efficient algorithms for overconstrained linear regression pr...
research
∙
01/24/2019
Theoretically Principled Trade-off between Robustness and Accuracy
We identify a trade-off between robustness and accuracy that serves as a...
research
∙
11/19/2018
Stackelberg GAN: Towards Provable Minimax Equilibrium via Multi-Generator Architectures
We study the problem of alleviating the instability issue in the GAN tra...
research
∙
10/31/2018
Recovery Guarantees for Quadratic Tensors with Limited Observations
We consider the tensor completion problem of predicting the missing entr...
research
∙
10/18/2018
Testing Matrix Rank, Optimally
We show that for the problem of testing if a matrix A ∈ F^n × n has rank...
research
∙
06/06/2018
Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex
Several recently proposed architectures of neural networks such as ResNe...
research
∙
04/25/2018
Improved Algorithms for Adaptive Compressed Sensing
In the problem of adaptive compressed sensing, one wants to estimate an ...
research
∙
12/26/2017
Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
We show that the (stochastic) gradient descent algorithm provides an imp...
research
∙
12/26/2017
Algorithmic Regularization in Over-parameterized Matrix Recovery
We study the problem of recovering a low-rank matrix X^ from linear meas...
research
∙
12/23/2017
Distance Labelings on Random Power Law Graphs
A Distance Labeling scheme is a data structure that can answer shortest...
research
∙
07/03/2017
Regression Phalanxes
Tomal et al. (2015) introduced the notion of "phalanxes" in the context ...
research
∙
04/27/2017
Optimal Sample Complexity for Matrix Completion and Related Problems via ℓ_2-Regularization
We study the strong duality of non-convex matrix factorization: we show ...
research
∙
04/19/2017
Noise-Tolerant Interactive Learning from Pairwise Comparisons
We study the problem of interactively learning a binary classifier using...
research
∙
03/22/2017
S-Concave Distributions: Towards Broader Distributions for Noise-Tolerant and Sample-Efficient Learning Algorithms
We provide new results concerning noise-tolerant and sample-efficient le...
research
∙
06/25/2015
Completing Low-Rank Matrices with Corrupted Samples from Few Coefficients in General Basis
Subspace recovery from corrupted and missing data is crucial for various...
research
∙
04/23/2013