Technische Samenvatting: Het herzien van de Zeroth-Order Hessian benadering: Een Single-Step Policy Optimization perspectief

1. Probleemstelling

Zeroth-order (ZO) optimalisatie adresseert scenario's waarbij de doelfunctie $F(\theta) = \mathbb{E}_\xi[f(\theta; \xi)]$ een black box is die alleen toegankelijk is via ruisgevoelige functie-evaluaties. Hoewel ZO gradiëntschatting goed gevestigd is, blijft een nauwkeurige ZO Hessian benadering een significante uitdaging, met name in hoogdimensionale en ruisgevoelige regimes.

Nauwkeurige krommingsinformatie is cruciaal voor:

• Derivative-free bilevel optimalisatie.
• Onzekerheidskwantificatie.
• Krommingsbewuste fine-tuning van Large Language Models (LLMs).

Bestaande methoden kampen met twee primaire beperkingen:

1. Hoge Variantie: Klassieke gerandomiseerde schatters (bijv. Stein-type schatters) lijden vaak aan een hoge variantie in hoogdimensionale settings, wat leidt tot instabiele optimalisatie.
2. Beperkte Omvang: Voorgaand onderzoek heeft zich primair gericht op het schatten van de Hessian matrix $\nabla^2 F(\theta)$ zelf. Er is beperkte aandacht besteed aan de geregulariseerde inverse Hessian $(\nabla^2 F(\theta) + \lambda I_d)^{-1}$ en de inverse Hessian-gradiënt product $(\nabla^2 F(\theta) + \lambda I_d)^{-1}\nabla F(\theta)$, die essentieel zijn voor second-order ZO updates.
3. Query Efficiëntie: Naïeve finite-difference methoden vereisen $O(d^2)$ queries, terwijl bestaande gerandomiseerde methoden vaak falen in het balanceren van variantiereductie met query-hergebruik.

2. Methodologie

2.1. Theoretisch Kader: Policy Optimization Perspectief

De auteurs stellen een verenigd kader voor dat de ZO Hessian benadering herinterpreteert door de lens van Single-Step Policy Optimization (PO).

• Gesmoothde Doelfunctie: De ZO doelfunctie wordt geherformuleerd als een gesmoothde doelfunctie $F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)}[\mathbb{E}_\xi[f(x; \xi)]]$, waarbij $\pi_\theta$ een geparametriseerde sampling policy is (bijv. Gaussische $N(\theta, \mu^2 I_d)$).
• Hessian Identiteit: Door de policy gradiënt te differentiëren, leiden de auteurs een algemene Hessian identiteit af voor de gesmoothde doelfunctie:
  $$\nabla^2 F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)} \left[ H_{\pi_\theta} \cdot \mathbb{E}_\xi[f(x; \xi)] \right]$$
  waarbij $H_{\pi_\theta}$ de Hessian van de policy log-densiteit is.
• Unificatie van Schatters: Dit perspectief onthult dat klassieke Stein-type schatters (One-point, Two-point, Three-point) en Central-Difference schatters speciale gevallen zijn van dit kader, onderscheiden door louter hun keuze van baseline (bijv. zero baseline, anchor baseline $f(\theta)$, of antithetic sampling).

2.2. ZoVH: Variantie-gereduceerde Hessian Schatter

Bouwend op het PO framework, introduceren de auteurs ZoVH (Zeroth-Order Variance-reduced Hessian), die gebruikmaakt van twee belangrijke technieken:

1. Optimale Gemiddelde Baseline:

   • In tegenstelling tot gradiëntschatters waar baselines vaak heuristisch zijn, bewijzen de auteurs dat voor de Hessian schatter afgeleid van de rank-one identiteit, de gemiddelde baseline $\hat{b} = \frac{1}{K}\sum f(x_k)$ de unieke keuze is die onbevooroordeeldheid (unbiasedness) behoudt.
   • Theoretisch is bewezen dat deze baseline de variantie van de schatter minimaliseert onder alle constante baselines.

2. Query Hergebruik Strategie:

   • Om de variantie verder te reduceren zonder de query-kosten te verhogen, maakt ZoVH gebruik van een geschiedenisbuffer van eerdere functie-queries.
   • Dit wordt geïnterpreteerd als off-policy leren binnen het PO framework, waarbij historische data (gegenereerd uit vorige iteraties) wordt hergewogen via importance sampling om de huidige Hessian te schatten.
   • Dit verhoogt effectief de steekproefomvang van $K$ naar $NK$ (waarbij $N$ de geschiedenislengte is) zonder extra functie-evaluaties.

2.3. Efficiënte Inverse Benaderingen

Om praktische second-order updates mogelijk te maken, breidt het paper ZoVH uit naar het benaderen van de inverse Hessian en de inverse Hessian-gradiënt product:

• Inverse Hessian: Maakt gebruik van de Woodbury matrix identiteit om de inverse van de geregulariseerde rank-$K$ Hessian schatter efficiënt te berekenen ($O(K^2 d)$ of $O(Kd)$ met een diagonale benadering) zonder een dichte $d \times d$ matrix te inverteren.
• Bias-Corrected Product: Wanneer dezelfde willekeurige richtingen worden gebruikt voor zowel de gradiënt als de Hessian schatting, wordt er een correlatie-bias geïntroduceerd. De auteurs stellen een leave-one-out strategie voor om deze bias te corrigeren, wat efficiënte berekening van $(\nabla^2 F + \lambda I)^{-1}\nabla F$ mogelijk maakt met minimale overhead.

3. Belangrijkste Bijdragen

1. Verenigd PO Perspectief: Heeft een theoretische equivalentie vastgesteld tussen algemene ZO Hessian schatters en de Hessian van een gesmoothde PO doelfunctie, waardoor klassieke gerandomiseerde schatters als specifieke instanties van baseline selectie worden verenigd.
2. ZoVH Algoritme: Ontwikkelde een uitgebreide suite van variantie-gereduceerde schatters voor de volledige Hessian, de geregulariseerde inverse, en het bias-gecorrigeerde inverse Hessian-gradiënt product.
3. Theoretische Garanties:
   • Bewijs van de onbevooroordeeldheid (unbiasedness) van de Hessian schatter met de gemiddelde baseline.
   • Demonstratie van de variantie-optimaliteit van de gemiddelde baseline.
   • Het leveren van foutbounds voor de gehele ZoVH suite (bias-variance decompositie).
   • Vaststellen van convergentie garanties voor het resulterende krommingsbewuste ZO algoritme naar een $\epsilon$-stationair punt.
4. Praktische Efficiëntie: Introduceerde een query hergebruik mechanisme dat de steekproefefficiëntie verhoogt zonder het query budget op te blazen, en leidde stabiele inverse benaderingen af die geschikt zijn voor hoogdimensionale problemen zoals LLM fine-tuning.

4. Experimentele Resultaten

De auteurs valideerden ZoVH via synthetische benchmarks, neurale netwerk training en black-box adversariële aanvallen.

• Hessian Schattingsnauwkeurigheid:

  • Op synthetische functies (Quadratic, Rosenbrock, Styblinski-Tang) en CNN lagen, behaalde ZoVH (met query hergebruik, $N=4$) consequent de laagste Frobenius norm fout vergeleken met klassieke Stein en Central-Difference schatters.
  • ZoVH ($N=1$) vertoonde een 8x verbetering in nauwkeurigheid ten opzichte van de Central-Difference schatter op Quadratic en Rosenbrock functies.
  • Op CNN lagen behaalde ZoVH ($N=4$) een 9x reductie in fout vergeleken met de Central-Difference schatter.

• Optimalisatie Convergentie:

  • In synthetische optimalisatietaken presteerde ZoVH ($N=4$) aanzienlijk beter dan Vanilla ZOO, HiZOO, en ZoAR in zowel convergentiesnelheid als uiteindelijke nauwkeurigheid, waarbij een gemiddelde 22x versnelling werd behaald ten opzichte van Vanilla ZOO.
  • In Black-Box Adversarial Attacks had ZoVH ($N=4$) 4x minder iteraties nodig om een succesvolle aanval te bereiken vergeleken met Vanilla ZOO.

• LLM Fine-Tuning:

  • Toegepast op het fine-tunen van OPT-1.3B en OPT-13B modellen op GLUE/SuperGLUE taken.
  • ZoVH demonstreerde snellere convergentie en hogere testnauwkeurigheid vergeleken met MeZO en HiZOO.
  • De runtime en geheugenoverhead waren minimaal, waarbij ZoVH slechts iets trager was dan MeZO en verwaarloosbare extra geheugen gebruikte (het opslaan van enkel scalaire waarden en seeds).

5. Betekenis en Claims

Het paper claimt dat ZoVH een robuust fundament biedt voor krommingsbewuste derivative-free optimalisatie. Door de kloof te overbruggen tussen ZO benadering en Policy Optimization, biedt het werk:

• Theoretische Helderheid: Een rigoureuze afleiding die verklaart waarom bepaalde schatters werken en hoe ze te optimaliseren via baseline selectie.
• Praktisch Nut: Een methode die superieure schattingsnauwkeurigheid en convergentieprestaties bereikt in real-world applicaties (inclusief LLMs) zonder de prohibitieve query kosten van volledige finite-difference schema's.
• Schaalbaarheid: Het vermogen om hoogdimensionale problemen (bijv. miljoenen parameters in LLMs) aan te pakken via efficiënte inverse benaderingen en query hergebruik, wat second-order optimalisatie haalbaar maakt in black-box settings waar dit voorheen onpraktisch was.

De auteurs benadrukken dat hoewel de methode een smoothing bias introduceert (inherent aan ZO methoden), de winsten in variantiereductie en query efficiëntie de nadelen aanzienlijk overtreffen, wat leidt tot snellere en stabielere convergentie in ruisgevoelige, hoogdimensionale omgevingen.