Phase 01 - Lesson 18

Optimización Convexa

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

Los problemas convexos tienen un solo valle. Las redes neuronales tienen millones. Conocer la diferencia importa.

Tipo: Construir Lenguaje: Python Requisitos previos: Fase 1, Lecciones 04 (Cálculo para ML), 08 (Optimización) Tiempo: ~90 minutos

Objetivos de Aprendizaje

• Probar si una función es convexa usando la definición, la segunda derivada y los criterios de la Hessiana
• Implementar el método de Newton y comparar su convergencia cuadrática con el descenso de gradiente
• Resolver problemas de optimización con restricciones usando multiplicadores de Lagrange e interpretar las condiciones KKT
• Explicar por qué las superficies de pérdida de las redes neuronales son no convexas y aun así el SGD encuentra buenas soluciones

El Problema

La Lección 08 te enseñó el descenso de gradiente, momentum y Adam. Esos optimizadores descienden por cualquier superficie. Pero no vienen con garantías. El descenso de gradiente sobre una superficie no convexa podría detenerse en un mínimo local malo, quedarse atascado en un punto de silla u oscilar para siempre. Lo usaste de todos modos porque las redes neuronales son no convexas y no hay alternativa.

Pero muchos problemas en machine learning son convexos. Regresión lineal, regresión logística, SVMs, LASSO, regresión ridge. Para estos existe algo más fuerte: optimización con garantías matemáticas. Un problema convexo tiene exactamente un valle. Cualquier algoritmo que descienda alcanzará el mínimo global. Sin necesidad de reinicios. Sin programaciones de tasa de aprendizaje. Sin rezar.

Entender la convexidad hace tres cosas. Primero, te indica cuándo tu problema es fácil (convexo) versus difícil (no convexo). Segundo, te da herramientas más rápidas como el método de Newton para problemas convexos. Tercero, explica conceptos que aparecen en todo el ML: la regularización como restricción, la dualidad en los SVMs y por qué el deep learning funciona a pesar de violar todas las buenas propiedades que ofrece la convexidad.

El Concepto

Conjuntos convexos

Un conjunto S es convexo si, para cualesquiera dos puntos en S, el segmento de recta entre ellos también queda completamente en S.

Prueba formal: para cualesquiera puntos x, y en S y cualquier t en [0, 1], el punto tx + (1-t)y también está en S.

Ejemplos de conjuntos convexos:

• Una recta, un plano, todo R^n
• Una bola (círculo, esfera, hiperesfera)
• Un semiespacio: {x : a^T x <= b}
• La intersección de cualquier número de conjuntos convexos

Ejemplos de conjuntos no convexos:

• Una dona (anillo)
• La unión de dos círculos disjuntos
• Cualquier conjunto con una "hendidura" o "agujero"

Funciones convexas

Una función f es convexa si su dominio es un conjunto convexo y, para cualesquiera dos puntos x, y en su dominio y cualquier t en [0, 1]:

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

Geométricamente: el segmento de recta entre cualesquiera dos puntos en la gráfica queda por encima o sobre la gráfica.

Funciones convexas comunes:

• f(x) = x^2 (parábola)
• f(x) = |x| (valor absoluto)
• f(x) = e^x (exponencial)
• f(x) = max(0, x) (ReLU, aunque lineal por tramos)
• f(x) = -log(x) para x > 0 (log negativo)
• Cualquier función lineal f(x) = a^T x + b (tanto convexa como cóncava)

Probando la convexidad

Tres pruebas prácticas, de la más fácil a la más rigurosa.

Prueba 1: Prueba de la segunda derivada (1D). Si f''(x) >= 0 para todo x, entonces f es convexa.

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

Prueba 2: Prueba de la Hessiana (multivariable). Si la matriz Hessiana H(x) es semidefinida positiva para todo x, entonces f es convexa. La Hessiana es la matriz de las segundas derivadas parciales.

Prueba 3: Prueba de la definición. Verifica la desigualdad f(tx + (1-t)y) <= t*f(x) + (1-t)*f(y) directamente. Útil para funciones donde las derivadas son difíciles de calcular.

Por qué importa la convexidad

El teorema central de la optimización convexa:

Para una función convexa, todo mínimo local es un mínimo global.

Esto significa que el descenso de gradiente no puede quedar atrapado. Cualquier camino descendente conduce a la misma respuesta. El algoritmo tiene garantía de converger a la solución óptima.

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

Consecuencias:

• Sin necesidad de reinicios aleatorios
• Sin necesidad de programaciones sofisticadas de tasa de aprendizaje
• Las pruebas de convergencia son posibles (la tasa depende de las propiedades de la función)
• La solución es única (salvo por regiones planas)

Convexo vs no convexo en ML

Los modelos lineales con pérdidas convexas son convexos. En el momento en que agregas capas ocultas con activaciones no lineales, la convexidad se rompe.

La matriz Hessiana

La Hessiana H de una función f: R^n -> R es la matriz n x n de las segundas derivadas parciales.

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 ]

La Hessiana informa sobre la curvatura:

• Valores propios todos positivos: la función se curva hacia arriba en todas las direcciones (convexa en ese punto)
• Valores propios todos negativos: se curva hacia abajo en todas las direcciones (cóncava, un máximo local)
• Signos mixtos: punto de silla (se curva hacia arriba en algunas direcciones, hacia abajo en otras)
• Valor propio cero: plano en esa dirección (degenerado)

Para la convexidad, la Hessiana debe ser semidefinida positiva (todos los valores propios >= 0) en todas partes, no solo en un punto.

Método de Newton

El descenso de gradiente usa información de primer orden (el gradiente). El método de Newton usa información de segundo orden (la Hessiana). Ajusta una aproximación cuadrática en el punto actual y salta directamente al mínimo de esa cuadrática.

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

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

El método de Newton reemplaza la tasa de aprendizaje escalar por la inversa de la Hessiana. Esto ajusta automáticamente el tamaño y la dirección del paso en función de la 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

Ventajas:

• Convergencia cuadrática cerca del mínimo (el error se eleva al cuadrado en cada paso)
• Sin tasa de aprendizaje que ajustar
• Invariante a la escala (funciona sin importar cómo parametrices el problema)

Desventajas:

• Calcular la Hessiana cuesta O(n^2) de memoria y O(n^3) para invertir
• Para una red neuronal con 1 millón de pesos, eso es 10^12 entradas y 10^18 operaciones
• No es práctico para deep learning

Optimización con restricciones

Optimización sin restricciones: minimizar f(x) sobre todos los x. Optimización con restricciones: minimizar f(x) sujeto a restricciones.

Los problemas reales tienen restricciones. Quieres minimizar el costo, pero tu presupuesto es limitado. Quieres minimizar el error, pero la complejidad de tu modelo está acotada.

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

El método de los multiplicadores de Lagrange convierte un problema con restricciones en uno sin restricciones.

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

Solución: introducir una nueva variable (el multiplicador de Lagrange lambda) y resolver el problema sin restricciones:

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

En la solución, el gradiente de L es cero:

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

Intuición geométrica: en el mínimo con restricciones, el gradiente de f debe ser paralelo al gradiente de la restricción g. Si no fueran paralelos, podrías moverte a lo largo de la superficie de restricción y reducir f aún más.

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"]

Ejemplo: minimizar f(x,y) = x^2 + y^2 sujeto 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

El punto más cercano al origen sobre la recta x + y = 1 es (0.5, 0.5).

Condiciones KKT

Las condiciones de Karush-Kuhn-Tucker extienden los multiplicadores de Lagrange a restricciones de desigualdad.

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

Las condiciones KKT (necesarias para la optimalidad):

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

La holgura complementaria es la idea clave: o la restricción está activa (g_i = 0, la solución está sobre la frontera) o el multiplicador es cero (la restricción no importa). Una restricción que no afecta la solución tiene lambda = 0.

Las condiciones KKT son centrales para los SVMs. Los vectores de soporte son los puntos de datos donde la restricción está activa (lambda > 0). Todos los demás puntos de datos tienen lambda = 0 y no afectan la frontera de decisión.

Regularización como optimización con restricciones

Las regularizaciones L1 y L2 no son trucos arbitrarios. Son problemas de optimización con restricciones disfrazados.

Regularización L2 (Ridge):

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

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

La restricción ||w||^2 <= t define una bola (círculo en 2D, esfera en 3D). La solución está donde las curvas de nivel de la pérdida tocan esa bola por primera vez.

Regularización L1 (LASSO):

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

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

La restricción ||w||_1 <= t define un rombo (cuadrado rotado en 2D).

Esto explica por qué la L1 produce modelos dispersos (selección de características) mientras que la L2 solo encoge los pesos. El rombo tiene vértices alineados con los ejes. Las curvas de nivel de la pérdida tienen mayor probabilidad de tocar un vértice, fijando uno o más pesos exactamente en cero.

Dualidad

Todo problema de optimización con restricciones (el primal) tiene un problema acompañante (el dual). Para problemas convexos, el primal y el dual tienen el mismo valor óptimo. Esto es la dualidad fuerte.

La función 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 qué importa la dualidad:

• El problema dual a veces es más fácil de resolver que el primal
• Los SVMs se resuelven en su forma dual, donde el problema depende de productos punto entre puntos de datos (habilitando el truco del kernel)
• El dual proporciona una cota inferior para el óptimo del primal, útil para verificar la calidad de la solución

Para los SVMs específicamente:

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 qué el deep learning funciona a pesar de la no convexidad

Las funciones de pérdida de las redes neuronales son extremadamente no convexas. Por toda medida clásica, optimizarlas debería fracasar. Aun así, el descenso de gradiente estocástico encuentra buenas soluciones de forma confiable. Varios factores explican esto.

La mayoría de los mínimos locales son lo suficientemente buenos. En espacios de alta dimensión, los puntos críticos aleatorios (donde el gradiente es cero) son abrumadoramente puntos de silla, no mínimos locales. Los pocos mínimos locales que existen tienden a tener valores de pérdida cercanos al mínimo global. Quedar atrapado en un mínimo local terrible es extremadamente improbable cuando el espacio de parámetros tiene millones de dimensiones.

Los puntos de silla, no los mínimos locales, son el verdadero obstáculo. En una función con n parámetros, un punto de silla tiene una mezcla de direcciones de curvatura positiva y negativa. Para un punto crítico aleatorio en alta dimensión, la probabilidad de que los n valores propios sean positivos (mínimo local) es de aproximadamente 2^(-n). Casi todos los puntos críticos son puntos de silla. El ruido del SGD ayuda a escapar de ellos.

La sobreparametrización suaviza la superficie. Las redes con más parámetros que ejemplos de entrenamiento tienen superficies de pérdida más suaves y más conectadas. Las redes más anchas tienen menos mínimos locales malos. Esto es contraintuitivo, pero empíricamente consistente.

Estructura de la superficie de pérdida:

El ruido estocástico actúa como regularización implícita. El SGD por mini-batch agrega ruido que impide asentarse en mínimos agudos. Los mínimos agudos sobreajustan; los mínimos planos generalizan. El ruido sesga la optimización hacia las regiones planas de la superficie de pérdida.

Métodos de segundo orden en la práctica

El método de Newton puro es impráctico para modelos grandes. Varias aproximaciones hacen utilizable la información de segundo orden.

L-BFGS (BFGS de memoria limitada): Aproxima la inversa de la Hessiana usando las últimas m diferencias de gradiente. Requiere O(mn) de memoria en lugar de O(n^2). Funciona bien para problemas con hasta ~10.000 parámetros. Usado en ML clásico (regresión logística, CRFs), pero no en deep learning.

Gradiente natural: Usa la matriz de información de Fisher (la Hessiana esperada de la log-verosimilitud) en lugar de la Hessiana estándar. Esto considera la geometría de las distribuciones de probabilidad. El K-FAC (Kronecker-Factored Approximate Curvature) aproxima la matriz de Fisher como un producto de Kronecker, haciéndola práctica para redes neuronales.

Optimización sin Hessiana (Hessian-free): Usa el gradiente conjugado para resolver Hx = g sin formar nunca H. Solo requiere productos Hessiana-vector, que pueden calcularse en tiempo O(n) vía diferenciación automática.

Aproximaciones diagonales: El segundo momento de Adam es una aproximación diagonal de la diagonal de la Hessiana. AdaHessian extiende esto usando los elementos reales de la diagonal de la Hessiana vía el estimador de Hutchinson.

Constrúyelo

Paso 1: Verificador de convexidad

Construye una función que pruebe la convexidad empíricamente, muestreando puntos y verificando la definición.

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

Paso 2: Método de Newton para 2D

Implementa el método de Newton usando una Hessiana explícita. Compara la velocidad de convergencia con el descenso de 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

Paso 3: Solucionador de multiplicadores de Lagrange

Resuelve la optimización con restricciones usando descenso de gradiente sobre el 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

Paso 4: Comparar primer orden vs segundo orden

Ejecuta el descenso de gradiente y el método de Newton sobre la misma función cuadrática. Cuenta los pasos hasta la convergencia.

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]]

El método de Newton convergerá en 1 paso (es exacto para cuadráticas). El descenso de gradiente tomará cientos de pasos porque los valores propios de la Hessiana difieren por un factor de 5, creando un valle alargado.

Úsalo

El análisis de convexidad se aplica directamente al elegir modelos y solucionadores de ML.

Para problemas convexos (regresión logística, SVMs, LASSO):

• Usa solucionadores dedicados (liblinear, CVXPY, scipy.optimize.minimize con method='L-BFGS-B')
• Espera una solución global única
• Los métodos de segundo orden son prácticos y rápidos

Para problemas no convexos (redes neuronales):

• Usa métodos de primer orden (SGD, Adam)
• Acepta que la solución depende de la inicialización y de la aleatoriedad
• Usa sobreparametrización, ruido y programaciones de tasa de aprendizaje como regularización implícita
• No pierdas tiempo buscando el mínimo global. Un buen mínimo local es 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 los SVMs, la formulación dual permite usar el truco del 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_}")

Ejercicios

1. Galería de convexidad. Prueba estas funciones para convexidad usando el 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). Explica por qué cada resultado tiene sentido.

2. Carrera Newton vs descenso de gradiente. Ejecuta ambos métodos sobre f(x,y) = 50*x^2 + y^2 desde el punto inicial (10, 10). ¿Cuántos pasos necesita cada uno para alcanzar pérdida < 1e-10? ¿Qué le ocurre al descenso de gradiente cuando el número de condición (razón entre el mayor y el menor valor propio de la Hessiana) aumenta?

3. Geometría de los multiplicadores de Lagrange. Minimiza f(x,y) = (x-3)^2 + (y-3)^2 sujeto a x + 2y = 4. Verifica la solución comprobando que el gradiente de f es paralelo al gradiente de g en la solución.

4. Restricción de regularización. Implementa la optimización con restricción L1: minimiza (x-3)^2 + (y-2)^2 sujeto a |x| + |y| <= 1. Muestra que la solución tiene una coordenada igual a cero (dispersión proveniente de la restricción en rombo).

5. Análisis de valores propios de la Hessiana. Calcula la Hessiana de la función de Rosenbrock en (1,1) y en (-1,1). Calcula los valores propios en ambos puntos. ¿Qué te dicen los valores propios sobre la curvatura en el mínimo versus lejos de él?

Términos Clave

Lecturas Adicionales

• Boyd & Vandenberghe: Convex Optimization - el libro de texto estándar, disponible gratuitamente en línea
• Bottou, Curtis, Nocedal: Optimization Methods for Large-Scale Machine Learning (2018) - tiende un puente entre la teoría de optimización convexa y la práctica del deep learning
• Choromanska et al.: The Loss Surfaces of Multilayer Networks (2015) - por qué las superficies no convexas de las redes neuronales no son tan malas como parecen
• Nocedal & Wright: Numerical Optimization - referencia completa para el método de Newton, L-BFGS y la optimización con restricciones