Learning Distributions from Multiple Data Providers

Summary§

This paper studies learning an unknown distribution $p$ on $[n]$ from conditional samples. The learner has access to a family $\mathscr{S} \subseteq 2^{[n]}$ of queryable sets; each query to $S \in \mathscr{S}$ returns an independent sample from $p(\cdot \mid S)$. The key concept is the co-occurrence graph: vertices are domain elements, edges exist if two elements appear together in some $S \in \mathscr{S}$.

Core Results§

• Pointwise consistency (estimate $p$ at each point with vanishing error) is achievable iff the co-occurrence graph is connected on the support of $p$.
• PAC learning (estimate $p$ within $\varepsilon$ in total variation with high probability) requires the co-occurrence graph to be complete (every pair co-occurs).
• Sample complexity for PAC: $\tilde{O}(n^2/\varepsilon^2)$ for any family with complete co-occurrence graph, and this is tight in the worst case.
• If $[n] \in \mathscr{S}$ (i.e., we can sample unconditionally), complexity improves to $\Theta(n/\varepsilon^2)$, and this cannot be improved even if all subsets are queryable.
• Under hierarchical comparability (a structural condition on $\mathscr{S}$), the optimal complexity is nearly linear: $\tilde{\Theta}(n/\varepsilon^2)$. Pairwise query families (all pairs) are a canonical example.
• For any $\alpha \in (1,2)$, there exists a query family with optimal rate $\tilde{\Theta}(n^\alpha/\varepsilon^2)$, showing the full range of polynomial rates.

Methodology§

Define unknown distribution $p \in \Delta([n])$. For $S \in \mathscr{S}$, we can draw $x \sim p(\cdot \mid S)$. The learner aims to output $\hat{p}$ close to $p$ in total variation distance.

When the co-occurrence graph is complete, one can estimate all pairwise ratios $p(i)/p(j)$ by querying sets containing $\{i,j\}$ and using samples to estimate conditional probabilities. Then, using linear algebra (e.g., solving for $p$ up to scaling), the distribution can be recovered. Sample complexity arises from needing enough samples to accurately estimate many ratios.

A simple algorithm for complete co-occurrence graph: 1. For each pair $(i,j)$, use query $S_{ij}$ containing $\{i,j\}$ (exists by completeness) to estimate $\hat{r}_{ij} = \frac{\hat{p}(i \mid S_{ij})}{\hat{p}(j \mid S_{ij})} \approx \frac{p(i)}{p(j)}$. 2. Fix a reference element $1$. For each $i$, estimate $\hat{p}(i)/\hat{p}(1) = \hat{r}_{i1}$. 3. Normalize to get $\hat{p}$: $\hat{p}(i) = \hat{r}_{i1} / \sum_j \hat{r}_{j1}$.

Each $\hat{r}_{ij}$ requires $O(1/\varepsilon^2)$ samples for accuracy $\varepsilon/n$ (to control total variation), leading to $O(n^2/\varepsilon^2)$ total.

Pseudocode Illustration§

import numpy as np

def learn_distribution_from_conditional_samples(n, query_family, sample_oracle, epsilon, delta):
    # query_family: list of sets covering all pairs
    # sample_oracle(S): returns a sample from p(·|S)
    # For simplicity, assume complete co-occurrence graph and known support.
    
    # Step 1: Estimate ratios for all pairs (i,1)
    ratios = np.ones(n)
    num_samples = int(np.ceil(2*n / (epsilon**2) * np.log(2*n/delta)))  # heuristic
    for i in range(1, n):
        S = find_set_containing_pair(query_family, i, 0)  # assume exists
        count_i = 0
        count_0 = 0
        for _ in range(num_samples):
            sample = sample_oracle(S)
            if sample == i:
                count_i += 1
            elif sample == 0:
                count_0 += 1
        # estimate ratio p(i)/p(0) as count_i/count_0 (handle zeros)
        if count_0 == 0:
            ratios[i] = float('inf')  # degenerate case
        else:
            ratios[i] = count_i / count_0
    
    # Step 2: Normalize
    p_hat = ratios / np.sum(ratios)
    return p_hat

Key Equations§

• Total variation error: $\|\hat{p} - p\|_{TV} \le \varepsilon$
• Sample complexity for complete graph: $\tilde{O}(n^2/\varepsilon^2)$
• For hierarchical comparability: $\tilde{\Theta}(n/\varepsilon^2)$
• Intermediate rates: $\tilde{\Theta}(n^\alpha/\varepsilon^2)$ for $\alpha \in (1,2)$

The paper uses information-theoretic lower bounds (Le Cam, Fano) and constructive algorithms to establish tight rates.