- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies gradient estimation for vector-valued black-box scores in a setting where a model makes many binary decisions and the evaluator's outputs depend only on counts (or bounded integer-weighted totals) over publicly known row partitions, while the mapping from these aggregates to scores is unknown. The proposed Block-OSRB conditions the two-query DisARM antithetic Bernoulli estimator on the paired cell/block aggregates, computing exact per-row coefficients via bivariate generating-function coefficient extraction (Eq. 8) at O(Mnb²) local cost and no additional oracle calls. The theory establishes columnwise PSD covariance dominance (Thm 1), joint dominance under a common refinement (Thm 3), an extension to weighted totals (Thm 2), a nested block path (Thm 4), convex multi-partition averaging (Thm 5), and a bias bound under contract misspecification (Prop 1). Experiments optimize a 32-dimensional logit residual over frozen representations on Adult, ACSIncome, Waterbirds, and UCI Credit with 24H/96H query budgets, reporting 1−HV regret, plus a small trainable-MLP test on Student Dropout and a weighted-total study on UCI Credit.
Critical strengths
S1. Clean, correct method with unchanged query cost. Exact coefficient extraction (Eq. 8) computes the conditional expectation without counterfactual queries, and Thms 1/3/4 give a nested PSD covariance order from DisARM to full-cell conditioning. Fig. 2 confirms that b = 64 reduces the gradient covariance trace by 70–89% at the initial state. This is the main reason I consider the work potentially publishable.
S2. Careful and transparent experimental practice. Query ledgers, one-time frozen holdouts, and paired intervals are reported, and unfavorable results are disclosed (Quotient-FD is best at Adult 96H in Table 6; the group-ranking policy dominates on Student Dropout in Table 9; the R176 failure in App. C.6). This makes the concerns below verifiable rather than hidden.
Critical weaknesses
W1. The headline empirical claim relies on a weaker parent and a coarse metric, overstating the gains.
- Table 2 compares against unmasked DisARM on three of the four tasks. The paper's own decomposition (App. C.5, l.781–783) shows that at Adult 24H, 0.01721 of the 0.01800 ordinary-to-Block regret difference comes from masking publicly irrelevant rows, not from count conditioning.
- Against masked DisARM, the Adult development gains shrink to 0.20% / 3.40%, with the 24H interval spanning zero (Table 3, l.398). On the Adult 96H holdout, Block wins in only 4/8 seeds (l.384, l.1158). Holdout comparisons against the masked parent exist only for UCI Credit (4.5% / 6.3%) and Student Dropout (0.7% / 2.9%), and no non-LR baseline (SPSA, Quotient-FD, AS/FW) is evaluated on the holdouts.
- Each preference optimizes vᵀE[H], but the reported metric is the hypervolume of three points. Table 17 shows the union adds only 0.09–5.91% HV beyond the best single point. App. H.4 shows that, for the Adult fairness preference, Block is worse on the scalarized loss it actually optimizes (holdout 24H vs. ordinary DisARM: 0.13808 vs. 0.13329; development vs. masked DisARM: 0.13869 vs. 0.12906 at 24H and 0.12496 vs. 0.12183 at 96H).
As a result, the abstract's claim of lower regret "in all eight task–budget cells" is not adequately supported. Holdout results against masked DisARM and per-preference scalarized losses for all tasks would address this.
W2. The main experimental arm lacks the stated guarantee, and the practical regime is not demonstrated.
- The main arm is the objective-wise estimator, for which Thm 1 guarantees only columnwise dominance. Because different columns are conditioned on different σ-algebras, the variance of the scalarized gradient under a fixed v is not guaranteed to decrease, and Cor 2 explicitly covers only the single-objective and common-refinement cases. The scalarized variance is checked empirically only at the initial Waterbirds state (l.420), and the optimizer is Adam with gradient-norm clipping and a parameter-radius cap (l.1075–1076), not the constant-step SGD analyzed in Cor 2.
- The access model requires ground-truth labels and protected attributes for every evaluated row to be public, yet the experimental h (macro-F1, |DP|, |EO|) consists of standard closed-form functions of confusion counts. The paper prints these formulas, and black-box access is implemented by a process boundary (l.618–620). In this regime, each objective depends on only two public cells, so the gradient of E[h(C)] could be computed exactly by a Poisson-binomial DP (or estimated to arbitrary precision by local sampling) with zero oracle queries.
- Local cost is roughly 54–124× that of DisARM (58.28 ms vs. 0.47 ms per update; 55.37 s vs. 1.02 s per Student trajectory), giving a break-even single-H latency of about 289 ms, but no experiment uses a genuinely unknown or expensive oracle. In the only larger trainable experiment (4.7M parameters, R176), Block is clearly worse than DisARM (0.626 vs. 0.531, l.844–846).
Questions for authors
- Q1. Can you report Adult, ACSIncome, and Waterbirds holdout results for masked DisARM and Quotient-FD/SPSA? If the frozen protocol does not allow rescoring, would you restate the abstract and Table 2 with the masked parent as the primary comparator?
- Q2. Can you provide scalarized losses vᵀH for every task, method, and preference? Why is Block worse under the Adult fairness preference?
- Q3. Why is the objective-wise arm used as the main method rather than the common-refinement arm, which carries the joint guarantee? Can you report the scalarized gradient variance along full optimization trajectories rather than only at the initial state?
- Q4. What explains Block being substantially worse than DisARM in R176? All methods use lr = 0.03 without per-method tuning. Could lower-variance gradients interact with Adam's normalization and clipping?
- Q5. When pᵢ ≡ p within a cell g, Σ_{j∈g} q_j = ½c(A_g − B_g) with c = max(p, 1−p)/(p(1−p)) is already count-measurable, so by exchangeability φᵢ reduces to ½c(A_g − B_g)/n_g. How much of the variance reduction does this O(n) closed-form approximation capture, and what is the incremental benefit of the exact O(nb²) DP?
Response to cRqg
Q1. Stronger baselines
The original eight-cell statement concerns mean HV regret against the evaluated DisARM/UGC arms. The text also reports Adult 96H's 4/8 seed wins. We added these test comparisons:
H is one full-vector oracle call. Relative HV-regret reductions at 24H / 96H; positive favors Block; †: 95% CI excludes zero. Masked comparisons use 8 paired seeds; non-LR uses 5/10/8 for Adult/ACS/Waterbirds. Pairing is within cohort; actual query use is retained.
Q2. Losses for each preference
The Q2 tables report every preference loss. Adult 24H fairness loss is 0.138080 for Block, 0.133289 for ordinary DisARM and 0.131017 for masked DisARM. Against ordinary DisARM, utility/DP improve by 0.006476/0.014874, but EO worsens by 0.030090: the weighted loss rises by 0.004791. HV measures the policy set, so its improvement can coexist with this loss.
Adult Quotient-FD wins five of six own-loss comparisons with CIs excluding zero; Student Dropout group ranking wins all six original test comparisons. Waterbirds favors Block against all three stronger baselines in all six comparisons, with favorable CIs.
Q3. Why objective-wise conditioning?
We use objective-wise conditioning because its coarser per-objective statistics can remove more marginal noise. Common refinement retains cross-objective distinctions to guarantee joint/fixed-scalarization PSD reduction. Neither provides an Adam guarantee.
For this response, we measured all 4,608 pre-update states of 96 Student trajectories through 94H, using 128 shared pairs and three scalarizations:
All 13,824 CIs per estimator favor reduction. At 96H, Block/Common regret is 0.439003/0.440493; CIs favor Block for all three preference losses and HV, versus none at 24H.
Q4. The larger-model failure
The original Waterbirds tail training used learning rate 10−4. In a 36-update diagnostic, all 26 zero gradients had identical paired feedback despite nonzero Jacobian probes. We then compared five estimators, two rules, eight seeds, three preferences and 4,721,153 trainable tail/head parameters; earlier layers stayed frozen.
Backtracking bounds actual raw-logit RMS/max changes at 0.1/0.5, with tolerance 10−6. It scales an Adam proposal, allows 20 halvings, and restores parameters on failure while retaining moments. These checks add local forwards, no H. The 384H test results are:
Block improves 20.81%/30.72% over masked/mean-p with favorable CIs; Common's CI includes zero. Backtracking worsens all five methods' early fairness losses, so it also changes the optimization trade-off.
Q5. The mean-p approximation
Your expression is exact at equal probabilities: ϕi=(Ag−Bg)/(2ngmin(p,1−p)) in probability coordinates; multiply by p(1−p) for logits. Mean-p uses the block mean here, retaining actual sampling/Jacobians. In six heterogeneous exhaustive cases, relative bias is 0.38–49.57%, while one-pair MSE is lower in all six.
On Student, CIs for the three preference losses and HV at 24/96H cross zero. On Waterbirds, all four at 96/384H favor Block over mean-p, despite mean-p's lower trace in all 36 diagnostic comparisons.
W2. Unknown objectives and runtime
We agree that known formulas allow local gradients. In a controlled Adult development experiment with an MLP oracle, common-refinement Block reduces HV regret by 24.96%/26.24% against DisARM at 24/96H (8/8 wins). The opaque-objective comments describe the oracle and scoring.
We added CityFlow signal-control benchmarks, each run twice. At Manhattan 384H, deployment-loss reductions against DisARM/mean-p are 6.00%/21.35% in the first batch and 17.24%/24.81% in the repeat. Repeat policy-ready times are 563.0/560.3/564.2s for Block/DisARM/mean-p. CEM is faster and better on Hangzhou and Manhattan 24/96H.
Fast exact counts reduce Student 96H time from 4.537 to 1.519s (masked: 1.131s). Weighted cost remains pseudo-polynomial; 288.82 ms/H was a break-even threshold.
New tests reuse existing splits. CIs are pointwise 95% on fixed tasks/panels; trajectory states are correlated. CityFlow times describe a shared host; the same three seeds are kept separate across batches.