Pith. sign in

REVIEW 5 major objections 5 minor 31 references

Adaptive Estimation of the Number of Algorithm Runs in Stochastic Optimization

T0 review · 5 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Pith's one-line read A paper proposes stopping algorithm runs online once the collected results are symmetric around their mean, reporting 82–95% estimation accuracy and roughly 50% fewer runs.

desk verdict Original skewness-based stopping rule, but the accuracy metric is too lenient and the savings claim lacks a baseline. read the letter →

arxiv 2507.01629 v1 pith:OEFJBO7C submitted 2025-07-02 cs.NE

classification cs.NE
keywords numberofalgorithmrunsonlinestoppingruleskewnesssamplesizeestimationstochasticoptimizationbenchmarkinggreenbootstrapconfidenceintervals
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that the number of repeated runs of a stochastic optimizer on a problem instance can be decided online, while running, rather than fixed in advance. The proposed rule runs the algorithm a few times, centers the results on their mean, and checks whether the distribution is symmetric; if the centering leaves noticeable skewness, another run is added, and the check repeats. Across 5,748,000 runs spanning 104 configurations of a popular evolutionary algorithm and 11 optimizers from a second public portfolio, the authors report 82–95% of estimates are accurate and roughly half of all runs could be omitted without changing the conclusions. If true, experimental benchmarking and algorithm configuration would become much cheaper and less energy-intensive.

What carries the argument

The load-bearing object is the sample skewness of centered run values, defined as $\tilde{\mu}_3 = E\left[\left(\frac{Y-\mu}{\sigma}\right)^3\right]$, computed after subtracting the mean and after outlier removal. It serves as a distributional symmetry check: the paper hypothesizes that an algorithm that has gathered sufficient data should produce results balanced around the mean, so a skewness near zero is the stopping signal. The threshold $\tau$ (tested at 0.05, 0.10, 0.15, and 0.20) controls how strict the symmetry requirement is, and the outlier preprocessing is needed because a few extreme failed runs would otherwise dominate the skewness estimate.

What would settle it

Simulate a distribution whose early samples are nearly symmetric but whose true mean is far from the early-sample mean, for example a mixture with many near-optimal values plus rare extremely large failures. Run the proposed rule with a fixed threshold: if it stops early and the stopped-sample mean differs from the 50-run mean by more than the paper's reported error margins, the symmetry criterion is falsified.

Watch

Extended reading notes

Core claim

The paper's central claim is that sample skewness of centered run values is a usable online signal for when enough algorithm runs have been collected. The procedure starts with five runs, subtracts the current mean from each result, removes outliers with one of three detection rules, and computes the skewness of the cleaned values. It keeps adding one run until the skewness falls inside a user-chosen threshold around zero. The authors assert that, compared with a ground-truth mean computed from 50 runs, this stopping rule gives accurate performance estimates in 82–95% of cases depending on the threshold and algorithm portfolio, and that applying it would save about 50% of runs overall.

Load-bearing premise

The load-bearing premise is that a small skewness in the collected run values guarantees that their mean is close to the long-run mean; if skewness and mean accuracy come apart, the stopping rule can be confidently wrong.

Editorial extensions

If this is right

  • If the method is correct, benchmarking studies can replace a fixed run count with an online stop rule: run, check skewness, and stop when the results balance around the mean.
  • The required number of runs becomes algorithm- and instance-specific, so easy cases stop early while variable cases continue, which is what produces the roughly 50% reduction in total runs.
  • The skewness threshold becomes a practical cost-accuracy dial: tighter thresholds buy accuracy at the price of more runs, while looser thresholds save compute at the cost of accuracy.
  • Comparative evaluations that adopt the rule could retain their statistical conclusions while consuming about half the energy, which is the paper's green-benchmarking consequence.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the symmetry-based stop rule could be compared against standard-error-based stopping rules for the mean to test whether the 50% saving comes from the skewness signal specifically or from sequential stopping in general.
  • A testable extension is to apply the same online pipeline to bootstrap confidence-interval width instead of skewness, stopping when the uncertainty around the mean crosses a target; this might behave better on heavy-tailed error distributions.
  • The paper's accuracy measure compares the stopped-sample mean with the 50-run mean, not with the true expected performance, so the reported 82–95% accuracy may not transfer to other benchmark suites or other run budgets.
  • A direct empirical probe would be to record how often the method stops early on instances whose error distribution is right-skewed, since rare failed runs are exactly the cases where symmetry and mean accuracy can diverge.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. The paper proposes an online stopping rule for determining the number of algorithm runs needed to estimate the performance of a stochastic optimizer on a given problem instance. The rule starts with five runs, computes the sample skewness of the centered performance values, and stops when the absolute skewness falls below a user-chosen threshold after optional outlier removal. The authors evaluate the rule on 104 Differential Evolution configurations and 11 Nevergrad algorithms across COCO problems in dimensions 10, 20, and 40, totaling 5,748,000 runs, and report 82%–95% "accuracy" in estimating the required number of runs, with an expected reduction of roughly 50% in the number of runs. The paper also discusses green benchmarking implications and the availability of data and code.

Significance. If the central claims were supported, the method would provide a practical, low-cost way to reduce the computational burden of benchmarking stochastic optimizers, which is a relevant and timely goal. The scale of the experimental campaign (5.7 million runs) and the public release of data and code are clear strengths, and the paper addresses an important practical problem. However, the evidence as presented is not convincing. The reported accuracy metric is a low-power confidence-interval containment test that systematically favors small samples, and no fixed-sample-size baseline is provided, so the headline accuracy and savings figures may be artifacts of the evaluation procedure rather than of the skewness-based stopping rule. The core hypothesis linking small skewness to accurate mean estimation is not theoretically justified or empirically validated, and the shared outlier-trimming step in both the rule and the evaluation further obscures the effect. The contribution is potentially valuable but requires a fundamentally reworked evaluation and a direct test of the underlying assumption.

major comments (5)
  1. [Section 4, "Bootstrapping evaluation scenario"] The accuracy metric is a CI-containment test with strong a priori bias toward accepting small n. For roughly normal data, the difference between the stopped-sample mean and the 50-run ground-truth mean has standard deviation about σ√((50−n)/(50n)), while the 95% percentile bootstrap CI for the resampled difference has half-width about 1.96σ√(1/n+1/50). At n=5 these are approximately 0.42σ and 0.92σ, respectively, so the CI would contain zero in roughly 97% of trials even if the stopping rule always stopped at five runs. The reported "true" accuracies of 82–95% are therefore below what a trivial always-stop-at-five policy would achieve, and they do not establish that the skewness rule provides accurate mean estimation. The paper should report a fixed-n baseline (e.g., n=5, 10, 15) and a direct error metric such as the relative difference between the stopped-sample mean and the 50-run mean, not a low-power hypothesis test.
  2. [Section 3, "Estimating the Number of Runs Needed"] The central hypothesis — that an algorithm gathering sufficient data from the runs should exhibit a symmetric distribution around the mean — is neither derived nor empirically tested. Performance distributions for stochastic optimizers are frequently right-skewed because of occasional bad runs, and small sample skewness can occur by chance even when the sample mean is far from the long-run mean; conversely, a symmetric distribution does not guarantee a precise mean estimate if the variance is large. The paper provides no evidence that the skewness condition is necessary or sufficient for accurate mean estimation. At least, the authors should test this hypothesis directly on their large dataset, for example by comparing the stopped-sample mean with the 50-run mean for cases where the rule stops versus cases where it continues, and by reporting the distribution of skewness for samples of different sizes.
  3. [Section 3 and Section 4, outlier removal] Outlier removal is applied both in the stopping rule (before the symmetry check) and in the evaluation (to both the estimated and ground-truth samples). This introduces a systematic bias: removing extreme runs can eliminate exactly the failed runs that matter for performance evaluation, and the reported "accuracy" compares trimmed means, not the actual performance statistic. The paper does not report results without outlier removal, so the effect of this choice on the headline numbers is unknown. The authors should present results with and without outlier removal and justify the trimming as appropriate for the intended performance measure.
  4. [Section 6, Table 2] The "expected saved runs" are computed by multiplying raw saved runs by the CI-based accuracy percentages. Since the accuracy percentages are inflated by the low-power bootstrap CI test, the resulting ~50% reduction claim is not credible. A correct analysis would use an unbiased accuracy measure (e.g., mean absolute error of the stopped-sample mean relative to the ground truth) and would compare the savings against a mechanism-free baseline that stops at a fixed small n. Without such a baseline, the green-benchmarking savings claim is unsupported.
  5. [Abstract and Section 5] The abstract claims "82%–95% accuracy in estimations across different algorithms," but Table 1 shows that for 104 DE configurations the accuracy ranges from 64.63% to 86.16% depending on the threshold and outlier method, and the 82–95% range is observed only for the Nevergrad portfolio at the strictest threshold (Figure 4). This discrepancy overstates the results and should be corrected or clarified.
minor comments (5)
  1. [Section 3, Equation (1)] The notation is confusing: after defining Y_i = X_i − X̄, the text says "the resulting variables are not independent Bernoulli variables." The performance values are continuous, not Bernoulli; the intended point seems to be that the centered values are not independent because of the shared sample mean. Please rephrase for clarity.
  2. [Section 4, "Bootstrapping evaluation scenario"] The number of bootstrap resamples M is not specified, and the text mentions using both a standard percentile CI and a bias-corrected accelerated bootstrap, but the decision rule for switching between them is not described precisely. Please state M and the exact CI construction procedure.
  3. [Throughout] The paper contains several typos and inconsistent spellings, e.g., "Nevergard" (should be "Nevergrad"), "conidtions" in the Conclusion, and "solutions" where "runs" is meant. A careful proofreading pass is needed.
  4. [Section 2 and Section 7] The related work discusses sample-size estimation methods by Campelo and Takahashi, but the experimental evaluation does not compare the proposed approach to these existing methods. Adding such a comparison, even on a subset of the data, would strengthen the paper.
  5. [Section 5, Table 1 and Figure 1] The post-hoc error thresholds (≤0.5%, ≤1%, ≤5%, etc.) are described only vaguely in Section 4; the exact definition of the error percentage (relative to what value?) should be stated explicitly so the reader can interpret the columns.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the stopping rule and the accuracy evaluation are independent, and the central claims are assessed against an external 50-run ground truth.

full rationale

The paper's derivation chain is not circular. The proposed method stops when sample skewness falls within a threshold; the number of runs n is determined by that skewness condition, not by any quantity that is later called a prediction. The accuracy of the method is evaluated by comparing the stopped n-sized sample against a separate 50-run ground-truth sample using a bootstrap confidence interval for the mean difference. This is an external comparison rather than a construction from the target result. The skewness thresholds and outlier detection techniques are varied in a grid and reported separately; they are not fitted to maximize the reported accuracy percentages. Self-citations in the paper are contextual (statistical comparison background, data provenance) and are not load-bearing for the central claim that the online method estimates the required number of runs. The bootstrap CI 'contains zero' criterion is statistically weak and may overstate accuracy for small samples, and the absence of a fixed-run baseline is a serious threats-to-validity concern, but those are correctness and experimental-design issues, not circularity: the evaluation does not define the stopping rule's output in terms of itself, and no fitted parameter is renamed as a prediction. Therefore, no circular step can be exhibited, and the appropriate circularity score is 0.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The method introduces no new physical or theoretical entities. Its load-bearing ingredients are the skewness threshold, the arbitrary initial run count, the outlier detection parameters, and the unproven symmetry hypothesis. All of these are either chosen by hand or assumed without derivation. The invented_entities list is empty because the contribution is procedural, not ontological.

free parameters (3)
  • Skewness threshold tau = 0.05, 0.10, 0.15, 0.20 (grid, no selection rule)
    Controls when the algorithm stops; accuracy ranges from 64.63% to 86.16% depending on tau and outlier method, so the choice is load-bearing and is left to the user.
  • Initial run count p = 5
    Section 3 states the choice is arbitrary, following chi-square test practice; different p would change the stopping behavior and the sample.
  • Outlier detection parameters = IQR multiplier 1.5; percentile bounds 2.5/97.5; modified z-score cutoff 3.5; MAD fallback
    Chosen from literature, but they interact with the skewness check and affect both accuracy and the estimated number of runs.
assumptions (4)
  • ad hoc to paper Sufficiently many runs make the performance distribution symmetric around its mean
    Section 3: 'Our hypothesis is that an algorithm gathering sufficient data from the runs should exhibit a symmetric distribution around the mean.' This is the core justification for the stopping rule and is not proven.
  • ad hoc to paper Removing detected outliers before the symmetry check does not bias the estimation of the required number of runs
    Section 3 applies outlier detection before the symmetry check, but outlier removal can systematically drop informative bad runs from right-skewed performance distributions.
  • domain assumption The 50-run sample is a reliable ground truth for the true performance distribution
    Section 4 uses 50 runs as ground truth for all comparisons; for high-variance settings 50 runs may still not stabilize the mean.
  • domain assumption Sequential stopping on skewness does not bias the selected sample mean
    The paper never addresses stopping-time bias; the decision to stop depends on the same data used to estimate performance.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adaptive Estimation of the Number of Algorithm Runs in Stochastic Optimization." pith.science (2026). https://pith.science/paper/OEFJBO7C

@misc{pith2026250701629,
  author       = {Pith},
  title        = {Pith review of: Adaptive Estimation of the Number of Algorithm Runs in Stochastic Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OEFJBO7C}},
  note         = {Machine review of arXiv:2507.01629}
}
read the original abstract

Determining the number of algorithm runs is a critical aspect of experimental design, as it directly influences the experiment's duration and the reliability of its outcomes. This paper introduces an empirical approach to estimating the required number of runs per problem instance for accurate estimation of the performance of the continuous single-objective stochastic optimization algorithm. The method leverages probability theory, incorporating a robustness check to identify significant imbalances in the data distribution relative to the mean, and dynamically adjusts the number of runs during execution as an online approach. The proposed methodology was extensively tested across two algorithm portfolios (104 Differential Evolution configurations and the Nevergrad portfolio) and the COCO benchmark suite, totaling 5748000 runs. The results demonstrate 82% - 95% accuracy in estimations across different algorithms, allowing a reduction of approximately 50% in the number of runs without compromising optimization outcomes. This online calculation of required runs not only improves benchmarking efficiency, but also contributes to energy reduction, fostering a more environmentally sustainable computing ecosystem.

Figures

Figures reproduced from arXiv: 2507.01629 by the authors.

Figure 1
Figure 1. The distribution of correctly estimated run percentages across all 104 configurations is presented for a skewness [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. The error bars represent confidence intervals for the percentage of problems per dimension where the estimated runs [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. The percentage of triplets with inaccurate estimations across 104 DE configurations is presented by problem and [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The heatmap shows the percentage of triplets where the proposed method correctly estimates the number of runs, [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 23 canonical work pages

  1. [1]

    Thomas Bartz-Beielstein. 2006. The new experimentalism. Experimental Research in Evolutionary Computation: The New Experimentalism (2006), 13–39

  2. [2]

    Thomas Bartz-Beielstein, Carola Doerr, Daan van den Berg, Jakob Bossek, Sowmya Chandrasekaran, Tome Eftimov, Andreas Fischbach, Pascal Kerschke, William La Cava, Manuel Lopez-Ibanez, et al. 2020. Benchmarking in optimization: Best practice and open issues. arXiv preprint arXiv:2007.03488 (2020)

  3. [3]

    Thomas Bartz-Beielstein and Mike Preuss. 2007. Experimental research in evolutionary computation. In Proceedings of the 9th annual conference companion on genetic and evolutionary computation . 3001–3020

  4. [4]

    Hans-Georg Beyer and Hans-Paul Schwefel. 2002. Evolution strategies – A comprehensive introduction. Natural computing 1 (2002), 3–52. https://doi.org/10.1023/A:1015059928466

  5. [5]

    Felipe Campelo and Fernanda Takahashi. 2019. Sample size estimation for power and accuracy in the experimental comparison of algorithms. Journal of Heuristics 25 (2019), 305–338

  6. [6]

    Felipe Campelo and Elizabeth F Wanner. 2020. Sample size calculations for the experimental comparison of multiple algorithms on multiple problem instances. Journal of Heuristics 26, 6 (2020), 851–883

  7. [7]

    William G Cochran. 1952. The 𝜒2 test of goodness of fit. The Annals of mathematical statistics (1952), 315–345

  8. [8]

    Joaquín Derrac, Salvador García, Daniel Molina, and Francisco Herrera. 2011. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation 1, 1 (2011), 3–18

Show all 31 references
  1. [9]

    Thomas J Diciccio and Joseph P Romano. 1988. A review of bootstrap confidence intervals. Journal of the Royal Statistical Society: Series B (Methodological) 50, 3 (1988), 338–354

  2. [10]

    Richard M Dudley. 1978. Central limit theorems for empirical measures. The Annals of Probability (1978), 899–929

  3. [11]

    Tome Eftimov and Peter Korošec. 2019. Identifying practical significance through statistical comparison of meta-heuristic stochastic optimization algorithms. Applied Soft Computing 85 (2019), 105862

  4. [12]

    Tome Eftimov, Peter Korošec, and Barbara Koroušić Seljak. 2017. A Novel Approach to statistical comparison of meta-heuristic stochastic optimization algorithms using deep statistics. Information Sciences 417 (2017), 186–215

  5. [13]

    Hansen, A

    N. Hansen, A. Auger, R. Ros, O. Mersmann, T. Tušar, and D. Brockhoff. 2021. COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting. Optimization Methods and Software 36 (2021), 114–144. Issue 1. https://doi.org/10.1080/10556788.2020.1808977

  6. [14]

    Nikolaus Hansen, Steffen Finck, Raymond Ros, and Anne Auger. 2009. Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions. Research Report RR-6829. INRIA. https://hal.inria.fr/inria-00362633

  7. [15]

    Nikolaus Hansen and Andreas Ostermeier. 2001. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation 9, 2 (2001), 159–195. https://doi.org/10.1162/106365601750190398

  8. [16]

    K Senthamarai Kannan, K Manoj, and S Arumugam. 2015. Labeling methods for identifying outliers. International Journal of Statistics and Systems 10, 2 (2015), 231–238

  9. [17]

    James Kennedy and Russell Eberhart. 1995. Particle swarm optimization. In Proceedings of International Conference on Neural Networks (ICNN’95), Perth, W A, Australia, November 27 - December 1, 1995. IEEE, 1942–1948. https://doi.org/10.1109/ICNN.1995.488968

  10. [18]

    Ana Kostovska, Anja Jankovci, Diederick Vermetten, Sašo Džeroski, Tome Eftimov, and Carola Doerr. 2023. Comparing Algorithm Selection Approaches on Black-Box Optimization Problems. In Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion. In Press

  11. [19]

    Pedro Larrañaga and José Antonio Lozano (Eds.). 2002. Estimation of Distribution Algorithms . Springer. https://doi.org/10.1007/978-1- 4615-1539-5

  12. [20]

    Jing J Liang, Bo Y Qu, and Ponnuthurai N Suganthan. 2013. Problem definitions and evaluation criteria for the CEC 2014 special session and competition on single objective real-parameter numerical optimization. Technical report Zhengzhou, China 635 (2013), 490

  13. [21]

    Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, and Günter Rudolph. 2011. Exploratory landscape analysis. In Proceedings of the 13th annual conference on Genetic and evolutionary computation . 829–836

  14. [22]

    Laurent Meunier, Herilalaina Rakotoarison, Pak Kan Wong, Baptiste Roziere, Jeremy Rapin, Olivier Teytaud, Antoine Moreau, and Carola Doerr. 2022. Black-box optimization revisited: Improving algorithm selection wizards through massive benchmarking. IEEE Transactions on Evolutio...

  15. [23]

    Andrew Ng. 2022. Unbiggen ai. IEEE Spectrum 9 (2022)

  16. [24]

    Michael JD Powell. 1994. A direct search optimization method that models the objective and constraint functions by linear interpolation . Springer

  17. [25]

    2006.Differential Evolution: A Practical Approach to Global Optimization

    Kenneth Price, Rainer M Storn, and Jouni A Lampinen. 2006.Differential Evolution: A Practical Approach to Global Optimization. Springer Science & Business Media

  18. [26]

    Rapin and O

    J. Rapin and O. Teytaud. 2018. Nevergrad - A gradient-free optimization platform. https://GitHub.com/FacebookResearch/Nevergrad. 12 Adaptive Estimation of the Number of Algorithm Runs in Stochastic Optimization

  19. [27]

    Rainer Storn and Kenneth Price. 1997. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization 11, 4 (1997), 341

  20. [28]

    Niki Veček, Matej Črepinšek, and Marjan Mernik. 2017. On the influence of the number of algorithms, problems, and independent runs in the comparison of evolutionary algorithms. Applied Soft Computing 54 (2017), 23–45

  21. [29]

    Diederick Vermetten, Fabio Caraffini, Anna V Kononova, and Thomas Bäck. 2023. Modular differential evolution. In Proceedings of the Genetic and Evolutionary Computation Conference . 864–872

  22. [30]

    Diederick Vermetten, Hao Wang, Manuel López-Ibañez, Carola Doerr, and Thomas Bäck. 2022. Analyzing the impact of undersampling on the benchmarking and configuration of evolutionary algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference. 867–875

  23. [31]

    Dewey Lonzo Whaley III. 2005. The interquartile range: Theory and estimation . Ph. D. Dissertation. East Tennessee State University. 13

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.