CHISAO skúša hľadať viac vrcholov funkcie priamo na GPU

Optimalizácia multimodálnych black-box funkcií patrí medzi problémy, pri ktorých sa výskumníci často zmieria s kompromisom. Funkcia má viac lokálnych vrcholov alebo módov, gradienty nie sú dostupné a cieľom nie je nájsť iba jedno dobré riešenie, ale čo najviac relevantných riešení. Nový arXiv preprint predstavuje metódu CHISAO, ktorá sa pokúša tento problém preformulovať pre masívny paralelizmus grafických procesorov.

Názov CHISAO je skratka pre Convergence-Halt-Invert-Stick-And-Oscillate. Za dlhým názvom je jednoduchá myšlienka: celá populácia vzoriek beží naraz na GPU, pričom časti populácie sa nechajú zbiehať, nájdené skutočné vrcholy sa zmrazia a zvyšné vzorky sa cielene rozhýbu tak, aby neuviazli v rovnakých lokálnych pasciach. Autori to opisujú ako cyklus konvergencie a antikonvergencie, ktorý má striedať sústredenie na sľubné oblasti s únikom z nich.

Black-box optimalizácia je dôležitá v bayesovskej inferencii, vedeckom výpočte, ladení simulácií, návrhu materiálov či hyperparametrickom hľadaní. Označenie black-box znamená, že algoritmus môže funkciu vyhodnocovať, ale nemá k dispozícii jej analytický tvar alebo spoľahlivý gradient. Tradičné postupy ako basin-hopping, CMA-ES alebo viacnásobné štarty gradientných metód často pracujú sekvenčne alebo len čiastočne paralelne. To obmedzuje ich schopnosť využiť moderný hardvér, najmä keď je potrebné prehľadať veľký priestor možností.

CHISAO podľa abstraktu stavia na asymetrickom zaobchádzaní so vzorkami. Tie, ktoré dosiahnu potvrdené módy, zostanú zachované. Ostatné pokračujú v prieskume cez momentum, anti-konvergenčné správanie a stochasticky vyhladené gradienty odvodené z konečných rozdielov. Populačnú rozmanitosť majú udržiavať aj dve stratégie adaptívneho opätovného osievania, ktoré autori pomenovali Repulse Monkey a Golden Rooster. Hoci názvy pôsobia hravo, riešia klasický problém: ako zabrániť tomu, aby sa všetky vzorky predčasne zhlukli okolo jedného riešenia.

Deklarované výsledky sú ambiciózne. Na 42 funkciách zo Simon Fraser University optimization benchmark suite v dimenziách od 2 po 64 má CHISAO dosiahnuť stopercentnú obnovu módov tam, kde CPU baseline metódy kolabujú pri ťažkých multimodálnych funkciách od dimenzie 8 vyššie. Autori uvádzajú aj zrýchlenia do 34-násobku oproti basin-hoppingu na funkciách, kde uspejú všetky metódy, a do 39-násobku pri unimodálnych funkciách. Zaujímavé je, že porovnanie používa iba hodnoty funkcie; gradienty sú odvodené konečnými rozdielmi, takže nejde o výhodu z analytického gradientu.

Ak sa výsledky potvrdia, najväčší význam môže byť v úlohách, kde je dôležitá diverzita riešení. Pri návrhu molekúl, nastavení robotického správania alebo kalibrácii vedeckých modelov často nestačí nájsť jedno maximum. Potrebujeme viac kandidátov, aby sa dali porovnať stabilita, náklady, bezpečnosť alebo iné obmedzenia. GPU natívna metóda, ktorá vie udržať nájdené módy a zároveň pokračovať v prieskume, by tu mohla byť prakticky užitočná.

Treba však čítať aj opatrne. Preprint vychádza z benchmarkov, nie z rozsiahleho nasadenia v priemyselných alebo vedeckých workflow. Výkon pri syntetických optimalizačných funkciách nemusí automaticky znamenať rovnaký prínos pri drahých simuláciách, šumových meraniach alebo funkciách s komplikovanými obmedzeniami. Autori síce uvádzajú robustnosť pri výraznom šume pravdepodobnosti, no praktické nasadenie bude závisieť od implementácie, pamäťových nárokov a toho, ako ľahko sa algoritmus napojí na existujúce experimentálne slučky.

Pre AI infraštruktúru je však smer zaujímavý. Veľa optimalizačných nástrojov vzniklo v ére, keď bola sekvenčná práca s CPU prirodzeným východiskom. CHISAO ukazuje opačný prístup: najprv navrhnúť dynamiku algoritmu tak, aby vyhovovala dávkovému paralelizmu GPU, a až potom ju porovnávať s klasickými metódami. Podobný posun už vidíme pri trénovaní neurónových sietí, inferencii aj simuláciách.

Pre výskumné tímy je praktický odkaz v tom, že hardvér môže meniť aj samotnú podobu algoritmov, nielen ich rýchlosť. Ak je cieľom nájsť veľa módov naraz, nemusí dávať zmysel opakovane spúšťať starý sekvenčný postup. Lepšia cesta môže byť navrhnúť populáciu, ktorá sa na GPU správa ako koordinovaný prieskumný systém. CHISAO je zatiaľ preprint, ale otvára zaujímavú debatu o tom, ako má vyzerať black-box optimalizácia v ére lacnej paralelnej výpočtovej kapacity.