Deep learning is becoming more widespread in its application due to its power in solving complex classification problems. However, deep learning models often require large memory and energy consumption, which may prevent them from being deployed effectively on embedded platforms, limiting their applications. This work addresses the problem by proposing methods {\em Weight Reduction Quantisation} for compressing the memory footprint of the models, including reducing the number of weights and the number of bits to store each weight. Beside, applying with sparsity-inducing regularization, our work focuses on speeding up stochastic variance reduced gradients (SVRG) optimization on non-convex problem. Our method that mini-batch SVRG with $\ell$1 regularization on non-convex problem has faster and smoother convergence rates than SGD by using adaptive learning rates. Experimental evaluation of our approach uses MNIST and CIFAR-10 datasets on LeNet-300-100 and LeNet-5 models, showing our approach can reduce the memory requirements both in the convolutional and fully connected layers by up to 60$\times$ without affecting their test accuracy. Artificial intelligence is finding wider application across a number of domains where computational resources can vary from large data centres to mobile devices. However, state-ofthe-art techniques such as deep learning BID14 require significant resources, including large memory requirements and energy consumption. Reducing the size of the deep learning model to a compact model that has small memory footprint without compromising its performance is a desirable research aim to address the challenges for deploying these leading approaches on mobile devices. 1 regularization can be used as a penalty to train models to prevent the model from over-fitting the training data. As well as providing, 1 regularization is a powerful compression techniques to penalize some weights to be zero. As the results, our research focus on improving the method based on 1 regularization to reduce memory requirements. Moreover, as deep neural network optimization is a non-convex problem, the optimization can be stuck in local-minimal, which can reduce the performance. To address the problem, we improve SGD optimization for non-convex function to enhancing sparse representations obtained with 1 regularization. In this paper, we propose our compression method Weight Reduction Quantisation which reduces both the number of weights and bits-depth of model without sacrificing accuracy. To reduces the number of weights, our method employs sparsity-inducing 1 regularization to encourage many connections in both convolutional and fully connected layers to be zero during the training process. Formally, in this paper we consider the following unconstrained minimization problem, Given training labels y 1 , y 2 , ..., y N as correct outputs for input data x 1 , x 2 , ..., x N , the optimization problem to estimate the weights in all layers, W, is defined by DISPLAYFORM0 L(y i , f(x i ; W)) + λr(W),where λ is a hyper-parameter controlling the degree of regularization and the weights in all layers is given by W. The problem 1 can be strongly convex or possibly non-convex BID2 . Following update rule, the mini-batch SGD method with 1 regularization is a popular approach for performing the optimization, and the weight update rule is given by DISPLAYFORM1 where each weight of network can be represented by w j ,the total number of weights is M. k is the iteration counter and η k is the learning rate and B is mini-batch size (1 < B < N) used to approximate the full gradient. However, SGD optimization with 1 regularization has two challenges: firstly, it inefficiently encourages weight to be zero due to fluctuations generated by SGD BID18 . Secondly, SGD optimization slowing down convergence rate due to the high variance of gradients. The two methods of cumulative 1 regularization and SVRG can solve the two challenges respectively:Cumulative 1 regularization BID18 proposed a method cumulating the 1 penalties to resolve the problem. The method clips regularization at zero, which avoids the derivative DISPLAYFORM2 being non-differentiable when w j = 0 and provides a more stable convergence for the weights. Moreover, the cumulative penalty can reduce the weight to zero more quickly. Mini-batch SVRG As SGD optimization has slow convergence asymptotically due to noise, BID12 proposed SVRG that can efficiently decrease the noise of SGD by reducing the variance of gradients by: DISPLAYFORM3 whereμ j is the average gradient of sub-optimal weightsw j which is the weight after every m SGD iterationsμ DISPLAYFORM4 whereW is the sub-optimal weights after m SGD iterations in all layers. For succinctness we also write ∇ψ i (w DISPLAYFORM5 . They determined that reduction of variance helps initial weights w 0 close to global minima at the beginning in order to boost the convergence rate of SGD in strongly convex problems. BID12 further prove that the performance of SGD degrades with mini-batching by the theoretical result of complexity. Specifically, for batch size of B, SGD has a 1/ √ B dependence on the batch size. In contrast, SVRG in a parallel setting has 1/B dependence on the batch size which is much better than SGD. Hence, SVRG allows more efficient mini-batching. However, for non-strongly convex problems, global minimization of non-convex function is NP-hard BID1 . BID12 have a assumption that SVRG can also be applied in neural networks to accelerate the local convergence rate of SGD. Further, Allen BID1 prove non-asymptotic rates of convergence of SVRG for non-convex optimization and proposed improved SVRG that is provably faster than SGD. Hence, a promising approach is to use mini-batch SVRG instead of SGD with cumulative 1 regularization. We summarize our main contributions below:1. Reducing memory requirements:1.1 We analyse a method that combines SVRG with cumulative 1 regularization to reduce the number of weights, and propose our method Delicate-SVRGcumulative-1 which can significantly reduce the number of weights by up to 25× without affecting their test accuracy. To our knowledge, ours is the first work that to combine mini-batch SVRG with cumulative 1 regularization for non-convex optimization.1.2 To further reduce the memory requirements of models, we aim to reduces the number of bits to store each weight. Compression method Weight Reduction Quantisation, including both reducing number of weights and bit-depth, can reduce the memory footprints up to 60× without affecting accuracy. 2. Accelerating convergence rates:2.1 We analyse non-convex stochastic variance reduced gradient (SVRG). Based on the results from BID17 , we provide the condition when SVRG has faster rates of convergence than SGD.2.2 We empirically show that modified SVRG in our method have faster rates of convergence than ordinary SVRG and SGD. Different methods have been proposed to remove redundancy in deep learning models. Sparse representation is a good approach to reduce the number of parameters. Han et al. mainly explored pruning which is a direct approach to remove small values of connection and focuses on the important connections with large weight values in all layers of the network. However, a disadvantage is that after pruning the needs networks to be retrained. One idea from matrix factorization can be applied to compressed parameters in models by finding a low rank approximation of the weight matrix BID6 . However, in practice whilst it improves computation performance, it dose not significantly reduce memory requirements. Weight sharing aims to approximate weights by a single weight. Chen et al. proposed HashedNets binning network connections into hash buckets uniformly at random by a hash function. As part of a three stage compression pipeline, Han et al. use k-means clustering to identify the shared weights for each layer of a trained network. Weight quantization for reducing the bit-width to store each weight is an other approach to reduce memory requirements of models. Gysel et al. can successfully condense CaffeNet and SqueezeNet to 8 bits with only slight accuracy loss. Han et al. quantizes the sparse weights matrix to be an index which encodes in 8-bit for convolutional layers and 5-bit for fully connected layers. Rastegari et al. used binary operations to find the best approximations of the convolutions, in which the bit-size can be reduced to 1-bit. Another type of approach uses regularization to induce sparsity. Hinton et al. proposed "dropout" that refers to dropping out neurons that are from visible and hidden layers in neural network during training, which can be shown to be a kind of regularization. Collins & Kohli applied 1 regularization and shrinkage operators in the training process. However, it only reduced the weights by only 4× with inferior accuracy. Tsuruoka et al. improved on this with 1 regularization with superior compression, but the methods use SGD and has slow asymptotical convergence due to the inherent variance BID12 .3 Mini-batch Non-convex SVRG For Problem 1, a stochastic iterative learning algorithm estimate a stationary point x and achieve ε-accuracy in finite iterations satisfying || f (x)|| 2 ≤ ε, which is termed of the ε-accurate solution. For a non-convex problem, the goal is to find a reasonable local minimum. However, the challenge is that gradients are easy to be stuck into saddle-point or a local minimum. As a result, such an algorithm aims to help gradients escape from saddle-point or local-minimal, e.g. BID8 demonstrated that adding additional noise can help the algorithm escape from saddle points. To our best knowledge, there is no theoretically proof that can guarantee SVRG has faster rates of convergence than SGD. BID17 compared the Incremental First-order Oracle (IFO) complexity BID0 of SGD and SVRG on non-convex problem, O 1/ε 2 and O n + (n our analysis, whether non-convex SVRG can be efficiently close to reasonable optimal local minimum depends on the number of training samples. Suppose f i is non-convex for i ∈ [n] and f has ε-bounded gradients, the IFO complexity of mini-batch SGD with a adaptive learning rate is O 1/ε 2 and for mini-batch SVRG with a fixed learning rate O n + (n 2 3 /ε) . If the value of ε is constant, the speed of convergence rates of SVRG depends on the number of training samples: when n is small, SVRG is faster than SGD for non-convex optimization and vice versa. Our experiment results showed in Figure1 and Figure5can support our view. In our case, SVRG is applied on sparse representation. However, if directly combining minibatch non-convex SVRG with cumulative 1 regularization (called SVRG-cumulative-1): let u k be the average value of the total 1 penalty given by DISPLAYFORM0 At each training sample, weights that are used in current sample can be updated as DISPLAYFORM1 where, q k j is the total difference of two weights between the SGD update and the 1 regularization update, DISPLAYFORM2 where t is an index to calculate cumulative value of q, the algorithm has two problems: (1) As we mentioned, SVRG on sparse representation cannot guarantee to be faster than SGD. FIG1 shows that for small dataset (e.g. MNIST) the convergence of SVRG is faster than SGD but slower than SGD using a larger dataset (e.g. CIFAR-10), (2) The trade-off of SVRG-cumulative-1 in the variance reduction versus the sparsity of the cumulative 1 regularization. After the variance of the gradient is reduced by SVRG in Equation 6, the absolute value of the updated weight w k+ 1 2 j is higher than that using SGD, which causes SVRG to have an adverse effect on the sparsity of 1-regularization. Compared to ordinary SVRG, BID17 proposed an extension of SVRG: MSVRG that introduces adapts the learning rate, which guarantee that their method has equal or better than SGD. Therefore, similar to the method MSVRG, our method provides separate adaptive learning rates for SVRG-cumulative-1, which empirically demonstrates that it has faster convergence rate than SGD. To reduce the number of weights, we introduce our compression method Delicate-SVRGcumulative-1 that have two main improvements :(1) Separate Adaptive Learning Rate Learning rates play an important rule in effecting the convergence rate of optimization during the training process which must be chosen carefully to ensure that the convergence rate is fast, but not too aggressive in which case the algorithms may become unstable. Reddi et al. believe that adaptive learning rates can be applied with reduced variance to provide faster convergence rates on nonconvex optimization. As a result, the convergence rate of the algorithms can be improved if the learning rate is adaptively updated. Our algorithm includes three parameters to provide greater fidelity in controlling the convergence of gradients for implementation of the 1 regularization. Firstly, the learning rate γ k is chosen based on the learning rate from Collins et al. shown as, DISPLAYFORM0 where η 0 is an initial learning rate with large value. Our experiments determined the parameters in three learning rates are over range of values, and a value of π=0.6 as determined to be efficient. The learning rate schedule can emphasis the large distance between the gradient in the current optimization iteration and the sub-optimal solutions after every m iteration in the beginning, which avoids the current gradient being stuck in a local minimum at the start. It has a fast convergence rate to start with which decreases over time to minima local station. The second learning rate, β k , that reduces the variance of the SVRG-cumulative-1 and better balances the trade-off in both of SVRG and cumulative 1 regularization. β k is chosen such that β k > γ k with slower convergence as DISPLAYFORM1 here β k =0.75, and the results of experiment is the best when q = 3 that can keep relatively large penalty of average gradients. During updating weight, it is efficient to prevent the absolute value of weight from being increased by SVRG, which can reduce the bad effect of 1 regularization, and sparsity. We retain the same learning rate η k for cumulative 1 regularization BID18 shown as, DISPLAYFORM2 The exponential decay ensures that the learning rates dose not drop too fast at the beginning and too slowly at the end.(2) Bias-based Pruning To further reduce the number of weights, we add a bias-based pruningb after the 1 regularization in each iteration. The pruning rule is based on following heuristic BID7 : connections (weights) in each layer will be removed if their value is smaller than the network's minimal bias. If the absolute value of weight connections are smaller than the absolute value of the smallest bias of the entire network in each batch, these connections have least contribution to the node, which can be removed. In practice, bias-based pruning has no effect on train and test loss. Consequently, Delicate-SVRG-cumulative-1 that incorporates the adaptive learning rate schedules and bias-based pruning as, The pseudo code of our method is illustrated as Algorithm 1 in the Appendix. To further compress the model, weight quantization can significantly reduce memory requirement by reducing bit precision. We quantize to 3-bit after reducing by Delicate-SVRG-cumulative-1 for convolutional layers and encode 5 bits for fully connected layers. Consequently, we propose our final compression method Weight Reduction Quantisation. In order to estimate and compare the effect of our compression method on different topologies, e.g. fully connected networks and convolutional networks, we select deep neural networks (DNNs) and convolutional neural networks (CNNs). The DNN chosen is LeNet-300-100 which has two fully connected layers as hidden layers with 300 and 100 neurons respectively. The CNN chosen is LeNet-5 which has two convolutional layers and two fully connected layers. We evaluate the performance of our new compression method using MNIST, and CIFAR as benchmarks. MNIST (LeCun et al., 2001 ) is a set of handwritten digits which is a commonly used dataset in machine learning. It has 60,000 training examples and 10,000 test samples. Each image is grey-scale with 28×28 pixels. CIFAR-10 is a dataset that has 10 classes with 5,000 training images and 1,000 test images in each class. In total, it contains 50,000 training images and 10,000 test images with 32×32 pixels. CIFAR-10 images are RGB. Two types of error rate are used to measure the performance of models, which are top-1 and top-5 error rate. Here, we consider top-1 error on MNIST, while top-5 error on CIFAR-10 because many images in CIFAR are small and ambiguous. Our compression method was implemented using Caffe 1 . Applying Weight Reduction Quantisation to the MNIST dataset, we choose the results with the best combination of compression and error rate for comparison. Our method can reduce 98% of the memory requirements with a 1.57% test error rate on the LeNet-300-100 model and 98% of the parameters with a 0.74% test error on the LeNet-5 model. In TAB0 , the compression pipeline is summarised with weight statistics in comparison to the method from BID10 . In our first stage Delicate-SVRG-cumulative-1 that focus on reducing the number of weights, we compare the results of pruning method from BID10 (b) CIFAR-10 dataset on LeNet-300-100 model (left) and LeNet-5 (right): error rate is top-5 error Figure 2 : Four 1 regularization compression methods experiment on two deep learning models, including LeNet-300-100 and LeNet-5 using MNIST datasets and CIFAR-10.second stage is to further compress the model by bit-depth reduction, and Table1 shows our method Weight Reduction Quantisation that combines Delicate-SVRG-cumulative-1 with bit-depth reduction can achieve 1.56% error rate on MNIST, and 0.737% error rate on CIFAR-10, where the two errors are all lower than that of original model. The compression rates are up to 60× in LeNet-300-100 and up to 57× in LeNet-5 model. Focusing on Delicate-SVRG-cumulative-1 to examine the performance of method at different compression rates controlled by threshold λ, we compare the performance of different model-compression based on 1 regularization over the range of memory requirements. Figure 2 shows how the test error rate and weight sparsity vary as the regularization parameter λ is adjusted. Where pareto fronts are not available for comparison, we compare with a single trade-off and determine the related performance by the side of the pareto front that the point lies. Figure 2(a) shows LeNet on MNIST. Compared with SVRGcumulative-1, SGD-cumulative-1 has the better ability of compression, but the error rate is higher due to the variance generated by SGD optimiser. Replacing SGD with SVRG, SVRG-cumulative-1 reduces the test error but the compression ability is also reduced. The Delicate-SVRG-cumulative-1 method has the least number of weights and the best performance having the lowest test error for almost every compression value. Its performance is similar with the method without bias-based pruning, which means that adding bias-based pruning can further reduce the number of weights without side-effect on the performance. The pink box on 2(a) showed that the results within the box is better than pink point. Figure 2 (b) shows LeNet on CIFAR-10 dataset that is a larger and more complicated dataset than MNIST. SVRG-cumulative-1 has chances to achieve lower test error than SGD-cumulative 1 but can not guarantee that the performance is always better than SGD-cumulative-1. Delicate-SVRG-cumulative-1 method has better performance than the other methods. Its performance is further enhanced by adding biasbased pruning. Consequently,Delicate-SVRG-cumulative-1 can be effectively applied in LeNet-300-100 and LeNet-5 models without accuracy loss when applied to MNIST and CIFAR-10. Figure3 shows the test error at different compression rates for Delicate-SVRG-cumulative-1 and weight Quantization. Individually, weight quantization can reduce more memory before the test error increases significantly in Delicate-SVRG-cumulative-1 using MNIST dataset, but the reverse results applied on CIFAR-10 dataset. However, if combining together, the approach consistently outperforms. Figure 3: The test error with compression rate under different compression methods. D is Delicate-SVRG-cumulative-1, Q is weight quantization. Combining Delicate-SVRGcumulative-1 with weight quantization can achieve the best performance. To confirm the theoretical insights that our method has no bad effect on convergence rate to achieve similar fast convergence with SGD-cumulative-1 or SVRG-cumulative-1, we calculate the training loss of two LeNet models on MNIST and CIFAR datasets during increasing iterations. In Figure 4 (a), all methods have similar convergence rates in LeNet-300-100. In all of our experiments, Delicate-SVRG-cumulative-1 has same or lower training loss and faster convergence rate than other methods, meaning that adaptive learning rate can help SVRG with cumulative 1 regularization to escape the local minimum in the beginning and quickly converge to a good local minimum within finite training iterations. Moreover, Delicate-SVRG-cumulative-1 without bias-based pruning has a similar train loss, which illustrates that adding bias-based pruning in 1 regularization has no obvious bad effect on the convergence of weights. Consequently, applying adaptive learning rates, Delicate-SVRG-cumulative-1 is a efficient compression method for neural network problems. In this paper, we proposed Weight Reduction Quantisation that efficiently compressed neural networks without scarifying accuracy. Our method has two stages that reduce the number of weights and reduce the number of bits to store each weight. We show that SVRG and cumulative 1 regularization can improve over SGD and 1-regularization. By combining them, we have presented a new compression method Delicate-SVRG-cumulative-1 that can efficiently reduce the number of parameters by the separate adaptive learning rates. The three adaptive learning rates are applied on SVRG and cumulative 1 penalty, which provides a high accuracy and reduced number of weights. Besides, our method improved SVRG that can be used on non-convex problem with fast convergence rate. In our experiments on LeNet-300-100 and LeNet-5, our method can significantly reduce the memory requirements up to 60× without accuracy loss. After compression by our method, a compact deep neural network can be efficiently deployed on an embedded device with performance of the original model. Algorithm 1 Delicate-SVRG-cumulative-1: Stochastic descent training with cumulative 1 penalty procedure Train( λ) u ← 0 µ ← 0 Initial w j and q j with zero for all number of weights M for k=0 to Maximal Iterations do DISPLAYFORM0 end for u ← u + ηλ/M end for for j ∈ features used in sample i do randomly select m features from train samples DISPLAYFORM1 (∇ψ i (w j ) -∇ψ i (w j )) + β kμ ∇ψ i (w j ) = ∇ψ i (w j ) if w j andw j converge to the same weights theñ µ = 0 end if µ ←μ + The results showed in Figure4.7.3 Using multiple initializations to compare the performance of our method and other three methods. The experiments were run with multiple initializations and there was some small variability in the results. However, the relative performance of the our method is always better than SVRG and SGD combining with cumulative 1 regularization. The results showed in (b) The test loss: MNIST dataset on LeNet-5 (left) and CIFAR-10 dataset on LeNet-300-100 (middle) and Figure 4: Estimate the convergence rate when using four compression methods, including our method Delicate-SVRG-cumulative-1, Delicate-SVRG-cumulative-1 (without BiasPruning) that without bias-based pruning in 1 regularization,SVRG-cumulative-1 and SGD-cumulative-1, on LeNet-300-100 and LeNet-5 models with MNIST and CIFAR-10 datasets. Here we choose the compression rate that equal 90% to observe training and test loss. For MNIST dataset, we did not notice subtle difference train and test loss on LeNet-300-100 model generated by four methods. Figure 5: Using three types of initial weights, we compare our method with other three methods. D-SVRG-C-L1 and D-SVRG-C-L1(wo BiasPruning) are always better than other two methods. This experiment also can verify the our view that the performance of SVRG is better or worse than SGD that depends on the number of training samples. In our experiment, if choosing small dataset (e.g. MNIST), SVRG is better than SGD. Otherwise, if choosing relatively large dataset (e.g. CIFAR-10), SVRG is worse than SGD.
Compression of Deep neural networks deployed on embedded device.  The authors present an l-1 regularized SVRG based training algorithm that is able to force many weights of the network to be 0. This work reduces memory requirements.