You are tuning the learning rate for fitting a line y ≈ w · x + b by gradient descent on the mean squared error. The recipe your team follows: try a list of candidate rates, throw out every rate for which the loss ever goes up, and keep the largest rate that is left.
Write pick_learning_rate(xs, ys, rates, steps). For every rate in rates, run steps steps of gradient descent from w = 0.0, b = 0.0 (each step computes both partial derivatives at the current point, then updates both parameters). The rate is unstable if some step makes the loss larger than it was before that step by more than 1e-9. Return the tuple (rate, loss) for the largest rate that is not unstable, where loss is its loss after the steps steps. Return None if every rate is unstable.
Examples
Input: xs = [1, 2, 3, 4, 5, 6], ys = [9, 11, 15, 16, 21, 24],
rates = [0.001, 0.003, 0.01, 0.03, 0.1], steps = 100
Output: (0.03, 1.0024035627496228)
Explanation: with 0.1 the first step already raises the loss; 0.03 is the largest rate
that lowers the loss at every one of the 100 steps.
Input: the same data, rates = [0.5, 0.2], steps = 50
Output: None
Constraints
1 <= len(xs) == len(ys) <= 200,1 <= len(rates) <= 20, the rates are distinct, positive and in any order0 <= steps <= 5000; with0steps every rate is stable and the loss is the loss at(0, 0)- floats are compared with a tolerance of
1e-6
Goals
- Run the same gradient descent with several learning rates
- Recognise an unstable learning rate by a loss that goes up
- Choose the largest rate whose loss keeps falling, as practitioners do