Research map / Learning theory and algorithms / Sample complexity
Linear Regression using Heterogeneous Data Batches
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gradient-based algorithm with clipping and subspace estimation that recovers linear regression vectors for all sizeable sub-populations from heterogeneous batches, removing the isotropic-Gaussian and separation assumptions of prior work.
Problem
Learning linear regression vectors from batches of data where batches come from k unknown sub-populations with possibly different, heavy-tailed input distributions, and most batches are very small.
Approach
Clipped gradient descent where the expected gradient is estimated in a low-dimensional subspace (top singular vectors of a matrix built from small batches) and medium batches are filtered by a test against a reference medium batch; the output is a list of estimates containing one close to each large sub-population's regression vector.
Key results
- In the original Kong et al. setting (isotropic Gaussian, k=16), the proposed algorithm significantly outperforms the baseline at all medium batch sizes tested.
- With different per-subgroup covariances (eigenvalues in [1,4]), the baseline completely fails while the proposed algorithm retains good performance.
- Theoretical sample complexity: O~(d/alpha^2) small batches and O~(min(sqrt k, 1/sqrt alpha)/alpha) medium batches of size O~(min(sqrt k, 1/sqrt alpha)), with output list of size O~(1/alpha).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed gradient-based algorithm instead of the prior baseline | Linear regression from heterogeneous data batches · Simulated setting with isotropic Gaussian inputs, k=16 | MSE | Helped |
| Use the proposed algorithm with different input covariances across subgroups | Linear regression from heterogeneous data batches · Simulated setting with different input distributions, k=16 | MSE | Helped |
| Use the proposed algorithm instead of the prior baseline | Linear regression from heterogeneous data batches · Small regression-vector separation | MSE | Helped |
| Use the proposed algorithm instead of the prior baseline | Linear regression from heterogeneous data batches · Many subgroups, recovering subgroups present in a sufficient fraction of batches | MSE | Helped |
| Reduce the required total sample complexity relative to the prior polynomial-time method | Linear regression from heterogeneous data batches · Theoretical guarantees | sample complexity: by a factor of 1/\alpha^2 | Helped |
Surprising findings
- Selecting from the list using a fresh batch of only logarithmically many samples works better empirically than the theoretically analyzed selection procedure.
Limitations
- Requires a medium-size reference batch b* from the target sub-population and a symmetric-noise assumption for the analysis.
- Output is a list of size O~(1/alpha) rather than a single estimate, and identifying the right entry needs extra samples from the sub-population.
- Only small-scale synthetic experiments are reported; no real-data evaluation.
Experimental setup
Datasets: synthetic Gaussian linear regression batches
Benchmarks: synthetic mixed linear regression batch simulations
Metrics: MSE of selected regression vector on a new batch
Baselines: Kong et al. 2020 batch-based mixed linear regression algorithm
Builds on: mixed linear regression with batches (Kong et al. style subspace estimation) median-of-means estimation list-decodable regression
Closest papers by meaning
- Batch List-Decodable Linear Regression via Higher Moments (ICML 2025 · similarity 0.86)
- Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation (ICML 2024 · similarity 0.84)
- Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms (ICML 2024 · similarity 0.84)
- Learning with Exact Invariances in Polynomial Time (ICML 2025 · similarity 0.83)
- Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach (ICML 2024 · similarity 0.83)
- Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data (ICLR 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.