Technische Samenvatting: Stochastische Regret-garanties voor Online Zeroth- en First-Order Bilevel Optimalisatie

Probleemstelling

Het artikel behandelt Online Bilevel Optimalisatie (OBO), een raamwerk waarin zowel de buitenste als de binnenste doelstellingen in de tijd evolueren, waardoor dynamische updates van beslissingsvariabelen vereist zijn zonder voorafgaande kennis van toekomstige uitkomsten. In de standaard offline setting minimaliseert bilevel optimalisatie een buitenste doelstelling $f(x, y^*(x))$ onder de voorwaarde dat $y^*(x)$ de oplossing is van een binnenste minimaliseringsprobleem $g(x, y)$. In de online setting veranderen de functies $f_t$ en $g_t$ in elke ronde $t$, en moet de agent sequentieel $x_t$ en $y_t$ selecteren.

Een kritieke uitdaging in de bestaande OBO-literatuur is de afhankelijkheid van deterministische venster-gesmoothde regret-minimalisatie. Huidige methoden (bijvoorbeeld OAGD, SOBOW) middelen doelstellingen over een venster $w$ om sublineaire regret-grenzen te bereiken. De auteurs betogen echter dat wanneer functies snel veranderen, venster-smoothing de systeemprestaties kan verkeerd weergeven en het ware regret-gedrag niet kan vangen. Bovendien vereisen bestaande benaderingen vaak toegang tot exacte gradiënten, Hessiaanse matrices en Jacobiaanse matrices, of vertrouwen ze op dure iteratieve oplosmethoden (zoals Conjugate Gradient) om de hypergradiënt te benaderen, wat de schaalbaarheid in grootschalige of black-box settings beperkt.

Het artikel richt zich op stochastische OBO, waarbij alleen ruisbeïnvloede evaluaties van functies, gradiënten en Hessiaanse matrices beschikbaar zijn. Het doel is het minimaliseren van stochastisch bilevel regret zonder venster-smoothing en met beperkte orakeltoegang (specifiek functiewaarde-orakels in de zeroth-order setting).

Methodologie

De auteurs stellen een nieuw raamwerk voor dat centraal staat om een nieuwe zoekrichting die sublineaire regret mogelijk maakt zonder venster-smoothing. Dit raamwerk wordt geïmplementeerd via twee primaire algoritmen:

1. Simultane Online Gradient Descent (SOGD)

Voor settings met toegang tot first-order en binnenste second-order orakels, introduceert het artikel SOGD (Algoritme 1).

• Nieuwe Zoekrichting: In tegenstelling tot eerdere methoden die venster-gesmoothde gradiënten of alternerende lussen gebruiken, hanteert SOGD een recursieve momentum-achtige zoekrichting (Vergelijking 7) die het verschil tussen huidige en vorige gradiënten incorporateert. Deze richting wordt gebruikt voor het gelijktijdig updaten van de follower-variabele $y$, de hulpvariabele $v$ (het oplossen van het lineaire systeem) en de leader-variabele $x$.
• Enkel-lus Structuur: Het algoritme update alle variabelen ($x_t, y_t, v_t$) in een enkele lus per ronde, waardoor de rekenkundige overhead van meerdere binnen-lus iteraties wordt vermeden, zoals vereist door methoden zoals SOBOW.
• Benadering van Lineaire Systemen: In plaats van het lineaire systeem $\nabla^2_y g_t v + \nabla_y f_t = 0$ exact op te lossen, update SOGD een hulpvariabele $v_t$ met een enkele gradiëntstap, waardoor de niet-lineaire structuur van de hypergradiënt effectief wordt ontkoppeld.

2. Zeroth-Order SOGD (ZO-SOGD)

Voor black-box settings waar gradiënten niet beschikbaar zijn, stelt het artikel ZO-SOGD (Algoritme 2) voor.

• Functiewaarde-orakels: Deze methode vertrouwt uitsluitend op ruisbeïnvloede functiewaarde-evaluaties. Het construeert onbevooroordeelde schatters voor gradiënten, Hessiaanse matrices en Jacobiaanse matrices met behulp van Gaussische smoothing en eindige-differentiebenaderingen.
• Schattingstrategie:
  • Gradiënten worden geschat met behulp van twee-punts functiewaarde-evaluaties (Vergelijkingen 24-25).
  • Hessiaans-vector en Jacobiaans-vector producten worden benaderd via eindige differenties van de geschatte gradiënten (Vergelijking 26).
• Convergentiecontrole: Het algoritme hanteert een projectiestap op de hulpvariabele $v$ om de norm ervan te begrenzen, waardoor de variantie in de updates wordt gecontroleerd.

Belangrijkste Bijdragen

1. Stochastische Regret-minimalisatie zonder Venster-smoothing:
   Het artikel introduceert een nieuwe zoekrichting en bewijst dat zowel first-order (SOGD) als zeroth-order (ZO-SOGD) algoritmen sublineair stochastisch bilevel regret bereiken met een venstergrootte van $w=1$. Dit verwijdert de noodzaak voor venster-smoothing, wat vaak beperkend is in snel veranderende omgevingen. De regret-grenzen hangen af van padlengtes en functieveranderingen van de onderliggende sequenties.

2. Efficiëntie in Orakel-afhankelijkheid:
   Het raamwerk reduceert de orakel-afhankelijkheid aanzienlijk.

   • First-Order: Het vermijdt de noodzaak voor exacte oplossingen van het binnenste lineaire systeem, door een enkel-staps update te gebruiken voor de hulpvariabele.
   • Zeroth-Order: Het is de eerste die regret-garanties biedt voor OBO met uitsluitend functiewaarde-orakels voor zowel de leader- als de follower-doelstellingen. Het schat succesvol Hessiaanse matrices, Jacobiaanse matrices en gradiënten af uit functiewaarden, waardoor de uitdaging van de geneste structuur in bilevel-problemen wordt aangepakt.

3. Eén Iteratie van de Subprobleem-oplosser:
   De voorgestelde algoritmen vereisen slechts één iteratie van de subprobleem-oplosser per ronde. Dit staat in contrast met methoden zoals SOBOW, die Conjugate Gradient gebruiken met toenemende iteraties, waardoor de rekenkundige efficiëntie en schaalbaarheid worden verbeterd.

Resultaten en Regret-grenzen

Het artikel stelt theoretische regret-grenzen vast voor beide algoritmen onder standaard aannames (sterke convexiteit van de binnenste doelstelling, gladheid en begrenste variantie van stochastische schatters).

• SOGD (First-Order):
  Theorema 2.6 garandeert een bilevel lokale regret-grens van:
  $$BL\text{-}Reg_T \le O\left( T^{1/3}(\sigma^2 + \Delta_T) + T^{2/3}\Psi_T \right)$$
  waarbij $\sigma^2$ de variantie van stochastische schatters vertegenwoordigt, en $\Delta_T, \Psi_T$ de variaties in de omgeving vastleggen (functiewaarden, gradiënten, Hessiaanse matrices en Jacobiaanse matrices). Onder geschikte voorwaarden waarbij deze variaties sublineair groeien, is de gemiddelde dynamische regret sublineair ($o(T)$). Opmerkelijk is dat dit een verbetering is op de $O(T^{-1/2}\sigma^2)$-snelheid van eerdere stochastische OBO-methoden.

• ZO-SOGD (Zeroth-Order):
  Theorema 3.2 biedt de eerste regret-garantie voor OBO met uitsluitend ruisbeïnvloede functiewaarde-evaluaties. De grens is:
  $$BL\text{-}Reg_T \le O\left( (d_1 + d_2)^{3/4} T^{1/3}(\hat{\sigma}^2 + \hat{\Delta}_T) + (d_1 + d_2)^{3/2} T^{2/3}\hat{\Psi}_T \right)$$
  De afhankelijkheid van de dimensie $(d_1 + d_2)$ komt overeen met optimale resultaten voor offline min-max problemen. De grens hangt ook af van batchgroottes en smoothing-parameters.

Experimentele Validatie

De auteurs valideren hun aanpak op twee toepassingen:

1. Online Black-Box Adversarial Attacks (BBAA): Met behulp van MNIST-data werden ZO-SOGD en ZO-SOGD (Adam) vergeleken met single-level zeroth-order baselines (ZO-O-GD, ZO-O-Adam, enz.). Resultaten toonden aan dat ZO-SOGD superieure aanvalsaccuraatheid bereikte en effectieve perturbaties behield, ondanks de toegevoegde complexiteit van de buitenste optimalisatie.
2. Parametrische Loss-tuning voor Ongelijke Data: De algoritmen werden getest op het afstellen van logit-aanpassingen voor ongelijke datasets. SOGD vertoonde een snellere runtime in vergelijking met SOBOW (vanwege de enkel-lus structuur) en behaalde concurrerende accurateit in het balanceren van klassen naarmate de data-distributie verschuift.

Betekenis en Claims

Het artikel claimt de beperkingen van bestaande OBO-algoritmen te overwinnen die afhankelijk zijn van uitgebreide orakelinformatie en hoge rekenkosten. Door een nieuwe zoekrichting in te voeren en beperkte feedback (inclusief zeroth-order) te gebruiken, bereiken de voorgestelde methoden sublineair bilevel regret zonder venster-smoothing.

De auteurs positioneren dit werk als een belangrijke stap naar efficiënte online bilevel optimalisatie in dynamische, niet-convexe en black-box settings. Zij wijzen expliciet op een beperking: de resultaten focussen op niet-convexe regret-grenzen en breiden geen garanties uit naar convexe settings. Het werk wordt gepresenteerd als een fundamenteel raamwerk voor het behandelen van dynamische bilevel-problemen waarbij traditionele smoothing-technieken de prestaties niet nauwkeurig weerspiegelen.