acceptodds
Under review as a conference paper at ICLR 2027

Block-OSRB: Exact Output-Statistic Rao–Blackwellization for Aggregate-Invariant Vector Black-Box Optimization

Abstract

Optimizing differentiable models against vector-valued black-box scores is expensive when each query evaluates thousands of binary decisions. Many utility and fairness scores depend only on public aggregates, despite an unknown mapping from aggregates to values. We ask whether this structure can reduce gradient noise without increasing oracle queries. Block Output-Statistic Rao–Blackwellization (Block-OSRB) conditions a two-query antithetic estimator on paired block aggregates, integrating out row identities invisible to the evaluator. The same two oracle values suffice for every row, without counterfactual calls. For independent Bernoulli decisions, the estimator is unbiased for the unsmoothed objective and has no greater covariance than its DisARM parent for each output column. Nested blocks provide a variance–compute path; common refinement gives joint covariance control, and weighted-total conditioning dominates weight-category count conditioning. On Adult, ACSIncome, Waterbirds, and UCI Credit, count Block-OSRB has lower mean one-time holdout hypervolume regret in all eight task–budget cells than the evaluated DisARM and true UGC arms: 2.0–19.7% and 2.2–23.8% reductions, respectively. The first three DisARM holdouts use the ordinary parent; UCI Credit uses relevance masking. A separately frozen Student Dropout trainable-MLP test shows an estimator gain, while a deterministic group-ranking policy performs better. On weighted UCI Credit development data, conditioning on totals removes 59.4–60.7% of the covariance trace remaining after category-count conditioning. The approach targets declared aggregate interfaces when oracle queries dominate local computation.

Primary area:
optimization
Keywords:
Black-box optimization, Bernoulli gradient estimation, Rao-Blackwellization, Variance reduction, Multi-objective optimization, Aggregate-invariant metrics

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_cRqgOpenReview ↗
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?
1 comment
AuthorsOpenReview ↗

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:

Taskvs masked DisARMvs Quotient-FDvs SPSA
Adult-0.062% / 2.012%-0.857% / -4.951%2.421% / 5.370%
ACSIncome4.325%† / 3.268%†4.845%† / 3.474%6.033%† / 4.530%†
Waterbirds4.776%† / 14.213%†6.176%† / 12.714%†7.684%† / 21.428%†

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:

Estimator vs maskedMedian trace reductionRange
Block76.53%58.74–86.71%
Common76.15%59.36–85.94%
Mean-p86.58%71.94–93.58%

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−410^{-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−610^{-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:

Update rule: HV regretBlockMaskedCommonMean-p
Original Adam0.6263780.4507950.5756380.542038
Backtracking0.2628710.3319680.2804990.379412

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))\phi_i=(A_g-B_g)/(2n_g\min(p,1-p)) in probability coordinates; multiply by p(1−p)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.

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

This paper introduces Block-OSRB (Output-Statistic Rao-Blackwellization), a method designed to optimize differentiable models against vector-valued black-box scores that rely on public aggregate statistics. By recognizing that metrics like demographic parity or F-scores depend only on confusion matrix counts, the authors propose conditioning the two-query antithetic DisARM estimator on paired block aggregates. This integration analytically averages out row-identity randomness that is invisible to the evaluator, thereby reducing gradient variance without requiring additional counterfactual oracle calls. The authors establish a nested variance-computation trade-off and demonstrate empirical regret reductions against standard baselines on diverse classification and fairness benchmarks under constrained query budgets.

Critical strengths
  • The approach exploits the public contracts of standard utility and fairness metrics, using the fact that exchanging decisions within a label-group cell leaves the final metric unchanged. This allows exact coefficient extraction without extra oracle evaluations.
  • The paper provides strong proofs for columnwise Positive Semi-Definite (PSD) covariance dominance over the DisARM parent (Theorem 1). It also formalizes a nested block path where larger aligned blocks strictly lower covariance (Theorem 4).
  • Block-OSRB introduces a tunable block size parameter bb. This provides practitioners a direct lever to balance local computational overhead—scaling at O(Mnb2)O(Mnb^2)—against the latency and expense of black-box oracle queries.
Critical weaknesses
  • The technique fundamentally requires independent Bernoulli decisions and a declared aggregate contract, such as exact counts or bounded weighted totals. It cannot be applied to continuous optimization or unstructured black-box oracles that lack these symmetric aggregate properties.
  • While the method saves external oracle calls, the local dynamic programming scales quadratically with block size bb. For the weighted additive extension, this local cost becomes pseudo-polynomial O(nb2A2)O(nb^2A^2), relying heavily on the maximum normalized weight AA, which can become prohibitive for fine-grained or continuous weights.
Questions for authors
  • How does Block-OSRB's performance and covariance reduction scale when updating significantly larger parameter spaces (e.g., fine-tuning large vision or language models end-to-end), given that the primary experiments restricted optimization to 32-dimensional residuals?
  • Proposition 1 outlines the bias incurred under contract misspecification. In real-world deployments where the evaluator's internal aggregation logic might be obfuscated or approximate, how disruptive is this bias to the optimizer's trajectory, and are there robust ways to dynamically correct it?
2 comments
AuthorsOpenReview ↗

Response to caVw

Does the method scale to larger models?

The fixed model Jacobian preserves columnwise PSD covariance order at any parameter dimension. Common refinement gives the joint guarantee for fixed scalarizations. This requires independent Bernoulli variables and a declared aggregate contract; model parameters can be continuous. Aligned nested blocks give non-increasing covariance, with strict reduction only where conditional variance can be removed.

An existing exact count factorization reduces arithmetic from O(Mnb2)O(Mnb^2) to O(Mnb)O(Mnb) for MM columns, nn decisions and block size bb. On the same RTX 4090, median Student Dropout runtime at 96H fell from 4.537 to 1.519 s (2.99x), including initialization and optimizer work. Integer-weighted conditioning retains pseudo-polynomial cost. One H is one full-vector oracle call.

In a new Waterbirds experiment, we trained 4,721,153 parameters in the last ResNet18 block and head, keeping earlier layers frozen. We compared five estimators, two update rules, eight seeds and three preferences at 24/96/384H. Mean-p replaces only the probability in the conditional coefficient with the block mean; sampling probabilities and model derivatives stay unchanged.

For the shared backtracking rule, all 12 comparisons with masked DisARM across three own-preference losses, HV regret and three budgets favor Block by their paired intervals. The 384H results are:

MethodHV regretMethod minus Block [95% interval]
Block0.262871—
Masked DisARM0.3319680.069097 [0.045837, 0.096798]
Mean-p0.3794120.116541 [0.105932, 0.126899]
Common refinement0.2804990.017628 [-0.006127, 0.047348]

Block's regret is 20.81% lower than masked DisARM's and 30.72% lower than mean-p's. All four 384H intervals against common refinement include zero. Original Adam leaves Block at 0.626378 at every budget; backtracking also worsens every method's early fairness losses.

The rule scales an Adam proposal by s=min⁡(1,0.1/r,0.5/a)s=\min(1,0.1/r,0.5/a), where r,ar,a are proposed raw-logit RMS/max displacements. It checks actual logits on all development rows and allows 20 further halvings to meet bounds 0.1/0.5 (tolerance 10−610^{-6}). Failure restores parameters while retaining Adam moments. Every estimator uses this rule; checks add local model evaluations but no H.

At 24 fixed development checkpoints from one seed, we reused 256 antithetic pairs per state, adding no H. Under backtracking, Block's sampled parameter-gradient covariance trace is 40.22–60.35% below masked DisARM's, with favorable intervals in all 36 state–scalarization comparisons. Mean-p has lower trace than Block in all 36; one interval favors common refinement over Block. Eleven original-Adam states have zero sampled gradients, which does not establish zero true variance.

All 720 checkpoints were scored on the previously used official test. Optimization intervals resample eight seeds; covariance intervals resample pairs within a state. They are pointwise 95% intervals without multiplicity adjustment. The evidence covers tail training on reused test data and covariance at fixed development states.

How do contract errors affect optimization?

On Student data we used Hλ=(1−λ)H0+λWH_\lambda=(1-\lambda)H_0+\lambda W. Here H0H_0 contains macro-F1 loss and absolute DP/EO gaps; WW contains weighted classification error, positive-decision rate and positive-label false-negative rate, each normalized by relevant weights. Weights are 0.5/1 for ages at/below versus above the development median. Five strengths, four methods, eight seeds and three preferences give 480 runs capped at 128H, including probes.

Exact eight-decision analysis gives relative bias of 1.25–3.19% at λ=0.2\lambda=0.2 and 14.30–20.33% at λ=1\lambda=1 for the coarse estimator, which ignores age. The valid parent and age-stratified estimator match the reference numerically. Both coarse and refined conditioning beat masked DisARM in all 15 final strength–preference comparisons. Fallback is worse than coarse conditioning in all 15, with intervals excluding zero.

Four swaps cost 8H. Fixed-state detection is 116/128 (90.625%; Wilson interval 84.33–94.56%) at each positive strength, with 0/128 control false alarms. Online, all 24 runs at each positive strength alarm after 8 or 16 probe calls; controls use 32. Shared probe streams and noiseless outputs explain the identical detection rates across strengths.

Thanks for your clarification. I will keep my score.

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

The authors explain the general setting as having a high amount of binary decisions that are mapped to a score and explain that often the scores do not depend on the precise decisions directly but rather on aggregates. They raise the question whether this can be leveraged to reduce the gradient noise while not making evaluation more costly. They cite the existing DisARM gradient estimator that partially fulfills this and build their estimator on it. For this, a known partition of the objectives is assumed and the estimator is conditioned using those cells. They proceeded by establishing theoretical results, for instance that their gradient estimator under mild conditions has lower covariance than the DisARM estimator. They conclude with numerical experiments, showing improved performance for their method compared to the DisARM estimator and UGC estimator on several tasks.

Critical strengths

The authors seem to provide novel research by extending an existing estimator. They give a good and extensive theoretical justification for their approach, in particular showing reduced gradient noise while not needing more oracle evaluations.

Critical weaknesses

No.

Questions for authors

Is it generally the case that we know the partitions, or is that assumption quite restrictive? Also, to me the improvement in the experiments, seem rather small, although consistent. Is there a reason or limit for this improvement?

1 comment
AuthorsOpenReview ↗

Response to gCVd

When is the partition available?

The partition comes from the evaluator's declared aggregates. For confusion-count metrics, public labels and group membership determine the cells. More generally, the interface supplies CmC_m in Hm(X)=hm(Cm(X))H_m(X)=h_m(C_m(X)); the mapping hmh_m can remain unknown. This assumption limits the method to evaluators that provide such structure. Inferring a partition from observations alone would require a separate justification of the aggregate contract.

Why are the optimization gains modest?

At a fixed iterate, the covariance removed from each objective column equals the parent's expected conditional covariance given the paired aggregates. Thus, conditioning removes variation among decisions with the same aggregates, while variation across aggregates remains. If the parent is already determined by these statistics, there is nothing left to remove. The resulting improvement in final loss also depends on curvature, step sizes and adaptive normalization.

For this response, we examined all 4,608 pre-update states of 96 Student Dropout MLP trajectories: four estimators, eight seeds, three training preferences and 48 updates. At each state, we used 128 shared antithetic pairs to compare three scalarizations. One H denotes one full-vector oracle call.

Student development resultReduction relative to masked DisARM
Sampled gradient covariance trace58.74–86.71%; median 76.53%
Hypervolume regret, 24H1.40%
Hypervolume regret, 96H4.92%

This illustrates the distinction: substantial noise reduction can accompany a modest change in optimization performance.

We also extended the Adult development trajectories to 384H, retaining the same eight paired seeds. Positive values below favor Block. The intervals are for the absolute regret difference; reductions are relative percentages.

BudgetRegret reductionBlock winsMasked minus Block: 95% interval
24H0.20%4/8[-0.00635, +0.00750]
96H3.40%7/8[+0.00484, +0.02096]
384H5.22%8/8[+0.01070, +0.02134]

The 24H/96H vectors exactly reproduce the earlier development results. The mean advantage grows at 384H, although these three budgets cannot establish a saturation limit or explain the cause of that growth.

The additional test comparisons against masked DisARM show that the size of the gain also varies by task:

Reused test splitRegret reduction, 24HRegret reduction, 96H95% paired intervals
Waterbirds4.776%14.213%Both favor Block
ACSIncome4.325%3.268%Both favor Block
Adult-0.062%2.012%Both include zero

The 384H extension is an exploratory continuation beyond the original protocol, and the test comparisons reuse the existing splits. Trajectory states are correlated development observations. Adult budget intervals use 10,000 paired-seed resamples; all intervals are pointwise 95%, conditional on the fixed task and scoring panel.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.