This paper proves that robustness implies generalization via data-dependent generalization bounds. As a result, robustness and generalization are shown to be connected closely in a data-dependent manner. Our bounds improve previous bounds in two directions, to solve an open problem that has seen little development since 2010. The first is to reduce the dependence on the covering number. The second is to remove the dependence on the hypothesis space. We present several examples, including ones for lasso and deep learning, in which our bounds are provably preferable. The experiments on real-world data and theoretical models demonstrate near-exponential improvements in various situations. To achieve these improvements, we do not require additional assumptions on the unknown distribution; instead, we only incorporate an observable and computable property of the training samples. A key technical innovation is an improved concentration bound for multinomial random variables that is of independent interest beyond robustness and generalization.

We study the algorithmic problem of estimating the mean of a heavy-tailed random vector in R^d, given n i.i.d. samples. The goal is to design an efficient estimator that attains the optimal sub-gaussian error bound, only assuming that the random vector has bounded mean and covariance. Polynomial-time solutions to this problem are known but have high runtime due to their use of semi-definite programming (SDP). Moreover, conceptually, it remains open whether convex relaxation is truly necessary for this problem. In this work, we show that it is possible to go beyond SDP and achieve better computational efficiency. In particular, we provide a spectral algorithm that achieves the optimal statistical performance and runs in time O ( n^2 d ), improving upon the previous fastest runtime O( n^{3.5}+ n^2 d ) by Cherapanamjeri et.al. (COLT ’19). Our algorithm is spectral in that it only requires (approximate) eigenvector computations, which can be implemented very efficiently by, for example, power iteration or the Lanczos method. At the core of our algorithm is a novel connection between the furthest hyperplane problem introduced by Karnin et. al. (COLT ’12) and a structural lemma on heavy-tailed distributions by Lugosi and Mendelson (Ann. Stat. ’19). This allows us to iteratively reduce the estimation error at a geometric rate using only the information derived from the top singular vector of the data matrix, leading to a significantly faster running time.

We give a short argument that yields a new lower bound on the number of subsampled rows from a bounded, orthonormal matrix necessary to form a matrix with the restricted isometry property. We show that a matrix formed by uniformly subsampling rows of an N × N Hadamard matrix contains a K-sparse vector in the kernel, unless the number of subsampled rows is Ω(K log K log (N/K)) --- our lower bound applies whenever min(K, N/K) > logCN. Containing a sparse vector in the kernel precludes not only the restricted isometry property, but more generally the application of those matrices for uniform sparse recovery.

Let A be an n x n matrix, X be an n x p matrix, and Y = AX. A challenging and important problem in data analysis, motivated by dictionary learning and other practical problems, is to recover both A and X, given Y. Under normal circumstances, it is clear that this problem is underdetermined. However, in the case, when X is sparse and random, Spielman et al. showed that one can recover both A and X efficiently from Y with high probability, given that p (the number of samples) is sufficiently large. Their method works for p ≥ Cn2log2n and they conjectured that p ≥ Cn log n suffices. The bound n log n is sharp for an obvious information theoretical reason. In this paper, we show that p ≥ Cn log4n suffices, matching the conjectural bound up to a polylogarithmic factor. The core of our proof is a theorem concerning l1concentration of random matrices, which is of independent interest. Our proof of the concentration result is based on two ideas. The first is an economical way to apply the union bound. The second is a refined version of Bernstein's concentration inequality for the sum of independent variables. Both have nothing to do with random matrices and are applicable in general settings.

Let X be a sparse random matrix of size n by p (p >> n). We prove that if p > C n log4 n, then with probability 1-o(1), |XT v|1 is close to its expectation for all vectors v in Rn (simultaneously). The bound on p is sharp up to the polylogarithmic factor. The study of this problem is directly motivated by an application. Let A be an n by n matrix, X be an n by p matrix and Y = AX. A challenging and important problem in data analysis, motivated by dictionary learning and other practical problems, is to recover both A and X, given Y. Under normal circumstances, it is clear that this problem is underdetermined. However, in the case when X is sparse and random, Spiel man, Wang and Wright showed that one can recover both A and X efficiently from Y with high probability, given that p (the number of samples) is sufficiently large. Their method works for p > C n2 log2 n and they conjectured that p > C n log n suffices. The bound n log n is sharp for an obvious information theoretical reason. The matrix concentration result verifies the Spiel man et. Al. Conjecture up to a log3 n factor. Our proof of the concentration result is based on two ideas. The first is an economical way to apply the union bound. The second is a refined version of Bernstein's concentration inequality for a sum of independent variables. Both have nothing to do with random matrices and are applicable in general settings.