Oracle-effizientes Hybrid-Lernen bei eingeschränkten Gegnern

In der Hybrid-Online-Lernaufgabe werden die Merkmale zufällig aus einer unbekannten Verteilung gezogen, während die Labels von einem Gegner adversarial erzeugt werden. Dieses Setting liegt zwischen klassischer statistischer Lernmethodik und vollständig adversarialen Online-Lernmodellen und bietet daher ein besonders spannendes Forschungsfeld.

Frühere Arbeiten haben bereits zwei gegensätzliche Richtungen aufgezeigt: Auf der einen Seite stehen statistisch optimale Algorithmen, die jedoch rechnerisch unpraktisch sind (Wu et al., 2023). Auf der anderen Seite gibt es rechnerisch effiziente Verfahren, die jedoch statistisch suboptimal bleiben (Wu et al., 2024). Das neue Papier strebt an, beide Ziele gleichzeitig zu erreichen.

Der Ansatz konzentriert sich auf eine strukturierte Variante des Problems, bei der der Gegner auf die Auswahl von Labels aus einer festen, aber ausdrucksstarken Funktionsklasse R beschränkt ist. Unter dieser Bedingung wird ein neuer Lernalgorithmus vorgestellt, der mit Hilfe eines ERM‑Orakels effizient arbeitet und einen Regret‑Wert erzielt, der sich mit der Rademacher‑Komplexität einer Klasse verbindet, die aus der Hypothesenklasse H des Lerners und der Labelklasse R des Gegners abgeleitet ist.

Ein bedeutendes Nebenresultat ist die Entwicklung eines Orakel‑effizienten Algorithmus zur Berechnung von Gleichgewichten in stochastischen Null‑Sum‑Spielen. Dabei können die Aktionsräume hochdimensional sein, solange die Auszahlungsfunktion eine Art niedriger Dimensionalität aufweist.

Technisch wurden mehrere neue Werkzeuge eingeführt: eine Frank‑Wolfe‑Reduktion mit einem „truncated entropy regularizer“ sowie ein neuer Tail‑Bound für Summen von „hybrid“ Martingaldifferenzsequenzen. Diese Innovationen bilden die Grundlage für die Analyse und das Design des vorgestellten Lernalgorithmus.