Benchmarking Stochastic Approximation Algorithms for Fairness-Constrained Training of Deep Neural Networks

1. Problemstellung

Das Paper adressiert die Herausforderung, Deep Neural Networks (DNNs) so zu trainieren, dass sie faire Vorhersagen treffen, indem sie diskriminierende Verzerrungen gegenüber geschützten Untergruppen (z. B. basierend auf Rasse oder Geschlecht) minimieren.

• Formulierung: Das Problem wird als eingeschränkte empirische Risikominimierung (Constrained Empirical Risk Minimization - ERM) formuliert:
  $$\min_{x \in \mathbb{R}^n} \mathbb{E}[f(x, \xi)] \quad \text{s.t.} \quad \mathbb{E}[c(x, \zeta)] \leq 0$$
  Dabei ist $f$ die Verlustfunktion (Ziel) und $c$ die Fairness-Nebenbedingung.
• Herausforderungen:
  • Nicht-Konvexität und Nicht-Glattheit: Durch die Verwendung von DNNs sind die Zielfunktionen und Nebenbedingungen oft nicht konvex und nicht glatt.
  • Stochastische Natur: Da die Erwartungswerte über große Datensätze berechnet werden, müssen Sampling-Verfahren (Mini-Batches) verwendet werden.
  • Ungleichheitsnebenbedingungen: Im Gegensatz zu vielen existierenden Algorithmen, die nur Gleichheitsnebenbedingungen behandeln, müssen hier Ungleichheitsnebenbedingungen (z. B. $|Loss_A - Loss_B| \leq \delta$) erfüllt werden.
  • Fehlende Standards: Es gibt derzeit keinen weit verbreiteten Standard oder Benchmark, um verschiedene Algorithmen für dieses spezifische Problem zu vergleichen.

2. Methodik und Ansatz

Die Autoren stellen einen umfassenden Benchmark vor, der auf dem US Census-Datensatz (Folktables) basiert, und implementieren sowie vergleichen drei neuartige, bisher nicht in diesem Kontext angewandte stochastische Approximationsalgorithmen.

A. Der Benchmark

• Daten: Nutzung des ACSIncome-Datensatzes (Vorhersage des Einkommens > 50.000 $).
• Aufgaben:
  1. Binäres geschütztes Attribut: Vergleich von „weiß" vs. „nicht-weiß" (Oklahoma-Daten).
  2. Mehrwertiges geschütztes Attribut: Vergleich von fünf Kategorien (z. B. Familienstand in Virginia-Daten).
• Fairness-Metriken: Die Nebenbedingungen basieren auf Verlustdifferenzen zwischen Gruppen, die Konzepte wie Statistical Parity (Unabhängigkeit), Equal Opportunity (Separation) und Sufficiency abdecken.

B. Verglichene Algorithmen

Die Studie implementiert und evaluiert drei Algorithmen, die speziell für stochastische, nicht-konvexe Probleme mit Ungleichheitsnebenbedingungen geeignet sind:

1. Stochastic Ghost (StGh):

   • Kombiniert deterministische Methoden (Ghost-Penalties) mit stochastischem Sampling.
   • Löst ein quadratisches Teilproblem, um eine Suchrichtung zu finden, unter Verwendung von „Geister"-Mini-Batches, um die Erwartungswerte der Gradienten und Nebenbedingungen zu schätzen.
   • Vorteil: Theoretische Konvergenzgarantien für „tame" Funktionen.
   • Nachteil: Hohe Varianz und rechenintensive Mini-Batch-Strategien.

2. Stochastic Smoothed and Linearized Augmented Lagrangian Method (SSL-ALM):

   • Basiert auf der augmentierten Lagrange-Funktion mit einem Glättungsterm (Moreau-Hülle).
   • Behandelt Ungleichheitsnebenbedingungen durch Schlupfvariablen.
   • Vorteil: Benötigt keine großen Mini-Batches; nutzt kleine Stichproben für Ziel und Nebenbedingungen separat.
   • Nachteil: Ursprünglich für lineare Nebenbedingungen entwickelt, hier für nicht-lineare angepasst.

3. Stochastic Switching Subgradient (SSw):

   • Ein „Switching"-Ansatz: Wenn die Nebenbedingung verletzt ist, wird ein Subgradient der Nebenbedingung verwendet; wenn sie erfüllt ist, wird der Gradient der Zielfunktion verwendet.
   • Vorteil: Funktioniert auch bei nicht-glatten (nonsmooth) Funktionen.
   • Nachteil: Neigt dazu, die Zielfunktion (Genauigkeit) zu vernachlässigen, um die Nebenbedingungen zu erfüllen.

Als Baseline dienen:

• Standard SGD (ohne Fairness).
• SGD mit Fairness-Regularisierung (Fairret-Library), bei dem Fairness als Strafterm in die Verlustfunktion integriert wird.

3. Wichtige Beiträge

1. Erster umfassender Benchmark: Das Paper liefert den ersten standardisierten Benchmark für das Training von DNNs unter Fairness-Nebenbedingungen auf realen, großskaligen Datensätzen.
2. Open-Source-Toolbox: Die Autoren stellen eine Python-Package-Bibliothek bereit, die die Implementierung dieser Algorithmen und die Reproduzierbarkeit der Experimente ermöglicht.
3. Theoretische Einordnung: Eine detaillierte Übersicht der aktuellen Literatur zeigt auf, dass keine der existierenden Algorithmen theoretische Konvergenzgarantien für die allgemeine Kombination aus stochastischen, nicht-glatten, nicht-konvexen Zielen und stochastischen Ungleichheitsnebenbedingungen bietet.
4. Empirische Analyse: Umfassende numerische Experimente vergleichen Optimierungsgeschwindigkeit, Konvergenzverhalten und Fairness-Verbesserung.

4. Ergebnisse

Die Experimente auf dem ACSIncome-Datensatz zeigen folgende Erkenntnisse:

• Optimierungsleistung:

  • Augmented Lagrangian Methoden (ALM und SSL-ALM) zeigen das beste Gesamtergebnis. Sie minimieren den Verlust effektiv und halten die Nebenbedingungen auf dem Trainingsset ein.
  • Stochastic Ghost zeigt eine hohe Varianz in Verlust und Nebenbedingungen, ist aber theoretisch interessant.
  • Stochastic Switching Subgradient (SSw) erfüllt die Nebenbedingungen am besten, scheitert jedoch oft daran, die Zielfunktion (Genauigkeit) so stark zu minimieren wie die anderen Methoden.
  • Standard SGD minimiert den Verlust am schnellsten, erfüllt aber keine Fairness-Bedingungen.
  • Regularized SGD (Fairret) erreicht einen Kompromiss, neigt aber dazu, die Nebenbedingungen auf dem Testset zu verletzen, da der Strafgewichtungsparameter schwer optimal zu wählen ist.

• Fairness-Performance:

  • Alle eingeschränkten Optimierungsmodelle verbessern die Fairness-Metriken (Unabhängigkeit, Separation, Suffizienz) im Vergleich zum unbeschränkten SGD signifikant.
  • SSL-ALM und ALM bieten den besten Kompromiss: Sie verbessern die Fairness-Metriken deutlich, während die Genauigkeit nur moderat sinkt.
  • Auf dem Testset zeigen alle eingeschränkten Modelle eine leichte Verzerrung (Bias), was auf das Generalisierungsverhalten von Fairness-Modellen hindeutet.

• Hyperparameter-Sensitivität:

  • Die eingeschränkten Algorithmen (insbesondere SSL-ALM) sind weniger empfindlich gegenüber der Wahl der Hyperparameter als die Regularisierungsmethode (Fairret), bei der die Wahl des Strafgewichts $\lambda$ kritisch für den Trade-off zwischen Genauigkeit und Fairness ist.

5. Bedeutung und Fazit

Das Paper unterstreicht, dass das Training fairer DNNs ein komplexes Optimierungsproblem ist, das über einfache Regularisierung hinausgeht.

• Praktische Relevanz: Die Ergebnisse legen nahe, dass Augmented Lagrangian-basierte Methoden (wie SSL-ALM) derzeit die vielversprechendste praktische Lösung für das Training von DNNs unter harten Fairness-Nebenbedingungen darstellen. Sie bieten eine bessere Kontrolle über den Trade-off zwischen Genauigkeit und Fairness als reine Regularisierung.
• Forschungslücke: Es wird betont, dass es noch keine Algorithmen mit strengen theoretischen Konvergenzgarantien für dieses spezifische, allgemeine Problemsetting gibt. Der Benchmark dient als Katalysator für die Entwicklung robusterer Algorithmen.
• Ethische Warnung: Die Autoren warnen davor, Fairness-Optimierung als „Allheilmittel" zu betrachten. Sie muss Teil eines interdisziplinären Prozesses sein, der den spezifischen Anwendungsfall berücksichtigt, und darf nicht als Ausrede dienen, um ethische Probleme im Geschäftsprozess zu ignorieren.

Zusammenfassend liefert das Paper ein essentielles Werkzeug und eine fundierte Analyse für die Community, um die Grenzen aktueller Optimierungsmethoden im Bereich Fairness zu verstehen und zukünftige Forschung zu lenken.