Answers.Body: <p>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 x<sup>2</sup>.</p>
  <p>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).</p>
  <p>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.</p>
  <p>For future study, you can look up term 'optimization'. As one example, there are nice and accessible materials from a course at Stanford: <a href="https://web.stanford.edu/group/sisl/k12/optimization/#!index.md" rel="nofollow noreferrer">https://web.stanford.edu/group/sisl/k12/optimization/#!index.md</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-22T18:41:04.990Z
Answers.Text: 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.
Answers.UserDisplayName: Ababababa
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-21T12:29:15.043Z
Answers.LastActivityDate: 2024-02-22T13:52:11.933Z
Answers.LastEditDate: 2024-02-22T13:52:11.933Z
Answers.UserDisplayName: Kirill Fedyanin
Body: <p>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 &quot;step size multiplyer&quot; (a.k.a. &quot;learning rate&quot;) I found that value of approximatively <code>0.7068</code> works best. I cannot figure out <strong>why</strong> 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 &quot;learning_rate&quot; as input and the &quot;number of steps&quot; as output?</p>
  <p>Quick search yields topic of Lipschitz constant, but it does not seem to provide a result similar to that value. The code in question:</p>
  <pre><code>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) &lt; min_step:
              print(f'Best result (step {current_step_num}): {new_position}')
              return new_position
          if current_step_num &gt; 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
  <span class="math-container">```</span>
  </code></pre>
  
Tags: <machine-learning><gradient-descent><learning-rate>
Title: Is there a theoretical way to determine the best learning rate for gradient descent if the function is a simple known polynomial?
UserDisplayName: Ababababa
ThreadText: # Is there a theoretical way to determine the best learning rate for gradient descent if the function is a simple known polynomial?
  
  (Asked by: username_0 on 2024-02-19)
  
  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
  ```
  
  **Tags:** machine-learning, gradient-descent, learning-rate
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-02-21. Score: 4 | Accepted answer
  
  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>.
  
  > **Comments:**
  > **username_0**: 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.  
  
  ---
  
  