Phase 01 - Lesson 18

Otimização Convexa

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Problemas convexos têm um único vale. Redes neurais têm milhões. Saber a diferença importa.

Tipo: Construir Linguagem: Python Pré-requisitos: Fase 1, Lições 04 (Cálculo para ML), 08 (Otimização) Tempo: ~90 minutos

Objetivos de Aprendizagem

• Testar se uma função é convexa usando a definição, a segunda derivada e os critérios da Hessiana
• Implementar o método de Newton e comparar sua convergência quadrática com a descida do gradiente
• Resolver problemas de otimização com restrições usando multiplicadores de Lagrange e interpretar as condições KKT
• Explicar por que as superfícies de loss de redes neurais são não convexas e ainda assim o SGD encontra boas soluções

O Problema

A Lição 08 ensinou descida do gradiente, momentum e Adam. Esses otimizadores descem qualquer superfície. Mas não vêm com garantias. A descida do gradiente em uma superfície não convexa pode parar em um mínimo local ruim, ficar presa em um ponto de sela ou oscilar para sempre. Você a usou mesmo assim porque redes neurais são não convexas e não há alternativa.

Mas muitos problemas em machine learning são convexos. Regressão linear, regressão logística, SVMs, LASSO, regressão ridge. Para esses, algo mais forte existe: otimização com garantias matemáticas. Um problema convexo tem exatamente um vale. Qualquer algoritmo que desça vai alcançar o mínimo global. Sem necessidade de reinícios. Sem cronogramas de taxa de aprendizado. Sem reza.

Entender a convexidade faz três coisas. Primeiro, ela diz quando seu problema é fácil (convexo) versus difícil (não convexo). Segundo, ela fornece ferramentas mais rápidas como o método de Newton para problemas convexos. Terceiro, ela explica conceitos que aparecem em todo o ML: regularização como restrição, dualidade em SVMs e por que deep learning funciona apesar de violar todas as boas propriedades que a convexidade oferece.

O Conceito

Conjuntos convexos

Um conjunto S é convexo se, para quaisquer dois pontos em S, o segmento de reta entre eles também estiver inteiramente em S.

Teste formal: para quaisquer pontos x, y em S e qualquer t em [0, 1], o ponto tx + (1-t)y também está em S.

Exemplos de conjuntos convexos:

• Uma reta, um plano, todo o R^n
• Uma bola (círculo, esfera, hiperesfera)
• Um semiespaço: {x : a^T x <= b}
• A interseção de qualquer número de conjuntos convexos

Exemplos de conjuntos não convexos:

• Uma rosquinha (anel)
• A união de dois círculos disjuntos
• Qualquer conjunto com uma "reentrância" ou "buraco"

Funções convexas

Uma função f é convexa se seu domínio é um conjunto convexo e, para quaisquer dois pontos x, y em seu domínio e qualquer t em [0, 1]:

f(tx + (1-t)y) <= t*f(x) + (1-t)*f(y)

Geometricamente: o segmento de reta entre quaisquer dois pontos no gráfico está acima ou sobre o gráfico.

Funções convexas comuns:

• f(x) = x^2 (parábola)
• f(x) = |x| (valor absoluto)
• f(x) = e^x (exponencial)
• f(x) = max(0, x) (ReLU, embora linear por partes)
• f(x) = -log(x) para x > 0 (log negativo)
• Qualquer função linear f(x) = a^T x + b (tanto convexa quanto côncava)

Testando a convexidade

Três testes práticos, do mais fácil ao mais rigoroso.

Teste 1: Teste da segunda derivada (1D). Se f''(x) >= 0 para todo x, então f é convexa.

• f(x) = x^2: f''(x) = 2 >= 0. Convexa.
• f(x) = x^3: f''(x) = 6x. Negativa para x < 0. Não convexa.
• f(x) = e^x: f''(x) = e^x > 0. Convexa.

Teste 2: Teste da Hessiana (multivariável). Se a matriz Hessiana H(x) é positiva semidefinida para todo x, então f é convexa. A Hessiana é a matriz das segundas derivadas parciais.

Teste 3: Teste da definição. Verifique a desigualdade f(tx + (1-t)y) <= t*f(x) + (1-t)*f(y) diretamente. Útil para funções onde as derivadas são difíceis de computar.

Por que a convexidade importa

O teorema central da otimização convexa:

Para uma função convexa, todo mínimo local é um mínimo global.

Isso significa que a descida do gradiente não pode ficar presa. Qualquer caminho descendente leva à mesma resposta. O algoritmo tem garantia de convergir para a solução ótima.

graph LR
    subgraph "Convex: ONE answer"
        direction TB
        C1["Loss surface has a single valley"] --> C2["Gradient descent ALWAYS finds the global minimum"]
    end
    subgraph "Non-convex: MANY traps"
        direction TB
        N1["Loss surface has multiple valleys and peaks"] --> N2["Gradient descent may get stuck in a local minimum"]
        N2 --> N3["Global minimum might be missed"]
    end

Consequências:

• Sem necessidade de reinícios aleatórios
• Sem necessidade de cronogramas sofisticados de taxa de aprendizado
• Provas de convergência são possíveis (a taxa depende das propriedades da função)
• A solução é única (a menos de regiões planas)

Convexo vs não convexo em ML

Modelos lineares com losses convexas são convexos. No momento em que você adiciona camadas ocultas com ativações não lineares, a convexidade se quebra.

A matriz Hessiana

A Hessiana H de uma função f: R^n -> R é a matriz n x n das segundas derivadas parciais.

H[i][j] = d^2 f / (dx_i dx_j)

Para f(x, y) = x^2 + 3xy + y^2:

df/dx = 2x + 3y       d^2f/dx^2 = 2      d^2f/dxdy = 3
df/dy = 3x + 2y       d^2f/dydx = 3      d^2f/dy^2 = 2

H = [ 2  3 ]
    [ 3  2 ]

A Hessiana informa sobre a curvatura:

• Autovalores todos positivos: a função curva para cima em todas as direções (convexa naquele ponto)
• Autovalores todos negativos: curva para baixo em todas as direções (côncava, um máximo local)
• Sinais mistos: ponto de sela (curva para cima em algumas direções, para baixo em outras)
• Autovalor zero: plano naquela direção (degenerado)

Para a convexidade, a Hessiana deve ser positiva semidefinida (todos os autovalores >= 0) em todo lugar, não apenas em um ponto.

Método de Newton

A descida do gradiente usa informação de primeira ordem (o gradiente). O método de Newton usa informação de segunda ordem (a Hessiana). Ele ajusta uma aproximação quadrática no ponto atual e salta diretamente para o mínimo dessa quadrática.

Update rule:
  x_new = x - H^(-1) * gradient

Compare to gradient descent:
  x_new = x - lr * gradient

O método de Newton substitui a taxa de aprendizado escalar pela inversa da Hessiana. Isso ajusta automaticamente o tamanho e a direção do passo com base na curvatura local.

graph TD
    subgraph "Gradient Descent"
        GD1["Start"] --> GD2["Step 1"]
        GD2 --> GD3["Step 2"]
        GD3 --> GD4["..."]
        GD4 --> GD5["Step ~500: Converged"]
        GD_note["Follows gradient blindly — many small steps"]
    end
    subgraph "Newton's Method"
        NM1["Start"] --> NM2["Step 1"]
        NM2 --> NM3["..."]
        NM3 --> NM4["Step ~5: Converged"]
        NM_note["Uses curvature for optimal steps"]
    end

Vantagens:

• Convergência quadrática perto do mínimo (o erro é elevado ao quadrado a cada passo)
• Sem taxa de aprendizado para ajustar
• Invariante a escala (funciona independentemente de como você parametriza o problema)

Desvantagens:

• Computar a Hessiana custa O(n^2) de memória e O(n^3) para inverter
• Para uma rede neural com 1 milhão de pesos, isso é 10^12 entradas e 10^18 operações
• Não é prático para deep learning

Otimização com restrições

Otimização sem restrições: minimizar f(x) sobre todos os x. Otimização com restrições: minimizar f(x) sujeito a restrições.

Problemas reais têm restrições. Você quer minimizar o custo, mas seu orçamento é limitado. Você quer minimizar o erro, mas a complexidade do seu modelo é limitada.

graph LR
    subgraph "Unconstrained"
        U1["Loss function"] --> U2["Free minimum: lowest point of the loss surface"]
    end
    subgraph "Constrained"
        C1["Loss function"] --> C2["Constrained minimum: lowest point within the feasible region"]
        C3["Constraint boundary limits the search space"]
    end

Multiplicadores de Lagrange

O método dos multiplicadores de Lagrange converte um problema com restrições em um sem restrições.

Problema: minimizar f(x) sujeito a g(x) = 0.

Solução: introduzir uma nova variável (o multiplicador de Lagrange lambda) e resolver o problema sem restrições:

L(x, lambda) = f(x) + lambda * g(x)

Na solução, o gradiente de L é zero:

dL/dx = df/dx + lambda * dg/dx = 0
dL/dlambda = g(x) = 0

Intuição geométrica: no mínimo com restrições, o gradiente de f deve ser paralelo ao gradiente da restrição g. Se não fossem paralelos, você poderia se mover ao longo da superfície de restrição e reduzir f ainda mais.

graph LR
    A["Contours of f(x,y): concentric ellipses"] --- S["Solution point"]
    B["Constraint curve g(x,y) = 0"] --- S
    S --- C["At the solution, gradient of f is parallel to gradient of g"]

Exemplo: minimizar f(x,y) = x^2 + y^2 sujeito a x + y = 1.

L = x^2 + y^2 + lambda(x + y - 1)

dL/dx = 2x + lambda = 0  =>  x = -lambda/2
dL/dy = 2y + lambda = 0  =>  y = -lambda/2
dL/dlambda = x + y - 1 = 0

From first two: x = y
Substituting: 2x = 1, so x = y = 0.5, lambda = -1

O ponto mais próximo da origem na reta x + y = 1 é (0.5, 0.5).

Condições KKT

As condições de Karush-Kuhn-Tucker estendem os multiplicadores de Lagrange para restrições de desigualdade.

Problema: minimizar f(x) sujeito a g_i(x) <= 0 para i = 1, ..., m.

As condições KKT (necessárias para a otimalidade):

1. Stationarity:    df/dx + sum(lambda_i * dg_i/dx) = 0
2. Primal feasibility:  g_i(x) <= 0  for all i
3. Dual feasibility:    lambda_i >= 0  for all i
4. Complementary slackness:  lambda_i * g_i(x) = 0  for all i

A folga complementar é a percepção-chave: ou a restrição está ativa (g_i = 0, a solução está sobre a fronteira) ou o multiplicador é zero (a restrição não importa). Uma restrição que não afeta a solução tem lambda = 0.

As condições KKT são centrais para os SVMs. Os vetores de suporte são os pontos de dados onde a restrição está ativa (lambda > 0). Todos os outros pontos de dados têm lambda = 0 e não afetam a fronteira de decisão.

Regularização como otimização com restrições

As regularizações L1 e L2 não são truques arbitrários. Elas são problemas de otimização com restrições disfarçados.

Regularização L2 (Ridge):

minimize  Loss(w)  subject to  ||w||^2 <= t

Equivalent unconstrained form:
minimize  Loss(w) + lambda * ||w||^2

A restrição ||w||^2 <= t define uma bola (círculo em 2D, esfera em 3D). A solução é onde as curvas de nível do loss tocam essa bola pela primeira vez.

Regularização L1 (LASSO):

minimize  Loss(w)  subject to  ||w||_1 <= t

Equivalent unconstrained form:
minimize  Loss(w) + lambda * ||w||_1

A restrição ||w||_1 <= t define um losango (quadrado rotacionado em 2D).

Isso explica por que a L1 produz modelos esparsos (seleção de features) enquanto a L2 apenas encolhe os pesos. O losango tem vértices alinhados com os eixos. As curvas de nível do loss têm maior probabilidade de tocar um vértice, fixando um ou mais pesos exatamente em zero.

Dualidade

Todo problema de otimização com restrições (o primal) tem um problema companheiro (o dual). Para problemas convexos, o primal e o dual têm o mesmo valor ótimo. Isso é a dualidade forte.

A função dual de Lagrange:

Primal: minimize f(x) subject to g(x) <= 0
Lagrangian: L(x, lambda) = f(x) + lambda * g(x)
Dual function: d(lambda) = min_x L(x, lambda)
Dual problem: maximize d(lambda) subject to lambda >= 0

Por que a dualidade importa:

• O problema dual às vezes é mais fácil de resolver que o primal
• Os SVMs são resolvidos em sua forma dual, onde o problema depende de produtos escalares entre pontos de dados (viabilizando o truque do kernel)
• O dual fornece um limite inferior para o ótimo do primal, útil para verificar a qualidade da solução

Para os SVMs especificamente:

Primal: find w, b that maximize the margin 2/||w|| subject to
        y_i(w^T x_i + b) >= 1 for all i

Dual:   maximize sum(alpha_i) - 0.5 * sum_ij(alpha_i * alpha_j * y_i * y_j * x_i^T x_j)
        subject to alpha_i >= 0 and sum(alpha_i * y_i) = 0

The dual only involves dot products x_i^T x_j.
Replace x_i^T x_j with K(x_i, x_j) to get the kernel trick.

Por que deep learning funciona apesar da não convexidade

As funções de loss de redes neurais são extremamente não convexas. Por toda medida clássica, otimizá-las deveria falhar. Ainda assim, a descida do gradiente estocástica encontra boas soluções de forma confiável. Vários fatores explicam isso.

A maioria dos mínimos locais é boa o suficiente. Em espaços de alta dimensão, pontos críticos aleatórios (onde o gradiente é zero) são esmagadoramente pontos de sela, não mínimos locais. Os poucos mínimos locais que existem tendem a ter valores de loss próximos ao mínimo global. Ficar preso em um mínimo local terrível é extremamente improvável quando o espaço de parâmetros tem milhões de dimensões.

Pontos de sela, não mínimos locais, são o real obstáculo. Em uma função com n parâmetros, um ponto de sela tem uma mistura de direções de curvatura positiva e negativa. Para um ponto crítico aleatório em alta dimensão, a probabilidade de todos os n autovalores serem positivos (mínimo local) é cerca de 2^(-n). Quase todos os pontos críticos são pontos de sela. O ruído do SGD ajuda a escapar deles.

A superparametrização suaviza a superfície. Redes com mais parâmetros do que exemplos de treinamento têm superfícies de loss mais suaves e mais conectadas. Redes mais largas têm menos mínimos locais ruins. Isso é contraintuitivo, mas empiricamente consistente.

Estrutura da superfície de loss:

O ruído estocástico age como regularização implícita. O SGD em mini-batch adiciona ruído que impede o assentamento em mínimos agudos. Mínimos agudos sofrem overfitting; mínimos planos generalizam. O ruído enviesa a otimização em direção a regiões planas da superfície de loss.

Métodos de segunda ordem na prática

O método de Newton puro é impraticável para modelos grandes. Várias aproximações tornam a informação de segunda ordem utilizável.

L-BFGS (BFGS de memória limitada): Aproxima a inversa da Hessiana usando as últimas m diferenças de gradiente. Requer O(mn) de memória em vez de O(n^2). Funciona bem para problemas com até ~10.000 parâmetros. Usado em ML clássico (regressão logística, CRFs), mas não em deep learning.

Gradiente natural: Usa a matriz de informação de Fisher (a Hessiana esperada da log-verossimilhança) em vez da Hessiana padrão. Isso leva em conta a geometria das distribuições de probabilidade. O K-FAC (Kronecker-Factored Approximate Curvature) aproxima a matriz de Fisher como um produto de Kronecker, tornando-a prática para redes neurais.

Otimização sem Hessiana (Hessian-free): Usa o gradiente conjugado para resolver Hx = g sem nunca formar H. Requer apenas produtos Hessiana-vetor, que podem ser computados em tempo O(n) via diferenciação automática.

Aproximações diagonais: O segundo momento do Adam é uma aproximação diagonal da diagonal da Hessiana. O AdaHessian estende isso usando os elementos reais da diagonal da Hessiana via o estimador de Hutchinson.

Construa

Passo 1: Verificador de convexidade

Construa uma função que testa a convexidade empiricamente, amostrando pontos e verificando a definição.

import random
import math

def check_convexity(f, dim, bounds=(-5, 5), samples=1000):
    violations = 0
    for _ in range(samples):
        x = [random.uniform(*bounds) for _ in range(dim)]
        y = [random.uniform(*bounds) for _ in range(dim)]
        t = random.uniform(0, 1)
        mid = [t * xi + (1 - t) * yi for xi, yi in zip(x, y)]
        lhs = f(mid)
        rhs = t * f(x) + (1 - t) * f(y)
        if lhs > rhs + 1e-10:
            violations += 1
    return violations == 0, violations

Passo 2: Método de Newton para 2D

Implemente o método de Newton usando uma Hessiana explícita. Compare a velocidade de convergência com a descida do gradiente.

def newtons_method(f, grad_f, hessian_f, x0, steps=50, tol=1e-12):
    x = list(x0)
    history = [x[:]]
    for _ in range(steps):
        g = grad_f(x)
        H = hessian_f(x)
        det = H[0][0] * H[1][1] - H[0][1] * H[1][0]
        if abs(det) < 1e-15:
            break
        H_inv = [
            [H[1][1] / det, -H[0][1] / det],
            [-H[1][0] / det, H[0][0] / det],
        ]
        dx = [
            H_inv[0][0] * g[0] + H_inv[0][1] * g[1],
            H_inv[1][0] * g[0] + H_inv[1][1] * g[1],
        ]
        x = [x[0] - dx[0], x[1] - dx[1]]
        history.append(x[:])
        if sum(gi ** 2 for gi in g) < tol:
            break
    return history

Passo 3: Solver de multiplicadores de Lagrange

Resolva a otimização com restrições usando descida do gradiente sobre o Lagrangiano.

def lagrange_solve(f_grad, g_val, g_grad, x0, lr=0.01,
                   lr_lambda=0.01, steps=5000):
    x = list(x0)
    lam = 0.0
    history = []
    for _ in range(steps):
        fg = f_grad(x)
        gv = g_val(x)
        gg = g_grad(x)
        x = [
            xi - lr * (fgi + lam * ggi)
            for xi, fgi, ggi in zip(x, fg, gg)
        ]
        lam = lam + lr_lambda * gv
        history.append((x[:], lam, gv))
    return history

Passo 4: Comparar primeira ordem vs segunda ordem

Execute a descida do gradiente e o método de Newton na mesma função quadrática. Conte os passos até a convergência.

def quadratic(x):
    return 5 * x[0] ** 2 + x[1] ** 2

def quadratic_grad(x):
    return [10 * x[0], 2 * x[1]]

def quadratic_hessian(x):
    return [[10, 0], [0, 2]]

O método de Newton vai convergir em 1 passo (ele é exato para quadráticas). A descida do gradiente vai levar centenas de passos porque os autovalores da Hessiana diferem por um fator de 5, criando um vale alongado.

Use

A análise de convexidade se aplica diretamente ao escolher modelos e solvers de ML.

Para problemas convexos (regressão logística, SVMs, LASSO):

• Use solvers dedicados (liblinear, CVXPY, scipy.optimize.minimize com method='L-BFGS-B')
• Espere uma solução global única
• Métodos de segunda ordem são práticos e rápidos

Para problemas não convexos (redes neurais):

• Use métodos de primeira ordem (SGD, Adam)
• Aceite que a solução depende da inicialização e da aleatoriedade
• Use superparametrização, ruído e cronogramas de taxa de aprendizado como regularização implícita
• Não perca tempo procurando o mínimo global. Um bom mínimo local é suficiente.

from scipy.optimize import minimize

result = minimize(
    fun=lambda w: sum((y - X @ w) ** 2) + 0.1 * sum(w ** 2),
    x0=np.zeros(d),
    method='L-BFGS-B',
    jac=lambda w: -2 * X.T @ (y - X @ w) + 0.2 * w,
)

Para SVMs, a formulação dual permite usar o truque do kernel:

from sklearn.svm import SVC

svm = SVC(kernel='rbf', C=1.0)
svm.fit(X_train, y_train)
print(f"Support vectors: {svm.n_support_}")

Exercícios

1. Galeria de convexidade. Teste estas funções quanto à convexidade usando o verificador: f(x) = x^4, f(x) = sin(x), f(x,y) = x^2 + y^2, f(x,y) = x*y, f(x) = max(x, 0). Explique por que cada resultado faz sentido.

2. Corrida Newton vs descida do gradiente. Execute ambos os métodos em f(x,y) = 50*x^2 + y^2 a partir do ponto inicial (10, 10). Quantos passos cada um precisa para alcançar loss < 1e-10? O que acontece com a descida do gradiente quando o número de condição (razão entre o maior e o menor autovalor da Hessiana) aumenta?

3. Geometria dos multiplicadores de Lagrange. Minimize f(x,y) = (x-3)^2 + (y-3)^2 sujeito a x + 2y = 4. Verifique a solução checando que o gradiente de f é paralelo ao gradiente de g na solução.

4. Restrição de regularização. Implemente a otimização com restrição L1: minimize (x-3)^2 + (y-2)^2 sujeito a |x| + |y| <= 1. Mostre que a solução tem uma coordenada igual a zero (esparsidade vinda da restrição em losango).

5. Análise de autovalores da Hessiana. Compute a Hessiana da função de Rosenbrock em (1,1) e em (-1,1). Compute os autovalores em ambos os pontos. O que os autovalores dizem sobre a curvatura no mínimo versus longe dele?

Termos-Chave

Leitura Complementar

• Boyd & Vandenberghe: Convex Optimization - o livro-texto padrão, disponível gratuitamente online
• Bottou, Curtis, Nocedal: Optimization Methods for Large-Scale Machine Learning (2018) - faz a ponte entre a teoria de otimização convexa e a prática de deep learning
• Choromanska et al.: The Loss Surfaces of Multilayer Networks (2015) - por que as superfícies não convexas de redes neurais não são tão ruins quanto parecem
• Nocedal & Wright: Numerical Optimization - referência abrangente para o método de Newton, L-BFGS e otimização com restrições