CS
Problems Base course RU

Problem

The longest safe step

optimization gradient linear algebra

Before training a model for a long time, one wants to know what gradient descent step one can afford. Too small, and training drags on for weeks; too large, and the descent blows up. For functions of two variables of the form

$$f(u, v) = a u^2 + 2b\,uv + c v^2 + d u + e v$$

the answer can be found in advance. Descent with a constant step η makes the steps (u, v) ← (u, v) − η·∇f(u, v). Find the number η* such that for any step 0 < η < η* the descent from any starting point converges to the minimum point of f, and for η > η* it no longer does. If the function has no single minimum point, there is no such step at all.

The sum of squared misses of a line y ≈ u·x + v fitted to points has exactly this form: a = Σx², b = Σx, c = n, d = −2Σxy, e = −2Σy. Several tests are the sums for the mean annual temperatures of Almaty in 1941–2025: with the years as they are and with the years counted from the middle of the series.

Input

The first line holds the number of functions t (1 ≤ t ≤ 100,000). Each of the following t lines holds five integers a, b, c, d, e (|a|, |b|, |c| ≤ 10⁹, |d|, |e| ≤ 10¹²).

Output

For each function, a line with the number η* or the word never if there is no single minimum point. A number is accepted if its relative error is at most 10⁻⁶.

Examples

Example 1

Input
7
1 0 1 0 0
1 0 10 -4 6
5 4 5 0 0
1 1 1 2 2
1 2 1 0 0
-1 0 -1 0 0
0 0 1 3 0
Output
1.0
0.1
0.1111111111111111
never
never
never
never

Limits

Time · Python
4000 ms
Time · Go
1000 ms
Memory
256 MB
Judging
6 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

For a ravine along the axes, when b = 0, the answer is known: the step must be less than 2 / (the largest curvature), and the curvatures are the second derivatives 2a and 2c. What does the term 2b·uv change? Draw the level lines of u² + uv + v²: where do the axes of the ellipses point?

2Hint 2

Write the descent step for the error, the difference between the current point and the minimum point. The gradient of a quadratic function is linear: ∇f = H·(point) + (d, e), where H = 2·[[a, b], [b, c]]. What does the error turn into after one step?

3The idea

If the minimum point z* exists, then ∇f(z) = H(z − z*), and the error e = z − z* is multiplied by the matrix I − ηH at each step. In the basis of eigenvectors of H this is just a ravine along the axes: along each eigendirection the error is multiplied by 1 − ηλ, where λ is the eigenvalue. Convergence from any start requires |1 − ηλ| < 1 for both λ, that is, 0 < ηλ < 2. So both eigenvalues are positive and η < 2/λmax. The linear terms d, e only shift the minimum and do not affect the answer.

If one of the eigenvalues is not greater than zero, the error along its direction does not decrease for any step: there is no single minimum point, and the answer is never.

4Walkthrough

Both eigenvalues of a symmetric 2 × 2 matrix being positive is the same as a > 0 and ac − b² > 0 (Sylvester’s criterion). Check this in integers: ac and b² up to 10¹⁸ fit in int64. It cannot be checked in floating point: the fourth test is built on Cassini’s identity for Fibonacci numbers, Fk+1Fk−1 − Fk² = (−1)k, and the difference in it is ±1 with terms of order 10¹⁷; in float64 it is lost.

The largest eigenvalue of [[a, b], [b, c]] is the larger root of the characteristic equation: (a + c)/2 + √(((a − c)/2)² + b²). For H it is twice as large, so η* = 2/λmax(H) = 1 / ((a + c)/2 + √(((a − c)/2)² + b²)).

The Almaty test shows why data are shifted before descent. If the column holds the years themselves, η* ≈ 3·10⁻⁹; if the years are counted from 1941, about 5·10⁻⁶; if from the middle of the series, about 2·10⁻⁵. The ratio of curvatures κ = λmax/λmin, on which the number of steps depends, changes even more: about 2.6·10¹⁰, 9300 and 602. A column of years around 2000 is almost parallel to the column of ones, and the ravine comes out incredibly narrow; after subtracting the mean the columns are perpendicular, and the ravine lies along the axes.

4+Solution
5Complexity

O(1) per function, O(t) in all.

6Common mistakes
  • 1 / max(a, c). This is the answer for a ravine along the axes. With b ≠ 0 the ravine is rotated, and the steepest direction is steeper than either axis: the function 5u² + 8uv + 5v² has second derivatives of 10 along the axes and 18 along the diagonal.
  • A lost factor of two. The derivative of au² is 2au, so the Hessian is twice [[a, b], [b, c]].
  • Checking convexity by a > 0 and c > 0. The function u² + 4uv + v² is positive along both axes but goes down along the diagonal u = −v: it is a saddle.
  • The determinant in floating point. Breaks on the fourth test.

Algorithms behind it

NUM~ Algorithm Gradient descent Finds the minimum of a function by steps against the gradient, in the direction of steepest descent. O(κ · log(1/ε)) steps 2 problems ML Algorithm Linear regression Picks a model’s coefficients so that the sum of squared misses over the data is smallest. O(n·d² + d³) 2 problems
The algorithms catalogue