Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper investigates the step decay schedule (constant then cut) for SGD. It provides theoretical analyzes of this strategy in strongly-convex, convex, and non-convex settings showing near-optimal results. Empirical experiments illustrate its advantage over other popular optimizers.
main_review: The step decay (constant then cut) strategy is widely used in training deep neural networks. There have been quite a few works dedicated to it, both theoretical and empirical. This paper does a great job in synthesizing the related works, identifying their contributions and limits, and pointing out where this work stands.

This strategy is of course not novel, nor are the rates they obtained in any setting, but providing the theoretical guarantees for the step decay schedule as proved in this paper for various settings are new. In addition, the sampling scheme of being inversely proportional to $\eta_t$ is novel and very intuitive in giving weights to last iterates.

Some of my concerns are:
1. The assumption on the upper-boundedness of $f$ is worrisome, especially when it appears in the bound with the term $f_{max} - f^*$ showing that if it is unbounded then the bound is trivial. If the domain is bounded then this assumption would be more natural but for unbounded domain, this assumption seems too restrictive. Note that other results typically include a term $f(x_1) - f^*$ which is fine as $f(x_1)$ can be manually selected and easily be bounded. Looking at the proofs, however, the term $f_{max} - f^*$ is not just a simple upper-bound of $f(x_1) - f^*$ and the assumption on $f_{max} < \infty$ is indispensable.
2. In the paper on exponential step sizes [Li et al., 2020], they also studied the cosine step sizes and showed that it also performs really well and surpasses the exponential step sizes and the step decay in some settings. Also, in their paper, the step decay schedule has the flexibility of using different inner-loop sizes thus should be different from your definition in this paper. Hence, I would like to see a comparison with it.
3. I see that you answered Yes to Checklist 3.a, but could not find your codes on implementing the algorithm and comparing with other optimizers, apart from download link to datasets you used.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: 
This paper studies theoretical properties and practical efficiencies of a step decay step-size policy for non-convex, convex and deep learning problems. The main contribution is to establish a novel convergence guarantee for a practical step decay step-size scheme of SGD beyond existing results on least-squares problems. 

main_review: 
It is known that decaying step sizes too fast may result in poor performance in SGD. Step decay step-size policies are hence often used in non-convex optimization such as deep learning problems. They can sometimes achieve a fast convergence towards solutions with a good generalization performance. This papers focuses on a practical step decay step-size policy and two stopping rules (either a random iterate or the last iterate), and analyzed their theoretical properties. The practical performance are then evaluated against popular step-size policies. 

The paper is well-organized and well-written. 
I have a few questions/comments: 
* The first main contribution, such as the removal of ln(T) factor for the 1/sqrt(t) step-size, comes from an important assumption that the objective function is upper bounded, isn’t it? It seems that this assumption is in all the results of non-convex cases, therefore it is better to be mentioned in the introduction, e.g. to make a comparision on such assumptions with related works. 
* In Figure 3, why the method with Step-decay has a loss that is increased over epochs 60-110? 
* Enlarge the legend size in all the figures if possible. They are too small to read. 
* Typo: line 16 can be, line 77 for. 

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors present a new analysis of SGD with the very popular step decay implemented in all DL framework for instance. They provide convergence guarantee in various setting and show that the classical exponential decay is a very special case of their result, still achieving the state of the art result in this special case. They also provide some lower bound to show tightness of their results and finally propose a new sampling of the iterates that allows to remove some annoying log term in the convergence bound.
main_review: \paragraph{Strengths:}

The authors provide new convergence result on a very popular setting, used in practice but not studied theoretically. They provide some comprehension on this scheduler and their general bound allows to understand how to choose optimally the length of the plateau.
Moreover their general analysis is sufficiently tight to be able to recover known results of another scheduler as a special case.

\paragraph{Weaknesses:}

In Theorem 4.1, 4.3 and 4.4, the condition "bounded gradient oracle" with the strong convexity is very problematic in my humble opinion. Indeed, bounded gradient oracle implies that the (deterministic) gradient of the objective function is bounded as well, while strong convexity implies it is lower bounded by the distance of the iterate to optimum. The 2 conditions combined together implies that the authors assume the iterates to be bounded, which is problematic to me as this is not an assumption on the problem, but on the result itself, excluding some possible scenario.
A minor weakness is that to reach the sqrt convergence bound, one needs to know in advance the number of iterations.

\paragraph{Correctness:}

I have not check all the proofs in details, but from what I checked, I have not spotted any mistake.

\paragraph{Clarity:}

The claim is clear and results follow. I would still make a couple of very minor suggestions to make some point clearer:

- Definition 4: I m a bit confused by the definition of subgradient. I generally consider the subgradient is precisely the set of vector verifying the inequality provided in Definition. Therefore a convex function is a function which subgradient is non empty in any point. And for non convex function, we need a new definition of the subgradient. For sake of clarity, could the authors add the definition of $\partial f(x)$ before using it?
- Theorem 3.2 l.166: it became clear to me after equation 5, that $N = \log_{\alpha} T / 2$ actually meant $\frac{\log_{\alpha} T}{2}$, and not $\log_{\alpha} \frac{T}{2}$. In my humble opinion, the lack of parenthesis is confusing. Could the authors either add parenthesis, or use "frac" or replace the division by 2 by a sqrt inside the log? I think it would improve clarity here.
- l.181: I think the authors means that when $V$ gets large, it doesn't slow too much the convergence of the algorithm in the sense we can bound the rate uniformly in $V$. In that sense, I think we can say, the convergence bound inn not affected by very large $V$. However, "the convergence bound unaffected by the noise variance" can bring a confusion as a reader can understand that the bound does not depend at all of $V$ and we can derive, in the stochastic setting, the deterministic setting's bound, which I think is not the case here.

\paragraph{General remarks and suggestions:}

\begin{itemize}
- l.16: "can either be"
- l.67: "smooth with Lipschitz continuous gradient": isn't repetitive?
- Algorithm 1: To my point of view, " inner-loop size S = T/N" should go after the input line, as $S$ is not an input but some value the method computes from inputs.
- l.175: there is a typo here, a $T$ is missing into the log
- l.191-192: the authors propose here to consider $\alpha = \left(\frac{\beta}{T}\right)^{-1/T}$ and then $\beta = O(\sqrt(T))$. Note that Theorem 3.2 suggests to consider $N$ such that $\alpha^N = \sqrt(T)$. In the special case where $S=1$, then $N=T$, this equality suggests the choice of $\alpha$ to be $alpha = \sqrt(T)^{1/T}$ which is aligned with l.191-192's choice. I think it would worth adding a word on this. Especially since the authors say that the choice $\alpha = \left(\frac{\beta}{T}\right)^{-1/T}$ comes from another paper. I think they should stress they not only make this choice based on another paper, but that it is also a consequence of a very special case of their own Theorem.
\end{itemize}

\paragraph{Conclusion}

I think this paper brings interesting new analysis of some very used technique in practice. In my humble opinion, this type of results is of great importance for the community to understand what makes this scheduler works well and then have insight on how to tune it (choose N or equivalently S, and choose alpha). Even if the proposed tuning depends on inaccessible noise of gradient, or on the final number of iterations, I think those results are interesting and open future work. For instance estimate V to try to set $\alpha$ without exterior knowledge, or set $N$ independently of $T$ by for instance, changing it online. I would vote the accept the paper. However, in my humble opinion authors should consider either removing theorems using contradictory assumptions or fix them if possible.
limitations_and_societal_impact: I think this section does not apply for this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proved convergence results for SGD with step decay step-size (the step size is decayed by some factor after certain iterations). 

In the smooth non-convex setting, this paper sampled the output from $\\{x_t\\}$ with probability of $x_t$ being $O(1/\eta_t).$ Based on this novel approach of sampling the output, the authors 
1. proved the first convergence bound for SGD with step-decay step-sizes on non-convex problems and achieved a $O(\ln T/\sqrt{T})$ rate towards a stationary point, which is comparable to the folklore results for $\eta_t = O(1/\sqrt{t})$ step-size;
2. improved the convergence results for exponentially decaying step-size, which allows larger initial step size compared with previous work;
3. improved the convergence rate from $O(\ln T/\sqrt{T})$ to $O(1/\sqrt{T})$ for the $1/\sqrt{t}$ step-size.

For the strongly convex and smooth functions, this paper proved an $O(\ln T/T)$ convergence rate for the last iteration, which generalized the result of Ge et al. The paper also proved a $O(\ln^2 T/T)$ convergence rate for the strongly convex and non-smooth functions.

In the experiments, the authors verified that step-decay step-size scheduling have better performance in training neural networks compared with constant step size or polynomially decaying step-size. 
main_review: I think this is a good theory paper that studied the convergence rate of SGD for different class of functions under step decay step-size. There are not many theoretical guarantees for SGD with step decay step-size. I believe this paper is a good step along this direction. 

It's an interesting idea to sample the output from the trajectory with the probability of each point inverse to the step size. This novel sampling scheme allowed the proof of the convergence bounds with step-decay step-sizes and also allowed the improvement of some other results. I think this sampling scheme might be of interests also in other settings, and also might be useful in practice.

Some suggestions:
Since this is mostly a theory paper, I think it might be good to talk more about the challenges in the proof and also the technical contributions. Currently, the results are well explained, but it's unclear what the novelty of the analysis is and how the proof differs from the previous works. 
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: This paper analyzes the step decay schedule (constant and then cut) for nonconvex optimization problems, showing that it can find an approximate first order stationary point in O(ln T/\sqrt{T}) rate. Most reviewers found the result interesting and that it gives a better understanding of the step decay schedule. There are some concerns that should be addressed in the revision: 1. clarifying why the requirement on boundedness of f can be replaced by E[f(x_t) - f(x^*)] and why the latter expectation can be bounded in natural cases; 2. detailed comparisons with previous results acknowledging that similar (or even better) rates were achieved by different algorithms in all the settings.
Decision: Accept (Poster)