- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the problem how regularization geometry and signal sparsity affect generalization in the regime where training data is almost perfectly fitted. The paper proposes a zero-one loss under the overparameterized (high-dimensional) noiseless regression setting. In the regime where feature dimension is proportional to the sample size, the authors characterize the estimation error of the optimal solutions of their regularized loss objective as well as the MNI solutions. They further apply their convergence results to understand, when a solution is nearly perfect for training data fitting, how much benefits to generalization does it have to make it fit the training data exactly, and how does it depend on the regularization norm geometry and weights sparsity.
Critical strengths
-
I like this paper a lot due to its substantial theoretical contributions to the understanding of regularization-driven generalization. I checked most part of the proofs and haven't found any critical/unsolvable bug. Hence, I truly value that the results and proofs are rigorous and well-written. The proof seems novel and nontrivial, making the technical part of this paper strong.
-
They provide a new perspective of grokking. Rather than understanding how a finite-step optimization algorithm induces grokking, they focus on understanding that, when a solution is nearly perfect for training data fitting, how much benefits to generalization does it have to make it fit the training data exactly.
Critical weaknesses
-
I think the main theoretical results of the paper is not directly related to the topic "grokking". Basically, the paper proves a sharp transition in generalization across regularization geometries, but does not establish delayed generalization along an optimization trajectory in terms of the training steps/time. Later in section 4.2 and 4.3, the paper focuses on the properties of the optimal solutions to the regularized loss objective rather than optimization solutions with fixed training time. I noticed that the authors also propose in their conclusion section that "A natural next step is to quantify the correspondence observed between early-stopped diagonal networks and regression with their initialization-dependent implicit regularizer." Therefore, I think maybe it's better to not put the main focus on grokking but instead mention grokking as an application? That said, I still believe the current work provides a new perspective of understanding grokking and could potentially shed light on establishing end-to-end provable grokking in non-linear learning scenarios.
-
The main results are almost asymptotic. Is it possible to derive non-asymptotic analysis with finite sample size and feature dimension to bound the gap to its asymptotic limit?
Questions for authors
My main concerns are in the above weakness part. The following are some minor things.
-
In Equation (4), since the training loss is evaluated on the square root of MSE, I would expect the generalization/test loss to be evaluated on the square-rooted population MSE where is an i.i.d. test instance. However, if I calculate correctly, its evaluation instead satisfies . Therefore, I expect the generalization measure to be , though preserves comparisons. Moreover, I believe your results could survive under the evaluation of the square-rooted population MSE. Hence, there won't be any technical issue but just to make the results more natural and understandable.
-
Regarding Lemma 1, since the authors study the ordinary -regularized MSE on the high-dimensional regression with sparsity (LASSO), I believe that abundant works have established convergence results for the estimator (convergence in probability or even almost-surely convergence). I don't mean that Lemma 1 is lacking novelty compared to existing works, but I think its incremental novelty needs to be clarified carefully.
-
Regarding Theorem 1, while the result is clean and elegant, the regularization objective seems, however, artificial and impractical. It would be better if such a separation can be identified and proved with some natural choice of learning objectives/algorithms. Do you know any of such candidates?
-
I found the writing of Section 4.2 a bit messy and not very understandable. For example, it is hard for me to follow what is the purpose to write Equations (12) and (13). I feel that add more explanations such as "why the scalar estimator studied here is related and useful to the previous high-dimensional regression problem" before the mathematical interpretation would make the idea more clear. Also, Lemma 2 is also hard to parse due to many notations are defined without explanation.
4 comments
Part II
Question 2. Novelty of Lemma 1 relative to existing results.
We agree that sparse recovery and Lasso risk have an extensive literature. Lemma 1 concerns square-root Lasso, but we do not claim novelty for this estimator, the leading Donoho–Tanner recovery threshold, or Gaussian comparison methods. The novelty is in a quantitative all-or-nothing law along the regularization path: every fixed yields exact recovery, whereas every fixed yields asymptotically trivial relative risk.
The substantive step is to control all competing predictors, including mixtures of signal and off-support coordinates. Comparing the objectives at and zero suggests the threshold but does not exclude intermediate solutions. Above the transition, our proof establishes
\quad\Longrightarrow\quad \\|b\\|_2^2+\\|b\\|_1\le C_\kappa\frac{k_\*^2}{n}.$$ This controls the entire sublevel set, rather than only a selected optimizer. The $\ell_1$ bound controls the signal–estimator cross term and yields the $O_\kappa(L^{-1})$ relative-risk rate for every minimizer. In the revision (see the last paragraph of Section 4.1), we have expanded the comparison with [Bayati and Montanari (2012)](https://arxiv.org/abs/1008.2581) and [Miolane and Montanari (2021)](https://arxiv.org/abs/1811.01212). Their usual formulations at fixed positive aspect ratio do not directly establish our joint limit $n/p\to0$, $k_\*\sim n/(2\log(p/n))$, and $\log p=o(n)$ without additional uniform estimates. We also discuss the related all-or-nothing results of Reeves et al. ([2019a](https://proceedings.mlr.press/v99/reeves19a.html), [2019b](https://arxiv.org/abs/1912.13027)). Our trivial-risk conclusion is specific to the estimator, as regularization varies with the statistical model unchanged, rather than an information-theoretic impossibility as sampling parameters vary. **Question 3. Theorem 1’s construction and natural alternatives.** We agree that Theorem 1 is deliberately calibrated. However, the construction has a simple interpretation: with $m_\kappa=(p/\kappa)\sqrt{2/(\pi L)}$, it is the sum of the largest $m_\kappa$ absolute coordinates, with fractional interpolation when $m_\kappa$ is noninteger. It therefore preserves the $\ell_1$ cost of sufficiently sparse representations while discounting dense residual completions. We have clarified this connection to the classical top-k norm right before the statement of Theorem 1. **Question 4. Clarity of Section 4.2.** Thank you for pointing this out. We agree that the connection between the scalar estimator and the high-dimensional regression problem could use a clarification. To address this, we have revised the opening of Section 4.2 and added the new paragraph **“Scalar denoising problem.”** There, we first explain the purpose of the scalar characterization: it reduces the computation of the asymptotic training error and MSE to solving two equations for an effective noise level and a shrinkage parameter. We introduce the meaning of the scalar variables and parameters, and explicitly connect the scalar estimator to regression: under the assumptions of Lemma 2, the joint empirical distribution of the true and estimated coefficients converges to the law of $(B,f_{\tau_\kappa,\alpha_\kappa})$, as established in Remark 3. In particular, the scalar estimation error gives the limiting regression MSE. To clarify the notation used in Lemma 2, we now explain the roles of H_r,D_r,U_r before defining them in Equation (16). These quantities describe the normalized squared error, average sensitivity, and normalized coefficient moment, and enter the characterization of the MSE, training residual, and regularization calibration, respectively. Together with the explanation following Lemma 2—that the first equation in (17) determines the effective noise level from the observation noise and estimation error, while the second relates scalar shrinkage to the regression penalty—this makes explicit why these equations are introduced and how they characterize the original regression estimator.References
-
Bayati, M., and Montanari, A. (2012). The LASSO risk for Gaussian matrices. IEEE Transactions on Information Theory, 58(4), 1997–2017.
-
Celentano, M., Cheng, C., and Montanari, A. (2021). The high-dimensional asymptotics of first order methods with random data. arXiv preprint, arXiv:2112.07572.
-
Donoho, D. L., and Tanner, J. (2009). Counting faces of randomly projected polytopes when the projection radically lowers dimension. Journal of the American Mathematical Society, 22(1), 1–53.
-
Miolane, L., and Montanari, A. (2021). The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning. The Annals of Statistics, 49(4), 2313–2335.
-
Reeves, G., Xu, J., and Zadik, I. (2019a). The all-or-nothing phenomenon in sparse linear regression. Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99, 2652–2663.
-
Reeves, G., Xu, J., and Zadik, I. (2019b). All-or-nothing phenomena: From single-letter to high dimensions. 2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), 654–658.
I thank the authors for your careful response and the substantial amount of additional work that you have done in the rebuttal. I will maintain my score!
Part 1
We thank the reviewer for the careful reading and positive assessment of our work. We respond to all comments below, and we have uploaded a revision marking the new text in red.
Weakness 1. Connection to grokking and scope of our contribution.
We agree that grokking is a temporal phenomenon. Our contribution addresses a complementary statistical question: why can further fitting yield substantial generalization improvements when training error is already nearly zero, and what determines those improvements? We quantify generalization against training residual, separating this question from the speed at which an optimizer traverses its trajectory. In the stated regimes, we prove that more sparsity-promoting regularization and sparser signals yield larger generalization gains near interpolation, with the gain becoming unbounded in the noiseless ℓ1 case.
Our experiments on diagonal networks support the algorithmic relevance of this perspective by exhibiting the predicted dependence on initialization-induced bias and signal sparsity. Furthermore, in the paragraph “Regularization paths and training dynamics” in Section 6 of the revision, we develop a theoretical connection between gradient training and regularized regression by showing that, in the dual space, they both operate on the same strongly convex landscape. See also our response to Reviewer 3zYZ for details.
Having said that, a sharp characterization of the training curve remains an outstanding open direction. In that regard, the dual formulation put forward in Appendix F of the revision suggests exploring dynamical mean-field methods, such as those of Celentano et al. (2021), although applying them here is likely to require novel technical ideas.
Weakness 2. Non-asymptotic analysis.
Following the reviewer’s suggestion, the revised version provides non-asymptotic versions of the results in Lemma 1, Theorem 1, Lemma 2, and Lemma 3. We briefly discuss them below, and we have revised the manuscript accordingly.
Writing L=2log(p/n) and retaining the stated calibration of k\* and the sparsity margin η, for each fixed 0<κ<1, Lemma 1 gives unique exact recovery with probability at least 1−e−cnη2, for all sufficiently large dimensions along the stated sequence. For each fixed κ>1, every minimizer satisfies
\le C_\kappa\frac{k_\*}{n}, \qquad 0\le1-\mathcal E_s(\widehat\beta_{\kappa,1}) \le C_\kappa\frac{k_\*}{n},$$ with failure probability at most $e^{-c_\kappa k_\*}$. Since $k_\*/n\asymp L^{-1}$, these are $O_\kappa(1/\log(p/n))$ deviations with exponentially small failure probability. Theorem 1 similarly gives exact interpolation with exponentially high probability and, above the transition, $$\left|\mathsf{MSE}_s(\widetilde\beta_\kappa)-1\right| \le C_\kappa\left(\frac{k_\*}{n}+\sqrt{\frac np}\right) =O_\kappa(L^{-1}).$$ Below the transition, it gives exact recovery, with an additional exponentially small failure term from the interpolation argument. Finally, for strictly positive noise and i.i.d. signal coefficients, both Lemma 2 and Lemma 3 can be made non-asymptotic, and the resulting rate is of order n-1/4. This is proved in the new Proposition 3 added to Appendix C.1 of the revision. **Question 1. Squared versus square-root generalization error.** We agree that Equation (4) should explicitly distinguish coefficient estimation error from population prediction RMSE. For an independent test covariate $x\sim N(0,I_p/n)$, conditionally on the training data, $$\mathbb E_x\langle x,b-\beta_\*\rangle^2 =\frac1n\\|b-\beta_\*\\|_2^2 =\frac pn\\,\mathsf{MSE}(b).$$ Thus, the prediction RMSE against the regression function is $\sqrt{(p/n)\mathsf{MSE}(b)}$, as the reviewer suggests. The prediction of a noisy test response additionally includes $\sigma^2$ in the squared error. Importantly, **the zero–one conclusions and quantitative rates survive the suggested square-root evaluation**. Normalization by the zero predictor gives $$\mathsf{RMSE}_s(b)=\sqrt{\mathsf{MSE}_s(b)},$$ and $|\sqrt{x}-1|\le|x-1|$ preserves the upper-side deviation bounds. Exact recovery still gives zero. We keep the MSE in Section 4.3, noting that taking square roots preserves which estimator generalizes better, but rescales derivatives and does not automatically preserve their ordering across different problem parameters.