summaries: This paper studies the problem of learning the parameter of one hidden layer neural network with sigmoid activation function based on the negative log likelihood loss. The authors consider the teacher network setting with Gaussian input, and show that gradient descent can recover the teacher network’s parameter up to certain statistical accuracy when the initialization is sufficiently close to the true parameter. The main contribution of this paper is that the authors consider the classification problem with negative log likelihood loss, and provide the local convergence result for gradient descent. However, based on the previous results in Mei et al., 2016 and Zhong et al., 2017, this work is incremental, and current results in this paper is not strong enough. To be more specific, the paper has the following weaknesses:

summaries: This paper studies the problem of recovering a true underlying neural network (assuming there exists one) with cross-entropy loss. This paper shows if the input is standard Gaussian, within a small ball around the ground truth, the objective function is strongly convex and smooth if there is a sufficiently large number of samples. Furthermore, the global minimizer is actually the true neural network. This geometric analysis implies applying gradient descent within this neighborhood, one can recover the underlying neural network. This paper also proposed a provable method based on spectral learning to find a good initialization point. Lastly, this paper also provides some simulation studies.

abstractText: We study model recovery for data classification, where the training labels are generated from a one-hidden-layer fully-connected neural network with sigmoid activations, and the goal is to recover the weight vectors of the neural network. We prove that under Gaussian inputs, the empirical risk function using cross entropy exhibits strong convexity and smoothness uniformly in a local neighborhood of the ground truth, as soon as the sample complexity is sufficiently large. This implies that if initialized in this neighborhood, which can be achieved via the tensor method, gradient descent converges linearly to a critical point that is provably close to the ground truth without requiring a fresh set of samples at each iteration. To the best of our knowledge, this is the first global convergence guarantee established for the empirical risk minimization using cross entropy via gradient descent for learning one-hidden-layer neural networks, at the near-optimal sample and computational complexity with respect to the network input dimension.

title: Universal approximation bounds for superpositions of a sigmoidal function

venue: IEEE Transactions on Information theory,

authors:
Peter L Bartlett
Dylan J Foster
Matus J Telgarsky

title: Spectrally-normalized margin bounds for neural networks

venue: In Advances in Neural Information Processing Systems,

authors:
Srinadh Bhojanapalli
Behnam Neyshabur
Nati Srebro

title: Global optimality of local search for low rank matrix recovery

authors:
Digvijay Boob
Guanghui Lan

title: Theoretical properties of the global optimizer of two layer neural network

venue: arXiv preprint arXiv:1710.11241,

authors:
Alon Brutzkus
Amir Globerson

title: Globally optimal gradient descent for a convnet with gaussian inputs

venue: arXiv preprint arXiv:1702.07966,

authors:
Alon Brutzkus
Amir Globerson
Eran Malach
Shai Shalev-Shwartz

title: Sgd learns overparameterized networks that provably generalize on linearly separable data

venue: arXiv preprint arXiv:1710.10174,

authors:
E.J. Candès
X. Li
M. Soltanolkotabi

title: Phase retrieval via Wirtinger flow: Theory and algorithms

venue: IEEE Transactions on Information Theory,

title: Approximation by superpositions of a sigmoidal function

venue: Mathematics of control, signals and systems,

authors:
Yann N Dauphin
Razvan Pascanu
Caglar Gulcehre
Kyunghyun Cho
Surya Ganguli
Yoshua Bengio

title: Identifying and attacking the saddle point problem in high-dimensional non-convex optimization

venue: In Advances in neural information processing systems,

authors:
Simon S Du
Jason D Lee
Yuandong Tian

title: When is a convolutional filter easy to learn

venue: arXiv preprint arXiv:1709.06129,

authors:
Simon S Du
Jason D Lee
Yuandong Tian
Barnabas Poczos
Aarti Singh

title: Gradient descent learns one-hidden-layer cnn: Don’t be afraid of spurious local minima

venue: arXiv preprint arXiv:1712.00779,

authors:
Soheil Feizi
Hamid Javadi
Jesse Zhang
David Tse

title: Porcupine neural networks:(almost) all local optima are global

venue: arXiv preprint arXiv:1710.02196,

authors:
Rong Ge
Tengyu Ma

title: On the optimization landscape of tensor decompositions

venue: arXiv preprint arXiv:1706.05598,

authors:
Rong Ge
Jason D Lee
Tengyu Ma

title: Matrix completion has no spurious local minimum

title: Learning one-hidden-layer neural networks with landscape design

venue: arXiv preprint arXiv:1711.00501,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Kurt Hornik
Maxwell Stinchcombe
Halbert White

title: Multilayer feedforward networks are universal approximators

venue: Neural networks,

title: Real and functional analysis

venue: Springer-Verlag, New York,,

authors:
Yuanzhi Li
Yang Yuan

title: Convergence analysis of two-layer neural networks with relu activation

authors:
Cong Ma
Kaizheng Wang
Yuejie Chi
Yuxin Chen

title: Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution

venue: arXiv preprint arXiv:1711.10467,

authors:
Song Mei
Yu Bai
Andrea Montanari

title: The landscape of empirical risk for non-convex losses

venue: arXiv preprint arXiv:1607.06534,

authors:
Marco Mondelli
Andrea Montanari

title: On the connection between learning two-layers neural networks and tensor decomposition

venue: arXiv preprint arXiv:1802.07301,

authors:
Quynh Nguyen
Matthias Hein

title: The loss surface of deep and wide neural networks

venue: In International Conference on Machine Learning,

authors:
Olga Russakovsky
Jia Deng
Hao Su
Jonathan Krause
Sanjeev Satheesh
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
Michael Bernstein

title: Imagenet large scale visual recognition challenge

venue: International Journal of Computer Vision,

authors:
Itay Safran
Ohad Shamir

title: On the quality of the initial basin in overspecified neural networks

title: Spurious local minima are common in two-layer relu neural networks

venue: arXiv preprint arXiv:1712.08968,

authors:
David Silver
Aja Huang
Chris J Maddison
Arthur Guez
Laurent Sifre
George Van Den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot

title: Mastering the game of go with deep neural networks and tree

venue: search. nature,

title: Learning relus via gradient descent

venue: arXiv preprint arXiv:1705.04591,

authors:
Mahdi Soltanolkotabi
Adel Javanmard
Jason D Lee

title: Theoretical insights into the optimization landscape of over-parameterized shallow neural networks

venue: arXiv preprint arXiv:1707.04926,

authors:
J. Sun
Q. Qu
J. Wright

title: Complete dictionary recovery using nonconvex optimization

venue: International Conference on Machine Learning,

authors:
Ruoyu Sun
Zhi-Quan Luo

title: Guaranteed matrix completion via non-convex factorization

title: benefits of depth in neural networks

venue: In Conference on Learning Theory,

title: An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis

venue: arXiv preprint arXiv:1703.00560,

title: Introduction to the non-asymptotic analysis of random matrices

venue: Compressed Sensing, Theory and Applications, pp

venue: arXiv preprint arXiv:1011.3027,

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

venue: arXiv preprint arXiv:1611.03530,

authors:
Kai Zhong
Zhao Song
Inderjit S Dhillon

title: Learning non-overlapping convolutional neural networks with multiple kernels

venue: arXiv preprint arXiv:1711.03440,

authors:
Kai Zhong
Zhao Song
Prateek Jain
Peter L. Bartlett
Inderjit S. Dhillon

title: Recovery guarantees for one-hidden-layer neural networks

venue: In Proceedings of the 34th International Conference on Machine Learning,

heading: 1 INTRODUCTION

text:
Neural networks have attracted a significant amount of research interest in recent years due to the success of deep neural networks (LeCun et al., 2015) in practical domains such as computer vision and artificial intelligence (Russakovsky et al., 2015; He et al., 2016; Silver et al., 2016). However, the theoretical underpinnings behind such success remains mysterious to a large extent. Efforts have been taken to understand which classes of functions can be represented by deep neural networks (Cybenko, 1989; Hornik et al., 1989; Barron, 1993; Telgarsky, 2016), when (stochastic) gradient descent is effective for optimizing a non-convex loss function (Dauphin et al., 2014), and why these networks generalize well (Zhang et al., 2016; Bartlett et al., 2017; Brutzkus et al., 2017).
One important line of research that has attracted extensive attention is a model-recovery setup, i.e., given that the training samples (xi, yi) ∼ (x, y) are generated i.i.d. from a distribution D based on a neural network model with the ground truth parameterW ?, the goal is to recover the underlying model parameterW ?, which is important for the network to generalize well (Mondelli & Montanari, 2018). Previous studies along this topic can be mainly divided into two types of data generations. First, a regression problem, for example, assumes that each sample y is generated as y = 1K ∑K k=1 φ(w ?> k x), wherewk ∈ Rd is the weight vector of the kth neuron, 1 ≤ k ≤ K, and the input x ∈ Rd is Gaussian. This type of regression problem has been studied in various settings. In particular, (Soltanolkotabi, 2017) studied the single-neuron model under ReLU activation, (Zhong et al., 2017b) studied the onehidden-layer multi-neuron network model, and (Li & Yuan, 2017) studied a two-layer feedforward networks with ReLU activations and identity mapping. Second, for a classification problem, suppose each label y ∈ {0, 1} is drawn under the conditional distribution P(y = 1|x) = 1K ∑K k=1 φ(w ?> k x), wherew?k ∈ Rd is the weight vector of the kth neuron, 1 ≤ k ≤ K, and the input x ∈ Rd is Gaussian. Such a problem has been studied in (Mei et al., 2016) in the case with a single neuron.
For both the regression and the classification settings, in order to recover the neural network parameters, all previous studies considered (stochastic) gradient descent over the squared loss, i.e.,
`qu (W ;x, y) = 1
2
( y − 1
K K∑ i=1 φ ( w>i x
))2 , (1)
which yields gradient and Hessian in relatively simple forms to assist the landscape characterization of the function as well as model recovery analysis.
However, for the classification problem, the cross entropy objective used in practice takes the following form
` (W ;x, y) = −y · log
( 1
K K∑ i=1 φ ( w>i x
)) − (1− y) · log ( 1− 1
K K∑ i=1 φ ( w>i x
)) . (2)
The geometry as well as the model recovery problem based on the entropy loss function have not yet been understood. It is expected that such a loss function is very challenging to analyze, not just because it is nonconvex with multiple neurons, but also because the gradient and Hessian take much more complicated forms compared with the squared loss. The main focus of this paper is to develop technical analysis for guaranteed model recovery under the challenging cross entropy loss function in eq. (2) for the classification problem in the multi-neuron case.
Furthermore, previous studies provided two types of statistical guarantees for such model recovery problems using the squared loss. More specifically, (Zhong et al., 2017b) showed that in the local neighborhood of the ground truth, the Hessian of the empirical loss function is positive definite for each given point under independent high probability event. Hence, their guarantee for gradient descent to converge to the ground truth requires a fresh set of samples at every iteration, thus the total sample complexity will depend on the number of iterations. On the other hand, studies such as (Mei et al., 2016; Soltanolkotabi, 2017) establish certain types of uniform geometry such as strong convexity so that resampling per iteration is not needed for gradient descent to have guaranteed linear convergence as long as it enters such a local neighborhood. However, such a stronger statistical guarantee without per-iteration resampling have only been shown for the squared loss function. In this paper, we aim at developing such a strong statistical guarantee for the loss function in eq. (2), which is much more challenging but more practical than the squared loss for the classification problem.

heading: 1.1 OUR CONTRIBUTIONS

text:
This study provides the first performance guarantee for the recovery of one-hidden-layer neural networks using the cross entropy loss function, to the best of our knowledge. More specifically, our contributions are summarized as follows.
• For multi-neuron classification problem with sigmoid activations, we show that, if the input is Gaussian, the empirical risk function fn(W ) = 1n ∑n i=1 ` (W ;xi) based on the cross entropy
loss in eq. (2) is uniformly strongly convex in a local neighborhood of the ground truthW ? of size O(1/K3/2) as soon as the sample size is O(dK5 log2 d), where d is the input dimension and K is the number of neurons.
• We further show that, if initialized in this neighborhood, gradient descent converges linearly to a critical point Ŵn (which we show to exist), with a sample complexity of O(dK5 log2 d), which is near-optimal up to a polynomial factor in K and log d. Due to the nature of quantized labels here, the recover of W ? is only up to certain statistical accuracy, and Ŵn converges to W ? at a rate of O( √ dK9/2 log n/n) in the Frobenius norm. Furthermore, such a convergence guarantee does
not require a fresh set of samples at each iteration due to the uniform strong convexity in the local neighborhood. To obtain -accuracy, it requires a computational complexity of O(ndK2 log(1/ )).
• We adopt the tensor method proposed in (Zhong et al., 2017b), and show it provably provides an initialization in the neighborhood of the ground truth. In particular, our proof replaces the homogeneous assumption on activation functions in (Zhong et al., 2017b) by a mild condition on the curvature of activation functions aroundW ?, which holds for a larger class of activation functions including sigmoid and tanh.
In order to analyze the challenging cross-entropy loss function, our proof develops various new machineries in order to exploit the statistical information of the geometric curvatures, including the gradient and Hessian of the empirical risk, and to develop covering arguments to guarantee uniform concentrations. Our technique also yields similar performance guarantees for the classification problem using the squared loss in eq. (1), which we omit due to space limitations, as it is easier to analyze than cross entropy.

heading: 1.2 RELATED WORK

text:
Due to page limitations we focus on the most relevant literature on theoretical and algorithmic aspects of learning shallow neural networks via nonconvex optimization.
The parameter recovery viewpoint is relevant to the success of non-convex learning in signal processing problems such as matrix completion, phase retrieval, blind deconvolution, dictionary learning and tensor decomposition (Sun & Luo, 2016; Candès et al., 2015; Ge & Ma, 2017; Ge et al., 2016; Sun et al., 2015; Bhojanapalli et al., 2016; Ma et al., 2017), to name a few. The statistical model for data generation effectively removes worst-case instances and allows us to focus on average-case performance, which often possess much benign geometric properties that enable global convergence of simple local search algorithms.
The studies of one-hidden-layer network model can be further categorized into two classes, landscape analysis and model recovery. In the landscape analysis, it is known that if the network size is large enough compared to the data input, then there are no spurious local minima in the optimization landscape, and all local minima are global (Soltanolkotabi et al., 2017; Boob & Lan, 2017; Safran & Shamir, 2016; Nguyen & Hein, 2017). For the case with multiple neurons (2 ≤ K ≤ d) in the under-parameterized setting, the work of Tian (Tian, 2017) studied the landscape of the population squared loss surface with ReLU activations. In particular, there exist spurious bad local minima in the optimization landscape (Ge et al., 2017; Safran & Shamir, 2017) even at the population level. Zhong et. al. (Zhong et al., 2017b) provided several important characterizations for the local Hessian for the regression problem for a variety of activation functions for the squared loss.
In the model recovery problem, the number of neurons is smaller than the dimension of inputs. In the case with a single neuron (K = 1), under Gaussian input, (Soltanolkotabi, 2017) showed that gradient descent converges linearly when the activation function is ReLU, i.e. φ(z) = max{z, 0}, with a zero initialization, as long as the sample complexity is O(d) for the regression problem. On the other end, (Mei et al., 2016) showed that when φ(·) has bounded first, second and third derivatives, there is no other critical points than the unique global minimum (within a constrained region of interest), and (projected) gradient descent converges linearly with an arbitrary initialization, as long as the sample complexity is O(d log2 d) with sub-Gaussian inputs for the classification problem using the squared loss. Moreover, (Zhong et al., 2017b) shows that the ground truth From a technical perspective, our study differs from all the aforementioned work in that the cross entropy loss function we analyze has a very different form. Furthermore, we study the model recovery classification problem under the multi-neuron case, which has not been studied before.
Finally, we note that several papers study one-hidden-layer or two-layer neural networks with different structures under Gaussian input. For example, (Brutzkus & Globerson, 2017; Du et al., 2017a;b; Zhong et al., 2017a) studied the non-overlapping convolutional neural network, (Li & Yuan, 2017) studied a two-layer feedforward networks with ReLU activations and identity mapping, and (Feizi et al., 2017) introduced the Porcupine Neural Network. These results are not directly comparable to ours since both the networks and the loss functions are different.

heading: 1.3 PAPER ORGANIZATION AND NOTATIONS

text:
The rest of the paper is organized as follows. Section 2 describes the problem formulation. Section 3 presents the main results on local geometry and local linear convergence of gradient descent. Section 4 discusses the initialization method. Numerical examples are demonstrated in Section 5, and finally, conclusions are drawn in Section 6.
Throughout this paper, we use boldface letters to denote vectors and matrices, e.g. w andW . The transpose ofW is denoted byW>, and ‖W ‖, ‖W ‖F denote the spectral norm and the Frobenius norm. For a positive semidefinite (PSD) matrixA, we writeA 0. The identity matrix is denoted by I . The gradient and the Hessian of a function f(W ) is denoted by ∇f(W ) and ∇2f(W ), respectively. Let σi (W ) denote the i-th singular value ofW . Denote ‖ · ‖ψ1 as the sub-exponential norm of a random variable. We use c, C,C1, . . . to denote constants whose values may vary from line to line. For nonnegative functions f(x) and g(x), f(x) = O (g(x)) means there exist positive constants c and a such that f(x) ≤ cg(x) for all x ≥ a; f(x) = Ω (g(x)) means there exist positive constants c and a such that f(x) ≥ cg(x) for all x ≥ a.

heading: 2 PROBLEM FORMULATION

text: We first describe the generative model for training data, and then describe the gradient descent algorithm for learning the network weights.

heading: 2.1 MODEL

text:
Suppose we are given n training samples {(xi, yi)}ni=1 ∼ (x, y) that are drawn i.i.d., where x ∼ N (0, I). Assume the activation function is sigmoid, i.e. φ (z) = 1/(1 + e−z) for all z. Conditioned on x ∈ Rd, we consider the classification setting, where y is mapped to a discrete label using the one-hidden layer neural network model as follows:
P(y = 1|x) = 1 K K∑ k=1 φ(w?>k x). (3)
and P(y = 0|x) = 1− P(y = 1|x), where K is the number of neurons. Our goal is to estimateW ? = [w?1 , · · · ,w?K ], via minimizing the following empirical risk function:
fn(W ) = 1
n n∑ i=1 ` (W ;xi) , (4)
where ` (W ;x) := ` (W ;x, y) is the cross entropy loss, i.e., the negative log-likelihood function, i.e.,
` (W ;x) = − [ y · log ( 1
K K∑ i=1 φ ( w>i x
)) + (1− y) · log ( 1− 1
K K∑ i=1 φ ( w>i x
))] .
Let w = vec(W ) = [ w>1 , · · · ,w>K ]> ∈ RdK be the vectorized form of W . With slight abuse of notation, we denote the gradient and Hessian of `(W ;x) with respect to the vector w.

heading: 2.2 GRADIENT DESCENT

text:
To estimateW ?, since (4) is a highly nonconvex function, vanilla gradient descent with an arbitrary initialization may get stuck at local minima. Therefore, we implement the gradient descent algorithm with a well-designed initialization scheme that is described in detail in Section 4. The update rule is given as Wt+1 = Wt − η∇fn (Wt) , where η is the step size. The algorithm is summarized in Algorithm 1.
Algorithm 1 Gradient Descent Input: Training data {(xi, yi)}ni=1, step size η, iteration T Initialization: W0 ← INITIALIZATION ({(xi, yi)}ni=1) Gradient Descent: for t = 0, 1, · · · , T
Wt+1 = Wt − η∇fn (Wt) .
Output: WT
We note that throughout the execution of the algorithm, the same set of training samples is used which is the standard implementation of gradient descent. This is in sharp contrast to existing work such as Zhong et al. (2017b) that employs the impractical scheme of resampling, where a fresh set of training samples is used at every iteration of gradient descent.

heading: 3 MAIN RESULTS

text:
Before stating our main results, we first introduce an important quantity regarding φ(z) that captures the geometric properties of the loss function, distilled in (Zhong et al., 2017b).
Definition 1. Let αq(σ) = Ez∼N (0,1)[φ′(σ · z)zq],∀q ∈ {0, 1, 2}, and βq(σ) = Ez∼N (0,1)[φ′2(σ · z)zq],∀q ∈ {0, 2}. Define ρ(σ) as
ρ(σ) = min{β0(σ)− α20(σ)− α21(σ), β2(σ)− α21(σ)− α22(σ)}.
Note that the definition here is different from that in (Zhong et al., 2017b, Property 3.2) but consistent with (Zhong et al., 2017b, Lemma D.4) which removes the third term in (Zhong et al., 2017b, Property 3.2). For the activation function considered in this paper, the first two terms suffice. We depict ρ(σ) as a function of σ in a certain range for the sigmoid activation in Fig. 1. It is easy to observe that ρ(σ) > 0 for all σ > 0.

heading: 3.1 LOCAL STRONG CONVEXITY

text:
We first characterize the local strong convexity of fn(W ) in a neighborhood of the ground truthW ?. Let B (W ?, r) denote a Euclidean ball centered atW ? ∈ Rd×K with a radius r, i.e.
B (W ?, r) = { W ∈ Rd×K : ‖W −W ?‖F ≤ r } .
Let σi := σi (W ?) denote the i-th singular value ofW ?. Let the condition number be κ = σ1/σK , and λ = ∏K i=1 (σi/σK). The following theorem guarantees the Hessian of the empirical risk function fn(W ) in the local neighborhood ofW ? is positive definite with high probability.
Theorem 1. For the classification model (3) with sigmoid activation function, assume ‖W ?‖F ≤ 1, then there exists some constant C, such that if
n ≥ C · dK5 log2 d · ( κ2λ
ρ (σK)
)2 ,
then with probability at least 1− d−10, for allW ∈ B(W ?, r),
Ω
( 1
K2 · ρ (σK) κ2λ
) · I ∇2fn (W ) C · I
hold, where r := min { C
K 3 2 · ρ(σK)κ2λ , 0.7
} .
We note that all column permutations ofW ? are equivalent global minima of the loss function, and Theorem 1 applies to all such permutation matrices ofW ?. The proof of Theorem 1 is outlined in Appendix A. Theorem 1 guarantees that the Hessian of the empirical cross-entropy loss function fn(W ) is positive definite (PD) in a neighborhood of the ground truthW ?, as long as ρ(σK) > 0 (i.e. W ? is full-column rank), when the sample size n is sufficiently large for the sigmoid activation. The bounds in Theorem 1 depend on the dimension parameters of the network (n and K), as well as the activation function and the ground truth (ρ(σK), λ). As a special case, suppose W ? is composed of orthonormal columns with ρ(σK) = O(1), κ = 1, λ = 1. Then, Theorem 1 guarantees Ω(1/K2)I ∇2fn (W ) C within the neighborhood B(W ?,Ω(1/K √ K)), as soon as the sample complexity n = Ω(dK5 log2 d). The sample complexity is order-wise near-optimal in d up to polynomial factors of K and log d, since the number of unknown parameters is dK.

heading: 3.2 PERFORMANCE GUARANTEES OF GRADIENT DESCENT

text:
For the classification problem, due to the nature of quantized labels, W ? is no longer a critical point of fn(W ). By the strong convexity of the empirical risk function fn(W ) in the local neighborhood ofW ?, there can exist at most one critical point in B(W ?, r), which is the unique local minimizer in B (W ?, r) if it exists. The following theorem shows that there indeed exists such a critical point Ŵn, which is provably close to the ground truthW ?, and gradient descent converges linearly to Ŵn. Theorem 2. For the classification model (3) with sigmoid activation function, and assume ‖W ?‖F ≤ 1, there exist some constants C,C1 > 0 such that if the sample size n ≥ C · dK5 log2 d · ( κ2λ ρ(σK) )2 , then with probability at least 1 − d−10, there exists a unique critical point Ŵn in B(W ?, r) with r := min { c
K3/2 · ρ(σK)κ2λ , 0.7 } , which satisfies∥∥∥Ŵn −W ?∥∥∥
F ≤ C1
K9/4κ2λ
ρ (σK)
√ d log n
n . (5)
Moreover, if the initial pointW0 ∈ B (W ?, r), then gradient descent converges linearly to Ŵn, i.e.∥∥∥Wt − Ŵn∥∥∥ F ≤ (1−Hminη)t ∥∥∥W0 − Ŵn∥∥∥ F (6)
where Hmin = Ω ( 1 K2 · ρ(σK) κ2λ ) , as long as the step size η = Ω ( 1 K2 · ρ(σK) κ2λ ) .
Similarly to Theorem 1, Theorem 2 also holds for all column permutations ofW ?. The proof can be found in Appendix B. Theorem 2 guarantees that there exists a critical point Ŵn in B(W ?, r) which converges to W ? at the rate of O(K9/4 √ d log n/n), and therefore W ? can be recovered
consistently as n goes to infinity. Moreover, gradient descent converges linearly to Ŵn at a linear rate, as long as it is initialized in the basin of attraction. To achieve -accuracy, i.e. ∥∥∥Wt − Ŵn∥∥∥ F ≤ , it
requires a computational complexity of O ( ndK2 log (1/ ) ) , which is linear in n, d and log(1/ ).

heading: 4 INITIALIZATION

text: Our initialization adopts the tensor method proposed in (Zhong et al., 2017b). In this section, we first briefly describe this method, and then present the performance guarantee of the initialization with remarks on the differences from that in (Zhong et al., 2017b).

heading: 4.1 PRELIMINARY AND ALGORITHM

text:
This subsection briefly introduces the tensor method proposed in (Zhong et al., 2017b), to which a reader can refer for more details. We first define a product ⊗̃ as follows. If v ∈ Rd is a vector and I is the identity matrix, then v⊗̃I = ∑d j=1[v ⊗ ej ⊗ ej + ej ⊗ v ⊗ ej + ej ⊗ ej ⊗ v]. If M is a
symmetric rank-r matrix factorized asM = ∑r i=1 siviv > i and I is the identity matrix, then
M⊗̃I = r∑ i=1 si d∑ j=1 6∑ l=1 Al,i,j ,
where A1,i,j = vi ⊗ vi ⊗ ej ⊗ ej , A2,i,j = vi ⊗ ej ⊗ vi ⊗ ej , A3,i,j = ej ⊗ vi ⊗ vi ⊗ ej , A4,i,j = vi ⊗ ej ⊗ ej ⊗ vi,A5,i,j = ej ⊗ vi ⊗ ej ⊗ vi andA6,i,j = ej ⊗ ej ⊗ vi ⊗ vi. Definition 2. DefineM1,M2,M3,M4 and m1,i, m2,i, m3,i, m4,i as follows: M1 = E[y · x], M2 = E[y · (x⊗ x− I)], M3 = E[y · (x⊗3 − x⊗̃I)], M4 = E[y · (x⊗4 − (x⊗ x)⊗̃I + I⊗̃I)], m1,i = γ1(‖w?i ‖), m2,i = γ2(‖w?i ‖)− γ0(‖w?i ‖), m3,i = γ3(‖w?i ‖)− 3γ1(‖w?i ‖), m4,i = γ4(‖w?i ‖) + 3γ0(‖w?i ‖)− 6γ2(‖w?i ‖), where γj(σ) = Ez∼N (0,1)[φ(σ · z)zj ], ∀j = 0, 1, 2, 3, 4.
Definition 3. Let α ∈ Rd denote a randomly picked vector. We define P2 and P3 as follows: P2 = Mj2(I, I,α, · · · ,α),1 where j2 = min{j ≥ 2|Mj 6= 0}, and P3 = Mj3(I, I, I,α, · · · ,α), where j3 = min{j ≥ 3|Mj 6= 0}.
We further denote w = w/‖w‖. The initialization algorithm based on the tensor method is summarized in Algorithm 2, which includes two major steps. Step 1 first estimates the direction of each column of W ? by decomposing P2 to approximate the subspace spanned by {w?1,w?2, · · · ,w?K} (denoted by V ), then reduces the third-order tensor P3 to a lower-dimension tensorR3 = P3 (V ,V ,V ) ∈ RK×K×K , and applys non-orthogonal tensor decomposition onR3 to output the estimate siV >w?i , where si ∈ {1,−1} is a random sign. Step 2 approximates the magnitude of w?i and the sign si by solving a linear system of equations.
Algorithm 2 Initialization via Tensor Method Input: Partition n pairs of data {(xi, yi)}ni=1 into three parts D1,D2,D3. Output: 1: Estimate P̂2 of P2 from data set D1. 2: V ← POWERMETHOD(P̂2,K). 3: Estimate R̂3 of P3(V ,V ,V ) from data set D2. 4: {ûi}i∈[K] ← KCL(R̂3). 5: {w(0)i }i∈[K] ← RECMAG(V , {ûi}i∈[K],D3).

heading: 4.2 PERFORMANCE GUARANTEE OF INITIALIZATION

text:
For the classification problem, we make the following technical assumptions, similarly in (Zhong et al., 2017b, Assumption 5.3) for the regression problem. Assumption 1. The activation function φ(z) satisfies the following conditions:1. If Mj 6= 0, then
K∑ i=1 mj,i ( w?i >α )j−2 wi ?wi ?> 6= 0 ∀j,
K∑ i=1 mj,i ( w?>i α )j−3 (V >w?i )vec((V >w?i )(V >w?i ) >)> 6= 0 for j ≥ 3

heading: 2. At least one of M3 and M4 is non-zero.

text:
Furthermore, we do not require the homogeneous assumption ((i.e., φ(az) = apz for an integer p)) required in (Zhong et al., 2017b), which can be restrictive. Instead, we assume the following condition on the curvature of the activation function around the ground truth, which holds for a larger class of activation functions such as sigmoid and tanh. Assumption 2. Let l1 be the index of the first nonzero Mi where i = 1, . . . , 4. For the activation function φ (·), there exists a positive constant δ such that ml1,i(·) is strictly monotone over the interval (‖w?i ‖ − δ, ‖w?i ‖+ δ), and the derivative of ml1,i(·) is lower bounded by some constant for all i.
We next present the performance guarantee for the initialization algorithm in the following theorem. Theorem 3. For the classification model (3), under Assumptions 1 and 2, if the sample size n ≥ dpoly (K,κ, t, log d, 1/ ), then the outputW0 ∈ Rd×K of Algorithm 2 satisfies ‖W0 −W ?‖F ≤ poly (K,κ) ‖W ?‖F, (7) with probability at least 1− d−Ω(t).
The proof of Theorem 3 consists of (a) showing the estimation of the direction ofW ? is sufficiently accurate and (b) showing the approximation of the norm of W ? is accurate enough. Our proof of part (a) is the same as that in (Zhong et al., 2017b), but our argument in part (b) is different, where we relax the homogeneous assumption on activation functions. More details can be found in the supplementary materials in Appendix C.
1See (15) in the supplemental materials for definition.

heading: 5 NUMERICAL EXPERIMENTS

text:
In this section, we first implement gradient descent to verify that the empirical risk function is strongly convex in the local region around W ?. If we initialize multiple times in such a local region, it is expected that gradient descent converges to the same critical point Ŵn, with the same set of training samples. Given a set of training samples, we randomly initialize multiple times, and then calculate the variance of the output of gradient descent. Denote the output of the `th run as ŵ(`)n = vec(Ŵ (`) n )
and the mean of the runs as w̄. The error is calculated as SDn = √ 1 L ∑L `=1 ‖ŵ (`) n − w̄‖2, where L = 20 is the total number of random initializations. Adopted in (Mei et al., 2016), it quantifies the standard deviation of the estimator Ŵn under different initializations with the same set of training samples. We say an experiment is successful, if SDn ≤ 10−2. Figure 2 (a) shows the successful rate of gradient descent by averaging over 50 sets of training samples for each pair of n and d, where K = 3 and d = 15, 20, 25 respectively. The maximum iterations for gradient descent is set as itermax = 3500. It can be seen that as long as the sample complexity is large enough, gradient descent converges to the same local minima with high probability.
We next show that the statistical accuracy of the local minimizer for gradient descent if it is initialized close enough to the ground truth. Suppose we initialize around the ground truth such that ‖W0 −W?‖F ≤ 0.1 · ‖W?‖F. We calculate the average estimation error as ∑L `=1 ‖Ŵ (`) n − W ?‖2F/(L‖W ?‖2F) over L = 100 Monte Carlo simulations with random initializations. Fig. 2 (b) shows the average estimation error with respect to the sample complexity when K = 3 and d = 20, 35, 50 respectively. It can be seen that the estimation error decreases gracefully as we increase the sample size and matches with the theoretical prediction of error rates reasonably well.
We further compare the performance of gradient descent algorithm applied to both the cross entropy loss and the squared loss, respectively. As shown in Fig 2 (c), when K = 3, d = 20, cross entropy loss with gradient descent achieves a much lower error than the squared loss. Clearly, the cross entropy loss is favored in the classification problem over the squared loss.

heading: 6 CONCLUSIONS

text: In this paper, we have studied the model recovery of a one-hidden-layer neural network using the cross entropy loss in a multi-neuron classification problem. In particular, we have characterized the sample complexity to guarantee local strong convexity in a neighborhood (whose size we have characterized as well) of the ground truth when the training data are generated from a classification model. This guarantees that with high probability, gradient descent converges linearly to the ground truth if initialized properly. In the future, it will be interesting to extend the analysis in this paper to more general class of activation functions, particularly ReLU-like activations; and more general network structures, such as convolutional neural networks (Du et al., 2017b; Zhong et al., 2017a).

heading: A PROOF OF THEOREM 1

text:
To begin, denote the population loss function as
f(W ) = E [fn(W )] = E [` (W ;x)] , (8)
where the expectation is taken with respect to the distribution of the training sample (x; y).
The proof of Theorem 1 follows the following steps:
1. We first show that the Hessian∇2f(W ) of the population loss function is smooth with respect to ∇2f(W ?) (Lemma 1);
2. We then show that∇2f(W ) satisfies local strong convexity and smoothness in a neighborhood of W ?, B(W ?, r) with appropriately chosen radius by leveraging similar properties of ∇2f(W ?) (Lemma 2);
3. Next, we show that the Hessian of the empirical loss function ∇2fn(W ) is close to its popular counterpart∇2f(W ) uniformly in B(W ?, r) with high probability (Lemma 3).
4. Finally, putting all the arguments together, we establish∇2fn(W ) satisfies local strong convexity and smoothness in B(W ?, r).
We will first show that the Hessian of the population risk is smooth enough around W ? in the following lemma. Lemma 1. For sigmoid activations, assume ‖W ?‖F ≤ 1, we have
‖∇2f (W )−∇2f (W ?) ‖ ≤ C K 1 2 · ‖W −W ?‖F, (9)
holds for some large enough constant C, when ‖W −W ?‖F ≤ 0.7.
The proof is given in Appendix D.2. Lemma 1 together with the fact that ∇2f(W ?) be lower and upper bounded, will allow us to bound∇2f(W ) in a neighborhood around ground truth, given below. Lemma 2 (Local Strong Convexity and Smoothness of Population Loss). For sigmoid activations, there exists some constant C, such that
4 K2 · ρ (σK) κ2λ · I ∇2f (W ) C · I,
holds for allW ∈ B(W ?, r) with r := min { C
K 3 2 · ρ(σK)κ2λ , 0.7
} .
The proof is given in Appendix D.3. The next step is to show the Hessian of the empirical loss function is close to the Hessian of the population loss function in a uniform sense, which can be summarized as following. Lemma 3. For sigmoid activations, there exists constant C such that as long as n ≥ C · dK log dK, with probability at least 1− d−10, the following holds
sup W∈B(W ?,r)
‖∇2fn (W )−∇2f (W ?) ‖ ≤ C √ dK logn
n ,
where r := min { C
K 3 2 · ρ(σK)κ2λ , 0.7
} .
The proof can be found in Appendix D.4.
The final step is to combine Lemma 3 and Lemma 1 to obtain Theorem 1 as follows,
Proof of Theorem 1. By Lemma 3 and Lemma 2, we have with probability at least 1− d−10, ∇2fn(W ) ∇2f (W )− ∥∥∇2fn (W )−∇2f(W )∥∥ · I
Ω ( 1
K2 · ρ (σK) κ2λ
) · I − Ω ( C · √ dK log n
n
) · I.
As long as the sample size n is set such that C · √ dK log n
n ≤ 1 K2 · ρ (σK) κ2λ ,
i.e. n ≥ C · dK5 log2 d · (
κ2λ ρ(σK)
)2 , we have
∇2fn(W ) Ω ( 1
K2 · ρ (σK) κ2λ
) · I.
holds for allW ∈ B (W ?, r). Similarly, we have
∇2fn(W ) C · I
holds for allW ∈ B (W ?, r).

heading: B PROOF OF THEOREM 2

text:
We have established that fn (W ) is strongly convex in B(W ?, r) in Theorem 1, thus there exists at most one critical point in B(W ?, r). The proof of Theorem 2 follows the steps below:
1. We first show that the gradient∇fn (W ) concentrates around ∇f (W ) in B(W ?, r) (Lemma 4), and then invoke (Mei et al., 2016, Theorem 2) to guarantee there indeed exists a critical point Ŵn in B(W ?, r);
2. We next show Ŵn is close toW ? and gradient descent converges linearly to Ŵn with a properly chosen step size.
The following lemma establishes that∇fn (W ) uniformly concentrates around∇f (W ). Lemma 4. For sigmoid activation function, assume ‖W ?‖F ≤ 1, there exists constant C such that as long as n ≥ CdK log(dK), with probability at least 1− d−10, the following holds
sup W∈B(W ?,r)
‖∇fn (W )−∇f(W )‖ ≤ C
√ d √ K log n
n ,
where r := min { C
K 3 2 · ρ(σK)κ2λ , 0.7
} .
Notice that for the population risk function, f(W ),W ? is the unique critical point in B(W ?, r) due to local strong convexity. With Lemma 3 and Lemma 4, we can invoke (Mei et al., 2016, Theorem 2), which guarantees the following.
Corollary 1. There exists one and only one critical point Ŵn ∈ B (W ∗, r) that satisfies ∇fn ( Ŵn ) = 0.
We first show that Ŵn is close toW ?. By the intermediate value theorem, ∃W ′ ∈ B (W ?, r) such that
fn ( Ŵn ) = fn (W ?) + 〈 ∇fn (W ?) , vec ( Ŵn −W ? )〉 + 1 2 vec ( Ŵn −W ? )> ∇2fn (W ′) vec ( Ŵn −W ?
) ≤ fn (W ?) , (10)
where the last inequality follows from the optimality of Ŵn. By Theorem 1, we have
1 2 vec ( Ŵn −W ? )> ∇2fn (W ′) vec ( Ŵn −W ? ) ≥ Ω ( 1 K2 · ρ (σK) κ2λ )∥∥∥Ŵn −W ?∥∥∥2 F .
(11)
On the other hand, by the Cauchy-Schwarz inequality, we have∣∣∣〈∇fn (W ?) , vec(Ŵn −W ?)〉∣∣∣ ≤ ‖∇fn (W ?) ‖2‖Ŵn −W ?‖F ≤ Ω (√ dK1/2 log n
n
) ‖Ŵn −W ?‖F, (12)
where the last line follows from Lemma 4. Plugging (11) and (12) into (10), we have
‖Ŵn −W ?‖F ≤ Ω
( K 9 4κ2λ
ρ (σK)
√ d log n
n
) . (13)
Now we have established there indeed exists a critical point in B(W ?, r). We can establish local linear convergence of gradient descent as below. LetWt be the estimate at the t-th iteration. According to the update rule, we have∥∥∥Wt+1 − Ŵn∥∥∥2 F = ∥∥∥Wt − η∇fn (Wt)− Ŵn∥∥∥2 F
= ‖Wt − Ŵn‖2F + η2‖∇fn (Wt) ‖2F − 2η 〈 ∇fn (Wt) , vec ( Wt − Ŵn )〉 .
(14)
Moreover, by the fundamental theorem of calculus (Lang, 1993),∇fn (Wt) can be written as ∇fn (Wt) = ∇fn (Wt)−∇fn ( Ŵn ) =
(∫ 1 0 ∇2fn ( Ŵn + γ ( Wt − Ŵn )) dγ ) vec ( Wt − Ŵn ) ,
whereW (γ) = Ŵn + γ ( Wt − Ŵn ) for γ ∈ [0, 1]. By Theorem 1, we have
Hmin · I ∇2fn (W (γ)) Hmax · I, where Hmin = Ω ( 1 K2 · ρ(σK) κ2λ ) and Hmax = C. Therefore, we have
‖∇fn (Wt) ‖2F ≤ H2max ∥∥∥Wt − Ŵn∥∥∥2
F .
Hence,
‖Wt+1 − Ŵn‖2F ≤ ( 1− 2ηHmin + η2H2max ) ‖Wt − Ŵn‖2F
≤ (
1− 1 2 ηHmin
)2 ‖Wt − Ŵn‖2F
as long as we set η < HminH2max := Ω ( 1 K2 · ρ(σK) κ2λ ) . In summary, gradient descent converges linearly to
the local minimizer Ŵn.

heading: C PROOF OF THEOREM 3

text:
The proof contains two parts. Part (a) proves that the estimation of the direction ofW ? is sufficiently accurate, which follows the arguments similar to those in (Zhong et al., 2017b) and is only briefly summarized below. Part (b) is different, where we do not require the homogeneous condition for the activation function, and instead, our proof is based on a mild condition in Assumption 2. We detail our proof in part (b).
We first define a tensor operation as follows. For a tensor T ∈ Rn1×n2×n3 and three matrices A ∈ Rn1×d1 ,B ∈ Rn2×d2 ,C ∈ Rn3×d3 , the (i, j, k)-th entry of the tensor T (A,B,C) is given by
n1∑ i′ n2∑ j′ n3∑ k′ Ti′,j′,k′Ai′,iBj′,jCk′,k. (15)
(a) In order to estimate the direction of each wi for i = 1, . . . ,K, (Zhong et al., 2017b) shows that for the regression problem, if the sample size n ≥ dpoly (K,κ, t, log d), then ‖wi? − siV ûi‖ ≤ poly (K, κ) (16) holds with high probability. Such a result also holds for the classification problem with only slight difference in the proof as we describe as follows. The main idea of the proof is to bound the estimation error of P2 andR3 via Bernstein inequality. For the regression problem, Bernstein inequality was applied to terms associated with each neuron individually, and the bounds were then put together via triangle inequality in (Zhong et al., 2017b), whereas for the classification problem here, we apply Bernstein inequality to terms associated with all neurons all together. Another difference is that the label yi of the classification model is bounded by nature, whereas the output yi in the regression model needs to be upper bounded via homogeneously bounded conditions of the activation function. A reader can refer to (Zhong et al., 2017b) for the details of the proof for this part.
(b) In order to estimate ‖wi‖ for i = 1, . . . ,K, we provide a different proof from (Zhong et al., 2017b), which does not require the homogeneous condition on the activation function, but assumes a more relaxed condition in Assumption 2.
We define a quantity Q1 as follows: Q1 = Ml1(I,α, · · · ,α︸ ︷︷ ︸
(l1−1)
), (17)
where l1 is the first non-zero index such that Ml1 6= 0. For example, if l1 = 3, then Q1 takes the following form
Q1 = M3 (I,α,α) = 1
K K∑ i=1 m3,i(‖w?i ‖) ( α>w?i )2 w?i , (18)
where w = w/‖w‖ and by definition m3,i(‖w?i ‖) = E [ φ (‖w?i ‖ · z) z3 ] − 3E [φ (‖w?i ‖ · z) z] . (19)
Clearly, Q1 has information of ‖w?i ‖, which can be estimated by solving the following optimization problem:
β? = argminβ∈RK ∥∥∥∥∥ 1K K∑ i=1 βisiwi ? −Q1 ∥∥∥∥∥ , (20) where each entry of the solution takes the form
β?i = s 3 im3,i(‖w?i ‖) ( αT siwi ? )2 . (21)
In the initialization, we substitute Q̂1 (estimated from training data) for Q1, V ûi (estimated in part (a)) for siwi? into (20), and obtain an estimate β̂ of β?. We then substitute β̂ for β? and V ûi for siwi
? into (21) to obtain an estimate âi of ‖w?i ‖ via the following equation β̂i = s 3 im3,i(âi) ( αTV ûi )2 . (22) Furthermore, since ml1,i(x) has fixed sign for x > 0 and for l1 ≥ 1, si can be estimated correctly from the sign of β̂i for i = 1, . . . ,K.
For notational simplicity, let β?1,i := β?i
s3i (α T siwi?) 2 and β̂1,i := β̂is3i (αTV ûi)2 , and then (21) and (22)
become β̂1,i = m3,i(âi), β ? 1,i = m3,i(‖w?i ‖). (23)
By Assumption 2 and (21), there exists a constant δ′ > 0 such that the inverse function g(·) ofm3,1(·) has upper-bounded derivative in the interval (β?1,i − δ′, β?1,i + δ′), i.e., |g′(x)| < Γ for a constant Γ. By employing the result in (Zhong et al., 2017b), if the sample size n ≥ dpoly (K,κ, t, log d), then Q̂1 and Q1, V ûi and siwi? can be arbitrarily close so that |β?1,i − β̂1,i| < min{δ′, r√KΓ}.
Thus, by (23) and mean value theorem, we obtain
|âi − ‖w?i ‖| = |g′(ξ)||β?1,i − β̂1,i| (24) where ξ is between β?1,i and β̂1,i, and hence |g′(ξ)| < Γ. Therefore, |âi − ‖w?i ‖| ≤ r√K , which is the desired result.

heading: D PROOF OF TECHNICAL LEMMAS

text:
D.1 PRELIMINARIES
We introduce some useful definitions and results that will be used in the proofs. The first one is the definition of norms of random variable, i.e.
Definition 4 (Sub-gaussian and Sub-exponential norm). The sub-gaussian norm of a random variable X , denotes as ‖X‖ψ2 , is defined as
‖X‖ψ2 = sup p≥1
p− 1 2 (E [|X|p]) 1 p , (25)
and the sub-exponential norm of X , denoted as ‖X‖ψ1 , is defined as
‖X‖ψ1 = sup p≥1
p−1 (E [|X|p]) 1 p . (26)
The definition is summarized from (Vershynin, 2012, Def 5.7,Def 5.13), and if ‖X‖ψ2 is upper bounded, then X is a sub-gaussian random variable and it satisfies
P (|X| > t) ≤ exp ( 1− ct2/‖X‖2ψ2 ) for all t ≥ 0. (27)
Next we provide the calculations of the gradient and Hessian of E [` (W ;x)]. Let’s denote p (W ) = 1 K ∑K i=1 φ ( w>i x ) , and then
E [ ∂` (W ;x)
∂wj
] = E − 1 K  1K ∑Ki=1 φ (w?>i x)− 1K ∑Ki=1 φ (w>i x)( 1 K ∑K i=1 φ ( w>i x ))( 1− 1K ∑K i=1 φ ( w>i x )) · φ′ (w>j x) x  , = E [ − 1 K φ′ ( w>j x ) · p (W ?)− p (W ) p (W ) (1− p (W )) · x ] (28)
E [ ∇2` (W ;x) ∂wj∂wl ] = E [ ξj,l (W ) (p (W ) (1− p (W )))2 · xx> ] (29)
where if j 6= l,
ξj,l (W ) = 1 K2 φ′ ( w>j x ) φ′ ( w>l x ) · ( p (W ) 2 + p (W ?)− 2p (W ?) p (W ) ) ,
and if j = l,
ξj,j (W ) = 1 K2 φ′ ( w>j x )2 · (p (W )2 + p (W ?)− 2p (W ?) p (W )) − 1 K φ′′ ( w>j x ) (p (W ?)− p (W )) (p (W ) (1− p (W ))) .
D.2 PROOF OF LEMMA 1
Proof. Let ∆ = ∇2f(W )−∇2f(W ?). For each (j, l) ∈ [K]× [K], let ∆j,l ∈ Rd×d denote the (j, l)-th block of ∆. Let a = [a>1 , · · · ,a>K ]> ∈ RdK . Since by definition,
‖∇2f(W )−∇2f(W ?)‖ = max ‖a‖=1 a>(∇2f(W )−∇2f(W ?))a
= max ‖a‖=1 K∑ j=1 K∑ l=1 a>j ∆j,lal. (30)
Next we will evaluate ∆j,l. From (29) we can write the hessian block more concisely as
∂2f (W ) ∂wj∂wl = E
[ gj,l (W ) · xx> ] , (31)
where gj,l (W ) = ξj,l(W ) (p(W )(1−p(W )))2 ∈ R, and then by the mean value theorem, we can write gj,l (W ) as
gj,l (W ) = gj,l (W ?) + K∑ k=1
〈 ∂gj,l ( W̃ )
∂w̃k ,wk −w?k
〉 (32)
where W̃ = η ·W + (1− η)W ? for some η ∈ (0, 1). Thus we can calculate ∆j,l as
∆j,l = ∂2f (W ) ∂wj∂wl − ∂ 2f (W ?) ∂w?j∂w ? l
= E [ gj,l (W ) · xx> ] − E [ gj,l (W ?) · xx> ]
= E  K∑ k=1 〈 ∂gj,l ( W̃ ) ∂w̃k ,wk −w?k 〉 · xx>  , (33)
and plug it back to (30) we can obtain
‖∇2f(W )−∇2f(W ?)‖
= max ‖a‖=1 K∑ j=1 K∑ l=1 a>j ∆j,lal
= max ‖a‖=1 K∑ j=1 K∑ l=1 E  K∑ k=1 〈 ∂gj,l ( W̃ ) ∂w̃k ,wk −w?k 〉 · (a>j x) (a>l x)
= max ‖a‖=1 K∑ j=1 K∑ l=1 E [( K∑ k=1 Tj,l,k 〈x,wk −w?k〉 ) · ( a>j x ) ( a>l x )]
≤ max ‖a‖=1 K∑ j=1 K∑ l=1 √√√√E[ K∑ k=1 T 2j,l,k ] · √√√√E[ K∑ k=1 (〈x,wk −w?k〉) 2 ( a>j x )2 ( a>l x )2]
≤ max ‖a‖=1 K∑ j=1 K∑ l=1 √√√√ K∑ k=1 E [ T 2j,l,k ] · √√√√ K∑ k=1 ‖wk −w?k‖22 · ‖aj‖22 · ‖al‖22, (34)
for the third equality we have used the fact that ∂gj,l(W̃ ) ∂w̃k
can be written as Tj,l,k ·x, where Tj,l,k ∈ R, since the variable of gj,l ( W̃ ) is in the form ofw>i x. and for the last two inequalities, we have used
Cauchy-Schwarz inequality. Our next goal is to upper bound E [ T 2j,l,k ] . Further since
∂gj,l (W )
∂wk =
1 K2 · ∂ φ′(w>j x)φ ′(w>l x)·(p(W ) 2+p(W ?)−2p(W ?)p(W )) (p(W )(1−p(W )))2 ∂wk ,
which aligns with x and the scalar coefficient is upper bounded by 1K2 · C (p(W̃ )(1−p(W̃ ))) 3 , since φ (·), φ′ (·), φ′′ (·) are all upper bounded, thus we leave only the denominator. And then
E [ T 2j,l,k ] ≤ C K4 · E  1( p ( W̃ )( 1− p ( W̃ )))6  ≤ C K4 · e‖W̃ ‖ 2 F , (35)
holds for some constant C, where the second inequality follows from Lemma 5.
Lemma 5. Let x ∼ N (0, I), t = max {‖w1‖2, · · · ‖wK‖2} and z ∈ Z such that z ≥ 1 , for the sigmoid activation function φ (x) = 11+e−x , the following
E  1 1 K ∑K i=1 φ ( w>i x ) ( 1− 1K ∑K i=1 φ ( w>i x )) z ≤ C · et2 , (36)
holds for a large enough constant C which depends on the constant z.
Plugging (35) into (34), we can obtain
‖∇2f(W )−∇2f(W ?)‖ ≤ C K 3 2 e‖W̃ ‖ 2 F · ‖W −W ?‖F · max ‖a‖=1 K∑ j=1 K∑ l=1 ‖aj‖2‖al‖2
≤ C K 1 2 e‖W̃ ‖ 2 F · ‖W −W ?‖F, (37)
Further since e‖W̃ ‖ 2 F ≤ C · (1 + ‖W −W ?‖F) when ‖W −W ?‖F ≤ 0.7, where we have used the assumption that ‖W ?‖F ≤ 1 thus we can conclude that if ‖W −W ?‖F ≤ 0.7, then
‖∇2f(W )−∇2f(W ?)‖ ≤ C K 1 2 ‖W −W ?‖F (38)
holds for some constant C.
D.3 PROOF OF LEMMA 2
Proof. We will first present upper and lower bounds of the Hessian of the population risk at ground truth, i.e. ∇2f(W ?), and then apply Lemma 1 to obtain a uniform bound in the neighborhood of W ?. As a reminder,
∂2f (W ?)
∂w2j = E  1 K2 ·  φ′ (w?>j x)2( 1 K ∑K i=1 φ ( w?>i x ))( 1− 1K ∑K i=1 φ ( w?>i x )) xx>  (39) ∂2f (W ?)
∂wj∂wl = E  1 K2 ·  φ′ (w?>j x)φ′ (w?>l x)( 1 K ∑K i=1 φ ( w?>i x ))( 1− 1K ∑K i=1 φ ( w?>i x )) xx>  , (40) and let a = [a>1 , · · · ,a>K ]> ∈ RdK , we can write
∇2f (W ?) (
min ‖a‖2=1
a>∇2f (W ?)a ) · I
= min ‖a‖2=1
1
K2 E
 (∑K i=1 φ ′ (w?>i x) (a>i x))2(
1 K ∑K i=1 φ ( w?>i x ))( 1− 1K ∑K i=1 φ ( w?>i x
))
min ‖a‖2=1
4
K2 E ( K∑ i=1 φ′ ( w?>i x ) ( a>i x ))2 4 K2 · ρ (σK) κ2λ · I, (41)
the second inequality holds due to the fact that (
1 K ∑K i=1 φ ( w?>i x ))( 1− 1K ∑K i=1 φ ( w?>i x )) ≤
1 4 , and the last inequality follows from (Zhong et al., 2017b, Lemmas D.4 and D.6).
Further more, we can uppder bound∇2f (W ?) as
∇2f (W ?) (
max ‖a‖2=1
a>∇2f (W ?)a ) · I
= max ‖a‖2=1
1
K2 E
 (∑K i=1 φ ′ (w?>i x) (a>i x))2
1 K2 ∑K i=1 ∑K j=1 φ ( w?>i x ) ( 1− φ ( w?>j x
))  · I
max ‖a‖2=1
1
K2 E
 (∑K i=1 φ ′ (w?>i x)2) · (∑Ki=1 (a>i x)2)
1 K2 ∑K i=1 ∑K j=1 φ ( w?>i x ) ( 1− φ ( w?>j x
))  · I by Cauchy-Schwarz inequality
max ‖a‖2=1
1
K2 E
 C4 (∑K i=1 φ ′ (w?>i x)) · (∑Ki=1 (a>i x)2)
1 K2 ∑K i=1 φ ( w?>i x ) ( 1− φ ( w?>i x
))  · I
max ‖a‖2=1
1
K2 E
[ CK2
4 K∑ i=1 ( a>i x )2] · I = C · I, (42)
where for the third and fourth inequality we have used the fact that φ ( w?>i x ) ( 1− φ ( w?>i x )) ≤ 14 and K∑ i=1 K∑ j=1 φ ( w?>i x ) ( 1− φ ( w?>j x )) ≥ K∑ i=1 φ ( w?>i x ) ( 1− φ ( w?>i x )) = K∑ i=1 φ′ ( w?>i x ) .
Thus together with the lower bound (41) we can conclude that
4 K2 · ρ (σK) κ2λ · I ∇2f (W ?) C · I, (43)
From Lemma 1, we have
‖∇2f(W )−∇2f(W ?)‖ . C K 1 2 ‖W −W ?‖F , (44)
therefore, when ‖W ? −W ‖F ≤ 0.7 and
C
K 1 2
· ‖W −W ?‖F ≤ 4 K2 · ρ (σK) κ2λ ,
i.e., when ‖W −W ?‖F ≤ min { C
K 3 2 · ρ(σK)κ2λ , 0.7
} for some constant C, we have
σmin ( ∇2f (W ) ) ≥ σmin ( ∇2f (W ?) ) − ‖∇2f (W )−∇2f (W ?) ‖ (45)
& 4 K2 · ρ (σK) κ2λ − C K 1 2 ‖W −W ?‖F & 4 K2 · ρ (σK) κ2λ . (46)
Moreover, within the same neighborhood, by the triangle inequality we have
‖∇2f (W ) ‖ ≤ ‖∇2f (W )−∇2f (W ?) ‖+ ‖∇2f (W ?) ‖ . C. (47)
D.4 PROOF OF LEMMA 3
Proof. We adapt the analysis in (Mei et al., 2016) to our setting. Let N be the -covering number of the Euclidean ball B (W ?, r). It is known that logN ≤ dK log (3r/ ) (Vershynin, 2010). Let W = {W1, · · · ,WN } be the -cover set with N elements. For any W ∈ B (W ?, r), let j (W ) = argminj∈[N ] ‖W −Wj(W )‖F ≤ for allW ∈ B (W ?, r).
For anyW ∈ B (W ?, r), we have
∥∥∇2fn (W )−∇2f(W )∥∥ ≤ 1 n ∥∥∥∥∥ n∑ i=1 [ ∇2` (W ;xi)−∇2` ( Wj(W );xi )]∥∥∥∥∥ +
∥∥∥∥∥ 1n n∑ i=1 ∇2` ( Wj(W );xi ) − E [ ∇2` ( Wj(w);x )]∥∥∥∥∥ + ∥∥E [∇2` (Wj(W );x)]− E [∇2` (W ;x)]∥∥ .
Hence, we have
P ( sup
W∈B(W ?,r) ∥∥∇2fn (W )−∇2f(W )∥∥ ≥ t) ≤ P (At) + P (Bt) + P (Ct) , (48) where the events At, Bt and Ct are defined as
At =
{ sup
W∈B(W ?,r)
1
n ∥∥∥∥∥ n∑ i=1 [ ∇2` (W ;xi)−∇2` ( Wj(W );xi )]∥∥∥∥∥ ≥ t3 } , (49)
Bt = { sup W∈W ∥∥∥∥∥ 1n n∑ i=1 ∇2` (W ;xi)− E [ ∇2` (W ;x) ]∥∥∥∥∥ ≥ t3 } , (50)
Ct =
{ sup
W∈B(W ?,r) ‖E [ ∇2` ( Wj(W );x )] − E [ ∇2` (W ;x) ] ‖ ≥ t 3
} . (51)
In the sequel, we will bound the terms P (At), P (Bt), and P (Ct), separately.
1. Upper bound P (Bt). Before continuing, let us state a simple technical lemma that is useful for our proof, whose proof can be found in (Mei et al., 2016).
Lemma 6. LetM ∈ Rd×d be a symmetric d× d matrix and V be an -cover of unit-Euclideannorm ball B (0, 1), then
‖M‖ ≤ 1 1− 2 sup v∈V | 〈v,Mv〉 |. (52)
Let V 1 4
be a (
1 4 ) -cover of the ball B(0, 1) = {W ∈ Rd×K : ‖W ‖F = 1}, where log |V 1 4 | ≤
dK log 12. From Lemma 6, we know that∥∥∥∥∥ 1n n∑ i=1 ∇2` (W ;xi)− E [ ∇2` (W ;x) ]∥∥∥∥∥ ≤ 2 supv∈V 1 4 ∣∣∣∣∣ 〈 v, ( 1 n n∑ i=1 ∇2` (W ;xi)− E [ ∇2` (W ;x) ]) v 〉∣∣∣∣∣ . (53) Taking the union bound overW and V 1 4 yields
P (Bt) ≤ P  sup W∈W ,v∈V 1
4
∣∣∣∣∣ 1n n∑ i=1 〈 v, ( ∇2` (W ;xi)− E [ ∇2` (W ;x) ]) v 〉∣∣∣∣∣ ≥ t6  ≤ edK(log 3r +log 12) sup
W∈W ,v∈V 1 4
P (∣∣∣∣∣ 1n n∑ i=1 〈 v, ( ∇2` (W ;xi)− E [ ∇2` (W ;x) ]) v 〉∣∣∣∣∣ ≥ t6 ) .
(54)
LetGi = 〈 v, ( ∇2` (W ;xi)− E [ ∇2` (W ;x) ]) v 〉 where E[Gi] = 0. Let a = [ a>1 , · · · ,a>K ] ∈ RdK . Then we can show that ‖Gi‖ψ1 is upper bounded, which we summariz as follows. Lemma 7. There exists some constant C such that
‖Gi‖ψ1 ≤ C :≡ τ2.
Applying the Bernstein inequality for sub-exponential random variables (Mei et al., 2016, Theorem 9) to (54), we have for fixedW ∈ W ,v ∈ V 1
4 ,
P (∣∣∣∣∣ 1n n∑ i=1 〈 v, ( ∇2` (W ;xi)− E [ ∇2` (W ;x) ]) v 〉∣∣∣∣∣ ≥ t6 ) ≤ 2 exp ( −c · n ·min ( t2 τ4 , t τ2 )) , (55) for some universal constant c. As a result,
P (Bt) ≤ 2 exp ( −c · n ·min ( t2
τ4 , t τ2
) + dK log 3r + dK log 12 ) . (56)
Thus as long as
t > C ·max  √ τ4 ( dK log 36r + log 4 δ ) n , τ2 ( dK log 36r + log 4 δ ) n  (57) for some large enough constant C, we have P (Bt) ≤ δ2 .
2. Upper bound P (At) and P (Ct). These two events will be bounded in a similar way. Let J? satisfy
E [ sup
W 6=W ′∈B(W ?,r) ‖∇2` (W ,x)−∇2` (W ′,x) ‖ ‖W −W ′‖F
] ≤ J?. (58)
Let us look at the deterministic event Ct first. Since
sup W∈B(W ?,r)
‖E [ ∇2` ( Wj(W );x )] − E [ ∇2` (W ;x) ] ‖
≤ sup W∈B(W ?,r)
‖E [ ∇2` ( Wj(W );x )] − E [ ∇2` (W ;x) ] ‖
‖W −Wj(W )‖F · sup W∈B(W ?,r) ‖W −Wj(W )‖F
≤ J? · . (59)
Therefore, Ct holds as long as t ≥ 3J? · . (60)
We can bound the event At as below.
P (At) = P ( sup
W∈B(W ?,r)
1
n ∥∥∥∥∥ n∑ i=1 [ ∇2` (W ;xi)−∇2` ( Wj(W );xi )]∥∥∥∥∥ ≥ t3 )
≤ 3 t E
[ sup
W∈B(W ?,r) ∥∥∥∥∥ 1n n∑ i=1 [ ∇2` (W ;xi)−∇2` ( Wj(W );xi )]∥∥∥∥∥ ]
(61)
≤ 3 t E
[ sup
W∈B(W ?,r)
∥∥∇2` (W ;xi)−∇2` (Wj(W );xi)∥∥ ]
≤ 3 t E
[ sup
W∈B(W ?,r)
‖∇2` (W ;xi)−∇2` ( Wj(W );xi ) ‖
‖W −Wj(W )‖F
] · sup W∈B(W ?,r) ‖W −Wj(W )‖F
≤ 3J? t
(62)
where (61) follows from the Markov inequality. Thus, taking
t ≥ 6 J? δ
(63)
ensures that P (At) ≤ δ2 . It now boils down to control the quantity J?, which we have the following lemma, whose proof is in Appendix E.3.
Lemma 8. There exists some constant C such that
E [ sup
W 6=W ′∈B(W ?,r) ‖∇2` (W ,x)−∇2` (W ′,x) ‖ ‖W −W ′‖F
] ≤ C · d √ K ≡ J?. (64)
3. Final step. Let = δτ 2 6J?·ndK , δ = d −10 plugging into (57) we need
t > τ2 ·max  1ndK ,C · √( dK log(36rnd11K) + log 4δ ) n , ( dK log(36rnd11K) + log 4δ ) n  . (65) Since the middle term can be expressed as
dK log(36rnd11K) + 10 log d
n ≤ dK log n n + dK log 36r n + 11dK log dK n + 10 log d n , (66)
when n ≥ C · dK log dK for some large enough constant C, the first term, dK log n dominants and is on the order of dK log dK. Moreover, it decreases as n increases when n ≥ 3. Thus we can set
t ≥ τ2 √( dK log(36rnd11K) + log 4δ )
n (67) which holds as t ≥ C ′ · τ2 √
dK logn n for some constant C ′.
By setting t := Cτ2 √
dK logn n for sufficiently large C, as long as n ≥ C ′ · dK log dK,
P ( sup
W∈B(W ?,r) ‖∇2fn (W )−∇2f(W )‖ ≥ Cτ2
√ dK log n
n
) ≤ d−10. (68)
D.5 PROOF OF LEMMA 4
Proof. We nedd the following Lemma for the proof. Lemma 9 Lemma 9. Assume x ∼ N (0, I). Let u be a fixed unit norm vector u = [ u>1 , · · · ,u>K ] ∈ RdK with ‖u‖2 = 1, the following ‖u>∇` (W ;x) ‖ψ2 ≤ √ K,
hold.
By a similar argument (details omitted) as the proof of Lemma 3, and applies Lemma 9, we can get the following concentration inequality:
sup W∈B(W ?,r)
‖∇fn (W )−∇f (W ) ‖2 ≤ C ·
√ d √ K log n
n , (69)
holds with probability at least 1− d−10, as long as the sample size n ≥ C · dK log(dK).

heading: E PROOF OF AUXILIARY LEMMAS

text:
E.1 PROOF OF LEMMA 5
Proof. We can rewrite the left-hand side as
E  1 K2 K∑ i=1 K∑ j=1 φ ( w>i x ) ( 1− φ ( w>j x ))−z , (70)
which is upper bounded by E [
1 K2 ∑K i=1 ∑K j=1 ( φ ( w>i x ) ( 1− φ ( w>j x )))−z] , since f (x) = x−z
is convex for x > 0 and z ≥ 1. And apply Cauchy-Schwarz inequality we can have E [( φ ( w>i x ) ( 1− φ ( w>j x )))−z] ≤√E [φ (w>i x)−2z] ·√E [(1− φ (w>j x))−2z]. (71) Further since 1φ(x) = 1 + e −x, 11−φ(x) = 1 + e x and g = w>i x ∼ N ( 0, σ2i = ‖wi‖22 ) , then we can exactly calculate the two terms in the above equation, i.e.,
E [ φ (g) −2z ] = E [( 1 + e−g )2z] = E [ 2z∑ l=0 ( 2z l ) e−lg ] = 2z∑ l=0 ( 2z l ) e ( σ2i l 2 2 ) , (72)
and in the same way,
E [ (1− φ (g))−2z ] = E [ (1 + eg) 2z ] = 2z∑ l=0 ( 2z l ) e ( σ2i l 2 2 ) , (73)
since g is a Gaussian random which is a symmetric random variable. Plugging this back into (71) we can conclude that for t = max (‖w1‖2, · · · , ‖wK‖2) and p ≥ 1,
E  1 1 K ∑K i=1 φ ( w>i x ) ( 1− 1K ∑K i=1 φ ( w>i x )) p ≤ C · et2 , (74)
holds.
E.2 PROOF OF LEMMA 7
Proof. The sub-exponential norm of Gi can be bounded as ‖Gi‖ψ1 ≤ ‖ 〈 u,∇2` (W ; z)u 〉 ‖ψ1 + ‖∇2f (W ; z) ‖,
where ‖∇2f (W ; z) ‖ is upper bounded by CK according to lemma 2, and denote the (j, l)-th block of∇2` (W ; z) as αj,l · xx>, we can write
‖ 〈 u,∇2` (W ; z)u 〉 ‖ψ1 ≤ K∑ l=1 K∑ j=1 ‖αj,l · u>j xx>ul‖ψ1
≤ K∑ l=1 K∑ j=1 sup t≥1 t−1 ( E ∣∣αj,l · u>j xx>ul∣∣t) 1t . (75)
Note that
• for j 6= l
αj,l = 1
K2
φ′ ( w>j x ) φ′ ( w>l x ) · ( p (W ) 2 + y − 2y · p (W ) ) (p (W ) (1− p (W )))2 ,
(76)
further since
p (W ) 2 + y − 2y · p (W ) ≤
{ p (W )
2 p (W ) > 12
(1− p (W ))2 p (W ) ≤ 12 , (77)
then
|αj,l| ≤  1 K2 φ′(w>j x)φ ′(w>l x) (1−p(W ))2 p (W ) > 1 2
1 K2
φ′(w>j x)φ ′(w>l x)
p(W )2 p (W ) ≤ 12
, (78)
moreover,
p (W ) 2 =
( 1
K K∑ i=1 φ ( w>i x ))2 ≥ 1 K2 φ ( w>j x ) φ ( w>l x ) (1− p (W ))2 = ( 1− 1
K K∑ i=1 φ ( w>i x ))2 ≥ 1 K2 ( 1− φ ( w>j x )) ( 1− φ ( w>l x )) and recall that φ (x) (1− φ (x)) = φ′ (x), together we can obtain
|αj,l| ≤ { φ ( w>j x ) φ ( w>l x ) ≤ 1 p (W ) > 12(
1− φ ( w>j x )) · ( 1− φ ( w>l x )) ≤ 1 p (W ) ≤ 12 . (79)
• for j = l:
|αj,j | ≤ ∣∣∣∣∣∣ 1K2 φ′ ( w>j x ) φ′ ( w>l x ) · ( p (W ) 2 + y − 2y · p (W ) ) (p (W ) (1− p (W )))2 ∣∣∣∣∣∣ + ∣∣∣∣∣ 1K φ′′ ( w>j x ) (y − p (W )) p (W ) (1− p (W ))
∣∣∣∣∣ , (80) the first term is upper bounded by a constant, and for the second term∣∣∣∣∣φ′′ ( w>j x ) ( 1{y=1} − p (W ) ) p (W ) (1− p (W )) ∣∣∣∣∣ ≤
φ′′(w>j x) (1−p(W )) ≤ K y = 0 φ′′(w>j x) p(W ) ≤ K y = 1 , (81)
where we have used the fact that the second derivative is φ′′ (x) = φ (x) (1− φ (x)) (1− 2φ (x)), the absolute value of which can be upper bounded by φ (x) or 1− φ (x). Thus we can show that
|αj,j | ≤ C. (82)
Finally, we conclude that
|αj,l| ≤ C, (83) holds for all j, l. And
‖ 〈 u,∇2` (W ; z)u 〉 ‖ψ1 ≤ C · K∑ l=1 K∑ j=1 sup t≥1 t−1E [ | ( u>j xx >ul| )t] 1t
(84)
≤ C · K∑ l=1 K∑ j=1 sup t≥1 t−1 (√ E [( u>j x )2t] ·√E [(u>l x)2t] ) 1 t (85) ≤ C · K∑ l=1 K∑ j=1 ‖uj‖2‖ul‖2 · sup p≥1 t−1 ((2t− 1)!!) 1 t (86) ≤ C K∑ l=1 K∑ j=1 ‖uj‖2‖ul‖2 (87) ≤ C K∑ l=1 K∑ j=1 ‖uj‖22 + ‖ul‖22 2 (88)
≤ C :≡ τ2 (89) Thus we can conclude that
‖Gi‖ψ1 ≤ C :≡ τ2
E.3 PROOF OF LEMMA 8
Proof. As noted before, we can write the (j, l)-th block of ∇2` (W ; z) as gj,l (W )xx>, where
gj,l (W ) = ξj,l (W )
(p (W ) (1− p (W )))2 , (90)
then we can obtain the following bound,
‖∇2` (W ; z)−∇2` (W ′; z) ‖ ≤ K∑ j=1 K∑ l=1 |gj,l (W )− gj,l (W ′) | · ‖xx>‖. (91)
Using the same method as shown in the proof of Lemma 1, we can upper bound |gj,l (W )−gj,l (W ′) | as
|gj,l (W )− gj,l (W ′) | ≤ 1 K2 1( p ( W̃ )( 1− p ( W̃ )))6 · ‖x‖2 · √K · ‖W −W ′‖F (92)
where W̃ = ηW + (1− η)W ′ for η ∈ (0, 1). And thus, when ‖W −W ′‖F ≤ 0.7 we have
E [ sup
W 6=W ′ ‖∇2` (W )−∇2` (W ′) ‖ ‖W −W ′‖F ] ≤ C K 3 2 ·K2 · E  1( p ( W̃ )( 1− p ( W̃ )))6 · ‖x‖2 · ‖xx>‖  ≤ C · d √ K (93)
Thus we only need to set J? ≥ C · d √ K for some large enough C.
E.4 PROOF OF LEMMA 9
Proof. By definition, we have
〈∇` (W ) ,u〉 = K∑ k=1 〈 ∂` (W ) ∂wk ,uk 〉
= 1
K K∑ k=1
 ( y − 1K ∑K i=1 φ ( w>i x )) · φ′ ( w>k x ) 1 K ∑K i=1 φ ( w>i x ) ( 1− 1K ∑K i=1 φ ( w>i x )) (u>k x) ,
and then we can upper bound the sub-gaussian norm as
‖ 〈∇` (W ) ,u〉 ‖ψ2 ≤  1 K ∑K k=1 ∥∥∥∥ φ′(w>k x)·u>k x(1− 1K ∑Ki=1 φ(w>i x))u>k x ∥∥∥∥ ψ2 ≤ ∑K k=1 ‖u>k x‖ψ2 y = 0
1 K ∑K k=1 ∥∥∥∥ φ′(w>k x)·u>k x1 K ∑K i=1 φ(w>i x) u>k x ∥∥∥∥ ψ2 ≤ ∑K k=1 ‖u>k x‖ψ2 y = 1 .
Thus we can have
‖ 〈∇` (W ) ,u〉 ‖ψ2 ≤ K∑ k=1 ‖uk‖2 √ K, (94)
and conclude that the directional gradient is √ K-sub-Gaussian.


summaries: This paper proposed a feature boosting and suppression method for dynamic channel pruning. To be specific, the proposed method firstly predicts the importance of each channel and then use an affine function to amplify/suppress the importance of different channels. However, the idea of dynamic channel pruning is not novel. Moreover, the comparisons in the experiments are quite limited.

summaries: This manuscript presents a nice method that can dynamically prune some channels in a CNN network to speed up the training. The main strength of the proposed method is to determine which channels to be suppressed based upon each data sample without incurring too much computational burden or too much memory consumption.  The good thing is that the proposed pruning strategy does not result in a big performance decrease. Overall, this is a nicely written paper and may be empirically useful for training a very large CNN. Nevertheless, the authors did not present a real-world application in which it is important to speed up by 2 or 3 times at a small cost, so it is hard to judge the real impact of the proposed method.

abstractText: Making deep convolutional neural networks more accurate typically comes at the cost of increased computational and memory resources. In this paper, we reduce this cost by exploiting the fact that the importance of features computed by convolutional layers is highly input-dependent, and propose feature boosting and suppression (FBS), a new method to predictively amplify salient convolutional channels and skip unimportant ones at run-time. FBS introduces small auxiliary connections to existing convolutional layers. In contrast to channel pruning methods which permanently remove channels, it preserves the full network structures and accelerates convolution by dynamically skipping unimportant input and output channels. FBS-augmented networks are trained with conventional stochastic gradient descent, making it readily available for many state-of-the-art CNNs. We compare FBS to a range of existing channel pruning and dynamic execution schemes and demonstrate large improvements on ImageNet classification. Experiments show that FBS can respectively provide 5× and 2× savings in compute on VGG-16 and ResNet-18, both with less than 0.6% top-5 accuracy loss.

authors:
Amjad Almahairi
Nicolas Ballas
Tim Cooijmans
Yin Zheng
Hugo Larochelle
Aaron Courville

title: Dynamic capacity networks

venue: In Proceedings of the 33rd International Conference on International Conference on Machine Learning (ICML),

authors:
Jose M Alvarez
Mathieu Salzmann

title: Learning the number of neurons in deep networks

venue: Advances in Neural Information Processing Systems (NIPS),

authors:
Tolga Bolukbasi
Joseph Wang
Ofer Dekel
Venkatesh Saligrama

title: Adaptive neural networks for efficient inference

venue: In Proceedings of the 34th International Conference on Machine Learning (ICML),

authors:
J. Deng
W. Dong
R. Socher
L.-J. Li
K. Li
L. Fei-Fei

title: ImageNet: A large-scale hierarchical image database

venue: In IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Xuanyi Dong
Junshi Huang
Yi Yang
Shuicheng Yan

title: More is less: A more complicated network with less inference complexity

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Michael Figurnov
Maxwell D. Collins
Yukun Zhu
Li Zhang
Jonathan Huang
Dmitry Vetrov
Ruslan Salakhutdinov

title: Spatially adaptive computation time for residual networks

authors:
Mikhail Figurnov
Aizhan Ibraimova
Dmitry P Vetrov
Pushmeet Kohli

title: PerforatedCNNs: Acceleration through elimination of redundant convolutions

venue: In Advances in Neural Information Processing Systems (NIPS),

authors:
Yiwen Guo
Anbang Yao
Yurong Chen

title: Dynamic network surgery for efficient DNNs

authors:
Song Han
Xingyu Liu
Huizi Mao
Jing Pu
Ardavan Pedram
Mark A Horowitz
William J Dally

title: Eie: efficient inference engine on compressed deep neural network

venue: In Computer Architecture (ISCA),

authors:
Babak Hassibi
David G. Stork
Gregory Wolff

title: Optimal brain surgeon: Extensions and performance comparisons

title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification

venue: In Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV),

title: Deep residual learning for image recognition

venue: In IEEE Conference on Computer Vision and Pattern Recognition

authors:
Yang He
Guoliang Kang
Xuanyi Dong
Yanwei Fu
Yi Yang

title: Soft filter pruning for accelerating deep convolutional neural networks

venue: In International Joint Conference on Artificial Intelligence (IJCAI),

authors:
Yihui He
Xiangyu Zhang
Jian Sun

title: Channel pruning for accelerating very deep neural networks

venue: IEEE International Conference on Computer Vision (ICCV),

authors:
Yihui He
Ji Lin
Zhijian Liu
Hanrui Wang
Li-Jia Li
Song Han

title: AMC: AutoML for model compression and acceleration on mobile devices

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

authors:
J. Huang
V. Rathod
C. Sun
M. Zhu
A. Korattikara
A. Fathi
I. Fischer
Z. Wojna
Y. Song
S. Guadarrama
K. Murphy

title: Speed/accuracy trade-offs for modern convolutional object detectors

authors:
Qiangui Huang
Kevin Zhou
Suya You
Ulrich Neumann

title: Learning to prune filters in convolutional neural networks

venue: In IEEE Winter Conference on Computer Vision

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: In Proceedings of the 32Nd International Conference on International Conference on Machine Learning (ICML),

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

venue: In Advances in Neural Information Processing Systems (NIPS)

authors:
Alex Krizhevsky
Vinod Nair
Geoffrey Hinton

title: The CIFAR-10 and CIFAR-100 datasets

authors:
Yann LeCun
John S. Denker
Sara A. Solla

title: Optimal brain damage

authors:
Hao Li
Asim Kadav
Igor Durdanovic
Hanan Samet
Hans Peter Graf

title: Pruning filters for efficient convnets

authors:
Ji Lin
Yongming Rao
Jiwen Lu
Jie Zhou

title: Runtime neural pruning

authors:
Lanlan Liu
Jia Deng

title: Dynamic deep neural networks: Optimizing accuracy-efficiency trade-offs by selective

authors:
Zhuang Liu
Jianguo Li
Zhiqiang Shen
Gao Huang
Shoumeng Yan
Changshui Zhang

title: Learning efficient convolutional networks through network slimming

venue: In International Conference on Computer Vision (ICCV),

authors:
J. Long
E. Shelhamer
T. Darrell

title: Fully convolutional networks for semantic segmentation

venue: In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Jian-Hao Luo
Jianxin Wu
Weiyao Lin

title: ThiNet: A filter level pruning method for deep neural network compression

venue: In ICCV,

authors:
Augustus Odena
Dieterich Lawson
Christopher Olah

title: Changing model behavior at test-time using reinforcement learning

authors:
Angshuman Parashar
Minsoo Rhu
Anurag Mukkara
Antonio Puglielli
Rangharajan Venkatesan
Brucek Khailany
Joel Emer
Stephen W Keckler
William J Dally

title: Scnn: An accelerator for compressed-sparse convolutional neural networks

venue: In ACM SIGARCH Computer Architecture News,

authors:
Mengye Ren
Andrei Pokrovsky
Bin Yang
Raquel Urtasun

title: SBNet: Sparse blocks network for fast inference

authors:
S. Ren
K. He
R. Girshick
J. Sun

title: Faster R-CNN: Towards real-time object detection with region proposal networks

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

authors:
Noam Shazeer
Azalia Mirhoseini
Krzysztof Maziarz
Andy Davis
Quoc Le
Geoffrey Hinton
Jeff Dean

title: Outrageously large neural networks: The sparsely-gated mixture-ofexperts

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: In International Conference on Learning Representations (ICLR),

authors:
Rupesh Kumar Srivastava
Jonathan Masci
Faustino J. Gomez
Jürgen Schmidhuber

title: Understanding locally competitive networks

authors:
Wei Wen
Chunpeng Wu
Yandan Wang
Yiran Chen
Hai Li

title: Learning structured sparsity in deep neural networks

authors:
Zuxuan Wu
Tushar Nagarajan
Abhishek Kumar
Steven Rennie
Larry S. Davis
Kristen Grauman
Rogerio Feris

title: BlockDrop: Dynamic inference paths in residual networks

authors:
Jianbo Ye
Xin Lu
Zhe L. Lin
James Z. Wang

title: Rethinking the smaller-norm-lessinformative assumption in channel pruning of convolution layers

authors:
Yiren Zhao
Xitong Gao
Robert Mullins
Chengzhong Xu

title: Mayo: A framework for autogenerating hardware friendly deep neural networks

venue: In Proceedings of 2nd International Workshop on Embedded and Mobile Deep Learning, EMDL ’18

authors:
Hao Zhou
Jose M. Alvarez
Fatih Porikli

title: Less is more: Towards compact cnns

venue: Computer Vision – ECCV

authors:
Zhuangwei Zhuang
Mingkui Tan
Bohan Zhuang
Jing Liu
Yong Guo
Qingyao Wu
Junzhou Huang
Jinhui Zhu

title: Discrimination-aware channel pruning for deep neural networks

venue: For NS,

venue: For image preprocessing,

heading: 1 Introduction

text:
State-of-the-art vision and image-based tasks such as image classification (Krizhevsky et al., 2012; Simonyan & Zisserman, 2015; He et al., 2016), object detection (Ren et al., 2017; Huang et al., 2017) and segmentation (Long et al., 2015) are all built upon deep convolutional neural networks (CNNs). While CNN architectures have evolved to become more efficient, the general trend has been to use larger models with greater memory utilization, bandwidth and compute requirements to achieve higher accuracy. The formidable amount of computational resources used by CNNs present a great challenge in the deployment of CNNs in both cost-sensitive cloud services and low-powered edge computing applications.
One common approach to reduce the memory, bandwidth and compute costs is to prune over-parameterized CNNs. If performed in a coarse-grain manner this approach is known as channel pruning (Ye et al., 2018; He et al., 2017; Liu et al., 2017; Wen et al., 2016). Channel pruning evaluates channel saliency measures and removes all input and output connections from unimportant channels— generating a smaller dense model. A saliency-based pruning method, however, has threefold disadvantages. Firstly, by removing channels, the capabilities of CNNs are permanently lost, and the resulting CNN may never regain its accuracy for difficult inputs for which the removed channels were responsible. Secondly, despite the fact that channel pruning may drastically shrink model size, without careful design, computational resources cannot be effectively reduced in a CNN without a detrimental impact on its accuracy. Finally, the saliency of a neuron is not static, which can be illustrated by the feature visualization in Figure 1. Here, a CNN is shown a set of input images, certain channel neurons in a convolutional output may get highly excited, whereas another set of
∗Equal contribution, corresponding authors.
images elicit little response from the same channels. This is in line with our understanding of CNNs that neurons in a convolutional layer specialize in recognizing distinct features, and the relative importance of a neuron depends heavily on the inputs.
The above shortcomings prompt the question: why should we prune by static importance, if the importance is highly input-dependent? Surely, a more promising alternative is to prune dynamically depending on the current input. A dynamic channel pruning strategy allows the network to learn to prioritize certain convolutional channels and ignore irrelevant ones. Instead of simply reducing model size at the cost of accuracy with pruning, we can accelerate convolution by selectively computing only a subset of channels predicted to be important at run-time, while considering the sparse input from the preceding convolution layer. In effect, the amount of cached activations and the number of read, write and arithmetic operations used by a well-designed dynamic model can be almost identical to an equivalently sparse statically pruned one. In addition to saving computational resources, a dynamic model preserves all neurons of the full model, which minimizes the impact on task accuracy.
In this paper, we propose feature boosting and suppression (FBS) to dynamically amplify and suppress output channels computed by the convolutional layer. Intuitively, we can imagine that the flow of information of each output channel can be amplified or restricted under the control of a “valve”. This allows salient information to flow freely while we stop all information from unimportant channels and skip their computation. Unlike pruning statically, the valves use features from the previous layer to predict the saliency of output channels. With conventional stochastic gradient descent (SGD) methods, the predictor can learn to adapt itself by observing the input and output features of the convolution operation.
FBS introduces tiny auxiliary connections to existing convolutional layers. The minimal overhead added to the existing model is thus negligible when compared to the potential speed up provided by the dynamic sparsity. Existing dynamic computation strategies in CNNs (Lin et al., 2017; Odena et al., 2017; Bolukbasi et al., 2017) produce on/off pruning decisions or execution path selections. Training them thus often resorts to reinforcement learning, which in practice is often computationally expensive. Even though FBS similarly use non-differentiable functions, contrary to these methods, the unified losses are still wellminimized with conventional SGD.
We apply FBS to a custom CIFAR-10 (Krizhevsky et al., 2014) classifier and popular CNN models such as VGG-16 (Simonyan & Zisserman, 2015) and ResNet-18 (He et al., 2016) trained on the ImageNet dataset (Deng et al., 2009). Empirical results show that under the same speed-ups, FBS can produce models with validation accuracies surpassing all other channel pruning and dynamic conditional execution methods examined in the paper.

heading: 2 Related Work

heading: 2.1 Structured Sparsity

text:
Since LeCun et al. (1990) introduced optimal brain damage, the idea of creating more compact and efficient CNNs by removing connections or neurons has received significant attention. Early literature on pruning deep CNNs zero out individual weight parameters (Hassibi et al., 1994; Guo et al., 2016). This results in highly irregular sparse connections, which were notoriously difficult for GPUs to exploit. This has prompted custom accelerator solutions that exploit sparse weights (Parashar et al., 2017; Han et al., 2016). Although supporting both sparse and dense convolutions efficiently normally involves some compromises in terms of efficiency or performance.
Alternatively, recent work has thus increasingly focused on introducing structured sparsity (Wen et al., 2016; Ye et al., 2018; Alvarez & Salzmann, 2016; Zhou et al., 2016), which can be exploited by GPUs and allows custom accelerators to focus solely on efficient dense operations. Wen et al. (2016) added group Lasso on channel weights to the model’s training loss function. This has the effect of reducing the magnitude of channel weights to diminish during training, and remove connections from zeroed-out channels. To facilitate this process, Alvarez & Salzmann (2016) additionally used proximal gradient descent, while Li et al. (2017) and He et al. (2018a) proposed to prune channels by thresholds, i.e. they set unimportant channels to zero, and fine-tune the resulting CNN. The objective to induce sparsity in groups of weights may present difficulties for gradient-based methods, given the large number of weights that need to be optimized. A common approach to overcome this is to solve (He et al., 2017) or learn (Liu et al., 2017; Ye et al., 2018) channel saliencies to drive the sparsification of CNNs. He et al. (2017) solved an optimization problem which limits the number of active convolutional channels while minimizing the reconstruction error on the convolutional output. Liu et al. (2017) used Lasso regularization on channel saliencies to induce sparsity and prune channels with a global threshold. Ye et al. (2018) learned to sparsify CNNs with an iterative shrinkage/thresholding algorithm applied to the scaling factors in batch normalization. There are methods (Luo et al., 2017; Zhuang et al., 2018) that use greedy algorithms for channel selection. Huang et al. (2018) and He et al. (2018b) adopted reinforcement learning to train agents to produce channel pruning decisions. PerforatedCNNs, proposed by Figurnov et al. (2016), use predefined masks that are model-agnostic to skip the output pixels in convolutional layers.

heading: 2.2 Dynamic Execution

text:
In a pruned model produced by structured sparsity methods, the capabilities of the pruned neurons and connections are permanently lost. Therefore, many propose to use dynamic networks as an alternative to structured sparsity. During inference, a dynamic network can use the input data to choose parts of the network to evaluate.
Convolutional layers are usually spatially sparse, i.e. their activation outputs may contain only small patches of salient regions. A number of recent publications exploit this for acceleration. Dong et al. (2017) introduced low-cost collaborative layers which induce spatial sparsity in cheap convolutions, so that the main expensive ones can use the same sparsity information. Figurnov et al. (2017) proposed spatially adaptive computation time for residual networks (He et al., 2016), which learns the number of residual blocks required to compute a certain spatial location. Almahairi et al. (2016) presented dynamic capacity networks, which use the gradient of a coarse output’s entropy to select salient locations in the input image for refinement. Ren et al. (2018) assumed the availability of a priori spatial sparsity in the input image, and accelerated the convolutional layer by computing non-sparse regions.
There are dynamic networks that make binary decisions or multiple choices for the inference paths taken. BlockDrop, proposed by Wu et al. (2018), trains a policy network to skip blocks in residual networks. Liu & Deng (2018) proposed conditional branches in deep neural networks (DNNs), and used Q-learning to train the branching policies. Odena et al. (2017) designed a DNN with layers containing multiple modules, and decided which module to use with a recurrent neural network (RNN). Lin et al. (2017) learned an RNN to
adaptively prune channels in convolutional layers. The on/off decisions commonly used in these networks cannot be represented by differentiable functions, hence the gradients are not well-defined. Consequently, the dynamic networks above train their policy functions by reinforcement learning. There exist, however, methods that workaround such limitations. Shazeer et al. (2017) introduced sparsely-gated mixture-of-experts and used a noisy ranking on the backpropagate-able gating networks to select the expensive experts to evaluate. Bolukbasi et al. (2017) trained differentiable policy functions to implement early exits in a DNN. Hua et al. (2018) learned binary policies that decide whether partial or all input channels are used for convolution, but approximate the gradients of the non-differentiable policy functions with continuous ones.

heading: 3 Feature Boosting and Suppression

text: We start with a high-level illustration (Figure 2) of how FBS accelerates a convolutional layer with batch normalization (BN). The auxiliary components (in red) predict the importance of each output channel based on the input features, and amplify the output features accordingly. Moreover, certain output channels are predicted to be entirely suppressed (or zero-valued as represented by ), such output sparsity information can advise the convolution operation to skip the computation of these channels, as indicated by the dashed arrow. It is notable that the expensive convolution can be doubly accelerated by skipping the inactive channels from both the input features and the predicted output channel saliencies. The rest of this section provides detailed explanation of the components in Figure 2.

heading: 3.1 Preliminaries

text:
For simplicity, we consider a deep sequential batch-normalized (Ioffe & Szegedy, 2015) CNN with L convolutional layers, i.e. xL = F (x0) = fL (· · · f2 (f1 (x0)) · · · ), where the lth layer fl : RCl−1×Hl−1×Wl−1 → RCl×Hl×Wl computes the features xl ∈ RCl×Hl×Wl , which comprise of Cl channels of features with height Hl and width Wl. The l th layer is thus defined as:
fl (xl−1) = (γl · norm (convl (xl−1,θl)) + βl)+ . (1)
Here, additions (+) and multiplications (·) are element-wise, (z)+ = max (z, 0) denotes the ReLU activation, γl,βl ∈ RCl are trainable parameters, norm (z) normalizes each channel of features z across the population of z, with µz,σ 2 z ∈ RCl respectively containing the population mean and variance of each channel, and a small prevents division by zero:
norm (z) = z− µz√ σ2z + . (2)
Additionally, convl (xl−1,θl) computes the convolution of input features xl−1 using the weight tensor θl ∈ RC l×Cl−1×k2 , where k is the kernel size. Specifically, FBS concerns the
optimization of convl (xl−1,θl) functions, as a CNN spends the majority of its inference time in them, using k2Cl−1ClHlWl multiply-accumulate operations (MACs) for the lth layer.

heading: 3.2 Designing a Dynamic Layer

text:
Consider the following generalization of a layer with dynamic execution:
f̂ (x, · · · ) = f (x,θ, · · · ) · π (x,φ, · · · ) , (3)
where f and π respectively use weight parameters θ and φ and may have additional inputs, and compute tensors of the same output shape, denoted by F and G. Intuitively, the expensive F[i] can always be skipped for any index i whenever the cost-effective G[i] evaluates to 0. Here, the superscript [i] is used to index the ith slice of the tensor. For example, if we have features F ∈ RC×H×W containing C channels of H-by-W features, F[c] ∈ RH×W retrieves the cth feature image. We can further sparsify and accelerate the layer by adding, for instance, a Lasso on π to the total loss, where Ex [z] is the expectation of z over x:
R (x) = Ex [‖π (x,φ, · · · )‖1] , (4)
Despite the simplicity of this formulation, it is however very tricky to design f̂ properly. Under the right conditions, we can arbitrarily minimize the Lasso while maintaining the same output from the layer by scaling parameters. For example, in low-cost collaborative layers (Dong et al., 2017), f and π are simply convolutions (with or without ReLU activation) that respectively have weights θ and φ. Since f and π are homogeneous functions, one can always halve φ and double θ to decrease (4) while the network output remains the same. In other words, the optimal network must have ‖φ‖∞ → 0, which is infeasible in finiteprecision arithmetic. For the above reasons, Dong et al. (2017) observed that the additional loss in (4) always degrades the CNN’s task performance. Ye et al. (2018) pointed out that gradient-based training algorithms are highly inefficient in exploring such reparameterization patterns, and channel pruning methods may experience similar difficulties. Shazeer et al. (2017) avoided this limitation by finishing π with a softmax normalization, but (4) can no longer be used as the softmax renders the `1-norm, which now evaluates to 1, useless. In addition, similar to sigmoid, softmax (without the cross entropy) is easily saturated, and thus may equally suffer from vanishing gradients. Many instead design π to produce on/off decisions and train them with reinforcement learning as discussed in Section 2.

heading: 3.3 Feature Boosting and Suppression with Channel Saliencies

text:
Instead of imposing sparsity on features or convolutional weight parameters (e.g. Wen et al. (2016); Alvarez & Salzmann (2016); Li et al. (2017); He et al. (2018a)), recent channel pruning methods (Liu et al., 2017; Ye et al., 2018) induce sparsity on the BN scaling factors γl. Inspired by them, FBS similarly generates a channel-wise importance measure. Yet contrary to them, instead of using the constant BN scaling factors γl, we predict channel importance and dynamically amplify or suppress channels with a parametric function π(xl−1) dependent on the output from the previous layer xl−1. Here, we propose to replace the layer definition fl (xl−1) for each of l ∈ [1, L] with f̂l (xl−1) which employs dynamic channel pruning:
f̂l (xl−1) = (πl (xl−1) · (norm (convl (xl−1,θl)) + βl))+ , (5)
where a low-overhead policy πl (xl−1) evaluates the pruning decisions for the computationally demanding conv (xl−1,θl):
πl (xl−1) = wtaddCle (gl (xl−1)) . (6)
Here, wtak(z) is a k-winners-take-all function, i.e. it returns a tensor identical to z, except that we zero out entries in z that are smaller than the k largest entries in absolute magnitude. In other words, wtaddCle(gl(xl−1)) provides a pruning strategy that computes only ddCle most salient channels predicted by gl(xl−1), and suppresses the remaining channels with zeros. In Section 3.4, we provide a detailed explanation of how we design a cheap gl(xl−1) that learns to predict channel saliencies.
It is notable that our strategy prunes Cl − ddCle least salient output channels from lth layer, where the density d ∈ ]0, 1] can be varied to sweep the trade-off relationship between performance and accuracy. Moreover, pruned channels contain all-zero values. This allows the subsequent (l + 1) th layer to trivially make use of input-side sparsity, since all-zero features can be safely skipped even for zero-padded layers. Because all convolutions can exploit both input- and output-side sparsity, the speed-up gained from pruning is quadratic with respect to the pruning ratio. For instance, dynamically pruning half of the channels in all layers gives rise to a dynamic CNN that uses approximately 14 of the original MACs.
Theoretically, FBS does not introduce the reparameterization discussed in Section 3.2. By batch normalizing the convolution output, the convolution kernel θl is invariant to scaling. Computationally, it is more efficient to train. Many alternative methods use nondifferentiable π functions that produce on/off decisions. In general, DNNs with these policy functions are incompatible with SGD, and resort to reinforcement learning for training. In contrast, (6) allows end-to-end training, as wta is a piecewise differentiable and continuous function like ReLU. Srivastava et al. (2015) suggested that in general, a network is easier and faster to train for complex tasks and less prone to catastrophic forgetting, if it uses functions such as wta that promote local competition between many subnetworks.

heading: 3.4 Learning to Predict Channel Saliencies

text:
This section explains the design of the channel saliency predictor gl(xl−1). To avoid significant computational cost in gl, we subsample xl−1 by reducing the spatial dimensions of each channel to a scalar using the following function ss : RC×H×W → RC :
ss (xl−1) = 1
HW
[ s ( x [1] l−1 ) s ( x [2] l−1 ) · · · s ( x [C] l−1 )] , (7)
where s ( x [c] l−1 ) reduces the cth channel of z to a scalar using, for instance, the `1-norm ‖x[c]l−1‖1, `2-norm, `∞-norm, or the variance of x [c] l−1. The results in Section 4 use the `
1- norm by default, which is equivalent to global average pooling for the ReLU activated xl−1. We then design gl(xl−1) to predict channel saliencies with a fully connected layer following the subsampled activations ss (xl−1), where φl ∈ RC l×Cl−1 is the weight tensor of the layer:
gl (xl−1) = (ss (xl−1)φl + ρl)+ . (8)
We generally initialize ρl with 1 and apply He et al. (2015)’s initialization to φl. Similar to how Liu et al. (2017) and Ye et al. (2018) induced sparsity in the BN scaling factors, we regularize all layers with the Lasso on gl(xl−1): λ ∑L
l=1 Ex [‖gl(xl−1)‖1] in the total loss, where λ = 10−8 in our experiments.

heading: 4 Experiments

text:
We ran extensive experiments on CIFAR-10 (Krizhevsky et al., 2014) and the ImageNet ILSVRC2012 (Deng et al., 2009), two popular image classification datasets. We use MCifarNet (Zhao et al., 2018), a custom 8-layer CNN for CIFAR-10 (see Appendix A for its structure), using only 1.3 M parameters with 91.37% and 99.67% top-1 and top-5 accuracies respectively. M-CifarNet is much smaller than a VGG-16 on CIFAR-10 (Liu et al., 2017), which uses 20 M parameters and only 2.29% more accurate. Because of its compactness, our CNN is more challenging to accelerate. By faithfully reimplementing Network Slimming (NS) (Liu et al., 2017), we closely compare FBS with NS under various speedup constraints. For ILSVRC2012, we augment two popular CNN variants, ResNet-18 (He et al., 2016) and VGG-16 (Simonyan & Zisserman, 2015), and provide detailed accuracy/MACs trade-off comparison against recent structured pruning and dynamic execution methods.
Our method begins by first replacing all convolutional layer computations with (5), and initializing the new convolutional kernels with previous parameters. Initially, we do not suppress any channel computations by using density d = 1 in (6) and fine-tune the resulting network. For fair comparison against NS, we then follow Liu et al. (2017) by iteratively decrementing the overall density d of the network by 10% in each step, and thus gradually
using fewer channels to sweep the accuracy/performance trade-off. The difference is that NS prunes channels by ranking globally, while FBS prunes around 1− d of each layer.

heading: 4.1 CIFAR-10

text:
By respectively applying NS and FBS to our CIFAR-10 classifier and incrementally increasing sparsity, we produce the trade-off relationships between number of operations (measured in MACs) and the classification accuracy as shown in Figure 3a. FBS clearly surpasses NS in its ability to retain the task accuracy under an increasingly stringent computational budget. Besides comparing FBS against NS, we are interested in combining both methods, which demonstrates the effectiveness of FBS if the model is already less redundant, i.e. it cannot be pruned further using NS without degrading the accuracy by more than 1%. The composite method (NS+FBS) is shown to successfully regain most of the lost accuracy due to NS, producing a trade-off curve closely matching FBS. It is notable that under the same 90.50% accuracy constraints, FBS, NS+FBS, and NS respectively achieve 3.93×, 3.22×, and 1.19× speed-up ratios. Conversely for a 2× speed-up target, they respectively produce models with accuracies not lower than 91.55%, 90.90% and 87.54%.
Figure 3b demonstrates that our FBS can effectively learn to amplify and suppress channels when dealing with different input images. The 8 heat maps respectively represent the channel skipping probabilities of the 8 convolutional layers. The brightness of the pixel at location (x, y) denotes the probability of skipping the xth channel when looking at an image of the yth category. The heat maps verify our belief that the auxiliary network learned to predict which channels specialize to which features, as channels may have drastically distinct probabilites of being used for images of different categories. The model here is a M-CifarNet using FBS with d = 0.5, which has a top-1 accuracy of 90.59% (top-5 99.65%). Moreover, channels in the heat maps are sorted so the channels that are on average least frequently evaluated are placed on the left, and channels shaded in stripes are never evaluated. The network in Figure 3b is not only approximately 4× faster than the original, by removing the unused channels, we also reduce the number of weights by 2.37×. This reveals that FBS naturally subsumes channel pruning strategies such as NS, as we can simply prune away channels that are skipped regardless of the input. It is notable that even though we specified a universal density d, FBS learned to adjust its dynamicity across all layers, and prune different ratios of channels from the convolutional layers.

heading: 4.2 ImageNet ILSVRC2012 Classification

text:
By applying FBS and NS respectively to ResNet-18, we saw that the ILSVRC2012 validation accuracy of FBS consistently outperforms NS under different speed-up constraints (see Appendix B for the implementation details and trade-off curves). For instance, at d = 0.7, it utilizes only 1.12 G MACs (1.62× fewer) to achieve a top-1 error rate of 31.54%, while NS requires 1.51 G MACs (1.21× fewer) for a similar error rate of 31.70%. When compared
across recent dynamic execution methods examined in Table 1, FBS demonstrates simultaneously the highest possible speed-up and the lowest error rates. It is notable that the baseline accuracies for FBS refer to a network that has been augmented with the auxiliary layers featuring FBS but suppress no channels, i.e. d = 1. We found that this method brings immediate accuracy improvements, an increase of 1.73% in top-1 and 0.46% in top-5 accuracies, to the baseline network, which is in line with our observation on M-CifarNet.
In Table 2, we compare different structured pruning and dynamic execution methods to FBS for VGG-16 (see Appendix B for the setup). At a speed-up of 3.01×, FBS shows a minimal increase of 0.44% and 0.04% in top-1 and top-5 errors respectively. At 5.23× speed-up, it only degrades the top-1 error by 1.08% and the top-5 by 0.59%.
Not only does FBS use much fewer MACs, it also demonstrates significant reductions in bandwidth and memory requirements. In Table 3, we observe a large reduction in the number of memory accesses in single image inference as we simply do not access suppressed weights and activations. Because these memory operations are often costly DRAM accesses, minimizing them leads to power-savings. Table 3 further reveals that in diverse application scenarios such as low-end and cloud environments, the peak memory usages by the optimized models are much smaller than the originals, which in general improves cache utilization.

heading: 5 Conclusion

text:
In summary, we proposed feature boosting and suppression that helps CNNs to achieve significant reductions in the compute required while maintaining high accuracies. FBS fully
preserves the capabilities of CNNs and predictively boosts important channels to help the accelerated models retain high accuracies. We demonstrated that FBS achieves around 2× and 5× savings in computation respectively on ResNet-18 and VGG-16 within 0.6% loss of top-5 accuracy. Under the same performance constraints, the accuracy gained by FBS surpasses all recent structured pruning and dynamic execution methods examined in this paper. In addition, it can serve as an off-the-shelf technique for accelerating many popular CNN networks and the fine-tuning process is unified in the traditional SGD which requires no algorithmic changes in training. Finally, the implementation of FBS and the optimized networks are fully open source and released to the public1.

heading: Acknowledgements

text: This work is supported in part by the National Key R&D Program of China (No. 2018YFB1004804), the National Natural Science Foundation of China (No. 61806192). We thank EPSRC for providing Yiren Zhao his doctoral scholarship.

heading: A Details of M-CifarNet on CIFAR-10

text:
For the CIFAR-10 classification task, we use M-CifarNet, a custom designed CNN, with less than 1.30 M parameters and takes 174 M MACs to perform inference for a 32-by-32 RGB image. The architecture is illustrated in Table 4, where all convolutional layers use 3 × 3 kernels, the Shape column shows the shapes of each layer’s features, and pool7 is a global average pooling layer.
We trained M-CifarNet (see Appendix A) with a 0.01 learning rate and a 256 batch size. We reduced the learning rate by a factor of 10× for every 100 epochs. To compare FBS against NS fairly, every model with a new target MACs budget were consecutively initialized with the previous model, and trained for a maximum of 300 epochs, which is enough for all models to converge to the best obtainable accuracies. For NS, we follow Liu et al. (2017) and start training with an `1-norm sparsity regularization weighted by 10−5 on the BN scaling factors. We then prune at 150 epochs and fine-tune the resulting network without the sparsity regularization.
We additionally employed image augmentation procedures from Krizhevsky et al. (2012) to preprocess each training example. Each CIFAR-10 example was randomly horizontal flipped and slightly perturbed in the brightness, saturation and hue.
Table 4 additionally provides further comparisons of layer-wise compute costs between FBS, NS, and the composition of the two methods (NS+FBS). It is notable that the FBS column has two different output channel counts, where the former is the number of computed channels for each inference, and the latter is the number of channels remaining in the layer after removing the unused channels.
Figure 4 shows how the skipping probabilites heat maps of the convolutional layer conv4 evolve as we fine-tune FBS-augmented M-CifarNet. The network was trained for 12 epochs, and we saved the model at every epoch. The heat maps are generated with the saved models in sequence, where we apply the same reordering to all heat map channels with the sorted result from the first epoch. It can be observed that as we train the network, the channel skipping probabilites become more pronounced.

heading: B Details of the ILSVRC2012 classifiers

text:
ILSVRC2012 classifiers, i.e. ResNet-18 and VGG-16, were trained with a procedure similar to Appendix A. The difference was that they were trained for a maximum of 35 epochs, the learning rate was decayed for every 20 epochs, and NS models were all pruned at 15 epochs. For image preprocessing, we additionally cropped and stretched/squeezed images randomly following Krizhevsky et al. (2012).
Since VGG-16 is computationally intensive with over 15 G MACs, We first applied NS on VGG-16 to reduce the computational and memory requirements, and ease the training of the FBS-augmented variant. We assigned a 1% budget in top-5 accuracy degradation and compressed the network using NS, which gave us a smaller VGG-16 with 20% of all channels pruned. The resulting network is a lot less redundant, which almost halves the compute requirements, with only 7.90 G MACs remaining. We then apply FBS to the well-compressed network.
Residual networks (He et al., 2016), such as ResNet-18, adopt sequential structure of residual blocks: xb = K (xb−1) + F (xb−1), where xb is the output of the bth block, K is either an identity function or a downsampling convolution, and F consists of a sequence of convolutions. For residual networks, we directly apply FBS to all convolutional layers, with a difference in the way we handle the feature summation. Because the (b+ 1) th
block receives as input the sum of the two features with sparse channels K (xb−1) and F (xb−1), a certain channel of this sum is treated as sparse when the same channels in both features are simultaneously sparse.
Figure 5 compares the accuracy/performance trade-off curves between FBS and NS for ResNet-18.

title: Dynamic Channel Pruning: Feature Boosting and Suppression