Самый длинный безопасный шаг
Перед долгим обучением модели хочется знать, какой шаг градиентного спуска можно себе позволить. Слишком маленький — обучение растянется на недели, слишком большой — спуск разлетится. Для функций двух переменных вида
$$f(u, v) = a u^2 + 2b\,uv + c v^2 + d u + e v$$ответ можно найти заранее. Спуск с постоянным шагом η делает шаги (u, v) ← (u, v) − η·∇f(u, v). Найдите такое число η*, что при любом шаге 0 < η < η* спуск из любой начальной точки сходится к точке минимума f, а при η > η* — уже нет. Если у функции нет единственной точки минимума, такого шага нет вовсе.
Именно такой вид имеет сумма квадратов промахов прямой y ≈ u·x + v, подогнанной к точкам: a = Σx², b = Σx, c = n, d = −2Σxy, e = −2Σy. Несколько тестов — суммы для среднегодовых температур Алматы 1941–2025 годов: с годами как есть и с годами, отсчитанными от середины ряда.
Вход
В первой строке число функций t (1 ≤ t ≤ 100 000). В каждой из следующих t строк пять целых чисел a, b, c, d, e (|a|, |b|, |c| ≤ 10⁹, |d|, |e| ≤ 10¹²).
Выход
Для каждой функции — строку с числом η* или словом never, если единственной точки минимума нет. Число засчитывается, если его относительная погрешность не больше 10⁻⁶.
Примеры
Пример 1
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
1.0 0.1 0.1111111111111111 never never never never
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Для оврага вдоль осей, когда b = 0, ответ известен: шаг должен быть меньше 2 / (наибольшая кривизна), а кривизны — вторые производные 2a и 2c. Что меняет слагаемое 2b·uv? Нарисуйте линии уровня u² + uv + v²: куда смотрят оси эллипсов?
2Подсказка 2
Запишите шаг спуска для ошибки — разности между текущей точкой и точкой минимума. Градиент квадратичной функции линеен: ∇f = H·(точка) + (d, e), где H = 2·[[a, b], [b, c]]. Во что превращается ошибка за один шаг?
3Идея
Если точка минимума z* существует, то ∇f(z) = H(z − z*), и ошибка e = z − z* за шаг умножается на матрицу I − ηH. В базисе из собственных векторов H это просто овраг вдоль осей: по каждому собственному направлению ошибка умножается на 1 − ηλ, где λ — собственное число. Сходимость из любого старта требует |1 − ηλ| < 1 для обоих λ, то есть 0 < ηλ < 2. Значит, оба собственных числа положительны и η < 2/λmax. Линейные члены d, e только сдвигают минимум и на ответ не влияют.
Если же одно из собственных чисел не больше нуля, по его направлению ошибка не убывает при любом шаге: единственной точки минимума нет, и ответ — never.
4Разбор
Положительность обоих собственных чисел симметричной матрицы 2 × 2 — то же, что a > 0 и ac − b² > 0 (критерий Сильвестра). Проверяем это в целых числах: ac и b² до 10¹⁸ помещаются в int64. В числах с плавающей точкой проверять нельзя: четвёртый тест построен на тождестве Кассини для чисел Фибоначчи, Fk+1Fk−1 − Fk² = (−1)k, и разность в нём равна ±1 при слагаемых порядка 10¹⁷ — в float64 она теряется.
Наибольшее собственное число [[a, b], [b, c]] — больший корень характеристического уравнения: (a + c)/2 + √(((a − c)/2)² + b²). У H оно вдвое больше, так что η* = 2/λmax(H) = 1 / ((a + c)/2 + √(((a − c)/2)² + b²)).
Тест с Алматы показывает, зачем перед спуском сдвигают данные. Если в столбце стоят сами годы, η* ≈ 3·10⁻⁹, если годы от 1941-го — около 5·10⁻⁶, если от середины ряда — около 2·10⁻⁵. Ещё сильнее меняется отношение кривизн κ = λmax/λmin, а от него зависит число шагов: примерно 2,6·10¹⁰, 9300 и 602. Столбец лет около 2000 почти параллелен столбцу единиц, и овраг выходит невероятно узким; после вычитания среднего столбцы перпендикулярны, а овраг лежит вдоль осей.
4+Решение
5Сложность
O(1) на функцию, O(t) всего.
6Типичные ошибки
- 1 / max(a, c). Это ответ для оврага вдоль осей. При b ≠ 0 овраг повёрнут, и самое крутое направление круче любой из осей: у функции 5u² + 8uv + 5v² вторые производные по осям равны 10, а по диагонали — 18.
- Потерянная двойка. Производная au² — это 2au, поэтому матрица Гессе — удвоенная [[a, b], [b, c]].
- Проверка выпуклости по a > 0 и c > 0. Функция u² + 4uv + v² положительна по обеим осям, но по диагонали u = −v уходит вниз: это седло.
- Определитель в числах с плавающей точкой. Ломается на четвёртом тесте.