Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels

Introduction

Convolutional Neural Networks (CNNs) have been very successful in many machine learning areas, including image classification [KSH12], face recognition [LGTB97], machine translation [GAG+17] and game playing [SHM+16]. Comparing with fully-connected neural networks (FCNN), CNNs leverage three key ideas that improve their performance in machine learning tasks, namely, sparse weights, parameter sharing and equivariance to translation [GBC16]. These ideas allow CNNs to capture common patterns in portions of original inputs.

Despite the empirical success of neural networks, the mechanism behind them is still not fully understood. Recently there are several theoretical works on analyzing FCNNs, including the expressive power of FCNNs [CSS16, CS16, RPK+16, DFS16, PLR+16, Tel16], the achievability of global optima [HV15, LSSS14, DPG+14, SS16, HM17] and the recovery/generalization guarantees [XLS17, SA15, JSA15, Tia17a, ZSJ+17].

However, theoretical results for CNNs are much fewer than those for FCNNs, possibly due to the difficulty introduced by the additional structures in CNNs. Recent theoretical CNN research focuses on generalization and recovery guarantees. In particular, generalization guarantees for two-layer CNNs are provided by [ZLW17], where they convexify CNNs by relaxing the class of CNN filters to a reproducing kernel Hilbert space (RKHS). However, to pair with RKHS, only several uncommonly used activations are acceptable. A recent CNN work [BG17] provides global optimality and recovery guarantees using gradient descent for one-hidden-layer non-overlapping CNNs with ReLU activations and Gaussian inputs. Recently [DLT17] eliminated the Gaussian inputs assumption. However, both papers only handle one kernel with non-overlapping patches.

In this paper, we consider multiple kernels instead of just one kernel as in [BG17, DLT17]. We follow the analysis in [ZSJ+17], where recovery guarantees for one-hidden-layer FCNN are provided. One-hidden-layer CNNs have additional structures compared with one-hidden-layer FCNNs, therefore, the analysis for FCNNs needs be substantially modified to be applied to CNNs. The technical barrier comes from the interaction among different patches. Fortunately, we can still show recovery guarantees of one-hidden-layer CNNs with non-overlapping patches for most commonly-used activations.

In particular, we first show that the population Hessian of the squared loss of CNN at the ground truth is positive definite (PD) as long as the activation satisfies some properties in Section 4. Note that the Hessian of the squared loss at the ground truth can be trivially proved to be positive semidefinite (PSD), but only PSD-ness at the ground truth can’t guarantee convergence of most optimization algorithms like gradient descent. The proof for the PD-ness of Hessian at the ground truth is non-trivial. Actually we will give examples in Section 4 where the distilled properties are not satisfied and their Hessians are only PSD but not PD. Then given the PD-ness of population Hessian at the ground truth, we are able to show that the empirical Hessian at any fixed point that is close enough to the ground truth is also PD with high probability by using matrix Bernstein inequality and the distilled properties of activations. Then, in Section 5 we show gradient descent converges to the global optimal given an initialization that falls into the PD region. In Section 6, we provide existing guarantees for the initialization using tensor methods. Finally, we present some experimental results to verify our theory.

We show that the Hessian of the squared loss at a given point that is sufficiently close to the ground truth is positive definite with high probability(w.h.p.) when a sufficiently large number of samples are provided and the activation function satisfies some properties.

Given an initialization point that is sufficiently close to the ground truth, which can be obtained by tensor methods, we show that for smooth activation functions that satisfy the distilled properties, gradient descent converges to the ground truth parameters within $\epsilon$ precision using $O(\log(1/\epsilon))$ samples w.h.p.. To the best of our knowledge, this is the first time that recovery guarantees for non-overlapping CNNs with multiple kernels are provided.

Related Work

With the great success of neural networks, there is an increasing amount of literature that provides theoretical analysis and guarantees for NNs. Some of them measure the expressive power of NNs [CSS16, CS16, RPK+16, DFS16, PLR+16, Tel16] in order to explain the remarkable performance of NNs on complex tasks. Many other works try to handle the non-convexity of NNs by showing that the global optima or local minima close to the global optima will be achieved when the number of parameters is large enough [HV15, LSSS14, DPG+14, SS16, HM17]. However, such an over-parameterization will also overfit the training data easily and limit the generalization.

In this work, we consider parameter recovery guarantees, where the typical setting is to assume an underlying model and then try to recover the model. Once the parameters of the underlying model are recovered, generalization performance will also be guaranteed. Many non-convex problems, such as matrix completion/sensing [JNS13] and mixed linear regression [ZJD16], have nice recovery guarantees. Recovery guarantees for FCNNs have been studied in several works by different approaches. One of the approaches is tensor method [SA15, JSA15]. In particular, [SA15] guarantee to recover the subspace spanned by the weight matrix but no sample complexity is given, while [JSA15] provide the recovery of the parameters and require $O(d^{3}/\epsilon^{2})$ sample complexity. [Tia17b, Tia17a, ZSJ+17] consider the recovery of one-hidden-layer FCNNs using algorithms based on gradient descent. [Tia17b, Tia17a] provide recovery guarantees for one-hidden-layer FCNNs with orthogonal weight matrix and ReLU activations given infinite number of samples sampled from Gaussian distribution. [ZSJ+17] show the local strong convexity of the squared loss for one-hidden-layer FCNNs and use tensor method to initialize the parameters to the local strong convexity region followed by gradient descent that finally converges to the ground truth parameters. In this work, we consider the recovery guarantees for non-overlapping CNNs following the approach in [ZSJ+17].

There is little theoretical literature on CNNs. [CS16] consider the CNNs as generalized tensor decomposition and show the expressive power and depth efficiency of CNNs. [BG17] provide a globally converging guarantee of gradient descent on one-hidden-layer CNNs. [DLT17] eliminate the Gaussian input assumption and only require a weaker assumption on the inputs. However, 1) their analysis depends on $\mathsf{ReLU}$ activations, 2) they only consider one kernel. In this paper, we provide recovery guarantees for CNNs with multiple kernels and give sample complexity analysis. Moreover our analysis can be applied to a large range of activations including most commonly used activations. Another approach for CNNs that is worth mentioning is convex relaxation [ZLW17], where the class of CNN filters is relaxed to a reproducing kernel Hilbert space (RKHS). They show generalization error bound for this relaxation. However, to pair with RKHS, only several uncommonly used activations work for their analysis. Also, the learned function by convex relaxation is not the original CNN anymore.

Problem Formulation

By construction of $\{P_{i}\}_{i\in[r]}$, $P_{i}\cdot x$ and $P_{i^{\prime}}\cdot x$ $(i\neq i^{\prime})$ don’t have any overlap on the features of $x$. Throughout this paper, we assume the number of kernels $t$ is no more than the size of each patch, i.e., $t\leq k$. So by definition of $d$, $d\geq\max\{k,r,t\}$.

Given a distribution ${\cal D}$, we define the Expected Risk,

We calculate the gradient and the Hessian of $f_{\cal D}(W)$. The gradient and the Hessian of $\widehat{f}_{S}(W)$ are similar. For each $j\in[t]$, the partial gradient of $f_{\cal D}(W)$ with respect to $w_{j}$ can be represented as

For each $j\in[t]$, the second partial derivative of $f_{\cal D}(W)$ with respect to $w_{j}$ can be represented as

For each $j,l\in[t]$ and $j\neq l$, the second partial derivative of $f_{\cal D}(W)$ with respect to $w_{j}$ and $w_{l}$ can be represented as

For activation function $\phi(z)$, we define the following three properties. These properties are critical for the later analyses. The first two properties are related to the first derivative $\phi^{\prime}(z)$ and the last one is about the second derivative $\phi^{\prime\prime}(z)$.

The first derivative $\phi^{\prime}(z)$ is nonnegative and homogeneously bounded, i.e., $0\leq\phi^{\prime}(z)\leq L_{1}|z|^{p}$ for some constants $L_{1}>0$ and $p\geq 0$.

The second derivative $\phi^{\prime\prime}(z)$ is either (a) globally bounded $|\phi^{\prime\prime}(z)|\leq L_{2}$ for some constant $L_{2}$, i.e., $\phi(z)$ is $L_{2}$-smooth, or (b) $\phi^{\prime\prime}(z)=0$ except for $e$ ($e$ is a finite constant) points.

Note that these properties follow [ZSJ+17] with slight modification for $\rho(\sigma)$ and as shown in [ZSJ+17], most commonly used activations satisfy these properties, such as ReLU ($\phi(z)=\max\{z,0\},\rho(\sigma)=0.091$), leaky ReLU ($\phi(z)=\max\{z,0.01z\},\rho(\sigma)=0.089$), squared ReLU ($\phi(z)=\max\{z,0\}^{2},\rho(\sigma)=0.27\sigma^{2}$) and sigmoid ($\phi(z)=1/(1+e^{-z})^{2},\rho(1)=0.049$). Also note that when Property 3.3(b) is satisfied, i.e., the activation function is non-smooth, but piecewise linear, i.e., $\phi^{\prime\prime}(z)=0$ almost surely. Then the empirical Hessian exists almost surely for a finite number of samples.

Positive definiteness of Hessian Near the Ground Truth

In this section, we first show the eigenvalues of the Hessian at any fixed point that is close to the ground truth are lower bounded and upper bounded by two positives respectively w.h.p.. Then in the subsequent subsections, we present the main idea of the proofs step-by-step from special cases to general cases. Since we assume $t\leq k$, the following definition is well defined.

Note that $\kappa$ is the traditional condition number of $W^{*}$, while $\lambda$ is a more involved condition number of $W^{*}$. Both of them are $1$ if $W^{*}$ has orthonormal columns. $\rho(\sigma)$ is a number that is related to the activation function as defined in Property 3.2. Property 3.2 requires $\rho(\sigma_{t})>0$, which is important for the PD-ness of the Hessian. We will show a proof sketch in Sec. 10.

Then as long as we set $A$ such that $A=-A^{\top}$, we have $\langle A,\sum_{i=1}^{r}x_{i}x_{i}^{\top}\rangle=0$ for any $x$. Therefore, the smallest eigenvalue of the population Hessian at the ground truth for the quadratic activation function is zero. That is to say, the Hessian is only PSD but not PD. Also note that $\rho(\sigma)=0$ for the quadratic activation function. Therefore, Property 3.2 is important for the PD-ness of the Hessian.

Locally Linear Convergence of Gradient Descent

A caveat of Theorem 4.2 is that the lower and upper bounds of the Hessian only hold for a fixed $W$ given a set of samples. That is to say, given a set of samples, Eq (4) doesn’t hold for all the $W$’s that are close enough to the ground truth w.h.p. at the same time. So we want to point out that this theorem doesn’t indicate the classical local strong convexity, since the classical strong convexity requires all the Hessians at any point at a local area to be PD almost surely. Fortunately, our goal is to show the convergence of optimization methods and we can still show gradient descent converges to the global optimal linearly given a sufficiently good initialization.

Let $W$ be the current iterate satisfying $\|W-W^{*}\|\leq\operatorname{poly}(1/t,1/r,1/\lambda,1/\kappa,\rho/\sigma_{1}^{2p})\|W^{*}\|$.

Let $S$ denote a set of i.i.d. samples from distribution ${\cal D}$ (defined in (1)). Let the activation function satisfy Property 3.1,3.2 and 3.3(a). Define $m_{0}=\Theta(r\rho(\sigma_{t})/(\kappa^{2}\lambda))$ and $M_{0}=\Theta(tr^{2}\sigma_{1}^{2p})$. For any $s\geq 1$, if we choose $|S|\geq d\cdot\operatorname{poly}(s,t,\log d,\tau,\kappa,\lambda,\sigma_{1}^{2p}/\rho)$ and perform gradient descent with step size $1/M_{0}$ on $\widehat{f}_{S}(W)$ and obtain the next iterate, $\widetilde{W}=W-\frac{1}{M_{0}}\nabla\widehat{f}_{S}(W),$ then with probability at least $1-d^{-\Omega(s)}$,

To show the linear convergence of gradient descent for one iteration, we need to show that all the Hessians along the line between the current point to the optimal point are PD, which can’t be satisfied by simple union bound, since there are infinite number of Hessians. Our solution is to set a finite number of anchor points that are equally distributed along the line, whose Hessians can be shown to be PD w.h.p. using union bound. Then we show all the points between two adjacent anchor points have PD Hessians, since these points are much closer to the anchor points than to the ground truth. The proofs are postponed to Appendix D.4.2.

Note that this theorem holds only for one iteration. For multiple iterations, we need to do resampling at each iteration. However, since the number of iterations required to achieve $\epsilon$ precision is $O(\log(1/\epsilon))$, the number of samples required is also proportional to $\log(1/\epsilon)$.

Initialization by Tensor Method

It is known that most tensor problems are NP-hard [Hås90, HL13] or even hard to approximate [SWZ17]. Tensor decomposition method becomes efficient [AGH+14, WTSA15, WA16, SWZ16] under some assumptions. Similarly as in [ZSJ+17], we utilize the noiseless assumption and Gaussian inputs assumption to show a provable and efficient tensor methods.

We denote $\overline{w}=w/\|w\|$ and $x_{i}=P_{i}\cdot x$. For each $i\in[r]$, we can calculate the second-order and third-order moments,

For simplicity, we assume $\gamma_{2}(\|w_{j}^{*}\|)\neq\gamma_{0}(\|w_{j}^{*}\|)$ and $\gamma_{3}(\|w_{j}^{*}\|)\neq 3\gamma_{1}(\|w_{j}^{*}\|)$ for any $j\in[t]$, then $M_{i,2}\neq 0$ and $M_{i,3}\neq 0$. Note that when this assumption doesn’t hold, we can seek for higher-order moments and then degrade them to second-order moments or third-order moments. Now we can use non-orthogonal tensor decomposition [KCL15] to decompose the empirical version of $M_{i,3}$ and obtain the estimation of $w_{j}^{*}$ for $j\in[t]$. According to [ZSJ+17], from the empirical version of $M_{i,2}$ and $M_{i,3}$, we are able to estimate $W^{*}$ to some precision.

Therefore, setting $\epsilon=\rho(\sigma_{t})^{2}/\operatorname{poly}(t,\kappa,\lambda)$, $W^{(0)}$ will satisfy the initialization condition in Theorem 5.1.

Global Convergence Guarantee

In this section, we can show the global convergence of gradient descent initialized by tensor method (Algorithm 1) by combining the local convergence of gradient descent Theorem 5.1 and the tensor initialization guarantee Theorem 6.1.

with probability at least $1-d^{-\Omega(s)}$.

Experimental Results

In our first experiment, we show that the minimal eigenvalues of Hessians at the the ground truth for different number of samples and different activation functions. As we can see from Fig. 1(a), The minimal eigenvalues using ReLU, squared ReLU and sigmoid activations are positive, while the minimal eigenvalue of Hessian using quadratic activation is zero. Note that we use log scale for y-axis. Also, we can see when the sample size increases the minimal eigenvalues converges to the minimal eigenvalue of the population Hessian.

In the second experiment, we demonstrate how gradient descent converges. We use squared ReLU as an example, pick stepsize $\eta=0.01$ for gradient descent and set $n=1000$. In the experiments, we don’t do the resampling for each iteration since the algorithm still works well without resampling. The results are shown in Fig. 1(b), where different lines use different initializations sampled from normal distribution. The common properties of all the lines are that 1) they converge to the global optimal; 2) they have linear convergence rate when the objective value is close to zero, which verifies Theorem 5.1.

Conclusion

In this work, we show that the local strong convexity of the squared loss for non-overlapping CNNs with multiple filters when the activation function satisfies some mild properties. We then show gradient descent has local linear convergence rate and tensor methods are able to initialize the parameters to the local strong convexity region. Therefore, the ground truth parameters are guaranteed to be recovered in polynomial time for non-overlapping CNNs. The current no-overlap assumption is strong and we leave removing this as future work.

Proof Sketch

In this section, we briefly give the proof sketch for the local strong convexity. The main idea is first to bound the range of the eigenvalues of the population Hessian $\nabla^{2}f_{\cal D}(W^{*})$ and then bound the spectral norm of the remaining error, $\|\nabla^{2}\widehat{f}_{S}(W)-\nabla^{2}f_{\cal D}(W^{*})\|$. The later can be bounded by mainly applying matrix Bernstein inequality and Property 3.1, 3.3 carefully. In Sec. 10.1, we show that when Property 3.2 is satisfied, $\nabla^{2}f_{\cal D}(W^{*})$ for orthogonal $W^{*}$ with $k=t$ can be lower bounded. Sec. 10.2 shows how to reduce the case of a non-orthogonal $W^{*}$ with $k\geq t$ to the orthogonal case with $k=t$. The upper bound is relatively easier, so we leave those proofs in Appendix D. In Sec. 10.3, we will show that the vanilla matrix Bernstein inequality is not applicable in our case and we introduce a modified matrix Bernstein inequality.

The last formulation Eq. (8) has a unit independent element $u_{j}$ in $\phi^{\prime}(\cdot)$, thus can be calculated explicitly by defining some quantities. In particular, we can obtain the following lower bounded for Eq. (8).

Note that the definition of $\widehat{\rho}$ contains two elements of the definition of $\rho(1)$ in Property 3.2. Therefore, if $\rho(1)>0$, we also have $\widehat{\rho}>0$. More detailed proofs for the orthogonal case can be found in Appendix D.1.1.

2 Non-orthogonal weight matrices for the population case

In this section, we show how to reduce the minimal eigenvalue problem with a non-orthogonal weight matrix into a problem with an orthogonal weight matrix, so that we can use the results in Sec. 10.1 to lower bound the eigenvalues.

Similar to the steps in Eq. (7) and Eq. (8), we have

Since $g(w_{i}^{*})\propto w_{i}^{*}$ and $U_{\perp}^{\top}x$ is independent of $\phi^{\prime}(w_{i}^{*\top}x)$, we have $C_{3}=0$. $C_{1}$ can be lower bounded by the orthogonal case with a loss of a condition number of $W^{*}$, $\lambda$, as follows.

The last formulation is the orthogonal weight case in Eq. (8) in Sec. 10.1. So we can lower bound it by Lemma 10.1. The intermediate steps for the derivation of the above inequalities and the lower bound for $C_{2}$ can be found in Appendix D.1.2.

3 Matrix Bernstein inequality

In our proofs we need to bound the difference between some population Hessians and their empirical versions. Typically, the classic matrix Bernstein inequality Lemma 10.2 (Theorem 6.1 in [Tro12]) requires the norm of the random matrix be bounded almost surely or the random matrix satisfies subexponential property (Theorem 6.2 in [Tro12]) .

The function $h(u):=(1+u)\log(1+u)-u$ for $u\geq 0$.

However, in our cases, most of the random matrices don’t satisfy these conditions. So we derive the following lemma that can deal with random matrices that are not bounded almost surely or follow subexponential distribution, but bounded with high probability.

Then we have for any $0<\epsilon<1$ and $t\geq 1$, if $\gamma\leq(\epsilon\|\overline{B}\|/(2L))^{2}$ and

then, with probability at least $1-d^{-2t}-n\gamma$,

References

Appendix

Appendix A Notation

We provide several definitions related to matrix $A$. Let $\det(A)$ denote the determinant of a square matrix $A$. Let $A^{\top}$ denote the transpose of $A$. Let $A^{\dagger}$ denote the Moore-Penrose pseudoinverse of $A$. Let $A^{-1}$ denote the inverse of a full rank square matrix. Let $\|A\|_{F}$ denote the Frobenius norm of matrix $A$. Let $\|A\|$ denote the spectral norm of matrix $A$. Let $\sigma_{i}(A)$ to denote the $i$-th largest singular value of $A$.

For any function $f$, we define $\widetilde{O}(f)$ to be $f\cdot\log^{O(1)}(f)$. In addition to $O(\cdot)$ notation, for two functions $f,g$, we use the shorthand $f\lesssim g$ (resp. $\gtrsim$) to indicate that $f\leq Cg$ (resp. $\geq$) for an absolute constant $C$. We use $f\eqsim g$ to mean $cf\leq g\leq Cf$ for constants $c,C$.

Appendix B Preliminaries

This section provides some elementary facts, tools or some lemmas from existing papers.

We provide some facts that will be used in the later proofs.

Let $z$ denote a fixed $d$-dimensional vector, then for any $C\geq 1$ and $n\geq 1$, we have

Part (\@slowromancapii@). We first show how to lower bound $\sigma_{k}(\overline{W})$,

It remains to upper bound $\sigma_{1}(\overline{W})$,

Since all the three components $|u^{\top}x|$, $|v^{\top}x|$, $|w^{\top}x|$ are positive and related to a common random vector $x$, we can show a lower bound,

B.2 Matrix Bernstein inequality

Appendix C Properties of Activation Functions

We can easily verify that $\mathsf{ReLU}$ , leaky $\mathsf{ReLU}$ and squared $\mathsf{ReLU}$ satisfy Property 3.2 by calculating $\rho(\sigma)$ in Property 3.2, which is shown in Table 1. Property 3.1 for $\mathsf{ReLU}$ , leaky $\mathsf{ReLU}$ and squared $\mathsf{ReLU}$ can be verified since they are non-decreasing with bounded first derivative. $\mathsf{ReLU}$ and leaky $\mathsf{ReLU}$ are piece-wise linear, so they satisfy Property 3.3(b). Squared $\mathsf{ReLU}$ is smooth so it satisfies Property 3.3(a).

The equality in the first inequality happens when $\phi^{\prime}(\sigma\cdot z)$ is a constant a.e.. The equality in the second inequality happens when $|\phi^{\prime}(\sigma\cdot z)|$ is a constant a.e., which is invalidated by the non-linearity and smoothness condition. The equality in the third inequality holds only when $\phi^{\prime}(z)=0$ a.e., which leads to a constant function under non-decreasing condition. $\alpha_{0}=0$ if only if $\phi^{\prime}(z)=0$ almost surely, since $\phi^{\prime}(z)\geq 0$. Therefore, $\rho(\sigma)>0$ for any smooth non-decreasing non-linear activations with bounded symmetric first derivatives. ∎

Appendix D Positive Definiteness of Hessian near the Ground Truth

The goal of this section is to prove Lemma D.1.

This follows by combining Lemma D.4 and Lemma D.5. ∎

First, we can rewrite the term $C$ in the following way,

Further, we can rewrite the diagonal term in the following way,

We can rewrite the off-diagonal term in the following way,

where the first step follows by $B=B_{1}+B_{2}+B_{3}$, and the second step follows by the definition of $A,B_{1},B_{2},B_{3},C$ the third step follows by $A+B_{1}+B_{2}+B_{3}-C=C_{1}+C_{2}+C_{3}+C_{4}$, the fourth step follows by $C_{1},C_{2}\geq 0$, the fifth step follows $a\geq\min(a,b)$, the sixth step follows by $\|\operatorname{diag}(P)\|^{2}=\|\operatorname{diag}(\operatorname{diag}(P))\|_{F}^{2}$, the seventh step follows by triangle inequality, and the last step follows the definition of $\rho$. ∎

$A+B_{1}+B_{2}+B_{3}-C=C_{1}+C_{2}+C_{3}+C_{4}$.

The key properties we need are, for two vectors $a,b$, $\|a+b\|^{2}=\|a\|^{2}+2\langle a,b\rangle+\|b\|^{2}$; for two matrices $A,B$, $\|A+B\|_{F}^{2}=\|A\|_{F}^{2}+2\langle A,B\rangle+\|B\|_{F}^{2}$. Then, we have

where the second step follows by $\langle P,\operatorname{diag}(\operatorname{diag}(P))\rangle=\|\operatorname{diag}(P)\|^{2}$ and $\|\operatorname{diag}(\operatorname{diag}(P))\|_{F}^{2}=\|\operatorname{diag}(P)\|^{2}$. ∎

D.1.2 Lower bound on the eigenvalues of the population Hessian at the ground truth

If $\phi(z)$ satisfies Property 3.1, 3.2, 3.3 we have

For each $j,l,\in[t]$ and $j\neq l$, the second partial derivative of $f_{\cal D}(W)$ with respect to $w_{j}$ and $w_{l}$ can be represented as

First we show the lower bound of the eigenvalues. The main idea is to reduce the problem to a $k$-by-$k$ problem and then lower bound the eigenvalues using orthogonal weight matrices.

Then, we can analyze the smallest eigenvalue of the Hessian in the following way,

Since $\min_{\|a\|=1}\sum_{i=1}^{r}f_{i}(a)\geq\sum_{i=1}^{r}\min_{\|a\|=1}f_{i}(a)$. Thus, we only need to consider one $i\in[r]$,

where the second step follows by definition of function $h_{i}(y)$,

We calculate $A,B,C$ separately. First, we can show

where the first step follows by definition of $A$ and the last step follows by $U^{\top}g(w_{i}^{*})=\widehat{g}(v_{i}^{*})$.

Third, we have $C=0$ since $U_{\perp}^{\top}x$ is independent of $w_{i}^{*\top}x$ and $U^{\top}x$, and $g(w^{*})\propto w^{*}$, then $U_{\perp}^{\top}g(w^{*})=0$.

Note that $\phi^{\prime}(\sigma_{t}\cdot u_{i})$’s are independent of each other, so we can simplify the analysis.

In particular, Lemma D.2 gives a lower bound in this case in terms of $p_{i}$. Note that $\|p_{i}\|\geq\|b_{i}\|/\kappa$. Therefore,

For $B$, similar to the proof of Lemma 10.1, we have,

Note that $1=\|a\|^{2}=\|b\|^{2}+\|c\|^{2}$. Thus, we finish the proof for the lower bound. ∎

D.1.3 Upper bound on the eigenvalues of the population Hessian at the ground truth

If $\phi(z)$ satisfies Property 3.1, 3.2, 3.3, then

Similarly to the proof in previous section, we can calculate the upper bound of the eigenvalues by

It remains to bound $A_{j,i,j^{\prime},i^{\prime}}$. We have

D.2 Error bound of Hessians near the ground truth for smooth activations

The goal of this Section is to prove Lemma D.6

then we have, with probability at least $1-1/d^{\Omega(s)}$,

This follows by combining Lemma D.8 and Lemma D.13 directly. ∎

The goal of this Section is to prove Lemma D.8.

Note that if $\|W-W^{*}\|\leq\sigma_{t}(W^{*})/2$, we have $\sigma_{t}(W^{*})/2\leq\sigma_{i}(W)\leq\frac{3}{2}\sigma_{1}(W^{*})$ for all $i\in[t]$ by Weyl’s inequality. By definition of singular value, we have $\sigma_{t}(W^{*})\leq\|w_{i}^{*}\|\leq\sigma_{1}(W^{*})$. By definition of spectral norm, we have $\|w_{i}-w_{i}^{*}\|\leq\|W-W^{*}\|$. Thus, we can lower bound $\|w_{i}\|$,

Similarly, we have $\|w_{i}\|\geq\frac{1}{2}\|w_{i}^{*}\|$. ∎

Using Claim D.9 and Claim D.10, we can bound $\Delta_{j,l}^{(1)}$ and $\Delta_{j,l}^{(2)}$.

where the first step follows by $\nabla^{2}f_{\operatorname*{\mathcal{D}}}(W)-\nabla^{2}f_{\operatorname*{\mathcal{D}}}(W^{*})$, the second step follows by the definition of $y$.

Using Claim D.11, we can bound $\Delta_{j,j}^{(1)}$. Using Claim D.12, we can bound $\Delta_{j,j}^{(2)}$.

Putting it all together, we can bound the error by

For each $(j,l)\in[t]\times[t]$ and $j\neq l$, $\|\Delta_{j,l}^{(1)}\|\lesssim r^{2}L_{1}L_{2}\sigma_{1}^{p}(W^{*})\|W-W^{*}\|.$

Recall the definition of $\Delta_{j,l}^{(1)}$,

In order to upper bound $\|\Delta_{j,l}^{(1)}\|$, it suffices to upper bound the spectral norm of this quantity,

We can upper bound the first term of above Equation in the following way,

Similarly, we can upper bound the second term. By summing over $O(r^{2})$ terms, we complete the proof. ∎

For each $(j,l)\in[t]\times[t]$ and $j\neq l$, $\|\Delta_{j,l}^{(2)}\|\lesssim r^{2}L_{1}L_{2}\sigma_{1}^{p}(W^{*})\|W-W^{*}\|.$

We consider the first term as follows. The second term is similar.

By summing over $O(r^{2})$ terms, we complete the proof. ∎

For each $j\in[t]$, $\|\Delta_{j,j}^{(1)}\|\lesssim r^{2}tL_{1}L_{2}\sigma_{1}^{p}(W^{*})\|W-W^{*}\|.$

Recall the definition of $\Delta_{j,j}^{(1)}$,

In order to upper bound $\|\Delta_{j,j}^{(1)}\|$, it suffices to upper bound the spectral norm of this quantity,

By summing over all the $O(tr^{2})$ terms and using triangle inequality, we finish the proof. ∎

For each $j\in[t]$, $\|\Delta_{j,j}^{(2)}\|\lesssim r^{2}tL_{1}L_{2}\sigma_{1}^{p}(W^{*})\|W-W^{*}\|.$

Recall the definition of $\Delta_{j,j}^{(2)}$,

In order to upper bound $\|\Delta_{j,j}^{(2)}\|$, it suffices to upper bound the spectral norm of these two quantities, the diagonal term

These two terms can be bounded by using the proof similar to the other Claims of this Section. ∎

D.2.2 Empirical and population difference for smooth activations

Note that Bernstein inequality requires the spectral norm of each random matrix to be bounded almost surely. However, since we assume Gaussian distribution for $x$, $\|x\|^{2}$ is not bounded almost surely. The main idea is to do truncation and then use Matrix Bernstein inequality. Details can be found in Lemma 10.3 and Corollary B.5.

then we have, with probability at least $1-1/d^{\Omega(s)}$,

Define $\Delta=\nabla^{2}f_{\operatorname*{\mathcal{D}}}(W)-\nabla^{2}\widehat{f}_{S}(W)$. Let us first consider the diagonal blocks. Define

Further, we can decompose $\Delta_{j,j}$ into $\Delta_{j,j}=\Delta_{j,j}^{(1)}+\Delta_{j,j}^{(2)}$, where

Note that $\Delta_{j,j}^{(2)}$ is a special case of $\Delta_{j,l}$ so we just bound $\Delta_{j,l}$. Combining Claims D.14 D.15, and taking a union bound over $t^{2}$ different $\Delta_{j,l}$, we obtain if $n\geq\epsilon^{-2}k\tau\kappa^{2}\operatorname{poly}(\log d,s)$, with probability at least $1-1/d^{4s}$,

For each $j\in[t]$, if $|S|\geq k\operatorname{poly}(\log d,s)$

Using Properties 3.1,3.2 and 3.3(a), we have for each $x\in S$, for each $(i,i^{\prime})\in[r]\times[r]$,

(\@slowromancapi@) Bounding $|h_{l}(x)|$.

According to Fact B.1, we have for any constant $s\geq 1$, with probability $1-1/(nd^{8s})$,

(\@slowromancapii@) Bounding $\|\overline{B}_{l}\|$.

where the first step follows by definition of spectral norm, and last step follows by Fact B.4. Using Fact B.4, we can also prove an upper bound $\|\overline{B}_{l}\|$, $\|\overline{B}_{l}\|\lesssim L_{1}L_{2}\|w_{l}\|^{p}\|w_{l}-w_{l}^{*}\|$.

By applying Corollary B.5, for each $(i,i^{\prime})\in[r]\times[r]$ if $n\geq\epsilon^{-2}k\operatorname{poly}(\log d,s)$, then with probability $1-1/d^{8s}$,

For each $(j,l)\in[t]\times[t]$, $j\neq l$, if $|S|\geq\epsilon^{-2}k\tau\kappa^{2}\operatorname{poly}(\log d,s)$

To apply Lemma 10.3, we show the following.

By using Fact B.1,B.2, we have with probability $1-1/nd^{4s}$,

Obviously, $A_{1}\geq 0$. For the term $A_{2}$, we have

Therefore, applying Lemma 10.3, if $|S|\geq\epsilon^{-2}\kappa^{2}\tau k\operatorname{poly}(\log d,s)$ we have

holds with probability at least $1-1/d^{\Omega(s)}$. ∎

For each $j\in[t]$, if $|S|\geq\epsilon^{-2}k\tau\kappa^{2}\operatorname{poly}(\log d,s)$

D.3 Error bound of Hessians near the ground truth for non-smooth activations

The goal of this Section is to prove Lemma D.17,

with probability at least $1-1/d^{\Omega(s)}$,

As we noted previously, when Property 3.3(b) holds, the diagonal blocks of the empirical Hessian can be written as, with probability 1, for all $j\in[t]$,

We also know that, for each $(j,l)\in[t]\times[t]$ and $j\neq l$,

Recall the definition of $\nabla^{2}f_{\operatorname*{\mathcal{D}}}(W^{*})$, for each $j\in[t]$, the diagonal block is

For each $j,l,\in[t]$ and $j\neq l$, the off-diagonal block is

where the second step follows by triangle inequality, the third step follows by Lemma D.18 and Lemma D.19. ∎

If $|S|\geq\epsilon^{-2}k\tau\kappa^{2}\operatorname{poly}(\log d,s)$, then we have

Using Claim D.15, we can bound the spectral norm of all the off-diagonal blocks, and using Claim D.16, we can bound the spectral norm of all the diagonal blocks. ∎

This follows by using the similar technique from [ZSJ+17]. Let $\Delta=H_{\operatorname*{\mathcal{D}}}(W)-\nabla^{2}f_{\operatorname*{\mathcal{D}}}(W^{*})$. For each $j\in[t]$, the diagonal block is,

For each $(j,l)\in[t]\times[t]$ and $j\neq l$, the off-diagonal block is,

Applying Claim D.20 and D.21 completes the proof. ∎

where the first step follows by definition of spectral norm, the second step follows by triangle inequality, and the last step follows by linearity of expectation.

where the first step follows by $a=Ub+U_{\bot}c$, the last step follows by $(a+b)^{2}\leq 2a^{2}+2b^{2}$. Let’s consider the first term. The second term is similar.

By Property 3.3(b), we have $e$ exceptional points which have $\phi^{\prime\prime}(z)\neq 0$. Let these $e$ points be $p_{1},p_{2},\cdots,p_{e}$. Note that if $v_{j}^{\top}z$ and $v_{j}^{*\top}z$ are not separated by any of these exceptional points, i.e., there exists no $j\in[e]$ such that $v_{i}^{\top}z\leq p_{j}\leq v_{j}^{*\top}z$ or $v_{j}^{*\top}z\leq p_{j}\leq v_{j}^{\top}z$, then we have $\phi^{\prime}(v_{j}^{\top}z)=\phi^{\prime}(v_{j}^{*\top}z)$ since $\phi^{\prime\prime}(s)$ are zeros except for $\{p_{j}\}_{j=1,2,\cdots,e}$. So we consider the probability that $v_{j}^{\top}z,v_{j}^{*\top}z$ are separated by any exception point. We use $\xi_{j}$ to denote the event that $v_{j}^{\top}z,v_{j}^{*\top}z$ are separated by an exceptional point $p_{j}$. By union bound, $1-\sum_{j=1}^{e}\Pr{\xi_{j}}$ is the probability that $v_{j}^{\top}z,v_{j}^{*\top}z$ are not separated by any exceptional point. The first term of Equation (D.20) can be bounded as,

where the first step follows by if $v_{j}^{\top}z,v_{j}^{*\top}z$ are not separated by any exceptional point then $\phi^{\prime}(v_{j}^{\top}z)=\phi^{\prime}(v_{j}^{*\top}z)$ and the last step follows by Hölder’s inequality and Property 3.1.

It remains to upper bound $\Pr_{z\sim\operatorname*{\mathcal{D}}_{3}}[\xi_{j}]$. First note that if $v_{j}^{\top}z,v_{j}^{*\top}z$ are separated by an exceptional point, $p_{j}$, then $|v_{j}^{*\top}z-p_{j}|\leq|v_{j}^{\top}z-v_{j}^{*\top}z|\leq\|v_{j}-v_{j}^{*}\|\|z\|$. Therefore,

Note that $(\frac{v_{j}^{*\top}z}{\|z\|\|v_{j}^{*}\|}+1)/2$ follows Beta(1,1) distribution which is uniform distribution on $$.

where the first step is because we can view $\frac{v_{j}^{*\top}z}{\|z\|}$ and $\frac{p_{j}}{\|z\|}$ as two independent random variables: the former is about the direction of $z$ and the later is related to the magnitude of $z$. Thus, we have

We bound $\|\Delta_{j,l}^{(2)}\|$. $\|\Delta_{j,j}^{(2)}\|$ is a special case of $\|\Delta_{j,l}^{(2)}\|$.

where the last inequality uses the same analysis in Claim D.20. ∎

D.4 Main results

The goal of this Section is to prove Theorem D.22

then with probability at least $1-d^{-\Omega(s)}$,

The main idea of the proof follows the following inequalities,

We first provide lower bound and upper bound for the range of the eigenvalues of $\nabla^{2}f_{\cal D}(W^{*})$ by using Lemma D.1. Then we show how to bound the spectral norm of the remaining error, $\|\nabla^{2}\widehat{f}_{S}(W)-\nabla^{2}f_{\operatorname*{\mathcal{D}}}(W^{*})\|$. $\|\nabla^{2}\widehat{f}_{S}(W)-\nabla^{2}f_{\operatorname*{\mathcal{D}}}(W^{*})\|$ can be further decomposed into two parts, $\|\nabla^{2}\widehat{f}_{S}(W)-H_{\operatorname*{\mathcal{D}}}(W)\|$ and $\|H_{\operatorname*{\mathcal{D}}}(W)-\nabla^{2}f_{\operatorname*{\mathcal{D}}}(W^{*})\|$, where $H_{\operatorname*{\mathcal{D}}}(W)$ is $\nabla^{2}f_{\cal D}(W)$ if $\phi$ is smooth, otherwise $H_{\operatorname*{\mathcal{D}}}(W)$ is a specially designed matrix . We can upper bound them when $W$ is close enough to $W^{*}$ and there are enough samples. In particular, if the activation satisfies Property 3.3(a), we use Lemma D.8 to bound $\|H_{\operatorname*{\mathcal{D}}}(W)-\nabla^{2}f_{\cal D}(W^{*})\|$ and Lemma D.13 to bound $\|H_{\operatorname*{\mathcal{D}}}(W)-\nabla^{2}\widehat{f}_{S}(W)\|$. If the activation satisfies Property 3.3(b), we use Lemma D.19 to bound $\|H_{\operatorname*{\mathcal{D}}}(W)-\nabla^{2}f_{\cal D}(W^{*})\|$ and Lemma D.18 to bound $\|H_{\operatorname*{\mathcal{D}}}(W)-\nabla^{2}\widehat{f}_{S}(W)\|$.

Finally we can complete the proof by setting $\epsilon=O(\rho(\sigma_{1})/(r^{2}t^{2}\kappa^{2}\lambda\sigma_{1}^{2p}))$ in Lemma D.6 and Lemma D.17.

If the activation satisfies Property 3.3(a), we set $\|W-W^{*}\|\lesssim\rho(\sigma_{t})/(rt\kappa^{2}\lambda\sigma_{1}^{p})$ in Lemma D.6.

If the activation satisfies Property 3.3(b), we set $\|W-W^{*}\|\lesssim\rho^{2}(\sigma_{t})\sigma_{t}/(r^{2}t^{2}\kappa^{4}{\lambda}^{2}\sigma_{1}^{4p})$ in Lemma D.17. ∎

D.4.2 Linear convergence of gradient descent

The goal of this Section is to prove Theorem D.23.

Let $S$ denote a set of i.i.d. samples from distribution ${\operatorname*{\mathcal{D}}}$ (defined in (1)). Let the activation function satisfy Property 3.1,3.2 and 3.3(a). Define

and perform gradient descent with step size $1/M_{0}$ on $\widehat{f}_{S}(W)$ and obtain the next iterate,

then with probability at least $1-d^{-\Omega(s)}$,

Given a current iterate $W$, we set $k^{(p+1)/2}$ anchor points $\{W^{a}\}_{a=1,2,\cdots,k^{(p+1)/2}}$ equally along the line $\xi W^{*}+(1-\xi)W$ for $\xi\in$. Using Theorem D.22, and applying a union bound over all the events, we have with probability at least $1-d^{-\Omega(s)}$ for all anchor points $\{W^{a}\}_{a=1,2,\cdots,k^{(p+1)/2}}$, if $|S|$ satisfies Equation (18), then

Then based on these anchors, using Lemma D.24 we have with probability $1-d^{-\Omega(s)}$, for any points $W$ on the line between $W$ and $W^{*}$,

where the third equality holds by setting $\eta=1/M_{0}$. ∎

D.4.3 Bounding the spectrum of the Hessian near the fixed point

The goal of this Section is to prove Lemma D.24.

For each $j,l\in[t]$ and $j\neq l$, we use $\Delta_{j,l}$ to denote the off-diagonal block,

For each $j\in[t]$, we use $\Delta_{j,j}$ to denote the diagonal block,

We further decompose $\Delta_{j,j}$ into $\Delta_{j,j}=\Delta_{j,j}^{(1)}+\Delta_{j,j}^{(2)}$, where

Combining Claims D.25, D.26, D.28 D.27 and taking a union bound over $O(t^{2})$ events, we have

holds with probability at least $1-d^{-\Omega(s)}$. ∎

For each $j\in[t]$, if $|S|\geq k\operatorname{poly}(\log d,s)$, then

holds with probability $1-d^{-\Omega(s)}$.

Recall the definition $\Delta_{j,j}^{(1,1)}$,

In order to upper bound $\|\Delta_{j,j}^{(1,1)}\|$, it suffices to upper bound the spectral norm of

We focus on the case for $i=i^{\prime}$. The case for $i\neq i^{\prime}$ is similar. Note that

By Fact B.2, we have $h(x)\lesssim(sk\log dn)^{(p+1)/2}$ with probability at least $1-1/(nd^{4s})$.

with probability at least $1-1/d^{\Omega(s)}$,

Therefore we have with probability at least $1-1/d^{\Omega(s)}$,

For each $j\in[t]$, if $|S|\geq k\operatorname{poly}(\log d,s)$, then

holds with probability $1-d^{-\Omega(s)}$.

Recall the definition of $\Delta_{j,l}^{(1,2)}$,

In order to upper bound $\|\Delta_{j,l}^{(1,2)}\|$, it suffices to upper bound the spectral norm of this quantity,

Using Property 3.3, we have $(|\phi^{\prime\prime}(w_{j}^{a^{\top}}z)|+|\phi^{\prime\prime}(w_{j}^{\top}z)|)\leq 2L_{2}$. Thus, $h(y,z)\leq 2L_{1}L_{2}|(w_{l}^{a}-w_{l}^{*})^{\top}y|\cdot(|w_{l}^{a\top}y|^{p}+|w_{l}^{*\top}y|^{p})$.

Using Fact B.1, matrix Bernstein inequality Corollary B.5, we have, if $|S|\geq k\operatorname{poly}(\log d,s)$,

where $S$ denote a set of samples from distribution $D_{2k}$. Thus, we obtain

Taking the union bound over $O(tr^{2})$ events, summing up those $O(tr^{2})$ terms completes the proof. ∎

For each $(j,l)\in[t]\times[t]$ and $j\neq l$, if $|S|\geq k\operatorname{poly}(\log d,s)$, then

holds with probability $1-d^{-\Omega(s)}$.

We can lower and upper bound the above term by

By using Fact B.2, we have with probability $1-1/nd^{4s}$,

The upper bound can be obtained similarly,

Using Fact B.1 and matrix Bernstein inequality Lemma 10.3, we have, if $|S|\geq rk\operatorname{poly}(\log d,s)$, with probability at least $1-1/d^{\Omega(s)}$,

For each $j\in[t]$, if $|S|\geq k\operatorname{poly}(\log d,s)$, then

holds with probability $1-d^{-\Omega(s)}$.

$\Delta_{j,j}^{(2)}$ is a special case of $\Delta_{j,l}$, so we refer readers to the proofs in Claim D.27. ∎

Appendix E Acknowledgments

The authors would like to thank Peter L. Bartlett, Surbhi Goel, Prateek Jain, Adam Klivans, Qi Lei, Eric Price, David P. Woodruff, Lin Yang, Peilin Zhong, Hongyang Zhang and Jiong Zhang for useful discussions.