Large-scale deep neural networks have achieved remarkable success on complex cognitive tasks, including image classification, e.g., He et al. (2016), speech recognition, e.g., Amodei et al. (2016) and machine translation, e.g., Wu et al. (2016). However, a drawback of the modern large-scale DNNs is their low inference speed and high energy cost, which makes it less appealing to deploy those models on edge devices such as mobile phones and Internet of Things (Cai et al., 2019).
It has been shown that network pruning (Han et al., 2015) is an effective technique to reduce the size of the DNNs without a significant drop of accuracy. However, most existing works on network pruning are based on heuristics, leaving the theoretical questions largely open on what kind of network can be effectively pruned, how much we can prune a DNN given a specified tolerance of accuracy drop and how to achieve it with a practical and computationally efficient procedure.
Recently, a line of works on network pruning with theoretical guarantees have emerged, including sensitivity-based methods (Baykal et al., 2019b;Liebenwein et al., 2020), coreset-based methods (Baykal et al., 2019a;Mussay et al., 2020), greedy forward selection (Ye et al., 2020). Both the sensitivity-based and coreset-based methods prune the network by sampling and bound the error caused pruning via concentration inequalities. They show that the error introduced by pruning decays with an O(n -1 ) rate w.r.t. the size n of pruned network. This is comparable to the asymptotic error obtained by directly training a neural network of size n with gradient descent descent, which is also O(n -1 ) following the mean field analysis of Mei et al. (2018); Araújo et al. (2019); Sirignano & Spiliopoulos (2019). More recently, Ye et al. (2020) proposed the first pruning method that achieves a faster O(n -2 ) error rate and is hence provably better than direct training with gradient descent. See Table 1 for a summary on those works.
However, the analysis of Ye et al. (2020) only applies to two-layer networks and requires the original network to be sufficiently over-parameterized. In this paper, we proposed a new greedy optimization based pruning method, which learns sub-networks of size n with a significantly smaller O(exp(-cn))
No Over-param Deep Net Baykal et al. (2019b); Liebenwein et al. (2020) O(n -1 ) Baykal et al. (2019a); Mussay et al. (2020) O(n -1 ) Ye et al. (2020) O(n -2 ) × × This paper O(exp(-cn)) Table 1: Overview on theoretical guaranteed pruning methods. Rate above gives how the error due to pruning decays as the size of the pruned network (n) increases. Column 'No Over-param' denotes whether the method applies to an original network that is not over-parameterized in order to obtained the rate. Column 'Deep net' denotes whether the analysis applies to deep networks.
error rate, improving the rate from polynomial to exponential. In addition, our theoretical rate only requires weak assumptions that hold for most networks in practice, without requiring the the original networks to be overparameterized as Ye et al. (2020). Different from the Lottery Ticket Hypothesis (Frankle & Carbin, 2018), which selects the winning tickets that give good performance when trained in isolation from initialization, our approach finds the tickets (that already won) from a fully converged network.
Practically, our algorithm is simple and easy to implement. In addition, we introduce practical speedup techniques to further improve the time efficiency. Empirically, our method improves the prior arts on network pruning under various network structures including ResNet-34 (He et al., 2016), MobileNetV2 (Sandler et al., 2018) and MobileNetV3 (Howard et al., 2019) on ImageNet (Deng et al., 2009) as well as DGCNN (Wang et al., 2019) on ModelNet40 (Wu et al., 2015) on point cloud classification.
Notation We use notation [N ] := 1, ..., N for the set of the first N positive integers. All the vector norms • are assumed to be 2 norm. We denote the vector 0 norm by • 0 . • Lip denotes the Lipschitz norm for functions. I{•} indicates the indicator function.
Problem Setup Given a pre-trained deep neural network with L layers:
, where the -th layer F consisting of N neurons forms a mapping of form
with z as a proper input of the -th layer, which is the output of the previous -1 layers. Here σ(θ, •) is a general nonlinear map parameterized by θ that represents a neuron or other module in the network. For example, in a fully connected layer, we have σ(θ, z) = w 1 σ + (w 2 z) with θ = [w 1 , w 2 ] and σ + an activation function such as ReLU or Tanh. In a convolution layer, we have σ(θ, z) = w 1 σ + (w 2 * z), where * denotes the convolution operator. In this paper we may call σ(θ i , •) the neuron i or the i-th neuron for simplicity. Without loss of generality, we assume each layer in the given deep network has the same number of neurons using the same activation function.
The goal of network pruning is to construct a thinner network by replacing each layer with a subset of n < N neurons. For simplicity of presentation, we focus on pruning a single layer F for now and we discuss how to apply our algorithm in a layer-wise fashion to prune the whole network in section 2.4.
To prune the -th layer, the goal is to replace F with a thinner layer f ,A with n < N neurons:
where Ω [N ] is the probability simplex on the N neurons, that is,
By enforcing that A ∈ Ω N , we prune the layer by finding the best convex combination of a subset of neurons. The constraint that i a i = 1 ensures that the overall magnitude of the output of the layer after pruning matches that of the original network even when a lot neurons are moved. We denote the network with the -th layer replaced by f ,A as f A , i.e.,
Given an observed dataset D m := (x (i) , y (i) ) m i=1 with m data points. We want to choose A such that the pruned network f A is close to the original F as much as possible, measured by the regression discrepancy loss,
Our algorithm and theoretical analysis can be extended to other discrepancy losses such as the cross-entropy. The problem of pruning the -th layer can be formulated by the following constraint problem
This yields a challenging sparse optimization problem, which we address using greedy optimization, yielding algorithms that are both theoretically guaranteed and practically efficient.
We first introduce a simply greedy algorithm via local imitation for searching a good solution of problem (1). The pruned network can be viewed as
Here z is the output of the -1-th layers and i) ). The set D m := (z (i) ) m i=1 denotes the distribution of training data pushed through the first -1 layers. Suppose H is Lipschitz continuous, which typically holds for neural networks, we are about to upper bound
where D is the local discrepancy loss measuring the discrepancy on the output of the -th layer between the pruned and original network
In local imitation, we construct f ,A such that its output well imitates the output of F , i.e., The local imitation is a bi-directional greedy optimization for solving (2). It starts with an empty layer, and sequentially adds, removes or adjusts neurons that yield the largest decrease of the loss. Specifically, denote by f ,A(k) the layer we obtained at the k-th iteration with A(k) = [a 1 (k), ..., a N (k)]. We start with selecting the single best neuron that minimizes the loss:
where i * 0 is the index of the selected neuron; correspondingly, we have a i (0) = I{i = i * 0 }. At iteration k, we search for the best neuron i * k and step size γ * k that minimizes the loss most, i.e.,
Then we update
Here U i in (4) is the search interval of the step size γ. We set U i = [0, 1] if the i-th neuron has not been selected yet (i.e., a i (k) = 0) and U i = [-a i (k)/(1 -a i (k)), 1] if the neuron has already been added (i.e., a i (k) > 0). Therefore, this update can correspond to adding or removing a neuron, or simply adjusting the weight of existing neurons: the i * k -th neuron is added into the pruned network f ,A if we have a i * k (k) = 0, and it is removed from f ,A if we have γ
; no new neuron is added or removed if otherwise.
We stop the iteration when a convergence criterion, i.e., D ≤ , is met.
Solving Greedy Optimization in (4) A naive way to solve problem (4) is by enumerating each neuron and solving the corresponding inner minimization on γ. This is computational costly as it requires computing the forward pass in neural network many times. However, given i, the local discrepancy loss is a quadratic function w.r.t. γ. Combined with some special property of the local imitation algorithms, we are able to solve (4) with only computing the forward pass in network once. We refer readers to Appendix 5.1 for details
Now we proceed to give the convergence rate for the proposed local imitation algorithm. We introduce the following assumption.
Assumption 1 Assume that for any i ∈ [N ], z (j) ∈ D m , we have σ(θ i , z (j) ) ≤ c 1 and H Lip ≤ c 1 for some c 1 < ∞.
Assumption 1 holds when network parameters and data are bounded and the activation is Lipschitz continuous, which is very mild and holds for most network in practice. The following theorem characterizes the convergence of local imitation showing that the error caused by pruning decays exponentially fast when the number of neurons in the pruned model increases.
Theorem 1 (Convergence Rate) Under assumption 1, at each step k of the greedy optimization in (2), we obtain a layer with no more than k neurons (i.e., A(k) 0 ≤ k), whose loss satisfies
, where λ > 0 is a strictly positive constant. That is, the loss decays exponentially with the number of neurons in f ,A(k) .
Remark Minimizing γ over U i can be viewed as line searching the optimal step size for adjusting neuron i. We may also consider to choose a proper fixed step size, e.g., γ = 1/(k + 1) instead of line searching, in which case the optimization in (2) is simplified into
which can be shown to give an O(k -2 ) error at the k-th step under the same assumption as Theorem 1. See Appendix 5.2 for more details.
The local imitation method uses a surrogate local discrepancy loss which is convex w.r.t. A to prune the networks. Despite the good property of local imitation, the use of surrogate loss can be ineffective for some layers. For example, during the iteration of local imitation, the best neuron that minimizes the surrogate loss is not necessarily the best one that minimizes the actual discrepancy loss.
We propose a second pruning method, which directly minimizing the original discrepancy loss. This method follows the similar greedy fashion as the local imitation. We initialize the network by
and
Similarly, at each iteration, We adjust the network in a greedy way by solving the following problem:
However, solving problem ( 7) is computationally costly as the loss is non-convex w.r.t. A and thus solving the inner minimization on γ requires exhaustive search. To reduce the computational cost, in iteration k, we instead consider the following problem
Suppose that i * k gives that solution of problem (8), we update the network by setting
And we end the iteration when convergence criterion is met. Notice that different from local imitation, the algorithm adjusts A based on the final output of the network instead of the 'local' output of the pruned layer and thus we name it global imitation.
Different from the local imitation, due to the nonlinear of H 2 , besides Assumption 1, obtaining a convergence rate for the global imitation requires several additional assumptions characterizing the linearity of H 2 as well as the geometric property of the pruned layer.
Theorem 2 Under Assumption 1 and some additional assumptions, specified in Appendix 5.3, on the linearity of H 2 and initialization, we have
A native way to solve problem ( 8) is by enumerating all the neurons and calculating
, which has at least O(N n) time complexity for pruning a layer with N neurons to n neurons. Here we propose a technique to reduce the computational cost via Taylor approximation. At iteration k, for any neuron i ∈ [N ], we have
where we define
Thus, when k is large enough (which we find 25 is sufficient in practice), this approximation allows us to find the (near) optimal solution with small error of problem ( 8) by finding the neuron with the largest gr A,i . Simple algebra shows that
In appendix, we show that r A(k),i can be easily computed with automatic differentiation function in common deep learning libraries by introducing some ancillary parameters into the model. See Appendix 5.4 for details. If we choose to use this approximation when k > k for some k > 0, we reduce the complexity from O(N n) to O(n).
Our result implies that the subnetwork f A obtained by pruning gives
where n is the number of neurons remained in the pruned layer. In comparison, the mean field analysis (Araújo et al., 2019;Mei et al., 2018) suggests that directly train a network with same size as the pruned model gives O n -1 discrepancy loss. This suggests that pruning is provably better than training. We conduct a numerical experiment to verify the theoretical result. Given some simulated dataset, we firstly train a two hidden layer neural network with 100 neurons for each layer. And we prune the layer close to the input to different number of neurons using the local and global imitation.
We also train the network with different number of neurons for the pruned layer and 100 neurons for the other one. Figure 1 plots the discrepancy loss and the number of neurons of the pruned layer. The empirical result matches our theoretical findings. We refer readers to Appendix 5.5 for more details. The loss is in logarithm scale.
In section 2.1 and 2.2 we introduce how to use the greedy local/global imitation to prune a certain layer in a network.
In order to prune the whole network, we apply the greedy optimization scheme in a layer-wise fashion. Starting from the full network F , we apply the pruning method to prune the first layer (the one that is closest to the input)
We then apply the pruning method to prune the second layer F 2 in F prune,1 and continue until all the layers are pruned. By applying the pruning algorithm in this manner we prune the whole network.
The local imitation and global imitation perform differently when pruning different layers. To combine their advantages, when pruning each layer, both methods are applied individually with same convergence criterion and the one gives better performance is picked up. In this paper, we stop pruning when the discrepancy loss D of the pruned model is smaller than a user specified threshold. The method prunes more neurons at convergence is selected. If both methods prune the same number of neurons, then the one with smaller discrepancy loss is chosen. Algorithm 1 summarizes the procedure of local and global imitation and Algorithm 2 gives the layer-wise scheme on pruning the whole deep network.
The exponential decay rate can be obtained by iteratively applying our theory on each layer. Suppose the pruned model F pruned has n neurons at each layer, we have D[F pruned , F ] = O(exp(-λn)). We refer reader to Appendix 5.6 for details. Also notice that the exponential decay rate also holds for Algorithm 1 as it chooses the method with smaller loss.
Our first experiment aims to analyze the performance of local and global imitation for pruning deep neural network for image classification. We first apply both methods to a pretrained VGG-11 on CIFAR-10 dataset. We prune all the 8 convolution layers individual (when pruning one layer, the other layers remain unpruned) using both local and global imitation in order to compare these two methods side by side. Code for reproducing can be found at https://github.com/lushleaf/ Network-Pruning-Greedy-Forward-Selection.
Settings The full network is trained with SGD optimizer with momentum 0.9. We use 128 batch size with initial learning rate 0.1 and train the model for 160 epochs. We decay the learning rate by 0.1 at the 80-th and the 120-th epochs. During pruning we use 128 batch size. We do not apply the Taylor approximation tricks to global imitation for this experiment. we use cross entropy between the pruned model and original model as discrepancy loss.
Result Figure 2
We use ILSVRC2012, a subset of ImageNet (Deng et al., 2009) which consists of about 1.28 million training images and 50000 validation images with 1000 different classes.
Setting We apply our method on pruning ResNet34 (traditional large architecture) (He et al., 2016), MobileNetV2 (efficient architecture) (Sandler et al., 2018) and MobileNetV3-small (an very small efficient architecture) (Howard et al., 2019) on ImageNet.
We use batch size 64 for both local and global imitation. We set the algorithm to converge when the gap between the cross entropy training loss before pruning and after pruning is smaller than .
Top-1 Acc Size (M) FLOPs
Full Model (He et al., 2016) 73.4 21.8 3.68G L 1 norm (Li et al., 2017) 72.1 -2.79G Neural Imp (Molchanov et al., 2019) 72.8 -2.83G Rethink (Liu et al., 2018) 72.9 -2.79G More is Less (Dong et al., 2017) 73.0 -2.75G GFS (Ye et al., 2020) 73.5 17.2 2.64G Ours 73.5 14.9 2.20G SPF (He et al., 2018a) 71.8 -2.17G FPGM (He et al., 2019) 72.5 -2.16G GFS (Ye et al., 2020) 72.9 14.7 2.07G Ours 73.3 13.5 1.90G
Full Model (Sandler et al., 2018) 72.2 3.5 314M GFS (Ye et al., 2020) 71.9 3.2 258M Ours 72.2 3.2 245M Uniform (Sandler et al., 2018) 70.4 2.9 220M AMC (He et al., 2018b) 70.8 2.9 220M Meta Pruning (Liu et al., 2019) 71.2 -217M LeGR (Chin et al., 2019) 71.4 -224M GFS (Ye et al., 2020) 71.6 2.9 220M Ours 71.7 2.9 218M ThiNet (Luo et al., 2017) 68.6 -175M DPL (Zhuang et al., 2018) 68.9 -175M GFS (Ye et al., 2020) 70.4 2.3 170M Ours 70.5 2.3 170M
Full Model (Howard et al., 2019) 67.5 2.5 64M Uniform (Howard et al., 2019) 65.4 2.0 47M GFS (Ye et al., 2020) 65.8 2.0 49M Ours 66.4 2.0 48M We vary to get pruned model with different sizes. When conducting global imitation, we use the Taylor approximation trick introduced in section 2.2.1 to accelerate global imitation. We start the approximation when the number of neurons is larger than 25 and we evaluate the top 5 neurons with largest gr A,i and pick up the best one to adjust. We find that this setting is able to produce the same pruning result as the exact version while substantially reduces the computation cost.
We finetune the pruned models with standard SGD optimizer with momentum 0.9 and weight decay 5 × 10 -5 . All the pruned models are finetuned for 150 epochs with batch size 256 using cosine learning rate decay (Loshchilov & Hutter, 2016). We use initial learning 0.001 for ResNet34 and 0.01 for MobileNetV2 and MobileNetv3. We resize images to 224 × 224 resolution and adopt the standard data augumentation scheme (mirroring and shifting).
Result Table 2 reports the top1 accuracy, FLOPs and model size of the pruned network. Our algorithm consistently improves prior arts on network pruning.
We conduct experiment on the point cloud classification tasks on ModelNet40. Since the network structure used to extract the global information in point cloud usually requires to aggregate features from neighbor points, the high feature dimension heavily influence the forward time. We deploy our method on DGCNN. We compare with several baselines, including PointNet (Qi et al., 2017a), PointNet++ (Qi et al., 2017b), DGCNN with different width multipliers, and signed splitting steepest descent (Wu et al., 2020), which obtains a compact DGCNN by growing a extremely thin model. Table 3 shows that our method produces networks with comparable accuracy while with much less inference time. We refer readers to Appendix 5.7 for details of experiment settings.
Acc. Forward time (ms) # Param (M) PointNet (Qi et al., 2017a) 89.2 32.19 2.85 PointNet++ (Qi et al., 2017b)
Greedy Method Our method is highly related to Ye et al. (2020), which is also a greedy method with O(n -2 ) error rate for pruning over-parameterized two layer network. In comparison, we obtain exponential decay rate for pruning deep neural network with no requirement on the overparameterization of full model. Our local imitation method is also related to Frank Wolfe algorithm (Frank & Wolfe, 1956). Compared with it, our local imitation is a bi-level greedy joint optimization method while Frank Wolfe first searches for best direction and then conduct descent greedily.
Theory on Lottery Ticket Hypothesis (Malach et al., 2020) aims to prove the existence of subnetwork inside a random network that well approximates an unknown target network which has finite width and depth. It shows that a sufficiently large random network (with a specific structure) contains such a subnetwork with width of higher order compared with the targeted network.
This paper proposes a greedy optimization based pruning method, which is guaranteed to find a set of winning tickets (neurons) that approximates the fully trained unpruned network with exponential decay error rate w.r.t the number of selected tickets. The proposed pruning method is efficient with small time and space complexity and can be generally applied to various modern deep learning models.
Broader Impact Statement This work proposes a greedy optimization based pruning method, which has strong theoretical guarantee and good empirical performance. It gives positive improvement to the community of network efficiency. Our work do not have any negative societal impacts that we can foresee in the future.
In this section we give detailed discussion on local imitation with a fixed step size scheme shown in Section 2.2.1. Different from the greedy optimization (4), in this scheme, as the step size is fixed, the solution returned in each iteration is no better than the one of (4). As a consequence, it gives slower convergence rate.
Theorem 4 Under Assumption 1, at each step k of the greedy optimization in 5, we have
Now we give the theoretical result on greedy global imitation. Denote
and D as the diameter of M, which is defined in Lemma 5. Notice that κ 1 κ 2 ≥ 1. Using Lemma 3, we know that h ∈ riM, which indicate that there exists some λ > 0 such that
where B( h, λ) denotes the ball with radius λ centered at h.
Theorem 5 (Complete Version of Theorem 2) Suppose Assumption 1 holds. Further suppose that 1.
Remark Here the descending property of global imitation is influenced by the non-linear mapping H. As a consequence, the algorithm gives good convergence property when the whole dynamics is guaranteed to stay in a proper convergence region (R). The first extra assumption assumes the existence of this convergence region; The second extra assumption assumes a good initialization to ensure the dynamics stays in the convergence region at initialization; The third assumption can be roughly interpreted as assuming the dynamics will not jump out of the convergence region during descending. Notice that the extra assumptions holds when κ 1 and κ 2 is sufficiently close to 1.
In this section we give details on the computation of Taylor approximation tricks. Notice that
Thus the key quantities we want to obtain is
And once we obtain r A,i , we are able to calculate gr A,i = 2 N j=1 (I {j = i} -a j ) r A,j . Now we introduce how to calculate r A,i efficiently by introducing an ancillary variable. Suppose when pruning layer , we have
Here b i is the introduced ancillary variable, which alway takes 0 value. We have
This for implementation in practice, we can introduce b i with its value fixed 0 and calculate its gradient using, which is r A,i using the auto differentiate operator in common deep learning libraries.
In this section, we give details on the toy experiment on verifying numeric rate. We first introduce the problem setup for the comparison between pruning and direct gradient training in obtaining small network. We use the two-hidden-layer deep mean field network formulated by Araújo et al. (2019). Suppose that the second hidden layer (the one close to output) has 50 neurons; the first hidden layer (the one close to input) has n ≤ 50 neurons with 50 dimensional feature map; and the input has 100 dimension. That is, we consider the following deep mean field network
, where
Suppose that we train the original network F N with N = 50 neuron at the first hidden layer using gradient descent defined in Araújo et al. (2019) for T time (T < ∞) with random initialization. To obtain a small network with n neurons at the first hidden layer, we consider two approaches. In the first approach, we prune the first hidden layer of the trained F N using local imitation to obtain F n local where n indicates the number of neurons remained in the first hidden layer. In the second approach, we direct train the network F n direct train with n neurons in the first layer using the same gradient descent dynamics, initialization and training time as that in training F N . By the analysis in Araújo et al. (2019), we have D[F n direct train , F N ] = O(n -1 ). And by Theorem 1, we have D[F n local , F N ] = O(exp(-λn)) for some λ > 0. This implies that pruning is provably much better than directly training in obtaining compact neural network. Now we introduce the experiment settings. To simulate the data, we first generate a random network F gen (x) = (exp (w 2 /10) -0.5) Tanh(sin (2πw 1 ) x/5)/1000, where w 1 ∈ R 1000×100 and w 2 ∈ R 1000 is generated by randomly sampling from uniform distribution Unif[0, 1] (each element is sampled independently). And then we generate the training data by sampling feature x from Unif[0, 1] (each coordinate is sampled independently) and then generate label y = F gen (x). The simulated training dataset consists of 200 data points. We initialize the parameters of F N and F n direct train from standard Gaussian distribution with variance 1, N (0, 1) (each element are initialized independently) and both F N and F n direct train are trained using the same and sufficiently long time to ensure convergence. We also include the pruned model using global imitation, which is denoted as F n global . The pruned models are not finetuned. We vary different n and summarize the discrepancy.
In the main text, we mainly discuss the convergence rate of pruning one layer. In this section, we discuss how to apply our convergence rate for single layer pruning to obtain an overall convergence rate. Following the layer-wise procedure introduced in Section 2.4, suppose that the algorithms prunes F to f ,A , ∈ [L]. And thus, during the layer-wise pruning, the algorithm generates a sequence of pruned networks
we set A = A local , else we set A = A global . Define
denotes the distribution of training data pushed through the first -1 layers.
We introduce the following assumption on the boundedness.
Assumption 2 Assume that for any i ∈
Theorem 6 (Overall Convergence) Under assumption 2, we have
We deploy our method on DGCNN (Wang et al., 2019). DGCNN contains 4 EdgeConv layers that use K-Nearest-Neighbor(KNN) to aggregate the information from the output of convolution operation.
Pruning the convolution operation in EdgeConv can significantly speed up the KNN operation and therefor make the whole model more computational efficient.
Settings The full network is trained with SGD optimizer with momentum 0.9 and weight decay 1 × 10 -4 . We train the model using 64 batch size with an initial learning rate 0.1 for 250 epochs. We apply cosine learning rate scheduler during the training and decrease the learning rate to 0.001 at the final epoch. During the pruning, we use 32 batch sizes and the other settings keep the same as our ImageNet experiment in Section 3.2.
We introduce several technical Lemmas that are useful for proving the main theorems.
Lemma 1 Given some convex set M ⊂ R d , for any q 1 ∈ riM and q 2 ∈ clM . Then all the points from the half-segment [q 1 , q 2 ) belongs to the relative interior of M , i.e.,
Lemma 2 Let M be a convex set in R d , then if M is nonempty, then the relative interior of M is nonempty.
Lemma 1 and 2 are classic results from convex optimization.
where S = {q 1 , ..., q n } ⊆ R d with 1 ≤ n < ∞. Define q = 1 n n i=1 q i , then q ∈ riM .
Lemma 4 Suppose that for some λ > 0 such that
Lemma 5 Under Assumption 1, for any h, h ∈ M, hh ≤ D for some D ≤ 2 √ mc 1 . Here D can be viewed as the diameter of M.
, for some ρ ∈ (0, 1).
Lemma 7 Consider the following number sequence x 2 k+1 ≤ ax 2 k -bx k + c. Suppose that this number sequence satisfies the following conditions: (1) a > 1, b ≥ 0, c ≥ 0; (2) x k ≥ 0 for any k;
(3) (a -1)x 2 -bx 2 + c has two real roots z 1 ≤ z 2 ; (we allow z
Using Lemma 3, we know that h ∈ riM, which indicate that there exists some λ > 0 such that
where B( h, λ) denotes the ball with radius λ centered at h. Define Extre(M) as the set of extreme points of M, we know that Extre(M) ⊆ {h 1 , ..., h N }. Consider the following problem
Here the last inequality is by Lemma 6. This gives that h
And thus we have
And thus we have
where the last inequality is by A(k) 0 ≤ k.
Notice that if we have
, by the argument in proving Theorem 1, we have
Using Lemma 3, we know that h ∈ riM, which indicate that there exists some λ > 0 such that
where B( h, λ) denotes the ball with radius λ centered at h. Following the same argument of Ye et al. (2020) in proving theorem 2, we have hh A(k) 2 = O((k + 1) -2 ). The result that A(k) 0 ≤ k + 1 is obvious as in each iteration, the number of nonzero elements in A at most increases by 1.
Suppose that at iteration k, we have h A(k) . And the global imitation algorithm returns h A(k+1) with f .A
We also define i k as the solution of local imitation. And we let f
Here D is the quantities defined in Lemma 5, (1) and (3) use the definition of κ 1 and κ 2 and (2) is by the argument of Ye et al. (2020) in proving Theorem 2 (notice that their argument also applies to the case that h is in the relative interior of M, which is proved by Lemma 3, instead of that h is in the interior of M). By the assumption that D
.
We define q 1 = κ 2 1 κ 2 2 and q 2 = κ 2 1 κ 2 , and we have
1, then the rate holds by directly applying the argument of Ye et al. (2020) in proving Theorem 2. If q 1 > 1, we know that 2q 2 λ ≥ 0 and κ 2 1 D 2 ≥ 0; W k ≥ 0 for any k by its definition; the formula q 1 x 2 -2q 2 λx + κ 2 1 D 2 = x 2 has two real roots z 1 ≤ z 2 ; z 2 ≥ κ 1 D by the assumption; and W k+1 ≤ z 2 by the assumption. Using Lemma 7, we have, for any k,
and thus D[f A(k) , F ] = O(k -2 ). The result that A(k) 0 ≤ k + 1 is obvious as in each iteration, A(k) 0 at most increase 1.
When pruning the -th layer, if this layer is pruned by local imitation, by applying Theorem 1 on the -th layer of f [ -1] , we have
for some λ > 0. Else if this layer is pruned by global imitation, we have
Using triangle inequality, we know that
Proof of Lemma 3
The case that n = 1 is trivial and we consider the case that n ≥ 2. By the definition, we know that M is an non-empty and closed convex set. And thus by Lemma 2, riM is not empty. Define q ∈ riM, q = n i=1 α i q i , n i=1 α i = 1 and α i ≥ 0 ∀i ∈ [n].
We define α max = max i∈[n] α i . Notice that α max ≥ 1/n, otherwise, if α max < 1/n, we have n i=1 α i ≤ nα max < 1, which makes contradiction. If α max = 1/n, then α i = 1/n for all i ∈ [n], otherwise, n i=1 α i < 1, which makes contradiction. In the case that α max = 1/n, we have already obtained the desired result. Now we assume α max > 1 n . Define λ = 1 -1 nαmax ∈ [0, 1) and β i = αmax-αi nαmax-1 . Notice this gives that n i=1
We define q = n i=1 β i q i and by the property of β i and the definition of M , we have q ∈ M = clM . Notice that q = 1 n n i=1
Using Lemma 1, we know that q ∈ riM .
Notice that by choosing
5.9 Proof of Lemma 5
Notice that for any i ∈ [N ],
And for any h ∈ M, we have h = N i=1 β i h i , for some β i ≥ 0 and N i=1 β i = 1, which gives that
Proof of this Lemma follows standard argument in analyzing Frank Wolfe algorithm. We include it for the completeness. Notice that s * k = arg min Using Lemma 4, we know that h
where the last inequality uses the fact that h
. And thus we have
where the last inequality is by Lemma 5.
Define f (x) = ax 2 -bx+c. By assumption (1) and assumption (3), for any z ∈ [z 1 , z 2 ], f (z)-z 2 ≤ 0. We proof the desired result by induction. Suppose that x k ∈ [0, z 2 ]. Case 1: x k ∈ [z 1 , z 2 ] and in this case,
x 2 k+1 ≤ f (x k ) ≤ x 2 k ≤ z 2 2 . Case 2: x k ∈ [0, z 1 ) and in this case
f (z) ≤ max(f (0), f (z 1 )) = max(c, z 2 1 ).
This gives that x k+1 ≤ max( √ c, z 1 ) ≤ max(z 2 , z 1 ) = z 2 . The desired result follows by induction.