2025 USA-NA-AIO Round 1, Problem 3, Part 15

AI Olympiads 2025 USA-NA-AIO Round 1
1

Problem 15 (5 points, non-coding task)

To learn \mathbf{\beta}, we do whole-batch iteration with the gradient descent algorithm and the Netwon’s method.

In this part, denote by \eta > 0 the learning rate.

Do the following tasks in this part (reasoning is not required).

  1. Write down the gradient descent algorithm in the following form:

    \mathbf{\beta} \leftarrow \mathbf{\beta} - \eta \cdot \boxed{???} .

  2. Write down the Newton’s method in the following form:

    \mathbf{\beta} \leftarrow \mathbf{\beta} - \eta \cdot \boxed{???} .
2

\color{green}{\text{### WRITE YOUR SOLUTION HERE ###}}

\mathbf{\beta} \leftarrow \mathbf{\beta} - \eta \cdot \boxed{\nabla_{\mathbf{\beta}} \ L \left( \mathbf{\beta} \right)} .
\mathbf{\beta} \leftarrow \mathbf{\beta} - \eta \cdot \boxed{\left( \nabla_{\mathbf{\beta}}^2 \ L \left( \mathbf{\beta} \right) \right)^{-1} \left( \nabla_{\mathbf{\beta}} \ L \left( \mathbf{\beta} \right) \right)} .

\color{red}{\text{""" END OF THIS PART """}}