Deterministic Zeroth-Order Mirror Descent via Vector Fields with A Posteriori Certification

Technische Samenvatting: Deterministische Zeroth-Order Mirror Descent via Vectorenvelden met A Posteriori Certificering

1. Probleemstelling
Het artikel behandelt de uitdaging van deterministische, zeroth-order (afgeleide-vrije) optimalisatie in matige dimensies, specifiek voor doelstellingen waarbij gradiënten niet beschikbaar, evenredig duur of numeriek instabiel zijn om te berekenen (bijv. matrixfuncties met log-determinanten of kwantumrelatieve entropie). Standaard Mirror Descent (MD) biedt weliswaar geometrie-bewuste optimalisatie via Bregman-divergenties, maar vertrouwt traditioneel op exacte gradiënten. Bestaande deterministische zeroth-order optimalisatiemethoden (bijv. direct search, trust-region modellen) opereren doorgaans in de Euclidische meetkunde en richten zich op stationariteitsmaten in plaats van last-iterate functiewaarde-garanties. Omgekeerd bieden gerandomiseerde zeroth-order methoden bounds op basis van verwachtingswaarden, maar missen zij de reproduceerbaarheid en run-wise certificering die vereist is voor veiligheidskritische of controleerbare toepassingen. De kern van het probleem is het ontwikkelen van een deterministisch zeroth-order framework dat de Bregman-meetkunde behoudt, uitsluitend functiewaarden gebruikt en expliciete, verifieerbare last-iterate convergentiegaranties biedt.

2. Methodologie
De auteurs stellen een gegeneraliseerd $\Omega$-gedreven Mirror Descent framework voor. In plaats van de gradiënt $\nabla f(x)$ te gebruiken, hanteert het algoritme een algemeen vectorveld $\Omega(x)$ dat deterministisch wordt geconstrueerd uit functiewaarden.

• Gegeneraliseerde Update Regel: De update brengt de primaire iteratie $x_j$ naar de duale ruimte via $\theta_j = \nabla \Phi(x_j)$, voert een stap uit $\theta_{j+1} = \theta_j - \eta_j \Omega(x_j)$, en brengt terug naar de primaire ruimte $x_{j+1} = (\nabla \Phi)^{-1}(\theta_{j+1})$.
• A Posteriori Certificering: De analyse steunt op een traject-gewijze relatieve gladheidsvoorwaarde (Vergelijking 2.5): $\eta_j D_{f,\Omega}(x_{j+1} \| x_j) \leq D_\Phi(x_{j+1} \| x_j)$. In tegenstelling tot globale aannames, wordt deze conditie gecontroleerd langs de gerealiseerde iteraties. Indien voldaan, levert dit expliciete last-iterate garanties op.
• Punctured-Neighborhood Generalized Star-Convexity: Om de fout die inherent is aan zeroth-order oracles te hanteren, introduceren het artikel een versoepelde star-convexiteit conditie. Het vereist dat $\langle \Omega(x), x - x^* \rangle \geq f(x) - f(x^*)$ alleen geldt buiten een kleine buurt $U$ van de minimizer $x^*$. Dit isoleert een expliciete "error floor" die bepaald wordt door de resolutie van de zeroth-order oracle.
• Deterministische Instantiatie: Het framework wordt geïnstantieerd met behulp van deterministische centrale eindige differenties in matige dimensies. Het vectorveld $\Omega(x)$ wordt geconstrueerd met behulp van $2d$ off-center functiewaarde-evaluaties (plus één herbruikbare centrumwaarde).
• Robuuste Conische Dominantie: Een belangrijke technische bijdrage is het bewijs dat het eindige-differentie vectorveld voldoet aan de vereiste star-convexiteit conditie buiten een specifieke set $V_{\epsilon, c}$. Dit wordt bereikt door het probleem te formuleren als een robuust conische dominantie ontwerp-probleem, waarbij wordt gewaarborgd dat één geschaalde proxy-richting alle toegestane ware richtingen domineert over een circulaire kegel van onzekerheid.

3. Belangrijkste Bijdragen

• Verenigd Framework: Het artikel vestigt een algemeen sjabloon voor $\Omega$-gedreven mirror descent dat diverse informatie-geometrische algoritmen (inclusief gegeneraliseerde Blahut–Arimoto updates) en deterministische eindige-differentie schema's omvat.
• Traject-gewijze Certificering: Het biedt een mechanisme voor run-wise, verifieerbare certificaten. Als de relatieve gladheidsvoorwaarde standhoudt langs een specifieke traject, garandeert het algoritme een specifieke last-iterate functiewaarde bound, onafhankelijk van globale gladheidsaannames.
• Expliciete Error Floor Analyse: Voor deterministische eindige differenties leiden de auteurs een "rate-plus-floor" convergentiebound af: de fout neemt af als $O(1/t)$ buiten een resolutie-afhankelijke buurt, waarbij de error floor expliciet wordt gekarakteriseerd door de eindige-differentie stapgrootte $\epsilon$ en de conditiegetal van het probleem.
• Geometrische Connectie: Het werk onthult een verborgen geometrische structuur die Bregman telescopische identiteiten, deterministische certificering en robuuste conische geometrie (specifiek tweede-orde kegel dualiteit) koppelt in de context van zeroth-order optimalisatie.

4. Hoofdresultaten

• Theorem 2.1 & 2.3: Onder de traject-gewijze relatieve gladheidsvoorwaarde en punctured-neighborhood generalized star-convexity garandeert het algoritme:
  $$f(x_t) - f(x^*) \leq \max \left( \frac{D_\Phi(x^* \| x_1)}{\sum_{j=1}^{t-1} \eta_j}, \max_{x \in U} (f(x) - f(x^*)) \right)$$
  Deze bound scheidt de convergentiesnelheid (gedreven door de Bregman divergentie en stapgroottes) van de benaderingsfout (gedreven door de buurt $U$).
• Theorem 6.4 & Corollary 6.6: Wanneer geïnstantieerd met deterministische centrale eindige differenties, wordt aangetoond dat de uitzonderlijke verzameling $V_{\epsilon, c}$ geconteneerd is binnen een Euclidische bal met een straal proportioneel aan $\epsilon\sqrt{d}$. Dit levert een concrete bound op waarbij de error floor wordt bepaald door de variatie van de doelstelling binnen deze $\epsilon$-buurt.
• Haalbaarheid (Theorem 5.1): Het artikel bewijst dat voor voldoende kleine stapgroottes de traject-gewijze relatieve gladheidsvoorwaarde altijd haalbaar is, wat het gebruik van een certificate-driven line search rechtvaardigt.

5. Betekenis en Claims
Het artikel claimt een brug te slaan tussen deterministische zeroth-order optimalisatie en geometrie-bewuste mirror descent. De primaire betekenis ligt in:

1. Determinisme en Verifieerbaarheid: Het bieden van een framework geschikt voor toepassingen die reproduceerbaarheid en controleerbaarheid vereisen (bijv. wetenschappelijke computing, veiligheidskritisch ontwerp), waar stochastische methoden ontoereikend zijn.
2. Geometrische Flexibiliteit: Het uitbreiden van de voordelen van Bregman-meetkunde (cruciaal voor problemen met simplex-, entropie- of positief-definiete restricties) naar settings waar gradiënten niet beschikbaar zijn.
3. Theoretisch Inzicht: Het aantonen dat voor zeroth-order mirror descent, de kritieke structurele aanname niet klassieke convexiteit per se is, maar een punctured-neighborhood generalized star-convexity conditie. Deze conditie accommodeert op natuurlijke wijze de resolutielimieten van eindige-differentie benaderingen.
4. Methodologische Verschuiving: Het verleggen van de focus van globale aannames naar a posteriori, traject-gewijze certificaten, waardoor praktijkgebruikers convergentiegaranties kunnen verifiëren op basis van de werkelijke run-data in plaats van worst-case theoretische bounds.

De auteurs positioneren dit werk als een complement aan bestaande DFO-tradities, waarbij een specifiek interface wordt geboden waar de Bregman-meetkunde behouden blijft, en waarbij zij de eerste traject-gewijze, verifieerbare mirror-descent-stijl certificering voor last-iterate functiewaarden onder functiewaarde-only oracles presenteren.