Pourquoi on n'utilise pas tout le jeu

• ·

  $\mathcal{B}$ est de cardinal $B$, tiré uniformément sans remise dans $[\![1,N]\!]$.

• ·

  $\mathbf{g}_{n}=\mathrm{grad}_{\boldsymbol{\theta}}\,\ell\big(f_{\boldsymbol{\theta}}(\mathbf{x}^{(n)}),c^{(n)}\big)\in\mathbb{R}^{p}$ est le gradient de la perte du seul exemple $n$.

• ·

  $\boldsymbol{\theta}$ est fixé : l'aléa ne porte que sur le tirage du lot.

• ·

  Linéarité de l'espérance

• ·

  Symétrie du tirage uniforme : chaque indice a la même probabilité $B/N$ d'appartenir à $\mathcal{B}$

1. Le gradient est linéaire en la fonction qu'il dérive, et $C_{\mathcal{B}}$ est une moyenne. Donc :

2. $$\mathrm{grad}_{\boldsymbol{\theta}}\,C_{\mathcal{B}}(\boldsymbol{\theta})=\frac{1}{B}\sum_{n\in\mathcal{B}}\mathbf{g}_{n}=\frac{1}{B}\sum_{n=1}^{N}\mathbb{1}\{n\in\mathcal{B}\}\,\mathbf{g}_{n}$$

   La seconde écriture fait porter tout l'aléa sur les indicatrices, et les $\mathbf{g}_{n}$ deviennent des constantes.

3. $$\mathbb{E}\big[\mathbb{1}\{n\in\mathcal{B}\}\big]=\mathbb{P}(n\in\mathcal{B})=\frac{B}{N}\qquad\text{pour tout } n\in[\![1,N]\!]$$

   Le tirage est uniforme sans remise : les $\binom{N}{B}$ parties de cardinal $B$ sont équiprobables, et $\binom{N-1}{B-1}/\binom{N}{B}=B/N$ d'entre elles contiennent un indice donné.

4. $$\mathbb{E}\big[\mathrm{grad}_{\boldsymbol{\theta}}\,C_{\mathcal{B}}\big]=\frac{1}{B}\sum_{n=1}^{N}\frac{B}{N}\,\mathbf{g}_{n}=\frac{1}{N}\sum_{n=1}^{N}\mathbf{g}_{n}=\mathrm{grad}_{\boldsymbol{\theta}}\,C_{\mathcal{D}}(\boldsymbol{\theta})$$

   Linéarité de l'espérance, puis simplification de $B$, puis reconnaissance de la moyenne des $\mathbf{g}_{n}$.

Un lot ne donne pas le bon gradient, il en donne un autre, et la page le mesure. Mais il ne se trompe pas systématiquement : en moyenne sur les tirages, il vise juste. C'est cela qui autorise à l'employer, puisque les erreurs de direction se compensent d'un pas au suivant au lieu de s'accumuler.

• ·

  $\mathbf{g}=\mathrm{grad}_{\boldsymbol{\theta}}\,C_{\mathcal{D}}(\boldsymbol{\theta})$, et $\mathbf{g}_{\mathcal{B}}$ le gradient d'un lot de taille $B$.

• ·

  Hypothèse de travail : les $\mathbf{g}_{n}$ du lot sont tirés indépendamment, de variance finie $\sigma^{2}=\mathbb{E}\|\mathbf{g}_{n}-\mathbf{g}\|^{2}$.

• ·

  $\kappa=\sigma^{2}/\|\mathbf{g}\|^{2}$, un nombre sans dimension qui ne dépend que du point $\boldsymbol{\theta}$ et du jeu.

• ·

  La variance d'une moyenne de $B$ variables indépendantes de même variance $\sigma^{2}$ vaut $\sigma^{2}/B$

• ·

  Décomposition orthogonale : $\mathbf{g}_{\mathcal{B}}=\mathbf{g}+(\mathbf{g}_{\mathcal{B}}-\mathbf{g})$, dont le second terme est centré

1. $$\mathbb{E}\big\|\mathbf{g}_{\mathcal{B}}-\mathbf{g}\big\|^{2}=\frac{\sigma^{2}}{B}$$

   $\mathbf{g}_{\mathcal{B}}$ est la moyenne de $B$ termes indépendants d'espérance $\mathbf{g}$, par la proposition 4.

2. Écrivons $\mathbf{g}_{\mathcal{B}}=\mathbf{g}+\mathbf{r}$, où $\mathbf{r}=\mathbf{g}_{\mathcal{B}}-\mathbf{g}$ est le bruit du tirage. Par la proposition 4 il est centré, donc $\mathbb{E}\langle\mathbf{g},\mathbf{r}\rangle=\langle\mathbf{g},\mathbb{E}\mathbf{r}\rangle=0$ : en moyenne le bruit est orthogonal au signal. Il vient alors deux identités en espérance :

3. $$\mathbb{E}\langle\mathbf{g}_{\mathcal{B}},\mathbf{g}\rangle=\|\mathbf{g}\|^{2},\qquad \mathbb{E}\|\mathbf{g}_{\mathcal{B}}\|^{2}=\|\mathbf{g}\|^{2}+\mathbb{E}\|\mathbf{r}\|^{2}=\|\mathbf{g}\|^{2}+\frac{\sigma^{2}}{B}$$

   La première vient de la linéarité et de $\mathbb{E}\mathbf{r}=\mathbf{0}$ ; la seconde développe $\|\mathbf{g}+\mathbf{r}\|^{2}=\|\mathbf{g}\|^{2}+2\langle\mathbf{g},\mathbf{r}\rangle+\|\mathbf{r}\|^{2}$ et prend l'espérance, le terme croisé s'annulant.

4. $$\mathbb{E}\big[\cos^{2}(\mathbf{g}_{\mathcal{B}},\mathbf{g})\big]\ \approx\ \frac{\|\mathbf{g}\|^{2}}{\|\mathbf{g}\|^{2}+\sigma^{2}/B}=\frac{1}{1+\kappa/B}$$

   C'est ici qu'est l'approximation, et c'est la seule. $\cos^{2}$ est le quotient $\langle\mathbf{g}_{\mathcal{B}},\mathbf{g}\rangle^{2}/(\|\mathbf{g}_{\mathcal{B}}\|^{2}\|\mathbf{g}\|^{2})$, et l'on remplace l'espérance de ce quotient par le quotient des espérances calculées ci-dessus. Les deux ne sont égales que si la dispersion est petite, et la mesure de $B=1$ montrera ce qu'il advient quand elle ne l'est pas.

5. $$\frac{1}{\mathbb{E}[\cos^{2}]}-1=\frac{\kappa}{B}\qquad\Longleftrightarrow\qquad B\left(\frac{1}{\mathbb{E}[\cos^{2}]}-1\right)=\kappa$$

   Inversion de la relation précédente. Le membre de gauche porte $\mathbb{E}[\cos^{2}]$ et non $\cos^{2}$ : la table de mesure substituera le carré du cosinus moyen, et dira ce que cette substitution coûte.

Pour $B$ grand, $\cos\approx 1-\kappa/(2B)$ : l'écart au bon gradient décroît comme $1/B$, donc l'angle comme $1/\sqrt{B}$. Multiplier la taille du lot par quatre divise l'angle par deux, et c'est un rendement décroissant, puisque le passage de $8$ à $64$ gagne bien plus que celui de $512$ à $4\,096$. C'est cet arbitrage qui décide de la taille employée.