Shared Thresholds for Checking Descent in Discrete Robust Learning

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.