Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

Technische Zusammenfassung: Nicht-expansive stochastische Approximation mit zwei Zeitskalen

Problemstellung
Die vorliegende Arbeit untersucht die Konvergenzraten der stochastischen Approximation mit zwei Zeitskalen (Two-Time-Scale Stochastic Approximation, TTSA) in einem Regime, in dem die schnelle Abbildung kontraktiv, aber die reduzierte langsame Abbildung nur nicht-expansiv ist. Dieser Kontext ergibt sich aus der Minimax-Optimierung, variablen Ungleichungen und eingeschränkter stochastischer Approximation. Im Gegensatz zur kontraktiven TTSA, bei der die langsame Variable gegen ein eindeutiges Gleichgewicht konvergiert, weist der nicht-expansive Fall eine potenziell nicht-einzelwertige Fixpunktmenge auf. Folglich ist die natürliche Leistungsmetrik das Fixpunkt-Residuum $p(y) = h(y) - y$ anstatt des Abstand zu einem spezifischen Punkt.

Vorangegangene Arbeiten etablierten eine Last-Iterate-Mittelwertquadrat-Residuenrate von $O(k^{-1/4+\epsilon})$ für dieses Regime. Die Arbeit zielt darauf ab, den theoretischen Ursprung dieses $1/4$-Exponenten zu erklären und zu bestimmen, ob algorithmische Modifikationen diesen verbessern können.

Methodik und theoretischer Rahmen
Die Autoren zerlegen die Fehlerdynamik in zwei distinkte Komponenten: die intrinsische Konvergenz der nicht-expansiven langsamen Rekursion und das „Leckage“ (Leakage) der schnellen Tracking-Fehler in das langsame Oracle.

1. Schärfe der Fixed-Schedule KM-Barriere:
   Die Arbeit stellt zunächst fest, dass die klassische Krasnoselskii–Mann (KM)-Residuen-Skala, definiert durch den Kehrwert der Summe $\sum \beta_i(1-\beta_i)$, für jede feste langsame Schrittweiten-Schedule $(\beta_k)$ scharf ist. Unter Verwendung eines planaren Rotationsbeispiels beweisen die Autoren eine Finite-Horizon-Untere Schranke, die zeigt, dass kein unregularisierter KM-Update eine schnellere Worst-Case-Residuen-Abnahme als diese Skala für eine gegebene Schedule erreichen kann. Dies impliziert, dass eine Verbesserung der Rate eine Änderung des algorithmischen Regimes oder der Oracle-Struktur erfordert und nicht bloß eine Verfeinerung der Analyse des Standard-KM-Updates darstellt.

2. Diagnose des $1/4$-Exponenten:
   Die Arbeit identifiziert die „First-Order Fast-Manifold Leakage“ als primäres Hindernis. In der rohen TTSA evaluiert das langsame Oracle die Abbildung am aktuellen schnellen Iterat $X_k$ anstatt am wahren Gleichgewicht $x^*(Y_k)$. Aufgrund der Lipschitz-Stetigkeit der langsamen Abbildung in der schnellen Koordinate ist der Fehler $g(X_k, Y_k) - h(Y_k)$ erster Ordnung im Tracking-Fehler $\|X_k - x^*(Y_k)\|$. Der Tracking-Fehler selbst wird durch ein Gleichgewicht zwischen der schnellen stochastischen Varianz ($\alpha_k$) und dem deterministischen Rückstand hinter dem beweglichen Ziel ($(\beta_k/\alpha_k)^2$) gesteuert. Selbst unter der Standard-Separationsbedingung $\beta_k^2/\alpha_k^3 \lesssim 1$ führt die Kombination aus der scharfen KM-Skala und dieser First-Order-Leakage zu einer Gesamtsample-Komplexität von $T^{-1/4+o(1)}$. Die Verletzung der Separationsbedingung verbessert die Rate nicht; sie verschiebt lediglich den Engpass von der statistischen Varianz zum Moving-Target-Lag, welcher dennoch als First-Order-Perturbation einfließt.

3. Bias-Korrektur via Residuen-Präkonditionierung:
   Um diese First-Order-Leakage zu überwinden, führen die Autoren ein residuen-präkonditioniertes langsames Oracle ein. Durch Nutzung der Ableitungen der schnellen und langsamen Abbildungen konstruieren sie einen Korrekturterm, der die lineare Abhängigkeit vom schnellen Tracking-Fehler aufhebt.
   Konkret, falls $A(y) = I - \nabla_x f(x^*(y), y)$ und $C(y) = \nabla_x g(x^*(y), y)$ sind, lautet der Präkonditionier $P^*(y) = C(y)A(y)^{-1}$. Das korrigierte Oracle ist definiert als:
   $$H_{corr}(x, y) = g(x, y) + P^*(y)(f(x, y) - x)$$
   Eine Taylor-Entwicklung zeigt, dass diese Korrektur den Bias des langsamen Oracles von erster Ordnung ($O(\|e\|)$) auf zweite Ordnung ($O(\|e\|^2)$) reduziert, wobei $e$ der schnelle Tracking-Fehler ist.

Wesentliche Beiträge und Ergebnisse

Die Arbeit präsentiert drei wesentliche theoretische Ergebnisse, die von der Diagnose der Rohmethode bis hin zu optimierten Algorithmen unter strukturierten Oracle-Annahmen fortschreiten.

1. Fixed-Schedule Untere Schranke:
   Die Autoren beweisen, dass für jede feste langsame Schrittweiten-Schedule das Mittelwertquadrat-Residuum einer unregulierten KM-Iteration nicht uniform über die Skala $(\sum \beta_i(1-\beta_i))^{-1}$ hinaus verbessert werden kann. Dies bestätigt, dass der $1/4$-Exponent in vorangegangener Arbeit kein Artefakt einer lockeren Analyse ist, sondern eine Konsequenz der scharfen KM-Residuen-Skala in Kombination mit First-Order-Leakage.

2. Nested Bias-Corrected Algorithmus ($T^{-1/3}$):
   In einem geschachtelten (nested) Tikhonov-KM-Framework wenden die Autoren die Residuen-Präkonditionierung an.

• Unkorrigiert: Die geschachtelte Methode mit einem rohen Oracle erreicht eine Gesamtsample-Rate von $T^{-1/4+o(1)}$.
• Korrigiert: Durch die Verwendung des präkonditionierten Oracles wird der quadratische Bias des langsamen Oracles zu $O(n^{-2})$ (wobei $n$ die Anzahl der inneren Samples ist) anstatt $O(n^{-1})$. Diese strukturelle Änderung verbessert die gesamte Sample-Komplexität auf $T^{-1/3+o(1)}$.
• Hinweis: Dieses Ergebnis setzt den Zugriff auf den exakten Präkonditionier $P^*(y)$ oder einen Schätzer voraus, der spezifische Produkt-Genauigkeitsbedingungen erfüllt.

3. Single-Loop Learned Preconditioner ($T^{-1/2}$):
   Um den wiederholten Kosten der inneren Loop-Lösungen in der geschachtelten Methode zu vermeiden, schlagen die Autoren einen Single-Loop-Algorithmus vor, der das schnelle Gleichgewicht, die langsame Variable und den Präkonditionier-Matrix online verfolgt.

• Diese Methode hält laufende Schätzungen von $X_k$, $Y_k$ und $P_k$ unter Verwendung stochastischer Ableitungs-Beobachtungen aufrecht.
• Unter Glattheitsannahmen (Differenzierbarkeit der Abbildungen und Zugriff auf Ableitungs-Oracles) erreicht dieser Ansatz eine Gesamtsample-Rate von $T^{-1/2+o(1)}$ mit $O(1)$ primitiven Samples pro Iteration.
• Diese Verbesserung beruht auf der Fähigkeit, den Leakage-Präkonditionier online zu lernen, wodurch die Kosten der inneren Lösung amortisiert werden.

Bedeutung und Ansprüche
Die Arbeit beansprucht, eine vollständige theoretische Erklärung für den $1/4$-Exponenten in der nicht-expansiven TTSA zu liefern, indem sie diesen dem Zusammenspiel zwischen der scharfen KM-Residuen-Skala und der First-Order-Fast-Manifold-Leakage zuschreibt. Der primäre Beitrag besteht darin, zu zeigen, dass diese Barriere nicht fundamental für die Problemklasse ist, sondern spezifisch für die „rohe“ Oracle-Struktur gilt.

Durch die Einführung eines residuen-präkonditionierten Oracles zeigen die Autoren, dass die Leakage auf zweite Ordnung reduziert werden kann, wodurch die Konvergenzraten verbessert werden. Das $T^{-1/3}$-Ergebnis dient als Zertifikat dafür, dass die Bias-Korrektur effektiv ist, während das $T^{-1/2}$-Ergebnis demonstriert, dass diese Gewinne in einem Single-Loop-Setting realisiert werden können, sofern Ableitungs-Informationen verfügbar sind. Die Autoren rahmen diese Ergebnisse explizit als „Structured-Oracle“-Errungenschaften ein und merken an, dass sie auf Differenzierbarkeit und Zugriff auf Jacobian-bezogene Informationen angewiesen sind, was sie von Black-Box-Nicht-Expansions-Fixpunkt-Methoden unterscheidet. Die Arbeit beansprucht nicht, das Problem für allgemeine Black-Box-Oracles gelöst zu haben, sondern identifiziert die spezifische strukturelle Modifikation (Bias-Kompensation), die erforderlich ist, um die Konvergenzrate in Anwesenheit von Glattheit zu beschleunigen.