Summary
This paper studies the cost of not regularizing in kernel ridge regression. Suppose you draw some data iid from a distribution, and build a kernel matrix for this data. We could then consider two different Kernel Ridge Regression (KRR) estimators that we learn from this data:
1. The KRR estimator with the best possible regularization (this minimizes the true population risk)
2. The KRR estimator with zero regularization (this minimizes training set error)
The paper asks when the second estimator, which has zero training error because it overfits the training data, has similar true population risk as the first (and statistically optimal) estimator. Specifically, the paper is interested in bounding the ratio of these risks:
$$
\text{ratio} = \frac{\text{Risk of unregularized model}}{\text{Risk of perfectly regularized model}} \geq 1
$$
The paper is interested in the _agnostic_ setting, where we do not assume that the labeled data points are generated, or even well approximated, by a KRR estimator. Specifically, suppose we fix a distribution over input features $x$ (and hence a fixed distribution over kernel matrices) and are allowed to vary the conditional distribution of labels $y | x$. Then, **what is the maximum value that the above ratio can take?**
The paper provides bounds on this maximum ratio, denoted $\mathcal{E}_0$. At the core of the paper is Theorem 6, which provides a tight characterization for which kernels have a benign, tempered, or catastrophic concern about overfitting:
- Overfitting is _benign_ if this worst-case ratio has $\mathcal{E}_0 \rightarrow 1$ as the sample size $n\rightarrow\infty$
- Overfitting is _tempered_ if this worst-case ratio has $\mathcal{E}_0 \rightarrow c>1$ as the sample size $n\rightarrow\infty$
- Overfitting is _catastrophic_ if this worst-case ratio has $\mathcal{E}_0 \rightarrow \infty$ as the sample size $n\rightarrow\infty$
Finite sample guarantees are also given throughout the paper, and those theorems are the focus of the paper. Though, Theorem 6 above, conveys that message most concisely.
The paper is purely theoretical, and has no experiments.
Strengths
The paper asks and interesting questions and formalizes this question nicely. Understanding the worst-case values of this $\text{ratio}$ across all conditional distributions $y|x$ is a good framework. The question carries sufficient significance in producing a fairly thorough understanding of a fundamental ML task (KRR) with and without regularization.
The paper makes a good effort in making the story of the results pretty clear -- we start with a naturally interesting problem, formalize it mathematically, apply a reasonable approximation and assumption, and then tackle benign, tempered, and catastrophic overfitting. The fairly mathematical results are presented nicely, which short theorem statements and clearly worked out examples demonstrating the impact of the theorems. While I sometimes wish the intuitive takeaway of these theorems was more clearly discussed, the many rigorous theoretical examples were nice to see worked out.
All of this is well executed, and piles up enough for the paper to earn a weak accept.
Weaknesses
### Overview
The paper has some presentation and significance issues. I'll give my opinions and thoughts at the top of this box, and back it up with evidence at the bottom of this box.
For significance, the worst-case bounds achieved in this agnostic model are tight only in unrealistic cases. Specifically, the worst-case ratio $\mathcal{E}_0$ should only be representative of the $\text{ratio}$ for a real ML task if the Bayes-Optimal estimator is the always-zero function.
It's understandable and reasonable that we give guarantees in the worst case, but the fact that the worst-case is achieved by an unrealistic setting means that I'm skeptical that this theory can precisely characterize when overfitting actually is benign or catastrophic. The result is nice either way, but any practical takeaways will further require understanding the gap between $\mathcal{E}_0$ and $\text{ratio}$. This harms significance, but is not a deal breaker.
$\phantom{.}$
The paper also suffers from a lack of clear discussion of the mathematics involved. This is felt in two key ways: there are no proof sketches or intuitive justifications for why the theorems should be true; and there are no good intuitions given for key mathematical properties of a kernel used in the theorems. The lack of proof sketches harms my confidence that the results are correct, but frankly the results feel believable, so I'm not really marking down a lot here (though the paper would be significantly improved from just a bit of discussion of what the proofs look like).
The really painful point here is about the **Effective Rank** of a matrix. On page 5, Definition 2 introduces the values $r\_k$ and $R\_k$, both called the _effective rank_ of a matrix. $r\_k$ and $R\_k$ can differ by upwards of a quadratic factor, but no intuitive understanding of the difference between these definitions is given. Further, it's not even clear why we call these "ranks" -- usually the rank of a matrix has no notion of starting to count only from the $k^{th}$ eigenvalue.
Theorems throughout the paper depend on both $r\_k$ and $R\_k$, though $r\_k$ appears more often. I have no understanding of what these value really mean, so when I see Theorem 6 on page 8, I'm not really clear what's going on. This theorem me if our kernel matrix lies in the benign or tempered or catastrophic setting, depending on the limit $\lim\_{k\rightarrow\infty} \frac{k}{r\_k}$. Is this limit a way of characterizing the rate of decay of a spectrum? What kinds of spectra ___intuitively___ make this limit large or small?
This lack of discussion really hurts the clarity of the takeaway from the paper.
---
### Evidence
1. $\mathcal{E}_0$ _only matches_ $\text{ratio}$ _if the optimal KRR estimator is the always zero estimator_:
This follows from the top of page 5, before equation (11). This paragraph says that $\text{ratio} = \mathcal{E}_0$ if we have $v_i = 0$ for all $i=1,...,\infty$. Here, $v_i$ is the $i^{th}$ coefficient in the expansion $f^*(x) = \sum\_{i=1}^\infty v_i \phi_i(x)$ where $f^*$ is the Bayes-optimal estimator and $\phi_i$ is a function in the Mercer-theorem-decomposition of the kernel function. Essentially, since $v_i=0$ for all $i$, we get that $f^*(x)=0$ everywhere, and hence that $\mathcal{E}_0 = \text{ratio}$ only if the Bayes-Optimal estimator is always zero.
2. _There are no proof sketches_:
This is in all of the theorems except Theorem 1, which is proven in the body of the paper. Theorems 2 and 3 on page 5 are good examples though. It's just a theorem statement with discussion of the implication of the theorem. No justification for the correctness of the theorem is given.
3. _$r\_k$ and $R\_k$ can differ by upwards of a quadratic factor._
See page 5, just below equation (13)
4. _Usually the rank of a matrix has no notion of starting to count only from the $k^{th}$ eigenvalue._
This even holds for "smooth" notions of the rank of a matrix, like the intrinsic dimension $tr(K(K+\lambda I)^{-1})$ or the stable rank $\frac{\tr(A)}{\|\|A\|\|_2}$.
Questions
These are really small questions or recommended edits. You don't need to respond to these; make these edits if you want to.
1. [page 2] It feels weird to call (4) representer theorem. It's really just like kernel ridge regression. In my mind, the second line of equation (7) feels more like a representer theorem. This could just be a difference of perspective though.
1. [page 3] I have no idea what spherical harmonics or the Fourier-Walsh (parity) basis are, nor how they apply here. I'd cite something here.
1. [page 3] The omiscient risk estimate and equations (8) and (9) remind me of various ideas from various papers not discussed here. You don't need to discuss them, but I figured I should mention them since they seem relevant:
- The effective regularization constant seems similar to the parameter $\gamma$ in equation (2) on page 3 of _[Precise expressions for random projections: Low-rank approximation and randomized Newton](https://arxiv.org/pdf/2006.10653.pdf)_
- The $\mathcal{L}\_{i,\delta}$ values seems to be exactly _ridge leverage scores_, so that for instance $\sum\_i \mathcal{L}\_{i,\delta}$ is the intrinsic dimension of the kernel. See eg _[Fast Randomized Kernel Ridge Regression with Statistical Guarantees](https://proceedings.neurips.cc/paper_files/paper/2015/file/f3f27a324736617f20abbf2ffd806f6d-Paper.pdf)_ or _[Fast Randomized Kernel Ridge Regression with Statistical Guarantees](https://arxiv.org/pdf/1511.07263.pdf)_ or _[Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://arxiv.org/pdf/1804.09893.pdf)_.
1. [page 4] For reader like me, who forget what pareto-optimal is, move the parenthetical "(point on the regularization path)" earlier in the paper to the first use of the word "pareto"
1. [page 5] The statement that $k = o(n)$ and $R_k = \omega(n)$ is one condition, not two. It's not well defined to say that $R_k = \omega(n)$ without a notion of how large $k$ is. Really, this statement is "$R_k = \omega(n)$ for some $k = o(n)$", which is clearly a single condition.
1. [page 6] At the end of example 1, explicitly note that $\mathcal{E}_0 \rightarrow 1$.
1. [page 7] It's kinda weak that the tempered overfitting doesn't have any matching lower bound part. We are already given the freedom to pick a really adversarial $y|x$ distribution, so it'd feel much more satisfying if the example could fully indulge a proof that $1 < \lim_{n\rightarrow\infty} \mathcal{E}_0 < \infty$. This might be hard, but it'd be a good payoff for strengthening the paper.
1. [page 8] Theorem 6 should be MUCH EARLIER in the paper. It's really clean and is nice to glance at and understand. It would be nice to first see this limiting result, and then see the finite-sample complexity statements that make it up. We could also then always compare a finite sample complexity result back to Theorem 6 from the (eg) introduction, making everything feel more soundly tied together into a comprehensive story.
1. [page 8] I'd change the language a bit in the theorem to recall that $\mathcal{E}_0$ is a worst-case across all $y|x$:
- _then overfitting must be benign_
- _then overfitting can only be tempered_
- _then overfitting can be catastrophic_
These phrases make it clear that, eg, $\mathcal{E}_0 \rightarrow 1$ means that you must always be benign while $\mathcal{E}_0 \rightarrow 3$ means that some $y|x$ can achieve this $\text{ratio}$ of 3 but not that all $y|x$ distributions must do this.
1. [page 8, just above "inner-product kernels"] What is $\mathcal{D}$?
1. [page 8, equation (20)] What is $\mu_{d,k}$?
1. [page 8, below equation (20)] What does i mean for the eigenvalues a matrix to have block-diagonal structure? The eigenvalues don't define a matrix.
1. [page 8, equation (22)] How does this bound on $R_k$ translate to a sufficiently tight bound on $r_k$? If $R_k = \omega(n)$ then we only know that $r_k = \omega(\sqrt{n})$, right?
1. [page 8, below equation (22)] Where and why do we need $\ell$ to be bounded away from being an integer?
1. [page 9, before "conclusion"] Spell out how these limits in this last paragraph imply that you're in the benign regime.
Rating
6: marginally above the acceptance threshold
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.