{'fraction_non_alphanumeric': 0.057126846963753794, 'fraction_numerical': 0.022738667531778098, 'mean_word_length': 3.495889684433837, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 34, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk

We examine the theoretical properties of enforcing priors provided by generative deep neural networks via empirical risk minimization. In particular we consider two models, one in which the task is to invert a generative neural network given access to its last layer and another which entails recovering a latent code in the domain of a generative neural network from compressive linear observations of its last layer. We establish that in both cases, in suitable regimes of network layer sizes and a randomness assumption on the network weights, that the non-convex objective function given by empirical risk minimization does not have any spurious stationary points. That is, we establish that with high probability, at any point away from small neighborhoods around two scalar multiples of the desired solution, there is a descent direction. These results constitute the first theoretical guarantees which establish the favorable global geometry of these non-convex optimization problems, and bridge the gap between the empirical success of deep learning and a rigorous understanding of non-linear inverse problems.


Introduction
Exploiting the structure of natural signals and images has proven to be a fruitful endeavor across many domains of science. Breaking with the dogma of the Nyquist sampling theorem, which stems from worst-case analysis, Candes and Tao, and Donoho [8,10], provided a theory and practice of compressed sensing (CS), which exploits the sparsity of natural signals to design acquisition strategies whose sample complexity is on par with the sparsity level of the signal at hand. On a practical level, compressed sensing has lead to significant reduction in the sample complexity of signal acquisition of natural images, for instance speeding up MRI imaging by a factor of 10. Beyond MRI, compressed sensing has impacted many if not all imaging sciences, by providing a general tool to exploit the parsimony of natural signals to improve acquisition speed, increase SNR and reduce sample complexity. CS has also lead to the development of the fields of matrix completion [7], phase retrieval, [9,6] and several other subfields [1] which analogously exploit the sparsity of singular values of low rank matrices as well as sparsity in some basis.
Meanwhile, the advent of practical deep learning has significantly improved meaningful compression of images and acoustic signals. For instance, deep learning techniques are now the state of the art across most of computer vision, and have taken the field far beyond where it stood just a few years prior. The success of deep learning ostensibly stems from its ability to exploit the hierarchical nature of images and other signals. There are many techniques and add-on architectural choices associated with deep learning, but many of them are non-essential from a theoretical and, to an extent, practical perspective, with simple convolutional deep nets with ReLUs achieving close to the state of the art performance on many tasks [15]. The class of functions represented by such deep networks is readily interpretable as hierarchical compression schemes with exponentially many linear filters, each being a linear combination of filters in earlier layers. Constructing such compression schemes by hand would be quite tedious if not impossible, and the biggest surprise of deep learning is that simple stochastic gradient descent (SGD) allows one to efficiently traverse this class of functions subject to highly non-convex learning objectives. While this latter property has been empirically established in an impressive number of applications, it has so far eluded a completely satisfactory theoretical explanation.
Optimizing over the weights of a neural network or inverting a neural network may both be interpreted as inverse problems [13]. Traditionally, rigorous understanding of inverse problems has been limited to the simpler setting in which the optimization objective is convex. More recently, there has been progress in understanding non-convex optimization objectives for inverse problems, in albeit analytically simpler situations than those involving multilayer neural networks. For instance, the authors of [16,4] provide a global analysis of non-convex objectives for phase retrieval and community detection, respectively, ruling out adversarial geometries in these scenarios for the purposes of optimization.
Very recently, deep neural networks have been exploited to construct highly effective natural image priors, by training generative adversarial networks to find a Nash equilibrium of a nonconvex game [11]. The resulting image priors have proven useful in inverting hidden layers of lossy neural networks [14] and performing super-resolution [12]. Naturally, one may ponder whether these generative priors may be leveraged to improve compressive sensing. Indeed, while natural images are sparse in the wavelet basis, a random sparse linear combination of wavelets is far less structured than say a real-world scene or a biological structure, illustrating that a generic sparsity prior is nowhere near tight. The generative priors provided by GANs have already been leveraged to improve compressed sensing in particular domains [3]. Remarkably, empirical results by [3] dictate that given a dataset of images from a particular class, one can perform compressed sensing with 10X fewer measurements than what the sparsity prior alone would permit in traditional CS. As GANs and other neural network-based priors improve in modeling more diverse datasets of images, many scenarios in compressed sensing will benefit analogously. Moreover, using generative priors to improve signal recovery in otherwise underdetermined settings is not limited to linear inverse problems, and in principle these benefits should carry over to any inverse problem in imaging science.
In this paper we present the first global analysis of empirical risk minimization for enforcing generative multilayer neural network priors. In particular we show that under suitable randomness assumptions on the weights of a neural network and successively expansive hidden layer sizes, the empirical risk objective for recovering a latent code in R k from m linear observations of the last layer of a generative network, where m is proportional to k up to log factors, has no spurious local minima, in that there is a descent direction everywhere except possibly small neighborhoods around two scalar multiples of the desired solution. Our descent direction analysis is constructive and relies on novel concentration bounds of certain random matrices, uncovering some interesting geometrical properties of the landscapes of empirical risk objective functions for random ReLU'd generative multilayer networks. The tools developed in this paper may be of independent interest, and may in particular lead to global non-asymptotic guarantees regarding convergence of SGD for training deep neural networks.

Related theoretical work
In related work, the authors of [3] also rigorously study inverting compressive linear observations under generative priors, by proving a restricted eigenvalue condition on the range of the generative neural network. However, they only provide a guarantee that is local in nature, in showing the global optimum of empirical risk is close to the desired solution. The global properties of optimizing the objective function are not theoretically studied in [3]. In addition, [2] studied inverting neural networks given access to the last layer using an analytical formula that approximates the inverse mapping of a neural network. The results of [2] are in a setting where the neural net is not generative, and their procedure is at best approximate, and, since it requires observation of the last layer, it is not readily extendable to the compressive linear observation setting. Meanwhile, the optimization problem we study can yield exact recovery, which we observe empirically via gradient descent. Most importantly, in contrast to [3,2], we provide a global analysis of the nonconvex empirical risk objective function and constructively exhibit a descent direction at every point outside a neighborhood of the desired solution and a negative scalar multiple of it. Our guarantees are non-asymptotic, and to the best of our knowledge the first of their kind.

Generative priors with two layers
We consider the nonlinear inverse problem of recovering a signal from linear measurements of the last layer of a generative neural network with two layers, gaussian weights and a ReLU activation function at each layer. Let k be the dimensionality of the latent code space. Let n 1 and n 2 be the number of neurons in the first and second layers, respectively. Let A ∈ R n 1 ×k and W ∈ R n 2 ×n 1 be the weights of the neural network at the first and second layers. Let C ∈ R m×n 2 be a matrix that linearly subsamples the output of the generative network. Here, we consider k < n 1 < n 2 and k < m < n 2 . The problem at hand is: Let: x 0 ∈ R k , A ∈ R n 1 ×k , B ∈ R n 2 ×n 1 , C ∈ R m×n 2 Given: A, B, C, and observations C[relu(B(relu(Ax 0 )))] Find: x 0 We consider solving this signal recovery problem by minimization of empirical risk under an ℓ 2 loss. That is, we study the minimization of Note that f is not differentiable, but its (one-sided) directional derivatives exist at all points and in all directions.
. We show that if the neural network weights A, B and sampling matrix C are Gaussian and independent from each other, then the empirical risk function has a strict descent direction at any non-zero point outside of a neighborhood of x 0 and −x 0 /π, with high probability, provided that m = Ω(k log(n 1 n 2 )) and n 1 = Ω(k log k) and n 2 = Ω(n 1 log n 1 ). Specifically, we show that a descent direction is given by with A +,x = diag(Ax > 0)A and B +,x = diag(BA +,x x > 0)B, where we take diag(w) to be a diagonal matrix with the entries of a vector w on the diagonal. This expression is the gradient of f where f is differentiable. Where f is not differentiable, this expression is the gradient of the terms in f where all arguments to the ReLU functions are strictly positive. Note that it can be computed at arbitrary x knowing only A, B, C and the observations C[relu(B(relu(Ax 0 )))]. Additionally, we show that 0 is a local max by establishing that the directional derivative of f at zero is negative in all directions.
Gaussian entries with mean 0 and variances 1/n 1 , 1/n 2 and 1/m, respectively. If n 1 ≥ ck log k and n 2 ≥ cn 1 log n 1 and m > ck log(n 1 n 2 ), then with probability at least 1 − c 0 (n 1 e −γk + n 2 e −γn 1 + e −γm ), we have , simultaneously for all x 0 = 0. Here, c and γ are constants that depend only on ǫ, and c 0 is a universal constant.
In particular, by taking large enough and sufficiently successively expansive layers with m = O(k log(n 1 n 2 )) observations, we can guarantee strict descent directions of the empirical risk objective everywhere but two arbitrarily small neighborhoods of two scalar multiples of x 0 .
The case of inversion of a two-layer network follows by taking the matrix C to be identity, or alternatively by taking m → ∞.

Corollary 2. (Inversion of Two Layer Network)
Under the same assumptions as Theorem 1, but with m = n 2 and C = I n 2 , we have the same result if n 1 ≥ ck log k and n 2 ≥ cn 1 log n 1 , with probability at least 1 − c 0 (n 1 e −γk + n 2 e −γn 1 ).
The proofs of this theorem and corollary are in Section 6.3. Note that the theorem assumes each layer has at least a logarithmic factor more neurons than the layer before it. For the probability bounds to be nontrivial, each layer can not have more than exponentially many more neurons than the prior layer. This theorem establishes that if an algorithm for minimizing (1) finds a stationary point, then that point is near x 0 or − 1 π x 0 with high probability, provided that there are a sufficient number of neurons at each layer and provided that the number of linear observations of the last layer is Ω(k log(n 1 n 2 )). Note that the number of required random linear observations of the last layer is proportional up to log factors to the dimension of the latent code space, which may be significantly smaller than the embeddings space R n 2 of the last layer. Thus our guarantees hold in the regime of genuine compressive sensing under a generative prior.

Generative priors with d layers
We also consider the nonlinear inverse problem of recovering a signal from linear measurements about the last layer of a random generative neural network with d layers, with ReLU activations at each layer. Let k = n 0 be the dimensionality of the latent code space. Let n i be the number of neurons in the i layer. Let W i ∈ R n i ×n i−1 be the weights of the neural network at the ith layer. Let C ∈ R m×n d be a matrix that linearly subsamples the output of the generative network. Here, we consider k < n 1 < · · · < n d and k < m < n d . The problem at hand is: Let: x 0 ∈ R n 0 , C ∈ R m×n d , W i ∈ R n i ×n i−1 for i = 1 . . . d Find: x 0 We study the minimization of We show that if the neural network weights and the entries of the sampling matrix are independent gaussians, then the empirical risk function f (x) has a strict descent direction at any point outside of a neighborhood of x 0 and a negative multiple of x 0 , with high probability, provided that m = Ω(k log Π d i=1 n i ) and n i = Ω(n i−1 log n i−1 ). Specifically, we show that a descent direction is given by where , simultaneously for all x 0 = 0, where ρ d is a d-dependent positive number. Here, c, c 0 , c i , γ are constants that depend only on ǫ.
In particular, for a fixed d, by taking large enough and sufficiently successively expansive layers with m = O(k log(Π d i=1 n i )) observations, we can guarantee strict descent directions of the empirical risk objective everywhere but two arbitrarily small neighborhoods of two scalar multiples of x 0 .
The case of inversion of a d-layer network follows by taking the matrix C to be identity, or alternatively by taking m → ∞.
The proofs of this theorem and corollary are in the supplemental materials and parallels those of Theorem 1.
This theorem extends Theorem 1 to the case of an arbitrary number of layers. It establishes that for a generative prior with an arbitrary number of fixed layers, if there are a sufficient number of measurements and if the size of each layer increases fast enough, then an algorithm that finds a stationary point of (1) well either converge near x 0 or near a negative multiple of x 0 with high probability. As with the two layer case, signal recovery is possible when the output of the generative model is significantly under sampled, achieving genuine compressive sensing.

Notation
Let [n] = {1, . . . , n}. Let relu(x) = r(x) = max(x, 0) apply entrywise for x ∈ R n . Let diag(Ax > 0) be the diagonal matrix that is 1 in the (i, i)th entry and 0 otherwise. Let B(x, r) be the Euclidean ball of radius r centered at x.
. Let I n be the n × n identity matrix. Let A B mean that B − A is a positive semidefinite matrix. For matrices A, let A be the spectral norm of A. Let S k−1 be the unit sphere in R k . Let θ x,x 0 = ∠(x, x 0 ) and α x,x 0 = cos −1 1 π (π − θ x,x 0 ) cos θ x,x 0 + sin θ x,x 0 . For any nonzero x ∈ R n , letx = x/ x . For fixed x, y ∈ R n , let Mx ↔ŷ is the matrix such that x →ŷ,ŷ →x, and z → 0 for all z ∈ span({x, y}) ⊥ . For a set S, let |S| denote its cardinality. Let row-supp(A) be the set of indices corresponding to nonzero rows of A.

Organization of this paper
In Section 6, we prove Theorem 1 and state the technical lemmas used in its proof. We additionally state the technical lemmas used in the proof of Theorem 3. In the appendix, we prove the technical lemmas and Theorem 3. Most Lemmas are stated twice with two different numbers.

Lemma Statements and Proof of Theorem 1
We prove Theorems 1 and 3 using arguments from probabilistic concentration theory. Specifically, we show that the descent vector v concentrates around its expectation. Hence, v is nonzero with high probability in regions where its expectation is not small in norm.

Central Technical Lemma
The central technical lemma concerns concentration of the matrices A t +,x A +,y and A t +,x C t CA +,y uniformly over all x, y. For any nonzero x, y, let θ x,y = ∠(x, y) ∈ [0, π]. Define Q x,y := π−θx,y wherex = x/ x 2 ,ŷ = y/ y 2 , and Mx ↔ŷ is the matrix such thatx →ŷ,ŷ →x, and z → 0 for all In the special case that x = y, we have Here c, γ are constants that depend only on ǫ.

Technical Lemmas for proof of Theorem 1
The central result about matrix concentration allows us to prove concentration of matrices of the form A t +,x B t +,x B +,x A +,x and of vectors A t +,x B t +,x B +,y A +,y y. These are established in the next two lemmas.
Here, c and γ are constants that depend only on ǫ.
entries. If n 1 ≥ ck log k and if n 2 ≥ cn 1 log n 1 , then with probability at least 1 − 24n 1 e −γk − 10n 2 e −γn 1 , for all x = 0 and y = 0, Here, c 1 and c 2 are constants that depend only on ǫ.
The following lemma is a matrix RIP-like condition for C acting on the range of B +,x A +,x for all x ∈ R k . Note that C t C ≈ I n 2 when m < n 2 . We note that a closely related statement to Lemma 8 appears as Lemma 4.2 in [3]. We require a stronger condition, which we state as follows.
Here, c and γ are constants that depend only on ǫ.
We must also establish that C acts like an isometry for certain vectors given by the points of non-differentiability of f . Letting A 0,x = diag(Ax = 0)A. That is, A 0,x keeps only the rows of A that are orthogonal to x. where Here, c and γ are constants that depend only on ǫ.
In order to bound the spectral norm of A 0,x and B 0,x , we bound the spectral norm of matrices formed by selecting arbitrary subsets of a fraction of rows of a Gaussian matrix.
Lemma 10 (Also Lemma 28). Let where d is an integer greater than 1 and let g x,x 0 and θ 1 , θ 2 . . . , θ d−1 be defined by where θ 0 is the angle between x and x 0 , and we assume ǫd 2 2 2d is bounded above by some universal constant. Defineζ In particular, we have

Proof of Theorem 1
Using the Lemmas in the previous section, we may prove the theorem in the two-layer case.
Proof of Theorem 1. Let It suffices to prove ∀x ∈ S 50ǫ,x 0 , D −v f (x) < 0. For brevity in notation we will let r(x) = relu(x). For a fixed x and sufficiently small t, we have r( By Lemma 6, if n 1 > ck log k and n 2 > cn 1 log n 1 , then P( y 2x . By Lemma 7, if n 1 > ck log k and n 2 > By Lemma 9, if m > ck log(n 1 n 2 ), then P( Let E 6 be the event that A 0,x ≤ ǫ/6 ∀x = 0, and let E 7 be the event that B 0,x ≤ ǫ/6 ∀x = 0. Because any k independent Gaussians are linearly independent with probability 1, Lemma 11 provides that there exists δ > 0 such that if n 1 ≥ 36k/ǫ 2 , then P( We can now compute the directional derivative of f in the direction of −v. On E 4 , where the fifth line follows from the definition of E 4 , and r x 2 ≤ x 2 ; and the last line follows from the triangle inequality, A +,x ≤ A and B +,x ≤ B for all x = 0, and ǫ < 1.
To complete the argument, we continue from (43), using (46) and (10), where the inequality follows by definitions of the events E 3 and E 2 , and because x, h x, The proof is finished by observing that Lemma 10 establishes that S ǫ,x 0 is contained in the union of two balls of radius at most a monotonic function in ǫ.

Technical Lemmas for proof of Theorem 3
Lemma 11 (Also Lemma 26).
Lemma 12 (Also Lemma 27). and Here, c i are constants that depend only on ǫ, and K is a universal constant.
Here, c and γ are constants that depend only on ǫ. [

A Central Technical Lemmas on Uniform Matrix Concentration
In this section, we prove the central lemmas about concentration of the matrices A t +,x A +,y and A t +,x C t CA +,y uniformly over all x, y. Recall the definition that A +,x = diag(Ax > 0)A and wherex = x/ x 2 ,ŷ = y/ y 2 , and Mx ↔ŷ is the matrix such thatx →ŷ,ŷ →x, and z → 0 for all z ∈ span({x, y}) ⊥ . An elementary calculation shows that if A ∈ R n×k has i.i.d. N (0, 1/n) entries, then Q x,y = EA t +,x A +,y .
Lemma 14 (Also Lemma 5). Fix 0 < ǫ < 1. Let A ∈ R n×k have i.i.d. N (0, 1/n) entries. If n > ck log k, then with probability at least 1 − 8ne −γk , In the special case that x = y, we have Here c, γ are constants that depend only on ǫ.
We will prove this lemma by separately establishing high probability matrix upper bounds and lower bounds for A t +,x A +,y . We now introduce some notation in order to state these bounds. Let When applied to a vector, let h −ǫ and h ǫ act component-wise. Let a t i be the ith row of A. Note that A t +,x A +,y = n i=1 1 a i ·x>0 1 a i ·y>0 · a i a t i , and define First we establish a matrix upper bound on G −ǫ (x, y) uniformly over all nonzero x, y. For ease of exposition, in the next two Lemmas, we will take the entries of A to be i.i.d. N (0, 1). In this case, Here, c and γ are constants that depend only on ǫ.
Proof. In this proof, the values of the constants c and γ may change from line to line, but they are all bounded above and below, respectively, by some ǫ-dependent constant. Without loss of generality, let x, y ∈ S k−1 .
We now bound E[1 −ǫ≤a i ·x≤0 · a i a t i ]. For deriving this bound, we may take x = e 1 without loss of generality. We have Thus, E[1 −ǫ<a i ·x<0 · a i a t i ] ǫ 2 I k for any x = 0, resulting in Second, we show concentration of G −ǫ (x, y) for fixed x, y ∈ S k−1 . Let Note that ξ i is sub-Gaussian for all i and that the sub-Gaussian norm of ξ i is bounded above by an absolute constant, which we will call K. By the first part of Remark 5.40 in [17], there exist constants c K and γ K such that for all t ≥ 0, with probability at least 1 − 2e −γ K t 2 , If n > (2/ǫ) 2 c 2 K k, t = ǫ √ n/2, and ǫ < 1, we have that with probability at least 1 − 2e −γ K ǫ 2 n/4 , Third, we bound the Lipschitz constant of G −ǫ . Forx,ỹ ∈ R k we have Thus, where the second inequality follows because |h −ǫ (z)| ≤ 1 for all z, and where the third inequality follows because h −ǫ is 1/ǫ-Lipschitz. , there exists a constant γ 0 such that for fixed i, a i 2 ≤ 2 √ k with probability at least 1 − e −γ 0 k . Thus, for all x, y,x,ỹ ∈ S k−1 . Finally, we complete the proof by a covering argument. Let N δ be a δ-net on S k−1 such that (16) and (13), we have . If n >ck log k, for an appropriatec, then this probability is at least 1 − 2e −γn for someγ > 0. For any x, y ∈ S k−1 , letx,ỹ ∈ N δ be such that x −x 2 < δ and y −ỹ 2 < δ. By (17), we have that In conclusion, the result of this lemma holds if n > (2/ǫ) 2 c 2 K k and n >ck log k, with probability N (0, 1) entries. If n > ck log k, then with probability at least 1 − 4ne −γk , ∀x = 0, y = 0, G ǫ (x, y) nQ x,y − 3ǫnI k Here, c and γ are constants that depend only on ǫ.
Proof. The proof follows that of Lemma 15 exactly.
First, we bound E[G ǫ (x, y)] for fixed x, y ∈ S k−1 . For deriving this bound, we take x = e 1 without loss of generality. Noting that h ǫ (z) ≥ 1 z>0 (z) − 1 0≤z≤ǫ (z) for all z, we have We have Thus, E[1 0≤a i ·x≤ǫ · a i a t i ] ǫ 2 I k for any x = 0, resulting in Second, the same argument as in Lemma 15 provides that for fixed x, y ∈ S k−1 , if n > (2/ǫ) 2 c 2 K k, then we have that with probability at least 1 − 2e −γ K ǫ 2 n/4 , Third, the same argument as in Lemma 15 provides that on the event E 1 ∩ E 2 , we have for all x, y,x,ỹ ∈ S k−1 . Finally, we complete the proof by an identical covering argument as in Lemma 15. We have that if n > c 0 k log k then with probability at least 1 − 4ne −γk , ∀x, y ∈ S k−1 , G ǫ (x, y) nQ x,y − 3ǫnI k .
We may now prove Lemma 5.

Proof of Lemma 5 / Lemma 14. The result is immediate if
For all nonzero x and y , G ǫ (x, y) A t +,x A +,y G −ǫ (x, y). The lemma then follows directly from Lemmas 15 and 16.

B Control of Terms with Compression
We will make use of a standard compressed sensing RIP lemma from [5].
Proof. This proof is an immediate extension of Lemma 5.1 in Baraniuk. As C is Gaussian, we may take T to be the span of k standard basis vectors and directly apply the lemma in that paper. The inner product form follows by a standard argument based on the parallelogram identity. The last inequality holds by applying the second inequality to all subspaces of the form span(V i , W j ), which have dimension at most 2k, and by applying a union bound.
Here, c and γ are constants that depend only on ǫ.
Proof. It suffices to show that In order to apply Lemma 17, we will show that {B +,x A +,x w | x, w ∈ S k−1 } is a subset of a union of at most (n 2 1 n 2 ) k subspaces of dimension at most k.
where V is a union of at most (n 2 1 n 2 ) k subspaces of dimensionality at most k. By applying Lemma 17 to the sets V and V , we get that for fixed A, B, with probability at least 1 − (c 1 n 2 1 n 2 /ǫ) 2k e −γ 1 ǫm ≥ 1 − e −γ 2 m , provided m ≥ck log(n 1 n 2 ), for some γ 2 > 0,c > 0.
Integrating over the probability space of (A, B), independence of C and (A, B) implies that (19) holds for random (A, B) with the same probability bound.
Lemma 19. Let V be a subspace of R k with dimension at least 5. Let A ∈ R n×k have i.i.d. N (0, 1/n) entries. With probability 1, the following hold Proof. Let ℓ = dim V . By rotational invariance of Gaussians, we may take V = span(e 1 , . . . , e ℓ ) without loss of generality. Without loss of generality, we may let A have dimensions n × ℓ and take V = R ℓ .
To establish the first inequality, we will appeal to a classical result from sphere covering [18]. If n hyperplanes in R ℓ contain the origin and are such that the normal vectors to any subset of ℓ of those hyperplanes are independent, then the complement of the union of these hyperplanes is partitioned into at most 2 ℓ−1 i=0 n − 1 i disjoint regions. Note that for fixed A, |{diag(Av > 0)A | v ∈ R ℓ }| equals the number of binary vectors of the form (1 a i ·v>0 ) i∈ [n] for v ∈ S ℓ−1 . Each such binary vector corresponds uniquely to one of the disjoint regions given by partitioning the unit sphere in R ℓ by the n half-spaces going through the origin with normal vectors {a i } i∈ [n] . With probability 1, any subset of ℓ rows of A are linearly independent, and thus, where the first inequality uses the fact that n ℓ ≤ (en/ℓ) ℓ and the second inequality uses that ℓ ≥ 5. To establish the third inequality, note that if ℓ rows of A ∈ R n×ℓ are orthogonal to a nonzero v ∈ R ℓ , then those rows are linearly dependent. With probability 1, any subset of ℓ rows of A are independent with probability 1, and thus To establish the second inequality, we note that because of (23), |{diag(Av = 0)A | v ∈ R ℓ }| is at most the number of ways to select at most ℓ − 1 of the n rows of A. Thus, where the last inequality uses that ℓ ≥ 4.
Proof. In order to apply Lemma 17, we will find a probability 1 event on which {y x,x 0 | x, x 0 = 0} and {z x,x 0 | x, x 0 = 0} are respectively in the union of at most M = n 3k 1 n 3k 2 and N = 2 2k n 4k 1 n 2k 2 subspaces of dimensionality at most 2k.
, and B + = {B +,x | x = 0}. Let row-supp(A) be the set of indices corresponding to nonzero rows of A. By Lemma 20, there exists a probability 1 event, E, over (A, B) on which |A 0 | ≤ n k 1 ; |A + | ≤ n k 1 ; | row-supp(Â)| < k ∀Â ∈ A 0 ; |B 0 | ≤ n k 1 n k 2 ; |B + | ≤ n k 1 n k 2 ; and | row-supp(B)| < k ∀B ∈ B 0 . For any (A, B) ∈ E, we have that where the right hand side of this inclusion involves at most n 3k 1 n 3k 2 subspaces of dimension at most 2k.
For any (A, B) ∈ E, we have that where the right hand side of this inclusion involves at most 2 2k n 4k 1 n 2k 2 subspaces of dimension at most 3k.

C Properties of A +,x
With Lemma 5, we will now prove several technical lemmas of the behavior of A +,x as a function of x. N (0, 1/n) entries. If n > ck log k, then with probability at least 1 − 8ne −γk , we have that for all x = 0, y = 0, Here, c and γ are constants that depend only on ǫ.
Proof. Without loss of generality, let x 2 = y 2 = 1. We have The second part of Lemma 5 provides that there exist constants c, γ such that if n > ck log k, then with probability at least 1 − 8ne −γk , A t +,x A +,x − I k /2 ≤ ǫ/4. As ǫ < 1, we have

Thus,
where the last inequality uses that ǫ ≤ 1.
Note that there exists δ such that ( e δ ) δ ≤ e ǫ 2 /36 because lim δ→0 ( e δ ) δ = 1. Thus, by a union bound, the probability that A Ω ≤ ǫ for all Ω such that |Ω| = ⌊δn⌋ is at least and whereθ i is the expected value of the angle between Π 1 i=d W i,+,x x and Π 1 i=d W i,+,x 0 x 0 . If n i+1 ≥ cn i log n i , then with probability at least 1 − d−1 i=0 c i n i+1 e −γn i , for all x = 0 and y = 0, Here, c i are constants that depend only on ǫ, and K is a universal constant.
Proof. Define . . W 1,+,x (x) and analogously, y d := Π 1 i=d W i,+,y y Thus x = x 0 and y = y 0 . Also define θ i := θ x i ,y i as the random variable which is the angle between x i and y i . When taking products of elements in a non-commutative space we allow the indices of a product to run backward, while if the product of scalars has indices which run from a larger integer to a smaller one, we use the convention that this is an empty product equal to 1. We use ≈ to denote equality up to O(max( x 2 , y 2 ) ǫ(d−1) 2 d−1 ) with high probability, with the appropriate concentration bound. We have Where in the third line we used that max i W i,+,x ≤ 1 2 + ǫ for all x. In the 5th line we used that Therefore, where we used that 1+x We also use that and the analogous lower bound, where the last inequality uses Solving this recurrence relation with Γ 0 := y, we get (π −θ j ) 2π Thus, we have Lemma 28 (Also Lemma 10). Let where d is an integer greater than 1 and let g x,x 0 and θ 1 , θ 2 . . . , θ d−1 be defined by where θ 0 is the angle between x and x 0 , and we assume ǫd 2 2 2d is bounded above by some universal constant. Defineζ whereθ 0 = π andθ i , i = 1, 2, 3, . . . d − 1 is defined iteratively by (39). If x ∈ S ǫ,x 0 , then we have that either θ 0 = π + O(4d2 d √ ǫ) and In particular, we have where we used that the θ i are defined by a function with derivative bounded by 1. Therefore, Combining the information from both cases, we use for any x, y where θ is the angle between x and y.
Proof. In order to apply Lemma 17, we will find a probability 1 event on which {y x,x 0 | x, x 0 = 0} and {z x,x 0 | x, x 0 = 0} are respectively in the union of at most M = (Π d i=1 n i ) 2k and N = (Π d i=1 n i ) 2kd 2 kd subspaces of dimensionality at most (2 d + 2)k. For fixed W 1 , . . . , W d , let W i, where the right hand side of this inclusion involves at most (Π d i=1 n i ) 2k subspaces of dimension at most 2k.
Applying Lemma 17 with M = (Π d i=1 n i ) 2k and N = (Π d i=1 n i ) 2kd 2 kd , we get that (40) holds with probability at least 1 − (2Π d i=1 n i ) 2k(d+1) (c 1 /ǫ) 2 d k e −γ 1 ǫm . Thus if m > ck2 d log(Π d i=1 n i ), we have (40) for a fixed A, B with probability at least 1 − e −γm . Integrating over (A, B) in the probability-1 event E provides (40) with the same probability bound when A and B are random.

F Proof of Theorem 3
Proof. Let E 1 be the event that v x,y + h x,y 2 ≤ K d 2 ǫ 2 d max( x 2 , y 2 ) for all x = 0, y = 0.
By Lemma 12, if ǫ < 1/4d and n i+1 ≥ cn i log n i then there is a universal constant K such that P(E 1 ) ≥ 1 − d i=1 c i n i e −γn i−1 . Let E 2 be the event that | Cy x,x 0 , Cz x,x 0 − y x,x 0 , z x,x 0 | ≤ ǫ y x,x 0 2 z x,x 0 2 for all x = 0, y = 0 By Lemma 13, if m > ck2 d log(Π d i=1 n i ), then P(E 2 ) ≥ 1 − e −γm . Let E 3 be the event that W i,+,x 2 ≤ 1 2 + ǫ/2 for all x = 0 and for all i = 1 . . . d. By Lemma 5, for a fixed i, if n i > cn i−1 log n i−1 , then W i,+,x ≤ 1+ǫ 2 with probability at least 1 − 8n i e −γn i−1 . Thus P(E 3 ) ≥ 1 − d i=1 c i n i e −γn i−1 . Let E 4 be the event that W i,0,x ≤ ǫ/2 for all x = 0 and for all i = 1 . . . d. By an immediate generalization of Lemma 20, we have that for all x = 0, with probability 1, W i,0,x has at most k nonzero rows. By Lemma 11, if n i > 36n i−1 /ǫ 2 , then W i,0,x ≤ ǫ/6. Thus P(E 4 ) ≥ 1 − d i=1 2e −ǫ 2 n i /36 . Let E 5 be the event that (Π 1 i=d W i,+,x ) t C t C(Π 1 i=d W i,+,x 0 ) − |(Π 1 i=d W i,+,x ) t (Π 1 i=d W i,+,x 0 ) ≤ ǫΠ d i=1 W i,+,x W i,+,x 0 for all x = 0, x 0 = 0. By an immediate generalization of Lemma 20, we have that for all x = 0, with probability 1, |{W i,+,x | x = 0}| ≤ n k 1 · · · n k i . Thus, for any w ∈ R k , Π 1 i=d W i,+,x w is in the union of Π d i=1 n i subspaces of dimension at most k. Applying Lemma 17, we get that if m ≥ dk log(Π d i=1 n i ), then P(E 5 ) ≥ 1 − e −γ 2 m . Before we compute the directional derivative of f , we define some notation. Let W i,+,x = diag(W i (W i−1,+,x x) > 0)W i . Let Note that h i 2 ≤ W i,+,x + W i,0,x h i−1 2 for all i, and thus on E 3 , h d 2 ≤ (1/2 + ǫ) d v 2 . We can now compute the directional derivative of f in the direction of −v. On E 2 ∩ E 3 , = v 2 − v 2 + 4 · 2(1/2 + ǫ) 2d max( x 2 , x 0 2 )ǫ (43) where the first inequality follows from the definition of E 2 , the third inequality follows from the definition of E 3 . Now we provide a lower bound for v 2 . For any x ∈ SK ǫ,x 0 , on where the second line follows by the triangle inequality, the third line follows by the definitions of E 1 , E 2 , and E 3 , and the fourth line follows because x ∈ SK ǫ,x 0 , ifK ≥ 3Kd 2 /2 d . To complete the argument, we continue from (43) using (46) It remains to prove that ∀x = 0, D x f (0) < 0. We compute that where, on the event defined by Lemma 12, where the inequality follows by definitions of the events E 3 and E 2 , and because x, h x,x 0 ≥ 0.075 2 d x 2 x 0 2 for all x = 0, x 0 = 0. Thus, for appropriately small ǫ, D x f (0) < 0. The proof is finished by applying Lemma 10 and noting that S ǫ,x 0 is contained in two balls of radius monotonic in ǫ.