Entropy-Smooth Convex Optimization Cannot Be Accelerated

Technische Samenvatting: Entropie-gladde Convex Optimalisatie Kan Niet Versneld Worden

Probleemstelling
Dit artikel onderzoekt de convergentiesnelheden van eerste-orde optimalisatiemethoden voor het minimaliseren van convexe functies die $L$-glad zijn ten opzichte van de negatieve Shannon-entropie op de standaard $d$-simplex, $\Delta_d$. Specifiek beschouwt de auteur de klasse van functies $\text{Ent}_d(L)$, gedefinieerd door de conditie dat de Bregman-divergentie van de objectfunctie $f$ ten opzichte van de negatieve entropie $h(x) = \sum x_k \log x_k$ begrensd wordt door $L$ maal de Bregman-divergentie van $h$ zelf.

Terwijl standaard mirror descent een convergentierate van $O(L \log d / T)$ bereikt voor deze klasse, rijst de natuurlijke vraag of "versnelde" methoden (analoog aan Nesterovs acceleratie in Euclidische settings) een $O(1/T^2)$ rate kunnen bereiken. Voorgaand werk door Dragomir et al. (2022) suggereerde dat acceleratie mogelijk onmogelijk is onder relatieve gladheid, maar hun tegenvoorbeelden vertrouwden op pathologische prox-functies die adversarieel samen met de harde instanties werden geconstrueerd. De centrale vraag die hier wordt behandeld, is of acceleratie onmogelijk is voor de specifieke, zeer gestructureerde prox-functie van negatieve entropie, die breed in de praktijk wordt gebruikt.

Methodologie
De auteurs maken gebruik van een black-box complexiteitsframework en construeren een "resisterende oracle" om een ondergrens te bewijzen voor de convergentierate van elke deterministische eerste-orde methode. De kern van hun methodologie omvat:

1. Constructie van Harde Instanties: Ze construeren een sequentie van "backbone" functies, gedefinieerd als de maximumwaarde van verschoven coördinaat-atomen ($g(u) = \max_k \{-u_{j_k} - b_k\}$).
2. Smoothing via de Rechter Bregman-Moreau Envelope: Om ervoor te zorgen dat de harde instanties tot de klasse $\text{Ent}_d(L)$ behoren (wat relatieve gladheid vereist maar niet-differentieerbaarheid op de rand toestaat), passen de auteurs de rechter Bregman-Moreau envelope toe op deze niet-gladde backbones. Dit smoothing-mechanisme steunt cruciaal op de gezamenlijke convexiteit van de Kullback-Leibler (KL) divergentie, een eigenschap die uniek is voor de Euclidische en KL-gevallen onder de Bregman-divergenties.
3. Adaptieve Query-Respons: De resisterende oracle interageert met een willekeurig algoritme door bij elke stap een nieuwe coördinaat-atoom te selecteren die overeenkomt met de coördinaat met de kleinste massa in het huidige query-punt van het algoritme. De offsets van deze atomen worden geïncrementeerd om ervoor te zorgen dat nieuwe atomen "lokaal onzichtbaar" (strikt gedomineerd) blijven nabij de proximale punten van vorige queries.
4. Transcript Consistentie: Gebruikmakend van de lokaliteitseigenschappen van de Bregman-Moreau envelope (Lemma 4), bewijzen de auteurs dat de gesmoothe functie die in de laatste stap is geconstrueerd consistent is met alle voorgaande oracle-responsen, waardoor de ondergrens geldt voor de gehele interactie.

Belangrijkste Resultaten
Het artikel stelt de volgende hoofdtheorema's vast:

• Ondergrens voor Simplex-optimalisatie (Theorem 1 & 5): Voor elke deterministische eerste-orde methode die $T$ queries uitvoert, bestaat er een functie $f \in \text{Ent}_d(L)$ waarvoor de suboptimaliteitskloof voldoet aan:
  $$f(x_{T+1}) - \min_{x \in \Delta_d} f(x) > \frac{L}{4(T+1)}$$
  mits de dimensie $d = \Omega(T^2)$. Dit resultaat demonstreert dat een versnelde $O(1/T^2)$ convergentie onbereikbaar is voor deze klasse. Bijgevolg is de standaard mirror descent rate van $O(L \log d / T)$ optimaal tot een logaritmische factor wanneer de dimensie voldoende groot is.
• Quantum Extensie (Theorem 11): Het resultaat breidt zich uit naar de niet-commutatieve setting van de spectrahedron (dichtheidsmatrices). Voor functies die $L$-glad zijn ten opzichte van de negatieve von Neumann-entropie, geldt dezelfde $\Omega(L/T)$ ondergrens. Dit wordt bewezen door de diagonale harde instanties in de matrixruimte in te bedden en de Lindblad data-verwerkingsongelijkheid te gebruiken.
• Interpolatiecondities (Sectie 5): De auteurs leiden expliciete pointwise minimale interpolanten af voor de klasse $\text{Ent}_d(L)$, waarmee de resultaten van Dragomirs PhD-thesis worden gegeneraliseerd. Deze condities zijn noodzakelijk voor het bestaan van een functie in de klasse die past bij gegeven eerste-orde data.

Betekenis en Claims
Het artikel claimt de openstaande vraag op te lossen of acceleratie mogelijk is voor entropie-gladde optimalisatie. De auteurs stellen dat hun resultaat significant is omdat:

• Het acceleratie uitsluit voor een specifieke, gunstige prox-functie (negatieve entropie) in plaats van een pathologische. Dit staat in contrast met eerdere negatieve resultaten waarbij de potentiaalfunctie specifiek werd geconstrueerd om acceleratie te dwarsbomen.
• Het de optimaliteit van Mirror Descent bevestigt voor deze klasse, wat suggereert dat de logaritmische kloof tussen de bovengrens ($O(L \log d / T)$) en de ondergrens ($O(L/T)$) waarschijnlijk te wijten is aan de dimensionaliteit van het probleem in plaats van een fout in het algoritme.
• Het de beperkingen van Performance Estimation Programs (PEP) in niet-Euclidische geometrieën benadrukt, waarbij opgemerkt wordt dat hoewel PEPs pathologische tegenvoorbeelden kunnen construeren, ze moeite hebben met gestructureerde settings zoals de simplex met entropie.

De auteurs merken bescheiden op dat een logaritmische kloof ($\log d$) rest tussen hun ondergrens en de bekende bovengrens. Ze suggereren dat de afgeleide interpolatiecondities in Sectie 5, gecombineerd met recente primal-dual frameworks, kunnen worden ingezet om deze ontbrekende factor te herstellen, maar zij beweren niet deze kloof in het huidige werk te hebben gedicht. Verder merken zij op dat voor extreem hoge dimensies ($d = \exp(T)$), acceleratie formeel niet is uitgesloten, hoewel dergelijke regimes van beperkte praktische interesse zijn.