arXiv:2606.25601v1 [stat.ML] 24 Jun 2026
Statistically Valid Hyperparameter Selection From Tuning to Guarantees
Amirmohammad Farzaneh Osvaldo Simeone Institute for Intelligent Networked Systems (INSI) Northeastern University London {a.farzaneh, o.simeone}@nulondon.ac.uk
Contents 1 Reliable Hyperparameter Selection 1 1.1 Hyperparameter Selection in Modern AI Systems . . . . . . . 1 1.1.1 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Limitations of Best-Effort Tuning Methods . . . . . . . . . . . 4 1.2.1 Optimization-Centric Hyperparameter Selection . . . . 5 1.2.2 Lack of Reliability and Post-Selection Guarantees . . . 6 1.3 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.1 Hyperparameter Selection Domain . . . . . . . . . . . 8 1.3.2 Reliability Requirements . . . . . . . . . . . . . . . . . 8 1.4 Summary of Notation and Acronyms . . . . . . . . . . . . . . 10 1.5 Scope and Organization of the Monograph . . . . . . . . . . . 13 2 Hyperparameter Selection via Multiple Hypothesis Testing 2.1 Risk Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Multiple Hypothesis Testing . . . . . . . . . . . . . . . . . . . 2.3 Risk Control via Multiple Hypothesis Testing . . . . . . . . . 2.4 P-values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 P-values for Single-Hypothesis Testing . . . . . . . . . 2.4.3 P-values in MHT . . . . . . . . . . . . . . . . . . . . . 2.5 E-values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Construction . . . . . . . . . . . . . . . . . . . . . . . 2.5.3 E-values for Single-Hypothesis Testing . . . . . . . . . 2.5.4 Properties . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.5 E-values for MHT . . . . . . . . . . . . . . . . . . . . . 2.6 False Discovery Rate Control . . . . . . . . . . . . . . . . . . 1
16 17 18 22 24 24 27 28 30 30 31 33 34 35 36
2.7
2.6.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.2 FDR Control via P-values . . . . . . . . . . . . . . . . 2.6.3 FDR Control via E-values . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36 37 39 39
3 Applications 42 3.1 Image Classification . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2 Wireless Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 44 4 Beyond Average Risk 4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 General Reliability Functionals . . . . . . . . . . . . . . . . . 4.3 Confidence Bounds and Inversion-Based Testing . . . . . . . . 4.4 Quantile Risk Control . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Quantile Risk . . . . . . . . . . . . . . . . . . . . . . . 4.4.2 Confidence Bound and P-value for the Quantile Risk . 4.4.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Information-Theoretic Constraints . . . . . . . . . . . . . . . . 4.5.1 The Information Bottleneck Problem . . . . . . . . . . 4.5.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48 48 49 50 51 52 52 53 54 54 56 57
5 Multi-Objective Hyperparameter Selection 5.1 Multi-Objective Problem Formulation . . . . . . . . . . . . . . 5.2 Pareto Optimality and the Pareto Frontier . . . . . . . . . . . 5.3 Multi-Objective Hypothesis Testing . . . . . . . . . . . . . . . 5.4 Pareto Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 Statistical Guarantee . . . . . . . . . . . . . . . . . . . 5.4.3 Example: Multi-Objective Wireless Scheduling . . . . . 5.5 Reliability Graph-Based Pareto Testing . . . . . . . . . . . . . 5.5.1 Example: Reliable Prompt Engineering via RG-PT . . 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59 60 62 63 64 65 66 67 69 72 74
6 Adaptive and Sequential Hyperparameter Selection 6.1 Sequential Hyperparameter Selection . . . . . . . . . . . . . . 6.2 E-Processes and Anytime-Valid Inference . . . . . . . . . . . . 6.2.1 E-Processes . . . . . . . . . . . . . . . . . . . . . . . .
76 78 80 81
2
6.3
6.4 6.5
6.2.2 Betting Strategies . . . . . . . . . . . . . . . . . . . . . 6.2.3 Anytime-Valid P-values . . . . . . . . . . . . . . . . . Adaptive Learn-Then-Test . . . . . . . . . . . . . . . . . . . . 6.3.1 Algorithm Description . . . . . . . . . . . . . . . . . . 6.3.2 Acquisition Policies . . . . . . . . . . . . . . . . . . . . 6.3.3 Statistical Guarantees . . . . . . . . . . . . . . . . . . Example: Adaptive Wireless Scheduling . . . . . . . . . . . . 6.4.1 Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82 83 84 84 84 86 86 87 87 89
7 Hyperparameter Selection with Autoevaluation 90 7.1 The Autoevaluation Setting . . . . . . . . . . . . . . . . . . . 91 7.2 Reliable Evaluation with Real Data . . . . . . . . . . . . . . . 93 7.3 Bias-Corrected Evaluation via PPI . . . . . . . . . . . . . . . 94 7.4 Adaptive Autoevaluation (R-AutoEval+) . . . . . . . . . . . . 96 7.5 Example: Adaptive Autoevaluation for Wireless Scheduling . . 99 7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 8 Outlook and Future Work 104 8.1 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 8.2 Open Problems and Research Opportunities . . . . . . . . . . 105 Acknowledgements
107
A How to Measure Evidence 108 A.1 Evidence via Hypothesis Testing . . . . . . . . . . . . . . . . . 108 A.1.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 109 A.1.2 Setting Up the Hypotheses . . . . . . . . . . . . . . . . 110 A.1.3 Measures of Evidence . . . . . . . . . . . . . . . . . . . 112 A.2 P-values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 A.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 113 A.2.2 Rank P-value . . . . . . . . . . . . . . . . . . . . . . . 115 A.2.3 Power . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 A.2.4 Summary Statistics . . . . . . . . . . . . . . . . . . . . 117 A.2.5 Constructing P-values Using the Probability Integral Transform . . . . . . . . . . . . . . . . . . . . . . . . . 118 A.2.6 Constructing P-values Using Concentration Bounds . . 119 3
A.3 Limitations of P-values . . . . . . . . . . . . . . . . . . . . . . 120 A.3.1 No Anytime Validity . . . . . . . . . . . . . . . . . . . 120 A.3.2 No Compositional Validity . . . . . . . . . . . . . . . . 121 A.4 E-values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 A.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 121 A.4.2 P-values from E-values . . . . . . . . . . . . . . . . . . 123 A.5 Properties of E-values . . . . . . . . . . . . . . . . . . . . . . 124 A.5.1 Post-Hoc Validity . . . . . . . . . . . . . . . . . . . . . 124 A.5.2 Compositional Validity . . . . . . . . . . . . . . . . . . 126 A.5.3 Anytime Validity and E-processes . . . . . . . . . . . . 126 B P-value and E-value Constructions 129 B.1 Alternative Construction of P-values and E-values . . . . . . . 129 B.2 Proof of Validity for the Hoeffding P-value . . . . . . . . . . . 131 B.3 Refined Finite-Sample P-values for Bounded Losses . . . . . . 132 B.3.1 Exact Binomial P-values for 0–1 Losses . . . . . . . . . 132 B.3.2 Variance-Sensitive P-values . . . . . . . . . . . . . . . 132 B.3.3 The Cramér–Chernoff Method . . . . . . . . . . . . . . 133 C Additional Multiple Testing Procedures 134 C.1 Additional FWER-Controlling Procedures . . . . . . . . . . . 134 C.2 Validity of the e-BH Procedure . . . . . . . . . . . . . . . . . 135 References
137
4
Abstract Hyperparameter selection is a critical step in the deployment of modern artificial intelligence systems, given the need to tune degrees of freedom such as inference-time parameters, implementation-level settings, and thresholds driving decision rules. Despite its practical importance, hyperparameter selection is typically performed using best-effort empirical methods such as grid search or Bayesian optimization, which provide no formal statistical guarantees on reliability or safety. This monograph presents a unified statistical framework for reliable hyperparameter selection, centered on the learn-then-test (LTT) paradigm, which formulates the problem as multiple hypothesis testing over a candidate set of hyperparameters. The framework enables the selection of hyperparameters that provably satisfy application-specific reliability requirements—such as bounds on average risk, quantile risk, or information-theoretic constraints— with explicit, finite-sample control of error probabilities. The supporting statistical machinery, namely p-values, e-values, and concentration inequalities, is developed from first principles in a dedicated appendix. Starting from the core LTT methodology, the monograph progressively broadens the framework along four directions. First, it extends LTT beyond average risk to general reliability functionals, including quantile risk control and information-bottleneck constraints. Second, it addresses multiobjective settings where several reliability constraints must be enforced simultaneously, developing Pareto testing and reliability graph-based Pareto testing. Third, it relaxes the batch-calibration assumption via adaptive and sequential methods that exploit e-processes and anytime-valid inference to reduce the labelling budget. Fourth, it considers settings with limited groundtruth labels, combining testing-by-betting with prediction-powered inference (PPI) to enable reliable hyperparameter selection from autoevaluated data. Throughout, the framework is illustrated on practical applications including image classification, wireless packet scheduling, and large language model (LLM) prompt engineering, with empirical comparisons that demonstrate the gap between heuristic tuning and statistically guaranteed selection.
Chapter 1 Reliable Hyperparameter Selection 1.1
Hyperparameter Selection in Modern AI Systems
1.1.1
Scope
Hyperparameters determine how AI models are structured, trained, and deployed. Unlike model parameters, which are estimated automatically from training data, hyperparameters must be specified using additional sources of information, including prior knowledge and calibration or validation data. Broadly speaking, hyperparameters govern the operation of a machine learning system at different levels:
AI model Hyperparameters
Deployment
Figure 1.1: Illustration of post-training hyperparameter selection in a modern AI pipeline: Hyperparameters determine inference and deployment settings for a pre-trained model, influencing how model outputs are translated into operational behavior. 1
• At the model level, hyperparameters include architectural choices such as type of inter-token processing, e.g., self-attention versus statespace models, as well as network depth and width. • At the learning level, hyperparameters include learning rates, regularization coefficients, batch sizes, and training-time temperature in mixture-of-expert architectures. • At the inference level, hyperparameters determine how model outputs are translated into actions or decisions, for example through confidence thresholds, rejection rules, or decoding parameters such as the temperature of a language head. • At the deployment level, hyperparameters encode aspects such as precision of the activations and of the weights of a model. In conventional machine learning pipelines, optimizing model-based or learning-based hyperparameters typically requires running multiple training rounds using methods such as cross-validation (see, e.g., (Simeone, 2022)). However, for modern large AI models, this is not feasible, since even a single full training run constitutes a major computational investment (Kaplan et al., 2020; Hoffmann et al., 2022). Practical solutions for model-level or training-level hyperparameters include partial retraining across multiple hyperparameter configurations via optimized resource allocation strategies such as successive halving (Jamieson and Talwalkar, 2016) and Hyperband (Li et al., 2018). For extremely large models, one instead typically relies on scaling laws to translate optimal choices at lower scales to effective selection at higher scales (Kaplan et al., 2020; Hoffmann et al., 2022). Unlike model-level and training-level hyperparameters, inference and deploymentbased hyperparameters can be optimized via post-training strategies on pretrained models. Such post-training methods support data-driven evaluations of the performance of different hyperparameters even for large AI models. In this monograph, we target inference and deployment-based hyperparameters, thus focusing on post-training hyperparameter selection methods. This focus distinguishes the present monograph from algorithmic treatments of hyperparameter optimization (HPO). These include (Franceschi et al., 2025; Snoek et al., 2012; Bergstra and Bengio, 2012; Li et al., 2018), which 2
Tell me a story about a machine learning model LLM
LLM
Temperature
Temperature
The machine learning model woke up one morning convinced it understood the world…
A machine learning model was trained to classify images accurately…
Figure 1.2: Illustration of the effect of the decoding temperature on the outputs of a pre-trained large language model. For the same prompt and identical decoding settings except for temperature, a low temperature yields conservative, literal, and highly repeatable responses, while a high temperature produces more diverse, creative, and narrative-driven outputs. study how to efficiently search large hyperparameter spaces under computational budgets using methods such as Bayesian optimization, multi-fidelity methods, and gradient-based bilevel schemes. In contrast to these methods, this monograph treats the candidate set Λ as given, and concentrates instead on what can be said statistically about the final selected configuration under finite calibration data. The set Λ may be obtained in practice using any HPO method. Our goal is to endow post-training hyperparameter selection with explicit, finite-sample guarantees of reliability, e.g., on risk, constraint violations, or other deployment key performance indicators (KPIs), including after data-dependent selection among many candidates.
1.1.2
Examples
Examples of applications and use cases include the following: • In large language models, decoding hyperparameters such as temperature, nucleus sampling thresholds, and safety filters directly influence response diversity, factuality, and refusal behavior (Bommasani, 2021; Holtzman et al., 2019) (see Fig. 1.2 for an example). • In recommendation and ranking systems, regularization strengths and exploration parameters affect stability, long-term user engagement, and feedback loops (Covington et al., 2016).
3
Figure 1.3: Example of a learning-enabled wireless communication system in next-generation (6G) networks. In AI-native architectures such as ORAN (Polese et al., 2023), hyperparameters control key trade-offs among throughput, latency, reliability, and energy consumption, directly impacting system-level performance at deployment time (Simeone et al., 2025). • In computer vision pipelines, confidence thresholds determine whether predictions are accepted or deferred, shaping precision–recall trade-offs in detection and segmentation tasks (He et al., 2017). • In learning-enabled communication and control systems, hyperparameters regulate performance trade-offs among throughput, latency, reliability, and energy consumption (Shlezinger et al., 2021; Simeone et al., 2025). • In ground-truth in-the-loop systems (Geifman and El-Yaniv, 2017; Raghu et al., 2019), confidence thresholds and safety margins govern when models are permitted to act autonomously or escalate to fallback policies (Amodei et al., 2016).
1.2
Limitations of Best-Effort Tuning Methods
Hyperparameter selection has traditionally been approached as an empirical performance optimization problem. Given a calibration, or validation, 4
dataset and a predefined evaluation protocol, the goal is to identify hyperparameter configurations that achieve strong average empirical performance on the dataset under computational constraints. This optimization-centric perspective has given rise to a rich and mature literature on HPO. In the remainder of this section, we first briefly review HPO methods, and then discuss the gaps and limitations that motivate the reliability-oriented framework developed in this monograph.
1.2.1
Optimization-Centric Hyperparameter Selection
The dominant paradigm in HPO frames the problem as one of black-box optimization. Hyperparameters are treated as decision variables, the training and evaluation pipeline defines a stochastic objective function, and the task is to efficiently search the hyperparameter space in order to maximize expected empirical performance. Early approaches relied on exhaustive or randomized exploration strategies, such as grid search and random search, which remain widely used due to their simplicity and robustness (Bergstra and Bengio, 2012). Subsequent work introduced model-based strategies, most notably Bayesian optimization, which constructs a surrogate model of the validation performance and uses acquisition functions to balance exploration and exploitation (Snoek et al., 2012; Shahriari et al., 2016). To address the high computational cost of evaluating hyperparameter configurations, especially in modern deep learning, multi-fidelity and banditstyle approaches have been proposed. Methods such as successive halving and Hyperband allocate computational resources adaptively, terminating poorly performing configurations early while dedicating more resources to promising candidates (Jamieson and Talwalkar, 2016; Li et al., 2018). Related ideas appear in population-based training and evolutionary strategies, which maintain and evolve a population of configurations during training (Jaderberg et al., 2017). More recently, gradient-based HPO methods have been developed, leveraging implicit differentiation and hypergradients to optimize continuous hyperparameters directly through the training process (Franceschi et al., 2018). These methods are particularly effective when the training dynamics are differentiable and computationally tractable.
5
1.2.2
Lack of Reliability and Post-Selection Guarantees
From the perspective of this monograph, the methods reviewed above are best understood as best-effort tuning procedures. While they are highly effective at improving average performance and reducing computational cost, they are not designed to provide explicit guarantees on the reliability of the selected hyperparameter once deployed. In fact, despite their algorithmic diversity, these methods share a common objective, namely, to optimize empirical performance. Accordingly, standard optimization-based HPO approaches do not formally account for the uncertainty associated with empirical risk estimates. As emphasized in (Franceschi et al., 2025), the primary goals of HPO are sample efficiency, computational scalability, and asymptotic performance. Questions of post-selection validity, selective error control, or finite-sample guarantees on the selected configuration lie largely outside the scope of the optimization-centric framework. Fig. 1.4 illustrates the mismatch between conventional HPO, which is based on the minimization of the empirical risk, and true risk optimization for a scalar hyperparameter λ. Panel (a) shows the true risk R(λ) (blue b dashed curve), together with a realization of the empirical risk R(λ) (red curve). The shaded region represents the support of the empirical risk across different realizations of the calibration data. Given the realization of the empirical risk, and thus of the calibration data, depicted in panel (a) of Fig. 1.4, standard HPO selects a hyperparameter configuration λ̂HPO , as the minimizer of the empirical risk, which is significantly different from the true risk minimizer λ⋆ . This exemplifies the general fact that empirical risk minimization is inherently best-effort: it may favor hyperparameters that appear advantageous due to sampling variability rather than because they minimize the true risk R(λ). Panel (b) of Fig. 1.4 provides a conceptual view of the key principle underlying statistically valid hyperparameter selection. Instead of attempting to directly minimize the empirical risk, these methods fix a tolerated risk level and aim to identify hyperparameters whose true risk is not likely to exceed this target (dashed black line). Formally, the goal is to control the probability that the true risk exceeds the tolerated threshold. This naturally leads to a hypothesis testing formulation in which, for each hyperparameter λ, we test whether the true risk R(λ) is above the specified level using statistical tools such as p-values or e-values (Lehmann and Romano, 2005; Angelopoulos and Bates, 2023). 6
empirical risk
empirical risk
true risk
true risk
uncertainty on empirical risk
empirical risk distribution support
Λ̂
λ∗
λ̂HPO
(a)
(b)
Figure 1.4: (a) Empirical versus true risk as a function of the hyperparameter λ. The blue dashed curve shows the true risk R(λ), while the red curve b shows a realization of the empirical risk R(λ). The shaded region depicts the support of empirical risks across data realizations. Minimizing empirical risk selects λ̂HPO , which may differ from the true minimizer λ⋆ . (b) Risk-controlling hyperparameter selection. A tolerated risk level (horizontal dashed line) defines acceptable configurations. Statistical uncertainty bands are used to test, for each λ, whether the true risk exceeds the target. The highlighted set Λ̂ denotes the hyperparameters selected by the statistical procedure, which form a certified subset of the truly safe configurations (those with R(λ) below the threshold). As highlighted by the simplified illustration in Fig. 1.4(b), reliable hyperparameter selection must account for the inherent uncertainty on the true risk that is associated with the empirical estimate (shaded red area). Intuitively, only the hyperparameters that, even under the worst-case true risk within the range of plausible values (upper boundary of the red area), yield a true risk below the target value (dashed black line) can be considered as reliable given the available information. This way, the set of selected hyperparameters (denoted as Λ̂ in the figure) forms a certified subset of hyperparameters for which the true risk lies below the target level. Thus, while the procedure may be conservative and not recover all safe hyperparameters, it guarantees that every selected configuration satisfies the prescribed risk requirement with high probability. It is important to emphasize that the illustration in Fig. 1.4(b) hides several important challenges and should be taken as suggestive rather than pre7
scriptive. These challenges, which will be addressed throughout this monograph, are as follows: • User-defined failure probability: A reliable hyperparameter selection procedure must provide a mechanism to control the probability of selecting an unreliable hyperparameter. • Set-wide error control: The probabilistic guarantee must apply at the level of the entire set (Λ̂) of selected hyperparameters. For instance, one can impose the constraint that no hyperparameter in set Λ̂ is unreliable with the given target probability, or that the expected fraction of unreliable hyperparameters in set Λ̂ is smaller than a target value. The next section formalizes these requirements.
1.3
Problem Definition
Informally, a reliable hyperparameter choice is one that performs well enough, according to a user-defined threshold, with a low probability of violating critical requirements. Reliability is therefore a statement about the future behavior of the deployed system, under uncertainty arising from data variability and environment stochasticity. This perspective, detailed in this section, aligns with recent calls to move from performance-centric to reliability- and safety-centric evaluation of AI systems (Amodei et al., 2016).
1.3.1
Hyperparameter Selection Domain
Throughout this monograph, we use the symbol λ to denote a hyperparameter or a vector of hyperparameters controlling the behavior of a machine learning system. In practice, hyperparameters are often selected from a finite or discretized set Λ = {λ1 , . . . , λK } of K = |Λ| candidates. This preselection step can be implemented using any of the HPO methods reviewed in Sec. 1.2.1 from a possibly continuous hyperparameter space.
1.3.2
Reliability Requirements
To determine when a hyperparameter is acceptable or reliable, we start by specifying an application-specific loss measure, such as prediction error, constraint violation rate, or system-level cost. A hyperparameter is then declared 8
to be reliable if a chosen statistic of the loss, such as its expectation or a tail probability, lies below a user-defined threshold α. To elaborate, for a generic prediction problem, consider a random test point (X, Y ) drawn from the data distribution, where X denotes the input features and Y is the ground-truth label. For a given hyperparameter λ, let Lλ (X, Y ) denote the incurred loss on a single test point. Examples include the 0–1 loss Lλ (X, Y ) = I Ŷλ (X) ̸= Y , (1.1)
where Ŷλ (X) is the predictor deployed under hyperparameter λ, and I{·} denotes the indicator function, which equals 1 if its argument is true and 0 otherwise. A typical target statistic is the average of the loss (1.1), i.e., R(λ) = E [Lλ (X, Y )] .
(1.2)
Other options encompass quantiles, such as the median. Having defined a risk function R(λ), a hyperparameter λ is said to be reliable if it is able to control the risk R(λ) below a user-specified target level α, i.e., λ reliable ⇔ R(λ) = E[Lλ (X, Y )] ≤ α. (1.3)
Importantly, reliability is a property of the deployed system and of the underlying data distribution, not of a finite dataset. A hyperparameter selection procedure observes a finite calibration dataset and outputs a candidate λ̂ ∈ Λ. Because the data are random, the selected hyperparameter is also random. For a selected hyperparameter λ̂, the basic guarantee we seek is that the hyperparameter λ̂ is reliable with probability no smaller than a target 1 − δ, i.e., P λ̂ is reliable = P R(λ̂) ≤ α ≥ 1 − δ, (1.4) where the probability is over the randomness in the data used for selection. We emphasize that the guarantee (1.4) does not claim that the selected hyperparameter is optimal; or that failures never occur; or that performance is uniform across all possible conditions. However, it does claim that the act of selecting an unreliable hyperparameter is itself a rare event; and that the frequency of this event is explicitly quantified by the failure probability δ. Fig. 1.5 provides a visual illustration of the reliability guarantee (1.4) using a simple real-data classification experiment. We consider a fixed dataset 9
and a finite grid of regularization hyperparameters for an ℓ2 -regularized logistic regression model (Friedman et al., 2010). For each repetition, the available data are randomly split into training and calibration sets. A hyperparameter λ̂ is selected based solely on the calibration data and the resulting model is evaluated on a fixed held-out test set to estimate its deployment risk R(λ̂). Repeating this procedure over independent calibration realizations yields a distribution of test risks. The blue curve corresponds to hyperparameters selected using a statistically valid selection rule that accounts for uncertainty due to finite calibration data (see Fig. 1.4). While individual realizations may exceed the target risk level α = 0.2, the probability of such violations is controlled. In particular, the shaded region corresponding to events where the risk exceeds the maximum tolerance α, i.e., R(λ̂) > α, occupies at most a δ = 0.1 fraction of the distribution, illustrating that guarantee (1.4) holds. For comparison, the orange curve corresponds to hyperparameters selected by grid search, which minimizes the empirical risk on the calibration dataset without correcting for selection uncertainty. Because the search is conducted over many candidate configurations, as illustrated in Fig. 1.4, this approach can select hyperparameters whose apparent calibration performance is overly optimistic. As a result, the violation probability can substantially exceed the prescribed tolerance δ = 0.1. This contrast highlights the importance of statistical correction in reliable hyperparameter selection. The remainder of this monograph is concerned with developing methods that achieve such guarantees in practice.
1.4
Summary of Notation and Acronyms
Table 1.1 summarizes the notation used in the monograph, while Table 1.2 reports the main acronyms found in the text. Table 1.1: Summary of mathematical notation used throughout the monograph. Symbol λ Λ
Definition Hyperparameters (vector-valued) Finite candidate set of hyperparameters, Λ = {λ1 , . . . , λ|Λ| } Continued on next page 10
Symbol K X Y (X, Y )
Definition Number of candidate hyperparameters, K = |Λ| Input space Output/label space Random test point (features, outcome) drawn from distribution P Z Random test point drawn from distribution P (e.g., Z = (X, Y )) P, P(·), Unknown data-generating distribution; also used as P(X, Y ), P(·) to denote the probability of an event under this P(Z) distribution fλ Pre-trained model operating under hyperparameter λ, fλ : X → Y Lλ (X, Y ) Per-sample loss under hyperparameter λ, Lλ : X ×Y → [0, 1] R(λ) True risk, R(λ) = E[Lλ (X, Y )] b Rn (λ) Empirical risk on n calibration samples Dcal Calibration dataset Dcal = {(Xi , Yi )}ni=1 n Number of calibration samples α Reliability threshold; λ is reliable ⇔ R(λ) ≤ α (singleobjective) δ User-specified failure probability (outage rate) Λ̂ Certified subset of selected hyperparameters, Λ̂ ⊆ Λ λ̂ Single deployed hyperparameter, λ̂ ∈ Λ̂ Hk Null hypothesis for candidate λk : R(λk ) > α K0 Set of indices of true null hypotheses K̂ Set of rejected hypothesis indices (discoveries) pk P-value for null hypothesis Hk ek E-value for null hypothesis Hk I{·} Indicator function (equals 1 if argument is true, 0 otherwise) (·)+ Positive part, (x)+ = max{x, 0} R(λ) General risk functional, R(λ) = Φ(Pλ ) Rq (λ) Quantile risk: (1−q)-quantile of the distribution of loss Lλ I(A; B) Mutual information between random variables A and B Continued on next page 11
Symbol Rl (λ) α LC ΛPar
Definition Risk function for objective l in multi-objective setting Vector of risk thresholds (α1 , . . . , αLC ) in multiobjective setting (Ch. 5) Number of reliability (constrained) objectives Pareto-optimal subset of hyperparameters
Table 1.2: List of acronyms used throughout the monograph. Acronym AI BH BY CGF DAG E-HPO FDR FDP FST FWER HPO IB IB-LTT KPI LLM LTT MGF MHT O-RAN PCA PT QLTT QoS RG RG-PT
Definition Artificial Intelligence Benjamini–Hochberg (FDR-controlling procedure) Benjamini–Yekutieli (FDR-controlling procedure under arbitrary dependence) Cumulant Generating Function Directed Acyclic Graph Empirical Hyperparameter Optimization False Discovery Rate False Discovery Proportion Fixed Sequence Testing Family-Wise Error Rate Hyperparameter Optimization Information Bottleneck Information Bottleneck Learn-Then-Test Key Performance Indicator Large Language Model Learn-Then-Test Moment Generating Function Multiple Hypothesis Testing Open Radio Access Network Principal Component Analysis Pareto Testing Quantile Learn-Then-Test Quality of Service Reliability Graph Reliability Graph-Based Pareto Testing Continued on next page 12
Acronym UE 6G
1.5
Definition User Equipment Sixth Generation (wireless networks)
Scope and Organization of the Monograph
As mentioned, the remainder of this monograph develops the statistically valid hyperparameter selection framework outlined in Sec. 1.3 and progressively broadens its scope along four directions: more general notions of risk, multiple simultaneous objectives, adaptive and sequential evaluation budgets, and certification with limited labeled data. Chapter 2 introduces the core methodology, namely the learn-then-test (LTT) framework of (Angelopoulos et al., 2025), which formulates reliable hyperparameter selection as a multiple hypothesis testing (MHT) problem. Each candidate hyperparameter is associated with the null hypothesis that its true risk exceeds the target level, and a finite-sample certified set is produced by any MHT procedure that controls a global error criterion such as the family-wise error rate (FWER) or the false discovery rate (FDR). The chapter develops the supporting statistical machinery, namely p-values and e-values, and shows how concentration inequalities and testing-by-betting arguments translate empirical risk estimates into valid test statistics. Chapter 3 illustrates the LTT framework on two representative applications: image classification on Fashion-MNIST (Xiao et al., 2017) and packet scheduling for a learning-based wireless scheduler (Sant Ana and Marchenko, 2020; Valcarce, 2020). In both cases, conventional empirical hyperparameter optimization is shown to violate the prescribed reliability constraint at rates substantially exceeding the user-specified outage probability, while LTT controls the violation rate as guaranteed by theory. Chapter 4 extends LTT beyond the average risk to more general reliability functionals. The chapter presents a unified inversion-based recipe for constructing valid p-values from one-sided confidence bounds, and instantiates it for two important non-average criteria: quantile risk control, which yields the quantile LTT (QLTT) procedure of (Farzaneh et al., 2024) and provides protection against tail events; and information-theoretic relevance constraints, which yields the IB-LTT procedure of (Farzaneh and Simeone, 2025b) for the information bottleneck problem. Chapter 5 addresses settings in which several reliability constraints must 13
Reliable selection (risk-controlled)
35
Empirical HPO (e.g., grid search)
30
Target risk β = 0.2
Density (over calibration datasets)
40
25 20 15 10
failure probability = 0.18
failure probability = 0.05
5 0
0.16
0.17
0.18
0.19
0.20
0.21
0.22
0.23
ˆ of the selected hyperparameter ∏ ˆ Risk R(∏)
Figure 1.5: Distribution of the risk R(λ̂) for the selected hyperparameter λ̂ over repeated training-calibration data splits. The dashed line marks the target risk α = 0.2. The blue curve corresponds to a statistically valid selection rule, whose violation probability P(R(λ̂) > α) is controlled below threshold δ = 0.1 as per (1.4). The orange curve corresponds to conventional HPO based on empirical risk minimization, which exhibits a larger violation probability. be enforced simultaneously while best-effort secondary objectives are optimized. The chapter develops Pareto testing (PT) (Laufer-Goldshtein et al., 2023), which restricts hypothesis testing to the empirical Pareto frontier and applies fixed sequence testing along the resulting ordering, and reliability graph-based Pareto testing (RG-PT) (Farzaneh and Simeone, 2025a), which encodes prior structural knowledge through a directed acyclic graph and certifies hyperparameters via the DAGGER algorithm of (Ramdas et al., 2019). Chapter 6 relaxes the batch-calibration assumption of the previous chapters, allowing calibration data to arrive sequentially and acquisition decisions to depend on the evidence accumulated so far. Building on e-processes and Ville’s inequality, the chapter develops adaptive LTT (aLTT) (Zecchin et al., 2024), which combines testing-by-betting with ε-greedy acquisition to identify reliable hyperparameters with substantially fewer evaluations than batch LTT, while preserving FWER and FDR guarantees at every, possibly data-dependent, stopping time. Chapter 7 considers settings where ground-truth labels are expensive, but cheap autoevaluated labels are available, as in LLM-as-a-judge pipelines (Gu et al., 2024). Combining the testing-by-betting machinery of Chapter 6 14
with prediction-powered inference (Angelopoulos et al., 2023b), the chapter describes the R-AutoEval method of (Einbinder et al., 2025) and the adaptive R-AutoEval+ method of (Park et al., 2025), the latter of which adaptively reweights a grid of reliance factors and provably matches the better of full-real and full-autoevaluated testing in sample complexity. Chapter 8 concludes the monograph and outlines open research directions. Appendix A collects background material on statistical evidence. It provides a self-contained treatment of p-values and e-values, including their definitions, constructions from concentration bounds and randomization tests, and the key compositional and anytime-validity properties that distinguish them. Appendix B collects technical details on p-value and e-value constructions complementing Chapter 2: a unified moment generating function viewpoint covering bounded, sub-Gaussian, and sub-exponential losses; a proof of superuniformity for the Hoeffding-based p-value; and refined finite-sample constructions including exact binomial and variance-sensitive Bernstein pvalues. Appendix C gathers additional multiple testing procedures: Holm, Hochberg, Šidák, and Westfall–Young FWER procedures, and a proof of the FDR guarantee for the e-BH procedure.
15
Chapter 2 Hyperparameter Selection via Multiple Hypothesis Testing This chapter introduces a general framework for risk-controlling hyperparameter selection. As illustrated in Fig. 1.5, the goal is to identify a configuration λ̂ for which the true risk R(λ̂) is guaranteed to lie below a user-chosen threshold with high probability with respect to the randomness of the calibration data. The framework follows the post-training calibration methodology introduced by (Angelopoulos et al., 2025). This approach is also referred to as LTT, since it is based on training and calibration on separate datasets (Grünwald et al., 2020; Vovk and Wang, 2021; Chakraborty et al., 2026). The chapter is organized as follows. Sec. 2.1 introduces the risk-control objective and empirical risk estimation. Sec. 2.2 reviews the multiple hypothesis testing framework and the family-wise error rate. Sec. 2.3 shows how to connect MHT to hyperparameter certification and proves the main certifiedset guarantee. Sec. 2.4 introduces p-values as test statistics and derives the Hoeffding-based p-value for bounded losses. Sec. 2.5 introduces e-values as an alternative evidence measure and describes their key properties. Sec. 2.6 develops false discovery rate control via the BH and e-BH procedures, which are less conservative alternatives to FWER control. Sec. 2.7 summarizes the chapter. Technical material on p-value and e-value constructions from moment generating function bounds is collected in Appendix B.
16
2.1
Risk Control
Throughout this monograph, as discussed in Sec. 1.3, we fix a finite candidate set Λ = {λ1 , . . . , λK }, (2.1)
which may arise from any upstream hyperparameter search or model design process. Each hyperparameter λ ∈ Λ determines the operation of a pretrained model fλ : X → Y, (2.2)
where X denotes the input space and Y denotes the model output space. The model fλ may be predictive, generative, or it may prescribe a control policy. In the former case, the output space Y may encompass point estimates for the given target variables, probability distributions on the target variable space, or structured predictions such as class labels in multi-class classification (Hastie et al., 2009), and bounding boxes or segmentation masks in object detection (Ren et al., 2015; He et al., 2017). With generative models fλ , the output space Y may include images (Ho et al., 2020), videos (Ho et al., 2022), or text (Vaswani et al., 2017), often in the form of token sequences. Finally, control policies fλ output action sequences (Sutton and Barto, 1998). The key quantity of interest is the average risk of model fλ , which is defined as the expectation of a loss function under the (unknown) datagenerating distribution. Concretely, let (X, Y ) ∼ P denote a generic test-time input-output pair, and let Lλ : X × Y → [0, 1]
(2.3)
be a bounded loss function that encodes a deployment-relevant notion of (negatively oriented) performance. Note that any bounded performance measure can be constrained within the standardized interval [0, 1] by rescaling. Furthermore, unbounded losses can be handled via asymptotic or truncated constructions as discussed in (Angelopoulos et al., 2025). We define the risk of hyperparameter λ as R(λ) = E Lλ X, Y , (2.4) where the expectation is taken over the unknown test-time data distribution P. 17
The user specifies a target level α ∈ (0, 1) for the average risk (2.4), as well as a failure probability δ ∈ (0, 1). The goal is to select a (data-dependent) hyperparameter λ̂ ∈ Λ such that the deployed model fλ̂ satisfies the following risk control guarantee. Definition 2.1. A hyperparameter choice λ̂ ∈ Λ is said to be (α, δ)-riskcontrolling if the inequality P(R(λ̂) ≤ α) ≥ 1 − δ
(2.5)
holds, where the probability P(·) is taken over the randomness in the calibration data used to optimize the hyperparameter λ̂. The key challenge in ensuring condition (2.5) is that the risk R(λ) depends on the unknown distribution P, while hyperparameters λ̂ must be chosen based on a finite calibration dataset. To elaborate, let Dcal = {(X1 , Y1 ), . . . , (Xn , Yn )},
(2.6)
i.i.d.
where (Xi , Yi ) ∼ P for all i ∈ {1, . . . , n}, denote a calibration dataset. For each candidate hyperparameter λ ∈ Λ, define the corresponding empirical risk n 1X b Lλ (Xi , Yi ). (2.7) Rn (λ) = n i=1 Conventional E-HPO chooses the hyperparameter λ that minimizes the embn (λ), i.e., pirical estimates R bn (λ). λ̂HPO = arg min R λ∈Λ
(2.8)
As discussed in Sec. 1.2.2, E-HPO does not provide any reliability guarantees in general (see Fig. 1.4).
2.2
Multiple Hypothesis Testing
Following (Angelopoulos et al., 2025), we address this problem by treating the risk-control objective as a multiple hypothesis testing (MHT) problem. To explain MHT, consider the standard A/B testing methodology applied by an online retailer, as illustrated in Fig. 2.1. The online retailer 18
Algorithm 1 Empirical Hyperparameter Optimization (E-HPO) Input: candidate set Λ = {λ1 , . . . , λK }; calibration data {(Xi , Yi )}ni=1 Output: selected hyperparameter λ̂HPO ∈ Λ for k = 1, . . . , K do Compute empirical risk n
X bn (λk ) = 1 R Lλk Xi , Yi n i=1 end for Select hyperparameter with smallest empirical risk bn (λ) λ̂HPO = arg min R λ∈Λ
wishes to explore possible modifications relative to the current website configurations. For example, it may experiment with a new homepage layout, different product image sizes, alternative call-to-action button colors, revised pricing display formats, and personalized recommendation banners. For each proposed modification, the retailer formulates a baseline claim, called the null hypothesis, stating that the modification does not improve conversion relative to the current configuration. The retailer then collects user-interaction data, and evaluates whether the observed improvement is strong enough to contradict this baseline claim. When the data provide sufficient statistical evidence against the null hypothesis, the retailer declares a discovery, meaning that the modification is judged to produce a genuine improvement. However, when many modifications are tested simultaneously, the probability of making at least one incorrect discovery increases with the number of experiments. Even if each individual experiment has a small probability δ of producing a false discovery, running K experiments inflates the overall chance that at least one ineffective modification is incorrectly declared successful. In fact, under independence, this probability equals 1 − (1 − δ)K ≈ Kδ, which grows with K. For instance, if δ = 0.01 and K = 50, the probability of making at least one incorrect claim is (1 − 0.9950 ) ≈ 0.395. This observation motivates the adoption of MHT tools. As illustrated in Fig. 2.1, in MHT, we are generally faced with a set H = {H1 , . . . , HK } 19
Null hypotheses (Current settings)
VS.
VS.
Color
VS.
VS.
Size
VS.
VS.
Orientation
VS.
VS.
Style
VS.
VS.
Logo
Discoveries
Figure 2.1: Illustration of multiple hypothesis testing (MHT) for the example of A/B testing implemented by an online retailer. Multiple changes to the current settings of the retailer’s website are considered via separate tests, and a number of them are discovered as effective changes. of hypotheses that need to be tested simultaneously. An MHT procedure returns a subset K̂ ⊆ {1, . . . , K} of the hypotheses as discoveries, i.e., as null hypotheses that have been rejected by the MHT procedure. Rather than controlling the error rate separately for each hypothesis, MHT controls a global error criterion across the entire family of tests. One such criterion is the family-wise error rate (FWER), defined as the probability of making even a single incorrect claim among all tested modifications. Procedures that control the FWER ensure that, with high probability, none of the selected discoveries is actually ineffective. To formalize this setting, for each hypothesis Hk ∈ H, MHT methods construct a test statistic Tk based on the available data. The statistic Tk is ideally designed to measure how surprising the data are under the null Hk , so that large values provide evidence against Hk (see Sec. 2.4, Sec. 2.5, and Appendix A for more details on how to construct valid test statistics). An individual hypothesis Hk is rejected whenever its test statistic Tk exceeds a suitable rejection threshold. When testing multiple hypotheses simultaneously, the central statistical risk is that of false discovery, i.e., of rejecting a hypothesis Hk even though it is in fact true. Let K0 = { k : Hk is true } (2.9) denote the indices of all true null hypotheses. A false discovery occurs if hypothesis Hk is rejected for some k ∈ K0 , i.e., if the intersection between 20
the set of rejected hypotheses (discoveries) K̂, and the set of true nulls K0 , is non-empty, i.e., K̂ ∩ K0 ̸= ∅. To ensure reliability after selection, we seek to control the probability of making any such false discovery. This leads naturally to the notion of FWER, which is formally defined as FWER = P(∃ k ∈ K0 such that Hk is rejected) = P(K̂ ∩ K0 ̸= ∅).
(2.10)
i.e., the probability of having any true null hypothesis among the rejected hypotheses in set K̂. Fig. 2.2 illustrates two multiple testing outcomes, which may correspond to two distinct realizations of the calibration dataset Dcal . In the case illustrated in the left panel, the set K̂ of rejected hypotheses contains no true null hypotheses, while in the second at least one true null hypothesis is erroneously rejected, contributing to an increase of the FWER. Controlling FWER at level δ, i.e., FWER ≤ δ, (2.11) guarantees that, with probability at least 1 − δ, no true null hypothesis is rejected, as in the left panel of Fig. 2.2. Definition 2.2 (FWER-controlling procedure). A selection procedure AFWER : RK → 2K
(2.12)
that maps a collection of test statistics (T1 , . . . , TK ) to a set of rejected hypotheses (discoveries), i.e., K̂ = AFWER (T1 , . . . , TK ),
(2.13)
is said to control the FWER at level δ ∈ (0, 1] if the probability of rejecting any null hypothesis is smaller than δ, i.e., P K0 ∩ K̂ = ∅ ≥ 1 − δ. (2.14) In other words, an FWER-controlling procedure ensures that the entire rejected set consists only of false null hypotheses, with the exception of events having probability at most δ. 21
False null hypotheses False discovery
True null hypotheses
K̂
K̂
H
H
Figure 2.2: Schematic illustration of family-wise error rate (FWER) control in MHT. Each point represents a null hypothesis, with green markers denoting false null hypotheses and red markers denoting true null hypotheses. The shaded region corresponds to the subset K̂ of hypotheses rejected by a test, i.e., of discoveries. Left: The rejected set contains no true null hypotheses, a condition that occurs with probability at least 1 − δ if the FWER condition (2.11) is satisfied. Right: The rejected set includes at least one true null hypothesis, an event that occurs with probability smaller than δ under the FWER guarantee (2.11).
2.3
Risk Control via Multiple Hypothesis Testing
We now show how to connect MHT to the problem of reliable hyperparameter selection. To start, for each candidate hyperparameter λk ∈ Λ, we define the null hypothesis Hk : R(λk ) > α (2.15) that the average risk exceeds the target level α. Rejecting Hk therefore corresponds to certifying that hyperparameter λk meets the risk requirement (1.3). Assume we have a valid test statistic Tk for each null hypothesis Hk (see Sec. 2.4 and Sec. 2.5), as well as an MHT procedure AFWER that controls the FWER at level δ. The following guarantee is immediate by the definition of FWER-controlling procedures.
Theorem 2.1. Any FWER-controlling procedure at level δ for the null hypotheses (2.15) returns a subset Λ̂ ⊆ Λ of hyperparameters satisfying the 22
reliability condition ! P sup R(λ) ≤ α λ∈Λ̂
(2.16)
≥ 1 − δ.
Proof. Let ( E = {∄λ ∈ Λ̂ : R(λ) > α} =
)
sup R(λ) ≤ α
(2.17)
λ∈Λ̂
denote the event that all the hyperparameters in set Λ̂ are reliable. By the definition (2.15) of the null hypotheses, this is equivalent to the event E = {Λ̂ ∩ Λ0 = ∅}, where Λ0 is the subset of hyperparameters for which the null hypothesis (2.15) holds, i.e., Λ0 = {λ ∈ Λ : R(λ) > α}. Hence, by the FWER property (2.14), we have ! P sup R(λ) ≤ α λ∈Λ̂
= P(Λ̂ ∩ Λ0 = ∅) ≥ 1 − δ,
(2.18)
concluding the proof. This result has the following important consequence. Corollary 2.2. Any specific hyperparameter λ̂ ∈ Λ̂, possibly selected via a data-dependent way within the subset Λ̂, is (α, δ)-risk-controlling in the sense of Definition 2.1 as long as the selection procedure controls the FWER at level δ. By Corollary 2.2, once the certified set Λ̂ is obtained under FWER control, we may select any specific hyperparameter configuration λ̂ ∈ Λ̂ that optimizes any secondary objectives such as accuracy, efficiency, or interpretability, without invalidating the risk guarantee (1.4). Overall, as summarized in Fig. 2.3, the workflow of reliable hyperparameter selection via MHT is as follows: 1. For each candidate hyperparameter λk ∈ Λ, use the calibration data bn (λk ) for all λk ∈ Λ via (2.7). Dcal to estimate the empirical risks R bn (λk )}K in (2.7) into valid statistics, i.e., 2. Turn the empirical risks {R k=1 p-values (see Sec. 2.4) or e-values (see Sec. 2.5). 23
Multiple hypothesis testing (MHT)
Hyperparameter pre-selection
Λ
H1 : λ1 unreliable H2 : λ2 unreliable .. .
HK : λK unreliable
MHT
Λ̂ ⊆ Λ
Figure 2.3: Reliable hyperparameter selection as MHT. Each hyperparameter λk ∈ Λ is assigned to the null hypothesis Hk : R(λk ) > α that the hyperparameter is unreliable for a given target maximum risk level α. An MHT procedure outputs subset of hyperparameters Λ̂ that provides reliability guarantees on the number of unreliable hyperparameters (with R(λ) > α) in subset Λ̂. 3. Apply an MHT procedure to the derived statistics to obtain a certified set Λ̂ ⊆ Λ of reliable hyperparameters. 4. Select hyperparameter λ̂ ∈ Λ̂ for deployment by following any, possibly data-dependent, criterion.
2.4
P-values
This section describes standard statistics Tk to test the null hypotheses Hk , namely p-values. A self-contained broader background treatment of p-values, including their definition, power, and general constructions via the probability integral transform and concentration bounds, is provided in Appendix A.
2.4.1
Definition
For each candidate hyperparameter λk ∈ Λ, a p-value pk for the null hypothesis Hk in (2.15) is a function of the calibration data Dcal such that, for all u ∈ [0, 1], the inequality P(pk ≤ u | Hk ) ≤ u
(2.19)
holds, where the probability is taken over the randomness of the calibration dataset when conditioning on the null hypothesis Hk . Condition (2.19) is 24
1.0
CDF
0.8
Uniform random variable: FU (u) = u Superuniform random variable
0.6 0.4 0.2 0.0 0.0
0.2
0.4
0.6
0.8
1.0
u
Figure 2.4: Illustration of the superuniformity property (2.19): The CDF FU (u) = u of a uniform random variable Unif(0, 1) is shown as a dashed line, and a superuniform random variable has a CDF Fp (u) ≤ u for all u ∈ [0, 1], lying on or below the dashed diagonal line. known as the superuniformity property. It states that, under the null Hk , the p-value is stochastically no smaller than a uniform random variable in the interval (0, 1), i.e., small p-values occur no more often than they would under a uniform draw. The CDF of a uniform distribution Unif(0, 1) is given by FU (u) = u for u ∈ [0, 1]. Therefore, letting Fpk (u | Hk ) = P(pk ≤ u | Hk ) denote the CDF of the p-value pk , the superuniformity property (2.19) corresponds equivalently to the inequality Fpk (u | Hk ) ≤ FU (u) for all u ∈ [0, 1],
(2.20)
so that the null CDF of a valid p-value lies everywhere below the line FU (u) = u in the interval u ∈ [0, 1]. This property is illustrated in Fig. 2.4. P-values are often constructed from concentration inequalities (Boucheron et al., 2003). Notably, in the bounded-loss setting Lλ (·, ·) ∈ [0, 1], a simple and widely used construction of p-values is based on Hoeffding’s inequality (Hoeffding, 1963). Lemma 2.3 (Hoeffding’s inequality). Fix a hyperparameter λk ∈ Λ and assume that the losses Lλk (Xi , Yi ) are independent and bounded in [0, 1]. Then, 25
bn (λk ) satisfies for any t > 0, the empirical risk R bn (λk ) ≤ R(λk ) − t ≤ exp −2nt2 . P R
(2.21)
Lemma 2.4. The statistic bn (λk ) 2 pk = exp −2n α − R +
(2.22)
is a p-value for the null hypothesis Hk in (2.15), where (x)+ = max{x, 0}. bn (λk )] > Proof. Under the null hypothesis Hk in (2.15), i.e., when R(λk ) = E[R α, Hoeffding’s inequality (2.21) implies the condition bn (λk | Hk ) ≤ α − t ≤ exp −2nt2 , P R t > 0. (2.23) The following chain of inequalities establishes the superuniformity property: i h bn (λk ) 2 ≤ u Hk Fpk (u | Hk ) = P exp −2n α − R + " # r − log u bn (λk ) ≥ =P α−R Hk + 2n " # r − log u bn (λk ) ≤ α − =P R Hk 2n !2 r − log u ≤ exp−2n 2n (2.24)
= u.
To interpret the p-value (2.22), for a given hyperparameter λk , let ∆i,k = α − Lλk (Xi , Yi )
(2.25)
be the instantaneous reliability margin with respect to the target α for hyperparameter λk given the test pair (Xi , Yi ). Under the null hypothesis Hk , we have the inequality E[∆i,k | Hk ] = α − R(λk ) < 0, 26
(2.26)
i.e., the average margin is negative. Hence, under the null hypothesis Hk , the random variables ∆i,k have negative mean, and large positive deviations of their sum provide evidence against the null hypothesis Hk . Accordingly, the bn (λk ))+ p-value (2.22) decreases exponentially quickly as the quantity (α − R becomes increasingly positive. As further discussed in Appendix B, more refined p-values based on more powerful concentration inequalities such as exact binomial tails for 0-1 losses or empirical Bernstein bounds based on knowledge or estimates of the variance of the loss can substantially improve test performance in terms of capacity to identify true reliable hyperparameters.
2.4.2
P-values for Single-Hypothesis Testing
Before turning to MHT, it is useful to recall how p-values are used for a single hypothesis test. To this end, consider one candidate hyperparameter λk and the null hypothesis Hk : R(λk ) > α. The primary validity requirement for a single test is type-I error control. This requires controlling the probability of falsely deeming hyperparameter λk as reliable when in fact it is not. Given the p-value pk for hypothesis Hk , consider the following test if pk ≤ δ, reject Hk ; otherwise accept Hk .
(2.27)
The type-I probability of error is the probability of a false rejection, or false discovery. For the test (2.27), this probability is bounded as P(reject Hk | Hk ) = P(pk ≤ δ | Hk ) ≤ δ,
(2.28)
which is an immediate consequence of the superuniformity property (2.19) that defines a p-value. Accordingly, the test (2.27) gives a type-I error probability no larger than δ, and is said to be a level-δ test. Attaining an arbitrarily low type-I error probability is straightforward, as it suffices to accept the hypothesis Hk irrespective of the available data. It is thus necessary to evaluate also the type-II error probability, i.e., the probability of incorrectly identifying hyperparameter λk as unreliable when in fact it is reliable. Equivalently, one can evaluate the power, i.e., the complement of the type-II error. Writing the alternative hypothesis, i.e., that hyperparameter λk is reliable, as Hkc : R(λk ) ≤ α, 27
(2.29)
the power of the level-δ test (2.27) is Power(δ) = P(reject Hk | Hkc ) = P(pk ≤ δ | R(λk ) ≤ α).
(2.30)
The power of test (2.27) depends on the separation between the true risk R(λk ) and the target level α, the sample size n, and the tightness of the p-value. For example, suppose that hyperparameter λk is truly reliable by a margin ε, i.e., R(λk ) = α − ε for some ε > 0. Then, the p-value (2.22) decreases at the rate exp(−cnε2 ) for a constant c > 0. Consequently, the test (2.27) rejects the null hypothesis Hk with higher probability, i.e., has higher power, when we have more calibration samples n, or the gap ε between the true risk and the target α is larger. In summary, for a single hypothesis, with the test (2.27), the threshold δ directly controls the type-I error, i.e., the probability of selecting an unreliable hyperparameter, while the chosen p-value construction governs how quickly the test can improve power, i.e., select truly reliable hyperparameters.
2.4.3
P-values in MHT
Once p-values {pk }k=1,...,K have been constructed for all the K null hypotheses H, an FWER-controlling certified set Λ̂ can be obtained by applying any MHT procedure that controls the FWER (2.10) at level δ. We briefly review several widely used MHT procedures in the following. 1) Bonferroni correction: The most classical FWER procedure is the Bonferroni correction (Bonferroni, 1936), which rejects each null hypothesis Hk whenever the inequality δ (2.31) pk ≤ K holds. Proposition 2.1 (FWER control of the Bonferroni correction). The Bonferroni correction (2.31) controls the FWER at level δ under arbitrary dependence among the p-values. Proof. Under the Bonferroni rule (2.31), the event of violating the FWER condition (2.10) can be written as δ ∃ k ∈ K0 : pk ≤ , (2.32) K 28
i.e., that there exists a true null hypothesis k that satisfies the Bonferroni condition (2.31). By the union bound, X δ δ P ∃ k ∈ K0 : pk ≤ ≤ P pk ≤ . (2.33) K K k∈K 0
For each k ∈ K0 , the hypothesis Hk is true, and hence, by the superuniformity condition (2.19) with u = δ/K, δ δ δ P pk ≤ = P pk ≤ Hk ≤ . (2.34) K K K Substituting into (2.33) yields FWER ≤
X δ k∈K0
K
=
|K0 | δ ≤ δ, K
(2.35)
since |K0 | ≤ K. Note that, equivalently, one may define Bonferroni-adjusted p-values p̃k = min{1, Kpk },
(2.36)
and reject Hk if the inequality p̃k ≤ δ holds. Bonferroni is conservative when K is large, but it provides a simple baseline with minimal assumptions. 2) Fixed sequence testing (FST): An alternative FWER-controlling procedure is fixed sequence testing, which exploits a pre-specified ordering of the hypotheses. Suppose that, prior to examining the calibration data used to compute the p-values, the hypotheses in H are arranged in a fixed sequence from most promising to least promising to be reliable. This ordering may reflect prior information or structural considerations, such as increasing model complexity, decreasing validation performance on a separate dataset, or expert knowledge suggesting that certain hyperparameters are more promising. Denote the ordered list of hypotheses by H(1) , . . . , H(K) , and let p(1) , . . . , p(K) be the corresponding p-values arranged according to this predetermined sequence. FST starts by testing H(1) at level δ using the test (2.27). If p(1) ≤ δ, the hypothesis H(1) is rejected and the procedure proceeds to test H(2) at the 29
same level δ. In general, testing continues sequentially for k = 1, . . . , K as long as the inequality p(k) ≤ δ holds. FST stops at the first index k ⋆ = min{k : p(k) > δ},
(2.37)
with the convention k ⋆ = K + 1 if all hypotheses are rejected. The rejected set of hypotheses is then K̂ = {H(1) , . . . , H(k⋆ −1) }.
(2.38)
Proposition 2.2 (FWER control of fixed sequence testing). Fixed sequence testing (2.37) controls the FWER at level δ. Proof. Let k0 be the smallest index such that H(k0 ) is a true null hypothesis, i.e., H(k0 ) ∈ K0 . A family-wise error occurs only if H(k0 ) is rejected, since the procedure stops immediately after the first non-rejection. Because H(k0 ) is tested at level δ, FWER = P p(k0 ) ≤ δ H(k0 ) ≤ δ, (2.39) where the inequality follows from the superuniformity property (2.19).
Unlike Bonferroni, FST does not divide the level δ across the K hypotheses. When the ordering places truly reliable hyperparameters early in the sequence, the procedure can therefore be substantially more powerful. However, its performance depends critically on the quality of the predetermined ordering: if unreliable hyperparameters appear early, the procedure may stop prematurely and fail to identify reliable configurations appearing later in the sequence.
2.5
E-values
This section introduces e-values as alternative statistics Tk for the null hypotheses Hk . A self-contained background treatment of e-values, including their interpretation as generalized likelihood ratios and the proofs of the properties summarized below, is provided in Appendix A.
2.5.1
Definition
A conceptually distinct way to construct valid statistics is through e-values. E-values quantify evidence against a null hypothesis via an expectation constraint, rather than a tail-probability constraint like p-values (Vovk and 30
Wang, 2021; Grünwald et al., 2020; Shafer and Vovk, 2019; Ramdas and Wang, 2025; Shafer, 2019). They can be thought of as a generalization of likelihood ratios, as a betting score, or as a strong type of p-value with special properties (Ramdas and Wang, 2025). For each candidate hyperparameter λk ∈ Λ, an e-value ek for the null hypothesis Hk in (2.15) is a nonnegative random variable satisfying the inequality E[ek | Hk ] ≤ 1, (2.40) where the expectation is taken over the randomness in the calibration data used to evaluate, conditioned on the null hypothesis Hk . Large values of the statistic ek provide evidence against the null hypothesis Hk . The defining property (2.40) implies that pk =
1 ek
(2.41)
is a p-value for hypothesis Hk . In fact, by Markov’s inequality we have 1 1 P ek ≥ Hk = P ≥ u Hk ≤ E[ek | Hk ] · u ≤ u. (2.42) u ek Therefore, by the definition (2.40), the reciprocal (2.41) of an e-value is a pvalue. However, the converse does not hold: For a p-value pk , it is generally not true that the reciprocal 1/pk is an e-value. E-values hence correspond to special types of p-values. As further discussed in Sec. 2.5.4 and Appendix A, e-values have useful properties that general p-values do not possess. Notably, e-values enable the post-hoc selection of the level of the test (Koning, 2024); and multiple e-values can be combined via averaging or through products (under independence), supporting optional continuation and stopping in sequential testing (Ramdas and Wang, 2025).
2.5.2
Construction
There are several principled constructions of valid e-values. We summarize the most relevant ones for hyperparameter selection.
31
1. E-values from concentration inequalities: Like p-values, e-values can be constructed directly from concentration bounds. Consider again the bounded-loss setting Lλ (·, ·) ∈ [0, 1]. We first recall Hoeffding’s lemma (Hoeffding, 1963). Lemma 2.5 (Hoeffding’s lemma). Let X be a random variable such that a ≤ X ≤ b almost surely. Then for any η ∈ R, the inequality 2 η (b − a)2 (2.43) E exp η(X − E[X]) ≤ exp 8 holds. Fix any η > 0 and define the statistic 2 bn (λk )) − η n . ek (η) = exp ηn(α − R 8
(2.44)
To verify that ek (η) is an e-value, note that under the null Hk we have the bn (λk )] ≥ α. Since the losses are bounded in [0, 1], Lemma 2.5 inequality E[R implies that, for any η > 0, 2 h i bn (λk )) Hk ≤ exp η n . (2.45) E exp ηn(α − R 8 Dividing both sides by exp(η 2 n/8) yields E[ek (η) | Hk ] ≤ 1,
(2.46)
so that ek (η) satisfies the defining property (2.40). bn (λk ) produce exponentially large eLarge positive deviations of α − R values ek (η), thereby providing strong evidence against the null. The parameter η controls the trade-off between sensitivity to small deviations and robustness to variability. In practice, the parameter η may be optimized, discretized over a grid and averaged, or selected via mixture constructions to improve power while preserving validity (Howard et al., 2021; Ramdas et al., 2023; Waudby-Smith and Ramdas, 2024).
32
2. Calibrating P-values into E-values: Any p-value can be transformed into an e-value using an e-calibrator. Since e-values have additional properties as compared to p-values, this conversion typically yields statistics that are less powerful than the original p-values in detecting true null hypotheses. In other words, the price to pay for benefiting from the special properties of e-values (see Sec. 2.5.4) is a decrease in power. Definition 2.3. Given a superuniform random variable U , function f : [0, 1] → [0, ∞) is an e-calibrator if the following inequality holds (2.47)
E[f (U )] ≤ 1. By this definition, if pk is a p-value, then
(2.48)
ek = f (pk ) is an e-value for the same null hypothesis. A common family of e-calibrators can be expressed as fκ (p) = (1 − κ) p−κ ,
κ ∈ (0, 1),
(2.49)
which can be shown to satisfy the condition (2.47) (Vovk and Wang, 2021). An optimal e-calibrator would yield the largest e-value fκ (p) across all possible p-values p ∈ [0, 1]. However, as illustrated in Fig. 2.5, within the family (2.49), no single value of κ yields a larger e-value fκ (p), for all possible values of p (Vovk and Wang, 2021). Therefore, the optimal choice of the parameter κ is non-trivial, and a common selection is κ = 1/2 (Yanchenko et al., 2025). More generally, admissible calibrators can be derived via convex duality arguments (Vovk and Wang, 2021). Calibrators allow one to leverage existing p-value constructions (Sec. 2.4), while inheriting the sequential and combination advantages of e-values, at the cost of a loss in power.
2.5.3
E-values for Single-Hypothesis Testing
For a single null hypothesis Hk : R(λk ) > α, an e-value ek can be used to define a level-δ test as 1 if ek ≥ , reject Hk ; otherwise accept Hk . δ 33
(2.50)
6
κ = 0.1 κ = 0.3 κ = 0.5 κ = 0.7 κ = 0.9
fκ (p) = (1 − κ)p−κ
5
4
3
2
1
0 0.0
0.2
0.4
0.6
0.8
1.0
p
Figure 2.5: E-calibrators from the family (2.49) for several values of κ ∈ (0, 1). Each curve maps a p-value p to an e-value according to (2.49). The figure illustrates that no single value of κ dominates uniformly over the entire range p ∈ [0, 1]: calibrators with larger κ produce larger e-values for very small p-values, while smaller κ yields larger e-values for moderate p-values. The validity of test (2.50) follows immediately from the definition (2.40) and from Markov’s inequality as 1 (2.51) P (reject Hk |Hk ) = P ek ≥ Hk ≤ δ E[ek | Hk ] ≤ δ. δ Thus, e-values provide type-I error control via the test (2.50).
2.5.4
Properties
E-values possess structural properties that distinguish them from p-values and make them particularly attractive in adaptive and post-selection settings. We highlight two key features: post-hoc level selection (Grünwald et al., 2020) and stability under convex combination (Vovk and Wang, 2021). The corresponding limitations of p-values that motivate these properties, as well as the underlying proofs, are reviewed in Appendix A. 1. Post-hoc selection of the testing level: A distinctive feature of evalues is that a single realized test statistic simultaneously supports valid 34
tests at all levels δ ∈ (0, 1). For the test (2.27) based on p-values, the type-I error guarantee is only valid if the level δ is specified in advance, prior to observing the data, and thus the p-values pk . When the significance level δ is chosen as a function of the p-value p, one has the phenomenon of p-hacking (Simonsohn et al., 2014), causing a violation of the type-I error guarantee. In contrast, with e-values, any rejection rule of the form (2.50) retains valid type-I error control even with a data-dependent choice of δ. In this sense, 1/e plays the role of a data-determined significance level. 2. Additivity and stability under convex combination: Another major advantage of e-values is their stability under convex combination. If e1 , . . . , eM are valid e-values for the same null hypothesis H, then the average M 1 X em (2.52) ē = M m=1 is again a valid e-value. Indeed, by linearity of expectation we can write M
E[ē | H] =
1 X E[em | H] ≤ 1, M m=1
(2.53)
proving that ē is also a valid P e-value. More generally, for any nonnegative weights w1 , . . . , wM satisfying M m=1 wm = 1, the weighted average ew =
M X
wm e m
(2.54)
m=1
remains a valid e-value (Vovk and Wang, 2021). Importantly, this stability holds without any independence assumptions among the e-values em .
2.5.5
E-values for MHT
E-values can be used in MHT in two closely related ways. First, since pk = 1/ek is a valid p-value by (2.42), any p-value based FWER-controlling procedure discussed in Sec. 2.4.3 can be applied to the induced p-values as AFWER (1/e1 , . . . , 1/eK ). This immediately yields a certified set Λ̂ with the same FWER guarantees as in Sec. 2.4.3.
35
For example, one may control FWER using the test (2.50) with modified thresholds |Λ| . (2.55) ek ≥ δ This guarantees the condition FWER ≤ δ as, by the union bound, we can write the inequality ! X [ |Λ| |Λ| FWER = P ek ≥ ≤ P ek ≥ Hk . (2.56) δ δ k∈K k∈K 0
0
By Markov’s inequality and the property (2.40) we have E[ek | Hk ] ≤ 1, |Λ| δ Hk ≤ . (2.57) P ek ≥ δ |Λ| Inserting (2.57) into (2.56) and summing over k ∈ K0 yields FWER ≤
|K0 | δ ≤ δ, |Λ|
(2.58)
which establishes the desired condition FWER ≤ δ. More powerful MHT procedures may be obtained by targeting false discovery rate (FDR) instead of the FWER. This is discussed in Sec. 2.6.
2.6
False Discovery Rate Control
While FWER control prevents any false certification with high probability via the requirement (2.10), it can be overly conservative when the number of candidate hyperparameters K is large. In such cases, it may be acceptable to tolerate a number of false certifications, as long as they constitute only a small fraction of the certified set. This motivates control of the false discovery rate (FDR).
2.6.1
Definition
To quantify the amount of false certification within the subset Λ̂ of selected hyperparameters, let Λ̂ ∩ Λ0 | denote the number of false rejections, i.e., the number of certified hyperparameters that are actually unreliable. We recall that Λ0 ⊆ Λ denotes the subset of unreliable hyperparameters. 36
The false discovery proportion (FDP) is the ratio FDP =
Λ̂ ∩ Λ0 |
max{1, |Λ̂|}
(2.59)
between the number of false discoveries and the total number of discoveries. The FDR is defined as the average # " Λ̂ ∩ Λ0 | , (2.60) FDR = E[FDP] = E max{1, |Λ̂|} where the expectation is over the calibration dataset. Controlling the FDR at level δ, i.e., FDR < δ, ensures that, on average, the fraction of unreliable hyperparameters inside the certified set Λ̂ is at most δ. Unlike FWER control, FDR control does not rule out the presence of any false certifications on a given run. Rather, it bounds their expected proportion. Definition 2.4 (FDR-controlling procedure). A procedure AFDR : [0, 1]K → 2K , mapping a collection of statistics T1 , . . . , TK to a set of selected hyperparameters Λ̂ = AFDR (T1 , . . . , TK ), is said to control the FDR at level δ if # " Λ̂ ∩ Λ0 | ≤ δ. (2.61) E max{1, |Λ̂|} Fig. 2.6 illustrates two outcomes corresponding to different realizations of the calibration data. In the first realization (left), the FDP is smaller, while in the second (right) the FDP is larger. The FDR condition (2.61) ensures that on average, the realized FDP is no larger than the specified outage rate δ.
2.6.2
FDR Control via P-values
The most widely used FDR-controlling method for p-values is the Benjamini– Hochberg (BH) procedure (Benjamini and Hochberg, 1995). The BH procedure is an example of a step-up procedure that tests the null hypotheses 37
Reliable hyperparameters (false null hypotheses)
Λ̂
Λ
Λ̂
Unreliable hyperparameters (true null hypotheses)
FDP =
Λ
1 5
FDP =
2 6
Figure 2.6: Schematic illustration of FDR control in hyperparameter selection. Each point represents a candidate hyperparameter, with green and red markers denoting truly reliable and unreliable configurations, respectively. The shaded region corresponds to the subset Λ̂ of selected hyperparameters. The FDR requirement (2.61) ensures that the FDP is on average no larger than the target δ. in increasing order of the corresponding p-values (Rice and Rice, 2007). To elaborate, let p(1) ≤ p(2) ≤ · · · ≤ p(K) denote the p-values {p1 , . . . , pK } sorted in increasing order. BH rejects the k ⋆ hypotheses with smallest p-values, i.e., those indexed by {(1), . . . , (k ⋆ )}, where k ⋆ is selected as k ⋆ δ . (2.62) k = max k : p(k) ≤ K Accordingly, the smallest p-value p(1) is compared with the same threshold as in the Bonferroni procedure, i.e., δ/K, while larger p-values are compared to an increasing threshold, namely kδ/K for p-value p(k) . Under independence, BH controls the FDR at level δ. When the p-values are arbitrarily dependent, a classical conservative modification is the Benjamini–Yekutieli (BY) procedure (Benjamini and Yekutieli, 2001). The BY procedure replaces δ in (2.62) by δ/cK , where cK =
K X 1 i=1
i
.
(2.63)
Equivalently, BY uses the tests p(k) ≤ kδ/KcK in (2.62). This ensures FDR 38
control without dependence assumptions, at the cost of generally reducing the number of discoveries.
2.6.3
FDR Control via E-values
The standard FDR-controlling rule for e-values is the e-BH procedure introduced in (Wang and Ramdas, 2022; Ramdas and Wang, 2025), which can be seen as a direct counterpart of the BH procedure for p-values. Let e(1) ≥ e(2) ≥ · · · ≥ e(|Λ|) be the sorted e-values in decreasing order. The e-BH procedure rejects the k ⋆ hypotheses with largest e-values, with |Λ| ⋆ , (2.64) k = max k : e(k) ≥ kδ with the convention k ⋆ = 0 if no such k exists. In contrast to the BH procedure for controlling the FDR via p-values as described in Sec. 2.6.2, e-BH controls FDR at the target level δ under arbitrary dependence among the e-values, without requiring a correction term as in the BY procedure (see Appendix C.2 for a proof). Variants and refinements of e-value FDR control include adaptive and weighted versions, as well as procedures that combine e-values across groups or along structured graphs (Wang and Ramdas, 2022). These methods inherit robustness to dependence and compatibility with optional stopping (see Sec. 2.5.4).
2.7
Summary
This chapter introduced LTT, a statistically principled approach to hyperparameter selection based on MHT. The central idea is to associate each candidate hyperparameter with a null hypothesis expressing violation of the desired risk constraint, and to certify only those candidates for which the null can be rejected with controlled error. Upstream procedures generate a finite candidate set using arbitrary heuristics, optimization routines, or domain knowledge. Downstream, the calibration data are used to construct valid marginal evidence measures, either p-values or e-values, one per candidate hyperparameter. An MHT procedure is then applied to control global error, yielding a certified set of hyperparameters. 39
When the testing rule controls the FWER, the resulting certified set enjoys a finite-sample post-selection guarantee: with high probability, every hyperparameter in the certified set satisfies the prescribed risk requirement. Any (possibly data-dependent) choice within that set therefore remains riskcontrolling. If FDR control is used instead, the guarantee becomes weaker but potentially less conservative, allowing larger certified sets. We discussed two complementary forms of marginal evidence. P-values rely on superuniform tail bounds, and connect naturally to classical concentration inequalities. E-values rely on expectation bounds, and are particularly well suited to sequential or adaptive settings due to their stability under optional stopping and averaging. Algorithm 2 summarizes the full LTT hyperparameter selection pipeline. Its modular structure highlights a core message of this chapter: statistical validity can be layered on top of arbitrary hyperparameter generation strategies, provided that the final deployment decision is restricted to the certified set produced by a valid multiple testing rule.
40
Algorithm 2 Learn-Then-Test (LTT): Reliable hyperparameter selection via multiple hypothesis testing Input: candidate set Λ = {λ1 , . . . , λ|Λ| }; calibration data {(Xi , Yi )}ni=1 ; risk threshold α; error level δ; error type err ∈ {FWER, FDR}; errorcontrolling MHT procedure Aerr (·) at level δ; selection algorithm Asel (·), possibly data-dependent Output: certified set Λ̂ ⊆ Λ and a deployed hyperparameter λ̂ ∈ Λ̂ (if nonempty) for j = 1, . . . , |Λ| do Compute empirical risk n
X bn (λj ) = 1 Lλj Xi , Yi R n i=1 Compute a p-value pj or e-value ej for the null hypothesis Hj : R(λj ) > α end for |Λ| |Λ| Apply Aerr to {pj }j=1 or {ej }j=1 and obtain the subset Λ̂ = Aerr (p1 , . . . , p|Λ| ) or Λ̂ = Aerr (e1 , . . . , e|Λ| ) if Λ̂ ̸= ∅ then Choose λ̂ = Asel (Λ̂) ∈ Λ̂ end if
41
Chapter 3 Applications The previous chapters introduced a statistical framework for reliable hyperparameter selection. The central idea is to move from best-effort tuning methods, which optimize empirical performance, to procedures that provide explicit reliability guarantees under finite calibration data. This chapter presents representative applications of statistically valid hyperparameter selection. For each application, we describe the underlying system, define the relevant hyperparameters and performance metrics, and show how the statistical framework developed in the previous chapters can be applied to obtain reliability guarantees for deployment. Specifically, Sec. 3.1 applies LTT to image classification on the Fashion-MNIST dataset, and Sec. 3.2 considers a wireless scheduling application based on real packet-delay data.
3.1
Image Classification
We begin with an image-classification example based on the Fashion-MNIST dataset (Xiao et al., 2017). Fashion-MNIST is a standard benchmark consisting of grayscale images of size 28 × 28 from ten clothing categories, including T-shirts, pullovers, coats, sandals, bags, and ankle boots. For each input image X, the model outputs a class label Ŷλ (X) determined by hyperparameter configuration λ. In this experiment, performance is measured through the 0–1 loss Lλ (X, Y ) = I{Ŷλ (X) ̸= Y }. (3.1)
Specifically, the loss for a test point (X, Y ) is equal to 0 if the true label Y is estimated correctly, and 1 otherwise. Throughout this example, we set the 42
target reliability level to α = 0.2, and the target outage rate to δ = 0.2. The classifier is a multinomial logistic regression model (Hosmer Jr et al., 2013) applied to principal component analysis (PCA) (Abdi and Williams, 2010) features extracted from the image. Hence, each candidate hyperparameter is a pair λ = (d, C), (3.2) where d denotes the number of retained principal components, and C is the inverse regularization coefficient of the classifier. We consider a small finite candidate set obtained from the grid d ∈ {5, 20, 80},
C ∈ {0.02, 0.2, 2, 10},
(3.3)
yielding a total of 12 candidate configurations. The available data are divided into three disjoint parts. A training split is used to fit all candidate models, and a separate calibration split is used for hyperparameter selection. Finally, an independent evaluation split is reserved for testing the selected hyperparameters. LTT uses Algorithm 2 by computing p-values using the Hoeffding bound (2.22) and using the Bonferroni correction (2.31) to control the FWER (2.2). The conventional E-HPO baseline (Algorithm 1) simply selects the hyperparameter with the lowest empirical risk. Among the set Λ̂ of hyperparameters returned by Algorithm 2, we pick the one with the smallest empirical risk as the selected hyperparameter. Fig. 3.1 reports the distribution of the empirical risk obtained by the selected hyperparameters over 100 random splits of the dataset. The dashed vertical line marks the target level α = 0.2, and the shaded portions show the mass of the distributions corresponding to violations of the reliability requirement. Conventional E-HPO returns hyperparameters that fail to meet the requirement α = 0.2 on the average 0-1 loss for a fraction 0.53 of the test runs, while LTT successfully guarantees an outage rate of 0.03, which is well below the target δ = 0.2. Fig. 3.2 complements these results with representative images from the independent evaluation set. For each image, we report the ground-truth label together with the predictions produced by the hyperparameters chosen by conventional E-HPO and LTT. Consistent with the distributional comparison in Fig. 3.1, E-HPO produces models that can make more mistakes on visually ambiguous items. 43
Density (over calibration datasets)
α = 0.2
20
E-HPO LTT
outage rate = 0.53
15
> δ = 0.2
10
outage rate = 0.03
< δ = 0.2
5
0 0.100
0.125
0.150
0.175
0.200
0.225
0.250
0.275
ˆ of the selected hyperparameter ∏ ˆ Risk R(∏)
Figure 3.1: Distribution of the empirical risk of the hyperparameters selected by conventional E-HPO (Algorithm 1) and LTT (Algorithm 2), evaluated over many random batches from an independent evaluation set on FashionMNIST. E-HPO violates the reliability requirement in a fraction 0.53 of the test runs, exceeding the target δ = 0.2. In contrast, LTT successfully guarantees an outage rate of 0.03, which is well below the target δ = 0.2.
3.2
Wireless Scheduling
We now study an engineering application drawn from the wireless communications domain. Specifically, we consider a radio access scheduling problem based on the Nokia wireless suite (Valcarce, 2020) studied in (Farzaneh et al., 2024). In this setting, hyperparameters control the behavior of a learningbased scheduler that allocates wireless resources among users. We consider a downlink wireless system in which a base station must allocate radio resources to a set of user equipments (UEs). At every transmission time interval, the base station assigns a number of resource blocks to active users according to a scheduling policy. Each episode consists of a sequence of time intervals during which packets arrive, are buffered, and are scheduled for transmission. The scheduling policy is implemented by the learning-based agent described in (Sant Ana and Marchenko, 2020) whose behavior depends on a
44
True label: Shirt
True label: Trouser
True label: Bag
True label: Pullover
True label: Ankle boot
E-HPO: Bag LTT: Shirt True label: Shirt
E-HPO: Trouser LTT: Trouser True label: T-shirt/top
E-HPO: Bag LTT: Bag True label: T-shirt/top
E-HPO: Pullover LTT: Pullover True label: Shirt
E-HPO: Ankle boot LTT: Ankle boot True label: Shirt
E-HPO: Coat LTT: Shirt
E-HPO: Dress LTT: T-shirt/top
E-HPO: T-shirt/top LTT: T-shirt/top
E-HPO: Coat LTT: Shirt
E-HPO: T-shirt/top LTT: T-shirt/top
Figure 3.2: Representative Fashion-MNIST images from the independent evaluation set, shown together with the ground-truth class and the predictions produced by models obtained with the hyperparameters selected via conventional E-HPO and LTT. vector of hyperparameters λ = (λ1 , λ2 , λ3 , λ4 ).
(3.4)
Each component of vector λ controls the relative weight assigned to a specific term in the scheduler’s reward model. Referring to (Sant Ana and Marchenko, 2020) for details, hyperparameter λ1 weighs a term that accounts for channel-quality; hyperparameter λ2 weighs a term that grows with queue backlog; hyperparameter λ3 weighs a term that depends on waiting time; and hyperparameter λ4 weighs a term that encourages fairness among UEs. To evaluate the performance of a hyperparameter configuration λ, we define a risk function based on packet delays experienced by UEs belonging to the most stringent quality-of-service (QoS) class. Specifically, the risk is defined as R(λ) = E[Lλ (X, Y )], where Lλ (X, Y ) is the average packet delay (in ms) incurred during an episode under hyperparameter λ. In the experiments presented below, we set the maximum tolerated average delay to α = 10 ms, reflecting a typical latency requirement for delaysensitive traffic (Series, 2017). Moreover, the candidate hyperparameter set is constructed by scaling a baseline configuration λ⋆ obtained from the optimization procedure proposed in (Sant Ana and Marchenko, 2020). Specif45
E-HPO mean
Target α LTT mean
Figure 3.3: Distribution of individual packet delays observed on a single run obtained using hyperparameters selected via E-HPO and LTT. ically, we consider all configurations of the form λ = (a1 λ⋆1 , a2 λ⋆2 , a3 λ⋆3 , a4 λ⋆4 ) with scaling coefficients ai ∈ {1/2, 1, 3/2, 2}. This results in a candidate set containing K = 256 hyperparameter configurations. Using the boundedness of the delay-based loss, we construct p-values via Hoeffding’s inequality as described in Chapter 2. We then apply the Bonferroni correction (2.31) to these p-values to control the FWER at level δ = 0.2. Fig. 3.3 illustrates the distribution of the packet delays for models obtained using the hyperparameter chosen by E-HPO (Algorithm 1) and by LTT (Algorithm 2) over the test dataset. It can be seen that, while the empirical mean of the delay for the hyperparameter chosen by LTT is successfully controlled below the threshold α = 10 ms, the average packet delay for the hyperparameter chosen by E-HPO is 10.9 ms, which is larger than the threshold α = 10 ms. This highlights the fact that E-HPO does not provide any statistical guarantees on the hyperparameters it outputs. To further see this, we repeat this experiment over 100 random splits of the dataset, and plot the distribution of the empirical mean of the delay of the hyperparameters chosen by E-HPO and LTT over the test dataset. This 46
Target α
outage rate = 0.66
> δ = 0.2
Figure 3.4: Distribution of the average delay obtained by the hyperparameters selected via E-HPO and LTT on 100 random splits of the dataset. distribution, illustrated in Fig. 3.4, shows that in a fraction 0.66 of runs, E-HPO exhibited an empirical average above the target α = 10 ms, which is well above the target outage rate of δ = 0.2. On the other hand, LTT does not fail, keeping the outage rate below the target δ = 0.2.
47
Chapter 4 Beyond Average Risk In Chapter 2, we described LTT, a formal reliable hyperparameter selection approach aimed at controlling the average risk (2.4) (see Algorithm 2). A hyperparameter was declared reliable if its expected loss did not exceed a user-specified threshold α as per (1.3), and statistical validity was achieved by testing the null hypotheses (2.15) with control of FWER or FDR. While the average risk is a natural and widely adopted performance measure, it is often insufficient for modern AI deployments. In fact, in many applications, reliability concerns focus not on the mean behavior of the system, but rather on tail events, constraint violations, or more general functionals of the loss distribution. In this chapter, we develop this generalization of LTT by first introducing a unified methodological framework, and then exploring it along two main directions. First, we consider quantile risk control, which replaces the average risk with a specified quantile of the loss distribution, thereby enabling guarantees on tail behavior in Sec. 4.4. Second, we study reliability constraints involving information-theoretic quantities, with particular emphasis on the information bottleneck framework, where relevance is measured through mutual information in Sec. 4.5.
4.1
Motivation
The central question of this chapter is the following: Can the MHT-based hyperparameter selection procedure introduced in Chapter 2 be extended beyond average risk to certify hyperparameters under more general reliability 48
criteria? For example, settings of interest may include the following: • In safety-critical systems, one may wish to control the probability that the loss exceeds a critical threshold, rather than its average (Amodei et al., 2016; Varshney, 2016). • In latency-sensitive applications, guarantees may be required on highpercentile delays, e.g., 95th or 99th percentiles, not only on the mean (Dean and Barroso, 2013; Cardwell et al., 2000; Bennis et al., 2018). • In information bottleneck learning, the reliability requirement may involve information-theoretic quantities such as mutual information (Tishby et al., 2000; Saxe et al., 2019). • In fairness-aware systems (Hardt et al., 2016; Barocas and Selbst, 2016), constraints may involve group-conditional risks rather than a single global average. These examples share a common structure: reliability is expressed not as a bound on the average loss E[Lλ (X, Y )], but as a constraint on a more general functional R(λ) of the distribution of the loss Lλ (X, Y ), which may represent a quantile, a tail probability, a divergence, or an information-theoretic measure. The key insight is that the MHT framework of Chapter 2 does not fundamentally depend on the specific form of the risk functional. Rather, it requires only the ability to construct valid test statistics for null hypotheses of the form Hk : R(λk ) > α, (4.1)
where R(λ) can be any general functional derived from the distribution of the loss Lλ (X, Y ).
4.2
General Reliability Functionals
Let Lλ denote the loss induced by hyperparameter λ. As in the previous chapters, the random variable Lλ may be a function of input-output variables X and Y as Lλ = Lλ (X, Y ), but the framework here is more general. It encompasses, e.g., unsupervised or self-supervised learning settings, in 49
which the loss depends only on the input variable X. Let also Pλ denote the distribution of the random variable Lλ . We are interested in reliability measures of the form R(λ) = Φ(Pλ ) , (4.2) where Φ is a functional mapping a probability distribution to a real number. The reliability requirement takes the unified form λ is reliable
⇐⇒
R(λ) ≤ α.
(4.3)
This formulation encompasses many practically relevant notions of reliability, including the average risk R(λ) = E[Lλ ] studied so far.
4.3
Confidence Bounds and Inversion-Based Testing
This section reviews a useful approach to construct p-values and e-values for the null hypothesis Hλ : R(λ) > α, (4.4) where R(λ) is a general risk measure as defined in Sec. 4.2. Assume that, based on calibration data Dcal , we can construct a one-sided upper confidence bound Uε (λ) on the reliability measure R(λ) such that the inequality P(R(λ) ≤ Uε (λ)) ≥ 1 − ε (4.5)
holds for all probabilities ε ∈ (0, 1), where the probability is taken over the randomness of the calibration data. The specific construction of the upper bound Uε (λ) depends on the risk measure R(·), and we will provide specific examples in the next sections. Lemma 4.1. Given a family of upper bounds Uε (λ) for ε ∈ (0, 1) as in (4.5), a p-value pλ for the null hypothesis Hλ in (4.4) is obtained by inverting the confidence bound Uε (λ) as pλ = inf {ε ∈ (0, 1) : Uε (λ) ≤ α} .
(4.6)
In words, as illustrated in Fig. 4.1, the p-value pλ is the smallest confidence level at which the upper bound falls below α. 50
α Upλ (λ)
Uε (λ) Uε′ (λ) decreasing ε
Figure 4.1: Illustration of the inversion-based p-value construction (4.6) from a family of one-sided upper confidence bounds Uε (λ). For a fixed hyperparameter λ, by the definition (4.6), the bound Uε (λ) is nonincreasing in ε (arrow). The p-value pλ is defined as the smallest ε for which the bound drops below the target threshold α. Proof. Fix the outage rate δ ∈ (0, 1) and assume that hypothesis Hλ is true, i.e., R(λ) > α. By definition of the statistic (4.6), the event {pλ ≤ δ} is equivalent to the upper bound Uδ (λ) being smaller than α, i.e., {pλ ≤ δ} ≡ {Uδ (λ) ≤ α}.
(4.7)
Since we assume the inequality R(λ) > α, the event Uδ (λ) < R(λ) holds if we have Uδ (λ) ≤ α, i.e., {Uδ (λ) ≤ α} ⊆ {Uδ (λ) < R(λ)}.
(4.8)
Therefore, by (4.7) and (4.8), the probability of the event pλ ≤ δ is upper bounded by the probability of the event R(λk ) > Uδ (λk ), which in turn is upper bounded by δ due to (4.5), i.e., P(pλ ≤ δ) = P(Uδ (λ) ≤ α) ≤ P(R(λ) > Uδ (λ)) ≤ δ.
(4.9)
This establishes the validity of the p-values pλ in (4.6).
4.4
Quantile Risk Control
In many systems, controlling the mean is insufficient if rare but large failures are unacceptable. In this section, we describe a variant of LTT that can control the quantile risk.
51
4.4.1
Quantile Risk
We define the quantile risk R(λ) as
R(λ) = Rq (λ) = inf {t ∈ R : P(Lλ ≤ t) ≥ 1 − q} ,
(4.10)
i.e., as the (1 − q)-quantile of the loss Lλ . The objective of quantile risk control is to certify hyperparameters that violate the null hypothesis Hλ :
(4.11)
Rq (λ) > α,
where α is the target maximum latency. As an example, consider the setting in Fig. 4.2 in which a base station of a wireless system provides radio access to a group of users (see also Sec. 3.2). Consider as the loss Lλ the delay experienced by one of the users. A system that only ensures a mean delay below 30 ms does not prevent occasional larger delay spikes. This situation is illustrated in Fig. 4.2(a), where the average delay, across multiple users, is below 30 ms despite two users experiencing a delay larger than 30 ms. Instead, a system that controls the quantile risk as R0.1 (λ) ≤ 30 ms ensures that at least 90% of users experience delays below 30 ms. As illustrated in Fig. 4.2(b), this constraint explicitly limits the proportion of users experiencing high latency.
4.4.2
Confidence Bound and P-value for the Quantile Risk
In order to construct a p-value for the null hypothesis (4.11), we now obtain a one-sided upper confidence bound Uε (λ) as in (4.5) for the quantile risk R(λ) = Rq (λ), i.e., P(Rq (λ) ≤ Uε (λ)) ≥ 1 − ε,
∀ ε ∈ (0, 1).
(4.12)
For each hyperparameter λ ∈ Λ, write the losses evaluated on the calibration datasets as ℓi (λ), i = 1, . . . , n, and let ℓ(1) (λ) ≤ · · · ≤ ℓ(n) (λ) denote the corresponding sorted values. An upper bound Uε (λ) can then be obtained as the empirical (1 − q ⋆ (ε))-quantile of the calibration losses (Howard and Ramdas, 2022), i.e., Uε (λ) = ℓ(⌈n(1−q⋆ (ε))⌉) (λ), (4.13) with an adjusted outage level q ⋆ (ε) (Howard and Ramdas, 2022). Given the confidence bound (4.13), a p-value for the null hypothesis (4.11) is obtained as in (4.6). 52
36 ms 50 ms 36 ms 50 ms 1 ms1 ms (a)
28 ms 23 ms 28 ms 23 ms 29 ms 29 ms (b)
Figure 4.2: Illustration of mean versus quantile risk control for a wireless system. (a) The average delay across the users is below 30 ms, but two users experience a larger latency, showing that mean control alone does not prevent extreme outcomes. (b) Controlling the 0.1-quantile of the latency ensures that at least 90% of users experience delays below 30 ms, thereby limiting the proportion of high-latency events.
4.4.3
Example
We illustrate the difference between average-risk control and quantile-risk control using the wireless scheduling application introduced in Sec. 3.2. In this example, the performance metric of interest is the packet delay experienced by the highest-priority QoS class. As discussed in Sec. 4.4.1, the goal of the network operator is to ensure that packet delays remain below a target threshold with high probability. We compare LTT, reviewed in Chapter 2, which controls the average delay by enforcing the constraint E[Lλ ] ≤ α, with target α = 10 ms, with the quantile-risk control method described in this section. The latter, referred to as quantile LTT (QLTT), enforces the requirement R0.1 (λ) ≤ α, ensuring that at least 90% of packets experience delays below 10 ms. Fig. 4.3 shows the empirical distribution of packet delays obtained using the hyperparameters selected by the two procedures. The histogram is evaluated over test-time realizations of packet delays for a fixed calibration dataset. Note that this differs from the plot in Fig. 3.1, which describes the variability of the average risk across realizations of the calibration data. The hyperparameter selected using LTT achieves a mean delay below the target threshold. However, the distribution exhibits a heavy right tail, resulting in a 0.9-quantile that exceeds the desired latency target. In contrast, the hyperparameter selected using QLTT produces a distribution with significantly 53
LTT 0.9-quantile
Target α
QLTT 0.9-quantile
Figure 4.3: Distribution of packet delays obtained using hyperparameters selected by two statistically valid procedures in the wireless scheduling setting of Sec. 3.2. The blue histogram corresponds to average-risk control, while the red histogram corresponds to quantile-risk control. The dashed vertical lines indicate the corresponding 0.9-quantiles of the delay distributions. reduced tail behavior, ensuring that the 90th percentile of the delay remains below the target value α = 10 ms.
4.5
Information-Theoretic Constraints
In this section, we describe another variant of LTT that addresses the information bottleneck problem.
4.5.1
The Information Bottleneck Problem
The information bottleneck (IB) problem (Tishby et al., 2000; Saxe et al., 2019) formalizes representation learning as a trade-off between compression and relevance. To describe it, consider an input random variable X and a target variable Y . The goal is to extract from input X a compressed representation T that preserves information about the target variable Y . For example, input X may be a text, Y a topic of interest, and T a summary of the text that preserves information about topic Y . The IB problem leverages the information-theoretic measure of statistical dependence known as mutual information. Given two discrete random variables A and B with joint distribution P (A, B), the mutual information 54
Relevant information to be preserved
Compressed representation
Figure 4.4: Illustration of the Information Bottleneck setup (Tishby et al., 2000). The input X is mapped to a compressed representation T , while preserving information about the target variable Y . The objective is to balance compression I(X; T ) and relevance I(T ; Y ). is defined as I(A; B) =
X
P (a, b) log
a,b
P (a, b) , P (a)P (b)
(4.14)
where P (A) and P (B) are the marginal distributions obtained from the joint distribution P (A, B). With this definition, the IB problem seeks a mechanism PT |X that generates a representation T from input X by balancing two competing objectives: • Compression: Minimize the mutual information I(X; T ) so as to compress the representation T ; • Relevance: Maximize the mutual information I(T ; Y ), so that the representation T retains information about the target Y . Specifically, the IB problem is defined as the optimization problem in which the mutual information terms I(X; T ) and I(T ; Y ) are replaced by ˆ ˆ ; Y ), respectively: their estimates I(X; T ) and I(T ˆ ˆ ;Y ) min I(X; T ) − λI(T
PT |X
(4.15)
over the conditional distribution PT |X , where λ ≥ 0 is a hyperparameter. These can be obtained using a dataset of pairs (X, Y ), e.g., using plug-in or neural estimators (Belghazi et al., 2018; Poole et al., 2019). 55
The choice of the hyperparameter λ in (4.15) is dictated by the desired trade-off between relevance and compression. Ideally, hyperparameter λ should ensure that the solution of problem (4.15), which we denote as Tλ ∼ PTλ|X , ensures the relevance constraint I(Tλ ; Y ) ≥ α.
(4.16)
Accordingly, for every hyperparameter λ ∈ Λ, we define the null hypothesis Hλ :
I(Tλ ; Y ) < α.
(4.17)
Rejecting the null hypothesis (4.17) means certifying that hyperparameter λ satisfies the desired relevance requirement (4.16). As shown in (Farzaneh and Simeone, 2025b), statistically valid testing for (4.17) can be obtained by constructing a one-sided lower confidence bound on the mutual information I(Tλ ; Y ) (Stefani et al., 2014), and then inverting this bound to form valid p-values or e-values (see Sec. 4.3). This confidence bound is obtained by using a calibration dataset which is distinct from the dataset used for estimates in (4.15). Once a subset Λ̂ of reliable hyperparameters has been identified using this procedure, we choose the final hyperparameter as b Tλ ), λ⋆ ∈ arg min I(X; λ∈Λ̂
(4.18)
b where I(X; Tλ ) is the estimate of the compression term I(X; Tλ ) in (4.15). We refer to this approach as IB-LTT.
4.5.2
Example
We illustrate the IB-LTT using a variational IB model (Alemi et al., 2016), following the experimental setting detailed in (Farzaneh and Simeone, 2025b). We set a target relevance level α = 2.28 and outage level δ = 0.1. To visualize the performance of the different selection strategies, Fig. 4.5 reports the joint distribution of the mutual informations I(X; T ) and I(T ; Y ) evaluated across 100 realizations of the calibration dataset. In the figure, the relevance constraint I(T ; Y ) ≥ α is visualized by a vertical threshold at α. Outage events correspond to points that lie to the left of this threshold, i.e., trials (calibration dataset realizations) in which 56
8.6 8.6
8.55
E-HPO
IB-LTT
I(X; T )
8.50
I(X; T) XTC
I(X; T )
8.5 8.5 8.4 8.4
8.45
0
25 Density
Density
8.35
IB-LTT
8.3 8.3
8.40
8.2 8.2 2.1 2.1
5531High 5531 12471247 43014301 11141114 36103610 938 938 32853285 798 798 28682868 597 597 24282428 479 479 19621962 318 318 14621462 218 218 917 917 115 115 349 Low 349 31 31
2.2 2.2 2.3 2.3 YTC I(T Y );Y ) 0.07 ;I(T
25
LTT E-HPO IB-LTT
0.27
0 2.22
2.24
2.26
2.28 2.30 I(T ; Y )
2.32
E-HPO
8.60
2.34
Figure 4.5: Joint distribution of relevance and compression for the hyperparameter λ⋆ selected by E-HPO and IB-LTT across 100 independent trials. The horizontal axis shows the achieved relevance I(T ; Y ) and the vertical axis shows the compression I(X; T ). The vertical dashed line indicates the target relevance level α. the selected representation fails to meet the required relevance level. EHPO yields an empirical outage probability of approximately 0.27, indicating frequent violations of the relevance requirement (4.16). In contrast, IB-LTT concentrates the mass of the joint distribution in the figure to the right of the threshold, reducing the outage probability to about 0.07, thereby satisfying the desired reliability level.
4.6
Summary
This chapter extended the LTT framework beyond the classical setting of average risk control to accommodate more general and practically relevant notions of reliability. We showed that the MHT perspective introduced in Chapter 2 naturally generalizes to arbitrary risk functionals of the loss distribution, provided that suitable confidence bounds can be constructed. The key methodological insight is that statistical validity can be pre57
served by formulating reliability requirements in terms of hypotheses of the form R(λ) > α, and by constructing p-values via the inversion of one-sided confidence bounds. This yields a unified and modular approach, in which different reliability criteria can be handled by designing appropriate confidence bounds for the corresponding functional R(λ). We instantiated this framework along two main directions. First, we considered quantile risk control, which enables guarantees on tail behavior of the loss distribution. The resulting QLTT procedure provides protection against rare but severe failures, as illustrated in the wireless scheduling example, where it enforces constraints on high-percentile latency rather than on average delay. Second, we addressed reliability constraints involving information-theoretic quantities through the information bottleneck framework. The proposed IBLTT method certifies relevance in terms of mutual information with statistical guarantees, and then selects among reliable configurations by optimizing compression. This yields a principled approach to hyperparameter selection that mirrors the underlying IB objective while ensuring reliability. Overall, this chapter demonstrates that LTT is not limited to averagerisk guarantees, but can serve as a general-purpose framework for statistically valid hyperparameter selection under a broad class of reliability criteria, including tail risks, constraint violations, and information-theoretic objectives.
58
Chapter 5 Multi-Objective Hyperparameter Selection The previous chapters focused on selecting hyperparameters that satisfy a single reliability constraint, namely that the risk R(λ) lies below a userspecified threshold α. In many practical deployments, however, a single scalar objective is insufficient to capture the full range of system requirements. Modern AI systems often operate under multiple, potentially conflicting performance criteria. For instance, an LLM may need to be accurate, wellcalibrated, and computationally efficient (Rajendran et al., 2026); a wireless scheduler must balance latency, throughput, and fairness (Kuo and Liao, 2007); and a computer vision system must jointly optimize detection recall and segmentation quality (He et al., 2017). In such settings, the practitioner faces not one but several objectives, some of which are hard constraints to be satisfied with statistical guarantees, while others are soft objectives to be optimized in a best-effort manner. This chapter introduces a principled framework for multi-objective hyperparameter selection that extends the LTT methodology introduced in Chapter 2. As detailed in Sec. 5.1, the central challenge is to simultaneously satisfy a number of reliability constraints with statistical guarantees, while making a best effort at optimizing a number of additional unconstrained objectives. The chapter introduces Pareto testing (PT) (Laufer-Goldshtein et al., 2023) in Sec. 5.4. PT addresses this challenge by combining multi-objective optimization with sequential hypothesis testing to efficiently identify configurations on the reliability-performance frontier. Then, it describes reliability graph-based Pareto testing (RG-PT) (Farzaneh and Simeone, 2025a) in 59
Sec. 5.5. RG-PT further incorporates structured prior knowledge about expected reliability relationships among hyperparameters via a directed acyclic graph (Ramdas et al., 2019).
5.1
Multi-Objective Problem Formulation
We begin by formalizing the multi-objective hyperparameter selection problem. As in Chapter 2, let Λ = {λ1 , . . . , λK } denote a finite candidate set, and let fλ denote a pre-trained model operating under hyperparameter λ. In a multi-objective setting, we associate with each hyperparameter λ a collection of L risk functions Rl (λ) = E[Llλ (Z)],
l = 1, . . . , L,
(5.1)
where Z denotes a generic test-time data point and Llλ (Z) ∈ [0, 1] is a bounded per-sample loss for objective l. Note that, in a supervised learning setup, data point Z includes input X and output Y , i.e., Z = (X, Y ). Given a dataset D, the empirical estimate of Rl (λ) is computed as X bl (λ | D) = 1 Llλ (Z). R |D| Z∈D
(5.2)
We partition the L objectives into two groups: C • Reliability risk functions {Rl (λ)}Ll=1 : The first set of LC risk funcC tions must be controlled below user-specified thresholds {αl }Ll=1 . Accordingly, a hyperparameter λ is said to be reliable if the following inequalities hold.
Rl (λ) ≤ αl
for all l = 1, . . . , LC .
(5.3)
• Auxiliary risk functions {Rl (λ)}Ll=LC +1 : The remaining L − LC risk functions are unconstrained objectives that the practitioner wishes to minimize as a best-effort secondary goal. Fig. 5.1 illustrates a concrete example of multi-objective deployment in a wireless network. A base station serves multiple devices (UEs) and must simultaneously satisfy three system-level requirements (LC = 3), namely a packet error rate below 10−5 , a coverage above 95%, and a delay below 30 60
Packet error rate > 10−5
Coverage > 95 %
Maximize data rate
Delay < 30 ms
Figure 5.1: Example of multi-objective reliability requirements in a wireless network. A base station serving multiple devices (UEs) must simultaneously satisfy three system-level constraints, namely packet error rate, coverage, and delay, while maximizing the data rate. Multi-objective hyperparameter selection must certify configurations that satisfy all three constraints simultaneously with high probability, while making a best effort at maximizing the data rate. ms. Violating any of these three criteria can render the system unreliable for its intended use. Under these requirements, it is also desired to make a best effort at maximizing the data rate (L = 4, and hence L − LC = 1). Multi-objective hyperparameter selection is formalized by the optimization problem min {RLC +1 (λ), . . . , RL (λ)} λ∈Λ (5.4) subject to Rl (λ) ≤ αl ∀ l = 1, . . . , LC .
As with the single-objective case studied in the previous chapters, the risks Rl (λ) in (5.1) depend on the unknown data distribution and can only be estimated from finite calibration data. The key challenge is therefore to address problem (5.4) using only calibration data Dcal , while providing formal statistical guarantees on the reliability constraints (5.3) in the optimization (5.4). Definition 5.1 ((α, δ)-risk-controlling configuration). A hyperparameter λ̂ ∈ Λ selected using calibration data is said to be (α, δ)-risk-controlling for the 61
C risks {Rl (λ)}Ll=1 , where α = (α1 , . . . , αLC ), if the following condition holds. P Rl (λ̂) ≤ αl ∀ l = 1, . . . , LC ≥ 1 − δ, (5.5)
where the probability is over the randomness in the calibration data. Definition 5.1 generalizes Definition 2.1 from Chapter 2 to the case of multiple simultaneous reliability constraints.
5.2
Pareto Optimality and the Pareto Frontier
Before introducing the testing procedures, we recall the notion of Pareto optimality that underlies multi-objective optimization (Deb, 2011). Given a set of risk functions {Rl (λ)}Ll=1 , for any two hyperparameters λ and λ′ ∈ Λ, we say that hyperparameter λ′ dominates hyperparameter λ, written λ′ ≺ λ, if Rl (λ′ ) ≤ Rl (λ) for all l,
and Rl (λ′ ) < Rl (λ) for at least one l.
(5.6)
That is, hyperparameter λ′ is at least as good as hyperparameter λ on every objective and strictly better on at least one objective l ∈ {1, . . . , L}. The Pareto optimal set ΛPar consists of all non-dominated hyperparameters, i.e., ΛPar = {λ ∈ Λ : ∄ λ′ ∈ Λ with λ′ ̸= λ such that λ′ ≺ λ} .
(5.7)
Accordingly, the hyperparameter settings in the set ΛPar capture the best achievable trade-offs among all objectives. Any hyperparameter outside the set ΛPar is dominated and can be discarded without loss of optimality. Fig. 5.2 illustrates the Pareto frontier for a two-objective setting with R1 (λ) and R2 (λ). Dots represent the risk pairs (R1 (λ), R2 (λ)) achievable with some choice of hyperparameter λ ∈ Λ. Configurations on the frontier, displayed as green dots, represent the best achievable trade-offs between the two risks: no other configuration simultaneously improves both objectives. Returning to the multi-objective optimization formulation in problem (5.4), assume now that R1 (λ) is a reliability risk function, while R2 (λ) is an auxiliary risk function, i.e., we have LC = 1 and L = 2. Then, as shown in Fig. 5.2, only the configurations with R1 (λ) ≤ α are feasible for problem (5.4) (shaded area), and the solution of problem (5.4) corresponds to the dot marked with an asterisk. 62
R2 (λ)
*
α
R1 (λ)
Figure 5.2: Illustration of the Pareto frontier in a two-objective setting with one constrained objective R1 (λ) (to be controlled below α) and one free objective R2 (λ) (to be minimized). Each dot represents the risk pair (R1 (λ), R2 (λ)) attained with some hyperparameter choice λ. The Pareto frontier (green dots) identifies the hyperparameters λ yielding the best achievable trade-offs. The shaded region marks configurations that satisfy the reliability constraint R1 (λ) ≤ α.
5.3
Multi-Objective Hypothesis Testing
As discussed in the previous section, problem (5.4) must be addressed using only estimates of the risks based on calibration data. To account for this, in order to enforce the constraints in (5.4), we adopt an MHT framework in which the null hypothesis for each candidate hyperparameter λk ∈ Λ generalizes the single-risk hypothesis in (2.15) as Hk :
∃ l ∈ {1, . . . , LC } such that Rl (λk ) > αl .
(5.8)
Rejecting hypothesis Hk means certifying that hyperparameter λk satisfies all reliability constraints (5.3) simultaneously. As in Chapter 2, testing for hypothesis Hk can be carried out using pvalues or e-values. A p-value for the combined null hypothesis (5.8) can be obtained by taking the maximum of the individual p-values for the constituent null hypotheses Rl (λk ) > αl for all l ∈ {1, . . . , LC }. Conversely, an e-value for the null hypothesis (5.8) can be evaluated as the minimum of the individual e-values. 63
Focusing on the case of p-values, let pl,k be a valid p-value for the hypothesis Hk,l : Rl (λk ) > αl (5.9)
for each l = 1, . . . , LC , as described in Chapter 2. Then, the combined statistic pk = max pl,k (5.10) 1≤l≤LC
is a valid p-value for the null hypothesis Hk in (5.8).
Lemma 5.1 (Combined p-value validity). If pl,k is a valid p-value for hypothesis Hk,l in (5.9) for each l ∈ {1, . . . , LC }, then the statistic (5.10) satisfies the superuniformity condition P(pk ≤ u | Hk ) ≤ u for all u ∈ [0, 1],
(5.11)
and is thus a p-value for the null hypothesis Hk in (5.8).
Proof. Let I ⊆ {1, . . . , LC } denote the set of indices l for which the null hypothesis Hk,l is true, i.e., for which Rl (λk ) > αl . Under the combined null Hk , the set I is non-empty. For any u ∈ [0, 1], we have P(pk ≤ u | Hk ) = P max pl,k ≤ u Hk (5.12a) 1≤l≤LC
≤ P(pl∗ ,k ≤ u | Hk,l∗ ) ≤ u,
(5.12b) (5.12c)
where l∗ ∈ I indicates any true null hypothesis Hk,l∗ , i.e., l∗ ∈ I. The inequality (5.12b) holds because the event {pl∗ ,k ≤ u} includes the event {maxl pl,k ≤ u}, and hence has larger or equal probability. The final inequality (5.12c) follows from the superuniformity property (2.19) of the p-value pl∗ ,k under the null hypothesis Hk,l∗ .
5.4
Pareto Testing
By Lemma 5.1, the combined p-values {pk }K k=1 can be fed directly into any of the MHT procedures reviewed in Sec. 2.4.3, such as Bonferroni correction (2.31) or FST (2.37), to obtain a certified set Λ̂ of hyperparameters that are simultaneously reliable across all LC constraints with probability at least 1 − δ. 64
However, testing all K hyperparameter configurations via Bonferroni or standard FST can result in a small certified set Λ̂, especially when the number of candidates K and the number of constrained objectives LC are large. A small set Λ̂, or even an empty set Λ̂, offers little room for optimizing the L − LC auxiliary objectives. PT (Laufer-Goldshtein et al., 2023) addresses this efficiency challenge by focusing only on the configurations that are estimated to lie on the Pareto frontier in the joint objective space (see Fig. 5.2). The Pareto frontier is estimated via held-out data, and the restriction of candidate hyperparameters on the estimated Pareto frontier can reduce the number of hypotheses to test, thereby improving statistical power.
5.4.1
Overview
PT splits the calibration dataset Dcal into two disjoint subsets Dopt and DMHT , of respective sizes nopt and nMHT , as Dcal = Dopt ∪ DMHT .
(5.13)
Then, PT proceeds along the following two stages. Stage 1 (Optimization): As illustrated in Fig. 5.3, first, PT addresses the multi-objective optimization problem (5.4) by replacing all risks, both constrained and unconstrained, with empirical estimates obtained using the dataset Dopt . This can be done with any multi-objective optimizer, including exhaustive grid search for small candidate sets or methods such as Bayesian multi-objective optimization for larger spaces (Lindauer et al., 2022). Assuming that the dataset Dopt is sufficiently large, the resulting estimated Pareto set Λ̂Par ⊆ Λ contains only the most promising configurations, and is typically a small fraction of the full set Λ. C Considering only the estimated reliability risk functions {Rl (λ)}Ll=1 , PT Par orders the candidate hyperparameters λk ∈ Λ̂ from most likely to be reliable to least likely to be reliable. This step can be done using different measures of reliability based on empirical risk estimates obtained from dataset Par Dopt . Specifically, PT builds a p-value popt l,k for each configuration λk ∈ Λ̂ opt using dataset D . The combined p-values (5.10) for the null hypothesis in (5.8), i.e., opt popt (5.14) k = max pl,k , 1≤l≤LC
65
are then used to order the hyperparameters in set Λ̂Par from the smallest p-value (5.14) to the largest. Stage 2 (Testing): Using the disjoint dataset DMHT , as shown in Fig. 5.3, PT applies FST, as per (2.37), on the candidates λk ∈ Λ̂Par using the order identified in Stage 1. To this end, combined p-values pMHT = max pMHT k l,k 1≤l≤LC
(5.15)
are computed for each λk ∈ Λ̂Par using dataset DMHT , and FST is applied using the statistics (5.15). This yields a certified subset Λ̂ ⊆ Λ̂Par . Finally, within the certified set Λ̂, any hyperparameter λ̂ ∈ Λ̂ can be selected for deployment while satisfying the (α, δ) guarantee (5.5). In order to address problem (5.4), the configuration λ̂ is then selected by optimizing a suitable combination of the empirical estimates for the auxiliary risks {Rl (λ)}Ll=LC +1 . The PT procedure is summarized in Algorithm 3. Overall, the statistical efficiency of PT over naive application of LTT to the full candidate set Λ stems from the fact that the Pareto set Λ̂Par is typically much smaller than the full candidate set Λ, and that ordering configurations on the Pareto set places the most reliably performing configurations at the beginning of the testing sequence before the procedure stops at the first failure.
5.4.2
Statistical Guarantee
The following result establishes that PT achieves the (α, δ)-risk-controlling guarantee of Definition 5.1. Theorem 5.2 (Validity of Pareto Testing). Let Dopt and DMHT be disjoint i.i.d. subsets of the calibration data. Then, every hyperparameter λ̂ ∈ Λ̂ returned by PT (Algorithm 3) is (α, δ)-risk-controlling in the sense of Definition 5.1. Proof. Since datasets Dopt and DMHT are disjoint and i.i.d., the ordering of the hyperparameters in set Λ̂Par computed over dataset Dopt is independent of the p-values pMHT computed over DMHT . The combined p-values pMHT are k k therefore valid for the composite null hypotheses Hk in (5.8) by Lemma 5.1. Applying FST at level δ over the fixed predetermined ordering then controls the FWER at level δ as proved in Section 2.4.3. Hence, with probability at least 1 − δ, every λ ∈ Λ̂ satisfies all reliability constraints (5.3). 66
Algorithm 3 Pareto Testing (PT) (Laufer-Goldshtein et al., 2023) Input: Candidate set Λ; calibration data Dcal = Dopt ∪ DMHT ; risk thresholds α = (α1 , . . . , αLC ); error level δ Output: Certified set Λ̂ ⊆ Λ Stage 1: Optimization bl (λ | Dopt ) for all λ ∈ Λ and l = 1, . . . , L Compute empirical risks R bl (λ | Dopt )}L Compute Pareto frontier Λ̂Par using the empirical risks {R l=1 Par for each λk ∈ Λ̂ do LC opt Compute combined p-value popt k = maxl=1 pl,k end for Order the hyperparameters in set Λ̂Par by increasing popt to obtain the k (1) (2) (|Λ̂Par |) ordered sequence (λ , λ , . . . , λ )
k←1 for k = 1, . . . , |Λ̂Par | do LC MHT = maxl=1 pl,(k) for the k-th configuration λ(k) in the Compute pMHT (k) ordered sequence if pMHT ≤ δ then (k) Add λ(k) to Λ̂ else break end if end for return the certified set Λ̂ of hyperparameters
5.4.3
Example: Multi-Objective Wireless Scheduling
We revisit the wireless scheduling application introduced in Sec. 3.2 to illustrate the benefits of PT over single-objective LTT in a multi-objective setting. Recall that the system consists of a base station allocating radio resources to UEs across multiple QoS classes, with the hyperparameter vector λ = (λ1 , λ2 , λ3 , λ4 ) controlling the weights of different scheduling criteria. We consider a two-objective problem with LC = 2 and L = 2. The first reliability risk function R1 (λ) is the average packet delay of UEs in QoS class 1, which must be controlled below the threshold α1 = 10 ms. The second reliability risk function R2 (λ) is the average packet delay of UEs in QoS class 2, which must be controlled below the level α2 = 12 ms. The target failure 67
I
λ* T) I(X; T ) I(X; amirfar76 D D 1
1
September 2024
3September 2024
i=1 C5 ˆDOPT (X; D C5i Iˆi DOPT )) T ) (X;IT ) amirfar76 Iˆ TT(X; I(X; ⇤
I(X; T )
September 2024 amirfar76
4 Introduction
Introduction ⇤ IˆDIMHT (TT; Y) ) (X;
Iˆ (X; T )
I (T ; Y )
ord
I
amirfar76 amirfar76 2024 1 I(X; 3 T ) September
IˆDMHT (X; T )
amirfar76
ng
1
1
Te amirfar76 sti
nota
I(T ; Y )
I(X; T )
September 2024 Introduction
MHT
Introduction
D
Introduction
Temp
1
(T ; Y ) amirfar76
I
DOPT 2
1
3
D Iˆ OPT (T ; Y )
2
am
* Septem
Introduction 4 5
T
1
I(X; T 1
D Iˆ OPT (X; T )
September 2
Te sti n
2
amirfar7
Introduction
DMHT 1
Temp2024 1 amirfar76 September amirfar76
I(T ; Y )
D
Te Introduction sti ng ord er D OPT
3
* DMHT I(T ; Y ) September 2024 DOPT 1 Introduction September 2024 September 2024 I(T ; Y ) amirfar76 September 3 3 * I(T ; Y ) D DOPT2024 ̂12 (λ) ̂2 (λ)1 Introduction MHT4 R R nota 4 ˆDOPT 1 Introduction 5 Introduction DMHT September 2024 DOPT I(T ; Y ) D T) I (X; 1 ) Introduction IˆˆDOPT (X; T ) 1Introduction 1 T 1 IˆIntroduction DOPT DOPT (X; D OPT 4 ˆ n OPT Temp 4 I (X; T) I (X; T ) 1 Introduction D 1 D = {(X , Y )} 2D
Iˆ DOPT (T ; Temp YD ) T) DOPT I(X; MHT OPT ˆ amirfar76
Temp Temp amirfar76
1
DOPT
I(X; T )
amirfar76
D Iˆ OPT (T ; Y )
MHT 2024 September
DTemp OPT
DOPT
D Iˆ OPT (X;amirfar76 T)
1
Temp 2 MHT Temp
1 1
1 Temp
(T1 ; YIntroduction )
1
Temp
1 September 2024 Temp 2 amirfar76 TempTemp Introduction
I(T ; Y )
(X; T )Iˆ
Introduction
D
September 2024
Iˆ OPT (T ; Y ) DMHT I(X; T )
I
Temp
amirfar76
1
September 2024
(T ; Y )
D
DTemp OPT
Temp IˆDOPT (T ; Y ) ˆDOPTDOPTamirfar76
I(X; T )
amirfar76
September 2024
DIˆDOPT (T ; Y ) IˆDOPT (X; T ) Iˆ OPT (X; T )
D I(T ; Y(X; ) T) Iˆ OPT
September 2024
MHT 2024 September
D
DOPT DOPT D IˆI(X; (TT; Y DOPT DOPT IˆˆDOPT (X; TD) OPT OPT )D)
DTemp OPT
DOPT
D Iˆ OPT (X; T )
DOPT
amirfar76 September 2024 I(T ; Y ) Introduction September I(X; T )2024 D OPT Temp ˆ I (T ; Y ) DTemp OPT DOPT DOPT OPT ˆ OPT 1 Introduction ˆ amirfar76 I (X; T ) I (X; T ) Introduction I(T ; Y ) amirfar76
1
1
Temp
D
Temp September D D 2024 Iˆ OPT (X; T )IˆDOPT (T ; Y 1 Introduction Iˆ )OPT (T ; Y )
(T ; Y ) Iˆ OPT (X; T ) DOPT
Temp I(X; T ) amirfar76
amirfar76
er D June1 2025 OPT Introduction amirfar76 ˆ I (T ; Y ) D MHT 2024 September
Introduction
September 2024
)
Introduction
1
Introduction
D Iˆ OPT (T ; Y )
1
T)
I(T ; Y
D Iˆ OPT (X
I(X
ˆDOPT
I
(T
I(T IˆˆDOPT DOPT 2I(X; T ) Iˆ2 OPT (T ; Y (T ) ;Y ) 5 D(X; DIˆ= {(X , YIiT)})i=1(T ; YD) MHT5IˆDOPT OPT D I OPT (T ; Y ) September 2024 D(T OPT; Y ) Iˆi OPT (X; T ) D OPT June; Y2025 D D ; Y ) I(T ˆD)OPT (T ) Iˆ OPT (T 3;IY Iˆ OPT ; ;YY(T )) ; Y ) Pareto frontierI(T DOPT I(T DOPT Sequential FWER-contro 3 1 2 Split calibration data Estimate using 3 D ˆ D OPT OPT D DOPT I . 1 MHT Introduction DOPT D D I(T ; Y 4) IˆMHT Iˆ OPTD(T ; Y (T ) ;Y ) 4 OPT MHT using DMHT DOPT ˆDOPT D 5DOPT 5 I (X; T ) DMHT Sequential FWER-controlling 3 1 Split calibration 2 Estimate data Pareto frontier using OPT 1OPT D ˆ I OPT. (X; T ) D DMHT IˆDOPT (X; T ) 1 ˆDOPT OPT T MHT usingD (X; 1) Introduction DMHT DOPT DOPTI calDOPT 2 Estimate Pareto frontier using D n3 n Sequential FWER-controlling ˆ OPT D = {(X , Y )} IˆDOPT 1 Iof the (X; T ) DOPT of IB-MHT: DOPT D = {(X DOPT 1 (TSplitting Figure 2:i=1Illustration operations ○ the calibration data s i , iYi )}i i=1 ˆ D 1 MHT using . I ; Y ) MHT D MHT 1 D ˆOPT ˆOPT D ˆ I (T ; Y ) D DOPT ̂ ̂ I (T ; Y ) MHT α D R (λ) R (λ) I (T ; Y ) ˆ D D 2 1 two disjoint subsets DOPT Iand○ D Approximating the Pareto frontier using the OPT 1(T OPT Figure 2: Illustration ofOPTthe operations of IB-MHT: Splitting calibration data set D into ;C Y1 ) ○ the MHT DOPT C D 1 DMHT C C DMHT OPT DOPT DOPT ˆDDn(X; D D ˆ OPT MHTPareto I (T ; Y ) cal D 3 2 (T ; Y ) and I T ) to form ⇤ ○ Applying sequential FWER-controlling 1Split subsets DIˆdataset and D ○ Approximating the frontier using the estimates OPT Sequential FWERoperationstwo of disjoint IB-MHT: ○ Splitting the calibration data set D into Estimate Pareto frontier D Split data set D = {(X , Y )} OPT OPT MHT i OPT 1i Optimization 2 Testing D i=1 ˆ ˆ D I (X; T ) D I (X; T ) D D MHT D MHT D OPT OPT D MHT D ˆ ˆ MHT ⇤ MHT controlling MHT using using . D D ˆ 3 I (T ; Y ) and I (X; T ) to form ⇤ ○ Applying sequential FWER-controlling algorithm 2 nd DMHT ○ Approximating the Pareto frontier using estimates OPTchoose the hyperparameter OPT 1 (X OPT the and then that minimizes I DMHT on ⇤OPT1 to form ⇤MHTDMHT .DMHT ⇤ DMHT ˆ D 3 to T ) to form on ⇤OPT ○ Applying sequential FWER-controlling algorithm D 1 (X; OPT ⇤OPT form ⇤MHT then choose the hyperparameter that minimizes I T ). Figure 5.3: and Illustration of the two stages of Pareto Testing (PT) for two ˆ DOPT I (T ; Y ) D DMHT ⇤ OPT ˆ D OPT 1 (X;reliability 1 then choose the hyperparameter that I T ). risk functions, i.e.,minimizes L = 2, with one risk function R1D(λ) and one ⇤ OPT D OPT I (T ; Y ) D auxiliary risk function D RMHT =MHT 1. Having partitioned the dataset 2 (λ), i.e., LC D D cal opt MHT MHT D into splits D and D , the empirical Pareto frontier DisMHT estimated 1 ⇤ DMHT I (X; T ) 1 opt using dataset D , yielding a set of candidate configurations ordered from 1 1 most to least likely to be reliable. Sequential MHT via 10 FST is 1 applied to 1 the ordered Pareto frontier using 10 dataset DMHT . Testing proceeds along the 1 1 10 frontier in the predetermined order 1 and stops at the first failure to reject the null hypothesis (5.8). Configurations tested before the first failure (dark 1 green) are certified as reliable, and the final deployed hyperparameter λ∗ is selected among them by considering secondary objectives. 1
MHT
MHT
1
1
r de
Introduction
or
1
1
1
OPT
ng sti Te
Introduction
1
ˆDOPT n
1
1
probability is δ = 0.1. We compare three procedures: PT, which controls both constraints simultaneously; LTT controlling only R1 (λ) ≤ α1 ; and LTT controlling only R2 (λ) ≤ α2 . Fig. 5.4 shows the joint distribution of the risks (R1 (λ̂), R2 (λ̂)) of the selected hyperparameter over 100 independent calibration splits for each method, with the reliability thresholds α1 and α2 shown as dashed lines. Reflecting their theoretical performance, the first version of LTT successfully controls the risk R1 (λ) below the target value α1 , but provides no guarantee on risk R2 (λ), with a fraction 0.83 of runs exceeding the target α2 . Similarly, the second instantiation of LTT controls the risk R2 (λ) but not 1 R1 (λ), on which it exhibits a violation rate of 0.87. In contrast, PT controls both risks simultaneously, with the joint distribution concentrated in the safe region defined by the constraints R1 (λ) ≤ α1 and R2 (λ) ≤ α2 .
68
LTT (controls R1 only)
LTT (controls R2 only)
PT (controls R1 and R2 )
16 R2 violation 0.83
ˆ (ms) R2 (∏)
14
Both violated 0.01
R2 violation 0.05
Both violated 0.04
R2 violation 0.09
Both violated 0.00
12
10
R1 violation 0.01
R1 violation 0.87
Æ1 = 10 ms Æ2 = 12 ms
8 6
8
10
12
14
R1 violation 0.05
Æ1 = 10 ms Æ2 = 12 ms 6
8
10
12
14
Æ1 = 10 ms Æ2 = 12 ms 6
8
10
ˆ (ms) R1 (∏)
ˆ (ms) R1 (∏)
ˆ (ms) R1 (∏)
(a)
(b)
(c)
12
14
Figure 5.4: Joint distribution of the risks (R1 (λ̂), R2 (λ̂)) of the selected hyperparameter over 100 calibration splits in the wireless scheduling setting of Sec. 3.2, for three methods: (a) LTT controlling only R1 (λ); (b) LTT controlling only R2 (λ); and (c) PT controlling both R1 (λ) and R2 (λ) simultaneously. Dashed lines mark the reliability thresholds α1 and α2 . The shaded region beyond the threshold lines corresponds to reliability violations. The fraction of runs violating each reliability constraint is annotated within the corresponding shaded region.
5.5
Reliability Graph-Based Pareto Testing
As explained in the previous section, PT orders hyperparameters based on held-out data. This ordering may be imprecise when such data are limited, and it fails to capture richer structural relationships that may be known to exist among hyperparameters. In fact, in many practical settings, structural knowledge about relative reliability is available before any calibration data are observed. For example, longer, or more detailed, prompt templates in LLMs are generally expected to be more reliable; less sparse model configurations are typically more expressive; and hyperparameter configurations with larger regularization coefficients tend to be more conservative. Such relationships define a partial ordering over the hyperparameter space in terms of expected reliability that can be exploited to improve the efficiency of the testing procedure. Reliability Graph-Based Pareto Testing (RG-PT) (Farzaneh and Simeone, 2025a) extends PT by encoding this structural knowledge in a directed acyclic graph (DAG), referred to as the reliability graph (RG). In an RG, each node 69
λ1
Expected reliability
λ1
Is the sentiment of this review positive or negative? {review_text}
λλ12
Is the sentiment of this review positive or negative? {review_text}
λλ13
Is the sentiment of this review positive or negative? {review_text}
λ4
Is the sentiment of this review positive or negative? {review_text}
λ5
Is the sentiment of this review positive or negative? {review_text}
λ6
Is the sentiment of this review positive or negative? {review_text}
Figure 5.5: Illustration of a reliability graph (RG) for prompt template selection in an LLM-based sentiment analysis task (Farzaneh and Simeone, 2025a). Each node λi represents a candidate prompt template, and a directed edge from λi to λj encodes the prior expectation that λi is more reliable than λj , i.e., more likely to elicit a correct response from the LLM. Prompt templates closer to the root nodes are longer and more detailed, and are thus expected to be more reliable. Templates closer to the leaves are shorter and cheaper in terms of token cost, but are expected to be less reliable. represents a candidate hyperparameter λi and a directed edge from node λi to node λj encodes the expectation that hyperparameter λi is more reliable than hyperparameter λj . The acyclicity of the graph is a natural requirement: reliability relationships cannot be circular. Moving from root nodes towards leaves, one encounters hyperparameters of decreasing expected reliability. All nodes at the same depth level of the DAG are considered to have approximately the same expected reliability. An example is shown in Fig. 5.5, and is detailed in Sec. 5.5.1. An outline of the algorithm can be found in Fig. 5.6. As detailed in (Farzaneh and Simeone, 2025a), the RG is constructed from the Pareto-optimal subset Λ̂Par using the held-out data split Dopt and optional prior information. Prior information is expressed in terms of preferences between pairs of hyperparameters. Depth levels in the RG are assigned by combining data-driven pairwise p-value comparisons with the prior pairwise preferences into a scalar reliability score per hyperparameter via the BradleyTerry (BT) model (Hunter, 2004). Directed edges between adjacent depth levels are then learned via non-negative Lasso regression (Tibshirani, 1996), selecting as parents of each node the hyperparameters at the previous depth level that are most predictive of its reliability. 70
Algorithm 4 Reliability Graph-Based Pareto Testing (RG-PT) (Farzaneh and Simeone, 2025a) Input: Candidate set Λ; calibration data Dcal = Dopt ∪ DMHT ; risk thresholds α; FDR level δ; number of DAG levels D; prior parameters (np , {ηij }) Output: Certified set Λ̂ ⊆ Λ
Stage 1: Compute Λ̂Par ⊆ Λ via multi-objective optimization using Dopt
Stage 2: Learn the RG over set Λ̂Par using dataset Dopt and prior preferences via the Bradley-Terry model and non-negative Lasso Stage 3: Run DAGGER on the RG using dataset DMHT with combined p-values (5.10) to obtain Λ̂
As shown in Fig. 5.6, once the RG is constructed, RG-PT performs MHT via the DAGGER algorithm (Ramdas et al., 2019), which operates on DAGs. DAGGER begins testing at the root nodes and proceeds level by level. If a hyperparameter is deemed unreliable, all of its descendants are automatically excluded from further testing. This allows multiple promising paths to be explored in parallel, unlike the single linear sequence followed by PT. DAGGER can control the FDR, as defined in Sec. 2.6, at any given target level δ. The procedure is summarized in Algorithm 4 and illustrated in Fig. 5.6. The following result states its formal guarantee. Theorem 5.3 (FDR control of RG-PT (Farzaneh and Simeone, 2025a)). The set Λ̂ returned by RG-PT meets the FDR constraint " # |Λ̂ ∩ Λ0 | ≤ δ, (5.16) E max{1, |Λ̂|} where Λ0 = {λ ∈ Λ : ∃ l s.t. Rl (λ) > αl } is the set of unreliable hyperparameters. This result holds regardless of the accuracy of the prior information or the quality of the learned RG structure. The proof follows directly from the FDR-controlling property of DAGGER (Ramdas et al., 2019).
71
DMHT
September 20241
D Iˆ OPT (T ; Y )
DMHT
3
2
I(T ; Y )
a
* Sep
4 * September12024Introduction
1 DIntroduction 4
1
I(X
I(T ; T
D Iˆ OPT (X; T )
I(T ; Y )
I(X; T )
DOPT 1
1
amirfar76
I(X; T )
September 2024
3
Introduction
2
Temp
amirf
Septemb
Introduction
er D OPT
1
amirfar76 September 2024
1
ord
D 1
D Iˆ OPT (T ; Y )
DTemp OPT
September 2024
amirfar76 Temp Introduction
4 amirfar76 I(X; TSeptember ) 1 2024 Introduction 3
* September 2024
amirfar76
1 Temp 2
Te sti ng
amirfar76 Temp
amirfar76
I(T ; Yamirfar76 )
1
3
D Iˆ OPT (X; T )
2
1 Temp
DOPT DI(X; MHT T )
DOPT
2
D
MHT Introduction
I DOPT
OctoberTemp2024
1
Temp
Introduction
DOPT
Introduction
amirfar76 September 2024
ˆDOPT (T ; Y )
DOPT
September 2024
Introduction
MHT
amirfar76
3 4 September 2024 1 Introduction DMHT I(T ; Y ) 1 Introduction 1 Introduction 4 4 1 n Introduction DMHT D = {(X , Y )} i i 5 i=1 1 Introduction 1 DOPT3 ˆDOPT
)
Introduction
3
Temp
ˆDOPT
MHT D
I (T ; Y ) Introduction Te sti Temp D OPT ng ord D er D amirfar76 Iˆ OPT (X; T ) OPT
amirfar76
1
1 Introduction Λ̂ Introduction
HT
Iˆ OPT (X; T )
Temp
amirfar76
DTemp OPT
1 Temp D2 Iˆ OPT (T ; YD ) DOPT Temp
September 2024
Temp
D1 Iˆ OPT (T ;amirfar76 Y) D
I(T ; Y )
amirfar76
September 2024
DMHT 2024 September
D OPT Iˆ OPT (X; TD) OPT
D DOPT D Iˆ OPT (T ; YD) Iˆ OPT (X; TD) OPTDOPT
DOPT
D Iˆ OPT (X; T )
September 2024
PT
D Iˆ OPT (T ; Y )
I(T ; Y )
amirfar76 October 2024
I(T ; Y )
I(X; T )
I(X; T ) D Iˆ OPT (T ; Y ) DOPTD
DOPT
Tem MHT 2024 September
) ;Y ) Iˆ(T ; Y(T
(X; T )I
Introduction
D Iˆ OPT (X; T )
I
I(X; T )
ˆDOPT DOPT
Introduction
1
T;Y )
PT
amirfar76
September 2024
ˆDOPT
MHT 2024 September
X; T )
D Iˆ OPT (
1
1
G
1
1
1
opt
R̂2 (λ | D
1
I 5 D Iˆ OPT (X; ) D T) λ Iˆ OPTT(X; OPT ˆ D 1 I (X; T ) Iˆ OPT ( λ ˆ λ I (X; I(X; T ) par 5D ) T) I (X; T ) IˆDOPTT(X; D OPT I Iˆ OPT Y) Iˆ (T ; Y (T )IˆD; OPT 5 OPT I(X; T ) D =IˆD {(X )}Tni=1 λi,(X; ) T) (T ; Y ) D5OPT 2IˆYDiOPT (X; D O D I(T ; Y ) ) λ(T 1 I5ˆ OPT Y ) DAGGER ; Y (T ) ;Pareto λ2dataIˆDOPT λ4(TIˆ;DY2OPT DO Sequential FWER-con λ 3 1 Split calibration Estimate frontier using D D ˆ OPT D OPT D 3 I DOPT DMHT DOPT I(T ; Y ) Iˆ OPT Iˆ OPT (T ; Y (T ) ; Yλ) MHT using DM DOPT 3 Sequential FWER-controlling 1 Split calibration data 4 λ5 2 Estimate using DOPT 1 ParetoDfrontier ˆ OPT DOPT DMHT Dusing 1 OPT ID . (X; T ) MHT D DOPT MHT 3 Sequential FWER-controlling 2 Estimate Pareto frontier using DOPT ata ˆ D OPT I (X; T ) 1 D IˆDOO OPT 1 Splitting the calibration data Figure 2: Illustration of using the Doperations of IB-MHT: ○ opt D MHT . 1 OPT MHT R̂1 (λ | 1D ) DOPT D D MHTPareto IˆDOPT (Tfrontier ; Y into ) 2 Approximating two Ddisjoint subsets Dof and DMHT ○ the using th 1OPT Figure 2: Illustration of IB-MHT: ○ Splitting the calibration data set D OPT OPTthe operations D 1 D OPT DM ˆ D D D MHT D OPT OPT OPT ˆ MHTPareto I (T ; Y ) D 3 2 1subsets Apply FDR-controlling Learn the RG Identify OPT 3 the operations IB-MHT: ○ Splitting the calibration data set D into 2 Apply FDRIˆ1 Identify (T ; Y ) and I (X; T ) to form ⇤ ○ Applying sequential FWER-controlling twoofdisjoint Dhyperparameters and D ○ Approximating the frontier using the estimates OPT OPT MHT Learn the RG D D D MHT MHT OPT OPT MHTPareto Dalgorithm 2 Approximating on on the Pareto the using the estimates 3 then IˆD○ (T ; Yhyperparameters ) and IˆD⇤ (X;front T ) on to frontier form ⇤OPT Applying MHTFWER-controlling via DAGGER OPT PT and DMHT ⇤MHT and○ choosesequential thecontrolling hyperparameter minimizes IˆDMHT1 MHT ⇤ that the OPT to form DMHT DMHT D ⇤ Dalgorithm 3toApplying (X; T ) to formon⇤⇤ sequential FWER-controlling OPT OPT form Pareto ⇤MHT and then choose the hyperparameter that minimizes Iˆ MHT1 (X; T ). OPT○ via DAGGER front 1 Figure 5.6: Illustration of the threeˆDstages of RG-PT. ○ The Pareto-optimal D ⇤ MHT 1 (X; T ). OPT and then choose the hyperparameter that minimizes I subset Λ̂Par is identified from the full candidate set Λ using dataset Dopt , DOPT D retaining only the hyperparameters that represent the best achievable trade- DMHT b1 (λ | Dopt ) and R b2 (λ | Dopt1). ○ 2 offs between the empirical risk estimatesDMHT R Par opt The reliability graph G is learned over set Λ̂ using dataset D and op1 tional prior information. Nodes correspond to candidate10 hyperparameters, 1 10 and edges encode inferred reliability dependencies (see Fig. 5.5). 1 1 10 directed Hyperparameters at the same depth level,1 indicated by dashed red boxes, are considered to have approximately the same expected reliability, with re3 The DAGGER algorithm (Ramdas liability decreasing from left to right. ○ et al., 2019) is applied to the reliability graph G using dataset DMHT , returning the certified set Λ̂ of hyperparameters controlling the FDR (2.60) at the target level δ. 5
Λ̂
G
1
1
5.5.1
Example: Reliable Prompt Engineering via RGPT
We illustrate RG-PT on a prompt engineering problem for LLM-based sentiment analysis, following (Farzaneh and Simeone, 2025a). Each data point Z = (X, Y ) consists of a movie review X and a sentiment label Y ∈ {positive, negative} from the Stanford Sentiment Treebank (Socher et al., 2013). A prompt template λ is prepended to the review and passed to the LLaMA3-8B-Instruct model (Grattafiori et al., 2024). The reliability constraint requires the average 0-1 classification loss to satisfy the inequality Rprompt (λ) ≤ α = 0.2, while the auxiliary objective is to minimize prompt length, reflecting inference cost under pay-per-token billing. The candidate set Λ contains 100 instruction72
LTT
PT
RG-PT
Length of shortest prompt
Figure 5.7: Distribution of the length of the shortest certified prompt template returned by LTT, PT, and RG-PT over 100 independent calibration splits for the LLM-based sentiment analysis task on the Stanford Sentiment Treebank dataset (Socher et al., 2013). All methods satisfy the FDR constraint at level δ = 0.1. RG-PT identifies shorter reliable prompts by leveraging the prior reliability structure encoded in the reliability graph, constructed using the LLM-as-a-judge framework (Gu et al., 2024). style templates of varying length, which are generated by LLaMA3-70BInstruct (Grattafiori et al., 2024) using the forward generation procedure of (Zhou et al., 2022). The calibration dataset contains |Dopt | = |DMHT | = 1000 examples each, and an independent test set of 1000 examples is used for evaluation. The target FDR level is δ = 0.1. Prior information is incorporated via the LLM-as-a-judge framework (Gu et al., 2024): GPT-4 Turbo is queried to assess which of each pair of prompt templates is more likely to elicit a correct response, yielding pairwise preferences for the Bradley-Terry model. Within the certified set Λ̂, the shortest prompt is selected for deployment. Fig. 5.7 reports the distribution of the length of the shortest certified prompt over 100 independent calibration splits. RG-PT consistently identifies shorter reliable prompts than both LTT and PT, while all three methods satisfy the FDR constraint at the target level δ = 0.1. This improvement stems from RG-PT’s more efficient exploration of the hyperparameter space along reliability-informed paths encoded in the RG: by testing hyperparameters in an order informed by the prior reliability graph, RG-PT can certify shorter prompts that LTT and PT, which either ignore structure entirely or use only a linear ordering, fail to reach within the same testing budget. 73
5.6
Summary
This chapter extended the LTT framework to multi-objective hyperparameter selection, where the practitioner must simultaneously satisfy LC reliability constraints and optimize L − LC auxiliary objectives. The three methods presented in this chapter—LTT, PT, and RG-PT— differ along several dimensions, as summarized next and in Table 5.1. Testing scope: LTT applies an MHT procedure such as Bonferroni or BH to all K = |Λ| candidate hyperparameters, without any ordering or restriction. PT restricts testing to the empirical Pareto frontier Λ̂Par ⊆ Λ and applies FST along a single linear ordering. RG-PT further structures the testing over a DAG, enabling parallel exploration of multiple reliability paths. Use of prior information: LTT and PT do not use prior structural information about relative reliability. RG-PT explicitly incorporates such information via prior pairwise preferences in the Bradley-Terry model, while the validity guarantee is maintained regardless of the quality of these priors. Error control: All three methods provide formal error guarantees. LTT and PT, as described in (Laufer-Goldshtein et al., 2023), can be configured to control either FWER or FDR. RG-PT controls the FDR at the specified level δ. FDR control is generally less conservative than FWER control, enabling larger certified sets at the cost of allowing a small expected fraction of unreliable configurations in Λ̂. Multi-objective optimization: LTT can accommodate multiple reliability constraints via the combined p-value (5.10), but does not exploit the multi-objective structure of the problem. In particular, it tests all K candidates without regard for dominance relationships among them, and does not actively optimize any auxiliary objectives beyond what a secondary criterion applied to the certified set Λ̂ can achieve. PT and RG-PT address both of these limitations: by restricting testing to the Pareto frontier, they eliminate dominated configurations before testing begins, and by ordering or structuring the remaining tests, they recover certified configurations that are also efficient with respect to the auxiliary objectives. 74
Property
LTT
PT
RG-PT
Multi-objective support No
Yes
Yes
Prior structure
No
Linear order
DAG
Testing scope
Full Λ
Pareto frontier
Pareto frontier
Error criterion
FWER or FDR
FWER or FDR
FDR
∗
Table 5.1: Comparison of LTT, PT, and RG-PT along key dimensions. (∗ LTT can accommodate multiple reliability constraints via the combined p-value (5.10), but does not exploit multi-objective structure to improve efficiency or optimize auxiliary objectives.)
75
Chapter 6 Adaptive and Sequential Hyperparameter Selection The LTT framework introduced in Chapter 2 and its multi-objective extensions in Chapter 5 share a common pipeline: (i ) the calibration data are collected in advance; (ii) all candidate hyperparameters are evaluated on the same fixed dataset Dcal ; and (iii) the testing procedure is applied once to produce a certified set Λ̂ of hyperparameters. This batch-based operation is well-suited to settings where data are plentiful and testing is cheap, but it becomes costly or impractical when data acquisition is expensive or the number of candidates is large. Consider, for example, the problem of selecting a control policy for a robotic system via offline reinforcement learning (Levine et al., 2020). Policies trained on offline data must be validated through online interaction with the real environment before deployment (Paine et al., 2020). Each such interaction episode consumes physical resources, may cause wear on hardware, and in safety-critical settings such as autonomous driving or robotic surgery can pose direct risk of harm (Garcıa and Fernández, 2015). Reducing the number of episodes used for policy selection is thus of critical importance. Instead of evaluating all K candidate policies on a fixed budget of episodes, as LTT would require, it would be useful to evaluate policies adaptively, allocating evaluation episodes only to the most promising policies. As another example, consider automated prompt engineering for an LLM deployed under pay-per-token billing (Zhou et al., 2022). A set of K candidate prompt templates is generated, and each template must be evaluated on held-out queries by executing the LLM, with each execution incurring a direct 76
and measurable monetary cost (Bommasani, 2021). With K ranging into the hundreds in realistic pipelines (Zhou et al., 2022), and with each evaluation potentially consuming thousands of tokens, the total cost of exhaustively testing all candidates on a fixed calibration dataset can be prohibitive. It is far more economical to concentrate evaluations on the templates that have shown the most promise in early rounds, and to stop as soon as a sufficiently reliable subset has been identified. The principle of adaptive evaluation is already implemented, in different forms, by several existing HPO methods. Successive halving (Jamieson and Talwalkar, 2016) and Hyperband (Li et al., 2018) allocate computational resources adaptively across configurations, terminating poorly performing candidates early and concentrating the training budget on the most promising ones. Multi-fidelity Bayesian optimization extends this idea by leveraging a surrogate model of the validation performance to decide where to evaluate next (Shahriari et al., 2016), while freeze-thaw Bayesian optimization explicitly models partial learning curves to decide which training runs to pause, resume, or discard (Franceschi et al., 2025). The guarantees offered by these methods, when available, concern the efficient identification of the empirical optimum, rather than the reliability of the deployed configuration. For example, successive halving and Hyperband come with best-arm-identification and simple-regret bounds under suitable assumptions on the loss curves, ensuring that, with enough budget, a nearempirically-optimal configuration is returned (Jamieson and Talwalkar, 2016; Li et al., 2018). Freeze-thaw and related learning-curve-based schemes are largely heuristic, and their convergence properties typically rest on modelling assumptions about the learning curves rather than on finite-sample concentration arguments (Franceschi et al., 2025). Crucially, however, as in conventional HPO discussed in Chapter 1, none of these adaptive methods provides finite-sample statistical guarantees that the selected hyperparameter satisfies a user-specified reliability requirement of the form (1.4). This chapter introduces an adaptive extension of LTT, called adaptive LTT (aLTT), introduced in (Zecchin et al., 2024). aLTT replaces the static, batch hypothesis testing of LTT with a sequential, data-dependent procedure that (i) selects which hyperparameters to test next based on evidence accumulated in prior rounds, and (ii) terminates early as soon as a target number of reliable configurations have been certified. The statistical validity of the procedure, in terms of FWER or FDR control, is maintained throughout due to e-process-based testing, which supports anytime-valid inference. 77
The chapter is organized as follows. Section 6.1 motivates and formalizes the sequential calibration setting. Sec. 6.2 introduces e-processes and anytime-valid p-values, the central statistical tools underlying aLTT. Sec. 6.3 presents the aLTT algorithm. Sec. 6.4 illustrates aLTT on the wireless scheduling application of Sec. 3.2, adapted to the sequential calibration setting.
6.1
Sequential Hyperparameter Selection
As illustrated in Fig. 6.1(a), under the LTT framework reviewed in Chapter 2, all K = |Λ| candidate hyperparameters are fully tested using the entire calibration dataset Dcal . The MHT procedure is then applied once to the resulting p-values to produce a certified set Λ̂. As discussed, this batch design may be excessively costly in scenarios where one wishes to reduce data usage, as well as the number of evaluation rounds. To address such settings, as shown in Fig. 6.1(b), aLTT (Zecchin et al., 2024) operates in a feedback loop: at each round t, it evaluates the evidence accumulated so far and asks whether that evidence is sufficient to produce a certified set of the desired size. If not, it requests a new batch of calibration data, updates the evidence, and repeats. When sufficient evidence has been gathered, the loop exits and Λ̂ is returned. To formalize, as throughout this monograph, let Λ = {λ1 , . . . , λK } be a finite candidate set. For each hyperparameter λ ∈ Λ, the risk R(λ) = E[Lλ (Z)]
(6.1)
is defined with respect to an unknown data-generating distribution P, where Z is a generic test-time data point. As in Definition 2.1, the reliability threshold α and failure probability δ are specified by the user. Sequential hyperparameter selection proceeds in discrete rounds t = 1, 2, . . . In each round t, the procedure executes the following five steps. 1 Hyperparameter selection: An acquisition policy Qt selects a sub○ set I t ⊆ Λ of candidates to be tested in round t. The policy Qt may be adaptive, meaning that it may depend on the evidence Dt−1 collected in all previous rounds, or non-adaptive, meaning that the set I t is fixed in advance. 2 Testing: A batch of data samples Z t ∼ P are drawn independently ○ across rounds, and the empirical loss Lλi (Z t ) is evaluated. 78
Dcal
Dcal
…
… t
Yes
LTT
More evidence needed?
aLTT
No
Λ̂
Λ̂ (a)
(b)
E-value processes
Figure 6.1: Conceptual comparison of LTT and aLTT. (a) LTT is a singlepass batch procedure: a fixed calibration dataset Dcal is collected once, processed by the LTT procedure, and a certified set Λ̂ is returned. (b) aLTT is a sequential procedure in which calibration data arrive incrementally over rounds t = 1, 2, . . . At each round, aLTT evaluates the accumulated evidence and decides whether more data are needed. If so, a new data batch is requested and the available evidence is updated. The procedure terminates and returns Λ̂ as soon as sufficient evidence has been gathered. Testing round
3 Evidence update: The evidence accumulated for each candidate ○ hyperparameter is updated using the newly observed empirical losses. (6.2) Dt = Dt−1 ∪ (I t , {Lλi (Zit )}λi ∈I t ) , 4 Certification: A decision rule A is applied to the current evidence to ○ produce a candidate certified set Λ̂t . Depending on the desired error criterion, the decision rule A can be either FWER-controlling or FDR-controlling. 5 Stopping check: If |Λ̂t | ≥ d for a user-specified minimum certified ○ set size d ≥ 1, or if the maximum number of rounds tmax has been reached, the procedure terminates and returns Λ̂ = Λ̂t . Otherwise, time index t is 1 incremented and the procedure returns to ○. The entire sequential procedure is thus specified by the tuple ({Qt }t≥1 , A, T ), where {Qt }t≥1 is the acquisition policy, A is the decision rule that maps accumulated evidence to a certified set, and T is a stopping time that may itself depend on the evidence accumulated so far (adaptive stopping) or be fixed in advance (non-adaptive stopping). As described in the remainder of this chapter, aLTT implements adaptive 79
Observe samples
{Lλi (Zit )}λi ∈I t
Qt t
I ⊆Λ
Update evidence
Dt
E-value processes
Λ
λ1 λ2 λ3 λ4
FWER/FDRcontrolling selection procedure
Λ̂t
Testing round
Figure 6.2: Illustration of the operations performed within a single round t of the aLTT calibration procedure. The acquisition policy Qt selects a 1 subset I t ⊆ Λ of candidates to test (○). Fresh losses {Lλi (Zit )}λi ∈I t are 2 and used to update the evidence Dt (○), 3 which in practice observed (○) t amounts to updating the e-process Ei for each tested candidate, as shown by the curves. Candidates with growing e-processes (e.g., λ1 , λ2 ) accumulate evidence of reliability, while those with flat or decaying e-processes (e.g., λ3 , λ4 ) do not. The current e-process values are then passed to an FWER- or FDR-controlling selection procedure to produce the updated certified set Λ̂t 4 5 determines whether (○). At the end of each round, a stopping check (○) calibration should continue or terminate. HPO by leveraging the statistical tool of e-processes (see Fig. 6.2).
6.2
E-Processes and Anytime-Valid Inference
The central obstacle to applying LTT in a sequential, data-dependent manner is the invalidity of p-values under adaptive stopping. In fact, the type-I error guarantee relies on the superuniform property (2.19), which is no longer guaranteed if one conditions on observations made in past testing rounds. This violation of statistical validity is known as p-hacking, and is a key contributor to the reproducibility crisis in science (Simonsohn et al., 2014). A more detailed discussion of this limitation of p-values, including a worked illustration of the optional-stopping pathology, is provided in Appendix A. E-values, introduced in Sec. 2.5, are special types of test statistics that support anytime-valid testing: e-values computed at different time points can be combined by multiplication without losing validity. This makes them the natural foundation for sequential, adaptive testing (Ramdas and Wang, 2025; Wang and Ramdas, 2022). 80
6.2.1
E-Processes
An e-process for null hypothesis Hi : R(λi ) > α is a sequence of non-negative random variables {Eit }t≥0 such that, for any stopping time T , which may depend on all evidence accumulated up to and including round T , the stopped value EiT is a valid e-value, i.e., E[EiT | Hi ] ≤ 1.
(6.3)
Condition (6.3) is the sequential analog of the e-value validity condition (2.40), and it holds for all stopping times simultaneously, not just for a fixed time horizon. A more general treatment of e-processes, including Ville’s inequality and the corresponding anytime-valid testing guarantees, is given in Appendix A. A common and powerful construction of an e-process for the null Hi : R(λi ) > α follows the principle of testing by betting (Ramdas et al., 2023). Accordingly, at each round t in which hyperparameter λi is tested, we observe the loss Lλi (Zit ), and define a per-round e-value ϵti = 1 + µti α − Lλi (Zit ) , (6.4) where
1 µti ∈ 0, 1−α
(6.5)
is a tunable betting parameter (Waudby-Smith and Ramdas, 2024). In the testing by betting interpretation, the term (6.4) represents the multiplicative wealth growth for a bettor investing an amount µti against the null hypothesis Hi . By (6.4), the wealth grows by an amount that increases whenever the inequality Lλi (Zi ) < α holds. Recalling that the empirical estimate is unbiased, i.e., E[Lλi (Zi )] = R(λi ), this condition provides evidence against the null Hi : R(λi ) > α. Setting Ei0 = 1, the e-process is then given by the running product of the multiplicative wealth gains (6.4) as ( Eit−1 · ϵti if λi ∈ I t , Eit = (6.6) Eit−1 otherwise. That is, the e-process is updated by multiplying in the per-round factor ϵti whenever hyperparameter λi is tested, and is held constant otherwise. In the testing by betting interpretation, Eit represents the current wealth of the bettor for hyperparameter λi . 81
Lemma 6.1 (Validity of the sequential product e-process). The sequence {Eit } in (6.6) is an e-process for the null hypothesis Hi . Proof. By the unbiasedness of the empirical estimate, we have the inequality E[Lλi (Z t )] = R(λi ) ≥ α under the null Hi , and hence the average multiplicative gain in (6.4) satisfies the condition E[ϵti | Dt−1 , Hi ] = 1 + µti (α − R(λi )) ≤ 1.
(6.7)
Given the condition in (6.5), i.e., µti < 1/(1 − α), as well as the assumption Lλi (Z t ) ∈ [0, 1], each factor ϵti is non-negative. Together with the bound above, this shows that the product Eit is non-negative, and that it satisfies the inequality E[Eit | Hi ] ≤ 1. This shows that the process {Eit } is a nonnegative supermartingale with respect to the filtration generated by Dt under Hi . By Doob’s optional stopping theorem for non-negative supermartingales (Ramdas et al., 2023), the expectation at any stopping time T satisfies E[EiT | Hi ] ≤ Ei0 = 1,
(6.8)
confirming that the sequence EiT is an e-process as per condition (6.3).
6.2.2
Betting Strategies
The power of the e-process {Eit }Tt=1 to detect reliable hyperparameters depends on how quickly it grows when hyperparameter λi is truly reliable. The rate of this growth, in turn, depends critically on the choice of the betting parameters {µti }t≥1 . If the betting parameter µti is chosen to be large, the gambler is aggressive: the wealth grows rapidly when the hyperparameter is reliable, but can also decrease rapidly when individual losses exceed α. Conversely, if µti is small, the procedure is conservative, and growth is slow but stable. The optimal choice for the sequence of betting parameters µti is typically considered to be one that maximizes the expected log-wealth growth, i.e., E[log ϵti ], subject to the constraint µti ∈ (0, 1/(1 − α)) (Shafer and Vovk, 2019; Ramdas et al., 2023; Waudby-Smith and Ramdas, 2024). Accordingly, a practical and principled choice is the adaptive growth rate adaptive to the particular alternative (aGRAPA) strategy (Waudby-Smith and Ramdas, 2024), which sets the parameter µti based on the empirical mean of the losses observed up to round t − 1. More precisely, aGRAPA 82
estimates the true risk R(λi ) from past data and sets the parameter µti to be the solution of the per-round empirical wealth optimization problem. This adaptive approach requires no prior knowledge of R(λi ) and performs well across a wide range of true risk values. Another option is the online Newton step (ONS) betting strategy (WaudbySmith and Ramdas, 2024), which updates µti using a second-order online learning rule applied to the log-wealth objective. ONS typically achieves faster growth rates in practice. For simplicity of exposition, we set µti = µ as a fixed constant in the theoretical development below, while noting that data-adaptive strategies are preferable in practice.
6.2.3
Anytime-Valid P-values
Given an e-process {Eit }t≥0 , one can derive an anytime-valid p-value Pit for hypothesis Hi as follows. Define Pit =
1 maxτ ≤t Eiτ
.
(6.9)
That is, the anytime-valid p-value at time t is the reciprocal of the running maximum of the e-process up to round t. Lemma 6.2 (Anytime validity of the p-value (6.9)). For any stopping time T that may depend on the entire history DT , the statistic PiT in (6.9) is a valid p-value for Hi . Proof. For any u ∈ [0, 1], note that the inequality PiT ≤ u holds if and only if maxτ ≤T Eiτ ≥ 1/u, which implies EiT ≥ 1/u for some τ ≤ T . By Ville’s inequality for non-negative martingales (Ville, 1939), we have 1 τ P max Ei ≥ (6.10) Hi ≤ u E[Ei0 | Hi ] = u, τ ≤T u and thus the superuniformity condition P(PiT ≤ u | Hi ) ≤ u holds, as required.
83
6.3
Adaptive Learn-Then-Test
We now present the full aLTT algorithm (Zecchin et al., 2024), which combines the e-process machinery described in Sec. 6.2 with an adaptive acquisition policy and an adaptive stopping rule.
6.3.1
Algorithm Description
aLTT operationalizes the five-step sequential procedure of Sec. 6.1 by maintaining, for each candidate λi ∈ Λ, a running e-process Eit initialized at Ei0 = 1. At each round t, the acquisition policy selects a subset of hyperpa1 empirical losses are evaluated (step ○); 2 and the rameters I t ⊆ Λ (step ○); 3 The current e-processes are updated multiplicatively as per (6.6) (step ○). e-process values are then passed to the chosen MHT procedure to produce 4 the certified set Λ̂t as (step ○) ( AFWER (P1t , . . . , PKt ) if FWER control is desired, (6.11) Λ̂t = t ) if FDR control is desired, AFDR (E1t , . . . , EK where Pit = 1/ maxτ ≤t Eiτ are the anytime-valid p-values in (6.9). For FWER control, any procedure from Sec. 2.4.3 can be applied; for FDR control, the e-BH procedure from Sec. 2.6 is typically used directly on the e-values Eit . 5 terminates the procedure if |Λ̂t | ≥ d Finally, the stopping check (step ○) 1 The full aLTT or t = tmax , and otherwise increments t and returns to ○. procedure is summarized in Algorithm 5.
6.3.2
Acquisition Policies
A key design choice in aLTT is the acquisition policy Qt , which determines which candidates to test at each round. Following (Zecchin et al., 2024), we discuss two natural choices. Non-adaptive (random) acquisition: The simplest policy selects one or more candidates uniformly at random from set Λ at each round, independently of the e-process values. This recovers the same long-run performance as LTT when T → ∞, but, crucially, produces valid intermediate certified sets at every round t, enabling early termination. 84
Algorithm 5 Adaptive Learn-Then-Test (aLTT) (Zecchin et al., 2024) Input: Candidate set Λ = {λ1 , . . . , λK }; risk threshold α; error level δ; error type err ∈ {FWER, FDR}; acquisition policy {Qt }t≥1 ; betting parameters {µti }; maximum rounds tmax ; minimum certified set size d; error-controlling MHT procedure Aerr (·) at level δ; Output: Certified set Λ̂ ⊆ Λ Initialize Ei0 ← 1 for all i; t ← 1; Λ̂ ← ∅ while t ≤ tmax and |Λ̂| < d do I t ← Qt ({Eit−1 }K i=1 ) for each λi ∈ I t do Observe the losses Lλi (Zit ) and update the e-process Eit ← Eit−1 · 1 + µti (α − Lλi (Zit )) end for for each λi ∈ / I t do t−1 t Ei ← Ei end for if err = FWER then Compute the p-value Pit ← 1/ maxτ ≤t Eiτ for all i Λ̂ ← AFWER (P1t , . . . , PKt ) else t ) Λ̂ ← AFDR (E1t , . . . , EK end if t←t+1 end while return Λ̂ ε-greedy acquisition: A more effective adaptive policy is the ε-greedy rule: With probability 1 − ε, select the uncertified candidate λi ∈ / Λ̂t−1 t−1 with the largest current e-process value Ei ; otherwise, with probability ε, select a candidate uniformly at random from the uncertified set. The greedy component concentrates testing effort on the candidates that have accumulated the most evidence of reliability so far, accelerating the growth of their e-processes toward the rejection threshold. In contrast, the random component ensures that candidates whose e-processes have grown slowly due to limited testing are not permanently ignored.
85
6.3.3
Statistical Guarantees
The fundamental validity of aLTT rests on the anytime-validity property of the e-process (Lemma 6.2): no matter at which round T the procedure terminates, whether triggered by the early stopping criterion or the maximum round limit, the resulting certified set carries the same formal guarantees as the batch LTT procedure. Theorem 6.3 (Validity of aLTT (Zecchin et al., 2024)). Let T be any stopping time (possibly adaptive) at which aLTT terminates. (i) If AFWER is applied, the certified set Λ̂ = Λ̂T satisfies the FWER requirement ! P sup R(λ) ≤ α λ∈Λ̂
≥ 1 − δ.
(6.12)
(ii) If AFDR (e-BH) is applied, the certified set satisfies the FDR requirement # " |Λ̂ ∩ Λ0 | ≤ δ, (6.13) E max{1, |Λ̂|} where Λ0 = {λ ∈ Λ : R(λ) > α}.
Proof. For part (i), by Lemma 6.2, each statistic PiT is a valid p-value for Hi at the (possibly adaptive) stopping time T . The FWER-controlling procedure AFWER applied to these p-values therefore provides the guarantee (6.12) by the same argument as Theorem 2.1. For part (ii), the e-values EiT satisfy E[EiT | Hi ] ≤ 1 by the e-process property (6.3), for any stopping time T . The FDR guarantee then follows from the e-BH theorem (Appendix C.2) applied to the stopped e-values.
6.4
Example: Adaptive Wireless Scheduling
We illustrate the aLTT framework using the wireless scheduling application introduced in Sec. 3.2, now adapted to the sequential calibration setting. This application is a natural fit for adaptive testing: each evaluation of a candidate hyperparameter configuration requires executing a full scheduling episode in the Nokia wireless simulator (Valcarce, 2020), and reducing the total number of such episodes is a primary operational objective. 86
6.4.1
Setting
We consider the same downlink scheduling system described in Sec. 3.2. The learning-based scheduler of (Sant Ana and Marchenko, 2020) is parameterized by a vector λ = (λ1 , λ2 , λ3 , λ4 ) controlling the weights of four terms in the reward model. Following Sec. 3.2, a candidate set of K = 20 configurations is considered. The per-episode loss is the mean packet delay of the highest-priority QoS class, normalized to [0, 1] by clipping at 20 ms as Lλ (Z t ) =
min(delayλ (Z t ), 20 ms) . 20 ms
(6.14)
The reliability requirement is R(λ) = E[Lλ (Z)] ≤ α, where α = 0.5 corresponds to the mean delay target of 10 ms used in Sec. 3.2. The target error level is δ = 0.1. In the sequential calibration setting, data arrive one episode at a time. At each round t, the acquisition policy Qt selects a single candidate λi from the pool of uncertified configurations, one scheduling episode is drawn i.i.d. from the Nokia simulator, and the per-round normalized loss Lλi (Zit ) is observed. The e-process for λi is then updated as per (6.6) with fixed betting parameter µ = 1.5, while the e-processes of all other candidates remain unchanged. The maximum number of testing rounds is tmax = 2000. We compare aLTT with the ε-greedy acquisition policy for ε ∈ {0.25, 0.50, 0.75, 0.95} against non-adaptive LTT (ε = 1.0, uniform random selection with no greedy component). Both FWER control via Bonferroni and FDR control via e-BH are evaluated. Results are averaged over 200 independent calibration runs.
6.4.2
Results
Fig. 6.3 shows the TPR as a function of the testing round t on a logarithmic scale for both FWER and FDR control. The advantage of the ε-greedy acquisition policy over non-adaptive LTT is clear in both panels. Under FDR control, aLTT with ε = 0.25 reaches 50% of LTT’s final TPR in approximately 150 rounds, while non-adaptive LTT requires the full testing budget of tmax = 2000 rounds to reach the same level. The greedy policy achieves this by concentrating episodes on the candidates with the largest accumulated e-process values, building up evidence of reliability much faster than uniform random selection. Under FWER control, the Bonferroni threshold 87
True Positive Rate (TPR)
FWER Control 1.0
0.8
0.6
0.4
FDR Control
LTT (non-adaptive) ε = 0.25 (aLTT)
LTT (non-adaptive) ε = 0.25 (aLTT)
ε = 0.50 (aLTT) ε = 0.75 (aLTT) ε = 0.95 (aLTT)
ε = 0.50 (aLTT) ε = 0.75 (aLTT) ε = 0.95 (aLTT)
0.2
0.0 100
101
102
103
100
Testing round t (log scale)
101
102
103
Testing round t (log scale)
Figure 6.3: True positive rate (TPR) as a function of the number of testing rounds t (log scale) in the wireless scheduling application of Sec. 6.4, using episode data from the Nokia wireless simulator (Valcarce, 2020) with K = 20 candidate configurations and reliability threshold α = 0.5 (corresponding to a mean packet delay of 10 ms). Results are shown for aLTT with ε-greedy acquisition for ε ∈ {0.25, 0.50, 0.75, 0.95} and non-adaptive LTT (ε = 1.0), under FWER control via Bonferroni correction (left) and FDR control via e-BH (right), both at level δ = 0.1. Curves are averaged over 200 independent calibration runs. Smaller ε (more evidence-driven acquisition) yields substantially faster convergence to a large certified set. δ/K = 0.005 is more stringent, and the absolute TPR values are lower for all methods, but the relative advantage of aLTT is equally pronounced: aLTT with ε = 0.25 reaches 50% of LTT’s final TPR in approximately 335 rounds. In both panels, the benefit of the greedy component is monotone in the εgreedy acquisition probability ε: smaller ε (more exploitation of accumulated evidence) yields both faster convergence and a higher final TPR, while ε = 1.0 (non-adaptive LTT) is dominated by all greedy variants across the entire testing horizon. These results confirm the two key properties of aLTT established in this chapter. First, the ε-greedy acquisition policy substantially accelerates the discovery of reliable hyperparameter configurations by concentrating episodes on the candidates with the largest accumulated e-process values. Second, this acceleration comes at no cost to statistical validity: by Theorem 6.3, the FWER and FDR guarantees hold at every round and for any datadependent stopping time, as a direct consequence of the anytime validity of the e-processes. 88
6.5
Summary
This chapter extended the LTT framework of Chapter 2 to the adaptive sequential setting, introducing the aLTT algorithm of (Zecchin et al., 2024). The central motivation is that, in many practical deployments, evaluating candidate hyperparameters is costly, whether in terms of online interactions with a physical environment, LLM inference costs, or scarce labeled data, and it is therefore desirable to concentrate testing effort on the most promising candidates and terminate calibration as soon as a reliable set has been identified. The key methodological departure from LTT is the replacement of static p-values with e-processes. As established in Lemma 6.1, the running product of per-round e-values forms a non-negative supermartingale under the null hypothesis, and its stopped value remains a valid e-value at any stopping time, including data-dependent ones. This anytime-validity property, formalized in Lemma 6.2 for the derived p-values, is what makes adaptive acquisition and early stopping statistically rigorous: the FWER and FDR guarantees of Theorem 6.3 hold regardless of when and why the procedure terminates. It is worth emphasizing that the statistical guarantees of aLTT do not depend on the quality of the acquisition policy: any policy, adaptive or not, yields a valid certified set. The policy affects only the speed at which reliable candidates are discovered, not the correctness of the certification. This separation between validity and efficiency is a practically important property that allows practitioners to design aggressive acquisition strategies without fear of compromising the reliability guarantees. Finally, aLTT is complementary to the multi-objective extensions of Chapter 5. While PT and RG-PT address the challenge of certifying hyperparameters under multiple simultaneous reliability constraints, aLTT addresses the challenge of doing so efficiently when each evaluation is costly. Combining the two directions, adaptive sequential testing under multiple objectives, is a natural extension.
89
Chapter 7 Hyperparameter Selection with Autoevaluation The frameworks developed in previous chapters assume that the loss Lλ (Xi , Yi ) can be evaluated exactly on each calibration sample (Xi , Yi ), where Yi is a ground-truth label obtained through human annotation or direct measurement. In many modern AI applications, however, producing ground-truth labels is prohibitively expensive. Consider, for instance, the problem of selecting a prompt template for an LLM deployed on open-ended generation tasks, or of choosing a quantization format for a pretrained model evaluated on reading comprehension. In both cases, assessing whether a model output is correct ideally requires human judgment: a domain expert must read each response and decide whether it meets the desired quality standard. At scale, this process can be slow and costly, limiting the number of calibration samples available for hyperparameter selection. Autoevaluation (AutoEval) (Gu et al., 2024; Zheng et al., 2023; Novikova et al., 2017; Park et al., 2025) addresses this bottleneck by replacing groundtruth labels with labels generated by an automated evaluator, typically a larger pretrained model acting as a judge. Given an input X, the autoevaluator f : X → Y produces a synthetic label f (X) at low cost. This makes it possible to evaluate candidate hyperparameters on large collections of unlabeled inputs, substantially reducing the dependence on human annotation. The central challenge with AutoEval is bias: the autoevaluator f may systematically disagree with the ground-truth labeling mechanism, e.g., with human judgment, so that the synthetic loss Lλ (X, f (X)) is a biased estimate 90
of the true risk R(λ) = E[Lλ (X, Y )]. Relying naively on autoevaluated losses can therefore lead to incorrect hyperparameter selection, with no control over the resulting failure probability. This chapter develops a statistically principled framework for hyperparameter selection that combines a small amount of ground-truth labeled calibration data with a large pool of autoevaluated data, while providing the same finite-sample reliability guarantees as the LTT framework of Chapter 2. The methodology is based on prediction-powered inference (PPI) (Angelopoulos et al., 2023b; Zrnic and Candès, 2024; Song et al., 2026), which uses real data to correct for the bias introduced by the autoevaluator, and on the testing-by-betting framework introduced in Chapter 6 to construct valid e-values from the bias-corrected estimates. The chapter is organized as follows. Section 7.1 formalizes the autoevaluation setting and introduces the evaluation protocols. Section 7.2 reviews reliable evaluation using only real data (R-Eval) (Waudby-Smith and Ramdas, 2024). Section 7.3 describes how PPI can be used to incorporate autoevaluated data into the testing framework (R-AutoEval) (Einbinder et al., 2025). Section 7.4 presents R-AutoEval+, an adaptive method that automatically tunes the reliance on synthetic data based on the quality of the autoevaluator (Park et al., 2025). Section 7.5 illustrates the framework on the wireless scheduling application of Sec. 3.2.
7.1
The Autoevaluation Setting
As in the rest of the monograph, we fix a finite candidate set Λ = {λ1 , . . . , λK } of hyperparameters and a bounded loss function Lλ : X × Y → [0, 1]. The true risk of each candidate is given by R(λ) = E[Lλ (X, Y )], with test data prior (X, Y ) ∼ P. As illustrated in Fig. 7.1, in the autoevaluation setting, we assume access to two data sources: • A ground-truth labeled dataset Dcal = {(Xi , Yi )}ni=1 of n groundi.i.d. truth labeled samples (Xi , Yi ) ∼ P, where the number of labeled samples n is small due to, e.g., annotation cost in the case of human labels. i.i.d.
• An unlabeled dataset Dunl = {X̃i }N i=1 of N unlabeled inputs X̃i ∼ PX , where the number of unlabeled inputs N is large and the inputs are cheap to obtain. 91
Xi X̃i
✅ ✅ ✅
f( ⋅ )
Dcal = {(Xi , Yi )}ni=1
D̃cal = {(X̃i , f (X̃i )}N i=1
Figure 7.1: Illustration of the two data sources in the autoevaluation setting. The ground-truth labeled dataset Dcal = {(Xi , Yi )}ni=1 is produced, e.g., by a human annotator and is small due to annotation cost. The synthetic calibration dataset D̃cal = {(X̃i , f (X̃i ))}N i=1 is produced by applying the autoevaluator f to the large unlabeled dataset Dunl , and is cheap to obtain but potentially biased. A pre-trained autoevaluator f : X → Y provides synthetic labels f (X̃) for inputs in the unlabeled set. The autoevaluator may be, for instance, a large LLM used as a judge. The autoevaluator f is applied to the unlabeled dataset Dunl to obtain the synthetic calibration dataset D̃cal = {(X̃i , f (X̃i ))}N i=1 . The autoevaluated risk estimate for a hyperparameter λ is obtained using the synthetic labels as N X bf (λ) = 1 Lλ X̃i , f (X̃i ) . R N N i=1
(7.1)
While this estimate has low variance due to the large size N of the unlabeled dataset, it is generally biased, i.e., bf (λ)] = E[Lλ (X, f (X))] ̸= R(λ). E[R N
(7.2)
Three strategies are distinguished in this chapter:
• Eval: This baseline scheme uses only the ground-truth labeled data Dcal to estimate the risk via the empirical average n 1X b Rn (λ) = Lλ (Xi , Yi ). n i=1
(7.3)
bn (λ)] = R(λ), but it has high variThis estimate is unbiased, i.e., E[R ance due to the small labeled dataset size n. 92
• AutoEval: This complementary baseline uses only the autoevaluated data via the estimate (7.1). This approach exhibits low variance due to large unlabeled dataset size N but is generally biased. • R-AutoEval (Einbinder et al., 2025) / R-AutoEval+ (Park et al., 2025): These methods combine both data sources to achieve bias-corrected, statistically valid risk certification by leveraging PPI (Angelopoulos et al., 2023b). As in Chapter 6, reliability certification in this chapter is formulated as a sequential testing problem. Specifically, the ground-truth labeled samples in Dcal are processed one by one, and at each step the accumulated evidence is used to update an e-process for each candidate hyperparameter, as described in Sec. 6.2. This sequential formulation enables early termination as soon as sufficient evidence has been gathered, reducing the number of expensive ground-truth labeled samples required. As formalized in Definition 2.1, the goal remains to select a hyperparameter λ̂ ∈ Λ satisfying the (α, δ)-risk-controlling guarantee P(R(λ̂) ≤ α) ≥ 1−δ. The challenge is to achieve this guarantee while reducing the amount of ground-truth labeled data required. To measure the cost of an evaluation method, we define its sample complexity as the minimum expected number of ground-truth labeled samples needed to certify a reliable hyperparameter λ, i.e., to ensure that it is included in the set Λ̂. This can be defined mathematically as the conditional average i h (7.4) nmin (δ, λ) = E min{n : λ ∈ Λ̂} R(λ) ≤ α . A method with smaller sample complexity can certify reliable hyperparameters using fewer expensive ground-truth labeled samples.
7.2
Reliable Evaluation with Real Data
The simplest statistically valid approach is to use only the ground-truth labeled data Dcal . In the sequential testing setting described above, this is done by applying the e-process framework of Chapter 6, with the per-round observation Lλ (Xi , Yi ), which is an unbiased estimate of R(λ) bounded in [0, 1].
93
Following the testing-by-betting construction of Sec. 6.2, for any given candidate hyperparameter λ, R-Eval (Waudby-Smith and Ramdas, 2024) constructs the e-process EnR-Eval =
n Y i=1
1 − µi Lλ (Xi , Yi ) − α ,
(7.5)
where the betting parameter µi ∈ (0, 1/(1 − α)) is chosen using past observations. By Lemma 6.1, the sequence (7.5) provides a valid e-process for the null hypothesis Hλ : R(λ) > α. The corresponding anytime-valid test, with target error level δ ∈ (0, 1), is R-Eval R-Eval Tn = I max Ei ≥ 1/δ , (7.6) i≤n
which certifies λ as reliable as soon as the e-process exceeds the threshold 1/δ and satisfies P(TnR-Eval = 1 | R(λ) > α) ≤ δ. To certify a set Λ̂ ⊆ Λ, the e-values {EnR-Eval (λk )}K k=1 are fed into any of the MHT procedures of Chapter 2, exactly as in Algorithm 5. The limitation of R-Eval is its sample complexity. Since only the n ground-truth labeled samples are used, the e-process grows slowly when n is small, delaying certification. In fact, as shown in (Waudby-Smith and Ramdas, 2024), as δ → 0, the sample complexity nmin (δ, λ) in (7.4) scales as log(1/δ)/g ⋆ (λ), where g ⋆ (λ) = E[log(1 − µ⋆ (Lλ (X, Y ) − α)) | R(λ) ≤ α] is the maximum expected log-wealth increment, and µ⋆ is the optimal constant betting parameter. As discussed in Sec. 6.2, this quantity decreases with the variance of the per-sample loss, so high-variance losses lead to larger sample complexity.
7.3
Bias-Corrected Evaluation via PPI
R-AutoEval (Einbinder et al., 2025) addresses the sample complexity limitations of R-Eval by incorporating autoevaluated data through a bias correction mechanism based on PPI (Angelopoulos et al., 2023b). The core idea of PPI is to use the large unlabeled dataset to obtain a low-variance but potentially biased risk estimate, and then use the small ground-truth labeled dataset to correct for this bias. This yields an effective observation that is unbiased and potentially lower-variance than the raw ground-truth labeled loss alone when the autoevaluator is sufficiently accurate. 94
To proceed, let r = ⌊|Dunl |/n⌋ denote the ratio of unlabeled to labeled samples. Then, pair each labeled data point (Xi , Yi ) with a distinct subset of r autoevaluated samples drawn from D̃cal , namely {(X̃i′ , f (X̃i′ ))}ri i′ =r(i−1)+1 . Using the labeled data point (Xi , Yi ) and the corresponding autoevaluated batch {(X̃i′ , f (X̃i′ ))}ri i′ =r(i−1)+1 , we construct the PPI-based estimate 1 ℓfi (λ) =
ri X
Lλ X̃i′ , f (X̃i′ ) + Lλ (Xi , Yi ) − Lλ (Xi , f (Xi )) . | {z } r ′ i =r(i−1)+1 bias correction {z } |
(7.7)
autoevaluator data
The first term is the empirical autoevaluated risk over the r synthetic samples, providing low-variance, but biased, information about the true risk R(λ). The second term corrects for the bias of the autoevaluator using the paired real observation. As shown next, the estimate (7.7) is unbiased. Lemma 7.1 (Validity of PPI estimates). The estimates ℓfi (λ) in (7.7) are unbiased, i.e., E[ℓfi (λ)] = R(λ). (7.8) Moreover, the estimate is bounded as ℓfi (λ) ∈ [−1, 2].
Proof. By linearity of expectation and using the fact that X̃ and X share the same marginal distribution PX , i.e., E[Lλ (X̃, f (X̃))] = E[Lλ (X, f (X))], we obtain E[ℓfi (λ)] = E[Lλ (X̃, f (X̃))] + E[Lλ (X, Y )] − E[Lλ (X, f (X))] = R(λ). (7.9) For the range of the estimate, since each loss term lies in [0, 1], the lower bound is achieved when the autoevaluated average equals 0 and Lλ (Xi , Yi ) − Lλ (Xi , f (Xi )) = −1, giving the lower bound ℓfi (λ) ≥ −1. The upper bound is achieved when the autoevaluated average equals 1 and Lλ (Xi , Yi ) − Lλ (Xi , f (Xi )) = 1, giving the upper bound ℓfi (λ) ≤ 2. Since the estimate ℓfi (λ) is unbiased and bounded, it can be used in place of the estimate Lλ (Xi , Yi ) based solely on labeled data to construct a valid e-process for the null hypothesis Hλ : R(λ) > α. Accordingly, R-AutoEval (Einbinder et al., 2025) replaces the real-data observations in (7.5) with the effective observations (7.7), yielding EnR-AutoEval =
n Y i=1
1 − µi ℓfi (λ) − α , 95
(7.10)
where the betting parameter µi ∈ (0, 1/(2 − α)) accounts for the extended range [−1, 2] of ℓfi (λ). The test is then constructed as in (7.6) with the e-process EnR-AutoEval in lieu of EnR-Eval . The sample efficiency of R-AutoEval relative to R-Eval depends on whether the estimate ℓfi (λ) has lower variance than the raw loss Lλ (Xi , Yi ). When the autoevaluator is accurate, the bias correction term Lλ (Xi , Yi )−Lλ (Xi , f (Xi )) in (7.7) has small variance and the synthetic data effectively augments the calibration set, reducing sample complexity. However, when the autoevaluator is inaccurate, this correction term has high variance, and incorporating the synthetic data can actually increase the sample complexity compared to R-Eval (Angelopoulos et al., 2023b). This observation motivates a more adaptive approach: rather than committing to a fixed reliance on synthetic data, one should automatically adjust the reliance of the PPI estimator (7.7) based on the observed quality of the autoevaluator.
7.4
Adaptive Autoevaluation (R-AutoEval+)
R-AutoEval+ (Park et al., 2025) resolves the tension between R-Eval and RAutoEval by introducing a reliance factor ρ ∈ [0, 1] that controls the degree to which the estimate (7.7) relies on synthetic data. Rather than fixing ρ in advance, R-AutoEval+ considers a finite grid of S candidate values (7.11)
0 = ρ1 < ρ2 < · · · < ρS = 1,
and adaptively determines which candidate best matches the quality of the autoevaluator based on the accumulated evidence. For each candidate ρs , define the corresponding estimate by generalizing (7.7) as (Angelopoulos et al., 2023b) ρs ℓfs,i (λ) =
ri X
Lλ X̃i′ , f (X̃i′ )
r ′ i =r(i−1)+1 | {z
autoevaluator data
}
(7.12)
+ Lλ (Xi , Yi ) − ρs · Lλ (Xi , f (Xi )) . | {z } bias correction
Setting ρs = 0 recovers the pure real-data observation, i.e., R-Eval, whereas ρs = 1 recovers the PPI effective observation (7.7), i.e., R-AutoEval. 96
Lemma 7.2 (Validity of the ρs -weighted estimates). The estimate ℓfs,i (λ) in (7.12) is an unbiased estimate of R(λ), i.e., E[ℓfs,i (λ)] = R(λ), with range ℓfs,i (λ) ∈ [−ρs , 1 + ρs ]. Proof. The proof follows by the same argument as Lemma 7.1. For each candidate factor ρs , R-AutoEval+ constructs a separate e-process λ Es,i =
i Y j=1
1 − µs,j ℓfs,j (λ) − α ,
(7.13)
λ using the effective observations (7.12). Larger values of Es,i indicate that reliance factor ρs is accumulating strong evidence in favor of the reliability of λ. The R-AutoEval+ e-value combines these S processes via adaptive exponential weighting as
Enλ =
n X S Y i=1 s=1
ws,i 1 − µs,i ℓfs,i (λ) − α ,
(7.14)
where the weight ws,i assigned to the s-th factor at round i is updated proportionally to the evidence accumulated by that factor as ws,i (λ) = PS
λ ws,0 · Es,i−1
s′ =1
ws′ ,0 · Esλ′ ,i−1
,
(7.15)
P with strictly positive initial weights {ws,0 }Ss=1 satisfying Ss=1 ws,0 = 1. The update rule (7.15) is an instance of exponential weighting, namely the Hedge algorithm (Freund and Schapire, 1997). In this algorithm, factors that accumulate large e-values, indicating that the corresponding level of reliance on synthetic data is well-supported by the data, are assigned proportionally larger weights. Lemma 7.3 (Validity of the R-AutoEval+ e-value). The quantity Enλ in (7.14) is a valid e-value for the null hypothesis Hλ : R(λ) > α, i.e., E[Enλ | R(λ) > α] ≤ 1. Proof. Since each quantity ℓfs,i (λ) is an unbiased estimate of the true risk R(λ) with range [−ρs , 1 + ρs ] and µs,i ∈ (0, 1/(1 + ρs − α)), each term 1 − 97
µs,i (ℓfs,i (λ) − α) is non-negative. Under the null hypothesis R(λ) > α, since the weights ws,i depend only on past observations {ℓfs,j (λ)}j<i , the conditional expectation of each factor satisfies " S # X f f E ws,i 1 − µs,i (ℓs,i (λ) − α) {ℓs,j }j<i , R(λ) > α s=1
=
S X s=1
(7.16)
ws,i 1 − µs,i (R(λ) − α) ≤ 1.
Taking iterated expectations and using the fact that E0λ = 1, by induction we obtain E[Enλ | R(λ) > α] ≤ 1. The validity of the e-value in Lemma 7.3 implies that the test Tn = I{maxi≤n Eiλ ≥ 1/δ} satisfies the reliability condition P(Tn = 1 | R(λ) > α) ≤ δ, providing the same finite-sample guarantee as R-Eval and R-AutoEval. To certify a set of hyperparameters Λ̂ ⊆ Λ with FWER or FDR control, Algorithm 6 is run for each candidate λk ∈ Λ, and the resulting e-values {Enλk }K k=1 are fed into any of the MHT procedures described in Chapter 2. The adaptive weighting in (7.15) is designed so that R-AutoEval+ tracks the best reliance factor ρs in the grid (7.11), achieving a sample complexity no larger than the best of R-Eval and R-AutoEval. In particular, reference (Park et al., 2025) shows that, under the main condition that the betting strategies {µs,i } satisfy sublinear regret with respect to the optimal constant betting parameters µs,⋆ , the sample complexity of R-AutoEval+ satisfies, as δ → 0, the inequality R-Eval nR-AutoEval+ (δ, λ) ≤ min nmin (δ, λ), nR-AutoEval (δ, λ) . (7.17) min min Furthermore, a strict improvement in sample complexity is obtained when there exists an intermediate reliance factor ρs ∈ (0, 1) for which the variance of ℓfs,i (λ) is strictly smaller than for both ρ1 = 0 (corresponding to R-Eval, with observation Lλ (Xi , Yi )) and ρS = 1 (corresponding to R-AutoEval, with observation ℓfi (λ)). This occurs whenever the autoevaluator is sufficiently but not perfectly accurate. The complete R-AutoEval+ procedure for a single candidate hyperparameter λ is summarized in Algorithm 6. It processes labeled samples sequentially, updating the weighted e-value at each round. Once Algorithm 6 has been run for all candidates λk ∈ Λ, the resulting e-values are fed into 98
Algorithm 6 R-AutoEval+ (Park et al., 2025) Input: Candidate hyperparameter λ; ground-truth labeled data {(Xi , Yi )}ni=1 ; unlabeled data Dunl ; autoevaluator f ; risk threshold α; error level δ; reliance factors {ρs }Ss=1 as in (7.11); initial weights {ws,0 }Ss=1 with PS s=1 ws,0 = 1 Output: E-value Enλ for use in MHT (see Chapter 2) λ ← 1 for all s Initialize E0λ ← 1, Es,0 for i = 1, . . . , n do λ ws,0 · Es,i−1 Compute weights ws,i ← PS for all s λ s′ =1 ws′ ,0 · Es′ ,i−1 for s = 1, . . . , S do Compute effective observation ℓfs,i (λ) via (7.12) λ λ Update Es,i ← Es,i−1 · 1 − µs,i (ℓfs,i (λ) − α) end for P λ · Ss=1 ws,i · 1 − µs,i (ℓfs,i (λ) − α) Update Eiλ ← Ei−1 end for return Enλ the MHT procedures of Chapter 2 to obtain a certified set Λ̂, exactly as in Algorithm 5.
7.5
Example: Adaptive Autoevaluation for Wireless Scheduling
We illustrate the autoevaluation framework on the wireless scheduling application of Sec. 3.2, using the Nokia delay table (Valcarce, 2020) as the source of ground-truth episodes. As in Sec. 6.4, we consider K = 20 candidate scheduler configurations. To bring the variance of the per-sample loss into a regime where the autoevaluation framework is informative, we adopt the per-episode binary service-level agreement (SLA) loss Lλk (Xi , Yi ) = I delayλk (Xi ) > 10 ms , (7.18) which records whether the average packet delay in episode Xi violates the 10 ms SLA under configuration λk . We set the tolerated violation rate to 99
α = 0.3 and the outage rate to δ = 0.1. Under the loss (7.18), the empirical risks of the 20 candidates range from 0 to 0.84, with 16 candidates reliable. The autoevaluator is constructed as a biased low-variance proxy of the binary loss. Specifically, for each candidate λk with population mean R(λk ), the autoevaluator’s per-sample loss is given by the convex-shrinkage construction Lλk (Xi , f (Xi )) = R(λk ) + bk + κ Lλk (Xi , Yi ) − R(λk ) , (7.19) where κ ∈ [0, 1] controls the fidelity of the autoevaluator and bk is a small per-candidate systematic bias drawn from N (0, 0.022 ) and truncated to the range that keeps Lλk (Xi , f (Xi )) in [0, 1] without clipping. The construction (7.19) models a low-fidelity surrogate of the simulator: with κ = 0.9, the variance of the autoevaluator is reduced by a factor of κ2 ≈ 0.8 relative to the binary truth, while the per-candidate bias bk , fixed once drawn, introduces a constant offset between the autoevaluator’s mean and the true risk R(λk ), simulating the calibration mismatch that occurs when an automated evaluator is not perfectly aligned with the ground-truth loss. The unlabeled term in the PPI estimate (7.7) is approximated by the population mean of the autoevaluator over all 200 episodes. A direct computation shows that, with the autoevaluator (7.19), the PPI effective observation (7.12) reduces to ℓfs,i (λk ) = (1 − ρs κ) Lλk (Xi , Yi ) + ρs κ R(λk ),
(7.20)
which is a convex combination of two quantities in [0, 1], implying the inclusion ℓfs,i (λk ) ∈ [0, 1] for every reliance factor ρs . Under this tighter range, the per-round factor 1 − µs,i (ℓfs,i (λk ) − α) remains non-negative as long as µs,i ∈ (0, 1/(1 − α)), which is strictly more permissive than the worst-case range µs,i ∈ (0, 1/(1 + ρs − α)) of Lemma 7.3. We compare three statistically valid certification methods: R-Eval, which uses only ground-truth labels via the e-process (7.5); R-AutoEval with reliance factor ρ = 1, i.e., the PPI e-process (7.10); and R-AutoEval+ with the reliance grid {0, 1/3, 2/3, 1} and uniform initial Hedge weights ws,0 = 1/4. For all three methods, the betting parameter µs,i is chosen via the aGRAPA strategy of Sec. 6.2, which sets µs,i to the value maximizing the expected log-wealth growth (see Sec. 6.2), estimated from the empirical mean and variance of the past i − 1 effective observations, clipped to the validity range (0, 1/(1 − α)). Certification of λk from a budget of n ground-truth labeled 100
samples uses the Bonferroni-corrected anytime-valid test maxτ ≤n Eτλ ≥ |Λ|/δ, providing FWER control at level δ. We report the true positive rate (TPR), defined as the fraction of truly reliable hyperparameters certified, averaged over 300 independent calibration sequences. Fig. 7.2 presents the results. Panel (a) plots TPR against the number of ground-truth labeled samples n, while panel (b) plots the miss rate 1 − TPR on log–log axes. The autoevaluation methods are dramatically more sample-efficient than R-Eval: R-AutoEval already certifies 94% of the reliable hyperparameters by n = 80 labeled samples and reaches near-perfect TPR by n = 400, whereas R-Eval reaches only 59% at n = 80 and is still below 80% at n = 2000. The bottleneck for R-Eval is the variance of the binary loss, which equals R(λk )(1 − R(λk )) and can be close to 1/4 for hyperparameters near the threshold; the PPI estimate (7.20) reduces this variance by a factor (1−ρs κ)2 , which gives R-AutoEval roughly an order-of-magnitude advantage. R-AutoEval+ tracks R-AutoEval after a brief warm-up of fewer than 50 rounds, demonstrating that the Hedge re-weighting in (7.15) concentrates rapidly on the high-reliance processes when the autoevaluator is informative. All three methods satisfy the finite-sample reliability constraint, with empirical FWER violation rate equal to zero across all values of n. The main takeaway message is that, when the autoevaluator is informative enough to reduce the variance of the PPI effective observation, RAutoEval and R-AutoEval+ certify reliable hyperparameters with markedly fewer ground-truth labeled samples than R-Eval. R-AutoEval+ retains this benefit while remaining safe to deploy without prior knowledge of the quality of the autoevaluator.
7.6
Summary
This chapter extended the LTT framework to the autoevaluation setting, where ground-truth labeled data are expensive and a large pool of autoevaluated data is available at low cost. The core methodological challenge is that autoevaluators introduce bias, making it impossible to use synthetic labels directly in the testing framework without compromising the reliability guarantee. R-AutoEval addresses this challenge through PPI (Angelopoulos et al., 2023b). By using a small amount of real data to correct for the autoevaluator’s bias, R-AutoEval con101
Miss rate 1 − TPR (log scale)
True positive rate (TPR)
(a) TPR 1.0 0.8 0.6 0.4
R-Eval R-AutoEval R-AutoEval+
0.2 0.0 101
102
103
Number of labelled samples n (log scale)
(b) Miss rate (log scale) 100
10−1
10−2
R-Eval R-AutoEval R-AutoEval+
10−3 101
102
103
Number of labelled samples n (log scale)
Figure 7.2: Comparison of R-Eval, R-AutoEval (with reliance factor ρ = 1), and R-AutoEval+ on the wireless scheduling task of Sec. 3.2, with K = 20 candidate scheduler configurations, the binary SLA loss (7.18), target risk α = 0.3, outage rate δ = 0.1, autoevaluator fidelity κ = 0.9, and bias standard deviation 0.02. (a) True positive rate (TPR) as a function of the number of ground-truth labeled samples n. (b) Miss rate 1 − TPR on log– log axes, which exposes the late-saturation regime. Results are averaged over 300 independent calibration sequences. R-AutoEval and R-AutoEval+ certify essentially all reliable hyperparameters by n ≈ 400, whereas R-Eval is still missing more than 20% at n = 2000. structs unbiased effective observations that can be plugged into the e-process framework of Chapter 6. However, R-AutoEval can increase sample complexity compared to REval when the autoevaluator is inaccurate, since the bias correction term introduces additional variance. R-AutoEval+ (Park et al., 2025) resolves this tension by maintaining a family of reliance factors {ρs }Ss=1 and adaptively weighting them based on accumulated evidence via the exponential weighting scheme (7.15). The resulting method provably dominates both R-Eval and R-AutoEval in terms of sample complexity (7.17), while preserving the same finite-sample reliability guarantee. A key practical message of this chapter is that, under suitable assumptions, autoevaluators can be incorporated into statistically valid hyperparameter selection without risk: R-AutoEval+ is guaranteed to perform at least as well as conventional ground-truth labeled testing, and strictly better when the autoevaluator provides useful information. This makes it a natural default for modern AI deployment pipelines where automated evaluation 102
tools are readily available (Einbinder et al., 2025; Angelopoulos et al., 2023b; Angelopoulos et al., 2023a). The autoevaluation framework of this chapter is complementary to the adaptive sequential framework of Chapter 6. While aLTT reduces evaluation cost by concentrating testing effort on the most promising candidates across rounds, R-AutoEval+ reduces the cost of each individual evaluation by substituting expensive human labels with cheap synthetic ones. Combining both directions, i.e., adaptive sequential testing with autoevaluated observations, is a natural avenue for future work.
103
Chapter 8 Outlook and Future Work This monograph has developed a rigorous framework for statistically valid hyperparameter selection in AI and machine learning systems. Starting from the Learn-Then-Test (LTT) method (Angelopoulos et al., 2025), the monograph has progressively extended the core methodology along several dimensions: non-average risk measures such as quantile risk and informationtheoretic constraints (Chapter 4); multi-objective selection via Pareto testing and reliability graphs (Chapter 5); adaptive and sequential selection using eprocesses and the adaptive LTT (aLTT) algorithm (Chapter 6); and hyperparameter selection with limited labeled data via prediction-powered inference and the R-AutoEval framework (Chapter 7). A unifying theme across all chapters is the use of hypothesis testing as the bridge between statistical evidence and deployment decisions. P-values and e-values, introduced in Chapter 2 and reviewed in depth in Appendix A, each provide finite-sample reliability guarantees with distinct practical trade-offs: P-values are well-suited to single-shot evaluation with pre-specified sample sizes, while e-values enable anytime-valid, adaptive, and compositional testing that is essential for the sequential and multi-stage settings treated in Chapters 6 and 7.
8.1
Outlook
The LTT framework and its variants have reached a level of maturity that supports deployment in real AI engineering pipelines. The core theoretical guarantees, i.e., control of FWER and FDR at finite sample sizes, without 104
distributional assumptions beyond boundedness of the loss, are well established and have been validated in image classification (Sec. 3.1) and wireless scheduling (Sec. 3.2) applications. The shift from p-value-based to e-value-based testing has proven particularly fruitful for adaptive and sequential settings. E-processes, introduced in Chapter 6, allow the analyst to interleave evaluation and selection, concentrate testing resources on the most promising candidates, and incorporate autoevaluated data without compromising the reliability guarantee. These properties make e-value-based methods the natural choice for large-scale or online deployment scenarios. The prediction-powered inference (PPI) framework (Angelopoulos et al., 2023b; Einbinder et al., 2025) underlying R-AutoEval and R-AutoEval+ provides a principled way to exploit cheap automated evaluations without sacrificing statistical validity. As automated evaluation tools, e.g., large language models used as judges (Zheng et al., 2023), become ubiquitous in modern AI pipelines, the autoevaluation framework of Chapter 7 provides a ready-made solution for incorporating them into statistically valid selection.
8.2
Open Problems and Research Opportunities
Continuous and structured hyperparameter spaces: The LTT framework, in both its basic and extended forms, is designed for a finite candidate set Λ = {λ1 , . . . , λK } of hyperparameters. Extending the methodology to continuous or combinatorially large spaces, without requiring exhaustive evaluation of all candidates, is an important open problem. One direction is to combine LTT with Bayesian optimization or active learning to focus evaluation on a small promising subset (Paine et al., 2020), but theoretical guarantees for this combination remain largely open. Distribution shift: All the reliability guarantees developed in this monograph assume that the calibration data D are drawn from the same distribution as the deployment environment. In practice, distribution shift between calibration and deployment is common and may invalidate the guarantees. Extending the framework to handle covariate shift, label shift, or general nonstationarity is a natural and practically important direction, with potential connections to robust statistics and distributionally robust optimization. 105
Multi-task and meta-learning settings: In many practical applications, hyperparameter selection is performed repeatedly for related tasks, e.g., multiple users, environments, or problem instances. Sharing calibration data or statistical power across tasks, e.g., via meta-learning or hierarchical models, could substantially reduce the per-task sample complexity. Formalizing this in a way that preserves the finite-sample reliability guarantee is an open problem. Online and non-stationary environments: The sequential and adaptive methods of Chapter 6 allow the sample size to grow over time but still assume a stationary data-generating distribution. In non-stationary environments, where the optimal hyperparameter may change over time, a framework that tracks the best hyperparameter while maintaining reliability guarantees at every time step is needed. Connections to online learning and tracking (Audibert et al., 2009) may be fruitful here. Integration with autoevaluation at scale: The R-AutoEval framework of Chapter 7 handles a single fixed autoevaluator. As AI systems increasingly use ensembles of automated evaluators, or evaluators that are themselves updated over time, generalizing R-AutoEval+ to the multi-autoevaluator and online-autoevaluator settings is an important open problem. The PPI++ framework (Angelopoulos et al., 2023a) and its cross-prediction variant (Zrnic and Candès, 2024) offer relevant technical machinery. Interpretability and post-selection analysis: The LTT framework certifies which hyperparameters are reliable, but does not explain why certain configurations are reliable or how to improve unreliable ones. Combining reliability certification with interpretability tools, such as feature attribution or sensitivity analysis, would provide more actionable guidance for practitioners and is an avenue largely unexplored in the current literature.
106
Acknowledgements The authors are grateful to Sangwoo Park and Matteo Zecchin for their collaboration on several of the results presented in this monograph. This work was supported by the European Research Council (ERC) under the European Union’s Horizon Europe Programme (grant agreement No. 101198347). The work of O. Simeone was also supported by an EPSRC Open Fellowship (EP/W024101/1) and by the EPSRC project (EP/X011852/1).
107
Appendix A How to Measure Evidence This appendix reviews in a self-contained fashion the modern toolbox for quantifying evidence against a statistical null hypothesis. We start from the classical notion of a p-value as a stochastically large statistic under the null. We then discuss two structural limitations of p-values, namely their lack of anytime validity and the absence of a simple rule for combining independent evidence. To address these limitations, we introduce e-values and e-processes as non-negative statistics with unit mean under the null. Technical details on p-value constructions from concentration bounds and additional FWERand FDR-controlling procedures are collected in Appendices B and C.
A.1
Evidence via Hypothesis Testing
We observe data X1 , X2 , . . . , Xn drawn from some unknown distribution P. A statistical hypothesis is a claim about the distribution P. Formally, it corresponds to a partition of the set of all allowed candidate distributions P, which is possibly a strict subset of all distributions, into two disjoint subsets as in H0 : P0 (null)
and
H1 : P1 = P \ P0 (alternative).
(A.1)
The null H0 typically represents the status quo: a new drug is not effective, an AI model is not reliable, a new software still contains bugs, and so on. The alternative encodes the corresponding positive claim. Rejecting the null in favor of the alternative means that the observed data are sufficiently 108
inconsistent with every distribution P ∈ P0 , lending support to the claim described by P1 . The central questions addressed in this appendix are: Does the data provide evidence against the null ? Can the amount of evidence be quantified so as to support principled decision making?
A.1.1
Examples
The following are useful and common examples. i.i.d.
Example 1: Testing a mean value: Let X1 , X2 , . . . ∼ P take values in [0, 1] with unknown mean µ(P) = E[X]. For fixed values µ0 , µ1 ∈ (0, 1), test H0 : µ(P) = µ0
vs.
H1 : µ(P) = µ1 .
(A.2)
In a clinical context, the observation Xi may represent a biomarker, with µ0 the average value for a healthy patient and µ1 that of a sick patient. The hypotheses are composite: each contains many distributions, since only the mean is fixed. □ i.i.d.
Example 2: Testing a zero mean: With X1 , X2 , . . . ∼ P on the real line, test H0 : µ(P) = 0 vs. H1 : µ(P) ̸= 0. (A.3)
This test may be useful, for example, to assess whether augmenting a dataset with synthetic samples changes the average model performance, i.e., whether the mean difference in losses equals zero. Both hypotheses are composite, and the set P encompasses all distributions with finite mean. □ i.i.d.
Example 3: Testing a bound on the mean: For X1 , X2 , . . . ∼ P in [0, 1] and tolerance µmax ∈ (0, 1), test H0 : µ(P) ≥ µmax (negative)
vs.
H1 : µ(P) < µmax (positive). (A.4)
Here the observation Xi may represent a score or loss (smaller is better) of a drug, AI model, or theory. □
109
i.i.d.
Example 4: Two-sample testing: Given X1 , . . . , Xn ∼ PX indepeni.i.d. dent of Y1 , . . . , Ym ∼ PY , test H0 : PX = PY
vs.
(A.5)
H1 : PX ̸= PY .
A typical application contrasts measurements from nominal conditions (Xi ) with those from a test population (Yi ). □ Example 5: Testing independence: For paired observations i.i.d. (X1 , Y1 ), . . . , (Xn , Yn ) ∼ PXY , test H0 : PXY = PX ⊗ PY
vs.
(A.6)
H1 : PXY ̸= PX ⊗ PY ,
where observation Xi might be a treatment assigned to patient i and Yi a downstream biomarker. □
A.1.2
Setting Up the Hypotheses
Setting a hypothesis test to evaluate a claim about the data distribution P requires defining a null class P0 together with the alternative class P1 , or equivalently the set P of all allowed distributions. The null H0 : P ∈ P0 is a modelling choice that governs both what can be concluded from a rejection and how hard it is to design a valid test. A broad null, corresponding to a large set P0 , may support a more tractable test construction, but it typically requires more data to be rejected, since the test must hedge against more null distributions P ∈ P0 . A more specific null, with a small set P0 , may make valid test construction harder, but it allows the test to enhance its statistical power, i.e., its capacity to correctly reject the null under an alternative distribution P ∈ P1 . d
Example 2 (continued): Testing a zero mean: Denote as = equality in distribution. In place of the zero-mean null H0 : µ(P) = 0, one may test the more specific null d H0′ : X = −X, (A.7)
stipulating that the distribution P is symmetric about zero. Since symmetry about zero implies a zero mean, the set P0′ covered by the null H0′ is included in the original set P0 , i.e., d
P0′ = {P : X = −X} ⊂ {P : µ(P) = 0} = P0 . 110
(A.8)
The price of this specialization is that rejecting the null H0′ does not imply rejection of the original null H0 , because the data may be incompatible with symmetry while the mean is still zero. As we will see, the advantage of this approach is that one can construct more powerful tests for the null H0′ . □ Example 6: Testing exchangeability and anomaly detection: Conversely, testing an enlarged null can leverage structural symmetries or invariances to make test design more tractable. In this case, rejecting the larger null also rejects the original null. A canonical example of a structured larger null is exchangeability. To elaborate, denote as Sn the set of all permutations of n integers. Definition A.1. The random variables X1 , . . . , Xn are exchangeable if for every permutation π ∈ Sn the joint distribution P is unchanged, i.e., d
(X1 , . . . , Xn ) = (Xπ(1) , . . . , Xπ(n) );
(A.9)
equivalently, if the joint distribution P depends only on the multiset of values {x1 , . . . , xn }. Sequences with i.i.d. samples are exchangeable, but the class of exchangeable distributions is strictly larger, including equicorrelated Gaussians, samples drawn without replacement from a finite population, and functions of i.i.d. variables with shared randomness. The exchangeability null, H0 : X1 , . . . , Xn exchangeable,
(A.10)
can provide a tractable, enlarged hypothesis for many settings of interest. To illustrate this point, consider the task of anomaly detection. In it, given a calibration set X1 , . . . , Xn−1 and a new point Xn , we wish to determine if the test point Xn is an anomaly or not. To this end, we can test whether the sample X1 , . . . , Xn , including calibration and test data is exchangeable. □ Example 4 (continued): Two-sample testing: For two-sample testing, define the pooled samples as Z = (Z1 , . . . , Zn+m ) = (X1 , . . . , Xn , Y1 , . . . , Ym ). 111
(A.11)
Under the original null H0 : PX = PY , the pooled sample is exchangeable, so that the larger null H0′ : Z1 , . . . , Zn+m exchangeable contains H0 , and rejecting H0′ rejects also H0 .
(A.12) □
Example 5 (continued): Testing independence: For independence testing, under the original null H0 : PXY = PX ⊗ PY the sequence Y1 , . . . , Yn is exchangeable conditional on X1 , . . . , Xn , so the exchangeability null H0′ : Y1 , . . . , Yn exchangeable given X1 , . . . , Xn
(A.13)
contains the original null H0 . □ Beyond the null, the overall set P encodes the distributions deemed plausible, with P1 = P \ P0 being the alternative set. A broad set P ensures robustness with respect to possible alternative ground-truth conditions. However, this comes at the cost of power, since the test must hedge against many possible deviations from the null H0 . Conversely, a narrow set P delivers higher power, but it exposes the analysis to misspecification, as the true distribution may lie outside P. The power of a test will be discussed further in Sec. A.2.3.
A.1.3
Measures of Evidence
To carry out a test, one needs a statistic computed from the data that serves as a measure of evidence against the null. Three properties are desirable for such measures: • Validity: The statistic should take an extreme value (small or large, by convention) when the data would be surprising under the null H0 . This property supports tests obtained by thresholding the statistic while allowing for the control of the probability of false alarm. • Anytime validity: Evidence should remain “honest” regardless of when one decides to stop collecting data, whether before, after, or mid-study. In other words, the probability of false alarm should not be inflated by optional stopping mechanisms for data collection.
112
Property
P-value E-value
Validity at fixed sample size
Yes
Yes
Anytime validity
No
Yes
Compositional validity (product, independent)
No
Yes
Compositional validity (average, any dependence)
No
Yes
Table A.1: Comparison of key properties of P-values and E-values. • Compositional validity: Evidence from independent sources should combine into a single, valid measure of evidence without additional assumptions: more experiments should mean more evidence. This appendix focuses on two such measures: p-values, also known sometimes as p-variables, and e-values, or e-variables. As summarized in Table A.1, both statistics satisfy the first property, namely validity at a fixed sample size, but only e-values automatically satisfy the other two.
A.2
P-values
A.2.1
Definition
A p-value for the null H0 is a statistic p = p(X1 , . . . , Xn ) ∈ [0, 1] that tends to be large when the null H0 is true, so that small values of variable p flag surprising observations under the null H0 . The resulting test takes the form reject H0 if p ≤ δ,
(A.14)
for a prespecified threshold δ ∈ (0, 1), chosen as a function of the target probability of false alarm. Formally, the condition of being large under the null means that p is stochastically larger than a uniform random variable on [0, 1], i.e., superuniform. Definition A.2 (p-value). A p-value for H0 is a statistic p ∈ [0, 1] such that, for every distribution P ∈ P0 and every u ∈ (0, 1), we have the inequality P(p ≤ u) ≤ u. 113
(A.15)
Equivalently, as illustrated in Fig. A.1, the cumulative distribution function (CDF) of p lies on or below the diagonal of the unit square. As also illustrated in Fig. A.1, a p-value controls the probability of false alarm, i.e., the type-I error. P(p ≤ u) 1 rm
U
fo ni
0.5
type-I error ≤ δ
δ 0 δ
0.5
1
u
Figure A.1: By definition, the CDF of a p-value lies on or below the uniform diagonal under any null distribution P ∈ P0 . The value of the CDF at u = δ coincides with the type-I error of the test “reject H0 if p ≤ δ”, and is no larger than δ by construction. Proposition A.1 (type-I error control). The test “reject H0 if p ≤ δ” controls the probability of false alarm at level δ, i.e., for every distribution P ∈ P0 , we have the inequality P(reject H0 ) ≤ δ. (A.16) Proof. By the definition of a p-value, we have P(reject H0 ) = P(p ≤ δ) ≤ δ. A p-value whose CDF is strictly below the diagonal is conservative, in the sense that it controls the type-I error at a value smaller than δ, which typically entails a lower power under the alternative H1 (see Sec. A.2.3). Accordingly, the ideal case is a uniformly distributed p-value. As a final remark, based on Proposition A.1, it is tempting to read smaller p-values as stronger evidence against the null H0 . The popular argument runs: “p is the smallest significance level δ at which, had I pre-specified it, 114
I would have rejected H0 ”. It should be noted, however, that this is only a counterfactual statement. In fact, setting δ = p after observing the data does not provide a valid type-I error guarantee, and is not the same as a quantitative statement about factual evidence. That said, in practice, the p-value is often used as an informal measure of evidence, whose usefulness in that role depends on the test’s power against the alternative of interest (see Sec. A.2.3).
A.2.2
Rank P-value
The null (H0 : X1 , . . . , Xn exchangeable) in (A.10) admits a particularly simple and exact p-value, which serves as a useful first example to illustrate the definition of p-values. Given real-valued scalar data X1 , . . . , Xn ∈ R, the rank statistic at the i-th index is the number of values Xj that are no larger than Xi , i.e., rank(Xi ; X1 , . . . , Xn ) = |{j : Xj ≤ Xi }|, (A.17) where | · | denotes the set cardinality.
Proposition A.2. Under the exchangeability null H0 and assuming no ties almost surely, for any fixed index i ∈ {1, . . . , n}, the rank statistic is uniformly distributed in the set {1, . . . , n}, i.e., rank(Xi ; X1 , . . . , Xn ) ∼ Unif{1, . . . , n}.
(A.18)
Proof. All n! orderings of X1 , . . . , Xn are equally likely, so the variable Xi is equally likely to occupy each of the n positions. This result immediately yields a p-value for the exchangeability null. Definition A.3 (Rank p-value). For real-valued scalar data X1 , . . . , Xn ∈ R, the statistic rank(Xn ; X1 , . . . , Xn ) p = (A.19) n is a p-value for the exchangeability null. Note that the rank p-value can be proved to remain valid when ties are allowed, although it is no longer uniformly distributed under the null. It is also emphasized that the reference index n in (A.19) is arbitrary, and it may also be chosen at random from the set {1, . . . , n}. 115
Example 6 (continued): Testing exchangeability and anomaly detection: Consider the calibration set {X1 , . . . , Xn−1 } given by {−1.21, −0.95, −0.62, −0.37, 0.17, 0.43, 0.88, 1.02, 1.55}
(A.20)
together with a test point X10 . The rank p-value p10 = |{j : Xj ≤ X10 }|/10 measures the fraction of pooled samples not exceeding the test point X10 . Set the target type-I error to δ = 0.1. For the test point X10 = 0.50, we have p10 = 7/10 = 0.70 > δ and the point is not flagged as an anomaly. In contrast, for the test point X10 = −3.80, we have p10 = 1/10 = 0.1 ≤ δ and the point is flagged. □
A.2.3
Power
For a given null H0 , many statistics give rise to valid p-values. Among all such statistics, one would ideally wish to choose one that maximizes power against the alternative class H1 . Power refers to the probability of correctly rejecting the null under the alternative, i.e., to PP (p(X n ) ≤ δ) for distributions P ∈ P1 . Considering the worst case among all alternative distributions P ∈ P1 yields the objective max PP p(X n ) ≤ δ . (A.21) P∈P1
Example 6 (continued): Testing exchangeability and anomaly detection: Consider an anomaly detection problem in which the test sample Xn is anomalous if it is too large as compared to typical values. In this setting, the rank p-value p = |{j : Xj ≤ Xn }|/n discussed above would tend to 1 under the alternative. Therefore, while valid, this p-value is powerless against such anomalies, i.e., against such alternatives. Can we devise a more powerful rank p-value? Negating the data gives an equally valid rank p-value under the exchangeability null, i.e., |{j : Xj ≥ Xn }| . (A.22) p′ = n Importantly, this p-value tends to be small precisely when the test sample Xn is unusually large. For example, for the calibration set (A.20), with the test point X10 = 3.80, we set the p-value p′ = 1/10, correctly flagging the outlier, whereas the original rank p-value, p = 1, would not. 116
A.2.4
Summary Statistics
As seen for the exchangeability null, the construction of a p-value typically starts with the design of a suitable summary statistic as a function of the data X n , such as rank(Xn ; X1 , . . . , Xn ) used in Example 6. As a general rule, the summary statistic T (X n ) should be designed to be small under the null H0 and large under H1 . Example 7: Simple hypotheses: In the case of a simple null P0 = {P0 }, the natural choice is the information-theoretic surprise (see, e.g., (Simeone, 2026)) T (X n ) = − log P0 (X1 , . . . , Xn ). (A.23) If the alternative is also simple, i.e., P1 = {P1 }, the log-likelihood ratio P1 (X n ) n (A.24) T (X ) = log P0 (X n )
is the preferred choice, as it can be shown to be optimal in the sense of optimizing the power (A.21). □ Example 3 (continued): Testing a bound on the mean: For the null H0 : µ(P) ≥ µmax , a reasonable summary statistic is the mean-deficit n
T (X n ) = µmax −
1X Xi . n i=1
(A.25)
P In fact, when the empirical mean ni=1 Xi /n is close to the true mean µ(P), this statistic tends to be small under the null, as T (µ(P)) = µmax − µ(P) ≤ 0 under H0 , and large under the alternative, as T (µ) = µmax − µ(P) > 0 under H1 . □ Example 6 (continued): Testing exchangeability: The rank p-values are only applicable when the observed data are real scalars and when the alternative prescribes unusually small or large values. More generally, the exchangeability null may need to be tested for an arbitrary data type. In this case, one can start with a summary statistic T (X n ) designed to measure how unlikely data X n are under the null. As discussed next, any summary statistic can be turned into a valid p-value. To elaborate, for any permutation π ∈ Sn , let Xπn = (Xπ(1) , . . . , Xπ(n) ) denote the permuted sequence. 117
Proposition A.3. If the random vector X n is exchangeable, then the n! transformed random variables {T (Xπn )}π∈Sn are exchangeable. Proof sketch. A transformation preserves exchangeability if, for each input permutation, there exists an output permutation leaving the function unchanged. See (Ritzwoller et al., 2024) for details. Applying the rank p-value to these n! exchangeable values gives the permutation p-value |π ∈ Sn : T (Xπn ) ≥ T (X n )| p = , (A.26) n! where the inequality reflects the design assumption that large values of the summary statistic T (X n ) are surprising under H0 . Since computing the summary statistic T (X n ) on all n! permutations is usually infeasible, one can practically either leverage symmetries or apply Monte Carlo sampling (Ritzwoller et al., 2024). □ Example 5 (continued): Testing independence: For paired observations (X, Y ), a dependence statistic T (X, Y ), such as the absolute Pearson correlation or a mutual-information estimator, can be leveraged to yield a permutation p-value for the independence null upon permutation of the Y values (Ritzwoller et al., 2024). □ The set of permutations Sn is a group: it contains the identity, inverses, and is closed under composition. The permutation p-value generalizes to nulls defined by an arbitrary group-invariance property, yielding randomization pvalues (Ritzwoller et al., 2024).
A.2.5
Constructing P-values Using the Probability Integral Transform
Once a summary statistic is selected, the main challenge is to turn it into a valid p-value. To this end, the following result plays a key role. Theorem A.1 (Probability integral transform). If the random variable T is continuous with complementary CDF (CCDF) F̄ (t) = P(T ≥ t), then the random variable U = F̄ (T ) is uniformly distributed in the interval (0, 1), i.e., Unif(0, 1).
118
Proof. For any u ∈ (0, 1), since the CCDF F̄ (t) is continuous and strictly decreasing, we have P(U ≤ u) = P F̄ (X) ≤ u = P X ≥ F̄ −1 (u) = F̄ F̄ −1 (u) = u. (A.27) The transformation F̄ (T ) for a random variable T with CCDF F̄ (t) is known as the probability integral transform (PIT). The PIT can be readily applied to obtain a p-value. Lemma A.2 (p-value from PIT). Denote as F̄P (t) the CCDF of the test statistic T (X n ) under distribution P. Then, the quantity p(X n ) = max F̄P (T (X n )) P∈P0
(A.28)
is a p-value for the null H0 : P ∈ P0 . Note that the definition (A.28) contains a maximum over all the distributions in set P0 (or a supremum if the set is not closed) in order to account for the worst case among all the null distributions. To understand the significance of the p-value (A.28), it is useful to rewrite it in an equivalent way as follows. Define as X̃ n a fictitious dataset drawn from a distribution P. Fix the data X n , and imagine generating X̃ n independently of the fixed realization X n . As it can be directly checked, we have the equality F̄P (X n ) = PX̃ n ∼P T (X̃ n ) ≥ T (X n ) , (A.29) and thus the p-value (A.28) can also be expressed as
p(X n ) = max PX̃ n ∼P T (X̃ n ) ≥ T (X n ) . P∈P0
(A.30)
For a well-designed test statistic T (·), under an alternative distribution P ∈ P1 , the random variable T (X n ) with data X n ∼ P should be large. Accordingly, the probability in (A.30) tends to take small values under the alternative. This is precisely what is required to maximize the power.
A.2.6
Constructing P-values Using Concentration Bounds
In practice, the CCDF of a test statistic may not be known and, as a result, the PIT-based construction (A.28) of a p-value is not directly applicable. 119
However, it is often possible to identify an upper bound p̃(X n ) ≥ p(X n ) on the p-value (A.28). Any such upper bound is also a valid p-value. In fact, if p̃ ≥ p, the inequality p̃ ≤ u implies p ≤ u, and hence we have the defining condition P(p̃(X n ) ≤ u) ≤ P(p(X n ) ≤ u) ≤ u, (A.31)
for all P ∈ H0 , which coincides with the superuniformity of the variable p̃(X n ) under the null. The bound p̃(X n ) is generally conservative, yielding a CDF further below the diagonal than the exact p-value, but it is always valid. Example 3 (continued): Testing a bound on the mean: For observations Xi ∈ [0, 1] i.i.d. : µ(P) ≥ µmax , consider the test Pand the null H0 P statistic T (X n ) = µmax − ni=1 Xi /n, where ni=1 Xi /n is the empirical mean. The maximum in (A.28) is attained at the boundary µ(P) = µmax , since a larger mean increases the empirical mean X̄n , making a large statistic T (X n ) less likely. Applying Hoeffding’s inequality (Boucheron et al., 2013) to the p-value (A.28) produces the p-value !2 n X 1 (A.32) Xi − µmax . p(X n ) ≤ p̃(X n ) = exp−2n n i=1
□ More discussion on p-values obtained from concentration bounds can be found in Appendix B.
A.3
Limitations of P-values
Elaborating on Table A.1, we now discuss two key limitations of p-values, which motivate the introduction of e-values.
A.3.1
No Anytime Validity
The defining inequality P(pn ≤ u) ≤ u is a guarantee at a pre-specified sample size n. If, instead, the analyst inspects the data as it arrives and stops at a random time N chosen adaptively, then in general the inequality P(pN ≤ u) ≫ u 120
(A.33)
holds. This inequality can be interpreted as the phenomenon that “peeking” inflates the type-I error. A classical example is the “stop and reject as soon as pn ≤ δ” strategy. Under the null H0 , the running p-value will eventually fall below δ by chance, yielding a false rejection with probability tending to one. This optional-stopping pathology has been singled out as a contributor to the reproducibility crisis (Howard et al., 2021; Ramdas et al., 2023).
A.3.2
No Compositional Validity
A second limitation concerns combining independent evidence. If two independent studies report p-values p(1) and p(2) for the same null, neither the product p(1) p(2) nor the average is a valid p-value.
A.4
E-values
The structural shortcomings of p-values reviewed in the previous section motivate the introduction of a stronger measure of evidence. As discussed next, e-values can be derived as a generalization of likelihood ratios.
A.4.1
Definition
As seen in the previous section, when the hypotheses are both simple, i.e., P0 = {P0 } and P1 = {P1 }, the likelihood ratio T (X n ) =
P1 (X n ) , P0 (X n )
(A.34)
or equivalently its logarithm (A.24), offer the most powerful test statistic at any type-I level by the Neyman–Pearson lemma (Lehmann and Romano, 2005). We now observe that the likelihood ratio has a key property that supports generalization to a new class of evidence measures. Lemma A.3. Under the null H0 , the likelihood ratio has mean equal to one, i.e., EP0 [T (X n )] = 1. (A.35) Proof. The proof is by direct calculation: Z P1 (x) n EP0 [T (X )] = P0 (x) dx = 1. P0 (x) 121
(A.36)
The e-value generalizes the likelihood ratio by retaining and generalizing this property as follows. Definition A.4 (e-value). An e-value for the null H0 is a non-negative random variable E such that its mean under any of the null distributions does not exceed 1, i.e., for every P ∈ P0 .
EP [E] ≤ 1
(A.37)
According to this definition, large e-values indicate evidence against the null. The next proposition shows how an e-value supports testing by thresholding. Proposition A.4. The test “reject H0 when E ≥ 1/δ” controls the probability of false alarm at level δ, i.e., for every distribution P ∈ P0 , we have the inequality P(reject H0 ) ≤ δ. (A.38) Proof. By Markov’s inequality, we have P(E ≥ 1/δ) ≤ δ EP [E] ≤ δ. Example 6 (continued): Testing exchangeability: For non-negative observations X1 , . . . , Xn ≥ 0, the statistic E =
1 n
X Pn n
i=1 Xi
(A.39)
is an e-value for the exchangeability null, which is known as the soft-rank e-value P (Ramdas and Wang, 2025). Indeed, under exchangeability, the ratio Xj / ni=1 Xi has the same distribution for every j, so we have the equalities " Pn # X Xn j j=1 n EP Pn = EP Pn = 1, (A.40) i=1 Xi i=1 Xi implying the desired equality EP [E] = 1 for all P ∈ P0 .
122
□
A.4.2
P-values from E-values
Unlike a p-value, by its definition, an e-value constrains only its mean and not its entire CDF. As we discuss next, this yields a more robust, but generally less powerful, test statistic. Proposition A.5 (From e-values to p-values). For any e-value E for a null H0 , the statistic p = min(1, 1/E) is a p-value for H0 . Proof. Markov’s inequality gives 1 1 ≤ δ = PH0 E ≥ ≤ δ EH0 [E] ≤ δ, PH0 E δ
(A.41)
concluding the proof. The converse to the proposition, however, fails. In particular, if p is a p-value for 0 with p ∼ Unif(0, 1) under H0 , then the average yields R 1 H−1 EH0 [1/p] = 0 u du = ∞, so 1/p is not an e-value (Vovk and Wang, 2021; Ramdas and Wang, 2025). Overall, as shown in Fig. A.2, the inverses of evalues form a strict subset of the family of p-values. As discussed in the next section, e-values have special, additional, properties as compared to p-values. p-values
{1/E : E is an e-value}
Figure A.2: The inverses of e-values are valid p-values, but the converse fails. P-values obtained as the inverse of an e-value have special properties, namely post-hoc validity, compositional validity, and anytime validity.
Example 6 (continued): Testing exchangeability: The additional properties of e-values typically come with a loss of power. To see this, for the
123
exchangeability null, consider the soft-rank p-value against the rank p-value, i.e., Pn Xi 1 |{j : Xj ≥ Xn }| pE = = i=1 , prank = . (A.42) E nXn n One can readily check that we have the inequality pE ≥ prank pointwise. In fact, since we have Xi /Xn ≥ 1 whenever Xi ≥ Xn , we can write n 1 X Xi |{i : Xi ≥ Xn }| 1 X Xi ≥ ≥ = prank . pE = n i=1 Xn n i:X ≥X Xn n i
(A.43)
n
For a numerical example, with n = 4 and X n = (0.5, 1.0, 0.8, 2.5), the softrank-based p-value equals pE = 4.8/10 = 0.48, while the rank p-value is prank = 1/4 = 0.25. The compositional benefits of e-values, developed below, often justify the loss in power. □
A.5
Properties of E-values
In this section, we review the special properties of e-values, which set them apart from more general p-values.
A.5.1
Post-Hoc Validity
A common practice in applied work is to choose the significance level only after looking at the test statistic, for instance by reporting whichever of the conventional levels 0.05, 0.01, or 0.001 is just exceeded. This kind of post-hoc choice is not valid for p-values, since the standard guarantee PH0 (p ≤ δ) ≤ δ only protects levels δ that are fixed before the data are observed. As discussed in Sec. A.3.1, the p-value reading “I would have rejected at level p, had I prespecified it” is therefore counterfactual. The corresponding e-value reading “I reject at level 1/E” is, by contrast, a factual claim, as made precise in the rest of this subsection. Suppose that the analyst chooses the rejection level as a function δ(X n ) of the data X n = (X1 , . . . , Xn ). The strongest guarantee one could hope for is that, conditional on the chosen level, the probability of false rejection still does not exceed it, i.e., PX n |δ(X n ) [reject H0 ] ≤ δ(X n ) 124
for every P ∈ P0 ,
(A.44)
where the inner probability is computed under the conditional distribution P(X n | δ(X n )) of the data X n given the realized level δ(X n ), with P ranging over the null class P0 . Dividing through by the data-dependent level δ(X n ), the bound (A.44) is equivalent to the ratio inequality PX n |δ(X n ) [reject H0 ] ≤ 1. δ(X n )
(A.45)
As shown in (Koning, 2024), the strong conditional guarantee (A.45) is generally unattainable. A natural relaxation is to require the ratio to be bounded by one only on average over the random level δ(X n ). As the following theorem shows, the e-value rejection rule meets exactly this relaxed requirement. Theorem A.4 (Post-hoc validity (Ramdas et al., 2023; Koning, 2024)). Let E be an e-value for the null H0 . For any positive, possibly data-dependent, level δ(X n ) and any null distribution P ∈ P0 , we have PX n |δ(X n ) [reject H0 ] Eδ(X n ) ≤ 1, (A.46) δ(X n ) where the outer expectation is taken under the marginal distribution P(δ(X n )) of the data-dependent level induced by distribution P. Proof. The rejection event of the e-value test is {E ≥ 1/δ(X n )}. By the tower property of conditional expectation, the left-hand side of (A.46) equals the marginal expectation I{E ≥ 1/δ(X n )} . (A.47) E δ(X n ) On the rejection event, the indicator equals one, so the fraction equals 1/δ(X n ), which by definition of the event is at most E; off the rejection event, the fraction equals zero. The pointwise bound I{E ≥ 1/δ(X n )} ≤ E δ(X n )
(A.48)
thus holds for every realization. Taking expectations under P and using the e-value definition E[E] ≤ 1 gives (A.46).
125
The bound (A.46) substantiates the claim that, when using e-values, the analyst is free to inspect the calibration data, decide when to stop, and pick the rejection level after the fact. In fact, the expected ratio between the conditional type-I error and the chosen level is still bounded by one. The criterion (A.46) was further shown in (Koning, 2024) to serve as a natural measure of post-hoc validity within an axiomatic formulation.
A.5.2
Compositional Validity
While p-values cannot be generally combined, e-values combine in two simple ways. For independent e-values E (1) and E (2) for the same null, the product E (1) ·E (2) is again an e-value, since we have E[E (1) E (2) ] = E[E (1) ] E[E (2) ] ≤ 1. For arbitrarily dependent e-values E (1) , . . . , E (K) , the average (1) (K) 1 E + · · · + E (A.49) K is always an e-value by linearity of expectation. Example: Suppose labs A and B compute e-values EA = 7.3 and EB = 8.7. At level δ = 0.05 neither value exceeds the threshold 1/δ = 20. Their product, however, does, i.e., EA · EB ≈ 63.5 ≥ 20. Thus, the null H0 is rejected at δ = 0.05 using no distributional assumption beyond independence. □
A.5.3
Anytime Validity and E-processes
As discussed in Sec. A.5.2, a sequence of e-values for the same null can be multiplied to give a sequential measure of evidence. To elaborate, assume i.i.d. observations X1 , X2 , . . . with Et being an e-value computed from Xt . The running product Wn =
n Y
with W0 = 1,
Et ,
(A.50)
t=1
is an example of an e-process, which can be used for sequential testing, resolving the “peeking” problem of p-values highlighted in Sec. A.3. Before formalizing this property, we define e-processes more generally.
126
Definition Q A.5 (e-process). A non-negative process obtained as the prodn uct Wn = t=1 Et , with W0 = 1, is an e-process for the null class P0 if for every t ≥ 1, the statistic Et ≥ 0 depends only on the past observations X1 , . . . , Xt−1 , and for every P ∈ P0 and every past sequence X1 = x1 , . . . , Xt−1 = xt−1 , we have EP Et | X1 = x1 , . . . , Xt−1 = xt−1 ≤ 1. (A.51) The condition (A.51) generalizes the requirement that the variables Et be independent e-values, allowing dependence among the variables. The next result, a sequential analog of Proposition A.4, shows the anytime validity of tests obtained from e-processes. Theorem A.5 (Anytime validity, Ville’s inequality). Let {Wn } be an eprocess. The test “reject H0 as soon as Wn ≥ 1/δ” controls the Type-I error probability at level δ, i.e., 1 ≤ δ (A.52) P sup Wn ≥ δ n≥0 for all null distributions P ∈ P0 . By Theorem A.5, the analyst is free to peek, to plan optional stopping, and to revise the stopping rule mid-study, without inflating the Type-I error. As an illustration, Fig. A.3 shows several sample paths under the null H0 , together with one under the alternative H1 . The alternative path crosses the threshold and triggers rejection, while the H0 paths remain under the threshold. Example 3 (continued): Testing a bound on the mean: For the null H0 : µ(P) ≥ µmax with i.i.d. data Xi ∈ [0, 1], the quantity i h (A.53) Et = 1 + λt (µmax − Xt ), λt ∈ 0, 1−µ1max , is an e-value for every choice of the sequence λt such that λt depends only on the past observations X1 , . . . , Xt−1 . The constraint on the parameter λt keeps each factor non-negative, and one can directly check the requirement on the mean under H0 . This e-process has a useful interpretation in terms of betting (Waudby-Smith and Ramdas, 2024). □ 127
e-process Wn
reject
1/δ = 20 H1 path
10 1
0
2
4
6 8 10 observation n
H0 paths
12
14
Figure A.3: Several sample paths of an e-process under H0 (blue, shaded by trajectory) and one under H1 (green). Ville’s inequality (A.52) guarantees that under the null H0 the supremum supn≥0 Wn exceeds the threshold 1/δ with probability at most δ, so the test “stop and reject at the first crossing” is valid for any data-dependent stopping rule.
128
Appendix B P-value and E-value Constructions This appendix collects technical details on the construction of p-values and e-values, complementing the treatment in Chapter 2. Sec. B.1 presents a unified viewpoint on constructing valid test statistics via moment generating function bounds, covering bounded, sub-Gaussian, and sub-exponential losses. Sec. B.2 proves superuniformity of the Hoeffding-based p-value (2.22). Sec. B.3 reviews sharper finite-sample constructions, including exact binomial p-values for 0–1 losses, variance-sensitive Bernstein bounds, and the unifying Cramér–Chernoff perspective.
B.1
Alternative Construction of P-values and E-values
This section provides an alternative and unifying viewpoint on the construction of p-values and e-values. Rather than working directly with the empirical bn (λk ), we express evidence against the null hypothesis Hk in terms of risk R the cumulative sum of reliability margins. Here, ∆i,k = α − Lλk (Xi , Yi ) denotes the reliability margin of sample i under candidate λk , as introduced in Sec. 2.4. This perspective makes it transparent how standard concentration arguments lead to valid test statistics, and it naturally extends beyond bounded losses to more general tail assumptions. The cumulant generating function (CGF) of a random variable Z is defined
129
as the logarithm of its moment generating function (MGF): MZ (η) = E[exp(ηZ)] ,
(B.1)
for values of η for which the expectation exists. The CGF is thus log MZ (η). Following standard derivations of concentration bounds (Boucheron et al., 2013), assume that there exists a function ψ(η) such that, for all η > 0 the inequality log E exp η∆i,k | Hk ≤ ψ(η) (B.2) holds. That is, the function ψ(η) upper-bounds the CGF of the margin variable ∆i,k under the null Hk . Such bounds arise in many settings of practical interest: Bounded losses: If the loss Lλk (X, Y ) is bounded within the interval [0, 1], then the margin variable satisfies the condition ∆i,k ∈ [−1, 1]. By taking a log of both sides of (2.45), we obtain η 2 log E exp η(∆i,k − E[∆i,k ]) ≤ . 8
(B.3)
This yields a quadratic bound ψ(η) = η 2 /8 + ηE[∆i,k ]. Sub-Gaussian losses: If ∆i,k is conditionally sub-Gaussian with variance proxy σ 2 , then the cumulant generating function of ∆i,k is bounded by σ2η2 ψ(η) = ηE[∆i,k ] + . (B.4) 2 Such bounds arise for bounded random variables, Gaussian variables, and many light-tailed losses such as the squared loss with additive Gaussian noise, the logistic loss under bounded features, and the negative log-likelihood for sub-Gaussian observations (Vershynin, 2018; Boucheron et al., 2013). Sub-exponential losses: If ∆i,k is sub-exponential with parameters (ν, b), we have ψ(η) = ηE[∆i,k ] +
ν 2η2 2
1 for |η| < . b
(B.5)
This setting covers heavier-tailed losses while still permitting exponential concentration (Vershynin, 2018; Boucheron et al., 2013).
130
Lemma B.1. Given the bound (B.2) and a fixed η > 0, the statistic ! n X ek = exp η ∆i,k − nψ(η) ,
(B.6)
i=1
is a valid e-value for the null hypothesis Hk . Proof. Using independence of the calibration samples, we can write n Y E[ek | Hk ] = E exp η∆i,k − ψ(η) | Hk .
(B.7)
i=1
By (B.2) we have Hence,
E exp η∆i,k − ψ(η) | Hk ≤ 1.
(B.8)
E[ek | Hk ] ≤ 1,
(B.9)
so ek satisfies the defining property of an e-value (2.40).
B.2
Proof of Validity for the Hoeffding P-value
Proposition B.1 (Superuniformity of (2.22)). Under the null hypothesis Hk : R(λk ) > α, the p-value pk in (2.22) is superuniform, i.e., it satisfies P(pk ≤ u | Hk ) ≤ u for every u ∈ [0, 1]. Proof. Fix u ∈ (0, 1] and let r s(u) =
log(1/u) . 2n
(B.10)
bn (λk ) ≤ α − s(u). Under the null Hk , The event {pk ≤ u} is equivalent to R i.e., R(λk ) > α, this implies bn (λk ) − R(λk ) < −s(u). R Applying Hoeffding’s inequality (2.21) with t = s(u) yields P(pk ≤ u | Hk ) ≤ exp − 2n s(u)2 = u.
131
(B.11)
(B.12)
B.3
Refined Finite-Sample P-values for Bounded Losses
The Hoeffding p-value (2.22) is assumption-free, but it depends only on the range of the loss and is therefore conservative whenever the loss exhibits additional structure or small variance. This section reviews sharper constructions for bounded losses. All of them yield valid p-values for the null Hk : R(λk ) > α via the inversion principle of Sec. 4.3: a one-sided conbn (λk ) − R(λk ) is evaluated at the realized deviation centration bound on R b ∆k = (α − Rn (λk ))+ .
B.3.1
Exact Binomial P-values for 0–1 Losses
When the loss is binary, i.e., Lλk ∈ {0, 1}, as is the case for the 0–1 misbn (λk ) = Pn Lλ (Xi , Yi ) classification loss in (1.1), the test statistic S = nR k i=1 follows a binomial distribution with parameters n and R(λk ). Under the null R(λk ) > α, the left-tail probability P(S ≤ s) is monotonically decreasing in R(λk ), so the least favourable null distribution is the boundary R(λk ) = α. The resulting exact one-sided p-value is pbin k
S X n j = α (1 − α)n−j , j j=0
(B.13)
which is the classical Clopper–Pearson tail (Clopper and Pearson, 1934). The p-value (B.13) is exact rather than concentration-based, and is typically much sharper than the Hoeffding p-value (2.22) for binary losses.
B.3.2
Variance-Sensitive P-values
When the loss variance is small, the Hoeffding bound is loose because it depends only on the range of the loss. Bernstein-type inequalities incorporate the variance and can yield substantially tighter bounds. Specifically, letting σ 2 = Var(Lλk (X, Y )), Bernstein’s inequality (Bernstein, 1924; Bennett, 1962; Boucheron et al., 2013) states that, for any t > 0, nt2 b (B.14) P Rn (λk ) − R(λk ) ≤ −t ≤ exp − 2 2 . 2σ + 3 t 132
bn (λk ))+ Inverting the bound (B.14) at the realized deviation ∆k = (α − R yields the Bernstein p-value n∆2k Bern pk = exp − 2 2 . (B.15) 2σ + 3 ∆k Validity follows by the same argument as in the proof of Proposition B.1, with Hoeffding’s inequality (2.21) replaced by (B.14). Bennett’s inequality (Bennett, 1962) gives a related exponential bound with a slightly sharper exponent for moderate deviations, and can be inverted analogously. The variance σ 2 is generally unknown, and two strategies are common. The first replaces σ 2 by the worst-case bound σ 2 ≤ 1/4 valid for [0, 1]bounded losses, yielding a distribution-free refinement of Hoeffding. The second uses the empirical variance n 1X bn (λk ) 2 b Lλk (Xi , Yi ) − R Vn (λk ) = n i=1
(B.16)
in place of σ 2 in (B.15), invoking an empirical Bernstein inequality (Maurer and Pontil, 2009; Audibert et al., 2009) to obtain a fully data-adaptive p-value. Empirical Bernstein p-values are particularly powerful when the deployed predictor is near-deterministic for most inputs, so that the per-sample loss variance is small.
B.3.3
The Cramér–Chernoff Method
The Cramér–Chernoff method (Chernoff, 1952) provides a unifying perspective on the constructions above. As detailed in Sec. B.1, all the bounds discussed here can be obtained by upper-bounding the cumulant generating function of the per-sample reliability margin under the null and inverting the resulting exponential bound. Different assumptions on the loss, such as boundedness, sub-Gaussianity, or sub-exponentiality, yield different bounding functions ψ(η) and hence different p-value constructions, but the underlying methodology is the same.
133
Appendix C Additional Multiple Testing Procedures This appendix collects additional multiple testing procedures that complement the treatment in Chapter 2. Sec. C.1 reviews four FWER-controlling procedures beyond Bonferroni and fixed sequence testing: Holm step-down, Hochberg step-up, Šidák refinement, and Westfall–Young permutation calibration. Sec. C.2 proves the FDR control guarantee for the e-BH procedure (Theorem C.1).
C.1
Additional FWER-Controlling Procedures
This section reviews four FWER-controlling procedures that complement the Bonferroni rule (2.31) and fixed sequence testing introduced in Sec. 2.4.3. |Λ| In all cases, given a vector of p-values {pk }k=1 , the procedure returns a set K̂ ⊆ {1, . . . , |Λ|} of rejected null hypotheses, and the corresponding certified set Λ̂ = {λk : k ∈ K̂} enjoys the FWER guarantee of Theorem 2.1. Let p(1) ≤ · · · ≤ p(|Λ|) denote the sorted p-values with associated hypotheses H(1) , . . . , H(|Λ|) . Holm step-down procedure: Holm’s procedure rejects the first k ⋆ ordered hypotheses, where δ ⋆ k = max k : p(i) ≤ for all i = 1, . . . , k . (C.1) |Λ| − i + 1 Holm controls FWER at level δ under arbitrary dependence among the p134
values, and is uniformly more powerful than Bonferroni in the sense that the certified set produced by (C.1) always contains the one produced by (2.31). Hochberg step-up procedure: Hochberg’s procedure uses the same thresholds as Holm but in a step-up manner, rejecting the k ⋆ ordered hypotheses with δ ⋆ . (C.2) k = max k : p(k) ≤ |Λ| − k + 1 Hochberg is less conservative than Holm, but its FWER guarantee requires additional assumptions on the dependence structure, such as independence or positive regression dependence among the p-values. Šidák refinement: If the p-values are independent under the joint null, the Bonferroni threshold δ/|Λ| in (2.31) can be replaced by the Šidák threshold pk ≤ 1 − (1 − δ)1/|Λ| , (C.3)
which is slightly larger and hence enlarges the certified set. Analogously, the Holm thresholds in (C.1) can be refined to 1 − (1 − δ)1/(|Λ|−i+1) , yielding the Holm–Šidák procedure. The improvement over Bonferroni and Holm is modest for small δ, and should only be used when independence is defensible. Westfall–Young permutation calibration: In hyperparameter certi|Λ| fication, the p-values {pk }k=1 are typically highly dependent because they are all computed on the same calibration dataset (2.7). When the data admit a valid permutation scheme under the global null, e.g., label permutations in classification, the Westfall–Young procedure estimates the null distribution of the minimum p-value mink pk and uses it to calibrate a threshold cδ satisfying P min pk ≤ cδ ≤ δ (C.4) k
under the global null. The rejection rule pk ≤ cδ then controls FWER at level δ and can yield substantial power gains over Bonferroni and Holm when the dependence is strong, at the cost of the additional computation required to sample from the permutation distribution.
C.2
Validity of the e-BH Procedure
This section proves the FDR-control property of the e-BH procedure introduced in Sec. 2.6. The result holds under arbitrary dependence among the e-values and requires only their marginal validity. 135
Theorem C.1 (FDR control of e-BH (Wang and Ramdas, 2022)). Let e1 , . . . , e|Λ| be e-values for the null hypotheses H1 , . . . , H|Λ| satisfying the marginal validity condition E[ek | Hk ] ≤ 1,
k = 1, . . . , |Λ|.
(C.5)
Let Λ̂ ⊆ Λ denote the rejected set returned by the e-BH rule (2.64). Then, # " |Λ0 | |Λ̂ ∩ Λ0 | ≤ FDR = E δ ≤ δ, (C.6) |Λ| max{1, |Λ̂|} where Λ0 is the set of unreliable hyperparameters. Proof. Let R = |Λ̂| denote the number of rejections. By the e-BH rule (2.64), every rejected index k satisfies ek ≥ |Λ|/(R δ), which can be rewritten as δ ek I{k ∈ Λ̂} ≤ . max{1, R} |Λ| The false discovery rate can therefore be bounded as " # |Λ̂ ∩ Λ0 | FDR = E max{1, R} # " X I{k ∈ Λ̂} = E max{1, R} k∈Λ0 δ X |Λ0 | δ ≤ δ, ≤ E[ek | Hk ] ≤ |Λ| k∈Λ |Λ|
(C.7)
(C.8) (C.9) (C.10)
0
where the first inequality uses (C.7) and the second invokes the marginal validity (C.5) at each k ∈ Λ0 . Crucially, the proof does not require independence among the e-values. FDR control follows from the marginal validity condition (C.5) and from the rejection rule (2.64).
136
References Abdi, H. and L. J. Williams (2010). “Principal component analysis”. In: Wiley interdisciplinary reviews: computational statistics 2.4, pp. 433–459. Alemi, A. A. et al. (2016). “Deep variational information bottleneck”. In: arXiv preprint arXiv:1612.00410. Amodei, D. et al. (2016). “Concrete problems in AI safety”. In: arXiv preprint arXiv:1606.06565. Angelopoulos, A. N. and S. Bates (2023). “Conformal prediction: A gentle introduction”. In: Foundations and Trends in Machine Learning 16.4, pp. 494–591. Angelopoulos, A. N., J. C. Duchi, and T. Zrnic (2023a). “Ppi++: Efficient prediction-powered inference”. In: arXiv preprint arXiv:2311.01453. Angelopoulos, A. N. et al. (2023b). “Prediction-powered inference”. In: Science 382.6671, pp. 669–674. Angelopoulos, A. N. et al. (2025). “Learn then test: Calibrating predictive algorithms to achieve risk control”. In: The Annals of Applied Statistics 19.2, pp. 1641–1662. Audibert, J.-Y., R. Munos, and C. Szepesvári (2009). “Exploration– exploitation tradeoff using variance estimates in multi-armed bandits”. In: Theoretical Computer Science 410.19, pp. 1876–1902. Barocas, S. and A. D. Selbst (2016). “Big data’s disparate impact”. In: Calif. L. Rev. 104, p. 671. Belghazi, M. I. et al. (2018). “Mutual information neural estimation”. In: International conference on machine learning. PMLR, pp. 531–540. Benjamini, Y. and Y. Hochberg (1995). “Controlling the false discovery rate: a practical and powerful approach to multiple testing”. In: Journal of the Royal statistical society: series B (Methodological) 57.1, pp. 289–300.
137
Benjamini, Y. and D. Yekutieli (2001). “The control of the false discovery rate in multiple testing under dependency”. In: Annals of statistics, pp. 1165– 1188. Bennett, G. (1962). “Probability inequalities for the sum of independent random variables”. In: Journal of the American Statistical Association 57.297, pp. 33–45. Bennis, M., M. Debbah, and H. V. Poor (2018). “Ultrareliable and lowlatency wireless communication: Tail, risk, and scale”. In: Proceedings of the IEEE 106.10, pp. 1834–1853. Bergstra, J. and Y. Bengio (2012). “Random search for hyper-parameter optimization”. In: Journal of Machine Learning Research 13, pp. 281– 305. Bernstein, S. (1924). “On a modification of Chebyshev’s inequality and of the error formula of Laplace”. In: Ann. Sci. Inst. Sav. Ukraine, Sect. Math 1.4, pp. 38–49. Bommasani, R. (2021). “On the opportunities and risks of foundation models”. In: arXiv preprint arXiv:2108.07258. Bonferroni, C. (1936). “Teoria statistica delle classi e calcolo delle probabilita”. In: Pubblicazioni del R istituto superiore di scienze economiche e commericiali di firenze 8, pp. 3–62. Boucheron, S., G. Lugosi, and O. Bousquet (2003). “Concentration inequalities”. In: Summer school on machine learning. Springer, pp. 208–240. Boucheron, S., G. Lugosi, and P. Massart (Feb. 2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press. isbn: 9780199535255. doi: 10.1093/acprof:oso/9780199535255.001. 0001. url: https://doi.org/10.1093/acprof:oso/9780199535255. 001.0001. Cardwell, N., S. Savage, and T. Anderson (2000). “Modeling TCP latency”. In: Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No. 00CH37064). Vol. 3. IEEE, pp. 1742–1751. Chakraborty, A., J. Lee, and E. Katsevich (2026). “Comparing three learnthen-test paradigms in a multivariate normal means problem”. In: arXiv preprint arXiv:2601.07764. Chernoff, H. (1952). “A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations”. In: The Annals of Mathematical Statistics, pp. 493–507. 138
Clopper, C. J. and E. S. Pearson (1934). “The use of confidence or fiducial limits illustrated in the case of the binomial”. In: Biometrika 26.4, pp. 404– 413. Covington, P., J. Adams, and E. Sargin (2016). “Deep neural networks for youtube recommendations”. In: Proceedings of the 10th ACM conference on recommender systems, pp. 191–198. Dean, J. and L. A. Barroso (2013). “The tail at scale”. In: Communications of the ACM 56.2, pp. 74–80. Deb, K. (2011). “Multi-objective optimisation using evolutionary algorithms: an introduction”. In: Multi-objective evolutionary optimisation for product design and manufacturing. Springer, pp. 3–34. Einbinder, B.-S., L. Ringel, and Y. Romano (2025). “Semi-supervised risk control via prediction-powered inference”. In: IEEE Transactions on Pattern Analysis and Machine Intelligence. Farzaneh, A., S. Park, and O. Simeone (2024). “Quantile learn-then-test: Quantile-based risk control for hyperparameter optimization”. In: IEEE Signal Processing Letters 31, pp. 3044–3048. Farzaneh, A. and O. Simeone (2025a). “Multi-Objective Hyperparameter Selection via Hypothesis Testing on Reliability Graphs”. In: The Thirtyninth Annual Conference on Neural Information Processing Systems. url: https://openreview.net/forum?id=BiEwLgytGu. Farzaneh, A. and O. Simeone (2025b). “Statistically valid information bottleneck via multiple hypothesis testing”. In: 2025 IEEE International Symposium on Information Theory (ISIT). IEEE, pp. 1–5. Franceschi, L. et al. (2018). “Bilevel programming for hyperparameter optimization and meta-learning”. In: International conference on machine learning. PMLR, pp. 1568–1577. Franceschi, L. et al. (2025). “Hyperparameter Optimization in Machine Learning”. In: Foundations and Trends in Machine Learning 18.6. arXiv:2410.22854, pp. 1054–1201. Freund, Y. and R. E. Schapire (1997). “A decision-theoretic generalization of on-line learning and an application to boosting”. In: Journal of computer and system sciences 55.1, pp. 119–139. Friedman, J. H., T. Hastie, and R. Tibshirani (2010). “Regularization paths for generalized linear models via coordinate descent”. In: Journal of statistical software 33, pp. 1–22.
139
Garcıa, J. and F. Fernández (2015). “A comprehensive survey on safe reinforcement learning”. In: Journal of Machine Learning Research 16.1, pp. 1437–1480. Geifman, Y. and R. El-Yaniv (2017). “Selective classification for deep neural networks”. In: Advances in neural information processing systems 30. Grattafiori, A. et al. (2024). “The llama 3 herd of models”. In: arXiv preprint arXiv:2407.21783. Grünwald, P., R. de Heide, and W. M. Koolen (2020). “Safe testing”. In: 2020 Information theory and applications workshop (ITA). IEEE, pp. 1–54. Gu, J. et al. (2024). “A survey on llm-as-a-judge”. In: arXiv preprint arXiv:2411.15594. Hardt, M., E. Price, and N. Srebro (2016). “Equality of opportunity in supervised learning”. In: Advances in neural information processing systems 29. Hastie, T., R. Tibshirani, J. Friedman, et al. (2009). The elements of statistical learning. He, K. et al. (2017). “Mask r-cnn”. In: Proceedings of the IEEE international conference on computer vision, pp. 2961–2969. Ho, J., A. Jain, and P. Abbeel (2020). “Denoising diffusion probabilistic models”. In: Advances in neural information processing systems 33, pp. 6840– 6851. Ho, J. et al. (2022). “Video diffusion models”. In: Advances in neural information processing systems 35, pp. 8633–8646. Hoeffding, W. (1963). “Probability inequalities for sums of bounded random variables”. In: Journal of the American statistical association 58.301, pp. 13–30. Hoffmann, J. et al. (2022). “Training compute-optimal large language models”. In: arXiv preprint arXiv:2203.15556. Holtzman, A. et al. (2019). “The curious case of neural text degeneration”. In: arXiv preprint arXiv:1904.09751. Hosmer Jr, D. W., S. Lemeshow, and R. X. Sturdivant (2013). Applied logistic regression. John Wiley & Sons. Howard, S. R. and A. Ramdas (2022). “Sequential estimation of quantiles with applications to A/B testing and best-arm identification”. In: Bernoulli 28.3, pp. 1704–1728. Howard, S. R. et al. (2021). “Time-uniform, nonparametric, nonasymptotic confidence sequences”. In: The Annals of Statistics 49.2, pp. 1055–1080. 140
Hunter, D. R. (2004). “MM algorithms for generalized Bradley-Terry models”. In: The annals of statistics 32.1, pp. 384–406. Jaderberg, M. et al. (2017). “Population based training of neural networks”. In: arXiv preprint arXiv:1711.09846. Jamieson, K. and A. Talwalkar (2016). “Non-stochastic best arm identification and hyperparameter optimization”. In: Artificial intelligence and statistics. PMLR, pp. 240–248. Kaplan, J. et al. (2020). “Scaling laws for neural language models”. In: arXiv preprint arXiv:2001.08361. Koning, N. W. (2024). “Continuous testing: Unifying tests and e-values”. In: arXiv preprint arXiv:2409.05654. Kuo, W.-H. and W. Liao (2007). “Utility-based resource allocation in wireless networks”. In: IEEE Transactions on Wireless Communications 6.10, pp. 3600–3606. Laufer-Goldshtein, B. et al. (2023). “Efficiently Controlling Multiple Risks with Pareto Testing”. In: The Eleventh International Conference on Learning Representations. url: https://openreview.net/forum?id= cyg2YXn_BqF. Lehmann, E. L. and J. P. Romano (2005). Testing statistical hypotheses. Springer. Levine, S. et al. (2020). “Offline reinforcement learning: Tutorial, review, and perspectives on open problems”. In: arXiv preprint arXiv:2005.01643. Li, L. et al. (2018). “Hyperband: A novel bandit-based approach to hyperparameter optimization”. In: Journal of Machine Learning Research 18.185, pp. 1–52. Lindauer, M. et al. (2022). “SMAC3: A Versatile Bayesian Optimization Package for Hyperparameter Optimization”. In: Journal of Machine Learning Research 23.54, pp. 1–9. url: http : / / jmlr . org / papers / v23/21-0888.html. Maurer, A. and M. Pontil (2009). “Empirical Bernstein bounds and sample variance penalization”. In: arXiv preprint arXiv:0907.3740. Novikova, J. et al. (2017). “Why we need new evaluation metrics for NLG”. In: Proceedings of the 2017 conference on empirical methods in natural language processing, pp. 2241–2252. Paine, T. L. et al. (2020). “Hyperparameter selection for offline reinforcement learning”. In: arXiv preprint arXiv:2007.09055.
141
Park, S., M. Zecchin, and O. Simeone (2025). “Adaptive prediction-powered autoeval with reliability and efficiency guarantees”. In: arXiv preprint arXiv:2505.18659. Polese, M. et al. (2023). “Understanding O-RAN: Architecture, interfaces, algorithms, security, and research challenges”. In: IEEE Communications Surveys & Tutorials 25.2, pp. 1376–1411. Poole, B. et al. (2019). “On variational bounds of mutual information”. In: International conference on machine learning. PMLR, pp. 5171–5180. Raghu, M. et al. (2019). “Direct uncertainty prediction for medical second opinions”. In: International conference on machine learning. PMLR, pp. 5281–5290. Rajendran, B., O. Simeone, and B. Al-Hashimi (Feb. 2026). “Towards efficient and reliable artificial intelligence through neuromorphic principles”. In: Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 384.2315, p. 20240522. issn: 1364-503X. doi: 10.1098/rsta.2024.0522. eprint: https://royalsocietypublishing. org / rsta / article - pdf / doi / 10 . 1098 / rsta . 2024 . 0522 / 6117087 / rsta.2024.0522.pdf. url: https://doi.org/10.1098/rsta.2024. 0522. Ramdas, A. and R. Wang (2025). “Hypothesis testing with e-values”. In: Foundations and Trends® in Statistics 1.1-2, pp. 1–390. Ramdas, A. et al. (2019). “A sequential algorithm for false discovery rate control on directed acyclic graphs”. In: Biometrika 106.1, pp. 69–86. Ramdas, A. et al. (2023). “Game-theoretic statistics and safe anytime-valid inference”. In: Statistical Science 38.4, pp. 576–601. Ren, S. et al. (2015). “Faster r-cnn: Towards real-time object detection with region proposal networks”. In: Advances in neural information processing systems 28. Rice, J. A. and J. A. Rice (2007). Mathematical statistics and data analysis. Vol. 371. Thomson/Brooks/Cole Belmont, CA. Ritzwoller, D. M., J. P. Romano, and A. M. Shaikh (2024). “Randomization inference: Theory and applications”. In: arXiv preprint arXiv:2406.09521. Sant Ana, P. M. de and N. Marchenko (2020). “Radio access scheduling using CMA-ES for optimized QoS in wireless networks”. In: 2020 IEEE Globecom Workshops (GC Wkshps. IEEE, pp. 1–6. Saxe, A. M. et al. (2019). “On the information bottleneck theory of deep learning”. In: Journal of Statistical Mechanics: Theory and Experiment 2019.12, p. 124020. 142
Series, M. (2017). “Minimum requirements related to technical performance for IMT-2020 radio interface (s)”. In: Report 2410, pp. 2410–2017. Shafer, G. (2019). “The language of betting as a strategy for statistical and scientific communication”. In: arXiv preprint arXiv:1903.06991. Shafer, G. and V. Vovk (2019). Game-theoretic foundations for probability and finance. John Wiley & Sons. Shahriari, B. et al. (2016). “Taking the human out of the loop: A review of Bayesian optimization”. In: Proceedings of the IEEE 104.1, pp. 148–175. Shlezinger, N. et al. (2021). “Model-based machine learning for communications”. In: arXiv preprint arXiv:2101.04726. Simeone, O. (2022). Machine learning for engineers. Cambridge university press. Simeone, O. (2026). Classical and Quantum Information Theory: Uncertainty, Information, and Correlation. Cambridge, UK: Cambridge University Press. isbn: 9781009579520. doi: 10.1017/9781009579551. url: https://doi.org/10.1017/9781009579551. Simeone, O., S. Park, and M. Zecchin (2025). “Conformal calibration: Ensuring the reliability of black-box ai in wireless systems”. In: arXiv preprint arXiv:2504.09310. Simonsohn, U., L. D. Nelson, and J. P. Simmons (2014). “p-curve and effect size: Correcting for publication bias using only significant results”. In: Perspectives on psychological science 9.6, pp. 666–681. Snoek, J., H. Larochelle, and R. P. Adams (2012). “Practical Bayesian optimization of machine learning algorithms”. In: Advances in Neural Information Processing Systems. Vol. 25. Socher, R. et al. (2013). “Recursive deep models for semantic compositionality over a sentiment treebank”. In: Proceedings of the 2013 conference on empirical methods in natural language processing, pp. 1631–1642. Song, Y. et al. (2026). “Demystifying Prediction Powered Inference”. In: arXiv preprint arXiv:2601.20819. Stefani, A. G. et al. (2014). “Confidence intervals for the mutual information”. In: International Journal of Machine Intelligence and Sensory Signal Processing 1.3, pp. 201–214. Sutton, R. S. and A. G. Barto (1998). Reinforcement learning: An introduction. Vol. 1. 1. MIT press Cambridge. Tibshirani, R. (1996). “Regression shrinkage and selection via the lasso”. In: Journal of the Royal Statistical Society Series B: Statistical Methodology 58.1, pp. 267–288. 143
Tishby, N., F. C. Pereira, and W. Bialek (2000). “The information bottleneck method”. In: arXiv preprint physics/0004057. Valcarce, A. (2020). “Wireless Suite: A collection of problems in wireless telecommunications”. In: https://github.com/nokia/wireless-suite. Varshney, K. R. (2016). “Engineering safety in machine learning”. In: 2016 Information Theory and Applications Workshop (ITA). IEEE, pp. 1–5. Vaswani, A. et al. (2017). “Attention is all you need”. In: Advances in neural information processing systems 30. Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science. Vol. 47. Cambridge university press. Ville, J. (1939). Étude critique de la notion de collectif. Paris: GauthierVillars. Vovk, V. and R. Wang (2021). “E-values: Calibration, combination and applications”. In: The Annals of Statistics 49.3, pp. 1736–1754. doi: 10. 1214/20-AOS2020. url: https://doi.org/10.1214/20-AOS2020. Wang, R. and A. Ramdas (Jan. 2022). “False Discovery Rate Control with E-values”. In: Journal of the Royal Statistical Society Series B: Statistical Methodology 84.3, pp. 822–852. issn: 1369-7412. doi: 10.1111/ rssb . 12489. eprint: https://academic.oup.com/jrsssb/article-pdf/84/ 3/822/49322390/jrsssb_84_3_822.pdf. url: https://doi.org/10. 1111/rssb.12489. Waudby-Smith, I. and A. Ramdas (Feb. 2024). “Estimating means of bounded random variables by betting”. In: Journal of the Royal Statistical Society Series B: Statistical Methodology 86.1, pp. 1–27. issn: 1369-7412. doi: 10.1093/jrsssb/qkad009. eprint: https://academic.oup.com/ jrsssb/article- pdf/86/1/1/56961777/qkad009.pdf. url: https: //doi.org/10.1093/jrsssb/qkad009. Xiao, H., K. Rasul, and R. Vollgraf (2017). “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms”. In: arXiv preprint arXiv:1708.07747. Yanchenko, E., J. P. Williams, and R. Martin (2025). “Hypothesis testing for community structure in temporal networks using e-values”. In: arXiv preprint arXiv:2507.23034. Zecchin, M., S. Park, and O. Simeone (2024). “Adaptive learn-then-test: Statistically valid and efficient hyperparameter selection”. In: arXiv preprint arXiv:2409.15844.
144
Zheng, L. et al. (2023). “Judging llm-as-a-judge with mt-bench and chatbot arena”. In: Advances in neural information processing systems 36, pp. 46595–46623. Zhou, Y. et al. (2022). “Large language models are human-level prompt engineers”. In: The Eleventh International Conference on Learning Representations. Zrnic, T. and E. J. Candès (2024). “Cross-prediction-powered inference”. In: Proceedings of the National Academy of Sciences 121.15, e2322083121.
145