On Elo++ updating rule

I am not sure if this is the correct place to ask this kind of question, I hope it is. I am studying this paper on an improvement of Elo rating system called Elo++. On page 4 the author states that he want minimize a function called total loss that is

$$L=\sum_{i,j\in T}w_{i j}\left( \hat o_{i j}-o_{i j}\right)^2+\lambda\sum_{i\in D}\left(r_i-a_i\right)^2$$

where $$r_i$$ is the rank of the player that as to be estimated, $$\hat o_{i j}$$ is the outcome of a game where player $$r_i$$ plays against player $$r_j$$, $$a_i$$ is the arithmetic average of the set $$D$$ of the player $$r_j$$ (the players $$r_j$$ which have played against $$r_i$$), $$o_{i j}$$ is the predicted outcome that is a function of $$r_i, r_j$$.

The problem for me comes at page 5 where the author says that in order to minimize the total loss, he had used a stochastic gradient descent. The updating formula in the stochastic gradient descent is

$$r_i \leftarrow r_i-\eta\left(w_{i j}\left(\hat o_{i j}-o_{i j}\right)\hat o_{i j}\left(1-\hat o_{i j}\right)+\frac{\lambda}{N_i} \left(r_i-a_i\right)\right)$$

How is this updating formula is related to the problem of minimizing the first condition?

• Are you asking why that formula comes from the gradient of the loss function $L$? The coordinates of the gradient when you just consider the $j$th opponents are proportional to $\bigg( \cdots \bigg)$ because of the formula for $o_{ij}$ and the chain rule. Sep 2 '12 at 9:06
• If you put this comment in a form of answer i will give you a +1 :) Sep 2 '12 at 9:54

There is some disagreement between your notation and the notation in the paper. You disagree on whether $\hat o$ or $o$ is the predicted outcome or the observed outcome. I'll use the paper's notation.

In one step of the stochastic gradient descent, you compute a noisy estimate of the gradient of the loss function as the gradient of the loss attributed to one example,

$$L = w_{ij} (\hat o_{ij} - o_{ij})^2 + \frac \lambda N_i (r_i - a_i)^2.$$

We want the partial derivative of this with respect to $r_i.$ By the chain rule,

$$\frac {\partial L}{\partial r_i} = 2 w_{ij}(\hat o_{ij} - o_{ij})( \frac{\partial}{\partial r_i} \hat o_{ij}) + 2 \frac \lambda N_i (r_i - a_i).$$

Here $\hat o_{ij}$ is a logistic function $\hat o_{ij} = P(-r_j+r_i+\gamma) = 1/(1 + \exp(r_j - r_i- \gamma))$. The logistic function $P(x)$ has the property that $P'(x) = P(x)(1-P(x)),$ which is easily checked by the chain rule. So,

$$\frac {\partial}{\partial r_i} \hat o_{ij} = \hat o_{ij}(1- \hat o_{ij})$$

$$\frac {\partial L}{\partial r_i} = 2 w_{ij}(\hat o_{ij} - o_{ij})( \hat o_{ij}(1- \hat o_{ij})) + 2 \frac \lambda N_i (r_i - a_i).$$

The factor of $2$ is absorbed into $\eta$ to give the update rule for $r_i$. For $r_j$, there is an extra factor of $-1$ from the chain rule applied to $P(-r_j+r_i+\gamma),$ so

$$\frac {\partial}{\partial r_j} \hat o_{ij} = -\hat o_{ij}(1- \hat o_{ij}).$$