- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the relationship between training loss and generalization in high-dimensional linear regression. The authors show that, under specific spectral and dimensional conditions, well-generalizing predictors must incur large training losses. They further establish conditions under which one-pass SGD achieves vanishing test error despite increasing training loss, and demonstrate how label-irrelevant signal directions can affect SGD's generalization performance.
Critical strengths
-
The paper provides formal guarantees showing that well-generalizing predictors necessarily incur large training losses under the specified assumptions.
-
The authors derive necessary and sufficient conditions for the consistency of one-pass SGD in the considered setting.
-
The paper illustrates how label-irrelevant high-variance features can affect SGD's generalization performance.
Critical weaknesses
-
The theoretical results rely on a highly specialized setting, including noiseless Gaussian linear regression, specific covariance structures, and restrictive dimensional scaling conditions. It is unclear whether the observed phenomenon persists under more general or realistic settings.
-
The relationship between overfitting and generalization in high-dimensional regression has been extensively studied. Although the paper establishes a stronger theoretical characterization, it remains unclear what fundamentally new insights it provides beyond existing understandings of overfitting and regularization.
-
The analysis focuses on one-pass SGD with a batch size of one and a constant learning rate. Given the extensive literature on online SGD for linear regression, the authors should better clarify the novelty of their results and whether the conclusions extend to more common optimization settings.
-
The experiments primarily focus on synthetic settings closely aligned with the theoretical assumptions. Additional experiments examining the sensitivity to sample size, covariance structure, and optimization settings would help establish the broader relevance of the findings.
Questions for authors
-
How do the main findings differ fundamentally from existing results on overfitting and regularization in high-dimensional linear regression? What new insights does the misfitting phenomenon provide beyond the established trade-off between training overfitting and generalization?
-
How essential are the specific spectral and dimensional scaling assumptions? Does the misfitting phenomenon persist when these assumptions are relaxed, particularly when the sample size increases relative to the feature dimension?
-
How do the results differ from existing analyses of online SGD for linear regression? Do similar conclusions hold for multi-pass SGD, mini-batch SGD, or decaying learning rates?
-
Can the authors provide empirical evidence of the misfitting phenomenon under more realistic data distributions or learning settings, beyond the synthetic constructions used in the paper?
Misfitting isn't the same as benign overfitting or where traditional regularization would take us. And misfitting happens quite generally, not just when our theorem's assumptions hold.
Thank you for your review and for asking how misfitting differs from ordinary regularization.
1. What does misfitting add to the usual trade-off between training fit and generalization?
Regularization has always given up some training fit for better generalization.
But how much training fit can we give up with positive ridge? Positive ridge's training loss can never exceed that of the zero predictor. In the regime of out Theorem 1, a predictor whose coefficients are a weighted sum of training inputs (a span predictor) must incur many times that loss to beat the zero predictor's test error by a fixed fraction. This rules out positive ridge, however its penalty is chosen, even from the data. Our submission shows that this effect arises even with noiseless labels and fresh inputs from the same distribution.
What does work is moving the other way. Guarded negative ridge learns both example problems of our Corollary 4. In the easier one, a single large-step SGD pass also learns the target while ending with higher training loss than it started with.
Why is the fit so much worse on the training points? A weighted sum of training inputs picks up their nuisance features (weak features unrelated to the label). On a training point those features line up with themselves. On a fresh point they are independent and contribute much less error. Ranade and Sahai showed this mechanism with one signal direction. Our Theorem 1 extends it to random inputs with several signal directions.
2. How essential are the assumptions, particularly as sample size increases?
More data can remove the need to misfit. Suppose the sample size n far exceeds the number of signal directions and is far smaller than the number of nuisance directions. With common signal variance γ and d0 unit-variance nuisance directions, the misfitting range is d0/γ2≪n≪d0/γ. Far below it even the best span predictor learns little. Far above it the interpolator predicts well (Appendix G). For unequal strengths, the weakest and strongest signals set the lower and upper ends of Theorem 1's guarantee, respectively.
We use Gaussian sampling to control inner products in the training-loss proof and to obtain the exact SGD recurrence. The experiment below shows the effect with non-Gaussian inputs, correlated features and a decaying background spectrum. The misfitting phenomenon is far more general than the proof here.
3. What is new about online SGD? What extends to mini-batches, extra passes and decaying rates?
The upper bounds of Varre et al. and Zou et al. use steps too small to learn even the strongest signal in one pass here. Could a larger step work? In the misfitting regime, one constant rate learns every target precisely when sample size grows faster than total signal variance divided by the weakest signal variance (our Theorem 3).
Mini-batches and extra passes can change which predictor SGD finds. Starting from zero, linear SGD stays in the training span even with minibatches and learning-rate schedules, so any accurate (i.e. good generalization) iterate must fit poorly. If no single-example step enlarges the error on the example it uses, test error stays near that of predicting zero for any number of passes (Proposition E.1).
In our Corollary 4's easier example, we find that a late rate cut preserves vanishing expected error. Raising only variances in directions the label ignores gives the harder example "B". There, no nonnegative schedule fixed before training makes one-pass expected error tend to zero as the problem grows. Data-dependent (but not precient) rates remain open.
4. What happens with less restrictive data and different optimizers?
We tested a Fourier kernel on a phase x drawn unevenly around a circle. The signal is proportional to sin(2πx)+sin(4πx). Uneven sampling gives neighboring sine features a correlation of 0.25. The 32,000-plus background frequencies have variances that decrease from 13.5 to 0.5.
How well could we fit the data if we required test error at most one quarter of the zero predictor's? The known covariance lets us compute the minimum training loss in the span. With 64 examples, even that minimum exceeded the zero predictor's training loss on all 64 draws (median ratio 2.33). With 128 examples, it fell below that baseline on every draw (median ratio 0.28). Including a background frequency correlated with the signal preserved the 64-example result on every draw.
With 64 examples the minimum-norm interpolator fit every label and had median test error 0.632 (predicting zero gives 1). One pass of SGD gave 0.081 despite median training loss 13.8 times that of predicting zero. Adding momentum of 0.1 gave 0.077. Adam scales each coordinate's update separately. At the same step size its median test error went from 0.863 in the sine coordinates to 0.143 after a random rotation. We will add this experiment and the sample-size comparison to the revision.