{"id":"1d61d688-d1b0-44c2-a9c0-917e20c97a39","arxiv_id":"2411.19045","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For multiple instance regression and learning from label proportions, optimal data bagging for linear regression reduces approximately to k-means clustering over labels or features, and the mechanisms can be made label-differentially private with a quantified utility cost.","lead":"This paper studies how to best group data into bags when only aggregate labels (one label per group) are available, showing that good groupings reduce to familiar k-means-like clustering problems. It also adds privacy guarantees for these grouping schemes, which matters for systems that must learn from aggregated user data.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The instance-MIR reduction to k-means (Thm 1, Eq. 3) is only valid when n=mk; for n>mk the equal-size program is infeasible, so the claimed optimal bagging is unproven under the stated |B_l|≥k constraint.","rationale":"The reader's weakest assumption identifies exactly this feasibility/equality gap, and I agree with it. The paper's central theoretical contribution is the claim that optimal bagging reduces to k-means; Theorem 1 and the surrounding text are the first and most load-bearing instance of that claim. If the intended setting really is n=mk, then the lower-bound constraint and the equal-size constraint coincide and the concern disappears, so the fix is a modest clarification rather than a rejection. But as written, the theorem overclaims: for n>mk the optimization in (3) is infeasible, and the paper gives no argument that the unconstrained-size optimum behaves like the equal-size k-means solution. The rest of the paper, including the upper-bound proofs and the experimental validation, still supports the weaker statement that k-means bagging is a good heuristic, and the appendix contains the makings of a corrected analysis. The private theorems also contain an independently visible inconsistency between Theorem 5 and Appendix B.5.2, but the equal-size feasibility gap is the more fundamental issue for the central claim, so I did not split the attack across both. The verdict should remain conditional, not because the concern is minor, but because it is precisely the kind of missing-assumption gap that a revised version can close.","tokens_in":28916,"tokens_out":11720,"duration_ms":115135,"concrete_test":"Run a brute-force enumeration on n=5, k=2, m=2 with ỹ = [0,1,10,11,100]: list all partitions into 2 nonempty bags with |B_l|≥2, compute the RHS of (2) for each, and check whether any partition achieving the maximum has all bags of size k=2. Since 5 cannot be split into two 2-element bags, the optimization (3) is infeasible, which by itself shows Theorem 1's reduction does not apply to the stated problem unless n=mk is added.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing gap is the reduction of instance-MIR bagging to the k-means objective (3) under the stated constraints. The problem definition allows any bagging with |B_l| ≥ k, and only requires n ≥ mk. For the bound (2), the only bag-dependent term is T(B)=Σ_l (Σ_{i∈B_l} ỹ_i)^2 / |B_l|; Lemma 13 is an identity linking T(B) to the k-means objective for that same B, but it does not characterize the maximizer of T over the feasible set. The optimization problem (3) imposes |B_l| = k for every bag, which either is the only feasible case (when n=mk) or has no solution at all (when n>mk). In the latter case the stated reduction is not just unproven but infeasible: no partition of n points into m bags of size k exists, while the original constraint admits many baggings. The paper does not state or prove that the optimum under |B_l| ≥ k must have all bags exactly size k; examples with n>mk and k=2, m=2 (e.g., n=5) show the equal-size program cannot even be formulated. Thus Theorem 1 and the Section 1.2.1 'amounts to' claim hold only under an unstated assumption n=mk (equivalently m=n/k), and the claimed optimality of k-means bagging is not established for the problem as defined.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies how to partition a training set into bags for Multiple Instance Regression (MIR) and Learning from Label Proportions (LLP) so that a downstream linear regression model, trained only on aggregate bag labels, is as close as possible to the underlying model. For instance-level MIR, bag-level LLP, and aggregate-level MIR, it derives upper bounds on the expected squared parameter error and claims that optimizing these bounds reduces to natural objectives: k-means over labels, minimizing the condition number of the bag-centroid covariance, and a combination of both. It then presents label-differentially-private versions of these bagging mechanisms with quantified extra error, extends the analysis to GLMs, and reports experiments on synthetic data.","tokens_in":29248,"tokens_out":18034,"duration_ms":161593,"significance":"If the reductions were proven, the paper would provide a principled, parameter-free account of optimal bag construction in aggregate-label regression, with practical guidance (k-means on feature vectors) and explicit privacy-utility trade-offs. The paper's strengths include the clean decomposition of the instance-MIR error into a bag-dependent k-means-like term, the breadth of the experimental study, and the attempt to give formal label-DP guarantees. However, the central optimality claims rely on several unproven equal-size reductions and a number of coefficient-level proof errors; the random-bagging analysis for bag-LLP is invalid as written, and the GLM extension is not quantitatively supported. The paper is promising but not ready in its current form.","major_comments":[{"comment":"The reduction to the equal-size k-means program (3) is not justified. The problem definition in Section 1.2 only requires |B_l| ≥ k and n ≥ mk; when n > mk, no feasible solution to (3) exists, because the program insists on |B_l| = k for all m bags. Lemma 13 is an identity for a fixed bagging and does not characterize the maximizer of T(B) = Σ_l (Σ_{i∈B_l} y~_i)^2 / |B_l| under the stated constraint; allowing variable bag sizes can increase T(B). Theorem 1 and the claimed equivalence therefore hold only under an unstated assumption such as n = mk, and the conclusion that optimal bagging reduces to k-means is not established for the problem as defined.","section":"Section 1.2.1, Eq. (3); Theorem 1"},{"comment":"The random-bagging analysis for bag-LLP is invalid as written. Lemma 11 states λ_min((SX)^T SX) = (1/k^2) λ_min(Σ_l X_l^T X_l), but (SX)^T SX is the sum of outer products of bag centroids, which includes cross terms (Σ_{i∈B_l} x_i)(Σ_{i∈B_l} x_i)^T; it is not equal to the sum of per-instance outer products X_l^T X_l. Equation (13) and the subsequent Matrix Chernoff bound therefore control a different matrix from the one appearing in Theorem 2. In addition, Theorem 2 defines f(X) = g(X)g(X)^T as an m×m matrix, which is singular with λ_min = 0 whenever m > d (as in the experiments, where m = 5,000 and d = 32), making the stated condition-number bound vacuous; the d×d matrix (SX)^T(SX) used in the appendix is the appropriate object.","section":"Section 2.2.1, Lemma 11 and Eq. (13)"},{"comment":"The proof of Proposition 10 uses E[||A||_op^2] = 1, but for the attribution matrix defined by Eq. (8), all rows in the same bag are identical unit vectors, so ||A||_op^2 = max_l |B_l|, which equals k for equal-size bags. This changes the constant in Theorem 1 and, more importantly, the bag-label noise term in Theorem 4: the claimed extra error d α^2/k^2 in the full version would become d k times the per-label noise variance (or an n term under the alternative inequality), so the privacy-utility trade-off is not correctly quantified.","section":"Appendix B.2, Proposition 10"},{"comment":"Lemma 14 computes the expected difference between k-means objectives for a fixed bagging B, but the private clustering mechanism in Theorem 4 chooses B as the optimal clustering of the noisy labels, so B and the label noise γ are dependent. Conditioning on the realized B changes the distribution of γ, and the equality E[k-means(B(y))] = E[k-means(B(y~))] + (n-m)σ^2 does not follow for the data-dependent clustering. The claimed additional privacy error n(1-1/k)α^2 from 'add N(0,α^2) then cluster optimally' is therefore unsupported.","section":"Appendix B.1 and B.5.1, Lemma 14"},{"comment":"In the proof of the aggregate-MIR bound, the term E[||Aγ||_2^2] is evaluated as nσ^2. Since A is the m×n attribution matrix of Eq. (15), Aγ contains one selected label noise per bag, so the expectation is mσ^2. This makes the noise term in Theorem 3 and in the aggregate-MIR privacy analysis (B.5.3, 'additional error of nk α^2/k^2') incorrect by a factor of k; the stated aggregate-MIR privacy guarantee is not established.","section":"Appendix B.4, Theorem 3"},{"comment":"Theorem 5 as stated in the main text, E[||·||^2] = OPT(d/k α^2 + σ^2 m/k) with α^2 = 4R^2 log(1.25/δ)/ε^2, differs from the full version in Appendix B.5.2, which gives OPT((σ^2 + α^2/k) m/k) = OPT(σ^2 m/k + α^2 m/k^2). The two formulas have different dependence on d and m, and the theorem is written as an equality even though Theorem 2 provides only an upper bound. The correct expression and its inequality status need to be reconciled.","section":"Section 1.2.4 vs. Appendix B.5.2, Theorem 5"},{"comment":"The GLM analysis contains dimensionally inconsistent algebra. In Theorem 22, the derived optimization objective is written as min Σ_l Σ_{i∈B_l} (μ_i - μ_l)^2 - Σ_l |B_l| μ_l, mixing a quadratic term with a linear term and misdefining μ_l (it appears to be μ_i/|B_l|); the remark that maximizing the second term forces larger bags contradicts the equal-size constraint used elsewhere. Moreover, the bound E[||Ay||^2] ≤ m(||b'(Xθ*)||^2 + ||Db''(Xθ*)||_1) is not derived; under equal-size bags the operator-norm factor should be k, not m. The aggregate-GLM bound in Theorem 23 contains an unexplained factor n and several missing justifications. The GLM generalization is not quantitatively supported in its current form.","section":"Appendix F.1.1, Theorems 22 and 23"}],"minor_comments":[{"comment":"The relationship among n, m, and k is not stated consistently: the text says n ≥ mk, but the theorems reduce to equal-size bags with n = mk, and the experiments never report m. Please state the exact assumptions, including whether n is divisible by k.","section":"Section 1.2 and Section 3"},{"comment":"Algorithm 1 requires n to be divisible by 2k and silently outputs m/2 bags rather than m bags; for general n the procedure is undefined, and the relation to the m-bag problem is unclear.","section":"Section 2.2.1, Algorithm 1"},{"comment":"The private experiments do not specify which differentially private k-means mechanism is used for label k-means, nor how the privacy budget is split between clustering and bag-label noise; without this, the empirical privacy results cannot be reproduced.","section":"Section 3, Table 2"},{"comment":"Theorem 4's displayed bound has unbalanced parentheses in the definition of α^2, and the main-text and appendix versions of the bound differ in the coefficient of OPT; these need to be reconciled.","section":"Section 1.2.4, Theorem 4"},{"comment":"The reference list contains a broken citation '[Ska, pri]' and typos such as 'intital' in Appendix B.5.2 and 'event-level MIR' in Appendix F.1.1; these should be corrected.","section":"References and typos"}],"recommendation":"major_revision","confidential_remarks":"The number of load-bearing proof errors is high. If the equal-size reduction in Theorem 1 and the random-bagging matrix identity in Section 2.2.1 cannot be fixed, the paper's central theoretical claims would need to be substantially weakened, perhaps to heuristic or experimental findings. I would not support acceptance in the current form, but I think the paper is potentially salvageable with a major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real contribution, more useful than the abstract promises, but the \"optimal bagging\" claim is only established under an equal-size condition the paper never states.\n\nThe genuinely new pieces are the MIR instance-level and aggregate-level analyses, the bag-level LLP bound, and the label-DP mechanisms. The instance-level LLP k-means characterization is already in Javanmard et al., and the paper says so. The experiments are simple but honestly reported, and they support the main practical takeaway: k-means over instances is a decent label-agnostic bagging heuristic.\n\nThe load-bearing soft spot is Theorem 1. The bound depends on the term sum_l (sum_{i in B_l} ytilde_i)^2 / |B_l|, and Lemma 13 correctly rewrites that as the k-means objective for the same B. But the reduction then imposes |B_l| = k for all l, while the problem as defined only requires |B_l| >= k and n >= mk. If n > mk, no equal-size partition exists, so the claimed equivalence is either contingent on an unstated n = mk assumption or unproved for the stated problem. The paper should either restrict the setting or prove that the optimum under the lower-bound constraint must have equal-size bags; the proof as written does not do that.\n\nTwo smaller issues. First, the private LLP bound in Theorem 5 differs from the full version in Appendix B.5.2 by a factor of d; the appendix version follows from the noise calculation, so the main text needs correction. Second, the GLM appendix is rough: several inequalities do not have consistent scaling, and the final objective has a garbled definition of mu_l. I would treat Appendix F as a sketch rather than a theorem.\n\nThe citation pattern is honest, and the derivations are parameter-free from the stated assumptions; no circularity problem. The main theorems are upper bounds, and the paper sometimes slides from \"bound\" to \"optimal,\" but the abstract mostly hedges with \"approximately.\"\n\nWho should read this: people building aggregate-label pipelines for ad attribution or privacy-preserving analytics, and theorists working on LLP/MIR bag construction. A serious referee should engage with it. I would send it out, asking for the equal-size fix, reconciliation of the two Theorem 5 statements, and either repair or demotion of the GLM appendix.","headline":"Useful results on bag construction for MIR/LLP under squared loss, but the headline optimality claim rests on an unstated equal-size assumption, and the private LLP bound is internally inconsistent.","tokens_in":29768,"tokens_out":3708,"would_cite":true,"duration_ms":36709,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes that for MIR and LLP under squared loss, the bagging configuration maximizing downstream linear-regression utility is approximately the one minimizing k-means-like objectives over expected labels or bag-centroid…","keywords":["multiple instance regression","learning from label proportions","bagging","k-means clustering","label differential privacy","linear regression","generalized linear models","utility bounds"],"falsifier":"Take four points with expected labels 0, 0, 10, 10, form two bags with minimum size 1, and compare the Theorem 1 utility-bound term. Equal bags of size 2 give $(0+0)^2/2 + (10+10)^2/2 = 200$, while unequal bags of sizes 1 and 3 give $0^2/1 + (0+10+10)^2/3 \\approx 133.3$, so the unequal configuration beats the equal-size solution that the k-means reduction selects.","tokens_in":28744,"feed_emoji":"🎯","tokens_out":7032,"duration_ms":57959,"temperature":0.7,"pith_summary":"This paper asks how a trusted aggregator should partition data into bags when learners only see aggregate labels—one random label per bag (multiple instance regression, MIR) or the bag mean (learning from label proportions, LLP)—so that a downstream linear-regression model is as accurate as possible. The authors prove that for each setting the bagging that maximizes utility is approximately the one minimizing a natural clustering objective: a k-means objective over the expected labels for instance-level MIR, the condition number of the bag-centroid covariance for bag-level LLP, and both for aggregate-level MIR. They further show that each bagging mechanism can be made label-differentially private by adding calibrated noise, with the extra error quantified in the utility bounds, and they extend the analysis to generalized linear models. The upshot is that a single, well-studied primitive—k-means clustering—can serve as the organizing principle for private data aggregation in regression.","feed_headline":"Optimal bagging for private learning reduces to k-means","feed_subtitle":"For MIR and LLP, the best bags for linear regression are the ones that minimize k-means-style objectives.","key_machinery":"The argument runs through two linear-algebra objects that encode bagging: the attribution matrix $A$ for instance-MIR, which assigns each bag's disclosed label to every instance in the bag (with expectation $S$ having entries $1/|B_l|$), and the bagging matrix $S$ for bag-LLP and aggregate-MIR, whose rows average the feature vectors in each bag. The utility bounds are obtained by expanding $\\hat{\\theta} - \\theta^*$ around the true model and bounding terms with the operator norm of $(X^TX)^{-1}X^T$, the expected attribution error, and the spectrum of $(SX)^T(SX)$. The load-bearing identity is Lemma 13: minimizing the k-means objective over expected labels is exactly equivalent to maximizing $\\sum_l (\\sum_{i \\in B_l} \\tilde{y}_i)^2 / |B_l|$, the bag-dependent term in Theorem 1. The LLP and aggregate bounds hinge on the condition number of the bag-centroid covariance, which random bagging controls via a matrix Chernoff tail bound.","core_discovery":"Under squared loss with labels drawn as $y_i = x_i^T \\theta^* + \\gamma_i$, the paper establishes utility upper bounds on $\\mathbb{E}[\\|\\hat{\\theta} - \\theta^*\\|_2^2]$ for three bagged-regression estimators. For instance-MIR, the bound (Theorem 1) is minimized exactly by the k-means clustering of expected labels $\\tilde{y}$, and since $\\tilde{y}$ is a one-dimensional projection, the optimal bags are contiguous segments of the sorted labels. For bag-level LLP, the bound (Theorem 2) reduces to minimizing the ratio $\\lambda_{\\max}/\\lambda_{\\min}$ of the covariance matrix of bag centroids—a label-agnostic objective—and a random bagging algorithm provides a high-probability upper bound on this ratio. For aggregate-level MIR, the bound (Theorem 3) combines the label k-means term with the centroid-condition-number term. The paper then shows that these baggings remain effective under label differential privacy: private instance-MIR pays an extra error from private clustering plus subsampled noise on bag labels, while private bag-LLP pays only the label-noise error because its bagging is label-agnostic. Experiments on synthetic data confirm that instance k-means is a strong heuristic across all three settings.","pith_inferences":["The equal-size assumption is the one place the k-means reduction could silently fail: the paper's experiments use equal-size bags, so whether unequal bags ever improve the non-private utility bound remains an open empirical question that the stated theorems do not settle.","The private-clustering step in Theorem 4 is analyzed via label noise that actually satisfies the stronger local-DP notion; switching to a central-model private k-means could shrink the $n(1-1/k)\\alpha^2$ term, so the bound is likely loose in the privacy regime.","The condition-number objective for bag-LLP suggests that for non-isotropic data the effective label-agnostic bagging should cluster whitened features $\\Sigma^{-1/2}X$ rather than raw $X$; the paper's scaled instance k-means experiments support this, but the theory's guarantee there is only heuristic."],"forward_implications":["If the theorems hold, a practitioner building a regression model from aggregate labels can treat 'choose bags' as 'run k-means on labels or features' and obtain a utility guarantee with no further search.","For bag-level LLP, the optimal bagging is label-agnostic, so the same bagging can be released without using label information, which matters when the aggregator may not know the labels.","Label differential privacy is achievable at a quantified cost: private instance-MIR pays an extra term from private clustering and subsampled label noise, while private bag-LLP pays only label noise.","The GLM extension implies that for instance-MIR over the exponential family, label k-means remains the right bagging target, and for aggregate-MIR with a monotone link, grouping instances with similar expected labels into contiguous sorted bags is optimal.","Since 1D k-means with equal-size bags has contiguous sorted segments, the practical bagging algorithm is simply sorting by labels and cutting into equal chunks."],"supporting_citations":[{"why":"introduces MIR, the setting where a bag label is one instance's label, and defines the problem studied.","marker":"Ray and Page [2001]"},{"why":"introduces LLP, the setting where a bag label is the mean, used in the bag-level loss definition.","marker":"de Freitas and Kück [2005]"},{"why":"provides the lemma that 1D k-means optimal bags are contiguous sorted segments, used to conclude the sorting bagging for instance-MIR.","marker":"Javanmard et al. [2024]"},{"why":"defines the bag-level loss for LLP that the paper optimizes.","marker":"Ardehaly and Culotta [2017]"},{"why":"defines label differential privacy, the privacy notion the private bagging mechanisms satisfy.","marker":"Chaudhuri and Hsu [2011]"},{"why":"supplies privacy amplification by subsampling used to calibrate noise in private instance-MIR.","marker":"Balle et al. [2018]"},{"why":"gives the matrix Chernoff bound used to control the minimum eigenvalue of the bag-centroid covariance under random bagging.","marker":"Tropp [2012]"},{"why":"motivates the aggregate-label problem through privacy-preserving conversion reporting on advertising platforms.","marker":"O'Brien et al. [2022]"}],"fun_headline_variants":["Optimal bagging for private learning is k-means","How to bag data for optimal private learning: use k-means","In MIR and LLP, optimal bags come from k-means clustering"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exact reduction of instance-MIR to k-means requires every bag to have exactly the same size k, the constraint imposed in equation (3), whereas the problem only requires bags of size at least k; if the true optimum uses unequal bag sizes, the claimed equivalence is not established.","fun_headline_variants_meta":{"raw":{"variants":["Optimal bagging for private learning is k-means","How to bag data for optimal private learning: use k-means","In MIR and LLP, optimal bags come from k-means clustering"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000571,"raw_usage":{"total_tokens":2734,"prompt_tokens":1012,"completion_tokens":1722,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":628,"completion_tokens_details":{"reasoning_tokens":1664}},"tokens_in":628,"tokens_out":1722,"duration_ms":14255,"temperature":1.0,"reasoning_tokens":1664,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:38:54.530352+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take four points with expected labels 0, 0, 10, 10, form two bags with minimum size 1, and compare the Theorem 1 utility-bound term. Equal bags of size 2 give $(0+0)^2/2 + (10+10)^2/2 = 200$, while unequal bags of sizes 1 and 3 give $0^2/1 + (0+10+10)^2/3 \\approx 133.3$, so the unequal configuration beats the equal-size solution that the k-means reduction selects.","supporting_citations":[{"cited_title":"PriorBoost: An Adaptive Algorithm for Learning from Aggregate Responses","cited_arxiv_id":"2402.04987","evidence_quote":"provides the lemma that 1D k-means optimal bags are contiguous sorted segments, used to conclude the sorting bagging for instance-MIR."},{"cited_title":"Co-training for demographic classification using deep learning from label proportions","cited_arxiv_id":null,"evidence_quote":"defines the bag-level loss for LLP that the paper optimizes."},{"cited_title":"Sample complexity bounds for differentially private learning","cited_arxiv_id":null,"evidence_quote":"defines label differential privacy, the privacy notion the private bagging mechanisms satisfy."},{"cited_title":"User-friendly tail bounds for sums of random matrices","cited_arxiv_id":null,"evidence_quote":"gives the matrix Chernoff bound used to control the minimum eigenvalue of the bag-centroid covariance under random bagging."},{"cited_title":"Challenges and approaches to privacy preserving post-click conversion prediction","cited_arxiv_id":"2201.12666","evidence_quote":"motivates the aggregate-label problem through privacy-preserving conversion reporting on advertising platforms."}],"review_version":1}