Technical Summary: Learning from Biased and Costly Data Sources

Problem Formulation

This work addresses the challenge of multi-source data collection under a fixed budget to estimate population statistics. In many practical scenarios (e.g., clinical trials, political polling), data must be gathered from $M$ heterogeneous sources, each with distinct group compositions and sampling costs.

The core difficulty arises from three factors:

1. Heterogeneous Costs: Sampling from source $m$ incurs a cost $c_m$.
2. Distributional Mismatch: The group distribution at each source ($p_m$) differs from the target population distribution ($q$) and from other sources.
3. Unobservable Group Identity at Recruitment: While group identities are known for the sources and the target, individuals cannot be pre-selected based on group identity without incurring the measurement cost.

The goal is to design a sampling plan $\mathbf{n} = (n_1, \dots, n_M)$ (where $n_m$ is the number of samples from source $m$) and an estimator $\hat{\theta}$ to minimize the minimax risk (expected squared loss) for estimating either:

• The population mean $\theta_{PM}(Q) = \mathbb{E}_{Y \sim Q}[Y]$.
• The vector of group-conditional means $\theta_{GM}(Q) = \{\mathbb{E}[Y|Z=z]\}_{z \in [K]}$.

The problem is constrained by a budget $B$, such that $\mathbf{c}^\top \mathbf{n} \le B$. The authors assume the conditional distribution $P_{Y|Z}$ is unknown but belongs to a class with bounded means ($| \mathbb{E}[Y|Z] | \le R$) and bounded variance ($\text{Var}(Y|Z) \le \sigma^2$).

Methodology

1. Effective Sample Size and Discrepancy

The authors introduce the effective sample size ($n_{\text{eff}}$) as the central metric for evaluating a sampling plan. For a plan $\mathbf{n}$, let $p_{\mathbf{n}}$ be the mixture distribution of groups induced by the sampling plan. The effective sample size with respect to a target distribution $q$ is defined as:
$$n_{\text{eff}}(\mathbf{n}, q) := \frac{\mathbf{1}^\top \mathbf{n}}{d(q || p_{\mathbf{n}})}$$
where $d(a || b) = \sum_{z} \frac{a(z)^2}{b(z)}$ is a discrepancy measure related to the $\chi^2$-divergence ($d(a||b) = D_{\chi^2}(a||b) + 1$). This metric quantifies how well the collected data approximates the target distribution, penalizing plans that result in high divergence.

2. Optimal Sampling Plan

The authors propose a sampling plan $\mathbf{n}^\star_T$ that maximizes the effective sample size subject to the budget constraint:
$$\mathbf{n}^\star_T \in \arg\max_{\mathbf{n}} n_{\text{eff}}(\mathbf{n}, q) \quad \text{s.t.} \quad \mathbf{c}^\top \mathbf{n} \le B$$
For estimating group-conditional means, the target distribution $q$ is replaced by the uniform distribution $u_K$. The optimization problem is convex, making it computationally efficient to solve.

3. Estimator Design

The paper pairs the optimal sampling plan with specific estimators:

• For Population Mean: A post-stratified estimator ($\hat{\theta}_{PS}$), which estimates the mean within each group and re-weights them by the target distribution $q$.
  $$\hat{\theta}_{PS} = \sum_{z \in [K]} q(z) \bar{Y}_z$$
• For Group-Conditional Means: The vector of observed group-conditional means ($\hat{\theta}_{VM}$).
• For Prediction: An Importance-Weighted Empirical Risk Minimization (IWERM) procedure.

Key Contributions and Results

1. Minimax Lower Bounds

The authors establish lower bounds on the minimax risk for any policy. A key technical contribution is the proof technique, which utilizes a uniform prior over bounded means and analyzes the variance of a truncated normal posterior. This is necessary because standard conjugate priors (normal-normal) are invalid when means are bounded.

The lower bound for population mean estimation is:
$$R^\star_{PM}(B, P_{Y|Z}) \ge \frac{\sigma^2}{n_{\text{eff}}(\mathbf{n}^\star_T, q)} - o\left(\frac{1}{B}\right)$$
This demonstrates that the risk is fundamentally limited by the effective sample size of the optimal sampling plan.

2. Minimax Upper Bounds and Optimality

The authors prove that the policy $(\mathbf{n}^\star_T, \hat{\theta}_{PS})$ achieves an upper bound that matches the lower bound in the leading term:
$$R_{PM}((\mathbf{n}^\star_T, \hat{\theta}_{PS}), P_{Y|Z}) \le \frac{\sigma^2}{n_{\text{eff}}(\mathbf{n}^\star_T, q)} + o\left(\frac{1}{B}\right)$$
This establishes that the proposed approach is minimax optimal. The analysis shows that naive strategies (e.g., matching the target distribution exactly or maximizing raw sample count) are suboptimal because they fail to account for the interplay between cost, source composition, and the estimator's ability to correct bias.

3. Extension to Prediction Problems

The framework is extended to prediction tasks (minimizing excess risk).

• Upper Bound: The policy $(\mathbf{n}^\star_T, \hat{h}_{IWERM})$ achieves an excess risk bound scaling with $\sqrt{\frac{P_{\text{dim}}(H) K d(q || p_{\mathbf{n}^\star_T})}{B}}$.
• Lower Bound: A novel reduction-to-testing lemma is developed to handle the mismatch between source and target distributions. This yields a lower bound scaling with $\sqrt{\frac{VC_{\text{dim}}(H) q_{\min} d(q || p_{\mathbf{n}^\star_T})}{B}}$.
  While there is a gap of $\sqrt{K/q_{\min}}$ between the upper and lower bounds, the dependence on the effective sample size and discrepancy measure is matched, suggesting the principle holds for prediction as well.

4. Impossibility Result

The paper proves that without the assumption of bounded means ($| \mathbb{E}[Y|Z] | \le R$), the problem is hopeless (infinite risk), justifying the boundedness assumption used in the theoretical framework.

Significance and Claims

The paper claims to provide the first minimax-optimal data collection strategy for multi-source settings with heterogeneous costs and distributions. Its significance lies in:

1. Redefining Efficiency: Moving beyond "matching the target distribution" to maximizing the effective sample size, which balances cost, bias, and variance.
2. Theoretical Rigor: Providing matching upper and lower bounds for mean estimation, establishing the fundamental limits of learning from biased, costly sources.
3. Novel Techniques: Introducing a new reduction-to-testing framework for prediction problems where source and target distributions differ, and utilizing truncated normal analysis for lower bounds under boundedness constraints.
4. Practicality: Demonstrating through simulations that the proposed policy significantly outperforms naive baselines (Uniform, Inverse-Cost, Nearest, and Hybrid) across various target distributions and budget constraints.

The authors note that while the results are established for mean estimation and specific prediction settings, the principle of maximizing effective sample size offers a principled approach to multi-source learning in the presence of costly and heterogeneous data.