Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach

Technische Samenvatting: Oplossen van het Offline en Online Min-Max Probleem van Niet-Gladde Submodulair-Concave Functies

Probleemformulering
Dit werk behandelt gemengd-gehele min-max en max-min optimalisatieproblemen van de vorm:
$$\max_{y \in Y} \min_{S \subset Q} f(S, y) \quad \text{en} \quad \min_{S \subset Q} \max_{y \in Y} f(S, y)$$
waarbij $Q = [n]$ een grondverzetting is van $n$ elementen, $2^Q$ de machtsverzetting aanduidt, en $Y \subset \mathbb{R}^m$ een compacte convexe verzameling is. De doelfunctie $f: 2^Q \times \mathbb{R}^m \to \mathbb{R}$ wordt verondersteld submodulair te zijn met betrekking tot de verzetsvariabele $S$ en concav met betrekking tot de continue variabele $y$. Cruciaal is dat de functie niet-glad (niet-differentieerbaar) mag zijn met betrekking tot beide variabelen. De auteurs beogen een $\epsilon$-zadelpunt te berekenen, gedefinieerd als een paar $(\bar{S}, \bar{y})$ zodat het dualiteitsgat begrensd is door $\epsilon$.

Methodologie
De voorgestelde aanpak maakt gebruik van een Zeroth-Order (ZO) raamwerk gebaseerd op de extragradient-methode. De methodologie vertrouwt op twee primaire technieken om de niet-gladheid en de gemengde-variabele structuur te hanteren:

1. Lovász-extensie voor Submodulariteit: Om het discrete submodulaire onderdeel te hanteren, gebruiken de auteurs de Lovász-extensie $f^L$, die de submodulaire verzetsfunctie afbeeldt op een continue, convexe functie over de hyperkubus $[0, 1]^n$. De subgradient van $f^L$ met betrekking tot de verzetsvariabele kan worden berekend met uitsluitend functiewaarde-evaluaties (via een maximale keten van deelverzamelingen), waardoor de noodzaak voor informatie van hogere orde wordt vermeden.
2. Gaussische Gladding voor Concaviteit: Voor de continue concave variabele $y$, waarbij de functie niet-glad kan zijn, passen de auteurs Gaussische gladding toe. Zij definiëren een random oracle met behulp van een twee-punts schatter om de gradient van de gegladde functie te benaderen. Dit maakt gradient-gebaseerde updates mogelijk zonder expliciete toegang tot afgeleiden.

Het resulterende algoritme (Algoritme 1, ZO-EG) werkt in een iteratieve lus:

• Forward-stap: Schat de operator op de huidige iteratie $z_k = (x_k, y_k)$ door Gaussische richtingen te bemonsteren om de random oracle voor $y$ te berekenen en de subgradient voor $x$ te berekenen.
• Extrapolatiestap: Voer een afdalingsstap uit naar een vooruitkijkend punt $\hat{z}_k$.
• Update-stap: Her-schat de operator op $\hat{z}_k$ en voer een tweede afdalingsstap uit om $z_{k+1}$ te updaten.

De methode vereist uitsluitend functiewaarde-vragen (zeroth-order informatie) en neemt geen directe toegang tot gradienten of subgradienten aan.

Belangrijkste Bijdragen en Theoretische Resultaten
Het artikel biedt convergentiegaranties voor zowel offline als online settings:

• Offline Convergentie: De auteurs bewijzen dat het algoritme, in verwachting, convergeert naar een $\epsilon$-zadelpunt. De totale steekproefcomplexiteit blijkt $O(nm^2\epsilon^{-2})$ te zijn, waarbij $n$ de grootte van de grondverzetting is en $m$ de dimensie van de continue variabele. De afhankelijkheid van $n$ vloeit voort uit de kosten per iteratie voor het berekenen van Lovász-extensie subgradienten, terwijl het aantal iteraties afhangt van $m$.
• Online Convergentie: In de online setting, waarbij de kostenfunctie $f_k$ in de tijd verandert, bereikt het algoritme een verwachte online dualiteitsgat van $O(\sqrt{N \bar{P}_N})$. Hierbij is $N$ het aantal iteraties en $\bar{P}_N$ de padlengte van de reeks optimale beslissingen. Dit resultaat sluit aan bij gevestigde dynamische regret-begrenzingen in online optimalisatie.
• Bestaan van Oplossingen: Het artikel bespreekt voorwaarden waaronder zadelpunten bestaan voor het oorspronkelijke discrete probleem door deze te relateren aan de oplossingen van het continue Lovász-extensie probleem, specifiek wanneer de minimalizer van de extensie op een hoekpunt van de hyperkubus ligt.

Numerieke Resultaten en Toepassingen
De theoretische bevindingen worden geïllustreerd door numerieke voorbeelden, met name gericht op adversariële beeldsegmentatie en semi-supervised clustering:

• Offline Adversariële Segmentatie: De methode wordt toegepast op een min-max probleem waarbij een adversary de vertrouwensgewichten van zaad-pixels verstoort. Het algoritme slaagt erin segmentatie te herstellen die overeenkomt met de grondwaarheid, wat robuustheid tegen adversariële verstoringen demonstreert.
• Online Adversariële Segmentatie: Het algoritme wordt getest op een videostream waarbij vormen en clusters bewegen en roteren, waardoor de kostenfunctie bij elk frame verandert. De methode voert real-time segmentatie uit (ongeveer 80 fps op CPU) zonder voorafgaande training.
• Vergelijking met Deep Learning: In de online adversariële setting presteert de voorgestelde ZO-methode beter dan zowel supervised als semi-supervised getrainde U-Net-modellen wat betreft Intersection over Union (IoU), precisie en recall. Opmerkelijk is dat de ZO-methode geen voorafgaande training vereist, een aanzienlijk kleiner geheugengebruik heeft (~0,05 MB versus ~8 MB voor U-Net), en effectief werkt in onbekende omgevingen zonder toegang tot grote datasets.

Betekenis en Claims
De auteurs claimen dat dit het eerste onderzoek is dat is gewijd aan het oplossen van min-max optimalisatieproblemen met niet-gladde submodulair-concave kostenfuncties. De betekenis van het werk ligt in:

1. Overbruggen van een Kloof: Het adresseert een klasse van combinatorische min-max problemen die eerder moeilijk op te lossen waren vanwege het ontbreken van gladheid en de gemengde discrete-continue aard.
2. Zeroth-Order Efficiëntie: Het demonstreert dat zeroth-order methoden, traditioneel gebruikt voor continue niet-gladde problemen, effectief kunnen worden aangepast voor submodulaire optimalisatie via de Lovász-extensie.
3. Robuustheid en Efficiëntie: De numerieke resultaten suggereren dat deze aanpak een haalbaar alternatief biedt voor deep learning voor real-time, resource-beperkte en adversariële omgevingen, met name waar voorafgaande training onuitvoerbaar is of de omgeving niet-stationair is.

Het artikel concludeert met de opmerking dat toekomstig werk de relatie tussen deze oplossingen en gemengde-strategie Nash-evenwichten zou kunnen verkennen, de resultaten kan uitbreiden naar submodulair-submodulaire kostenfuncties, en onbegrensde constraint sets kan onderzoeken.