{"id":"ce59df19-b7a7-4273-ac69-4da3c0d9471c","arxiv_id":"1908.01720","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A method for computing the required number of instances and per-instance runs when comparing multiple algorithms, based on pairwise effect sizes, power, and Holm-corrected error rates.","lead":"This paper gives formulas and an R package for deciding how many test problems and how many repeated runs are needed when comparing several optimization algorithms. It extends the authors' earlier two-algorithm method to any number of algorithms, using Holm-corrected significance levels and adjustable power targets.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2's mean-power planning is unvalidated: under Holm, the threshold applied to a comparison depends on p-value rank, so averaging per-comparison powers at fixed α/i may not equal the achieved mean power.","rationale":"The reader's weakest_assumption is exactly the load-bearing point I would stress: Algorithm 2 computes the number of instances by averaging the per-comparison power functions at the fixed Holm significance levels, without establishing that this average equals the mean rejection probability of the actual step-down procedure. This matters because the abstract and Section 4 advertise mean-power as one of the supported design modes, and the case study uses it to justify N = 57. A wrong or optimistic approximation here would directly under-size the experiment. The concern is not merely that the approximation is unproven; there is a structural reason to doubt it: under Holm, which threshold applies to a comparison depends on the joint ordering of all K p-values, and that ordering changes when some nulls are true or effect sizes are heterogeneous. The paper offers neither a proof nor a simulation check, and the case study cannot validate the approximation because it reports only the realized configuration, not repeated-sampling power. I do not see a reason to move the verdict: the reader already marked the paper CONDITIONAL on this basis, and the other contributions — the worst-case instance-count formulas and the greedy per-instance sampling rule — appear to stand independently. A simulation of the actual Holm procedure, as described in concrete_test, would settle whether the mean-power mode is reliable.","tokens_in":23213,"tokens_out":17706,"duration_ms":174587,"concrete_test":"Simulate the full Holm procedure under the design used in Section 5/Figure 2: e.g., K = 21 paired comparisons, N = 57, d* = 0.5, α_f = 0.05, two-sided paired t-tests on Gaussian instance-level differences. Generate 10,000 experiments (a) with all 21 comparisons at effect d*, and (b) with, say, 10 comparisons at d* and 11 under H0; for each experiment run Holm's step-down procedure and record all rejection indicators. Compare the empirical mean rejection rate (over all comparisons in case (a), or over the false comparisons in case (b)) against the nominal π* = 0.8. If the empirical rate is materially below π*, Algorithm 2's averaging approximation is invalid. Repeat using the N actually returned by Algorithm 2 for each scenario to test the sizing rule itself.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4 recommends designing experiments for 'mean power' using Algorithm 2, whose stopping condition averages Power(α/i, N, d*, H1) over i = 1..K. This treats the K Holm thresholds as if each comparison were equally likely to be tested at each threshold. Under Holm (Eq. 39), however, the threshold applied to a given comparison is determined by the rank of its p-value among all K tests. The rank of a false comparison is not uniform once some null hypotheses are true or effect sizes differ: a signal p-value tends to be smaller, so it is more often tested at the stricter thresholds (small i). The paper provides no proof or simulation that the achieved mean rejection probability equals this average, and the case study does not verify it — it only reports realized p-values and confidence intervals for one dataset. If the approximation is optimistic, the N returned by Algorithm 2 is too small and the claimed 'mean power' design target is not met. The worst-case (Bonferroni) formulas and the per-instance run allocation do not depend on this approximation, so the paper's other contributions are not affected by this concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper generalizes the authors' earlier sample-size methodology from two algorithms to an arbitrary number. The number of repeated runs per instance is framed as a constrained minimization problem on the standard errors of estimated paired differences; the authors derive optimal sample-size ratios for simple differences and for percent differences under all-vs-one and all-vs-all comparisons, and give a greedy sampling algorithm (Algorithm 1). The number of instances is derived from a paired-t-test power calculation (Eq. 38), with significance levels corrected by either Bonferroni or Holm. For Holm's procedure they propose worst-case, mean-power, and median-power planning modes (Algorithm 2), and they illustrate the whole protocol on a 22-algorithm comparison of simulated-annealing variants on a scheduling benchmark. The main advertised advances are the multi-algorithm generalization, the Holm-based instance-number formulas, and the per-instance run-allocation ratios.","tokens_in":23487,"tokens_out":15195,"duration_ms":163453,"significance":"If the proposed formulas are valid, the paper supplies a practical and much-needed alternative to arbitrary choices of instance counts and repetition numbers in metaheuristic comparisons. The worst-case (Bonferroni) instance-size formulas are standard and correctly applied, and the derivations of the per-instance optimal ratios are carefully executed for the three difference types. The accompanying R package and the realistic case study are valuable. The principal weakness is that the recommended mean-power mode for Holm's procedure rests on an unvalidated approximation of the achieved rejection rate, so the central claim about this design mode is not yet established.","major_comments":[{"comment":"The mean-power planning in Algorithm 2 averages Power(α/i, N, d*, H1) over i = 1,...,K, treating the Holm thresholds as fixed quantities assigned to comparisons. In the actual Holm procedure, the threshold available to a comparison depends on the rank of its p-value among all K tests, and that rank is random and correlated with the p-value itself; for example, with K = 2 independent tests under the global null, the average of the fixed thresholds is 3α/4, whereas the expected per-test rejection rate under Holm is α/2 + 3α^2/8. The paper provides no proof or simulation that the achieved mean rejection probability equals the averaged quantity when some alternatives are true or effect sizes vary, and Figure 2 is generated from the same approximation, so it cannot serve as evidence. The case study in Section 5.4 reports realized p-values and confidence intervals but not achieved power, so it also does not validate the approximation. Because Section 4 recommends mean power as the preferred design target, this gap is load-bearing; please provide either an analytic justification under stated conditions or a simulation study covering equal and unequal effect sizes, and revise the corresponding claims if the approximation is optimistic.","section":"Section 4, Algorithm 2; Eq. (39)"},{"comment":"The text states that if Algorithm 1 is interrupted by the computational budget, 'the resulting standard errors of estimation will be the smallest ones achievable.' This global optimality claim is not established: the greedy rule of augmenting the algorithm that contributes most to the current maximal standard error does not in general imply that the realized standard-error vector is minimal for the total number of runs used, because early choices constrain later possibilities. The procedure is a reasonable heuristic for reducing the worst-case standard error, but the claim should either be proved or weakened to say that the procedure is designed to reduce the worst-case standard error. This secondary issue does not affect the derivation of the pairwise sample-size ratios, but it is directly tied to the optimality language used to motivate Algorithm 1.","section":"Section 3, Algorithm 1 and text following Eq. (13)"}],"minor_comments":[{"comment":"Holm's thresholds become less strict as r increases, since α'_r = α/(K - r + 1) grows with r; the phrase 'increasingly stricter significance level' is therefore inverted and should be corrected.","section":"Section 4, paragraph after Eq. (39)"},{"comment":"The sentence 'an all vs. one design was be the most appropriate' contains a grammatical error and should read 'was the most appropriate.'","section":"Section 5.2"},{"comment":"The lower-bound constraints n_k|ℓ ≥ 2 are mentioned only in the prose; include them in the displayed formulation or explicitly state that they are implicit.","section":"Section 3.1, Eq. (13)"},{"comment":"The inserted row 'Stop rejecting H0' is informal; use a conventional separation, such as a rule or boldfaced boundary, and state clearly that all comparisons below the line are not rejected.","section":"Table 1"},{"comment":"The text says CAISEr version 1.0.5 was used, while reference [14] lists version 1.0.13; please make these consistent.","section":"Section 5.3 vs. reference [14]"},{"comment":"The pseudocode does not state explicitly that all K comparisons are assumed to be under the alternative with effect size d*; this assumption should be written into the algorithm's contract.","section":"Section 4, Algorithm 2"},{"comment":"The figure is extremely dense and the instance labels are difficult to read; consider faceting by instance size or using a rotated, smaller set of labels.","section":"Figure 3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the scope of a methodology-oriented heuristics journal. The mean-power issue is correctable in principle, but because it affects a prominently advertised design mode, it should be addressed with either simulation evidence or appropriately weakened claims before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The key thing to know: this paper gives algorithm researchers a principled way to size multi-algorithm comparisons, generalizing the authors' earlier two-algorithm results to an arbitrary number A, with Holm correction for multiple tests. It also ships a working R package (CAISEr) and the formulas are mostly standard power analysis, applied carefully. If you design experiments that compare several algorithms on a problem class, this is worth reading.\n\nWhat's actually new: the all-vs-all and all-vs-one treatment for A>2, the optimal sample-size ratios for simple and percent differences (including the all-vs-all percent-difference case, where the derivation correctly accounts for the grand-mean term and the coupling terms cancel in the KKT conditions), and the greedy per-instance sampling heuristic in Algorithm 1. The worst-case (Bonferroni) instance-count formulas are exactly what you'd expect and are correct. The case study with 21 simulated-annealing variants is honest and illustrates the workflow, though it is not itself a validation of the power approximations.\n\nThe soft spot is Algorithm 2, the 'mean power' planning mode. The paper computes the required N by averaging per-comparison powers Power(α/i, N, d*, H1) over i=1..K, treating the Holm thresholds as fixed. Under Holm, the threshold a given comparison actually gets depends on the rank of its p-value, which is random and depends on which nulls are true and on effect sizes. The paper gives no proof or simulation that the achieved mean rejection probability equals this average. If the approximation is optimistic, the N returned by Algorithm 2 can be too small. This is a real limitation, but it is contained: the Bonferroni/worst-case formulas and Algorithm 1's per-instance sampling do not rely on it. So the paper's central contributions are not undermined; the mean-power mode just needs a simulation check or a more careful analytic argument before it should be used with confidence.\n\nThe citation pattern looks fine: the prior work [15] is cited where the two-algorithm results come from, and Holm's procedure is attributed properly. No evidence of fabrication or p-hacking; the data and code are available.\n\nThis is a solid methodological paper for people doing experimental algorithm comparison. It deserves a serious referee. I'd recommend accepting it for peer review, with the expectation that the authors add a small simulation study verifying the achieved mean power under Holm before publication. Without that, the mean-power algorithm should be flagged as provisional.","headline":"A genuinely useful extension of the two-algorithm sample-size machinery to arbitrary A, with real software; the main soft spot is the unvalidated mean-power approximation in Algorithm 2.","tokens_in":23965,"tokens_out":1652,"would_cite":true,"duration_ms":18217,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F03","62K10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows how to choose the number of instances and the number of runs per instance for comparing any number of algorithms, with controlled error rates and prespecified power to detect a minimally relevant difference.","keywords":["sample size calculation","experimental comparison of algorithms","Holm step-down procedure","familywise error rate","statistical power","minimally relevant effect size","paired differences","benchmark instances"],"falsifier":"Run a Monte Carlo simulation of the designed experiment: generate $A$ algorithms on $N$ instances with all pairwise standardised differences exactly $d^*$ (and also with only some pairs differing and the rest null), apply Holm's step-down procedure, and compare the empirical mean, best, and worst rejection power across many repetitions to the values predicted by Equation (38) and Algorithm 2. A systematic shortfall would show that the recommended instance count is miscalibrated in mean-power mode.","tokens_in":22992,"feed_emoji":"📊","tokens_out":9676,"duration_ms":98010,"temperature":0.7,"pith_summary":"Experimental comparisons of stochastic algorithms need two sample sizes: the number of problem instances and the number of repeated runs per algorithm per instance. This paper claims that both can be planned in advance, for any number of algorithms, from two user-chosen targets: a minimally relevant standardised difference $d^*$ and a desired statistical power for detecting it, together with a controlled familywise error rate. The instance count comes from a noncentral $t$ power calculation with Holm-corrected significance levels, so an experiment can be sized for best-, worst-, mean-, or median-case power across the planned pairwise tests. The run count comes from a greedy per-instance allocation that drives every pairwise standard error below a chosen threshold $se^*$, using optimal sample-size ratios derived for simple and percent differences. A sympathetic reader would care because this replaces the common practices of using as many instances as budget allows and an arbitrary 30 or 50 runs with quantities that have a stated statistical meaning.","feed_headline":"Sizing multi-algorithm experiments by power and effect size","feed_subtitle":"Holm-corrected power calculations pick the instance count; a greedy rule sets per-instance runs to a chosen accuracy.","key_machinery":"Minimally relevant effect size (MRES), $d^*=|\\delta^*|/\\sigma$, the smallest standardised mean paired difference judged practically relevant, anchors both the power calculation and the interpretation of detected effects. Holm's step-down procedure assigns significance level $\\alpha'_r=\\alpha_f/(K-r+1)$ to the $r$-th ordered hypothesis, controlling the familywise error rate while being less conservative than Bonferroni; the paper uses these levels in the instance-count calculation. The instance-count engine is Equation (38), a noncentral $t$ power formula with noncentrality $|d^*|\\sqrt{N}$, together with Algorithm 2, which finds $N$ by averaging per-comparison powers. The run-count engine is Algorithm 1, a greedy allocation that reduces the worst pairwise standard error on each instance subject to $se^*$, using the optimal ratios $n_i/n_j=\\sigma_i/\\sigma_j$ and $n_1/n_j=(\\sigma_1/\\mu_1)/(\\sigma_j/\\mu_j)$ to decide which algorithm receives the next run.","core_discovery":"The paper establishes that the comparison of $A$ algorithms over a problem class can be planned as a set of paired comparisons on instance-blocked differences, and that the required number of instances $N$ is the smallest integer satisfying the noncentral $t$ condition $t_{N-1}^{1-\\alpha/2}\\le t_{N-1}^{\\beta^*;|ncp^*|}$ with $|ncp^*|=|d^*|\\sqrt{N}$, where the significance level is corrected by Holm's step-down procedure. For the least-favourable comparison this correction is $\\alpha_f/K$; for mean-power design, the paper's Algorithm 2 iterates $N$ until the average of per-comparison powers $\\mathrm{Power}(\\alpha/i, N, d^*, H_1)$ reaches $\\pi^*$. Within each instance, the number of runs is the solution of a constrained minimization: the smallest total runs such that every pairwise standard error $se_{(ij)|\\ell}^2\\le(se^*)^2$. The paper derives optimal allocation ratios $n_i/n_j=\\sigma_i/\\sigma_j$ for simple differences and for all-vs-all percent differences, and $n_1/n_j=(\\sigma_1/\\mu_1)/(\\sigma_j/\\mu_j)$ for all-vs-one percent differences, and embeds them in a greedy algorithm that allocates the next run to the algorithm most responsible for the current worst standard error. The case study with 21 variants of a simulated-annealing scheduler demonstrates that the instance count (57 in that experiment) and per-instance run counts determined this way deliver the planned power and controlled standard errors.","pith_inferences":["A natural extension, not explored in the paper, would replace the single $d^*$ with a distribution of effect sizes across pairs or instance subclasses; the same noncentral-$t$ machinery could then be integrated over that distribution to size experiments under heterogeneity.","The mean-power shortcut in Algorithm 2 ignores the dependence among Holm-ordered $p$-values and the possibility that some null hypotheses are true; a Monte Carlo calibration across those scenarios would state how much the realised power can deviate from $\\pi^*$.","The optimal-run ratios are derived per pair and ignore correlations among comparisons that share the reference algorithm or the grand mean; a joint allocation rule could in principle beat the greedy rule in total runs when such correlations are strong.","Because the method can reserve unused benchmark instances, it offers a practical guard against tuning a heuristic to a fixed benchmark set; this suggests a testable protocol where held-out instances, not just held-out runs, are used to validate algorithm-design choices."],"forward_implications":["An experimenter who fixes $d^*$, $\\pi^*$, and $\\alpha_f$ can compute the minimum number of instances directly, instead of using the entire benchmark set or an arbitrary default.","Because Holm's procedure is less conservative than Bonferroni, designing for mean power yields a smaller $N$ than the Bonferroni-equivalent design, while the worst-case power stays close to $\\pi^*$ in the paper's examples.","For a fixed available set of instances, the same formulas give a power-versus-effect-size curve, so researchers can report the sensitivity their chosen benchmark set actually provides.","The per-instance run allocation guarantees, up to the computational budget, that all pairwise estimates meet the chosen accuracy $se^*$, which keeps estimation noise from inflating the residual variance used in the paired tests.","All-vs-one and one-sided designs are systematically cheaper than all-vs-all and two-sided designs, since they create fewer and less heavily corrected hypotheses."],"supporting_citations":[{"why":"The two-algorithm version of this method, whose instance-count formula and per-instance standard-error criterion the paper generalises to $A$ algorithms.","marker":"[15]"},{"why":"Holm's step-down procedure, whose sequential significance levels control the familywise error rate and define the correction used in the instance-count calculation.","marker":"[34]"},{"why":"Review of multiple-hypothesis testing that justifies controlling FWER and describes Holm's method as uniformly more powerful than Bonferroni.","marker":"[55]"},{"why":"Fieller's interval-estimation results used to derive the standard error of percent differences of means.","marker":"[26]"},{"why":"Practical guide to ratio standard errors, used alongside Fieller's result for the percent-difference formulas.","marker":"[27]"},{"why":"The simulated-annealing method whose 21 variants form the case study; supplies the algorithms and performance data.","marker":"[54]"},{"why":"Provides the unrelated-parallel-machine benchmark instances and problem class used to demonstrate the sample-size rules.","marker":"[58]"},{"why":"Earlier analysis of how many instances and runs to use, which the paper extends by adding power and effect-size targets.","marker":"[9]"},{"why":"Prior discussion of power curves and sample size in nested linear models, which the paper generalises beyond nested models.","marker":"[7]"}],"fun_headline_variants":["Holm-corrected power sizes algorithm comparison studies","How many instances to compare algorithms? New stats answer","Optimal run allocation for multi-algorithm experiments","Power-based sample sizes for benchmarking algorithms","Plan algorithm experiments with Holm-corrected power"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the planned mean power of a Holm-corrected experiment is well approximated by the average of per-comparison powers computed at fixed thresholds $\\alpha/i$ ($i=1,\\dots,K$) with every comparison at effect size $d^*$; actual Holm thresholds are assigned to ordered, dependent $p$-values, so the realised mean power can differ from the planned $\\pi^*$.","fun_headline_variants_meta":{"raw":{"variants":["Holm-corrected power sizes algorithm comparison studies","How many instances to compare algorithms? New stats answer","Optimal run allocation for multi-algorithm experiments","Power-based sample sizes for benchmarking algorithms","Plan algorithm experiments with Holm-corrected power"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000275,"raw_usage":{"total_tokens":1689,"prompt_tokens":1037,"completion_tokens":652,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":653,"completion_tokens_details":{"reasoning_tokens":581}},"tokens_in":653,"tokens_out":652,"duration_ms":7497,"temperature":1.0,"reasoning_tokens":581,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:05:55.931936+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a Monte Carlo simulation of the designed experiment: generate $A$ algorithms on $N$ instances with all pairwise standardised differences exactly $d^*$ (and also with only some pairs differing and the rest null), apply Holm's step-down procedure, and compare the empirical mean, best, and worst rejection power across many repetitions to the values predicted by Equation (38) and Algorithm 2. A systematic shortfall would show that the recommended instance count is miscalibrated in mean-power mode.","supporting_citations":[{"cited_title":"Journal of Heuristics25(2), 305–338 (2019)","cited_arxiv_id":null,"evidence_quote":"The two-algorithm version of this method, whose instance-count formula and per-instance standard-error criterion the paper generalises to $A$ algorithms."},{"cited_title":"Scandinavian journal of statistics 6(2), 65–70 (1979)","cited_arxiv_id":null,"evidence_quote":"Holm's step-down procedure, whose sequential significance levels control the familywise error rate and define the correction used in the instance-count calculation."},{"cited_title":"Annual review of psychology46(1), 561–584 (1995)","cited_arxiv_id":null,"evidence_quote":"Review of multiple-hypothesis testing that justifies controlling FWER and describes Holm's method as uniformly more powerful than Bonferroni."},{"cited_title":"Journal of the Royal Statistical Society","cited_arxiv_id":null,"evidence_quote":"Fieller's interval-estimation results used to derive the standard error of percent differences of means."},{"cited_title":"Ratios: A short guide to confidence limits and proper use","cited_arxiv_id":"0710.2024","evidence_quote":"Practical guide to ratio standard errors, used alongside Fieller's result for the percent-difference formulas."},{"cited_title":"International Transactions in Operational Research00 (2016)","cited_arxiv_id":null,"evidence_quote":"The simulated-annealing method whose 21 variants form the case study; supplies the algorithms and performance data."},{"cited_title":"European Journal of Operational Research211(3), 612–622 (2011)","cited_arxiv_id":null,"evidence_quote":"Provides the unrelated-parallel-machine benchmark instances and problem class used to demonstrate the sample-size rules."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Earlier analysis of how many instances and runs to use, which the paper extends by adding power and effect-size targets."},{"cited_title":"Springer (2010)","cited_arxiv_id":null,"evidence_quote":"Prior discussion of power curves and sample size in nested linear models, which the paper generalises beyond nested models."}],"review_version":1}