Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: ##########################################################################


Summary:

This paper studies the convergence of adaptive gradient methods under an interpolation assumption, showing for example these methods can converge at an O(1/t), instead of O(1/\sqrt{t}) rate when perfect interpolation is satisfied. Convergence behaviors with line search and Polyak step sizes are also analyzed. 


##########################################################################


Reasons for score: 
 

This paper provides good insights regarding how an interpolation assumption may help accelerate adaptive gradient methods. I do not feel the technical results very solid, as some difficult-to-check properties are just put as assumptions (see cons). 


##########################################################################Pros: 
 

Pros: 

1. The results provides insights regarding why adaptive gradient methods may converge faster when the interpolation assumption is satisfied.  

2. Line search and Polyak step size methods help address the need of problem and algorithm parameters in standard theories. Moreover, there are few papers discussing line search and Polyak step size methods in the finite-sum setup.  

3. The Polyak step size is well-motivated in the interpolation setting. 
 

##########################################################################

Cons: 

1. The abstract claims that “AdaGrad can achieve an O(1) regret in the online convex optimization framework.” I do not see this result in the main text.

2. The paper reads waiving regarding difficult-to-check assumptions. In particular, this paper assumes the sequence of iterates is bounded in a set of radius D and the eigenvalue of the preconditioning matrices are bounded. The main argument supporting these assumptions are simply they are “common” in existing literature. I feel the technical challenges in the analyses are alleviated a lot because of these “common” assumptions.   Notice that without the conditions, the convergence guarantees may not be meaningful because the D parameter in all theorems and a_{min} and a_{max} in Theorem 3 and Theorem 4 can scale with the iteration counter.  

3. The proposed line search methods seem to be computationally very expensive. The proposed line search methods require computing the largest step size satisfying the desired inequality, instead of the *largest among a sequence of exponentially decaying step sizes* as in standard Armijo line search methods. Is it possible to analyze the performance of latter—more computationally favorable—scheme? 

4. It is claimed that the step size chosen by the proposed conservative Lipschitz line search method is bounded in [2 (1 - c) / L_{max}, \eta_{k - 1}]. Can it happen that \eta_{k - 1} \leq 2 (1 - c) / L_{max}? If yes, then is the step size selection rule well-defined? There is also a similar claim for the stochastic Armijo line search method.  

5. I don’t get the sentence that “a similar distinction between the convergence of constant step-size Adam (or AMSGrad) vs. AdaGrad has also been recently discussed in the non-convex setting (Défossez et al., 2020)” in Section 4. What is the distinction?  

6. Minor comment: 
    1. Typo in the first paragraph: online batch reduction -> online-to-batch reduction
    2. m_1 is not specified in (1). 
    3. The abbreviation SPS is not defined when it appears for the first time in the main text.  

##########################################################################

After reading author rebuttal: 

I think the value of this work is to demonstrate the possible benefits of an interpolation assumption. Hence, though there are some theoretical issue and theory-practice gap, I keep the original score. 

- I do not feel it very reasonable to emphasize the regret result in the abstract and then put the corresponding section in the appendix. It is more reasonable to move Appendix C.2 to the main text though I guess it would be difficult in practice. 

- I understand adding a projection step typically does not change the proof much. However, this is not the setup analyzed in this paper. I feel the associated newly-added clarification in Section 2 reads somewhat waiving. I suggest the authors add some clarifications in the revision similar to the following in the rebuttal. 

"Without an explicit projection step, we believe it is possible to adopt the recent SGD analysis "On the almost sure convergence of stochastic gradient descent in non-convex problems, NeurIPS, 2020." to prove that the iterates do remain bounded with high-probability. We leave this for future work."

- The other clarifications are OK to me. 

- I suggest the authors add some clarification regarding 4 in the main text. 
 

#########################################################################
review_title: Nice insight with difficult-to-check assumptions

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies adaptive gradient methods under the over-parametrized settings, where the authors study the converge in the interpolation setting. In this setting, the optimal objective is 0. The authors show that the convergence rate is O(1/T). In addition, when the interpolation is approximately satisfied, the authors show the convergence to a neighborhood of the solution. The authors also provide theoretical justifications for popular line search methods.

Overall, I find the paper easy to read. However, I do have a few questions that would like to see the authors' answers:

1. The authors implicitly assume that the optimal solution is unique.  However, this is not the case in many over-parametrized models. For example, consider the case for logistic regression where the two classes are perfectly separable. The minimizer is not well defined, but there have been extensive work on this topic. Can the authors' analysis adapt to such situations? 

2. Taking the logistic regression as an example again, the "minimizer" is not within a bounded region. Can the authors' analysis been adopted to analyze such case?

3. The result are all in the form of expectation. Can the authors bound the L2-norm?

4. I think it would be informative to add the result when the loss is strongly convex, where we can have the bound for the solutions.
review_title: Reviewer Summary

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper analyzes adaptive algorithms such as adagrad and AMSGrad in a finite-sum optimization problem. The proofs appear to treat this setting through online convex optimization and online-to-batch conversion. It is shown that both AdaGrad and AMSGrad improve when the individual losses are all minimized at the same point. Further, line search techniques are analyzed in conjunction with these algorithms, and empirical results show that in practice the line searches speed up convergence.

I do not think Theorem 1 is particularly novel. I am not sure of an original reference (it may be a kind of folklore), but see for example https://parameterfree.com/2019/09/20/adaptive-algorithms-l-bounds-and-adagrad/ theorem 7, from which it is trivial to deduce Theorem 1 by observing that WLOG we may assume f_i^*=0 for all i since subtracting the minimum value does not change the gradients.

For Theorem 2, I may be missing something. This value of alpha seems *strictly worse* than what we would get in Theorem 1 by just setting eta=eta_max. So what is the line search buying us? Is it just for empirical performance with no theoretical benefit yet? It is not obviously presented this way, so if so I think some remarks to this effect are in order.

The assumption on bounded eigenvalues for the results on AMSGrad seems a little troublesome to me: I am worried that all of the adaptive nature of the preconditioner is irrelevant and these assumptions are doing all the heavy-lifting. Indeed, if we set \beta=0, then with learning rate \eta = a_min/L and sgd update w_{t+1} = w_t - eta * V^(-1) g_t for *any* V in [a_min, a_max], then I suspect that standard analysis of gradient descent using learning rates at most 1/L will yield fairly similar results to Theorem 3. I would be happy to hear otherwise, though!

My overall feeling is that there is a missing piece here in the theory to show that the line search is useful. I am not confident that the other results are significant on their own. 

As for the empirical results, these seem like reasonable gains over Adam. I would have preferred to see more standard deep learning benchmarks on non-image tasks as well,, but I am not an expert here and so would defer to other opinions.


Nits:
I am not sure that the assumption that the iterates are bounded is well justified here. I do believe it has been assumed in some past literature, but this does not make it actually true. It is certainly *not* standard in the literature on online learning. The two references (Duchi et al 2011 and Levy et al 2018) cited as evidence here do not actually assume this. Instead, they use projections to *ensure* that the iterates are bounded without assumptions.

review_title: concerns about theory.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper revisited two important stochastic algorithms, AdaGrad and AMSGrad. It reanalyzes these two algorithms under interpolation setup and shows how the results get improved under this particular case.
***
Strength: interpolation setup is reasonable in over-parametrized regime. This paper establishes a thorough analysis on AdaGrad and AMSGrad under the interpolation setup. Further, it incorporates the stochastic line search technique and stochastic Polyak stepsize technique with AMSGrad to make the stepsize selection adaptive. The improvement results and the dependence on the extent of interpolation violation seem interesting.
***
Concerns: why do the authors not consider the unconservative stochastic line search and Polyak for AdaGrad. Also, I'm wondering what's the technical challenges to reestablish these results. Is that simply combining the classical analysis with the previous work (Vaswani et al. 2019 Painless stochastic gradient: Interpolation, line-search, and convergence rates). The stepsize lies in a bounded interval lower bounded away from zero, so that the randomness of stepsize is well controlled. 
***
For future improvement, I think authors should emphasize the difficulty of the analysis more clear. Based on my reading, authors list comprehensive results while how significance of these results is less discussed. It would be good to provide a general proof framework to make "how interpolation helps on a sharper analysis" more clear.

   
***
During rebuttal:
The authors should highlight some technical difficulties in the paper. In principle, stochastic line search under overparameterized regime does not make things harder because the stepsize is lower bounded. The difficulty of stochastic stepsize is to control the product of stepsize and gradient, while under this regime the product is separable. It seems the analysis of momentum plus this observation is enough for the analysis. It would be useful to provide some insights and challenges of the analysis.

  
review_title: Recommendation to Accept

Meta-review: Dear authors,

the paper contains many interesting and novel ideas. Indeed, tuning step-size is very time and energy-consuming, and deriving and analyzing new adaptive algorithms has not only theoretical benefits but, more importantly, is a key when training more complicated ML models.

The paper contains many weaknesses as noted by reviewers. I know that you have addressed many of them one of the reviewers is still concerned about the other issues involving Theorem 1 and the assumption of the bounded preconditioner.
He thinks the preconditioner bound is troublesome. In the overparameterized regime, he would expect the gradients to become near zero as the algorithm converges, which would actually cause the preconditioner to NOT be bounded below. It seems that the analysis might actually improve if the authors abandoned AMSGrad/Adam and instead just considered SGD for which the preconditioner assumption is not an assumption but just a property of the algorithm.





Thank you  
Decision: Reject