Boldyrev, Ratnikov and Shevelev (2025) proposed an empirical protocol for finding robust deep learning models: train many independently initialized instances of each candidate model on random training subsamples, measure robustness by a statistical criterion (mean, median, minimum, maximum, or more generally a quantile of the instance losses), and feed the criterion into an iterative elimination meta-algorithm that finds robust models with about 8 times fewer trainings than exhaustive repeated evaluation. The paper's own conclusion leaves the central theoretical question open: it is unknown which selection criteria allow the algorithm to select a model with guaranteed robustness, and how many training repetitions any such guarantee requires. The source-faithful core of the question is: construct selection criteria for the elimination algorithm that carry explicit probabilistic guarantees on the selected model's instance-loss distribution (for example, a bound on its high-quantile or worst-case loss that is not vacuously satisfied by every candidate configuration), bound the number of training runs needed as a function of the candidate set size and target confidence, and delimit which criteria in the source's family admit finite-sample guarantees at all. Adjacent quantile best-arm-identification results supply a toolbox but do not analyze this protocol.

Background

In supervised deep learning, model quality is conventionally reported from a single training run, yet the loss achieved by a fixed architecture-and-hyperparameter configuration is a random variable: random weight initialization and the random draw of the training subsample both influence the outcome. Boldyrev, Ratnikov and Shevelev (2025), motivated by fast-simulation regression tasks for particle detectors (a calorimeter measures particle energies, and their networks emulate its response on simulated data), call a model robust when the losses of its independently trained instances show low variability, and they measure robustness by training many instances of the same configuration and applying a statistical criterion — mean, median, minimum, maximum, or more generally a quantile — to the set of instance losses.

Their model-selection meta-algorithm (Algorithm 1 of the paper) works as follows. Start from a set MM of candidate configurations (in their experiments, 6,912 small convolutional neural networks with at most about 24,000 trainable parameters). At each step, train one new instance of every surviving configuration (fresh random initialization, fresh random training subsample) and update each configuration's robustness value from all its observed instance losses; once each surviving configuration has accumulated a warm-up number of instances, eliminate the configurations whose robustness is worse than the current criterion value, so the set shrinks until one model remains. In their experiments the criterion was the mean loss, and at each of 12 iterations the half of the surviving models with the highest mean loss was discarded. This is structurally a racing or successive-halving scheme — the classic budget-allocation approach that repeatedly gives every surviving candidate a little more resource and eliminates the worst half, introduced for hyperparameter optimization by Jamieson and Talwalkar (2015) and popularized by Hyperband (Li et al. 2016). Empirically, their schedule found robust models for two calorimeter regression tasks with 41,567 training runs instead of the 345,600 that exhaustive evaluation (50 instances of each of the 6,912 models) would require, and a neural architecture search built on Optuna (a hyperparameter-optimization library; NAS, the automated search over network architectures) produced models with comparable best-case losses but higher loss variability. Notably, the paper motivates this budget comparison by an exhaustive search 'with the same robustness guarantee' — yet no guarantee is defined anywhere; all criteria, thresholds, and repetition counts are purely empirical (boxplots over 50–1,000 instances). That the underlying run-to-run variability is real and consequential in automated model search is independently documented by Li and Talwalkar (2019), who showed random-seed variance undermining NAS evaluation rankings.

A formal guarantee for such a criterion has the shape of best-arm identification theory from multi-armed bandits: each candidate configuration is an arm, each training run draws one sample from that configuration's loss distribution, and one asks for a δ\delta-PAC algorithm — one that, with overall probability at least 1−δ1-\delta, returns a configuration whose loss distribution satisfies a stated property — together with a sample-complexity bound on the number of runs. For mean-type criteria this theory is classical (successive elimination and racing). For quantile-type criteria it has been worked out recently: Nikolakakis et al. (2020) give a δ\delta-PAC successive-elimination algorithm that identifies the arm with the highest quantile at a prescribed level, with essentially matching upper and lower sample-complexity bounds, and Zhang and Ong (2020) analyze a quantile version of Successive Accepts and Rejects (SAR, a fixed-budget best-arm-identification scheme that in each round accepts the apparently best and rejects the apparently worst arms) with misidentification-probability bounds under non-decreasing hazard-rate assumptions on the arm distributions. What this adjacent literature does not treat: the specific interleaved schedule and criterion family of the source protocol, run losses induced jointly by weight initialization and training-subsample draws under a cost model where every sample is a full training run, guarantees (or impossibility) for the worst-case maximum-loss criterion, and the conversion of the empirical budget saving of elimination over exhaustive evaluation into a proven sample-complexity statement.

Problem Statement

For the iterative model-selection algorithm of Boldyrev, Ratnikov and Shevelev (2025) — which maintains a set of candidate model configurations, trains one new instance of every surviving configuration per step (random weight initialization and random training subsample), and eliminates configurations by a statistical criterion computed from the accumulated instance losses — construct and delimit selection criteria with formal guarantees:

(1) Guaranteed criterion. Give a criterion, together with any needed modification of the elimination rule that preserves the protocol's structure (one new instance of every surviving configuration per step, elimination by a statistical criterion computed from the accumulated instance losses; since the source leaves the elimination threshold implicit, the threshold rule analyzed must be stated explicitly), for which the algorithm provably outputs a model whose loss distribution over independent training runs satisfies an explicit robustness property — for example Pr⁡[instance loss≤θ]≥1−ε\Pr[\text{instance loss} \le \theta] \ge 1-\varepsilon for stated θ\theta and ε\varepsilon — with overall confidence 1−δ1-\delta, under explicitly stated assumptions on the run-loss distributions. The guarantee must be nontrivial: the source itself notes that robustness alone is achievable vacuously (in its words, 'a constant model will be robust because all its instances predict the same constant') and couples the algorithm's purpose to selecting robust models among the top-performing ones. Accordingly, the certified property must not be one that every configuration satisfies regardless of quality; the guarantee must hold for target parameters θ\theta, ε\varepsilon, δ\delta that can be tightened within a stated non-degenerate range (with the required run budget growing as they tighten) rather than for a single fixed vacuous choice; and the certified robustness must be tied to the competitiveness of the selected configuration within the candidate set, with that competitiveness condition stated explicitly and in checkable form — for example, as a bound or near-optimality relation between the selected configuration's criterion value and the best value attainable over the candidate set — in line with the source's stated purpose.

(2) Sample complexity. Bound the number of training runs the algorithm requires as a function of the number of candidate configurations nn, the target parameters ε\varepsilon and δ\delta, and properties of the loss distributions; in particular, characterize when elimination-based selection achieves the guarantee with asymptotically fewer runs than training a fixed number of instances of every configuration, as the empirical 41,567-versus-345,600 comparison suggests.

(3) Delimitation. Determine which criteria in the source's family (the paper lists mean, median, minimum, maximum, and 'etc.'; quantiles are the natural generalization) admit finite-sample guarantees without distributional assumptions — in particular, whether any finite number of repetitions can bound the worst-case (maximum) instance loss — and establish lower bounds showing when the required number of repetitions is unavoidable.

References

  1. Alexey Boldyrev, Fedor Ratnikov, Andrey Shevelev, 'Approach to Finding a Robust Deep Learning Model' (2025), arXiv:2505.17254, DOI 10.48550/arXiv.2505.17254, https://arxiv.org/abs/2505.17254
  2. Kevin Jamieson, Ameet Talwalkar, 'Non-stochastic Best Arm Identification and Hyperparameter Optimization' (2015), arXiv:1502.07943, DOI 10.48550/arXiv.1502.07943, https://arxiv.org/abs/1502.07943
  3. Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, Ameet Talwalkar, 'Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization' (2016), arXiv:1603.06560, DOI 10.48550/arXiv.1603.06560, https://arxiv.org/abs/1603.06560
  4. Kontantinos E. Nikolakakis, Dionysios S. Kalogerias, Or Sheffet, Anand D. Sarwate, 'Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme' (2020), arXiv:2006.06792, DOI 10.48550/arXiv.2006.06792, https://arxiv.org/abs/2006.06792
  5. Mengyan Zhang, Cheng Soon Ong, 'Quantile Bandits for Best Arms Identification' (2020), arXiv:2010.11568, DOI 10.48550/arXiv.2010.11568, https://arxiv.org/abs/2010.11568
  6. Liam Li, Ameet Talwalkar, 'Random Search and Reproducibility for Neural Architecture Search' (2019), arXiv:1902.07638, DOI 10.48550/arXiv.1902.07638, https://arxiv.org/abs/1902.07638
  7. G. V. Petushkov, 'Organization and study of cluster computing systems with functional architecture determined by executable models. Automata executable models of information processing' (2025), DOI 10.32362/2500-316x-2025-13-6-7-24, https://doi.org/10.32362/2500-316x-2025-13-6-7-24
  8. Hugh E. Ferguson, Carl D. Herickhoff, Ann M. Viano, Brent K. Hoffmeister, 'Evaluating bone density with ultrasonic backscatter: Leveraging time-frequency analyses and convolutional neural networks' (2026), DOI 10.1016/j.ultras.2025.107845, https://doi.org/10.1016/j.ultras.2025.107845