acceptodds
Under review as a conference paper at ICLR 2027

Bag Design for Model Evaluation from Aggregate Labels

Abstract

Aggregate labels provide responses for groups of instances, or bags, when individual outcomes are unavailable. Existing bag-curation methods target gradient recovery or prediction quality, while evaluating a fixed model requires understanding how grouping affects uncertainty about its ranking performance. Identical group means can support different values of the area under the receiver operating characteristic curve (AUC). We formulate bag design before feedback as minimizing the range of AUC values compatible with exact population group means. When each instance has its own response probability, we derive an exact width formula that sums contributions from score ranks within bags. For distinct scores and equal-capacity bags, adjacent-rank grouping minimizes worst-case width at a fixed overall response probability, provided its product with bag size is an integer. When instances with identical observed features share a response probability, their occurrences across bags couple the constraints. Using specified reference probabilities, we compute the coupled AUC endpoints by linear programming and search for width-reducing swaps that preserve bag sizes. Keeping each repeated state within one bag recovers the sum obtained by treating instance probabilities separately. On twelve-instance blocks, width-minimizing assignments that spread repeated states across bags reduce the median coupled-to-separable width ratio to 0.104, demonstrating that evaluation-width minimization and training-oriented curation can select different bags. In the separate-probability setting, adjacent-rank grouping yields narrower intervals than balanced random assignment across click-log, census and network-traffic workloads. On the click log at a fixed feedback budget, its interval width is 2.4 × 10⁻⁴ versus a balanced-random median of 0.992. These results support designing aggregate-label groups around the performance measure to be evaluated.

Primary area:
learning theory
Keywords:
learning from label proportions, aggregate labels, partial identification, AUC, experimental design, linear programming, model evaluation

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.40 over 5 reviews, above 68% of the others.
Reviewer_PAEhOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper discusses that when only bag-level (aggregate) label means are released, the AUC of a fixed scorer is only partially identified. The paper defines the sharp AUC width: the range of AUC values consistent with exact bag means. It treats the bag partition as a design choice made before feedback is released. The experimental results show that contiguous bags give width 2.4×10⁻⁴ versus 0.992 for random bags on Criteo. On small blocks, the search reduces the AUC range by 60–88% as shown in Table 3.

Critical strengths
  1. Considering bag design for evaluating a fixed model is interesting as it matters how to rank the performance of a model, as if simply change the evaluation method could flip model rank, that could confuse the partitioners.
Critical weaknesses
  1. Aggregate labels are ususally released for privacy protection such that the individal information won't be revealed; but there is no clear discussion how the different bag method could affect the privacy leakage. e.g., label-inference risk is not evaluated.
  2. To design the bag, the curator needs to know the evaluated model's scores; however, for a fair evaluation, isn't these two parts should be independent?
Questions for authors
  1. How does the width design trade off against label leakage? Can you measure it along with the widith shrinkage together on Criteo and Adult? This is the main concern I had, as naturally, by reducing the number of samples in a group, by probing multiple times, the true label information could be leaked.

  2. In table 3, why the adult with 24 has way higher upper 95% confident interval?

1 comment
AuthorsOpenReview ↗

Response to Reviewer PAEh

Thank you for your careful review. We have added matched comparisons on Criteo and Adult showing how bag capacity controls the tradeoff between AUC width and pure-bag disclosure. With one capacity-256 release, adjacent-rank widths are 2.4 × 10⁻⁴ and 7.1 × 10⁻³, with fewer than 1% of rows in pure bags in both datasets. A two-release test quantifies the effect of repeated probing. We also explain why score-aware grouping preserves interval validity and why the Adult-24 confidence limit is high.

W1/Q1: How does narrower AUC uncertainty trade off against label disclosure?

On Criteo and Adult, adjacent-rank grouping trades narrower AUC intervals for greater pure-bag disclosure. We compare adjacent ranks, round-robin and ten balanced-random partitions using the same rows and count budget at capacities 32, 64, 128 and 256. Each design receives one count vector, allowing evaluation information and disclosure to be measured jointly.

The disclosure measure follows from the released information: a row's binary label is fixed by counts and membership if and only if its bag is pure. In a mixed bag, swapping a positive and a negative preserves all counts. The matched results at capacity 256 are:

Data/designRealised-label AUC widthPure-bag rows
Criteo, adjacent ranks2.4 × 10⁻⁴0.93%
Criteo, random median0.9920.02%
Criteo, round-robin0.9960.05%
Adult, adjacent ranks7.1 × 10⁻³0.99%
Adult, random median0.9930%
Adult, round-robin0.9980%

As the table shows, the large AUC-width gains coincide with greater pure-bag disclosure. Increasing adjacent-rank capacity from 32 to 256 reduces exposure from 41.48% to 0.93% on Criteo and from 14.48% to 0.99% on Adult, at the cost of wider intervals. Bag capacity therefore provides an explicit evaluation–disclosure tradeoff.

A complementary guessing measure shows why determined labels matter. At capacity 256, adjacent ranks give a 4.99 percentage-point advantage over global-majority guessing on Adult. On Criteo, every design stays at the 96.75% global baseline despite differences in determined labels. We also measure the base-2 log-count of compatible joint labelings per row across all capacities.

We also tested repeated probing: a capacity-256 adjacent partition and a second partition shifted by 128 score ranks, with wraparound. Both rules are fixed independently of labels. From their joint counts and memberships, 6.59% of Criteo labels and 2.97% of Adult labels are determined, versus 0.93% and 0.99% after the first release. The sharp AUC widths become 1.19 × 10⁻⁴ and 3.54 × 10⁻³. Both widths and disclosure rates match a single capacity-128 release at the same total count budget. We compute joint extrema exactly from the intersection-cell count constraints. This comparison quantifies how overlapping releases combine information.

W2: Does using model scores compromise evaluation fairness?

Score-aware grouping changes evaluation precision while preserving the target and validity for a fixed scorer. We fix the scorer and design rule before feedback and match rows and count budgets. Scores organize known ranks, while released counts constrain unknown labels. Thus every resulting sharp interval contains the same realised-label AUC.

For the population target, score-aware design also retains coverage under fixed scores/states and conditionally independent Bernoulli labels. The concentration event holds simultaneously across partitions of those fixed rows. To test a practical pre-feedback protocol, we additionally freeze prediction-based and training-state designs before reading evaluation-label-derived probabilities.

Q2: Why is the Adult-24 upper confidence limit in Table 3 unusually high?

The high upper bootstrap limit comes from two of ten blocks attaining 100% width reduction. The median reduction is 88.35%, with a 95% percentile interval of [84.2%, 94.9%]. Specifically, we first compute (risk width − search width)/risk width within each paired block, then take the median. This interval describes variation in width reduction across blocks, whereas the AUC identification interval describes compatible AUC values.

Reviewer_qVmBOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies bag design for evaluating the AUC of a fixed scoring model when only aggregate labels are released. It adopts a partial-identification perspective: after bag means are observed, all response-probability configurations compatible with those means induce a range of possible AUC values, and the goal is to choose the bag assignment before feedback so that this range is as narrow as possible.

For the setting in which every row has its own response probability, the paper derives an affine representation of AUC and an exact decomposition of the sharp interval width into within-bag rank-transport terms. Under distinct scores and equal-capacity bags, adjacent-rank grouping minimizes width at the flat reference world and, when the bag capacity times prevalence is integral, is minimax-optimal over fixed-prevalence response worlds. The paper then considers repeated observable states that share a response probability, where constraints across bags become coupled. It computes exact AUC endpoints through linear programming and uses capacity-preserving swaps to search for width-reducing assignments. Experiments on Criteo, Adult, and UNSW-NB15 support the theoretical predictions and show that evaluation-oriented and training-oriented bag assignments can differ substantially in the presence of repeated states.

Critical strengths
  1. A clear and meaningful formulation of aggregate-label model evaluation. The paper distinguishes bag design for model evaluation from bag design for learning, and casts the former as minimizing the sharp AUC identification interval under aggregate feedback. This provides a clean and practically relevant objective.

  2. Strong theoretical and empirical support. In the separate-row setting, the paper derives exact sharp-width decompositions and proves optimality results for adjacent-rank grouping under stated conditions. In the shared-state setting, the LP formulation and exhaustive small-block experiments clearly demonstrate that evaluation-optimal and training-oriented bag designs can differ.

Critical weaknesses
  1. The main theory is restricted to exact population bag means, whereas practical aggregate labels are often empirical or noisy. The sharp AUC intervals and optimality results are derived for exact population means. The paper does discuss stochastic release channels in Appendix A and explicitly acknowledges that empirical counts, noisy counts, and differentially private releases induce different compatible sets. However, it does not derive corresponding sharp AUC bounds or bag-design guarantees for these practically common feedback mechanisms. This substantially limits the direct applicability of the main theoretical results.

  2. Direct width minimization in the shared-state setting remains difficult to scale. Each candidate assignment requires two LP solves, and global optimality is verified only for 12- and 16-row blocks. At larger scales the method switches to sampled or highly restricted proposal sets; on the full Adult and UNSW-NB15 windows, only 34 structured proposals are evaluated and the reported gains over the risk-based reference are much smaller than on the enriched small blocks. Thus, the paper convincingly establishes the value of the width objective, but provides more limited evidence that it can be effectively optimized at realistic scale.

Questions for authors
  1. Extension to empirical aggregate feedback. Can the framework be extended to a practically important release mechanism such as empirical binary counts or noisy proportions? In particular, can the authors derive useful sharp AUC bounds or a corresponding design objective when the exact-mean constraints no longer apply?

  2. Scalability of shared-state width minimization. The exact pair-swap search requires two LP solves per candidate, while the full-window experiments evaluate only a small structured proposal family. Is there a more scalable optimization method, approximation guarantee, or relaxation that can search a substantially larger portion of the assignment space?

  3. Reference probabilities in realistic deployment. The main shared-state experiments use label-derived reference probabilities, while Appendix D.7 shows encouraging results with predicted, constant, and training-derived references on smaller blocks. Could the authors evaluate such pre-feedback, non-label-derived references in the full-window setting as well? This would clarify whether the large-scale conclusions remain useful when instance-level evaluation labels are unavailable.

2 comments
AuthorsOpenReview ↗

Response to Reviewer qVmB

Thank you for identifying empirical feedback, scalability and pre-feedback references as the key practical questions. We have added sharp realised-label AUC bounds from empirical counts and proved a 95% population confidence bound under conditional independence. In paired simulations on Adult and UNSW, the new population intervals are substantially narrower than the previous per-bag bound. Full-window designs using prediction- and training-based references narrow exact-mean intervals in all 16 original settings. We additionally evaluate 340 distinct partitions in all eight predicted-reference settings.

W1/Q1: Can empirical counts replace exact population bag means?

Empirical binary counts yield sharp realised-label AUC endpoints and a computable 95% confidence outer interval for population AUC. Integer counts always admit the actual binary labels. Applying the bagwise knapsack formula gives the smallest and largest realised AUC compatible with those counts, so its width is directly computable. Repeated states share a response probability, while their realised binary outcomes can differ.

For the population target, our new Bernstein construction substantially narrows uncertainty. At capacity 256, the same 100 label draws per domain give:

DomainPrevious per-bag Hoeffding widthNew Bernstein width, adjacent ranks
Adult0.3280.044
UNSW0.5990.048

As the table shows, the Bernstein envelopes give much tighter population intervals on both domains. Adjacent-rank and predicted-reference search partitions both cover the target in all 100 draws per domain. Under the new envelopes, adjacent ranks give slightly narrower mean intervals, including cases where rounded widths coincide.

The coverage guarantee follows from concentration, independently of this empirical check. With fixed scores/states and conditionally independent Bernoulli outcomes, we prove 95% coverage by controlling prevalence and the rank-weighted sum using only scores and released counts. This includes uncertainty in the AUC denominator, with the valid fallback [0,1] when its interval reaches zero.

Thus empirical counts support sharp realised-label endpoints and a population confidence outer bound. The canonical minimax theorem concerns exact means. For noisy or private proportions, the observation constraints must encode the specified release mechanism.

W2/Q2: Is there a scalable method, approximation guarantee or relaxation?

We evaluate a larger search space at full-window scale and provide a relaxation for fixed-assignment evaluation. Dropping cross-bag state equalities gives the separable, bagwise-knapsack width, an upper bound on coupled width. Assignment search remains heuristic, without an approximation guarantee.

Using the predicted reference, we expanded the original 34-candidate schedule to 340 distinct partitions in all eight domain–capacity settings. Choices are frozen before evaluation in the original exact-mean world. Including exact endpoint LPs, search takes 13.4–17.6 seconds on Adult and 56.3–69.5 seconds on the 524,288-row UNSW window. Relative to adjacent ranks, exact-mean widths shrink by 2.9–6.7% and 0.74–1.04%, respectively. Compared with the original schedule, five settings improve, two tie, and one widens by 0.14%.

Small-block enumeration quantifies how closely search approaches the optimum. The separate 17-start pair-swap procedure attains it in all 20 twelve-row blocks and 12 of 20 sixteen-row blocks. In the other eight, search removes 54.4–70.8% of the score-contiguous reference width, versus 62.0–78.7% for the certified optimum. Thus lower hit counts still retain substantial width reductions.

Retaining cross-bag state equalities also provides measurable gains without changing the partition. At the original search partitions and exact means, they reduce marginal width by 9.3–45.1% on Adult and 70.2–85.8% on UNSW. These are gains from constraint coupling. The additional gains from re-partitioning are reported below.

Q3: Do full-window gains persist with references built before feedback?

Yes. Pre-feedback designs narrow exact-mean AUC intervals in all 16 predicted- and training-reference cells. We use two references × two domains × four capacities, retaining the original Adult and UNSW windows and capacities 32, 64, 128 and 256. Predictions come from a scorer fitted on disjoint training data. Training-state frequencies use training prevalence for unseen states. Each selected partition is frozen before retrospective evaluation.

Under the same 34-candidate budget, these designs narrow exact-mean AUC intervals relative to adjacent ranks by 1.4–4.8% on Adult and 0.3–1.7% on UNSW. The additional eight constant-reference cells show why the reference matters, including an 8.6% worsening on UNSW at capacity 32. Evaluating all 24 frozen designs in the same original evaluation-label-smoothed world isolates the effect of the pre-feedback reference.

Thank you for the detailed response and the additional analyses. The new empirical-count bounds, Bernstein population envelopes, expanded full-window search, and pre-feedback reference experiments address the practical questions I raised.

The remaining limitations are now clearer in scope: assignment search is still heuristic at large scale, and noisy or private release channels remain outside the main theory. These points do not change my overall assessment.

I will also take the other reviewers’ comments into account. I maintain my original score.

Reviewer_tKXfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies bag design for AUC evaluation from aggregate labels. It characterizes AUC identification width, establishes the optimality of score-contiguous grouping under specific conditions, and proposes shared-state optimization for repeated feature states.

Critical strengths

1.The paper introduces a new perspective on bag design, focusing on model evaluation rather than training.

2.The paper derives an exact AUC-width characterization and establishes the optimality of score-contiguous grouping under specific conditions.

Critical weaknesses

1.The method relies on exact population bag means, while practical finite-sample feedback may violate these constraints and make the shared-state optimization infeasible. This limits the applicability of the proposed AUC bounds. Moreover, the full-window experiments use reference probabilities estimated from evaluation labels, which are not available before bag design in practical settings.

2.The substantial improvements from shared-state optimization are mainly observed on small blocks enriched with repeated states. On full-window datasets, the improvements are much smaller despite the computational cost of repeated linear programming. Furthermore, the full-window search evaluates only a limited set of predefined candidate assignments, leaving its optimization effectiveness insufficiently demonstrated.

Questions for authors

1.How can the proposed method handle finite-sample aggregate feedback when the exact-mean constraints become infeasible?

2.Do the full-window improvements persist when reference probabilities are estimated without evaluation labels?

3.How does the frequency of repeated states affect the benefits of shared-state optimization on large datasets, given its additional computational cost?

1 comment
AuthorsOpenReview ↗

Response to Reviewer tKXf

Thank you for identifying finite-sample feasibility and pre-feedback design as the main deployment concerns. We now obtain feasible, sharp realised-label AUC intervals from counts and add a population confidence bound with a proved 95% guarantee under conditional independence. Full-window experiments with prediction- and training-based references reduce exact-mean widths in all 16 settings. We also separate the gains from shared-state constraints from those due to repartitioning and test 340 distinct partitions in eight predicted-reference settings.

W1/Q1: How can finite counts be used when shared-state equalities are infeasible?

Finite counts yield feasible, sharp realised-label AUC intervals and a confidence outer bound for population AUC. The actual binary labels satisfy the released counts, and bagwise knapsack gives sharp AUC endpoints. The key distinction is that sharing an observable state constrains a response probability, while individual outcomes remain binary observations.

Our simulations confirm this distinction: the realised-label formulation remains feasible in all 100 UNSW draws where shared-probability equalities fail. The equalities are feasible in all 100 Adult draws, with both findings holding for adjacent-rank and predicted-reference partitions. The four observed-data count vectors (two domains × two partitions) also satisfy those equalities. The realised-label formulation therefore handles both feasible and infeasible equality cases.

For population AUC, our added Bernstein construction proves 95% coverage and narrows the observed mean intervals. With fixed scores/states and conditionally independent Bernoulli outcomes, it controls prevalence and the rank-weighted sum from scores and counts, including denominator uncertainty and a [0,1] fallback. At capacity 256, adjacent-rank mean widths fall from 0.328 to 0.044 on Adult and from 0.599 to 0.048 on UNSW relative to the previous per-bag Hoeffding bound.

These narrower intervals cover the target in 100/100 draws per domain for both partitions. Adjacent ranks retain slightly narrower average intervals under the new envelopes. The concentration argument supplies the population coverage guarantee, and the paired draws check its implementation. This confidence bound complements the sharp realised-label intervals and the exact-mean minimax theorem by addressing a different target.

W1/Q2: Do full-window gains persist without evaluation labels during design?

Yes. Both predicted and training-state references narrow exact-mean AUC intervals relative to adjacent ranks across two domains and four capacities: 2 × 2 × 4 = 16 cells. We retain the original Adult and UNSW windows and capacities 32, 64, 128 and 256. Predictions use disjoint training data. Training-state frequencies use training prevalence for unseen states. Each partition is fixed before reading evaluation-label-derived probabilities.

With the original 34-candidate budget, these designs narrow exact-mean AUC intervals by 1.4–4.8% on Adult and 0.3–1.7% on UNSW. The additional eight constant-reference cells demonstrate the role of reference choice, including an 8.6% worsening on UNSW at capacity 32. All 24 frozen designs are evaluated in the same retrospective label-smoothed world, isolating how the design reference changes the resulting width.

W2/Q3: How do repeated-state frequency and search cost affect the benefit?

Repeated-state frequency alone does not determine the search gain. The gain depends on how shared states connect bags, their ranks and reference probabilities. State equalities can also narrow intervals without changing the partition. At each original search partition with exact bag means, adding these equalities reduces marginal width by 9.3–45.1% on Adult and 70.2–85.8% on UNSW. In contrast, Covertype has 581,012 distinct states for 581,012 rows, so its coupled problem reduces to the separate-row problem.

Repeated-row proportions are 73.8% on Adult and 97.1% on UNSW. Nevertheless, their pre-feedback search gains over adjacent ranks are 1.4–4.8% and 0.3–1.7%, respectively, as reported above. The fixed-partition comparison separates the information supplied by state sharing from the improvement due to search.

We expanded predicted-reference search to 340 distinct partitions per domain–capacity setting. This takes 13.4–17.6 seconds on Adult and 56.3–69.5 seconds on UNSW. Exact-mean width reductions from adjacent ranks are 2.9–6.7% and 0.74–1.04%. Against the original 34-candidate schedule, five settings improve, two tie, and one widens by 0.14%.

On small blocks, the 17-start procedure reaches the certified minimum in 20/20 twelve-row and 12/20 sixteen-row blocks. Even the other eight remove 54.4–70.8% of the score-contiguous reference width, against 62.0–78.7% for the optimum. This separates gains from state sharing and repartitioning. Exact LPs evaluate each candidate.

Reviewer_AptUOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary
  • Setting: This paper concerns (i) the evaluation of a binary-classification model with logits-like continuous output f:X→Rf: \mathcal{X} \to \mathbb{R}, (ii) with the performance metric, AUC, (iii) under the constraint that we can only get the averaged ground-truth label of each sample-group, i.e., yˉj=(1/∣Bj∣)∑i∈BjPr⁡(yi=1)\bar{y}_j = (1/|B_j|) \sum_{i \in B_j} \Pr(y_i=1), where yi∈0,1y_i \in \\{0,1\\} and BjB_j is the jj-th sample-group with ∣Bj∣|B_j| samples; (iv) nonetheless, we can arbitrarily decide the disjoint sample-group partition Bjj=1m\\{B_j\\}_{j=1}^m of indices of all samples (xi,yi)i=1n\\{(x_i,y_i)\\}_{i=1}^n under some partition budgets.
  • Problem: The problem is (i) to define what a good partition is, (ii) to find the best partition.
  • Results: This paper proposes a criterion, AUC range width, to reflect how good the partition is. The AUC range width measures the gap between the largest and smallest AUC values that are compatible with the averaged labels with respect to the selected partition. Under reasonable assumptions, the paper proves that the partition in the worst case, each group of which contains samples with adjacent model outputs f(xi)f(x_i), is the best partition that minimizes the AUC range width. This paper also extends the aforementioned approach with heuristic algorithmic improvements to tackle practical scenarios for the "shared state" case. Experiments with real-life datasets demonstrate the effectiveness of the approaches.
Critical strengths
  • Interestingness: The problem is interesting and relates to many real-life applications. AUC is a fundamental performance metric in machine learning and beyond, and the "aggregate labels" setting has concrete practical backgrounds. This paper lies at the cross point.
  • Elegance: This paper uses straightforward and clear math to formulate intuitive ideas, including the AUC range width and the "adjacent rank" partition. The "shared state" case and the corresponding linear-programming characterization bring new insights to the problem, including the separation between training-oriented criteria and evaluation-oriented criteria.
Critical weaknesses

None.

Questions for authors
  • Limited impact: This paper focuses on a single stage, evaluating a trained model with the "aggregate labels" constraint. The impact of this paper on the full machine learning pipeline is insufficiently discussed. Particularly, the heuristic algorithmic improvements for the "shared state" case are computationally expensive, but no evidence shows these improvements benefit downstream stages in the full pipeline, such as model selection and hyperparameter tuning. Can the authors explain the significance of this paper beyond evaluating a trained model?
1 comment
AuthorsOpenReview ↗

Response to Reviewer AptU

Thank you for your positive review. We have added a direct comparison of two fixed Adult models. A single aggregate release certifies the network's higher realised-label AUC at each of four capacities, while all 48 original single-score or random releases leave the choice unresolved. This decision uses one sort and bagwise sums, providing a model-selection application without shared-state search.

Q1: Can bag design support model selection beyond evaluating one scorer?

One aggregate release can determine which of two fixed models has higher realised-label AUC. Our added comparison certifies the two-layer network over logistic regression at all four original bag capacities on the same 25,856 Adult rows.

To target this decision directly, we subtract the two affine AUC expressions and obtain a coefficient difference for each row. Sorting these differences and forming consecutive bags groups rows according to their effect on the model comparison. We freeze this design before reading labels and keep models, rows and count budgets fixed. Each design uses one count vector, independently of the other releases.

The bagwise knapsack calculation then gives exact difference endpoints attained by compatible labelings. The logistic-minus-network intervals are shown in AUC percentage points (1 point = 0.01 AUC):

Bag capacityAUC-difference interval (percentage points)
32[−1.88, −1.73]
64[−1.95, −1.66]
128[−2.08, −1.53]
256[−2.33, −1.29]

As the table shows, every interval lies below zero, so every compatible labeling ranks the network above logistic regression. The two AUCs are 0.830 and 0.848. Lower endpoints are rounded down and upper endpoints up to two decimals, preserving the comparison even after rounding.

This comparison-directed release resolves a choice that all 48 original single-score or random releases leave unidentified, because their AUC-difference intervals contain zero. Its individual AUC widths increase to approximately 0.645–0.832. Thus designing for the difference can support model selection more directly than estimating either AUC separately.

The result also connects selection to disclosure: at capacities 128 and 256, the model choice is certified with zero pure bags. In these releases, counts and membership do not determine individual labels through pure bags.

Q2: Does this downstream benefit require expensive shared-state search?

No. The demonstrated fixed-pair decision requires one sort of coefficient differences followed by bagwise sums. It applies the separate-row formulation to a comparison objective, using one release for the fixed pair. This is a concrete model-selection use of the width framework with a low-cost design rule.

Shared-state constraints make a complementary contribution to evaluating a fixed scorer. Under exact bag means and at the original search partitions, adding state equalities narrows single-model intervals by 9.3–45.1% on Adult and 70.2–85.8% on UNSW. Training-risk and AUC-width minimizers are also disjoint in all 40 enumerated blocks. These findings explain why an evaluation-oriented objective matters, while the fixed-pair construction above demonstrates its use in selecting between models.

Reviewer_3gQzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper investigates the bag design problem when evaluating the models’ AUC with grouped results. It mainly focuses on theory and provides a comprehensive theoretical analysis regarding rank transportation, flat-world and canonical minmax optimality and more. Extensive experiments across multiple settings prove that adjacent ranks can retain more AUC information, and that different approaches should be applied for better AUC evaluation.

Critical strengths
  1. This paper develops a comprehensive theoretical framework along with corresponding experiments. Starting from the definitions of the responses and the grouping, the theoretical analysis simplifies the pairwise AUC to a constant plus a weighted sum of response probabilities, then it uses continuous-knapsack to obtain the AUC width, the score-contiguous assignment strategy’s optimality is proved afterwards. This paper also discusses the scenario of a shared probability on repeated observable states. Experiments provide empirical ground for the proposed theory, highlighting its correctness.
  2. This paper provides a good point in selecting bags to evaluate AUC. Under two assumptions, the paper gives different optimal strategy of selecting bags, instead of using a one-fits-all method. This shed a light on designing a proper strategy based on the characteristics of models’ outputs. More researches can be carried out for selecting bags for different models across varying domains.
Critical weaknesses
  1. The paper provides few new methods or algorithms. As states in the Strengths section, there does not exist a one-fits-all method. The adjacent-rank strategy was proposed in 2025 according to the related works. The width-directed search method seems promising on the twelve rows per block setting but hit counts drop on the sixteen rows per block setting.
  2. This paper is ill-formatted with figures, tables and text hard to understand. The caption of Figure 4 states that there are two panels, namely (a) and (b), but it is not implemented in the figure. The right figure in Figure 4 is not properly zoomed and the lines cannot be seen clearly. Panel (a) of Figure 5 has colliding objects. The risk width column in Table 5 has different forms, confusing readers. There are too many digits in Table 6, inconsistent with other tables. Moreover, there are no signs of Q.E.D. after each proof. The second-level title has wrong format. At the end of the appendix, there is an extended related work section which does not possess a clear goal. Line 392 contains a confusing statement of not ratios of median widths.
Questions for authors
  1. If this paper is fully written by authors without AI assistance, how will you organize your analysis and experiments to present your idea? Can the proposed conclusion be applicable to different models across different domains?
  2. Could you please state the intention of Appendix F and explain why there are so many repeated references?
1 comment
AuthorsOpenReview ↗

Response to Reviewer 3gQz

Thank you for your comments. We have clarified the argument from the AUC-width formula to its design consequences, corrected the figures and tables, and removed duplicated discussion from Appendix F. We also quantify the sixteen-row search gaps: even when the heuristic misses the optimum, it reduces width by 54.4–70.8%. Our contribution is the AUC evaluation guarantees and the separation from training-oriented bag design.

W1: What is new beyond adjacent-rank grouping, and what do lower search hits mean?

Our contribution is the exact AUC-width characterization and the separation between training-oriented and evaluation-oriented bag design. Lower hit counts reflect missed optima in a heuristic search, with substantial width reductions retained. The adjacent-rank rule also appears in Agarwal et al. (2025), “Aggregating Data for Optimal Learning,” and the PriorBoost partitioning step. We establish what this rule guarantees for AUC evaluation: a width decomposition for arbitrary partitions, flat-world optimality and canonical minimax optimality under distinct scores, equal capacities and integer capacity-times-prevalence. For shared states, complete enumeration finds disjoint training-risk and AUC-width minimizer sets in all 40 small blocks.

The 17-start pair-swap procedure reaches the certified minimum in all 20 twelve-row blocks and 12 of 20 sixteen-row blocks. In the other eight, it removes 54.4–70.8% of the score-contiguous reference width, compared with 62.0–78.7% for the optimum. Endpoint LPs evaluate each candidate exactly. The full-window procedure examines 34 structured candidates. Separately, at unchanged original search partitions and exact means, shared equalities narrow marginal widths by 9.3–45.1% on Adult and 70.2–85.8% on UNSW, demonstrating information gains from state coupling itself.

W2: How have the figures, tables, proofs and unclear wording been clarified?

We have revised the presentation to make the figures readable and the notation consistent. Your specific points are addressed as follows:

  • Figure 4 has explicit (a)/(b) titles. Its right panel uses a zoomed vertical scale, with both curves visible and the legend outside the data.
  • Figure 5 places the median annotation above the bars. A separate trajectory panel (c) resolves the overlap with calibration points.
  • Table 5 uses scientific notation for both width columns. Table 6 uses three decimals consistently for its three width columns.
  • Proofs have end-of-proof markers, and second-level headings use the conference template's subsection format.
  • The calculation at line 392 is now stated directly: compute each block's paired relative reduction, then take the median across blocks. This explains how the reported statistic is formed.
  • Appendix F now states its purpose and removes duplicated discussion, as explained below.

Q1: How should the argument be organized, and does it transfer across models and domains?

We organize the exposition from evaluation uncertainty to a design rule. The rank formula transfers across scoring models, while optimality uses the conditions in W1. First, we define the AUC target and compatible response worlds. The rank-weighted representation then yields the width formula and its design consequences. Next, repeated states explain why cross-bag constraints can change the best design. The experiments follow this argument through assignment comparisons, mechanism controls, certified objective separation and larger-window search. Each experiment therefore answers a specific mathematical question.

The separate-row rank formula also permits tied scores. Experiments on Criteo, Adult and UNSW test the design consequences across domains. The Adult nonlinear-scorer comparison retains the adjacent-rank/random/round-robin ordering. Covertype has no repeated states, so its coupled problem reduces to the separate-row case. The evidence thus links model-independent rank formulas to their conditional design guarantees and observed behavior.

Q2: What does Appendix F add, and why are references repeated?

Appendix F explains why learning-oriented and AUC-evaluation bag criteria solve different problems. It separates learning from fixed aggregates, designing bags for training, evaluating a fixed model without individual labels, and designing bags for AUC identification. The main related-work discussion places our contribution. Appendix F develops the differing assumptions and targets, including the cross-bag constraints induced by shared states.

To make these roles distinct, we removed duplicated introductory, modern-method and LLP-theory paragraphs. Citations that remain in both places support different comparisons: the main text establishes the research context, while Appendix F explains the mathematical differences between tasks.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.