Exercícios — Aula 8: Otimização Irrestrita e Descida do Gradiente

Otimização e Álgebra Linear para Machine Learning

Aula Soluções

DicaContexto e Notação

Nesta lista, consideramos problemas de otimização contínua irrestrita em aprendizado de máquina da forma: \[\min_{\mathbf{w} \in \mathbb{R}^d} f(\mathbf{w})\] onde \(f: \mathbb{R}^d \to \mathbb{R}\) é uma função de perda duas vezes continuamente diferenciável (\(C^2\)).

• \(\nabla f(\mathbf{w}) \in \mathbb{R}^d\) é o vetor gradiente formatado como vetor-coluna;
• \(\nabla^2 f(\mathbf{w}) \in \mathbb{R}^{d \times d}\) é a matriz Hessiana simétrica;
• A iteração da Descida do Gradiente com tamanho de passo fixo \(\alpha > 0\) é dada por: \[\mathbf{w}_{k+1} = \mathbf{w}_k - \alpha \nabla f(\mathbf{w}_k)\]
• Uma função tem gradiente \(L\)-Lipschitziano (\(L\)-suave) se \(\|\nabla f(\mathbf{u}) - \nabla f(\mathbf{v})\|_2 \le L \|\mathbf{u} - \mathbf{v}\|_2\) para todos \(\mathbf{u}, \mathbf{v}\), o que equivale a \(\nabla^2 f(\mathbf{w}) \preceq L I\);
• Para uma forma quadrática estritamente convexa \(f(\mathbf{w}) = \frac{1}{2}\mathbf{w}^T A \mathbf{w} - \mathbf{b}^T \mathbf{w}\) com \(A \succ 0\):
  • \(\lambda_{\max} = \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_d = \lambda_{\min} > 0\) são os autovalores de \(A\);
  • \(\kappa = \text{cond}(A) = \frac{\lambda_{\max}}{\lambda_{\min}} \ge 1\) é o número de condição espectral da Hessiana;
  • \(\rho(M)\) denota o raio espectral de uma matriz quadrada \(M\);
• Na Regressão Logística, dados \(N\) pares \((\mathbf{x}_n, y_n)\) com \(\mathbf{x}_n \in \mathbb{R}^d\) e \(y_n \in \{0, 1\}\):
  • \(\sigma(z) = \frac{1}{1 + e^{-z}}\) é a função logística sigmoide;
  • \(\hat{y}_n = \sigma(\mathbf{w}^T \mathbf{x}_n)\) é a probabilidade predita;
  • A perda de Entropia Cruzada Binária média é \(\mathcal{L}(\mathbf{w}) = -\frac{1}{N}\sum_{n=1}^N [y_n \ln \hat{y}_n + (1 - y_n)\ln(1 - \hat{y}_n)]\).

Questões discursivas

1. O Lema de Descida e o Limite Teórico do Tamanho de Passo: Considere uma função convexa \(f: \mathbb{R}^d \to \mathbb{R}\) cujo gradiente é \(L\)-Lipschitziano.
   1. Pelo Teorema Fundamental do Cálculo, mostre que \(f(\mathbf{y}) = f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y} - \mathbf{x}) + \int_0^1 (\nabla f(\mathbf{x} + t(\mathbf{y}-\mathbf{x})) - \nabla f(\mathbf{x}))^T (\mathbf{y} - \mathbf{x}) \, dt\).
   2. Utilizando a propriedade de Cauchy-Schwarz e a hipótese de Lipschitz \(\|\nabla f(\mathbf{u}) - \nabla f(\mathbf{v})\| \le L \|\mathbf{u} - \mathbf{v}\|\), deduza o Lema de Descida (Descent Lemma): \[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. Aplicando um passo da Descida do Gradiente \(\mathbf{y} = \mathbf{x} - \alpha \nabla f(\mathbf{x})\), mostre que: \[f(\mathbf{x}_{k+1}) \le f(\mathbf{x}_k) - \alpha \left(1 - \frac{\alpha L}{2}\right) \|\nabla f(\mathbf{x}_k)\|_2^2\] A partir dessa desigualdade, determine a faixa exata de valores de \(\alpha > 0\) que garante decréscimo estrito da função de perda (\(f(\mathbf{x}_{k+1}) < f(\mathbf{x}_k)\) para \(\nabla f(\mathbf{x}_k) \ne \mathbf{0}\)) e encontre o valor de \(\alpha\) que maximiza a cota teórica de redução da perda em uma única iteração.
2. Dedução Exata da Taxa de Convergência e do Fator de Contração de Chebyshev: Considere o problema quadrático \(\min_{\mathbf{w}} 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 positiva definida com autovalores \(\lambda_{\max} \ge \dots \ge \lambda_{\min} > 0\). Seja \(\mathbf{w}^\star = A^{-1}\mathbf{b}\) o minimizador global único.
   1. Mostre que o erro \(\mathbf{e}_k = \mathbf{w}_k - \mathbf{w}^\star\) evolui linearmente segundo a equação em diferenças \(\mathbf{e}_{k+1} = (I - \alpha A)\mathbf{e}_k\).
   2. Utilizando a decomposição espectral \(A = Q \Lambda Q^T\), prove que o erro na base dos autovetores \(\tilde{\mathbf{e}}_k = Q^T \mathbf{e}_k\) satisfaz \(\tilde{e}_{k+1, i} = (1 - \alpha \lambda_i) \tilde{e}_{k, i}\) para cada \(i \in \{1, \dots, d\}\).
   3. Para garantir que \(\lim_{k \to \infty} \mathbf{e}_k = \mathbf{0}\) para qualquer inicialização, deduza a condição necessária e suficiente sobre \(\alpha\) em termos de \(\lambda_{\max}\).
   4. O raio espectral de contração é \(\rho(\alpha) = \max_{i} |1 - \alpha \lambda_i| = \max\{|1 - \alpha \lambda_{\min}|, |1 - \alpha \lambda_{\max}|\}\). Prove formalmente que o valor de \(\alpha\) que minimiza o raio espectral (passo ótimo de Chebyshev) é: \[\alpha^\star = \frac{2}{\lambda_{\max} + \lambda_{\min}}\] e que a taxa de contração ótima resultante é dada exclusivamente pelo número de condição \(\kappa = \frac{\lambda_{\max}}{\lambda_{\min}}\): \[\rho^\star = \frac{\kappa - 1}{\kappa + 1}\]
3. Geometria de Escalas e Padronização no Problema dos Mínimos Quadrados: Considere uma matriz de dados \(X \in \mathbb{R}^{N \times 2}\) onde o atributo 1 possui variância amostral \(\sigma_1^2 = 1\) e o atributo 2 possui variância amostral \(\sigma_2^2 = 10.000\), sem correlação entre eles (\(X^T X = \text{diag}(N, 10000 N)\)). A perda é \(L(\boldsymbol\beta) = \frac{1}{2N}\|X\boldsymbol\beta - \mathbf{y}\|_2^2\).
   1. Determine a matriz Hessiana \(\nabla^2 L(\boldsymbol\beta)\), seus autovalores e o número de condição \(\kappa = \text{cond}(\nabla^2 L)\).
   2. Calcule o maior tamanho de passo \(\alpha_{\text{crit}}\) que ainda impede a divergência do Gradient Descent nos dados brutos.
   3. Com o passo ótimo \(\alpha^\star\), calcule quantas iterações são necessárias para reduzir a norma do erro em \(99\%\) (\(\|\mathbf{e}_k\| \le 0{,}01 \|\mathbf{e}_0\|\)).
   4. Suponha que aplicamos a padronização \(Z\)-score nas colunas de \(X\). Calcule a nova Hessiana \(\nabla^2 \tilde{L}\), o novo número de condição \(\tilde{\kappa}\) e a nova quantidade de iterações necessárias para obter a mesma redução de \(99\%\). Compare os resultados.
4. Derivação Analítica Completa do Gradiente e Hessiana da Regressão Logística: Dada a função de perda média da regressão logística: \[\mathcal{L}(\mathbf{w}) = -\frac{1}{N}\sum_{n=1}^N \left[ y_n \ln \sigma(\mathbf{w}^T \mathbf{x}_n) + (1 - y_n) \ln(1 - \sigma(\mathbf{w}^T \mathbf{x}_n)) \right]\]
   1. Mostre primeiramente que a derivada da função sigmoide satisfaz \(\sigma'(z) = \sigma(z)(1 - \sigma(z))\).
   2. Utilizando a regra da cadeia multivariada com gradientes em vetor-coluna, deduza a expressão analítica do vetor gradiente \(\nabla \mathcal{L}(\mathbf{w}) \in \mathbb{R}^d\) e escreva-o na forma matricial compacta: \[\nabla \mathcal{L}(\mathbf{w}) = \frac{1}{N} X^T (\hat{\mathbf{y}} - \mathbf{y})\] onde \(\hat{\mathbf{y}} = (\sigma(\mathbf{w}^T \mathbf{x}_1), \dots, \sigma(\mathbf{w}^T \mathbf{x}_N))^T\).
   3. Derive a matriz Hessiana \(\nabla^2 \mathcal{L}(\mathbf{w}) \in \mathbb{R}^{d \times d}\) e mostre que ela pode ser expressa como: \[\nabla^2 \mathcal{L}(\mathbf{w}) = \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))\). Prove que, se \(X\) possui posto coluna completo (\(rk(X) = d\)), então \(\nabla^2 \mathcal{L}(\mathbf{w}) \succ 0\) para qualquer \(\mathbf{w} \in \mathbb{R}^d\).

---

Questões de Verdadeiro/Falso

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

• □ 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\)).

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

• □ 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\).

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

• □ 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\).

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

• □ 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.

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

• □ 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.

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

• □ 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.