Debiasing Evaluations That are Biased by Evaluations

1 Introduction

• Student and author ratings remain widely used, despite potential unfairness, unreliable rankings, and incentives that can distort teaching or reviewer evaluation.The paper notes that ratings may reverse the true ordering and affect promotion, tenure, or reviewer awards.Source: §1 · p. 2

1.1 Our contributions

• The proposed estimator jointly estimates true qualities and bias under a known partial ordering, while cross-validation selects regularization through a designed validation error.The ordering is derived from observed outcomes such as grades or paper decisions.Source: §1.1 · p. 2, §1 · p. 2
• Theoretical analysis covers the estimator’s extreme regularization settings and cross-validation convergence, while synthetic and semi-synthetic experiments test broader settings.At λ = 0 and ∞, guarantees apply respectively to only-bias and only-noise settings.Source: §1.1 · p. 3

1.2 Related work

• Prior work adjusts grades across courses, but the paper identifies its nonparametric ordering constraint as distinctive and notes prior peer-review work does not address author feedback bias.The authors identify combining their method with prior peer-review approaches as future work.Source: §1.2 · p. 3
• The formulation connects to isotonic regression under total ordering with λ = 0 and x = 0, but its analysis differs from prior least-squares work because of the course-membership design.The cited least-squares results rely on assumptions such as random design or i.i.d. quality coordinates, which do not apply here.Source: §1.2 · p. 3
• The estimator also draws inspiration from permutation-based shape-constraint models, while its cross-validation requires a distinct scheme because order restrictions make samples nonexchangeable.The paper says classical cross-validation cannot be directly applied in this setting.Source: §1.2 · p. 3

2 Problem formulation

• Each rating is modeled as a course’s unknown true quality plus a bias term and a noise term.The model treats ratings from different courses as coming from distinct students and assumes the noise terms are i.i.d.Source: §2 · p. 4
• Observed outcomes, such as grades, define a known partial ordering requiring bias terms to respect the specified pairwise relations.A constraint orders the bias for one student-course pair below that for another.Source: §2 · p. 4
• The goal is to estimate true quality values from ratings and the ordering, with identifiability assumptions that the noise and aggregate bias have mean zero.Estimator performance is measured by normalized squared ℓ2 error.Source: §2 · p. 4

3 Proposed estimator

• The estimator optimizes over true qualities and ordered biases, penalizing bias magnitude to balance fitting the observations against overfitting noise.The optimization is a convex quadratic program, and the penalty strength λ controls the balance.Source: §3 · pp. 4–5

3.1 Behavior of our estimator under some fixed choices of λ

• At λ = 0 the estimator fits observations through ordered bias, while λ = ∞ sets bias to zero and reduces the estimate to the sample mean.Intermediate values gradually shrink estimated bias toward zero as λ increases.Source: §3.1 · p. 5

3.2 A cross-validation algorithm for selecting λ

• Cross-validation selects λ from a finite candidate set by splitting observations using an ordering consistent with the partial order and validating with interpolated bias estimates.The split is designed so each validation element has a nearby training element under the ordering.Source: §3.2 · pp. 5–6

18 end

• For each λ, the method fits on training observations, interpolates estimated bias onto validation entries, and selects the value with minimum validation error.For a given total ordering, interpolation uses the closest training element; ties use the mean of the two nearest bias estimates.Source: §18 · pp. 6–7

Implementation

• For each validation entry, the method’s interpolation step uses nearby training estimates under a consistent total ordering to synthesize a held-out bias estimate.The paper notes that sampling one ordering can make cross-validation error variable and can lead to choosing an excessively large λ.Source: §18 · p. 7, Implementation · p. 7

18 end

• Averaging interpolated biases over all consistent total orderings removes variance due to sampling a single ordering and supports a better λ choice.When iterating over all orderings is intractable, the method approximates their mean by sampling multiple orderings.Source: §18 · p. 7, Implementation · p. 7

4.1 Preliminaries

• The theoretical analysis focuses on group orderings and assumes iid Gaussian noise, marginally Gaussian bias assigned consistently with the partial ordering, and fixed d; the algorithm requires no knowledge of these distributions.The theoretical results apply to arbitrary x*.Source: §4.1 · p. 8

4.2 λ = 0 is consistent when there is no noise

• With no noise, λ=0 converges to x* for all-c-fraction group orderings, the specified two-course/two-group case, or any total ordering.The assumptions also imply consistent ranking of distinct course qualities; the ordinary mean is inconsistent under these conditions because it does not account for bias.Source: §4.2 · p. 9
• The λ=0 estimator consistently ranks distinct course qualities under the theorem’s conditions, while the ordinary mean is inconsistent because it does not account for bias.The ranking guarantee follows from convergence of the estimator to x*.Source: §4.2 · p. 9

4.3 λ = ∞is minimax-optimal when there is no bias

• With no bias, λ=∞ is well-defined and reduces the estimator to the sample mean, which is minimax-optimal for fixed d.The sample-mean guarantee applies in the no-bias setting.Source: §4.3 · p. 10

4.4 Cross-validation effectively selects λ

• With no noise, cross-validation’s estimator approaches the λ=0 solution under all-c-fraction group orderings or total orderings with d=2.The cross-validation algorithm is agnostic to σ, η, and the specific shape of bias or noise.Source: §4.4 · pp. 10–11
• With no bias, cross-validation’s estimator approaches the λ=∞ solution under single-c-fraction group orderings or interleaved total orderings with d=2.The sample mean is the λ=∞ endpoint, and cross-validation recovers it when no bias is present.Source: §4.4 · p. 11

5 Experiments

• The experiments measure squared ℓ2 error, compare cross-validation with mean, median, and reweighted-mean estimators, and simulate only-bias, only-noise, and mixed settings.Results are averaged over 250 runs; the best fixed λ is an empirical oracle unavailable in practice.Source: §5 · p. 12

5.1 Dependence on n

• With imbalanced bias, the estimator beats mean and median; in binary cases it slightly beats reweighted mean at only-bias/noise extremes, though cross-validation trails it in noisy settings.The comparison across n also includes the cross-validated and best fixed-λ estimator.Source: §5.1 · pp. 12, 14, Figure 1 · p. 13
• In the more balanced interleaving case, the estimator performs on par with mean and median while correcting small bias in the only-bias setting.Source: §5.1 · p. 14

5.2 Choices of λ by cross-validation

• Cross-validation selects small λ most often with only bias, large λ with only noise, and intermediate values when both are present, adapting to bias and noise levels.Source: §5.2 · p. 14, Figure 2 · p. 14

5.3 The regime of d > n

• When d grows beyond n, the estimator generally beats mean and median under bias, but performs poorly with only noise and non-interleaving order.For that exception, small λ can produce large error by explaining noise as bias; the setting lacks the constant-fraction interleaving assumption cited for Theorem 10(b).Source: §5.3 · pp. 14–15, Figure 3 · p. 16

5.4 General partial orderings

• On two non-group tree orderings, cross-validation beats mean and median when noise is present; against tree-specific reweighted means, it wins with only bias and is on par with noise.The best fixed λ performs better than the reweighted estimators when noise is present.Source: §5.4 · pp. 15, 17, Figure 4 · p. 17

5.5 Semi-synthetic grading data

• On semi-synthetic grading data, finer grade orderings improve both estimators; the proposed estimator is slightly better for fine grades and on some coarse-grade settings.For binary grades, both estimators’ error rises with relative bias, likely because the data are generated using fine grades.Source: §5.5 · pp. 18–19, Figure 5 · p. 18

• The cross-validation algorithm adapts without prior knowledge of the relative extents of bias and noise, a flexibility the authors say matters because such prior knowledge can be challenging to access.Source: §6 · p. 19
• Open theoretical questions include joint bias and noise, other partial orderings, non-asymptotic guarantees, and high-dimensional settings; bias mitigation during data elicitation is also left for future work.Source: §6 · p. 19
• The method addresses biases that obey user-provided information, not necessarily demographic biases; users should validate ordering constraints separately.Source: §6 · p. 19

• Appendix A presents auxiliary theoretical results comparing the proposed estimator with other estimators.Source: A Auxiliary results · p. 22
• Appendix A.1 compares the proposed estimator with the mean estimator.Source: A Auxiliary results · p. 22
• Appendix A.2 introduces a reweighted mean estimator and compares it with the proposed estimator.Source: A Auxiliary results · p. 22

A.1 Comparison with the mean estimator

• The mean estimator is consistent when each course has exactly cn students from each group, making bias evenly distributed across courses.Source: §A.1 · p. 23
• In the noiseless settings examined, λ=0 is consistent for course comparisons and quality estimates, while the mean estimator can fail at both.The mean estimator's failure can be arbitrarily severe because the probability of correct comparison or estimation may be arbitrarily small.Source: §A.1 · pp. 22–23

A.2 A reweighted mean estimator

• The reweighted mean balances group representation by reweighting observations so each group contributes equally across courses before averaging.Its weights correspond to sampling equal numbers from each group across courses.Source: §A.2 · p. 23
• Recentering is needed because reweighting aligns bias across courses but may leave the overall expected bias mean nonzero.The step also makes the empirical comparison with the proposed estimator fair.Source: §A.2 · p. 24
• The reweighted mean is undefined for total orderings; with constant group fractions it is consistent, yet λ=0 still beats it by a constant factor in a uniform-bias example.Source: §A.2 · p. 24
• At most half the squared ℓ2-risk of the reweighted mean, ignoring higher-order terms, is achieved by our estimator in the two-course, two-group noiseless example.The example assumes the specified opposing group grade distributions and uniform bias.Source: §A.2 · p. 24

B.1 Implementation

• The estimator is computed by course means at λ = ∞, a unique-solution QP for 0 < λ < ∞, and a convex QP with possible pre-tie-breaking multiplicity at λ = 0.For general group orderings, retaining only constraints involving each course-group's maximum and minimum observations, and adding their observation ordering, reduces constraints and speeds up the solver.Source: §B.1 · pp. 24–25
• For group orderings, total orderings are sampled by permuting elements within groups; for tree or group-tree orderings, the procedure recursively allocates positions among subtrees, and interpolation uses 100 sampled orderings.For trees, root elements receive the lowest-ranked positions; remaining positions are assigned uniformly at random among child subtrees.Source: §B.1 · p. 25

B.2 Extending the reweighted mean estimator to tree orderings

• The tree-ordering reweighted mean estimators replace groups with partitions by tree node or by tree level.The node partition groups all elements at the same node; the level partition groups all elements on the same tree level.Source: §B.2 · p. 25

B.3 Extending our estimator and the reweighted mean estimator to an unequal number of students per course

• With unequal course sizes, observations are represented in a padded matrix with an observed-element set, and estimation is restricted to that set.The reweighted mean uses only observed elements for reweighting and recenters on the restricted set; after recentering it satisfies the same empirical equality as the proposed estimator. Algorithm 1 is adapted to the observed-element count and per-course student counts.Source: §B.3 · pp. 25–26, The reweighted mean estimator · p. 26

C Proofs

• The proof appendix introduces notation and preliminaries for its theoretical claims, assumes each course contributes at least one element in considered sets, and ignores rounding because it does not affect the claims.For the proof setup, n is assumed even, with odd n handled by minor modifications.Source: C Proofs · p. 26, §C.1 · p. 26, §C.2 · p. 29

C.2.1 Properties of the estimator

• Under its tie-breaking rule, the estimator has a unique solution for every λ ∈ [0, ∞), and the λ = ∞ limiting solution exists.The appendix also establishes shift invariance: shifting all observations by a course-specific vector shifts the estimated course effects by that vector while leaving estimated bias unchanged.Source: §C.2.1 · pp. 29–30
• The cross-validation algorithm using the estimator is shift-invariant under the observation model.This follows from the stated shift-invariance corollary for the estimator.Source: §C.2.1 · p. 30
• When there are two courses and two groups with no noise, the estimator at λ = 0 has a closed-form solution under any group ordering.If some group is absent from a course, the corresponding case in that expression is ignored.Source: §C.2.1 · p. 31

C.2.2 Order statistics

• The order-statistics preliminaries state that Gaussian adjacent-order-statistic spacings converge to 0 and that order statistics converge to the inverse Gaussian c.d.f.The section also provides a bound on the maximum and minimum of i.i.d. Gaussian variables.Source: §C.2.2 · pp. 31–32

C.2.3 Additional preliminaries

• Additional preliminaries give deterministic relations for training-validation counts, bound rank gaps between adjacent elements across the split, and bound the mean of Gaussian bias terms.The rank-gap result applies to partitions produced by Algorithm 1; the mean bound assumes marginally N(0, 1) bias.Source: §C.2.3 · pp. 32–33

C.3 Proof of Theorem 5

• The proof of Theorem 5 establishes an estimator constraint for course pairs in S_c and shows that quality differences along a course cycle converge to 0 in probability.The constraint result assumes marginally Gaussian bias and no noise; the cycle result assumes a fixed number of courses.Source: §C.3 · pp. 33–34

C.3.1 Proof of part (a)

• For a fixed-length cycle of courses under the stated c-fraction condition, the estimated quality differences between any two courses in the cycle converge to 0 in probability.The proof of part (a) uses the all c-fraction assumption to make every course pair satisfy the condition defining S_c, forming a cycle.Source: §C.3 · pp. 33–34, §C.3.1 · p. 34

C.3.2 Proof of part (b)

• When course 2 has more students in the higher-bias group, the proof shows that the probability y2 − y1 > −ϵ tends to 1, using random assignment within groups.The closed-form estimator relation then gives bx2 − bx1 > −ϵ whenever y2 − y1 > −ϵ.Source: §C.3.2 · p. 35

C.3.3 Proof of part (c)

• The proof constructs hypernodes by merging cycles across groups, yielding consecutive course blocks whose elements’ ranks are also consecutive and increasing.Lemma 32 additionally states that any two courses in one hypernode lie on a cycle of length at most 2(d −1).Source: §C.3.3 · pp. 37–38
• Bounds within and across hypernodes support the proof’s contradiction: on the relevant event, an alternative solution preserves the ordering constraints but lowers the bias norm, ruling out that event.The proof concludes that the bad event intersected with E1 ∩ E2 ∩ E3 has probability zero, then invokes Lemma 21 to complete the probability bound.Source: §C.3.3 · pp. 38–42

C.4 Proof of Proposition 7

• When V = V*, (bx(∞), bB(∞)) is the unique solution for every λ > 0 and therefore equals the estimator’s limit as λ tends to infinity.When V > V*, the proof instead establishes that the bias norm tends to zero as λ tends to infinity.Source: §C.4 · p. 42
• The displayed inequality chain establishes that the objective at λ* is strictly greater than V.Source: §C.4 · p. 42
• Because the limiting pair attains objective V, the assumed solution at λ* leads to a contradiction, proving lim_{λ→∞} bB(λ) = 0.Source: §C.4 · p. 42
• The proof combines this limit with Lemma 16’s relation (20) to obtain a coordinate-wise statement for each i ∈ [d].Source: §C.4 · p. 42

C.5 Proof of Theorem 9

• The estimator remains consistent on any fixed Algorithm 1 training set for all-c-fraction group orderings or total orderings.The theorem generalizes the full-observation consistency result to these training sets.Source: §C.5 · p. 43
• With x*=0 and no noise, objective (15) attains zero at (0, B), giving Y_Ωt = [x̂(0)1^T + B̂(0)]_Ωt.This follows from the model and the objective’s value at (0, B).Source: §C.5 · p. 43

C.5.1 Proof of part (a)

• Algorithm 1’s interpolation makes the estimated bias close to the mean estimated bias over the training elements of a group.The proof uses this relation to analyze the λ=0 validation error.Source: §C.5.1 · p. 44
• For all-c-fraction group orderings, the proof combines consistency and concentration bounds to control the interpolated bias at λ=0.The cited corollary applies to any fixed training set obtained by Algorithm 1.Source: §C.5.1 · pp. 44–45
• The validation-error analysis separates contributions by course and group before combining the terms into a bound at λ=0.The proof identifies three terms and then bounds their combined contribution.Source: §C.5.1 · pp. 45–46
• The proof compares validation error at λ=0 with errors for λ in Λϵ, where the estimated quality norm exceeds ϵ.It aims to show that the latter errors are greater than the error at λ=0.Source: §C.5.1 · p. 46

C.5.2 Proof of part (b)

• The proof bounds validation error at λ=0 by combining three terms with the consistency result for the estimated quality.It then compares this bound with validation error for λ in Λϵ.Source: §C.5.2 · p. 48
• For total orderings, λ=∞ gives the per-course sample-mean estimator, while the proof treats λ=∞ and finite λ separately.For finite λ, it assumes a value in Λϵ and derives a contradiction to optimality.Source: §C.5.2 · pp. 49–51
• In the d=2 case, the argument uses non-overlapping validation pairs whose bias gap lies between 0 and c to lower-bound validation error.The pairs are drawn from the set S_c defined by 0 < b_2j′ − b_1j < c.Source: §C.5.2 · pp. 51–52

C.6 Proof of Theorem 10

• Under assumption (A3), d is constant, so the sample-mean estimator at λ = ∞ is consistent on the training set.At λ = ∞, the estimator is the per-course sample mean; the proof uses the model’s Gaussian-noise setting.Source: §C.6 · p. 53
• At λ = ∞, the estimated and interpolated biases are zero, and Hoeffding bounds control the validation error.The proof separately bounds terms T1, T2, and T3 before combining them.Source: §C.6 · pp. 53–54
• Lemma 41 supplies a deterministic relation bounding the estimated bias from the value of the estimator, for any non-empty observation set.It applies for every λ in [0, ∞].Source: §C.6 · p. 54

C.6.1 Proof of part (a)

• For finite λ, part (a) partitions Λϵ by the estimator’s value and bounds validation error using concentration inequalities and the single cf-fraction assumption.The proof combines the resulting cases with the λ = ∞ bound.Source: §C.6.1 · pp. 54, 55, 56, 59
• The part (a) proof combines bounds for both cases of finite λ with the validation-error bound at λ = ∞ to establish the theorem’s target inequality.The proof chooses constants depending on ϵ, d, and the single cf-fraction condition.Source: §C.6.1 · p. 59

C.6.2 Proof of part (b)

• The proof pairs validation interleaving points across two courses and uses their ordering to compare interpolated biases.The paired points have ranks t < t′, and nearest-neighbor interpolation makes the bias non-decreasing in rank.Source: §C.6.2 · pp. 60–62
• For finite λ, the proof divides cases by the estimator’s value, bounds the first three validation-error terms as in part (a), and handles the remaining term using ordered pairs.The four terms are combined to obtain the bound for each case.Source: §C.6.2 · pp. 60, 62, 63
• Combining the two finite-λ cases with the λ = ∞ bound establishes part (b)’s target inequality for d = 2.The proof selects constants depending on ϵ and cf.Source: §C.6.2 · p. 63

C.7 Proof of Proposition 11

• Proposition 11’s proof constructs partial orderings satisfying each of its three conditions and shows the mean estimator fails under each construction.The argument uses bias means that differ significantly across courses; the Gaussian bias standard deviation is set to σ = 1.Source: §C.7 · p. 63

C.7.1 Proof of part (a)

• Under an all-cf-fraction ordering, the mean estimator underestimates course 1 and overestimates course 2, despite true qualities satisfying x_1^* > x_2^*.The proof constructs the ordering and bounds course means to establish the claimed result.Source: §C.7.1 · pp. 64–65

C.7.2 Proof of part (b)

• For part (b), the proof specializes the part (a) construction to r = 2 groups and d = 2 courses.This specialization completes the proof of part (b).Source: §C.7.2 · p. 65

C.7.3 Proof of part (c)

• For part (c), the proof uses a non-interleaving total bias order, placing the n lowest-bias students in course 1 and the n highest-bias students in course d.The stated order is b_11 ≤ ... ≤ b_1n ≤ b_21 ≤ ... ≤ b_dn.Source: §C.7.3 · p. 65

C.8.1 The reweighted mean estimator

• 1/(24n) + 1/[96r(1-r)n] ≥ 1/(12n) for every r ∈ (0,1) in the reweighted-mean calculation.The derivation considers course 1 and uses symmetry between the two courses.Source: §C.8.1 · pp. 66–67

C.8.2 Our estimator at λ = 0

• E[γ^2] ≤ 6r^2n^2 + 6(1-r)^2n^2 + 8r(1-r)n^2 = c for some constant c > 0.The proof bounds the terms T2 and T3 by 6(1-r)^2n^2 and 4r(1-r)n^2, respectively, and combines them with T1.Source: §C.8.2 · p. 68

C.9.1 Proof of Proposition 14

• For full observations, tie-breaking gives a unique solution at λ = 0, while strict convexity and coercivity establish existence and uniqueness for λ > 0; uniqueness also extends to partial observations.The proof invokes the Projection and Weierstrass theorems [4].Source: §C.9.1 · pp. 69–70

C.9.2 Proof of Lemma 16

• The proof of Lemma 16 derives relation (19) for finite λ by minimizing over x and completing the square; for λ = ∞ it uses the closed-form solution.Source: §C.9.2 · p. 70

C.9.3 Proof of Lemma 17

• For Lemma 17, shifting every bias entry by a constant preserves the ordering and fitted values, so the proof compares solutions through the bias-norm penalty.The passage establishes invariance of the first objective term under this shift.Source: §C.9.3 · p. 70

C.9.4 Proof of Proposition 18

• The proof rules out a shifted alternative: at λ = ∞ it verifies the claimed result using closed-form expressions (3), while for λ ∈ [0, ∞) objective comparison on Y and tie-breaking yield contradiction.Source: §C.9.4 · p. 71

C.9.5 Proof of Lemma 20

• For fixed Ωt, Part (b) invokes Hoeffding’s inequality; separately, a contradiction setup assumes bx_i > 0 for all i ∈ [d] while showing that some bx_i′ ≤ 0.Source: §C.9.5 · p. 71

C.9.7 Proof of Proposition 22

• Proposition 22 determines the optimal γ by finding the range that satisfies cross-course ordering constraints, then minimizing the bias norm over that range.The proof states that this range is nonempty and that combining it with the norm minimization yields expression (24).Source: §C.9.7 · pp. 73–74

C.9.9 Proof of Lemma 24

• The convergence proofs reduce almost-sure convergence to convergence in probability and combine convergence of empirical inverse CDFs with convergence of order statistics.Source: §C.9.8 · p. 74, §C.9.9 · p. 74

C.9.10 Proof of Lemma 26

• For the split-set lemmas, consecutive-group counting yields the stated bounds when ℓik ≥ 4, while Lemma 27 rules out a rank gap ≥ 2d + 2 because Algorithm 1 splits a same-course pair across sets.Source: §C.9.10 · p. 74, §C.9.11 · p. 75

C.9.12 Proof of Lemma 28

• Lemma 28 establishes split-sample concentration by randomly assigning one element from each pair to training and using Hoeffding bounds and a union bound across courses.The union bound uses the assumption that d is constant.Source: §C.9.12 · pp. 75–76

C.10.1 Proof of Lemma 29

• Lemma 29 uses adjacent bias ranks and an ordering constraint to obtain the claimed bound on bx(0) with probability at least 1 − δ.The proof bounds the rank gap between the relevant course-specific bias terms, then bounds their value difference.Source: §C.10.1 · pp. 76–77

C.10.2 Proof of Lemma 31

• Lemma 31 applies Lemma 29 to the cycle’s pairs and uses telescoping coordinate differences to show bxi_m′ − bxi_m < ϵ.The proof first shortens cycles to length at most d and uses a union bound over their pairs.Source: §C.10.2 · p. 77

C.10.3 Proof of Lemma 32

• Induction shows every pair of courses in a hypernode lies on a cycle, and any such cycle can be shortened to length at most 2(d −1).The shortening removes repeated-course subpaths; the existence argument handles both courses in an existing hypernode and courses brought together by a merge.Source: §C.10.3 · p. 78

C.10.4 Proof of Lemma 33

• The graph argument establishes that hypernodes contain consecutive courses and ranks, are ordered consistently, and have edges only between adjacent hypernodes.It first constructs paths between courses in increasing order, then uses cycle contradictions to prove the consecutive-block properties.Source: §C.10.4 · p. 79

C.11.1 Proof of Theorem 34

• Theorem 34(a) follows by adapting Lemma 29 and Lemma 31 to the training set Ωt, with rank differences bounded with high probability.The proof bounds ranks of training-restricted maximum and minimum biases relative to their unrestricted counterparts, then reuses the original arguments.Source: §C.11.1 · pp. 79–80
• For Theorem 34(b), the proof restricts the total ordering to Ωt, bounds adjacent-rank gaps, and adapts Lemma 29, Lemma 31, and the remaining original arguments.For pairs in St′, the corresponding ranks satisfy k′ −k ≤2d + 1.Source: §C.11.1 · pp. 80–81

C.11.2 Proof of Lemma 35

• Lemma 35 separates orderings by whether validation-item nearest neighbors stay within its group: within-group averages yield the group training bias, while cross-group neighbors occur with low probability.A cross-group nearest neighbor can come only from an adjacent group, and the proof bounds the fraction of orderings producing such neighbors under the all cf-fraction assumption.Source: §C.11.2 · pp. 81–82

C.11.3 Proof of Corollary 36

• The Corollary 36 proof combines Lemma 35 with bounds on the maximum bias to complete its stated argument.The supplied passages show these ingredients being substituted into the corollary’s bound, but do not provide its conclusion in readable form.Source: §C.11.3 · p. 83

C.11.4 Proof of Lemma 37

• Lemma 37 applies Hoeffding’s inequality without replacement and a union bound under the all c-fraction assumption to establish (75a) and (75b).The proof first conditions on the bias and bounds validation-group means, then controls the bias range and takes a union bound over courses and groups.Source: §C.11.4 · pp. 83–84

C.11.5 Proof of Lemma 39

• The Lemma 39 proof invokes Lemma 51 and derives a closed-form solution to (239) by setting the objective’s derivative with respect to u to zero.The passage states that the resulting unconstrained solution is u∗, but does not include its formula.Source: §C.11.5 · pp. 84–85
• The unconstrained solution is also a constrained solution to (239); substituting (240) into the objective completes the proof.Source: §C.11.5 · p. 85
• PAVA returns the squared-distance projection of any y in R^d onto M, as established by induction over its iterations [2, Section 1.2].The iteration sequence starts at y and ends at Π_M y.Source: §C.11.5 · p. 85
• At each iteration, PAVA merges adjacent violating blocks, and the proof verifies that the projection minimizer is preserved across the merge.The merged block receives the weighted average of the two block values.Source: §C.11.5 · pp. 85–86

C.11.6 Proof of Lemma 40

• After trimming the non-overlapping pairs, each survives the training-validation split with probability 1/4 independently, and Hoeffding’s inequality completes the proof of Lemma 40.The two removals leave at least c′n/4 pairs whose elements occur in different split pairs.Source: §C.11.6 · p. 87
• The proof reduces Lemma 52 to finding linearly many non-overlapping pairs in Rγ,c, then uses rank-placement arguments and a Gaussian order-statistic bound to establish the needed existence claim.Rγ,c is shown to lie within Sc with high probability, so it suffices to lower-bound its non-overlapping pairs.Source: §C.11.6 · pp. 88–90

C.11.7 Proof of Lemma 53

• Under assumption (A2), Rγ,c is contained in S2c on the stated high-probability event, by bounding Gaussian order statistics across rank intervals.For pairs in Rγ,c, the ranks imply b2j′ > b1j; the proof bounds the bias difference to obtain the inclusion.Source: §C.11.7 · p. 91

C.11.8 Proof of Lemma 54

• The Lemma 54 proof conditions on seven Gaussian order statistics, defines a range A whose probability tends to one, and shows T < 0 there for sufficiently small γ.The conditional bounds use Hoeffding’s inequality and combine the terms in T.Source: §C.11.8 · pp. 92, 94

C.12 Proof of auxiliary results for Theorem 10

• Section C.12 introduces proofs of auxiliary results for Theorem 10.Source: §C.12 · p. 94

C.12.1 Proof of Lemma 41

• For Lemma 41, the λ = ∞ case follows directly from Proposition 7; for finite λ, the proof reduces the desired bound using the triangle inequality and an alternative solution B′.It fixes Y and x, sets U := Y − x1ᵀ, and bounds the observed entries of U by those of Y plus ∥x∥∞.Source: §C.12.1 · p. 94
• The Lemma 41 proof constructs an ordering-feasible B′ with a strictly smaller objective, contradicting the assumed optimality of B(λ).B′ satisfies the partial ordering because B(λ) does.Source: §C.12.1 · pp. 94–95

C.12.2 Proof of Lemma 42

• The Lemma 42 proof invokes a monotone-cone projection bound, Moreau decomposition, and Markov’s inequality.The cited projection bound is E[Π_M Z] ≤ c√log d [1, Section 3.5]; the Moreau decomposition reference is [50, Eq. 20].Source: §C.12.2 · p. 95

C.12.4 Proof of Lemma 44

• For Lemma 44, the proof uses interleaving to form distinct pairs, applies Hoeffding’s inequality to lower-bound validation-set size, and takes a union bound over four sets.The sets are S+∩S1, S−∩S1, S+∩S2, and S−∩S2.Source: §C.12.4 · p. 96