# Is it a good idea to use $\eta = \arg \max( L(y, f(x) )$ to choose the step size for stochastic gradient descent (SGD)?

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)})$$

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.
• @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. Jan 13, 2016 at 19:35
• Changed my comment to an answer with a little more detail. Jan 13, 2016 at 19:40

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.
• 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? Jan 13, 2016 at 19:49
• 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? Jan 13, 2016 at 20:12