{'fraction_non_alphanumeric': 0.03433191422880131, 'fraction_numerical': 0.01773229699644573, 'mean_word_length': 4.6646017699115045, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Alternating Direction Method of Multipliers for Sparse Convolutional Neural Networks

The storage and computation requirements of Convolutional Neural Networks (CNNs) can be prohibitive for exploiting these models over low-power or embedded devices. This paper reduces the computational complexity of the CNNs by minimizing an objective function, including the recognition loss that is augmented with a sparsity-promoting penalty term. The sparsity structure of the network is identified using the Alternating Direction Method of Multipliers (ADMM), which is widely used in large optimization problems. This method alternates between promoting the sparsity of the network and optimizing the recognition performance, which allows us to exploit the two-part structure of the corresponding objective functions. In particular, we take advantage of the separability of the sparsity-inducing penalty functions to decompose the minimization problem into sub-problems that can be solved sequentially. Applying our method to a variety of state-of-the-art CNN models, our proposed method is able to simplify the original model, generating models with less computation and fewer parameters, while maintaining and often improving generalization performance. Accomplishments on a variety of models strongly verify that our proposed ADMM-based method can be a very useful tool for simplifying and improving deep CNNs.


INTRODUCTION
Deep Convolutional Neural Networks (CNNs) have achieved remarkable performance in challenging computer vision problems such as image classification and object detection tasks, at the cost of a large number of parameters and computational complexity. These costs can be problematic for deployment especially on mobile devices and when real-time operation is needed.
To improve the efficiency of CNNs, several attempts have been made to reduce the redundancy in the network. Jaderberg et al. (2014) proposed to represent the full-rank original convolutional filters tensor by a low-rank approximation composed of a sequence of two regular convolutional layers, with rectangular filters in the spatial domain. A different network connection structure is suggested by Ioannou et al. (2015), which implicitly learns linear combinations of rectangular filters in the spatial domain, with different vertical/horizontal orientations. Tai et al. (2015) presented an exact and closed-form solution to the low-rank decomposition approach of Jaderberg et al. (2014) to enforce connection sparsity on CNNs.
Sparse learning has been shown to be efficient at pruning the irrelevant parameters in many practical applications, by incorporating sparsity-promoting penalty functions into the original problem, where the added sparsity-promoting terms penalize the number of parameters (Kiaee et al. (2016a;b;c)). Motivated by learning efficient architectures of a deep CNN for embedded implementations, our work focuses on the design of a sparse network using an initial pre-trained dense CNN.
The alternating direction method of multipliers (ADMM) (Boyd et al. (2011)) has been extensively studied to minimize the augmented Lagrangian function for optimization problems, by breaking them into smaller pieces. It turns out that ADMM has been recently applied in a variety of contexts provides an effective tool for optimal sparsity imposing on deep neural connections. This is achieved by augmenting a sparsity-inducing penalty term to the recognition loss of a pre-trained network. Different functions including the l 0 -norm and its convex l 1 -norm relaxations can be considered as a penalty term. The variables are then partitioned into two subsets, playing two different roles: 1) promoting the sparsity of the network at the level of a predetermined sparse block structure; 2) minimizing the recognition error.
The augmented Lagrangian function is then minimized with respect to each subset by fixing all other subsets at each iteration. In the absence of the penalty term, the performance results correspond to the original network with a dense structure. By gradually increasing the regularization factor of the sparsity-promoting penalty term, the optimal parameters move from their initial setting to the sparse structure of interest. This regularization factor is increased until the desired balance between performance and sparsity is achieved.
Several approaches have been developed to create sparse networks by applying pruning or sparsity regularizers: Wen et al. (2016); Alvarez & Salzmann (2016); Liu et al. (2015); Han et al. (2015). The most relevant to our work in these papers is the Structured Sparsity Learning (SSL) method of Wen et al. (2016), that regularizes the structures (i.e., filters, channels, filter shapes, and layer depth) of CNNs using a group lasso penalty function. However, the SSL approach suffers from two limitations compared to our proposed method. First, it relies on a rigid framework that disallows incorporation of non-differentiable penalty functions (e.g., l 0 -norm). Second, it requires training the original full model, while our proposed method allows to decompose the corresponding optimization problems into two sub-problems and exploit the separability of the sparsity-promoting penalty functions to find an analytical solution for one of the sub-problems (see Sec. 5 for more details).
Our numerical experiments on three benchmark datasets, namely CIFAR-10, CIFAR-100, and SVHN, show that the structure of the baseline networks can be significantly sparsified. While most previous efforts report a small drop or no change in performance, we found a slight increase of classification accuracy in some cases.

CNN WITH SPARSE FILTERS
Consider a CNN network consisting of a total of L layers, including convolutional and fully connected layers, which are typically interlaced with rectified linear units and pooling (see Fig. 1). Let the l-th layer includes m l input feature maps and n l output feature maps, with W l ij representing the convolution filter between the i-th and j-th input and output feature maps, respectively 1 . Our goal is to design the optimal filters, subject to sparse structural constraints. In order to obtain the filters which balance a trade-off between the minimization of the loss function and sparseness, we consider the following objective function minimize where L net stands for the logistic loss function of the output layer of the network which is a function of the convolutional filters of all layers W = {W l ij |i = 1, . . . , m l , j = 1, . . . , n l , l = 1, . . . , L}. The term f (W ) is a penalty function on the total size of the filters. The l 0 -norm (cardinality) function or relaxations to higher orders such as l 1 -norm function can be employed to promote the sparsity of the filters.
The parameter µ controls the effect of sparse penalty term. As µ varies, the solution of (1) traces the trade-off path between the performance and the sparsity. In the next section, the alternating direction method of multipliers (ADMM) which is employed to find the optimal solution of (1) is described.

USING ADMM FOR SPARSIFYING CNNS
Consider the following constrained optimization problem: minimize which is clearly equivalent to the problem stated in (1). The key point here is that by introducing an additional variable F and an additional constraint W − F = 0, the objective function of the problem (1) is decoupled into two parts that depend on two different variables.
The augmented Lagrangian associated with the constrained problem (2) is given by where Γ l ij is the dual variable (i.e., the Lagrange multiplier), ρ is a positive scalar, . F and is the Frobenius norm.
In order to find a minimizer of the constrained problem (3), the ADMM algorithm uses a sequence of iterative computations: 1. Make use of a descent method to solve the following performance promoting problem, 2. Find the analytical expressions for the solutions of the following sparsity promoting problem, 3. Update the dual variable Γ l ij using a step-size equal to ρ, in order to guarantee that the dual feasibility conditions is satisfied in each ADMM iteration, The three described computation steps are applied in an alternating manner. Re-estimation stops when the Frobenius distance of F in two consecutive iterations as well as the Frobenius distance of W and F at current iterations are less than a small threshold value. The details of steps 1 and 2 are described in the next sections. The outline of the proposed sparse CNN approach is summarized in Algorithm 1. At each individual regularization µ, in order to improve the performance of the sparsestructured network we fine tune the initial non-augmented recognition loss subject to the parameters belonging to the identified sparse structure.
fully connected layer at Fig. 1, you can see that it is just composed of one (m l = 1) vectorized input feature map and n l 1-dim convolutions, one for each output class.
S: a set of small logarithmically spaced points in increasing order, as regularization factor.

5:
for each µ in S do 6: do 7: Find the estimate of W {k+1} by minimizing (7) 8: Find the estimate of F {k+1} from (9) or (10) 9: Update dual variable Γ {k+1} from (6) 10: Fix the identified sparse structure and fine-tune network according to L net w.r.t. nonzero parameters 12: end for 13: return W l ij 14: end function 3.1 PERFORMANCE PROMOTING STEP By completing the squares with respect to W in the augmented Lagrangian C(W , F , Γ), we obtain the following equivalent problem to (4) where U l ij = F l ij − 1 ρ Γ l ij . From (7), it can be seen that by exploiting the separability property of ADMM method in the minimization of the augmented Lagrangian, the sparsity penalty term which might be non-differentiable is excluded from (7). Consequently, descent algorithms that rely on the differentiability can be utilized to solve the performance promoting sub-problem (7) This property allows that popular software and toolkit resources for Deep Learning, including Caffe, Theano, Torch, and TensorFlow, to be employed for implementing the proposed approach. In our work, we use Stochastic Gradient Descent (SGD) method of TensorFlow to optimize the weights (W ), which seemed a reasonable choice for the high-dimensional optimization problem at hand. The entire procedure relies mainly on the standard forward-backward pass that is used to train the convolutional network.

SPARSITY PROMOTING STEP
The completion of squares with respect to F in the augmented Lagrangian can be used to show that (5) is equivalent to where V l ij = W l ij + 1 ρ Γ l ij . From (8), it can be seen that the proposed method provides a flexible framework to select arbitrary sparsity blocks. Sparse structure can then be achieved at the level of the selected block. Specifically, both terms on the right-hand side of (8), f (F ) (for either the case of l 1 -norm or l 0 -norm) as well as the square of the Frobenius norm can be written as a summation of component-wise functions of a tensor. In our experiments, individual filter components are selected as the sparsity blocks (see Fig. 1). Hence (8) can simply be expressed in terms of F l ij components corresponding to the filters. However, any other individual sub-tensor components can be selected as the sparsity block.
More precisely, if f (F ) is selected to be the l 1 -norm function, then C(F ) = l,i,j (µ F l ij F F ) and consequently (8) is converted to a minimization problem that only involves spatial filters. The solution of (8) can then be determined analytically by the following soft thresholding operation, where a = µ ρ . Similarly, the following hard thresholding operation is the analytical solution for the case of the selection of the l 0 -norm f (F ) penalty term.

CONVERGENCE OF THE PROPOSED ADMM-BASED SPARSE CNN METHOD
For convex problems, the ADMM is guaranteed to converge to the global optimum solution (Boyd et al. (2011)). For non-convex problems, where there is a general lack of theoretical proof, extensive computational experience suggests that ADMM works well when the penalty parameter ρ in the augmented Lagrangian is chosen to be sufficiently large. This is related to the quadratic term that tends to locally convexify the objective function for sufficiently large ρ.
Unfortunately, in the deep learning problems, the objective is inherently highly non-convex and consequently there is the risk that it becomes trapped into a local optimum. This difficulty could be circumvented by considering a warm start that may be obtained by running a pre-trained version of the network. The proposed ADMM approach is then used to sparsify the final solution. Using this procedure, as the experiments in the next section show, we have obtained good empirical results.

EXPERIMENTAL RESULTS
In order to validate our approach, we show that our proposed sparse CNN approach can be efficiently applied to existing state-of-the-art network architectures to reduce the computational complexity without reducing the accuracy performance. For this purpose, we evaluate the proposed scheme on the CIFAR-10, CIFAR-100, and SVHN datasets with several CNN models.
In the implementation of the performance promoting step in Sec. 3.1, the batch size is 128 and the learning rate is set to a rather small value (i.e., 0.001 to search the space around the dense initialized filters to find a sparse solution). Since the regularization factor µ is selected from gradually increasing values, for the first small values of µ the selection of long epochs for performance-promoting step (inner loop) and fine-tuning steps is computationally prohibitive and would result in over-fitting. Instead, we start with one epoch for the first µ and increase the number of epochs by δ for the next µ values up to the ν-th µ value, after which the number of epochs is limited to δν. We found that δ = 1 and ν = 15 generally work well in our experiments. We already incorporated the number of training epochs at tables 3, 4, and 5 of Appendix B. If the maximum limiting number of iterations of inner loop is ξ (suggested value of ξ=10), the training time of the ν-th µ value takes a total of δνξ + δν epochs (δνξ for performance-promoting step and δν for fine-tuning) under the worst-case assumption, where the inner loop has not converged and completes only at the ξ-th iteration.

RESULTS ON CIFAR-10 OBJECT CLASSIFICATION
The CIFAR-10 dataset is a well-known small dataset of 60,000 32 x 32 images in 10 classes. This dataset comprises standard sets of 50,000 training images, and 10,000 test images. As a baseline for the CIFAR-10 dataset, we deploy four models: the Network in Network (NIN) architecture (Lin et al., 2013b), its low-rank version (Ioannou et al., 2015), a custom CNN, and its low-rank counterpart as well, two last being learned from scratch on the CIFAR dataset. The configurations of the baseline models are outlined in Table 1. The architecture of the NIN model is slightly different from the one introduced in Lin et al. (2013b). The original NIN uses 5x5 filters in the first and second convolutional layer which are replaced with one and two layers of 3x3 filters, respectively. As suggested by Ioannou et al. (2015), this modified architecture has comparable accuracy and less 256 × 10 256 × 10 computational complexity. In the low-rank networks, every single convolutional layer of the fullrank model is replaced with two convolutional layers with horizontal and vertical filters. NIN and low-rank NIN have an accuracy of 90.71 % and 90.07 %, respectively. The custom CNN and its low-rank variant show a baseline accuracy of 80.0 % and 80.2%, respectively. The results of our experiments are plotted in Fig. 2 for both l 0 -norm and l 1 -norm sparsity constraints. Fig. 2 shows how the accuracy performance changes as we increase the regularization factor µ.
The case with µ = 0 can be considered as the baseline model. In order to avoid over pruning of some layers, if the number of pruned filters in one layer exceeds 50 % of the total number of filters in that layer, then we change the pruning threshold to the statistical mean of the Frobenius norm of all the filters at that layer in the sparsity promoting step (explained in Sec. 3.2) to stop the over pruning of that layer. Taking the NIN and low-rank-NIN as an example, using the l 0 -norm sparsity function, the parameters in the networks are reduced by 34.13 % and 28.5 % and the relative accuracy performance is +.5 % and +1.23 %, respectively. Using the l 1 -norm sparsity constraint achieves slightly lower accuracy compared to the l 0 -norm, although it still conveniently sparsifies the network.
Using the proposed sparsity promoting approach on the custom CNN models, the networks with sparse connections and similar accuracy (79.9% vs 80 %) are achieved, but they have approximately 49.4 % fewer parameters than the original networks model. Since the target solution is likely to be sparse, enforcing sparsity at the beginning of the learning process with our proposed method provides a way to avoid overfitting for achieving a better performance. However, as the experiment results show, increasing more the sparsity strength of the solution may lead to slight oversmoothing and drop in the performance. For the low-rank CNN, we achieve a comparable accuracy of 80.14 %, with 25 % fewer parameters.
To further verify that the advantage of ADMM training is statistically significant, a t-test is conducted by repeating the experiment 15 times on CIFAR-10 by using NIN model. The t-test results are in Appendix A. In Appendix B, however, we present detailed results for random sample runs over the configurations tested. According to the results presenting in Table 3 of Appendix B, the number of parameters in the network can be reduced by a large factor, especially for the higher convolution layers. Interestingly, even with significant reductions in the number of parameters, the performance does not decrease that much. This parameter reduction also gives rise to the speed-up of the network, reported at the last columns of the tables. Note that most of the results listed in Table 3 outperform the baseline model.

RESULTS ON CIFAR-100 OBJECT CLASSIFICATION
The CIFAR-100 dataset is similar to the CIFAR-10 dataset containing 100 classes with 600 images per class. For CIFAR-100 we again use the baseline networks in Table 1 with only one structural difference (i.e., the NIN networks contain 100 feature maps at the last convolution layer and custom CNN networks contain 100 output labels). The baseline NIN, low-rank NIN, custom CNN, and low-rank CNN models show a test accuracy of 63.3 %, 63.6 %, 60.11 %, and 60.23 %, respectively. Using the proposed sparsity promoting approach on these networks, the total number of parameters in the layers can be reduced by a large factor with comparable or even better performance accuracy.
In particular, on the CIFAR-100 dataset, we achieve 64.09 % classification accuracy with 34.1 % sparsity for the NIN model, which improves upon the original NIN on this dataset. A test accuracy of 65.23 % is obtained for CIFAR-100 for the low-rank NIN model with 28.5 % sparsity which surpasses the performance of the baseline model. The proposed method on custom CNN and lowrank CNN show comparable performance accuracy to their corresponding baseline models (59.82 % vs 60.11 % and 60.1 % vs 60.23 %) with much less computation (49.7 % and 24.4 % number of zero elements, respectively). The details of changing sparsity in different layers of the networks on the CIFAR-100 dataset are presented in Table 4 of Appendix B. The same conclusions made for CIFAR-10 can be drawn from these results.

RESULTS ON SVHN OBJECT CLASSIFICATION
The SVHN dataset consists of 630,420 32x32 color images of house numbers collected by Google Street View. The task of this dataset is to classify the digit located at the center of each image. The structure of the baseline models used in SVHN is similar to those used for CIFAR-10, which are presented in Table 1. The training and testing procedure of the baseline models follows Lin et al. (2013b). The baseline NIN, low-rank NIN, custom CNN, and low-rank CNN models show the accuracy of 96.2 %, 96.7 %, 85.1 %, and 87.6 %, respectively. For this dataset, by applying our proposed sparse approach to NIN and low-rank NIN models, we obtain a higher accuracy of 96.97 % and 99 % with 34.17 % and 28.6 % fewer parameters, respectively. We also achieve comparable accuracy of 83.3 % and 86.3 % using 49.7 % and 24.7 % less parameters of the original model parameters on custom CNN and low-rank CNN models, respectively (see Table 5 of Appendix B for the details on changing the sparsity in different layers of the networks on SVHN dataset).

DISCUSSION
In this paper we proposed a framework to optimal sparsification of a pre-trained CNN approach. We employed the ADMM algorithm to solve the optimal sparsity-promoting problem, whose solution gradually moves from the original dense network to the sparse structure of interest as our emphasis on the sparsity-promoting penalty term is increased. The proposed method could potentially reduce the memory and computational complexity of the CNNs significantly.
Briefly, the main contributions of the proposed sparse CNN can be summarized as follows: Separability : The penalty function is separable with respect to the individual elements of the weight tensors. In contrast, the recognition loss function cannot be decomposed into component-wise functions of the weight tensors. By separating the two parts in the minimization of the augmented Lagrangian, we can analytically determine the solution to the sparsity promoting sub-problem (8). Differentiability : The recognition loss function L net (W ) is typically differentiable with respect to the parameters, as opposed to some choices of sparsity penalty terms (e.g., l 0 -norm which is a non-differentiable function). In our approach, by separating the two parts in the minimization of the augmented Lagrangian, descent algorithms can be utilized to solve the performance promoting sub-problem (7) )). However, these techniques can be used in conjunction with our proposed sparse method to achieve further speedup.
Some methods such as SSL (Wen et al. (2016)), based on group Lasso regularization of the block structures (e.g. filters), appears to be closely related to our work. Indeed, these methods learn sparse filters and minimize the classification error simultaneously. In contrast, our proposed approach uses ADMM to provide a separate scheme that optimize the sparse blocks and classification error separately. Indeed, at the core of our contribution, ADMM brings the above major separability and differentiability benefits to the proposed sparse CNN method. Our proposed algorithm has the advantage that it is partially and analytically solvable due to the separability property. This contributes to the efficient trainability of the model. Moreover, the differentiability problem of l 0norm penalty function makes it unusable for a joint performance/sparsity optimization, while it can be conveniently incorporated as a sparsity penalty term in our proposed method.
Furthermore, in the SSL method, strengths of structured sparsity regularization is selected by cross validation and the networks weights are initialized by the baseline. This is computationally beneficial for small regularization level. However, for larger regularization value, the presented SSL approach requires training the original full model from scratch. In contrast, our approach gradually modifies the regularization factor and each step continues training from the solution achieved in the previous step (corresponding to the previous regularization factor), which plays an important role in reducing the computational complexity of the method. Stephen

APPENDIX A SIGNIFICANCE VALIDATION OF IMPROVEMENTS
On order to verify that the advantage of ADMM training is statistically significant, we conduct t-test by repeating the experiment 15 times on CIFAR-10 using NIN to compare the error rate of ADMM training and standard fine-tuning (by dropping the learning rate upon "convergence" and continuing to learn), with the same number of epochs and learning rates. Initialized from the same baseline model with 90.71 % accuracy, the ADMM training using l 0 -norm and standard fine-tuning on average achieve accuracy of 91.34 % and 91.09 %, respectively. The results demonstrate the ADMM training achieves improvement of 0.63 % from the baseline model which is statistically significant (t-test result with p < 0.001). ADMM training performance is also significantly 25 % better than what the standard fine-tuning achieves (t-test result with p < 0.001). The t-test experiment also shows that ADMM could reduce the variance of learning. In the 15 repeated experiments, ADMM training has the lowest standard deviation of errors compared with their counterparts using standard fine-tuning (standard deviation of 0.04 % for ADMM vs 0.06 % for standard fine-tuning).

APPENDIX B SINGLE RUN RESULTS
Due to space consideration, we present some extra results in the current appendix. First, the results for our sparsity promoting approach for the different models on CIFAR-10, CIFAR-100, and SVHN are presented in Tables 3, 4 and 5, respectively. Follows in Table 6 results showing joint variations of accuracy and sparsity obtained with increasing µ values, for the three tested datasets. All these results are for a single random run of each method on the dataset at hand.