Cost-aware Stopping for Bayesian Optimization

Sintesi Tecnica: Arresto Consapevole dei Costi per l'Ottimizzazione Bayesiana

Problematica
Nell'apprendimento automatico automatizzato (Automated Machine Learning), nella scoperta scientifica e in altre applicazioni dell'ottimizzazione bayesiana (BO), i professionisti affrontano la sfida di decidere quando terminare l'valutazione di funzioni black-box costose. Sebbene esistano regole di arresto esistenti, esse spesso non riescono a tenere conto dei costi variabili in modo rigoroso.

• Regole euristiche (ad esempio, conteggi fissi delle iterazioni o arresto quando il miglior valore rimane invariato) mancano di garanzie teoriche e possono fermarsi troppo presto o comportare valutazioni non necessarie.
• Regole basate sul regret (ad esempio, UCB-LCB, Knowledge Gradient) sono teoricamente fondate per minimizzare il regret semplice, ma sono tipicamente progettate per scenari a costo uniforme. Non tengono esplicitamente conto dei costi di valutazione, portando spesso a costi cumulativi eccessivi e a un elevato regret aggiustato per il costo quando i costi sono alti.
• Funzioni di acquisizione consapevoli del costo (ad esempio, Pandora's Box Gittins Index (PBGI) e Log Expected Improvement per Costo (LogEIPC)) sono state sviluppate per ottimizzare il compromesso tra qualità della soluzione e costo, ma la loro integrazione con regole di arresto adattive non è stata studiata sistematicamente.

L'obiettivo principale è progettare una regola di arresto che ottimizzi il regret semplice aggiustato per il costo atteso, definito come la somma del regret semplice (la differenza tra la migliore soluzione trovata e l'ottimo globale) e del costo cumulativo della raccolta dati.

Metodologia
Gli autori propongono una nuova, rigorosa regola di arresto consapevole del costo derivata dal framework decisionale di Pandora's Box. La metodologia stabilisce una connessione teorica tra due funzioni di acquisizione consapevoli del costo all'avanguardia:

1. Pandora's Box Gittins Index (PBGI): Derivato dalla soluzione di programmazione dinamica del problema di Pandora's Box, adattato per l'ottimizzazione bayesiana correlata.
2. Log Expected Improvement per Costo (LogEIPC): Un'approssimazione a singolo step della politica ottimale bayesiana.

La regola di arresto proposta, denominata regola di arresto PBGI/LogEIPC, è definita dalla condizione per cui l'ottimizzazione deve cessare quando nessun punto non osservato offre un miglioramento atteso che valga il suo costo di valutazione. Matematicamente, la regola si arresta al tempo $\tau$ quando:
$$\min_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{PBGI}^\tau(x) \geq y^*_{1:\tau}$$
o equivalentemente:
$$\max_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{LogEIPC}^\tau(x) \leq 0$$
dove $y^*_{1:\tau}$ è il miglior valore osservato finora.

I dettagli chiave dell'implementazione includono:

• Tempistica dell'aggiornamento del posteriore: La regola utilizza i valori della funzione di acquisizione calcolati dopo l'aggiornamento del posteriore dell'iterazione corrente (prospettica), il che, secondo gli autori, riflette meglio l'intuizione del "valore equo" (fair value) e produce guadagni empirici rispetto agli approcci retrospettivi.
• Gestione di costi sconosciuti: Quando i costi sono sconosciuti, vengono modellati stochasticamente (ad esempio, come un Processo Gaussiano sul log-costo) e il costo atteso $E[c(x)]$ viene utilizzato nella condizione di arresto.
• Stabilizzazione: Per prevenire arresti spurii causati da fluttuazioni del modello o da un'ottimizzazione imperfetta della funzione di acquisizione (specialmente in dimensioni elevate), gli autori impongono un periodo di stabilizzazione e applicano uno smoothing tramite media mobile al segnale di arresto.

Contributi Chiave

1. Una Nuova Regola di Arresto Consapevole del Costo: Il documento presenta una regola di arresto adattiva derivata dalla teoria di Pandora's Box che estende naturalmente il principio di progettazione del miglioramento atteso. Fornisce un framework unificato applicabile sia alla BO classica che a quella consapevole del costo.
2. Garanzie Teoriche: Gli autori dimostrano che, quando accoppiata con funzioni di acquisizione PBGI o LogEIPC, la proposta regola di arresto soddisfa un limite superiore teorico sul regret semplice aggiustato per il costo atteso. Nello specifico, la politica è garantita di non performare peggio della baseline di "arresto immediato" (arresto subito dopo la prima valutazione). Questo costituisce la prima garanzia teorica di questo tipo per qualsiasi regola di arresto adattiva nell'ottimizzazione bayesiana.
3. Validazione Empirica: Lo studio fornisce una valutazione sistematica attraverso compiti sintetici e benchmark empirici (LCBench per l'ottimizzazione degli iperparametri e NATS-Bench per la ricerca di architetture neurali).

Risultati

• Compiti Sintetici: In impostazioni di regret bayesiano 1D e 8D con funzioni di costo uniformi, lineari e periodiche, la regola di arresto PBGI/LogEIPC, accoppiata con la sua corrispondente funzione di acquisizione, eguaglia o supera costantemente altre coppie (inclusi UCB-LCB, LogEIPC-med e PRB). È particolarmente robusta in scenari ad alto costo.
• Benchmark Empirici:
  • Su LCBench (35 dataset), la regola proposta accoppiata con PBGI o LogEIPC si posiziona nei primi 3 posti per circa il 75% dei task.
  • Su NATS-Bench, la regola performa in modo competitivo, avvicinandosi alle prestazioni ottimali a posteriori (hindsight-optimal).
  • La regola interrompe l'esecuzione in modo affidabile prima del limite di iterazioni (200 iterazioni), mentre le regole basate sul regret di baseline (come SRGap-med e UCB-LCB) spesso non riescono ad arrestarsi precocemente, incorrendo in costi eccessivi.
  • Gli autori notano che le prestazioni inferiori su specifici piccoli dataset sono probabilmente dovute a mismatch intrinseci tra validazione e test nel benchmark piuttosto che alla regola di arresto stessa.

Significatività e Rivendicazioni
Il documento sostiene di affrontare una considerazione pratica critica ma poco esplorata nell'ottimizzazione bayesiana: la determinazione consapevole del costo di quando fermarsi.

• Avanzamento Teorico: Il lavoro colma il divario tra le funzioni di acquisizione consapevoli del costo e l'arresto adattivo, fornendo la prima garanzia formale che una politica adattiva non incorrerà in un regret aggiustato per il costo peggiore rispetto all'arresto immediato.
• Utilità Pratica: La regola proposta elimina la necessità di una sintonizzazione euristica delle soglie di arresto (ad esempio, costanti fisse o soglie basate sulla mediana) derivando la soglia direttamente dal costo di valutazione.
• Robustezza: Il framework dimostra robustezza attraverso diverse strutture di costo e misspecification del modello, offrendo un'alternativa fondata ai criteri di arresto euristici in compiti di ottimizzazione costosi.

Gli autori concludono che il loro framework può essere esteso a contesti che coinvolgono valutazioni rumorose, multi-fedeltà o a batch, sebbene queste siano note come direzioni future piuttosto che contributi attuali.