Problem 487838 · hard · Level 04 Non-Linear Data Structures

Where Gradient Descent Tips Over

learning rate · curvature · convexity · quadratic loss · condition number · feature scaling

In the lesson, gradient descent on the six deliveries converged with learning rate 0.06 and exploded with 0.065. You want to predict that boundary exactly instead of finding it by trial.

Fit a line y ≈ w·x + b by gradient descent on the mean squared error L(w, b) = mean((w·x + b - y)²), where every step computes the whole gradient and then updates both parameters with learning rate lr. For a direction (p, q) with p² + q² = 1, the curvature of the loss in that direction is the second derivative of t ↦ L(w + t·p, b + t·q). For this loss it does not depend on (w, b) or on the targets y. Let k_max and k_min be the largest and the smallest curvature over all directions.

Write rate_limits(xs) that returns a tuple of two floats:

  1. the critical learning rate: the number r such that, whatever the targets y and the starting point, gradient descent converges for every lr < r, while for every lr > r it diverges for some targets and starting points;
  2. the condition number k_max / k_min, which measures how long and narrow the valley of the loss is.

Examples

Input:  xs = [1, 2, 3, 4, 5, 6]
Output: (0.06256180030942513, 87.59810803785476)
Explanation: the lesson's learning rates 0.06 and 0.065 lie on either side of 0.0626. The valley is
about 88 times more sharply curved across than along, which is why convergence took hundreds of steps.

Input:  xs = [-1.5, -0.5, 0.5, 1.5]
Output: (0.8, 1.25)

Constraints

  • 2 <= len(xs) <= 10**4, and xs contains at least two different values
  • the results depend only on xs
  • floats are compared with a tolerance of 1e-6 (relative for large numbers)

Goals

  • Explain why the largest usable learning rate depends only on the shape of the loss bowl
  • Compute the steepest and gentlest curvature of the squared-error loss of a line
  • Predict, without running it, where gradient descent starts to diverge and how elongated the bowl is
Starting Python…