Blockwise Adaptivity:  Faster Training and Better Generalization in Deep Learning
Authors: Shuai Zheng
James T. Kwok
Venue:  (2020)
Keywords: optimization
deep learning
blockwise adaptivity

Abstract: Stochastic methods with coordinate-wise adaptive stepsize (such as RMSprop and Adam) have been widely used in training deep neural networks. Despite their fast convergence, they can generalize worse than stochastic gradient descent.  In this paper, by revisiting the design of Adagrad, we propose to split the network parameters into blocks, and use a blockwise
adaptive stepsize. Intuitively, blockwise adaptivity is less aggressive than adaptivity to individual coordinates, and can have a better balance between adaptivity and generalization. We show theoretically that the proposed blockwise adaptive gradient
descent has comparable regret in online convex learning and convergence rate for optimizing nonconvex objective as its counterpart with coordinate-wise adaptive stepsize, but is better up to some constant. We also study its uniform stability 
and show that blockwise adaptivity can lead to lower generalization error than coordinate-wise adaptivity. Experimental results show that blockwise adaptive gradient descent converges faster and improves generalization performance over Nesterov's accelerated gradient and Adam.

Under review as a conference paper at ICLR 2020
BLOCKWISE ADAPTIVITY: FASTER TRAINING AND BETTER GENERALIZATION IN DEEP LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Stochastic methods with coordinate- wise adaptive stepsize (such as RMSprop and Adam) have been widely used in training deep neural networks. Despite their fast convergence, they can generalize worse than stochastic gradient descent. In this paper, by revisiting the design of Adagrad, we propose to split the network parameters into blocks, and use blockwise adaptive stepsize. Intuitively, block- wise adaptivity is less aggressive than adaptivity to individual coordinates, and have better balance between adaptivity and generalization. We show the- oretically that the proposed blockwise adaptive gradient descent has comparable regret in online convex learning and convergence rate for optimizing nonconvex objective as its counterpart with coordinate-wise adaptive stepsize, but is better up some constant. We also study its uniform stability and show that blockwise adaptivity can lead to lower generalization eπтоr than coordinate-wise adaptiv- ity. Experimental results show that blockwise adaptive gradient descent converges faster and improves generalization performance over Nesterov's 's accelerated gra- dient and Adam.
INTRODUCTION
Deep networks have achieved excellent performance in a variety of domains such as computer vision (He et al.) 2016), language modeling (Zaremba et al. 2014), and speech recognition (Graves et al. 2013). The most popular optimizer is stochastic gradient decent (SGD) (Robbins Monro 1951), which is simple and has low per-iteration complexity. Its convergence rate is also well-established
(Ghadimi & Lan 2013 Bottou et al. 2018). However, vanilla SGD is sensitive to the choice of stepsize, and requires careful tuning.
To improve the efficiency and robustness of SGD, many variants based on coordinate- wise adaptive
stepsize (Almeida et al.] 1999 Duchi et al. 2011 Schaul et al.) 2013 Kingma & Ba 2015 Tieleman
Hinton| 2012] Zeiler 2012 Zheng & Kwok 2017 Reddi et al. 2018) Zaheer et al.) 2018 Zou & Shen 2018: 20e8 et al. 2019 Zou et al. (019) have been proposed. Though this is effective
in accelerating convergence, its generalization performance is often worse than SGD (Wilson et al.)
2017). Recently, it shown that coordinate- wise adaptive gradient descent is closely related to sign- based gradient descent (Balles & Hennig 2018 [ermstein et al.) 2018). Theoretical arguments and empirical evidence suggest that the gradient sign impedes generalization (Balles & Hennig 2018).
To contract the generalization gap, a partial adaptive parameter for the second-order momentum is proposed (Chen & Gu 2018). By using a smaller partial adaptive parameter, the adaptive gradient algorithm behaves less like sign descent and more like SGD. Based on the similar motivation, Luo (2019) proposed to gradually transform Adam Kingma & Ba (2015) to SGD. Moreover, to avoid numerical problems in practical implementation, a small (= TO- parameter is typically used in these methods. This parameter controls adaptivity of the algorithm (Zaheer et al. 2018). A
larger value (say, 10-3 3) can reduce adaptivity and empirically helps Adam to match its general- ization performance with SGD. This implies that coordinate-wirg adaptivity may be too aggressive for good generalization performance.
To improve generalization performance, attempts have been made to use a layer-wise stepsize (Singh et al. 2015: You et al. 2017, Yu et al.) 2017 Zhou et al.) 2018). which assign different stepsizes to different layers or normalize the layer-wise gradient. However, there has been no theoretical analysis for its empirical success.

---

Under review as a conference paper at ICLR 2020
In this paper, we consider the more general case in which model parameters are partitioned into blocks, instead of simply into layers. By revisiting the derivation of Adagrad, we propose the use of blockwise stepsize which depends on the corresponding gradient block. Such blockwise adap- tivity is less aggressive than coordinate-wise adaptivity, as it adapts to parameter blocks instead of to individual parameters. This can thus have better balance between adaptívity and generaliza- tion. Moreover, unlike coordinate-wise adaptivity, blockwise adaptivity is not sign-based gradient descent, and so does not suffer from its performance deterioration.
As in (Bernstein et al. 2018 Ghadimi & Lan 2013 Ward et al. 2018 Zaheer et al. 2018 Zou &
Shen 2018 Zou et al. 2019). we will focus on the expected risk minimization problem:
min F(0) = E (0;;
where f is some possibly nonconvex loss function, 2 is a random sample, is the model parameter, and the expectation is taken w.r.t. the underlying sample distribution. The expected risk measures the generalization performance on unseen data (Bottou et al. 2018), and reduces to the empirical risk when a finite training set is considered. We show theoretically ly that the proposed blockwise adaptive gradient descent can be faster than its coordinate-wise counterpart. Using tools on uniform stability (Bousquet& & Elisseeff 2002 Hardt et al. 2016), we also show that blockwise adaptivity has poten- tially lower generalization error than coordinate-wise adaptivity. Empirically, blockwise adaptive gradient descent converges faster and obtains better generalization performance than coordinate- wise descent (Adam) and Nesterov's 's accelerated gradient (NAG) (Sutskever et al., 2013).
Notations. For an integer n. [ni] = {1, ........,, n). For a vector I, xx denotes its transpose, Diag(z) is diagonal matrix with x on its diagonal, v is the element- wiie square root of x, x² is the coordinate-wisd square of z, ||
max; |r,]] ||æll2 x" =TQu, where Q is positive semidefinite (psd) matrix, and x 2 0 means 2; 2 0 for all i. For two vectors x and y, x/v, and (z. y) denote the element-wise division and dot product, respectively. For a square matrix X, X 1 is its inverse, and X 0 means that X is psd. Moreover, La [1, 1,1, l...,, 1)" Rd.
Vz x, ||
2 RELATED WORK
2.1 ADAGRAD
Adagrad (shown in Algorithm 1 is an adaptive gradient method in online convex learning with coordinate-wis stepsize (Duchi al. 2011 McMahan & Streeter 2010). It particularly useful for sparse learning, as parameters for the rare features can take large steps. Recently, Ward et al. (2018) established its convergence properties with a global adaptive stepsize nonconvex optimization, shown that Adagrad converges stationary point at the optimal O(I/VT) rate (up factor log(T)), where T is the total number of iterations.
Recall that the SGD iterate the solution to the problem: θe11 arg mino (gt, 8) + 2n l|e 0.12.. where 9t is the gradient of the loss f. at iteration t, and 6, E IR is the parameter vector. To incorporate information about the curvature of sequence [sr], the fn-norm in the SGD update can be replaced by the Mahalanobis norm, leading to (Duchi et al. 201T):
0++1 arg min ()
110 0. l Diag(e))
2n
where s, 2 O. This is an instance of mirror descent (Nemrrovkii & Yudin 1983). Its regret bound has a gradient-related term Σ [1 (19dl/aagss))-- Adagrad's stepsize can be obtained by examining
a similar objective (Duchi et al. 2011
min SES
Σ llgel 1 (iag(s)-1,
(3)
where S {s : > 0, (s, I c). and is some constant. At optimality, $,,i clIguT,ill2 Σ I1.. where 91.T,+ = [g1, 9T,""" As s, cannot depend on gj'ss 's with j >> t, this suggests st,i x 1191,, Theoretically, this choice of s, leads to a regret bound that is competitive with the best post-hoe optimal bound Macan & Streeter 2010).
2

---

W.W-- where Under review as a conference paper at ICLR 2020
To solve the expected risk minimization problem in I Adagrad variant called weighted AdaEMA is recently proposed in (Zou et al. 2019). It employs weighted averaging of gf, 's for stepsize. Moreover, weighted AdaEMA is general searddinate-wisse adaptive method and includes many Adagrad variants, including Adam and RMSprop, as special cases.
2.2 UNIFORM STABILITY
Given n samples S = {= drawn i.i.d. from an underlying data distribution D, one often learns the model by minimizing the empirical risk: ming ss( = و - f(0;; 2,). Let M (S) be the output of a possibly randomized algorithm M (e.g., SGD) running on data S.
n
Definition 1. (Hardt et al.) 2016) Let S and S' be two data sets of size n that differ in only one sample. Algorithm M is -n-uniformly stable if estab = sups,s supzeD EM (S))))); f(M(S"); S Cu-
The generalization error is defined Egen Es.M 4 (M(())) (S)), where the expectation taken w.r.t. the set and randomness of M (Hardt et al. 2016). It is shown that the generalization error is bounded by the uniform stability of M, i.e., (gen I Cttbb (Hardt et al. 2016). In other words, the more uniformly stable an algorithm is, the lower is its generalization error.
BLOCKWISE ADAPTIVE DESCENT
Consider the under-determined least squares problem:
min X yll2.
(4)
where X E Rnxd is the input matrix (with sample size and dimensionality >> n). and output E
R". We assume that XX" is invertible. As pointed out in (Zhang et al. 2017 Wilson et al. 2017). any stochastic gradient descent method problem (4) with global stepsize outputs trajectory with iterates lying in the span of the rows X. One solution of (4) happens be the solution with minimum 22-norm among all possible global minimizers. This minimum-norm solution has the largest margin, and maximizing margin typically leads to lower generalization error (Boser et al. 1992).
(XX"))-'2 y, which
is known that SGD converges to the minimum εg-norm solution of problem (4) ZZang et al,, 2017). On the other hand, coordinate-wise adaptive methods (such as Adagrad, RMSprrp, and Adam) fail to find the minimum æ2-norm solution, but converge to solutions with low -nom instead (Wilson et al., 2017). Examples in (Wilson al. 2017) show that solutions obtained by these udaptive methods can generalize arbitrarily poorly, while the SGD solution makes no error.
first show that blockwise adaptivity, unlike coordinate-wise adaptivity, can find the minimum no-m solution of nonlinear least squares problem in layer-wise training of a neural network. This motivates training (Section 3.2). To provide more analysis, Section 3.3 studies the proposed algorithm in the
In Section 3.1
further exploit blockwise adaptivity in end-to-end neural network
online convex learning setting as (Duchi al. 2011 Kingma & Ba 2015 Reddi et al. 2018).
3.1 BLOCKWISE VS COORDINATE- WISE ADAPTIVITY
Consider a L-layer neural network with output (--- {W1- E [gdi-1xd, )/ are weight matrices with dy d and d, = m, the output dimensionality. Assume that the nonlinear activation functions [ are bijective with nonzero derivatives on E (e.g., tanh and leaky ReLU). For simplicity, we further assume that di = d m for all Training this neural network with the square loss corresponds to solving the nonlinear optimization (0--1(0--22000 (XW:))
W, Y l| where Y =g= the label matrix. Consider training the network layer-by-laye starting from the bottom one. For layer 1, its optimization subproblem can be rewritten as
problem: min
min b (Hi - Y
(5)
where (.(-) = ó 01+1 ( .... W,- W),, H, 1 di (XW1) WT-1) is the input activation the 1th layer, and Ho X. Note that (4) is special case of with L.
3

---

Under review as a conference paper at ICLR 2020
and identity mapping. To minimize 5 the weights for this layer updated as
W1+1.1 We, 11,19t.55
(6)
where It.t is stochastic gradient evaluated at We, at time and T is the stepsize which may be adaptive in that it depends on Jt,
Proposition 1. Assume that Wy 's (with >>> 1) are invertible If W is initialized to zero, and Hi-1
has full rank, the critical point that o converges the minimum fg-norm solution of 5 in expectation.
Another benefit of using blockwise stepsize is that the optimizer's extra memory cost can be reduced. Using coordinate- wise stepsize requires an additional ((d) memory for storing estimates of the second moment, while the blockwise stepsize only needs an extra O memory, where B is the number of blocks. A deep network generally has millions of parameters but only tens of layers. If we set B to be the number of layers, memory reduction can be significant.
3.2 BLOCKWISE ADAPTIVE GRADIENT (BAG)
Let the gradient E Rd be partitioned to {gi.s, E Rd b L).,,, where Go is the set of indices in block b, and It.., the corresponding subvector of gr- Inspired by problem (3) in the derivation of Adagrad, we consider the following variant which imposes a block structure on 8:
min SES'
11 Bing(s)
0, (s, S c} for some E R. We assume the indices in Gb are consecutive; otherwise, we can simply reorder the elements of the gradient. Note that reordering does not change the result, as the objective is invariant to ordering of the coordinates. It can be easily shown that optimality of ( q6 cllg1.r,9. ........
where S' = : =
98 dg
E Vdlllgi.T.G. ll2), where 01:T,S. -.. ...--9..s. oT,,," JT. The optimal d is thus proportional lIg1.T, e. |l dd.- When in
(2 is partitioned by the same block structure, the optimal q suggests to incorporate [1g 2l2/ db into 9, for block b at time t.
Algorithm 1 Adagrad: Adaptive gradient for online convex learning (Duchi et al. 2011).
Algorithm 2 BAG: Blockwise adaptive gradient for online convex learning.
1: Input: 0; 0.
1: Input: 7) > 0; 6 > 0.
2: initialize 0, 00 +-
initialize 01;00 +-
... .., do 4: Receive subgradient gr Of((
3: for =
3: for t = 1.2..... do
4: Receive subgradient gi E f((ee)
5: for 1,
do
5: for b = 1,2...... ... B do
6: U1 = 141 i 1
6: Ut = 1/-1,6 + ll 113 db
7: f.41,1 = 0, n (v +c)
7: 0..1.6. G. Or.g. 79t. / /Ub c)
8: end for
8: end for
9:
end for
end for
The proposed procedure, which will be called blockwise adaptive gradient (BAG), is shown in Algorithm 2 Compared to Adagrad, each block, instead of each coordinate, has its own learn- ing rate, When B d (i.e., each block has only one coordinate), BAG reduces to Adagrad. When B 1 (i.e., all coordinates are grouped together), Algorithm
2 produces the update: +)) with global adaptive learning rate, which is equivalent
0.+1 = 0r to AdaGrad-Norm (Ward et al. 2018).
Returning to the underdetermined least squares problem in (4) the following Proposition shows that when B- 1, BAG finds the minimum f--n solution in each subspace induced by the group structure. When B 1, BAG converges to the minimum 2--norm solution of (4).
Proposition 2. Assume that for each b E [B]. each submatrix X. E Raxds has full row rank. BAG (with 02 initialized to 0) converges to an optimal solution 0_, of (d]. For each E [B], the subvector O_ G, of O, equals g. (X X. - -Lub some us IR and Eee(e) Ub y.
4

---

Under review as a conference paper at ICLR 2020
3.3 REGRET ANALYSIS
To further illustrate the advantages of blockwise adaptivity over coordinate-wise adaptivity, we con- sider the online convex learning setting. At round the learner picks 0,, and suffers a loss (O.).. After I' rounds, the learner wants to achieve low regret w.r.t an optimal 0. = arg ming Σ (c) in hindsight:
T R(T) = Σ f(())) E=1
T Σ f((O)) = Σ 1=1
T f((0)) - inf Σ 1()).
T
(8)
0
1=1
We make the following assumptions.
Assumption 1. Each fo in (8) is convex but possibly nonsmooth. There exists a subgradient g (f((0) such that fe(0") 2 feld) + (g. 0' 1g,0'-00 00) for all 0, 0'. Assumption 2. Each parameter block is in ball of the corresponding optimal block throughout the iterations. In other words, for all E [B], maxt ||0r... 0..0ol22 & Da for some Dn, where 0. G. is the subvector of 0. in block b.
When 1. this reduces to the common assumption online convex learning Duchi & Singer 2009). When B > 1, it naturally encodes the heterogeneity of model parameters.
Theorem 1. Suppose that Assumptions
7 and hold. Then,
B
R(T) S
Σ
DJ + mn / dh 2n
119...00.l2..
Assume that max, |10, -0 |lxc S Do for some constant Doc. When = d, the above regret bound reduces to that of Adagrad (Theorem 5 of (Duchi et al. 2011 by setting D2 = Dox for all b E [B].
In the following, we show that when gradient magnitudes for elements in the same block have the same upper bound, blockwise adaptive learning can have lower regret than coordinate-wise adap- tive learning. As deep network can be naturally divided into blocks (examples will be given in Section (52)) and parameters in the same block are likely have gradients with similar magnitudes (which is verified empirically in Appendix(B) (B). blockwise adaptivity can be more beneficial.
Corollary 1. Assume that E g I of for all E Gb. The expectation of 9 can be bounded as:
1 2m
E[R(T)) Σ
DJ + nds VT.
(10)
When B = d (which corresponds to Adagrad). Assumption some D;. Expectation of the bound in ( then reduces to
2 becomes max, (fr, O..i) I D; for
E[R(T))
Σ iEGs
D3 nds VT.
(11)
27
Assuming that Assumption 2 tight in the sense that DJ. < Eieg, DJ. The bound in 10 is then smaller than that in (TT). Intuitively, when gradients in block have similar magnitudes in expectation, we have from the weak law of large numbers that vr,b Eveg, Ut,s/db (where 01 and ve,; are as defined in Algorithms 2 and respectively) a better estimate of E(vr,J] than vg,; for single coordinate i. This implies using blockwise adaptivity may lead to better performance.
4 BLOCKWISE ADAPTIVE GRADIENT WITH MOMENTUM (BAGM)
In Algorithm Vr.a's 's are increasing w.r.t. t. The update suffers from vanishing stepsize, making slow progress on nonconvex problems such deep network training. To alleviate this problem, many Adagrad variants (such as R.Mprrpp, Adam and weighted AdaEMA (Zou et al. (019 use weighted moving average momentum. In this paper, we extend the use of blockwise adaptive step- size to weighted AdaEMA (Section 4.1). which includes Adam and RMSprop as special cases. The proposed algorithm will be called blockwise adaptive gradient with momentum (BAGM). Sec- tions 4.2 and 4.3 then study its convergence and generalization properties. Note that as BAG is special case of BAGM, the analysis there also apply BAG.
5

---

Under review as a conference paper at ICLR 2020
4.1 PROPOSED ALGORITHM
The proposed BAGM is shown in Algorithm Here, m, serves as an exponential moving averaged momentum, (3:} is sequence of momentum parameters, and o, 's assign different weights to the past gradients in the accumulation of variance. Note from Algorithm that the variance estimate can be rewritten as
19.0.11 A
19 do
Gr
(12)
de
1== aj i=1
In particular, we will consider the three weight sequences {at} introduced in (Zou & Shen 2018 S.1: a for some a > 0; S.2: a, t" for some T > 0; The fraction a,/A, in 112) then decreases as (1/11) S.3: a; = o -t for some < < can be shown that this is equivalent to using the exponential moving average estimate: Ut.b = -0 1,b + (1 a)
lls. a. and 6r.b = UsAb I-a"
de
With f. O, weight sequence S.1 and c 0, BAGM reduces BAG. When d and c O, BAGM reduces weighted AdA As weighted AdaEMA includes many Adagrad variants, the proposed BAGM also covers the corresponding blockwise variants.
Algorithm 4 BAGM: Blockwise adaptive gra- dient with momentum for stochastic nonconvex optimization.
Algorithm Weighted AdaEMA for stochastic nonconvex optimization.
1: Input: {m:}: {ax]: [Be]: 6 0.
1: Input: ]: {at): [Be): 0. initialize 01; 00 + mg 0; Ao +0
2: initialize 01;00 10 0; mg <- 0; Ag t
3: tort= = ,,, do
3: for 1,2..... do
4: Sample an unbiased stochastic gradient
Sample an unbiased stochastic gradient 9t
Ft
5:
A₁ = 1 1 a
A, AA at
6:
for i 1,2,.... d do
6: for b = 1,2...., B do
7:
Ut = 14-1,1 + or.
7:
Ut = 1/t-1.6 + ar vellgr... 1l//db
8:
G,, = Vr,1/Ar
8:
êG, Vt.b/Ar
9:
m = B:m + (1 Br)gr..
9:
m, 8 + (1 Br)g
10:
f.41, = 01,1 Memuii/ Vut.
10:
0,41.60 = f2.c. m. //v Dz,b +
11: end for
11: end for
12:
end for
12: end for
4.2 CONVERGENCE ANALYSIS ON NONCONVEX PROBLEMS
Assumption 3. F in 7 is lover-bounded (i.e., F(0.) = info F(0) > -xx) and L-smooth. Assumption 4. Each block of stochastic gradient has bounded second moment, i.e., E.ll9e,,,,111 / S of. vb {B], Vt, where the expectation is taken w.E.f the random ft-
Assumption implies the variance of each block of stochastic gradient is upper- bounded by dj VV F(O:)1B dgaa)). This naturally encodes the
(i.e., E, I...G. Vs, [(0.) E, [llgr... notion of heterogeneous gradient in a multi-layer neural network. When B = 1, this reduces to the
usual second moment bound in stochastic approximation (Shamir Zhang 2013 Zou al. 2019)
Assumption 5. 0 < 8t < 3 for some 0 5 <<L 1.
Assumption allows us use, for example, constant B, = 3, a decreasing sequence 3r = B//t,, or an increasing sequence 3 = 3(1 1/t").
Assumption (i) {a.} dec-eecc::;: (ii) at grows slowly such that {At-1/Ai) is non- decreasing and AA + w1) < w for some w 2 0; (iii) p lim A > 83.
Assumption 6 is satisfied by the three weight sequences introduced above. Specifically, for S.I (1 1/a)/2 and p > $2.
and S.2 w (1 + / and p S:3
Assumption 7. (Zou et al. 2019) The stepsize πu is chosen such that wi n// Vas/A, is "almost" non-increasing. i.e. there exists a non-increasee con-increasing sequence {ze} and positive constants C₁ and C2 such that C1 w. < C2 for all t.

---

Under review as a conference paper at ICLR 2020
Assumption 7 is satisfied by the weights sequences S.1
S.2
S.3
when
T n/vt
(13)
for some 0. Interested readers referred to (Zou et al.
2019) for details.
Proposition 3. Suppose that Assumptions
hold.
With probability at least 82/3
min VF(00) S ((log)))) VT) for S.1 and
S.2
and miniger ((.)) S 00(1)
forS. S.3
Note that SGD, with the decreasing stepsize in 13 converges rate of 0 (log / (Ghadimi & Lan 2013). Thus, the rates for for(S.1 S.2 bound, it has good performance in practice (Kingma & Bal 2013 Zaheer et al. 2018). Moreover, recall that when B = d and e O, BAGM reduces to weighted AdaEMA. In this case, Proposition obtains the same convergence rates as in (Zou al.) 2019).
S.2 are as good as SGD. Though SS. only leads to an O[)
Next, we consider B / for some B * d (blockwise stepsize), and compare with B d Ccoordinate-wist stepsize). This requires the following assumption, which is slightly stronger than Assumption 4 (that only bounds the expectation).
Assumption 8. ll9....11// S C.. vb E [B] and vt.
Note that when B d, Assumption 8 becomes Ji. S G for some G., and Assumption becomes E. S of for some o,. Let Go be the set of indices in block b when B = B. The follow- ing Corollary shows that BAGM has faster convergence than its coordinate wise counterpart when (ot have low variability. This also agrees with our observation in Section 3.3 that blockwise adaptivity can have lower regret under this condition.
Ebsi Eieo, lox (01(02/++11 Eth di log(o)/(+11) T22 =
Corollary 2. Suppose that Assumptions
3 hold. Define T1
IE Eieo, oi and r3- Ebsi adde high probability upper bound on minsseeT (/)))1) when B = (resp. = B). If
Σ Eb Eied, a log(ot((+1) Let Ča(T)/8 (resp. (T(T)) be the Ehsi ondy lox(os/(+1)
min(1, minn1,,r1,221 P2, max; max, G7+t2 maxe G6-
2 then Ca(T) 2 CT()).
maxt max Gf+c2 maxy Go+e
Note that and numerator in 72,72, T3. it can be seen that min(r1, 72, r3) is close to or greater than when {o hee. have low variability. These will be verified empirically in Appendix B
2 when Assumption is tight. By comparing the denominator
4.3 UNIFORM STABILITY AND GENERALIZATION ERROR
As in Definition let S be two data sets of size n that differ in only one sample, and the ith iterates of BAGM on S and S' by O, and 0/. respectively. Let A. 110, 0/ and Áe(z)
[f(0;; =) - (0'; =)). The following Proposition allows us to study how affects the growth of , (=)]. where the expectation is taken w.r.t. randomness of the algorithm.
Proposition 4. Suppose that Assumptions
7 hold.
Assume that I is 5-Lipschit D We have sups,s sup, E[)++1 S
3 0, and the initial 0,,0, values are the same.
25Ca nCi
? EBn de log e + 1) du Σ1_ k= nh t + (1- 7),, where W =
7 Dtm
km Mi E
maxi 11/(UuR, 02.b + + 1/( 0/ + +
+ L E (Ax((/min minn 0..6 + e)
Recall that of < 1 E.eo. of. If 1 Eieg, of, the first term on the RHS of the above bound smallest when B d; otherwise, some B d will make this term smallest. For the min, 6g.6
d,
du
term inside W., this reduces to 1 E ūbD6 when B 1, and to min, min;eā, 0R when B d.
In other words, 2f(02)) f(01;=)) < 5/10 8' for any z.

---

Under review as a conference paper at ICLR 2020
As 1 Σ 0x 2 miny tg,D 2 min, mi, 0k,6, this min, 0g,6 term is the smallest when B = d. and is largest when B = 1. As for the other terms in Wt, the first term is small when is close to d, and the second term is small when B approaches 1. Hence, for B equals some < B d. sups.s' sup, (z)], and thus the generalization error, grows slower than those of = d and B = Besides, Proposition 4 also indicates that a larger makes the bound smaller.
B3
Note that the uniform stability bound of SGD (Theorem 3.8 in [12]) is not directly comparable with our Proposition However, as SGD and B = 1 both depend the same second moment upper bound (Assumption 4p. by showing B B is better than B 1, expect blockwise adaptivity to be also better than SGD.
EXPERIMENTS
In Section 5.1 we first empirically validate the regret analysis results of BAG (Section 3.3) on linear model. In Section 5.2 we run deep networks on a number of standard benchmark data sets
including CIFAR-10 10 (Section 5.2.Ip ImageNet (Section 5.3) and WikiTexxt-2 (Section 5.4). As the
focus is deep learning, we only use BAGM (instead of BAG) in this section.
5.1 ILLUSTRATION OF THE REGRET ANALYSIS RESULTS
In this section, we use BAG on the linear model f.().) = max(0, 1 yr (0,, with input o, E R generated in a blockwise manner and y/ E {- is the label for z;. Assume that xe is partitioned into B blocks, whose structure may be different from that of the B gradient blocks. With probability -
Pb, each element Ty, in input block is sampled from ((c.3. 75) for some scaling factor a and variance 78. and it,; = 0 otherwise. It can be easily shown that for elements in the same input block their expected gradient magnitudes have the same upper bound (Elg?,1 S Pb(c] + +1))).
We generate a synthetic data set, with d = 100, using the above procedure. The first 50 features of T, are sampled independently from ((10y, 100) with probability 0.5, and zero otherwise. The last 50 features are sampled independently from (M-5p) 5yt, 25) with probability 0.4, and zero otherwise. The class label y: E 1) are sampled randomly with equal probabilities.
We study BAG with B = 1, 2, 3, 4 and 100. For B gradient gr is partitioned in the same way as the input. For B 3, we form the first block using the first 35 coordinates, the second block with the next 30 coordinates, and the third block with the remaining 35 elements. For into four blocks each of 25 elements. We initialize 0, to zero, fix = 10- and 1 0.01.
3.20
2:50
4, Sr is divided
1:29
Figure D compares the expected regret, which is estimated by averaging the regrets over 100 rep- etitions. BAG with B 2 and 4 achieve lower regrets than the others (as B 4 covers the case for B 2). BAG with B 3 is little worse its block structure different from the input block structure, but still performs better than B d. For B = 1, the mismatch in block structures is severe and performance is worst.
1.0
2000
Figure Expected regret with different B's (note that curves for B = 2 and 4 overlap).
5.2 REAL-WORLDE DATA SETS
We introduce four block construction strategies: B.1: Use a single adaptive stepsize for each pa- rameter tensor/matrri/vecctor A parameter tensor can be the kernel tensor in a convolution layer, parameter matrix can be the weight matrix in a fully-connected layer, and a parameter vector can be bias vector; B.2: Use an adaptive stepsize for each output dimension of the parameter matrix/vector in fully connected layer, and an adaptive stepsize for each output channel in the convolution layer; B.3: Use adaptive stepsize for each output dimension of the parameter matrix/vector in fully
8

---

Under review as a conference paper at ICLR 2020
connected layer, and an adaptive stepsize for each kernel in the convolution layer; B.4: Use an adap- tive stepsize for each imput dimension of the parameter tensor/matrix, and an adaptive stepsize for each parameter vector. More details on the implementation can be found in Appendix A
We compare the proposed BAGM (with block construction approaches B.1 B.2, B.3
B.4 with
the following baselines: (i) Nesterov's accelerated gradient (NAG) (Sutskever al.,
2013); and
(ii) Adam (Kingma & Ba (015). These two algorithms are widely used in deep networks. NAG provides a strong baseline with good generalization performance, while Adam serves fast coun- terpart with coordinate-wise adaptive stepsize.
As grid search for all hyper-parameters is very computationally expensive, we only the most important ones using validation set and fix the rest. We use constant 3r = ] (momentum parameter) and exponential increasing sequence [S.3 with a 0.999 for BAGM. For Adam, we fix its second moment parameter to 0.999 and tune its momentum parameter. Note that with such configurations, Adam is a special case of BAGM with = d (i.e., weighted AdaEMA). For all the adaptive methods, we use 10-3 as suggested in (Zaheer et al. 2018). All the experiments are run on a AWS p3.16 instance with NVIDIA V100 GPUs.
5.2.1 CIFAR-10
We train a deep residual network from the MXNet Gluon CV model zoo Guo et al. (2019) on the CIFAR-10 10 data set. We use the 56-layer and 1 110-layer networks in (He al. 2016). 10% of the training data are carved out as validation set. We perform grid search using the validation set for the initial stepsize 7) and momentum parameter 3 ResNet56. The obtained hyperparameters are then also used on ResNetl 10. We follow a similar setup as in (He et al. 2016). Details are in To reduce statistical variance, results averaged over 5 repetitions.
Appendix A.2
ResNet56 6.91 = 0.15
ResNet110
top- I error (%)
top-5 error (%)
NAG
6.28 0.23
NAG
20.94
5.51
Adam
6.64 + 0.30
6.35 + 0.18
Adam
21.04
5.47
BAGM
B.1
6.26
5.94 0.09
BAGM
B.
20.79
5.43
BAGM B.
6.51 = 0.14
6.27 + 0.18
BAGM
B
20.90
5.39
BAGM
B
6.52 + 0.33
6.31 + 0.06
BAGM B.3
20.88
5.52
BAGM
B.4
6.38 + 0.40
6.02 + 0.15
BAGM B.4
20.82
5.48
Table I: Testing errors (%) on CIFAR-10. The best results are bolded.
Table 2: Validation set errors on ImageNet. The best results are bolded.
Table I shows the testing errors of the various methods. With a large = 10 the testing perfor- mance of Adam matches that of NAG. This agrees with (Zaheer et al. 2018) that a larger e reduces adaptivity and improves generalization performance. It also agrees with Proposition that the bound smaller when is larger. As for BAGM, it outperforms Adam for all block construction schemes used. It also outperforms NAG with schemes B. B.2 and B.4
Convergence of the training, testing, and generalization errors (absolute difference between training and testing error) shown in Figure 2 As can be seen, both ResNet models, BAGM B.1 converges to lower training error rate than Adam. This agrees with Corollary 2 that blockwise adaptive methods can have faster convergence than their counterparts with element-wise adaptivity. Moreover, the generalization eтror of BAGM B.I is smaller than Adam, which agrees with Proposi- tion 4 that blockwise adaptivity can have a slower growth of generalization error. On both models, BAGM-B.1 gives the smallest generalization error, while NAG has the highest generalization error on ResNet56. Hence, the proposed methods can accelerate convergence and improve generalization.
5.3 IMAGENET
In this experiment, we train 50-layer ResNet model on ImageNet (Russakovsky et al. 2015). The data set has 1000 classes, 1.28M training samples, and 50,000 validation images. As the data set does not come with labels for its test set, we evaluate its generalization performance on the validation
TT reduce clutterness, only show results of the block construction scheme BAGM B.1 which gives the lowest testing error among the proposed block schemes. The full results shown in Figure

---

Under review as a conference paper at ICLR 2020
1.50
(a) Training error.
(b) Testing error.
(c) Generalization error.
Generalization error. Figure 2: Results CIFAR-10. Top: ResNet56; Bottom: ResNet1 10. Note that the training error (%) is plotted in log scale.
(d) Training error.
(c) Testing error.
set. We use the ResNet50 vld network from the MXNet Gluon CV model zoo. We train the FP16 (half precision) model on 8 GPUs, each of which processes 128 images each iteration. More As it takes long time to train on ImageNet, we only run each algorithm
details are in Appendix A.3 once.
Performance the validation set is shown in Table 2 As can be seen, BAGM with all the block schemes (particularly BAGM-B.IJ achieve lower top- errors than Adam and NAG. As for the top-5 error, BAGM B.2 obtains the lowest, which is then followed by BAGM B.1 Overall, BAGM B.1 has the best performance on both CIFAR-10 10 and ImageNet.
5.4 WORD-LEVEL LANGUAGE MODELING
In this section, train the AWD-LSTM word-level language model (Merity al. 2018) the WikiText-2 (WT2) data set (Merity et al. the Gluon NLP toolkit Guo et al. (209)). We perform grid search on the initial learning rate and momentum parameter as in Section 5.2.1 and set the weight decay to 1.2 x 10-h as in (Merity et al., 2018). Results are averaged over 3 repetitions. More details on the setup are in Appendix A.4 As
2017). We use the publicly available implementation in
there is no convolutional layer, B.2 and B.3 are the same.
Table shows the testing perplexities, the lower the better. can be seen, all adaptive methods achieve lower test perplexities than NAG, and BAGMM B.2 obtains the best result.
NAG
Adam
BAGM
BAGM-B.2
BAGM B.4
65.77 1 0.10 65.40 + 0.13 65.42
0.10
65.29
0.14
65.55
0.07
Table 3: Testing perplexities on the WikiText-2 data set. The best results are bolded.
CONCLUSION
In this paper, proposed adapting the stepsize for each parameter block, instead of for each in- dividual parameter as Adam and RMSprop. Regret, convergence and uniform stability analyses show that it can have lower regret, faster convergence and lower generalization error than its counter- part with coordinate-wise adaptive stepsize. Experiments on synthetic dataset, image classification and language modeling confirm these theoretical results.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
L. B. Almeida, T. Langlois. J. D. Amaral, and A. Plakhov. Parameter adaptation in stochastic optimization. In On-line learning in neural networks, pp. 111-134. Cambridge University Press, 1999.
L. Balles and P. Hennig. Dissecting adam: The sign, magnitude and variance of stochastic gradients. In Proceedings of the International Conference on Machine Learning, pp. 404-413, 2018.
J. Bernstein, Y. Wang, K. Azizzadenesheli, and A. Anandkumar. signSGD: Compressed optimi- sation for non-convex problems. In Proceedings of the International Conference on Machine Learning, pp. 560-569, 2018.
B. E. Boser, I. M. Guyon, and N. Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the annual workshop on Computational learning theory, pp- 144-152. ACM, 1992.
Bottou, E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-31, 2018.
O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2(3):499-526, 2002.
N. Cesa-Bianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2000-2557, 2004.
J. Chen and Q. Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprint arXiv:1806.0677 0e0.1880606763, 2018.
X. Chen, S. Liu, R. Sun, and M. Hong. the convergence class of adam-type algorithms for non-convex optimization. In Proceedings of the International Conference for Learning Represen- tations, 2019.
J. Duchi and Y. Singer. Efficient online and batch learning using forward backward splitting. Journal of Machine Learning Research, 10(12):8899-2334 2009.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7):121-21599 2011.
B. S. Everitt. The Cambridge dictionary of statistics. Cambridge University Press, 2006.
Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic pro- gramming. SIAM Journal on Optimization, 23(4):2341-2368. 2013.
A. Graves, A. Mohamed, and G. Hinton. Speech recognition with deep recurrent neural networks. In Proceedings of the International Conference on Acoustics, Speech and Signal Processing, pp. 6645 6645-6649, 2013.
J. Guo, H. Hc, He, L. Lausen, M. H., Lin, X. Shi, C. Wang, J. Xie, S. Zha, A. Zhang, H. Zhang, Z. Zhang. Z. Zhang, and S. Zheng. Gluonev and gluonnip: Deep learning in computer vision and natural language processing. arXiv preprint 199iv:I907.0 0443304433 2019.
M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proceedings of the International Conference on Machine Learning, pp. 1225-1234, 2016.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the International Conference on Computer Vision and Pattern Recognition, pp- 770-778, 2016.
D. Kingma and J. Ba. Adam: A method for stochastic optimization. In Proceedings of the Interna- tional Conference for Learning Representations, 2015.
I. Loshchilov and F. Hutter. SGDR: Stochastic gradient descent with warm restarts. In Proceedings of the International Conference Learning Representations, 2017.
11

---

Under review as a conference paper at ICLR 2020
L. Luo, Y. Xiong, Y. Liu, and X. Sun. Adaptive gradient methods with dynamic bound of learning rate. Proceedings of the International Conference on Learning Representations, 2019.
H. B. McMahan and M. Streeter. Adaptive bound optimization for online convex optimization. In Proceedings of the Annual Conference on Computational Learning Theory, pp. 244, 2010.
S. Merity, C. Xiong, J. Bradbury, and R. Socher. Pointer sentinel mixture models. In Proceedings of the International Conference on Learning Representations, 2017.
S. Merity, N. S. Keskar, and R. Socher. Regularizing and optimizing LSTM language models. In Proceedings of the International Conference on Learning Representations, 2018.
A. Nemirovski and D.B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
S. J. Reddi, S. Kale, and S. Kumar. On the convergence of adam and beyond. In Proceedings of the International Conference for Learning Representations, 2018.
H. Robbins and Monro. stochastic approximation method. The Annals of Mathematical Statis- fics, 22(3):400-4017 1951.
O. Russakovsky, Deng, H. Su, Krause, Satheesh, S. Ma, Huang, Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):111-552 2015.
T. Schaul, S. Zhang, and Y. Lecun. No more pesky learning rates. In Proceedings of the International Conference on Machine Learning, pp. 343-351, 2013.
O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Convergence re- sults and optimal averaging schemes. Proceedings of the International Conference on Machine Learning. pp. 71-79, 2013.
B. Singh, De, Zhang. Goldstein, and G. Taylor. Layer-specific adaptive learning rates for deep networks. In Proceedings of the International Conference Machine Learning and Applications, pp. 364-368, 2015.
I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and momentum in deep learning. In Proceedings of the International Conference on Machine Learning, pp. 1139- 2013,
Tieleman and G. Hinton. Lecture 6.5 RMSProp, COURSERA: Neural networks for machine learning, 2012.
R. Ward, X. Wu, and L. Bottou. Adagrad stepsizes: Sharp convergence nonconvex landscapes, from any initialization. arXiv preprint arXiv:/806.018) 2018.
A. C. Wilson, R. Roelofs, M. Stern, N. Srebro, and B. Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4148 4158, 2017.
Y. You, Gitman, and B. Ginsburg. Large batch training of convolutional networks. arXiv preprint 170700700,.38888, 2017.
A. W. Yu, Q. Lin, R. Salakhutdinov, and J. Carbonell. Normalized gradient with adaptive stepsize method for deep neural network training, arXiv preprint 107.02270.. 2017.
M. Zaheer, Reddi, D. Sachan. S. Kale, and S. Kumar. Adaptive methods for nonconvex optimiza- tion. In Advances in Neural Information Processing Systems, pp. 9793-9803, 2018
W. Zaremba, I. Sutskever, and O. Vinyals. Recurrent neural network regularization. arXiv preprint arXiv: 1409.224, 2014.
M. D. Zeiler. ADADELTA: An adaptive learning rate method. Preprint arXiv: 2012.
12

---

Under review as a conference paper at ICLR 2020
C. Zhang, Q. Liao, A. Rakhlin, K. Sridharan, B. Miranda, N. Golowich, and T. Poggio. Theory of deep learning ii:: Generalization properties of sgd. Technical report, Center for Brains, Minds and Machines (CBMM), 2017.
H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz. mixup: Beyond empirical risk minimization. In Proceedings of the International Conference on Learning Representations, 2018
Zheng and T. Kwok. Follow the moving leader in deep learning. In Proceedings of the Inter- national Conference on Machine Learning, pp. 40.4411--444 10-4119, 2017.
Z. Zhou, Q. Zhang, G. Lu, H. Wang, W. Zhang, and Y. Yu. Adashift: Decorrelation and convergence of adaptive learning rate methods. arXiv preprint arXiv: (000:08810000144 2018.
F. Zou and L. Shen. On the convergence of weighted adagrad with momentum for training deep neural networks. arXiv preprint arXiv: 003.80088.0 2018.
F. Zou, L. Shen, Z. Jie, W. Zhang, and W. Liu. A sufficient condition for convergences of adam and rmsprop. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1p.11127-1113,, 2019.
A EXPERIMENTAL SETUP
A.1 IMPLEMENTATION DETAILS
As {ar} is non-decreas,ng, the accumulated sum A, can grow significantly, which may potentially cause numerical issue. In practice, using steps 7 and in Algorithms equivalently rewrite the update in (12) as the following exponentially moving update:
be.b = =000-1.66 + (1 - or))
de
where oa = 1- a./A.. of a then = a(1 - aa-11//10 this setting leads to an (11) bound. On the other hand, if a; = 1", then we have a:/ = (11l)).
a²). Based on Proposition 3
This suggests that we can use polynomial-decay averaging O₁2 = - (c+ 1)/(1+ c) for some c 2 0
Shamir & Zhang 2013), whereas > 0 reduces the weight of carlier iterates compared to later
ones. The larger corresponds to the larger т. In this case, as Σ 0r = O(77) for some > 0.
have convergence rate of (log(T))TT)
A.2 CIFAR-10
The CIFAR-10 10 data set has 50,000 training images and 10,000 testing images. As in (He et al. 2016), we employ data augmentation for training. We first pad the input picture by adding 4 pixels on each side of the image. Then, 32 32 crop is randomly sampled from the padded image with random horizomtal flipping. A
size of 128 is used. The stepsize is divided by 10 at the 39k-th and 59k-th iterations. We use a weight decay of 0.0001.
For NAG, the initial stepsize 7) is chosen from {0.01, 0.05, 0.1, 1]. For the adaptive methods, have 7) E {0.0001, 0.0005, 0.001, 0.005, 0.013. The momentum parameter is searched over (0, 0.5, 0.9). The learning rate is multiplied by 0.1 at the 100th and 150th epochs. We perform grid search on the hyper-parameters by running each algorithm for 200 epochs on ResNet56. The hyper-parameters that give the highest accuracy on the validation set are employed. The testing performance is obtained by running each algorithm with best hyper-parameters on full training set for 400 epochs. The same obtained hyperparameters NAG applied to ResNetl 10, we use a smaller learning rate at the beginning to warm up the training. Specifically, the obtained learning rate is divided by 10 in the first 4000 iterations, and then go back to the original one and continue training. The grid search results are shown in Table
then used on training ResNetl 10. When
Figure shows that, ResNet56, BAGM converges a lower training error rate than Adam for all schemes used. For the deeper ResNet100 model, BAGM-B.J [.44 have faster convergence than Adam, while BAGM-B.B and B.3 show the same convergence speed with Adam.
13

---

Under review as a conference paper at ICLR 2020
7)
NAG
0.5
0.9
Adam
0.005
BAGM B.1
0.005
BAGM B.2
0,005
BAGM
0.005
BAGM
0.005
Table 4: The best v and obtained by grid search CIFAR-10.
Nar's
(a) Training error.
(b) Testing error.
(c) Generalization error.
(d) Training
(e) Testing
(1) Generalization
Figure 3: Results on CIFAR-10 for the proposed method with all four block construction schemes and the baselines. Top: ResNet56; Bottom: ResNetl 10. The training error (%) is plotted on logarithmic scale.
A.3 IMAGENET
In this experiment, we employ label smoothing and mixup (Zhang al. 2018). The cosine schedule (Loshchilov & Hutter 2017) for learning rate used. A warmup of epochs is applied. During validation, we the center crop. Hyperparameter tuning is based the obtained results in Sec- tion A.2 Specifically, for NAG, the initial learning rate chosen from {0.4, 0.5). and momentum parameter is fixed to 0.9. For Adam and BAGM,, we have the initial learning rate f0.004, 0.005), and we use momentum parameter 8 = O. A weight decay of 0.0001 is used (weight decay is not applied to bias vectors, and parameters for batch normalization layers) The best learning rates for each method are shown in Table 5
A.4 WORD LANGUAGE MODELING
In this experiment, we follow the same setting in (Merity et al., 2018). A 3-layer AWD-LSTM considered. The model unrolled for 70 steps, and mini-batch size 80 is used. We
clip the norm of the gradients at 0.25. The details of the configuration used in this experiment can be found in https:
cwwccoomm//////o dml c htt.:///aa.....ooooooo//o//aa/aa
'The example script for running NAG with "
0.4 can found in https://raw.
g sithubusercontent. ctt/ chtes//mmc///e web- https/atttt/mmtee//giooooo
imagenet/rrenet00__ee wa sh| Details of the data augmentation can be found in
https:://gittuu.comm h//p://mmmmmm/////// uon- cv/b
wwt.co//llo//maatttteeeeeo wwwplloo/////e/e///om/ooaoeeeeee http://teeeerrrrtsaa/aeeaeeeeeee fication
Tmagenet/trainn_imggenss
14

---

Under review as a conference paper at ICLR 2020
"
NAG
0.4
Adam
0.004
BAGM B.1
0.004
BAGM B B.2
0.004
BAGM B
0.004
BAGM
0.004
Table 5: The best y obtained by grid search on ImageNet.
language model/word wawgualaaggggggaaaaeaeeeee figuration in Table
For completeness, we show the model con-
dimensionnlltyydropouu rate
embedding size
400
hidden size
1150
dropout
0.4
dropout for RNN layers
0.2
dropout for input embedding layers
0.65
dropout to remove words from embedding layer
0.1
weight dropout
0.5
Table 6: Model configuration of AWD-LSTM model.
As the WikiText-2 data set comes with a validation set, we perform grid search by evaluating the performance the validation set. For NAG, the initial stepsize chosen from {1,3, 10,30) 30). For the adaptive methods, we select 77 {0.1, 0.03, 0.01, 0.003). The momentum parameter varies in {0, 0.5, 0.9]. The learning rate is multiplied by 0.1 when the validation performance does improve for 30 consecutive epochs. We tie the word embeddings and softmax weights. For each algorithm, we employ the iterate averaging scheme proposed in (Merity et al. (018). The model is trained for 750 epochs. The pyppe--asameters obtained by grid search are shown Table 7 In general. B.I and [.44 are not suitable for updating the word embedding matrix word frequency varies lot and thus the gradient is highly sparse. However, the gradient becomes dense when use weight tying. In modern toolkits such as Tensorflow, MXNet, and Pytorch, the weight matrices of the LSTM gates are concatenated to speed up matrix-vector multiplication. We need to apply B.1 and B.4 to these weight matrices separately.
17
B
NAG
30
Adam
0.03
0.5
BAGM
0.03
0.9
BAGM B.2
0.03
0.5
BAGM
B.4
0.03
0.5
Table 7: The best and 3 obtained by grid search on the word language modeling experiment.
B GRADIENTS PARAMETER BLOCK
As discussed in Corollary 2 BAGM can have faster convergence than its coordinate- counter- part when {o } ked. have low variability. In this section, we verify this experimentally. Using the focus BAGM-B.1 which shows the fastest convergence. At the end of each epoch, we perform 10 full data passes with random shuffle and data augmentation (as described in Appendix A.2) to compute Elg,] and Elllg,, l/. We then approximate of and of by their empirical maxima over all epochs. Figure 4 shows the coefficient of variation of To],,, which defined as the ratio of the standard deviation to the mean (Everitt) 2006). As can be seen, around 86% (resp. 75%) all blocks for ResNet56 (resp. ResNetl 10) have coefficient of variation smaller than 1, indicating that {o] heg. have low variance and concentrate around the mean.
setup in Section 5
15

---

Under review as a conference paper at ICLR 2020
maxs max max, G/++2
We also compute the empirical values of miin min(r1, 72,73) rs) and Corollary We use the two symbols (Ür,B and C(T)) that are defined in Appendix for the corresponding main theorem. Moreover, we estimate V
in
max; Gg
innatee 0r,a+e" where öT,d
VT,6=1 and
maxieds Ge+ maxs Go+
T Br instead of
C(T) is tighter than C(T). We estimate
Br B using maxigisT maxy 81
The results are shown in Table
ResNet56
ResNet1
@ratte "T B +2
(2,
Br,tte
min(r1,72,55)
"r,8+
B.1
3.70
1.02
3.30
1.01
B.2
1.50
1.06
1.73
1.05
B.3
1.47
1.01
1.39
1.01
B.4
2.27
1.17
2.47
1.13
Table 8: Empirical estimate of Pr.ate
fr,ate? and min(ri, (2, r2, rs).
V
As can been seen, all min(r1, F2,77) 73) are larger than 1, indicating {o]hee ked. have low variability for all the proposed blocks, which agree with Corollary 2 and explain why the proposed blockwise adaptivity leads faster convergence. Moreover, B.1 has largest v /r.ate" a Theoretically, means B.1 should lead to fastest convergence, which is empirically verified in Figure 3. Similarly, B.2 has
trw and is therefore the second fastest.
second largest V fr
BAGISSS
BRGM
1.50
3.75
codfoott nanida
contcie streeti
2.2
3.25
3.00
Moo
0.23
0.00
-20
200
Stock
1lack
(a) ResNet56.
(b) 1es
Figure 4: Coefficient of variation of {o oof Neg, for all the blocks with B.1
The blocks with higher
indices the abscissa belong deeper layers.
C PROOF OF PROPOSITION
Proof. In this proof, we use denominator layout for matrix calculus. As all the activation func- tions are bijective and (W+) are invertible, Φ is bijective and has an inverse function 4- Specifically, Φ-1 is given by
क; (V) (--
W
Then, with the assumption that H1 has full row rank, the nonconvex objective can reformu- lated as the following convex problem:
min H. W. (Y)
(14)
Wi
obvious that its large margin solution H (H2- (HH,, H 1- In the sequel, we will that every critical point of (5) is global optimal solution. Let h41-1 denotes column vector
16

---

Under review as a conference paper at ICLR 2020
that is the i-th row of Hi-1 and Z be the i-th column of matrix Z. The gradient of (5)
2
Diag D, YY,) 14
k=
(x(x))] E Raxd and E₁ Y.,) GR. to be the enror matrix. As Hi-1 has full row rank, then clearly gradient is zero if only and if Ei O. By the definition of Gk,,, we can see that Ej only and if (H(H-1 Y when V v==h, w, (((z) has full row rank for all i [n]. Note that
where G =
V >= (x)x):: k V
2 2 Diag
the gradient V x ,T, w: (x) of the following form:
V V==AT (2) (W, o -
(W1+1 o
where o the Hadamard product. For ts E fl.................... L 1]. as W841 has full rank and o (z) + for any = E IR, we have that Wk+1 144 (M W ""1 has full rank. Applying the fact that the mul- tiplication of number of invertible matrices preserves full rank, we obtain that Va=nr,,,, 2r(x) has full rank. Therefore, every critical point satisfies (H Y and every critical point is global optimal solution.
Let i be the index chosen iteration and Yt, be the 4,tth of Y. Let define 6,,1 2 >E (4) (#i -- - (k., V= , We, (x(x)). Now, we prove that the following update rule applied on (5) finds critical point, then the iterate converges to the largest margin solution.
W11.= We,1 -n.hh,,,-eee -
Σ E.
(15)
where W1,1 I is the stepsize for I-th layer at iteration and Ej,1 is matrix in which its ig-th row is ej and all the other rows are zeros. Then, the solution found by (I5) lies in the span of rows of H other words, the solution has the following parametric form:
W1 =T
for some E IR. Thus, if (15) is converging to critical point in expectation, then we have Wi, + W., as + oo, where W., = H&F , an optimal solution, then W., is also solution to (14), and we have
au,, for some optimal a.,r. Since every critical point
( = HW., H1 11
We solve for a., and obtain
a,1 = (H|- (1
Therefore, W., = (H,
D PROOF OF PROPOSITION 2
Proof. Let (Ira ys.) be the pair of sample selected at iteration 4. The stochastic gradient of least square problem (4) at the f-th iteration is
2(x ys, ).,
X eT
where we define to be the error vector with value 2(x 0g nr,) in the iy coordinate and zeros elsewhere, For each block b, BAG with 01 uses the following update rule:
0.+1e, = 0c.g. - TT 19, = X
Σ nhbes
17

---

Under review as a conference paper at ICLR 2020
e 12/d/ +).. Then, each subvector of the solution found by BAG lies in the span of of gs. In other words, each subvector of the solution of the following parametric form:
||X where 76,6 = n/( Ei=i /
0g. g. Cts
for some Og 1R. Combining with Theorem and online-to-batee conversion (Cesa-Bianchi) al.
2004 BAG is converging in expectation -1 A - 02 as - oo, where 9..9. X. ax,b for some optimal 04,b- Since 02 is solution
have
B X. 16000 Ca.b.
y = X0,
b=1
Assume that each submatrix N. has full row rank, then No .9. invertible, we can solve for Q+.b'ss and obtain
Ua.b (X 1
for u, R and _b=1 Up y.
E PROOF OF THEOREM
Lemma 1. Let f8i} be the sequence generated by the Algoritim 2 Define
1( +
1 d....... (VTLD + + IT Let H, Diag(s:). Then, for any 0, have
f((0.) - fe(0) S
1 _ 110 01l21.
- 11100 0122. + 22 11 H.
7
21)
21
Proof. For any 0, the convexity of fi indicates that f(():) fi)
I (gr, O2 - 8)
(or, bet1 0) (gi, O2 B(+1)
= 1 10011 -0, H,, 0c+1)) + (gt, 0z - Oc+1)
= 00 0|: 21
| - 01121.
2n 110++1 - -Bell2e, + (gt, 0, +e+1)
2m
< 21
00 0|;
10++1
011i,,
211 110c+1 0cllin, 21 110c 08l1ir, 2 1190l112 2
21j
=
02
0| 2
10c+1 - 0112,, + 2 9 |1
2n
2m
where the second to last inequality follows from Fenchel's inequality applied the conjugate func-
tions 2n 11 and 2 -
Lemma 2. Considering arbitrary R-valued sequence {ai} and its vector representation a1:t
[a1,..., ar), we have
Σ
211aart|1.
|axell2
Proof. The lemma can be proved by induction. The lemma trivially holds when T = 1. Assume the lemma holds for 1, we get
T
a
< 2110117-111
|a 2
|
= 2 - x +
x
vz
18

---

Under review as a conference paper at ICLR 2020
where we define Z ||a1rT l2 and a²z As the RHS is non-increasing for 2 0. We set maximize the bound and obtain 2vZ.
Lemma 3. Let H₂ be defined as in Lemma Denote 91.t.6 [T..
I. 17. We have
T
11 H1
S
Vo dollr.a
Proof.
T
19:
1|
ge. Diag (t) ( 'gg))
H1
T
dc.199....1
111.t. 12
1 11
d
191. l1
b=1
du 1..
where the last inequality follows from the Lemma by setting a, 119..
E.1 PROOF THEOREM
Proof. By summing up the equation in Lemma 1 with 0 = 02, we obtain
1 2n
Σ - < 10 0. 1212
|10++1 0- 11+++1 - -01124,
+
1 || H.
2n
[=1
t=1
By the construction of H,, we have that H(+1 2 Hr. Then, we get
||0+1 0, 11 10 11
(0 0m, Diag(Se+1 (0)(11+1 0m))
B
Σ
110+1.0. ol. - vv..))
Given the above result, we have
|10+1 0.1171.4 -10 - -0.117%
10 O 12(VV-11,6 /v,b))
B
10141.. - -22,9 12..1v 12./22-1166 - vv, +
Σ
|10... - 0,,ea11(Vee1. - /01.))
D
UT
101,0, - -0. -0. Σ
6=1
b=1
Recall that UT,6 1 en db. Let 0. Combining Lemma
3 with the fact that ||:: 00
ΣB |11.00 - 0. 113 /1.b,
/ we have
D2
B Σ / dollgg.r...ule
Σ ((())) f(().) s
1
ll2 17
2n
dd
19

---

Under review as a conference paper at ICLR 2020
E.2 PROOF OF COROLLARY 1
Proof. Taking expectation of the gradient terms in P9. we have, for all b's,
B s
Σ VEDo t=1
E Elgh oov dsT.
Let B = B. Then, reduces to
E [(((T)
S Σ Ob
D + ndb VT.
2n
F MAIN THEOREM
Let or V E. I2l. We define sequence of virtual estimates of the second moment:
1
Oe
0r,6
(U
+
E, el..
At
dp
1
19 12
oi,
at
wb E [B]
(16)
A
db
do
Let 0T.B = g Elmax, 02,0] Theorem 2. Suppose that Assumptions
hold. Let = 8² //. We have
E VF VF /1/33//// C(T),
min ITST
where
C(T)
12 + 22)
2C2
Cu C4
3
onds Σ w/ (V
(V
T
(1- 3)C
CCa
B
( 2
r
+ Σ
Ch
Wi log
+1)
+ Σ
V
03 A
(17)
b=1
t=1
C. F(01) F(O.), C4
20²
Cj
LC de
Co Ci
and C33
CiVCall-Van
(D)(1-3)
C- vP)2
8/(-8)
+ 1.
(CAA1/A211-))
When B d, the bound here is tighter than that in ZZu al. 2019), neous second-order upper bound (Assumption 4. Note that constants Co, C3, C4 are not related to block partition. They only depend initial optimality gap and sequences {m.) {ar), (Bc). In the following, we introduce several lemmas to prove the Theorem 2
exploit heteroge-
In the sequel, we define H,
H, = Diag(st).
where
8t = (Vor, + 1) .......(vv (Vor, + ( +c)
Let 6, = 0.41 0, - We introduce H, as
H, = Diag(5:),
where Ur defined in [6 and
8,
[( 8,,1 + +c]17 ... (V Un c)12 1f
Assume that 02.0/ do < or for all t and let Σ = Diag([o]17 1 JT).
*When T the second term C(T) (involving summation from t to T) disappears.
20

---

Under review as a conference paper at ICLR 2020
Lemma 4. Let St Su Ei= ai where {ai) is non-negative sequence and So > 0. We have
at St
S log(Sr) - log(So)
Proof. The concavity of log leads to log(b) - log(a) (b a) for all a, b> 0. This suggests that
log(a) log(b) log (
a
Hence, we have
T
St
S
T
S₁
<
log
= -log(S)) log(So).
S
S
S
1=1
1=1
Lemma 5. Let faet and { be two real number sequences, and let St = Ei= 8t. Then, we have
T-1
Σ
055 Σ (a a ar
Proof. Let So O. Expanding the summation, obtain
Σ (s St-1)
8t8
T
T-1 S+ Σ
a+t1S. + ST
1=1
(ar 0,+ 0.+1445 )² ST
Lemma 6. Assume } is non-decreasing such that (At))/At} is non-decreasing, Define wt ne/ V ar Ac" Assume we is "almost" non-increasing. This means there exists another non- ine-increasingg sequence { and positive constants C1 and C2 such that C1 S we S Cztr. Then, wy S C2/Crw and tu S C2/Cim
for all i
Proof. For any < 1,
S C2 s C2 S C2/Crwn
Then,
< O2var/A -,-1-A,-1/A Ciya:/A, 111 C1V1- A n S C2/Cim.
Lemma 7. Assume that {ae) is non-decreasing. For any block diagonal matrix
Diag([c;1] 17, ..... Cg 1T with 2 for all b, we have
T
B
oo +1 +1) + log (1 T a +1 +1) log
Σ
a+ H 9el12
<
co
A
2
b=1
21

---

Under review as a conference paper at ICLR 2020
Proof.
T
T
B
Cb 9t.0 11
at A
H
9ellè
01.6 + c)2
1=1
B
cb
L4 A, 19
0r,6 + 6²
B
T
cbal s.
aellgi,0 /1 //db A,E²
Σ Chdd
0s1lgi 1.1 + dg. A,E
a+ ael19t.0.113
Chdy
21=1 0:11gh.0.1
doaiee
Hence,
T a.l.... doaie² - log(dda())))
H
goll2
<
Σ cddy
log
Σ
A,
where the inequality follows from Lemma
Using Jensen's inequality, we get
B E
E
H
9:
11c
CodgE
log
Σ a ll. 11 + dsaje?
log (og(daa)e)))
A
1=1
6=1
1=1
B
Chdla
log
Σ as
El
+ doare?
log(dhaaee?
b=1
B
cbds
log
doop
Σ
+ dbare?) log(dbale?
bml
i=1
B
of
cods
log
Σ
aj
ajc²
i=1
Using the inequality log(1 + ab) log(1 a au+bb bbb)) have
log(1 a) + +lg([1 (1 b) for a, b 2 0, we
T
a A
H
1el12
<
Σ
B
cods
log
of + log
+1) 22
{
1 @ =
t=1
Assume W, is "al- most" non-increasing. This means there exists another non-increasing sequence {2e} and posi- rive constants C₁ and C2 such that Ci I wi S Cz for all For any block diagonal matrix C Diag((ei [cr 12 ..... Cn 12 1T) with ea 2 0 f.ror all b, we have
Lemma 8. Assume that {at} is non-decreasing. Define w; =m//
dg
T
E
V
at A
H. 11
<
C1
C2
w1
B
cody log
( c2
+1
+
Σ
B
cols
T
ni
A
Ot
A
A
+
b=1
1=1
22

---

Under review as a conference paper at ICLR 2020
Proof. Let Ee
0. HH
l then Se Ei=ı E.. Lemma 5
gullé.
indicates that have
T
n
A
Ot
H
gelle
=
Σ
wiht
1=1
T
$
C2
21E1
t=1
C2
Σ
(3
24116e + 25lr
Define = = -b Cods [log (3 +1] + log
Ei= ai + 1)]
By Lemma we have ElG] -
ai
Mp. Then,
T Σ E E
H sill2
C2
s411 ElGd 2T Elsr]
A
t=1
T-1
C2
Σ
(2t 2 + MT
where the last inequality follows from the assumption that 2 ze+1- Then,
E
H
C2
Σ (2
2+11 + Mr
At
T
C2
(M, M4-1) + Mo
B
T
At + a1
)
=
C2
21
cods log
+1
+
2t
Codp log
A + a1
b=1
b=1
C2
2
B
AA + a1
<
C1
W1
cydo log
?
+
+
Wt
crdy log
A,-1 +
h=
(=1
b=1
As log(1 + x) $ x for x > -1 and the fact that Ar Ac-1, we get
log
A + 01 A, aa
=log 1+
A + a1
-1 1)
<
A
a2
Ar
01
A,1+
+
A,
+
Hence,
a1 H 1e A
C2
B
B
A a1
T
<
W1
Co log
+
1
+
Wt
cody log
C
A--1 + a1
C2
C1
B
Co log
o0
?
+1
+
B
cbdb
T
1)t
A A
Qt
Ax
a1
b=1
1=1
1=1
Lemma 9, Let Nr.6
m Versti
For each block and 2 2, we have
6
B.7
8c-1
= =-
Be)
7r.b
A,do
19r.
Ne.
+ în
Ttbb Yeb Ze,b.
V1 ur/ Ac
Vūrs te
/dn
G6
23

---

Under review as a conference paper at ICLR 2020
where
Bem 1.5b
(1- gr)
Xt,b
Vors + Ar 1z 10.11
V 11,66 + 02.6
Aiva, 110.01l12
Be
at Ards
Acdh
dr
Otbb
Yeb
VoL+ +e 101-100-10/4 + BB, + 1 1,0/A V0, + A₁ 1
9r.. (1- 3c)
osh
Vdb
VoD + @v + /Vub
(--AA-1/A)
Zt
A.pm--1..
(VAL-10-10/A A + v AA-11AAcc)
Proof. For any 1 2.
Bin
6.
82-1
v A 1AAth
nome
St
/A-1//A80--
m
B1
1/1
8t
AA-2/A180-
3.m
1
/0e +e
Vu
VA +E
1
--
(A-181-1/A1+ VA-I/Are
1
B0
(18)
V +
Vott VAI-1"h-1/A 1/A A +
(1-VAr-1/A) c
+ +Behmm--
AA 111 + AAec/AAc)
Let expand the first term of
(18 as
(1 - Bemse
(1 Br 3.)
1
+ (1- 101--Bi0 B:)mi
Vue +e
Vor +c
/ue +e
Vū: +
(1 3.)
0r -144
+ (1 - B.)m
Vo +
(Vui + +V(( +
(ot+++((V c)( + vvx)
For each block b, we have
(1 - B.)
VorD -e
Be)mgroo
21 A,d,
(0 1191.9, 112)
=
Unb +e
+ (1 Be)
(Vor, <)( Vi. + e)
Vi. / (eD
(1 B. + R.D Oeb at gr..
(1- 3i) anD
Aeds 19 113 (1 3,) P19)
Vil.
me. ddb Tib + c / + .
/0 + V + 02,b
24

---

Under review as a conference paper at ICLR 2020
Then, expand the second term of (8):
Vot V AA -Ap-1uh-1/A4 EE
A U/- A - VVz
(v + +c(( 1 10-10-11//0 +
1 1/ et
B (Vor + A + () AL-10--1/A)
Similarly, for each block b, we have
Vot VAL-IUL-L0/A Ar +e
as se (A,da)
01, + + A 10: 1,6 A, + e)( Fi.b + A
0.119....113 (A,
=
-
(Vir.b + c)
00,b ()(v0r.
a aellgr.s (B(())
01,6 c)
(0r, VA--10-1100A4
VAL-mG-1oAAttc
Vūe +e
Rt
119....11
3.m4-1.00
Aedo
Nebb -
0cs te Vor +
/1-100-1,//A
0rb - ddg
A.vdo 190.
Bem4-190
A.do
R1
0t. 1/1
Azds
ar
Othb
(20)
Vo VA--ii-11/AA + Vo, + A 1,0/ Ar /ib + 1
Combining (19) and 20 into 18). we obtain the result.
Lemma 10. Suppose that {ar} is non-decreasing sequence and A, E/= ar such that (At/Aet1} is non-decreasing and lim;-
At = = > 0. Let Å = I[b=it1 A; A,
for sist
Att1
and Ar, 1. For fixed constant P such that 3² < < < p. we have
A 2 Capt
1 and N the maximum of the indices for which Aj-1/Az P. When A,P there are such indices, iee, A A1/As A2 2 D. we use C. by convention.
where C. (II,
Proof.
A N
N
Az-1
N
Az-1
N
Aj-1
A
D'N-=
p
2
pr.
Aj
Aj
A,p
A,p
j=i+1
y=i+1
j=i+1
j=2
Lemma 11. Suppose that 0 S B: < 3 < for all I, Let p F.
g²
where p is defined in Lemma
10
Then, for all t, we have
| < C.at/
6r.b
where Co is defined in Lemma 10
25

---

Under review as a conference paper at ICLR 2020
Proof. Let Be, Iī==t1 By for i < and Be,e
|m..g.ll 112
Be)
3.)
Di
Acds
Aeds
2
B
Σ
a4
ee 112
Ands
A.do
B,)
02.b-
(21)
Addo
Then, with Lemma 10
we get
B,
3,)
Ba
4
(22)
A.do
ai A:ds
Ar,i
Caat/(Aeda)
p
Caael(A p)
Then, combining
21 and
22
we obtain the result.
Lemma 12. Assume F is L-smooth, {ar} non decreasirnnn such that {Ai-1/At is non non-decreasing
and lim Ar+1
AL = p > 0. Let p be a constant such that 3² < p < p. Assume E. l1ž1
Assume w, is "almost" non-increasing. This means there exists another non-increasing sequence {ze} and positive constants C1 and C2 such that Cizt S we S C2 for all I. Assume 0 < 3, I 3 < 1 for all I. Define following Lyapunov function:
oi I d.oî. Define we nel v as
M₁ = El ( ((.)), 5,) + 11).
Let C3 =
B/(1-8) + where = F. Then, for any 2 2, we have
g²
(CaA1/A((1-1)
Me S AI-1/Aellc1
Ben
M
2 E
B₁
|VF .
+ Cw
at
|| H 9e 1121/
1
A
(1
Bw
A
+LE [| 6. +
Ca p) (v
-
anda
(23)
A
b=1
for 1 = 1, we have
M1 < 1-
31
E
|VF(6)) + +2w1 E
a1
H s1ll
+ LE (24)
2
A
Proof. For any 12 2.
Bon
5 5 ) (25) VAL-/Am
Ben
((FF(()))
E
(VF(())) E
((()))
VALi/Am
Then, for the first term of (25). we have
( = 00
< (VF(O,-)), ((00--),,,-11 11-10-0-11111
(FF(0-2))&,.1) + 1116,-1113
where the first inequality follows from Schwartz inequality and the smoothness of the function F. Hence, we have
B.n.
BiTr
E (V,)),
E (VF(0--)) 61
V A A
A Belli
/ Aohh-1
M,
/ AA-1/Ach A/A
26

---

Under review as a conference paper at ICLR 2020
Now, estimate the second term of (25 By Lemma 9
for each block b, get
Bon
E
V. F(t),
82-1,96
VA--1AAm
R1
11 11
1
-(1- EK) V 5.. F(O),, Fe.09... + E
Vs. F(t)), R1.bb
A.d.
v + Xr.b)
Jzh Mo,b) +E K Vo, F(O,), n ddb
)}
EV F(O.), Zcn))
(26)
For the first term of 26)) we have
(1 - 3. E G. (())), 6...6..)
-(1 -1
-(1 - FV,,
(27)
For the second term of (26). we have
A. ge 12
Vo, F(.),
Xe.b) Xxb)
V0r.D +
v Mr.0 Vg. F (0)) 112 19 /ll////
m. x, 190, /12/ / // Vbbll
E
(28)
Tt.b/ Vo
Vos +
Note that
nool Vvbb +6
no
V o/ /
Dhob
Wurob.
(29)
/o1/A107,.//o
Vau/Ae
Besides, we have
Be
(1 - Be Be)
|r,ull2
Bib + VAL-10
v 00.6 + 2r.b
8,
(1 - B.)
<
+
Bist + v 10
Ur. + /r..b
2
With Lemma II
we have
M1-18
my 14-11.n
5
5 ACad (Aldb) (Ard)) p)¹ (30)
Vols
10
A
2
V A
1.b/ AA
1
Val
It.Gs
Jt.Sr
gt.Sr
(31)
Vor V Erb
/ 01.b
v Va. Ae l2/db
Var/Ae
2
2
Then, we get
8
(1 3.
X
CaAr-1 / (A,db)(1 p)
Vua/A.
3e/(1 -3)
(1 B.)
+1
/CAA--/AA(110
V /at/Al
8/(1- - 3)
(1 B.)
CaAA-1/A((11 +
aar/A.
8/(1 3)
(1 3.
= C3 (1 (1- B.)
CaA1/A2(1 p)
/a/AA
Vat/A.
27

---

Under review as a conference paper at ICLR 2020
where the last-to-second inequality follows from the assumption that 3e I B, and the last inequal- ity holds as we assume {ar} is chosen such that {A--1/A} is non-decreasing for all t. Hence, combining the above result with 29 and (88). we have
19 Xxb I1
E
Vg, F(O)), Re,b
A.do
Vos++ te
V. F(66)l12 01 le/Vdb
Vuro Br) V T. 19 112
11.b
E
Tr,b/ /b
3e m..bl Vg, F(O.)) 91.9 12/dd + wxoaC3(1 - Bx)) (v 0r + e
1. ge, Go 11
4
/ dp
3e n Vg, F(,)) 11 E 19..
/2///bb + ww - 3,) (v 0r.6 =)2
4
o..//b de
3r
Me y. F(0,)1 + woobO3
A.
(32)
4
(v 01,6 x)²
where the second inequality follows from ab < term of (66
eb? 2
for any > O. Now, we estimate the third
2c
E
(o.. F(O,), R..b Vdl
othh Yr., )
Tc.b Vv. F(O))l2
Oehh T..6
[Yesell
vdo
Similarly, with (30) and 31. by expanding ||22lll,, we have
||r,lll < Asvan 19..00 Bellm,-1,00l
V Acdo 119..0112
Aid, ozbb
Vor te
1 /ur + v 10-101-1.0/ /or. v A
4, llo0,olll2 (1-3))
vit
v vo Vēc. + Voe.s
A,yd, 119 lla
3e
A, 11 1 Be
Bib te
/CAA,-1/A (A:b-1/AAa/AAab))))) (Ardb)(1 pp)
Vor +e
+e Vas/ Ap
9 119,
Ae 119h.so ll2
Br
AA +
Bi)
Vis+ +E
Vob+t +6
31/(1- B3)
+1 (1 (1-B,)
Ver te
(CCAA-1/A((1 - pp)
A. ll Ca(1- ((1--B)) Bc),
Vūra +e
where C3 is the constant defined above. Hence, together with
29
we obtain
E
(oo
Vo, F(O.), Rr.b Vdl
Tt YED )
S E
Trb Vg,
F(o))l2
or
aL A
19..r
Cs(1 BBa)
ddh
Vor +c
Be
2, 11l1
VVg. [(b))1
+ wro
3,)
4
( (0, + c)2
3
BL 1191..9111 113
Th
E
[ F(0))1
+ W.OLCEE
(33)
4
0r.b + +e)
28

---

Under review as a conference paper at ICLR 2020
The last term of 26 can be bounded follows
( L.V,,F(BB F(t)), Ze,o)| - E F(.))()) Bloovd [2,0122)
and with 30
get
(1 (1-VAL-1/A
Be 1100ll
12,,o122 1
A 11-00-100 1.bb- + V A 1/-1/AAe (v 14
B.n.
(1- \--AA-1/A
/CaAt-//Aaai (A1d6) (Aad)(A(d)))(
3TH Ardb/a
At
(V AA-1 -1]
VCal1 p)
Buiv
At
-1111) 1
VCal1- -p) p)
A4-1
Hence,
Bondowr Caal1 p)
(V
-1
A
V (l..F.((O)) Z,,0) 5
(34)
Ar-1
Combining
26
27
32
33
and (34)
we get
BeT
E
V ((e), de,
81
VA A 1/A
1 1 Br Te
91
99.9s
Bordour
A (V
V.. F(0))1
2wior
Ac
0c + e)²
VCa(1-1)
Summing from b to B, obtain
Be
8r 8 )
E
(F(()),
8c
1 B m E
[IFF())))?))))
+ Cw
at HH 90 1
2
A
Swi
A (Va
A
-1)
)
Σ
andy.
v Ca(1-p)
b=1
Then, with 25
we have
E F(O,), Sc)
BETE
Mr-1
1- 3r
The
|VF(0)))
+ 2w, 2w,C.E
Qt
11,
9ell33
A A/A/AAn--1
A,
Bwr
(V
Ar
obdb.
VCa(1-1) p)
A4-1
We obtain 23 by adding the term
[ to both sides of the above equation. When = 1, we
have
Mi
11 E (VF(()(())... 7 31)g. +)) + 11181
E(- (n /
(35)
Then, following the derivation of (1),, for each block b, we have
(1 - B1)m91ss.
(1 3.,,,,.0... + mss T
A, 9...
(1- B1)
Van
V0
vdh
01 +e / /0, 00,
01 Aido
11 11 (1 - 1--8,9....
7.b
Di +c /ib + / 01,
29

---

Under review as a conference paper at ICLR 2020
Hence, with similar argument, we get
E VF((1), mn (1 (1- (1)11)
)}
1 31
mn
E
[IVF(0)))
+ 2w C2
a1
H
91
1123
V01 +
2
A1
Combining above with 35 and adding LE[[)] we obtain (4
Lemma 13. With the same assumptions in Lemma 12
we have
T Σ
C//C/w
11 S
Wt
Of
|
Ca(1
vD)²
A
E=1
Proof. For each block b,
me.gull2
Σ
II
$3 |3.
(1 3c)ar.
f=++1
2
33(1 .83) (BB) 11
j=++1
119.0ul12-
Then,
| lla
ge 19..0
Vor, +e
Vor +e
1=1
Since 0r, 2 A,-10t-1,// Ac, we have 01.6 2
[Ti A Ag-1/A/) 0g.b Ae,0s, 2 Cart by
Lemma 10
It follows that
||m.g.ll2
gr 1gi.all2
B 11 Σ
vD 1- 191.00
Vūrs +
Vūr +c
VCa i=1
Vp
VoLo +e
VCa
Vols +
1=1
s=l
Then, as at/4
= 1 - A A is non-decreasing, we have
||
Σ
B
B =
Σ
Wt v (ar//Ann Armm.
W
B
Σ 1=1
vp
v a / A, 11
2
=
Vūr, +E
Ver. +e
Co
VoLb+ +e
b=1
b=1
B
ai As 119.0ool2
2
vp--
Ca
Ui.b +
b=1
2
Va,/A, 100.oll1 2
VTL-
VP-
Ca
Σ =1 vD--))
v /0 +E
b=1
1=1
?
B
ai/iAlll 11...
wf Ca(l - vp)
B
0./A4 11 (VoLb + 6)2
Vp--1
S
vP
C₂
(Viz,) + 6)²
b=1
1=1
w
ag
9:.12.
=
C.
A
iml
As w/ S C2/Ci for any E t by Lemma then we have
| < C.(1 vp)
/ /C/w
vp wi
04
||
H 1/.1..
A
i=1
30

---

Under review as a conference paper at ICLR 2020
Hence,
T
C3/Cpun
T
di
|
W;
|H, 9:112
Ca(1 vp)
A
1= i=1
c3/Cuun
Σ
di H 9:112
Wi A
Ca(1 vp)
i=1
C3 /ff
T
Σ
#4
0i
H 9:112.
Ca(1
vp)²
A;
Lemma 14. With the same assumptions in Lemma 12
let M, E (VF +. we have
C2
I.2//Cwr
Σ Mr s 1=1
20
E
HH," De fells1/a
+
Σ
W
H
gel1
CivC,(1 VD)
A
Ca(1 vp)
A
1=1
1=1
T
At
))
1-3
|VF
VCa(1 - p)
W1
(
A1-1
2
b=1
Proof. Let define following quantity
N₂ E
at
H De gell
+ [
Bul
(V
A
Σ
B
obdb, Vt 2,
A
VCa(1- p)
(AAL1
b=1
N1 =
2w1 CGE
Q1
91 11
+ LE 11 112].
A1
Then, by Lemma 12
for any
2, we have
3.71
1- Be
M,
M
2 E
|VF(0.) + N.
v Ac-1/ArT
BiTT
M1-1+ N₁
VA-1/AMi:
and M1 & N1. Then, by recursively applying above relation, we get
M <
Mi
Be
N₂
1-
E
[VF(0))
A
A
1=2
BESTIe
1 -
Br Th:
<
E
where B., I1; Bj for i < I and Br, 1 and
Å.,
II
--+++
A for i < l and A.. 1. A,
Note that Br, S gr-i, and n I C2/Cim. mi. By Lemma
10 we have A C.pt- Then,
C2 t
t-i
1-
B
Me s CivCa i=1
N
E
(()))))
Vp
2
C2
1
Br
N;
E
CiVCa
2
1=1
31

---

Under review as a conference paper at ICLR 2020
It can be verified that the above inequality holds for t 1 as C2/(CIVCa) 2 1. Then, summing
from t = 1 to = T, we obtain
T
T
C2
3
M v
N
T
VF
V
CIVC
2
C2
ΣΣ
T
T
VP
N
Σ
T
3
E
VF
(0.)
CivCo iml
2
1=1
C
1-
3
T Σ
N₂
E
[VP
(36)
CivCo(1 vp)
2
t=1
With Lemma
13
we get
T
N₂
=
T
2w,
C
E
A,
Qt HH,
Sells3/a
+ [E([1,,11)]
+
T
V CCa(1 p)
A
A
Σ
B
ondy
1=1
t=1
1=2
6=1
LC2/09w1
20
3
E
A
Gg
HH
96 11/2
Ca(1 vp)²
E
A
at
| 9cl12
1=1
3
T
A
Σ
A,-1 -1
Wt
Ca(1 P)
Combining the above with (36). we obtain the result.
Lemma 15. Assume {ae} is non-decreasing such that {Ai-1/Ac} is non-decreasing. Define wt
Mi/ V ai Assume is "almost" non-increasing. This means there exists another non-increasing As"
sequence } and positive constants C₁ and C2 such that C₁ S wi S C224. We have
1 T
(DIIF((0)11"")) 3/2
/2 (maxigigr E [maxx 01,0 + 2)
Σ
T
m E
[FF()))
1 A.
C1/C2n
Proof. By Hölder's inequality, we have [| < (BIIX)))) /a for any 0 < p.q with 1/p 1/q = 1. Taking p = 3/2, q = 3, and
(0.)1
2/3
maax Te.6 +c)
2/3
x
Y
max; dtdb
we obtain
2/3
)TT) 1/3
VF(00)1
(11 max U0,0 + +e)
E VF
maxxs U2.b +
Hence,
1)
(E) (Vmga Te + )") 1/2
E (F(0))2
4/3
3/2
E
IVF(0))1
maxs Ue.b +
Note that
VF(0.)11
F(O)11
maxi 0r,b te
/mxx Gr,b +
B
IV F(B.)1
<
Vūr +
b=1
[V)
=
32

---

Under review as a conference paper at ICLR 2020
We also have
( max 0r,b + )
E
2E
max Ur +
2 E
max 8z + +22
Then, for any S T, we get
(1I 3/2
max DtDb + t E [VF(
b
2 (E [maxt 0r +
||VE(())
H,
2 (maxisieT maxx 01,6)
+ 22)
C1/Can
E
[FF()))
H,
where the last inequality follows from Lemma Taking average from 1 to we get
B[I (II 3/2
2 (maxigier E max; 0t + 22)
E
(FF()))))))))
T
C//22T
PROOF OF THEOREM
Proof: As F is L-smooth, then we have
L
F(8.41) S F(8.) + (VF(0)),
02) " 11 0.112.
2
Recursively applying the above relation, we get
F(O.) < E[F((T- S F(O)) + Σ Mrs
where M, = EE(F((()))) 5,) + 11) By Lemma 14 we have
E [[] []
< F(0,) F(O.) + CivC.(1 vp)
C2
20
W. E
Q1
H
9:
9:
A
LC3/CFWI Ca(1 vp)2
Σ W.E
Qt
|H
1
9.112
B
B
ordB
Σ
Wi
(1 A (V
At
A
Ca
1
t=1
b=1
1=2
F(O1) F(O.)
C2
20
E
at
HH, 9
11
11231/2
CI -
/p)
A
T.C3/Clui Ca(1- 2
T
B
T
(1 (v -1)
Σ
E
Gt
H
9
+
Σ
ord
Wi
A
Ca, (1
p)
b=1
1=2
33

---

Under review as a conference paper at ICLR 2020
Applying Lemma g
we have
1 1-8 8 T
Σ T |I
1=1
< F(01) F(O.)
CIvC((1- - vp)
C2
20
Ci
C2
W1
B
oody log
%
+1
Ty db
A,
A 1
A
+ a1
B
2
B
T
Gt
A,
Ca(1 vp)
101
de
log
c
+1
1
+
db
1/1
A
A
+
01
b=1
b=1
1=1
B
A
Σ
Oodo
Wi
VCa(1 - P)
A111
b=1
1=2
< F(O1) ((O.)
C2
C2
B
0
2
T
at
CivC.(1 Vp)
20
C1
W1
ondh log
2
+1
+
oadh
1/e
A
b=1
b=1
t=1
LC2//Pw1
of
T
a+
W1
de
log
+1
w
Ca(1 VD)
A
B
B
T
AA
]
oodb
Wt
-1
VCa(1 - p)
A!-1
b=1
1=2
C2
8
A₂
F(O:) F(O.)
CIVCa(1-VP)
CCa(1 p)
Σ
Jbdy
Σ
1t'
(V
A
b=1
t=2
+ ΣΣ b=1
B LC33/Punds
223C2o +
Wi log
of x2
+1
+
t
T
at
Ca(l- vp)²
C1
A
1=1
Combining above with Lemma 15 we have
min
E (F)))E
3/2
1
(EIIEE())11))))) 3/2
2 (maxissTT E maxx 02,6)
[F(0)) - -((.)
C1/C2(1 BTTTT
C2
T
Ai
Jbdr Σ Wh
1
CIvC,(1- vp)
VC P)
Ar-1
2=
B
LCC/CC
2C3
T
Ca(1 - vD)²
C₁
Wi log
0 22
+1
+ w Σ
T/t
A
at
1=1
2 (maxisiST E [maas U1,b1 +2)
2C₂
[F(0,)
F(Oo)]
T
(1 8)C
2C3
8
B
T
A
C CC - (1 8)
V Call p)
obd
Wt
(1
A
(37)
b=1
1=2
B
LC
2C
T
a1
C1Ca(1 vp)
C1
wi
log
2
+1
+
A
(38)
b=1
t=1
34

---

Under review as a conference paper at ICLR 2020
F.2 PROOF OF PROPOSITION 3
To prove the result, we use the following high probability bound.
Proposition 5. With probability at least 1 62/3, mini (VF < C(T)/6.
Proof. By the concavity of the minimum, we have
E
min [F((0))
4/3
3/2
min E (1 3/2
ISAST
Let X = mini (0. The Theorem
suggests that we have [ - C(T))/3 By
Markov's inequality, we get
C(T))/33
E E[X2/3
X2/3 >
S
82/3 $
82/3
C(T)
Hence, P P(X>
X
C(T)
82/3, and we have P(X < c(T) 11-82 82/3
Proof. (of Proposition Recall the definition of C(T) Ott +T). This suggests that
When de = =tt, we have A
at
77
Q0
7
0
A
1
3
tA
1
A
7
A
(1),
1
3g
tat
8
ta:
and
A
v
Ar
v A
1-1
0 (
A,1
V
Hence,
A
O (log(T)), and C(T) O (log(T)
Σ L"VE A₂
O (log(T)).
Σ Wi
At-1
/T
On the other hand, when a; = -1 we have
at A,
a
7
1/t
<
3
a
<
Vi
A
17
1- at
7
W/
1
B
t,t
B
(1-a)t
2
(1 B) (1 a)t
and
A
1 1-at a
lta
A
1 (1 | a) a
Then, we get
A Σ Wt (1
al Σ " A,
2nVTT
-
and -1))
A,-1 A
Combining the results with Proposition
we complete the proof.
35

---

Under review as a conference paper at ICLR 2020
F.3 PROOF OF COROLLARY 2
Proof. As 1B/do I G. then we have
vrb = (01-1, + at E.llg,,, (11//111////// S G.
and therefore ë = maxigisT E maxx T, S max; G. Arranging the terms in Ö(T), we obtain
C(T)
1 2 (maxs G7 +2)
2C2
[F(O)) - F(O.)]
1/T²
B)CI
CVVCa vD) - 33
203
Ca(1 - p)
B
Σ
wi
V
A
A
-
1)
+
2CJC2
C1
T
7
0t A
Σ
B
ordR
1=2
1=1
b=
LCBw3
B
% +1)
203 C2wr
B
of c²
dg log
oodg log
+1
CyC,(1 - vp)
2
C₁
b=1
b=1
WCJ dw
T
at
C9Ca(1 vp)
1
Ae
t=1
When B = d, we have
Ca(T)
2 maxx ma. G. + 22)
2C²
[F(0) F(0.)]
(1 1-3
2C
B
Σ
T
W
Ae
-1
1
+
204C2
W
T
1/
dt
d
CLvCa(1 vD)(L 3)
Ca(1 pp)
Ar-1
C
A
1=2
1=1
LC
d
0²2 +1) +
22
0²
log
log
2 +1)
C1
vp)
2
C1
LCJ dw
Σ
at
C)Co
vp)
1/
Av
(Maxb max.ea
G? + 22)
20²
- -3C [F(0) F(O.)]
'TT
202
3
Σ w)
T
A
20
T
at
B
1
T
CP vD)(1- (0)(1-3) 3)
Ca(11 - p)
A
C1
A
1=2
1=1
b=
LE9s
LC
B
2Cg
log
+ +1) +
Σ
Σ
log
+1
C)Ca(1 - vp)²
2
C
2
b=1 ieg.
6=1
LCJ
T
at
C1
-p)²
1h
A
36

---

Under review as a conference paper at ICLR 2020
Σimm Deeo log (0((0//++11
Eo-1 Eieo, o1 and 73
Substituting 71
Σe du log( (og(o /2/c211)
12
Σ ords
Ci Eie, or log +1)
we get
Ebs aads log (01(0)/++11
CT(T)
max; maxxeeh G + c²)
20
[F(O)) F(O.)]
T/T
- 3)C1
CVVCa1
2C3
vD)
Ca(1 - p)
B
Σ
T
(1
A
A
-1)
+
203C2
C1
Σ
T
1)6
A
Qt
B
obds
1=2
1=1
b
1
LC
of +1
20 C2
o
C9Cal1
11 vp)²
do log
+
C₁
r3
oodg log
x
+1
T
at
CiCo(1
vp)
1/s
A
1=
max, Eā C +
2 min(1 (1,ml)))
max; G + Cg(T),
where min = min(ri, P2, ra). Then,
r2,
Ca(2) (g(T) 2 min (1, Fmin)
maxy max max,ee LEG,
G7+c²
When B B,
max, G
we assume that Assumption is tight in the sense that of de Eiego Thus, Tiin can be larger than 1 as of I do EiEg, o. Corollary 2 then indicates that blockwise adaptive stepsize will lead to improvement if /mmax, max G? + <2) ()/mmx C% + + Tmm
1. Similarly, assume that the
upper bound GB is tight so that G3 & d, Eieg, G.. Thus, max; max G? 2 max, G7 and the above condition is likely to hold when Tiin is close to or larger than 1. From the definitions of that they get close to is larger than 1 when {o? (eg. have sufficiently
rı, 12 and rs. low variability.
F.4 PROOF OF PROPOSITION 4
Proof. As function is 5-Lipschitz, we have the following result:
sup ((M(())))))))) (EM - -
Therefore, we can consider bounding EM (I) (S)))2 Let 3r 0 for all t.
01
Mi H m+
01
Σ
Tis H gk
k=
0
Σ
Mr H 1 (02(0i zi.,,
k=1
'Note that J Er 19,9,,,,111 [b3 +
Es(gi,s < 1 Eieg o. On the other hand, मे Es Belllg. 113) <
T. Thus, this bound is tight in the sense that oū 1 Eicú, of
d,
37

---

Under review as a conference paper at ICLR 2020
where is E [n]] is the example index selected at iteration k. Then, can bound Ac+1 1|0
8' 8/11 12 as follows
E[A++]] B1| 01+11l l1z]
B|[10 - 0 Σ I H V =
H 1i-vVs(0 [[((0;=
E||10 - 0illa] +
mh E H S =in)) H - 1(0(; =4,1
k=1
The ( - 21)12
(39)
Note that 2ip = 24, with probability 1 1- 1/n. Then, we can bound each term Hi| Vf(( zic)
H ' f((
24, ) [|z] as follows
E 1 f(0i 2. 11 (V((/) 21 M12]
2 H ff(k Zix )12l + 1
1
E[I| (V z..) H V 2z. )
2
(1
H 1 v f(0:: 24 )all +
E Ell f 24. H f 2he 11
(1 -
E H - ([((; - H - f((2; 24 112].
(40)
The second term is bounded as
E H ([(u; H1 - [0x: 2, l12]
$
El|
H - 12 V 2s, l12]
E
[ - 1 [|2]
E
max
VukD +e
Voh.0 +
We expand the third term of
40
as
H
f( 2..) - 26x
Vf((k:
E
B| k 2 V ff(nn: 2.,) V f(0/= Zi,, ]12]
LE
H 12 0x - 8%112)
LE
1 0/112
mins Uū.b
LE
Ax
min; 0g +
Substituting the above results into
40
and combining with 39 we obtain
2
E|A+1]
S
mi El| H V
(0R5 )1))
k=1
(1
7
1/3 E
max
/Unbt +e
Vokn +e
+
1
L
Dk
mins Uk.b
Rr
38

---

Under review as a conference paper at ICLR 2020
Note that if w.
is "almost" non-increasing w.r.t another non-inereasing sequence { and positive constant C₁ and C2, then 3 is also "almost" non-increasing w.r.t. another non-
increasing sequence {2,) and positive constant C2 and C2.. Using Lemma 8 with C = I, we have
H V f(kk: M121
Vt
E
H
ff(us: 21 1131
k=1
A
Vt
E
H
V f(xs f( 21
ak
Ak
1=
B
0/
As
V1
W
dp
log
+1
d
Σ
1
62
A
+ 01
b=1
k=1
o c
dg log
+1
+
du
7/
t.
b=1
Then, we get
2C₂
B
0 2
E|A+1]
dp log
+
+
dw
mh
2
t
nC1
b=1
7
7/s E
max b
n1
Von. +E
v V0.00 +e
---- (1-))
1
m7
E
ming Uk.b + e
h=1
As the bound holds for any S,S', z, it also holds for its supreme.
39


Reviews:
[{"review_id": "Hkgm9j2x5S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes adaptive gradient approaches where the step-size is not determined on the per-coordinate basis but rather for blocks of coordinates. Theoretical results are presented in terms of regret in online convex optimization, regarding convergence in non-convex optimization,  and with respect to uniform stability and generalization. These indicate that under certain conditions adaptivity at the block level could outperform coordinate-wise adaptivity. The approach is evaluated against alternatives on simulated and real-world problems.\n\nThe paper considers an important topic, which has been the object of many related studies. Though the proposed approach is interesting, there are several issues with the present manuscript that would warrant significant revision.\n- Though the discussion in section 3 aims at motivating the use of block-wise adaptivity, it is quite confusing. Indeed the problem considered in that section is different from the setup eventually considered.  Moreover the paper claims that it is more general than the many previous work on layer-wise adaptation. However, the example considered here does consider layers. \n- The paper organization could be improved significantly. BAG is presented followed by a regret analysis in convex optimization. Then BAGM is presented followed by the theory on non-convex optimization. It might be more effective to first present the algorithms BAG and BAGM and then have a theory section.  It would also be good to emphasize that the regret analysis is solely for convex optimization, which makes it much less relevant in the context of deep learning.\n- The claimed superiority of block-wise adaptivity in the theory relies heavily on an assumption relying on tightness and closeness of  upper bounds on gradient magnitude /  gradient second moment in each block.  As this assumption is crucial to the results, its validity in practice should be more thoroughly investigated, beyond the small study relegated in the appendix  B. It would also be important to assess what happens when the assumption breaks down. \n- The aforementioned issue is somewhat also related to the choice of design for the blocks. Some choices might help, some might hurt based on the unknown structure of the data. This is barely touched upon in section 5.1. as it is noted that the more sever the mismatch the worse the results. \n- The empirical evaluation needs to be more comprehensive in terms of comparison methods. Among others it would be important to assess performance against previously proposed layer wise stepwise approaches mentioned in the introduction. \n- These related approaches should also be discussed more deeply and contrasted against qualitatively.\n- The empirical results are not substantially superior. It is also quite disappointing to see that the training, testing and generalization curves on Figure 2 are quite similar with NAG and Adam and do not exhibit less instability etc. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgPOgw1qH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a generalization of AdaGrad, called BAG, that operates on blocks of parameters instead of each individual parameter. The authors also propose a momentum version of BAG called BAGM. Convergence rate results are proved for the algorithm, and some uniform stability results show situations where BAG would generalize better than previous adaptive gradient methods.\n\nOverall I found the paper interesting, although I found the paper very dense and hard to read. The paper would be much easier to read if an effort was made to present the theoretical results in slightly simplified forms. In addition to this, I have a couple more concerns about the paper, which I list below:\n\n1. I am a bit unsure about the what the uniform stability results add to the paper. \na) While Proposition 1 is interesting, is it relevant for the BAG algorithm since it considers a layer-wise training process. \nb) Proposition 2 is also a bit confusion to me. How does generalization get worse as the number of blocks approaches the number of parameters (i.e., gets closer to AdaGrad)?\nc) Proposition 4 looks interesting, but hard to interpret the way it is presented now.\n\n2. Is the better generalization performance observed for BAGM (as well as Adam) simply due to the larger epsilon value used in the experiments? Would such an epsilon value simply turn off the adaptivity as the iterates gets closer to the minimizer (when the gradients are small relative to epsilon), and effectively do SGD? How does performance vary with epsilon?\n\n==================================\n\nEdit after rebuttal:\nI thank the authors for their response. Some of the other authors have expressed a number of concerns about this paper's theoretical and empirical contributions, and I am not raising my score.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1xwlWqiKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes blockwise adaptivity.  We divide the parameters into blocks, for example in a linear threshold unit the bias term is in a bias term block while the input weights are in an input weight block.  We then average the square norm of the gradients over each block and use the same adaptation based on this average square norm for all parameters in the block.  theoretical and experimental results are given.\n\nThe idea of assigning different learning rates to different types of parameters is old.  Extending this idea to blockwise adaptation is natural and intuitively I would expect this to be an improvement on Adam.  However, I did not find this paper very compelling.  First, I believe that the theoretical results are a straightforward adaptation of know methods.  Second, and more significantly, comparing optimizers empirically is very tricky and I am not convinced that the experiments described here are convincing.  In particular the performance of optimizers is very sensitive to the tuning of hyper-parameters.  I would need to be convinced that the hyper-parameter tuning is sufficient.  Grid search is very inefficient compared to random or quasi-random methods.  Adam has four hyper-parameters and gird search over four parameters is very difficult.  For vision applications of Adam joint tuning of the learning rate and the epsilon parameter is critical --- these parameters are coupled.  It seems extremely likely to me that the move to blockwise adaptation has a profound effect on the optimal value of epsilon.  A thorough investigation of epsilon tuning is needed to demonstrate the value of blockwise adaptation in vision applications.\n\nPostscript:\n\nI still feel that the theoretical analysis provides little to no evidence of in-practice value of the method.  In general I find that theorems guaranteeing getting stuck on a flat plateau to be not very exciting.  What about the exploration goal of local search or mcmc?  In the absence of meaningful theory, the empirical results are what matter.\n\nI have read the response and am not convinced by the comments on optimizing epsilon.  I still believe that empirical claims about optimizers require extraordinary do-diligence in hyper-parameter optimization of both the proposed method and the baselines.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose an adaptive block-wise coordinate descent method and claim faster convergence and lower generalization error. While the reviewers agreed that this method may work well in practice, they had several concerns about the relevance of the theory and strength of the empirical results. After considering the author responses, the reviewers have agreed that this paper is not yet ready for publication. 
Decision: Reject