Gradient Descent on Paper

Gradient Descent on Paper

English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email [email protected].

All-Russian School Olympiad in Informatics 2025–2026, Final Stage
“Artificial Intelligence” profile, Tour 1, Moscow, 23 March 2026
Task C

Consider the function $f(x, y) = x^{20} + y^{26}$. Below is an algorithm that, given a starting point $(a, b)$, constructs a sequence of points $(X_i, Y_i)$, $i = 0, 1, 2, \ldots$

In the code below, decrease_lr = False for part (a), and decrease_lr = True for part (b).

X_0, Y_0 ← a, b
dx, dy ← 0, 1
lr ← 1
for i = 1, 2, 3, ... do
    dx, dy ← dy, -dx
    if decrease_lr and i · lr ⩾ 2 then:
        lr ← lr / 2
    end if
    X_i, Y_i ← X_{i-1}, Y_{i-1}
    if f(X_i + dx · lr, Y_i + dy · lr) < f(X_i, Y_i) then
        X_i ← X_i + dx · lr
        Y_i ← Y_i + dy · lr
    end if
end for

Prove that, whatever the starting point, the following statements hold.

(a) There exists an index $N$ such that the distance from the point $(X_N, Y_N)$ to the origin does not exceed 1.

(b) There exists an index $N_0$ such that, for every index $N \geq N_0$, the distance from the point $(X_N, Y_N)$ to the origin does not exceed $\frac{1}{1000}$.