Efficiently Controlling Multiple Risks with Pareto Testing
Authors: Bracha Laufer-Goldshtein
Adam Fisch
Regina Barzilay
Tommi S. Jaakkola
Venue: ICLR 2023 poster (2023)
Keywords: conformal prediction
risk control
multi-objective optimization
hypothesis testing

Abstract: Machine learning applications frequently come with multiple diverse objectives and constraints that can change over time. Accordingly, trained models can be tuned with sets of hyper-parameters that affect their predictive behavior (e.g., their run-time efficiency versus error rate). As the number of constraints and hyper-parameter dimensions grow, naively selected settings may lead to sub-optimal and/or unreliable results. We develop an efficient method for calibrating models such that their predictions provably satisfy multiple explicit and simultaneous statistical guarantees (e.g., upper-bounded error rates), while also optimizing any number of additional, unconstrained objectives (e.g., total run-time cost). Building on recent results in distribution-free, finite-sample risk control for general losses, we propose Pareto Testing: a two-stage process which combines multi-objective optimization with multiple hypothesis testing. The optimization stage constructs a set of promising combinations on the Pareto frontier. We then apply statistical testing to this frontier only to identify configurations that have (a) high utility with respect to our objectives, and (b) guaranteed risk levels with respect to our constraints, with specifiably high probability. We demonstrate the effectiveness of our approach to reliably accelerate the execution of large-scale Transformer models in natural language processing (NLP) applications. In particular, we show how Pareto Testing can be used to dynamically configure multiple inter-dependent model attributes—including the number of layers computed before exiting, number of attention heads pruned, or number of text tokens considered—to simultaneously control and optimize various accuracy and cost metrics.

Published as a conference paper at ICLR 2023
EFFICIENTLY CONTROLLING MULTIPLE RISKS WITH PARETO TESTING
Bracha Laufer-Goldshtein, Adam Fisch, Regina Barzilay & Tommi Jaakkola CSAIL, MIT, (lauferb, fisch, regina, tommi J@csa i w.l.m..ie........ edu
ABSTRACT
Machine learning applications frequently come with multiple diverse objectives and constraints that can change over time. Accordingly, trained models can be tuned with sets of syyer-parameteer that affect their predictive behavior (e.g., their run-time efficiency versus error rate). As the number of constraints and hyper- parameter dimensions grow, naively selected settings may lead to sub-optimal and/or unreliable results. We develop efficient method for calibrating models such that their predictions provably satisfy multiple explicit and simultaneous statistical guarantees (e.g., upper-bounde error rates), while also optimizing any number of additional, unconstrained objectives (c.g., total run-time cost). Building on recent results in distribution-free free, inite-sample risk control for general losses, we propose Pareto Testing: two-stage process which combines multi-objective optimization with multiple hypothesis testing. The optimization stage constructs a set of promising combinations the Pareto frontier. We then apply statistical testing to this frontier only to identify configurations that have (i) high utility with respect to objectives, and (ii) guaranteed risk levels with respect to our constraints, with specifiably high probability. We demonstrate the effectiveness approach to reliably accelerate the execution of large-scale Transformer mod- els natural language processing (NLP) applications. In particular, we show how Pareto Testing can be used to dynamically configure multiple inter-dependent model attribtes-incluuinn the number of layers computed before exiting, number of attention heads pruned, number of text tokens considered simultaneously control and optimize various accuracy and cost metrics.
INTRODUCTION
Suppose you want to deploy a modern machine learning model in a real-world environment. As a practitioner, you may frequently have to weigh several performance considerations (Jin & Sendhoff, 2008; Ribeiro et al., 2020; Min et al., 2021). For example, how much computational budget you spend? What accuracy do you require? How large, if any, of discrepancy in predictive performance across different groups of end-users can you tolerate? Often models are equipped with hyper-parameter configurations that provide "knobs" for tuning different aspects of their performance, depending on how such questions are answered. As the number of parameter dimensions and objectives grow, however, choosing the right set of parameters to rigorously control model performance on test data in the intended ways can become prone to error.
To address this challenge, the recently proposed Learn Then Test (LTT) framework of Angelopoulos et al. (2021) combines any type of parameterizable predictive model with classic statistical hypothe- sis testing to provide an algorithm for selecting configurations that lead to provable distribution-fii finite-sample risk control of any user-specified objective. Nevertheless, while theoretically general, a key pair of practical challenges arises when the space of parameters to explore and constraints to satisfy are large. The first is that evaluating all possible configurations can quickly become intractable, while the second is that the statistical tests relied upon to guarantee risk control can quickly lose power and fail to identify configurations that also useful for the task hand.
In this work, we build upon the results of LTT by introducing Pareto Testing, a simple procedure that provide computationally and statistically efficient way identify valid, risk- cist-cootoolling config- urations with (specifiably) high probability, which, critically, are also useful with respect to other ob- jectives of interest. Our method consists of two stages. In the first stage, solve unconstrained,

---

Published as a conference paper at ICLR 2023
Multi- Dititd-DDmnsinalll Adaptive Transformer
Pareto Testing
Bound
Error
Configuration
Space (q,
Attention
lead
0
Manimizze
Attention
Coot
Head
Cost
Which exte!
Multi-Objecctvee Optimization
2
Pareto
Frontler
Which heads to prune?
Error
Attertion Heedd
Ordering
This
very
good
film
1
Testing
Which to prune?
Figure A demonstration of our calibration procedure applied to multi-dimensional adaptive computation in Transformer model (left). Here we have the option to drop tokens from the input, make an "early-exit" prediction after processing subset of the layers, or only compute a subset of the self-attention heads in each layer in order to do faster inference. Our calibration procedure (right) applies multi-objective optimization to identify a Pareto frontier of configurations with different performance profiles, and then applies statistical testing to efficiently identify a subset of "risk-cottrolling" configurations with high probability (e.g., bounded error rates).
multi-objective optimization problem in order to recover an approximate set of Pareto-optimal con- figurations, i.e., settings for which other configuration exists that is uniformly better in all spects. Here we can exploit standard multi-objective optimization methods to efficiently explore and filter large parameter spaces to only most promising configurations. perform rigorous sequential testing over the recovered set, which we empirically find to yield tight control of our desired risks, while also giving good performance with respect to our free objectives.'
the second stage, we
We apply our approach to adaptive computation in large-scale Transformer models (Vaswani et al., 2017) for natural language processing (NLP), see Figure While larger models generally perform better, they can also be incredibly computationally intensive to run (Bapna et al., 2020; Schwartz et al., 2020; Moosavi et al., 2021). Often, however, not every application, domain, or example re- quires the same amount of computation to achieve similar performance. As such, many techniques have been proposed for accelerating computation, including attention head pruning, token dropping, early exiting (Graves, 2016; Xin al., 2020; Hou al., 2020; Goyal et al., 2020). Still, deter- mining the extent to which to apply different modifications while still preserving good performance can be tricky. Our proposed procedure allows the user jointly configure multiple model settings subject to multiple statistical guarantees on model performance-soe -ucha as average and worst-case relative reductions in accuracy (e.g., so that the adaptive model is within 5% of the full model's accuracy), average inference cost (e.g., so that the adaptive model uses less than a certain number of FLOPS on average), or maximum abstention rates in selective prediction settings.
Contribution. The core idea and contribution of our work can be summarized quite plainly:
1. Our framework leverages statistical testing techniques via the LIT framework (Angelopoulos al., 2021) to identify valid risk-controlling hyper-parameter configurations:
2. To improve efficiency, we introduce Pareto Testing, our main contribution, as way to efficiently guide the number and order of configurations that we test when searching for valid settings;
3. We demonstrate the scalability and effectiveness of our method in managing trade-off's in multi- dimensional adaptive computation in NLP applications with large-scale Transformer models;
4. On diverse text classification tasks, we empirically achieve tight, simultaneous control of multiple risks while also improving performance on any con-contoolled objectives, relative to baselines.
If we fail find any valid configurations (which may not exist) with the right confidence, then abstain.
2

---

Published as a conference paper at ICLR 2023
2 RELATED WORK
Risk control. Our work adds to a rich history of tools for uncertainty estimation and risk control for machine learning algorithms (Vovk, 2002; Vovk et al., 2015; 2017; et al., 2020; Bates et al., 2021; Barber et al., 2021; Angelopoulos et al., 2021). Here we focus on achieving model-agnostic, distribution-free, and finite-sample performance guarantees-$imilar to the coverage guarantees given by prediction sets or regression intervals in conformal prediction (Pa- padopoulos et al., 2002: Vovk et al., 2005; Angelopoulos et al., 2022). As outlined in $1, this paper builds on the groundwork set by Angelopoulos et al. (2021), which provides a general methodology for calibrating any risk function that is controllable via some diwddimnniionll syyer-parameted con- figuration. We extend their framework to efficiently handle (relatively) higher-dimensione with multiple auxiliary objectives. Our application to confident model acceleration is also closely related to Schuster et al. (2021; 2022), though our method is designed for a much broader setting that involves (i) multiple objectives, and (ii) multiple model pruning dimensions.
Lei et al., 2013; 2018: Gupta
settings
Multi-objective optimization. Solving for multiple objectives is fundamental problem (Deb, 2001; Miettinen, 2012: Bradford et al., 2018). Typically, multi-objective problems are more difficult than single-objective problems, as single solution does not always exist due to trade-offs. Instead, there is a set of solutions that are all equally "good", which is known as the Pareto frontier (Censor, 1977; Arora, 2004). Our setting falls at the intersection of multi-objective optimization and risk-control, where we want to perform multi-objective optimization subject to statistical bounds on subset of the objectives. Our two-stage approach is able directly combine techniques in multi-objective optimization (Knowles, 2006; Lindauer et al., 2022) with those in risk control (Angelopoulos al., 2021), in order identify valid, statistically efficient solutions.
Model contiguration. We approach our multi-objective optimization problem by uncovering model configurations that deliver on the desired performance guarantees (e.g., bounded error rates), while also providing "best-effort" optimization of the auxiliary objectives (e.g.. minimal inference cost) without any re-training. This is adjacent to the field of hyper-parameter tuning and architecture search, which deals with determining appropriate model hyper-parameter values, or even designing higher-level network structures (Elsken et al., 2019). While most approaches focus on finding con- figurations that maximize predictive performance, some have also considered additional measures such as efficiency (Shah & Ghahramani, 2016; Belakaria et al., 2019; Elsken et al., 2018; Dong ct al., 2018; Zhou al., 2018; Chu et al., 2020), fairness (Schmucker al., 2020; Candelieri al., 2022), or robustness (Karl et al., 2022). Our work, however, differs by treating hyper-parameter selection as multiple-testing problem with rigorous statistical guarantees following Angelopoulos al. (2021).
Adaptive computation. Our main application is configuring adaptive model computation. Large- scale deep learning models can be accurate, but also computationally intensive run. Many efforts have been focused on improving run-time efficiency, including model distillation (Sanh et al., 2019; Jiao et al., 2020; Sun et al., 2020), dynamic architecture selection (Yu et al., 2019; Cai et al., 2020; Hou et al., 2020), carly-exiting (Teerapittayanon et al., 2016; Liu et al., 2020), token pruning (Goyal et al., 2020; Ye et al., 2021: Kim et al., 2021; Modarressi et al., 2022; Guan et al., 2022), and others. This work focuses on configurable, adaptive computation that does not require model re- re-training. Furthermore, only a few methods have proposed combining multiple pruning dimensions, such as depth and width (Hou et al., 2020), token pruning with early-exiting (He et al., 2021), and pruning model units of different granularity (Xia et al., 2022). Our multi-dimensional calibration scheme generalizes these approaches, and allows for flexible tuning in each pruning axis.
3 PROBLEM FORMULATION
Consider an input variable X E X, and an associated label Y E y, drawn from some joint distribution. Assume a predictive model of the form f: X' x A + V, where A A A₁ x x... x An, is the space of n hyper-parameters (Ai,..., ...) that configure f. The parameters of the model ʃ are then provide n additional degrees
optimized over a training set Duain. while the of freedom in influencing either (i) how the model is trained over Dusinn or (ii) how the model is used. We focus on the latter in this paper. For example, in our adaptive Transformer example, f has n = 3 pruning dimensions: the number of attention heads per layer, the truncated length of the input text sequence, and the effective network depth in terms of the selected early-exit layer. In this
3

---

Published as a conference paper at ICLR 2023
scenario, the hyper- paremmerrssterss (Λ1, )2, As) are real-valued thresholds, and determine the extent of sparsification along each axis given some "importance/confddneee" score (to be defined later).
Next, consider set of objective functions {Qi..... Qc-kk of the form Q. An)
Elg, (X, Y; AI...., Xa)] for some loss function 9,- Under our setting, we assume that the user wishes to arbitrarily bound the first c objective functions (hereby called risk functions) by fal,...,,a.) ac} E Re, while also minimizing the remaining & objective functions. We further assume that (Ai, (Ai,..., An) can be used to either increase decrease each objective Qi (not necessarily independently). although we do not assume that all values of Qi are jointly achievable.
To estimate suitable hyper-parameter values, let Drat = (X,, Yi), i 1, ,....,, m be an i.i.d. calibra- tion set that we will use to select (ÅI,..., )n). As functions of Deat, (AI,..., 2n) are also random variables, and therefore Qi(A An) is a random conditional expectation (constant given Deal)- Our goal is to select (A1...., ...) in such way that the (Q1..... Qc objectives that we wish to control are appropriately bounded with specifiably high probability as we now formally define.
Definition 3.1 ((a, 8)- controlling configuration). Let Deal = {(X,, Ym) be i.i.d. random be a set of risk functions conditioned on the choice of (A1,.... An)) For any set of risk levels {as) and tolerance å (0,1), 1), we say that (Ai,..., Xn,) is (a, 6)-risk controlling configuration, if:
variables that are used to estimate a model configuration (ay....,A)) Let (Q((2).....AA,))
P (Q.(tt...... 8n) S aa) 21 8, Vi (l, simultaneously,
where the probability in Eq. (1) is over the draw of Daal-
Many satisfactory configurations may exist for given task and constraints. Our key practical goal is to find a (a, 8--rssk controlling configuration that also best minimizes the remaining objectives, {Qc+1,-... [c++]- As such, we focus on the expected performance of Qe+s (A,,..,,),,)))) for j E An),
{1, {1....,k: }} as a relative measure of effectiveness when comparing selected configurations.
BACKGROUND
We briefly review the Learn then Test framework of Angelopoulos al. (2021), multiple hypothesis testing, and multiple objective optimization which comprise the key components of our method.
Learn then Test (LTT). The core idea of LTT is to use multiple hypothesis testing to rigorously select risk controlling configuration À = (A1,..., An) E A. Consider single risk Q. A set of possible configurations Ag chosen for testing, usually by defining discrete grid over the configu- ration space A. For each configuration À E Ag. LTT tests the null hypothesis, Hy: Q(x)= > i.e., that the risk is not controlled. A successful rejection of HA then implies that À is risk-controlling.
A valid (super-uniform) p-value to use as a basis for accepting or rejecting Hx can be derived from concentration bounds on the empirical risk. For example, Hoeffding's 's incquality can be used to yield
pal (A.a) p((=m) (A); m) = 2m (A))
(2)
so that (A, a) < u) S u, for all u E 1]. Similar p-values can be derived from different bounds. Here, we will use the more powerful A subset of valid X configurations is then selected out of Ag by applying family-wise error rate (FWER) controlling procedure, so that the probability of making one or more false discoveries (i.c., choosing invalid A) is bounded by å (0, 1). This can be extended to multiple risk control by defin- ing the combined null hypothesis, HA- 3 where (A) > a; A valid combined p- can be obtained by taking the maximum p-value over all objective functions (see Appendix A for proof):
greffding-Benttee p-value throughout (Appendix A).
paol ()ll(A, xx) = max p((,aa) (A); m), with a = (ai,..., 1si5e
Multiple hypothesis testing. A key component of LTT is the choice TWER-controllin procedure. As the number of tested hypotheses HA grows (c.g., for combinatorially many A), the harder it is to
Thiis is slight ahuse terminology in that, technically, (λ..... )n) as a random variable not necessar- ily a configuration that achieves risk control, but rather its realizations are valid with the appropriate probability. "This is analogous using the average set size to compare conformal predictors (Vovk et al., 2005; 2016).
4

---

Published as a conference paper at ICLR 2023
reject HA while limiting the probability of false discoveries to 8. Different FWER- controlling proce- dures have different statistical efficiency/power (i.e., ability to correctly reject HA when it is false). Angelopoulos et al. (2021) consider number of FWER-controllingg procedures, namely the Bonfer- roni correction, Fixed Sequence Testing (FST), and Sequential Graphical Testing (SGT)-see Ap- pendix E. for a complete discussion. At high level, the Bonferroni correction assigns an "error bud- get" of A/1 to each possible A E Ag. For large AAgl this strict tolerance can result in conservative rejections. FST and SGT attempt to exploit structure in by ordering and testing that are likely to result in more valid rejections. FST considers sequence of hypothesis tests in some order, and terminates when the first null hypothesis H fails to be rejected. The efficiency of FST relies heavily on the ordering of hypothesis tests (e.g., those that are more likely to be rejected should be tested earlier). Defining a proper ordering for FST is challenging for a large, possibly unstructured (or with unknown structure) A. This challenge intensifies when combined with the additional goal of finding configurations that not only provide multiple risk control, but also optimize Qc+1...., Qc+k-
Ag ways
Multiple objective optimization. Generally speaking, multi-objectiive optimization minimizes vector-valued function g(>)= A RT, where g(>) [Gr (A)....; (A]] consists of objec- tives G; (we use G to avoid confusion with Q for now). For nontrivial multi-objective function g(A) with conflicting objectives (e.g., accuracy vs. cost), there is no single point that minimizes all objec- tives simultancously. Instead, for any X, A' E A, we say that A' dominates À (X' < A), if for every i E (1....r) ......)).... (X) s (A), and for some i [1....r) r). Gx < G; In other words, X' dominates À if there is no objective for which X is superior to X, and for at least one objective X is strictly better. The Pareto optimal ser consists of all points that are not dominated by any point in A:
Apor
{xEA: EX X
X, X + } = 0}.
5 PARETO TESTING
We now present our method for selecting effective risk-controlling configurations. We adopt the strategy of Split FST (Angelopoulos et al., 2021) for separating the calibration data into two disjoint subsets Dopt and Dresting of sizes m, and my, respectively. The first split is used for defining an ordered sequence of configurations test, while the second is used to conduct the hypothesis tests.
5.1 CONSTRUCTING THE PARETO FRONTIER
We begin with defining a set of tests/configurations to consider. We solve the multi-objective optimization problem defined by the vector-valued function q(A) A Igc that consists of all of the objective functions (both constrained and unconstrained), i.c. q(A) = [Qi(A)..... Qc+ (A))². Practically, we use (A) with empirical objectives (A) defined over Dopt- Any efficient solver for multi-objective optimization can be used to approximate the Pareto optimal set Aper We will show results with both brute-force optimization over a grid of configurations, as well as with a multi-objective Bayesian optimizer (Lindauer et al., 2022).
The main idea of our method is to perform testing only over the Pareto optimal set. This consists of the most "promising" configurations, and provides the best achievable trade-off's between all ob- jectives (with respect to D.p)). As mentioned earlier, a major challenge when dealing with a large hyper-parane paramm-r space is that testing numerous configurations can quickly lead to a loss in statistical efficiency. We overcome this by focusing only on the "optimal" regiio of the hyper-paramett space.
5.2 ORDERING THE PARETO FRONTIER
We now define an ordering for the set of tests/configurations on the Pareto frontier along which to conduct FST. We take the simple, but empirically effective, strategy of ordering À E Apur by their mi). which we compute over Dopt (the same data used to recover the Pareto frontier, but separate from testing data). Con- verting the e constrained dimensions to p-values and taking their maximum, allows us to align and compare risks of different types (c.g., binary 0/1 eттоr vs. precision/recall rates in [0, ID, or that are controlled by different bounds (e.g., 0; & az)). Intuitively, because we focus on the Pareto optimal set, for each configuration along this ordering there is no other configuration with lower estimated p-value that is also expected be dominant on the k free objectives. Note that for > 1, we can
(combined) estimated p-values y0 a)) maxigise p(Q. ((Q; (A);
5

---

Published as a conference paper at ICLR 2023
Algorithm Pareto Testing
Definitions: f is configurable model with thresholds À (Az...., An)) Deal Dopt U Dresting is calibration set of size m. split into optimization and (statistical) testing sets of my and my, respectively. (Q....., Q y are objective functions. a = {(i,... "oi,...,ae" are user-specified risk bounds for the first c ob- jectives. A is the configuration space. is the tolerance. PARETOOPTIMAL returns the Pareto frontier, and can either he computed via a multi-objective optimization algorithm exhaustive search (see Algorithm F.1).
1: function OPTIMIZATION( A, ox)
2: Apur S P-PPRTTOOPTIALSSTTTC @T
D. (A, &- mix p( (A); m1). for all E Ape
4: Aodered <- Order configurations according to increasing p a))
5: return Aordered
6:
function CALUBRATION Diesiigg Aorderdd 8)
7:
(A) - (xxr Desing (x Y; A), for all À E Aocdrea, and sisc
8: D
Jesting (x, f- maxi Q (A); a, m2). for all X Andeaa
Apply FST: A. (X6) :j J}, J= min {j j:: gening (A a)),a)) 2
10:
A' PARETOOPTIMALSET(A. Qutiie (
11: return A
(optionally) prune the frontier by considering only the subset Afur S Apar that is optimal with respect to q [X, ox) (A, ax), Q (A). (A)..... Qoee (A)]". In other words, since we only care about the maximum p-value over the constrained objectives, can ignore configurations in A Apar that only dif-
fer along the constrained dimensions, without affecting the free dimensions or the combined p-value.
5.3 APPLYING FIXED SEQUENTIAL TESTING ON THE PARETO FRONTIER
After defining and ordering Apar over Dapt. then pro- ceed with FST over Dresting to identify a subset A, S Apar of configurations for which ject HA (i.e., that are valid risk-controlling configura- tions). Finally, after obtaining the validated subset Ay. we again find and return the resulting Pareto frontier (now, with respect to only the objectives of practical interest: [Qct1..... Qa+k D. For &- = 1, this consists of single configuration A while for k > 1, this consists of set of non-dominated, valid configurations A*.
successfully re-
Algorithm and is illustrated in Figure 2. We call it Pureto Testing for two reasons: (i) the method reduces to applying FST over a path defined by the Pareto front of the multi-objective problem, and (ii) repeated testing for different a limita- tions yields calibrated Pareto frontier with constraints on specific dimensions in the objective function space. It is straightforward show that Pareto Testing achieves valid risk control, as we now formally state.
Our method summarized
Q. Figure 2: Pareto Testing with two objectives. Q1 is controlled at a while Q2 is minimized. FST is applied along the sequence of configurations on the Pareto front, ordered from low to high expected risk w.r.t. Q1.
Proposition 5.1. Lei Deal = [(X,, Ye be a set i.i.d random variables split into two disjoint subsets, Dopt and D Dresting- Let p poosting (X,x) 3) be a valid p-value for configuration X. where F(ptesting( (x, a)) I u) S u for all u E [0, over the draw of Dreating. Then all configurations in the output set A of Algorithm I are also simultaneously (a, -)-risk controlling configurations.
The proof, given in Appendix A, follows from Split FST. Note that for 1, the chosen set A* con- tains configurations that are simultaneously valid. We are therefore free to use any X; E A", as well as any randomly combined configuration in the convex hull of A defined follows. Consider a ran- domized strategy, where for each test point, we sample the configuration X; E " to use with prob- ability Ay. where A lies in the A 1 dimensional probability simplex. The resulting combination also (a, 8)riskk controlling, and allows for different (average) outcomes on the & free objectives.
Corollary 5.2. Any randomized thme-shared use of configurations in A (a, 0)-iskk controlling.

---

Published as a conference paper at ICLR 2023
6 ADAPTIVE MULTI-DIMENSIONAL PRUNING
We now turn to a concrete application of our method, which we demonstrate its effectiveness for reliably accelerating Transformer models (Vaswani et al., 2017). Here we pair each pruning "dimension" " with a score function that estimates the relative importance of each prunable element in that dimension. By thresholding scores, obtain different versions of the model with different performance. We assume a K Kllayer Transformer model with W attention heads per layer, and L(X) input tokens (see Vaswani et al. (2017) for complete description of the Transformer model).
6.1 CONFIGUR ABLE DIMENSIONS
We consider the following adaptive behaviors (see also Appendix for details):
1. Token pruning. We assign each token with an (after- fact) importance score, based on the gradient of the output probability w.r.t. the token embedding. determine token importance at run-time, we predict the score at each layer (Modarressi et al., 2022), then remove tokens with estimated scores bellow a threshold \lok, yielding a sequence of size (X; Aluk) at the j-th layer.
2. Early exiting. We attach a softmax classifier head to each layer, and exit whenever the predictive entropy of its output below threshold Xlayer, The exit layer is denoted as Kexi(X; (X; Xlayer).
Head pruning. Similar to token pruning, we compute an importance score for each attention head per layer by the gradient of the loss over the validation set (from training) w.r.t the head hidden representation, following Michel et al. (2019). W, (A denotes the number of retained heads in layer j. Note that this is fixed for all inputs, unlike the previous mechanisms.
6.2 OBJECTIVE FUNCTIONS
We also define several practical objective functions. f(; Xo) denotes the full model without pruning- Relative computational cost. We define the relative computations cost by the ratio between the computational cost of the pruned model and the computational cost of the full model:
E
Kan(X:A b9r))
W5(Aben)) L, (X;; A
Q ()) E
(5)
Σj=1 W. I((X)2
Eq. (5) reflects simplistic definition that incorporates quadratic dependency the sequence length due to the attention mechanism, and a linear dependency on the number of attention heads. We also consider total FLOPs (floating-poin) operations) per forward pass.
Relative accuracy reduction. Speeding up the run-time of a model can also degrade its accuracy. Define the random variable D(X, ;; A) (X((;
Y} 1{ Y), which is when both model predictions are the same, 1 when the full model is correct while the pruned model incorrect, and -1 the opposite true. We define the relative accuracy reduction as:
Quee (A) TE [D(X, Y; A) = [E
Y} E [1([(x; =Y],,
(6)
i.e, the difference in accuracy between the full and pruned models. In order to exploit p-values derived from confidence bounds that assume the risk is in [0, 1] (Angelopoulos et al., 2021), we define (X, Y; X) [D(X, Y; X)] which differs only for the rare event that the pruned model is correct while the full model is not, and is more restrictive since E [D(X, Y; A)] E [D'(X, Y; A)].
Worst-class relative accuracy reduction. In some cases, we would like to control the worst-class accuracy, or equivalently, that every class accuracy reduction is controlled by the same level:
Quce-class (y:: A) = E (D'(X,Y; Y = y] < a, Vy E y
(7)
Note that this adds an additional | objectives (that can still be solved efficiently, see Appendix A).
Selective classification abstention rate. Consider selective classification problem, where the model allowed to abstain from making a prediction when it is unsure, based on some threshold r on the model's confidence (we the probability of the predicted class max, f(X, y; A)). In this case, we re-define the relative accuracy and cost reductions to be conditioned on making a prediction. We also introduce abstention rate objective (e.g., abstain from prediction at most 20% of the time):
absttention rake (A, E 1 max /(X,y: < 7//-
(
y
7

---

Published as a conference paper at ICLR 2023
122
Mathod
2:23
0.21
Meched
Method
30 SCT
30 SGT
SGT
Sundo brileg
Parta
Faesto
2.33
2.22
0.10
0.10
Method 20
Nethod
Hethed
Verred
521
30
DANDLA C24
Hnorts mnding
IST
0.05
8:38
0.15
322
0.0
8:38
0.15
0.20
0.08
3.50
0.32
0.20
6:55
0.10
6:33
0.20
(a) IMDB
(b) AG News
(c) QNLI
(d) QQP
Figure 3: Two objectives (100 random splits). Relative accuracy reduction is controlled, while com- putational cost is minimized. Top plots show accuracy differences; bottom plots show relative cost.
7 EXPERIMENTS
Experimental setup. we test our method over five text classification tasks of varied difficulty levels: IMDB (Maas al., 2011), 1), AG News (Zhang al., 2015). QNLI (Rajpurkar et al., 2016), QQP, MNLI (Williams et al., 8). We use a BERT-base model (Devlin et al., 2018) with K = 12 layers and W 12 heads per layer, and attach prediction head and token importance predictor per layer.
Baselines and Evaluation. We present both risk controlling and contrisk- baselines. Non-risk-controlling baselines: (I) a-constrained, the solution the constrained optimization problem Eq. (21); (2) (a, o)coonstrai the same as before, but with constraints defined over p-values, which is equivalent to testing without FWER control. Rist-controlling baselines: (3) 3D SGT, SGT defined over a 3D graph, see Algorithm F.3; (4) Split FST, the split method proposed in Angelopoulos al. (2021), where set of hypotheses ordered by increasing estimated p-values. For fairness, each baseline (including our method) operates over the same predefined grid of config- urations. We use 6480 configurations in total (18 head, 20 token, and 18 early-exit thresholds). Note that the recovered Pareto front in this case is restricted to points in this grid, see Algorithm F.1. We also show the results obtained while using a multi-ohjective optimizer to demonstrate the actual com- putationally efficient implementation of our method (rather than brute-force exploration of the grid). We repeat each experiment over different splits of calibration and test data (50-100 runs total), and report the mean over all splits (with 95% CIs) for the configurations selected by each method.
Two objectives (one controlled, one free). We start with a two-objective scenario, where we wish to control the accuracy reduction (Eq. (6)), while minimizing the cost (Eq. (5)). The average accuracy reduction and relative cost are presented in Fig. 3 for the risk controlling baselines. We observe that the proposed method obtains the lowest cost among the risk controlling baselines for all a values and across all tasks. In particular, it can be seen that Split FST obtains slightly looser control of relative accuracy reduction, but higher relative computational costs compared to Pareto Testing, Ordering by p-values alone does not take into account scenarios where several configurations have similar accuracy, but vary in costs, while the proposed method optimizes the selection and ordering of configurations in both dimensions. We also see that 3D-SGT performs well for low a values, but often becomes worse as increases. A possible factor is that as a increases, 3D testing is allowed to explore more of the 3D graph, but does so inefficiently-llediing to overall lower rejection rates. Figure shows the difference between the risk controlling and the non-risk-controlle baselines in terms of satisfying Definition 3.1. In non-risk controlling baselines (left), the risk exceeds a more frequently than the allowed tolerance level 8 = 0. By contrast and as expected, see that all the risk controlling baselines (right) are always below the tolerance level.
Three objectives (two controlled, one free). We study a scenario with three objectives on MNLI, where we control both the average accuracy (Eq. (6)) and the clrst-class accuracy (Eq. (7)) while minimizing cost (Eq. (5)). We vary the values of a for average accuracy and set a2 = 0.15 for worst accuracy. Figure 5 reports the results of the three objective functions. It can be seen that when
8

---

Published as a conference paper at ICLR 2023
Nethod e-constrained (o. 0i-ccmmttrinedd Pleter lestin
0.4
Aucuracy Officeenc
d-constra
0.15
Pa Testing
Villttio
(9.
(o.p)-ocratr
0.4
Dengto
Solit
0.3
500 Testing
6.5
6.3
0.59
0.05
0.55
0.05
0.1
0.15
0.025
0.05
0.075
0.1 0.125 0.15 0.15 02
Accuracy Differunce
Figure 4: Two-objectives, QNLI (100 splits), Acc. reduction is controlled, cost is minimized. Left: histogram of acc. reduction, 0.05; middle: violin plots of acc, reduction; right: risk violations.
degoral
Worst Accuracy Dirteeece
0.55
Method
Accuracy Dfferencee
Method
0.50
3D SGT
0.15
3D SGT
Solit
0.12
0.43
Split FST
lesting
Pareto Testing
0.10
Belafien
0.40
0.10
0.08
Method
0.35
0.30
0.05
Split
0.04
Pareto Tealing
0.05
0.10
0.15
0.20
0.05
0.10
0.15
0.20
0.09
0.30
0.35
0.20
Figure 5: Three- cbjec-objectives. MNLI (100 random splits): average accuracy controlled by ai (0.025, 0.5..... 0.2),, worst accuracy is controlled by dg = 0.15, 5 = 0.1, and cost is minimized.
01 is small, testing is dominated by average accuracy (worst accuracy is not tight), and as 0₁ in- creases, worst accuracy becomes dominant and average accuracy becomes loosely controlled. Here too we see that Pareto Testing obtains improved cost reduction with respect the other baselines.
Results with an off-the-shelf optimizer. On the first scenario with accuracy control and cost minimization, in Figure D.I we show comparison between the proposed method with grid (blue) and multi-objective optimizer (red to yellow) with different number function evaluations. For multi-objective optimizer, used implementation (Lindauer et al., 2022) of ParEGO optimiza- tion algorithm (Knowles, 2006; Cristescu & Knowles, 2015). We observe that even with a small number of evaluations (e.g., 50), we obtain reasonable results, which further improve as the number of evaluations increases. The grid option performs better for certain a values, but it requires signifi- cantly more function evaluations. more in depth analysis of how the multi-objective optimization method and the allowed number of evaluations influence testing efficiency is left for future work.
Additional results. We briefly highlight a number of results contained in Appendix D. On the same "accuracy control" setting, we report FLOPs saved, as an alternative measure for cost improvement. In addition, we show flipped results for controlling cost while minimizing the relative loss in aceu- racy. We also explore a selective prediction setting with three objectives when one is controlled while two are free. Specifically, we control the selective accuracy loss (Eq. (17)), while minimizing both the selective cost (Eq. (16)) and the abstention rate (Eq. (8)). Figure D.2 reports the cost and absten- tion rate for the chosen configurations by either the proposed method and Split FST. It can be seen that Pareto Testing selects richer set of configurations that conveys better cost-coverage trade-offs.
8 CONCLUSION
Deployment of machine learning models in the real world can frequently demand precise guarantees that certain constraints will be satisfied, together with good empirical performance on other objec- tives of interest. In this work, we presented Pareto Testing, two-stage procedure for multiple risk control combined with multi-objective optimization. the first stage, Pareto Testing relaxes all con- straints, and converts the problem to standard multi-objective optimization format that can be effi- ciently solved with off-the-shelf optimizers to yield Pareto frontier of ppper-paramtter configura- tions affecting model performance. In the second stage, this Pareto frontier is filtered via multiple hy- pothesis testing to identify configurations that simultaneously satisfy the desired risk constraints with (specifiably) high probability-wi while also being effective solutions for the free objectives. Bridging theory and practice, we demonstrated the effectiveness our method for reliable and efficient adap- tive computation of Transformer models several text classification tasks under various conditions.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank the anonymous reviewers and members of the Barzilay and Jaakkola research groups for helpful discussions and feedback. B.L.G. is supported in part by the CHE Data Science fellowship, the Zuckerman- CHE STEM Leadership Program, the Schmidt Futures Israeli Women's 's Postdoc- toral Award and the Technion Viterbi Fellowship. A.F. is supported in part by the NSF Graduate Research Fellowship. This work also supported in part by the MI. for Pharmaceutical Discovery and Synthesis (MLPDS) Consortium and the DARPA Accelerated Molecular Discovery program.
REFERENCES
Anastasios N Angelopoulos, Stephen Bates, Emmanuel J Candès, Michael Jordan, and Lihua Lei. Learn then test: Calibrating predictive algorithms to achieve risk control. arXiv preprint arXiv:211000100 2021.
Anastasios Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control. arXiv preprint arXiv:2208.022 02811, 2022.
Jasbir Arora. Introduction to optimum design. Elsevier, 2004.
Ankur Bapna, Naveen Arivazhagan, and Orhan Firat. Controlling computation versus quality for neural sequence models. 2020. doi: 10.4550AAKK12200207116.. URL https: arxiv. org/abs. 2002. 07106.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, +9(1))486-500) 2021.
Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution-free,, risk-controlling prediction sets. Journal of the ACM (JACM), 68(6) 2021.
Syrine Belakaria, Aryan Deshwal, and Janardhan Rao Doppa. Max-value entropy search for multi- objective bayesian optimization. Advances in Neural Information Processing Systems, 32, 2019.
Carlo Bonferroni. Teoria statistica delle classi e calcolo delle probabilita. Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commericiali di Firenze, 8:3-62, 1936.
Eric Bradford, Artur M Schweidtmann, and Alexei Lapkin. Efficient multiobjective optimization employing gaussian processes, spectral sampling and genetic algorithm. Journal of global optimization, 71 71(2):407-438 2018.
Frank Bretz, Willi Maurer, Werner Brannath, and Martin Posch. A graphical approach to sequen- tially rejective multiple test procedures. Statistics in medicine, 28(4):586-66) 908866604,55 2009.
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once for all: Train one network and specialize it for efficient deployment. In International Conference on Learning Representations, 2020.
Antonio Candelieri, Andrea Ponti, and Francesco Archetti. Fair and green hyperparameter optimiza- tion via multi-objective and multiple information source bayesian optimization. arXiv preprint arXiv:2205.08835, 2022.
Yair Censor. Pareto optimality in multiobjective problems. Applied Mathematics and Optinization, 4(1):41-59, 1977.
Xiangxiang Chu, Bo Zhang, and Ruijun Xu. Multi-objective reinforced evolution in mobile neural architecture search. In European Conference Computer Vision, pp. 99-113. Springer, 2020.
Cristina Cristeseu and Joshua Knowles. Surrogate- based multiobjective optimization: Parego update and test. In Workshop Computational Intelligence (UKCI), volume 770, 2015.
Kalyanmoy Deb. Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons, 2001.
10

---

Published as a conference paper at ICLR 2023
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 040004 2018.
Jin-Dong Dong, An-Chieh Cheng, Da-Cheng Juan, Wei Wei, and Min Sun. Dpp-net: Device- aware progressive search for pareto-optimal neural architectures. In Pruceedings of the European Conference on Computer Vision (ECCV), pp. 517-531, 2018.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Efficient multi-objective neural architecture search via lamarckian evolution. arXiv preprint orXiv:/804.0908/ 2018.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, 20(1):1997-200 2017 2019.
Saurabh Goyal, Anamitra Roy Choudhury, Saurabh Raje, Venkatesan Chakaravarthy, Yogish Sab- harwal, and Ashish Verma. Power-bert: Accelerating bert inference via progressive word-vector elimination. In International Conference Machine Learning, pp. 3690-3699. PMLR, 2020.
Alex Graves. Adaptive computation time for recurrent neural networks. 2016.
Yue Guan, Zhengyi Li, Jingwen Leng, Zhouhan Lin, and Minyi Guo. Transkimmer; Transformer learns to layer-wise skim. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pp. 7275-727775 2022.
Chirag Gupta, Aleksandr Podkopaev, and Aaditya Ramdas. Distribution-fres free binary classification: prediction sets, confidence intervals and calibration. In Advances in Neural Information Process- ing Systems (NeurIPS), 2020.
Xuanli He, Iman Keivanloo, Yi Xu. Xiang He, Belinda Zeng, Santosh Rajagopalan, and Trishul Chilimbi. Magic pyramid: Accelerating inference with early exiting and token pruning. arXiv preprint (xXi:2211.0022: 2021.
Sture Holm. A simple sequentially rejective multiple test procedure. Scandinavian journal statis- tics, pp. 65-70, 1979.
Lu Hou, Zhiqi Huang, Lifeng Shang. Xin Jiang. Xiao Chen, and Qun Liu. Dynabert: Dynamic bert with adaptive width and depth. Advances in Neural Information Processing Systems, 33: 9782-9793, 2020.
Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. Tinybert: Distilling bert for natural language understanding. Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 4163-4174, 2020.
Yaochu Jin and Bernhard Sendhoff. Pareto-based multiobjective machine learning: An overview and case studies. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applicattons and Reviews), 38(3):397-4155 2008
Florian Karl, Tobias Pielok, Julia Mooshauer, Florian Pfisterer, Stefan Coors, Martin Binder, Lennart Schneider, Janek Thomas, Jakob Richter, Michel Lang, al. Multi-objective hyperparameter optimization-an overview. arXiv preprint arXiv:2206.074: 2022.
Schoon Kim, Sheng Shen, David Thorsley, Amir Gholami, Woosuk Kwon, Joseph Hassoun, and
Kurt Keutzer. Learned token pruming for transformers. arXiv preprint wxXiv:2107.00910 2021.
Joshua Knowles. Parego: A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Transactions on Evolutionary Computation, 10(1): 50-66, 2006.
Jing Lei, James Robins, and Larry Wasserman. Distribution-fres prediction sets. Journal of the American Statistical Association, 108(501):278-287 2013.
Jing Lei, Max Gelll, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 1523):1094-1111, 2018.
11

---

Published as a conference paper at ICLR 2023
Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp. Difan Deng, Car- olin Benjamins, Tim Ruhkopf, René Sass, and Frank Hutter. Smac3: A versatile bayesian opti- mization package for hyperparameter optimization. J. Mach. Learn. Res., 23:54-1, 2022.
Weijie Liu, Peng Zhou, Zhe Zhao, Zhiruo Wang. Haotang Deng, and Qi Ju. Fastbert: a self-distilling bert with adaptive inference time. arXiv preprint arXiv:2004.02178 2020.
Andrew Maas, Raymond Daly, Peter Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pp. 142-150, 2011.
Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one? Advances in neural information processing systems, 32, 2019.
Kaisa Miettinen. Nonlinear multiobjectiive optimization, volume 12. Springer Science & Business Media, 2012.
Sewon Min, Jordan Boyd-Graber, Chris Alberti, Danqi Chen, Eunsol Choi, Michael Collins, Kelvin Guu, Hannaneh Hajishirzi, Kenton Lee, Jennimaria Palomaki, Colin Raffel, Adam Roberts, Tom Kwiatkowski, Patrick Lewis. Yuxiang Wu, Heinrich Küttler, Linqing Liu, Pasquale Minervini, Pontus Stenetorp. Sebastian Riedel, Sohee Yang. Minjoon Seo, Gautier Izacard, Fabio Petroni, Lucas Hosseini, Nicola De Cao, Edouard Grave, Ikuya Yamada, Sonse Shimaoka, Masatoshi Suzuki, Shumpei Miyawaki, Shun Sato, Ryo Takahashi, Jun Suzuki, Martin Fajcik, Martin Do- cekal, Karel Ondrej. Pavel Smiz, Hao Cheng, Yelong Shen, Xiaodong Liu, Pengcheng He, Weizhu Chen, Jianfeng Gao, Barlas Oguz, Xilun Chen, Vladimir Karpukhin, Stan Peshterliev, Dmytro Okhonko, Michael Schlichtkrull, Sonal Gupta, Yashar Mehdad, and Wen-tau Yih. Neurips 2020 efficientqa competition: Systems, analyses and lessons learned. In Proceedings of the NeurlPS 2020 Competition and Demonstration Track, 2021.
Ali Modarressi, Hosein Mohebbi, and Mohammad Taher Pilehvar. Adapler: Speeding up inference by adaptive length reduction. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1-15, 2022.
Nafise Sadat Moosavi, Iryna Gurevych, Angela Fan, Thomas Wolf, Yufang Hou, Ana Marasović. and Sujith Ravi (eds.). Proceedings of the Second Workshop on Simple and Efficient Natural Language Processing, 2021.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning, pp. 345-356. Springer, 2002.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions for machine comprehension of text. arXiv preprint arXiv: 1606. 1606.0520, 2016
Marco Tulio Ribeiro, Tongshuang Wu, Carlos Guestrin, and Sameer Singh. Beyond accuracy: Be- havioral testing of NLP models with CheckList. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (ACL), 2020.
Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generaliza- tion. arXiv preprint arXiv: 19I.::9911.01 1.08331, 2019.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv: 1910.01 2019.
Robin Schmucker, Michele Donini, Valerio Perrone, Muhammad Bilal Zafar, and Cédric Archam- beau. Multi-objective multi-fidelity hyperparameter optimization with application fairness. In NewrlPS Workshop on Meta-Learning, volume 2, 2020.
Tal Schuster, Adam Fisch, Tommi Jaakkola, and Regina Barzilay. Consistent accelerated inference via confident adaptive transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 196224977) 2021.
12

---

Published as a conference paper at ICLR 2023
Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghani, Dara Bahri, Vinh Q Tran. Yi Tay, and Donald Metzler. Confident adaptive language modeling. arXiv preprint arXiv:2207.0706. 2022.
Roy Schwartz, Jesse Dodge, Noah A. Smith, and Oren Etzioni. Green ai. Communications of the ACM, 63(12), 2020.
Amar Shah and Zoubin Ghahramani. Pareto frontier learning with expensive correlated objectives. In International conference on machine learning, pp. 1919-1927. PMLR, 2016.
Zhiqing Sun, Hongkun Yu, Xiaodan Song, Renjie Liu, Yiming Yang, and Denny Zhou. Mobilebert: compact task-agnostic bert for resource-limited devices. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 2158-118220 2170, 2020.
Surat Teerapittayanon, Bradley McDanel, and Hsiang-Tsuue Kung. Branchyner: Fast inference via early exiting from deep neural networks. In 2016 23rd International Conference Pattern Recognition (ICPR), pp. 2464-2469, IEEE, 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- tion processing systems, 30, 2017.
Vladimir Vovk. On-line confidence machines are well-calibrated. In The 43rd Annual IEEE Sym- posium Foundations of Computer Science., 2002.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer Science & Business Media, 2005.
Vladimir Vovk, Ivan Petej, and Valentina Fedorova. Large-scale probabilistic predictors with and without guarantees of validity. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
Vladimir Vovk, Valentina Fedorova, Ilia Nouretdinov, and Alexander Gammerman. Criteria of efficiency for conformal prediction. In International Symposium on Conformal and Probabilistic Prediction with Applications Volume 9653, 2016
Vladimir Vovk, Jieli Shen, Valery Manokhin, and Min-ge Xic. Nonparametric predictive distribu- tions based on conformal prediction. In Proceedings of the Sixth Workshop on Conformal and Probabilistic Prediction and Applications, 2017.
Adina Williams, Nikita Nangia, and Samuel R Bowman. A broad-coverage challenge corpus for sentence understanding through inference. In 2018 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, NAACL HLT 2018, pp. 1112-1122. Association for Computational Linguistics (ACL), 2018.
Maciej Wolezyk, Bartosz Wójcik, Klaudia Batazy, Igor Podolak, Jacek Tabor, Marek Šmieja, and Tomasz Trzcinski. Zero time waste: Recycling predictions in early exit neural networks. Advances in Neural Information Processing Systems, 34:2516 2528, 2021.
Mengzhou Xia, Zexuan Zhong, and Danqi Chen. Structured pruning learns compact and accurate models. arXiv preprint arXh::2204.00400 2022.
Ji Xin, Raphael Tang, Jaejun Lee, Yaoliang Yu, and Jimmy Lin. DeeBERT: Dynamic early exiting for accelerating BERT inference. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (ACL), 2020.
Deming Ye, Yankai Lin, Yufei Huang, and Maosong Sun. Tr-bert: Dynamic token reduction for accelerating bert inference. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 5798- 5809, 2021.
Jiahui Yu, Linjie Yang, Ning Xu, Jianchao Yang, and Thomas Huang. Slimmable neural networks. In International Conference on Learning Representations, 2019.
13

---

Published as a conference paper at ICLR 2023
Xiang Zhang. Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas-
sification. Advances in neural information processing systems, 28, 2015.
Yanqi Zhou, Siavash Ebrahimi, Sercan Ô Ark, Haonan Yu, Hairong Liu, and Greg Diamos. Resource-efficient neural architect. arXiv preprint arXiv:/806.079111 2018.
A MATHEMATICAL DETAILS
We present the proofs for our thcoretical claims.
A. MAX P-VALUE FOR MULTIPLE RISKS
First we re-state and re- re-prove that taking the maximum p-value is also a valid p-value.
Lemma A.1. Let p:(A,00 ox) be p-value for Hxs Qi(A) > as for each i E (l....,c). Define
pl X, o)) maxigise P()), Then, for all X such that Hx 3i where Q;(A) > holds, have:
P
(9)
Proof. Let S (I....,cc be the set of all true null hypotheses at A. We have:
F(p(A, s S I
max Pi (A, a S
EET
(10)
n
=P
Pi (A, ai) su
max P (p(A, a:) S s.).
NET
VET
Since for each i E I, (,, an) u) S have maxier (p(A, as) u S u. which implies
P (p(A, S u) S u.
A.2 PROOF OF PROPOSITION 5.1
This is direct result of Split FST (Angelopoulos et al., 2021), which we prove here for completeness.
Proof. Since D and D Dresting are disjoint, i.i.d., D Dresting is also i..d. w.r.t the returned Pareto frontier over Dopt. Lemma A.1 then gives that pesttnng (X, a are super-uniform under Hx-
We now prove simultaneous (a, -oontrlll over A,. Let Hx be the first true null hypothesis in the sequence. Given that p(X, a) is a super uniform p- p-value under Hx, the probability of making false discovery X bounded by 5. However, if Hx fails to rejected (no false discovery), then all other Hx that follow in the sequence also fail to be rejected (regardless of if H is true or not). So the probability of making any false discoveries is also bounded by 5.
This implies that the probability that all configurations in A C A, are risk controlling is at least 1 8, which also implies that any configuration A is (ax, 8)-risk controlling.
A.3 PROOF OF PROPOSITION 5.2
Proof. We restate randomized time-sharing strategy: for each test point (X,Y) indepen- dently sample the configuration X3 A* with probability Aj, where A SIA'l is point in the |A* - dimensional probability simplex SI^"l { T[AT Σ, = 1,,,
Given Deats A is constant set, and each risk Q,(2;) Elg is also constant for all Aj A and i (1. For each Qi, the combined risk of the time-sharing strategy then
14

---

Published as a conference paper at ICLR 2023
be derived as the mean of mixture model where
|^"1
Qi(Ashang share)
4,0((27)
(11)
|A1 A max Q((A)) max (2
Let E be the event that all X; E A are risk controlling across all Q2 at level a, given the draw of Deat. Proposition 5.1 gives that this event occurs with probability least 1 6. Therefore,
P (A share)
Q:(A5) I <ai P()max:(AA5) S a4) 2 1-16, vi {L....,e} c) simultaneously.
(12)
Thus we have that Ashare is also (a, 8)-risk controlling for any choice of A.
A.4 HOEITDING-BENTKE INEQUALITY P-VALUES
The Heeffding-Bentkus Bentkus from (Bates et al., 2021) is combination of Hoeffding and Bentkus in- equalities:
p (A): m) = min (exp(-mhh (Q (A) A a, a)), eP (Binom(m, (x) S (((((((())]]
(13)
where hy (a. b) = a log(f) + (1 a) log( (-8).
A.5 WORST-CLASS OBJECTIVE
The empirical risk for the class-conditioned objective E (( = y| computed over the samples in class y:
Qace-olass (y. A)
Σ A' DM {(X, Y) E Dealy = 5} (X.Y)ED)
(14)
D
Note that the per-class risks are of the same type and are bounded by the same a. If furthermore classes are approximately balanced, i.e !D& s (Då Vy, 7 E V, than due to the monotonicity of the p-luuue with respect the empirical risk, we have:
p(A a) may p (Quce-ciass (y. a) (Daa)) ID P max Quee-etass (y. A): a, (D vEy
(15)
Therefore, instead of | objective functions, one per each class, we can define a single equivalent empirical objective Q Quce- A) = max.ey Qucc-class A).
A.6 SELECTIVE CLASSIFICATION
Similarly above derivation for per-class accuracy, for selective classification we define the selec- tive cost (given selection):
Q select- cost (A, Scous (X; max J(X,y; 2 T
(16)
and the same for selective accuracy reduction:
Quelect-noo (A,
Pace (X; A) max f(X, y/ A)
(17)
which are evaluated empirically by:
Q select-coosrA., =
Joost (X; A)
D
XED
Quetect.ncc (A,T)
Qaco (X;
D
XED
where D (X E Deall max, [(X,;; r}.
15

---

Published as a conference paper at ICLR 2023
B MULTI-DIMENSIONAL PRUNING
First, we describe the core model units and introduce some essential notation, while keeping the exact model implementation as general possible. Second, we describe each of the pruning dimen- sions, its associated importance score, and the thresholding mechanism.
B.1 TRANSFORMER MODEL
Consider Transformer model (Vaswani et al., 2017: Devlin et al., 2018) with K layers. The input to the model is given as a sequence of L (for notational simplicity we omit here the dependency of the length x)) tokens
: (L)) which first mapped to learneable word embeddings e = (e eL). Tokens are then passed through the model's 's layers, with h; = (h..1..... h,,L) denoting the j-th layer hidden representation. Each layer consists of multi-head attention, with W heads producing the combined output a, Σw A (1 (h)- which is followed by a feed- forward network to provide the next layer hidden representation. The last layer is attached to classification head with | outputs, where fzz y) denotes the output of class y- The model is optimized by minimizing loss function L computed empirically over the training set.
B.2 TOKEN PRUNING
It is often the case that the input consists of large amount tokens that have negligible contribu- tion for the prediction task. The idea in token pruning is to identify unimportant tokens and discard them at some point in the model.
To identify the contribution of each token, we attach to each layer a token importance predictor tok X + R based on the token hidden representation hj,, Following (Modarressi et al., 2022),
we use importance scores gradient attributions, computed by:
0f Me) dei
(18)
where Ye is the true label, and @ denotes element- wise product. The token importance predic- tors in each layer are optimized with a cross-entropy loss, where the labels are the scores, nor- malised to sum one. In the j-th layer, tokens with (x1) < Atok are pruned and are not transferred next layer. The number of tokens remaining after pruning is given by Ly Alo)) Eta N=== { slok (z1) Alo
B.3 EARLY EXITING
Early-exiting is based on the idea that examples vary in their difficulty level, hence, require different amount of computation to reach to good prediction. While for simple examples a decision can be made early difficult examples may require going through the full model. We attach prediction head fj : X' + y to each layer, trained to predict the labels via the same loss function as the original model. Following (Liu et al., 2020), we define the importance score based the prediction head entropy:
layer (x)
Σ P)(y(x) log (w)=))
(19)
DE 31
where Py (ylxx) are the per-class probabilities provided by the j-th prediction head. Based on this score, examples with 8; layer (xr < Alayrr exit in the j-th layer. The exit layer of x given by
K (2; Awwer) arg min, {i {1,.... ................................ K} layer (x) < Alayer]
B.4 HEAD PRUNING
It was shown by Michel et al. (2019) that significant fraction of attention heads can be removed with little impact on the performance. Each attention head (w,j), < j < K, < < W is assigned a score shead(() (w) according to:
a (w) = Attn (hg-1)² OAttn (hg-1)
(20)
16

---

C IMPLEMENTATION AND DATASET DETAILS Published as a conference paper at ICLR 2023
Table C.I: Datasets Details
Dataset
Task
Trin
Val.
Test
Cal. fout of Test)
Full model Acc. [%]
IMDB
Sentiment analysis on movie reviews
20K
5K
10K
5K
94
AG News
News topic classification
115K
5K
7.6K
5K
93
QNLI
Question-anss wnswer pair classification
~ 10K
6K
-..KK
3.4K
92
QQP
Question pair semantic equivalence
360K
5K
10K
5K
91
MNLI
Natural language inference
250K
150K
30K
10K
86
0.20
Method
0.25
Method
Accuracy Dilference
diagonal
0.20
evaluations
0.15
Opt: evaluations
Opt: 100 evaluations
Relative Cost
Opt: 150 evaluations
Opt: 100 evaluations
Opt: 150 avalustions
0.15
Opt: 200 evaluations
0.10
Opt: evaluations
Grid: evaluations
Grid: evaluations
0.10
0.05
0.05
0.00
Figure D.1: Results of Pareto Testing over AG News with multi-objective optimizer for different number of evaluations, and with a grid of thresholds. Results are averaged over 50 random splits. Accuracy reduction controlled and cost is minimized.
The scores in each layer normalized hhaad are pruned. The number heads left after pruning is given by Wj (A Ew 1 (wr) >> Abbad). Note that this is fixed pruning, unlike the previous pruning dimen- sions that vary according to the input æ.
one. Attention heads with (w))
Datasets. Splitting specifications and full model performance each task contained in Ta- ble C.1. Note that for IMDB, QQP and MNLI we used a subset of the original dev/test set order expedite evaluation. For MNLI used the split of (Sagawa al., 2019).
Prediction Heads. Each prediction head is 2-layer feed-forward neural network with 32 dimen- sional hidden states, and ReLU activation. The input is the hidden representation of the [CLS] to- ken concatenated with the hidden representation of all previous layers, as was proposed in (Wotezyk al., 2021).
Token importance predictors. Each token importance predictor is a 2-layer feed-forward neural network with 32 dimensional hidden states, and ReLU activation. The input is the hidden represen- tation of each token in the current layer and all previous layers, following (Wolczyk et al., 2021).
Training. The core model is first finetuned on each task. We compute the attention head importance scores based on validation data. We freeze the backbone model and train the early-exit classifiers and the token importance predictors on the training data.
Code.
Our code will be made available at httpt///gggggggttttttt///////// http:///ggghhh...cc//raahaaaeeae
D ADDITIONAL BASELINES AND RESULTS
Our method is based the Learn then Test (LTT) framework (Angelopoulos et al., 2021). which is summarized in Algorithm F.2. We compare our method to two baselines from (Angelopoulos et al., 2021): 3D-SGT summarised in Algorithm F.3, which is 3D extension to the 2D Hamming SGT,
17

---

Published as a conference paper at ICLR 2023
0.7
Pareto Testing
0.02
0.5
Abstention Rate
0.5
0.04
Split FST
0.01
0.3
0.2
0.1
Mate
0.0
0.00
0.05
0.10
0.15
0.20
0.25
Relative Cost
Figure D.2: Three-objectives, AG News one controlled, two free: accuracy reduction controlled by 0.05, 8 0.1, cost and abstention rate are minimized. The coloring according to accuracy reduction.
and Split-FST described in Appendix E. Note that we consider a broader setting in which, besides multiple risk control wish optimize additional free objective functions.
In addition, we define two non-risk controlling baselines:
a-constrained constrained optimization problem can be defined by:
min AEA
q
(A)
(21)
(1 < ai, V1 visisc.
s.t.
where qk (A) (Q=tt (A)...., Sal (A)]T. Directly solving for Eq. (21) the calibration data, however, would not necessarily yield a generalizable Á with the desired 1 - probability. other words, the true risk (Å) over test data might exceed a; possibly with high probability.
(a, ooodssntrdd We simultaneously test all possible configurations with error level å without correcting for multiple hypothesis testing.
Moreover, develop additional baselines and present their results herein:
Low-Risk Path similar to Split-FST (and Pareto Testing), this is a dual-stage method, assum- ing that the calibration data is split into subsets. In the first stage, we find solution to the constrained optimization problem, defined in Eq. (21). Then low risk path is defined from full model to the solution. The path is defined over the grid of in each step we pick neighbouring eyper-parameter combination (increasing one dimension with respect previous step) with lowest risk among all neighbours. The method is summarized in Algorithm F.4. Note that the method defines the path in the peramme space, implicitly assumes that the objective functions are monotonic with respect to each of the hyper-parameters.
combinations, where
This can be considered variant of the proposed method. When inter- ested in single configuration selection for specific a and 6, cheaper (but not equivalent) approach would be to solve multiple constrained problems:
Constrained-Pate Testing
min xEΛ
q
opt (A)
(22)
6UP4 (A) <a--e, visis
s.t.
for a sequence of values [O..... min; as]. Then, an ordered set of configurations to test is de- fined by the solutions to Eq. (22) with decreasing values of Note that both the constrained and the full multi-objective variants are equivalent for the case of a single control constraint. How- ever, when there multiple constraints Pareto Testing operates larger set of hyper--aramette
18

---

Published as a conference paper at ICLR 2023
0.9
0.8
0.8
ttllesstew
Ed
0.01
tS Bi-inosh
Ed
0.11
Accurazy
0.50
0.
Accuras
0.7
0.00
0.7
030
HeadTorutald
01
0.8
HaadThmahhldd
0445
60
0.11
0.45
6.0
0.11
040
001
032
0.60
E.0
011
0.25
1.0
6.44
0015
0.5
-3.3
0.2
-133
0.1
0.1
0.0
0.2
0.4
0.6
0.6
1.0
0.0
0.2
0.4
0.6
0.6
1.0
Relative Cost
Relative Cost
IMDB
(b) AG News
0.9
0.9
0.8
0.8
Accuracy
0.35
1.0
3.00
0.7
0.00
0.7
0.20
0:45
5.0
03
0.6
0.50
Head/hrodooh
01
0.11
0.15
0.15
0.22
0.13
-24
E33
0.08
035
1934
0.5
-2.8
0.35
0.14
0.5
0.1
0.6
Relative Cost
Relative Cost
(c) QNLI
(d) QQP
Figure D.3: Shows cost and accuracy trade-off's test data provided by grid of 6480 configura- tions (18 head, 20 token and 18 early-exit thresholds).
combinations, consisting of solutions to:
min x
9 (A)
(23)
(A) VI visis
with e; values in [O...., ag), namely, solving the constrained problem for all possible combinations of (c).
Pruning model. Figure D.3 shows the accuracy and the relative cost of the proposed adaptive prun- ing model f for various threshold combinations, computed over test data. We see that the fusion of all pruning dimensions yields a wide variety of configurations with a clear trade-offs between accuracy and cost. In addition, the Pareto front consists of different threshold combinations, indi- cating that the optimal threshold value in each dimension is not fixed and varies with the desired cost/accuracy level.
Two objectives accuracy controlled, cost minimized (additional results). Results for additional baselines are shown in Fig. D.4, including the two non-controlling baselines: a-constrained and (a, d)-constrained, and our derived Low-Risk Path baseline. We that, in many cases, Low-Risk Path obtains similar cost reduction compared to our proposed method, however, it is inferior for certain tasks and a values. compared to our method. This of course comes with price of suffering from risk violations that exceed = 0.1, 1 as can be seen in the bottom line bar plots. However, we see that the there not large difference between the cost reductions obtained by method and the non-controlling basclines. This indicates that our method, though providing risk control guarantees, as opposed to the non-controlling baselines, is not overly conservative, and effectively optimizes the free objective function, leading to significant cost reduction.
expected, both non-risk controlling baselines obtain lower costs
We further examine the different aspects of the proposed method. The size of the Pareto optimal set obtained for each task is shown in Fig. D.5. We see that the size of the Pareto set varies among tasks and is around 3 5% of the original set (6480 configurations for each task), which is significant
19

---

Published as a conference paper at ICLR 2023
Metted
Pathed
0.20
Patted
3.33
1413
Futh
3.33
0.25
035
0.10
0.15
2.28
0.10
0:13
0.31
0:35
000
0:15
0.70
Nethod
Hittool (o.
Hathed aicemnoked
Mattes
eooe med
Lowil 1ath
Ion Res Aan
Pararo Tarting
Turting
011
2.0
332
0.55
6:15
2.2
0.55
0.10
6.15
0.22
3.10
6:15
6.55
0.10
0.20
Methed
Mahhal R.d0conmmsiee
03
PST
PST Names lesting
Lowilachees
Eush
03
35
(a) IMDB
(b) AG News
(c) QNLI
(d) QQP
Figure D.4: Additional results for two-objectives accuracy reduction is controlled by a E {0.025, 0.5.... ..2), = 0.1, cost is minimized. Top row: accuracy reduction; mid-
dle row: relative cost; last row: rate of risk-violations. Results are averaged over 100 random splits to calibration and test.
Size
200
150
100
50
IMU
Task
Figure D.5: Additional results for two-objectives: accuracy reduction and cost. Sizes of the Pareto set for each task.
reduction of the hypotheses space. To demonstrate the variation across splits we show the violin plots in Figure D.7. We observe that our method obtains lower variance compared to Spit FST. This may be due to the fact that Split FST orders the hypothesis according to p-values only, and similar p-values can correspond to varying costs. Our method has slightly higher variance compared to 3D SGT, which may be attributed to the additional level of randomization caused by calibration set splitting. Figure D.6 compares the sizes of the validated
returned by either Pareto Testing and Split FST, showing that our methods leads to larger sets of valid configurations. In Fig. D.8, we show the results our method for different sizes of Dopt We see that as expected the performance improves the size of Dopt increases, and that size of 500 points is already sufficient to obtain stable performance.
Two objectives cost controlled, relative accuracy loss minimized. We evaluated the opposite scenario where the relative cost is controlled, while accuracy reduction is minimized. Note that for 3D-SGT and Low-Ris Path start testing from the empty model (lowest cost risk) towards the full model. The accuracy reductions of all methods are summarized Table D. We observe that as opposed to accuracy reduction, here the results of all methods are similar (except for Low-Risk Path).
Two objectives- - accuracy controlled, FLOPs minimized. We experimented with a different cost measure in terms of FL.PSs speed-up, which can be considered as more practical measure, tailored
20

---

Published as a conference paper at ICLR 2023
340
Merhed
Methed Parco Tarl
Method Parcso Tast
Nethod Permic Tustrn
Parees Tasting
(a) IMDB
(b) AG News
(c) QNLI
(d) QQP
Figure D.6: Additional results for two-objectives accuracy reduction controlled by a E (0.025, 0.075, 0.125, 0.2), 8 = 0.1, cost is minimized. Compare sizes of validated configurations for Pareto Testing and Split FST (computed over 20 random trials).
3330 HST Tusking
3.55
Spill HST
HOT
Tuasing
Toxting
a.u
auto
833
3.33
20-
SCT
06
Splt
28
(a) IMDB
(b) AG News
(c) QNLI
(d) QQP
Figure D.7: Additional results for two-objectives accuracy reduction is controlled by E {0.05, 0.1, 0.15]. 5 = 0.1, cost is minimized. Top: violin plots for accuracy reduction; bottom: violin plots for relative cost (computed over 100 random splits).
the specific architecture being used. Results are summarized in Table D.2. We see that the proposed method almost always obtains the best speed-ups, which is inline with our other results.
Three objectives accuracy/worst accuracy controlled, cost minimized. Results for additional baselines are shown in Fig. D.9. Here too, our method performs the best. In this scenario, Constrained-Patt Testing obtains similar results while Low-Risk Path is significantly worse
Three objectives accuracy and abstention rate controlled, cost minimized. We use the same setup of selective classification described $7. Note that combining т with the other three prun- ing dimensions, obtain four dimensional hyper-parameter space, where there is complex interplay between the hyper-parameters and the risk functions. As t increases we expect to get better accuracy-cost trade-offs since remove difficult examples. In addition, abstention rate is monotonic with respect to 7 but is also influenced by the pruning dimension in an uncharacterized manner.
Here we control both accuracy reduction and abstention rate, while minimizing cost. Since the risk functions not necessarily monotonic with respect to all hyper-parameters, Low-Risk Path is not relevant. Moreover, since here we have a 4D hyper-parameter space, 3D SGT cannot be applied. Results are summarized in Fig. D. where all methods obtain similar results.
E WAMILY-WISE ERROR RATE CONTROL.
Let Ag denote set of possible configurations to test, and A, C Ag denote the set of rejected hypotheses. When performing multiple hypothesis testing (MHT)), FWERRcontrolling procedure accounts for controlling the probability of making one or more false discoveries, i.e. falsely rejecting at least one true null hypothesis:
P P(A,, nAl > 1) <
(24)
where Ag C Ag is the set of configurations for which the null hypothesis is true.
21

---

Published as a conference paper at ICLR 2023
2.33
2.5
2.00
0.10
2300
2505
LYCE
2003
0.10
2.2
0.10
0.33
0.31
0.33
0.23
0:16
0.00
Apt
503
590
350
SCMANN Coll
506
190
20
33
0.55
6:10
222
0.55
0.15
3.50
0.00
6.55
0.10
0.20
(a) IMDB
(b) AG News
(c) QNLI
(d) QQP
Figure D.8:
Additional results for two-objectives accuracy reduction is controlled by
{0.025, 0.05. ..... 0.2). 8 0.1, cost minimized. Top: accuracy reduction; bottom:
relative cost for different sizes of D (computed over 100 random splits to calibration and test).
Table D.I: Two-ohjective scenario: relative cost is controlled by a E 0..1,0.2.033),. 5 = 0.1, accuracy reduction is minimized. Shows accuracy reduction. Results averaged 100 random splits to calibration and test.
Method
0.1
01.2
01.3
IMDB
Ag News
QNLI
QQP
IMDB
Ag News
QNLI
QQP
IMDB
Ag News
QNLI
QQP
3D-SGT
0.05
0.04
0.14
0.09
0.03
0.02
0.09
0.06
0.02
0.00
0.05
0.03
Split FST
0.05
0.01
0.15
0.10
0.02
0.02
0.09
0.06
0.02
0.01
0.06
0.03
Low-Risk Path
0.26
0.22
0.25
0.17
0.05
0.26
0.11
0.16
0.01
0.12
0.05
Pureto Testing
0.05
0.04
0.13
0.09
0.02
0.02
0.08
0.06
0.02
0.01
0.05
0.03
We briefly describe several possible procedures, some of which exploit a-priori known structure in the hypotheses set.
Bonferroni Correction. This is the simplest procedure for counteracting the multiple testing prob- lem, while being also the most conservative. The set of rejected hypotheses retrieved by the Bonfer- roni correction (Bonferroni, 1936), is given by:
HBr = HH p () < 6/|Ag]
(25)
Fixed Sequence Testing. Multiplicity correction can be avoided when relying on a pre-defined ordering of the hypotheses. In FST, the hypotheses are sequentially tested with the same error budget, until failing to reject for the first time. Denoting by HAay.... H H.A. AgD the ordered set of hypotheses, FST yields the following set of rejected hypotheses (Holm, 1979):
HEsT (H j < J}, J minfj p() 2 8).
(26)
This procedure is advantageous in the case that there is natural ordering of the hypotheses from the most likely to rejected to the least likely one. For example, it can be applied our problem when n and the hypotheses are ordered by threshold values from low to high.
Sequential Graphical Testing SGT (Bretz et al., 2009) can be viewed as an extension FST, where the relation between the hypotheses is richer than just sequential path, and is therefore pa- rameterized by a directed graph G. The graph's nodes are null hypotheses, and the edges connecting between them specify the way the error budget propagates from one node to the other. Each node allocated an initial error budget. Each time an hypothesis is rejected, the procedure reallocates the error budget from node i to the rest of the nodes according to the edge's weights, and the graph is modified. Several possible graph structures were proposed in (Angelopoulos et al., 2021) for the case of two-dimensional grid of hypotheses. One option is 'Hamming graph' in which the ini-
22

---

Published as a conference paper at ICLR 2023
Table D.2: FLOPs Speed-Up. Accuracy Reduction controlled by level a, while Flops Speed-Up is maximized. Results are averaged over 10 random splits to calibration and test.
0.025
Ag News
IMD8
QNLI
QQP
Ag News
IMD8
QNLI
QQP
Ag News
IMDB
QNLI
QQP
3D-SGT
x2.34
x1.71
x1.38
x1 89
x2.80
x4.45
x1.59
X2.16
x3.12
x4.45
x1.98
x2.71
Split FST
x1.69
x1.35
x1.99
x1.50
x4.18
x1.89
Low-Risk Path
x2.38
x3.96
x1.37
x1.85
x2.95
x4.2
x1.36
x2.16
x3.65
x4.20
x1.94
x2.73
Parcto Testing
x2.42
x4.
x1.37
x1 86
x3.00
x4
x1.59
x2 18
x3.65
x4. 82
x2
x2 86
Method
Vosst Difference
0.5
Method Pach
Accurscy Diffeeecce
Inse-Rtee
digoral
0.325
Camstrained--eet Sead ng
Constrained- Path Testing
Rolaatvve Cast
Parato Testiing
Panetic lisling
sk Peth
0.4
Constralnee Path Testing
0.075
Parato lesting
0.05
0.025
0.05
0.05
(a) Accuracy Difference
(h) Worst Accuracy Difference
(c) Relative Cost
Figure D.9: Three-objective scenario, MNLI two controlled, one free: average accuracy con- trolled by a1 {0.025, 0.5..... 0.2), worst accuracy is controlled by ag 0.15, 6 0.1, cost is minimized without control. Results are averaged over 100 random splits to calibration and test.
tial error budget is allocated to the bottom- right node, and the error budget is propagated outward. Another option is 'Fallback', where the error budget is split between each possibility in the first dimension. An FST then performed for a fixed value on the first dimension, and progressing in the other dimension.
Split Fixed Sequence Testing. Proposed in (Angelopoulos et al., 2021), Split-FST can be utilized when there is no clear structural relationship between the hypotheses for defining graph for SGT. The core idea is to split the calibration data in two subsets, where the first split is used to learn the graph, while the other is used for testing. Specifically, they propose to define a sequence of p-values 3 ranging from to Then, for each B, find the hypothesis where the p-values of all risks (computed over the first split) are the closest (in vector infinity norm) to B. Based on this ordering, FST can be then performed over the second split.
23

---

Published as a conference paper at ICLR 2023
0.20
degonal
6.10
Method
0.20
Nethod
Accurccy Diffe Difference ercee
Method
Spiit FST
Spilt FST
0.15
Alsteertoon Rater
0.09
Constraincd Testing
Berattee Coet
Constraines-Pn Pach
Cureitsinee-Puil Seling
Parwio Testing
Tenling
Poreto lesting
0.10
0.00
0.30
0.05
0.07
0.00
0.05
0.10
0.15
0.20
0.05
0.10
0.15
0.20
0.05
0.10
0.15
0.20
(a) Accuracy Difference
(b) Absteation Rate
(c) Relative Cost
Figure D.10: obree-ob scenario, AG News two controlled, one free: average accuracy is controlled by on E {0.025, 0.5...., 0.2), abstention rate controlled by a2 = 0.1, 0.1, cost minimized. Results are averaged over 100 random splits to calibration and test.
ALGORIHHMS
Algorithm F.1 Recover Pareto Optimal Set
Definitions: A is the hyper-parameters search space. GI,..., G, is set of objective functions. B is the maximum number of function evaluations. Opt imi zer a multi-objective optimization algorithm.
1: function PARETOOPTIMALSSTTA, GI, if Optimi zer Brute-Force then Ag f uniformly sample B configurations in A
2:
3:
4: Apar + NONDOMINATEDAA, CI....,,, ,,)
5: else
6:
Apar + P--pppmmize(A.. GI...., Gr, B) return Apar
7:
function NONDOMINATEDDAA, GI,...,Gr
8: Ao + Ag
9:
for Ag do for X' Ag, X + X do
10:
d=0 0
12:
for i (1...., ..... do
13:
G, < (A) then
14:
d d+1
15:
if d = then
Ag = Ao/ break
17:
return A,
24

---

Published as a conference paper at ICLR 2023
Algorithm F.2 Learn then Test (Single Objective)
Definitions: configurable model f adapted by thresholds À ,A Aa), calibration data Deat of size m, objective function Q, user-specified control limit and tolerance level 6, set of hyper-parameter combinations Ag-
1: function CALIBRATION(Pea. Ag. a, 8)
2:
for À Ag do Associate the null hypothesis:
3:
Hx: Q(A) 2
(27)
4: Compute the empirical risk over Deal:
Qcal
Σ q(x,Y: Y;
(28)
(X,Y)EDa)
5:
Compute Hoeffding p-value (or Hoeffding-Benee Bentkus p-value (13)):
p (A, a) = (p(pm))@ (2); (
-2m(a-Quu)
(29)
6: Recover subset of thresholds A, Ag for which the null hypothesis is rejected, by apply- ing FWER controlling procedure.
7: return A,
Algorithm F.3 3D Graph Testing
Definitions: configurable model f adapted by thresholds À (A1..... An), calibration data Deat of size m. objective functions Q......
., Q.. user-specified control limits (a)..... 0g) and
tolerance level 5, grid of 7 x J x K thresholds Ag = {Y] ................................ X1 (At...., X x (
3: X
Aii.k (Af. Xg. Xg), 3D graph W with / J x K nodes and weights W .. j.k determining the error propagation, A an x J x K matrix with initial error budget for each configuration, satisfying E.j.k A.j.k 8.
1: function CALIBRATE(D cal, a A, W)
2: for E Ag do
3: For X E Ag compute Q (A) J. E(x,reE (;)
4: For X E Ag compute, compute p-values ofal (A, (A, maxigisel (A);a,)
5: A, + SGT p8, (X, a)).
6: return A,
7:
function SGT(W, p (A, a)) J/ (I....,K) K}
8:
I (1...., 1 (1,
9:
Ap + 0
10:
i",j", K* arg min (ig.)eez p (Xiik a) Ai,,
11:
while
I > do
12:
if p ادد (Aij.
a) < A then
A, + A, U jtt j
13:
レ (/ (i"
15:
Ai.i Ai.j. + Ainijo,ko Win.jake- -ij.k, V(i,j,k) EI A.)Ai....
i'j",," arg min p (
(Ai
return A,
25

---

Published as a conference paper at ICLR 2023
Algorithm F.4 Shortest-Path Testing
Definitions: configurable model adapted by thresholds À (A1...., An), Deal Dopt U Dresting is a calibration set of size m, split into optimization and (statistical) testing sets of size my and m2, respectively, objective functions Q1...., Qc. user-specified control limits a = (aI...., (e)) and tolerance level 6, the resolution in the j-th dimension, Amin consists of the minimum values of all thresholds, Amax consists of the maximum values of all thresholds.
parameter resolution y = (M...., 7,), where y is
function OPTIMIZATION(( opt, Q:)
2: Define the constrained problem (21).
3: Apply constrained optimization to find optimal configuration Aopt.
4: Aop CREATEPATH (Amin: Aapt. 7) U CREATEPATH (Aopt: Amax 7).
5:
return Aopt
6: function CREATEPATH(A Xend
7:
( Astan
8:
i+1
9: while (0) # Aend do
Punin +
11:
for j E {l,....
n
do
(4)
(8)
+ 7s
X
and then
14:
Continue
15:
else
16:
A next
+ (211) (1)
(1)
17:
if pog A next .x) <
Pmin then
18:
(1) A
19:
Poin oP next
20:
return (X
21:
function CALIBRATION resting, Aopts ax, d)
Same as in Algorithm
26


Reviews:
[{"review_id": "aExy3kwQUL", "reviewer": "Reviewer_F3Rn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers combining multi-objective optimization with multiple-hypothesis testing. More specifically, they consider optimizing some objectives Q_i's while applying risk control on multiple other objectives such that Q_j\\le c with high probability. They consider reducing the dimension of the high dimensional vector of candidates of configurations by only restricting themselves to the Pareto frontier. Effectiveness of their method is considered on large-scale transformer models in NLP.\n\nMain method is based on existing work fixed sequential testing, by adapted it to the Pareto frontier setting.\n\n", "summary_of_the_review": "See comments above.", "strength_and_weaknesses": "Strength. Reducing high-dim configurations is an interesting topic. Experiments are comprehensive.\n\nWeakness:\n1. Writing is not clear.  For example, is equation 3, should the optimization objective be of subscript c+1 instead of c? The discussion of c+1 and c+k is not clear enough, constantly switching between the two cases.\n2. Lack of innovation. The main technique is based on FST. The only contribution is to suggest using the Pareto frontier to reduce the dimensionality of (tau_1, \\cdots, tau_n)'s need to be considered, which is quite natural. Also, there is a discrepancy between the empirical Pareto frontier based on Q.hat and based on the real Q. The one based on real Q is the desired frontier. \n3. Notation sloppiness. In equation 4, argmin is mis-used, which is also pointed out by the author themsevle -- it is possible that no uniformly optimal solution exists.\n\nI suggest the authors significantly polish this writing and consider more extensions.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EJEvNJajWiX", "reviewer": "Reviewer_R3DQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose Pareto Testing, a multiple hypothesis testing strategy based on Learn then test (LTT) for statistically controlling multiple risks. In contrast to prior work, the method uses an additional split of the data to identify hyper-parameter configurations that are Pareto optimal (i.e., on the Pareto frontier). This improves statistical efficiency as less hypothesis tests are required.", "summary_of_the_review": "I think the paper is a good contribution for ICLR. Due to the density, I feel that writing can be improved at places and I’d appreciate comments on my other questions regarding experiments.", "strength_and_weaknesses": "Strengths:\n- Writing, while very dense, is generally well structured and includes the main points to follow the paper despite building on extensive work in the Learn Then Test paper.\n- Related work is covered thoroughly and differentiates the contributions of the paper well.\n- The method generally addresses an important problem and improves over previous work by decreasing the number of hypotheses to test.\n\nWeaknesses:\nSome comments on writing:\n-- Because the paper is very dense, it would occasionally be worth resorting to easier sentences. The fourth paragraph in the introduction is a good example for this.\n-- I found the intro figure a bit misleading as it puts too much focus on the architecture. I understand that the experiments use architectural hyper-parameters for risk control. But the figure does not really tell me anything about the risk control itself. It is not a bad figure, but I feel it misses the main contributions.\n-- The notation of minimizing a set of is a bit unclear – I assume the authors want to emphasize that we jointly want to minimize different risks. But I feel this should be made clearer – see Eq. (4) and (6) and algorithm 1.\n-- The computation of the p-values – which is an integral part of the method – could be made clearer in the main paper. I could only find that in algorithm F.1 or related work and I feel the paper would benefit from making that clearer for readers less familiar with these approaches (e.g., conformal p-values are computed quite differently compared to p-values based on these bounds).\n\nMethod:\n- How exactly is the Pareto frontier found in practice. The experiments include one paragraph on this, but it is actually unclear what the default method of optimization is? Is it right that exhaustive optimization over the grid is used?\n\nExperiments:\n- In general, I feel that the main contribution is improving statistical efficiency and reducing the number of hypotheses to test. I would appreciate some more concrete experiments surrounding this:\n-- More explicitly showcases to what extent Pareto Testing reduces the hypotheses space – i.e., how big is the Pareto optimal set, how many hypotheses are tested compared to LTT?\n-- How does the D_opt set size impact that and influence the variation or the tightness of the risk control in the end?\n- In plots, I assume the are is the standard deviation, or are the min/max/X% confidence interval? I am trying to understand whether Pareto Testing has some influence on this variation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BmleSmq-xH", "reviewer": "Reviewer_ZXwJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work is built upon the results of Learn Then Test framework by introducing Pareto Testing.  The authors develop an efficient method for calibrating models such that their predictions provably satisfy multiple explicit and simultaneous statistical guarantees (e.g., uppper-bound error rates), while also optimizing any number of additional, unconstrained objectives.\n\nThis method contains two stages. Stage1: solving an unstrained  multi-objective optimization problem to recover an approximate set of Pareto-optimal configurations; Stage2: performing rigorous sequential testing over the recovered set to yield tight control of the desired risks.\n\nThe main idea of this proposed method is that  to perform testing ONLY over the Pareto optimal set. And the effectiveness is demonstrated for reliably accelerating Transformers \n", "summary_of_the_review": "Overall, this paper is marginally above the acceptance threshold. ", "strength_and_weaknesses": "Strength:\n\nThis work is a great attempt by combining the combination of multi-objective optimization and \"Learn and Test\" for risk-control.  Intuitively, it is obvious that applying FST only on Pareto Front will be efficient (because the size of configuration is much smaller). \n\nWeaknesses:\n\nThe setting discussed in this paper is as:  for all c+k objectives,  the first c objectives are controlled by c user-specified risk bounds, and the rest k objectives are free to optimize.  If k =0, i.e., all the risks are controlled, how to decide the final configuration?\n\nOther minor comments:\n\n(1) Equation(3),  minimizing the remaining objective function $Q_c$? ( I guess it should be $Q_{c+1}$)\n\n(2) Algorithm 1 line 11, when k>1, how to get a set of configurations representing different possible trade-offs?\n\n(3) Figure 2 is a bit confusing, from the path showed, Q1 is not controlled under $\\alpha$, instead, the configuration selected with $Q_1>\\alpha$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "94dWqgpCeW", "reviewer": "Reviewer_xGYM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a two-stage approach to flexibly optimize and test to find\nhyperparameter settings that have provable guarantees with respect to the\noptimized objectives. The authors describe their framework and evaluate it\nempirically on a Transformer model. The presented results demonstrate the\npromise of the proposed method.", "summary_of_the_review": "The paper studies an interesting and important problem with real-world\nconsequences. It is well written, although the density of math makes it\nchallenging to understand. Intuitively, it is difficult to follow the presented\ntechnique -- the paper seems to imply that I can guarantee e.g. 100% accuracy\nwith 100% probability, which does not make sense in practice. A detailed example\nto illustrate this would be helpful, in particular as the risks for the\napplication are not defined in terms of absolute, but relative performance.\n\nThe empirical results are not easy to interpret either as all results are shown\ndependent on a specific range of alpha values (chosen how?) and it is unclear\nhow this affects other approaches that are not controlled. If I decided to use\nthe proposed method, what results can I expect compared to other hyperparameter\noptimizers, e.g. SMAC, when given the same resources?\n\nThe authors denote hyperparameters with tau, whereas most of the literature uses\nlambda. It would be nice to be consistent with the literature.\n\nIn the \"Model configuration\" section on page 2, the example given for\nperformance guarantees should be _minimal_ error rates. The labels in most\nfigures are too small.", "strength_and_weaknesses": "+ important and interesting problem\n+ novel angle of analysis\n\n- approach not intuitive to understand\n- performance in practice not clear", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster