Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies an interesting and important problem: what is the optimal early stopping time (considering the model dimension and sample size, especially under an overparameterization setting)? The data distribution is synthetic. Considering a standard linear least squares regression problem, the gradient flow is expressed as a differential equation. Further, solving the differential equation, the estimator can be expressed as a function of the time and data. Given such a result from an earlier work, the paper studies the optimal stopping time that minimizes the expected risk and presents high probability (upper and lower) bounds for the overparameterization setting. It suggests that with a high probability, the optimal early stopping time is $\tilde{\Theta}(\frac{n}{n+d})$, which implies that the optimal early stopping time increases as $n$ increases and $d$ decreases. The paper also shows that the bounds decrease as $n$ increases, which implies that optimal early stopping can mitigate sample-wise double descent. Empirical results validate the theory.
main_review: I quickly checked the proof and did not find an obvious flaw. 

Pros:

1. The problem is interesting and important. Early stopping has a long history of being used as a regularization of machine learning algorithms. 

2. The results are insightful for me. The main results about the overparameterization setting agree with some empirical findings and make a step towards understanding the training procedure of machine learning algorithms.  

Cons:

1. The data distribution and problem are restrictive. I understand that this is an early theoretical attempt and I notice that the authors also find some related work falls into the same setting. However, the approaches in this paper rely on the assumption that the estimation can be expressed as a function of early stopping time. I worry that it would be highly nontrivial to extend the results to real settings. 

2. Technically, the results of Theorem 1 and 2 are not directly comparable because Theorem 1 presents high probability bounds while Theorem 2 presents deterministic bounds with a further assumption on the data distribution. It may be confusing to present the main claims in parallel without discussing the differences in the two settings.
summary_of_the_review: Overall this is an interesting theoretical paper with its limitation. Currently, I tend to accept it.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the optimal early stopping time of gradient flow for linear regression in two regimes: over-informative features or under-informative features, where the first regime means the features contain sufficient information to generate the response, while the second regime means responses rely on additional information beyond those in the features. In the two different regimes, the paper shows that the optimal early stopping time behaves quite differently. Theory are built for linear regression, and experimental verifications are performed in both toy data and neural networks.
main_review: # Pros:
+ The different behaviors of optimal stopping time for gradient flow in over- or under-informative settings seem to be interesting and novel.
+ The observation from neural network experiments are also inspiring.


# Cons:
- First of all, the terminology of "overparameterization" and "underparameterization" are rather mis-leading!!!! In literature, those terminologies are widely used to refer to regimes where the number of parameter is larger/smaller than the number of data. However in this paper, if I understand it correctly, the authors aim to mean two different feature generating processes. More concretely, let $X$ be feature, $Z$ be the hidden variable and $Y$ be the response, then the two regimes in Markov chain can be represented as 
$$
X \\to Z \\to Y
$$ 
and 
$$
X \\leftarrow Z \\rightarrow Y
$$
I would rather refer these two regimes as "over-informative" and "under-informative". Better to avoid misleading here.

- Beyond terminologies, I would say the paper needs some further revision, at least in terms of languages. For a few examples:
   * the first two paragraphs in Sec 1 could use some references. 
   * Sec. 1, Over- vs. Under-parameterization paragraph: I am not sure whether or not these are "discovered" by the authors. There are a number of references in Sec. 4.2 that seem to suggest low-dim data structure is known. Could use some clarification here. 
   * The paragraph above Sec. 1.1. "early-stopped models" 
   * It is such a mess when introducing $P$ --- is it deterministic or random?

- Paragraph below Thm1. The claims about case $ n \gg d$ is clearly incorrect. Note that $n / (d+n)  = \Theta(1)$, but $\log (1 + \Theta(n / d)) \gg 1$, so the logarithmic factors are actually leading factors. All the following claims need revision. 

- As for the Theorems, I find the feature assumption is too strong to be interesting. For example in Thm1, it assumes $x \sim N(0,1)$. This is too specialized and is basically equivalent to a 1-dimensional problem. Thm1 could be more interesting if can cover $x \sim N(0,H)$ where $H$ is a general PSD matrix. Similar assumptions on hidden variable is also made for Thm2.

- Finally, I feel the main conclusion of this work is less surprising (or interesting), given the fact that the different behaviors of optimal early stopping is in fact caused by **different data generating process** instead of **different regimes of number of parameter vs. number of data**. In the first setting of the paper, which is also the traditional setting we see in literature, the feature contains full information for recovering the label, and the optimal stopping time is obtained by balancing the bias vs. variance error. In this case, it is very clearly one needs to stop earlier with a smaller $n$ or larger $d$ to avoid overfitting. In the second setting, it is more like an issue of insufficient observation, and no wonder one can stop latter as $d$ increases (where the information in features increases). I do not think this is beyond the traditional statistics wisdom. 








summary_of_the_review: The current paper is misleading and needs a significant revision. Based on my current understanding, the paper is less interesting as suggested by the title. I cannot recommend acceptance given the current version.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work looks at implicit (algorithmic) regularization of learning algorithms, with a particular focus on the impact of early stopping in the context of iterative gradient-based learning algorithms.

The model of interest is a linear model with additive random noise, and for their analytical entry point, the authors consider the gradient flow differential equation as in Ali et al. (2019), i.e., a typical gradient descent update in the limit where step size is taken to zero. They provide confidence intervals for the optimal early stopping time (optimal in terms of the expected squared error) and subsequently derive upper/lower bounds in expectation for the risk achieved at such the optimal early stopping time.

In addition, the authors carry out empirical analysis of optimal stopping times for both linear and non-linear models, over a range of sample size, data dimension, and model dimension settings. They argue that well-trained neural networks admit "low-rank" representations which are akin to the over-parametrized linear model that they study in theory.
main_review: *Strong point(s) of the paper*

- The authors obtain novel theoretical results on the optimal stopping times for gradient flow under a linear model (with Gaussian data/noise assumptions), refining the initial theory built up by Ali et al. (2019).

- Their theoretical analysis explicitly separates the over-parametrized and under-parametrized settings (e.g., whether the number of model parameters in larger than the number of data features or not), obtaining distinct insights for each of these settings, with empirical tests that are designed to invesigate the "sharpness" of this distinction. This distinction is, at least in extreme cases, quite important, and additional insights both in theory and practice are of value.


*Weak point(s) of the paper*

- I felt that the theoretical results were poorly explained, given the context of previous work such as Ali et al. (2019). In section 2.1, the authors just say "we can derive a high probability upper and lower bound on (the optimal stopping time)" and give the result, without any discussion of the technical side of this. Since Ali et al. say that controlling the optimal stopping time is "difficult" (their Rmk 4), one would expect that the authors here would describe what assumptions or techniques made it possible for them to solve this difficulty. Since this previous work did not (as far as I can tell) make any Gaussian assumptions on the data, one expects that the Gaussianity might play an important role in the authors' analysis, but since this is not described, the reader is left wondering. One is also left wondering if it would be straightforward to obtain high-probability bounds on the risk, since bounds are with high probability for the stopping time control.

- While I would not say the writing itself is poor, it is rather careless in many places. Some are notation issues, others are explanation issues. Here are a few representative examples:
  - The matrix exponential (p.4) is not introduced anywhere as far as I can see. 
  - On p.6, the authors say that "Theorem 2 implies that when the number of features is larger than the model dimension, optimal early stopping time increases as $n$ and $d$ increases." This is a very broad statement; in reality, doesn't it depend on how fast $n$ and $d$ respectively increase? A similar statement is on p.7 for the under-parametrized case.
  - In the experimental section, there is very little information on how the optimal stopping times are actually computed, and a brief glance at the supplementary materials does not shed any more light on this.

summary_of_the_review: To the best of my understanding, the theoretical results obtained by the authors (optimal stopping time control + resulting risk bounds) are new and provide more refined insights that the existing literature with respect to the impact of sample size and dimensionality, despite the limiting Gaussian assumptions. In addition, while the experimental section could use a lot more exposition, from what I can tell the design is straightforward and natural considering the theoretical results the authors want to verify. My overall take on this paper is that there are some results of value here, but the paper itself needs some work, so I am left on the borderline with this work, tending to accept, but with the caveat that I am not very familiar with the developments in this line of work since Ali et al.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper the authors analyze early stopping in linear regression. The authors show that the optimal early stopping time behaves differently in overparameterized and underparameterized regimes. Specifically, the optimal early stopping time decreases when increasing model size in the overparameterized regime, but increases with model size in the underparameterized regime. Some empirical results demonstrate the theoretical results in linear regression and deep neural networks.
main_review: I think the main contribution of the paper is the analysis of optimal early stopping in overparameterized regime. However, I think the definition of “overparameterized regime“ in this paper is different from what is usually used in the literature. Specifically, the definition in the paper doesn’t take into account the number of examples, but only the number of features and model size. I think the authors should clarify what do they mean by “model size” in general (e.g. in neural networks), is it the number of parameters? The width of the network ? 

Another relevant paper in the overparameterized regime:

Vaskevicius et al, Implicit regularization for optimal sparse recovery. NeurIPS 2019.

However, I think the novelty of the paper is quite limited. The underparametererized setting was previously analyzed in Nakkiran et al., 2020b, where the effect of regularization is studied, and it is well known that $L_2$ regularization is strongly related to early stopping. For example, Nakkiran et al., 2020b showed that the expected test risk of the optimally-regularized model is monotonic in the model size (theorem 3 therein). Also, the optimal ridge parameter $\lambda\sim\frac{1}{d}$ (lemma 3 therein), and since stopping time decreases when $\lambda$ increases, the optimal stopping time is monotonic in model size, which is also the result in this paper. The authors claim that “optimal early stopping can help mitigate double descent in various settings” – this should be compared to similar results in Nakkiran et al., 2020b for $L_2$ regularization.

Comments and questions about the empirical part:

I think the empirical part with neural networks should be improved:

-	Is it possible to show that the results hold when changing the model size by changing the depth and not width ?
-	Would be good to show that the results hold when playing with the amount of label noise.
-	I think Figure 13 should go more to the right (more epochs) to see the entire curve.
-	In figures 11,12 – can you explain how $a,b$ are selected ?
-	In figure 14 – is the test loss correspond to optimal early stopping time ?

summary_of_the_review: Overall, I think the theoretical contribution is rather limited given the work of Nakkiran et al., 2020b, and the empirical part should be improved. Therefore, I don’t recommend the paper for acceptance at this stage.
review_title: null

Meta-review: This paper studies the problem of characterizing the optimal early stopping time in overparameterized learning as a function of model dimension and sample size. To do this the paper uses an explicit form of the gradient flow from prior work to present high probability bounds in the over-parameterized setting and characterizes various properties of the optimal stopping time. The authors also conduct various experiments to verify the theory. The reviews though the paper was interesting and insightful. They also raised some concerns about the (1)restrictiveness of the distributional assumptions, (2) poor explanation of the theoretical results, and (3) novelty with respect to other work and (4) other technical issues. The discussion and response mitigated these concerns but the reviewers decided to mostly keep their original score. My own reading of the paper is that there are good ideas in this paper and I agree with the authors that some of the technical issues raised by the reviewers is incorrect. However, it is also clear that the paper needs a bit more work to put it into the right context and also the proof need to be more clearly and carefully written before this paper can be accepted. Therefore I recommend rejection but encourage the authors to submit to a future ML venue after a thorough revision.
Decision: Reject