Learning from Biased and Costly Data Sources: Minimax-optimal Data Collection under a Budget

• URL: http://arxiv.org/abs/2602.17894v1
• Date: Thu, 19 Feb 2026 23:17:59 GMT
• Title: Learning from Biased and Costly Data Sources: Minimax-optimal Data Collection under a Budget
• Authors: Michael O. Harding, Vikas Singh, Kirthevasan Kandasamy,
• Abstract summary: In many use cases, such as medical studies or political polling, different sources incur different sampling costs.<n>We develop a sampling plan which maximizes the effective sample size.<n>We provide matching lower bounds, establishing that our approach achieves the budgeted minimax optimal risk.
• Score: 23.14662431994667
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Data collection is a critical component of modern statistical and machine learning pipelines, particularly when data must be gathered from multiple heterogeneous sources to study a target population of interest. In many use cases, such as medical studies or political polling, different sources incur different sampling costs. Observations often have associated group identities (for example, health markers, demographics, or political affiliations) and the relative composition of these groups may differ substantially, both among the source populations and between sources and target population. In this work, we study multi-source data collection under a fixed budget, focusing on the estimation of population means and group-conditional means. We show that naive data collection strategies (e.g. attempting to "match" the target distribution) or relying on standard estimators (e.g. sample mean) can be highly suboptimal. Instead, we develop a sampling plan which maximizes the effective sample size: the total sample size divided by $D_{χ^2}(q\mid\mid\overline{p}) + 1$, where $q$ is the target distribution, $\overline{p}$ is the aggregated source distribution, and $D_{χ^2}$ is the $χ^2$-divergence. We pair this sampling plan with a classical post-stratification estimator and upper bound its risk. We provide matching lower bounds, establishing that our approach achieves the budgeted minimax optimal risk. Our techniques also extend to prediction problems when minimizing the excess risk, providing a principled approach to multi-source learning with costly and heterogeneous data sources.

Related papers

• Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise [26.182166506085114]
  We show that learning across $k$ distributions incurs slow rates scaling with $k/2$, even under constant noise levels, unless each distribution is learned separately.<n>A key technical contribution is a structured hypothesis-testing framework that captures the statistical cost of certifying near-optimality.
  arXiv  Detail & Related papers  (2026-02-24T16:00:15Z)
• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [72.69498649272347]
  conditional distributions is a central problem in machine learning.<n>We propose a new paradigm that integrates both paired and unpaired data.<n>We show that our approach can theoretically recover true conditional distributions with arbitrarily small error.
  arXiv  Detail & Related papers  (2024-10-03T16:12:59Z)
• Rejection via Learning Density Ratios [50.91522897152437]
  Classification with rejection emerges as a learning paradigm which allows models to abstain from making predictions.<n>We propose a different distributional perspective, where we seek to find an idealized data distribution which maximizes a pretrained model's performance.<n>Our framework is tested empirically over clean and noisy datasets.
  arXiv  Detail & Related papers  (2024-05-29T01:32:17Z)
• Causality Pursuit from Heterogeneous Environments via Neural Adversarial Invariance Learning [12.947265104477237]
  Pursuing causality from data is a fundamental problem in scientific discovery, treatment intervention, and transfer learning.<n>This paper introduces a novel algorithmic method for addressing nonparametric invariance and causality learning in regression models across multiple environments.<n>The proposed Focused Adrial Invariant Regularization framework utilizes an innovative minimax optimization approach that drives regression models toward prediction-invariant solutions through adversarial testing.
  arXiv  Detail & Related papers  (2024-05-07T23:37:40Z)
• Active Preference Optimization for Sample Efficient RLHF [27.772423917657626]
  Large Language Models (LLMs) aligned using Reinforcement Learning from Human Feedback (RLHF)<n>We show that uniform sampling of contexts could lead to a policy that suffers a constant sub-optimality gap from the optimal policy.<n>We propose an algorithm, $textttAPO$, that iteratively collects preferences for the most uncertain contexts.
  arXiv  Detail & Related papers  (2024-02-16T08:19:34Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.<n>We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• EM for Mixture of Linear Regression with Clustered Data [6.948976192408852]
  We discuss how the underlying clustered structures in distributed data can be exploited to improve learning schemes. We employ the well-known Expectation-Maximization (EM) method to estimate the maximum likelihood parameters from $m$ batches of dependent samples. We show that if properly, EM on the structured data requires only $O(1)$ to reach the same statistical accuracy, as long as $m$ grows up as $eo(n)$.
  arXiv  Detail & Related papers  (2023-08-22T15:47:58Z)
• Feature Importance Disparities for Data Bias Investigations [2.184775414778289]
  It is widely held that one cause of downstream bias in classifiers is bias present in the training data. We present one such method that given a dataset $X$ consisting of protected and unprotected features, outcomes $y$, and a regressor $h$ that predicts $y$ given $X$. We show across $4$ datasets and $4$ common feature importance methods of broad interest to the machine learning community that we can efficiently find subgroups with large FID values even over exponentially large subgroup classes.
  arXiv  Detail & Related papers  (2023-03-03T04:12:04Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• Bias Mimicking: A Simple Sampling Approach for Bias Mitigation [57.17709477668213]
  We introduce a new class-conditioned sampling method: Bias Mimicking. Bias Mimicking improves underrepresented groups' accuracy of sampling methods by 3% over four benchmarks.
  arXiv  Detail & Related papers  (2022-09-30T17:33:00Z)
• A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments [54.172993875654015]
  The paper proposes a family of communication efficient methods for distributed learning in heterogeneous environments. One-shot approach, based on local computations at the users and a clustering based aggregation step at the server is shown to provide strong learning guarantees. For strongly convex problems it is shown that, as long as the number of data points per user is above a threshold, the proposed approach achieves order-optimal mean-squared error rates in terms of the sample size.
  arXiv  Detail & Related papers  (2022-09-22T09:04:10Z)
• Examining and Combating Spurious Features under Distribution Shift [94.31956965507085]
  We define and analyze robust and spurious representations using the information-theoretic concept of minimal sufficient statistics. We prove that even when there is only bias of the input distribution, models can still pick up spurious features from their training data. Inspired by our analysis, we demonstrate that group DRO can fail when groups do not directly account for various spurious correlations.
  arXiv  Detail & Related papers  (2021-06-14T05:39:09Z)
• Transfer Learning with Multi-source Data: High-dimensional Inference for Group Distributionally Robust Models [0.0]
  Learning with multi-source data helps improve model generalizability and is integral to many important statistical problems. This paper considers multiple high-dimensional regression models for the multi-source data. We devise a novel it DenseNet sampling method to construct valid confidence intervals for the high-dimensional maximin effect.
  arXiv  Detail & Related papers  (2020-11-15T16:15:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.