Calc-10 — Optimization: gradient descent, convexity, Lagrange

Why this matters for ML

Aquí se junta todo el cálculo en el algoritmo que entrena el machine learning: gradient descent. Entenderás por qué funciona (Taylor + gradient), cómo elegir el learning rate, qué es la convexity (y por qué unas losses son fáciles y otras no), sus variantes (momentum, SGD) y cómo optimizar con restricciones vía Lagrange multipliers (que también reaparecen al derivar SVMs y PCA).

Concepts covered

• Gradient descent: la regla y por qué baja
• Learning rate: efectos y trade-offs
• Variantes: SGD, mini-batch, momentum
• Convexity multivariable
• Optimización con restricciones: Lagrange multipliers
• Vistazo a las condiciones KKT

Intuition first

🎬 3Blue1Brown Neural Networks cap. 2 ("Gradient descent, how neural networks learn"). Para restricciones, Khan Academy "Lagrange multipliers".

Theory & key results

Gradient descent (GD): para minimizar $L(\boldsymbol\theta)$, itera $$\boldsymbol\theta_{t+1} = \boldsymbol\theta_t - \eta,\nabla L(\boldsymbol\theta_t).$$ Por qué baja: por Taylor de 1er orden (Calc-08), moverte en dirección $-\nabla L$ es la dirección de máximo descenso local; con $\eta$ pequeño, $L$ disminuye.

Learning rate $\eta$:

• Muy pequeño → converge lentísimo.
• Muy grande → oscila o diverge (se pasa del mínimo).
• Justo → baja rápido y estable. En la práctica se ajusta y a veces se programa (learning rate schedule).

Variantes (clave en deep learning):

• SGD (stochastic): usa el gradiente de un ejemplo (o mini-batch) en vez de todo el dataset → pasos ruidosos pero baratos y escalables. El ruido incluso ayuda a escapar de saddles.
• Mini-batch: el punto medio (lo estándar).
• Momentum: acumula una "velocidad" $v_{t+1}=\beta v_t + \nabla L$, $\theta\leftarrow\theta-\eta v_{t+1}$ → acelera en valles largos y amortigua oscilaciones. (Adam, RMSProp: refinamientos de esta idea.)

Convexity (multivariable): $L$ es convexa si su Hessian es positive semidefinite en todo el dominio (LA-08). Consecuencia enorme: todo mínimo local es global, así que GD encuentra la solución. Linear/logistic regression → convexas. Redes neuronales → no convexas (saddles y mínimos locales), por eso entrenar requiere trucos.

Optimización con restricciones — Lagrange multipliers: para minimizar $f(\mathbf{x})$ sujeto a $g(\mathbf{x})=0$, forma el Lagrangiano $$\mathcal{L}(\mathbf{x},\lambda) = f(\mathbf{x}) - \lambda,g(\mathbf{x)},$$ y resuelve $\nabla_{\mathbf{x}}\mathcal{L}=\mathbf{0}$, $;g(\mathbf{x})=0$. Intuición: en el óptimo, $\nabla f$ es paralelo a $\nabla g$ (no puedes mejorar $f$ sin violar la restricción). Aparece al derivar PCA (maximizar varianza con $|\mathbf{w}|=1$) y SVMs.

KKT (vistazo): generalización a restricciones de desigualdad ($g(\mathbf{x})\le0$). Las condiciones KKT (estacionariedad, factibilidad, complementary slackness) son la base teórica de SVMs y de la optimización convexa con restricciones. Solo necesitas saber que existen y qué generalizan por ahora.

Worked example

Minimizar $f(x,y)=x^2+y^2$ sujeto a $x+y=1$. Lagrangiano: $\mathcal{L}=x^2+y^2-\lambda(x+y-1)$. $\partial_x=2x-\lambda=0$, $\partial_y=2y-\lambda=0$ → $x=y$. Con $x+y=1$: $x=y=0.5$. Mínimo en $(0.5,0.5)$, valor $0.5$. (Geométricamente: el punto de la recta más cercano al origen.)

GD numérico: minimizando $f(x,y)=x^2+y^2$ desde $(3,3)$ con $\eta=0.1$ converge a $(0,0)$ en pocas iteraciones; con $\eta=1.1$ diverge. Pruébalo abajo.

Notebook exercises (by hand)

1. Escribe la actualización de GD para $L(w)=(w-5)^2$ y haz 3 iteraciones a mano con $\eta=0.1$, $w_0=0$.
2. ¿Para qué rango de $\eta$ converge GD en $L(w)=aw^2$? (Pista: analiza $w_{t+1}=(1-2a\eta)w_t$.)
3. Minimiza $f(x,y)=x^2+4y^2$ sujeto a $x+y=3$ con Lagrange.
4. Explica por qué momentum ayuda en un valle largo y estrecho.
5. Argumenta por qué SGD es preferible a GD "full-batch" en datasets enormes.
6. Da la intuición geométrica de "$\nabla f \parallel \nabla g$ en el óptimo con restricción".

Python lab

import numpy as np

def gradient_descent(grad, theta0, eta, steps):
    theta = np.array(theta0, float); traj = [theta.copy()]
    for _ in range(steps):
        theta = theta - eta*grad(theta); traj.append(theta.copy())
    return theta, np.array(traj)

grad = lambda t: 2*t                    # de f = ||t||^2
for eta in [0.1, 0.5, 1.1]:
    final, _ = gradient_descent(grad, [3., 3.], eta, 30)
    print(f"eta={eta}: theta_final={np.round(final,3)}  "
          f"{'diverge' if np.linalg.norm(final)>1e3 else 'converge'}")

# momentum
def gd_momentum(grad, theta0, eta, beta, steps):
    theta = np.array(theta0, float); v = np.zeros_like(theta)
    for _ in range(steps):
        v = beta*v + grad(theta); theta = theta - eta*v
    return theta
print("con momentum:", np.round(gd_momentum(grad,[3.,3.],0.1,0.9,30),3))

Examen final 📝

Intenta cada nivel antes de abrir las soluciones.

🟡 Medio

1. Escribe 3 iteraciones de GD para $L(w)=(w-3)^2$ desde $w_0=0$ con $\eta=0.25$.
2. Minimiza $f(x,y)=x^2+2y^2$ sujeto a $x+y=6$ con Lagrange multipliers.

🟠 Medio-difícil

3. Para $L(w)=aw^2$ ($a>0$), la iteración es $w_{t+1}=(1-2a\eta)w_t$. Halla el rango de $\eta$ para el que GD converge y el $\eta$ óptimo.
4. Demuestra que minimizar $f$ sujeto a $g(\mathbf x)=0$ exige $\nabla f=\lambda\nabla g$ en el óptimo, e interpreta geométricamente.

🔴 Difícil

5. Deriva el estimador de PCA/SVM-style: maximiza $\mathbf w^\top C\mathbf w$ sujeto a $|\mathbf w|^2=1$ con Lagrange y muestra que el óptimo es el eigenvector principal de $C$ con valor óptimo = eigenvalue máximo (une Calc-10 + LA-07).
6. Compara GD full-batch vs. SGD en términos de la varianza del estimador del gradiente (Prob-04/08): ¿por qué el gradiente de mini-batch es un estimador insesgado del gradiente verdadero, y cómo escala su varianza con el batch size $B$?