Product Distribution Learning with Imperfect Advice
Authors: Arnab Bhattacharyya
Davin Choo
Philips George John
Themis Gouleakis
Venue: NeurIPS 2025 spotlight ()
Keywords: distribution learning
statistics
algorithms
sample complexity
Primary area: theory
TL;DR: Product distributions on n dimensions can be learned with sublinear samples if a sufficiently close distribution is provided as advice.

Abstract: Given i.i.d.~samples from an unknown distribution $P$, the goal of distribution learning is to recover the parameters of a distribution that is close to $P$. When $P$ belongs to the class of product distributions on the Boolean hypercube $\{0,1\}^d$, it is known that $\Omega(d/\epsilon^2)$ samples are necessary to learn $P$ within total variation (TV) distance $\epsilon$. We revisit this problem when the learner is also given as advice the parameters of a product distribution $Q$. We show that there is an efficient algorithm to learn $P$ within TV distance $\epsilon$ that has sample complexity $\tilde{O}(d^{1-\eta}/\epsilon^2)$, if $\|\mathbf{p} - \mathbf{q}\|_1<\epsilon d^{0.5 - \Omega(\eta)}$. Here, $\mathbf{p}$ and $\mathbf{q}$ are the mean vectors of $P$ and $Q$ respectively, and no bound on $\|\mathbf{p} - \mathbf{q}\|_1$ is known to the algorithm a priori.

Product distribution learning with imperfect advice
Arnab Bhattacharyya Department of Computer Science
University of Warwick
arnab. hhw.aaacchhrrraaaarriii......
Davin Choo
Harvard John A. Paulson School Of Engineering And Applied Sciences
Harvard University
davinchoo@seas.. harvardd www.ahoooeeaaaaaaaa.eeeeee...
edu
Philips George John
Themis Gouleakis
CNRS@ CRRATC & Dept. of Computer Science National University of Singapore
College of Computing & Data Science Nanyang Technological University themis chemis.gouleaki edu. sg
philips.geors george..g.....o george.john@u john@u. nus edu
Abstract
Given i.i.d. samples from an unknown distribution P. the goal of distribution learning is to recover the parameters of distribution that is close to P. When P belongs to the class product distributions on the Boolean hypercube {0, 1]dd, it is known that ((d/e²) samples necessary leam P within total variation (TV) distance c. We revisit this problem when the learner is also given as advice the parameters of product distribution Q. We show that there is efficient algorithm to leamn P within TV distance that has sample complexity O(d' /E?), if ||p q/ı1 3--00)) Here, p and q the mean vectors of P and respectively, and no bound on ||p q//a is known to the algorithm a priori.
Introduction
Science fundamentally relies on the ability to learn models from data. many real-world settings, the majority of available datasets consist of unlabeled examples sample points drawn without correspouding labels, outputs or classifications. These unlabeled datascts are often modeled as samples from joint probability distribution
large domain. The goal of distribution learning is to output the description a distribution that approximates the underlying distribution that generated the observed samples. See [Dia16] for comprehensive survey.
In practice, distribution learning rarely occurs isolation. While a given dataset may new, one often has access to previously learned models from related datasets. Alternatively, the data may arise from an evolving process, motivating current inference. This prior information can be viewed some kind. In the framework of algorithms with predictions, the objective is to integrate such advice in way that improves performance when the advice is accurate, while ensuring robustness: performance should not degrade beyond that an advice- free baseline algorithm, even when the predictions are inaccurate. Most previous works in this setting in the context of online algorithms, e.g. for the ski-rental problem [GP19 WLW20 ADJ+ non-clairvoyant scheduling [PSK18], scheduling (20 BMRS20 AJS22 augmenting classical data structures with predictions (e.g. indexing KBC 18 and Bloom filters Mit ) online selection and matching problems (AGKK20)
reuse of information from past learning to guide
form of "advice" "prediction" of
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

DLPLV21 CGLB24 CJS25], online TSP BLMS 22 GLS23 and a more general framework of online primal-dual algorithms [BM220]
However, there have been some recent applications to other areas, e.g. graph algorithms CSVV22 21L causal learning [CGB23) mechanism design
[KKST22 ABG 22], and most relevantly to us, distribution learning (BCGG25).
In this work, we study the problem of learning product distributions over the d-dimensional Boolean hypercube {0, 13d, arguably one of the most fundamental classes of discrete high-dimensional distributions. A product distribution P is fully specified by its mean vector p [0. 1]" where the i-th coordinate p; represents the expectation of the i-th marginal of P. or equivalently, the probability that the i-th coordinate of sample from P is 1. It is well-known that (dd/s²) samples from a product distribution P are both necessary and sufficient learn a distribution Puuch that drv (P, P) S with probability at least 2/3, where drv denotes the total variation distance. This optimal sample complexity achieved by a simple, natural and efficient algorithm: computing the empirical mean of each coordinate. Motivated by the framework of algorithms with predictions, we investigate whether this sample complexity can be improved when, in addition to samples from P. the learner is given an advice mean vector q E [0, 1]s. Importantly, P. However, if we can detect that q is accurate - i.c., that ||q - pll is small in an appropriate norm can this information be leveraged to constrain the search space and improve sample or computational efficiency? Our goal is to design algorithms that adapt to the quality of the advice: performing better when q is accurate, while remaining robust when it is not.
make assumption that q is close to the true mean
Our main result establishes that this is indeed possible. Specifically, we show that if [|q-ppli < e ev then there exists polynomial-ting algorithm with sample complexity sublinear that outputs a distribution P such that drv (P. P) I & with probability at least 2/3. More precisely, under the regularity condition that no coordinate of P is too close to deterministic (i.e., bounded away from 0 and 1), we show that the sample complexity is:
δ d d (a=t min
||P d g2
for any small enough constant 1). In particular, when ||p Ip-qqe Fllp is small, the dependence on d becomes sublinear. We also prove that the non-determinism assumption is necessary: if coordinates of P can be arbitrarily close to 1, then sample complexity that is sublinear in d is impossible, even when l|q - pll: O()). Furthermore, we show that when ||q pll > evdd, no algorithm with sublinear sample complexity exists.
1.1 Technical Overview
We call product distribution P balanced if no marginal of P is too biased. That is, each coordinate of p is bounded away from O and 1. It is known that, for balanced distributions, learning P in TV distance is equivalent to learning the mean vector p with ez-error. Hence, in this overview, we focus on the latter task.
To build intuition about how an advice vector q can be exploited, consider the following two situations:
1. Exact advice:
Suppose q = p. Then, it suffices to verify that | pplp S and learning algorithm can simply return q. This is the classic identity testing problem, which has been extensively studied (see (Can20) for a detailed survey). For product distributions, Daskalakis and Pan (DP17) and Canonne, Diakonikolas, Kane and Stewart (CDKS17] independently showed that identity testing requires ((vd/=²) samples. This demonstrates that sublinear sample complexity is achievable when q p. Morever, ((vd/= is fundamental lower bound that applies even when q = p.
2. Sparse disagreement: Suppose q differs from p in at most coordinates, i.e. ||q-pli S t. In this case, one only needs to estimate on those t coordinates, so the informmtion-thhoreee sample complexity should scale as ~ log (:)) Unfortunately, since t is unknown a priori, we cannot directly exploit this sparsity. However, from the compressive sensing literature, it is known that closeness in & norm to a f-sparse vector can be certified by a small & norm (e.g., Theorem 2.5 of [F13)).
Motivated by the above, we take the quality of the advice q to be governed by the ddsittance |pp - qlla, and aim for an algorithm whose sample complexity improves this distance decreases.

---

Suppose we can certify that l|p - -ll1 I A. Then, we may restrict attention to the f1-ball of radius centered at q, and cover it with N Ez-balls of radius E, where the covering number N grows polynomially as do(A2)=)) It is known (e.g. see Chapter 4 of [DLOT] that using the Scheffé tournament method, the sample complexity of learning p up to fy-norm scales as (log N)
which yields bound of O 2 log d). While the Scheffé tournament is computationally inefficient, the same sample complexity guarantee can be achieved efficiently by solving constrained least squares problem. More precisely, given samples X1 Xn from P. we consider the estimator:
argmin
Σ
||x - b
bER b- SA
For n = 0(X log d), this estimates achieves 2--error at most E.
The key challenge that remains is then to approximate X x ||p 1qll using a sublinear number
of samples from P. To this end, we devise a new identity testing algorithm that, using O(vd/s?) samples, either (i) 2-approximates ||p 4ll2. or (ii) certifies that |p alle S E, in which we
simply return q. If we are in case (i), we can upper bound ||p - allb with x = ||p - all2 Vd.
However, this would make the sample complexity of the learning algorithm be O (?e logd)
O ( (dlogdd-]pp-alll > _ i.e., exceeding the standard Odde²²) bound and defeating the purpose.
To improve upon this, we can partition the d coordinates into d/k k blocks of size each. Then, within each block, the ratio between the & and & norms improves from v to Vk. By appropriately choosing k we can obtain non-trivial reduction in overall sample complexity.
The structure of our algorithm described above and its analysis parallels the recent work by (BCGG25), which addresses the problem of learning Gaussian distributions with imperfect advice. However, our setting differs in several important ways:
BCGG25 used well-known algorithm approximate the & norm of Gaussian's 's mean vector. In contrast, our (2-approximation algorithm for product distribution is new, to the best of our knowledge.
We critically rely on the balancedness assumption to relate total variation distance and l error the mean vector. No such assumption is needed in the Gaussian setting. In fact, we show that for product distributions, balancedness is essential: without it, no sublinear-sample algorithm exists, even when the advice vector is ((1)-llose to the truth in l distance. We find this somewhat surprising since O ((V//22) samples suffice without any balancedness assumptions in identity testing (DP17 CDKS17).
2 Preliminaries
distribution P on {0, 13dd said be a product distribution if there exist distributions Pi...., Pa on {0. 1} such that P(x)= = P1 (21) P2(x22 Pa(aa) for every {0, 1] In this case, we can write P = P1 @ P2... 8 Pa.
Definition 2.1 (Mean vectors). The mean vector of a distribution Pis p - E,- (x]. In particular, if P= P1 < ... 36 Pa is product distribution, p [p1 Pa). where pt = (.).).
For a vector p E [0, 1] we denote by Ber(p) the product distribution with mean vector We next define the notion of balancedness.
Definition 2.2. For 7 E [0. 1/2], a product distribution P {0, 1)d is said to be r-balanced if for every i E [d], the marginal P, satisfies 7 - P1(1) 1---
Proposition 2.3 (c.g.. (CDKSI7, Lemma 1). Suppose P Pand Q are T-balanced product distributions on (0, 1)dd with mean vectors p and respectively. Then their KL. divergence dRL (PI(() satisfies:
2 p ali < dPll()llQ) <
912
Proposition 2.4. Suppose P and Q are r-balanced product distributions on {0, with mean vectors p and q respectively. Then, for some constant e < 0.2, the TV distance drv (P, P,, Q) satisfies:
1
c. min ||p al12) s &dr (P,Q)= < V= |lp 9/22-
3

---

Proof. The first inquality is the main result of [Kon25] The second inequality follows from applying Pinsker to the upper bound on dgi. Proposition 2.3
Note that the dependence on 7 above is necessary (up to constant factors). For example, suppose P Bcr(O) and Q Ber(u) where the all-zero vector and u [ d) Then,
|00 - 2 = 1/vd, while drv(P, 2 P(O) - Q(0) = 1 - (1 1/dy* x - 1//ee.
3 Algorithm
The goal of this section is to establish the following result.
Theorem 3.1. There exists algorithm TESTANDOPTUMMEEEENN that for any given E, ò, E (0, 1),
7 2 O, and q E [0, 11 and sample access to T-balanced product distribution Ber(p) {0. 1)",
draws n. 0 (5 (d-" + min (1, (p, q, d. m,,))) i..d. samples from Ber(p), where:
P 9
f(p. q, d, 1),)) = d 26
The algorithm produces as output P in poly(n, d) time such that (rv(Br((p) Ber(p)) I 8 with success probability at least 1- 8.
basic component of the algorithm a test to determine how close the advice q is the true p in fz norm.
Lemma 3.2 (Tolerant mean tester). Given
8 (0, 1). d sufficiently large integer, and E [0, 11s, there is tolerant tester TMT that uses O ( Idd 2x log (t) i..d. samples from Ber(p) and
satisfies both conditions below with probability at least 1 - 5:
1. If llp 4/l2 S e, then the tester outputs Accept
2. If |pp all2 2 2e, then the tester outputs Reject
Proof. Notice that if Σp: Eg = 1, we could interpret .i..... Pa and gl...., Qa distributions P and q on [d] that sample [d] with probability p; and qi respectively. Diakonikolas and Kane DK showed that using (11lpl12/e samples from p. one can test whether ||p ålle S ε or 9 2 2E. Inspired by this observation, we mimic the analysis of [DK16] to devise a tolcrant tester for general product distributions.
Assume the desired failure probability be 1/3; we can reduce to any ô by repeating the test O(log 1/5) times and taking the majority vote. Set m = cvdde² for a large enough constant c, and let m, be sampled independently from Poi(mn for each i E [d]. Note that max; S 2em with high probability; we condition on this event and set the desired failure probability to 1/4. Therefore, using 2em samples from (er(p), for each i, we can obtain m, samples from the ith coordinate, and let X; be the number of times the i' I'th coordinate is sampled to be 1. Note that by standard properties of the Poisson distribution, the X1,... Xd are independent and each X; is sampled from Poi(mp:).
Define the statistic 7 Ed d i== Zi, where:
Z4 (X; mq:)² ) X
Using similar calculations as in [K16), we can show that:
E E m² ) and
BiZ] m² 911.-
Also, we can calculate the variance to be:
Var Z
4m
Ep(r. - ----)))2200 + 2m Σ
4m ps <
4m |pl|||l allā + 2m 1pl2.
where the inequality is by Cauchy-Schwar
If 1lppppap 4/|2 < E. then E|Z] dd//22 and Varlz] (4c² + 222 On the other hand, it always
holds that E[2] > ddlpp
/t and Varlz] < dd. (11l1ll - + 22cdd] <
|p (4c²
q / 2e wd hdf/// /sa, since ||l||2 & vd. Using Chebyshev's inequality, if is large enough,
when 1p g S. e. is at most 2c- d/e2 with probability 3/4, but when ||p q/|2 2 2s, Z is at
least 3c d/= with probability 3/4.
D

---

Algorithm The APPROXL1 algorithm.
Input: Block size k [d], lower bound O, upper bound 2a, failure rate (0, 1).
advice q E [0, 1] and i..d. samples & (multiset) from Ber(p).
2: Output: Fail or X E IR
3: Define [d/k] and 8' an luga </al
4: Partition the index set [d] into w blocks:
B = (I....,,k)) k), B2 (k: 1, 1,...,,........... .k...,,k....... .k...... B [k(w - 1) 1.......
5: for (l...., w). do
6:
Define multiset Sj
(xB,
BI E S) as the samples projected to Bj
7:
Let QB, |31 be the vector q projected to coordinates B,.
8:
Initialize 0j Fail
9:
for 1,
Define 4 = 2 [log2 </o]] do
10:
11:
Let Outcome be the output of the tolerant tester TMT of Lemma 3.2 using sample set Sj
12:
with parameters +- 4,, 8', d t [B] and q +- qB, Outcome is Accept then
13:
14:
Set 0, and break (Escape inner loop for block j) 15: end if
end for
17: end for
18: if there exists Fail amongst {ol,.... 0w) then
19: return Fail
else
21:
return À = 2 V B,] oj {} is an estimate for ||p -q/l1}
22:
end if'
Lemma 3.3. Let k. and ( be the inpul parameters to the APPROXL. algorithm. Given [0, 1j
and m(k, 8) [16//1 (1+ [log 12w-log,[[/0 [C/a]]
i.i.d. samples from Ber(p), APPROXLI
succeeds with probability at least 1 and has the following properties:
Property 1: If APPROXL1 outputs Fail, then [|p ql|2 > C/2.
Property 2: APPROXL1 outputs À IR then |p qll S (Id/k) a + 2/Ip 9ll1).
Proof. We begin by stating some properties of o1..... Ow- Fix an arbitrary index j E {l..... w)
and suppose 0j is not a Fail, i.e. the tolerant tester of Lemma 3.2 outputs Accept for some 21, .... [log2 [/a]}. Note that APPROXLI sets 0j 4. and the tester outputs Reject for all smaller indices
{l.....
1}. Since the tester outputs Accept for i", we have that ||PB,
qB, ll2 < 2 20y. Meanwhile, if i* 1, then [PPB, QB, l1, f 4-- /2 o, /2 since the tester outputs Reject for 1" - 1. Thus, we see that
When 0j is not Fail, we have [IPB, -qB ll S 20,-
When |/PB, qB, l2 I 20: we have i" and 0g = (1 = a.
When |PB, qB, l2 2a 261, we have i > 1 and o, < 2 <2|PB, qB, 112-
Success probability. Fix an arbitrary index (1,2, ...,..., flgg </a]) with 2 where 4 < f for any i. We invoke the tolerant tester with l in the th invocation, the 5th invocation uses at most mi mi(k,, 5, 6) & nk,s Tá i.idd. samples to succeed with probability at least and ra 1 [ogg(2/6))]
16VE 1 - 6, where n4_= - 32
So. with at most m(k, a. A my (k, 8') = n4a T8 samples, any call to the tolerant tester succeeds with probability at least -- 6', where 8' ing C/a By construction. there will be at most w [log, [/a] calls to the tolerant tester. Therefore, by union bound, all calls the tolerant tester jointly succeed with probability at least 8.
8

---

Proof of Property 1. When APPROXL outputs Fail, there exists Fail amongst foi..... )w) For any fixed index j [l,..., w/. this can only happen when all calls the tolerant tester outputs Reject. This means that | la > 81 & 2'-1, a for all i E {1,2,.... ...,, floge {/a]). In particular, this means that TB la 2/2.
Proof of Property 2. as follows:
When APPROXL outputs 2 B₁ O5 E E, we can lower bound
PB,
qB,lL2
A = 2
Bj Oj 2 2
Byl
(since |p, qn,ll2 S 20,)
2
1=1
f=1
2
PB, qB,
ll
(since |PB, 4B, 11 S /B] IPB, qB, 122
1=1
pp
rll
(since Σj IPB, qB, 11
PBB qB 11
That is, A 2 1p- 4/11- Meanwhile, also upper bound À follows:
=
Byl oj < 22
0j
(since [By k)
10
W
=2
Σ
Σ
Oj
Oj
j=1 (lpB, -0, S2
IIP
92,
112>20
(partitioning the blocks based on |PB,
QB, 2l2 versus 2a)
=
Σ
Σ
Oj
j=1
[|pB, QB, S2a
[IPB, -QB, 1l >2a
(since
||PB,
qB, lla s 2a implies 05 = a)
w
$ 2vk.
Σ
Σ j=1
2|[BB, - qB,Bl2
IIpn j=1 (since
Saa
Ilpn qn, >>
[BB
QB, lll 2a implies 0f s 2|[PB,
Σ
2+2
Σ
Pn, qn, |||
|IpB, -BB, 1252a
PB, qn, ||a>
(since
[PB
qB 112 < |BB,
QB, |11)
< 2Vk -
[d/k] +2
PB, qB, l11
j=1
[PB, qB, >>>>20
(since { E [w] Pn, ||2 2axH| S w)
< 2vk- (Id/k)
+ +121pp 9/11)
(since Σ
PB, - QB, 111 $ Σ |PB, QB, ||1 = ||BB, qB, 1l
j=1
lpn; qn, >>>
That is, 2/T ([d/k] a 2/pp q ). The property follows by putting together both bounds.
D

---

Now, suppose APPROXL1 I tells us that ||p - qlla r. We can then perform a constrained LASSO to search for candidate [0, 1]d using O log ()) samples from Ber(p).
Lemma 3.4. Fix 1, 2 0, E O, and q E [0, 11 Given O log )) samples from Ber(p)
for some unknown p E [0, 1f with ||p qllı S T, one can produce an estimate p [0, 1]4 in
poly(n, d) time such that |p pll2 with success probability at least - 6.
Proof. Suppose we get n samples Yı,.... .n ~ Ber(p). For i E [n]. we can re-express each y; as Y: = + + 2; for some 2; distributed as Ber(p) p. Let us define p E [o, 1]d as follows:
p argmin
yi bl2
(1)
By optimality of in Equation
1 have
ly,
111
ll: pl12
(2)
1=1
2=1
By expanding and rearranging Equation
2b. one can show:
n I Σ
pp pl
Z. P
Meanwhile, a standard Chernoff bound shows that Pr
Σ 2:l1z0 2 2n log 2d
S 6. There-
fore, using Hölder's inequality and triangle inequality with the above, we see that, with probability least 1 - 5,
2 P
2
B P
2,
p)
Σ
2
|1 - pll1
7
n
:=1
i=1
2
Σ
Zi
(II all + - i
2 log
(2d)
4r
Finally, it is known that LASSO runs in poly(n, d) time.
Using Lemma 3.4 we now ready to prove Theorem 3.1
Proof of Theorem 3.7 Correctness of p output. TESTANDOPTIMIZEEENN (Algorithm 2 has two possible outputs for p:
Case 1: argmin lb sllis En ly. bll which can only happen when Outcome E TR
and X < eVd
Case 2: p= Σn
Conditioned APPROXL1 succeeding, with probability at least 1 5, will show that drv (Ber(p). Ber(p)) < & and failure probability at most in each of these cases, which implies the theorem statement.
Case Using r = as the upper bound, Lemma 3.4 tells us that || plla S a 7(1 - with failure probability most when Õ(x² ((22))204) i.i.d. samples are used. Using Proposition 2.4 drv (rrv(Brr()) (p), Ber (p) E.
Case 2: With Ōdde22) samples, is known that the empirical mean p achieves dry (Ber()),)), (p)( < with failure probability most 6.
7

---

Algorithm 2 The TESTANDOPTIMIZEMEAN algorithm.
1: Input: Error rate E > 0, failure rate 8 E (0, 1), parameter 17 E [0, 11. parameter T E [0, 2 and
sample access to Ber(p)
2: Output: p E IRd
3: Define k ==mnn(d""/>1)
(T 48 Vd, and 8' Ta/ </a
6
4: Draw O(vk log(1/"")/aa) ii.d. samples from Ber(p) and store it into a set S
5: Let Outcome be the output the APPROXLI algorithm given k. a, ç, and as inputs
6: if Outcome is À E R and X evd then
7: Draw E O(>3/=*) ii.d. samples y .I..... Yn [0,
8: return p = jr sllis Ei=ll b -
9:
else
10:
Draw E O(d/8²) i..d. samples Yn.... E 10,
11: return p = Ei= Yr (Empirical mean)
12:
end if
Sample complexity used. APPROXLI uses |S| a E Ö(Vk/a²) samples to pro- duce Outcome. Then, APPROXLI further uses 0(22/126)) samples O(d/a²) samples de- pending on whether X < evd. So, TESTANDOPTMIZEMEAN has total sample complex-
ity of Ô L + min
Xa : .. Mcanwhile, Lemma 3.3 states that |lp all1 S s
2vK ([d/k] a + 2|Ip- alli) whenever Outcome is R. Since (a + 6)²² S 2a² + 26
12 for any two real numbers a, b we see that सिद E 0
Po R llp all S
o ( 2x
x-llp-llli) =
Putting together the above observations, we see that the total
de
sample complexity is
v a
d +
da²
6-Ilp- all
}
-min
c2,2k +
E²
dr dr
Recalling that TESTANNOPTIMIZEMEAN sets k min([dta (ddtaa-daa,a above expression simplifies to θ
$1, d) and a ed 133 the 1p-P1
4 (d + min (I, 7 6n
4 Lower Bounds
For proving of our lower bounds, we use the following corollary of Fano's inequality. Lemma 4.1 (Lemma 6.1 of [ABDH* 201). Let k R be a function and let F be a class of distributions such that, for all > O, there exist distributions f1,..., E F such that
dKa. (Ji, fi) S x(E) and drv ( [f) > 2s Vi f j E [M]
Then any method that learns FF within total variation distance e with probability 2/3 has sample complexity St log M
log(//
Lemma 4.2 (Learning unbalanced distributions requires linear samples). Suppose is sufficiently small, and we are given sample access to a product distribution Ber(p) on {0, 1] with mean vector having entries which are (11/d), along with advice mean vector q such that ||p qlli S O(e). Even in this case, learning D such that drv (Ber()),Ber(p))
requires ÿ (1) samples
Proof. Suppose that the advice distribution Ber(q) has mean vector q [ S C [d]. define ps E 1d with ps[i] llss allp { for all S [d. Also, for all S,T C [d] we have drv (Ber(ps))) Ber(pr)) 2 [
-. 2s if i E S and & otherwise. Then, we have d
Pr.-:Ber(ps) (ISS = 0) Pr PrawBer(px (ΛSTT = 0)] = (1 15/7 (1 5) 2
I d
this using the inequalities (1 =²"" 2 - ræ for r E {0) [1,
142
BUTE

---

x I 1, and (1 - 2) 1 the set T S, we get drv(Ber(ps), Ber(pT)) 2 1 |nS drv (rv(BBe(ps). Ber(pT)) 2 (877)) g
1 for r 2 0, x E (-1/r.1). Using the same argument with Itr
142 142 Thus, we have
1- (s+ 1-(s+
1
Note that, by calculation, we can
142E
show that - -05 ( Similarly, we have dKL (Ber(ps) )| (PT))) = EiE(a) kl([psl (Prk) = Exesy kl 2 9) Eierys kl 2)) (where kl(p. q) - dkg (Ber(p))[Ber(()) We can see by simple calculations along
1 I+22 2 5/2 - 5- for { 2 0, which is 22(5) for 5 E (0,1/4).
with the logarithmic inequality In (1) S for r > -1, that kl( 2) S 5 (02) + カ-23 S
0.5g (for d 2 10 and 5 S 1), and kl 7 5) < 1l - 1 X-z)
S d (for d 2 10 and S 1).
0.5
d
Thus dKL. (Ber Ps) (er(pr)) S 2a (1S) 7| - [7 S) = 2d
|
Viewing sets S S [d] as vectors in Fý and using the Gilbert-Varshamer Varshamov bound, we can say that, for any constant c E (0, 1) and sufficiently large d, there exists a family of sets {Si...., S S 2/d] with M 2 20(ed) such that [S;] = ed and |S; @ S,1 2 o for all i,j E [M]. We use this family to instantiate distributions Ji A Ber(ps,) for each i [M].
Suppose we take S = S;, T = Sj, with |S| = [T] = cd and |S @ T| E [ed 2nd]. so that I |SeT| S c for all i E [M]. Since J.S. @ S,I 2 ed/4, we will have least one of 2d
H {S T.T $} with H E cd]. Thus, we will have He d E [ . CE| (()) (for constant > 0), and drv (fi, 2 (2)) (supposing cs < 1/4).
By appropriately scaling & and applying Lemma 4.1 we can show that we need ś (3) samples to learn a product distribution f = Ber (ps-) E ........MM.. to within e in TV distance, even when given advice q with ||ps- - allb E, if the distribution mean vector ps- are allowed to be unbalanced (specifically, with entries S O(1/)).
We also prove a sample complexity lower bound for learning product distributions balanced case given advice, which adapts the sample complexity lower bound in ([BCGG25), Lemma 32) for learning multivariate isotropic gaussians N(u,", Ia) given an advice vector which is close to the true mean vector in & distance.
Lemma 4.3. Let > 0 be suffiiinnlly small. Suppose that we are given sample access to a distribution Ber(p) where p is h-balanced, and also an advice vector q with 1|p uap-qa -ll1 Z 100a. Then, any algorithm that learns Ber(p) up to distance in total variation with constant failure probability requires 9 (min {Ilp- 90---12 /li/e" ee/ d/e²)) samples. In particular, when ||p 1111 evd, we need O(d/s²) samples.
Proof. Suppose we want ||p q/11 = A for À sufficiently small. Fix q 1 = Ps for some S S [d] with |S| = ke such that ps[i]
1 and suppose
1 + for e S and = otherwise. Then ||ps q/l1 = À and ||ps Prl12 2/4 / STT. If 1. the distributions ps are balanced for r - In that case, for any 5, T [d]. we can bound dKI. (BBe(ps)[[Ber(PP)))) S
8
S + Tl (by Proposition 2.3 and the total variation distance by dry Ber(q)) 2 Q min L. A (AVSSTT (Proposition 2.4
As in (BCGG25). Lemma 32), we consider (Si,.... Sas) } and take Pa A Ps, for a family of k- subsets with M 2 20)()) and |S, 4 Syl 2 k/4 for all i * j. known exist via the Gilbert- Varsshmmy bound. We can do this as long as, e.g. h 2 10. This gives dKl (Ber(p:))[ is function of e) and drv Ber (p;)) 2 C long A 1.
< 16X²
k (where À
2VR
If we choose A = - 2 100 such that > evi 2v1. we will get pairwise TV 2 cs/2 and pairwise KL < 16s < O(E²). Finally, scaling before applying Lemma 4.1 gives the result. D

---

5 Conclusion
This work introduces an efficient algorithm for learning product distributions on the Boolean hyper- cube when provided with an imperfect advice distribution. The sample complexity of this algorithm O(d--v/s") under specific conditions on the advice quality and "balancedness" assumption on the true distribution. Note that the algorithm's 's sample complexity becomes sublinear in the dimension if the advice is sufficiently accurate, and it remains robust even with poor advice. Key to this is a novel tolerant mean tester and techniques for approximating the fı-distance between the true and advice distributions. Future research could extend this learning-with-advie framework to other complex models like Bayesian networks and Ising models, aiming to understand how structural properties of these models interact with advice quality. would also interesting to investigate advice can improve the sample complexity of learning an unstructured distribution over discrete domain [rx] compared to the classical upper bound of O ( samples.
Acknowledgments and Disclosure of Funding
PGJ's research is supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. TG's research is supported by start up grant at Nanyang Technological University.
References
[0 Hassan Ashtiani, Shai Ben-David, Nicholas J. A. Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. J. ACM, 67(6), oct 2020.
[ABG+22] Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning-augmented mechanism design: Leveraging predictions for facility location. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 497-528, 2022.
[0D]+20] Spyros Angelopoulos, Christoph Dür,, Shendan Jin, Shahin Kamali, and Marc Renault. Online Computation with Untrusted Advice. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl--Leinniz-zeee Informatik, 2020.
für
[AGKK20] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems, 33:7933-7944, 2020.
[AJS22] Antonios Antoniadis, Peyman Jabbarzade, and Golnoosh Shahkarami. A Novel Predic- tion Setup for Online Speed-Scaling. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Schloss Dagssuhl-Leibniizzeentuu für Informatik, 2022.
[BCGG25) Arab Bhattacharyya, Davin Choo, Philips George John, and Themis Gouleakis. Learning multivariate gaussians with imperfect advice. International Conference on Machine Learning (ICML), 2025.
[BLMS+22] Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamell Nicole Megow, Leen Stougie, and Michelle Sweering. A Universal Error Measure for Input Predictions Applied to Online Graph Problems. In Advances in Neural Information Processing Systems, 2022.
[BMRS20] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning Augmented Energy Minimization via Speed Scaling. Advances Neural Information Processing Systems, 33:15350-15335 2020.
[BMS20] Etienne Bamas, Andreas Maggiori, and Ola Svensson. The Primal-Dual method for Learning Augmented Algorithms. Advances in Neural Information Processing Systems, 33:20083-20088 2,03,,000,,22000 2020.
10

---

[Can20] Clément L Canonne. A survey on distribution testing: Your data is big. but is it blue? Theory of Computing, pages 1-100, 2020.
[CDKS17] Clément L Canonne, Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Testing PMLR, 2017.
bayesian networks. In Conference on Learning Theory, pages
[CGB23) Davin Choo, Themistoklis Gouleakis, and Arnab Bhattacharyya. Active causal structure learning with advice. In International Conference on Machine Learning, pages 5838- 5867. PMLR, 2023.
[CGLB24) Davin Choo, Themistoklis Gouleakis, Chun Kai Ling, and Arnab Bhattacharyya. Online bipartite matching with imperfect advice. In International Conference on Machine Learning. PMLR, 2024.
[CJS25) Davin Choo, Billy Jin, and Yongho Shin. tional matching. Conference on Neural Information Processing Systems (NeurIPS), 2025.
online bipartite frac-
[CSVZ22] Justin Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pages 3583-3602. PMLR, 2022.
[Dia16] Ilias Diakonikolas. Learning structured distributions. Handbook of Big Data, 267:10- 1201, 2016.
[DIL+ Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassil- vitskii. Faster matchings via learned duals. Advances in neural information processing 34ttem9
2021.
[DK16] Ilias Diakonikolas and Daniel M Kane. A new approach for testing properties of discrete distributions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 685-694. IEEE, 2016.
[DL01] Luc Devroye and Gábor Lugosi. Combinatorial methods in density estimation. Springer Science & Business Media, 2001.
[DLPLV2]] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secre- taries with Advice. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 409-429, 2021.
[DP17] Constantinos Daskalakis and Qinxuan Pan. Square hellinger subadditivity for bayesian networks and its applications to identity testing. In Conference on Learning Theory, pages 697-703. PMLR, 2017.
[FR13] Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Birkhäuser Basel, 2013.
[GKST22) Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan. Improved price of anarchy via predictions. In Proceedings of the 23rd ACM Conference Economics and Computation, pages 529-557, 2022.
[GLS23] Themis Gouleakis, Konstantinos Lakis, and Golnoosh Shahkarami. Learning- Augmented Algorithms for Online TSP on the Line. In 37th AAAI Conference Artificial Intelligence. AAAI, 2023.
[GP19] Sreenivas Gollapudi and Debmalya Panigrahi. Online Algorithms for Rent-or-Buy with Expert Advice. In International Conference Machine Learning, pages 2319-2327. PMLR. 2019.
IKBC+ 18] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The Case for Leamed Index Structures. In Proceedings of the 2018 international conference management of data, pages 489-504, 2018.
[Kon25] Aryeh Kontorovich. On the tensorization of the variational distance. Electronic Communications in Probability, 30:1-10, 2025.

---

[LLMV20] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online Scheduling via Learned Weights. In Proceedings of the Fourteenth Anmual ACM-SIAM Symposium on Discrete Algorithms, pages 1859-1877. SIAM, 2020.
[Mit18] Michael Mitzenmacher. A Model for Learned Bloom Filters, and Optimizing by Sandwiching. Advances in Neural Information Processing Systems, 31, 2018.
[PSK18] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving Online Algorithms via ML Predictions. Advances in Neural Information Processing Systems, 31, 2018.
[WLW20] Shufan Wang. Jian Li, and Shiqiang Wang. Online Algorithms for Multi-shop Ski
Rental with Machine Learned Advice. Advances in Neural Information Processing Systems, 33:8150-8116 2020.
12

---

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: Formal theorems are stated and proved for every claim made.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
The paper is entirely theoretical. Theoretical limitations and assumptions etc are formally discussed. The claims are only made under the scope of these assumptions.
Justification:
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 a 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 well-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 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]
13

---

Justification:
All assumptions are stated and full proofs are given in the paper itself.
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: This 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 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?
14

---

Answer:
[NA]
Justification:
This paper does not include experiments, and does not provide code or data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
crriiinnolccyc icy 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
/ /pipps.cc/pullc//uuui wwwiiicgguie//eeeeeeeeeic CoodeSubeiiie ssi wsionnolli 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: This 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: This 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 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.
15

---

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 figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This 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 individual experimental runs as 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 or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics ctttas///eerrrss..cc//bb/////iie
Answer: [Yes]
The paper is entirely theoretical, and does not use human subjects or real-world datasets. The proposed algorithms are fully specified for reproducibility, and theorems/ideas from other papers have been acknowledged.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., . if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is theoretical and abstract; there is no direct societal impact.
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 socictal 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.
16

---

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 negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not introduce real world data or models, and poses no risks.
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 not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or 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 (c.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 package should be provided. For popular datasets, paperswi thcode. com com/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.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset'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: This paper does not introduce any assets other than the pseudocode and algorithms described.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl 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 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 as details about compensation (if any)?
Answer: [NA]
Justification: The paper is entirely theoretical and does not use crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper is entirely theoretical and has no human subjects or study partici- pants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 the NeurIPS Code of Ethics and the guidelines for their institution.
18

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs
used in the development of this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non standtaddard components.
Please refer to our LLM policy (https: for what should or should not be described.
19


Reviews:
[{"review_id": "LDsHPJBGc0", "reviewer": "Reviewer_kAA6", "summary": "I really like the model of \"learning with imperfect advice\", which I think is both conceptually interesting and practically well motivated.  In my own words, and at a high level,  this model is the following: A learner interacts with some untrusted third party which gives them \"advice\". If the advice is \"good\" then the query complexity of the learner should improve over the baseline learning algorithm. However, the learner should never require more queries than the baseline algorithm, even if the advice is \"bad\" -- i.e. the learning algorithm should be robust against \"bad\" advice. The learner has no promise on whether the advice is good or bad.\nGiven this setup, there is a clear high-level algorithm for this problem, which is roughly the following:\nTest if the advice is good or bad.\nIf the advice is good, accept the advice - you're done.\nIf the advice was bad, revert to learning, possibly using extra information gained during testing.\nFrom the above its clear that this model mixes learning and testing in an interesting way,  and that learning with sublinear query complexity should be possible when the advice is good and a sublinear test for this is possible. As before, I think this really is an interesting model, and that there are many many natural and interesting open questions.\nWith this in mind, the submitted manuscript studies the problem of learning product distributions in this model, where the advice is a full description of a candidate product distribution. This is a natural analogue of previous work in this area on learning multivariate Gaussians with imperfect advice (BCGJ24), and indeed the high-level structure of the algorithm given in the manuscript is analogous to the one given in BCGJ24. However, to instantiate this algorithm the authors of the submitted manuscript need to develop a novel tolerant mean tester and l1 approximation algorithm. Interestingly, it also turns out that unlike the multivariate gaussian case, one provably needs a \"balancedness\" assumption in this setting (even though this assumption is not necessary for identity testing of product distributions!). With this in mind, I think the manuscript has the following strengths and weaknesses:", "questions": "None.", "limitations": "None.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nI think that the model considered is very interesting and well motivated, and the paper provides some foundational results in this model, which has only very recently been proposed and studied for the first time. I think its great to draw more attention to this model!\nThe paper exposes an interesting and unexpected  discrepancy between testing product distributions and learning product distributions with imperfect advice.\n\nWeaknesses:\nIn many ways (both upper and lower bounds) the submitted manuscript parallels the earlier work of BCGJ24 on learning multivariate gaussians in this model. While the authors do require some novel elements -- namely a new tolerant mean tester and l1 approximation algorithm -- the high level ideas mostly already present in earlier work. To be fair though, because there is an \"obvious\" high-level algorithm, most work in this area will probably share the same key ideas and methods.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort to review our work and for your feedback. While our work indeed closely follows the framework of [BCJG24] as you said, there \nare both conceptual as well as technical differences. Conceptually, [BCJG24] uses tools from linear algebra and facts about probability densities, while the \nwork here is for discrete distributions on the Boolean hypercube. Technically, the novelty here is in (i) the tolerant mean-vector L2 tester and using it to approximate mean-vector L1 distance for binary product distributions, (ii) identifying the necessity of the balancedness assumption (already explored in the product distribution learning literature) in learning using sublinear (in dimension $d$) samples, even when given good advice (Lemma 4.2)."}, {"review_id": "vxvks11tOJ", "reviewer": "Reviewer_kA8u", "summary": "This paper studies distribution learning with advice, within the line of research on learning-augmented algorithms or algorithms with predictions. In the standard version of the problem, the algorithm is given samples from a product distribution $P$ over $\\{0,1\\}^d$ and the goal is to output an estimate of $P$ which is $\\epsilon$ close in TV distance. In this work, the algorithm is also given access to the parameters of another distribution $Q$, also a product distribution over $\\{0,1\\}^d$. The goal is to design an algorithm which is more sample efficient if $Q$ is close to $P$ and which is not much more sample inefficient ($O(d/\\epsilon^2)$ samples is the benchmark in the standard setting) for worst-case $Q$.\n\nThe main result of this paper is an algortihm which improves over $O(d/\\epsilon^2)$ samples as long as $\\|Q-P\\|_1 \\ll \\epsilon \\sqrt{d}$. This result is restricted to the case where every coordinate of $P$ has probability bounded away from $0$ and $1$. The authors show that both this condition and the dependence on the $\\ell_1$ distance between $P$ and $Q$ are required: there exist distributions which do not satisfy these conditions for which sublinear in $d$ samples are insufficient for learning.\n\nIf the $\\ell_1$ distance between $P$ and $Q$ was known, then the authors show that a reduction to hypothesis selection by covering the $\\ell_1$ ball around $Q$ with $\\ell_2$ balls of radius $\\epsilon$. To estimate the distance, the authors develop a tolerant tester for product distributions based on tolerant testers for discrete distributions over $[d]$.", "questions": "Is there hope to improve the quantitative dependence on the $\\ell_1$ distance?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper addresses the natural and fundamental problem of learning product distributions over the Boolean hypercube. The advice in the model is natural and the main result shows a nice tradeoff between the accuracy of the prediction and sample complexity of the algorithm.\n\nThe dependence on the $\\ell_1$ norm and the restriction to balanced distributions are justified by hard examples. Despite this, the balanced assumption in particular seems somewhat strong. It would be very interesting if some relaxations of this assumption could be made which avoid the hard example and still allow for sublinear learning when the prediction is good.\n\nThe paper is purely theoretically, and I would be very interested to see (proof-of-concept) experiments which could perhaps investigate whether $\\ell_1$ distance between $p$ and $q$ is strongly correlated empirically with the accuracy of perhaps a simplified version of your tester.\n\n## Minor Comments\n\nLemma 4.2 is missing a period at the end of the lemma.", "was_revised": true, "final_justification": "I maintain my positive score for the reasons given in the review.", "rebuttal": "Thank you for time and effort to review our work, and for your feedback.\n\n**Balancedness assumption:**\nIn Lemma 4.2, we have shown that learning unbalanced distributions (with $O(1/d)$ entries in the mean vector) requires a number of samples linear in the dimension $d$, even when given ``very good'' advice (with $O(\\varepsilon)$ $\\ell_1$ distance). Such an assumption is also common in the product distribution learning literature (e.g. Freund and Mansour 1999, Theorem 4.14). Such an assumption can be avoided, for instance by using the reduction (taking mixture size $k = 1$) from learning the parameters in $\\ell_\\infty$ distance to learning a (mixture of one) product distribution in KL divergence, which can be found in (Feldman et al. , Theorems 16 and 17). But then the number of samples required is linear (in dimension $d$). This defeats the purpose of using sublinear samples (in $d$) when given sufficiently good advice.\n\n\n**Proof of concept experiments:**\nThis paper is intended as a primarily theoretical work. However, the algorithm is based on an elementary test statistic (described in Lemma 3.2), the exponential search with coordinate-bucketing in ApproxL1, and the standard LASSO algorithm (implemented in packages like scikit-learn, etc). We can include some basic experiments in the final version of the paper.\n\n\n**Improving quantitative dependence on the $\\ell_1$ distance:**\nUnder balancedness, our lower bound in Lemma 4.3 shows that the dependency on $d$ is tight for constant $\\varepsilon$.\n\n**References**\n\n1. Y. Freund and Y. Mansour. ``Estimating a mixture of two product distributions''. COLT 1999.\n\n2. J. Feldman, R. O'Donnell and R. Servedio, ``Learning mixtures of product distributions over discrete domains''. SIAM Journal on Computing 2008."}, {"review_id": "cJFIcrHzNV", "reviewer": "Reviewer_Ch6Q", "summary": "The authors considered the problem setting of learning product distribution under imperfect advice, \nWith some assumption on the mean for each coordinate that is balanced (not too close to 0 or 1).\nThe problem setting is as follows.\nGiven an unknown product distribution of {0,1}^d (with p be the mean vector of it), \nand advice vector q.\nThe algorithm needs to learn a $\\hat{p}$ as an estimation of p, such that the product distribution specified by $\\hat{p}$\nIt is close to the true input product distribution in total variance distance. \n(With the balanced assumption here, this is equivalent to small l_2 norm between $\\hat{p}$ and $p$.)\nIf the given advice is good ($\\|q-p\\|_1$ is small), the algorithm needs to use fewer samples than the trivial $d/\\epsilon^2$ sample complexity.\nAnd if the given advice is bad, the algorithm needs to perform as well as the trivial $d/\\epsilon^2$ sample complexity. \nThis need to be done without the previous knowledge of $\\|q-p\\|_1$.\n\nFor their result, the authors give a polynomial time algorithm with $d^{1-\\eta}/\\epsilon^2$ sample complexity algorithm when $\\|p-q\\|_1<\\epsilon d^{0.5-\\Omega(\\eta)}$.\nThe high-level idea they used is the following:\nThe first step is to get an estimation of $\\|q-p\\|_1$.\nDirectly approximating it would result in linear sample complexity and defeat the purpose.\nSo the author partitions it into d/k blocks, each with k coordinates.\nThen, estimate the L2 norm difference on each block and add them up.\nThis gives an estimation of the l1 norm by a multiplicative error factor of at most $\\sqrt{k}$.\nAfter that, the problem can then be reformulated as the convex optimization below line 84.\n\nI feel like the result is far from optimal, and a lot more should be done in this setting. \nIn particular, there isn't much justification from the lower bound side, or some argument such as\nthis result is the best achievable under some particular type of methods. \nFurthermore, it seems both the assumption and the guarantee are very artificial. \n(mostly to incorporate the methodology using L2 norm from my understanding)\nThe author didn't explain about this L2 norm approach, like whether they are typical in this setting, or if this is the best we can do.\nThis is based on my limited knowledge of this topic, and I would encourage the authors to point out any mistakes I may have made.", "questions": "Can the authors explain more about why the assumptions are need here?\nEspecially if there is anything known about the sample complexity for unbalanced product distribution\nwhen the advice has o(1) l1 error.", "limitations": "Yes.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "One weakness I can think of is that the balanced assumption isn't very well justified.\nWhile the author did mention that there no sublinear sample complexity algorithm even when advice is O(1) close \nto the truth in l1 distance, it is unclear how sample complexity changes with o(1) l1 distance.\nAnd it is plausible that less samples are needed given the previous $\\sqrt{n}/\\epsilon^2$ indentity testing result.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for time and effort to review our work, and for your feedback.\n\n\n**Use of $\\ell_2$ norm:**\nWe would like to counter the suggestion that the $\\ell_2$ norm is artificial in this setting. It is known that the $\\ell_2$-distance between the mean\nvectors is a lower bound on the TV distance between product distributions (Kontorovich '25); so, to learn product distributions with small TV error, it is \n *necessary* to learn the mean vector with small $\\ell_2$ error.\n\n**Justification from the lower bound side:**\nTo be clear, in Lemma 4.2, the condition $\\|p-q\\|_1<\\epsilon$ implies that the total variation distance between the product distributions with mean vectors $p$ and $q$ \nis $<\\varepsilon$. This is also from (Kontorovich '25). So, Lemma 4.2 makes sense only if $\\|p-q\\|_1>\\varepsilon$, since otherwise the sample complexity would become 0 \nas an algorithm could simply return $q$. \n\nNote that our lower bounds are in the easier setting where the $\\ell_1$ distance from the advice and true mean vectors is promised to satisfy an upper bound. \nOur algorithms are in the harder setting where there is no promise, so our lower bounds automatically translate. Your question about learning when\nthe advice quality is $\\ll \\varepsilon$ is definitely valid when the advice error is not known to the algorithm, and we have not explored lower bounds in this setting here.\n\nWe will make sure to add a fuller discussion of these issues in the final version.\n\n**References**\n1. Aryeh Kontorovich. ``On the tensorization of the variational distance.'' Electronic Communications in Probability, 30:1–10, 2025."}, {"review_id": "xciBXePcbQ", "reviewer": "Reviewer_84iq", "summary": "The paper falls in the line of research of algorithms with predictions where algorithms are equipped with advice or predictions. Given recent developments in machine learning it is often too pessimistic to run a worst-case algorithm and not leverage predictable structures of the input. The line of research seeks to bridge algorithms and ML by obtaining provably improved algorithms with accurate predictions while also maintaining worst case guarantees.\n\nThe paper studies the problem of learning a product distribution $\\bf{p}$ (parametrized by Bernoulli parameters $(p_1,\\dots,p_d)$) over the hypercube $\\{0,1\\}^d$. It is well-known that $\\Theta(d/\\varepsilon^2)$ is necessary and sufficient in the classic setting of the problem where we want to return a distribution of total variation distance at most $\\varepsilon$ to $\\textbf{p}$. The paper shows that if each $p_i\\in [\\tau,1-\\tau]$ (they call this assumption \\emph{balancedness}), say for some $\\tau=\\Omega(1)$, if we are given access to an \\emph{advice} distribution $\\bf{q}$ such that $\\|\\textbf{p}-\\textbf{q}\\|_1$ is small, one can reduce the sample complexity. Specifically, one can obtain sublinear sample complexity $\\tilde O (d^{1-\\eta}/\\varepsilon^2)$ as long as $\\|\\textbf{p}-\\textbf{q}\\|_1\\leq \\varepsilon d^{0.5-\\Omega(\\eta)}$. The paper additionally shows lower bounds demonstrating that without the balancedness assumption, even with very accurate advice, say $\\|\\textbf{p}-\\textbf{q}\\|_1=O(1)$, we must use $\\Omega(d/\\varepsilon)$ samples. Additionally, they show that when $\\|\\textbf{p}-\\textbf{q}\\|_1\\geq \\varepsilon\\sqrt{d}$, we again require $\\Omega(\\sqrt{d})$ samples.\n\nI found the problem well motivated and the techniques quite interesting. The main challenge is to estimate $\\|\\textbf{p}-\\textbf{q}\\|_1$ using a small number of samples from $\\textbf{p}$. If this quantity is large, say $\\geq \\lambda$, the algorithm just resorts to its classic counterpart which returns the empirical mean of a bunch of samples. Otherwise, they can return the solution to a constrained (by $\\|\\hat \\textbf{p}-\\textbf{q}\\|\\leq \\lambda$) least squares problem. With this constraint, the sample complexity is correspondingly smaller.", "questions": "l89: You say that we can simply return $\\textbf{q}$ but this sound different from what your algorithm does, namely either running the least squares algorithm or the classic algorithm. Can you clarify?\n\nl155: $\\|\\textbf{p}\\|\\to \\|\\textbf{p}\\|_1$\n\nl159: $m(k,\\alpha, \\delta')$ hasn't been defined.\n\nAlgorithm 1, l6: Do  you want to define $\\mathcal{S}_j$ as a multiset?\n\nAlgorithm 1, l11: It's not really clear what it means to run the algorithms with these parameters. For example, you should mention that $l_i$ is the accuracy paramter.\n\nl174: $n_{k,\\varepsilon}$ and $r_\\delta$ haven't been defined.\n\nl181: I think you want to claim that $\\|\\textbf{p}\\|\\to \\|\\textbf{p}\\|_2$ is large\n\nl187: What does it mean to perform a constrained LASSO?\n\nAnd finally: The dependence on $\\varepsilon$ seems to be $1/\\varepsilon$ in your lower bound in Lemma 4.2, but the upper bound is $O(d/\\varepsilon^2)$. Do you have any idea what the right dependence is?", "limitations": "None", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "(1) The paper is well and clearly written and I had little difficulty following the proofs.\n(2) Distribution learning is an important problem and I found the  model well-motivated and interesting.\n(3) The algorithmic/theoretical content of the paper is quite nice. It seems to me that the main algorithmic contribution is the algorithm \\texttt{ApproxL1} which fails if $\\|\\textbf{p}-\\textbf{q}\\|_2$ is large (which implies that $\\|\\textbf{p}-\\textbf{q}\\|_1$ is large) and otherwise outputs an estimate $\\lambda$ of $\\|\\textbf{p}-\\textbf{q}\\|_1$.\n\n\\textbf{Weaknesses} (1) The author's state that their paper and analysis parallels that of [BCJG24] which address the problem of learning Gaussian distributions with imperfect advice. They state that one of their different contributions is their new $\\ell_2$-approximation algorithm. If by this, they refer to the one of Lemma 3.2, this is maybe a little disappointing as the ideas are very similar to [DK16]. I am thus curious whether the ideas behind Lemma 3.3 are new, or if similar ideas appeared in [BCJG24].", "was_revised": true, "final_justification": "Please see the discussion with the authors", "rebuttal": "Thank you for the time and effort to review our work, and for your feedback.\n\n**Lemma 3.2:**\nWhile we agree that the test statistic is taken from [DK16], the context is quite different, as the authors there were studying 1-dimensional distributions,\nwhereas here, we apply the test to high-dimensional product distributions. Also, there is no additional flattening step, as is necessary to get the optimal\nsample complexity in the 1-dimensional case. \n\n\n**Line 89:**\nYou are right that we did not describe Algorithm 2 as such. We can explicitly write an additional case in our algorithm (where the advice is good enough to return directly without a Lasso optimization step). But it does not qualitatively change our theoretical guarantees, so we opted to absorb this special case into the least-squares Lasso optimization case.\n\n**Line 155:**\nThank you for pointing out the typo. In Lines 155 and 156, it should be $\\|p\\|_2$ and $\\|p-q\\|_2$. We will add fix these in our revision.\n\n**Line 159 and 174:**\nWe take $n_{k, \\varepsilon} = \\lceil\\frac{16\\sqrt{k}}{3\\varepsilon^2}\\rceil$, $r_{\\delta} = 1 + \\lceil \\log(12/\\delta) \\rceil$, and define $m(k, \\alpha, \\delta) \\triangleq n_{k, \\varepsilon} \\cdot r_{\\delta}$ for any choice of $\\varepsilon, \\delta$. We will add these definitions properly in our final version. As in lines 174-177, we set $\\delta$ to $\\delta^\\prime = \\frac{\\delta}{w \\cdot \\lceil \\log_2 (\\zeta/\\alpha)\\rceil}$ in each invocation and then take a union bound over all invocations. Hence we use $m(k, \\alpha, \\delta^\\prime)$ samples.\n\n**Algorithm 1, Line 6:**\nYes, both $\\mathcal{S}$ and $\\mathcal{S}_j$ are indeed multisets.\n\n**Algorithm 1, Line 11:**\nWe invoke ApproxL1 (Lemma 3.2) with accuracy $\\varepsilon = \\ell_i$, $\\delta = \\delta'$ (as defined in line 176), $S_j$ as samples from $\\mathrm{Ber}(\\mathbf{p})$ projected to coordinates $B_j$, and $\\mathbf{q}$ projected to coordinates $B_j$ as the advice. We will write this mapping more clearly in our revision.\n\n**Line 181:**\nSorry, could you please clarify what you mean by $\\|p\\| \\to \\|p\\|_2$ here? There is no mention of $p$ on Line 181.\n\n**Line 187:**\nBy constrained LASSO, we meant the optimization problem:\n\n$\\arg\\min_{\\|\\mathbf{b}-\\mathbf{q}\\|_1 \\leq \\lambda} \\frac{1}{n} \\sum_{i=1}^{n} \\|\\mathbf{b} - \\mathbf{q}_i\\|_2^2$\n\n\nwhich is what we put in Line 8 of Algorithm 2. This is the standard version of LASSO with an $\\ell_1$ constraint. We will change the phrasing to ``LASSO in its constraint form''.\n\n**Dependence on $\\varepsilon$ in the lower bound and upper bound:**\nLemma 4.2 is meant to show the linear dependence on $d$ in the unbalanced setting. The $1/\\varepsilon^2$ dependence comes from the balanced setting. Lemma 4.3 for the balanced setting is currently written for constant $\\varepsilon$. In the final version, we will put in a more refined argument that shows the correct dependence on $\\varepsilon$ as well; this is similar to the lower bound for learning gaussians."}]

Author rebuttal:

Meta-review: This paper studies the classic and fundamental problem of learning a discrete product distribution $p$ over $\{0,1\}^d$ from i.i.d. samples, with the twist that the algorithm is now given some additional (imperfect) advice $q$ on what the true distribution is. While the classic problem is well-understood, requiring $\Theta(d/\epsilon^2)$ samples to learn to total variation distance $\epsilon$, this paper shows how to beat the bound polynomially under a balancedness assumption---which the authors show are necessary---and improve the sample complexity to $O(d^{1-\eta}/\epsilon^2)$ where $\eta$ is a parameter derived from how close $p$ and $q$ are.

Reviewers and I all agree that this paper has an interesting model and an interesting result, and is a solid contribution to NeurIPS.
Decision: Accept (spotlight)