Year: 2018

Abstract:
Deep neural networks provide state-of-the-art performance for image denoising, where the goal is to recover a near noise-free image from a noisy image. The underlying principle is that neural networks trained on large datasets have empirically been shown to be able to generate natural images well from a lowdimensional latent representation of the image. Given such a generator network, or prior, a noisy image can be denoised by finding the closest image in the range of the prior. However, there is little theory to justify this success, let alone to predict the denoising performance as a function of the networks parameters. In this paper we consider the problem of denoising an image from additive Gaussian noise, assuming the image is well described by a deep neural network with ReLu activations functions, mapping a k-dimensional latent space to an n-dimensional image. We state and analyze a simple gradient-descent-like iterative algorithm that minimizes a non-convex loss function, and provably removes a fraction of p1 ́Opk{nqq of the noise energy. We also demonstrate in numerical experiments that this denoising performance is, indeed, achieved by generative priors learned from data.

heading: 1 INTRODUCTION
text: We consider the image or signal denoising problem, where the goal is to remove noise from an unknown image or signal. In more detail, our goal is to obtain an estimate of an image or signal y˚ P Rn from y “ y˚ ` η, where η is unknown noise, often modeled as a zero-mean white Gaussian random variable with covariance matrix σ2{nI . Image denoising relies on modeling or prior assumptions on the image y˚. For example, suppose that the image y˚ lies in a k-dimensional subspace of Rn denoted by Y . Then we can estimate the original image by finding the closest point in `2-distance to the noisy observation y on the subspace Y . The corresponding estimate, denoted by ŷ, obeys
}ŷ ´ y˚}2 À σ2 k
n , (1)
with high probability (throughout, }¨} denotes the `2-norm). Thus, the noise energy is reduced by a factor of k{n over the trivial estimate ŷ “ y which does not use any prior knowledge of the signal. The denoising rate (1) shows that the more concise the image prior or image representation (i.e., the smaller k), the more noise can be removed. If on the other hand the prior (the subspace, in this example) does not include the original image y˚, then the error bound (1) increases as we would remove a significant part of the signal along with noise when projecting onto the range of the signal prior. Thus a concise and accurate prior is crucial for denoising.
Real world signals rarely lie in a priori known subspaces, and the last few decades of image denoising research have developed sophisticated and accurate image models or priors and algorithms. Examples include models based on sparse representations in overcomplete dictionaries such as wavelets (Donoho, 1995) and curvelets (Starck et al., 2002), and algorithms based on exploiting
self-similarity within images (Dabov et al., 2007). A prominent example of the former class of algorithms is the BM3D (Dabov et al., 2007) algorithm, which achieves state-of-the-art performance for certain denoising problems. However, the nuances of real world images are difficult to describe with handcrafted models. Thus, starting with the paper (Elad & Aharon, 2006) that proposes to learn sparse representation based on training data, it has become common to learn concise representation for denoising (and other inverse problems) from a set of training images.
In 2012, Burger et al. (Burger et al., 2012) applied deep networks to the denoising problem, by training a deep network on a large set of images. Since then, deep learning based denoisers (Zhang et al., 2017) have set the standard for denoising. The success of deep network priors can be attributed to their ability to efficiently represent and learn realistic image priors, for example via autodecoders (Hinton & Salakhutdinov, 2006) and generative adversarial models (Goodfellow et al., 2014). Over the last few years, the quality of deep priors has significantly improved (Karras et al., 2017; Ulyanov et al., 2017). As this field matures, priors will be developed with even smaller latent code dimensionality and more accurate approximation of natural signal manifolds. Consequently, the representation error from deep priors will decrease, and thereby enable even more powerful denoisers.
As the influence of deep networks in inverse problems grows, it becomes increasingly important to understand their performance at a theoretical level. Given that most optimization approaches for deep learning are first order gradient methods, a justification is needed for why they do not get stuck in local minima. The closest theoretical work to this question is Bora et al. (2017), which solves a noisy compressive sensing problem with generative priors by minimizing empirical risk. Under the assumption that the network is Lipschitz, they show that if the global optimizer can be found, which is in principle NP-hard, then a signal estimate is recovered to within the noise level. While the Lipschitzness assumption is quite mild, the resulting theory does not provide justification for why global optimality can be reached.
The most related work that establishes theoretical reasons for why gradient methods would not get stuck in local minima, when using deep generative priors for solving inverse problems, is Hand & Voroninski (2018). In it, the authors establish global favorability for optimization of the noiseless empirical risk function. Specifically, they show existence of a descent direction outside a ball around the global optimizer and a negative multiple of it in the latent space of the generative model. This work does not provide a specific algorithm which provably estimates the global minimizer, nor does it provide an analysis of the robustness of the problem with respect to noise.
In this paper, we propose the first algorithm for solving denoising with deep generative priors that provably finds an approximation of the underlying image. Following the lead of Hand & Voroninski (2018), we assume an expansive Gaussian model for the deep generative network in order to establish this result.
Contributions: The goal of this paper is to analytically quantify the denoising performance of deep-prior based denoisers. Specifically, we characterize the performance of a simple and efficient algorithm for denoising based on a d-layer generative neural network G : Rk Ñ Rn, with k ă n, and random weights. In more detail, we propose a gradient method with a tweak that attempts to minimize the least-squares loss fpxq “ 12}Gpxq ´ y}
2 between the noisy image y and an image in the range of the prior, Gpxq. While f is non-convex, we show that the gradient method yields an estimate x̂ obeying
}Gpx̂q ´ y˚}2 À σ2 k
n ,
with high probability, where the notation À absorbs a constant factor depending on the number of layers of the network, and its expansitivity, as discussed in more detail later. Our result shows that the denoising rate of a deep prior based denoiser is determined by the dimension of the latent representation.
We also show in numerical experiments, that this rate—shown to be analytically achieved for random priors—is also experimentally achieved for priors learned from real imaging data.

heading: 2 PROBLEM FORMULATION
text: We consider the problem of estimating a vector y˚ P Rn from a noisy observation y “ y˚ ` η. We assume that the vector y˚ belongs to the range of a d-layer generative neural network G : Rk Ñ Rn, with k ă n. That is, y˚ “ Gpx˚q for some x˚ P Rk. We consider a generative network of the form
Gpxq “ relupWd . . . relupW2 relupW1x˚qq . . .q,
where relupxq “ maxpx, 0q applies entrywise, Wi P Rniˆni´1 , are the weights in the i-th layer, ni is the number of neurons in the ith layer, and the network is expansive in the sense that k “ n0 ă n1 ă ¨ ¨ ¨ ă nd “ n. The problem at hand is: Given the weights of the network W1 . . .Wd and a noisy observation y, obtain an estimate ŷ of the original image y˚ such that }ŷ ´ y˚} is small and ŷ is in the range of G.

heading: 3 DENOISING VIA EMPIRICAL RISK MINIMIZATION
text: As a way to solve the above problem, we first obtain an estimate of x˚, denoted by x̂, and then estimate y˚ as Gpx̂q. In order to estimate x˚, we minimize the empirical risk objective
fpxq :“ 1 2 }Gpxq ´ y}2.
Since this objective is nonconvex, there is no a priori guarantee of efficiently finding the global minimum. Approaches such as gradient methods could in principle get stuck in local minima, instead of finding a global minimizer that is close to x˚.
However, as we show in this paper, under appropriate conditions, a gradient method with a tweak— introduced next—finds a point that is very close to the original latent parameter x˚, with the distance to the parameter x˚ controlled by the noise. In order to state the algorithm, we first introduce a useful quantity. For analyzing which rows of a matrix W are active when computing relupWxq, we let
W`,x “ diagpWx ą 0qW.
For a fixed weight matrix W , the matrix W`,x zeros out the rows of W that do not have a positive dot product with x. Alternatively put, W`,x contains weights from only the neurons that are active for the input x. We also define W1,`,x “ pW1q`,x “ diagpW1x ą 0qW1 and
Wi,`,x “ diagpWiWi´1,`,x ¨ ¨ ¨W2,`,xW1,`,xx ą 0qWi.
The matrix Wi,`,x consists only of the weights of the neurons in the ith layer that are active if the input to the first layer is x.
We are now ready to state our algorithm: a gradient method with a tweak informed by the loss surface of the function to be minimized. Given a noisy observation y, the algorithm starts with an arbitrary initial point x0 ‰ 0. At each iteration i “ 0, 1, . . ., the algorithm computes the step direction ṽxi “ pΠ1i“dWi,`,xiqtpGpxiq ´ yq, which is equal to the gradient of f if f is differentiable at xi. It then takes a small step opposite to ṽxi . The tweak is that before each iteration, the algorithm checks whether fp´xiq is smaller than fpxiq, and if so, negates the sign of the current iterate xi. This tweak is informed by the loss surface. To understand this step, it is instructive to examine the loss surface for the noiseless case in Figure 1. It can be seen that while the loss function has a global minimum at x˚, it is relatively flat close to ´x˚. In expectation, there is a critical point that is a negative multiple of x˚ with the property that the curvature in the ˘x˚ direction is positive, and the curvature in the orthogonal directions is zero. Further, around approximately ´x˚, the loss function is larger than around the optimum x˚. As a simple gradient descent method (without the tweak) could potentially get stuck in this region, the negation check provides a way to avoid converging to this region. Our algorithm is formally summarized as Algorithm 1 below.
Algorithm 1 Gradient method Require: Weights of the network Wi, noisy observation y, and step size α ą 0
1: Choose an arbitrary initial point x0 P Rkzt0u 2: for i “ 0, 1, . . . do 3: if fp´xiq ă fpxiq then 4: xi Ð ´xi; 5: end if 6: Compute ṽxi “ pΠ1i“dWi,`,xiqtpGpxiq ´ yq 7: xi`1 “ xi ´ αṽxi 8: end for
Other variations of the tweak are also possible. For example, the negation check in Step 2 could be performed after a convergence criterion is satisfied, and if a lower objective is achieved by negating the latent code, then the gradient descent can be continued again until a convergence criterion is again satisfied.

heading: 4 MAIN RESULTS
text: For our analysis, we consider a fully-connected generative network G : Rk Ñ Rn with Gaussian weights and no bias terms. Specifically, we assume that the weights Wi are independently and identically distributed as N p0, 2{niq, but do not require them to be independent across layers. Moreover, we assume that the network is sufficiently expansive:
Expansivity condition. We say that the expansivity condition with constant ą 0 holds if
ni ě c ´2 logp1{ qni´1 log ni´1, for all i,
where c is a particular numerical constant.
In a real-world generative network the weights are learned from training data, and are not drawn from a Gaussian distribution. Nonetheless, the motivation for selecting Gaussian weights for our analysis is as follows:
1. The empirical distribution of weights from deep neural networks often have statistics consistent with Gaussians. AlexNet is a concrete example (Arora et al., 2015).
2. The field of theoretical analysis of recovery guarantees for deep learning is nascent, and Gaussian networks can permit theoretical results because of well developed theories for random matrices.
3. It is not clear which non-Gaussian distribution for weights is superior from the joint perspective of realism and analytical tractability.
4. Truly random nets, such as in the Deep Image Prior (Ulyanov et al., 2017), are increasingly becoming of practical relevance. Thus, theoretical advances on random nets is of independent interest.
We are now ready to state our main result.
Theorem 1. Consider a network with the weights in the i-th layer,Wi P Rniˆni´1 , i.i.d. N p0, 2{niq distributed, and suppose that the network satisfies the expansivity condition for some ď K{d90. Also, suppose that the noise variance obeys
ω ď }x˚}K1 d16 , ω :“ c 18σ2 k n logpnd1nd´12 . . . ndq.
Consider the iterates of Algorithm 1 with stepsize α “ K4 1d2 . Then, there exists a number of steps N upper bounded by
N ď K2 d4 fpx0q }x˚}
such that after N steps, the iterates of Algorithm 1 obey
}xi ´ x˚} ď K5d9}x˚} ? `K6d6ω, for all i ě N, (2)
with probability at least 1´2e´2k logn´ řd i“2 8nie ´K7ni´2´8n1e´K7 2 logp1{ qk. Here,K1,K2, .. are numerical constants, and x0 is the initial point in the optimization.
The error term in the bound (2) consists of two terms—the first is controlled by , and the second depends on the noise. The first term is negligible if is chosen sufficiently small, but that comes at the expense of the expansivity condition being more stringent. The second term in the bound (2) is more interesting and controls the effect of noise. Specifically, for sufficiently small, our result guarantees that after sufficiently many iterations,
}xi ´ x˚}2 À σ2 k
n ,
where the notation À absorbs a factor logarithmic in n and polynomial in d. One can show that G is Lipschitz in a region around x˚1,
}Gpxiq ´Gpx˚q}2 À σ2 k
n .
Thus, the theorem guarantees that our algorithm yields the denoising rate of σ2k{n, and, as a consequence, denoising based on a generative deep prior provably reduces the energy of the noise in the original image by a factor of k{n. We note that the intention of this paper is to show rate-optimality of recovery with respect to the noise power, the latent code dimensionality, and the signal dimensionality. As a result, no attempt was made to establish optimal bounds with respect to the scaling of constants or to powers of d. The bounds provided in the theorem are highly conservative in the constants and dependency on the number of layers, d, in order to keep the proof as simple as possible. Numerical experiments shown later reveal that the parameter range for successful denoising are much broader than the constants suggest. As this result is the first of its kind for rigorous analysis of denoising performance by deep generative networks, we anticipate the results can be improved in future research, as has happened for other problems, such as sparsity-based compressed sensing and phase retrieval.

heading: 4.1 THE WEIGHT DISTRIBUTION CONDITION (WDC)
text: To prove our main result, we make use of a deterministic condition on G, called the Weight Distribution Condition (WDC), and then show that Gaussian Wi, as given by the statement of Theorem 1 are such that Wi{ ? 2 satisfies the WDC with the appropriate probability for all i, provided the expansivity condition holds. Our main result, Theorem 1, continues to hold for any weight matrices such that Wi{ ? 2 satisfy the WDC.
1The proof of Lipschitzness follows from applying the Weight Distribution Condition in Section 4.1.
The condition is on the spatial arrangement of the network weights within each layer. We say that the matrix W P Rnˆk satisfies the Weight Distribution Condition with constant if for all nonzero x, y P Rk,
›
›
›
n ÿ i“1 1〈wi,x〉ą01〈wi,y〉ą0 ¨ wiw t i ´Qx,y › › › ď , with Qx,y “ π ´ θ0 2π Ik ` sin θ0 2π Mx̂Øŷ, (3)
where wi P Rk is the ith row of W ; Mx̂Øŷ P Rkˆk is the matrix2 such that x̂ ÞÑ ŷ, ŷ ÞÑ x̂, and z ÞÑ 0 for all z P spanptx, yuqK; x̂ “ x{}x}2 and ŷ “ y{}y}2; θ0 “ =px, yq; and 1S is the indicator function on S. The norm in the left hand side of (3) is the spectral norm. Note that an elementary calculation3 gives thatQx,y “ Er řn i“1 1〈wi,x〉ą01〈wi,y〉ą0 ¨wiwtis forwi „ N p0, Ik{nq. As the rows wi correspond to the neural network weights of the ith neuron in a layer given by W , the WDC provides a deterministic property under which the set of neuron weights within the layer given by W are distributed approximately like a Gaussian. The WDC could also be interpreted as a deterministic property under which the neuron weights are distributed approximately like a uniform random variable on a sphere of a particular radius. Note that if x “ y, Qx,y is an isometry up to a factor of 1{2.

heading: 5 APPLICATIONS TO COMPRESSED SENSING
text: In this section we briefly discuss another important scenario to which our results apply to, namely regularizing inverse problems using deep generative priors. Approaches that regularize inverse problems using deep generative models (Bora et al., 2017) have empirically been shown to improve over sparsity-based approaches, see (Lucas et al., 2018) for a review for applications in imaging, and (Mardani et al., 2017) for an application in Magnetic Resonance Imaging showing a significant performance improvement over conventional methods.
Consider an inverse problem, where the goal is to reconstruct an unknown vector y˚ P Rn from m ă n noisy linear measurements:
z “ Ay˚ ` η P Rm,
where A P Rmˆn is called the measurement matrix and η is zero mean Gaussian noise with covariance matrix σ2{nI , as before. As before, assume that y˚ lies in the range of a generative prior G, i.e., y˚ “ Gpx˚q for some x˚. As a way to recover x˚, consider minimizing the empirical risk objective fpxq “ 12}AGpxq ´ z}, using Algorithm 1, with Step 6 substituted by ṽxi “ pAΠ1i“dWi,`,xiqtpAGpxiq ´ yq, to account for the fact that measurements were taken with the matrix A.
Suppose that A is a random projection matrix, for concreteness assume that A has i.i.d. Gaussian entries with variance 1{m. One could prove an analogous result as Theorem 1, but with ω “ b
18σ2 km logpn d 1n d´1 2 . . . ndq, (note that n has been replaced by m). This extension shows that,
provided is chosen sufficiently small, that our algorithm yields an iterate xi obeying
}Gpxiq ´Gpx˚q}2 À σ2 k
m ,
where again À absorbs factors logarithmic in the ni’s, and polynomial in d. Proving this result would be analogous to the proof of Theorem 1, but with the additional assumption that the sensing matrix A acts like an isometry on the union of the ranges of Π1i“dWi,`,xi , analogous to the proof in (Hand & Voroninski, 2018). This extension of our result shows that Algorithm 1 enables solving inverse problems under noise efficiently, and quantifies the effect of the noise.
2A formula for Mx̂Øŷ is as follows. If θ0 “ =px̂, ŷq P p0, πq and R is a rotation matrix such that x̂ and ŷ
map to e1 and cos θ0 ¨ e1 ` sin θ0 ¨ e2 respectively, then Mx̂Øŷ “ Rt ¨ ˝ cos θ0 sin θ0 0 sin θ0 ´ cos θ0 0 0 0 0k´2 ˛ ‚R, where 0k´2 is a k ´ 2ˆ k ´ 2 matrix of zeros. If θ0 “ 0 or π, then Mx̂Øŷ “ x̂x̂t or ´x̂x̂t, respectively. 3To do this calculation, take x “ e1 and y “ cos θ0 ¨ e1 ` sin θ0 ¨ e2 without loss of generality. Then each entry of the matrix can be determined analytically by an integral that factors in polar coordinates.
We hasten to add that the paper (Bora et al., 2017) also derived an error bound for minimizing empirical loss. However, the corresponding result (for example Lemma 4.3) differs in two important aspects to our result. First, the result in (Bora et al., 2017) only makes a statement about the minimizer of the empirical loss and does not provide justification that an algorithm can efficiently find a point near the global minimizer. As the program is non-convex, and as non-convex optimization is NP-hard in general, the empirical loss could have local minima at which algorithms get stuck. In contrast, the present paper presents a specific practical algorithm and proves that it finds a solution near the global optimizer regardless of initialization. Second, the result in (Bora et al., 2017) considers arbitrary noise η and thus can not assert denoising performance. In contrast, we consider a random model for the noise, and show the denoising behavior that the resulting error is no more than Opk{nq, as opposed to }η}2 « Op1q, which is what we would get from direct application of the result in (Bora et al., 2017).

heading: 6 EXPERIMENTAL RESULTS
text: In this section we provide experimental evidence that corroborates our theoretical claims that denoising with deep priors achieves a denoising rate proportional to σ2k{n. We consider both a synthetic, random prior, as studied theoretically in the paper, as well as a prior learned from data. All our results are reproducible with the code provided in the supplement.

heading: 6.1 DENOISING WITH A SYNTHETIC PRIOR
text: We start with a synthetic generative network prior with ReLu-activation functions, and draw its weights independently from a Gaussian distribution. We consider a two-layer network with n “ 1500 neurons in the output layer, 500 in the middle layer, and vary the number of input neurons, k, and the noise level, σ. We next present simulations showing that if k is sufficiently small, our algorithm achieves a denoising rate proportional to σk{n as guaranteed by our theory. Towards this goal, we generate Gaussian inputs x˚ to the network and observe the noisy image y “ Gpx˚q ` η, η „ N p0, σ2{nIq. From the noisy image, we first obtain an estimate x̂ of the latent representation by running Algorithm 1 until convergence, and second we obtain an estimate of the image as ŷ “ Gpx̂q. In the left and middle panel of Figure 3, we depict the normalized mean squared error of the latent representation, MSEpx̂, x˚q, and the mean squared error in the image domain, MSEpGpx̂q, Gpx˚qq, where we defined MSEpz, z1q “ }z ´ z1}2. For the left panel, we fix the noise variance to σ2 “ 0.25, and vary k, and for the middle panel we fix k “ 50 and vary the noise variance. The results show that, if the network is sufficiently expansive, guaranteed by k being sufficiently small, then in the noiseless case (σ2 “ 0), the latent representation and image are perfectly recovered. In the noisy case, we achieve a MSE proportional to σ2k{n, both in the representation and image domains.
We also observed that for the problem instances considered here, the negation trick in step 3-4 of Algorithm 1 is often not necessary, in that even without that step the algorithm typically converges to the global minimum. Having said this, in general the negation step is necessary, since there exist problem instances that have a local minimum opposite of x˚.

heading: 6.2 DENOISING WITH A LEARNED PRIOR
text: We next consider a prior learned from data. Technically, for such a prior our theory does not apply since we assume the weights to be chosen at random. However, the numerical results presented in this section show that even for the learned prior we achieve the rate predicted by our theory pertaining to a random prior. Towards this goal, we consider a fully-connected autoencoder parameterized by k, consisting of an decoder and encoder with ReLu activation functions and fully connected layers. We choose the number of neurons in the three layers of the encoder as 784, 400, k, and those of the decoder as k, 400, 784. We set k “ 10 and k “ 20 to obtain two different autoencoders. We train both autoencoders on the MNIST (Lecun et al., 1998) training set.
We then take an image y˚ from the MNIST test set, add Gaussian noise to it, and denoise it using our method based on the learned decoder-network G for k “ 10 and k “ 20. Specifically, we estimate
the latent representation x̂ by running Algorithm 1, and then set ŷ “ Gpx̂q. See Figure 2 for a few examples demonstrating the performance of our approach for different noise levels.
We next show that this achieves a mean squared error (MSE) proportional to σ2k{n, as suggested by our theory which applies for decoders with random weights. We add noise to the images with noise variance ranging from σ2 “ 0 to σ2 “ 6. In the right panel of Figure 3 we show the MSE in the image domain, MSEpGpx̂q, Gpx˚qq, averaged over a number of images for the learned decoders with k “ 10 and k “ 20. We observe an interesting tradeoff: The decoder with k “ 10 has fewer parameters, and thus does not represent the digits as well, therefore the MSE is larger than that for k “ 20 for the noiseless case (i.e., for σ “ 0). On the other hand, the smaller number of parameters results in a better denoising rate (by about a factor of two), corresponding to the steeper slope of the MSE as a function of the noise variance, σ2.

heading: A PROOFS
text: In this section we prove our main result, Theorem 1. Instead of proving Theorem 1 as stated, we will prove the following equivalent rescaled statement for when Wi have i.i.d. N p0, 1{niq entries. Because of this rescaling, Gpxq scales like 2´d{2}x}, the noise ω is assumed to scale like 2´d{2, ∇f scales like 2d, and α scales like 2d. Theorem 2. Consider a network with the weights in the i-th layer,Wi P Rniˆni´1 , i.i.d. N p0, 1{niq distributed, and suppose that the network satisfies the expansivity condition for some ď K{d90. Also, suppose that the noise variance obeys
ω ď }x˚}K12´d{2
d16 , ω :“
c
18σ2 k
n logpnd1nd´12 . . . ndq.
Consider the iterates of Algorithm 1 with stepsize α “ K4 2 d
d2 . Then, there exists a number of steps N upper bounded by
N ď K2 d4
fpx0q2d
}x˚} such that after N steps, the iterates of Algorithm 1 obey
}xi ´ x˚} ď K5d9}x˚} ? `K6d62d{2ω, for all i ě N, (4)
with probability at least 1´2e´2k logn´ řd i“2 8nie ´K7ni´2´8n1e´K7 2 logp1{ qk. Here,K1,K2, .. are numerical constants, and x0 is the initial point in the optimization.
As mentioned in Section 4.1, our proof makes use of a deterministic condition, called the Weight Distribution Condition (WDC), formally defined in Section 4.1. The following proposition establishes that the expansivity condition ensures that the WDC holds: Lemma 3 (Lemma 9 in (Hand & Voroninski, 2018)). Fix P p0, 1q. If the entires of Wi P Rniˆni´1 are i.i.d. N p0, 1{niq and the expansivity condition ni ą c ´2 logp1{ qni´1 log ni´1 holds, then Wi satisfies the WDC with constant with probability at least 1 ´ 8nie´K
2ni´1 . Here, c and K are numerical constants.
We note that the form of dependence of ni on can be read off the proofs of Lemma 10 in (Hand & Voroninski, 2018). It follows from Lemma 3, that the WDC holds for all Wi with probability at least 1´
řd i“2 8nie ´K7ni´2 ´ 8n1e´K7 2 logp1{ qk.
In the remainder of the proof we work on the event that the WDC holds for all Wi.

heading: A.1 PRELIMINARIES
text: Recall that the goal of our algorithm is to minimize the empirical risk objective
fpxq “ 1 2 }Gpxq ´ y}2,
where y :“ Gpx˚q ` η, with η „ N p0, σ2{nIq. Our results rely on the fact that outside of two balls around x “ x˚ and x “ ´ρdx˚, with ρd a constant defined below, the direction chosen by the algorithm is a descent direction, with high probability. Towards this goal, we use a concentration argument, similar to the arguments used in (Hand & Voroninski, 2018). First, define Λx :“ Π1i“dWi,`,x (with Wi,`,x defined in Section 3) for notational convenience, and note that the step direction of our algorithm can be written as
ṽx “ vx ` q̄x, with vx :“ ΛtxΛxx´ pΛxqtpΛx˚qx˚, and q̄x :“ Λtxη. (5) Note that at points x where G (and hence f ) is differentiable, we have that ṽx “ ∇fpxq. The proof is based on showing that ṽx concentrates around a particular hx P Rk, defined below, that is a continuous function of nonzero x, x˚ and is zero only at x “ x˚ and x “ ´ρdx˚. The
definition of hx depends on a function that is helpful for controlling how the operator x ÞÑ W`,xx distorts angles, defined as:
gpθq :“ cos´1 ´ pπ ´ θq cos θ ` sin θ
π
¯
. (6)
With this notation, we define
hx :“ ´ 1
2d
´ d´1 ź
i“0
π ´ θi π ¯ x˚ ` 1 2d
«
x´ d´1 ÿ
i“0
sin θi π ´
d´1 ź
j“i`1
π ´ θj π ¯}x˚}2 }x}2 x
ff
,
where θ0 “ =px, x˚q and θi “ gpθi´1q. Note that hx is deterministic and only depends on x, x˚, and the number of layers, d.
In order to bound the deviation of ṽx from hx we use the following two lemmas, bounding the deviation controlled by the WDC and the deviation from the noise: Lemma 4 (Lemma 6 in (Hand & Voroninski, 2018)). Suppose that the WDC holds with ă 1{p16πd2q2. Then, for all nonzero x, x˚ P Rk,
}vx ´ hx}2 ď K d3 ?
2d maxp}x}2, }x˚}2q, and (7)
@ pΠ1i“dWi,`,xqx, pΠ1i“dWi,`,x˚qx˚ D ě 1 4π 1 2d }x}2}x˚}2, and (8)
› ›Π1i“dWi,`,x › › 2 ď 1 2d p1` 2 qd ď 13 12 2´d. (9)
Proof. Equation (7) and (8) are Lemma 6 in (Hand & Voroninski, 2018). Regarding (9), note that the WDC implies that }Wi,`,x}2 ď 1{2` . It follows that
› ›Π1i“dWi,`,x › › 2 ď 1 2d p1` 2 qd “ 1 2d ed logp1`2 q ď 1` 4 d 2d ď 13 12 2´d,
where the last inequalities follow by our assumption on .
Lemma 5. Suppose the WDC holds with ă 1{p16πd2q2, that any subset of ni´1 rows of Wi are linearly independent for each i, and that η „ N p0, σ2{nIq. Then the event
Enoise :“ ! › ›pΠ1i“dWi,`,xqtη › › ď ω 2d{2 , for all x )
, ω :“ c 16σ k
n logpnd1nd´12 . . . ndq (10)
holds with probability at least 1´ 2e´2k logn.
As the cost function f is not differentiable everywhere, we will make use of the generalized subdifferential in order to reference the subgradients at nondifferentiable points. For a Lipschitz function f̃ defined from a Hilbert space X to R, the Clarke generalized directional derivative of f̃ at the point x P X in the direction u, denoted by f̃opx;uq, is defined by f̃opx;uq “ lim supyÑx,tÓ0 f̃py`tuq´f̃pyq t , and the generalized subdifferential of f̃ at x, denoted by Bf̃pxq, is defined by Bf̃pxq “ tv P Rk | xv, uy ď f̃opx;uq, for all u P X u.
Since fpxq is a piecewise quadratic function, we have
Bfpxq “ convpv1, v2, . . . , vtq, (11)
where conv denotes the convex hull of the vectors v1, . . . , vt, t is the number of quadratic functions adjoint to x, and vi is the gradient of the i-th quadratic function at x. Lemma 6. Under the assumption of Lemma 5, and assuming that Enoise holds, we have that, for any x ‰ 0 and any vx P Bfpxq,
}vx ´ hx} ď K d3 ?
2d maxp}x}2, }x˚}2q `
ω
2d{2 .
In particular, this holds for the subgradient vx “ ṽx.
Proof. By (11), Bfpxq “ convpv1, . . . vtq for some finite t, and thus vx “ a1v1 ` . . . atvt for some a1, . . . , at ě 0, ř
i ai “ 1. For each vi, there exists a w such that vi “ limtÓ0 ṽx`tw. On the event Enoise, we have that for any x ‰ 0, for any ṽx P Bfpxq
}ṽx ´ hx} “ }vx ` q̄x ´ hx} ď }vx ´ hx} ` }q̄x}
ď Kd 3 ?
2d maxp}x}2, }x˚}2q `
ω
2d{2 ,
where the last inequality follows from Lemmas 4 and 5 above. The proof is concluded by appealing to the continuity of hx with respect to nonzero x, and by noting that
}vx ´ hx} ď ÿ
i
ai}vi ´ hx} ď K d3 ?
2d maxp}x}2, }x˚}2q `
ω
2d{2 ,
where we used the inequality above and that ř i ai “ 1.
We will also need an upper bound on the norm of the step direction of our algorithm: Lemma 7. Suppose that the WDC holds with ă 1{p16πd2q2 and that the event Enoise holds with ω ď 2
´d{2}x˚} 8π . Then, for all x,
}ṽx} ď dK
2d maxp}x}, }x˚}q, (12)
where K is a numerical constant.
Proof. Define for convenience ζj “ śd´1 i“j π´θ̄j,x,x˚ π . We have
}ṽx} ď}hx} ` }hx ´ ṽx}
ď
›
›
›
›
›
1 2d x´ 1 2d ζ0x˚ ´ 1 2d
d´1 ÿ
i“0
sin θ̄i,x π ζi`1 }x˚} }x} x
›
›
›
›
›
`K1 d3 ?
2d maxp}x}2, }x˚}2q `
ω
2d{2
ď 1 2d }x} `
ˆ
1 2d ` d π2d
˙ }x˚} `K1 d3 ?
2d maxp}x}, }x˚}q `
ω
2d{2
ďdK 2d maxp}x}, }x˚}q,
where the second inequality follows from the definition of hx and Lemma 6, the third inequality uses |ζj | ď 1, and the last inequality uses the assumption ω ď 2 ´d{2}x˚}
8π .

heading: A.2 PROOF OF THEOREM 2
text: We are now ready to prove Theorem 2. The logic of the proof is illustrated in Figure 4. Recall that xi is the ith iterate of x as per Algorithm 1. We first ensure that we can assume throughout that xi is bounded away from zero: Lemma 8. Suppose that WDC holds with ă 1{p16πd2q2 and that Enoise holds with ω in (10) obeying ω ď 2
´d{2}x˚} 8π . Moreover, suppose that the step size in Algorithm 1 satisfies 0 ă α ă K2d d2 ,
where K is a numerical constant. Then, after at most N “ p 38πK02 d
α q 2 steps, we have that for all
i ą N that xi R Bp0,K0}x˚}q, K0 “ 132π .
In particular, if α “ K2d{d2, then N is bounded by a constant times d4. We can therefore assume throughout this proof that xi R Bp0,K0}x˚}q, K0 “ 132π . We prove Theorem 2 by showing that if }hx} is sufficiently large, i.e., if the iterate xi is outside of set
Sβ “ ! x P Rk | }hx} ď 1
2d βmaxp}x}, }x˚}q
)
,
with
β “ 4Kd3 ? ` 13ω2d{2{}x˚}, (13)
then the algorithm makes progress in the sense that fpxi`1q´fpxiq is smaller than a certain negative value. The set Sβ is contained in two balls around x˚ and ´ρx˚, whose radius is controlled by β: Lemma 9. For any β ď 1642d12 ,
Sβ Ă Bpx˚, 5000d6β}x˚}2q Y Bp´ρdx˚, 500d11 a β}x˚}2q. (14)
Here, ρd ą 0 is defined in the proof and obeys ρd Ñ 1 as dÑ8.
Note that by the assumption ω ď }x˚}K12 ´d{2 d16 and Kd 45 ? ď 1, our choice of β in (13) obeys β ď 1642d12 for sufficiently small K1,K, and thus Lemma 9 yields:
Sβ Ă Bpx˚, rq Y Bp´ρdx˚, b r}x˚}d8q.
were we define the radius r “ K2d9 ? }x˚} `K3d6ω2d{2, where K2,K3 are numerical constants. Note that hat the radius r is equal to the right hand side in the error bound (4) in our theorem. In order to guarantee that the algorithm converges to a ball around x˚, and not to that around ´ρdx˚, we use the following lemma:
Lemma 10. Suppose that the WDC holds with ă 1{p16πd2q2. Moreover suppose that Enoise holds, and that ω in the event Enoise obeys ω2´d{2}x˚}2 ď K9{d
2, where K9 ă 1 is a universal constant. Then for any φd P rρd, 1s, it holds that
fpxq ă fpyq (15)
for all x P Bpφdx˚,K3d´10}x˚}q and y P Bp´φdx˚,K3d´10}x˚}q, where K3 ă 1 is a universal constant.
In order to apply Lemma 10, define for convenience the two sets:
S`β :“Sβ X Bpx˚, rq, and
S´β :“Sβ X Bp´ρdx˚, b r}x˚}d8q.
By the assumption that Kd45 ? ď 1 and ω ď K1d´162´d{2}x˚}, we have that for sufficiently small K1,K,
S`β Ď Bpx˚,K3d ´10}x˚}q and S´β Ď Bp´ρdx˚,K3d ´10}x˚}q.
Thus, the assumptions of Lemma 10 are met, and the lemma implies that for any x P S´β and y P S`β , it holds that fpxq ą fpyq. We now show that the algorithm converges to a point in S ` β . This fact and the negation step in our algorithm (line 3-5) establish that the algorithm converges to a point in S`β if we prove that the objective is nonincreasing with iteration number, which will form the remainder of this proof.
Consider i such that xi R Sβ . By the mean value theorem (Clason, 2017, Theorem 8.13), there is a t P r0, 1s such that for x̂i “ xi ´ tαṽxi there is a vx̂i P Bfpx̂iq, where Bf is the generalized subdifferential of f , obeying
fpxi ´ αṽxiq ´ fpxiq “xvx̂i ,´αṽxiy “xṽxi ,´αṽxiy ` xvx̂i ´ ṽxi ,´αṽxiy ď ´ α}ṽxi}2 ` α}vx̂i ´ ṽxi}}ṽxi} “ ´ α}ṽxi}p}ṽxi} ´ }vx̂i ´ ṽxi}q. (16)
In the next subsection, we guarantee that for any t P r0, 1s, vx̂i with x̂i “ xi´ tαṽxi is close to ṽxi :
}vx̂i ´ ṽxi} ď ˆ 5
6 ` αK7
d2
2d
˙
}ṽxi}, for all vx̂i P Bfpx̂iq. (17)
Applying (17) to (16) yields
fpxi ´ αṽxiq ´ fpxiq ď ´ 1
12 α}ṽxi}22,
where we used that αK7 d 2 2d ď 112 , by our assumption on the stepsize α being sufficiently small.
Thus, the maximum number of iterations for which xi R Sβ is fpx0q12{pαmini }ṽxi} 2q. We next lower-bound }ṽxi}. We have that on Enoise, for all x R Sβ , with β given by (13).
}ṽx}2 ě }hx} ´ }hx ´ ṽx}
ě 2´d maxp}x}, }x˚}q ´ β ´K1d3 ? ´ ω 2 d{2
}x˚}
¯
ě 2´d maxp}x}, }x˚}q ˆ 3Kd3 ? ` 12ω 2 d{2
}x˚}
˙
(18)
ě 2´d}x˚}3Kd3 ?
where the second inequality follows by the definition of Sβ and Lemma 6, and the third inequality follows from our definition of β in (13). Thus,
fpxi ´ αṽxiq ´ fpxiq ď ´αK52´2dd6 }x˚} 2 ď ´2´dd4K6 }x˚}2
where we used α “ K4 2 d d2 . Hence, there can be at most fpx0q2d K6d4 }x˚}2 iterations for which xi R Sβ .
In order to conclude our proof, we remark that once xi is inside a ball of radius r around x˚, the iterates do not leave a ball of radius 2r around x˚. To see this, note that by (12) and our choice of stepsize,
α}ṽxi} ď K
d maxp}xi}, }x˚}q.
This concludes our proof.
The remainder of the proof is devoted to prove the lemmas used in this section.

heading: A.3 PROOF OF EQUATION (17)
text: Our proof relies on hx being Lipschitz, as formalized by the lemma below, which is proven in Section A.9:
Lemma 11. For any x, y R Bp0,K0}x˚}q, where K0 and K4 are numerical constants,
}hx ´ hy} ď K4d
2
2d }x´ y}.
By Lemma 11, for all t P r0, 1s and i ą N (recall that by Lemma 8, after at most N steps, xi ‰ Bp0,K0}x˚}q):
}hx̂i ´ hxi} ď K4d
2
2d }x̂i ´ xi}, (19)
where x̂i “ xi ´ tαṽxi . Thus, we have that on Enoise, for any vx̂i P Bfpx̂iq by Lemma 6,
}vx̂i ´ ṽxi} ď}vx̂i ´ hx̂i} ` }hx̂i ´ hxi} ` }hxi ´ ṽxi}
ďK1 d3 ?
2d maxp}x̂i}, }x˚}q `
ω 2d{2 ` K4d
2
2d }x̂i ´ xi} `K1
d3 ?
2d maxp}xi}, }x˚}q `
ω
2d{2
ďK1 d3 ?
2d maxp}xi} ` α}ṽxi}, }x˚}q `
K4d 2
2d α}ṽxi} `K1
d3 ?
2d maxp}xi}, }x˚}q ` 2
ω
2d{2
ďK1 d3 ?
2d
ˆ
2` αdK 2d
˙
maxp}xi}, }x˚}q ` K4d
2
2d α}ṽxi} ` 2
K9{d2
2d }x˚} (20)
where the second inequality is from Lemma 6 and Equation 19, and the fourth inequality is from (12) and the assumption ω
2´d{2}x˚}2 ď K9{d 2.
Combining (20) and (18), we get that
}vx̂i ´ ṽxi} ď ˆ 5
6 ` αK7
d2
2d
˙
}ṽxi},
with the appropriate constants chosen sufficiently small. This concludes the proof of Equation (17).

heading: A.4 PROOF OF LEMMA 8
text: First suppose that xi P Bp0, 2K0}x˚}q. We show that after a polynomial number of iterations N , we have that xi`N R Bp0, 2K0}x˚}q. Below, we prove that
〈x, ṽx〉 ă 0 and }ṽx} ě 1
2d16π }x˚} for all x P Bp0, 2K0}x˚}q. (21)
It follows that for any xi P Bp0, 2K0}x˚}q, xi and the next iterate produced by the algorithm, xi`1 “ xi ´ αṽxi , form an obtruse triangle. As a consequence,
}xi`1}2 ě }xi}2 ` α2}ṽxi} 2
ě }xi}2 ` α2 1
p2d16πq2 }x˚} 2 ,
where the last inequality follows from (21). Thus, the norm of the iterates xi will increase until after `
2K02 d16π α ˘2 iterations, we have xi`N R Bp0, 2K0}x˚}q.
The proof of the lemma is concluded by showing that
xi R Bp0, 2K0}x˚}q implies xi`1 R Bp0,K0}x˚}q (22)
As a consequence, in a polynomial number N of steps, for each iterate, we have that xi R Bp0,K0}x˚}q, for all i ě N , as claimed.
We next prove the implication (22). Consider xi R Bp0, 2K0}x˚}q, and note that }xi`1} “ }xi ´ αṽxi} ě }xi} ´ α}ṽxi}
ě }xi} ´ α dK
2d maxp}xi}, }x˚}q
ě }xi} ´ α dK 2d }xi} 2K0 ě }xi} ´ 1
2 }xi}
where the second inequality follows from (12), the third inequality from }xi} ě 2K0}x˚}, and finally the last inequality from our assumption on the stepsize α. This concludes the proof of (22).
Proof of (21): It remains to prove (21). We start with proving 〈x, ṽx〉 ă 0. For brevity of notation, let Λz “ ś1 i“dWi,`,z . We have
xT ṽx “ 〈 ΛTxΛxx´ ΛTxΛx˚x˚ ` ΛTx η, x 〉 ď13
12 2´d}x}2 ´ 1 4π 1 2d }x}}x˚} ` }x} ω 2d{2
ď}x} ˆ 13 12 2´d}x} ` 1{p8πq 2d }x˚} ´ 1 4π 1 2d }x˚} ˙
ď}x} 1 2d
ˆ
2}x} ´ 1 8π }x˚}
˙
.
The first inequality follows from (8) and (9), and the second inequality follows from our assumption on ω. Therefore, for any x P Bp0, 116π }x˚}q, 〈x, ṽx〉 ă 0, as desired.
We next show that, for any x P Bp0, 116π }x˚}q
}ṽx} “}ΛTxΛxx´ ΛTxΛx˚x˚ ` ΛTx η} ě }ΛTxΛx˚x˚} ´ }ΛTxΛxx} ´ }ΛTx η}
ě 1 4π 1 2d }x˚} ´ 13 12 1 2d }x} ´ w 2d{2
ě 1 2d
ˆ
1 8π ´ 1 16π
˙
}x˚}.
where the second inequality is from (8) and (9). This concludes the proof of (21).

heading: A.5 PROOF OF LEMMA 5
text: Let Λx “ Π1i“dWi,`,x. We have that
}q̄x}2 “ › ›Λtxη › › 2 ď }Λx}2}PΛxη} 2 ,
where PΛx is a projector onto the span of Λx. As a consequence, }PΛxη} 2 is χ2-distributed random variable with k-degrees of freedom scaled by σ{n. A standard tail bound (see (?, p. 43)) yields that, for any β ě k,
P ”
}PΛxη} 2 ě 4β
ı
ď 2e´β .
Next, we note that by applying Lemmas 13-14 from (Hand & Voroninski, 2018, Proof of Lem. 15))4, with probability one, that the number of different matrices Λx can be bounded as
| tΛx|x ‰ 0u | “ | Π1i“dWi,`,x|x ‰ 0 ( | ď 10d 2 pnd1nd´12 . . . ndqk ď pnd1nd´12 . . . ndq2k, where the second inequality holds for logp10q ď k{4 logpn1q. To see this, note that pnd1nd´12 . . . ndqk ě 10d 2
is implied by kpd logpn1q ` pd ´ 1q logpn2q ` . . . logpndqq ě kd2{4 logpn1q ě d2 logp10q. Thus, by the union bound,
P ”
}PΛxη} 2 ď 16k logpnd1nd´12 . . . ndq, for all x
ı
ě 1´ 2e´2k logpnq,
4The proof in that argument only uses the assumption of independence of subsets of rows of the weight matrices.
where n “ nd. Recall from (9) that }Λx} ď 1312 . Combining this inequality with }q̄x} 2 ď }Λx}2}PΛxη} 2 concludes the proof.

heading: A.6 PROOF OF LEMMA 9
text: We now show that hx is away from zero outside of a neighborhood of x˚ and ´ρdx˚. We prove Lemma 9 by establishing the following: Lemma 12. Suppose 64d6 ? β ď 1. Define
ρd :“ d´1 ÿ
i“0
sin qθi π
˜
d´1 ź
j“i`1
π ´ qθj π
¸
,
where qθ0 “ π and qθi “ gpqθi´1q. If x P Sβ , then we have that either
|θ0| ď 32d4β and |}x}2 ´ }x˚}2| ď 132d6β}x˚}2 or
|θ0 ´ π| ď 8πd4 a β and |}x}2 ´ }x˚}2ρd| ď 200d7 ? }x˚}2.
In particular, we have
Sβ Ă Bpx˚, 5000d6β}x˚}2q Y Bp´ρdx˚, 500d11 a
β}x˚}2q. (23)

heading: Additionally, ρd Ñ 1 as dÑ8.
text: Proof. Without loss of generality, let }x˚} “ 1, x˚ “ e1 and x̂ “ r cos θ0 ¨ e1 ` r sin θ0 ¨ e2 for θ0 P r0, πs. Let x P Sβ . First we introduce some notation for convenience. Let
ξ “ d´1 ź
i“0
π ´ θi π , ζ “ d´1 ÿ
i“0
sin θi π
d´1 ź
j“i`1
π ´ θj π , r “ }x}2, M “ maxpr, 1q.
Thus, hx “ ´ 12d ξx̂0 ` 1 2d pr ´ ζqx̂. By inspecting the components of hx, we have that x P Sβ implies
| ´ ξ ` cos θ0pr ´ ζq| ď βM (24) | sin θ0pr ´ ζq| ď βM (25)
Now, we record several properties. We have:
θi P r0, π{2s for i ě 1 θi ď θi´1 for i ě 1 |ξ| ď 1 (26)
|ζ| ď d π sin θ0 (27)
qθi ď 3π
i` 3 for i ě 0 (28)
qθi ě π
i` 1 for i ě 0 (29)
ξ “ d´1 ź
i“0
π ´ θi π ě π ´ θ0 π d´3 (30)
θ0 “ π `O1pδq ñ θi “ qθi `O1piδq (31)
θ0 “ π `O1pδq ñ |ξ| ď δ
π (32)
θ0 “ π `O1pδq ñ ζ “ ρd `O1p3d3δq if d2δ
π ď 1 (33)
We now establish (28). Observe 0 ă gpθq ď ` 1 3π ` 1 θ ˘´1 “: g̃pθq for θ P p0, πs. As g and g̃ are monotonic increasing, we have qθi “ g˝ipqθ0q “ g˝ipπq ď g̃˝ipπq “ ` i 3π ` 1 π
˘´1 “ 3πi`3 . Similarly, gpθq ě p 1π ` 1 θ q ´1 implies that qθi ě πi`1 , establishing (29).
We now establish (30). Using (28) and θi ď qθi, we have d´1 ź
i“1
´ 1´ θi π ¯
ě d´1 ź
i“1
´ 1´ 3 i` 3 ¯ ě d´3,
where the last inequality can be established by showing that the ratio of consecutive terms with respect to d is greater for the product in the middle expression than for d´3.
We establish (31) by using the fact that |g1pθq| ď 1 for all θ P r0, πs and using the same logic as for (Hand & Voroninski, 2018, Eq. 17).
We now establish (33). As θ0 “ π `O1pδq, we have θi “ qθi `O1piδq. Thus, if d 2δ π ď 1,
d´1 ź
j“i`1
π ´ θj π “ d´1 ź
j“i`1
´π ´ qθj π `O1p iδ 2π q ¯ “ ´
d´1 ź
j“i`1
π ´ qθj π ¯ `O1pd2δq
So
ζ “ d´1 ÿ
i“0
´ sin qθi π `O1p iδ π q ¯”´
d´1 ź
j“i`1
π ´ qθj π ¯ `O1pd2δq ı
(34)
“ ρd `O1 ´ d2δ{π ` d3δ{π ` d4δ2{π ¯
(35)
“ ρd `O1p3d3δq. (36)
Thus (33) holds.
Next, we establish that x P Sβ ñ r ď 4d, and thus M ď 4d. Suppose r ą 1. At least one of the following holds: | sin θ0| ě 1{ ? 2 or | cos θ0| ě 1{ ? 2. If | sin θ0| ě 1{ ? 2 then (25) implies that |r ´ ζ| ď ?
2βr. Using (27), we get r ď d{π 1´ ? 2β ď d{2 if β ă 1{4. If | cos θ0| ě 1{
? 2, then
(24) implies that |r ´ ζ| ď ? 2pβr ` |ξ|q. Using (26), (27), and β ă 1{4, we get r ď ?
2|ξ|`ζ 1´ ? 2β ď
d` ?
2 1´ ? 2β ď 4d. Thus, we have x P Sβ ñ r ď 4dñM ď 4d.
Next, we establish that we only need to consider the small angle case (θ0 « 0) and the large angle case (θ0 « π), by considering the following three cases:
(Case I) sin θ0 ď 16d4β: We have θ0 “ O1p32d4βq or θ0 “ π`O1p32d4βq, as 32d4β ă 1. (Case II) |r ´ ζ| ă ? βM : Applying case II to inequality (24) yields |ξ| ď 2 ? βM . Using (30), we get θ0 “ π `O1p2πd3 ? βMq. (Case III) sin θ0 ą 16d4β and |r ´ ζ| ě ? βM : Finally, consider Case III. By (25), we have |r ´ ζ| ď βM sin θ0 . Using this inequality in (24), we have |ξ| ď βM ` βM sin θ0 ď 2βM sin θ0
ď 1 8d ´4M ď 12d
´3, where the second to last inequality uses sin θ0 ą 16d4β and the last inequality uses M ď 4d. By (30), we have π´θ0π d ´3 ď ξ ď 12d ´3, which implies that
θ0 ě π{2. Now, as |r ´ ζ| ě ? βM , then by (25), we have | sin θ0| ď ? β. Hence, θ0 “ π `O1p2 ? βq, as θ0 ě π{2 and as β ă 1.
At least one of the Cases I,II, or III hold. Thus, we see that it suffices to consider the small angle case θ0 “ O1p32d4βq or the large angle case θ0 “ π `O1p8πd4 ? βq.
Small Angle Case. Assume θ0 “ O1pδq with δ “ 32d4β. As θi ď θ0 ď δ for all i, we have 1 ě ξ ě p1´ δπ q d “ 1`O1p 2δdπ q provided δd{π ď 1{2 (which holds by our choice δ “ 32d 4β by
assumption 64d6 ? β ď 1). By (27), we also have ζ “ O1p dπ δq. By (24), we have
| ´ ξ ` cos θ0pr ´ ζq| ď βM.
Thus, as cos θ0 “ 1`O1pθ 2 0{2q “ 1`O1pδ2{2q,
´ ´ 1`O1p 2δd π q ¯ ` p1`O1p 2δd π qqpr `O1p δd π qq “ O1p4dβq,
and r ďM ď 4d (shown above) provides,
r ´ 1 “ O1p4dβ ` 2δd π ` δd π ` 2δd π 4d` 2δ
2d2
π2 q (37)
“ O1p4βd` 4δd2q. (38)
By plugging in that δ “ 32d4β, we have that r ´ 1 “ O1p132d6βq, where we have used that 32d5β π ď 1{2. Large Angle Case. Assume θ0 “ π ` O1pδq where δ “ 8πd4 ? β. By (32) and (33), we have
ξ “ O1pδ{πq, and we have ζ “ ρd `O1p3d3δq if 8d6 ? β ď 1. By (24), we have
| ´ ξ ` cos θ0pr ´ ζq| ď βM,
so, as cos θ0 “ 1´O1pθ20{2q,
O1pδ{πq ` p1`O1pδ2{2qqpr ´ ρd `O1p3d3δqq “ O1pβMq,
and thus, using r ď 4d, ρd ď d, and δ “ 8πd4 ? β ď 1,
r ´ ρd “ O1pβM ` δ{π ` 3d3δ ` 5 2 δ2d` 3 2 d3δ3q (39)
“ O1 ´ 4βd` δp 1 π ` 3d3 ` 5 2 d` 3 2 d3q ¯
(40)
“ O1p200d7 a βq (41)
To conclude the proof of (23), we use the fact that
}x´ x˚}2 ď ˇ ˇ}x}2 ´ }x˚}2 ˇ ˇ` p}x˚}2 ` ˇ ˇ}x}2 ´ }x˚}2 ˇ ˇqθ0.
This fact simply says that if a 2d point is known to have magnitude within ∆r of some r and is known to be within angle ∆θ from 0, then its Euclidean distance to the point of polar coordinates pr, 0q is no more than ∆r ` pr `∆rq∆θ.
Finally, we establish that ρd Ñ 1 as d Ñ 8. Note that ρd`1 “ p1 ´ qθd π qρd ` sin qθd π and ρ0 “ 0. It suffices to show ρ̃d Ñ 0, where ρ̃d :“ 1 ´ ρd. The following recurrence relation holds: ρ̃d “ p1 ´ qθd´1π qρ̃d´1 ` qθd´1´sin qθd´1 π , with ρ̃0 “ 1. Using the recurrence formula (Hand & Voroninski, 2018, Eq. (15)) and the fact that qθ0 “ π, we get that
ρ̃d “ d ÿ
i“1
qθi´1 ´ sin qθi´1 π
d ź
j“i`1
` 1´ qθj´1 π ˘
(42)
using (29), we have that
d ź
j“i`1
´ 1´ qθj´1 π ¯
ď d ź
j“i`1
´ 1´ 1 j ¯ “ exp ´
´ d ÿ
j“i`1
1
j
¯ ď exp ´ ´ ż d`1
i`1
1 s ds ¯ “ i` 1 d` 1
Using (28) and the fact that qθi´1 ´ sin qθi´1 ď qθ3i´1{6, we have that ρ̃d ď řd i“1 qθ3i´1 6π ¨ i`1 d`1 Ñ 0 as dÑ8.

heading: A.7 PROOF OF LEMMA 10
text: Consider the function fηpxq “ f0pxq ´ xGpxq ´Gpx˚q, ηy, and note that fpxq “ fηpxq ` }η}2. Consider x P Bpφdx˚, ϕ}x˚}q, for a ϕ that will be specified later. Note that
|〈Gpxq ´Gpx˚q, η〉| ď | 〈 Π1i“dWi,`,xx, η 〉 | ` | 〈 Π1i“dWi,`,x˚x˚, η 〉 |
“ | 〈 x, pΠ1i“dWi,`,xqtη 〉 | ` | 〈 x˚, pΠ1i“dWi,`,x˚qtη 〉 | ď p}x} ` }x˚}q ω
2d{2
ď pϕ}x˚} ` }x˚}q ω
2d{2 ,
where the second inequality holds on the event Enoise, by Lemma 5, and the last inequality holds by our assumption on x. Thus, for x P Bpφdx˚, ϕ}x˚}q fηpxq ďEf0pxq ` |f0pxq ´ Ef0pxq| ` |〈Gpxq ´Gpx˚q, η〉|
ď 1 2d`1
ˆ
φ2d ´ 2φd ` 10
K32 dϕ
˙
}x˚}2 ` 1
2d`1 }x˚}2
` p1` 4 dq 2d
}x}2 ` p1` 4 dq ` 48d 3 ?
2d`1 }x}}x˚} ` p1` 4 dq 2d }x˚}2
` pϕ}x˚} ` }x˚}q ω
2d{2
ď 1 2d`1
ˆ
φ2d ´ 2φd ` 10
K32 dϕ
˙
}x˚}2 ` 1
2d`1 }x˚}2
` p1` 4 dq 2d pφd ` ϕq2}x˚}2 ` p1` 4 dq ` 48d3
?
2d`1 pφd ` ϕq}x˚}2 ` p1` 4 dq 2d }x˚}2
` pϕ}x˚} ` }x˚}q ω
2d{2
ď }x˚}2
2d`1
ˆ
1` φ2d ´ 2φd ` 10
K32 d ` 68d2
? ˙
` pϕ}x˚} ` }x˚}q ω
2d{2 (43)
where the last inequality follows from ă ? , ρd ď 1, 4 d ă 1, ϕ ă 1 and assuming ϕ “ .
Similarly, we have that for any y P Bp´φdx˚, ϕ}x˚}q fηpyq ěErfpyqs ´ |fpyq ´ Erfpyqs| ´ |〈Gpxq ´Gpx˚q, η〉|
ě 1 2d`1 ` φ2d ´ 2φdρd ´ 10d3ϕ ˘ }x˚}2 ` 1 2d`1 }x˚}2
´ ˆ p1` 4 dq 2d
}y}2 ` p1` 4 dq ` 48d 3 ?
2d`1 }y}}x˚} ` p1` 4 dq 2d }x˚}2 ˙
´ pϕ}x˚} ` }x˚}q ω
2d{2
ě}x˚} 2
2d`1 `
1` φ2d ´ 2φdρd ´ 10d3ϕ´ 68d2 ? ˘ ´ pϕ}x˚} ` }x˚}q ω
2d{2 (44)
Using ă ? , ρd ď 1, 4 d ă 1, ϕ ă 1 and assuming ϕ “ , the right side of (43) is smaller than the right side of (44) if
ϕ “ ď
¨
˝ φd ´ ρdφd ´ 13}η}2 ´
125` 5 K32
¯
d3
˛
‚
2
. (45)
We can establish that: Lemma 13. For all d ě 2, that
1{ ` K1pd` 2q2 ˘ ď 1´ ρd ď 250{pd` 1q.
Thus, it suffices to have ϕ “ “ K3d10 and 13}η}2 ď K9 d2 ď 1 2 K2 K1pd`2q2 for an appropriate universal constant K9, and for an appropriate universal constant K3.

heading: A.8 PROOF OF LEMMA 13
text: It holds that }x´ y} ě 2 sinpθx,y{2qminp}x}, }y}q, @x, y (46) sinpθ{2q ě θ{4, @θ P r0, πs (47) d
dθ gpθq P r0, 1s @θ P r0, πs (48) logp1` xq ď x @x P r´0.5, 1s (49) logp1´ xq ě ´2x @x P r0, 0.75s (50)
where θx,y “ =px, yq. We recall the results (36), (37), and (50) in (Hand & Voroninski, 2018):
θ̌i ď 3π i` 3 and θ̌i ě π i` 1 @i ě 0
1´ ρd “ d´1 ź
i“1
ˆ
1´ θ̌i π
˙ ` d´1 ÿ
i“1
θ̌i ´ sin θ̌i π
d´1 ź
j“i`1
ˆ
1´ θ̌j π
˙
.
Therefore, we have for all 0 ď i ď d´ 2, d´1 ź
j“i`1
ˆ
1´ θ̌j π
˙ ď d´1 ź
j“i`1
ˆ
1´ 1 j ` 1
˙
“ e řd´1 j“i`1 logp1´ 1j`1 q ď e´ řd´1 j“i`1 1 j`1 ď e´ şd i`1 1 s`1ds “ i` 2
d` 1 ,
d´1 ź
j“i`1
ˆ
1´ θ̌j π
˙ ě d´1 ź
j“i`1
ˆ
1´ 3 j ` 3
˙
“ e řd´1 j“i`1 logp1´ 3j`3 q ě e´ řd´1 j“i`1 6 j`3 ě e´ şd´1 i 6 s`3ds “
ˆ
i` 3 d` 2
˙6
,
where the second and the fifth inequalities follow from (49) and (50) respectively. Since π3{p12pi` 1q3q ď θ̌3i {12 ď θ̌i ´ sin θ̌i ď θ̌3i {6 ď 27π3{p6pi` 3q3q, we have that for all d ě 3
1´ ρd ď 2 d` 1 ` d´1 ÿ
i“1
27π3 6pi` 3q3 i` 2 d` 1 ď 2 d` 1 ` 3π5 4pd` 1q ď 250
d` 1 and
1´ ρd ě ˆ 3
pd` 2q
˙6 ` d´1 ÿ
i“1
π3
12pi` 3q3
ˆ
i` 3 d` 2
˙6
ě 1 K1pd` 2q2 ,
where we use ř8 i“4 1 i2 ď π2 6 and řn i“1 i 3 “ Opn4q.

heading: A.9 PROOF OF LEMMA 11
text: To establish Lemma 11, we prove the following: Lemma 14. For all x, y ‰ 0,
}hx ´ hy} ď ˆ 1 2d ` 6d` 4d 2 π2d max ˆ 1 }x} , 1 }y} ˙ }x˚} ˙ }x´ y}
Lemma 11 follows by noting that if x, y R Bp0, r}x˚}q, then }hx ´ hy} ď ´ 1 2d ` 6d`4d 2 πr2d ¯ }x´ y}.
Proof of Lemma 14. For brevity of notation, let ζj,z “ śd´1 i“j π´θ̄i,z π . Combining (46) and (47) gives |θ̄0,x ´ θ̄0,y| ď 4 max ´ 1 }x} , 1 }y} ¯
}x´ y}. Inequality (48) implies |θ̄i,x ´ θ̄i,y| ď |θ̄j,x ´ θ̄j,y| for all i ě j. It follows that
}hx ´ hy} ď 1 2d }x´ y} ` 1 2d |ζ0,x ´ ζ0,y| l jh n
T1
}x˚}
` 1 2d
ˇ
ˇ
ˇ
ˇ
ˇ
d´1 ÿ
i“0
sin θ̄i,x π
ζi`1,xx̂´ d´1 ÿ
i“0
sin θ̄i,y π ζi`1,y ŷ
ˇ
ˇ
ˇ
ˇ
ˇ
l jh n
T2
}x˚}. (51)
By Lemma 15, we have
T1 ď d
π |θ̄0,x ´ θ̄0,y| ď
4d
π max
ˆ
1 }x} , 1 }y}
˙
}x´ y}. (52)
Additionally, it holds that
T2 “
ˇ
ˇ
ˇ
ˇ
ˇ
d´1 ÿ
i“0
sin θ̄i,x π ζi`1,xx̂´ sin θ̄i,x π ζi`1,xŷ ` sin θ̄i,x π
ζi`1,xŷ ´ d´1 ÿ
i“0
sin θ̄i,y π ζi`1,y ŷ
ˇ
ˇ
ˇ
ˇ
ˇ
ď d π }x̂´ ŷ} `
ˇ
ˇ
ˇ
ˇ
ˇ
d´1 ÿ
i“0
sin θ̄i,x π
ζi`1,x ´ d´1 ÿ
i“0
sin θ̄i,y π ζi`1,y
ˇ
ˇ
ˇ
ˇ
ˇ
l jh n
T3
. (53)
We have
T3 ď d´1 ÿ
i“0
„ ˇ
ˇ
ˇ
ˇ sin θ̄i,x π ζi`1,x ´ sin θ̄i,x π ζi`1,y
ˇ
ˇ
ˇ
ˇ
` ˇ ˇ ˇ
ˇ sin θ̄i,x π ζi`1,y ´ sin θ̄i,y π ζi`1,y
ˇ
ˇ
ˇ
ˇ

ď d´1 ÿ
i“0
„
1
π
ˆ
d´ i´ 1 π ˇ ˇθ̄i´1,x ´ θ̄i´1,y ˇ ˇ
˙
` 1 π | sin θ̄i,x ´ sin θ̄i,y|

ďd 2
π |θ̄0,x ´ θ̄0,y| ď
4d2
π max
ˆ
1 }x} , 1 }y}
˙
}x´ y}. (54)
Using (46) and (47) and noting }x̂´ ŷ} ď θx,y yield
}x̂´ ŷ} ď θx,y ď 2 max ˆ 1 }x} , 1 }y} ˙ }x´ y}. (55)
Finally, combining (51), (52), (53), (54) and (55) yields the result.
Lemma 15. Suppose ai, bi P r0, πs for i “ 1, . . . , k, and |ai´bi| ď |aj´bj |,@i ě j. Then it holds that
ˇ
ˇ
ˇ
ˇ
ˇ
k ź
i“1
π ´ ai π ´ k ź
i“1
π ´ bi π
ˇ
ˇ
ˇ
ˇ
ˇ ď k π |a1 ´ b1|.
Proof. Prove by induction. It is easy to verify that the inequality holds if k “ 1. Suppose the inequality holds with k “ t´ 1. Then
ˇ
ˇ
ˇ
ˇ
ˇ
t ź
i“1
π ´ ai π ´ t ź
i“1
π ´ bi π
ˇ
ˇ
ˇ
ˇ
ˇ
ď
ˇ
ˇ
ˇ
ˇ
ˇ
t ź
i“1
π ´ ai π ´ π ´ at π
t´1 ź
i“1
π ´ bi π
ˇ
ˇ
ˇ
ˇ
ˇ
`
ˇ
ˇ
ˇ
ˇ
ˇ π ´ at π
t´1 ź
i“1
π ´ bi π ´ t ź
i“1
π ´ bi π
ˇ
ˇ
ˇ
ˇ
ˇ
ď t´ 1 π |a1 ´ b1| ` 1 π |at ´ bt| ď t π |a1 ´ b1|.

Review summaries:
The paper analyzes the recovery accuracy of a "tweaked" gradient descent algorithm for imaging denoising and compressive sensing under deep generative priors. In particular, when assuming Gaussian randomness of the network weights and extremely stringent conditions of network sizes, they demonstrate a specific denoising rate of O(k/n), with k and n being the input and output dimension of the generative network. This is seemingly optimal in terms of the dependence on the latent code dimensionality and the signal dimensionality and is the first result of this kind. 

The paper studies the standard denoising problem under the assumption that the unknown n-dimensional signal can be written as the output of a known d-layer neural network G mapping k dimensions to n dimensions. The paper specifies an algorithm to perform this denoising and the algorithm is based on a variant of the usual gradient method. Then, under additional assumptions on the neural network G, the paper proves that their algorithm produces a denoised signal that achieves a mean squared accuracy of k/n. Because the input signal has "effective" dimensionality k (as it can be written as G(x) for some k-dimensional x), it is nice that it can be recovered at the accuracy k/n by Gradient Descent despite the complicated nature of G. In this respect, the result is quite interesting. However, the underlying assumptions are too strong in my opinion as described below: