Aula 8: Otimização Irrestrita e Descida do Gradiente

Otimização e Álgebra Linear para Machine Learning

Slides Lista de aulas

1 Revisão e Introdução

Na Aula 7, resolvemos a grande dúvida teórica deixada pelo cálculo multivariado da Aula 6: quando encontramos um ponto de gradiente nulo \(\nabla f(\mathbf{x}) = \mathbf{0}\), como saber se atingimos um mínimo, um máximo ou um ponto de sela?

Provamos que a resposta reside na convexidade e na matriz Hessiana: 1. Se a função for convexa em todo o domínio (\(\nabla^2 f(\mathbf{x}) \succeq 0\)), a aproximação linear de primeira ordem é uma cota inferior global: \[f(\mathbf{y}) \ge f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y} - \mathbf{x})\] 2. Em qualquer ponto crítico \(\mathbf{x}^\star\) onde \(\nabla f(\mathbf{x}^\star) = \mathbf{0}\), essa desigualdade colapsa imediatamente em \(f(\mathbf{y}) \ge f(\mathbf{x}^\star)\) para todo \(\mathbf{y}\). Portanto, sob convexidade, todo ponto crítico é um mínimo global. 3. Na regressão linear de mínimos quadrados, a perda \(L(\boldsymbol{\beta}) = \|X\boldsymbol{\beta} - \mathbf{y}\|^2\) tem Hessiana constante \(\nabla^2 L = 2 X^T X \succeq 0\), sendo sempre convexa. Se \(X\) tiver posto coluna completo (\(rk(X) = d\)), então \(X^T X \succ 0\), a perda é estritamente convexa e o minimizador é único, dado analiticamente pelas equações normais: \[\hat{\boldsymbol{\beta}} = (X^T X)^{-1} X^T \mathbf{y}\]

Contudo, a Aula 7 encerrou com uma provocação prática crucial: saber que existe um único mínimo global não nos diz como chegar até ele quando a inversão direta de \((X^T X)\) é inviável, nem como otimizar perdas que não admitem solução em forma fechada.

1.1 O Dilema Numérico no California Housing (Parte 1: Os Sintomas Visuais)

Para sentir na pele por que a otimização de primeira ordem exige fundamentação matemática rigorosa, realizamos um experimento no California Housing com \(N = 20.640\) distritos e \(d = 4\) atributos (MedInc, HouseAge, AveRooms, AveBedrms).

A perda de mínimos quadrados média é: \[L(\boldsymbol{\beta}) = \frac{1}{2N}\|X\boldsymbol{\beta} - \mathbf{y}\|_2^2 \implies \nabla L(\boldsymbol{\beta}) = \frac{1}{N}X^T(X\boldsymbol{\beta} - \mathbf{y})\]

Pelas equações normais da Aula 3, encontramos a solução exata \(\boldsymbol{\beta}^\star = (X^TX)^{-1}X^T\mathbf{y}\) em meros \(0{,}001\) segundos, obtendo a perda ótima \(L^\star \approx 0{,}263\).

Porém, ao tentar resolver esse mesmo problema via Descida do Gradiente partindo da origem \(\boldsymbol{\beta}_0 = \mathbf{0}\): - Se escolhermos um passo ligeiramente agressivo \(\alpha = 2{,}8 \cdot 10^{-3}\) (acima do limite teórico \(\alpha_{\text{crit}} = \frac{2}{\lambda_{\max}} \approx 2{,}35 \cdot 10^{-3}\)), a perda sofre uma divergência exponencial catastrófica, multiplicando o erro a cada iteração e explodindo para o infinito. - Se recuarmos para um passo aparentemente “seguro” \(\alpha = 1{,}5 \cdot 10^{-3}\), a perda cai timidamente nos primeiros passos e entra em estagnação quase absoluta, estacionando em \(\approx 3{,}75\) após centenas de iterações — paralisada no eixo de menor curvatura (\(\lambda_{\min} \approx 0{,}0362\)) a anos-luz do valor ótimo.

A causa desse comportamento aberrante não é um bug de programação, mas um fenômeno puramente algébrico e espectral:

1. Disparidade Brutal de Escalas: Os atributos físicos possuem grandezas incomparáveis:
   • MedInc (renda média): varia entre \(0{,}5\) e \(15\) (\(\text{média} \approx 3{,}87\), \(\sigma \approx 1{,}90\)).
   • HouseAge (idade dos imóveis): varia de \(1\) a \(52\) anos (\(\text{média} \approx 28{,}64\), \(\sigma \approx 12{,}59\)).
   • AveRooms e AveBedrms: médias de \(5{,}43\) e \(1{,}10\).
2. A Hessiana Normalizada \(\frac{1}{N}X^T X\): Como os termos da matriz de Gram envolvem produtos cruzados das colunas de \(X\), os autovalores da Hessiana \(H = \frac{1}{N}X^T X\) são severamente deformados: \[\lambda_1 = \lambda_{\min} \approx 0{,}0362, \quad \lambda_2 \approx 2{,}55, \quad \lambda_3 \approx 13{,}27, \quad \lambda_4 = \lambda_{\max} \approx 849{,}37\]
3. O Número de Condição Gigantesco: \[\kappa = \text{cond}\left(\frac{1}{N}X^T X\right) = \frac{\lambda_{\max}}{\lambda_{\min}} \approx \frac{849{,}37}{0{,}0362} \approx \mathbf{23.460{,}5}\]
4. O Conflito Inconciliável de Passo:
   • Para não divergir ao longo da direção de maior curvatura (\(\lambda_{\max}\)), provaremos que o passo é estritamente limitado por \(\alpha < \frac{2}{\lambda_{\max}} \approx 2{,}35 \cdot 10^{-3}\).
   • Com o passo agressivo \(\alpha = 2{,}8 \cdot 10^{-3} > \frac{2}{\lambda_{\max}}\), o fator de amplificação ao longo de \(\lambda_{\max}\) é \(|1 - \alpha \lambda_{\max}| \approx |1 - 2{,}38| = 1{,}38 > 1\), ejetando o algoritmo em divergência exponencial (\(L_k \to \infty\)).
   • Mas com o passo seguro \(\alpha = 1{,}5 \cdot 10^{-3}\), a taxa de contração do erro ao longo do eixo plano (\(\lambda_{\min}\)) é de míseros: \[1 - \alpha \lambda_{\min} \approx 1 - (1{,}5 \cdot 10^{-3})(0{,}0362) \approx \mathbf{0{,}999946}\] O erro no eixo plano diminui apenas \(0{,}0054\%\) por iteração! Seriam necessárias quase \(13.000\) iterações para reduzir o erro à metade.

1.2 Ideia Central: Da Álgebra Estática à Dinâmica Iterativa

A ideia central desta aula apoia-se em um princípio operacional fundamental: quando a solução analítica em forma fechada é inacessível ou computacionalmente proibitiva, substituímos a resolução de matrizes estáticas por um processo dinâmico iterativo guiado pelo vetor gradiente.

Vimos na Aula 6 que o vetor gradiente \(\nabla f(\mathbf{x})\) aponta na direção de maior taxa de subida instantânea da função. Por conseguinte, a direção oposta, \(-\nabla f(\mathbf{x})\), aponta na direção de maior descida local (steepest descent).

O algoritmo da Descida do Gradiente consiste em inicializar em um ponto arbitrário \(\mathbf{w}_0\) e dar passos sucessivos ao longo dessa direção: \[\mathbf{w}_{k+1} = \mathbf{w}_k - \alpha \nabla f(\mathbf{w}_k)\] onde \(\alpha > 0\) é o tamanho de passo ou taxa de aprendizado (learning rate).

Contudo, para operar esse mecanismo com segurança, precisamos de respostas teóricas precisas para três perguntas: 1. O que é suavidade e qual é o limite exato de \(\alpha\) para garantir que a função sempre decresça? (Lema da Descida). 2. Qual é a taxa exata de convergência e como o número de condição \(\kappa\) dita o ziguezague? (Análise Espectral de Chebyshev). 3. Como a Álgebra Linear cura esse mau condicionamento na prática? (Padronização e Pré-condicionamento).

1.3 Roteiro da Aula

1. Intuição Geométrica: A descida na neblina, as bacias elípticas e o cálculo real do vetor gradiente sob diferentes números de condição (\(\kappa = 1, 5, 20\)).
2. Bloco 1 — O Algoritmo, a Suavidade e o Tamanho de Passo: Formulação rigorosa, definição de \(L\)-suavidade, demonstração do Limitante Superior Quadrático via Teorema Fundamental do Cálculo, demonstração do Lema da Descida (\(\alpha < 2/L\)) e análise dos 5 regimes de passo.
3. Bloco 2 — A Dinâmica Espectral do Erro e a Contração de Chebyshev: Equação matricial do erro \(\mathbf{e}_{k+1} = (I - \alpha A)\mathbf{e}_k\), desacoplamento modal via Teorema Espectral e dedução da taxa de Chebyshev \(\rho^\star = \frac{\kappa - 1}{\kappa + 1}\).
4. Bloco 3 — O Diagnóstico do California Housing e a Padronização: Como \(\kappa \approx 23.460\) paralisa a convergência e como a padronização \(Z\)-score homogeneíza a Hessiana (\(\tilde{\kappa} \approx 12{,}9\)), acelerando o treinamento em mais de \(1.800\times\).
5. Bloco 4 — Além dos Mínimos Quadrados: A Regressão Logística: Formulação probabilística, perda de Entropia Cruzada Binária, derivação do gradiente \(\frac{1}{N}X^T(\hat{\mathbf{y}} - \mathbf{y})\), ausência de solução fechada e prova de estrita convexidade (\(\nabla^2 \mathcal{L} \succ 0\)).

1.4 Pausa Ativa 1: Soluções Analíticas vs. Iterativas

DicaO Preço da Inversão

Se as equações normais fornecem a solução exata \(\hat{\boldsymbol{\beta}} = (X^T X)^{-1} X^T \mathbf{y}\) em um único cálculo matricial, por que o treinamento de modelos modernos de Machine Learning com terabytes de dados recorre quase que exclusivamente a métodos iterativos de primeira ordem?

DicaV ou F: Soluções Analíticas e Primeira Ordem

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

• □ Resolver as equações normais via fatoração de Cholesky custa \(O(d^3)\) operações aritméticas, onde \(d\) é o número de atributos.
• □ A Descida do Gradiente exige a computação e armazenamento explícito da matriz Hessiana a cada passo.
• □ Em qualquer função de perda com mínimo único, dar um passo de qualquer tamanho finito na direção \(-\nabla f\) garante a diminuição da perda.
• □ Na regressão logística com perda de entropia cruzada, a condição de gradiente nulo \(\nabla \mathcal{L}(\mathbf{w}) = \mathbf{0}\) não possui solução algébrica fechada para isolar \(\mathbf{w}\).

2 Intuição — A Descida na Neblina e a Geometria das Bacias

2.1 O Alpinista Cego e a Ortogonalidade às Curvas de Nível

Para construir uma imagem mental precisa da Descida do Gradiente, imagine um alpinista perdido em uma montanha durante uma tempestade de neblina espessa. A visibilidade é nula: ele não enxerga o pico, não enxerga a base e não possui um mapa topográfico global.

Tudo o que o alpinista consegue sentir é a inclinação local do terreno sob as solas das suas botas. O vetor gradiente \(\nabla f(\mathbf{x})\) mede o vetor de maior subida. Logo, a decisão mais prudente e natural para descer a montanha é dar um passo na direção de maior declive imediato: \[\mathbf{d} = -\nabla f(\mathbf{x})\]

Como as curvas de nível de qualquer função são superfícies onde \(f(\mathbf{x}) = \text{constante}\), provamos na Aula 6 que o vetor gradiente é ortogonal às curvas de nível em qualquer ponto.

Mas aqui reside o ponto crítico: a ortogonalidade à curva de nível não significa que o gradiente aponte para o mínimo global! Ele aponta apenas para onde a função varia mais rapidamente naquele instante. O quanto essa direção coincide com a direção do mínimo depende exclusivamente da curvatura da bacia, isto é, do número de condição \(\kappa\).

2.2 O Cenário Ideal: A Bacia Isotrópica (\(\kappa = 1\))

Considere uma bacia circular perfeitamente simétrica em \(\mathbb{R}^2\): \[f(\mathbf{x}) = \frac{1}{2}(x_1^2 + x_2^2) = \frac{1}{2}\mathbf{x}^T \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \mathbf{x}\] Aqui, \(\lambda_1 = \lambda_2 = 1\), logo \(\kappa = \frac{1}{1} = 1\). O mínimo global está na origem \(\mathbf{x}^\star = (0, 0)\).

Vamos calcular o gradiente de forma explícita no ponto \(\mathbf{x}_0 = (2, 1)\): \[\nabla f(2, 1) = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \implies -\nabla f(2, 1) = \begin{bmatrix} -2 \\ -1 \end{bmatrix}\]

A direção que leva diretamente ao minimizador a partir de \(\mathbf{x}_0\) é: \[\mathbf{v}^\star = \mathbf{x}^\star - \mathbf{x}_0 = \begin{bmatrix} 0 - 2 \\ 0 - 1 \end{bmatrix} = \begin{bmatrix} -2 \\ -1 \end{bmatrix}\]

Observe que \(-\nabla f(\mathbf{x}_0)\) é exatamente paralelo a \(\mathbf{v}^\star\)! O ângulo entre a descida do gradiente e o mínimo é rigorosamente \(\mathbf{0^\circ}\). Se adotarmos o passo \(\alpha = 1/\lambda = 1\): \[\mathbf{x}_1 = \mathbf{x}_0 - 1 \cdot \nabla f(\mathbf{x}_0) = \begin{bmatrix} 2 \\ 1 \end{bmatrix} - \begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} = \mathbf{x}^\star\] O algoritmo atinge o mínimo global em um único passo!

2.3 A Bacia Deformada: O Desvio Angular (\(\kappa = 10\))

Agora, deformemos a tigela esticando-a na direção de \(x_2\) por um fator de curvatura \(\gamma = 10\): \[f(\mathbf{x}) = \frac{1}{2}(x_1^2 + 10 x_2^2) = \frac{1}{2}\mathbf{x}^T \begin{bmatrix} 1 & 0 \\ 0 & 10 \end{bmatrix} \mathbf{x}\] Aqui, \(\lambda_1 = 1\), \(\lambda_2 = 10\), logo o número de condição é \(\kappa = \frac{10}{1} = 10\). As curvas de nível são elipses cuja largura no eixo \(x_1\) é \(\sqrt{10} \approx 3{,}16\) vezes maior do que no eixo \(x_2\).

No mesmo ponto \(\mathbf{x}_0 = (2, 1)\), o gradiente real é: \[\nabla f(2, 1) = \begin{bmatrix} 1 \cdot 2 \\ 10 \cdot 1 \end{bmatrix} = \begin{bmatrix} 2 \\ 10 \end{bmatrix} \implies -\nabla f(2, 1) = \begin{bmatrix} -2 \\ -10 \end{bmatrix}\]

A direção ideal para o mínimo continua sendo \(\mathbf{v}^\star = [-2, -1]^T\). O ângulo \(\theta\) entre \(-\nabla f\) e a direção ótima \(\mathbf{v}^\star\) é dado por: \[\cos \theta = \frac{\langle -\nabla f, \mathbf{v}^\star \rangle}{\|-\nabla f\| \|\mathbf{v}^\star\|} = \frac{(-2)(-2) + (-10)(-1)}{\sqrt{(-2)^2 + (-10)^2}\sqrt{(-2)^2 + (-1)^2}} = \frac{14}{\sqrt{520}} \approx 0{,}614 \implies \boldsymbol{\theta \approx 52{,}1^\circ}!\]

O vetor de descida já está desviado em mais de \(52^\circ\) em relação ao caminho até o mínimo! Ele empurra o ponto violentamente contra a encosta íngreme lateral (\(x_2\)), com pouquíssimo ímpeto de avançar no fundo do vale (\(x_1\)).

2.4 A Bacia Alongada: A Fenda Crítica (\(\kappa = 20\))

Estendendo o desbalanceamento para \(\kappa = 20\): \[f(\mathbf{x}) = \frac{1}{2}(x_1^2 + 20 x_2^2) \implies \lambda_1 = 1, \quad \lambda_2 = 20, \quad \kappa = 20\]

No mesmo ponto \(\mathbf{x}_0 = (2, 1)\), o vetor de descida é \(-\nabla f(2, 1) = [-2, -20]^T\). A componente vertical transversal que empurra para a encosta oposta é dez vezes maior do que a componente longitudinal que avança no vale!

O ângulo com a direção ideal ao centro satisfaz: \[\cos \theta = \frac{(-2)(-2) + (-20)(-1)}{\sqrt{(-2)^2 + (-20)^2}\sqrt{(-2)^2 + (-1)^2}} = \frac{24}{\sqrt{404}\sqrt{5}} \approx 0{,}534 \implies \boldsymbol{\theta \approx 57{,}7^\circ}!\]

O passo do gradiente \(\mathbf{x}_1 = \mathbf{x}_0 - \alpha \nabla f(\mathbf{x}_0)\) salta quase puramente na direção transversal, cruzando o vale e aterrissando na parede oposta em \(x_{2,1} \approx -0{,}90\), tendo avançado quase nada no eixo longo \(x_1\) (\(2{,}0 \to 1{,}81\)).

2.5 O Cânion Estreito: O Ziguezague Transversal (\(\kappa \gg 1\))

O que acontece quando o número de condição atinge valores severos, como \(\kappa = 20\), \(\kappa = 100\) ou o valor do California Housing (\(\kappa \approx 23.460\))?

Como o gradiente é estritamente perpendicular às curvas de nível extremamente alongadas, o algoritmo é vítima de um padrão patológico inevitável: 1. O algoritmo dá um passo e salta quase perpendicularmente em direção à parede oposta do cânion. 2. Na parede oposta, a componente transversal do gradiente inverte de sinal e o empurra de volta. 3. O algoritmo ziguezagueia furiosamente entre as duas encostas laterais, enquanto o deslocamento útil ao longo do fundo do vale avança a passos infinitesimais.

3 Bloco 1: O Algoritmo de Descida do Gradiente e o Tamanho de Passo

3.1 Formulação Formal e a Direção de Maior Descida Euclidiana

Consideremos o problema fundamental de otimização contínua irrestrita: \[\min_{\mathbf{w} \in \mathbb{R}^d} f(\mathbf{w})\] onde \(f: \mathbb{R}^d \to \mathbb{R}\) é continuamente diferenciável (\(C^1\)).

Estando no ponto atual \(\mathbf{w}\), desejamos nos deslocar por uma distância infinitesimal \(\delta > 0\) ao longo de uma direção unitária \(\mathbf{u} \in \mathbb{R}^d\) (\(\|\mathbf{u}\|_2 = 1\)). A aproximação de Taylor de primeira ordem da função é: \[f(\mathbf{w} + \delta \mathbf{u}) \approx f(\mathbf{w}) + \delta \nabla f(\mathbf{w})^T \mathbf{u}\]

A taxa instantânea de variação ao longo de \(\mathbf{u}\) é a derivada direcional \(D_{\mathbf{u}} f(\mathbf{w}) = \nabla f(\mathbf{w})^T \mathbf{u}\). Para maximizar o decréscimo da função, queremos escolher a direção unitária \(\mathbf{u}^\star\) que resolve o problema de otimização direcional: \[\min_{\|\mathbf{u}\|_2 = 1} \nabla f(\mathbf{w})^T \mathbf{u}\]

NotaTeorema 1 (Direção de Maior Descida / Steepest Descent; Boyd §9.3; MathML §7.1)

Sob a norma euclidiana \(\|\cdot\|_2\), a direção unitária que minimiza a derivada direcional é anti-paralela ao vetor gradiente: \[\mathbf{u}^\star = -\frac{\nabla f(\mathbf{w})}{\|\nabla f(\mathbf{w})\|_2}\] Demonstração: Pela desigualdade de Cauchy-Schwarz, para quaisquer dois vetores em \(\mathbb{R}^d\): \[|\nabla f(\mathbf{w})^T \mathbf{u}| \le \|\nabla f(\mathbf{w})\|_2 \|\mathbf{u}\|_2 = \|\nabla f(\mathbf{w})\|_2\] Isso implica diretamente a dupla desigualdade: \[-\|\nabla f(\mathbf{w})\|_2 \le \nabla f(\mathbf{w})^T \mathbf{u} \le \|\nabla f(\mathbf{w})\|_2\] O limitante inferior absoluto \(-\|\nabla f(\mathbf{w})\|_2\) é atingido se e somente se \(\mathbf{u}\) for colinear e em sentido oposto a \(\nabla f(\mathbf{w})\), isto é, \(\mathbf{u}^\star = -\frac{\nabla f(\mathbf{w})}{\|\nabla f(\mathbf{w})\|_2}\). \(\blacksquare\)

Isso estabelece formalmente por que atualizamos contra o gradiente: \[\mathbf{w}_{k+1} = \mathbf{w}_k - \alpha \nabla f(\mathbf{w}_k)\] Mas isso gera uma questão crucial: a aproximação linear sugere que podemos andar infinitamente na direção \(-\nabla f\) e a função diminuirá para sempre (\(-\alpha \|\nabla f\|^2 \to -\infty\)). Mas em qualquer função real com curvatura, se o passo \(\alpha\) for longo demais, a função ultrapassa o vale e sobe para o infinito. Como controlar matematicamente esse erro?

3.2 O Que é Suavidade Lipschitz do Gradiente (\(L\)-Suavidade)

Para impedir que a função exploda ao dar um passo finito, precisamos impor uma condição sobre a velocidade máxima com que o gradiente pode mudar de direção e magnitude. Essa condição matemática é a suavidade de Lipschitz (Lipschitz smoothness).

NotaDefinição 1 (Gradiente \(L\)-Lipschitziano / \(L\)-Suavidade)

Uma função diferenciável \(f: \mathbb{R}^d \to \mathbb{R}\) possui gradiente \(L\)-Lipschitziano com constante \(L > 0\) se, para todos \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^d\): \[\|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\|_2 \le L \|\mathbf{x} - \mathbf{y}\|_2\]

3.2.1 Conexão Fundamental com a Matriz Hessiana (Aula 7)

Se a função \(f\) for duas vezes continuamente diferenciável (\(C^2\)), podemos relacionar diretamente a constante de Lipschitz com os autovalores da matriz Hessiana: Pelo Teorema do Valor Médio, \(\nabla f(\mathbf{x}) - \nabla f(\mathbf{y}) = \int_0^1 \nabla^2 f(\mathbf{y} + t(\mathbf{x}-\mathbf{y})) (\mathbf{x}-\mathbf{y})\, dt\). Tomando a norma espectral: \[\|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\|_2 \le \sup_{\mathbf{z}} \|\nabla^2 f(\mathbf{z})\|_2 \|\mathbf{x}-\mathbf{y}\|_2\]

Portanto, para matrizes simétricas, a \(L\)-suavidade equivale rigorosamente a dizer que a curvatura direcional máxima é uniformemente limitada por \(L\): \[\nabla^2 f(\mathbf{x}) \preceq L I \iff \lambda_{\max}(\nabla^2 f(\mathbf{x})) \le L, \quad \forall \mathbf{x} \in \mathbb{R}^d\]

Em termos intuitivos: \(L\) é o teto máximo de curvatura da paisagem. Uma função \(L\)-suave nunca dobra para cima mais rápido do que uma parábola de abertura quadrática proporcional a \(L\).

3.3 Demonstração Formal do Limitante Superior Quadrático (Majorante)

A partir da definição de \(L\)-suavidade, deduzimos agora um dos teoremas mais poderosos e fundamentais de toda a teoria da otimização: o Majorante Quadrático (Quadratic Upper Bound).

NotaTeorema 2 (Limitante Superior Quadrático / Majorante; Boyd §9.3.1; Nesterov, 2018)

Seja \(f: \mathbb{R}^d \to \mathbb{R}\) uma função com gradiente \(L\)-Lipschitziano. Então, para quaisquer dois pontos \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^d\): \[f(\mathbf{y}) \le f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y} - \mathbf{x}) + \frac{L}{2}\|\mathbf{y} - \mathbf{x}\|_2^2\]

3.3.1 Demonstração Rigorosa Passo a Passo:

1. Parametrizamos o segmento de reta que une \(\mathbf{x}\) a \(\mathbf{y}\) por \(\mathbf{r}(t) = \mathbf{x} + t(\mathbf{y}-\mathbf{x})\), com \(t \in [0, 1]\).
2. Pelo Teorema Fundamental do Cálculo aplicado à função escalar \(g(t) = f(\mathbf{r}(t))\): \[f(\mathbf{y}) - f(\mathbf{x}) = g(1) - g(0) = \int_0^1 g'(t)\, dt = \int_0^1 \nabla f(\mathbf{x} + t(\mathbf{y}-\mathbf{x}))^T (\mathbf{y} - \mathbf{x})\, dt\]
3. Somamos e subtraímos o termo linear fixo \(\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})\) dentro da integral: \[f(\mathbf{y}) - f(\mathbf{x}) = \nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x}) + \int_0^1 \left[ \nabla f(\mathbf{x} + t(\mathbf{y}-\mathbf{x})) - \nabla f(\mathbf{x}) \right]^T (\mathbf{y} - \mathbf{x})\, dt\]
4. Avaliamos a magnitude do termo residual sob a integral usando a desigualdade de Cauchy-Schwarz: \[\left| \int_0^1 [\dots]^T (\mathbf{y}-\mathbf{x})\, dt \right| \le \int_0^1 \|\nabla f(\mathbf{x} + t(\mathbf{y}-\mathbf{x})) - \nabla f(\mathbf{x})\|_2 \|\mathbf{y}-\mathbf{x}\|_2\, dt\]
5. Aplicamos a hipótese de Lipschitz \(\|\nabla f(\mathbf{x} + t(\mathbf{y}-\mathbf{x})) - \nabla f(\mathbf{x})\|_2 \le L \|t(\mathbf{y}-\mathbf{x})\|_2 = t L \|\mathbf{y}-\mathbf{x}\|_2\): \[\le \int_0^1 (t L \|\mathbf{y}-\mathbf{x}\|_2) \|\mathbf{y}-\mathbf{x}\|_2\, dt = L \|\mathbf{y}-\mathbf{x}\|_2^2 \int_0^1 t\, dt = \frac{L}{2}\|\mathbf{y}-\mathbf{x}\|_2^2\]
6. Concluímos que a integral residual é no máximo \(\frac{L}{2}\|\mathbf{y}-\mathbf{x}\|_2^2\). Somando \(f(\mathbf{x})\) de ambos os lados, obtemos: \[f(\mathbf{y}) \le f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y} - \mathbf{x}) + \frac{L}{2}\|\mathbf{y} - \mathbf{x}\|_2^2 \quad \blacksquare\]

Significado Geométrico: A função verdadeira \(f(\mathbf{y})\) fica globalmente “abraçada por cima” por uma parábola esférica de curvatura \(L\) apoiada no plano tangente em \(\mathbf{x}\).

3.4 Demonstração Formal do Lema da Descida e o Limite \(\alpha < 2/L\)

Agora, colhemos o fruto direto do Majorante Quadrático para derivar a garantia fundamental da Descida do Gradiente.

Substituímos o próximo passo do algoritmo no lugar de \(\mathbf{y}\): \[\mathbf{y} = \mathbf{w}_{k+1} = \mathbf{w}_k - \alpha \nabla f(\mathbf{w}_k) \implies \mathbf{y} - \mathbf{w}_k = -\alpha \nabla f(\mathbf{w}_k)\]

Substituindo esse vetor de deslocamento diretamente no Majorante Quadrático: \[f(\mathbf{w}_{k+1}) \le f(\mathbf{w}_k) + \nabla f(\mathbf{w}_k)^T \left(-\alpha \nabla f(\mathbf{w}_k)\right) + \frac{L}{2} \|-\alpha \nabla f(\mathbf{w}_k)\|_2^2\] \[f(\mathbf{w}_{k+1}) \le f(\mathbf{w}_k) - \alpha \|\nabla f(\mathbf{w}_k)\|_2^2 + \frac{\alpha^2 L}{2} \|\nabla f(\mathbf{w}_k)\|_2^2\]

Colocando o termo comum \(\alpha \|\nabla f(\mathbf{w}_k)\|_2^2\) em evidência: \[f(\mathbf{w}_{k+1}) \le f(\mathbf{w}_k) - \alpha \left(1 - \frac{\alpha L}{2}\right) \|\nabla f(\mathbf{w}_k)\|_2^2\]

NotaTeorema 3 (Lema da Descida / Descent Lemma)

Se \(f\) possui gradiente \(L\)-Lipschitziano e \(\nabla f(\mathbf{w}_k) \ne \mathbf{0}\): 1. A Descida do Gradiente garante descida estrita (\(f(\mathbf{w}_{k+1}) < f(\mathbf{w}_k)\)) se e somente se: \[1 - \frac{\alpha L}{2} > 0 \iff \mathbf{0 < \alpha < \frac{2}{L}}\] 2. O tamanho de passo que maximiza a redução garantida pelo majorante é: \[\alpha^\star = \frac{1}{L}\] gerando a célebre garantia de decréscimo proporcional à energia do gradiente: \[f(\mathbf{w}_{k+1}) \le f(\mathbf{w}_k) - \frac{1}{2L}\|\nabla f(\mathbf{w}_k)\|_2^2\]

Se escolhermos \(\alpha \ge \frac{2}{L}\), o termo \(\left(1 - \frac{\alpha L}{2}\right)\) torna-se não positivo, a cota superior passa a ser maior ou igual a \(f(\mathbf{w}_k)\), e a garantia matemática de descida colapsa por completo!

3.5 Anatomia dos Regimes de Passo: Como \(\alpha\) Quebra a Otimização

Para enxergar com clareza cristalina como um passo mal calibrado destrói a otimização, consideremos uma função quadrática unidimensional simples: \[f(w) = \frac{L}{2}w^2 \implies f'(w) = L w, \quad w^\star = 0\]

A iteração da Descida do Gradiente é: \[w_{k+1} = w_k - \alpha (L w_k) = (1 - \alpha L) w_k \implies w_k = (1 - \alpha L)^k w_0\]

O fator de amplificação a cada passo é o número real \(\mu(\alpha) = 1 - \alpha L\). Existem cinco regimes analíticos fundamentais: 1. Passo Tímido / Sub-amortecido (\(0 < \alpha < \frac{1}{L}\)): \(0 < 1 - \alpha L < 1\). O valor de \(w_k\) decai monotonamente em direção a \(0\) pelo mesmo lado da bacia, sem jamais oscilar ou cruzar o mínimo. 2. Passo Ótimo (\(\alpha = \frac{1}{L}\)): \(1 - \alpha L = 0\). Temos \(w_1 = 0 \cdot w_0 = 0\). O algoritmo atinge o mínimo global exato em um único passo! 3. Passo Oscilante Amortecido (\(\frac{1}{L} < \alpha < \frac{2}{L}\)): \(-1 < 1 - \alpha L < 0\). O ponto pula de um lado para o outro do vale a cada iteração (ziguezague com alternância de sinal), mas a amplitude decai geometricamente: \(|w_k| \to 0\). 4. Passo Crítico de Estabilidade (\(\alpha = \frac{2}{L}\)): \(1 - \alpha L = -1\). Temos \(w_{k+1} = -w_k\). O algoritmo salta eternamente entre \(+w_0\) e \(-w_0\)! A perda permanece rigorosamente constante (\(f(w_k) = f(w_0)\)) e nunca converge. 5. Passo Excessivo / Divergência Geométrica (\(\alpha > \frac{2}{L}\)): \(1 - \alpha L < -1 \implies |1 - \alpha L| > 1\). A cada iteração, a distância ao mínimo é multiplicada por um número maior que 1. A trajetória explode exponencialmente: \(|w_k| \to \infty\). A otimização quebra completamente!

3.6 Pausa Ativa 2: Suavidade de Lipschitz e o Limite do Passo

DicaA Dinâmica na Parábola Unidimensional

Considere a função quadrática \(f(x) = \frac{1}{2} L x^2\) em \(\mathbb{R}\) (\(L > 0\)). Se aplicarmos a Descida do Gradiente \(x_{k+1} = x_k - \alpha f'(x_k)\) partindo de \(x_0 = 1\), deduza \(x_k\) em função de \(k\). O que ocorre se fixarmos \(\alpha = \frac{1}{L}\), \(\alpha = \frac{2}{L}\) e \(\alpha = \frac{2{,}1}{L}\)?

DicaV ou F: Lipschitz e Hiperparâmetros

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

• □ Para uma função duas vezes diferenciável, a constante de Lipschitz do gradiente é igual ao supremo do maior autovalor da Hessiana: \(L = \sup_{\mathbf{x}} \lambda_{\max}(\nabla^2 f(\mathbf{x}))\).
• □ Pelo Lema de Descida, fixar \(\alpha = \frac{1}{L}\) garante que \(f(\mathbf{x}_{k+1}) \le f(\mathbf{x}_k) - \frac{1}{2L} \|\nabla f(\mathbf{x}_k)\|^2\).
• □ Escolher \(\alpha = \frac{1{,}99}{L}\) em uma função convexa suave causa divergência numérica exponencial para o infinito.
• □ Na perda dos mínimos quadrados \(f(\boldsymbol{\beta}) = \|X\boldsymbol{\beta} - \mathbf{y}\|^2\), a constante de Lipschitz é dada por \(L = 2 \lambda_{\max}(X^T X)\).

4 Bloco 2: A Dinâmica Espectral do Erro e o Teorema de Chebyshev

4.1 De Onde Vem a Equação do Vetor de Erro: \(\mathbf{e}_{k+1} = (I - \alpha A)\mathbf{e}_k\)

Para compreender a fundo a geometria e o comportamento dinâmico da Descida do Gradiente em múltiplas dimensões, analisamos a classe canônica das formas quadráticas estritamente convexas: \[f(\mathbf{w}) = \frac{1}{2}\mathbf{w}^T A \mathbf{w} - \mathbf{b}^T \mathbf{w}\] onde \(A \in \mathbb{R}^{d \times d}\) é simétrica e definida positiva (\(A = A^T \succ 0\)), e \(\mathbf{b} \in \mathbb{R}^d\).

Como vimos na Aula 7, o minimizador global único \(\mathbf{w}^\star\) é o ponto onde o gradiente se anula: \[\nabla f(\mathbf{w}^\star) = A\mathbf{w}^\star - \mathbf{b} = \mathbf{0} \implies \mathbf{b} = A\mathbf{w}^\star\]

Substituindo \(\mathbf{b} = A\mathbf{w}^\star\) de volta na expressão do gradiente para qualquer ponto arbitrário \(\mathbf{w}\): \[\nabla f(\mathbf{w}) = A\mathbf{w} - \mathbf{b} = A\mathbf{w} - A\mathbf{w}^\star = A(\mathbf{w} - \mathbf{w}^\star)\] Essa relação algébrica fundamental revela que, em qualquer quadrática, o vetor gradiente é linearmente proporcional à distância física até o mínimo \(\mathbf{w}^\star\), ponderado pela matriz de curvatura \(A\).

Definimos agora o vetor de erro na iteração \(k\) como a discrepância em relação à solução ótima: \[\mathbf{e}_k = \mathbf{w}_k - \mathbf{w}^\star\]

A iteração da Descida do Gradiente é dada por: \[\mathbf{w}_{k+1} = \mathbf{w}_k - \alpha \nabla f(\mathbf{w}_k) = \mathbf{w}_k - \alpha A(\mathbf{w}_k - \mathbf{w}^\star)\]

Subtraindo \(\mathbf{w}^\star\) de ambos os lados da equação: \[\mathbf{w}_{k+1} - \mathbf{w}^\star = (\mathbf{w}_k - \mathbf{w}^\star) - \alpha A(\mathbf{w}_k - \mathbf{w}^\star)\] Substituindo a definição do vetor de erro \(\mathbf{e}_k\): \[\mathbf{e}_{k+1} = \mathbf{e}_k - \alpha A \mathbf{e}_k = (I - \alpha A)\mathbf{e}_k\]

A matriz \(T_\alpha = (I - \alpha A) \in \mathbb{R}^{d \times d}\) é a matriz de transição do erro. Esse resultado prova que a Descida do Gradiente aplicada a uma perda quadrática é um sistema dinâmico linear discreto e invariante no tempo, cujo estado de erro no passo \(k\) é: \[\mathbf{e}_k = (I - \alpha A)^k \mathbf{e}_0\]

4.2 Desacoplamento Modal nos Autovetores via Teorema Espectral

O problema da equação \(\mathbf{e}_{k+1} = (I - \alpha A)\mathbf{e}_k\) é que as coordenadas do vetor \(\mathbf{e}_k\) estão fortemente acopladas se a matriz \(A\) não for diagonal (produtos cruzados misturam as variáveis).

Como contornar esse acoplamento? Recorremos ao Teorema Espectral (Aula 4): como \(A\) é simétrica (\(A = A^T\)), existe uma base ortonormal de autovetores \(\mathbf{v}_1, \dots, \mathbf{v}_d\) tal que: \[A = Q \Lambda Q^T, \quad Q = [\mathbf{v}_1, \dots, \mathbf{v}_d] \text{ com } Q^T Q = Q Q^T = I\] \[\Lambda = \text{diag}(\lambda_1, \dots, \lambda_d), \quad \text{onde } \lambda_{\max} = \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_d = \lambda_{\min} > 0\]

Substituindo essa fatoração na matriz de transição do erro: \[I - \alpha A = Q I Q^T - \alpha Q \Lambda Q^T = Q (I - \alpha \Lambda) Q^T\] Portanto, a dinâmica do erro no espaço original é: \[\mathbf{e}_{k+1} = Q (I - \alpha \Lambda) Q^T \mathbf{e}_k\]

Multiplicando à esquerda por \(Q^T\) e definindo as coordenadas modais do erro \(\tilde{\mathbf{e}}_k = Q^T \mathbf{e}_k\) (que representam a projeção do erro sobre cada eixo próprio \(\mathbf{v}_i\)): \[\tilde{\mathbf{e}}_{k+1} = (I - \alpha \Lambda) \tilde{\mathbf{e}}_k\]

Como a matriz \((I - \alpha \Lambda)\) é estritamente diagonal: \[\begin{bmatrix} \tilde{e}_{k+1, 1} \\ \tilde{e}_{k+1, 2} \\ \vdots \\ \tilde{e}_{k+1, d} \end{bmatrix} = \begin{bmatrix} 1 - \alpha \lambda_1 & 0 & \dots & 0 \\ 0 & 1 - \alpha \lambda_2 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 - \alpha \lambda_d \end{bmatrix} \begin{bmatrix} \tilde{e}_{k, 1} \\ \tilde{e}_{k, 2} \\ \vdots \\ \tilde{e}_{k, d} \end{bmatrix}\]

O acoplamento dimensional desaparece por completo! Cada coordenada modal \(i \in \{1, \dots, d\}\) evolui de forma totalmente isolada como uma dinâmica escalar 1D: \[\tilde{e}_{k+1, i} = (1 - \alpha \lambda_i) \tilde{e}_{k, i} \implies \mathbf{\tilde{e}_{k, i} = (1 - \alpha \lambda_i)^k \tilde{e}_{0, i}}\]

O Significado Geométrico e Físico: No sistema de eixos canônico, as variáveis interagem e parecem ziguezaguear de maneira complexa. Mas, quando olhamos o mesmo processo pela ótica dos eixos principais da Hessiana (os autovetores), o problema se decompõe em \(d\) trajetórias retilíneas paralelas e independentes. Ao longo de cada autovetor \(\mathbf{v}_i\), o erro é multiplicado pelo fator \((1 - \alpha \lambda_i)\) a cada passo.

4.3 A Taxa Ótima de Chebyshev e a Análise Minimax em Detalhes

Com o erro desacoplado em coordenadas modais, como determinar o tamanho de passo \(\alpha\) que garante a convergência mais rápida possível de todo o vetor?

4.3.1 1. A Condição de Estabilidade Assintótica

Como a transformação ortogonal preserva normas euclidianas (\(\|\mathbf{e}_k\|_2 = \|Q \tilde{\mathbf{e}}_k\|_2 = \|\tilde{\mathbf{e}}_k\|_2\)): \[\|\mathbf{e}_k\|_2^2 = \sum_{i=1}^d \tilde{e}_{k, i}^2 = \sum_{i=1}^d (1 - \alpha \lambda_i)^{2k} \tilde{e}_{0, i}^2\] Para que \(\|\mathbf{e}_k\|_2 \to 0\) quando \(k \to \infty\) a partir de qualquer erro inicial \(\mathbf{e}_0\), todas as \(d\) componentes modais devem contrair estritamente. Isso exige: \[|1 - \alpha \lambda_i| < 1 \iff -1 < 1 - \alpha \lambda_i < 1 \iff 0 < \alpha < \frac{2}{\lambda_i}, \quad \forall i \in \{1, \dots, d\}\] Como essa condição deve valer para todos os autovalores, ela é ditada pela direção mais exigente (o maior autovalor): \[\mathbf{0 < \alpha < \frac{2}{\lambda_{\max}}}\]

4.3.2 2. O Raio Espectral como Fator Limitante

O decaimento da norma do erro é dominado pela coordenada que contrai mais lentamente: \[\|\mathbf{e}_k\|_2 \le \left(\max_{i=1,\dots,d} |1 - \alpha \lambda_i|\right)^k \|\mathbf{e}_0\|_2\] A taxa de contração no pior caso é o raio espectral da matriz de transição \(T_\alpha\): \[\rho(\alpha) = \max_{i=1,\dots,d} |1 - \alpha \lambda_i|\]

4.3.3 3. Por Que Apenas os Extremos \(\lambda_{\min}\) e \(\lambda_{\max}\) Importam?

A função \(h(\lambda) = 1 - \alpha \lambda\) é uma reta estritamente decrescente em \(\lambda\). Para qualquer autovalor intermediário \(\lambda_i \in [\lambda_{\min}, \lambda_{\max}]\), o valor de \(1 - \alpha \lambda_i\) fica rigorosamente ensanduichado entre os extremos: \[1 - \alpha \lambda_{\max} \le 1 - \alpha \lambda_i \le 1 - \alpha \lambda_{\min}\] Portanto, o valor absoluto máximo \(|1 - \alpha \lambda_i|\) só pode ser atingido em uma das duas extremidades do espectro: - No eixo de menor curvatura (\(\lambda_{\min}\)): a contração é \(1 - \alpha \lambda_{\min} > 0\). - No eixo de maior curvatura (\(\lambda_{\max}\)): se \(\alpha > 1/\lambda_{\max}\), o fator torna-se negativo, com módulo \(|1 - \alpha \lambda_{\max}| = \alpha \lambda_{\max} - 1\).

Assim, o pior fator de contração colapsa no máximo entre duas retas: \[\rho(\alpha) = \max \left\{ 1 - \alpha \lambda_{\min}, \; \alpha \lambda_{\max} - 1 \right\}\]

4.3.4 4. O Problema Minimax de Chebyshev

Temos um dilema antagônico (“cabo de guerra”): - Se aumentamos \(\alpha\): a reta \(1 - \alpha \lambda_{\min}\) diminui (o eixo lento contrai mais depressa, o que é desejável), mas a reta \(\alpha \lambda_{\max} - 1\) sobe (o eixo rápido oscila com maior amplitude transversal, arriscando instabilidade). - Se diminuímos \(\alpha\): o eixo rápido acalma, mas o eixo lento praticamente estagna (\(1 - \alpha \lambda_{\min} \approx 1\)).

O tamanho de passo ideal deve minimizar o pior fator de contração possível: \[\min_{\alpha > 0} \; \max \left\{ 1 - \alpha \lambda_{\min}, \; \alpha \lambda_{\max} - 1 \right\}\]

Como uma reta é estritamente decrescente e a outra é estritamente crescente, o mínimo do máximo ocorre com precisão cirúrgica na interseção das duas retas: \[1 - \alpha^\star \lambda_{\min} = \alpha^\star \lambda_{\max} - 1\] \[2 = \alpha^\star (\lambda_{\max} + \lambda_{\min}) \implies \mathbf{\alpha^\star = \frac{2}{\lambda_{\max} + \lambda_{\min}}}\]

4.3.5 5. Dedução Rigorosa da Fórmula \(\frac{\kappa - 1}{\kappa + 1}\)

Substituindo o passo ótimo \(\alpha^\star\) na expressão de contração no eixo lento: \[\rho^\star = 1 - \alpha^\star \lambda_{\min} = 1 - \frac{2\lambda_{\min}}{\lambda_{\max} + \lambda_{\min}} = \frac{(\lambda_{\max} + \lambda_{\min}) - 2\lambda_{\min}}{\lambda_{\max} + \lambda_{\min}} = \frac{\lambda_{\max} - \lambda_{\min}}{\lambda_{\max} + \lambda_{\min}}\]

Dividimos agora tanto o numerador quanto o denominador pelo autovalor mínimo \(\lambda_{\min}\): \[\rho^\star = \frac{\frac{\lambda_{\max}}{\lambda_{\min}} - 1}{\frac{\lambda_{\max}}{\lambda_{\min}} + 1}\] Lembrando que o número de condição da matriz \(A\) é \(\kappa = \text{cond}(A) = \frac{\lambda_{\max}}{\lambda_{\min}} \ge 1\):

NotaTeorema 4 (Taxa Ótima de Contração de Chebyshev; Boyd §9.3.2; MathML §7.1)

Para qualquer função quadrática estritamente convexa (\(A \succ 0\)), a taxa ótima de contração do erro por iteração da Descida do Gradiente é: \[\rho^\star = \frac{\kappa - 1}{\kappa + 1}, \quad \text{com } \kappa = \frac{\lambda_{\max}}{\lambda_{\min}} \ge 1\] O decaimento no valor da função de perda em relação ao valor ótimo \(f^\star = f(\mathbf{w}^\star)\) satisfaz: \[f(\mathbf{w}_k) - f^\star \le \left(\frac{\kappa - 1}{\kappa + 1}\right)^{2k} (f(\mathbf{w}_0) - f^\star)\]

Por que o expoente é \(2k\) na perda? Porque a perda quadrática mede o produto interno do erro ponderado por \(A\): \[f(\mathbf{w}_k) - f^\star = \frac{1}{2} \mathbf{e}_k^T A \mathbf{e}_k = \frac{1}{2} \tilde{\mathbf{e}}_k^T \Lambda \tilde{\mathbf{e}}_k = \frac{1}{2} \sum_{i=1}^d \lambda_i \tilde{e}_{k, i}^2 = \frac{1}{2} \sum_{i=1}^d \lambda_i (1 - \alpha \lambda_i)^{2k} \tilde{e}_{0, i}^2\] Como \((1 - \alpha^\star \lambda_i)^2 \le (\rho^\star)^2\) para todo \(i\): \[f(\mathbf{w}_k) - f^\star \le (\rho^\star)^{2k} \left(\frac{1}{2}\sum_{i=1}^d \lambda_i \tilde{e}_{0, i}^2\right) = (\rho^\star)^{2k} (f(\mathbf{w}_0) - f^\star) \quad \blacksquare\]

4.3.6 6. A Lição Fundamental nos Diferentes Valores de \(\kappa\)

Observe o impacto avassalador de \(\kappa\) na velocidade de convergência:

Condição \(\kappa\)	Taxa \(\rho^\star = \frac{\kappa-1}{\kappa+1}\)	Fator de Perda \((\rho^\star)^2\)	Comportamento Prático
\(\kappa = 1\) (Esfera)	\(\frac{0}{2} = \mathbf{0{,}0000}\)	\(0\)	Convergência perfeita em 1 único passo.
\(\kappa = 3\)	\(\frac{2}{4} = \mathbf{0{,}5000}\)	\(0{,}25\)	Erro cai pela metade a cada passo (\(10\) passos reduzem \(1.000\times\)).
\(\kappa = 10\)	\(\frac{9}{11} \approx \mathbf{0{,}8182}\)	\(0{,}67\)	Ziguezague perceptível; requer dezenas de iterações.
\(\kappa = 100\)	\(\frac{99}{101} \approx \mathbf{0{,}9802}\)	\(0{,}96\)	O erro reduz míseros \(2\%\) ao passo; exige centenas de passos.
\(\kappa \approx 23.460\) (Calif. Housing)	\(\frac{23459{,}5}{23461{,}5} \approx \mathbf{0{,}999915}\)	\(0{,}99983\)	Paralisia numérica quase total! Mais de \(81.000\) iterações para reduzir o erro em \(99{,}9\%\).

4.4 Pausa Ativa 3: Análise Espectral e o Número de Condição

DicaO Preço do Eixo Lento

Considere uma forma quadrática em \(\mathbb{R}^2\) com Hessiana diagonal tendo autovalores \(\lambda_1 = 100\) e \(\lambda_2 = 1\). Se aplicarmos a Descida do Gradiente com o passo ótimo \(\alpha^\star = \frac{2}{100 + 1} \approx 0{,}0198\), qual será o fator de redução do erro na coordenada \(1\) e na coordenada \(2\) a cada passo? Por que o eixo de menor curvatura dita a lentidão de todo o processo?

DicaV ou F: Dinâmica Espectral do Erro

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

• □ Em uma forma quadrática \(A \succ 0\), o passo crítico máximo para evitar que o erro exploda assintoticamente é \(\alpha_{\text{crit}} = \frac{2}{\lambda_{\max}(A)}\).
• □ Quando o tamanho de passo satisfaz \(\frac{1}{\lambda_i} < \alpha < \frac{2}{\lambda_i}\), o erro ao longo do autovetor \(\mathbf{v}_i\) oscila alternando de sinal a cada iteração.
• □ Se todos os autovalores da matriz Hessiana forem rigorosamente iguais (\(\kappa = 1\)), a Descida do Gradiente com passo \(\alpha = 1/\lambda_1\) requer \(d\) iterações para convergir.
• □ O raio espectral da matriz de transição de erro \((I - \alpha A)\) pode ser estritamente negativo.

5 Bloco 3: O Problema-Fio no California Housing e a Padronização

5.1 Diagnóstico do Mau Condicionamento no California Housing

Vamos agora aplicar essa teoria analítica ao caso real do California Housing.

Na perda dos mínimos quadrados \(L(\boldsymbol{\beta}) = \frac{1}{2N}\|X\boldsymbol{\beta} - \mathbf{y}\|_2^2\), a matriz Hessiana é \(\nabla^2 L = \frac{1}{N}X^T X\). Nos dados brutos com as 4 colunas (MedInc, HouseAge, AveRooms, AveBedrms), calculamos: \[\lambda_{\max} \approx 849{,}37, \quad \lambda_{\min} \approx 0{,}0362 \implies \kappa = \frac{\lambda_{\max}}{\lambda_{\min}} \approx \mathbf{23.460{,}5}\]

Substituindo esse valor na fórmula de Chebyshev do Teorema 4: \[\rho^\star = \frac{23.460{,}5 - 1}{23.460{,}5 + 1} = \frac{23.459{,}5}{23.461{,}5} \approx \mathbf{0{,}9999147}\]

Quantas iterações são necessárias para reduzir o erro em uma fração de \(10^{-3}\) (\(99{,}9\%\) de redução de erro)? \[(\rho^\star)^k \le 10^{-3} \implies k \ln(\rho^\star) \le \ln(10^{-3})\] \[k \ge \frac{-6{,}908}{\ln(0{,}9999147)} \approx \frac{-6{,}908}{-8{,}53 \cdot 10^{-5}} \approx \mathbf{81.000\text{ iterações}}!\]

Executar \(81.000\) iterações de um algoritmo em terabytes de dados pode levar dias. Como resolver esse problema sem abandonar a Descida do Gradiente?

5.2 A Cura Algébrica: Padronização Z-Score como Pré-condicionamento

A cura clássica para essa patologia em Aprendizado de Máquina é a padronização das colunas (\(Z\)-score). Mas por que ela funciona tão bem? Do ponto de vista da Álgebra Linear e da Otimização, a padronização é rigorosamente um pré-condicionamento diagonal de Jacobi (Jacobi diagonal preconditioning).

5.2.1 1. A Padronização como Mudança de Base no Espaço de Parâmetros

Considere os dados centralizados \(X_c = X - \mathbf{1}\boldsymbol{\mu}^T\), onde cada atributo tem média zero. Seja \(D = \operatorname{diag}(s_1^2, s_2^2, \dots, s_d^2)\) a matriz diagonal contendo as variâncias amostrais \(s_j^2 = \frac{1}{N} \sum_{n=1}^N (x_{nj} - \bar{x}_j)^2\).

A matriz de atributos padronizados \(\tilde{X}\) é obtida multiplicando à direita pela raiz quadrada inversa de \(D\): \[\tilde{X} = X_c D^{-1/2}, \quad \text{onde } D^{-1/2} = \operatorname{diag}\left(\frac{1}{s_1}, \frac{1}{s_2}, \dots, \frac{1}{s_d}\right)\]

Para que as predições do modelo linear sejam idênticas nos dois sistemas de coordenadas (\(\hat{\mathbf{y}} = X_c \boldsymbol{\beta} = \tilde{X} \tilde{\boldsymbol{\beta}}\)), os coeficientes devem se relacionar por: \[X_c \boldsymbol{\beta} = X_c D^{-1/2} \tilde{\boldsymbol{\beta}} \implies \boldsymbol{\beta} = D^{-1/2} \tilde{\boldsymbol{\beta}} = P \tilde{\boldsymbol{\beta}}\] onde definimos a matriz de mudança de coordenadas \(P = D^{-1/2}\).

5.2.2 2. A Hessiana Padronizada é o Pré-condicionador de Jacobi (Matriz de Correlação)

A função de perda no espaço original é \(L(\boldsymbol{\beta}) = \frac{1}{2N} \|X_c \boldsymbol{\beta} - \mathbf{y}\|_2^2\), cuja matriz Hessiana é \(H = \nabla^2 L(\boldsymbol{\beta}) = \frac{1}{N} X_c^T X_c\). Observe que o elemento diagonal \(H_{jj} = \frac{1}{N} \sum_{n=1}^N (x_{nj} - \bar{x}_j)^2 = s_j^2\), de modo que: \[D = \operatorname{diag}(H)\]

No espaço parametrizado por \(\tilde{\boldsymbol{\beta}}\), a perda é \(\tilde{L}(\tilde{\boldsymbol{\beta}}) = L(P \tilde{\boldsymbol{\beta}})\). A nova Hessiana \(\tilde{H}\) é dada pela transformação de congruência: \[\tilde{H} = \nabla^2_{\tilde{\boldsymbol{\beta}}} \tilde{L} = P^T H P = D^{-1/2} H D^{-1/2}\]

Analisando os elementos dessa nova matriz: \[\tilde{H}_{ij} = \frac{H_{ij}}{\sqrt{H_{ii} H_{jj}}} = \frac{\operatorname{Cov}(x_i, x_j)}{s_i s_j} = r_{ij} \quad (\text{coeficiente de correlação de Pearson})\] Em particular, para todo elemento diagonal (\(i = j\)): \[\tilde{H}_{jj} = \frac{s_j^2}{s_j \cdot s_j} = 1, \quad \forall j \in \{1, \dots, d\}\]

Em Álgebra Linear Numérica, escolher uma matriz de escalonamento diagonal \(M = \operatorname{diag}(H)\) para normalizar a diagonal da matriz do sistema para \(1\) é conhecido como o Pré-condicionador de Jacobi (Jacobi preconditioner). Ele equilibra as grandezas nas diferentes direções canônicas, eliminando as assimetrias causadas por unidades físicas arbitrárias (como anos vs quartos vs dólares).

5.2.3 3. Equivalência Formal com a Descida do Gradiente Pré-Condicionada

O que acontece no algoritmo quando rodamos a Descida do Gradiente nos dados padronizados? A regra de atualização sobre \(\tilde{\boldsymbol{\beta}}\) é: \[\tilde{\boldsymbol{\beta}}_{k+1} = \tilde{\boldsymbol{\beta}}_k - \alpha \nabla_{\tilde{\boldsymbol{\beta}}} \tilde{L}(\tilde{\boldsymbol{\beta}}_k)\]

Pela regra da cadeia, \(\nabla_{\tilde{\boldsymbol{\beta}}} \tilde{L} = P^T \nabla_{\boldsymbol{\beta}} L = D^{-1/2} \nabla_{\boldsymbol{\beta}} L\). Multiplicando a atualização inteira à esquerda por \(P = D^{-1/2}\) para expressar a dinâmica no espaço original de parâmetros (\(\boldsymbol{\beta} = D^{-1/2}\tilde{\boldsymbol{\beta}}\)): \[D^{-1/2} \tilde{\boldsymbol{\beta}}_{k+1} = D^{-1/2} \tilde{\boldsymbol{\beta}}_k - \alpha D^{-1/2} \left( D^{-1/2} \nabla_{\boldsymbol{\beta}} L(\boldsymbol{\beta}_k) \right)\] \[\boldsymbol{\beta}_{k+1} = \boldsymbol{\beta}_k - \alpha D^{-1} \nabla_{\boldsymbol{\beta}} L(\boldsymbol{\beta}_k)\]

Essa identidade revela um fato profundo: > Treinar a Descida do Gradiente com atributos padronizados por \(Z\)-score é algebricamente idêntico a executar a Descida do Gradiente Pré-Condicionada (PGD) nos dados originais com a matriz de pré-condicionamento diagonal de Jacobi \(M = D = \operatorname{diag}(H)\)!

Coordenada a coordenada, cada parâmetro recebe uma taxa de aprendizado efetiva individual: \[\beta_{j, k+1} = \beta_{j, k} - \frac{\alpha}{s_j^2} [\nabla L(\boldsymbol{\beta}_k)]_j\] - Variáveis com variância gigantesca (paredes abruptas que causavam instabilidade) têm seu passo atenuado por \(1/s_j^2\). - Variáveis com variância pequena têm seu passo amplificado, avançando com firmeza no cânion.

5.2.4 4. O Impacto no Espectro e na Velocidade de Convergência

No California Housing, os autovalores da nova Hessiana \(\tilde{H}\) (que agora é a matriz de correlação das 4 variáveis) tornam-se: \[\tilde{\lambda}_1 \approx 0{,}17, \quad \tilde{\lambda}_2 \approx 0{,}62, \quad \tilde{\lambda}_3 \approx 1{,}02, \quad \tilde{\lambda}_4 \approx 2{,}19\]

1. O número de condição cai espetacularmente: \[\tilde{\kappa} = \frac{\tilde{\lambda}_{\max}}{\tilde{\lambda}_{\min}} = \frac{2{,}19}{0{,}17} \approx \mathbf{12{,}9}!\]
2. O fator de contração ótimo de Chebyshev passa a ser: \[\tilde{\rho}^\star = \frac{12{,}9 - 1}{12{,}9 + 1} = \frac{11{,}9}{13{,}9} \approx \mathbf{0{,}856}\]
3. O número de iterações para reduzir o erro em \(99{,}9\%\) (\(10^{-3}\)) cai de \(81.000\) para: \[k \ge \frac{\ln(10^{-3})}{\ln(0{,}856)} \approx \frac{-6{,}908}{-0{,}155} \approx \mathbf{45\text{ iterações}}!\]

Uma aceleração superior a \(1.800\) vezes, alcançada sem trocar de otimizador — apenas aplicando uma matriz pré-condicionadora diagonal!

5.3 Pausa Ativa 4: Padronização e a Hessiana

DicaO Segredo da Padronização

No California Housing, a renda média varia de \(0{,}5\) a \(15\), e a idade dos imóveis varia de \(1\) a \(52\). O que acontece geometricamente com as curvas de nível quando combinamos variáveis com escalas tão discrepantes? De que maneira a padronização linear consegue achatar o número de condição de \(23.460\) para \(12{,}9\)?

DicaV ou F: Escala e Condicionamento

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

• □ A padronização de atributos via \(Z\)-score altera a predição final ótima \(\hat{\mathbf{y}}\) de um modelo de regressão linear OLS não regularizado.
• □ Após a padronização das colunas de \(X\), todos os elementos da diagonal de \(\frac{1}{N}\tilde{X}^T \tilde{X}\) são rigorosamente iguais a 1.
• □ O algoritmo de Descida do Gradiente é invariante a transformações lineares de escala nos atributos.
• □ Reduzir o número de condição de \(20.000\) para \(13\) diminui o número de iterações necessárias para atingir uma tolerância de erro fixa em ordens de magnitude.

6 Bloco 4: Extensão para Além dos Mínimos Quadrados — Regressão Logística

6.1 Por Que Precisamos da Descida do Gradiente? A Classificação Binária

Até este momento, poderíamos pensar: “Por que estudar a Descida do Gradiente se para regressão linear sempre temos a solução fechada \((X^T X)^{-1} X^T \mathbf{y}\)?”

A resposta reside no fato de que a esmagadora maioria dos modelos de Machine Learning não possui solução analítica fechada. O exemplo mais célebre e essencial é a Regressão Logística para classificação binária (\(y_n \in \{0, 1\}\)) (Bishop, 2006, §4.3.2).

Queremos modelar a probabilidade condicional de a observação pertencer à classe \(1\): \[P(y_n = 1 \mid \mathbf{x}_n, \mathbf{w}) = \sigma(\mathbf{w}^T \mathbf{x}_n) = \hat{y}_n\] onde \(\sigma(z)\) é a função logística sigmoide: \[\sigma(z) = \frac{1}{1 + e^{-z}} = \frac{e^z}{1 + e^z}\]

A função sigmoide possui a propriedade diferenciável notável: \[\sigma'(z) = \frac{d}{dz}(1 + e^{-z})^{-1} = -(1 + e^{-z})^{-2}(-e^{-z}) = \frac{1}{1 + e^{-z}} \frac{e^{-z}}{1 + e^{-z}} = \mathbf{\sigma(z)(1 - \sigma(z))}\]

6.2 A Perda de Entropia Cruzada Binária e o Cálculo Cuidadoso do Gradiente

Assumindo que os rótulos \(y_n\) seguem uma distribuição de Bernoulli independente condicional a \(\mathbf{x}_n\): \[p(\mathbf{y} \mid X, \mathbf{w}) = \prod_{n=1}^N \hat{y}_n^{y_n} (1 - \hat{y}_n)^{1 - y_n}\]

Minimizar o negativo do logaritmo da verossimilhança normalizado por \(N\) fornece a perda de Entropia Cruzada Binária (Binary Cross-Entropy): \[\mathcal{L}(\mathbf{w}) = -\frac{1}{N}\sum_{n=1}^N \left[ y_n \ln \hat{y}_n + (1 - y_n) \ln(1 - \hat{y}_n) \right]\]

Vamos calcular o gradiente \(\nabla \mathcal{L}(\mathbf{w})\) aplicando cautelosamente a Regra da Cadeia Multivariada da Aula 6: Seja \(a_n = \mathbf{w}^T \mathbf{x}_n\), de modo que \(\hat{y}_n = \sigma(a_n)\). 1. Derivada da perda em relação a \(\hat{y}_n\): \[\frac{\partial \mathcal{L}}{\partial \hat{y}_n} = -\frac{1}{N} \left[ \frac{y_n}{\hat{y}_n} - \frac{1 - y_n}{1 - \hat{y}_n} \right] = -\frac{1}{N} \left[ \frac{y_n(1 - \hat{y}_n) - (1 - y_n)\hat{y}_n}{\hat{y}_n(1 - \hat{y}_n)} \right] = \frac{1}{N}\frac{\hat{y}_n - y_n}{\hat{y}_n(1 - \hat{y}_n)}\] 2. Derivada de \(\hat{y}_n\) em relação à ativação linear \(a_n\): \[\frac{\partial \hat{y}_n}{\partial a_n} = \sigma'(a_n) = \hat{y}_n(1 - \hat{y}_n)\] 3. Multiplicando as duas derivadas, os denominadores se cancelam com perfeição: \[\frac{\partial \mathcal{L}}{\partial a_n} = \frac{\partial \mathcal{L}}{\partial \hat{y}_n} \frac{\partial \hat{y}_n}{\partial a_n} = \frac{1}{N}(\hat{y}_n - y_n)\] 4. Como \(a_n = \mathbf{x}_n^T \mathbf{w}\), o gradiente em relação ao vetor de parâmetros \(\mathbf{w}\) é \(\nabla_{\mathbf{w}} a_n = \mathbf{x}_n\). Somando sobre todas as \(N\) observações: \[\nabla \mathcal{L}(\mathbf{w}) = \sum_{n=1}^N \frac{\partial \mathcal{L}}{\partial a_n} \nabla_{\mathbf{w}} a_n = \frac{1}{N}\sum_{n=1}^N (\hat{y}_n - y_n) \mathbf{x}_n\]

Em formato matricial compacto: \[\nabla \mathcal{L}(\mathbf{w}) = \frac{1}{N} X^T (\hat{\mathbf{y}} - \mathbf{y})\] onde \(\hat{\mathbf{y}} = \boldsymbol{\sigma}(X\mathbf{w})\).

6.3 O Impasse Transcendental e a Salvação Convexa (\(\nabla^2 \mathcal{L} \succ 0\))

Para encontrar o minimizador, impomos a condição de ponto crítico da Aula 7: \[\nabla \mathcal{L}(\mathbf{w}) = \mathbf{0} \iff \frac{1}{N}X^T (\boldsymbol{\sigma}(X\mathbf{w}) - \mathbf{y}) = \mathbf{0}\]

Aqui nos deparamos com o grande divisor de águas entre a álgebra estática e o aprendizado de máquina moderno: Essa equação é não linear transcendental! Como \(\boldsymbol{\sigma}(\cdot)\) aplica a função exponencial elemento a elemento, não existe nenhuma propriedade matricial, fatoração de Cholesky ou inversão de matrizes capaz de isolar \(\mathbf{w}\). A solução em forma fechada simplesmente não existe.

Mas será que a Descida do Gradiente consegue encontrar a solução com segurança? E se o problema tiver múltiplos mínimos locais ou pontos de sela? Para responder, calculamos a matriz Hessiana derivando o gradiente novamente em relação a \(\mathbf{w}\): \[\nabla^2 \mathcal{L}(\mathbf{w}) = \frac{1}{N}\sum_{n=1}^N \mathbf{x}_n \frac{\partial \hat{y}_n}{\partial \mathbf{w}^T} = \frac{1}{N}\sum_{n=1}^N \hat{y}_n(1 - \hat{y}_n) \mathbf{x}_n \mathbf{x}_n^T = \frac{1}{N} X^T S X\] onde \(S = \text{diag}(\hat{y}_1(1 - \hat{y}_1), \dots, \hat{y}_N(1 - \hat{y}_N)) \in \mathbb{R}^{N \times N}\).

Analisemos a definitude dessa Hessiana: 1. Como a sigmoide \(\hat{y}_n \in (0, 1)\) para qualquer \(\mathbf{w}\) finito, o produto \(\hat{y}_n(1 - \hat{y}_n)\) é estritamente positivo: \[0 < \hat{y}_n(1 - \hat{y}_n) \le \frac{1}{4} \implies S \succ 0 \quad (\text{matriz diagonal estritamente positiva definida})\] 2. Para qualquer vetor \(\mathbf{v} \in \mathbb{R}^d\) não nulo (\(\mathbf{v} \ne \mathbf{0}\)): \[\mathbf{v}^T \nabla^2 \mathcal{L}(\mathbf{w}) \mathbf{v} = \frac{1}{N} (X\mathbf{v})^T S (X\mathbf{v})\] Se a matriz de dados \(X\) tem posto coluna completo (\(rk(X) = d\)), então \(X\mathbf{v} \ne \mathbf{0}\). Como \(S \succ 0\), a forma quadrática é estritamente positiva: \[\mathbf{v}^T \nabla^2 \mathcal{L}(\mathbf{w}) \mathbf{v} > 0 \implies \nabla^2 \mathcal{L}(\mathbf{w}) \succ 0, \quad \forall \mathbf{w} \in \mathbb{R}^d\]

A conclusão é triunfal: A perda de entropia cruzada da regressão logística é estritamente convexa em todo o espaço \(\mathbb{R}^d\)! Não existem mínimos locais falsos. Embora não haja solução fechada, o algoritmo iterativo da Descida do Gradiente: \[\mathbf{w}_{k+1} = \mathbf{w}_k - \frac{\alpha}{N} X^T (\boldsymbol{\sigma}(X\mathbf{w}_k) - \mathbf{y})\] tem garantia matemática absoluta de convergir para o minimizador global único!

6.4 Pausa Ativa 5: Regressão Logística e a Otimização de 1ª Ordem

DicaPor Que Não Inverter?

Na regressão linear, isolamos \(\boldsymbol{\beta} = (X^T X)^{-1} X^T \mathbf{y}\). Na regressão logística, o gradiente tem formato idêntico: \(\frac{1}{N}X^T(\boldsymbol{\sigma}(X\mathbf{w}) - \mathbf{y}) = \mathbf{0}\). Por que não podemos usar inversão de matrizes para achar \(\mathbf{w}\) na regressão logística? A ausência de solução fechada significa que o problema tem múltiplos mínimos locais?

DicaV ou F: Regressão Logística e Otimização

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

• □ A derivada da função sigmoide satisfaz \(\sigma'(z) = \sigma(z)(1 - \sigma(z))\).
• □ A matriz Hessiana da regressão logística é constante em todo o espaço de parâmetros.
• □ Como \(\hat{y}_n \in (0, 1)\), a matriz de pesos \(S = \text{diag}(\hat{y}_n(1 - \hat{y}_n))\) é estritamente definida positiva.
• □ A perda de entropia cruzada binária é estritamente convexa quando \(X\) possui posto coluna completo, garantindo que todo ponto crítico é mínimo global único.

7 Fechamento

7.1 Retomando as Cinco Perguntas Fundamentais

1. Como o algoritmo de Descida do Gradiente é formulado e qual o limite máximo do tamanho de passo? Atualiza parâmetros iterativamente via \(\mathbf{w}_{k+1} = \mathbf{w}_k - \alpha \nabla f(\mathbf{w}_k)\). Pelo Lema de Descida quadrático derivado da \(L\)-suavidade de Lipschitz (\(\|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\| \le L \|\mathbf{x} - \mathbf{y}\|\)), a descida estrita é garantida se e somente se o passo satisfaz \(0 < \alpha < \frac{2}{L}\), com passo ótimo teórico \(\alpha^\star = \frac{1}{L}\).
2. Qual é a dinâmica exata de convergência em formas quadráticas fortemente convexas? O erro evolui como \(\mathbf{e}_{k+1} = (I - \alpha A)\mathbf{e}_k\). Pela decomposição espectral \(A = Q \Lambda Q^T\), cada autovetor desacopla em \(\tilde{e}_{k, i} = (1 - \alpha \lambda_i)^k \tilde{e}_{0, i}\). O passo ótimo de Chebyshev é \(\alpha^\star = \frac{2}{\lambda_{\max} + \lambda_{\min}}\), e a taxa de contração ótima resultante é \(\rho^\star = \frac{\kappa - 1}{\kappa + 1}\), onde \(\kappa = \text{cond}(A) = \lambda_{\max}/\lambda_{\min}\).
3. Por que o mau condicionamento causa o fenômeno de ziguezague? Em elipsóides alongados (\(\kappa \gg 1\)), o gradiente é perpendicular às curvas de nível e aponta quase transversalmente às encostas íngremes, possuindo uma projeção ínfima na direção do mínimo. O passo é limitado pelo autovalor máximo (\(\alpha < 2/\lambda_{\max}\)), paralisando o progresso ao longo do autovalor mínimo (\(1 - \alpha \lambda_{\min} \approx 1\)).
4. Como a padronização de atributos cura o mau condicionamento no California Housing? A enorme disparidade de escalas entre variáveis físicas (HouseAge \(\sim 28\) vs AveBedrms \(\sim 1\)) estica a Hessiana para \(\kappa \approx 23.460\). A padronização \(Z\)-score iguala todas as variâncias diagonais a 1, homogeneizando os autovalores (\(\tilde{\kappa} \approx 12{,}9\)) e acelerando a convergência de dezenas de milhares de passos para menos de 50 iterações.
5. Como aplicar a Descida do Gradiente na Regressão Logística? A perda de entropia cruzada não possui solução analítica fechada porque \(\mathbf{w}\) está aprisionado na função sigmoide transcendental. Seu gradiente é \(\nabla \mathcal{L} = \frac{1}{N}X^T(\hat{\mathbf{y}} - \mathbf{y})\) e sua Hessiana é \(\nabla^2 \mathcal{L} = \frac{1}{N}X^T S X \succ 0\). A Descida do Gradiente é a ferramenta universal que viabiliza o treinamento do modelo.

7.2 O Que Fica em Aberto e Limitações

Nesta aula, descobrimos que a geometria da curvatura governa a dinâmica da Descida do Gradiente e vimos como a Álgebra Linear cura o mau condicionamento estático na regressão linear via pré-condicionamento diagonal (\(Z\)-score). Mas três grandes dilemas conceituais e práticos permanecem em aberto:

7.2.1 1. O Enigma da Regressão Logística: Curvatura Dinâmica e a Insuficiência do Z-Score Estático

Na regressão linear, a Hessiana \(H = \frac{1}{N}X^T X\) é estática (constante em todo o espaço). Por isso, a padronização \(Z\)-score \(P = D^{-1/2}\) atua como um pré-condicionador de Jacobi perfeito e permanente, fixando todos os elementos diagonais em \(1\) do início ao fim do treinamento.

Porém, na regressão logística, a Hessiana é dinâmica e dependente do estado atual \(\mathbf{w}_k\): \[H(\mathbf{w}_k) = \nabla^2 \mathcal{L}(\mathbf{w}_k) = \frac{1}{N} X^T S(\mathbf{w}_k) X, \quad \text{onde } S(\mathbf{w}_k) = \operatorname{diag}\big(\hat{y}_n(1 - \hat{y}_n)\big)\] - À medida que \(\mathbf{w}_k\) evolui, as predições \(\hat{y}_n = \sigma(\mathbf{w}_k^T \mathbf{x}_n)\) se alteram: exemplos classificados com alta certeza têm \(\hat{y}_n \approx 0\) ou \(1 \implies S_{nn} \approx 0\) (saturação), enquanto exemplos próximos à fronteira de decisão têm \(S_{nn} \approx 0{,}25\). - O \(Z\)-score padroniza as colunas de \(X\) e elimina disparidades brutas de unidades físicas, mas corrige apenas parte do problema: ele não consegue compensar a matriz de pesos \(S(\mathbf{w}_k)\), que deforma e gira continuamente os autovetores e autovalores da Hessiana ao longo da trajetória! - Não existe um pré-condicionador fixo único capaz de manter a bacia isotrópica em todas as regiões do espaço.

7.2.2 2. A Motivação para Métodos de Segunda Ordem: O Método de Newton (IRLS)

Se a curvatura muda a cada passo \(\mathbf{w}_k\), a resposta natural da Álgebra Linear é: adaptar o pré-condicionamento dinamicamente a cada iteração! Em vez de uma matriz fixa \(P\), usamos a própria inversa da Hessiana local como matriz condicionadora: \[\mathbf{w}_{k+1} = \mathbf{w}_k - [H(\mathbf{w}_k)]^{-1} \nabla \mathcal{L}(\mathbf{w}_k)\] Esse é o célebre Método de Newton-Raphson (que na regressão logística torna-se o algoritmo Iteratively Reweighted Least Squares - IRLS), que distorce localmente a bacia elíptica em uma esfera perfeita a cada passo, atingindo convergência quadrática.

7.2.3 3. A Motivação para Métodos de Momento: Inércia contra o Ziguezague

Calcular e inverter a Hessiana \(H(\mathbf{w}_k) \in \mathbb{R}^{d \times d}\) a cada iteração custa \(O(Nd^2 + d^3)\), tornando-se proibitivo quando a dimensão \(d\) é grande. Se só podemos pagar o custo de primeira ordem \(O(Nd)\), como enfrentar ravinas estreitas com curvatura oscilante sem sofrer com o ziguezague patológico? A solução é adicionar inércia física (momento): ao acumular uma média móvel dos gradientes anteriores, o algoritmo cancela as oscilações transversais opostas nas paredes do cânion e soma construtivamente o avanço ao longo do fundo do vale.

DicaPonte para a Aula 9

Na próxima aula (Aula 9: Séries de Taylor e a Regra da Cadeia Multivariada), investigaremos o que acontece quando abandonamos a linearidade nos parâmetros e avançamos para funções altamente compostas, como as Redes Neurais (Multilayer Perceptrons): 1. O Teorema de Taylor Multivariado, formalizando as aproximações de 1ª e 2ª ordens com seus respectivos restos e provando como o passo de Gradient Descent decorre da minimização da aproximação linear sob uma região de confiança proximal. 2. A Regra da Cadeia Multivariada e Backpropagation, deduzindo matricialmente a propagação retrógrada de erros e sensibilidades através de camadas não-lineares.

Exercícios Soluções