Year: 2020

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 largescale 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.

heading: 1 INTRODUCTION
text: 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 effective and efficient for saving computational resource and improving model performance especially in the scenarios of very high-dimensional data. Meanwhile, the simple rounding approach is very unreliable due to the inherent low accuracy of these optimizers.
In this paper, we develop a 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. In this section, we describe the two types of optimization methods, and explain the motivation of our work.

heading: 1.1 ADAPTIVE OPTIMIZATION METHODS
text: Due to the simplicity and effectiveness, adaptive optimization methods (Robbins & Monro, 1951; Polyak, 1964; Duchi et al., 2011; Zeiler, 2012; Kingma & Ba, 2015; Reddi et al., 2018; Yao et al., 2020) have become the de-facto algorithms used in deep learning. There are multiple variants, but they can be represented using the general update formula (Reddi et al., 2018):
xt+1 = xt − αtmt/ √ Vt, (1)
where αt is the step size, mt is the first moment term which is the weighted average of gradient gt and Vt is the so called second moment term that adjusts updated velocity of variable xt in each direction. Here, √ Vt := V 1/2 t , mt/ √ Vt := √ Vt −1 ·mt. By setting different mt, Vt and αt , we can derive different adaptive optimizers including MOMENTUM (Polyak, 1964), ADAGRAD (Duchi et al., 2011), ADAM (Kingma & Ba, 2015), AMSGRAD (Reddi et al., 2018) and ADAHESSIAN (Yao et al., 2020), etc. See Table 1.

heading: 1.2 REGULARIZED OPTIMIZATION METHODS
text: Follow-the-regularized-leader (FTRL) (McMahan & Streeter, 2010; McMahan et al., 2013) has been widely used in click-through rates (CTR) prediction problems, which adds `1-regularization (lasso) to logistic regression and can effectively balance the performance of the model and the sparsity of features. The update formula (McMahan et al., 2013) is:
xt+1 = arg min x
g1:t · x+ 1
2 t∑ s=1 σs‖x− xs‖22 + λ1‖x‖1, (2)
where g1:t = ∑ t s=1gs, 1 2 ∑t s=1 σs‖x− xs‖22 is the strong convex term that stabilizes the algorithm and λ1‖x‖1 is the regularization term that produces sparsity. However, it doesn’t work well in DNN models since one input feature can correspond to multiple weights and lasso only can make single weight zero hence can’t effectively delete zeros features.
To solve above problem, Ni et al. (2019) adds the `21-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 `21-regularization 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.

heading: 1.3 MOTIVATION
text: Eq. (1) can be rewritten into this form:
xt+1 = arg min x
mt · x+ 1 2αt ‖ √ Vt 1 2 (x− xt)‖22. (3)
Furthermore, we can rewrite Eq. (3) into
xt+1 = arg min x
m1:t · x+ t∑
s=1
1
2αs ‖Q
1 2 s (x− xs)‖22, (4)
where m1:t = ∑t s=1ms, ∑t s=1Qs/αs = √ Vt/αt. It is easy to prove that Eq. (3) and Eq. (4) are equivalent using the method of induction. The matrices Qs can be interpreted as generalized learning rates. To our best knowledge, Vt of Eq. (1) of all the adaptive optimization methods are diagonal for the computation simplicity. Therefore, we considerQs as diagonal matrices throughout this paper.
We find that Eq. (4) is similar to Eq. (2) except for the regularization term. Therefore, we add the regularization term Ψ(x) to Eq. (4), which is the sparse group lasso penalty also including `2-
regularization that can diffuse weights of neural networks. The concrete formula is:
Ψt(x) = G∑ g=1 ( λ1‖xg‖1 + λ21 √ dxg‖A 1 2 t x g‖2 ) + λ2‖x‖22, (5)
where λ1, λ21, λ2 are regularization parameters of `1, `21, `2 respectively, G is the total number of groups of weights, xg is the weights of group g and dxg is the size of group g. In DNN models, each group is defined as the set of outgoing weights from a unit which can be an input feature, or a hidden neuron, or a bias unit (see, e.g., Scardapane et al. (2016)). At can be arbitrary positive matrix satisfying At+1 At, e.g., At = I. In Section 2.1, we let At = ( ∑t s=1 Qgs 2αs
+ λ2I) just for solving the closed-form solution directly, where Qgs is a diagonal matrix whose diagonal elements are part of Qs corresponding to xg . The ultimate update formula is:
xt+1 = arg min x
m1:t · x+ t∑
s=1
1
2αs ‖Q
1 2 s (x− xs)‖22 + Ψt(x). (6)

heading: 1.4 OUTLINE OF CONTENTS
text: The rest of the paper is organized as follows. In Section 1.5, we introduce the necessary notations and technical background.
In Section 2, we present the closed-form solution of Eq. (4) 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, we give two concrete examples of the algorithm.1
In Section 3, we derive the regret bounds of the method and convergence rates.
In Section 4, we validate the performance of new optimizers in the public datasets.
In Section 5, we summarize the conclusion.
Appendices A-B list the details of GROUP ADAM and Group Adagrad respectively. Appendices C-F contain technical proofs of our main results and Appendix G includes the details of the empirical results of Section 4.4.

heading: 1.5 NOTATIONS AND TECHNICAL BACKGROUND
text: We use lowercase letters to denote scalars and vectors, and uppercase letters to denote matrices. We denote a sequence of vectors by subscripts, that is, x1, . . . , xt, and entries of each vector by an additional subscript, e.g., xt,i. We use the notation g1:t as a shorthand for ∑t s=1 gs. Similarly we
write m1:t for a sum of the first moment mt, and f1:t to denote the function f1:t(x) = ∑t s=1 fs(x). Let Mt = [m1 · · ·mt] denote the matrix obtained by concatenating the vector sequence {mt}t≥1 andMt,i denote the i-th row of this matrix which amounts to the concatenation of the i-th component of each vector. The notation A 0 (resp. A 0) for a matrix A means that A is symmetric and positive semidefinite (resp. definite). Similarly, the notations A B and A B mean that A−B 0 andA−B 0 respectively, and both tacitly assume thatA andB are symmetric. Given A 0, we write A 12 for the square root of A, the unique X 0 such that XX = A (McMahan & Streeter (2010), Section 1.4).
Let E be a finite-dimension real vector space, endowed with the Mahalanobis norm ‖ · ‖A which is denoted by ‖·‖A = √ 〈·, A·〉 as induced byA 0. Let E∗ be the vector space of all linear functions
on E . The dual space E∗ is endowed with the dual norm ‖ · ‖∗A = √ 〈·, A−1·〉.
Let Q be a closed convex set in E . A continuous function h(x) is called strongly convex on Q with norm ‖ · ‖H ifQ ⊆ dom h and there exists a constant σ > 0 such that for all x, y ∈ Q and α ∈ [0, 1] we have
h(αx+ (1− α)y) ≤ αh(x) + (1− α)h(y)− 1 2 σα(1− α)‖x− y‖2H .
1To fulfill research interest of optimization methods, we will release the code in the future.
The constant σ is called the convexity parameter of h(x), or the modulus of strong convexity. We also denote by ‖ · ‖h = ‖ · ‖H . Further, if h is differential, we have
h(y) ≥ h(x) + 〈∇h(x), y − x〉+ σ 2 ‖x− y‖2h.
We use online convex optimization as our analysis framework. On each round t = 1, . . . , T , a convex loss function ft : Q 7→ R is chosen, and we pick a point xt ∈ Q hence get loss ft(xt). Our goal is minimizing the regret which is defined as the quantity
RT = T∑ t=1 ft(xt)−min x∈Q T∑ t=1 ft(x). (7)
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 convergence rate O(RT /T ) using an online-to-batch conversion technique (Littlestone, 1989). In this paper, we assume Q ≡ E = Rn, hence we have E∗ = Rn. We write sTx or s · x for the standard inner product between s, x ∈ Rn. For the standard Euclidean norm, ‖x‖ = ‖x‖2 =√ 〈x, x〉 and ‖s‖∗ = ‖s‖2. We also use ‖x‖1 = ∑n i=1 |x(i)| and ‖x‖∞ = max i|x(i)| to denote `1-norm and `∞-norm respectively, where x(i) is the i-th element of x.

heading: 2 ALGORITHM

heading: 2.1 CLOSED-FORM SOLUTION
text: We will derive the closed-form solution of Eq. (6) with specific At and Algorithm 1 with slight modification in this section. We have the following theorem.
Theorem 1. Given At = ( ∑t s=1 Qgs 2αs
+ λ2I) of Eq. (5), zt = zt−1 + mt − Qtαt xt at each iteration t = 1, . . . , T and z0 = 0, the optimal solution of Eq. (6) is updated accordingly as follows:
xt+1 = ( t∑ s=1 Qs αs + 2λ2I)−1 max(1− √ dxgt λ21 ‖s̃t‖2 , 0)st (8)
where the i-th element of st is defined as
st,i = { 0 if |zt,i| ≤ λ1, sign(zt,i)λ1 − zt,i otherwise, (9)
s̃t is defined as
s̃t = ( t∑ s=1 Qs 2αs + λ2I)−1st (10)
and ∑t s=1 Qs αs is the diagonal and positive definite matrix.
The proof of Theorem 1 is given in Appendix C. We slightly modify (8) where we let s̃t = st. Our purpose is to let every entry of the group have the same effect of `21-regularization. Hence, we get Algorithm 1. Furthermore, we have the following theorem which shows the relationship between Algorithm 1 and adaptive optimization methods. The proof is given in Appendix D. Theorem 2. If regularization terms of Algorithm 1 vanish, Algorithm 1 is equivalent to Eq. (1).

heading: 2.2 CONCRETE EXAMPLES
text: Using Algorithm 1, we can easily derive the new optimizers based on ADAM (Kingma & Ba, 2015), ADAGRAD (Duchi 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 λ1, λ2, λ21 are all zeros, Algorithm 2 is equivalent to ADAM (Kingma & Ba, 2015).
Algorithm 1 Generic framework of adaptive optimization methods with sparse group lasso 1: Input: parameters λ1, λ21, λ2 x1 ∈ Rn, step size {αt > 0}Tt=1, sequence of functions {φt, ψt}Tt=1, initialize z0 = 0, V0 = 0, α0 = 0
2: for t = 1 to T do 3: gt = ∇ft(xt) 4: mt = φt(g1, . . . , gt) and Vt = ψt(g1, . . . , gt)
5: Qt αt = √ Vt αt − √ Vt−1 αt−1 6: zt ← zt−1 +mt − Qtαt xt 7: for i ∈ {1, . . . , n} do
8: st,i = {
0 if |zt,i| ≤ λ1 sign(zt,i)λ1 − zt,i otherwise.
9: end for
10: xt+1 = ( √ Vt αt + 2λ2I)−1 max(1− √ d x g t λ21 ‖st‖2 , 0)st 11: end for
GROUP ADAGRAD
The detail of the algorithm is given in Appendix B. Similarly, from Theorem 2, when λ1, λ2, λ21 are all zeros, Algorithm 3 is equivalent to ADAGRAD (Duchi et al., 2011). Furthermore, we can find that when λ21 = 0, Algorithm 3 is equivalent to FTRL (McMahan et 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., 2018), ADAHESSIAN (Yao et al., 2020), etc., with the same framework and we will not list the details.

heading: 3 CONVERGENCE AND REGRET ANALYSIS
text: Using the framework developed in Nesterov (2009); Xiao (2010); Duchi et al. (2011), we have the following theorem providing the bound of the regret. Theorem 3. Let the sequence {xt} be defined by the update (6) and
x1 = arg min x∈Q
1 2 ‖x− c‖22, (11)
where c is an arbitrary constant vector. Suppose ft(x) is convex for any t ≥ 1 and there exists an optimal solution x∗ of ∑T t=1 ft(x), i.e., x ∗ = arg minx∈Q ∑T t=1 ft(x), which satisfies the condition
〈mt−1, xt − x∗〉 ≥ 0, t ∈ [T ], (12) where mt is the weighted average of the gradient ft(xt) and [T ] = {1, . . . , T} for simplicity. Without loss of generality, we assume
mt = γmt−1 + gt, (13)
where γ < 1 and m0 = 0. Then
RT ≤ ΨT (x∗) + T∑ t=1 1 2αt ‖Q 1 2 t (x ∗ − xt)‖22 + 1 2 T∑ t=1 ‖mt‖2h∗t−1 , (14)
where ‖·‖h∗t is the dual norm of ‖·‖ht . ht is 1-strongly convex with respect to ‖·‖√Vt/αt for t ∈ [T ] and h0 is 1-strongly convex with respect to ‖ · ‖2.
The proof of Theorem 3 is given in Appendix E. Since in most of adaptive optimizers, Vt is the weighted average of diag(g2t ), without loss of generality, we assume αt = α and
Vt = ηVt−1 + diag(g2t ), t ≥ 1, (15) where V0 = 0 and η ≤ 1. Hence, we have the following lemma whose proof is given in Appendix F.1.
Lemma 1. Suppose Vt is the weighted average of the square of the gradient which is defined by (15), αt = α, mt is defined by (13) and Vt satisfies the following arbitrary conditions:
1. η = 1,
2. η < 1, η ≥ γ and κVt Vt−1 for all t ≥ 1 where κ < 1.
Then we have T∑ t=1 ‖mt‖2 ( √ Vt αt )−1 < 2α 1− ν d∑ i=1 ‖MT,i‖2, (16)
where ν = max(γ, κ) and d is the dimension of xt.
We can always add δ2I to Vt at each step to ensure Vt 0. Therefore, ht(x) is 1-strongly convex with respect to ‖ · ‖√δ2I+Vt/αt . Let δ ≥ maxt∈[T ] ‖gt‖∞, for t > 1, we have
‖mt‖2h∗t−1 = 〈 mt, αt(δ 2I + Vt−1)− 1 2mt 〉 ≤ 〈 mt, αt ( diag(g2t ) + ηVt−1 )− 12 mt〉 = 〈 mt, αtV − 12 t mt 〉 = ‖mt‖2
( √ Vt αt )−1 .
(17)
For t = 1, we have ‖m1‖2h∗0 = 〈 m1, α1(δ 2I + I)− 1 2m1 〉 ≤ 〈 m1, α1 ( diag− 1 2 (g21) ) m1 〉 = 〈 m1, α1V − 12 1 m1 〉 = ‖m1‖2
( √ V1 α1 )−1 .
(18)
From (17), (18) and Lemma 1, we have
Lemma 2. Suppose Vt, mt, αt, ν, d are defined the same as Lemma 1, maxt∈[T ] ‖gt‖∞ ≤ δ, ‖ · ‖2h∗t = 〈 ·, αt(δ2I + Vt)− 1 2 · 〉 for t ≥ 1 and ‖ · ‖2h∗0 = 〈 ·, α1 ( (δ2 + 1)I )− 12 ·〉. Then T∑ t=1 ‖mt‖2h∗t−1 < 2α 1− ν d∑ i=1 ‖MT,i‖2. (19)
Therefore, from Theorem 3 and Lemma 2, we have
Corollary 1. Suppose Vt, mt, αt, h∗t , ν, d are defined the same as Lemma 2, there exist constants G, D1, D2 such that maxt∈[T ] ‖gt‖∞ ≤ G ≤ δ, ‖x∗‖∞ ≤ D1 and maxt∈[T ] ‖xt − x∗‖∞ ≤ D2. Then
RT < dD1 ( λ1 + λ21( √ TG
2α + λ2)
1 2 + λ2D1 ) + dG ( D22 2α + α (1− ν)2 )√ T . (20)
The proof of Corollary 1 is given in F.2. Furthermore, from Corollary 1, we have
Corollary 2. Suppose mt is defined as (13), αt = α and satisfies the condition (19). There exist constantsG,D1,D2 such that tG2I Vt, maxt∈[T ] ‖gt‖∞ ≤ G, ‖x∗‖∞ ≤ D1 and maxt∈[T ] ‖xt− x∗‖∞ ≤ D2. Then
RT < dD1 ( λ1 + λ21( √ TG
2α + λ2)
1 2 + λ2D1 ) + dG ( D22 2α + α (1− ν)2 )√ T . (21)
Therefore, we know that the regret of the update (6) is O( √ T ) and can achieve the optimal convergence rate O(1/ √ T ) under the conditions of Corollary 1 or Corollary 2.

heading: 4 EXPERIMENTS

heading: 4.1 EXPERIMENT SETUP
text: 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 iPinYou dataset2 (iPinYou, 2013) is another real-world dataset for ad click logs over 21 days. The dataset contains 16 categorical features3. 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 et al., 2016), and follow the standard settings of Qu et al. (2016), i.e., 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 7 days. There are 13 integer features and 26 categorical features. After onehot 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 no timestamp. We use Deep & Cross Network (DCN) (Wang et al., 2017) and choose the following settings4: one embedding layer with embedding dimension 8, two deep layers of size 64 each, and two cross layers.
For the convenience of discussion, we use MLP, 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 is considered as a group, and a visual comparison between `1, `21 and mixed regularization effect is given in Fig. 2 of Scardapane et al. (2016).
We treat the training set as the streaming data, hence we train 1 epoch with a 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 in CTR estimation (Graepel et al., 2010). We explore 5 learning rates from 1e-5 to 1e-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 t-test. Without loss of generality, we choose two new optimizers to validate the performance, which are GROUP ADAM and GROUP ADAGRAD.

heading: 4.2 ADAM VS. GROUP ADAM
text: First, we compare the performance of the two optimizers on the same sparsity level. We keep λ1, λ2 be zeros and choose different values of λ21 of Algorithm 2, i.e., GROUP ADAM, and achieve the
2We only use the data from season 2 and 3 because of the same data schema. 3See https://github.com/Atomu2014/Ads-RecSys-Datasets/ for details. 4Limited by training resources available, we don’t use the optimal hyperparameter settings of Wang et al.
(2017).
same sparsity with ADAM that uses the magnitude pruning method, i.e., sort 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 2 reports the average results of the two 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, as shown in Figure 1, the same `21-regularization strength λ21 has different effects of sparsity and accuracy on different datasets. The best choice of λ21 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 λ21.
1
1
1
Next, we compare the performance of ADAM without post-processing procedure, i.e., no magnitude pruning, and GROUP ADAM with appropriate regularization terms which we choose in Table 3 on the AUC metric. In general, good default settings of λ2 is 1e-5. The results are shown in Table 4. Note that compared with ADAM, GROUP ADAM with appropriate regularization terms can achieve significantly better or highly competitive performance with producing extremely high sparsity.

heading: 4.3 ADAGRAD VS. GROUP ADAGRAD
text: We compare with the performance of ADAGRAD without magnitude pruning and GROUP ADAGRAD with appropriate regularization terms which we choose in Table 5 on the AUC metric. The results are 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.
Table 4: AUC for three datasets and sparsity (feature rate) in parentheses. The best value for each dataset is bolded. The pvalue of t-test is also listed.
Dataset ADAM GROUP ADAM P-Value
MLP 0.7458 (1.000) 0.7486 (0.018) 1.10e-3 (2.69e-11)
OPNN 0.7588 (0.827) 0.7617 (0.130) 0.289 (6.20e-11)
DCN 0.8021 (1.000) 0.8019 (0.030) 0.422 (1.44e-11)
Table 6: AUC for three datasets and sparsity (feature rate) in parentheses. The best value for each dataset is bolded. The pvalue of t-test is also listed.
Dataset ADAGRAD GROUP ADAGRAD P-Value
MLP 0.7453 (1.000) 0.7469 (0.063) 0.106 (1.51e-9)
OPNN 0.7556 (0.827) 0.7595 (0.016) 0.026 (< 2.2e-16)
DCN 0.7975 (1.000) 0.7978 (0.040) 0.198 (3.94e-11)

heading: 4.4 DISCUSSION
text: In this section we will discuss the hyperparameters of emdedding dimension, `1-regularization and `21-regularization to show how these hyperparameters affect the effects of regularization.
Embedding Dimension Table 7 of Appendix G reports the average results of different embedding dimensions of MLP, whose optimizer is GROUP ADAM and regularization terms are same to MLP of Table 5. Note that the sparsity increases with the growth of the embedding dimension. The reason is that the square root of the embedding dimension is the multiplier of `21-regularization.
`1 vs. `21 From lines 8 and 10 of Algorithm 1, we know that if zt has the same elements, the values of `1 and `21, i.e., λ1 and λ21, have the same regularization effects. However, this situation almost cannot be happen in reality. Without loss of generality, we set optimizer, λ2 and embedding dimension be GROUP ADAM, 1e-5 and 16 respectively, and choose different values of λ1, λ21. The results on MLP are shown in Table 8 of Appendix G. It is obvious that `21-regularization is much more effective than `1-regularization in producing sparsity. For example, when λ1 = 0 and λ21 = 5e-3, the feature sparsity is 0.136, while for λ1 = 5e-3 and λ21 = 0, the feature sparsity is 0.470. Therefore, if just want to produce sparsity, we can only tune λ21 and use default settings for λ2 and λ1, i.e., λ2 = 1e-5 and λ1 = 0.

heading: 5 CONCLUSION
text: In this paper, we propose a novel framework that adds the regularization terms to a family of adaptive optimizers for producing sparsity of DNN models. We apply this framework to create a 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 equivalent 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 optimizers 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, it would be interesting in the future to investigate the convergence in non-convex settings and evaluate our optimizers on more applications from fields such as compute vision, natural language processing and etc.

heading: A GROUP ADAM
text: Algorithm 2 Group Adam 1: Input: parameters λ1, λ21, λ2, β1, β2, x1 ∈ Rn, step size α, initialize z0 = 0, m̂0 = 0, V̂0 = 0, V0 = 0
2: for t = 1 to T do 3: gt = ∇ft(xt) 4: m̂t ← β1m̂t−1 + (1− β1)gt 5: mt = m̂t/(1− βt1) 6: V̂t ← β2V̂t−1 + (1− β2)diag(g2t ) 7: Vt = V̂t/(1− βt2)
8: Qt = { √ Vt − √ Vt−1 + I t = 1√
Vt − √ Vt−1 t > 1
9: zt ← zt−1 +mt − 1αQtxt 10: for i ∈ {1, . . . , n} do
11: st,i = {
0 if |zt,i| ≤ λ1 sign(zt,i)λ1 − zt,i otherwise.
12: end for 13: xt+1 = ( √ Vt+ I α + 2λ2I)−1 max(1− √ d x g t λ21 ‖st‖2 , 0)st 14: end for

heading: B GROUP ADAGRAD
text: Algorithm 3 Group Adagrad 1: Input: parameters λ1, λ21, λ2, x1 ∈ Rn, step size α, initialize z0 = 0, V0 = 0
2: for t = 1 to T do 3: gt = ∇ft(xt) 4: mt = gt
5: Vt = { Vt−1 + diag(g2t ) + I t = 1 Vt−1 + diag(g2t ) t > 1 6: Qt = √ Vt − √ Vt−1 7: zt ← zt−1 +mt − 1αQtxt 8: for i ∈ {1, . . . , n} do
9: st,i = {
0 if |zt,i| ≤ λ1 sign(zt,i)λ1 − zt,i otherwise.
10: end for 11: xt+1 = ( √ Vt α + 2λ2I)−1 max(1− √ d x g t λ21 ‖st‖2 , 0)st 12: end for

heading: C PROOF OF THEOREM 1
text: Proof.
xt+1 = arg min x
m1:t · x+ t∑
s=1
1
2αs (x− xs)TQs(x− xs) + Ψt(x)
= arg min x
m1:t · x+ t∑
s=1
1
2αs (‖Q
1 2 s x‖22 − 2x · (Qsxs) + ‖Q 1 2 s xs‖22) + Ψt(x)
= arg min x
( m1:t −
t∑ s=1 Qs αs xs
) · x+
t∑ s=1 1 2αs ‖Q 1 2 s x‖22 + Ψt(x).
(22)
Define zt−1 = m1:t−1 − ∑t−1 s=1 Qs αs xs (t ≥ 2) and we can calculate zt as
zt = zt−1 +mt − Qt αt xt, t ≥ 1. (23)
By substituting (23), (22) is simplified to be
xt+1 = arg min x
zt · x+ t∑
s=1
Qs 2αs ‖x‖22 + Ψt(x). (24)
By substituting Ψt(x) (Eq. (5)) into (24), we get
xt+1 = arg min x zt · x+ G∑ g=1 ( λ1‖xg‖1 + λ21 √ dxg‖( t∑ s=1 Qgs 2αs + λ2I) 1 2xg‖2 ) +
‖( t∑
s=1
Qs 2αs + λ2I) 1 2x‖22.
(25)
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 i, in the g-th group. Let ∑t s=1 Qgs 2αs = diag(σgt ) where σ g t = (σgt,1, . . . , σ g t,dxg ). The objective of (25) on xgt+1,i is
Ω(xgt+1,i) = z g t,ix g t+1,i + λ1|x g t+1,i|+ Φ(x g t+1,i), (26)
where Φ(xgt+1,i) = λ21 √ dxg‖(σgt,i + λ2) 1 2xgt+1,i‖2 + ‖(σ g t,i + λ2) 1 2xgt+1,i‖22 is a non-negative function and Φ(xgt+1,i) = 0 iff x g t+1,i = 0 for all i ∈ {1, . . . , dxg}.
We discuss the optimal solution of (26) in three cases:
a) If zgt,i = 0, then x g t+1,i = 0.
b) If zgt,i > 0, then x g t+1,i ≤ 0. Otherwise, if x g t+1,i > 0, we have Ω(−x g t+1,i) < Ω(x g t+1,i), which
contradicts the minimization value of Ω(x) on xgt+1,i.
Next, if zgt,i ≤ λ1, then x g t+1,i = 0. Otherwise, if x g t+1,i < 0, we have Ω(x g t+1,i) = (z g t,i − λ1)x g t+1,i + Φ(x g,i t+1) > Ω(0), which also contradicts the minimization value of Ω(x) on x g t+1,i.
Third, zgt,i > λ1 (∀ i = 1, . . . , dxg ). The objective of (26) for the g-th group, Ω(x g t+1), becomes
(zgt − λ11dxg ) · x g t+1 + Φ(x g t+1).
c) If zgt,i < 0, the analysis is similar to b). We have x g t+1,i ≥ 0. When −z g t,i ≤ λ1, x g t+1,i = 0.
When −zgt,i > λ1 (∀ i = 1, . . . , dxg ), we have
Ω(xgt+1) = (z g t + λ11dxg ) · x g t+1 + Φ(x g t+1).
From a), b), c) above, we have
xgt+1 = arg min x −sgt · x+ Φ(x), (27)
where the i-th element of sgt is defined same as (9).
Define y = (diag(σgt ) + λ2I) 1 2x. (28)
By substituting (28) into (27), we get
ygt+1 = arg min y
−s̃gt · y + λ21 √ dxg‖y‖2 + ‖y‖22, (29)
where s̃gt = (diag(σ g t )+λ2I)−1s g t which is defined same as (10). This is unconstrained non-smooth optimization problem. Its optimality condition (see Rockafellar (1970), Section 27) states that ygt+1 is an optimal solution if and only if there exists ξ ∈ ∂‖ygt+1‖2 such that
−s̃gt + λ21 √ dxgξ + 2y g t+1 = 0. (30)
The subdifferential of ‖y‖2 is ∂‖y‖2 = { {ζ ∈ Rdxg | − 1 ≤ ζ(i) ≤ 1, i = 1, . . . , dxg} if y = 0, y ‖y‖2 if y 6= 0.
Similarly to the analysis of `1-regularization, we discuss the solution of (30) in two different cases:
a) If ‖s̃gt ‖2 ≤ λ21 √ dxg , then y g t+1 = 0 and ξ = s̃gt λ21 √ dxg ∈ ∂‖0‖2 satisfy (30). We also show that
there is no solution other than ygt+1 = 0. Without loss of generality, we assume y g t+1,i 6= 0 for all i ∈ {1, . . . , dxg}, then ξ = ygt+1 ‖ygt+1‖2 , and
−s̃gt + λ21 √ dxg
‖ygt+1‖2 ygt+1 + 2y g t+1 = 0. (31)
From (31), we can derive
( λ21 √ dxg
‖ygt+1‖2 + 2)‖ygt+1‖2 = ‖s̃ g t ‖2.
Furthermore, we have
‖ygt+1‖2 = 1
2 (‖s̃gt ‖2 − λ21
√ dxg ), (32)
where ‖ygt+1‖2 > 0 and ‖s̃ g t ‖2 − λ21 √ dxg ≤ 0 contradict each other.
b) If ‖s̃gt ‖2 > λ21 √ dxg , then from (31) and (32), we get
ygt+1 = 1 2 (1− λ21
√ dxg
‖s̃gt ‖2 )s̃gt . (33)
We replace ygt+1 of (33) by x g t+1 using (28), then we have
xgt+1 = (diag(σ g t ) + λ2I)− 1 2 ygt+1
= (2diag(σgt ) + 2λ2I)−1(1− λ21 √ dxg
‖s̃gt ‖2 )sgt
= ( t∑ s=1 Qs αs + 2λ2I)−1(1− λ21 √ dxg ‖s̃gt ‖2 )sgt .
(34)
Combine a) and b) above, we finish the proof.

heading: D PROOF OF THEOREM 2
text: Proof. We use the method of induction.
a) When t = 1, then Algorithm 1 becomes
Q1 = α1( √ V1 α1 − √ V0 α0
) = √ V1,
z1 = z0 +m1 − Q1 α1 x1 = m1 − √ V1 α1 x1, s1 = −z1 = √ V1 α1 x1 −m1,
x2 = ( √ V1 α1 )−1s1 = x1 − α1 m1√ V1 ,
which equals to Eq. (1).
b) Assume t = T , Eq. (35) are true.
zT = mT − √ VT αT xT , xT+1 = xT − αT mT√ VT . (35)
For t = T + 1, we have
zT+1 = zT +mT+1 − QT+1 αT+1 xT+1
= mT − √ VT αT xT +mT+1 − QT+1 αT+1 xT+1 = mT − √ VT αT (xT+1 + αT mT√ VT ) +mT+1 − QT+1 αT+1 xT+1 = mT+1 − ( √ VT αT + QT+1 αT+1 )xT+1 = mT+1 − √ VT+1 αT+1 xT+1,
xT+2 = (
√ VT+1
αT+1 )−1sT+1 = −(
√ VT+1
αT+1 )−1zT+1 = xT+1 − αT mT+1√ VT+1 .
Hence, we complete the proof.

heading: E PROOF OF THEOREM 3
text: Proof. Let
ht(x) =
{ ∑t s=1 1 2αs ‖Q 1 2 s (x− xs)‖22 ∀ t ∈ [T ],
1 2‖x− c‖ 2 2 t = 0.
It is easy to verify that for all t ∈ [T ], ht(x) is 1-strongly convex with respect to ‖ · ‖√Vt/αt which√ Vt αt = ∑t s=1 Qs αs , and h0(x) is 1-strongly convex with respect to ‖ · ‖2.
From (7), we have
RT = T∑ t=1 (ft(xt)− ft(x∗)) ≤ T∑ t=1 〈gt, xt − x∗〉
= T∑ t=1 〈mt − γmt−1, xt − x∗〉 ≤ T∑ t=1 〈mt, xt − x∗〉
= T∑ t=1 〈mt, xt〉+ ΨT (x∗) + hT (x∗) + ( T∑ t=1 〈−mt, x∗〉 −ΨT (x∗)− hT (x∗))
≤ T∑ t=1 〈mt, xt〉+ ΨT (x∗) + hT (x∗) + sup x∈Q {〈−m1:T , x〉 −ΨT (x)− hT (x)} ,
(36)
where in the first and second inequality above, we use the convexity of ft(x) and the condition (12) respectively.
We define h∗t (u) to be the conjugate dual of Ψt(x) + ht(x):
h∗t (u) = sup x∈Q {〈u, x〉 −Ψt(x)− ht(x)} , t ≥ 0,
where Ψ0(x) = 0. Since ht(x) is 1-strongly convex with respect to the norm ‖ · ‖ht , the function h∗t has 1-Lipschitz continuous gradients with respect to ‖ · ‖h∗t (see, Nesterov (2005), Theorem 1): ‖∇h∗t (u1)−∇h∗t (u2)‖ht ≤ ‖u1 − u2‖h∗t , (37) and
∇h∗t (u) = arg min x∈Q {− 〈u, x〉+ Ψt(x) + ht(x)} . (38)
As a trivial corollary of (37), we have the following inequality:
h∗t (u+ δ) ≤ h∗t (u) + 〈∇h∗t (u), δ〉+ 1
2 ‖δ‖2h∗t . (39)
Since ht+1(x) ≥ ht(x) and Ψt+1(x) ≥ Ψt(x), from (38), (39), (6), we have h∗T (−m1:T ) ≤ h∗T−1(−m1:T )
≤ h∗T−1(−m1:T−1)− 〈 ∇h∗T−1(−m1:T−1),mT 〉 + 1
2 ‖mT ‖2h∗T−1
≤ h∗T−2(−m1:T−1)− 〈xT ,mT 〉+ 1
2 ‖mT ‖2h∗T−1
≤ h∗0(0)− 〈∇h∗0(0),m1〉 − T∑ t=2 〈xt,mt〉+ 1 2 T∑ t=2 ‖mt‖2h∗t−1
= − T∑ t=1 〈xt,mt〉+ 1 2 T∑ t=1 ‖mt‖2h∗t−1 .
(40)
where the last equality above follows from h∗0(0) = 0 and (11) which deduces x1 = ∇h∗0(0). By substituting (40), (36) becomes
RT ≤ T∑ t=1 〈mt, xt〉+ ΨT (x∗) + hT (x∗) + h∗T (−m1:T )
≤ ΨT (x∗) + hT (x∗) + 1
2 T∑ t=1 ‖mt‖2h∗t−1 .
(41)

heading: F ADDITIONAL PROOFS
text: F.1 PROOF OF LEMMA 1
Proof. Let Vt = diag(σt) where σt is the vector of the diagonal elements of Vt. For i-th entry of σt, by substituting (13) into (15), we have
σt,i = g 2 t,i + ησt−1,i = (mt,i − γmt−1,i)2 + ηg2t−1,i + η2σt−2,i
= t∑ s=1 ηt−s(ms,i − γms−1,i)2 ≥ t∑ s=1 ηt−s(1− γ)(m2s,i − γm2s−1,i)
= (1− γ) ( m2t,i + (η − γ) t−1∑ s=1 ηt−s−1m2s,i ) .
(42)
Next, we will discuss the value of η in two cases.
a) η = 1. From (42), we have
σt,i ≥ (1− γ) ( m2t,i + (1− γ) t−1∑ s=1 m2s,i ) > (1− γ)2 t∑ s=1 m2s,i ≥ (1− ν)2 t∑ s=1 m2s,i. (43)
Recalling the definition of Mt,i in Section 1.5, from (43), we have T∑ t=1 m2t,i√ σt,i < 1 1− ν T∑ t=1 m2t,i ‖Mt,i‖2 ≤ 2 1− ν ‖MT,i‖2,
where the last inequality above follows from Appendix C of Duchi et al. (2011). Therefore, we get
T∑ t=1 ‖mt‖2 ( √ Vt αt )−1 = α T∑ t=1 d∑ i=1 m2t,i√ σt,i < 2α 1− ν d∑ i=1 ‖MT,i‖2. (44)
b) η < 1. We assume η ≥ γ and κVt Vt−1 where κ < 1, then we have t∑
s=1
κt−sσt,i ≥ t∑
s=1
σs,i ≥ (1− γ) t∑
s=1
m2s,i.
Hence, we get
σt,i ≥ 1− κ 1− κt
(1− γ) t∑
s=1
m2s,i > (1− κ)(1− γ) t∑
s=1
m2s,i ≥ (1− ν)2 t∑
s=1
m2s,i, (45)
which deduces the same conclusion (44) of a).
Combine a) and b), we complete the proof.
F.2 PROOF OF COROLLARY 1
Proof. From the definition of mt (13), Vt (15), we have
|mt,i| = | t∑
s=1
γt−sgs,i| ≤ 1− γt
1− γ G <
G 1− γ ≤ G 1− ν ,
|σt,i| = | t∑
s=1
ηt−sg2s,i| ≤ tG2.
Hence, we have
ΨT (x ∗) ≤ λ1dD1 + λ21dD1(
√ TG
2α + λ2)
1 2 + λ2dD 2 1, (46)
hT (x ∗) ≤ dD
2 2G
2α
√ T , (47)
1
2 T∑ t=1 ‖mt‖2h∗t−1 < α 1− ν d∑ i=1 √ TG 1− ν = dαG (1− ν)2 √ T . (48)
Combining (46), (47), (48), we complete the proof.

heading: G ADDITIONAL EMPIRICAL RESULTS

Review summaries:
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.