A descida de gradiente estocástico (muitas vezes abreviada como SGD, do inglês stochastic gradient descent) é um método iterativo para otimizar uma função objetivo com propriedades de suavidade adequadas (por exemplo, diferenciável ou subdiferenciável). Pode ser considerada uma aproximação estocástica da otimização por descida de gradiente, uma vez que substitui o gradiente real (calculado a partir de todo o conjunto de dados) por uma estimativa dele (calculada a partir de um subconjunto dos dados selecionado aleatoriamente). Especialmente em problemas de otimização de alta dimensionalidade, isso reduz a altíssima carga computacional, alcançando iterações mais rápidas em troca de uma menor taxa de convergência.

A ideia básica por trás da aproximação estocástica pode ser rastreada até ao algoritmo de Robbins-Monro da década de 1950. Hoje, a descida de gradiente estocástico tornou-se um importante método de otimização no aprendizado de máquina.

Contexto

Tanto a estimativa estatística quanto o aprendizado de máquina consideram o problema de minimizar uma função objetivo que tem a forma de uma soma: onde o parâmetro que minimiza deve ser estimado. Cada função parcela está tipicamente associada à -ésima observação no conjunto de dados (usado para treinamento).

Na estatística clássica, problemas de minimização de soma surgem nos mínimos quadrados e na estimativa de máxima verossimilhança (para observações independentes). A classe geral de estimadores que surgem como minimizadores de somas são chamados de M-estimadores. No entanto, na estatística, há muito tempo reconhece-se que exigir a minimização mesmo local é demasiado restritivo para alguns problemas de estimativa de máxima verossimilhança. Portanto, teóricos estatísticos contemporâneos consideram frequentemente pontos estacionários da função de verossimilhança (ou zeros da sua derivada, a função score, e outras equações de estimação).

O problema da minimização de soma também surge para a minimização do risco empírico. Nesse caso, é o valor da função de perda no -ésimo exemplo, e é o risco empírico.

Quando usado para minimizar a função acima, um método padrão (ou "em lote") de descida de gradiente realizaria as seguintes iterações: O tamanho do passo é denotado por (às vezes chamado de taxa de aprendizado no aprendizado de máquina) e aqui "" denota a atualização de uma variável no algoritmo.

Em muitos casos, as funções da parcela têm uma forma simples que permite avaliações baratas da função-soma e do gradiente da soma. Por exemplo, na estatística, famílias exponenciais de um parâmetro permitem avaliações económicas de função e de gradiente.

No entanto, noutros casos, a avaliação do gradiente da soma pode exigir avaliações caras dos gradientes de todas as funções da parcela. Quando o conjunto de treinamento é enorme e não existem fórmulas simples, a avaliação das somas dos gradientes torna-se muito cara, porque a avaliação do gradiente requer a avaliação dos gradientes de todas as funções da parcela. Para economizar no custo computacional a cada iteração, a descida de gradiente estocástico amostra um subconjunto das funções da parcela a cada passo. Isto é muito eficaz no caso de problemas de aprendizado de máquina em larga escala.

Método iterativo direita|miniaturadaimagem|Flutuações na função objetivo total à medida que passos de gradiente em relação a minilotes (mini-batches) são dados Na descida de gradiente estocástico (ou "online"), o verdadeiro gradiente de é aproximado por um gradiente em uma única amostra: À medida que o algoritmo varre o conjunto de treinamento, ele executa a atualização acima para cada amostra de treinamento. Várias passagens podem ser feitas sobre o conjunto de treinamento até que o algoritmo convirja. Se isso for feito, os dados podem ser embaralhados a cada passagem para evitar ciclos. Implementações típicas podem usar uma taxa de aprendizado adaptativa para que o algoritmo convirja.

Em pseudocódigo, a descida de gradiente estocástico pode ser apresentada como:

Escolha um vetor inicial de parâmetros e uma taxa de aprendizado . Repita até obter um mínimo aproximado: Embaralhe aleatoriamente as amostras no conjunto de treinamento. Para , faça:

Um meio-termo entre calcular o gradiente verdadeiro e o gradiente numa única amostra é calcular o gradiente em relação a mais do que uma amostra de treinamento (chamado de "minilote" ou mini-batch) em cada passo. Isto pode ter um desempenho significativamente melhor do que a descida de gradiente estocástico "verdadeira" descrita, porque o código pode fazer uso de bibliotecas de vetorização em vez de calcular cada passo separadamente, conforme mostrado pela primeira vez em onde foi chamado de "algoritmo de retropropagação no modo de grupo". Também pode resultar numa convergência mais suave, uma vez que o gradiente calculado a cada passo é a média de mais amostras de treinamento.

A convergência da descida de gradiente estocástico tem sido analisada utilizando as teorias de minimização convexa e de aproximação estocástica. Resumidamente, quando a taxa de aprendizagem diminui com uma taxa apropriada, e sujeita a suposições relativamente brandas, a descida de gradiente estocástico converge quase certamente para um mínimo global quando a função objetivo é convexa ou pseudoconvexa, e caso contrário converge quase certamente para um mínimo local. Isto é, na verdade, uma consequência do teorema de Robbins-Siegmund.

Regressão linear Suponha que queremos ajustar uma linha reta a um conjunto de treinamento com observações e as respostas estimadas correspondentes usando mínimos quadrados. A função objetivo a ser minimizada é A última linha no pseudocódigo acima para esse problema específico tornar-se-á: Note que, a cada iteração ou passo de atualização, o gradiente é avaliado apenas em um único . Esta é a principal diferença entre a descida de gradiente estocástico e a descida de gradiente em lote.

No geral, dado um problema de regressão linear , a descida de gradiente estocástico comporta-se de forma diferente quando (subparametrizada) e (sobreparametrizada). No caso sobreparametrizado, a descida de gradiente estocástico converge para . Ou seja, a SGD converge para a solução de interpolação com distância mínima do ponto de partida . Isso é verdade mesmo quando a taxa de aprendizado permanece constante. No caso subparametrizado, a SGD não converge se a taxa de aprendizado permanecer constante.

História Em 1951, Herbert Robbins e Sutton Monro introduziram os primeiros métodos de aproximação estocástica, precedendo a descida de gradiente estocástico. Com base neste trabalho, um ano depois, Jack Kiefer e Jacob Wolfowitz publicaram um algoritmo de otimização muito próximo da descida de gradiente estocástico, usando diferenças centrais como uma aproximação do gradiente. Mais tarde, na década de 1950, Frank Rosenblatt usou a SGD para otimizar o seu modelo perceptron, demonstrando a primeira aplicabilidade da descida de gradiente estocástico a redes neurais.

A retropropagação foi descrita pela primeira vez em 1986, com a descida de gradiente estocástico a ser utilizada para otimizar eficientemente parâmetros através de redes neurais com múltiplas camadas ocultas. Pouco depois, foi desenvolvida outra melhoria: a descida de gradiente em minilotes, onde pequenos lotes de dados substituem amostras individuais. Em 1997, os benefícios práticos de desempenho da vetorização alcançáveis com tais pequenos lotes foram explorados pela primeira vez, pavimentando o caminho para a otimização eficiente em aprendizado de máquina. Até 2023, essa abordagem de minilotes permanece a norma para o treinamento de redes neurais, equilibrando os benefícios da descida de gradiente estocástico com a descida de gradiente.

Na década de 1980, o momentum já havia sido introduzido e foi adicionado às técnicas de otimização de SGD em 1986. Contudo, estas técnicas de otimização presumiam hiperparâmetros constantes, isto é, uma taxa de aprendizado e parâmetro de momentum fixos. Na década de 2010, foram introduzidas abordagens adaptativas à aplicação de SGD com uma taxa de aprendizagem por parâmetro, com o AdaGrad (de "Adaptive Gradient") em 2011 e o RMSprop (de "Root Mean Square Propagation") em 2012. Em 2014, foi publicado o Adam (de "Adaptive Moment Estimation"), aplicando as abordagens adaptativas do RMSprop ao momentum; muitos aprimoramentos e ramificações do Adam foram então desenvolvidos, tais como Adadelta, Adagrad, AdamW e Adamax.

Dentro do aprendizado de máquina, as abordagens à otimização em 2023 são dominadas por otimizadores derivados do Adam. O TensorFlow e o PyTorch, de longe as bibliotecas de aprendizado de máquina mais populares até ao mesmo ano, no geral, apenas incluem otimizadores derivados do Adam, bem como os precursores do Adam como o RMSprop e o SGD clássico. O PyTorch também suporta parcialmente o L-BFGS, um método de pesquisa em linha, mas apenas para configurações de dispositivo único sem grupos de parâmetros.

Aplicações notáveis A descida de gradiente estocástico é um algoritmo popular para treinar uma vasta gama de modelos no aprendizado de máquina, incluindo máquinas de vetores de suporte (lineares), regressão logística (ver, e.g., Vowpal Wabbit) e modelos gráficos.Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning (2008). Efficient, Feature-based, Conditional Random Field Parsing. Proc. Annual Meeting of the ACL. Quando combinado com o algoritmo de retropropagação, é o algoritmo padrão de facto para treinar redes neurais artificiais.LeCun, Yann A., et al. "Efficient backprop." Neural networks: Tricks of the trade. Springer Berlin Heidelberg, 2012. 9-48 O seu uso também foi relatado na comunidade de Geofísica, especificamente em aplicações de Inversão de Forma de Onda Completa (Full Waveform Inversion - FWI).

A descida de gradiente estocástico concorre com o algoritmo L-BFGS, que também é amplamente utilizado. A descida de gradiente estocástico tem sido usada desde pelo menos 1960 para treinar modelos de regressão linear, originalmente com o nome de ADALINE.

Outro algoritmo de descida de gradiente estocástico é o filtro adaptativo de mínimos quadrados médios (LMS).

Extensões e variantes Muitas melhorias no algoritmo básico de descida de gradiente estocástico foram propostas e utilizadas. Em particular, no aprendizado de máquina, a necessidade de definir uma taxa de aprendizado (tamanho do passo) foi reconhecida como problemática. Defini-la muito alta pode fazer o algoritmo divergir; defini-la muito baixa faz com que a convergência seja lenta. Uma extensão conceitualmente simples da descida de gradiente estocástico torna a taxa de aprendizado uma função decrescente do número da iteração , estabelecendo um cronograma de taxa de aprendizado, de modo que as primeiras iterações causem grandes mudanças nos parâmetros, enquanto as posteriores façam apenas ajustes finos. Tais cronogramas são conhecidos desde o trabalho de MacQueen no agrupamento -means.Citado por Orientações práticas sobre a escolha do tamanho do passo em várias variantes do SGD são dadas por Spall. thumb|Um gráfico visualizando o comportamento de um conjunto selecionado de otimizadores, usando uma projeção em perspectiva 3D de uma função de perda f(x, y) thumb|Um gráfico visualizando o comportamento de um conjunto selecionado de otimizadores

Atualizações implícitas (ISGD) Como mencionado anteriormente, a descida de gradiente estocástico clássica é geralmente sensível à taxa de aprendizado . A convergência rápida requer altas taxas de aprendizado, mas isso pode induzir instabilidade numérica. O problema pode ser amplamente resolvido considerando atualizações implícitas onde o gradiente estocástico é avaliado na próxima iteração em vez de na atual:

Esta equação é implícita, pois aparece em ambos os lados da equação. É uma forma estocástica do método do gradiente proximal, uma vez que a atualização também pode ser escrita como: