KSOS-BO: Improving Sampling in Bayesian Optimization via Kernel Sum of Squares

Technische Samenvatting: KSOS-BO: Het Verbeteren van Sampling in Bayesiaanse Optimalisatie via Kernel Som van Kwadraten

Probleemstelling
Bayesiaanse Optimalisatie (BO) is een standaardkader voor het globaal optimaliseren van dure black-box functies, en wordt veel gebruikt bij het afstemmen van hyperparameters, in robotica en voor wetenschappelijk ontwerp. Het BO-proces omvat twee stappen: het aanpassen van een surrogaatmodel (doorgaans een Gaussisch Proces) en het optimaliseren van een acquisitiefunctie om het volgende querypunt te selecteren. Hoewel aanzienlijk onderzoek is gericht op het verbeteren van surrogaatmodellen en het ontwerp van acquisitiefuncties, blijft de optimalisatie van de acquisitiefunctie zelf een kritieke knelpunt. In de praktijk is dit innerlijke optimalisatieprobleem vaak niet-convex, multimodaal en hoogdimensionaal. Bestaande gradientenvrije optimalisatoren (bijvoorbeeld Differentiële Evolutie, CMA-ES, Sobol Search) behandelen dit vaak als een generiek black-box probleem, waarbij ze niet expliciet gebruikmaken van de gestructureerde aard van acquisitielandschappen. Bijgevolg kunnen deze methoden vastlopen in lokale optima of buitensporig veel evaluaties vereisen om hoogwaardige kandidaten te vinden, wat de algehele efficiëntie van het BO-proces beperkt.

Methodologie: KSOS-BO
De auteurs stellen KSOS-BO voor, een op kernels gebaseerde, gradientenvrije framework dat specifiek is ontworpen om acquisitiefuncties te optimaliseren. De methode past de Kernel Som-van-Kwadraten (KernelSOS)-benadering toe op de BO-context.

1. Formulering: Het kernidee is om de minimalisatie van de acquisitiefunctie $\alpha(x)$ te herformuleren als een globaal optimalisatieprobleem dat streeft naar de grootste ondergrens $c$ zodat $\alpha(x) - c \geq 0$ voor alle $x$ in het domein.
2. Kernel Relaxatie: In tegenstelling tot klassieke Som-van-Kwadraten (SOS)-methoden die beperkt zijn tot polynoomdoelen, maakt KSOS-BO gebruik van Reproducterende Kernel Hilbertruimtes (RKHS). Het vervangt eindigdimensionale polynoombases door kernelfuncties. De niet-negativiteitsbeperking wordt losgelaten tot een semidefiniet programma (SDP) dat een kernelmatrix $K$ omvat, afgeleid van een eindige set geprobeerde punten.
3. Optimalisatie en Herstel: Het algoritme lost een SDP op om een op kernels gebaseerde surrogaatrepresentatie van de verschoven acquisitiefunctie te vinden. In plaats van direct te optimaliseren in de invoerruimte, herstelt het een continu kandidaatpunt $x^*$ als een gewogen combinatie van de geprobeerde punten. Dit stelt de methode in staat om een gestructureerde globale zoektocht uit te voeren met uitsluitend functiewaarden.
4. Integratie: In elke BO-iteratie sampleert KSOS-BO punten om de huidige acquisitiefunctie te evalueren, construeert het het KernelSOS-surrogaat, lost het de SDP op om de volgende kandidaat te vinden, en werkt het het BO-model bij.

Belangrijkste Bijdragen

• Gestructureerde Globale Zoektocht: Het artikel introduceert een nieuwe toepassing van KernelSOS op acquisitieoptimalisatie, waarbij men verder gaat dan generieke black-box zoektochten om gebruik te maken van het gladde, gestructureerde karakter van acquisitielandschappen die worden veroorzaakt door Gaussische Proces-surrogaatmodellen.
• Gradientenvrij Kader: De methode werkt zonder dat gradiënten nodig zijn, waardoor deze compatibel is met standaard gradientenvrije instellingen, terwijl het een principiële alternatief biedt voor heuristische populatiegebaseerde zoektochten.
• Prestatiewinst: De auteurs tonen aan dat, ondanks hogere computerkosten per iteratie vanwege de SDP-stap, KSOS-BO snellere convergentie bereikt in kloktime door met minder acquisitie-evaluaties hoogwaardige oplossingen te bereiken.

Experimentele Resultaten
De auteurs hebben KSOS-BO geëvalueerd tegenover drie gradientenvrije baselines (Sobol Search, Differentiële Evolutie en CMA-ES) over 15 benchmarkfuncties met variërende landschapseigenschappen (multimodaal, komvormig, dalvormig, plateauvormig en steile dalingen) in 10 dimensies.

• Verbetering in Regret: KSOS-BO behaalde de beste prestaties op 10 van de 15 benchmarks. Op deze top-presterende functies toonde het een gemiddelde regretverbetering van 81,16% ten opzichte van de op één na beste optimalisator.
• Efficiëntie in Kloktime: Hoewel KSOS-BO hogere computerkosten per iteratie met zich meebrengt, convergeerde het sneller in real time. Op de 10 benchmarks waar het eerste stond, bereikte het een gemiddelde verbetering in kloktime van 93,55%, wat effectief de tijd halveert die nodig is om dezelfde nauwkeurigheid te bereiken als de baselines.
• Landschapsgevoeligheid: De methode excelleerde op sterk multimodale functies (bijvoorbeeld Ackley, Rastrigin, Griewank) en gladde unimodale functies (bijvoorbeeld Rosenbrock, Dixon Price). De prestaties verslechterden echter op functies met extreme kromming, steile dalingen of plateauvormige gebieden (bijvoorbeeld Michalewicz, Zakharov, Styblinski Tang), waar de op kernels gebaseerde representatie bleek minder adequaat te zijn.
• Robuustheid: Ablatiestudies gaven aan dat KSOS-BO robuust is tegen variaties in de grootte van het initiële ontwerp, evaluatiebudgetten en kernelkeuzes (Gaussisch versus Laplace), hoewel het consistent de baselines overtrof op het merendeel van de testgevallen.

Betekenis en Claims
Het artikel beweert dat het verbeteren van de optimalisatiestap van de acquisitie op zichzelf meetbare verbeteringen oplevert in de algehele prestaties van Bayesiaanse Optimalisatie. De primaire betekenis ligt in het aantonen dat het behandelen van acquisitieoptimalisatie als een gestructureerd probleem dat oplosbaar is via KernelSOS-relaxaties superieur is aan het behandelen ervan als een generiek black-box probleem.

De auteurs merken bescheiden op dat, hoewel KSOS-BO effectief is voor diverse landschapsstructuren, het geen universele oplossing is; het heeft moeite met specifieke geometrische kenmerken zoals steile dalingen of vlakke plateaus. Bovendien introduceert de methode een computertwist: de SDP-stap is duurder dan standaard evolutionaire strategieën, maar deze kosten worden gerechtvaardigd door de vermindering in het aantal dure functiewaarden die nodig zijn om optimale oplossingen te vinden. Het werk suggereert dat toekomstige richtingen zich moeten richten op het verbeteren van de schaalbaarheid van KSOS-BO, het verkennen van hybride strategieën met lokale verfijning, en het testen in hogerdimensionale of beperkte omgevingen.