Learning Correlated Reward Models: Statistical Barriers and Opportunities

Constantinos Daskalakis; Gabriele Farina; Sobhan Mohammadpour; Yeshwanth Cherapanamjeri

REVIEW 3 major objections 6 minor 15 references

Learning Correlated Reward Models: Statistical Barriers and Opportunities

T0 review · 3 major / 6 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Three-way choices reveal correlated preferences that pairwise comparisons cannot.

desk verdict Strong identifiability and estimation theory for correlated probit from full ranking triples; but the 'best-of-three' framing is misleading because winner-only data is a different, non-identifiable object, and the experiments overclaim. read the letter →

arxiv 2510.15839 v2 pith:XIKWTPES submitted 2025-10-17 cs.LG econ.EMstat.ML

Yeshwanth Cherapanamjeri , Constantinos Daskalakis , Gabriele Farina , Sobhan Mohammadpour This is my paper

classification cs.LGecon.EMstat.ML MSC 62F0762H1291B06

keywords randomutilitymodelscorrelatedprobitpreferencelearningRLHFidentifiabilitybest-of-threerankingspairwisecomparisonssamplecomplexity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Reward models built from human feedback typically assume independent utilities, which forces every user to share one universal utility and ignores correlations. This paper shows that with the correlated probit model, pairwise "A or B?" comparisons are fundamentally powerless to recover the covariance: infinitely many distinct models produce identical pairwise probabilities. It then proves that best-of-three ranking data is both necessary and sufficient to identify the mean and covariance, and gives a polynomial-time estimator achieving epsilon accuracy with about n^2 triple samples. Because triple-wise data is cheap to collect, the result makes correlated, personalized preference models practical in settings such as reinforcement learning from human feedback. Experiments confirm the theory: a probit trained on triples matches an oracle baseline and recovers interpretable correlations, while a pairwise-trained probit does not.

What carries the argument

The central object is the correlated probit model X ~ N(mu, Sigma), and the load-bearing identity is that a three-way ranking probability equals a difference of pairwise and two-dimensional wedge probabilities, so after whitening every wedge mass is a monotone function of the angle between two unit vectors. Those angles, together with normal-CDF-derived projections, determine the covariance's shape. For the global n-item problem, the machinery is a graph whose vertices are pairs of items and whose edges are shared triples, chosen as a sparse O(n^2)-edge graph with logarithmic diameter via per-anchor binary trees. The lower bound uses two zero-mean Gaussians differing only in one off-diagonal

What would settle it

Generate zero-mean correlated probit data from two normalized covariance matrices that differ only in one off-diagonal entry and have identical pairwise win probabilities; such pairs exist by the paper's construction. Feed best-of-three rankings to the proposed estimator and check that the recovered covariance separates the two models at the predicted O(epsilon^-2) sample rate, and feed pairwise rankings to any estimator and verify that the two models remain statistically indistinguishable at any sample size.

Watch

Extended reading notes

Core claim

The paper's central claim is that moving from pairs to triples removes a statistical barrier. Under a zero-sum normalization and full-rank condition, any Gaussian random utility model with at least three alternatives has infinitely many distinct mean-covariance pairs generating the same pairwise ranking probabilities, so pairwise data cannot identify correlation even before sampling noise. In contrast, three-way ranking probabilities determine the mean and covariance uniquely, and the paper constructs a polynomial-time estimator whose error in every coordinate is at most epsilon from N >= C n^2 epsilon^-2 gamma^-24 log(n/delta) log^6(n/(gamma epsilon)) independent triple rankings, with a mat

Load-bearing premise

The load-bearing premise is that all users' utilities come from one multivariate Gaussian distribution, normalized so utilities sum to zero, and that every triple ranking has probability at least gamma; if preferences are heterogeneous or multi-modal, or some rank-3 outcomes are nearly impossible, the identifiability and sample-complexity guarantees do not apply.

Editorial extensions

If this is right

Pairwise comparison datasets, as collected in many RLHF pipelines, cannot support recovery of correlated reward structure; the impossibility is information-theoretic, not a sample-size issue.
Best-of-three preference data is sufficient: a polynomial-time estimator recovers mean and covariance to accuracy epsilon from about n^2 epsilon^-2 triple rankings, and the sample count is near-optimal in n, epsilon, and confidence.
Triples-trained probit models match the performance of an oracle matrix-completion baseline on synthetic and real preference data, while pairwise-trained probit learns spurious or missing correlations.
Correlation-aware welfare optimization changes concrete recommendations: menus chosen with a triple probit differ from logit or pairwise choices, and can serve more users' top preferences.
Learned correlations are interpretable: sequels and similar items cluster positively, while divisive items and mainstream blockbusters are negatively correlated.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: because the identifiability argument only uses rank-3 probabilities, any higher-order query format that can be decomposed into triples, such as full rankings, should also be sufficient; the paper does not state this.
Editorial inference: the pairwise impossibility suggests that covariance estimates from existing pairwise-only pipelines are determined by regularization and initialization rather than by data; augmenting collection with triples is a cheap test of whether claimed correlations are real.
Editorial inference: the gamma dependence, requiring every triple ordering to have probability at least gamma, is likely improvable through adaptive sampling; the paper's lower bound does not address gamma.
Editorial inference: if real human preferences are a mixture of subpopulations, the single-Gaussian assumption is a misspecification; triple-order frequencies may still identify mixture components under a separation condition, an open direction the paper does not explore.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. First, the theoretical core is real: pairwise data provably cannot identify the correlated probit, while observing the full ranking of triples identifies (μ, Σ), and there is a near-optimal polynomial-time estimator with a matching lower bound. Second, the paper calls this "best-of-three" data, but the model and proofs use the full ordering—six permutation probabilities per triple, five independent degrees. Winner-only best-of-three, the standard RLHF annotation, gives two independent probabilities for three items and cannot identify the five-parameter model. The stress-test is right: the identifiability theorem does not transfer to winner-only data, and the experiments all use full rankings or ratings converted to rankings, so the practical message as written is unsupported.

What is actually new and good: Theorem 3.2 is a clean formalization of the folklore that pairwise comparisons lose correlation information; the proof is elementary and self-contained. The geometric identifiability argument in Section 4—project onto the plane, recover the isotropic transformation, then read off the covariance—is neat and convincing. The estimator is a real contribution: the graph construction cuts the number of triples from O(n^3) to O(n^2) with only logarithmic diameter, and error propagation is handled explicitly. The proofs are detailed; I did not find a load-bearing gap.

Soft spots. (1) The winner-only vs. full-ranking gap is the main issue. The abstract and title should say "full ranking of triples" unless the authors can prove something for winner-only data, which for n=3 they cannot. (2) The real-data experiments show mostly 0.01–0.03 accuracy gains over pairwise probit, with no error bars, yet the text claims "great improvement." That overstates the evidence; the synthetic results, where best-of-three clearly recovers correlations that pairwise methods miss, are much stronger and should be foregrounded. (3) Assumption 5.1—every permutation of every triple has probability at least γ—is strong, and the γ^{-24} dependence in Theorem 5.2 means the finite-sample guarantee is mostly of theoretical interest. Worth stating in the limitations. (4) The lower-bound KL derivation is a bit loose in presentation but the bound itself checks out; a few lines of cleanup would help.

Who is this for? Anyone working on choice models, preference learning, or RLHF data collection with an interest in what can be identified from ordinal feedback. The theory is solid, but the reader should not take the "best-of-three" label at face value. I would accept with major revision: clarify the data type, moderate the empirical claims, add error bars, and discuss the γ dependence and the homogeneous-Gaussian assumption.

Referee Report

3 major / 6 minor

Summary. This paper studies the correlated probit RUM X ∼ N(µ,Σ) on n alternatives, normalized as in Assumption 3.1 (mean on the hyperplane, Σ1=0, trace n, rank n−1). The main results are: (i) Theorem 3.2, pairwise comparison probabilities are not sufficient to identify the model; (ii) Theorems 4.1 and 4.4, the model is identifiable from three-way full-ranking probabilities P{X_i ≥ X_j ≥ X_k} for all permutations; (iii) Theorem 5.2, a polynomial-time estimator from rank-3 permutation data with N ≥ Cn² ε^{-2} γ^{-24} ... samples; (iv) Theorem 5.3, a minimax lower bound showing that Ω(n² ε^{-2}) queries are necessary. The paper also reports synthetic and real-data experiments comparing probit models fit from pairwise and three-way data, claiming improved personalization. The formal positive results are for full rankings of three alternatives, not for winner-only 'best-of-three' data, a distinction that matters for the paper's practical claims.

Significance. If the results are read as applying to full rank-3 permutation data, they are a valuable contribution: to my knowledge this is the first rigorous identifiability and finite-sample analysis for the correlated probit model from higher-order choice data, and the pairwise-insufficiency theorem explains a real gap in the literature. The lower-bound proof is a genuine minimax argument (Bretagnolle–Huber + Le Cam) and the upper-bound construction is non-circular: it builds estimators for 3-item triples and aggregates them via a sparse graph with logarithmic diameter. The sample-complexity dependence n² ε^{-2} is tight in n and ε. The paper also openly provides code. However, the matching of the formal object (full ranking) to the advertised object ('best-of-three') is not sound as written, and the experiments do not substantiate the 'great improvement' language. The theoretical core is defensible after revision.

major comments (3)

[§3 and §4 (Theorems 4.1, 4.4, 5.2)] The data model is stated inconsistently. §3 says observations are 'the choices arg max_{i∈R} X_i' for query sets R; for |R|=3 this is winner-only data. The positive results, however, are proved for the six three-way ranking probabilities P{X_i ≥ X_j ≥ X_k} (Figure 1, Theorem 4.4, Theorem 5.2). These are very different. For n=3 under Assumption 3.1 the model has four free parameters (two for μ on the plane, two for the rank-2 trace-normalized covariance), whereas winner-only best-of-three data has only three cell probabilities summing to one, i.e. two independent degrees of freedom. Identifiability from winner-only data is therefore impossible by dimension counting. Thus the paper's central slogan that 'best-of-three preference data provably overcomes' pairwise insufficiency is not supported unless 'best-of-three' is explicitly and prominently defined as a full ranking of the three altern
[§6, Table 2] The experimental validation is overstated. In Table 2 the best-of-three probit differs from logit or pairwise probit by at most 0.01–0.03 in most rows, and many entries are identical at the reported precision (e.g., ml-1k-llm all 0.57; nf-10k-llm all 0.59; sushi-B-default 0.65 for logit and best-of-three). No error bars, confidence intervals, or repeated-seed results are given, and Table 1 reports only quantile levels. The text claims 'great improvement' and the abstract claims 'improved personalization'; these claims are not supported by the displayed effect sizes. Please provide variance estimates, report the actual differences, or soften the conclusions.
[§E.1, Lemma 4.3 (and Claim E.3)] The proof of the key monotonicity step is incomplete for the zero-mean case. Claim E.3 states eξ'(θ) = −d1 − d2 cosθ / sin²θ < 0 for θ∈(0,π), but this is false when d1=d2=0, which is permitted by Assumption 3.1 and is in fact a case used in the experiments. Since Lemma 4.3 establishes identifiability of α12 from the monotone relation γ(θ), the proof as written does not cover μ=0. The lemma is true (for an isotropic Gaussian, γ12 directly determines arccos⟨v1,v2⟩), so this is a patchable gap, but it must be addressed explicitly.

minor comments (6)

[§E.2, Theorem 3.2 proof] The normalization is inconsistent: DIFF-FORM sets Tr(Σ)=n−1, but in Case 2 the text says Tr(eΣ)=n+ν and rescales with t=(n+ν)/n. This appears to be a typo and should be corrected.
[§4.1, Eq. (2)] The phrase 'by relaxing the scale constraint Tr ˙Σ = 1' is unclear because the preceding normalization is Tr(Σ)=n and, since P is orthogonal, Tr(˙Σ)=n. State the scale convention used in the construction.
[Theorem 5.2] 'given there is a polynomial time algorithm which when allowed N observations ... of its choice' should be rephrased and should specify whether the choice of triples is nonadaptive.
[Figure 2] The caption says 'two figures on the right'/'two figure on the left' but does not clearly identify which panels are pairwise, ground truth, and best-of-three; label the panels.
[§6, Table 2] Column headings 'dds. var. feat.' are not defined; please spell out the dataset variants and feature encodings.
[Assumption 5.1] The γ-dependence γ^{-24} makes the finite-sample guarantee very sensitive to rare orderings; a sentence discussing when this is reasonable for preference data would help the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the identifiability and estimation results are self-contained, with no fitted-input-as-prediction or load-bearing self-citation chain.

full rationale

I walked the derivation chain from the pairwise insufficiency result (Theorem 3.2) through the triple-wise identifiability theorems (Lemma 4.2, Lemma 4.3, Theorem 4.1, Theorem 4.4), the finite-sample estimator (Theorem B.1, Theorem 5.2), and the lower bound (Theorem 5.3). The proofs are constructive: they map observable three-way ranking probabilities to parameters via strictly monotone functions (e.g., Φ in Lemma 4.2, the monotone γ(θ) in Lemma 4.3) and invertible linear systems. No equation or parameter is defined in terms of the quantity being recovered, and no fitted subset is later relabeled as a prediction. The lower bound is a genuine minimax/Le Cam argument against arbitrary estimators, not a renaming of an input. The paper contains no self-citations used as load-bearing support for its central claims; the identifiability and estimation arguments are original and proved in the text. The skeptical concern that 'best-of-three' in the abstract may be read as winner-only data while the theorems require full rank-3 permutations is an external-validity/scope issue, not circularity: Theorem 5.2 explicitly quantifies over 'observations of rank-3 permutations from Choice(µ*,Σ*)'. Therefore the honest finding is no significant circularity, score 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No new entities or fitted constants are introduced. The only parameters (µ,Σ) are the targets of estimation, and γ is an explicit assumption governing observability of the data process.

assumptions (3)

domain assumption X ∼ N(µ,Σ) with ⟨µ,1⟩=0, Σ1=0, Tr(Σ)=n, rank(Σ)=n−1 (Assumption 3.1).
Defines the correlated probit model and removes the unidentifiable additive constant and scale by fixing trace and null-space of Σ.
domain assumption For every triple i,j,k, P{i ≻ j ≻ k} ≥ γ > 0 (Assumption 5.1).
Ensures all ordering events are observable; sample complexity scales as γ^{-24}, so it is load-bearing for finite-sample guarantees though not for identifiability.
standard math Standard concentration inequalities (Hoeffding, Bretagnolle–Huber) and Gaussian orthant probability monotonicity.
Used in proofs of Lemmas B.4, B.5, E.2 and Theorem 5.3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Learning Correlated Reward Models: Statistical Barriers and Opportunities." pith.science (2026). https://pith.science/paper/XIKWTPES

@misc{pith2026251015839,
  author       = {Pith},
  title        = {Pith review of: Learning Correlated Reward Models: Statistical Barriers and Opportunities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XIKWTPES}},
  note         = {Machine review of arXiv:2510.15839}
}

read the original abstract

Random Utility Models (RUMs) are a classical framework for modeling user preferences and play a key role in reward modeling for Reinforcement Learning from Human Feedback (RLHF). However, a crucial shortcoming of many of these techniques is the Independence of Irrelevant Alternatives (IIA) assumption, which collapses \emph{all} human preferences to a universal underlying utility function, yielding a coarse approximation of the range of human preferences. On the other hand, statistical and computational guarantees for models avoiding this assumption are scarce. In this paper, we investigate the statistical and computational challenges of learning a \emph{correlated} probit model, a fundamental RUM that avoids the IIA assumption. First, we establish that the classical data collection paradigm of pairwise preference data is \emph{fundamentally insufficient} to learn correlational information, explaining the lack of statistical and computational guarantees in this setting. Next, we demonstrate that \emph{best-of-three} preference data provably overcomes these shortcomings, and devise a statistically and computationally efficient estimator with near-optimal performance. These results highlight the benefits of higher-order preference data in learning correlated utilities, allowing for more fine-grained modeling of human preferences. Finally, we validate these theoretical guarantees on several real-world datasets, demonstrating improved personalization of human preferences.

Figures

Figures reproduced from arXiv: 2510.15839 by the authors.

**Figure 1.** The probabilities P {Xi ⩾ Xj ⩾ Xk}, for permutations, (i, j, k), of {1, 2, 3}, correspond to the probability mass in each of the six slices of the plane denoted 1 through 6 . This result will serve as the basis for the general case in Subsection 4.2. A probit model satisfying the constraints in Assumption 3.1 defines a bivariate normal distribution that lies in the plane defined by 1 ⊤X = 0. We start by projecting t… view at source ↗

**Figure 2.** Center: ground truth covariance matrix, two figures on the right, covariance matrix learned from [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Preference of the welfare maximizing choices, left to right for [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Larger version of the first row of Figure 2. Top to bottom rows: pairwise, ground truth, best-of [PITH_FULL_IMAGE:figures/full_fig_p041_4.png]

**Figure 5.** Figure 5: Larger version of the second row of Figure 2. Top to bottom rows: pairwise, ground truth, best [PITH_FULL_IMAGE:figures/full_fig_p042_5.png]

**Figure 6.** Figure 6: Two probit models where P(Y > X) = 0.5 (two leftmost) and P(Y > X) = 0.75 (two rightmost). gradient steps with a batch size of 10240 on matrix factorization models. We train the matrix factorization models with the Huber loss. For the probit models learned from 3-way c…

**Figure 7.** Figure 7: A probit model learned from best-of-three observation from sushi-a [PITH_FULL_IMAGE:figures/full_fig_p046_7.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

15 extracted references · 2 linked inside Pith

[1]

representation power, for instance, the logit cannot represent correlated choices,
[2]

OpenReview.net.https://openreview.net/forum?id=w1d9DOGymR Gerard Debreu. 1960. Reviewed Work: Individual choice behavior: A theoretical analysis.The American Economic Review50, 1 (1960), 186–188. Patrick Ding, Guido Imbens, Zhaonan Qu, and Yinyu Ye. 2024. Computationally Efficient Estimation of Large Probit Models.arXiv preprint arXiv:2407.09371(2024). Gu...

arXiv 1960
[3]

InForty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024

Position: A Roadmap to Pluralistic Alignment. InForty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net.https://openreview.net/ forum?id=gQpBnRHwxM Kenneth E Train. 2009.Discrete choice methods with simulation. Cambridge University Press. Alexandre B. Tsybakov. 2009.Introduction to nonparametr...

arXiv 2024
[5]

number of parameters, while the logit hasn=|C|parameters, the probit hasn(n+ 3)/2 parameters, and
[6]

whether they provide some notion of welfare. Representative agents models (RAM), are defined as P{I R =i}= arg max π∈∆(R) ⟨π, uR⟩ −ΩR(π) i , for some utility vectorurestricted the set of alternativeR, some strictly convex regularizer Ω R, and the probability simplex overRdenoted by ∆(R). RAMs also provide an expected welfare function, but learning a regul...

1988
[7]

In the first step, we show thatθis asolutionwith small error
[8]

β1i β1jp 1−β 2 1i q 1−β 2 1j # and bBij :=

Next, we show that all points outside a small interval aroundθhave large error. Claim B.9.We have: ∀s1 ∈ {±v1}, s2 ∈ {±v2}:ℓ s1,s2 (θ∗)⩽ 64ε γ p log(1/(γε)) ∥µ−bµ(θ∗)∥⩽4 ε γ . Proof.Observe from the rotational symmetry of a standard Gaussian that for anyu 1, u2 ∈S 1: PX∼N(0,I) {⟨X, u1⟩,⟨X, u2⟩⩾0}= 1 2 − arccos(⟨u1, u2⟩) 2π . Hence, applying Lemma B.2 with...
[9]

It requires comparison data forallof the Ω(n 3) sub-matrices

Show all 15 references

[10]

Observe that each potential sub-matrix corresponds to an edge of the graph and the vertices correspond to entries of Σ that we aim to recover

The sub-matrices need to be specifiedexactlywhich is infeasible with statistical noise To reduce the number of sub-matrices required, we formally relate our estimation guarantees to the structure of sub-graphs on the following graph: G= (V, E) V={{i, j} ∈[n]×[n] :i̸=j} E={({i,...
[11]

The sub-graph being connected suffices for recovering Σ from 3×3 sub-matrices
[12]

Lemma C.1.There exists a subgraphG ′ = (V, E′)withE ′ ⊂Esatisfying: |E′|⩽n 2 ∀v1, v2 ∈V: dist G′(v1, v2)⩽4(log(n) + 1)

The error of this aggregation process scaleslinearlywith thediameterof the sub-graph The next result (efficiently) constructs a sub-graph with drastically fewer edges (O(n 2) vsO(n 3)) while maintaining connectivity of the sub-graph with small (logarithmic) diameter. Lemma C.1...
[13]

For anyi∈[n], letV i = [n]\ {i}
[14]

Consider a complete binary treeT i = (Vi, Ei) onV i
[15]

the movie database

For any (j, k)∈E i, add edge ({i, j},{i, k}) toG′. First, observe thatE ′ ⊂Eby construction. Next, we have: |E′|⩽n· |Ei|=n(n−2)< n 2. For the final claim, we have from the construction ofE ′ andT i being a complete binary tree: ∀i̸=j̸=k̸=i: dist G′({i, j},{i, k})⩽2(log(n) + 1)...

2006
[2024]

InForty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27,

Position: Social Choice Should Guide AI Alignment in Dealing with Diverse Human Feedback. InForty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27,

2024

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

representation power, for instance, the logit cannot represent correlated choices,

[2] [2]

OpenReview.net.https://openreview.net/forum?id=w1d9DOGymR Gerard Debreu. 1960. Reviewed Work: Individual choice behavior: A theoretical analysis.The American Economic Review50, 1 (1960), 186–188. Patrick Ding, Guido Imbens, Zhaonan Qu, and Yinyu Ye. 2024. Computationally Efficient Estimation of Large Probit Models.arXiv preprint arXiv:2407.09371(2024). Gu...

arXiv 1960

[3] [3]

InForty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024

Position: A Roadmap to Pluralistic Alignment. InForty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net.https://openreview.net/ forum?id=gQpBnRHwxM Kenneth E Train. 2009.Discrete choice methods with simulation. Cambridge University Press. Alexandre B. Tsybakov. 2009.Introduction to nonparametr...

arXiv 2024

[4] [5]

number of parameters, while the logit hasn=|C|parameters, the probit hasn(n+ 3)/2 parameters, and

[5] [6]

whether they provide some notion of welfare. Representative agents models (RAM), are defined as P{I R =i}= arg max π∈∆(R) ⟨π, uR⟩ −ΩR(π) i , for some utility vectorurestricted the set of alternativeR, some strictly convex regularizer Ω R, and the probability simplex overRdenoted by ∆(R). RAMs also provide an expected welfare function, but learning a regul...

1988

[6] [7]

In the first step, we show thatθis asolutionwith small error

[7] [8]

β1i β1jp 1−β 2 1i q 1−β 2 1j # and bBij :=

Next, we show that all points outside a small interval aroundθhave large error. Claim B.9.We have: ∀s1 ∈ {±v1}, s2 ∈ {±v2}:ℓ s1,s2 (θ∗)⩽ 64ε γ p log(1/(γε)) ∥µ−bµ(θ∗)∥⩽4 ε γ . Proof.Observe from the rotational symmetry of a standard Gaussian that for anyu 1, u2 ∈S 1: PX∼N(0,I) {⟨X, u1⟩,⟨X, u2⟩⩾0}= 1 2 − arccos(⟨u1, u2⟩) 2π . Hence, applying Lemma B.2 with...

[8] [9]

It requires comparison data forallof the Ω(n 3) sub-matrices