1
$\begingroup$

I was playing around gradient descent topic. Wrote a function that calculates a gradient descent of a degree-2 polynomial. While trying out what is the best "step size multiplyer" (a.k.a. "learning rate") I found that value of approximatively 0.7068 works best. I cannot figure out why it's best though- I simply found it by trial and error. Is it possible determine such values without any trial and error? Is there any mathematical theory that digs deep into this topic? Or is it either manual trial end error always? Or do I have to write a gradient descent over the gradient descent function in some way (with the "learning_rate" as input and the "number of steps" as output?

Quick search yields topic of Lipschitz constant, but it does not seem to provide a result similar to that value. The code in question:

def gradient_descent(derivative_function,
                     position,
                     step_multiplier=0.7068,
                     min_step=0.0001,
                     max_steps_num=1000):
    current_step_num = 0
    while True:
        slope = derivative_function(position)
        step = step_multiplier * slope
        new_position = position - (step * step_multiplier)
        if abs(step) < min_step:
            print(f'Best result (step {current_step_num}): {new_position}')
            return new_position
        if current_step_num > max_steps_num:
            print(f'Best result (step cap {current_step_num}): {new_position}')
            return new_position
        current_step_num += 1
        position = new_position


# With step_multiplier=0.7068 an optimal value is found in just 3 steps
gradient_descent(
    derivative_function=lambda a: 2 * (a - 1),
    position=-10000,
    step_multiplier=0.7068
)  # prints: Best result (step 3): 0.9999999943355022

# With step_multiplier=0.1 an optimal value is found after 833 steps
gradient_descent(
    derivative_function=lambda a: 2 * (a - 1),
    position=-10000,
    step_multiplier=0.1
)  # prints: Best result (step 833): 0.9995185063601436
```
$\endgroup$

1 Answer 1

4
$\begingroup$

You are considering a one-dimensional parabola; in this case, it is easy. The derivative is twice the distance to the optimal point, so the optimal learning rate is always 0.5/a, where a is coef near x2.

Your code has a small bug. I'll leave it as an exercise for you to find it. Hint: your optimal number is sqrt(0.5).

In fact, in the one-dimensional case, there is always such a learning rate (lr) that you can find a solution in one step, i.e., lr = x/d, where x is a distance to an optimal point, and d is the current derivative. The problem is that it depends on the initial position for any case when the dimensionality is larger than 2.

For future study, you can look up term 'optimization'. As one example, there are nice and accessible materials from a course at Stanford: https://web.stanford.edu/group/sisl/k12/optimization/#!index.md.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you! Found the bug, it was the double step_multiplier :D. Also indeed, with 0.5a multiplier it's just one step with a perfect result, vs 9 steps and an approximate result, for example, with a 0.6a multiplier. Will read through the link, thanks again. $\endgroup$
    – Ababababa
    Feb 22 at 18:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .