Konvexitet och optimeringslandskap

En funktion är konvex om linjen mellan två punkter på grafen alltid ligger ovanför grafen — en skål. Konsekvensen är stark: varje lokalt minimum är globalt. Gradient descent hittar rätt oavsett var man börjar.

x², eˣ, |x| och −log x är konvexa. sin x, x³ och nästan alla neuronnät är det inte.

Konvexa problem i ML: linjär regression (MSE), logistisk regression, SVM, lasso/ridge. Därför är de så stabila — samma data ger samma lösning varje gång.

Neuronnät är djupt icke-konvexa. Landskapet har många minima, sadelpunkter och platåer. Två körningar med olika frön landar i olika lösningar — som ändå ofta presterar likvärdigt.

Definition: $f$ är konvex om för alla $x, y$ och $\lambda\in[0,1]$: $f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda) f(y)$

Test i en dimension: $f''(x) \ge 0$ överallt. I flera dimensioner: Hessianen $H$ är positivt semidefinit (alla egenvärden $\ge 0$).

Kritiska punkter ($\nabla f = 0$) klassificeras av Hessianens egenvärden:

• alla positiva → lokalt minimum
• alla negativa → lokalt maximum
• blandade tecken → sadelpunkt

Varför sadelpunkter är det verkliga problemet i djupinlärning: i $d$ dimensioner krävs att alla $d$ egenvärden har samma tecken för ett äkta minimum. Sannolikheten för det avtar snabbt med $d$ — så i miljondimensionella landskap är de allra flesta kritiska punkter sadelpunkter, inte lokala minima (Dauphin m.fl. 2014).

Gradienten är nästan noll nära en sadelpunkt, så träningen «fastnar» — men bara tillfälligt. Momentum och brus från stokastiska gradienter tar sig förbi. Det är en av anledningarna till att SGD med brus fungerar bättre än man skulle tro.

import numpy as np

# Sadelpunkt: f(x,y) = x² − y², kritisk punkt i origo
f = lambda x, y: x**2 - y**2
H = np.array([[2.0, 0.0], [0.0, -2.0]])
print(np.linalg.eigvalsh(H))       # [-2.  2.]  ← blandade tecken = sadelpunkt

# Gradient descent från en punkt nära sadeln
x, y, eta = 0.001, 0.001, 0.1
for i in range(60):
    x -= eta * 2 * x               # dras mot 0
    y -= eta * (-2 * y)            # stöts bort från 0
print(round(x, 6), round(y, 3))    # 1e-06  0.115  ← kryper långsamt ur sadeln

Nära origo är gradienten liten åt båda håll, och det tar många steg innan y-riktningen tar fart. Det ser ut som att träningen står still — men den gör det inte.