Research map / Learning theory and algorithms / Prediction and decision losses

PriorBoost: An Adaptive Algorithm for Learning from Aggregate Responses

ICML 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Active learning and subset selection · 0 citations (OpenAlex)

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.

Shows that optimal bag construction for event-level loss in linear regression and GLMs reduces to 1-D size-constrained k-means, and proposes PriorBoost, an iterative algorithm that refines bags using predictions from the previous round's model.

Problem

Learning from aggregate responses (LAR) with bags: how to construct non-overlapping bags of minimum size k so that a model trained on bag-mean responses with event-level loss predicts individual responses well, without the learner seeing individual labels.

Approach

Use prior predictions of E[y|x] to form homogeneous bags via 1-D size-constrained k-means (sorted-structure DP), and iterate across data slices so each round's model produces better bags for the next, training only on the latest slice's aggregates.

Key results

• PriorBoost converges to the k=1 optimal test MSE for all bag sizes k in linear regression, while OneShot's test loss worsens as k increases.
• In logistic regression with label DP, PriorBoost's loss improves as bag size k grows (e.g., k=64 nearly reaches non-private loss for epsilon >= 0.3), whereas OneShot degrades.
• Theory: constrained k-means bags give estimator error vanishing as n,d grow, while random bags keep a non-vanishing bias of at least (1-1/k)^2 ||theta*||^2.

Measured effects reported in the paper

Surprising findings

• Under label DP, PriorBoost's utility improves with larger bag size k, the opposite of the non-adaptive OneShot baseline.
• The optimal bag size for PriorBoost grows with the sample size n.

Limitations

• Theoretical guarantees are for linear models under subgaussian features and asymptotic regimes; GLM analysis relies on upper bounds and a condition m/d large relative to the variance ratio.
• Experiments are limited to synthetic data for linear and logistic regression; no real-world datasets reported in the provided text.
• Prior predictions may mismatch the ordering of true responses, degrading bag quality (quantified via a mismatch term).

Experimental setup

Datasets: synthetic Gaussian linear/logistic regression data

Benchmarks: synthetic linear regression (test MSE) synthetic logistic regression (test log loss)

Metrics: test MSE test log loss

Baselines: OneShot PBPrefix random bagging

Builds on: learning from label proportions k-anonymity label differential privacy bag-level loss

Closest papers by meaning

• Learning from Aggregate responses: Instance Level versus Bag Level Loss Functions (ICLR 2024 · similarity 0.92)
• It's My Data Too: Private ML for Datasets with Multi-User Training Examples (ICML 2025 · similarity 0.83)
• Fairness without Harm: An Influence-Guided Active Sampling Approach (NeurIPS 2024 · similarity 0.83)
• Class-Attribute Priors: Adapting Optimization to Heterogeneity and Fairness Objective (AAAI 2024 · similarity 0.83)
• Nearly Optimal Sample Complexity for Learning with Label Proportions (ICML 2025 · similarity 0.83)
• Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers (AAAI 2024 · similarity 0.83)