- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper concerns empirical risk minimisation and carries out a theoretical investigation of what happens when a linear model is forced to train until it reaches a perfect fit (meaning 0 training error) on clean, noise-free data. Specifically, the paper asks whether the fact that the training data is limited induces a simple linear model to incur additional error on unseen data, compared to models that are are allowed to fit the data imperfectly. The authors establish 3 findings:
- When the model is required to achieve 0 training error, it enters the interpolation regime. This manifests as the model being forced to commit to directions never observed on training data, which however does show up when evaluating the model on unseen data. The authors theoretically demonstrate that in this case models achieve a worse-case error of (log n / n) on unseen data, more than the 1/n error of models that were not required to achieve perfect fit. GD and SGD run to convergence land at the worse rate, which disproves an earlier O(1/n) conjecture by Zhang et al. (2025)
- They construct a regression problem where GD and SGD initially reach (log n/n^{3/2}) loss on unseen data, but their error on unseen data then rises to (log n / n). The authors explain the mechanism as permanent error in directions the sample never observed, which is initially partly masked by leftover error early on and exposed once the model learns to identify and remove that leftover during training
- They demonstrate that even when the final model is perfect, no guarantee can be given that on unseen data the loss will be lower than (log n / n), by only looking at the training data.
Critical strengths
Sharp results on a question of broad relevance: Modern models are often trained well into the interpolation regime and much of the literature has recently focused on benign overfitting, investigating in which setting this is harmless despite the presence of noise or corrupted samples in the data. This paper asks the more foundational question of how much this interpolation regime actually costs, even when the training data is perfectly noiseless and clean and presents no distributional shifts to the population. The answer is a sharp log n factor, proven with matching upper and lower bounds and explicit constructions.
Critical weaknesses
No experiments or figures: The setting of the paper is noiseless linear regression with fully specified sampling laws. Reproducing this setting through synthetic data is trivial and can be achieved with minimal amount of code. Empirically showing the theory through experiments and providing figures such as error curves over training time would make the paper much more accessible to the community.
Questions for authors
Could you add a figure for a few values of n, and does the curve match eq. (4.1) at the sizes specified in the paper?
6 comments
Clarifications on dataset construction/experimental settings and practical implications.
I thank the authors for adding the synthetic experiments, which numerically illustrate the late-training rise in population risk predicted by Theorem 4.1.
I found the description of the experimental settings and dataset construction quite difficult to understand. As I understand it, the authors design a synthetic dataset of n rows and M + 1 columns where M = ⌊√n⌋. Every dataset of size n shares a fixed weight vector which provides the dataset noiseless labels as its inner product with the rows. The weight vector has size M + 1 and is computed as a function of n. Each dataset is made up of three types of rows, sampled according to a feature law that assigns half of the probability mass to a dense vector, non-zero everywhere ( with value (√q, -1/√M, ... −1/√M)*√︁2/3 and size M + 1); 0.5 − Mp probability for the 0-vector and probability p for the one-hot vector of column j (but with the 1 rescaled to 1/√︁3).
Could the authors please confirm that this reading is correct? In my opinion the paper would really benefit from an intuitive description of the dataset construction in plain and simple language. Additionally, could the authors please explain why the one-hot vector uses 1/√︁3, instead of 1 and why the dense, non-zero everywhere vector is scaled by √︁2/3 ?
Additionally, does the numerical/visual demonstrations also hold for the new Theorem 4.5 ? (even limited to the GD case only). Theorem 4.5 describes the opposite case, where features outnumber rows and which therefore seems closer in nature to the standard over-parametrised regime.
Finally, could the authors comment on the practical implications of their findings on real data and whether they suggest any guidance on early stopping or regularisation ?
Thank You for Your Feedback (Part 1/3)
Thank you very much for your careful reading and thoughtful follow-up comments. We appreciate your recognition that the newly added experiments illustrate the late-training rise in population risk predicted by Theorem 4.1. Your further questions are also very helpful in identifying aspects of our experimental construction, presentation, and practical implications that require clearer explanations. We have carefully addressed each of your points below.
Q1: I found the description of the experimental settings and dataset construction quite difficult to understand. As I understand it, the authors design a synthetic dataset of rows and columns where . Every dataset of size shares a fixed weight vector which provides the dataset noiseless labels as its inner product with the rows. Could the authors please confirm that this reading is correct? In my opinion the paper would really benefit from an intuitive description of the dataset construction in plain and simple language.
A: Thank you for carefully working through the construction. Your understanding is entirely correct. We apologize that our original description was not clear enough. For each , we fix a target vector of dimension , where . This target is chosen before sampling and shared across all repetitions at that . We then draw independent feature vectors and assign the noiseless labels .
Intuitively, the dense row provides an equation involving all target weights. It appears frequently, but every occurrence gives the same equation. Each rare coordinate row reveals one individual weight through its label. The zero row has label zero and adds no constraint on the weights. The sample can therefore leave some weights undetermined if the corresponding rare coordinate rows are missing. We have expanded Section 4.1 (pp. 6–7) to explain these roles in plain language. Appendix A.1 (p. 16) now explicitly states that the target is fixed before sampling and provides a table of all three row types and their sampling probabilities.
Q2: Could the authors please explain why the one-hot vector uses , instead of , and why the dense, non-zero everywhere vector is scaled by ?
A: Thank you for pointing out that these scaling choices need clarification. We apply a common rescaling to keep both row types within the length bound . Before rescaling, we use unit one-hot vectors and the dense vector , where . The dense row is sampled with probability . The factor cancels this in the expected squared loss because .
For , the dense vector has squared length . Dividing both row types by therefore makes every feature vector's length at most one. This gives for the one-hot vectors and for the dense vector. A unit one-hot vector would also satisfy the length bound. We scale both types together to keep their relative sizes unchanged. We have added this explanation to Appendix A.1 (p. 16), under Why the rows have these lengths.
Thank You for Your Feedback
Thank you for your support and for recognizing the sharpness and broad relevance of our results. We have revised the manuscript and highlighted all changes in blue. Our point-by-point responses follow.
Q: Could you add a figure for a few values of n, and does the curve match eq. (4.1) at the sizes specified in the paper?
A: Thank you for this suggestion. We have prepared risk plots for several values of n. Both GD and SGD show the initial decrease and subsequent rise predicted by Eq. (4.1), and the measured risk and time scales are consistent with the equation. We have added Figure 1 to Section 4.1. Appendix A now provides the full protocol and additional plots along with confidence intervals and numerical checks. This material appears on pp. 15–19 immediately after the appendix contents. Figure 3(c) directly compares the measured curve with the expression in Eq. (4.1). Selected numerical results are given below.
We use the original construction in Appendix K, with zero initialization and step size 1/4. GD is evaluated through its discrete-time spectral formula on 1,000 independent training sets per sample size. For SGD, we simulate 200 independent dataset/path pairs at each sample size in the first table. Each SGD path repeatedly samples from its fixed training set.
The tables summarize estimates of the expected population risk RT=EF(wˉT) of the prefix average. Population loss is computed directly from the feature law. In the first table, all values are divided by Rn, so the value at T=n is 1. The finite late horizon is TL=⌈120/(pq)⌉, with q=64/⌊n⌋ and p=1−q1/n.
The risk increase is already visible at the finite horizon TL and becomes larger as n increases. The last column averages analytically computed interpolation risks over the sampled datasets. Its six ratios have 95% Monte Carlo confidence intervals with half-widths below 0.007.
The second table compares GD with the risk and time scales in Eq. (4.1). Here T1/2 is estimated from the sampled curve as the first time after T=n when risk reaches (Rn+R∞)/2.
Across a thousandfold increase in n, each normalized quantity varies by less than a factor of two. These results support the intermediate-risk scale logn/n3/2, the interpolation-risk scale logn/n, and the rise-time scale n3/2/logn. Finite-sample effects remain visible. Eq. (4.1) specifies these orders up to universal constants, so it does not predict pointwise numerical equality. Theorem 4.1 also leaves the numerical threshold for sufficiently large n unspecified.