Riemannian Dueling Optimization

Dit artikel introduceert en analyseert twee nieuwe algoritmen, RDNGD en RDFW, voor duelerende optimalisatie op Riemanniaanse variëteiten, waarmee complexe problemen in gebieden zoals aanbevelingssystemen en robotica kunnen worden opgelost die met bestaande methoden niet hanteerbaar zijn.

De kern

Stel je voor dat je probeert de beste route te vinden in een groot, onbekend landschap, maar je hebt geen kaart, geen GPS en je kunt ook niet zien hoe hoog of laag je bent. Je kunt alleen twee punten naast elkaar vergelijken en iemand (of een computer) vraagt: "Is punt A mooier dan punt B?" of "Is punt A veiliger dan punt B?".

Dit is precies het probleem dat deze paper aanpakt, maar dan in de wereld van kunstmatige intelligentie en wiskunde. Hier is een uitleg in gewoon Nederlands, met een paar creatieve vergelijkingen.

1. Het Probleem: De Blinde Klimmer

Normaal gesproken gebruiken computers bij het leren van taken (zoals het herkennen van gezichten of het besturen van een robot) een "helling" of "gradiënt". Dat is alsof je een berg beklimt en je voelt met je voeten welke kant de grond het steilst naar beneden gaat. Je loopt dan gewoon die kant op.

Maar wat als je die helling niet kunt voelen? Wat als je alleen maar mag vragen: "Is deze stap beter dan die stap?"

• Voorbeeld: In een aanbevelingssysteem (zoals Netflix) weet je niet precies hoeveel een gebruiker van een film houdt (geen getal), maar je weet wel dat ze film A liever hebben dan film B.
• Voorbeeld: Bij robots weet een menselijke supervisor misschien niet precies hoeveel "punten" een beweging waard is, maar hij kan wel zeggen: "Deze beweging zag er natuurlijker uit dan die andere."

Deze paper noemt dit "Dueling Optimization" (Strijd-Optimalisatie). Je optimaliseert door te vechten: "Wie wint er, A of B?"

2. De Nieuwe Uitdaging: De Bolvormige Wereld

Tot nu toe hebben wetenschappers dit probleem opgelost op een platte vlakte (zoals een vel papier). Maar in de echte wereld is de "wereld" vaak niet plat.

• De Analogie: Stel je voor dat je een robot bestuurt die moet draaien. Of dat je een foto moet corrigeren die scheef staat. De mogelijke oplossingen liggen niet op een platte kaart, maar op een bol of een kring. In de wiskunde noemen we dit een "Riemanniaanse variëteit" (een gekromd oppervlak).

Als je op een bol loopt, zijn de regels anders dan op een platte weg. Als je rechtuit loopt, kom je op een bol uiteindelijk weer terug bij je startpunt! De oude methoden die werken op platte vlakken, werken hier niet meer. Ze raken de weg kwijt.

3. De Oplossing: Twee Nieuwe Methoden

De auteurs van deze paper hebben twee nieuwe methoden bedacht om op deze gekromde oppervlakken te navigeren, puur op basis van "wie wint er?"-vragen.

Methode A: De "Gokker" (RDNGD)

Stel je voor dat je op een heuvel staat en je wilt weten welke kant omlaag gaat, maar je mag niet kijken.

1. Je steekt een stok uit naar links en een stok naar rechts.
2. Je vraagt: "Is de grond links lager dan rechts?"
3. Als het antwoord "Ja" is, loop je een stap naar links. Zo niet, dan naar rechts.
4. Je herhaalt dit, maar je past je pas aan de vorm van de heuvel aan (de kromming).

Dit is hun RDNGD-methode. Het is slim omdat het niet alleen vraagt "welke kant?", maar ook rekening houdt met de vorm van de wereld (de bol). Ze bewijzen wiskundig dat deze methode snel genoeg is om een oplossing te vinden, zelfs als je geen getallen kunt zien.

Methode B: De "Zonder-Projectie" Methode (RDFW)

Soms is het heel moeilijk om te berekenen hoe je precies op de juiste plek moet landen als je een stap zet (dit heet "projecteren").

• Vergelijking: Stel je voor dat je in een zwembad zit en je wilt naar de rand zwemmen. Soms is het heel lastig om precies te berekenen waar je de rand raakt als je een bepaalde kant op zwemt.
• De RDFW-methode is een slimme truc. In plaats van te proberen precies op de rand te landen, vraagt de computer: "Welk punt in het hele zwembad ligt het dichtst bij de kant als ik in die richting zwem?"
• Dit is makkelijker te berekenen. De paper toont aan dat je ook zo kunt winnen, zelfs zonder die moeilijke berekeningen.

4. Waarom is dit belangrijk? (De Reële Wereld)

De auteurs laten zien dat dit niet alleen wiskundig leuk is, maar ook echt werkt:

1. Aanvallen op AI: Ze gebruiken het om "hackers" te helpen die een AI willen misleiden. Ze kunnen kleine, onzichtbare veranderingen aan een foto maken zodat de AI denkt dat een hond een auto is. Ze doen dit zonder de "score" van de AI te kennen, alleen door te vragen: "Is deze versie van de foto verwarrender dan die?"
2. Horizon Correctie: Stel je een foto van een landschap voor die scheef is. De computer moet de foto draaien tot de horizon recht is. In plaats van te meten hoeveel graden het scheef is, vraagt de computer: "Ziet deze versie er strakker uit dan die versie?" De computer draait de foto stap voor stap tot hij het beste resultaat vindt.

Samenvatting

Deze paper is als een nieuwe kompas voor blinde klimmers.

• Het oude kompas: Werkte alleen op platte vlakken en had een kaart nodig (getallen).
• Het nieuwe kompas: Werkt op bolvormige werelden (zoals robots en 3D-beelden) en heeft alleen een vriend nodig die kan zeggen: "Links is beter dan rechts."

Het is een grote stap voorwaarts voor kunstmatige intelligentie, omdat het machines in staat stelt om te leren in complexe, gekromde werelden, zelfs als ze geen duidelijke cijfers of scores krijgen, maar alleen maar feedback in de vorm van keuzes.

Technische samenvatting

Titel: Riemannian Dueling Optimization

Auteurs: Yuxuan Ren, Abhishek Roy, Shiqian Ma

---

1. Probleemstelling

Het artikel adresseert het probleem van dueling optimalisatie (optimalisatie via vergelijkingsfeedback) binnen de context van Riemanniaanse variëteiten (niet-Euclidische ruimtes).

• Dueling Feedback: In veel moderne toepassingen (zoals aanbevelingssystemen, robotica en representatieleren) zijn exacte functiewaarden of gradiënten van de doelfunctie $f(x)$ niet beschikbaar. De enige beschikbare feedback is een pairwise comparison oracle $Q_f(x, y)$, die aangeeft of $f(x) > f(y)$ of andersom.
• Riemanniaanse Context: Bestaande methoden voor dueling optimalisatie zijn voornamelijk beperkt tot de Euclidische ruimte. Echter, veel moderne problemen hebben een beslissingsruimte die van nature niet-Euclidisch is:
  • Hyperbolische ruimte: Voor hiërarchische embeddings in aanbevelingssystemen.
  • SO(3) (Speciale Orthogonale Groep): Voor trajectoptimalisatie in robotica.
  • Stiefel-variëteit: Voor projectiematrices in representatieleren.
  • Beperkte sets: Sferen en simplices.
• Doel: Het minimaliseren van een doelfunctie $f(x)$ over een Riemanniaanse variëteit $\mathcal{M}$, waarbij alleen toegang is tot de oracle $Q_f(x, y) = 2 \cdot \mathbb{1}(f(x) > f(y)) - 1$.

2. Methodologie

De auteurs ontwikkelen een theoretisch kader en drie specifieke algoritmen om dit probleem op te lossen, rekening houdend met de kromming van de variëteit en de afwezigheid van gradiëntinformatie.

A. Gradiëntrichtings-schatting

Om optimalisatie mogelijk te maken zonder gradiënten, introduceren de auteurs een Riemanniaanse gradiëntrichtings-schatting gebaseerd op twee punten-storing:
$$h_\nu(x) = Q_f(\text{Exp}_x(\nu u), \text{Exp}_x(-\nu u)) \cdot u$$
Waarbij:

• $\text{Exp}_x$ de exponentiële afbeelding is (verplaatst een vector langs een geodetische).
• $u$ een eenheidsvector is die uniform wordt gesampled uit de raakruimte $T_x\mathcal{M}$.
• $\nu$ de straal van de verstoring is.

De auteurs bewijzen dat deze schatter, in verwachting, uitgelijnd is met de genormaliseerde gradiënt $\frac{\text{grad}f(x)}{\|\text{grad}f(x)\|}$, zelfs in aanwezigheid van kromming. Ze verbeteren de ondergrens van de constante factor in deze schatting ten opzichte van eerdere Euclidische werken.

B. Algoritmen

1. RDNGD (Riemannian Dueling Normalized Gradient Descent):

   • Een projectie-gebaseerd algoritme voor zowel onbeperkte als beperkte convex problemen.
   • Update regel: $x_{k+1} = P_\mathcal{X}(\text{Exp}_{x_k}(-\eta_k h_\nu(x_k)))$.
   • Hierbij is $P_\mathcal{X}$ de projectie-operator op de toegestane set.
   • Het algoritme gebruikt een "best-so-far" strategie ($\hat{x}_k$) om de beste iteratie te retourneren.

2. RRDNGD (Riemannian Recurrent Dueling Normalized Gradient Descent):

   • Een variant voor sterk geodetisch convex problemen.
   • Werkt in fasen: in elke fase wordt RDNGD uitgevoerd om de sub-optimaliteit te halveren.
   • Dit leidt tot een lineaire convergentiesnelheid (logaritmische complexiteit in $\epsilon$).

3. RDFW (Riemannian Dueling Frank-Wolfe):

   • Ontworpen voor situaties waar projectie op de constraint set $X$ computatieel te duur is (bijv. bij complexe matrixvariëteiten).
   • Vervangt de projectie door een Linear Minimization Oracle (LMO): $\text{argmin}_{z \in X} \langle \bar{h}_k, \text{Log}_{x_k}(z) \rangle$.
   • Om de hoge variantie van de gradiënt-schatting te compenseren (wat kritiek is voor Frank-Wolfe), wordt een batch-schatting gebruikt met $M_k$ samples per iteratie.

3. Belangrijkste Bijdragen

• Eerste theoretisch kader: Dit is het eerste werk dat dueling optimalisatie uitbreidt naar Riemanniaanse variëteiten.
• Complexiteitsresultaten:
  • Voor geodetisch L-gladde (niet-convexe) functies: Iteratiecomplexiteit van $O(d/\epsilon^2)$.
  • Voor geodetisch convex functies: Iteratiecomplexiteit van $O(d/\epsilon)$.
  • Voor sterk geodetisch convex functies: Lineaire convergentie $O(d \log(1/\epsilon))$.
  • Voor projectie-vrije (Frank-Wolfe) setting: Oracle-complexiteit van $O(d/\epsilon^2)$.
• Verbeterde constanten: De analyse levert strakkere constanten op dan bestaande Euclidische methoden (zoals die van Saha et al., 2021), mede door het elimineren van logaritmische factoren in de bias-bounds.
• Geometrie-bewust: De methoden zijn adaptief aan de intrinsieke structuur van de variëteit (via krommingsgrenzen) in plaats van afhankelijk te zijn van de omgevingsdimensie.

4. Resultaten

De auteurs valideren hun methoden via numerieke experimenten op synthetische data en real-world toepassingen:

• Synthetische Problemen:

  • Rayleigh-kwotiënt maximalisatie: RDNGD presteert vergelijkbaar met Zeroth-Order Riemannian Gradient Descent (ZO-RGD), hoewel ZO-RGD functiewaarden nodig heeft en RDNGD alleen vergelijkingen.
  • Karcher-middelpunt: Oplossing van het gemiddelde van positief-definiete matrices. RDNGD convergeert naar een nauwkeurige oplossing.
  • Beperkt Karcher-middelpunt: RDFW slaagt erin om het probleem op te lossen met alleen vergelijkingen, zonder dure projecties.

• Real-World Toepassingen:

  • Aanval op Deep Neural Networks (DNN): In een black-box scenario (zonder toegang tot de loss-functie) wordt een adversarial attack uitgevoerd op een VGG-netwerk. RDNGD bereikt een hogere adversarial loss in minder iteraties en minder CPU-tijd dan ZO-RGD, ondanks het gebruik van strikt zwakkere informatie (alleen labels/vergelijkingen).
  • Horizon Leveling: Het corrigeren van de kanteling van een foto (optimalisatie op SO(2)). Het algoritme convergeert snel naar een correcte rotatie op basis van menselijke voorkeuren (welke versie staat "vlakker"?).

5. Betekenis en Conclusie

Dit werk vormt een brug tussen twee actieve onderzoeksgebieden: voorkeursgebaseerde optimalisatie (dueling feedback) en Riemanniaanse optimalisatie.

• Praktische impact: Het maakt het mogelijk om complexe machine learning taken op te lossen waar gradiënten ontoegankelijk zijn en de parameter ruimte niet-Euclidisch is (bijv. 3D-rotaties, hyperbolische embeddings).
• Theoretische doorbraak: Het overwint de intrinsieke geometrische barrières (zoals kromming en parallel transport) die standaard Euclidische dueling-methoden falen te behandelen.
• Toekomstige richtingen: Het opent de deur voor versnelde algoritmen, Hessiaan-bewuste methoden voor het vinden van lokale minima, en het onderzoeken van hoe ruis in de schatting kan helpen bij het ontsnappen aan zadelpunten.

Kortom, de paper biedt robuuste, theoretisch onderbouwde algoritmen die het optimaliseren van complexe systemen mogelijk maken wanneer alleen relatieve feedback beschikbaar is.