A Provably Convergent Scheme for Compressive Sensing under Random Generative Priors

Introduction

Generative models have greatly improved the state of the art in computer vision and image processing, including inpainting, super resolution, compression, compressed sensing, image manipulation, MRI imaging, and denoising [GPAM+14, OKK16, MSY16, YCL+17, SCT+16, LTH+16, JAFF16, MPB15, MB17, ZKSE16, RB17, MGC+17, MMP+17, MPB15, MB17]. At the heart of this success is the ability of generative models to sample from a good approximation of the manifold of natural signals or images relevant for a particular task. These models can be efficiently learned, in an unsupervised way, from a collection of examples of images of that signal class. The progress in generative modeling over just the past two years has been immense; as an example, multiple methods can now generate synthetic photorealistic images of celebrity faces [KALL17, KD18]. Generative models have also been trained in other contexts, and the quality of such models is expected to keep improving.

A reason for the success of some generative models in inverse problems is that they can efficiently map a low-dimensional space, called a latent code space, to an estimate of the natural signal manifold in high-dimensional signal space. That is, generative models can provide an explicit parameterization of an approximation of the natural signal manifold. This property then allows signal recovery problems to be posed in a low dimensional space. In contrast, a standard structural model for natural signals over the past decade or so has been sparsity in an appropriate basis, such as a wavelet basis. This perspective leads to a high dimensional optimization problem that cannot directly be solved and instead relies on a convex relaxation. While this relaxation has been quite successful in linear regimes, such as compressive sensing, it has not yet been effective in nonlinear regimes, such as compressive phase retrieval.

In comparison to sparsity-based methods, generative methods can permit lower dimensional representations of some signal classes. To see how lower dimensional representations are possible, consider the following toy model. Consider a 1-parameter family of high resolution natural images of a toy train rolling down wooden tracks. The representation of each image in terms of a wavelet bases will be approximately sparse, relative to the image dimensionality, but accurate reconstruction will still require many wavelet coefficients. In contrast, if that collection of images was directly modeled as a one-dimensional manifold, recovery should be possible with approximately 1 measurement.

In comparison to sparsity based methods, generative methods can be exploited more efficiently in some contexts. For example, in compressive phase retrieval [HLV18] show that the empirical risk objective under suitable assumptions has a favorable optimization landscape, in that there are no spurious local minima, when the number of generic measurements is linear in the latent dimensionality of a random generative model. In contrast, no algorithm for compressive phase retrieval is known to succeed under less than $O(s^{2})$ generic measurements, where $s$ is the signal sparsity.

In the context of compressive sensing from linear measurements and under generative priors, recovery can be posed as a nonconvex empirical risk optimization, which can be solved by first order gradient methods. When solved this way, generative models have been shown to empirically outperform sparsity models in the sense that they can give comparable reconstruction error with 5-10x fewer compressive measurements in some contexts. This empirical result indicates both that representations from generative models are low dimensional and can be efficiently exploited. Nonetheless, this observation does not have a firm theoretical footing. In principle, such gradient algorithms for nonconvex programs could get stuck in local minima. Thus, it is important to provide algorithms that provably recover the underlying signal.

In this paper, we introduce a gradient descent algorithm for empirical risk minimization under a generative network, given noisy compressive measurements of its output. We prove that if the network is random, the size of each layer grows appropriately, there are a sufficient number of compressive measurements, and the magnitude of the noise is sufficiently small, then the gradient descent algorithm converges to a neighborhood of the global optimizer and the size of the neighborhood only depends on the magnitude of the noise. In particular, the gradient descent algorithm converges to the global minimizer for noiseless measurements. To the best of our knowledge, this is the first recovery guarantee for compressive sensing under a generative neural network model. Using numerical experiments, we empirically verify recovery up to the noise level, and in particular exact recovery in the noiseless case.

The justification for studying random networks is as follows. First, the weights of some neural networks trained on real data exhibit statistics consistent with Gaussians. Second, the theory for inverse problems under generative priors is nascent and challenging even for Gaussian networks. Third, it is not immediately clear what model for the weights of trained generative models is most realistic while maintaining mathematical tractability. And finally, random neural networks have recently been shown to be useful for image processing tasks [UVL18, HH18]; thus, any theoretical analysis of them may be relevant for those contexts.

A first theoretical analysis of compressive sensing under a generative prior appeared in [BJPD17]. In that work, the authors studied the task of recovering a signal near the range of a generative network by the same nonconvex empirical risk objective as in the present paper. They establish that if the number of measurements scales linearly in the latent dimensionality, then if one can solve to global optimality the nonconvex empirical risk objective, then one recovers the signal to within the noise level and representational error of the network. Because the objective is nonconvex, and nonconvex problems are NP-hard in general, it is not clear that any particular computationally efficient optimization algorithm can actually find the global optimum. That is, it is possible that any particular numerically efficient optimization algorithm gets stuck in local minima. In the present paper, we provide a specific computationally efficient numerical algorithm and establish a recovery guarantee for compressive sensing under generative models that satisfy suitable architectural assumptions.

A recent paper by a subset of the authors [HV17] provides a global analysis of the nonconvex empirical risk objective below for expansive Gaussian networks. The paper shows that, under appropriate conditions, there are descent directions, of the nonconvex objective, outside neighborhoods of the global optimizer and a negative multiple thereof in the latent code space. That work, however, does not provide an analysis of the behavior of the empirical risk objective within these two neighborhoods, a specific algorithm, a proof of convergence of an algorithm, or a principled reason why the negative multiple of the global optimizer would not be returned by a naively applied gradient scheme. Additionally, that work does not study noise tolerance. Each of these aspects require considerable technical advances, for example establishing a nontrivial convexity-like property near the global minimizer.

The paper [ALM15] presents a simple layer-wise inversion process for neural networks. In the current setting, this result is not applicable because the final compressive layer can not be directly inverted without structural assumptions. Instead, in the present paper, we analyze the inversion of the compressive measurements and the generative network together.

Problem statement

For notational convenience, we let $W_{+,x}$ denote the matrix obtained by zeroing out the rows of $W$ that do not have a positive dot product with $x$, i.e.,

The matrix $W_{i,+,x}$ contains the rows of $W_{i}$ that are active after taking a ReLU if the input to the network is $x$. Therefore, under the model for $G$, the empirical risk (2.1) becomes

Main Results: Two algorithms and a convergence analysis

In this section, we propose two closely related algorithms for minimizing the empirical loss (2.1). The first algorithm is a subgradient descent method which is provably convergent. The second algorithm is a practical implementation that can be directly implemented with an explicit form of the gradient step that may or may not be within the subdifferential of the objective at some points.

Any vector in $\partial f(x)$ is called a subgradient of $f$ at $x$. Note that if $f$ is differentiable at $x$, then $\partial f(x)=\{\nabla f(x)\}$. We can now state Algorithm 1.

This subgradient method has an important twist. In lines 3–7, the algorithm checks whether negating the current iterate of the latent code causes a lower objective, and if so accepts that negation. The motivation for this step is as follows: In expectation, the empirical loss $f$ has a global minimum at $x_{*}$, a local maximum at 0, and a critical point at $-x_{*}\rho_{d}$, where $\rho_{d}\in(0,1)$, as established in [HV17]. Moreover, the empirical loss $f$ concentrates around its expectation. Thus, a simple gradient descent algorithm could in principle be attracted to $-x_{*}\rho_{d}$, and this check is used in order to ensure that it does not.

2 Convergence analysis for Algorithm 1

In this section, we prove that Algorithm 1 converges to the global minimizer $x_{*}$ up to an error determined by the noise $e$. Consequently, the signal estimate $G(x_{*})$ is also recovered up an error determined by the noise. In the noiseless case (i.e., $e=0$), Algorithm 1 converges to $x^{*}$, and $G(x^{*})$ is recovered exactly. Our theorem relies on two deterministic assumptions about the network $G$ and the sensing matrix $A$.

First, we assume that the weights of the network, $W_{i}$, satisfy the Weight Distribution Condition (WDC) defined below. This condition states that the weights are roughly uniformly distributed over a sphere of an appropriate radius.

Second, we assume that the measurement matrix $A$ satisfies an isometry condition with respect to $G$, defined below.

These deterministic conditions are satisfied with some probability by neural networks and measurement matrices that are such that

The network weights have i.i.d. $\mathcal{N}(0,1/n_{i})$ entries in the $i$th layer.

The network is expansive in each layer, in that

where $c$ is a universal constant and $\epsilon$ is sufficiently small.

The measurement vectors have i.i.d. $\mathcal{N}(0,1/m)$ entries.

There are a sufficient number of measurements in that

where $c$ is a universal constant and $\epsilon$ is sufficiently small.

The probability that the WDC and RRIC hold with constant $\epsilon$ under the assumption above is at least

As our main theoretical result, we prove that the iterates generated by Algorithm 1 converge to $x_{*}$ up to a term dependent on the noise level. The proof is given in Section 5.

Suppose the WDC and RRIC hold with $\epsilon\leq K_{1}/d^{90}$ and the noise $e$ obeys $\|e\|\leq\frac{K_{2}\|x_{*}\|}{d^{42}2^{d/2}}$. Consider the iterates $\{x_{i}\}$ generated by Algorithm 1 with step size $\nu=K_{3}\frac{2^{d}}{d^{2}}$. Then there exists a number of iterations, denoted by $N$ and upper bounded by $N\leq\frac{K_{4}f(x_{0})2^{d}}{d^{4}\epsilon\|x_{*}\|}$ such that

where $C=1-\frac{\nu}{2^{d}}\frac{7}{8}\in(0,1)$. Here, $K_{1},K_{2},K_{3}$, $K_{4}$, $K_{5}$, $K_{6}$, and $K_{7}$ are universal positive constants.

Theorem 3.1 shows that after a certain number of iterations $N$, an iterate of Algorithm 1 is in a neighborhood of the true latent code $x_{*}$, and the size of this neighborhood depends on the sample complexity parameter $\epsilon$ and the noise $e$ (see (3.4)). Furthermore, by (3.5), the theorem guarantees that once the iterates are in this ball, they converge linearly to a smaller neighborhood of $x_{*}$, and the size of the neighborhood only depends on the noise term $e$. If the noise term is zero, the algorithm converges linearly to $x_{*}$. Similarly, it follows from (3.6) that the recovered image $G(x_{i})$ converges to $G(x_{*})$ up to the noise.

Combining Proposition 4 from the paper [HV17, Proposition 4], with Theorem 3.1 yields the following corollary.

Consider an expansive generative neural network $G$ that satisfies (a) and (b), and let the measurements satisfy (c) and (d). Suppose $\epsilon<K_{1}/d^{90}$ and $\|e\|\leq\frac{K_{2}\|x_{*}\|}{d^{42}2^{d/2}}$. Then, at least with probability (3.3), the iterates $\{x_{i}\}$ generated by Algorithm 1 with step size $\nu=K_{3}\frac{2^{d}}{d^{2}}$ satisfies the following: There exists a number of step $N$ upper bounded by $N\leq\frac{K_{4}f(x_{0})2^{d}}{d^{4}\epsilon\|x_{*}\|}$ such that

3 Practical Algorithm

Experiments

In this section, we tested the performance of Algorithm 2 on synthetic data with various sizes of noise, and verified Theorem 2 by numerical results.Note that we do not observe that any entry in $W_{i}W_{i-1,+,x}\cdots W_{2,+,x}W_{1,+,x}x,\forall i$, is zero in our experiments. Therefore, Algorithm 2 is equivalent to Algorithm 1 in this case.

Figure 1 reports the empirical probability of successful recovery for noiseless problems. A run is called success if the relative error $\|x-x_{*}\|/\|x_{*}\|$ is smaller than $10^{-3}$. We observe that Algorithm 1 is able to find the true code $x_{*}$ when $m$ is sufficiently large relative to $k$. This experiment shows that signal recovery by empirical risk optimization for compressive sensing under expansive Gaussian generative priors succeeds in a much larger parameter range than that given by the theorem. In particular, the empirical dependence on $d$ appears to be much milder in practice than what was assumed in the theorem.

Figure 3 shows the relationships between the relative error $\|x_{i}-x_{*}\|/\|x_{*}\|$ and the number of iterations for the four values of SNR. The number of input neurons $k$ is $10$. Note that in the tests for the different values of SNR, all the other settings are identical, i.e., the initial iterate, latent code $x_{*}$, weights matrices $A$ and $W_{i}$ are the same. We observe that after approximately 20 iterations, Algorithm 1 converges linearly to a neighborhood of the true solution $x_{*}$, and the size of the neighborhood only depends on the magnitude of the noise. These results are consistent with Theorem 1. Additionally, this figure demonstrates that the relative error in the recovered latent code scales linearly with the magnitude of the noise, which is also consistent with the theorem.

Proof of Theorem 3.1

In this section, we prove our main result. Recall that the goal of Algorithm 1 is to minimize the cost function

The proof relies on a concentration of measure argument which ensures that the cost function $f(x)$ and the step direction ${v}_{x}$ concentrate around ${f^{E}}(x)$ and $h_{x}$, respectively. In particular, if the WDC and the RRIC hold with $\epsilon=0$ and the noise $e$ is 0, then $f(x)={f^{E}}(x)$ and ${v}_{x}=h_{x}$. The idea of our convergence analysis is to prove properties of ${f^{E}}(x)$ and the direction $h_{x}$ that are sufficient for a convergence analysis, if our method where to be run on ${f^{E}}(x)$ with step directions given by $h_{x}$, and then show that the actual cost function $f(x)$ and step direction are ‘close enough’ to establish convergence.

It is well known that if the gradient of a function is Lipschitz continuous, then a steepest descent method with a sufficient small step size converges to a stationary point from any starting point [NW06]. However, this result can not be used here since the gradient of the function (2.2) is not continuous. We overcome this technical difficulty by the following three steps, rigorously stated in Lemma 5.1, Lemma 5.2, and Lemma 5.3, respectively.

The function $h_{x}$ is Lipschitz continuous except in a ball around 0.

The (sub)-gradient of $f(x)$ is close to $h_{x}$.

The iterates generated by Algorithm 1 stay sufficiently far away from 0.

Those three steps are sufficient to show that the gradient of $f(x)$ is close to being Lipschitz continuous, and therefore the iterates from Algorithm 1 converge to a neighborhood of a stationary point. The size of the neighborhood depends on how close the (sub)-gradient of $f(x)$ is to $h_{x}$, and is controlled by the noise energy $\|e\|$ and the variable $\epsilon$ in the WDC and the RRIC. Of course, we also have to ensure that the algorithm not only converges to any of the three stationary points, but that it actually converges to a point close to $x_{*}$, for this we rely on the ‘tweak’ of the algorithm in steps 1-3.

The remainder of the proof is organized as follows. We start by defining notation used throughout the proof (see Section 5.1). In Section 5.2 we introduced several technical results formalizing the steps 1-3 above, and in Section 5.3 we use those properties to formally prove Theorem 3.1.

Here, we define some useful quantities, in particular ${f^{E}}(x)$ and $h_{x}$, and introduce standard notation used throughout. We start with defining a function that is helpful for controlling how the operator $x\to W_{+,x}x$ distorts angles, and is defined as

where $\check{\theta}_{0}=\pi$, and $\check{\theta}_{i}=g(\check{\theta}_{i-1})$.

2 Preliminaries

In this section, we state formal results making steps 1-3 from the beginning of this section rigorous, and collect properties used later in the proof of Theorem 3.1.

We start by showing that the function $h_{x}$ is Lipschitz continuous except in a ball around :

In addition, if $x,y\notin\mathcal{B}(0,r\|x_{*}\|)$ for any $r>0$, then $\|h_{x}-h_{y}\|\leq\left(\frac{1}{2^{d}}+\frac{6d+4d^{2}}{\pi r2^{d}}\right)\|x-y\|$.

The next lemma states that $h_{x}$ and the sub-gradient $v_{x}$ are close:

Suppose the WDC and RRIC hold with $\epsilon\leq 1/(16\pi d^{2})^{2}$. Then for any $x\neq 0$ and any $v_{x}\in{\partial f(x)}$,

Next, we ensure that after sufficiently many steps, the algorithm will be relatively far from the maximum around :

Recall that $S_{\beta}$ is the set of points with the norm of $h_{x}$ upper bounded by $\beta\max(\|x\|,\|x_{*}\|)$. The following lemma shows that this set is contained in balls around $x_{*}$ and $\rho_{d}x_{*}$, thus outside those balls, the norm of $h_{x}$ is lower bounded, which, together with Lemma 5.2, establishes that the sub-gradients are bounded away from zero. This in turn is important to show that outside those balls our gradient scheme makes progress.

[HHHV18, Lemma 8] For any $\beta\leq\frac{1}{64^{2}d^{12}}$,

Here, $\rho_{d}>0$ obeys $\rho_{d}\to 1$ as $d\to\infty$.

It has been shown in [HV17] that the function ${f^{E}}(x)$ has three stationary points: one at $-\rho_{d}x_{*}$, one global minimizer at $x_{*}$ and a local maximizer at . Therefore, Algorithm 1 could in principle be attracted to $-\rho_{d}x_{*}$. Lemma 5.5 guarantees that with the tweak from Step 3 to Step 7, the iterates of Algorithm 1 converges to a neighborhood of $x_{*}$.

Suppose the WDC and RRIC hold with $\epsilon<1/(16\pi d^{2})^{2}$. Moreover, suppose the noise $e$ satisfies $\|e\|\leq\frac{a_{3}\|x_{*}\|}{d^{2}2^{d/2}}$, where $a_{3}$ is a universal constant. Then for any $\phi_{d}\in[\rho_{d},1]$, it holds that

for all $x\in\mathcal{B}(\phi_{d}x_{*},a_{4}d^{-10}\|x_{*}\|)$ and $y\in\mathcal{B}(-\phi_{d}x_{*},a_{4}d^{-10}\|x_{*}\|)$, where $a_{4}<1$ is a universal constant.

Once an iterate is in a small neighborhood of $x_{*}$, Lemma 5.6 guarantees that the search directions of the iterates afterward point to $x_{*}$ up to the noise $e$. Therefore, the iterates by Algorithm 1 converge to $x_{*}$ up to the noise. In other words, the parameter $\epsilon$ in WDC and RRIC does not influence the size of the neighborhood that iterates converge to.

Suppose the WDC and RRIC hold with $200d\sqrt{d\sqrt{\epsilon}}<1$ and $x\in\mathcal{B}(x_{*},d\sqrt{\epsilon}\|x_{*}\|)$. Then for all $x\neq 0$ and for all $v_{x}\in\partial f(x)$,

3 Proof of Theorem 3.1

The proof can be divided into three parts. We first show that the iterates $\{x_{i}\}$ converge to a neighborhoods of $x_{*}$ and $-\rho_{d}x_{*}$, whose sizes depend on $\epsilon$ and the noise energy $\|e\|$. Second, we show that the iterates only converge to the neighborhood of $x_{*}$ that depends both on $\epsilon$ as well as on the noise energy $\|e\|$. Lastly, we show that once an iterate is in the aforementioned neighborhood of $x_{*}$, the subsequent iterates converge to a neighborhood of $x_{*}$ whose size only depends on the noise $\|e\|$, but not on $\epsilon$.

Convergence to a neighborhood of $x_{*}$ or $-\rho_{d}x_{*}$: We prove that if $\|h_{x_{i}}\|$ is sufficiently large, specifically if the iterate $x_{i}$ is not in the set $S_{\beta}$ with

then Algorithm 1 makes progress in the sense that $f(x_{i+1})-f(x_{i})$ is smaller than a certain negative value. Therefore, the iterates of Algorithm 1 converge to $S_{\beta}$.

where the second inequality follows from the definition of $S_{\beta}$ and Lemma 5.2, and the third inequality follows from the definition of $\beta$.

Second, by Lemma 5.1 and Lemma 5.3, for all $a\in$ and $i>T$ ($T$ is defined in Lemma 5.3), we have

where the second inequality follows from Lemma 5.2 and (5.6), and the fourth inequality follows from Lemma A.1 and the assumption $\|e\|\leq\frac{K_{2}\|x_{*}\|}{d^{42}2^{d/2}}$.

with the appropriate constants chosen sufficiently small, where $b_{1}$ is a universal constant. Choosing $v_{\hat{x}_{i}}=\eta_{\hat{x}_{i}}$ yields

Therefore, combining (5.3) and (5.8) yields

where we used that $\nu b_{0}\frac{d^{2}}{2^{d}}\leq 1/12$ by the assumption that the step size obeys $\nu=K_{3}2^{d}/d^{2}$ and by taking $K_{3}$ appropriately small. Applying (5.5) to (5.9) yields

Convergence to a neighborhood of $x_{*}$: Note that by the assumption $\|e\|\leq\frac{K_{2}\|x_{*}\|}{d^{42}2^{d/2}}$ and $\epsilon\leq K_{1}/d^{90}$, our choice of $\beta$ obeys $\beta\leq\frac{1}{64^{2}d^{12}}$ for sufficiently small $K_{1},K_{2}$, and thus the assumptions of Lemma 5.4 are met and we have

Here, we defined the radius $r=K_{5}d^{9}\sqrt{\epsilon}\|x_{*}\|+K_{6}d^{6}\|e\|2^{d/2}$, and $K_{5}$ and $K_{6}$ are universal constants and are used in (3.4).

By the assumption $\|e\|\leq\frac{K_{2}\|x_{*}\|}{d^{42}2^{d/2}}$ and $\epsilon\leq K_{1}/d^{90}$ and choosing $K_{1}$ and $K_{2}$ sufficiently small, we have $r\leq a_{4}d^{-10}\|x_{*}\|$ and $\sqrt{r\|x_{*}\|}d^{8}\leq a_{4}d^{-10}\|x_{*}\|$. Note that the powers of $d$ in the upper bounds of $\|e\|$ and $\epsilon$, which are $-42$ and $-90$ respectively, are used to get $\sqrt{r\|x_{*}\|}d^{8}\leq a_{4}d^{-10}\|x_{*}\|$. It follows from (5.10) that

where $a_{4}$ is defined in Lemma 5.5, $b_{2}=1-\frac{\nu}{2^{d}}\frac{7}{8}$ and $b_{4}$ is a universal constant.

Using (5.11) and $\nu=K_{3}\frac{2^{d}}{d^{2}}$, we have

where $b_{2}=1-7K_{3}/(8d^{2})$ and $b_{3}$ is a universal constant. Repeatedly applying (5.12) yields

where the last inequality follows from the definition of $b_{2}$ and the step size $\nu=K_{3}\frac{2^{d}}{d^{2}}$, and $b_{4}$ is a universal constant. This finishes the proof for (3.5). Inequality (3.6) follows from Lemma A.8.

This concludes the proof of our main result. In the remainder, we provide proofs of the lemmas above.

4 Proof of Lemma 5.1

For brevity of notation, let $\zeta_{j,z}=\prod_{i=j}^{d-1}\frac{\pi-\bar{\theta}_{i,z,x_{*}}}{\pi}$. Combining (5.13) and (5.14) gives $|\bar{\theta}_{0,x,x_{*}}-\bar{\theta}_{0,y,x_{*}}|\leq 4\max\left(\frac{1}{\|x\|},\frac{1}{\|y\|}\right)\|x-y\|$. Inequality (5.15) implies $|\bar{\theta}_{i,x,x_{*}}-\bar{\theta}_{i,y,x_{*}}|\leq|\bar{\theta}_{j,x,x_{*}}-\bar{\theta}_{j,y,x_{*}}|,\forall i\geq j$. It follows that

We use the following result which is proven later in Lemma A.2:

Using (5.13) and (5.14) and noting $\|\hat{x}-\hat{y}\|\leq\theta_{x,y,x_{*}}$ yield

Finally, combining (5.16), (5.17), (5.18), (5.19) and (5.20) yields the result.

5 Proof of Lemma 5.2

For any $x\neq 0$ and suppose $G(x)$ is differentiable at $x$, we have

where the second inequality follows from [HV17, (29)] and the third inequality follows from Lemma A.3 given later.

Since $f(x)$ is a piecewise quadratic function, by [Cla17, Theorem 9.6], we have

where $conv$ denotes the convex hull of the vectors $v_{1},\ldots,v_{t}$, $t$ is the number of quadratic functions adjoint to $x$ and $v_{i}$ is the gradient of the $i$-th quadratic function at $x$. Therefore, for any $v\in\partial f(x)$, there exist $c_{1},c_{2},\ldots,c_{t}\geq 0$ such that $c_{1}+c_{2}+\ldots+c_{t}=1$ and $v=c_{1}v_{1}+c_{2}v_{2}+\ldots+c_{t}v_{t}$. Note that for any $v_{i}$, there exists $u_{i}$ so that $v_{i}=\lim_{\delta\rightarrow 0^{+}}\nabla f(x+\delta_{i}u_{i})$, and $f$ is differentiable at $f(x+\delta u_{i})$ for sufficiently small $\delta$.

The proof is concluded by appealing to the continuity of $h_{x}$ with respect to nonzero $x$, inequality (5.21), and by noting that

where we used the inequality above and that $\sum_{i}c_{i}=1$.

6 Proof of Lemma 5.3

We next show that, for any $x\in\mathcal{B}(0,\frac{1}{16\pi}\|x_{*}\|)$, and $v_{x}\in\partial f(x)$, it holds that $\|{v}_{x}\|\geq\frac{1}{2^{d}16\pi}\|x_{*}\|$.

Therefore, $\left\|\Lambda_{x}^{T}A^{T}(A\Lambda_{x}x-A\Lambda_{x_{*}}x_{*})-\Lambda_{x}^{T}(\Lambda_{x}x-\Lambda_{x_{*}}x_{*})\right\|\leq\epsilon\frac{1}{2^{d}}(1+2\epsilon d)^{2}(\|x\|+\|x_{*}\|)$. Therefore, we have

If $G(x)$ is not differentiable at $x$, by equation (3.7), we have

for all $v_{x}\in\partial f(x)$. This concludes the proof of (5.22).

7 Proof of Lemma 5.5

and note that $f(x)=f_{\eta}(x)+\|e\|^{2}$. Consider $x\in\mathcal{B}(\phi_{d}x_{*},\varphi\|x_{*}\|)$, for a $\varphi$ that will be specified later. Note that

where the second inequality holds by Lemma A.3, and the last inequality holds by our assumption on $x$. Thus, by Lemma A.5 and Lemma A.6, we have

Additionally, for $x\in\mathcal{B}(\phi_{d}x_{*},\varphi\|x_{*}\|)$, we have

where the last inequality follows from $\epsilon<\sqrt{\epsilon}$, $\rho_{d}\leq 1$, $4\epsilon d<1$, $\varphi<1$ and assuming $\varphi=\epsilon$.

Similarly, we have that for any $y\in\mathcal{B}(-\phi_{d}x_{*},\varphi\|x_{*}\|)$

Using $\epsilon<\sqrt{\epsilon}$, $\rho_{d}\leq 1$, $4\epsilon d<1$, $\varphi<1$, $\|e\|\leq\frac{K_{2}\|x_{*}\|}{d^{42}2^{d/2}}\leq\frac{K_{2}\|x_{*}\|}{d^{2}2^{d/2}}$ and assuming $\varphi=\epsilon$, the right side of (5.25) is smaller than the right side of (5.26) if

It follows from Lemma A.4 that $1-\rho_{d}\geq 1/(a_{7}(d+2)^{2})$. Thus, it suffices to have $\varphi=\epsilon=\frac{a_{4}}{d^{10}}$ and $4K_{2}/d^{2}\leq\frac{1}{2}\frac{1}{a_{7}(d+2)^{2}}\leq 1-\rho_{d}$ for an appropriate universal constant $K_{2}$, and for an appropriate universal constant $a_{4}$.

8 Proof of Lemma 5.6

Therefore, $\left\|\bar{v}_{x}-\Lambda_{j,x}^{T}(\Lambda_{j,x}x-\Lambda_{j,x_{*}}x_{*})\right\|\leq\epsilon\frac{1.2}{2^{d}}(1+2\epsilon d)\|x-x_{*}\|\leq\frac{1}{16}\frac{1}{2^{d}}\|x-x_{*}\|$. Combining with Lemma A.9 yields that

For any $x\neq 0$ and for any $v\in\partial f(x)$, by (3.7), there exist $c_{1},c_{2},\ldots,c_{t}\geq 0$ such that $c_{1}+c_{2}+\ldots+c_{t}=1$ and $v=c_{1}v_{1}+c_{2}v_{2}+\ldots+c_{t}v_{t}$. It follows that $\|v-\frac{1}{2^{d}}(x-x_{*})\|\leq\sum_{j=1}^{t}c_{j}\|v_{j}-\frac{1}{2^{d}}(x-x_{*})\|\leq\frac{1}{2^{d}}\frac{1}{8}\|x-x_{*}\|+\frac{2}{2^{d/2}}\|e\|$.

References

Appendix A Supporting Lemmas

Lemma A.1 is used in proofs for Section 5.3 and Lemma 5.3.

Suppose that the WDC and RRIC holds with $\epsilon<1/(16\pi d^{2})^{2}$ and that the noise $e$ satisfies $\|e\|\leq a_{5}2^{-d/2}\|x_{*}\|$. Then, for all $x$ and all $v_{x}\in\partial f(x)$,

where $a_{5}$ and $a_{6}$ are universal constants.

Define for convenience $\zeta_{j}=\prod_{i=j}^{d-1}\frac{\pi-\bar{\theta}_{j,x,x_{*}}}{\pi}$. We have

where the second inequality follows from the definition of $h_{x}$ and Lemma 5.2, the third inequality uses $|\zeta_{j}|\leq 1$, and the last inequality uses the assumption $\|e\|\leq a_{5}2^{-d/2}\|x_{*}\|$. ∎

Lemma A.2 is used in proofs for Lemma 5.1.

Suppose $a_{i},b_{i}\in[0,\pi]$ for $i=1,\ldots,k$, and $|a_{i}-b_{i}|\leq|a_{j}-b_{j}|,\forall i\geq j$. Then it holds that

Prove by induction. It is easy to verify that the inequality holds if $k=1$. Suppose the inequality holds with $k=t-1$. Then

Lemma A.3 is used in proofs for Lemma 5.2, Lemma 5.3, and Lemma 5.5.

Suppose the WDC and RRIC hold with $\epsilon\leq 1/(16\pi d^{2})^{2}$. Then we have

where $q_{x}=\left(\prod_{i=d}^{1}W_{i,+,x}\right)^{T}A^{T}e$. In addition, if $x$ is differentiable at $G(x)$, then we have

where the second inequality follows from RRIC and the last inequality follows from [HV17, (10)]. Therefore, $\left|x^{T}q_{x}\right|\leq\frac{2}{2^{d/2}}\|e\|\|x\|$.

Combining above inequality with $\prod_{i=d}^{1}\|W_{i,+,x}\|\leq(1+2\epsilon d)/2^{d/2}\leq 1.5/2^{d/2}$ given in [HV17, (10)] yields

where the second inequality follows from the assumption on $\epsilon$. Therefore, we obtain

Lemma A.4 is used in proofs for Lemma 5.5.

We recall the results in [HV17, (36), (37), and (50)]:

Therefore, we have for all $0\leq i\leq d-2$,

where the second and the fifth inequalities follow from (A.2) and (A.3) respectively. Since $\pi^{3}/(12(i+1)^{3})\leq\check{\theta}_{i}^{3}/12\leq\check{\theta}_{i}-\sin\check{\theta}_{i}\leq\check{\theta}_{i}^{3}/6\leq 27\pi^{3}/(6(i+3)^{3})$, we have that for all $d\geq 3$

where we use $\sum_{i=4}^{\infty}\frac{1}{i^{2}}\leq\frac{\pi^{2}}{6}$ and $\sum_{i=1}^{n}i^{3}=O(n^{4})$. Since $\rho_{d}\geq 1-250/(d+1)$ and $\rho_{d}>0$ for all $d\geq 2$, we have $\min_{d\geq 2}\rho_{d}>0$. ∎

Lemma A.5 is used in proofs for Lemma 5.5.

Fix $0<a_{9}<\frac{1}{4d^{2}\pi}$. For any $\phi_{d}\in[\rho_{d},1]$, it holds that

If $x\in\mathcal{B}(\phi_{d}x_{*},a_{9}\|x_{*}\|)$, then we have $0\leq\bar{\theta}_{0,x,x_{*}}\leq\arcsin(a_{9}/\phi_{d})\leq\frac{\pi a_{9}}{2\phi_{d}}$, $0\leq\bar{\theta}_{0,x,x_{*}}\leq\bar{\theta}_{i,x,x_{*}}\leq\frac{\pi a_{9}}{2\phi_{d}}$, and $\phi_{d}\|x_{*}\|-a_{9}\|x_{*}\|\leq\|x\|\leq\phi_{d}\|x_{*}\|+a_{9}\|x_{*}\|$. Note that $\cos\theta\geq 1-\frac{\theta^{2}}{2},\forall\theta\in[0,\pi]$. We have

where the last inequality is by Lemma A.4 and $a_{9}<1/(4\pi)$.

If $x\in\mathcal{B}(-\phi_{d}x_{*},a_{9}\|x_{*}\|)$, then we have $0\leq\pi-\bar{\theta}_{0,x,x_{*}}\leq\arcsin(a_{9}\pi)\leq\frac{\pi^{2}}{2}a_{9}$, and $\phi_{d}\|x_{*}\|-a_{9}\|x_{*}\|\leq\|x\|\leq\phi_{d}\|x_{*}\|+a_{9}\|x_{*}\|$. It follows that

Lemma A.6 is used in proofs for Lemma 5.5.

If the WDC and RRIC hold with $\epsilon<1/(16\pi d^{2})^{2}$, then we have

For brevity of notation, let $\Lambda_{z}=\prod_{i=d}^{1}W_{i,+,z}$. We have

where the first inequality uses the WDC, the RRIC, and [HV17, Lemma 6]. ∎

Lemma A.7 is used in proofs for Lemma A.8.

Combining (A.4), (A.6), and $\|W_{i,+,x}\|^{2}\leq 1/2+\epsilon$ given in [HV17, (10)] yields the result. ∎

Lemma A.8 is used in proofs for Lemma 5.6 and Lemma A.9.

Suppose $x\in\mathcal{B}(x_{*},d\sqrt{\epsilon}\|x_{*}\|)$, and the WDC holds with $\epsilon<1/(200)^{4}/d^{6}$. Then it holds that

In this proof, we denote $\theta_{i,x,x_{*}}$ and $\bar{\theta}_{i,x,x_{*}}$ by $\theta_{i}$ and $\bar{\theta}_{i}$ respectively. Since $x\in\mathcal{B}(x_{*},d\sqrt{\epsilon}\|x_{*}\|)$, we have

By [HV17, (14)], we also have $|\theta_{i}-\bar{\theta}_{i}|\leq 4i\sqrt{\epsilon}\leq 4d\sqrt{\epsilon}$. It follows that

Note that $\sqrt{1+2\epsilon}\leq 1+\epsilon\leq 1+\sqrt{d\sqrt{\epsilon}}$. We have

where the second inequality is from that $(1+x)^{d}\leq 1+2dx$ if $0<xd<1$. Combining the above inequality with Lemma A.7 yields

Lemma A.9 is used in proofs for Lemma 5.6.

Suppose $x\in\mathcal{B}(x_{*},d\sqrt{\epsilon}\|x_{*}\|)$, and the WDC holds with $\epsilon<1/(200)^{4}/d^{6}$. Then it holds that

For brevity of notation, let $\Lambda_{j,k,z}=\prod_{i=j}^{k}W_{i,+,z}$. We have

where the first equation is by [HV17, (10)]; the second equation is by (A.6); the third equation is by Lemma A.8 and (A.8). The result follows from (A.9), (A.10) and (A.11). ∎