acceptodds
Under review as a conference paper at ICLR 2027

Decision-sufficient predictive representations for symmetric fixed-cardinality losses

Abstract

What information about uncertainty must a predictor expose to support optimal decisions? We answer this question for symmetric fixed-cardinality overlap losses, where decisions and outcomes are fixed-size subsets and the loss depends only on their overlap. Using the Johnson decomposition, we derive coefficients directly from the scalar loss profile to identify the active interaction layers, without constructing the full loss matrix. Projection onto these layers preserves every expected-loss comparison. Conversely, every nonzero direction in the active subspace yields two feasible outcome distributions with no common optimal decision. These results establish the minimum affine-linear interface dimension required to support optimal decisions for every outcome distribution. Applying existing convex-calibration bounds gives the same exact dimension, attained by a standard squared embedding with an explicit regret transfer bound. Required interaction orders need not form a prefix: a threshold loss can require third-order information while ignoring the second-order layer. Synthetic experiments and frozen-predictor ablations on a candidate-conditioned WikiSeeAlso task show that retaining active higher-order information can improve decisions, with its value shaped by sample size, estimation accuracy, and decision margins. Matched training-objective comparisons distinguish the information required for decision-making from the choice of estimator used to learn it.

Primary area:
learning theory
Keywords:
Decision-sufficient representations, Structured prediction, Convex calibration dimension, Predict-then-optimize, Loss embeddings

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_NbBAOpenReview ↗
Rating
3
Confidence
1(−1)
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies what minimum uncertainty information a predictor needs to retain for optimal decision-making. Using a mathematical decomposition, it identifies the necessary information components and their minimum dimension.

The theoretical and experimental results show that predicting only the information relevant to the loss function, rather than the full probability distribution, is sufficient for optimal decisions. The paper also examines how missing information, estimation errors, and decoding errors affect decision performance.

Critical strengths
  1. The theoretical analysis is solid. The non-prefix result is particularly interesting and somewhat novel. It challenges the common intuition that higher-order information necessarily includes lower-order information. For example, some loss functions require third-order information but do not need any second-order Johnson components.

  2. The experimental results are consistent with the theoretical findings.

Critical weaknesses
  1. Constructing the decision-relevant subspace from differences between loss vectors is a fairly standard idea.

  2. As the authors acknowledge, the number of correct labels or relevant documents is often not fixed in real-world multi-label classification, recommendation, and retrieval tasks. However, the theoretical results rely on fixed set cardinalities and symmetric overlap losses, which limits their applicability.

  3. The experiments are relatively small in scale, making it difficult to assess the practical value of the proposed approach in real-world applications.

Questions for authors
  1. I would like the authors to clarify how this work relates to existing research, particularly which theoretical tools and ideas are already established and which key results are genuinely new and cannot be directly derived from prior work. Also, since the analysis assumes fixed set cardinalities and symmetric overlap losses, it would be helpful to discuss how much these assumptions limit the applicability of the method to real-world tasks.

2.Although the paper includes experiments using real Wikipedia data, the candidate sets and decision spaces are still relatively small. Could the authors provide larger-scale retrieval experiments with an open candidate space to better demonstrate the scalability and practical value of the proposed approach?

5 comments
AuthorsOpenReview ↗

To Reviewer NbBA (1/2)

W1/Q1. The loss-specific characterization and its contribution.

We agree that constructing the decision-relevant subspace from differences between loss vectors is a standard idea. Johnson decompositions are classical spectral-analysis tools, while Bennouna et al. [1] and Ye et al. [2] provide general geometric criteria for sufficient measurement. Our contribution, however, is to derive an exact rule connecting the loss profile to the information required for optimal decisions. To the best of our knowledge, our work provides the first explicit, closed-form characterization of decision-sufficient representations for symmetric fixed-cardinality overlap losses, with the following results:

  • Closed-form characterization and non-prefix structure. Directly from the scalar loss profile, we identify which interaction orders affect decisions, which can be omitted, and their decision-score weights, without constructing the full loss matrix. The required layers need not form a prefix. At n=6,m=K=3n=6,m=K=3, threshold utility u(q)=1q≥2u(q)=\mathbf{1}\\{q\ge2\\} requires the 10-dimensional V1⊕V3V_1\oplus V_3, while the larger 14-dimensional V1⊕V2V_1\oplus V_2 is insufficient. This gives a concrete principle for representation design: retain the components selected by the loss.

  • Sufficiency, necessity, and minimum dimension. Retaining the active components preserves all expected-loss comparisons and hence Bayes-optimal decisions for every outcome distribution. For every nonzero active direction, we construct two distributions that become indistinguishable when that direction is removed, although they have no common optimal decision. Together, these results establish the exact minimum dimension of a universally sufficient affine-linear representation.

  • Empirical validation. Synthetic experiments validate the predicted loss-specific information requirements and show when learning higher-order information improves decisions. WikiSeeAlso experiments demonstrate substantial training and inference savings from directly estimating the sufficient representation and quantify the associated decision-quality tradeoff.

References

[1] Bennouna, Omar, et al. "What data enables optimal decisions? An exact characterization for linear optimization." Advances in Neural Information Processing Systems 38 (2026): 166020–166049.

[2] Ye, Yuhan, Saurabh Amin, and Asuman Ozdaglar. "Learning Decision-Sufficient Representations for Linear Optimization." arXiv preprint arXiv:2603.18551 (2026).

W2/Q1. How restrictive are fixed cardinalities and symmetry?

Thank you for highlighting this important limitation. Your valuable comment motivated us to revisit the fixed-cardinality assumption and develop a new theoretical extension for variable cardinality outcomes. For a fixed decision budget and symmetric overlap losses, the new analysis allows arbitrary conditional distributions over outcome subsets, without requiring outcome cardinality to be known or predicted at inference time. We construct observable training targets whose conditional means preserve optimal decision comparisons, establish the exact minimum universally sufficient affine-linear dimension, and derive a decision-regret bound linking estimation error to decision quality. The new result appears in Section 5, with its full derivation and training construction in Appendix G.1.

In detail, for a fixed decision budget 1≤K<n1\le K < n and arbitrary E⊆[n]E\subseteq[n], write u(q)=∑s=0Kαs(qs)u(q)=\sum_{s=0}^{K}\alpha_s\binom{q}{s}. Then

E[u(∣S∩E∣)∣x]=α0+∑s=1Kαs∑A⊆S,,∣A∣=sPr⁡(A⊆E∣x).\displaystyle \mathbb{E}[u(\lvert S\cap E\rvert)\mid x]=\alpha_0+\sum_{s=1}^{K}\alpha_s\sum_{A\subseteq S,\\,\lvert A\rvert=s}\Pr(A\subseteq E\mid x).

The required probabilities can be learned from observed subset-inclusion indicators without knowing ∣E∣\lvert E\rvert at prediction time. If rr is the highest nonzero order and d=min⁡(r,K,n−K)d=\min(r,K,n-K), the minimum universally sufficient affine-linear dimension over the full powerset is (nd)−1\binom{n}{d}-1. Constant utility requires zero coordinates. The appendix gives observable regression targets attaining this dimension and a decision-regret bound.

Fixed outcome cardinality can enable further compression, while sufficient representations remain available when cardinality is unknown. For threshold utility u(q)=1q≥2u(q)=\mathbf{1}\\{q\ge2\\} at n=6,K=3n=6,K=3, the minimum dimension is 10 on the m=3m=3 slice and 19 over arbitrary outcome sizes.

Regarding symmetry, we would like to clarify that the assumption concerns the loss function. Selecting the same number of relevant items gives the same utility, regardless of which items are selected. This does not mean that all items are equally likely to be relevant or that their relevance is independent. Items may have different relevance probabilities and arbitrary dependencies. We have added this explanation of symmetry to the revised paper.

AuthorsOpenReview ↗

To Reviewer NbBA (2/2)

W3/Q2. Computational benefits at larger candidate scales.

Thank you for your valuable comment. Our added WikiSeeAlso experiments show substantial computational savings at larger candidate scales (Section 6.3 and Appendix I.1). With 128 candidate labels, directly predicting pair scores (minimum representation) achieves 26.594× faster complete fitting and 34.178× faster inference than Full CE. Mean success is 16.835% versus 17.245%, with a paired difference of −0.410% (95% CI [−1.243%, 0.389%]). These results quantify the computational benefit and the accompanying decision-quality tradeoff.

We evaluate candidate sets of 32, 64, and 128 labels. For each article, a retrieval model fitted using only training data selects the highest-ranked candidate labels from the label pool available in training. At 128 candidates, the evaluation cohort contains 27,155 training articles and 9,605 test articles. Each example has three relevant labels, and the task is to select two labels that are both relevant. Our method predicts a success score for each candidate pair, whereas Full CE predicts the probability of each possible triple of relevant labels. At 128 candidates, this means 8,128 pair scores instead of 341,376 triple probabilities. Both models use the same 61,953-parameter scoring architecture.

Both methods use five paired seeds, 100 training epochs, and checkpoints selected on validation data. Success below is reported as mean ± standard deviation across seeds. Speedups are Full CE time divided by direct-prediction time. Complete fitting includes all 100 epochs, validation, and checkpointing. Inference is measured on 512 articles and includes batching cached features, prediction, score export, and exact decoding.

Candidate labelsDirect pair prediction successFull CE successComplete-fit speedupInference speedup
3230.478% ± 0.807%31.036% ± 0.859%2.663×3.034×
6422.530% ± 0.514%22.878% ± 0.877%8.541×16.946×
12816.835% ± 0.167%17.245% ± 0.804%26.594×34.178×

We appreciate your thoughtful questions and would be happy to clarify any remaining points about our work.

AuthorsOpenReview ↗

Kind Follow-up on Our Rebuttal Submission

Dear Reviewer NbBA,

We hope you are doing well. We would like to follow up on our rebuttal, which addresses your questions about the contribution, assumptions, and experimental scale.

We are particularly grateful for your comment on the fixed outcome cardinality assumption. It motivated us to develop a new theoretical extension to variable outcome cardinality, leading to additional sufficiency and minimum-dimension results that broaden the scope of our theory.

Our responses and revisions include:

  • A clearer contribution: We distinguish established tools from our new results, which identify the information needed for optimal decisions and its minimum dimension.

  • Broader theoretical scope: Following your suggestion, we extended the theory to variable outcome sizes under a fixed decision budget. The extension provides sufficient prediction targets and their exact minimum dimension. We also clarify that symmetry applies to the loss.

  • Larger-scale experiments: We added WikiSeeAlso comparisons with 32, 64, and 128 candidates, showing the training and inference savings alongside the difference in decision accuracy.

If you have a moment, we would be grateful if you could review our responses and let us know whether any questions remain about the theoretical extension or the additional experiments.

We sincerely appreciate the time and care you have devoted to reviewing our work, and thank you for the suggestion that helped us strengthen its theoretical scope.

Warm regards,
The Authors

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

The paper analyses predictors that, given a set of n elements, output the subset of K elements that should minimize a certain loss. The considered losses depend on the cardinality of the intersection between the predicted subset of K elements and the outcome subset of m elements. The authors theoretically derive the representation space Z that guarantees the existence of a predictor that maps Z to predictions that minimize the loss for each probability distribution of the possible outcomes. They characterise Z with Johnson decomposition.

The theoretical results seem valid and interesting. However, I find the paper very hard to follow, in both the theoretical and experimental parts. Most importantly, I think that the practical significance of the contribution is not demonstrated.

Critical strengths

S1. Theoretical contributions seem correct and relevant.

S2. The theoretical approach is valuable and clever

Critical weaknesses

W1. The presentation is poor. The paper is very dense with mathematical details without proper introduction, explanation or interpretation. In my opinion, the paper is very hard to follow for someone who is not an expert in the mathematical tools employed. Some examples of these problems:

  • Theorem 2 is introduced but no clear interpretation is provided. Why this theorem implies all active layers must be retained should be explained more clearly.
  • Notation is often not explained, and must be inferred. In section 3.1, V^(m), V^(K) belong to two different spaces. P_{X} should indicate a projection on X, but this is not clarified (e.g. eq. 5). The purpose of some sections is not always clear. Section 5 is a collection of results whose implications are not practically connected to the learning problem.

W2. The experimental part is also very difficult to follow. The experiments are poorly described, as the results. Some plots (Figure 3, 4, and 5) are described in short paragraphs of 3-4 lines, not sufficient to fully explain the results obtained. Most importantly, I think that neither the text nor the experiments convincingly demonstrated the advantages of this theoretically optimal representation.

Minor: table 1 lacks references.

Questions for authors

N/A

2 comments
AuthorsOpenReview ↗

To Reviewer wZ8S

W1. Clarifying the theory and its connection to learning.

Thank you for these constructive suggestions, which helped us improve the clarity and organization of the paper. We have added brief motivations and interpretations around the main theoretical results and made their connection to the learning procedure more explicit.

  • Clarifying the notation and spaces. Sections 3.1 now explain that choosing the best action requires comparing expected losses across actions. For each interaction order, the spectral coefficient tells us whether that order contributes to these comparisons: a zero coefficient means it has no effect on the choice of action. We define PXP_X as orthogonal projection and distinguish outcome-distribution components Vj(m)V_j^{(m)} from decision-score components Vj(K)V_j^{(K)}. The example n=10,m=3,K=5n=10,m=3,K=5 illustrates the two spaces with 120 outcome coordinates and 252 decision scores.

  • Explaining Theorem 2. Section 4.2 now introduces the necessity question after establishing sufficiency: can any active information be removed while retaining optimal decisions for every distribution? We explain that deleting an active direction makes two distributions indistinguishable although they have no common optimal decision. A decoder receiving the same information cannot be optimal for both.

  • Connecting Section 5 to training. Section 5 now describes the learning procedure step by step: convert each observed outcome into a target vector tailored to the decision loss, train a model to predict that vector, and use the prediction to choose an action. The two dimension results address different questions. The first asks how many coordinates are needed to preserve optimal decisions. The second asks how many prediction outputs are required for calibrated learning, where approaching the best possible surrogate loss also leads to optimal decision performance. We then connect prediction error to decision quality. Excess squared loss measures how accurately the model predicts the target vector's conditional mean. When two actions have nearly equal expected utilities, a small prediction error can reverse their ranking and change the chosen action.

W2. Reorganizing the experiments around three questions.

Thank you for your suggestion. We have reorganized Section 6 around three questions and expanded the explanations of the experimental design and results. The main text now identifies the information required by each loss, explains when learning it improves decisions, and measures the computational benefit of estimating it directly.

  • Which information does each loss require? (Section 6.1) Figure 2 holds the outcome distributions fixed and changes only the downstream utility. Without fitting a predictor, it shows that the sufficient layers change from V1V_1 for additive utility to V1⊕V2V_1\oplus V_2 for pair reward and V1⊕V3V_1\oplus V_3 for threshold utility.

  • When does learning active information improve decisions? (Section 6.2) Table 3 separates the theoretical gain ceiling from the gain recovered through learning. With strong association and weak item preference, active prediction reaches the 5.625% ceiling over the best fixed decision at 5,000 samples. When the same decision is optimal in both contexts, the ceiling is zero. Estimation error reduces success by 2.137% at 250 samples, and this deficit shrinks to 0.056% at 5,000 samples. Figure 3 then shows why continued reduction in training loss need not improve decision quality, motivating validation-based checkpoint selection.

  • What computational gains does direct estimation provide on real data? (Section 6.3) Under both-hit utility, a prediction succeeds only if both selected labels are relevant. Our model directly predicts this success probability for each label pair. Each training example provides three relevant labels: the three pairs formed from these labels are positive training targets, and all other pairs are negative. Full CE instead predicts the probability of every possible triple of relevant labels. With 128 candidate labels, our model predicts 8,128 pair scores, whereas Full CE predicts 341,376 triple probabilities. Both models have 61,953 trainable parameters: each reuses its scoring network across all pairs or triples. The difference is how many pairs or triples must be scored. In this experiment, direct pair prediction gives 26.594× faster fitting and 34.178× faster inference. Across five paired seeds, direct pair prediction achieves 16.835% success, compared with 17.245% for Full CE. The paired difference is −0.410% (95% CI [−1.243%, 0.389%]). Thus, the experiment demonstrates substantial computational savings.

  • Minor: References in Table 1. We have added author–year citations to the related-work entries in Table 1, with full references in the bibliography.

We appreciate your suggestions and would be happy to clarify any remaining questions.

AuthorsOpenReview ↗

Kind Follow-up on Our Rebuttal Submission

Dear Reviewer wZ8S,

We hope you are doing well. We would like to follow up on our rebuttal and the revisions motivated by your suggestions, including:

  • Clearer theory: We explain the notation, the meaning of Theorem 2, and how the theoretical results guide model training.

  • Clearer experiments: We reorganized the experiments around three questions: what information is needed, when learning it helps, and how much computation direct prediction saves.

  • Complete references: We added the missing citations in Table 1 and the corresponding bibliography entries.

If you have a moment, we would be grateful if you could review our responses and let us know whether the revised explanations address your concerns or whether any points still need clarification.

We sincerely appreciate your thoughtful suggestions, which have helped us improve the clarity and organization of the paper.

Warm regards,
The Authors

Reviewer_rW5tOpenReview ↗
Rating
4(+1)
Confidence
2(+1)
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper characterizes the predictive information needed for Bayes-optimal decisions under symmetric fixed-cardinality overlap losses. It computes active Johnson layers directly from the scalar loss profile, proves that projection onto their span preserves all expected-loss comparisons, and constructs distribution pairs establishing direction-wise necessity. This yields the minimum universally sufficient affine-linear interface dimension. Applying existing convex-calibration bounds gives the same dimension, attained by a squared embedding. Complement symmetry explains non-prefix active supports. Synthetic studies and a controlled candidate-conditioned Wikipedia task distinguish population sufficiency, estimation error, and the decision value of additional layers.

Critical strengths
  1. The loss-specific characterization is precise and interpretable. The coefficient formula and Theorems 1–2 connect classical Johnson decomposition to both sufficient information and a necessity witness for every active direction (pp.4–5; Appendices B–D). The threshold example requiring V1 and V3 but not V2 makes clear why retaining more coordinates or a longer prefix need not retain the right information. Appendix F also checks the conditions needed to obtain the exact calibration dimension from existing bounds.

  2. The experiments carefully separate information from estimation. Frozen-predictor projections isolate the value of retained layers, while matched training comparisons show that directly learning the sufficient target need not be best. The paper reports unfavorable results and decoder sensitivity rather than conflating population sufficiency with finite-sample superiority (Tables 6, 13–16, 18–21).

Critical weaknesses
  1. The practical reach of the characterization remains limited. The principal real-data result uses a constructed six-candidate, exactly-three-positive task and improves threshold success by 0.276 percentage points (pp.9,25,28). All primary selected models are full CE predictors; the exported interface is smaller, but the networks retain 20 outputs and 6,305 parameters (p.28). Thus the evidence establishes a useful interface identity more clearly than an end-to-end computational or statistical advantage from learning the minimal representation.

  2. The learning conclusions are sensitive to estimator, endpoint, and decoder. The controlled-posterior information gain can be very small, the supplementary Top-3 endpoint loses significance after adjustment, and the fixed Interaction128 comparison is strongly affected by near ties (pp.21,29,31). These findings do not invalidate the structural theorems, but restrict the broader practical significance of the proposed workflow.

Questions for authors
  1. Beyond computing active support, what are the concrete costs of constructing/exporting coordinates and decoding at larger n? Can the practical benefit be demonstrated in a setting where full outcome prediction is infeasible, while keeping the comparison focused on the existing claims?
  2. How should a practitioner decide between direct active estimation and full CE followed by projection, given the negative direct-training and endpoint results? Which conclusions are intended to generalize beyond the candidate-conditioned Wiki task?
5 comments
AuthorsOpenReview ↗

To Reviewer rW5t (1/2)

W1. Practical value beyond an interface identity.

You are correct that the original result should be complemented by evidence of computational benefits from direct learning. We have added a new WikiSeeAlso experiment that directly trains the loss-specific minimal representation. At n=128n=128, this gives 26.594× faster fitting and 34.178× faster inference, with an observed success-rate difference of −0.410% (minimal representation minus Full CE).

WikiSeeAlso experiment (m=3,K=2m=3,K=2). Both methods use five paired training seeds, 100 epochs, validation-selected checkpoints, and the same number of trainable parameters. The n=32,64,128n=32,64,128 cohorts contain 4,768, 6,942, and 9,605 test articles. Minimal representation denotes direct pair CE, which directly estimates pair-inclusion probabilities, while Full CE predicts the complete outcome distribution. Paired entries below are minimal representation / Full CE. Success is mean ± SD across seeds; speedups are Full CE time divided by minimal representation time.

nnInterface dimensionSuccess (%)Complete-fit speedupInference speedup
32495 / 4,95930.478 ± 0.807 / 31.036 ± 0.8592.663×3.034×
642,015 / 41,66322.530 ± 0.514 / 22.878 ± 0.8778.541×16.946×
1288,127 / 341,37516.835 ± 0.167 / 17.245 ± 0.80426.594×34.178×

Both models share a scoring network but evaluate different numbers of pairs or triples. Fit time covers 100 epochs, including validation and checkpointing. Inference includes cached-feature batching, prediction, score export, and exact decoding for 512 articles. Retrieval and initial feature construction are separate common costs.

W2. Estimator, endpoint, and decoder sensitivity.

We agree that the practical significance of the characterization depends on when the required information can improve learned decisions. We therefore add a new controlled learning experiment that varies higher-order association, fixed item preference, and sample size. The results identify two conditions for realizing a benefit: higher-order information must change the optimal action, and it must be estimated accurately enough to recover that change.

The experiment uses n=6,m=K=3n=6,m=K=3 and threshold utility 1∣S∩e∣≥2\mathbf{1}\\{\lvert S\cap e\rvert\ge2\\}. We train the active representation V1⊕V3V_1\oplus V_3 from sampled outcomes using ordinary least squares and exact decoding. We vary association strength α\alpha, fixed item preference β\beta, and sample size, using 20 paired training-sample seeds per condition.

The exact first- and second-order information is identical in the two contexts, so a decoder using only this information cannot adapt its decision to the context. The best fixed decision is the single three-item set that maximizes average threshold success across the two contexts, computed from the known outcome distributions. This comparison examines when adapting decisions to context is beneficial and how much of that benefit can be learned from finite samples. The theoretical gain ceiling is the maximum possible improvement over the same fixed-decision reference.

Learned active − best fixed decision (%)

Entries are differences between the two success rates, expressed as percentages.

Association α\alphaFixed preference β\betaN=250N=250N=1,000N=1{,}000N=5,000N=5{,}000Theoretical gain ceiling
0.10.05−0.928+0.169+1.0691.125
0.10.2−2.137−0.675−0.0560
0.30.05+4.022+5.400+5.6255.625
0.30.2+1.856+2.194+2.2502.250
  • Higher-order information helps when it changes the optimal decision. When association is too weak to overcome fixed item preference, the same decision remains optimal across contexts and the theoretical gain ceiling is zero. Estimation error can then reduce success. Active prediction falls below the best fixed decision by 2.137% at 250 samples and 0.056% at 5,000 samples. Negative gains mean that the fitted policy has not yet matched this reference.

  • Sufficient data are needed to realize the information advantage. Under weak association and preference, the gain rises from −0.928% to +1.069%, approaching the 1.125% theoretical ceiling. Strong association and weak preference yield the 5.625% ceiling at 5,000 samples.

AuthorsOpenReview ↗

To Reviewer rW5t (2/2)

Q1. Constructing and using the representation at larger scales.

1. What are the construction, export, and decoding costs?

With the basis and action vectors precomputed and outcomes indexed, reading or exporting a DD-coordinate vector costs O(D)O(D), and exhaustive exact decoding costs O(MD)O(MD). Here N=(nm)N=\binom{n}{m}, M=(nK)M=\binom{n}{K}, and D=DLD=D_L. Dense projection of a full prediction costs O(ND)O(ND).

The explicit basis and action vectors require O(ND+MD)O(ND+MD) storage. Their construction is additional preprocessing. Network evaluation is also separate. Our result gives the smallest affine-linear representation that preserves optimal decisions. Whether it saves computation depends on the cost of building and storing it, and of finding the best action.

2. Can the benefit be demonstrated where full outcome prediction is infeasible?

Our experiments demonstrate substantial computational savings in a setting where full outcome prediction is costly but still feasible. They address the practical cost concern, although they do not establish a scale at which full prediction exceeds an operational resource budget.

For example, the WikiSeeAlso setting from W1 provides a concrete implementation in which construction, export, and decoding are all quadratic in the number of candidates. Here m=3m=3, K=2K=2, and the utility is both-hit. The required information is represented by pair-inclusion probabilities,

qij(x)=Pr⁡(i,j⊆E∣x),∑i<jqij(x)=3.\displaystyle q_{ij}(x)=\Pr(\\{i,j\\}\subseteq E\mid x),\qquad \sum_{i < j}q_{ij}(x)=3.

Each observed triple supplies three positive pair indicators. We train directly on these indicators normalized by three and rescale the predictions to obtain pair-inclusion scores. This avoids full-outcome prediction and construction of an outcome-space Johnson basis. Dense target construction and coordinate export require O(n2)O(n^2) work. Exact decoding selects the pair with the largest predicted inclusion score, also in O(n2)O(n^2) time. The representation has (n2)−1\binom{n}{2}-1 independent coordinates, implemented using (n2)\binom{n}{2} pair scores, compared with (n3)\binom{n}{3} probabilities for explicit full prediction.

At n=128n=128, this gives 8,128 pair scores representing 8,127 independent coordinates, compared with 341,376 full-outcome probabilities. With equal trainable parameter counts, direct pair prediction achieves 26.594× faster complete fitting and 34.178× faster inference. Inference includes forward computation, score export, and exact decoding. Success is 16.835% versus 17.245% for Full CE. The paired difference is −0.410% [−1.243%, +0.389%], with the full quality comparison reported in W1.

Q2. Estimator choice and generalization.

  • Choosing the estimator. Compare the two estimators using decision performance on validation data and computational cost. Use direct estimation if it meets the required decision quality at lower cost. Use Full CE followed by projection if its validation gain justifies the extra cost. The loss determines what information to predict, but a minimal representation does not guarantee better learned decisions, as the negative direct-training and endpoint results show. In Wiki, validation success selects each method's learning rate and checkpoint before testing. Projection preserves the full predictor's decision-relevant information.

  • What generalizes. The theoretical characterization applies to symmetric fixed-cardinality overlap losses beyond Wiki: it identifies the information needed to preserve optimal decisions and guides the choice of prediction targets and representations. Our controlled experiment illustrates when learning this information helps: it must change the optimal action and be learned accurately enough. The Wiki experiments quantify the quality–cost tradeoff for that task. The preferred estimator and the size of its benefit remain task-dependent.

We sincerely appreciate your thoughtful questions, which have helped us clarify the practical implications of our results and improve the paper. We would be happy to provide any further clarification.

AuthorsOpenReview ↗

Kind Follow-up on Our Rebuttal Submission

Dear Reviewer rW5t,

We hope you are doing well. We would like to follow up on our rebuttal, which provides responses to your questions and concerns, including:

  • Computational benefits: We added WikiSeeAlso experiments with 32, 64, and 128 candidates, comparing decision accuracy, training time, and inference time.

  • When higher-order information helps: We show that it must change the best decision, and that enough data are needed to learn it accurately.

  • Practical guidance: We explain the costs of constructing and decoding the representation, and how validation performance and computational cost guide predictor selection.

If you have a moment, we would be grateful if you could review our responses and let us know whether any concerns remain or require further clarification.

We sincerely appreciate the time and effort you have invested in reviewing our work, and thank you for considering our responses.

Warm regards,
The Authors

Comments on the paper

3 comments
AuthorsOpenReview ↗

Gentle Follow-up on Our Rebuttal Submission

Dear Reviewers rW5t, wZ8S, and NbBA,

As the discussion period draws to a close, we want to thank you for the time you’ve spent on our paper. We’ve posted our responses to each review, and we appreciate Reviewer rW5t’s follow-up on the new experiments.

If you have any remaining questions about the revised paper, we’d be happy to discuss them. Thank you again for your valuable time and consideration.

Best regards,
The Authors

AuthorsOpenReview ↗

Response Summary and Updated Manuscript to All Reviewers

Dear Reviewers rW5t, wZ8S, and NbBA,

We sincerely thank all reviewers for their detailed and constructive feedback, which has been invaluable to our work. In particular, we greatly appreciate the following acknowledgements from your reviews.

  • The value of the theoretical approach (wZ8S, NbBA). wZ8S described the approach as “valuable and clever” and wrote that the theoretical contributions “seem correct and relevant.” NbBA wrote, “The theoretical analysis is solid.”

  • A precise account of what each loss requires (rW5t). rW5t described the loss-specific characterization as “precise and interpretable,” highlighting how the coefficient formula and Theorems 1–2 identify which interactions suffice for optimal decisions and why each active direction is needed.

  • The non-prefix result (rW5t, NbBA). Both reviewers highlighted the threshold example in which first- and third-order information suffice even though the second-order layer is omitted. rW5t noted that “retaining more coordinates or a longer prefix need not retain the right information.” NbBA described this result as “particularly interesting and somewhat novel.”

  • Separating information from estimation (rW5t). rW5t wrote, “The experiments carefully separate information from estimation.”

  • Agreement between theory and experiment (NbBA). NbBA wrote, “The experimental results are consistent with the theoretical findings.”

Your questions led to the following revisions.

ConcernReviewer(s)RevisionLocation in Revised Manuscript
What is new relative to prior work?NbBAWe explain how our formula identifies the required interaction orders and how the necessity proof establishes the minimum affine-linear dimension.Section 2 (Table 1), Sections 4.1–4.2
How does the theory guide training?wZ8S, rW5tWe explain Theorem 2 with an example and show how to build training targets, select a predictor on validation data, and decode its output.Sections 3.1, 4.2, and 5
Can the number of relevant items vary?NbBANbBA’s question led to a new theorem for variable outcome sizes. With a fixed decision budget and symmetric overlap loss, it gives observable training targets and the exact minimum sufficient affine-linear dimension.Section 5 (Proposition 1), Appendix G.1
When does higher-order information help?rW5t, wZ8SWhen third-order information changed the best action across contexts, the learned active predictor improved success over the best fixed decision by 5.625 pp at 5,000 samples, reaching the theoretical ceiling for that setting.Section 6.2 (Table 3), Appendix H.2
How much computation does direct prediction save?rW5t, wZ8S, NbBAWe tested 32, 64, and 128 WikiSeeAlso candidates. At 128, pair prediction gave 26.594× faster fitting and 34.178× faster inference, with 16.835% success versus 17.245% for Full CE.Section 6.3 (Table 4), Appendix I.1
How can readers unfamiliar with the mathematical tools follow the main argument?wZ8SWe added a numerical example to distinguish outcome probabilities from decision scores, explained the intuition behind Theorem 2 before its proof, and showed how to train the predictor and use it to choose a decision.Sections 3.1, 4.2, and 5
What does each experiment establish, and how do the results fit together?wZ8SWe reorganized Section 6 around three questions. The first experiment identifies which information each loss requires. The second tests when learning that information improves decisions. The third measures the cost and decision quality of direct prediction on WikiSeeAlso. We also clarified the figure captions.Sections 6.1–6.3

Thank you again for your time. We would be happy to discuss any remaining questions about the revision.

Warm regards,
The Authors

AuthorsOpenReview ↗

Summary of Contributions, Reviewer Feedback, and Manuscript Revisions

Dear AC, SAC, and PCs,

Thank you for overseeing the review of our paper, Decision-Sufficient Predictive Representations for Symmetric Fixed-Cardinality Losses. The initial ratings were 3 (rW5t), 2 (wZ8S), and 3 (NbBA). rW5t raised their score from 3 to 4, citing the WikiSeeAlso speedups and clearer evidence on when higher-order information helps. NbBA confirmed that they had considered our responses, and NbBA's score remains 3.

1. Core Contributions

  • Which information does a loss require? For symmetric fixed-cardinality overlap losses, our closed-form rule gives the required interaction orders and their decision-score weights directly from the loss profile.
  • What is the smallest sufficient representation? The active interactions preserve every expected-loss comparison. For each active direction, we construct two distributions that become indistinguishable if it is removed yet have no optimal decision in common. This establishes the exact minimum affine-linear dimension.
  • How does the result guide training? The loss determines targets we can compute from observed outcomes. When both selected labels must be relevant, each observed triple supplies three positive pair targets. A model can learn pair probabilities directly and select the highest-scoring pair.

2. Acknowledged Strengths

  • Theoretical approach. wZ8S called it “valuable and clever.” NbBA wrote, “The theoretical analysis is solid.”
  • Precision. rW5t called the characterization “precise and interpretable.”
  • Which layers matter. rW5t and NbBA highlighted the example at n=6n=6, m=K=3m=K=3, where success requires at least two hits. The 10-dimensional V1⊕V3V_1 \oplus V_3 is sufficient, while the 14-dimensional V1⊕V2V_1 \oplus V_2 misses the required third-order information. NbBA called this “particularly interesting and somewhat novel.”
  • Information and estimation. rW5t wrote, “The experiments carefully separate information from estimation.”
  • Agreement with theory. NbBA wrote, “The experimental results are consistent with the theoretical findings.”

3. Summary of Rebuttal and Reviewer Feedback

ConcernReviewerOur ResponseLocation in Revised Manuscript
What does the result add to existing spectral and geometric tools?NbBAThe loss profile gives the active orders, their weights, and the exact minimum affine-linear dimension. We prove why each active direction is necessary.Section 2 (Table 1), Sections 4.1–4.3
What does symmetry require? Can outcome size vary?NbBASymmetry requires equal utility for selections with the same overlap. We thank NbBA for the question that led to a new theorem for unknown outcome size at prediction time. For a fixed decision budget, it gives observable training targets and the minimum dimension of a universally sufficient affine-linear representation.Sections 3 and 5 (Proposition 1), Appendix G.1
What does each experiment establish?wZ8SSection 6 now asks what information each loss requires, when learning it improves decisions, and what direct prediction saves on a real task.Sections 6.1–6.3
When does higher-order information help?rW5t, wZ8SWhen third-order information changed the best action across contexts, the active predictor gained 5.625 percentage points over the best fixed decision at 5,000 samples, reaching the theoretical ceiling.Section 6.2 (Table 3), Appendix H.2
What does direct prediction save, and how does success compare?rW5t, wZ8S, NbBAWe tested 32, 64, and 128 WikiSeeAlso candidates. At 128, scoring 8,128 pairs vs. 341,376 triples gave 26.594× faster fitting and 34.178× faster inference.Section 6.3 (Table 4), Appendix I.1
How can readers follow the mathematical argument?wZ8SA numerical example distinguishes outcome probabilities from decision scores. We explain why Theorem 2 requires every active direction and show how to construct a target, train a predictor, and decode its output.Sections 3.1, 4.2, and 5
How do estimator, checkpoint, and decoder choices affect decisions?rW5tWe explain how to choose between direct estimation and full prediction followed by projection on validation data. Figure 3 tracks decision quality during training, and Appendix H.3 compares exact and greedy decoding.Section 5, Section 6.2 (Figure 3), Appendix H.3

4. Concluding Remarks

The revised paper extends the characterization to unknown outcome sizes. The experiments show when higher-order information improves decisions and measure the cost of predicting the required quantities directly on WikiSeeAlso. Thank you for your time and consideration.

Sincerely,
The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.