{"id":"d845afac-315a-4f72-a692-2cd747e13b28","arxiv_id":"2412.01264","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A robust optimization framework trains interpretable decision-tree surrogates for optimization problems under budgeted observation perturbations, with exact and heuristic solution methods and NP-hardness analysis.","lead":"This paper builds decision trees that map noisy cost observations to solutions of an optimization problem, protecting against worst-case perturbations of the observed parameters. It offers exact and heuristic training methods, and experiments show robust trees keep nominal quality nearly intact while performing much better when observations are disturbed.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Out-of-sample global-budget evaluation dilutes the test adversary: training uses Γglob=NΓloc with N≈5, but Table 5 reuses that same total budget on 1000 test observations, making the global test threat much weaker than the training threat and undermining the central out-of-sample claim.","rationale":"Read in good faith, the paper's substantive contribution is the RIT formulation, the scenario-generation exact method, the heuristics, and the complexity results, and the central advertised finding is the empirical trade-off statement in Section 1.4. The RIT formulation itself and the local-budget experiments are coherent, and the paper is honest about the exact method's computational limits. I focused on the empirical claim because that is what the abstract and introduction assert. The weakest point I find is not the midpoint-threshold restriction, which mainly affects the exactness claim of the SG method and can be tested separately, but the global-budget out-of-sample evaluation. Section 5.1 defines Γloc from λ and sets Γglob = N Γloc for training; Section 5.2.3 states that the same absolute budget is used on a 1000-point test set. Since Uglob is a single L1 budget over all observations, this lowers the global threat on test data by a factor of roughly N_test/N relative to training. Thus the test-table advantage of robust trees under Uglob may be a consequence of an easier test adversary, not of robust generalization. The concrete test above would settle this. If the advantage persists after rescaling, the claim survives for global uncertainty; if not, the claim should be restricted to local budgets or re-evaluated. This does not change the verdict from CONDITIONAL, because the local-budget results and in-sample results still provide partial support, but it adds a concrete required revision to the paper's central empirical statement.","tokens_in":19812,"tokens_out":21253,"duration_ms":218796,"concrete_test":"Rerun the out-of-sample evaluation in Table 5 with Γglob_test = N_test Γloc (or, equivalently, evaluate each test observation with the global budget Γglob = Γloc for N_test = 1), and recompute the scaled robust objective values for Hglob_tree, H1, and Tnom using the published code. If the negative scaled values for Hglob_tree on the test rows shrink or become positive, the out-of-sample global-budget conclusion is an artifact of budget dilution; if they persist, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the empirical finding that robust trees lose little nominal performance and improve worst-case and out-of-sample performance. The most load-bearing evidence for this claim is the out-of-sample robust evaluation in Section 5.2.3. There, the global budget is set as Γglob = N Γloc during training, where N is the number of training samples (3–10 in the experiments), and Table 5 then evaluates the same absolute Γglob on a test set of T = 1000 observations. Because Uglob is a single L1 budget across the whole set of observations, reusing the training budget on T = 1000 test points dilutes the per-observation adversary power by a factor of order T/N, here roughly 100–300. The natural analogue of the training threat for the test set is Γglob_test = T Γloc, or a per-observation evaluation with Γglob = Γloc. The reported large global out-of-sample advantages of Hglob_tree over Tnom may therefore reflect a much weaker adversary on test data rather than robust generalization. Since the conclusion explicitly claims improvement 'even on new observations that are taken out-of-sample' (Section 1.4), this mismatch is load-bearing for the central claim. In addition, no error bars or significance tests are reported for these comparisons, so it is unclear whether the remaining differences are noise.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies decision-tree surrogates for optimization problems when the observed cost parameters are subject to worst-case perturbations. The authors formulate a min-max problem (RIT) over univariate trees, introduce a global budgeted uncertainty set Uglob and a local one Uloc, and propose an exact scenario-generation MIP (master problem (1) plus adversary problem (2)/(3)), a post-processing step, and three heuristics H_tree, H_sol, H_alt, together with a single-solution baseline H1. The main theoretical results are Theorem 4.1 (large-budget regimes make H1 optimal) and Theorem 4.2 (NP-hardness of leaf-solution assignment for a fixed tree). In experiments on synthetic grid shortest-path instances, the paper compares robust trees with a nominal surrogate Tnom and reports that robust models lose little nominal performance and improve worst-case and out-of-sample performance. The code and data are made available.","tokens_in":20034,"tokens_out":11867,"duration_ms":116389,"significance":"The contribution is potentially useful: it extends the interpretable-surrogate framework of Goerigk and Hartisch to a robust setting, and the two uncertainty models plus the exact/heuristic solution methods are clearly specified. Strengths include explicit adversary formulations, a clean large-budget characterization (Theorem 4.1), a correct-looking NP-hardness reduction for LSAP, reproducible code and data, and honest reporting that the exact scenario-generation method solves few instances to optimality for larger budgets. The main caveats are that the exact method is exact only over a discrete threshold grid, and that the global-budget out-of-sample experiment dilutes the test adversary by reusing the training budget on a 1000-point test set. If these are addressed, the empirical claims about robust generalization can be evaluated properly.","major_comments":[{"comment":"The out-of-sample evaluation for the global budget reuses the training budget Gammaglob = N Gammaloc (with N = 3 to 10 training samples) on a test set of T = 1000 observations. Since Uglob is a single L1 budget across the whole set, the per-observation adversary power on the test set is smaller by a factor of order T/N, roughly 100 to 300, than on the training set. The reported advantages of H_glob_tree over Tnom on the test data therefore likely reflect a much weaker test adversary rather than robust generalization. Please re-evaluate with Gammaglob_test = T Gammaloc, or with a per-observation evaluation using Gammaloc, and report error bars or significance tests over the 20 instances.","section":"Section 5.2.3, Table 5"},{"comment":"The exact method restricts split thresholds to the finite midpoint set Theta(i), while Problem (RIT) as defined in Section 2.1 allows any threshold in the interval [min_j c_{j,i}, max_j c_{j,i}]. The robust training objective is not constant on such intervals because the adversary costs rho_j^k depend linearly on the distance from c_{j,i} to the threshold; hence the midpoint restriction is not without loss of optimality. The post-processing over the nine-point grid Pi = {0.1, ..., 0.9} only explores a finite subset of each interval and does not restore global optimality. The paper should either define the solved problem as restricted to Theta(i) and adjust the 'optimal' claims accordingly, or justify that an optimal threshold can always be found on the grid.","section":"Section 2.2, Problem (1)"},{"comment":"The comparison between SG and the heuristics is difficult to interpret because SG is not solved to optimality for most instances; Table 3 reports only counts of instances with a gap of at most 0.001, not the actual observed gaps. Since the plotted SG objective values are therefore upper bounds on the true robust optimum for these instances, the claim that H_sol performs noticeably worse than other robust methods is not fully established. Please report average optimality gaps, or mark the points in Figures 6 and 7 where the one-hour time limit was reached.","section":"Section 5.2.2, Table 3 and Figures 6-7"}],"minor_comments":[{"comment":"The reduction starts from a partition problem with the additional constraint p = n/2, but the standard Partition problem does not constrain cardinality. Please state the cardinality-constrained variant explicitly and justify its NP-completeness, or give a short reduction from the unconstrained variant.","section":"Section 4.2, Theorem 4.2"},{"comment":"No error bars or significance tests are reported for any of the numerical comparisons beyond averaging over 20 instances. Adding standard errors, especially for the out-of-sample rows in Tables 4 and 5, would make the relative rankings much more informative.","section":"Section 5.1, Tables 4 and 5"},{"comment":"The big-M values M^j are defined as max_{x in X} c_j^T x or any upper bound; this assumes bounded X or a known finite upper bound. For the shortest-path experiments this is fine, but the text should state the boundedness assumption explicitly.","section":"Section 2.2, Constraint (1h)"},{"comment":"The proof's equality/inequality chain would benefit from one sentence explaining why, under the stated budgets, the adversary can simultaneously send every sample to any leaf, rather than only each sample individually.","section":"Section 4.1, Theorem 4.1"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the journal's scope and I do not see a circularity problem: the robust formulation, the two adversary models, and the complexity results are new even though the starting point is the authors' own GH23 framework. The main fixable issue is the budget mismatch in the out-of-sample global evaluation; the threshold-grid issue will require either a scope restriction or a proof that the grid is sufficient. The NP-hardness proof should cite the cardinality-constrained partition variant."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague —\n\nWorth a look: the authors extend the interpretable-surrogate framework (GH23) by adding robustness to budgeted perturbation of observed cost parameters. The formulation is clean: a min-max problem over observation perturbations under global and local L1 budgets, solved by an iterative scenario-generation method whose adversary is a multiple-choice knapsack, plus three heuristics and two sensible complexity results. Theorem 4.1 (large budget collapses RIT to the single-solution problem) is correct and useful; Theorem 4.2 (NP-hardness of the leaf-solution assignment with Γ=1) looks sound. The code is on GitHub, which is genuinely helpful.\n\nThe main empirical claim — robust trees lose little nominal performance and gain on disturbed and out-of-sample data — is supported in-sample, but the out-of-sample global-budget comparison is flawed. Training sets Γglob = NΓloc with N between 3 and 10; the test evaluation then reuses that same absolute Γglob on 1000 test observations. Because Uglob is one global L1 budget over the whole dataset, that makes the test adversary 100–300 times weaker per observation. The natural test analogue is Γglob = TΓloc, or per-observation evaluation. So the Hglob_tree vs. Tnom advantage in the Table 5 test rows mostly reflects a diluted adversary, not robust generalization. I checked Section 5.2.3 and the tables: the paper explicitly says the same absolute budget was used; the stress-test note is right.\n\nOther soft spots, in proportion: no error bars or significance tests anywhere, so some differences in Tables 4–5 could be noise. The exact method solves almost nothing for λ ≥ 0.05 on Uglob (Table 3), so the practical evidence rests on Htree; that is fine for a heuristic paper, but it should be stated that the \"optimal\" method is basically not solving the real instances. And the threshold grid restriction to midpoints plus a 9-point post-hoc search is a real limitation; I would like the paper to say outright that optimality is only within that grid.\n\nWhat is genuinely good: the adversary knapsack formulations, the NP-hardness proof, and the local-budget results, which do not suffer from the test-budget mismatch and show robust gains out-of-sample (Table 5, e.g., -6 to -8% for Hloc_tree vs. nominal). That part of the central claim survives.\n\nRecommendation: send it to a serious referee, but expect a major revision. The experimental protocol needs fixing (scale the test budget, add error bars or tests), and the threshold-grid limitation should be discussed head-on.","headline":"Solid robust-optimization extension of interpretable surrogates, but the out-of-sample global-budget comparison is weakened by a test/training budget mismatch and needs fixing before the headline claim is trusted.","tokens_in":20589,"tokens_out":3643,"would_cite":true,"duration_ms":32059,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C11","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Training a small decision tree that maps observed costs to solutions, under worst-case budgeted perturbations of those observations, gives surrogates that keep most of their nominal quality while performing much better on noisy and…","keywords":["data-driven optimization","interpretability and explainability in optimization","robust optimization","decision trees","budgeted uncertainty","surrogate optimization","scenario generation","min-max optimization"],"falsifier":"Take any training instance, solve the robust tree problem with the midpoint grid, then search each chosen split interval on a fine continuous grid; if a single threshold outside the midpoint set lowers the worst-case cost, the method's optimality claim fails. On the empirical side, an out-of-sample dataset containing real measurement noise would be the test: the paper's claim predicts the robust tree achieves lower average cost than the nominally trained tree at small nominal loss.","tokens_in":19565,"feed_emoji":"🌳","tokens_out":10490,"duration_ms":86872,"temperature":0.7,"pith_summary":"This paper asks whether a decision tree that maps observed cost data to solutions of an optimization problem can be made robust to measurement errors and still stay interpretable. It formalizes the task as choosing a tree that minimizes the worst-case total cost when an adversary perturbs each training observation within a budgeted uncertainty set. The authors design an exact scenario-generation method plus several heuristics and test them on shortest-path instances. Their central finding is that robust trees cost only a small loss in nominal, unperturbed performance, while improving worst-case performance on disturbed observations and also performing better on out-of-sample data. Accepting this claim would make interpretable surrogates usable in settings where input data are known to be unreliable.","feed_headline":"Robust trees survive noisy data for under 2% nominal loss","feed_subtitle":"Worst-case-aware training cuts robust costs by up to ~15% and generalizes better, with little nominal trade-off.","key_machinery":"The central object is the robust decision-tree surrogate: a univariate, bounded-depth tree whose internal nodes each test one cost coefficient against a threshold and whose leaves contain feasible solutions of the underlying optimization problem. The argument is carried by the robust interpretable tree (RIT) formulation, whose objective is the worst-case sum over training samples under a budgeted $\\ell^1$ perturbation set, either global $U_{\\text{glob}}$ (one budget for all perturbations) or local $U_{\\text{loc}}$ (a budget per sample). The exact method alternates a flow-based mixed-integer master problem, restricted to split thresholds at midpoints of sorted training values, with an adversary problem that maximizes cost by assigning samples to leaves; the adversary problem is a multiple-choice knapsack. Heuristics split the joint tree-structure and leaf-solution decision by fixing one side and optimizing the other, alternating between the two until convergence.","core_discovery":"On the paper's own terms, the central claim is that the min-max problem of finding a robust interpretable decision tree, $\\min_{T} \\max_{\\xi \\in U} \\sum_j c_j^\\top T(c_j+\\xi_j)$, is tractable enough in practice to be worth solving: exact scenario generation works for small instances, and a heuristic that fixes the tree structure and then optimizes the leaf solutions finds good surrogates quickly. The experiments show that the price of robustness is low—robust trees are within roughly two percent of the nominal tree's training objective—while their worst-case in-sample objective improves by up to about sixteen percent, and on out-of-sample data robust trees beat the nominal tree even when no perturbations are applied. The paper also establishes that with sufficiently large perturbation budgets a single-solution tree is optimal, and that assigning optimal solutions to the leaves of a fixed tree is NP-hard even for a simple selection problem with a unit budget.","pith_inferences":["The restriction of split thresholds to midpoints of sorted training values may make the reported robust optima conservative; solving the same min-max problem with continuous thresholds could find trees with even smaller nominal loss or better worst-case cost, an improvement the paper does not claim.","The out-of-sample gains in unperturbed settings suggest that robust training is implicitly regularizing the tree, which connects this work to structural-risk arguments without the paper drawing that link.","Because local-budget uncertainty is easier to optimize and strongly correlated with the global set, a practitioner could estimate per-observation budgets from historical measurement residuals and train under $U_{\\text{loc}}$ alone, an extension the paper lists as future work."],"forward_implications":["A robustly trained tree loses less than about two percent of nominal in-sample performance while improving worst-case in-sample cost by roughly nine to sixteen percent over a nominally trained tree, so robustness does not require sacrificing much everyday quality.","Trees trained for robustness beat the nominally trained tree on out-of-sample test data even when the test data are unperturbed, and the advantage grows with instance size, so robust training appears to act as a regularizer.","Whenever the perturbation budget exceeds $D\\cdot N\\cdot M$ (global) or $D\\cdot M$ (local), a single fixed solution is provably optimal, so large uncertainty budgets make deep trees unnecessary.","Even fixing the tree structure and choosing leaf solutions optimally is NP-hard for the selection problem, so the heuristic decomposition into tree-building and solution-assignment steps is justified.","Worst-case performance under the global and local budgeted uncertainty sets is strongly correlated, so the cheaper local-budget model can serve as a practical proxy for the global model."],"supporting_citations":[{"why":"Defines the inherently interpretable optimization framework and the nominal decision-tree surrogate that this work extends.","marker":"[GH23]"},{"why":"Introduces budgeted uncertainty sets, the basis for the global and local perturbation budgets used throughout.","marker":"[BS04]"},{"why":"Surveys min-max and min-max regret optimization, motivating the worst-case objective and scenario-generation approach.","marker":"[ABV09]"},{"why":"Provides the column-and-constraint generation scheme used for the iterative master-adversary solution loop.","marker":"[ZZ13]"},{"why":"Supplies the flow-based mixed-integer formulation for decision trees used in the master problem.","marker":"[JAGV22]"},{"why":"Establishes NP-hardness of constructing optimal binary decision trees, justifying the MIP and heuristic methods.","marker":"[LR76]"},{"why":"Documents the multiple-choice knapsack problem used to model the adversary's worst-case leaf assignment.","marker":"[KPP04]"},{"why":"Provides the partition problem used in the NP-hardness reduction for the leaf-solution assignment problem.","marker":"[GJ79]"}],"fun_headline_variants":["Robust decision trees: near-zero nominal loss, big worst-case gains","Worst-case-aware trees: less than 2% nominal sacrifice","Robust interpretable trees: tiny nominal cost, solid worst-case","Exact and heuristic robust trees beat nominal on unseen data","Robust surrogate trees: 2% nominal loss, up to 16% worst-case gain"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exact method proves optimality only among trees whose split thresholds are midpoints between sorted training values, so the true best robust tree might use a threshold the model never offers.","fun_headline_variants_meta":{"raw":{"variants":["Robust decision trees: near-zero nominal loss, big worst-case gains","Worst-case-aware trees: less than 2% nominal sacrifice","Robust interpretable trees: tiny nominal cost, solid worst-case","Exact and heuristic robust trees beat nominal on unseen data","Robust surrogate trees: 2% nominal loss, up to 16% worst-case gain"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000758,"raw_usage":{"total_tokens":3334,"prompt_tokens":874,"completion_tokens":2460,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":2364}},"tokens_in":490,"tokens_out":2460,"duration_ms":16771,"temperature":1.0,"reasoning_tokens":2364,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T04:31:55.580886+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any training instance, solve the robust tree problem with the midpoint grid, then search each chosen split interval on a fine continuous grid; if a single threshold outside the midpoint set lowers the worst-case cost, the method's optimality claim fails. On the empirical side, an out-of-sample dataset containing real measurement noise would be the test: the paper's claim predicts the robust tree achieves lower average cost than the nominally trained tree at small nominal loss.","supporting_citations":[],"review_version":1}