# Implicit Regularization in SGD on linear model

This question is about the apparent implicit regularization that is observed when training a linear model using SGD. I describe my understanding in the hope that someone can point out what I'm missing.

In Section 5 of Understanding Deep Learning Requires Rethinking Generalization, we are given the problem of fitting a linear model $$y=Xw,$$ where $y$ is the model output, $X$ is the $n \times d$ data matrix with $n$ observations of $d$-dimensional data points and $w$ are the parameters to be learnt. If we let $d \geq n$ then the system has an infinite number of solutions.

The paper goes on to derive the kernel trick (without an embedding into feature space) in the context of SGD. If we run SGD we get a solution of the form $w=X^T\alpha$ due to the update rule. We also have that $y=Xw$. Combining these two, we have $$XX^T\alpha = K \alpha = y.$$

This part (I think) I understand. I don't understand this part:

Note that this kernel solution has an appealing interpretation in terms of implicit regularization. Simple algebra reveals that it is equivalent to the minimum $\ell_2$-norm solution of $Xw=y$.

How is it known that this solution has the minimum $\ell_2$-norm?

• For a more general and recent discussion, see: Implicit Regularization in Deep Learning, arxiv.org/pdf/1709.01953.pdf – Student Dec 1 '17 at 0:17

The minimum $\ell_2$ norm solution can be found by solving the constrained optimization problem:

$\underset{w}{\min} \Vert w \Vert_2^2~~s.t.~~y=Xw$

This can be written as an unconstrained convex optimization using the method of Lagrange multipliers at the limit $\lambda \rightarrow \infty$:

$\underset{w}{\min}{\left(\Vert w \Vert_2^2 + \lambda \Vert y - Xw \Vert_2^2\right)}$

The reason $\lambda \rightarrow \infty$ is that we want $y=Xw$ exactly, with zero squared error.

This is a convex function, so the gradient should equal zero at the minimum:

$2w - 2\lambda X^T\left(y-Xw \right)=0$

$w\left(I+\lambda X^TX\right) = \lambda X^T y$,

where $I$ is the identity matrix. At the limit $\lambda \rightarrow \infty$, the solution is:

$w^* = \left( X^TX\right)^{-1}X^Ty$

where $\left( X^TX\right)^{-1}X^T$ is known as the left pseudoinverse of $X$.

Now, we use $w=X^T \alpha$ to replace $y$ with $XX^T \alpha$

$w^* = \left( X^TX\right)^{-1}X^T XX^T \alpha = X^T \alpha =w$

Therefore, if $w=X^T \alpha$ then the minimum $\ell_2$ norm solution for $y=Xw$ is the same: $w^*=X^T \alpha$.

• Don't think I've seen the ls solution derived like this (+1). It seems unintuitive to me to put the $\lambda$ on the $X^TX$ rather than on the Identity (and sending the limit to infinity rather than 0). Is there a benefit to thinking about it this way that I've missed? – David Kozak Nov 29 '17 at 15:07
• The solution is the same, I just find this form to arise more naturally if what we're minimizing is $\Vert w \Vert_2^2$ and the regularization represents a penalty that replaces the constraint $y=Xw$. – elliotp Nov 29 '17 at 17:21
• Thanks for the answer. Is this a well-known result? And the authors of the paper seem to expect that this result holds more generally to non-linear models - is this accurate? – Student Nov 29 '17 at 22:17
• The fact that the pseudoinverse gives the minimum $\ell_2$ norm solution to an overcomplete problem is well known. The relation to SGD with that kernel was new to me. – elliotp Nov 29 '17 at 23:04