21 citations · 36 across the 10 of their papers we have counts for
11 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…
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…
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…
Active Regression via Linear-Sample Sparsification
Xue Chen, Eric Price
We present an approach that improves the sample complexity for a variety of curve fitting problems, including active learning for linear regression, polynomial regression, and cont…
Derandomized Balanced Allocation
Xue Chen
In this paper, we study the maximum loads of explicit hash families in the -choice schemes when allocating sequentially balls into bins. We consider the \emph{Uniform-Gr…
Fourier-sparse interpolation without a frequency gap
Xue Chen, Daniel M. Kane, Eric Price +1
We consider the problem of estimating a Fourier-sparse signal from noisy samples, where the sampling is done over some interval and the frequencies can be "off-grid". Prev…
Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints
Xue Chen, Yuan Zhou
Given a constraint satisfaction problem (CSP) on variables, , and constraints, a global cardinality constraint has the form of $\sum_{i…
Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders
Xue Chen
We study the problem of approximating the quality of a disperser. A bipartite graph on is a -disperser if for any subset of size ,…