acceptodds
Under review as a conference paper at ICLR 2027

Shared Thresholds for Checking Descent in Discrete Robust Learning

Abstract

A training update that lowers a continuous relaxation can increase the discrete robust risk it approximates. We study how to verify a decrease in this risk while avoiding a full discrete solve at every update. For conditional value-at-risk (CVaR), the average loss in the worst-performing tail, a threshold optimized for one data subset also bounds the risk of other subsets. Sharing thresholds can therefore establish descent without solving each subset separately. We characterize how many thresholds suffice, bound the expected queries needed to find them under exact responses, and give smooth examples requiring queries proportional to the number of candidate subsets. Our algorithm, BranchCheck, first checks one stored subset and a bound over all subsets, then searches further if needed. It accounts for numerical error and uses an exact solver when the bounds remain inconclusive. Experiments cover linear predictors, fixed nonlinear features, and a network trained in all layers, with all checking costs included. On Bike Sharing with 12×12 groups, greedy checking is 1.78 and 1.94 times faster than direct dynamic programming for the linear and neural models, with identical learning paths. The first subset check and global bound provide most of the saving. Further search improves the linear result but has no clear additional benefit for the network: its value depends on whether avoided exact solves repay the search cost.

Primary area:
optimization
Keywords:
robust optimization, discrete optimization, continuous relaxation, conditional value-at-risk, descent checking, adaptive query complexity

Reviews

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

This work studies minimizing CVaR minimization for grouped data. They ask how to guarantee monotonimcally improving global error while the algorithm only saw part of the data. They study the theoretical property of using a shared threshold in CVaR for every group, and then based on the analysis, propose a branch-and-bound (BaB) algorithm that avoids checking all data through improving the global error bound. The resulting algorithm presents a computational trade-off: whether the overhead of BaB can off-balance the cost of checking all data groups to guarantee monotomic improvement.

Critical strengths

The problem seems interesting theoretically, and the final algorithm cleverly used BaB to avoid global checking. A LLM audit does not find major mistakes in the proofs.

Critical weaknesses
  1. The intuition of the problem is unclear. While the authors define the problem quite well, they do not provide any practical example about why it matters. In particular, I am not aware of settings where data must be grouped to learn CVaR thresholds, and where data is too large to be unable to get a global checking. Why not simply calculate the global CVaR loss to check improvement?

  2. The logic flow is weak in manuscript. I had a really hard time trying to understand the takeaway message for every section.

  3. The novelty is thus unclear to me based on previous 2 points. I have not been convinced about the importance of the problem, the practical relevance, and thus the importance of the resulting algorithm.

  4. This work only studies tail learning via CVaR, but in the title they claim "discrete robust learning" in general.

Questions for authors

See weakness.

5 comments
AuthorsOpenReview ↗

Author Response to Reviewer qSGU (Part 1/3)

We thank the reviewer for the comments, for checking the proofs, and for the questions on problem setup, section structure, novelty, and scope. Section, theorem, proposition, figure, and table numbers below refer to the revised PDF (10-page main text, 45 pages total).

W1 / Q1. Your summary ("while the algorithm only saw part of the data... Why not simply calculate the global CVaR loss to check improvement?") pointed to an ambiguity in our original introduction: our terms "retained subsets" and "deletion budget" made it sound as if observations were partially observed or subsampled to avoid scanning the dataset. We rewrote Sections 1 and 2.1 to clarify three points directly:

  • At step 1 of evaluating a candidate model yy, 100% of individual losses ℓi(y)\ell_i(y) across the dataset are computed. Nothing is hidden or partially observed. If the application objective were global (pooled) CVaR over the entire dataset, a single pass over all losses would indeed be the exact check (corresponding to the single-subset case ∣B∣=1|\mathcal B|=1).
  • Global pooled CVaR and grouped worst-subset CVaR are different mathematical objectives that can move in opposite directions on the exact same losses. Grouped CVaR partitions the dataset into GG pre-specified groups (such as monitoring stations and calendar months) and evaluates the worst tail average max⁡B∈BCVaRβ(B)\max_{B\in\mathcal B}\mathrm{CVaR}_\beta(B) across an admissible family B\mathcal B of group subsets (in the spirit of worst-subpopulation stress testing in Group DRO, Sagawa et al., 2020). Even on four observations, pooled CVaR and worst-group CVaR can have opposite signs on the same update (Section 1, Paragraph 1: G=2G=2 stations of 2 observations each, tail mass β=1/2\beta=1/2, k=1k=1 station per subset):
Criterion on the same 4 observationsCurrent model θ\theta: Station 1 (10,0)(10,0), Station 2 (6,6)(6,6)Candidate model yy: Station 1 (11,0)(11,0), Station 2 (4,4)(4,4)Direction of change
Global pooled CVaR1/2\mathrm{CVaR}_{1/2} (mean of top 2 of all 4 losses)(10+6)/2=8.0(10+6)/2 = 8.0(11+4)/2=7.5(11+4)/2 = 7.5Decreases (accepts yy)
Worst-station grouped CVaR1/2\mathrm{CVaR}_{1/2} (max⁡\max of the two stations)max⁡(10,6)=10.0\max(10, 6) = 10.0max⁡(11,4)=11.0\max(11, 4) = 11.0Increases (rejects yy)

The reverse disagreement also occurs in our 3×33\times 3 station–month matching example in Figure 1 and Appendix C.4 (18 observations across 9 cells, β=2/3\beta=2/3, 3!=63!=6 matchings): on the same candidate step, global pooled CVaR across all 18 observations rises from 97/24≈4.04297/24\approx 4.042 to 113/12≈9.417113/12\approx 9.417, whereas worst-matching grouped CVaR VDV_D falls from 85/8=10.62585/8=10.625 to 21/2=10.50021/2=10.500 (and the single-threshold relaxation VHV_H rises from 10.62510.625 to 10.75010.750). Checking global pooled CVaR therefore answers a different optimization question and can accept updates that worsen the worst admissible subset or reject updates that improve it.

  • Checking grouped CVaR remains computationally expensive despite known losses because finding the worst subset is a combinatorial maximization problem. Consider forecasting PM2.5 across 12 Beijing stations and 12 calendar months (420,768 raw hourly records; N=18,432N=18{,}432 risk observations in Table 2). Evaluating row-and-column matchings—retaining one cell per station and per month—tests every balanced pairing of stations and seasons without letting one anomalous station or month dominate. Computing all 18,432 losses takes milliseconds, yet there are 12!=479,001,60012! = 479{,}001{,}600 valid matchings, and each matching BB has its own optimal (1−β)(1-\beta)-quantile threshold tBt_B. Finding max⁡B∈BCVaRβ(B)\max_{B\in\mathcal B}\mathrm{CVaR}_\beta(B) via exact dynamic programming takes about 1 s per candidate check (about 101 exact solves per full-batch run, and 14.563 s per single endpoint check on a 24×2424\times 24 grid with 24!≈6.20×102324!\approx 6.20\times 10^{23} matchings in Table D.11). In full-batch training on Beijing at N=18,432N=18{,}432 (Table 2), Stage 1 bounds all 12!12! subsets via one O(n3)O(n^3) Hungarian assignment, resolving 98.0–99.8% of steps, reducing exact DP solves from about 101 to 1.4–5.0, and cutting complete training time by 3.6–10.3× (97.32 → 9.43 s on Linear, 99.79 → 13.77 s on MLP-16, 116.23 → 32.07 s on a 4,993-parameter MLP-128) with 180/180 identical parameter paths. In a separate end-to-end deployment-gate experiment (Section 5.3, Figure 3a, Table D.9), a two-hidden-layer ReLU MLP (128–64 units, 13,185 parameters) is trained freely by mini-batch SGD on 2013–2014 Beijing data and gated every 25 updates (40 checkpoints) on a fixed 2015 audit set (N=18,432N=18{,}432), keeping the deployed model on rejection without stopping SGD: unchecked deployment admits 111 verified audit-risk increases, whereas BranchCheck deploys zero increases, matches Direct DP on all 40/40 deployment sequences, and reduces fitting-plus-gating time from 49.62 ± 0.87 s to 23.25 ± 2.79 s (Stage 1 root) and 21.28 ± 1.46 s (Stage 2 Greedy 64).
AuthorsOpenReview ↗

Author Response to Reviewer qSGU (Part 2/3)

W2. We restructured the paper so each section opens with a concrete question showing how it builds on the preceding section, and ends with an explicit takeaway:

  • Section 1 defines grouped CVaR and the three subset families with domain examples, shows why pooled CVaR and single-threshold relaxations fail, motivates the check via deployment gating and monotone line search, positions prior work by pipeline stage, and previews two-stage BranchCheck.
  • Section 2 asks what must be decided and why surrogate descent fails: it explains VDV_D vs. VHV_H via subset quantiles and a 4-number example before Theorem 1, and proves the stopping-time-invariant interval test (Proposition 1). Takeaway: surrogate descent (VHV_H) cannot safely gate updates because subsets have distinct quantiles (Theorem 1; 124/3,432 violations in Figure 2a), whereas valid enclosures [L0,U0][L_0,U_0] and [L1,U1][L_1,U_1] certify discrete descent or nondecrease wherever search stops (Proposition 1).
  • Section 3 asks how cross-subset threshold sharing bounds B\mathcal B without enumeration: it proves the interval-piercing characterization of shared threshold pools (Theorem 2, Figure 1) and immediately presents two-stage BranchCheck (Algorithm 1)—Stage 1 (b=0b=0) probes one cached witness subset and bounds the entire family via one O(n3)O(n^3) assignment or top-kk selection, and Stage 2 (b>0b>0) splits B\mathcal B into subtrees when P(y,c)≥2P(y,c)\ge 2, falling back to exact DP/MILP only if unresolved. Takeaway: one subset's optimal threshold bounds all other subsets, and a small threshold pool can certify descent across n!n! branches when no single threshold suffices.
  • Section 4 asks how many queries and how much arithmetic Stage 2 requires: it bounds adaptive uniform cover discovery at O(PCln⁡(K/PC))O(P_{\mathcal C}\ln(K/P_{\mathcal C})) expected branch queries without knowing the intervals (Theorem 3), constructs smooth CVaR families forcing Ω(K)\Omega(K) endpoint calls even with unit-cost sweeps (Theorem 4), and proves explicit finite-budget tail bounds, n!n!-free polynomial tree arithmetic, and the wall-clock cost identity (Proposition 2, Equation 10). Takeaway: search is short when a small cover exists, budgets affect runtime rather than soundness, and tree search beats root-only checking precisely when avoided fallback time exceeds added assignment work.
  • Sections 5–6 follow the exact same order—surrogate violations and sub-query efficiency on 6,480 proposals (5.1, Figure 2), full-batch budget ablations and Beijing scaling (5.2, Tables 1–2), mini-batch SGD audit gating (5.3, Figure 3a), and 24×2424\times 24 grids, native unequal group sizes, and stalled-direction switching (5.4, Figure 3b)—concluding in Section 6 with an online rule driven by Stage 1 unresolved rate and per-fallback solve time.

W3. Relative to prior work on differentiable optimization layers (which supply update directions), robust objectives (which define the loss), and standard branch-and-bound (which bounds subtrees independently), our technical contribution lies in cross-subset variational threshold sharing and its finite-step complexity:

  • In standard branch-and-bound over B\mathcal B, evaluating one leaf BB yields fB(y)f_B(y) (a lower bound on max⁡B′∈BfB′(y)\max_{B'\in\mathcal B}f_{B'}(y)), which gives zero upper-bound information on disjoint subtrees. By CVaR's variational representation fB′(y)=min⁡tFB′(y,t)f_{B'}(y)=\min_t F_{B'}(y,t), a minimizing quantile threshold tBt_B from one solved subset decomposes additively over groups via wg(t)=∑i∈g[ℓi(y)−t]+w_g(t)=\sum_{i\in g}[\ell_i(y)-t]_+ to upper-bound every other subset—allowing one O(n3)O(n^3) assignment to bound all n!n! matchings (0.222 ms vs. 21.426 ms warm MILP and 14.563 s DP at n=24n=24, Table D.11). Outward-rounded floating-point bounds and upward-quantized integer assignment scores (Appendix C.5, Lemma C.1) ensure numerical error never yields a false acceptance or rejection.
  • On the theoretical side, we characterize multi-threshold certificates via Gyárfás–Lehel interval piercing (Theorem 2), prove O(PCln⁡(K/PC))O(P_{\mathcal C}\ln(K/P_{\mathcal C})) cover discovery without interval knowledge (Theorem 3) alongside explicit finite query and node-expansion budgets and a 2d2^d-branch separation between query count and node work (Proposition 2, Proposition B.3), and construct smooth CVaR instances where neither local relaxed derivatives (Theorem 1) nor unit-cost all-branch sweeps (Theorem 4) avoid Ω(K)\Omega(K) endpoint calls.
  • On the empirical side, all model, error-bound, LP, search, fallback, and refresh work is timed end to end, establishing both speedups (3.6–10.3× on Beijing full-batch, 2.33× on Beijing SGD gating, 40/40 synthetic 12×1212\times 12 Stage 2 wins, 71/80 Decision MILP wins) and clear boundaries (Stage 1 alone resolving 98–99.8% on large Beijing full-batch runs; Direct DP winning when exact solves take < 0.6 ms on 6×66\times 6 grids; and strict line-search monotonicity trading off against unchecked heldout error in Tables D.1 and D.13).
AuthorsOpenReview ↗

Author Response to Reviewer qSGU (Part 3/3)

W4. We agree that the title should match our implemented risk and experimental scope, and we changed the title from "Shared Thresholds for Checking Descent in Discrete Robust Learning" to "Shared Thresholds for Checking Descent in Grouped CVaR Learning" (synchronized in both the PDF and OpenReview metadata). Section 6 and Appendix B.8 state precisely which theoretical results extend beyond CVaR and what remains risk-specific:

  • Proposition 1 requires only valid numerical enclosures [L0,U0][L_0,U_0] and [L1,U1][L_1,U_1].
  • Theorems 2–3 and Proposition 2 require only that each branch objective t↦FB(y,t)t\mapsto F_B(y,t) is continuous, convex, coercive, and attains its minimum, with no convexity assumption on y↦ℓi(y)y\mapsto\ell_i(y) (supporting multi-layer ReLU networks). Any separable scalar-threshold risk FB(θ,t)=t+1m∑i∈Bϕ(ℓi(θ)−t)+R(θ)F_B(\theta,t)=t+\frac{1}{m}\sum_{i\in B}\phi(\ell_i(\theta)-t)+R(\theta) with convex coercive ϕ\phi (such as CVaR with ϕ(z)=[z]+/β\phi(z)=[z]_+/\beta, or entropic/buffered-tail convex ϕ\phi) also preserves additive per-group excess sums, so the O(n3)O(n^3) assignment and top-kk subtree bounds carry over structurally.
  • Instantiating the complete verifier for another risk measure requires supplying its 1D branch minimizer, forward-error numerical enclosures, and an exact fallback solver; we state this explicitly as future work rather than claiming empirical generality beyond grouped CVaR.
Reviewer_jctaOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies how to verify that a proposed training update decreases the true discrete risk, even when the update is obtained by optimizing a continuous surrogate. The surrogate risk can decrease while the true risk increases because each admissible data subset may have its own optimal CVaR threshold. The authors exploit the fact that any threshold provides an upper bound on a subset’s CVaR, allowing a threshold optimized for one subset to bound the risks of others as well. I find the paper’s central idea is interesting: it combines a discrete-risk descent check for each proposed update with shared threshold certificates across multiple subproblems, potentially avoiding a full solve of the discrete problem at every step. In some settings, this approach could substantially reduce optimization time. However, I lean toward rejection because the current presentation makes it difficult to assess the problem setup and the scope of the theoretical guarantees. A clearer exposition is needed for readers to evaluate the method’s contribution and assumptions.

Critical strengths
  • The method is interesting. The authors use CVaR thresholds to provide risk upper bounds for multiple data subsets, reducing the need to check every subset exactly. The core idea is not to accelerate the solve blindly, but to construct a certificate that verifies descent.
  • The experiments provide a fairly comprehensive comparison. They measure the complete training cost, including search and exact-solver fallback, and compare linear models, fixed-feature models, and a trainable neural network. Different methods obtain the same learning paths on most tasks; thus, the reported speedups come from checking efficiency rather than changes to the training process.
Critical weaknesses

Weakness 1: The presentation is not accessible to readers unfamiliar with the topic. Several points support this concern.

  • I had great difficulty understanding the problem the authors aim to study. The authors seem to assume too much background knowledge from the audience. They introduce many terms without sufficient explanation, such as “deletion budget,” “disjoint quotas,” and “one group per row and column of a grid.” Other concepts are also difficult to follow, including why a lower relaxed objective need not imply a lower discrete risk, grouped CVaR, and CVaR itself. It is difficult to understand the context from the introduction. After reading it, I still had no clear understanding of the problem or of how the related studies discussed in lines 39–49 differ from one another.

  • Adding an explanation of VDV_D and VHV_H, along with a concrete example, would greatly improve the paper’s accessibility. Equation (2) appears to formalize the statement in the introduction that “the relaxation uses one tail threshold for all subsets, while each subset has its own optimal threshold.” However, without defining or explaining these quantities first, it is very difficult to understand the statement.

  • Equation (4) should be presented as a theorem with a proof. Although I believe the result is correct, proving it would improve both rigor and accessibility. In its current presentation, it looks like an assumption.

Weakness 2: The query-complexity theorem (theorem 3) does not guarantee a runtime improvement for the practical algorithm.

The main threshold-discovery bound assumes exact queries, a fixed rule for selecting minimizing thresholds, and an unlimited search budget. In practice, training uses approximate numerical bounds and a finite tree-expansion budget; unresolved cases fall back to an exact solver. Therefore, the theory supports a query-count bound under specific conditions, but does not guarantee that the actual runtime will be faster. The paper also acknowledges that discovering a useful threshold and verifying a supplied set of thresholds have different costs; the distinction between “information-query bounds” and “total computational cost” could be made clearer.

Weakness 3: Experiments

  • More detailed statistics on solver fallback would be helpful. The paper reports total training time, and the appendix provides some fallback counts. However, it would be useful to report the unresolved rate, the time spent on fallback solves, and the number of exact solves avoided, broken down by dataset, model, and risk setting. This would make the practical speedups across different settings clearer, especially because the method relies on an exact solver as a fallback. Readers need to see how many exact solves are avoided and whether those savings offset the costs of threshold evaluation and tree search.

  • The experimental scale and data coverage are insufficient to support broad claims about practical applicability. The real-data experiments use only Bike Sharing and Appliances Energy, with at most 1,728 risk-relevant training observations; the neural-network experiments use a width-16 MLP. The larger-scale results are mainly from synthetic data. Thus, the current evidence demonstrates feasibility for specific matching-group problems, but does not establish stable advantages on larger datasets or more complex models. The authors should add experiments on larger-scale or more varied real datasets, or more clearly limit the scope of their claims.

Questions for authors
  1. Can the authors provide a finite-budget analysis that relates the query bound?
  2. Can the authors identify the problem regimes in which the reduction in exact-solver calls offsets the computational overhead of branch queries and tree search?
  3. Since a threshold sweep evaluates responses across all branches, how does its actual computational cost scale with the number of branches, and how does that cost compare with the unit-cost query model in the theorem?
5 comments
AuthorsOpenReview ↗

Author Response to Reviewer jcta (Part 1/5)

We thank the reviewer for the detailed comments and questions, and for noting that there are no substantive concerns about the soundness of the proofs. Every suggestion regarding problem exposition, finite-budget and approximate-response guarantees, sweep complexity, solver-fallback diagnostics, and experimental scale has been incorporated into the revised PDF (10-page main text, 45 pages total). Theorems 1–4 and Figures 1–2 retain their exact original numbering (so Theorem 3 remains the cover-discovery query bound and Theorem 4 the mixed-query lower bound), while old Equation (4) is now Proposition 1 and our new finite-budget analysis is Proposition 2.

W1. Sections 1 and 2.1 have been rewritten so all concepts, examples, and symbols are self-contained before any theorem appears:

  • Conditional value-at-risk (CVaRβ\mathrm{CVaR}_\beta) averages the largest β\beta-fraction of losses in an evaluation set. Partitioning a dataset of observed losses into GG pre-specified groups (such as monitoring stations, months, or geographic strata), grouped CVaR takes the largest (worst) CVaR across an allowed family B\mathcal B of group subsets. Section 1 defines the three constraint families with concrete domain examples before introducing notation: (i) a deletion budget drops up to G−kG-k outlier groups and retains any kk of GG groups (e.g., keeping any 4 of 6 monitoring stations); (ii) disjoint quotas retain prescribed group counts within each stratum (e.g., 2 of 3 northern stations and 2 of 3 southern stations); and (iii) row-and-column matchings on an n×nn\times n grid retain k=nk=n cells with one cell per row and one per column (e.g., pairing each station with a distinct calendar month so every subset covers all stations and seasons evenly, yielding n!n! matchings). A four-observation example in Paragraph 1 (β=1/2\beta=1/2, two groups of two observations, k=1k=1 retained group) shows that changing losses from (10,0)(10,0) and (6,6)(6,6) to (11,0)(11,0) and (4,4)(4,4) lowers pooled CVaR across all four observations (8.0→7.58.0\to 7.5) while raising worst-group CVaR (10.0→11.010.0\to 11.0).
  • Every symbol (θ\theta, ℓi(θ)\ell_i(\theta), R(θ)R(\theta), β\beta, tt, [z]+=max⁡{z,0}[z]_+=\max\lbrace z,0\rbrace) is defined prior to Equation (1). Before Equation (2), Section 2.1 explains that minimizing FB(θ,t)=t+1βm∑i∈B[ℓi(θ)−t]++R(θ)F_B(\theta,t)=t+\frac{1}{\beta m}\sum_{i\in B}[\ell_i(\theta)-t]_++R(\theta) over t∈Rt\in\mathbb R places tt at a (1−β)(1-\beta)-quantile of branch BB's losses, averaging the largest βm\beta m losses in BB (splitting boundary ties fractionally) to give fB(θ)f_B(\theta). Different subsets have different loss quantiles (e.g., calm summer stations vs. winter peak hours). Discrete risk VD(θ)=max⁡B∈Bmin⁡tFB(θ,t)V_D(\theta)=\max_{B\in\mathcal B}\min_t F_B(\theta,t) lets each subset pick its own optimal quantile tBt_B, whereas the hull relaxation VH(θ)=min⁡tmax⁡B∈BFB(θ,t)V_H(\theta)=\min_t\max_{B\in\mathcal B}F_B(\theta,t) forces all subsets to share one common threshold tt (derived by relaxing binary group indicators in the MILP to their convex hull, Appendix B.3). Right after Equation (2), we give a self-contained four-number example: let β=3/4\beta=3/4, R(θ)=0R(\theta)=0, m=2m=2 (βm=3/2\beta m=3/2), and consider two subsets with losses (0,4)(0,4) and (3,3)(3,3). On t∈[0,3]t\in[0,3], F1(t)=t+23(4−t)=83+t3F_1(t)=t+\frac23(4-t)=\frac83+\frac{t}{3} (minimized at t1=0t_1=0 with f1=8/3f_1=8/3) and F2(t)=t+43(3−t)=4−t3F_2(t)=t+\frac43(3-t)=4-\frac{t}{3} (minimized at t2=3t_2=3 with f2=3f_2=3), giving VD=max⁡(8/3,3)=3V_D=\max(8/3,3)=3, whereas max⁡(F1(t),F2(t))\max(F_1(t),F_2(t)) is minimized at their intersection t=2t=2 with VH=10/3≈3.333V_H=10/3\approx 3.333. Moving to a model where all four losses equal 3.13.1 yields VD=VH=3.1V_D=V_H=3.1: VHV_H decreases (3.333→3.1003.333\to 3.100) while VDV_D increases (3.000→3.1003.000\to 3.100).
  • Prior lines 39–49 (Section 1, Paragraph 3) are reorganized by pipeline stage: (i) differentiable optimization layers, combinatorial differentiation, and penalty/rounding methods propose update directions or discrete candidates without certifying finite-step discrete descent; (ii) group DRO, outlier-robust CVaR (DORO), interval-CVaR, and federated threshold-sharing methods specify or optimize surrogate risk objectives; and (iii) branch-and-bound supplies the bound-based stopping principle, within which we contribute cross-subset variational threshold sharing.
AuthorsOpenReview ↗

Author Response to Reviewer jcta (Part 2/5)

  • Old Equation (4) is now stated as Proposition 1 with its explicit proof: given valid enclosures L0≤VD(θ)≤U0L_0\le V_D(\theta)\le U_0 and L1≤VD(y)≤U1L_1\le V_D(y)\le U_1 (including floating-point error), margin γ≥0\gamma\ge 0, and acceptance level c=L0−γc=L_0-\gamma, if U1<cU_1<c then VD(y)≤U1<L0−γ≤VD(θ)−γV_D(y)\le U_1<L_0-\gamma\le V_D(\theta)-\gamma (ΔD<−γ\Delta_D<-\gamma), and if L1≥U0L_1\ge U_0 then VD(y)≥L1≥U0≥VD(θ)V_D(y)\ge L_1\ge U_0\ge V_D(\theta) (ΔD≥0\Delta_D\ge 0); if neither holds, the check returns unknown rather than nondecrease. With true decrease a=VD(θ)−VD(y)a=V_D(\theta)-V_D(y) and slacks ξ0=VD(θ)−L0\xi_0=V_D(\theta)-L_0, ξ1=U1−VD(y)\xi_1=U_1-V_D(y), acceptance holds iff a−γ>ξ0+ξ1a-\gamma>\xi_0+\xi_1. Section 2.1 also explains why a subset is called a branch (it forms a leaf of the search tree), defines c,tH,gH,Qb,Qs,m0,Ngen,ln⁡c, t_H, g_H, Q_b, Q_s, m_0, N_{\mathrm{gen}}, \ln before first use, and summarizes all notation in Appendix A.1.

W2. We agree that Theorem 3 bounds information queries under exact responses, fixed minimizers, and unlimited uniform sampling, rather than directly bounding the runtime of our finite-budget, floating-point implementation. Section 4.3 explicitly separates and connects these layers:

  • By Proposition 1, outward-rounded floating-point bounds and upward-quantized integer assignment scores (Appendix C.5) guarantee that every returned descent or nondecrease verdict is valid regardless of where search stops or whether nodes are popped greedily or uniformly; budgets and numerical slack affect only whether a step resolves before exact fallback (verified across 105,667 accepted full-batch updates and 2,049 gated SGD updates with zero violations). Uniform selection serves as our theoretically analyzable reference because deterministic greedy tie-breaking can require KK queries even at PC=1P_{\mathcal C}=1 (Proposition B.1), whereas greedy vs. uniform runtime is evaluated empirically.
  • Under approximate numerical bounds and suboptimal thresholds (Corollary A.1), suppose numerical shared responses satisfy FB(y,t)≤F‾B(y,t)≤FB(y,t)+ϵF_B(y,t)\le\overline F_B(y,t)\le F_B(y,t)+\epsilon, returned thresholds satisfy FB(y,tB)≤fB(y)+ζF_B(y,t_B)\le f_B(y)+\zeta, and VD(y)≤c−μV_D(y)\le c-\mu with descent margin μ>ϵ+ζ\mu>\epsilon+\zeta. Then every returned representative satisfies FB(y,tB)≤c−μ+ζ<c−ϵF_B(y,t_B)\le c-\mu+\zeta<c-\epsilon, placing tBt_B inside the tightened interval JB={t:FB(y,t)<c−ϵ}J_B=\{t:F_B(y,t)<c-\epsilon\}, while any t∈JB′t\in J_{B'} satisfies F‾B′(y,t)≤FB′(y,t)+ϵ<c\overline F_{B'}(y,t)\le F_{B'}(y,t)+\epsilon<c. Thus the Theorem 3 discovery bound carries over with PCP_{\mathcal C} replaced by the tightened cover size PϵP_\epsilon.
  • In the tree implementation, b=64b=64 caps internal node expansions, not leaf queries, and cannot be substituted as q=64q=64 into a query bound. Proposition B.3 proves why node work requires its own cap: take M=2dM=2^d single-group branches (m0=2,β=3/4,R=0m_0=2, \beta=3/4, R=0), half with losses (0,4)(0,4) (f=8/3f=8/3, IB(13/4)=(−7/4,7/4)I_B(13/4)=(-7/4,7/4)) and half with (3,3)(3,3) (f=3f=3, IB(13/4)=(9/4,13/4)I_B(13/4)=(9/4,13/4)), paired as siblings in a depth-dd binary tree with initial pool T0={0,3}T_0=\{0,3\} and c=13/4c=13/4. Here T0T_0 already resolves every leaf (K=0,Qb=0K=0, Q_b=0, cover size 2), yet every internal node contains both branch types and has single-threshold bound min⁡t∈{0,3}max⁡B∈BNFB(y,t)=min⁡{4,11/3}=11/3>13/4=c\min_{t\in\{0,3\}}\max_{B\in\mathcal B_N}F_B(y,t)=\min\{4,11/3\}=11/3>13/4=c, forcing all 2d−12^d-1 internal node expansions with zero branch queries.

W3. For per-setting solver-fallback breakdowns (W3.1), Tables 1–2 and Appendix Tables D.2, D.3, D.5, D.7, and D.8 report complete training time, pre-fallback unresolved rate (unknown checks / candidate trials), endpoint fallback count, avoided endpoint calls (candidate trials minus fallbacks), total DP calls (initialization + endpoint fallbacks + baseline refreshes), exclusive fallback DP kernel time, sharing+search time, forward/error-bound time, and LP/gradient time across datasets, models, and risk levels β∈{0.75,0.9}\beta\in\{0.75,0.9\}. Below is the complete 12-setting breakdown from Tables D.3 and D.5 (per-trajectory means; Direct DP time shown in parentheses):

AuthorsOpenReview ↗

Author Response to Reviewer jcta (Part 3/5)

Setting (Direct DP time)PolicyComplete (s)Unres. %FallbacksAvoidedAll DPFallback DP (s)Share+Search (s)Fwd/Err (s)LP/Grad (s)
Bike 6×66\times 6, Lin (0.490 s)Root / Gr.640.552 / 0.71144.0 / 14.4105.4 / 32.1103.8 / 177.1137.1 / 65.10.056 / 0.0170.032 / 0.2560.119 / 0.0940.280 / 0.279
Bike 6×66\times 6, MLP-16 (0.512 s)Root / Gr.640.535 / 0.56114.5 / 10.516.6 / 11.889.8 / 94.630.0 / 24.50.010 / 0.0070.020 / 0.0560.189 / 0.1820.276 / 0.275
Bike 12×1212\times 12, Lin (2.356 s; b=32b=32: 1.398 s)Root / Gr.641.728 / 1.49840.8 / 15.182.5 / 27.693.2 / 148.1110.4 / 56.20.945 / 0.3020.039 / 0.4830.107 / 0.0830.280 / 0.274
Bike 12×1212\times 12, MLP-16 (1.582 s)Root / Gr.640.696 / 0.7618.9 / 8.29.0 / 8.391.5 / 92.218.3 / 17.50.102 / 0.0950.024 / 0.0870.167 / 0.1690.265 / 0.271
Energy 6×66\times 6, Lin (0.133 s)Root / Gr.640.206 / 0.38252.3 / 14.8146.9 / 36.9130.6 / 242.9183.3 / 74.70.010 / 0.0030.032 / 0.2300.064 / 0.0490.059 / 0.060
Energy 6×66\times 6, MLP-16 (0.146 s)Root / Gr.640.193 / 0.26528.6 / 19.134.2 / 22.281.2 / 93.257.3 / 45.40.003 / 0.0020.018 / 0.0950.080 / 0.0750.068 / 0.068
Beijing 4.6k, Lin (8.210 s)Root / Gr.641.277 / 1.2510.6 / 0.50.6 / 0.599.4 / 99.52.1 / 2.00.047 / 0.0370.019 / 0.0210.123 / 0.1250.957 / 0.937
Beijing 4.6k, MLP-16 (8.731 s)Root / Gr.642.183 / 2.0841.8 / 1.51.8 / 1.598.2 / 98.54.1 / 4.00.140 / 0.1090.026 / 0.0340.452 / 0.4261.383 / 1.314
Beijing 4.6k, MLP-128 (11.737 s)Root / Gr.648.405 / 7.97816.9 / 14.617.8 / 15.385.1 / 87.634.2 / 31.61.482 / 1.2030.028 / 0.1883.501 / 3.3252.022 / 1.972
Beijing 18.4k, Lin (97.323 s)Root / Gr.6410.054 / 9.4340.2 / 0.20.2 / 0.299.8 / 99.81.4 / 1.40.225 / 0.2020.023 / 0.0250.537 / 0.5307.963 / 7.549
Beijing 18.4k, MLP-16 (99.789 s)Root / Gr.6413.767 / 13.8330.9 / 0.90.9 / 0.999.1 / 99.12.8 / 2.80.840 / 0.9000.027 / 0.0311.692 / 1.7349.385 / 9.310
Beijing 18.4k, MLP-128 (116.232 s)Root / Gr.6432.066 / 32.5202.0 / 2.02.0 / 2.098.0 / 98.05.0 / 5.01.937 / 1.9960.032 / 0.04311.805 / 11.86115.432 / 15.613

Stratifying by tail mass β∈{0.75,0.9}\beta\in\{0.75,0.9\} (Appendix D.3 and supplementary tables) further confirms the cost mechanism: on Bike 12×1212\times 12 linear, Stage 1 leaves about 40% open at both tail masses (42.3% at β=0.75\beta=0.75, 39.3% at β=0.9\beta=0.9), yet because our exact matching DP uses min⁡(tail count,complement count)\min(\text{tail count},\text{complement count}) states (Appendix B.7), one DP solve costs about 14 ms at β=0.75\beta=0.75 versus about 8 ms at β=0.9\beta=0.9. Consequently, Greedy 32 cuts fallback DP time from 1.323 s to 0.430 s (for 0.370 s added search) and saves 0.538 ± 0.457 s over Stage 1 at β=0.75\beta=0.75 (2.187 → 1.649 s; Direct DP 3.064 s), whereas at β=0.9\beta=0.9 it cuts fallback DP from 0.567 s to 0.213 s (for 0.285 s added search) and saves 0.120 ± 0.187 s over Stage 1 (1.268 → 1.148 s; Direct DP 1.648 s). For experimental scale and scope (W3.2), we both expanded real-data scale—adding Beijing Multi-Site Air Quality (420,768 raw records, N=4,608N=4{,}608 and 18,43218{,}432, up to 4,993-param MLP-128 with 3.6–10.3× speedups and 180/180 identical paths, Table 2), a 13,185-parameter two-hidden-layer 128–64 ReLU MLP trained by mini-batch SGD with an audit gate (49.62 ± 0.87 s → 21.28 ± 1.46 s at N=18,432N=18{,}432 with 40/40 identical deployment sequences, Section 5.3, Table D.9), endpoint replays on 16×1616\times 16–24×2424\times 24 grids (0.222 ms root vs. 21.426 ms warm MILP and 14.563 s completed DP at n=24n=24, Table D.11), and full native unequal-size Bike (8,645 rows) and Energy (11,706 rows) groups (Table D.12)—and narrowed the title and explicit scope statements in Section 6 and Appendix B.8.

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

This paper focuses on how to determine more quickly whether model updates actually reduce robust learning objectives. The proposed BRANCHCHECK algorithm reduces redundant computation during evaluation by sharing threshold information across different subsets of data. Experiments show that this method can shorten training time under certain settings while preserving the same training process.

Critical strengths
  1. The paper's methodology is clear and intuitive. By reusing some existing computational results, the efficiency of the algorithm's runtime is improved.

  2. The experimental section is clear and pragmatic. The paper demonstrates both the speedup effect of the proposed algorithm and also reports some experimental results where no advantage is observed.

Critical weaknesses
  1. To be honest, the reviewer lacks sufficient knowledge of the field. I want to further discuss the practical motivation for requiring the risk to decrease at every accepted update. More specific explanations or examples would help readers understanding.

  2. Some of the experiments reported in the paper appear to be relatively small-scale, and some of the observed speedups stemmed primarily from simple checks. Perhaps further evidence is needed to clarify when the additional search is worth its computational cost.

Questions for authors

Please refer to Weakness.

4 comments
AuthorsOpenReview ↗

Author Response to Reviewer MuPN (Part 1/3)

We thank the reviewer for the comments and questions, and for noting both the clarity of the method and our reporting of regimes where no speedup occurs. Section, theorem, proposition, figure, and table numbers below refer to the revised PDF (10-page main text, 45 pages total).

W1. In multi-environment or safety-sensitive regression (such as forecasting air pollution across monitoring stations and calendar months, or energy demand across days and hours), grouped CVaR acts as a structured stress test—evaluating the worst tail-average loss across an admissible family B\mathcal B of group subsets, such as all 12!≈4.8×10812!\approx 4.8\times 10^8 balanced station–month matchings so neither a single calm station nor a single season masks large tail errors elsewhere. When an application adopts this worst-subset risk as an update acceptance criterion, checking simpler surrogates does not enforce the rule:

  • Global pooled CVaR can move in the opposite direction (Section 1): with G=2G=2 groups of 2 observations, tail mass β=1/2\beta=1/2, and k=1k=1 retained group, changing losses from (10,0),(6,6)(10,0),(6,6) to (11,0),(4,4)(11,0),(4,4) lowers pooled CVaR from 8.0 to 7.5 while raising worst-group CVaR from 10.0 to 11.0.
  • The single-threshold continuous relaxation VHV_H can also move in the opposite direction (Section 2.1, Theorem 1, Section 5.1): because VD(θ)=max⁡B∈Bmin⁡tFB(θ,t)V_D(\theta)=\max_{B\in\mathcal B}\min_t F_B(\theta,t) lets each subset choose its own (1−β)(1-\beta)-quantile threshold tBt_B whereas VH(θ)=min⁡tmax⁡B∈BFB(θ,t)V_H(\theta)=\min_t\max_{B\in\mathcal B}F_B(\theta,t) forces one common threshold across all subsets, lowering VHV_H need not lower VDV_D. In Section 2.1 (β=3/4,R=0\beta=3/4, R=0), two subsets with losses (0,4)(0,4) and (3,3)(3,3) give branch CVaRs 8/38/3 and 33, so VD=3V_D=3, while their threshold curves cross at t=2t=2 with VH=10/3≈3.33V_H=10/3\approx 3.33; moving all four losses to 3.1 lowers VHV_H (3.33→3.103.33\to 3.10) while raising VDV_D (3.00→3.103.00\to 3.10). Theorem 1 proves this can occur smoothly even when all local relaxed values and derivatives match, and in our matched-proposal study 124 of 3,432 relaxed decreases increase VDV_D (Figure 2a).
  • Proposition 1 guarantees that any update accepted by BranchCheck strictly lowers VDV_D by more than γ\gamma under floating-point error (verified across all 105,667 accepted full-batch updates and 2,049 gated SGD updates). At the same time, we frame strict per-step descent as an operational constraint chosen by the application rather than a universal generalization method: in full-batch linear experiments (Table D.1), an unchecked baseline admits 300–620 training-risk increases while reaching lower mean heldout error. When unconstrained optimization is preferred during fitting, our deployment-gate workflow (Q1 below) enforces worst-subset improvement only at deployment checkpoints without restricting SGD steps.

W2. Beyond the 1,728-observation datasets and width-16 networks in the initial submission, the revised paper expands experimental scale across four dimensions:

  • On Beijing Multi-Site Air Quality (Section 5.2, Table 2, Appendix D.4: 420,768 raw hourly records across 12 stations, chronological train/test split, 12×1212\times 12 station–month matching grid with 12!≈4.8×10812!\approx 4.8\times 10^8 subsets), we evaluate full-batch training at N=4,608N=4{,}608 and N=18,432N=18{,}432 risk observations (10.7× the prior maximum) across Linear (38 params), MLP-16 (625 params), and MLP-128 (4,993 params):
NNModel (params)Direct DP (s)Stage 1: Probe/root (s)Stage 2: Greedy 64 (s)Speedup vs. DPUnresolved % (root / 64)DP calls (vs. ≈101\approx 101)
4,608Linear (38)8.210 ± 0.9311.277 ± 0.3751.251 ± 0.2066.56×0.6% / 0.5%2.1 / 2.0
4,608MLP-16 (625)8.731 ± 0.6882.183 ± 0.3762.084 ± 0.2184.19×1.8% / 1.5%4.1 / 4.0
4,608MLP-128 (4,993)11.737 ± 1.0538.405 ± 2.5457.978 ± 2.7151.47×16.9% / 14.6%34.2 / 31.6
18,432Linear (38)97.323 ± 0.47310.054 ± 1.5249.434 ± 1.19710.32×0.2% / 0.2%1.4 / 1.4
18,432MLP-16 (625)99.789 ± 1.91613.767 ± 2.80613.833 ± 2.0747.25×0.9% / 0.9%2.8 / 2.8
18,432MLP-128 (4,993)116.232 ± 1.72432.066 ± 4.85132.520 ± 5.7533.62×2.0% / 2.0%5.0 / 5.0
AuthorsOpenReview ↗

Author Response to Reviewer MuPN (Part 2/3)

All 180 paired comparisons on Beijing reproduce Direct DP's parameter and proposal paths identically, and speedups grow from N=4,608N=4{,}608 to N=18,432N=18{,}432 because each avoided exact DP solve rises to about 1 s.

  • In Section 5.3 (Appendix D.7), we evaluate a deeper two-hidden-layer 128–64 ReLU network (13,185 trainable parameters) trained by mini-batch SGD with periodic audit gating (Q1 below).
  • Across 180 endpoint comparisons from stored losses on 16×1616\times 16, 20×2020\times 20, and 24×2424\times 24 grids (Section 5.4, Table D.11), exact O(n2n)O(n2^n) DP rises from 0.050 s (n=16n=16) and 0.712 s (n=20n=20) to 14.563 s (n=24n=24, where 24!≈6.20×102324!\approx 6.20\times 10^{23} subsets), and warm-started complete Gurobi MILP takes 9.991 ms, 14.180 ms, and 21.426 ms; BranchCheck takes 0.481 ms (root) / 0.259 ms (Greedy 64) at n=16n=16, 0.193 ms at n=20n=20, and 0.222 ms at n=24n=24, resolving 178/180 checks at Stage 1 and 180/180 with Greedy 64 (reported as per-endpoint verification costs rather than full training runs).
  • Retaining all eligible Bike (8,645 rows, 204–248 rows/cell) and Energy (11,706 rows, 312–336 rows/cell) training observations under native unequal group sizes via our denominator-aware node bound (Section 5.4, Equation B.4, Table D.12) resolves 235/240 comparisons at Stage 1 (1.31–1.35 ms) and all 240/240 with Greedy 32 (1.14–1.18 ms vs. 9.56–11.01 ms for 720-matching enumeration).

Q1. Sections 1, 5.2, 5.3, and 5.4 detail two concrete practical workflows that apply the same BranchCheck verifier:

  • First, in an independent deployment gate alongside unconstrained mini-batch SGD (Section 5.3, Figure 3a, Tables D.9–D.10), a practitioner fits a neural network freely with mini-batch SGD while gating production deployment on a held-aside audit set so a new checkpoint replaces the deployed model only if its worst station–month tail risk on the audit set decreases. Because SGD optimizes average training loss with mini-batch noise, intermediate checkpoints frequently regress on worst-subset tail risk. We trained the 128–64 ReLU network (13,185 parameters) by mini-batch SGD (batch 256, 1,000 updates) on 2013–2014 Beijing data (189,157 rows) and gated deployment every 25 updates (40 checkpoints) on a fixed 2015 audit set (N=4,608N=4{,}608 or 18,43218{,}432), keeping the currently deployed model on rejection without rolling back or stopping SGD:
Audit NNPolicyFit + Gate (s)Gate Only (s)Accepted / 40Fallbacks (10 runs)Audit Increases Deployed
4,608Direct DP6.37 ± 0.295.76 ± 0.2833.4— (400 exact)0
4,608Stage 1 (Probe/root)5.03 ± 1.064.43 ± 1.0633.4620 (matches DP 20/20)
4,608Stage 2 (Greedy 64)4.76 ± 0.794.17 ± 0.7933.4450 (matches DP 20/20)
18,432Direct DP49.62 ± 0.8749.03 ± 0.8634.9— (400 exact)0
18,432Stage 1 (Probe/root)23.25 ± 2.7922.67 ± 2.7834.9540 (matches DP 20/20)
18,432Stage 2 (Greedy 64)21.28 ± 1.4620.69 ± 1.4634.9340 (matches DP 20/20)

Across 80 sessions, the unchecked stream deploys 111 verified audit-risk increases, whereas BranchCheck deploys zero increases, matches Direct DP's deployment sequence in all 40/40 runs, and cuts fitting-plus-gating time at N=18,432N=18{,}432 by 2.33× (49.62 → 21.28 s). This guarantees monotone risk on the fixed audit sample rather than unseen population risk (2016–2017 test MSE is 0.6724 ± 0.0213 checked vs. 0.6747 ± 0.0238 unchecked, Table D.10).

  • Second, in monotone full-batch line search along −gH(θ)-g_H(\theta) (Sections 5.2, 5.4, Figure 3b, Table D.13, Proposition D.1), strict acceptance guarantees every iterate improves VDV_D, though −gH(θ)-g_H(\theta) alone can stall after 12 halvings. In a 420-trajectory study across 60 Bike and Energy configurations, switching to a current worst-branch CVaR subgradient after 12 failed relaxed trials reduces early halts from 11/60 to 3/60 (Bike 6×66\times 6 linear: 4 → 1; Energy 6×66\times 6 linear: 5 → 2; Energy 6×66\times 6 MLP-16: 2 → 0) with all 240/240 checker pairs identical. Proposition D.1 proves that a uniquely worst branch's negative gradient decreases VDV_D for sufficiently small steps, and gives a two-group tied counterexample explaining why endpoint verification is still required.

Q2. First, Section 3.2 clarifies that Stage 1 (the probe/root check, b=0b=0) is not an external heuristic baseline—it is already our cross-subset threshold-sharing bound at budget zero, where one cached subset's optimal threshold bounds all n!n! matchings at once via a single O(n3)O(n^3) Hungarian assignment. Second, Equation (10) establishes the exact wall-clock condition for Stage 2 budgeted tree search (b>0b>0) to improve on Stage 1 (b=0b=0): fallback, refresh, and model time saved must exceed tree-search time added. Across all studies (Tables 1–2, D.2–D.9), comparing Exact Solver, Stage 1 (b=0b=0), and Stage 2 (b>0b>0) side by side delineates three regimes:

AuthorsOpenReview ↗

Author Response to Reviewer MuPN (Part 3/3)

Benchmark SettingExact SolverStage 1 (b=0b=0)Stage 2 (b>0b>0)Stage 2 vs. Stage 1 SavingGoverning Mechanism (Eq. 10)
Bike 12×1212\times 12, Linear (Table 1)2.356 s1.728 s1.398 s (b=32b=32)+0.329 ± 0.283 s40.8% open at ≈11\approx 11 ms/solve; cuts fallback DP 0.945 → 0.302 s (b=64b=64)
Bike 12×1212\times 12, RFF-128 (App. D.5)4.025 s3.220 s2.420 s (b=64b=64)+0.800 s (saves 1.606 ± 0.726 s vs. DP)Early tree closure avoids nonlinear feature and DP fallback work
Bike 12×1212\times 12, RFF-512 (App. D.5)5.010 s5.105 s3.860 s (b=64b=64)+1.245 s (saves 1.146 ± 0.317 s vs. DP)Only policy faster than DP due to costly 512-feature forward pass
Synthetic 12×1212\times 12 Grids (Table D.7)4.025 s2.935 s1.823 s (b=64b=64)+1.112 ± 0.138 s (wins 40/40)Cuts total DP calls per run from 347 (DP) and 236 (root) to 70
64-Group + Decision MILP (Table D.8)3.092 s2.779 s2.138 s (b=64b=64)+0.641 s (wins 71/80 vs. MILP)Cuts early-stopping MILP calls from 273.3 and 219.5 to 104.1
Beijing N=4,608N=4{,}608, MLP-128 (Table D.4)11.737 s8.405 s7.978 s (b=64b=64)+0.426 ± 0.633 s16.9% open; cuts fallback DP 1.482 → 1.203 s for 0.160 s search
Beijing SGD Gate N=18,432N=18{,}432 (Table D.9)49.62 s23.25 s21.28 s (b=64b=64)+1.97 s (54 → 34 fallbacks)Each avoided N=18,432N=18{,}432 DP fallback saves about 1 s
Bike 12×1212\times 12, MLP-16 (Table D.2)1.582 s0.696 s0.728 s (b=32b=32)−0.032 ± 0.014 sRoot already resolves 91.1%, leaving only 0.102 s fallback DP
Beijing N=18,432N=18{,}432, MLP-128 (Table D.4)116.232 s32.066 s32.520 s (b=64b=64)−0.454 ± 0.962 sRoot already resolves 98.0% (only 2.0 fallbacks/run remain)
Energy 6×66\times 6, Linear (Table D.2)0.133 s0.206 s0.375 s (b=32b=32)−0.169 ± 0.046 sExact DP takes 0.07 ms/solve; 110 avoided solves save only 0.007 s

Over-expanding the tree also illustrates diminishing returns: on Bike 12×1212\times 12 linear, raising bb from 32 to 256 scarcely lowers unresolved checks while adding assignment work, ending 0.363 ± 0.336 s slower than b=0b=0 (Table D.2). Because both quantities governing Equation (10)—the Stage 1 unresolved rate and the time per exact fallback solve—are directly observed online during training, Section 6 recommends running b=0b=0 by default and enabling a modest budget (b=32–64b=32\text{--}64) only when both quantities are substantial.

Thank you for your detailed rebuttal. As I mentioned in my original statements, I'm not familiar with this topic and thus gave a 1 on confidence score. I therefore would like to maintain my scorings.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General Response (Part 1/3)

We thank all three reviewers for their comments and questions. Across the reviews, three common themes emerged: (1) making the problem setup, plain-language definitions, and practical motivation self-contained early in the paper; (2) connecting the idealized query-complexity analysis to finite query and node-expansion budgets, numerical approximations, and wall-clock runtime; and (3) reporting detailed solver-fallback breakdowns and larger-scale real-data and neural-network experiments to show when each stage of BranchCheck reduces runtime and when direct exact solving remains faster. We have revised the manuscript accordingly (10-page main text, 45 pages total, consolidated Appendices A–D). Theorems 1–4 and Figures 1–2 retain their original numbering and roles, and we narrowed the title from "Shared Thresholds for Checking Descent in Discrete Robust Learning" to "Shared Thresholds for Checking Descent in Grouped CVaR Learning" to match our evaluated scope.

1. Sections 1–3 now present a self-contained problem setup, concrete worked examples, and a unified two-stage view of the verifier:

  • Paragraph 1 of Section 1 clarifies that 100% of observations and candidate losses are observed at evaluation time; the computational bottleneck is discrete maximization over an admissible family B\mathcal B of group subsets—deletion budgets (retaining any kk of GG groups), disjoint quotas (fixed counts per stratum), or row-and-column matchings on an n×nn\times n grid (one cell per row and column, giving n!n! subsets). A four-observation example ((10,0),(6,6)→(11,0),(4,4)(10,0),(6,6)\to(11,0),(4,4) at β=1/2\beta=1/2, k=1k=1 retained group) shows global pooled CVaR falling from 8.0 to 7.5 while worst-group CVaR rises from 10.0 to 11.0, illustrating why pooled CVaR cannot substitute for grouped CVaR.
  • Paragraph 2 of Section 1 motivates requiring strict grouped-risk descent in two workflows using the same verifier: (i) an independent deployment gate alongside unconstrained mini-batch SGD on held-aside audit data, and (ii) monotone full-batch line search along surrogate directions. Paragraph 3 reorganizes related work by functional stage (proposing update directions, defining robust risks, and bound-based stopping).
  • Before Equation (2), Section 2.1 explains that minimizing FB(θ,t)=t+1βm∑i∈B[ℓi(θ)−t]++R(θ)F_B(\theta,t)=t+\frac{1}{\beta m}\sum_{i\in B}[\ell_i(\theta)-t]_{+}+R(\theta) places tt at a (1−β)(1-\beta)-quantile of subset BB's losses. Discrete risk VD(θ)=max⁡B∈Bmin⁡tFB(θ,t)V_D(\theta)=\max_{B\in\mathcal B}\min_t F_B(\theta,t) lets each subset pick its own quantile tBt_B, whereas the convex-hull relaxation VH(θ)=min⁡tmax⁡B∈BFB(θ,t)V_H(\theta)=\min_t\max_{B\in\mathcal B}F_B(\theta,t) forces one common threshold across all subsets. Right after Equation (2), a four-number example (β=3/4,R=0\beta=3/4, R=0, branches (0,4)(0,4) and (3,3)(3,3)) shows VD=3V_D=3 and VH=10/3V_H=10/3 (at t=2t=2); moving all four losses to 3.1 lowers VHV_H (10/3→3.110/3\to 3.1) while raising VDV_D (3→3.13\to 3.1). Empirically, 124 of 3,432 relaxed decreases raise VDV_D in our matched-proposal study (Section 5.1, Figure 2a).
  • Old Equation (4) is stated and proved as Proposition 1: for valid enclosures L0≤VD(θ)≤U0L_0\le V_D(\theta)\le U_0 and L1≤VD(y)≤U1L_1\le V_D(y)\le U_1 (including floating-point error) and c=L0−γc=L_0-\gamma (γ≥0\gamma\ge 0), U1<c⇒ΔD<−γU_1<c\Rightarrow\Delta_D<-\gamma and L1≥U0⇒ΔD≥0L_1\ge U_0\Rightarrow\Delta_D\ge 0 at any stopping point. All notation (c,tH,gH,Qb,Qs,m0,Ngen,ln⁡c, t_H, g_H, Q_b, Q_s, m_0, N_{\mathrm{gen}}, \ln) is defined before first use and tabulated in Appendix A.1.
  • Section 3.2 (Algorithm 1) presents BranchCheck directly after the interval-cover characterization (Theorem 2, Figure 1) in two stages without enumerating B\mathcal B: Stage 1 (the root check, default b=0b=0) evaluates one cached witness subset in O(m)O(m) time and bounds B\mathcal B via additive group excess scores wg(t)=∑i∈g[ℓi(y)−t]+w_g(t)=\sum_{i\in g}[\ell_i(y)-t]_+—using top-kk selection for budgets/quotas or one O(n3)O(n^3) Hungarian assignment to bound all n!n! matchings at once; Stage 2 (optional budgeted tree search, b>0b>0) splits B\mathcal B into subfamilies when no single threshold pierces all intervals (P(y,c)≥2P(y,c)\ge 2), applying O(n3)O(n^3) subtree assignments up to bb internal expansions and calling exact DP or MILP only if unresolved.
AuthorsOpenReview ↗

General Response (Part 2/3)

2. Section 4.3 (proved in Appendix A.9) connects the query-complexity analysis (Theorems 3–4) to finite budgets, numerical approximations, and wall-clock runtime:

  • Under response overestimate ϵ\epsilon, ζ\zeta-suboptimal thresholds, and descent margin μ>ϵ+ζ\mu>\epsilon+\zeta, Corollary A.1 preserves cover discovery on tightened intervals JB={t:FB(y,t)<c−ϵ}J_B=\{t:F_B(y,t)<c-\epsilon\} of cover size PϵP_\epsilon. Proposition 2 proves that capping uniform discovery at q≥1q\ge 1 branch queries gives Emin⁡(Qb,q)≤min⁡{q,A}\mathbb E\min(Q_b,q)\le\min\{q,A\} for A=min⁡{K,2Pϵ[1+ln⁡(K/Pϵ)]}A=\min\{K,2P_\epsilon[1+\ln(K/P_\epsilon)]\}, Pr⁡(Qb>q)=0\Pr(Q_b>q)=0 for q≥Kq\ge K, and explicit tail bound Pr⁡(Qb>q)≤min⁡{1,A/(q+1),(eK/Pϵ)2Pϵ(3/4)q}\Pr(Q_b>q)\le\min\{1, A/(q+1), (eK/P_\epsilon)^{2P_\epsilon}(3/4)^q\}. Under an internal-node expansion cap b≥1b\ge 1 on a depth-hh binary tree where retaining t0∈T0t_0\in T_0 leaves K0K_0 branches open (E∞≤hK0E_\infty\le hK_0, Theorem A.2), Pr⁡(unresolved)≤min⁡{1,Pr⁡(Qb>q)+Pr⁡(E∞≥b)}\Pr(\text{unresolved})\le\min\{1,\Pr(Q_b>q)+\Pr(E_\infty\ge b)\}, with no node truncation when b>hK0b>hK_0. Proposition B.3 constructs a 2d2^d-branch CVaR family where T0T_0 resolves every leaf (K=0,Qb=0K=0, Q_b=0, cover size 2) yet single-threshold node bounds leave all 2d−12^d-1 internal nodes open, explaining why node expansions require an independent cap bb.
  • Whereas an explicit sweep over cached group scores costs O(∣B∣k)=O(n! n)O(|\mathcal B|k)=O(n!\,n) for matchings, a budget-bb tree makes qb≤b+1q_b\le b+1 leaf queries beyond q0=∣T0∣q_0=|T_0| initial thresholds and performs O((q0+qb)n2m0+(2+4b)(q0+qb)n3+qbnm0+(1+b)ln⁡(2+b))O((q_0+q_b)n^2m_0+(2+4b)(q_0+q_b)n^3+q_bnm_0+(1+b)\ln(2+b)) arithmetic operations on an n×nn\times n grid—polynomial in (n,m0,b)(n,m_0,b) and independent of n!n!. Equation (10) gives the exact wall-clock accounting identity: budget b>0b>0 beats b=0b=0 precisely when saved fallback/refresh/model time exceeds added tree-search time.

3. Section 5.2, Tables 1–2, and Appendix D.3–D.5 report full-batch training times alongside unresolved rates, fallback counts, and fallback DP times across datasets, models, and tail masses (β∈{0.75,0.9}\beta\in\{0.75,0.9\}, two-sided 95% Student intervals across seed means):

  • On Beijing Multi-Site Air Quality (420,768 raw hourly records, chronological split, 12×1212\times 12 station–month grid with 12!≈4.8×10812!\approx 4.8\times 10^8 subsets, N=4,608N=4{,}608 and 18,43218{,}432 risk observations; Linear [38 params], MLP-16 [625], and MLP-128 [4,993]), each exact DP solve at N=18,432N=18{,}432 takes about 1 s. Stage 1 resolves 98.0–99.8% of steps, reducing about 101 DP calls/run to 1.4–5.0 with 180/180 identical trajectories (Table 2, Tables D.4–D.5):
NNModel (params)Direct DP (s)Probe/root (s)Greedy 64 (s)DP / bestUnresolved % (root / 64)DP calls (root / 64)
4,608Linear (38)8.210 ± 0.9311.277 ± 0.3751.251 ± 0.2066.56×0.6% / 0.5%2.1 / 2.0
4,608MLP-16 (625)8.731 ± 0.6882.183 ± 0.3762.084 ± 0.2184.19×1.8% / 1.5%4.1 / 4.0
4,608MLP-128 (4,993)11.737 ± 1.0538.405 ± 2.5457.978 ± 2.7151.47×16.9% / 14.6%34.2 / 31.6
18,432Linear (38)97.323 ± 0.47310.054 ± 1.5249.434 ± 1.19710.32×0.2% / 0.2%1.4 / 1.4
18,432MLP-16 (625)99.789 ± 1.91613.767 ± 2.80613.833 ± 2.0747.25×0.9% / 0.9%2.8 / 2.8
18,432MLP-128 (4,993)116.232 ± 1.72432.066 ± 4.85132.520 ± 5.7533.62×2.0% / 2.0%5.0 / 5.0
  • Across all 900 paired runs in Tables 1–2, 891 match Direct DP step-for-step (the remaining 9, on Energy linear, differ in final risk by ≤8.1×10−5\le 8.1\times 10^{-5}), and all 105,667 accepted updates pass the numerical decrease test.
  • Consistent with Equation (10), Stage 2 (b>0b>0) beats both Direct DP and Stage 1 (b=0b=0) when many root checks remain open and exact fallbacks are costly: (i) Bike 12×1212\times 12 linear (Table 1, Table D.2: 40.8% open at root, fallback DP drops from 0.945 s to 0.302 s at b=64b=64, and b=32b=32 lowers total time from 1.728 s to 1.398 s vs. 2.356 s for DP, saving 0.329 ± 0.283 s over Stage 1); (ii) Bike 12×1212\times 12 nonlinear RFF-128 and RFF-512 (Appendix D.5: 4.03 → 3.22 → 2.42 s on RFF-128, saving 1.606 ± 0.726 s vs. DP, and 5.01 → 5.11 → 3.86 s on RFF-512, saving 1.146 ± 0.317 s vs. DP where Greedy is the only policy faster than DP); (iii) synthetic 12×1212\times 12 matchings (Table D.7: 2.935 → 1.823 s vs. 4.025 s DP, saving 1.112 ± 0.138 s over Stage 1 and winning in all 40/40 configurations, DP calls 347 → 236 → 70); and (iv) 64-group quota/budget families (∣B∣≤635,376|\mathcal B|\le 635{,}376, Table D.8: beating Full MILP 6.005 → 3.797 s, and beating early-stopping Decision MILP 3.092 → 2.779 s [Stage 1] → 2.138 s [Stage 2], winning in 71/80 configurations). Conversely, b=0b=0 suffices when the root settles nearly all steps (Beijing N=18,432N=18{,}432), and Direct DP is fastest when exact solves cost < 0.6 ms (6×66\times 6 grids in Table 1, or 0.235 s specialized quota DP in Table D.8).
AuthorsOpenReview ↗

General Response (Part 3/3)

4. Sections 5.3–5.4, Figure 3, and Appendix D.7–D.9 add four targeted studies examining stochastic deep-learning workflows, larger subset families, unequal group sizes, and line-search directions:

  • In our deployment-gate study alongside unconstrained mini-batch SGD (Section 5.3, Figure 3a, Tables D.9–D.10), a two-hidden-layer ReLU network (128–64 units, 13,185 parameters) is fitted freely by mini-batch SGD (batch 256, 1,000 updates) on 2013–2014 Beijing data and gated every 25 updates (40 checkpoints) on a fixed 2015 audit set, keeping the deployed model on rejection without stopping SGD:
Audit NNDirect DP (Fit + Gate)Probe/root (Fit + Gate)Greedy 64 (Fit + Gate)Fallbacks (root → 64)Audit Increases Deployed
4,6086.37 ± 0.29 s5.03 ± 1.06 s4.76 ± 0.79 s62 → 450 (vs. 111 unchecked across both NN)
18,43249.62 ± 0.87 s23.25 ± 2.79 s21.28 ± 1.46 s54 → 340 (40/40 sequences match Direct DP)

This guarantees monotone descent on the fixed audit sample rather than unseen population risk (test MSE is 0.6724 ± 0.0213 checked vs. 0.6747 ± 0.0238 unchecked, Table D.10).

  • In 180 endpoint replays starting from stored losses on 16×1616\times 16, 20×2020\times 20, and 24×2424\times 24 grids (Table D.11), Stage 1 resolves 178/180 checks and Greedy 64 resolves the remaining 2 (at n=16n=16); at n=24n=24 (24!≈6.20×102324!\approx 6.20\times 10^{23} subsets), a root check takes 0.222 ± 0.015 ms versus 21.426 ± 1.905 ms for warm-started complete Gurobi MILP and 14.563 s for completed exact DP (per-endpoint verification cost rather than full training time).
  • Retaining all eligible Bike (8,645 rows, 204–248/cell) and Energy (11,706 rows, 312–336/cell) observations under native unequal group sizes via a denominator-aware node bound (Equation B.4, Table D.12) resolves 235/240 comparisons at Stage 1 and 240/240 with Greedy 32 (1.14–1.18 ms vs. 9.56–11.01 ms for 720-matching enumeration).
  • In strict full-batch line search (Figure 3b, Table D.13, Proposition D.1), switching from −gH(θ)-g_H(\theta) to a current worst-branch subgradient after 12 failed halvings reduces early halts from 11/60 to 3/60 across 420 trajectories with 240/240 identical checker pairs, though tied worst branches can still obstruct single-branch steps (Proposition D.1) and unchecked controls can end at lower heldout risk when per-step monotonicity is not required (Table D.1).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.