REVIEW 2 major objections 6 minor 13 references
Nearly Optimal Sample Complexity for Learning with Label Proportions
T0 review · 2 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read The paper proves that learning from label proportions under square loss is nearly as sample-efficient as ordinary supervised learning, with only a linear bag-size penalty.
desk verdict Solid LLP sample-complexity paper: the linear-in-k upper bounds for square loss are the real contribution; the k/β lower bound is only proved asymptotically, not over the stated k=Ω(1/β) range. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the debiased, clipped bag-level square loss. For bag $z_j=(B_j,\alpha_j)$, define $\tilde{\alpha}_j=\alpha_j-p$ and $\tilde{E}_j(h)=\sum_{x\in B_j}h(x)-k\mathbb{E}[h(x)]$, with $p=\mathbb{E}[h^\star(x)]$; the unclipped loss is $\ell(h,z_j)=\frac1k(k\tilde{\alpha}_j-\tilde{E}_j(h))^2+(\mathbb{E}[h(x)]-p)^2$, whose bag-level expectation equals the individual square loss $L(h)$. The clipping factor $G_j(h)=\mathbf{1}\{|k\tilde{\alpha}_j-\tilde{E}_j(h)|\le \sqrt{8k\log(2/\theta)}\}$ truncates large deviations. The proof derives bias $O(k\theta)$, variance $O((\gamma(\hat{h}^\star,h^\star)+L(h)-L(\hat{h}^\star))\log(1/\theta)+k^2\theta)$, and range $O(\log(1/\theta))$ for the loss differences, and feeds them into a Bernstein-based fast-rate ERM analysis. For SGD, the same bag loss is centered by $\mu_x,\mu_y$ and truncated by $\|\bar{x}_j-\mu_x\|\le\theta\rho_x$, making each update $\zeta$-smooth and convex so that an online-to-batch argument yields the stated rates.
What would settle it
Run the paper's own variance probe: with $x$ uniform on $[0,1]$, $h^\star(x)=x^2$, $\hat{h}(x)=x$, and $p$ computed exactly, estimate the variance of the bag-level loss for bag sizes $k=2,\dots,256$. If the variance grows linearly with $k$, as it does for the prior estimators in Figure 2, rather than staying near constant, the variance-reduction claim collapses. A second test: on the two-function problem with $\Delta=0$, any algorithm that reliably identifies $h^\star$ with $n=o(k/\beta)$ samples would refute the lower bound.
Extended reading notes
Core claim
The central claim is that, for square loss with i.i.d. non-overlapping bags, bag-size dependence in LLP sample complexity is linear, not quadratic or cubic. For a finite class $H$, the ERM bound is $m=\widetilde{O}((\gamma(\hat{h}^\star,h^\star)+\beta)\log(k/\beta)/\beta^2)$ bags, hence $n=\widetilde{O}(k/\beta^2)$; when the Bayes predictor lies in $H$, the bound improves to $n=\widetilde{O}(k/\beta)$. The SGD version for norm-bounded linear predictors has the same rates. The upper bounds rest on a bag-level square loss that is an unbiased estimate of the individual loss, and a lower bound (Theorem 3.1) shows that when $\Delta=0$ no algorithm can succeed with fewer than $n=\Omega(k/\beta)$ samples. In short, the paper establishes that aggregating labels into proportions costs only a linear factor in bag size (up to logarithms) for square loss.
Load-bearing premise
The load-bearing premise is that the algorithm knows, or can estimate accurately, the expected predictions $\mathbb{E}[h(x)]$ and the label marginal $p$ (and the means $\mu_x,\mu_y$ for SGD), because the whole variance reduction depends on the bag-level loss being an unbiased estimator of the individual square loss; the paper proves the estimated version only for ERM, and for SGD it states the variant without proof.
Editorial extensions
If this is right
- Under square loss, ERM from label proportions needs only $\widetilde{O}(k/\beta)$ samples in the realizable case instead of the prior $\widetilde{O}(k^3/\beta)$, making the bag-size penalty linear.
- In the non-realizable case the bound is $\widetilde{O}(k/\beta^2)$, improving on the prior $\widetilde{O}(k^2/\beta^2)$ slow-rate bound.
- The $\Delta=0$ lower bound shows that no algorithm, even for a two-function class, can remove the linear dependence on $k$; the upper bound is therefore essentially tight.
- The SGD variant achieves the same rates for linear predictors, including fast $O(1/m)$ convergence when the noise level $L^\star$ is small, compared with $O(1/\sqrt{m})$ for earlier unbiased estimators.
Reading between the lines
- The same centering-plus-clipping mechanism suggests a transferable recipe: any loss that admits an unbiased bag-level estimator built from first moments can likely be variance-reduced the same way; testing it on log loss would require new bounds because log loss is unbounded.
- The mean-estimation variant of the ERM result pays $\log|H|$ instead of $\log|H_\beta|$; until a fully proved SGD variant with estimated means appears, the SGD rates should be trusted mainly when $p$ and $\mathbb{E}[h(x)]$ are computable.
- The $\min(1/\Delta^2,k/\beta)$ bound implies that estimating the bias $\Delta$ first and using a simple moment test when it is large could save samples in practice, an extension the paper only sketches for two functions.
- In privacy-motivated aggregation settings, this result suggests larger bag sizes no longer carry a quadratic or cubic sample penalty, so aggregators can offer stronger privacy at the same utility; that connection is not developed in the paper.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Learning from Label Proportions (LLP) under square loss, where the learner observes only bag-level label proportions. The authors propose variance-reduced bag-level losses for ERM and SGD, and prove sample complexity bounds of the form n = Õ(k/β) in the realizable case and n = Õ(k/β²) in the non-realizable case, improving on prior bounds that scaled as k²/β² and k³/β. A warm-up two-function realizable setting is analyzed with a matching lower bound up to constants, claiming Ω(k/β) when the bias Δ=0. The paper also includes an experimental comparison against EasyLLP, Li et al., and proportion-matching baselines, showing improved accuracy for larger bag sizes and fewer epochs.
Significance. If the results hold as stated, the paper essentially settles the dependence on bag size for square-loss LLP, improving the state of the art by a factor of k in both realizable and non-realizable regimes. The upper-bound analyses are detailed and the derivations of LB(h)=L(h), the bias-variance trade-off, and the Bernstein-based ERM analysis are sound in large part. The paper also provides a reproducible experimental study, including a variance comparison that illustrates the practical benefit of the proposed debiasing. The main weakness is the lower-bound proof in Theorem 3.1, which is only asymptotic in k but stated for k=Ω(1/β); this gap affects the central 'essentially optimal' claim. Fixing this, or relaxing the theorem statement, is necessary before the paper can be accepted.
major comments (2)
- [§3, Theorem 3.1 & Appendix A.1] The lower bound in Theorem 3.1 is stated for k=Ω(1/β), but the proof in Appendix A.1 establishes the mutual-information bound I(h⋆;(B1,α1)) ≤ −½log₂(1−β)+Õ(1/√k) only in an asymptotic regime where the entropy expansions (Theorems A.1 and A.2) apply and the remainder is 'smaller than β/2.' To make the total bound O(β), one needs 1/√k = O(β), i.e., k=Ω(1/β²) up to log factors, not merely k=Ω(1/β). Moreover, since −½log₂(1−β) ≈ 0.721β, the assertion that this quantity is 'of the form β' and 'becomes smaller than β/2' is numerically incorrect; the relevant requirement is that the whole bound is O(β). Consequently, the proof does not support the stated Ω(k(1−E(δ))/β) lower bound over the range k=Ω(1/β). Because this lower bound is the basis for the paper's claim that the k/β dependence is essentially optimal and that log k factors are shaved from the lower bound of Li et al. (2024), the theorem statement or the proof must be revised.
- [§4, Theorem 4.1 & Appendix B.2] The main text asserts that the ERM variant with estimated E[h(x)] and p 'enjoys the same sample complexity guarantees as above,' which includes a dependence on log|Hβ|. However, the proof in Appendix B.2 produces bounds with log|H| — the union bound is over h1,h2∈H and the condition on m2 depends on log|H|/δ — and Remark B.1 merely states that the dependence can be improved to log|Hβ| without giving the argument. As written, the theorem's claim that the estimated variant has the same guarantees is not fully supported. Please either provide the missing proof or weaken the statement to reflect the log|H| dependence.
minor comments (6)
- [Appendix A.1] The proof of the lower bound uses asymptotic expansions (O(1/k), O(1/√k), 'when k is large') inside a finite-sample theorem. Please state explicit non-asymptotic bounds with appropriate constants, or add a formal condition on k in Theorem 3.1 that matches what the proof actually requires.
- [§7, Conclusions and Limitations] The limitation statement that 'Theorem 3.1 applies only when k is big enough (k=Ω(1/β))' understates the issue: the proof requires k to be considerably larger (on the order of 1/β², up to log factors) for the remainder term to be controlled. Please correct this statement.
- [§5, Theorem 5.1] The text says the SGD algorithm 'can be immediately modified' to handle estimated μx and μy, but no proof or proof sketch is given. A brief remark with the main steps of such a modification would make the claim more concrete.
- [§6, Figures and text] There are several typos: 'variacne' in the Figure 2 caption, 'overalapped' in the Figure 1 caption, and 'worse worse' in Section 6.4.
- [§6.3, footnote 4] The footnote states that an earlier implementation of the Li et al. baseline contained a measurement bug, but the specific correction is not described. Adding a sentence on the corrected implementation would improve reproducibility.
- [§4, Equation (2)] The notation eαj and eEj(h) is used before it is formally defined; please define these quantities explicitly just before Equation (2).
Circularity Check
No circular dependency found: the upper and lower bounds follow from direct algebraic identities, concentration inequalities, and information-theoretic arguments rather than from the claims being proved.
full rationale
The derivation chain is self-contained. The key unbiasedness identity in Eq. (3), LB(h)=L(h), is proved by expanding the bag-level loss into zero-mean i.i.d. terms and computing the variance directly; it is not assumed as the desired regret bound. Theorem 4.1 then follows from Bernstein-style concentration applied to clipped loss differences, with the bias, variance, and range bounds derived from the clipping threshold θ and the metric γ(·,·); no fitted parameter is renamed as a prediction. Theorem 5.1 is obtained from a standard online-to-batch regret bound for smooth convex losses, with bias controlled by Lemma C.2; the population excess risk bound is not an input to the algorithm's analysis. The lower bound in Theorem 3.1 uses Fano's inequality and the data-processing inequality together with entropy estimates for Poisson-binomial distributions; it does not assume the Ω(k/β) rate. Self-citations to Busa-Fekete et al. (2023) appear only as experimental baselines and as the source of the experimental setup, not as justification of the central theoretical claims. The appendix's unsupported remark in Remark B.1 that |H| can be replaced by |Hβ|, and the scope restriction k=Ω(1/β) noted in Section 7 ("Theorem 3.1 applies only when k is big enough (k=Ω(1/β)), not for smaller k") are potential rigor or correctness concerns, but they are not instances of circular reasoning: no claim reduces to its own input by construction.
Assumptions & free parameters
assumptions (5)
- domain assumption Bags are non-overlapping and drawn i.i.d. from a fixed joint distribution D over X×Y.
- domain assumption Hypothesis space H is finite for Theorems 3.1 and 4.1.
- domain assumption The marginal statistics p = E[h*(x)], E[h(x)], and for SGD μ_x = E[x] and μ_y = E[y] are known exactly or can be estimated at higher resolution than the bag labels.
- domain assumption Labels are binary in Sections 3-4 and bounded real-valued in Section 5; features and linear predictors are norm-bounded.
- standard math Standard concentration and anti-concentration results: Hoeffding, Bernstein, Chernoff, vector Hoeffding, Berry-Esseen, and entropy bounds from Adell et al. 2010 and Harremoës 2001.
Cite this review
Pith. "Pith review of Nearly Optimal Sample Complexity for Learning with Label Proportions." pith.science (2026). https://pith.science/paper/IMCJBIZX
@misc{pith2026250505355,
author = {Pith},
title = {Pith review of: Nearly Optimal Sample Complexity for Learning with Label Proportions},
year = {2026},
howpublished = {\url{https://pith.science/paper/IMCJBIZX}},
note = {Machine review of arXiv:2505.05355}
}
read the original abstract
We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags, and only aggregate label values in each bag are available. Despite the partial observability, the goal is still to achieve small regret at the level of individual examples. We give results on the sample complexity of LLP under square loss, showing that our sample complexity is essentially optimal. From an algorithmic viewpoint, we rely on carefully designed variants of Empirical Risk Minimization, and Stochastic Gradient Descent algorithms, combined with ad hoc variance reduction techniques. On one hand, our theoretical results improve in important ways on the existing literature on LLP, specifically in the way the sample complexity depends on the bag size. On the other hand, we validate our algorithmic solutions on several datasets, demonstrating improved empirical performance (better accuracy for less samples) against recent baselines.
Figures
Reference graph
Works this paper leans on
-
[1]
No other processing is performed on CIFAR-10. Higgs: The Higgs dataset consists of Monte-Carlo simulated particle accelerator data, where the goal is to distinguish between processes that create Higgs bosons and that do not. Each example has 28 features consisting of raw simulated measurements and several human-designed higher level features. The Higgs da...
work page 2014
-
[6]
Lu, N., Niu, G., Menon, A. K., and Sugiyama, M. On the minimal supervision for training any binary classifier from only unlabeled data. In Proc. ICLR, 2019,
work page 2019
-
[10]
= 1 2 for bothh⋆ =h1 andh⋆ =h2. Moreover, for square loss, |L(h1)−L (h2)| = E[(h1(x)−h2(x))2] = 1 2(h1(1)−h2(1))2 + 1 2(h1(0)−h2(0))2 =β. Consider an i.i.d. sample ofm bags of sizek: S = ((x1,1,x 1,2,...,x 1,k),α 1)| {z } (B1,α1) ,..., ((xm,1,xm,2,...,x m,k),αm)| {z } (Bm,αm) , and any functionbh :{S}→H that maps any such sample toH. We consider the amoun...
work page 2006
-
[11]
In order to achieve fast rates, we will investigate loss differences
Therefore LB(h) = 1 k E kX i=1 vi !2 + (E[h(x)]−p)2 = 1 k E " kX i=1 v2 i # + 1 k E kX i̸=j vivj + (E[h(x)]−p)2 = E[v2 1] + (E[h(x)]−p)2 (using the fact that the variablesvi are zero-mean and independent) = Var(yj,1−h(xj,1)) + (E[h(x)]−p)2 = E[(y−h(x))2] =L(h), as anticipated. In order to achieve fast rates, we will investigate loss differe...
work page 2000
-
[12]
First, we note that E[ℓj(w)] =L(w); this follows directly from Equation (3)
Proof. First, we note that E[ℓj(w)] =L(w); this follows directly from Equation (3). Further, for allw such that∥w∥≤ ρw we haveℓj(w)≤ 9k(ρwρx +ρy)2, hence E[ℓj(w)]− E[eℓj(w)] = E h ℓj(w)·{∥ ¯xj−µx∥>θρ x} i ≤ 9k(ρwρx +ρy)2 P ∥¯xj−µx∥>θρ x . To bound the probability on the right-hand side, note that ¯xj−µx is an average of k i.i.d. zero-mean random vectors b...
work page 2013
-
[2000]
Improving the sample complexity using global data
Mendelson, S. Improving the sample complexity using global data. IEEE Trans. Inform. Theory, 48:1977–1991,
work page 1977
-
[2002]
Supervised learning by training on aggregate outputs
Musicant, D., Christensen, J., and Olson, J. Supervised learning by training on aggregate outputs. In Proceedings of the 7th IEEE International Conference on Data Mining (ICDM 2007),
work page 2007
-
[2005]
Deep learning from label proportions for emphysema quantification
Bortsova, G., Dubost, F., Orting, S., Katramados, I., Hogeweg, L., Thomsen, L., Wille, M., and de Bruijne, M. Deep learning from label proportions for emphysema quantification. In Medical Image Computing and Com- puter Assisted Intervention – MICCAI 2018, pp. 768–776,
work page 2018
Show all 13 references
-
[2006]
and Kuck, H
de Freitas, N. and Kuck, H. Learning about individuals from group statistics. In Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence (UAI 2005), pp. 332–339,
2005
-
[2010]
doi: 10.1109/tit.2010
ISSN 1557-9654. doi: 10.1109/tit.2010. 2044057. URL http://dx.doi.org/10.1109/ TIT.2010.2044057. Baldi, P., Sadowski, P., and Whiteson, D. Searching for Ex- otic Particles in High-Energy Physics with Deep Learn- ing. Nature Commun., 5:4308,
2010
-
[2017]
Deep multi-class learning from label propor- tions
Dulac-Arnold, G., Zeghidour, N., Cuturi, M., Beyer, L., and Vert, J.-P. Deep multi-class learning from label propor- tions. arXiv preprint arXiv:1905.12909,
1905 arXiv
-
[2019]
Binomial and poisson distributions as maxi- mum entropy distributions
Harremoës, P. Binomial and poisson distributions as maxi- mum entropy distributions. IEEE Transactions on Infor- mation Theory, 47(5):2039–2041,
-
[2022]
and Zhang, J
Scott, C. and Zhang, J. Learning from label proportions: A mutual contamination framework. In Advances in Neu- ral Information Processing Systems 33: Annual Confer- ence on Neural Information Processing Systems 2020, NeurIPS 2020,
2020
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.