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

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

Problem Statement
Large-scale benchmarking of stochastic optimization algorithms faces a fundamental tension between experimental reliability and computational efficiency. While repeated executions are necessary for valid performance assessment, the cost of extensive repetition grows rapidly with the scale of algorithm portfolios and problem dimensions. Current practices rely on static design choices (e.g., fixing the number of runs to 15, 25, or 50), which implicitly assume homogeneous algorithm behavior across problems—an assumption rarely supported by empirical evidence.

Recent work introduced an empirical online heuristic that adaptively estimates the required number of runs per instance by monitoring performance stability and distribution symmetry. While this method improves efficiency by reducing total executions by approximately 50%, it suffers from a critical limitation: in a subset of cases (5–25% deviation), the estimated run count is inaccurate. These inaccuracies can only be detected retrospectively after all runs are completed, rendering the method unsuitable for fully online benchmarking scenarios where real-time decision-making is required.

Methodology
This study proposes a learning-based extension to the existing empirical online heuristic, transforming it into a self-assessing system capable of early detection of unreliable run-number estimates.

• Data Source and Annotation: The study utilizes a dataset derived from 132,000 runs of 11 optimization algorithms (from the Nevergrad framework) across 24 problem classes in 20 dimensions (COCO benchmark suite). The ground truth labels (reliable vs. unreliable estimates) were established via post-hoc analysis of the original adaptive stopping experiments, which used three outlier detection methods (IQR, percentile trimming, modified z-score) and four skewness thresholds (0.05, 0.10, 0.15, 0.20).
• Feature Extraction: To enable supervised learning, variable-length sequences of objective function values are transformed into fixed-dimensional feature vectors. A total of 23 features are extracted, categorized as:
  • Statistical: Mean, median, standard deviation, variance, quartiles, interquartile range, MAD, coefficient of variation.
  • Distributional: Skewness, kurtosis, entropy.
  • Energy-related: Sum, sum of absolute values, signal energy, root mean square.
  • Shape and Stability: Slope of performance improvement, rolling standard deviation, FFT energy, and autocorrelation.
• Learning Task: The problem is formulated as a binary classification task to predict whether a run-number estimation is correct (1) or incorrect (0).
  • Class Imbalance: The dataset exhibits strong class imbalance. The study prioritizes the detection of incorrect estimates (minority class) to avoid premature stopping.
  • Model Selection: Hyperparameter optimization is performed using Optuna across tree-based and ensemble models (Decision Trees, Random Forests, XGBoost, LightGBM, CatBoost). The objective function maximizes Recall0 (recall of the minority class) rather than accuracy or F1-score, as false negatives (predicting an unreliable estimate as reliable) are more detrimental than false positives.
  • Experimental Setup: A "within-configuration" learning setup is employed. Models are trained and tested on data sharing the same optimizer, outlier method, and skewness threshold. This results in 132 distinct datasets (3 methods × 4 thresholds × 11 algorithms).

Key Contributions

1. Reframing Adaptive Stopping: The paper shifts the focus from merely estimating the number of runs to assessing the reliability of that estimate in real-time.
2. Feature Engineering for Optimization Dynamics: It introduces a specific set of 23 statistical, energy-free, and shape/stability features derived from optimization trajectories to characterize convergence behavior.
3. Imbalanced Classification Strategy: It demonstrates a specific approach to handling imbalanced data in benchmarking contexts, where the cost of missing an unreliable estimate (false negative) outweighs the cost of redundant runs (false positive).

Results
The evaluation reveals significant challenges and specific successes in learning reliability within fixed configurations:

• Limited Generalizability: Valid classifiers (meeting $F1_1 > 0.70$ and $Recall_0 > 0.80$) were obtained in only 48.5% of the 132 configurations (64/132). This highlights the difficulty of learning reliable models when restricted to a single optimizer and fixed experimental parameters.
• Algorithm Variability: Predictability varied significantly by algorithm. Differential Evolution (DE), Diagonal CMA, NGOpt14, and NGOpt38 achieved the highest success rates (66.7% valid configurations), while NaiveIsoEMNA was the most difficult to predict (8.3% valid configurations).
• Trade-off with Baseline: When compared to a majority-class baseline (which predicts all instances as reliable), the trained classifiers often underperformed in terms of $F1_1$ (only 6.8% of datasets outperformed the baseline). However, the baseline achieved a $Recall_0$ of 0.00, meaning it failed completely to identify unreliable estimates. In contrast, the trained classifiers consistently achieved $Recall_0$ values above 0.80, successfully identifying problematic convergence cases that the baseline missed.

Significance and Claims
The paper claims that run-number reliability can be learned in a within-configuration scenario, enabling the detection of unreliable estimates with high minority-class recall. This capability transforms the adaptive heuristic into a system that supports real-time experimental decisions while preserving the efficiency benefits of adaptive run estimation.

However, the authors are modest about the scope of these findings. They explicitly state that performance is "limited by the restricted data diversity within fixed configurations." With only 240 instances per configuration, models struggle to learn beyond majority-class prediction. The study concludes that while reliability prediction is possible, it remains challenging in data-limited settings, suggesting that future work should explore scenarios where data from different optimization algorithms are combined to increase training diversity.