Adaptive gradient descent

Question

I want to minimize some multivariable function $\Delta(\alpha, \beta)$. I know that this function has a zero point, $\Delta(5, 5) = 0$.

Starting from some $(\alpha, \beta)$ close to $(5,5)$ (e.g. (4.8, 5.2)), I want to use a gradient descent method to recover the 'correct' values $(5,5)$.

I can plot the surface $\alpha, \beta, \Delta$ and it clearly has a minimum point, but my algorithm fails to converge

My general approach is:

1. Start with some initial $\alpha, \beta$. Compute $\Delta$

2. Calculate $\frac{\partial \Delta}{\partial \alpha}$ and $\frac{\partial \Delta}{\partial \beta}$ by evaluating e.g. $$ \frac{\partial \Delta}{\partial \alpha} = \frac{\Delta(\alpha+\epsilon, \beta)-\Delta(\alpha-\epsilon, \beta)}{2 \epsilon} $$

   3. Update $\alpha, \beta$ as $$\alpha = \alpha - \gamma \frac{\partial \Delta}{\partial \alpha} $$ and the equivalent for $\beta$

   4. Iterate

Is there any reason why this general approach should not work?

Answer 1

There are a few issues that can cause the problem:

• first, you use gradient computation using finite difference approximations. Is this necessary? Can you compute the partial derivatives of $\Delta$ analytically?

• secondly, the finite difference approximation is only valid for small $\varepsilon$. However, using too small value can cause instabilities if the function $\Delta$ is not very smooth (yours seems smooth enough). When functions are well behaved I use something like $\varepsilon = 10^{-6}$ to test against the analytic gradient.

• let's say that you manage to compute the gradient correctly. Then the choice of the step $\gamma$ is also important. There are different ways of choosing the descent step size, but if you want to keep it simple, then do something like the following:

1. Choose a starting value for $\gamma$ which is not very large, like $\gamma=0.001$ or $\gamma=0.01$.

2. At each iteration, if you manage to decrease the value of the function, increase $\gamma$ using a rule like $\gamma \gets \min (\gamma_{max},1.1\gamma)$ (where $\gamma_{max}$ is an upper limit for the step size, like $\gamma_{max} = 1$ or smaller). If the value of the function does not decrease, then change $\gamma$ by doing something like $\gamma \gets 0.9\gamma$.

3. When $\gamma$ is too small or the decrease in the value of the function is too small, you stop.

For a convex and smooth function, these three should be enough to get you close to the minimum. For more complex examples, using an existing optimized approach like quasi-newton or lbfgs can give very good results.