acceptodds
Under review as a conference paper at ICLR 2027

Why and When Score-Function Learning Fails under Discrete Downstream Evaluation

Abstract

Score-function learning estimates gradients from scalar feedback and thereby enables optimization through nondifferentiable and even black-box evaluators. Although its estimator is unbiased for a smoothed objective, this guarantee does not determine whether the current gradient can be recovered under a finite evaluation budget. We identify two failure mechanisms under discrete downstream evaluation. Boundary starvation occurs when sampled candidates rarely cross loss-changing decision interfaces, causing centered group updates to vanish. Tangential noise arises because perturbation components tangent to these interfaces contribute variance without changing the mean gradient. Based on this characterization, we introduce two budget-dependent quantities. Activation evidence measures whether the available queries are likely to reveal an informative loss comparison, while gradient resolvability compares the squared norm of the smoothed gradient with the estimation variance remaining after budgeted averaging. Both quantities can be estimated from pilot groups through a confidence-aware diagnosis. Numerical experiments verify the existence of both failure mechanisms and the effectiveness of the proposed quantities.

Primary area:
optimization
Keywords:
Score-function learning, Failure modes, Discrete optimizer

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_sHVSOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies when grouped score function gradient estimates become unreliable under discrete downstream evaluation. It identifies two failure modes, boundary starvation and tangential noise, and introduces measures estimated from pilot samples to determine whether a fixed query budget can reveal informative loss differences and accurately recover the smoothed gradient. The proposed analysis and diagnostic are evaluated on controlled shortest path problems, SEMO Energy Knapsack, and UCI HAR feature selection.

Critical strengths

The paper provides a rigorous geometric characterization of two distinct sources of finite budget failure in score function learning. Separating the scarcity of informative loss comparisons from the variance contributed by irrelevant directions offers a useful framework for understanding when an unbiased estimator may still be practically unreliable.

The empirical evaluation also uses independent pilot, reference, and future samples across controlled and application based settings. This prospective design, together with explicit abstention when the pilot evidence is insufficient, makes the reported diagnostic results more credible.

Critical weaknesses
  1. High diagnostic overhead. The primary experiments use 256 pilot groups, corresponding to 2048 evaluator calls for SEMO and 2048 or 4096 calls for HAR. These costs are comparable to or larger than the future budgets being diagnosed, which range from 128 to 4096 calls. This overhead may eliminate the claimed query savings (Section 5.2, Appendix D.4 and D.5, Tables 26 and 38).

  2. Missing end to end validation. The experiments measure how well the pilot predicts future gradient error and diagnostic states, but do not show that using the diagnosis improves training convergence or downstream task performance under an equal total query budget (Section 5 and Section 6).

  3. Restricted operational scope. The diagnosis applies only to a fixed sampling configuration and assumes Gaussian perturbations with deterministic piecewise constant feedback. The authors also state that reusing a pilot after updating the sampling distribution is not covered, limiting the applicability of the method to iterative learning (Section 2 and Section 6).

Questions for authors
  1. When reporting reductions in the selected future budget, how are the pilot evaluations accounted for? Can pilot samples be incorporated into the final gradient estimate or reused after an update, and if not, how does the method achieve net query savings during iterative learning?

  2. Under an equal total query budget that includes pilot evaluations, does using the proposed diagnosis improve training convergence or downstream task performance relative to a fixed budget strategy?

  3. How well do the nominal confidence levels match empirical coverage across repeated pilot draws at the same configuration, particularly in rare activation regimes?

6 comments
AuthorsOpenReview ↗

Response to Reviewer sHVS (1/2)

Thank you for your careful review and for recognizing the geometric analysis and independent-sampling design. Your concerns about pilot overhead, end-to-end benefits, and reuse prompted us to distinguish how many queries gradient recovery requires from whether diagnosing that requirement provides practical benefits. We strengthen the former through budget and optimization analysis and reassess the latter through total-cost accounting and repeated-pilot coverage experiments.

Revisions primarily addressing your comments are highlighted in blue in the revised manuscript. Locations of shared revisions are also listed below. All references refer to the revised manuscript.

1. How are pilot costs counted? Can pilot samples enter the final gradient estimate or be reused after an update?

Response. Pilot queries must count toward the total; reducing the subsequent budget alone does not establish net savings. The revision reports pilot, subsequent-update, and total costs:

  • SEMO: among configurations with a selected budget, the mean total is 2048+623.2=2671.22048+623.2=2671.2 queries, exceeding the largest candidate single-update budget of 2,048.
  • HAR: the corresponding mean total is 5,680.3–7,728.3 queries, exceeding the largest candidate budget of 4,096.

These results do not establish net savings for a single update. We correct this interpretation and use the pilot study to examine what diagnostic information is obtainable and how much obtaining it costs.

Regarding sample use, the current experiments keep pilot, reference, and future samples independent; pilot samples are not incorporated into the evaluated future gradient estimate. Under a fixed distribution, pilot samples also contain gradient information. However, incorporating the same samples used to select the budget would change the current independence structure and require analysis of the resulting estimation error and statistical properties. We have not counted such pooling as a demonstrated source of savings.

Regarding reuse, two cases must be distinguished:

  • Unchanged sampling distribution: one pilot can support comparisons across candidate budgets and amortize its initial cost over repeated estimates, because the population moments remain unchanged.
  • An update changes the sampling distribution: the old pilot's activation probability, gradient signal, and variance need not remain applicable. The current analysis does not guarantee reuse across updates or establish net savings during iterative learning.

Diagnostic value and cost-effectiveness therefore require separate evaluation. The revision retains evidence relating pilot predictions to independent future gradient quality while explicitly reporting total costs and the fixed-state scope.

Changes in the manuscript:

  • Appendix C.7, “Accounting for pilot queries,” and Table 8: adds total costs and compares them directly with the largest candidate single-update budgets.
  • Appendix C.6, “Reference and future samples,” and Appendix C.7: specifies the independent-sampling protocol and restricts the reuse discussion to an unchanged distribution.
  • Abstract and Introduction contributions: centers the paper on geometric mechanisms, query costs, and optimization consequences, with pilot diagnostics as a supplementary study.

Questions 2 and 3 are addressed in the next comment.

AuthorsOpenReview ↗

Response to Reviewer sHVS (2/2)

2. Does diagnosis improve convergence or downstream performance under equal total budgets including pilot costs?

Response. The current experiments do not establish this benefit for the pilot-based budget strategy. We revised the practical-benefit interpretation and investigated a key missing link: does improved gradient estimation necessarily translate into optimization progress?

The revision provides new theory and direct experiments. In the BPM, under shared perturbations, a fixed smoothing scale, and common scalar step sizes, full and normal-projected estimates can have different mean-squared errors yet produce identical ordinary-SGD objective trajectories. Norm clipping instead couples tangential noise to the useful normal step, allowing estimation improvements to affect objective decrease.

We added paired experiments with equal query budgets: 32 evaluations per update, 120 updates, and 3,840 evaluations per trajectory. Each setting uses 256 independent trajectory pairs, with dimension and clipping-threshold sweeps. Projection uses the known BPM normal to isolate tangential noise.

The findings match the analysis:

  • Under ordinary SGD, full and projected updates have identical normal coordinates and objectives at every recorded step.
  • At D=128D=128 and clipping threshold 0.1, a separate same-state comparison shows that the full update retains only about 28.3% of the projected normal step. In the equal-budget trajectory experiment, final mean losses are 0.0111570 and 0.00233768, respectively.

These results establish how estimation noise affects optimization; they do not establish an end-to-end advantage for pilot-based budget selection. They explain why accurate prediction of future gradient error alone cannot imply better training: the effect also depends on noise direction and the update rule.

The revision thus strengthens the mechanism analysis you recognized with new budget and trajectory results, aligning its central contributions with direct evidence.

Changes in the manuscript:

  • Sections 4.1–4.2: adds joint query budgets and cost-dominance regimes.
  • Section 4.3 and Appendix B.6: adds ordinary-SGD trajectory equivalence and norm-clipping analysis.
  • Section 5.3, Figure 4, and Appendix C.4: adds equal-budget trajectories and same-state update controls.
  • Introduction, experiment organization, and Conclusion: distinguishes mechanism validation from pilot-policy benefits.

3. How does empirical coverage compare with nominal levels, especially under rare activation?

Response. We added repeated independent pilots at fixed configurations with known population quantities. The experiment covers weak-signal, rare-activation, and near-threshold settings: 21 configurations, each with 500 independent pilots and 799 multiplier draws per pilot.

Coverage varies with configuration and sample size, with undercoverage in some settings:

  • At the gradient-resolvability threshold, coverage increases from 85.6% at n=64n=64 to 94.2% at n=1024n=1024.
  • A two-interface weak-signal configuration still has 91.0% coverage at n=1024n=1024.
  • Under rare activation, unconditional coverage at n=64n=64 is 100%, but interval availability is only 1.2%. Unavailable inference returns the full parameter space, so this is not evidence of precise, reliable diagnosis. At n=1024n=1024, availability reaches 71.6%, unconditional coverage is 94.2%, and coverage conditional on availability is 91.9%.

We therefore report both coverage and interval availability, separately from diagnostic output rates and label agreement.

The added experiment evaluates two-sided simultaneous moment bounds, whereas the application diagnostics use direction-specific margin bounds. We distinguish these constructions and do not interpret the joint-interval experiment as direct coverage validation of the application rule. We also correct confidence statements to report the nominal levels actually used and retain the undercoverage results.

These experiments reveal a practical difficulty beyond the population budget relation: rare feedback increases gradient-recovery costs and can also prevent a finite pilot from providing informative statistical assessments.

Changes in the manuscript:

  • Appendix C.7, “Repeated-pilot interval coverage,” and Table 9: adds repeated-pilot experiments, reporting coverage, availability, and conditional coverage under rare activation.
  • Appendix C.7, “Moment estimates and operational labels,” and Table 7: clarifies the application construction and distinguishes nominal levels, output rates, and label agreement.

We hope these revisions address your concerns and clarify the paper's contribution to understanding query costs and optimization mechanisms in discrete-feedback SFL.

Thank you for the substantial revision, which addresses much of my original concern. I share Reviewer PZ7N’s remaining concern about directly validating the application diagnostic, and I am still unclear whether the pilot procedure retains an actionable methodological role after being repositioned as supplementary. Given the extensive reframing and new results, I am keeping my rating unchanged for now but remain open to revising it.

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

This paper considers Score Function Learning (also known as Score Function Gradient Estimation) as a mechanism for black-box optimization, main in the context of Decision Focused Learning, where one wishes to optimize a decision cost that is often piecewise constant and defined by averaging over groups of examples.

The authors identify two failure modes for SFL in this context. The first one (boundary starvation) is related to a lack of diversity in terms of cost values (at the extreme: all samples have the same cost) and directly impacts the usefulness of the estimated gradient. The second failure mode (tangential noise) is related to samples being diverse along an axis that does not affect predictions (and therefore cost), which affects the variance of the gradient estimate.

The authors devise a test to check whether a given sampling budget has a good chance of recovering the (smoothed gradient), which could be directly employed in practice when sampling is sufficiently cheap, or have implications in the design of algorithms when sampling is more expensive.

The empirical evaluation, carried on in a simplified setting, is centered on validating the existence and distinctive characteristics of the failure modes, and on evaluating the reliability of the proposed criterion.

Critical strengths

In the context of Score Function Learning, the paper makes a focused contribution that is interesting and sound.

The contribution is very self-contained. Basically, the main findings are relevant as long as SFL is used, and therefore spanning methods in DFL, Multi Armed Bandits and Reinforcement Learning.

All the main contributions are useful: the main insights could be used to improve algorithms, while the proposed budget calibration criterion might be directly applicable in some circumstances or (again) serve as a reference calibration rule in some more complex approaches.

Critical weaknesses

The focused nature of the contribution is probably also its main limitation: both the insights and the criterion are only relevant in the context of SFL.

From a methodological point of view, while both considered failure modes are intuitively quite broad and general in scope, in practice they are investigated in a much narrower setting (i.e. binary decision). The analysis does not sufficiently clarify whether the formal results (rules, limits, etc.) hold in a general setting, or whether they are limited to the considered setting.

In the latter case, the appeal of the work would be diminished and a more thorough empirical evaluation would be necessary to provide evidence for the claims.

Questions for authors
  1. Are the main theoretical results specific to binary switching or do they hold in a more general setting?

AFTER THE DISCUSSION AND THE AUTHORS' RESPONSE

The reviewers' response, and an updated version of the manuscript containing new experiment and more precise information on the assumption have addressed most of my concern. I am adjusting my score accordingly. The contribution here may seem narrow, but it addresses a fundamental problem in SFL and can therefore spur further research.

4 comments
Reviewer_spE2OpenReview ↗

A few clarifications

Dear authors,

thanks for the rebuttal, but a couple of points do not appeared to be covered there (or are only partially covered):

  1. Can you clarify the generality of your experiments? In particular, to what degree restricting the empirical analysis to binary decision biases the results, and in which direction?
  2. Can you comment more in detail on the differences between your analysis and the references mentioned by reviewer PZ7N?

I had already a moderately positive opinion in this work. As things stand now, I am inclined to keep my score

AuthorsOpenReview ↗

Response to Reviewer spE2 (1/2)

Thank you for your careful assessment and for recognizing the paper's focused contribution, technical coherence, and useful mechanisms. Your central concern is that the mechanisms appear broadly relevant, but the original manuscript did not adequately distinguish general formal results from those requiring the binary model. We have clarified these levels of applicability, added theoretical results beyond binary feedback, and expanded the experiments to richer feedback structures. Revisions primarily addressing your comments are highlighted in green in the revised manuscript.

1. Are the main theoretical results specific to binary switching?

Response. The results have different scopes. The boundary representation, feedback activation, and population budget relation apply more generally; the BPM provides exact expressions in terms of boundary distance, dimension, and group size; and our new fixed-active-subspace result extends the irrelevant-direction variance analysis to multivalued feedback. The revision explicitly distinguishes these three levels.

First, the general structural relations do not require binary feedback or a single planar boundary.

  • The boundary representation applies to piecewise-constant evaluators under the stated regularity conditions, allowing multiple decision regions, feedback values, and curved interfaces. The smoothed gradient combines contributions from all loss-changing interfaces.
  • The group activation probability is qK=1−∑rρrKq_K=1-\sum_r\rho_r^K for any finite-valued feedback with i.i.d. samples, where ρr\rho_r is the probability of each feedback value.
  • The joint budget relation depends on activation probability, gradient signal, and group-estimator variance. Under a fixed sampling distribution, independent unbiased group estimates, and the stated signal and moment conditions, it does not require the BPM. The BPM expresses these population quantities through geometric parameters, explaining the sources of query cost.

Second, the BPM enables an exact separation of the two mechanisms' costs.

The BPM preserves constant feedback within regions and abrupt changes across their interface, while separating the normal direction that affects feedback from tangential directions that do not. This yields closed-form normal–tangential covariance and identifies when rare-feedback or tangential-dimension costs dominate. These exact distance-dependent formulas use the planar structure.

The first-activation waiting-cost result has a different scope: it requires only binary i.i.d. feedback under the complete-group protocol, not planar geometry. Expressing this cost as a function of standardized boundary distance then uses the Gaussian BPM.

Third, we add variance and trajectory results beyond binary feedback.

For L(u)=f(Pu)L(u)=f(Pu), with a fixed rank-rr orthogonal projector PP, we prove that, under Gaussian sampling and the stated moment condition, irrelevant directions contribute exactly (D−r)Var⁡(Y)σ2(K−1)\frac{(D-r)\operatorname{Var}(Y)}{\sigma^2(K-1)} additional estimator variance. Here, ff may have multiple feedback values and multiple or curved interfaces within its active subspace. Thus, variance accumulation in irrelevant directions does not depend on a single binary planar boundary. The extension assumes global invariance along the excluded directions, specifying precisely which variance can be removed.

Ordinary-SGD trajectory equivalence also extends to this structure: with identical initial active coordinates, shared perturbations and matched groups, a fixed smoothing scale, and common scalar step sizes, full and projected updates preserve identical active coordinates and objective values. The distinction between estimation error and optimization progress therefore also extends beyond binary feedback.

Changes in the manuscript:

  • Sections 3.1–3.2: clarify the scope of the boundary and activation results, and distinguish the binary waiting cost from its Gaussian geometric interpretation.
  • Section 4.1: states the general budget conditions and the BPM's role in explaining their geometric dependence.
  • Section 4.2, “Beyond the BPM: globally invariant directions”: adds the fixed-active-subspace variance identity.
  • Appendices B.1 and B.4–B.6: provide conditions, proofs, and the subspace extension of SGD trajectory equivalence.

The additional empirical evidence is detailed in the next comment.

AuthorsOpenReview ↗

Response to Reviewer spE2 (2/2)

2. What empirical evidence has been added for richer feedback structures?

Response. We added three complementary types of evidence: tests of the extended exact result, analyses of multiple interfaces and curvature, and budget-dependent behavior in practical discrete tasks.

First, multivalued-feedback experiments directly test the new subspace variance identity. We use four-level grid feedback and three-level concentric-region feedback; the latter contains multiple curved interfaces. The experiments cover dimensions 2–128 and three group sizes, yielding 42 configurations with 32,768 independent groups each. Across the 36 configurations with positive variance increments, the largest relative discrepancy between prediction and measurement is 0.564%. Additional rotated-subspace experiments also match the predictions, showing that the result does not rely on coordinate-aligned active directions.

Second, multiple-interface cancellation and curvature experiments identify factors that matter in more general geometries. In a two-interface example, group activation is approximately 95.27%, yet the population gradient vanishes at the symmetric location because the interface contributions cancel. Frequent feedback differences therefore do not guarantee a nonzero mean gradient. The curvature experiment holds the nearest standardized boundary distance fixed while varying curvature, demonstrating different activation probabilities and gradient signal-to-noise ratios at the same nearest distance. These findings agree with the general boundary representation and show why richer geometries require considering the directions and Gaussian weights of multiple interface contributions.

Third, practical discrete-task experiments examine the distinction between feedback activation and gradient accuracy. We reorganized the SEMO Energy-Knapsack and HAR feature-selection experiments to compare activation with gradient quality measured using independent future samples across fixed sampling states, smoothing scales, and budgets. They exhibit distinct states: scarce feedback comparisons, available comparisons with inaccurate gradients, and recoverable gradients. Controlled experiments establish the mechanism attribution, while the application studies demonstrate the relevance of this distinction in practical tasks.

Changes in the manuscript:

  • Appendix C.5, “Multivalued Feedback and Additional Geometry”: adds multivalued and rotated-subspace tests, multiple-interface cancellation, and the fixed-distance curvature experiment.
  • Section 5.4 and Appendix C.6: reorganize the application budget and gradient-quality results, clarifying their complementary role alongside the controlled mechanism experiments.
  • Introduction and Section 4: clarify the theoretical organization: general structural relations, exact BPM cost analysis, and fixed-subspace extensions.

These revisions make the contribution and its scope more explicit: the general results describe how comparative information and gradient signal arise, the BPM quantifies the two mechanisms' costs, and the subspace extension and additional experiments establish how these insights apply to richer feedback structures.

We hope these revisions address your concerns.

Thank you for your follow-up. We briefly clarify both points below.

1. Experimental generality and the direction of potential bias.

The controlled shortest-path experiments deliberately isolate a local binary switch. However, the added multivalued-feedback experiments and the SEMO and HAR studies do not impose binary feedback.

The simplification can affect results in different directions. Under a fixed sampling distribution, merging feedback categories reduces activation, making feedback scarcity appear more severe. Conversely, a single planar interface excludes cancellation across interfaces and provides known irrelevant directions, potentially making gradient recovery and projection benefits appear more favorable. For example, in the two-interface experiment in Appendix C.5, activation is approximately 95.27%, yet the population gradient is zero because the interface contributions cancel.

We use the binary model to isolate the two mechanisms, then examine how they manifest under multivalued feedback, curved boundaries, and practical discrete tasks.

2. Differences from the 3 references.

  • DAPO makes training batches informative; we quantify when informative feedback is sufficient. Filtering zero-update groups does not ensure accurate gradients. We count all evaluator calls and derive the budget needed to satisfy both activation and gradient-accuracy requirements.

  • Nie et al. analyze group degeneracy and fixed-reference advantages; we explain what degeneracy probability cannot determine. Holding activation fixed, gradient-recovery cost can still change substantially: increasing dimension from 1 to 32 leaves our activation requirement at 488 queries but raises the joint requirement to 1,560. Our boundary-specific covariance identifies the source of this gap and when removing irrelevant directions actually reduces the required budget.

  • Guided ES analyzes surrogate-guided sampling through a local smooth approximation; we derive exact moments for discontinuous feedback at finite smoothing scales. A local expansion inside a constant-loss region misses the boundary crossings that generate our gradient signal. We additionally establish that variance reduction need not improve optimization: under the stated coupling conditions, projection leaves ordinary-SGD objective trajectories unchanged, while norm clipping can make tangential noise impede the useful step.

Our contribution is therefore to connect feedback geometry to distinct query costs and optimizer-dependent consequences, beyond identifying zero-update groups or the benefits of subspace variance reduction. These comparisons appear in Appendix A, with the technical results in Sections 3–4. We hope these clarifications address your concerns.

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

This paper studies the finite-budget reliability of grouped score-function gradient estimates for deterministic discrete downstream evaluators. It distinguishes between groups with identical feedback, which produce zero centered updates, and noise in directions tangent to loss-changing interfaces. For a binary planar interface under Gaussian perturbations, it derives activation probabilities and an exact normal–tangential variance decomposition. It then proposes pilot-based diagnostics for activation and gradient estimation accuracy, with an unresolved outcome when the evidence is insufficient. Experiments include controlled shortest-path problems, Energy-Knapsack, and feature selection.

Critical strengths
  1. The distinction between obtaining nonconstant feedback and estimating an accurate gradient is useful. The binary-interface analysis makes the dependence on boundary distance, group size, and tangential dimension explicit. The controlled shortest-path experiments provide a direct check of these predictions.

  2. The prospective evaluation separates pilot, reference, and future samples. The comparison with ratio-based confidence inference uses the same pilot data and query budget, and shows improved diagnostic coverage. Reporting abstention and sensitivity to pilot size is also helpful.

Critical weaknesses
  1. The paper does not sufficiently distinguish its contributions from closely related work on group-relative gradient estimation. The zero-update problem caused by identical within-group feedback has already been explicitly identified in the GRPO literature, with targeted mitigation strategies proposed. DAPO [1], for example, filters groups with identical rewards and continues sampling. Gradient Starvation in Binary-Reward GRPO [2] also gives the degeneracy probability pK+(1−p)Kp^K+(1-p)^K, whose complement is the binary activation probability used here. Neither work is cited or discussed.

    These approaches do not necessarily resolve gradient estimation under a fixed query budget, nor do they establish this paper’s exact boundary-specific variance decomposition. Nevertheless, their direct relevance makes it important to clarify what additional understanding the proposed geometric analysis and diagnostics provide. Likewise, the discussion of tangential noise would benefit from a comparison with existing subspace-variance analyses such as Guided ES [3]. Without these comparisons, the significance of the paper’s incremental contribution remains difficult to assess.

  2. The reliability of the confidence-aware diagnosis is not sufficiently established in the regimes motivating the paper. Appendix C.3 assumes consistency of the proposed multiplier approximation rather than providing concrete sufficient conditions for this construction, particularly with weak gradients or rare activation. The application results provide encouraging evidence of diagnostic accuracy, but their reported “coverage” is the fraction of configurations receiving a diagnosis, not confidence-interval coverage. Agreement with independently estimated future labels therefore does not directly validate the nominal confidence level. This matters because reliable prospective diagnosis is a central contribution.

References:

[1] Yu et al. DAPO: An Open-Source LLM Reinforcement Learning System at Scale. 2025. https://arxiv.org/abs/2503.14476

[2] Nie et al. Gradient Starvation in Binary-Reward GRPO: Why Group-Mean Centering Fails and Why the Simplest Fix Works. 2026. https://arxiv.org/abs/2605.07689

[3] Maheswaranathan et al. Guided Evolutionary Strategies: Augmenting Random Search with Surrogate Gradients. ICML 2019. https://proceedings.mlr.press/v97/maheswaranathan19a.html

Questions for authors
  1. Relative to [1–3], which results constitute the main technical advance? In particular, what conclusions follow from the exact boundary-specific analysis that are not captured by existing group-degeneracy and subspace-variance analyses?

  2. Can you establish sufficient conditions for the multiplier validity assumption in Appendix C.3, or provide repeated-independent-pilot experiments at fixed configurations with known population quantities? Weak-signal, rare-activation, and near-threshold settings would be particularly informative. Please also clarify whether the primary experiments use the joint calibration in Eq. (64) or the direction-specific constructions described in Appendix D.1, and how the stated overall confidence level follows.

  3. What practical use case justifies the pilot cost? For example, the SEMO pilot requires 2,048 calls, while the reported mean selected future budget is 623.2 calls among certified configurations. The resulting total exceeds the largest candidate future budget of 2,048 calls. I appreciate that the paper reports these costs separately; please clarify when the diagnostic information provides sufficient benefit to offset this overhead.

5 comments
AuthorsOpenReview ↗

Response to Reviewer PZ7N (1/2)

Thank you for your careful review, particularly your comments on related work, diagnostic coverage, and pilot costs. The distinction you found useful between obtaining different feedback and accurately estimating a gradient motivated our further developments. We address your three questions below; all section and table references refer to the revised manuscript. Revisions primarily addressing your comments are highlighted in red in the revised manuscript.

1. What are the main technical advances over DAPO, binary-reward starvation analyses, and Guided ES?

Response. DAPO and Nie et al. already discuss equal-reward group degeneracy, and binary activation follows directly from the existing degeneracy probability. Guided ES studies how subspace information can improve search. We now explicitly acknowledge and discuss these connections. Our advance is to connect feedback degeneracy and irrelevant-direction variance to loss-changing interfaces, deriving their distinct query costs, dominance regimes, and optimization consequences.

The exact boundary analysis yields three further conclusions:

  • From group activation to the query cost of gradient recovery. We combine activation probability, gradient signal, and covariance to obtain the minimum complete-group budget satisfying both activation and relative-MSE requirements, for a fixed group size and sampling distribution. The BPM expresses these quantities through boundary distance, dimension, and group size. For example, at the same boundary distance, increasing dimension from 1 to 32 leaves the activation requirement at 488 queries but raises the joint requirement from 488 to 1,560. Group-degeneracy probability alone cannot explain this difference.

  • Separate rare-feedback costs from tangential-dimension costs and identify intervention regimes. The rare-boundary analysis yields the tangential-to-normal cost scale χ=K(D−1)/[(K−1)a2]\chi=K(D-1)/[(K-1)a^2], where aa is standardized boundary distance, DD is dimension, and KK is group size. This identifies when rare observations dominate and when irrelevant-direction noise is the main additional burden. Projecting the same samples reduces variance without improving activation; when activation determines the budget, variance reduction need not reduce the joint requirement. We also derive an exact variance identity for a fixed global active subspace, extending the irrelevant-direction analysis to multivalued feedback.

  • Separate estimation benefits from optimization benefits. In the BPM, under shared perturbations, a fixed smoothing scale, and common scalar step sizes, removing tangential noise improves gradient estimation but leaves ordinary-SGD objective trajectories unchanged. Norm clipping can instead allow tangential noise to reduce the useful normal step. Thus, the optimization benefit of variance reduction also depends on the update rule.

The contribution is therefore a geometric explanation that turns the two mechanisms into quantifiable, distinguishable, and experimentally testable budget and optimization consequences. Added experiments directly test these predictions.

Changes in the manuscript:

  • Appendix A (Related Work): added DAPO, Nie et al., Guided ES, and related studies, with a concluding paragraph explaining our position.
  • Sections 3.2–3.3: clarified attribution of known degeneracy phenomena and added the exact first-activation waiting cost under the complete-group protocol.
  • Sections 4.1–4.3: added joint budgets, cost decomposition and dominance regimes, the fixed-subspace identity, and SGD/norm-clipping analysis.
  • Sections 5.2–5.3 and Appendices C.3–C.5: added corresponding budget, trajectory, and multivalued-feedback experiments.

Questions 2 and 3 are addressed in the next comment.

AuthorsOpenReview ↗

Response to Reviewer PZ7N (2/2)

2. How is multiplier reliability assessed, which construction is used, and how should confidence levels be interpreted?

Response. Your distinction is important: diagnostic availability and agreement with independently estimated labels do not establish confidence-interval coverage. We corrected the terminology and followed your suggestion to evaluate repeated independent pilots at fixed configurations with known population quantities.

The added experiment covers weak-signal, rare-activation, and near-threshold settings: 21 configurations, each with 500 independent pilots and 799 multiplier draws per pilot. At the gradient-resolvability threshold, coverage increases from 85.6% at n=64n=64 to 94.2% at n=1024n=1024. However, another weak-signal configuration still has 91.0% coverage at n=1024n=1024. In the rare-activation case, interval availability increases from 1.2% to 71.6%, illustrating why high unconditional coverage can coexist with little informative inference. Unavailable inference returns the full parameter space; coverage conditional on availability is 91.9% at n=1024n=1024 in this case.

Regarding the construction, the application experiments use direction-specific margin bounds, not the joint calibration described in the original Eq. (64). The primary application diagnostics use 1,000 multiplier draws. The new coverage experiment instead evaluates two-sided simultaneous moment bounds based on a studentized maximum. We distinguish the two constructions and do not present the latter experiment as direct coverage validation of the application rule.

We also distinguish nominal levels from established guarantees. The revision reports the nominal component levels used, corrects the overall-confidence interpretation, and retains the observed undercoverage. These experiments directly address your requested finite-sample assessment and identify settings where reliable diagnosis remains difficult.

Changes in the manuscript:

  • Appendix C.7, “Moment estimates and operational labels”: specifies the direction-specific application construction, sampling settings, and nominal levels.
  • Appendix C.7, Table 7: explicitly labels the former “coverage” metric as Output rate, separately from label agreement.
  • Appendix C.7, “Repeated-pilot interval coverage,” and Table 9: adds repeated-independent-pilot experiments, reports coverage alongside interval availability, and distinguishes this assessment from the application diagnostics.

3. What use case can justify pilot costs, given that SEMO's total exceeds the largest candidate budget?

Response. Your SEMO calculation is correct: 2,048 pilot queries plus the conditional mean future budget of 623.2 gives 2,671.2 queries, exceeding the largest candidate single-update budget of 2,048. The current results do not establish net query savings for this single-update use case. We now make this comparison explicit and apply the same total-cost accounting to HAR.

The pilot experiments nevertheless provide evidence relevant to the mechanism analysis: they examine whether quantities governing gradient-recovery difficulty can be estimated prospectively in practical tasks, and what this diagnosis costs. On the valid comparison subsets specified in the manuscript, pilot inverse resolvability and independently measured future relative gradient MSE have Spearman correlations of 0.946 for SEMO and 0.981 for HAR. This supports their diagnostic relationship, while not establishing net cost savings from budget selection.

A potential setting for amortizing pilot costs is repeated gradient estimation or comparisons across candidate budgets under the same sampling distribution: the population moments remain unchanged, allowing pilot reuse. We restrict this discussion to a fixed sampling state; we do not claim demonstrated amortized savings or extend reuse to a changing training distribution.

We therefore retain the pilot study as a supplementary investigation of the reliability and cost of translating population mechanisms into practical diagnostics. The paper's core contributions are the geometric mechanism analysis, query-budget results, and optimization consequences, supported by direct experimental tests.

Changes in the manuscript:

  • Appendix C.7, “Accounting for pilot queries,” and Table 8: adds total costs and explicitly compares them with the largest candidate single-update budgets.
  • Appendix C.7, “Continuous prediction and pilot size”: reports the relationship with independent future estimation quality and diagnostic availability as pilot size changes.
  • Abstract, Introduction contributions, and Sections 4–5: organizes the main argument around mechanisms, budgets, and optimization consequences. Pilot diagnostics are consolidated in Appendix C.7, with their supplementary role and fixed-state scope made explicit.

Thank you for the clarifications and the revised positioning. Table 9 evaluates the simultaneous bounds rather than the direction-specific application rule, and Table 7 measures agreement with estimated future labels, not known truth. Could you apply the actual rule to repeated independent pilots in the existing known-population cases (near-threshold, weak and rare signals) and report, over all pilots, the incorrect-label and abstention rates? If this is not feasible, please note this limitation in Appendix C.7. I will keep my rating unchanged for now and reassess after your response.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Revision Summary

We thank all three reviewers for their careful evaluations and constructive suggestions. Their concerns centered on our contribution relative to prior work on gradient starvation and subspace variance reduction; the scope of the binary planar model (BPM); the reliability of pilot diagnostics; and their practical benefits after accounting for pilot costs.

These comments helped sharpen our central question: Under discrete feedback, why do obtaining distinct feedback, accurately estimating a gradient, and making optimization progress require different conditions? We have strengthened the theory and experiments, extending the original identification of boundary starvation and tangential noise into an analysis of their query costs, dominance regimes, and optimization consequences. The revision develops two main contributions.

First, we connect feedback geometry to gradient-recovery costs and identify when each mechanism dominates. Prior work has studied equal-feedback group degeneracy and subspace variance reduction. We explain how the accessibility of loss-changing interfaces determines the availability of comparative feedback, while irrelevant perturbation directions increase the cost of extracting the gradient signal. Building on the original interface representation and covariance analysis, we derive query budgets that jointly satisfy activation and gradient-accuracy requirements, separating rare-feedback costs from tangential-dimension costs.

This yields concrete predictions about interventions: removing tangential components from the same queries improves estimation without changing feedback activation, and may therefore leave the joint budget unchanged when activation is the bottleneck. The expanded related work makes these distinctions explicit.

Second, we establish when estimation noise affects optimization. In the BPM, under shared perturbations, a fixed smoothing scale, and common scalar step sizes, ordinary SGD produces identical objective trajectories with the full estimator and its normal projection, despite potentially large differences in gradient mean-squared error. Norm clipping instead couples irrelevant noise to the useful normal step, allowing tangential noise to impede objective decrease. The optimization effect of variance therefore depends on its direction and the update rule.

We also derive a variance identity for losses depending on a fixed global active subspace, extending the irrelevant-direction analysis to multivalued feedback. The revision distinguishes general results from BPM-specific formulas and examines multiple-interface cancellation and curvature to clarify the role of richer feedback geometries.

The revised experiments address three questions:

  1. Do the mechanisms and query costs match the predictions? We retain validation with an actual shortest-path solver and add joint-budget sweeps and cost-decomposition experiments.
  2. When does better estimation improve optimization? Paired trajectory experiments at equal query budgets verify ordinary-SGD trajectory equivalence and demonstrate the clipping interaction.
  3. How do the explanations extend beyond the BPM? Multivalued-feedback, cancellation, and curvature experiments, together with SEMO and HAR studies, examine richer structures and practical discrete tasks.

Clarification and role of the pilot results. We agree that reducing the subsequent evaluation budget does not establish total query savings. We add explicit total-cost accounting and repeated-independent-pilot coverage experiments, distinguish diagnostic availability and label agreement from interval coverage, and correct claims about savings and confidence that exceeded the evidence.

The pilot study now addresses a complementary question: Can the quantities governing gradient-recovery difficulty be reliably diagnosed from finite samples, and at what cost? Abstention, undercoverage, and pilot overhead in rare-feedback and weak-signal settings reveal a gap between characterizing population query requirements and reliably identifying them in practice. We retain this study in the appendix to examine diagnostic reliability and cost; the mechanisms themselves and their optimization consequences are directly tested by the controlled experiments.

The revised manuscript proceeds from feedback geometry and the two mechanisms, through query costs and optimization consequences, to experimental validation. It provides a theoretically grounded and empirically tested account of whether discrete-feedback SFL is limited by insufficient comparative information or noisy gradient extraction, which interventions address each difficulty, and when those interventions can improve optimization. Code for the added experiments has been submitted as the supplement materials.

AuthorsOpenReview ↗

Summary of the Discussion

We thank the three reviewers and the Area Chair for the discussion. The original submission had two aims: to explain why gradient estimation can fail under discrete feedback and to use a pilot to predict whether a future query budget will suffice. The revision focuses on the mechanisms: when it is difficult to obtain distinct feedback, when the gradient remains difficult to estimate even after distinct feedback appears, and when these difficulties affect optimization. The pilot study remains in the appendix to examine how reliably finite samples can distinguish these cases.

1. Contribution relative to prior work and reliability of the pilot (Reviewer PZ7N)

PZ7N noted that DAPO already handles groups with identical rewards, prior work on binary-reward GRPO gives the probability of such groups, and Guided ES uses subspace information to reduce variance. Our analysis asks where the queries go: how much of the budget is needed to observe distinct feedback, and how much is needed to estimate the gradient accurately? In the binary planar model, we derive the budget required to meet both conditions. This explains why removing irrelevant directions from the same samples improves gradient precision while leaving the probability of observing distinct feedback unchanged.

PZ7N also asked us to test the actual diagnostic against known population labels. We ran 500 independent pilots per configuration and reported errors and abstentions over all pilots. At one weak-signal state, increasing the future budget changed the source of failure from insufficient feedback to insufficient gradient precision. The rule identified the two cases correctly in 90.2% and 94.8% of pilots, respectively. At the exact precision threshold, 88.2% abstained and 9.6% gave an incorrect label. These results show both where the pilot distinguishes the mechanisms and where the distinction is difficult to make from finite samples.

2. Scope of the binary planar model and direction of experimental bias (Reviewer spE2)

spE2 asked which conclusions extend to multivalued feedback and how restricting experiments to a single binary boundary affects the results. The revision distinguishes the interface representation for piecewise-constant feedback, the variance result for losses depending on a fixed subspace, and the exact distance-dependent budget formulas for a planar boundary. The simplification can affect the two mechanisms in different directions. Merging feedback categories makes distinct feedback less frequent, while a single interface rules out cancellation and can make the gradient appear easier to recover. In our two-interface experiment, about 95% of groups contained distinct feedback, yet the population gradient was zero because the interface contributions canceled. In the updated review, spE2 indicated that the revision addressed most of this concern and adjusted the score accordingly.

3. Practical value of the pilot and implications for optimization (Reviewer sHVS)

sHVS asked what decision the pilot supports once its cost is included. At a fixed sampling state, the pilot selects the smallest candidate budget it judges sufficient. In SEMO, it selected a budget in 38 of 105 configurations, and an independent future-sample evaluation judged all 38 sufficient. Including the pilot, those configurations averaged 2,671 evaluations, above the largest single-update budget of 2,048. sHVS acknowledged that the revision addressed several concerns and maintained the original rating, citing the extent of the reframing and the remaining limitations of the diagnostic.

The question about optimization also motivated us to bring forward an analysis originally planned as follow-up work: when does a more accurate gradient estimate actually change optimization progress? In the binary planar model, with shared perturbations, a fixed smoothing scale, and common scalar step sizes, removing tangential noise lowers estimation error but leaves the objective value at every ordinary SGD step unchanged. With norm clipping, the same noise can shorten the step in the direction that affects the loss. This result connects the source of estimation error to its consequence for a specific update rule.

We thank the reviewers again for their careful reading and follow-up questions, and the Area Chair for considering the revised work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.