Online Convex Optimization with Sublinear Noisy Probes

Technische Zusammenfassung: Online-Konvexe Optimierung mit sublinearen verrauschten Sonden

Problemformulierung
Dieses Paper untersucht die Online-Konvexe Optimierung (OCO) über einer konvexen Menge $K \subseteq \mathbb{R}^d$. In dem Standard-Szenario wählt ein Lernender in jeder Runde $t$ eine Entscheidung $x_t \in K$, erleidet einen adversariell gewählten konvexen Verlust $f_t(x_t)$ und erhält volles Feedback (die Funktion $f_t$ oder deren Subgradienten). Das Ziel ist es, den Regret gegenüber der besten fixen Entscheidung im Rückblick zu minimieren.

Die Autoren führen ein vereinheitlichtes Sonden-Modell (Probing Model) ein, das zwei jüngere Forschungsrichtungen generalisiert: die sublineare Abfrage des besten Experten im Experten-Setting [Russo et al., 2024] und das paarweise Vergleichs-Feedback in OCO [Bhaskara et al., 2023b]. In diesem Framework erhält der Lernende ein Budget von $k \le T$ paarweisen Sonden (pairwise probes). In einer Sondierungsrunde kann der Lernende vor der Auswahl von $x_t$ zwei Punkte $\{y_{t,1}, y_{t,2}\} \subseteq K$ abfragen und erhält eine Indikation darüber, welcher Punkt den geringeren Verlust aufweist. Entscheidend ist, dass diese Sonden verrauscht sind: Mit einer Wahrscheinlichkeit $\delta$ gibt der Orakel den Punkt mit dem höheren Verlust zurück (die „falsche“ Antwort), und mit einer Wahrscheinlichkeit $1-\delta$ den korrekten Minimierer zurück. Der Rauschparameter $\delta \in [0, 1]$ ist für den Lernenden unbekannt.

Das Protokoll setzt einen oblivious Adversary (vergesslichen Gegner) voraus, der die Sequenz der Verlustfunktionen $\{f_t\}_{t=1}^T$ festlegt, bevor der Lernende entscheidet, ob er in einer spezifischen Runde eine Sonde durchführt. Diese Einschränkung ist entscheidend; könnte der Adversary die Sondierungsentscheidung anpassen, könnte die Sonde nutzlos gemacht werden (z. B. indem die Verluste in den Sondierungsrunden auf 0 gesetzt werden), was den Regret-Bound auf $\Theta(\sqrt{T-k})$ verschlechtern würde.

Methodik
Der vorgeschlagene Algorithmus ist eine adaptive, sondenerweiterte Version des Continuous Exponential Weights (CEW). Die zentrale technische Erkenntnis beruht auf einem Varianzreduktionseffekt kombiniert mit einer Zweitordnung-Analyse (varianzbasiert) des CEW-Algorithmus.

1. Varianzreduktion durch Sondierung:
   In einer Sondierungsrunde sampelt der Algorithmus zwei Punkte unabhängig von der aktuellen Dichteverteilung $p_t$. Indem er den Punkt mit dem beobachteten geringeren Verlust spielt (oder den durch die Sonde vorgeschlagenen Punkt), sinkt der erwartete Verlust um einen Betrag, der proportional zur Varianz der Verlustfunktion unter $p_t$ ist, bezeichnet als $v_t = \text{Var}_{x \sim p_t}[f_t(x)]$. Speziell für rauschfreie Sonden sinkt der erwartete Verlust um $v_t$.

2. Umgang mit verrauschten Sonden (Meta-Learner):
   Da $\delta$ unbekannt ist, verwendet der Algorithmus einen leichtgewichtigen Meta-Learner (speziell AdaHedge), um zu entscheiden, ob er dem Vorschlag der Sonde „folgt“ (follow) oder ihn „invertiert“ (invert). Der Meta-Learner operiert auf zwei Aktionen: $F$ (Follow) und $I$ (Invert). Er aktualisiert seine Gewichte basierend auf den Verlusten, die durch diese beiden hypothetischen Aktionen in den Sondierungsrunden entstehen würden. Dies ermöglicht es dem Algorithmus, der Sonde adaptiv zu vertrauen, wenn sie informativ ist ($\delta$ fern von $1/2$), und sie zu ignorieren, wenn sie wenig informativ ist.

3. Regret-Zerlegung:
   Die Regret-Analyse zerlegt den Gesamtverlust in zwei Komponenten:

   • Nicht-Sondierungsrunden: Der Algorithmus folgt dem Standard-CEW-Update. Der Regret wird mittels einer Zweitordnung-Analyse (nach de Rooij et al., 2014) begrenzt, die den Basis-Regret mit dem kumulativen Varianzwert $V_T = \sum v_t$ in Beziehung setzt.
   • Sondierungsrunden: Der Verlust wird durch den Verlust der besseren der beiden Meta-Learner-Aktionen ($F$ oder $I$) plus eines Regret-Terms für den Meta-Learner begrenzt. Die Analyse zeigt, dass die „bessere“ Aktion eine Verlustreduktion erzielt, die proportional zu $|1-2\delta|v_t$ ist.

Wichtigste Ergebnisse
Das Paper etabliert, dass ein sublinearer Budget an verrauschten paarweisen Sonden den Worst-Case-Regret im Full-Feedback-OCO-Regime nachweislich verbessern kann.

• Allgemeine konvexe Verluste: Für allgemeine konvexe Verluste, die in $[0, 1]$ über einer konvexen Menge $K$ beschränkt sind, ist der erwartete Regret:
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{dT \ln T}, \frac{dT \ln T}{k |1 - 2\delta|} \right\} \right)$$
  Diese Schranke ist (bis auf logarithmische Faktoren in $T$) tight in Bezug auf den Horizont $T$, das Sondierungsbudget $k$ und den Rauschparameter $\delta$. Der Regret verschlechtert sich stetig, wenn $\delta \to 1/2$ (Münzwurf).

• Vorhersage mit Experten: Im Spezialfall des Experten-Settings (lineare Verluste über den Eckpunkten des Simplex $\Delta^{d-1}$) verbessert sich die Schranke zu:
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{T \ln d}, \frac{T \ln d}{k |1 - 2\delta|} \right\} \right)$$
  Diese Raten sind in allen Parametern, einschließlich der Dimension $d$, vollständig tight.

Bedeutung und Beiträge
Die Autoren beanspruchen mehrere signifikante Beiträge für sich:

1. Vereinheitlichung: Die Arbeit vereint das diskrete „Best-Expert“-Sondierungsmodell und das kontinuierliche „Pairwise Comparison“-Modell in einem einzigen Framework und zeigt, dass paarweise Sonden ebenso informativ wie Best-Expert-Sonden für das Erreichen optimaler Regret-Raten sind.
2. Robustheit gegenüber Rauschen: Im Gegensatz zu früheren Arbeiten, die oft rauschfreie Modelle oder spezifische Rauschmodelle voraussetzen, handhabt dieses Framework unbekannte Rauschniveaus $\delta$ und erreicht eine optimale Abhängigkeit von $|1-2\delta|$.
3. Technische Neuartigkeit: Die Analyse vermeidet Differential-Privacy-Mechanismen und Annahmen bezüglich Gradientennormen oder Krümmung (die in früheren Arbeiten wie Bhaskara et al., 2023b erforderlich waren). Stattdessen nutzt sie ein varianzbasiertes Reduktionsargument.
4. Optimalität: Das Paper liefert passende Lower Bounds (in Anhang A), die zeigen, dass die abgeleiteten Raten für das Experten-Setting tight sind und für allgemeine konvexe Mengen tight in $T, k, \delta$ sind.

Die Autoren merken an, dass die theoretischen Garantien zwar stark sind, der Hauptalgorithmus jedoch die Berechnung von Integralen über konvexe Mengen erfordert, was im Allgemeinen rechenintensiv sein kann. Sie identifizieren die Entwicklung effizienter Algorithmen, die vergleichbare Garantien erreichen, als eine offene Forschungsrichtung.