Learning to Assess the Reliability of Number-of-Runs Estimation in Stochastic Optimization

Sintesi Tecnica: Apprendere a Valutare l'Affidabilità della Stima del Numero di Esecuzioni nell'Ottimizzazione Stocastica

Enunciato del Problema
Il benchmarking su larga scala degli algoritmi di ottimizzazione stocastica affronta una tensione fondamentale tra affidabilità sperimentale ed efficienza computazionale. Sebbene esecuzioni ripetute siano necessarie per una valutazione valida delle prestazioni, il costo di una ripetizione estesa cresce rapidamente con la scala dei portafogli di algoritmi e delle dimensioni dei problemi. Le pratiche attuali si basano su scelte di progettazione statiche (ad esempio, fissare il numero di esecuzioni a 15, 25 o 50), che presuppongono implicitamente un comportamento omogeneo degli algoritmi tra i vari problemi, un'ipotesi raramente supportata da evidenze empiriche.

Un lavoro recente ha introdotto un euristica online empirica che stima in modo adattivo il numero di esecuzioni necessario per istanza monitorando la stabilità delle prestazioni e la simmetria della distribuzione. Sebbene questo metodo migliori l'efficienza riducendo il numero totale di esecuzioni di circa il 50%, soffre di una limitazione critica: in un sottoinsieme di casi (deviazione del 5–25%), la stima del numero di esecuzioni è inaccurata. Queste imprecisioni possono essere rilevate solo retrospettivamente, dopo il completamento di tutte le esecuzioni, rendendo il metodo inadatto a scenari di benchmarking completamente online dove è richiesta la presa di decisioni in tempo reale.

Metodologia
Questo studio propone un'estensione basata sull'apprendimento dell'euristica online empirica esistente, trasformandola in un sistema di autovalutazione capace di rilevare precocemente stime inaffidabili del numero di esecuzioni.

• Fonte dei Dati e Annotazione: Lo studio utilizza un dataset derivato da 132.000 esecuzioni di 11 algoritmi di ottimizzazione (dal framework Nevergrad) su 24 classi di problemi in 20 dimensioni (suite di benchmark COCO). Le etichette di verità fondamentale (stime affidabili vs. inaffidabili) sono state stabilite tramite un'analisi post-hoc degli esperimenti originali di arresto adattivo, che hanno utilizzato tre metodi di rilevamento degli outlier (IQR, potatura percentilica, z-score modificato) e quattro soglie di asimmetria (0,05; 0,10; 0,15; 0,20).
• Estrazione delle Caratteristiche: Per abilitare l'apprendimento supervisionato, sequenze di lunghezza variabile di valori della funzione obiettivo vengono trasformate in vettori di caratteristiche a dimensionalità fissa. Vengono estratte un totale di 23 caratteristiche, categorizzate come:
  • Statistiche: Media, mediana, deviazione standard, varianza, quartili, intervallo interquartile, MAD, coefficiente di variazione.
  • Distribuzionali: Asimmetria, curtosi, entropia.
  • Relativi all'energia: Somma, somma dei valori assoluti, energia del segnale, valore quadratico medio.
  • Forma e Stabilità: Pendenza del miglioramento delle prestazioni, deviazione standard mobile, energia FFT e autocorrelazione.
• Compito di Apprendimento: Il problema è formulato come un compito di classificazione binaria per prevedere se una stima del numero di esecuzioni è corretta (1) o errata (0).
  • Squilibrio delle Classi: Il dataset presenta un forte squilibrio di classe. Lo studio dà priorità al rilevamento di stime errate (classe di minoranza) per evitare arresti prematuri.
  • Selezione del Modello: L'ottimizzazione degli iperparametri viene eseguita utilizzando Optuna su modelli basati su alberi e modelli di ensemble (Alberi Decisionali, Random Forest, XGBoost, LightGBM, CatBoost). La funzione obiettivo massimizza il Recall0 (recall della classe di minoranza) piuttosto che l'accuratezza o il punteggio F1, poiché i falsi negativi (prevedere una stima inaffidabile come affidabile) sono più dannosi dei falsi positivi.
  • Configurazione Sperimentale: Viene adottata una configurazione di apprendimento "entro la configurazione". I modelli vengono addestrati e testati su dati che condividono lo stesso ottimizzatore, metodo di rilevamento degli outlier e soglia di asimmetria. Ciò risulta in 132 dataset distinti (3 metodi × 4 soglie × 11 algoritmi).

Principali Contributi

1. Riformulazione dell'Arresto Adattivo: Il documento sposta il focus dalla semplice stima del numero di esecuzioni alla valutazione dell'affidabilità di tale stima in tempo reale.
2. Ingegneria delle Caratteristiche per le Dinamiche di Ottimizzazione: Introduce un insieme specifico di 23 caratteristiche statistiche, prive di energia e relative a forma/stabilità, derivate dalle traiettorie di ottimizzazione per caratterizzare il comportamento di convergenza.
3. Strategia di Classificazione per Dati Sbilanciati: Dimostra un approccio specifico per la gestione di dati sbilanciati nei contesti di benchmarking, dove il costo di perdere una stima inaffidabile (falso negativo) supera il costo di esecuzioni ridondanti (falso positivo).

Risultati
La valutazione rivela sfide significative e successi specifici nell'apprendimento dell'affidabilità all'interno di configurazioni fisse:

• Generalizzabilità Limitata: Classificatori validi (che soddisfano $F1_1 > 0,70$ e $Recall_0 > 0,80$) sono stati ottenuti solo nel 48,5% delle 132 configurazioni (64/132). Ciò evidenzia la difficoltà di apprendere modelli affidabili quando si è limitati a un singolo ottimizzatore e a parametri sperimentali fissi.
• Variabilità degli Algoritmi: La prevedibilità è variata significativamente in base all'algoritmo. L'evoluzione differenziale (DE), CMA diagonale, NGOpt14 e NGOpt38 hanno raggiunto i tassi di successo più elevati (66,7% di configurazioni valide), mentre NaiveIsoEMNA è stato il più difficile da prevedere (8,3% di configurazioni valide).
• Compromesso con la Baseline: Se confrontati con una baseline di classe maggioritaria (che prevede tutte le istanze come affidabili), i classificatori addestrati hanno spesso ottenuto prestazioni inferiori in termini di $F1_1$ (solo il 6,8% dei dataset ha superato la baseline). Tuttavia, la baseline ha raggiunto un $Recall_0$ di 0,00, il che significa che ha fallito completamente nel rilevare stime inaffidabili. Al contrario, i classificatori addestrati hanno costantemente raggiunto valori di $Recall_0$ superiori a 0,80, identificando con successo casi di convergenza problematici che la baseline aveva mancato.

Significato e Affermazioni
Il documento afferma che l'affidabilità del numero di esecuzioni può essere appresa in uno scenario "entro la configurazione", consentendo il rilevamento di stime inaffidabili con un elevato recall della classe di minoranza. Questa capacità trasforma l'euristica adattiva in un sistema che supporta decisioni sperimentali in tempo reale, preservando al contempo i benefici di efficienza della stima adattiva del numero di esecuzioni.

Tuttavia, gli autori sono modesti riguardo alla portata di questi risultati. Affermano esplicitamente che le prestazioni sono "limitate dalla diversità dei dati ristretta all'interno delle configurazioni fisse". Con sole 240 istanze per configurazione, i modelli faticano ad apprendere oltre la previsione della classe maggioritaria. Lo studio conclude che, sebbene la previsione dell'affidabilità sia possibile, rimane una sfida in contesti con dati limitati, suggerendo che il lavoro futuro dovrebbe esplorare scenari in cui i dati provenienti da diversi algoritmi di ottimizzazione vengono combinati per aumentare la diversità dell'addestramento.