Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization

Dit artikel presenteert een convergentie- en complexiteitsanalyse voor een blok-majorisatie-minimalisatie-algoritme voor niet-convexe optimalisatie met Riemanniaanse beperkingen, waarbij wordt aangetoond dat het een $\epsilon$-stationair punt bereikt binnen $\widetilde{O}(\epsilon^{-2})$ iteraties en sneller convergeert dan standaard Euclidische methoden.

De kern

De Kunst van het Klimmen op een Berg met Blokken: Een Simpele Uitleg van het Onderzoek

Stel je voor dat je op zoek bent naar het laagste punt in een enorm, complex landschap. Dit landschap is niet vlak als een veld, maar vol met heuvels, dalen en kronkelende paden. In de wiskunde noemen we dit een Riemanniaanse variëteit (een gekromd oppervlak). Je doel is om de "hoogte" (de kosten of fouten) zo laag mogelijk te krijgen. Dit is een heel moeilijk probleem, vooral als het landschap vol zit met kuilen en gaten (niet-convex).

De auteurs van dit paper, Yuchen Li en zijn collega's, hebben een slimme manier bedacht om dit probleem op te lossen. Ze noemen hun methode Block Majorization-Minimization (BMM), of in het Nederlands: Blok-Maximalisatie-Minimalisatie.

Hier is hoe het werkt, vertaald naar alledaagse taal:

1. Het Probleem: De Grote Puzzel

Stel je voor dat je een enorme puzzel moet oplossen, maar je mag niet alle stukjes tegelijk verplaatsen. Je hebt een team van mensen (de "blokken"), en elk teamlid is verantwoordelijk voor een ander deel van de puzzel.

• De uitdaging: Als je alle stukjes tegelijk probeert te verplaatsen, wordt het te ingewikkeld.
• De oplossing: Je laat de mensen om de beurt werken. Terwijl Team A aan zijn stukje werkt, staan Team B, C en D stil. Zodra Team A klaar is, gaat Team B aan de slag, terwijl de anderen weer stil staan.

2. De Methode: De "Veilige Schatting" (Majorization)

Het echte genie van deze methode zit in hoe ze beslissen hoe ze een stukje verplaatsen. Ze gebruiken geen raden, maar een slimme truc: de veilige schatting.

Stel je voor dat je in een donkere kamer staat en je wilt naar de deur lopen, maar je ziet de vloer niet goed. Je maakt een schatting van de vloer: "Ik denk dat de vloer hier een beetje hellend is, maar ik ga er zeker van uit dat hij niet steiler is dan deze lijn die ik in de lucht teken."

• De "Majorizer": Dit is die lijn in de lucht. Het is een veilige, bovenste schatting van hoe de vloer eruitziet. Je weet zeker dat de echte vloer onder deze lijn ligt.
• De "Minimizing": In plaats van de echte, moeilijke vloer te beklimmen, beklim je die makkelijke lijn in de lucht. Omdat je weet dat de echte vloer eronder ligt, ben je gegarandeerd een stap dichter bij de deur (of in dit geval, het laagste punt).

3. Waarom is dit paper speciaal?

Vroeger hadden wiskundigen twee soorten problemen:

1. Vlakke landen (Euclidisch): Hier werken de oude methoden prima.
2. Gekromde landen (Riemanniaans): Denk aan een bol of een zadelvorm. Hier werken de oude methoden vaak niet goed of ze zijn te traag.

De auteurs van dit paper hebben bewezen dat hun methode (RBMM) werkt op beide soorten landen, zelfs als er extra regels zijn (bijvoorbeeld: "je mag alleen op de rand van de bol lopen, niet eronder").

De drie grote doorbraken:

• Het werkt overal: Of je nu op een vlakke vloer loopt of op een bol, de methode vindt altijd een goed punt.
• Het is snel: Ze hebben bewezen dat de methode niet oneindig lang doet. Als je wilt dat je fout kleiner is dan een bepaalde maat (bijvoorbeeld 0,01), weten ze precies hoeveel stappen je maximaal nodig hebt. Het is alsof ze een stopwatch hebben die zegt: "Je bent gegarandeerd binnen 1000 stappen dicht bij het doel."
• Het is robuust: Soms is het moeilijk om de perfecte stap te zetten (bijvoorbeeld door rekenfouten of ruis). Deze methode geeft niet op als de stap niet perfect is; hij komt er toch wel.

4. Waar is dit goed voor? (Voorbeelden uit de echte wereld)

De auteurs laten zien dat hun methode werkt voor hele coole problemen:

• Robuuste PCA: Stel je hebt een foto die grotendeels is vernietigd door vlekken (ruis). Je wilt de oorspronkelijke foto terugvinden. Deze methode helpt om de "echte" vorm te vinden, zelfs als er veel rommel in zit.
• Subspace Tracking: Denk aan een camera die een bewegend object volgt. Het object beweegt over een gekromd pad. De methode helpt om de camera zo te richten dat hij het object perfect blijft volgen, zelfs als het pad vreemd is.
• Woordenboeken maken: Het helpt computers om patronen in data te vinden, alsof je een woordenboek maakt van de "basisbouwstenen" van een taal, maar dan voor complexe data.

Samenvatting in één zin

De auteurs hebben een slimme, stap-voor-stap strategie bedacht om complexe, gekromde problemen op te lossen, waarbij ze telkens een veilige, makkelijke schatting gebruiken om een stap te zetten, en ze hebben bewezen dat deze strategie snel en betrouwbaar werkt, zelfs als je niet perfect kunt rekenen.

Het is alsof ze een GPS hebben ontworpen die je niet alleen door een vlak stadje leidt, maar ook door een bergachtig landschap, en die je altijd verzekert dat je binnen een bepaalde tijd bij je bestemming bent, ongeacht hoe slecht de wegen zijn.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Convergence and Complexity of Block Majorization-Minimization for Constrained Block-Riemannian Optimization" in het Nederlands.

Titel: Convergentie en Complexiteit van Block Majorization-Minimizing voor Beperkte Block-Riemanniaanse Optimalisatie

Auteurs: Yuchen Li, Laura Balzano, Deanna Needell, en Hanbaek Lyu.

---

1. Het Probleem

Het paper richt zich op het minimaliseren van een gladde, niet-convexe doelfunctie $f$ over een productruimte van parameters $\Theta = \Theta^{(1)} \times \dots \times \Theta^{(m)}$.

• Beperkingen: Elke parameterblok $\theta^{(i)}$ is beperkt tot een gesloten deelverzameling $\Theta^{(i)}$ van een Riemanniaanse variëteit $M^{(i)}$. Dit omvat zowel ingebouwde subvariëteiten (zoals Stiefel-variëteiten of laag-rang matrices) als volledige variëteiten (zoals Hadamard-variëteiten).
• Uitdaging: Traditionele optimalisatiemethoden op Riemanniaanse variëteiten zijn vaak complex, vooral bij niet-convexe problemen met meerdere blokken. Bestaande methoden voor block-coördinaat descent (BCD) of majorization-minimization (MM) op variëteiten missen vaak garanties voor convergentie naar stationaire punten voor $m \geq 3$ blokken, of bieden geen iteratie-complexiteitsgrenzen (d.w.z. hoeveel iteraties nodig zijn om een $\epsilon$-benadering te bereiken).
• Doel: Het ontwikkelen van een algoritme dat gegarandeerd convergeert naar stationaire punten en een scherpe iteratie-complexiteit biedt, zelfs bij onnauwkeurige sub-probleemoplossingen.

2. Methodologie: RBMM

De auteurs introduceren Riemannian Block Majorization-Minimization (RBMM), een iteratief algoritme dat de MM-strategie toepast op block-variabele optimalisatie op Riemanniaanse variëteiten.

Het Algoritme (RBMM):
In elke iteratie $n$ worden de blokken $\theta^{(i)}$ cyclisch bijgewerkt ($i=1$ tot $m$):

1. Majorisatie: Voor het huidige blok $i$, wordt een majoriserende surrogaatfunctie $g_n^{(i)}$ geconstrueerd die de doelfunctie $f_n^{(i)}$ (de functie waarbij andere blokken vaststaan) bovenwaardeert en gelijk is aan de doelfunctie in het huidige punt.
2. Minimalisatie: Het nieuwe blok $\theta_n^{(i)}$ wordt gevonden door $g_n^{(i)}$ te minimaliseren over de beperking $\Theta^{(i)}$.
   $$\theta_n^{(i)} \in \arg\min_{\theta \in \Theta^{(i)}} g_n^{(i)}(\theta)$$

Belangrijke Kenmerken van de Analyse:

• Surrogaatsoorten: De analyse dekt drie soorten surrogaatfuncties:
  1. Geodesisch glad (g-smooth): Surrogaten die zelf glad zijn op de variëteit.
  2. Riemanniaanse proximaal: $g(\theta) = f(\theta) + \frac{\lambda}{2} d^2(\theta, \theta_{old})$, waarbij $d$ de geodesische afstand is.
  3. Euclidisch proximaal: $g(\theta) = f(\theta) + \frac{\lambda}{2} \|\theta - \theta_{old}\|^2$, waarbij de afstand in de omringende Euclidische ruimte wordt gemeten (handig voor ingebouwde variëteiten zoals Stiefel).
• Onnauwkeurige Berekening: Het algoritme staat toe dat de sub-problemen (minimalisatie van de surrogaat) niet exact worden opgelost, zolang de optimaliteitsgaten ($\Delta_n$) sommeerbaar zijn. Dit maakt het robuust voor praktische implementaties.
• Geometrie: De analyse maakt expliciet gebruik van Riemanniaanse concepten zoals parallel transport, retractions (in plaats van de computationally zware exponentiële afbeelding), en injectiviteitsstralen.

3. Belangrijkste Bijdragen

1. Convergentie naar Stationaire Punten: Het paper bewijst dat RBMM asymptotisch convergeert naar de set van stationaire punten voor een breed scala aan niet-convexe problemen, zelfs bij $m \geq 3$ blokken. Dit lost een bekend probleem op waarbij standaard block-coördinaat methoden kunnen divergeren of in cycli kunnen komen zonder stationair punt te bereiken.
2. Iteratie-Complexiteit: Voor het eerst worden scherpe complexiteitsgrenzen afgeleid voor block-Riemanniaanse optimalisatie.
   • Voor Riemanniaanse/Euclidische proximaal surrogaten en g-smooth surrogaten met een kwadratische majorisatie-gap, wordt een complexiteit van $\tilde{O}(\epsilon^{-2})$ bewezen om een $\epsilon$-stationair punt te bereiken.
   • Dit betekent dat het aantal iteraties polynomiaal schaalt met $1/\epsilon$, wat vergelijkbaar is met de beste resultaten in de Euclidische setting.
3. Robuustheid: De theorie is robuust tegen onnauwkeurige oplossingen van sub-problemen, wat essentieel is voor complexe Riemanniaanse optimalisatie waar exacte minimalisatie vaak onmogelijk is.
4. Unificatie: Het framework verenigt bestaande algoritmen (zoals Riemanniaanse MM, block-projected gradient descent, en specifieke methoden voor Stiefel-variëteiten) onder één theoretische paraplu en levert nieuwe complexiteitsresultaten voor deze methoden.

4. Kernresultaten

• Stelling 3.2 & 3.3 (Asymptotische Convergentie): Onder redelijke aannames (zoals begrensdheid van sub-niveau sets en sommeerbaarheid van optimaliteitsgaten) convergeert elke limietpunt van de iteraties naar een stationair punt van de doelfunctie.
• Stelling 3.5 & 3.7 (Complexiteit):
  • Voor proximaal surrogaten (zowel Riemanniaans als Euclidisch) op compacte verzamelingen of Stiefel-variëteiten, is de iteratie-complexiteit $\tilde{O}(\epsilon^{-2})$.
  • Specifiek voor Stiefel-variëteiten (orthogonale frames): Als de doelfunctie en surrogaten Euclidisch $L$-glad zijn, zijn ze ook g-smooth op de variëteit. Hierdoor geldt de $\tilde{O}(\epsilon^{-2})$ complexiteit zelfs als men Euclidische proximaal termen gebruikt, wat computatieel efficiënter is dan het berekenen van geodesische afstanden.
• Vergelijking met Bestaande Werk: In tegenstelling tot eerdere werken die alleen asymptotische convergentie garandeerden of alleen voor convexe problemen gold, biedt dit paper de eerste $\tilde{O}(\epsilon^{-2})$ grenzen voor niet-convexe, block-Riemanniaanse optimalisatie met onnauwkeurige sub-stappen.

5. Toepassingen en Experimenten

De auteurs valideren hun theorie op diverse gestileerde toepassingen:

• Geodesisch Beperkte Subruimte Tracking: Een probleem waarbij subruimtes langs een geodesische kromme worden geschat. Het paper toont aan dat een geproximaliseerde versie van bestaande methoden convergeert met $\tilde{O}(\epsilon^{-2})$.
• Optimistische Likelihood (Fisher-Rao afstand): Toepassing op Hadamard-variëteiten (positief definiete matrices).
• Riemanniaanse CP-Dictionary Learning: Decompositie van tensors met beperkingen op de factor matrices (Stiefel of laag-rang). Experimenten tonen aan dat RBMM sneller convergeert dan standaard Alternating Least Squares (ALS), vooral in de Euclidische en Stiefel-settings.
• Robust PCA: Een alternatieve formulering met een harde laag-rang beperking.

Experimentele Bevindingen:
In numerieke experimenten (o.a. synthetische data voor subspace tracking en dictionary learning) convergeert RBMM sneller dan standaard Euclidische algoritmen toegepast op Riemanniaanse settings. De toevoeging van een proximaal regularisatieterm versnelt de convergentie niet altijd drastisch bij Stiefel-variëteiten (vanwege de orthogonale eigenschap die de kwadratische term lineair maakt), maar het zorgt wel voor de theoretische convergentiegaranties.

6. Betekenis en Impact

Dit paper is een belangrijke stap in de theorie van Riemanniaanse optimalisatie omdat het:

1. De kloof overbrugt tussen de succesvolle MM-methoden in de Euclidische ruimte en de complexe wereld van Riemanniaanse variëteiten.
2. Wiskundige garanties biedt voor een breed scala aan moderne machine learning problemen (zoals laag-rang matrix factorisatie, dictionary learning en subspace tracking) die vaak op niet-convexe, gebogen domeinen plaatsvinden.
3. Laat zien dat Euclidische benaderingen (zoals het gebruik van Euclidische afstanden in proximaal termen) vaak voldoende zijn om de complexe Riemanniaanse geometrie te benutten, mits de juiste aannames (zoals compactheid en g-convexiteit) worden voldaan. Dit maakt de algoritmen praktischer en sneller te implementeren.

Kortom, het paper levert een robuust theoretisch fundament voor het ontwerpen en analyseren van iteratieve optimalisatie-algoritmen op Riemanniaanse variëteiten, met specifieke focus op de efficiëntie en convergentie van block-wise methoden.