{"id":"742202c0-db23-443e-a0eb-6309104e4627","arxiv_id":"2607.24732","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"PAC learning from restricted conditional samples is possible iff the co-occurrence graph is complete, with optimal sample complexity ranging continuously from ~n/ε² to n²/ε² by query-family structure.","lead":"A fixed menu of overlapping data providers can learn a discrete distribution in total variation exactly when every pair of domain elements co-occurs in some provider set. Once that holds, the sample cost can still swing from nearly linear to quadratic in the domain size, depending on how clean or hub-diluted those overlaps are.","discovery_kind":"new_method","skeptic_critique":null,"referee_report":{"model":"moonshotai/kimi-k3","summary":"The paper studies PAC learning of a discrete distribution p on [n] when the learner may only request independent samples from conditional distributions p(·|S) for S in a fixed query family. It introduces the co-occurrence graph CO(S,U) and proves: (i) pointwise consistency on the known-support class iff CO(S,U) is connected (Thm 3.1); (ii) PAC learnability iff CO(S,U) is complete (Thm 3.2); (iii) a universal Õ(m²/ε²) upper bound for complete families via a reversible simulated Markov chain with a Doeblin minorization (Thm 4.2), matched by an Ω(n²/ε²) lower bound for a hub-diluted complete family (Thm 4.3); (iv) a near-linear Õ(m/ε²) rate under hierarchical comparability (Thm 4.4), with pairwise queries as the canonical instance, matched by the Ω(n/ε²) lower bound that holds even under full conditional access (Thm 4.1); and (v) a continuum of optimal rates Õ(n^{1+γ}/ε²) for every γ∈(0,1) via a block-lifted two-scale construction (Thm 4.10, Lemma C.1). A distribution-dependent 1/√t pointwise-consistency rate (Thm 4.11) rounds out the picture. The proofs are complete, self-contained, and use standard tools correctly instantiated: spanning-tree ratio products, hybrid/Fano transcript arguments, Doeblin contraction, and a Bernstein inequality for reversible chains.","tokens_in":53256,"tokens_out":1558,"duration_ms":460416,"significance":"If the results hold — and the proofs appear correct — this is a clean and complete structural theory of a natural restricted-COND model: sharp graph-theoretic learnability criteria; matching upper/lower bounds up to logarithmic factors at both ends of the rate spectrum; a structural condition (hierarchical comparability) recovering near-linear rates, with pairwise/BTL queries as a canonical case; and a continuum of intermediate exponents. The lower bounds are information-theoretic and genuinely tight against the algorithms: the hub-dilution instance certifies that the quadratic upper bound is not an artifact. The model is simple and likely to be reused; the continuum result in particular shows that the split between qualitative learnability and quantitative rate is a real phenomenon rather than a gap in analysis. Limitations are scope-level, not technical: exact noiseless conditional samples, the UNIF0 zero-mass convention, finite domains, and remaining polylog gaps. There are no free parameters or circular fits; hard instances and algorithms are defined independently, and the continuum construction matches upper and lower bounds on the same family by design, which is legitimate.","major_comments":[],"minor_comments":[{"comment":"Notation: optimal query complexity is q* in Definition 1 but q★ in Theorems 4.3 and 4.10 and Lemma C.1. Also Algorithm 1 uses S for the multiset of terminal states, colliding with the query family and its members. Please unify/rename.","section":"§2, §4"},{"comment":"k_t is defined as the ceiling of t/E_T, so E_T k_t can exceed t by up to E_T-1, contradicting 'this uses E_T k_t <= t queries' and the 'exactly t queries' convention of Definition 2. Use the floor and pad with dummy queries.","section":"§3.1 (Theorem 3.1 proof)"},{"comment":"Footnote 4 asserts FAIL and UNIF0 'lead to the same structural criteria and sample bounds in all cases' without proof. The lower-bound proofs do check target-independence of zero-mass responses under both conventions, but Algorithms 1 and 2 are analyzed only under UNIF0. A short remark (treat FAIL as a rejection/stay move, preserving detailed balance and the minorization) would close this.","section":"§2, footnote 4"},{"comment":"Algorithm 1 takes the support set U as input. This is consistent with the class P_U, but state explicitly that the learner knows U, and comment briefly on what changes if only a superset of the support is known (completeness must then hold on the superset).","section":"§4.2 (Theorem 4.2 / Algorithm 1)"},{"comment":"Proposition 4.8 is cited to [JSF18]. Please verify the exact form used (factor gamma multiplying M u^2 with sigma^2+u in the denominator, for a stationary reversible chain with absolute spectral gap gamma) matches a citable statement; a precise theorem number in [JSF18], or a pointer to Paulin's 2015 Bernstein inequalities for Markov chains, would suffice.","section":"§4.3.1 (Proposition 4.8)"},{"comment":"Hierarchical comparability is sufficient but not necessary for near-linear rates (e.g., the family {[n]} alone). Appendix B gestures at this, but a sentence in §4.3 would preempt misreading Definition 5 as a characterization. Relatedly, the polylog gaps (log(1/eps) between Theorems 4.2 and 4.3; (log m)^2 in Theorem 4.4) are acknowledged in §5; stating the conjectured correct dependence would be useful.","section":"§4.3 (Definition 5, Theorem 4.4)"},{"comment":"Spacing/formatting artifacts in abstract and body ('Learnabilityisgovernedby...', 'hierarchical comparabilityas') — presumably an extraction issue, but worth a pass. In Table 1, the first row would be clearer as 'CO(S,U) is complete' rather than 'U induces a complete (clique) CO(S,U)'.","section":"Abstract, Table 1"}],"recommendation":"accept","confidential_remarks":"The techniques are standard for the conditional-sampling literature; the contribution is the model and the resulting characterization, which is crisp and complete up to log factors. Good fit for a theory venue (SODA/ITCS-type, or SICOMP/TCS in journal form). No concerns about the citation pattern. The \"multiple data providers\" framing is stylized — the paper should be judged as distribution-learning/COND theory, not as a data-markets paper."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The thing to know is that this is a real structural package, not a rehash of COND. For fixed query family S they pin PAC learnability of distributions on U exactly to the co-occurrence graph being complete, and pointwise consistency (known support) to connectivity. That split is sharp and useful.\n\nWhat is actually new is the quantitative landscape once completeness holds. Completeness alone only buys Õ(n²/ε²) via a simulated reversible chain with Doeblin minorization; they match it with a hub-dilution hard family. Hierarchical comparability (tree-local witnesses) restores nearly linear Õ(n/ε²), with pairwise queries as the clean case. They also fill every intermediate exponent Õ(n^{1+γ}/ε²). The proofs are standard tools done carefully: spanning-tree ratios, transcript hybrids, Fano + average KL, Bernstein on the local chains. Related work placement is honest—COND, BTL, biased sampling, multi-distribution learning are distinguished rather than papered over.\n\nSoft spots are minor and mostly declared. The model is exact finite-domain conditionals with UNIF0/FAIL; no noise, no strategic providers. Hierarchical comparability is sufficient, not necessary. Polylog gaps remain. The data-provider story is motivation only; nothing empirical. None of that undercuts the theorems as stated.\n\nThis is for people who care about restricted sampling models, comparison-based estimation, or data-mixture structure. Worth a serious referee and worth reading if you work in the area. I would engage.","headline":"Clean structural theory: co-occurrence graph separates PAC from pointwise learnability, and complete families still span linear-to-quadratic sample rates.","tokens_in":32956,"tokens_out":411,"would_cite":true,"duration_ms":17052,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68W20","62G05"],"pacs":[],"model":"grok-4.5","headline":"PAC learning a discrete distribution from fixed conditional providers is possible exactly when every pair co-occurs in some queryable set, and the sample cost then ranges from nearly linear to quadratic in the domain size.","keywords":["distribution learning","conditional sampling","co-occurrence graph","PAC learnability","sample complexity","hierarchical comparability","pairwise comparisons","data providers"],"falsifier":"Construct any complete co-occurrence family whose PAC sample complexity is asymptotically larger than Õ(n²/ε²), or any hierarchically comparable family whose PAC complexity is asymptotically worse than Õ(n/ε²); either would break the claimed landscape.","tokens_in":33245,"feed_emoji":"🔗","tokens_out":980,"duration_ms":24160,"temperature":0.7,"pith_summary":"The paper studies how to recover an unknown discrete distribution when you can only sample from a fixed menu of overlapping providers, each returning a conditional sample on its own subset of the domain. Learnability is completely determined by the co-occurrence graph: two domain elements are linked if some provider covers both. Connectivity of that graph is enough for pointwise consistency on a known support; PAC learning of every distribution on a support requires the graph to be a complete clique. Once the clique condition holds, the optimal sample complexity is not fixed: every complete family admits an Õ(n²/ε²) learner, some hub-diluted families force Ω(n²/ε²) samples, hierarchical local comparisons restore the ordinary Õ(n/ε²) rate, and every intermediate exponent between 1 and 2 is realized by some complete family. The result gives a structural map from provider overlap patterns to both qualitative learnability and quantitative cost.","feed_headline":"When provider overlap lets you learn a distribution, and at what cost","feed_subtitle":"Complete co-occurrence is necessary and sufficient for PAC learning; sample rates then run from linear to quadratic","key_machinery":"The co-occurrence graph CO(S,U): vertices are elements of the target support U, with an edge whenever some allowed set contains both. Completeness of this graph is necessary and sufficient for PAC learnability; connectivity is necessary and sufficient for pointwise consistency on exact support. Sample rates are then controlled by finer structure (hub dilution versus hierarchical local witnesses) on top of that graph.","core_discovery":"For a fixed family of queryable sets, PAC learning every distribution supported on U is possible if and only if the co-occurrence graph on U is complete. Completeness alone guarantees an Õ(|U|²/ε²) sample bound via a simulated Markov chain; that quadratic dependence is tight for some complete families; hierarchical comparability restores the near-linear Õ(|U|/ε²) rate; and every intermediate polynomial rate Õ(|U|^{1+γ}/ε²) is achieved by some complete family.","pith_inferences":["Data-mixture and data-market settings that only control coarse domain overlaps may inherit the same clique-versus-rate gap when the goal is global distribution recovery rather than average risk.","Approximate or noisy conditionals would likely preserve the qualitative clique requirement while inflating the polynomial rates by noise-dependent factors not analyzed here.","The same co-occurrence criterion suggests a template for other tasks (testing, property estimation) under arbitrary fixed conditional menus.","Hierarchical comparability is a design target: taxonomies or geometric partitions that keep comparisons local convert wasteful overlap into useful recursive mass estimates."],"forward_implications":["Provider coverage design can be judged by the co-occurrence graph: missing pairs block PAC recovery even with infinite samples.","Redundant hub-style overlap can force quadratic samples even when every pair co-occurs somewhere.","Tree-local or pairwise menus recover the ordinary linear sample rate without needing to query the full domain.","Any desired intermediate polynomial rate between linear and quadratic can be forced by a suitable two-scale block construction.","Pointwise-consistent learners on connected supports achieve distribution-dependent 1/√t error rates."],"fun_headline_variants":["PAC needs complete co-occurrence; rates run linear to quadratic","Co-occurrence completeness is necessary and sufficient for PAC","Hierarchical comparability restores near-linear sample complexity","Query structure sets PAC rates anywhere from n to n²","Complete co-occurrence graph unlocks PAC; cost depends on family"],"cache_read_input_tokens":128,"weakest_assumption_plain":"Every query returns an exact independent sample from the true conditional distribution on the chosen set, with a fixed rule for zero-mass sets and no noise, mislabeling, or strategic providers.","fun_headline_variants_meta":{"raw":{"variants":["PAC needs complete co-occurrence; rates run linear to quadratic","Co-occurrence completeness is necessary and sufficient for PAC","Hierarchical comparability restores near-linear sample complexity","Query structure sets PAC rates anywhere from n to n²","Complete co-occurrence graph unlocks PAC; cost depends on family"]},"model":"grok-4.5","effort":"low","cost_usd":0.004302,"raw_usage":{"total_tokens":1352,"prompt_tokens":898,"num_sources_used":0,"completion_tokens":64,"cost_in_usd_ticks":43024000,"prompt_tokens_details":{"text_tokens":898,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":390,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":898,"tokens_out":64,"duration_ms":8114,"temperature":1.0,"reasoning_tokens":390,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T06:29:47.334756+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Construct any complete co-occurrence family whose PAC sample complexity is asymptotically larger than Õ(n²/ε²), or any hierarchically comparable family whose PAC complexity is asymptotically worse than Õ(n/ε²); either would break the claimed landscape.","supporting_citations":[],"review_version":1}