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?  
 A: 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$.
A: As noted by Leo, the other answer is technically incorrect since it assumes that $x^T x$ is invertible, but this is incompatible with the underdetermined problem where $d > n$, where $x^T x$ is not invertible but $xx^T$ is.
A correct derivation still, however, follows the same approach outlined by elliotp. In general, Lagrange multipliers to optimize a function $f(x)$ subject to the equality constraint $g(x) = 0$ yields the Lagrangian $\mathcal{L}(x, \lambda) = f(x) - \lambda g(x)$.  We form the Lagrangian to optimize the L2-norm $||w||_2^2$ subject to the equality constraint $y - xw = 0$:
$$||w||^2_2 + \lambda^T(y-xw)$$
We differentiate with respect to $w$ and set it to 0.
$$2w - x^T\lambda = 0$$
Left multiply by $x$:
$$2xw - xx^T \lambda = 0$$
Using $y = xw$,
$$2y = xx^t \lambda$$
$$2(xx^T)^{-1}y = (xx^T)(xx^T)^{-1} \lambda$$
$$2(xx^T)^{-1} y = \lambda$$
Using $2w - x^T \lambda = 0$, we get:
$$w = x^T(xx^T)^{-1}y$$
where $x^T(xx^T)^{-1}$ is the right pseudo-inverse of $x$.
Finally, using $y = xx^T \alpha$ from the parent post,
$$w = x^T (xx^T)^{-1}xx^T\alpha$$
$$w = x^T \alpha$$
since the middle term $(xx^T)^{-1}xx^T = I$.
