Descida do gradiente estocástica e minilotes

Estimar o gradiente com poucas amostras

A maioria dos problemas de ajuste minimiza uma média sobre dados, $f(\mathbf w)=\frac1n\sum_{i=1}^{n}\ell_i(\mathbf w)$, por exemplo erros quadráticos sobre $n$ observações. O gradiente exato precisa dos $n$ termos a cada passo, o que é lento demais quando $n$ são milhões de ticks. A descida do gradiente estocástica sorteia um minilote aleatório $B$ de $b$ observações e usa no lugar o gradiente médio $g_B$. Essa estimativa é não viesada: na média ela é igual ao gradiente verdadeiro.

O preço do atalho é o ruído. A variância do gradiente do lote cai como $1/b$, então reduzir à metade seu desvio padrão exige um lote quatro vezes maior, um retorno muito decrescente. Uma época é uma passagem completa pelos dados e contém $n/b$ atualizações. Com passo constante as iterações nunca se acomodam: continuam tremendo numa pequena bola em torno do mínimo, porque mesmo no mínimo o gradiente do lote não é zero. A solução é um passo que encolhe. As condições clássicas de Robbins-Monro pedem $\sum_t\eta_t=\infty$, para poder ir tão longe quanto preciso, e $\sum_t\eta_t^{2}<\infty$, para o ruído se apagar. O cronograma $\eta_t=\eta_0/t$ cumpre as duas.

• Não viesado: o gradiente de um lote aleatório é, na média, o gradiente completo.
• Ruidoso: variância $\sigma^2/b$; um lote quatro vezes maior reduz o desvio padrão à metade.
• Passos decrescentes: $\sum\eta_t=\infty$ e $\sum\eta_t^2<\infty$, p. ex. $\eta_t=\eta_0/t$, dão convergência.

Lab: o que é avaliado

• O gradiente completo15 pts
• O ruído de uma amostra15 pts
• O ruído de um lote15 pts
• Atualizações por época15 pts
• Um cronograma de passos que converge15 pts
• O laço de minilotes10 pts
• Por que um passo constante não se acomoda15 pts