I was trying to understand a learning theory paper and got stuck on why PAC learning seems to need much more than pointwise estimation.

The model: we want to learn an unknown distribution over domain [n], but we cannot sample directly from p. Instead, we fix a family S of queryable subsets, and each query to some S in S returns an independent sample from p(.|S). Think of overlapping data providers who only give conditional samples from their own slice of the domain.

The paper defines a co-occurrence graph: two elements are adjacent if some queryable set contains both. The abstract says:

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.

Connected I can motivate: if some S contains both x and y, then the ratio p(x)/p(y) can be recovered from the conditional probabilities p(x|S) and p(y|S), because the normalizer p(S) cancels. Chaining those ratios across a connected graph should reconstruct the distribution up to scale.

I am stuck on why PAC learning forces completeness. Suppose the graph is connected but has a bridge. Is the problem that the bridge mass can be tiny, and you need enough samples on both sides to control L1 error? Or that an adversary can place most mass on one side so the other side only appears through rare bridge samples? Complete co-occurrence removes that issue by giving a direct ratio comparison for every pair of elements.

The paper gives rates: optimal sample complexity is ~O(n^2/eps^2) in the worst case, and Theta(n/eps^2) if you can query the full domain [n]. A hierarchical comparability condition recovers nearly linear rates. The paper is at arxiv.org/abs/2607.24732v1.

One limitation I noticed: this is a clean finite-domain model with exact conditional samples. Real provider skew usually comes with noisy coverage and overlapping but not carefully chosen cohorts, and I have not checked whether the lower bounds survive approximate conditional sampling.

Can anyone point me to an explicit bad distribution for a connected but incomplete graph, or give a proof sketch of why every missing co-occurrence can break PAC learning?