Title: IRDA METHOD FOR SPARSE CONVOLUTIONAL NEURAL NETWORKS

Abstract: We propose a new approach, known as the iterative regularized dual averaging (iRDA), to improve the efficiency of convolutional neural networks (CNN) by significantly reducing the redundancy of the model without reducing its accuracy. The method has been tested for various data sets, and proven to be significantly more efficient than most existing compressing techniques in the deep learning literature. For many popular data sets such as MNIST and CIFAR-10, more than 95% of the weights can be zeroed out without losing accuracy. In particular, we are able to make ResNet18 with 95% sparsity to have an accuracy that is comparable to that of a much larger model ResNet50 with the best 60% sparsity as reported in the literature.

1. INTRODUCTION:

In recent decades, deep neural network models have achieved unprecedented success and state-ofthe-art performance in various tasks of machine learning or artificial intelligence, such as computer vision, natural language processing and reinforcement learning Lecun et al. (2015) . Deep learning models usually involve a huge number of parameters to fit variant kinds of datasets, and the number of data may be much less than the amount of parameters He et al. (2016) . This may implicate that deep learning models have too much redundancy. This can be validated by the literatures from the general pruning methods Pratt (1988) to the compressing models Han et al. (2015a) .

While compressed sensing techniques have been successfully applied in many other problems, few reports could be found in the literature for their application in deep learning. The idea of sparsifying machine learning models has attracted much attention in the last ten years in machine learning Donoho (2006) ; Xiao (2010) . When considering the memory and computing cost for some certain applications such as Apps in mobile, the sparsity of parameters plays a very important role in model compression Han et al. (2015a) ; Cheng et al. (2017) . The topic of computing sparse neural networks can be included in the bigger topic on the compression of neural networks, which usually further involves the speedup of computing the compressed models.

There are many sparse methods in machine learning models such as FOBOS method Duchi and Singer (2009) , also known as proximal stochastic gradient descent (prox-SGD) methods Mine and Fukushima (1981) , proposed for general regularized convex optimization problem, where 1 is a common regularization term. One drawback of prox-SGD is that the thresholding parameters will decay in the training process, which results in unsatisfactory sparsity Xiao (2010) . Apart from that, the regularized dual averaging (RDA) method Xiao (2010) , proposed to obtain better sparsity, has been proven to be convergent with specific parameters in convex optimization problem, but has not been applied in deep learning fields.

In this paper, we analyze the relation between simple dual averaging (SDA) method Nesterov (2009) and the stochastic gradient descent (SGD) method Robbins and Monro (1951) , as well as the relation between SDA and RDA. It is well-known that SGD and its variants work quite well in deep learning problems. However, there are few literatures in applying pure training algorithms to deep CNNs for model sparsification. We propose an iterative RDA (iRDA) method for training sparse CNN models, and prove the convergence under convex conditions. Numerically, we compare prox-SGD with iRDA, where the latter can achieve better sparsity results while keeping satisfactory accuracy on MNIST, CIFAR-10 and CIFAR-100. We also show iRDA works for different CNN models such as VGG Simonyan and Zisserman (2014) and He et al. (2016) . Finally, we compare the performance of iRDA with some other state-of-the-art compression methods. Cheng et al. (2017) reviews the work on compressing neural network models, and categorizes the related methods into four schemes: parameter pruning and sharing, low-rank factorization, transfered/compact convolutional filters and knowledge distillation. Among them, Liu et al. (2015) uses sparse decomposition on the convolutional filters to get sparse neural networks, which could be classified to the second scheme. Apart from that, Han et al. (2015b) prunes redundant connections by learning only the important parts. Louizos et al. (2017) starts from a Bayesian point of view, and removes large parts of the network through sparsity inducing priors. Yin et al. (2018) He et al. (2018) combines reinforcement learning methods to compression. Li and Hao (2018) considers deep learning as a discrete-time optimal control problem, and obtains sparse weights on ternary networks. Recently, Feng (2018) applies RDA to fully-connected neural network models on MNIST.

2. RELATED WORKS:



3. ALGORITHMS:

Let z = (x, y) be an input-output pair of data, such as a picture and its corresponding label in a classification problem, and f (w, z) be the loss function of neural networks, i.e. a scalar function that is differentiable w.r.t. weights w. We are interested in the expected risk minimization problem

min w {E z f (w, z)} .

(1)

The empirical risk minimization

EQUATION

is an approximation of (1) based on some finite given samples {z 1 , z 2 , . . . , z T } , where T is the size of the sample set.

Regularization is a useful technique in deep learning. In general, the regularized expected risk minimization has the form

EQUATION

where Ψ(w) is a regularization term with certain effect. For example, Ψ(w) = w 2 2 may improve the generalization ability, and an 1 -norm of w can give sparse solutions. The corresponding regularized empirical risk minimization we concern takes the form

EQUATION

)

SDA method is a special case of primal-dual subgradient method first proposed in Nesterov (2009) . Xiao (2010) proposes RDA for online convex and stochastic optimization. RDA not only keeps the same convergence rate as Prox-SGD, but also achieves more sparsity in practice.

In next sections, we will discuss the connections between SDA and SGD, as well as RDA and Prox-SGD. We then propose iRDA for 1 regularized problem of deep neural networks.

3.1. SIMPLE DUAL AVERAGING METHOD:

As a solution of (2), SDA takes the form

EQUATION

The first term t τ =1 g τ , w is a linear function obtained by averaging all previous stochastic gradient. g t is the subgradient of f t . The second term h(w) is a strongly convex function, and {β t } is a nonnegative and nondecreasing sequence which determines the convergence rate. As g τ (w τ ), τ = 1, . . . , t -1 is constant in current iteration, we use g τ instead for simplicity in the following. Since subproblem equation 5 is strongly convex, it has a unique optimal solution w t+1 . Let w 0 be the initial point, and h(w) = 1 2 w -w 0 2 2 , the iteration scheme of SDA can be written as

EQUATION

where ḡt = 1 t t τ =1 g τ , w . Let β t = γt α , SDA can be rewritten recursively as

EQUATION

where

1 -1 -1 t α → 0 and 1 -1 t α → 1 as t → ∞.

Thus, SDA can be viewed as a perturbation of SGD.

3.2. PROXIMAL STOCHASTIC GRADIENT DESCENT AND REGULARIZED DUAL AVERAGING METHODS:

For the regularized problem (4), we recall the well-known Prox-SGD and RDA method first. At each iteration, Prox-SGD solves the subproblem

EQUATION

Specifically, α t = 1 γ √ t obtains the best convergence rate. The first two terms are an approximation of the original objective function. Note that without the regularization term Ψ, equation 8 is equivalent to SGD. It can be written in forward-backward splitting (FOBOS) scheme

EQUATION

EQUATION

where the forward step is equivalent to SGD, and the backward step is a soft-thresholding operator working on w t+ 1 2 with the soft-thresholding parameter α t . Different from Prox-SGD, each iteration of RDA takes the form

EQUATION

Similarly, taking h(w) = 1 2 w -w 0 2 2 , RDA can be written as

EQUATION

or equivalently,

EQUATION

EQUATION

where β t = γ √ t to obtain the best convergence rate. From equation 14, one can see that the forward step is actually SDA and the backward step is the soft-thresholding operator, with the parameter t/β t .

3.3. 1 REGULARIZATION AND THE SPARSITY:

Set Ψ(w) = λ w 1 . The problem (4) then becomes

EQUATION

)

where λ is a hyper-parameter that determines sparsity.

In this case, from Xiao's analysis of RDA Xiao (2010) , the expected cost Eφ( wt ) -φ associated with the random variable wt converges with rate O(

1 √ t ) when β t = γ √ t.

This convergence rate is consistent with FOBOS Duchi and Singer (2009) . However, both results assume f to be a convex function, which can not be guaranteed in deep learning. Nevertheless, we can still verify that RDA is a powerful sparse optimization method for deep neural networks.

We conclude the closed form solutions of Prox-SGD and RDA for equation 16 as follows.

1. The subproblem of Prox-SGD

EQUATION

has the closed form solution

w (i) t+1 =      w (i) t -α t (g (i) t + λ), w (i) t -α t g (i) t > α t λ, 0, |w (i) t -α t g (i) t | ≤ α t λ, w (i) t -α t (g (i) t -λ), w (i) t -α t g (i) t < -α t λ. (18)

2. The subproblem of RDA

w t+1 = arg min w ḡT t w + β t 2t w -w 0 2 2 + λ w 1 (19)

has the closed form solution

w (i) t+1 =      w (i) 0 -t βt (ḡ (i) t + λ), w (i) 0 -t βt ḡ(i) t > t βt λ, 0, |w (i) 0 -t βt ḡ(i) t | ≤ t βt λ, w (i) 0 -t βt (ḡ (i) t -λ), w (i) 0 -t βt ḡ(i) t < -t βt λ.

(20)

3. The √ t-proximal stochastic gradient method has the form

EQUATION

The difference between √ t-Prox-SGD and Prox-SGD is the soft-thresholding parameter chosen to be √ t. It has the closed form solution

EQUATION

It is equivalent to

EQUATION

where the objective function is actually an approximation of

EQUATION

We can easily conclude that this iteration will converge to w = 0

if α t = 1 γ √ t and β t = γ √ t.

Now compare the threshold λ P G = α t λ of PG and the threshold λ RDA = t βt λ of RDA. With

α t = 1 γ √ t and β t = γ √ t, we have λ P G → 0 and λ RDA → ∞ as t → 0.

It is clear that RDA uses a much more aggressive threshold, which guarantees to generate significantly more sparse solutions.

3.4. ITERATIVE RDA METHOD FOR DEEP NEURAL NETWORKS:

Note that when Ψ = λ w 1 , RDA requires w 1 = w 0 = 0. However, this will make deep neural network a constant function, with which the parameters can be very hard to update. Thus, in Algorithm 1, we modify the RDA method as Step 1, where w 1 can be chosen not equal to 0, and add an extra Step 2 to improve the performance. We also prove the convergence rate of Step 1 for convex problem is O(

1 √ t ) when β t = O( √ t).

Theorem 3.1 Assume there exists an optimal solution w to the problem (3) with Ψ(w) = λ w 1 that satisfies h(w ) ≤ D 2 for some D > 0, and let φ = φ(w ). Let the sequences {w t } t≥1 be generated by Step 1 in iRDA, and assume g t * ≤ G for some constant G. Then the expected cost Eφ( wt ) converges to φ with rate O(

1 √ t ) Eφ( wt ) -φ = O( 1 √ t ),

with wt = 1 t t τ =1 w τ . See Appendix A for the proof.

3.5. INITIALIZATION:

To apply iRDA, the weights of a neural network should be initialized differently from that in a normal optimization method such as SGD or its variants. Our initialization is based on LeCun et al.

(2012), Glorot and Bengio (2010) and He et al. (2015) , with an additional re-scaling. Let s be a scalar, the mean and the standard deviation of the uniform distribution for iRDA is zero and

σ iRDA = s 2 n , n = k 2 c (25)

respectively, where c is the number of channels, and k is the spatial filter size of the layer (see He et al. (2015) ).

Choosing a suitable s is important when applying iRDA. As shown in Table 5 and Table 6 in Appendix B, if s is too small or too large, the training process could be slowed down and the generalization ability may be affected. Moreover, a small s usually requires much better initial weights, which results in too many samplings in initialization process. In our experiments, a good s for iRDA is usually much larger than √ 2, and unsuitable for SGD algorithms.

3.6. ITERATIVE RETRAINING:

Iterative retraining is a method that only updates the non-zero parameters at each iteration. A trained model can be further updated with retraining, thus both the accuracies and sparsity can be improved.

See Table 4 for comparisons on CIFAR-10.

Algorithm 1 The iterative RDA method for 1 regularized DNNs Input:

• A strongly convex function h(w) = w 2 2 . • A nonnegative and nondescreasing sequence β t = γ √ t.

Step 1: RDA with proper initialization Initialize: set w 0 = 0, ḡ0 = 0 and randomly choose w 1 with methods explained in section 3.5. for t=1,2, ..., T do

Given the sample z it and corresponding loss function f it .

Compute the stochastic gradient

EQUATION

Update the average gradient:

EQUATION

Compute the next weight vector:

EQUATION

)

Step 2: iterative retraining for t=T+1,T+2,T+3, ... do Given the sample z it and corresponding loss function f it .

Compute the stochastic gradient

EQUATION

Set (g t ) j = 0 if (w t ) j = 0 for every j.

Update the average gradient:

EQUATION

Compute the next weight vector:

EQUATION

)

4. EXPERIMENTS:

In this section, σ denotes the sparsity of a model, i.e. σ = quantity of zero parameters quantity of all parameters .

(32)

All neural networks are trained with mini-batch size 128.

4.1. PARAMETERS TEST:

We provide a test on different hyper-parameters, so as to give an overview of their effects on performance, as shown in Table 7 . We also show that the sparsity and the accuracy can be balanced with iRDA by adjusting the parameters λ and γ, as shown in Table 8 . Both tables are put in Appendix C.

4.2. MAIN RESULTS:

We compare iRDA with several methods including prox-SGD, √ t-SGD and normal SGD, on different datasets including MNIST, CIFAR-10, CIFAR-100 and ImageNet(ILSVRC2012). The main results are shown in Table 1 . Table 2 shows the performance of iRDA on different architectures including ResNet18, VGG16 and VGG19. Table 3 shows the performance of iRDA on different Figure 1 : The first 120 epochs of loss curves corresponding to Table 1 , and the sparsity curve for another result, where the top-1 validation accuracy is 91.34%, and σ = 0.87.

datasets including MNIST, CIFAR-10, CIFAR-100 and ImageNet(ILSVRC2012). In all tables, SGD denotes stochastic gradient methods with momentum Ruder (2016).

4.3. COMPARISON:

Currently, many compression methods include human experts involvement. Some methods try to combine other structures in training process to automatize the compression process. For example, He et al. (2018) combines reinforcement learning. iRDA, as an algorithm, requires no extra structure.

As shown above, iRDA can achieve good sparsity while keeping accuracy automatically, with carefully chosen parameters. For CIFAR-10, we compare the performance of iRDA with some other state-of-art compression methods in Table 4 . Due to different standards, σ is referred to directly or computed from the original papers approximately.

5. CONCLUSION:

In comparison with many existing rule-based heuristic approaches, the new approach is based on a careful and iterative combination of 1 regularization and some specialized training algorithms. We find that the commonly used training algorithms such as SGD methods are not effective. We thus develop iRDA method that can be used to achieve much better sparsity. iRDA is a variant of RDA methods that have been used for some special types of online convex optimization problems in the literature. New elements in the iRDA mainly consist of judicious initialization and iterative retraining. In addition, iRDA method is carefully analyzed on its convergence for convex objective functions.

Many deep neural networks trained by iRDA can achieve good sparsity while keeping the same validation accuracy as those trained by SGD with momentum on many popular datasets. This result shows iRDA is a powerful sparse optimization method for image classification problems in deep learning fields. A PROOF OF THEOREM 3.1

One of the differences between RDA Xiao (2010) and iRDA is that the former one takes w 1 = arg min w h(w) whereas the latter one chooses w 1 randomly. In the following, we will prove the convergence of iRDA Step 1 for convex problem. The proofs use Lemma 9, Lemma 10, Lemma 11 directly and modify Theorem 1 and Theorem 2 in Xiao (2010) . For clarity, we have some general assumptions:

• The regularization term Ψ(w) is a closed convex function with convexity parameter σ and domΨ is closed.

• For each t ≥ 1, f t (w) is convex and subdifferentiable on domΨ.

• h(w) is strongly convex on domΨ and subdifferentiable on rint(domΨ) and also satisfies

EQUATION

)

Without loss of generality, assume h(w) has convexity parameter 1 and min w h(w) = 0.

• There exist a constant G such that

EQUATION

• Require {β} t≥1 be a nonnegative and nondecreasing sequence and

EQUATION

Moreover, we could always choose β 1 ≥ σ such that β 0 = β 1 .

• For a random choosing w 1 , we assume

EQUATION

)

First of all, we define two functions:

EQUATION

EQUATION

)

The maximum in (37) is always achieved because F D = {w ∈ domΨ|h(w) ≤ D 2 } is a nonempty compact set. Because of (35), we have σt+β t ≥ β 0 > 0 for all t ≥ 0, which means tΨ(w)+β t h(w) are all strongly convex, therefore the maximum in ( 38) is always achieved and unique. As a result, we have domU t = domV t = E * for all t ≥ 0. Moreover, by the assumption (33), both of the functions are nonnegative. Let s t denote the sum of the subgradients obtained up to time t in iRDA Step 1, that is

EQUATION

and π t (s) denotes the unique maximizer in the definition of V t (s)

EQUATION

which then gives w t+1 = π t (-s t ).

(41)

Lemma A.1 For any s ∈ E * and t ≥ 0, we have

EQUATION

)

For a proof, see Lemma 9 in Xiao (2010) .

the maximization term in ( 55) is in fact U t (-s t ), therefore, by applying Lemma A.1, we have

EQUATION

)

Next, we show that ∆ t is an upper bound for the right-hand side of inequality (56). We consider τ ≥ 2 and τ = 1 respectively. For any τ ≥ 2, we have

EQUATION

where ( 47),( 39),( 45) and ( 43) are used. Therefore, we have

g τ , w τ -w 0 + Ψ(w τ +1 ) ≤ V τ -1 (-s τ -1 ) -V τ (-s τ ) + g τ 2 * 2(σ(τ -1) + β τ -1 ) , ∀τ ≥ 2.

For τ = 1, we have a similar inequality by using ( 49)

g 1 , w 1 -w 0 + Ψ(w 2 ) ≤ V 0 (-s 0 ) -V 1 (-s 1 ) + g 1 2 * 2β 0 .

Summing the above inequalities for τ = 1, ..., t and noting that V 0 (-s 0 ) = V 0 = 0, we arrive at

t τ =1 g τ , w τ -w 0 + Ψ(w τ +1 ) + V t (-s t ) ≤ t τ =1 g τ 2 * 2(σ(τ -1) + β τ -1

) .

Since Ψ(w t+1 ) ≥ 0, we subtract it from the left hand side and add Ψ(w 1 ) to both sides of the above inequality yields

EQUATION

Combing ( 54), ( 56), (57) and using assumption (34) and (36)we conclude

R t (w) ≤ δ t ≤ ∆ t = Q + β t D 2 + G 2 2 t-1 τ =0 1 στ + β τ .

Lemma A.5 Assume there exists an optimal solution w to the problem (3) that satisfies h(w ) ≤ D 2 for some D > 0, and let φ = φ(w ). Let the sequences {w t } t≥1 be generated by iRDA Step 1, and assume g t * ≤ G for some constant G. Then for any t ≥ 1, the expected cost associated with the random variable wt is bounded as

Eφ( wt ) -φ ≤ 1 t ∆ t .

Proof First, from the definition (50), we have the regret at w

R t (w ) = t τ =1 (f (w τ , z τ ) + Ψ(w τ )) - t τ =1 (f (w , z τ ) + Ψ(w )),

Let z[t] denote the collection of i.i.d. random variables (z , ..., z t ). We note that the random variable w τ , where 1 ≤ w ≥ t, is a function of (z 1 , ..., z τ -1 ) and is independent of (z τ , ..., z t ). Therefore

EQUATION

E z[t] (f (w , z τ ) + Ψ(w )) = E τ f (w , z τ ) + Ψ(w ) = φ(w ) = φ .

Since φ = φ(w ) = min w φ(w), we have the expected regret

EQUATION

Then, by convexity of φ, we have

EQUATION

Finally, from ( 59) and ( 58), we have

E z[t] φ( wt ) -φ ≤ 1 t t τ =1 E z[t] φ(w τ ) -tφ = 1 t E z[t] R t (w ).

Then the desired follows from that of Lemma A.4. Proof of Theorem 3.1 From Lemma A.5, the expected cost associated with the random variable wt is bounded as

EQUATION

Here, we consider 1 regularization function Ψ(w) = λ w 1 and it is a convex but not strongly convex function, which means σ = 0. Now, we consider how to choose β t for t ≥ 1 and β 0 = β 1 . First if β t = γt, we have 1 t • γtD 2 = γD 2 , which means the expected cost does not converge. Then assume β t = γt α , α > 0 and α = 1, the right hand side of the inequality (60) becomes

1 t Q + γD 2 t α + G 2 2γ t-1 τ =0 1 τ α ≤ 1 t Q + γD 2 t α + G 2 2γ 2 + t-1 τ =2 1 τ α ≤ 1 t Q + γD 2 t α + G 2 2γ 2 + t-1 1 1 τ α ∼ O(t α-1 + t -α ).

From above, we see that if 0 < α < 1, the expected cost converges and the optimal convergence rate O(t -1 2 ) achieves when α = 1 2 . Then we proved the Theorem 3.1. 

B INITIALIZATION:



:



Figures and Tables:

The main results of different methods. The architecture is ResNet18, and the dataset is CIFAR-10. This table shows the top-1 and top-5 accuracies on the validation dataset. iRDA achieves the highest top-1 accuracy and sparsity. See figure1for the corresponding loss curves.

Table content: <table><tr><td>Method</td><td colspan="2">TOP 1 Acc. TOP 5 Acc.</td><td>σ</td><td>λ</td><td>γ</td></tr><tr><td>SGD</td><td>92.69</td><td colspan="2">99.72 0.00</td><td colspan="2">N/A N/A</td></tr><tr><td>prox-SGD √ t-prox-SGD</td><td>89.80 82.47</td><td colspan="3">99.40 0.03 10 -5 99.07 0.72 10 -8</td><td>0.8 1.0</td></tr><tr><td>iRDA</td><td>93.47</td><td colspan="3">99.69 0.95 10 -6</td><td>1.0</td></tr></table>

iRDA on different Architectures. This table shows the top-1 and top-5 accuracies on the validation dataset. The results from SGD with momentum are in the brackets. iRDA works well on different CNN architectures.

Table content: <table><tr><td>ARCHITECTURE</td><td>TOP 1 Acc.</td><td>TOP 5 Acc.</td><td>σ</td><td>λ</td><td>γ</td></tr><tr><td>ResNet18</td><td colspan="5">93.47 (92.69) 99.69 (99.72) 0.95 10 -6 1.0</td></tr><tr><td>VGG16</td><td colspan="5">93.24 (93.42) 99.52 (99.79) 0.94 10 -6 1.0</td></tr><tr><td>VGG19</td><td colspan="5">91.87 (91.70) 99.37 (99.40) 0.98 10 -5 1.0</td></tr></table>

iRDA on different datasets. The architecture is ResNet18. This table shows the top-1 and top-5 accuracies on the validation dataset. The results from SGD with momentum are in the brackets. iRDA works well on different datasets.

Table content: <table><tr><td>DATASET</td><td>TOP 1 Acc.</td><td>TOP 5 Acc.</td><td>σ</td><td>λ</td><td>γ</td></tr><tr><td>MNIST</td><td>99.63 (99.65)</td><td colspan="3">100.00 0.95 10 -6</td><td>0.1</td></tr><tr><td>CIFAR-10</td><td colspan="4">93.47 (92.69) 99.69 (99.72) 0.95 10 -6</td><td>1.0</td></tr><tr><td>CIFAR-100</td><td colspan="5">72.29 (73.69) 89.94 (92.43) 0.56 10 -8 0.09</td></tr><tr><td colspan="5">ILSVRC2012 64.93 (70.58) 84.92 (89.64) 0.36 10 -8</td><td>0.1</td></tr></table>

iRDA and different state-of-the-art compression methods on CIFAR-10. This table shows the top-1 accuracies on the validation dataset. Due to different standards, σ is referred to directly or computed approximately. iRDA achieves almost the same accuracy and sparsity on VGG16, while the sparsity on ResNet18 is much better.

Table content: <table><tr><td colspan="2">ARCHITECTURE METHOD</td><td>TOP 1 Acc.</td><td>σ</td><td>λ</td><td>γ</td></tr><tr><td>ResNet-50</td><td>AMC(R Param ) He et al. (2018)</td><td colspan="2">93.64 0.60</td><td colspan="2">N/A N/A</td></tr><tr><td>ResNet-18</td><td>iRDA</td><td colspan="3">93.47 0.95 10 -6</td><td>1.0</td></tr><tr><td>VGG-16</td><td>VIBNet Dai et al. (2018)</td><td colspan="2">93.80 0.94</td><td colspan="2">N/A N/A</td></tr><tr><td>VGG-16</td><td>iRDA</td><td colspan="3">93.24 0.94 10 -6</td><td>1.0</td></tr></table>

Different initialization scalars on CIFAR-10 with iRDA. The architecture is ResNet18. λ = 10 -6 and γ = 1.0. This table shows the top-1 accuracies on the validation dataset. All models are trained for 120 epochs.

Table content: <table><tr><td>s</td><td colspan="2">TOP 1 Acc. TOP 5 Acc.</td><td>σ</td></tr><tr><td>1, 2</td><td>10.00</td><td colspan="2">50.00 N/A</td></tr><tr><td>3</td><td>85.52</td><td colspan="2">99.24 0.98</td></tr><tr><td>4</td><td>86.72</td><td colspan="2">99.45 0.97</td></tr><tr><td>5</td><td>90.03</td><td colspan="2">99.44 0.95</td></tr><tr><td>10</td><td>90.67</td><td colspan="2">89.50 0.94</td></tr><tr><td>100</td><td>91.41</td><td colspan="2">99.58 0.84</td></tr><tr><td>1000</td><td>90.36</td><td colspan="2">99.62 0.63</td></tr><tr><td>10000</td><td>71.80</td><td colspan="2">97.94 0.34</td></tr><tr><td>20000</td><td>68.06</td><td colspan="2">97.39 0.99</td></tr></table>

Different initialization scalars on CIFAR-100 with iRDA. The architecture is ResNet18. λ = 10 -8 and γ = 0.1. This table shows the top-1 accuracies on the validation dataset. All models are trained for 120 epochs.

Table content: <table><tr><td>s</td><td colspan="2">TOP 1 Acc. TOP 5 Acc.</td><td>σ</td></tr><tr><td>1</td><td>63.67</td><td colspan="2">87.85 0.91</td></tr><tr><td>2</td><td>66.90</td><td colspan="2">88.53 0.60</td></tr><tr><td>5</td><td>65.47</td><td colspan="2">88.09 0.60</td></tr><tr><td>10</td><td>65.54</td><td colspan="2">88.21 0.42</td></tr><tr><td>15</td><td>64.22</td><td colspan="2">87.53 0.43</td></tr><tr><td>25</td><td>63.06</td><td colspan="2">88.10 0.50</td></tr><tr><td>30</td><td>62.75</td><td colspan="2">86.80 0.42</td></tr><tr><td>50</td><td>64.48</td><td colspan="2">87.14 0.38</td></tr><tr><td>100</td><td>60.00</td><td colspan="2">86.14 0.36</td></tr></table>

Peer review (iclr2019):
 The submission made a few modifications to the RDA (regularized dual averaging) optimization solver to form the proposed "iterative RDA (iRDA)" algorithm, and shows that empirically the proposed algorithm could reduce the number of non-zero parameters by an order of magnitude on CIFAR10 for a number of benchmark network architectures (Resnet18, VGG16, VGG19). The experimental result of the paper is strong but the algorithm and also a couple of statements seem flawed. In particular: * For Algorithm 1, consider the case when lamda=0 and t -> infinity, the minimization eq (28) goes to negative infinity for any non-zero gradient, which corresponds to an update of infinitely large step size. It seems something is wrong. * Why in Step 2 the algorithm sets both g_t and w_t to 0 during each iterate? It looks so wrong. *The whole paper did not mention batch size even once. Does the algorithm apply only with batch size=1? *What is the "MRDA" method in the figure? Is it mentioned anywhere in the paper? *What are "k", "c" in eq (25)? Are they defined anywhere in the paper? *Theorem states 1/sqrt(t) convergence but eq (28), (31) have updates of unbounded step size. How is this possible?