Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: 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.

The 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.
- 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. 
- 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.
- 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. 
- 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. 
- 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. 
- These related approaches should also be discussed more deeply and contrasted against qualitatively.
- 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. 
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 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.

Overall 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:

1. I am a bit unsure about the what the uniform stability results add to the paper. 
a) While Proposition 1 is interesting, is it relevant for the BAG algorithm since it considers a layer-wise training process. 
b) 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)?
c) Proposition 4 looks interesting, but hard to interpret the way it is presented now.

2. 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?

==================================

Edit after rebuttal:
I 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.

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: 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.

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

Postscript:

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

I 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.
review_title: Official Blind Review #1

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