Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the problem of finding a first-order stationary point of a non-convex function which decomposes into a finite sum of $L$-smooth functions. The main motivating prior work is the SPIDER algorithm, which is an stochastic variance-reduction algorithm with non-adaptive step-sizes which achieves an order-optimal convergence rate for this setting. However, this algorithm is only guaranteed this convergence rate when the step-sizes are carefully tuned to problem parameters (e.g., the accuracy $\epsilon$ and smoothness constant $L$). Since these parameters may not be known a-priori, and the smoothness constant in particular may be difficult to compute, the authors aim to design an algorithm which does not need to be tuned w.r.t. these parameters. They propose a variant of the SPIDER algorithm which uses adaptively-chosen step sizes, and show that, up to logarithmic factors, their method obtains order-optimal convergence without tuning the step-size with $\epsilon$ or $L$.
strengths_and_weaknesses: **Strengths**:
This paper addresses an important problem of designing optimization algorithms which are guaranteed to converge even when the parameters of the objective function (namely, the smoothness constant) are not known, or are underestimated. The exposition of their algorithm, ideas, and analysis are well-written, and pretty concise and clear. Overall, I found this paper very accessible and easy to follow.

Moreover, except for some minor typos, some (inconsequential) weirdness w.r.t. dimensional analysis, and some expressions which are not fully explained, the results of this paper appear correct to me, after a thorough reading of the proofs.

**Weaknesses**:
There are a number of issues I came across in the paper (both technical, and in regards to prior work) that should be addressed. I will outline them below:

> _Discussion of prior work_

Your paper has missed a substantial amount of prior work which is very closely related to your paper. Indeed, the step-sizes that you consider are precisely the AdaGrad-Norm step sizes, introduced in “Less regret via online conditioning” (arXiv:1002.4862, 2010) in the online convex opt context, and analyzed further by “Scale-Free Algorithms for Online Linear
Optimization” (ALT’15) (again in the context of online), and later by, e.g., “AdaGrad stepsizes: Sharp Convergence over Nonconvex Landscapes” (ICML’19), “The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance” (COLT’22), and minor variations of this step-size by “On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes” (AISTATS’19), “A High Probability Analysis of Adaptive SGD
with Momentum” (ICML’20 workshop). There are many other papers in this line of work, and this is only a small sample.

Particularly related to your work is “The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance”, which deals with unbounded gradients, and guarantees their convergence rate without tuning the step size w.r.t. the smoothness constant $L$. In fact, Lemma 4 in your paper is essentially the same as Lemma 2 in that paper.

I believe your paper should include a discussion on the line of work of AdaGrad-Norm, since it is the algorithm you consider in this paper. Further, it would be good to draw connections to the other recent works which avoid the need for assumptions of bounded gradients.

Also, when referencing the AdaGrad algorithm, I would suggest also citing “Adaptive Bound Optimization for Online Convex Optimization” (COLT’10), which proposed the AdaGrad algorithm concurrently (and in the same conference) to the Duchi, Hazan, and Singer paper.

> _Technical novelty and limitations of results_:

I have some observations about the results of your paper in relation to those of prior work.

_The step-size choice_: While it is nice that your step-size choice does not need to be tuned w.r.t. the smoothness parameter $L$, this is not surprising to me, since AdaGrad-Norm is well-known to have this nice property (the earliest reference observing this property which I am aware of is “AdaGrad stepsizes: Sharp Convergence over Nonconvex Landscapes” (ICML’19), but I would not be surprised if it was observed in earlier work also).

In that prior work (as well as follow-up work to it), AdaGrad-Norm has an order-optimal convergence rate for _any_ choice of parameters. This seems to stand in contrast to your algorithm, where the step-size is tuned w.r.t. $n$ (which is, in a sense, a parameter which controls the variance, according to Lemma 5). It is not very intuitive to me why the step size in your setting should be tuned with this parameter (and, in particular, why the multiplicative factor of $1/n^{1/4}$ should be there). If $n = \Theta(T)$ (which I would assume is typically the regime of interest?), then this step size is typically smaller than $1/\sqrt{T}$, which I find somewhat surprising.

It would be very interesting, and perhaps a stronger result, if you could guarantee your convergence rate without tuning these parameters. Do you think this is possible? I noticed there seem to be a couple of places where there is some (small amount of) slack in your analysis (see my second comment in _Minor typos in some lemmas_). Do you think that by using this extra slack, your analysis could be improved to avoid this inverse multiplicative dependence on $n$ in the step-size? One possible place that I see where this (maybe?) could be improved is by more carefully upper-bounding in the second step of line 522, using the fact that for any $\lambda > 0$,
$$
-\gamma_t \nabla_t^\top (\nabla f(x_t) - \nabla_t)
\leq \frac{\lambda}{2} \lVert \nabla_t \rVert^2 + \frac{1}{2\lambda} \lVert \nabla f(x_t) - \nabla_t \rVert^2,
$$
and optimizing the choice of $\lambda$, perhaps as a function of $n$. In your analysis, you simply use $\lambda = 1$, but perhaps there is a better choice here that would improve your result?

_Convergence in “small-noise” regime_: Most results in stochastic first-order optimization (including all of the analyses of AdaGrad-Norm that I am aware of) obtain a faster convergence rate in the setting where the variance of the stochastic gradients is vanishingly small in $T$. In your setting, this perhaps could be viewed as many (or perhaps all) of the functions $f_i$ being the same (in this setting, your algorithm would obtain essentially a full estimate of the gradient for most time steps). I believe this should manifest itself as having a better dependence on $n$ in your convergence rate. Is there any way to quickly see this from Theorem 1? Or would a new, more refined analysis be needed to observe this phenomenon? 

_Technical novelty_: The results in this paper have a simple and concise proof, which is nice! However, it seems (at least to me – perhaps I am missing something!) that the results seem to follow from a straightforward combination of techniques from the SPIDER paper, together with prior techniques used to analyze AdaGrad-Norm in the stochastic setting. In this sense, the results of this paper are not too surprising to me – I would expect that the AdaGrad-Norm step size applied to SPIDER would have a similar convergence rate without having to tune w.r.t. $L$. Were there other (perhaps subtle?) challenges that you faced in obtaining these results? It would be nice to highlight these, if so.

> _Proof of Theorem 1_

I think that the first inequality in proof of Theorem 1 (line 545) needs a bit more explanation. First, there is a small typo, as there should be a sum over all times on the left-hand side. Second, you should explicitly say first that Lemmas 5-7 imply that
$$
\frac{1}{n^{1/4} \sqrt{T}} \mathbb{E}[\lVert \nabla_t \rVert] \leq 2\Delta_0 + 1 + \frac{L \log(...)}{\sqrt{n}} + L^2 n \mathbb{E}[\gamma_t^3 \lVert \nabla_t\rVert^2].
$$
That inequality is easy to see by just combining those Lemmas. Then, you should show how to relate the LHS to the quantity you are interested in, using the observation that:
$$
\frac{1}{T} \sum_t \mathbb{E}[\lVert \nabla f(x_t) \rVert]
=
\frac{1}{T} \sum_t \mathbb{E}[\lVert \nabla_t + \nabla f(x_t) - \nabla_t \rVert]
\leq
\frac{1}{T} \sum_t \mathbb{E}[\lVert \nabla_t \rVert + \lVert \nabla f(x_t) - \nabla_t \rVert],
$$
together with the fact that, by Lemma 5,
$$
\frac{1}{T} \sum_t \mathbb{E}[\lVert \nabla f(x_t) - \nabla_t \rVert]
\leq
\frac{L n^{1/4} log(...)}{\sqrt{T}}.
$$
I am not sure if the above is very standard in this line of work (I suspect that it probably is), but since it was not written anywhere in this paper, I originally thought there was a serious mistake in the proof of Theorem 1. I would strongly suggest that you elaborate on that inequality from line 545 so that others don’t have to think as much about this :)

> _Dimensional analysis_:

There are many places in the paper where the dimensional analysis of your results does not quite check out. For instance, the quantity inside of the $\log$ in Theorem 1 is not unitless, since $n L T \lVert \nabla f(x_0) \rVert$ has units $f^2 / x^3$. For a detailed discussion on the problems with taking a logarithm of a quantity with units, you can see, e.g., the discussion in Appendix A of arxiv:2002.11259, “Dimensional Analysis in Statistical Modeling”. There are a number of other places in your paper where this problem also appears, e.g., Lemma 4, 5, 6, among other places.

I would like to clarify, before continuing, that I don’t think this invalidates your results (though it should be either fixed or clarified in your paper). Indeed, it seems that the source of this “strangeness” comes from your choice of step-size. Indeed, in the denominator, you add a “unitless” quantity, $n$, with a quantity with units of ($f^2 / x^2$), $\lVert \nabla f(x_t) \rVert^2$. Additionally, to make the units of the update check out (i.e., to make $\gamma_t \nabla_t$ have units $x$), the constant scaling the step-size ($1/n^{1/4}$ in your case) should have units of $x$. Thus, if one were to change the units of the domain $x$ or of the function $f$, then these terms in the step size would need to be scaled accordingly.

In order to track these units through your analysis (which, in my opinion, is one of the easiest ways to quickly sanity-check an optimization result), it would make things much easier if you included constants in your step size, scaling the multiplicative $1/n^{1/4}$ and additive $n^{1/2}$ terms. These constants would implicitly have the correct units, and would make verifying your result much easier on a quick read.

To conclude – I don’t think this issue creates any contradictory results for your guarantee. However, it makes reading some of the results a bit confusing, and throws some red flags (especially seeing a quantity with units inside a log). So I would suggest this issue be fixed throughout the paper.

> _Minor typos in some lemmas_:

I came across a number of minor errors/omissions (all inconsequential) in your technical results.

_In the proof of Lemma 4_,  on line 507, it is not clear to me why $L$ and $\lVert \nabla f(x_0) \rVert$ should be larger than $1$ w.l.o.g. When this is not true, then the last inequality in the following line is not true. Why not just replace the multiplication with an addition here?

_Not an error, but_ it seems to me (unless I’m mistaken) that, on the second line of the inequality following line 525 (inside proof of Lemma 6), that $L$ can actually be $L/\sqrt{n}$. Perhaps this makes some constants in your convergence rate slightly smaller? Not sure…

_Also in the proof of Lemma 6_, in the third inequality on line 527, I believe you are using the fact that:
$$
\sum_t \frac{a_t}{\sqrt{\sum_{s\leq t} a_s}} \geq \sqrt{\sum_t a_t}.
$$
This, of course, is a standard result which can be proven easily by induction. However, it is not written anywhere in your paper. Perhaps it should be included in the statement of Lemma 1? In fact, I didn’t find anywhere in your paper where Lemma 1 was used, and it seemed to me you only needed the lower bound. Perhaps you can just replace Lemma 1 with this bound?

_One last thing in proof of Lemma 6_, it seems that the $L^2$ inside the $\tilde{O}$ on line 528 should actually be replaced by $L/\sqrt{n}$. This makes some constants in later results slightly better.

_Small comment in proof of Lemma 7_, on lines 532-533, you say that “...which we have to do to circumvent non-measurability issues”. I was confused by this statement, as I don’t see why having a decreasing step size has anything to do with measurability… Perhaps this comment should be changed?

_Another small typo in proof of Lemma 7_, the 3rd equality on line 536 should be an inequality I believe (it’s equality by adding $- \gamma_{t-1}\lVert \nabla f(x_t) - \nabla f(x_{t-1})\rVert$). Not a big deal, just wanted to point this out.

questions: I have outlined my main comments and questions in the **Limitations** section above. The main points that I would like to see addressed in the rebuttal are the following:

- A more detailed discussion of prior work, and its relation to your work, and some techniques you use (e.g., to removing bounded gradient assumptions) should be added to the paper. I would like to see an outline of how you plan to incorporate this discussion in your paper.
- I am particularly interested in hearing your responses to the points raised in _Technical novelty and limitations of results_, and would be interested to see if the results of your paper could be improved as suggested there, or if there are significant challenges in doing so.
- I think it is important to fix the issues regarding _Dimensional analysis_ in your paper, as these discrepancies that are currently in your results make quickly sanity-checking the results very difficult for the quick/casual reader.
- Regarding the missing lemmas/inequality explanations, I would like to see a discussion about this. Do you plan to incorporate these changes? Or have I missed something simple here?

**Please note** that my current score for this paper reflects the fact that there are a number of changes that should be addressed by the authors before it is ready for publication. I will happily upgrade my score if the concerns I have raised are satisfactorily addressed.

limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents a convergence analysis of an adaptive variance-reduction method (AdaSpider), which combines Spider method with the global(norm) version of AdaGrad stepsizes, for the minimization of smooth functions with a finite time structure. In particular, they show that AdaSpider can get an $\epsilon$ stationary point with $\tilde{O}\left(n + \sqrt{n}/\epsilon^2 \right)$ oracle complexity in expectation. Numerical results are also conducted. 
strengths_and_weaknesses: This paper is well written and easy to follow. As far as I know, it is the first parameter-free nonconvex variance reduction method. In this way, I tend to support accepting this paper. Yet I have the following concerns.

AdaSpider vs. Spider/Spiderboost: The advantage of AdaSpider is parameter-free, i.e. without prior knowledge of problem dependent parameter smoothness L/less tuning. However, theoretically, it has a worse dependency on the smoothness L as well as pays a logarithmic term compared to Spider. Also, though the method requires less tuning, it seems no better (sometimes worse) than the other variance reduction methods as shown in the experimental part. 

Minor:  Line 83, the dependency on the smoothness should be $L^4$?




questions: I'm wondering if it is possible to extend the analysis to the convex setting. Will AdaSpider still yield an (almost) optimal oracle complexity? 
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposed a adaptive variant of Spider, called AdaSpider, for solving non-convex and smooth finite-sum optimization problem with the complexity of $\tilde O(n + \sqrt{n}/\epsilon^2)$ of finding a first-order stationary point. In addition, the proposed AdaSpider is a parameter-free algorithm, which is pratical in real applications. Finally, the authors provided some experimental results on non-convex optimization and neural networks. 
strengths_and_weaknesses: Pros: The orginization of this paper is good and its presentation is clear to me. The proposed AdaSpide is parameter-free, which is a significant contribution to the non-convex optimization community. The experiments with neural networks are studied.  

Cons: The advantage of its convergence analysis over the standard one, i.e., Spider (Fang et. al), is not clear. Due to the additional $\log$ term, the convergence result of the proposed AdaSpider is even worse than Spider and Spiderboost (Wang et. al). The experimental results show that the proposed AdaSpider is worse than Spiderboost.  
questions: It seems the analysis heavily follows the Spider paper, which is very straightforward. I can not see the advantage of convergence analysis in this paper. Besider, the experimental results reveal that Spiderboost is better than AdaSpider. Can you explain?
limitations: No.
review_title: null

Meta-review: metareview: After discussion with the authors, all reviewers are satisfied with the technical quality of the paper. Achieving smoothness adaptivity in variance reduction is a significant result.
confidence: Less certain
Decision: Accept