Otimização Estocástica

O que “otimização estocástica (stochastic optimization)” significa no aprendizado de máquina (machine learning)

No aprendizado de máquina, o treinamento (training) normalmente significa minimizar uma função objetivo (objective) (perda (loss)) em relação aos parâmetros do modelo (\theta). Para aprendizado supervisionado (supervised learning), uma função objetivo comum é a minimização do risco empírico (empirical risk minimization):

[ \min_\theta ; F(\theta) ;=; \frac{1}{N}\sum_{i=1}^N \ell(\theta; x_i, y_i) ]

Aqui, (\ell(\theta; x_i, y_i)) é a perda no exemplo (i), e (N) é o tamanho do conjunto de dados (dataset).

Otimização estocástica se refere a uma família de métodos que otimizam (F(\theta)) usando estimativas ruidosas (noisy estimates) da verdadeira função objetivo e/ou do seu gradiente (gradient). O exemplo principal é a descida do gradiente estocástica (stochastic gradient descent, SGD), que substitui o gradiente completo (caro em conjuntos de dados grandes) por um gradiente calculado em um minilote (mini-batch) amostrado aleatoriamente.

Essa é uma ideia central no aprendizado profundo (deep learning) moderno porque calcular o gradiente exato em bilhões de exemplos muitas vezes é impossível e porque o ruído introduzido pela estocasticidade muda a dinâmica do treinamento de maneiras úteis.

Se você é novo em treinamento baseado em gradientes (gradient-based training), ajuda ler isto junto com Descida do Gradiente e (para a mecânica da retropropagação) Retropropagação.

Determinística vs. estocástica: a intuição central

Descida do gradiente em lote completo (full-batch gradient descent) (determinística)

Na descida do gradiente em lote completo, cada atualização usa o gradiente sobre todo o conjunto de dados:

[ \theta_{t+1} = \theta_t - \eta \nabla F(\theta_t) ]

  • Prós: Atualizações estáveis; a perda normalmente diminui de forma suave.
  • Contras: Cada passo é caro; pode ser lento para progredir por unidade de computação.

SGD (estocástica)

A SGD aproxima (\nabla F(\theta)) usando um minilote (B_t) de tamanho do lote (batch size) (m):

[ g_t ;=; \frac{1}{m}\sum_{i \in B_t} \nabla_\theta \ell(\theta_t; x_i, y_i) ] [ \theta_{t+1} = \theta_t - \eta g_t ]

  • Prós: Passos baratos; escala para conjuntos de dados grandes; muitas vezes chega a boas soluções mais rápido em tempo de relógio (wall-clock time).
  • Contras: Atualizações são ruidosas; curvas de perda oscilam; o ajuste do tamanho do passo (step size) fica mais delicado.

Uma propriedade importante (sob amostragem aleatória padrão) é que o gradiente de minilote geralmente é não enviesado (unbiased):

[ \mathbb{E}[g_t \mid \theta_t] = \nabla F(\theta_t) ]

Assim, a SGD está “correta em média”, mas cada passo individual é perturbado por ruído.

SGD como “sinal + ruído”

Um modelo mental útil:

[ g_t ;=; \nabla F(\theta_t) ;+; \xi_t ]

  • (\nabla F(\theta_t)) é o sinal (o verdadeiro gradiente completo).
  • (\xi_t) é ruído devido à amostragem de um minilote.

De onde vem o ruído

  1. Ruído de amostragem de minilotes
    • Minilotes diferentes contêm exemplos diferentes, produzindo gradientes diferentes.
  2. Ruído nos dados / ruído nos rótulos (labels)
    • Se os rótulos são ruidosos ou a tarefa é inerentemente incerta, os gradientes variam mais.
  3. Aleatoriedade do aumento de dados (data augmentation)
    • Cortes, inversões, mascaramento etc. aleatórios mudam as entradas a cada passo.
  4. Aleatoriedade da regularização (regularization)
    • Dropout (dropout) e métodos similares introduzem estocasticidade adicional.
  5. Não determinismo (nondeterminism) em nível de sistema
    • Não determinismo de kernel de GPU (GPU kernel), precisão mista (mixed precision), treinamento distribuído (distributed training) etc.

Como o tamanho do minilote muda o ruído

À medida que o tamanho do lote (m) aumenta, a estimativa do gradiente se torna menos ruidosa. Aproximadamente, a variância do gradiente muitas vezes escala como:

[ \mathrm{Var}(g_t) \propto \frac{1}{m} ]

Isso não é uma lei perfeita (redes profundas são complicadas), mas é uma intuição orientadora forte: lotes maiores reduzem o ruído estocástico, tornando o treinamento mais “determinístico”.

Fundamento teórico: aproximação estocástica (stochastic approximation)

A SGD pertence a uma classe mais ampla de métodos chamada aproximação estocástica, classicamente associada a Robbins–Monro. A configuração central é:

  • Você quer minimizar (F(\theta) = \mathbb{E}_{z \sim \mathcal{D}}[f(\theta; z)]),
  • Mas você só observa amostras (z_t),
  • Então você usa gradientes estocásticos (\nabla f(\theta_t; z_t)).

Sob condições como:

  • (F) é convexa (convex) (ou fortemente convexa (strongly convex)),
  • o ruído do gradiente tem variância limitada,
  • os tamanhos de passo seguem certos esquemas (schedules),

pode-se mostrar que a SGD converge (frequentemente em expectativa) para o ótimo, com taxas que dependem das suposições de convexidade.

Convergência (visão geral)

  • Para objetivos fortemente convexos, a SGD com taxa de aprendizado (learning rate) decrescente pode convergir para o ótimo com uma taxa como (O(1/t)) na suboptimalidade esperada (até constantes e termos de ruído).
  • Para convexos (não fortemente convexos), taxas típicas ficam mais próximas de (O(1/\sqrt{t})).
  • Para objetivos não convexos (nonconvex) (comuns em aprendizado profundo), a teoria frequentemente garante convergência para pontos estacionários (stationary points) no sentido de que (\mathbb{E}|\nabla F(\theta)|^2) diminui, mas não necessariamente para um mínimo global.

Para contraste, muitas garantias limpas vivem no mundo da Otimização Convexa. O treinamento de aprendizado profundo geralmente é não convexo, então a teoria guia a intuição mais do que fornece previsões completas.

Como a estocasticidade afeta a dinâmica de treinamento

A estocasticidade não é apenas “erro” — ela muda que tipos de soluções você tende a encontrar e como você chega até elas.

1) Progresso mais rápido por unidade de computação (especialmente no início)

No início do treinamento, os gradientes são grandes e passos ruidosos ainda se movem aproximadamente para baixo em média. Como os passos da SGD são baratos, você pode fazer muito mais atualizações com o mesmo orçamento computacional em comparação com métodos de lote completo.

Na prática, essa é uma grande razão pela qual métodos do tipo SGD dominam o treinamento de grandes Redes Neurais.

2) Curvas de perda ruidosas e comportamento “não monotônico”

Com SGD, a perda do minilote (e até mesmo a perda total avaliada ocasionalmente) pode aumentar em alguns passos. Isso é normal: o algoritmo troca confiabilidade por passo por atualizações mais baratas e mais frequentes.

3) Escapar de pontos de sela e armadilhas rasas

As perdas em aprendizado profundo têm muitos pontos de sela (saddle points) e regiões planas. O ruído pode ajudar a:

  • “Chutar” os parâmetros para fora de regiões onde o gradiente verdadeiro está perto de zero, mas não é uma boa solução.
  • Evitar que o otimizador fique preso em certas bacias estreitas.

Essa é uma razão pela qual métodos puramente determinísticos podem se comportar de forma diferente: remover o ruído pode tornar o treinamento mais estável, mas às vezes mais difícil de escapar de certas regiões problemáticas.

4) Regularização implícita (implicit regularization) e generalização (generalization)

Um fenômeno amplamente observado: a SGD frequentemente generaliza melhor do que o treinamento em lote completo, mesmo quando ambos atingem baixa perda de treinamento.

Uma intuição é que o ruído da SGD atua como um regularizador implícito, enviesando o treinamento em direção a soluções mais “simples” ou mais “robustas”. Explicações informais comuns incluem:

  • Preferência por mínimos mais planos (flatter minima) (regiões em que pequenas mudanças nos parâmetros não aumentam muito a perda).
  • Menor tendência a ajustar padrões espúrios e frágeis logo no início.

Isso não é um único teorema estabelecido em plena generalidade, mas é um padrão empírico forte que influencia escolhas práticas (tamanho do lote, taxa de aprendizado, aumento de dados).

5) Uma visão de “temperatura”: SGD como difusão

Em alguns regimes, a dinâmica da SGD pode ser aproximada por uma equação diferencial estocástica (stochastic differential equation), em que o ruído se comporta como um termo de difusão (diffusion). Nessa visão:

  • Taxa de aprendizado e tamanho do lote juntos controlam uma temperatura (temperature) efetiva.
  • Mais ruído (taxa de aprendizado mais alta, lote menor) explora mais; menos ruído refina em torno de uma bacia.

Isso é uma metáfora útil para pensar por que muitas receitas de treinamento:

  • Começam com taxas de aprendizado mais altas (mais exploração),
  • Depois fazem decair a taxa de aprendizado (mais exploração dirigida/refinamento).

Taxa de aprendizado: o principal controle da estocasticidade

Na SGD, a taxa de aprendizado (\eta) não é apenas uma configuração de velocidade; ela também controla a estabilidade e como o ruído se manifesta.

Taxas de aprendizado constantes vs. decrescentes

  • Taxa de aprendizado constante: pode convergir para uma vizinhança do ótimo devido ao ruído persistente; é boa para aprendizado contínuo ou cenários não estacionários (nonstationary settings).
  • Taxa de aprendizado decrescente: reduz o ruído dos passos ao longo do tempo e muitas vezes é necessária para obter perda de treinamento muito baixa.

Esquemas típicos usados em aprendizado profundo incluem decaimento em degraus (step decay), decaimento cosseno (cosine decay) e aquecimento linear (linear warmup) seguido de decaimento. A ideia-chave é a mesma: reduzir o ruído efetivo perto do fim para “assentar”.

Regra prática (SGD com minilotes)

  • Se o treinamento está instável/diverge: diminua a taxa de aprendizado ou aumente o tamanho do lote.
  • Se o treinamento está lento demais no início: aumente a taxa de aprendizado (com cuidado) ou use um esquema.

Minilotes: por que raramente usamos SGD “pura” (tamanho do lote = 1)

Em princípio, originalmente SGD significava usar uma única amostra por atualização. No aprendizado profundo moderno, “SGD” geralmente significa SGD com minilotes.

Razões:

  • GPUs/TPUs são eficientes com operações matriciais; tamanhos de lote melhoram a utilização de hardware (hardware utilization).
  • A média no lote reduz ruído extremo do gradiente, melhorando a estabilidade.

Existe um ponto ideal prático:

  • Pequeno demais: o treinamento fica instável ou ruidoso demais; a vazão (throughput) é ruim.
  • Grande demais: os passos ficam caros e podem prejudicar a generalização, a menos que a taxa de aprendizado e o esquema sejam ajustados.

O acoplamento tamanho do lote–taxa de aprendizado

Uma heurística comumente usada é a regra de escalonamento linear (linear scaling rule): se você multiplicar o tamanho do lote por (k), multiplique a taxa de aprendizado por (k) (pelo menos até certo ponto), muitas vezes com aquecimento. Isso funciona em muitos regimes de larga escala, mas pode falhar se você levar o tamanho do lote a uma faixa em que o comportamento de otimização/generalização muda.

Um exemplo concreto: regressão logística com SGD

Considere regressão logística (logistic regression) binária com perda no exemplo ((x_i, y_i)), (y_i \in {0,1}):

[ \ell(\theta; x_i, y_i) = -y_i \log \sigma(\theta^\top x_i) - (1-y_i)\log(1-\sigma(\theta^\top x_i)) ]

Um passo de SGD com minilote:

  1. Amostrar o minilote (B_t).
  2. Calcular o gradiente médio nesse minilote.
  3. Atualizar os parâmetros.

Em pseudocódigo com estilo de código:

theta = init()
for step in range(num_steps):
    B = sample_minibatch(data, batch_size=m)
    grad = 0.0
    for x, y in B:
        p = sigmoid(dot(theta, x))
        grad += (p - y) * x
    grad /= m
    theta -= lr * grad

Se você executar isso com diferentes sementes aleatórias (random seeds), pode obter trajetórias um pouco diferentes e, às vezes, soluções finais diferentes — especialmente em modelos não convexos. Essa variabilidade é uma assinatura direta da otimização estocástica.

Além da SGD simples: momento (momentum) e métodos adaptativos (adaptive methods) (brevemente)

Embora este artigo se concentre na estocasticidade, vale notar que a maioria dos otimizadores práticos modifica como gradientes estocásticos são usados:

  • SGD com momento suaviza gradientes ruidosos ao acumular um vetor de velocidade (velocity vector), frequentemente melhorando a velocidade de convergência e a estabilidade.
  • Métodos adaptativos (por exemplo, Adam) reescalam atualizações por parâmetro (per-parameter) com base em estatísticas acumuladas de gradientes passados.

Mesmo com esses métodos, a estocasticidade da estimativa do gradiente permanece fundamental: ela ainda afeta generalização, estabilidade e como as soluções são selecionadas.

(Para a linha de base determinística, veja Descida do Gradiente.)

Otimização estocástica em cenários com restrições (constrained settings)

Alguns problemas impõem restrições (constraints) em (\theta) (por exemplo, limites de norma, restrições de simplex). A otimização estocástica pode lidar com isso via:

  • SGD projetado (projected SGD): dar um passo estocástico e depois projetar de volta para o conjunto viável.
  • Métodos de penalidade/barreira (penalty/barrier methods) com gradientes estocásticos.

Para mais sobre o lado das restrições, veja Otimização com Restrições.

Orientações práticas: fazer a SGD funcionar bem

Diagnosticando problemas comuns

  • Divergência / NaNs
    • Diminua a taxa de aprendizado, adicione recorte de gradiente (gradient clipping), verifique a estabilidade de precisão mista, aumente o tamanho do lote.
  • A perda diminui, mas a acurácia estagna
    • Verifique o pipeline de dados, a qualidade dos rótulos, a força do aumento de dados e se o esquema de taxa de aprendizado é apropriado.
  • Treinamento muito ruidoso
    • Aumente o tamanho do lote, adicione momento ou diminua a taxa de aprendizado. Garanta que estatísticas de lote (batch statistics) (se existirem) estejam estáveis.

Dicas que refletem a “história do ruído”

  • Use embaralhamento (shuffling) a cada época (epoch): reduz viés na amostragem de minilotes.
  • Ajuste tamanho do lote e taxa de aprendizado juntos: eles controlam conjuntamente ruído e estabilidade.
  • Use decaimento da taxa de aprendizado: ruído alto no início pode ajudar a explorar; ruído baixo no fim ajuda a convergir.
  • Não superinterprete a perda por passo: observe médias móveis ou avalie periodicamente em um conjunto de validação (validation set).

Quando mais ruído pode ajudar

  • Treinamento inicial de redes profundas: o ruído pode evitar sobreajuste prematuro e ajudar na exploração.
  • Objetivos altamente não convexos: o ruído pode ajudar a atravessar selas/platôs.

Quando menos ruído pode ajudar

  • Ajuste fino (fine-tuning) perto de uma boa solução: reduza a taxa de aprendizado (e às vezes aumente o tamanho do lote) para refinar.
  • Objetivos sensíveis (por exemplo, algumas configurações de aprendizado por reforço (reinforcement learning)): ruído demais no gradiente pode desestabilizar o aprendizado.

Resumo: a essência da otimização estocástica

  • Otimização estocástica substitui gradientes exatos por estimativas aleatórias e ruidosas.
  • Na SGD, minilotes tornam o treinamento escalável e eficiente, ao custo de atualizações ruidosas.
  • O ruído não é apenas um incômodo:
    • Ele afeta estabilidade e convergência,
    • Ajuda a escapar de selas e explorar,
    • Frequentemente muda a generalização via regularização implícita.
  • Os principais controles práticos — taxa de aprendizado, tamanho do lote e esquemas — em grande parte controlam a quantidade e o impacto da estocasticidade.

No ML moderno, entender o treinamento significa entender essa troca: determinismo dá descida suave; estocasticidade dá aprendizado escalável e frequentemente soluções melhores.