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

Technische Samenvatting: Leren om de Betrouwbaarheid van het Schatten van het Aantal Runs te Beoordelen in Stochastische Optimalisatie

Probleemstelling
Grootschalige benchmarking van stochastische optimalisatiealgoritmen staat voor een fundamentele spanning tussen experimentele betrouwbaarheid en computationele efficiëntie. Hoewel herhaalde uitvoeringen noodzakelijk zijn voor een geldige prestatiebeoordeling, groeien de kosten van uitgebreide herhalingen snel naarmate de schaal van algoritmeportefeuilles en probleemdimensies toeneemt. Huidige praktijken vertrouwen op statische ontwerpkeuzes (bijvoorbeeld het vaststellen van het aantal runs op 15, 25 of 50), wat impliciet een homogeen algoritmegedrag over problemen veronderstelt – een aanname die zelden wordt ondersteund door empirisch bewijs.

Recent werk introduceerde een empirische online heuristiek die adaptief het vereiste aantal runs per instantie schat door prestatiestabiliteit en distributiesymmetrie te monitoren. Hoewel deze methode de efficiëntie verbetert door het totale aantal uitvoeringen met ongeveer 50% te verminderen, kampt het met een kritieke beperking: in een subset van gevallen (5–25% afwijking) is het geschatte aantal runs onnauwkeurig. Deze onnauwkeurigheden kunnen slechts achteraf worden gedetecteerd nadat alle runs zijn voltooid, waardoor de methode ongeschikt is voor volledig online benchmarking-scenario's waar real-time besluitvorming vereist is.

Methodologie
Deze studie stelt een op leren gebaseerde uitbreiding voor van de bestaande empirische online heuristiek, waardoor deze wordt omgezet in een zelfassessend systeem dat in staat is tot vroege detectie van onbetrouwbare schattingen van het aantal runs.

• Data Bron en Annotatie: De studie maakt gebruik van een dataset afgeleid van 132.000 runs van 11 optimalisatiealgoritmen (uit het Nevergrad-framework) over 24 probleemklassen in 20 dimensies (COCO benchmark-suite). De ground truth-labels (betrouwbare versus onbetrouwbare schattingen) werden vastgesteld via post-hoc analyse van de oorspronkelijke adaptieve stopexperimenten, die drie outlier-detectiemethoden (IQR, percentieltrimming, gemodificeerde z-score) en vier scheefheidsdrempels (0,05, 0,10, 0,15, 0,20) gebruikten.
• Functie-extractie: Om toezichtleren mogelijk te maken, worden variabele lengte-sequenties van doelwitfunctiewaarden omgezet in vaste dimensionale feature-vectoren. In totaal worden 23 features geëxtraheerd, ingedeeld als:
  • Statistisch: Gemiddelde, mediaan, standaardafwijking, variantie, kwartielen, interkwartielafstand, MAD, variatiecoëfficiënt.
  • Distributie: Scheefheid, kurtosis, entropie.
  • Energie-gerelateerd: Som, som van absolute waarden, signaalenergie, wortel-gemiddelde-kwadraat.
  • Vorm en Stabiliteit: Helling van prestatieverbetering, rollende standaardafwijking, FFT-energie en autocorrelatie.
• Leertaak: Het probleem wordt geformuleerd als een binaire classificatietak om te voorspellen of een schatting van het aantal runs correct (1) of incorrect (0) is.
  • Klasse-ongelijkheid: De dataset vertoont een sterke klasse-ongelijkheid. De studie prioriteert de detectie van incorrecte schattingen (minderheidsklasse) om voortijdig stoppen te voorkomen.
  • Modelselectie: Hyperparameteroptimalisatie wordt uitgevoerd met Optuna over boom-gebaseerde en ensemble-modellen (Decision Trees, Random Forests, XGBoost, LightGBM, CatBoost). De objectieve functie maximaliseert Recall0 (recall van de minderheidsklasse) in plaats van nauwkeurigheid of F1-score, omdat false negatives (een onbetrouwbare schatting voorspellen als betrouwbaar) schadelijker zijn dan false positives.
  • Experimentele Opstelling: Een "within-configuration" leeropstelling wordt toegepast. Modellen worden getraind en getest op data die dezelfde optimizer, outlier-methode en scheefheidsdrempel delen. Dit resulteert in 132 distincte datasets (3 methoden × 4 drempels × 11 algoritmen).

Belangrijkste Bijdragen

1. Hervervorming van Adaptief Stoppen: Het artikel verschuift de focus van het louter schatten van het aantal runs naar het beoordelen van de betrouwbaarheid van die schatting in real-time.
2. Feature Engineering voor Optimalisatiedynamiek: Het introduceert een specifieke set van 23 statistische, energie-vrije en vorm/stabiliteits-features afgeleid van optimalisatietrajecten om convergentiegedrag te karakteriseren.
3. Strategie voor Ongelijke Classificatie: Het demonstreert een specifieke aanpak voor het omgaan met ongelijke data in benchmarking-contexten, waarbij de kosten van het missen van een onbetrouwbare schatting (false negative) zwaarder wegen dan de kosten van redundante runs (false positive).

Resultaten
De evaluatie onthult aanzienlijke uitdagingen en specifieke successen in het leren van betrouwbaarheid binnen vaste configuraties:

• Beperkte Generaliseerbaarheid: Geldige classifiers (die voldoen aan $F1_1 > 0,70$ en $Recall_0 > 0,80$) werden verkregen in slechts 48,5% van de 132 configuraties (64/132). Dit onderstreept de moeilijkheid om betrouwbare modellen te leren wanneer beperkt tot een enkele optimizer en vaste experimentele parameters.
• Algoritme-variabiliteit: Voorspelbaarheid varieerde aanzienlijk per algoritme. Differential Evolution (DE), Diagonal CMA, NGOpt14 en NGOpt38 behaalden de hoogste successpercentages (66,7% geldige configuraties), terwijl NaiveIsoEMNA het moeilijkst te voorspellen was (8,3% geldige configuraties).
• Trade-off met Baseline: In vergelijking met een meerderheidsklasse-baseline (die alle instanties als betrouwbaar voorspelt), presteerden de getrainde classifiers vaak slechter in termen van $F1_1$ (slechts 6,8% van de datasets presteerde beter dan de baseline). De baseline behaalde echter een $Recall_0$ van 0,00, wat betekent dat het volledig faalde in het identificeren van onbetrouwbare schattingen. Daarentegen behaalden de getrainde classifiers consistent $Recall_0$-waarden boven de 0,80, en slaagden ze erin om problematische convergentiegevallen te identificeren die de baseline miste.

Betekenis en Claims
Het artikel beweert dat de betrouwbaarheid van het aantal runs kan worden geleerd in een within-configuration scenario, waardoor de detectie van onbetrouwbare schattingen mogelijk wordt met een hoge recall van de minderheidsklasse. Deze mogelijkheid transformeert de adaptieve heuristiek in een systeem dat real-time experimentele beslissingen ondersteunt, terwijl de efficiëntievoordelen van adaptieve runschatting behouden blijven.

Echter, de auteurs zijn bescheiden over de reikwijdte van deze bevindingen. Ze stellen expliciet dat de prestaties "beperkt worden door de beperkte data-diversiteit binnen vaste configuraties". Met slechts 240 instanties per configuratie, worstelen modellen om meer te leren dan meerderheidsklasse-voorspelling. De studie concludeert dat hoewel betrouwbaarheidsvoorspelling mogelijk is, het uitdagend blijft in datalimietende settings, wat suggereert dat toekomstig werk scenario's moet verkennen waarbij data van verschillende optimalisatiealgoritmen wordt gecombineerd om de trainingsdiversiteit te vergroten.