Technische Samenvatting: Strafbasede Eerste-orde Methoden voor Bi-niveau Optimalisatie met Minimax en Beperkte Onderliggende Problemen

Probleemformulering

Dit artikel behandelt een klasse van bi-niveau optimalisatieproblemen waarbij zowel het bovenste als het onderste niveau minimax-structuren vertonen. De algemene formulering is gedefinieerd als:
$$\min_{x_1, y_1, y_2} \left\{ \max_{x_2} f(x_1, x_2, y_1, y_2) \mid (y_1, y_2) \in \arg\min_{z_1} \max_{z_2} \tilde{f}(x_1, z_1, z_2) \right\}$$
waarbij $(y_1, y_2)$ een zadelpunt voorstelt van de onderliggende functie $\tilde{f}$. De auteurs veronderstellen specifieke structurele eigenschappen: $f$ en $\tilde{f}$ kunnen worden ontbonden in gladde componenten en geschikte gesloten convexe functies, met specifieke convexiteits/concaviteits-eigenschappen met betrekking tot hun respectieve variabelen (bijvoorbeeld is $\tilde{f}$ convex in $y_1$ en concav in $y_2$).

Een aanzienlijk deel van dit werk richt zich op bi-niveau problemen waarbij het onderste niveau een convex minimalisatieprobleem is met convexe niet-lineaire ongelijkheidsbeperkingen:
$$\min_{x_1, y_1} \left\{ f(x_1, y_1) \mid y_1 \in \arg\min_{z_1} \{ \bar{f}(x_1, z_1) \mid \bar{g}(x_1, z_1) \leq 0 \} \right\}$$
Onder de Slater-voorwaarde wordt dit beperkte probleem herschreven als een speciaal geval van het algemene minimax bi-niveau kader via Lagrange-dualiteit.

Bestaande literatuur richt zich grotendeels op bi-niveau optimalisatie waarbij het onderste niveau een enkelvoudig-objectief minimalisatie is (vaak sterk convex). Methoden die vertrouwen op hypergradienten of impliciete differentiatie falen vaak wanneer het onderste niveau slechts convex, niet-convex is, of een minimax-structuur bezit. Dit werk beoogt deze kloof te dichten door eerste-orde methoden te ontwikkelen voor de minimax onderliggende setting zonder sterk convexiteit te vereisen.

Methodologie

De voorgestelde aanpak maakt gebruik van een strafherformulering gebaseerd op de waarde-functie. Het beperkte bi-niveau probleem wordt getransformeerd tot een onbeperkt (of eenvoudiger beperkt) minimax-probleem door de invoering van een strafparameter $\rho$.

Deterministische Setting

1. Strafherformulering: Het oorspronkelijke probleem wordt herschreven tot een enkel-niveau minimax-probleem:
   $$\min_{x_1, y_1, y_2} \max_{x_2, z_1, z_2} P_\rho(x_1, x_2, y_1, y_2, z_1, z_2)$$
   waarbij $P_\rho$ de doelfunctie en de strafterm $\rho(p(x_1, y_1) - d(x_1, y_2))$ omvat, die de dualiteitskloof van het onderliggende probleem voorstelt.
2. Algoritme: De auteurs stellen een ongauwe proximaal punt-methode voor. De buitenste lus updatet de primaal-duale variabelen door een reeks sterk-convex-stark-concave (SCSC) subproblemen op te lossen.
3. Subprobleem-oplosser: Elk subprobleem wordt opgelost met een optimale eerste-orde methode (specifiek, een variant van de methode van Lu en Mei [52] of Kovalev en Gasnikov [37]), aangeduid als OptFOM.
4. Complexiteit: De methode vindt een $\epsilon$-KKT-punt met een orakelcomplexiteit van $\tilde{O}(\epsilon^{-4})$.

Stochastische Setting

Wanneer alleen stochastische gradient-orakels beschikbaar zijn voor de gladde componenten:

1. Algoritme: De deterministische proximaal punt-methode wordt aangepast om een Stochastisch Versnelde Primaal-Duale (SAPD) methode te gebruiken (specifiek SAPD+ van Zhang et al. [75]) om de binnenste subproblemen op te lossen.
2. Convergentie: De methode vindt een "bijna" $\epsilon$-KKT-punt (waarbij de oplossing binnen een afstand $\epsilon$ ligt van een exact $\epsilon$-KKT-punt) met een stochastische orakelcomplexiteit van $\tilde{O}(\epsilon^{-9})$.

Toepassing op Beperkte Onderliggende Problemen

Voor het specifieke geval van bi-niveau optimalisatie met een beperkt convex onderliggend niveau (Probleem 4) tonen de auteurs aan dat onder de Slater-voorwaarde de Lagrange-multiplicatoren begrensd zijn binnen een doos $[0, B]^l$. Dit maakt het mogelijk het beperkte probleem te herschrijven als het algemene minimax bi-niveau probleem (Probleem 1) door de duale variabelen in te voeren als expliciete optimalisatievariabelen met doosbeperkingen. Deze herformulering omzeilt de noodzaak van een binnenste strafparameter, wat leidt tot verbeterde complexiteitsgrenzen in vergelijking met eerdere werken.

Belangrijkste Bijdragen

1. Eerste Complexiteitsresultaten voor Bi-niveau Minimax: Het artikel vestigt de eerste complexiteitsgrenzen voor deterministische en stochastische eerste-orde methoden voor bi-niveau optimalisatie waarbij het onderste niveau een minimax-probleem is.
   • Deterministische complexiteit: $\tilde{O}(\epsilon^{-4})$.
   • Stochastische complexiteit: $\tilde{O}(\epsilon^{-9})$.
2. Verbeterde Grenzen voor Beperkte Bi-niveau Problemen: Door bi-niveau problemen met convexe beperkte onderliggende niveaus te herschrijven als instanties van het voorgestelde minimax-kader, bereiken de auteurs een complexiteit van $\tilde{O}(\epsilon^{-4})$. Dit verbetert bestaande resultaten voor slechts convexe onderliggende niveaus ($\tilde{O}(\epsilon^{-7})$ in [53]) en sterk convexe onderliggende niveaus ($\tilde{O}(\epsilon^{-6})$ in [51]). De verbetering vloeit voort uit het vermijden van het gebruik van een tweede strafparameter voor de binnenste beperkingen, wat eerder leidde tot hogere gladheidsparameters.
3. Empirische Validatie:
   • Synthetische Data: Op beperkte lineaire bi-niveau problemen vertoont de voorgestelde methode concurrerende convergentiesnelheden ten opzichte van bestaande strafgebaseerde methoden (FOP en SMO), met name wanneer de Lipschitz-constante wordt afgestemd.
   • Wereldse Toepassing: De methode wordt toegepast op hyperparameter-tuning voor Distributionally Robust Optimization (DRO) in deep learning. Op de CelebA- en Waterbirds-datasets presteert de voorgestelde stochastische bi-niveau aanpak beter dan standaard DRO-methoden wat betreft de nauwkeurigheid van de ergste groep, terwijl een vergelijkbare gemiddelde nauwkeurigheid wordt behouden.

Resultaten en Betekenis

Het artikel beweert dat het voorgestelde strafgebaseerde kader een geünificeerde aanpak biedt voor het behandelen van bi-niveau problemen met minimax-structuren, een setting die eerder niet was onderzocht in de literatuur met betrekking tot eerste-orde complexiteit.

• Theoretische Betekenis: Het werk overbrugt de kloof tussen bi-niveau optimalisatie en minimax-optimalisatie, en biedt rigoureuze convergentiegaranties zonder te vertrouwen op aannames van sterk convexiteit voor het onderliggende probleem. De reductie van complexiteit van $\tilde{O}(\epsilon^{-7})$ naar $\tilde{O}(\epsilon^{-4})$ voor beperkte onderliggende niveaus wordt gepresenteerd als een aanzienlijke theoretische vooruitgang.
• Praktische Betekenis: De toepassing op DRO demonstreert de bruikbaarheid van de methode in machine learning-scenario's die verdelingsschuivingen en groepsgerechtigheid omvatten. De resultaten op de CelebA- en Waterbirds-datasets tonen aan dat de methode de uitdaging van "ergste-groep"-optimalisatie effectief kan aanpakken, waarbij een hogere nauwkeurigheid voor de ergste groep wordt bereikt dan bij baseline DRO-methoden.

De auteurs erkennen beperkingen, waaronder de vereiste van compacte toelaatbare domeinen, het gebruik van een opgeheven ruimte voor KKT-definities, en de hoge complexiteit van het stochastische geval ($\tilde{O}(\epsilon^{-9})$), en merken op dat variantie-reductietechnieken een richting voor toekomstig werk zouden kunnen zijn.