{"id":"aa0ca8af-9d11-49c3-9a15-7fbfd44f4836","arxiv_id":"2412.03666","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Pessimistic bilevel optimization, which tunes hyperparameters against the worst-case inner-level model, gives more robust binary classifiers than optimistic bilevel tuning under limited or perturbed data.","lead":"This paper proposes a pessimistic way to tune machine learning hyperparameters: instead of assuming training will pick the model that best helps validation, it protects against the worst model among all models that fit the training data equally well. Experiments on small-data and shifted-data classification tasks show this pessimistic approach often achieves higher test accuracy than the standard optimistic approach.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The implemented method (24) fixes the label-flip set Vf from the optimistic solution, and Appendix B.1 validates that approximation using the same flipping operation, so the empirical gains are not yet tied to the true pessimistic bilevel objective.","rationale":"The reader's weakest assumption identifies exactly the load-bearing point: the implemented method (24) is only an approximation of the pessimistic problem, and its validation is not independent. I agree with this assessment. The formal equivalence in Theorem 3 covers 0-1 loss, but the implemented hinge-loss version fixes Vf from the optimistic solution, so the objective being optimized is not the true worst-case validation loss. Since Appendix B.1 uses the same flipping operation to compute both curves, it cannot certify the approximation. The proposed vertex-enumeration test on a small instance would directly measure the approximation gap and show whether the reported gains are attributable to pessimism or to the label-flip heuristic. I do not recommend changing the reader's conditional verdict: the paper is a plausible new application with a real computational path, but the missing gap analysis is a genuine condition for accepting the central claim.","tokens_in":21336,"tokens_out":10787,"duration_ms":114976,"concrete_test":"On the smallest configurations in Table A1 (e.g., Cancer and Diabetes with |T|=|V|=5), for each hyperparameter candidate on a coarse grid of w-bar, enumerate all vertices of the inner LP's optimal face (for epsilon=0) or its (1+epsilon)-sublevel polyhedron (for epsilon>0), and compute the exact maximum validation hinge loss over that set. Then compare the exact pessimistic objective value and argmin w-bar against the value and argmin produced by solving (24). Also evaluate the test accuracy of the model trained with the exact pessimistic w-bar. If the exact worst-case validation loss at the argmin of (24) exceeds the approximate loss by more than 5%, or if the selected w-bar or test accuracy changes materially, the Vf heuristic is not tight and the central empirical claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires that the algorithm actually solves a pessimistic bilevel problem. Section 4.2 replaces the inner maximization of the pessimistic relaxation (23) by the fixed label-flip formulation (24), with Vf determined from the optimistic hyperplane. Theorem 3's exact equivalence holds only for 0-1 loss; Corollary 4 relies on a θ-dependent partition (V1,V2,V3), but Vf is fixed before solving (24). No bound is given on the approximation gap between the true worst-case inner model and the flipped-set inner problem. This matters because if the true inner worst-case puts different points in the margin or misclassifies different points, (24) can select hyperparameters with much larger true pessimistic loss than reported. Appendix B.1 does not close this gap: to evaluate the 'optimistic under worst-case' model in (A1), it applies 'the previously mentioned flipping operation'—the same approximation being validated. Figure A1 therefore compares two instances of the heuristic rather than the heuristic against the exact pessimistic value. Appendix A adds further inconsistency: for Cancer, labels of all validation points are flipped, whereas Section 4.2 specifies flipping only misclassified and marginal points. These issues leave open the possibility that the test-accuracy gains in Figures 4-6 come from adversarial label flipping or from a particular Vf choice, not from pessimistic bilevel optimization itself.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a pessimistic bilevel optimization formulation for hyperparameter tuning in binary linear classification, in which the outer level minimizes validation hinge loss against the worst-case inner-level training solution. Following the relaxation of Zeng (2020), the authors convert the three-level problem into a min-max problem, then, for 0-1 loss, into an equivalent min-min problem via label flipping (Theorem 3). For hinge loss, they introduce a heuristic that flips the labels of a set V_f of misclassified and margin points determined from the optimistic solution, and solve the resulting bilevel linear program by a KKT-based single-level MILP. Experiments on two UCI data sets and on a CNN-extracted FashionMNIST transfer task are reported to show that pessimistic solutions outperform optimistic ones with limited training data or perturbed/shifted test data.","tokens_in":21577,"tokens_out":5613,"duration_ms":53979,"significance":"The theoretical reformulation in Theorem 3 for 0-1 loss is clean, and the paper provides a concrete, globally solvable MILP approach for the hinge-loss case. The experimental section is extensive and includes per-run tables, which is valuable for reproducibility. However, the central empirical claim of consistent superiority is contradicted by the paper's own Table A1, and the implemented method in Eq. (24) is a heuristic whose approximation gap to the true pessimistic objective is not quantified. The paper is therefore a promising step but needs substantial revision before its conclusions can be accepted.","major_comments":[{"comment":"The abstract and Section 5.1.1 state that pessimistic solutions 'consistently' outperform optimistic ones, but Table A1 contains multiple counterexamples for the Diabetes data set. For instance, with |V|=10, |T|=15 the optimistic accuracy is 0.735 versus 0.722 for pessimistic; with |V|=5, |T|=20 it is 0.728 versus 0.720; and with |V|=10, |T|=20 it is 0.739 versus 0.737. These are not within one standard deviation of each other, so the claim of consistent superiority is not supported by the paper's own results. The wording should be moderated or a proper statistical significance analysis should be provided.","section":"Section 5.1.1, Table A1"},{"comment":"The exact equivalence in Theorem 3 holds only for 0-1 loss, and Corollary 4 relies on a theta-dependent partition (V1, V2, V3). In the implemented method, however, the flip set V_f is computed once from the optimistic solution and then fixed before solving (24). No bound is given for the gap between the true worst-case inner problem in (23) and the fixed-flip approximation (24). Thus the hyperparameters returned by (24) are not established to be pessimistic solutions of (9). Appendix B.1 does not close this gap because the evaluation of the optimistic model under the worst case in (A1) uses 'the previously mentioned flipping operation'—the same heuristic being validated. A direct comparison of (24) against the exact pessimistic objective, or a bound on the approximation error, is required.","section":"Section 4.2, Eq. (24)"},{"comment":"There is a direct inconsistency in the experimental protocol. Appendix A states that for the Cancer data set, 'we have flipped the class labels of all the points in the randomly sampled validation set for each run,' whereas Section 4.2 specifies flipping only the misclassified and marginal points in V_f. This means the reported Cancer results do not correspond to the algorithm described in Section 4.2. The authors should clarify which procedure was actually used and re-run the experiments if necessary, since flipping all validation labels could be the source of the observed robustness gains.","section":"Appendix A vs. Section 4.2"},{"comment":"The claim of consistent superiority in perturbed-test experiments is also contradicted by Table A2 for Diabetes with clean validation data: at rho=0.5 the optimistic accuracy is 0.652 versus 0.647 for pessimistic, and at rho=0.6 it is 0.633 versus 0.629. The text in Section 5.1.2 already acknowledges that only epsilon <= 0.4 helps for small perturbations, but the abstract and conclusions still state a general preference for pessimistic solutions. The conclusions should be aligned with the actual performance patterns in the tables.","section":"Table A2"}],"minor_comments":[{"comment":"The heading 'Experimetns with Perturbed Data' contains a typo; it should read 'Experiments with Perturbed Data'.","section":"Section 5.1.2 heading"},{"comment":"The caption describes blue and black circles, but the text later mentions 'the blue and gray fitted surfaces.' Please harmonize the color descriptions so the figure is unambiguous.","section":"Figure 2 caption and text"},{"comment":"In Eq. (12), the notation f_{theta*}(x_i) is used inside the outer objective before theta* is defined in the following line. Please reorder the display so theta* is defined before it is used, and use a clearer notation such as f_{theta^*}(x_i).","section":"Eq. (12)"},{"comment":"Proposition 2 is stated without proof and is attributed to Zeng (2020). Since this tight relaxation is the foundation of the entire solution approach, the paper should either include a self-contained proof or state the precise conditions from Zeng (2020) under which the relaxation is tight, and verify that the SVM formulation satisfies those conditions.","section":"Proposition 2"},{"comment":"In Eq. (23), the replicated variables are denoted with hats (w_hat, b_hat, xi_hat), but in Eq. (24) the outer-level variables are also hatted while the inner-level variables are not; please make the distinction between outer replication and inner decision variables explicit to avoid confusion.","section":"Section 4.2, Eq. (23)"},{"comment":"The abbreviation PBL is used in Eq. (3) without an explicit expansion. Please expand it as 'pessimistic bilevel' at first use.","section":"Terminology"}],"recommendation":"major_revision","confidential_remarks":"The paper's core idea is interesting and the 0-1 loss equivalence is a nice result, but the implemented method is an unproven approximation and the empirical evidence is internally inconsistent. The authors should be asked to either prove or rigorously bound the approximation, fix the experimental-protocol inconsistency in Appendix A, and substantially temper the 'consistently better' claims. If the method is truly only a heuristic, the contribution becomes an engineering study of a particular label-flipping scheme, which would lower the bar for theoretical claims but could still be publishable with honest limitations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe thing to know: this is a genuine first — pessimistic bilevel optimization for hyperparameter tuning — and the theory in Theorem 3 is correct for 0-1 loss. But the method they actually implement (Eq. 24) is a heuristic, and both the theory and the experiments leave a real gap between the stated objective and what is solved.\n\nWhat's new and good: they formulate the three-level pessimistic problem, then use Zeng's relaxation to convert it to a min-max, then for binary linear classifiers with 0-1 loss they prove an exact equivalence (Theorem 3) that turns the inner max into a min over flipped labels. That's a clever and useful trick. Proposition 5's monotonicity of the ε-suboptimality value is also sound. The experiments cover limited data, perturbed test sets, and a transfer-learning setup with a CNN feature extractor. The results generally show pessimistic solutions keeping a higher floor than optimistic ones in small-data regimes, and the Appendix tables give raw numbers, which is worth credit.\n\nWhere it gets soft: the implementation switches to hinge loss and fixes the flip set Vf from the optimistic solution. That breaks the exact equivalence, and there is no bound on the approximation gap. Appendix B.1 tries to validate the heuristic, but it uses the same flipping operation to compute the 'worst-case' value, so the validation is circular. Also, the paper is internally inconsistent about what gets flipped: Section 4.2 says misclassified and marginal points, but Appendix A says they flipped all validation labels for the Cancer dataset in the small-sample experiments. That should have been caught. The empirical claim of consistent superiority is also overstated: in Table A1 several Diabetes rows show optimistic equal or better (e.g., |V|=5, |T|=10, and many rows with equal means), and there are no significance tests, no baselines like standard cross-validation or random search, and the scope is binary linear classifiers only. So the central claim is plausible but not yet proven.\n\nWho is this for: people working on bilevel optimization for AutoML or on robust hyperparameter selection. It deserves a serious referee because the formulation is novel and the 0-1 loss equivalence is a real result, but the paper needs major revision to either prove a bound on the heuristic, remove the circular validation, or temper the empirical claims.\n\nMy recommendation: send to peer review with a request for heavy revision, not a desk reject.\n\nBest.","headline":"Original application of pessimistic bilevel optimization to hyperparameter tuning, with a correct 0-1 loss reformulation but a heuristic implementation whose approximation gap is unproven and whose empirical validation is partly circular.","tokens_in":22136,"tokens_out":3187,"would_cite":false,"duration_ms":30119,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","68T05","90C31"],"pacs":[],"model":"deepseek-v4-flash","headline":"Pessimistic bilevel hyperparameter tuning, which hedges against the worst model among equally optimal training solutions, beats optimistic tuning in test accuracy under limited or shifted data, via a label-flipping relaxation.","keywords":["hyperparameter tuning","pessimistic bilevel optimization","AutoML","small-data learning","model uncertainty","support vector machines","adversarial perturbation","transfer learning"],"falsifier":"On a small synthetic dataset engineered so that the inner SVM training problem has a non-unique optimal face containing a model that misclassifies a validation point outside the optimistic solution's margin, run the proposed algorithm and also compute the true pessimistic optimum by enumerating all optimal face vertices; if the proposed solution's validation loss exceeds the true pessimistic optimum's, the $V_f$ heuristic is falsified.","tokens_in":21065,"feed_emoji":"🎛️","tokens_out":12199,"duration_ms":106254,"temperature":0.7,"pith_summary":"The paper argues that standard optimistic bilevel hyperparameter tuning—which assumes the training algorithm, among equally optimal models, will deliver the one that validates best—fails precisely in the small-data and distribution-shift regimes where tuning matters. It proposes pessimistic bilevel tuning: choose hyperparameters so that even the worst model in the inner-level optimal solution set performs well on validation data. The paper supplies a relaxation that turns this three-level problem into a tractable single-level mixed-integer program for hinge-loss support vector machines, and reports that pessimistic solutions obtain higher test accuracy than optimistic ones on two real-world datasets and in a CNN-feature transfer setting, with the largest gains at the smallest training sizes. If correct, this indicates automated machine learning should hedge against inner-level model uncertainty rather than assume cooperation from the training optimizer.","feed_headline":"Worst-case tuning beats optimistic tuning on small data","feed_subtitle":"Hedging against the worst optimal training model raises test accuracy with scarce or shifted data.","key_machinery":"The load-bearing mechanism is the tight relaxation of the three-level pessimistic problem due to Zeng (2020): replicate the inner-level variables at the outer level and add the constraint that the inner model's training loss is no worse than the replica's, converting the pessimistic problem into a bilevel min-max problem (Proposition 2). For binary classification with $0$-$1$ loss, Theorem 3 flips validation labels to turn the inner maximization into an empirical-risk minimization, giving a min-min problem. The implementation then uses hinge loss on the subset of validation points that the optimistic hyperplane misclassifies or leaves inside its margin, adds an $\\varepsilon$-relaxation of the training-loss constraint to model suboptimal training, and reduces the whole problem to a single-level mixed-integer program via Karush-Kuhn-Tucker conditions and big-M linearization.","core_discovery":"On the paper's own terms, the discovery is that pessimistic bilevel optimization for hyperparameter tuning is not merely a safer formulation but a computationally achievable and empirically superior one for binary linear classifiers. Theorem 3 shows that under $0$-$1$ loss the pessimistic min-max problem reduces exactly to a min-min empirical-risk problem by flipping validation labels, and the implemented method approximates that with hinge loss on the set of validation points that the optimistic solution misclassifies or leaves inside its margin, together with an $\\varepsilon$-relaxation of the training-loss constraint. In the reported experiments, pessimistic tuning achieves higher average test accuracy than optimistic tuning in nearly every small-data configuration—for example, on the breast-cancer dataset with 10 training and 5 validation points, $0.885$ versus $0.553$ accuracy—and keeps its edge when validation data are perturbed like the test data, and when a CNN feature extractor trained on MNIST is transferred to FashionMNIST, where it averages about $0.97$ versus $0.86$.","pith_inferences":["The label-flipping reduction is specific to binary $0$-$1$ classification; extending pessimistic tuning to multiclass or regression would require a different adversarial-validation surrogate, such as worst-case label or loss perturbations.","Because the flipped set is built from the optimistic solution, the procedure's guarantees inherit the optimistic solution's geometry; a natural variant would re-derive the flipped set from a preliminary pessimistic run and compare the resulting test accuracy.","The paper does not give a principled rule for choosing $\\varepsilon$, only monotonicity; one could select it by a second validation split, treating $\\varepsilon$ as an outer-loop hyperparameter in the same way the paper tunes the box constraint.","Part of the small-data gain may stem from the worst-case view acting as an implicit regularizer; comparing against an ordinary regularized SVM whose box bound is tuned by grid search on the same validation split would isolate the contribution of the bilevel machinery."],"forward_implications":["With limited training data, pessimistic tuning makes test accuracy largely insensitive to how the scarce data are split into training and validation sets, because it treats the inner model as uncertain rather than trusting a single optimizer's output.","When the validation set resembles the shifted or perturbed test distribution, pessimistic tuning exploits that resemblance better than optimistic tuning, as seen in the perturbed-validation and CNN transfer experiments.","The $\\varepsilon$-suboptimality parameter explicitly hedges against approximate inner-level training; by Proposition 5 the outer-level loss increases monotonically with $\\varepsilon$, so $\\varepsilon$ is a tunable robustness knob for anticipated distribution shift.","Adopting the pessimistic view in AutoML pipelines would replace the default assumption of a cooperative training solver with a worst-case hedge, at the cost of solving a larger mixed-integer program."],"supporting_citations":[{"why":"Supplies the SVM model-selection bilevel formulation with box constraints that the paper adopts as its inner training problem.","marker":"Bennett et al. (2006)"},{"why":"Extends that SVM bilevel model-selection approach and shows the KKT-based single-level reduction the paper reuses.","marker":"Kunapuli et al. (2008)"},{"why":"Introduces the optimistic/pessimistic bilevel framework and the solution-set notation the paper builds on.","marker":"Dempe (2002)"},{"why":"Documents the theoretical and computational challenges of pessimistic bilevel programming that motivate the relaxation strategy.","marker":"Dempe et al. (2014)"},{"why":"Provides the $\\varepsilon$-approximation concept for pessimistic bilevel problems that the paper generalizes.","marker":"Wiesemann et al. (2013)"},{"why":"Gives the tight relaxation converting the three-level pessimistic problem into a bilevel min-max problem, the key enabling step of the method.","marker":"Zeng (2020)"},{"why":"Supplies the real-world datasets used in the limited-data and perturbed-data experiments.","marker":"Dua and Graff (2017)"}],"fun_headline_variants":["Pessimistic tuning wins on small or noisy data","Pessimistic bilevel optimization boosts small-data accuracy","Worst-case hyperparameter tuning beats optimistic on scarce data","Relaxed pessimistic optimization improves tuning robustness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method's guarantee rests on the heuristic that flipping the labels of the points the optimistic solution misclassifies or leaves inside its margin produces a stand-in for the true worst-case inner model; the paper does not bound the error of this replacement, so a misspecified flipped set would make the obtained hyperparameters not truly pessimistic.","fun_headline_variants_meta":{"raw":{"variants":["Pessimistic tuning wins on small or noisy data","Pessimistic bilevel optimization boosts small-data accuracy","Worst-case hyperparameter tuning beats optimistic on scarce data","Relaxed pessimistic optimization improves tuning robustness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000569,"raw_usage":{"total_tokens":2697,"prompt_tokens":956,"completion_tokens":1741,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":572,"completion_tokens_details":{"reasoning_tokens":1677}},"tokens_in":572,"tokens_out":1741,"duration_ms":11677,"temperature":1.0,"reasoning_tokens":1677,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T22:13:30.307213+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small synthetic dataset engineered so that the inner SVM training problem has a non-unique optimal face containing a model that misclassifies a validation point outside the optimistic solution's margin, run the proposed algorithm and also compute the true pessimistic optimum by enumerating all optimal face vertices; if the proposed solution's validation loss exceeds the true pessimistic optimum's, the $V_f$ heuristic is falsified.","supporting_citations":[{"cited_title":"Model selection via bilevel optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the SVM model-selection bilevel formulation with box constraints that the paper adopts as its inner training problem."},{"cited_title":"Bilevel model selection for support vector machines","cited_arxiv_id":null,"evidence_quote":"Extends that SVM bilevel model-selection approach and shows the KKT-based single-level reduction the paper reuses."},{"cited_title":"Necessary optimality conditions in pessimistic bilevel programming","cited_arxiv_id":null,"evidence_quote":"Documents the theoretical and computational challenges of pessimistic bilevel programming that motivate the relaxation strategy."},{"cited_title":"Pessimistic bilevel optimization","cited_arxiv_id":null,"evidence_quote":"Provides the $\\varepsilon$-approximation concept for pessimistic bilevel problems that the paper generalizes."}],"review_version":1}