Adaptive Optimizers with Sparse Group Lasso
Authors: Yun Yue
Suo Tong
Zhen Zhang
Yongchao Liu
Chunyang Wen
Huanjun Bao
Jinjie Gu
Yixiang Mu
Venue:  (2021)
Keywords: adaptive optimizers
sparse group lasso
DNN models
online optimization

Abstract: We develop a novel framework that adds the regularizers to a family of adaptive optimizers in deep learning, such as MOMENTUM, ADAGRAD, ADAM, AMSGRAD, ADAHESSIAN, and create a new class of optimizers, which are named GROUP MOMENTUM, GROUP ADAGRAD, GROUP ADAM, GROUP AMSGRAD and GROUP ADAHESSIAN, etc., accordingly. We establish theoretically proven convergence guarantees in the stochastic convex settings, based on primal-dual methods. We evaluate the regularized effect of our new optimizers on three large-scale real-world ad click datasets with state-of-the-art deep learning models. The experimental results reveal that compared with the original optimizers with the post-processing procedure which use the magnitude pruning method, the performance of the models can be significantly improved on the same sparsity level. Furthermore, in comparison to the cases without magnitude pruning, our methods can achieve extremely high sparsity with significantly better or highly competitive performance.

Under review as a conference paper at ICLR 2021
ADAPTIVE OPTIMIZERS WITH SPARSE GROUP LASSO
Anonymous authors Paper under double-blind review
ABSTRACT
We develop a novel framework that adds the regularizers to a family of adaptive optimizers in deep learning, such as MOMENTUM, ADAGRAD, ADAM, AMS- GRAD, ADAHESSIAN, and create a new class of optimizers, which are named GROUP MOMENTUM, GROUP ADAGRAD, GROUP ADAM, GROUP AMSGRAD and GROUP ADAHESSIAN, etc.. accordingly. We establish theoretically proven convergence guarantees the stochastic convex settings, based on primal-dual methods. We evaluate the regularized effect of our new optimizers on three large- scale real-world ad click datasets with state-of-the-arr deep learning models. The experimental results reveal that compared with the original optimizers with the post-processing procedure which use the magnitude pruning method, the perfor- mance of the models can be significantly improved on the same sparsity level. Furthermore, in comparison to the cases without magnitude pruning, our methods can achieve extremely high sparsity with significantly better or highly competitive performance.
INTRODUCTION
With the development of deep learning, deep neural network (DNN) models have been widely used in various machine learning scenarios such as search, recommendation and advertisement, and achieved significant improvements. In the last decades, different kinds of optimization methods based on the variations of stochastic gradient descent (SGD) have been invented for training DNN models. However, most optimizers cannot directly produce sparsity which has been proven effec- tive and efficient for saving computational resource and improving model performance especially in the scenarios of very high-dimensional data. Mcanwhile, the simple rounding approach very unreliable due to the inherent low accuracy of these optimizers.
In this paper, we develop new class of optimization methods, that adds the regularizers especially sparse group lasso to prevalent adaptive optimizers, and retains the characteristics of the respective optimizers. Compared with the original optimizers with the post-processing procedure which use the magnitude pruning method, the performance of the models can be significantly improved on the same sparsity level. Furthermore, in comparison to the cases without magnitude pruning, the new optimizers can achieve extremely high sparsity with significantly better or highly competitive performance. this section, we describe the two types of optimization methods, and explain the motivation of our work.
1.1 ADAPTIVE OPTIMIZATION METHODS
Due to the simplicity and effectiveness, adaptive optimization methods (Robbins & Monro 195T
Polyak 1964 Duchi et al. 2011 Zeiler 2012) Kingma& & Ba, 2015 Reddi et al. [018]] Yao et al. 20200 have become the de-facto a algorithms used in deep learning. There are multiple variants, but they can be represented using the general update formula (Reddi al. 2018):
Tz+1 I2 a.m//V
where a is the step size, m, is the first moment term which is the weighted average of gradient Se and V, is the so called second moment term that adjusts updated velocity of variable 24, in each direction. Here, VV: := V. m2/ /V, == VV, m, By setting different m,, Ve and a, we can derive different adaptive optimizers including MOMENTUM (Polyak) 1964). ADAGRAD (Duchi jet al., (20TT) ADAM (Kingma & Ba 2015), AMSGRAD (Reddi et al. 2018) and ADAHESSIAN Yao al.) 2020), etc. See Table

---

Under review as a conference paper at ICLR 2021
Table 1: Adaptive optimizers with choosing different my, V, and or.
Optimizer
m
02
SGD
9t
vi
MOMENTUM
7 + gt
a
ADAGRAD
9t
diag Ei= gi)lt
yi
a
1- 1-85
ADAM
-1m--1 + (1 B1)g:
32 V2 + (1 - 32 diag ddaagg??"
AMSGRAD
m + (1 -B19gt
max (V-1, 1 + (1 - 82 diag(o)))
ADAHESSIAN -1m + -B1g
32V1-1 + (1 +1
D. (tag((H), where H, is the Hessian matrix.
1.2 REGULARIZED OPTIMIZATION METHODS
(FTRL) (McMahan & Streeter 2010 McMahan et al. 2013) has been widely used click-through rates (CTR) prediction problems, which adds E--reuularization (lasso) to logistic regression and can effectively balance the performance of the model and the spar- sity of features. The update formula (McMahan et al. 2013) is:
nollow-the-regllarizede
1 Σ Ft+1 = arg min D1rt x ++
0,11 x.112 X1 |2/121
2
rell2 2 is the strong convex term that stabilizes the algorithm and X1 ||=||| the regularization term that produces sparsity. However, it doesn't 't work well DNN models since one input feature can correspond to multiple weights and lasso only can make single weight zero hence can't I effectively delete zeros features.
where 91:1 = =E Ex= o.IL= cate-ralli
To solve above problem. Ni et al. (219)) adds the Ê21 Var-regularization (group lasso) to FTRL, which is named G-FTRL. Yang et al. (2010) conducts the research on a group lasso method for online learning that adds reguragulannzttion to the algorithm of Dual Averaging (DA) (Nesterov) 2009). which is named DA-GL. Even so, these two methods cannot been applied to other optimizers. Different scenarios are suitable for different optimizers in the deep learning fields. For example, MOMENTUM [Polyak 1964) is typically used in computer vision; ADAM (Kingma & Ba 2015) is used for training transformer models for natural language processing; and ADAGRAD (Duchi et al.) 2011) is used for
recommendation systems. If we want to produce sparsity of the model in some scenario, we have to change optimizer which probably influence the performance of the model.
1.3 MOTIVATION
Eq. ① can be rewritten into this form:
Ø1+1 arg min m, x I1 (x 21)112.
(3)
20,
Furthermore, we can rewrite Eq. into
T141 = arg min ma. a 20 +
1QQ (x x.)1 201
(4)
==1
where mi. Σ M. -= Q./a, VViaa, It is casy prove that Eq. and Eq. are equivalent using the method of induction. The matrices Q. can be interpreted as generalized learning rates. To our best knowledge, V. of Eq. ① of all the adaptive optimization methods diagonal for the computation simplicity. Therefore, we consider Q₂ as diagonal matrices throughout this paper.
We find that Eq. 4 is similar to Eq. except for the regularization term. Therefore, we add the regularization term ((x to Eq. which is the sparse group lasso penalty also including f--
2

---

Under review as a conference paper at ICLR 2021
regularization that can diffuse weights of neural networks. The concrete formula
vx(x)
Σ (11l + A21 dzw 114, [122) + >2 >22122 10
(5)
where Å₁ A21, A2 are regularization parameters of ε1, 621 l respectively, G is the total number of groups weights, x the weights of group and dya is the size group g. In DNN models, each group is defined as the set of outgoing weights from unit which hidden neuron, or bias unit (see, e.g., Se5adaaaaa et al. (2016)). As can be arbitrary positive matrix
be an input feature,
satisfying A,+1= = A,, e.g., A, = II. In Section 2.1 we let A, ( c=1 the closed-form solution directly, where Q is a diagonal matrix whose diagonal elements are part of Q, corresponding to Zig. The ultimate update formula is:
Q + >² just for solving
1 20s
11 (o 1.)0+11++ (.)))
T++1 arg min mi. x
(6)
1.4 OUTLINE OF CONTENTS
The rest of the paper is organized follows. In Section 1.5 introduce the necessary notations and technical background.
In Section 2 present the closed-form solution of Eq. and the algorithm of general framework of adaptive optimization methods with sparse group lasso. We prove the algorithm is equivalent to adaptive optimization methods when regularization terms vanish. In the end, give two concrete examples of the algorithm
In Section 3
derive the regret bounds of the method and convergence rates.
In Section
we validate the performance of new optimizers in the public datasets.
In Section summarize the conclusion.
list the details of GROUP ADAM and Group Adagrad respectively. Appendices C contain technical proofs of our main results and Appendix G includes the details of the empirical results of Section
Appendices A A
1.5 NOTATIONS AND TECHNICAL BACKGROUND
We use lowercase letters denote sealars and vectors, and uppercase letters denote matrices. We denote sequence of vectors by subscripts, that is, Ii...., Z4, and entries of each vector by an additional subscript, e.g., Tt,i- We use the notation Лıa as a shorthand for E Is- Similarly we write mı. for sum of the first moment mys and fi:t denote the function f1x(2) Et= (ar).. Let M, = [m...... .m]] denote the matrix obtained by concatenating the vector sequence {m ( and Mr. denote the i-th row of this matrix which amounts to the concatenation of the i-th component of each vector. The notation A > O (resp. A > 0) for matrix A means that A is symmetric and positive semidefinite (resp. definite). Similarly, the notations A > and A > B mean that A- B > () and A B > () respectively, and both tacitly assume that A and B are symmetric. Given A > 0, we write A for the square root of A, the unique X > 0 such that X Streeter (2010), Section 1.4).
McMahan &
Let E be finite-dimension real vector space, endowed with the Mahalanobis norm llA which is denoted by || ll Vl: A-) as induced by A 0. Let E" be the vector space of all linear functions on E. The dual space E" endowed with the dual norm | = V(,A-I,)
Let Q be closed convex set in E. A continuous function h(x::) is called strongly convex on Q with norm || F C dom and there exists a constant a > 0 such that for all x, y E Q and a E [0 we have
h(ar + - a)y) < (x + a) kly) ga(1 - a)l vl
"oo fulfill research interest of optimization methods, will release the code in the future.
3

---

Under review as a conference paper at ICLR 2021
The constant a is called the convexity parameter of h(x), or the modulus of strong convexity. We also denote by || I| = lla Further, if h differential, we have
h(y) 2 h(x)) + (Vh(z), y x) + 2 | - v
analysis framework. On each round 1, 1....y T, convex loss function Jt Q + IR is chosen, and we pick a point 2t E Q hence get loss f=(2)). Our goal is minimizing the regret which is defined the quantity
We use online convex optimization
T
T
R = Σ f((z)) 1=1
min Ef(l) ZE@ ==1
Online convex optimization can be seen as a generalization of stochastic convex optimization. Any regret minimizing algorithm can be converted to a stochastic optimization algorithm with conver- gence rate ((Tr/T) (T) using online-to-batee conversion technique (Littlestone 1989..
In this paper, we assume @ & = R", hence we have e = R We write s x or s x for the standard inner product between 8, R For the standard Euclidean norm, |||||| |
v ax) and || ||I||2. We also || Σ [x,01] and || max (/x(() denote f--nrrm and -orm respectively, where (1)) is the i-th element of x.
ALGORITHM
2.1 CLOSED-FORM SOLUTION
We will derive the closed-form solution of Eq. 66) with specific A, and Algorithm modification in this section. We have the following theorem.
D with slight
Of + X2II) of Eq. (5) 2, = 2 + m, 2s x, at each iteration Theorem 1, Given A, = (E Zo,
t 1,...,T and 2 = 0, the optimal solution of Eq. (6) is updated accordingly as follows:
Q.
Le+1
ax
2 max(1
||5e|1
.08ss
(8)
s=1
where the i-th element of is defined
if f/22,1 & A sign(2r,)) 21,1 otherwise,
81,1
(9)
3, is defined as
Q. + X21)
8
-st
(10)
20
and Et Qu is the diagonal and positive definite matrix.
The proof Theorem is given in Appendix C We slightly modify K where we let ă, = st. Our
purpose is to let every entry of the group have the same effect of l21 regulaaaaiii..nn. Hence, get Algorithm Furthermore, we have the following theorem which shows the relationship between Algorithm and adaptive optimization methods. The proof is given in Appendix D
Theorem 2. If regularization terms of Algorithm vanish, Algorithm is equivalent to Eq. ①
2.2 CONCRETE EXAMPLES
Using Algorithm I we can easily derive the new optimizers based on ADAM Kingma & Ba 2015).
ADAGRAD (uuchi et al. 2011) which we call GROUP ADAM, GROUP ADAGRAD respectively.
GROUP ADAM
The detail of the algorithm is given in Appendix A From Theorem 2 we know that when A₁. Ags Az1 are all zeros, Algorithm is equivalent to ADAM (Kingma & Ba 2015).
4

---

Under review as a conference paper at ICLR 2021
Algorithm Generic framework of adaptive optimization methods with sparse group lasso
1: Input: parameters λ1, A21, A2
æn E KK.. step size {ar > 0) sequence functions { 2h di initialize zq 0, Vo Okp
2: for = to I' do
3: = fx++))
4:
0e(01,.... 2c)
and V (01.
v V--1
5:
6: 2t + 21-1 + mi 111
Qi ot
oc
E (I...., n ) do
if |a, & A otherwise.
8: $1,1 sign(2r,;)A1 2e,
9: end for
10: I++1 (VT + 2x2l) max(1
0)8
||stl2
end for
GROUP ADAGRAD
The detail of the algorithm is given in Appendix B Similarly, from Theorem 2 when Å1, λ2, X21 are all zeros, Algorithm iis equivalent to ADAGRAD Duchi et al., 22011) Furthermore, we can find that when \21 O, Algorithm BJis equivalent FTRL (McMahan al. 2013). Therefore, GROUP ADAGRAD can also be called GROUP FTRL from the research of Ni et al. (2019).
Similarly, GROUP MOMENTUM, GROUP AMSGRAD, GROUP ADAHESSIAN, etc., can be derived from MOMENTUM (Polyak) 1964), AMSGRAD (Reddi et al.) (011)), ADAHESSIAN Yao et al. 2020). etc., with the same framework and we will not list the details.
CONVERGENCE AND REGRET ANALYSIS
Using the framework developed in Nesterov 2009)) Xiao 2010 Duchi al. (2011), have the following theorem providing the bound of the regret.
Theorem 3. Let the sequence { be defined by the update and
21 = arg min
|| - c
(11)
=EQ
where e an arbitrary constant vector. Suppose ft(z) is convex for any t 2 1 and there exists an optimal solution x² of Vi== ie,, x= = arg minzer ET Si(x), which satisfies the condition
(m--1. - -r) 20, E [T),
(12)
where me is the weighted average of the grudient fe(xz) and [T] (1...., T} for simplicity. Withou loss of generality, assume
m4 = 71 + St:
(13)
where y < 1 and mo = 0. Then
L - (x xx)
Rr S (x(x") +
Σ 1=1
melli: 1'
(14)
201
where I| lla; is the dual norm of l1 11 h, is 1-strongly convex with respect || Vlla for [T] and ho is 1-strongly convex with respect to
||
1|2-
The proof of Theorem 3 is given in Appendix E Since in most of adaptive optimizers, V, is the
weighted average of diag(g?) ? without loss of generality, we assume 0g and
V, v + diag(g?), 121,
(15)
where Vn and 7) < 1. Hence, we have the following lemma whose proof is given in Ap- pendix F.
5

---

Under review as a conference paper at ICLR 2021
Lemma 1. Suppose V1 is the weighted average of the square of the gradient which is defined by 13 a₂ = a, my defined by (13) and Vi satisfies the following arbitrary conditions:
1. 11- 1,
2. 11 < 1, 11 27
and KV. ž V for all 1 2 where K < 1.
Then we have
Σ mi
2x
Mr,
(16)
where v = max(7, k) and d is the dimension of st-
We can always add 6²1 to V at each step to ensure V > 0. Therefore, (x) is 1-strongly convex with respect to || VIv0-L+V///." Let max 119: bos for t 1, we have
(4, am V2-1) -mm)) 1 me as (diag(of) + vVVi11) - mi
| Ii
(17)
(mi - mi) || (
For f = 1, we have
(0 5 <(mi,a (diag (05) mi
||
(18)
am 2 2m1) |lm (
From 17 18 and Lemmal 1 we have
Lemma 2. Suppose Vo my. ar v, are defined the same as Lemma 1 max ry 1l9el 1 6,
||- 12; (. (6 + Vi) #.) for 2 1 and || -1:11 = (::on (152 + 1)T) Then
T
Σ Imelli; < 2a
MT
(19)
Therefore, from Theorem 3 and Lemma we have
Corollary 1. Suppose Vt, my Oc,, hü, v, are defined the same as Lemma there exist constants
G, Dr, D2 such that maxte(T] [| loo I G < 8. 1100" D2 and max 1| x Then
20 S D2.
Rr < dDi (
A + A21l
VTG 2a
+ d2)+ + +dolis + dG'
D2
+
a
VT.
(20)
2a
(1 v)3
The proof of Corollary iis given in F22 Furthermore, from Corollary 1 we have
Corollary 2. Suppose my is defined as 13 02 = a and satisfies the condition
19 There exist
constants G, D₁, D2 such that tGP V, max I1gelloo G. 1| 5 D2 and max 1|
x² ll S D2. Then
Rx < dD, d2n
VTG
A2) + SoDs) + dG
D2
+
VT.
(21)
2a
2a
(1 - v)2
Therefore, know that the regret of the update (6) is O (TV)) and can achieve the optimal conver- gence rate O(1/VT) under the conditions of Corollary 1 or Corollary

---

Under review as a conference paper at ICLR 2021
4 EXPERIMENTS
4.1 EXPERIMENT SETUP
We test the algorithms on three different large-scale real-world datasets with different neural network structures. These datasets are various display ads logs for the purpose of predicting ads CTR. The details are as follows.
a) The Avazu CTR dataset (Avazu, 2015) contains approximately 40M samples and 22 categorical features over 10 days. In order to handle categorical data, we use the one-hot-encoding based embedding technique (see, e.g., Wang et al. (2017), Section 2.1 or Naumov et al. (2019), Section 2.1.1) and get 9.4M features in total. For this dataset, the samples from the first 9 days (containing 8.7M one-hot features) are used for training, while the rest is for testing. Our DNN model follows the basic structure of most deep CTR models. Specifically, the model comprises one embedding layer, which maps each one-hot feature into 16-dimensional embeddings, and four fully connected layers (with output dimension of 64, 32, 16 and 1, respectively) in sequence.
b) The You datase You 2013) is another real-world dataset for ad click logs over 21 days. The dataset contains 16 categorical feature After one-hot encoding, we get a dataset containing 19.5M instances with 1033.1K input dimensions. We keep the original train/test splitting scheme, where the training set contains 15.4M samples with 937.7K one-hot features. We use Outer Product-based Neural Network (OPNN) (Qu al., 2016), and follow the standard settings of of et al. (2016), i.c., one embedding layer with the embedding dimension of 10, one product layer and three hidden layers of size 512, 256, 128 respectively where we set dropout rate at 0.5.
c) The third dataset is the Criteo Display Ads dataset (Criteo 2014) which contains approximately 46M samples over days. There are 13 integer features and 26 categorical features. After one- hot encoding of categorical features, we have total 33.8M features. We split the dataset into 7 partitions in chronological order and select the earliest 6 parts for training which contains 29.6M features and the rest for testing though the dataset has timestamp. We use Deep & Cross Network (DCN) (Wang et al. 2017) and choose the following setting c one embedding layer with embedding dimension 8, two deep layers of size 64 each, and cross layers.
For the convenience of discussion, we use MIP, OPNN and DCN to represent the aforementioned three datasets coupled with their corresponding models. It is obvious that the embedding layer has most of parameters of the neural networks when the features have very high dimension, therefore we just add the regularization terms to the embedding layer. Furthermore, each embedding vector considered group, and a visual comparison between 4, l21 and mixed regularization effect is given in Fig. 2 of Scarrdapae et al. (2016).
We treat the training set as the streaming data, hence train 1 epoch with batch size of 512 and do the validation. The experiments are conducted with 4-9 workers and 2-3 parameter servers, which depends on the different sizes of the datasets. We use the area under the receiver-operator curve (AUC) as the evaluation criterion since it is widely used in evaluating classification problems. Besides, some work validates AUC as a good measurement CTR estimation (Graepel al. 2010). We explore 5 learning rates from 1e-5 to le-1 with increments of 10x and choose the one with the best AUC for each new optimizer in the case of no regularization terms (It is equivalent to the original optimizer according to Theorem 2). All the experiments are run 5 times repeatedly and tested statistical significance using 1-test. Without loss generality, we choose two new optimizers to validate the performance, which are GROUP ADAM and GROUP ADAGRAD.
4.2 ADAM VS. GROUP ADAM
First, we compare the performance of the two optimizers on the same sparsity level. We keep X Ag be zeros and choose different values of Agi of Algorithm 2 i.c., GROUP ADAM, and achieve the
We only use the data from season 2 and 3 hecause of the same data schema.
See https:///// //gittbb/b com/ At omu201 4/ Ads RecSys Datasets/ for details.
'I Limited by training resources available, we don't It use the optimal hyperparameter settings of Wang al.
2017
7

---

Under review as a conference paper at ICLR 2021
same sparsity with ADAM that uses the magnitude pruning method, i..,, the norm of embedding vector from largest to smallest, and keep top N embedding vectors which depend on the sparsity when finish the training. Table reports the average results of the optimizers in the three datasets. Note that GROUP ADAM significantly outperforms ADAM on the AUC metric on the same sparsity level for most experiments. Furthermore, shown in Figure [ the same feg-regularization strength X21 has different effects of sparsity and accuracy on different datasets. The best choice of A2ι depends on the dataset as well as the application (For example, if the memory of serving resource is limited, sparsity might be relative more important). One can trade off accuracy to get more sparsity by increasing the value of X21
Table 2: AUC for the two optimizers and sparsity (feature rate) in parentheses. The best AUC for each dataset on each sparsity level is bolded. The p-value of the t-test of AUC also listed.
X21
MLP
OPNN
DCN
GROUP ADAM
ADAM
Grour ADAM
P-Natne
ADAM
GROUP ADAM
P-Vilue
ARAM
GROUP ADAM
P-Value
0.7452
0.7461
0.7551
0.7595
0.8018
0.8022
le-4
0.025
0.086
0.105
(0.974)
(0.974)
(0.078)
(0.078)
(0.518)
(0.518)
0.7464
0.7468
0.7491
0.7573
0.8017
0.8019
5e-4
0.466
0.091
0.487
(0.864)
(0.864)
(0.039)
(0.039)
(0.062)
(0.062)
0.7452
0.7468
0.7465
0.7595
0.8017
0.8017
1e-3
0.058
0.014
0.943
(0.701)
(0.701)
(0.032)
(0.032)
(0.018)
(0.018)
0.7452
0.7464
0.7509
0.7561
0.7995
0.8007
5c-3
0.155
0.041
9.11e-3
(0.132)
(0.132)
(0.018)
(0.018)
(4.2c-3)
(4.2c-3)
0.7430
0.7466
0.7396
0.7493
0.7972
0.7999
le-2
3.73e-4
0.031
5.97e-7
(0.038)
(0.038)
(9.2e-3)
(9.2e-3)
(2.5e-3)
(2.5e-3)
0300
Figure 1: The AUC across different sparsity on two optimizers for the three datasets. The x-axis is sparsity (number of non-zero features whose embedding vectors are not equal to O divided by the total number of features present the training data). The y-axis is AUC.
Next, we compare the performance of ADAM without post-processing procedure, i.e., magnitude pruning, and GROUP ADAM with appropriate regularization terms which we choose in Table on the AUC metric. In general, good default settings of X2 is 1e-5. The results are shown in Table Note that compared with ADAM, GROUP ADAM with appropriate regularization terms can achieve significantly better highly competitive performance with producing extremely high sparsity.
4.3 ADAGRAD VS. GROUP ADAGRAD
We compare with the performance of ADAGRAD without magnitude pruning and GROUP ADAGRAD with appropriate regularization terms which we choose in Table on the AUC metric. The results shown in Table 6 Again note that in comparison to ADAGRAD, GROUP ADAGRAD can not only achieve significantly better or highly competitive performance of AUC, but also effectively and efficiently reduce the dimensions of the features.
8

---

Under review as a conference paper at ICLR 2021
Table 4:
AUC for three datasets and sparsity (feature rate) in The best value for each dataset is bolded. The p- value of t-test is also listed.
The regularization terms of GROUP ADAM of three datasets.
Table 3:
parentheses.
Dataset
A ADAM 0.7458 (1.000)
GROUP ADAM
P- P-Vulue
Dataset
X1
A21
X
ML.P
0.7486 (0.018)
1.10e-3 (2.69e-11)
MLP
5e-3
le-2
1e-5
OPNN
0.7588 (0.827)
0.7617 (0.130)
0.289 (6.20e-11)
OPNN
8e-5
le-5
1e-5
DCN
4e-4
5e-4
le-5
DCN
0.8021 (1.000)
0.8019 (0.030)
0.422 (1.44e-11)
Table AUC for three datasets and sparsity (feature rate) in
Table 5: The regularization terms GROUP ADAGRAD
parentheses. The best value for each dataset is bolded. The p- value of I-test also listed.
of three datasets.
Dataset
ADAGRAD
GROUP ADAGRAD
P-Vulue
Dataset A1
A21
X2
MLP
0.7453 (1.000)
0.7469 (0.063)
0.106 (1.51e-9)
MLP
le-2
le-5
OPNN
0.7556 (0.827)
0.7595 (0.016)
0.026 (< 2.2e-16)
OPNN
8e-5
8e-5
le-5
DCN
4e-3
le-5
DCN
0.7975 (1.000)
0.7978 (0.040)
0.198 (3.94e-11)
4.4 DISCUSSION
In this section will discuss the hyperparameters of emdedding dimension, C reguulaariztio and 22 -egregularization to show how these hyperparameters affect the effects regularization.
Embedding Dimension Table of Appendix Geports the average results of different embedding dimensions MIP, whose optimizer is GROUP ADAM and regularization terms are same MILP of Ta Note that the sparsity increases with the growth of the embedding dimension. The reason that the square root of the embedding dimension the multiplier of L2 regulaarizztion
l vs. l21 From lines 8 and 10 of Algorithm [ we know that 2; has the same elements, the values of & and f21, i.e., A and A21. have the same regularization effects. However, this situation almost cannot be happen in reality. Without loss of generality, we set optimizer, A2 and embedding dimension be GROUP ADAM, le-5 and 16 respectively, and choose different values of Åi, A21- The results on MLP are shown in Table g of Appendix G It is obvious that regulaaaliiootoo is producing sparsity. For example, when A O and
much more effective than l e-rreulaarization A21 = 5e-3, the feature sparsity is 0. 031,,, while for A 5e-3 and d21 = 0, the feature sparsity is 0.470. Therefore, if just want to produce sparsity, we can only tune λ21 and use default settings for X2 and λ1 i.e., d2 = le-5 and d = 0.
CONCLUSION
In this paper, we propose a novel framework that adds the regularization terms to a family of adap- tive optimizers for producing sparsity of DNN models. We apply this framework create new class of optimizers. We provide closed-form solutions and algorithms with slight modification. We built the relation between new and original optimizers, i.e., our new optimizers become equiva- lent with the corresponding original ones, once the regularization terms vanish. We theoretically prove the convergence rate of the regret and also conduct empirical evaluation on the proposed op- timizers in comparison to the original optimizers with and without magnitude pruning. The results clearly demonstrate the advantages of our proposed optimizers in both getting significantly better performance and producing sparsity. Finally, would be interesting in the future to investigate the convergence in non-convex settings and evaluate our optimizers on more applications from fields such compute vision, natural language processing and etc.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Avazu. Avazu click-through rate prediction, 2015.
URL https: httpp::/wwww.aggg. httpss//www.kgggle..omm//
avazu streuuu-tttrreiiiiionn /dtt
Criteo. Criteo display ad challenge, 2014. URL http://laa..crrttee..mmm//222221
kaaggaa--ddipppaarroorettttiiiad dataset.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learn- ing and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011. doi: 10.5555/1953048.222100 2022006..
URLpttos: //trtts:://d.... acm. org/ doi/10. 5555/19530455 0ttg///oo///.5555/9933344
2021 068
Thore Graepel, Joaquin Quiñonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft's bing search engine. In Johannes Fürnkranz and Thorsten Joachims (eds.), Proceedings of the 27th Interna- fional Conference Machine Learning (ICML-10), June 21-24, 2010, Haifa, Israel, pp. 10-20. Omnipress, 2010.
iPin You. ipinyou global rtb bidding algorithm competition, 2013. URL.htttss://ww..K
com/ last summer httpummerriiiyouuuu ipinnyu
Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. Proceed- ings of the 3rd International Conference Learning Representations, ICLR '15, San Diego, CA, USA, 2015.
Nick Littlestone. From on-line batch learning. In Ronald L. Rivest, David Haussler, and Man- fred K. Warmuth (eds.), Proceedings of the Second Annual Workshop on Computational Learning Theory, COLT 1989, Santa Cruz, CA, USA, July August 2, 1989, pp. 269-284. Morgan Kauf- mann, 1989. URL ptstp://dl. acm. org ci tat on cfm d 93365
H. Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. In COLT 2010 The 23rd Conference Learning Theory, Haifa, Israel, June 27- 29, 2010, pp. 244-256. Omnipress, 2010. UtL.ttpp:// //ol//coooo t2010. hai.a..fa.....m / eapprs//O1122110pxoeeetttt
i.mm com/
H. Brendan McMahan, Gary Holt, D. Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, Sharat Chikkerur, Dan Liu, Martin Watten- berg, Arnar Mar Hrafnkelsson, Tom Boulos, and Jeremy Kubica. Ad click prediction: a view from the trenches. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD 113 pp. 1222-1230. Chicago, Illinois, USA, 2013. ACM.
Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, Jianyu Huang, Narayanan Sun- daraman, Jongsoo Park, Xiaodong Wang, Udit Gupta, Carole-Jean Wu, Alisson G. Azzolini. Dmytro Dzhulgakov, Andrey Mallevich, Ilia Cherniavskii, Yinghai Lu, Raghuraman Krish- namoorthi, Ansha Yu, Volodymyr Kondratenko, Stephanie Pereira, Xianjie Chen, Wenlin Chen, Vijay Rao, Bill Jia, Liang Xiong, and Misha Smelyanskiy. Deep learning recommendation model for personalization and recommendation systems. CoRR, abs/1906.00 00091, 2019. URL
wwwgg/b.//////oo/////.o/o/..aaee http: //tp:i////vv.///a//aa org/ abs 0111119660000900
Yurii E. Nesterov. Smooth minimization non-smooth functions. Math. Program., 103:127-152, 2005.
Yurii E. Nesterov. Primal-dual subgradient methods for convex problems, Math. Program., 120 (1:22112553 2009. doi: 10.10077/100007-077--14444 URL htttp:://cc..org///atta s 610107-007-0149-
Xiuyan Ni, Yang Yu, Peng Wu, Youlin Li, Shaoliang Nie, Qichao Que, and Chao Chen. Feature selection for facebook feed ranking system via pparsity-regulart training algorithm. In Proceedings of the 28th ACM International Conference on Information and Knowledge Manage- ment, CIKM '19, pp. 2085-2088. Beijing, China, 2019. ACM.
10

---

Under review as a conference paper at ICLR 2021
Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Compu- tational Mathematics and Mathematical Physics, 4(5):1-17, 1964. doi: 10.101600041-5559664) 90137-5.
Yanru Qu, Han Cai, Kan Ren, Weinan Zhang, Yong Yu, Ying Wen, and Jun Wang. Product-based neural networks for user response prediction. In Francesco Bonchi, Josep Domingo-Ferrer, Ri- cardo Baeza- Yates, Zhi-Hua Zhou, and Xindong Wu (eds.), IEEE 16th International Conference
on Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain, pp. 1114--1544 IEEE doi: 10.1009/CCDM.201.00155 URL httpt::t/////.... //op:: /oi http:///oooo///////////o or.
Computer Society, 2016.
1169/ICDM,
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In Pro- ceedings of the 6th International Conference on Learning Representations, ICLR '18, Vancouver, BC, Canada, 2018. OpenReview.net.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
R. Tyrell Rockafellar. Convex Analysis. Princeton Landmarks in Mathematics and Physics. Prince- ton University Press, 1970. ISBN 978-1-4008-731733.
Simone Scardapane, Danilo Comminicllo, Amir Hussain, and Aurelio Uncini. Group sparse regu- larization for deep neural networks. Neurocomputing. 241:43-52, 2016. doi: 10.10166f..eueeeee neucom. neucom. wtt.aiccc...00...... 2017 02.
2017.02.029. URL/nctpss///6..or///00..
Ruoxi Wang, Bin Fu, Gang Fu, and Mingliang Wang. Deep & cross network for ad click predic- tions. Proceedings of the ADKDD' 17, Halifax, NS, Canada, August 13 17, 2017, pp. 12:1- 12:7. ACM, 2017. doi: 10. 10.1145/112444933144444 URL
org 11.1.////...../////....1111 1145/
3124749. 3124754
Lin Xiao. Dual averaging method for regularized stochastic learning and online optimization. Jour- nal of Machine Learning Research, 11:2543-2596 2010. doi: 05555/1756006.153000 URL
https: //t::///ll... acm. orq
19530017
Haiqin Yang. Zenglin Xu, Irwin King, and Michael R. Lyu. Online learning for group lasso. In Proceedings of the 27th International Conference on Machine Learning, ICML '10, pp. 1191- 1198, Haifa, Israel, 2010. Omnipress.
Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, and Michael W. Mahoney, ADAHESSIAN: an adaptive second order optimizer for machine learning. CoRR, abs/2006.00719 2020. URL
200.:////200..00 00719
Matthew D. Zeiler. Adadelta: An adaptive learning rate method. CoRR, abs/ 1212..1011111111,,1111111 2012. URL ht:pss:/araa wttp://wwwww.g./////.2.22...

---

Under review as a conference paper at ICLR 2021
APPENDIX
A GROUP ADAM
Algorithm Group Adam
1: Input: parameters A21, A2, 31, 32.
æi E R step size a, initialize 2n 0, mi 0, Vo 0,
2: for = to T' do
3: = fx(+))
4: my 8ime-1 + -110g
m ms/(1 - -8))
6: Ve 8 + (1 32)diag(oE)
7:
Vi V1/(1 (5)
VV VV-i +eI
t=
8:
Q
VV VV-1
t>
9:
2: t 21-1 + Mi Qua
10:
for i E {1, [I....,f]
n do
|=,1 S A
11:
81.1
sign(=r,()A= - 21,1
otherwise.
12:
end for
1d.g A21
13:
Vit 2A21) max(1 (1-
Taulla 0)sc
14:
end for
B GROUP ADAGRAD
Algorithm 3 Group Adagrad
I: Input: parameters Åι A
æi E R step size a, initialize to 0, Vo
2: for to T' do
3:
Vf((w))
4:
0t
Vi Vi-1 + diag(g
+
t 1> 1
5:
Vi-1 + diag(gt)
6:
Q: = VV, VV-1
7:
4-1 +
8:
for E {1,
[I....,n] do
if |a.a| S A1 otherwise.
81 sign(ze,:)A1 2.,
10: end for
J4+1 (.V 2\a1l) max
1|sllla 0)s
12: end for
C PROOF THEOREM
Proof.
1
Jt+1 = arg min Mia I +
(x Iz) Te) - -x.) + v.(x)
20s
1=1
1
arg min Mia .
(I[Q)
x
2x (Q.I.) + 11Q2211 x. 22.111)) + ve(x)
(22)
2as
x=1
Qa Is
arg min
mia
x
+
1 x + Vx(x).
201
a=l
12

---

Under review as a conference paper at ICLR 2021
Define 2t-1 M1:-11
Ee=1
Qn Oa (t 2 2) and we can calculate
Qr
= - + my
Tt.
12 1.
(23)
Ott
By substituting 23) 22 is simplified to be
Q.
21+1 arg min 21
| + (((x).
(24)
2
By substituting (x) (Eq. (5) into 24
we get
Q2
F++1 = arg min 24 x
+
||
112
+
\21
dr
12 12 (1)))=112)+
20.
g=1
(25)
Q. 20,
+ X2 x
Since the objective of 25 is component-wise and element-wise, we can focus on the solution in one group, say g. and one entry, say in the g-th group. Let Σ 2a, ". The objective (5) on 1 is
@ diag(of) where of
(1(41,1) 20 + A1 + D(12+1.)):
(26)
where (1x(+1,) = A21 v dzs (o fi + 22) 2 x 21,lll + 10 + 22) is a non-negative
function and ((1(+1,)) = 0 iff x ++1, 0 for all E fl,...,,aa, d
We discuss the optimal solution of (26) in three cases:
a) If =f, then 2f+1, 0.
b) If 29, > O, then 2f41, S O. Otherwise, if #1+1,4 0, we have Q 0(- < 0(x which contradicts the minimization value (xx) on x 1:1,1
Next, if = I Å₁ then #141,- = Otherwise, if # 0, we have ((x(+1.) (2 A1)= + ((14+1)) 120),, which also contradicts the minimization value of ((xx) on x #
Third, 21. > (Vi =, I...., ................................ d==). The objective of 26 for the g-th group. (xx4+1). becomes
(2) A1 22 + (22441)
c) If =/. 0, the analysis is similar to b). We have xy 2 2 0. When -29, d1 24+1, O.
When = > \ι (V1 1,...,,,ay ,dy), we have 2(x (2f + A1 24+1 + ((x4+1).
From a), b), c) above, we have
2 arg min -s 2(zz)
(27)
x
where the i-th element of sy defined same Define
= (diag of) + 2211)
(28)
By substituting
28 into 27
we get
y2 arg min - 52 y + A21 dze |yl12 + 11y113
(29)
13

---

Under review as a conference paper at ICLR 2021
where 5 (diag(o() + + which is defined same (10). This is unconstrained non-smooth
optimization problem. Its optimality condition (see Rockafellar 1970), Section 27) states that yf+1 an optimal solution if and only if there exists 01 such that
5% X21 V dopg + 2 0.
(30)
The subdifferential of ||vl|2 is
{
if = 0, {c E Rd - 15 (0) - 1, = 1, dus}
allyl2
y
y + 0.
T
Similarly to the analysis of (e-regularization, we discuss the solution of 300 in two different cases:
a) If || S λ2 Vdz,, then v.+1 = 0 and 5 A2i 0||0||2 satisfy (30) We also show that
there is no solution other than b2 =
Without loss of generality, we assume Vi+1. F 0 for
v2+ and
all {I,..., dza }. then & 1
A21 v /dw
$7 +
11 1122 Vb-1 + 22L++1 =
(31)
From (1). we can derive
A21 Vuy
2)1l1 = ||5/112-
11 1|2
Furthermore, we have
1 ll2 =
2 (115g ll A21 drs
(32)
where 11 ll2 > O and
[55 1l2 A21 / I 0 contradict each other.
b) If | A21 daa, then from and
we get
A21
(33)
3 ll
We replace vL+a of 333 by 2 using (88 then we have
2t (diag(a?) + A21) $ #
A21 das
(2diag(o 2X21) -1
)s
3 lle
(34)
Q.
A21 dus
+ 2X -1
)8²
Os
| l2
Combine a) and b) above, we finish the proof.
D PROOF OF THEOREM 2
Proof. We use the method of induction.
a) When /. 1, then Algorithm becomes
Vo
Q 01
= VV.
01
Og
Q1
VV
= 40 + my
m,
01
01
V
-21
T
1111
M11
82 =
81 =
01
Q1
which equals to Eq. 1
14

---

Under review as a conference paper at ICLR 2021
b) Assume = T. Eq. 35 true.
VT
mT
2T mr
IT.
IT+1
IT
aT
(35)
0T
VVr
For + + 1, we have
QT+1 FT+1
27-1 2T + M+++
0T+1
VTT
QT 21+1
M2
2T + M+++1
aT
QT-1
VVT
M&
Q1+1 IT+1
1IT
(+T+1 0T
M1T1
OT
VT
0T+1
VT
QT+1
V
= MT++
+
3T+1 = M-T-1
TT+1:
QT
@T+1
0T+1
VT+1
VT+1
mT+1
2T-2
ST+1
TT+1 = 2T+1
QT
aT+1
0T+1
VV++1
Hence, complete the proof.
E
PROOF OF THEOREM 3
Proof. Let
he(z) = Ex= To 11 x2)1
11 E [7],
o c
==
is easy to verify that for all [T], (x) is 1-strongly convex with respect to || ll llve which
vV
Eim Qa and ho(r)) is 1-strongly convex with respect || 1|2.
Or
From have
R₂ = Σ (f((z)) - fx(x')) S
Σ
(gt, Ft x²)
1=1
Σ (mi -----1,, x²)
(m², Ft - x²)
(36)
Σ (me, 2z) + V+((*)) + NoT (x') +
(-m,, VT((*)) - 1r(x*))
Σ (m,, vx) + (T(")) + hr(a") + sup {(-miT, (T(x)- hr(x))
where in the first and second incquality above, we use the convexity of fe(x) and the condition 12 respectively.
define ht (u) to the conjugate dual Vz(x) + hx():: (u) sup (u, x) - V v. (x)), t t 0.
of Q
where (o(x)) = Since hx(x) 1-strongly convex with respect to the norm Il.. the function
hy has 1-Lipschitz continuous gradients with respect to || || (see, Nesterov 2005 Theorem 1):
||V (wi) - (u2))l),,, < || u2llig
(37)
and
(k = arg min f- (u, x) + (x(x) + 1x(x))
(38)
zeQ
15

---

Under review as a conference paper at ICLR 2021
As trivial corollary of (37 have the following inequality:
h (u + 6) = (T) + (Vhi + 1
(39)
Since hec1 (x) 2 (x)) and (x+1 2 (x)x) from 38
39
we have
h - 1 (-m1:r)
- h1 (-M1.T-) 1) - (W ( -m...-T------- 1), mT) +
/
1
(05-2(-m11T--0 mor)
| lnç
(40)
T
T
$ h2(0) - (Vhg(0), m1)
Σ
(oe, me)
+
m 1
2
1
T
T
1
Σ
(aa, me) +
||
2
where the last equality above follows from (0) 0 and
which deduces x1 (h)
By substituting 40)..
(36 becomes
RT S
(me, + (T(xx") + hr((=)) + (-((m)
(41)
S (T(xx') (x(xx") + mmllif 1
F ADDITIONAL PROOFS
F.1 PROOF OF LEMMA
Proof. Let V diag(oz (o)) where o, the vector of the diagonal elements of Vg. For i-th entry of o by substituting into 11).. we have
t1 Di, + 101-1. (ma,i 7,4-1,1) + -192-1,4 + 17 0,,00,2.5
(ms,i 7m 1,1)
(1 (m --m
(42)
1-1
(1 7) m + (17
Σ - m
Next, we will discuss the value of in two cases.
a) = 1. From 42 we have
1-1
o1s 2 (1 7)
(mi. mi + (1 7)
Σ
m > (1
7)²
Σ m 2 (1
w)²
Σ
m
(43)
s=1
#=1
==1
Recalling the definition of My,; in Section 1.5 from 43
we have
Σ
m Vor
m
2
MT,
Mral12
where the last inequality above follows from Appendix C Duchi al. 2011). Therefore, get
T
m
2
2a
d
m
2
/vV
Ot.
<
1
Mr
(44)
16

---

Under review as a conference paper at ICLR 2021
b) n 1. We assume 77 2 y and kVi Vi-1 where 1, then we have
Σ
t, 2
Σ SS (1 7)
Σ
m m,
Hence, we get
1 1- k (1 7) tt kz
Σ maa > (1 - k1 7) Σ
Ma.
2
2 (1 -23
Σ
4,53
2
(45)
which deduces the same conclusion 44 of a).
Combine a) and b), complete the proof.
F.2 PROOF OF COROLLARY
Proof. From the definition of me 13 Ve 15 we have
1 1-
G <
G
m =
9..1l 1
G
1 1-7
1 1- 7
- v
s=1
|0,, =
Fa.i < 1G
2
s=1
Hence, we have
VTG
(x(x') & dj + A21
+ 22) + +22dD]
(46)
2a
dD3G VT
hr(x")) 5
(47)
20
T
m. a
d
VTG
daG
VT.
(48)
2
1
(1 D)2
1=1
Combining (6))
47
48
we complete the proof.
G ADDITIONAL EMPIRICAL RESULTS
Table AUC of MI.P for different differentemmbedding dimensions and sparsity (feature rate) parentheses. The best results are bolded.
Embedding Dimension
GROUP ADAM
4
0.7462 (0.123)
8
0.7471 (0.056)
0.7486 (0.018)
32
0.7480 (0.006)
It is significantly better than embedding di-
mensions of 4, 8 but has no difference in 95% confidence level of the embedding di- mension of 32.
17

---

Under review as a conference paper at ICLR 2021
Table 8: Sparsity (feature rate) of MLP for different values of X21, d and AUC in parentheses.
A1
le-4
5e-4
1e-3
5e-3
1e-2
A21
0.987
0.927
0,866
0.470
0,214 (0.7475)
(0.7486)
(0.7482)
(0.7485)
(0.7481)
0.971
0.902
0.839
0.458
0.212
le-4
(0.7477)
(0.7486)
(0.7484)
(0.7480)
(0.7483)
0.867
0.829
0.682
0.344
0.169
5e-4
(0.7490)
(0.7485)
(0.7483)
(0.7485)
(0.7480)
0.702
0.684
0.612
0,274
0,134
1e-3
(0.7477)
(0.7477)
(0.7480)
(0.7479)
(0.7478)
0.136
0.138
0.120
0.106
0.035
5e-3
(0.7485)
(0.7484)
(0.7482)
(0.7482)
(0.7483)
0.033
0.037
0.033
0.029
0.018
le-2
(0.7481)
(0.7480)
(0.7481)
(0.7485)
(0.7486)
18


Reviews:
[{"review_id": "WkUFIa7_zr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The contribution is to introduce regularizers to adaptive optimizer for neural network optimization. Convergence guarantee is provided for the convex case. The authors claim that the proposed method achieves competitive performance but with more sparse solutions. \n\nPros:\n1. The introduced regularizer is general. It extends several existed adaptive optimizers. The extension is simple and the pursuit of sparse solution is reasonable and useful.\n2. The authors provide the convergence guarantee.\n\nCons:\n1. This work focuses the study on the solver for neural network optimization. However, the convergence guarantee is only for convex case. In the convex case, the authors fail to show that it is better than existed solvers, e.g., the convergence bound is tighter (showing the optimal convergence rate is not enough). Without the convergence guarantee for the nonconvex case, the results are weak.\n2. The main contribution is the regularizers which can be added in existed adaptive optimizer. Though the motivation is to find more sparse solutions, the formulation in (5) is a bit complicated without detailed explanation, e.g., the weights for the groups are so complicated. The regularizers are not practical since there have many parameters, e.g., $\\lambda_1$, $\\lambda_2$, $\\lambda_{21}$, the size of groups, the way of the group partition. The authors do not provide any suggestions on their choices. It is difficult to tune so many parameters in practice. \n3. The experimental results are not very convincing. \n(1) In the experiments, the authors evaluate the performance of optimizers mainly based on the learning performance and sparsity. However, the learning performance may depend on many different factors.  Showing the convergence of the objective function values (or other related functions) in each iterations is much more important.\n(2) The comparison in experiments may not be fair.  In the first experiment in section 4.2, the authors compare the proposed method with the traditional method by adding the regularization term to the loss. In this setting, both the model and the solver \nare different. It is hard to say that the proposed regularizer makes the results better. The roles of the regularization terms and the values of $\\ell_{21}$ are quite different in two compared models. It may not be fair to compare them based on the same value of $\\ell_{21}$. The above issues also appear in other experiments.\n(3) From the results in Table 8, the authors claim that $\\ell_{21}$-regularization is much more effective than `$\\ell_1$-regularization in producing sparsity. This is not convincing since the best value of $\\ell_{21}$ and $\\ell_1$ may be quite different. \n\nOther questions:\n1. How to choose the parameters $\\lambda_1$, $\\lambda_2$ and $\\lambda_{21}$ in experiments (though the authors show them in Table 3 for the experiments)? How to do the group partition? \n2. Section 2.1, the authors slightly modify (8) by setting $\\hat{s}_t=s_t$. Will this modification affect the algorithm and its convergence analysis? If the convergence analysis is for the modified version, it is not necessary to introduce (8) for avoiding confusion. \n3. The parameters $\\ell_1$, $\\ell_2$ and $\\ell_{21}$ in the experiments should be  $\\lambda_1$, $\\lambda_2$ and $\\lambda_{21}$ in (5).\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "IgExjU-Knjk", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper proposes a novel framework to add sparsity regularizers to adaptive optimizers in deep learning such as Adam, Adagrad... A generic algorithm is proposed and the theoretical convergence and regret guarantees are provided. Empirical evaluations on ad click logs datasets are provided to show the effectiveness of the framework\n\n \n\nPros: \n\n- The idea of using sparse regularization (sparse group lasso) in the general update formulation of adaptive optimizers is interesting. It provides a unified way to derive practical optimization algorithm of deep networks parameters under sparsity constraints. Re-assuringly the proposed algorithm reduces to the conventional adaptive optimizers when the regularization parameters are set to zeros.\n- The proposed formulation and algorithm is theoretically analyzed. Convergence guarantees, in terms of bound on the regret, are established using results from stochastic convex optimization and based on primal-dual analysis. The guarantees ensure a convergence rate of $\\sqrt{1/T}$. These results are interesting per se although they are not exploited in practice to control the algorithm convergence.\n- Evaluation of the new optimizers (including the sparse group lasso regularizer) to train deep networks on three real-world ad click datasets highlight the fact that the new optimizers achieve highly sparse layer weights with competitive or better accuracy performances compared to the classical un-regularized version of the optimizers (plain Adam, Adagrad…). The considered datasets are characterized by categorical features which are pre-processed using one-hot encoding and leads to sparse high-dimension inputs for the deep networks. The reported results shows the practical effectiveness of the method for ad click prediction.\n\nConcerns: \n- A concern about the paper is the lack of justification of the proposed regularization scheme. The rationale behind the regularization term, Equation (5), is insufficiently discussed and explained. For instance,  it is unclear why the “second order” matrix $Q_s^g/\\alpha_s + \\lambda_2 \\mathbf{I}$ is used in the group lasso term. Also, it is unclear why the same regularization parameter $\\lambda_2$ is used for the group lasso penalty and the $\\ell_2$-norm penalty. \n- The new optimizers GROUP ADAGRAD, GROUP ADAM… involve three additional hyper-parameters $\\lambda_1$, $\\lambda_2$, $\\lambda_{12}$  which tuning may be tedious compared with their un-regularized counterparts. \n-The introduction of the term $(\\sum_s Q_s^g/\\alpha_s + \\lambda_2 \\mathbf{I})^{1/2}$ in the group lasso regularization is justified by the fact that a close form solution (Equation 8) is attainable in such setting. However in Algorithm 1 this exact closed form is not used as $\\tilde{s}$ is replaced by $s_t$ in Equation (8). Here again this choice is not well justified. What does it entail to use $\\tilde{s}$?\n- The empirical evaluations are restricted to ad click datasets with highly sparse input vectors. Does it mean that the proposed group optimizers are only suited in that setting? If so, which other application domains may benefit from the group sparse optimizers?  Nevertheless, a deeper analysis of the proposed method on other application domains such computer vision (Adam optimizer is customary used in the latter domain) would be nice.\n- For the reproducibility sake, the paper should mention how the parameter groups are selected beforehand. A claim of the paper is the enhanced sparsity achieved by the new optimizers GROUP ADAGRAD, GROUP ADAM compared to Adam, Adagrad even when the latter are used to optimize the fitting term with a group lasso regularization. The paper should make explicit how the training with Adam or Adagrad was implemented in that setting. Does the training use a proximal-based at each iteration?\n- To improve the readability of the paper, the most prominent empirical results should be moved in the main paper. All the experimental results can not be deferred to the appendix as this leads to unpleasant to read Section 4.\n\n\nOther comments\n- In Lemma 1, the setting of $\\eta$ in assumptions 1 and 2 is confusing. \n- In Equation (16) what is $d$? \n- In Lemma 2, there are some trailing dot symbols in the definition of the dual norms. They should be removed.\n\nAfter rebuttal:\n- I  have read the response of the authors. \n- Some concerns are adressed: for instance some empirical results are moved to the main paper,  the tuning of the hyper-parameters is discussed and details about the groups of variables are provided.\n- Nevertheless it is still unclear why $s_t$ instead of $\\tilde{s}$ is  used in  algorithm 1 and what might be the performances of the deep models  trained using $\\tilde{s}$.\n- The baseline model is now moved to Adam with weight pruning. One concern of the review is to detail  how Adam, Adagrad are used to optimize the fitting term with a group lasso regularization. This point was skipped in the new version, hence it's not easy to assess the effectiveness of the Group Adam, Group Adagrad methods.", "extra_scores": {}, "extra_text": {}}, {"review_id": "G8HzC9q3EY", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work studies the adaptive proximal gradient descent method, and specifically studies the group sparsity. To encourage the group sparsity, a regularizer which is a combination of $\\ell_1$ norm, block $\\ell_1$ norm and $\\ell_2$ norm square is used. This paper gives the update rule of the proximal gradient with the specific regularizer. After proposing the update rule, the paper analyzes the convergence and regret guarantee of the algorithm.\n\nHowever, I'm not sure if the contribution is enough for the conference, as it is known that the block $\\ell_1$ norm can encourage the block sparsity, and the computation of proximal gradient is fairly standard and straightforward. The convergence of proximal gradient method is not too different from gradient method as well.\n\nI think it can be more interesting if the work can focus on the statistical property of the regularizer $\\Psi$. As suggested in Oymak et al, summing up a few regularization terms might not actually benefit with getting the structure. Analyzing whether the solution of the objective is group sparse, and whether one can find the group sparse parameter with less data than solving with unregularized least squares, is more interesting and less exploited.  \n\n================================= Update ===================================\n\nI slightly raise my rating, as everything is correct and well organized. However I'm still not sure if this is enough contribution or just incremental compared to the existing computation of proximal gd. I'd leave it to other reviewers.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-RHEJzDaYTt", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors propose addition of group sparsity regularizer into the FTRL framework, and derive update rules of AdaGrad/Adam. They demonstrate the effectiveness by inducing sparsity on several models used in the benchmarks.\n\nReason to Score: Weaker experimentation, lack of standard baselines -- including them can improve the paper.\n\nI have listed my concerns below and hopefully authors can address them during the rebuttal period.\n\nQuestions/Comments:\n\n1. Could authors contrast their work with algorithm presented in: \nhttps://static.googleusercontent.com/media/research.google.com/en//pubs/archive/41159.pdf \nwhich includes an implementation in: https://www.tensorflow.org/api_docs/python/tf/keras/optimizers/Ftrl\n\nIs the contribution an extension by using group sparsity?\n\n2. Missing word in sentence in abstract (\"not only can the\")\n... the loss functions, not only can the dimensions of features be effectively and efficiently reduced ...\n\n3. Incorrect citation\n\nAny regret minimizing algorithm can be converted to a stochastic optimization algorithm with convergence rate O(RT /T) using an online-to-batch conversion technique\n\nPlease cite:\nN. Littlestone. From On-Line to Batch Learning. In Proceedings of the 2nd Workshop on Computational Learning Theory, p. 269-284, 1989.\n\n4. A major concern was on experiment sections. Authors do not mention what type of groups were used clearly, which made it hard to judge the results. \n\nI also suggest authors include several baselines comparing with existing work:\na) block l1 (l2 of the norm of the group) as penalty to the objective\nb) standard magnitude pruning. https://arxiv.org/abs/1902.09574 \n\n== Update: Nov 30 2020 == \nThanks for the authors for the reply.  Thank you for running those experiments.  \n\nI had a few more clarifications needed from authors. (a) Magnitude pruning typically invovles a fine tuning phase after removing the weights, was this carried out? For eg: Fig 1. a behavior was why I asked this question (b) I would recommend authors to add error bars Table 2. has results that are quite close between the methods.  \n\nI raised my score but still below accept due to the above reservations.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a generic way to add group sparsity based regularizers to a family of adaptive optimizers leading to generalizations of many popular optimizers ADAM, ADAGRAD etc  to their group versions. Overall the reviewers appreciated the algorithmic contribution and its genericness in terms of application to most known adaptive optimizers. While the paper's revision during the rebuttal phase satisfied some reviewer concerns regarding the experimental baselines and the precise experimental methodology, reviewers continued to have concerns regarding the experiments performed - the potential lack of fine tuning post pruning, the use of s_t tilde as opposed to s_t in the practical algorithms amongst others listed in the review. Overall, the reviewers deemed the theoretical contribution of the paper not significant enough in terms of novelty and the decision hinged on the efficacy of the experimental evaluation - the lingering concerns for which led to the decision. 

Decision: Reject