Does training loss go to zero in kernel regression? Edit
Have left the original post in tact, scroll to bottom for updated thinking
High Level Problem Statement
While studying kernel regression, after playing around with some linear algebra, I appear to have managed to "prove" that training loss always goes to zero.
I'll go on first to explain why I find this problematic. I suspect however the problem is in my "proof" so I attach this in some detail below.
(for everything that follows, I'm assuming OLS loss)
Why is this weird
If the above doesn't concern you, consider the example of the most simple (almost so simple it doesn't make any pragmatic sense) form of kernel regression, Linear-Kernel Linear Regression (which I'll refer to as LKLR).
I stumbled upon a youtube lecture on the topic claiming that LKLR is "exactly the same as linear regression" and took it upon myself to think about what that actually means. I thought a good equivalence claim for a practitioner would be that:
for an unlabelled test example, a linear regressor and a LKLR would make the same prediction, provided they had been trained on the same training data
And after some pages of linear algebra, I believe I did manage to confirm this to be the case. If you didn't already think that training loss going to zero was weird, consider how that squares up against the fact that predictions for unlabelled examples must be equivalent in LKLR.
Because the training loss is zero, we know that the prediction surface of LKLR passes exactly through all data points. However, we also know that LKLR gives the same prediction as Linear Regression for unlabelled examples, and thus its prediction surface is a hyperplane (a line in 1d, a place in 2d, etc). This implies the prediction surface is a hyperplane which kinks infinitely steeply to match the training data...which doesn't seem right at all.
Something's got to give (?)
So I've concluded that in all kernel regression, training loss is zero, but that in LKLR, the prediction surface is the same as in linear regression...something's gotta give presumably.
I assume that the problem is in my proof that Kernel Regression OLS loss is zero, and most likely comes from a flawed assumption about matrix inversion. There probably isn't anything more I can do to set the scene at this point, I'll just dive into the calculation
Calculation/proof
Definition of the Kernel Trick in two stages:
A common misconception is that fitting functions of the form $f(x;a,b,c) = a + bx + cx^2$ is non-linear regression, but that's a story for another day. For what follows, assume we are interested in taking some features given by $\underline{x}$ and fitting a function $f(\underline{x}; \underline{w})=\underline{w}\cdot \underline{\phi}(\underline{x})$ in which  $\underline{\phi}(\underline{x})$ is a vector-outputting function which takes in the original features $\underline{x}$ and maps them to a higher-dimensional space in a parameterless way. An example of this would be $(x_{1},x_{2}) \to (x_{1}, x_{2}, x_{1}^{2}+x_{2}^{2})$
The OLS loss is then given by ($\underline{x}_{i}$ is the feature vector for datapoint i and $y_{i}$ the corresponding target)
$L = \sum_{i=1}^{N}\left(\underline{w}\cdot \underline{\phi} (\underline{x}_{i}) -y_{i}\right)^{2}$
and one could perform gradient descent as in standard linear regression, or differentiate wrt $w_{j}$ and solve via linear algebra (Moore-Penrose Pseudoinverse)
An alternate solution is the so-called "Kernel Trick" which consists of firstly reparametrising in terms of $N$ parameters $\underline{\alpha}$ and writing down the constraint
$ w_{j} = \sum_{i=1}^{N}\alpha_{i} \underline{\phi}(\underline{x}_{i})_{j}$
in which $\underline{\phi}(\underline{x}_{i})_{j}$ is the $j^{th}$ component of the mapping $\underline{\phi}(\underline{x}_{i})$ and I'll refer to this as $\phi_{ij}$ from now on, so that
$w_{j} = \sum_{i=1}^{N}\alpha_{i} \phi _{ij}$
Note that we are parametrising $\underline{w}$ in terms of $\underline{\alpha}$, the former having M components and the latter having N, where we assume N>M, and thus this equation is underdetermined, there will be many different $\underline{\alpha}$ vectors that satisfy this constraint. This is the first part of the kernel trick and has always seemed a bit weird to me. It's possible that I've misunderstood this part which might explain where I'm going wrong, any comments greatly appreciated.
Finding the optimal loss in Kernel Regression:
If I reparametrise the cost function in terms of $\underline{\alpha}$, after some sum manipulations which I'll spare you, I find
$L = \sum _{i=1}^{N} \left(\sum _{j=1}^{N} \alpha_{j} \left(\underline{\underline{\phi}} \cdot \underline{\underline{\phi}}^{T}\right)_{ij} - y_{i} \right)^{2}$
in which I've used the notation $\underline{\underline{\phi}}$ to show that this is a matrix, in which the entry $(i,j)$ has the same meaning as $\phi _{ij}$ above.
The second part of the kernel trick is that one now realises that the loss only depends on the data through the matrix product $\underline{\underline{\phi}}\cdot \underline{\underline{\phi}}^{T}$. This means at no point do we need to define explicitly the function $\underline{\phi}(\underline{x})$, we just need to define $\left(\underline{\underline{\phi}}\cdot \underline{\underline{\phi}}^{T}\right)_{ij}$, or $\underline{\phi}(\underline{x}_{i})\cdot \underline{\phi}(\underline{x}_{j})$. We tend to give the matrix $\underline{\underline{\phi}}\cdot \underline{\underline{\phi}}^{T}$ the name $\underline{\underline{K}}$, and we must define $K_{ij}$ in terms of $\underline{x}_{i}$ and $\underline{x}_{j}$. This is what makes the Kernel Trick so beautiful/powerful, you don't need to come up for weird and wonderful mappings $\underline{\phi}$, you just need to come up with powerful kernel functions $k(x,y)$ so that $K_{ij} = k(\underline{x}_{i}, \underline{x}_{j})$
When I take the loss function parametrised through $\underline{\alpha}$ and differentiate wrt $\alpha_{k}$ I find that
$\frac{\partial L}{\partial \alpha_{k}} = 2\sum _{i=1}^{N}K_{ik}\left(\sum_{j=1}^{N}\alpha_{j}K_{ij} - y_{i}\right)$
so after further sum manipulations, I find that
$ \nabla _{\alpha} L = 2\underline{\underline{K}}^{T}\cdot \left(\underline{\underline{K}}\cdot \underline{\alpha} - \underline{y} \right) $
and thus the $\underline{\alpha}$ which optimises the loss is given by
$\underline{\alpha} = (\underline{\underline{K}}^{T}\cdot \underline{\underline{K}})^{-1}\cdot \underline{\underline{K}}^{T}\cdot \underline{y}$
which provided $\underline{\underline{K}}$ is invertible simplifies to
$\underline{\alpha} =\underline{\underline{K}}^{-1}\cdot \underline{y}$
Substituting this back into the loss function, I find that
$L = \sum_{i=1}^{N}\left( \sum_{j=1}^{N}\left(\sum_{k=1}^{N}K^{-1}_{jk}y_{k}K_{ij}\right) - y_{i}\right)^{2}$
which, after manipulating summation order gives
$ L = \sum_{i=1}^{N}\left( \sum_{k=1}^{N}y_{k}\left(\sum_{j=1}^{N}K_{ij}K^{-1}_{jk}\right) - y_{i}\right)^{2}$
in which the term in the innermost bracket is readily identified as the Kroneker delta and thus the whole thing is zero.
I appreciate that I assumed $\underline{\underline{K}}$ is invertible, and it might be difficult to invert K in practice due to numerical instabilities, but I see no reason why it would fundamentally never be invertible ?
Final Remarks
To conclude, I've outlined my proof that training loss is zero for kernel regression, a proof that I suspect must be flawed. My suspicion is that the flaw is either in my understanding of the first part of the kernel trick, i.e. reparametrising the algorithm in terms of $\underline{\alpha}$ which has exactly N entries, or in my assumption that $\underline{\underline{K}}$ is invertible.
Edit
I stated a number of times that $\underline{\underline{K}}$ is invertible. However, $\underline{\underline{K}}=\underline{\underline{\phi}}\cdot \underline{\underline{\phi}}^{T}$. Generally speaking, I believe that unless $\underline{\underline{\phi}}$ is square, only one or the other of $\underline{\underline{\phi}}\cdot\underline{\underline{\phi}}^{T}$ and $\underline{\underline{\phi}}^{T}\cdot\underline{\underline{\phi}}$ will be invertible.
This is perhaps an oversimplification, but I believe that if $N>M$, then $\underline{\underline{\phi}}^{T}\cdot\underline{\underline{\phi}}$  is the invertible one and when $M>N$ it's $\underline{\underline{\phi}}\cdot\underline{\underline{\phi}}^{T}$. So K is invertible when $M>N$, and then this calculation is valid, and that's when you'd expect the loss to go to zero.
However when $N>M$, then this calculation is not valid, and thus the loss does not go to zero, as you would not expect it to.
 A: I have just been introduced to kernel methods this month and I think it's natural to have this thought. What you call $ \underline{\underline{K}} $ is canonically called the Gram matrix $ \mathbf{G} $. If you have some experience in python or matlab, it's pretty easy to find kernels and datasets which together create uninvertible Gram matrices. This is trivially true if you have colinear data points in your training set, although it is otherwise possible as well. On the conceptual level: $\phi$ does lift $\mathbf{x}$ to a feature-rich space, but that doesn't mean that those features are at all useful in separating the training data.
That said, if your dataset is free of collinearities you can always construct a kernel which creates an invertible Gram matrix $G$. The LKLR is an example. A less trivial example is the Gaussian Radial Basis Function
$$K_{RBF}(\mathbf{x},\mathbf{z}) = \exp\left(-\left(\frac{\Vert\mathbf{x}-\mathbf{z}\Vert}{\sigma}\right)^2\right)$$
As $\sigma$ approaches 0, the matrix $\mathbf{G}$ approaches the identity matrix, which is guaranteed to be invertible.
