How to set up a linear system to interpolate the train data perfectly with Gradient Descent?

Consider a (consistent) regression problem (i.e. we are trying to predict a real valued function and we don't have inconsistencies in the way we map x's to y).

I am trying to perfectly fit/interpolate the (train) data set with Gradient Descent (to understand academically Gradient Descent better) with fixed step size:

$$w^{(t+1)} = w^{(t)} - \eta \nabla_w L(w^{(t)})$$

I've tried things empirically by minimizing L2 loss:

$$L(w) = \| Xw - y \|^2$$

I noticed that sometimes its hard to find the right step size such that the loss value $L(w)$ is zero within machine precision (fit/interpolate data in this sense https://arxiv.org/abs/1712.06559). I suspect that its highly dependent on the basis/kernels I use since the gradient and hessian are:

$$\nabla L(w) = 2(X^T X w - y)$$

$$\nabla^2 L(w) = X$$

I wanted to only use 1st order methods to solve this problem so I am wondering, how do I figure out a good step size and/or basis/feature matrix $X$ given that I want to solve this problem with first order method?

If I decide to use say, Hermitian polynomials, why would that be better than other polynomials for example if I want to fit/interpolate the data perfect?

What if I used a Gaussian Kernel or Lapacian Kernel? How would $X = K$ kernel matrix change and how would Gradient Descent be affected? How does the curvature change/get affected as I change the kernel matrix? How can I set up the problem so the optimization via (S)GD fits the data perfectly?

• Maybe I'm confused by your notation, but I don't think your equations are correct. The first one should have some term involving 'w' , else the second partials wrt w will be zero, meaning that nabla squared is zero. In the end the loss function should be quadratic in the w's and gradient descent should work for most choices of a learning rate. – aginensky May 30 '18 at 2:48
• @aginensky oh yea there was a typo, ooops! – Pinocchio May 30 '18 at 16:57
• Incidentally, using the second derivative matrix allows one to use Newton – aginensky May 30 '18 at 17:22
• @aginensky yea I know I don't want to use Newton. This is an academic question of GD and least squares. – Pinocchio May 30 '18 at 21:38

I think you may be overthinking this a little bit, basis functions need not to enter into the problem and will only confuse the issue if your goal is to understand gradient descent. If your goal is understanding kernels and basis functions, I think you'll be able to find a better problem. Off the bat, your gradient is incorrect which is probably the source of the issue that has you asking this question.

Let's take it from the top. The system is consistent so that we have $y=Xw$ for some weight vector $w$. For academic interest we decide to use gradient descent to minimize the $L_2$ distance between the vectors,

$\arg\min_w(L) =\arg\min_w \frac{1}{2}\|Xw-y \|_2^2$, and $\nabla_w L= X^T(Xw-y)$.

Our gradient descent recursion is as follows:

$w_{k+1} = w_k - \eta \nabla_w L$.

For a generic function L (ie not just least squares problems), you can calculate the optimal stepsize, as described in this informative answer. At the end of the day, provided $0<\eta < \frac{2}{\gamma}$, where $\gamma$ is the Lipschitz constant of the gradient, gradient descent will converge to a stationary point at a linear rate. Of course, if the function is poorly conditioned the constant could be very small and it may appear not to converge. This is shown formally in most optimization textbooks (Boyd/Vandenberghe, Nocedal/Wright), a quick reference can be found here.

I just read the comments on the other answer. You should note further that the optimality of the result is subject to the convexity of $L$. If it is strongly convex then gradient descent will converge almost surely to the true solution, but if it is nonconvex (ie not a least squares problem) GD may not converge to a global minimum.

You're more than likely not going to be able to interpolate the data perfectly for most function if they aren't smooth and have some noise in them.

1. Typically with Hermitian polynomials, Hermitian polynomials can be utilized to decrease the effects of Gibbs phenomenon.. They sometimes have better spacing I believe.
1. I believe that both of those kernels are ill-conditioned and maybe you'd have problems.

For some reason this isn't formatting right. Some edits here. It is well known that the Gaussian Kernel is ill-conditioned. Generally, the method around this is regularization. You recommended using gradient descent. You realize that gradient descent with ill-conditioning means that the convergence rate would be slow. I think you said SGD which can sometimes help with this.

• what do you mean they would be ill-conditioned? It doesn't matter if there are many solutions, (S)GD chooses the one with minimum norm. – Pinocchio May 30 '18 at 16:58
• @Pinocchio (S)GD does no such thing ! It merely finds (approximately) points where the derivative is zero, i.e. local maxima and minima. In the case of least squares, there is a unique minma because the eqns are quadratic. In general, one has no way of knowing if the local extreme found by gradient descent are global extrema. Consider neural nets for example ! – aginensky May 30 '18 at 17:21
• I stick by my comment that properly coded gradient descent will work. – aginensky May 30 '18 at 17:24
• I don't think in general it will fit any underlying function. It has to do with whether there is noise or not in the function. The question you're asking is can you learn any type of function with a given set of orthogonal basis functions. Well, it matters what type of basis functions and how. If the function is smooth you can definitely do it. – user28896 May 30 '18 at 17:38
• @aginensky dude don't bring neural nets, thats not relevant. In the context that of this question. SGD finds minimum norm solution of course. – Pinocchio May 30 '18 at 21:40