0
$\begingroup$

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

enter image description here 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} $$

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

    2. Iterate

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

$\endgroup$
  • 5
    $\begingroup$ When it fails to converge, how close are you getting? How do you choose $\gamma$? $\endgroup$ – Tyler Olsen Feb 21 '18 at 14:28
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Should the updates to $\alpha, \beta$ use the same $\gamma$ ? $\endgroup$ – user1887919 Feb 22 '18 at 12:40
  • $\begingroup$ Not necessarily. Each step in your algorithm has a step size $\gamma$ and that can change. Don't make it too big, though. $\endgroup$ – Beni Bogosel Feb 22 '18 at 21:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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