Maximum Likelihood Estimation for Entity Ranking under Iterative Synthetic Data Augmentation

1 Introduction

• Prior augmentation analyses leave high-dimensional ranking and entrywise error control largely unaddressed, motivating this paper’s non-asymptotic analysis.The cited work either relies on closed-form estimators or restrictive loss assumptions, and existing results mainly focus on ℓ2 error and low-dimensional asymptotics.Source: §1 · pp. 2–3
• The paper derives optimal finite-sample ℓ2 and ℓ∞ rates for iterative MLE under sparse comparison graphs, with guarantees that hold as the real-data fraction vanishes.The stated regime allows the number of iterations to grow polynomially in n, subject to log t ≤ c for a fixed c > 0.Source: §1 · p. 3
• The paper also establishes asymptotic normality for the iterative MLE and supports its theoretical results with numerical experiments and an Arena Human Preference 140K application.The introduction describes an induction argument and leave-one-out constructions to manage dependence across iterations and control error propagation.Source: §1 · p. 3

1.1 Related Works

• The related-work section reviews ranking and iterative synthetic-data retraining, including work on collapse in discard and augmentation workflows.It also surveys notation conventions and outlines the paper’s sections and appendices.Source: §1.1 · pp. 3–4, §1.2 · p. 5

1.2 Notation

• The paper uses N for nonnegative integers, [n] for {1, 2, …, n}, and standard asymptotic notation for comparing sequences.The roadmap assigns model formulation to §2, main theory to §3, numerical evidence to §4, proof ideas to §5, and technical proofs to Appendices A–F.Source: §1.2 · p. 5, §1.3 · p. 5

2 Model Formulation

• At each iteration, the current fitted model generates synthetic pairwise comparisons that are incorporated into the training data before retraining.The initial preference observations are human feedback drawn from the BTL model with ground-truth score θ⋆; later feedback is generated from the preceding round’s fitted model.Source: §2 · p. 6
• The latent score vector lies in a bounded range, and the parameter space imposes an identifiability condition for estimating it.The comparison graph is modeled as Erdős–Rényi, with each round’s graph independently generated and L independent outcomes observed for each compared pair.Source: §2 · p. 6
• The iterative MLE at each round is computed using all data accumulated so far, including original human comparisons and synthetic comparisons from prior rounds.Because synthetic data accumulate while the amount of original human data stays fixed, the real-data proportion gradually decreases.Source: §2 · pp. 6–7
• The analysis considers BTL ranking over sparse comparison graphs and targets optimal finite-sample ℓ2 and ℓ∞ rates and asymptotic normality, including regimes where the real-data share vanishes.The paper frames this as a high-dimensional ranking setting for which the behavior of cumulative augmentation had remained unclear.Source: §2 · pp. 6–7

3 Main Results

• The iterative MLE achieves optimal ℓ2 and ℓ∞ rates under a sparse comparison graph, even as the real-data fraction vanishes over polynomially many iterations.The bounds hold uniformly across iterations under the stated conditions.Source: §3 · p. 7, §3.1 · p. 8

3.1 Rate of Convergence of Iterative MLE

• Theorem 3.1 establishes non-asymptotic estimation-error bounds for the iterative MLE in both ℓ2 and ℓ∞ norms.The theorem's guarantees hold uniformly over iterations satisfying its conditions, with probability at least 1−O(n^-5).Source: §3.1 · p. 8
• The rate analysis treats a high-dimensional regime with growing item count and provides non-asymptotic, coordinatewise guarantees across dependent iterations.The authors describe Theorem 3.1 as the first theoretical characterization of ranking-estimator rates under iterative synthetic augmentation.Source: §3.1 · p. 8
• The rate theorem requires nLp ≳ (log n)^(3/2) and np ≳ (log n)^2, exceeding the np ≳ log n connectivity threshold.The passage attributes the gap to the technical challenge of controlling ℓ∞ error throughout iterative augmentation.Source: §3.1 · p. 8
• Under Corollary 3.1's conditions, the estimator achieves exact top-K identification with probability at least 1−O(n^-5).Exact identification means the estimated top-K set coincides with the true top-K set.Source: §3.1 · p. 9

3.2 Asymptotic Normality of Iterative MLE

• A leading-term-plus-residual expansion and martingale central limit theorem establish asymptotic normality for linear projections of the estimation error.The expansion's residual is of smaller order than its leading term under mild conditions.Source: §3.2 · p. 9
• For any fixed-size coordinate subset, the paper also derives a limiting joint distribution of the iterative MLE.This follows from the linear-projection result via the Cramér–Wold device.Source: §3.2 · p. 10
• The asymptotic-normality result requires nLp ≳ log n log T, stronger than the np ≳ log n connectivity requirement.The authors attribute this condition to residual-term control and a union bound over iterations, and leave relaxing it for future work.Source: §3.2 · p. 11

4.1 Baseline Setting

• In the baseline setting, estimation errors rise initially and then stabilize within a bounded range, with regularized and unregularized estimates following closely aligned trajectories.The top five estimated scores remain close to their true values and preserve their ordering; final estimates also align with the ground truth across ranked items.Source: §4.1 · p. 11, Figure 1 · p. 12

4.2 Rate of Convergence

• For n = 50 and n = 100, both ℓ2 and ℓ∞ errors scale approximately linearly with 1/√pL, and regularized and unregularized estimators perform nearly identically.The rates are evaluated at iteration T = 50 across the (p, L) pairs listed in Table 1.Source: §4.2 · pp. 11, 13, Table 1 · p. 11, Figure 2 · p. 13

4.3 Asymptotic Normality

• Across the tested settings, empirical quantiles for the first coordinate align closely with reference normal quantiles, supporting asymptotic normality.For n = 200, histograms of both standardized statistics follow the standard Gaussian density in settings (p, L) = (0.2, 2) and (0.4, 10).Source: §4.3 · pp. 13, 15, Figure 3 · p. 14, Figure 4 · p. 15

4.4 Application to Arena Human Preference 140k Dataset

• After 50 iterations, augmentation estimates remain close to their real-data starting values across 25 models, while Discard estimates diverge, especially at (p, L) = (0.2, 2).The augmentation workflow largely preserves the ranking; under Discard, estimates become highly dispersed and no longer meaningfully preserve it in the sparsest setting.Source: §4.4 · pp. 16–17, Figure 6 · p. 17
• Across 50 iterations, augmentation yields stable, well-separated top-five score trajectories, whereas Discard scores drift and fluctuate, even in denser settings.The four augmentation configurations produce nearly identical trajectories for each model.Source: §4.4 · p. 17, Figure 7 · p. 18

Proof Sketch of Theorem 3.1

• The proof assumes the bounds hold through iteration T and uses three steps to establish them at T + 1.Step I establishes a constant-sized ℓ∞ neighborhood of θ*.Source: §5 · p. 18

Step I

• A sufficiently small regularization parameter keeps the regularized estimator bounded with high probability, and the unregularized estimator stays close to it.Leave-one-out constructions control the gradient-descent trajectory coordinatewise so no coordinate strays too far from θ*.Source: §5 · p. 18

Step II

• Initializing gradient descent at θ(T) and using strong convexity yields geometric convergence while keeping the trajectory close to its initialization.This controls the ℓ2 and ℓ∞ increments from θ(T) to θ(T + 1); the next iterate's ℓ2 error then follows from the tower property and induction.Source: §5 · pp. 18–19

Proof Sketch of Theorem 3.1

• The proof represents the next iterate as a minimizer of a quadratic surrogate obtained by locally approximating the cumulative loss around θ(T).The representation permits direct control of the cumulative leading term, leaving the approximation error to be bounded at smaller order.Source: §5 · p. 19
• A martingale concentration inequality controls the cumulative leading term, while an approximation-error bound completes the induction.The argument uses Fan et al. (2024b) and the preceding induction hypotheses to show the approximation error is smaller order.Source: §5 · p. 19
• The induction closes by showing the leading term determines asymptotic variance while the smaller-order approximation error is asymptotically negligible.The same Step III result also supports the proof of Theorem 3.2.Source: §5 · p. 19

Discussion

• The iterative MLE achieves optimal ℓ2 and ℓ∞ rates under a sparse comparison graph, even when the real-data fraction vanishes over iterations.A coupled induction framework with leave-one-out constructions controls error propagation and establishes asymptotic normality; numerical experiments and the Arena Human Preference 140K study support the theory.Source: §6 · p. 19
• Future directions include incorporating covariates and extending the analysis to graphical interactive training with heterogeneous, interactive human preferences.The paper also proposes studying how AI training and evaluation can be integrated with those preference sources.Source: §6 · pp. 19, 21
• The theory requires nLp ≳ (log n)^(3/2), excluding the sparsest regime p = O(log n/n), where avoiding model collapse remains open.Extending the analysis to that regime remains technically challenging.Source: §6 · p. 21

Preliminaries

• The appendix states that the loss gradient and Hessian can be expressed using the canonical basis vectors.The gradient at the true parameter θ* is then controlled.Source: A Preliminaries · p. 28
• For an Erdős–Rényi graph, the appendix introduces degree concentration and states a high-probability bound when the graph is sufficiently dense.The stated event holds with probability exceeding 1 − O(n^−10) for large n.Source: A Preliminaries · p. 28
• The unnormalized Laplacian is associated with the comparison graph G(T), and its smallest eigenvalue is considered on vectors orthogonal to 1.The appendix next summarizes smoothness and strong convexity for the cumulative loss.Source: A Preliminaries · p. 28

B.1 The Regularized MLE

• A regularized MLE with λT = (T + 1)/n serves as an intermediate proxy, and gradient descent is analyzed toward its minimizer.The described algorithm initializes at θ*, so the text notes that it is not practical.Source: §B.1 · p. 29

B.2 Leave-One-Out Arguments and Induction Hypotheses for Iteration t ∈[T]

• Leave-one-out sequences and induction hypotheses track the primary and auxiliary updates through iteration T.The construction preserves the zero-sum constraint when 1⊤θ* = 0.Source: §B.2 · pp. 29–30

B.3 Leave-One-Out Arguments and Induction Hypotheses for Iteration t = T +1

• An iteration-restricted leave-one-out construction and a tertiary induction hypothesis control the transition from iteration T to T + 1.The restricted loss replaces likelihood components involving item m with their expected values at iteration T.Source: §B.3 · pp. 31–32

B.4 Step I

• Step I uses a regularized counterpart to keep the next iterate within a constant-sized ℓ∞ neighborhood of θ*.A sufficiently small regularization parameter keeps the unregularized iterate close to the regularized one; Lemma B.1 controls the Hessian spectrum.Source: §B.4 · p. 32

B.5 Step II

• Step II initializes a leave-one-out construction at θ(T) to control the increment θ(T + 1) − θ(T) in both ℓ∞ and ℓ2.The increment is split into deterministic bias and centered stochastic fluctuation terms, which are controlled separately.Source: §B.5 · p. 32

B.6 Step III

• Step III uses parallel leave-one-out constructions on the cumulative losses to show the approximation error is negligible relative to the iterate increment.The resulting bound controls the next iterate's ℓ∞ error.Source: §B.6 · p. 33

C Proof of Auxiliary Lemmas in Appendix A

• Appendix C supplies detailed proofs of the auxiliary lemmas used in the analysis.The appendix states that these building blocks are proved in detail.Source: C Proof of Auxiliary Lemmas in… · p. 33

• Lemma A.1 provides an upper bound for the gradient vector in ℓ2-norm.Source: §C.1 · p. 33
• Corollary C.2 uses a symmetric 1/2-net, Hoeffding’s inequality, and a union bound to obtain its probability claim.The net has log |V| ≤ C′n; the corollary holds with probability exceeding 1 − O(n−10).Source: §C.1 · pp. 33–35
• Corollary C.1 uses an Azuma-Hoeffding bound for a martingale difference array to establish its probability claim.Source: §C.1 · pp. 34–35

C.2 Proof of Lemma A.4

• For Lemma A.4, a matrix Chernoff argument gives the lower-bound result when p > c0 log n.The proof combines Lemmas C.1 and C.2; Lemma C.2 assumes G(T) is i.i.d. from Gn,p.Source: §C.2 · pp. 37–38

D.1 Proof Outline of Lemma B.1 in Step I

• The Step I outline uses leave-one-out sequences and induction hypotheses to keep the iterates close to θ* in ℓ∞-norm.It also states that the unregularized estimator is close to its regularized counterpart with high probability.Source: §D.1 · p. 38

D.1.1 Proof of Auxiliary Induction Hypothesis (A)

• For induction hypothesis (A), the proof controls the loss-gradient difference from its leave-one-out counterpart in ℓ2-norm.It then verifies (A) for the next step with probability at least 1 − O(n−10).Source: §D.1.1 · pp. 38, 40

D.1.2 Proof of Auxiliary Induction Hypothesis (B)

• The proof of induction hypothesis (B) combines earlier bounds and Corollary C.2 to establish (B) at the next step.Source: §D.1.2 · p. 40

D.1.3 Proof of Auxiliary Induction Hypothesis (C)

• For induction hypothesis (C), the proof combines inequalities and bounds to verify (C) at the next step.Source: §D.1.3 · pp. 42–43

D.1.4 Proof of Lemma B.1

• The proof of Lemma B.1 establishes a finite ℓ∞ error bound and related estimator bounds with probability at least 1 − O(n−7).The bound for θ(t+1) is stated under auxiliary induction hypotheses (A)–(C) and primary hypotheses (D)–(H).Source: §D.1.4 · p. 43

D.2 Proof Outline of Lemma B.2 in Step II

• An iteration-restricted leave-one-out construction keeps iterates close to θ(T) in ℓ∞ and supports verifying tertiary induction hypotheses through successive steps.The proof targets control of θ(T + 1) − θ(T) in both ℓ2 and ℓ∞.Source: §D.2 · p. 43

D.2.1–D.2.4 Proofs of Tertiary Induction Hypotheses (A1)–(D1)

• The proof verifies tertiary induction hypotheses (A1)–(D1) successively, with the (C1) step requiring p ≥ c0 log n for sufficiently large c0.The (D1) step also requires D8 ≥ D7 + D6.Source: §D.2.1 · p. 44, §D.2.2 · p. 46, §D.2.3 · p. 47

D.2.5 Auxiliary Lemmas

• The auxiliary hypotheses (A1)–(D1) hold for all υ ≤ υ∗ with probability at least 1 − O(υ∗n−10), and ensuing lemmas derive ℓ∞ and ℓ2 bounds for regularized counterpart θ(T + 1).Lemmas D.4 and D.5 assume (A1)–(D1) through υ∗ and (D)–(H) at iteration T; their statements give probability at least 1 − O(n−5).Source: §D.2.5 · p. 48

D.2.6 Proof of Primary Induction Hypothesis (E) and (F)

• The proof establishes primary induction hypotheses (E) and (F) for T + 1 when D2 ≥ D12 + 2D8 and D3 ≥ D11 + D12.Source: §D.2.6 · p. 49

D.2.7 Proof of Primary Induction Hypothesis (G)

• The increment θ(T + 1) − θ(T) is split into pseudo-inverse-Hessian bias and centered martingale fluctuation; operator-norm bounds and Azuma–Hoeffding control these terms.Under npL ≳ log n and the stated constant condition, the proof establishes (G) for T + 1.Source: §D.2.7 · pp. 49, 51, 52

D.3 Proof Outline of Lemma B.3 in Step III; D.3.1 Useful Auxiliary Facts

• The Step III outline combines arguments from the preceding steps, with auxiliary facts including an event holding with probability at least 1 − O(n−10).Lemma D.11 also gives a bound with probability exceeding 1 − O(n−10) under the auxiliary and primary induction hypotheses.Source: §D.3 · p. 52, §D.3.1 · pp. 52–53

D.3.2 Preliminary Results on the Leave-One-Out Quadratic Loss

• For any θ ∈ R^n, some v ∈ Ψ⊥ gives θ+v ∈ Θ; the iteration-restricted leave-one-out loss replaces m-th-item likelihood components with their iteration-t expectations.Source: §D.3.2 · pp. 53–54
• Lemma D.17 states that, under Theorem 3.1’s assumptions, a conclusion is asserted to hold with probability at least 1−O(n^-5); the supplied passage ends before specifying that conclusion.Source: §D.3.2 · p. 55

D.3.3 Proof of Primary Induction Hypothesis (H)

• Combining Lemmas D.10 and D.17 establishes Lemma B.3 and gives (H) at T+1 with probability at least 1−O(n^-5).Source: §D.3.3 · p. 56

E Proof of Theorem 3.2

• The proof outline uses a martingale difference array indexed by iteration, comparison edge, and replicate to verify the CLT conditions.Source: E Proof of Theorem 3.2 · p. 57
• Theorem 3.2’s proof reduces asymptotic normality to martingale CLT conditions, including Lindeberg and normalized quadratic variation.The proof constructs a fine-grained martingale difference array with a deterministic ordering.Source: E Proof of Theorem 3.2 · pp. 57–58

F.1.1 Proof of Lemma D.1

• Lemma D.1’s proof separates two terms in the gradient comparison and applies Bernstein and Hoeffding bounds.One stated condition is np ≳ log n.Source: §F.1.1 · pp. 62–63

F.2.1 Proof of Lemma D.2

• Lemma D.2’s proof invokes a standard optimization result for a strongly convex objective based on auxiliary regularized gradient descent.Source: §F.2.1 · p. 64

F.2.2 Proof of Lemma D.3

• The proof of Lemma D.3 defines a constrained unregularized MLE and uses Taylor expansion and convexity in its argument.Source: §F.2.2 · pp. 64–65

F.4.1 Proof of Lemma D.9

• Lemma D.9’s proof states its result holds with probability exceeding 1 − O(n−10).Source: §F.4.1 · p. 67

F.4.2 Proof of Lemma D.10

• Lemma D.10’s proof treats coordinatewise sums as sub-Gaussian martingale differences and applies a sub-Gaussian Azuma-Hoeffding inequality.The summands are described as independent, mean zero, and bounded conditional on the history.Source: §F.4.2 · pp. 67–68

F.4.7 Proof of Lemma D.14

• Lemma D.14’s proof applies Hoeffding’s inequality to averages of L independent Bernoulli variables and extends a bound across ordered pairs.The union-bound statement covers all i, j ∈ [n] with i ≠ j at probability at least 1 − O(n−10).Source: §F.4.7 · p. 71

F.4.8 Proof of Lemma D.15

• The proof bounds B1–B3 separately and combines them into a bound holding with probability at least 1 − O(n^-5).The bounds for B2 and B3 are combined with the bound for B1.Source: §F.4.8 · pp. 72, 75, 76

F.4.9 Proof of Lemma D.16

• Taylor expansion and difference estimates lead to a bound that holds with probability at least 1 − O(n^-5).The proof then summarizes the estimates using a constant c23.Source: §F.4.9 · pp. 77–78

F.4.10 Proof of Lemma D.17

• Lemma D.17 combines Lemmas D.15 and D.16 to obtain a high-probability bound with a constant D25 ≥ 2(D23 + D24).The proof states that the bound holds with probability exceeding 1 − O(n^-5).Source: §F.4.10 · p. 79