{"id":"fcbf42c4-341b-49f6-bdcd-8b521b21034e","arxiv_id":"2505.05355","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New variance-reduced bag-level losses bring the sample complexity of LLP under square loss down to k/β (realizable) and k/β² (non-realizable), with a lower bound showing linear dependence on bag size is necessary.","lead":"This paper proves that learning from label proportions with square loss needs only about k/β samples in the realizable case, improving on prior k²/β² and k³/β bounds. It also gives a matching lower bound, so the bag-size dependence is essentially optimal.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1's lower bound is proved only for asymptotically large k (effectively k≫1/β²), but stated for k=Ω(1/β); the Ω(k/β) optimality claim is not established over the stated range.","rationale":"The upper-bound theorems (4.1 and 5.1) appear internally consistent: the unbiasedness identity (3) is correct, the bias/variance/clipping bounds in Appendix B.1 are plausible, and the SGD proof in Appendix C is standard. The estimated-moment issue flagged by the reader is real but secondary: Appendix B.2 already contains a sample-splitting ERM variant, albeit with log|H| instead of log|Hβ|, and the SGD extension with estimated μx,μy is asserted without proof. These do not invalidate the stated known-moment theorems. The load-bearing gap is the two-function lower bound in Theorem 3.1, because it is the evidence for the paper's 'essentially optimal' claim and for the improvement over the log k factors in Li et al. (2024). The proof is asymptotic: it requires k large enough for the Õ(1/√k) entropy approximation error to be below β/2, which forces k to grow faster than 1/β (typically k=Ω(polylog(1/β)/β²)), while the theorem only states k=Ω(1/β). For k=c/β, the proof's remainder is of order √β, which can dominate β, so the claimed Ω(k/β) bound does not follow in that regime. The limitation note in Section 7 only mentions k=Ω(1/β), not this stronger requirement. A finite-k re-derivation or exact entropy computation would settle whether the statement itself is true; if the statement is true but the proof needs strengthening, the paper should state the lower bound only for k sufficiently large, with explicit dependence on β.","tokens_in":33637,"tokens_out":21916,"duration_ms":233553,"concrete_test":"Compute the exact mutual information I(h⋆;(B,α)) for the lower-bound construction in Appendix A.1 (X={0,1}, uniform marginal, P(y=1|x=1)=1/2±√β/2) at β=2^{-j}, with k=⌈c/β⌉ and k=⌈c'/β²⌉, using exact binomial and Poisson-binomial entropy formulas. Check whether I≤Cβ for a constant C satisfying C<(1−E(δ)) for some δ<1/2. If the exact I is ≤Cβ for all k=Ω(1/β), the theorem survives and the proof only needs non-asymptotic entropy bounds; if not, Theorem 3.1 must be restated with a stronger lower bound on k (e.g., k=Ω(polylog(1/β)/β²)) and the log-free Ω(k/β) lower-bound claim is currently unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing gap is in the two-function lower bound of Theorem 3.1 and its proof in Appendix A.1. The theorem states unconditionally that when Δ=0 there is a distribution D and hypothesis class H={h1,h2} for which any algorithm must use n=Ω(k(1−E(δ))/β) examples, subject only to k=Ω(1/β). The proof, however, obtains I(h⋆;(B,α)) ≤ −½log₂(1−β)+Õ(1/√k) by invoking asymptotic entropy bounds (Theorems A.1 and A.2) that hold as k→∞, and then asserts this is 'of the form β+Õ(1/√k)' and 'smaller than β/2' when k is large. To make the Õ(1/√k) remainder below β/2 one needs k substantially larger than 1/β — typically k=Ω(polylog(1/β)/β²) — whereas the stated condition k=Ω(1/β) permits k≈c/β, where the remainder is of order √β and can dominate the claimed β gap. Thus the proof does not establish the Ω(k/β) rate over the range stated in the theorem. Since Theorem 3.1 is the basis for the paper's claim that the k/β dependence is essentially optimal and that the log k factors in the lower bound of Li et al. (2024) are shaved off, the central optimality claim is currently supported only in an asymptotic regime that the theorem does not formally state.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":33990,"tokens_out":13255,"duration_ms":127706,"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":[{"comment":"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.","section":"§3, Theorem 3.1 & Appendix A.1"},{"comment":"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.","section":"§4, Theorem 4.1 & Appendix B.2"}],"minor_comments":[{"comment":"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.","section":"Appendix A.1"},{"comment":"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.","section":"§7, Conclusions and Limitations"},{"comment":"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.","section":"§5, Theorem 5.1"},{"comment":"There are several typos: 'variacne' in the Figure 2 caption, 'overalapped' in the Figure 1 caption, and 'worse worse' in Section 6.4.","section":"§6, Figures and text"},{"comment":"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.","section":"§6.3, footnote 4"},{"comment":"The notation eαj and eEj(h) is used before it is formally defined; please define these quantities explicitly just before Equation (2).","section":"§4, Equation (2)"}],"recommendation":"major_revision","confidential_remarks":"The upper-bound contributions appear solid and the experimental study is careful. The main obstacle is the lower-bound proof in Theorem 3.1, which is asymptotic in k and does not cover the stated k=Ω(1/β) range. This directly affects the paper's headline optimality claim. The second issue, concerning the estimated-parameter ERM variant, is more local but still requires a correction to the theorem statement or a proof of the missing log|Hβ| bound. I would be willing to reconsider after a revision that fixes the lower-bound statement/proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe thing to know: this paper gives the first upper bounds for LLP under square loss that scale linearly in bag size k for both ERM and SGD—n=Õ(k/β) realizable, n=Õ(k/β²) non-realizable—with a matching lower bound n=Ω(k/β) in the two-function realizable case. If you work on label proportions, this is the dependence to beat.\n\nWhat is new and good: the clipped bag-level loss is clever. Equation (3), LB(h)=L(h), makes the debiasing transparent, and the bias-variance analysis in Appendix B.1 checks out. The OGD/SGD analysis in Appendix C is also coherent, with smoothness and truncation controlling the bag-dependent variance. The comparison to Busa-Fekete et al. 2023 (k²/β²) and Li et al. 2024 (k³/β) is fair, and the improvement is concrete. The prior work is engaged honestly.\n\nSoft spots:\n\n- Theorem 3.1's lower bound is the main one. The theorem is stated for k=Ω(1/β), but the proof's entropy estimates (Theorems A.1 and A.2) are asymptotic in k, and the Õ(1/√k) remainder only becomes smaller than β/2 when k is substantially larger than 1/β—roughly k=Ω(polylog(1/β)/β²). So the Ω(k/β) lower bound is currently established only in an asymptotic regime, not over the stated range. This matters because it is the basis for the \"essentially optimal\" claim. The upper bounds do not depend on this, so the main contribution survives, but the statement and proof should be aligned.\n\n- The data-dependent version of the SGD algorithm (estimated μx, μy) is asserted without proof. The ERM version is handled in Appendix B.2, but the SGD variant is not. Probably fixable, but as written it is a gap.\n\n- In Appendix B.2, the estimated-p variant replaces log|H_β| by log|H|; Remark B.1 says this can be fixed, but it is not shown.\n\n- Experiments tune the learning rate on the test set, which overstates absolute accuracy. The disclosed bug in the Li et al. baseline is handled honestly, but the empirical comparison should be read with caution. These are minor for a theory paper.\n\nWho it is for: people working on LLP, partial-label learning, or variance-reduced ERM/SGD. It deserves a serious referee; the upper bounds alone justify the review time, and the lower-bound gap is repairable in revision.\n\nRecommendation: send to review. The main theoretical claims are credible; the optimality claim needs a tightened statement or a non-asymptotic proof, and the SGD-estimates variant needs a proof or an explicit limitation.","headline":"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.","tokens_in":34569,"tokens_out":2448,"would_cite":true,"duration_ms":23843,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["learning from label proportions","sample complexity","square loss","variance reduction","fast rates","empirical risk minimization","stochastic gradient descent","bag-level loss"],"falsifier":"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.","tokens_in":33463,"feed_emoji":"🏷️","tokens_out":12134,"duration_ms":117659,"temperature":0.7,"pith_summary":"This paper tries to prove that learning from label proportions (LLP) under square loss needs essentially no more samples than ordinary supervised learning, apart from a factor linear in the bag size $k$. The proposed ERM and SGD algorithms achieve sample complexity $\\widetilde{O}(k/\\beta)$ in realizable settings and $\\widetilde{O}(k/\\beta^2)$ in non-realizable settings, improving on previous $\\widetilde{O}(k^2/\\beta^2)$ and $\\widetilde{O}(k^3/\\beta)$ bounds. A two-function lower bound with equal expected predictions ($\\Delta=0$) shows that $n=\\Omega(k/\\beta)$ samples are unavoidable, so the dependence on $k$ is essentially tight. If the claims hold, practitioners who only see aggregated labels can expect the same individual-level accuracy as with full labels, at a predictable and mild cost.","feed_headline":"Bag size now costs only a linear sample penalty","feed_subtitle":"Variance-reduced losses make label-proportion learning essentially optimal, replacing k²/β² and k³/β bounds.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the prior general debiasing technique and the slow $k^2/\\beta^2$ non-realizable baseline that this paper improves, along with the EasyLLP experimental baseline.","marker":"(Busa-Fekete et al., 2023)"},{"why":"Supplies the prior square-loss fast-rate result with $k^3/\\beta$ dependence and the log-$k$ lower bound that this paper sharpens.","marker":"(Li et al., 2024)"},{"why":"Provides the fast-rate bias-variance tradeoff framework used to analyze differences of bag-level losses.","marker":"(Massart, 2000)"},{"why":"Supplies the local complexity framework that lets variance and range bounds be converted into regret bounds in the ERM proof.","marker":"(Bartlett et al., 2005)"},{"why":"Supplies the data-processing and Fano inequalities used in the two-function information-theoretic lower bound.","marker":"(Cover & Thomas, 2006)"},{"why":"Provides the binomial entropy bounds used to bound the mutual information between the hidden hypothesis and a bag.","marker":"(Adell et al., 2010)"},{"why":"Provides the Poisson-binomial entropy comparison bounds used in the lower-bound mutual information calculation.","marker":"(Harremoës, 2001)"},{"why":"Supplies the online gradient descent regret bound used in the SGD proof.","marker":"(Shalev-Shwartz & Ben-David, 2014)"},{"why":"Supplies the online convex optimization regret analysis used in the SGD proof.","marker":"(Hazan et al., 2016)"},{"why":"Supplies the vector Hoeffding concentration inequality used to control the bias introduced by truncation in the SGD analysis.","marker":"(Boucheron et al., 2013)"}],"fun_headline_variants":["LLP sample complexity drops to linear in bag size","Square loss LLP: near-optimal sample complexity","Near-optimal LLP with linear bag cost","Variance reduction yields near-optimal LLP samples"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["LLP sample complexity drops to linear in bag size","Square loss LLP: near-optimal sample complexity","Near-optimal LLP with linear bag cost","Variance reduction yields near-optimal LLP samples"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00119,"raw_usage":{"total_tokens":4888,"prompt_tokens":899,"completion_tokens":3989,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":515,"completion_tokens_details":{"reasoning_tokens":3930}},"tokens_in":515,"tokens_out":3989,"duration_ms":28142,"temperature":1.0,"reasoning_tokens":3930,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:06:40.751201+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}