Research map / Learning theory and algorithms / Sample complexity
On the sample complexity of semi-supervised multi-objective learning
Tobias Wegel, Geelon So, Junhyung Park, Fanny Yang
Read the paperCheck your idea against 137,217 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.
Studies sample complexity of semi-supervised multi-objective learning, showing a label-complexity lower bound for zero-one loss even with Bayes classifiers and marginals known, and that pseudo-labeling with Bregman losses lets unlabeled data absorb the complexity of the richer class G, with uniform and localized rates.
Problem
Learning Pareto-optimal trade-offs across K tasks within a large model class G when each task is solvable in a smaller class H_k; the question is how much labeled versus unlabeled data is needed.
Approach
For Bregman losses, excess risks can be written as discrepancies from the Bayes-optimal predictor, so per-task ERMs on labeled data are used to pseudo-label unlabeled data, and the trade-off is then optimized over G; this makes the labeled complexity depend only on the H_k and the complexity of G enter only through unlabeled data.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Give the learner Bayes-optimal classifiers and marginal distributions but retain zero-one loss | Ideal semi-supervised S-MOL · Multi-objective binary classification | label sample complexity lower bound: at least CKd_G/eps^2 | No clear effect |
| Use PL-MOL with zero-one loss without additional regression structure | PL-MOL · Multi-objective binary classification | excess s-trade-off: c>0 (e.g., c=0.1) | Hurt |
| Estimate conditional means in a manageable class Theta_k before fitting trade-offs | Zero-one pseudo-labeling · Ideal semi-supervised S-MOL with zero-one loss | label sample complexity: Kd_Theta_k/eps^4 | Improved |
| Use PL-MOL with expanded polynomial class G rather than supervised ERM-MOL over G | Logistic regression trade-off learning · Logistic regression | excess s-trade-off | Improved |
| Use PL-MOL rather than ERM-MOL when unlabeled sample sizes are large | Lipschitz regression · Non-parametric regression with Lipschitz functions | excess s-trade-off: N_1=N_2 = 2^{12}; 2^5 | Improved |
| Increase unlabeled sample size while keeping labeled sample size sufficient to learn H | PL-MOL · Lipschitz regression | excess s-trade-off | Improved |
| Use an unlocalized rather than localized bound | PL-MOL · Non-parametric regression with Lipschitz functions | excess s-trade-off rate: L_H^{1/4}n_k^{-1/4} + L_G^{1/2}N_k^{-1/2} -> (L_H/n_k)^{2/3}+(L_G/N_k)^{2/3} | Hurt |
Surprising findings
- For the zero-one loss, pseudo-labeling can be inconsistent even with infinite unlabeled data, performing worse than ERM.
- Knowing the per-task Bayes classifiers does not help with trading off zero-one losses, unlike Bregman losses.
Limitations
- Localized bounds require linear scalarizations, star-shaped and convex-class assumptions, and norm equivalence.
- Results rely on Bregman losses; pseudo-labeling is inconsistent for non-Bregman losses such as zero-one loss.
- Experiments are small synthetic toy settings.
Experimental setup
Metrics: excess s-trade-off Pareto front sample complexity bound
Baselines: ERM-MOL linear ERM-MOL polynomial ERM-MOL
Builds on: empirical risk minimization local Rademacher complexity multi-distribution learning
Closest papers by meaning
- Nearly Optimal Sample Complexity for Learning with Label Proportions (ICML 2025 · similarity 0.87)
- Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.85)
- CGMatch: A Different Perspective of Semi-supervised Learning (CVPR 2025 · similarity 0.85)
- High-Dimensional Bayesian Optimization via Semi-Supervised Learning with Optimized Unlabeled Data Sampling (ICML 2024 · similarity 0.85)
- A New Concentration Inequality for Sampling Without Replacement and Its Application for Transductive Learning (ICML 2025 · similarity 0.85)
- Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.85)
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.
