Subdifferential konvexer Funktionen: Theorie und Praxis für ECE490

Einführung: Warum Subdifferentiale in der modernen Optimierung wichtig sind

In der konvexen Optimierung, einem Kernbereich des maschinellen Lernens und der KI-gestützten Finanzmodellierung, stoßen wir oft auf Funktionen, die nicht überall differenzierbar sind. Denk an die L1-Norm, die in der sparse Coding-Methode verwendet wird – sie hat an der Nullstelle einen Knick. Hier kommt das Subdifferential ins Spiel: Es verallgemeinert den Gradienten auf nicht-glatte Funktionen. In diesem Tutorial lernst du, wie man das Subdifferential einer konvexen Funktion definiert, seine Eigenschaften (Abgeschlossenheit, Konvexität) beweist und es für wichtige Normen sowie stückweise lineare Funktionen berechnet. Diese Konzepte sind essenziell für Hausaufgabe 5 in ECE490 und werden auch in aktuellen KI-Trends wie Large Language Models (z.B. bei der Optimierung von Transformern) angewendet.

1. Definition und grundlegende Eigenschaften des Subdifferentials

Sei f: R^n → R eine konvexe Funktion. Ein Vektor g ∈ R^n heißt Subgradient von f an der Stelle x, falls für alle y ∈ R^n gilt:

f(y) ≥ f(x) + g^T (y - x)

Die Menge aller Subgradienten an x heißt Subdifferential ∂f(x). Anschaulich ist ∂f(x) die Menge aller Steigungen von affinen Unterfunktionen, die f in x berühren.

Beispiel aus der Praxis: Optimierung eines KI-Modells

Stell dir vor, du trainierst ein neuronales Netz mit einer L1-Regularisierung (wie bei Lasso), um die Anzahl der Features zu reduzieren. Der Verlustterm ist glatt, aber der Regularisierungsterm ist nicht differenzierbar. Der subgradient descent (eine Verallgemeinerung des Gradientenabstiegs) verwendet Subgradienten, um das Minimum zu finden. Dieses Verfahren wird z.B. in TensorFlow oder PyTorch implementiert, um Modelle mit Millionen von Parametern zu trainieren.

2. Beweis: Das Subdifferential ist abgeschlossen und konvex

Diese Aufgabe (Wright & Recht, Kap. 8, Übung 1) verlangt, dass du zeigst, dass ∂f(x) für eine konvexe Funktion f sowohl abgeschlossen als auch konvex ist. Hier der Beweis:

Konvexität

Seien g1, g2 ∈ ∂f(x) und λ ∈ [0,1]. Für jedes y gilt:

f(y) ≥ f(x) + g1^T (y-x) und f(y) ≥ f(x) + g2^T (y-x)

Multipliziere die erste Ungleichung mit λ, die zweite mit (1-λ) und addiere sie:

f(y) ≥ f(x) + (λ g1 + (1-λ) g2)^T (y-x)

Also ist λ g1 + (1-λ) g2 ∈ ∂f(x), womit die Konvexität gezeigt ist.

Abgeschlossenheit

Sei (g_n) eine Folge in ∂f(x) mit g_n → g. Für jedes n und alle y gilt:

f(y) ≥ f(x) + g_n^T (y-x)

Grenzübergang n→∞ liefert (da g_n^T(y-x) → g^T(y-x)):

f(y) ≥ f(x) + g^T (y-x)

Also g ∈ ∂f(x). Somit ist ∂f(x) abgeschlossen.

Merke: Die Abgeschlossenheit ist wichtig für Existenzbeweise in der Optimierung, z.B. beim subgradient descent mit variablen Schrittweiten.

3. Subdifferential der gängigen Normen

In Übung 5 (Wright & Recht, Kap. 8) sollst du das Subdifferential der L1-, L∞- und L2-Norm bestimmen. Hier die Lösungen:

3.1 L1-Norm: f(x) = ||x||_1 = Σ |x_i|

Das Subdifferential ist das kartesische Produkt der Vorzeichenfunktionen:

∂||x||_1 = { g ∈ R^n : g_i = sign(x_i) falls x_i ≠ 0, g_i ∈ [-1,1] falls x_i = 0 }

Dies wird z.B. in der Compressed Sensing-Theorie verwendet, um Signale aus wenigen Messungen zu rekonstruieren – ein heißes Thema in der Medizintechnik (z.B. MRT-Beschleunigung).

3.2 L∞-Norm: f(x) = ||x||_∞ = max_i |x_i|

Sei I_max = { i : |x_i| = ||x||_∞ }. Dann gilt:

∂||x||_∞ = { g ∈ R^n : Σ_{i∈I_max} g_i sign(x_i) = 1, g_i = 0 für i∉I_max, |g_i| ≤ 1, und g_i sign(x_i) ≥ 0 }

Anschaulich: Die Subgradienten sind Wahrscheinlichkeitsvektoren auf der Menge der maximalen Komponenten, gewichtet mit dem Vorzeichen. Diese Norm wird in der Robustheit von KI-Modellen verwendet, z.B. bei adversarial attacks.

3.3 L2-Norm (Euklidische Norm): f(x) = ||x||_2

Für x ≠ 0 ist ∂||x||_2 = { x/||x||_2 } (eindeutig). Für x = 0 gilt:

∂||0||_2 = { g ∈ R^n : ||g||_2 ≤ 1 }

Das ist die Einheitskugel im Dualraum. Diese Norm ist fundamental für Gradientenabstiegsverfahren in der Deep Learning-Optimierung.

4. Subdifferential einer stückweise linearen konvexen Funktion

Übung 7 behandelt die Funktion f(x) = max_{i=1,...,m} (a_i^T x + b_i). Das Subdifferential ist die konvexe Hülle der Gradienten der aktiven Funktionen:

∂f(x) = conv{ a_i : i ∈ I(x) }

wobei I(x) = { i : a_i^T x + b_i = f(x) } die Menge der Indizes der aktiven affinen Funktionen ist. Dieses Ergebnis ist zentral für die lineare Programmierung und Support Vector Machines (SVMs). Im Machine Learning wird die stückweise lineare Funktion oft als Verlustfunktion (z.B. Hinge Loss) verwendet.

5. Subdifferential einer Maximumsfunktion differenzierbarer Funktionen

Die letzte Aufgabe verlangt den Beweis, dass für f(x) = max_{i=1,...,m} f_i(x) mit konvexen, stetig differenzierbaren f_i gilt:

∂f(x) = { Σ_{i∈I(x)} λ_i ∇f_i(x) : λ_i ≥ 0, Σ_{i∈I(x)} λ_i = 1 }

Dies ist eine Verallgemeinerung des obigen Ergebnisses. Der Beweis nutzt die Tatsache, dass der Epigraph von f der Schnitt der Epigraphen der f_i ist. Diese Formel wird in der Mehrzieloptimierung und im Reinforcement Learning (z.B. bei Policy Gradient-Methoden) angewendet.

6. Anwendungsbeispiel: Subgradient Descent in der Praxis

Nehmen wir an, du möchtest eine L1-regulierte logistische Regression trainieren, um in einer Finanz-App Kreditausfälle vorherzusagen. Die Verlustfunktion ist:

J(w) = (1/N) Σ log(1+exp(-y_i w^T x_i)) + λ ||w||_1

Der erste Teil ist glatt, der zweite nicht. Der Subgradient an w ist:

g = (1/N) Σ (-y_i x_i) / (1+exp(y_i w^T x_i)) + λ * sign(w)

wobei sign(w) komponentenweise für w_j ≠ 0 und ein Wert in [-1,1] für w_j=0 ist. Mit subgradient descent (Schrittweite α_t = 1/√t) konvergiert der Algorithmus zum Optimum. Dieses Verfahren ist in scikit-learn implementiert.

7. Zusammenfassung und Ausblick

Du hast gelernt, dass das Subdifferential einer konvexen Funktion immer abgeschlossen und konvex ist. Für Normen wie L1, L∞ und L2 sowie für stückweise lineare Funktionen und Maximumsfunktionen kannst du es explizit angeben. Diese Konzepte sind nicht nur für deine ECE490-Hausaufgabe relevant, sondern auch für aktuelle Forschung in KI, Optimierung und Data Science. Wenn du dich für nicht-glatte Optimierung interessierst, sind proximal methods der nächste logische Schritt – sie werden in Generative Adversarial Networks (GANs) und Wasserstein-GANs eingesetzt.

Pro-Tipp: Übe die Berechnung von Subdifferentialen mit kleinen Beispielen (n=2) und zeichne sie dir auf. Das hilft, ein geometrisches Verständnis zu entwickeln.