Soluções — Aula 8: Otimização Irrestrita e Descida do Gradiente

Otimização e Álgebra Linear para Machine Learning

Autor

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

Data de Publicação

21 de outubro de 2026

Dica

Este documento apresenta o gabarito detalhado das questões de Verdadeiro ou Falso da folha de exercícios. Cada afirmação é acompanhada de sua justificativa matemática formal.

Teste 1: Fundamentos da Descida do Gradiente e Direção de Descida

Afirmações

□ A direção \(-\nabla f(\mathbf{x})\) é matematicamente a direção de maior decréscimo local instantâneo, no sentido de minimizar a derivada direcional \(D_{\mathbf{v}}f(\mathbf{x})\) sobre todos os vetores unitários \(\|\mathbf{v}\|_2 = 1\).
□ Se \(\nabla f(\mathbf{x}_k) \ne \mathbf{0}\), existe sempre algum \(\alpha > 0\) suficientemente pequeno tal que \(f(\mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k)) < f(\mathbf{x}_k)\).
□ O algoritmo de Descida do Gradiente sempre converge em tempo finito para um ponto onde o gradiente é rigorosamente nulo.
□ Em um ponto crítico \(\mathbf{x}^\star\) onde \(\nabla f(\mathbf{x}^\star) = \mathbf{0}\), a iteração da Descida do Gradiente com passo \(\alpha > 0\) permanece estacionária (\(\mathbf{x}_{k+1} = \mathbf{x}_k\)).

Justificativas

✔ V: A derivada direcional é \(D_{\mathbf{v}}f = \nabla f^T \mathbf{v} = \|\nabla f\| \cos\theta\), cujo valor mínimo ocorre quando \(\cos\theta = -1\), ou seja, na direção \(-\nabla f\).
✔ V: Pela aproximação de primeira ordem, \(f(\mathbf{x} - \alpha \nabla f) = f(\mathbf{x}) - \alpha \|\nabla f\|^2 + o(\alpha)\); para \(\alpha\) suficientemente pequeno, o termo linear negativo domina.
✗ F: A Descida do Gradiente gera uma sequência infinita que se aproxima assintoticamente do ponto crítico (\(\lim_{k \to \infty} \nabla f(\mathbf{x}_k) = \mathbf{0}\)), exigindo um critério de parada finito \(\|\nabla f\| \le \epsilon\).
✔ V: Se \(\nabla f(\mathbf{x}^\star) = \mathbf{0}\), o termo de atualização é \(-\alpha \mathbf{0} = \mathbf{0}\), mantendo o ponto fixo.

Teste 2: Suavidade de Lipschitz e Escolha de Hiperparâmetros

Afirmações

□ Para uma função convexa com gradiente \(L\)-Lipschitziano, escolher um tamanho de passo constante \(\alpha = \frac{1}{L}\) garante que a sequência de valores \(f(\mathbf{x}_k)\) é monotonicamente não crescente.
□ Se uma função de perda possui \(\nabla^2 f(\mathbf{x}) \preceq 50 I\) em todo o domínio, a Descida do Gradiente com passo \(\alpha = 0{,}05\) tem divergência numérica garantida.
□ O valor da constante de Lipschitz \(L\) para a função \(f(x) = x^4\) em \(\mathbb{R}\) é constante e igual a 12.
□ Uma função fortemente convexa que é também \(L\)-suave satisfaz \(m I \preceq \nabla^2 f(\mathbf{x}) \preceq L I\) para constantes \(0 < m \le L < \infty\).

Justificativas

✔ V: Pelo Lema de Descida, \(\alpha = 1/L\) garante que \(f(\mathbf{x}_{k+1}) \le f(\mathbf{x}_k) - \frac{1}{2L}\|\nabla f(\mathbf{x}_k)\|^2 \le f(\mathbf{x}_k)\).
✗ F: Se \(L = 50\), o passo máximo de estabilidade é \(\alpha_{\text{crit}} = 2/L = 2/50 = 0{,}04\). Com \(\alpha = 0{,}05 > 0{,}04\), o método de fato divergirá em problemas quadráticos.
✗ F: Para \(f(x) = x^4\), a segunda derivada é \(f''(x) = 12x^2\), que cresce sem limite quando \(x \to \infty\); ela não é globalmente Lipschitziana.
✔ V: É a definição de funções com curvatura limitada inferiormente por \(m > 0\) (forte convexidade) e superiormente por \(L\) (\(L\)-suavidade).

Teste 3: Análise Espectral e Dinâmica de Convergência em Quadráticas

Afirmações

□ Em uma função quadrática \(f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T A \mathbf{x} - \mathbf{b}^T \mathbf{x}\) com \(A \succ 0\), o passo 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 da direção do autovetor \(\mathbf{v}_i\) oscila alternando de sinal a cada iteração.
□ Se todos os autovalores da matriz Hessiana forem rigorosamente iguais (\(\lambda_1 = \lambda_2 = \dots = \lambda_d\)), 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 para determinados valores de \(\alpha\).

Justificativas

✔ V: A condição \(|1 - \alpha \lambda_{\max}| < 1\) exige rigorosamente \(\alpha < 2/\lambda_{\max}\).
✔ V: Para \(1/\lambda_i < \alpha < 2/\lambda_i\), temos \(-1 < 1 - \alpha \lambda_i < 0\), de modo que \((1 - \alpha \lambda_i)^k\) inverte de sinal a cada passo mantendo decaimento em módulo.
✗ F: Se todos os autovalores são idênticos (\(\kappa = 1\)), a contração é total em uma única iteração (\(k=1\)), não em \(d\) iterações.
✗ F: O raio espectral de qualquer matriz é o módulo do maior autovalor (\(\rho(M) = \max_i |\lambda_i(M)|\)), sendo por definição um número real não negativo (\(\ge 0\)).

Teste 4: O Número de Condição e a Patologia do Ziguezague

Afirmações

□ Em uma tigela quadrática alongada onde o número de condição \(\kappa = \text{cond}(A)\) é muito grande (\(\kappa \gg 1\)), o vetor \(-\nabla f(\mathbf{x})\) aponta quase diretamente para o minimizador global \(\mathbf{x}^\star\).
□ A taxa assintótica de contração ótima do erro \(\rho^\star = \frac{\kappa - 1}{\kappa + 1}\) aproxima-se de 1 quando o número de condição \(\kappa \to \infty\).
□ Se \(\kappa = 10.000\), a cada iteração do Gradient Descent com passo ótimo, o erro diminui em menos de \(0{,}05\%\).
□ A presença de ziguezague intenso na Descida do Gradiente indica obrigatoriamente que a função objetivo não é convexa.

Justificativas

✗ F: Em elipsóides alongados, o vetor gradiente é ortogonal às elipses e aponta quase transversalmente ao eixo longo onde reside o mínimo, gerando ziguezague em vez de apontar para o centro.
✔ V: Quando \(\kappa \to \infty\), \(\frac{\kappa - 1}{\kappa + 1} \to 1\), indicando que a taxa de contração torna-se arbitrariamente lenta.
✔ V: Com \(\kappa = 10.000\), \(\rho^\star = \frac{9999}{10001} \approx 0{,}9998\), de modo que o erro diminui apenas \(\approx 0{,}02\%\) por passo.
✗ F: O ziguezague é típico de formas quadráticas perfeitamente convexas com Hessiana mal condicionada (\(A \succ 0\) com \(\lambda_{\max} \gg \lambda_{\min}\)).

Teste 5: Impacto Algébrico da Padronização de Atributos

Afirmações

□ A padronização \(Z\)-score transforma cada coluna da matriz de projeto para média amostral zero e variância unitária, preservando a linearidade do espaço.
□ Se duas colunas de \(X\) forem fortemente correlacionadas linearmente (\(r \approx 0{,}999\)), a padronização \(Z\)-score reduz o número de condição de \(X^T X\) para \(\kappa \approx 1\).
□ O algoritmo de Descida do Gradiente com passo constante é sensível à escala dos atributos, enquanto o método clássico de Newton-Raphson é invariante a transformações afins invertíveis.
□ Padronizar atributos melhora o condicionamento da Hessiana ao aproximar os elementos da diagonal principal da matriz de covariância.

Justificativas

✔ V: A padronização subtrai a média e divide pelo desvio-padrão (transformação afim invertível coluna a coluna).
✗ F: A padronização apenas iguala a variância diagonal (\(\sigma_j^2 = 1\)). Se duas colunas forem fortemente correlacionadas, o determinante de \(\tilde{X}^T \tilde{X}\) continuará próximo de zero e o menor autovalor será muito pequeno, mantendo \(\kappa \gg 1\).
✔ V: A direção \(-\nabla f\) depende da métrica euclidiana adotada, enquanto o passo de Newton \(-( \nabla^2 f)^{-1}\nabla f\) incorpora a métrica da curvatura e é afim-invariante.
✔ V: A padronização torna todos os elementos diagonais de \(\frac{1}{N}X^TX\) iguais a 1, eliminando disparidades de escala puramente artificiais.

Teste 6: Regressão Logística e Perdas Transcendetais

Afirmações

□ A perda de Entropia Cruzada Binária na regressão logística admite uma solução em forma fechada para o vetor ótimo \(\mathbf{w}^\star\) calculável via decomposição SVD.
□ A matriz de pesos diagonais \(S = \text{diag}(\hat{y}_n(1 - \hat{y}_n))\) na Hessiana da regressão logística atinge seus valores máximos para observações onde o modelo tem extrema certeza da classe (\(\hat{y}_n \approx 0\) ou \(\hat{y}_n \approx 1\)).
□ Como \(0 < \hat{y}_n < 1\) para todo \(\mathbf{w}\) finito, a matriz \(S\) é diagonal estritamente positiva, garantindo que \(\nabla^2 \mathcal{L}(\mathbf{w}) \succeq 0\) e que a perda é sempre convexa.
□ Na regressão logística, o gradiente \(\nabla \mathcal{L}(\mathbf{w}) = \frac{1}{N}X^T(\hat{\mathbf{y}} - \mathbf{y})\) é nulo se e somente se as predições do modelo coincidirem com os alvos para todas as observações onde isso for numericamente possível.

Justificativas

✗ F: A equação \(\nabla \mathcal{L} = \mathbf{0}\) na regressão logística é não linear transcendental e não admite inversão via SVD ou matrizes fechadas.
✗ F: Como \(s_{nn} = \hat{y}_n(1 - \hat{y}_n)\), se \(\hat{y}_n \approx 0\) ou \(\hat{y}_n \approx 1\), \(s_{nn} \approx 0\) (saturação). O valor máximo ocorre para casos ambíguos na fronteira (\(\hat{y}_n = 0{,}5 \implies s_{nn} = 0{,}25\)).
✔ V: Com \(0 < \hat{y}_n < 1\), temos \(S \succ 0\), o que garante \(X^TSX \succeq 0\) e convexidade global da perda.
✔ V: O gradiente é \(\frac{1}{N}X^T(\hat{\mathbf{y}} - \mathbf{y})\); quando o ajuste é ótimo, o vetor residual ponderado ortogonaliza-se com as colunas de \(X\).