A random m× n matrix S is an oblivious subspace embedding (OSE) with parameters є>0, δ∈(0,1/3) and d≤ m≤ n, if for any d-dimensional subspace W⊆ Rn, P( ∀x∈ W (1+є)−1||x||≤ ||Sx||≤ (1+є)||x|| )≥ 1−δ. It is known that the embedding dimension of an OSE must satisfy m≥ d, and for any θ > 0, a Gaussian embedding matrix with m≥ (1+θ) d is an OSE with є = Oθ(1). However, such optimal embedding dimension is not known for other embeddings. Of particular interest are sparse OSEs, having s≪ m non-zeros per column (Clarkson and Woodruff, STOC 2013), with applications to problems such as least squares regression and low-rank approximation.

Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We show that, for two Erdős–Rényi graphs with edge correlation $1-\alpha$, our algorithm recovers the underlying matching exactly with high probability when $\alpha \le 1 / (\log \log n)^C$, where $n$ is the number of vertices in each graph and $C$ denotes a positive universal constant. This improves the condition $\alpha \le 1 / (\log n)^C$ achieved in previous work.

High-dimensional settings, where the data dimension ($d$) far exceeds the number of observations ($n$), are common in many statistical and machine learning applications. Methods based on $\ell_1$-relaxation, such as Lasso, are very popular for sparse recovery in these settings. Restricted Eigenvalue (RE) condition is among the weakest, and hence the most general, condition in literature imposed on the Gram matrix that guarantees nice statistical properties for the Lasso estimator. It is hence natural to ask: what families of matrices satisfy the RE condition? Following a line of work in this area, we construct a new broad ensemble of dependent random design matrices that have an explicit RE bound. Our construction starts with a fixed (deterministic) matrix $X \in \mathbb{R}^{n \times d}$ satisfying a simple stable rank condition, and we show that a matrix drawn from the distribution $X \Phi^\top \Phi$, where $\Phi \in \mathbb{R}^{m \times d}$ is a subgaussian random matrix, with high probability, satisfies the RE condition. This construction allows incorporating a fixed matrix that has an easily {\em verifiable} condition into the design process, and allows for generation of {\em compressed} design matrices that have a lower storage requirement than a standard design matrix. We give two applications of this construction to sparse linear regression problems, including one to a compressed sparse regression setting where the regression algorithm only has access to a compressed representation of a fixed design matrix $X$.

Kernel methods are an extremely popular set of techniques used for many important machine learning and data analysis applications. In addition to having good practical performances, these methods are supported by a well-developed theory. Kernel methods use an implicit mapping of the input data into a high dimensional feature space defined by a kernel function, i.e., a function returning the inner product between the images of two data points in the feature space. Central to any kernel method is the kernel matrix, which is built by evaluating the kernel function on a given sample dataset. In this paper, we initiate the study of non-asymptotic spectral theory of random kernel matrices. These are n x n random matrices whose (i,j)th entry is obtained by evaluating the kernel function on $x_i$ and $x_j$, where $x_1,...,x_n$ are a set of n independent random high-dimensional vectors. Our main contribution is to obtain tight upper bounds on the spectral norm (largest eigenvalue) of random kernel matrices constructed by commonly used kernel functions based on polynomials and Gaussian radial basis. As an application of these results, we provide lower bounds on the distortion needed for releasing the coefficients of kernel ridge regression under attribute privacy, a general privacy notion which captures a large class of privacy definitions. Kernel ridge regression is standard method for performing non-parametric regression that regularly outperforms traditional regression approaches in various domains. Our privacy distortion lower bounds are the first for any kernel technique, and our analysis assumes realistic scenarios for the input, unlike all previous lower bounds for other release problems which only hold under very restrictive input settings.

We consider the power of “linear reconstruction attacks” in statistical data privacy, showing that they can be applied to a much wider range of settings than previously understood. Linear attacks have been studied before [3, 6, 11, 1, 14] but have so far been applied only in settings with releases that are “obviously” linear. Consider a database curator who manages a database of sensitive information but wants to release statistics about how a sensitive attribute (say, disease) in the database relates to some nonsensitive attributes (e.g., postal code, age, gender, etc). This setting is widely considered in the literature, partly since it arises with medical data. Specifically, we show one can mount linear reconstruction attacks based on any release that gives: 1. the fraction of records that satisfy a given non-degenerate boolean function. Such releases include contingency tables (previously studied by Kasiviswanathan et al. [11]) as well as more complex outputs like the error rate of classifiers such as decision trees; 2. any one of a large class of M-estimators (that is, the output of empirical risk minimization algorithms), including the standard estimators for linear and logistic regression. We make two contributions: first, we show how these types of releases can be transformed into a linear format, making them amenable to existing polynomial-time reconstruction algorithms. This is already perhaps surprising, since many of the above releases (like M-estimators) are obtained by solving highly nonlinear formulations. Second, we show how to analyze the resulting attacks under various distributional assumptions on the data. Specifically, we consider a setting in which the same statistic (either 1 or 2 above) is released about how the sensitive attribute relates to all subsets of size k (out of a total of d) nonsensitive boolean attributes.

Random matrices are widely used in sparse recovery problems, and the relevant properties of matrices with i.i.d. entries are well understood. This paper discusses the recently introduced restricted eigenvalue (RE) condition, which is among the most general assumptions on the matrix, guaranteeing recovery. We prove a reduction principle showing that the RE condition can be guaranteed by checking the restricted isometry on a certain family of low-dimensional subspaces. This principle allows us to establish the RE condition for several broad classes of random matrices with dependent entries, including random matrices with sub-Gaussian rows and nontrivial covariance structure, as well as matrices with independent rows, and uniformly bounded entries.

Marginal (contingency) tables are the method of choice for government agencies releasing statistical summaries of categorical data. In this paper, we derive lower bounds on how much distortion (noise) is necessary in these tables to ensure the privacy of sensitive data. We extend a line of recent work on impossibility results for private data analysis [9, 12, 13, 15] to a natural and important class of functionalities. Consider a database consisting of n rows (one per individual), each row comprising d binary attributes. For any subset of T attributes of size |T|=k, the marginal table for T has 2k entries; each entry counts how many times in the database a particular setting of these attributes occurs. We provide lower bounds for releasing all d k k-attribute marginal tables under several different notions of privacy. (1) We give efficient polynomial time attacks which allow an adversary to reconstruct sensitive information given insufficiently perturbed marginal table releases. In particular, for a constant k, we obtain a tight bound of ~Ω(min √n, √dk-1) on the average distortion per entry for any mechanism that releases all k-attribute marginals while providing "attribute" privacy (a weak notion implied by most privacy definitions). (2) Our reconstruction attacks require a new lower bound on the least singular value of a random matrix with correlated rows. Let M(k) be a matrix with d k rows formed by taking all possible k-way entry-wise products of an underlying set of d random vectors from {0,1}n. For constant k, we show that the least singular value of M(k) is ~Ω(√dk) with high probability (the same asymptotic bound as for independent rows). (3) We obtain stronger lower bounds for marginal tables satisfying differential privacy. We give a lower bound of ~Ω(min {√n, √ dk), which is tight for n ~Ω (dk). We extend our analysis to obtain stronger results for mechanisms that add instance-independent noise and weaker results when k is super-constant.

We study random submatrices of a large matrix A . We show how to approximately compute A from its random submatrix of the smallest possible size O ( r log r ) with a small error in the spectral norm, where r = ‖ A ‖ 2 F /‖ A ‖ 2 2 is the numerical rank of A . The numerical rank is always bounded by, and is a stable relaxation of, the rank of A . This yields an asymptotically optimal guarantee in an algorithm for computing low-rank approximations of A . We also prove asymptotically optimal estimates on the spectral norm and the cut-norm of random submatrices of A . The result for the cut-norm yields a slight improvement on the best-known sample complexity for an approximation algorithm for MAX-2CSP problems. We use methods of Probability in Banach spaces, in particular the law of large numbers for operator-valued random variables.

Let A be an n times n matrix, whose entries are independent copies of a centered random variable satisfying the subGaussian tail estimate. We prove that the operator norm of' A-1does not exceed Cn3/2with probability close to 1. In a geometric language, this bounds the probability that the affine span of n random vectors in Ropfnwith i.i.d. subGaussian coordinates comes close to the origin

Suppose we wish to transmit a vector f ϵ Rnreliably. A frequently discussed approach consists in encoding f with an m by n coding matrix A. Assume now that a fraction of the entries of Af are corrupted in a completely arbitrary fashion by an error e. We do not know which entries are affected nor do we know how they are affected. Is it possible to recover f exactly from the corrupted m-dimensional vector y = Af + e?