- 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
-
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?
-
The logic flow is weak in manuscript. I had a really hard time trying to understand the takeaway message for every section.
-
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.
-
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
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 vs. via subset quantiles and a 4-number example before Theorem 1, and proves the stopping-time-invariant interval test (Proposition 1). Takeaway: surrogate descent () cannot safely gate updates because subsets have distinct quantiles (Theorem 1; 124/3,432 violations in Figure 2a), whereas valid enclosures and certify discrete descent or nondecrease wherever search stops (Proposition 1).
- Section 3 asks how cross-subset threshold sharing bounds 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 () probes one cached witness subset and bounds the entire family via one assignment or top- selection, and Stage 2 () splits into subtrees when , 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 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 expected branch queries without knowing the intervals (Theorem 3), constructs smooth CVaR families forcing endpoint calls even with unit-cost sweeps (Theorem 4), and proves explicit finite-budget tail bounds, -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 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 , evaluating one leaf yields (a lower bound on ), which gives zero upper-bound information on disjoint subtrees. By CVaR's variational representation , a minimizing quantile threshold from one solved subset decomposes additively over groups via to upper-bound every other subset—allowing one assignment to bound all matchings (0.222 ms vs. 21.426 ms warm MILP and 14.563 s DP at , 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 cover discovery without interval knowledge (Theorem 3) alongside explicit finite query and node-expansion budgets and a -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 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 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 grids; and strict line-search monotonicity trading off against unchecked heldout error in Tables D.1 and D.13).
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 and .
- Theorems 2–3 and Proposition 2 require only that each branch objective is continuous, convex, coercive, and attains its minimum, with no convexity assumption on (supporting multi-layer ReLU networks). Any separable scalar-threshold risk with convex coercive (such as CVaR with , or entropic/buffered-tail convex ) also preserves additive per-group excess sums, so the assignment and top- 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.
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:
The reverse disagreement also occurs in our 3×3 station–month matching example in Figure 1 and Appendix C.4 (18 observations across 9 cells, β=2/3, 3!=6 matchings): on the same candidate step, global pooled CVaR across all 18 observations rises from 97/24≈4.042 to 113/12≈9.417, whereas worst-matching grouped CVaR VD falls from 85/8=10.625 to 21/2=10.500 (and the single-threshold relaxation VH rises from 10.625 to 10.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.