# Gradient Descent on Paper: Official Solution

*English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email sota.ai.community@gmail.com.*

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

*The official solutions file repeats each statement before its solution; the statement is in the task statement file. The marking criteria below come from the “Marking criteria for the first tour” pages at the end of the same file.*

## Solution

Let us study a single step of the algorithm. An *attempt* is made to change the value of one of the coordinates by some amount $lr$. This change happens if and only if the absolute value of the corresponding coordinate decreases, since

$$f(x + lr, y) < f(x, y) \iff |x + lr| < |x|,$$

$$f(x, y + lr) < f(x, y) \iff |y + lr| < |y|.$$

### Part (a)

Along the $x$ coordinate the algorithm makes the change attempts $+1, -1, +1, -1, \ldots$; along the $y$ coordinate, conversely, $-1, +1, -1, +1, \ldots$.

Consider two consecutive attempts to change the $x$ coordinate.

- If $|x| > \frac{1}{2}$, then exactly one of the two attempts leads to a change of the coordinate, and $|x|$ decreases by exactly 1.
- If $|x| \leq \frac{1}{2}$, then neither attempt leads to a change of the coordinate.

Thus, after a finite number of such pairs of algorithm steps, the inequality $|x| \leq \frac{1}{2}$ will hold, since $|x|$ cannot decrease by 1 infinitely many times.

The same is true for the $y$ coordinate; hence, for some index $N$ the inequalities

$$|X_N| \leq \frac{1}{2}, \qquad |Y_N| \leq \frac{1}{2}$$

will hold.

Then the distance to the origin at that moment will also be less than 1:

$$X_N^2 + Y_N^2 \leq \frac{1}{4} + \frac{1}{4} = \frac{1}{2} < 1.$$

By what was said above, this inequality will also hold for every index $M \geq N$; we will need this observation to solve the other part.

### Part (b)

Let us divide the steps of the algorithm into blocks of consecutive steps with the same value of $lr$. Consider the $m$-th block, consisting of the steps with indices $i = 2^m + 1, \ldots, 2^{m+1}$, where $lr = \frac{1}{2^m}$. From now on we study the blocks with $m \geq 3$.

Then, as in part a), within each block every second attempt to change the $x$ coordinate decreases the value of $|x|$ as long as the inequality $|x| > \frac{lr}{2} = \frac{1}{2^{m+1}}$ holds.

Hence, for the $m$-th block of steps at least one of the following statements holds.

1. After all steps of the $m$-th block have been performed, $|x| \leq \dfrac{lr}{2}$.
2. As a result of every fourth step of the algorithm (that is, of every second attempt to change the $x$ coordinate), the quantity $|x|$ decreased by $lr$. Thus, over this block of steps it decreased in total by $2^{m-2} \cdot lr = \frac{1}{4}$.

Note that case 2 could occur only for a finite number of blocks, since $|x|$ cannot decrease by $\frac{1}{4}$ infinitely many times.

Consequently, there exists a number $M_x$ such that, for the blocks with indices greater than $M_x$, the first statement holds.

Altogether, for $N > N_x = \max(2^{M_x+1}, 10)$ the inequalities

$$|X_N| \leq \frac{1}{2^{N_x+1}} \leq \frac{1}{2^{11}} < \frac{1}{2000}$$

will hold.

Similarly, for the $y$ coordinate there also exists an index $N_y$ such that, for $N > N_y$, the inequality $|Y_N| < \dfrac{1}{2000}$ holds.

Then, for $N > \max(N_x, N_y)$, the inequalities $|X_N| < \dfrac{1}{2000}$ and $|Y_N| < \dfrac{1}{2000}$ hold. Hence,

$$\sqrt{|X_N|^2 + |Y_N|^2} \leq \sqrt{|X_N|^2 + 2 \cdot |X_N||Y_N| + |Y|^2} = |X_N| + |Y_N| < \frac{1}{2000} + \frac{1}{2000} = \frac{1}{1000}.$$

Thus, the index $N_0 = \max(N_x, N_y)$ satisfies the conditions of the problem.

**Remark.** It follows from the solution above that the sequence of points $(X_i, Y_i)$ converges to the minimum point of the function $f(x, y)$, the origin.

## Marking criteria

General part.

C1 (5 points) The alternation of the descent directions with period 4 is stated.

C2 (5 points) The decrease of $|X|$ and $|Y|$ is established.

Part (a).

A. A correct proof of part (a): 20 points.

MA. The stopping region is given incorrectly, or the existence of such a region is used without proof: 10 points are deducted.

Part (b).

B. A correct proof of part (b): 20 points.

B1. The block structure is introduced, with the relation between the block sizes and the common value of $lr$ indicated: 5 points.

B2. It is proved that the contribution of each block to the change of the parameters $|X|$ and $|Y|$ is at least some constant if all steps of this block led to a change of the corresponding coordinates.

MB. Errors in the presentation of the remaining part of the proof: at least 5 points are deducted.

- The progress items and penalties for the three listed parts of the problem are added up.