2
$\begingroup$

I wanted to have a good (as optimal as possible) automatic way of choosing the step size for minimizing the generalization error $\mathbb{E}_{ (x,y) \sim p_{x,y} }[L(y, f(x))]$, where $L$ is the loss function. For this I was using stochastic gradient descent were I updated the parameters of my model according to:

$$ \theta^{(t+1)} = \theta^{(t)} - \eta_{\theta} \nabla_{\theta}L(y,f_{\theta}(x))$$

however, I wanted to use a good way to choose the step size $\eta_{\theta}$. For this I came across the following method to choose a step size when $g$ is the objective function we want to minimize

$$ \eta_{\theta} = \arg \max_{\eta \in \mathbb{R}}\{ g(\theta^{(t+1)} ) \}$$ where $$\theta^{(t+1)} = \theta^{(t)} - \eta \nabla_{\theta}g(\theta^{(t)}) $$

this method is usually is considered "optimal" (in optimization) because it minimizes $g$ as best as it can given the constraint that we only know the current parameters value $\theta^{(t)}$ and the gradient $\nabla_{\theta}g(\theta^{(t)})$ (since it chooses a step size such that $g$ decreases as much as possible with the current information).

If $g$ is actually Empirical Risk Minimization (ERM), then one knows that $g$ is a sum of loss functions $g(\theta) = \frac{1}{N} \sum^{N}_{n=1} L(y_n, f_{\theta}(x_n))$. So intuitively, I thought, that maybe we could take the steepest descent with respect to each of these loss functions and choose the step size similarly:

$$ \eta_{\theta} = \arg \max_{\eta \in \mathbb{R}}\{ L(y, f_{ \theta^{(t+1)} }(x) ) \}$$ where $$\theta^{(t+1)} = \theta^{(t)} - \eta \nabla_{\theta}g(\theta^{(t)}) $$

as I was thinking about this. My main questions are:

  1. is this a good method to optimize a machine learning model if the goal is to generalize?
  2. Would this method converge to a some local optimum in the Empirical Risk Minimization (ERM)?
  3. Why is this method to choose the step size rarely discussed in the Machine Learning literature if it seems to be the method of choice (for choosing step sizes) optimization?
  4. Having computational issue aside, is if we can compute such a step size (or an some approximation, cheaply), is it ever a good idea to use this step size when only considering one data point as in stochastic gradient descent?

My current hunch answers to these questions are:

  1. It might not be a bad method to use, but since it choose to decrease as much as possible with respect to one data sample and one less, it could be prone to take extreme steps with respect to a single example.
  2. I would suspect that it would since we are minimizing a single term of the summation of losses.
  3. I don't really know why this is not the method of choice in Machine Learning, but I guess it doesn't generalize well? There doesn't seem to be any literature about it. I am aware that sometimes finding a closed form solution of this can be tricky, however, it seems that line search can be easily and cheaply used to find an approximation. So I find it rather strange that there is no literature (I could find) about this. Maybe I just didn't look hard enough.
  4. As I mentioned early, I would be scared that we would take too aggressive steps with respect to single data point and possibly not generalize.
$\endgroup$
  • $\begingroup$ @Dougal not sure if I understood your last point: "You'll have to compute several, possibly many, function evaluations to find the best one. If function evaluations are comparably priced to the gradient, you might have been better off just taking a reasonable step size and repeating." The goal is to use a good step size that is automatic. $\endgroup$ – Charlie Parker Jan 13 '16 at 19:35
  • 1
    $\begingroup$ Changed my comment to an answer with a little more detail. $\endgroup$ – Dougal Jan 13 '16 at 19:40
2
$\begingroup$

If you do this with actually one data point as written here, I imagine that it'll be far too likely to take crazily large steps. If you do it with a decently-sized minibatch instead, it might be okay in that respect; but you might need a fairly large minibatch. One of the reasons SGD works is that when you take a "bad" step due to a poor minibatch, it doesn't matter too much, whereas here any step can end up being enormous.

Another problem is: optimizing over the step size isn't free! You'll have to compute $L(y, f_{\theta - \eta \nabla_\theta g(\theta)}(x))$ several, possibly many, times in order to find the best value of $\eta$ before choosing a new $\theta$. If evaluating $f$ takes a similar amount of time as evaluating $\nabla_\theta g$, you might have been better off just taking any non-terrible step size and repeating.

$\endgroup$
  • $\begingroup$ Sure, its a good point, that computing $\eta$ isn't free, which is obvious. I guess I forgot to write it in my question details, but I guess I was mostly interested to think even if one could compute such a step size (or an approximation), would it ever be a good idea to use such a step size $ \eta_{\theta} = \arg \max_{\eta \in \mathbb{R}}\{ L(y, f_{ \theta^{(t+1)} }(x) ) \}$ when we minimize only with respect to 1 data point? $\endgroup$ – Charlie Parker Jan 13 '16 at 19:49
  • 1
    $\begingroup$ @CharlieParker That's an interesting question that probably needs some investigation, theoretical and/or empirical. I'd be real worried about it with just one data point, but it might possibly make sense if you ignore the computational issues. $\endgroup$ – Dougal Jan 13 '16 at 19:50
  • $\begingroup$ Lets assume for the sake of argument that $f$ and $\nabla_{\theta}L$ take comparable times. Then what is a non-terrible way to choose a step size that you mention at the end of your answer? $\endgroup$ – Charlie Parker Jan 13 '16 at 20:12
  • 1
    $\begingroup$ @CharlieParker I meant by that any typical step size schedule, which are usually either hand-designed by trial and error or picked by a hyperparameter optimization procedure "outside the loop" (which is itself pretty expensive, so this might be better in some situtaions). You might also be interested in adaptive step size methods, e.g. AdaGrad, vSGD, SAGA, Adam, or others. $\endgroup$ – Dougal Jan 13 '16 at 20:46

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.