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

Question

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?

Answer 1

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.

Answer 2

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.
   2. 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.