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

AI Olympiads 2025 USA-NA-AIO Round 1
1

Part 13 (5 points, non-coding task)

In this part, you are asked to compute \nabla_{\mathbf{\beta}}^2 \ L \left( \mathbf{\beta} \right) and express your solutions in two forms. Reasoning is not required.

  1. Write \nabla_{\mathbf{\beta}}^2 \ L \left( \mathbf{\beta} \right) in the following summation form:

    \nabla_{\mathbf{\beta}} \ L \left( \mathbf{\beta} \right) = \sum_{n=0}^{N-1} \cdots .

  2. Denote

    \mathbf{Z} = \begin{bmatrix} z_0 & 0 & \cdots & 0 \\ 0 & z_1 & \cdots & 0 \\ \vdots & \vdots & \ddots & 0 \\ 0 & 0 & \cdots & z_{N-1} \end{bmatrix} .

    Write \nabla_{\mathbf{\beta}}^2 \ L \left( \mathbf{\beta} \right) in terms of \mathbf{X}, \mathbf{Z} with matrix operations (the summation symbol is not allowed).

2

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

We have

\begin{align*} \nabla_{\mathbf{\beta}}^2 \ L \left( \mathbf{\beta} \right) & = \boxed{ \sum_{n = 0}^{N-1} \sigma \left( \mathbf{x}^{(n), \top} \mathbf{\beta} \right) \left( 1 - \sigma \left( \mathbf{x}^{(n), \top} \mathbf{\beta} \right) \right) \mathbf{x}^{(n)} \mathbf{x}^{(n)^\top} } \\ & = \boxed{\mathbf{X}^\top \mathbf{Z} \mathbf{X} } . \end{align*}

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

3

I believe the answer to the second part should be

\mathbf{X}^{\top} \mathbf{Z} (I - \mathbf{Z}) \mathbf{X}.

(I is the identity matrix).

If not, where does the 1 - \sigma(\dots) come from?

4

You’re right; they omitted the \mathbf{(I - Z)}. If we write \mathbf{Z} as a diagonal matrix and derive from there, so the correct answer would be:

\sum_{n=0}^{N-1} \sigma\!\left(x^{(n)\top}\beta\right) \boxed{\left(1-\sigma\!\left(x^{(n)\top}\beta\right)\right)} \, x^{(n)} x^{(n)\top}

Evaluating the boxed part as well :smiling_face_with_sunglasses::

\mathbf{X}^{\top} \mathbf{Z} (I - \mathbf{Z}) \mathbf{X}.

So yeah, nice catch!