summaries: To enforce sparsity in neural networks, the paper proposes a scale-invariant regularizer (DeepHoyer) inspired by the Hoyer measure. It is simply the ratio between l1 and l2 norm, which is almost everywhere differentiable, and enforces element-wise sparsity. It further proposes the Hoyer measure to quantify sparsity and applies the DeepHoyer in DNN training to train pruned models. The extension of Hoyer-Square is also straightforward.

summaries: The paper focuses on sparse neural networks. Typically, l1 regularization is the go-to strategy, however, it is not scale invariant. That is, all weights are affected by the regularization, not only those that are being driven to 0. l0 regularization is theoretically optimal, however, it is not smooth and has no gradients almost everywhere, so it cannot be used for training. As a compromise the paper proposes Hoyer regularization, that is the l1/l2 ratio. The Hoyer regularization has the same minima structure and leads to sparse solutions while being scale invariant, that is it does not affect all weights in the process. Additionally, the paper proposes structured Hoyer regularization. Last, it employs the said regularizations in deep networks: LeNet, AlexNet and ResNet on several datasets: MNIST, CIFAR, ImageNet.

abstractText: In seeking for sparse and efficient neural network models, many previous works investigated on enforcing `1 or `0 regularizers to encourage weight sparsity during training. The `0 regularizer measures the parameter sparsity directly and is invariant to the scaling of parameter values. But it cannot provide useful gradients and therefore requires complex optimization techniques. The `1 regularizer is almost everywhere differentiable and can be easily optimized with gradient descent. Yet it is not scale-invariant and causes the same shrinking rate to all parameters, which is inefficient in increasing sparsity. Inspired by the Hoyer measure (the ratio between `1 and `2 norms) used in traditional compressed sensing problems, we present DeepHoyer, a set of sparsity-inducing regularizers that are both differentiable almost everywhere and scale-invariant. Our experiments show that enforcing DeepHoyer regularizers can produce even sparser neural network models than previous works, under the same accuracy level. We also show that DeepHoyer can be applied to both element-wise and structural pruning. The codes are available at https://github.com/yanghr/DeepHoyer.

authors:
Jose M Alvarez
Mathieu Salzmann

title: Learning the number of neurons in deep networks

venue: In Advances in Neural Information Processing Systems,

authors:
Peter Auer
Mark Herbster
Manfred K Warmuth

title: Exponentially many local minima for single neurons

venue: In Advances in neural information processing systems,

authors:
Xiaoliang Dai
Hongxu Yin
Niraj K. Jha

title: Nest: A neural network synthesis tool based on a grow-and-prune paradigm

authors:
Xiaohan Ding
Guiguang Ding
Yuchen Guo
Jungong Han

title: Centripetal sgd for pruning very deep convolutional networks with complicated structure

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Ernie Esser
Yifei Lou
Jack Xin

title: A method for finding structured sparse solutions to nonnegative least squares problems with applications

venue: SIAM Journal on Imaging Sciences,

authors:
Jianqing Fan
Runze Li

title: Variable selection via nonconcave penalized likelihood and its oracle properties

venue: Journal of the American statistical Association,

authors:
Ariel Gordon
Elad Eban
Ofir Nachum
Bo Chen
Hao Wu
Tien-Ju Yang
Edward Choi

title: Morphnet: Fast & simple resource-constrained structure learning of deep networks

authors:
Yiwen Guo
Anbang Yao
Yurong Chen

title: Dynamic network surgery for efficient dnns

venue: In Advances In Neural Information Processing Systems,

authors:
Song Han
Huizi Mao
William J Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

venue: arXiv preprint arXiv:1510.00149,

authors:
Song Han
Jeff Pool
John Tran
William Dally

title: Learning both weights and connections for efficient neural network

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Yang He
Guoliang Kang
Xuanyi Dong
Yanwei Fu
Yi Yang

title: Soft filter pruning for accelerating deep convolutional neural networks

venue: arXiv preprint arXiv:1808.06866,

authors:
Yihui He
Xiangyu Zhang
Jian Sun

title: Channel pruning for accelerating very deep neural networks

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Yihui He
Ji Lin
Zhijian Liu
Hanrui Wang
Li-Jia Li
Song Han

title: Amc: Automl for model compression and acceleration on mobile devices

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

title: Non-negative matrix factorization with sparseness constraints

venue: Journal of machine learning research,

authors:
Zehao Huang
Naiyan Wang

title: Data-driven sparse structure selection for deep neural networks

authors:
Niall Hurley
Scott Rickard

title: Comparing measures of sparsity

venue: IEEE Transactions on Information Theory,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Dilip Krishnan
Terence Tay
Rob Fergus

title: Blind deconvolution using a normalized sparsity measure

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in neural information processing

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Namhoon Lee
Thalaiyasingam Ajanthan
Philip Torr

title: SNIP: SINGLE-SHOT NETWORK PRUNING BASED ON CONNECTION SENSITIVITY

venue: In International Conference on Learning Representations,

authors:
Hao Li
Asim Kadav
Igor Durdanovic
Hanan Samet
Hans Peter Graf

title: Pruning filters for efficient convnets

venue: arXiv preprint arXiv:1608.08710,

authors:
Tuanhui Li
Baoyuan Wu
Yujiu Yang
Yanbo Fan
Yong Zhang
Wei Liu

title: Compressing convolutional neural networks via factorized convolutional filters

authors:
Shaohui Lin
Rongrong Ji
Yuchao Li
Yongjian Wu
Feiyue Huang
Baochang Zhang

title: Accelerating convolutional networks via global & dynamic filter pruning

venue: In IJCAI,

authors:
Shaohui Lin
Rongrong Ji
Yuchao Li
Cheng Deng
Xuelong Li

title: Toward compact convnets via structure-sparsity regularized filter pruning

venue: IEEE transactions on neural networks and learning systems,

authors:
Baoyuan Liu
Min Wang
Hassan Foroosh
Marshall Tappen
Marianna Pensky

title: Sparse convolutional neural networks

authors:
Zhuang Liu
Jianguo Li
Zhiqiang Shen
Gao Huang
Shoumeng Yan
Changshui Zhang

title: Learning efficient convolutional networks through network slimming

authors:
Christos Louizos
Karen Ullrich
Max Welling

title: Bayesian compression for deep learning

authors:
Christos Louizos
Max Welling
Diederik P Kingma

title: Learning sparse neural networks through l_0 regularization

venue: arXiv preprint arXiv:1712.01312,

authors:
Jian-Hao Luo
Jianxin Wu

title: Autopruner: An end-to-end trainable filter pruning method for efficient deep model inference

venue: arXiv preprint arXiv:1805.08941,

authors:
Jian-Hao Luo
Jianxin Wu
Weiyao Lin

title: Thinet: A filter level pruning method for deep neural network compression

venue: In Proceedings of the IEEE international conference on computer vision,

authors:
Rongrong Ma
Jianyu Miao
Lingfeng Niu
Peng Zhang

title: Transformed `1 regularization for learning sparse deep neural networks

venue: Neural Networks,

authors:
Konstantinos Makantasis
Konstantinos Karantzalos
Anastasios Doulamis
Nikolaos Doulamis

title: Deep supervised learning for hyperspectral data classification through convolutional neural networks

venue: In 2015 IEEE International Geoscience and Remote Sensing Symposium (IGARSS),

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin Riedmiller

title: Playing atari with deep reinforcement learning

venue: arXiv preprint arXiv:1312.5602,

authors:
Dmitry Molchanov
Arsenii Ashukha
Dmitry Vetrov

title: Variational dropout sparsifies deep neural networks

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Kirill Neklyudov
Dmitry Molchanov
Arsenii Ashukha
Dmitry P Vetrov

title: Structured bayesian pruning via log-normal multiplicative noise

authors:
Jongsoo Park
Sheng Li
Wei Wen
Ping Tak Peter Tang
Hai Li
Yiran Chen
Pradeep Dubey

title: Faster cnns with direct sparse convolutions and guided pruning

venue: arXiv preprint arXiv:1608.01409,

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic differentiation in pytorch

venue: NIPS-W,

authors:
Audrey Repetti
Mai Quyen Pham
Laurent Duval
Emilie Chouzenoux
Jean-Christophe Pesquet

title: Euclid in a taxicab: Sparse blind deconvolution with smoothed `1/`2 regularization

venue: IEEE signal processing letters,

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

authors:
Pravendra Singh
Vinay Kumar Verma
Piyush Rai
Vinay P Namboodiri

title: Leveraging filter correlations for deep model compression

venue: arXiv preprint arXiv:1811.10559,

authors:
Ilya Sutskever
James Martens
George Dahl
Geoffrey Hinton

title: On the importance of initialization and momentum in deep learning

venue: In International conference on machine learning,

title: Regression shrinkage and selection via the lasso

venue: Journal of the Royal Statistical Society: Series B (Methodological),

authors:
Armenak Petrosyan Tran
Clayton Webster

title: Reconstruction of jointly sparse vectors via manifold optimization

venue: arXiv preprint arXiv:1811.08778,

authors:
Fei Wen
Lei Chu
Peilin Liu
Robert C Qiu

title: A survey on nonconvex regularization-based sparse and low-rank recovery in signal processing, statistics, and machine learning

venue: IEEE Access,

authors:
Wei Wen
Chunpeng Wu
Yandan Wang
Yiran Chen
Hai Li

title: Learning structured sparsity in deep neural networks

authors:
Wei Wen
Yuxiong He
Samyam Rajbhandari
Minjia Zhang
Wenhan Wang
Fang Liu
Bin Hu
Yiran Chen
Hai Li

title: Learning intrinsic sparse structures within long short-term memory

venue: arXiv preprint arXiv:1709.05027,

authors:
Penghang Yin
Ernie Esser
Jack Xin

title: Ratio and difference of l1 and l2 norms and sparse representation with coherent dictionaries

venue: Commun. Inform. Systems,

authors:
Ruichi Yu
Ang Li
Chun-Fu Chen
Jui-Hsin Lai
Vlad I Morariu
Xintong Han
Mingfei Gao
Ching-Yung Lin
Larry S Davis

title: Nisp: Pruning networks using neuron importance score propagation

authors:
Ming Yuan
Yi Lin

title: Model selection and estimation in regression with grouped variables

venue: Journal of the Royal Statistical Society: Series B (Statistical Methodology),

authors:
Jihun Yun
Peng Zheng
Eunho Yang
Aurelie Lozano
Aleksandr Aravkin

title: Trimming the `1 regularizer: Statistical analysis, optimization, and applications to deep learning

venue: In International Conference on Machine Learning,

title: Nearly unbiased variable selection under minimax concave penalty

venue: The Annals of statistics,

authors:
Tianyun Zhang
Shaokai Ye
Kaiqi Zhang
Jian Tang
Wujie Wen
Makan Fardad
Yanzhi Wang

title: A systematic dnn weight pruning framework using alternating direction method of multipliers

authors:
Zhuangwei Zhuang
Mingkui Tan
Bohan Zhuang
Jing Liu
Yong Guo
Qingyao Wu
Junzhou Huang
Jinhui Zhu

title: Discrimination-aware channel pruning for deep neural networks

heading: 1 INTRODUCTION

text:
The use of deep neural network (DNN) models has been expanded from handwritten digit recognition (LeCun et al., 1998) to real-world applications, such as large-scale image classification (Simonyan & Zisserman, 2014), self driving (Makantasis et al., 2015) and complex control problems (Mnih et al., 2013). However, a modern DNN model like AlexNet (Krizhevsky et al., 2012) or ResNet (He et al., 2016) often introduces a large number of parameters and computation load, which makes the deployment and real-time processing on embedded and edge devices extremely difficult (Han et al., 2015b;a; Wen et al., 2016). Thus, model compression techniques, especially pruning methods that increase the sparsity of weight matrices, have been extensively studied to reduce the memory consumption and computation cost of DNNs (Han et al., 2015b;a; Wen et al., 2016; Guo et al., 2016; Louizos et al., 2017b; Luo et al., 2017; Zhang et al., 2018; Liu et al., 2015).
Most of the previous works utilize some form of sparsity-inducing regularizer in searching for sparse neural networks. The `1 regularizer, originally proposed by Tibshirani (1996), can be easily optimized through gradient descent for its convex and almost everywhere differentiable property. Therefore it is widely used in DNN pruning: Liu et al. (2015) directly apply `1 regularization to all the weights of a DNN to achieve element-wise sparsity; Wen et al. (2016; 2017) present structural sparsity via group lasso, which applies an `1 regularization over the `2 norms of different groups of parameters. However, it has been noted that the value of the `1 regularizer is proportional to the scaling of parameters (i.e. ||αW ||1= |α|·||W ||1), so it “scales down” all the elements in the weight matrices with the same speed. This is not efficient in finding sparsity and may sacrifice the flexibility of the trained model. On the other hand, the `0 regularizer directly reflects the real sparsity of weights and is scale invariant (i.e. ||αW ||0= ||W ||0,∀α 6= 0), yet the `0 norm cannot provide useful gradients. Han et al. (2015b) enforce an element-wise `0 constraint by iterative pruning a fixed percentage of smallest weight elements, which is a heuristic method and therefore can hardly achieve optimal compression rate. Some recent works mitigate the lack of gradient information by integrating `0 regularization with stochastic approximation (Louizos et al., 2017b) or more complex optimization methods (e.g.
ADMM) (Zhang et al., 2018). These additional measures brought overheads to the optimization process, making the use of these methods on larger networks difficult. To achieve even sparser neural networks, we argue to move beyond `0 and `1 regularizers and seek for a sparsity-inducing regularizer that is both almost everywhere differentiable (like `1) and scale-invariant (like `0).
Beyond the `1 regularizer, plenty of non-convex sparsity measurements have been used in the field of feature selection and compressed sensing (Hurley & Rickard, 2009; Wen et al., 2018). Some popular regularizers like SCAD (Fan & Li, 2001), MDP (Zhang et al., 2010) and Trimmed `1 (Yun et al., 2019) use a piece-wise formulation to mitigate the proportional scaling problem of `1. The piece-wise formulation protects larger elements by having zero penalty to elements greater than a predefined threshold. However, it is extremely costly to manually seek for the optimal trimming threshold, so it is hard to obtain optimal result in DNN pruning by using these regularizers. The transformed `1 regularizer formulated as ∑N i=1 (a+1)|wi| a+|wi| manages to smoothly interpolate between `1 and `0 by tuning the hyperparameter a (Ma et al., 2019). However, such an approximation is close to `0 only when a approaches infinity, so the practical formulation of the transformed `1 (i.e. a = 1) is still not scale-invariant.
Particularly, we are interested in the Hoyer regularizer (Hoyer, 2004), which estimates the sparsity of a vector with the ratio between its `1 and `2 norms. Comparing to other sparsity-inducing regularizers, Hoyer regularizer achieves superior performance in the fields of non-negative matrix factorization (Hoyer, 2004), sparse reconstruction (Esser et al., 2013; Tran et al., 2018) and blend deconvolution (Krishnan et al., 2011; Repetti et al., 2015). We note that Hoyer regularizer is both almost everywhere differentiable and scale invariant, satisfying the desired property of a sparsityinducing regularizer. We therefore propose DeepHoyer, which is the first Hoyer-inspired regularizers for DNN sparsification. Specifically, the contributions of this work include:
• Hoyer-Square (HS) regularizer for element-wise sparsity: We enhance the original Hoyer regularizer to the HS regularizer and achieve element-wise sparsity by applying it in the training of DNNs. The HS regularizer is both almost everywhere differentiable and scale invariant. It has the same range and minima structure as the `0 norm. Thus, the HS regularizer presents the ability of turning small weights to zero while protecting and maintaining those weights that are larger than an induced, gradually adaptive threshold; • Group-HS regularizer for structural sparsity, which is extended from the HS regularizer; • Generating sparser DNN models: Our experiments show that the proposed regularizers beat
state-of-the-arts in both element-wise and structural weight pruning of modern DNNs.

heading: 2 RELATED WORK ON DNN PRUNING

text:
It is well known that high redundancy pervasively exists in DNNs. Consequently, pruning methods have been extensively investigated to identify and remove unimportant weights. Some heuristic pruning methods (Han et al., 2015b; Guo et al., 2016) simply remove weights in small values to generate sparse models. These methods usually require long training time without ensuring the optimality, due to the lack of theoretical understanding and well-formulated optimization (Zhang et al., 2018). Some works formulate the problem as a sparsity-inducing optimization problem, such as `1 regularization (Liu et al., 2015; Park et al., 2016) that can be optimized using standard gradientbased algorithms, or `0 regularization (Louizos et al., 2017b; Zhang et al., 2018) which requires stochastic approximation or special optimization techniques. We propose DeepHoyer regularizers in this work, which belong to the line of sparsity-inducing optimization research. More specific, the proposed Hoyer-Square regularizer for element-wise pruning is scale-invariant and can serve as an differentiable approximation to the `0 norm. Furthermore, it can be optimized by gradient-based optimization methods in the same way as the `1 regularization. With these properties, the HoyerSquare regularizer achieves a further 38% and 63% sparsity improvement on LeNet-300-100 model and LeNet-5 model respectively comparing to previous state-of-the-arts, and achieves the highest sparsity on AlexNet without accuracy loss.
Structurally sparse DNNs attempt to create regular sparse patterns that are friendly for hardware execution. To achieve the goal, Li et al. (2016) propose to remove filters with small norms; Wen et al. (2016) apply group Lasso regularization based methods to remove various structures (e.g., filters, channels, layers) in DNNs and the similar approaches are used to remove neurons (Alvarez &
Salzmann, 2016); Liu et al. (2017) and Gordon et al. (2018) (MorphNet) enforce sparsity-inducing regularization on the scaling parameters within Batch Normalization layers to remove the corresponding channels in DNNs; ThiNet (Luo et al., 2017) removes unimportant filters by minimizing the reconstruction error of feature maps; and He et al. (2017) incorporate both Lasso regression and reconstruction error into the optimization problem. Bayesian optimization methods have also been applied for neuron pruning (Louizos et al., 2017a; Neklyudov et al., 2017), yet these methods are not applicable in large-scale problems like ImageNet. We further advance the DeepHoyer to learn structured sparsity (such as reducing filters and channels) with the newly proposed “Group-HS” regularization. The Group-HS regularizer further improves the computation reduction of the LeNet-5 model by 8.8% from the `1 based method (Wen et al., 2016), and by 110.6% from the `0 based method (Louizos et al., 2017b). Experiments on ResNet models reveal that the accuracy-speedup tradeoff induced by Group-HS constantly stays above the Pareto frontier of previous methods. More detailed results can be found in Section 5.

heading: 3 MEASURING SPARSITY WITH THE HOYER MEASURE

text:
Sparsity measures provide tractable sparsity constraints for enforcement during problem solving and therefore have been extensively studied in the compressed sensing society. In early non-negative matrix factorization (NMF) research, a consensus was that a sparsity measure should map a ndimensional vector X to a real number S ∈ [0, 1], such that the possible sparsest vectors with only one nonzero element has S = 1, and a vector with all equal elements has S = 0 (Hoyer, 2004). Unders the assumption, the Hoyer measure was proposed as follows
S(X) =
√ n− ( ∑ i|xi|)/ √∑ i x
2 i√
n− 1 . (1)
It can be seen that
1 ≤ ∑
i|xi|√∑ i x 2 i ≤ √ n, ∀X ∈ Rn. (2)
Thus, the normalization in Equation (1) fits the measure S(X) into the [0, 1] interval. According to the survey by Hurley & Rickard (2009), among the six desired heuristic criteria of sparsity measures, the Hoyer measure satisfies five, more than all other commonly applied sparsity measures. Given its success as a sparsity measure in NMF, the Hoyer measure has been applied as a sparsity-inducing regularizer in optimization problems such as blind deconvolution (Repetti et al., 2015) and image deblurring (Krishnan et al., 2011). Without the range constraint, the Hoyer regularizer in these works adopts the form R(X) = ∑ i|xi|√∑
i x 2 i
directly, as the ratio of the `1 and `2 norms.
Figure 1 compares the Hoyer regularizer and the `1 regularizer. Unlike the the `1 norm with a single minimum at the origin, the Hoyer regularizer has minima along axes, the structure of which is very similar to the `0 norm’s. Moreover, the Hoyer regularizer is scale-invariant, i.e. R(αX) = R(X), because both the `1 norm and the `2 norm are proportional to the scale of X . The gradients of the Hoyer regularizer are purely radial, leading to “rotations” towards the nearest axis. These features make the Hoyer regularizer outperform the `1 regularizer on various tasks (Esser et al., 2013; Tran
et al., 2018; Krishnan et al., 2011; Repetti et al., 2015). The theoretical analysis by Yin et al. (2014) also proves that the Hoyer regularizer has a better guarantee than the `1 norm on recovering sparse solutions from coherent and redundant representations.

heading: 4 MODEL COMPRESSION WITH DEEPHOYER REGULARIZERS

text: Inspired by the Hoyer regularizer, we propose two types of DeepHoyer regularizers: the Hoyer-Square regularizer (HS) for element-wise pruning and the Group-HS regularizer for structural pruning.

heading: 4.1 HOYER-SQUARE REGULARIZER FOR ELEMENT-WISE PRUNING

text:
Since the process of the element-wise pruning is equivalent to regularizing each layer’s weight with the `0 norm, it is intuitive to configure the sparsity-inducing regularizer to have a similar behavior as the `0 norm. As shown in Inequality (2), the value of the original Hoyer regularizer of a N - dimensional nonzero vector lies between 1 and √ N , while its `0 norm is within the range of [1, N ]. Thus we propose to apply the square of Hoyer regularizer, namely Hoyer-Square (HS), to the weights W of a layer, like
HS(W ) = ( ∑
i|wi|)2∑ i w 2 i . (3)
The proposed HS regularizer behaves as a differentiable approximation to the `0 norm. First, both regularizers now have the same range of [1, N ]. Second,HS is scale invariant asHS(αW ) = HS(W ) holds for ∀α 6= 0, so as the `0 norm. Moreover, as the squaring operator monotonously increases in the range of [1, √ N ], the Hoyer-Square regularizer’s minima remain along the axes as the Hoyer regularizer’s do (see Figure 1). In other words, they have similar minima structure as the `0 norm. At last, the Hoyer-Square regularizer is also almost everywhere differentiable and Equation (4) formulates the gradient of HS w.r.t. an element wj in the weight matrix W :
∂wjHS(W ) = 2sign(wj)
∑ i|wi|
( ∑
i w 2 i ) 2 ( ∑ i w2i − |wj | ∑ i |wi|). (4)
Very importantly, this formulation induces a trimming effect: when HS(W ) is being minimized through gradient descent, wj moves towards 0 if |wj |< ∑ i w 2 i∑
i|wi| , otherwise moves away from 0. In
other words, unlike the `1 regularizer which tends to shrink all elements, our Hoyer-Square regularizer will turn weights in small value to zero meanwhile protecting large weights. Traditional trimmed regularizers (Fan & Li, 2001; Zhang et al., 2010; Yun et al., 2019) usually define a trimming threshold as a fixed value or percentage. Instead, the HS regularizer can gradually extend the scope of pruning as more weights coming close to zero. This behavior can be observed in the gradient descent path shown in Figure 2.

heading: 4.2 GROUP-HS REGULARIZER FOR STRUCTURAL PRUNING

text:
Beyond element-wise pruning, structural pruning is often more preferred because it can construct the sparsity in a structured way and therefore achieve higher computation speed-up on general computation platforms (Wen et al., 2016). The structural pruning is previously empowered by the group lasso (Yuan & Lin, 2006; Wen et al., 2016), which is the sum (i.e. `1 norm) of the `2 norms of all the groups within a weight matrix like
RG(W ) = G∑ g=1 ||w(g)||2, (5)
where ||W ||2= √∑ i w 2 i represents the `2 norm, w
(g) is a group of elements in the weight matrix W which consists of G such groups.
Following the same approach in Section 4.1, we use the Hoyer-Square regularizer to replace the `1 regularizer in the group lasso formulation and define the Group-HS (GH ) regularizer in Equation (6):
GH(W ) = ( ∑G
g=1||w(g)||2)2∑G g=1||w(g)||22
= ( ∑G g=1||w(g)||2)2
||W ||22 . (6)
Note that the second equality holds when and only when the groups cover all the elements of W without overlapping with each other. Our experiments in this paper satisfy this requirement. However, the Group-HS regularizer can always be used in the form of the first equality when overlapping exists across groups. The gradient and the descent path of the Group-HS regularizer are very similar to those of the Hoyer-Square regularizer, and therefore we omit the detailed discussion here. The derivation of the Group-HS regularizer’s gradient shall be found in Appendix A.

heading: 4.3 APPLY DEEPHOYER REGULARIZERS IN DNN TRAINING

text:
The deployment of the DeepHoyer regularizers in DNN training follows the common layer-based regularization approach (Wen et al., 2016; Liu et al., 2015). For element-wise pruning, we apply the Hoyer-Square regularizer to layer weight matrix W (l) for all L layers, and directly minimize it alongside the DNN’s original training objective L(W (1:L)). The `2 regularizer can also be added to the objective if needed. Equation (7) presents the training objective with HS defined in Equation (3). Here, α and β are pre-selected weight decay parameters for the regularizers.
min W (1:L)
L(W (1:L)) + L∑
l=1
(αHS(W (l)) + β||W (l)||2). (7)
For structural pruning, we mainly focus on pruning the columns and rows of fully connected layers and the filters and channels of convolutional layers. More specific, we group a layer in filter-wise and channel-wise fashion as proposed by Wen et al. (2016) and then apply the Group-HS regularizer to the layer. The resulted optimization objective is formulated in Equation (8).
min W (1:L)
L(W (1:L)) + L∑
l=1
(αn ( ∑Nl nl=1 ||w(l)nl,:,:,:||2)2
||W (l)||22 + αc
( ∑Cl
cl=1 ||w(l):,cl,:,:||2)2
||W (l)||22 + β||W (l)||2). (8)
HereNl is the number of filters andCl is the number of channels in the lth layer if it is a convolutional layer. If the lth layer is fully connected, then Nl and Cl is the number of rows and columns respectively. αn, αc and β are pre-selected weight decay parameters for the regularizers.
The recent advance in stochastic gradient descent (SGD) method provides satisfying results under large-scale non-convex settings (Sutskever et al., 2013; Kingma & Ba, 2014), including DNNs with non-convex objectives (Auer et al., 1996). So we can directly optimize the DeepHoyer regularizers with the same SGD optimizer used for the original DNN training objective, despite their nonconvex formulations. Our experiments show that the tiny-bit nonconvexity induced by DeepHoyer does not affect the performance of DNNs.
The pruning is conducted by following the common three-stage operations: (1) train the DNN with the DeepHoyer regularizer, (2) prune all the weight elements smaller than a predefined small threshold, and (3) finetune the model by fixing all the zero elements and removing the DeepHoyer regularizer.

heading: 5 EXPERIMENT RESULT

text: The proposed DeepHoyer regularizers are first tested on the MNIST benchmark using the LeNet300-100 fully connected model and the LeNet-5 CNN model (LeCun et al., 1998). We also conduct tests on the CIFAR-10 dataset (Krizhevsky & Hinton, 2009) with ResNet models (He et al., 2016) in various depths, and on ImageNet ILSVRC-2012 benchmark (Russakovsky et al., 2015) with the AlexNet model (Krizhevsky et al., 2012) and the ResNet-50 model (He et al., 2016). All the models are implemented and trained in the PyTorch deep learning framework (Paszke et al., 2017), where we match the model structure and the benchmark performance with those of previous works for the fairness of comparison. The experiment results presented in the rest of this section show that the proposed DeepHoyer regularizers consistently outperform previous works in both element-wise and structural pruning. Detailed information on the experiment setups and the parameter choices of our reported results can be found in Appendix B.

heading: 5.1 ELEMENT-WISE PRUNING

text:
Table 1 and Table 2 summarize the performance of the proposed Hoyer-square regularizer on the MNIST benchmark, with comparisons against state of the art (SOTA) element-wise pruning methods. Without losing the testing accuracy, training with the Hoyer-Square regularizer reduces the number of nonzero weights by 54.5× on the LeNet-300-100 model and by 122× on the LeNet-5 model. Among all the methods, ours achieves the highest sparsity: it is a 38% improvement on the LeNet-300-100 model and a 63% improvement on the LeNet-5 model comparing to the best available methods. Additional results in Appendix C.1 further illustrates the effect of the Hoyer-Square regularizer on each layer’s weight distribution during the training process.
The element-wise pruning performance on the AlexNet model testing on the ImageNet benchmark is presented in Table 3. Without losing the testing accuracy, the Hoyer-Square regularizer improves
1We implement the transformed `1 regularizer in (Ma et al., 2019) ourselves because the experiments in the original paper are under different settings. Implementation details can be found in Appendix B.
the compression rate by 21.3×. This result is the highest among all methods, even better than the ADMM method (Zhang et al., 2018) which requires two additional Lagrange multipliers and involves the optimization of two objectives. Considering that the optimization of the Hoyer-Square regularizer can be directly realized on a single objective without additional variables, we conclude that the Hoyer-Square regularizer can achieve a sparse DNN model with a much lower cost. A more detailed layer-by-layer sparsity comparison of the compressed model can be found in Appendix C.2.
We perform the ablation study for performance comparison between the Hoyer-Square regularizer and the original Hoyer regularizer. The results in Tables 1, 2 and 3 all show that the Hoyer-Square regularizer always achieves a higher compression rate than the original Hoyer regularizer. The layer-wise compression results show that the Hoyer-Square regularizer emphasizes more on the layers with more parameters (i.e. FC1 for the MNIST models). This corresponds to the fact that the value of the Hoyer-Square regularizer is proportional to the number of non-zero elements in the weight. These observations validate our choice to use the Hoyer-Square regularizer for DNN compression.

heading: 5.2 STRUCTURAL PRUNING

text:
This section reports the effectiveness of the Group-HS regularizer in structural pruning tasks. Here we mainly focus on the number of remaining neurons (output channels for convolution layers and rows for fully connected layers) after removing the all-zero channels or rows in the weight matrices. The comparison is then made based on the required float-point operations (FLOPs) to inference with the remaining neurons, which indeed represents the potential inference speed of the pruned model. As shown in Table 4, training with the Group-HS regularizer can reduce the number of FLOPs by 16.2× for the LeNet-300-100 model with a slight accuracy drop. This is the highest speedup among all existing methods achieving the same testing accuracy. Table 5 shows that the Group-HS regularizer can reduce the number of FLOPs of the LeNet-5 model by 12.4×, which outperforms most of the existing work—an 8.8% increase from the `1 based method (Wen et al., 2016) and a 110.6% increase from the `0 based method (Louizos et al., 2017b). Only the Bayesian compression (BC) method with the group-horseshoe prior (BC-GHS) (Louizos et al., 2017a) achieves a slightly higher speedup on the LeNet-5 model. However, the complexity of high dimensional Bayesian inference limits BC’s capability. It is difficult to apply BC to ImageNet-level problems and large DNN models like ResNet.
In contrast, the effectiveness of the Group-HS regularizer can be easily extended to deeper models and larger datasets, which is demonstrated by our experiments. We apply the Group-HS regularizer to ResNet models (He et al., 2016) on the CIFAR-10 and the ImageNet datasets. Pruning ResNet has long been considered difficult due to the compact structure of the ResNet model. Since previous works usually report the compression rate at different accuracy, we use the “accuracy-#FLOPs” plot to represent the tradeoff. The tradeoff between the accuracy and the FLOPs are explored in this work by changing the strength of the Group-HS regularizer used in training. Figure 3 shows the performance of DeepHoyer constantly stays above the Pareto frontier of previous methods.

heading: 6 CONCLUSIONS

text: In this work, we propose DeepHoyer, a set of sparsity-inducing regularizers that are both scaleinvariant and almost everywhere differentiable. We show that the proposed regularizers have similar range and minima structure as the `0 norm, so it can effectively measure and regularize the sparsity of the weight matrices of DNN models. Meanwhile, the differentiable property enables the proposed regularizers to be simply optimized with standard gradient-based methods, in the same way as the `1 regularizer is. In the element-wise pruning experiment, the proposed Hoyer-Square regularizer achieves a 38% sparsity increase on the LeNet-300-100 model and a 63% sparsity increase on the LeNet-5 model without accuracy loss comparing to the state-of-the-art. A 21.3× model compression rate is achieved on AlexNet, which also surpass all previous methods. In the structural pruning experiment, the proposed Group-HS regularizer further reduces the computation load by 24.4% from the state-of-the-art on LeNet-300-100 model. It also achieves a 8.8% increase from the `1 based method and a 110.6% increase from the `0 based method of the computation reduction rate on the LeNet-5 model. For CIFAR-10 and ImageNet dataset, the accuracy-FLOPs tradeoff achieved by training ResNet models with various strengths of the Group-HS regularizer constantly stays above the Pareto frontier of previous methods. These results prove that the DeepHoyer regularizers are effective in achieving both element-wise and structural sparsity in deep neural networks, and can produce even sparser DNN models than previous works.

heading: ACKNOWLEDGMENTS

text: The authors would like to thank Feng Yan for his help on computation resources throughout this project. Our work was supported in part by NSF SPX-1725456 and NSF CNS-1822085.

heading: A DERIVATION OF DEEPHOYER REGULARIZERS’ GRADIENTS

text:
In this section we provide detailed derivation of the gradient of the Hoyer-Square regularizer and the Group-GS regularizer w.r.t. an element wj in the weight matrix W .
The gradient of the Hoyer-Square regularizer is shown in Equation (9). The formulation shown in Equation (4) is achieved at the end of the derivation.
∂wjHS(W ) = [∂wj ((
∑ i|wi|)2)] ∑ i w 2 i − [∂wj ( ∑ i w 2 i )]( ∑ i|wi|)2
( ∑
i w 2 i ) 2
= 2[∂wj (|wj |)]
∑ i|wi| ∑ i w 2 i − 2wj( ∑ i|wi|)2
( ∑
i w 2 i ) 2
= 2
∑ i|wi|
( ∑
i w 2 i )
2 (sign(wj) ∑ i w2i − sign(wj)|wj | ∑ i |wi|)
= 2sign(wj)
∑ i|wi|
( ∑
i w 2 i ) 2 ( ∑ i w2i − |wj | ∑ i |wi|).
(9)
The gradient of the Group-HS regularizer is shown in Equation (10). For simplicity we use the form shown in the second equality of Equation (6), where there is no overlapping between the groups. Here we assume that wj belongs to group w(ĝ).
∂wjGH(W ) = ∂wj ( ∑G
g=1||w(g)||2)2∑ i w 2 i
= [∂wj ((
∑G g=1||w(g)||2)2)] ∑ i w 2 i − [∂wj ( ∑ i w 2 i )]( ∑G g=1||w(g)||2)2
( ∑
i w 2 i ) 2
= 2[∂wj (||w(ĝ)||2)]
∑G g=1||w(g)||2 ∑ i w 2 i − 2wj( ∑G g=1||w(g)||2)2
( ∑
i w 2 i ) 2
= 2 ∑G g=1||w(g)||2 ( ∑
i w 2 i )
2 ( wj ||w(ĝ)||2 ∑ i w2i − wj G∑ g=1 ||w(g)||2)
= 2 wj
||w(ĝ)||2
∑ i|wi|
( ∑
i w 2 i ) 2 ( ∑ i w2i − ||w(ĝ)||2 G∑ g=1 ||w(g)||2).
(10)

heading: B DETAILED EXPERIMENT SETUP

text:
B.1 MNIST EXPERIMENTS
The MNIST dataset (LeCun et al., 1998) is a well known handwritten digit dataset consists of greyscale images with the size of 28× 28 pixels. We use the dataset API provided in the “torchvision” python package to access the dataset. In our experiments we use the whole 60,000 training set images for the training and the whole 10,000 testing set images for the evaluation. All the accuracy results reported in the paper are evaluated on the testing set. Both the training set and the testing set are normalized to have zero mean and variance one. Adam optimizer (Kingma & Ba, 2014) with learning rate 0.001 is used throughout the training process. All the MNIST experiments are done with a single TITAN XP GPU.
Both the LeNet-300-100 model and the LeNet-5 model are firstly pretrained without the sparsityinducing regularizer, where they achieve the testing accuracy of 98.4% and 99.2% respectively. Then the models are further trained for 250 epochs with the DeepHoyer regularizers applied in the objective. The weight decay parameters (αs in Equation (7) and (8)) are picked by hand to reach the best result. In the last step, we prune the weight of each layer with threshold proportional to the standard derivation of each layer’s weight. The threshold/std ratio is chosen to achieve the highest sparsity without accuracy loss. All weight elements with a absolute value smaller than the threshold
is set to zero and is fixed during the final finetuning. The pruned model is finetuned for another 100 steps without DeepHoyer regularizers and the best testing accuracy achieved is reported. Detailed parameter choices used in achieving the reported results are listed in Table 6.
B.2 IMAGENET AND CIFAR-10 EXPERIMENTS
The ImageNet dataset is a large-scale color-image dataset containing 1.2 million images of 1000 categories (Russakovsky et al., 2015), which has long been utilized as an important benchmark on image classification problems. In this paper, we use the “ILSVRC2012” version of the dataset, which can be found at http://www.image-net.org/challenges/LSVRC/ 2012/nonpub-downloads. We use all the data in the provided training set to train our model, and use the provided validation set to evaluate our model and report the testing accuracy. We follow the data reading and preprocessing pipeline suggested by the official PyTorch ImageNet example (https://github.com/pytorch/examples/tree/master/imagenet). For training images, we first randomly crop the training images to desired input size, then apply random horizontal flipping and finally normalize them before feeding them into the network. Validation images are first resized to 256× 256 pixels, then center cropped to desired input size and normalized in the end. We use input size 227 × 227 pixels for experiments on the AlexNet, and input size 224 × 224 for experiments on the ResNet-50. All the models are optimized with the SGD optimizer Sutskever et al. (2013), and the batch size is chosen as 256 for all the experiments. Two TITAN XP GPUs are used in parallel for the AlexNet training and four are used for the ResNet-50 training.
One thing worth noticing is that the AlexNet model provided in the “torchvision” package is not the ordinary version used in previous works Han et al. (2015b); Wen et al. (2016); Zhang et al. (2018). Therefore we reimplement the AlexNet model in PyTorch for fair comparison. We pretrain the implemented model for 90 epochs and achieve 19.8 % top-5 error, which is the same as reported in previous works. In the AlexNet experiment, the reported result in Table 3 is achieved by applying the Hoyer-Square regularizer with decay parameter 1e-6. Before the pruning, the model is firstly train from the pretrained model with the Hoyer-Square regularizer for 90 epochs, where an initial learning rate 0.001 is used. An `2 regularization with 1e-4 decay is also applied. We then prune the convolution layers with threshold 1e-4 and the FC layers with threshold equal to 0.4× of their standard derivations. The model is then finetuned until the best accuracy is reached. The learning rate is decayed by 0.1 for every 30 epochs of training. The training process with the Hoyer regularizer and the T`1 regularizer (Ma et al., 2019) is the same as the HS regularizer. For the reported result, we use decay 1e-3 and FC threshold 0.8× std for the Hoyer regularizer, and use decay 2e-5 and FC threshold 1.0× std for the T`1 regularizer. For the ResNet-50 experiments on ImageNet, the model architecture and pretrained model provided in the “torchvision” package is directly utilized, which achieves 23.85% top-1 error and 7.13% top-5 error. All the reported results in Figure 3 and Table 8 are achieved with 90 epochs of training with the Group-HS regularizer from the pretrained model using initial learning rate 0.1. All the models are pruned with 1e-4 as threshold and finetuned to the best accuracy. We only tune the decay parameter of the Group-HS regularizer to explore the accuracy-FLOPs tradeoff. The exact decay parameter used for each result is specified in Table 8.
We also use the CIFAR-10 dataset (Krizhevsky & Hinton, 2009) to evaluate the structural pruning performance on ResNet-56 and ResNet-110 models. The CIFAR-10 dataset can be directly accessed through the dataset API provided in the “torchvision” python package. Standard preprocessing,
including random crop, horizontal flip and normalization is used on the training set to train the model. We implemented the ResNet models for CIFAR-10 following the description in (He et al., 2016), and pretrain the models for 164 epochs. Learning rate is set to 0.1 initially, and decayed by 0.1 at epoch 81 and epoch 122. The pretrained ResNet-56 model reaches the testing accuracy of 93.14 %, while the ResNet-110 model reaches 93.62 %. Similar to the ResNet-50 experiment, we start with the pretrained models and train with the Group-HS regularizer. Same learning rate scheduling is used for both pretraining and training with Group-HS. All the models are pruned with 1e-4 as threshold and finetuned to the best accuracy. The decay parameters of the Group-HS regularizer used to get the result in Figure 3 is specified in Table 9 and Table 10.

heading: C ADDITIONAL EXPERIMENT RESULTS

text:
C.1 WEIGHT DISTRIBUTION AT DIFFERENT STAGES
Here we demonstrate how will the weight distribution change in each layer at different stages of our element-wise pruning process. Since most of the weight elements will be zero in the end, we only plot the histogram of nonzero weight elements for better observation. The histogram of each layer of the LeNet-300-100 model and the LeNet-5 model are visualized in Figure 4 and Figure 5 respectively. It can be seen that majority of the weights will be concentrated near zero after applying the HS regularizer during training, while rest of the weight elements will spread out in a wide range. The weights close to zero are then set to be exactly zero, and the model is finetuned with zero weights fixed. The resulted histogram shows that most of the weights are pruned away, only a small amount of nonzero weights are remaining in the model.
C.2 LAYER-BY-LAYER COMPARISON OF ELEMENT-WISE PRUNING RESULT OF ALEXNET
Table 7 compares the element-wise pruning result of the Hoyer-Square regularizer on AlexNet with other methods in a layer-by-layer fashion. It can be seen that the Hoyer-Square regularizer achieves high pruning rates on the largest layers (i.e. FC1-3). This observation is consistent with the observation made on the element-wise pruning performance of models on the MNIST dataset.
C.3 DETAILED RESULTS OF THE RESNET EXPERIMENTS
In this section we list the data used to plot Figure 3. Table 8 shows the result of pruning ResNet-50 model on ImageNet, Table 9 shows the result of pruning ResNet-56 model on CIFAR-10 and Table 10 shows the result of pruning ResNet-110 model on CIFAR-10. For all the tables, the results of previous works are listed on the top, and are ordered based on publication year. Results achieved with the Group-HS regularizer are listed below, marked with the regularization strength used for the training.

title: DEEPHOYER: LEARNING SPARSER NEURAL NETWORK WITH DIFFERENTIABLE SCALE-INVARIANT SPARSITY MEASURES


summaries: In the setting of online convex optimization, this paper investigates the question of whether adaptive gradient methods can achieve “data dependent” logarithmic regret bounds when the class of loss functions is strongly convex. To this end, the authors propose a variant of Adam - called SAdam - which indeed satisfies such a desired bound. Importantly, SAdam is an extension of SC-RMSprop (a variant of RMSprop) for which a “data independent” logarithmic bound was found. Experiments on optimizing strongly convex functions and training deep networks show that SAdam outperforms other adaptive gradient methods (and SGD).

summaries: In this paper, the authors propose a variant of Adam, named as SAdam, and establish a data-dependent O(log T) regret bound. The key idea is using a faster decaying yet under controlled step size to exploit strong convexity. Some experiments are carried out to demonstrate the effectiveness of the proposed algorithm. The idea seems interesting, the writing is well-written, and the analysis seems correct (I did not fully check all steps, but the key steps seems ok to me).

abstractText: O( √ T ) regret bound where T is the time horizon. However, whether strong convexity can be utilized to further improve the performance remains an open problem. In this paper, we give an affirmative answer by developing a variant of Adam (referred to as SAdam) which achieves a data-dependent O(log T ) regret bound for strongly convex functions. The essential idea is to maintain a faster decaying yet under controlled step size for exploiting strong convexity. In addition, under a special configuration of hyperparameters, our SAdam reduces to SC-RMSprop, a recently proposed variant of RMSprop for strongly convex functions, for which we provide the first data-dependent logarithmic regret bound. Empirical results on optimizing strongly convex functions and training deep networks demonstrate the effectiveness of our method.

authors:
Parnia Bahar
Tamer Alkhouli
Jan-Thorsten Peter
Christopher Jan-Steffen Brix
Hermann Ney

title: Empirical investigation of optimization algorithms in neural machine translation

venue: The Prague Bulletin of Mathematical Linguistics,

authors:
Amitabh Basu
Soham De
Anirbit Mukherjee
Enayat Ullah

title: Convergence guarantees for rmsprop and adam in non-convex optimization and their comparison to nesterov acceleration on autoencoders

venue: arXiv preprint arXiv:1807.06766,

authors:
Sebastian Bock
Josef Goppold
Martin Wei

title: An improvement of the convergence proof of the adam-optimizer

venue: arXiv preprint arXiv:1804.10587,

authors:
Xiangyi Chen
Sijia Liu
Ruoyu Sun
Mingyi Hong

title: On the convergence of a class of adam-type algorithms for non-convex optimization

venue: In Proceedings of the 7th International Conference on Learning Representations,

authors:
Zaiyi Chen
Yi Xu
Enhong Chen
Tianbao Yang

title: Sadagrad: Strongly adaptive stochastic gradient methods

venue: In Proceedings of 35th International Conference on Machine Learning,

authors:
Michael Denkowski
Graham Neubig

title: Stronger baselines for trustable results in neural machine translation

venue: In Proceedings of the 1st Workshop on Neural Machine Translation,

title: Incorporating nesterov momentum into adam

venue: In Proceedings of 4th International Conference on Learning Representations, Workshop Track,

authors:
John Duchi
Elad Hazan
Yoram Singer

title: Adaptive subgradient methods for online learning and stochastic optimization

venue: Journal of Machine Learning Research,

authors:
Karol Gregor
Ivo Danihelka
Alex Graves
Danilo Jimenez Rezende
Daan Wierstra

title: Draw: a recurrent neural network for image generation

venue: In Proceedings of the 32nd International Conference on Machine Learning,

authors:
Elad Hazan
Satyen Kale

title: Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization

authors:
Elad Hazan
Amit Agarwal
Satyen Kale

title: Logarithmic regret algorithms for online convex optimization

venue: Machine Learning,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the 29th IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Sham M Kakade
Ambuj Tewari

title: On the generalization ability of online strongly convex programming algorithms

venue: In Advances in Neural Information Processing Systems

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: In Proceedings of 3rd International Conference on Learning Representations,

authors:
Ryan Kiros
Yukun Zhu
Ruslan R Salakhutdinov
Richard Zemel
Raquel Urtasun
Antonio Torralba
Sanja Fidler

title: Skip-thought vectors

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

title: The mnist database of handwritten digits. http://yann

venue: lecun. com/exdb/mnist/,

authors:
H Brendan McMahan
Matthew Streeter

title: Adaptive bound optimization for online convex optimization

venue: In Proceedings of the 23rd Annual Conference on Learning Theory, pp

authors:
Mahesh Chandra Mukkamala
Matthias Hein

title: Variants of rmsprop and adagrad with logarithmic regret bounds

venue: In Proceedings of the 33rd International Conference on Machine Learning,

authors:
Sashank J Reddi
Satyen Kale
Sanjiv Kumar

title: On the convergence of adam and beyond

venue: In Proceedings of 6th International Conference on Learning Representations,

authors:
Noam Shazeer
Mitchell Stern

title: Adafactor: Adaptive learning rates with sublinear memory cost

venue: In Proceedings of the 35th International Conference on Machine Learning,

authors:
Tijmen Tieleman
Geoffrey Hinton

title: Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine

title: On the convergence proof of amsgrad and a new version

authors:
Kelvin Xu
Jimmy Ba
Ryan Kiros
Kyunghyun Cho
Aaron Courville
Ruslan Salakhudinov
Rich Zemel
Yoshua Bengio

title: Show, attend and tell: Neural image caption generation with visual attention

venue: In Proceedings of 32nd International Conference on Machine Learning,

title: Adadelta: an adaptive learning rate method

venue: arXiv preprint arXiv:1212.5701,

authors:
Jiawei Zhang
Limeng Cui
Fisher B

title: Gouza. Gadam: Genetic-evolutionary adam for deep neural network optimization

venue: arXiv preprint arXiv:1805.07500,

title: Online convex programming and generalized infinitesimal gradient ascent

venue: In Proceedings of the 20th International Conference on Machine Learning,

authors: AMSgrad Reddi

title: 2018) provide the following regret bound

venue: Reddi et al

authors: Recently Tran

venue: (Proof of Lemma

venue: To address this issue, Tran et al

heading: 1 INTRODUCTION

text:
Online Convex Optimization (OCO) is a well-established learning framework which has both theoretical and practical appeals (Shalev-Shwartz et al., 2012). It is performed in a sequence of consecutive rounds: In each round t, firstly a learner chooses a decision xt from a convex set D ⊆ Rd, at the same time, an adversary reveals a loss function ft(·) : D 7→ R, and consequently the learner suffers a loss ft(xt). The goal is to minimize regret, defined as the difference between the cumulative loss of the learner and that of the best decision in hindsight (Hazan et al., 2016):
R(T ) := T∑ t=1 ft(xt)−min x∈D T∑ t=1 ft(x).
The most classic algorithm for OCO is Online Gradient Descent (OGD) (Zinkevich, 2003), which attains an O( √ T ) regret. OGD iteratively performs descent step towards gradient direction with a predetermined step size, which is oblivious to the characteristics of the data being observed. As a result, its regret bound is data-independent, and can not benefit from the structure of data. To address this limitation, various of adaptive gradient methods, such as Adagrad (Duchi et al., 2011), RMSprop (Tieleman & Hinton, 2012) and Adadelta (Zeiler, 2012) have been proposed to exploit the geometry of historical data. Among them, Adam (Kingma & Ba, 2015), which dynamically adjusts the step size and the update direction by exponential average of the past gradients, has been extensively popular and successfully applied to many applications (Xu et al., 2015; Gregor et al., 2015; Kiros et al., 2015; Denkowski & Neubig, 2017; Bahar et al., 2017). Despite the outstanding performance, Reddi et al. (2018) pointed out that Adam suffers the non-convergence issue, and developed two modified versions, namely AMSgrad and AdamNC. These variants are equipped with data-dependent regret bounds, which are O( √ T ) in the worst case and become tighter when gradients are sparse 1.
∗Lijun Zhang is the corresponding author. 1We note that, as very recently pointed out by Tran et al. (2019), there still exists a minor theoretical flaw in the analysis of Reddi et al. (2018), and such issue in fact appears in many of recent variants of AMSgrad/AdamNC. In this paper, we provide a simple way to fix this problem. The details can be found in Appendix G.
While the theoretical behavior of Adam in convex cases becomes clear, it remains an open problem whether strong convexity can be exploited to achieve better performance. Such property arises, for instance, in support vector machines as well as other regularized learning problems, and it is wellknown that the vanilla OGD with an appropriately chosen step size enjoys a much better O(log T ) regret bound for strongly convex functions (Hazan et al., 2007). In this paper, we propose a variant of Adam adapted to strongly convex functions, referred to as SAdam. Our algorithm follows the general framework of Adam, yet keeping a faster decaying step size controlled by time-variant heperparameters to exploit strong convexity. Theoretical analysis demonstrates that SAdam achieves a data-dependent O(log T ) regret bound for strongly convex functions, which means that it converges faster than AMSgrad and AdamNC in such cases, and also enjoys a huge gain in the face of sparse gradients.
Furthermore, under a special configuration of heperparameters, the proposed algorithm reduces to the SC-RMSprop (Mukkamala & Hein, 2017), which is a variant of RMSprop algorithm for strongly convex functions. We provide an alternative proof for SC-RMSprop, and establish the first data-dependent logarithmic regret bound. Finally, we evaluate the proposed algorithm on strongly convex problems as well as deep networks, and the empirical results demonstrate the effectiveness of our method.
Notation. Throughout the paper, we use lower case bold face letters to denote vectors, lower case letters to denote scalars, and upper case letters to denote matrices. We use ‖ · ‖ to denote the `2-norm and ‖ · ‖∞ the infinite norm. For a positive definite matrix H ∈ Rd×d, the weighted `2-norm is defined by ‖x‖2H = x>Hx. The H-weighted projection ΠHD (x) of x onto D is defined by ΠHD (x) = arg miny∈D ‖y− x‖2H . We use gt to denote the gradient of ft(·) at xt. For vector sequence {vt}Tt=1, we denote the i-th element of vt by vt,i. For diagonal matrix sequence {Mt}Tt=1, we use mt,i to denote the i-th element in the diagonal of Mt. We use g1:t,i = [g1,i, · · · , gt,i] to denote the vector obtained by concatenating the i-th element of the gradient sequence {gt}Tt=1.

heading: 2 RELATED WORK

text:
In this section, we briefly review related work in online convex and strongly convex optimization.
In the literature, most studies are devoted to the minimization of regret for convex functions. Under the assumptions that the infinite norm of gradients and the diameter of the decision set are bounded, OGD with step size on the order of O(1/ √ t) (referred to as convex OGD) achieves a data-independent O(d √ T ) regret (Zinkevich, 2003), where d is the dimension. To conduct more informative updates, Duchi et al. (2011) introduce Adagrad algorithm, which adjusts the step size of OGD in a perdimension basis according to the geometry of the past gradients. In particular, the diagonal version of the algorithm updates decisions as
xt+1 = xt − α√ t Vt −1/2gt (1)
where α > 0 is a constant factor, Vt is a d× d diagonal matrix, and ∀i ∈ [d], vt,i = ( ∑t j=1 g 2 j,i)/t is the arithmetic average of the square of the i-th elements of the past gradients. Intuitively, while the step size of Adagrad, i.e., (α/ √ t)V −1/2 t , decreases generally on the order of O(1/ √ t) as that in convex OGD, the additional matrix V −1/2t will automatically increase step sizes for sparse dimensions in order to seize the infrequent yet valuable information therein. For convex functions, Adagrad enjoys an O( ∑d i=1 ‖g1:T,i‖) regret, which is O(d √ T ) in the worst case and becomes tighter when gradients are sparse.
Although Adagrad works well in sparse cases, its performance has been found to deteriorate when gradients are dense due to the rapid decay of the step size since it uses all the past gradients in the update (Zeiler, 2012). To tackle this issue, Tieleman & Hinton (2012) propose RMSprop, which alters the arithmetic average procedure with Exponential Moving Average (EMA), i.e.,
Vt = βVt−1 + (1− β)diag(gtg>t )
where β ∈ [0, 1] is a hyperparameter, and diag(·) denotes extracting the diagonal matrix. In this way, the weights assigned to past gradients decay exponentially so that the reliance of the update is
essentially limited to recent few gradients. Since the invention of RMSprop, many EMA variants of Adagrad have been developed (Zeiler, 2012; Kingma & Ba, 2015; Dozat, 2016). One of the most popular algorithms is Adam (Kingma & Ba, 2015), where the first-order momentum acceleration, shown in (2), is incorporated into RMSprop to boost the performance:
ĝt = β1ĝt−1 + (1− β1)gt (2) Vt = β2Vt−1 + (1− β2)diag(gtg>t ) (3) xt+1 = xt − α√ t Vt −1/2ĝt (4)
While it has been successfully applied to various practical applications, a recent study by Reddi et al. (2018) shows that Adam could fail to converge to the optimal decision even in some simple one-dimensional convex scenarios due to the potential rapid fluctuation of the step size. To resolve this issue, they design two modified versions of Adam. The first one is AMSgrad,
V̂t = max { V̂t−1, Vt } xt+1 = xt −
α√ t V̂ −1/2 t ĝt
where an additional element-wise maximization procedure is employed before the update of xt to ensure a stable step size. The other is AdamNC, where the framework of Adam remains unchanged, yet a time-variant β2 (i.e., β2t) is adopted to keep the step size under control. Theoretically, the two algorithms achieve data-dependentO( √ T ∑d i=1 vT,i+ ∑d i=1 ‖g1:T,i‖ log T ) andO( √ T ∑d i=1 vT,i+∑d
i=1 ‖g1:T,i‖) regrets respectively. In the worst case, they suffer O(d √ T log T ) and O(d √ T )
regrets respectively, and enjoy a huge gain when data is sparse.
Note that the aforementioned algorithms are mainly analysed in general convex settings and suffer at least O(d √ T ) regret in the worst case. For online strongly convex optimization, the classical OGD with step size proportional to O(1/t) (referred to as strongly convex OGD) achieves a dataindependent O(d log T ) regret (Hazan et al., 2007). Inspired by this, Mukkamala & Hein (2017) modify the update rule of Adagrad in (1) as follows
xt+1 = xt − α t Vt −1gt
so that the step size decays approximately on the order of O(1/t), which is similar to that in strongly convex OGD. The new algorithm, named SC-Adagrad, is proved to enjoy a data-dependent regret bound of O( ∑d i=1 log(‖g1:T,i‖2)), which is O(d log T ) in the worst case. They further extend this idea to RMSprop, and propose an algorithm named SC-RMSprop. However, as pointed out in Section 3, their regret bound for SC-RMSprop is in fact data-independent, and in this paper we provide the first data-dependent regret bound for this algorithm.
Very recently, several modifications of Adam adapted to non-convex settings have been developed (Chen et al., 2019; Basu et al., 2018; Zhang et al., 2018; Shazeer & Stern, 2018). However, to our knowledge, none of these algorithms are particularly designed for strongly convex functions, nor enjoy a logarithmic regret bound.

heading: 3 SADAM

text: In this section, we first describe the proposed algorithm, then state its theoretical guarantees, and finally compare it with the SC-RMSprop algorithm.

heading: 3.1 THE ALGORITHM

text:
Before proceeding to our algorithm, following previous studies, we introduce some standard definitions (Boyd & Vandenberghe, 2004) and assumptions (Reddi et al., 2018). Definition 1. A function f(·) : D 7→ R is λ-strongly convex if ∀x1, x2 ∈ D,
f(x1) ≥ f(x2) +∇f(x2)>(x1 − x2) + λ
2 ‖x1 − x2‖2. (5)
Algorithm 1 SAdam
1: Input: {β1t}Tt=1, {β2t}Tt=1, δ 2: Initialize: ĝ0 = 0, V̂0 = 0d×d, x1 = 0. 3: for t = 1, . . . , T do 4: gt = ∇ft(xt) 5: ĝt = β1tĝt−1 + (1− β1t)gt 6: Vt = β2tVt−1 + (1− β2t)diag(gtg>t ) 7: V̂t = Vt + δ t Id
8: xt+1 = ΠV̂tD ( xt − αt V̂ −1 t ĝt ) 9: end for
Assumption 1. The infinite norm of the gradients of all loss functions are bounded by G∞, i.e., their exists a constant G∞ > 0 such that maxx∈D ‖∇ft(x)‖∞ ≤ G∞ holds for all t ∈ [T ]. Assumption 2. The decision set D is bounded. Specifically, their exists a constant D∞ > 0 such that maxx1,x2∈D ‖x1 − x2‖∞ ≤ D∞.
We are now ready to present our algorithm, which follows the general framework of Adam and is summarized in Algorithm 1. In each round t, we firstly observe the gradient at xt (Step 4), then compute the first-order momentum ĝt (Step 5). Here β1t a time-variant hyperparameter. Next, we calculate the second-order momentum Vt by EMA of the square of past gradients (Step 6). This procedure is controlled by β2t, whose value will be discussed later. After that, we add a vanishing factor δt to the diagonal of Vt and get V̂t (Step 7), which is a standard technique for avoiding too large steps caused by small gradients in the beginning iterations. Finally, we update the decision by ĝt and V̂t, which is then projected onto the decision set (Step 8).
While SAdam is inspired by Adam, there exist two key differences: One is the update rule of xt in Step 8, and the other is the configuration of β2t in Step 6. Intuitively, both modifications stem from strongly convex OGD, and jointly result in a faster decaying yet under controlled step size which helps utilize the strong convexity while preserving the practical benefits of Adam. Specifically, in the first modification, we remove the square root operation in (4) of Adam, and update xt at Step 8 as follows
xt+1 = xt − α
t V̂ −1t ĝt. (6)
In this way, the step size used to update the i-th element of xt is αt v̂ −1 t,i , which decays in general on the order of O(1/t), and can still be automatically tuned in a per-feature basis via the EMA of the historical gradients.
The second modification is made to β2t, which determines the value of Vt and thus also controls the decaying rate of the step size. To help understand the motivation behind our algorithm, we first revisit Adam, where β2t is simply set to be constant, which, however, could cause rapid fluctuation of the step size, and further leads to the non-convergence issue. To ensure convergence, Reddi et al. (2018) propose that β2t should satisfy the following two conditions: Condition 1. ∀t ∈ [T ] and i ∈ [d],
√ tv
1/2 t,i α − √ t− 1v1/2t−1,i α ≥ 0.
Condition 2. For some ζ > 0 and ∀t ∈ [T ], i ∈ [d],√√√√t t∑ j=1 Πt−jk=1β2(t−k+1)(1− β2j)g2j,i ≥ 1 ζ √√√√ t∑ j=1 g2j,i.
The first condition implies that the difference between the inverses of step sizes in two consecutive rounds is positive. It is inherently motivated by convex OGD (i.e., OGD with step size α√
t , where
α > 0 is a constant factor), in which √ t
α − √ t− 1 α ≥ 0,∀t ∈ [T ]
is a key condition used in the analysis. We first modify Condition 1 by mimicking the behavior of strongly convex OGD as we are devoted to minimizing regret for strongly convex functions. In strongly convex OGD (Hazan et al., 2007), the step size at each round t is set as αt with α ≥ 1 λ for λ-strongly convex functions. Under this configuration, we have
t α − t− 1 α ≤ λ,∀t ∈ [T ]. (7)
Motivated by this, we propose the following condition for our SAdam, which is an analog to (7).
Condition 3. Their exists a constant C > 0 such that for any α ≥ Cλ , we have ∀t ∈ [T ] and i ∈ [d],
tvt,i α − (t− 1)vt−1,i α ≤ λ(1− β1). (8)
Note that the extra (1 − β1) in the righthand side of (8) is necessary because SAdam involves the first-order momentum in its update. Finally, since the step size of SAdam scales with 1/t rather than 1/ √ t in Adam, we modify Condition 2 accordingly as follows:
Condition 4. For some ζ > 0, ∀t ∈ [T ] and i ∈ [d],
t t∑ j=1 t−j∏ k=1 β2(t−k+1)(1− β2j)g2j,i ≥ 1 ζ t∑ j=1 g2j,i. (9)

heading: 3.2 THEORETICAL GUARANTEES

text:
In the following, we give a general regret bound when the two conditions are satisfied.
Theorem 1. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λstrongly convex. Let δ > 0, β1t = β1νt−1, where β1 ∈ [0, 1), ν ∈ [0, 1), and {β2t}Tt=1 ∈ [0, 1]T be a parameter sequence such that Conditions 3 and 4 are satisfied. Let α ≥ Cλ . The regret of SAdam satisfies
R(T ) ≤ dD 2 ∞δ
2α(1− β1) +
dβ1D 2 ∞(G 2 ∞ + δ)
2α(1− β1)(ν − 1)2 +
αζ (1− β1)3 d∑ i=1 log  1 ζδ T∑ j=1 g2j,i + 1  . (10) Remark 1. The above theorem implies that our algorithm enjoys an O( ∑d i=1 log(‖g1:T,i‖2)) regret bound, which is O(d log T ) in the worst case, and automatically becomes tighter whenever the gradients are small or sparse such that ‖g1:T,i‖2 G2∞T for some i ∈ [d]. The superiority of data-dependent bounds have been witnessed by a long list of literature, such as Duchi et al. (2011); Mukkamala & Hein (2017); Reddi et al. (2018). In the following, we give some concrete examples:
• Consider a one-dimensional sparse setting where non-zero gradient appears with probability c/T and c > 1 is a constant. Then E [ log (∑T
t=1 g 2 t,1
)] = O(log(c)), which is a constant
factor.
• Consider a high-dimensional sparse setting where in each dimension of gradient non-zero element appears with probability p = T (m−d)/d with m ∈ [1, d) being a constant. Then, E [∑d i=1 log (∑T j=1 g 2 j,i )] = O(m log T ), which is much tighter than O(d log T ).
Remark 2. In practice, first-order momentum is a powerful technique that can significantly boost the performance (Reddi et al., 2018), and our paper is the first to show that algorithms equipped with such technique can achieve logarithmic regret bound for strongly convex functions. However, since the regret bound of SAdam is data-dependent, it is difficult to rigorously analyse the influence of the first-order momentum parameter β1 as it affects all the gradients appearing in the last term of the regret of Theorem 1. We will further investigate this in the feature work. We note that the regret bounds of adaptive algorithms with first-order momentum (e.g., Reddi et al., 2018; Chen et al., 2019) all share a similar structure as our regret bound with respect to β1.
Next, we provide an instantiation of {β2t}Tt=1 such that Conditions 3 and 4 hold, and derive the following Corollary. Corollary 2. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λstrongly convex. Let δ > 0, β1t = β1νt−1 where ν, β1 ∈ [0, 1), and 1 − 1t ≤ β2t ≤ 1 − γ t , where γ ∈ (0, 1]. Then we have: 1. For any α ≥ (2−γ)G 2 ∞
λ(1−β1) , ∀t ∈ [T ] and i ∈ [d],
tvt,i α − (t− 1)vt−1,i α ≤ λ(1− β1).
2. For all t ∈ [T ] and j ∈ [d],
t t∑ j=1 t−j∏ k=1 β2(t−k+1)(1− β2j)g2j,i ≥ γ t∑ j=1 g2j,i.
Moreover, let α ≥ (2−γ)G 2 ∞
λ(1−β1) , and the regret of SAdam satisfies:
R(T ) ≤ dD 2 ∞δ
2α(1− β1) +
dβ1D 2 ∞(G 2 ∞ + δ)
2α(1− β1)(ν − 1)2 +
α γ(1− β1)3 d∑ i=1 log γ δ T∑ j=1 g2j,i + 1  . Furthermore, as a special case, by setting β1t = 0 and 1 − 1t ≤ β2t ≤ 1 − γ t , our algorithm reduces to SC-RMSprop (Mukkamala & Hein, 2017), which is a variant of RMSprop for strongly convex functions. Although Mukkamala & Hein (2017) have provided theoretical guarantees for this algorithm, we note that their regret bound is in fact data-independent. Specifically, the regret bound provided by Mukkamala & Hein (2017) takes the following form:
R(T ) ≤δdD 2 ∞
2α +
α
2γ d∑ i=1 log ( TvT,i δ + 1 ) + α γ d∑ i=1 (1− γ)(1 + log T ) infj∈[1,T ] jvj,i + δ . (11)
Focusing on the denominator of the last term in (11), we have
inf j∈[1,T ]
jvj,i + δ ≤ 1v1,i + δ ≤ G∞ + δ
thus α
γ d∑ i=1 (1− γ)(1 + log T ) infj∈[1,T ] jvj,i + δ ≥ dα γ (1− γ)(log T + 1) G∞ + δ
which implies that their regret bound is of order O(d log T ), and thus data-independent. In contrast, based on Corollary 2, we present a new regret bound for SC-RMSprop in the following, which is O( ∑d i=1 log(‖g1:T,i‖2)), and thus data-dependent.
Corollary 3. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λstrongly convex. Let δ > 0, β1t = 0, and 1− 1t ≤ β2t ≤ 1− γ t , where γ ∈ (0, 1]. Let α ≥ (2−γ)G2∞ λ . Then SAdam reduces to SC-RMSprop, and its regret satisfies
R(T ) ≤dD 2 ∞δ 2α + α γ d∑ i=1 log γ δ T∑ j=1 g2j,i + 1  . (12) Finally, we note that Mukkamala & Hein (2017) also consider a more general version of SC-RMSprop which uses a time-variant non-increasing δ for each dimension i. In Appendix D we introduce the δ-variant technique to our SAdam, and provide the corresponding theoretical guarantee.

heading: 4 EXPERIMENTS

text:
In this section, we present empirical results on optimizing strongly convex functions and training deep networks. More results can be found Appendix.
Algorithms. In both experiments, we compare the following algorithms:
• SC-Adagrad (Mukkamala & Hein, 2017), with step size αt = α/t. • SC-RMSprop (Mukkamala & Hein, 2017), with step size αt = α/t and βt = 1− 0.9t . • Adam (Kingma & Ba, 2015) and AMSgrad (Reddi et al., 2018), both with β1 = 0.9, β2 = 0.999, αt = α/ √ t for convex problems and time-invariant αt = α for non-convex
problems. • AdamNC (Reddi et al., 2018), with β1 = 0.9, β2t = 1− 1/t, and αt = α/ √ t for convex
problems and a time-invariant αt = α for non-convex problems. • Online Gradient Descent (OGD), with step size αt = α/t for strongly convex problems and
a time-invariant αt = α for non-convex problems. • Our proposed SAdam, with β1 = 0.9, β2t = 1− 0.9t .
For Adam, AdamNC and AMSgrad, we choose δ = 10−8 according to the recommendations in their papers. For SC-Adagrad and SC-RMSprop, following Mukkamala & Hein (2017), we choose a time-variant δt,i = ξ2e−ξ1tvt,i for each dimension i, with ξ1 = 0.1, ξ2 = 1 for convex problems and ξ1 = 0.1, ξ2 = 0.1 for non-convex problems. For our SAdam, since the removing of the square root procedure and very small gradients may cause too large step sizes in the beginning iterations, we use a rather large δ = 10−2 to avoid this problem. To conduct a fair comparison, for each algorithm, we choose α from the set {0.1, 0.01, 0.001, 0.0001} and report the best results. Datasets. In both experiments, we examine the performances of the aforementioned algorithms on three widely used datasets: MNIST (60000 training samples, 10000 test samples), CIFAR10 (50000 training samples, 10000 test samples), and CIFAR100 (50000 training samples, 10000 test samples). We refer to LeCun (1998) and Krizhevsky (2009) for more details of the three datasets.

heading: 4.1 OPTIMIZING STRONGLY CONVEX FUNCTIONS

text:
In the first experiment, we consider the problem of mini-batch `2-regularized softmax regression, which belongs to the online strongly convex optimization framework. Let K be the number of classes and m be the batch size. In each round t, firstly a mini-batch of training samples {(xm, ym)}mi=1 arrives, where yi ∈ [K],∀i ∈ [m]. Then, the algorithm predicts parameter vectors {wi, bi}Ki=1, and suffers a loss which takes the following form:
J(w, b) =− 1 m m∑ i=1 log
( ew > yi
xi+byi∑K j=1 e w>j xi+bj
) + λ1
K∑ k=1 ‖wk‖2 + λ2 K∑ k=1 b2k.
The value of λ1 and λ2 are set to be 10−2 for all experiments. The regret (in log scale) v.s. dataset proportion is shown in Fig. 1. It can be seen that our SAdam outperforms other methods across all the considered datasets. Besides, we observe that data-dependent strongly convex methods such as SC-Adagrad, SC-RMSprop and SAdam preform better than algorithms for general convex functions such as Adam, AMSgrad and AdamNC. Finally, OGD has the overall highest regret on all three datasets.

heading: 4.2 TRAINING DEEP NETWORKS

text: Following Mukkamala & Hein (2017), we also conduct experiments on a 4-layer CNN, which consists of two convolutional layers (each with 32 filters of size 3 × 3), one max-pooling layer (with a 2 × 2 window and 0.25 dropout), and one fully connected layer (with 128 hidden units and 0.5 dropout). We employ ReLU function as the activation function for convolutional layers and softmax function as the activation function for the fully connected layer. The loss function is the cross-entropy. The training loss v.s. epoch is shown in Fig. 2, and the testing accuracy v.s. epoch is presented in Fig. 4. As can be seen, our SAdam achieves the lowest training loss on the three data sets. Moreover, this performance gain also translates into good performance on testing accuracy. The experimental results show that although our proposed SAdam is designed for strongly convex functions, it could lead to superior practical performance even in some highly non-convex cases such as deep learning tasks.

heading: 5 CONCLUSION AND FUTURE WORK

text:
In this paper, we provide a variant of Adam adapted to strongly convex functions. The proposed algorithm, namely SAdam, follows the general framework of Adam, while keeping a step size decaying in general on the order of O(1/t) and controlled by data-dependent heperparameters to exploit strong convexity. Theoretical analysis shows that SAdam achieves a data-dependent O(d log T ) regret bound for strongly convex functions, which means that it converges much faster than Adam, AdamNC, and AMSgrad in such cases, and can enjoy a huge gain in the face of sparse gradients. In addition, we also provide the first data-dependent logarithmic regret bound for SCRMSprop. Finally, we test the proposed algorithm on optimizing strongly convex functions as well as training deep networks, and the empirical results demonstrate the effectiveness of our method.
Since SAdam enjoys a data-dependent O(d log T ) regret for online strongly convex optimization, it can be easily translated into a data-dependent O(d log T/T ) convergence rate for stochastic strongly convex optimization (SSCO) by using the online-to-batch conversion (Kakade & Tewari, 2009). However, this rate is not optimal for SSCO, and it is sill an open problem how to achieve a datadependent O(d/T ) convergence rate for SSCO. Recent development on adaptive gradient method (Chen et al., 2018) has proved that Adagrad combined with the multi-stage scheme (Hazan & Kale, 2014) can achieve this rate, but it is highly non-trivial to extend this technique to SAdam, and we leave it as a future work.

heading: 6 ACKNOWLEDGEMENT

text: This work was partially supported by NSFC (61976112), NSFC-NRF Joint Research Project (61861146001), and the Collaborative Innovation Center of Novel Software Technology and Industrialization.

heading: A PROOF OF THEOREM 1

text:
From Definition 1, we can upper bound regret as
R(T ) = T∑ t=1 ft(xt)− T∑ t=1 ft(x∗) (5) ≤ T∑ t=1 g>t (xt − x∗)− λ 2 ‖xt − x∗‖2 (13)
where x∗ := minx∈D ∑T t=1 ft(x) is the best decision in hindsight. On the other hand, by the update rule of xt+1 in Algorithm 1, we have
‖xt+1 − x∗‖2V̂t = ∥∥∥ΠV̂tD (xt − αtV̂ −1t ĝt)− x∗∥∥∥2
V̂t
≤‖xt − αtV̂ −1t ĝt − x∗‖2V̂t =− 2αtĝ>t (xt − x∗) + ‖xt − x∗‖2V̂t + α 2 t ||ĝt||2V̂ −1t
=− 2αt ( β1tĝt−1 + (1− β1t)gt )> (xt − x∗)
+ ‖xt − x∗‖2V̂t + α 2 t ||ĝt||2V̂ −1t
(14)
where αt := α/t, and the inequality is due to the following lemma, which implies that the weighted projection procedure is non-expansive. Lemma 1. (McMahan & Streeter, 2010) Let A ∈ Rd×d be a positive definite matrix and D ⊆ Rd be a convex set. Then we have, ∀x, y ∈ Rd,
‖ΠAD(x)−ΠAD(y)‖A ≤ ‖x− y‖A. (15)
Rearranging (14), we have
g>t (xt − x∗) ≤ ‖xt − x∗‖2V̂t − ‖xt+1 − x∗‖ 2 V̂t
2αt(1− β1t) + β1t 1− β1t ĝ>t−1(x∗ − xt)
+ αt
2(1− β1t) ‖ĝt‖2V̂ −1t
≤ ‖xt − x∗‖2V̂t − ‖xt+1 − x∗‖ 2 V̂t
2αt(1− β1t) + β1t 1− β1t ĝ>t−1(x∗ − xt)
+ αt
2(1− β1) ‖ĝt‖2V̂ −1t
(16)
where the last inequality is due to β1t ≤ β1. We proceed to bound the second term of the inequality above. When t ≥ 2, by Young’s inequality and the definition of β1t, we get
β1t 1− β1t ĝ>t−1(x∗ − xt) ≤ αt−1β1t 2(1− β1t) ‖ĝt−1‖2V̂ −1t−1 + β1t 2αt−1(1− β1t) ‖xt − x∗‖2V̂t−1
≤ αt−1 2(1− β1) ‖ĝt−1‖2V̂ −1t−1 + β1t 2αt−1(1− β1t) ‖xt − x∗‖2V̂t−1 .
(17)
When t = 1, this term becomes 0 since ĝ0 = 0 in Algorithm 1. Plugging (16) and (17) into (13), we get the following inequality, of which we divide the righthand side into three parts and upper bound each of them one by one. R(T )≤ T∑ t=1 ( ‖xt − x∗‖2V̂t − ‖xt+1 − x∗‖ 2 V̂t 2αt(1− β1t) − λ 2 ‖xt − x∗‖2 ) ︸ ︷︷ ︸
P1
+ 1
2(1− β1) T∑ t=2 αt−1‖ĝt−1‖2V̂ −1t−1 + ∑T t=1 αt‖ĝt‖2V̂ −1t 2(1− β1)︸ ︷︷ ︸
P2
+ T∑ t=2 β1t 2αt−1(1− β1t)
‖xt − x∗‖2V̂t−1︸ ︷︷ ︸ P3 .
To bound P1, we have
P1 = ‖x1 − x∗‖2V̂1 2α1(1− β1) − ‖xT+1 − x∗‖2VT 2αT (1− β1T )︸ ︷︷ ︸
≤0
− T∑ t=1 ( λ 2 ‖xt − x∗‖2 )
+ T∑ t=2 ( ‖xt − x∗‖2V̂t 2αt(1− β1t) − ‖xt − x∗‖2V̂t−1 2αt−1(1− β1(t−1)) )
≤ ‖x1 − x∗‖2V̂1 2α1(1− β1) − T∑ t=1 ( λ 2 ‖xt − x∗‖2 ) + T∑ t=2
1
1− β1t
( ‖xt − x∗‖2V̂t
2αt − ‖xt − x∗‖2V̂t−1 2αt−1
)
= T∑ t=2
1 2α(1− β1t) ( t‖xt − x∗‖2V̂t − (t− 1)‖xt − x∗‖ 2 V̂t−1 − λα(1− β1t)‖xt − x∗‖2 ) + ( ‖x1 − x∗‖2V̂1 2α1(1− β1) − λ 2 ‖x1 − x∗‖2
) (18)
where the inequality is derived from β1(t−1) ≥ β1t. For the first term in the last equality of (18), we have
t‖xt − x∗‖2V̂t − (t− 1)‖xt − x∗‖ 2 V̂t−1 − λα(1− β1t)‖xt − x∗‖2
= d∑ i=1 (xt,i − x∗,i)2(tv̂t,i − (t− 1)v̂t−1,i − λα(1− β1t))
= d∑ i=1 (xt,i − x∗,i)2(tvt,i − (t− 1)vt−1,i − λα(1− β1t))
(8) ≤ d∑ i=1 (xt,i − x∗,i)2(αλ(1− β1)− λα(1− β1t)) ≤ 0
(19)
where the second equality is because v̂t,i = vt,i + δt , and the second inequality is due to 1− β1 ≤ 1− β1t. For the second term of (18), we have(
‖x1 − x∗‖2V̂1 2α1(1− β1) − λ 2 ‖x1 − x∗‖2
) =
d∑ i=1 (x1,i − x∗,i)2 ( v̂1,i − λα(1− β1) 2α(1− β1) )
= d∑ i=1 (x1,i − x∗,i)2 ( v1,i − λα(1− β1) + δ 2α(1− β1) )
≤ d∑ i=1 (x1,i − x∗,i)2 (
δ
2α(1− β1) ) ≤ dD 2 ∞δ
2α(1− β1)
(20)
where first inequality is due to Condition 3, and the second inequality follows from Assumption 2. Combining (18), (19) and (20), we get
P1 ≤ dD2∞δ
2α(1− β1) . (21)
To bound P2, we introduce the following lemma. Lemma 2. The following inequality holds
T∑ t=1 αt‖ĝt‖2V̂ −1t ≤ αζ (1− β1)2 d∑ i=1 log  1 ζδ T∑ j=1 g2j,i + 1  . (22)
By Lemma 2, we have
P2 = 1
2(1− β1) T∑ t=2 αt−1‖ĝt−1‖2V̂ −1t−1 + ∑T t=1 αt‖ĝt‖2V̂ −1t 2(1− β1)
≤ 1 (1− β1) T∑ t=1 αt‖ĝt‖2V̂ −1t
(22) ≤ αζ (1− β1)3 d∑ i=1 log  1 ζδ T∑ j=1 g2j,i + 1  . (23)
Finally, we turn to upper bound P3:
P3 = T∑ t=2 β1t 2αt−1(1− β1t) ‖xt − x∗‖2V̂t−1
= d∑ i=1 T∑ t=2 β1t 2α(1− β1t) (xt,i − x∗,i)2(t− 1)v̂t−1,i
≤D 2 ∞(G 2 ∞ + δ)
2α
d∑ i=1 T∑ t=1 β1t 1− β1t t
≤β1D 2 ∞(G 2 ∞ + δ)
2α
d∑ i=1 T∑ t=1 νt−1 1− β1 t
= β1D
2 ∞(G 2 ∞ + δ)
2α(1− β1) d∑ i=1 T−1∑ t=0
νt(t+ 1)︸ ︷︷ ︸ P ′3 .
To further bound P ′3, following Bock et al. (2019), we have
P ′3 = T−1∑ t=0 νtt+ νt
=
( (T − 1)νT+1 − TνT + ν
(ν − 1)2 +
1− νT
1− ν ) =
1− T (νT − νT+1)− νT (1− ν)2
≤ 1 (1− ν)2
(24)
where the inequality follows from νT ≥ νT+1. Thus,
P3 ≤ dβ1D
2 ∞(G 2 ∞ + δ)
2α(1− β1)(ν − 1)2 . (25)
We complete the proof by combining (21), (23) and (25).

heading: B PROOF OF COROLLARY 2

text:
For the first condition, we have
tvt,i − (t− 1)vt−1,i =tβ2tvt−1,i + t(1− β2t)g2t,i − (t− 1)vt−1,i ≤t (
1− γ t
) vt−1,i + t 1
t g2t,i − (t− 1)vt−1,i
≤(t− γ − (t− 1))vt−1,i +G2∞ ≤(2− γ)G2∞
(26)
where the first inequality is derived from the definition of β2t, the second and the third inequalities are due to Assumption 1. Based on (26), for any α ≥ (2−γ)G 2 ∞
λ(1−β1) , we have tvt,i α − (t−1)vt−1,i α ≤ λ(1− β1)
holds for all t ∈ [T ] and i ∈ [d]. For the second condition, we have
t t∑ j=1 t−j∏ k=1 β2(t−k+1) (1− β2j) g2j,i ≥t t∑ j=1 t−j∏ k=1 ( 1− 1 t− k + 1 ) γ j g2j,i
=t t∑ j=1 t−j∏ k=1 t− k t− k + 1 γ j g2j,i
=t t∑ j=1 j t γ j g2j,i
=γ t∑ j=1 g2j,i
(27)
where the inequality follows from βt ≥ 1− 1t and 1− βt ≥ γ t .

heading: C PROOF OF LEMMA 2

text:
We begin with the following lemma that is central to our analysis.
Lemma 3. For all i ∈ [d] and t ∈ [T ], we have
T∑ j=1 g2j,i∑j k=1 g 2 k,i + ζδ ≤ log
(∑T j=1 g 2 j,i
ζδ + 1
) . (28)
Proof. For any a ≥ b > 0, the inequality 1 + x ≤ ex implies that
1 a (a− b) ≤ log a b . (29)
Let m0 = ζδ, and mj = ∑j k=1 g 2 k,i + ζδ > 0. By (29), we have
g2j,i∑j k=1 g 2 k,i + ζδ = mj −mj−1 mj ≤ log mj mj−1 .
Summing over 1 to T , we have
T∑ j=1 g2j,i∑j k=1 g 2 k,i + ζδ ≤ log mt m0 = log
(∑T j=1 g 2 j,i
ζδ + 1
) .
Now we turn to the proof of Lemma 2. First, expending the last term in the summation by the update rule of Algorithm 1, we get
αT ‖ĝT ‖2V̂ −1T = αT d∑ i=1 ĝ2T,i vT,i + δ T = α d∑ i=1
(∑T j=1(1− β1j) ∏T−j k=1 β1(T−k+1)gj,i )2 T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δ . (30)
The above equality can be further bounded as
αT ‖ĝT ‖2V̂ −1T ≤α d∑ i=1
(∑T j=1 ∏T−j k=1 β1(T−k+1)gj,i )2 T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δ
≤α d∑ i=1
(∑T j=1 ∏T−j k=1 β1(T−k+1) )(∑T j=1 ∏T−j k=1 β1(T−k+1)g 2 j,i ) T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δ
≤α d∑ i=1
(∑T j=1 β T−j 1 )(∑T j=1 ∏T−j k=1 β1(T−k+1)g 2 j,i ) T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δ
≤ α (1− β1) d∑ i=1
∑T j=1 β T−j 1 g 2 j,i
T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δ
(9) ≤ αζ
(1− β1) d∑ i=1
∑T j=1 β T−j 1 g
2 j,i∑T
j=1 g 2 j,i + ζδ
≤ αζ (1− β1) d∑ i=1 T∑ j=1 βT−j1 g2j,i∑j k=1 g 2 k,i + ζδ
(31)
where the first inequality is due to 1− β1j ≤ 1, the second inequality follows from Cauchy-Schwarz inequality, the third inequality is due to β1t ≤ β1. Let rj = g2j,i/( ∑j k=1 g 2 k,i + ζδ). Using similar arguments for all time steps and summing over 1 to T , we have T∑ t=1 αt‖ĝt‖2V̂ −1t ≤ αζ (1− β1) d∑ i=1 T∑ t=1 t∑ j=1 βt−j1 rj
= αζ
(1− β1) d∑ i=1 T∑ j=1 T−j∑ l=0 βl1rj
= αζ
(1− β1) d∑ i=1 T∑ j=1
∑T−j l=0 β l 1g
2 j,i∑j
k=1 g 2 k,i + ζδ
≤ αζ (1− β1)2 d∑ i=1 T∑ j=1 g2j,i∑j k=1 g 2 k,i + ζδ
(28) ≤ αζ (1− β1)2 d∑ i=1 log
(∑T j=1 g 2 j,i
ζδ + 1
) .
(32)

heading: D SADAM WITH A DECAYING REGULARIZATION FACTOR

text:
Algorithm 2 SAdam with time-variant δt (SAdamD)
1: Input: {β1t}Tt=1, {β2t}Tt=1, {δt}Tt=1 2: Initialize: ĝ0 = 0, V̂0 = 0d×d, x1 = 0. 3: for t = 1, . . . , T do 4: gt = ∇ft(xt) 5: ĝt = β1tĝt−1 + (1− β1t)gt 6: Vt = β2tVt−1 + (1− β2t)diag(gtg>t ) 7: V̂t = Vt + diag ( δt t
) 8: xt+1 = ΠV̂tD ( xt − αt V̂ −1 t ĝt
) 9: end for
In this section, we establish a generalized version of SAdam, which employs a time-variant regularization factor δt,i for each dimension i, instead of a fixed one for all i ∈ [d] and t ∈ [T ] as in the original SAdam. The algorithm is referred to as SAdamD and summarized in Algorithm 2. It can be seen that
our SAdamD reduces to SC-RMSprop with time-variant δt when β1t = 0 and 1− 1t ≤ β2t ≤ 1− γ t . For SAdamD, we prove the following theoretical guarantee:
Theorem 4. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λ-strongly convex. Let {δt,i}Tt=1 ∈ (0, 1]T be a non-increasing sequence for all i ∈ [d], β1t = β1νt−1 where β1 ∈ [0, 1), ν ∈ [0, 1), and {β2t}Tt=1 ∈ [0, 1]T be a parameter sequence such that Conditions 3 and 4 are satisfied. Let α ≥ Cλ . The regret of SAdamD satisfies
R(T ) ≤ D2∞
∑d i=1 δ1,i
2α(1− β1) +
αζ (1− β1)3 d∑ i=1 log  1 ζδT,i T∑ j=1 g2j,i + 1 + β1D2∞ ( dG2∞ + ∑d i=1 δ1,i ) 2α(1− β1)(ν − 1)2 .
(33)
By setting β1t = 0 and 1 − 1t ≤ β2t ≤ 1 − γ t , we can derive the following regret bound for SC-RMSprop:
Corollary 5. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λstrongly convex. Let {δt,i}Tt=1 ∈ (0, 1]T be a non-increasing sequence for all i ∈ [d], and 1− 1t ≤ β2t ≤ 1− γt , where γ ∈ (0, 1]. Let α ≥ (2−γ)G2∞ λ . Then SAdamD reduces to SC-RMSprop, and the regret satisfies
R(T ) ≤ D2∞
∑d i=1 δ1,i
2α + α γ d∑ i=1 log  γ δT,i T∑ j=1 g2j,i + 1  . (34) Finally, we provide an instantiation of δt and derive the following Corollary.
Corollary 6. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λstrongly convex. Let δt,i = ξ21+ξ1 ∑t j=1 g 2 j,i
, where ξ2 ∈ (0, 1] and ξ1 ≥ 0 are hypeparameters. Then we have δt,i ∈ (0, 1] and is non-increasing ∀i ∈ [d], t ∈ [T ]. Let 1 − 1t ≤ β2t ≤ 1 − γ t , where γ ∈ (0, 1], and α ≥ (2−γ)G 2 ∞
λ . Then SAdamD reduces to SC-RMSprop, and the regret satisfies
R(T ) ≤dD 2 ∞ξ2 2α + α γ d∑ i=1 log γ T∑ j=1 g2j,i + ξ2 + α γ d∑ i=1 log ξ1 ξ2 T∑ j=1 g2j,i + 1 ξ2  . (35)

heading: E PROOF OF THEOREM 4

text:
By similar arguments as in the proof of Theorem 1, we can upper bound regret as R(T )≤ T∑ t=1 ( ‖xt − x∗‖2V̂t − ‖xt+1 − x∗‖ 2 V̂t 2αt(1− β1t) − λ 2 ‖xt − x∗‖2 ) ︸ ︷︷ ︸
P1
+ 1
2(1− β1) T∑ t=2 αt−1‖ĝt−1‖2V̂ −1t−1 + ∑T t=1 αt‖ĝt‖2V̂ −1t 2(1− β1)︸ ︷︷ ︸
P2
+ T∑ t=2 β1t 2αt−1(1− β1t)
‖xt − x∗‖2V̂t−1︸ ︷︷ ︸ P3 .
To bound P1, based on (18), we have
P1 ≤ T∑ t=2
1 2α(1− β1t) ( t‖xt − x∗‖2V̂t − (t− 1)‖xt − x∗‖ 2 V̂t−1 − λα(1− β1t)‖xt − x∗‖2 ) + ( ‖x1 − x∗‖2V̂1 2α1(1− β1) − λ 2 ‖x1 − x∗‖2 ) . (36)
For the first term in (36), we have
t‖xt − x∗‖2V̂t − (t− 1)‖xt − x∗‖ 2 V̂t−1 − λα(1− β1t)‖xt − x∗‖2
= d∑ i=1 (xt,i − x∗,i)2(tv̂t,i − (t− 1)v̂t−1,i − λα(1− β1t))
= d∑ i=1 (xt,i − x∗,i)2(tvt,i − (t− 1)vt−1,i − λα(1− β1t) + δt,i − δt−1,i)
≤ d∑ i=1 (xt,i − x∗,i)2(λα(1− β1)− λα(1− β1t)︸ ︷︷ ︸ ≤0 + δt,i − δt−1,i︸ ︷︷ ︸ ≤0 )
≤0
(37)
For the second term of (36), we have
( ‖x1 − x∗‖2V̂1 2α1(1− β1) − λ 2 ‖x1 − x∗‖2 ) = d∑ i=1 (x1,i − x∗,i)2 ( v̂1,i − λα(1− β1) 2α(1− β1) )
= d∑ i=1 (x1,i − x∗,i)2 ( v1,i − λα(1− β1) + δ1,i 2α(1− β1) )
≤ D2∞
∑d i=1 δ1,i
2α(1− β1)
(38)
where the inequality follows from Condition 3. Combining (36), (37) and (38), we have
P1 ≤ D2∞
∑d i=1 δ1,i
2α(1− β1) . (39)
To bound P2, we first introduce the following lemma.
Lemma 4. The following inequality holds
T∑ t=1 αt‖ĝt‖2V̂ −1t ≤ αζ (1− β1)2 d∑ i=1 log  1 ζδT,i T∑ j=1 g2j,i + 1  . (40)
The proof of Lemma 4 can be found in Appendix F. Based on Lemma 4, we have
P2 = 1
2(1− β1) T∑ t=2 αt−1‖ĝt−1‖2V̂ −1t−1 + ∑T t=1 αt‖ĝt‖2V̂ −1t 2(1− β1)
≤ 1 (1− β1) T∑ t=1 αt‖ĝt‖2V̂ −1t
(40) ≤ αζ (1− β1)3 d∑ i=1 log  1 ζδT,i T∑ j=1 g2j,i + 1  . (41)
Finally, we turn to upper bound P3:
P3 ≤ d∑ i=1 T∑ t=1 β1t 2α(1− β1t) (xt,i − x∗,i)2tv̂t,i
≤ D 2 ∞
2α d∑ i=1 T∑ t=1 β1t 1− β1t t(G2∞ + δ1,i)
≤ β1D 2 ∞
2α d∑ i=1 T∑ t=1 νt−1 1− β1 t(G2∞ + δ1,i)
= β1D
2 ∞
2α d∑ i=1 (G2∞ + δ1,i) 1− β1 T−1∑ t=0 νt(t+ 1)
(24) ≤ β1D 2 ∞
2α d∑ i=1 (G2∞ + δ1,i) (1− β1)(ν − 1)2
= β1D
2 ∞(dG 2 ∞ + ∑d i=1 δ1,i)
2α(1− β1)(ν − 1)2 .
(42)
We finish the proof by combining (39), (41) and (42).

heading: F PROOF OF LEMMA 4

text:
Expending the last term in the summation by using the update rule of Algorithm 2, we have
αT ‖ĝT ‖2V̂ −1T =αT d∑ i=1
ĝ2T,i
vT,i + δT,i T
= α d∑ i=1
(∑T j=1(1− β1j) ∏T−j k=1 β1(T−k+1)gj,i )2 T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δT,i . (43)
The above equality can be further bounded as
αT ‖ĝT ‖2V̂ −1T ≤α d∑ i=1
(∑T j=1 ∏T−j k=1 β1(T−k+1) )(∑T j=1 ∏T−j k=1 β1(T−k+1)g 2 j,i ) T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δT,i
≤α d∑ i=1
(∑T j=1 β T−j 1 )(∑T j=1 ∏T−j k=1 β1(T−k+1)g 2 j,i ) T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δT,i
≤ α (1− β1) d∑ i=1
∑T j=1 β T−j 1 g 2 j,i
T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δT,i
(9) ≤ αζ
(1− β1) d∑ i=1
∑T j=1 β T−j 1 g
2 j,i∑T
j=1 g 2 j,i + ζδT,i
≤ αζ (1− β1) d∑ i=1 T∑ j=1 βT−j1 g2j,i∑j k=1 g 2 k,i + ζδT,i .
(44)
The first inequality follows from Cauchy-Schwarz inequality and 1 − β1t ≤ 1, and the second inequality is due to β1t ≤ β1. Let rj =
g2j,i∑j k=1 g 2 k,i+ζδT,i . By using similar arguments as in (32), we
have
T∑ t=1 αt‖ĝt‖2V̂ −1t ≤ αζ (1− β1) d∑ i=1 T∑ t=1 t∑ j=1 βT−j1 g2j,i∑j k=1 g 2 k,i + ζδt,i
≤ αζ (1− β1) d∑ i=1 T∑ t=1 t∑ j=1 βT−j1 g2j,i∑j k=1 g 2 k,i + ζδT,i
= αζ
(1− β1) d∑ i=1 T∑ t=1 t∑ j=1 rj
≤ αζ (1− β1) d∑ i=1 T∑ j=1
∑T−j l=0 β l 1g
2 j,i∑j
k=1 g 2 k,i + ζδT,i
≤ αζ (1− β1)2 d∑ i=1 T∑ j=1 g2j,i∑j k=1 g 2 k,i + ζδT,i
(28) ≤ αζ (1− β1)2 d∑ i=1 log  1 ζδT,i T∑ j=1 g2j,i + 1  .
(45)

heading: G ON THE CONVERGENCE OF AMSGRAD

text:
In this section, we firstly provide the AMSgrad algorithm and its theoretical guarantees (Reddi et al., 2018), then state a theoretical flaw in their analysis revealed by Tran et al. (2019), and finally propose a simple solution to fix this problem.
The AMSgrad algorithm developed in Reddi et al. (2018) is summarized in Algorithm 3.
Algorithm 3 AMSgrad
1: Input: {β1t}Tt=1, β2 2: Initialize: ĝ0 = 0, V̂0 = 0d×d, x1 = 0. 3: for t = 1, . . . , T do 4: gt = ∇ft(xt) 5: ĝt = β1tĝt−1 + (1− β1t)gt 6: Vt = β2Vt−1 + (1− β2)diag(gtg>t ) 7: V̂t = max{Vt, V̂t−1}
8: xt+1 = Π √ V̂t
D ( xt − αtV̂ −1/2t ĝt ) , where αt = α√t
9: end for
For AMSgrad, Reddi et al. (2018) provide the following regret bound.
Theorem 7 (Theorem 4 in Reddi et al. (2018), problematic). Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are convex. Let δ > 0, β1 > 0, β1t ≤ β1, and γ = β1√β2 ≤ 1. The regret of AMSgrad satisfies
R(T ) ≤ D 2 ∞ √ T
α(1− β1) d∑ i=1 v̂ 1/2 T,i + D2∞ 2(1− β1) T∑ t=1 d∑ i=1 β1tv̂ 1/2 t,i αt + α √ 1 + log T
(1− β1)2(1− γ) √ (1− β2) d∑ i=1 ‖g1:T,i‖.
(46)
Recently, Tran et al. (2019) point out a mistake in the proof of Theorem 7. Specifically, in Reddi et al. (2018), the following inequality is utilized (Proof of Lemma 2, Page 18):
T∑ t=1 [ 1 2αt(1− β1t) [ ‖V̂ 1/4t (xt − x∗)‖2 − ‖V̂ 1/4 t (xt+1 − x∗)‖2 ] +
β1t 2αt(1− β1t)
‖V̂ 1/4t (xt − x∗)‖2 ] + α √ 1 + log T
(1− β1)2(1− γ) √ (1− β2) d∑ i=1 ‖g1:T,i‖
≤ 1 2α1(1− β1) ‖V̂ 1/4t (x1 − x∗)‖2 + 1 2(1− β1) T∑ t=2
[ ‖V̂ 1/4t (xt − x∗)‖2
αt − ‖V̂ 1/4t−1 (xt − x∗)‖2 αt−1
]
+ T∑ t=1 [ β1t 2αt(1− β1) ‖V̂ 1/4t (xt − x∗)‖2 ] +
α √ 1 + log T
(1− β1)2(1− γ)( √ 1− β2) d∑ i=1 ‖g1:T,i‖
(47)
which, however, may not hold. To see this, we note that essentially (47) uses
T∑ t=1
1
2αt(1− β1t)
[ ‖V̂ 1/4t (xt − x∗)‖2 − ‖V̂ 1/4 t (xt+1 − x∗)‖2 ] ≤ 1
(1− β1) T∑ t=1 1 2αt [ ‖V̂ 1/4t (xt − x∗)‖2 − ‖V̂ 1/4 t (xt+1 − x∗)‖2 ] (48)
which holds only if β1t ≤ β1 and ‖V̂ 1/4t (xt − x∗)‖2 − ‖V̂ 1/4 t (xt+1 − x∗)‖2 is non-negative. However, as empirically shown by Tran et al. (2019), the letter requirement can be violated in some counterexamples. Note that similar problems exist in many recent proposed Adam variants. To address this issue, Tran et al. (2019) establish a new convergence proof of AMSGrad, which indicates an O(d √ T ) data-independent regret bound. Moreover, as an alternative, they also propose a variant of AMSgrad, called AdamX, which alters the stricture of AMSgrad to force the inequality been satisfied. For AdamX, they also give a new theoretical analysis and an O(d √ T ) data-independent regret bound.
In this paper, we find out that the above problem can be solved by simply configuring β1t of AMSgrad in a non-increasing manner, i.e., ∀t ≥ 2, β1t ≤ β1(t−1). Specifically, when β1t is non-increasing, we can rewrite (47) as
T∑ t=1 [ 1 2αt(1− β1t) [ ‖V̂ 1/4t (xt − x∗)‖2 − ‖V̂ 1/4 t (xt+1 − x∗)‖2 ] +
β1t 2αt(1− β1t)
‖V̂ 1/4t (xt − x∗)‖2 ] + α √ 1 + log T
(1− β1)2(1− γ) √ (1− β2) T∑ i=1 ‖g1:T,i‖
≤ 1 2α1(1− β1) ‖V̂ 1/41 (x1 − x∗)‖2 + 1 2 T∑ t=2
[ ‖V̂ 1/4t (xt − x∗)‖2
αt(1− β1t) − ‖V̂ 1/4t−1 (xt − x∗)‖2 αt−1(1− β1(t−1))
]
+ T∑ t=1 [ β1t 2αt(1− β1) ‖V̂ 1/4t (xt − x∗)‖2 ] +
α √ 1 + log T
(1− β1)2(1− γ)( √ 1− β2) d∑ i=1 ‖g1:T,i‖
≤ 1 2α1(1− β1) ‖V̂ 1/41 (x1 − x∗)‖2 + 1 2 T∑ t=2
[ ‖V̂ 1/4t (xt − x∗)‖2
αt(1− β1t) − ‖V̂ 1/4t−1 (xt − x∗)‖2 αt−1(1− β1t)
]
+ T∑ t=1 [ β1t 2αt(1− β1) ‖V̂ 1/4t (xt − x∗)‖2 ] +
α √ 1 + log T
(1− β1)2(1− γ)( √ 1− β2) d∑ i=1 ‖g1:T,i‖
≤ 1 2α1(1− β1) ‖V̂ 1/41 (x1 − x∗)‖2 + 1 2(1− β1) T∑ t=2
[ ‖V̂ 1/4t (xt − x∗)‖2
αt − ‖V̂ 1/4t−1 (xt − x∗)‖2 αt−1
]
+ T∑ t=1 [ β1t 2αt(1− β1) ‖V̂ 1/4t (xt − x∗)‖2 ] +
α √ 1 + log T
(1− β1)2(1− γ)( √ 1− β2) d∑ i=1 ‖g1:T,i‖
where the second inequality is derived from β1t ≤ β1(t−1), and the last inequality is due to the fact that β1t ≤ β1 and [ ‖V̂ 1/4t (xt−x∗)‖ 2 αt − ‖V̂ 1/4 t−1 (xt−x∗)‖ 2 αt−1 ] is non-negative. In this way, the proof of
AMSgrad can proceed, and the algorithm structure as well as the conclusion in Theorem 7 remain unchanged.
To summarize, we restate Theorem 7 as follows. Theorem 8 (Fixed theoretical guarantee of AMSgrad). Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are convex. Let δ > 0, β1 > 0, β1t ≤ β1(t−1) where t ≥ 2, β11 = β1, and γ = β1√
β2 ≤ 1. The regret of AMSgrad satisfies
R(T ) ≤ D 2 ∞ √ T
α(1− β1) d∑ i=1 v̂ 1/2 T,i + D2∞ 2(1− β1) T∑ t=1 d∑ i=1 β1tv̂ 1/2 t,i αt + α √ 1 + log T
(1− β1)2(1− γ) √ (1− β2) d∑ i=1 ‖g1:T,i‖.
(49)

heading: H EXPERIMENTS ON RESNET18

text: In this section, we conduct the image classification task on CIFAR10 dataset using ResNet18 (He et al., 2016). The parameter configuration of algorithms is the same as that in Section 4. We repeat each experiment 10 times and take their average. The training loss v.s. epoch is shown in Fig. 4a, and the testing accuracy v.s. epoch is shown in Fig. 4b. As can be seen, our proposed SAdam outperforms other algorithms.

title: STRONGLY CONVEX FUNCTIONS