Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: **Summary**:

The paper focuses on estimating when stochastic gradient dynamics have reached a stationary phase by considering the inner product of pairwise stochastic trajectories referred to as threads. The chosen approach avoids strongly correlated estimates which leads to better mixing and more reliable identification of a stationary phase than previous work for certain problems. The proposed algorithm is specifically adapted for Deep Learning problems and performs well on the presented synthetic and real world problems.

**Reason for score**:

A prevalent problem of ML/DL is laid out and solution is provided that is backed by theory, intuition, simulations and empirical experiments and altogether presented in a systematic comprehensible manner. These are all constituents of a great paper that I also think provides a valid contribution to the field. 




**Pros**:

- The paper is well-written and makes good use of visual media to convey results and intuition.
- A drawback of previous methods for stationarity detection is the (potentially) correlated samples obtained from successive gradient steps. This did not seem to be a problem in the DL case presented in the experiments but would be for more general problems. The paper presents a clever way to address this problem. 
- All decisions regarding parameters and modifications to the algorithm are properly backed up with good arguments, empirical evidence and theory.

**Questions**:

- There is also one question regarding the implementation of SplitSGD for the Deep Learning experiments that I might have missed. Is it the case that each epoch of SplitSGD requires 2 passes through the training set or is it alternating between 1 epoch standard training and 1 epoch diagnostic?

- SplitSGD is generalized to use different optimizers such as SGD with momentum and Adam and I see no reason why other first-order methods could not be incorporated as well. In ML these optimizers often rely on a diagonal preconditioning (call it $P_t$) where the update $\theta_{t+1}= \theta_t - \eta_t P_t g_t$ is used. If we assume $P_t=P$ to be constant during the diagnostic we end up with average gradients of $P\bar{g}_i$ and $Q_i=<P\bar{g}_i^{(1)},P\bar{g}_i^{(2)}>=<\bar{g}_i^{(1)},\bar{g}_i^{(2)}>_{P^2}$. Do you know how this affects the estimates $Q_i$ and whether it would be necessary to invert the preconditioning for such adaptive methods? How was this handled for SplitAdam?

- In theorem 3.1 and 3.2 and by extension figure 3 the effects of large learning rates and long time-horizons for the diagnostic are compared. Let's assume the horizon $t_1$ is fixed to a "suitable" value. It then looks as if a more general adaptation scheme could be constructed from the condition in Eq.7. Denote the sum on the LHS of Eq.7 as $\Sigma$. If the learning rate is too small, the red histogram of Figure 1 is expected -> $\Sigma$ would be small, which for the chosen $t_1$ has not lead to stationarity. Would it then be possible to slightly increase the learning rate to bring the next diagnostic closer to stationarity? An extreme case of which could be to replace lines 8-12 of the algorithm with:
```
if S:
	decrease eta by factor gamma 
else:
	increase eta by factor gamma/2
```

Did you consider such an adaptation or see any advantages/disadvantages of such a procedure?



**Tips**:

- In figure 3 you could flip the colors in the left pair of histograms to have "stationary distribution as blue" consistently.  
- The x-labels of figure 6 are difficult to read. You could replace such a label with just a pair of parameters in larger size. Ex. "w=10, q=0.35" -> "(10, 0.35)" and explain the ($w$,$q$) setup in the caption.
- Search for "improvement is only mandatory is" and replace last "is" with "as"
- At the end of section 4.3 the values for $w$ and $q$ got mixed up.
review_title: Official Review #3

final_score: rating: 7: Good paper, accept
review_content: The paper introduces SplitSGD method that detects the stationary phase in the stochastic optimization process and shrinks the learning rate. The SplitSGD is based on the observation that before reaching the stationary phase, two random batches of data will likely to have the gradient aligned as the noise between different batches is dominated by the shared gradient, whereas after reaching the stationary phase, two random batches should have misaligned gradient as the gradient has become mainly noise. This observation is intuitive, and some theoretical results show that (a) at the beginning, the algorithm determines non-stationary with high probability, and (b) more important, the SplitSGD algorithm is guaranteed to converge with probability tending to 1. The experiment reveals the advantage of the SplitSGD method over alternative SGD algorithms for CNN, Resnet, and LSTM.

Personally, I feel this paper is good enough to be accepted. The intuition is neat, and the new approach, as supported by both the theoretical and empirical results, should merit significant values to be widely known to other scholars. The paper has made enough contributions and has high clarity in terms of writing.

Here are some concerns that I would suggest the author to consider:
1. The theoretical results are of course important, however, the proven results could appear expected and not have surprise, despite the many technical challenges. The proven results are either for the initial steps, or for the final state on whether the algorithm converges. To further enhance the significance of the theoretical results, it could seem better to establish results on the convergence process, such as the convergence rate analysis that the author in this paper already states would be “left for future work” and the analysis “appears to be a very challenging problem”.
2. The datasets in the empirical evaluation seem not to have large sizes, especially considering the availability of large datasets nowadays. It would make the paper more convincing if the authors can add larger datasets for comparison of methods.
3. The proposed method has gains over a number of alternatives in the simulation. The gap between the new method and the other methods appears not really large. More comparison could be helpful, although I do not think it is fully critical.
4. For the simulation results, as far as I understand, the SplitSGD has better test metrics and results in less overfitting. It would be very helpful if the authors could provide an intuitive explanation of why this is the case. Also, could early stopping achieve a similar performance?
5. Here is a typo: in Eq (5) and in line 21 of algorithm 1, $\theta^{(k)}_{i\cdot l}$ should have $i\cdot l +1$ rather than $i\cdot l$ in the subscript, to match the definition in Eq (4).
review_title: Official review for 1120

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a sign-based test to determine if a stochastic process is in its stationary state or not. Unlike Pflug test, this test uses two independent trajectories to build its test. It divides each trajectory into w parts and averages the gradients insides each part. Then measure the similarity of each average of one trajectory to the corresponding average from the other trajectory via dot product and then counting the negative signs and positive signs. When the negative signs are above a threshold then the process is its stationary station. Then it shrinks the step size of SGD for future iterations. 


Comments: 
1- Several parts of the paper needs more clarification and explanations: 
It is not clear what the statistical intuition behind the splitting test is and why we should expect a more robust test. 
The notion of informativeness is mentioned in the introduction but it is not used in the rest of the paper. Besides in its definition, it doesn’t say how they measure the “relatively largeness” of gradient w.r.t. the noise.
Fig 3 just represent eq 3 and gives no extra information. If it means something else such as the inner product for nonstationary is positive with high probability it should be mentioned clearly 
 In related work: 1- Le Roux et. al. don’t detect stationarity. Why do you mention it? 2-  This work “Scott  Pesme,  Aymeric  Dieuleveut,  and  Nicolas  Flammarion.   On  convergence-diagnostic
based step sizes for stochastic gradient descent. ICML20” is highly relevant which is not mentioned. 
In assumption 4, there is a parameter m which is not clear what it is or there is a limit on it, for example, can m be infinity?. In Thm 3.1. It doesn’t say what sd(Q_i) is.
It is not clear the connection between the result of Thm, 3.1. And the line above it which says with high probability P(Q_i <0) is small. It would be nice to mention how small the \eta should be to guarantee the ineq. in this theorem. Besides we know that in a stationary state E(Q_i) is zero ( assuming after t_i steps we are in the stationary state ). Then what does this result mean?      
For both Thm’s 3.1 and 3.2 it would be helpful to add an interpretation for their result. 
2- For the empirical results 
I think you should compare against  “Lang, H., Zhang, P., and Xiao, L. (2019). Using statistics to automate stochastic optimization” instead of FDR since FDR test has high variance. 
You should add a comparison against “Scott  Pesme,  Aymeric  Dieuleveut,  and  Nicolas  Flammarion.   On convergence-diagnostic based step sizes for stochastic gradient descent” which is a distance-based test instead of sign-based. 
Fig 4 shows that your test does not work when the step size is too small. However, all your theories hold when the step size is small. SGD ½ is as good as yours. 
For your DNN results, are this results average of several runs? If yes, you should add the std bar into the graph, If not why should we rely on the results? 

review_title: No clear advantage over existing methods. 

final_score: rating: 3: Clear rejection
review_content: Review: This paper proposes SplitSGD, a novel heuristic for adapting the learning rate. This novel learning rate schedule is based 
on the identification of stationary phases, where for stationary phases the authors refer to the training stage where the noise
in the gradient estimate becomes dominant and therefore the iterates start jumping around a stationary point.
The authors develop an heuristic to detect such phases. When a stationary phase is detected, the learning rate is 
decreased of a factor $\gamma$. Under some assumptions, the authors provide a theoretical analysis for the
stationary phase detection mechanism which also underlines the relation with the learning rate value. SplitSGD is then benchmarked and compared against some of the standard learning rate decaying heuristics generally adopted 
in combination with SGD or other first order stochastic methods.
___________________________________________________________________________________________________________________ 

+ Overall the paper is well-written and clear.

___________________________________________________________________________________________________________________
 
Concerns: 

1. The learning rate, also called step-size, can be interpreted as a brutal approximation of the local curvature with a scaled identity matrix. All the work on second-order methods attempts to refine this brutal approximation with better estimates of the local curvature. Despite being the learning rate and how to adjust it the central topic of this paper, nothing is mentioned regarding the
fundamental relation of the learning rate and the local curvature.


2. There are some wrong statements here and there in the paper, i.e.
"""
Specifically, in the case of a relatively small learning rate, we can imagine that, if the number of iterations is fixed, the SGD updates are not too far from the starting point, so the stationary phase has not been reached yet.
 """


3. The authors claim to propose an optimization method while what they are proposing is an heuristic to decrease the learning rate in an adaptive fashion. 


4. The costs of the stationary phase check are not discussed but the authors just briefly mention that SplitSGD comes with no significant extra costs. This does not seem to be the case though.


5. The literature on increasing the batch size toward the final part of training is not discussed at all, as well as other state-of-the-art heuristics to deal with the noisy gradient estimate.


6. The benchmarks are limited as the authors are not considering state-of-the-art learning rate  decaying heuristics such as the cosine decaying schedule. In addition, they could show more solid empirical results by letting an hyperparameter optimizer such as BOHB choose for the best learning schedule. Otherwise it is hard to say that the superior performance of SplitSGD is not a consequence of a wrong hyperparameter tuning of the competitors.


7. I think the deep learning community at this stage needs less work on learning rate heuristics and more attentions on the theoretical analysis of the geometry of the landscape, novel optimization methods with theoretical guarantees and solid work on generalization properties, as there has been enough works on such heuristics which often ends up 'adding extra noise' and therefore constitute an obstacle in the process of bringing clarity and understanding in the field.


review_title: Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic

Meta-review: This paper proposes to automatically determine when the SGD step-size should be decreased, by running two "threads" of SGD for a bunch of iterations, divide those into windows, and then look at the average inner-product of the gradients in the two threads in each window. If the inner-product tends to be high, that indicates that there is still "signal" in the gradient and it should not be decreased. If it is low, that indicates that the gradient is mostly "noise". In the latter case, the learning rate is decreased by a factor of gamma and the length of the next phase is increased by gamma.

Theorem 3.1 essentially assumes smoothness, a bounded fourth moment for the stochastic gradient, and that the stochastic gradient error is not too far from isotropic. Then it shows that if the step-size is set small enough, the standard deviation of the diagnostic (Q_i) can be upper-bounded in terms of the expected value of Q_i. It follows that the probability of Q_i being negative cannot be too large (bounded in terms of the step size eta and the length of the windows l).

Theorem 3.2 adds the assumption of strong convexity and weakens the assumption on the gradient to a bounded second moment. Then it upper-bounds the expected value of the diagnostic in terms of its standard deviation.

Proposition 3.4 gives a proof of convergence. As far as I can tell the proof is essentially that the learning rate decay can't be much worse than what would happen if the diagnostic *always* set to decrease. In particular: (1) It's impossible for the learning rate to decay too quickly, since the length of each phase is increased by gamma whenever the learning rate is decreased by gamma. (This is a "non-adaptive result.) (2) The learning rate will eventually decay with probability 1.

Various concerns were brought up by the reviewers. Perhaps the most strongly voiced concern was that the proposed method is a heuristic rather than a method with a rigorous guarantee. For my part I am in agreement with the authors and other reviewers that heuristic methods for decreasing the learning rate are worthy of study given the large practical importance of this problem.

I concur with the concern raised by some reviewers that the theoretical component of the paper may not have little explanatory value for the results that are given. The assumption of strong convexity is not a major concern to me. (Though not true it can still give intuition.) More concerning is that theory essentially takes a fixed step-size scheme (repeatedly decrease the step size by gamma and increasing the length of a phase by gamma) and then shows that the diagnostic can’t be too much worse. This isn’t in keeping with the motivation of being adaptive.

The reviewers were also concerned about the explanation of better results due to less overfitting. This may be true, but the theory makes no mention of overfitting.

There was a consensus that the experimental results were promising, though some minor issues were raised.

While the direction explored in the paper has value, there are enough open questions about the relationship of the theory to the experimental results to warrant another round of review.

Small thoughts, not significant to acceptance:

The current heuristic runs two separate threads and looks at the inner-product of those gradients. An alternative to this would be to run a single thread along with a "ghost" thread that computes a different gradient at each iteration. It would be great to comment on the difference and why one might be superior to the other. A more radical alternative would be to run a single thread, but then compute the diagnostic on each half of the minibatch. A more radical alternative still would be to analytically do that splitting many times and average the results. This seems like it might simultaneously reduce the variance of the diagnostic and also reduce the computational cost.

2. The current heuristic runs two threads. Is there a tradeoff if you run more?

3. The statement of theorems could be more user-friendly. To understand Thm 3.1, I needed to search o find the definitions of: eta, l, i, w, Q_i. With a small amount of effort this could be re-written to remind the reader that w is the number of windows, l is the length, eta is the stepsize, etc. It is particularly unfortunate that sd() is never formally defined (only by reading the appendix did I discover that this was the standard deviation.)

4. The fact that the length of threads is always increased by a factor of gamma whenever the step size is reduced by gamma seems contrary to the spirit of the proposed diagnostic. After all, this "bakes in" a kind of "fastest possible" decay schedule. If the diagnostic were fully reliable, shouldn't this not be necessary? The decision to add this doe not get nearly enough discussion in the paper in my view.

5. I think it might be clearer to re-state theorem 3.1 including the Chebyshev result after it.
Decision: Reject