Optimierung in Python: Praktische Übungen zu ERM, Projektion und Gradientenabstieg (Ece490 HW4 P0)

Einleitung: Optimierung in der Praxis – von Machine Learning bis zur App-Entwicklung

Optimierungsalgorithmen sind das Herz vieler moderner Technologien – von der KI-gestützten Bilderkennung in Apps wie Instagram bis zur Portfoliooptimierung in Finanz-Apps. In diesem Tutorial vertiefen wir die Konzepte aus Wright und Recht, Kapitel 6 und 7, und zeigen, wie du sie in Python umsetzt. Wir betrachten den Empirical Risk Minimization (ERM)-Rahmen, die euklidische Projektion auf die Einheitskugel, die Minimierung linearer Funktionen über konvexe Mengen und den projizierten Gradientenabstieg. Diese Methoden sind essenziell für Hausaufgaben wie die Ece490 Aufgabe 4 und für reale Anwendungen.

1. ERM und die Kosten der Funktionsauswertung (Aufgabe 1)

In Abschnitt 6.1 von Wright und Recht wird gezeigt, dass die Berechnung von f(x + γ ei) die gleiche Komplexität hat wie die Aktualisierung des Gradienten ∇f, nämlich O(|A·i|). Dies ist besonders relevant, wenn A eine dünnbesetzte Matrix ist – zum Beispiel in Empfehlungssystemen wie bei Netflix oder Spotify, wo Millionen von Benutzern und Artikeln interagieren.

Python-Code: Kostenberechnung für ERM

import numpy as np

def compute_f(x, A, b, i, gamma):
    # f(x) = 0.5 * ||Ax - b||^2
    # Berechne f(x + gamma * e_i)
    x_pert = x.copy()
    x_pert[i] += gamma
    return 0.5 * np.linalg.norm(A @ x_pert - b)**2

def cost_of_update(A, i):
    # Anzahl der Nicht-Null-Elemente in Spalte i
    return np.count_nonzero(A[:, i])

# Beispiel: dünnbesetzte Matrix (zufällig)
n, m = 1000, 100
A = np.random.randn(n, m)
A[np.random.rand(*A.shape) > 0.1] = 0  # 90% sparse
x = np.random.randn(m)
b = np.random.randn(n)
i = 0
gamma = 0.01
print("Kosten (Anzahl Nicht-Null in Spalte i):", cost_of_update(A, i))
print("f(x + gamma e_i):", compute_f(x, A, b, i, gamma))

Dieser Code zeigt, dass die Kosten linear mit der Anzahl der Nicht-Null-Einträge in der Spalte i skalieren – genau wie die Gradientenaktualisierung.

2. Euklidische Projektion auf die Einheitskugel (Aufgabe 2)

Die euklidische Projektion PΩ(x) auf die Einheitskugel Ω = {x ∈ ℝn : ‖x‖ ≤ 1} ist gegeben durch:

def project_ball(x):
    norm = np.linalg.norm(x)
    if norm <= 1:
        return x
    else:
        return x / norm

Diese Projektion wird häufig in Machine-Learning-Optimierern wie dem projizierten Gradientenabstieg verwendet, um sicherzustellen, dass die Parameter in einem beschränkten Bereich bleiben – ähnlich wie beim Training von neuronalen Netzen in TensorFlow oder PyTorch, wo Gewichtsbeschränkungen die Stabilität verbessern.

3. Minimierung linearer Funktionen über konvexe Mengen (Aufgabe 3)

Gegeben f(x) = cTx, suchen wir den Minimierer über drei konvexe Mengen:

(a) Einheitskugel {x : ‖x‖ ≤ 1}

Der Minimierer ist x* = -c / ‖c‖ (entgegengesetzte Richtung von c).

(b) Einheitssimplex {x : xi ≥ 0, Σ xi = 1}

Der Minimierer ist der Einheitsvektor ej, wobei j = argmin ci (die kleinste Komponente von c).

(c) Hyperwürfel [0,1]n

Der Minimierer ist xi = 1, wenn ci < 0, sonst xi = 0.

Diese einfachen Ergebnisse sind fundamental für die lineare Programmierung und werden in der Ressourcenallokation verwendet, z. B. bei der Budgetplanung in Finanz-Apps oder der Aufgabenverteilung in Cloud-Computing.

4. Projizierter Gradientenabstieg (Aufgabe 4)

Der projizierte Gradientenabstieg (PGD) ist ein mächtiges Werkzeug für Optimierung über konvexe Mengen. Ein Schritt lautet:

def projected_gradient_step(x, grad, alpha, project):
    # x in Omega, grad = gradient of f at x
    # alpha > 0 Schrittweite
    x_new = project(x - alpha * grad)
    return x_new

Die Aufgabe verlangt den Beweis, dass ‖xk+1 - xk‖² ≤ αk ∇f(xk)T(xk - xk+1). Dies folgt aus der Projektionseigenschaft und der Konvexität von Ω. In der Praxis wird PGD für Lasso-Regression, Bildentrauschung und Robuste Optimierung eingesetzt – zum Beispiel in der App „Snapchat“, wo Filter auf Gesichtern optimiert werden müssen.

Zusammenfassung

Dieses Tutorial hat die Kernkonzepte aus Wright und Recht Kapitel 6 und 7 behandelt: ERM-Komplexität, euklidische Projektion, Minimierung linearer Funktionen und projizierten Gradientenabstieg. Mit den bereitgestellten Python-Codes kannst du diese Methoden direkt anwenden und für deine Hausaufgabe (Ece490 HW4 P0) nutzen. Die Beispiele aus der Praxis – von Empfehlungssystemen über Cloud-Computing bis zu KI-Apps – zeigen die Relevanz dieser Optimierungsverfahren.