x₁−x*=(1−2aγ)(x₀−x*); γ*=1/(2a)
Условие
Минимизируется y(x)=ax²+bx+c, a>0, методом gradient descent. Какой шаг γ приводит из произвольной x₀ точно в минимум за одну итерацию? Затем обобщите на Q(x)=xᵀAx+bᵀx+c и объясните шаг Newton.
Скалярный случай
Минимум x*=−b/(2a). Производная y′=2ax+b. Один шаг:
x₁=x₀−γ(2ax₀+b).
Вычитая x*, получаем
x₁−x*=(1−2aγ)(x₀−x*).
Чтобы x₁=x* для любого старта, нужно γ=1/(2a) — ответ источника.
Векторный случай
При симметричной положительно определённой A имеем ∇Q=2Ax+b и Hessian H=2A. Для шага x₁=x₀−Γ∇Q(x₀) точное попадание в минимум обеспечивается
Γ=(2A)⁻¹=A⁻¹/2.
Почему это Newton
Newton использует x_new=x−H(x)⁻¹∇Q(x). Для квадратичной функции Hessian постоянен, поэтому локальная квадратичная аппроксимация совпадает с самой функцией и один Newton-step решает задачу точно.
Неквадратичная функция
Для общей гладкой функции Hessian меняется с x, поэтому тот же принцип применяется повторно: на каждой итерации строится локальная квадратичная модель. Один шаг уже не обязан приводить в истинный минимум.
Если A несимметрична, xᵀAx зависит только от её симметричной части (A+Aᵀ)/2; исходный ответ A⁻¹/2 подразумевает стандартную симметричную квадратичную форму.
Борис Демешев и участники · mlearn_pro, задача 116 · CC BY 4.0. γ и Γ источника сохранены; условие симметрии уточнено.