Konvexe Optimierung und Regularisierung: Gradientenabstieg, Schrittweite, Ridge und Lasso

Konvexität: warum ein Gradient von null genügt

Eine konvexe Funktion ist eine Schüssel mit einem einzigen Boden, also ist der Punkt, an dem die Steigung verschwindet, der beste Punkt überhaupt.

Eine konvexe Funktion (convex function) ist eine Funktion, bei der die Strecke zwischen zwei beliebigen Punkten ihres Graphen nie unter den Graphen fällt. Die kleinsten Quadrate und der logistische Log-Loss sind konvex; die Verlustfunktion eines neuronalen Netzes ist es nicht und kann einen Abstieg in einer lokalen Mulde festhalten. Alles in dieser Sitzung setzt den konvexen Fall voraus.

Zieht man $f(x)$ ab, teilt durch $t > 0$ und lässt $t$ gegen null gehen, wird aus der Sehnenungleichung die Tangentenungleichung. Die Kurve liegt über jeder ihrer Tangenten. Das ist die Form, die den ganzen Vormittag über verwendet wird.

Ist der Gradient in $x^\star$ gleich null, verschwindet der lineare Term, und $f(y) \ge f(x^\star)$ gilt für jedes $y$. Ein stationärer Punkt einer konvexen Funktion ist daher ein globales Minimum. Deshalb genügten die Normalgleichungen der vorigen Sitzung. Die Hesse-Matrix der kleinsten Quadrate ist $2X^{\T}X$, und $v^{\T}X^{\T}Xv = \lVert Xv \rVert^2 \ge 0$, also ist die lineare Regression konvex.

Das durchgehende Beispiel des Foliensatzes ist die Schüssel $f(w) = (w - 3)^2 + 1$. Ihre Steigung $2(w - 3)$ ist links von 3 negativ, bei 3 null und rechts davon positiv, und die Höhe ist genau dort am kleinsten, wo die Steigung verschwindet. Zwei Konstanten beschreiben dann die Form jeder Schüssel: $L$, die größte Krümmung, und $\mu$, die kleinste. Bei einer quadratischen Funktion sind das die extremen Eigenwerte der Hesse-Matrix, und ihr Verhältnis $\kappa = L/\mu$ ist die Konditionszahl (condition number), die schon bei der SVD vorkam.

Zurück zum Inhalt.

Gradientenabstieg und die Schrittweite η

Die Steigung ertasten, einen Schritt bergab machen, wiederholen: Die einzige echte Entscheidung ist die Länge jedes Schritts, und ein zu langer Schritt macht alles schlimmer.

Der Gradient zeigt bergauf, also geht man in die Gegenrichtung. Die Cauchy-Schwarz-Ungleichung zeigt, dass unter allen Richtungen gleicher Länge $-\nabla f$ die Funktion $f$ in erster Ordnung am schnellsten verringert. Das ist der Gradientenabstieg (gradient descent), und die Schrittlänge ist die Lernrate (learning rate) $\eta$.

Übersteigt die Krümmung nie $L$, bleibt die Funktion unter einer Parabel der Krümmung $L$ (das Abstiegslemma, im Foliensatz ohne Beweis verwendet). Setzt man den Schritt dort ein, ergibt sich eine garantierte Abnahme, solange $\eta < 2/L$ gilt.

Bei einer quadratischen Funktion ist das Bild exakt. In der Eigenbasis der Hesse-Matrix wird jede Koordinate des Abstands zum Minimum bei jedem Schritt mit $1 - \eta\lambda_i$ multipliziert. Jeder Faktor muss betragsmäßig kleiner als 1 sein, und der größte Eigenwert liefert die strengste Bedingung: $\eta < 2/L$. Die Schrittweite $\eta = 1/L$ beseitigt die steilste Richtung in einem einzigen Zug.

Gleiche Schüssel, gleicher Start, vier Schrittweiten (hier 1/L = 0,5 und 2/L = 1)

1. η = 0,25. Faktor 0,5: Die Iterierten 1,5; 2,25; 2,625 nähern sich der 3 von einer Seite.
2. η = 0,5. Faktor 0: Der erste Schritt landet auf 3 und bleibt dort.
3. η = 0,75. Faktor −0,5: 4,5; 2,25; 3,375. Der Abstieg schießt über das Ziel hinaus und kehrt zurück, konvergiert aber noch.
4. η = 1,2. Faktor −1,4, jenseits von 2/L: 7,2; −2,88; 11,23. Jeder Schritt springt weiter weg. Das ist der Trainingslauf, dessen Verlust zu NaN wird.

Zurück zum Inhalt.

Warum die Konditionszahl das Tempo bestimmt

In einem langen, schmalen Tal muss der Schritt für die steile Flanke klein sein, also geht es entlang des flachen Talbodens nur langsam voran; das Umskalieren der Variablen rundet das Tal ab.

Mit $\eta = 1/L$ ist die steile Richtung sofort erledigt, und die flache Richtung gibt das Tempo vor: Ihr Faktor ist $1 - \mu/L = 1 - 1/\kappa$. Den Abstand durch zehn zu teilen, kostet daher etwa $2.3\,\kappa$ Iterationen.

Der Foliensatz prüft das an kleinsten Quadraten mit vier Beobachtungen und zwei korrelierten Spalten. Die Hesse-Matrix des mittleren Verlusts hat die Eigenwerte 1 und 4, also $L = 4$, $\kappa = 4$ und $\eta = 0.25$. Ab der zweiten Iteration ist jeder Abstand zur Lösung genau das 0,75-Fache des vorigen, und $\ln 10 / (-\ln 0.75) \approx 8$ Iterationen teilen ihn durch zehn.

Das hat praktische Folgen. Eine Spalte in Euro neben einer Spalte in Jahren macht $\kappa$ riesig: Für die Kreditausfalldaten des Kurses gibt der Foliensatz eine Konditionszahl von etwa $4 \cdot 10^{12}$ für die Rohspalten der logistischen Hesse-Matrix an, gegenüber etwa 300 nach Zentrieren und Skalieren, berechnet auf dem Trainingsdatensatz mit 18.000 Zeilen. Die Standardisierung ist die billigste Beschleunigung, die es gibt. Mittelwert und Standardabweichung werden dabei nur auf dem Trainingsdatensatz berechnet, sonst fließen Validierungs- und Testdaten in das Modell ein.

Zurück zum Inhalt.

Stochastischer Gradient, Momentum und Adam

Nur die Steigung einiger zufällig gewählter Beobachtungen statt aller zu verwenden, macht jeden Schritt weit billiger, um den Preis von etwas Rauschen.

Der Verlust ist ein Mittelwert aus $n$ Einzelverlusten, also ist sein Gradient der Mittelwert aus $n$ Einzelgradienten. Der stochastische Gradientenabstieg (stochastic gradient descent, SGD) verwendet nur einen davon, zufällig gezogen: Im Mittel ist das die richtige Richtung, und ein Schritt kostet $n$-mal weniger. Ein Mini-Batch aus $B$ Beobachtungen hält die Schätzung erwartungstreu und teilt ihre Varianz durch $B$.

Mit fester Schrittweite verschwindet das Rauschen nie, und die Iterierten kreisen immer weiter um das Minimum. Robbins und Monro (1951) gaben die Bedingungen für eine abnehmende Schrittweite an: $\sum \eta_k = \infty$, damit der Weg überallhin führen kann, und $\sum \eta_k^2 < \infty$, damit das Rauschen abklingt. Im Beispiel des Foliensatzes mit zwei Variablen unterscheiden sich die vier Einzelgradienten im Ursprung, ihr Mittelwert ist aber der volle Gradient $(-3.5, -4.5)$, mit einer Streuung $\sigma^2 = 10$.

Zwei Verfeinerungen schließen die erste Hälfte ab. Momentum (Polyak, 1964) akkumuliert vergangene Gradienten: In der steilen Richtung wechseln sie das Vorzeichen und heben sich auf, entlang des Talbodens addieren sie sich. Adam (Kingma und Ba, 2015) fügt eine Schrittweite pro Koordinate hinzu, skaliert mit einem gleitenden Mittel der quadrierten Gradienten, was wie eine automatische Standardisierung wirkt. Es ist der Standard für neuronale Netze, bietet im konvexen Fall aber keine Konvergenzgarantie; für eine logistische Regression genügen einfacher Gradientenabstieg oder L-BFGS.

Zurück zum Inhalt.

Ridge-Regression: Schrumpfung, Richtung für Richtung

Ridge belegt große Koeffizienten mit Kosten, was sie in Richtung null zieht und die Richtungen zähmt, die die Daten kaum festlegen.

Nahezu kollineare Spalten machen $X^{\T}X$ fast singulär, und die Kleinste-Quadrate-Koeffizienten werden riesig, mit instabilen Vorzeichen. Ridge (Hoerl und Kennard, 1970, auch als Tikhonov-Regularisierung bekannt) addiert $\lambda \lVert \beta \rVert^2$ zum Kriterium. Der Gradient bleibt linear, also ist die Lösung durch die Normalgleichungen mit $\lambda$ auf der Diagonale gegeben, invertierbar für jedes $\lambda > 0$. Der Achsenabschnitt wird nicht bestraft: Man zentriert zuerst $y$ und die Spalten.

Auf einem Spielzeugdatensatz mit vier Zeilen und zwei orthogonalen Spalten aus $\pm 1$ gilt $X^{\T}X = 4I$ und $X^{\T}y = (9.6, 4.8)$. Die kleinsten Quadrate ergeben $(2.4, 1.2)$, und Ridge teilt durch $4 + \lambda$ statt durch 4, sodass beide Koeffizienten mit $4/(4 + \lambda)$ multipliziert werden, also mit 0,8 bei $\lambda = 1$, mit 0,5 bei $\lambda = 4$ und mit 0,1 bei $\lambda = 36$. Das ist Schrumpfung (shrinkage): Die Koeffizienten werden kleiner, erreichen null aber nie.

Die SVD $X = UDV^{\T}$ zeigt den genauen Mechanismus. Die kleinsten Quadrate teilen jede Projektion $u_j^{\T}y$ durch den Singulärwert $d_j$, und bei einem winzigen $d_j$ explodiert die Varianz. Ridge multipliziert jede Richtung mit einem Faktor zwischen 0 und 1.

In die ursprüngliche Basis zurückgerechnet ergibt das $\hat\beta = (0.55, 1.05)$ gegenüber $(0.5, 1.5)$ bei den kleinsten Quadraten, dasselbe wie mit der direkten Formel. Die Summe der Faktoren, hier 1,3 statt 2, ist die effektive Zahl der Parameter, die das Modell tatsächlich nutzt.

Zurück zum Inhalt.

Lasso: weiche Schwellenwertbildung, Ecken und A-priori-Verteilungen

Das Lasso zieht von jedem Koeffizienten einen festen Betrag ab, setzt diejenigen exakt auf null, die dabei die Null überqueren würden, und wählt so Variablen aus.

Das Lasso (Tibshirani, 1996) ersetzt die quadrierte Norm durch die Summe der Beträge. Bei orthonormalen Spalten ($X^{\T}X/n = I$, die Konvention von scikit-learn mit $1/2n$ vor dem quadratischen Fehler) zerfällt das Kriterium in ein Problem pro Koordinate. Jedes hat bei null eine Ecke, die mit dem Subgradienten $[-1, 1]$ von $|b|$ behandelt wird, und die Lösung ist die weiche Schwellenwertbildung (soft thresholding) des Kleinste-Quadrate-Koeffizienten $z_j$.

Eine Probe aus dem Foliensatz: Bei $\lambda = 1$ beträgt das Kriterium 2,605 im Punkt $(1.4, 0.2)$ nach der Schwellenwertbildung, 2,625, wenn der zweite Koeffizient zu früh auf null gezwungen wird, und 3,605 im Kleinste-Quadrate-Punkt. Ohne orthonormale Spalten gibt es keine geschlossene Form, und Löser wechseln einen Gradientenschritt mit einer Schwellenwertbildung ab (ISTA) oder führen einen Koordinatenabstieg aus, wie es scikit-learn tut.

Geometrie. Bestrafen ist gleichbedeutend damit, den Verlust innerhalb eines Budgets $\lVert\beta\rVert \le t$ zu minimieren. Das L2-Budget ist eine Kreisscheibe, das L1-Budget eine Raute mit Ecken auf den Achsen; die elliptischen Höhenlinien des Verlusts berühren die Raute meist zuerst an einer Ecke, wo einige Koordinaten exakt null sind.

Bayessche Lesart. Eine A-priori-Verteilung (prior) auf $\beta$ verwandelt das Maximum a posteriori in Verlust plus Strafe. Eine Gauß-Verteilung $\mathcal{N}(0, \tau^2)$ als Prior ergibt Ridge mit $\lambda = \sigma^2/\tau^2$, eine Laplace-Verteilung das Lasso. Ein großes $\lambda$ zu wählen heißt zu erklären, dass man im Vergleich zum Rauschen kleine Koeffizienten erwartet, und beim Lasso, dass viele davon null sind.

Zurück zum Inhalt.

λ per Kreuzvalidierung wählen, nie auf dem Testdatensatz

Die Stärke der Strafe ist eine Einstellung, die auf zurückgehaltenen Folds der Trainingsdaten gewählt wird; der Testdatensatz wird ein einziges Mal geöffnet, ganz am Ende.

$\lambda$ ist ein Hyperparameter. Auf den Trainingsdaten angepasst, würde er immer auf null fallen, und auf dem Testdatensatz abgestimmt, bliebe nichts Ehrliches mehr zu berichten. Die Antwort ist die Kreuzvalidierung (cross-validation) der vorigen Sitzung: ein Gitter von $\lambda$-Werten auf logarithmischer Skala, beginnend bei $\lambda_{\max}$, wo alle Lasso-Koeffizienten null sind, fünf Folds des Trainingsdatensatzes und der mittlere Validierungsfehler pro Wert mit seinem Standardfehler. Die Standardisierung wird innerhalb jedes Folds neu angepasst.

Zwei Entscheidungen sind vertretbar: $\lambda_{\min}$, das Minimum der Kurve, oder die Ein-Standardfehler-Regel (Breiman und Koautoren, 1984), also das größte $\lambda$, dessen Fehler innerhalb eines Standardfehlers vom Minimum bleibt. Die zweite liefert ein einfacheres Modell, das die Daten nicht vom besten unterscheiden können, und meist ist sie es, die in Produktion geht. In scikit-learn wird die logistische Regression über $C$ parametrisiert, den Kehrwert der Strafstärke.

Der Regularisierungspfad (regularisation path) trägt jeden Koeffizienten gegen $\lambda$ auf. Beim Lasso ist er stückweise linear: Alle Koeffizienten beginnen bei null, und die Variablen kommen nacheinander hinzu, während die Strafe nachlässt, die informativsten zuerst. Der Foliensatz ergänzt einen Test für den produktiven Einsatz: das Lasso auf vielen Neustichproben des Trainingsdatensatzes neu schätzen und zählen, wie oft jede Variable behalten wird (Stabilitätsselektion, Meinshausen und Bühlmann, 2010). Eine kurze, stabile Liste von Variablen ist das, was ein Kreditausschuss lesen, erklären und pflegen kann, und genau darum geht es in der nächsten Sitzung über Schwellenwerte und reproduzierbare Auslieferung.

Zurück zum Inhalt.

Das Wichtigste in Kürze

1. Bei einer konvexen Funktion ist ein Punkt, an dem der Gradient verschwindet, ein globales Minimum: Sehne über der Kurve, Kurve über ihren Tangenten.
2. Der Gradientenabstieg konvergiert für eine Schrittweite η < 2/L, wobei L die größte Krümmung ist; darüber steigt der Verlust bei jedem Schritt.
3. Die Zahl der Iterationen wächst mit der Konditionszahl κ = L/μ, deshalb werden die Spalten standardisiert, mit Statistiken, die nur auf dem Trainingsdatensatz berechnet werden.
4. SGD und Mini-Batches nehmen einen erwartungstreuen, aber verrauschten Gradienten in Kauf und erhalten dafür einen weit billigeren Schritt; das Rauschen fällt wie 1/B, und die Schrittweite muss abnehmen, damit sich das Verfahren einpendelt.
5. Ridge schrumpft jede singuläre Richtung um den Faktor d²/(d² + λ) und setzt nie einen Koeffizienten auf null; das Lasso zieht λ per weicher Schwellenwertbildung ab und erzeugt exakte Nullen.
6. Ridge entspricht einer gaußschen A-priori-Verteilung, das Lasso einer Laplace-Verteilung: λ vergleicht das erwartete Rauschen mit der erwarteten Größe der Koeffizienten.
7. λ wird per Kreuzvalidierung auf den Trainings-Folds gewählt, oft mit der Ein-Standardfehler-Regel; der Testdatensatz bleibt bis zum Abschlussbericht verschlossen.

Glossar

konvexe Funktion (convex function)

Eine Funktion, deren Sehnen über ihrem Graphen liegen; jeder Punkt mit Gradient null ist ein globales Minimum.

Gradientenabstieg (gradient descent)

Iteratives Verfahren, das sich gegen den Gradienten bewegt, mit einem Schritt proportional zur Lernrate.

Lernrate (learning rate)

Mit η bezeichnet: die Länge eines Gradientenschritts pro Einheit Steigung; sie muss unter 2/L bleiben, damit der Abstieg konvergiert.

Konditionszahl (condition number)

Mit κ bezeichnet: das Verhältnis L/μ von größter zu kleinster Krümmung; es bestimmt, wie viele Iterationen der Gradientenabstieg braucht.

stochastischer Gradientenabstieg (stochastic gradient descent, SGD)

Gradientenabstieg, der pro Schritt eine Beobachtung oder einen Mini-Batch verwendet, erwartungstreu, aber verrauscht.

Momentum

Akkumulation vergangener Gradienten in einer Geschwindigkeit, die Schwingungen dämpft und flache Richtungen beschleunigt.

Ridge

Kleinste Quadrate mit einer L2-Strafe λ‖β‖²; schrumpft die Koeffizienten, ohne sie auf null zu setzen.

Schrumpfung (shrinkage)

Geschätzte Koeffizienten in Richtung null ziehen, um ihre Varianz zu verringern, auf Kosten von etwas Bias.

Lasso

Kleinste Quadrate mit einer L1-Strafe λ‖β‖₁; erzeugt exakte Nullen und wählt so Variablen aus.

weiche Schwellenwertbildung (soft thresholding)

Die Abbildung z ↦ sign(z)(|z| − λ)₊, die Lasso-Lösung Koordinate für Koordinate bei orthonormalen Spalten.

Regularisierungspfad (regularisation path)

Die angepassten Koeffizienten als Funktion von λ, von lauter Nullen bis zur unbestraften Anpassung.

A-priori-Verteilung (prior)

Verteilung der Parameter, bevor man die Daten sieht; ein gaußscher Prior ergibt Ridge, ein Laplace-Prior das Lasso.

Kreuzvalidierung (cross-validation)

Rotierende Aufteilung des Trainingsdatensatzes in Folds, um Hyperparameter wie λ ohne den Testdatensatz zu wählen.

Die anderen Notizen des Kurses

Eine öffentliche Zusammenfassung pro Foliensatz, in der Reihenfolge des Kurses.

Zurück: Maximum Likelihood und logistische RegressionWeiter: Entscheidungsschwelle und reproduzierbares ML

1. EinführungKI-Winter, Arbeitsmarkt und Methode
2. WerkzeugeKaggle, GitHub, Python: die Werkzeuge
3. Sitzung 1Projektrahmen und kleinste Quadrate
4. Sitzung 2Maximum Likelihood und logistische Regression
5. Sitzung 3Gradientenabstieg, Ridge und Lasso
6. Sitzung 4Entscheidungsschwelle und reproduzierbares ML
7. HausaufgabeML-Projekt abstecken: der Projektsteckbrief
8. Sitzung 5Kernel, SVM und Entscheidungsbäume
9. Sitzung 6Random Forests, Boosting, ehrlicher Vergleich
10. Sitzung 7SHAP, Fairness, PCA und Clustering
11. HausaufgabeEin einfaches Modell mit vollständiger Methode
12. Sitzung 8Neuronale Netze, Drift, konforme Vorhersage
13. HausaufgabeEin ausgeliefertes Machine-Learning-Projekt
14. Sitzung 9Ein Machine-Learning-Projekt verteidigen
15. ReferenzProjekt zum Kreditausfallscore
16. ReferenzAktienrenditen: XGBoost und Sentiment
17. ReferenzPython-Code für jedes ML-Modell
18. ReferenzDeep Learning, das Wesentliche
19. ReferenzML-Projekte mit offenen Daten nach Branche
20. ReferenzHandbuch für Daten- und KI-Fachleute
21. ReferenzData Engineering, SRE und Cloud
22. ReferenzPanorama der Machine-Learning-Modelle

Alle Notizen als Leseliste

Aufmerksamkeit und Transformer, Schritt für Schritt

Über diese Notizen

Vom Dozenten auf Grundlage der Folien verfasst, als öffentliche Zusammenfassung: die Kernideen, die Formeln und ein durchgerechnetes Beispiel. Die Übungen, ihre Lösungen, die Tests und die Bewertung bleiben im Foliensatz, für die Studierenden des Kurses.

Stand: 16. Oktober 2026.