0
$\begingroup$

This scenario is mostly academic or of conceptual interest. It might not make much sense in real life.

Consider the case when we are trying to learn a regression function via gradient descent. Say we are doing this by minimizing the training error:

$$ H[f] = \sum^N_{n=1} (y_n - f(x_n))^2$$

(or if you want the regularized version of it $ \lambda \| f\|^2_2$).

Consider the case where we only have a single training example $(x,y)$.

If updated the coefficient parameters $\theta$ of $f$ via gradient descent:

$$ \theta := \theta - \gamma \frac{\partial H[f] }{\partial \theta_i}$$

then how many iterations would it take to converge to a minimum? How long would it take for $\frac{\partial H[f] }{\partial \theta_i}$ to be zero and stop updating the parameters?

The reason I am asking this is because conceptually, say that I asked the same question but for the perceptron algorithm. The perceptron algorithm would start pointing towards the labeled point immediately, hence, it would converge in 1 step. However, it seems less obvious how to reason about this in the case of regression and gradient descent. What are people's thoughts? Would it ever be the case the the gradient is zero after some number of iterations?

Would this question have different answers if we use regularized least squares or only least squares?

What I think is that because we dont have many "conflicting" points of view of what the output of f should be, it would probably converge in very few iterations with only one example.


I know generalization might not be good but I am just trying to understand gradient descent from a conceptual stand point rather than actually use this to predict stuff.

$\endgroup$
0
$\begingroup$

I think this would depend on the learning rate. It is a function of the initial error and the learning rate. With a constant learning rate you run the risk of overshooting the minimum error and going back and forth and never converging.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.