Power Homotopy for Zeroth-Order Non-Convex Optimizations

Technische Samenvatting: Power Homotopy voor Zeroth-Order Niet-Convexe Optimalisaties

Probleemstelling
Het artikel behandelt de uitdaging van zeroth-order (ZO) optimalisatie voor niet-convexe problemen, waarbij de doelfunctie $f: \mathbb{R}^d \to \mathbb{R}$ gemaximaliseerd moet worden zonder toegang tot de gradiënten ervan. Hoewel bestaande methoden zoals GS-PowerOpt gebruikmaken van power-getransformeerde Gaussische smoothing om globale optima te lokaliseren, vertrouwen zij op een vaste smoothing-radius $\sigma$. De auteurs identificeren een fundamentele beperking in dit vaste-$\sigma$-ontwerp: een inherente afruil tussen globale exploratie en lokale verfijning. Een grote $\sigma$ vergemakkelijkt globale exploratie en versnelt de surrogaatoptimalisatie, maar vervormt de locatie van de surrogaat-maximaal; omgekeerd behoudt een kleine $\sigma$ de lokale geometrie, maar levert het zwakke gradiëntsignalen wanneer de iteratie ver verwijderd is van gebieden met hoge waarden.

Methodologie: GS-PowerHP
Om deze afruil op te lossen, stellen de auteurs GS-PowerHP (Power-Transformed Gaussian Homotopy) voor, een single-loop zeroth-order algoritme dat power-transformatie integreert met een principieel verval van de smoothing-radius.

1. Doeltransformatie: De methode richt zich op de surrogaat-doelfunctie:
   $$F_{N,\sigma}(\mu) := \mathbb{E}_{x \sim \mathcal{N}(\mu, \sigma^2 I_d)}[e^{N f(x)}]$$
   waarbij $N$ een power-parameter is en $\sigma$ de smoothing-radius.
2. Verval-schema (Decaying Schedule): In tegenstelling tot GS-PowerOpt, dat een vaste $\sigma$ gebruikt, werkt GS-PowerHP de smoothing-radius in elke iteratie $t$ bij volgens:
   $$\sigma_{t+1} = \sigma_0 \beta^{t+1} + b$$
   waarbij $\beta \in (0, 1)$ een vervactorfactor is en $b > 0$ een ondergrens.
3. Update-regel: Het algoritme voert een stochastische gradiënt-ascent stap uit:
   $$\mu_{t+1} = \mu_t + \alpha_t \hat{\nabla} F_{N,\sigma_{t+1}}(\mu_t)$$
   De gradiëntschatter wordt berekend met behulp van $K$ monsters getrokken uit $\mathcal{N}(\mu_t, \sigma_{t+1}^2 I_d)$.
4. Mechanisme: De strategie begint met een grotere $\sigma$ om informatieve gradiëntsignalen te behouden tijdens globale exploratie (wanneer $\mu_t$ ver van het optimum verwijderd is) en verlaagt $\sigma$ geleidelijk om de lokale verfijning te verbeteren naarmate de iteratie de maximaal nadert.

Belangrijkste Bijdragen

1. Theoretisch Inzicht: De auteurs bieden een formele analyse die de afruil tussen exploratie en verfijning identificeert die inherent is aan het vaste-$\sigma$-mechanisme van GS-PowerOpt. Ze tonen aan dat de iteratiecomplexiteit evenredig is met $\sigma^{-2}$ (wat grotere $\sigma$ bevoordeelt), terwijl de uitlijning tussen de surrogaat-maximaal en de ware globale maximaal verbetert naarmate $\sigma \to 0$ (wat kleinere $\sigma$ bevoordeelt).
2. Algoritmische Innovatie: GS-PowerHP is de eerste zeroth-order methode die expliciet power-transformatie combineert met een incrementeel $\sigma$-vervalmechanisme.
3. Convergentiegaranties: Het artikel stelt theoretische convergentieresultaten vast (Corollaries 1 en 3). Het bewijst dat, onder milde aannames, GS-PowerHP in verwachting convergeert naar een willekeurige kleine omgeving van de globale maximaal. De eindige-tijd convergentiesnelheid naar first-order stationariteit wordt aangetoond als $O((d^2 \epsilon^{-1} b^{-2})^{\frac{2}{1-2\gamma}})$, wat valideert dat het verval-schema snelle initiële progressie mogelijk maakt terwijl lokale nauwkeurigheid in de limiet wordt gewaarborgd.
4. Empirische Superieuriteit: Uitgebreide experimenten tonen aan dat GS-PowerHP consequent beter presteert dan fixed-$\sigma$ baselines (inclusief GS-PowerOpt) en andere smoothing-gebaseerde ZO-methoden (zoals ZOSGD, ZO-AdaMM en ZOSLGH).

Experimentele Resultaten
De auteurs evalueerden GS-PowerHP op:

• Benchmark Functies: Maximalisatie van de Ackley- en Rastrigin-functies in $d=100$ dimensies. GS-PowerHP behaalde de hoogste fitnesswaarden onder de smoothing-gebaseerde methoden en had minder iteraties nodig om te convergeren vergeleken met GS-PowerOpt.
• Adversariële Aanvallen (Black-Box): De methode werd getest op "least-likely" gerichte aanvallen tegen classificatiesystemen voor MNIST, CIFAR-10 en ImageNet.
  • Op ImageNet ($d=150,528$) behaalde GS-PowerHP een succespercentage van 78%, een substantiële verbetering ten opzichte van GS-PowerOpt (47%) en ZOSLGHd (67%), terwijl een vergelijkbare perturbatiegrootte en beeldgelijkenis werden behouden.
  • Op MNIST en CIFAR-10 behaalde het een succespercentage van 100% met kleinere perturbatie-normen dan concurrerende smoothing-gebaseerde algoritmen.
• Ablatie-studies: Experimenten op synthetische doelfuncties en gerichte aanvallen bevestigden dat het verval-$\sigma$-mechanisme de primaire drijfveer is van de prestatiewinst, waardoor het algoritme exploratie en verfijning effectiever kan balanceren dan fixed-$\sigma$ varianten.

Betekenis en Claims
Het artikel claimt dat GS-PowerHP een significante vooruitgang vertegenwoordigt in zeroth-order niet-convexe optimalisatie door de smoothing-radius te behandelen als een adaptieve computationele hulpbron in plaats van een statische hyperparameter. De auteurs stellen dat deze aanpak de structurele spanning tussen exploratie en nauwkeurigheid oplost die aanwezig is in eerdere power-smoothing methoden.

De betekenis van het werk wordt benadrukt door de robuuste prestaties in extreem hoog-dimensionale instellingen (bijv. ImageNet-aanvallen), waar het bestaande smoothing-gebaseerde methoden overtreft en een computationeel lichtere alternatief biedt voor covariantie-adaptatie methoden zoals CMA-ES (die een volledige covariantie-matrix vereist om te onderhouden). De auteurs concluderen dat de combinatie van power-transformatie en homotopy-stijl verval zowel sterke theoretische convergentiegaranties als superieure empirische resultaten biedt voor uitdagende black-box optimalisatietaken.