Summary
This submission establishes equivalences between ridge regression (i.e. $\ell_2$-penalized
linear regression) and ensembles of linear models trained on sub-sampled datasets.
In particular, the authors prove that for a fixed feature/sub-sample-size $d/k$, ratio, there
exists a ridge-regression model with risk asymptotically equivalent to the full
ensemble, i.e. the average of all $k$ models trained on sub-samples of size $k$.
Moreover, this equivalence holds for all convex combinations of the
ridge-regression and full sub-sampled model.
Note that the asymptotics assume $d$, $k$, $n$ approach infinity such that
the ratios $d/k$ and $d/n$ are held constant.
This equivalence result is then extended to other metrics, such as training error
and the weight estimation error, and to "structural" results which
show asymptotic equivalence of the weights of the models.
The authors leverage these equivalences to show that the prediction
risk of the best ridge regression model is monotone increasing in $d/n$.
Strengths
The main strength of this work is the theoretical contributions. In
particular:
- The authors extend exist results on equivalent risk of ridge regression
models and sub-sampled ensembles to new metrics and to the model weights
themselves ("structural results").
- The theorems are proved under relaxed conditions compared to previous work.
In particular, general data distributions are allowed provided a fairly
weak assumption on the moments holds.
- The authors answer an open problem on the behavior of risk for ridge regression
models with the optimal regularization constant.
The paper is also well written, with very few typos. I congratulate the authors
on their polished manuscript.
Related work appears to be correctly cited, although this is not my research
area so it is hard for me to check.
Note that I did not check the theoretical derivations in the appendix so I
cannot comment on their correctness.
Weaknesses
The greatest weakness of this paper is that the theoretical results are
somewhat incremental and unlikely to have an impact outside of learning theory.
In particular,
- The connection between ridge regression and sub-sampled ensembles was
previously established, so that the main contributions of this work
are weakened conditions and new types of equivalences.
- It's not clear how interesting it is to answer the conjecture from
Nakkiran et al. While the authors prove that the risk for the ridge
regression model with optimal regularization constant is monotone
increasing in the ratio $d/n$, this only applies to the asymptotic
regime and so its practical importance may be limited.
- While the authors motivate their work by highlighting connections between
ridge regularization and dropout, noisy training, data augmentation,
and early stopping. However, these connections are not developed any further
and I am skeptical the asymptotic equivalences in this submission will
impact those areas.
Questions
Line 93: Is this supposed to mean that Assumption 2 defines RMT features?
It's not obvious because the acronym RMT is not defined anywhere and
not used in Assumption 2.
Line 176: I suggest Changing the name of Assumption 2 from "Feature Vector Distribution"
to "RMT" features as well as including a definition for the initialism/acronym, since
it isn't stated anywhere.
Line 156 and Definition E.1: Does $C_p$ need to be bounded away from zero?
Otherwise the asymptotic
equivalence definition will be meaningless when $C_p = 0$ almost surely
for every $p$. Or perhaps when you say "any sequence $C_p$" you mean
"every sequence"?
Line 183: Shouldn't this solution be $(\\lambda, \\bar{\\psi})$?
Figures 1/2: The paths between equivalent models don't appear to be linear
in these figures, although Equation 5 seems to indicate that they are always
linear combinations. Is this because the figures are in log-log scale?
Theorem 3: I don't understand what is "structural" or "first-order" in this
theorem compared to Theorem 1. Is this because the estimators themselves
are equivalent, rather than a risk functional of the estimators?
While is equivalence of risk functionals "second order"?
Theorem 3: "this implies that the predicted values (or even any continuous function
applied to them due to the continuous mapping theorem) of any test point will eventually be the same,
almost surely, with respect to the training data."
The asymptotic equivalence of parameters in Theorem 3 and this
statement seem to imply that Theorem 3 covers both Theorem 1 and Proposition 2
by taking $M = \\infty$ --- is this correct?
If yes, what is the novelty of these two previous results given Theorem 3?
Proposition 4: Is Equation 8 always guaranteed to admit a solution?
Moreover, what is the utility of this result when the equivalence only
holds asymptotically? That is, when $n \rightarrow \infty$ and the
root-finding problem defined by Equation (8) is impractical to solve.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
As mentioned in the "Weaknesses" section, I think the main limitation of this
submission is the impracticality of the main theoretical results.
Since they extend and generalize a previous result showing asymptotic equivalence
of the risk, I do not see the theoretical derivations having an impact on practice.
Furthermore, the connections to high-interest topics in ML like early stopping
and dropout seem tenuous at best.
Since I am not actively involved in learning theory research, I cannot
comment on the importance of this work for other members of this community.
It would be nice if the authors could provide additional context for their
work, including some comments on the novelty of their proof techniques and so
on. That way I can better understand the impact on this specific research community.