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?