acceptodds
Under review as a conference paper at ICLR 2027

Persistent Overfitting: The Statistical Price of Interpolation

Abstract

What is the statistical price of fitting noiseless training examples exactly? In noiseless linear regression with sufficient dimension, requiring interpolation raises the minimax expected population risk from to , with the same data and linear predictor class. Gradient descent and fixed-dataset SGD incur this statistical price at convergence, matching the minimax rate among interpolating estimators. Yet, on a single instance, their -point prefix averages achieve expected population risk at , followed by a persistent deterioration to , even though the iterates never move farther from the target in Euclidean distance. We explain this behavior through shared constraints and missing coordinate penalties. For general realizable quadratics, we sharply characterize how the interpolation price depends on dimension, population trace, and sample rank. Finally, we study how accurately the risk of the converged predictor can be certified from observed data. With fresh validation examples, the optimal certification scale is , even when the true risk is zero.

Primary area:
learning theory
Keywords:
generalization, realizability, overfitting, gradient descent, stochastic gradient descent

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_6rJAOpenReview ↗
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
AuthorsOpenReview ↗

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 nn. 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/41/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)R_T=\mathbb{E}F(\bar w_T) of the prefix average. Population loss is computed directly from the feature law. In the first table, all values are divided by RnR_n, so the value at T=nT=n is 11. The finite late horizon is TL=⌈120/(pq)⌉T_L=\lceil 120/(pq)\rceil, with q=64/⌊n⌋q=64/\lfloor\sqrt n\rfloor and p=1−q1/np=1-q^{1/n}.

MethodnnR1/RnR_1/R_nRTL/RnR_{T_L}/R_nR∞/RnR_\infty/R_n
GD10510^51.2801.6711.814
GD10610^61.3023.9374.449
GD3×1063\times 10^61.3856.3917.281
SGD10510^51.2761.6661.809
SGD10610^61.2953.9194.425
SGD3×1063\times 10^61.3776.3517.240

The risk increase is already visible at the finite horizon TLT_L and becomes larger as nn 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.0070.007.

The second table compares GD with the risk and time scales in Eq. (4.1). Here T1/2T_{1/2} is estimated from the sampled curve as the first time after T=nT=n when risk reaches (Rn+R∞)/2(R_n+R_\infty)/2.

nnn3/2Rn/log⁡nn^{3/2}R_n/\log nnR∞/log⁡nnR_\infty/\log nT1/2log⁡n/n3/2T_{1/2}\log n/n^{3/2}
10610^60.4640.002072.38
10710^70.6190.002511.78
10810^80.7250.002851.47
10910^90.8000.003111.29

Across a thousandfold increase in nn, each normalized quantity varies by less than a factor of two. These results support the intermediate-risk scale log⁡n/n3/2\log n/n^{3/2}, the interpolation-risk scale log⁡n/n\log n/n, and the rise-time scale n3/2/log⁡nn^{3/2}/\log n. 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 nn unspecified.

Reviewer_6rJAOpenReview ↗

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 ?

AuthorsOpenReview ↗

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 nn rows and M+1M+1 columns where M=⌊n⌋M=\lfloor\sqrt n\rfloor. Every dataset of size nn 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 nn, we fix a target vector wn⋆w_n^\star of dimension M+1M+1, where M=⌊n⌋M=\lfloor\sqrt n\rfloor. This target is chosen before sampling and shared across all repetitions at that nn. We then draw nn independent feature vectors and assign the noiseless labels yi=xi⊤wn⋆y_i=x_i^\top w_n^\star.

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 1/31/\sqrt{3}, instead of 11, and why the dense, non-zero everywhere vector is scaled by 2/3\sqrt{2/3}?

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 ∥x∥≤1\\\|x\\\|\leq1. Before rescaling, we use unit one-hot vectors and the dense vector 2v\sqrt{2}v, where v=(q,−M−1/21)v=(\sqrt{q},-M^{-1/2}\mathbf{1}). The dense row is sampled with probability 1/21/2. The factor 2\sqrt{2} cancels this 1/21/2 in the expected squared loss because 12(2)2=1\frac12(\sqrt{2})^2=1.

For q≤1/2q\leq1/2, the dense vector 2v\sqrt{2}v has squared length 2(1+q)≤32(1+q)\leq3. Dividing both row types by 3\sqrt{3} therefore makes every feature vector's length at most one. This gives 1/31/\sqrt{3} for the one-hot vectors and 2/3\sqrt{2/3} 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.

Reviewer_LGWdOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers a noiseless regression model and studies the optimal risks of a statistical estimator of the unknown signal vector. The main conclusion of this paper is that when the estimator is required to interpolate the data perfectly, the minimax risk of such a statistical estimator increases logarithmically compared to all estimators. The paper also studies the minimax risk of the estimator obtained by gradient descent and SGD, how these risks compare at different number of iterations, and establishes a certification result.

Critical strengths

-The problem the paper studies is relevant in high dimensional statistics

-The paper is fairly comprehensive and proves a large range of theoretical results, including the minimax risk of an interpolator vs all estimators, behavior of GD and SGD, examining the behavior of GD and SGD in different time scales, etc

Critical weaknesses

-The main weakness of the paper is the significance of the results. I do not believe the results to be significant: I don't think the logarithmic factor one pays for interpolation to be a significant cost, and the main reason one could argue for significance is the conjecture of Zhang et al 2025 mentioned in the first paragraph. Consequently, I don't find this logarithmic separation factor particularly surprising or interesting; this is especially considering the fact that this result holds in the worst case over all data distributions, and the data distribution considered for the theorem is an artificial construction

-The writing of the paper is unclear and the wording is confusing in many places, making the paper quite hard to follow. The paper also feels like a rather disorganized collection of the (many) result, and it would feel better to have a more crisp message and central theorem, or make it clear what exactly the central point of the paper is.

Questions for authors

Do the authors expect similar separations behind interpolation and all estimators to hold in "natural" data distributions, e.g. Gaussian covariates?

4 comments
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 1/3)

Thank you for your careful review and for recognizing the relevance of our problem and the breadth of our results. We have revised the manuscript and highlighted all changes in blue. Our point-by-point responses follow.


Q1: The result holds in the worst case over all data distributions, and the distribution considered for the theorem is an artificial construction. Do the authors expect similar separations between interpolation and all estimators to hold in "natural" data distributions, e.g., Gaussian covariates?


A: Thank you for this important question. Our new results show that even when the additional Gaussian mixture weight vanishes (ε=n−1/2→0\varepsilon=n^{-1/2}\to0), interpolation can still incur a full Θ(log⁡n)\Theta(\log n) minimax penalty compared with unrestricted estimators. This penalty disappears for a single Gaussian distribution, although GD can still suffer a persistent Θ(n)\Theta(n)-fold risk deterioration. Our main results are summarized below.

SettingMain resultImplication
Distribution-free (Theorem 3.1)Rint/Rfree=Θ(log⁡n)R_{\mathrm{int}}/R_{\mathrm{free}}=\Theta(\log n)Unavoidable interpolation penalty
Gaussian mixtures (Theorem 3.4)Rint/Rfree=Θ(1+log⁡(1+nε))R_{\mathrm{int}}/R_{\mathrm{free}} =\Theta(1+\log(1+n\varepsilon))Full logarithmic penalty even for ε=n−1/2→0\varepsilon=n^{-1/2}\to0
Gaussian dynamics (Theorem 4.5)EF(w∞)/EF(wˉn)=Θ(n)\mathbb{E}F(w_\infty)/\mathbb{E}F(\bar w_n)=\Theta(n)Persistent deterioration on the same instance

The two results below now appear as Theorem 3.4 in Section 3.3 and Theorem 4.5 in Section 4.3. Appendices B (pp. 20–26) and C (pp. 27–32) contain their complete proofs.

Theorem 3.4 (Sharp interpolation price for Gaussian mixtures). Consider noiseless linear regression with d≥2nd\ge 2n, ∥w∗∥≤1\\\|w^*\\\|\le1, and Gaussian-mixture covariates x∼(1−θ)N(0,Σ0)+θ∑j=1MπjN(0,Σj)x\sim(1-\theta)\mathcal N(0,\Sigma_0)+\theta\sum_{j=1}^{M}\pi_j\mathcal N(0,\Sigma_j), where 0≤θ≤ε0\le\theta\le\varepsilon, ∑jπj=1\sum_j\pi_j=1, and all component covariances are unknown, positive definite, and have trace at most one. The number of components may grow with nn. Then

Rfree=Θ(1/n),Rint=Θ(1+log⁡(1+nε)n).R_{\mathrm{free}}=\Theta(1/n),\qquad R_{\mathrm{int}}= \Theta\left(\frac{1+\log(1+n\varepsilon)}{n}\right).

The lower bound applies to every possibly randomized interpolating estimator, with unrestricted output norm. In particular, the full Θ(log⁡n)\Theta(\log n) penalty persists even when ε=n−1/2→0\varepsilon=n^{-1/2}\to0. The matching lower bound is attained within smooth, full-support Gaussian mixtures.

Theorem 4.5 (Persistent overfitting under Gaussian covariates). Consider noiseless Gaussian regression with d=3nd=3n, x∼N(0,Σn)x\sim\mathcal N(0,\Sigma_n), where Σn=14diag⁡(1,n−1In−1,n−3I2n)\Sigma_n=\frac14\operatorname{diag}(1,n^{-1}I_{n-1},n^{-3}I_{2n}), and target wn∗=−e1/(2n)−en+1/2w_n^*=-e_1/(2n)-e_{n+1}/2. Zero-initialized GD with a sample-dependent, run-constant stable step size satisfies

EF(wˉn)=Θ(n−3),EF(w∞)=Θ(n−2).\mathbb{E}F(\bar w_n)=\Theta(n^{-3}),\qquad \mathbb{E}F(w_\infty)=\Theta(n^{-2}).

Thus, continued optimization causes a persistent Θ(n)\Theta(n)-fold deterioration on the same fixed instance. A corresponding result holds for fixed-step GD and fixed-dataset SGD with x=g/1+∥g∥2x=g/\sqrt{1+\\\|g\\\|^2}, g∼N(0,Σn)g\sim\mathcal N(0,\Sigma_n), whose density is smooth and positive in the open unit ball.

We hope these new results address the your concern about the artificial discrete constructions in our original analysis. They demonstrate that the logarithmic interpolation penalty can persist under smooth Gaussian mixtures, even with vanishing additional mixture weight, while substantial training deterioration can occur even under a single Gaussian distribution.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 2/3)

Q2: I don't think the logarithmic factor one pays for interpolation is a significant cost, nor do I find this separation particularly surprising or interesting. The main reason one could argue for significance seems to be the conjecture of Zhang et al. (2025).


A: Thank you for this comment. The significance of our result is not merely the logarithmic factor, but that exact interpolation itself imposes an unavoidable statistical cost. Even in noiseless regression, the true predictor achieves zero population risk, yet no interpolating estimator can uniformly achieve the optimal statistical rate. Our result advances the algorithm-specific lower bounds of Vaškevičius and Zhivotovskiy (Bernoulli 2023) to an impossibility result for the entire class of interpolating estimators, which also explains why Zhang et al.'s (AISTATS 2025) conjecture fails. The advances over these works are closely connected:

Theoretical advancePrior finding and open questionOur result
1. Statistical barrierVaškevičius & Zhivotovskiy (Bernoulli 2023): Some ERMs incur a logarithmic penalty. Could a better interpolator avoid it?Theorem 3.1: No. Minimax risk: Interpolation Θ(log⁡n/n)\Theta(\log n/n) vs. unrestricted estimation Θ(1/n)\Theta(1/n).
2. Algorithmic consequenceZhang et al. (AISTATS 2025): Conjectured O(1/n)O(1/n) risk even after arbitrarily long GD/SGD training.Theorems 3.1–3.2: GD/SGD converge to interpolation and inherit the barrier in Step 1: Θ(log⁡n/n)\Theta(\log n/n).
3. Training dynamicsZhang et al. (AISTATS 2025): Is long-run deterioration genuine or merely a loose upper bound?Theorem 4.1: Genuine. Persistent Θ(n)\Theta(\sqrt n)-fold risk deterioration on one fixed noiseless instance.

The crucial advance is that our lower bound applies to every interpolating estimator, rather than just particular algorithms. Theorem 3.1 covers even randomized estimators with unrestricted output norms. Both estimator classes use the same data and full linear predictor space, and the only difference is whether exact interpolation is required. This penalty cannot be uniformly avoided by choosing a better algorithm or a different interpolating solution. Our new Gaussian-mixture result in Q1 further shows that this separation is not limited to the original discrete constructions.

Theorem 4.1 shows that longer training can indeed hurt generalization. Because the empirical and population covariances weigh errors differently, continued training can remove a cancellation that initially keeps population risk low. On the same noiseless instance, this leads to a persistent Θ(n)\Theta(\sqrt n)-fold increase in risk, even though the Euclidean distance to the true predictor never increases. We have revised the introduction and the discussion after Theorem 3.1 to emphasize the lower bound for every interpolator. Remark 4.1 now distinguishes this minimax bound from fixed-instance temporal deterioration. We also present the Gaussian-mixture extension in Theorem 3.4.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 3/3)

Q3: The paper also feels like a rather disorganized collection of results. It would be better to have a crisper message and a clearer central theorem.


A: Thank you for this feedback. Our paper addresses one central question: What is the statistical cost of exact interpolation in noiseless learning? Our main result (Theorem 3.1) shows that no interpolating estimator can uniformly avoid this cost even when a perfect predictor exists. We then examine how this limitation affects GD and SGD in practice and whether the risk of the resulting predictor can be reliably certified.

Theoretical progressionCentral questionOur results
1. Statistical limitDoes exact interpolation itself impose an unavoidable statistical cost?Theorem 3.1: Yes. Even the best interpolating estimator has minimax risk Θ(log⁡n/n)\Theta(\log n/n), compared with Θ(1/n)\Theta(1/n) without the constraint.
2. Gradient trainingHow does this statistical cost affect gradient training?Theorem 3.2: GD/SGD converge to interpolation and inherit its Θ(log⁡n/n)\Theta(\log n/n) worst-case risk. Theorem 4.1: On one fixed instance, continued training causes a persistent Θ(n)\Theta(\sqrt n)-fold risk deterioration.
3. Risk certificationIf not every interpolator performs poorly, can we tell whether a trained predictor is accurate?Theorem 5.1: Even at zero population risk, training data alone cannot certify risk below the Θ(log⁡n/n)\Theta(\log n/n) scale. Fresh validation data improve this limit.

The connection between these results is the move from a general statistical limit to practical training and then to assessing the trained predictor. Theorem 3.1 establishes a limitation that holds regardless of how the interpolating solution is found. We then examine what this means for GD and SGD in practice. Theorem 3.2 characterizes their worst-case risk at convergence, while Theorem 4.1 shows that continued training can destroy accuracy attained earlier on the same fixed problem. However, these worst-case results do not mean that every trained predictor performs poorly. This motivates Theorem 5.1, which studies whether we can reliably assess the risk of a particular trained predictor using the available data. We have revised the abstract, introduction, and section openings around Theorem 3.1 and the progression from statistical limits to training dynamics and risk certification.

AuthorsOpenReview ↗

Sincere Thanks for Your Time and Thoughtful Feedback

Thank you very much for your time and consideration. Your feedback has been extremely valuable in helping us improve the paper. With less than 24 hours remaining in the discussion period, we would be sincerely grateful to hear whether our responses address your concerns or whether any points need further clarification.

Following your suggestion, we have extended our analysis to more natural distributions, including Gaussian mixtures and single Gaussian designs. Our main result goes beyond resolving Zhang et al.’s (AISTATS 2025) conjecture. It also extends the “some ERMs” lower bound of Vaškevičius and Zhivotovskiy (Bernoulli 2023) to all interpolating estimators within the full linear predictor class. Reviewer Na4t also noted this distinction. We understand that you may have a busy schedule and would welcome any further questions or suggestions. Thank you again for helping us improve the paper.

Reviewer_Na4tOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper looks at the problem of linear regression and provides a separation between the performance of every perfect-fit estimator and a estimator. It shows that there is a log n performance gap between the two.

The result is conceptually interesting and is worth the discussion. They are also able to derive out of it further insights to the performance of specific algorithms such as GD and SGD, but from what I see this mostly rely on using the fact that in the long run they are interpolating.

Technically, the result is not very sophisticated. And the proof is basically a coupon collector argument where the learner doesn't observe one coordinate therefore suffers a loss of 1 on that coordinate. Unless it sees all samples.

I also found the writing a little bit dense and hard to follow. The paper doesn't distinguish between known and novel results (e.g. in the abstract: "Gradient Descent and fixed dataset incur this statistical price...." Did you show it or is it known?). There are also alot of enigmatic statements that appear throughout the text. For example end of the statistcial setup: "The minimax comparisons enforce ||w||\le 1", what does that mean? which minmax comparisons, why do they enforce that? what is this about. Fortunately, the assumption that w^\star is smaller than one is being reiterated at the main result. So I could at least figure out if that assumption is imposed or not.

Finally, there are also missing related work and some of the results shouldn't be published as novel. The performance of ridge regression was analyzed in "Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors" (theorem 2.2). It is not a novel result They also observe that some interpolators fail in this setup (but not all).

There's also another related work worth mentioning: A separation between exact ERM and learning in the more general setting of SCO has been observed in "All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension", Though, this is not in linear regression. But as for Zhang's open problem: If long training can lead to deterioration, this paper already resolves it.

Critical strengths

The result is conceptually interesting

Critical weaknesses

Missing related work (especially w.r.t upper bound of ridge regression). Technical contribution is not being discussed enough.

Questions for authors

no questions.

5 comments
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 1/3)

Thank you for your support and for recognizing the conceptual value of our main result. We have revised the manuscript and highlighted all changes in blue. Our point-by-point responses follow.


Q1: The performance of ridge regression was analyzed in [1, Theorem 2.2]. They also observe that some interpolators fail in this setup (but not all).


A: Thank you for pointing out this closely related work. Our main result (Theorem 3.1) extends the failure of particular interpolators in [1] to a sharp minimax lower bound for the entire class of interpolating estimators. The statistical penalty is therefore inherent to exact interpolation in the worst case, rather than to the particular ERM solutions considered in [1]. The key differences are summarized below:

ComparisonPrior work [1]Our work (Theorem 3.1)
Lower boundSome constrained ERMs incur Ω(log⁡n/n)\Omega(\log n/n) risk (Proposition 2.3).Every interpolating rule incurs this penalty in the worst case.
Can another interpolator avoid the failure?Yes, on their construction: the minimum-norm interpolator has zero risk.No rule can uniformly avoid the penalty, even with randomization and unrestricted output norms.
Minimax characterizationNot established.Sharp rate: Θ(min⁡log⁡(1+n),1+log⁡d/n)\Theta(\min\\{\log(1+n),1+\log d\\}/n). The minimum-norm interpolator is minimax optimal.

Why does our lower bound apply to every interpolator? The construction in [1] uses zero labels, so the zero vector is a perfect interpolator with zero population risk. Our construction avoids this limitation. Consider a sample that leaves two possible target coordinates aa and bb. Both are consistent with the observed data, but interpolation requires their weights to sum to one: w^a+w^b=1\widehat w_a+\widehat w_b=1. If aa is the true target, assigning weight to bb incurs population risk. The reverse holds when bb is the true target. Averaging over the two possibilities gives

p4(w^a2+w^b2)≥p8.\frac{p}{4} \left(\widehat w_a^2+\widehat w_b^2\right) \ge \frac{p}{8}.

This lower bound holds regardless of how the learner chooses its coefficients, including randomized choices. Equation (3.2) extends the argument to the full construction. We have explicitly acknowledged the established ridge guarantee in [1, Theorem 2.2] and distinguished the two lower-bound quantifiers immediately after Theorem 3.1 and in Appendix P.6.


Q2: A separation between exact ERM and learning in SCO has been observed in [2]. As for Zhang's open problem: If long training can lead to deterioration, this paper already resolves it.


A: Thank you for pointing out this related work. Zhang et al.'s conjecture [3, Section 4] specifically concerns smooth realizable losses. In contrast, [2] uses nonsmooth constructions and explicitly states: "At present, our lower bounds do not apply to smooth objectives." Thus, [2] does not resolve this conjecture. Our results refute it in the smooth realizable setting.

More importantly, extending these lower bounds to the smooth realizable setting is nontrivial. The construction in [2] uses nonsmooth terms to force empirical minimizers to overfit. Since the problem is realizable, the true target itself is a zero-risk empirical minimizer. GD and SGD also never move farther from the true target under our step-size conditions. Our construction establishes overfitting despite these restrictions by exploiting directions missed by the training sample but penalized by the population loss. Specifically, Theorem 3.1 establishes a sharp Θ(log⁡n/n)\Theta(\log n/n) minimax interpolation penalty, ruling out Zhang et al.'s conjectured O(1/n)O(1/n) long-run guarantee for GD and SGD. Theorem 4.1 further proves persistent Θ(n)\Theta(\sqrt n) risk deterioration on a single fixed noiseless instance. We have cited [2] and clarified its nonsmooth scope in the introduction and Section 6 (Related work).

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 2/3)

Q3: The proof is basically a coupon collector argument. The technical contribution is not being discussed enough.


A: Thank you for this comment. We agree that the technical contribution should be explained more clearly. The main technical step in Theorem 3.1 is to establish a risk lower bound for every interpolating rule. This requires accounting for arbitrary real-valued weights on unobserved coordinates. Our hidden-target construction combines indistinguishable candidates with a shared interpolation constraint. Equation (3.2) shows that even the optimal allocation of these weights incurs positive risk. The argument applies to randomized estimators with unrestricted output norms. The coupon-collector argument then determines the sharp logarithmic scale. Beyond this lower bound, two further results require separate technical arguments:

ResultTechnical contribution
Theorem 3.2 (Sharp dimension–trace laws)Spectral rounding gives the trace-sensitive upper bound. A separate hidden-target construction provides the matching lower bound.
Theorem 4.1 (Complete GD/SGD risk curves)Slow-mode spectral analysis and conditional covariance control establish matching risk curves for both methods at every training horizon.

We have clarified the all-interpolator posterior argument in Remark 3.1, the spectral upper-bound mechanism in Remark 3.2, and the separate finite-time GD/SGD analysis at the start of Section 4.1.


Q4: The paper doesn't distinguish between known and novel results (e.g. in the abstract: "Gradient Descent and fixed dataset incur this statistical price...." Did you show it or is it known?). The insights for GD and SGD mostl rely on using the fact that in the long run they are interpolating.


A: Thank you for this comment. Our GD/SGD contributions include a new sharp characterization of their risk at convergence and an independent theoretical result on persistent overfitting. We agree that these findings should be distinguished from the known convergence properties of gradient methods.

GD/SGD resultStatusExplanation
Convergence to minimum-norm interpolationKnown propertyGD and fixed-dataset SGD converge to the minimum-norm interpolator in our setting (Eq. 2.1).
Risk at convergenceNew statistical resultTheorem 3.1, together with the convergence property, establishes the sharp worst-case expected risk Θ(log⁡n/n)\Theta(\log n/n) for both methods in sufficiently high dimension.
Persistent risk deteriorationIndependent theoretical resultTheorem 4.1 establishes matching risk bounds at every training horizon and a persistent Θ(n)\Theta(\sqrt n) deterioration on one fixed instance.

Importantly, Theorem 4.1 does not follow from the convergence property. Its proof requires a separate spectral analysis of the training trajectory and conditional covariance control for fixed-dataset SGD. We have revised the abstract to state the new risk characterization explicitly:

We prove that GD and fixed-dataset SGD have worst-case expected population risk Θ(log⁡n/n)\Theta(\log n/n) at convergence, matching the minimax rate among interpolating estimators.

The introduction now distinguishes known convergence from the new statistical and dynamical results. Section 2 explicitly identifies the common-endpoint convergence property as standard, and Section 4.1 explains the additional finite-time analysis.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 3/3)

Q5: The writing is a little bit dense and hard to follow. What does “the minimax comparisons impose ∥w⋆∥≤1\\\|w^\star\\\|\le 1” mean?


A: Thank you for pointing out this unclear wording. We have replaced the sentence in Section 2 with:

In Section 3, we compare the minimax risk over all estimators with that over estimators required to interpolate the training data. In both cases, we assume ∥w⋆∥≤1\\\|w^\star\\\|\le 1, while the estimator's output norm is unrestricted.

To address your broader concern about readability, we have also made the following revisions throughout the manuscript and highlighted all changes in blue:

AspectRevisionLocation
SetupBoth estimator classes are now defined explicitly. The norm bound applies only to the target.Sections 2 and 3.1
Known and new resultsWe distinguish known convergence and ridge guarantees from the new minimax and finite-time results.Abstract; Sections 2, 3.1 and 4.1
Proof intuitionAlongside the main results, we explain the proof ideas and why risk can rise during training.Remarks 3.1–3.2; Section 4.1
OrganizationThe introduction explains how the three parts fit together. New experiments and complete proofs appear first in the appendices.Introduction; Appendices A–D

References

[1] T. Vaškevičius and N. Zhivotovskiy. Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors. Bernoulli, 2023.

[2] T. Burla and R. Livni. All ERMs Can Fail in Stochastic Convex Optimization: Lower Bounds in Linear Dimension. ICML, 2026.

[3] P. Zhang, J. Teng, and J. Zhang. Generalization Lower Bounds for GD and SGD in Smooth Stochastic Convex Optimization. AISTATS, 2025.

Reviewer_wYz1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the statistical cost of requiring exact interpolation in noiseless linear regression,

y=x⊤w∗,∥x∥2≤1,∥w∗∥2≤1,F(w)=12E[(x⊤(w−w∗))2].y=x^\top w_{\ast},\qquad \left\lVert x\right\rVert_2\le 1,\qquad \left\lVert w_{\ast}\right\rVert_2\le 1,\qquad F(w)=\frac{1}{2}\mathbb{E}\left[(x^\top(w-w_{\ast}))^2\right].

Both the feature distribution and the target are unknown. The comparison is between estimators with the same observations and the same output space Rd\mathbb{R}^d, differing only in whether they must interpolate the training sample. Estimators may be randomized and have unrestricted output norm.

The main theorem establishes

R_{\mathrm{int}}(n,d)=\Theta\\!\left(\frac{\min\\{\log(1+n),\\,1+\log d\\}}{n}\right).$$ The lower bound applies to every linear interpolating rule. The minimum Euclidean norm interpolator attains the matching upper bound, as do the limits of zero-initialized GD and fixed-dataset SGD. Thus the result concerns a restriction on the estimator class, rather than only a failure of a particular optimizer.
Critical strengths

The most compelling contribution is that the logarithm is necessary for every linear interpolating estimator. An algorithm-specific example could be explained by a poor implicit bias or tie-breaking rule. Here the lower bound survives arbitrary choices among empirical interpolators, including randomized rules, signed coefficients, and unrestricted output norms.

The proof isolates a precise obstruction. A shared observation imposes a sum constraint, while observed zero-label coordinate examples force individual coefficients to vanish. The learner is left with a small set of indistinguishable coordinates, and exact fitting requires the coefficient sum on that set to equal one. A posterior quadratic minimization shows that even the best fractional hedge pays for the remaining ambiguity. The coupon-collector calibration makes a surviving false coordinate carry population probability Θ(log⁡n/n)\Theta(\log n/n).

This is a particularly clean use of a lower-bound construction: the probabilistic mechanism is elementary, but the quantifier over all interpolating learning rules is strong. The matching upper bound confirms that the logarithm is the correct statistical scale.

Critical weaknesses

The lower bound is a worst-case result with specific sampling geometry

The hard feature law is discrete, and it is calibrated so that some population-relevant coordinate constraints remain absent from the sample. Even when n≫dn\gg d, repeated rows leave the design matrix rank deficient with constant probability. The law and target may depend on nn, while remaining fixed before the sample is drawn.

This is fully legitimate for the stated minimax theorem. It limits the interpretation, however: the result does not imply a logarithmic penalty for every design, for well-conditioned continuous designs, or for every fixed distribution as fresh sample size increases. If a noiseless design matrix has full column rank, every linear interpolator equals the target.

The manuscript addresses perturbations rather than ignoring this issue. Its smooth full-support examples preserve long finite deterioration plateaus, but eventually recover the target. A finite plateau and a nonzero infinite-time endpoint risk are distinct claims.

Unknown population geometry is essential

Both the target and feature law are unknown, and the hard family varies them jointly with the hidden index. This information restriction is explicit in the paper and is not a defect in the lower bound.

It deserves prominent explanation because a reader could otherwise interpret the result as a universal disadvantage of interpolation with known design geometry. The known-covariance observation gives an elementary observation derived in this report: if the population covariance is supplied, an unrestricted estimator can be projected onto the empirical interpolation set in the population metric without increasing risk. Thus the unknown population geometry is a meaningful part of the obstruction.

Historical novelty should be attached to the exact theorem

Coupon-collector lower bounds and logarithmic penalties for restricted learners have established antecedents. Auer and Ortner show that some consistent rules pay an avoidable logarithm [1]. Bousquet et al. give classes for which every proper binary learner pays such a penalty [2]. Høgsgaard, Larsen, and Zou establish a related all-proper-learner penalty for constructed regression classes under cutoff loss [3]. Zhang, Teng, and Zhang study generalization lower bounds for GD and SGD in smooth stochastic convex optimization and conjecture that improved upper bounds can close the remaining gap in the realizable setting [4].

The present distinction is the sharp separation in bounded, noiseless squared-loss regression while both estimators retain the same full linear parameter class, together with the dimension, trace, and rank laws. These earlier theorems do not by themselves establish that statement. The manuscript acknowledges the antecedents in Section 6 and Appendix L.6; the review should not suggest that they are uncited. A concise comparison next to Theorem 3.1 would make the contribution easier to assess.

References

[1] P. Auer and R. Ortner. A new PAC bound for intersection-closed concept classes. Machine Learning 66, 151–163, 2007.

[2] O. Bousquet, S. Hanneke, S. Moran, and N. Zhivotovskiy. Proper Learning, Helly Number, and an Optimal SVM Bound. COLT 2020, PMLR 125, 582–609. See Theorem 11.

[3] M. M. Høgsgaard, K. G. Larsen, and L.-Y. Zou. The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity. ICML 2026, PMLR 306, 43351–43387. Theorem numbering 3.12 refers to arXiv:2605.29819v2, 27 July 2026: versioned preprint.

[4] P. Zhang, J. Teng, and J. Zhang. Generalization Lower Bounds for GD and SGD in Smooth Stochastic Convex Optimization. AISTATS 2025, PMLR 258, 334–342. The conjecture is also stated in the full preprint.

Questions for authors
  1. Make the exact novelty boundary prominent. Could the discussion adjacent to Theorem 3.1 explicitly compare the all-interpolator linear-class quantifier with the proper-learning restrictions in the closest prior work? Section 6 and Appendix L.6 already contain the relevant acknowledgments.

  2. Clarify the information restriction. Would it be useful to discuss known covariance or additional unlabeled feature observations? The population-metric projection in the known-covariance observation suggests a concise way to explain why unknown sampling geometry matters.

As I am not an expert in this field, if the authors would convince the reviewers in the rebuttal that this work is novel, then I would raise my score.

4 comments
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 1/2)

Thank you for your careful review and for recognizing our sharp minimax results. We have revised the manuscript and highlighted all changes in blue. Our point-by-point responses follow.


Q1: Could the discussion adjacent to Theorem 3.1 explicitly compare the all-interpolator linear-class quantifier with the proper-learning restrictions in the closest prior work? Section 6 and Appendix L.6 already contain the relevant acknowledgments.


A: Thank you for this suggestion. We appreciate your recognition that “The most compelling contribution is that the logarithm is necessary for every linear interpolating estimator” and your observation that “These earlier theorems do not by themselves establish that statement.” As you noted, Section 6 and Appendix L.6 of our original manuscript already compare our results with these works and explain why prior proper-learning lower bounds do not imply our result. We agree that this distinction should be made more prominent next to Theorem 3.1. The comparison is summarized below:

Theoretical advancePrior work and remaining gapsOur result
1. Statistical barrierAuer & Ortner [1]; Bousquet et al. [2]; Høgsgaard et al. [3]: Some consistent rules pay an avoidable logarithmic penalty. Other results establish such a penalty for all proper learners in restricted hypothesis classes. Does the penalty persist when exact interpolation is the only restriction?Theorem 3.1: Yes. Sharp minimax risk in sufficient dimension: interpolation Θ(log⁡n/n)\Theta(\log n/n) vs. unrestricted estimation Θ(1/n)\Theta(1/n).
2. Algorithmic consequenceZhang et al. [4]: Conjectured O(1/n)O(1/n) risk after arbitrarily long GD/SGD training. Does it hold at convergence?Theorem 3.1: No. GD/SGD converge to interpolators with sharp worst-case risk Θ(log⁡n/n)\Theta(\log n/n).

Bousquet et al. [2] and Høgsgaard et al. [3] establish logarithmic penalties for proper learners restricted to specific hypothesis classes. Our result goes beyond this restriction: both estimator classes use the same data and the same full linear predictor space, differing only in whether exact interpolation is required. Theorem 3.1 proves that this requirement alone creates an unavoidable logarithmic minimax penalty. Following your suggestion, we have added this comparison immediately after Theorem 3.1 in Section 3.1 and expanded the detailed discussion in Appendix P.6.


Q2: Would it be useful to discuss known population covariance or additional unlabeled feature observations?


A: Thank you for this suggestion. When the population covariance is known, the additional minimax cost of interpolation disappears entirely. With sufficiently many unlabeled observations, the O(1/n)O(1/n) risk rate can also be recovered. As you noted, “This information restriction is explicit in the paper and is not a defect in the lower bound.” Section 2 and Appendix P.6 already specify that the feature distribution and target are unknown. We further establish the following results.

1. Known covariance. Let Σ=E[xx⊤]\Sigma=\mathbb{E}[xx^\top] and CS=w:Xw=y\mathcal{C}_S=\\{w:Xw=y\\}. Given any estimator w^\widehat{w}, project it onto CS\mathcal{C}_S using the population metric: w~∈arg⁡min⁡w∈CS∥w−w^∥Σ2.\widetilde{w}\in\arg\min_{w\in\mathcal{C}_S} \\\|w-\widehat{w}\\\|_\Sigma^2. Since w⋆∈CSw_\star\in\mathcal{C}_S, this projection guarantees F(w~)≤F(w^)F(\widetilde{w})\le F(\widehat{w}). Consequently, when both estimator classes know Σ\Sigma,

Rintknown,Σ=Rfreeknown,Σ.R_{\mathrm{int}}^{\mathrm{known}\\,\Sigma} = R_{\mathrm{free}}^{\mathrm{known}\\,\Sigma}.

Thus, exact interpolation incurs no additional statistical cost when the population geometry is known.

2. Additional unlabeled observations. With mm independent unlabeled features, we estimate Σ\Sigma and project a norm-bounded ridge estimator onto the interpolation set within the unit ball. Under our existing assumptions, this yields

EF(w~)≤12n+4m.\mathbb{E}F(\widetilde{w}) \le \frac{1}{2n}+\frac{4}{\sqrt{m}}.

Hence, m≥n2m\ge n^2 suffices to recover the O(1/n)O(1/n) risk rate while maintaining exact interpolation, without any spectral-gap assumption. Together, these results clarify that the statistical penalty in Theorem 3.1 arises from requiring exact interpolation when the population geometry is unknown. We have added these results to Section 3.3, with complete constructions and proofs in Propositions D.1–D.2 in Appendix D (p. 33).

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 2/2)

Q3: The lower bound is a worst-case result with specific sampling geometry. A finite plateau and a nonzero infinite-time endpoint risk are distinct claims.


A: Thank you for recognizing that “This is fully legitimate for the stated minimax theorem” and that “The manuscript addresses perturbations rather than ignoring this issue.” We agree that the original lower bound is a worst-case statement and that its smooth perturbations establish finite-time deterioration rather than nonzero endpoint risk. We establish two complementary results for Gaussian designs. Theorem 3.4 extends the minimax separation to smooth Gaussian mixtures with full support. Theorem 4.5 establishes persistent risk deterioration at the infinite-time endpoint for a single Gaussian instance.

Theorem 3.4 (Sharp interpolation price for Gaussian mixtures). Consider noiseless linear regression with d≥2nd\ge 2n, ∥w∗∥≤1\\\|w^*\\\|\le1, and Gaussian-mixture covariates x∼(1−θ)N(0,Σ0)+θ∑j=1MπjN(0,Σj)x\sim(1-\theta)\mathcal N(0,\Sigma_0)+\theta\sum_{j=1}^{M}\pi_j\mathcal N(0,\Sigma_j), where 0≤θ≤ε0\le\theta\le\varepsilon, ∑jπj=1\sum_j\pi_j=1, and all component covariances are unknown, positive definite, and have trace at most one. The number of components may grow with nn. Then

Rfree=Θ(1/n),Rint=Θ(1+log⁡(1+nε)n).R_{\mathrm{free}}=\Theta(1/n),\qquad R_{\mathrm{int}}=\Theta\left(\frac{1+\log(1+n\varepsilon)}{n}\right).

The lower bound applies to every possibly randomized interpolating estimator, with unrestricted output norm. In particular, the full Θ(log⁡n)\Theta(\log n) penalty persists even when ε=n−1/2→0\varepsilon=n^{-1/2}\to0. The matching lower bound is attained within smooth, full-support Gaussian mixtures.

Theorem 4.5 (Persistent overfitting under Gaussian covariates). Consider noiseless Gaussian regression with d=3nd=3n, x∼N(0,Σn)x\sim\mathcal N(0,\Sigma_n), where Σn=14diag⁡(1,n−1In−1,n−3I2n)\Sigma_n=\frac14\operatorname{diag}(1,n^{-1}I_{n-1},n^{-3}I_{2n}), and target wn∗=−e1/(2n)−en+1/2w_n^*=-e_1/(2n)-e_{n+1}/2. Zero-initialized GD with a sample-dependent, run-constant stable step size satisfies

EF(wˉn)=Θ(n−3),EF(w∞)=Θ(n−2).\mathbb{E}F(\bar w_n)=\Theta(n^{-3}),\qquad \mathbb{E}F(w_\infty)=\Theta(n^{-2}).

Thus, continued optimization causes a persistent Θ(n)\Theta(n)-fold deterioration on the same fixed instance. A corresponding result holds for fixed-step GD and fixed-dataset SGD with x=g/1+∥g∥2x=g/\sqrt{1+\\\|g\\\|^2}, g∼N(0,Σn)g\sim\mathcal N(0,\Sigma_n), whose density is smooth and positive in the open unit ball.

For each fixed sufficiently large nn, the limiting expected risk is positive and exceeds the risk of the early averaged iterate by a factor of Θ(n)\Theta(n). The instance is held fixed during training but may depend on nn. Your full-rank observation remains valid: when the training design has full column rank, noiseless interpolation recovers the target. Our original smooth perturbation falls into this setting with d≤nd\le n, whereas the new Gaussian construction has d=3nd=3n and a nontrivial empirical nullspace. These results remain worst-case or instance-specific; we do not claim the same behavior for every well-conditioned design or a single distribution held fixed across sample sizes. We have made these distinctions explicit in Sections 3.3 and 4.3. The new results appear as Theorems 3.4 and 4.5, with complete proofs in Appendices B (pp. 20–26) and C (pp. 27–32). The finite-plateau perturbation results remain in Appendix N and are distinguished from persistent endpoint deterioration.

Thanks for the detailed rebuttal and the clarifications, I believe I would increase my score.

AuthorsOpenReview ↗

Thank You for Your Continued Support

Thank you again for your encouraging response and for your willingness to increase the score. We sincerely apologize for taking up a little more of your time with this additional follow-up. We noticed that the rating currently displayed on OpenReview has not yet changed, and just wanted to kindly check whether the update might still be pending. If you still feel that an increase is appropriate, we would be very grateful if you could update it whenever convenient. We sincerely appreciate your time, consideration, and continued support.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Review Discussion

Dear Area Chair,

Thank you for coordinating the discussion. Reviewer Na4t (confidence 4) and Reviewer 6rJA (confidence 2) both rated the paper 3 (weak acceptance). Reviewer wYz1 (rating 2, confidence 2) wrote after our rebuttal, “I believe I would increase my score.” We therefore expect a revised rating of 3 or 4. Reviewer LGWd (rating 2, confidence 2) is the only reviewer with a negative rating who has not replied. We believe our revisions address their three concerns about Gaussian covariates, significance, and the central theorem.

Our main result (Theorem 3.1) shows that exact interpolation itself imposes an unavoidable statistical cost. In noiseless linear regression with sufficient dimension, requiring interpolation raises the minimax expected population risk from Θ(1/n)\Theta(1/n) to Θ(log⁡n/n)\Theta(\log n/n), with the same data and linear predictor class. We extend the ERM lower bound of Vaškevičius & Zhivotovskiy (Bernoulli 2023) to every interpolating estimator and refute the long-training conjecture of Zhang et al. (AISTATS 2025). On one fixed instance, continued training raises the expected risk of GD and fixed-dataset SGD to Θ(log⁡n/n)\Theta(\log n/n), a Θ(n)\Theta(\sqrt n)-fold increase that persists through convergence.

1. Gaussian covariates

Following Reviewer LGWd’s suggestion, we extended our main results to Gaussian covariates.

SettingMain resultImplication
Distribution-free (Theorem 3.1)Rint/Rfree=Θ(log⁡n)R_{\mathrm{int}}/R_{\mathrm{free}}=\Theta(\log n)Unavoidable interpolation penalty
Gaussian mixtures (Theorem 3.4)Rint/Rfree=Θ(1+log⁡(1+nε))R_{\mathrm{int}}/R_{\mathrm{free}} =\Theta(1+\log(1+n\varepsilon))Full logarithmic penalty even for ε=n−1/2→0\varepsilon=n^{-1/2}\to0
Gaussian dynamics (Theorem 4.5)EF(w∞)/EF(wˉn)=Θ(n)\mathbb{E}F(w_\infty)/\mathbb{E}F(\bar w_n)=\Theta(n)Persistent deterioration on the same instance

2. Significance and prior work

Reviewer LGWd questioned whether the logarithmic cost is significant. The significance of our result is not merely the logarithmic factor, but that exact interpolation itself imposes an unavoidable statistical cost.

Theoretical advancePrior finding and open questionOur result
1. Statistical barrierVaškevičius & Zhivotovskiy (Bernoulli 2023): Some ERMs incur a logarithmic penalty. Could a better interpolator avoid it?Theorem 3.1: No. Minimax risk: Interpolation Θ(log⁡n/n)\Theta(\log n/n) vs. unrestricted estimation Θ(1/n)\Theta(1/n).
2. Algorithmic consequenceZhang et al. (AISTATS 2025): Conjectured O(1/n)O(1/n) risk even after arbitrarily long GD/SGD training.Theorems 3.1–3.2: GD/SGD converge to interpolation and inherit the barrier in Step 1: Θ(log⁡n/n)\Theta(\log n/n).
3. Training dynamicsZhang et al. (AISTATS 2025): Is long-run deterioration genuine or merely a loose upper bound?Theorem 4.1: Genuine. Persistent Θ(n)\Theta(\sqrt n)-fold risk deterioration on one fixed noiseless instance.

The other three reviewers emphasized its significance. Reviewer wYz1 wrote, “The most compelling contribution is that the logarithm is necessary for every linear interpolating estimator.” Reviewer Na4t found it “conceptually interesting”. Reviewer 6rJA called the problem “a question of broad relevance”.

3. How the results fit together

At Reviewer LGWd’s suggestion, we revised the abstract, introduction, and section openings to show how the results build on Theorem 3.1. Reviewer wYz1 noted that the proof “isolates a precise obstruction” and called it “a particularly clean use of a lower-bound construction”.

Theoretical progressionCentral questionOur results
1. Statistical limitDoes exact interpolation itself impose an unavoidable statistical cost?Theorem 3.1: Yes. Even the best interpolating estimator has minimax risk Θ(log⁡n/n)\Theta(\log n/n), compared with Θ(1/n)\Theta(1/n) without the constraint.
2. Gradient trainingHow does this statistical cost affect gradient training?Theorem 3.2: GD/SGD converge to interpolation and inherit its Θ(log⁡n/n)\Theta(\log n/n) worst-case risk. Theorem 4.1: On one fixed instance, continued training causes a persistent Θ(n)\Theta(\sqrt n)-fold risk deterioration.
3. Risk certificationIf not every interpolator performs poorly, can we tell whether a trained predictor is accurate?Theorem 5.1: Even at zero population risk, training data alone cannot certify risk below the Θ(log⁡n/n)\Theta(\log n/n) scale. Fresh validation data improve this limit.

In summary, Reviewer Na4t and Reviewer 6rJA support acceptance. Reviewer wYz1 thanked us for the clarifications and indicated they would raise their score, which would put it in the acceptance range. We believe the revisions fully address Reviewer LGWd’s concerns. We would be grateful if you could consider the new results and the reviewers’ feedback in your final assessment.

Best regards,
The authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.