Aula 11: Otimização de Segunda Ordem (Método de Newton) e Precondicionamento Diagonal

Otimização e Álgebra Linear para Machine Learning

Autor

Marcos M. Raimundo — Instituto de Computação, UNICAMP

Data de Publicação

23 de outubro de 2026

1 Revisão e Introdução

1.1 Revisão Cuidadosa: O Que a Aula 10 Deixou Pronto

Na Aula 10, investigamos o treinamento estocástico em larga escala com o Gradiente Descendente Estocástico (SGD) e o Mini-Batching. Provamos que avaliar somas finitas sobre \(N\) amostras a cada iteração torna-se proibitivo quando os conjuntos de dados atingem milhões de exemplos (\(\mathcal{O}(Nd)\) por passo). Ao sortear lotes de tamanho \(B \ll N\), reduzimos o custo computacional por atualização e exploramos a arquitetura vetorial massiva de processadores modernos (BLAS-3 e Tensor Cores), reduzindo a variância do ruído amostral por um fator de \(1/B\).

No entanto, tanto o SGD quanto o Batch Gradient Descent (BGD) clássico compartilham uma limitação estrutural severa: eles operam com uma única taxa de aprendizado escalar global \(\alpha\) aplicada uniformemente a todos os parâmetros do modelo.

Na Aula 8, vimos que a taxa de contração de erro do gradiente descendente em uma forma quadrática é governada pelo número de condição da matriz Hessiana: \[\kappa = \frac{\lambda_{\max}}{\lambda_{\min}}\] Quando as variáveis de entrada exibem escalas heterogêneas ou correlações acentuadas, o número de condição atinge valores na ordem de milhares ou milhões (\(\kappa \gg 1\)). Nesse cenário, um valor de \(\alpha\) grande o bastante para avançar nas direções de baixa curvatura (\(\lambda_{\min}\)) causa oscilações catastróficas e divergência nas direções íngremes (\(\lambda_{\max}\)). Inversamente, escolher \(\alpha < 2/\lambda_{\max}\) para garantir estabilidade condena o modelo a rastejar de forma paralisante ao longo das direções suaves.

1.2 Ideia Central: Da Bússola Cega à Curvatura de Segunda Ordem

O gradiente \(\nabla f(\mathbf{w})\) é uma bússola de primeira ordem: ele informa rigorosamente para onde o terreno sobe com maior inclinação instantânea, mas é completamente cego sobre como essa inclinação varia conforme nos deslocamos.

Para saber quão longe podemos pisar sem ultrapassar o fundo da bacia, precisamos de informação de segunda ordem: a matriz Hessiana \(\nabla^2 f(\mathbf{w})\). Se a função puder ser aproximada localmente por uma parábola, o vértice dessa parábola pode ser calculado diretamente em um único passo.

Esta aula investiga essa transição matemática fundamental: 1. O que seria o algoritmo perfeito sob curvatura exata? \(\to\) O Método de Newton Multivariado. 2. Por que esse método ideal colapsa computacionalmente em modelos reais? \(\to\) O custo cúbico \(\mathcal{O}(d^3)\) e as armadilhas de não-convexidade. 3. Como aproximar a curvatura de forma barata e escalável? \(\to\) O Precondicionamento Diagonal e as taxas de aprendizado adaptativas do AdaGrad e RMSProp.

1.3 Roteiro da Aula

Nesta aula, responderemos a quatro perguntas centrais: 1. O Modelo Quadrático: Como a expansão de Taylor multivariada deduz analiticamente o passo de Newton e por que ele é imune a transformações lineares de coordenadas? 2. As Patologias em Larga Escala: Por que a inversão exata da Hessiana falha em aprendizado profundo (\(\mathcal{O}(d^3)\) em tempo, \(\mathcal{O}(d^2)\) em espaço e atração fatal por pontos de sela)? 3. A Geometria do Precondicionamento: Como a mudança de variáveis desacopla o espaço de parâmetros e por que a restrição a matrizes diagonais reduz a complexidade para \(\mathcal{O}(d)\)? 4. Escalas Adaptativas por Coordenada: Como o AdaGrad e o RMSProp utilizam o histórico de gradientes de 1ª ordem para construir taxas adaptativas sem calcular segundas derivadas?

1.4 Problema Motivador: O Descompasso no California Housing

Considere a base de dados do California Housing sem padronização prévia, predizendo o valor mediano dos imóveis a partir de variáveis com naturezas físicas distintas: * MedInc: Renda mediana das famílias (em dezenas de milhares de dólares, variando entre \(0{,}5\) e \(15\)). * AveBedrms: Número médio de dormitórios (variando em torno de \(1\)).

Ao computarmos a matriz Hessiana empírica \(H = \frac{1}{N} X^T X\) dos dados brutos, o autovalor máximo atinge \(\lambda_{\max} \approx 6{,}3 \cdot 10^3\), enquanto o menor autovalor é \(\lambda_{\min} \approx 0{,}27\). O número de condição resultante é: \[\kappa \approx 23.460{,}5\]

Se executarmos o Gradiente Descendente euclidiano, a taxa máxima de aprendizado admitida sem divergir é \(\alpha < \frac{2}{\lambda_{\max}} \approx 0{,}0003\). Com essa taxa, a coordenada de alta variância caminha de forma estável, mas a coordenada associada a \(\lambda_{\min}\) tem contração por passo de apenas \((1 - \alpha \lambda_{\min}) \approx 0{,}99991\). Para reduzir o erro nessa variável suave por míseros 50%, seriam necessárias mais de 7.700 iterações!

1.5 A Limitação do Passo Escalar Único

O Dilema da Taxa Global

Suponha uma função quadrática \(f(w_1, w_2) = \frac{1}{2}(1000 w_1^2 + w_2^2)\). O que acontece ao aplicar Gradiente Descendente com passo escalar único \(\alpha\)? Qual é o valor máximo de \(\alpha\) para evitar divergência em \(w_1\)? Sob esse \(\alpha\), quantas iterações são necessárias para reduzir o erro em \(w_2\) por um fator de 10?

Diagnóstico de Condicionamento

Julgue V ou F — a questão só conta se acertar os 4 itens:

□ Em uma superfície com número de condição \(\kappa = 1000\), o maior autovalor da Hessiana impõe o teto da taxa de aprendizado admissível (\(\alpha < 2/\lambda_{\max}\)).
□ Ao selecionar \(\alpha = 1/\lambda_{\max}\), a coordenada associada a \(\lambda_{\min}\) atinge o valor ótimo em uma única iteração.
□ A padronização de variáveis por escore \(Z\) elimina completamente todas as discrepâncias de curvatura em modelos não-lineares arbitrários.
□ Em modelos com representações esparsas (como one-hot encoding em PLN), atributos raros recebem gradientes nulos na maioria dos passos, de modo que um passo escalar pequeno global retarda excessivamente seu aprendizado.

2 Intuição — A Bacia Elíptica e a Lente Métrica

2.1 O Vale Estreito e a Ilusão do Gradiente

Imagine uma tigela perfeitamente esférica esculpida em mármore. Se soltarmos uma esfera em qualquer ponto da borda, a força gravitacional aponta exatamente para o ponto mais baixo no centro. Em uma bacia esférica, a direção do gradiente descendente \(-\nabla f(\mathbf{w})\) coincide rigorosamente com o vetor que conecta a posição atual ao minimizador global \(\mathbf{w}^\star\).

Agora imagine que esmagamos lateralmente essa bacia, transformando-a em uma calha estreita com proporção de 100 para 1. As curvas de nível deixam de ser círculos concêntricos e tornam-se elipses extremamente achatadas.

Nesse vale elíptico: * Nas laterais íngremes, o gradiente aponta quase transversalmente às curvas de nível — ou seja, perpendicularmente à calha! * Ele manda o otimizador atravessar o vale de um lado para o outro, em ziguezague frenético, em vez de apontar para o fundo ao longo do eixo longitudinal.

O Método de Newton pode ser interpretado como uma lente geométrica: ele mede a curvatura em todas as direções via Hessiana e aplica uma deformação métrica inversa (\(H^{-1}\)). Essa lente distorce o espaço de volta, transformando as elipses achatadas em círculos perfeitos. Nesse espaço corrigido pela curvatura, um único passo de gradiente aponta diretamente para o centro!

O Precondicionamento Diagonal, por sua vez, é uma versão pragmática dessa lente: em vez de corrigir rotações complexas, ele apenas estica ou encolhe os eixos cartesianos independentemente, equalizando a largura e o comprimento das coordenadas sem girar o espaço.

2.2 Visualização: Deformação Métrica em Bacia Elíptica

O gráfico abaixo ilustra como a transformação métrica gerada por \(H^{-1/2}\) converte as curvas de nível elípticas em círculos perfeitos:

3 Bloco 1: A Aproximação Quadrática de Taylor e o Método de Newton

3.1 A Minimização do Modelo Substituto Local e o Papel dos Restos de Taylor

Para compreender a fundamentação matemática do Método de Newton, é essencial contrastá-lo com a derivação rigorosa do Gradiente Descendente através da Série de Taylor com Resto.

Considere uma função de perda suficientemente diferenciável \(f: \mathbb{R}^d \to \mathbb{R}\). Na vizinhança da iteração corrente \(\mathbf{w}_k\), podemos expandir a função em diferentes ordens de aproximação.

3.1.1 1. O Passo do Gradiente: Taylor de 1ª Ordem com Resto

A expansão de Taylor de primeira ordem com resto de Lagrange é dada por: \[f(\mathbf{w}_k + \Delta\mathbf{w}) = f(\mathbf{w}_k) + \nabla f(\mathbf{w}_k)^T \Delta\mathbf{w} + R_1(\Delta\mathbf{w})\] onde o termo residual exato de segunda ordem é: \[R_1(\Delta\mathbf{w}) = \frac{1}{2}\Delta\mathbf{w}^T \nabla^2 f(\boldsymbol{\xi}) \Delta\mathbf{w}, \quad \text{para algum } \boldsymbol{\xi} \in [\mathbf{w}_k, \mathbf{w}_k + \Delta\mathbf{w}]\]

Observe o impasse fundamental: se tentássemos minimizar diretamente apenas a parte linear \(f(\mathbf{w}_k) + \nabla f(\mathbf{w}_k)^T \Delta\mathbf{w}\), o problema seria ilimitado inferiormente (\(\inf_{\Delta\mathbf{w}} \nabla f^T \Delta\mathbf{w} = -\infty\)). Um plano inclinado não possui fundo!

Para tornar a minimização factível, precisamos de um modelo substituto. Na Aula 8, sob a hipótese de \(L\)-suavidade (\(\|\nabla^2 f(\boldsymbol{\xi})\|_2 \le L\)), vimos que o Lema da Descida majora o resto \(R_1\) pelo pior caso esférico isotrópico: \[R_1(\Delta\mathbf{w}) \le \frac{L}{2} \|\Delta\mathbf{w}\|_2^2 \implies R_1(\Delta\mathbf{w}) \approx \frac{1}{2\alpha} \|\Delta\mathbf{w}\|_2^2\]

O modelo substituto de 1ª ordem do GD é, portanto: \[m_{\text{GD}}(\Delta\mathbf{w}) \triangleq f(\mathbf{w}_k) + \nabla f(\mathbf{w}_k)^T \Delta\mathbf{w} + \frac{1}{2\alpha} \|\Delta\mathbf{w}\|_2^2\]

Minimizando esse modelo esférico: \[\nabla_{\Delta\mathbf{w}} m_{\text{GD}}(\Delta\mathbf{w}) = \nabla f(\mathbf{w}_k) + \frac{1}{\alpha}\Delta\mathbf{w} = \mathbf{0} \implies \Delta\mathbf{w}_{\text{GD}} = -\alpha \nabla f(\mathbf{w}_k)\]

O que ficou faltando no Gradiente Descendente? Ficou faltando o resto de segunda ordem real \(R_1(\Delta\mathbf{w})\). O GD ignorou completamente a curvatura direcional e as correlações cruzadas entre coordenadas, substituindo a Hessiana por uma esfera cega \(\frac{1}{\alpha} I\).

3.1.2 2. O Passo de Newton: Taylor de 2ª Ordem com Resto

Em vez de jogar fora o resto de 2ª ordem e substituí-lo por uma penalidade esférica, o Método de Newton incorpora a curvatura real da função calculada no ponto \(\mathbf{w}_k\), expandindo a Série de Taylor até o termo quadrático: \[f(\mathbf{w}_k + \Delta\mathbf{w}) = \underbrace{f(\mathbf{w}_k) + \nabla f(\mathbf{w}_k)^T \Delta\mathbf{w} + \frac{1}{2}\Delta\mathbf{w}^T H_k \Delta\mathbf{w}}_{q(\Delta\mathbf{w})} + R_2(\Delta\mathbf{w})\] onde \(H_k \triangleq \nabla^2 f(\mathbf{w}_k)\) é a matriz Hessiana calculada em \(\mathbf{w}_k\) e o novo resto é de terceira ordem: \[R_2(\Delta\mathbf{w}) = \mathcal{O}(\|\Delta\mathbf{w}\|^3) = \frac{1}{6} \nabla^3 f(\boldsymbol{\xi})[\Delta\mathbf{w}, \Delta\mathbf{w}, \Delta\mathbf{w}]\]

O modelo substituto de 2ª ordem de Newton minimiza o paraboloide tangente \(q(\Delta\mathbf{w})\), desconsiderando o resto \(R_2\): \[\min_{\Delta\mathbf{w}} \; q(\Delta\mathbf{w}) = f(\mathbf{w}_k) + \nabla f(\mathbf{w}_k)^T \Delta\mathbf{w} + \frac{1}{2} \Delta\mathbf{w}^T H_k \Delta\mathbf{w}\]

Aplicando as condições de otimalidade da Aula 7: 1. Condição de 1ª Ordem: Anulando a derivada em relação a \(\Delta\mathbf{w}\): \[\nabla_{\Delta\mathbf{w}} q(\Delta\mathbf{w}) = \nabla f(\mathbf{w}_k) + H_k \Delta\mathbf{w} = \mathbf{0} \implies H_k \Delta\mathbf{w} = -\nabla f(\mathbf{w}_k)\] 2. Condição de 2ª Ordem: Como \(\nabla^2_{\Delta\mathbf{w}} q = H_k \succ 0\), a matriz é invertível e o ponto crítico é um mínimo global estrito de \(q\): \[\Delta\mathbf{w}_{\text{nt}} = -H_k^{-1} \nabla f(\mathbf{w}_k)\]

O que fica faltando no Método de Newton? Fica faltando o resto de terceira ordem \(R_2(\Delta\mathbf{w}) = \mathcal{O}(\|\Delta\mathbf{w}\|^3)\)! * Caso Exato (Formas Quadráticas): Se \(f(\mathbf{w})\) for estritamente quadrática (como nos Mínimos Quadrados da Aula 3 e Aula 8), as derivadas de ordem 3+ são identicamente nulas (\(\nabla^3 f \equiv \mathbf{0} \implies R_2 \equiv 0\)). O modelo quadrático coincide rigorosamente com a função real em todo o espaço, e Newton converge em 1 único passo! * Caso Geral (Não-Linear): Se \(f\) tiver termos cúbicos ou superiores, \(R_2 \neq 0\). O passo de Newton só é uma aproximação fiel localmente, na vizinhança onde o deslocamento \(\|\Delta\mathbf{w}\|\) é suficientemente pequeno para que o erro residual de 3ª ordem \(\|\Delta\mathbf{w}\|^3\) seja desprezível diante da curvatura de 2ª ordem.

3.1.3 3. A Regra de Atualização e a Auto-Calibração de Escala

Como \(\Delta\mathbf{w} \triangleq \mathbf{w} - \mathbf{w}_k\) representa o vetor de deslocamento relativo, a próxima iteração \(\mathbf{w}_{k+1}\) é a translação pelo passo ótimo: \[\mathbf{w}_{k+1} \triangleq \mathbf{w}_k + \Delta\mathbf{w}_{\text{nt}} = \mathbf{w}_k - [\nabla^2 f(\mathbf{w}_k)]^{-1} \nabla f(\mathbf{w}_k)\]

Por que Newton não possui taxa de aprendizado hiperparamétrica \(\alpha\)? Observe a análise dimensional: * O gradiente \([\nabla f]\) possui dimensão de \([\text{perda}] / [\text{parâmetro}]\). * A Hessiana \([H]\) possui dimensão de \([\text{perda}] / [\text{parâmetro}]^2\), de modo que sua inversa \([H^{-1}]\) tem dimensão de \([\text{parâmetro}]^2 / [\text{perda}]\). * O produto \([H^{-1} \nabla f]\) resulta em: \[\frac{[\text{parâmetro}]^2}{[\text{perda}]} \times \frac{[\text{perda}]}{[\text{parâmetro}]} = [\text{parâmetro}]\]

No Gradiente Descendente, o passo é \(-\alpha \nabla f\); como o gradiente é uma taxa de variação (inclinação), o hiperparâmetro \(\alpha\) precisa atuar artificialmente como um fator de conversão de unidades para transformar inclinação em distância. Em Newton, a curvatura \(H^{-1}\) já realiza essa conversão de forma analítica e exata: nas direções onde a parábola é muito fechada (\(\lambda_i\) grande), \(H^{-1}\) encurta o passo; onde a parábola é rasa (\(\lambda_i\) pequeno), \(H^{-1}\) estica o passo, atingindo o vértice da bacia diretamente.

3.2 Como Surge o Decremento de Newton?

Após calcular o passo de Newton \(\Delta\mathbf{w}_{\text{nt}} = -H_k^{-1}\nabla f(\mathbf{w}_k)\), surge uma questão natural: quanto o modelo quadrático prevê que a função de perda vai diminuir se dermos esse passo?

Para responder, calculamos a diferença entre o valor do modelo na posição atual (\(q(\mathbf{0}) = f(\mathbf{w}_k)\)) e o valor atingido no vértice da parábola (\(q(\Delta\mathbf{w}_{\text{nt}})\)): \[q(\Delta\mathbf{w}_{\text{nt}}) = f(\mathbf{w}_k) + \nabla f(\mathbf{w}_k)^T \Delta\mathbf{w}_{\text{nt}} + \frac{1}{2}\Delta\mathbf{w}_{\text{nt}}^T H_k \Delta\mathbf{w}_{\text{nt}}\]

Substituindo \(\Delta\mathbf{w}_{\text{nt}} = -H_k^{-1}\nabla f(\mathbf{w}_k)\): \[q(\Delta\mathbf{w}_{\text{nt}}) = f(\mathbf{w}_k) + \nabla f(\mathbf{w}_k)^T \left(-H_k^{-1}\nabla f(\mathbf{w}_k)\right) + \frac{1}{2}\left(-H_k^{-1}\nabla f(\mathbf{w}_k)\right)^T H_k \left(-H_k^{-1}\nabla f(\mathbf{w}_k)\right)\] \[= f(\mathbf{w}_k) - \nabla f(\mathbf{w}_k)^T H_k^{-1} \nabla f(\mathbf{w}_k) + \frac{1}{2}\nabla f(\mathbf{w}_k)^T \underbrace{H_k^{-T} H_k H_k^{-1}}_{= H_k^{-1}} \nabla f(\mathbf{w}_k)\]

Como \(H_k\) é simétrica (\(H_k^{-T} = H_k^{-1}\)), os dois termos quadráticos se combinam: \[q(\Delta\mathbf{w}_{\text{nt}}) = f(\mathbf{w}_k) - \frac{1}{2}\nabla f(\mathbf{w}_k)^T H_k^{-1} \nabla f(\mathbf{w}_k)\]

Portanto, a queda prevista de custo pelo modelo quadrático é dada exatamente por: \[f(\mathbf{w}_k) - q(\Delta\mathbf{w}_{\text{nt}}) = \frac{1}{2}\nabla f(\mathbf{w}_k)^T H_k^{-1} \nabla f(\mathbf{w}_k)\]

A forma quadrática \(\nabla f(\mathbf{w}_k)^T H_k^{-1} \nabla f(\mathbf{w}_k)\) surge espontaneamente no coração da otimização de segunda ordem. Para expressar essa grandeza na mesma escala dimensional do gradiente (em vez do seu quadrado), define-se o Decremento de Newton \(\lambda(\mathbf{w})\) como sua raiz quadrada: \[\lambda(\mathbf{w}) \triangleq \left( \nabla f(\mathbf{w})^T [\nabla^2 f(\mathbf{w})]^{-1} \nabla f(\mathbf{w}) \right)^{1/2}\]

Assim, a redução prometida pelo modelo expressa-se compactamente como: \[f(\mathbf{w}) - \min_{\Delta\mathbf{w}} q(\Delta\mathbf{w}) = \frac{1}{2}\lambda(\mathbf{w})^2\]

Além disso, \(\lambda(\mathbf{w})\) admite duas interpretações geométricas imediatas: 1. Norma do Gradiente na Métrica de Curvatura: Como \(H \succ 0\), \(H^{-1}\) define uma métrica Riemanniana no espaço tangente. O decremento é a norma induzida: \(\lambda(\mathbf{w}) = \|\nabla f(\mathbf{w})\|_{H^{-1}}\). 2. Comprimento do Passo de Newton: Ponderando pela Hessiana, \(\|\Delta\mathbf{w}_{\text{nt}}\|_H = (\Delta\mathbf{w}_{\text{nt}}^T H \Delta\mathbf{w}_{\text{nt}})^{1/2} = \lambda(\mathbf{w})\). 3. Critério de Parada: Em funções fortemente convexas (\(f(\mathbf{w}) - f(\mathbf{w}^\star) \le \frac{1}{2\mu}\lambda(\mathbf{w})^2\)), o algoritmo encerra o treinamento com garantia de precisão quando \(\frac{1}{2}\lambda(\mathbf{w})^2 \le \epsilon_{\text{tol}}\).

3.3 Teorema da Invariância Afim e o Contraste com o GD

Uma das propriedades mais elegantes do Método de Newton é sua Invariância Afim:

Teorema: Invariância Afim do Método de Newton (Boyd & Vandenberghe §9.5.1)

Seja \(f: \mathbb{R}^d \to \mathbb{R}\) uma função duas vezes diferenciável e considere uma mudança linear de coordenadas arbitrária dada por \(\tilde{\mathbf{w}} = A \mathbf{w}\), onde \(A \in \mathbb{R}^{d \times d}\) é uma matriz inversível. Defina a função no novo sistema de coordenadas como \(\phi(\tilde{\mathbf{w}}) \triangleq f(A^{-1}\tilde{\mathbf{w}})\).

Então, o passo de Newton \(\Delta\tilde{\mathbf{w}}_{\text{nt}}\) calculado para \(\phi\) em \(\tilde{\mathbf{w}}\) satisfaz rigorosamente: \[\Delta\tilde{\mathbf{w}}_{\text{nt}} = A \Delta\mathbf{w}_{\text{nt}}\] e o passo mapeado de volta ao espaço original recupera exatamente o passo original: \(A^{-1}\Delta\tilde{\mathbf{w}}_{\text{nt}} = \Delta\mathbf{w}_{\text{nt}}\).

Demonstração: Pela regra da cadeia multivariada, o gradiente e a Hessiana no espaço transformado são: \[\nabla_{\tilde{\mathbf{w}}} \phi(\tilde{\mathbf{w}}) = A^{-T} \nabla_{\mathbf{w}} f(\mathbf{w})\] \[\nabla_{\tilde{\mathbf{w}}}^2 \phi(\tilde{\mathbf{w}}) = A^{-T} \nabla_{\mathbf{w}}^2 f(\mathbf{w}) A^{-1}\]

Calculando o passo de Newton no novo espaço: \[\Delta\tilde{\mathbf{w}}_{\text{nt}} = -[\nabla_{\tilde{\mathbf{w}}}^2 \phi(\tilde{\mathbf{w}})]^{-1} \nabla_{\tilde{\mathbf{w}}} \phi(\tilde{\mathbf{w}}) = -\left[ A^{-T} \nabla^2 f(\mathbf{w}) A^{-1} \right]^{-1} \left( A^{-T} \nabla f(\mathbf{w}) \right)\] \[= -\left[ A \left(\nabla^2 f(\mathbf{w})\right)^{-1} A^T \right] A^{-T} \nabla f(\mathbf{w}) = -A [\nabla^2 f(\mathbf{w})]^{-1} \nabla f(\mathbf{w}) = A \Delta\mathbf{w}_{\text{nt}} \quad \blacksquare\]

Mapeando de volta para o espaço original de parâmetros \(\mathbf{w} = A^{-1}\tilde{\mathbf{w}}\): \[\Delta\mathbf{w} = A^{-1} \Delta\tilde{\mathbf{w}}_{\text{nt}} = A^{-1}(A \Delta\mathbf{w}_{\text{nt}}) = \Delta\mathbf{w}_{\text{nt}}\]

3.3.1 Por que o Gradiente Descendente Falha na Invariância Afim?

Vejamos agora o que acontece quando executamos o Gradiente Descendente clássico no espaço transformado \(\tilde{\mathbf{w}}\): \[\Delta\tilde{\mathbf{w}}_{\text{GD}} = -\alpha \nabla_{\tilde{\mathbf{w}}} \phi(\tilde{\mathbf{w}}) = -\alpha A^{-T} \nabla_{\mathbf{w}} f(\mathbf{w})\]

Mapeando esse passo de volta para o espaço original \(\mathbf{w} = A^{-1}\tilde{\mathbf{w}}\): \[\Delta\mathbf{w}_{\text{equiv}} = A^{-1} \Delta\tilde{\mathbf{w}}_{\text{GD}} = -\alpha A^{-1} A^{-T} \nabla_{\mathbf{w}} f(\mathbf{w}) = -\alpha (A^T A)^{-1} \nabla_{\mathbf{w}} f(\mathbf{w})\]

Observe o resultado: o passo equivalente no espaço original não é \(-\alpha \nabla f(\mathbf{w})\), mas sim \(-\alpha (A^T A)^{-1} \nabla f(\mathbf{w})\)! * A equivalência \(\Delta\mathbf{w}_{\text{equiv}} = \Delta\mathbf{w}_{\text{GD}}\) ocorre se e somente se \((A^T A)^{-1} = I \iff A^T A = I\), ou seja, se \(A\) for uma matriz ortogonal (rotações ou reflexões puras). * Se a transformação envolver qualquer mudança de escala entre variáveis (por exemplo, \(A = \text{diag}(100, 1)\)), \((A^T A)^{-1} \neq I\), e a direção seguida pelo GD torna-se completamente distorcida! O GD depende criticamente das unidades de medida dos dados.

3.3.2 Por Que a Invariância Afim é Crucial no Aprendizado de Máquina?

A invariância afim não é mera elegância formal; ela resolve quatro dos maiores desafios práticos da otimização em Machine Learning:

O Fim da Dependência de Normalização de Dados (StandardScaler): No Gradiente Descendente, se treinamos um modelo com features em escalas díspares — por exemplo, a idade em anos (\(10 \text{ a } 80\)) e a renda em centavos (\(10^6 \text{ a } 10^8\)) —, o número de condição \(\kappa = \lambda_{\max}/\lambda_{\min}\) explode para \(10^{12}\). O GD exige uma taxa de aprendizado microscópica \(\alpha \le 2/L\) para não divergir na direção da renda, o que faz a convergência ao longo do eixo da idade praticamente congelar. Por isso, a padronização via z-score (StandardScaler) é uma muleta obrigatória para o GD. Para o Método de Newton, a normalização é algebricamente supérflua: medir a renda em centavos, reais ou milhões produz exatamente a mesma sequência de parâmetros no espaço original, convergindo no mesmo número de passos!
Imunidade a Correlações e Multicolinearidade: Quando atributos são correlacionados (como metragem quadrada e número de quartos no dataset California Housing), as curvas de nível da perda tornam-se elipses rotacionadas oblíquas. O GD perpendicular às curvas de nível sofre ziguezague severo. Newton calcula os termos cruzados fora da diagonal \(\frac{\partial^2 f}{\partial w_i \partial w_j}\) e elimina o efeito da correlação instantaneamente.
Geometria Intrínseca vs. Geometria Arbitrária de Coordenadas: O vetor gradiente \(\nabla f\) só aponta para a “descida mais íngreme” porque adotamos arbitrariamente o produto interno euclidiano padrão \(\langle \mathbf{u}, \mathbf{v} \rangle = \mathbf{u}^T \mathbf{v}\). Se rotacionarmos ou esticarmos o sistema de coordenadas, essa noção geométrica se quebra. A Hessiana define a métrica Riemanniana intrínseca da superfície de perda: Newton não segue a descida mais íngreme do sistema de eixos do usuário, mas sim o gradiente natural intrínseco da função!
A Ponte Conceitual para o Precondicionamento: Se a invariância afim completa de Newton é o ideal teórico supremo mas custa impeditivos \(\mathcal{O}(d^3)\), e o GD tem custo linear \(\mathcal{O}(d)\) mas possui zero invariância, surge a pergunta que moldou a otimização em Deep Learning: podemos projetar um algoritmo que custe \(\mathcal{O}(d)\) e seja invariante ao menos sob mudanças de escala axiais (matrizes diagonais)? Essa é a motivação direta do Precondicionamento Diagonal e de métodos como AdaGrad e RMSProp.

Além da invariância, sob condições brandas (Hessiana Lipschitz contínua e fortemente convexa), Newton exibe Convergência Quadrática Local: \[\|\mathbf{w}_{k+1} - \mathbf{w}^\star\| \le M \|\mathbf{w}_k - \mathbf{w}^\star\|^2\] Uma vez que o modelo entra no raio de atração quadrática, o número de casas decimais de precisão exata dobra a cada iteração (ex.: erro \(10^{-2} \to 10^{-4} \to 10^{-8} \to 10^{-16}\)).

3.4 O Passo de Newton e a Invariância Afim

O Salto em Formas Quadráticas

Seja \(f(\mathbf{w}) = \frac{1}{2}\mathbf{w}^T A \mathbf{w} - \mathbf{b}^T \mathbf{w}\) com \(A \succ 0\). Quantas iterações o Método de Newton exige para encontrar a solução exata \(\mathbf{w}^\star = A^{-1}\mathbf{b}\) partindo de um \(\mathbf{w}_0\) arbitrário? Qual é o papel geométrico do decremento de Newton \(\lambda(\mathbf{w})^2\)?

Propriedades de Segunda Ordem

Julgue V ou F — a questão só conta se acertar os 4 itens:

□ Se \(f\) for uma forma quadrática estritamente convexa, a expansão de Taylor de segunda ordem é exata, tornando o resíduo de ordem superior identicamente nulo.
□ O passo de Newton \(\Delta\mathbf{w}_{\text{nt}} = -H^{-1}\nabla f\) tem unidade dimensional compatível com o vetor de parâmetros \(\mathbf{w}\).
□ Se reescalonarmos os dados transformando \(\mathbf{w} \to c \mathbf{w}\) com \(c > 0\), o passo do Gradiente Descendente clássico é multiplicado por \(1/c\), preservando a mesma trajetória geométrica.
□ O decremento de Newton \(\lambda(\mathbf{w})^2 = \nabla f(\mathbf{w})^T H^{-1} \nabla f(\mathbf{w})\) é estritamente não-negativo para qualquer função convexa e anula-se se e somente se \(\nabla f(\mathbf{w}) = \mathbf{0}\).

4 Bloco 2: As Três Patologias de Newton em Aprendizado de Máquina

4.1 Por Que Redes Neurais Não São Treinadas com Newton Puro?

Diante da convergência quadrática e da imunidade a escalas, seria tentador decretar que o Método de Newton deveria substituir todos os otimizadores existentes. No entanto, em Aprendizado de Máquina moderno, o Método de Newton puro é quase inutilizável em sua forma bruta.

Existem três barreiras teóricas e práticas intransponíveis:

4.1.1 Patologia 1: O Muro Computacional \(\mathcal{O}(d^3)\) e de Memória \(\mathcal{O}(d^2)\)

Em problemas reais de aprendizado supervisionado, o número de parâmetros \(d\) varia de dezenas de milhares (modelos lineares e convolucionais leves) a centenas de bilhões (Large Language Models): 1. Armazenamento da Hessiana (\(\mathcal{O}(d^2)\)): Uma rede modesta com \(d = 10^6\) parâmetros exige uma matriz Hessiana de \(10^{12}\) elementos em ponto flutuante. Em precisão float32 (4 bytes por float), armazenar uma única matriz Hessiana requer \(4\) Terabytes de memória RAM! Para um modelo de 70 bilhões de parâmetros (como Llama-3-70B), seriam necessários cerca de \(20\) Zetabytes — mais do que toda a RAM física existente em supercomputadores do planeta. 2. Inversão do Sistema Linear (\(\mathcal{O}(d^3)\)): Resolver o sistema linear \(H \Delta\mathbf{w} = -\mathbf{g}\) via Eliminação Gaussiana ou Decomposição de Cholesky consome \(\approx \frac{1}{3}d^3\) operações aritméticas (FLOPs). Para \(d = 10^6\), isso equivale a \(\approx 3{,}3 \times 10^{17}\) FLOPs por passo de atualização. Enquanto um passo de SGD consome milissegundos, uma única iteração de Newton levaria dias.

4.1.2 Patologia 2: A Armadilha dos Pontos de Sela e Não-Convexidade

O modelo quadrático de Taylor assume tacitamente que \(H_k \succ 0\) (curvatura positiva em todas as direções). Contudo, funções de perda de redes neurais profundas são altamente não-convexas: * Em regiões onde a Hessiana é indefinida (possui autovalores positivos e negativos), impor \(\nabla q(\Delta\mathbf{w}) = \mathbf{0}\) encontra o ponto estacionário do modelo quadrático, que pode ser um ponto de sela ou até um máximo local! * Se um autovalor for negativo (\(\lambda_i < 0\)), o passo de Newton ao longo desse autovetor move-se no sentido de maximizar a função (\(\mathbf{g}^T \Delta\mathbf{w} > 0\)), arremessando os pesos montanha acima. * Em espaços de alta dimensão, Dauphin et al. (2014) provaram que pontos de sela proliferam exponencialmente em relação aos mínimos locais, tornando o método de Newton um “ímã de pontos de sela”.

4.1.3 Patologia 3: Incompatibilidade com Ruído Estocástico

Calcular a Hessiana exata sobre o dataset completo de tamanho \(N\) custa \(\mathcal{O}(Nd^2)\). Se tentarmos estimar a Hessiana sobre um mini-batch de tamanho \(B \ll N\): \[\hat{H} = \frac{1}{B}\sum_{i \in \mathcal{B}} \nabla^2 f_i(\mathbf{w})\] o posto dessa matriz amostral é no máximo \(B\). Para \(B < d\), a matriz \(\hat{H}\) é estritamente singular (posto incompleto), impossibilitando sua inversão direta! Mesmo que \(B \ge d\), os autovalores menores de \(\hat{H}\) são dominados por ruído amostral violento: ao inverter a matriz, o inverso dos autovalores ruidosos (\(1/\hat{\lambda}_i\)) amplifica o ruído estocástico por ordens de magnitude.

4.2 O Remédio Clássico: Newton Amortecido e Regularizado

A engenharia numérica clássica atenua essas patologias através da Regularização de Levenberg-Marquardt (também conhecida como método de Newton amortecido ou trust-region): \[(H_k + \lambda_k I) \Delta\mathbf{w} = -\nabla f(\mathbf{w}_k)\] onde \(\lambda_k > 0\) é um parâmetro de amortecimento escalar adaptativo.

Pelo Teorema Espectral (\(H_k = Q \Lambda Q^T\)), a matriz modificada tem decomposição: \[H_k + \lambda_k I = Q (\Lambda + \lambda_k I) Q^T\] Os novos autovalores são \(\lambda_i + \lambda_k\). Escolhendo \(\lambda_k > |\min(0, \lambda_{\min})|\), garantimos que todos os autovalores tornem-se estritamente positivos (\(\lambda_i + \lambda_k > 0\)), restaurando a descida estrita e a invertibilidade.

Além disso, observe o comportamento assintótico: * Se \(\lambda_k \to 0\): recuperamos o Método de Newton Puro. * Se \(\lambda_k \to \infty\): a identidade domina (\((H_k + \lambda_k I)^{-1} \approx \frac{1}{\lambda_k}I\)), e a atualização aproxima-se do Gradiente Descendente Euclidiano com taxa de aprendizado \(\alpha = 1/\lambda_k\).

Embora Levenberg-Marquardt cure a patologia dos pontos de sela, ele não resolve o muro computacional \(\mathcal{O}(d^3)\).

4.3 Patologias de Newton em Alta Dimensão

O Salto no Ponto de Sela

Considere a função hiperbólica \(f(w_1, w_2) = w_1^2 - w_2^2\), que possui um ponto de sela em \((0, 0)\). Calcule o passo de Newton a partir do ponto inicial \(\mathbf{w}_0 = (1, 1)^T\). Para onde o algoritmo se desloca? O que ocorreria se o ponto inicial fosse \((0, 1)^T\)?

Escala Computacional de Newton

Julgue V ou F — a questão só conta se acertar os 4 itens:

□ Em um ponto de sela onde a Hessiana possui autovalores estritamente negativos, a direção \(-\nabla^2 f(\mathbf{w})^{-1}\nabla f(\mathbf{w})\) pode apontar no sentido de crescimento da perda (\(\nabla f^T \Delta\mathbf{w} > 0\)).
□ A fatoração de Cholesky de uma matriz Hessiana \(d \times d\) requer complexidade temporal \(\mathcal{O}(d^2)\) e consumo de memória linear \(\mathcal{O}(d)\).
□ A regularização de Levenberg-Marquardt \((H + \lambda I)^{-1}\nabla f\) com \(\lambda > |\min_i \lambda_i|\) garante que a matriz invertida seja simétrica positiva definida.
□ Em modelos modernos com 70 bilhões de parâmetros (LLMs), o armazenamento de uma única matriz Hessiana em precisão de 32 bits exigiria menos de 1 Terabyte de memória.

5 Bloco 3: A Geometria do Precondicionamento e a Matriz Diagonal

5.1 Mudança Métrica de Variáveis e a Origem de \(P^{-1/2}\)

O dilema é evidente: * O Gradiente Descendente custa apenas \(\mathcal{O}(d)\), mas sofre em superfícies mal-condicionadas com ziguezagues infinitos. * O Método de Newton elimina o mau condicionamento e equaliza todas as direções, mas custa impeditivos \(\mathcal{O}(d^3)\).

Como capturar os benefícios de escala de Newton sem pagar a penalidade cúbica? A resposta matemática reside na teoria do Precondicionamento.

5.1.1 O Objetivo Geométrico: Esfericizar o Terreno

No bloco anterior, vimos que sob uma mudança linear de coordenadas \(\tilde{\mathbf{w}} = M \mathbf{w}\) (com \(M\) inversível), a Hessiana no espaço transformado deforma-se segundo: \[\nabla_{\tilde{\mathbf{w}}}^2 \phi = M^{-T} H M^{-1}\]

O que desejamos para que o Gradiente Descendente convirja em linha reta, sem oscilações transversais? Desejamos que no novo espaço \(\tilde{\mathbf{w}}\) as curvas de nível sejam perfeitamente esféricas — isto é, que a Hessiana transformada seja a matriz identidade: \[M^{-T} H M^{-1} \approx I \iff H \approx M^T M\]

Se buscarmos uma transformação simétrica (\(M^T = M\)), essa condição exige que: \[M^2 \approx H \implies M \approx H^{1/2}\]

Portanto, se escolhermos uma matriz simétrica estritamente positiva definida \(P \succ 0\) que sirva como aproximação da curvatura (\(P \approx H\)), pelo Teorema Espectral (Aula 4) existe uma única raiz quadrada simétrica \(P^{1/2} \succ 0\) que satisfaz \(P^{1/2} P^{1/2} = P\).

A mudança de variáveis natural para esfericizar o terreno é: \[\tilde{\mathbf{w}} \triangleq P^{1/2} \mathbf{w} \iff \mathbf{w} = P^{-1/2} \tilde{\mathbf{w}}\]

5.1.2 Por que o fator \(P^{-1/2}\) aparece no gradiente e no passo?

A Regra da Cadeia no Espaço Transformado: Definindo a função de custo na nova coordenada como \(\phi(\tilde{\mathbf{w}}) \triangleq f(P^{-1/2} \tilde{\mathbf{w}})\), a regra da cadeia vetorial estabelece que o gradiente em relação a \(\tilde{\mathbf{w}}\) é: \[\nabla_{\tilde{\mathbf{w}}} \phi(\tilde{\mathbf{w}}) = (P^{-1/2})^T \nabla_{\mathbf{w}} f(\mathbf{w}) = P^{-1/2} \nabla_{\mathbf{w}} f(\mathbf{w})\] (Como \(P\) e sua inversa são simétricas, \((P^{-1/2})^T = P^{-1/2}\)). O primeiro fator \(P^{-1/2}\) surge da projeção da inclinação no espaço reescalonado.
O Passo de Gradiente Descendente no Espaço Esférico: No espaço \(\tilde{\mathbf{w}}\), as elipses foram arredondadas. Damos um passo euclidiano padrão com taxa \(\alpha\): \[\Delta\tilde{\mathbf{w}} = -\alpha \nabla_{\tilde{\mathbf{w}}} \phi(\tilde{\mathbf{w}}) = -\alpha P^{-1/2} \nabla_{\mathbf{w}} f(\mathbf{w})\]
A Conversão de Volta para o Espaço Físico Original: Para saber como atualizar os parâmetros reais \(\mathbf{w}\), aplicamos a relação inversa \(\mathbf{w} = P^{-1/2} \tilde{\mathbf{w}}\): \[\Delta\mathbf{w} = P^{-1/2} \Delta\tilde{\mathbf{w}} = P^{-1/2} \left( -\alpha P^{-1/2} \nabla_{\mathbf{w}} f(\mathbf{w}) \right) = -\alpha \underbrace{P^{-1/2} P^{-1/2}}_{= P^{-1}} \nabla_{\mathbf{w}} f(\mathbf{w})\]

Os dois fatores \(P^{-1/2}\) se fundem naturalmente: o primeiro decorre da regra da cadeia ao medir a inclinação no espaço esfericizado; o segundo decorre da mudança de base inversa ao trazer o deslocamento de volta ao espaço original!

A atualização resultante é a fórmula universal do Gradiente Descendente Precondicionado: \[\mathbf{w}_{k+1} = \mathbf{w}_k - \alpha P^{-1} \nabla f(\mathbf{w}_k)\] * Se \(P = I\): recuperamos o Gradiente Descendente euclidiano padrão (\(\mathcal{O}(d)\)). * Se \(P = \nabla^2 f(\mathbf{w}_k)\) e \(\alpha = 1\): recuperamos o Método de Newton Puro (\(\mathcal{O}(d^3)\)). * Se \(P = D\) (diagonal): obtemos passos desacoplados por coordenada em tempo linear (\(\mathcal{O}(d)\))!

5.2 A Aproximação Diagonal: O Ponto Doce de \(\mathcal{O}(d)\)

A grande sacada computacional é: e se restringirmos a matriz de precondicionamento \(P\) a ser estritamente diagonal? \[D_k = \begin{bmatrix} s_{1, k} & 0 & \dots & 0 \\ 0 & s_{2, k} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & s_{d, k} \end{bmatrix} \succ 0 \quad (s_{i, k} > 0)\]

As consequências práticas são revolucionárias: 1. Inversão Trivial e Instantânea: A inversa de uma matriz diagonal não requer Cholesky nem fatoração: basta calcular o recíproco escalar de cada elemento: \[D_k^{-1} = \text{diag}\left(\frac{1}{s_{1, k}}, \frac{1}{s_{2, k}}, \dots, \frac{1}{s_{d, k}}\right)\] Complexidade temporal de inversão: exatamente \(d\) divisões escalares (\(\mathcal{O}(d)\))! 2. Armazenamento Vetorial: Armazenar \(D_k\) consome exatamente um vetor de dimensão \(d\) (\(\mathcal{O}(d)\) em memória RAM). 3. Desacoplamento Completo por Coordenada: A atualização matricial \(\mathbf{w}_{k+1} = \mathbf{w}_k - \alpha D_k^{-1} \nabla f(\mathbf{w}_k)\) quebra-se em \(d\) regras unidimensionais totalmente independentes: \[w_{i, k+1} = w_{i, k} - \alpha \frac{g_{i, k}}{s_{i, k}}, \quad \text{para cada } i = 1, \dots, d\]

Cada parâmetro \(w_i\) recebe sua própria taxa de aprendizado efetiva adaptativa: \[\alpha_{i, k}^{\text{eff}} \triangleq \frac{\alpha}{s_{i, k}}\] Se a coordenada \(i\) possuir alta curvatura (\(s_i\) grande), seu passo é reduzido para evitar instabilidade. Se a coordenada \(i\) for suave (\(s_i\) pequeno), seu passo é amplificado para acelerar o progresso!

5.3 Precondicionamento Diagonal

O Desacoplamento Matricial

Mostre algebricamente por que a multiplicação matriz-vetor \(D^{-1}\mathbf{g}\) com \(D = \text{diag}(s_1, \dots, s_d)\) possui custo computacional linear \(\mathcal{O}(d)\). Por que essa operação pode ser distribuída perfeitamente em threads paralelas em uma GPU?

Propriedades do Precondicionamento

Julgue V ou F — a questão só conta se acertar os 4 itens:

□ O precondicionamento diagonal equivale a aplicar uma mudança linear de variáveis onde cada coordenada \(w_i\) é reescalonada por \(\sqrt{s_i}\) independentemente.
□ Uma matriz de precondicionamento diagonal é capaz de rotacionar os eixos de coordenadas para cancelar covariâncias cruzadas não-diagonais da Hessiana.
□ Se escolhermos \(s_i = \frac{\partial^2 f}{\partial w_i^2}\), o passo por coordenada recupera o método de Newton unidimensional aplicado a cada parâmetro isoladamente.
□ O custo de memória de armazenar uma matriz de precondicionamento diagonal cresce quadraticamente com a dimensão do espaço de parâmetros (\(\mathcal{O}(d^2)\)).

6 Bloco 4: Escalas Adaptativas na Prática: AdaGrad e RMSProp

6.1 O Contexto do SGD e Por Que Evitar Segundas Derivadas

Estabelecemos que a regra desacoplada \(w_{i, k+1} = w_{i, k} - \frac{\alpha}{s_{i, k}} g_{i, k}\) custa \(\mathcal{O}(d)\). Contudo, resta um desafio fundamental: de onde extrair os coeficientes de escala \(s_{i, k}\) na prática do Aprendizado de Máquina?

6.1.1 O Cenário Real: Otimização Estocástica (SGD)

No aprendizado moderno (e em redes neurais profundas), quase nunca temos acesso à perda sobre o conjunto de dados completo de uma só vez. Operamos com o Gradiente Descendente Estocástico (SGD) sobre pequenos lotes de dados (mini-batches \(B_t\) de tamanho 32, 64 ou 256). O gradiente computado \(\mathbf{g}_t = \nabla f_{B_t}(\mathbf{w}_t)\) é uma variável aleatória ruidosa.

6.1.2 A Extrema Instabilidade das Estimativas de 2ª Ordem no SGD

Por que simplesmente não calcular a diagonal da Hessiana amostral \(\text{diag}(\nabla^2 f_{B_t}(\mathbf{w}))\) a cada iteração? 1. Ruído e Variância Amostral Gigantesca: Em pequenos lotes, as segundas derivadas sofrem de uma variância amostral ordens de magnitude superior à do gradiente. A curvatura de um mini-batch raramente reflete a geometria da perda populacional. 2. Indefinição e Curvatura Negativa Espúria: Em terrenos não-convexos, o ruído amostral frequentemente gera derivadas parciais de 2ª ordem negativas na diagonal. Se \(s_{i, t} < 0\), o passo precondicionado apontaria na direção de subida da perda! 3. Custo Computacional Proibitivo: Obter segundas derivadas exige passes de autograd de ordem superior, degradando o throughput computacional em GPUs.

6.1.3 A Solução: Proxy de Curvatura Baseado em 1ª Ordem

A genialidade de algoritmos como AdaGrad (Duchi et al., 2011) e RMSProp (Hinton, 2012) foi perceber que eles foram criados especificamente dentro do contexto de SGD.

Em vez de arriscar estimativas de 2ª ordem altamente instáveis, eles utilizam a história acumulada dos próprios gradientes estocásticos de 1ª ordem (\(g_{t, i}^2\)) como uma estimativa empírica estável e barata da escala local: * Se ao longo de várias iterações uma coordenada \(i\) exibe gradientes de grande magnitude (\(|g_{t, i}| \gg 0\)), isso revela que a função tem inclinação íngreme ou alta oscilação estocástica nessa direção \(\to\) \(s_{i}\) deve ser grande para atenuar o passo e garantir estabilidade. * Se uma coordenada recebe gradientes minúsculos ou esparsos na maior parte do tempo (como um parâmetro associado a uma palavra rara em NLP) \(\to\) \(s_i\) deve ser pequeno para permitir passos largos quando o gradiente finalmente ocorrer.

6.1.4 1. Otimizador AdaGrad (Duchi, Hazan & Singer, 2011)

O AdaGrad (Adaptive Gradient Algorithm) define o fator de precondicionamento como a raiz quadrada da soma de todos os gradientes quadrados observados no passado: \[G_{t, i} = G_{t-1, i} + g_{t, i}^2 = \sum_{\tau=1}^t g_{\tau, i}^2\]

A regra de atualização vetorial é: \[\mathbf{w}_{t+1} = \mathbf{w}_t - \frac{\alpha}{\sqrt{\mathbf{G}_t} + \epsilon} \odot \mathbf{g}_t\] onde \(\odot\) denota produto de Hadamard elemento a elemento e \(\epsilon > 0\) (ex.: \(10^{-8}\)) é uma constante minúscula para evitar divisão por zero.

O Triunfo do AdaGrad: Em dados com alta esparsidade (sistemas de recomendação, modelos de linguagem clássicos), o AdaGrad brilha: atributos raros mantêm \(G_{t, i} \approx 0\), recebendo taxas de aprendizado muito mais agressivas do que atributos frequentes.

A Patologia Fatal do AdaGrad: Como \(g_{\tau, i}^2 \ge 0\), a sequência \(G_{t, i}\) é estritamente não-decrescente: \[G_{t, i} \ge G_{t-1, i} \implies \lim_{t \to \infty} G_{t, i} = \infty\] Consequentemente, a taxa de aprendizado efetiva cai continuamente para zero: \[\lim_{t \to \infty} \frac{\alpha}{\sqrt{G_{t, i}} + \epsilon} = 0\] Em redes neurais profundas com milhares de épocas, o AdaGrad acumula tanta energia gradiente em fases iniciais que a taxa de aprendizado efetiva colapsa antes que o modelo chegue perto do minimizador: o treinamento congela prematuramente!

6.2 2. Otimizador RMSProp (Geoffrey Hinton, 2012)

Em suas famosas aulas de rede neural na plataforma Coursera (Aula 6e, 2012), Geoffrey Hinton propôs a cura definitiva para o congelamento do AdaGrad: descartar a história remota e reter apenas a variância local recente.

Em vez de somar todos os gradientes passados até o infinito, o RMSProp (Root Mean Square Propagation) utiliza uma Média Móvel Exponencial (EMA) dos gradientes ao quadrado: \[v_{t, i} = \beta_2 v_{t-1, i} + (1 - \beta_2) g_{t, i}^2\] onde \(\beta_2 \in (0, 1)\) é o fator de decaimento exponencial (tipicamente fixado em \(\beta_2 = 0{,}9\) ou \(0{,}99\)).

A regra de atualização de parâmetros é: \[\mathbf{w}_{t+1} = \mathbf{w}_t - \frac{\alpha}{\sqrt{\mathbf{v}_t} + \epsilon} \odot \mathbf{g}_t\]

Propriedades Notáveis do RMSProp: 1. Memória com Janela Móvel Eficaz: Expandindo a recursão \(v_t = (1-\beta_2)\sum_{k=0}^{t-1} \beta_2^k g_{t-k}^2\), percebe-se que as iterações passadas têm peso decaindo geometricamente. A janela temporal de memória efetiva abrange aproximadamente: \[\tau_{\text{mem}} \approx \frac{1}{1 - \beta_2} \text{ iterações}\] Para \(\beta_2 = 0{,}9\), o otimizador olha para as últimas \(\approx 10\) iterações; para \(\beta_2 = 0{,}99\), para as últimas \(\approx 100\) iterações. 2. Taxa Adaptativa Não-Saturante: Se o otimizador atravessar uma região íngreme e posteriormente entrar em um vale suave e plano onde os gradientes diminuem, o acumulador \(v_t\) decai, fazendo a taxa efetiva de aprendizado \(\alpha / \sqrt{v_t}\) subir novamente! O modelo nunca congela. 3. Normalização por Desvio Padrão: A raiz \(\sqrt{v_{t, i}}\) estima o desvio padrão quadrático médio (root mean square) do gradiente recente. O passo resultante \(\frac{g_t}{\sqrt{v_t}}\) tem magnitude aproximadamente unitária em termos de escala, transformando a atualização em algo próximo de um passo de sinal calibrado.

6.3 Dinâmica Comparada: AdaGrad vs. RMSProp

Avaliamos abaixo a trajetória dos algoritmos em uma bacia com número de condição \(\kappa = 100\) e a evolução das respectivas taxas efetivas de aprendizado \(\alpha_t^{\text{eff}}\):

6.4 AdaGrad vs. RMSProp

O Destino dos Otimizadores

Por que o AdaGrad é considerado o algoritmo clássico de escolha para problemas com vocabulários esparsos em Processamento de Linguagem Natural, mas falhou ao ser aplicado no treinamento de redes neurais convolucionais profundas em visão computacional? De que forma a média móvel exponencial do RMSProp sana esse impasse?

Dinâmica de Escalas Adaptativas

Julgue V ou F — a questão só conta se acertar os 4 itens:

□ No AdaGrad, a sequência de acumuladores \(G_{t, i} = \sum_{\tau=1}^t g_{\tau, i}^2\) é monotonicamente não-decrescente em \(t\).
□ O decaimento da taxa de aprendizado efetiva no AdaGrad satisfaz \(\lim_{t\to\infty} \frac{\alpha}{\sqrt{G_{t, i}} + \epsilon} = 0\) sempre que o gradiente ao longo da coordenada não for identicamente nulo.
□ No RMSProp, o fator \(\beta_2\) define a constante de tempo da memória móvel, atribuindo peso efetivo às últimas \(\approx \frac{1}{1-\beta_2}\) iterações.
□ O RMSProp substitui a necessidade de calcular gradientes estocásticos por estimativas de segunda ordem da curvatura calculadas via diferenças finitas.

7 Fechamento

7.1 Retomando as 4 Perguntas

O que é o passo de Newton e por que ele é invariante? É o minimizador do modelo quadrático de Taylor local de 2ª ordem (\(\Delta\mathbf{w}_{\text{nt}} = -H^{-1}\nabla f\)). Ele possui convergência quadrática local e é invariante sob qualquer transformação linear afim de variáveis (\(\tilde{\mathbf{w}} = A \mathbf{w}\)), tornando-o imune a escalas heterogêneas dos dados.
Por que o Método de Newton puro colapsa em larga escala em ML? Pelo custo cúbico \(\mathcal{O}(d^3)\) para inverter a Hessiana, custo quadrático \(\mathcal{O}(d^2)\) de memória RAM (impraticável para milhões/bilhões de parâmetros) e pela atração perigosa por pontos de sela e máximos locais quando a Hessiana não é positiva definida.
Como a teoria do precondicionamento diagonal resolve esse gargalo? Ao restringir a matriz métrica \(P\) a ser uma matriz diagonal positiva \(D = \text{diag}(s_1, \dots, s_d)\), a inversão matricial reduz-se a \(d\) divisões escalares triviais (\(\mathcal{O}(d)\) em tempo e memória), desacoplando completamente a atualização em regras independentes por coordenada.
Como o AdaGrad e o RMSProp constroem taxas adaptativas? O AdaGrad acumula os quadrados históricos de todas as primeiras derivadas (\(G_t = \sum g^2\)), beneficiando dados esparsos mas congelando prematuramente. O RMSProp introduz a média móvel exponencial (\(v_t = \beta_2 v_{t-1} + (1-\beta_2)g^2\)), permitindo que a taxa de aprendizado se adapte continuamente à variância local sem nunca saturar.

7.2 O Que Fica em Aberto

O RMSProp representou um salto gigantesco: ele calibra de forma autônoma a escala de atualização de cada parâmetro do modelo, garantindo que coordenadas suaves avancem com vigor enquanto coordenadas íngremes sejam contidas.

Contudo, repare no que o RMSProp não faz: * A atualização do RMSProp depende unicamente do gradiente instantâneo \(\mathbf{g}_t\) da iteração corrente (normalizado pela raiz da variância recente \(\sqrt{v_t}\)). * Se o gradiente estocástico sofrer de ruído pontual ou se o relevo formar um desfiladeiro com inclinação transversal mista, o RMSProp continua suscetível a ziguezaguear a cada iteração, pois não possui memória direcional nem inércia temporal. * Em termos da física clássica: o RMSProp ajustou o atrito individual de cada patinador, mas ele ainda não possui massa nem quantidade de movimento!

7.3 Ponte para a Aula 12: Inércia Mecânica e a Síntese do Adam

Como dotar o otimizador de memória direcional persistente para atravessar ravinas estreitas sem oscilar lateralmente?

Na física clássica, uma esfera de massa \(m\) rolando morro abaixo acumula velocidade na direção persistente do vale: solavancos e ruídos transversais são filtrados pela sua inércia mecânica.

Na Aula 12: Momento, Curvatura e Métodos Acelerados, investigaremos a dinâmica espectral do Momento de Polyak (Heavy-Ball) e do Gradiente Acelerado de Nesterov (NAG).

E, coroando o Bloco 3, realizaremos a grande síntese da otimização moderna: a fusão do Primeiro Momento com Inércia (Polyak) com o Segundo Momento Adaptativo (RMSProp), dando origem ao algoritmo hegemônico do aprendizado profundo contemporâneo: o Adam (Adaptive Moment Estimation) e sua correção AdamW.

Exercícios Soluções