Introduction
Pairwise human-preference judgments have become a standard tool to evaluate large language models (LLMs). In arena-style evaluation, a user submits a prompt, views two responses with the model identities hidden, and selects the preferred response (Zheng et al., 2023; Chiang et al., [10 ] ). Given these pairwise comparisons, a common approach is to fit a statistical model to estimate a latent score for each model, and use the estimated scores to rank the models. But model quality is not one-dimensional: a model preferred for code generation need not be preferred for creative writing or vision (Liang et al., 2023; Frick et al., [19 ] ). How should models be compared without collapsing these tradeoffs into a scalar score?
A natural target is the strict Pareto frontier: a model lies outside the frontier only if another model has a strictly higher latent score on every objective. This criterion excludes uniformly inferior models, while retaining models with different cross-objective strengths. Identifying this frontier reliably, however, requires costly human-preference comparisons across model pairs and objectives. How should the comparisons be allocated to identify the frontier efficiently? We develop an adaptive sampling procedure that identifies the strict Pareto frontier at a prescribed confidence level while reducing the number of comparisons required. As a preview, Figure 1 presents an application of our method to comparisons from Arena-Human-Preference-140K (Chiang et al., [10 ] ), collected through July 2025. Treating code, math, and Instruction-Following as three objectives, the method identifies three models on the strict Pareto frontier.
Figure 1. Three-dimensional comparison along the Code, Math, and Instruction-Following objectives from the Arena-Human-Preference-140K dataset [10 ] . Diamonds denote the strict Pareto frontier.
Problem formulation
We formalize this task as a fixed-confidence sequential identification problem. Consider K ≥ 2 K \ge2 K ≥ 2 d d d i ∈ [ K ] : = { 1 , … , K } i \in[K] := \{1, \ldots, K\} i ∈ [ K ] := { 1 , … , K } θ i = ( θ i , 1 , … , θ i , d ) \theta_i = (\theta_{i,1}, \ldots, \theta_{i,d}) θ i = ( θ i , 1 , … , θ i , d )
Let F t − 1 \mathcal{F}_{t-1} F t − 1 t t t t t t F t − 1 \mathcal{F}_{t-1} F t − 1 Q t = ( I t , J t , R t ) Q_t = (I_t, J_t, R_t) Q t = ( I t , J t , R t ) I t , J t ∈ [ K ] I_t, J_t \in[K] I t , J t ∈ [ K ] R t ∈ [ d ] R_t \in[d] R t ∈ [ d ] ( i , j , r ) (i,j,r) ( i , j , r ) Y t ( i , j ) ∈ { 0 , 1 } Y_t^{(i,j)} \in\{0,1\} Y t ( i , j ) ∈ { 0 , 1 } t t t 1 1 1 i i i j j j r r r Y t : = Y t ( R t ) ( I t , J t ) Y_t := Y_t^{(R_t)}(I_t,J_t) Y t := Y t ( R t ) ( I t , J t ) [6 ] :
P θ ( Y t = 1 ∣ F t − 1 , Q t = ( i , j , r ) ) = p i j ( r ) ( θ ) : = σ ( θ i , r − θ j , r ) , where σ ( x ) : = 1 1 + e − x . (1) \mathbb{P}_{\theta}(Y_t = 1 \mid\mathcal{F}_{t-1}, Q_t = (i,j,r)) = p_{ij}^{(r)}(\theta) := \sigma(\theta_{i,r} - \theta_{j,r}), \qquad\text{where } \sigma(x) := \frac{1}{1+e^{-x}}. \tag*{(1)} P θ ( Y t = 1 ∣ F t − 1 , Q t = ( i , j , r )) = p ij ( r ) ( θ ) := σ ( θ i , r − θ j , r ) , where σ ( x ) := 1 + e − x 1 . (1) Consequently, p j i ( r ) = 1 − p i j ( r ) p_{ji}^{(r)} = 1 - p_{ij}^{(r)} p j i ( r ) = 1 − p ij ( r ) p i i ( r ) = 1 / 2 p_{ii}^{(r)} = 1/2 p ii ( r ) = 1/2
Definition 1.1 (Strict Pareto frontier). For a collection of vectors x = ( x 1 , … , x K ) ∈ ( R d ) K x = (x_1,\ldots,x_K) \in(\mathbb{R}^d)^K x = ( x 1 , … , x K ) ∈ ( R d ) K j j j i i i i ≺ x j i \prec_x j i ≺ x j x i , r < x j , r x_{i,r} < x_{j,r} x i , r < x j , r r ∈ [ d ] r \in[d] r ∈ [ d ] x x x
P ( x ) : = { i ∈ [ K ] : ∄ j ∈ [ K ] such that i ≺ x j } . \mathcal{P}(x) := \{i \in[K] : \nexists j \in[K] \text{ such that } i \prec_x j\}. P ( x ) := { i ∈ [ K ] : ∄ j ∈ [ K ] such that i ≺ x j } . Remark 1.1. Our strict-dominance convention differs slightly from the standard Pareto convention, under which a model dominates another if it is at least as good in every coordinate and strictly better in at least one coordinate [5 ] . This strict convention also has a natural decision-making interpretation: if a user cares only about an objective on which two models are tied, neither model should be discarded on performance grounds; token cost, availability, or other application-specific considerations may instead determine the final choice. From a technical perspective, non-strict dominance requires additional assumptions to handle ties on individual coordinates. Our finite-sample termination guarantee requires all classification gaps defined in Definition 2.2 to be positive, which may fail at coordinate-wise ties.
Accordingly, our goal is to design an algorithm A \mathrm{A} A ( I t , J t , R t ) (I_t, J_t, R_t) ( I t , J t , R t ) τ A \tau_{\mathrm{A}} τ A τ A = ∞ \tau_{\mathrm{A}} = \infty τ A = ∞ P ^ \widehat{\mathcal{P}} P P ⋆ : = P ( θ ) \mathcal{P}^{\star} := \mathcal{P}(\theta) P ⋆ := P ( θ ) δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) δ \delta δ 1 − δ 1-\delta 1 − δ
Definition 1.2 (δ \delta δ Θ ⊆ ( R d ) K \Theta\subseteq(\mathbb{R}^{d})^{K} Θ ⊆ ( R d ) K δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) A \mathrm{A} A δ \delta δ Θ \Theta Θ θ ∈ Θ \theta\in\Theta θ ∈ Θ
P θ ( τ A < ∞ , P ^ = P ( θ ) ) ≥ 1 − δ . \mathbb{P}_{\theta}\left(\tau_{\mathrm{A}} < \infty, \widehat{\mathcal{P}} = \mathcal{P}(\theta)\right) \geq1-\delta. P θ ( τ A < ∞ , P = P ( θ ) ) ≥ 1 − δ . Among δ \delta δ α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 )
Q θ , α ( A ) : = inf { T ∈ N 0 : P θ ( τ A ≤ T ) ≥ 1 − α } , Q_{\theta,\alpha}(\mathrm{A}) := \inf\left\{T \in\mathbb{N}_0 : \mathbb{P}_{\theta}(\tau_{\mathrm{A}} \leq T) \geq1-\alpha\right\}, Q θ , α ( A ) := inf { T ∈ N 0 : P θ ( τ A ≤ T ) ≥ 1 − α } , with the convention inf ∅ : = ∞ \inf\varnothing:= \infty inf ∅ := ∞
Our contributions
Our contributions are threefold. First, we formulate fixed-confidence Pareto-set identification under objective-specific Bradley–Terry feedback and introduce Vector-Borda Empirical-Gap Elimination (VB-EGE) , an adaptive sampling procedure for this problem. The key technical insight is an order-preserving reduction from the latent score vectors to vector-Borda scores. Each Borda coordinate is the average win probability of a model against all opponents on a given objective, and the transformation preserves the coordinate-wise ordering of the latent scores—and therefore the strict Pareto set. Moreover, each Borda coordinate can be estimated directly from Bernoulli outcomes by comparing a model with a uniformly sampled opponent. This problem therefore reduces to Pareto-set identification over K d Kd K d
Second, we prove that VB-EGE is δ \delta δ
Finally, we evaluate VB-EGE on synthetic Bradley–Terry instances and logged comparisons from three real-world Arena datasets: Arena, SearchArena, and VisionArena. The synthetic experiments confirm the predicted scaling behavior and demonstrate the sample efficiency of VB-EGE. Arena experiments also demonstrate substantial gains in sample efficiency over uniform baselines in realistic settings.
Related work
We review three related literatures, arena-based LLM evaluation, adaptive pairwise comparison, and Pareto set identification, and provide additional discussion on related work in Appendix § 6 .
Arena-based LLM evaluation. Chatbot Arena aggregates human pairwise preferences into scalar model leaderboards [10 ] (Zheng et al. 2023). Subsequent work has improved their statistical stability by modeling ties and score dependence [1 ] , replacing iterative Elo updates with maximum-likelihood estimation and accounting for annotator reliability (Liu et al., 2025), and developing nonparametric ranking and uncertainty quantification [18 ] . Adaptive model-pair selection improves comparison efficiency (Liu et al., 2026), while prompt- or task-specific rankings address heterogeneity [19 ] (Li et al. 2026). These methods still produce scalar rankings, either overall or conditional on prompts or tasks. We instead identify the set of models that remain nondominated across multiple objectives.
Pure exploration from pairwise comparisons. Pairwise-comparison methods study winner and ranking identification without directly observing item utilities. Random-opponent comparisons lead to Borda scores and have been used for Borda-winner identification and active ranking ([23 ] (Jamieson et al. 2015)); simple Borda-type procedures can also be robust beyond parametric Bradley–Terry models ((Shah & Wainwright, 2018)). More recently, Goldberger & Rudi [21 ] developed an asymptotically optimal fixed-confidence method for top-k k k
Beyond these scalar targets, comparison-based methods have also been used for Pareto or skyline recovery. Asudeh et al. [2 ] adaptively select criterion-specific crowd comparisons to identify Pareto-optimal objects, Groz et al. [22 ] study skyline recovery under noisy coordinate comparisons, and Audiffren & Ralaivola [4 ] identify maximal arms from dueling feedback over a partial order. Our setting instead considers objective-specific Bradley–Terry comparisons generated by latent utilities and uses an order-preserving vector-Borda reduction for Pareto-set identification.
Pareto set identification. Pareto-set identification has primarily been studied in multi-objective bandits where pulling an arm directly yields a vector-valued observation. Existing work considers approximate and relaxed fixed-confidence recovery ([5 ] (Kone et al. 2023)), fixed-budget identification through Empirical-Gap Elimination and its cost-aware extension ((Kone et al., 2024; Xue et al., 2026)), and exact fixed-confidence identification with asymptotically optimal allocation ([13 ] ). Structured extensions include preference-cone and multi-output linear models ([14 ] (Karagözlü et al. 2024; Kone et al. 2025; Shukla & Basu 2024)). Our elimination rule is closest to ((Kone et al., 2024)), but our feedback is objective-specific and binary rather than a directly observed vector.
Vector-Borda Empirical-Gap Elimination (VB-EGE)
In this section, we present our proposed algorithm, VB-EGE, which adaptively allocates the comparisons to identify the Pareto frontier. The algorithm first represents the ordering of the models along each objective coordinate using the Borda scores (to be defined shortly), and then applies the empirical-gap elimination principle ((Kone et al., 2024)) to the vector of Borda scores to determine the sampling and stopping rule. We first introduce the notation used in the remainder of the paper.
Notation. For any x ∈ R x \in\mathbb{R} x ∈ R x + = max { x , 0 } x^{+} = \max\{x,0\} x + = max { x , 0 } a , b ∈ R a,b \in\mathbb{R} a , b ∈ R a ∧ b : = min { a , b } a \wedge b := \min\{a,b\} a ∧ b := min { a , b } a ∨ b : = max { a , b } a \vee b := \max\{a,b\} a ∨ b := max { a , b } f f f g g g f = O ( g ) f = O(g) f = O ( g ) f ≲ g f \lesssim g f ≲ g C > 0 C > 0 C > 0 f ≤ C g f \le Cg f ≤ C g f = Ω ( g ) f = \Omega(g) f = Ω ( g ) f ≳ g f \gtrsim g f ≳ g g = O ( f ) g = O(f) g = O ( f ) f = Θ ( g ) f = \Theta(g) f = Θ ( g ) f ≍ g f \asymp g f ≍ g f = O ( g ) f = O(g) f = O ( g ) f = Ω ( g ) f = \Omega(g) f = Ω ( g ) f = O ~ ( g ) f = \widetilde{O}(g) f = O ( g ) f = Ω ~ ( g ) f = \widetilde{\Omega}(g) f = Ω ( g ) f = Θ ~ ( g ) f = \widetilde{\Theta}(g) f = Θ ( g ) p , q ∈ [ 0 , 1 ] p,q \in[0,1] p , q ∈ [ 0 , 1 ] kl ( p , q ) : = p log p q + ( 1 − p ) log 1 − p 1 − q \operatorname{kl}(p,q) := p \log\frac{p}{q} + (1-p) \log\frac{1-p}{1-q} kl ( p , q ) := p log q p + ( 1 − p ) log 1 − q 1 − p 0 log ( 0 / x ) : = 0 0\log(0/x) := 0 0 log ( 0/ x ) := 0 x ∈ [ 0 , 1 ] x \in[0,1] x ∈ [ 0 , 1 ] x log ( x / 0 ) : = + ∞ x\log(x/0) := +\infty x log ( x /0 ) := + ∞ x > 0 x > 0 x > 0
The vector-Borda reduction
We first define the coordinate-wise Borda scores that are central to the algorithm.
Definition 2.1 (Coordinate-wise Borda scores). For each model i ∈ [ K ] i \in[K] i ∈ [ K ] r ∈ [ d ] r \in[d] r ∈ [ d ]
b i , r ( θ ) : = 1 K − 1 ∑ j ≠ i p i j ( r ) ( θ ) = 1 K − 1 ∑ j ≠ i σ ( θ i , r − θ j , r ) . b_{i,r}(\theta) := \frac{1}{K-1}\sum_{j \ne i} p_{ij}^{(r)}(\theta) = \frac{1}{K-1}\sum_{j \ne i} \sigma(\theta_{i,r} - \theta_{j,r}). b i , r ( θ ) := K − 1 1 j = i ∑ p ij ( r ) ( θ ) = K − 1 1 j = i ∑ σ ( θ i , r − θ j , r ) . When the dependence on θ \theta θ b i , r b_{i,r} b i , r b i , r ( θ ) b_{i,r}(\theta) b i , r ( θ ) representation of model i i i b i : = ( b i , 1 , … , b i , d ) ∈ [ 0 , 1 ] d b_i := (b_{i,1}, \ldots, b_{i,d}) \in[0,1]^d b i := ( b i , 1 , … , b i , d ) ∈ [ 0 , 1 ] d b = ( b 1 , … , b K ) b = (b_1, \ldots, b_K) b = ( b 1 , … , b K )
The key property of the vector-Borda transformation is that it preserves the ordering of the models along each coordinate induced by the latent scores θ \theta θ § 7 .§ 2.1 .
Lemma 2.1 (Coordinate-wise order preservation). For every i , j ∈ [ K ] i,j \in[K] i , j ∈ [ K ] and r ∈ [ d ] r \in[d] r ∈ [ d ]
sign ( b i , r − b j , r ) = sign ( θ i , r − θ j , r ) . (2) \operatorname{sign}(b_{i,r}-b_{j,r})=\operatorname{sign}(\theta_{i,r}-\theta_{j,r}). \tag*{(2)} sign ( b i , r − b j , r ) = sign ( θ i , r − θ j , r ) . (2) Consequently,
i ≺ b j ⟺ i ≺ θ j and P ( b ) = P ( θ ) = P ⋆ . (3) i \prec_b j \Longleftrightarrow i \prec_\theta j \quad\text{and}\quad\mathcal{P}(b)=\mathcal{P}(\theta)=\mathcal{P}^{\star}. \tag*{(3)} i ≺ b j ⟺ i ≺ θ j and P ( b ) = P ( θ ) = P ⋆ . (3) By Lemma 2.1, the latent strict Pareto frontier coincides with the Pareto frontier of the vector-valued Bernoulli means b 1 , … , b K b_1,\ldots,b_K b 1 , … , b K θ 1 , … , θ K \theta_1,\ldots,\theta_K θ 1 , … , θ K
For a selected focal model i i i r r r J ∼ Unif ( [ K ] ∖ { i } ) J \sim\operatorname{Unif}([K]\setminus\{i\}) J ∼ Unif ([ K ] ∖ { i }) Q t = ( i , J , r ) Q_t=(i,J,r) Q t = ( i , J , r ) Z : = Y t ( r ) ( i , J ) Z := Y_t^{(r)}(i,J) Z := Y t ( r ) ( i , J ) ( i , r ) (i,r) ( i , r ) J J J Z ∼ Bernoulli ( b i , r ) Z \sim\operatorname{Bernoulli}(b_{i,r}) Z ∼ Bernoulli ( b i , r )
Pareto classification gaps
Next, we define classification gaps that measure how difficult it is to determine each model’s Pareto status, while accounting for its role in identifying other models as non-Pareto. For x = ( x 1 , … , x K ) ∈ ( R d ) K x=(x_1,\ldots,x_K)\in(\mathbb{R}^d)^K x = ( x 1 , … , x K ) ∈ ( R d ) K i , j i,j i , j
m x ( i , j ) : = min r ∈ [ d ] ( x j , r − x i , r ) , M x ( i , j ) : = max r ∈ [ d ] ( x i , r − x j , r ) . m_x(i,j):=\min_{r\in[d]}(x_{j,r}-x_{i,r}),\qquad M_x(i,j):=\max_{r\in[d]}(x_{i,r}-x_{j,r}). m x ( i , j ) := r ∈ [ d ] min ( x j , r − x i , r ) , M x ( i , j ) := r ∈ [ d ] max ( x i , r − x j , r ) . Thus, M x ( i , j ) = − m x ( i , j ) M_x(i,j)=-m_x(i,j) M x ( i , j ) = − m x ( i , j ) i ≺ x j ⟺ m x ( i , j ) > 0 i\prec_x j\Longleftrightarrow m_x(i,j)>0 i ≺ x j ⟺ m x ( i , j ) > 0
Our algorithm follows a successive-elimination scheme, where models are sequentially removed from an active set. Subsequent comparisons use only remaining models as focal models, while opponents are drawn uniformly from the full original set of models excluding the focal model. We therefore define the classification gaps relative to an arbitrarily given set S ⊆ [ K ] S\subseteq[K] S ⊆ [ K ] S S S
P S ( x ) : = { i ∈ S : ∄ j ∈ S ∖ { i } such that m x ( i , j ) > 0 } . \mathcal{P}_S(x):=\{i\in S:\nexists j\in S\setminus\{i\}\text{ such that }m_x(i,j)>0\}. P S ( x ) := { i ∈ S : ∄ j ∈ S ∖ { i } such that m x ( i , j ) > 0 } . The definition of the classification gap is then given as follows.
Definition 2.2 (Restricted-set classification gaps). Let S ⊆ [ K ] S\subseteq[K] S ⊆ [ K ] ∣ S ∣ ≥ 2 |S|\ge2 ∣ S ∣ ≥ 2 x i ∈ R d x_i\in\mathbb{R}^d x i ∈ R d i ∈ S i\in S i ∈ S i ∈ S i\in S i ∈ S Δ i , S ⋆ ( x ) : = max j ∈ S ∖ { i } m x ( i , j ) \Delta^\star_{i,S}(x):=\max_{j\in S\setminus\{i\}}m_x(i,j) Δ i , S ⋆ ( x ) := max j ∈ S ∖ { i } m x ( i , j )
δ i , S ⋆ ( x ) : = min j ∈ S ∖ { i } { M x ( i , j ) ∧ [ M x ( j , i ) + + ( Δ j , S ⋆ ( x ) ) + ] } . \delta^\star_{i,S}(x):=\min_{j\in S\setminus\{i\}}\left\{M_x(i,j)\wedge\left[M_x(j,i)^++\left(\Delta^\star_{j,S}(x)\right)^+\right]\right\}. δ i , S ⋆ ( x ) := j ∈ S ∖ { i } min { M x ( i , j ) ∧ [ M x ( j , i ) + + ( Δ j , S ⋆ ( x ) ) + ] } . The restricted-set classification gap is
Δ i , S ( x ) : = { Δ i , S ⋆ ( x ) , i ∉ P S ( x ) , δ i , S ⋆ ( x ) , i ∈ P S ( x ) . \Delta_{i,S}(x):=
\begin{cases}
\Delta^\star_{i,S}(x), & i\notin\mathcal{P}_S(x),\\
\delta^\star_{i,S}(x), & i\in\mathcal{P}_S(x).
\end{cases} Δ i , S ( x ) := { Δ i , S ⋆ ( x ) , δ i , S ⋆ ( x ) , i ∈ / P S ( x ) , i ∈ P S ( x ) . Intuitively, for i ∉ P S ( x ) i\notin\mathcal{P}_S(x) i ∈ / P S ( x ) Δ i , S ⋆ ( x ) \Delta^\star_{i,S}(x) Δ i , S ⋆ ( x ) i i i i ∈ P S ( x ) i\in\mathcal{P}_S(x) i ∈ P S ( x ) δ i , S ⋆ ( x ) \delta^\star_{i,S}(x) δ i , S ⋆ ( x ) i i i i i i Δ i , S ( x ) \Delta_{i,S}(x) Δ i , S ( x ) i i i P S ( x ) \mathcal{P}_S(x) P S ( x )
In the following, we omit the set subscript when S = [ K ] S=[K] S = [ K ] P ( x ) : = P [ K ] ( x ) \mathcal{P}(x):=\mathcal{P}_{[K]}(x) P ( x ) := P [ K ] ( x ) Δ i ⋆ ( x ) : = Δ i , [ K ] ⋆ ( x ) \Delta_i^\star(x):=\Delta_{i,[K]}^\star(x) Δ i ⋆ ( x ) := Δ i , [ K ] ⋆ ( x ) δ i ⋆ ( x ) : = δ i , [ K ] ⋆ ( x ) \delta_i^\star(x):=\delta_{i,[K]}^\star(x) δ i ⋆ ( x ) := δ i , [ K ] ⋆ ( x ) Δ i ( x ) : = Δ i , [ K ] ( x ) \Delta_i(x):=\Delta_{i,[K]}(x) Δ i ( x ) := Δ i , [ K ] ( x ) Δ i B : = Δ i ( b ) \Delta_i^{\mathrm{B}}:=\Delta_i(b) Δ i B := Δ i ( b ) Δ i θ : = Δ i ( θ ) \Delta_i^{\theta}:=\Delta_i(\theta) Δ i θ := Δ i ( θ ) Δ min B : = min i ∈ [ K ] Δ i B \Delta_{\min}^{\mathrm{B}}:=\min_{i\in[K]}\Delta_i^{\mathrm{B}} Δ m i n B := min i ∈ [ K ] Δ i B
Phased vector-Borda elimination
VB-EGE proceeds in phases, maintaining an active set A A A B B B m ≥ 1 m \ge1 m ≥ 1 ( i , r ) ∈ A × [ d ] (i,r) \in A \times[d] ( i , r ) ∈ A × [ d ] n m − n m − 1 n_m-n_{m-1} n m − n m − 1
Z i , r , s : = Y t ( i , r , s ) ( r ) ( i , J i , r , s ) , where J i , r , s ∼ i . i . d . Unif ( [ K ] ∖ { i } ) , ∀ s = n m − 1 + 1 , … , n m , (4) Z_{i,r,s} := Y^{(r)}_{t(i,r,s)}(i,J_{i,r,s}), \qquad\text{where } J_{i,r,s} \mathrel{\mathop{\sim}^{\mathrm{i.i.d.}}} \operatorname{Unif}([K]\setminus\{i\}), \qquad\forall s=n_{m-1}+1,\ldots,n_m, \tag*{(4)} Z i , r , s := Y t ( i , r , s ) ( r ) ( i , J i , r , s ) , where J i , r , s ∼ i.i.d. Unif ([ K ] ∖ { i }) , ∀ s = n m − 1 + 1 , … , n m , (4) where t ( i , r , s ) t(i,r,s) t ( i , r , s ) s s s i i i r r r n 0 = 0 n_0=0 n 0 = 0 { n m } m ≥ 1 \{n_m\}_{m\ge1} { n m } m ≥ 1 m m m
b ^ i , r ( m ) : = 1 n m ∑ s = 1 n m Z i , r , s , ( i , r ) ∈ A × [ d ] . \widehat{b}^{(m)}_{i,r}:=\frac{1}{n_m}\sum_{s=1}^{n_m} Z_{i,r,s}, \qquad(i,r)\in A\times[d]. b i , r ( m ) := n m 1 s = 1 ∑ n m Z i , r , s , ( i , r ) ∈ A × [ d ] . Write b ^ i ( m ) = ( b ^ i , 1 ( m ) , … , b ^ i , d ( m ) ) \widehat{\mathbf{b}}^{(m)}_i=(\widehat{b}^{(m)}_{i,1},\ldots,\widehat{b}^{(m)}_{i,d}) b i ( m ) = ( b i , 1 ( m ) , … , b i , d ( m ) ) A A A A A A
S ^ A : = P A ( b ^ ( m ) ) , Δ ^ i , A : = Δ i , A ( b ^ ( m ) ) , i ∈ A . (5) \widehat{S}_A:=\mathcal{P}_A(\widehat{\mathbf{b}}^{(m)}), \qquad\widehat{\Delta}_{i,A}:=\Delta_{i,A}(\widehat{\mathbf{b}}^{(m)}), \qquad i\in A. \tag*{(5)} S A := P A ( b ( m ) ) , Δ i , A := Δ i , A ( b ( m ) ) , i ∈ A . (5) If all the estimated classification gaps in A A A max i ∈ A Δ ^ i , A ≤ C t h r r m \max_{i\in A}\widehat{\Delta}_{i,A}\le C_{\mathrm{thr}}r_m max i ∈ A Δ i , A ≤ C thr r m C t h r C_{\mathrm{thr}} C thr r m r_m r m i m ∈ arg max i ∈ A Δ ^ i , A i_m\in\arg\max_{i\in A}\widehat{\Delta}_{i,A} i m ∈ arg max i ∈ A Δ i , A A A A i m i_m i m m m m i m ∈ S ^ A i_m\in\widehat{S}_A i m ∈ S A B B B B ∪ A B\cup A B ∪ A m m m m + 1 m+1 m + 1
The sampling schedule and removal thresholds are chosen so that, with high probability, every model added to B B B m ≥ 1 m\ge1 m ≥ 1
ε m : = 2 − m , L m : = log C l o g K d m 2 δ , n m : = ⌈ C s a m p L m ε m 2 ⌉ , r m : = L m 2 n m , (6) \varepsilon_m:=2^{-m}, \qquad L_m:=\log\frac{C_{\mathrm{log}}Kdm^2}{\delta}, \qquad n_m:=\left\lceil\frac{C_{\mathrm{samp}}L_m}{\varepsilon_m^2}\right\rceil, \qquad r_m:=\sqrt{\frac{L_m}{2n_m}}, \tag*{(6)} ε m := 2 − m , L m := log δ C log K d m 2 , n m := ⌈ ε m 2 C samp L m ⌉ , r m := 2 n m L m , (6) where C = ( C s a m p , C t h r , C l o g ) C=(C_{\mathrm{samp}},C_{\mathrm{thr}},C_{\mathrm{log}}) C = ( C samp , C thr , C log )
C = ( C s a m p , C t h r , C l o g ) = ( 2 , 4 , 4 ) . (7) C=(C_{\mathrm{samp}},C_{\mathrm{thr}},C_{\mathrm{log}})=(2,4,4). \tag*{(7)} C = ( C samp , C thr , C log ) = ( 2 , 4 , 4 ) . (7) The complete procedure is summarized in Algorithm 1.
Remark 2.1 (Sampling and tie-breaking conventions). VB-EGE samples only active models as focal models, but draws each opponent uniformly from the full original set of models [ K ] ∖ { i } [K]\setminus\{i\} [ K ] ∖ { i } b i , r b_{i,r} b i , r Δ ^ i , A \widehat{\Delta}_{i,A} Δ i , A S ^ A \widehat{S}_A S A Lemma B.6 , this tie-breaking rule ensures that each active non-Pareto model i i i Δ i B \Delta_i^B Δ i B
Algorithm 1 Phased Vector-Borda Empirical-Gap Elimination VB-EGE( δ ; C ) (\delta;\mathcal{C}) ( δ ; C )
Require: number of candidate models K ≥ 2 K \ge2 K ≥ 2 d ≥ 1 d \ge1 d ≥ 1 δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) C = ( C s a m p , C t h r , C l o g ) ∈ ( 0 , ∞ ) 2 × [ 1 , ∞ ) \mathcal{C}=(C_{\mathrm{samp}},C_{\mathrm{thr}},C_{\mathrm{log}})\in(0,\infty)^2\times[1,\infty) C = ( C samp , C thr , C log ) ∈ ( 0 , ∞ ) 2 × [ 1 , ∞ )
Initialization: A ← [ K ] A\leftarrow[K] A ← [ K ] B ← ∅ B\leftarrow\varnothing B ← ∅ n 0 ← 0 n_0\leftarrow0 n 0 ← 0
for m = 1 , 2 , … m=1,2,\ldots m = 1 , 2 , … do
Set ε m , L m , n m , r m \varepsilon_m,L_m,n_m,r_m ε m , L m , n m , r m (6) .
for ( i , r ) ∈ A × [ d ] (i,r)\in A\times[d] ( i , r ) ∈ A × [ d ] do
Draw { Z i , r , s } s = n m − 1 + 1 n m \{Z_{i,r,s}\}_{s=n_{m-1}+1}^{n_m} { Z i , r , s } s = n m − 1 + 1 n m (4) , and compute b ^ i , r ( m ) ← 1 n m ∑ s = 1 n m Z i , r , s \widehat b_{i,r}^{(m)}\leftarrow\frac{1}{n_m}\sum_{s=1}^{n_m}Z_{i,r,s} b i , r ( m ) ← n m 1 ∑ s = 1 n m Z i , r , s
end for
Compute S ^ A \widehat S_A S A { Δ ^ i , A } i ∈ A \{\widehat\Delta_{i,A}\}_{i\in A} { Δ i , A } i ∈ A { b ^ i ( m ) : i ∈ A } \{\widehat b_i^{(m)}:i\in A\} { b i ( m ) : i ∈ A } (5) .
while ∣ A ∣ ≥ 2 |A|\ge2 ∣ A ∣ ≥ 2 max i ∈ A Δ ^ i , A > C t h r r m \max_{i\in A}\widehat\Delta_{i,A}>C_{\mathrm{thr}}r_m max i ∈ A Δ i , A > C thr r m do
G ← a r g m a x i ∈ A Δ ^ i , A G\leftarrow\mathop{\rm arg\,max}_{i\in A}\widehat\Delta_{i,A} G ← arg max i ∈ A Δ i , A
Choose i m ∈ G ∖ S ^ A i_m\in G\setminus\widehat S_A i m ∈ G ∖ S A G ∖ S ^ A ≠ ∅ G\setminus\widehat S_A\ne\varnothing G ∖ S A = ∅ i m ∈ G i_m\in G i m ∈ G
if i m ∈ S ^ A i_m\in\widehat S_A i m ∈ S A then
B ← B ∪ { i m } B\leftarrow B\cup\{i_m\} B ← B ∪ { i m }
end if
A ← A ∖ { i m } A\leftarrow A\setminus\{i_m\} A ← A ∖ { i m }
if ∣ A ∣ = 1 |A|=1 ∣ A ∣ = 1 then return B ∪ A B\cup A B ∪ A
Recompute S ^ A \widehat S_A S A { Δ ^ i , A } i ∈ A \{\widehat\Delta_{i,A}\}_{i\in A} { Δ i , A } i ∈ A A A A { b ^ i ( m ) : i ∈ A } \{\widehat b_i^{(m)}:i\in A\} { b i ( m ) : i ∈ A }
end while
end for
Theoretical guarantees
This section presents the theoretical guarantees for VB-EGE. Recall that, for any algorithm A A A τ A \tau_A τ A τ = τ A \tau=\tau_A τ = τ A
For B , Δ > 0 B,\Delta>0 B , Δ > 0
Θ B , d : = { θ ∈ ( R d ) K : max r ∈ [ d ] max i , j ∈ [ K ] ∣ θ i , r − θ j , r ∣ ≤ 2 B } . \Theta_{B,d}:=\left\{\theta\in(\mathbb{R}^{d})^K:\max_{r\in[d]}\max_{i,j\in[K]}|\theta_{i,r}-\theta_{j,r}|\le2B\right\}. Θ B , d := { θ ∈ ( R d ) K : r ∈ [ d ] max i , j ∈ [ K ] max ∣ θ i , r − θ j , r ∣ ≤ 2 B } . Θ B , d ( Δ ) : = { θ ∈ Θ B , d : min i ∈ [ K ] Δ i θ ≥ Δ } . \Theta_{B,d}(\Delta):=\left\{\theta\in\Theta_{B,d}:\min_{i\in[K]}\Delta_i^\theta\ge\Delta\right\}. Θ B , d ( Δ ) := { θ ∈ Θ B , d : i ∈ [ K ] min Δ i θ ≥ Δ } . We also write
κ B : = inf ∣ x ∣ ≤ 2 B σ ′ ( x ) = σ ( 2 B ) ( 1 − σ ( 2 B ) ) . \kappa_B:=\inf_{|x|\le2B}\sigma'(x)=\sigma(2B)(1-\sigma(2B)). κ B := ∣ x ∣ ≤ 2 B inf σ ′ ( x ) = σ ( 2 B ) ( 1 − σ ( 2 B )) . In what follows, § 3.1 establishes the δ \delta δ Θ B , d \Theta_{B,d} Θ B , d § 3.2 provides a worst-case lower bound over Θ B , d ( Δ ) \Theta_{B,d}(\Delta) Θ B , d ( Δ ) Θ B , d ( Δ ) \Theta_{B,d}(\Delta) Θ B , d ( Δ )
Upper bound
The following theorem establishes the δ \delta δ
Theorem 3.1 (Quantile upper bound). Fix B > 0 B>0 B > 0 θ ∈ Θ B , d \theta\in\Theta_{B,d} θ ∈ Θ B , d satisfying min i ∈ [ K ] Δ i θ > 0 \min_{i\in[K]}\Delta_i^\theta>0 min i ∈ [ K ] Δ i θ > 0 Define for each i ∈ [ K ] i\in[K] i ∈ [ K ]
M i θ : = 1 + ⌈ log 2 4 κ B Δ i θ ⌉ , L i θ ( δ ) : = log 4 K d ( M i θ ) 2 δ . M_i^\theta:=1+\left\lceil\log_2\frac{4}{\kappa_B\Delta_i^\theta}\right\rceil,\qquad L_i^\theta(\delta):=\log\frac{4Kd(M_i^\theta)^2}{\delta}. M i θ := 1 + ⌈ log 2 κ B Δ i θ 4 ⌉ , L i θ ( δ ) := log δ 4 K d ( M i θ ) 2 . Then VB-EGE (Algorithm 1) implemented with δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) C = ( 2 , 4 , 4 ) C=(2,4,4) C = ( 2 , 4 , 4 )
P θ ( P ^ = P ( θ ) , τ ≤ d K + 128 d κ B 2 ∑ i = 1 K L i θ ( δ ) ( Δ i θ ) 2 ) ≥ 1 − δ . \mathbb{P}_{\theta}\left(\widehat{\mathcal{P}}=\mathcal{P}(\theta),\ \tau\le dK+\frac{128d}{\kappa_{B}^{2}}\sum_{i=1}^{K}\frac{L_{i}^{\theta}(\delta)}{(\Delta_{i}^{\theta})^{2}}\right)\ge1-\delta. P θ ( P = P ( θ ) , τ ≤ d K + κ B 2 128 d i = 1 ∑ K ( Δ i θ ) 2 L i θ ( δ ) ) ≥ 1 − δ . Consequently, VB-EGE is δ \delta δ Θ B , d \Theta_{B,d} Θ B , d
Q θ , δ ( V B - E G E ) ≤ d K + 128 d κ B 2 ∑ i = 1 K L i θ ( δ ) ( Δ i θ ) 2 = O ~ ( d κ B 2 ∑ i = 1 K ( Δ i θ ) − 2 ) . Q_{\theta,\delta}(\mathrm{VB\text{-}EGE})\le dK+\frac{128d}{\kappa_{B}^{2}}\sum_{i=1}^{K}\frac{L_{i}^{\theta}(\delta)}{(\Delta_{i}^{\theta})^{2}}=\widetilde{O}\left(\frac{d}{\kappa_{B}^{2}}\sum_{i=1}^{K}(\Delta_{i}^{\theta})^{-2}\right). Q θ , δ ( VB - EGE ) ≤ d K + κ B 2 128 d i = 1 ∑ K ( Δ i θ ) 2 L i θ ( δ ) = O ( κ B 2 d i = 1 ∑ K ( Δ i θ ) − 2 ) . If B B B κ B \kappa_{B} κ B
The proof of Theorem 3.1 is provided in B.2.2, in which it first establishes exact recovery and finite stopping in Borda space, and then converts the bound to latent-score gaps.
Lower bound
We now turn to the lower bound on the sample complexity of any δ \delta δ Θ B , d ( Δ ) \Theta_{B,d}(\Delta) Θ B , d ( Δ ) ( 1 − δ ) (1-\delta) ( 1 − δ )
Q B , d ( Δ , δ ) : = inf A : δ -correct on Θ B , d ( Δ ) sup θ ∈ Θ B , d ( Δ ) Q θ , δ ( A ) . Q_{B,d}(\Delta,\delta):=\inf_{\mathcal{A}:\ \delta\text{-correct on }\Theta_{B,d}(\Delta)}\ \sup_{\theta\in\Theta_{B,d}(\Delta)} Q_{\theta,\delta}(\mathcal{A}). Q B , d ( Δ , δ ) := A : δ -correct on Θ B , d ( Δ ) inf θ ∈ Θ B , d ( Δ ) sup Q θ , δ ( A ) . Thus, Q B , d ( Δ , δ ) Q_{B,d}(\Delta,\delta) Q B , d ( Δ , δ ) ( 1 − δ ) (1-\delta) ( 1 − δ ) δ \delta δ Θ B , d ( Δ ) \Theta_{B,d}(\Delta) Θ B , d ( Δ ) Q B , d ( Δ , δ ) Q_{B,d}(\Delta,\delta) Q B , d ( Δ , δ )
Theorem 3.2 (Gap-separated minimax lower bound). Fix B > 0 B>0 B > 0 0 < Δ ≤ min { 1 , B } 0<\Delta\le\min\{1,B\} 0 < Δ ≤ min { 1 , B } 0 < δ < 1 / 3 0<\delta<1/3 0 < δ < 1/3
Q B , d ( Δ , δ ) ≥ d ( K − 1 ) Δ 2 kl ( 1 − 2 δ , δ ) . Q_{B,d}(\Delta,\delta)\ge\frac{d(K-1)}{\Delta^{2}}\operatorname{kl}(1-2\delta,\delta). Q B , d ( Δ , δ ) ≥ Δ 2 d ( K − 1 ) kl ( 1 − 2 δ , δ ) . The proof of Theorem 3.2 is deferred to Appendix § 7 .§ 2.3 . Here, we sketch the high-level idea: the proof considers the hard instance, where for some i ∈ [ K ] i\in[K] i ∈ [ K ]
θ i = ( 0 , … , 0 ) , θ j = ( − Δ , … , − Δ ) , ∀ j ∈ [ K ] ∖ { i } . (8) \theta_i=(0,\ldots,0),\qquad\theta_j=(-\Delta,\ldots,-\Delta),\qquad\forall j\in[K]\setminus\{i\}. \tag*{(8)} θ i = ( 0 , … , 0 ) , θ j = ( − Δ , … , − Δ ) , ∀ j ∈ [ K ] ∖ { i } . (8) Raising any model other than i i i + Δ +\Delta + Δ d ( K − 1 ) d(K-1) d ( K − 1 )
Finally, applying Theorem 3.1 with Δ i θ ≥ Δ \Delta_i^\theta\ge\Delta Δ i θ ≥ Δ i i i Theorem 3.2 yields the following minimax guarantee for fixed B B B
Corollary 3.3 (Gap-separated minimax optimality). Under the same assumptions as in Theorem 3.2 ,
Q B , d ( Δ , δ ) ≤ sup θ ∈ Θ B , d ( Δ ) Q θ , δ ( V B - E G E ) ≤ d K + 128 d K κ B 2 Δ 2 log 4 K d ( ⌈ log 2 8 κ B Δ ⌉ ) 2 δ . Q_{B,d}(\Delta,\delta)\le\sup_{\theta\in\Theta_{B,d}(\Delta)}Q_{\theta,\delta}(\mathrm{VB\text{-}EGE})\le dK+\frac{128dK}{\kappa_{B}^{2}\Delta^{2}}\log\frac{4Kd\left(\left\lceil\log_{2}\frac{8}{\kappa_{B}\Delta}\right\rceil\right)^{2}}{\delta}. Q B , d ( Δ , δ ) ≤ θ ∈ Θ B , d ( Δ ) sup Q θ , δ ( VB - EGE ) ≤ d K + κ B 2 Δ 2 128 d K log δ 4 K d ( ⌈ log 2 κ B Δ 8 ⌉ ) 2 . Consequently, for any fixed B > 0 B>0 B > 0
Q B , d ( Δ , δ ) = Θ ~ ( d K Δ 2 log 1 δ ) as δ ↓ 0 , Q_{B,d}(\Delta,\delta)=\widetilde{\Theta}\left(\frac{dK}{\Delta^{2}}\log\frac{1}{\delta}\right)\qquad\text{as }\delta\downarrow0, Q B , d ( Δ , δ ) = Θ ( Δ 2 d K log δ 1 ) as δ ↓ 0 , where Θ ~ \widetilde{\Theta} Θ K K K d d d Δ − 1 \Delta^{-1} Δ − 1
Experiments
This section evaluates the scaling and sample efficiency of VB-EGE on synthetic data, as well as its sample efficiency on logged Arena comparisons.
Synthetic experiments
In the scaling experiments, we generate data from the BT model corresponding to the hard instance in (8) and vary the values of K K K d d d Δ \Delta Δ δ \delta δ Convex , Arena , Witness , and Two-group , respectively. Details of the data-generating process in both experiments are provided in Appendix § 8 .§ 1 .
We compare VB-EGE with three baselines using uniform sampling:
Focal Borda. At each phase, the algorithm collects new observations for every model-objective pair ( i , r ) ∈ [ K ] × [ d ] (i, r) \in[K] \times[d] ( i , r ) ∈ [ K ] × [ d ] { n m } m ≥ 1 \{n_m\}_{m \ge1} { n m } m ≥ 1
BT-MLE. The algorithm uniformly samples from all d K ( K − 1 ) / 2 dK(K - 1)/2 d K ( K − 1 ) /2 , w h e r e $ 1 ≤ i < j ≤ K , where \$1 \le i < j \le K , w h er e $1 ≤ i < j ≤ K r ∈ [ d ] r \in[d] r ∈ [ d ]
Borda plug-in. The algorithm uses the same sampling rule as BT-MLE but estimates the Borda scores directly using smoothed empirical win rates, whose exact definition is given in Appendix § 8 .§ 2 . The stopping and Pareto certification rule follows from VB-EGE.
All methods use δ = 0.05 \delta= 0.05 δ = 0.05 C = ( 2 , 4 , 4 ) C = (2, 4, 4) C = ( 2 , 4 , 4 ) δ \delta δ Table 1 summarizes the parameter grids, with further implementation details in Appendix § 8 .§ 2 . Each experiment is repeated over 500 independent trials, and we report the mean stopping time, measured in objective-specific comparisons, and proportion of trials in which the Pareto set is incorrectly classified.
Table 1. Parameters used in the scaling experiments.
Results. Across all synthetic settings, we observe no errors in identifying the Pareto set. In Figure 2 a, the empirical log–log slopes of the mean stopping time with respect to K K K d d d Δ \Delta Δ log ( 1 / δ ) \log(1/\delta) log ( 1/ δ ) R 2 ≈ 0.99997 R^2 \approx0.99997 R 2 ≈ 0.99997
Figure 2. Mean stopping time (mean ± \pm ± K K K d d d Δ \Delta Δ log ( 1 / δ ) \log(1/\delta) log ( 1/ δ )
Figure 2 b shows the results from the eight heterogeneous benchmarks. VB-EGE achieves the lowest mean stopping cost in all settings. For each baseline, we compute the ratio between its mean stopping time and that of VB-EGE. Across the eight settings, the resulting ratio ranges from 1.25 to 111 for Focal Borda, from 1.79 to 261 for BT-MLE, and from 29.7 to 4.23 × 10 3 4.23 \times10^3 4.23 × 1 0 3 § 8 presents additional results and diagnostics.
Realistic Arena data experiments
We consider Arena-Human-Preference-140K (Arena-140K) [10 ] , Search-Arena-24K (Miroyan et al., 2026), and VisionArena-Battle [12 ] , treating the released task tags, search intents, and vision categories as objectives, respectively. Within each dataset, we retain only decisive comparisons—those in which either model is labeled the winner—and exclude the ties and “both bad” outcomes. We then select the largest subset of models such that every pair has at least one retained comparison for every objective. Additional preprocessing details are in Appendix § 9 .§ 1 .
For each model and objective, we compute a Borda score by averaging its logged win rates against all other retained models, and take the strict Pareto frontier of the resulting Borda vectors as the *empirical ground truth. For VB-EGE and Focal Borda, each query selects a focal model and an objective, then draws an opponent uniformly from the other retained models. BT-MLE and the Borda plug-in sample unordered pair–objective cells uniformly. A binary outcome is then drawn uniformly with replacement from the selected cell (see Appendix § 9 .§ 2 ). We evaluate VB-EGE and the three baseline methods described in § 4.1 , using δ = 0.05 \delta= 0.05 δ = 0.05 C = ( 2 , 4 , 4 ) C = (2, 4, 4) C = ( 2 , 4 , 4 )
Table 2. Main realistic Arena data settings. Rows are retained pair–objective records; the VisionArena-Battle records arise from 12,937 unique multi-label comparisons.
Results. Across all experiments, every method stopped and correctly identified the empirical Pareto frontier in every trial. Figure 2 c compares the mean stopping time, where VB-EGE achieves the lowest value on all three datasets. The ratio of mean stopping times (baseline/VB-EGE) ranges from 3.96 to 16.54 for Focal Borda, from 1.20 to 18.27 for BT-MLE, and from 15.20 to 301.36 for Borda plug-in. Additional results and discussion are provided in Appendix § 9 .§ 3 and Appendix § 9 .§ 4 .
Limitations and future work
This paper introduced a fixed-confidence adaptive sampling framework for identifying Pareto-optimal models from pairwise comparison. Several directions remain for future work. First, although our guarantees are stated under the BT model, the order-preservation property of the vector-Borda reduction requires only that the comparison probability be strictly increasing in the latent score difference. The reduction therefore applies more broadly to monotone comparison models. Second, our Bradley–Terry theory considers only decisive comparisons and does not model the tie and both_bad labels in Chatbot Arena [10 ] . Appendix § 9 .§ 4 empirically shows that the Borda-level guarantee extends to half-credit observations and uses a fitted Davidson construction to assess target sensitivity. A model-based treatment of non-decisive outcomes with a recovery guarantee for the population Pareto frontier remains open. Third, the Arena experiments use several forms of objective labeling, including mutually exclusive groups, primary-intent labels, and overlapping categories. An important open question is how sensitive the identified frontiers are to these choices. One extension is to allow soft or learned assignments, where each comparison context is associated with a mixture of capabilities.
Beyond VB-EGE, there are also several algorithmic directions worth investigating. For example, under the BT model, one could estimate the latent scores and guide sampling using likelihood-based methods. Appendix § 10 explores Pareto BT-GLR Track-and-Stop as a screened implementation of this approach, leaving a rigorous theoretical analysis for future work. Another promising direction is graph-aware sampling that exploits nonuniform historical support when selecting opponents and objectives. Such methods would be particularly relevant for larger, evolving arenas in which comparison coverage is uneven and new models are introduced over time.
Reproducibility
Code for reproducing the results in this paper is available at https://github.com/Twist-Shan/Beyond_Scalar_Leaderboards . Dataset links, pinned revisions, and preprocessing details are provided in Appendix § 9 .§ 1 .
AI Use Statement
In this work, we used generative AI tools (including ChatGPT 6 Astra, Claude Opus 5.5, etc.) for organizing the paper outline, polishing the writing, and structuring the appendices; searching for relevant literature; implementing synthetic-data generation and sampling from realistic Arena datasets; and, after the upper-bound proof had been established, searching for and assisting with the derivation of a matching lower bound. We have not used generative AI tools for designing the conceptual frameworks, proposing or refining hypotheses or interpreting results. We have reviewed all technical claims, proofs, experimental designs, implementations, and reported results. We take responsibility for the final content of this work, including text, claims or artifacts produced with the aid of generative AI.
Additional related work
Best arm identification Best-arm identification is a canonical pure-exploration problem in stochastic bandits, where samples are collected to identify an optimal arm rather than to maximize cumulative reward. Early work established PAC sample-complexity bounds and confidence-based elimination and stopping procedures for identifying a near-optimal arm [17 ] (Mannor & Tsitsiklis 2004). Subsequent work developed sharper procedures for best-arm identification under fixed-budget and fixed-confidence formulations, including Successive Rejects [3 ] , Sequential Halving (Karnin et al., 2013), and lil’UCB (Jamieson et al., 2014). Kaufmann et al. (2016) studied the instance-dependent complexity of the two dominant fixed-budget and fixed-confidence formulations, while Garivier & Kaufmann [20 ] derived a tight fixed-confidence lower bound and introduced the asymptotically optimal Track-and-Stop strategy. More recent work has developed alternative adaptive-allocation principles, notably Top-Two methods (Russo, 2020; Jourdan et al., 2022). Elimination strategies can further reduce the computational cost of fully adaptive fixed-confidence identification while preserving sample-complexity guarantees (Tirinzoni & Degenne, 2022).
Set-valued and structured identification. Beyond best-arm identification, bandit identification has been studied for richer terminal targets. Top-m m m [7 ] (Kaufmann & Kalyanakrishnan 2013), while thresholding and good-arm identification aim to determine which arms satisfy a prescribed performance criterion [11 ] (Locatelli et al. 2016). Combinatorial pure exploration generalizes the answer space to structured decision classes, including fixed-size subsets, matchings, spanning trees, and paths [9 ] , with recent work developing fixed-budget methods for more general real-valued combinatorial action classes (Nakamura & Sugiyama, 2024). Related extensions consider vector-valued observations and constrained decision spaces: Katz-Samuels & Scott (2018) study feasible-arm identification with multivariate means, while Carlsson et al. [8 ] consider fixed-confidence identification when the optimal policy is subject to linear constraints and may mix several arms. More generally, Degenne & Koolen [16 ] develop a fixed-confidence framework for pure-exploration problems that may admit multiple correct answers.
Technical proofs
Supporting results
Properties of the classification gaps
Lemma B.1 (Basic inequalities for pairwise margins). Let x = ( x 1 , … , x K ) x=(x_1,\ldots,x_K) x = ( x 1 , … , x K ) y = ( y 1 , … , y K ) ∈ ( R d ) K y=(y_1,\ldots,y_K) \in(\mathbb{R}^{d})^K y = ( y 1 , … , y K ) ∈ ( R d ) K i , j , k ∈ [ K ] i,j,k \in[K] i , j , k ∈ [ K ]
(i) m x ( i , k ) ≥ m x ( i , j ) + m x ( j , k ) m_x(i,k) \geq m_x(i,j) + m_x(j,k) m x ( i , k ) ≥ m x ( i , j ) + m x ( j , k )
(ii) if max u ∈ [ K ] max r ∈ [ d ] ∣ x u , r − y u , r ∣ ≤ ρ \max_{u\in[K]}\max_{r\in[d]} |x_{u,r}-y_{u,r}| \leq\rho max u ∈ [ K ] max r ∈ [ d ] ∣ x u , r − y u , r ∣ ≤ ρ
∣ m x ( i , j ) − m y ( i , j ) ∣ ≤ 2 ρ , ∣ M x ( i , j ) − M y ( i , j ) ∣ ≤ 2 ρ ; |m_x(i,j)-m_y(i,j)| \leq2\rho,\qquad|M_x(i,j)-M_y(i,j)| \leq2\rho; ∣ m x ( i , j ) − m y ( i , j ) ∣ ≤ 2 ρ , ∣ M x ( i , j ) − M y ( i , j ) ∣ ≤ 2 ρ ; (iii) for all a , b ∈ R a,b \in\mathbb{R} a , b ∈ R ∣ a + − b + ∣ ≤ ∣ a − b ∣ |a^{+}-b^{+}| \leq|a-b| ∣ a + − b + ∣ ≤ ∣ a − b ∣
Proof. For part (i), coordinate-wise,
x k , r − x i , r = ( x k , r − x j , r ) + ( x j , r − x i , r ) , x_{k,r}-x_{i,r}=(x_{k,r}-x_{j,r})+(x_{j,r}-x_{i,r}), x k , r − x i , r = ( x k , r − x j , r ) + ( x j , r − x i , r ) , Taking the minimum over r r r min r ( a r + b r ) ≥ min r a r + min r b r \min_r(a_r+b_r)\geq\min_r a_r+\min_r b_r min r ( a r + b r ) ≥ min r a r + min r b r
m x ( i , k ) ≥ m x ( i , j ) + m x ( j , k ) . m_x(i,k) \geq m_x(i,j) + m_x(j,k). m x ( i , k ) ≥ m x ( i , j ) + m x ( j , k ) . For part (ii), every coordinate difference satisfies
∣ ( x j , r − x i , r ) − ( y j , r − y i , r ) ∣ ≤ 2 ρ . |(x_{j,r}-x_{i,r})-(y_{j,r}-y_{i,r})| \leq2\rho. ∣ ( x j , r − x i , r ) − ( y j , r − y i , r ) ∣ ≤ 2 ρ . Both the minimum and maximum maps are 1-Lipschitz with respect to the ℓ ∞ \ell_\infty ℓ ∞
Part (iii) follows because the map a ↦ a + a \mapsto a^{+} a ↦ a +
Lemma B.2 (Pareto witness for a non-Pareto model). If i ∉ P ( x ) i \notin\mathcal{P}(x) i ∈ / P ( x )
Δ i ⋆ ( x ) = max p ∈ P ( x ) m x ( i , p ) > 0. \Delta_i^\star(x) = \max_{p \in\mathcal{P}(x)} m_x(i,p) > 0. Δ i ⋆ ( x ) = p ∈ P ( x ) max m x ( i , p ) > 0. In particular, there exists i x ⋆ ∈ P ( x ) i_x^\star\in\mathcal{P}(x) i x ⋆ ∈ P ( x ) m x ( i , i x ⋆ ) = Δ i ⋆ ( x ) m_x(i,i_x^\star) = \Delta_i^\star(x) m x ( i , i x ⋆ ) = Δ i ⋆ ( x )
Proof. Since i ∉ P ( x ) i \notin\mathcal{P}(x) i ∈ / P ( x ) i i i
Δ i ⋆ ( x ) = max j ∈ [ K ] ∖ { i } m x ( i , j ) > 0. \Delta_i^\star(x) = \max_{j \in[K]\setminus\{i\}} m_x(i,j) > 0. Δ i ⋆ ( x ) = j ∈ [ K ] ∖ { i } max m x ( i , j ) > 0. Because the model set is finite, we may choose i x ⋆ ∈ arg max j ∈ [ K ] ∖ { i } m x ( i , j ) i_x^\star\in\arg\max_{j \in[K]\setminus\{i\}} m_x(i,j) i x ⋆ ∈ arg max j ∈ [ K ] ∖ { i } m x ( i , j ) m x ( i , i x ⋆ ) = Δ i ⋆ ( x ) > 0 m_x(i,i_x^\star) = \Delta_i^\star(x) > 0 m x ( i , i x ⋆ ) = Δ i ⋆ ( x ) > 0 i ≺ x i x ⋆ i \prec_x i_x^\star i ≺ x i x ⋆
We claim that i x ⋆ ∈ P ( x ) i_x^\star\in\mathcal{P}(x) i x ⋆ ∈ P ( x ) p ∈ [ K ] p \in[K] p ∈ [ K ] i x ⋆ ≺ x p i_x^\star\prec_x p i x ⋆ ≺ x p m x ( i x ⋆ , p ) > 0 m_x(i_x^\star,p) > 0 m x ( i x ⋆ , p ) > 0
m x ( i , p ) ≥ m x ( i , i x ⋆ ) + m x ( i x ⋆ , p ) > m x ( i , i x ⋆ ) = Δ i ⋆ ( x ) . m_x(i,p) \ge m_x(i,i_x^\star) + m_x(i_x^\star,p) > m_x(i,i_x^\star) = \Delta_i^\star(x). m x ( i , p ) ≥ m x ( i , i x ⋆ ) + m x ( i x ⋆ , p ) > m x ( i , i x ⋆ ) = Δ i ⋆ ( x ) . This contradicts the definition of i x ⋆ i_x^\star i x ⋆ i x ⋆ ∈ P ( x ) i_x^\star\in\mathcal{P}(x) i x ⋆ ∈ P ( x ) j ≠ i j \ne i j = i p ∈ P ( x ) p \in\mathcal{P}(x) p ∈ P ( x )
For a Bradley–Terry instance θ ∈ Θ B , d \theta\in\Theta_{B,d} θ ∈ Θ B , d b = b ( θ ) b = b(\theta) b = b ( θ )
Δ i B : = Δ i ( b ( θ ) ) , Δ i θ : = Δ i ( θ ) . \Delta_i^{\mathrm{B}} := \Delta_i(b(\theta)), \qquad\Delta_i^\theta:= \Delta_i(\theta). Δ i B := Δ i ( b ( θ )) , Δ i θ := Δ i ( θ ) . Recall that
κ B = inf ∣ x ∣ ≤ 2 B σ ′ ( x ) = σ ( 2 B ) ( 1 − σ ( 2 B ) ) > 0. \kappa_B = \inf_{|x| \le2B} \sigma'(x) = \sigma(2B)(1-\sigma(2B)) > 0. κ B = ∣ x ∣ ≤ 2 B inf σ ′ ( x ) = σ ( 2 B ) ( 1 − σ ( 2 B )) > 0. Lemma B.3 (Borda gaps dominate latent gaps). If θ ∈ Θ B , d \theta\in\Theta_{B,d} θ ∈ Θ B , d i i i
Δ i B ≥ κ B Δ i θ . \Delta_i^{\mathrm{B}} \ge\kappa_B \Delta_i^\theta. Δ i B ≥ κ B Δ i θ . Proof. Fix models a a a c c c r r r u ∈ [ K ] u \in[K] u ∈ [ K ]
b ˉ u , r : = 1 K ∑ ℓ = 1 K σ ( θ u , r − θ ℓ , r ) . \bar{b}_{u,r} := \frac{1}{K}\sum_{\ell=1}^{K}\sigma(\theta_{u,r} - \theta_{\ell,r}). b ˉ u , r := K 1 ℓ = 1 ∑ K σ ( θ u , r − θ ℓ , r ) . For each ℓ \ell ℓ ξ ℓ \xi_\ell ξ ℓ θ a , r − θ ℓ , r \theta_{a,r} - \theta_{\ell,r} θ a , r − θ ℓ , r θ c , r − θ ℓ , r \theta_{c,r} - \theta_{\ell,r} θ c , r − θ ℓ , r
σ ( θ c , r − θ ℓ , r ) − σ ( θ a , r − θ ℓ , r ) = σ ′ ( ξ ℓ ) ( θ c , r − θ a , r ) . \sigma(\theta_{c,r} - \theta_{\ell,r}) - \sigma(\theta_{a,r} - \theta_{\ell,r}) = \sigma'(\xi_\ell)(\theta_{c,r} - \theta_{a,r}). σ ( θ c , r − θ ℓ , r ) − σ ( θ a , r − θ ℓ , r ) = σ ′ ( ξ ℓ ) ( θ c , r − θ a , r ) . Hence
b ˉ c , r − b ˉ a , r = γ a c r ( θ c , r − θ a , r ) , γ a c r : = 1 K ∑ ℓ = 1 K σ ′ ( ξ ℓ ) . \bar{b}_{c,r} - \bar{b}_{a,r} = \gamma_{acr}(\theta_{c,r} - \theta_{a,r}), \qquad\gamma_{acr} := \frac{1}{K}\sum_{\ell=1}^{K}\sigma'(\xi_\ell). b ˉ c , r − b ˉ a , r = γ a cr ( θ c , r − θ a , r ) , γ a cr := K 1 ℓ = 1 ∑ K σ ′ ( ξ ℓ ) . Because θ ∈ Θ B , d \theta\in\Theta_{B,d} θ ∈ Θ B , d ξ ℓ \xi_\ell ξ ℓ [ − 2 B , 2 B ] [-2B,2B] [ − 2 B , 2 B ] γ a c r ≥ κ B \gamma_{acr} \ge\kappa_B γ a cr ≥ κ B
b u , r = K b ˉ u , r − 1 / 2 K − 1 , b_{u,r} = \frac{K\bar{b}_{u,r} - 1/2}{K-1}, b u , r = K − 1 K b ˉ u , r − 1/2 , we obtain
b c , r − b a , r = K K − 1 γ a c r ( θ c , r − θ a , r ) . b_{c,r} - b_{a,r} = \frac{K}{K-1}\gamma_{acr}(\theta_{c,r} - \theta_{a,r}). b c , r − b a , r = K − 1 K γ a cr ( θ c , r − θ a , r ) . In particular, because K / ( K − 1 ) ≥ 1 K/(K-1) \ge1 K / ( K − 1 ) ≥ 1 θ c , r ≥ θ a , r \theta_{c,r} \ge\theta_{a,r} θ c , r ≥ θ a , r
b c , r − b a , r ≥ κ B ( θ c , r − θ a , r ) . (9) b_{c,r} - b_{a,r} \ge\kappa_B(\theta_{c,r} - \theta_{a,r}). \tag*{(9)} b c , r − b a , r ≥ κ B ( θ c , r − θ a , r ) . (9) We then record three consequences.
First, if m θ ( a , c ) > 0 m_\theta(a,c)>0 m θ ( a , c ) > 0 θ c , r − θ a , r \theta_{c,r}-\theta_{a,r} θ c , r − θ a , r (9) gives
m b ( a , c ) ≥ κ B m θ ( a , c ) . (10) m_b(a,c)\ge\kappa_B m_\theta(a,c). \tag*{(10)} m b ( a , c ) ≥ κ B m θ ( a , c ) . (10) Second, for all a , c a,c a , c
M b ( a , c ) + ≥ κ B M θ ( a , c ) + . (11) M_b(a,c)^+\ge\kappa_B M_\theta(a,c)^+. \tag*{(11)} M b ( a , c ) + ≥ κ B M θ ( a , c ) + . (11) If M θ ( a , c ) ≤ 0 M_\theta(a,c)\le0 M θ ( a , c ) ≤ 0 M θ ( a , c ) = θ a , r − θ c , r > 0 M_\theta(a,c)=\theta_{a,r}-\theta_{c,r}>0 M θ ( a , c ) = θ a , r − θ c , r > 0 (9) with the roles of a a a c c c
Third, for every model j j j
( Δ j ⋆ ( b ) ) + ≥ κ B ( Δ j ⋆ ( θ ) ) + . (12) \left(\Delta_j^\star(b)\right)^+\ge\kappa_B\left(\Delta_j^\star(\theta)\right)^+. \tag*{(12)} ( Δ j ⋆ ( b ) ) + ≥ κ B ( Δ j ⋆ ( θ ) ) + . (12) If Δ j ⋆ ( θ ) ≤ 0 \Delta_j^\star(\theta)\le0 Δ j ⋆ ( θ ) ≤ 0 c c c Δ j ⋆ ( θ ) > 0 \Delta_j^\star(\theta)>0 Δ j ⋆ ( θ ) > 0 (10) to ( j , c ) (j,c) ( j , c )
We now consider the two possible Pareto classes of model i i i
If i ∉ P ( θ ) i\notin P(\theta) i ∈ / P ( θ ) i ∉ P ( b ) i\notin P(b) i ∈ / P ( b ) c c c Δ i ⋆ ( θ ) > 0 \Delta_i^\star(\theta)>0 Δ i ⋆ ( θ ) > 0
Δ i B = Δ i ⋆ ( b ) ≥ m b ( i , c ) ≥ κ B m θ ( i , c ) = κ B Δ i θ . \Delta_i^{\mathrm{B}}=\Delta_i^\star(b)\ge m_b(i,c)\ge\kappa_Bm_\theta(i,c)=\kappa_B\Delta_i^\theta. Δ i B = Δ i ⋆ ( b ) ≥ m b ( i , c ) ≥ κ B m θ ( i , c ) = κ B Δ i θ . Suppose instead that i ∈ P ( θ ) i\in P(\theta) i ∈ P ( θ ) i ∈ P ( b ) i\in P(b) i ∈ P ( b ) j ≠ i j\ne i j = i i i i M θ ( i , j ) ≥ 0 M_\theta(i,j)\ge0 M θ ( i , j ) ≥ 0
If M θ ( i , j ) > 0 M_\theta(i,j)>0 M θ ( i , j ) > 0 (9) at an objective attaining the positive maximum gives
M b ( i , j ) ≥ κ B M θ ( i , j ) . M_b(i,j)\ge\kappa_B M_\theta(i,j). M b ( i , j ) ≥ κ B M θ ( i , j ) . If M θ ( i , j ) = 0 M_\theta(i,j)=0 M θ ( i , j ) = 0 θ i , r = θ j , r \theta_{i,r}=\theta_{j,r} θ i , r = θ j , r b i , r = b j , r b_{i,r}=b_{j,r} b i , r = b j , r M b ( i , j ) ≥ 0 = κ B M θ ( i , j ) M_b(i,j)\ge0=\kappa_BM_\theta(i,j) M b ( i , j ) ≥ 0 = κ B M θ ( i , j )
M b ( i , j ) ≥ κ B M θ ( i , j ) . M_b(i,j)\ge\kappa_B M_\theta(i,j). M b ( i , j ) ≥ κ B M θ ( i , j ) . Moreover, combining (11) and (12) gives
M b ( j , i ) + + ( Δ j ⋆ ( b ) ) + ≥ κ B [ M θ ( j , i ) + + ( Δ j ⋆ ( θ ) ) + ] . M_b(j,i)^++\left(\Delta_j^\star(b)\right)^+\ge\kappa_B\left[M_\theta(j,i)^++\left(\Delta_j^\star(\theta)\right)^+\right]. M b ( j , i ) + + ( Δ j ⋆ ( b ) ) + ≥ κ B [ M θ ( j , i ) + + ( Δ j ⋆ ( θ ) ) + ] . Therefore, for every j ≠ i j\ne i j = i
M b ( i , j ) ∧ [ M b ( j , i ) + + ( Δ j ⋆ ( b ) ) + ] ≥ κ B { M θ ( i , j ) ∧ [ M θ ( j , i ) + + ( Δ j ⋆ ( θ ) ) + ] } , M_b(i,j)\wedge\left[M_b(j,i)^++\left(\Delta_j^\star(b)\right)^+\right]\ge\kappa_B\left\{M_\theta(i,j)\wedge\left[M_\theta(j,i)^++\left(\Delta_j^\star(\theta)\right)^+\right]\right\}, M b ( i , j ) ∧ [ M b ( j , i ) + + ( Δ j ⋆ ( b ) ) + ] ≥ κ B { M θ ( i , j ) ∧ [ M θ ( j , i ) + + ( Δ j ⋆ ( θ ) ) + ] } , Taking the minimum over j ≠ i j\ne i j = i
Δ i B = δ i ⋆ ( b ) ≥ κ B δ i ⋆ ( θ ) = κ B Δ i θ . \Delta_i^{\mathrm{B}}=\delta_i^\star(b)\ge\kappa_B\delta_i^\star(\theta)=\kappa_B\Delta_i^\theta. Δ i B = δ i ⋆ ( b ) ≥ κ B δ i ⋆ ( θ ) = κ B Δ i θ . This proves the claim for every model i i i
High-probability analysis of VB-EGE
We first state the upper-bound argument for a generic vector-Bernoulli mean instance. Fix b = ( b 1 , … , b K ) ∈ ( [ 0 , 1 ] d ) K b=(b_1,\ldots,b_K)\in([0,1]^d)^K b = ( b 1 , … , b K ) ∈ ([ 0 , 1 ] d ) K i i i r r r
Z i , r , 1 , Z i , r , 2 , … ∼ i i d Bernoulli ( b i , r ) , i ∈ [ K ] , r ∈ [ d ] , Z_{i,r,1},Z_{i,r,2},\ldots\mathrel{\overset{\mathrm{iid}}{\sim}}\operatorname{Bernoulli}(b_{i,r}),\qquad i\in[K],\ r\in[d], Z i , r , 1 , Z i , r , 2 , … ∼ iid Bernoulli ( b i , r ) , i ∈ [ K ] , r ∈ [ d ] , These streams are independent of any additional internal randomization used by the algorithm.
Let P b \mathbb{P}_b P b
Δ i B : = Δ i ( b ) , P : = P ( b ) , Δ min B : = min i ∈ [ K ] Δ i B . \Delta_i^{\mathrm{B}}:=\Delta_i(b),\qquad\mathcal{P}:=P(b),\qquad\Delta_{\min}^{\mathrm{B}}:=\min_{i\in[K]}\Delta_i^{\mathrm{B}}. Δ i B := Δ i ( b ) , P := P ( b ) , Δ m i n B := i ∈ [ K ] min Δ i B . Throughout this section, Algorithm 1 is run with the common configuration C = ( 2 , 4 , 4 ) C=(2,4,4) C = ( 2 , 4 , 4 ) (7) . Let τ \tau τ τ = ∞ \tau=\infty τ = ∞ Δ min B > 0 \Delta_{\min}^{\mathrm{B}}>0 Δ m i n B > 0
M i : = 1 + ⌈ log 2 4 Δ i B ⌉ , L i ( δ ) : = log 4 K d M i 2 δ . M_i:=1+\left\lceil\log_2\frac{4}{\Delta_i^{\mathrm{B}}}\right\rceil,\qquad L_i(\delta):=\log\frac{4KdM_i^2}{\delta}. M i := 1 + ⌈ log 2 Δ i B 4 ⌉ , L i ( δ ) := log δ 4 K d M i 2 . Also define the ( 1 − δ ) (1-\delta) ( 1 − δ ) b b b
Q b , δ ( V B - E G E ) : = inf { T ∈ N 0 : P b ( τ ≤ T ) ≥ 1 − δ } , inf ∅ : = ∞ . Q_{b,\delta}(\mathrm{VB\text{-}EGE}):=\inf\left\{T\in\mathbb{N}_0:\mathbb{P}_b(\tau\le T)\ge1-\delta\right\},\qquad\inf\varnothing:=\infty. Q b , δ ( VB - EGE ) := inf { T ∈ N 0 : P b ( τ ≤ T ) ≥ 1 − δ } , inf ∅ := ∞. Proposition B.4 (VB-EGE guarantee under vector-Bernoulli feedback). If Δ min B > 0 \Delta_{\min}^{\mathrm{B}}>0 Δ m i n B > 0 C C C (7) , satisfies
P b ( P ^ = P ( b ) , τ ≤ d K + 128 d ∑ i = 1 K L i ( δ ) ( Δ i B ) 2 ) ≥ 1 − δ . (13) \mathbb{P}_{\mathrm{b}}\left(\widehat{\mathcal{P}}=\mathcal{P}(\mathrm{b}),\ \tau\le dK+128d\sum_{i=1}^{K}\frac{L_i(\delta)}{(\Delta_i^{\mathrm{B}})^2}\right)\ge1-\delta. \tag*{(13)} P b ( P = P ( b ) , τ ≤ d K + 128 d i = 1 ∑ K ( Δ i B ) 2 L i ( δ ) ) ≥ 1 − δ . (13) Consequently,
Q b , δ ( V B - E G E ) ≤ d K + 128 d ∑ i = 1 K L i ( δ ) ( Δ i B ) 2 = O ~ ( d ∑ i = 1 K ( Δ i B ) − 2 ) . Q_{\mathrm{b},\delta}(\mathrm{VB\text{-}EGE})\le dK+128d\sum_{i=1}^{K}\frac{L_i(\delta)}{(\Delta_i^{\mathrm{B}})^2}=\widetilde{O}\left(d\sum_{i=1}^{K}(\Delta_i^{\mathrm{B}})^{-2}\right). Q b , δ ( VB - EGE ) ≤ d K + 128 d i = 1 ∑ K ( Δ i B ) 2 L i ( δ ) = O ( d i = 1 ∑ K ( Δ i B ) − 2 ) . We first establish several lemmas used in the proof of Proposition B.4 . Under (7) , the phase schedule is
ε m = 2 − m , L m = log 4 K d m 2 δ , n m = ⌈ 2 L m ε m 2 ⌉ , r m = L m 2 n m , \varepsilon_m=2^{-m},\qquad L_m=\log\frac{4Kdm^2}{\delta},\qquad n_m=\left\lceil\frac{2L_m}{\varepsilon_m^2}\right\rceil,\qquad r_m=\sqrt{\frac{L_m}{2n_m}}, ε m = 2 − m , L m = log δ 4 K d m 2 , n m = ⌈ ε m 2 2 L m ⌉ , r m = 2 n m L m , and the removal threshold is 4 r m 4r_m 4 r m
For every phase m m m i i i r r r m m m
b ^ i , r ( m ) : = 1 n m ∑ s = 1 n m Z i , r , s . \widehat{b}_{i,r}^{(m)}:=\frac{1}{n_m}\sum_{s=1}^{n_m}Z_{i,r,s}. b i , r ( m ) := n m 1 s = 1 ∑ n m Z i , r , s . For an inactive model–objective pair, this quantity is used only in the analysis; the algorithm need not have revealed the corresponding prefix. At an inner-loop iteration with active set A A A
m ^ A ( i , j ) : = m b ^ ( m ) ( i , j ) , M ^ A ( i , j ) : = M b ^ ( m ) ( i , j ) , Δ ^ i , A ⋆ : = Δ i , A ⋆ ( b ^ ( m ) ) , δ ^ i , A ⋆ : = δ i , A ⋆ ( b ^ ( m ) ) . \widehat{m}_A(i,j):=m_{\widehat{\mathbf{b}}^{(m)}}(i,j),\qquad\widehat{M}_A(i,j):=M_{\widehat{\mathbf{b}}^{(m)}}(i,j),\qquad\widehat{\Delta}_{i,A}^{\star}:=\Delta_{i,A}^{\star}(\widehat{\mathbf{b}}^{(m)}),\qquad\widehat{\delta}_{i,A}^{\star}:=\delta_{i,A}^{\star}(\widehat{\mathbf{b}}^{(m)}). m A ( i , j ) := m b ( m ) ( i , j ) , M A ( i , j ) := M b ( m ) ( i , j ) , Δ i , A ⋆ := Δ i , A ⋆ ( b ( m ) ) , δ i , A ⋆ := δ i , A ⋆ ( b ( m ) ) . Lemma B.5 (Empirical gap identities). For every active set A ⊆ [ K ] A\subseteq[K] A ⊆ [ K ] ∣ A ∣ ≥ 2 |A|\ge2 ∣ A ∣ ≥ 2 i ∈ A i\in A i ∈ A
i ∈ S ^ A ⟺ Δ ^ i , A ⋆ ≤ 0 , i ∉ S ^ A ⟺ Δ ^ i , A ⋆ > 0. i\in\widehat{S}_A\iff\widehat{\Delta}_{i,A}^{\star}\le0,\qquad i\notin\widehat{S}_A\iff\widehat{\Delta}_{i,A}^{\star}>0. i ∈ S A ⟺ Δ i , A ⋆ ≤ 0 , i ∈ / S A ⟺ Δ i , A ⋆ > 0. and,
Δ ^ i , A = Δ ^ i , A ⋆ ∨ δ ^ i , A ⋆ . \widehat{\Delta}_{i,A}=\widehat{\Delta}_{i,A}^{\star}\vee\widehat{\delta}_{i,A}^{\star}. Δ i , A = Δ i , A ⋆ ∨ δ i , A ⋆ . Proof. By definition,
Δ ^ i , A ⋆ = max j ∈ A ∖ { i } m ^ A ( i , j ) . \widehat{\Delta}_{i,A}^{\star}=\max_{j\in A\setminus\{i\}}\widehat{m}_A(i,j). Δ i , A ⋆ = j ∈ A ∖ { i } max m A ( i , j ) . Hence i ∉ S ^ A i\notin\widehat{S}_A i ∈ / S A j ∈ A ∖ { i } j\in A\setminus\{i\} j ∈ A ∖ { i } m ^ A ( i , j ) > 0 \widehat{m}_A(i,j)>0 m A ( i , j ) > 0 Δ ^ i , A ⋆ > 0 \widehat{\Delta}_{i,A}^{\star}>0 Δ i , A ⋆ > 0
Suppose first that i ∈ S ^ A i\in\widehat{S}_A i ∈ S A Δ ^ i , A ⋆ ≤ 0 \widehat{\Delta}_{i,A}^{\star}\le0 Δ i , A ⋆ ≤ 0 j ∈ A ∖ { i } j\in A\setminus\{i\} j ∈ A ∖ { i } j j j i i i r ∈ [ d ] r\in[d] r ∈ [ d ] b ^ i , r ≥ b ^ j , r \widehat{b}_{i,r}\ge\widehat{b}_{j,r} b i , r ≥ b j , r
M ^ A ( i , j ) = max r ∈ [ d ] ( b ^ i , r − b ^ j , r ) ≥ 0. \widehat{M}_A(i,j)=\max_{r\in[d]}(\widehat{b}_{i,r}-\widehat{b}_{j,r})\ge0. M A ( i , j ) = r ∈ [ d ] max ( b i , r − b j , r ) ≥ 0. The other term, M ^ A ( j , i ) + + ( Δ ^ j , A ⋆ ) + \widehat{M}_A(j,i)^++(\widehat{\Delta}_{j,A}^{\star})^+ M A ( j , i ) + + ( Δ j , A ⋆ ) + δ ^ i , A ⋆ \widehat{\delta}_{i,A}^{\star} δ i , A ⋆ δ ^ i , A ⋆ ≥ 0 ≥ Δ ^ i , A ⋆ \widehat{\delta}_{i,A}^{\star}\ge0\ge\widehat{\Delta}_{i,A}^{\star} δ i , A ⋆ ≥ 0 ≥ Δ i , A ⋆
Δ ^ i , A ⋆ ∨ δ ^ i , A ⋆ = δ ^ i , A ⋆ = Δ ^ i , A . \widehat{\Delta}_{i,A}^{\star}\vee\widehat{\delta}_{i,A}^{\star}=\widehat{\delta}_{i,A}^{\star}=\widehat{\Delta}_{i,A}. Δ i , A ⋆ ∨ δ i , A ⋆ = δ i , A ⋆ = Δ i , A . Now suppose that i ∉ S ^ A i\notin\widehat{S}_A i ∈ / S A j ∈ A ∖ { i } j\in A\setminus\{i\} j ∈ A ∖ { i } m ^ A ( i , j ) > 0 \widehat{m}_A(i,j)>0 m A ( i , j ) > 0
M ^ A ( i , j ) = − m ^ A ( i , j ) < 0. \widehat{M}_A(i,j)=-\widehat{m}_A(i,j)<0. M A ( i , j ) = − m A ( i , j ) < 0. Using this j j j δ ^ i , A ⋆ \widehat{\delta}_{i,A}^{\star} δ i , A ⋆
δ ^ i , A ⋆ ≤ M ^ A ( i , j ) ∧ [ M ^ A ( j , i ) + + ( Δ ^ j , A ⋆ ) + ] = M ^ A ( i , j ) < 0 , \widehat{\delta}_{i,A}^{\star}\le\widehat{M}_A(i,j)\wedge\left[\widehat{M}_A(j,i)^++(\widehat{\Delta}_{j,A}^{\star})^+\right]
=\widehat{M}_A(i,j)<0, δ i , A ⋆ ≤ M A ( i , j ) ∧ [ M A ( j , i ) + + ( Δ j , A ⋆ ) + ] = M A ( i , j ) < 0 , because the second term in the wedge is nonnegative. Since Δ ^ i , A ⋆ > 0 \widehat{\Delta}^{\star}_{i,A} > 0 Δ i , A ⋆ > 0
Δ ^ i , A ⋆ ∨ δ ^ i , A ⋆ = Δ ^ i , A ⋆ = Δ ^ i , A . \widehat{\Delta}^{\star}_{i,A} \vee\widehat{\delta}^{\star}_{i,A} = \widehat{\Delta}^{\star}_{i,A} = \widehat{\Delta}_{i,A}. Δ i , A ⋆ ∨ δ i , A ⋆ = Δ i , A ⋆ = Δ i , A . This proves the claim.
Lemma B.6 (Uniform Borda concentration). Define
E : = { ∀ m ≥ 1 , ∀ i ∈ [ K ] , ∀ r ∈ [ d ] : ∣ b ^ i , r ( m ) − b i , r ∣ ≤ r m } . \mathcal{E} := \left\{\forall m \ge1,\ \forall i \in[K],\ \forall r \in[d] : \left|\widehat{b}^{(m)}_{i,r} - b_{i,r}\right| \le r_m\right\}. E := { ∀ m ≥ 1 , ∀ i ∈ [ K ] , ∀ r ∈ [ d ] : b i , r ( m ) − b i , r ≤ r m } . Then P b ( E ) ≥ 1 − δ \mathbb{P}_b(\mathcal{E}) \ge1 - \delta P b ( E ) ≥ 1 − δ Moreover, on E \mathcal{E} E for every phase m m m active set A A A and distinct i , j ∈ A i,j \in A i , j ∈ A
∣ m ^ A ( i , j ) − m b ( i , j ) ∣ ≤ 2 r m , ∣ M ^ A ( i , j ) − M b ( i , j ) ∣ ≤ 2 r m . (14) \left|\widehat{m}_A(i,j) - m_b(i,j)\right| \le2r_m,\qquad\left|\widehat{M}_A(i,j) - M_b(i,j)\right| \le2r_m. \tag*{(14)} ∣ m A ( i , j ) − m b ( i , j ) ∣ ≤ 2 r m , M A ( i , j ) − M b ( i , j ) ≤ 2 r m . (14) Proof. For a fixed triple ( i , r , m ) (i,r,m) ( i , r , m ) r m r_m r m
P b ( ∣ b ^ i , r ( m ) − b i , r ∣ > r m ) ≤ 2 exp ( − 2 n m r m 2 ) = 2 e − L m = δ 2 K d m 2 . \mathbb{P}_b\left(\left|\widehat{b}^{(m)}_{i,r} - b_{i,r}\right| > r_m\right) \le2\exp\left(-2nm r_m^2\right) = 2e^{-Lm} = \frac{\delta}{2Kdm^2}. P b ( b i , r ( m ) − b i , r > r m ) ≤ 2 exp ( − 2 nm r m 2 ) = 2 e − L m = 2 K d m 2 δ . Taking a union bound over i ∈ [ K ] i \in[K] i ∈ [ K ] r ∈ [ d ] r \in[d] r ∈ [ d ] m ≥ 1 m \ge1 m ≥ 1
P b ( E c ) ≤ δ 2 ∑ m = 1 ∞ 1 m 2 < δ . \mathbb{P}_b(\mathcal{E}^{c}) \le\frac{\delta}{2}\sum_{m=1}^{\infty}\frac{1}{m^2} < \delta. P b ( E c ) ≤ 2 δ m = 1 ∑ ∞ m 2 1 < δ . The two margin bounds follow from Lemma B.1 .
For every non-Pareto model i ∉ P i \notin\mathcal{P} i ∈ / P Lemma B.2 :
i ⋆ ∈ arg max p ∈ P m b ( i , p ) , m b ( i , i ⋆ ) = Δ i B > 0. i^{\star} \in\underset{p\in\mathcal{P}}{\arg\max}\ m_b(i,p),\qquad m_b(i,i^{\star}) = \Delta_i^{\mathrm{B}} > 0. i ⋆ ∈ p ∈ P arg max m b ( i , p ) , m b ( i , i ⋆ ) = Δ i B > 0. For an active set A A A
W ( A ) : = { ∀ i ∉ P , i ∈ A ⇒ i ⋆ ∈ A } . \mathrm{W}(A) := \left\{\forall i \notin\mathcal{P},\quad i \in A \Rightarrow i^{\star} \in A\right\}. W ( A ) := { ∀ i ∈ / P , i ∈ A ⇒ i ⋆ ∈ A } . Initially, W ( [ K ] ) \mathrm{W}([K]) W ([ K ])
Lemma B.7 (Every removed model is correctly classified). Assume that E \mathcal{E} E and W ( A ) \mathrm{W}(A) W ( A ) hold when a model i ∈ A i \in A i ∈ A is removed in phase m m m Then:
(i) if i ∉ S ^ A i \notin\widehat{S}_A i ∈ / S A then i ∉ P i \notin\mathcal{P} i ∈ / P
(ii) if i ∈ S ^ A i \in\widehat{S}_A i ∈ S A then i ∈ P i \in\mathcal{P} i ∈ P
Thus every model removed without acceptance is truly non-Pareto, while every accepted model is truly Pareto.
Proof. For simplicity, we write r = r m r = r_m r = r m
First suppose i ∉ S ^ A i \notin\widehat{S}_A i ∈ / S A i i i Δ ^ i , A > 4 r \widehat{\Delta}_{i,A} > 4r Δ i , A > 4 r Lemma B.5 , Δ ^ i , A = Δ ^ i , A ⋆ \widehat{\Delta}_{i,A} = \widehat{\Delta}^{\star}_{i,A} Δ i , A = Δ i , A ⋆ j ∈ A ∖ { i } j \in A \setminus\{i\} j ∈ A ∖ { i } m ^ A ( i , j ) > 4 r \widehat{m}_A(i,j) > 4r m A ( i , j ) > 4 r (14) ,
m b ( i , j ) ≥ m ^ A ( i , j ) − 2 r > 2 r > 0. m_b(i,j) \ge\widehat{m}_A(i,j) - 2r > 2r > 0. m b ( i , j ) ≥ m A ( i , j ) − 2 r > 2 r > 0. Hence i ≺ b j i \prec_b j i ≺ b j i ∉ P ( b ) = P i \notin\mathcal{P}(b) = \mathcal{P} i ∈ / P ( b ) = P
Now suppose i ∈ S ^ A i \in\widehat{S}_A i ∈ S A i ∉ P i \notin\mathcal{P} i ∈ / P i ⋆ ∈ A i^{\star} \in A i ⋆ ∈ A
m b ( i , i ⋆ ) = Δ i B > 0 , M b ( i , i ⋆ ) = − Δ i B . m_b(i,i^{\star}) = \Delta_i^{\mathrm{B}} > 0,\qquad M_b(i,i^{\star}) = -\Delta_i^{\mathrm{B}}. m b ( i , i ⋆ ) = Δ i B > 0 , M b ( i , i ⋆ ) = − Δ i B . If Δ i B > 2 r \Delta_i^{\mathrm{B}} > 2r Δ i B > 2 r (14) implies
m ^ A ( i , i ⋆ ) ≥ Δ i B − 2 r > 0 , \widehat{m}_A(i,i^{\star}) \ge\Delta_i^{\mathrm{B}} - 2r > 0, m A ( i , i ⋆ ) ≥ Δ i B − 2 r > 0 , contradicting i ∈ S ^ A i \in\widehat{S}_A i ∈ S A Δ i B ≤ 2 r \Delta_i^{\mathrm{B}} \le2r Δ i B ≤ 2 r
Since i ∈ S ^ A i \in\widehat{S}_A i ∈ S A Δ ^ i , A = δ ^ i , A ⋆ \widehat{\Delta}_{i,A}=\widehat{\delta}^{\star}_{i,A} Δ i , A = δ i , A ⋆ j = i ⋆ j=i^{\star} j = i ⋆
Δ ^ i , A ≤ M ^ A ( i , i ⋆ ) ∧ [ M ^ A ( i ⋆ , i ) + + ( Δ ^ i , A ⋆ ) + ] ≤ M ^ A ( i , i ⋆ ) ≤ M b ( i , i ⋆ ) + 2 r = − Δ i B + 2 r ≤ 2 r , \begin{aligned}
\widehat{\Delta}_{i,A}\le\widehat{M}_A(i,i^{\star})\wedge\left[\widehat{M}_A(i^{\star},i)^{+}+(\widehat{\Delta}^{\star}_{i,A})^{+}\right] \\
&\le\widehat{M}_A(i,i^{\star}) \\
&\le M_b(i,i^{\star})+2r \\
&=-\Delta^{\mathrm{B}}_i+2r\le2r,
\end{aligned} Δ i , A ≤ M A ( i , i ⋆ ) ∧ [ M A ( i ⋆ , i ) + + ( Δ i , A ⋆ ) + ] ≤ M A ( i , i ⋆ ) ≤ M b ( i , i ⋆ ) + 2 r = − Δ i B + 2 r ≤ 2 r , contradicting the removal condition Δ ^ i , A > 4 r \widehat{\Delta}_{i,A}>4r Δ i , A > 4 r i ∈ P i\in\mathcal{P} i ∈ P
Lemma B.8 (Witness-invariant preservation). Assume that E \mathcal{E} E W ( A ) \mathrm{W}(A) W ( A ) m m m A ′ A^{\prime} A ′ W ( A ′ ) \mathrm{W}(A^{\prime}) W ( A ′ ) Proof. Write r = r m r=r_m r = r m Lemma B.7 , the only possible way to violate the invariant is to remove a true Pareto model p ∈ P p\in\mathcal{P} p ∈ P i ∉ P i\notin\mathcal{P} i ∈ / P i ⋆ = p i^{\star}=p i ⋆ = p p , i ∈ A p,i\in A p , i ∈ A p p p Lemma B.7 implies that it cannot be empirically non-Pareto. Thus p ∈ S ^ A p\in\widehat{S}_A p ∈ S A
Δ ^ p , A = δ ^ p , A ⋆ > 4 r . (15) \widehat{\Delta}_{p,A}=\widehat{\delta}^{\star}_{p,A}>4r. \tag*{(15)} Δ p , A = δ p , A ⋆ > 4 r . (15) There are two cases to be considered.
Case 1: p p p i i i Then m ^ A ( i , p ) > 0 \widehat{m}_A(i,p)>0 m A ( i , p ) > 0 i ∉ S ^ A i\notin\widehat{S}_A i ∈ / S A Δ ^ i , A = Δ ^ i , A ⋆ > 0 \widehat{\Delta}_{i,A}=\widehat{\Delta}^{\star}_{i,A}>0 Δ i , A = Δ i , A ⋆ > 0
M ^ A ( i , p ) + = 0. \widehat{M}_A(i,p)^{+}=0. M A ( i , p ) + = 0. Taking j = i j=i j = i δ ^ p , A ⋆ \widehat{\delta}^{\star}_{p,A} δ p , A ⋆
Δ ^ p , A ≤ M ^ A ( i , p ) + + ( Δ ^ i , A ⋆ ) + = Δ ^ i , A . \widehat{\Delta}_{p,A}\le\widehat{M}_A(i,p)^{+}+(\widehat{\Delta}^{\star}_{i,A})^{+}=\widehat{\Delta}_{i,A}. Δ p , A ≤ M A ( i , p ) + + ( Δ i , A ⋆ ) + = Δ i , A . Since p p p G : = arg max u ∈ A Δ ^ u , A G:=\operatorname*{arg\,max}_{u\in A}\widehat{\Delta}_{u,A} G := arg max u ∈ A Δ u , A Δ ^ i , A > Δ ^ p , A \widehat{\Delta}_{i,A}>\widehat{\Delta}_{p,A} Δ i , A > Δ p , A p ∈ G p\in G p ∈ G i ∈ G ∖ S ^ A i\in G\setminus\widehat{S}_A i ∈ G ∖ S A p p p p p p
Case 2: p p p i i i Then m ^ A ( i , p ) ≤ 0 \widehat{m}_A(i,p)\le0 m A ( i , p ) ≤ 0
M ^ A ( i , p ) = − m ^ A ( i , p ) ≥ 0. \widehat{M}_A(i,p)=-\widehat{m}_A(i,p)\ge0. M A ( i , p ) = − m A ( i , p ) ≥ 0. Since M b ( i , p ) = − m b ( i , p ) = − Δ i B M_b(i,p)=-m_b(i,p)=-\Delta^{\mathrm{B}}_i M b ( i , p ) = − m b ( i , p ) = − Δ i B (14) gives
0 ≤ M ^ A ( i , p ) = M ^ A ( i , p ) + ≤ 2 r − Δ i B . 0\le\widehat{M}_A(i,p)=\widehat{M}_A(i,p)^{+}\le2r-\Delta^{\mathrm{B}}_i. 0 ≤ M A ( i , p ) = M A ( i , p ) + ≤ 2 r − Δ i B . So Δ i B ≤ 2 r \Delta^{\mathrm{B}}_i\le2r Δ i B ≤ 2 r q ∈ A ∖ { i } q\in A\setminus\{i\} q ∈ A ∖ { i }
m ^ A ( i , q ) ≤ m b ( i , q ) + 2 r ≤ Δ i B + 2 r , \widehat{m}_A(i,q)\le m_b(i,q)+2r\le\Delta^{\mathrm{B}}_i+2r, m A ( i , q ) ≤ m b ( i , q ) + 2 r ≤ Δ i B + 2 r , Therefore,
( Δ ^ i , A ⋆ ) + ≤ Δ i B + 2 r . (\widehat{\Delta}^{\star}_{i,A})^{+}\le\Delta^{\mathrm{B}}_i+2r. ( Δ i , A ⋆ ) + ≤ Δ i B + 2 r . Since p ∈ S ^ A p\in\widehat{S}_A p ∈ S A Δ ^ p , A = δ ^ p , A ⋆ \widehat{\Delta}_{p,A}=\widehat{\delta}^{\star}_{p,A} Δ p , A = δ p , A ⋆ j = i j=i j = i
Δ ^ p , A ≤ M ^ A ( p , i ) ∧ [ M ^ A ( i , p ) + + ( Δ ^ i , A ⋆ ) + ] \widehat{\Delta}_{p,A}\le\widehat{M}_A(p,i)\wedge\left[\widehat{M}_A(i,p)^{+}+(\widehat{\Delta}^{\star}_{i,A})^{+}\right] Δ p , A ≤ M A ( p , i ) ∧ [ M A ( i , p ) + + ( Δ i , A ⋆ ) + ] ≤ M ^ A ( i , p ) + + ( Δ ^ i , A ⋆ ) + \le\widehat{M}_A(i,p)^{+}+(\widehat{\Delta}^{\star}_{i,A})^{+} ≤ M A ( i , p ) + + ( Δ i , A ⋆ ) + ≤ ( 2 r − Δ i B ) + ( Δ i B + 2 r ) \le(2r-\Delta^{\mathrm{B}}_i)+(\Delta^{\mathrm{B}}_i+2r) ≤ ( 2 r − Δ i B ) + ( Δ i B + 2 r ) contradicting (15) . Hence the invariant is preserved.
Proposition B.9 (Correctness on the confidence event). On E \mathcal{E} E P ( b ) \mathcal{P}(b) P ( b )
Proof. The invariant holds initially and is preserved after every removal by Lemma B.8 . By induction over removals and Lemma B.7 , every model added to B B B P \mathcal{P} P B B B P \mathcal{P} P
If the algorithm stops with a singleton active set A = { a } A=\{a\} A = { a } a ∉ P a\notin\mathcal{P} a ∈ / P a ⋆ a^\star a ⋆ ∣ A ∣ = 1 |A|=1 ∣ A ∣ = 1 B ∪ A B\cup A B ∪ A P \mathcal{P} P B ∪ A B\cup A B ∪ A B ∪ A B\cup A B ∪ A P ( b ) \mathcal{P}(b) P ( b )
Lemma B.10 (Removal once the radius is small). Assume E \mathcal{E} E m m m i i i
r m < Δ i B 8 , r_m < \frac{\Delta_i^{\mathrm{B}}}{8}, r m < 8 Δ i B , then either the algorithm stops during phase m m m i i i
Proof. Write r = r m r=r_m r = r m i i i ∣ A ∣ ≥ 2 |A|\ge2 ∣ A ∣ ≥ 2 Lemma B.8 , the witness invariant W ( A ) W(A) W ( A )
If i ∉ P i\notin\mathcal{P} i ∈ / P i ⋆ i^\star i ⋆ (14) ,
m ^ A ( i , i ⋆ ) ≥ Δ i B − 2 r > 0. \widehat{m}_A(i,i^\star)\ge\Delta_i^{\mathrm{B}}-2r>0. m A ( i , i ⋆ ) ≥ Δ i B − 2 r > 0. Thus i ∉ S ^ A i\notin\widehat{\mathcal{S}}_A i ∈ / S A Lemma B.5 gives
Δ ^ i , A = Δ ^ i , A ⋆ ≥ Δ i B − 2 r > 6 r > 4 r . \widehat{\Delta}_{i,A}=\widehat{\Delta}_{i,A}^{\star}\ge\Delta_i^{\mathrm{B}}-2r>6r>4r. Δ i , A = Δ i , A ⋆ ≥ Δ i B − 2 r > 6 r > 4 r . Now suppose i ∈ P i\in\mathcal{P} i ∈ P Δ i B = δ i ⋆ ( b ) \Delta_i^{\mathrm{B}}=\delta_i^\star(b) Δ i B = δ i ⋆ ( b ) j ∈ A ∖ { i } j\in A\setminus\{i\} j ∈ A ∖ { i } Δ i B \Delta_i^{\mathrm{B}} Δ i B
M b ( i , j ) ≥ Δ i B , M b ( j , i ) + + ( Δ j ⋆ ( b ) ) + ≥ Δ i B . (16) M_b(i,j)\ge\Delta_i^{\mathrm{B}},\qquad M_b(j,i)^+ + \bigl(\Delta_j^\star(b)\bigr)^+ \ge\Delta_i^{\mathrm{B}}. \tag*{(16)} M b ( i , j ) ≥ Δ i B , M b ( j , i ) + + ( Δ j ⋆ ( b ) ) + ≥ Δ i B . (16) By (14) ,
M ^ A ( i , j ) ≥ Δ i B − 2 r > 0. \widehat{M}_A(i,j)\ge\Delta_i^{\mathrm{B}}-2r>0. M A ( i , j ) ≥ Δ i B − 2 r > 0. Thus no active model empirically strictly dominates i i i i ∈ S ^ A i\in\widehat{\mathcal{S}}_A i ∈ S A j ∈ A j\in A j ∈ A
( Δ ^ j , A ⋆ ) + ≥ ( Δ j ⋆ ( b ) ) + − 2 r . \bigl(\widehat{\Delta}_{j,A}^\star\bigr)^+\ge\bigl(\Delta_j^\star(b)\bigr)^+-2r. ( Δ j , A ⋆ ) + ≥ ( Δ j ⋆ ( b ) ) + − 2 r . Indeed, if j ∈ P j\in\mathcal{P} j ∈ P Δ j ⋆ ( b ) ≤ 0 \Delta_j^\star(b)\le0 Δ j ⋆ ( b ) ≤ 0 j ∉ P j\notin\mathcal{P} j ∈ / P j ⋆ j^\star j ⋆ A A A
Δ ^ j , A ⋆ = max q ∈ A ∖ { j } m ^ A ( j , q ) ≥ m ^ A ( j , j ⋆ ) ≥ m b ( j , j ⋆ ) − 2 r = Δ j ⋆ ( b ) − 2 r . \widehat{\Delta}_{j,A}^\star
=\max_{q\in A\setminus\{j\}}\widehat{m}_A(j,q)
\ge\widehat{m}_A(j,j^\star)
\ge m_b(j,j^\star)-2r
=\Delta_j^\star(b)-2r. Δ j , A ⋆ = q ∈ A ∖ { j } max m A ( j , q ) ≥ m A ( j , j ⋆ ) ≥ m b ( j , j ⋆ ) − 2 r = Δ j ⋆ ( b ) − 2 r . Since Δ j ⋆ ( b ) > 0 \Delta_j^\star(b)>0 Δ j ⋆ ( b ) > 0
( Δ ^ j , A ⋆ ) + ≥ ( Δ j ⋆ ( b ) ) + − 2 r . \bigl(\widehat{\Delta}_{j,A}^\star\bigr)^+\ge\bigl(\Delta_j^\star(b)\bigr)^+-2r. ( Δ j , A ⋆ ) + ≥ ( Δ j ⋆ ( b ) ) + − 2 r . Combining with (16) yields
M ^ A ( j , i ) + + ( Δ ^ j , A ⋆ ) + ≥ Δ i B − 4 r > 4 r . \widehat{M}_A(j,i)^+ + \bigl(\widehat{\Delta}_{j,A}^\star\bigr)^+
\ge\Delta_i^{\mathrm{B}}-4r>4r. M A ( j , i ) + + ( Δ j , A ⋆ ) + ≥ Δ i B − 4 r > 4 r . Together with M ^ A ( i , j ) ≥ Δ i B − 2 r \widehat{M}_A(i,j)\ge\Delta_i^{\mathrm{B}}-2r M A ( i , j ) ≥ Δ i B − 2 r δ ^ i , A ⋆ \widehat{\delta}_{i,A}^\star δ i , A ⋆ Δ i B − 4 r \Delta_i^{\mathrm{B}}-4r Δ i B − 4 r
Δ ^ i , A = δ ^ i , A ⋆ ≥ Δ i B − 4 r > 4 r . \widehat{\Delta}_{i,A}=\widehat{\delta}_{i,A}^\star\ge\Delta_i^{\mathrm{B}}-4r>4r. Δ i , A = δ i , A ⋆ ≥ Δ i B − 4 r > 4 r . In either case, as long as i i i ∣ A ∣ ≥ 2 |A|\ge2 ∣ A ∣ ≥ 2 i i i i i i
Proof of Proposition B.4 . By Lemma B.6, P b ( E ) ≥ 1 − δ \mathbb{P}_{b}(\mathcal{E}) \ge1-\delta P b ( E ) ≥ 1 − δ E \mathcal{E} E Proposition B.9 ; it remains to bound the query count.
For each model i i i
m i : = min { m ≥ 1 : ε m < Δ i B 4 } . m_i := \min\left\{m \ge1 : \varepsilon_m < \frac{\Delta_i^{\mathrm{B}}}{4}\right\}. m i := min { m ≥ 1 : ε m < 4 Δ i B } . This integer is well defined because ε m ↓ 0 \varepsilon_m \downarrow0 ε m ↓ 0 0 < Δ i B ≤ 1 0 < \Delta_i^{\mathrm{B}} \le1 0 < Δ i B ≤ 1 M b ( i , j ) ≤ 1 M_b(i,j) \le1 M b ( i , j ) ≤ 1 m i > 1 m_i > 1 m i > 1 m i m_i m i
ε m i − 1 ≥ Δ i B 4 , ε m i = 1 2 ε m i − 1 ≥ Δ i B 8 . \varepsilon_{m_i-1} \ge\frac{\Delta_i^{\mathrm{B}}}{4}, \qquad\varepsilon_{m_i} = \frac{1}{2}\varepsilon_{m_i-1} \ge\frac{\Delta_i^{\mathrm{B}}}{8}. ε m i − 1 ≥ 4 Δ i B , ε m i = 2 1 ε m i − 1 ≥ 8 Δ i B . On the other hand, the defining property of m i m_i m i
ε m i < Δ i B 4 . \varepsilon_{m_i} < \frac{\Delta_i^{\mathrm{B}}}{4}. ε m i < 4 Δ i B . Since n m ≥ 2 L m / ε m 2 n_m \ge2L_m/\varepsilon_m^2 n m ≥ 2 L m / ε m 2
r m = L m 2 n m ≤ ε m 2 . r_m = \sqrt{\frac{L_m}{2n_m}} \le\frac{\varepsilon_m}{2}. r m = 2 n m L m ≤ 2 ε m . Therefore
r m i < Δ i B 8 . r_{m_i} < \frac{\Delta_i^{\mathrm{B}}}{8}. r m i < 8 Δ i B . By Lemma B.10, if the algorithm reaches phase m i m_i m i i i i i i i i i i m i m_i m i
In particular, the algorithm stops after finitely many phases. Indeed, let
m ‾ : = max i ∈ [ K ] m i < ∞ . \overline{m} := \max_{i\in[K]}m_i < \infty. m := i ∈ [ K ] max m i < ∞. If the algorithm had not stopped by the end of phase m ‾ \overline{m} m m i m_i m i
Consequently, the algorithm stops by phase m ‾ \overline{m} m i i i m i m_i m i d d d n m i n_{m_i} n m i
τ ≤ d ∑ i = 1 K n m i . \tau\le d\sum_{i=1}^{K}n_{m_i}. τ ≤ d i = 1 ∑ K n m i . It remains to bound n m i n_{m_i} n m i ε m i ≥ Δ i B / 8 \varepsilon_{m_i} \ge\Delta_i^{\mathrm{B}}/8 ε m i ≥ Δ i B /8
n m i ≤ 1 + 2 ε m i 2 log 4 K d m i 2 δ ≤ 1 + 128 ( Δ i B ) 2 log 4 K d m i 2 δ . n_{m_i} \le1+\frac{2}{\varepsilon_{m_i}^{2}}\log\frac{4Kdm_i^2}{\delta}
\le1+\frac{128}{(\Delta_i^{\mathrm{B}})^2}\log\frac{4Kdm_i^2}{\delta}. n m i ≤ 1 + ε m i 2 2 log δ 4 K d m i 2 ≤ 1 + ( Δ i B ) 2 128 log δ 4 K d m i 2 . Furthermore, m i ≤ M i m_i \le M_i m i ≤ M i
ε M i = 2 − M i ≤ Δ i B 8 < Δ i B 4 . \varepsilon_{M_i}=2^{-M_i}\le\frac{\Delta_i^{\mathrm{B}}}{8}<\frac{\Delta_i^{\mathrm{B}}}{4}. ε M i = 2 − M i ≤ 8 Δ i B < 4 Δ i B . Consequently,
n m i ≤ 1 + 128 L i ( δ ) ( Δ i B ) 2 . n_{m_i}\le1+\frac{128L_i(\delta)}{(\Delta_i^{\mathrm{B}})^2}. n m i ≤ 1 + ( Δ i B ) 2 128 L i ( δ ) . Combining the preceding two displays gives
τ ≤ d K + 128 d ∑ i = 1 K L i ( δ ) ( Δ i B ) 2 . \tau\le dK+128d\sum_{i=1}^{K}\frac{L_i(\delta)}{(\Delta_i^{\mathrm{B}})^2}. τ ≤ d K + 128 d i = 1 ∑ K ( Δ i B ) 2 L i ( δ ) . Thus, on E \mathcal{E} E P ( b ) \mathcal{P}(b) P ( b ) P b ( E ) ≥ 1 − δ \mathbb{P}_b(\mathcal{E}) \ge1-\delta P b ( E ) ≥ 1 − δ (13) follows. The quantile statement follows directly from the definition of Q b , δ ( V B - E G E ) Q_{b,\delta}(\mathrm{VB\text{-}EGE}) Q b , δ ( VB - EGE )
Change-of-measure tools
Lemma B.11 (Monotonicity of binary relative entropy). Let
0 ≤ q ≤ b < a ≤ p ≤ 1. 0 \le q \le b < a \le p \le1. 0 ≤ q ≤ b < a ≤ p ≤ 1. Then
kl ( p , q ) ≥ kl ( a , b ) , \operatorname{kl}(p,q) \ge\operatorname{kl}(a,b), kl ( p , q ) ≥ kl ( a , b ) , where binary relative entropy is extended to the boundary by the usual conventions.
Proof. For p , q ∈ ( 0 , 1 ) p,q \in(0,1) p , q ∈ ( 0 , 1 )
∂ ∂ p kl ( p , q ) = log p ( 1 − q ) q ( 1 − p ) , \frac{\partial}{\partial p}\operatorname{kl}(p,q)=\log\frac{p(1-q)}{q(1-p)}, ∂ p ∂ kl ( p , q ) = log q ( 1 − p ) p ( 1 − q ) , which is positive whenever p > q p>q p > q
∂ ∂ q kl ( p , q ) = q − p q ( 1 − q ) , \frac{\partial}{\partial q}\operatorname{kl}(p,q)=\frac{q-p}{q(1-q)}, ∂ q ∂ kl ( p , q ) = q ( 1 − q ) q − p , which is negative whenever p > q p>q p > q kl ( p , q ) \operatorname{kl}(p,q) kl ( p , q ) p > q p>q p > q
Lemma B.12 (Logistic KL upper bound). For all x , y ∈ R x,y \in\mathbb{R} x , y ∈ R
kl ( σ ( x ) , σ ( y ) ) ≤ ( x − y ) 2 8 . \operatorname{kl}(\sigma(x),\sigma(y)) \le\frac{(x-y)^2}{8}. kl ( σ ( x ) , σ ( y )) ≤ 8 ( x − y ) 2 . Proof. The Bernoulli distribution with mean σ ( u ) \sigma(u) σ ( u ) A ( u ) = log ( 1 + e u ) A(u)=\log(1+e^u) A ( u ) = log ( 1 + e u ) A ′ ′ ( u ) = σ ( u ) ( 1 − σ ( u ) ) ≤ 1 / 4 A^{\prime\prime}(u)=\sigma(u)(1-\sigma(u))\le1/4 A ′′ ( u ) = σ ( u ) ( 1 − σ ( u )) ≤ 1/4 A A A 1 / 4 1/4 1/4
kl ( σ ( x ) , σ ( y ) ) = A ( y ) − A ( x ) − A ′ ( x ) ( y − x ) ≤ ( y − x ) 2 8 . \operatorname{kl}(\sigma(x),\sigma(y))=A(y)-A(x)-A^{\prime}(x)(y-x)\le\frac{(y-x)^2}{8}. kl ( σ ( x ) , σ ( y )) = A ( y ) − A ( x ) − A ′ ( x ) ( y − x ) ≤ 8 ( y − x ) 2 . For 1 ≤ i < j ≤ K 1 \le i<j \le K 1 ≤ i < j ≤ K r ∈ [ d ] r \in[d] r ∈ [ d ] u ∈ N 0 u \in\mathbb{N}_0 u ∈ N 0 u ≤ τ u \le\tau u ≤ τ
N i j , r p a i r ( u ) : = ∑ t = 1 u 1 { R t = r , { I t , J t } = { i , j } } . N^{\mathrm{pair}}_{ij,r}(u):=\sum_{t=1}^{u}\mathbb{1}\{R_t=r,\{I_t,J_t\}=\{i,j\}\}. N ij , r pair ( u ) := t = 1 ∑ u 1 { R t = r , { I t , J t } = { i , j }} . Thus N i j , r p a i r ( u ) N^{\mathrm{pair}}_{ij,r}(u) N ij , r pair ( u ) { i , j } \{i,j\} { i , j } r r r u u u i ∈ [ K ] i \in[K] i ∈ [ K ]
N i , r i n c ( u ) : = ∑ j < i N j i , r p a i r ( u ) + ∑ j > i N i j , r p a i r ( u ) . N^{\mathrm{inc}}_{i,r}(u):=\sum_{j<i}N^{\mathrm{pair}}_{ji,r}(u)+\sum_{j>i}N^{\mathrm{pair}}_{ij,r}(u). N i , r inc ( u ) := j < i ∑ N j i , r pair ( u ) + j > i ∑ N ij , r pair ( u ) . Lemma B.13 (Bounded-horizon transportation). Fix T ∈ N 0 T \in\mathbb{N}_0 T ∈ N 0 θ \theta θ λ \lambda λ G G G τ ∧ T \tau\wedge T τ ∧ T T T T
∑ r = 1 d ∑ 1 ≤ i < j ≤ K E θ [ N i j , r p a i r ( τ ∧ T ) ] kl ( p i j ( r ) ( θ ) , p i j ( r ) ( λ ) ) ≥ kl ( P θ ( G ) , P λ ( G ) ) . (17) \sum_{r=1}^{d}\sum_{1\le i<j\le K}\mathbb{E}_{\theta}\left[N^{\mathrm{pair}}_{ij,r}(\tau\wedge T)\right]\operatorname{kl}\left(p^{(r)}_{ij}(\theta),p^{(r)}_{ij}(\lambda)\right)\ge\operatorname{kl}\left(\mathbb{P}_{\theta}(G),\mathbb{P}_{\lambda}(G)\right). \tag*{(17)} r = 1 ∑ d 1 ≤ i < j ≤ K ∑ E θ [ N ij , r pair ( τ ∧ T ) ] kl ( p ij ( r ) ( θ ) , p ij ( r ) ( λ ) ) ≥ kl ( P θ ( G ) , P λ ( G ) ) . (17) Proof. Let P θ T \mathbb{P}_{\theta}^{T} P θ T P λ T \mathbb{P}_{\lambda}^{T} P λ T τ ∧ T \tau\wedge T τ ∧ T T T T
KL ( P θ T , P λ T ) = E θ [ ∑ t = 1 τ ∧ T kl ( p I t J t ( R t ) ( θ ) , p I t J t ( R t ) ( λ ) ) ] . \operatorname{KL}\left(\mathbb{P}_{\theta}^{T},\mathbb{P}_{\lambda}^{T}\right)=\mathbb{E}_{\theta}\left[\sum_{t=1}^{\tau\wedge T}\operatorname{kl}\left(p_{I_tJ_t}^{(R_t)}(\theta),p_{I_tJ_t}^{(R_t)}(\lambda)\right)\right]. KL ( P θ T , P λ T ) = E θ [ t = 1 ∑ τ ∧ T kl ( p I t J t ( R t ) ( θ ) , p I t J t ( R t ) ( λ ) ) ] . For a reverse-orientation query, p j i ( r ) = 1 − p i j ( r ) p_{ji}^{(r)}=1-p_{ij}^{(r)} p j i ( r ) = 1 − p ij ( r ) kl ( 1 − p , 1 − q ) = kl ( p , q ) \operatorname{kl}(1-p,1-q)=\operatorname{kl}(p,q) kl ( 1 − p , 1 − q ) = kl ( p , q ) (17) . Finally, applying data processing to the binary statistic 1 G \mathbf{1}_G 1 G
KL ( P θ T ∥ P λ T ) ≥ kl ( P θ ( G ) , P λ ( G ) ) , \operatorname{KL}\left(\mathbb{P}_{\theta}^{T}\mathbin\Vert\mathbb{P}_{\lambda}^{T}\right)\geq\operatorname{kl}\left(\mathbb{P}_{\theta}(G),\mathbb{P}_{\lambda}(G)\right), KL ( P θ T ∥ P λ T ) ≥ kl ( P θ ( G ) , P λ ( G ) ) , which proves the claim.
Proofs of main results
Proof of Lemma 2.1
Proof of Lemma 2.1. For every model u ∈ [ K ] u\in[K] u ∈ [ K ] r ∈ [ d ] r\in[d] r ∈ [ d ]
b ˉ u , r : = 1 K ∑ ℓ = 1 K σ ( θ u , r − θ ℓ , r ) . \bar{b}_{u,r}:=\frac{1}{K}\sum_{\ell=1}^{K}\sigma(\theta_{u,r}-\theta_{\ell,r}). b ˉ u , r := K 1 ℓ = 1 ∑ K σ ( θ u , r − θ ℓ , r ) . Since σ ( 0 ) = 1 / 2 \sigma(0)=1/2 σ ( 0 ) = 1/2
b u , r = K b ˉ u , r − 1 / 2 K − 1 . b_{u,r}=\frac{K\bar{b}_{u,r}-1/2}{K-1}. b u , r = K − 1 K b ˉ u , r − 1/2 . In particular, b u , r b_{u,r} b u , r b ˉ u , r \bar{b}_{u,r} b ˉ u , r
Fix i , j ∈ [ K ] i,j\in[K] i , j ∈ [ K ] r ∈ [ d ] r\in[d] r ∈ [ d ] θ i , r > θ j , r \theta_{i,r}>\theta_{j,r} θ i , r > θ j , r ℓ ∈ [ K ] \ell\in[K] ℓ ∈ [ K ]
θ i , r − θ ℓ , r > θ j , r − θ ℓ , r . \theta_{i,r}-\theta_{\ell,r}>\theta_{j,r}-\theta_{\ell,r}. θ i , r − θ ℓ , r > θ j , r − θ ℓ , r . Because the logistic function is strictly increasing,
σ ( θ i , r − θ ℓ , r ) > σ ( θ j , r − θ ℓ , r ) for every ℓ ∈ [ K ] . \sigma(\theta_{i,r}-\theta_{\ell,r})>\sigma(\theta_{j,r}-\theta_{\ell,r})\qquad\text{for every }\ell\in[K]. σ ( θ i , r − θ ℓ , r ) > σ ( θ j , r − θ ℓ , r ) for every ℓ ∈ [ K ] . Averaging over ℓ \ell ℓ b ˉ i , r > b ˉ j , r \bar{b}_{i,r}>\bar{b}_{j,r} b ˉ i , r > b ˉ j , r b i , r > b j , r b_{i,r}>b_{j,r} b i , r > b j , r
Exchanging i i i j j j θ i , r < θ j , r \theta_{i,r}<\theta_{j,r} θ i , r < θ j , r b i , r < b j , r b_{i,r}<b_{j,r} b i , r < b j , r θ i , r = θ j , r \theta_{i,r}=\theta_{j,r} θ i , r = θ j , r b ˉ i , r \bar{b}_{i,r} b ˉ i , r b ˉ j , r \bar{b}_{j,r} b ˉ j , r ℓ \ell ℓ b i , r = b j , r b_{i,r}=b_{j,r} b i , r = b j , r
sign ( b i , r − b j , r ) = sign ( θ i , r − θ j , r ) , \operatorname{sign}(b_{i,r}-b_{j,r})=\operatorname{sign}(\theta_{i,r}-\theta_{j,r}), sign ( b i , r − b j , r ) = sign ( θ i , r − θ j , r ) , which proves (2) .
Applying the sign identity coordinate-wise gives
θ i , r < θ j , r for all r ∈ [ d ] ⟺ b i , r < b j , r for all r ∈ [ d ] . \theta_{i,r}<\theta_{j,r}\text{ for all }r\in[d]\quad\Longleftrightarrow\quad b_{i,r}<b_{j,r}\text{ for all }r\in[d]. θ i , r < θ j , r for all r ∈ [ d ] ⟺ b i , r < b j , r for all r ∈ [ d ] . Hence i ≺ θ j i\prec_{\theta}j i ≺ θ j i ≺ b j i\prec_{b}j i ≺ b j
P ( b ) = P ( θ ) = P ⋆ , \mathcal{P}(b)=\mathcal{P}(\theta)=\mathcal{P}^{\star}, P ( b ) = P ( θ ) = P ⋆ , which proves (3) .
Proof of Theorem 3.1
Proof of Theorem 3.1. Conditional on F t − 1 \mathcal{F}_{t-1} F t − 1 ( I t , R t ) = ( i , r ) (I_t,R_t)=(i,r) ( I t , R t ) = ( i , r ) J t J_t J t [ K ] ∖ { i } [K]\setminus\{i\} [ K ] ∖ { i } (1) ,
P θ ( Y t = 1 ∣ F t − 1 , I t = i , R t = r ) = 1 K − 1 ∑ j ≠ i p i j ( r ) ( θ ) = b i , r ( θ ) . \mathbb{P}_{\theta}(Y_t=1\mid\mathcal{F}_{t-1},I_t=i,R_t=r)=\frac{1}{K-1}\sum_{j\ne i}p_{ij}^{(r)}(\theta)=b_{i,r}(\theta). P θ ( Y t = 1 ∣ F t − 1 , I t = i , R t = r ) = K − 1 1 j = i ∑ p ij ( r ) ( θ ) = b i , r ( θ ) . Since the opponent and comparison randomness are fresh at every query, the oracle can be realized by mutually independent pre-generated streams
Z i , r , 1 , Z i , r , 2 , … ∼ i i d Bernoulli ( b i , r ( θ ) ) , Z_{i,r,1},Z_{i,r,2},\ldots\overset{\mathrm{iid}}{\sim}\operatorname{Bernoulli}(b_{i,r}(\theta)), Z i , r , 1 , Z i , r , 2 , … ∼ iid Bernoulli ( b i , r ( θ )) , revealing the next unused observation whenever the algorithm queries ( i , r ) (i,r) ( i , r ) Proposition B.4 applies with b = b ( θ ) b=b(\theta) b = b ( θ ) P θ \mathbb{P}_{\theta} P θ
P ( b ( θ ) ) = P ( θ ) . \mathcal{P}(b(\theta))=\mathcal{P}(\theta). P ( b ( θ )) = P ( θ ) . Let M i M_i M i L i ( δ ) L_i(\delta) L i ( δ ) § 7 .§ 1.2 . By Lemma B.3 , Δ i B ≥ κ B Δ i θ \Delta_i^B\ge\kappa_B\Delta_i^\theta Δ i B ≥ κ B Δ i θ
M i = 1 + ⌈ log 2 4 Δ i B ⌉ ≤ 1 + ⌈ log 2 4 κ B Δ i θ ⌉ = M i θ . M_i=1+\left\lceil\log_2\frac{4}{\Delta_i^B}\right\rceil\le1+\left\lceil\log_2\frac{4}{\kappa_B\Delta_i^\theta}\right\rceil=M_i^\theta. M i = 1 + ⌈ log 2 Δ i B 4 ⌉ ≤ 1 + ⌈ log 2 κ B Δ i θ 4 ⌉ = M i θ . It follows that L i ( δ ) ≤ L i θ ( δ ) L_i(\delta)\le L_i^\theta(\delta) L i ( δ ) ≤ L i θ ( δ )
L i ( δ ) ( Δ i B ) 2 ≤ L i θ ( δ ) κ B 2 ( Δ i θ ) 2 . \frac{L_i(\delta)}{(\Delta_i^B)^2}\le\frac{L_i^\theta(\delta)}{\kappa_B^2(\Delta_i^\theta)^2}. ( Δ i B ) 2 L i ( δ ) ≤ κ B 2 ( Δ i θ ) 2 L i θ ( δ ) . Substituting this inequality into (13) , with b = b ( θ ) b=b(\theta) b = b ( θ )
P θ ( P ^ = P ( θ ) , τ ≤ d K + 128 d κ B 2 ∑ i = 1 K L i θ ( δ ) ( Δ i θ ) 2 ) ≥ 1 − δ . \mathbb{P}_{\theta}\left(\widehat{\mathcal{P}}=\mathcal{P}(\theta),\quad\tau\le dK+\frac{128d}{\kappa_B^2}\sum_{i=1}^{K}\frac{L_i^\theta(\delta)}{(\Delta_i^\theta)^2}\right)\ge1-\delta. P θ ( P = P ( θ ) , τ ≤ d K + κ B 2 128 d i = 1 ∑ K ( Δ i θ ) 2 L i θ ( δ ) ) ≥ 1 − δ . The displayed event gives the stated bound on Q θ , δ ( V B - E G E ) Q_{\theta,\delta}(\mathrm{VB\text{-}EGE}) Q θ , δ ( VB - EGE ) L i θ ( δ ) L_i^\theta(\delta) L i θ ( δ ) O ~ \widetilde{O} O B B B B = O ( 1 ) B=O(1) B = O ( 1 ) κ B \kappa_B κ B κ B = Θ ( 1 ) \kappa_B=\Theta(1) κ B = Θ ( 1 )
Proof of Theorem 3.2
We first establish a quantile lower bound for a symmetric instance and then apply it to the gap-separated class.
Fix Δ > 0 \Delta>0 Δ > 0 θ Δ \theta^\Delta θ Δ
θ 1 , r Δ = 0 , θ i , r Δ = − Δ , i ∈ { 2 , … , K } , r ∈ [ d ] . \theta_{1,r}^\Delta=0,\qquad\theta_{i,r}^\Delta=-\Delta,\qquad i\in\{2,\ldots,K\},\ r\in[d]. θ 1 , r Δ = 0 , θ i , r Δ = − Δ , i ∈ { 2 , … , K } , r ∈ [ d ] . The first model strictly dominates every other model, and hence P ( θ Δ ) = { 1 } \mathcal{P}(\theta^\Delta)=\{1\} P ( θ Δ ) = { 1 }
To obtain a lower bound, we construct alternatives under which one of the dominated models becomes Pareto. For i ∈ { 2 , … , K } i\in\{2,\ldots,K\} i ∈ { 2 , … , K } r ∈ [ d ] r\in[d] r ∈ [ d ] η > 0 \eta>0 η > 0
λ a , s i , r , η : = { η , ( a , s ) = ( i , r ) , θ a , s Δ , otherwise . \lambda_{a,s}^{i,r,\eta}:=
\begin{cases}
\eta, & (a,s)=(i,r),\\
\theta_{a,s}^\Delta, & \text{otherwise}.
\end{cases} λ a , s i , r , η := { η , θ a , s Δ , ( a , s ) = ( i , r ) , otherwise . The alternative changes only the i i i r r r − Δ -\Delta − Δ η > 0 \eta>0 η > 0 i i i λ i , r , η \lambda^{i,r,\eta} λ i , r , η P ( λ i , r , η ) ≠ P ( θ Δ ) \mathcal{P}(\lambda^{i,r,\eta})\ne\mathcal{P}(\theta^\Delta) P ( λ i , r , η ) = P ( θ Δ )
The parameter η \eta η 0 0 0 η \eta η Δ + η \Delta+\eta Δ + η
Lemma B.14 (Quantile lower bound). Let δ ∈ ( 0 , 1 / 2 ) \delta\in(0,1/2) δ ∈ ( 0 , 1/2 ) A A A δ \delta δ C \mathcal{C} C θ Δ \theta^\Delta θ Δ η ˉ > 0 \bar{\eta}>0 η ˉ > 0 i ∈ { 2 , … , K } i \in\{2,\ldots,K\} i ∈ { 2 , … , K } r ∈ [ d ] r \in[d] r ∈ [ d ] C \mathcal{C} C λ i , r , η i , r \lambda^{i,r,\eta_{i,r}} λ i , r , η i , r 0 < η i , r ≤ η ˉ 0<\eta_{i,r}\leq\bar{\eta} 0 < η i , r ≤ η ˉ α ∈ ( 0 , 1 − 2 δ ) \alpha\in(0,1-2\delta) α ∈ ( 0 , 1 − 2 δ )
Q θ Δ , α ( A ) ≥ 4 d ( K − 1 ) ( Δ + η ˉ ) 2 kl ( 1 − δ − α , δ ) . Q_{\theta^\Delta,\alpha}(A) \geq\frac{4d(K-1)}{(\Delta+\bar{\eta})^2}\operatorname{kl}(1-\delta-\alpha,\delta). Q θ Δ , α ( A ) ≥ ( Δ + η ˉ ) 2 4 d ( K − 1 ) kl ( 1 − δ − α , δ ) . If, moreover, arbitrarily small frontier-changing perturbations are admissible, namely, for every i ∈ { 2 , … , K } i \in\{2,\ldots,K\} i ∈ { 2 , … , K } r ∈ [ d ] r \in[d] r ∈ [ d ] η n i , r ↓ 0 \eta_n^{i,r}\downarrow0 η n i , r ↓ 0 λ i , r , η n i , r ∈ C \lambda^{i,r,\eta_n^{i,r}}\in\mathcal{C} λ i , r , η n i , r ∈ C n n n
Q θ Δ , α ( A ) ≥ 4 d ( K − 1 ) Δ 2 kl ( 1 − δ − α , δ ) . Q_{\theta^\Delta,\alpha}(A) \geq\frac{4d(K-1)}{\Delta^2}\operatorname{kl}(1-\delta-\alpha,\delta). Q θ Δ , α ( A ) ≥ Δ 2 4 d ( K − 1 ) kl ( 1 − δ − α , δ ) . In particular, if α = δ < 1 / 3 \alpha=\delta<1/3 α = δ < 1/3
Q θ Δ , δ ( A ) ≥ 4 d ( K − 1 ) Δ 2 kl ( 1 − 2 δ , δ ) = Ω ( d K Δ 2 log 1 δ ) as δ ↓ 0. Q_{\theta^\Delta,\delta}(A) \geq\frac{4d(K-1)}{\Delta^2}\operatorname{kl}(1-2\delta,\delta)
= \Omega\left(\frac{dK}{\Delta^2}\log\frac{1}{\delta}\right)
\qquad\text{as }\delta\downarrow0. Q θ Δ , δ ( A ) ≥ Δ 2 4 d ( K − 1 ) kl ( 1 − 2 δ , δ ) = Ω ( Δ 2 d K log δ 1 ) as δ ↓ 0. The lower bound holds under the full adaptive ordered-pair oracle of § 1.1 , and therefore also applies to the uniform-opponent implementation used by VB-EGE. The proof uses a bounded-horizon change-of-measure argument (Kaufmann et al., 2016, Lemma 1).
Proof of Lemma B.14. It suffices to lower-bound every finite T T T
P θ Δ ( τ ≤ T ) ≥ 1 − α . (18) \mathbb{P}_{\theta^\Delta}(\tau\leq T)\geq1-\alpha. \tag*{(18)} P θ Δ ( τ ≤ T ) ≥ 1 − α . (18) If no such T T T
Fix a suboptimal model i ∈ { 2 , … , K } i\in\{2,\ldots,K\} i ∈ { 2 , … , K } r ∈ [ d ] r\in[d] r ∈ [ d ] η > 0 \eta>0 η > 0 θ Δ \theta^\Delta θ Δ P ( θ Δ ) = { 1 } \mathcal{P}(\theta^\Delta)=\{1\} P ( θ Δ ) = { 1 } λ i , r , η \lambda^{i,r,\eta} λ i , r , η i i i λ i , r i , r , η = η > 0 = λ 1 , r i , r , η \lambda^{i,r,\eta}_{i,r}=\eta>0=\lambda^{i,r,\eta}_{1,r} λ i , r i , r , η = η > 0 = λ 1 , r i , r , η i i i r r r η \eta η i i i
P ( λ i , r , η ) ≠ { 1 } = P ( θ Δ ) . (19) \mathcal{P}(\lambda^{i,r,\eta})\ne\{1\}=\mathcal{P}(\theta^\Delta). \tag*{(19)} P ( λ i , r , η ) = { 1 } = P ( θ Δ ) . (19) Consider the stopped event G T : = { τ ≤ T , P ^ = { 1 } } G_T:=\{\tau\leq T,\widehat{\mathcal{P}}=\{1\}\} G T := { τ ≤ T , P = { 1 }}
By δ \delta δ (18) ,
P θ Δ ( G T ) ≥ 1 − δ − α . \mathbb{P}_{\theta^\Delta}(G_T)\geq1-\delta-\alpha. P θ Δ ( G T ) ≥ 1 − δ − α . By (19) , outputting { 1 } \{1\} { 1 } λ i , r , η \lambda^{i,r,\eta} λ i , r , η
P λ i , r , η ( G T ) ≤ δ . \mathbb{P}_{\lambda^{i,r,\eta}}(G_T)\leq\delta. P λ i , r , η ( G T ) ≤ δ . Since
P θ Δ ( G T ) ≥ 1 − δ − α > δ ≥ P λ i , r , η ( G T ) , \mathbb{P}_{\theta^\Delta}(G_T)\geq1-\delta-\alpha>\delta\geq\mathbb{P}_{\lambda^{i,r,\eta}}(G_T), P θ Δ ( G T ) ≥ 1 − δ − α > δ ≥ P λ i , r , η ( G T ) , Lemma B.11 yields
kl ( P θ Δ ( G T ) , P λ i , r , η ( G T ) ) ≥ ℓ δ , α h p : = kl ( 1 − δ − α , δ ) . (20) \operatorname{kl}\left(\mathbb{P}_{\theta^\Delta}(G_T),\mathbb{P}_{\lambda^{i,r,\eta}}(G_T)\right)
\geq\ell^{\mathrm{hp}}_{\delta,\alpha}:=\operatorname{kl}(1-\delta-\alpha,\delta). \tag*{(20)} kl ( P θ Δ ( G T ) , P λ i , r , η ( G T ) ) ≥ ℓ δ , α hp := kl ( 1 − δ − α , δ ) . (20) The two instances differ only in objective r r r i i i r r r i i i r r r i i i Δ + η \Delta+\eta Δ + η − Δ -\Delta − Δ η \eta η 0 0 0 Δ + η \Delta+\eta Δ + η ( Δ + η ) 2 / 8 (\Delta+\eta)^2/8 ( Δ + η ) 2 /8 (20) yields
ℓ δ , α h p ≤ ( Δ + η ) 2 8 E θ Δ [ N i , r i n c ( τ ∧ T ) ] . \ell^{\mathrm{hp}}_{\delta,\alpha}\leq\frac{(\Delta+\eta)^2}{8}\mathbb{E}_{\theta^\Delta}\left[N^{\mathrm{inc}}_{i,r}(\tau\wedge T)\right]. ℓ δ , α hp ≤ 8 ( Δ + η ) 2 E θ Δ [ N i , r inc ( τ ∧ T ) ] . Therefore
E θ Δ [ N i , r i n c ( τ ∧ T ) ] ≥ 8 ℓ δ , α h p ( Δ + η ) 2 . \mathbb{E}_{\theta^\Delta}\left[N^{\mathrm{inc}}_{i,r}(\tau\wedge T)\right]\geq\frac{8\ell^{\mathrm{hp}}_{\delta,\alpha}}{(\Delta+\eta)^2}. E θ Δ [ N i , r inc ( τ ∧ T ) ] ≥ ( Δ + η ) 2 8 ℓ δ , α hp . By the assumption of Lemma B.14 , for every i ∈ { 2 , … , K } i \in\{2,\ldots,K\} i ∈ { 2 , … , K } r ∈ [ d ] r \in[d] r ∈ [ d ] η i , r ∈ ( 0 , η ˉ ] \eta_{i,r} \in(0,\bar{\eta}] η i , r ∈ ( 0 , η ˉ ] λ i , r , η i , r ∈ C \lambda^{i,r,\eta_{i,r}} \in\mathcal{C} λ i , r , η i , r ∈ C
E θ Δ [ N i , r i n c ( τ ∧ T ) ] ≥ 8 ℓ δ , α h p ( Δ + η i , r ) 2 ≥ 8 ℓ δ , α h p ( Δ + η ˉ ) 2 . \mathbb{E}_{\theta^\Delta}\left[N^{\mathrm{inc}}_{i,r}(\tau\wedge T)\right] \geq\frac{8\ell^{\mathrm{hp}}_{\delta,\alpha}}{(\Delta+\eta_{i,r})^2} \geq\frac{8\ell^{\mathrm{hp}}_{\delta,\alpha}}{(\Delta+\bar{\eta})^2}. E θ Δ [ N i , r inc ( τ ∧ T ) ] ≥ ( Δ + η i , r ) 2 8 ℓ δ , α hp ≥ ( Δ + η ˉ ) 2 8 ℓ δ , α hp . Summing over i ∈ { 2 , … , K } i \in\{2,\ldots,K\} i ∈ { 2 , … , K } r ∈ [ d ] r \in[d] r ∈ [ d ]
∑ i = 2 K ∑ r = 1 d E θ Δ [ N i , r i n c ( τ ∧ T ) ] ≥ 8 d ( K − 1 ) ℓ δ , α h p ( Δ + η ˉ ) 2 . \sum_{i=2}^{K}\sum_{r=1}^{d}\mathbb{E}_{\theta^\Delta}\left[N^{\mathrm{inc}}_{i,r}(\tau\wedge T)\right] \geq\frac{8d(K-1)\ell^{\mathrm{hp}}_{\delta,\alpha}}{(\Delta+\bar{\eta})^2}. i = 2 ∑ K r = 1 ∑ d E θ Δ [ N i , r inc ( τ ∧ T ) ] ≥ ( Δ + η ˉ ) 2 8 d ( K − 1 ) ℓ δ , α hp . On every sample path,
∑ i = 2 K ∑ r = 1 d N i , r i n c ( τ ∧ T ) ≤ 2 ( τ ∧ T ) ≤ 2 T , \sum_{i=2}^{K}\sum_{r=1}^{d}N^{\mathrm{inc}}_{i,r}(\tau\wedge T) \leq2(\tau\wedge T) \leq2T, i = 2 ∑ K r = 1 ∑ d N i , r inc ( τ ∧ T ) ≤ 2 ( τ ∧ T ) ≤ 2 T , because one objective-specific binary comparison is incident to at most two models in { 2 , … , K } \{2,\ldots,K\} { 2 , … , K }
T ≥ 4 d ( K − 1 ) ( Δ + η ˉ ) 2 kl ( 1 − δ − α , δ ) . T \geq\frac{4d(K-1)}{(\Delta+\bar{\eta})^2}\operatorname{kl}(1-\delta-\alpha,\delta). T ≥ ( Δ + η ˉ ) 2 4 d ( K − 1 ) kl ( 1 − δ − α , δ ) . Taking the infimum over all finite T T T
P θ Δ ( τ ≤ T ) ≥ 1 − α \mathbb{P}_{\theta^\Delta}(\tau\leq T) \geq1-\alpha P θ Δ ( τ ≤ T ) ≥ 1 − α proves the first assertion.
The sequence assumption in the second part of Lemma B.14 implies the preceding admissibility condition for every η ˉ > 0 \bar{\eta}>0 η ˉ > 0 η ˉ > 0 \bar{\eta}>0 η ˉ > 0 η ˉ ↓ 0 \bar{\eta}\downarrow0 η ˉ ↓ 0
Q θ Δ , α ( A ) ≥ 4 d ( K − 1 ) Δ 2 kl ( 1 − δ − α , δ ) . Q_{\theta^\Delta,\alpha}(\mathcal{A}) \geq\frac{4d(K-1)}{\Delta^2}\operatorname{kl}(1-\delta-\alpha,\delta). Q θ Δ , α ( A ) ≥ Δ 2 4 d ( K − 1 ) kl ( 1 − δ − α , δ ) . The specialization α = δ < 1 / 3 \alpha=\delta<1/3 α = δ < 1/3
kl ( 1 − 2 δ , δ ) = Θ ( log 1 δ ) as δ ↓ 0. \operatorname{kl}(1-2\delta,\delta)=\Theta\left(\log\frac{1}{\delta}\right)\quad\text{as }\delta\downarrow0. kl ( 1 − 2 δ , δ ) = Θ ( log δ 1 ) as δ ↓ 0. □ \square □
Remark B.1 (Admissible alternatives). For the bounded-range class Θ B , d \Theta_{B,d} Θ B , d Lemma B.14 holds whenever 0 < Δ < 2 B 0<\Delta<2B 0 < Δ < 2 B η n : = 2 B − Δ n + 1 ↓ 0 \eta_n:=\frac{2B-\Delta}{n+1}\downarrow0 η n := n + 1 2 B − Δ ↓ 0
This condition cannot hold on the gap-separated subclass Θ B , d ( Δ ) \Theta_{B,d}(\Delta) Θ B , d ( Δ ) η > 0 \eta>0 η > 0 Δ i ( λ i , r , η ) ≤ η \Delta_i(\lambda^{i,r,\eta})\leq\eta Δ i ( λ i , r , η ) ≤ η Θ B , d ( Δ ) \Theta_{B,d}(\Delta) Θ B , d ( Δ ) η ↓ 0 \eta\downarrow0 η ↓ 0 Δ ≤ B \Delta\leq B Δ ≤ B
θ Δ , λ i , r , Δ ∈ Θ B , d ( Δ ) for every i ≥ 2 , r ∈ [ d ] . \theta^\Delta,\lambda^{i,r,\Delta}\in\Theta_{B,d}(\Delta)\quad\text{for every }i\geq2,\ r\in[d]. θ Δ , λ i , r , Δ ∈ Θ B , d ( Δ ) for every i ≥ 2 , r ∈ [ d ] . The first part of Lemma B.14 therefore applies with η ˉ = Δ \bar{\eta}=\Delta η ˉ = Δ Theorem 3.2 .
We now apply the preceding lemma to prove the minimax lower bound.
Proof of Theorem 3.2 . Let A \mathcal{A} A δ \delta δ Θ B , d ( Δ ) \Theta_{B,d}(\Delta) Θ B , d ( Δ ) θ Δ \theta^\Delta θ Δ Lemma B.14 . Directly from Definition 2.2 ,
P ( θ Δ ) = { 1 } , Δ a ( θ Δ ) = Δ for every a ∈ [ K ] . \mathcal{P}(\theta^\Delta)=\{1\},\qquad\Delta_a(\theta^\Delta)=\Delta\quad\text{for every }a\in[K]. P ( θ Δ ) = { 1 } , Δ a ( θ Δ ) = Δ for every a ∈ [ K ] . For every i ≥ 2 i\geq2 i ≥ 2 r ∈ [ d ] r\in[d] r ∈ [ d ] λ i , r , Δ \lambda^{i,r,\Delta} λ i , r , Δ θ i , r Δ = − Δ \theta^\Delta_{i,r}=-\Delta θ i , r Δ = − Δ + Δ +\Delta + Δ
P ( λ i , r , Δ ) = { { i } , d = 1 , { 1 , i } , d ≥ 2 , \mathcal{P}(\lambda^{i,r,\Delta})=
\begin{cases}
\{i\}, & d=1,\\
\{1,i\}, & d\geq2,
\end{cases} P ( λ i , r , Δ ) = { { i } , { 1 , i } , d = 1 , d ≥ 2 , and
Δ 1 ( λ i , r , Δ ) = Δ i ( λ i , r , Δ ) = Δ , Δ k ( λ i , r , Δ ) ≥ Δ for every k ∉ { 1 , i } . \Delta_1(\lambda^{i,r,\Delta})=\Delta_i(\lambda^{i,r,\Delta})=\Delta,\qquad\Delta_k(\lambda^{i,r,\Delta})\geq\Delta\quad\text{for every }k\notin\{1,i\}. Δ 1 ( λ i , r , Δ ) = Δ i ( λ i , r , Δ ) = Δ , Δ k ( λ i , r , Δ ) ≥ Δ for every k ∈ / { 1 , i } . Moreover,
max s ∈ [ d ] max a , b ∈ [ K ] ∣ θ a , s Δ − θ b , s Δ ∣ = Δ , \max_{s\in[d]}\max_{a,b\in[K]}\left|\theta^\Delta_{a,s}-\theta^\Delta_{b,s}\right|=\Delta, s ∈ [ d ] max a , b ∈ [ K ] max θ a , s Δ − θ b , s Δ = Δ , whereas
max s ∈ [ d ] max a , b ∈ [ K ] ∣ λ a , s i , r , Δ − λ b , s i , r , Δ ∣ ≤ 2 Δ . \max_{s\in[d]}\max_{a,b\in[K]}\left|\lambda^{i,r,\Delta}_{a,s}-\lambda^{i,r,\Delta}_{b,s}\right|\leq2\Delta. s ∈ [ d ] max a , b ∈ [ K ] max λ a , s i , r , Δ − λ b , s i , r , Δ ≤ 2Δ. Since Δ ≤ B \Delta\leq B Δ ≤ B
θ Δ , λ i , r , Δ ∈ Θ B , d ( Δ ) . \theta^\Delta,\lambda^{i,r,\Delta}\in\Theta_{B,d}(\Delta). θ Δ , λ i , r , Δ ∈ Θ B , d ( Δ ) . Since λ i , r , Δ ∈ Θ B , d ( Δ ) \lambda^{i,r,\Delta}\in\Theta_{B,d}(\Delta) λ i , r , Δ ∈ Θ B , d ( Δ ) i ≥ 2 i\geq2 i ≥ 2 r ∈ [ d ] r\in[d] r ∈ [ d ] η ˉ = Δ \bar{\eta}=\Delta η ˉ = Δ α = δ \alpha=\delta α = δ
sup θ ∈ Θ B , d ( Δ ) Q θ , δ ( A ) ≥ Q θ Δ , δ ( A ) ≥ d ( K − 1 ) Δ 2 kl ( 1 − 2 δ , δ ) . \sup_{\theta\in\Theta_{B,d}(\Delta)}Q_{\theta,\delta}(A)\geq Q_{\theta^\Delta,\delta}(A)\geq\frac{d(K-1)}{\Delta^2}\operatorname{kl}(1-2\delta,\delta). θ ∈ Θ B , d ( Δ ) sup Q θ , δ ( A ) ≥ Q θ Δ , δ ( A ) ≥ Δ 2 d ( K − 1 ) kl ( 1 − 2 δ , δ ) . Taking the infimum over all such A A A
Proof of Corollary 3.3
Proof of Corollary 3.3. For every θ ∈ Θ B , d ( Δ ) \theta\in\Theta_{B,d}(\Delta) θ ∈ Θ B , d ( Δ )
Δ i θ ≥ Δ , M i θ ≤ ⌈ log 2 8 κ B Δ ⌉ , \Delta_i^\theta\geq\Delta,\qquad M_i^\theta\leq\left\lceil\log_2\frac{8}{\kappa_B\Delta}\right\rceil, Δ i θ ≥ Δ , M i θ ≤ ⌈ log 2 κ B Δ 8 ⌉ , L i θ ( δ ) ≤ log 4 K d ( ⌈ log 2 8 κ B Δ ⌉ ) 2 δ . L_i^\theta(\delta)\leq\log\frac{4Kd\left(\left\lceil\log_2\frac{8}{\kappa_B\Delta}\right\rceil\right)^2}{\delta}. L i θ ( δ ) ≤ log δ 4 K d ( ⌈ log 2 κ B Δ 8 ⌉ ) 2 . Hence Theorem 3.1 gives
sup θ ∈ Θ B , d ( Δ ) Q θ , δ ( V B - E G E ) ≤ d K + 128 d K κ B 2 Δ 2 log 4 K d ( ⌈ log 2 8 κ B Δ ⌉ ) 2 δ . \sup_{\theta\in\Theta_{B,d}(\Delta)}Q_{\theta,\delta}(\mathrm{VB\text{-}EGE})\leq dK+\frac{128dK}{\kappa_B^2\Delta^2}\log\frac{4Kd\left(\left\lceil\log_2\frac{8}{\kappa_B\Delta}\right\rceil\right)^2}{\delta}. θ ∈ Θ B , d ( Δ ) sup Q θ , δ ( VB - EGE ) ≤ d K + κ B 2 Δ 2 128 d K log δ 4 K d ( ⌈ log 2 κ B Δ 8 ⌉ ) 2 . The joint recovery statement in Theorem 3.1 also shows that VB-EGE is δ \delta δ Θ B , d ( Δ ) \Theta_{B,d}(\Delta) Θ B , d ( Δ ) Q B , d ( Δ , δ ) Q_{B,d}(\Delta,\delta) Q B , d ( Δ , δ )
Q B , d ( Δ , δ ) ≤ sup θ ∈ Θ B , d ( Δ ) Q θ , δ ( V B - E G E ) . Q_{B,d}(\Delta,\delta)\leq\sup_{\theta\in\Theta_{B,d}(\Delta)}Q_{\theta,\delta}(\mathrm{VB\text{-}EGE}). Q B , d ( Δ , δ ) ≤ θ ∈ Θ B , d ( Δ ) sup Q θ , δ ( VB - EGE ) . Combining this upper bound with Theorem 3.2 gives the minimax rate. Since K ≥ 2 K\geq2 K ≥ 2 K − 1 ≥ K / 2 K-1\geq K/2 K − 1 ≥ K /2 B B B κ B \kappa_B κ B
kl ( 1 − 2 δ , δ ) = Θ ( log 1 δ ) as δ ↓ 0. \operatorname{kl}(1-2\delta,\delta)=\Theta\left(\log\frac{1}{\delta}\right)\quad\text{as }\delta\downarrow0. kl ( 1 − 2 δ , δ ) = Θ ( log δ 1 ) as δ ↓ 0. Moreover, because Δ ≤ 1 \Delta\leq1 Δ ≤ 1 δ < 1 / 3 \delta<1/3 δ < 1/3 d K dK d K d K Δ − 2 dK\Delta^{-2} d K Δ − 2 K K K d d d Δ − 1 \Delta^{-1} Δ − 1 log ( 1 / δ ) \log(1/\delta) log ( 1/ δ )
Additional details and results for synthetic experiments
Details for the data-generating process
In the scaling experiments, the parameter grids are specified in Table 1 .
In the Convex-3D, Witness, and Arena settings, we first generate s s s θ i = 0.151 d + 0.75 z i \theta_i = 0.151d + 0.75z_i θ i = 0.151 d + 0.75 z i z i ∼ i i d Dirichlet ( α 1 d ) z_i \overset{\mathrm{iid}}{\sim} \operatorname{Dirichlet}(\alpha\mathbf{1}_d) z i ∼ iid Dirichlet ( α 1 d ) ∀ i ∈ [ s ] \forall i \in[s] ∀ i ∈ [ s ] α \alpha α s s s
t p = p − 1 s − 1 , θ p = ( 0.20 + 0.65 t p , 0.85 − 0.65 t p ) , p ∈ [ s ] . t_p = \frac{p-1}{s-1}, \qquad\theta_p = (0.20 + 0.65t_p,\, 0.85 - 0.65t_p), \qquad p \in[s]. t p = s − 1 p − 1 , θ p = ( 0.20 + 0.65 t p , 0.85 − 0.65 t p ) , p ∈ [ s ] . In the synthetic Arena and Convex settings, each dominated arm i ∉ [ s ] i \notin[s] i ∈ / [ s ] P i ∼ Unif ( [ s ] ) P_i \sim\operatorname{Unif}([s]) P i ∼ Unif ([ s ])
θ i = θ P i − m i where m i , r ∼ i i d Unif [ ℓ , u ] ∀ i ∉ [ s ] . (21) \theta_i = \theta_{P_i} - m_i \text{ where } m_{i,r} \overset{\mathrm{iid}}{\sim} \operatorname{Unif}[\ell,u] \quad\forall i \notin[s]. \tag*{(21)} θ i = θ P i − m i where m i , r ∼ iid Unif [ ℓ , u ] ∀ i ∈ / [ s ] . (21) For Convex-2D, [ ℓ , u ] = [ 0.03 , 0.18 ] [\ell,u] = [0.03, 0.18] [ ℓ , u ] = [ 0.03 , 0.18 ] q q q p ∈ [ s ] p \in[s] p ∈ [ s ] K = s ( q + 1 ) K = s(q+1) K = s ( q + 1 ) (21) with P i = p P_i = p P i = p p p p K l o w K_{\mathrm{low}} K low K h i g h K_{\mathrm{high}} K high K = K l o w + K h i g h K = K_{\mathrm{low}} + K_{\mathrm{high}} K = K low + K high Unif [ 0.20 , 0.45 ] \operatorname{Unif}[0.20, 0.45] Unif [ 0.20 , 0.45 ] Unif [ 0.55 , 0.75 ] \operatorname{Unif}[0.55, 0.75] Unif [ 0.55 , 0.75 ] Table 3 .
Table 3. Parameters used in the synthetic benchmark experiments.
For Convex-3D and Arena-10, we generate 50 sets of latent model scores and simulate comparisons independently 10 times for each setting. The other benchmarks use 500 independently generated instances. For benchmarks with repeated observations of the same instance, standard errors are computed from the 50 instance-level averages.
Implementation details for the baseline models
For BT-MLE , at each phase, we refit a centered ridge-regularized Bradley–Terry model per objective using all accumulated comparisons. For numerical stability, we use a ridge penalty coefficient of 10 − 8 10^{-8} 1 0 − 8 10 − 9 10^{-9} 1 0 − 9 10 − 4 10^{-4} 1 0 − 4
For Borda plug-in , let N i j , r c o m p ( t ) N_{ij,r}^{\mathrm{comp}}(t) N ij , r comp ( t ) i i i j j j r r r t t t W i j , r o n ( t ) W_{ij,r}^{\mathrm{on}}(t) W ij , r on ( t ) i i i i < j i < j i < j i i i j j j
p ~ i j ( r ) ( t ) : = W i j , r o n ( t ) + 1 / 2 N i j , r c o m p ( t ) + 1 , p ~ j i ( r ) ( t ) : = 1 − p ~ i j ( r ) ( t ) . \widetilde{p}_{ij}^{(r)}(t) := \frac{W_{ij,r}^{\mathrm{on}}(t) + 1/2}{N_{ij,r}^{\mathrm{comp}}(t) + 1}, \qquad\widetilde{p}_{ji}^{(r)}(t) := 1 - \widetilde{p}_{ij}^{(r)}(t). p ij ( r ) ( t ) := N ij , r comp ( t ) + 1 W ij , r on ( t ) + 1/2 , p j i ( r ) ( t ) := 1 − p ij ( r ) ( t ) . The added counts prevent estimates of exactly zero or one. We estimate each model’s Borda score on objective r r r
b ^ i , r ( t ) : = 1 K − 1 ∑ j ≠ i p ~ i j ( r ) ( t ) . \widehat{b}_{i,r}(t) := \frac{1}{K-1} \sum_{j \ne i} \widetilde{p}_{ij}^{(r)}(t). b i , r ( t ) := K − 1 1 j = i ∑ p ij ( r ) ( t ) . Additional results from synthetic experiments
Table 4 and Table 5 report the numerical results underlying (i)–(iii) of Figure 2 a and Figure 2 b, respectively. Table 6 provides the results for panel (iv) of Figure 2 a, while Table 7 reports confidence for the Arena-10 benchmark. Here, q 0.95 ( τ ) q_{0.95}(\tau) q 0.95 ( τ ) log ( 1 / δ ) \log(1/\delta) log ( 1/ δ ) R 2 ≈ 0.99997 R^2 \approx0.99997 R 2 ≈ 0.99997 1 / δ 1/\delta 1/ δ 10 − 3 10^{-3} 1 0 − 3
Table 4. Fixed-confidence scaling results. Parentheses contain one standard error for VB-EGE; remaining columns report each baseline’s mean comparison count divided by that of VB-EGE.
Table 5. Mean comparison counts for VB-EGE and ratios of mean comparison counts (baseline/VB-EGE). Parentheses contain one standard error. Ratio standard errors use the paired delta method, with instance-level averages as the independent units when multiple trials share the same latent instance.
Table 6. Confidence scaling on the symmetric K = 64 K = 64 K = 64 d = 10 d = 10 d = 10
Table 7. Confidence scaling on the Arena-10 medium task.
Figure 3. Arena-10 medium mean stopping time (mean ± one standard error) versus log ( 1 / δ ) \log(1/\delta) log ( 1/ δ )
Hyperparameter sensitivity analysis
We now examine sensitivity to the sampling and removal-threshold parameters by varying C s a m p ∈ { 0.5 , 1 , 2 , 4 } C_{\mathrm{samp}} \in\{0.5, 1, 2, 4\} C samp ∈ { 0.5 , 1 , 2 , 4 } C t h r ∈ { 2 , 3 , 4 , 6 } C_{\mathrm{thr}} \in\{2, 3, 4, 6\} C thr ∈ { 2 , 3 , 4 , 6 } C log = 4 C_{\log} = 4 C l o g = 4 δ = 0.05 \delta= 0.05 δ = 0.05 K = 64 K = 64 K = 64 d = 10 d = 10 d = 10 Theorem 3.1 as stated. Figure 4 present heatmaps corresponding to the sensitivity analysis results. We see that smaller C t h r C_{\mathrm{thr}} C thr
Figure 4. Mean stopping-time with respect to difference choices of ( C s a m p , C t h r ) (C_{\mathrm{samp}}, C_{\mathrm{thr}}) ( C samp , C thr )
Pareto-set size sensitivity analysis
We hold K = 64 K = 64 K = 64 ∣ P ∣ ∈ { 4 , 8 , 16 , 32 } |\mathcal{P}| \in\{4, 8, 16, 32\} ∣ P ∣ ∈ { 4 , 8 , 16 , 32 } [ 0.08 , 0.25 ] [0.08, 0.25] [ 0.08 , 0.25 ] [ 0.06 , 0.20 ] [0.06, 0.20] [ 0.06 , 0.20 ] Table 8 and visualized in Figure 5 , where we see that stopping cost increases with ∣ P ∣ |\mathcal{P}| ∣ P ∣
Table 8. Sensitivity to Pareto-set size. Parentheses contain one standard error for VB-EGE; other entries report each baseline’s mean comparison count divided by that of VB-EGE.
Figure 5. Mean stopping time (mean ± \pm ±
Sampling-mechanism diagnostics
Figure 6 plots the per-arm sample allocation against the Borda classification gap, showing that VB-EGE collects more observations for models with smaller gaps.
Figure 6. Total VB-EGE allocation to each model versus its Borda classification gap on representative Arena-4 medium and Two-group-10 instances. Smaller-gap models receive more samples.
Additional details and results for real-data experiments
This section describes preprocessing and sampling from the three real-world Arena datasets, followed by detailed results and sensitivity to the treatment of non-decisive outcomes.
Datasets, preprocessing, and retained models
Dataset versions and definition of the objectives. We fix the dataset versions before preprocessing. Comparisons are assigned to objectives solely from the released metadata, without using the prompt or response text.
Arena-Human-Preference-140K (Arena-140K): lmarena-ai/arena-human-preference-140k . Revision: 6322995ab34d7c2693e3f47dd13fa5caa0789a74. We construct five mutually exclusive prompt categories: general, code, math, creative writing, and instruction following. The four specialized categories are determined by the following metadata fields:
is_code for code,
category_tag.math_v0.1.math for math,
category_tag.creative_writing_v0.1.creative_writing for creative writing,
category_tag.if_v0.1.if for instruction following.
Because the released indicators may overlap, we assign each comparison to the first applicable category according to the prespecified priority ordering:
code > math > creative_writing > instruction_following.
Comparisons with no active specialized indicators are assigned to the general category. For example, a comparison marked as both code and math is assigned to code.
Search-Arena-24K: lmarena-ai/search-arena-24k . Revision: fac8dcf86146c8773ef020095c5694c9b2bc98d7. We use the nine released values of the categorical primary_intent field as objectives: Factual Lookup, Info Synthesis, Recommendation, Analysis, Explanation, Guidance, Creative Generation, Other, and Text Processing. Since primary_intent is single-valued, each retained comparison contributes to at most one objective. Comparisons with a missing or unsupported intent are excluded.
VisionArena-Battle: lmarena-ai/VisionArena-Battle . Revision: a41d58f15caa3e2d9685774153d2bc815b943d96. We use the eight released Boolean category indicators directly: captioning, creative_writing, diagram, entity_recognition, homework, humor, is_code, and ocr. These annotations are multi-label by construction. A comparison contributes once to every pair–objective cell whose corresponding indicator is true. Consequently, the number of pair–objective assignments may exceed the number of unique source comparisons; these repeated assignments represent overlapping category membership.
We retain only comparisons in which either model wins. In Arena-140K, we remove 21,528 tie and 15,749 both_bad records. In Search-Arena-24K, we remove 2,282 tie, 1,442 both_bad records, 10,751 missing outcomes, and 1,285 comparisons whose two model names refer to the same model after name normalization. In VisionArena-Battle, we remove 5,216 tie and 5,905 both_bad records; another 2,762 decisive records match none of the eight released category indicators and are therefore removed.
Selection of the retained models. After removing the non-decisive comparisons, we take as candidates all models that appear in at least one decisive comparison on every objective. We connect two candidate models when their pair has at least one decisive comparison on every objective, and retain a maximum-cardinality clique. If several maximum cliques exist, we choose the one with the largest total number of within-clique comparisons across objectives, then the lexicographically smallest sorted list of model names.
The resulting retained sets have 35, 8, and 12 models for Arena-140K, Search-Arena-24K, and VisionArena-Battle, respectively. We call these tasks Arena-35 , SearchArena-8 , and VisionArena-12 ; the suffix gives the number of retained models.
Having determined the retained models, we then remove comparisons involving discarded models. This step removes 25,197, 4,004, and 5,467 objective records from Arena-140K, Search-Arena-24K, and VisionArena-Battle, respectively. The details are summarized in Table 9 . The resulting empirical strict frontiers are presented in Table 10 .
Table 9. Preprocessing counts for the three Arena datasets. “Assigned comparisons” counts source comparisons assigned to at least one evaluation objective; “Objective records” counts the resulting pair–objective records. As in the main text, “Rows” counts pair–objective records involving only retained models. The 23,458 retained VisionArena-Battle records correspond to 12,937 unique source comparisons.
Table 10. Full-dimensional strict empirical Pareto sets on the three retained model sets.
Sampling from logged Arena comparisons
We evaluate the four methods by sampling with replacement from the retained logs, where each draw counts as one comparison. We evaluate the methods by treating the logged comparisons as the ground truth and comparing the methods’ outputs against the empirical Pareto frontier derived from these logs.
Ground truth and inferential target. Let D l o g \mathcal{D}_{\mathrm{log}} D log r ∈ [ d ] r \in[d] r ∈ [ d ] N i j , r l o g N^{\mathrm{log}}_{ij,r} N ij , r log N i j , r l o g ≥ 1 N^{\mathrm{log}}_{ij,r} \ge1 N ij , r log ≥ 1 pair–objective cell , defined as
D i j , r : = ( Y i j , r , s ) s = 1 N i j , r l o g , \mathcal{D}_{ij,r} := \left(Y_{ij,r,s}\right)_{s=1}^{N^{\mathrm{log}}_{ij,r}}, D ij , r := ( Y ij , r , s ) s = 1 N ij , r log , where Y i j , r , s = 1 Y_{ij,r,s}=1 Y ij , r , s = 1 i i i 0 0 0 j j j Y j i , r , s = 1 − Y i j , r , s Y_{ji,r,s}=1-Y_{ij,r,s} Y j i , r , s = 1 − Y ij , r , s N j i , r l o g = N i j , r l o g N^{\mathrm{log}}_{ji,r}=N^{\mathrm{log}}_{ij,r} N j i , r log = N ij , r log
Define
p ^ i j , r : = 1 N i j , r l o g ∑ s = 1 N i j , r l o g Y i j , r , s , p ^ j i , r = 1 − p ^ i j , r , \widehat{p}_{ij,r} := \frac{1}{N^{\mathrm{log}}_{ij,r}}\sum_{s=1}^{N^{\mathrm{log}}_{ij,r}}Y_{ij,r,s}, \qquad\widehat{p}_{ji,r}=1-\widehat{p}_{ij,r}, p ij , r := N ij , r log 1 s = 1 ∑ N ij , r log Y ij , r , s , p j i , r = 1 − p ij , r , and the empirical uniform-opponent Borda coordinates
b i , r e m p : = 1 K − 1 ∑ j ≠ i p ^ i j , r . b^{\mathrm{emp}}_{i,r}:=\frac{1}{K-1}\sum_{j\ne i}\widehat{p}_{ij,r}. b i , r emp := K − 1 1 j = i ∑ p ij , r . Writing b i e m p = ( b i , 1 e m p , … , b i , d e m p ) b^{\mathrm{emp}}_i=(b^{\mathrm{emp}}_{i,1},\ldots,b^{\mathrm{emp}}_{i,d}) b i emp = ( b i , 1 emp , … , b i , d emp ) b e m p = ( b i e m p ) i = 1 K b^{\mathrm{emp}}=(b^{\mathrm{emp}}_i)_{i=1}^{K} b emp = ( b i emp ) i = 1 K
P e m p : = P ( b e m p ) . \mathcal{P}_{\mathrm{emp}}:=\mathcal{P}(b^{\mathrm{emp}}). P emp := P ( b emp ) . Uniform-opponent queries. For a focal query ( i , r ) (i,r) ( i , r )
J ∼ Unif ( [ K ] ∖ { i } ) , S ∣ J = j ∼ Unif ( { 1 , … , N i j , r l o g } ) . J \sim\operatorname{Unif}([K] \setminus\{i\}), \qquad S \mid J=j \sim\operatorname{Unif}(\{1,\ldots,N^{\mathrm{log}}_{ij,r}\}). J ∼ Unif ([ K ] ∖ { i }) , S ∣ J = j ∼ Unif ({ 1 , … , N ij , r log }) . It returns
Z : = Y i J , r , S . Z := Y_{iJ,r,S}. Z := Y i J , r , S . Both sampling steps are performed with replacement, using fresh randomness independent of any other draw and of the algorithm’s internal randomization. The following lemma establishes that the sampled Z Z Z D l o g \mathcal{D}_{\mathrm{log}} D log
Lemma D.1 (Conditional Bernoulli representation). For every fixed logged data D l o g \mathcal{D}_{\mathrm{log}} D log ( i , r ) (i,r) ( i , r )
Z ∣ D l o g , i , r ∼ Bernoulli ( b i , r e m p ) . Z \mid\mathcal{D}_{\mathrm{log}},i,r \sim\operatorname{Bernoulli}(b^{\mathrm{emp}}_{i,r}). Z ∣ D log , i , r ∼ Bernoulli ( b i , r emp ) . The sampling randomization can be represented by mutually independent streams, one for each model–objective pair, with
Z i , r , 1 , Z i , r , 2 , … ∣ D l o g ∼ i i d Bernoulli ( b i , r e m p ) . Z_{i,r,1},Z_{i,r,2},\ldots\mid\mathcal{D}_{\mathrm{log}} \mathrel{\overset{\mathrm{iid}}{\sim}} \operatorname{Bernoulli}(b^{\mathrm{emp}}_{i,r}). Z i , r , 1 , Z i , r , 2 , … ∣ D log ∼ iid Bernoulli ( b i , r emp ) . Proof. Conditional on the log and J = j J=j J = j Z Z Z p ^ i j , r \widehat{p}_{ij,r} p ij , r
E s a m p [ Z ∣ D l o g , i , r ] = 1 K − 1 ∑ j ≠ i p ^ i j , r = b i , r e m p . \mathbb{E}_{\mathrm{samp}}[Z \mid\mathcal{D}_{\mathrm{log}},i,r] = \frac{1}{K-1}\sum_{j\ne i}\widehat{p}_{ij,r}=b^{\mathrm{emp}}_{i,r}. E samp [ Z ∣ D log , i , r ] = K − 1 1 j = i ∑ p ij , r = b i , r emp . Since Z Z Z ( i , r ) (i,r) ( i , r )
For fixed n ≥ 1 n\ge1 n ≥ 1 Z ‾ i , r ( n ) : = n − 1 ∑ s = 1 n Z i , r , s \overline{Z}_{i,r}(n):=n^{-1}\sum_{s=1}^{n}Z_{i,r,s} Z i , r ( n ) := n − 1 ∑ s = 1 n Z i , r , s m m m b ^ i , r ( m ) = Z ‾ i , r ( n m ) \widehat{b}^{(m)}_{i,r}=\overline{Z}_{i,r}(n_m) b i , r ( m ) = Z i , r ( n m )
Remark D.1 (Recovery conditional on the logged data). If min i Δ i ( b e m p ) > 0 \min_i\Delta_i(b^{\mathrm{emp}})>0 min i Δ i ( b emp ) > 0 b = b e m p b=b^{\mathrm{emp}} b = b emp 1 − δ 1-\delta 1 − δ D l o g \mathcal{D}_{\mathrm{log}} D log C = ( 2 , 4 , 4 ) C=(2,4,4) C = ( 2 , 4 , 4 ) P e m p \mathcal{P}_{\mathrm{emp}} P emp Δ i ( b e m p ) \Delta_i(b^{\mathrm{emp}}) Δ i ( b emp )
Opponent weighting and baseline sampling. For VB-EGE and Focal Borda, each focal query ( i , r ) (i,r) ( i , r )
For efficiency, the implementations sample batch counts directly. A batch of n n n ( i , r ) (i,r) ( i , r ) Binomial ( n , b i , r e m p ) \operatorname{Binomial}(n,b^{\mathrm{emp}}_{i,r}) Binomial ( n , b i , r emp ) ( i , j , r ) (i,j,r) ( i , j , r ) Binomial ( n , p ^ i j , r ) \operatorname{Binomial}(n,\widehat{p}_{ij,r}) Binomial ( n , p ij , r )
Population-level unbiasedness under an additional logging assumption. The recovery guarantee above conditions on the observed log. To relate its Borda means to population means, write N = ( N i j , r l o g ) i < j , r \mathbf{N}=(N^{\mathrm{log}}_{ij,r})_{i<j,r} N = ( N ij , r log ) i < j , r E l o g \mathbb{E}_{\mathrm{log}} E log
Lemma D.2 (Population Borda unbiasedness under cell-wise iid logging). Suppose that, for every cell,
Y i j , r , 1 , … , Y i j , r , N i j , r l o g ∣ N ∼ i i d Bernoulli ( p i j , r ) , (22) Y_{ij,r,1},\ldots,Y_{ij,r,N^{\mathrm{log}}_{ij,r}} \mid\mathbf{N} \mathrel{\overset{\mathrm{iid}}{\sim}} \operatorname{Bernoulli}(p_{ij,r}), \tag*{(22)} Y ij , r , 1 , … , Y ij , r , N ij , r log ∣ N ∼ iid Bernoulli ( p ij , r ) , (22) where p i j , r p_{ij,r} p ij , r p j i , r = 1 − p i j , r p_{ji,r}=1-p_{ij,r} p j i , r = 1 − p ij , r
b i , r p o p : = 1 K − 1 ∑ j ≠ i p i j , r . b^{\mathrm{pop}}_{i,r}:=\frac{1}{K-1}\sum_{j\ne i}p_{ij,r}. b i , r pop := K − 1 1 j = i ∑ p ij , r . Then
E log [ p ^ i j , r ∣ N ] = p i j , r , E log [ b i , r e m p ∣ N ] = b i , r p o p . \mathbb{E}_{\log}[\widehat{p}_{ij,r} \mid N] = p_{ij,r}, \qquad\mathbb{E}_{\log}[b^{\mathrm{emp}}_{i,r} \mid N] = b^{\mathrm{pop}}_{i,r}. E l o g [ p ij , r ∣ N ] = p ij , r , E l o g [ b i , r emp ∣ N ] = b i , r pop . For every fixed n ≥ 1 n \ge1 n ≥ 1 E log , s a m p [ Z ‾ i , r ( n ) ∣ N ] = b i , r p o p \mathbb{E}_{\log,\mathrm{samp}}[\overline{Z}_{i,r}(n) \mid N] = b^{\mathrm{pop}}_{i,r} E l o g , samp [ Z i , r ( n ) ∣ N ] = b i , r pop
Proof. The cell average has expectation p i j , r p_{ij,r} p ij , r (22) . Averaging these expectations over opponents proves the Borda identity.
The last assertion follows by iterated expectation and E s a m p [ Z ‾ i , r ( n ) ∣ D log ] = b i , r e m p \mathbb{E}_{\mathrm{samp}}[\overline{Z}_{i,r}(n) \mid\mathcal{D}_{\log}] = b^{\mathrm{emp}}_{i,r} E samp [ Z i , r ( n ) ∣ D l o g ] = b i , r emp
Together with Remark D.1, this lemma connects the two levels of the logged-data experiment. Conditional on the log, VB-EGE recovers P e m p \mathcal{P}_{\mathrm{emp}} P emp 1 − δ 1-\delta 1 − δ b e m p b^{\mathrm{emp}} b emp b p o p b^{\mathrm{pop}} b pop
Although unbiasedness does not necessarily transfer to P e m p \mathcal{P}_{\mathrm{emp}} P emp P ( ⋅ ) \mathcal{P}(\cdot) P ( ⋅ ) P e m p = P ( b p o p ) \mathcal{P}_{\mathrm{emp}} = \mathcal{P}(b^{\mathrm{pop}}) P emp = P ( b pop ) min i Δ i ( b p o p ) > 0 \min_i \Delta_i(b^{\mathrm{pop}}) > 0 min i Δ i ( b pop ) > 0 max i , r ∣ b i , r e m p − b i , r p o p ∣ < min i Δ i ( b p o p ) / 2 \max_{i,r} \lvert b^{\mathrm{emp}}_{i,r} - b^{\mathrm{pop}}_{i,r} \rvert< \min_i \Delta_i(b^{\mathrm{pop}})/2 max i , r ∣ b i , r emp − b i , r pop ∣ < min i Δ i ( b pop ) /2 min i < j , r N i j , r log → ∞ \min_{i<j,r} N^{\log}_{ij,r} \to\infty min i < j , r N ij , r l o g → ∞
Full Pareto-set results and method comparisons
Comparison of the four methods on the three Arena datasets
Table 11 gives the complete stopping-time comparison in the three real-world Arena datasets.
Table 11. Comparison of the four methods on the three Arena datasets. Entries are mean stopping times in millions of sampled comparisons (including repeated records), with each method’s mean divided by the VB-EGE mean in parentheses. Every method stops and recovers the exact frontier in all 100 trials on each dataset.
Full-dimensional empirical Borda profiles
Figure 7 to Figure 9 present the Borda scores for all the models under evaluation. Pareto membership is computed using all five, nine, or eight objectives for Arena-35, SearchArena-8, and VisionArena-12, respectively. Colored lines correspond to strict-frontier members and faint gray lines are dominated models from the same retained set. Across all three datasets, the frontier profiles cross one another repeatedly, reflecting the complementary strengths of the Pareto models.
Figure 7. Arena-35: empirical Borda profiles on all five objectives.
Figure 9. VisionArena-12: empirical Borda profiles on all eight objectives.
Figure 8. SearchArena-8: empirical Borda profiles on all nine objectives.
Low-dimensional illustrative projections
Figures 10 to 12 present representative two-dimensional and three-dimensional projections for each dataset, where we recompute Pareto membership in each projected space. Because strict dominance in the sense of Definition 1.1 is preserved when coordinates are removed, each projected frontier is a subset of the full-dimensional frontier.
The Arena-35 views here and in Figure 1 use the same 35 retained models and the same empirical Borda coordinates. The General, Code, and Math projection retains only gemini-2.5-pro. The Code, Math, and Instruction-Following projection in Figure 1 retains all three members of the full frontier: chatgpt-4o-latest-20250326, gemini-2.5-pro, and grok-3-preview-02-24. All recovery results use the full-dimensional target.
(a) 2D: Code versus Math.
(b) 3D: General, Code, and Math.
Figure 10. Arena-35 illustrative projections.
Figure 11. SearchArena-8 illustrative projections.
Figure 12. VisionArena-12 illustrative projections.
Sensitivity to tie and both_bad handling
The main experiments retain only decisive comparisons. This section examines the sensitivity of our results to different treatments of non-decisive outcomes. We consider two alternative treatments in addition to removing the non-decisive items:
D = decisive-only , H = direct merged half-credit , F = fitted Davidson half-credit . D = \text{decisive-only}, \qquad H = \text{direct merged half-credit}, \qquad F = \text{fitted Davidson half-credit}. D = decisive-only , H = direct merged half-credit , F = fitted Davidson half-credit . All three use the same retained models, objective assignments, and uniform-opponent aggregation.
Common setup and comparison metrics. For an unordered pair { i , j } \{i,j\} { i , j } r r r W i j , r W_{ij,r} W ij , r W j i , r W_{ji,r} W j i , r T i j , r T_{ij,r} T ij , r N i j , r b a d N^{\mathrm{bad}}_{ij,r} N ij , r bad U i j , r : = T i j , r + N i j , r b a d U_{ij,r} := T_{ij,r} + N^{\mathrm{bad}}_{ij,r} U ij , r := T ij , r + N ij , r bad Table 12 reports their totals; non-decisive records account for 27.5% to 38.0% of each retained log.
Table 12. Outcome counts on the retained models, before non-decisive labels are merged. Each record is one comparison assigned to one objective, and the last column is the fraction of records labeled tie or both_bad.
For X ∈ { D , H , F } X \in\{D,H,F\} X ∈ { D , H , F } b X = ( b i X ) i = 1 K b^X = (b_i^X)_{i=1}^K b X = ( b i X ) i = 1 K
b D = b e m p , P X = P ( b X ) , Δ min X = min i Δ i ( b X ) , H X = ∑ i Δ i ( b X ) − 2 , b^D = b^{\mathrm{emp}}, \qquad\mathcal{P}_X = \mathcal{P}(b^X), \qquad\Delta_{\min}^X = \min_i \Delta_i(b^X), \qquad\mathcal{H}_X = \sum_i \Delta_i(b^X)^{-2}, b D = b emp , P X = P ( b X ) , Δ m i n X = i min Δ i ( b X ) , H X = i ∑ Δ i ( b X ) − 2 , where the definition of b e m p b^{\mathrm{emp}} b emp
For two methods X X X Y Y Y
Jac ( X , Y ) = ∣ P X ∩ P Y ∣ ∣ P X ∪ P Y ∣ , \operatorname{Jac}(X,Y)=\frac{\lvert\mathcal{P}_X\cap\mathcal{P}_Y\rvert}{\lvert\mathcal{P}_X\cup\mathcal{P}_Y\rvert}, Jac ( X , Y ) = ∣ P X ∪ P Y ∣ ∣ P X ∩ P Y ∣ , and let ρ min ( X , Y ) \rho_{\min}(X,Y) ρ m i n ( X , Y ) δ = 0.05 \delta=0.05 δ = 0.05 C = ( 2 , 4 , 4 ) C=(2,4,4) C = ( 2 , 4 , 4 )
Direct merged half-credit recoding
Under D D D
p ^ i j , r D = W i j , r W i j , r + W j i , r = p ^ i j , r . \widehat{p}^{D}_{ij,r}=\frac{W_{ij,r}}{W_{ij,r}+W_{ji,r}}=\widehat{p}_{ij,r}. p ij , r D = W ij , r + W j i , r W ij , r = p ij , r . The direct construction H H H ( 1 , 0 ) (1,0) ( 1 , 0 ) ( 1 / 2 , 1 / 2 ) (1/2,1/2) ( 1/2 , 1/2 )
p ^ i j , r H = W i j , r + 1 2 U i j , r W i j , r + W j i , r + U i j , r , p ^ j i , r H = 1 − p ^ i j , r H . \widehat{p}^{H}_{ij,r}=\frac{W_{ij,r}+\frac{1}{2}U_{ij,r}}{W_{ij,r}+W_{ji,r}+U_{ij,r}},\qquad\widehat{p}^{H}_{ji,r}=1-\widehat{p}^{H}_{ij,r}. p ij , r H = W ij , r + W j i , r + U ij , r W ij , r + 2 1 U ij , r , p j i , r H = 1 − p ij , r H . Every pair–objective cell is estimated directly from its own logged counts, and the corresponding Borda mean is b i , r H = ( K − 1 ) − 1 ∑ j ≠ i p ^ i j , r H b^{H}_{i,r}=(K-1)^{-1}\sum_{j\ne i}\widehat{p}^{H}_{ij,r} b i , r H = ( K − 1 ) − 1 ∑ j = i p ij , r H Figure 13 to Figure 15 compare D D D H H H
Figure 13. Arena-35: union of both Pareto sets. Thicker opaque lines are frontier members; line pattern and marker distinguish models from the same provider. Left panel: D: decisive-only. Right panel: H: direct half-credit. Objectives: General, Code, Math, Creative Writing, Instruction Following. Borda score ranges from 0.45 to 0.75. Models: gemini-2.5-pro, grok-3-preview-02-24, chatgpt-4o-latest-20250326, minimax-m1. Arena-35: Borda profiles of the models in P D ∪ P H P_D\cup P_H P D ∪ P H H H H D D D H H H
Figure 15. VisionArena-12: Borda profiles of the models in P D ∪ P H \mathcal{P}_D \cup\mathcal{P}_H P D ∪ P H D D D H H H
As in Appendix § 9 .§ 2 , each query draws an opponent uniformly from the other retained models, then a record uniformly with replacement from the selected cell. A win, a non-decisive outcome, and a loss return 1, 1/2, and 0. The proof of Proposition B.4 uses Hoeffding’s inequality, which also applies to these [ 0 , 1 ] [0,1] [ 0 , 1 ] P H P_H P H
Figure 14. SearchArena-8: Borda profiles of the models in P D ∪ P H \mathcal{P}_D \cup\mathcal{P}_H P D ∪ P H D D D H H H
For batching, we average the three outcome probabilities over opponents and draw multinomial category counts, extending the batch-count implementation in Appendix § 9 .§ 2 . The resulting sums and counts have the same distribution as sequential queries; these are the only observation summaries used by VB-EGE.
Fitted Davidson construction
Three-outcome likelihood. The fitted construction F F F ( W i j , r , W j i , r , U i j , r ) (W_{ij,r}, W_{ji,r}, U_{ij,r}) ( W ij , r , W j i , r , U ij , r ) r r r [15 ] ) with pair-specific tie weights, following the factored tie construction of Ameli et al. [1 ] . Let θ i , r \theta_{i,r} θ i , r i i i i < j i < j i < j η i j , r \eta_{ij,r} η ij , r i i i j j j
( π i j , r W , π i j , r L , π i j , r U ) = softmax ( θ i , r F − θ j , r F 2 , θ j , r F − θ i , r F 2 , η i j , r ) , ∑ i = 1 K θ i , r F = 0. (23) \left(\pi^{W}_{ij,r},\pi^{L}_{ij,r},\pi^{U}_{ij,r}\right)=\operatorname{softmax}\left(\frac{\theta^{F}_{i,r}-\theta^{F}_{j,r}}{2},\frac{\theta^{F}_{j,r}-\theta^{F}_{i,r}}{2},\eta_{ij,r}\right),\qquad\sum_{i=1}^{K}\theta^{F}_{i,r}=0. \tag*{(23)} ( π ij , r W , π ij , r L , π ij , r U ) = softmax ( 2 θ i , r F − θ j , r F , 2 θ j , r F − θ i , r F , η ij , r ) , i = 1 ∑ K θ i , r F = 0. (23) Conditional on a decisive outcome, the win probability follows the Bradley–Terry model with score difference θ i , r F − θ j , r F \theta^{F}_{i,r}-\theta^{F}_{j,r} θ i , r F − θ j , r F (23) by ( W i j , r , W j i , r , U i j , r ) (W_{ij,r},W_{ji,r},U_{ij,r}) ( W ij , r , W j i , r , U ij , r ) i < j i<j i < j
Factored tie weight. We use a parameter k t i e k_{\mathrm{tie}} k tie η i j , r \eta_{ij,r} η ij , r k t i e = 0 k_{\mathrm{tie}}=0 k tie = 0 r r r η i j , r = γ r t i e \eta_{ij,r}=\gamma^{\mathrm{tie}}_{r} η ij , r = γ r tie k t i e > 0 k_{\mathrm{tie}}>0 k tie > 0
η i j , r = ( Γ r ) i j , Γ r = V r Φ T + Φ V r T , ( Φ ) a ℓ = 2 K cos [ π ( 2 a − 1 ) ( 2 ℓ − 1 ) 4 K ] . \eta_{ij,r}=(\Gamma_{r})_{ij},\qquad\Gamma_{r}=V_{r}\Phi^{\mathsf{T}}+\Phi V_{r}^{\mathsf{T}},\qquad(\Phi)_{a\ell}=\sqrt{\frac{2}{K}}\cos\left[\frac{\pi(2a-1)(2\ell-1)}{4K}\right]. η ij , r = ( Γ r ) ij , Γ r = V r Φ T + Φ V r T , ( Φ ) a ℓ = K 2 cos [ 4 K π ( 2 a − 1 ) ( 2 ℓ − 1 ) ] . where V r , Φ ∈ R K × k t i e V_r,\Phi\in\mathbb{R}^{K\times k_{\mathrm{tie}}} V r , Φ ∈ R K × k tie Φ \Phi Φ k t i e k_{\mathrm{tie}} k tie Γ r \Gamma_r Γ r k t i e k_{\mathrm{tie}} k tie tie-factor size . Ameli et al. [1 ] call it the rank of the factor matrices; we use a different name because Γ r \Gamma_r Γ r 2 k t i e 2k_{\mathrm{tie}} 2 k tie k t i e ≥ 1 k_{\mathrm{tie}}\ge1 k tie ≥ 1 γ r t i e \gamma^{\mathrm{tie}}_r γ r tie k t i e ≥ 1 k_{\mathrm{tie}}\ge1 k tie ≥ 1 V r V_r V r k t i e k_{\mathrm{tie}} k tie k t i e + 1 k_{\mathrm{tie}}+1 k tie + 1 k t i e = 0 k_{\mathrm{tie}}=0 k tie = 0
Selection of k t i e k_{\mathrm{tie}} k tie Within each objective, we assign each observation independently to training with probability 0.9. Whenever a model pair has no training observations in that objective, we move one of its validation observations, taken from its most frequent outcome category, to training.
The candidate grids are prespecified and listed in Table 13 ; Arena-35 uses a broader grid than the two smaller model sets. Selection is restricted to these grids. We select the size with the smallest held-out mean negative log-likelihood and refit it to all observations. Fits use BFGS with analytic gradients; all 76 candidate fits and 22 full-data fits converged, with one candidate requiring an L-BFGS-B fallback.
Table 13. Selection of the tie-factor size k t i e k_{\mathrm{tie}} k tie § 9 .§ 1 .
The held-out losses for all candidate tie-factor sizes are shown in Figure 16 to Figure 18 .
Figure 16. Arena-35: held-out NLL for each candidate tie-factor size k t i e k_{\mathrm{tie}} k tie
Figure 18. VisionArena-12: held-out NLL for each candidate tie-factor size k t i e k_{\mathrm{tie}} k tie
Binary interface and fitted target. After refitting the selected model to all observations, we convert its fitted outcome probabilities to half-credit win probabilities
p ^ i j , r F = π i j , r W + 1 2 π i j , r U , p ^ j i , r F = π i j , r L + 1 2 π i j , r U = 1 − p ^ i j , r F . \widehat{p}^{F}_{ij,r}=\pi^{W}_{ij,r}+\frac{1}{2}\pi^{U}_{ij,r},\qquad\widehat{p}^{F}_{ji,r}=\pi^{L}_{ij,r}+\frac{1}{2}\pi^{U}_{ij,r}=1-\widehat{p}^{F}_{ij,r}. p ij , r F = π ij , r W + 2 1 π ij , r U , p j i , r F = π ij , r L + 2 1 π ij , r U = 1 − p ij , r F . As in Appendix § 9 .§ 2 , each oracle query first draws an opponent uniformly from the other retained models. Conditional on the selected pair ( i , j ) (i,j) ( i , j ) r r r p ^ i j , r F \widehat{p}^{F}_{ij,r} p ij , r F
b i , r F = 1 K − 1 ∑ j ≠ i p ^ i j , r F b^{F}_{i,r}=\frac{1}{K-1}\sum_{j\ne i}\widehat{p}^{F}_{ij,r} b i , r F = K − 1 1 j = i ∑ p ij , r F and obtain the Pareto set P F P_F P F
For each model–objective pair, the marginal observation law is Bernoulli(b i , r F b^F_{i,r} b i , r F D D D
Figure 17. SearchArena-8: held-out NLL for each candidate tie-factor size k t i e k_{\mathrm{tie}} k tie
Target and stopping-time comparisons
Target sensitivity. Table 14 compares the two alternatives with D D D H H H minimax-m1 to the frontier, increasing its size from three to four. Under F F F minimax-m1 enters and chatgpt-4o-latest-20250326 leaves, keeping the frontier size at three. The respective Jaccard overlaps with D D D Figure 13 and Figure 19 show the Arena-35 profiles where membership changes.
Figure 19. Arena-35: Borda profiles of the models in P D ∪ P F P_D \cup P_F P D ∪ P F minimax-m1 enters and chatgpt-4o-latest-20250326 leaves the strict Pareto frontier under F F F D D D F F F
Table 14. Target sensitivity on the fixed sets of retained models used in the main experiments.
Figure 20. SearchArena-8: Borda profiles of the models in P D ∪ P F P_D \cup P_F P D ∪ P F D D D F F F
Figure 21. VisionArena-12: Borda profiles of the models in P D ∪ P F P_D \cup P_F P D ∪ P F D D D F F F
Table 14: Target sensitivity on the fixed sets of retained models used in the main experiments. D / H / F D/H/F D / H / F Jac ( D , H ) \operatorname{Jac}(D,H) Jac ( D , H ) Jac ( D , F ) \operatorname{Jac}(D,F) Jac ( D , F ) ρ min \rho_{\min} ρ m i n
Borda profiles under the fitted Davidson target. Figures 19 to 21 compare D D D F F F
Stopping times and gap summaries. Under D D D F F F D D D H H H { 0 , 1 / 2 , 1 } \{0,1/2,1\} { 0 , 1/2 , 1 } u i , r H u_{i,r}^{H} u i , r H b i , r H ( 1 − b i , r H ) − u i , r H / 4 b_{i,r}^{H}(1-b_{i,r}^{H})-u_{i,r}^{H}/4 b i , r H ( 1 − b i , r H ) − u i , r H /4 D D D
Table 15 reports the minimum gaps, inverse-squared-gap sums, and stopping times. The gap summaries do not track stopping times closely: from D D D F F F H X \mathcal{H}_{X} H X
(a) Gap summaries
(b) Stopping times
(c) Final phases (numbers of trials)
Table 15.
Table 15: Gap summaries and stopping times under D D D H H H F F F H X = ∑ i Δ i ( b X ) − 2 \mathcal{H}_{X}=\sum_i\Delta_i(b^{X})^{-2} H X = ∑ i Δ i ( b X ) − 2
In phase m m m n m n_m n m n m n_m n m F F F
Each phase’s cost also depends on the number of active models. On Arena-35, all 100 trials under D D D H H H D D D H H H
Additional comparison with a Track-and-Stop extension
The BT-MLE baseline in the main experiments samples pair–objective cells uniformly, so its gap to VB-EGE leaves open whether an adaptive likelihood-based method would perform better. This section empirically examines that question using a Pareto extension of the scalar top-k k k [21 ] . Appendix § 10 .§ 1 describes the extension, and Appendix § 10 .§ 2 compares it with VB-EGE on the synthetic tasks of Appendix § 8 .
Implementation used in the reported experiments
The scalar top-k k k [21 ] combines Bradley–Terry MLE, adaptive allocation, and a generalized likelihood-ratio (GLR) stopping rule. We retain this template and replace its scalar alternatives with Pareto alternatives, calling the resulting procedure Pareto BT-GLR Track-and-Stop (Pareto BT-GLR T&S). Here, an alternative is a set of score arrays defined by linear inequalities describing a change in the current Pareto frontier, up to boundary points. The implementation ranks these alternatives by approximate Fisher-information scores and refits the likelihood only under the selected alternative. We call this approximation screening .
Let N c e l l = d ( K 2 ) N_{\mathrm{cell}}=d\binom{K}{2} N cell = d ( 2 K ) n 0 n_0 n 0 w i j , r = 1 / N c e l l w_{ij,r}=1/N_{\mathrm{cell}} w ij , r = 1/ N cell m m m t t t N i j , r ( t ) N_{ij,r}(t) N ij , r ( t ) ( i , j , r ) (i,j,r) ( i , j , r ) θ ^ ⋅ , r , t ∈ R K \widehat{\theta}_{\cdot,r,t}\in\mathbb{R}^{K} θ ⋅ , r , t ∈ R K r r r θ ^ t = ( θ ^ i , t ) i = 1 K \widehat{\theta}_t=(\widehat{\theta}_{i,t})_{i=1}^{K} θ t = ( θ i , t ) i = 1 K θ ^ i , t = ( θ ^ i , r , t ) r = 1 d \widehat{\theta}_{i,t}=(\widehat{\theta}_{i,r,t})_{r=1}^{d} θ i , t = ( θ i , r , t ) r = 1 d Table 16 .
Table 16. Constants used by Pareto BT-GLR T&S.
Fit. Separately for each objective r r r
θ ^ ⋅ , r , t ∈ arg max ϑ ∈ Θ b o x ℓ r , t ( ϑ ) , Θ b o x : = { ϑ ∈ R K : 1 T ϑ = 0 , ∥ ϑ ∥ ∞ ≤ S max } , \widehat{\theta}_{\cdot,r,t}\in\underset{\vartheta\in\Theta_{\mathrm{box}}}{\arg\max}\ \ell_{r,t}(\vartheta),\qquad\Theta_{\mathrm{box}}:=\{\vartheta\in\mathbb{R}^{K}: \mathbf{1}^{\mathsf{T}}\vartheta=0,\ \lVert\vartheta\rVert_{\infty}\le S_{\max}\}, θ ⋅ , r , t ∈ ϑ ∈ Θ box arg max ℓ r , t ( ϑ ) , Θ box := { ϑ ∈ R K : 1 T ϑ = 0 , ∥ ϑ ∥ ∞ ≤ S m a x } , where ℓ r , t \ell_{r,t} ℓ r , t r r r Table 16 .
Construct alternatives. Let P ^ t = P ( θ ^ t ) \widehat{P}_t=\mathcal{P}(\widehat{\theta}_t) P t = P ( θ t ) drop alternative ( p , p ′ ) (p,p') ( p , p ′ ) p , p ′ ∈ P ^ t p,p'\in\widehat{P}_t p , p ′ ∈ P t θ p ′ , r ≥ θ p , r \theta_{p',r}\ge\theta_{p,r} θ p ′ , r ≥ θ p , r r r r p p p add alternative for c ∉ P ^ t c\notin\widehat{P}_t c ∈ / P t g ( p ) ∈ [ d ] g(p)\in[d] g ( p ) ∈ [ d ] p ∈ P ^ t p\in\widehat{P}_t p ∈ P t θ c , g ( p ) ≥ θ p , g ( p ) \theta_{c,g(p)}\ge\theta_{p,g(p)} θ c , g ( p ) ≥ θ p , g ( p ) c c c d ∣ P ^ t ∣ d^{|\widehat{P}_t|} d ∣ P t ∣
Screen alternatives and refit. Set p ^ i j , r , t = σ ( θ ^ i , r , t − θ ^ j , r , t ) \widehat{p}_{ij,r,t}=\sigma(\widehat{\theta}_{i,r,t}-\widehat{\theta}_{j,r,t}) p ij , r , t = σ ( θ i , r , t − θ j , r , t )
I r , t = ∑ i < j N i j , r ( t ) p ^ i j , r , t ( 1 − p ^ i j , r , t ) ( e i − e j ) ( e i − e j ) T , \mathcal{I}_{r,t}=\sum_{i<j}N_{ij,r}(t)\widehat{p}_{ij,r,t}(1-\widehat{p}_{ij,r,t})(e_i-e_j)(e_i-e_j)^{\mathsf{T}}, I r , t = i < j ∑ N ij , r ( t ) p ij , r , t ( 1 − p ij , r , t ) ( e i − e j ) ( e i − e j ) T , where e i e_i e i i i i θ a , r ≥ θ b , r \theta_{a,r}\ge\theta_{b,r} θ a , r ≥ θ b , r
h a b , r , t = ( ( θ ^ b , r , t − θ ^ a , r , t ) + ) 2 2 ( e a − e b ) T I r , t † ( e a − e b ) . h_{ab,r,t}=\frac{\left((\widehat{\theta}_{b,r,t}-\widehat{\theta}_{a,r,t})_{+}\right)^2}{2(e_a-e_b)^{\mathsf{T}}\mathcal{I}_{r,t}^{\dagger}(e_a-e_b)}. h ab , r , t = 2 ( e a − e b ) T I r , t † ( e a − e b ) ( ( θ b , r , t − θ a , r , t ) + ) 2 . where I r , t † \mathcal{I}_{r,t}^{\dagger} I r , t † ∑ r h p ′ p , r , t \sum_r h_{p'p,r,t} ∑ r h p ′ p , r , t c c c max p ∈ P ^ t min r h c p , r , t \max_{p\in\widehat{P}_t}\min_r h_{cp,r,t} max p ∈ P t min r h c p , r , t
For an add candidate c c c g c ( p ) ∈ arg min r h c p , r , t g_c(p) \in\arg\min_r h_{c p,r,t} g c ( p ) ∈ arg min r h c p , r , t p ∈ P ^ t p \in\widehat{P}_t p ∈ P t max p h c p , g ( p ) , t \max_p h_{c p,g(p),t} max p h c p , g ( p ) , t g g g
Let ξ ^ t \widehat{\xi}_t ξ t h ^ t s c r \widehat{h}^{\mathrm{scr}}_t h t scr
For each objective r r r ξ ^ t \widehat{\xi}_t ξ t ( p , p ′ ) (p,p') ( p , p ′ ) ϑ p ′ ≥ ϑ p \vartheta_{p'} \ge\vartheta_p ϑ p ′ ≥ ϑ p ( c , g ) (c,g) ( c , g ) ϑ c ≥ ϑ p \vartheta_c \ge\vartheta_p ϑ c ≥ ϑ p p ∈ P ^ t p \in\widehat{P}_t p ∈ P t g ( p ) = r g(p)=r g ( p ) = r Θ ξ ^ t , r \Theta_{\widehat{\xi}_t,r} Θ ξ t , r Θ b o x \Theta_{\mathrm{box}} Θ box ξ \xi ξ
max ϑ ∈ Θ ξ ^ t , r ℓ r , t ( ϑ ) \max_{\vartheta\in\Theta_{\widehat{\xi}_t,r}} \ell_{r,t}(\vartheta) ϑ ∈ Θ ξ t , r max ℓ r , t ( ϑ ) and denote the resulting estimate by ϑ ~ ⋅ , r , t \widetilde{\vartheta}_{\cdot,r,t} ϑ ⋅ , r , t
These fits separate across objectives. To account for numerical optimization error, write f r , t = − ℓ r , t f_{r,t}=-\ell_{r,t} f r , t = − ℓ r , t
g r , t = [ ∇ f r , t ( ϑ ~ ⋅ , r , t ) T ϑ ~ ⋅ , r , t − min ϑ ∈ Θ ξ ^ t , r ∇ f r , t ( ϑ ~ ⋅ , r , t ) T ϑ ] + . g_{r,t}=\left[\nabla f_{r,t}(\widetilde{\vartheta}_{\cdot,r,t})^{\mathsf{T}}\widetilde{\vartheta}_{\cdot,r,t}-\min_{\vartheta\in\Theta_{\widehat{\xi}_t,r}}\nabla f_{r,t}(\widetilde{\vartheta}_{\cdot,r,t})^{\mathsf{T}}\vartheta\right]^+. g r , t = [ ∇ f r , t ( ϑ ⋅ , r , t ) T ϑ ⋅ , r , t − ϑ ∈ Θ ξ t , r min ∇ f r , t ( ϑ ⋅ , r , t ) T ϑ ] + . Convexity gives a lower bound f r , t ( ϑ ~ ⋅ , r , t ) − g r , t f_{r,t}(\widetilde{\vartheta}_{\cdot,r,t})-g_{r,t} f r , t ( ϑ ⋅ , r , t ) − g r , t Θ ξ ^ t , r \Theta_{\widehat{\xi}_t,r} Θ ξ t , r f r , t ( ϑ ^ ⋅ , r , t ) f_{r,t}(\widehat{\vartheta}_{\cdot,r,t}) f r , t ( ϑ ⋅ , r , t ) Θ b o x \Theta_{\mathrm{box}} Θ box
G t a l t = ∑ r [ f r , t ( ϑ ~ ⋅ , r , t ) − g r , t − f r , t ( ϑ ^ ⋅ , r , t ) ] + . G^{\mathrm{alt}}_t=\sum_r\left[f_{r,t}(\widetilde{\vartheta}_{\cdot,r,t})-g_{r,t}-f_{r,t}(\widehat{\vartheta}_{\cdot,r,t})\right]^+. G t alt = r ∑ [ f r , t ( ϑ ⋅ , r , t ) − g r , t − f r , t ( ϑ ⋅ , r , t ) ] + . The implemented statistic is Ψ t = min { h ^ t s c r , G t a l t } \Psi_t=\min\{\widehat{h}^{\mathrm{scr}}_t,G^{\mathrm{alt}}_t\} Ψ t = min { h t scr , G t alt }
Stop. Define the comparison-count matrix
Ω r , t = ∑ i < j N i j , r ( t ) ( e i − e j ) ( e i − e j ) T \Omega_{r,t}=\sum_{i<j}N_{ij,r}(t)(e_i-e_j)(e_i-e_j)^{\mathsf{T}} Ω r , t = i < j ∑ N ij , r ( t ) ( e i − e j ) ( e i − e j ) T and threshold
β t ( δ ) = log 1 δ + λ r e g 2 ∑ r ∥ ϑ ^ ⋅ , r , t ∥ 2 2 + 1 2 ∑ r log det ( I K + σ ‾ 2 λ r e g Ω r , t ) . \beta_t(\delta)=\log\frac{1}{\delta}+\frac{\lambda_{\mathrm{reg}}}{2}\sum_r\lVert\widehat{\vartheta}_{\cdot,r,t}\rVert_2^2+\frac{1}{2}\sum_r\log\det\left(I_K+\frac{\overline{\sigma}^2}{\lambda_{\mathrm{reg}}}\Omega_{r,t}\right). β t ( δ ) = log δ 1 + 2 λ reg r ∑ ∥ ϑ ⋅ , r , t ∥ 2 2 + 2 1 r ∑ log det ( I K + λ reg σ 2 Ω r , t ) . The method returns P ^ t \widehat{P}_t P t ϑ ^ ⋅ , r , t \widehat{\vartheta}_{\cdot,r,t} ϑ ⋅ , r , t ϑ ~ ⋅ , r , t \widetilde{\vartheta}_{\cdot,r,t} ϑ ⋅ , r , t r r r Ψ t ≥ β t ( δ ) \Psi_t\ge\beta_t(\delta) Ψ t ≥ β t ( δ ) t = T max t=T_{\max} t = T m a x
Allocate the next batch. For each pair–objective cell, compute
κ i j , r , t = kl σ ( σ ( ϑ ^ i , r , t − ϑ ^ j , r , t ) , σ ( ϑ ~ i , r , t − ϑ ~ j , r , t ) ) , κ max , t : = max { ϵ κ , max a < b , s κ a b , s , t } . \kappa_{ij,r,t}=\operatorname{kl}_{\sigma}\left(\sigma(\widehat{\vartheta}_{i,r,t}-\widehat{\vartheta}_{j,r,t}),\sigma(\widetilde{\vartheta}_{i,r,t}-\widetilde{\vartheta}_{j,r,t})\right),\qquad\kappa_{\max,t}:=\max\left\{\epsilon_\kappa,\max_{a<b,s}\kappa_{ab,s,t}\right\}. κ ij , r , t = kl σ ( σ ( ϑ i , r , t − ϑ j , r , t ) , σ ( ϑ i , r , t − ϑ j , r , t ) ) , κ m a x , t := max { ϵ κ , a < b , s max κ ab , s , t } . Update the current weights by
w i j , r n e w = w i j , r o l d exp ( α M W κ i j , r , t / ( m κ max , t ) ) ∑ a < b ∑ s = 1 d w a b , s o l d exp ( α M W κ a b , s , t / ( m κ max , t ) ) . w^{\mathrm{new}}_{ij,r}=\frac{w^{\mathrm{old}}_{ij,r}\exp\left(\alpha_{\mathrm{MW}}\kappa_{ij,r,t}/(\sqrt{m}\,\kappa_{\max,t})\right)}{\sum_{a<b}\sum_{s=1}^{d}w^{\mathrm{old}}_{ab,s}\exp\left(\alpha_{\mathrm{MW}}\kappa_{ab,s,t}/(\sqrt{m}\,\kappa_{\max,t})\right)}. w ij , r new = ∑ a < b ∑ s = 1 d w ab , s old exp ( α MW κ ab , s , t / ( m κ m a x , t ) ) w ij , r old exp ( α MW κ ij , r , t / ( m κ m a x , t ) ) . This favors comparisons that distinguish the current fit from the selected alternative. Schedule the next check at
t n e x t : = min { T max , max ( t + N c e l l , ⌈ a b a t c h t ⌉ ) } . t_{\mathrm{next}}:=\min\left\{T_{\max},\max\left(t+N_{\mathrm{cell}},\lceil a_{\mathrm{batch}}t\rceil\right)\right\}. t next := min { T m a x , max ( t + N cell , ⌈ a batch t ⌉ ) } . Form the mixed weights w ~ i j , r = ( 1 − ρ t m i x ) w i j , r + ρ t m i x / N c e l l \widetilde{w}_{ij,r}=(1-\rho_t^{\mathrm{mix}})w_{ij,r}+\rho_t^{\mathrm{mix}}/N_{\mathrm{cell}} w ij , r = ( 1 − ρ t mix ) w ij , r + ρ t mix / N cell ρ t m i x = t n e x t − γ m i x \rho_t^{\mathrm{mix}}=t_{\mathrm{next}}^{-\gamma_{\mathrm{mix}}} ρ t mix = t next − γ mix w i j , r w_{ij,r} w ij , r t n e x t − t t_{\mathrm{next}}-t t next − t
C-tracking ([20 ] ): update the cumulative target counts, initialized at P i j , r = n 0 P_{ij,r}=n_0 P ij , r = n 0 P i j , r ← P i j , r + ( t n e x t − t ) w ~ i j , r P_{ij,r} \leftarrow P_{ij,r}+(t_{\mathrm{next}}-t)\widetilde{w}_{ij,r} P ij , r ← P ij , r + ( t next − t ) w ij , r ( P i j , r − N i j , r ( t ) ) + (P_{ij,r}-N_{ij,r}(t))^{+} ( P ij , r − N ij , r ( t ) ) + t n e x t − t t_{\mathrm{next}}-t t next − t
Relation to the scalar implementation. The threshold follows the form in Goldberger & Rudi [21 ] ’s Equation (4). Stacking the objective-specific score vectors gives a block-diagonal comparison-count matrix with blocks Ω r , t \Omega_{r,t} Ω r , t [ 0 , 1 ] [0,1] [ 0 , 1 ] t − 0.2 t^{-0.2} t − 0.2
Comparison with VB-EGE
We run this exploratory comparison at δ = 0.05 \delta=0.05 δ = 0.05 § 8 . This gives 12,400 trials per method over 28 settings: 12 scaling settings, 8 benchmarks, and 8 Pareto-set size settings. The capped mean stopping time is the mean comparison count until stopping or capping, with capped trials recorded at T max T_{\max} T m a x R R R n n n exp ( n − 1 ∑ k = 1 n log R k ) \exp(n^{-1}\sum_{k=1}^{n}\log R_k) exp ( n − 1 ∑ k = 1 n log R k )
Pareto BT-GLR T&S has the smaller capped mean stopping time in 1 of the 28 settings: 1 of the 12 scaling settings, and none of the 8 benchmarks or the 8 Pareto-set size settings (Figure 22 to Figure 24 ). The geometric-mean ratios are 4.10 over the scaling settings and 20.6 over the Pareto-set size settings.
Figure 22. Scaling comparison at δ = 0.05 \delta=0.05 δ = 0.05 K = 16 K=16 K = 16 ± \pm ±
Figure 24. Pareto-set size sensitivity at δ = 0.05 \delta= 0.05 δ = 0.05 ± \pm ±
On Convex-3D and Two-group-10, respectively, 10 and 9 of the 500 Pareto BT-GLR T&S trials are capped (2.0% and 1.8%). These capped trials contribute 2.0 × 10 16 2.0\times10^{16} 2.0 × 1 0 16 1.8 × 10 16 1.8\times10^{16} 1.8 × 1 0 16
Figure 23. Benchmark comparison at δ = 0.05 \delta= 0.05 δ = 0.05 ± \pm ±
