Convergence of gradient descent for deep neural networks

A convergence criterion for gradient descent

with $\phi(0)=x_{0}$. Gradient descent and its many variants are indispensable tools in all branches of science and engineering, and particularly in modern machine learning and data science. The convergence properties of gradient descent are well-understood when the objective function $f$ is convex , and it is known that finding local minima of nonconvex functions by gradient descent is an NP-complete problem . In spite of this, gradient descent is widely used in practice to find local and global minima in highly nonconvex problems, especially in high dimensions. For example, it has been observed that gradient descent can often find global minima of training loss in deep learning , which is one of the reasons behind great success of the ‘deep learning revolution’ .

This article presents a novel criterion for convergence of gradient descent to a global minimum. The criterion is related to (and maybe seen as a strengthening of) the classical Kurdyka–Łojasiewicz inequality . It is also related to results from nonsmooth analysis, such as those in . Indeed, our proof idea bears close resemblance with the classical ‘Łojasiewicz trapping argument’ . Nevertheless, the convergence criterion stated below has not appeared in this exact form previously in the literature.

where $|\nabla f(x)|$ is the Euclidean norm of $\nabla f(x)$. If $f(x)=0$ for all $x\in B(x_{0},r)$, then we let $\alpha(x_{0},r):=\infty$. Our main assumption is that for some $r>0$,

Under the above assumption, we have two results. The first result, stated below, shows that the gradient flow started at $x_{0}$ converges exponentially fast to a global minimum of $f$ in $B(x_{0},r)$ where $f$ is zero. The existence of a global minimum in $B(x_{0},r)$ is a part of the conclusion, and not an assumption.

Let $f$, $x_{0}$, and $\alpha$ be as above. Assume that (1.1) holds for some $r>0$, and let $\alpha:=\alpha(x_{0},r)$. Then there is a unique solution of the gradient flow equation

on $[0,\infty)$ with $\phi(0)=x_{0}$, and this flow stays in $B(x_{0},r)$ for all time, and converges to some $x^{*}\in B(x_{0},r)$ where $f(x^{*})=0$. Moreover, for each $t\geq 0$, we have

Our second result is the analogue of Theorem 1.1 for gradient descent. It says that under the condition (1.1), gradient descent started at $x_{0}$, with a small enough step size, converges to a global minimum of $f$ in $B(x_{0},r)$. Again, the existence of a global minimum in $B(x_{0},r)$ is a part of the conclusion.

Let $f$, $x_{0}$, and $\alpha$ be as above. Assume that (1.1) holds for some $r>0$, and let $\alpha:=\alpha(x_{0},r)$. Choose $\epsilon\in(0,1)$ such that

which is possible since (1.1) holds. Let $L_{1}$ be a uniform upper bound on the magnitudes of the first-order derivatives of $f$ in $B(x_{0},r)$, and let $L_{2}$ be a uniform upper bound on the magnitudes of the second-order derivatives of $f$ in $B(x_{0},2r)$. Choose any $\eta>0$ such that

for each $k\geq 0$. Then $x_{k}\in B(x_{0},r)$ for all $k$, and as $k\to\infty$, $x_{k}$ converges to a point $x^{*}\in B(x_{0},r)$ where $f(x^{*})=0$. Moreover, with $\delta:=\min\{1,(1-\epsilon)\alpha\eta\}$, we have that for each $k$,

Note that the above results have nothing to say about variants of gradient descent, such as stochastic gradient descent. Adding a stochastic component to the gradient descent algorithm has various benefits, such as helping it escape saddle points . Since it is known that stochastic gradient methods often asymptotically follow the path of a differential equation , it would be interesting to see if analogues of Theorems 1.1 and 1.2 can be proved for stochastic gradient descent. We also do not have anything to say about algorithms that aim to find critical points instead of global minima in nonconvex problems, such as the ones surveyed in . For a recent survey of the many variants of stochastic gradient descent and their applications in machine learning, see . For a comprehensive account of all variants of gradient descent, see . For some essential limitations of nonconvex optimization, see .

It is possible that Theorems 1.1 and 1.2 may be generalizable to what are variously called lower $C^{2}$ functions, or proximal-regular functions, or weakly convex functions. However, the generalizations are not obvious (especially for Theorem 1.2), and are therefore left for future investigation.

Application to deep neural networks

A feedforward neural network consists of the following components:

A positive integer $L$, which denotes the number of layers. It is sometimes called the depth of the network. The number $L-1$ denotes the ‘number of hidden layers’. To avoid trivialities, we will assume that $L\geq 2$ — that is, there is at least one hidden layer.

A sequence of positive integers $d_{1},\ldots,d_{L}$, denoting the dimensions of layers $1,\ldots,L$. The maximum of $d_{1},\ldots,d_{L}$ is called the width of the network. The dimension of the ‘output layer’, $d_{L}$, is often taken to be $1$. We will henceforth take $d_{L}=1$.

where the activation functions $\sigma_{1},\ldots,\sigma_{L}$ act componentwise on vectors of dimensions $d_{1},\ldots,d_{L}$.

for $k\geq 0$, where $\eta$ is the step size, and $\nabla S$ denotes the gradient of $S$ (assuming that the activation functions are differentiable).

There is an enormous body of literature on convergence properties of gradient descent for neural networks. The following are some of the most important contributions. Further references can be found in the review sections of these papers and also in the recent comprehensive survey .

Convergence for convex neural networks was studied in , and for linear networks in . Convergence in the absence of convexity and linearity has remained an open problem, except in one particular scenario — when the dimensions of the hidden layers $1,\ldots,L-1$ are extremely large, where ‘extremely large’ may mean either tending to infinity, or larger than some large enough power of the sample size. This is now called the ‘infinite width’ or ‘overparametrized’ regime. Following some early results in , this approach was fully developed independently in the concurrent papers . The key idea here is that in the overparametrized regime, gradient descent for the neural net can be approximated by gradient descent in a linear setting. Since then, this idea has been widely applied in a variety of settings, for example, in . For some recent advances beyond the overparametrized regime, see and references therein.

We have two results about convergence of gradient descent for feedforward neural networks of bounded width and depth. The first theorem shows that under fairly general conditions, it is possible to find an exact fit to the data (i.e., a point $w^{*}$ where $S(w^{*})=0$) via gradient descent with suitable initialization and step size. The main requirement is that the input data $x_{1},\ldots,x_{n}$ have to be linearly independent, which necessarily means that the dimension $d$ of the input space has to be $\geq n$. This condition is inevitable, because if this is not true, then there may not exist any point $w^{*}$ where $S(w^{*})=0$ even for linear activation.

Recall that the width of the network is the number $m:=\max\{d_{1},\ldots,d_{L}\}$. It is important to note that this excludes the input dimension $d_{0}=d$. Theorem 2.1 implicitly needs $d\geq n$, but there is no requirement on the width $m$. Most previous works need the width to grow with $n$. For example, Soltanolkotabi et al. require $m\geq 2n$ (their result is only for networks with one hidden layer), while both Du et al. and Allen-Zhu et al. — who deal with networks of arbitrary depth — require $m$ to be at least as large as some polynomial in $n$. One existing result result that might imply Theorem 2.1 is [19, Theorem 2.4], but it is completely clear if it does.

The class of activation functions allowed by Theorem 2.1 includes many functions used in common practice, such as linear activation ($\sigma(x)=x$), bipolar sigmoid activation ($\sigma(x)=(1-e^{-x})/(1+e^{-x})$), and tanh activation ($\sigma(x)=\tanh x$). Moreover, the condition $\sigma(0)=0$ is not a serious restriction, since the presence of the bias vectors implies that the class of models remains the same if we subtract off some constants from our activation functions to make them zero at the origin. In that sense, Theorem 2.1 also allows the sigmoid activation ($\sigma(x)=1/(1+e^{-x})$), smoothed ReLU activation ($\sigma(x)=\log(1+e^{x})$), and complementary log-log activation ($\sigma(x)=1-e^{-e^{x}}$). It does not, however, allow activation functions that are not twice continuously differentiable, such as ReLU activation ($\sigma(x)=\max\{x,0\}$), step activation ($\sigma(x)=1$ if $x>0$ and if $x\leq 0$), and piecewise linear activation.

Theorem 2.1 gives a criterion for convergence of gradient descent to a solution that perfectly interpolates the data. It does not, however, say anything about why such interpolating solutions sometimes have good generalization errors, or conditions under which deep learning performs well (or poorly). These are some of the other great mysteries of deep neural networks that have attracted much attention. For more about these, see and references therein.

The proof of Theorem 2.1 yields formulas for $A$ and $\eta$, but they are quite complicated and possibly sub-optimal, and are therefore omitted from the discussion. In practice, it may be easiest to just choose $A$ and $\eta$ by trial and error after choosing $W_{2},\ldots,W_{L-1}$ with arbitrary positive entries, by increasing $A$ and decreasing $\eta$ until convergence is achieved.

Not many activation functions in common use satisfy the condition that the slope is uniformly bounded below by a positive constant. One prominent example that satisfies this condition is the leaky ReLU activation function ($\sigma(x)=x$ if $x>0$ and $\sigma(x)=ax$ if $x\leq 0$, where $a$ is some positive number less than $1$). However, leaky ReLU activation is not twice continuously differentiable. We propose the following smooth modification of the leaky ReLU:

Here $a\in(0,1)$, as in the definition of leaky ReLU. Note that as $x\to\pm\infty$, smooth leaky ReLU has the same asymptotic behavior as leaky ReLU. Although $\sigma(0)\neq 0$, this can be easily fixed by subtracting a constant (which does not affect anything since we have bias vectors in our model).

Proof of Theorem 1.1

To avoid trivialities, let us assume that $f$ is not everywhere zero in $B(x_{0},r)$, and hence $\alpha<\infty$. Throughout this proof, we will denote the closed ball $B(x,r_{0})$ by $B$ and its interior by $U$.

Take any $S<T_{x}-t$. Define $g(s):=\phi_{x}(t+s)$ for $s\in[0,S]$. Then

Thus, $h_{1}$ satisfies the integral equation for the gradient flow starting from $y$ in the interval $[0,L]$. Thus, by the uniqueness assumption for this flow in $[0,L]$, we get that $h_{1}=\phi_{y}$ in this interval. Consequently, $h=g$ in $[0,t+L]$. Thus, the gradient flow starting from $x$ has a unique solution in $[0,T]$ for every $T\leq t+S$. Since $t+S>T_{x}$, this contradicts the definition of $T_{x}$. ∎

Let $K^{\prime}$ be the set of all points that are within distance $1$ from $K$. Note that $K^{\prime}\supseteq K$ and $K^{\prime}$ is compact. Since $f$ is in $C^{2}$, its first and second order derivatives are uniformly bounded on $K^{\prime}$. Thus, there is some $L$ such that for any $x,y\in K^{\prime}$,

Let $\mathcal{A}$ be the subset of $\mathcal{B}$ consisting of all $g$ such that $g(0)=x$ and $g(t)\in K^{\prime}$ for all $t\in[0,T]$. It is easy to see that $\mathcal{A}$ is a closed subset of $\mathcal{B}$. Define a map $\Phi:\mathcal{A}\to\mathcal{B}$ as

where the second inequality holds because $g(s)\in K^{\prime}$ for all $s$, and the third inequality holds because $t\leq 1/L$. Since all points at distance $\leq 1$ from $x$ are in $K^{\prime}$, this shows that $\Phi(\mathcal{A})\subseteq\mathcal{A}$. Next, note that for any $g,h\in\mathcal{A}$, and any $t\in[0,T]$,

We claim that $g^{*}$ is the only such map. To prove this, suppose that there exists another map $h$ with the above properties. If $h$ maps into $K^{\prime}$, then the uniqueness of the fixed point implies that $h=g^{*}$. So, suppose that $h$ ventures outside $K^{\prime}$. Let

Since $h(0)=x\in K^{\prime}$ and $h$ goes outside $K^{\prime}$, $t_{0}$ is well-defined and finite. Moreover, since $K^{\prime}$ is closed, $h(t_{0})\in\partial K^{\prime}$. But note that since $h(s)\in K^{\prime}$ for all $s\leq t_{0}$,

But this implies that the ball of radius $1/3$ centered at $h(t_{0})$ is completely contained in $K^{\prime}$, and hence, $h(t_{0})\notin\partial K^{\prime}$. Thus, $h$ cannot venture outside $K^{\prime}$. We conclude that $T_{x}\geq 1/L$. ∎

The above lemma has several useful corollaries.

Suppose that $|\phi_{x}(t)|\not\to\infty$. Then there is a compact set $K$ such that for any $\epsilon>0$, we can find $t\in[T_{x}-\epsilon,T_{x})$ with $\phi_{x}(t)\in K$. By Lemma 3.2, we can find $\epsilon\in(0,\inf_{y\in K}T_{y})$. Take any $t\in[T_{x}-\epsilon,T_{x})$ such that $y:=\phi_{x}(t)\in K$. Then, by Lemma 3.1, we have $T_{y}=T_{x}-t<\epsilon$. But this contradicts the fact that $T_{y}\geq\inf_{z\in K}T_{z}>\epsilon$. ∎

If $f(x)=0$, then since $f$ is a nonnegative $C^{2}$ function, $\nabla f(x)$ must also be zero. Thus, it suffices to prove the result under the assumption that $\nabla f(x)=0$. Taking $K=\{x\}$ in Lemma 3.2, we get that $T_{x}>0$. Suppose that $T_{x}$ is finite. Then let $t:=T_{x}/2$. Note that since $\nabla f(x)=0$, $g(s)\equiv x$ is a solution of the gradient flow equation starting from $x$ in the interval $[0,t]$. By uniqueness, this shows that $\phi_{x}(s)=x$ for all $s\in[0,t]$. In particular, $\phi_{x}(t)=x$. By Lemma 3.1, this implies that $T_{x}=T_{x}-t=T_{x}/2$, which contradicts the fact that $T_{x}$ is nonzero and finite. Thus, $T_{x}=\infty$. Again, the function $g(t)\equiv x$ is a solution of the flow equation in $[0,\infty)$. Thus, by uniqueness, $\phi_{x}(t)=x$ for all $x$. ∎

Take any $t$ such that $\nabla f(\phi_{x}(t))=0$ or $f(\phi_{x}(t))=0$. Let $y:=\phi_{x}(t)$. Then by Lemma 3.1, $T_{y}=T_{x}-t$. But by Corollary 3.4, $T_{y}=\infty$. Thus, $T_{x}=\infty$. Also by Corollary 3.4, $\phi_{y}(u)=y=\phi_{x}(t)$ for all $u>0$, and by Lemma 3.1, $\phi_{y}(u)=\phi_{x}(t+u)$ for all $u>0$. Thus, $\phi_{x}(s)=\phi_{x}(t)$ for all $s>t$. ∎

In the following, let us fix $x_{0}$ and $r$ as in Theorem 1.1 and write $\phi$ and $T$ instead of $\phi_{x_{0}}$ and $T_{x_{0}}$, for simplicity of notation.

If $T<\infty$, then $\phi$ must visit the boundary of $B$.

Suppose that $T<\infty$ and $\phi$ remains in $U$ throughout. By Lemma 3.2, there is some $\delta>0$ such that $T_{y}\geq\delta$ for all $y\in B$. Choose $t\in(T-\delta,T)$. Let $z:=\phi(t)$. Then $z\in U$, and therefore $T_{z}\geq\delta$. This shows that the gradient flow starting from $x_{0}$ exists up to time at least $t+\delta$. Since $t+\delta>T$, this gives a contradiction which proves that $\phi$ cannot remain in $U$ throughout. ∎

Let $t\geq 0$ be any number such that $\phi(s)\in B$ for all $s\leq t$. Then for all $s\leq t$,

Note that by the flow equation for $\phi$,

By the definition of $\alpha$, the right side is bounded above by $-\alpha f(\phi(s))$ if $\phi(s)\in B$. It is now a standard exercise to deduce the claimed inequality. ∎

The flow $\phi$ cannot visit the boundary of $B$.

Suppose that $\phi$ does visit the boundary of $B$. Let $t_{0}:=\inf\{t:\phi(t)\in\partial B\}$. Then $\phi(t_{0})\in\partial B$ and $\phi(s)\in U$ for all $s<t_{0}$. By the flow equation,

Now, since $\phi(s)\neq\phi(t_{0})$ for all $s<t_{0}$, Corollary 3.5 shows that $f(\phi(s))\neq 0$ for all $s<t_{0}$. Thus, the map

is differentiable in $(0,t_{0})$, with continuous derivative

where the second identity follows from (3.1). Thus, for any compact interval $[a,b]\subseteq(0,t_{0})$,

Since $g$ is continuous on $[0,t_{0}]$, we can take $a\to 0$ and $b\to t_{0}$, and apply the monotone convergence theorem on the left, to get

Therefore, by (3.2) and the Cauchy–Schwarz inequality,

On the other hand, since $\phi(s)\in B$ for all $s\leq t_{0}$, Lemma 3.7 shows that

for all $s\leq t_{0}$. Plugging this bound into the previous display, we get

But the last quantity is strictly less than $r$, by assumption (1.1). Since $\phi(t_{0})\in\partial B$, this gives a contradiction, which proves the lemma. ∎

Combining Lemma 3.6 and Lemma 3.8, we see that $T=\infty$. Moreover by Lemma 3.8, $\phi$ stays in $U$ forever. Therefore, by Lemma 3.7, it follows that $f(\phi(s))\leq e^{-\alpha s}f(x_{0})$ for all $s$. It remains to establish the convergence of the flow and the rate of convergence. Let

with the understanding that $t_{0}=\infty$ if $f(\phi(t))>0$ for all $t$. Then note that for any $0\leq s<t<t_{0}$,

where $g(u)=\sqrt{f(\phi(u))}$, as in the proof of Lemma 3.8. As in that proof, note that

Combining the last three displays, and invoking assumption (1.1), we get

Note that the bound does not depend on $t$. If $t_{0}<\infty$, then by Corollary 3.5, $\phi(t)=\phi(t_{0})$ for all $t>t_{0}$. Thus, in this case $\phi(t)$ converges to $x^{*}:=\phi(t_{0})$. The rate of convergence is established by taking $t\to t_{0}$ in (3.3). If $t_{0}=\infty$, then (3.3) proves the Cauchy property of the flow $\phi$, which shows that $\phi(t)$ converges to some $x^{*}\in B$ as $t\to\infty$. Again, taking $t\to\infty$ in (3.3) proves the rate of convergence. ∎

Proof of Theorem 1.2

If $f(x_{0})=0$, then $\nabla f(x_{0})=0$ and therefore $x_{k}=x_{0}$ for all $k$, and there is nothing to prove. So, let us assume that $f(x_{0})>0$. The following lemma is the key step in the proof of Theorem 1.2.

For all $k\geq 0$, $x_{k}\in B(x_{0},r)$.

The proof of this lemma will be carried out via induction on $k$. We have $x_{0}\in B(x_{0},r)$. Suppose that $x_{1},\ldots,x_{k-1}\in B(x_{0},r)$ for some $k\geq 1$. We will use this hypothesis to show that $x_{k}\in B(x_{0},r)$, with $k$ remaining fixed henceforth.

Then for all $0\leq j\leq k-1$, $|R_{j}|\leq\epsilon\eta|\nabla f(x_{j})|^{2}$.

Since $x_{k-1}\in B(x_{0},r)$, the assumed upper bound on $\eta$ implies that

Thus, $|x_{k}-x_{k-1}|\leq r$, and therefore, $x_{k}\in B(x_{0},2r)$. Consequently, the line segment joining $x_{k-1}$ and $x_{k}$ lies entirely in $B(x_{0},2r)$. Since $x_{0},\ldots,x_{k-1}\in B(x_{0},r)$, the line segments joining $x_{j}$ and $x_{j+1}$ lies in $B(x_{0},r)$ for all $j\leq k-2$. Thus, by Taylor expansion, we have that for any $0\leq j\leq k-1$,

where $x_{j}^{*}$ is a point on the line segment joining $x_{j}$ and $x_{j+1}$, and $\nabla^{2}f(x_{j}^{*})$ is the Hessian matrix of $f$ at $x_{j}^{*}$. Since $L_{2}$ is an upper bound on the magnitudes of all second order derivatives of $f$ in $B(x_{0},2r)$, and $x_{j}^{*}\in B(x_{0},2r)$, this gives

which proves that $|R_{j}|\leq\frac{1}{2}L_{2}p\eta^{2}|\nabla f(x_{j})|^{2}$. Since $L_{2}p\eta\leq 2\epsilon$, this proves the claim. ∎

We have $(1-\epsilon)\alpha\eta\leq 1$, and for any $0\leq j\leq k$,

Since $x_{j}\in B(x_{0},r)$ for $j\leq k-1$, Lemma 4.2 and the definition of $\alpha$ imply that for $j\leq k-1$,

Since $f(x_{0})>0$ and $f(x_{1})\geq 0$, we can take $j=0$ above and divide both sides by $f(x_{0})$ to get that $(1-\epsilon)\alpha\eta\leq 1$. Iterating the above inequality gives the desired upper bound for $f(x_{j})$. ∎

Rearranging terms, we get the desired inequality. ∎

Let $\kappa:=(1-\epsilon)^{-1}$. By Lemma 4.4,

Also by Lemma 4.4, $f(x_{j})\geq f(x_{j+1})$ for each $j\leq k-1$. Thus, for any $j\leq k-1$, we use the Cauchy–Schwarz inequality to get

Using Lemma 4.3 to bound the terms on the right side, we get

Now, for $t\in$, we have the inequality $1-t\leq(1-t/2)^{2}$. This gives

Plugging this into the previous display completes the proof. ∎

We are now ready to complete the proof of Lemma 4.1 and then use it prove Theorem 1.2.

Applying Lemma 4.5 with $j=0$, and recalling the criterion (1.2) used for choosing $\epsilon$, we get

This proves that $x_{k}\in B(x_{0},r)$, completing the induction step. ∎

By Lemma 4.1, we know that $x_{k}\in B(x_{0},r)$ for all $k$. Thus, Lemma 4.5 holds for all $k\geq 1$ and all $j<k$. In particular,

Note that the bound goes to zero as $j\to\infty$, and has no dependence on $k$. Thus, $\{x_{k}\}_{k\geq 0}$ is a Cauchy sequence in $B(x_{0},r)$, and therefore, converges to a limit $x^{*}\in B(x_{0},r)$. Moreover, the above bound is also a bound for $|x^{*}-x_{j}|$, since it has no dependence on $k$. Lastly, since $x_{k}\in B(x_{0},r)$ for all $k$, Lemma 4.3 also holds for any $j$. This shows that $f(x^{*})=0$ and gives the required bound for $f(x_{j})$. ∎

Proof of Theorem 2.1

Using this relation and the fact that $D_{L}=1$, we get

Then the definition of $S$ shows that for any $w$ where $S(w)\neq 0$,

We obtain a lower bound on the above term by simply considering those $j$’s that correspond to the entries of $W_{1}$. By (5.1), this gives

Now take any $w$ as in the statement of Theorem 2.1, that is,

the entries of $W_{2},\ldots,W_{L-1}$ are all strictly positive, and

irrespective of the values of $W_{2},\ldots,W_{L}$. Let $\delta$ be the minimum of all the entries of $W_{2},\ldots,W_{L-1}$ and $K$ be the maximum. Take any $w^{\prime}=(W_{1}^{\prime},b_{1}^{\prime},\ldots,W_{L}^{\prime},b_{L}^{\prime})$ such that $|w-w^{\prime}|\leq\delta/2$. Then the entries of $W_{2}^{\prime},\ldots,W_{L-1}^{\prime}$ are all bounded below by $\delta/2$ and bounded above by

Thus, by (5.3) and (5.4), we see that for any $w^{\prime}\in B(w,\delta/2)$ where $S(w^{\prime})\neq 0$,

Since this holds for every $w^{\prime}\in B(w,\delta/2)$, and the numbers $c_{1},\ldots,c_{L-1}$ have no dependence on $A$, it follows that if we fix $\delta$ and $K$, and take $A$ sufficiently large, then by (5.5), we can ensure that

which is the criterion (1.1) for this problem. By Theorems 1.1 and 1.2, this completes the proof of Theorem 2.1.

Proof of Theorem 2.2

In this proof, $\theta_{1},\theta_{2},\ldots$ will denote arbitrary positive constants whose values depend only on $c$, $C_{1}$, $C_{2}$, $\alpha$, $\beta$, $L$, and $d_{1},\ldots,d_{L}$. (The important thing is that these constants do not depend on the input dimension $d$.)

Thus, if $E$ happens, and we also have that

then (1.1) holds for $S$ in the ball $B(w,M)$. Looking at the above inequality, it is clear that we can choose $M=\theta_{5}$ so large that the above event is implied by the event

for some suitably defined $\theta_{6}$. Thus, if $E\cap F$ happens, then (1.1) holds for $S$ in the ball $B(w,\theta_{5})$. Now note that since the entries of $W_{1}$ are i.i.d. $\mathcal{N}(0,c/d)$ random variables,

Acknowledgements

I thank Persi Diaconis, Dmitriy Drusvyatskiy, John Duchi, and Lexing Ying for useful feedback, references, and suggestions.

References