arXiv CSopen access

Learning Distributions from Multiple Data Providers

Learning Distributions from Multiple Data Providers Jon Kleinberg

Amin Saberi

Cornell University [email protected]

Stanford University [email protected]

Xizhi Tan

Grigoris Velegkas

Google Research [email protected]

Stanford University [email protected]

arXiv:2607.24732v1 [cs.DS] 27 Jul 2026

Abstract Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples. The goal is to learn an unknown distribution 𝑝 on a finite domain [𝑛]. The learner is given a fixed family of queryable sets 𝒮 ⊆ 2[𝑛] , and each query to 𝑆 ∈ 𝒮 returns an independent sample from the conditional distribution 𝑝(· | 𝑆). Learnability is governed by the co-occurrence graph associated with 𝒮: two domain elements are adjacent if they appear together in some queryable set. Pointwise consistency is achievable when this graph is connected on the target support. PAC learning requires more: it is possible when the co-occurrence graph is complete. The optimal sample complexity of PAC learning ranges from nearly linear to quadratic. Eve 2 /𝜀2 ), and ery query family with complete co-occurrence graph admits sample complexity 𝑂(𝑛 this bound is tight in the worst case. On the other hand, if [𝑛] ∈ 𝒮 ordinary sampling improves the bound to Θ(𝑛/𝜀2 ), and this cannot be improved further even if every set is queryable. More generally, we identify hierarchical comparability as a sufficient structural condition on 𝒮 2 ), with pairwise query families as e under which the optimal complexity is nearly linear, Θ(𝑛/𝜀 a canonical example. Finally, the full range of polynomial rates between linear and quadratic is e 𝛼 /𝜀2 ). attainable: for every 𝛼 ∈ (1, 2), there exists a query family with optimal PAC rate Θ(𝑛

1

Introduction

Modern generative models have benefited enormously from broad public and web-scale data, but high-quality, human-generated data may become a limiting resource for continued model scaling [VHS+ 24]. As model developers look beyond broad web crawling, curated and provider-controlled data sources become increasingly important. The central question is not simply how much data to acquire, but from which sources and how their coverage patterns affect learning. This challenge stems from two inherent phenomena: coverage and redundancy. A provider specialized in a narrow domain offers deep localized coverage, but does not reveal much about how that domain should be weighted within the global distribution. Conversely, querying multiple broad providers often introduces wasteful redundancy if they have a lot of overlap.

1

To isolate these issues, we study perhaps the simplest possible version of generative modeling: learning an unknown discrete distribution 𝑝 over a finite domain [𝑛]. The elements of [𝑛] may be viewed as document clusters, or more generally as latent content types. A data provider is represented by a subset 𝑆 ⊆ [𝑛]. When queried, the provider returns an independent sample from the conditional distribution 𝑝(· | 𝑆). The learner has access only to a fixed collection of such subsets, denoted by 𝒮, and its goal is to output a distribution close to 𝑝 in total variation distance. Our framework raises two fundamental questions. The first is qualitative: what overlap structure is necessary and sufficient for learning, either pointwise or in the PAC sense? The second is quantitative: once learning is possible, what is the optimal sample complexity? In particular, does the same structure that determines learnability also determine the rate of learning, or can different query families with the same qualitative learnability behavior have different sample complexities? Since our focus is on high-dimensional domains, we track the dependence on both the domain size 𝑛 and the target accuracy 𝜀. This is a restricted variant of the conditional-sampling model, commonly denoted by COND. Prior work on COND typically assumes unrestricted, or otherwise well-structured, access to conditional samples, and uses this access to accelerate distribution testing, frequency estimation, and related tasks [CRS15, CFGM16, Can20b]. In contrast, because we are motivated by settings in which data providers might offer sources that overlap in complex and arbitrary ways, our goal is to understand the learning landscape induced by an arbitrary fixed query family 𝒮, with a focus on learning in total variation distance.

1.1

Our Results

Our results give a structural theory of distribution learning in total variation distance from an arbitrary query family 𝒮. They divide into two parts: qualitative learnability, which identifies when recovery is possible, and quantitative sample complexity, which determines how the geometry of 𝒮 controls the optimal rate. Characterization of learnability. The qualitative results, summarized in Table 1, give exact combinatorial characterizations of PAC learnability and pointwise consistency. The central object is the co-occurrence graph1 induced by the query family 𝒮 on a target support 𝑈; see Definition 3. Its vertices are the elements of 𝑈, and two vertices 𝑥, 𝑦 ∈ 𝑈 are adjacent exactly when some queryable set 𝑆 ∈ 𝒮 contains both. This graph is denoted by CO(𝒮, 𝑈). We first consider PAC learnability (Definition 1), which requires that for any error target 𝜀 there is a single sample complexity bound that holds simultaneously over all distributions in the target class. We show that this is possible if and only if the co-occurrence graph on 𝑈 is complete (Theorem 3.2). (Note that a complete co-occurrence graph is consistent with a wide range of possible underlying hypergraph structures.) We then consider pointwise consistency (Definition 2), where the learning rate is allowed to be distribution-dependent. Here, the requirement on CO(𝒮, 𝑈) is significantly weaker: assuming the learner knows the exact support of the distribution (the target class is 𝒫𝑈+ ), connectivity of the co-occurrence graph is both necessary and sufficient (Theorem 3.1).2 1 In the hypergraph theory literature, this object appears under several names, including 2-section, clique graph,

representing graph, primal graph, and Gaifman graph, see, e.g.,[Bre13]. 2 If the exact support is unknown and allows for zero-mass elements (the class 𝒫 ), the potential for zero-mass 𝑈

2

Learning guarantee

Necessary and sufficient condition for target support 𝑈

PAC Learnability of 𝒫𝑈

𝑈 induces a complete (clique) CO(𝒮, 𝑈)

Pointwise Consistency on 𝒫𝑈+

𝑈 induces a connected CO(𝒮, 𝑈)

Pointwise Consistency on 𝒫𝑈

𝑈 induces a complete CO(𝒮, 𝑈)

Table 1: Learnability characterization of a query family 𝒮. Given 𝑈 ⊆ [𝑛], 𝒫𝑈+ denotes the set of distributions supported on 𝑈 and 𝒫𝑈 the set of distributions supported on any subset of 𝑈. Optimal sample complexity. Having established when learning is possible, the next question is the optimal sample complexity of PAC learning. The resulting landscape is summarized in Figure 1. As an ideal benchmark, with maximal query power (that is when 𝒮 consists of all subsets of [𝑛]) the optimal bound is Θ(𝑛/𝜀2 ) (Theorem 4.1).3 Completeness of the co-occurrence graph characterizes PAC learnability, but it does not determine the optimal rate. In contrast to classical settings such as binary classification, where the qualitative condition for learnability (finite VC dimension) also pins down the quantitative sample complexity [SSBD14], complete query families can exhibit much larger complexity. In particular, there exist families 𝒮 that induce complete co-occurrence graphs for which any PAC learner requires Ω(𝑛 2 /𝜀2 ) samples (Theorem 4.3). Thus, relative to full conditional access, restricted query families can incur an additional factor of 𝑛, even when PAC learning is possible. This is the true ˜ 2 /𝜀2 ) sample complexity worst-case degradation: completeness alone guarantees a general 𝑂(𝑛 bound (Theorem 4.2). The gap between the nearly linear benchmark and the quadratic worst case raises a natural structural question: which properties of 𝒮 allow for better bounds? Favorable local structure can lead to nearly linear sample complexity. In particular, hierarchical comparability (Definition 5) is a sufficient condition under which the optimal complexity is Θ̃(𝑛/𝜀2 ). This condition requires that the domain admit a recursive, tree-like partition in which internal nodes have appropriate “local queries”. The pure pairwise-query setting, closely related to PCOND and to Bradley–Terry–Luce comparisons [BT52], where 𝑆 consists of every pair {𝑥, 𝑦}, serves as a canonical example. Finally, linear and quadratic dependence on 𝑛 are not the only possible rates. For every 𝛾 ∈ (0, 1), there exist families 𝒮 that induce complete co-occurrence graphs and have optimal sample complexity Θ̃(𝑛 1+𝛾 /𝜀2 ) (Theorem 4.10). Takeaways. We believe our results yield conceptual insights that extend beyond our stylized setting and capture natural phenomena in learning from heterogeneous data sources. • Learnability does not determine sample complexity. The co-occurrence graph gives a sharp qualitative characterization of learnability, but it does not determine the quantitative rate. 2) e Among PAC learnable query families, the optimal sample complexity can range from Θ(𝑛/𝜀 e 2 /𝜀2 ), with intermediate polynomial rates also possible. Thus, once enough overlap exists to Θ(𝑛 to make learning possible, finer structural properties of 𝒮 still govern the cost of learning. “bridge” points breaks this connectivity guarantee, and pointwise consistency reverts to requiring a complete graph. 3 While this upper bound can be trivially achieved by repeatedly querying the full domain [𝑛], such direct access may be precluded by 𝒮.

3

Upper Bounds (Algorithms)

Lower Bounds (Hardness)

i.i.d. sample from [𝑛] or Hierarchical comparability (Theorem 4.4)

Θ̃

General complete query family (Theorem 4.2)

  𝑛 𝜀2

Full conditional access (Theorem 4.1)

Θ̃

 2 𝑛 𝜀2

Continuum  1+𝛾  of optimal rates Θ̃ 𝑛𝜀2 (Theorem 4.10) Redundancy-dominated query family (Theorem 4.3)

Figure 1: Sample complexity landscape illustrating the spectrum from linear to quadratic bounds based on the structural properties of the query family. • Redundant overlap can dilute signal. The quadratic lower bound is witnessed by query families in which every queryable set contains a common high-mass element 𝑀 together with only a constant number of other elements. When the target distribution assigns constant mass to 𝑀 and spreads the remaining mass roughly uniformly over the rest of the domain, most conditional samples reveal only the common element. The overlap is therefore abundant but uninformative: it repeatedly exposes the same dominant content while obscuring the low-mass distinctions needed for learning. • Hierarchical structure enables targeted comparisons. Near-linear rates become possible when the query family supports recursive localization. Hierarchical comparability formalizes this principle: the domain can be partitioned in a tree-like way, and the query family contains local queries that let the learner compare and refine mass estimates within successively smaller regions. This structure turns overlap into useful comparisons rather than redundant sampling.

1.2

Related Work

We now overview several areas that are related to our work. Conditional sampling. The conditional sampling model was introduced in distribution testing by [CRS15] and independently by [CFGM16]. In the full COND model, the algorithm may query arbitrary subsets and receives samples from the target conditioned on the queried set. This access can yield polylogarithmic or even dimension-independent bounds for several testing, evaluation, and mass-estimation tasks; see the survey of [Can20b] and recent work of [AFL26]. In particular, [CFGM16, AFL26] study the related problem of learning a distribution up to permutations (for well-structured 𝒮) and obtain poly(log(𝑛)) bounds. Note that this does not contradict our lower bound, since this is an easier task than learning in TV distance. Several variants of restricted conditional sampling have been studied, including non-adaptive conditional sampling [KT19], interval or subcube, and pairwise comparison models. Our contribution is not another algorithm for a given restriction, but a structural theory for arbitrary fixed query families.

4

Data mixtures and data markets. Our motivation is related to recent work on data selection for large-scale model training and on data markets. In language-model pretraining, several works study how the mixture proportions of different data domains affect model performance [XPD+ 23, YLS+ 25]. Work on data markets and data acquisition studies how training data should be procured or valued when it is supplied by multiple strategic or heterogeneous providers [LHK+ 24, HXY22]. Our model isolates a basic statistical question that underlies these settings: when data sources expose different overlapping parts of an unknown population, how does the overlap pattern determine whether the global distribution can be learned, and at what sample cost? Luce, Plackett–Luce, and comparison models. On a positive support, the conditional law Í 𝑝(𝑥 | 𝑆) = 𝑝 𝑥 / 𝑦∈𝑆 𝑝 𝑦 is the Luce choice rule on menu 𝑆 [Luc59]. Thus our model is a samplingbased version of stochastic choice from an arbitrary collection of menus. [AFM25] characterize Luce rationalizability for arbitrary menu collections, including settings with zero choice probabilities, and discuss implications for falsification, identification, and prediction. Their setting is structural and passive, whereas we study adaptive sampling and finite-sample learning guarantees. The pairwise special case coincides with the Bradley–Terry–Luce comparison model [BT52, Luc59]. A large literature studies passive or designed estimation from pairwise comparisons, including topology-dependent minimax rates [SBB+ 15], Rank Centrality [NOS17], and spectral ranking methods [MG15, APA18]. These works typically estimate latent quality scores or rankings under a given comparison graph, often under regularity assumptions such as positive weights, bounded dynamic range, or fixed sampling designs. By contrast, our loss is total variation distance to the normalized distribution, and our main question is how the allowed conditional queries determine both learnability and labeled distribution-learning complexity. Local sampling and active subset-wise feedback. [FKT22] study perfect sampling from pairwise comparisons in a local-sampling model where comparison sets are drawn from an exogenous design. Our generic complete-graph upper bound uses a related Markov-chain idea, but the query family is chosen adaptively by the learner and the goal is PAC learning rather than exact sampling. Active subset-wise Plackett–Luce feedback has also been studied for ranking and bestitem objectives [SG19]; those objectives differ from learning the entire labeled distribution in TV. Biased sampling and stochastic choice. Our model is also related to classical biased-sampling and selection-bias models. In that literature, one observes samples from known biased versions of an unknown distribution, often with density proportional to 𝑤 𝑖 (𝑥) 𝑑𝑃(𝑥) for known weight functions 𝑤 𝑖 . Querying a provider set 𝑆 in our model corresponds to the special case 𝑤 𝑆 (𝑥) = 1{𝑥 ∈ 𝑆}. [Var85] introduced nonparametric estimation for such selection-bias models, and [GVW88] developed large-sample theory for the NPMLE in multi-sample biased-sampling models, including identifiability, consistency, and asymptotic efficiency results. In stochasticÍ choice language, the conditional law 𝑝(𝑥 | 𝑆) = 𝑝 𝑥 / 𝑦∈𝑆 𝑝 𝑦 is the Luce or multinomial-logit choice rule on menu 𝑆 [Luc59]; recent work also studies Luce rationalizability for arbitrary collections of menus [AFM25]. These works are closest to our qualitative identifiability results. Our focus is different: we study adaptive conditional-query access to an arbitrary fixed family, distribution-free PAC learning in total variation, and finite-sample minimax rates. Multi-distribution learning.

Multi-distribution learning was introduced by [BHPQ17] under 5

the name collaborative PAC learning. This line of work studies supervised learning, with a focus on binary classification, from 𝑘 labeled distributions, with the goal of achieving small classification error simultaneously across them. [HJZ22] established optimal agnostic rates for finite hypothesis classes, while [ZZC+ 25] and [Pen24] obtained nearly optimal rates for classes of finite VC dimension. More recently, [HSJ26] studied multi-distribution learning under bounded label noise and showed that the fast rates available in the single-distribution setting need not extend to multiple distributions. In this literature, the different distributions are part of the learning objective: the learner is evaluated by its classification error on each distribution or by its worst-case error across them. Our setting has a different objective. There is a single target distribution 𝑝, and the provider-specific conditional distributions 𝑝(· | 𝑆) describe only the learner’s restricted access to 𝑝. The learner is not evaluated separately on these conditional distributions; rather, it must recover their relative normalizations and reconstruct the single global distribution 𝑝 in total variation distance. Moreover, the focus of our setting is distribution learning whereas the focus of that line of work is mostly binary classification.

2

Preliminaries

Let [𝑛] = {1, . . . , 𝑛} denote the finite universe of elements (e.g., a vocabulary of tokens). The objective to learn is a discrete probability distribution 𝑝 over [𝑛], belonging to the probability simplex ( ) Δ([𝑛]) :=

𝑛 : 𝑝 ∈ R≥0

𝑛 Õ

𝑝𝑥 = 1 .

𝑥=1

We model the heterogeneous data providers as a fixed query family 𝒮 = {𝑆1 , . . . , 𝑆 𝑘 }, where each 𝑆 𝑖 ⊆ [𝑛] is non-empty. Each 𝑆 𝑖 represents the part of the domain the 𝑖-th data provider can generate samples from. For any set 𝑆 ⊆ [𝑛], we denote its total probability mass under the target Í distribution as 𝑝(𝑆) := 𝑥∈𝑆 𝑝 𝑥 . The learner may not be able to sample directly from the global distribution 𝑝. Instead, it can only query provider sets 𝑆 ∈ 𝒮. The family 𝒮 is fixed in advance, but at each round the learner may adaptively choose which set 𝑆 ∈ 𝒮 to query. The sets in 𝒮 are the atomic query options: after selecting 𝑆, the learner receives one sample from 𝑝(· | 𝑆) and cannot impose an additional condition 𝑇 ⊊ 𝑆, unless 𝑇 is itself an allowed set in 𝒮. We use the UNIF0 convention for zero-mass queries4 . Thus, for every nonempty 𝑆 ⊆ [𝑛], define the one-query response law 𝑄 𝑝,𝑆 on [𝑛] by 𝑝𝑥   1{𝑥 ∈ 𝑆}, 𝑝(𝑆) > 0,    𝑝(𝑆)  𝑄 𝑝,𝑆 (𝑥) :=  1   𝑝(𝑆) = 0.  1{𝑥 ∈ 𝑆},  |𝑆| 4 To handle edge cases where a queried provider’s set has zero mass under the target distribution (𝑝(𝑆) = 0), we adopt the standard UNIF0 convention used in the conditional sampling literature, where the oracle returns a uniformly random point from the queried set (𝑄 𝑝,𝑆 := 𝑢𝑆 ). An alternative is the FAIL convention, where the oracle returns a failure symbol. The two conventions lead to the same structural criteria and sample bounds in all cases, so we proceed with UNIF0 for clarity.

6

Equivalently, if 𝑝(𝑆) > 0, then 𝑄 𝑝,𝑆 = 𝑝(· | 𝑆), while if 𝑝(𝑆) = 0, then 𝑄 𝑝,𝑆 = 𝑢𝑆 , the uniform distribution on 𝑆. We denote the family of one-query response laws accessible to the learner as Obs𝒮 (𝑝) := (𝑄 𝑝,𝑆 )𝑆∈𝒮 . Throughout this work, all probability spaces are finite. For two distributions 𝑃, 𝑄 on the same finite set Ω, let 1Õ 𝑑TV (𝑃, 𝑄) := |𝑃(𝜔) − 𝑄(𝜔)| 2 𝜔∈Ω

be the total variation distance and

Õ

DKL (𝑃∥𝑄) :=

𝑃(𝜔) log

𝜔∈Ω

𝑃(𝜔) 𝑄(𝜔)

the Kullback–Leibler divergence, with the usual convention that the summand is 0 when 𝑃(𝜔) = 0 and the divergence is +∞ if there exists 𝜔 with 𝑄(𝜔) = 0, 𝑃(𝜔) > 0. All logarithms are natural. If 𝑉, 𝑋 are finite random variables, 𝐻(𝑉) denotes entropy and 𝐼(𝑉; 𝑋) denotes mutual information. If 𝑉 and 𝑋 are random variables taking values in finite sets 𝒱 and 𝒳 with joint distribution 𝑃𝑉,𝑋 and marginals 𝑃𝑉 and 𝑃𝑋 , the Shannon entropy of 𝑉 is 𝐻(𝑉) :=

Õ

𝑃𝑉 (𝑣) log

𝑣∈𝒱

1 , 𝑃𝑉 (𝑣)

and their mutual information is defined as 𝐼(𝑉; 𝑋) := DKL (𝑃𝑉,𝑋 ∥𝑃𝑉 ⊗ 𝑃𝑋 ), where 𝑃𝑉 ⊗ 𝑃𝑋 denotes the product distribution (𝑃𝑉 ⊗ 𝑃𝑋 )(𝑣, 𝑥) := 𝑃𝑉 (𝑣) · 𝑃𝑋 (𝑥). Moreover, for two strings 𝜎, 𝜏 ∈ 𝒜 𝑚 over a common alphabet 𝒜, their Hamming distance is 𝑑𝐻 (𝜎, 𝜏) := {𝑗 ∈ [𝑚] : 𝜎 𝑗 ≠ 𝜏𝑗 } =

𝑚 Õ

1{𝜎 𝑗 ≠ 𝜏𝑗 }.

𝑗=1

We will use the following elementary Bernoulli concentration bound. If 𝐵1 , . . . , 𝐵 𝑁 are independent random variables in {0, 1} with common mean 𝜃, then for every 𝑢 > 0,

" P

𝑁

#

1 Õ 𝐵𝑡 − 𝜃 ≥ 𝑢 ≤ 2 exp(−2𝑁𝑢 2 ). 𝑁 𝑡=1

Notions of learnability. Throughout our work we study two notions of learnability for a target class 𝒫 ⊆ Δ([𝑛]) and query family 𝒮. Given 𝑈 ⊆ [𝑛], we denote 𝒫𝑈+ := 𝑝 ∈ Δ([𝑛]) : 𝑝 𝑥 > 0 iff 𝑥 ∈ 𝑈



and

𝒫𝑈 := 𝑝 ∈ Δ([𝑛]) : 𝑝 𝑥 = 0 for all 𝑥 ∉ 𝑈 ,



i.e., 𝒫𝑈+ consists of distributions with support exactly 𝑈, while 𝒫𝑈 allows any support ⊆ 𝑈. We begin with the standard PAC framework, requiring a single sample bound that holds simultaneously for the entire class.

7

Definition 1 (PAC learnability). Fix a target class 𝒫 ⊆ Δ([𝑛]). We say that 𝒮 PAC learns 𝒫 if there exists a sample-complexity function 𝑚 : (0, 1)2 → N such that for every 𝜀, 𝛿 ∈ (0, 1) there is an adaptive randomized learner which, for every target distribution 𝑝 ∈ 𝒫 makes at most 𝑚(𝜀, 𝛿) queries and outputs 𝑝ˆ satisfying ˆ 𝑝) ≤ 𝜀] ≥ 1 − 𝛿 , P[𝑑𝑇𝑉 ( 𝑝, where the probability is taken with respect to the randomness of the samples and the internal randomness of ∗ the learner. The optimal PAC query complexity is denoted by 𝑞𝒮,𝒫 (𝜀, 𝛿). We also consider the weaker notion of pointwise consistency, which allows the required number of samples to achieve some given error bound to depend on the specific target distribution. Definition 2 (Pointwise consistency). Fix a target class 𝒫 ⊆ Δ([𝑛]). We say that 𝒮 pointwise consistently learns 𝒫 if there exists a sequence of adaptive randomized learners (𝐴𝑡 )𝑡≥1 , where 𝐴𝑡 makes 𝑡 queries on 𝒮, such that for every 𝑝 ∈ 𝒫 and every 𝜀, 𝛿 ∈ (0, 1) there exists 𝑡0 = 𝑡0 (𝑝, 𝜀, 𝛿) such that for all 𝑡 ≥ 𝑡0 P𝑝 [𝑑𝑇𝑉 (𝐴𝑡 , 𝑝) ≤ 𝜀] ≥ 1 − 𝛿 . Note that PAC learnability implies pointwise consistency. Proposition 2.1. If 𝒮 PAC learns a class 𝒫, then 𝒮 pointwise consistently learns 𝒫. Proof. For each 𝑠 ≥ 1, let 𝐵 𝑠 be a PAC learner with parameters (𝜀𝑠 , 𝛿 𝑠 ) = (1/𝑠, 1/𝑠), and let 𝑁𝑠 be its query bound. Define 𝑀 𝑠 := max1≤𝑗≤𝑠 𝑁 𝑗 . Given budget 𝑘, let 𝑠(𝑘) := max{𝑠 ≤ 𝑘 : 𝑀 𝑠 ≤ 𝑘}, if this set is nonempty; otherwise output an arbitrary fixed distribution. If 𝑠(𝑘) is defined, let 𝐴 𝑘 run 𝐵 𝑠(𝑘) . Then 𝐴 𝑘 uses at most 𝑀 𝑠(𝑘) ≤ 𝑘 queries. Also 𝑠(𝑘) → ∞, since for every fixed 𝑠, we have 𝑠(𝑘) ≥ 𝑠 whenever 𝑘 ≥ max{𝑠, 𝑀 𝑠 }. Fix 𝑝 ∈ 𝒫 and 𝜀, 𝛿 ∈ (0, 1). Choose 𝑠 0 with 1/𝑠0 ≤ min{𝜀, 𝛿}. For all large enough 𝑘, 𝑠(𝑘) ≥ 𝑠0 , and hence Pr[𝑑TV (𝐴 𝑘 , 𝑝) ≤ 𝜀] ≥ Pr[𝑑TV (𝐵 𝑠(𝑘) , 𝑝) ≤ 1/𝑠(𝑘)] ≥ 1 − 𝑝

𝑝

1 ≥ 1 − 𝛿. 𝑠(𝑘)

□

We defer several technical lemmas that are useful for our results to Appendix A.

3

Learnability and Query Families

We first characterize the qualitative limits of learning from a restricted collection of providers. In other words, we answer the following basic question: given a fixed query family 𝒮, which distribution classes 𝒫 can be learned from conditional queries to 𝒮? The answer is governed by how the available sets 𝑆 ∈ 𝒮 overlap on the target support. Informally, if two elements 𝑥, 𝑦 ∈ [𝑛] appear together in some queryable set 𝑆, conditional samples from 𝑆 directly reveal their relative probability mass. If the target domain is connected via a chain of such overlaps, these local comparisons can be propagated to calibrate the entire distribution. We formalize this overlap structure through the co-occurrence graph. As we will show, the topology of this graph characterizes learnability. For pointwise consistency on a known support, mere connectivity of the graph is necessary and sufficient. However, for PAC learning, where a single finite-sample bound must hold even for distributions that place arbitrarily small mass on intermediate bridge points, connectivity fails, and completeness of the graph is required. 8

Definition 3 (Co-occurrence graph). For a given subset 𝑈 ⊆ [𝑛] and query family 𝒮, the co-occurrence graph CO(𝒮, 𝑈) is defined as the graph with vertex set 𝑈 and edge set 𝐸 (CO(𝒮, 𝑈)) := {𝑥, 𝑦} ⊆ 𝑈 : ∃𝑆 ∈ 𝒮 with 𝑥, 𝑦 ∈ 𝑆 .



In words, an edge {𝑥, 𝑦} indicates that some provider set contains both 𝑥 and 𝑦, and therefore allows the learner to compare their relative masses through conditional queries to 𝑆. We say that CO(𝒮, 𝑈) is connected if there exists a path between every pair of elements of 𝑈. Furthermore, CO(𝒮, 𝑈) is complete if there exists an edge between every pair of distinct elements of 𝑈, i.e., every possible pair co-occurs within the domain of at least one provider.

3.1

Pointwise Consistency: Connected Support

We first consider the ability of a query family to pointwise consistently learn a target distribution. In this regime, the learner knows the exact support of the target distribution, and the sample complexity is allowed to depend on the specific target. Our main result here shows that connectedness of the co-occurrence graph is necessary and sufficient. Before providing the main proof, we give some intuition for the result. If CO(𝒮, 𝑈) is connected, the learner fixes a spanning tree of this graph. Each tree edge {𝑢, 𝑣} lies in some set 𝑆 ∈ 𝒮, and conditional samples from 𝑆 can estimate the ratio 𝑝 𝑣 /𝑝 𝑢 . By multiplying these estimated ratios along paths from a root 𝑟, the learner estimates 𝑝 𝑥 /𝑝 𝑟 for every 𝑥 ∈ 𝑈. Conversely, suppose CO(𝒮, 𝑈) is disconnected, with connected components 𝐶1 , . . . , 𝐶 𝑚 , 𝑚 ≥ 2. Then, no provider set 𝑆 can “compare” points 𝑥, 𝑦 from different components. Hence, the learner can estimate masses within each component, but it cannot estimate the relative total weights of the components. Theorem 3.1. Fix a nonempty set 𝑈 ⊆ [𝑛]. Then, 𝒮 pointwise consistently learns 𝒫𝑈+ if and only if the co-occurrence graph CO(𝒮, 𝑈) is connected. Proof. We prove the two directions separately. Sufficiency. Assume first that CO(𝒮, 𝑈) is connected. If |𝑈| = 1, the learner outputs the point mass on the unique element of 𝑈, so assume |𝑈| ≥ 2. Choose a spanning tree 𝒯 of CO(𝒮, 𝑈) and root it at some vertex 𝑟 ∈ 𝑈. Orient every tree edge away from 𝑟. For each directed tree edge 𝑒 = (𝑢 → 𝑣), choose one provider set 𝑆 𝑒 ∈ 𝒮 and 𝑢, 𝑣 ∈ 𝑆 𝑒 . Such a set exists by the definition of the co-occurrence graph. Let 𝐸𝒯 := |Edges(𝒯 )| = |𝑈| − 1. We now define a sequence of learners (𝐴𝑡 )𝑡≥1 satisfying the query counting convention in Definition 2: learner 𝐴𝑡 makes exactly 𝑡 queries. Given the total budget 𝑡, let   𝑡 . 𝑘 𝑡 := 𝐸𝒯 The learner queries each tree-edge provider set 𝑆 𝑒 exactly 𝑘 𝑡 times. This uses 𝐸𝒯 𝑘 𝑡 ≤ 𝑡 queries. 9

(𝑡)

For a directed tree edge 𝑒 = (𝑢 → 𝑣) and endpoint 𝑦 ∈ {𝑢, 𝑣}, let 𝑁𝑒 (𝑦) be the number of times the useful 𝑘 𝑡 samples from 𝑆 𝑒 return 𝑦, and define (𝑡)

b𝑒(𝑡) (𝑦) := 𝑁𝑒 (𝑦) , 𝜃

𝑦 ∈ {𝑢, 𝑣},

𝑘𝑡

whenever 𝑘 𝑡 ≥ 1. If 𝑘 𝑡 = 0, define the estimate arbitrarily; this affects only finitely many values of 𝑡 and is irrelevant for consistency. For 𝑘 𝑡 ≥ 1, define the lower-truncated frequencies

e𝑒(𝑡) (𝑦) := max 𝜃



b𝑒(𝑡) (𝑦), 1 𝜃 𝑘𝑡



,

𝑦 ∈ {𝑢, 𝑣}.

(𝑡)

and also let b 𝜌𝑟 := 1. For 𝑥 ∈ 𝑈 \ {𝑟}, let 𝑟 = 𝑣 0 , 𝑣 1 , . . . , 𝑣ℓ = 𝑥 be the unique path from 𝑟 to 𝑥 in 𝒯 . Writing 𝑒 𝑖 = (𝑣 𝑖−1 → 𝑣 𝑖 ) for the directed edges on this path, define ℓ Ö e𝑒(𝑡) (𝑣 𝑖 ) 𝜃 (𝑡) 𝑖 b 𝜌 𝑥 := . (𝑡) e 𝜃 (𝑣 ) 𝑖−1 𝑖=1 𝑒 𝑖 Finally, define the normalized values

b𝑡 := 𝑍

Õ 𝑧∈𝑈

(𝑡) b 𝜌𝑧 ,

(𝑡) b 𝑝 𝑥 :=

(𝑡) b 𝜌𝑥 b𝑡 𝑍

(𝑥 ∈ 𝑈),

(𝑡)

𝑝 (𝑡) . and set b 𝑝 𝑥 := 0 for 𝑥 ∉ 𝑈. The learner 𝐴𝑡 outputs b Fix any target distribution 𝑝 ∈ 𝒫𝑈+ . Since 𝑝 has exact support 𝑈, every point in 𝑈 has positive mass. In particular, 𝑝 𝑟 > 0. Moreover, for every tree edge 𝑒 = (𝑢 → 𝑣), the chosen set 𝑆 𝑒 contains both 𝑢 and 𝑣, so 𝑝(𝑆 𝑒 ) ≥ 𝑝 𝑢 + 𝑝 𝑣 > 0. Thus, every useful query to 𝑆 𝑒 returns an ordinary conditional sample from 𝑄 𝑝,𝑆𝑒 = 𝑝(· | 𝑆 𝑒 ). For 𝑦 ∈ {𝑢, 𝑣}, write 𝑝𝑦 𝜃𝑒 (𝑦) := 𝑝(𝑦 | 𝑆 𝑒 ) = . 𝑝(𝑆 𝑒 ) Because 𝑝 𝑦 > 0 and 𝑝(𝑆 𝑒 ) > 0, we have 𝜃𝑒 (𝑦) > 0. Couple the learners across stages by imagining, for each tree edge 𝑒, an infinite i.i.d. stream of samples from 𝑄 𝑝,𝑆𝑒 , with learner 𝐴𝑡 using the first 𝑘 𝑡 samples from each stream. Since 𝑘 𝑡 → ∞, we have that b𝑒(𝑡) (𝑦) −→ 𝜃𝑒 (𝑦) 𝜃 almost surely for every tree edge 𝑒 and every endpoint 𝑦 of 𝑒. The lower truncation by 1/𝑘 𝑡 does not change the limit. Indeed, 1/𝑘 𝑡 → 0, while 𝜃𝑒 (𝑦) > 0. Hence, almost surely, for all sufficiently large 𝑡, (𝑡)

b𝑒 (𝑦) > 𝜃 (𝑡)

(𝑡)

𝜃𝑒 (𝑦) 2

and (𝑡)

𝜃𝑒 (𝑦) 1 < . 𝑘𝑡 2

e𝑒 (𝑦) = 𝜃 b𝑒 (𝑦), and so 𝜃 e𝑒 (𝑦) −→ 𝜃𝑒 (𝑦) almost surely. Therefore, eventually, 𝜃 10

Consequently, for every directed tree edge 𝑒 = (𝑢 → 𝑣), (𝑡)

e𝑒 (𝑣) 𝜃 e𝑒(𝑡) (𝑢) 𝜃

−→

𝑝(𝑣 | 𝑆 𝑒 ) 𝑝𝑣 𝜃𝑒 (𝑣) = = 𝑝 𝜃𝑒 (𝑢) 𝑝(𝑢 | 𝑆 𝑒 ) 𝑢

almost surely.

Multiplying these convergent edge ratios along the unique path from 𝑟 to 𝑥 gives (𝑡) b 𝜌 𝑥 −→

ℓ Ö 𝑝𝑣

𝑖

𝑝 𝑣 𝑖−1

𝑖=1

𝑝𝑥 𝑝𝑟

=

almost surely.

For the root, this same result holds because (𝑡) b 𝜌𝑟 = 1 =

𝑝𝑟 . 𝑝𝑟

Thus, if we define the true ratio vector 𝜌 𝑥 :=

𝑝𝑥 , 𝑝𝑟

𝑥 ∈ 𝑈,

(𝑡)

then b 𝜌 𝑥 → 𝜌 𝑥 almost surely for every 𝑥 ∈ 𝑈. Since 𝑈 is finite,

b𝑡 = 𝑍

Õ 𝑧∈𝑈

(𝑡) b 𝜌 𝑧 −→

Õ

𝜌𝑧 =

𝑧∈𝑈

Õ 𝑝𝑧 𝑧∈𝑈

𝑝𝑟

=

1 𝑝𝑟

almost surely. (𝑡)

This is where the root mass is recovered: even though we set b 𝜌𝑟 = 1, the normalized estimate satisfies 1 (𝑡) b 𝑝𝑟 = −→ 𝑝 𝑟 almost surely. b𝑡 𝑍 For every 𝑥 ∈ 𝑈, we therefore obtain (𝑡) b 𝜌𝑥 𝑝 𝑥 /𝑝 𝑟 (𝑡) b = 𝑝𝑥 𝑝𝑥 = −→ 1/𝑝 𝑟 b𝑡 𝑍

almost surely.

(𝑡)

For 𝑥 ∉ 𝑈, both b 𝑝 𝑥 and 𝑝 𝑥 are identically zero. Hence 𝑑𝑇𝑉 b 𝑝 (𝑡) , 𝑝 −→ 0

almost surely.

Necessity. If CO(𝒮, 𝑈) is disconnected, write its connected components as 𝐶1 , . . . , 𝐶 𝑟 with 𝑟 ≥ 2. Choose any 𝑝 ∈ 𝒫𝑈+ and positive scalars 𝑎 1 , . . . , 𝑎 𝑟 not all equal. Define 𝑞 𝑥 = Í𝑟

𝑎 𝑗 𝑝𝑥

ℓ =1 𝑎ℓ 𝑝(𝐶ℓ )

for 𝑥 ∈ 𝐶 𝑗 .

Then 𝑞 ∈ 𝒫𝑈+ and 𝑞 ≠ 𝑝. Every allowed query 𝑆 intersects 𝑈 in at most one connected component; otherwise it would create an edge between two components. Therefore conditioning on 𝑆 cancels the common multiplicative factor 𝑎 𝑗 , and 𝑞(· | 𝑆) = 𝑝(· | 𝑆) for every informative query. Hence the map is not injective. □

11

Remark 1 (Unknown support requires completeness). If the exact support is unknown (the target class is 𝒫𝑈 ), pointwise consistency requires CO(𝒮, 𝑈) to be complete. If two elements never cooccur directly, connecting them requires intermediate bridge points. If the distribution assigns zero mass to these bridges, the path is “broken,” making their relative weights unobservable. Indeed, suppose CO(𝒮, 𝑈) is not complete. Then there exist distinct elements 𝑎, 𝑏 ∈ 𝑈 that never co-occur in any queryable set 𝑆 ∈ 𝒮. The unknown-support class 𝒫𝑈 contains the two-point family of distributions parameterized by 𝜃: 𝑝 𝜃 = 𝜃𝛿 𝑎 + (1 − 𝜃)𝛿 𝑏 , 𝜃 ∈ (0, 1). Because 𝑎 and 𝑏 never appear together in any allowed query set, every query 𝑆 ∈ 𝒮 intersects {𝑎, 𝑏} in at most one element. Consequently, if the learner queries a set 𝑆 containing 𝑎 (which implies 𝑏 ∉ 𝑆), the conditional distribution 𝑝 𝜃 (· | 𝑆) assigns probability 1 to 𝑎, regardless of 𝜃. Symmetrically, if 𝑆 contains 𝑏, the conditional distribution assigns probability 1 to 𝑏, again regardless of 𝜃. If 𝑆 contains neither 𝑎 nor 𝑏, the probability of the set is zero. In all valid cases, the response law of every allowed query in 𝒮 is independent of 𝜃. Because the samples provide no information about 𝜃, the relative weight between 𝑎 and 𝑏 is unobservable, making it impossible to pointwise consistently learn the distribution.

3.2

PAC Learnability: Complete Support

For PAC learning, the learner must achieve a guaranteed error bound within a fixed sample size, simultaneously for all distributions in the class. As foreshadowed in Remark 1, mere connectivity is insufficient to provide such a uniform guarantee. Even if the distribution has full support on 𝑈, it might assign arbitrarily small positive mass to intermediate bridge points. At any fixed sample size, these low-mass bridges become statistically invisible, breaking the propagation of local ratios. Thus, PAC learnability requires the co-occurrence graph to be complete. Theorem 3.2. Fix a nonempty set 𝑈 ⊆ [𝑛]. Then 𝒮 PAC learns 𝒫𝑈 if and only if the co-occurrence graph CO(𝒮, 𝑈) is complete. Proof. We prove the two directions separately. Sufficiency. If CO(𝒮, 𝑈) is complete, PAC learnability follows from the learner in Algorithm 1, proved in Theorem 4.2. Necessity. Choose distinct 𝑎, 𝑏 ∈ 𝑈 that never co-occur in an allowed query set. First suppose 𝑈 = {𝑎, 𝑏}. Consider 1 1 2 2 𝑞 = 𝛿 𝑎 + 𝛿𝑏 . 𝑝 = 𝛿 𝑎 + 𝛿𝑏 , 3 3 3 3 Every allowed query contains at most one of 𝑎, 𝑏. If a query contains exactly one of them, then under both targets the conditional response is deterministic on that point. If it contains neither, then the queried set has zero mass under both targets, so the response law is target-independent under either zero-mass convention. Hence every adaptive strategy has exactly the same transcript law under 𝑝 and 𝑞. Since 1 𝑑TV (𝑝, 𝑞) = , 3 PAC learning is impossible. 12

Now assume 𝑚 := |𝑈| ≥ 3. Let 𝑅 := 𝑈 \ {𝑎, 𝑏}. Choose 𝜂 > 0 small enough that Define 𝑝 𝜂 , 𝑞 𝜂 ∈ 𝒫𝑈+ . by 𝜂

𝑝𝑎 = and

1 𝜆 := 1 − (𝑚 − 2)𝜂 ≥ . 2 2𝜆 , 3

𝜂

𝑝𝑏 =

𝜆 , 3

𝜂

𝑝𝑧 = 𝜂

(𝑧 ∈ 𝑅),

𝜆 2𝜆 𝜂 𝜂 , 𝑞𝑏 = , 𝑞𝑧 = 𝜂 3 3 These are valid distributions with exact support 𝑈, because 𝜂

𝑞𝑎 =

(𝑧 ∈ 𝑅).

2𝜆 𝜆 + + (𝑚 − 2)𝜂 = 𝜆 + (𝑚 − 2)𝜂 = 1, 3 3 and all masses are positive. Moreover, 1 𝑑TV (𝑝 , 𝑞 ) = 2 𝜂

𝜂



2𝜆 𝜆 𝜆 2𝜆 − + − 3 3 3 3

 =

𝜆 1 ≥ . 3 6

We next show that every one-query response law is close under these two targets. Fix an allowed query set 𝑆 ∈ S. If 𝑆 contains neither 𝑎 nor 𝑏, then the restrictions of 𝑝 𝜂 and 𝑞 𝜂 to 𝑆 are identical. Thus, if 𝑆 has positive mass, the conditional response laws are identical; if 𝑆 has zero mass, the response law is again target-independent under either zero-mass convention. By the choice of 𝑎, 𝑏, no allowed query contains both 𝑎 and 𝑏. It remains to consider the case where 𝑆 contains exactly one of them. Suppose first that 𝑎 ∈ 𝑆 and 𝑏 ∉ 𝑆; the case 𝑏 ∈ 𝑆 and 𝑎 ∉ 𝑆 is symmetric. Let Õ 𝑐 𝑆 := 𝜂 = 𝜂|𝑆 ∩ 𝑅| ≤ (𝑚 − 2)𝜂. 𝑧∈𝑆∩𝑅

Define 𝐴 := Then,

2𝜆 , 3

𝐵 :=

𝑝 𝜂 (𝑆) = 𝐴 + 𝑐 𝑆 ,

𝜆 . 3

𝑞 𝜂 (𝑆) = 𝐵 + 𝑐 𝑆 .

The conditional response laws on 𝑆 are therefore the normalized laws 𝑄 ★𝑝 𝜂 ,𝑆 =

Õ 𝜂 𝐴 𝛿𝑎 + 𝛿𝑧 , 𝐴 + 𝑐𝑆 𝐴 + 𝑐𝑆

and

𝑧∈𝑆∩𝑅

𝑄 ★𝑞 𝜂 ,𝑆 =

Õ 𝜂 𝐵 𝛿𝑎 + 𝛿𝑧 . 𝐵 + 𝑐𝑆 𝐵 + 𝑐𝑆

All points outside 𝑈 have zero probability under both laws. We now compute their total variation distance. Since 𝐴 > 𝐵, we have 𝑐 𝑆 (𝐴 − 𝐵) 𝐴 𝐵 − = . 𝐴 + 𝑐𝑆 𝐵 + 𝑐𝑆 (𝐴 + 𝑐 𝑆 )(𝐵 + 𝑐 𝑆 ) For each 𝑧 ∈ 𝑆 ∩ 𝑅,

𝜂 𝜂 𝜂(𝐴 − 𝐵) − = . 𝐵 + 𝑐𝑆 𝐴 + 𝑐𝑆 (𝐴 + 𝑐 𝑆 )(𝐵 + 𝑐 𝑆 ) 13

𝑧∈𝑆∩𝑅

Summing over 𝑧 ∈ 𝑆 ∩ 𝑅 gives

Õ  𝑧∈𝑆∩𝑅

Therefore

𝜂 𝜂 𝑐 𝑆 (𝐴 − 𝐵) − = . 𝐵 + 𝑐𝑆 𝐴 + 𝑐𝑆 (𝐴 + 𝑐 𝑆 )(𝐵 + 𝑐 𝑆 )



𝑐 𝑆 (𝐴 − 𝐵) 𝑐 𝑆 (𝐴 − 𝐵) + (𝐴 + 𝑐 𝑆 )(𝐵 + 𝑐 𝑆 ) (𝐴 + 𝑐 𝑆 )(𝐵 + 𝑐 𝑆 ) 𝑐 𝑆 (𝐴 − 𝐵) = . (𝐴 + 𝑐 𝑆 )(𝐵 + 𝑐 𝑆 ) Substituting 𝐴 = 2𝜆/3 and 𝐵 = 𝜆/3 yields 1 𝑑TV (𝑄 ★𝑝 𝜂 ,𝑆 , 𝑄 ★𝑞 𝜂 ,𝑆 ) = 2



𝑑TV (𝑄 ★𝑝 𝜂 ,𝑆 , 𝑄 ★𝑞 𝜂 ,𝑆 ) =

𝑐 𝑆 (𝜆/3) . (2𝜆/3 + 𝑐 𝑆 )(𝜆/3 + 𝑐 𝑆 )

Since 𝑐 𝑆 ≥ 0 and 𝜆 ≥ 1/2, (2𝜆/3 + 𝑐 𝑆 )(𝜆/3 + 𝑐 𝑆 ) ≥ Thus 𝑑TV (𝑄 ★𝑝 𝜂 ,𝑆 , 𝑄 ★𝑞 𝜂 ,𝑆 ) ≤ Hence



2𝜆 𝜆 2𝜆2 · = . 3 3 9

𝑐 𝑆 (𝜆/3) 3𝑐 𝑆 = ≤ 3𝑐 𝑆 ≤ 3(𝑚 − 2)𝜂. 2𝜆 2𝜆2 /9

sup 𝑑TV (𝑄 ★𝑝 𝜂 ,𝑆 , 𝑄 ★𝑞 𝜂 ,𝑆 ) ≤ 3(𝑚 − 2)𝜂. 𝑆∈S

Suppose, for contradiction, that a uniform PAC learner exists for 𝒫𝑈+ . with accuracy 𝜀0 := 1/24 and confidence 2/3. Let 𝑇 be its worst-case query bound at parameters (𝜀0 , 1/3). Choose 𝜂 > 0 small enough that, in addition to 𝜆 ≥ 1/2, 3𝑇(𝑚 − 2)𝜂 <

1 . 6

By Lemma A.5, the transcript laws under targets 𝑝 𝜂 and 𝑞 𝜂 have total variation distance less than 1/6. On the other hand, the PAC guarantee gives Pr𝜂 𝑑TV (b 𝑝 , 𝑝 𝜂 ) ≤ 𝜀0 ≥



𝑝



2 3

and

Because 𝑑TV (𝑝 𝜂 , 𝑞 𝜂 ) ≥ the two balls

  2 Pr𝜂 𝑑TV (b 𝑝 , 𝑞 𝜂 ) ≤ 𝜀0 ≥ . 𝑞 3

1 1 > 2𝜀0 = , 6 12

{𝜇 : 𝑑TV (𝜇, 𝑝 𝜂 ) ≤ 𝜀0 },

{𝜇 : 𝑑TV (𝜇, 𝑞 𝜂 ) ≤ 𝜀0 }

are disjoint. Therefore, for the event 𝐸 := {𝑑TV (b 𝑝 , 𝑝 𝜂 ) ≤ 𝜀0 }, we have 2 Pr𝜂 (𝐸) ≥ , 𝑝 3

1 Pr𝜂 (𝐸) ≤ . 𝑞 3

Thus, the two transcript laws must differ by at least 1/3 in total variation, contradicting the upper bound < 1/6 we established before. Hence, no uniform PAC learner exists when CO(𝒮, 𝑈) is not complete. □ 14

4

Query Family Structure and Sample Complexity

The previous section established that for uniform PAC learning on an unknown support, qualitative learnability is characterized by the co-occurrence graph: learning is possible if and only if CO(𝒮, 𝑈) is complete. We now ask whether this qualitative topological condition also governs the quantitative sample complexity. The answer turns out to be negative. Completeness captures whether pairs can be calibrated somewhere, but it does not characterize how “cleanly” those comparisons are exposed. If cooccurrences only happen inside broad, hub-dominated sets, the relevant signal is heavily diluted, leading to worst-case sample complexities. Conversely, when the query family supports clean, localized comparisons, the learner can recursively decompose the domain to isolate subcategories and achieve near-ideal efficiency; we formalize this property as hierarchical comparability. We explore this surprisingly rich landscape in the remainder of the section. We first establish the ideal benchmark: maximal query power achieves the ordinary empirical rate of Θ(𝑛/𝜀2 ) e 2 /𝜀2 ) (Section 4.1). Moving to restricted families, we show that completeness alone guarantees a 𝑂(𝑛 sample complexity via a simulated Markov chain (Section 4.2). We prove this quadratic bound is worst-case optimal by constructing a hub-dominated family that requires Ω(𝑛 2 /𝜀2 ) queries (Theorem 4.3). However, we show that query families satisfying hierarchical comparability bypass 2 ) rate (Section 4.3). Next, we bridge these extremes, e this worst case to recover the near-linear 𝑂(𝑛/𝜀 proving the existence of complete query families whose optimal sample complexities tightly span e 1+𝛾 /𝜀2 ) for every 𝛾 ∈ (0, 1) (Section 4.4). Finally, we study the convergence rates the continuum Θ(𝑛 of pointwise-consistent algorithms (Section 4.5).

4.1

The Ideal Benchmark: Full Conditional Access

We first show the best possible rate when the learner has maximum query power. Folklore results show that by only querying [𝑛], the learner achieves TV error 𝜀 using 𝑂(𝑛/𝜀2 ) samples (see, e.g., [Can20a]). Thus, it is natural to ask whether the additional conditional querying power gives it an advantage. We show that this is not the case. Theorem 4.1. Let 𝒮 = 2[𝑛] \ {∅}. Then, for every sufficiently small 𝜀 it holds that ∗ 𝑞𝒮,𝒫 + (𝜀, 1/3) = Ω [𝑛]

𝑛 𝜀2

.

Proof. Without loss of generality, we assume that 𝑛 is even. Let 𝑚 = 𝑛/2 and partition [𝑛] into pairs 𝑃 𝑗 = {2𝑗 − 1, 2𝑗}. For 𝜎 ∈ {−1, +1}𝑚 and 𝛼 ∈ (0, 1/2], define 𝜎 𝑝2𝑗−1 =

1 + 𝛼𝜎 𝑗 𝑛

𝜎 𝑝2𝑗 =

,

1 − 𝛼𝜎 𝑗 𝑛

.

Let C ⊆ {−1, +1}𝑚 be the code from Lemma A.2. If 𝜎, 𝜏 ∈ C are distinct, then 𝑑TV (𝑝 𝜎 , 𝑝 𝜏 ) =

2𝛼 𝛼 𝑑𝐻 (𝜎, 𝜏) ≥ . 𝑛 4

Set 𝛼 = 16𝜀, so for 𝜀 ≤ 1/32 all code distributions are full support and pairwise 4𝜀-separated. 15

Fix any nonempty query set 𝑆 ⊆ [𝑛]. For 𝑖 ∈ [𝑛], define 𝜏𝑖 (𝜎) = 𝜎 𝑗 if 𝑖 = 2𝑗 − 1 and 𝜏𝑖 (𝜎) = −𝜎 𝑗 if 𝑖 = 2𝑗. Let 𝑃𝜎,𝑆 be the conditional response distribution under 𝑝 𝜎 and let 𝑈𝑆 be uniform on 𝑆. For 𝑖 ∈ 𝑆, 𝑃𝜎,𝑆 (𝑖) 1 + 𝛼𝜏𝑖 (𝜎) 1 Õ = , 𝜏𝑆 (𝜎) = 𝜏𝑖 (𝜎). 𝑈𝑆 (𝑖) 1 + 𝛼𝜏𝑆 (𝜎) |𝑆| 𝑖∈𝑆

Since |𝜏𝑖 | ≤ 1, |𝜏𝑆 | ≤ 1, and 𝛼 ≤ 1/2,

𝑃𝜎,𝑆 (𝑖) − 1 ≤ 4𝛼. 𝑈𝑆 (𝑖)

Using 𝑥 log 𝑥 ≤ (𝑥 − 1) + (𝑥 − 1)2 and the fact that the first-order term integrates to zero, DKL (𝑃𝜎,𝑆 ∥𝑈𝑆 ) ≤ 16𝛼2 . Now let Σ be uniform on C and let Π be the full transcript of any adaptive 𝑞-query learner, including its internal randomness. Conditional on any past history, the next query set is fixed. By Lemma A.4, the mutual information between Σ and the next response, conditional on that history, is at most 16𝛼2 . The chain rule gives 𝐼(Σ; Π) ≤ 16𝑞𝛼 2 . If the learner outputs b 𝑝 with 𝑑TV (b 𝑝 , 𝑝 Σ ) ≤ 𝜀 with probability at least 2/3 for every codeword, then nearest-neighbor decoding recovers Σ with probability at least 2/3 because the code distributions are 4𝜀-separated. By Lemma A.3, 𝐼(Σ; Π) ≥ 𝑐 1 𝑚 for a universal constant 𝑐1 > 0 and all sufficiently large 𝑚. Therefore 𝑞 ≥ 𝑐2

4.2

𝑛 𝑚 = Ω . 𝛼2 𝜀2

□

Worst-Case Complete Query Families

We now ask what quantitative rate can be guaranteed from the qualitative PAC condition alone. Suppose the query family 𝒮 induces a complete co-occurrence graph on the target support 𝑈. 2 )? e Does this topological condition automatically yield the ordinary-sampling rate 𝑂(|𝑈|/𝜀 We answer this negatively. While completeness is sufficient for PAC learnability, in the worst 2 /𝜀2 ) e case it guarantees only a quadratic rate. The upper bound below establishes a generic 𝑂(|𝑈| learner for any complete query family; the subsequent lower bound (Theorem 4.3) proves this dependence is unavoidable without further structural assumptions. Sampling via a simulated Markov chain. The algorithm achieves the quadratic bound by using conditional queries to simulate a reversible Markov chain whose stationary distribution is the unknown target 𝑝. Because CO(𝒮, 𝑈) is complete, every pair 𝑥, 𝑦 ∈ 𝑈 has at least one witness set 𝑊𝑥 𝑦 ∈ 𝒮 containing both points. Crucially, we symmetrize this choice so that 𝑊𝑥 𝑦 = 𝑊𝑦𝑥 . From a current state 𝑥, the random walk proposes a new state 𝑦 uniformly from 𝑈 \ {𝑥}, queries the witness set 𝑊𝑥 𝑦 , and transitions to 𝑦 only if the oracle returns 𝑦. This process requires just one query per step and visits states in proportion to their true masses without the learner needing to 16

estimate all conditional probabilities. The chain mixes in 𝑂(|𝑈| log(1/𝜀)) steps. By independently restarting the walk and recording the terminal states, the learner obtains approximate independent samples from 𝑝; the empirical distribution of these samples gives the claimed PAC bound. The formal algorithm is described in Algorithm 1. Algorithm 1: Markov Chain Sampling for Target Distribution 𝑝 Input: Universe 𝑈 of size 𝑚 ≥ 2, query access to witness sets 𝑊𝑥𝑦 ∈ 𝒮, target accuracy 𝜀 > 0, confidence 𝛿 > 0. Burn-in steps 𝐵 = ⌈(𝑚 − 1) log(2/𝜀)⌉, sample count 𝑀 = Θ((𝑚 + log(1/𝛿))/𝜀2 ). 1 Initialize an empty multiset 𝑆 ← ∅ 2 Fix an arbitrary starting state 𝑥 0 ∈ 𝑈. 3 for 𝑖 = 1 to 𝑀 do 4 Initialize 𝑥 ← 𝑥 0 . 5 for 𝑡 = 1 to 𝐵 do 6 Draw a candidate state 𝑦 uniformly at random from 𝑈 \ {𝑥} 7 Query 𝑊𝑥 𝑦 and receive a sample 𝑧 ∼ 𝑄 𝑝,𝑊𝑥 𝑦 8 if 𝑧 = 𝑦 then 9 𝑥←𝑦 /* Accept the proposed move */ 10 else 11 𝑥←𝑥 /* Reject and remain at current state */ 12 𝑆 ← 𝑆 ∪ {𝑥} /* Record the terminal state */ 13 return empirical distribution b 𝑝 of 𝑆

Theorem 4.2 (Complete co-occurrence graph quadratic learner). Let 𝑈 ⊆ [𝑛] be nonempty with |𝑈| = 𝑚 and suppose CO(𝒮, 𝑈) is complete. Then, 𝒮 PAC learns 𝒫𝑈 with query complexity ∗ 𝑞𝒮,𝒫 (𝜀, 𝛿) ≤ 𝐶 𝑈

𝑚(𝑚 + log(1/𝛿)) log(2/𝜀) 𝜀2

for an absolute constant 𝐶. Proof. Assume that CO(𝒮, 𝑈) is complete. We show that 𝒮 PAC learns 𝒫𝑈 = {𝑝 ∈ Δ([𝑛]) : 𝑝 𝑥 = 0 for all 𝑥 ∉ 𝑈}. Let 𝑚 := |𝑈|. If 𝑚 = 1, the learner outputs the point mass on the unique element of 𝑈, so assume 𝑚 ≥ 2. Since CO(𝒮, 𝑈) is complete, for every unordered pair {𝑥, 𝑦} ⊆ 𝑈, fix a symmetric witness set 𝑊𝑥 𝑦 = 𝑊𝑦𝑥 ∈ 𝒮 such that 𝑥, 𝑦 ∈ 𝑊𝑥 𝑦 . Fix an arbitrary target 𝑝 ∈ 𝒫𝑈 . The learner simulates a Markov chain on the state space 𝑈. From current state 𝑥 ∈ 𝑈, it chooses a challenger 𝑦 ∈ 𝑈 \ {𝑥} uniformly at random, queries 𝑊𝑥 𝑦 , and moves to 𝑦 if and only if the oracle response is 𝑦. Otherwise it stays at 𝑥. Equivalently, for 𝑥 ≠ 𝑦, 1 𝐾(𝑥, 𝑦) = 𝑄 𝑝,𝑊𝑥𝑦 (𝑦), 𝑚−1 where 𝑄 𝑝,𝑊𝑥 𝑦 is the one-query response law from the preliminaries. The diagonal probability is 𝐾(𝑥, 𝑥) = 1 −

Õ 𝑦∈𝑈\{𝑥}

17

𝐾(𝑥, 𝑦).

This definition is valid for every 𝑝 ∈ 𝒫𝑈 , including targets whose support is a strict subset of 𝑈, because 𝑄 𝑝,𝑆 is defined even when 𝑝(𝑆) = 0. We first show that 𝑝 is stationary for 𝐾. It suffices to verify detailed balance. Fix distinct 𝑥, 𝑦 ∈ 𝑈. If 𝑝(𝑊𝑥 𝑦 ) = 0, then since 𝑥, 𝑦 ∈ 𝑊𝑥 𝑦 and 𝑝 is nonnegative, we have 𝑝 𝑥 = 𝑝 𝑦 = 0. Therefore 𝑝 𝑥 𝐾(𝑥, 𝑦) = 𝑝 𝑦 𝐾(𝑦, 𝑥) = 0. If 𝑝(𝑊𝑥 𝑦 ) > 0, then the zero-mass convention is irrelevant and 𝑄 𝑝,𝑊𝑥 𝑦 (𝑦) =

𝑝𝑦 𝑝(𝑊𝑥 𝑦 )

Thus 𝑝 𝑥 𝐾(𝑥, 𝑦) =

,

𝑄 𝑝,𝑊𝑥𝑦 (𝑥) =

𝑝𝑥 . 𝑝(𝑊𝑥 𝑦 )

𝑝𝑥 𝑝𝑦 1 = 𝑝 𝑦 𝐾(𝑦, 𝑥). 𝑚 − 1 𝑝(𝑊𝑥 𝑦 )

Hence detailed balance holds for every pair 𝑥 ≠ 𝑦, and so 𝑝 is stationary for 𝐾. Next we prove a uniform minorization. We claim that for every 𝑥 ∈ 𝑈, 𝐾(𝑥, ·) ≥

1 𝑝(·) 𝑚−1

pointwise on 𝑈. First fix 𝑦 ≠ 𝑥. If 𝑝(𝑊𝑥 𝑦 ) > 0, then 𝐾(𝑥, 𝑦) =

𝑝𝑦 𝑝𝑦 1 ≥ , 𝑚 − 1 𝑝(𝑊𝑥 𝑦 ) 𝑚 − 1

because 𝑝(𝑊𝑥 𝑦 ) ≤ 1. If 𝑝(𝑊𝑥 𝑦 ) = 0, then 𝑝 𝑦 = 0, so the same inequality holds trivially. It remains to check the diagonal coordinate. If 𝑝 𝑥 = 0, then 𝐾(𝑥, 𝑥) ≥ 0 =

𝑝𝑥 . 𝑚−1

If 𝑝 𝑥 > 0, then for every challenger 𝑦 ≠ 𝑥, the set 𝑊𝑥 𝑦 has positive mass because it contains 𝑥. Therefore 𝑝𝑥 1 − 𝑄 𝑝,𝑊𝑥 𝑦 (𝑦) ≥ 𝑄 𝑝,𝑊𝑥𝑦 (𝑥) = ≥ 𝑝𝑥 . 𝑝(𝑊𝑥 𝑦 ) Averaging over the uniformly chosen challenger gives 𝐾(𝑥, 𝑥) =

𝑝𝑥 1 Õ 1 − 𝑄 𝑝,𝑊𝑥𝑦 (𝑦) ≥ 𝑝 𝑥 ≥ . 𝑚 − 1 𝑦≠𝑥 𝑚−1

This proves the minorization. The minorization implies rapid mixing (Lemma A.6). If 𝑚 = 2, then 𝐾(𝑥, ·) ≥ 𝑝(·) for every 𝑥 ∈ 𝑈, and since both sides have total mass one, this implies 𝐾(𝑥, ·) = 𝑝(·) for every 𝑥. Thus one step already has distribution 𝑝. 18

For 𝑚 > 2, define Π𝑝 to be the rank-one kernel whose every row is 𝑝. The minorization gives the Doeblin decomposition   1 1 𝐾= Π𝑝 + 1 − 𝑅, 𝑚−1 𝑚−1 where 𝑅 is a Markov kernel. Consequently, for every starting distribution 𝜇 on 𝑈, 1 𝑑𝑇𝑉 (𝜇𝐾 , 𝑝) ≤ 1 − 𝑚−1



𝑡

Set

𝑡

≤ 𝑒 −𝑡/(𝑚−1) .

2 𝐵 := (𝑚 − 1) log . 𝜀





Starting from any fixed state in 𝑈 and running the chain for 𝐵 steps produces a terminal distribution 𝜇𝐵 satisfying 𝜀 𝑑𝑇𝑉 (𝜇𝐵 , 𝑝) ≤ . 2 The learner independently restarts this simulated chain 𝑀 times, each time running it for 𝐵 steps, and records the terminal states. These terminal states are i.i.d. samples from 𝜇𝐵 . By the empirical distribution lemma (Lemma A.1), for a sufficiently large universal constant 𝐶, if 𝑀≥𝐶

𝑚 + log(1/𝛿) , 𝜀2

then with probability at least 1 − 𝛿, 𝑑𝑇𝑉 (b 𝑝 , 𝜇𝐵 ) ≤

𝜀 . 2

On this event, the triangle inequality gives 𝑑𝑇𝑉 (b 𝑝 , 𝑝) ≤ 𝑑𝑇𝑉 (b 𝑝 , 𝜇𝐵 ) + 𝑑𝑇𝑉 (𝜇𝐵 , 𝑝) ≤ 𝜀. Each approximate sample costs 𝐵 provider queries, so the total number of queries is 𝑚(𝑚 + log(1/𝛿)) log(2/𝜀) 𝑀𝐵 = 𝑂 . 𝜀2





Thus 𝒮 PAC learns 𝒫𝑈 whenever CO(𝒮, 𝑈) is complete.

□

Why the quadratic dependence can be necessary. The previous upper bound raises a natural question: is the quadratic dependence on |𝑈| an artifact of this Markov chain construction, or is it necessary for some 𝒮 that induce complete co-occurrence graphs? The next theorem shows that the quadratic bound is intrinsic in the worst case. Intuitively, this is because completeness shows that every pair co-occurs somewhere, but it does not show how informative those co-occurrences are. The hardness arises from hub dilution. We construct a query family where every allowed set 𝑆 ∈ 𝒮 contains a central “hub” element alongside a few “light” elements, ensuring the co-occurrence graph remains complete. In our hard family of distributions, the hub is assigned constant mass, while the light elements receive mass Θ(1/𝑛). Consequently, any conditional query returns the uninformative hub except for an 𝑂(1/𝑛)-fraction of the time. To observe a light element and 19

gain information about its true mass, the learner must waste Θ(𝑛) samples per query. Since the learner must calibrate Θ(𝑛) such light elements, this dilution forces the overall sample complexity to Ω(𝑛 2 /𝜀2 ). The proof relies on Fano’s inequality and coding-theoretic tools to make this intuition formal. Theorem 4.3 (Quadratic complexity). There exist absolute constants 𝑐 > 0 and 𝑛0 ∈ N such that for every 𝑛 ≥ 𝑛0 , there exists a query family 𝒮 on [𝑛] with complete co-occurrence graph such that, for all 0 < 𝜀 ≤ 𝑐, 𝑛2 . 𝑞★ (𝜀, 1/3) ≥ 𝑐 + 𝒮,𝒫[𝑛] 𝜀2 Proof. Let 𝑛 = 2𝑚 + 1 and define [𝑛] = {0} ∪ {𝑎 1 , 𝑏1 , . . . , 𝑎 𝑚 , 𝑏 𝑚 }. Define the allowed query family S = {𝑆 𝑗 𝑘 : 1 ≤ 𝑗 < 𝑘 ≤ 𝑚},

𝑆 𝑗 𝑘 = {0, 𝑎 𝑗 , 𝑏 𝑗 , 𝑎 𝑘 , 𝑏 𝑘 }.

The co-occurrence graph is complete: vertices from different pairs co-occur in the corresponding 𝑆 𝑗 𝑘 , vertices within the same pair co-occur in any 𝑆 𝑗 𝑘 with 𝑘 ≠ 𝑗, and the hub 0 co-occurs with every other vertex. For 𝜎 ∈ {−1, +1}𝑚 and 𝛼 ∈ (0, 1/2], define 1 𝑝 𝜎 (0) = , 2

𝑝 𝜎 (𝑎 𝑗 ) =

1 + 𝛼𝜎 𝑗 4𝑚

,

𝑝 𝜎 (𝑏 𝑗 ) =

1 − 𝛼𝜎 𝑗 4𝑚

.

Let C ⊆ {−1, +1}𝑚 be the code from Lemma A.2. If 𝜎, 𝜏 ∈ C are distinct, then each differing coordinate contributes 𝛼/(2𝑚) to TV distance, so 𝑑TV (𝑝 𝜎 , 𝑝 𝜏 ) =

𝛼 𝛼 𝑑𝐻 (𝜎, 𝜏) ≥ . 2𝑚 8

Set 𝛼 = 32𝜀, assuming 𝜀 ≤ 1/64. Then, the code distributions are 4𝜀-separated. Fix a query 𝑆 𝑗 𝑘 . Let 𝑄 𝑗 𝑘 be the baseline distribution on 𝑆 𝑗 𝑘 with 𝑄 𝑗 𝑘 (0) =

𝑚 , 𝑚+2

𝑄 𝑗 𝑘 (𝑎 𝑗 ) = 𝑄 𝑗 𝑘 (𝑏 𝑗 ) = 𝑄 𝑗 𝑘 (𝑎 𝑘 ) = 𝑄 𝑗 𝑘 (𝑏 𝑘 ) =

The conditional law under 𝑝 𝜎 is 𝑃 𝑗𝜎𝑘 (0) = 𝑃 𝑗𝜎𝑘 (𝑎 𝑗 ) =

1 + 𝛼𝜎 𝑗 2(𝑚 + 2)

𝑚 , 𝑚+2 𝑃 𝑗𝜎𝑘 (𝑏 𝑗 ) =

,

1 − 𝛼𝜎 𝑗 2(𝑚 + 2)

1 . 2(𝑚 + 2)

,

and similarly for the pair 𝑘. Therefore DKL (𝑃 𝑗𝜎𝑘 ∥𝑄 𝑗 𝑘 ) =

(1 + 𝛼) log(1 + 𝛼) + (1 − 𝛼) log(1 − 𝛼) . 𝑚+2

For |𝛼| ≤ 1/2, the numerator is at most 2𝛼2 , hence DKL (𝑃 𝑗𝜎𝑘 ∥𝑄 𝑗 𝑘 ) ≤ 20

2𝛼2 . 𝑚+2

Let Σ be uniform on C and let Π be the transcript of any adaptive 𝑞-query learner. Conditional on any history, the next query is some fixed 𝑆 𝑗 𝑘 . By Lemma A.4, the conditional mutual information between Σ and the next response is at most 2𝛼2 /(𝑚 + 2). Therefore, 𝐼(Σ; Π) ≤

2𝑞𝛼2 . 𝑚+2

A learner that succeeds to TV error 𝜀 with probability at least 2/3 permits nearest-neighbor decoding of Σ with error probability at most 1/3. By Fano, 𝐼(Σ; Π) ≥ 𝑐 0 𝑚 for a universal 𝑐0 > 0. Combining the two bounds yields 𝑚(𝑚 + 2) 𝑛2 = Ω . 𝑞 ≥ 𝑐1 𝛼2 𝜀2





Pair 𝑗

𝑎𝑗

𝑏𝑗

Query Set 𝑆 𝑗 𝑘

Query Set 𝑆 𝑗ℓ

0 𝑎𝑘 Pair 𝑘

𝑎ℓ

Hub (Mass 1/2)

𝑏𝑘

𝑏ℓ

Pair ℓ

Figure 2: Visualization of the complete co-occurrence lower bound instance. Solid, brightly colored regions represent the query sets 𝑆 𝑗 𝑘 and 𝑆 𝑗ℓ , which intersect exactly at the hub 0 and pair 𝑗.

□

4.3

Faster Query Families: Hierarchical Comparability

Having established the range in which the optimal sample complexity lies, we seek to understand for which 𝒮 the near-linear rate is attainable. Our main contribution is a general sufficient condition that enables this rate and is based on the ability to recursively decompose the target support into sets that are (implicitly) queryable. The following definitions are useful. Definition 4 (Balanced binary partition tree). A binary partition tree 𝒯 over a finite set 𝑈 is a rooted binary tree whose nodes are nonempty subsets of 𝑈. Specifically, the root is 𝑈, the leaves are singletons {𝑥} for 𝑥 ∈ 𝑈, and each internal node 𝐶 is partitioned by its two children 𝐶 𝐿 , 𝐶 𝑅 (i.e., 𝐶 𝐿 ∪ 𝐶 𝑅 = 𝐶 and 𝐶 𝐿 ∩ 𝐶 𝑅 = ∅). We say 𝒯 is balanced if its depth is 𝑂(log |𝑈|). 21

Definition 5 (Hierarchical Comparability). Let 𝑈 ⊆ [𝑛], and let 𝒮 ⊆ 2𝑈 \ {∅} be a family of allowed query sets. We say that 𝒮 is hierarchically comparable on 𝑈 if there exists a balanced binary partition tree 𝒯 over 𝑈 such that for every internal node 𝐶 ∈ 𝒯 and every unordered pair {𝑥, 𝑦} ⊆ 𝐶, there exists 𝑊𝐶 ({𝑥, 𝑦}) ∈ 𝒮 satisfying {𝑥, 𝑦} ⊆ 𝑊𝐶 ({𝑥, 𝑦}) ⊆ 𝐶. Equivalently, every pair of elements inside every tree cell can be compared using a query set that stays inside that cell.

Remark 2. We note that this property depends solely on 𝑈, 𝒮 and not the target distribution. Many natural query families satisfy it, including pairwise queries, hierarchical category menus, and geometric families such as intervals, boxes, and subcubes. We provide more concrete examples in Appendix B. Theorem 4.4 (Near-linear learning from tree-local completeness). Let 𝑈 ⊆ [𝑛] be nonempty with |𝑈| = 𝑚 and suppose 𝒮 is hierarchically comparable on 𝑈. Then, for an absolute constant 𝐶, 𝒮 PAC learns 𝒫𝑈 with query complexity 𝑚(log 𝑚)2 log(𝑚/𝛿) ∗ . 𝑞𝒮,𝒫 (𝜀, 𝛿) ≤ 𝐶 𝑈 𝜀2 The following corollary follows immediately from Theorem 4.4. Corollary 4.5 (Pairwise queries have a nearly linear PAC rate). For the pairwise query family 𝒮 = [𝑛]
∗ on any nonempty support 𝑈 ⊆ [𝑛] of size 𝑚, the PAC query complexity satisfies 𝑞 𝒮,𝒫 (𝜀, 𝛿) ≤ 2 𝐶𝑚(log 𝑚)2 log(𝑚/𝛿)/𝜀2 for an absolute constant 𝐶.

𝑈

To get some intuition for the proof, fix a balanced binary tree over the domain. Each internal node 𝐶 is split into two children 𝐶 𝐿 and 𝐶 𝑅 , and the goal at that node is to estimate the fraction of mass in the left child, 𝑝(𝐶 𝐿 | 𝐶). Once these split probabilities are known for all internal nodes, the distribution is obtained by multiplying the corresponding split probabilities along each root-to-leaf path. The main challenge is that the learner cannot directly sample from 𝑝(· | 𝐶). Fortunately, due to Definition 5 it turns out we can simulate such local sampling indirectly. Inside each node 𝐶, the learner runs a local random walk by querying an appropriate set 𝑆 ∈ 𝒮. This walk has stationary distribution 𝑝(· | 𝐶), so the fraction of time it spends in 𝐶 𝐿 estimates the desired split. The bulk of the technical work is to show that due to the nature of the estimation problem we do not need to restart this chain every time we obtain a sample; a Bernstein bound establishes the estimation error. Repeating this across all nodes of the tree gives a recursive estimator for the entire distribution. The algorithm is presented in Algorithm 2 and Section 4.3.1 is devoted to the proof of this result. 4.3.1

Proof of Theorem 4.4

The proof works for the support class 𝒫𝑈 , so the target may have zero-mass points inside 𝑈. Let 𝑚 := |𝑈|. If 𝑚 = 1, the learner outputs the unique point mass, so assume 𝑚 ≥ 2. Fix a balanced binary partition tree T over 𝑈 witnessing hierarchical comparability. Let 𝐷 denote the

22

Algorithm 2: Tree-Based Recursive Learner under Hierarchical Comparability Input: Ambient set 𝑈 of size 𝑚, a supply network 𝒮 hierarchically comparable on 𝑈, target accuracy 𝜀 > 0, confidence 𝛿 > 0. Data: A witnessing balanced binary partition tree T over 𝑈; witnesses 𝑊𝐶 ({𝑥, 𝑦}) for all internal nodes 𝐶 and pairs {𝑥, 𝑦} ⊆ 𝐶; node error budget 𝜏 = Θ(𝜀2 /𝐷); node confidence 𝛿 𝐶 = 𝛿/(2𝑚). 1 for each internal node 𝐶 ∈ T do 2 Let 𝐶 𝐿 , 𝐶 𝑅 be the children of 𝐶, and let 𝑘 = |𝐶| 3 𝐵𝐶 ← ⌈(𝑘 − 1) log(4/𝛿 𝐶 )⌉ /* Burn-in steps */
4 𝑀𝐶 ← Θ 𝑘 log(4/𝛿 𝐶 )/𝜏 /* Estimation steps */ 5 Choose an arbitrary starting state 𝑥 ∈ 𝐶 /* Phase 1: 6 7 8 9

/* Phase 2: 10 11 12 13 14 15 16 17

Burn-in

*/

for 𝑡 = 1 to 𝐵𝐶 do Draw challenger 𝑦 uniformly from 𝐶 \ {𝑥} Query 𝑊𝐶 ({𝑥, 𝑦}) and receive 𝑧 ∼ 𝑄 𝑝,𝑊𝐶 ({𝑥,𝑦}) if 𝑧 = 𝑦 then 𝑥 ← 𝑦 Estimate the left-child occupation

*/

ℎ𝑖𝑡𝑠 ← 0 for 𝑡 = 1 to 𝑀𝐶 do Draw challenger 𝑦 uniformly from 𝐶 \ {𝑥} Query 𝑊𝐶 ({𝑥, 𝑦}) and receive 𝑧 ∼ 𝑄 𝑝,𝑊𝐶 ({𝑥,𝑦}) if 𝑧 = 𝑦 then 𝑥 ← 𝑦 if 𝑥 ∈ 𝐶 𝐿 then ℎ𝑖𝑡𝑠 ← ℎ𝑖𝑡𝑠 + 1 𝛼 𝐶 ← ℎ𝑖𝑡𝑠/𝑀𝐶   b 𝛼 𝐶 ← min 1 − 𝜏4 , max 𝜏4 , 𝛼 𝐶 /* Reconstruct full distribution via path products

*/

for each leaf 𝑣 ∈ 𝑈 do b 19 𝑝𝑣 ← 1 20 for each internal node 𝐶 on the root-to-𝑣 path do 21 if 𝑣 ∈ 𝐶 𝐿 then b 22 𝑝𝑣 ← b 𝑝𝑣 · b 𝛼𝐶 23 else b 24 𝑝𝑣 ← b 𝑝 𝑣 · (1 − b 𝛼𝐶 ) 25 return reconstructed distribution b 𝑝 18

depth of T, so 𝐷 = 𝑂(log 𝑚). For every internal node 𝐶 ∈ T and every unordered pair {𝑥, 𝑦} ⊆ 𝐶, fix a witness set 𝑊𝐶 ({𝑥, 𝑦}) ∈ 𝒮

such that

{𝑥, 𝑦} ⊆ 𝑊𝐶 ({𝑥, 𝑦}) ⊆ 𝐶.

The witness is symmetric in 𝑥, 𝑦 because it is indexed by the unordered pair {𝑥, 𝑦}. For a node 𝐶 with 𝑝(𝐶) > 0, define 𝑝 𝐶 (𝑥) := 𝑝(𝑥 | 𝐶) =

𝑝𝑥 , 𝑝(𝐶)

and define the split parameter 𝛼 𝐶 := 𝑝(𝐶 𝐿 | 𝐶) = 23

𝑥 ∈ 𝐶,

𝑝(𝐶 𝐿 ) . 𝑝(𝐶)

If 𝑝(𝐶) = 0, the value of 𝛼 𝐶 is irrelevant and may be chosen arbitrarily. Such nodes contribute zero mass to the error decomposition below. Lemma 4.6 (Tree KL chain rule with zero-mass nodes). Suppose that for every internal node 𝐶 we have an estimate b 𝛼 𝐶 ∈ (0, 1) and reconstruct a leaf distribution b 𝑝 by multiplying the estimated split probabilities along each root-to-leaf path. Then 𝐷KL (𝑝∥b 𝑝) =

Õ 𝐶∈ℐ (T): 𝑝(𝐶)>0

𝛼 𝐶 )) , 𝑝(𝐶) 𝐷KL (Bern(𝛼 𝐶 ) ∥ Bern(b

where ℐ (T) denotes the set of internal nodes of T. Consequently, 𝑑𝑇𝑉 (𝑝, b 𝑝) ≤

v t

1 2

Õ 𝐶∈ℐ (T): 𝑝(𝐶)>0

𝛼 𝐶 )). 𝑝(𝐶) 𝐷KL (Bern(𝛼 𝐶 ) ∥ Bern(b

Proof. For a leaf 𝑥 with 𝑝 𝑥 > 0, all nodes on the root-to-𝑥 path have positive 𝑝-mass. Write 𝑝𝑥 =

Ö

𝛽 𝐶 (𝑥),

b 𝑝𝑥 =

𝐶∋𝑥

Ö

b 𝛽 𝐶 (𝑥),

𝐶∋𝑥

where 𝛽 𝐶 (𝑥) = 𝛼 𝐶 if 𝑥 ∈ 𝐶 𝐿 and 𝛽 𝐶 (𝑥) = 1 − 𝛼 𝐶 if 𝑥 ∈ 𝐶 𝑅 , and similarly for b 𝛽 𝐶 (𝑥) using b 𝛼 𝐶 . Hence log

𝑝𝑥 Õ 𝛽 𝐶 (𝑥) . = log b b 𝑝 𝑥 𝐶∋𝑥 𝛽 𝐶 (𝑥)

Taking expectation under 𝑝 and exchanging the finite sums gives 𝐷KL (𝑝∥b 𝑝) = =

Õ

Õ

𝑝 𝑥 log

𝐶: 𝑝(𝐶)>0 𝑥∈𝐶

Õ 𝐶: 𝑝(𝐶)>0

𝛽 𝐶 (𝑥)

b 𝛽 𝐶 (𝑥)

𝛼𝐶 1 − 𝛼𝐶 𝑝(𝐶) 𝛼 𝐶 log . + (1 − 𝛼 𝐶 ) log b 1−b 𝛼𝐶 𝛼𝐶





This is the desired identity. Pinsker’s inequality gives the total-variation bound.

□

A local chain for estimating a split. Fix an internal node 𝐶 with 𝑝(𝐶) > 0 and 𝑘 := |𝐶| ≥ 2. We define a Markov chain 𝐾 𝐶 on the state space 𝐶. From current state 𝑥 ∈ 𝐶, choose a challenger 𝑦 uniformly from 𝐶 \ {𝑥}, query the tree-local witness set 𝑊𝐶 ({𝑥, 𝑦}), and move to 𝑦 if and only if the oracle response is 𝑦. Otherwise, stay at 𝑥. Equivalently, for 𝑥 ≠ 𝑦, 1 𝐾 𝐶 (𝑥, 𝑦) = 𝑄 𝑝,𝑊𝐶 ({𝑥,𝑦}) (𝑦), 𝑘−1 where 𝑄 𝑝,𝑊𝐶 ({𝑥,𝑦}) is the one-query response law from the preliminaries. This definition is valid even when 𝑝(𝑊𝐶 ({𝑥, 𝑦})) = 0. If 𝑘 = 2, then the unique challenger is the other point of 𝐶, and a direct calculation gives 𝐾 𝐶 (𝑥, ·) = 𝑝 𝐶 (·) for every 𝑥 ∈ 𝐶. Hence the mixing and spectral-gap conclusions hold immediately. Assume below that 𝑘 > 2. 24

Lemma 4.7 (Stationarity and minorization of the local chain). For every positive-mass node 𝐶, the conditional distribution 𝑝 𝐶 is stationary and reversible for 𝐾 𝐶 . Moreover, for every 𝑥 ∈ 𝐶, 𝐾 𝐶 (𝑥, ·) ≥ pointwise on 𝐶. Consequently,

1 𝑝 𝐶 (·) 𝑘−1

𝑑𝑇𝑉 (𝐾 𝐶𝑡 (𝑥, ·), 𝑝 𝐶 ) ≤ 𝑒 −𝑡/(𝑘−1)

for every starting state 𝑥 ∈ 𝐶, and the spectral gap of 𝐾 𝐶 is at least 1/(𝑘 − 1). Proof. We first prove reversibility. Fix distinct 𝑥, 𝑦 ∈ 𝐶 and let 𝑊 := 𝑊𝐶 ({𝑥, 𝑦}). By hierarchical comparability, 𝑥, 𝑦 ∈ 𝑊 ⊆ 𝐶. If 𝑝(𝑊) = 0, then since 𝑥, 𝑦 ∈ 𝑊 and 𝑝 is nonnegative, we have 𝑝 𝑥 = 𝑝 𝑦 = 0. Therefore 𝑝 𝐶 (𝑥)𝐾 𝐶 (𝑥, 𝑦) = 𝑝 𝐶 (𝑦)𝐾 𝐶 (𝑦, 𝑥) = 0. If 𝑝(𝑊) > 0, then the zero-mass convention is irrelevant and 𝑄 𝑝,𝑊 (𝑦) = Hence

𝑝𝑦 𝑝(𝑊)

,

𝑄 𝑝,𝑊 (𝑥) =

𝑝𝑥 . 𝑝(𝑊)

𝑝𝑦 𝑝𝑥 1 𝑝(𝐶) 𝑘 − 1 𝑝(𝑊) 𝑝𝑦 𝑝𝑥 1 = = 𝑝 𝐶 (𝑦)𝐾 𝐶 (𝑦, 𝑥). 𝑝(𝐶) 𝑘 − 1 𝑝(𝑊)

𝑝 𝐶 (𝑥)𝐾 𝐶 (𝑥, 𝑦) =

Thus detailed balance holds for every pair 𝑥 ≠ 𝑦, and so 𝑝 𝐶 is stationary and reversible for 𝐾 𝐶 . We next prove the minorization. Fix 𝑥 ∈ 𝐶. First consider 𝑦 ≠ 𝑥 and again write 𝑊 := 𝑊𝐶 ({𝑥, 𝑦}). If 𝑝(𝑊) > 0, then 𝐾 𝐶 (𝑥, 𝑦) =

𝑝𝑦 𝑝𝑦 𝑝 𝐶 (𝑦) 1 ≥ = , 𝑘 − 1 𝑝(𝑊) (𝑘 − 1)𝑝(𝐶) 𝑘−1

because 𝑊 ⊆ 𝐶 implies 𝑝(𝑊) ≤ 𝑝(𝐶). If 𝑝(𝑊) = 0, then 𝑝 𝑦 = 0, so the same inequality holds trivially. It remains to check the diagonal coordinate. If 𝑝 𝑥 = 0, then 𝐾 𝐶 (𝑥, 𝑥) ≥ 0 =

𝑝 𝐶 (𝑥) . 𝑘−1

If 𝑝 𝑥 > 0, then for every challenger 𝑦 ≠ 𝑥, the witness set 𝑊𝐶 ({𝑥, 𝑦}) has positive mass because it contains 𝑥. Therefore 1 − 𝑄 𝑝,𝑊𝐶 ({𝑥,𝑦}) (𝑦) ≥ 𝑄 𝑝,𝑊𝐶 ({𝑥,𝑦}) (𝑥) = 25

𝑝𝑥 𝑝𝑥 ≥ = 𝑝 𝐶 (𝑥), 𝑝(𝑊𝐶 ({𝑥, 𝑦})) 𝑝(𝐶)

where the last inequality uses 𝑊𝐶 ({𝑥, 𝑦}) ⊆ 𝐶. Averaging over 𝑦 ∈ 𝐶 \ {𝑥} gives 𝐾 𝐶 (𝑥, 𝑥) =

𝑝 𝐶 (𝑥) 1 Õ 1 − 𝑄 𝑝,𝑊𝐶 ({𝑥,𝑦}) (𝑦) ≥ 𝑝 𝐶 (𝑥) ≥ . 𝑘 − 1 𝑦≠𝑥 𝑘−1

Thus the pointwise minorization holds. The minorization yields a Doeblin decomposition 1 1 Π𝐶 + 1 − 𝑅𝐶 , 𝐾𝐶 = 𝑘−1 𝑘−1





where Π𝐶 is the rank-one kernel whose every row is 𝑝 𝐶 , and 𝑅 𝐶 is a Markov kernel. Hence 𝑑𝑇𝑉 (𝐾 𝐶𝑡 (𝑥, ·), 𝑝 𝐶 ) ≤



1 1− 𝑘−1

𝑡

≤ 𝑒 −𝑡/(𝑘−1) .

Since 𝐾 𝐶 is reversible, the same Doeblin contraction gives absolute spectral gap at least 1/(𝑘 − 1).

□

We use the following standard Bernstein inequality for stationary reversible chains with spectral gap; see, for example, [JSF18]. Proposition 4.8 (Bernstein inequality for the local chain). There is a universal constant 𝑐 𝐵 > 0 such that if (𝑋𝑡 ) is stationary, reversible, has invariant law 𝜋, and has absolute spectral gap at least 𝛾, then for every 0 ≤ 𝑓 ≤ 1 with mean 𝜇 and variance 𝜎2 ,

"

𝑀

#

𝑀𝛾𝑢 2 1 Õ Pr 𝑓 (𝑋𝑡 ) − 𝜇 > 𝑢 ≤ 2 exp −𝑐 𝐵 2 . 𝑀 𝜎 +𝑢





𝑡=1

One-node split estimation. At a positive-mass node 𝐶, the goal is to estimate 𝛼 𝐶 = 𝑝(𝐶 𝐿 | 𝐶). Run the local chain for

4 𝐵𝐶 := (𝑘 − 1) log 𝛿𝐶





burn-in steps. Then, run it for 𝑀𝐶 additional steps and define 𝑀𝐶

𝛼 𝐶 :=

1 Õ 1{𝑋𝑡 ∈ 𝐶 𝐿 }. 𝑀𝐶 𝑡=1

For a node KL budget 𝜏𝐶 ∈ (0, 1/16], clip

n𝜏 oo 𝜏𝐶 𝐶 b , max , 𝛼𝐶 . 𝛼 𝐶 := min 1 − 4 4 n

Lemma 4.9 (One-node KL estimate). There are universal constants 𝐴, 𝐶 > 0 such that the following hold. Fix a positive-mass internal node 𝐶 of size 𝑘, a node budget 𝜏𝐶 ∈ (0, 1/16], and a failure probability 𝛿 𝐶 ∈ (0, 1). If 𝑘 log(4/𝛿 𝐶 ) 𝑀𝐶 ≥ 𝐶 , 𝜏𝐶 26

then the clipped estimator above satisfies 𝛼 𝐶 )) > 𝐴𝜏𝐶 ] ≤ 𝛿 𝐶 . Pr[𝐷KL (Bern(𝛼 𝐶 ) ∥ Bern(b The number of queries used at node 𝐶 is 𝑘 log(4/𝛿 𝐶 ) 1 𝑂 𝑘 log + . 𝛿𝐶 𝜏𝐶





Proof. By Lemma 4.7, after 𝐵𝐶 burn-in steps the current-state law is within 𝛿 𝐶 /4 in total variation of stationarity. Since the subsequent path is obtained by applying a Markov kernel to the initial state, the law of the length-𝑀𝐶 path is also within 𝛿 𝐶 /4 of the stationary path law. For a stationary copy of the chain, apply Proposition 4.8 with 𝑓 (𝑥) = 1{𝑥 ∈ 𝐶 𝐿 },

𝜎2 = 𝛼 𝐶 (1 − 𝛼 𝐶 ),

𝜇 = 𝛼𝐶 ,

𝛾≥

1 . 𝑘−1

With 𝐶 sufficiently large, the displayed choice of 𝑀𝐶 implies that, with probability at least 1 − 𝛿 𝐶 /2 under the stationary path law, |𝛼 𝐶 − 𝛼 𝐶 | ≤

1p 𝜏𝐶 𝛼 𝐶 (1 − 𝛼 𝐶 )𝜏𝐶 + . 64 64

Adding the burn-in discrepancy gives this event with probability at least 1 − 𝛿 𝐶 for the actual run. It remains to convert the additive event into Bernoulli KL control. We record thepstandard argument. If 𝛼 𝐶 ∈ [8𝜏𝐶 , 1 − 8𝜏𝐶 ], then the additive error is at most a small constant times 𝛼 𝐶 (1 − 𝛼 𝐶 )𝜏𝐶 , no clipping occurs, and 𝐷KL (Bern(𝛼 𝐶 ) ∥ Bern(b 𝛼 𝐶 )) ≤ 𝑂(𝜏𝐶 ). If 𝛼 𝐶 < 8𝜏𝐶 , then the additive event implies 𝛼 𝐶 ≤ 9𝜏𝐶 , so after clipping

b 𝛼 𝐶 ∈ [𝜏𝐶 /4, 9𝜏𝐶 ]. Both Bernoulli parameters are then 𝑂(𝜏𝐶 ), and the Bernoulli KL is again 𝑂(𝜏𝐶 ). The case 𝛼 𝐶 > 1 − 8𝜏𝐶 is symmetric. Taking 𝐴 large enough proves the lemma. □ The recursive estimator. For a node 𝐶 at level ℓ , set 𝜏𝐶 :=

𝜀2 , 4𝐴𝐷

where 𝐴 is the constant from Lemma 4.9, and 𝛿 𝐶 :=

𝛿 . 2𝑚

The learner runs the one-node procedure at every internal node of the tree. If a node has zero mass, the output split is irrelevant for the analysis; the algorithm need not know which nodes have zero mass. Reconstruct b 𝑝 from the estimated splits by multiplying estimated split probabilities along root-to-leaf paths. 27

By Lemma 4.9 and a union bound over at most 𝑚 − 1 internal nodes, with probability at least 1 − 𝛿, every positive-mass internal node 𝐶 satisfies 𝛼 𝐶 )) ≤ 𝐴𝜏𝐶 = 𝐷KL (Bern(𝛼 𝐶 ) ∥ Bern(b

𝜀2 . 4𝐷

On this event, Lemma 4.6 gives 𝐷KL (𝑝∥b 𝑝) ≤

≤

𝐷−1 Õ

Õ

𝑝(𝐶)

ℓ =0 𝐶 at level ℓ 𝑝(𝐶)>0 𝐷−1 Õ ℓ =0

𝜀2 4𝐷

𝜀2 𝜀2 = , 4𝐷 4

because the internal nodes at a fixed level are pairwise disjoint, so their total mass is at most one. Pinsker’s inequality yields r 1 𝑑𝑇𝑉 (𝑝, b 𝑝) ≤ 𝐷KL (𝑝∥b 𝑝 ) ≤ 𝜀. 2 It remains to count queries. The internal nodes at a fixed level are pairwise disjoint, so the sum of their cardinalities is at most 𝑚. Since 𝜏𝐶 =

𝜀2 4𝐴𝐷

for all nodes, the total provider-query cost on one level is 𝑚 log(𝑚/𝛿) 𝑚𝐷 log(𝑚/𝛿) 𝑂 =𝑂 . 𝜏𝐶 𝜀2









Summing over the 𝐷 = 𝑂(log 𝑚) levels gives 𝑚𝐷 2 log(𝑚/𝛿) 𝑚(log 𝑚)2 log(𝑚/𝛿) 𝑂 = 𝑂 . 𝜀2 𝜀2









This proves Theorem 4.4.

4.4

A Continuum of Optimal Sample Complexities

So far we have shown that whenever PAC learning is possible the sample complexity cannot be ˜ 2 /𝜀2 ). Moreover, there are families 𝒮 for which Ω(𝑛 2 /𝜀2 ) samples are necessary, worse than 𝑂(𝑛 and for more well-structured 𝒮 the learner can achieve Θ̃(𝑛/𝜀2 ) sample complexity. Thus, it is natural to ask if intermediate sample complexities of the form Θ̃(𝑛 1+𝛾 /𝜀2 ) can arise as optimal bounds for certain 𝒮. Our next result shows that this is indeed the case. The proof relies on a generalization of our quadratic lower bound construction and is deferred to Appendix C. Theorem 4.10 (Continuum of optimal polynomial rates). There exist universal constants 𝑐 1 , 𝑐2 , 𝜀0 > 0 such that for every exponent 𝛾 ∈ (0, 1), there exists some 𝑁𝛾 where for all 𝑛 ≥ 𝑁𝛾 , one can construct a query family 𝒮 on [𝑛] satisfying 𝑐1

𝑛 1+𝛾 log(1/𝜀) log 𝑛 𝑛 1+𝛾 ★ ≤ 𝑞 (𝜀, 1/3) ≤ 𝑐 2 𝒮,𝒫[𝑛] 𝜀2 𝜀2 28

for all 0 < 𝜀 ≤ 𝜀0 . In particular, this yields an optimal sample complexity of

e 𝑞★ (𝜀, 1/3) = Θ 𝒮,𝒫[𝑛]



𝑛 1+𝛾 . 𝜀2



Remark 3 (The structural parameter behind the intermediate rates). The construction in Theorem 4.10 has a natural two-scale structure. Contract each internally queryable block 𝐴 𝑗 and 𝐵 𝑗 to a single coarse atom, while keeping the hub 0 as a singleton, and let 𝐻 denote the number of atoms in the resulting coarse domain. Thus, 𝐻 is the size of the quotient obtained after contracting the fine blocks. Learning the lifted distribution consists of two statistical tasks. First, the learner must recover the conditional distributions within the blocks, whose total dimension is 𝑛 and whose cost is 2 ). Second, it must recover the masses of the 𝐻 coarse atoms. The induced query family on e Θ(𝑛/𝜀 e 2 /𝜀2 ). Consequently, the block-lifted these atoms is the hub-diluted hard family, whose cost is Θ(𝐻 family has optimal rate   2 𝑛 + 𝐻 e Θ . 𝜀2 For the family in Theorem 4.10, we choose 𝐻 ≍ 𝑛 (1+𝛾)/2 , which proves the result.

4.5

Distribution-Dependent Rates for Pointwise Consistency

We conclude this section by providing a bound on the pointwise-consistency rates √of our task. Our result here shows that whenever learning is possible, the error rate decays as 𝐶/ 𝑡, for some distribution-dependent constant 𝐶, where 𝑡 is the number of samples the learner is using. Theorem 4.11 (Distribution-dependent pointwise rate). Let 𝑈 ⊆ [𝑛] be nonempty and suppose that CO(𝒮, 𝑈) is connected. There exists a single sequence of learners (𝐴𝑡 )𝑡≥1 such that, for every target 𝑝 ∈ 𝒫𝑈+ , there is a finite constant 𝐶 𝑝,𝒮,𝑈 > 0 satisfying the following: for every 𝜀 ∈ (0, 1) and 𝛿 ∈ (0, 1/2), 𝑡 ≥ 𝐶 𝑝,𝒮,𝑈

log(1/𝛿) 𝜀2

implies P𝑝 𝑑TV (𝐴𝑡 , 𝑝) ≤ 𝜀 ≥ 1 − 𝛿.





Proof. We use the spanning-tree learner from the proof of Theorem 3.1. The case |𝑈| = 1 is immediate, so let 𝑚 := |𝑈| ≥ 2. Fix a rooted spanning tree 𝒯 of CO(𝒮, 𝑈) and a witness set 𝑆 𝑒 ∈ 𝒮 for every directed tree edge 𝑒 = (𝑢 → 𝑣). For an endpoint 𝑦 ∈ {𝑢, 𝑣} of an edge 𝑒, define 𝜃𝑒 (𝑦) := 𝑝(𝑦 | 𝑆 𝑒 ). Because 𝑝 ∈ 𝒫𝑈+ , every one of these quantities is strictly positive. Collect the 2(𝑚 − 1) endpoint probabilities into a vector 𝜃(𝑝).

29

Let 𝐹 denote the deterministic reconstruction map used in the spanning-tree learner: given positive endpoint probabilities, it forms the corresponding edge ratios, multiplies them along root-to-vertex paths, and normalizes the resulting vector. By construction, 𝐹(𝜃(𝑝)) = 𝑝. The map 𝐹 is continuously differentiable on the positive orthant. Therefore, there exist constants 𝑟 𝑝 > 0 and 𝐿 𝑝 < ∞ such that 𝑑TV (𝐹(𝑧), 𝑝) ≤ 𝐿 𝑝 ∥𝑧 − 𝜃(𝑝)∥∞ whenever ∥𝑧 − 𝜃(𝑝)∥∞ ≤ 𝑟 𝑝 . Given a total budget 𝑡, the learner uses 𝑡 𝑘 𝑡 := 𝑚−1





b(𝑡) be the vector of empirical endpoint frequencies. Each samples for every tree edge. Let 𝜃 coordinate is the empirical mean of 𝑘 𝑡 independent Bernoulli variables. Hence, by Hoeffding’s inequality and a union bound, for every 𝑢 > 0, h

i

2

b(𝑡) − 𝜃(𝑝)∥∞ > 𝑢 ≤ 4(𝑚 − 1)𝑒 −2𝑘𝑡 𝑢 . P 𝑝 ∥𝜃 The learner uses the same lower truncation as in the proof of Theorem 3.1. Since all coordinates of 𝜃(𝑝) are positive, for all sufficiently large 𝑘 𝑡 —where the required threshold may depend on 𝑝— b(𝑡) lies in a sufficiently small neighborhood of 𝜃(𝑝). this truncation is inactive whenever 𝜃 Let   𝜀 . 𝑢 := min 𝑟 𝑝 , 𝐿𝑝 On the event

b(𝑡) − 𝜃(𝑝)∥∞ ≤ 𝑢, ∥𝜃 the reconstructed distribution therefore satisfies 𝑑TV (𝐴𝑡 , 𝑝) ≤ 𝐿 𝑝 𝑢 ≤ 𝜀. It is enough to take

4(𝑚 − 1) 1 log . 2 𝛿 2𝑢 Since 𝑝, 𝑈, and the chosen spanning tree are fixed, 𝑘𝑡 ≥

𝐶 𝑝′ 1 ≤ 𝑢2 𝜀2 for some finite constant 𝐶 𝑝′ , for every 𝜀 ∈ (0, 1). Absorbing the number of tree edges, the fixed truncation threshold, and log(4(𝑚 − 1)) into a constant 𝐶 𝑝,𝒮,𝑈 proves the result. □

30

5

Conclusion

In this work, we studied the problem of learning discrete distributions from arbitrary restricted conditional query families 𝒮. Our findings provide a complete qualitative characterization of learnability, as well as the range of the optimal sample complexity bounds for different 𝒮. This framework opens several promising avenues for future research. First, while our sample complexity bounds are tight up to logarithmic factors, closing the remaining polylogarithmic gaps is an immediate next step. Second, our current analysis focuses strictly on distributions with finite support; extending these structural insights to more general spaces, such as countably infinite or continuous domains, presents a natural and compelling theoretical challenge. Finally, it would be interesting to explore the graph-theoretic conditions that 𝒮 must satisfy to enable other fundamental statistical tasks, such as distribution testing or property estimation from arbitrary 𝒮.

31

References [AFL26] Tomer Adar, Eldar Fischer, and Amit Levi. Optimal mass estimation in the conditional sampling model. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 4105–4174. SIAM, 2026. [AFM25] Carlos Alós-Ferrer and Maximilian Mihm. A characterization of the luce choice rule for an arbitrary collection of menus. Journal of Economic Theory, 223:105941, 2025. [APA18] Arpit Agarwal, Prathamesh Patil, and Shivani Agarwal. Accelerated spectral ranking. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 70–79. PMLR, 10–15 Jul 2018. [BHPQ17] Avrim Blum, Nika Haghtalab, Ariel Procaccia, and Mingda Qiao. Collaborative pac learning. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. [Bre13] Alain Bretto. Hypergraph Theory: An Introduction. Springer Publishing Company, Incorporated, 2013. [BT52] Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324–345, 1952. [Can20a] Clément L Canonne. A short note on learning discrete distributions. arXiv preprint arXiv:2002.11457, 2020. [Can20b] Clément L. Canonne. A Survey on Distribution Testing: Your Data is Big. But is it Blue? Number 9 in Graduate Surveys. Theory of Computing Library, 2020. [CFGM16] Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah. On the power of conditional samples in distribution testing. SIAM Journal on Computing, 45(4):1261–1296, 2016. [CRS15] Clément L. Canonne, Dana Ron, and Rocco A. Servedio. Testing probability distributions using conditional samples. SIAM Journal on Computing, 44(3):540–616, 2015. [FKT22] Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos. Perfect sampling from pairwise comparisons. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA, 2022. Curran Associates Inc. [GVW88] Richard D. Gill, Yehuda Vardi, and Jon A. Wellner. Large sample theory of empirical distributions in biased sampling models. The Annals of Statistics, 16(3):1069–1112, 1988. [HJZ22] Nika Haghtalab, Michael Jordan, and Eric Zhao. On-demand sampling: Learning optimally from multiple distributions. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 406–419. Curran Associates, Inc., 2022. 32

[HSJ26] Rafael Hanashiro, Abhishek Shetty, and Patrick Jaillet. Is Multi-Distribution Learning as easy as PAC Learning: Sharp rates with bounded label noise. In Steve Hanneke and Tor Lattimore, editors, Proceedings of Thirty Ninth Conference on Learning Theory, volume 336 of Proceedings of Machine Learning Research, pages 3109–3142. PMLR, 29 Jun–03 Jul 2026. [HXY22] Shiyang Huang, Yan Xiong, and Liyan Yang. Skill acquisition and data sales. Management Science, 68(8):6116–6144, 2022. [JSF18] Bai Jiang, Qiang Sun, and Jianqing Fan. Bernstein’s inequalities for general markov chains. arXiv preprint arXiv:1805.10721, 2018. [KT19] Gautam Kamath and Christos Tzamos. Anaconda: a non-adaptive conditional sampling algorithm for distribution testing. In Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, SODA ’19, page 679–693, USA, 2019. Society for Industrial and Applied Mathematics. [LHK+ 24] Charles Lu, Baihe Huang, Sai Praneeth Karimireddy, Praneeth Vepakomma, Michael Jordan, and Ramesh Raskar. Data acquisition via experimental design for data markets. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. [Luc59] R.D. Luce. Individual Choice Behavior: A Theoretical Analysis. Wiley, 1959. [MG15] Lucas Maystre and Matthias Grossglauser. Fast and accurate inference of plackett-luce models. In Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 1, NIPS’15, page 172–180, Cambridge, MA, USA, 2015. MIT Press. [NOS17] Sahand Negahban, Sewoong Oh, and Devavrat Shah. Rank centrality: Ranking from pairwise comparisons. Operations Research, 65(1):266–287, 2017. [Pen24] Binghui Peng. The sample complexity of multi-distribution learning. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 4185–4204. PMLR, 30 Jun–03 Jul 2024. [Ros95] Jeffrey S Rosenthal. Minorization conditions and convergence rates for markov chain monte carlo. Journal of the American Statistical Association, 90(430):558–566, 1995. [RR04] Gareth O. Roberts and Jeffrey S. Rosenthal. General state space markov chains and mcmc algorithms. Probability Surveys, 1(none), January 2004. [SBB+ 15] Nihar Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ramchandran, and Martin Wainwright. Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence. In Guy Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pages 856–865, San Diego, California, USA, 09–12 May 2015. PMLR.

33

[SG19] Aadirupa Saha and Aditya Gopalan. Active ranking with subset-wise preferences. In Kamalika Chaudhuri and Masashi Sugiyama, editors, The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, Proceedings of Machine Learning Research, pages 3312–3321. PMLR, 2019. [SSBD14] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. [Var85] Y. Vardi. Empirical distributions in selection bias models. The Annals of Statistics, 13(1):178–203, 1985. [VHS+ 24] Pablo Villalobos, Anson Ho, Jaime Sevilla, Tamay Besiroglu, Lennart Heim, and Marius Hobbhahn. Position: Will we run out of data? limits of LLM scaling based on human-generated data. In Ruslan Salakhutdinov, Zico Kolter, Katherine A. Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Fortyfirst International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024, Proceedings of Machine Learning Research, pages 49523–49544. PMLR / OpenReview.net, 2024. [XPD+ 23] Sang Michael Xie, Hieu Pham, Xuanyi Dong, Nan Du, Hanxiao Liu, Yifeng Lu, Percy Liang, Quoc V Le, Tengyu Ma, and Adams Wei Yu. Doremi: Optimizing data mixtures speeds up language model pretraining. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. [YLS+ 25] Jiasheng Ye, Peiju Liu, Tianxiang Sun, Jun Zhan, Yunhua Zhou, and Xipeng Qiu. Data mixing laws: Optimizing data mixtures by predicting language modeling performance. In The Thirteenth International Conference on Learning Representations, 2025. [ZZC+ 25] Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S. Du, and Jason Lee. Optimal multidistribution learning. J. ACM, 72(5), October 2025.

34

A

Technical Lemmas

Below we state several technical lemmas that are useful for our main results. The first folklore result shows the error rate of a simple learner that queries 𝑁 times the set [𝑛]. Lemma A.1 (Empirical distribution). Let Ω be a finite set of size 𝑚, let 𝑝 be an arbitrary distribution on Ω, and let 𝑋1 , . . . , 𝑋𝑁 be independent samples from 𝑝. Define the empirical distribution 𝑁

b 𝑝 (𝑥) :=

1 Õ 1{𝑋𝑡 = 𝑥}, 𝑁

𝑥 ∈ Ω.

𝑡=1

There  is a universal constant 𝐶 > 0 such that, for every 𝜀, 𝛿 ∈ (0, 1), if 𝑁 ≥ 𝐶 𝜀 ≥ 1 − 𝛿.

 𝑚+log(1/𝛿) , then P 𝑑TV (b 𝑝 , 𝑝) ≤ 2 𝜀

Proof. For two distributions 𝜇, 𝜈 on a finite set, by definition 𝑑TV (𝜇, 𝜈) = sup𝐴⊆Ω |𝜇(𝐴) − 𝜈(𝐴)| holds. It is therefore enough to control the empirical mass of every subset of Ω. Fix 𝐴 ⊆ Ω. The random variables 𝐵𝑡 := 1{𝑋𝑡 ∈ 𝐴}, 𝑡 = 1, . . . , 𝑁, are i.i.d. Bernoulli random variables with mean 𝑝(𝐴), and b 𝑝 (𝐴) = 𝑁1 bound stated above,   2 P |b 𝑝 (𝐴) − 𝑝(𝐴)| > 𝜀 ≤ 2𝑒 −2𝑁 𝜀 .

Í𝑁

𝑡=1 𝐵𝑡 . By the Bernoulli tail

There are at most 2𝑚 subsets 𝐴 ⊆ Ω, so a union bound gives





2

P 𝑑TV (b 𝑝 , 𝑝) > 𝜀 = P sup |b 𝑝 (𝐴) − 𝑝(𝐴)| > 𝜀 ≤ 2𝑚+1 𝑒 −2𝑁 𝜀 .





𝐴⊆Ω

The right-hand side is at most 𝛿 whenever 𝑁≥

(𝑚 + 1) log 2 + log(1/𝛿) . 2𝜀2

By choosing the appropriate absolute constant 𝐶 in the statement we get the claimed sufficient condition. □ The next result employs standard ideas from coding theory to show that there is a large set of words that are pairwise far enough in Hamming distance. For completeness, we provide a proof. Lemma A.2 (Large separated code). There are universal constants 𝑐0 > 0 and 𝑚0 ∈ N such that the following holds for every integer 𝑚 ≥ 𝑚0 . There exists a set C ⊆ {−1, +1}𝑚 of sign vectors with log |C| ≥ 𝑐0 𝑚 and such that any two distinct 𝜎, 𝜏 ∈ C have Hamming distance at least 𝑚/4: 𝑑𝐻 (𝜎, 𝜏) := {𝑗 ∈ [𝑚] : 𝜎 𝑗 ≠ 𝜏𝑗 } ≥

35

𝑚 . 4

Proof. Let 𝑀 = ⌈𝑒 𝑚/100 ⌉ and draw Σ(1) , . . . , Σ(𝑀) independently and uniformly from {−1, +1}𝑚 . For each 𝑎 < 𝑏, 𝑑𝐻 (Σ(𝑎) , Σ(𝑏) ) ∼ Bin(𝑚, 1/2), so Hoeffding’s inequality gives

h

Pr 𝑑𝐻 (Σ(𝑎) , Σ(𝑏) ) <

𝑚i ≤ 𝑒 −𝑚/8 . 4

Hence the expected number of bad pairs is at most



𝑀 −𝑚/8 𝑒 <1 2



for all sufficiently large 𝑚. Therefore there is a realization with no bad pair. Taking 𝒞 to be that realization proves the distance property, and log |𝒞 | ≥

𝑚 . 100

□ The following result shows that if an estimator of a random variable has a constant probability of predicting it correctly, then the mutual information between the estimator and the underlying variable admits a non-trivial lower bound.

b be Lemma A.3 (Fano inequality). Let 𝑉 be uniformly distributed on a finite set 𝒱 with |𝒱 | ≥ 2, and let 𝑉 1 b ≠ 𝑉] ≤ , then any estimator of 𝑉, possibly randomized and possibly constructed from arbitrary data. If P[𝑉 3 2 b ≥ log |𝒱 | − log 2. More generally, if P[𝑉 b ≠ 𝑉] ≤ 𝑝 𝑒 , then 𝐼(𝑉; 𝑉) b ≥ (1 − 𝑝 𝑒 ) log |𝒱 | − log 2. 𝐼(𝑉; 𝑉) 3 b ≠ 𝑉}. Since 𝑉 is uniform on 𝒱 , 𝐻(𝑉) = log |𝒱 |. We upper bound the conditional Proof. Let 𝐸 := 1{𝑉 b By the chain rule for entropy, entropy of 𝑉 given 𝑉. b ≤ 𝐻(𝐸, 𝑉 | 𝑉) b = 𝐻(𝐸 | 𝑉) b + 𝐻(𝑉 | 𝐸, 𝑉). b 𝐻(𝑉 | 𝑉) b so the The first term is at most log 2 because 𝐸 is binary. For the second term, if 𝐸 = 0, then 𝑉 = 𝑉, conditional entropy is zero. If 𝐸 = 1, the variable 𝑉 can take at most |𝒱 | values, so the conditional entropy is at most log |𝒱 |. Therefore b ≤ P[𝐸 = 1] log |𝒱 | ≤ 𝑝 𝑒 log |𝒱 |. 𝐻(𝑉 | 𝐸, 𝑉) Combining the last two displays gives

b ≤ log 2 + 𝑝 𝑒 log |𝒱 |. 𝐻(𝑉 | 𝑉) Thus

b = 𝐻(𝑉) − 𝐻(𝑉 | 𝑉) b ≥ (1 − 𝑝 𝑒 ) log |𝒱 | − log 2. 𝐼(𝑉; 𝑉) The stated 𝑝 𝑒 = 1/3 case follows immediately.

□

The next result employs standard ideas from information theory. 36

Lemma A.4 (Average KL to a reference bounds mutual information). Let 𝑉 be a random variable taking values in a finite set 𝒱 . Conditional on 𝑉 = 𝑣, let 𝑋 have distribution 𝑃𝑣 on a finite set 𝒳 . Let Í 𝜇(𝑣) = P[𝑉 = 𝑣], and let 𝑃 := 𝑣∈𝒱 𝜇(𝑣)𝑃𝑣 be the marginal distribution of 𝑋. Then, for every distribution 𝑄 on 𝒳 , Õ 𝐼(𝑉; 𝑋) ≤ 𝜇(𝑣) DKL (𝑃𝑣 ∥𝑄) . 𝑣∈𝒱

Proof. If the right-hand side is +∞, the claim is trivial, so assume it is finite. Then every 𝑃𝑣 with 𝜇(𝑣) > 0 is absolutely continuous with respect to 𝑄, and so is 𝑃. By definition of mutual information for finite variables, 𝐼(𝑉; 𝑋) =

Õ

𝜇(𝑣) DKL (𝑃𝑣 ∥𝑃).

𝑣∈𝒱

For each 𝑥 ∈ 𝒳 with 𝑃(𝑥) > 0, insert the factor 𝑃(𝑥)/𝑄(𝑥) into the KL divergence:

Õ

𝜇(𝑣) DKL (𝑃𝑣 ∥𝑄) =

Õ

=

𝑣

𝜇(𝑣)

Õ

𝑣

𝑥

Õ

𝜇(𝑣)

Õ

𝑣

𝑃𝑣 (𝑥) log 𝑃𝑣 (𝑥) log

𝑥

= 𝐼(𝑉; 𝑋) +

Õ

𝑃(𝑥) log

𝑥

𝑃𝑣 (𝑥) 𝑄(𝑥) 𝑃𝑣 (𝑥) 𝑃(𝑥)

+

Õ

𝜇(𝑣)

Õ

𝑣

𝑥

𝑃𝑣 (𝑥) log

𝑃(𝑥) 𝑄(𝑥)

𝑃(𝑥) 𝑄(𝑥)

= 𝐼(𝑉; 𝑋) + DKL (𝑃∥𝑄). The last term is nonnegative, which proves the inequality.

□

For a nonempty query set 𝑆 ⊆ [𝑛], a distribution 𝑝 ∈ Δ([𝑛]), and a zero-mass convention ★ ∈ {FAIL, UNIF0}, define 𝑄 ★𝑝,𝑆 as the oracle’s one-query response law on the alphabet 𝑆 ∪ {FAIL} as follows. If 𝑝(𝑆) > 0, then 𝑄 ★𝑝,𝑆 (𝑥) =

𝑝𝑥 1{𝑥 ∈ 𝑆}, 𝑝(𝑆)

𝑄 ★𝑝,𝑆 (FAIL) = 0.

If 𝑝(𝑆) = 0 and ★ = FAIL, then 𝑄 ★𝑝,𝑆 = 𝛿FAIL . If 𝑝(𝑆) = 0 and ★ = UNIF0, then 𝑄 ★𝑝,𝑆 is uniform on 𝑆 and assigns mass zero to FAIL. For the result below, the transcript may include the internal random seed, queried sets, oracle responses, and stopping indicator. Early stopping is interpreted by padding the remaining rounds with deterministic dummy symbols. This result shows that if the laws of the oracles are close in TV distance for every query set in S, then the distributions of the transcripts of any adaptive learner must also be close. Lemma A.5 (Adaptive transcript hybrid). Fix a finite domain [𝑛], an allowed query family S ⊆ 2[𝑛] \ {∅}, and a zero-mass convention ★ ∈ {FAIL, UNIF0}. Let 𝑝, 𝑞 ∈ Δ([𝑛]) satisfy sup 𝑑TV 𝑄 ★𝑝,𝑆 , 𝑄 ★𝑞,𝑆 ≤ 𝛼.

𝑆∈S

Then, for every randomized adaptive strategy making at most 𝑇 queries from S, the total variation distance between its full transcript law under 𝑝 and its full transcript law under 𝑞 is at most 𝑇𝛼. 37

Proof. Encode all internal randomization of the learner by a random seed 𝑅, independent of the target. We first condition on 𝑅 = 𝑟. After this conditioning, the strategy is deterministic: at each round, the next query is a deterministic function of the previous transcript, unless the strategy has already stopped. If it has stopped, all later rounds are padded by a fixed dummy query-response symbol. Thus it suffices to prove the claim for deterministic fixed-seed strategies and then average over 𝑅. For a deterministic strategy, let 𝐻𝑡 denote the padded transcript after 𝑡 rounds, including the queried sets and responses. Let 𝑃𝑡 and 𝑄 𝑡 be the laws of 𝐻𝑡 under targets 𝑝 and 𝑞, respectively. We prove by induction that 𝑑TV (𝑃𝑡 , 𝑄 𝑡 ) ≤ 𝑡𝛼,

𝑡 = 0, 1, . . . , 𝑇.

The case 𝑡 = 0 is trivial because the empty transcript has the same law under both targets. We use a standard one-step fact about Markov kernels. Here a Markov kernel 𝐾 from a finite set ℋ to a finite set ℋ ′ simply means that, for each current history ℎ ∈ ℋ , 𝐾(ℎ, ·) is a probability distribution on possible next histories in ℋ ′ . If 𝑃 is a distribution on ℋ , then 𝑃𝐾 denotes the induced distribution on ℋ ′ : Õ (𝑃𝐾)(𝐴) = 𝑃(ℎ)𝐾(ℎ, 𝐴). ℎ∈ℋ

In words, to sample from 𝑃𝐾, first draw ℎ ∼ 𝑃, and then draw the next history according to 𝐾(ℎ, ·). Suppose 𝐾 and 𝐿 are two such kernels and sup 𝑑TV 𝐾(ℎ, ·), 𝐿(ℎ, ·) ≤ 𝛼.

ℎ∈ℋ

Then, for any two past-history laws 𝑃, 𝑄, 𝑑TV (𝑃𝐾, 𝑄𝐿) ≤ 𝑑TV (𝑃, 𝑄) + 𝛼. Indeed, by the triangle inequality, 𝑑TV (𝑃𝐾, 𝑄𝐿) ≤ 𝑑TV (𝑃𝐾, 𝑄𝐾) + 𝑑TV (𝑄𝐾, 𝑄𝐿). The first term is at most 𝑑TV (𝑃, 𝑄) because applying the same randomized transition cannot increase total variation. In finite spaces this follows from 𝑑TV (𝑃𝐾, 𝑄𝐾) =

1 Õ Õ 1Õ (𝑃(ℎ) − 𝑄(ℎ))𝐾(ℎ, 𝑧) ≤ |𝑃(ℎ) − 𝑄(ℎ)| = 𝑑TV (𝑃, 𝑄). 2 2 ′ 𝑧∈ℋ

ℎ∈ℋ

ℎ∈ℋ

For the second term, 𝑑TV (𝑄𝐾, 𝑄𝐿) = ≤

1 Õ Õ 𝑄(ℎ) 𝐾(ℎ, 𝑧) − 𝐿(ℎ, 𝑧) 2 ′

𝑧∈ℋ Õ

ℎ∈ℋ

𝑄(ℎ) 𝑑TV 𝐾(ℎ, ·), 𝐿(ℎ, ·) ≤ 𝛼.

ℎ∈ℋ

This proves the one-step inequality. 38

We now identify the relevant kernels for the adaptive transcript. Fix a past history ℎ before round 𝑡. If the learner has already stopped, then the next history is obtained by appending the same deterministic dummy symbol under both targets, so the two next-step kernels are identical. Otherwise, the deterministic learner chooses a query set 𝑆𝑡 (ℎ) ∈ S. Under target 𝑝, the next oracle response has law 𝑄 ★𝑝,𝑆 (ℎ) ; under target 𝑞, it has law 𝑄 ★𝑞,𝑆 (ℎ) . The next 𝑡 𝑡 transcript is obtained by appending the same query 𝑆𝑡 (ℎ) and the realized response. Equivalently, the next-step kernel is the distribution obtained from the corresponding oracle response law by the deterministic map 𝑦 ↦−→ ℎ ◦ (𝑆𝑡 (ℎ), 𝑦). Total variation cannot increase under a deterministic map. Therefore 𝑑TV 𝐾 𝑝 (ℎ, ·), 𝐾 𝑞 (ℎ, ·) ≤ 𝑑TV 𝑄 ★𝑝,𝑆𝑡 (ℎ) , 𝑄 ★𝑞,𝑆𝑡 (ℎ) ≤ 𝛼. (𝑡)

(𝑡)

Thus the one-step inequality applies with (𝑡)

(𝑡)

𝑃𝑡 = 𝑃𝑡−1 𝐾 𝑝 ,

𝑄 𝑡 = 𝑄 𝑡−1 𝐾 𝑞 ,

and gives 𝑑TV (𝑃𝑡 , 𝑄 𝑡 ) ≤ 𝑑TV (𝑃𝑡−1 , 𝑄 𝑡−1 ) + 𝛼. By induction, 𝑑TV (𝑃𝑇 , 𝑄𝑇 ) ≤ 𝑇𝛼 for every fixed seed 𝑟. It remains to remove the conditioning on the learner’s random seed. Let 𝑃𝑇𝑟 and 𝑄𝑇𝑟 be the conditional laws of the padded query-response transcript 𝐻𝑇 given seed 𝑅 = 𝑟, under targets 𝑝 and 𝑞 respectively. Let 𝜈 be the common distribution of 𝑅. First suppose that the seed is included in the full transcript. Let P𝑇 and Q𝑇 denote the laws of the pair (𝑅, 𝐻𝑇 ) under targets 𝑝 and 𝑞. For any event 𝐸 in the joint seed-transcript space, define its section at seed 𝑟 by 𝐸𝑟 := {ℎ : (𝑟, ℎ) ∈ 𝐸}. Then

∫ P𝑇 (𝐸) =

∫

𝑃𝑇𝑟 (𝐸𝑟 ) 𝑑𝜈(𝑟),

Hence

Q𝑇 (𝐸) =

𝑄𝑇𝑟 (𝐸𝑟 ) 𝑑𝜈(𝑟).

∫

𝑃𝑇𝑟 (𝐸𝑟 ) − 𝑄𝑇𝑟 (𝐸𝑟 ) 𝑑𝜈(𝑟)

∫

𝑃𝑇𝑟 (𝐸𝑟 ) − 𝑄𝑇𝑟 (𝐸𝑟 ) 𝑑𝜈(𝑟)

∫

𝑑TV (𝑃𝑇𝑟 , 𝑄𝑇𝑟 ) 𝑑𝜈(𝑟) ≤ 𝑇𝛼.

|P𝑇 (𝐸) − Q𝑇 (𝐸)| = ≤ ≤

Taking the supremum over all events 𝐸 gives 𝑑TV (P𝑇 , Q𝑇 ) ≤ 𝑇𝛼. 39

If the seed is not included in the transcript, then the observed transcript is obtained from the full pair (𝑅, 𝐻𝑇 ) by applying the deterministic projection that discards 𝑅. Total variation cannot increase under deterministic post-processing, so the same bound holds for the transcript law without the seed as well. This proves the lemma. □ We also use the following standard result about the mixing time of Markov chains. We provide a proof for completeness. Lemma A.6 (Doeblin minorization [Ros95, RR04]). Let 𝐾 be a Markov kernel on a finite state space Ω, and let 𝜋 be a stationary distribution for 𝐾. Suppose that for some 𝜂 ∈ (0, 1], 𝐾(𝑥, ·) ≥ 𝜂 𝜋(·)

for every 𝑥 ∈ Ω.

Then, for every initial distribution 𝜇 on Ω and every 𝑡 ≥ 0, 𝑑TV (𝜇𝐾 𝑡 , 𝜋) ≤ (1 − 𝜂)𝑡 𝑑TV (𝜇, 𝜋) ≤ (1 − 𝜂)𝑡 . In particular, if 𝑡 ≥ 𝜂−1 log(1/𝜀), then 𝑑TV (𝜇𝐾 𝑡 , 𝜋) ≤ 𝜀. Proof. If 𝜂 = 1, then 𝐾(𝑥, ·) = 𝜋(·) for every 𝑥, so the claim is immediate. Assume 𝜂 < 1. Define 𝑅(𝑥, ·) :=

𝐾(𝑥, ·) − 𝜂𝜋(·) . 1−𝜂

The minorization assumption implies that 𝑅(𝑥, ·) is a probability distribution for every 𝑥, so 𝑅 is a Markov kernel. Thus 𝐾 = 𝜂Π𝜋 + (1 − 𝜂)𝑅, where Π𝜋 is the rank-one kernel whose every row is 𝜋. Since 𝜋 is stationary for 𝐾, 𝜋 = 𝜋𝐾 = 𝜂𝜋 + (1 − 𝜂)𝜋𝑅, and hence 𝜋𝑅 = 𝜋. Therefore, for any distribution 𝜇, 𝜇𝐾 − 𝜋 = 𝜂𝜋 + (1 − 𝜂)𝜇𝑅 − 𝜂𝜋 + (1 − 𝜂)𝜋𝑅 = (1 − 𝜂)(𝜇𝑅 − 𝜋𝑅).

Taking total variation and using that Markov kernels contract total variation, 𝑑TV (𝜇𝐾, 𝜋) ≤ (1 − 𝜂)𝑑TV (𝜇, 𝜋). Iterating gives Finally, 𝑑TV (𝜇, 𝜋) ≤ 1 and

𝑑TV (𝜇𝐾 𝑡 , 𝜋) ≤ (1 − 𝜂)𝑡 𝑑TV (𝜇, 𝜋). (1 − 𝜂)𝑡 ≤ 𝑒 −𝜂𝑡 ,

so 𝑡 ≥ 𝜂−1 log(1/𝜀) implies 𝑑TV (𝜇𝐾 𝑡 , 𝜋) ≤ 𝜀.

□

40

B

Examples of Hierarchically Comparable Query Families

We give several natural classes of query families satisfying Definition 5. The common theme is that, inside each cell of a balanced partition tree, the family contains enough local queries to compare any two points without leaving that cell. Pairwise queries. The canonical example is the pairwise query family Spair := {𝑥, 𝑦} : 𝑥, 𝑦 ∈ 𝑈, 𝑥 ≠ 𝑦 .



This family is hierarchically comparable with respect to any balanced binary partition tree over 𝑈. Indeed, for every internal node 𝐶 and every pair 𝑥, 𝑦 ∈ 𝐶, the query set 𝑊𝐶 ({𝑥, 𝑦}) := {𝑥, 𝑦} belongs to Spair and satisfies

{𝑥, 𝑦} ⊆ 𝑊𝐶 ({𝑥, 𝑦}) ⊆ 𝐶.

Thus pairwise access is the strongest and cleanest instance of local comparability. Hierarchical category menus. A less restrictive example arises when the domain is organized by a taxonomy or category tree. Let 𝒯 be a balanced binary partition tree over 𝑈. For each internal category 𝐶 ∈ 𝒯 , suppose there is a local menu family S𝐶 ⊆ 2𝐶 \ {∅} such that every pair of points in 𝐶 appears together in some local menu: for every 𝑥, 𝑦 ∈ 𝐶, there exists 𝑊 ∈ S𝐶 with {𝑥, 𝑦} ⊆ 𝑊 ⊆ 𝐶. Then the union S :=

Ø

S𝐶

𝐶∈𝒯

is hierarchically comparable on 𝑈. One concrete version is the following. Fix a constant 𝐾 ≥ 2, and inside each cell 𝐶 allow all local menus of size min{𝐾, |𝐶|}: S𝐶 := 𝑊 ⊆ 𝐶 : |𝑊| = min{𝐾, |𝐶|} .



For any pair 𝑥, 𝑦 ∈ 𝐶, one can choose such a menu 𝑊 containing 𝑥, 𝑦. When 𝐾 = 2, this recovers pairwise queries; when 𝐾 > 2, it gives a model in which data providers expose small local menus rather than individual pairs. Intervals, boxes, and subcubes. Hierarchical comparability also holds for standard geometric query families. If 𝑈 = {1, . . . , 𝑛} is ordered and S contains all intervals, take 𝒯 to be the balanced dyadic interval tree. Each node 𝐶 is an interval. For any 𝑥, 𝑦 ∈ 𝐶, the interval 𝑊𝐶 ({𝑥, 𝑦}) := [min{𝑥, 𝑦}, max{𝑥, 𝑦}] 41

is queryable, contains 𝑥, 𝑦, and is contained in 𝐶. Similarly, if 𝑈 is a finite grid and S contains all axis-aligned boxes, take a balanced recursive spatial partition tree whose cells are boxes. For any two points 𝑥, 𝑦 in a box 𝐶, the smallest axis-aligned box containing 𝑥 and 𝑦 is contained in 𝐶 and is queryable. Finally, if 𝑈 = {0, 1}𝑑 and S contains all subcubes, take a balanced coordinate-splitting tree. Every node 𝐶 is a subcube. For any 𝑥, 𝑦 ∈ 𝐶, the smallest subcube containing 𝑥 and 𝑦 is contained in 𝐶 and is queryable. Hence the subcube family is hierarchically comparable. These geometric examples should be interpreted as structural examples of the condition. In cases where the full domain 𝑈 itself is queryable, the ordinary empirical learner already gives the near-linear rate; the value of Definition 5 is that it also covers local-menu families where learning must be assembled recursively from smaller comparisons

C

Intermediate Exponents

In this section we prove Theorem 4.10. The only difference from the equal-block construction is that we allow the inflated blocks to have unequal sizes. This removes the divisibility constraint 𝑛 = 1 + (𝐻 − 1)𝑏. Lemma C.1 (Unequal block lift). There exist universal constants 𝐻0 ≥ 5 and 𝑐 0 , 𝜀0 , 𝐶 > 0 such that the following holds. Fix an odd integer 𝐻 = 2𝑚 + 1 ≥ 𝐻0 . Let 𝐴1 , 𝐵1 , . . . , 𝐴 𝑚 , 𝐵 𝑚 be pairwise disjoint nonempty blocks, and set 𝑈 := {0} ∪ 𝐴1 ∪ 𝐵1 ∪ · · · ∪ 𝐴𝑚 ∪ 𝐵𝑚 ,

𝑛 := |𝑈|,

and b := |𝐴1 |, |𝐵1 |, . . . , |𝐴𝑚 |, |𝐵𝑚 | .

There is a complete co-occurrence query family S𝐻,b on 𝑈 such that 𝑞★ S𝐻,b ,𝒫𝑈 (𝜀, 1/3) ≥ 𝑐 0

𝑛 + 𝐻2 𝜀2

for all 0 < 𝜀 ≤ 𝜀0 ,

while 𝑞★ S𝐻,b ,𝒫𝑈 (𝜀, 𝛿) ≤ 𝐶

𝐻(𝐻 + log(1/𝛿)) log(𝑒/𝜀) + 𝑛 + 𝐻 log(𝑒𝐻/𝛿) 𝜀2

for all 𝜀, 𝛿 ∈ (0, 1).

Proof. Let the coarse domain be 𝑈 = {0} ∪ {𝑎 1 , 𝑏 1 , . . . , 𝑎 𝑚 , 𝑏 𝑚 }. The point 0 is the hub. The coarse atoms 𝑎 𝑗 , 𝑏 𝑗 are inflated into the blocks 𝐴 𝑗 , 𝐵 𝑗 . Define the block-query family ℬ := {𝐴 𝑖 : 1 ≤ 𝑖 ≤ 𝑚} ∪ {𝐵 𝑖 : 1 ≤ 𝑖 ≤ 𝑚}, 42

and the lifted hard-query family 𝒯 := {𝑇𝑗 𝑘 : 1 ≤ 𝑗 < 𝑘 ≤ 𝑚},

𝑇𝑗 𝑘 := {0} ∪ 𝐴 𝑗 ∪ 𝐵 𝑗 ∪ 𝐴 𝑘 ∪ 𝐵 𝑘 .

Set S𝐻,b := ℬ ∪ 𝒯 . The co-occurrence graph is complete. Points in the same block co-occur in that block query. Points in different blocks co-occur in some 𝑇𝑗 𝑘 . The hub co-occurs with every non-hub point in some 𝑇𝑗 𝑘 . Lower bound. Let S𝐻 := {𝑇 𝑗 𝑘 : 1 ≤ 𝑗 < 𝑘 ≤ 𝑚},

𝑇 𝑗 𝑘 := {0, 𝑎 𝑗 , 𝑏 𝑗 , 𝑎 𝑘 , 𝑏 𝑘 }.

This is the coarse hard family from Theorem 4.3. The quadratic lower bound gives a full-support hard subfamily 𝒫 𝐻 ⊆ Δ+ (𝑈) such that every learner for the coarse problem requires at least 𝑐0

𝐻2 𝜀2

queries for all 0 < 𝜀 ≤ 𝜀0 , after adjusting universal constants if necessary. For a coarse distribution 𝑝 ∈ Δ(𝑈), define its lift to 𝑈 by Lift(𝑝)(0) := 𝑝(0), Lift(𝑝)(𝑥) :=

𝑝(𝑎 𝑗 ) |𝐴 𝑗 |

(𝑥 ∈ 𝐴 𝑗 ),

Lift(𝑝)(𝑥) :=

𝑝(𝑏 𝑗 ) |𝐵 𝑗 |

(𝑥 ∈ 𝐵 𝑗 ).

Thus a lifted hard distribution has the same coarse block masses as 𝑝 and is uniform inside each block. Since 𝒫 𝐻 is full support, every lifted hard distribution has exact support 𝑈. Suppose there were a learner 𝐿 for the lifted problem using 𝑞 queries. We construct a coarse learner 𝐿 with no larger query count by simulating the transcript of 𝐿. If 𝐿 queries a block 𝐴 𝑗 , then 𝐿 uses its own randomness to return a uniformly random point of 𝐴 𝑗 . This is the correct conditional law under every lifted hard target, because the lifted target is uniform inside 𝐴 𝑗 . The same applies to queries of 𝐵 𝑗 . If 𝐿 queries 𝑇𝑗 𝑘 , then 𝐿 queries 𝑇 𝑗 𝑘 . If the coarse oracle returns 0, the simulator returns 0. If it returns 𝑎 𝑗 , the simulator returns a uniformly random point of 𝐴 𝑗 , and similarly for the other three non-hub coarse atoms. For example, for 𝑥 ∈ 𝐴 𝑗 , Pr[simulator returns 𝑥] =

𝑝(𝑎 𝑗 )

Lift(𝑝)(𝑥) 1 = . 𝑝(𝑇 𝑗 𝑘 ) |𝐴 𝑗 | Lift(𝑝)(𝑇𝑗 𝑘 ) ·

Thus the simulated response law is exactly the lifted conditional response law. By induction over adaptive rounds, the entire simulated transcript has exactly the same law as the transcript of 𝐿 on the lifted target.

43

When 𝐿 outputs b 𝑝 on 𝑈, the coarse learner outputs the block projection Πb 𝑝 , defined by (Πb 𝑝 )(0) = b 𝑝 (0),

(Πb 𝑝 )(𝑎 𝑗 ) = b 𝑝 (𝐴 𝑗 ),

(Πb 𝑝 )(𝑏 𝑗 ) = b 𝑝 (𝐵 𝑗 ).

For every coarse target 𝑝, Π Lift(𝑝) = 𝑝. Moreover, total variation contracts under this deterministic coarse-graining: 𝑑TV Πb 𝑝 , 𝑝 = 𝑑TV Πb 𝑝 , Π Lift(𝑝) ≤ 𝑑TV b 𝑝 , Lift(𝑝) .

Hence any successful lifted learner would give a successful coarse learner with no larger query count. The coarse lower bound transfers: 𝑞★ S𝐻,b ,𝒫𝑈 (𝜀, 1/3) ≥ 𝑐 0

𝐻2 . 𝜀2

Independently, Theorem 4.1 implies 𝑞★ S𝐻,b ,𝒫𝑈 (𝜀, 1/3) ≥ 𝑐

𝑛 , 𝜀2

because unrestricted conditional access is at least as informative as access to S𝐻,b , and 𝒫𝑈 contains 𝒫𝑈+ . Combining this with the transferred coarse lower bound, ′ 𝑞★ S𝐻,b ,𝒫𝑈 (𝜀, 1/3) ≥ 𝑐

𝑛 + 𝐻2 . 𝜀2

Upper bound. Fix 𝑝 ∈ 𝒫𝑈 . Define the block-mass vector 𝑤 as above. For each block 𝐷 ∈ {𝐴1 , 𝐵1 , . . . , 𝐴𝑚 , 𝐵𝑚 }, define ( 𝑝(· | 𝐷), 𝑝(𝐷) > 0, 𝑝 𝐷 := 𝑢𝐷 , 𝑝(𝐷) = 0. The learner has two stages. First, using the lifted hard queries 𝑇𝑗 𝑘 and projecting each response to its coarse atom, the learner obtains conditional samples from 𝑤(· | 𝑇 𝑗 𝑘 ). Since the coarse cooccurrence graph is complete, Theorem 4.2 learns 𝑤 to TV error 𝜀/4 and failure probability 𝛿/2 using   𝐻(𝐻 + log(1/𝛿)) log(𝑒/𝜀) 𝑂 𝜀2 queries. Second, the learner estimates the internal conditional distribution inside each block. Since each block is queryable, Lemma A.1 and a union bound over the 2𝑚 blocks give simultaneous TV error at most 𝜀/4 in every block with failure probability at most 𝛿/2, using

Í𝑚 𝑂

𝑗=1 |𝐴 𝑗 | +

Í𝑚

𝑗=1 |𝐵 𝑗 | + 𝐻 log(𝑒𝐻/𝛿)

𝜀2

queries. 44

!

𝑛 + 𝐻 log(𝑒𝐻/𝛿) =𝑂 𝜀2





b be the block-mass estimate and b Let 𝑤 𝑝 𝐷 the conditional estimate inside block 𝐷. Define b b0 𝛿0 + 𝑝 := 𝑤 Also define

e 𝑝 := 𝑤0 𝛿0 +

𝑚 Õ 𝑗=1

𝑚 Õ 𝑗=1

b𝑎 𝑗 b 𝑤 𝑝𝐴𝑗 +

𝑝𝐴𝑗 + 𝑤𝑎𝑗 b

𝑚 Õ 𝑗=1

𝑚 Õ 𝑗=1

b𝑏 𝑗 b 𝑤 𝑝𝐵𝑗 .

𝑤𝑏 𝑗 b 𝑝𝐵𝑗 .

On the good event for the block estimates, 𝑑TV (𝑝, e 𝑝) ≤

𝑚 Õ 𝑗=1

𝑝𝐴𝑗 ) + 𝑤 𝑎 𝑗 𝑑TV (𝑝 𝐴 𝑗 , b

𝑚 Õ 𝑗=1

𝑤 𝑏 𝑗 𝑑TV (𝑝 𝐵 𝑗 , b 𝑝𝐵𝑗 ) ≤

𝜀 . 4

On the good event for the block-mass estimate,

b) ≤ 𝑑TV (e 𝑝, b 𝑝 ) = 𝑑TV (𝑤, 𝑤 Therefore 𝑑TV (𝑝, b 𝑝) ≤

𝜀 . 4

𝜀 < 𝜀. 2

The total query bound is 𝐻(𝐻 + log(1/𝛿)) log(𝑒/𝜀) + 𝑛 + 𝐻 log(𝑒𝐻/𝛿) . 𝑂 𝜀2





This proves the theorem.

□

Proof of Theorem 4.10. Fix 𝛾 ∈ (0, 1), and set 𝑎 :=

1+𝛾 . 2

For every sufficiently large 𝑛, let 𝐻𝑛 be the largest odd integer at most 𝑛 𝑎 . Write 𝐻𝑛 = 2𝑚𝑛 + 1. By increasing 𝑁𝛾 if necessary, we may assume that for all 𝑛 ≥ 𝑁𝛾 , 𝐻𝑛 ≥ 𝐻0 ,

𝐻𝑛 ≤ 𝑛,

𝐻𝑛 ≥

1 𝑎 𝑛 . 2

The last inequality holds for all large 𝑛 because the largest odd integer below 𝑛 𝑎 is at least 𝑛 𝑎 − 2. Since 𝐻𝑛 ≤ 𝑛, we have 2𝑚𝑛 = 𝐻𝑛 − 1 ≤ 𝑛 − 1. Thus we can partition the 𝑛 − 1 non-hub elements of [𝑛] into 2𝑚𝑛 nonempty blocks 𝐴1 , 𝐵1 , . . . , 𝐴 𝑚 𝑛 , 𝐵 𝑚 𝑛 . 45

Apply Lemma C.1 with 𝐻 = 𝐻𝑛 and these blocks, and let 𝒮 = S𝐻𝑛 ,b . By construction, the co-occurrence graph of 𝒮 on [𝑛] is complete. For the lower bound, Lemma C.1 gives 𝑞★ (𝜀, 1/3) ≥ 𝑐 0 𝒮,𝒫 [𝑛]

Since 𝐻𝑛 ≥ 21 𝑛 𝑎 and 2𝑎 = 1 + 𝛾, 𝐻𝑛2 ≥

1 1+𝛾 𝑛 . 4

Therefore 𝑞★ (𝜀, 1/3) ≥ 𝒮,𝒫 [𝑛]

for all 0 < 𝜀 ≤ 𝜀0 . Set

𝐻𝑛2 . 𝜀2

𝑐0 𝑛 1+𝛾 4 𝜀2

𝑐0 . 4 For the upper bound, apply Lemma C.1 with 𝛿 = 1/3: 𝑐1 :=

𝑞★ (𝜀, 1/3) ≤ 𝐶 𝒮,𝒫 [𝑛]

𝐻𝑛 (𝐻𝑛 + 1) log(𝑒/𝜀) + 𝑛 + 𝐻𝑛 log(𝑒𝐻𝑛 ) , 𝜀2

where we absorbed constants depending on 𝛿 = 1/3. Using 𝐻𝑛 ≤ 𝑛, 𝐻𝑛2 ≤ 𝑛 1+𝛾 ,

𝑛 ≤ 𝑛 1+𝛾 ,

and 𝑛 ≥ 3, the numerator is at most 𝐶 ′ 𝑛 1+𝛾 log(𝑒/𝜀) log 𝑛 for a universal constant 𝐶 ′ . Finally, shrink 𝜀0 if necessary so that 𝜀0 ≤ 𝑒 −1 . Then for 0 < 𝜀 ≤ 𝜀0 , log(𝑒/𝜀) ≤ 2 log(1/𝜀). Thus 𝑞★ (𝜀, 1/3) ≤ 𝑐 2 𝒮,𝒫 [𝑛]

𝑛 1+𝛾 log(1/𝜀) log 𝑛 𝜀2

for a universal constant 𝑐2 > 0. Combining the lower and upper bounds proves the theorem.

46

□