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 front due to applications where reliability and security are critical. However, theoretical understanding of algorithms that are robust to adversarial perturbations is limited. In this work we focus on Principal Component Analysis (PCA), a ubiquitous algorithmic primitive in machine learning. We formulate a natural robust variant of PCA where the goal is to find a low dimensional subspace to represent the given data with minimum projection error, that is in addition robust to small perturbations measured in $\ell_q$ norm (say $q=\infty$). Unlike PCA which is solvable in polynomial time, our formulation is computationally intractable to optimize as it captures a variant of the well-studied sparse PCA objective as a special case. We show the following results: 1. Polynomial time algorithm that is constant factor competitive in the worst-case with respect to the best subspace, in terms of the projection error and the robustness criterion. 2. We show that our algorithmic techniques can also be made robust to adversarial training-time perturbations, in addition to yielding representations that are robust to adversarial perturbations at test time. Specifically, we design algorithms for a strong notion of training-time perturbations, where every point is adversarially perturbed up to a specified amount. 3. We illustrate the broad applicability of our algorithmic techniques in addressing robustness to adversarial perturbations, both at training time and test time. In particular, our adversarially robust PCA primitive leads to computationally efficient and robust algorithms for both unsupervised and supervised learning problems such as clustering and learning adversarially robust classifiers.

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 natural model of robustness for high-dimensional statistical estimation problems that we call the {\em adversarial perturbation model}. An adversary can perturb {\em every} sample arbitrarily up to a specified magnitude $\delta$ measured in some $\ell_q$ norm, say $\ell_\infty$. Our model is motivated by emerging paradigms such as {\em low precision machine learning} and {\em adversarial training}. We study the classical problem of estimating the top-$r$ principal subspace of the Gaussian covariance matrix in high dimensions, under the adversarial perturbation model. We design a computationally efficient algorithm that given corrupted data, recovers an estimate of the top-$r$ principal subspace with error that depends on a robustness parameter $\kappa$ that we identify. This parameter corresponds to the $q \to 2$ operator norm of the projector onto the principal subspace, and generalizes well-studied analytic notions of sparsity. Additionally, in the absence of corruptions, our algorithmic guarantees recover existing bounds for problems such as sparse PCA and its higher rank analogs. We also prove that the above dependence on the parameter $\kappa$ is almost optimal asymptotically, not just in a minimax sense, but remarkably for {\em every} instance of the problem. This {\em instance-optimal} guarantee shows that the $q \to 2$ operator norm of the subspace essentially {\em characterizes} the estimation error under adversarial perturbations.

We consider the problem of learning an unknown f with a sparse Fourier spectrum in the presence of outlier noise. In particular, the algorithm has access to a noisy oracle for (an unknown) f such that (i) the Fourier spectrum of f is k-sparse; (ii) at any query point x, the oracle returns y such that with probability 1 – ρ, |y – f (x)| ≤ ε. However, with probability p, the error y – f (x) can be arbitrarily large. We study Fourier sparse functions over both the discrete cube {0, 1}n and the torus [0, 1) and for both these domains, we design efficient algorithms which can tolerate any ρ < 1/2 fraction of outliers. We note that the analogous problem for low-degree polynomials has recently been studied in several works [AK03, GZ16, KKP17] and similar algorithmic guarantees are known in that setting. While our main results pertain to the case where the location of the outliers, i.e., x such that |y – f (x)| > ε is randomly distributed, we also study the case where the outliers are adversarially located. In particular, we show that over the torus, assuming that the Fourier transform satisfies a certain granularity condition, there is a sample efficient algorithm to tolerate ρ = Ω(1) fraction of outliers and further, that this is not possible without such a granularity condition. Finally, while not the principal thrust, our techniques also allow us non-trivially improve on learning low-degree functions f on the hypercube in the presence of adversarial outlier noise. Our techniques combine a diverse array of tools from compressive sensing, sparse Fourier transform, chaining arguments and complex analysis.

We consider the following basic inference problem: there is an unknown high-dimensional vector w ∈ ℝ n , and an algorithm is given access to labeled pairs (x,y) where x ∈ ℝ n is a measurement and y = w · x + noise. What is the complexity of deciding whether the target vector w is (approximately) k-sparse? The recovery analogue of this problem — given the promise that w is sparse, find or approximate the vector w — is the famous sparse recovery problem, with a rich body of work in signal processing, statistics, and computer science.

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 continuous sparse Fourier transforms. In the active linear regression problem, one would like to estimate the least squares solution $\beta^*$ minimizing $\|X\beta - y\|_2$ given the entire unlabeled dataset $X \in \mathbb{R}^{n \times d}$ but only observing a small number of labels $y_i$. We show that $O(d)$ labels suffice to find a constant factor approximation $\widetilde{\beta}$: \[ \mathbb{E}[\|{X} \widetilde{\beta} - y \|_2^2] \leq 2 \mathbb{E}[\|X \beta^* - y\|_2^2]. \]{This} improves on the best previous result of $O(d \log d)$ from leverage score sampling. We also present results for the \emph{inductive} setting, showing when $\widetilde{\beta}$ will generalize to fresh samples; these apply to continuous settings such as polynomial regression. Finally, we show how the techniques yield improved results for the non-linear sparse Fourier transform setting.

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 $g(t)$ with Fourier spectrum in a narrow range $[f_0 - Δ, f_0 + Δ]$, how accurately is it possible to identify $f_0$? We present generic conditions on $g$ that allow for efficient, accurate estimates of the frequency. We then show bounds on these conditions for $k$-Fourier-sparse signals that imply recovery of $f_0$ to within $Δ+ \tilde{O}(k^3)$ from samples on $[-1, 1]$. This improves upon the best previous bound of $O\big( Δ+ \tilde{O}(k^5) \big)^{1.5}$. We also show that no algorithm can do better than $Δ+ \tilde{O}(k^2)$. In the process we provide a new $\tilde{O}(k^3)$ bound on the ratio between the maximum and average value of continuous $k$-Fourier-sparse signals, which has independent application.

In this paper, we study the maximum loads of explicit hash families in the d-choice schemes when allocating sequentially n balls into n bins. We consider the Uniform-Greedy scheme [ABKU99], which provides d independent bins for each ball and places the ball into the bin with the least load, and its non-uniform variant — the Always-Go-Left scheme introduced by Vöcking [Vöc03]. We construct a hash family with O(log n log log n) random bits based on the previous work of Celis et al. [CRSW13] and show the following results. 1. With high probability, this hash family has a maximum load of in the Uniform-Greedy scheme. 2. With high probability, it has a maximum load of in the Always-Go-Left scheme for a constant ϕd > 1.61. The maximum loads of our hash family match the maximum loads of a perfectly random hash function [ABKU99, Vöc03] in the Uniform-Greedy and Always-Go-Left scheme separately, up to the low order term of constants. Previously, the best known hash families matching the same maximum loads of a perfectly random hash function in d-choice schemes were O(log n)-wise independent functions [Vöc03], which needs Θ(log2 n) random bits.

We consider the problem of estimating a Fourier-sparse signal from noisy samples, where the sampling is done over some interval [0, T] and the frequencies can be "off-grid". Previous methods for this problem required the gap between frequencies to be above 1/T, the threshold required to robustly identify individual frequencies. We show the frequency gap is not necessary to estimate the signal as a whole: for arbitrary k-Fourier-sparse signals under l2 bounded noise, we show how to estimate the signal with a constant factor growth of the noise and sample complexity polynomial in k and logarithmic in the bandwidth and signal-to-noise ratio. As a special case, we get an algorithm to interpolate degree d polynomials from noisy measurements, using O(d) samples and increasing the noise by a constant factor in l2.