A descida do gradiente

Descer a ladeira

A descida do gradiente repete um único movimento: dar um passo contra o gradiente, $\mathbf w_{k+1}=\mathbf w_k-\eta\,\nabla f(\mathbf w_k)$. O número $\eta>0$ é o tamanho do passo, muitas vezes chamado taxa de aprendizado. Um $\eta$ pequeno é seguro mas lento. Um $\eta$ grande passa do vale e as iterações podem se afastar mais a cada vez.

Na tigela mais simples a atualização multiplica $w$ por $1-\eta a$ a cada vez, então as iterações tendem a zero exatamente quando $|1-\eta a|<1$, isto é $\eta<2/a$. A escolha $\eta=1/a$ cai no mínimo em um passo, e qualquer $\eta$ entre $1/a$ e $2/a$ ainda converge mas alterna de sinal no caminho. Além de $2/a$ o fator passa de um em módulo e as iterações explodem.

Em várias variáveis a curvatura muda conforme a direção. O maior autovalor $L$ da hessiana limita o passo utilizável ($\eta<2/L$) e o menor $\mu$ define quão lento é atravessar a direção mais plana. A razão $\kappa=L/\mu$ é o número de condição. Com o melhor passo fixo $\eta=2/(L+\mu)$ o erro encolhe cerca do fator $(\kappa-1)/(\kappa+1)$ por passo, então um $\kappa$ grande dá um fator perto de um e um zigue-zague lento num vale longo e estreito. Para a matriz de covariância de doze grandes ações dos EUA desde 2010, $\kappa$ é cerca de $33$: o fator é $0.941$ e reduzir o erro cem vezes leva cerca de 76 passos.

• Passo seguro: $\eta<2/L$, com $L$ o maior autovalor da hessiana; senão as iterações divergem.
• Velocidade: definida pelo número de condição $\kappa=L/\mu$; quanto maior, mais lenta a descida.
• Parada: parar quando $\lVert\nabla f\rVert$ cair abaixo de uma tolerância, com um teto de iterações.

Lab: o que é avaliado

• O primeiro passo15 pts
• O segundo passo10 pts
• O maior passo estável15 pts
• Um passo grande demais15 pts
• Um número de condição15 pts
• O melhor fator de contração15 pts
• Por que o mau condicionamento é lento15 pts