Tight Bounds for Learning RUMs from Small Slates
Authors: Flavio Chierichetti
Mirko Giacchini
Ravi Kumar
Alessandro Panconesi
Andrew Tomkins
Venue: NeurIPS 2024 poster (2024)
Keywords: discrete choice
random utility model
approximation theory
Primary area: learning_theory

Abstract: A Random Utility Model (RUM) is a classical model of user behavior defined by a distribution over $\mathbb{R}^n$. A user, presented with a subset of $\\{1,\ldots,n\\}$, will select the item of the subset with the highest utility, according to a utility vector drawn from the specified distribution. In practical settings, the subset is often of small size, as in the ``ten blue links'' of web search. 


In this paper, we consider a learning setting with complete information on user choices from subsets of size at most $k$. We show that $k=\Theta(\sqrt{n})$ is both necessary and sufficient to predict the distribution of all user choices with an arbitrarily small, constant error.


Based on the upper bound, we obtain new algorithms for approximate RUM learning and variations thereof. Furthermore, we employ our lower bound for approximate RUM learning to derive lower bounds to fractional extensions of the well-studied $k$-deck and trace reconstruction problems.

Tight Bounds for Learning RUMs from Small Slates
Flavio Chierichetti Sapienza University Rome flavio@di. uniromal it
Mirko Giacchini
Sapienza University Rome stacchini@di uniromal it
Ravi Kumar
Alessandro Panconesi Sapienza University Rome ale@di. uniromal, it
Andrew Tomkins Google, Mountain View atomkins@gmail. com
Google, Mountain View ravi. k530gmai1l com
Abstract
A Random Utility Model (RUM) a classical model of user behavior defined by a distribution over R". A user, presented with subset of {1...., n), will select the item of the subset with the highest utility, according to a utility vector drawn from the specified distribution. In practical settings, the subset is often of small size, in the "ten blue links" of web search.
In this paper, we consider a learning setting with complete information on user choices from subsets of size at most k. We show that k = ((vn) is both necessary and sufficient to predict the distribution of all user choices with an arbitrarily small, constant error.
Based on the upper bound, we obtain new algorithms for approximate RUM learning and variations thereof. Furthermore, we employ our lower bound for approximate RUM learning to derive lower bounds to fractional extensions of the well-studied k-deck and trace reconstruction problems.
Introduction
In many common settings, both online and offline, users select from set of available candidates: cars on a dealer's ' lot; songs on a streaming service; movies in a Netflix carousel of choices; and so forth. Often, it is unrealistic to offer the user the entire universe of items. No car dealership has every new and used car ever produced. Likewise, recommendation services have enormous catalogs of songs, products, movies, etc, and must carefully curate more manageable subset of recommended items that will fit within the constraints of the user interface. Thus, user feedback often arrives as choice from slates of items of a certain standard cardinality-thin of "ten blue links" in web search as the classical example.
Random Utility Models (commonly called RUMs) have been the standard mathematical model for studying user choices over subsets of universe of items. RUMs are the subject of many decades of study, and the centerpiece of the 2000 Nobel prize in economics. The model family is straightforward: and is characterized by a distribution over R user draws from this distribution to generate vector specifying the utility of each item of U. The user is offered subset of U called slate, and must select a single item from the slate; the user behaves rationally by selecting the available item of the highest utility. The winning distribution of the slate is probability distribution over the items of the slate representing the likelihood (over draws from the utility distribution) that particular item selected. To learn a RUM, an algorithm given a training set of examples of slates with their winning distributions, and must then guess the winning distributions of a new test set slates.
RUM operates over a universe U of items, with [
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

We are interested in learning RUMs when the example slates in the training set are constrained to have at most certain cardinality. We will then deem an algorithm successful if exposure these smaller slates allows it to approximate the winning distribution of all slates. In the extreme example, the algorithm should infer the winning distribution over the universal slate U itself, representing the likelihood that particular item is random user's favorite from the entire catalog.
Our contributions. We present two main results representing paired upper and lower bounds for this question. The upper bound shows that, with knowledge of the winning distributions for slates of size at most O(vn), one can approximate the winning probability for any item in any slate to within an arbitrarily small additive constant. Using this upper bound, we obtain an exponential improvement in the time to learn a RUM. The previous best-known algorithm, implicit in earlier work, requires time 20(n), Our new algorithm learns any RUM to within an -eror (resp.. L frrerrrr) of > 0 in time o (V :)
(resp.. n ( log ))). We also give "simulation" result: the winning distribution of each slate T can be approximated within a constant & -error by querying polynomially many sub-slates of T, each of size at most O
log [T]
Our near- mear-matching lower bound shows that, with knowledge of the winning distributions for all slates up to size of on),, any algorithm must make error 1/2 (almost the worst possible) in predicting a target item's 's probability in the universal slate, for arbitrarily small constant e. Based on this lower bound, we also obtain lower bounds to fractional extensions of the well-studied k-deck and trace reconstruction problems.
The bounds for RUM learning algorithms depend on the nature of the oracle used to present examples to the algorithm. For a given slate, the MAX-DIST oracle returns the exact winning distribution, while the MAX-S from a real-world setting. The algorithms we present work with both oracles, with asymptotically the same running time and the same sample complexity.
oracle simply returns draw from the winning distribution, as we would expect
Overview of techniques. Our results are proved by observing a series of connections between RUM learning and the approximation of the bitwise AND function via polynomials. Specifically, the two main quantities of interest in approximating Boolean functions with polynomials are (i) the degree of the polynomial, and (ii) the En-norm of the coefficients of the polynomial. We will show that these two quantities are related, respectively, to (i) the size of the slates required approximate a RUM (Theorem Jann and Theorem 12). and (ii) the running time to approximate the winning distribution of a queried slate (Theorem and Corollary 10P.
Related work. Discrete choice has been the subject of extensive research in machine learning and economics; see [Triin] 2003) for an excellent introduction. RUMs are an important class of models in discrete choice particular, Multinomial Logits (MNLs) and their mixtures are special classes of RUMs. RUMs have been extensively studied from both active and passive learning perspectives [Soufiani et al. 2012 Oh and Shahl 20144] (Chierichetti et al.) 201 8a b Negahban et al., 2018 Tang
2020 and from an elficient representation point of view Farias et al. 2009 Chicrichetti et al.
A number of papers have used linear programming (LP) for obtaining representation of RUMs that agree with an empirical distribution on small slates [Farias et al.] [209 Almanza et al. 2022
Chierichetti et al., 2023]. J. In particular, Farias et al. [2009] make strong assumptions on the underlying RUM, while in [Almanza et al.) 2022 Chierichetti et al., 2023) the algorithms are not required to generalize outside of the observed training set. Instead, we asking what is the minimum & such that if one observes all the winning distributions of slates of size up to k, one can approximately reconstruct all the winning distributions of a RUM? Note that we do not make any assumption on the RUM and our algorithms must generalize to all the slates.
The approximation of Boolean functions via polynomials has found applications in disparate and apparently remote number of fields such as cryptography [Bogdanov et al. 2016), differential privacy [Thaler al.] 2012), quantum query complexity (Beals et al.] [001]] J. PAC learning (Klivans and Servedio] 20044, and more. Our work draws connections between this field and RUM learning for the first time, showing yet another important application of such techniques.
In this paper we also strengthen the relation, that was first observed in (Chierichetti et al. 2018a] between RUM learning and the k-deck problem.
2

---

Organization. In Section 2 we introduce the definitions and notation. In Section 3 we prove our upper bound, which we then use Section 3 to obtain algorithms for learning RUMs. In Section we present our lower bound. Finally, in and we derive, as corollaries of our results, lower bounds for other learning problems. All the proof' missing from the main body of the paper can be found in Appendix A
Background
Let in] {l....,,0 n and let S, denote the symmetric group on n items (the set of all permutations of [n]). Let also (:) = (T S S [T] =).. For a distribution D, D denotes that the random variable x is drawn from D and Dii) denotes Prz-p(æ d]. where E supp(D). For a. b E [n], π E Sn we write < b or b >5 to say that ı ranks b higher than a.
Random utility models. A slate is a non-empty subset of [n).. For a slate Ø + S S permutation क Sn, let (S) be the item of S that wins, i.e., ranks the highest in π
[Tx] and a
The following definition of RUMs, based on probability distributions over permutations, equivalent to the utility-veetors definition given in the Introduction [Chierichetti et al., 2018a]; adopt the distribution-over perooovttrttmmttiooonn definition, since it makes it easier to present our algorithmss.
Definition (Random Utility Model (RUM)). A random utility model (RUM) R on [n] is distribu- tion on Sn, For slate S, Rs denotes the distribution of the random variable (S) where π R, so (s()) = Pr(s wins in S) is called the winning distribution on S induced by RUM R.
We consider two types of oracle access to the RUM: the MAX-DuB oracle returns for a given slate the (exact) winning distribution for the slate and the MAX-SAMPA oracle returns draw from the winning distribution.
Approximation of AND. For a bit string x = 2I... E {0, 13" and S C [n]. let xs(x) = Ikes Z₁. By convention, X=(x) = 1. The function AND,, [0,1)" - {0, is the bitwise- AND given by AND,, (x) = (z). We write only AND when n is clear from the context. A polynomial p {0, 1 + R is said to e-approximate the AND function if for all x E 10 Tm holds (NND(=) - p(z) S e. The E-approximate degree of AND is the smallest value (AND() such that there exists a polynomial of such degree that e-approximates the AND function, and it is well known that the optimal value is dog, (AND) O log(1/c) [Bun and Thaler 2022 The general form of a degree-k polynomial is Es (s as Xs (z)). where the { are real coefficients. However, all the polynomials proposed in the literature have at most A + distinct coefficients ag; 01....., (gg, such that ag dIsl. therefore in this work we will focus only on polynomials of such form While it is folklore that such coefficients time, for completeness we provide in Appendix aD explicit algorithm for this task. We will use several results on the approximation of the AND function that we introduce as needed.
be computed in polynomial
3 Uniform approximation of a RUM
In this section we show that if two RUMs agree on small slates, then they nearly agree on all slates. Our result can be obtained consequence of more general result of Sherstov [2008). which is based on the approximate degree of the AND function and was originally stated only for sub-constant errors. The following is restatement of SSerstov [2088 Theorem 4.8), using the upper bound on the approximate degree of AND proved by Buhrman et al. 1999] we also make the error term explicit.
Theorem 2 (Sherstov (2008). There exists a constant e > 0 such that the following holds. Consider any two probability spaces Pi and P2, and any events AI,..., , An in Pi and BI, ..., B., in Pa such that, for any S C [m). |S| S c. /n In 1 1/e, it holds Pre, [Ne A,] Prr, (Nkes B&). Then, holds: Pre, [NEem]] Ai| - Prr. []] < 6, where e (2 1/3)
In the literature, other works focus on the coefficients of univariate polynomials ş [0, n] + R taking in input the number of bits set to one. We stress that this is not the case in this work, where we always consider coefficients of multivariate polynomials p {0, 1)" R unless otherwise specified.
3

---

Theorem 3 (RUMs Upper Bound). Let P and Q be two RUMs on [n]. There exists a con-
stant c such that for given s [n]. T - [n] {s}, if (s) Qsu(s) for
each S T' 1 TT and IT' S c. (T) In } then Pru(a(s) - Qru(s)(s)] s e, where CE (2(2-171,,7) 1/3).
Proof. Let c be the constant of Theorem and define h = c. v(Ti [T] - l/n./. Consider the probability space Pi (resp. P2) having S, as sample space and RUM (resp. Q) as the probability mass
function. For / E T. let A, be the event { E S, >> 1). Then, for any S S T, { E S.. (S {+)) = 8} = Aç. Therefore, for any T, |S| S k it holds:
Pr
[ies = Pr. Pr. = = (s) Qsu(a)()) = Pr [NiesAi Pl
T~P
P2
where the third equality follows by hypothesis. Finally, by Theorem 2
(s) (T)(O)(S) Pr A
Pr
(NterAil cc. Pa
In light of Theorem 3 accessing slates of size up to O (Vn n. In ( is enough to predict the winning distribution of all the slates, within additive In the section, obtain computational version of this result.
4 Reconstruction algorithms
In this section we obtain two algorithms for reconstructing the winning distributions on large slates using the winning distribution on small slates. The goal of these algorithms is obtain a computational version of Theorem 3 The first algorithm is a proper learning algorithm that outputs a RUM. Building the RUM takes time n ((") but once built, querying this RUM to get the approximate winning distribution of any given slate takes only polynomial time. Moreover, using previous work (Chierichetti et al. [002]. this RUM can actually be approximately represented using On log n) bits. The second algorithm an improper learning algorithm: while its output model allows uniformly approximating the winning distribution on each slate, this model might not be a RUM. Building the model takes time n ((v)) and once built, querying this model to get the approximate winning distribution of any given slate takes time 20(va), The total bit complexity of the second algorithm's 's model is n ((v)), This second algorithm has two nice properties: (i) if we are given access slates larger than vn. then querying the model becomes more efficient, and (ii) if we want to estimate the winning distribution of only M = poly(n) pre-determined slates, then building the model becomes more efficient. Putting these two properties together we are able to prove "simulation" result: for any pre-determined slate T C [rx] it is possible to estimate Rr to within
constant Lo -error e in polynomial time and accessing slates of size at most O
(T
In T
4.1 A proper learning algorithm
Fix a large enough integer & < n - 1. For RUM Q, let the winning distributions slates of size at most k. for = O (v In
be known. To estimate the probability distributions Qr for any E [n]] and for any slate T [n] {s} such that [T') < t, it is sufficient solve the following linear program (LP), with no objective function:
Σ RES T(SUfs))=3
Pr (s) V [n] AS C [n]]
{s} s.t. |S| $1SA k
Σ P=
# S
Px 2
YT S,
Indeed, returns a RUM that is compatible with RUM Q on each slate of size at most k. Applying Theorem
we obtain:

---

Observation 4. For k = =0 (vttnn)) let P be the RUM obtained by solving 1 Then, for any 8 E [n], and for any T _ [n] {8} such that (T) holds (Pro(e)(s) QT)
and solving 11 an LP with n! variables and o (Vnln constraints get: Theorem (Proper learning algorithm). Let Q be RUM over [n]. There exists an algorithm that (v RUM such that for each S S [n] and for each E S, Ps Qs(t))
By fixing t
uses the MAX-DIST oracle on each slate of size at most O n n and in time n O(n) produces
Using the result in Chierichetti et al. 2021 the RUM P can be subsampled in poly(n) time to uniform RUM P with multiset of O (n/²² permutations its support, and such that for each 5 - [m]. P3 - Ps| I c. Thus, by accessing slates of size at most O (Vnin?) (resp., O (v )) one can produce a data structure P time n ((") such that (i) P be represented with O (c-3.. n12 log bits, and (ii) when P is queried on slate S, it can return in poly(n) time distribution Ps such that Ps Qs 20
S (resp.,
Ps Qs e)
By providing a version of Theorem 3 that holds when the small slates are approximately equal, this algorithm also be made work with MAX-SAMPLE oracle. More details given in Appendix B
We mention that this algorithm can be made run in time 20(n) by using the ellipsoid method and the separation oracle of Chierichetti et al. 22033; more details are given in Appendix
4.2 An improper learning algorithm
In this section obtain learning algorithm whose data structure is RUM but be built faster. As before, this is a restatement of |Sherstov| (2008] Theorem 4.8):
Theorem (Sherstov (2008). Consider any probability space P, and any events AI...., An in P. For k 2 θ Vn- In 1/c). ..E CE (2"".1.6 ./33), let fashogigk be the coefficients of a degree k polynomial approximating the AND function within (for any S [ [r], |S| < k, the coefficient of the monomial Xs (x) ais)). Then, Pre [Nkem]] - dsl Pre [NiesA,]
Se
Given a RUM over [x] and access to slates of size k 2 θ (v (T) log : consider an element $ E [n] and a slate S [n] ~ {s}. Let far Josisk-1 be the coefficients of polynomial degree k 1 that approximates the AND function. Then, the following is good approximation for
(s)
(s)
Σ
disD (s)
SCT
In fact, choosing the probability space and events as in Theorem and applying Theorem 6 get: Observation 7. [RTU()(s) - (s) S where R is RUM over [n], E [m], T T [n] {s}.
and for 2 θ In {aiJosisk-1 are the coefficients of polynomial of degree k 1 approximating the AND TI) function (the coefficient of the monomial xs(x) is ais)).
From the above observation and given MAX- -IST oracle access to slates of size we obtain a deterministic algorithm that first stores Rs(s) for all E S C [n], |S| - k, in time ((k) and then, upon query (s. T) returns the approximation RTu(s} (s) that can be computed in [2/06//TT in(1e)) < ((k) time
e (e(/nnn11/c)
Note that this result holds for any polynomial approximating the AND function. To get a better algorithm, which also works with
oracle, focus specific polynomial. (Observe
We assume [2' 2 & otherwise computing Rru(s) is trivial since just query the oracle
5

---

also that the time to answer query in the previous algorithm does not improve as k increases. This coumter-intuitive given access to larger slates, should become easier to approximate the target slate. The second algorithm that we provide gets faster as k increases, overcoming this limitation.)
The polynomial that use is the one proposed by Huang and Viola 2022 Corollary 1.5]:
Theorem 8 (Huang and Viola ).22 For all E (2-", 1/3), In(l//) S d I n, there exists polynomial p {0, IJ" I of degree k ((d) and real coefficients Jasjss where the coefficient of (s(x) is 0|s], such that: fir each & E {0,1]", ((()) - , S G, and (ii)
ESchNISS |0sl|| = Σe= (a 200( (0()))))))
Theorem 9 (Improper learning algorithm). Let R be RUM over [n]. Let d Vnln(1/e), (0, 1/3), and 8 E (0, 1) such that e, 6 2 noi... Then, there exists randomized algorithm that accesses slates of size at most k (dd) and such that:
(i) it first makes n ((k) queries to MAX-SAMPLE oracle (or MAX-DIST oracle) and then,
(ii) for any query [n], T [n] {s), it returns, in time 20 (( poly((TT) and with probability least 8, an estimate Bru(s) (s) such that [Rruts] (s) RTu(s) (s) S..
For k @(v (1)c))), Theorem gives an algorithm with pre-processing time of n o(k) and that can answer any query (s, T) in time 20(TT) (TT (T)) < 20(y//) < 20()), Note that the query-time of this algorithm gets better increasing lo (although the pre-processing time gets worse since more slates must be queried).
4.3 A simulation algorithm
The re-processing time of the improper learning algorithm increases with the slate size because the algorithm must be able to reply to every query after the pre- prepprocessing phase. Suppose, however, that the algorithm knows advance which slates will be queried; in that case, can perform the pre-processing phase to satisfy only such requests. In this setting where the queries are known offline (or where the oracles can be called lazily), we can get a faster algorithm.
Corollary 10 (Simulation algorithm). Let R be RUM over [n). Choose any element E [ni], slate T S [m] {s}, E 1/3), and E (0,1) such that e,8 2 [T|00S. Then, there exists a randomized algorithm that, for d 2 /T accesses slates of size at most k (dd), makes at most
(PTly(TT) queries to MAX-DIST oracle (or MAX-SAMPLE oracle), and that with probability at least 8 outputs value (ru(s)(() (5) such that [RTU(s) (r)( Sc
2
Note that by choosing &: e
[T S (Im)) and constant E (0, 1), the previous algorithm
In
returns, with high probability and accessing slates of size most k, approximation Ri in polynomial time, for any predetermined
[n],T C [m] {s}.
We can also interpret this algorithm in the more general setting of [Sherstov 2008 In such setting, Corollary 10 implies that, for any events in probability space, the probability of the intersection of all the events can be well-approximated by a linear combination of polynomially many probabilities of smaller intersections (specifically, each intersection is over most Onn/ nn) events).
5 Lower bounds
In this section we present lower bound showing that it is impossible to reconstruct the winning dis- tribution of the full slate by only looking at slates of size o(yn), i.e., our reconstruction (Theorem 3) is optimal. For simplicity, we consider the approximation of the winning distribution of the full slate
[n], as opposed to any slate T in Theorem 3
'This is w.l.o.g., since we can build our construction for a given slate size t, by choosing n = t; later, one can add to the same construction as many new items as desired (placing them at the end of the sampled permutation), get to total of N 2 t items in the RUM.

---

Our construction actually shows that, in this o(vn)- setting, it is impossible to approximate the distribution of the full slate even within a constant &o error. Specifically, for any constant 0, not possible to learn whether special item, n, has probability at least 1 or at most in the full slate by accessing only slates of size oVv)..
We will make use of the following result, which is a consequence of the method of dual polynomials (see, e.g., [Bun and Thaler 2022 Chapter 6J), and was first proved for cryptographic applications in [Bogdanov et al., 2016 Theorem IJ. While the original result considers general Boolean functions, we state only for the AND function, plugging in the lower bound on the e-approximate degree of the AND proved in (Bun and Thaler, 2015, Proposition 14].
Theorem 11 (Bogdanov et al. 2016). For a sufficiently large n and constant e E (0, 1), there exists constant с O and two probability distributions μ., ib over {0, [0, such that: (i) for each polynomial p : {0, 1), + R of degree at most c vn. Ezna [p(x)] = Egwy pp()), and (ii)
[Ezy [AND(=)] Ezwe [AND(=)]] 1-c
We are now ready to prove our lower bound for RUMs.
Theorem 12 (RUMs Lower Bound). For a sufficiently large and for constant c E (0, 1). there exists constant > 0 and two RUMs A, B on [n] such that: (i) for each S C [n] such that
|S| V (n - 1) E O @v)n), it holds As Bs, and (ii) Ara BIn((n)) -
Proof. Consider the distributions μr, 1 over (0, 1) n-1 from Theorem 11 and let k: = c. Vnn - 1) We build RUM A on [n] as follows: sample x {0. 1} according to μ. then, let S. = fi [n-1] I; = }} and sample uniform at random permutation among those where the set of elements ranked lower than n Sz. RUM B defined similarly, but sampled from th. Note that for
S C [n 1]. Asu(n)(1) (n) Baz [xs [2:)], and similarly for B. Then, from property (ii) of Theorem
11 we have:
[mm - [n][ = E [AND E (ANDD-1(())) > 11-6.
map
Moreover, fix any S _ [n 11.15| $ k. We have:
Asu(n) (m) = E [xs(x)] E [xs(x)] BBBBstu (n),
amap
where the second equality follows by Theorem II (i) and since xs((x) II dy a polynomial of degree |S| < k.
remains to show that the winning distributions for the elements different from n in the small slates also coincide. We show that for RUMs A and B, these probability distributions be expressed in terms of winning distributions of n: below, we do the calculations only for A, the calculations for B analogous.
Let Il be the uniform distribution over the set of permutations where the set of elements ranked lower than n is Sg, for string x E {0. 1]=-1 For convenience, for E {0, 1}" set 2n, 1.
Choose any i E C [m]. i n, |S| S k; then:
As(i)
=1] Pr (1) and
Pr TCS PNp
Σ
Xr(x)
II (1 xx)== = (())
SES-T
Σ Pr TCS
(r(x)
II 8ES-T
(1 - (1-x))
Pr I.
TTS) =i xr(x) II .ES-T
(1 xx)
Here, the third equality follows by the law of total probabilities, partitioning the possible values of bits (xr bes. Since always holds x, 1, we assume without loss generality that either n E T
or & S. Given that II, is uniform, we have:
if E T and |S T = 0 and n & S
T
if E 7 and n T
Pr +ll,,
T(S) = xx(x) II
(1 - (1-xx)= =1
=
0
i E T and |S T
sES-T
if E S x T
B
7

---

Therefore, thanks to the conditioning, this first probability does not depend on A (the probability is the same if we sample z from to and then from II,,). Moreover:
Pr zmpp
(r(x)
II (1 18-2,y x.) =1 eES~T
E zmp
XT(x)
II (1 I.))
E zmp
Σ
(-1)1P)
xTup(T)
#ES~T
PCS-I
Σ (-1)) ATUPU(N)(n).
PESNT
Since Aruru(n)(n) (r (n)) we have As(i) (i( for any E S [n]. |S| S k.
5.1 Lower bound when only slates of size k: are given
We know that accessing slates of size natural to wonder if the slates smaller than k are needed, if those of size exactly & are enough. A simple observation shows that accessing smaller slates is necessary.
k 2,...,k
(n) is sufficient to approximate the full slate.
Observation 13. For any n, there exists a RUM R on [y] such that: (i) Rg(o) = 1/k for all E S E ((r)), and (ii) Rig (+) = 1/k for all i E [k]
Proof. Consider the RUM R that first samples a uniform at random element i E [k], this element is
placed at the top of the permutation, followed by elements [n] > [k] permuted uniformly at random,
and finally by the elements [k] {i} permuted uniformly at random. Consider any & E S E
(())
If [k], then (s(s) 1 /k. instead e [n] [k]] let a |S n [&:] < we have, Rs(s) (1 - aa/k) 1/(k - a) 1/ k. Moreover, for any i E [k], by construction, (imi(t) = 1/k.
O
Consider A: = e n, for any E (0, 1), and let R be the RUM of the previous construction. Consider now RUM Q that samples uniform random permutation over [m]] Clearly, R and Q coincide on slates of size k. but for all i E [k]. R (i) = 1/k and (2) = 1/n,, and in particular the & disittnne 2c. Therefore, any algorithm accessing only slates of size = O n) will incur in an --erroor of - e on the full slate. By selecting k O(n"), for any (and also an eeror of (2( )) on the full slate. On the other hand, accessing all the slates of size O (Vn lo and smaller, one can obtain an -error as small as 1/n for any constant > 0. Therefore, accessing smaller slates is necessary.
between R R[n and Q/n] is k- (1/k 1/n) + (n k)/n=
(0, 1), have that any algorithm must incur fi-error of 1 n=
Fractional kedeck
The de-ecc problem [Kalashnik] 1973] is well-studied problem at the intersection of combinatorics and computer science. Given a string E {0, 1}" and set I (i.,..., i <... < ig. the projection of s to I, denoted as 87, is the string sy = St, ... 8ig. The k-deck of s the multiset
ix) .......,x]
(I)) with
VI [m]]
De(s)
The k-deck problem asks for the smallest k = kn))) such that any n nibit string can be reconstructed from its k-deec. This problem has a long history. Manvel al. [1991] originally showed that reconstruction is possible with & 3; they also showed that it is not possible with k = O(log n)) Later, it was shown in [Kasiiovv and Roditty/ [1977 (see also [Scott] 1997] that reconstruction always possible with k = O(vn); it is widely conjectured that this bound is tight. The best known lower bound, however, no better than subpolynomial: in [Dudik and Schulman 2003 is shown that & = @ is insufficient for reconstruction. In |Chierichetti et al. 201 8a lower bounds for the k-deck problem were used to obtain lower bounds the maximum size of slates required for reconstructing a RUM.
In this section we define fractional version of the k-deck problem and show a reconstruction lower bound. Note that the k-deck of string is a function fa (0, 13* Z2o, where fs(s') is the multiplicity of s' in Ds(s). Now, given a probability distribution P over n-bit strings, the

---

Theorem 15. For each constant >> O, there exists constant с > 0 and two distributions XA and X B over n-bits strings of weight such that if d 1 _ J. then (i) with fewer than 2/7 fractional k-deck of P is a function fp -0.11- - +R20 where fp(s') E [s') Also, for a distribution P over n-bit strings, we define its ith marginal be the probability that the ith bit of string sampled from P equals 1. The fractional k-deck problem seeks the minimum k = k(n, e) such that the fractional k-deck of an unknown distribution over n-bit strings is sufficient to approximate any marginal of P to within an additive c. It is easy to see that the fractional k-deck problem generalizes the k-deck problem (by also setting e < 1/2).
Based on our RUM lower bound, we can construct two probability distributions over binary strings giving the same fractional (dynk, but very different marginals for the first bit, obtaining:
Theorem 14. For sufficiently large n, and for each constant >> there exists constant > 0 and two distributions XA and Xg over n n-bits strings of weight that (i) give rise to the same fractional k kedeek, for k = Ic- vn], (ii) the marginal of the first bit of X is 2 1 c, and (iii) the marginal of the first bit of X is S.
7 Fractional trace reconstruction
In the trace reconstruction problem, there is an unknown n-bit string and parameter d' (0, 1). A sample is obtained by passing z through a d'deletion channel that erases each bit of independently with probability d. In this setting, one asks for the minimum number of samples necessary to reconstruct z. Indeed, with probability (1 - d)" itself is returned as a sample and
hence reconstruction is trivial with 92 ((1 d) =)) samples. This problem has been the subject of
intense study [Chase 202 b. De et al. 2017 Batu et al., 20044, Holenstein et al. [0088 Nazarov
and Peres 2017 Peres and Zhai 2017 Viswanathan and Swaminathan, 2008). It can be solved with
samples in the so-called high deletion rate setting ( < d S 1 -
). and this bound vn
is tight for a special class of "mean-based algorithms [De et al. 2017].
In this section we prove an unconditional lower bound for the fractional trace reconstruction problem, which we define similarly to the fractional k-deck problem: given a distribution over the n-bit strings, sample string from that distribution, pass the string through d-deletion channel, and return the resulting subsequence as a sample. Note that, each time, a new fresh string is sampled before passing it through the deletion channel. The goal is to reconstruct the marginals of the distribution.
Several variants of trace reconstruction have been studied in the literature [Chen et al. 2023 Davies et al.
2021 The variant closest to ours is perhaps the average-case trace reconstruction [Peres and
Zhai 2017]. However, average-case trace reconstruction is computationally easier version of the problem since the single hidden string is sampled from a uniform distribution. Our fractional trace reconstruction is instead true generalization of trace reconstruction.
We will show that fractional trace reconstruction cannot be solved with fewer than el(vT) samples. Our lower bound is obtained as a corollary of our result for the fractional k-deck problem.
col(1-d) (((1-d)-n) m) =oo(%) samples, the probability of correctly distinguishing between XA and XB is at most 1 + o(1), (ii) the marginal of the first bit of XA is 2 of <
1 - and (iii) the marginal of the first bit
In this very high deletion rate setting (d = 1 (
the magnitude of our lower bound for fractional trace reconstruction is not larger than that of [De et al. (017)] for trace reconstruction; our lower bound, though, holds for any reconstruction algorithm, not just for mean-based ones.
vT
8 Conclusions
We considered the problem of learning a RUM by only looking at slates of size at most k. We showed that to obtain uniform approximation of the winning distributions, k: O(vn) is necessary and sufficient. Moreover, we provided two explicit algorithms that learn the RUM. While optimal with respect to the slate-size, both our algorithms require time exponential in n: we leave open the problem of finding algorithms with better running times.

---

We also provided a third algorithm that can approximate any given slate by accessing only poly- nomially many subslates of size (nn/ In n). In this setting, we leave open the problem of decreasing the slate size, while maintaining a polynomial running time.
Another interesting research direction would be considering PAC-learning variant of the problem, where the slates of the testing phase and/or the training phase come from a probability distribution and the goal is to minimize the expected error in the testing phase. This variant might be easier with respect to both slate size and computational complexity.
Acknowledgments and Disclosure of Funding
The authors thank the anonymous reviewers, whose insightful suggestions directly led to significant simplification of our results. Flavio Chierichetti and Alessandro Panconesi were supported in part by BiCi Bertinoro international Center for informatics and by Google Focused Research Award. Flavio Chierichetti was supported in part by the PRIN project 20229BCXNW.
References
Matteo Almanza, Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, and Andrew Tomkins. RUMs from head-to-head contests. In ICML, pages 452-467, 2022.
Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor. Reconstructing strings from random traces. In SODA, page 910-918, 2004.
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4), 2001.
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson. Bounded indistin- guishability and the complexity recovering secrets. In CRYPTO, 2016.
Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. Bounds for small-error and zero-error quantum algorithms. In FOCS, pages 358-368, 1999.
Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Information and Computation, 243:2-25, 2015.
Mark Bun and Justin Thaler. Approximate degree in classical and quantum computing. Foundations and Trends Theoretical Computer Science, 15(3-4):229 423, 2022.
Zachary Chase. New lower bounds for trace reconstruction. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 57(2):627 643, 202
Zachary Chase. Separating words and trace reconstruction. In STOC, page 21-31, 2021b.
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha. Approximate trace reconstruction from a single trace. In SODA, 2023.
Flavio Chierichetti, Ravi Kumar, and Andrew Tomkins. Discrete choice, permutations, and recon- struction. In SODA, pages 576-586, 2018a.
Flavio Chierichetti, Ravi Kumar, and Andrew Tomkins. Learning a mixture of two multinomial logits. In ICML, pages 961-969, 2018b.
Flavio Chierichetti, Ravi Kumar, and Andrew Tomkins. Light RUMs. In ICML., pages 1888-1897, 2021.
Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Alessandro Panconesi, and Andrew Tomkins. Approximating RUM from distributions on k-slates. In AISTATS, pages 4757-4767, 2023.
Sami Davies, Miklós Z. Rácz, Benjamin G. Schiffer, and Cyrus Rashtchian. Approximate trace reconstruction: Algorithms. In ISIT, 2021.
Anindya De, Ryan O'Donnell, and Rocco A. Servedio. Optimal mean-based algorithms for trace reconstruction. In STOC, page 1047-1056, 2017.
10

---

Devdatt Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Random- ized Algorithms. Cambridge University Press, 1st edition. 2009.
Miroslav Dudík and Leonard J. Schulman. Reconstruction from subsequences. Journal of Combina- torial Theory, Series A, 103(2):337-348, 2003.
Vivek F. Farias, Srikanth Jagabathula, and Devavrat Shah. A data-driven approach modeling choice. In NIPS, pages 504-512, 2009.
Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder. Trace reconstruction with constant deletion probability and related results. In SODA, page 389-398, 2008.
Xuangui Huang and Emanuele Viola. Approximate degree, weight, and indistinguishability. ACM ToCT, 14(1), 2022.
L. I. Kalashnik. The reconstruction of word from fragments. Numerical Mathematics and Computer Technology, pages 56-57, 1973.
Adam R. Klivans and Rocco Servedio. Learning DNF in time 210(n JCSS, 68, 2004.
Ilia Krasikov and Yehuda Roditty. On reconstruction problem for sequences. Journal of Combina- torial Theory, Series A, 77(2):344-344 -48, 1997.
Bennet Manvel, Aaron D. Meyerowitz, Allen J. Schwenk, Ken W. Smith, and Paul K. Stockmeyer. Reconstruction of sequences. Discrete Mathematics, 94(3):209-219, 1991.
Fedor Nazarov and Yuval Peres. Trace reconstruction with exp(O(n!/3) samples. In STOC, page 1042-1046, 2017.
Sahand Negahban, Sewoong Oh, Kiran K. Thekumparampil, and Jiaming Xu. Learning from comparisons and choices. JMLR, 1172:1477--152, 2018.
Sewoong Oh and Devavrat Shah. Learning mixed multinomial logit model from ordinal data. In NIPS, pages 595-603, 2014.
Yuval Peres and Alex Zhai. Average-case reconstruction for the deletion channel: Subpolynomially many traces suffice. FOCS, pages 228-239, 2017.
Alex D. Scott. Reconstructing sequences. Discrete Mathematics, 175(1):231-238, 1997.
Alexander A. Sherstov. Approximate inclusion-exchusion for arbitrary symmetric functions. CCC, 2008.
Hossein Azari Soufiani, David C. Parkes, and Lirong Xia. Random utility theory for social choice. In NIPS, pages 126-134, 2012.
Wenpin Tang. Learning arbitrary mixture of two multinomial logits. arXiv, 2007.00204 2020.
Justin Thaler, Jonathan Ullman, and Salil Vadhan. Faster algorithms for privately releasing marginals. In ICALP, 2012.
Kenneth Train. Discrete Choice Methods with Simulation. Cambridge University Press, 2003.
Krishnamurthy Viswanathan and Ram Swaminathan. Improved string reconstruction over insertion- deletion channels. In SODA, pages 408, 2008.

---

A Missing proofs
A.1 Proof of improper learning algorithm result
Proof of Theorem 9 Fixed integer d 2 v In(1/e), consider the polynomials given by Theorem to approximate AND& AND,, These polynomials will have degrees kg,..., k2 and & f-mm of the coefficients Wa...., Wn. Let l = [ka) = ( be the maximum degree of these polynomials and let W [ax S 20 - 2 be the maximum &n-orrm of the coefficients of these polynomials. Note that these values can be computed in poly(n) time. The algorithm will access slates of size at most k.
Let us start by describing the first phase. Using the MAX-DIST oracle, the algorithm simply stores the values (ES Using the MAX-SAMPLE oracle, the algorithm must instead estimate such values. In particular, let H = k E (*) = [max (1, log f 1 log 3 1. and m [W7 4 n da + H, note that a = O()) given that ed 2 1/n therefore m = 0(0), Fixed any [m], C [n]] [.), < 1, the algorithm makes queries to MAX-SAMPLE oracle for the slate SU (8). Upon such query the oracle samples π ~ and returns (S {*}), X; be the indicator variable that 1 if the ith query returns and 0 otherwise. Define the random variable R (8) = |/ Em]m X;, and observe that E Rsu(e) (s)] Rsu[s) (8). A standard additive Chernoff bound (see, e.g., Duubaahi and Panconesi, 2009 Theorem 1.1]) ensures that:
Inm 2 m
Pr [sS (s)
m
We repeat this process for each slate of size at most and, given that m 2 H, a simple union bound ensures that with probability at least 1 - 2/m 2 6 it holds that, for each [n], S
[n] {s), |S] s we have [Rs (s) (s((.) (s) S T m 1/4, m-44 This concludes the first phase of the algorithm, which makes ne ((k) queries and successful with probability 1 8-
Consider now query s E [n], T S [n] {s}, we assume [T'| 2 k 2 vn otherwise the algorithm
can just return Rru(e) (s) (or Rrug (s) if it has access to MAX-DIST oracle). We describe the rest of the algorithm with the MAX-SAMPLE oracle. Consider the polynomial, given by Theorem of degree at most k 1 with coefficients {oibogigk-1 that c-approximates AND and let
8.
W
(aol S W. Note that the inequalities are true by our initial choice of k and W.
Define
(s) (s) = Σ dssl Ass
S
By the triangle inequality and Observation 7
we have:
(s) (ru(s) (s) (s) Rru() |RTu(s)(s) (s)
<
Σ
lasil [sS( (s) +c
SCT, SISk-1
1/4 W m 114 + te 2e.
Grouping terms with the same coefficient, we have:
k-1
k-1
[T)
(s) ==
Σ Oc Σ (s)
Σ ac
[s)[,
(~)()
sE(?)
where the expectation is over a uniform at random S E (?)) To get a faster algorithm, we estimate this expectation via sampling. Fix c E {0, ll....,,, 1}. and define m [W [T]da, Sample
WWen using LAX-DIST oracle we simply have Rru (s) = (s)
12

---

mn slates S1..... ......,Sm Sm i..dd and uniformly at random from Again via Cneemoff-Hoeftiee bound, we obtain:
()) Define Mc 1 Rssu(s)
Ei=
m
In m
2 m
Pr Mc
E [ s-())
m
Using that 2 [T] 2 and by applying a union bound, we obtain that with probability at least
2/m 2 for each e E (0, 1,..., ., k - } holds JM, FT)((T) [Rsute) S
In m
m 1/4 S W Define finally our estimate for (s):
1-1
(T)
(+)
(0)
Σ
ac
M
c
c=0
With probability at least 1 - 8, we have:
(s) - (8)
aae
M
F.
[s)
S W. W 17| S
SE(:)
Therefore, a triangle inequality implies [Tr(s)) (s) - ( (s) S 3c. Since c can be chosen arbitrarily, we can set == e/3 and obtain the desired approximation guarantee.
Finally, note that by Theorem W 2 Tl therefore k 20 T and this also the running time to answer a query.
poly((7)
A.2 Proof of simulation algorithm result
Proof of Corollary 70 Consider the polynomial given by Theorem g to approximate AND mI Such
polynomial has degree lc (dd), and & -o-mrrm of the coefficients at most W = 20 (2 Setting m [W4] [T)4a 4a for a [max log 1. log 31 we have that the estimate R (s)
returned by Theorem a
[ru(s) (s). To compute such an estimate, one needs compute Me for each E (0. T, h - }}. and each of these values requires knowing R.. (s) for m
slates 81, ...... Sm, finally, each such slate requires m ni queries to MAX-SAMPLE oracle (or
one query to MAX-DIST oracle). Therefore, with total of k m. m = 20 (m1 queries, we can provide the desired approximation.
poly (
A.3 Proof of fractional k-deck lower bound
As a first step to proving a lower bound for the fractional k-deck problem, we show that, for the RUMs of our lower bound construction, the MAX-DIST oracle can used to reconstruct, for each slate, the distribution over the permutations of the slate induced by the RUM
Lemma 16. Consider RUMs A and over [n] given by Theorem 12 For each slate S, the distribution over the permutations of S induced by RUM A (resp. B) can be obtained from the values (ATu(H) (n)rrss (resp. (B)
Proof. Fix any slate C [n]]. For a permutation over [n]. denote with S, the slate S sorted according to æ. Let S be the set of all possible permutations of S. Note that S E S. We focus on RUM A, the proof is identical for B. We have prove that for all p E S, PrawasS p] can be written in terms of {ATu(n) (n))((s.))))........ It holds:
Pr [S, = p] Σ ANA
Pr 2Npastell
Xr(x)
II (1 - xx) = n S, =
TCS
eES-T
Σ Pr
(x) II (1 x3.) x=)=1
=1
Pr x-
S p (x(x)
II (1 x.)) #ES
TCS
SES-T
Incidentally, this is impossible in general RUMs.
13

---

As proved in Theorem 12 the first probability can be written in terms of (Apu(a) (n) is also easy to see that, once the bits {Ix are fixed, one can write explicitly the probability that S and that such probability does not depend on RUM A.
We now prove the lower bound for fractional k-deck.
We use the RUMs A and B from the construction of Theorem 12 to obtain two distributions over n-bit strings of Hamming weight one.
Proof of Theorem 14
Given RUM A (resp., B) we define XA (resp., XB) to return an n-bit string containing in position i, and O's in all the other positions, whenever (resp., B) returns a permutation where the "special" item n is in position i.
Recall that 0 < E < is a constant, Theorem 12 guarantees that for each slate S S [m]] such that
|S] S C. v for some C, O, holds As Bs. As consequence, Lemma 16 guarantees that RUMs A and B give rise to the same distributions over projected permutations on slates of size at most [c. vnj. Thus, the fractional k-deck of X equals the fractional k-deck of XB. Indeed, let S be the binary string induced by slate S when sorted according л, then, for any {0, 13
(x)
Σ Pr = (E(
Σ (2(
Pr Ir fx)
Theorem 12 also entails that A (n) > 1 1 and Binj (n) S Therefore, XA returns a bit string with 1 in the first position with probability at least 1-c E, whereas X returns a bit string with 1 in the first position with probability at most c. This yields the desired lower bound.
L
A.4 Proof of fractional trace reconstruction lower bound
Proof of Theorem 75 Given a string x E {0, 1}", let Da., be the random variable that represents
the output of a deletion channel with erasure probability d on input æ;; let &a,d,x be the event that this output has at least a(1 d)n bits. Then, Pr(Ca,da)] is a function only of o;, d, and |a|| = n; let Pa,d, dr]
Observation 17, It holds P2.d. S e e-1 (1-d)n/33,
Proof. Let x be any string of length n. By standard multiplicative Chernoff bound (see, e.g., Duubashi and Panconesi 2009 Theorem 1.1]), we get:
Pr [r[ 2 2(1 d'm] = Pr Pa., 2 2E Se- EE Da. e -1--d)///
Thus, if we sample the deletion channel fewer than o (e(1-d) times, with probability - (1) we will never get sample of length more than 2(1 - d)n, We can then apply Theorem 14 which gave the same fractional k-decc (hence the same fractional k de-deck for each 1 < k= k) for
= Ic Vnj to its two distributions XA and XB. while guaranteeing very different marginals on vn O(1) and therefore we have no sample of length more than c +n+ O(1). Under this conditioning, the two distributions induced by the channel seeded by XA and the channel seeded by X B are the same. Indeed, call y/ such event, then for any string y, lyl - 2(1 d)n,
their first bit. Selecting
2 + 2n we get that 2(1 - d)n
Pr [Daxx = = V = Pr [|aa = lyv XoXA
V
Pr. X~XA
[Da,x = = v1aaax = |v]]
X~XA
xx= = x] fz(v)
Pr X~XB
D ly/ V
Σ
Pr
X~XA
(7)
=E(0.1)
Prx [Daxx] = Iyl
V
fxa (2)
'This is true for standard le-ecck (see Manvel et al. fractional version.
1991 and the argument directly generalizes to the
14

---

Prx~Xoll 1|
1yl V
Ix (1)
(01) [Dax = 1...
Pr X
We then get the desired lower bound.
B Proper learning algorithm with MAX-SAMPA oracle
Theorem 18. Let P and Q be two RUMs on [n]. There exists constants c, d > O such that for a given E [nl, [n] {8}, if (PsSoo))()) Qsuts)(b)] S 2 2- 2-dm//m for each
S E (T' I and IT' c VITI- In } then ( Qr)( S 6, where e (2 v
Proof. Consider the polynomial given by Theorem for = In(//e, of degree k S c VIT[n((//) = e( (n(/e)) and with fn-nrrm of the coefficients W s 2c" //T/i/((( =
20 (T] for some constants c, c, > 0, that e-approximates AND Ty- Set = d" + Then,
by Observation 7
(r)(ss]s) Qr)(s)()) S (ru(ss)) - (r)) (QQr(()(ss))))))) (s)++
(P) (s) - (s))
<3e,
where the last inequality uses (Pruaa) (8) (s)(s)(s) s W. 2-d'V// < 2 Vi Setting e == c/3 completes the proof.
2-V S c.
A practical implication of this theorem is proper learning algorithm using MAX-SAMPLE SAMPLE oracle. Indeed, using enough samples one can approximate the winning distributions within an exponentially small error, and then, fitting the approximate winning distributions with a RUM minimizing the maximum error, the theorem guarantees that such RUM will approximate the original RUM on any slate.
It is not difficult see that an analogous theorem can be proved in the more general setting of Sherstov [2008]: taken any events AI,..,, An. and Bi Bi.... B, such that the probabilities of the .
intersections up to size @(vn n (1()))) differ by at most an exponentially small error, we have that the probabilities any intersection differ by at most e.
C Proper learning algorithm in time (0(n)
In this section, we give more details how to improve the running time of the proper learning algorithm from ((n) to 20()) both for the MAX-DIST oracle and the MAX-SAMPLE oracle. The n (()) algorithm for both oracles, can be obtained by solving directly the following LP with the ellipsoid method, for k = (n(/el((l/e))
min Σ
Pr D(SU
SS [n]
(s) St. [S] S k
TES
(SU(s)))
Σ
- - (o), - ASA
IS|
S k
TES
(2)
T(SU(=))== )=
Σ P7 =1
T
<20 0
Pr 20
VT Sn
15

---

Where (s) is equal to Qu (s) for RUM Q in case of MAX-DIST oracle, or it is equal to an approximation Qsugey(>) (s) in case MAX-SAMPLE oracle. Our strategy to compute the optimal solution of (2) by first passing to the dual to reduce the number of variables. In particular, by employing the same ideas of et al. 2023), one can see that the dual LP is:
max B
Σ
D(S,)) 8) As.a
SESC ISikkk
E
A (,)
B
VT E Sn
ScInLIS S
Σ
As 1
(3)
S.. unrestricted B unrestricted
vs E 1 k
Note that the constraint
S S can easily be turned into a linear constraint by &ES[miI.sIs
Σ
introducing one auxiliary variable for each As... Given a possible solution B, f (es.
checking all the constraints {ESCI)) (s) 2 BEs, is equivalent solving an instance of Weighted Feedback Hyperedge Set as described in Chierichetti et al. (023) and this can be done in time (0(n) via dynamic programming [Chierichetti et al., 2023] Theorem 10]. Therefore, via the ellipsoid method, the dual (3) can be solved in time (0m),, In particular the ellipsoid method will call the separation oracle at most 20(n) times, obtaining at most (0 separating hyperplanes relative to a permutation constraint. Let S S,, be the set of permutations relative these constraints. Now, by solving the LP (2) restricted to the permutation variables P. we obtain an optimal RUM R for LP
(2 in time 20(n), The output of our proper learning algorithm is R.
D Computing coefficients in polynomial time
We show in this section that the coefficients of the polynomial proposed by Huang and Viola [022] approximate AND,,, are computable in polynomial time. This is folklore in the literature, but for completeness, we provide here an explicit algorithm.
Since the AND is symmetric function, the construction of HHaan and Viola 2022 consists of first building a univariate polynomial q: [0. 1] - R such that: (i) ((1) = and (ii) ((i/n)] <
for all (0, 1....,P n 1)- Then, the final polynomial is p(x:)
hE Te #z/n) /n) that clearly
e-approximates the AND on n bits. We first show that, given the coefficients of the univariate polynomial g, those of the final polynomial p are computable in polynomial time.
For a set and a tuple E A define sT' as the set obtained by removing duplicates from T (e.g., (e, 1, 2, 3)) = (1,2,3)). For set A + Ø and integer b define m(A, b) (T E A (7)) A)/. Instead of writing m ([a). b) we usually write m(a, b) for integer 2 1. Define for convenience m0) = and m(0, 6) = 0 for b 2 1.
Lemma 19. The following properties hold for A * Ø. b 1:
(i) m(A b) m((AA1,)). b).
(ii) ifb < a, ma, b) O,
for every n 2 - (7) m(,. =n. (iv) if 2 a, m(a,b) = - -i-1 (9) mmi,b))
Proof. Properties (i) and (ii) are immediate by definition.
Note that property (iii) is true for n = If n 2 1, note that for each tuple T E [n] there exists unique non-empty set S C [rs] such that set = S.. Let [set(T') S] be 1 if set( S and 0
16

---

otherwise. Then:
n = Σ
Σ (sc = =S
Σ
Σ
(set(T) = =|
Σ
m(S,b)
Sc TE(N)
Sc 51 TES*
$C s0nl
(in(n.b)
Σ
m(i,,b)
where the last equality applies properties (i) and (ii). Property (iv) follows by applying property (iii) with n = a.
Lemma 20. If q
[0, 1] - R a univariate polynomial of degree k with real coefficients (ai)ie(o,1,....1) then p [0, + E, such that p(x)
D (2)=1_)) ")). is a multivariate polynomial
of degree l such that p(x) = Σ SgghsssSs P|s (x(z) with coefficient Bist = 16=1s 15
m b))
n
Proof. By definition, q (2 therefore, for i 2 1. we have:
Σ Ei=o 04
[ n
Note that for each j [n], x3 Zzj.
Σ
II -イ
Σ
m([S), (x)
JEIn
tE|n JEMy
1E
where we used that m([S),
mS, = (t E [n]] set(t) = S} Therefore:
p(x) ag Σ
Σ
m(S)) xs(x)
i=1
sc
Si
=0 +
Σ
Σ
m())) xs(x) ag
Σ
xs(x)3
SC
scIm
Finally, note that using the convention m(0,0) 0) 1, (0, b) 0 for 2 1, we have 30 0c.
From the recurrence of Lemma 19 iv), it is easy to devise dynamic programming algorithm that computes all the needed values of maa, b) in time O where le is the degree of the univariate polynomial. Therefore, from the coefficients of the univariate polynomial g, one can compute those of the final polynomial in time O(k"), using Lemma
20
We now focus on the univariate polynomial of Huang and Viola 2022). This polynomial is the product of n Chebyshev polynomials shifted and scaled. In particular, recall that the Chebyshev polynomial of the first type of degree d, Ta(x), is defined by the following recurrence: To(x) = Ti (z()) Ta+ (x) 2x Ta(x) - (x). Therefore, via dynamic programming, the coefficients of T'(x) can be computed (d A simple calculation shows that, if (a; (ae..........) are the coefficients of (a(),, then Ta(a x7 + b), for integer 7, is a polynomial of degree d 7, where coefficient of the term x is Ei, jnj ()) (bb for E {0, 1,..., d}, while all other monomials have coefficient O. Therefore, the coefficients of Ta(a xx + b) can be computed in O(d2) from the ag's. Let d; for E [n]] be the coefficient of the ith Chebyshev polynomial in the product of the final polynomial. The final polynomial has degree k, therefore computing the coefficients of all the scaled Chebyshev polynomials takes time Σn= O < (E )d,))) = O(k²). Recall that two polynomials of degree & can be multiplied in time O(k log k) via the Fast Fourier Transform, then the
n - 1 multiplications can be performed in time Onk log k). Putting it all together the coefficients of
the polynomial can be computed in time O + nk log k + k²) O(nk log k + k3).
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:
[Yes]
Justification: upper bound and algorithms can be found in sections 3 and while the lower bounds section Lower bounds for other problems are in sections and
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: section 4 and section 8 Shighlight the limitations of the algorithms.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
18

---

Justification:
proofs missing from the main body can be found in Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
19

---

Answer:
[NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp..c/pulli//guuii wwwiiicgguie///eeeeeee CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
20

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification: the paper conforms with the NeurIPS Code of Ethics
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: there are no foresecable negative impacts; while on the positive side, the ideas introduced might potentially be used improve recommender systems.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
21

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: the paper does not include experiments and we do not release any data nor model.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: the paper does not include experiments and does not existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cow/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
22

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "doulrcL5IL", "reviewer": "Reviewer_19Lt", "summary": "The paper considers the Random Utility Model (RUM) problem and gives upper and lower bound on plate size.\n\nRUM is a classic economic model that is used to understand user behavior by modeling choices from subsets of available items. In the RUM problem, there is a set of element $[n]$ and there is a probability distribution $P$ over the permutation of $[n]$. The algorithm could query a set of $k$ elements, and either observe the one with the highest rank (sampled from $P$) or the winning distribution on these $k$ elements. The paper seeks to understand the optimal value of $k$, such that the algorithm could figure out the permutation distribution (up to small error) given all plate of size $k$. The answer turns out to be $k = \\Theta(\\sqrt{n})$.\n\nIn particular, \n1.  The upper bound shows that knowledge of choices from slates of size$ O(\\sqrt{n})$ allows approximating the choice distribution for any slate with high accuracy. Moreover, it gives an algorithm that learns RUMs efficiently: A proper learning algorithm with $n^{n}$ time and an improper learning algorithm with $n^{\\sqrt{n}}$ time. \n2.  Lower bounds are derived, indicating that learning from slates smaller than $\\sqrt{n}$ results in high prediction errors. These results also contribute to understanding the k-deck and trace reconstruction problems.\n\nIn terms of technique, the proofs rely on connections between RUM learning and the approximation of Boolean functions by polynomials. The paper leverages results from the approximation of the AND function to develop their bounds and algorithms.\n\nOverall, the paper solves a meaningful problem and characterizes the optimal plater size. The drawback is that that query complexity and the runtime is exponential.", "questions": ".", "limitations": ".", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper solves a meaningful problem and characterize the optimal plater size.", "weaknesses": "1. Query complexity and the runtime is exponential; \n2. I think it needs some explanation on the query model. In particular, why the model can only see plate of size $k$. \n3. The writing could be improved: for example, Line 58, our results are proved *by* observing; Line 95, the citation appears at a wrong place.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments. \n\n1. Please see the general comment.\n\n2. We were motivated to consider this model by the observation that modern user interfaces work hard to present small and easily scanned slates for the user to consider; typical examples of such interactions are the 10 blue links of Web search, the 3 choices in Google local search, or the handful of movies in a Netflix carousel. Therefore, we allow access only to slates of size $2,\\dots, k$ and our goal is to make $k$ as small as possible while providing good estimates to every slate.\n\n3. Thank you for pointing out the typos; we will improve the writing in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eH6L80wseT", "reviewer": "Reviewer_5X2F", "summary": "A random utility model is defined by a distribution over permutations of $1,2,\\dots,n$. Given a non-empty subset $S \\subseteq \\{1,2,\\dots,n\\}$, an oracle stochastically returns which one in $S$ is the highest according to this distribution. This paper considers the problem of estimating a random utility model from winning probabilities for small $S$.\n- This paper first proposes an algorithm that queries all $S$ with $|S| = \\tilde{O}(\\sqrt{n})$ and then estimates a RUM by solving an LP. The authors shows that this estimated model has small error even for large $S$. This algorithm takes $n^{O(n)}$ time.\n- Next the authors consider an approach of expressing RUMs by polynomials. The proposed algorithm again queries all $S$ with $|S| = \\tilde{O}(\\sqrt{n})$. However, as the expression of an estimated RUM does not require $n!$ dimensions, both the estimation and prediction takes $n^{\\tilde{O}(\\sqrt{n})}$ time.\n- The authors also provide a lower bound. That is, if two RUMs coincide on all $S \\subseteq [n]$ with $|S| = O(\\sqrt{n})$, the error for $S = [n]$ can be very large.\n- The last contributions are on the fractional versions of the $k$-deck and trace reconstruction problems. The authors give lower bounds on the sample complexity for these problems based on the RUM lower bound.", "questions": "Is there any possible future direction to develop the results of this paper for more practical applications?", "limitations": "The contribution of this paper is only theoretical and does not seem to have a large practical impact for now.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "RUMs are an important decision making model in economics and statistics, and the problem of estimating it from data is significant. For this problem, this paper determines the size of queries (i.e., $|S|$) that is necessary for estimating a RUM by providing both upper and lower bounds. For the upper bound, the main technical contribution is to translate the result on the AND function by Sherstov (2008) to RUMs. For the lower bound, the authors construct a difficult instance by reducing it to the difficult instance on the AND function proposed by Bogdanovet al. (2016). These proofs are decently built on existing results on boolean functions. The lower bounds for fractional $k$-deck and trace reconstruction are also interesting.", "weaknesses": "In my opinion, the largest weakness of this paper is the lack of practical insight. The main result claims that estimating a RUM requires $n^{\\tilde{O}(\\sqrt{n})}$ queries, which is unrealistically large for suggested applications such as web search results. Theoretically, this bound is meaningful; the upper and lower bounds coincide, so this order is tight. However, in practice, I do not know a realistic scenario in which we can query all size $\\tilde{O}(\\sqrt{n})$ subsets, and the proposed algorithm seems to be designed for the theoretical purpose. Actually, the authors do not provide any experimental result. I think there might be a more appropriate venue other than NeurIPS for this paper. The technical contribution of this paper is mainly to relate RUMs and the AND function, which seems to attract more audience in TCS conferences.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments. Regarding the computational complexity of the algorithms, please see the general comment. Also note that, while querying all the slates of size $O(\\sqrt{n})$ is required to learn the complete RUM, if we are interested only in some target slates, our algorithm becomes more efficient as characterized in Corollary 10.  \n\nRUM learning is an important ML problem that is still not well understood theoretically. We believe our work is an attempt to fill this gap and would be of interest to the ML community, as evidenced by previous work [Farias et al., NeurIPS 2009, Soufiani et al., NeurIPS 2012, Oh and Shah, NeurIPS 2014, Chierichetti et al., ICML 2018, ICML 2021, Almanza et al., ICML 2022].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7b3GH8U0FL", "reviewer": "Reviewer_R6u3", "summary": "This paper studies the problem of learning a Random Utility Model with limited information.  A RUM is a distribution on the symmetric group on $n$ letters and a slate is a nonempty subset of the universe of letters.  The paper studies the problem of learning the RUM given access to the probabilities that a given letter $s$ is most preferred by a sample from the RUM out of all of the elements in a given slate $S$.  The authors apply classical techniques to derive an information theoretic upper bound for the necessary size of a slate in order to learn the RUM to additive error $\\epsilon$, which is complemented by a matching lower bound at the end of the paper.  They then provide two algorithms bounding the sample complexity of learning the RUM with such slates: one relying on solving a linear program requiring $n^{O(n)}$ samples and another algorithm relying on polynomial approximations for the Boolean AND.  The latter algorithm is then applied to demonstrate that large slates can be used to learn an RUM in polynomial time to constant accuracy.  The paper concludes with applications of their techniques to two other problems in the intersection of combinatorics and CS theory.", "questions": "1. Is there some middle ground in the size of the slates, say $\\Theta(n^c)$ for $1/2 < c < 1$ that allows for poly algorithms in approximating the RUM?  As it stands there is quite a gap between the exponential algorithms in the case of $\\Theta(\\sqrt{n})$ and the poly algorithms in the case of $\\Theta(n / \\log n)$.\n\n2. Are there weaker notions of learning the RUM that allow for either smaller slates or more sample-efficient algorithms?  For example, I could imagine that some of the sample complexity is coming from learning the precise order of very low-preference items in high probability according to the RUM.  If one were to only care about properties of the RUM relevant to some notion of the most preferred items, can the bounds be improved?\n\n3.  It would be nice to rigorously demonstrate that the algorithm in Theorem 5 actually can be made to run with $2^{O(n)}$ slates as opposed to $n^{O(n)}$.  It is poor form to simply state this as a footnote, as future authors may wish to cite this result without being forced to rewrite your entire proof.", "limitations": "The limitations have been adequately discussed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper lays out a clear and interesting problem and provides a fairly complete solution using classical results in Boolean analysis in novel ways.  The solution is thorough and the presentation is clear and compelling.", "weaknesses": "The main weakness in the paper is the exponentially large number of slates required by the algorithm in order to learn the RUM.  The simulation lemma is able to reduce this to polynomial at the cost of increasing the size of the slates, but the time is still exponential in the error.  It would be nice to have a clearer idea of the landscape with respect to if polynomially many slates are sufficient even in a polynomially smaller slate setting.  The authors also heavily use prior technical contributions and it might be useful to better delineate the core technical contributions of the present paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and suggestions.\n\nExponential time: please see the general comment.\n\nOn a high level, the main technical contributions are: (i) relating the approximation degree of the AND function to the slate size to learn a RUM (Theorem 9 and Theorem 12), (ii) relating the $\\ell_1$-norm of the coefficients to approximate the AND function to the query time of an algorithm for RUM learning (Theorem 9 and Corollary 10), and (iii) deriving, from the lower bound for RUM learning, lower bounds to fractional versions of other well studied problems (Theorem 14 and Theorem 15). The proofs are non-trivial and the techniques we use come from seemingly unrelated areas such as cryptography and Boolean function approximation. We believe that connecting such distant areas to RUM learning is a contribution by itself. In the revision, we will ensure that our contributions are more clearly highlighted. \n\nWe now answer the questions in order:\n\n1. This is an interesting open problem. We currently do not know the optimal slate size that allows for polynomial time simulation algorithms. (We mention this problem in the Conclusions at line 358.) \n\n2. This is an excellent point.  Our problem currently asks for a good approximation on *all* possible slates. It is possible that a PAC-learning variant of the problem (where, say, the testing and/or the learning phases have to use slates coming from a distribution) might be easier, both in terms of running time and slate size. We will mention this as a possible future direction.\n\nRegarding the point of focusing only on the most preferred items. If we consider the task of just estimating the winning probability of the most preferred item, then our lower bound (Theorem 12) answers this in the negative: there is one item for which we cannot say if its winning probability is $\\ge 1-\\epsilon$ or $\\le \\epsilon$ in the full-slate. Thus, the slate size cannot be improved in this context.\n\n3. Thank you for the suggestion and apologies for the lack of details; we will add a rigorous proof in the revision. The high level idea is that, instead of solving the primal LP (1) (that takes $n^{O(n)}$ time), we can solve the dual LP. The separation oracle of the dual can be solved in time $2^{O(n)}$ using an algorithm in [Chierichetti et al., 2023], therefore, employing the ellipsoid method provides the desired running time.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1cgH9KTgYs", "reviewer": "Reviewer_NbMn", "summary": "This paper studies the learning of Random Utility Models (RUMs). A RUM is a probability distribution $P$ over the set of permutations over $[n]$. Fix a permutation $\\pi$ and consider any subset $T \\subseteq [n]$, known as a *slate*. The winner of the slate (corresponding to $\\pi$) is the highest ranked element in $T$ accordint to $\\pi$. We can imagine fixing a slate $T$, and consider the distribution of the winner of the slate $T$ as we draw $\\pi$ from $P$. In the problem of learning RUMs, one is given a set of slates, together with the corresponding distribution of the winner of that slate. The task is to reconstruct the distribution of the winner of every possible slate.\n\nSpecifically, this paper considers the problem when the example slates given to a learning algorithm are at most a size $k$. The main result of the paper is that having access to the winning distributions of all slates of size at most $O(k)$ is necessary and sufficient for the task of learning RUMs. The same result also holds if one has only sample access to the winning distributions of all slates of this size. The authors present two algorithms that achieve the upper bound: 1) a proper algorithm, that constructs a RUM in time $n^{O(n)}$, and thereafter, given any slate, returns an approximation to the winning distribution of that slate in polynomial time 2) an improper algorithm, that does not construct a RUM, but runs in time $n^{O(\\sqrt{n})}$, and thereafter, given any slate, returns an approximation to the winning distribution of that slate in time $2^{O(\\sqrt{n})}$. The latter algorithm thus, in time $n^{O(\\sqrt{n})}$, approximates the winning distribution of the full slate $[n]$ in $l_\\infty$, which is an improvement over the previous best running time of $2^{O(n)}$ for the same task, implicit in prior work. The latter algorithm can also be adapted to yield the following guarantee: given a prespecified slate $T \\subseteq [n]$, one can approximate the winning distribution of $T$ in $l_\\infty$ in time polynomial in $n$, by querying slates of size at most $O(|T|/\\log|T|)$. The authors also show that any algorithm that only accesses slates of size $o(\\sqrt{n})$ can not successfully learn the winning distribution of the full slate. This shows that their earlier two algorithms are optimal in the maximum size of the slates they access. Finally, the authors define fractional versions of two classic problems in the intersection of combinatorics and computer science: $k$-deck and trace reconstruction. Using their techniques for learning RUMs with small slates, they are able to obtain new results for the fractional versions of both these problems (similar quantitative results would be major breakthroughs for the original problems).\n\nThe upper bounds rely crucially on results by Sherstov in 2008, and on the state-of-the-art approximation of the AND function by low degree polynomials due to Huang and Viola, 2022. The lower bound is a reduction to a lower bound on the approximation of the AND function by low-degree polynomials, due to Bogdanov et al. 2016.", "questions": "1) The authors do show in Observation 13 that having access to slates of size exactly $k=\\Theta(\\sqrt{n})$ is also not sufficient for learning the RUM. Might it however be possible that such a result holds for some $k > \\Theta(\\sqrt{n})$? Say I am given all the slates of size exactly $\\Theta(n^{0.6})$?\n\n\n2) Are similar fractional versions of the $k$-deck or trace reconstruction problems known? I suggest doing a literature survey to cite some works that have considered variants of these problems -- this might make these sections more complete and situate your definitions of the problems better within the literature. For example, here are two works I found with a preliminary google search: 1) Approximate Trace Reconstruction from a Single Trace. Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha, 2022 2) Approximate Trace Reconstruction. Sami Davies, Miklos Z. Racz, Cyrus Rashtchian, Benjamin G. Schiffer, 2020.", "limitations": "The authors have satisfactorily addressed the limitations of their work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper considers a natural constrained formulation of the problem of learning RUMs on $n$ elements: algorithms that are only given input access to slates of size at most $k$. For such algorithms, what is the smallest $k$ that is both necessary and sufficient? Satisfyingly, the authors give a compete answer to this question: $k=O(\\sqrt{n})$ is necessary and sufficient. Given the pre-existing technical machinery by Sherstov, 2008, Huang and Viola, 2022 and Bogdanov et al. 2016 (albeit for problems not directly related to learning RUMs), the connections to RUMs are not too difficult to read and understand, and I found them innovative and cute. I also liked the applications of the the authors' techniques to obtain novel bounds for relaxed versions of classical hard problems in computer science. While I am not closely familiar with the literature on these problems, I imagine the fractional definitions of these problems given by the authors, together with their bounds, might be of interest to people who study these problems. Overall, I find the authors' work to be a strong and compelling study.", "weaknesses": "If I am to nitpick: while the technical narration of the problem of learning RUMs given by the authors is clear (I admit that I did not even know this problem before reading the paper, but could understand almost all of the paper), I would have liked to see a little more story-building and motivation around this problem in the introduction. I felt that the authors dived into their technical contributions rather too soon. I would also have liked to see the authors elaborate more on how their work compares to prior work by Chierichetti et al. 2021, 2023. As of now, these works, while seeming to be most relevant, are only cited in passing in the related work. Also, I feel that a few more references could be provided with respect to variations of the $k$-deck and trace reconstruction problems that have been considered in the literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestions and feedback.  In the revision, we will provide more story-building and motivation around the problem. \n\nRegarding related works on RUMs, in [Chierichetti et al., ICML 2021] they take in input a RUM $R$ and their goal is to output a new RUM $R’$ whose support is only on a linear number of permutations, while maintaining a good approximation of $R$. Therefore, they consider a lossy-compression problem rather than a learning problem, as we do instead.\nIn [Chierichetti et al., AISTATS, 2023], they take in input the empirical winning distributions of small slates and their goal is to output a RUM consistent with such input slates. Crucially, they do not require their RUM to work well on slates outside of the input set. Instead, we consider a learning problem where the algorithms must provide good approximations on all the slates, even the large ones not given in input.  We will clarify these better in the revision.\n\nWe now address the questions:\n\n1. Unfortunately, the answer is no.  Having access to all and only the slates of size exactly $O(n^c)$ for any constant $0<c<1$ is not sufficient to reconstruct the winning distribution on the full slate. In particular, Observation 13 entails that access to slates of size $O(\\epsilon \\cdot n)$ leads to an $\\ell_1$-error of at least $1 - \\epsilon$ on the full slate. Therefore, selecting $\\epsilon = n^{c-1}$ yields the claim. We will mention this in the revision.\n\n2. Thanks for your suggestion and the references; we will mention some variations of the problems to better situate our work in the literature.  \n\nBoth papers you mentioned, [Chen et al., 2022] and [Davies et al., 2020], fall into the literature of approximate trace reconstruction. In such variation, one seeks to approximately reconstruct the single hidden string $x$, up to some error in edit distance. In our version we have instead a hidden distribution over strings, rather than a fixed string.\n\nSome results of the first paper you mentioned, [Chen et al., 2022], consider the average-case trace reconstruction. The works in this literature are maybe the most related to our version. However, our problem differs from such variations in two aspects. 1) in average-case trace reconstruction the hidden string is sampled from a uniform distribution, instead, we consider arbitrary distributions, and 2) in average-case trace reconstruction, one first samples a string $x$ and then each trace is obtained by running the same string $x$ through the deletion channel. Instead, in our fractional trace reconstruction, to collect a new trace we first sample a new string $x$ and then run it through the deletion channel. Note that the average-case trace reconstruction is not a generalization of trace-reconstruction, while our fractional trace-reconstruction is a true generalization.\n\nWe will add these comments in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their insights, and the time and efforts spent reviewing our work. We consider each comment carefully below, but let us begin by addressing a common concern regarding the computational complexity. While the asymptotic complexity of the algorithms is high, there are some interesting special cases for which the algorithms are practical.

1. Our learning algorithm is able to infer the winning distributions of slates up to size $\sim k^2$ by looking at the $\sim n^k$ slates of size at most $k$. For moderate values of $k$, e.g., constant $k$, this algorithm is practical and is a significant improvement over the trivial $\sim n^{k^2}$ algorithm. 

2. For modest values of $n$, e.g., learn the winning distributions over the $n$ restaurants in a town, our algorithm only requires $\sim 2^{\sqrt{n} \lg n}$ queries to approximate the full-slate, while the previous best algorithm needs $\sim 2^{n}$ queries.

In general, we view our results as the necessary first steps towards understanding the learnability of RUMs, which has been a long-standing research question.

Since the CFP welcomes “Theory” contributions in “learning theory”, we hope that the theoretical nature of our contribution will not be seen as a limitation.

Meta-review: This paper has developed very strong results for the problem of learning RUMs. The improvement relative to previous work is enormous, improving the order of $n$ in the exponent itself, along with matching lower bounds. The analysis is technically sophisticated and interesting, connecting to boolean function analysis and polynomial approximation. This paper has very strong support from two reviewers and less support from two lower-confidence reviewers.  One criticism from several reviewers is the exponential complexity, but the authors have shown that this is unavoidable and hence I do not find that this should be viewed as a weakness. Another criticism that came out during the discussion period with the reviewers is that the paper uses an existing connection with boolean function analysis and polynomial approximation; however, I am not convinced that this is a valid criticism since (as noted by another reviewer) boolean function analysis and polynomial approximation are entire fields of study. It does seem that some heavy lifting is done by the prior work of Sherstov (2008), but finding these connections and the authors' own analysis looks impressive. This work is a welcome addition to the proceedings.
Decision: Accept (poster)