AI Paper Atlas

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

NeurIPS 2025 · Learning theory and algorithms › Sample complexity · approach: PAC learnability theory · 0 citations (OpenAlex)

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 changedWhereMeasuredEffect
Give the learner Bayes-optimal classifiers and marginal distributions but retain zero-one lossIdeal semi-supervised S-MOL · Multi-objective binary classificationlabel sample complexity lower bound: at least CKd_G/eps^2No clear effect
Use PL-MOL with zero-one loss without additional regression structurePL-MOL · Multi-objective binary classificationexcess s-trade-off: c>0 (e.g., c=0.1)Hurt
Estimate conditional means in a manageable class Theta_k before fitting trade-offsZero-one pseudo-labeling · Ideal semi-supervised S-MOL with zero-one losslabel sample complexity: Kd_Theta_k/eps^4Improved
Use PL-MOL with expanded polynomial class G rather than supervised ERM-MOL over GLogistic regression trade-off learning · Logistic regressionexcess s-trade-offImproved
Use PL-MOL rather than ERM-MOL when unlabeled sample sizes are largeLipschitz regression · Non-parametric regression with Lipschitz functionsexcess s-trade-off: N_1=N_2 = 2^{12}; 2^5Improved
Increase unlabeled sample size while keeping labeled sample size sufficient to learn HPL-MOL · Lipschitz regressionexcess s-trade-offImproved
Use an unlocalized rather than localized boundPL-MOL · Non-parametric regression with Lipschitz functionsexcess 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

Limitations

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

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy