Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: Tail-averaging is a very useful trick, in both theory and practice, to improve the performance of iterative learning/optimization method. Yet, it introduces an important hyperparameter, the starting point for the tail-averaging. This work proposes a two-tailed averaging method as an adaptive and hyperparameter-free alternative to the tail-averaging method. Under suitable conditions, it is proved that two-tailed averaging has many good properties, inclduing being (1) anytime, (2) adaptive, and (3) optimal once in a while. Besides to the method and theory, some experiments are conducted to verify the advantage of two-tailed averaging. 
strength_and_weaknesses: # Strength 
1. Overall I think the paper is written well. I find the problem well motivated, that treating with the hyperparameter in tail-averaging might be painful, so we need a fix to that. 
2.  The proposed two-tailed averaging is novel to my knowledge. 
3. Both theory and experiments are presented for better demonstrating the advantages of  two-tailed averaging. 

# Weakness
1. It is claimed that two-tailed averaging is "adaptive" and "hyperparameter-free". However I find this a bit misleading, because the procedure needs to be able to evaluate the "loss" periodically. Note that the "loss" refers to the targeted objective to be minimized if I understand correctly. For example, in the context of stochastic optimization [Jain et al, 2018], the "loss" refers to the population loss. But being able to evaluate the true loss is a very strong requirement, and makes the point of "hyperparameter-free" less interesting. For example, one can easily come up with a variant of tail-averaging that is "hyperparameter-free" provided the ability to evaluate the loss. Let us consider the setting of [Jain et al, 2018] again, one can simply save all the SGD iterates, and evaluate the loss over all possibilities of tail-averaging (or any general weighted averaging of the iterates), and output the optimal one --- this is "hyperparameter-free" and "optimal". I would like to see some discussions on the requirement of accessing the true loss. I just think this is too strong in many settings. 


2. I think the current presentation is somewhat "abstract". Perhaps the authors can discuss a potential application of the proposed two-tailed averaging in some theory/application problem? As the authors mentioned [Jain et al, 2018] many times, could you formally state a bound for two-tailed averaging in the setting of learning least squares with SGD, and compare it to the one obtained by tail-averaging? Being "anytime", "adaptive" and "optimal once in a while" sounds very cool but I would like to see some more specific benefits of using two-tailed averaging. 


3. I also think the assumptions could have been checked with a specific exemplar problem. The current assumptions are just very abstract and I do not immediately see how applicable/realistic they are. 



clarity,_quality,_novelty_and_reproducibility: Clarity is fine. 

Quality needs some discussion. Please see my questions above. 

Novelty is good. 

Reproducibility is good. 
summary_of_the_review: Please see above. Due to the mentioned issues I would like to keep my score low. I would like to hear the authors rebuttal to see whether or not I have misunderstood anything.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This submission proposes a new iterative averaging scheme for stochastic
gradient methods. 
The scheme, which works by maintaining two iterate averages
at any given time, manages to be parameter free by setting the average length
parameters dynamically based on the validation loss. 
As such, it is parameter-free unlike suffix/tail averaging, where the tail 
length parameter must be specified a-priori.
The authors prove that their "two-tailed" averaging scheme is optimal at
specific iterates infinitely often ("once in a while") under assumptions
on the behavior of the validation loss with respect to the length of the 
average.
The submission concludes with several experiments on the Penn Treebank dataset.
strength_and_weaknesses: The main strength of the submission is the relative simplicity and elegance of
the averaging method.
By maintaining two averages --- one over a short time scale and one over a long time scale ---
the averaging scheme can capture both local improvement in the objective
and long-term behavior of the optimizer. 
I think it is possible that the length of the short/long intervals could be
set to give near-optimal anytime convergence rates for the training objective,
e.g. something like Theorem 5 of Rakhlin et al. [1].

The major weaknesses of the submission are the following: (i) the theoretical
justification for two-tailed averaging is unrealistic and 
(ii) the experimental evaluation is to small in scope to justify the 
method without strong theory. 

**Theoretical Justification**: The theory in this submission does not justify
the proposed method.
My major complaint here is that the authors assume exactly the properties of 
the validation loss that they need for their averaging scheme to work.
In particular, Assumptions 1 --- monotonic behavior of the validation loss 
with respect to the length of the average --- is deeply unrealistic for several
reasons:

- It is unlikely to be satisfied for stochastic optimization of non-convex models,
    where monotone improvement of any train/validation/test metric is unlikely.
- It makes a very strong assumption on the connection between the training objective
    and the validation objective. That is, progress on the training objective
    should roughly equate to progress on the validation metric. 

Because of the weakness of the theoretical analysis, I can only evaluate
two-tailed averaging as a heuristic method for setting the suffix parameter.

**Empirical Evaluation**: The empirical evaluation is small scale and does
not investigate the assumptions on which the theory is based.
Only two experiments are presented, both on Penn treebank.
No comparison is made against other anytime averaging methods 
(see "Missing References"), making it difficult to establish a baseline for
the performance of two-tailed averaging.

While two-tailed averaging performs well on Penn Treebank, one experiment does 
not justify it's wide-spread use.
In particular, I disagree with the authors statement that two-tailed averaging "is approximately equivalent 
to a series of TA which were tuned for each evaluation step separately" and thus requires no other experiments;
this only holds under their assumptions.
While the assumptions were tested via downstream metrics like behavior
of the average lengths, this is only (approximately) addresses Assumption 3. 
Checking the assumptions properly requires carefully plotting the behavior of
the validation loss and optimal average length on multiple heterogeneous datasets.

Finally, some experiments appear to be omitted from the manuscript.  
Specifically, the authors say: "To explore the effect of the evaluation period E, we tuned models with four times larger and four times smaller E than in our previously discussed experiments."
I do not see these results presented anywhere, so we can only take the authors
on their word that $E$ doesn't strongly affect performance. 
clarity,_quality,_novelty_and_reproducibility: **Clarity**: The paper is generally well written. Some of theoretical derivations were
difficult to follow because of poor notation choices (see "Minor Comments").

**Reproducibility**: The experiments are not reproducible with the information
provided. Batch-size and other critical details are missing for the experiments in Figures 3/4.

**Missing References**:
- Tail averaging as described by Jain et al. (2018) is functionally identical to
    suffix averaging, which was proposed by Rakhlin et al. [1] in 2012. 
    Rakhlin et al. proved that suffix averaging is optimal for strongly convex
    stochastic optimization. I'm not certain why Jain et al. don't discuss 
    the work by Rahklin et al., given that they even note tail averaging is 
    the same method on page 4 of their work.
    Regardless, this highly related branch of work should be properly discussed
    here.

- Several other works have developed anytime variants of suffix averaging which
    are also optimal. For example, polynomial-decay averaging [2] is easy to compute
    and also obtains the optimal convergence rate. Lacoste-Julien et al. [3]
    provide yet another optimal anytime averaging scheme with a simpler proof
    of convergence than that for polynomial-decay averaging.

**Novelty**: The two-tailed averaging method is new to the literature as far as I am aware.

### Minor Comments

- Equation 2: Note that Polyak-Rupert averaging is easily implemented as an EMA using 
    $\beta_t = t/(t+1)$. The optimal scheme of Lacoste-Julien et al. [3] is also easily
    implemented in this fashion.

**Related Works**: 
- "In summary, existing averaging methods which behave well in practice all have one or more hyper- parameters to govern the weighting of early iterates." --- this is not necessarily true. See "Missing References".
- "these methods are not flexible enough to estimate the optimal average at multiple optimization steps in general" --- this is not true once the missing references are considered. 

**Problem Statement**:
- The notation $O(t)$ for optimal averaging length is somewhat confusing due to the clash with standard "Big-O" notation.

**Analysis**:
- Given assumption 3, doesn't assumption 4 simply imply the conclusion holds for all $E$? I don't see why the precondition is even introduced here given assumption 3.
- Figure 2: Is this generated from a real optimization problem, or is it just a synthetic example? 
- What is the notation $E | S(n)$ in Prop. 2 (i)? It doesn't appear to be introduced anywhere. 

### References

[1] Rakhlin, Alexander, Ohad Shamir, and Karthik Sridharan. "Making gradient descent optimal for strongly convex stochastic optimization." arXiv preprint arXiv:1109.5647 (2011).

[2] Shamir, Ohad, and Tong Zhang. "Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes." International conference on machine learning. PMLR, 2013. 

[3] Lacoste-Julien, Simon, Mark Schmidt, and Francis Bach. "A simpler approach to obtaining an O (1/t) convergence rate for the projected stochastic subgradient method." arXiv preprint arXiv:1212.2002 (2012).
summary_of_the_review: === Update ===

I appreciate the discussion with the authors, who have clarified several issues in the manuscript. I think the paper is improved, but I remain skeptical of the main assumptions required for the theoretical analysis. In particular, I think that Assumption 1 is not justified and I am reluctant to accept this submission without (i) an in-depth experimental justification for the assumption, or (ii) a revised theoretical analysis. Although I would normally increase my score to four reflect our discussion, I cannot due to the review form. As such, I will maintain my score of 3.

=====

This submission is an interesting attempt to develop anytime methods for iterate 
averaging. I like two-tailed averaging scheme; perhaps it can be shown to admit
a near optimal convergence rate for the training loss.
Instead of pursing this direction, the authors rely on difficult-to-trust
assumptions on the validation for their theoretical analysis, which shows that the averaging
scheme is once-in-a-while optimal.
As the experiments are limited to a single dataset and do not verify the assumptions, 
I feel the proposed method is not well-justified by theory or experiment. 
I recommend the submission be rejected.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a tail averaging method for stochastic optimization that maintains two averages of different lengths in order to adaptively choose tail averging length.
The average produced by the longer of the two averages is provably close to optimal in length every once in a while.
The advantage of the proposed method over existing tail averaging methods is that it does not have tail averaging length as a hyperparameter.
The only hyperparameter is the number of iterations that pass between evaluating and comparing the two averages and the proposed method is robust to larger changes of this parameter.
The paper provides a theoretical analysis of the algorithm under a set of assumptions and argues how applicable the assumptions are in practice.
The paper also provides a demonstration that the method works well in practice also compared to other iterate averaging approaches for a toy example using an LM on Penn Treebank.
strength_and_weaknesses: Strength:
- Paper does a great job explaining the algorithm itself and also the motivation for it
- Assumptions are clearly stated and even though they seem to be too strict for a nonconvex setting they should still be motivated in practice close to optimum and otherwise treated by the heuristics
- Great figures, they take some time to think about but then make sense and illustrate useful properties once you understand them
- Figure 3 nicely demonstrates that the approach competes with hyperparameter tuned alternatives but in a purely adaptive fashion
- Figure 5 nicely demonstrates the TTA has the potential to improve over not using any tail averaging
- Figure 6 nicely demonstrates the effect of a required reset heuristic from nonconvexity and again how much too-short-averaging-length hurts the validation loss

Weakness:
- Authors fairly point out that the analysis would become more cumbersome when trying to make a statement about the worst case difference between f^O and f^L but explain why this should not be a problem in practice. Under simplified assumptions where f is convex extending the analysis could potentially not be as cumbersome? Perhaps the loss is also monotonous in the averaging length before the averaging length becomes suboptimal? Having this analysis would present a nice addition for the paper making the theoretical analysis even more high quality.
- Figure quality (e.g. of Figure 3, Figure 5) could be improved (the numbers on the axes look blury)
- Would be nice to see the experimental evaluation also on modern architectures and in general on a broader set of evaluations
- The structure of the experiments section could be clearer by separating the different research questions into separate sections making the presentation cleaner

Questions:
- How much wall-clock time cost is added in practice by maintaining the additional sets of weights?
- In this paper about anytime tail averaging: https://arxiv.org/pdf/1902.05083.pdf the averaging length k seems to depend on t (k=ct) which makes maintaining the average more expensive and still requires tuning c. But such approach does not seem to be used for comparison in the author's paper / they seem to compare to a constant averaging length "only". Does the k=ct approach behave qualitatively differen
tly / more similar to the author's proposed adaptive method before the last iterate for which it was tuned?
- The authors mention that tail averaging performs similarly to learning rate decay. Are there comparable adaptive methods for learning rate decay and how does the presented method compare in terms of com
putational cost (memory and wall-clock time)?
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is written clearly and the analysis is elegant and understandable

Quality: The paper presents a high quality theoretical analysis, the experiments section could be improved by being a bit more extensive

Novelty: I'm not familiar with the tail averaging literature so I'm not sure about this point but to me the presented method seems like novel and original work 

Reproducability: The focus of the paper is on the algorithm and theory which is clearly presented and reproducable. The presented experiment is a typical setup which could be easily reproduced with simila
r models and the same dataset which is publicly available.
summary_of_the_review: I recommend to accept the paper due to the clear and elegant theoretical contribution that adds to the tail averaging literature, an important area of stochastic optimization, and the method is also directly applicable and practically feasible for many different machine learning applications.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper seems to rely on an unverified assumption about the behavior of the value of a stochastic function evaluated on averaged iterates of SGD. The assumption seems to be critical for the analysis and indeed it seems to have been proposed exactly to make the analysis go through. There is no empirical evaluation to verify when this assumption holds nor a theoretical argument to show benign conditions that imply this assumption. These issues have not been solved despite a detailed discussion with the reviewers.
Hence, the paper might have potential but it seems to be built on shaky grounds and as such it cannot be accepted at ICLR.
justification_for_why_not_higher_score: The unverified assumption makes the entire theory not very useful.
Decision: Reject