Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a new analysis for AdaGrad method in smooth and non-convex optimization, to get high probability convergence toward stationary points.

Based on some assumptions (Eqs. (2), (6) and (7)), i.e., Lipschitz, bounded variance of gradient estimates, and bounded stochastic gradient, the authors analyzed Algorithm 1 (AdaGrad), which does not use any information of the quantities in the assumptions. They show that (in Theorem 4.2), with high probability, the averaged cumulative gradient norm square is converging to $0$ at order of $\tilde{O}(\log{(1/\delta)}/\sqrt{T})$. The main difficulty is to derive high probability bounds for the two quantities in Eq. (10), i.e., Propositions 4.1 and 4.2.

The authors then generalized their analysis to the generic AGD template (Algorithm 2), which recovers AdaGrad, AdaGrad with averaging, adaptive RSAG, and AcceleGrad as special cases by choosing different $\alpha_t$, $\eta_t$ and $\gamma_t$ parameters. Similar high probability convergence results can be obtained for AdaGrad with averaging, and adaptive RSAG, but not for AcceleGrad.


main_review: Disclaimer: My apologies for putting this review very late, due to I have been assigned as an emergency reviewer about two days ago.

strength:

- The high probability bound results provide more information than the expected convergence results (basically the variance of the optimization behaviours), while the AdaGrad method is a base for many widely used optimizers in machine learning, and therefore the topic is important to optimization community.
- The analysis is simple and elegant, which I appreciate. The proofs are correct as far as I have checked.
- The presentation is very clear and easy to follow.

weakness:

- I am concerned with the results do not tell us much information about why the AdaGrad and its variants enjoy good performance in practice. In particular,

- The main results in Theorem 4.2 claims that after $T$ iterations, the averaged cumulated gradient norm is small with high probability. However, it seems this result cannot exclude a bad case of saddle points, where the gradient norm is small, while since the normalizer in Algorithm 1 is the sum of the historical gradient norm (let's say $g_1$ has its norm at $\Theta(1)$), the AdaGrad would get stuck around the saddle points, since it will do very small updates around saddle points.

- A more desirable result to explain the effectiveness of AdaGrad would be to show that AdaGrad not only converges to stationary points (which is shown in this paper) but also converges to points with good second order information (local minima rather than saddle points).

- I found the sentence above Eq. (1) "by choosing to output ... uniformly at random from the set of query points ... is bounded" a bit confusing. Does this mean the last iteration is not guaranteed to have small gradient norm (I can imagine somehow the algorithm could have oscillation behaviour, but not sure if this is the case here)? And does this imply we need to do some post-processing after running the AdaGrad method (which to my knowledge is not the case)? If this can be turned into a more direct result of last iteration convergence result with high probability, that would be better, since as I am aware of, there are expectation convergence results for last iteration convergence.

minor: Lemma 4.2: $a_i$ in the denominator should be $a_k$?
summary_of_the_review: Overall, I think this work provides a neat and elegant analysis for AdaGrad and several variants. It shows that AdaGrad behaves similarly in terms of expectation convergence and with high probability convergence. However, I found the results still unsatisfactory in terms of I did not see how those results could explain the good performances achieved by AdaGrad and its variants. To my understanding, this is more like verifying and improving existing analysis to some extent but lack of providing new insights.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides an analysis of adaptive learning rate scheme in stochastic non-convex settings. Under assumptions of smoothness and bounded stochastic gradients (a light tailed condition), it is shown that the sum of the gradient norms of the iterates of the non-convex algorithm is small.
In order to accomplish this, the analysis must deal with the standard difficulty for adaptive learning rates, which is that the learning rate depends on the current iterate and so makes it harder to apply standard martingale inequalities.
The final results include a dependence on the smoothness constant $L$ and variance $\sigma$ which are not explicitly used in the algorithm.
main_review: The paper addresses an interesting and relevant problem, and the difficulties present are significant.
I have two main concerns about the results currently.

1: Although it is true that the final result depends on the "unknown" $L$ and $\sigma$, it does not have a very good dependence on these quantities. In particular, the in-expectation results for adaptive methods would be more like
$$O\left(\sigma/\sqrt{T}\right)$$
while these results are more like $$O\left(\left(\sigma\sqrt{\log(1/\delta)}/\sqrt{T} + \tilde GL/\sqrt{T}\right)\right).$$ That is, when $\sigma\to 0$, the result does not have any asymptotic improvement. In fact, I believe a similar result is achievable with \emph{non-adaptive} SGD using learning rate $\eta_t = 1/\sqrt{t}$. In this case, applying standard martingale bounds to the second display of page 5 (which is fine since the learning rate is deterministic), would yield $$1/\sqrt{T} \sum_{t=1}^T \|\bar g_t\|^2 \le \Delta + \sqrt{\sigma^2 G^2 \log(T)\log(1/\delta)} + L\tilde G^2 \log(T),$$ from which some rearrangement provides a similar bound. Notably, SGD also doesn't require any knowledge of the smoothness or Lipschitz parameters. Thus, unless I miss some interpretation, this result seems to be more on the line of "the adaptive method doesn't *break* anything" rather than "the adaptive method is actually useful".

2: The high probability bound is a little weird, as it applies to just a sum of the gradients. What does this actually mean? For the in-expectation bounds I can actually produce an iterate that has a small gradient norm in expectation by randomly picking an iterate. Here if I randomly select an iterate I think the high-probability guarantee will be lost, so unless there is some other construction or better argument, it cannot actually provide any high-probability guarantees about any iterate. Since my feeling is that the point of the high-probability analysis is to say things about individual runs of the algorithm, this may limit the usefulness of the result. Now, this could be surmounted by simply calculating a batch stochastic gradient for each iterate as done in Ghadimi and Lan, but this seems to require a lot of gradient computations. Another alternative would be to use minibatch sizes of $\sqrt{T}$ for $\sqrt{T}$ iterations, but this would essentially average out all the variance and so we may possibly run into an even more extreme version of the issue in which the bounds do not obviously improve on non-adaptive methods.


summary_of_the_review: The paper considers and interesting and difficult problem. However, the results seem to fall short of realizing the ideal goals.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proves a high probability convergence rate for the first order algorithm, achieving the optimality of the probability and the convergence rate under this type of algorithm. 
main_review: I believe the conclusion is meaningful and important. The writing and presentation clearly shows the main steps of reasoning. By partitioning the proof into three steps in Sec. 4.2, with their corresponding lemmas, I can easily see the ideas and pinpoint to each separate proof. 

I can barely find weaknesses of the paper. I have a few questions below.

1. As far as I remember, the AdaGrad usually means an entrywise step size. Compared to the paper, I would rather say $\eta_{i,t} = (G_0^2 + \sum g_{k,i}^2)^{-1/2}$ and $x_{t+1} = x_t - diag(\eta_{i,t}) g_t$. The diagonal matrix approximates the inversed Hessian to accelarate. Does this paper apply to that case, and will there be an acceleration if the Hessian is truly diagonal?

2. I'm not quite familiar with the high probability reasoning, so it could be helpful to add in appendix a comparison with the papers in "High probability results" paragraph, say, what algorithms did they use, what are their result.

3. I think the usual "convergence in expectation" result also indicates the probability. $f(x)-f(x^*)$ is lower bounded by $0$, so a small expectation $Ef(x)-f(x^*)<\epsilon$ means that "with probability $p$, $f(x)-f(x^*)<\delta(p)$". Does a standalone argument about probability benefit? 
summary_of_the_review: I think the contribution is meaningful and the writing is clear. If other reviewers are not doubtful about the novelty, then I'll give an accept.
review_title: null

Meta-review: The paper provides a high probability analysis for Adagrad for smooth non-convex optimization and shows its rate of convergence to critical points. Both rates for deterministic optimization and for stochastic optimization are provided. The main contribution of the paper is that unlike for SGD they don’t require knowledge of smoothness parameter in advance and second, they prove high probability results. 

The reviewers lean positively towards the paper. One of the reviewers comments about the comparison with SGD which has some merit. The main comparison of this paper is w.r.t. ward et al 2019 and Zhou et al 2018 both of which prove high probability results. However, both these works require prior knowledge of smoothness parameter. The other axis of comparison is w.r.t algorithms like spider by Fang et al 2018 which uses variance reduction type techniques to obtain the optimal rate for critical point (here it is 1/sqrt{T} for norm square which is T^{-1/4} for norm and spider is T^{-1/3} for norm). Of course, an argument can be made for the fact that the algorithm here is closer to what is used in practice and more importantly, the assumptions there are somewhat stronger. 

In any case, the paper still has interesting results and I am leaning towards an accept.
Decision: Accept (Poster)