Error Bounds for Statistical Estimators in BTL Model with Parametric Multivariate Utility Functions

1 Introduction

• The unconstrained canonical MLE can fail to be finite when realized responses are separated, even if the Fisher information matrix is positive definite.External constraints or regularizers can ensure finiteness, but estimates along escaping directions may then be determined primarily by regularization.Source: §1 · pp. 2–3
• For general covariates, graph topology alone does not capture the conic geometry of query directions, and existing bounds can be conservative for heterogeneous designs.The paper targets a design-dependent sufficient condition for an arbitrary fixed collection of pairwise queries.Source: §1 · p. 3

1.1 Main contributions

• The paper derives Cramér–Rao and minimax lower bounds whose Fisher-information criteria govern local efficiency and finite-sample difficulty under Euclidean and query-wise error measures.The model covers linear-in-parameter utilities subject to linear equality constraints and requires an identifiability condition.Source: §1.1 · p. 4
• A two-step convex localization strategy gives a design-dependent sample threshold above which the unconstrained MLE exists and is unique with high probability.The proof localizes the likelihood minimizer near the ground truth without imposing boundedness constraints or explicit regularization.Source: §1.1 · pp. 4–5
• The error decomposition separates a linear stochastic term, second-order bias, and higher-order remainder, while minimax-rate attainment depends on effective rank rather than the FIM’s extreme eigenvalue.The paper distinguishes sample sizes sufficient for MLE existence from those sufficient for minimax optimality.Source: §1.1 · p. 5

2.1 The Parametric Random Utility Model

• The utility framework uses a fixed feature map to make utility linear in an unknown parameter subject to equality constraints, encompassing discrete-choice and other specifications.The constraints can encode known structure or remove non-identifiable directions; the scale parameter is fixed because the response law is invariant to jointly scaling utility and scale.Source: §2.1 · pp. 6–7

2.2 Questionnaire and Responses

• The questionnaire design consists of selected alternative pairs and their presentation counts, while bounded dynamic range keeps response variance away from zero.Without repeated presentations, empirical choice frequencies cannot reliably estimate choice probabilities, so testing whether observed choices fit the model is outside the paper’s scope.Source: §2.2 · pp. 8–9

2.3.1 Identifiability

• After removing equality constraints by reparameterization, identifiability holds exactly when the joint rank condition combines feature structure, constraints, and the comparison graph.Unlike classical ranking models, the general linear utility model can be identifiable even on a disconnected comparison graph because parameters are shared across alternatives.Source: §2.3 · p. 9, §2.3.1 · p. 10

2.3.2 Likelihood Function

• Under the identifiability condition, the canonical MLE is the unique solution of an unconstrained convex program if it exists, but response-data separation can prevent existence.The Jeffreys-prior Firth correction guarantees existence under identifiability.Source: §2.3.2 · p. 12
• The joint rank condition is equivalent to positive definiteness of the design matrix, whose Fisher-information form approximates the comparison-graph Laplacian up to constants depending only on B.If the condition fails, adding constraints that eliminate the null-space directions yields an identifiable model.Source: §2.3.2 · p. 13
• Equation (2.25) projects θ⋆ onto the selected query directions’ span while preserving queried choice probabilities, with a unique augmented-model parameter matching them.Source: §2.3.2 · p. 13
• The comparison graph shapes information geometry through A and its null space, so connectivity alone is insufficient; selected edges and multiplicities determine W, which approximates the FIM.Source: §2.3.2 · p. 13

3.1 The Cram´er-Rao Lower Bound

• The section derives a Cramér–Rao inequality for locally unbiased estimators at a fixed ground-truth parameter.It introduces the local result for estimating a differentiable function h(θ) and notes that the lower bounds are compared with minimax rates.Source: §3.1 · p. 14

3.2 Minimax Lower Bounds

• When the parameter space is unbounded, every finite-valued estimator has infinite worst-case risk, making the minimax risk infinite.The passage also states that the candidate estimator class is empty when B = ∞.Source: §3.2 · pp. 15, 17
• The finite-sample Euclidean error lower bound is characterized by the same Fisher-information geometry as the local Cramér–Rao bound.For fixed bounded dynamic range, the passage states that σ²tr(W⁻¹) and tr(I(θ⋆)⁻¹) are comparable.Source: §3.2 · p. 17
• For fixed design features, an A-optimal design allocates comparisons to minimize tr(W⁻¹), targeting the criterion in the minimax lower bound.W can be positive definite even when the comparison graph is disconnected.Source: §3.2 · p. 17
• The minimax lower-bound analysis extends to canonical-link generalized linear models when the cumulant function has bounded second-order derivative.The section also reports that the canonical MLE attains the minimax benchmark up to logarithmic factors with high probability above a design-dependent sample threshold.Source: §3.2 · p. 17
• The coherence level μQ governs the query-wise minimax rate, complementing the trace-based geometry for Euclidean error.Together, trace- and coherence-type Fisher-information geometry characterize non-asymptotic performance in Euclidean and query-wise norms, respectively.Source: §3.2 · p. 18

Theorem 4.2

• The refined error expansion separates a centered linear stochastic term, deterministic second-order bias, and higher-order remainder.The bias may dominate the stochastic term over a nontrivial finite-sample regime without additional questionnaire structure.Source: §4 · pp. 19, 21

Theorem 4.1

• Under a design-dependent sample-size condition, the canonical MLE exists and is unique with probability at least 1-d^-c.Theorem 4.1 gives this guarantee when W ≻ 0 and the stated assumptions hold.Source: §4 · p. 19
• The existence condition alone does not ensure minimax scaling: the error bound has an additional term beyond its minimax-rate term.The section distinguishes the sample sizes sufficient for existence from those sufficient for minimax optimality.Source: §4 · p. 20

Corollary 4.1

• The excess-risk bound is optimal up to logarithmic and B factors, and its sample-size scaling improves on the quadratic one of Ostrovskii and Bach [52, Theorem 1.1].The comparison is with the minimax lower bound in excess risk.Source: §4 · p. 20

Localization

• Because likelihood curvature need not stay uniformly positive over the full parameter space, the analysis first localizes the MLE near the ground truth.The section notes that positive definiteness of the Hessian at the ground truth is insufficient for a global curvature lower bound.Source: §4 · p. 20

Theorem 4.2

• The MLE attains the query-wise minimax rate up to logarithmic and B factors when the sample size meets the refined design-dependent conditions.The stated dimensional requirement can improve on a quadratic dependence, up to logarithmic and B factors.Source: §4 · p. 21

Corollary 4.2

• For Euclidean minimax error, the additional sample-size dependence is summarized by the effective rank of the inverse Fisher information, not its extreme eigenvalues.Near-singularity can increase the absolute error bound without a corresponding increase in the required sample size.Source: §4 · p. 22

5.1 Implementation Details

• The experiments use D-optimal query allocations and 3000 Monte Carlo trials; Green-Flight simulations cross 367 respondents with 48 templates per destination.The Green-Flight ground truth is estimated from the survey responses using Firth correction, then used to generate BTL responses for the simulations.Source: §5.1 · p. 23, §5.3 · pp. 29–30

5.2 Synthetic Questionnaire

• The crossover sample size Ncross generally increases with ρ and decreases with r_e,tar; when r_e,tar=dθ, its distribution is invariant to ρ.Table 1 reports Monte Carlo means and standard deviations of αcross=log_dθ Ncross across the parameter grid.Source: §5.2 · p. 25, Table 1 · p. 25
• The MLE is absent in most synthetic trials for dθ ≤ N ≤ 2dθ, but its existence probability approaches one before the d^(3/2) scale; RMSE reaches the CRLB only at larger N.For dθ=50, RMSE nearly coincides with the CRLB at N≥1650; the existence condition is conservative in this instance.Source: Figure 4 · p. 26, Figure 5 · p. 26, §5.2 · pp. 27–28
• At N≈450, the synthetic MLE’s higher-order residual falls below its second-order bias; for N≥1650, its RMSE nearly coincides with the CRLB.Between N=450 and 900, the RMSE slope tracks the bias curve, even though the bias is already below the CRLB.Source: Figure 5 · p. 26, §5.2 · pp. 27–28
• For synthetic designs, Firth RMSE is comparable to the second-order bias at N=150–450 and approaches the CRLB as N exceeds 450.The authors describe Firth as a more reliable finite-sample default for the fixed-design setting and conjecture minimax optimality under additional conditions.Source: Figure 5 · p. 26, §5.2 · p. 28

5.3 The Green-Flight Questionnaire

• In the Green-Flight experiments, MLE existence is close to one by N≈192, while Euclidean and query-wise RMSEs remain substantially above their CRLBs.For DC, the RMSE–median gap and wide percentile ranges at N=55–295 indicate variable, right-skewed errors.Source: Figure 7 · p. 28, Figure 8 · p. 29, Figure 9 · p. 30
• For Green-Flight data, higher-order nonlinear terms dominate at small N, fall below the CRLB for N≥250, and the MLE RMSE then approaches the CRLB.Firth RMSE decreases steadily for N≥128 and nearly coincides with the CRLB at N=576.Source: Figure 8 · p. 29, Figure 9 · p. 30, §5.3 · p. 31

6 Concluding Remarks

• The paper derives Cramér–Rao and minimax lower bounds for general estimators, then establishes MLE existence and conditions for upper and lower bounds to meet up to constants.The analysis concerns linear-in-parameter utility functions under the BTL framework.Source: §6 · p. 31
• Extending the analysis beyond linear equality constraints to polyhedral parameter spaces could cover monotonicity or convexity constraints on utility functions.The current feasible parameter set is characterized by linear equations.Source: §6 · p. 31
• Whether analogous theory applies to nonlinear-in-parameter univariate utilities or the Plackett-Luce model remains unclear.Source: §6 · p. 31
• Extending the results to Bayesian learning could provide finite-sample posterior concentration rates; Jeffreys’ invariant prior is noted as yielding the Firth correction at its mode.Source: §6 · pp. 31–32

7.1.1 Proof of Theorem 3.1

• Theorem 3.1’s lower-bound proof uses a binary precoder/decoder, a feasible Rademacher subset, and bounds on weighted Hamming distance and total variation.The construction is designed to retain a sufficiently large set of feasible points.Source: §7.1.1 · pp. 33–35

7.1.2 Proof of Corollary 3.2

• Corollary 3.2’s proof derives an excess-risk lower bound from the Bernoulli KL lower bound and the same Hamming-distance argument.It then obtains the stated bounds by taking an infimum over estimators and adapting the preceding second-moment argument.Source: §7.1.2 · pp. 36–37

7.1.3 Proof of Theorem 3.2

• Theorem 3.2’s lower-bound proof constructs a separated two-point pair in the Q,∞ norm and controls its total variation through a KL bound.The proof verifies that both constructed parameters lie in the feasible set before applying the two-point method.Source: §7.1.3 · pp. 37–38

7.2.1 Proof of Theorem 4.1

• Theorem 4.1’s proof constructs a compact convex set on which the residual map is a self-map, enabling fixed-point localization and local strong convexity without the regularity conditions used in earlier approaches.The proof uses Brouwer’s theorem to obtain a stationary point; strict convexity of the negative log-likelihood then establishes uniqueness.Source: §7.2.1 · pp. 38–39, §7.2.1.2 · p. 41

7.2.1.1 Taylor Expansion of High-Order Residuals

• The likelihood-score expansion separates the estimation error into linear, second-order bias, and higher-order residual terms, and converts the residual into a fixed-point system.The analysis invokes pseudo self-concordance to control the higher-order remainder and Hessian variation.Source: §7.2.1.1 · pp. 39–40

7.2.1.2 Existence of Fixed Point

• The fixed point θ̂h is unique and lies in N(rH, r∞) with probability at least 1−d−c; the proof invokes N ≳ B^3μQdθ log d to recover (4.41a).Source: §7.2.1.2 · pp. 41–42

7.2.1.3 Local Strong Convexity

• The proof establishes 1/4-local strong convexity at θ⋆ and, under Lemma 7.8’s assumptions, places θ̂ in W∞,1/2 with probability at least 1−d−c.Source: §7.2.1.3 · p. 42

7.2.2 Proof of Theorem 4.2

• Theorem 4.2’s proof bounds the quadratic and higher-order error terms, using a vector-space Hanson–Wright inequality to control the quadratic term.The proof targets the bounds in (4.43) and (4.44).Source: §7.2.2 · pp. 43–44

A Proofs of Auxiliary Results

• The displayed argument concludes by deriving equation (4.44) from the preceding inequality.Source: A Proofs of Auxiliary Results · p. 47
• The appendix provides proofs of intermediate results needed in the paper’s main part.Source: A Proofs of Auxiliary Results · p. 47

A.1 Proof of Proposition 2.3

• Because the logistic link is strictly increasing, equal pairwise probabilities across selected comparisons are equivalent to equal linear predictors.The proof works in the injective reparameterization θ ↦ w_o + V_A⊥θ.Source: §A.1 · p. 47
• Equal linear predictors imply that A V_A⊥(θ − θ′) is constant on each connected component of the selected-comparison graph.Source: §A.1 · p. 47
• Full column rank of [C_I, A V_A⊥] forces both the component constants and θ − θ′ to vanish, proving identifiability.Source: §A.1 · p. 48
• If the rank condition fails, a nonzero solution yields distinct feasible parameters with identical selected-comparison probabilities, so the model is not identifiable.Source: §A.1 · p. 48

A.2 Proof of Corollary 2.1

• Null(W) = {0} is equivalent to condition (2.13), establishing the proof’s identifiability criterion.The argument uses the linear independence of the columns of CI.Source: §A.2 · p. 48
• When rank(W) = r < dθ, the refined model is identifiable by enforcing (2.13) and attaining rank([CI, AVA⊥Q+]) = r + K.The proof also constructs a refined parameter ˜w⋆ from w⋆.Source: §A.2 · p. 48

A.3 Proof of Proposition 3.2

• The proof of Proposition 3.2 considers feasible rays and constructs response realizations agreeing with the utility-difference signs along them.It presents the result as a generalization of [61, Proposition 17].Source: §A.3 · p. 49

A.4 Proof of Lemma 7.4

• Bernoulli KL divergence is expressed as the first-order Taylor remainder of Ψ.The displayed identity writes the remainder as Ψ(z) − Ψ(a) − Ψ′(a)(z − a).Source: §A.4 · p. 49
• Because Ψ′ is strictly increasing, the proof places z⋆ between a and b and bounds intermediate points within [−log B, log B].The proof assumes a ≤ b without loss of generality.Source: §A.4 · p. 49
• The remaining inequalities invoke Proposition 2.2 and the variance of the Bernoulli distribution.The supplied passage does not specify the resulting bound.Source: §A.4 · p. 50

A.5 Proof of Lemma 7.6

• The score equation at θ⋆ + ∆ is expanded around θ⋆ using the Hessian contributions of ∆lin, ∆bias, and h.The rearranged equation gives (7.80).Source: §A.5 · p. 50
• The error is decomposed as ∆ = ∆lin + ∆bias + h before rewriting the first-order optimality condition.The proof uses the definitions of ∆lin and ∆bias from (4.40).Source: §A.5 · p. 50

A.6.1 Deterministic residuals

• The deterministic residual lemmas control norms of the second-order bias and use projection and pseudo-self-concordance bounds.Lemma 7.8 relies on intermediate results controlling the Hessian-induced and Q,∞ norms.Source: §A.6 · p. 50, §A.6.1 · pp. 51–52

A.6.2 Random residuals

• The random-residual analysis provides tail bounds for ∆lin and bounds involving centered sub-Gaussian quadratic forms.The cited lemmas use union bounds and sub-Gaussian quadratic-form tail behavior.Source: §A.6.2 · pp. 52–53

A.6.3 Self-mapping property

• The self-mapping proof uses a Taylor expansion, treating Q2(∆lin) as the second-order bias and the other two terms as higher-order residuals.It bounds the map in both the Hessian-induced norm and the Q,∞ norm.Source: §A.6.3 · pp. 53, 54, 57
• On event E, STEP 1 verifies ∥Φ(h)∥∇²ℓ(θ⋆) ≤ rH for every h ∈ N(rH, r∞), establishing the stated neighborhood self-mapping bound.The cited sample-complexity bounds are N ≳ BµQdθ log d and N ≳ B²µQd^(3/2).Source: §A.6.3 · pp. 55–57

• A symmetric positive-semidefinite A admits a factorization A = BB⊤.Source: §A.7 · p. 59
• The entry bound is reduced to maxi∈[N] Aii, whose upper bound follows from Definition 3.2 and Proposition 2.2.Source: §A.7 · p. 59

A.8 Proof of Lemma A.4

• Bernstein’s inequality and Hanson-Wright inequality establish (A.110) and (A.111), respectively.The proof cites Bernstein’s inequality as [73, Theorem 2.8.4].Source: §A.8 · pp. 59–60

A.9 Proof of Lemma A.6

• The proofs of (A.114a)–(A.114c) derive tail and deterministic bounds using inequality (A.112) and Cauchy-Schwarz.Source: §A.9 · pp. 60–61

A.10 Proof of Corollary 4.2

• Corollary 4.2’s proof controls the linear and bias error terms, bounding the linear term with matrix Bernstein.The argument invokes a sample-size condition to compare intermediate bounds before applying the triangle inequality.Source: §A.10 · pp. 61–62

B Supporting Lemmas

• The supporting lemmas include concentration bounds for independent sub-Gaussian variables and random matrices, including Hanson-Wright [58], [1], and [68].Source: B Supporting Lemmas · p. 63