Otimização Estocástica

A otimização estocástica minimiza um objetivo usando estimativas ruidosas de seu gradiente ou valor, atualizando parâmetros a partir de subconjuntos aleatórios de dados ou perturbações aleatórias, em vez do objetivo completo e exato.

Definition

A otimização estocástica é uma família de métodos iterativos que atualizam estimativas de parâmetros usando estimativas aleatórias e não enviesadas de um objetivo ou seu gradiente, permitindo a otimização quando o objetivo completo é muito caro para ser avaliado ou é observado apenas com ruído.

Scope

Este tópico abrange a aproximação estocástica na tradição de Robbins-Monro, o gradiente descendente estocástico e suas variantes de mini-lote e momentum, os agendamentos de tamanho de passo (taxa de aprendizado) que controlam a convergência, a troca entre ruído e custo computacional, e garantias de convergência. Seu papel no ajuste de modelos estatísticos e de aprendizado de máquina em larga escala é enfatizado.

Core questions

• Como estimativas de gradiente ruidosas podem impulsionar a convergência para um ótimo?
• Quais agendamentos de tamanho de passo garantem a convergência no arcabouço de Robbins-Monro?
• Como o mini-lote troca ruído por custo computacional por passo?
• Por que a otimização estocástica é essencial para conjuntos de dados muito grandes?

Key concepts

• Aproximação estocástica
• Gradiente de mini-lote
• Agendamento da taxa de aprendizado
• Estimativa de gradiente não enviesada
• Decaimento do tamanho do passo
• Convergência quase-certa

Key theories

Aproximação estocástica

O esquema de Robbins-Monro encontra a raiz de uma função desconhecida a partir de medições ruidosas, dando pequenos passos cujos tamanhos diminuem a uma taxa prescrita, convergindo quase certamente sob condições na sequência do tamanho do passo.

Métodos de gradiente estocástico

Substituir o gradiente completo por uma estimativa não enviesada de um subconjunto de dados aleatório produz atualizações baratas cuja trajetória média desce o objetivo, com agendamentos da taxa de aprendizado equilibrando a velocidade de convergência contra a variância do ruído.

Clinical relevance

Os métodos de gradiente estocástico possibilitam ajustar modelos a conjuntos de dados grandes demais para serem processados de uma só vez, e são a estratégia de otimização dominante para treinar redes neurais e regressão em larga escala, onde o cálculo do gradiente completo a cada passo seria proibitivo.

History

Robbins e Monro introduziram a aproximação estocástica em 1951 para encontrar raízes a partir de observações ruidosas, e Kiefer e Wolfowitz a adaptaram para otimização logo depois; a explosão do aprendizado de máquina em larga escala reviveu essas ideias como gradiente descendente estocástico e suas muitas variantes modernas.

Key figures

• Herbert Robbins
• Sutton Monro
• Harold Kushner
• Jack Kiefer

Seminal works

• robbins1951
• kushner2003

Frequently asked questions

Por que usar gradientes ruidosos em vez do gradiente exato?

Calcular o gradiente exato sobre milhões de pontos de dados é caro. Um gradiente estimado a partir de um pequeno lote aleatório é muito mais barato e, embora ruidoso, ainda aponta para baixo em média, então muitos passos ruidosos e baratos podem superar alguns exatos.

Por que o tamanho do passo geralmente diminui com o tempo?

Diminuir o tamanho do passo amortece o ruído do gradiente à medida que as iterações se aproximam do ótimo, o que as condições de Robbins-Monro exigem para a convergência. Um tamanho de passo que permanece muito grande faz com que a estimativa oscile em torno da solução.