5 papers
Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence
Xue Chen, Michał Dereziński
Consider a regression problem where the learner is given a large collection of -dimensional data points, but can only query a small subset of the real-valued labels. How many qu…
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…
Testing noisy linear functions for sparsity
Xue Chen, Anindya De, Rocco A. Servedio
We consider the following basic inference problem: there is an unknown high-dimensional vector , and an algorithm is given access to labeled pairs where…
Reconstruction under outliers for Fourier-sparse functions
Xue Chen, Anindya De
We consider the problem of learning an unknown with a sparse Fourier spectrum in the presence of outlier noise. In particular, the algorithm has access to a noisy oracle for (a…
Estimating the Frequency of a Clustered Signal
Xue Chen, Eric Price
We consider the problem of locating a signal whose frequencies are "off grid" and clustered in a narrow band. Given noisy sample access to a function with Fourier spectrum i…