Non-Ridge Kernelized Regression? Every presentation that I have seen for kernelized regression focuses on finding
$$\underset{f \in \mathcal{H}_k}{\min} \sum_{i=1}^{n}(y_i-f(\mathbf{x}_i))^2+\lambda \|f\|^2_{\mathcal{H}_k}.$$
Here, $\mathcal{H}_k$ is a Reproducing kernel Hilbert space (RKHS).
I was wondering

*

*Why the focus on ridge regression? Can we use other penalties here, or is there something about the ridge penalty that is natural in this setting?

*Can we do un-penalized kernelized regression? Why is this not usually presented prior to kernel ridge regression?


Great question!
Alternative Norms Exist (kind of): Though we call it "Kernel Ridge", let's take a second to note that the norm we're using is the RKHS norm (whereas regular "ridge regression" penalizes the $\ell_2$ norm of the parameter vector). One could consider a different function space norm to be penalized instead, like an $L_p$ norm. Alternatively, we could directly penalize the kernel coefficients, as in this article about kernel lasso. But yeah, what's so nice about the RKHS penalty is that its solution is available in closed form (from the Bayesian perspective, it is a conjugate prior to the normal likelihood). GPs wouldn't be nearly as popular if you needed to solve a nonlinear optimization program to use them. (but you often do anyways if you have enough kernel hyperparameters to estimate...)
Other Approaches than Penalties Exist (kind of): The reason we usually use regularization in kernel regression is because we have, in effect, an infinite dimensional parameter space, with one "column" associated with each possible input location: $k(\mathbf{x},.)$. Without regularization, there are not only infinitely many solutions which interpolate our data (which is possible in underdetermined, finite-dimensional regression), but indeed most of those solutions are made of infinitely many kernel functions $\hat{f}=\sum_{i=1}^\infty a_i k(\mathbf{x}_i,.)$. So we want some way of simplifying things. But it doesn't have to be a penalty per se. Usually we solve:
$$ \min_{f\in\mathcal{H}_k} \sum_{i=1}^N (f(\mathbf{x}_i)-y_i)^2+\lambda||f||_{\mathcal{H}_k} $$
which has solution given by $\alpha = (\mathbf{K}+\lambda \mathbf{I})^{-1}\mathbf{y}$ then $\hat{f}=\sum_{i=1}^N \alpha_i k(\mathbf{x}_i,.)$.
But instead of solving a penalized problem, we could instead solve this constrained one:
$$ \min_{f\in\mathcal{H}_k} ||f||_{\mathcal{H}_k}$$
$$\textrm{Such that:}$$
$$\sum_{i=1}^N (f(\mathbf{x}_i)-y_i)^2 = 0 $$
Which has solution given by $\alpha = (\mathbf{K})^{\dagger}\mathbf{y}$, where $\mathbf{A}^\dagger$ gives the Moore-Penrose Pseudoinverse of $\mathbf{A}$. [I should mention I have the noiseless case in mind here, where $y_i$ is observed exactly as $f(\mathbf{x}_i)$].
Now the reason I put "kind of" above is that this is clearly what the limit of our penalty method gives us as $\lambda\to 0$, so while not a penalty method, it is a limit of them. There may be other, truly different ways of sieving it down to a finite dimensional approximation space that are useful in applications, but I haven't personally run into them.
