Learning Correlated Reward Models: Statistical Barriers and Opportunities

## Abstract

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 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 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 fundamentally insufficient to learn correlational information, explaining the lack of statistical and computational guarantees in this setting. Next, we demonstrate that 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.

## 1 Introduction

Random Utility Models (RUMs) (Train, 2009) are the leading framework for modelling human preferences. Classical applications dating back to the 1960s include mathematical psychology (Luce, 1959), transportation science (Ben-Akiva, 1973), econometrics (McFadden, 1980), and marketing (Rust and Zahorik, 1993). More recently, they are a core component of the Reinforcement Learning from Human Feedback (RLHF) pipeline (Christiano et al., 2017), used to align Large Language Models (LLMs) with human preferences. Unfortunately, many classical RUMs adopt the Independence of Irrelevant Alternatives (IIA) assumption. In the context of LLMs, the IIA posits a universal underlying utility function for all users of a system. A growing body of work highlights the limits of this approach in capturing the full range of human preferences (Bai et al., 2022; Casper et al., 2023; Sorensen et al., 2024; Anwar et al., 2024; Conitzer et al., 2024).

Formally, a RUM models utilities over a set of $n$ items as a high-dimensional random vector, $X$(^1^11For RLHF, the items correspond to (prompt, response) pairs). A classical choice is the logit model, where each component $X_{i}$ is independent and distributed according to a Gumbel distribution $X_{i}\thicksim\mathrm{Gumbel}(\mu_{i})$. The IIA assumption implies that for any unobserved item (or response), the model assigns the same average utility irrespective of the user’s past preferences.

In this paper, we investigate the statistical challenges of learning correlated utility models, focusing in particular on the correlated probit model where $X\thicksim\mathcal{N}(\mu,\Sigma)$. By explicitly modeling correlations, these techniques allow past user behavior to inform future responses, providing a more accurate representation of human preferences. However, in contrast to the logit model, little is known about the statistical and computational challenges of learning these models: i) What data is needed to learn them? and ii) How many samples do we need?

We make key advancements on several fronts: 1) We show that the conventional paradigm of pairwise preference data is fundamentally insufficient to learn these models, 2) On the other hand, three-way-preference data is both necessary and sufficient and finally, 3) Validate the efficacy of higher-order preference data in accurately modelling correlated user preferences. Our results highlight fundamental drawbacks in conventional data collection pipelines and suggest deliberate amendments to address these shortcomings. Prior to our work, even identifiability results, disregarding any statistical considerations, did not exist. Hence, we establish the first identifiability guarantees and complement them with a near-optimal polynomial-time estimator.

## 2 Related work

A wealth of ideas exists for modeling rewards. However, we focus on choice modeling, where subjective preferences between items are expressed. Consequently, we find a treatment of reward models like step-wise reward models (Havrilla et al., 2024) and process reward models (Luo et al., 2023) beyond the scope of this work. We are interested in models that can make counterfactual choices from preference data. Outside of machine learning, choice models have been successfully applied to planning problems like public transport scheduling (Wei et al., 2022), effect of price markups (Gallego and Wang, 2014), airline scheduling (Wei et al., 2020), EV charging station placement (Lamontagne et al., 2023), and toll placement Osorio and Atasoy (2021).

Random Utility Models (RUMs) are among the most common models of human behavior in mathematical psychology, econometrics, transportation, and marketing (e.g., see McFadden, 2001, a Nobel Prize lecture on RUMs). RUMs impose structure on the choice model by assuming that the agents are rational, meaning that when confronted with a finite set of alternatives, they choose the one that maximizes their (latent) utility. The agent’s unobserved utility is commonly modeled as a random variable to acknowledge the heterogeneity of utilities. Formally, an agent is assumed to have a random utility vector $X$, where $X_{i}$ is the utility of choosing some alternative $i$ from the set of all possible alternatives $\mathcal{C}$, and, when presented with a subset $\mathcal{R}\subseteq\mathcal{C}$ of alternatives, the agent chooses the alternative $I_{\mathcal{R}}$ satisfying

$$ $I_{\mathcal{R}}\in\arg\max_{i\in\mathcal{R}}X_{i}.$ $$

Given observations of the form $(\mathcal{R}^{t},I_{\mathcal{R}^{t}}^{t})$, $t=1,\ldots,T$, a common challenge is to learn the distribution of the latent $X$. Obtaining an estimate $\tilde{X}$ of $X$ not only gives us an estimate $\tilde{I}_{\mathcal{R}}$ of $I_{\mathcal{R}}$ for any subset of alternatives $\mathcal{R}$, but it also allows making predictions about the welfare of $\mathcal{R}$, $G(\mathcal{R}):=\max_{i\in\mathcal{R}}X_{i}$. It is important to note that learning the distribution of $X$ from preference data is inherently underconstrained as adding the same potentially stochastic value to all components of $X$ yields no change in the distribution of $I$.

The most popular RUM is the logit (Train, 2009, Chapter 3) or also sometimes referred to as Luce -Shephard-McFadden model, or, in the binary case (i.e. $|\mathcal{C}|=2$), the Bradley-Terry model. The logit is the only RUM that satisfies independence of irrelevant alternatives (IIA) (Luce, 1959), that is, the ratio of the probabilities of choosing two alternatives is independent of the presence of other alternatives. The logit enjoys many useful properties, for instance, it can be learned using pairwise comparisons, it can learn any distribution over the set of full alternatives(^2^22by setting the utilities to the log probabilities), and is easy to calculate via a softmax. Unfortunately, if the utilities are correlated, the logit cannot be used to make correct counterfactual predictions. A classical example showcasing this impossibility is the red bus/blue bus problem introduced by Debreu (1960). If half of the populations prefer red buses over blue buses and half of the population prefers red buses made by company A over those made by company B, then IIA implies that 2/3 of the population prefers red buses made by A or B over blue buses, a contradiction. In practice, as shown by Benson et al. (2016), many datasets do not satisfy the IIA assumption. We continue our discussion on choice modeling in Appendix [A](https://arxiv.org/html/2510.15839v1#A1)

## 3 Problem Setup, and the Need for Best-Of-Three Observations

Here, we avoid the restrictive IIA assumption and assume, instead, that the utilities follow the classical probit model with $X\thicksim\mathcal{N}(\mu,\Sigma)$. We aim to recover $(\mu,\Sigma)$ from only the choices $\arg\max_{\left\{i\in\mathcal{R}\right\}}X_{i}$ made for various subsets $\mathcal{R}\subset{\left[n\right]}$. For binary choice, $\mathcal{R}$ is pairs of elements $(i,j)\in{\left[n\right]}^{2}$. Similarly, for the three-way choice setting, $\mathcal{R}$ is triplets $(i,j,k)\in{\left[n\right]}^{3}$. Note that $(\mu,\Sigma)$ are not fully identifiable in this setting: for any $X\thicksim\mathcal{N}(\mu,\Sigma)$, $X^{\prime}$ defined as

$$ $t{\left(X-\frac{1}{n}\sum_{i}X_{i}\right)},$ $$

for any $t>0$, induces the same ranking probabilities.
Hence, we adopt the following necessary normalization $\mu,\Sigma$.

###### Assumption 3.1 .

For $X\thicksim\mathcal{N}(\mu,\Sigma)$, we assume, without changing the choice distributions, that

$$ $\langle\mu,\bm{1}\rangle=0,\quad\Sigma\bm{1}=0\text{, and}\quad\operatorname*{\mathrm{Tr}}(\Sigma)=n.$ $$

Consequently, $X$ lives on the hyperplane $\bm{1}^{\top}X=0$. Furthermore, we assume $\Sigma$ has rank $n-1$.

Unfortunately, the classical paradigm of pairwise comparisons ($|\mathcal{R}|=2$) is insufficient for recovering $(\mu,\Sigma)$, even accounting for [Assumption 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1). Its proof is deferred to [Subsection E.2](https://arxiv.org/html/2510.15839v1#A5.SS2).

###### Theorem 3.2 .

For any $n\geqslant 3$ and $\mu,\Sigma$ satisfying [Assumption 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1), there exists an infinite set $\mathcal{S}$:

$$ $\forall i,j\in[n],\mu^{\prime},\Sigma^{\prime}\in\mathcal{S}:\operatorname*{\mathbb{P}}_{X\thicksim\mathcal{N}(\mu,\Sigma)}{\left\{X_{i}\geqslant X_{j}\right\}}=\operatorname*{\mathbb{P}}_{X\thicksim\mathcal{N}(\mu^{\prime},\Sigma^{\prime})}{\left\{X_{i}\geqslant X_{j}\right\}}.$ $$

[Theorem 3.2](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem2) indicates that pairwise comparison data is fundamentally unable to account for correlations in the probit model. While the full proof of [Theorem 3.2](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem2) is somewhat involved, the particular setting with $\mu=0$ is instructive. Here, observe that for any pair of distinct alternatives, $i,j$, the probability that $X_{i}\geqslant X_{j}$ is $1/2$ irrespective of the value of $\Sigma$. Hence, correlational information is fundamentally impossible to learn given only access to pairwise comparisons.

###### Assumption 3.1 .

###### Theorem 3.2 .

## 4 Identifiability

[Theorem 3.2](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem2) prompts the natural question: can higher order preference data help?
We answer the question in the affirmative and show that best-of-three observations ([Theorem 4.4](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem4)) are sufficient and from [Theorem 3.2](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem2), necessary to recover $\mu,\Sigma$. Observing that:

$$ $\operatorname*{\mathbb{P}}{\left\{X_{i}\geqslant X_{j}\geqslant X_{k}\right\}}=\operatorname*{\mathbb{P}}{\left\{X_{j}\geqslant X_{k}\right\}}-\operatorname*{\mathbb{P}}{\left\{X_{j}\geqslant X_{i},X_{k}\right\}},$ (RANK-PROB) $$

we may assume access to three-way ranking probabilities.

### 4.1 The Case of Three Alternatives

As a stepping stone towards identifying probit models with an arbitrary number $n$ of alternatives, we focus on the case $n=3$ and establish the following theorem.

###### Theorem 4.1 .

$(\mu,\Sigma)$ are uniquely identifiable from the three-way observation probabilities.

This result will serve as the basis for the general case in [Subsection 4.2](https://arxiv.org/html/2510.15839v1#S4.SS2).
A probit model satisfying the constraints in [Assumption 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1) defines a bivariate normal distribution that lies in the plane defined by $\bm{1}^{\top}X=0$. We start by projecting the utilities onto a lower-dimensional space:

$$ $\begin{bmatrix}V_{1}\\ V_{2}\end{bmatrix}\coloneqq\underbrace{\begin{bmatrix}1/\sqrt{6}&1/\sqrt{6}&-2/\sqrt{6}\\ 1/\sqrt{2}&-1/\sqrt{2}&0\end{bmatrix}}_{=:\ P}\begin{bmatrix}X_{1}\\ X_{2}\\ X_{3}\end{bmatrix}\quad\leftrightarrow\quad\begin{bmatrix}X_{1}\\ X_{2}\\ X_{3}\end{bmatrix}=\underbrace{\begin{bmatrix}1/{\sqrt{6}}&1/{\sqrt{2}}\\ 1/{\sqrt{6}}&-1/{\sqrt{2}}\\ -2/{\sqrt{6}}&0\\ \end{bmatrix}}_{=:\ P^{\top}}\begin{bmatrix}V_{1}\\ V_{2}\end{bmatrix}.$ (1) $$

Under the transformation $P$, the probit model $X\sim\mathcal{N}(\mu,\Sigma)$ is mapped to some bivariate normal distribution $V\sim\mathcal{N}(\dot{\mu},\dot{\Sigma})$.
Upon identification of the parameters $\dot{\mu}$ and $\dot{\Sigma}$ in two dimensions, we recover the original parameters $\mu$ and $\Sigma$ through the transformation:

$$ $\mu=P^{\top}\dot{\mu},\qquad\text{and}\quad\Sigma=P^{\top}\dot{\Sigma}P.$ $$

Defining,

$$ $c_{1}:=\begin{bmatrix}0\\ 1\end{bmatrix},\qquad c_{2}:=\begin{bmatrix}\sqrt{3}/2\\ -1/2\end{bmatrix},\qquad c_{3}:=\begin{bmatrix}\sqrt{3}/2\\ 1/2\end{bmatrix},$ $$

the probability of the events $\{X_{i}\geqslant X_{j}\}$, are satisfy the following:

$$ $\operatorname*{\mathbb{P}}\{X_{1}\geqslant X_{2}\}=\operatorname*{\mathbb{P}}\{c_{1}^{\top}V\geqslant 0\},\quad\operatorname*{\mathbb{P}}\{X_{2}\geqslant X_{3}\}=\operatorname*{\mathbb{P}}\{c_{2}^{\top}V\geqslant 0\},\quad\operatorname*{\mathbb{P}}\{X_{1}\geqslant X_{3}\}=\operatorname*{\mathbb{P}}\{c_{3}^{\top}V\geqslant 0\},$ $$

with each three-way permutation corresponding to the intersections of the corresponding halfspaces. The projection and the partitioning of the 2-dimensional space are illustrated in [Figure 1](https://arxiv.org/html/2510.15839v1#S4.F1).

Figure: Figure 1: The probabilities $\operatorname*{\mathbb{P}}{\left\{X_{i}\geqslant X_{j}\geqslant X_{k}\right\}}$, 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.
Refer to caption: x1.png

We will further transform $V$, rendering the distribution isotropic. Define $\dot{\Sigma}^{-1/2}$ as a solution of

$$ $\dot{\Sigma}^{-1/2}\dot{\Sigma}(\dot{\Sigma}^{-1/2})^{\top}=I.$ $$

Note that $\dot{\Sigma}^{-1/2}$ is unique up to an orthonormal transformation on the left. We will fix a convenient choice subsequently. For now, observe that $\dot{\Sigma}^{-1/2}$ and $\dot{\Sigma}^{1/2}\coloneqq((\dot{\Sigma}^{-1/2})^{-1})^{\top}$ satisfy:

$$ $\forall x_{1},x_{2}\in\mathbb{R}^{2}:\langle x_{1},x_{2}\rangle=\langle\dot{\Sigma}^{1/2}x_{1},\dot{\Sigma}^{-1/2}x_{2}\rangle.$ $$

Setting $x_{1}=c_{i}$ and $x_{2}=V$, we now observe:

$$ $\langle\dot{\Sigma}^{1/2}c_{i},\dot{\Sigma}^{-1/2}V\rangle\text{ with }\dot{\Sigma}^{-1/2}V\thicksim\mathcal{N}(\widetilde{\mu},I)\text{ where }\widetilde{\mu}\coloneqq\dot{\Sigma}^{-1/2}\dot{\mu}.$ $$

Lastly, note that:

$$ $\forall i\in[3]:\langle c_{i},V\rangle\geqslant 0\iff\langle\widetilde{c}_{i},\dot{\Sigma}^{-1/2}V\rangle\geqslant 0\text{ where }\widetilde{c}_{i}\coloneqq\frac{\dot{\Sigma}^{1/2}c_{i}}{\lVert\dot{\Sigma}^{1/2}c_{i}\rVert}.$ $$

Note that $\dot{\Sigma}^{-1/2}V$ is isotropic. Defining,

$$ $\alpha_{i}\coloneqq\widetilde{c}_{i}^{\top}\widetilde{\mu}\text{ and }\alpha_{ij}\coloneqq\widetilde{c}_{i}^{\top}\widetilde{c}_{j},$ $$

Our first technical result identifies $\alpha_{i}$ from observational data.

###### Lemma 4.2 .

The quantities $\alpha_{i}$ are identifiable from three-way ranking probabilities.

###### Proof.

Note that

$$ $\mathbb{P}{\left\{c_{i}^{\top}V\geqslant 0\right\}}=\mathbb{P}{\left\{\langle\Sigma^{-1/2}V,\widetilde{c}_{i}\rangle\geqslant 0\right\}}=\mathbb{P}_{g\thicksim\mathcal{N}(0,1)}{\left\{g+\langle\widetilde{c}_{i},\widetilde{\mu}\rangle\geqslant 0\right\}}=\Phi(\langle\widetilde{c}_{i},\widetilde{\mu}\rangle).$ $$

As $\Phi(\cdot)$ is a strictly increasing function, $\langle\widetilde{c}_{i},\widetilde{\mu}\rangle$ is recoverable from the observables.
∎

In the next lemma, we use the values $\alpha_{i}$ from [Lemma 4.2](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem2) to establish a monotonic relationship between $\langle\widetilde{c}_{i},\widetilde{c}_{j}\rangle$ and the probability of the events in [Figure 1](https://arxiv.org/html/2510.15839v1#S4.F1). However, the precise choice of events depends on the $\alpha_{i}$. Note that for any distinct $i,j\in[3]$, there exist signings $s_{i},s_{j}\in\{\pm 1\}$ such that $s_{i}\langle\widetilde{c}_{i},\widetilde{\mu}\rangle,s_{j}\langle\widetilde{c}_{j},\widetilde{\mu}\rangle\geqslant 0$ and the events ${\left\{s_{i}\langle\widetilde{c}_{i},\dot{\Sigma}^{-1/2}V\rangle,s_{j}\langle\widetilde{c}_{j},\dot{\Sigma}^{-1/2}V\rangle\leqslant 0\right\}}$ correspond to combinations of one or more events in [Figure 1](https://arxiv.org/html/2510.15839v1#S4.F1) and is hence, observable. By instantiating the subsequent lemma with the signed vectors $s_{i}\widetilde{c}_{i},s_{j}\widetilde{c}_{j}$, we recover the $\alpha_{ij}$ by relating it to the probability of the event ${\left\{s_{i}\langle\widetilde{c}_{i},\dot{\Sigma}^{-1/2}V\rangle,s_{j}\langle\widetilde{c}_{j},\dot{\Sigma}^{-1/2}V\rangle\leqslant 0\right\}}$. Its proof is deferred to [Subsection E.1](https://arxiv.org/html/2510.15839v1#A5.SS1).

###### Lemma 4.3 .

Let $v_{1},v_{2}\in\mathbb{R}^{2}$ be two independent unit vectors and $\xi\in\mathbb{R}^{2}$ be such that $d_{1}\coloneqq\langle v_{1},\xi\rangle,d_{2}\coloneqq\langle v_{2},\xi\rangle\geqslant 0$. Then,

$$ $\alpha_{12}\coloneqq\langle v_{1},v_{2}\rangle$ $$

is identifiable from $d_{1},d_{2},$ and

$$ $\gamma_{12}\coloneqq\mathbb{P}{\left\{\langle X,v_{1}\rangle,\langle X,v_{2}\rangle\leqslant 0\right\}}\text{ for }X\thicksim\mathcal{N}(\xi,I).$ $$

###### Proof of Theorem 4.1 .

We will show that $\dot{\Sigma}^{1/2}$ is recoverable from the observation probabilities. $\dot{\Sigma}$ is then obtainable from the fact that $\dot{\Sigma}=(\dot{\Sigma}^{1/2})^{\top}\dot{\Sigma}^{1/2}$. From [Lemma 4.2](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem2), we recover $\alpha_{i}=\langle\widetilde{c}_{i},\widetilde{\mu}\rangle$ for $i\in[3]$ and from [Lemma 4.3](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem3), we recover $\alpha_{ij}=\langle\widetilde{c_{i}},\widetilde{c_{j}}\rangle$ for $i\neq j\in[3]$.
Without loss of generality, we assume that for some $s,t>0$ by relaxing the scale constraint $\operatorname*{\mathrm{Tr}}\dot{\Sigma}=1$:

$$ $\dot{\Sigma}^{1/2}c_{1}=\begin{bmatrix}1\\ 0\end{bmatrix},\quad\dot{\Sigma}^{1/2}c_{2}=s\begin{bmatrix}\alpha_{12}\\ \sqrt{1-\alpha^{2}_{12}}\end{bmatrix},\quad\dot{\Sigma}^{1/2}c_{3}=t\begin{bmatrix}\alpha_{13}\\ \sqrt{1-\alpha_{13}^{2}}\end{bmatrix}.$ (2) $$

The signs of the second component of the vector are determined by fixing the sign of $\dot{\Sigma}^{1/2}c_{2}$ (this is an orthonormal transformation) and for $\dot{\Sigma}^{1/2}c_{3}$, follows from the fact that $c_{3}=c_{1}+c_{2}$. Noting that $\alpha_{13}\neq\alpha_{12}$ (as otherwise, we obtain permutation observations with 0 probability), we obtain:

$$ $\begin{bmatrix}1\\ 0\end{bmatrix}+s\begin{bmatrix}\alpha_{12}\\ \sqrt{1-\alpha^{2}_{12}}\end{bmatrix}=t\begin{bmatrix}\alpha_{13}\\ \sqrt{1-\alpha_{13}^{2}}\end{bmatrix}\implies\begin{bmatrix}1\\ 0\end{bmatrix}=\begin{bmatrix}\alpha_{13}&\alpha_{12}\\ \sqrt{1-\alpha_{13}^{2}}&\sqrt{1-\alpha^{2}_{12}}\end{bmatrix}\begin{bmatrix}t\\ -s\end{bmatrix}.$ $$

Since the above forms an invertible system, we obtain the values of $s,t>0$. This now enables the recovery of $\dot{\Sigma}$ (and consequently, $\Sigma$) via the invertible system:

$$ $\dot{\Sigma}^{1/2}\cdot\begin{bmatrix}c_{1}&c_{2}\end{bmatrix}=\begin{bmatrix}1&s\alpha_{12}\\ 0&s\sqrt{1-\alpha_{12}^{2}}\end{bmatrix}$ $$

To recover $\dot{\mu}$, note that $\widetilde{c}_{1}$ and $\widetilde{c}_{2}$ form a basis for $\mathbb{R}^{2}$ and observing that these are determined by [Eq. 2](https://arxiv.org/html/2510.15839v1#S4.E2), we identify $\widetilde{\mu}$. Noting that $\dot{\Sigma}^{-1/2}\dot{\mu}=\widetilde{\mu}$, we recover $\dot{\mu}$ and $\mu$ by our previous discussion.
∎

###### Theorem 4.1 .

###### Lemma 4.2 .

###### Proof.

###### Lemma 4.3 .

###### Proof of Theorem 4.1 .

### 4.2 Identifiability: More Than Three Alternatives

We now utilize [Theorem 4.1](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem1) to establish identifiability for an arbitrary number of alternatives, $n$. [Theorem 4.1](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem1) recovers $\mu,\Sigma$ restricted to tuples of $3$ alternatives up to the symmetries in [Assumption 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1). However, the sub-matrices of $\mu,\Sigma$ (or more precisely, $\mu$ and $\Sigma$ restricted to these alternatives) could potentially violate these assumptions. Hence, we establish that there is a unique pair, $\mu,\Sigma$, consistent with the equivalence class of parameters identified by [Theorem 4.1](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem1) for all choices of $3$ alternatives. In what follows, we will use $\bar{\mu}_{ijk}$ and $\bar{\Sigma}_{ijk}$ to denote the parameters $\mu$ and $\Sigma$ restricted to the tuple $i,j$ and $k$, projected onto the two-dimensional subspace orthogonal to $\bm{1}$.

###### Theorem 4.4 .

$\mu,\Sigma$ are uniquely identifiable from the three-way observation probabilities.

###### Proof.

First, note for any distinct indices $i,j,k$, [Theorem 4.1](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem1) yields $\widetilde{\mu}_{ijk},\widetilde{\Sigma}_{ijk}$ satisfying:

$$ $\displaystyle t_{ijk}\widetilde{\mu}_{ijk}=\bar{\mu}_{ijk}\text{ and }t_{ijk}^{2}\widetilde{\Sigma}_{ijk}=\bar{\Sigma}_{ijk}$ $$

for some scaling $t_{ijk}>0$. Denoting $c_{ij}=e_{i}-e_{j}$, we have:

$$ $c_{ij}^{\top}t_{ijk}^{2}\widetilde{\Sigma}_{ijk}c_{ij}=c_{ij}^{\top}\bar{\Sigma}_{ijk}c_{ij}=c_{ij}^{\top}\Sigma c_{ij}\implies t_{ijk}^{2}=\frac{c_{ij}^{\top}\Sigma c_{ij}}{c_{ij}^{\top}\widetilde{\Sigma}_{ijk}c_{ij}}.$ $$

The first step uses the fact that $c_{ij}^{\top}\bar{\Sigma}_{ijk}c_{ij}=c_{ij}^{\top}\Sigma_{ijk}c_{ij}$. Since scaling $\Sigma$ (and $\mu$) produces the same solution, we may assume without loss of generality that $t_{123}=1$. Noting that this allows the recovery of $c_{12}^{\top}\Sigma c_{12}$, the above equality enables determination of the $t_{12k}$ for all $k\in[n]$. This further enables the determination of $t_{1jk}$ for all distinct $k,j\in[n]$. Another application of the argument finally yields the values of $t_{ijk}$ for all distinct $i,j,k\in[n]$.

Furthermore, observe that for all distinct $i,j,k\in[n]$ with $\sigma_{ij}\coloneqq\Sigma_{ij}$:

$$ $c_{ij}^{\top}t_{ijk}^{2}\widetilde{\Sigma}_{ijk}c_{ij}=c_{ij}^{\top}\Sigma c_{ij}=\sigma_{ii}+\sigma_{jj}-2\sigma_{ij}.$ $$

Furthermore, noting that $c_{ii}=\bm{0}$, we determine $\alpha_{ij}=c_{ij}^{\top}\Sigma c_{ij}$ for all $i,j\in[n]$. Observe that

$$ $\sum_{j=1}^{n}c_{ij}^{\top}\Sigma c_{ij}=n\sigma_{ii}+\operatorname*{\mathrm{Tr}}(\Sigma)-2\sum_{j=1}^{n}\sigma_{ij}=n\sigma_{ii}+\operatorname*{\mathrm{Tr}}(\Sigma).$ $$

where the last step is due to fact that $\bm{1}^{\top}\mu=0,\Sigma\bm{1}=\bm{0}$. By further summing over $i$, we get

$$ $\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}^{\top}\Sigma c_{ij}=n\operatorname*{\mathrm{Tr}}(\Sigma)+n\operatorname*{\mathrm{Tr}}(\Sigma)$ $$

which now enables recovery of $\operatorname*{\mathrm{Tr}}(\Sigma)$ and from the above discussion $\sigma_{ii}$ and consequently, $\sigma_{ij}$ for all $i,j$. Hence, we have identified $\Sigma$. For the mean, observe again the following:

$$ $c_{ij}^{\top}(t_{ijk}\widetilde{\mu}_{ijk})=c_{ij}^{\top}\bar{\mu}_{ijk}=\mu_{i}-\mu_{j}.$ $$

The last step is valid because all of the elements of $\mu_{ijk}$ were shifted by the same amount to obtain $\bar{\mu}_{ijk}$, and consequently, their difference did not change.
Since $t_{ijk}$ are determined, this determines $\mu_{1}-\mu_{j}$ for all $j$ (note the choice of $\mu_{1}$ is arbitrary). Letting $\beta_{j}=\mu_{1}-\mu_{j}$, we have:

$$ $\sum_{j=1}^{n}\beta_{j}=n\mu_{1}-\sum_{j=1}^{n}\mu_{j}=n\mu_{1}.$ $$

This determines $\mu_{1}$ and, consequently, the remaining $\mu_{j}$. This concludes the proof as $(\mu,\Sigma)$ have been recovered up to the universal symmetries previously described.
∎

###### Theorem 4.4 .

###### Proof.

## 5 Finite-sample Guarantees: Upper and Lower Bounds

In this section, we extend our identifiability results [Section 4](https://arxiv.org/html/2510.15839v1#S4) to estimation. The key conceptual advancement over [Section 4](https://arxiv.org/html/2510.15839v1#S4) is in the aggregation procedure which combines the standardized estimators of the $3$ item setting ([Subsection 4.1](https://arxiv.org/html/2510.15839v1#S4.SS1)) into a solution for the $n$ item setting ([Subsection 4.2](https://arxiv.org/html/2510.15839v1#S4.SS2)). The procedure described in [Subsection 4.2](https://arxiv.org/html/2510.15839v1#S4.SS2) is wasteful as it requires estimating all $3\times 3$ sub-matrices of $\Sigma$, resulting in a total of $O(n^{3})$ total $3\times 3$ matrices. We show that this can be substantially improved upon using a much smaller number ($\widetilde{O}(n^{2})$) of sub-matrices in [Theorem 5.2](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem2). We then establish a statistical lower bound demonstrating the near-optimality of our estimator. We start with our estimation guarantees. In addition to [Assumption 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1), we require the following assumption:

###### Assumption 5.1 .

(Observability)
For any three alternatives $i,j,k\in[n]$ and $X\thicksim\mathcal{N}(\mu,\Sigma)$:

$$ $\operatorname*{\mathbb{P}}{\left\{i>j>k\right\}}\geqslant\gamma$ $$

for some $\gamma>0$.

Intuitively, [Assumption 5.1](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem1) avoids worst-case scenarios where an overwhelming difference in utilities renders a choice unobservable, making some parameters impossible to estimate.
We now state our main estimation guarantee for the general $n$-item setting.

###### Theorem 5.2 .

Let $(\mu^{*},\Sigma^{*})$ satisfy [Assumptions 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1) and [5.1](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem1) with $\operatorname*{\mathrm{Tr}}(\Sigma^{*})=n$. Then, for any $\varepsilon,\delta\in(0,1/2]$, given there is a polynomial time algorithm which when allowed $N$ observations of rank-$3$ permutations from $\mathrm{Choice}(\mu^{*},\Sigma^{*})$ of its choice, returns estimates, $(\overline{\mu},\overline{\Sigma})$, satisfying:

$$ $\displaystyle\lVert\overline{\mu}-\mu^{*}\rVert_{\infty}\leqslant\varepsilon\text{ and }\lVert\overline{\Sigma}-\Sigma^{*}\rVert_{\infty}\leqslant\varepsilon$ $$

with probability at least $1-\delta$ as long as $N\geqslant Cn^{2}\varepsilon^{-2}\gamma^{-24}\log(n/\delta)\log^{6}(n/(\gamma\varepsilon))$.

Next, we present a lower bound that shows that [Theorem 5.2](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem2) is near-optimal. We introduce some notation before proceeding. An estimator, $T$, is parameterized by a set of tuples $\{((i,j,k),N_{ijk}):i,j,k\in[n],\,i\neq j\neq k\neq i\}$. The estimator then obtains $N_{ijk}$ samples from $\mathrm{Choice}(\mu^{*}_{ijk},\Sigma^{*}_{ijk})$ for each $i,j,k$ and outputs estimates $(\overline{\mu},\overline{\Sigma})$. Furthermore, we denote:

$$ $N_{ij}\coloneqq\sum_{k}N_{ijk}.$ $$

As before, we adopt [Assumption 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1) for normalization and state our main lower bound below.

###### Theorem 5.3 .

Let $n\in\mathbb{N}$, $\delta,\varepsilon\in(0,2^{-4})$. For any estimator $T$ parameterized by $\{((i,j,k),N_{ijk})\}_{i\neq j\neq k\neq i}$ such that $N_{i^{*},j^{*}}\leqslant\varepsilon^{-2}\log(1/\delta)/4$ for some $i^{*}\neq j^{*}\in[n]$, there exist two choice models, parameterized by $(\bm{0},\Sigma^{1})$ and $(\bm{0},\Sigma^{2})$ with:

$$ $\operatorname*{\mathrm{Tr}}(\Sigma^{1})=\operatorname*{\mathrm{Tr}}(\Sigma^{2})=n\text{ and }\lVert\Sigma^{1}-\Sigma^{2}\rVert_{\infty}\geqslant\varepsilon,$ $$

satisfying:

$$ $\max_{\Sigma\in\{\Sigma^{1},\Sigma^{2}\}}\mathbb{P}_{\bm{X}\thicksim(T,\mathrm{Choice}(\bm{0},\Sigma))}{\left\{\lVert T(\bm{X})-\Sigma\rVert_{\infty}\geqslant\frac{\varepsilon}{4}\right\}}\geqslant\delta.$ $$

We pause for a few remarks. Firstly, note that each pair $(i,j)$ must appear in at least $\Omega(\varepsilon^{-2})$ experiments. Since each sample only accounts for $O(1)$ pairs, this result implies a lower bound of $\Omega(n^{2})$ on the number of unique experiments for any successful estimator matching [Theorem 5.2](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem2). Finally, note that this argument also implies that the total number of samples is at least $\Omega(n^{2}\varepsilon^{-2}\log(1/\delta))$ again matching [Theorem 5.2](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem2) in terms of $n,d,\text{ and }\delta$.

Figure: Figure 2: Center: ground truth covariance matrix, two figures on the right, covariance matrix learned from best-of-three observations, two figure on the left, covariance matrix learned from pairwise comparisons. We reproduce larger version these plots in Appendix [F](https://arxiv.org/html/2510.15839v1#A6).
Refer to caption: x2.png

###### Assumption 5.1 .

###### Theorem 5.2 .

###### Theorem 5.3 .

## 6 Experiments

We empirically evaluate modeling correlations(^3^33Code is available at https://github.com/SobhanMP/lcorr). We use datasets of ratings and rankings. In rating datasets users are asked to assign a numerical value to alternatives. In contrasts, ranking datasets contain the ordered list of preferences. We convert rankings to ratings and vice versa by using the index as rating and assuming alternatives with higher ratings are preferred over alternatives with lower ratings. The data gathering process can either be organic i.e., users rate movies they watch, or structured, every user ranks all food items on the menu.

We use two types of models on these datasets: RUMs and matrix completion models, both trained with gradient based methods. For RUMs, we use logit and probit models learned from two way comparisons and probit models learned from three way comparisons. In all cases we use the maximum likelihood estimate. RUMs do not take the user as input and directly create a model for the population. Matrix completion (Koren et al., 2009) learns the ratings for all users in the training set, we then use the counts of users in the training set to approximate the probability of certain events. For sanity checks, we include a model we refer to as direct, which is similar to matrix completion, except we compute the desired quantities directly on the training set. We argue that this model is unrealistic in some scenarios, for instance where the set of alternative and user is large or when the ratings are grouped but anonymous. Still, since these matrix completion models the whole population, we expect them to be able to learn correlated preferences.

In the first set of experiments we sample six choices from a user, we present the ranking of four of the alternatives as context and predict the preference over the remaining two alternatives. We start with synthetic data sampled from probit model as we can compare our results to the ground truth. In Figure [2](https://arxiv.org/html/2510.15839v1#S5.F2), we show the recovered covariance matrices with pairwise and best-of-three observations using a probit RUM. We can see that the model learned from pairwise comparisons learns nonexistent correlations in the uncorrelated case while in the correlated case, initialization can play an important role as apparent by the change in value in the first cell of the second row. We report the performance in Table [2](https://arxiv.org/html/2510.15839v1#S6.T2). The location $\mu$ can either be zero or sampled randomly, the covariance matrix can either be the identity matrix I, diagonal random rI, plus minus one bin, and random r. In all cases the best-of-three probit matches the performance direct method (with simulation).

**Table 1: Accuracy of different methods on the synthetic dataset. Notice how the direct method matches best-of-three probit.**
| structure | logit | matrix completion | probit (pairwise) | probit (best-of-three) |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | accuracy quantile | accuracy quantile | accuracy quantile | accuracy quantile |  |  |  |  |  |  |  |  |  |
| $\mu$ | $\Sigma$ | 0.25 | 0.50 | 0.75 | 0.25 | 0.50 | 0.75 | 0.25 | 0.50 | 0.75 | 0.25 | 0.50 | 0.75 |
| 0 | I | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 |
| 0 | bin | 0.50 | 0.50 | 0.50 | 0.78 | 0.78 | 0.78 | 0.45 | 0.50 | 0.54 | 0.79 | 0.79 | 0.79 |
| 0 | rI | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 | 0.51 | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 |
| 0 | r | 0.50 | 0.50 | 0.50 | 0.67 | 0.67 | 0.67 | 0.47 | 0.51 | 0.55 | 0.67 | 0.67 | 0.67 |
| r | I | 0.70 | 0.70 | 0.71 | 0.68 | 0.70 | 0.70 | 0.66 | 0.66 | 0.67 | 0.68 | 0.70 | 0.70 |
| r | bin | 0.79 | 0.79 | 0.80 | 0.94 | 0.95 | 0.95 | 0.95 | 0.95 | 0.95 | 0.94 | 0.95 | 0.95 |
| r | rI | 0.72 | 0.72 | 0.72 | 0.71 | 0.71 | 0.72 | 0.69 | 0.70 | 0.71 | 0.70 | 0.70 | 0.72 |
| r | r | 0.63 | 0.63 | 0.64 | 0.71 | 0.71 | 0.71 | 0.67 | 0.68 | 0.69 | 0.71 | 0.71 | 0.71 |

For real data, we use the data from a sushi preference dataset (Kamishima, 2003), the eigen-taste joke dataset (Goldberg et al., 2001), Netflix prize (Netflix, Inc., 2006), and the MovieLens dataset (Harper and Konstan, 2015). The sushi dataset is the only ranking dataset. It’s A variant is the only dataset where every user rank every alternative. The results are presented in Table [2](https://arxiv.org/html/2510.15839v1#S6.T2). We observe that training with best-of-three observations lead to great improvement over probit models trained with best-of-two observations. The mean effect are strong in these datasets and the improvement over the logit is modest. Table [3](https://arxiv.org/html/2510.15839v1#S6.T3) lists some movies with strong correlations in the Netflix and MovieLense datasets. In particular we note that we find sequels like Spider-Man (2002) and Spider-Man 2 (2004) or Kill Bill Vol. 1 (2003) and Kill Bill Vol. 2 (2004) to have strong positive correlations while we find a strong negative correlation between more critically acclaimed movies like Memento (2000) and Eternal Sunshine of the Spotless Mind (2004) compared to Hollywood comedy and blockbusters like Perl Harbor (2001) or Cheaper by the Dozen (2003). In Figure [7](https://arxiv.org/html/2510.15839v1#A6.F7), we see that sea urchins are very divisive and that a preference for cucumber sushi negatively correlates with preference for toro (fatty tuna) sushi.

Table: Table 3: Left to right, movies with the lowest and highest correlations in a probit learned from the Netflix (top) and MovieLens (bottom) datasets. A table with more movie pair is produced in Appendix [F](https://arxiv.org/html/2510.15839v1#A6).

We finish this section with a welfare maximization experiment. We evaluate the welfare maximizing subset of alternatives given a fixed size, i.e., solve the following equation for some fixed $N$, $\max_{\mathcal{R}\subseteq\mathcal{C}:|\mathcal{R}|=N}\mathbb{E}\left[\max_{i\in\mathcal{R}}X_{i}\right].$ We use the models from the previous experiments to generate welfare maximizing subsets of size 1 to 3 in the sushi-A dataset. Figure [3](https://arxiv.org/html/2510.15839v1#S6.F3) illustrates what percentage of the test population have their $i$th preferred alternative in the set, e.g., the bar with $x=4$ corresponds to the ratio of people who have at least their third favorite alternative in the set. We acknowledge that this quantity does not directly correlate with welfare as welfare is sensitive to the magnitude of utility change whereas this plot is not. It might not make significant utility difference for someone if their second or third choice are present but it affects this plot. Nonetheless, we see that for subsets of size 2 and 3, more people have their preferred sushi on the menu. The optimal size one menu, for all RUMs, is toro (fatty tuna), the optimal size 2 menu according to the logit is toro (fatty tuna) and maguro (tuna) while our probit suggests uni (sea urchin) and maguro (fatty tuna) instead. Looking at the output of the model in Figure [7](https://arxiv.org/html/2510.15839v1#A6.F7) we see that the utility of uni (sea urchin) has high variance and correlates negatively with the utility of toro (fatty tuna) and maguro (tuna). This difference in menu highlights the problem with not modeling correlations properly, a menu of two alternatives that are high utility is not much better than one with only one alternative if they are very correlated. The probit learned from pairwise comparisons instead suggests anago (eel) and toro (fatty tuna) instead.

Figure: Figure 3: Preference of the welfare maximizing choices, left to right for $N=1,2,3$.
Refer to caption: x12.png

## 7 Conclusions and Future Directions

In this paper, we investigated the methodological shortcomings of learning correlated reward models from simple preference data. We established the statistical deficiency of pairwise comparisons for identifying correlation and showed that best-of-three preferences are provably sufficient. Our analysis culminated in a statistically and computationally efficient estimator for this setting, complete with finite-sample guarantees. Ultimately, our findings show that modeling preference correlations is not only feasible but essential for enabling more advanced applications like in-context learning and the strategic sampling of alternatives.

## Acknowledgments

CD is supported by a Simons Investigator Award, a Simons Collaboration on Algorithmic Fairness, ONR MURI grant N00014-25-1-2116, ONR grant N00014-25-1-2296. GF are supported by NSF Award CCF-244306, ONR grant N00014-25-1-2296, and an AI2050 Early Career Fellowship. SM is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), 599271-2025.

## References

- (1)
- Anderson et al. (1988)
Simon P Anderson,
André De Palma, and J-F Thisse.
1988.
A representative consumer theory of the logit
model.
International Economic Review
(1988), 461–466.
- Anwar et al. (2024)
Usman Anwar, Abulhair
Saparov, Javier Rando, Daniel Paleka,
Miles Turpin, Peter Hase,
Ekdeep Singh Lubana, Erik Jenner,
Stephen Casper, Oliver Sourbut,
Benjamin L. Edelman, Zhaowei Zhang,
Mario Günther, Anton Korinek,
José Hernández-Orallo, Lewis
Hammond, Eric J. Bigelow, Alexander Pan,
Lauro Langosco, Tomasz Korbak,
Heidi Chenyu Zhang, Ruiqi Zhong,
Seán Ó hÉigeartaigh,
Gabriel Recchia, Giulio Corsi,
Alan Chan, Markus Anderljung,
Lilian Edwards, Aleksandar Petrov,
Christian Schröder de Witt,
Sumeet Ramesh Motwani, Yoshua Bengio,
Danqi Chen, Philip Torr,
Samuel Albanie, Tegan Maharaj,
Jakob Nicolaus Foerster, Florian
Tramèr, He He, Atoosa Kasirzadeh,
Yejin Choi, and David Krueger.
2024.
Foundational Challenges in Assuring Alignment and
Safety of Large Language Models.
Trans. Mach. Learn. Res.
2024 (2024).
https://openreview.net/forum?id=oVTkOs8Pka
- Bai et al. (2022)
Yuntao Bai, Saurav
Kadavath, Sandipan Kundu, Amanda Askell,
Jackson Kernion, Andy Jones,
Anna Chen, Anna Goldie,
Azalia Mirhoseini, Cameron McKinnon,
Carol Chen, Catherine Olsson,
Christopher Olah, Danny Hernandez,
Dawn Drain, Deep Ganguli,
Dustin Li, Eli Tran-Johnson,
Ethan Perez, Jamie Kerr,
Jared Mueller, Jeffrey Ladish,
Joshua Landau, Kamal Ndousse,
Kamile Lukosiute, Liane Lovitt,
Michael Sellitto, Nelson Elhage,
Nicholas Schiefer, Noemí Mercado,
Nova DasSarma, Robert Lasenby,
Robin Larson, Sam Ringer,
Scott Johnston, Shauna Kravec,
Sheer El Showk, Stanislav Fort,
Tamera Lanham, Timothy Telleen-Lawton,
Tom Conerly, Tom Henighan,
Tristan Hume, Samuel R. Bowman,
Zac Hatfield-Dodds, Ben Mann,
Dario Amodei, Nicholas Joseph,
Sam McCandlish, Tom Brown, and
Jared Kaplan. 2022.
Constitutional AI: Harmlessness from AI
Feedback.
CoRR abs/2212.08073
(2022).
https://doi.org/10.48550/ARXIV.2212.08073
arXiv:2212.08073
- Ben-Akiva (1973)
Moshe E. Ben-Akiva.
1973.
Structure of passenger travel demand models.
Ph. D. Dissertation.
Massachusetts Institute of Technology.
- Benson et al. (2016)
Austin R Benson, Ravi
Kumar, and Andrew Tomkins.
2016.
On the relevance of irrelevant alternatives. In
Proceedings of the 25th international conference on
world wide web. 963–973.
- Boucheron et al. (2013)
Stéphane Boucheron,
Gábor Lugosi, and Pascal Massart.
2013.
Concentration inequalities.
Oxford University Press, Oxford.
A nonasymptotic theory of independence, With a foreword by Michel
Ledoux.
- Bretagnolle and Huber (1979)
J. Bretagnolle and C.
Huber. 1979.
Estimation des densités: risque minimax.
Z. Wahrsch. Verw. Gebiete
47, 2 (1979),
119–137.
- Bunch (1991)
David S Bunch.
1991.
Estimability in the multinomial probit model.
Transportation Research Part B:
Methodological 25, 1
(1991), 1–12.
- Bunch and Kitamura (1991)
David S Bunch and
Ryuichi Kitamura. 1991.
Probit model estimation revisited: trinomial models
of household car ownership.
(1991).
- Canonne (2023)
Clément L. Canonne.
2023.
A short note on an inequality between KL and TV.
arXiv:2202.07198
- Casper et al. (2023)
Stephen Casper, Xander
Davies, Claudia Shi, Thomas Krendl
Gilbert, Jérémy Scheurer,
Javier Rando, Rachel Freedman,
Tomasz Korbak, David Lindner,
Pedro Freire, Tony Tong Wang,
Samuel Marks, Charbel-Raphaël
Ségerie, Micah Carroll, Andi Peng,
Phillip J. K. Christoffersen, Mehul
Damani, Stewart Slocum, Usman Anwar,
Anand Siththaranjan, Max Nadeau,
Eric J. Michaud, Jacob Pfau,
Dmitrii Krasheninnikov, Xin Chen,
Lauro Langosco, Peter Hase,
Erdem Biyik, Anca D. Dragan,
David Krueger, Dorsa Sadigh, and
Dylan Hadfield-Menell. 2023.
Open Problems and Fundamental Limitations of
Reinforcement Learning from Human Feedback.
Trans. Mach. Learn. Res.
2023 (2023).
https://openreview.net/forum?id=bx24KpJ4Eb
- Christiano et al. (2017)
Paul F Christiano, Jan
Leike, Tom Brown, Miljan Martic,
Shane Legg, and Dario Amodei.
2017.
Deep reinforcement learning from human
preferences.
Advances in neural information processing
systems 30 (2017).
- Clark (1961)
Charles E Clark.
1961.
The greatest of a finite set of random variables.
Operations Research 9,
2 (1961), 145–162.
- Conitzer et al. (2024)
Vincent Conitzer, Rachel
Freedman, Jobst Heitzig, Wesley H.
Holliday, Bob M. Jacobs, Nathan Lambert,
Milan Mossé, Eric Pacuit,
Stuart Russell, Hailey Schoelkopf,
Emanuel Tewolde, and William S.
Zwicker. 2024.
Position: Social Choice Should Guide AI Alignment
in Dealing with Diverse Human Feedback. In
Forty-first International Conference on Machine
Learning, ICML 2024, Vienna, Austria, July 21-27, 2024.
OpenReview.net.
https://openreview.net/forum?id=w1d9DOGymR
- Debreu (1960)
Gerard Debreu.
1960.
Reviewed Work: Individual choice behavior: A
theoretical analysis.
The American Economic Review
50, 1 (1960),
186–188.
- Ding et al. (2024)
Patrick Ding, Guido
Imbens, Zhaonan Qu, and Yinyu Ye.
2024.
Computationally Efficient Estimation of Large
Probit Models.
arXiv preprint arXiv:2407.09371
(2024).
- Feng et al. (2017)
Guiyun Feng, Xiaobo Li,
and Zizhuo Wang. 2017.
On the relation between several discrete choice
models.
Operations research 65,
6 (2017), 1516–1525.
- Gallego and Wang (2014)
Guillermo Gallego and
Ruxian Wang. 2014.
Multiproduct price optimization and competition
under the nested logit model with product-differentiated price
sensitivities.
Operations Research 62,
2 (2014), 450–461.
- Gessner et al. (2020)
Alexandra Gessner,
Oindrila Kanjilal, and Philipp Hennig.
2020.
Integrals over Gaussians under linear domain
constraints. In International conference on
artificial intelligence and statistics. PMLR, 2764–2774.
- Goldberg et al. (2001)
Ken Goldberg, Theresa
Roeder, Dhruv Gupta, and Chris
Perkins. 2001.
Eigentaste: A constant time collaborative filtering
algorithm.
information retrieval 4,
2 (2001), 133–151.
- Harper and Konstan (2015)
F Maxwell Harper and
Joseph A Konstan. 2015.
The movielens datasets: History and context.
Acm transactions on interactive intelligent
systems (tiis) 5, 4
(2015), 1–19.
- Havrilla et al. (2024)
Alex Havrilla, Sharath
Raparthy, Christoforus Nalmpantis, Jane
Dwivedi-Yu, Maksym Zhuravinskyi, Eric
Hambro, and Roberta Raileanu.
2024.
Glore: When, where, and how to improve llm
reasoning via global and local refinements.
arXiv preprint arXiv:2402.10963
(2024).
- Hofbauer and Sandholm (2002)
Josef Hofbauer and
William H Sandholm. 2002.
On the global convergence of stochastic fictitious
play.
Econometrica 70,
6 (2002), 2265–2294.
- Kamakura (1989)
Wagner A Kamakura.
1989.
The estimation of multinomial probit models: A new
calibration algorithm.
Transportation Science
23, 4 (1989),
253–265.
- Kamishima (2003)
Toshihiro Kamishima.
2003.
Nantonac collaborative filtering: recommendation
based on order responses. In Proceedings of the
ninth ACM SIGKDD international conference on Knowledge discovery and data
mining. 583–588.
- Kingma (2014)
Diederik P Kingma.
2014.
Adam: A method for stochastic optimization.
arXiv preprint arXiv:1412.6980
(2014).
- Koren et al. (2009)
Yehuda Koren, Robert
Bell, and Chris Volinsky.
2009.
Matrix factorization techniques for recommender
systems.
Computer 42,
8 (2009), 30–37.
- Lamontagne et al. (2023)
Steven Lamontagne,
Margarida Carvalho, Emma Frejinger,
Bernard Gendron, Miguel F Anjos, and
Ribal Atallah. 2023.
Optimising electric vehicle charging station
placement using advanced discrete choice models.
INFORMS Journal on Computing
35, 5 (2023),
1195–1213.
- Luce (1959)
R Duncan Luce.
1959.
Individual choice behavior.
Vol. 4.
Wiley New York.
- Luo et al. (2023)
Haipeng Luo, Qingfeng
Sun, Can Xu, Pu Zhao,
Jianguang Lou, Chongyang Tao,
Xiubo Geng, Qingwei Lin,
Shifeng Chen, and Dongmei Zhang.
2023.
Wizardmath: Empowering mathematical reasoning for
large language models via reinforced evol-instruct.
arXiv preprint arXiv:2308.09583
(2023).
- McFadden (1980)
Daniel McFadden.
1980.
Econometric models for probabilistic choice among
products.
Journal of Business (1980),
S13–S29.
- McFadden (2001)
Daniel McFadden.
2001.
Economic choices.
American economic review
91, 3 (2001),
351–378.
- McFadden and Train (2000)
Daniel McFadden and
Kenneth Train. 2000.
Mixed MNL models for discrete response.
Journal of applied Econometrics
15, 5 (2000),
447–470.
- Natarajan et al. (2000)
Ranjini Natarajan,
Charles E McCulloch, and Nicholas M
Kiefer. 2000.
A Monte Carlo EM method for estimating multinomial
probit models.
Computational statistics & data analysis
34, 1 (2000),
33–50.
- Netflix, Inc. (2006)
Netflix, Inc.
2006.
Netflix Prize Data.
- Osorio and Atasoy (2021)
Carolina Osorio and
Bilge Atasoy. 2021.
Efficient simulation-based toll optimization for
large-scale networks.
Transportation science
55, 5 (2021),
1010–1024.
- Pardo (2006)
Leandro Pardo.
2006.
Statistical inference based on divergence
measures. Statistics: Textbooks and Monographs,
Vol. 185.
Chapman & Hall/CRC, Boca Raton, FL.
- Rust and Zahorik (1993)
Roland T Rust and
Anthony J Zahorik. 1993.
Customer satisfaction, customer retention, and
market share.
Journal of retailing 69,
2 (1993), 193–215.
- Sørensen and Fosgerau (2022)
Jesper R-V Sørensen and
Mogens Fosgerau. 2022.
How McFadden met Rockafellar and learned to do more
with less.
Journal of Mathematical Economics
100 (2022), 102629.
- Sorensen et al. (2024)
Taylor Sorensen, Jared
Moore, Jillian Fisher, Mitchell L.
Gordon, Niloofar Mireshghallah,
Christopher Michael Rytting, Andre Ye,
Liwei Jiang, Ximing Lu,
Nouha Dziri, Tim Althoff, and
Yejin Choi. 2024.
Position: A Roadmap to Pluralistic Alignment. In
Forty-first International Conference on Machine
Learning, ICML 2024, Vienna, Austria, July 21-27, 2024.
OpenReview.net.
https://openreview.net/forum?id=gQpBnRHwxM
- Train (2009)
Kenneth E Train.
2009.
Discrete choice methods with simulation.
Cambridge University Press.
- Tsybakov (2009)
Alexandre B. Tsybakov.
2009.
Introduction to nonparametric estimation.
Springer, New York. xii+214 pages.
https://doi.org/10.1007/b13794
Revised and extended from the 2004 French original, Translated by
Vladimir Zaiats.
- Tversky (1972)
Amos Tversky.
1972.
Choice by elimination.
Journal of mathematical psychology
9, 4 (1972),
341–367.
- Wainwright (2019)
Martin J. Wainwright.
2019.
High-Dimensional Statistics: A
Non-Asymptotic Viewpoint.
Cambridge University Press, Cambridge.
- Wei et al. (2020)
Keji Wei, Vikrant Vaze,
and Alexandre Jacquillat.
2020.
Airline timetable development and fleet assignment
incorporating passenger choice.
Transportation Science
54, 1 (2020),
139–163.
- Wei et al. (2022)
Keji Wei, Vikrant Vaze,
and Alexandre Jacquillat.
2022.
Transit planning optimization under ride-hailing
competition and traffic congestion.
Transportation Science
56, 3 (2022),
725–749.
- Zhang et al. (2025)
Yanzhao Zhang, Mingxin
Li, Dingkun Long, Xin Zhang,
Huan Lin, Baosong Yang,
Pengjun Xie, An Yang,
Dayiheng Liu, Junyang Lin,
Fei Huang, and Jingren Zhou.
2025.
Qwen3 Embedding: Advancing Text Embedding and
Reranking Through Foundation Models.
arXiv preprint arXiv:2506.05176
(2025).

## Appendix A Prior Work

There has been considerable interest in scaling probit estimation, with recent techniques extending the method from ten alternatives (e.g., Natarajan et al., 2000) to one hundred (e.g., Ding et al., 2024). As we show in the next section these methods cannot actually recover the correlations properly.

The nested logit (NL) relaxes the IIA axiom by grouping the alternatives in the groups and assuming IIA between the elements of the same group or the groups themselves. In the cat, golden retriever, and borzoi example, this can mean that first, the agents choose whether they prefer cats or dots and then choose between gold retrievers and borzois. In this structure, IIA holds between cats and dogs and between golden retrievers and borzois, but not between borzois and cats. In its generality, the NL is described by a tree whose leaves are the alternatives. To choose an alternative, an agent starts at the root and must select one of the current node’s children using an IIA model. The agent repeats this process until they reach a leaf (alternative). Ben-Akiva (1973) showed that the welfare and choice probabilities of the NL can be calculated in a bottom-up fashion as the value of each node is the log-sum-exp of the values of its children. Benson et al. (2016) show that at least $\Omega(n^{2})$ statistical tests are required to recover the structure of the NL.

The mixed logit McFadden and Train (2000) relaxes the IIA axioms by assuming that there exists an unobserved utility that would validate IIA. Since we do not observe these utilities, we have to marginalize them. The mixed logit is defined as

$$ $\operatorname*{\mathbb{P}}{\left\{I_{\mathcal{R}}=i\right\}}=\operatorname*{\mathbb{P}}{\left\{\forall_{j}u_{i}+\epsilon_{i}+A_{i}\geqslant u_{i}+\epsilon_{i}+A_{j}\right\}}=\int\text{sm}_{\tau}(u+A)_{i}{\,\mskip 0.0mu{}{\mathrm{d}\operatorname*{\mathbb{P}}}\mskip 0.0mu}{\left\{A\right\}}.$ $$

In practice, the integral is evaluated using numerical methods, and the mixed logit is learned using MLE. McFadden and Train (2000) showed that if they take the limit of $\tau$ to 0, this model converges to a RUM with utility $A$ because the softmax converges to the indicator function, returning one when $A_{i}\geqslant A_{j}$ for all $j$ and zero otherwise.

Over the years, many choice models have been developed and RUMs are by no means the only class of choice models. We can characterize them by

- 1.
representation power, for instance, the logit cannot represent correlated choices,
- 2.
number of parameters, while the logit has $n=|\mathcal{C}|$ parameters, the probit has $n(n+3)/2$ parameters, and
- 3.
whether they provide some notion of welfare.

Representative agents models (RAM), are defined as

$$ $\operatorname*{\mathbb{P}}{\left\{I_{\mathcal{R}}=i\right\}}={\left\{\arg\max_{\pi\in\Delta(\mathcal{R})}\langle\pi,u_{\mathcal{R}}\rangle-\Omega_{\mathcal{R}}(\pi)\right\}}_{i},$ $$

for some utility vector $u$ restricted the set of alternative $\mathcal{R}$, some strictly convex regularizer $\Omega_{\mathcal{R}}$, and the probability simplex over $\mathcal{R}$ denoted by $\Delta(\mathcal{R})$. RAMs also provide an expected welfare function, but learning a regularizer for all possible sets of alternatives may not be trivial. Taking $\Omega$ to be the negative entropy yields the same model as the logit (Anderson et al., 1988). Generally, an equivalent RAM exists for every RUM but not vice-versa (Hofbauer and Sandholm, 2002). As noted by works like Sørensen and Fosgerau (2022), working with RAMs may be more convenient for mathematical purposes. We refer to Feng et al. (2017) for a class halfway between RAMs and RUMs.

Tversky (1972) introduces a different class of models, where each agent splits the set of alternatives in a desirable and an undesirable subset. While the model has an exponential number of parameters (in terms of the number of alternatives) and requires a different type of data, it is subset-consistent for all possible choice models.

A wealth of work exists on approximations for the probit model starting with Clark (1961). Clark approximates $\max(X,Y)$ with a normal distribution. We refer to Kamakura (1989) and Bunch and Kitamura (1991) for references to other approximation methods. We note that Bunch and Kitamura (1991) finds that none of the approximations consistently outperform others, and all have critical failure modes. Compared to simulation-based methods, one of the most significant weaknesses of this type of work is the inability to trade compute for accuracy.

Train (2009, Chapter 5) and Bunch (1991) mention several ways of removing the symmetries in estimating probit models and how to verify that the parametrization is “correct”. Interestingly, they omit our reparametrization. McFadden (1980) claim that the primary issue with the probit is evaluating and differentiating the choice probabilities.

#### Notation.

We use $\mathbb{R}$ and $\mathbb{N}$ to denote the set of real and natural numbers respectively. For $n\in\mathbb{N}$, $\mathbb{R}^{n}$ and $\mathbb{R}^{n\times n}$ denote the set of $n$-dimensional vectors and $n\times n$ dimensional matrices respectively. Furthermore, $\mathbb{S}^{n}$ and $\mathcal{S}^{n\times n}$ correspond to the set of unit vectors and positive semi-definite matrices of dimension $n$. For $n\in\mathbb{N}$, $[n]$ is shorthand for $\{1,\ldots,n\}$. We denote the pdf and cdf of a standard Gaussian as $\phi$ and $\Phi$, respectively. For a matrix $A$, $\operatorname*{\mathrm{Tr}}(A)$ and $\det(A)$ denote the trace and determinant of $A$. For two vectors $x$ and $y$ in $\mathbb{R}^{n}$, $\langle x,y\rangle$ is their inner product. We use $\operatorname{TV}$ and $\operatorname{KL}$ for the total variation and Kullback–Leibler divergence. Lastly, $\mathrm{Choice}(\mu,\Sigma)$, for $\mu\in\mathbb{R}^{n}$ and $\Sigma\in\mathbb{R}^{n\times n}$, refers to the choice model defined by a RUM whose utilities follow a multivariate normal distribution $\mathcal{N}(\mu,\Sigma)$ whose mean is $\mu$ and covariance matrix is $\Sigma$.

## Appendix B Estimation with Three Alternatives - Proof of Theorem B.1

Here, we extend the arguments of [Theorem 4.1](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem1) presented in [Subsection 4.1](https://arxiv.org/html/2510.15839v1#S4.SS1) to the setting of estimation, where one aims to. Recall, our observability assumption from [Section 5](https://arxiv.org/html/2510.15839v1#S5):
See [5.1](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem1)
The main theorem of the section is stated below:

###### Theorem B.1 .

Let $(\mu,\Sigma)\in\mathbb{R}^{3}\times\mathcal{S}^{3\times 3}$ satisfy [Assumption 5.1](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem1) for some $\gamma>0$ and $\varepsilon,\delta\in(0,1/2]$. Then, there is an algorithm which when given $n$ i.i.d samples from $\mathrm{Choice}(\mu,\Sigma)$, returns estimates, $(\widehat{\mu},\widehat{\Sigma})$ satisfying for some $t>0$:

$$ $\displaystyle\lVert t\mu-\widehat{\mu}\rVert\leqslant\varepsilon$ $\displaystyle(1-\varepsilon)t^{2}\Sigma\preccurlyeq\widehat{\Sigma}\preccurlyeq(1+\varepsilon)t^{2}\Sigma$ $\displaystyle\operatorname*{\mathrm{Tr}}(t^{2}\Sigma),\operatorname*{\mathrm{Tr}}(\widehat{\Sigma})\geqslant\frac{1}{2}$ $$

with probability at least $1-\delta$ as long as $n\geqslant C\varepsilon^{-2}\gamma^{-20}\log(1/\delta)\log^{2}(1/(\gamma\varepsilon))$.

We begin with some useful technical results. The first concerns the maximizer of the minimum of the Gaussian masses of two symmetric cones defined by the intersection of two half-spaces.

###### Lemma B.2 .

Let $v_{1},v_{2}\in\mathbb{S}^{2}$. Then, we have:

$$ $\operatorname*{arg\,max}_{\mu}{\left(\min{\left\{\mathbb{P}_{X\thicksim\mathcal{N}(\mu,I)}{\left(\langle X,v_{1}\rangle,\langle X,v_{2}\rangle\geqslant 0\right)},\mathbb{P}_{X\thicksim\mathcal{N}(\mu,I)}{\left(\langle X,v_{1}\rangle,\langle X,v_{2}\rangle\leqslant 0\right)}\right\}}\right)}=\bm{0}.$ $$

###### Proof.

Consider any $\mu\neq 0$. Note, that without loss of generality, we may assume:

$$ $v_{1}=\begin{bmatrix}\sin(\theta)\\ -\cos(\theta)\end{bmatrix},\ v_{2}=\begin{bmatrix}\sin(\theta)\\ \cos(\theta)\end{bmatrix}.$ $$

for some $\theta\in[0,\pi/2]$. Now, observe:

$$ $\displaystyle\xi_{1}$ $\displaystyle\coloneqq\mathbb{P}_{X\thicksim\mathcal{N}(\mu,I)}{\left(\langle X,v_{1}\rangle,\langle X,v_{2}\rangle\geqslant 0\right)}=\frac{1}{2\pi}\int_{0}^{\infty}\int_{-x\tan\theta}^{x\tan\theta}\exp{\left\{-\frac{(x-\mu_{1})^{2}+(y-\mu_{2})^{2}}{2}\right\}}dydx$ $\displaystyle\xi_{2}$ $\displaystyle\coloneqq\mathbb{P}_{X\thicksim\mathcal{N}(\mu,I)}{\left(\langle X,v_{1}\rangle,\langle X,v_{2}\rangle\leqslant 0\right)}=\frac{1}{2\pi}\int_{0}^{\infty}\int_{-x\tan\theta}^{x\tan\theta}\exp{\left\{-\frac{(-x-\mu_{1})^{2}+(y-\mu_{2})^{2}}{2}\right\}}dydx$ $$

When $\mu_{1}>0$, $(x+\mu_{1})^{2}>x^{2}$ for all $x\geqslant 0$ and consequently:

$$ $\displaystyle\xi_{2}$ $\displaystyle\leqslant\frac{1}{2\pi}\int_{0}^{\infty}\int_{-x\tan\theta}^{x\tan\theta}\exp{\left\{-\frac{x^{2}+(y-\mu_{2})^{2}}{2}\right\}}dydx.$ $$

Similarly for $\mu_{1}<0$ with $\xi_{1}$ taking the place of $\xi_{2}$. Therefore, for any $\mu_{2}$:

$$ $\operatorname*{arg\,max}_{\mu_{1}}\min(\xi_{1},\xi_{2})=0.$ $$

###### Claim B.3 .

We have for any $t>0$:

$$ $\operatorname*{arg\,max}_{\mu}\int_{-t}^{t}\exp{\left\{-\frac{(x-\mu)^{2}}{2}\right\}}dx=0.$ $$

###### Proof.

First, define

$$ $f(\mu)\coloneqq\int_{-t}^{t}\exp{\left\{-\frac{(x-\mu)^{2}}{2}\right\}}dx.$ $$

We now have:

$$ $\displaystyle\frac{d}{d\mu}f(\mu)$ $\displaystyle=\int_{-t}^{t}(x-\mu)\exp{\left\{-\frac{(x-\mu)^{2}}{2}\right\}}dx$ $\displaystyle=\int_{(t+\mu)^{2}/2}^{(t-\mu)^{2}/2}\exp{\left\{-u\right\}}du=\exp{\left\{-\frac{(t+\mu)^{2}}{2}\right\}}-\exp{\left\{-\frac{(t-\mu)^{2}}{2}\right\}}.$ $$

Hence, we have:

$$ $\frac{d}{d\mu}f(\mu)\begin{cases}<0&\text{if }\mu>0\\ >0&\text{if }\mu<0\\ 0&\text{otherwise}\end{cases}.$ $$

Hence, $\mu=0$ is the unique minimizer of $f(\mu)$ concluding the proof of the claim.
∎

From [Claim B.3](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem3), we get for any $\mu_{2}\neq 0$:

$$ $\displaystyle\xi_{2}$ $\displaystyle<\frac{1}{2\pi}\int_{0}^{\infty}\int_{-x\tan\theta}^{x\tan\theta}\exp{\left\{-\frac{(x^{2}+y^{2})}{2}\right\}}dydx$ $\displaystyle=\mathbb{P}_{X\thicksim\mathcal{N}(0,I)}{\left\{\langle X,v_{1}\rangle,\langle X,v_{2}\rangle\geqslant 0\right\}}=\mathbb{P}_{X\thicksim\mathcal{N}(0,I)}{\left\{\langle X,v_{1}\rangle,\langle X,v_{2}\rangle\leqslant 0\right\}}$ $$

concluding the proof of the lemma.
∎

The following lemma establishes the probabilistic concentration properties required for our result with the parameter $\widetilde{\varepsilon}$ to be chosen subsequently.

###### Lemma B.4 .

There exists a constant $C>0$ such that:

$$ $\displaystyle\forall v_{1},v_{2}\in{\left\{\pm c_{i}\right\}}_{i=1}^{3}\text{ s.t }v_{1}\nparallel v_{2}:\left\lvert\frac{1}{n}\sum_{i=1}^{n}\bm{1}{\left\{\langle X_{i},v_{1}\rangle,\langle X_{i},v_{2}\rangle\geqslant 0\right\}}-\mathbb{P}_{X\thicksim\mathcal{N}(\mu,\Sigma)}{\left\{\langle X,v_{1}\rangle,\langle X,v_{2}\rangle\geqslant 0\right\}}\right\rvert\leqslant\widetilde{\varepsilon}$ $\displaystyle\forall v\in{\left\{\pm c_{i}\right\}}_{i=1}^{3}:\left\lvert\frac{1}{n}\sum_{i=1}^{n}\bm{1}{\left\{\langle X_{i},v\rangle\geqslant 0\right\}}-\mathbb{P}_{X\thicksim\mathcal{N}(\mu,\Sigma)}{\left\{\langle X,v\rangle\geqslant 0\right\}}\right\rvert\leqslant\widetilde{\varepsilon}$ $$

with probability at least $1-\delta$ if $n\geqslant C\log(1/\delta)/\widetilde{\varepsilon}^{2}$.

###### Proof.

The lemma follows from Hoeffding’s inequality ([Theorem E.1](https://arxiv.org/html/2510.15839v1#A5.Thmtheorem1)) along with a union bound over the $18$ events in the conclusion of the lemma.
∎

The next lemma shows that permutation probabilities remain stable under mild perturbations of the center of a Gaussian.

###### Lemma B.5 .

Let $\mu\in\mathbb{R}^{2}$ and $S$ be a set such that:

$$ $\mathbb{P}_{X\thicksim\mathcal{N}(\mu,I)}{\left\{X\in S\right\}}\geqslant\gamma.$ $$

Then, we have:

$$ $\forall\mu^{\prime}\in\mathbb{B}(\mu,\varepsilon):\left\lvert{\mathbb{P}_{X\thicksim\mathcal{N}(\mu^{\prime},I)}{\left\{X\in S\right\}}-\mathbb{P}_{X\thicksim\mathcal{N}(\mu,I)}{\left\{X\in S\right\}}}\right\rvert\leqslant 4\varepsilon\sqrt{\log(1/(\gamma\varepsilon))}\cdot\mathbb{P}_{X\thicksim\mathcal{N}(\mu,I)}{\left\{X\in S\right\}}.$ $$

###### Proof.

Let $\mu=0$ without loss of generality and defining $r=2(\sqrt{\log(1/(\gamma\varepsilon))}+\varepsilon)$, we have:

$$ $\displaystyle\mathbb{P}{\left\{X\in S\right\}}$ $\displaystyle=\frac{1}{2\pi}\int_{S}\exp{\left\{-\frac{\lVert x-\mu^{\prime}\rVert^{2}}{2}\right\}}dx$ $\displaystyle=\frac{1}{2\pi}{\left(\int_{S\cap\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x-\mu^{\prime}\rVert^{2}}{2}\right\}}dx+\int_{S\setminus\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x-\mu^{\prime}\rVert^{2}}{2}\right\}}dx\right)}$ $\displaystyle\leqslant\frac{1}{2\pi}\int_{S\cap\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x-\mu^{\prime}\rVert^{2}}{2}\right\}}dx+\mathbb{P}_{G\thicksim\mathcal{N}(\mu^{\prime},I)}{\left\{\lVert G\rVert\geqslant r\right\}}$ $\displaystyle\leqslant\frac{1}{2\pi}\int_{S\cap\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x-\mu^{\prime}\rVert^{2}}{2}\right\}}dx+\mathbb{P}_{G\thicksim\mathcal{N}(0,I)}{\left\{\lVert G\rVert\geqslant r-\varepsilon\right\}}$ $\displaystyle\leqslant\frac{1}{2\pi}\int_{S\cap\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x\rVert^{2}+\lVert\mu\rVert^{2}-2\langle x,\mu^{\prime}\rangle}{2}\right\}}dx+\mathbb{P}_{G\thicksim\mathcal{N}(0,I)}{\left\{\lVert G\rVert\geqslant r-\varepsilon\right\}}$ $\displaystyle\leqslant\frac{1}{2\pi}\int_{S\cap\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x\rVert^{2}-2\langle x,\mu^{\prime}\rangle}{2}\right\}}dx+\gamma\varepsilon$ $\displaystyle\leqslant\frac{1}{2\pi}\int_{S\cap\mathbb{B}(0,r)}\exp{\left\{\varepsilon r\right\}}\exp{\left\{-\frac{\lVert x\rVert^{2}}{2}\right\}}dx+\gamma\varepsilon$ $\displaystyle\leqslant\exp{\left\{\varepsilon r\right\}}\mathbb{P}_{X\thicksim\mathcal{N}(0,I)}{\left\{X\in S\right\}}+\gamma\varepsilon\leqslant(\exp(\varepsilon r)+\varepsilon)\cdot\mathbb{P}_{X\thicksim\mathcal{N}(0,I)}{\left\{X\in S\right\}}.$ $$

For the lower bound, we have:

$$ $\displaystyle\mathbb{P}{\left\{X\in S\right\}}$ $\displaystyle=\frac{1}{2\pi}\int_{S}\exp{\left\{-\frac{\lVert x-\mu^{\prime}\rVert^{2}}{2}\right\}}dx$ $\displaystyle=\frac{1}{2\pi}{\left(\int_{S\cap\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x-\mu^{\prime}\rVert^{2}}{2}\right\}}dx+\int_{S\setminus\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x-\mu^{\prime}\rVert^{2}}{2}\right\}}dx\right)}$ $\displaystyle\geqslant\frac{1}{2\pi}\int_{S\cap\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x-\mu^{\prime}\rVert^{2}}{2}\right\}}dx$ $\displaystyle=\frac{1}{2\pi}\int_{S\cap\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x\rVert^{2}+\lVert\mu\rVert^{2}-2\langle x,\mu^{\prime}\rangle}{2}\right\}}dx$ $\displaystyle\geqslant\frac{1}{2\pi}\int_{S\cap\mathbb{B}(0,r)}\exp{\left\{-\varepsilon(\varepsilon+r)\right\}}\exp{\left\{-\frac{\lVert x\rVert^{2}}{2}\right\}}dx$ $\displaystyle=\frac{\exp{\left\{-\varepsilon(\varepsilon+r)\right\}}}{2\pi}{\left(\int_{S}\exp{\left\{-\frac{\lVert x\rVert^{2}}{2}\right\}}dx-\int_{S\setminus\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x\rVert^{2}}{2}\right\}}dx\right)}$ $\displaystyle\geqslant\frac{\exp{\left\{-\varepsilon(\varepsilon+r)\right\}}}{2\pi}{\left(\int_{S}\exp{\left\{-\frac{\lVert x\rVert^{2}}{2}\right\}}dx-\int_{\mathbb{R}^{d}\setminus\mathbb{B}(0,r)}\exp{\left\{-\frac{\lVert x\rVert^{2}}{2}\right\}}dx\right)}$ $\displaystyle=\exp{\left\{-\varepsilon(\varepsilon+r)\right\}}{\left(\mathbb{P}_{X\thicksim\mathcal{N}(0,I)}{\left\{X\in S\right\}}-\mathbb{P}_{X\thicksim\mathcal{N}(0,I)}{\left\{\lVert X\rVert\geqslant r\right\}}\right)}$ $\displaystyle\geqslant(1-\varepsilon(\varepsilon+r))(1-\varepsilon)\mathbb{P}_{X\thicksim\mathcal{N}(0,I)}{\left\{X\in S\right\}}$ $\displaystyle\geqslant(1-2\varepsilon(\varepsilon+r))\mathbb{P}_{X\thicksim\mathcal{N}(0,I)}{\left\{X\in S\right\}}$ $$

which concludes the proof of the result.
∎

We also require the upper bound on the Gaussian tail.

###### Lemma B.6 .

For all $t\geqslant 0$, we have:

$$ $\mathbb{P}_{X\thicksim\mathcal{N}(0,1)}{\left\{X\geqslant t\right\}}\leqslant\frac{1}{2}\exp{\left\{-\frac{t^{2}}{2}\right\}}.$ $$

We will now adapt the three steps outlined in [Section 4](https://arxiv.org/html/2510.15839v1#S4) for estimation. These proofs are similar to those for identifiability but are substantially more technical. We will adopt a more streamlined notation for this proof. Recall that [Section 4](https://arxiv.org/html/2510.15839v1#S4) required two projections, the first to reduce the dimensionality to $2$ ([Figure 1](https://arxiv.org/html/2510.15839v1#S4.F1)) and another to reduce the $2$-dimensional Gaussian to the isotropic setting. Here, we will instead work with a single transformation. We start by defining:

$$ $c_{1}\coloneqq\begin{bmatrix}1\\ -1\\ 0\end{bmatrix},\ c_{2}\coloneqq\begin{bmatrix}0\\ 1\\ -1\end{bmatrix},\ c_{3}\coloneqq\begin{bmatrix}1\\ 0\\ -1\end{bmatrix}.$ $$

For the utility vector $x\thicksim\mathcal{N}(\mu,\Sigma)$, we observe the permutation $u_{1}\succ u_{2}\succ u_{3}$ when $\langle c_{1},x\rangle>0$ and $\langle c_{2},x\rangle>0$. Similar conditions may be derived for all other permutations. Note that $c_{1},c_{2}$ and $c_{3}$ are linearly dependent $c_{1}+c_{2}=c_{3}$, and any two form a basis for the subspace orthogonal to $\bm{1}$.

Consider the linear transformations $\Sigma^{-1/2}\in\mathbb{R}^{2\times 3}$ and $\Sigma^{1/2}\in\mathbb{R}^{2\times 3}$ where

$$ $\displaystyle\Sigma^{-1/2}\Sigma(\Sigma^{-1/2})^{\top}=\mathrm{Id}(2),$ (3) $\displaystyle\Sigma^{-1/2}(\Sigma^{1/2})^{\top}=\mathrm{Id}(2)$ (4) $\displaystyle\Sigma^{1/2}c_{1}=t_{1}\begin{bmatrix}1\\ 0\end{bmatrix},\text{ and}$ (5) $\displaystyle\Sigma^{1/2}c_{2}=\begin{bmatrix}\star\\ t_{2}\end{bmatrix}\text{ where }t_{2}\geqslant 0.$ (6) $$

Since we assume that $\Sigma$ has rank 2, ([3](https://arxiv.org/html/2510.15839v1#A2.E3)) must have a solution. Since the left-hand side of ([3](https://arxiv.org/html/2510.15839v1#A2.E3)) is invariant to rotations and reflections, without loss of generality, ([5](https://arxiv.org/html/2510.15839v1#A2.E5)) and ([6](https://arxiv.org/html/2510.15839v1#A2.E6)) can be satisfied. Observe that this implies a similar property for $c_{3}$ as $c_{1}+c_{2}=c_{3}$.

Let $\widetilde{\mu}\coloneqq\Sigma^{-1/2}\mu$ and consider the transformed vectors:

$$ $\widetilde{c}_{1}=\frac{\Sigma^{1/2}c_{1}}{\lVert\Sigma^{1/2}c_{1}\rVert},\ \widetilde{c}_{2}=\frac{\Sigma^{1/2}c_{2}}{\lVert\Sigma^{1/2}c_{2}\rVert},\ \text{ and }\widetilde{c}_{3}=\frac{\Sigma^{1/2}c_{3}}{\lVert\Sigma^{1/2}c_{3}\rVert}.$ $$

We now show that the quantities $\langle\widetilde{c}_{i},\widetilde{\mu}\rangle$ are estimable under the conclusion of [Lemma B.4](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem4). This extends the identification result from [Lemma 4.2](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem2).

###### Lemma B.7 .

Defining the estimates:

$$ $\widehat{\alpha_{i}}\coloneqq\Phi^{-1}{\left\{\sum_{j=1}^{n}\bm{1}{\left\{\langle X_{j},c_{i}\rangle\geqslant 0\right\}}\right\}}\text{ and }\alpha_{i}\coloneqq\langle\widetilde{c}_{i},\widetilde{\mu}\rangle,$ $$

we have:

$$ $\displaystyle\lvert\widehat{\alpha_{i}}-\alpha_{i}\rvert\leqslant\sqrt{2\pi}\cdot\frac{\widetilde{\varepsilon}}{\gamma}$ $\displaystyle-\sqrt{2\log(1/\gamma)}\leqslant\widehat{\alpha_{i}},\alpha_{i}\leqslant\sqrt{2\log(1/\gamma)}.$ $$

###### Proof.

Recall from [Lemma 4.2](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem2):

$$ $\alpha_{i}=\Phi^{-1}(\mathbb{P}_{X\thicksim\mathcal{N}(\mu,\Sigma)}{\left\{\langle X,c_{i}\rangle\geqslant 0\right\}}).$ $$

Furthermore, we have from [Assumptions 5.1](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem1) and [B.4](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem4):

$$ $\frac{\gamma}{2}\leqslant\frac{1}{n}\sum_{j=1}^{n}\bm{1}{\left\{\langle X_{j},c_{i}\rangle\geqslant 0\right\}}\leqslant 1-\frac{\gamma}{2}.$ $$

Therefore, we get from [Lemma B.6](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem6):

$$ $-\sqrt{2\log(1/\gamma)}\leqslant\widehat{\alpha_{i}},\alpha_{i}\leqslant\sqrt{2\log(1/\gamma)}.$ $$

Using this fact, we obtain:

$$ $\displaystyle\widetilde{\varepsilon}$ $\displaystyle\geqslant\lvert\Phi(\alpha_{i})-\Phi(\widehat{\alpha_{i}})\rvert=\left\lvert\int_{\alpha_{i}}^{\widehat{\alpha}_{i}}\phi(x)dx\right\rvert\geqslant\frac{1}{\sqrt{2\pi}}\lvert\alpha_{i}-\widehat{\alpha_{i}}\rvert\cdot\min_{x\in[\alpha_{i},\widehat{\alpha_{i}}]}\exp{\left\{-\frac{x^{2}}{2}\right\}}\geqslant\frac{1}{\sqrt{2\pi}}\lvert\alpha_{i}-\widehat{\alpha}_{i}\rvert\gamma.$ $$

By re-arranging the above, we get:

$$ $\lvert\alpha_{i}-\widehat{\alpha_{i}}\rvert\leqslant\sqrt{2\pi}\cdot\frac{\widetilde{\varepsilon}}{\gamma}$ $$

concluding the proof of the lemma.
∎

Next, we adapt the second step of our identification argument ([Lemma 4.3](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem3)) to estimation. As before, this step is substantially more involved to account for the statistical noise.

###### Lemma B.8 .

Let $\mu\in\mathbb{R}^{2}$ and $v_{1},v_{2}$ be two linearly independent unit vectors. Suppose, further that estimates $\widehat{d}_{1}\geqslant\widehat{d}_{2}\geqslant 0$ are known estimates such that:

$$ $\lvert\widehat{d}_{1}-\langle v_{1},\mu\rangle\rvert\leqslant\varepsilon\text{ and }\lvert\widehat{d}_{2}-\langle v_{2},\mu\rangle\rvert\leqslant\varepsilon.$ $$

Furthermore, assume that the following hold:

$$ $\forall u_{1}\in\{\pm v_{1}\},u_{2}\in\{\pm v_{2}\}:\mathbb{P}_{X\thicksim\mathcal{N}(\mu,I)}{\left\{\langle X,u_{1}\rangle,\langle X,u_{2}\rangle\geqslant 0\right\}}\geqslant\gamma$ $$

and we have access to estimates, ${\left\{\widehat{\gamma}_{s_{1},s_{2}}\right\}}_{s_{1}\in\{\pm v_{1}\},s_{2}\in\{\pm v_{2}\}}$ with:

$$ $\left\lvert\widehat{\gamma}_{s_{1},s_{2}}-\mathbb{P}_{X\thicksim\mathcal{N}(\mu,I)}{\left\{\langle X,s_{1}\rangle,\langle X,s_{2}\rangle\geqslant 0\right\}}\right\rvert\leqslant\varepsilon.$ $$

Then, we may recover estimate $\widehat{\beta}$ such that:

$$ $\lvert\widehat{\beta}-\langle v_{1},v_{2}\rangle\rvert\leqslant C\frac{\varepsilon}{\gamma^{4}}\sqrt{\log(1/(\gamma\varepsilon))}$ $$

from $\widehat{d}_{1}$, $\widehat{d}_{2}$, and $\{\widehat{\gamma}_{s_{1},s_{2}}\}$.

###### Proof.

As in the proof of [Lemma 4.3](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem3), we may assume $v_{1}=e_{2}$ and $(v_{2})_{1}\geqslant 0$ without loss of generality. Since, $v_{2}$ is a unit vector, it may be parameterized as $v_{2}=v(\theta^{*})$ for $\theta^{*}\in[0,\pi]$ with $v(\theta)$ defined as follows:

$$ $v(\theta)\coloneqq\begin{bmatrix}\sin(\theta)\\ -\cos(\theta)\end{bmatrix}\text{ for }\theta\in[0,\pi].$ $$

Now, defining $\widehat{\mu}(\theta)$:

$$ $\widehat{\mu}(\theta)\coloneqq\begin{bmatrix}\widetilde{\mu}(\theta)\\ \widehat{d}_{1}\end{bmatrix}\text{ where }\widetilde{\mu}(\theta)\coloneqq\frac{\widehat{d}_{1}\cos(\theta)+\widehat{d}_{2}}{\sin(\theta)}.$ $$

Our estimate of $\theta^{*}$ (with $\cos(\pi-\theta^{*})=\langle v_{1},v_{2}\rangle$) is defined below:

$$ $\widehat{\theta}\coloneqq\operatorname*{arg\,min}_{\theta}\max_{s_{1}\in\{\pm v_{1}\},s_{2}\in\{\pm v_{2}\}}\ell_{s_{1},s_{2}}(\theta)\text{ where }\ell_{s_{1},s_{2}}(\theta)\coloneqq\left\lvert\mathbb{P}_{X\thicksim\mathcal{N}(\widehat{\mu}(\theta),I)}{\left\{\langle X,s_{1}\rangle,\langle X,s_{2}\rangle\geqslant 0\right\}}-\widehat{\gamma}_{s_{1},s_{2}}\right\rvert.$ $$

Our proof that $\widehat{\theta}$ is close to $\theta^{*}$ will proceed in two steps:

- 1.
In the first step, we show that $\theta$ is a solution with small error
- 2.
Next, we show that all points outside a small interval around $\theta$ have large error.

###### Claim B.9 .

We have:

$$ $\displaystyle\forall s_{1}\in\{\pm v_{1}\},s_{2}\in\{\pm v_{2}\}:\ell_{s_{1},s_{2}}(\theta^{*})\leqslant\frac{64\varepsilon}{\gamma}\sqrt{\log(1/(\gamma\varepsilon))}$ $\displaystyle\lVert\mu-\widehat{\mu}(\theta^{*})\rVert\leqslant 4\frac{\varepsilon}{\gamma}.$ $$

###### Proof.

Observe from the rotational symmetry of a standard Gaussian that for any $u_{1},u_{2}\in\mathbb{S}^{1}$:

$$ $\mathbb{P}_{X\thicksim\mathcal{N}(0,I)}{\left\{\langle X,u_{1}\rangle,\langle X,u_{2}\rangle\geqslant 0\right\}}=\frac{1}{2}-\frac{\arccos(\langle u_{1},u_{2}\rangle)}{2\pi}.$ $$

Hence, applying [Lemma B.2](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem2) with the vectors $(v_{1},v_{2})$ yields:

$$ $\frac{\pi-\theta^{*}}{2\pi}\geqslant\gamma\implies\theta^{*}\leqslant\pi-2\pi\gamma.$ $$

Similarly, applying [Lemma B.2](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem2) with the vectors $(v_{1},-v_{2})$ yields:

$$ $\theta^{*}\geqslant 2\pi\gamma.$ $$

Hence, we get:

$$ $2\pi\gamma\leqslant\theta^{*}\leqslant\pi-2\pi\gamma\implies\sin(\theta^{*})\geqslant\frac{2}{\pi}\cdot 2\pi\gamma=4\gamma.$ $$

Now, observing that:

$$ $\mu=\begin{bmatrix}\frac{d_{1}\cos(\theta^{*})+d_{2}}{\sin(\theta^{*})}\\ d_{1}\end{bmatrix},$ $$

we get:

$$ $\displaystyle\lVert\mu-\widehat{\mu}(\theta^{*})\rVert$ $\displaystyle\leqslant\left\lvert\frac{d_{1}\cos(\theta^{*})+d_{2}}{\sin(\theta^{*})}-\frac{\widehat{d}_{1}\cos(\theta^{*})+\widehat{d}_{2}}{\sin(\theta^{*})}\right\rvert+\left\lvert d_{1}-\widehat{d}_{1}\right\rvert$ $\displaystyle\leqslant\lvert d_{1}-\widehat{d}_{1}\rvert\lvert\cot(\theta^{*})\rvert+\lvert d_{2}-\widehat{d}_{2}\rvert\lvert\csc(\theta^{*})\rvert+\varepsilon\leqslant 4\frac{\varepsilon}{\gamma}$ $$

yielding the first claim. The second now follows from [Lemma B.5](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem5).
∎

We now proceed to the second step of the proof. We start by bounding $\widetilde{\mu}(\theta^{*})$.

###### Claim B.10 .

We have:

$$ $\lvert\widetilde{\mu}(\theta^{*})\rvert\leqslant\lvert\widetilde{\mu}(\theta^{*})\rvert\leqslant\sqrt{2\log(1/(2\gamma))}+\frac{\varepsilon}{\gamma}$ $$

###### Proof.

Furthermore, observe that:

$$ $\displaystyle\forall\theta\in{\left[0,\frac{\pi}{2}\right]}:\{x:\langle x,v_{1}\rangle,\langle x,v_{2}\rangle\geqslant 0\}\subseteq\{x:x_{1}\geqslant 0\}$ $\displaystyle\forall\theta\in{\left[\frac{\pi}{2},\pi\right]}:\{x:\langle x,-v_{1}\rangle,\langle x,v_{2}\rangle\geqslant 0\}\subseteq\{x:x_{1}\geqslant 0\}.$ $$

As a consequence, in both cases:

$$ $\mathbb{P}_{X\thicksim\mathcal{N}(\mu,I)}{\left\{X_{1}\geqslant 0\right\}}\geqslant\gamma.$ $$

Hence, we get from [Lemma B.6](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem6):

$$ $\mu_{1}\geqslant-\sqrt{2\log(1/2\gamma)}.$ $$

Similarly, we get

$$ $\displaystyle\forall\theta\in{\left[0,\frac{\pi}{2}\right]}:\{x:\langle x,-v_{1}\rangle,\langle x,-v_{2}\rangle\geqslant 0\}\subseteq\{x:x_{1}\leqslant 0\}$ $\displaystyle\forall\theta\in{\left[\frac{\pi}{2},\pi\right]}:\{x:\langle x,v_{1}\rangle,\langle x,-v_{2}\rangle\geqslant 0\}\subseteq\{x:x_{1}\leqslant 0\}.$ $$

We, hence, get as a consequence:

$$ $\mathbb{P}_{X\thicksim\mathcal{N}(\mu,I)}{\left\{X_{1}\leqslant 0\right\}}\geqslant\gamma.$ $$

[Lemma B.6](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem6) similarly yields:

$$ $\mu_{1}\leqslant\sqrt{2\log(1/(2\gamma))}.$ $$

Note, as before:

$$ $\mu=\begin{bmatrix}\frac{d_{1}\cos(\theta^{*})+d_{2}}{\sin(\theta^{*})}\\ d_{1}\end{bmatrix}.$ $$

Finally, we get from [Claim B.9](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem9):

$$ $\lVert\mu-\widehat{\mu}(\theta^{*})\rVert\leqslant\frac{\varepsilon}{\gamma}\implies\lvert\widetilde{\mu}(\theta^{*})\rvert\leqslant\sqrt{2\log(1/(2\gamma))}+\frac{\varepsilon}{\gamma}$ $$

concluding the proof of the claim.
∎

Similar to [Lemma 4.3](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem3), define:

$$ $\widehat{\gamma}(\theta)\coloneqq\mathbb{P}_{X\thicksim\mathcal{N}(\widehat{\mu}(\theta),I)}{\left\{\langle X,v_{1}\rangle,\langle X,v_{2}\rangle\leqslant 0\right\}}.$ $$

The next claim lower bounds the derivative of $\widehat{\gamma}$ in an interval around $\theta^{*}$.

###### Claim B.11 .

We have:

$$ $\displaystyle\forall\theta\in(0,\pi):\widehat{\gamma}^{\prime}(\theta)>0$ $\displaystyle\forall\theta\in[\theta_{l},\theta_{h}]:\widehat{\gamma}^{\prime}(\theta)\geqslant\frac{\gamma^{3}}{16}$ $\displaystyle\text{ with }\theta_{l}=\theta^{*}-\nu,\quad\theta_{h}=\theta^{*}+\nu,\quad\nu=C\frac{\varepsilon\sqrt{\log(1/(\gamma\varepsilon))}}{\gamma^{4}}.$ $$

###### Proof.

The proof that $\widehat{\gamma}^{\prime}(\theta)>0$ for all $\theta\in(0,\pi)$ is identical to that of the corresponding result in [Lemma 4.3](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem3). We now proceed to the second claim. Observe as in the proof of [Lemma 4.3](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem3) that:

$$ $\displaystyle\widehat{\gamma}^{\prime}(\theta)$ $\displaystyle\geqslant\int_{0}^{\infty}\frac{1}{2\pi}\exp{\left\{-\frac{(r\cos(\theta)+\widetilde{\mu}(\theta))^{2}+(r\sin(\theta)+\widehat{d}_{1})^{2}}{2}\right\}}rdr$ $\displaystyle=\exp{\left\{-\frac{\widetilde{\mu}(\theta)^{2}+\widehat{d}_{1}^{2}}{2}\right\}}\int_{0}^{\infty}\frac{1}{2\pi}\exp{\left\{-\frac{r^{2}+2r(\cos(\theta)\widetilde{\mu}(\theta)+\sin(\theta)\widehat{d}_{1})}{2}\right\}}rdr$ $\displaystyle\geqslant\exp{\left\{-\frac{\widetilde{\mu}(\theta)^{2}+\widehat{d}_{1}^{2}}{2}\right\}}\int_{0}^{1}\frac{1}{2\pi}\exp{\left\{-\frac{r^{2}+2r(\cos(\theta)\widetilde{\mu}(\theta)+\sin(\theta)\widehat{d}_{1})}{2}\right\}}rdr$ $\displaystyle\geqslant\exp{\left\{-\frac{\widetilde{\mu}(\theta)^{2}+\widehat{d}_{1}^{2}+2(\lvert\widetilde{\mu}(\theta)\rvert+\lvert\widehat{d}_{1}\rvert)}{2}\right\}}\int_{0}^{1}\frac{1}{2\pi}\exp{\left\{-\frac{r^{2}}{2}\right\}}rdr$ $\displaystyle\geqslant\exp{\left\{-\frac{\widetilde{\mu}(\theta)^{2}+\widehat{d}_{1}^{2}+2(\lvert\widetilde{\mu}(\theta)\rvert+\lvert\widehat{d}_{1}\rvert)}{2}\right\}}\cdot\frac{1}{16}\geqslant\gamma^{3}\cdot\frac{1}{16}=\frac{\gamma^{3}}{16}$ $$

where the last inequality follows from the following:

$$ $\displaystyle\lvert\widetilde{\mu}(\theta)\rvert$ $\displaystyle\leqslant\lvert\widetilde{\mu}(\theta^{*})\rvert+(\theta_{h}-\theta_{l})\max_{\theta\in[\theta_{l},\theta_{h}]}\lvert\widetilde{\mu}^{\prime}(\theta)\rvert$ $\displaystyle=\lvert\widetilde{\mu}(\theta^{*})\rvert+(\theta_{h}-\theta_{l})\max_{\theta\in[\theta_{l},\theta_{h}]}\left\lvert\frac{\widehat{d}_{1}-\widehat{d}_{2}\cos(\theta)}{\sin^{2}(\theta)}\right\rvert\leqslant\lvert\widetilde{\mu}(\theta^{*})\rvert+(\theta_{h}-\theta_{l})\cdot\frac{\sqrt{\log(2/\gamma)}}{\gamma^{2}}$ $$

concluding the proof of the claim with [Claim B.10](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem10).
∎

From [Claim B.11](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem11), we get that:

$$ $\displaystyle\forall\theta\geqslant\theta_{h}:\widehat{\gamma}(\theta)\geqslant\widehat{\gamma}(\theta^{*})+\frac{\nu\gamma^{3}}{16}$ $\displaystyle\forall\theta\leqslant\theta_{l}:\widehat{\gamma}(\theta)\geqslant\widehat{\gamma}(\theta^{*})-\frac{\nu\gamma^{3}}{16}.$ $$

Consequently, we obtain from [Claim B.9](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem9) and picking $C^{\prime}$ large enough:

$$ $\displaystyle\forall\theta\geqslant\theta_{h}:\widehat{\gamma}(\theta)-\widehat{\gamma}_{-v_{1},-v_{2}}\geqslant\frac{\nu\gamma^{3}}{16}-\frac{64\varepsilon}{\gamma}\sqrt{\log(1/(\gamma\varepsilon))}\geqslant\frac{128\varepsilon}{\gamma}\sqrt{\log(1/(\gamma\varepsilon))}$ $\displaystyle\forall\theta\leqslant\theta_{l}:\widehat{\gamma}_{-v_{1},-v_{2}}-\widehat{\gamma}(\theta)\leqslant\frac{64\varepsilon}{\gamma}\sqrt{\log(1/(\gamma\varepsilon))}-\frac{\nu\gamma^{3}}{16}\leqslant-\frac{128\varepsilon}{\gamma}\sqrt{\log(1/(\gamma\varepsilon))}.$ $$

Hence, we get that $\widehat{\theta}\in[\theta_{l},\theta_{h}]$. Defining $\widehat{\beta}=-\cos(\widehat{\theta})$, the conclusion follows from the $1$-Lipschitzness of the function $-\cos(\theta)$.
∎

###### Proof of Theorem B.1 .

The proof proceeds similarly to that of [Theorem 4.1](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem1). Let $\widetilde{\varepsilon}$ be a parameter that will be chosen subsequently. We have from [Lemma B.4](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem4) that:

$$ $\displaystyle\forall v_{1},v_{2}\in{\left\{\pm c_{i}\right\}}_{i=1}^{3}\text{ s.t }v_{1}\nparallel v_{2}:\left\lvert\frac{1}{n}\sum_{i=1}^{n}\bm{1}{\left\{\langle X_{i},v_{1}\rangle,\langle X_{i},v_{2}\rangle\geqslant 0\right\}}-\mathbb{P}_{X\thicksim\mathcal{N}(\mu,\Sigma)}{\left\{\langle X,v_{1}\rangle,\langle X,v_{2}\rangle\geqslant 0\right\}}\right\rvert\leqslant\widetilde{\varepsilon}$ $\displaystyle\forall v\in{\left\{\pm c_{i}\right\}}_{i=1}^{3}:\left\lvert\frac{1}{n}\sum_{i=1}^{n}\bm{1}{\left\{\langle X_{i},v\rangle\geqslant 0\right\}}-\mathbb{P}_{X\thicksim\mathcal{N}(\mu,\Sigma)}{\left\{\langle X,v\rangle\geqslant 0\right\}}\right\rvert\leqslant\widetilde{\varepsilon}$ $$

with probability at least $1-\delta$ when $n\geqslant C(\log(1/\delta)/\widetilde{\varepsilon}^{2})$. We condition on this event in the remainder of the proof. Recall the definition of the vectors:

$$ $\displaystyle\widetilde{c}_{i}=\frac{\Sigma^{1/2}c_{i}}{\lVert\Sigma^{1/2}c_{i}\rVert}\text{ and }\widetilde{\mu}=\Sigma^{-1/2}\mu.$ $$

From [Lemma B.7](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem7), we obtain estimates, $\widehat{\alpha}_{i}$ such that:

$$ $\lvert\langle\widetilde{\mu},\widetilde{c}_{i}\rangle-\widehat{\alpha}_{i}\rvert\leqslant\frac{8\widetilde{\varepsilon}}{\gamma}\eqqcolon\varepsilon^{\prime}.$ $$

An application of [Lemma B.8](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem8) now yields estimates $\widehat{\beta}_{ij}$ for all $i,j\in[3]$ such that:

$$ $\lvert\widehat{\beta}_{ij}-\langle\widetilde{c}_{i},\widetilde{c}_{j}\rangle\rvert\leqslant C\frac{\widetilde{\varepsilon}}{\gamma^{4}}\sqrt{\log(1/(\gamma\varepsilon))}\eqqcolon\varepsilon^{\dagger}.$ $$

We now fix the normalization of $\Sigma^{1/2}$ and assume without loss of generality that:

$$ $\Sigma^{1/2}c_{1}=\begin{bmatrix}1\\ 0\end{bmatrix},\ \Sigma^{1/2}c_{2}=s\begin{bmatrix}\beta_{12}\\ \sqrt{1-\beta^{2}_{12}}\end{bmatrix},\text{ and }\Sigma^{1/2}c_{3}=t\begin{bmatrix}\beta_{13}\\ \sqrt{1-\beta^{2}_{13}}\end{bmatrix}$ $$

Noting that $c_{1}+c_{2}=c_{3}$, we get similarly to before:

$$ $\begin{bmatrix}1\\ 0\end{bmatrix}=\begin{bmatrix}\beta_{13}&\beta_{12}\\ \sqrt{1-\beta_{13}^{2}}&\sqrt{1-\beta_{12}^{2}}\end{bmatrix}\begin{bmatrix}t\\ -s\end{bmatrix}.$ $$

As observed in [Theorem 4.1](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem1), the above equations allow for identifiability of $\Sigma$. However, for estimation, we incur errors due to inaccurate estimates of quantities $\beta_{ij}$ and $s$. We start with the corresponding empirical approximation of the above equality:

$$ $\begin{bmatrix}1\\ 0\end{bmatrix}=\begin{bmatrix}\widehat{\beta}_{13}&\widehat{\beta}_{12}\\ \sqrt{1-\widehat{\beta}_{13}^{2}}&\sqrt{1-\widehat{\beta}_{12}^{2}}\end{bmatrix}\begin{bmatrix}\widehat{t}\\ -\widehat{s}.\end{bmatrix}$ $$

In our first claim, we bound the approximation error of the above matrices by their empirical counterparts. Define:

$$ $\forall i,j\in[3]\text{ s.t }i\neq j:B_{ij}\coloneqq\begin{bmatrix}\beta_{1i}&\beta_{1j}\\ \sqrt{1-\beta_{1i}^{2}}&\sqrt{1-\beta_{1j}^{2}}\end{bmatrix}\text{ and }\widehat{B}_{ij}\coloneqq\begin{bmatrix}\widehat{\beta}_{1i}&\widehat{\beta}_{1j}\\ \sqrt{1-\widehat{\beta}_{1i}^{2}}&\sqrt{1-\widehat{\beta}_{1j}^{2}}\end{bmatrix}.$ $$

Our approximation guarantees are stated below:

###### Claim B.12 .

We have:

$$ $\displaystyle\lvert\det(B_{ij})\rvert\geqslant\frac{2\gamma}{\pi}\text{ and }\lvert\det(\widehat{B}_{ij})\rvert\geqslant\frac{\gamma}{\pi}$ $\displaystyle\lVert B_{ij}\rVert,\lVert\widehat{B}_{ij}\rVert\leqslant 2$ $\displaystyle\lVert B_{ij}-\widehat{B}_{ij}\rVert\leqslant\frac{4\varepsilon^{\dagger}}{\gamma}$ $\displaystyle\lVert B_{ij}^{-1}\rVert\leqslant\frac{\pi}{\gamma}\text{ and }\lVert\widehat{B}_{ij}^{-1}\rVert\leqslant\frac{2\pi}{\gamma}$ $\displaystyle\lVert B_{ij}^{-1}-\widehat{B}_{ij}^{-1}\rVert\leqslant\frac{8\varepsilon^{\dagger}\pi^{2}}{\gamma^{3}}.$ $$

###### Proof.

We have as a consequence of [Lemma B.2](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem2) and [Assumption 5.1](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem1) that $\langle\widetilde{c}_{i},\widetilde{c}_{j}\rangle=\cos(\theta_{ij})$ for some $\gamma\leqslant\theta_{ij}\leqslant\pi-\gamma$. Similarly, we get from the approximation guarantees of [Lemma B.8](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem8) that the empirical estimates satisfy $\langle\widehat{c}_{i},\widehat{c}_{j}\rangle=\cos(\widehat{\theta}_{ij})$ for $\nicefrac{{\gamma}}{{2}}\leqslant\widehat{\theta}_{ij}\leqslant\pi-\nicefrac{{\gamma}}{{2}}$. Consequently, we have:

$$ $\lvert\det(B_{ij})\rvert\geqslant\lvert\sin(\theta_{ij})\rvert\geqslant\frac{2\gamma}{\pi}\text{ and }\lvert\det(\widehat{B}_{ij})\rvert\geqslant\sin(\widehat{\theta}_{ij})\geqslant\frac{\gamma}{\pi}$ $$

establishing the first result of the claim. For the second, we have:

$$ $\lVert B_{ij}\rVert\leqslant\lVert B_{ij}\rVert_{F}=\sqrt{2}$ $$

and similarly for $\widehat{B}_{ij}$. For the third, observe again from the guarantees of $\theta_{ij}$ and $\widehat{\theta}$:

$$ $\left\lvert\sqrt{1-\beta_{ij}^{2}}-\sqrt{1-\widehat{\beta}_{ij}^{2}}\right\rvert=\left\lvert\frac{(\beta_{ij}+\widehat{\beta}_{ij})(\beta_{ij}-\widehat{\beta}_{ij})}{\sqrt{1-\beta_{ij}^{2}}+\sqrt{1-\widehat{\beta}_{ij}^{2}}}\right\rvert\leqslant\frac{2\varepsilon^{\dagger}}{\gamma}$ $$

and consequently,

$$ $\lVert B_{ij}-\widehat{B}_{ij}\rVert\leqslant\lVert B_{ij}-\widehat{B}_{ij}\rVert_{F}\leqslant 2\cdot\frac{2\varepsilon^{\dagger}}{\gamma}=\frac{4\varepsilon^{\dagger}}{\gamma}.$ $$

For the fourth claim, we have:

$$ $\lVert B_{ij}^{-1}\rVert=\frac{1}{\sigma_{\mathrm{min}}(B_{ij})}=\frac{\lVert B_{ij}\rVert}{\lvert\det(B_{ij})\rvert}\leqslant\frac{\pi}{\gamma}$ $$

and similarly, for $\widehat{B}_{ij}$. For the final claim, we have:

$$ $\displaystyle\frac{\gamma}{\pi}\lVert B_{ij}^{-1}-\widehat{B}_{ij}^{-1}\rVert$ $\displaystyle\leqslant\sigma_{\mathrm{\min}}\lVert B_{ij}^{-1}-\widehat{B}_{ij}^{-1}\rVert\leqslant\lVert B_{ij}(B_{ij}^{-1}-\widehat{B}_{ij}^{-1})\rVert=\lVert I-B_{ij}\widehat{B}_{ij}^{-1}\rVert$ $\displaystyle=\lVert I-\widehat{B}_{ij}\widehat{B}_{ij}^{-1}-(B_{ij}-\widehat{B}_{ij})\widehat{B}_{ij}^{-1}\rVert=\lVert(B_{ij}-\widehat{B}_{ij})\widehat{B}_{ij}^{-1}\rVert$ $\displaystyle\leqslant\lVert B_{ij}-\widehat{B}_{ij}\rVert\lVert\widehat{B}_{ij}^{-1}\rVert\leqslant\frac{2\pi}{\gamma}\lVert B_{ij}-\widehat{B}_{ij}\rVert\leqslant\frac{8\pi\varepsilon^{\dagger}}{\gamma^{2}}.$ $$

∎

Our next claim bounds the magnitude of $s$ and the relative error of its approximation by $\widehat{s}$.

###### Claim B.13 .

We have:

$$ $\displaystyle\frac{\pi}{\gamma}\geqslant\max{\left\{s,t\right\}}\geqslant\frac{1}{2}\text{ and }\lvert s-\widehat{s}\rvert,\lvert t-\widehat{t}\rvert\leqslant\frac{8\varepsilon^{\dagger}\pi^{2}}{\gamma^{3}}.$ $$

###### Proof.

For the first claim, observe the following

$$ $\displaystyle\beta_{13}t-\beta_{12}s=1\implies s+t\geqslant 1,$ $$

implying the lower bound. For the upper bound:

$$ $\max{\left\{s,t\right\}}\leqslant\left\lVert B_{23}^{-1}\begin{bmatrix}1\\ 0\end{bmatrix}\right\rVert\leqslant\lVert B_{23}^{-1}\rVert$ $$

and the conclusion follows from [Claim B.12](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem12). For the second, we have:

$$ $\lvert s-\widehat{s}\rvert,\lvert t-\widehat{t}\rvert\leqslant\left\lVert(B_{23}^{-1}-\widehat{B}_{23}^{-1})\begin{bmatrix}1\\ 0\end{bmatrix}\right\rVert\leqslant\lVert B^{-1}_{23}-\widehat{B}^{-1}_{23}\rVert$ $$

and the conclusion follows from [Claim B.12](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem12).
∎

The remainder of the proof proceeds in two cases: 1) $\widehat{s}\geqslant\widehat{t}$ or 2) $\widehat{t}>\widehat{s}$. We start with the first:

Case 1: $\widehat{s}\geqslant\widehat{t}$. Since $c_{1}$ and $c_{2}$ are a basis for the subspace orthogonal to $\bm{1}$, we may write:

$$ $\Sigma^{1/2}=AC\text{ where }C=\begin{bmatrix}c_{1}^{\top}\\ c_{2}^{\top}\end{bmatrix}\text{ and }A\in\mathbb{R}^{2\times 2}.$ $$

Therefore, we get:

$$ $\Sigma^{1/2}C^{\top}=A(CC^{\top})=\begin{bmatrix}1&s\beta_{12}\\ 0&s\sqrt{1-\beta_{12}^{2}}\end{bmatrix}\implies A=\begin{bmatrix}1&\beta_{12}\\ 0&\sqrt{1-\beta_{12}^{2}}\end{bmatrix}\begin{bmatrix}1&0\\ 0&s\end{bmatrix}(CC^{\top})^{-1}.$ $$

We may now write its empirical counterpart:

$$ $\widehat{A}=\begin{bmatrix}1&\widehat{\beta}_{12}\\ 0&\sqrt{1-\widehat{\beta}_{12}^{2}}\end{bmatrix}\begin{bmatrix}1&0\\ 0&\widehat{s}\end{bmatrix}(CC^{\top})^{-1}.$ $$

Noting that $\lVert(CC^{\top})^{-1}\rVert\leqslant 1$, we get from [Claims B.12](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem12) and [B.13](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem13):

$$ $\displaystyle\lVert A-\widehat{A}\rVert$ $\displaystyle\leqslant\left\lVert\widehat{B}_{12}\begin{bmatrix}1&0\\ 0&\widehat{s}\end{bmatrix}-B_{12}\begin{bmatrix}1&0\\ 0&s\end{bmatrix}\right\rVert=\left\lVert(\widehat{B}_{12}-B_{12})\begin{bmatrix}1&0\\ 0&\widehat{s}\end{bmatrix}-B_{12}\begin{bmatrix}0&0\\ 0&s-\widehat{s}\end{bmatrix}\right\rVert$ $\displaystyle\leqslant\left\lVert(\widehat{B}_{12}-B_{12})\begin{bmatrix}1&0\\ 0&\widehat{s}\end{bmatrix}\right\rVert+\left\lVert\widehat{B}_{12}\begin{bmatrix}0&0\\ 0&s-\widehat{s}\end{bmatrix}\right\rVert$ $\displaystyle\leqslant\lVert\widehat{B}_{12}-B_{12}\rVert\max{\left\{1,\widehat{s}\right\}}+\lVert\widehat{B}_{12}\rVert\lvert s-\widehat{s}\rvert\leqslant\frac{4\varepsilon^{\dagger}}{\gamma}\cdot\frac{2\pi}{\gamma}+2\cdot\frac{8\varepsilon^{\dagger}\pi^{2}}{\gamma^{3}}\leqslant 24\frac{\varepsilon^{\dagger}\pi^{2}}{\gamma^{3}}.$ $$

Furthermore, we have for any $v\in\mathbb{R}^{2}$ with $\lVert v\rVert=1$:

$$ $\displaystyle\lVert Av\rVert$ $\displaystyle=\left\lVert B_{12}\begin{bmatrix}1&0\\ 0&s\end{bmatrix}(CC^{\top})^{-1}v\right\rVert\geqslant\sigma_{\mathrm{min}}(B_{12})\cdot\sigma_{\mathrm{min}}{\left(\begin{bmatrix}1&0\\ 0&s\end{bmatrix}\right)}\cdot\sigma_{\mathrm{min}}((CC^{\top})^{-1})$ $\displaystyle\geqslant\frac{\gamma}{\pi}\cdot\min{\left\{1,s\right\}}\cdot\frac{1}{3}\geqslant\frac{\gamma}{12\pi}$ $$

where the inquality follows from an explicit calculation for $(CC^{\top})^{-1}$, [Claim B.13](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem13) for the middle term and [Claim B.12](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem12) for the first term. Similarly, note that:

$$ $\displaystyle\lVert Av\rVert$ $\displaystyle=\left\lVert B_{12}\begin{bmatrix}1&0\\ 0&s\end{bmatrix}(CC^{\top})^{-1}v\right\rVert\leqslant\sigma_{\mathrm{max}}(B_{12})\cdot\sigma_{\mathrm{max}}{\left(\begin{bmatrix}1&0\\ 0&s\end{bmatrix}\right)}\cdot\sigma_{\mathrm{max}}((CC^{\top})^{-1})$ $\displaystyle\leqslant 2\cdot\max{\left\{1,s\right\}}\cdot 1\leqslant\frac{2\pi}{\gamma}$ $$

from [Claims B.12](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem12) and [B.13](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem13). Consequently, we obtain for all $\lVert v\rVert=1$:

$$ $\displaystyle\left\lvert v^{\top}A^{\top}Av-v^{\top}\widehat{A}^{\top}\widehat{A}v\right\rvert$ $\displaystyle=\left\lvert\lVert Av\rVert^{2}-\lVert\widehat{A}v\rVert^{2}\right\rvert=(\lVert Av\rVert+\lVert\widehat{A}v\rVert)\left\lvert\lVert Av\rVert-\lVert\widehat{A}v\rVert\right\rvert$ $\displaystyle\leqslant(\lVert A\rVert+\lVert\widehat{A}\rVert)\lVert(A-\widehat{A})v\rVert\leqslant{\left(\frac{4\pi}{\gamma}+\lVert A-\widehat{A}\rVert\right)}\lVert A-\widehat{A}\rVert\leqslant 120\frac{\varepsilon^{\dagger}\pi^{3}}{\gamma^{4}}.$ $$

From the above three displays, we get:

$$ ${\left(1-\varepsilon^{\ddagger}\right)}A^{\top}A\preccurlyeq\widehat{A}^{\top}\widehat{A}\preccurlyeq{\left(1+\varepsilon^{\ddagger}\right)}A^{\top}A\text{ where }\varepsilon^{\ddagger}\coloneqq\frac{2^{15}\pi^{5}\varepsilon^{\dagger}}{\gamma^{6}}.$ $$

Finally, defining our estimate $\widehat{\Sigma}^{1/2}=\widehat{A}C$ and since $\Sigma=C^{\top}A^{\top}AC$, we get:

$$ ${\left(1-\varepsilon^{\ddagger}\right)}\Sigma\preccurlyeq\widehat{\Sigma}\preccurlyeq{\left(1+\varepsilon^{\ddagger}\right)}\Sigma.$ $$

Case 2: $\widehat{t}\geqslant\widehat{s}$. Here, we use $c_{1}$ and $c_{3}$ as a basis for the subspace orthogonal to $\bm{1}$ and write:

$$ $\Sigma^{1/2}=AC\text{ where }C=\begin{bmatrix}c_{1}^{\top}\\ c_{3}^{\top}\end{bmatrix}\text{ and }A\in\mathbb{R}^{2\times 2}.$ $$

Therefore, we get:

$$ $\Sigma^{1/2}C^{\top}=A(CC^{\top})=\begin{bmatrix}1&t\beta_{13}\\ 0&t\sqrt{1-\beta_{13}^{2}}\end{bmatrix}\implies A=\begin{bmatrix}1&\beta_{13}\\ 0&\sqrt{1-\beta_{13}^{2}}\end{bmatrix}\begin{bmatrix}1&0\\ 0&t\end{bmatrix}(CC^{\top})^{-1}.$ $$

The remainder of the proof is identical to the previous setting with $t$ taking the role of $s$
and $B_{13}$ (resp $\widehat{B}_{13}$) that of $B_{12}$ (resp $\widehat{B}_{13}$). This concludes the estimation guarantees for $\Sigma$.

Estimating $\mu$: To estimate $\mu$, we adopt the $B_{1i}$ and $C$ from the previous two cases and note:

$$ $\widetilde{\mu}=\Sigma^{-1/2}\mu,\ B_{1i}^{\top}\widetilde{\mu}=Q\implies\mu=(\Sigma^{1/2})^{\top}\widetilde{\mu}=C^{\top}A\widetilde{\mu}=C^{\top}A^{\top}(B_{1i}^{-1})^{\top}Q\text{ with }Q\coloneqq\begin{bmatrix}\alpha_{1}\\ \alpha_{i}\end{bmatrix}.$ $$

Empirically, we use the estimates:

$$ $\widehat{\mu}=C^{\top}\widehat{A}^{\top}(\widehat{B}_{1i}^{-1})^{\top}\widehat{Q}\text{ with }\widehat{Q}\coloneqq\begin{bmatrix}\widehat{\alpha}_{1}\\ \widehat{\alpha_{i}}\end{bmatrix}.$ $$

Therefore, we get that:

$$ $\displaystyle\lVert\widehat{\mu}-\mu\rVert$ $\displaystyle=\left\lVert C^{\top}(A^{\top}(B_{1i}^{-1})^{\top}Q-\widehat{A}^{\top}(\widehat{B}_{1i}^{-1})^{\top}\widehat{Q})\right\rVert\leqslant 2\left\lVert A^{\top}(B_{1i}^{-1})^{\top}Q-\widehat{A}^{\top}(\widehat{B}_{1i}^{-1})^{\top}\widehat{Q}\right\rVert$ $\displaystyle\leqslant 2(\lVert A^{\top}(B_{1i}^{-1})^{\top}(Q-\widehat{Q})\rVert+\lVert A^{\top}(B_{1i}^{-1})^{\top}\widehat{Q}-\widehat{A}^{\top}(\widehat{B}_{1i}^{-1})^{\top}\widehat{Q}\rVert)$ $\displaystyle\leqslant 2(\lVert A^{\top}(B_{1i}^{-1})^{\top}\rVert\lVert(Q-\widehat{Q})\rVert+\lVert A^{\top}(B_{1i}^{-1})^{\top}-\widehat{A}^{\top}(\widehat{B}_{1i}^{-1})^{\top}\rVert\lVert\widehat{Q}\rVert)$ $\displaystyle\leqslant 4{\left(\left\lVert A^{\top}(B_{1i}^{-1})^{\top}\right\rVert\varepsilon^{\prime}+\left\lVert A^{\top}(B_{1i}^{-1})^{\top}-\widehat{A}^{\top}(\widehat{B}_{1i}^{-1})^{\top}\right\rVert\sqrt{\log(1/\gamma)}\right)}.$ (7) $$

For the first term, we have by [Claim B.12](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem12):

$$ $\lVert A^{\top}(B_{1i}^{-1})^{\top}\rVert\leqslant\lVert A^{\top}\rVert\lVert(B_{1i}^{-1})^{\top}\rVert=\lVert A\rVert\lVert B_{1i}^{-1}\rVert\leqslant\frac{2\pi}{\gamma}\cdot\frac{\pi}{\gamma}=\frac{2\pi^{2}}{\gamma^{2}}.$ $$

For the second, we have:

$$ $\displaystyle\lVert A^{\top}(B_{1i}^{-1})^{\top}-\widehat{A}^{\top}(\widehat{B}_{1i}^{-1})^{\top}\rVert$ $\displaystyle=\lVert B_{1i}^{-1}A-\widehat{B}_{1i}^{-1}\widehat{A}\rVert\leqslant\lVert B_{1i}^{-1}(A-\widehat{A})\rVert+\lVert(B_{1i}^{-1}-\widehat{B}_{1i}^{-1})\widehat{A}\rVert$ $\displaystyle\leqslant\lVert B_{1i}^{-1}\rVert\lVert A-\widehat{A}\rVert+\lVert B^{-1}_{1i}-\widehat{B}^{-1}_{1i}\rVert\lVert\widehat{A}\rVert$ $\displaystyle\leqslant\frac{\pi}{\gamma}\cdot\frac{24\varepsilon^{\dagger}\pi^{2}}{\gamma^{3}}+\frac{8\varepsilon^{\dagger}\pi^{2}}{\gamma^{3}}\cdot\frac{2\pi}{\gamma}=\frac{40\pi^{3}\varepsilon^{\dagger}}{\gamma^{4}}.$ $$

Plugging this back into ([7](https://arxiv.org/html/2510.15839v1#A2.Ex171)) yields:

$$ $\lVert\widehat{\mu}-\mu\rVert\leqslant\frac{200\pi^{3}\sqrt{\log(1/\gamma)}}{\gamma^{4}}\varepsilon^{\dagger}.$ $$

Now, setting:

$$ $\widetilde{\varepsilon}\coloneqq c\frac{\varepsilon\gamma^{10}}{\log(1/(\gamma\varepsilon))}$ $$

for some small constant $c$, the theorem follows by the definitions of $\varepsilon^{\dagger}$ and $\varepsilon^{\ddagger}$.
∎

###### Theorem B.1 .

###### Lemma B.2 .

###### Proof.

###### Claim B.3 .

###### Proof.

###### Lemma B.4 .

###### Proof.

###### Lemma B.5 .

###### Proof.

###### Lemma B.6 .

###### Lemma B.7 .

###### Proof.

###### Lemma B.8 .

###### Proof.

###### Claim B.9 .

###### Proof.

###### Claim B.10 .

###### Proof.

###### Claim B.11 .

###### Proof.

###### Proof of Theorem B.1 .

###### Claim B.12 .

###### Proof.

###### Claim B.13 .

###### Proof.

## Appendix C Estimation - Multiple Alternatives

In [Appendix B](https://arxiv.org/html/2510.15839v1#A2), we extended [Theorem 4.1](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem1) to an algorithm with estimation guarantees ([Theorem B.1](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem1)) that is robust to statistical noise. Hence, we now have a procedure that allows recovering the parameters $\mu,\Sigma$ on $3\times 3$ sub-matrices (up to the symmetries described in [Assumption 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1)). We now prove the main result of [Section 5](https://arxiv.org/html/2510.15839v1#S5), [Theorem 5.2](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem2), stated below for convenience, which uses the estimation algorithm for $3$ items to construct one for the general $n$-item setting.
See [5.2](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem2)
In [Theorem 4.4](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem4), we showed that $\mu,\Sigma$ can be recovered from exact specifications of all $3\times 3$ sub-matrices. However, this approach has $2$ substantial drawbacks:

- 1.
It requires comparison data for all of the $\Omega(n^{3})$ sub-matrices
- 2.
The sub-matrices need to be specified exactly which 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:

$$ $\displaystyle G=(V,E)$ $\displaystyle V=\{\{i,j\}\in[n]\times[n]:i\neq j\}$ $\displaystyle E=\{(\{i,j\},\{j,k\}):i\neq j\neq k\neq i\}.$ $$

Observe that each potential sub-matrix corresponds to an edge of the graph and the vertices correspond to entries of $\Sigma$ that we aim to recover. Furthermore, note that a particular choice of sub-matrices corresponds to a sub-graph. The properties of this sub-graph relate to both of the aforementioned challenges:

- 1.
The sub-graph being connected suffices for recovering $\Sigma$ from $3\times 3$ sub-matrices
- 2.
The error of this aggregation process scales linearly with the diameter of the sub-graph

The next result (efficiently) constructs a sub-graph with drastically fewer edges ($O(n^{2})$ vs $O(n^{3})$) while maintaining connectivity of the sub-graph with small (logarithmic) diameter.

###### Lemma C.1 .

There exists a subgraph $G^{\prime}=(V,E^{\prime})$ with $E^{\prime}\subset E$ satisfying:

$$ $\displaystyle\lvert E^{\prime}\rvert\leqslant n^{2}$ $\displaystyle\forall v_{1},v_{2}\in V:\mathrm{dist}_{G^{\prime}}(v_{1},v_{2})\leqslant 4(\log(n)+1).$ $$

###### Proof.

We will construct our edge set as follows:

- 1.
For any $i\in[n]$, let $V_{i}=[n]\setminus\{i\}$
- 2.
Consider a complete binary tree $T_{i}=(V_{i},E_{i})$ on $V_{i}$
- 3.
For any $(j,k)\in E_{i}$, add edge $(\{i,j\},\{i,k\})$ to $G^{\prime}$.

First, observe that $E^{\prime}\subset E$ by construction. Next, we have:

$$ $\lvert E^{\prime}\rvert\leqslant n\cdot\lvert E_{i}\rvert=n(n-2)<n^{2}.$ $$

For the final claim, we have from the construction of $E^{\prime}$ and $T_{i}$ being a complete binary tree:

$$ $\forall i\neq j\neq k\neq i:\mathrm{dist}_{G^{\prime}}{\left(\{i,j\},\{i,k\}\right)}\leqslant 2(\log(n)+1).$ $$

Hence, we get:

$$ $\mathrm{dist}_{G^{\prime}}(\{i,j\},\{k,l\})\leqslant\mathrm{dist}_{G^{\prime}}(\{i,j\},\{j,k\})+\mathrm{dist}_{G^{\prime}}(\{j,k\},\{k,l\})\leqslant 4(\log(n)+1)$ $$

concluding the proof of the lemma.
∎

Before we proceed, we introduce some notation to ease exposition. We will now run the algorithm of [Theorem B.1](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem1) on the tuples $(i,j,k)$ such that $(\{i,j\},\{j,k\})\in E^{\prime}$. Let $(\widehat{\mu}_{ijk},\widehat{\Sigma}_{ijk})$ be the estimates obtained through this process. We will abuse notation and write $(i,j,k)\in E^{\prime}$ for the set of tuples. It will be convenient to index matrices with alternatives rather than numerical indices. We will typically use $c_{ij}=e_{i}-e_{j}$ with $e_{i}$ and $e_{j}$ corresponding to the vectors with $1$ for item $i$ and $j$ respectively and 0 elsewhere. In the context estimates $\widehat{\Sigma}_{i,j,k}$, $e_{i}$ and $e_{j}$ (and consequently, $c_{i,j}$) will denote vectors in $\mathbb{R}^{3}$ for the positions corresponding to $i$ and $j$ while in the context of $\Sigma$, they will denote vectors in $\mathbb{R}^{n}$.

We now recover $\Sigma^{*}$ by solving the following convex program:

$$ $\displaystyle\operatorname*{arg\,min}_{t,\Sigma}t$ $\displaystyle\forall i,j,k\in E^{\prime}:(1-t)\frac{c_{ij}^{\top}\widehat{\Sigma}_{ijk}c_{ij}}{c_{ik}^{\top}\widehat{\Sigma}_{ijk}c_{ik}}\leqslant\frac{c_{ij}^{\top}\Sigma c_{ij}}{c_{ik}^{\top}\Sigma c_{ik}}\leqslant(1+t)\frac{c_{ij}^{\top}\widehat{\Sigma}_{ijk}c_{ij}}{c_{ik}^{\top}\widehat{\Sigma}_{ijk}c_{ik}}$ $\displaystyle\operatorname*{\mathrm{Tr}}(\Sigma)=n$ $\displaystyle\Sigma\bm{1}=\bm{0}$ $$

We assume that the estimates, $\widehat{\Sigma}_{ijk}$ are obtained by the algorithm of [Theorem B.1](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem1) with failure probability $\delta^{\prime}=\delta/(2n^{2})$ and accuracy $\widehat{\varepsilon}$ for a parameter $\widetilde{\varepsilon}$ to be decided subsequently. Letting $\overline{\Sigma}$ denote the solution to the above (linear) program and noting that $\Sigma^{*}$ is a solution with $t=\widetilde{\varepsilon}$, we get that $\overline{\Sigma}$ has cost at most $\widetilde{\varepsilon}$. We require a brief technical result bounding the largest entry of $\Sigma$.

###### Lemma C.2 .

We have:

$$ $\Sigma_{ii}\leqslant\frac{100\log(8/\gamma)}{\gamma^{2}}.$ $$

###### Proof.

By Markov’s inequality, there exist two indices $j,k$ such that $\Sigma_{jj},\Sigma_{kk}\leqslant 2$. We start by bounding the distance between $\mu_{j}$ and $\mu_{k}$. Let $X\thicksim\mathcal{N}(\mu_{ijk},\Sigma_{ijk})$ and we have:

$$ $\displaystyle\mathbb{P}{\left\{\lvert X_{j}-\mu_{j}\rvert\geqslant 2\sqrt{\log(4/\gamma)}\right\}}\leqslant\frac{\gamma}{4}$ $\displaystyle\mathbb{P}{\left\{\lvert X_{k}-\mu_{k}\rvert\geqslant 2\sqrt{\log(4/\gamma)}\right\}}\leqslant\frac{\gamma}{4}.$ $$

From the above two inequalities and [Assumption 5.1](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem1):

$$ $\min{\left\{\mathbb{P}{\left\{X_{j}\geqslant X_{k}\right\}},\mathbb{P}{\left\{X_{j}\leqslant X_{k}\right\}}\right\}}\geqslant\gamma,$ $$

we get the following set of inequalities by the probabilistic method:

$$ $\displaystyle\mu_{j}+2\sqrt{\log(4/\gamma)}\geqslant\mu_{k}-2\sqrt{\log(4/\gamma)}\implies\mu_{k}-\mu_{j}\leqslant 4\sqrt{\log(4/\gamma)}$ $\displaystyle\mu_{j}-2\sqrt{\log(4/\gamma)}\leqslant\mu_{k}+2\sqrt{\log(4/\gamma)}\implies\mu_{k}-\mu_{j}\geqslant-4\sqrt{\log(4/\gamma)}.$ $$

The above two inequalities yield:

$$ $\lvert\mu_{j}-\mu_{k}\rvert\leqslant 4\sqrt{\log(4/\gamma)}.$ (8) $$

Next, we have again:

$$ $\displaystyle\mathbb{P}{\left\{\lvert X_{j}-\mu_{j}\rvert\geqslant 2\sqrt{\log(8/\gamma)}\right\}}\leqslant\frac{\gamma}{8}$ $\displaystyle\mathbb{P}{\left\{\lvert X_{k}-\mu_{k}\rvert\geqslant 2\sqrt{\log(8/\gamma)}\right\}}\leqslant\frac{\gamma}{8}.$ $$

By a union bound and using [Eq. 8](https://arxiv.org/html/2510.15839v1#A3.E8), we get:

$$ $\displaystyle\mathbb{P}{\left\{X_{j},X_{k}\in[\mu_{j}-8\sqrt{\log(8/\gamma)},\mu_{j}+8\sqrt{\log(8/\gamma)}]\right\}}\geqslant 1-\frac{\gamma}{4}.$ $$

Denoting the event in the above probability by $E$, we now have from [Assumption 5.1](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem1):

$$ $\displaystyle\gamma$ $\displaystyle\leqslant\mathbb{P}{\left\{X_{i}\in[X_{j},X_{k}]\right\}}=\mathbb{P}{\left\{X_{i}\in[X_{j},X_{k}]\cap E\right\}}+\mathbb{P}{\left\{X_{i}\in[X_{j},X_{k}]\cap E^{c}\right\}}$ $\displaystyle\leqslant\mathbb{P}{\left\{X_{i}\in{\left[\mu_{j}-8\sqrt{\log(8/\gamma)},\mu_{j}+8\sqrt{\log(8/\gamma)}\right]}\right\}}+\mathbb{P}{\left\{E^{c}\right\}}$ $\displaystyle\leqslant\frac{1}{\sqrt{2\pi\Sigma_{ii}}}\cdot 16\sqrt{\log(8/\gamma)}+\frac{\gamma}{4}.$ $$

By rearranging the above inequality,

$$ $\sqrt{\Sigma_{ii}}\leqslant\frac{64}{3\sqrt{2\pi}\gamma}\sqrt{\log(8/\gamma)}\implies\Sigma_{ii}\leqslant\frac{100\log(8/\gamma)}{\gamma^{2}}.$ $$

∎

We now show that $\overline{\Sigma}$ is close to $\Sigma^{*}$.

###### Lemma C.3 .

We have:

$$ $\forall i,j\in[n]:\lvert\Sigma_{ij}-\Sigma^{*}_{ij}\rvert\leqslant C\gamma^{-2}(\log(n)+1)\log(8/\gamma)\widetilde{\varepsilon}.$ $$

###### Proof.

First, observe from the fact that $\overline{\Sigma}\bm{1}=\bm{0}$:

$$ $c_{ij}^{\top}\overline{\Sigma}c_{ij}=\Sigma_{ii}+\Sigma_{jj}-2\Sigma_{ij}\implies\sum_{j=1}^{n}c_{ij}^{\top}\overline{\Sigma}c_{ij}=n\overline{\Sigma}_{ii}+\operatorname*{\mathrm{Tr}}(\overline{\Sigma})=n\overline{\Sigma}_{ii}+n.$ (9) $$

Furthermore, we have from the guarantees of [Theorem B.1](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem1) that:

$$ $\forall i,j,k\in E^{\prime}:(1-4\widetilde{\varepsilon})\frac{c_{ij}^{\top}\Sigma^{*}c_{ij}}{c_{ik}^{\top}\Sigma^{*}c_{ik}}\leqslant\frac{c_{ij}^{\top}\widehat{\Sigma}_{ijk}c_{ij}}{c_{ik}^{\top}\widehat{\Sigma}_{ijk}c_{ik}}\leqslant(1+4\widetilde{\varepsilon})\frac{c_{ij}^{\top}\Sigma^{*}c_{ij}}{c_{ik}^{\top}\Sigma^{*}c_{ik}}.$ $$

Putting these together with the constraints on $\overline{\Sigma}$, we get:

$$ $\forall i,j,k\in E^{\prime}:(1-6\widetilde{\varepsilon})\frac{c_{ij}^{\top}\Sigma^{*}c_{ij}}{c_{ik}^{\top}\Sigma^{*}c_{ik}}\leqslant\frac{c_{ij}^{\top}\overline{\Sigma}c_{ij}}{c_{ik}^{\top}\overline{\Sigma}c_{ik}}\leqslant(1+6\widetilde{\varepsilon})\frac{c_{ij}^{\top}\Sigma^{*}c_{ij}}{c_{ik}^{\top}\Sigma^{*}c_{ik}}.$ $$

From [Lemma C.1](https://arxiv.org/html/2510.15839v1#A3.Thmtheorem1), that for any $\{i,j\}$ and $\{k,l\}$, there exists a path $v_{0}\coloneqq\{i,j\},v_{1},\dots,v_{T}=\{k,l\}$ with $T\leqslant 4(\log(n)+1)$ with $(v_{i-1},v_{i})\in E^{\prime}$ for all $i\in[T]$. Now observing that:

$$ $\displaystyle\frac{c_{v_{0}}^{\top}\overline{\Sigma}c_{v_{0}}}{c_{v_{T}}^{\top}\overline{\Sigma}c_{v_{T}}}=\prod_{i=1}^{T}\frac{c_{v_{i-1}}^{\top}\overline{\Sigma}c_{v_{i-1}}}{c_{v_{i}}^{\top}\overline{\Sigma}c_{v_{i}}}$ $\displaystyle\frac{c_{v_{0}}^{\top}\Sigma^{*}c_{v_{0}}}{c_{v_{T}}^{\top}\Sigma^{*}c_{v_{T}}}=\prod_{i=1}^{T}\frac{c_{v_{i-1}}^{\top}\Sigma^{*}c_{v_{i-1}}}{c_{v_{i}}^{\top}\Sigma^{*}c_{v_{i}}}$ $$

We get for any $i,j,k,l$ with $i\neq j$ and $k\neq l$:

$$ $(1-\varepsilon^{\dagger})\frac{c_{ij}^{\top}\Sigma^{*}c_{ij}}{c_{kl}^{\top}\Sigma^{*}c_{kl}}\leqslant\frac{c_{ij}^{\top}\overline{\Sigma}c_{ij}}{c_{kl}^{\top}\overline{\Sigma}c_{kl}}\leqslant(1+\varepsilon^{\dagger})\frac{c_{ij}^{\top}\Sigma^{*}c_{ij}}{c_{kl}^{\top}\Sigma^{*}c_{kl}}\text{ where }\varepsilon^{\dagger}=50\widetilde{\varepsilon}(\log(n)+1).$ $$

Now, consider the ratios:

$$ $\forall i\neq j:r_{ij}\coloneqq\frac{c_{ij}^{\top}\overline{\Sigma}c_{ij}}{c_{ij}^{\top}\Sigma^{*}c_{ij}},\ r_{\mathrm{min}}\coloneqq\min_{ij}r_{ij}\text{ and }r_{\mathrm{max}}\coloneqq\max_{ij}r_{ij}.$ $$

As a consequence, we have for any $i,j,k,l$:

$$ $r_{\mathrm{min}}\leqslant r_{\mathrm{max}}\leqslant(1+\varepsilon^{\dagger})r_{\mathrm{min}}.$ $$

Hence, we get:

$$ $\displaystyle\sum_{ij}c_{ij}^{\top}\overline{\Sigma}c_{ij}=n\sum_{i}(\overline{\Sigma}_{ii}+1)=2n^{2}=\sum_{ij}c_{ij}^{\top}\Sigma^{*}c_{ij}$ $\displaystyle r_{\mathrm{min}}(2n^{2})=r_{\mathrm{min}}\sum_{ij}c_{ij}^{\top}\Sigma^{*}c_{ij}\leqslant\sum_{ij}c_{ij}^{\top}\overline{\Sigma}c_{ij}=2n^{2}\leqslant r_{\mathrm{max}}\sum_{ij}c_{ij}^{\top}\Sigma^{*}c_{ij}\leqslant(1+\varepsilon^{\dagger})r_{\mathrm{min}}(2n^{2}).$ $$

Therefore, we get:

$$ $r_{\mathrm{min}}\leqslant 1\leqslant r_{\mathrm{max}}\leqslant(1+\varepsilon^{\dagger})r_{\mathrm{min}}\implies(1-\varepsilon^{\dagger})\leqslant r_{\mathrm{min}}\leqslant r_{\mathrm{max}}\leqslant(1+\varepsilon^{\dagger}).$ $$

Plugging this into to [Eq. 9](https://arxiv.org/html/2510.15839v1#A3.E9), we get:

$$ $(1-\varepsilon^{\dagger})n(\Sigma^{*}_{ii}+1)=(1-\varepsilon^{\dagger})\sum_{j=1}^{n}c_{ij}\Sigma^{*}c_{ij}\leqslant n(\overline{\Sigma}_{ii}+1)\leqslant(1+\varepsilon^{\dagger})\sum_{j=1}^{n}c_{ij}\Sigma^{*}c_{ij}=(1+\varepsilon^{\dagger})n(\Sigma^{*}_{ii}+1).$ $$

By re-arranging the above, we get:

$$ $\forall i:\lvert\Sigma^{*}_{ii}-\overline{\Sigma}_{ii}\rvert\leqslant\varepsilon^{\dagger}(\Sigma^{*}_{ii}+1).$ $$

For the off-diagonal terms, observe:

$$ $\overline{\Sigma}_{ij}=\frac{c_{ij}^{\top}\overline{\Sigma}c_{ij}-\overline{\Sigma}_{ii}-\overline{\Sigma}_{jj}}{2}\leqslant\frac{(1+\varepsilon^{\dagger})c_{ij}\Sigma^{*}c_{ij}-(1-\varepsilon^{\dagger})(\Sigma^{*}_{ii}+\Sigma^{*}_{jj})+2\varepsilon^{\dagger}}{2}\leqslant\Sigma^{*}_{ij}+\varepsilon^{\dagger}(2(\Sigma^{*}_{ii}+\Sigma^{*}_{jj})+1).$ $$

Similarly, we get:

$$ $\overline{\Sigma}_{ij}=\frac{c_{ij}^{\top}\overline{\Sigma}c_{ij}-\overline{\Sigma}_{ii}-\overline{\Sigma}_{jj}}{2}\geqslant\frac{(1-\varepsilon^{\dagger})c_{ij}\Sigma^{*}c_{ij}-(1+\varepsilon^{\dagger})(\Sigma^{*}_{ii}+\Sigma^{*}_{jj})-2\varepsilon^{\dagger}}{2}\leqslant\Sigma^{*}_{ij}-\varepsilon^{\dagger}(2(\Sigma^{*}_{ii}+\Sigma^{*}_{jj})+1).$ $$

Putting the above two displays together, we get:

$$ $\lvert\Sigma_{ij}-\Sigma^{*}_{ij}\rvert\leqslant 2\varepsilon^{\dagger}(\Sigma^{*}_{ii}+\Sigma^{*}_{jj}+1)$ $$

which with [Lemma C.2](https://arxiv.org/html/2510.15839v1#A3.Thmtheorem2), concludes the proof of the lemma.
∎

A similar approach now allows recovering $\mu^{*}$ with a related convex program.

###### Lemma C.4 .

We have:

$$ $\lVert\bar{\mu}-\mu^{*}\rVert_{\infty}\leqslant\frac{4000\log(8/\gamma)}{\gamma}\varepsilon^{\dagger}.$ $$

###### Proof.

We use $\mu_{ijk}$ and $\Sigma_{ijk}$ (and correspondingly for their starred and barred variants) to denote the restriction of $\mu$ and $\Sigma$ (and their variants) to the alternatives $i,j,$ and $k$, and projected orthogonal to the vector $\bm{1}$. We estimate some rescaling parameters to obtain $\overline{\Sigma}$ from the $3$-way estimates. Define:

$$ $\forall i,j,k\in E^{\prime}:s^{2}_{ijk}\coloneqq\frac{\operatorname*{\mathrm{Tr}}(\overline{\Sigma}_{ijk})}{\operatorname*{\mathrm{Tr}}(\widehat{\Sigma}_{ijk})}.$ $$

The linear program we solve to find $\mu$ is defined below:

$$ $\displaystyle\operatorname*{arg\,min}_{t,\mu}t$ $\displaystyle\forall i,j,k\in E^{\prime}:\left\lVert s_{ijk}\widehat{\mu}_{ijk}-\mu_{ijk}\right\rVert_{\infty}\leqslant t$ $\displaystyle\langle\mu,\bm{1}\rangle=0.$ $$

Before we proceed, we prove an analogue of [Lemma C.2](https://arxiv.org/html/2510.15839v1#A3.Thmtheorem2) which bounds the mean of $\mu$.

###### Lemma C.5 .

We have:

$$ $\forall i\in[n]:\lvert\mu_{i}\rvert\leqslant\frac{40\log(8/\gamma)}{\gamma}.$ $$

###### Proof.

First, define:

$$ $i_{M}\coloneqq\max_{i}\mu_{i}\text{ and }i_{m}=\min_{i}\mu_{i}.$ $$

Consider the random variable:

$$ $Y=X_{i_{M}}-X_{i_{m}}\text{ for }X\thicksim\mathcal{N}(\mu,\Sigma).$ $$

We have from [Lemma C.2](https://arxiv.org/html/2510.15839v1#A3.Thmtheorem2):

$$ $\mathbb{E}[Y]=\mu_{i_{M}}-\mu_{i_{m}}\text{ and }\operatorname*{\mathrm{Var}}(Y)\leqslant\frac{400\log(8/\gamma)}{\gamma^{2}}\eqqcolon\sigma^{2}.$ $$

However, we also have:

$$ $\mathbb{P}{\left\{Y\leqslant 0\right\}}\geqslant\gamma\implies\mathbb{P}_{Z\thicksim\mathcal{N}(0,\sigma^{2})}{\left\{Z\leqslant-(\mu_{i_{M}}-\mu_{i_{m}})\right\}}\geqslant\gamma.$ $$

Hence, we get from [Lemma B.6](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem6):

$$ $\lVert\mu\rVert_{\infty}\leqslant\mu_{i_{M}}-\mu_{i_{m}}\leqslant\sigma\sqrt{2\log(1/\gamma)},$ $$

concluding the proof of the lemma.
∎

First, let:

$$ $\Sigma^{*}_{ijk}=\widetilde{s}_{ijk}^{2}\widetilde{\Sigma}^{*}_{ijk},\text{ and }\mu^{*}_{ijk}=\widetilde{s}_{ijk}\widetilde{\mu}^{*}_{ijk}$ $$

be such that:

$$ $\displaystyle(1-\widetilde{\varepsilon})\widetilde{\Sigma}^{*}_{ijk}\preccurlyeq\widehat{\Sigma}_{ijk}\preccurlyeq(1+\widetilde{\varepsilon})\widetilde{\Sigma}^{*}_{ijk}$ $\displaystyle\lVert\widetilde{\mu}^{*}_{ijk}-\widehat{\mu}_{ijk}\rVert\leqslant\widetilde{\varepsilon}$ $$

guaranteed by [Theorem B.1](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem1). Note that:

$$ $\forall l,m\in\{i,j,k\}:(1-\varepsilon^{\dagger})c_{lm}^{\top}\Sigma^{*}_{ijk}c_{lm}\leqslant c_{lm}^{\top}\overline{\Sigma}_{ijk}c_{lm}\leqslant(1+\varepsilon^{\dagger})c_{lm}^{\top}\Sigma^{*}_{ijk}c_{lm}.$ $$

As a consequence, we have:

$$ $\displaystyle(1-\varepsilon^{\dagger})\sum_{lm}c_{lm}^{\top}\Sigma^{*}_{ijk}c_{lm}$ $\displaystyle=(1-\varepsilon^{\dagger})6\operatorname*{\mathrm{Tr}}(\Sigma^{*}_{ijk})\leqslant\sum_{lm}c_{lm}^{\top}\overline{\Sigma}_{ijk}c_{lm}=6\operatorname*{\mathrm{Tr}}(\overline{\Sigma}_{ijk})$ $\displaystyle\leqslant(1+\varepsilon^{\dagger})\sum_{lm}c_{lm}^{\top}\Sigma^{*}_{ijk}c_{lm}=(1+\varepsilon^{\dagger})6\operatorname*{\mathrm{Tr}}(\Sigma^{*}_{ijk}).$ $$

As a consequence, we get:

$$ $(1-\varepsilon^{\dagger})\operatorname*{\mathrm{Tr}}(\Sigma^{*}_{ijk})\leqslant\operatorname*{\mathrm{Tr}}(\bar{\Sigma}_{ijk})\leqslant(1+\varepsilon^{\dagger})\operatorname*{\mathrm{Tr}}(\Sigma^{*}_{ijk}).$ $$

Similarly, we get that:

$$ $(1-\widetilde{\varepsilon})\operatorname*{\mathrm{Tr}}(\widetilde{\Sigma}^{*}_{ijk})\leqslant\operatorname*{\mathrm{Tr}}(\widehat{\Sigma}_{ijk})\leqslant(1+\widetilde{\varepsilon})\operatorname*{\mathrm{Tr}}(\widetilde{\Sigma}^{*}_{ijk}).$ $$

Consequently, we get that:

$$ $(1-4\varepsilon^{\dagger})\widetilde{s}^{2}_{ijk}=(1-4\varepsilon^{\dagger})\frac{\operatorname*{\mathrm{Tr}}(\Sigma^{*}_{ijk})}{\operatorname*{\mathrm{Tr}}(\widetilde{\Sigma}^{*}_{ijk})}\leqslant s_{ijk}^{2}\leqslant(1+4\varepsilon^{\dagger})\frac{\operatorname*{\mathrm{Tr}}(\Sigma^{*}_{ijk})}{\operatorname*{\mathrm{Tr}}(\widetilde{\Sigma}^{*}_{ijk})}=(1+4\varepsilon^{\dagger})\widetilde{s}^{2}_{ijk}.$ $$

Hence, we obtain:

$$ $\displaystyle\lVert s_{ijk}\widehat{\mu}_{ijk}-\mu^{*}_{ijk}\rVert$ $\displaystyle\leqslant\lVert\widetilde{s}_{ijk}\widehat{\mu}_{ijk}-\mu^{*}_{ijk}\rVert+\lvert s_{ijk}-\widetilde{s}_{ijk}\rvert\lVert\widehat{\mu}_{ijk}\rVert$ $\displaystyle\leqslant\lVert\widetilde{s}_{ijk}\widetilde{\mu}^{*}_{ijk}-\mu^{*}_{ijk}\rVert+\widetilde{s}_{ijk}\lVert\widetilde{\mu}^{*}_{ijk}-\widehat{\mu}_{ijk}\rVert+4\varepsilon^{\dagger}\widetilde{s}_{ijk}\lVert\widehat{\mu}_{ijk}\rVert$ $\displaystyle\leqslant\lVert\mu^{*}_{ijk}-\mu^{*}_{ijk}\rVert+\widetilde{s}_{ijk}\widetilde{\varepsilon}+4\varepsilon^{\dagger}\widetilde{s}_{ijk}\lVert\widehat{\mu}_{ijk}\rVert$ $\displaystyle\leqslant 0+\widetilde{s}_{ijk}\varepsilon^{\dagger}(1+4\lVert\widehat{\mu}_{ijk}\rVert).{}$ (10) $$

For the final term, we get from the guarantees of [Theorem B.1](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem1) that:

$$ $\operatorname*{\mathrm{Tr}}(\widehat{\Sigma}_{ijk})\geqslant\frac{1}{2}\implies\operatorname*{\mathrm{Tr}}(\widetilde{\Sigma}^{*}_{ijk})\geqslant\frac{1}{4}\implies\widetilde{s}^{2}_{ijk}\leqslant\frac{1200\log(8/\gamma)}{\gamma^{2}}$ $$

and consequently, we get from [Lemmas C.2](https://arxiv.org/html/2510.15839v1#A3.Thmtheorem2) and [C.5](https://arxiv.org/html/2510.15839v1#A3.Thmtheorem5):

$$ $\displaystyle\widetilde{s}_{ijk}\lVert\widehat{\mu}_{ijk}\rVert$ $\displaystyle\leqslant\widetilde{s}_{ijk}(\lVert\widetilde{\mu}^{*}_{ijk}\rVert+\widetilde{\varepsilon})=\lVert\mu_{ijk}^{*}\rVert+\widetilde{s}_{ijk}\widetilde{\varepsilon}\leqslant\frac{160\log(8/\gamma)}{\gamma}+\frac{40\sqrt{\log(8/\gamma)}}{\gamma}\leqslant\frac{200\log(8/\gamma)}{\gamma}.$ $$

Plugging this into [Eq. 10](https://arxiv.org/html/2510.15839v1#A3.Ex242), we get:

$$ $\lVert s_{ijk}\widehat{\mu}_{ijk}-\mu^{*}_{ijk}\rVert\leqslant\frac{1000\log(8/\gamma)}{\gamma}\varepsilon^{\dagger}\eqqcolon\varepsilon^{\ddagger}.$ $$

To conclude the proof of the lemma, let:

$$ $i_{M}\coloneqq\operatorname*{arg\,max}_{i}(\overline{\mu}_{i}-\mu^{*}_{i})\text{ and }i_{m}\coloneqq\operatorname*{arg\,min}_{i}(\overline{\mu}_{i}-\mu^{*}_{i}).$ $$

Note now that:

$$ $\sum_{i=1}^{n}\overline{\mu}_{i}=0=\sum_{i=1}^{n}\mu^{*}_{i}\implies(\overline{\mu}_{i_{M}}-\mu^{*}_{i_{M}})\geqslant 0\text{ and }(\overline{\mu}_{i_{m}}-\mu^{*}_{i_{m}})\leqslant 0.$ $$

Furthermore, there exists $k$ such that $i_{M},i_{m},k\in E^{\prime}$. Therefore, we have by the triangle inequality:

$$ $\displaystyle\lVert\widehat{\mu}_{i_{M},i_{m},k}-\mu^{*}_{i_{M},i_{m},k}\rVert\leqslant 2\varepsilon^{\ddagger}\implies 4\varepsilon^{\ddagger}$ $\displaystyle\geqslant c_{i_{M},i_{m}}^{\top}(\widehat{\mu}_{i_{M},i_{m},k}-\mu^{*}_{i_{M},i_{m},k})$ $\displaystyle=(\overline{\mu}_{i_{M}}-\mu^{*}_{i_{M}})-(\overline{\mu}_{i_{m}}-\mu^{*}_{i_{m}})\geqslant\lVert\overline{\mu}-\mu^{*}\rVert_{\infty}$ $$

where the last inequality follows from the fact that each of the terms in the sum are positive and one of them is equal to $\lVert\overline{\mu}-\mu^{*}\rVert_{\infty}$.
∎

###### Proof of Theorem 5.2 .

The theorem follows from [Lemmas C.4](https://arxiv.org/html/2510.15839v1#A3.Thmtheorem4) and [C.3](https://arxiv.org/html/2510.15839v1#A3.Thmtheorem3) by setting:

$$ $\widetilde{\varepsilon}\coloneqq c\frac{\gamma^{2}\varepsilon}{\log(8/\gamma)\log(n)}\text{ and }\delta^{\prime}=\frac{\delta}{n^{2}}$ $$

and applying [Theorem B.1](https://arxiv.org/html/2510.15839v1#A2.Thmtheorem1) with parameters $\widetilde{\varepsilon}$ and $\delta^{\prime}$ for the elements $i,j,k\in E^{\prime}$ from [Lemma C.1](https://arxiv.org/html/2510.15839v1#A3.Thmtheorem1). A union bound yields the corresponding guarantees on failure probability failure probability.
∎

###### Lemma C.1 .

###### Proof.

###### Lemma C.2 .

###### Proof.

###### Lemma C.3 .

###### Proof.

###### Lemma C.4 .

###### Proof.

###### Lemma C.5 .

###### Proof.

###### Proof of Theorem 5.2 .

## Appendix D Proof of Lower Bound - Theorem 5.3

Here, we provide the proof of [Theorem 5.3](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem3) restated below for convenience which shows that the guarantees of [Theorem 5.2](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem2) are almost tight.

See [5.3](https://arxiv.org/html/2510.15839v1#S5.Thmtheorem3)

###### Proof.

Let $T$ be an estimator with $N_{i^{*},j^{*}}\leqslant\varepsilon^{-2}\log(1/\delta)/4$ for some $i^{*}\neq j^{*}$. We define:

$$ $\displaystyle\Sigma^{1}=\frac{n}{n-1}{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}I{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}$ $\displaystyle\Sigma^{2}=\frac{n}{(n-1)-2(\varepsilon/n)}{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}(I+\varepsilon e_{i^{*}}e_{j^{*}}^{\top}+\varepsilon e_{j^{*}}e_{i^{*}}^{\top}){\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}.$ $$

From the following calculations:

$$ $\displaystyle\operatorname*{\mathrm{Tr}}(\Sigma^{1})$ $\displaystyle=\frac{n}{n-1}\operatorname*{\mathrm{Tr}}{\left({\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}I{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}\right)}=\frac{n}{n-1}\operatorname*{\mathrm{Tr}}{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}=n$ $\displaystyle\operatorname*{\mathrm{Tr}}(\Sigma^{2})$ $\displaystyle=\frac{n}{(n-1)-2(\varepsilon/n)}\operatorname*{\mathrm{Tr}}{\left({\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}(I+\varepsilon e_{i^{*}}e_{j^{*}}^{\top}+\varepsilon e_{j^{*}}e_{i^{*}}^{\top}){\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}\right)}$ $\displaystyle=\frac{n}{(n-1)-2(\varepsilon/n)}\operatorname*{\mathrm{Tr}}{\left((I+\varepsilon e_{i^{*}}e_{j^{*}}^{\top}+\varepsilon e_{j^{*}}e_{i^{*}}^{\top}){\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}\right)}$ $\displaystyle=\frac{n}{(n-1)-2(\varepsilon/n)}{\left(n-1+\varepsilon\operatorname*{\mathrm{Tr}}{\left((e_{i^{*}}e_{j^{*}}^{\top}+e_{j^{*}}e_{i^{*}}^{\top}){\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}\right)}\right)}$ $\displaystyle=\frac{n}{(n-1)-2(\varepsilon/n)}{\left(n-1-\varepsilon\operatorname*{\mathrm{Tr}}{\left((e_{i^{*}}e_{j^{*}}^{\top}+e_{j^{*}}e_{i^{*}}^{\top}){\left(\frac{\bm{1}\bm{1}^{\top}}{n}\right)}\right)}\right)}$ $\displaystyle=\frac{n}{(n-1)-2(\varepsilon/n)}{\left(n-1-2\frac{\varepsilon}{n}\right)}=n,$ $$

we see that $\Sigma^{1}$ and $\Sigma^{2}$ are normalized. Furthermore, we have:

$$ $\displaystyle\lVert\Sigma^{2}-\Sigma^{1}\rVert_{\infty}$ $\displaystyle\geqslant e_{i^{*}}^{\top}(\Sigma^{2}-\Sigma^{1})e_{j^{*}}=e_{i^{*}}^{\top}\Sigma^{2}e_{j^{*}}-\frac{n}{n-1}e_{i^{*}}^{\top}{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}I{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}e_{j^{*}}$ $\displaystyle=e_{i^{*}}^{\top}\Sigma^{2}e_{j^{*}}-\frac{n}{n-1}e_{i^{*}}^{\top}{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}e_{j^{*}}=e_{i^{*}}^{\top}\Sigma^{2}e_{j^{*}}+\frac{1}{n-1}$ $\displaystyle=\frac{n}{(n-1)-2(\varepsilon/n)}e_{i^{*}}^{\top}{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}(I+\varepsilon e_{i^{*}}e_{j^{*}}^{\top}+\varepsilon e_{j^{*}}e_{i^{*}}^{\top}){\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}e_{j^{*}}+\frac{1}{n-1}$ $\displaystyle=\frac{n}{(n-1)-2(\varepsilon/n)}{\left(-\frac{1}{n}+e_{i^{*}}^{\top}{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}(\varepsilon e_{i^{*}}e_{j^{*}}^{\top}+\varepsilon e_{j^{*}}e_{i^{*}}^{\top}){\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}e_{j^{*}}\right)}+\frac{1}{n-1}$ $\displaystyle=\frac{n\varepsilon}{(n-1)-2(\varepsilon/n)}{\left(e_{i^{*}}^{\top}{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}(e_{i^{*}}e_{j^{*}}^{\top}+e_{j^{*}}e_{i^{*}}^{\top}){\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}e_{j^{*}}\right)}-\frac{2\varepsilon/n}{(n-1)((n-1)-2\varepsilon/n)}$ $\displaystyle=\frac{n\varepsilon}{(n-1)-2(\varepsilon/n)}{\left({\left(1-\frac{1}{n}\right)}^{2}+{\left(e_{i^{*}}^{\top}{\left(I-\frac{\bm{1}\bm{1}^{\top}}{n}\right)}e_{j^{*}}\right)}^{2}\right)}-\frac{2\varepsilon/n}{(n-1)((n-1)-2\varepsilon/n)}$ $\displaystyle=\frac{\varepsilon(n^{2}-2n+2)}{n((n-1)-2(\varepsilon/n))}-\frac{2\varepsilon}{n(n-1)((n-1)-2\varepsilon/n)}=\frac{\varepsilon(n(n-1)(n-2)+2(n-1)-2)}{n(n-1)((n-1)-2\varepsilon/n)}$ $\displaystyle\geqslant\frac{\varepsilon n(n-1)(n-2)}{n(n-1)((n-1)-2\varepsilon/n)}\geqslant\frac{\varepsilon(n-2)}{(n-1-2\varepsilon/n)}\geqslant\frac{\varepsilon}{2}.$ $$

We will now compute the KL-divergence between $(T,\mathrm{Choice}(\bm{0},\Sigma^{1}))$ and $(T,\mathrm{Choice}(\bm{0},\Sigma^{2}))$. We have by the definition of $T$:

$$ $\displaystyle\operatorname{KL}((T,\mathrm{Choice}(\bm{0},\Sigma^{1}))\|(T,\mathrm{Choice}(\bm{0},\Sigma^{2})))$ $\displaystyle=\operatorname{KL}{\left(\prod_{ijk}\prod_{l=1}^{N_{ijk}}X^{i,j,k}_{l}\|\prod_{ijk}\prod_{l=1}^{N_{ijk}}Y^{i,j,k}_{l}\right)}$ $$

where

$$ $X^{i,j,k}_{l}\thicksim\mathrm{Choice}((\bm{0},\Sigma^{1}_{ijk}))\text{ and }Y^{i,j,k}_{l}\thicksim\mathrm{Choice}((\bm{0},\Sigma^{2}_{ijk}))$ $$

and from the tensorization of the KL-divergence, we have:

$$ $\displaystyle\operatorname{KL}((T,\mathrm{Choice}(\bm{0},\Sigma^{1}))\|(T,\mathrm{Choice}(\bm{0},\Sigma^{2})))$ $\displaystyle=\sum_{ijk}\operatorname{KL}{\left(\prod_{l=1}^{N_{ijk}}X^{i,j,k}_{l}\|\prod_{l=1}^{N_{ijk}}Y^{i,j,k}_{l}\right)}$ $\displaystyle=\sum_{ijk}N_{ijk}\operatorname{KL}{\left(X^{i,j,k}\|Y^{i,j,k}\right)}.$ $$

We now observe from the definitions of $\Sigma^{1}$ and $\Sigma^{2}$ for all $i,j,k$:

$$ $\displaystyle X^{i,j,k}\thicksim\mathrm{Choice}(\bm{0},I)$ $\displaystyle Y^{i,j,k}\thicksim\mathrm{Choice}(\bm{0},\Sigma^{i,j,k})$ $\displaystyle\text{ where }\Sigma^{i,j,k}=\begin{cases}I&\text{if }\{i^{*},j^{*}\}\not\subset\{i,j,k\}\\ I+\varepsilon(e_{i^{*}}e_{j^{*}}^{\top}+e_{j^{*}}e_{i^{*}}^{\top})&\text{otherwise}\end{cases}$ $$

Since $\Sigma^{i,j,k}=I$ for all $i,j,k$ such that $\{i^{*},j^{*}\}\not\subset\{i,j,k\}$, we get:

$$ $\operatorname{KL}((T,\mathrm{Choice}(\bm{0},\Sigma^{1}))\|(T,\mathrm{Choice}(\bm{0},\Sigma^{2})))=\sum_{\begin{subarray}{c}i,j,k\\ \{i^{*},j^{*}\}\subset\{i,j,k\}\end{subarray}}N_{ijk}\operatorname{KL}{\left(X^{i,j,k}\|Y^{i,j,k}\right)}.$ $$

Now, we have by the data-processing inequality and utilizing the closed form solution for the KL-divergence between two multivariate Gaussians (Pardo, 2006, Exercise 11 in Section 1.6) for $W\thicksim\mathcal{N}(\bm{0},I)$ and $Z\thicksim\mathcal{N}(0,\Sigma^{i,j,k})$:

$$ $\displaystyle\operatorname{KL}{\left(X^{i,j,k}\|Y^{i,j,k}\right)}$ $\displaystyle\leqslant\operatorname{KL}{\left(W\|Z\right)}=\frac{1}{2}{\left(\operatorname*{\mathrm{Tr}}(I\cdot\Sigma^{i,j,k}-I)+\log{\left(\frac{\det(I)}{\det(\Sigma^{i,j,k})}\right)}\right)}$ $\displaystyle=\frac{1}{2}{\left(0+\log{\left(\frac{1}{1-\varepsilon^{2}}\right)}\right)}\leqslant\varepsilon^{2}$ $$

for $\varepsilon\leqslant 1/2$. By substituting this back, we get:

$$ $\displaystyle\operatorname{KL}((T,\mathrm{Choice}(\bm{0},\Sigma^{1}))\|(T,\mathrm{Choice}(\bm{0},\Sigma^{2})))$ $\displaystyle\leqslant\sum_{\begin{subarray}{c}i,j,k\\ \{i^{*},j^{*}\}\subset\{i,j,k\}\end{subarray}}N_{ijk}\operatorname{KL}{\left(X^{i,j,k}\|Y^{i,j,k}\right)}$ $\displaystyle\leqslant\sum_{\begin{subarray}{c}i,j,k\\ \{i^{*},j^{*}\}\subset\{i,j,k\}\end{subarray}}N_{ijk}\varepsilon^{2}=N_{i^{*},j^{*}}\varepsilon^{2}.$ $$

We now get as a consequence of the Bretagnolle–Huber inequality ([Lemma E.2](https://arxiv.org/html/2510.15839v1#A5.Thmtheorem2)):

$$ $\operatorname{TV}((T,\mathrm{Choice}(\bm{0},\Sigma^{1})),(T,\mathrm{Choice}(\bm{0},\Sigma^{2})))\leqslant 1-\frac{1}{2}\exp{\left\{-N_{i^{*},j^{*}}\varepsilon^{2}\right\}}\leqslant 1-\frac{1}{2}\sqrt{\delta}\leqslant 1-2\delta.$ $$

We now have by the minimax characterization of the Bayes risk:

$$ $\max_{\Sigma\in\{\Sigma^{1},\Sigma^{2}\}}\mathbb{P}_{\bm{X}\thicksim(T,\mathrm{Choice}(\bm{0},\Sigma))}{\left\{\lVert T(\bm{X})-\Sigma\rVert_{\infty}\geqslant\frac{\varepsilon}{4}\right\}}\geqslant\frac{1}{2}{\left(1-(1-2\delta)\right)}=\delta$ $$

by an application of Le Cam’s method ((Wainwright, 2019, Section 15.2)), concluding the proof.
∎

###### Proof.

## Appendix E Miscellaneous Technical Results

Here, we include technical results used in the proofs of our theorems. We start with Hoeffding’s inequality.

###### Theorem E.1 .

Boucheron et al. (2013)
Let $X_{1},\dots,X_{n}$ be independent random variables such that $X_{i}$ takes values in $[a_{1},b_{i}]$ almost surely for all $i\leqslant n$. Let

$$ $S=\sum_{i=1}^{n}(X_{i}-\mathbb{E}[X_{i}]).$ $$

Then for every $t\geqslant 0$:

$$ $\mathbb{P}{\left\{S\geqslant t\right\}}\leqslant\exp{\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right)}.$ $$

We will make use of the following inequality which will be crucial in obtaining the high-probability lower bounds in the respective statements:

###### Lemma E.2 ( Bretagnolle and Huber ( 1979 ); Tsybakov ( 2009 ); Canonne ( 2023 ) ) .

We have for any two distributions, $P$ and $Q$:

$$ $\operatorname{TV}(P,Q)\leqslant 1-\frac{1}{2}\exp(-\operatorname{KL}(P\|Q)).$ $$

###### Theorem E.1 .

###### Lemma E.2 ( Bretagnolle and Huber ( 1979 ); Tsybakov ( 2009 ); Canonne ( 2023 ) ) .

### E.1 Proof of Lemma 4.3

See [4.3](https://arxiv.org/html/2510.15839v1#S4.Thmtheorem3)

###### Proof.

Without loss of generality, due to the invariance of an isotropic Gaussian to to rotations and reflections, we may assume $d_{1}\geqslant d_{2}$, $v_{1}=e_{2}$, and $(v_{2})_{1}\geqslant 0$. Since $v_{2}$ is a unit vector, it may be parameterized as $v_{2}=v(\theta^{*})$ for $\theta^{*}\in[0,\pi]$ with $v(\theta)$ defined as follows:

$$ $v(\theta)\coloneqq\begin{bmatrix}\sin(\theta)\\ -\cos(\theta)\end{bmatrix}\text{ for }\theta\in[0,\pi].$ $$

Now, $\xi(\theta)$ satisfying the first two constraints imposed by $d_{1},d_{2}$ for the vectors $v_{1}$ and $v(\theta)$ is given by the following expression:

$$ $\xi(\theta)\coloneqq\begin{bmatrix}\widetilde{\xi}(\theta)\\ d_{1}\end{bmatrix}\text{ where }\widetilde{\xi}(\theta)\coloneqq\frac{d_{1}\cos(\theta)+d_{2}}{\sin(\theta)}.$ $$

###### Claim E.3 .

We have for $\theta\in(0,\pi)$:

$$ $\widetilde{\xi}^{\prime}(\theta)<0.$ $$

###### Proof.

Observe from the chain rule that:

$$ ${\widetilde{\xi}}^{\prime}(\theta)=\frac{-\cos(\theta)(d_{1}\cos(\theta)+d_{2})}{\sin^{2}\theta}-d_{1}=\frac{-d_{1}-d_{2}\cos(\theta)}{\sin^{2}(\theta)}<0$ $$

for $\theta\in(0,\pi)$ concluding the proof of the claim.
∎

Continuing with the proof, define:

$$ $\gamma(\theta)\coloneqq\mathbb{P}{\left\{\langle X,v_{1}\rangle,\langle X,v(\theta)\rangle\leqslant 0\right\}}\text{ for }X\thicksim\mathcal{N}(\widetilde{\xi}(\theta),I).$ $$

Our next claim shows that $\gamma(\theta)$ is also monotonic in $\theta$.

###### Claim E.4 .

We have for $\theta\in(0,\pi)$:

$$ $\gamma^{\prime}(\theta)>0.$ $$

###### Proof.

First, observe the following:

$$ $\displaystyle\{x:\langle v_{1},x\rangle,\langle v(\theta),x\rangle\leqslant 0\}\coloneqq{\left\{(r\cos(\alpha),r\sin(\alpha)):r\geqslant 0,\alpha\in(\pi,\pi+\theta)\right\}}$ $\displaystyle\{x:\langle v_{1},x\rangle,\langle v(\theta),x\rangle\leqslant 0\}\coloneqq{\left\{(x,y):y\leqslant 0,x\leqslant y\cot(\theta)\right\}}$ $$

As a consequence, we get by switching to polar coordinates:

$$ $\gamma(\theta)=\int_{0}^{\infty}\int_{\pi}^{\pi+\theta}\frac{1}{2\pi}\exp{\left\{-\frac{(r\cos(\alpha)-\widetilde{\xi}(\theta))^{2}+(r\sin(\alpha)-d_{1})^{2}}{2}\right\}}d\alpha rdr.$ $$

Hence, we get by the Leibniz integral rule:

$$ $\displaystyle\gamma^{\prime}(\theta)$ $\displaystyle=\int_{0}^{\infty}\frac{d}{d\theta}{\left(\int_{\pi}^{\pi+\theta}\frac{1}{2\pi}\exp{\left\{-\frac{(r\cos(\alpha)-\widetilde{\xi}(\theta))^{2}+(r\sin(\alpha)-d_{1})^{2}}{2}\right\}}d\alpha\right)}rdr$ $\displaystyle=\int_{0}^{\infty}\frac{1}{2\pi}\exp{\left\{-\frac{(r\cos(\theta)+\widetilde{\xi}(\theta))^{2}+(r\sin(\theta)+d_{1})^{2}}{2}\right\}}rdr\ +$ $\displaystyle\quad\int_{0}^{\infty}\int_{\pi}^{\pi+\theta}\frac{\partial}{\partial\theta}{\left(\frac{1}{2\pi}\exp{\left\{-\frac{(r\cos(\alpha)-\widetilde{\xi}(\theta))^{2}+(r\sin(\alpha)-d_{1})^{2}}{2}\right\}}\right)}d\alpha rdr$ $\displaystyle=\int_{0}^{\infty}\frac{1}{2\pi}\exp{\left\{-\frac{(r\cos(\theta)+\widetilde{\xi}(\theta))^{2}+(r\sin(\theta)+d_{1})^{2}}{2}\right\}}rdr\ +$ $\displaystyle\quad\int_{0}^{\infty}\int_{\pi}^{\pi+\theta}\frac{1}{2\pi}\exp{\left\{-\frac{(r\cos(\alpha)-\widetilde{\xi}(\theta))^{2}+(r\sin(\alpha)-d_{1})^{2}}{2}\right\}}(r\cos(\alpha)-\widetilde{\xi}(\theta))\widetilde{\xi}^{\prime}(\theta)d\alpha rdr$ $\displaystyle=\int_{0}^{\infty}\frac{1}{2\pi}\exp{\left\{-\frac{(r\cos(\theta)+\widetilde{\xi}(\theta))^{2}+(r\sin(\theta)+d_{1})^{2}}{2}\right\}}rdr\ +$ $\displaystyle\quad\widetilde{\xi}^{\prime}(\theta)\int_{0}^{\infty}\int_{\pi}^{\pi+\theta}\frac{1}{2\pi}\exp{\left\{-\frac{(r\cos(\alpha)-\widetilde{\xi}(\theta))^{2}+(r\sin(\alpha)-d_{1})^{2}}{2}\right\}}(r\cos(\alpha)-\widetilde{\xi}(\theta))d\alpha rdr.$ $$

For the second term, we have:

$$ $\displaystyle\int_{0}^{\infty}\int_{\pi}^{\pi+\theta}\frac{1}{2\pi}\exp{\left\{-\frac{(r\cos(\alpha)-\widetilde{\xi}(\theta))^{2}+(r\sin(\alpha)-d_{1})^{2}}{2}\right\}}(r\cos(\alpha)-\widetilde{\xi}(\theta))d\alpha rdr$ $\displaystyle\quad=\int_{-\infty}^{0}\int_{-\infty}^{y\cot(\theta)}\frac{1}{2\pi}\exp{\left\{-\frac{(x-\widetilde{\xi}(\theta))^{2}+(y-d_{1})^{2}}{2}\right\}}(x-\widetilde{\xi}(\theta))dxdy$ $\displaystyle\quad=\int_{-\infty}^{0}\int_{\infty}^{(y\cot(\theta)-\widetilde{\xi}(\theta))^{2}/2}\frac{1}{2\pi}\exp{\left\{-t+\frac{(y-d_{1})^{2}}{2}\right\}}dtdy$ $\displaystyle\quad=\frac{1}{2\pi}\int_{-\infty}^{0}\exp{\left\{-\frac{(y-d_{1})^{2}}{2}\right\}}\cdot(-\exp(-t))\Biggr|_{\infty}^{(y\cot(\theta)-\widetilde{\xi}(\theta))^{2}/2}dy$ $\displaystyle\quad=\frac{-1}{2\pi}\int_{-\infty}^{0}\exp{\left\{-\frac{(y-d_{1})^{2}}{2}\right\}}\exp{\left\{-\frac{(y\cot(\theta)-\widetilde{\xi}(\theta))^{2}}{2}\right\}}dy.$ $$

Noting that the above integral is negative, the previous two displays and [Claim E.3](https://arxiv.org/html/2510.15839v1#A5.Thmtheorem3) now yield:

$$ $\gamma^{\prime}(\theta)>0\text{ for }\theta\in(0,\pi)$ $$

concluding the proof of the claim.
∎

From, [Claim E.4](https://arxiv.org/html/2510.15839v1#A5.Thmtheorem4), we get that there exists a unique solution $\theta^{*}$ such that $\gamma(\theta^{*})=\gamma$. Observing that $\langle v_{1},v_{2}\rangle=-\cos(\theta^{*})$ establishes the lemma.
∎

###### Proof.

###### Claim E.3 .

###### Proof.

###### Claim E.4 .

###### Proof.

### E.2 Proof of Theorem 3.2

Here, we present the proof of [Theorem 3.2](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem2), stated below for convenience.
See [3.2](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem2)

###### Proof.

We will establish the result for a mildly different normalization of the parameters, $(\mu,\Sigma)$. Formally, we will assume that:

$$ $\mu_{1}=0,\quad\Sigma_{1,1}=0,\quad\operatorname*{\mathrm{Tr}}(\Sigma)=n-1$ (DIFF-FORM) $$

We will establish the equivalence between [DIFF-FORM](https://arxiv.org/html/2510.15839v1#A5.Ex308) and [Assumption 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1) subsequently. [DIFF-FORM](https://arxiv.org/html/2510.15839v1#A5.Ex308) is motivated by the observation that for any $X\thicksim\mathcal{N}(\mu,\Sigma)$, $X^{\prime}$ generated by the following transformation:

$$ $\forall i\in[n]:X^{\prime}_{i}=t(X_{i}-X_{1})$ $$

for any $t>0$ induces the same set of rankings. This results in deterministically fixing the utility of the first item to 0 resulting in the first two constraints and the third is chosen for normalization. As before, we assume that the rank of $\Sigma$ is $n-1$.

Now, consider any $(\mu,\Sigma)$ satisfying [DIFF-FORM](https://arxiv.org/html/2510.15839v1#A5.Ex308). Let $X\thicksim\mathcal{N}(\mu,\Sigma)$. First, observe that:

$$ $X_{i}-X_{j}\thicksim\mathcal{N}(\underbrace{\mu_{i}-\mu_{j}}_{\mu_{ij}},\underbrace{\Sigma_{i,i}+\Sigma_{j,j}-2\Sigma_{i,j}}_{\sigma^{2}_{ij}}).$ (DIFF-PROB) $$

Note that since $\Sigma$ has rank $n-1$ (and satisfies $\Sigma e_{1}=0$), $\sigma_{ij}>0$. We will now establish our results in two different cases:

###### Proof.

#### Case 1:

$\exists i,j>1:\mu_{i}=\mu_{j}$. In this case, observe that since $\Sigma$ is of rank $n-1$, defining:

$$ $E=e_{i}e_{j}^{\top}+e_{j}e_{i}^{\top}$ $$

we have for some $\nu>0$:

$$ $\forall\delta\in[0,\nu]:\Sigma+\delta E\text{ satisfies \ref{eq:diff_form} and has rank }n-1.$ $$

Note, furthermore that for any $X^{\prime}\thicksim\mathcal{N}(\mu,\Sigma+\delta E)$:

$$ $\displaystyle\forall k,l\in[n],k\neq l,\{k,l\}\neq\{i,j\}:\operatorname*{\mathbb{P}}{\left\{X_{k}>X_{l}\right\}}=\operatorname*{\mathbb{P}}{\left\{X^{\prime}_{k}>X^{\prime}_{l}\right\}}$ $\displaystyle\operatorname*{\mathbb{P}}{\left\{X_{i}>X_{j}\right\}}=\frac{1}{2}=\operatorname*{\mathbb{P}}{\left\{X^{\prime}_{i}>X^{\prime}_{j}\right\}}.$ $$

Hence,

$$ $\mathcal{S}^{\prime}={\left\{(\mu,\Sigma+\delta E):\delta\in[0,\nu]\right\}}$ $$

consists of an infinite set of solutions with the same pairwise rankings.

#### Case 2:

$\exists i>1:\mu_{i}=0$. For this case, consider the matrix $\widetilde{\Sigma}$:

$$ $\widetilde{\Sigma}_{kl}=\begin{cases}\Sigma_{ii}+\nu&\text{if }k=l=i\\ \Sigma_{il}-\frac{\nu}{2}&\text{if }k=i\text{ and }1<l\neq i\\ \Sigma_{ki}-\frac{\nu}{2}&\text{if }l=i\text{ and }1<k\neq i\\ \Sigma_{kl}&\text{otherwise}\end{cases}.$ $$

Note that for small enough $\nu$, $\widetilde{\Sigma}$ remains positive-semidefinite with rank $n-1$. Furthermore, $X\thicksim\mathcal{N}(\mu,\Sigma)$ and $X\thicksim\mathcal{N}(\mu,\widetilde{\Sigma})$ induce the same distribution over pairwise rankings of the $n$ alternatives. Finally, observe that $(\mu,\widetilde{\Sigma})$ satisfy the conditions of [DIFF-FORM](https://arxiv.org/html/2510.15839v1#A5.Ex308) except for $\operatorname*{\mathrm{Tr}}(\widetilde{\Sigma})=n+\nu$. To restore this, we simply rescale the $(\mu,\widetilde{\Sigma})$ to obtain:

$$ $t=\frac{n+\nu}{n},\quad\mu^{\prime}=\frac{\mu}{\sqrt{t}},\quad\Sigma^{\prime}=\frac{\Sigma}{t}.$ $$

Now, $(\mu^{\prime},\Sigma^{\prime})$ induce the same distribution over pairwise preferences $(\mu,\Sigma)$. Furthermore, $(\mu^{\prime},\Sigma^{\prime})$ is distinct from $(\mu,\Sigma)$ – $\mu\neq\mu^{\prime}$ and $\Sigma\neq\Sigma^{\prime}$. Since $(\mu^{\prime},\Sigma^{\prime})$ may be constructed for all small enough $\nu$, there exist infinitely many solutions satisfying [DIFF-FORM](https://arxiv.org/html/2510.15839v1#A5.Ex308) with the same distribution over pairwise rankings.

#### Case 3:

$\forall i,j\in[n]:\mu_{i}\neq\mu_{j}$. In this setting, we start by modifying the parameter $\mu$ as follows:

$$ $u\neq 0,\lVert u\rVert\leqslant 1,u_{1}=u_{n}=0:\widetilde{\mu}=\mu+\nu^{\prime}u$ $$

for some $\nu^{\prime}$ to be chosen subsequently. We will now construct an alternative solution from $\widetilde{\mu}$ by setting $\widetilde{\mu}_{n}$ and the entries of $\widetilde{\Sigma}$, the corresponding covariance matrix accordingly. Note from [DIFF-PROB](https://arxiv.org/html/2510.15839v1#A5.Ex310), to ensure that the pairwise ranking probabilities do not change, we must :

$$ $\forall i\in[2,n-1]:\widetilde{\Sigma}_{ii}={\left(\frac{\widetilde{\mu}_{i}}{\mu_{i}}\right)}^{2}\Sigma_{ii}$ $$

Next, we will set:

$$ $\widetilde{\Sigma}_{nn}=n-\sum_{i=2}^{n-1}\widetilde{\Sigma}_{ii}\text{ and }\widetilde{\mu}_{n}=\sqrt{\frac{\widetilde{\Sigma}_{nn}}{\Sigma_{nn}}}\mu_{n}.$ $$

Note that the above settings result in the correct pairwise probabilities as long as $\nu^{\prime}$ is chosen small enough. From [DIFF-PROB](https://arxiv.org/html/2510.15839v1#A5.Ex310), this setting preserves the pairwise ranking probabilities between the first alternative and all other alternatives in the list. To ensure the correct pairwise ranking probabilities between other pairs, $i,j$, with $i\neq j$ and $i,j\neq 1$, we will set the values of $\Sigma_{ij}$ accordingly. To do this, observe from [DIFF-PROB](https://arxiv.org/html/2510.15839v1#A5.Ex310), it suffices to set $\Sigma_{ij}$ such that:

$$ $\frac{\mu_{i}-\mu_{j}}{\sqrt{\Sigma_{ii}+\Sigma_{jj}-2\Sigma_{ij}}}=\frac{\widetilde{\mu}_{i}-\widetilde{\mu}_{j}}{\sqrt{\widetilde{\Sigma}_{ii}+\widetilde{\Sigma}_{jj}-2\widetilde{\Sigma}_{ij}}}.$ $$

We now prove that $(\widetilde{\mu},\widetilde{\Sigma})$ is a valid solution satisfying [DIFF-FORM](https://arxiv.org/html/2510.15839v1#A5.Ex308). The first three constraints are satisfied by construction. Furthermore, $(\widetilde{\mu},\widetilde{\Sigma})$ achieve the same pairwise observation probabilities by [DIFF-PROB](https://arxiv.org/html/2510.15839v1#A5.Ex310). The only remaining constraint is to prove that $\widetilde{\Sigma}$ is positive semidefinite and has rank $n-1$. To do this, note that $\sigma_{ij}>0$ for all $i\neq j$, $\Sigma_{ii}>0$ for all $i\in[n]$, $\mu_{i}\neq\mu_{j}$, and consequently, we have that:

$$ $\widetilde{\Sigma}=\Sigma+\nu E$ $$

where $E$ is symmetric, satisfies $E_{1i}=0$ for all $i\in[n]$, and $\lVert E\rVert\leqslant 1$. Furthermore, $\nu$ may be made arbitrarily small by an appropriate choice of $\nu^{\prime}$. Since the sub matrix corresponding to the last $n-1$ rows and columns of $\Sigma$ is full rank and positive definite, the corresponding matrix of $\widetilde{\Sigma}$ is also full rank and positive definite by making $\nu$ correspondingly small. Hence, $\widetilde{\Sigma}$ is itself of rank $n-1$ and positive semidefinite. Since such a solution may be constructed for arbitrary choices of $u$, this concludes the proof in this case as well.

The theorem under [Assumption 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1) is now a consequence of the following claim.

###### Claim E.5 .

Let

$$ $\displaystyle\mathcal{V}={\left\{(\mu,\Sigma):(\mu,\Sigma)\text{ satisfy \lx@cref{creftype~refnum}{def:universal_symmetries}}\right\}}$ $\displaystyle\mathcal{U}={\left\{(\mu,\Sigma):(\mu,\Sigma)\text{ satisfy \ref{eq:diff_form}}\right\}}.$ $$

Then, there exists an invertible mapping $f:\mathcal{U}\to\mathcal{V}$, such that for any $(\mu,\Sigma)\in\mathcal{U}$, $f(\mu,\Sigma)$ induces the same distribution over the rankings of the $n$ alternatives.

###### Proof.

Letting:

$$ $M_{U}\coloneqq I-\frac{\bm{1}\bm{1}^{\top}}{n}\text{ and }M_{V}\coloneqq I-\bm{1}e_{1}^{\top},$ $$

we will show that:

$$ $f(\mu,\Sigma)=\frac{M_{U}\mu}{\sqrt{t}},\frac{M_{U}\Sigma M_{U}}{t}\text{ where }t=\frac{\operatorname*{\mathrm{Tr}}(M_{U}\Sigma M_{U})}{n}$ (MAP) $$

is the required transformation. First, observe:

$$ $\displaystyle M_{V}M_{U}=I-\bm{1}e_{i}^{\top}-\frac{\bm{1}\bm{1}^{\top}}{n}+\frac{\bm{1}\bm{1}^{\top}}{n}=I-\bm{1}e_{i}^{\top}$ $\displaystyle M_{U}M_{V}=I-\frac{\bm{1}\bm{1}^{\top}}{n}-\bm{1}e_{1}^{\top}+\bm{1}e_{i}^{\top}=I-\bm{1}\bm{1}^{\top}.$ $$

Consequently, we have:

$$ $\displaystyle\forall\mu,\Sigma\in\mathcal{U}:M_{V}M_{U}\Sigma M_{U}^{\top}M_{V}^{\top}=\Sigma$ $\displaystyle\forall\mu,\Sigma\in\mathcal{V}:M_{U}M_{V}\Sigma M_{V}^{\top}M_{U}^{\top}=\Sigma.$ $$

Hence, $t>0$ in [MAP](https://arxiv.org/html/2510.15839v1#A5.Ex326) and the mapping $f$ is well defined. Next, observe that for any $X\thicksim\mathcal{N}(\mu,\Sigma)$, $M_{U}X$ has distribution $\mathcal{N}(M_{U}\mu,M_{U}\Sigma M_{U})$ and induces the same distribution over rankings. Therefore, $f(\mu,\Sigma)$ induces the same distribution over rankings as $(\mu,\Sigma)$. Finally, to show that $f$ is invertible, define $g:\mathcal{V}\to\mathcal{U}$:

$$ $g(\mu,\Sigma)=\frac{M_{V}\mu}{\sqrt{t}},\frac{M_{V}\Sigma M_{V}^{\top}}{t}\text{ where }t=\frac{\operatorname*{\mathrm{Tr}}(M_{V}\Sigma M_{V}^{\top})}{n}.$ (INV-MAP) $$

Note that $g$ is well defined as $t>0$ due to the definition of $M_{U}M_{V}$ and its operation on $(\mu,\Sigma)\in\mathcal{V}$. Similarly, $g(\mu,\Sigma)$ induces the same distribution over rankings as $(\mu,\Sigma)$. Finally, we have:

$$ $\displaystyle g\circ f(\mu,\Sigma)$ $\displaystyle\quad=\frac{M_{V}M_{U}\mu}{\sqrt{t_{1}t_{2}}},\frac{M_{V}M_{U}\Sigma M_{U}^{\top}M_{V}}{t_{1}t_{2}}\qquad{\left(t_{1}=\frac{\operatorname*{\mathrm{Tr}}(M_{U}\Sigma M_{U})}{n},\ t_{2}=\frac{\operatorname*{\mathrm{Tr}}(M_{V}M_{U}\Sigma M_{U}^{\top}M_{V}^{\top})}{nt_{1}}\right)}$ $\displaystyle\quad=\frac{M_{V}M_{U}\mu}{\sqrt{\operatorname*{\mathrm{Tr}}(M_{V}M_{U}\Sigma M_{U}^{\top}M_{V}^{\top})/n}},\frac{M_{V}M_{U}\Sigma M_{U}^{\top}M_{V}}{\operatorname*{\mathrm{Tr}}(M_{V}M_{U}\Sigma M_{U}^{\top}M_{V}^{\top})/n}$ $\displaystyle\quad=\frac{M_{V}M_{U}\mu}{\sqrt{\operatorname*{\mathrm{Tr}}(\Sigma)/(n)}},\frac{\Sigma}{\operatorname*{\mathrm{Tr}}(\Sigma)/(n)}=\mu,\Sigma$ $$

where the third and fourth inequality follow from the fact that $(\mu,\Sigma)\in\mathcal{U}$.
∎

[Claim E.5](https://arxiv.org/html/2510.15839v1#A5.Thmtheorem5) establishes that there exists a one-to-one mapping between pairs $(\mu,\Sigma)$ satisfying [Assumption 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1) and [DIFF-FORM](https://arxiv.org/html/2510.15839v1#A5.Ex308) which induce the same distribution over rankings. Hence, identifiability under one parameterization implies identifiability under the other. Therefore, the existence of infinitely many solutions satisfying [DIFF-FORM](https://arxiv.org/html/2510.15839v1#A5.Ex308) with the same pairwise ranking probabilities as any $(\mu,\Sigma)\in\mathcal{U}$ satisfying implies the existencec of infinitely many solutions satisfying [Assumption 3.1](https://arxiv.org/html/2510.15839v1#S3.Thmtheorem1) with the same pairwise ranking probabilities as any particlar $(\mu,\Sigma)\in\mathcal{V}$ concluding the proof of the theorem.
∎

###### Claim E.5 .

###### Proof.

## Appendix F Implementation details

Figure: Figure 4: Larger version of the first row of Figure [2](https://arxiv.org/html/2510.15839v1#S5.F2). Top to bottom rows: pairwise, ground truth, best-of-three.
Refer to caption: x13.png

Figure: Figure 5: Larger version of the second row of Figure [2](https://arxiv.org/html/2510.15839v1#S5.F2). Top to bottom rows: pairwise, ground truth, best-of-three.
Refer to caption: x18.png

Figure: Figure 6: Two probit models where $\mathbb{P}(Y>X)=0.5$ (two leftmost) and $\mathbb{P}(Y>X)=0.75$ (two rightmost).
Refer to caption: x23.png

Figure: Figure 7: A probit model learned from best-of-three observation from sushi-a
Refer to caption: x27.png

Figure [6](https://arxiv.org/html/2510.15839v1#A6.F6) shows multiple Gaussian distributions with the same pairwise probabilities.

Table: Table 4: Left to right, movies with the lowest and highest correlations in a probit learned from the Netflix dataset.

Table: Table 5: Left to right, movies with the lowest and highest correlations in a probit learned from the MovieLens dataset.

We split the users into a train and validation sets (90% train, 10%validation) for testing. For the Netflix and MovieLens datasets, we only take movies with more than $n$ ratings, e.g., $n=10^{4}$ for nf-10k. For datasets where we convert ratings to rankings, we assume that alternatives with the same rankings can be shuffled in the ranking. To sample the six alternatives, we first sample a user with probability proportional to the number of choices made, then we sample the choices uniformly, lastly, we sort the choices according to the ratings and query format. For the LLM experiments, we use “the movie database” (TMBD) to generate the input, the correctness of the TMBD ID, including mapping correctly to TV show or movie, was manually verified for both datasets. We omit alternatives that do not have clear entries in TMBD. Examples of such movies are double features like “The Fly (1986) / The Fly II (1989) double feature” were omitted.. We use a linear network for all experiments. For the probit experiments, we output the Cholesky decomposition of the covariance matrix. We use the Adam optimizer (Kingma, 2014) with a learning rate of 3e-4 for RUM and 0.01 otherwise. For the matrix factorization model we learn 128 embedding for users and alternatives with a per user and per alternative bias. We do 9000 gradient steps with a batch size of 1024 on RUMs and 1000 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 comparisons, we project the problem in 2D using the $P$ matrix introduced in the main body of the text to both speed up the calculation, which is done via numerical integration over a coarse grid, and remove the symmetries present in the loss landscape. To calculate conditioned outcome probability, we use rejection sampling to measure the high-dimensional integrals instead of methods like Gessner et al. (2020).

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 4
presentation: 3
questions: One question that I am interested in thinking about (and getting the authors to weigh in on) is what does this imply for policy learning in RLHF setups -- in particular, I am thinking about situations involving intransitive preferences.
soundness: 3
strengths: 1. A very clearly written paper, a concrete model / setup and clear theoretical results.
2. Interesting observations, and a particularly relevant problem in the current scheme of RLHF based pipelines for training foundation models.
summary: This paper considers a correlated probit model of preferences that avoids the Independence of Irrelevant alternatives (IIA) assumption; for this model, the paper shows that pairwise preference data isn't sufficient for provably learning the correlations, and suggests the use of three way preference data to provably solve for the parameters of this model.
weaknesses: 1. In principle, this is a fairly stylized model and its applicability to realistic setups, particularly in RLHF is questionable in the sense of how useful it can be compared to optimizing the standard pairwise loss.
2. This specific connection to training improved reward models (in RLHF) is not explored as part of the empirical evaluations which could've helped bolster the results offered by this paper.

---

confidence: 3
contribution: 4
initial_rating: 6
presentation: 3
questions: - How strong is Assumption 3.1? Could the authors elaborate on its necessity and implications?
soundness: 3
strengths: I think that the contribution of this paper is significant, particularly Theorem 3.2, which rigorously proves that the classical pairwise comparison paradigm is fundamentally insufficient for recovering the parameters of a correlated probit model.
This finding challenges long-standing assumptions in choice modeling and clearly explains why existing methods fail to capture correlations in human preferences.
Moreover, the paper provides both theoretical and practical advances by establishing the first identifiability and finite-sample guarantees for correlated Random Utility Models.
Overall, the work offers a novel perspective on preference learning to the community.
summary: This paper studies RUMs and explores the statistical and computational challenges of learning a correlated probit model that avoids the IIA assumption.
The authors first prove that pairwise preference data is fundamentally insufficient to capture correlation among utilities.
They then show that best-of-three preference data is both identifiable and sufficient, and propose a statistically and computationally efficient estimator that achieves near-optimal performance.
weaknesses: Despite its strong theoretical contributions, the paper also has a few weaknesses and open questions.

- In Theorem 5.2, the sample complexity depends on $\gamma^{-24}$. Since $\gamma$ can be extremely small in practical settings, this dependence may lead to an unrealistic sample requirement. It would be important to discuss whether this exponent can be tightened or whether a refined analysis could yield a more favorable dependence on $\gamma$.

- While the paper motivates its setting through RLHF, it treats each item as a single (prompt, response) pair. In RLHF, however, the prompt space is effectively infinite and highly structured. It remains unclear how the proposed framework could be extended to handle such a large or continuous prompt and action space. 

- I think this work is also highly related to general preference modeling frameworks, such as [1] and [2].
Could the authors compare their proposed framework with these prior approaches and clarify the key similarities and differences?

---
[1] Ye, Chenlu, et al. "Online iterative reinforcement learning from human feedback with general preference model." NeurIPS, 2024.
[2] Zhang, Yuheng, et al. "Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning.", ICLR 2025.

---

confidence: 3
contribution: 3
initial_rating: 4
presentation: 3
questions: When does the best-of-three-probit model outperform the direct matrix completion method?
soundness: 3
strengths: This paper explores an interesting question and provides substantive theoretical analysis to support their conclusion: pairwise comparisons are not sufficient to recover the parameters of a correlated choice model, but best-of-three comparisons are. This conclusion is interesting and, to the best of my knowledge, addresses an important gap in existing literature.
summary: This paper focusses on learning correlated utility models—parameterized as a correlated probit model——to avoid the IIA assumptions required by RUMs. The paper first proves that pairwise comparison data is insufficient to identify the data generating model. The paper then proves that best-of-three observations are both sufficient and necessary to learn the data generating probit model, and provides finite sample guarantees. Finally, the paper presents a series of experiments evaluating the use of best-of-three observations to learn the parameters of a probit model for 3 real-world datasets and 1 synthetic dataset.
weaknesses: My main concerns are with the experiments in Section 6. Across all datasets, the proposed best-of-three-probit model matches or underperforms the direct matrix completion method. The authors claim that the direct matrix completion method is unrealistic in some scenarios—particularly when the set of alternatives and users is large—-but do not evaluate their method on those scenarios. Therefore, as far as I can tell, how their method also performs with larger alternatives/user sets remains an open question. Given the experimental evidence the authors do provide, there is no clear empirical benefit to using the best-of-three-probit model. I will raise my score if the authors can provide empirical evidence indicating where their best-of-three-probit model outperforms all other baselines. 

Also, regarding Figure 3: the authors call this a “welfare maximizing experiment” but then note that the quantity they evaluate by “does not directly correlate with welfare as welfare is sensitive to the magnitude of utility change whereas this plot is not”. The authors should therefore change the name and how they discuss this experiment to avoid confusion.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: N/A
soundness: 3
strengths: 1. The paper is clearly written and logically organized, presenting formal identifiability theorems that rigorously establish the necessity and sufficiency of triplet comparisons for learning correlated probit models.

2. The paper delivers a persuasive critique of the Independence of Irrelevant Alternatives (IIA) assumption commonly used in RLHF, and introduces a well-justified alternative that enables more nuanced and personalized preference modeling.

3. The experimental results, though modest in some cases, effectively demonstrate the advantages of triplet-based modeling on real-world datasets (e.g., Netflix, MovieLens, Sushi).
summary: The paper demonstrates that pairwise preference data is insufficient to learn correlated utility models in Random Utility Models (RUMs), specifically the correlated probit model. It proves that best-of-three comparisons are both necessary and sufficient for identifiability, proposes a near-optimal estimator, and empirically validates its advantages over traditional models in capturing human preference correlations.
weaknesses: While I am not a domain expert, I would like to offer a few comments based on my understanding of the paper. One notable limitation is the absence of experiments conducted in an actual RLHF setting (whether in reinforcement learning tasks or fine-tuning large language models). Although the theoretical and empirical results (i.e., the correlations) on general preference datasets are compelling, they may not fully demonstrate the practical value of the proposed approach. Without experiments in the RLHF context, it remains unclear how well the method performs in the scenarios it is ultimately intended to support.


Decision: Accept (Poster)