Neue Untere Schranken für Bilevel-Optimierung mit First-Order-Oracles

In einer kürzlich veröffentlichten Arbeit auf arXiv wird ein bedeutender Fortschritt bei der Analyse der Komplexität von Bilevel-Optimierungsproblemen vorgestellt. Die Autoren konzentrieren sich auf das glatte, nicht-konvexe‑stark-konvexe Setting und entwickeln neue, hart zu lösende Instanzen, die unter deterministischen und stochastischen First‑Order‑Oracles nicht trivialen Untergrenzen aufzeigen.

Für deterministische First‑Order‑Algorithmen zeigen die Ergebnisse, dass mindestens \(\Omega(\kappa^{3/2}\epsilon^{-2})\) Oracle‑Aufrufe erforderlich sind, um einen \(\epsilon\)-genauen stationären Punkt zu finden. Diese Schranke übertrifft die bisher bekannten unteren Schranken für einzelne nicht-konvexe Optimierungsprobleme sowie für nicht-konvexe‑stark-konvexe Min‑Max‑Probleme.

Im stochastischen Fall wird nachgewiesen, dass mindestens \(\Omega(\kappa^{5/2}\epsilon^{-4})\) stochastische Oracle‑Aufrufe nötig sind. Auch hier verbessert die neue Schranke die besten bekannten Grenzen in verwandten Bereichen.

Die Ergebnisse legen ein deutliches Gap zwischen den aktuellen Upper‑ und Lower‑Bounds für Bilevel‑Optimierung offen und zeigen, dass selbst vereinfachte Regime – etwa mit quadratischen Unterproblem‑Zielen – noch weiter untersucht werden müssen, um die optimale Komplexität unter Standard‑First‑Order‑Oracles zu bestimmen.