{"id":"773c63f0-c6b1-47ad-8368-a7f0fee55f80","arxiv_id":"2506.06599","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"DPSM reformulates conformal training as a bilevel problem with quantile regression in the lower level and claims an O(1/sqrt n) learning bound, cutting prediction set size by about 20% in experiments.","lead":"This paper trains classifiers so their conformal prediction sets are as small as possible while keeping the promised coverage, using a bilevel optimization that learns the cutoff quantile with quantile regression. If it holds up, classifiers could give users much shorter, more practical uncertainty lists instead of overly broad answer sets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1's O(1/√n) bound applies to the exact QR minimizer q*_f, but Algorithm 1 never computes it; the paper itself leaves convergence as an open challenge, so the bound is not yet established for the implemented method.","rationale":"The reader's weakest_assumption identifies exactly the major soft spot: Theorem 4.1 is a statistical guarantee for the exact QR lower-level minimizer, while Algorithm 1 is a stochastic first-order method with no proven convergence. This is the most load-bearing concern because the paper's headline contribution is the O(1/√n) learning bound and its claimed superiority over the SA-based Ω(1/s) bound. If the implemented q-update does not converge to q*_f, then the bound is irrelevant to the method that was run, and the comparison to ConfTr/CUT is not a comparison of the claimed quantities. The paper itself flags the open challenge, which is honest but confirms the gap rather than resolving it. The empirical results are still meaningful as an engineering contribution: the algorithm does appear to converge in the reported settings, and the prediction-set-size reductions are large, especially on Caltech-101. However, those reductions do not by themselves validate the O(1/√n) claim, since the empirical comparisons involve hyperparameter selection and some dataset/score cells where DPSM is worse than baselines. The proposed concrete test (comparing final q_T to the exact minimizer and measuring the resulting APSS difference) would settle whether the theory-algorithm gap is merely formal or whether it also undermines the practical behavior. Given the explicit admission of the open challenge and the moderate confidence of the empirical claims, the CONDITIONAL verdict is appropriate; no change is needed, but the stated conditions should include a convergence analysis or an exact-minimizer ablation before the theoretical claim is accepted as applying to Algorithm 1.","tokens_in":35499,"tokens_out":6172,"duration_ms":67327,"concrete_test":"Using the released code, reproduce the CIFAR-100/DenseNet DPSM run with the reported hyperparameters. After training, compute the exact QR minimizer q*_f on the full training set (by sorting the training conformity scores or by running QR minimization to high tolerance) and compare: (i) the final QR optimization gap \\hat{L}^{QR}(f_T, q_T) - min_q \\hat{L}^{QR}(f_T, q), and (ii) the test APSS evaluated with threshold q_T versus q*_f. If the APSS difference is within, say, 1% relative, the unproven convergence is not practically consequential for the empirical claim; if the difference is substantial, the O(1/√n) learning bound demonstrably does not hold for the implementation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical claim, Theorem 4.1, bounds |\\bar{L}^{DM}_c(f) - L_c(f)| ≤ O~(1/√n) for \\bar{L}^{DM}_c(f) = \\hat{L}^{DM}_c(f, q*_f), where q*_f is an exact minimizer of the full-training-set QR loss over the scalar q. Algorithm 1, however, updates q by a single stochastic gradient step on a mini-batch pinball loss each iteration (Line 10) and never computes q*_f. The paper explicitly concedes in Section 4.2 that 'it is non-trivial and an open challenge to develop a simple stochastic gradient optimization algorithm' for this problem and leaves the convergence question to future work. Therefore the O(1/√n) bound does not transfer to the implemented method: the relevant quantity for the trained model f_T and last-iterate q_T is |\\hat{L}^{DM}_c(f_T, q_T) - L_c(f_T)|, which includes the optimization error in q. Without a convergence guarantee for q_T → q*_f, or at least a bound on |q_T - q*_f|, the claimed improvement over the SA-based Ω(1/s) bound is not established for the algorithm that produced the empirical results. The convergence plots in Figure 2 cover a single dataset/model configuration and do not substitute for a guarantee.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes DPSM, a bilevel optimization method for training deep classifiers to minimize the expected size of conformal prediction sets. The upper-level objective is a differentiable prediction-set-size loss evaluated at a quantile q of the non-conformity scores, and the lower-level problem learns q by minimizing the pinball loss on the training scores. The authors prove a learning bound of O(1/√n) for the exact lower-level minimizer q*_f, contrasting with an Ω(1/s) lower bound they derive for prior stochastic-approximation (SA) conformal training methods. They present a stochastic first-order algorithm (Algorithm 1) that alternately updates the classifier and q, and they report experiments on CIFAR-100, Caltech-101, and iNaturalist showing an average 20.46% reduction in prediction set size over the best baseline.","tokens_in":35825,"tokens_out":8550,"duration_ms":81081,"significance":"If the O(1/√n) bound were matched to the implemented algorithm, the paper would be a solid contribution to conformal training, since prior analyses degrade with batch size as O(1/√s). The bilevel formulation with quantile regression is a natural way to decouple quantile estimation from mini-batch noise, and the paper is transparent about the open optimization question, which is methodologically honest. However, the current disconnect between Theorem 4.1 and Algorithm 1 prevents the theoretical claim from supporting the method that produced the empirical results, and the empirical headline is not uniform across settings. With these issues addressed, the paper could become a valuable reference for prediction-set-efficient classifier training.","major_comments":[{"comment":"The learning bound in Theorem 4.1 applies to \\bar{L}_c^DM(f) = \\hat{L}_c^DM(f, q*_f), where q*_f is an exact minimizer of the full-training-set pinball loss. Algorithm 1 (lines 9–10) updates q by a single stochastic gradient step on a mini-batch pinball loss, and the paper explicitly states in Section 4.2 that proving convergence of such an algorithm is an open challenge left for future work. Therefore the O(1/√n) bound is not established for the implemented method; the quantity that matters for the trained f_T and last iterate q_T is |\\hat{L}_c^DM(f_T, q_T) - L_c(f_T)|, which includes the optimization error in q. In addition, the penalty-based reformulation (10) and Corollary 4.6 are not connected to Algorithm 1, since Algorithm 1 does not optimize the penalized objective. The authors should either provide a convergence guarantee for the q-updates (e.g., a bound on |q_T - q*_f|), revise the theorem to bound the actual quantity including the optimization error, or modify the algorithm to provably solve the lower-level problem.","section":"§4.2, Algorithm 1 and Theorem 4.1"},{"comment":"The lower-bound proof of Theorem 3.5 expands (\\hat{L}_c^SA(f) - L_c(f))^2 and lower-bounds the cross term 2(E[\\hat{ℓ}(f,\\hat{q}_f)] - \\hat{ℓ}(f,E[\\hat{q}_f]))(\\hat{ℓ}(f,E[\\hat{q}_f]) - ℓ(f,Q_f)) by a positive quantity using Lemma B.3. However, since \\hat{ℓ}(f,·) is μ-strongly concave (Assumption 3.2), Jensen's inequality gives \\hat{ℓ}(f,E[\\hat{q}_f]) - E[\\hat{ℓ}(f,\\hat{q}_f)] ≥ 0, so E[\\hat{ℓ}(f,\\hat{q}_f)] - \\hat{ℓ}(f,E[\\hat{q}_f]) ≤ 0. The sign of this factor is opposite to what the proof assumes, making the product with the nonnegative factor from Lemma B.4 nonpositive. As stated, the proof does not establish the claimed Ω(1/s) lower bound; it needs to control the sign of the total deviation or use a different decomposition.","section":"Appendix B.2, proof of Theorem 3.5"},{"comment":"The headline reduction of 20.46% is an average over all settings and is driven by the Caltech-101 results (e.g., 59.17% reduction for DenseNet with APS). On several settings DPSM is worse than the best baseline: CIFAR-100 DenseNet with APS is 2.64 vs 2.41 for CUT (8.71% increase), iNaturalist ResNet with APS is 79.43 vs 79.00 (0.54% increase), and additional increases appear for RAPS in Tables 5–6 (e.g., CIFAR-100 DenseNet 8.55% increase, iNaturalist ResNet 0.08% increase). The abstract's claim that DPSM 'significantly outperforms' the best baseline is therefore not supported uniformly. The authors should report per-setting improvements with statistical significance and either temper the abstract or restrict the claim to the settings where the improvement is consistent.","section":"Table 1 and Appendix F.1"}],"minor_comments":[{"comment":"The entry for iNaturalist ResNet reads '↑-0.54%', which is self-contradictory; it should be either '↑0.54%' or '-0.54%' depending on the intended meaning.","section":"Table 5"},{"comment":"There is a typo in 'Lipscthiz Hessians'; it should be 'Lipschitz Hessians'.","section":"§4.2"},{"comment":"The notation bQn f is used without a formal definition; it is introduced in the text of Figure 3 but should be defined at first use in Section 3 or the caption.","section":"Figure 3 and Appendix F.1"},{"comment":"The convergence justification is based only on CIFAR-100 with DenseNet (and ResNet in the appendix); a statement that this is a representative configuration rather than evidence for all datasets would be helpful.","section":"§5.2, Figure 2"}],"recommendation":"major_revision","confidential_remarks":"The paper is honest about the open optimization question, but this gap is load-bearing: the central theoretical claim does not cover the algorithm that produces the empirical results. The referee recommends requiring either a convergence analysis for the q-updates or a revised theorem that explicitly accounts for the optimization error. The lower-bound proof of Theorem 3.5 also appears to have a sign error that should be corrected. The empirical claims should be reported per setting, as the average 20.46% is not representative of all configurations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about this paper. First, the bilevel formulation with a quantile-regression-learned q is new and worth knowing; it cleanly decouples quantile estimation from the noisy batch-level quantiles used in ConfTr and CUT. Second, the headline theoretical claim is not established for the implemented method, and the authors admit as much in Section 4.2.\n\nWhat the paper does well: the problem formulation is sensible, and the theoretical contribution is real for the exact lower-level minimizer. Theorem 3.5 gives an Ω(1/s) lower bound for stochastic-approximation conformal training, which is a useful result in its own right. Theorem 4.1 proves O(1/√n) for |\\bar{L}^{DM}_c(f) − L_c(f)| when q is the exact QR minimizer; the proof structure (Chernoff plus Lipschitzness of the smoothed set size) is plausible. The experiments are extensive: three datasets, two architectures, three scoring functions, and the code is released.\n\nThe soft spot is load-bearing. Algorithm 1 updates q with one stochastic gradient step on a mini-batch pinball loss, and the paper explicitly says that proving convergence of such an algorithm is an open challenge left for future work. So the O(1/√n) bound does not transfer to the last-iterate quantities (f_T, q_T) that actually produced the numbers. The convergence plots in Figure 2 are for one dataset/model and are empirical heuristics, not a substitute for a guarantee. This disconnect between the theorem and the algorithm is the central issue, and it limits what the paper can claim.\n\nThe empirical headline is also shakier than the 20.46% average suggests. The average is dominated by Caltech-101, where gains are huge; on CIFAR-100 with APS, DPSM is 8.71% worse than the best baseline, and on iNaturalist with ResNet it is essentially tied. That heterogeneity is not misleading, but it tempers the claim of consistent improvement.\n\nMinor concern: the \"learning bound approximation\" in Figure 3(c) is a train-test gap, which is a reasonable proxy but not the quantity in Theorem 4.1, and it includes optimization error in a way that muddies the comparison.\n\nOverall: the core idea is good, the paper is honest about its limitations, and the experiments support the method's practical value in several settings. It deserves a serious referee round, but the referee should push for either a convergence analysis for the stochastic algorithm or a reframing of the theory as applying to the ideal bilevel solver with an empirical study of the optimization gap. I would bring it to the reading group to spark discussion, but I wouldn't cite the O(1/√n) claim in my own work yet.","headline":"A genuinely novel conformal-training formulation whose O(1/√n) theory only applies to the exact lower-level solution, not to the stochastic algorithm that actually runs.","tokens_in":36355,"tokens_out":1731,"would_cite":false,"duration_ms":20421,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that conformal prediction sets can be trained to be smaller by solving a bilevel problem that learns the quantile threshold, with an $O(1/\\sqrt{n})$ learning bound and a 20.46% average reduction in set size.","keywords":["conformal prediction","prediction set size","bilevel optimization","quantile regression","conformal training","uncertainty quantification","learning bound","mini-batch quantile"],"falsifier":"Run DPSM's Algorithm 1 at fixed batch size $s$ with increasing training sizes $n$ and measure the gap between training and test average set size (or between learned $q_t$ and the dataset-level quantile); if that gap decays like $\\tilde O(1/\\sqrt{s})$ rather than $\\tilde O(1/\\sqrt{n})$, or if $q_t$ fails to approach the dataset-level quantile, the bound does not describe the implemented method.","tokens_in":35308,"feed_emoji":"🎯","tokens_out":8592,"duration_ms":74478,"temperature":0.7,"pith_summary":"This paper tries to make conformal prediction sets smaller by training the underlying classifier for that goal, not only calibrating it afterwards. It reformulates conformal training as a bilevel optimization problem in which the upper level minimizes the average prediction-set size and the lower level learns the needed quantile of non-conformity scores by quantile regression. The paper's central theoretical claim is that this achieves a learning bound of $O(1/\\sqrt{n})$ in the number of training samples, while prior stochastic-approximation methods have a bound of at least $\\Omega(1/s)$ for batch size $s$. If the claim holds, conformal classifiers can be trained end-to-end with the same sample-complexity rate as ordinary supervised learning, and the reported experiments put the average prediction-set-size reduction at 20.46% over the best baseline.","feed_headline":"Bilevel training shrinks conformal prediction sets by 20 percent","feed_subtitle":"By learning the quantile threshold rather than estimating it from mini-batches, DPSM shrinks prediction sets by about 20 percent at the…","key_machinery":"The machine carrying the argument is a bilevel objective that couples classifier $f$ and a scalar quantile $q$. The lower level minimizes the empirical pinball loss $\\hat L_{QR}(f,q)=\\frac1n\\sum_i \\rho_\\alpha(q,S_f(X_i,Y_i))$, whose minimizer $q^*_f$ is a $(1-\\alpha)$-quantile of conformity scores; the upper level minimizes the classification loss plus the smoothed prediction-set-size loss $\\hat L_c^{DM}(f,q)$ conditioned on that $q$. Explicitly parameterizing $q$ decouples the threshold from batch randomness. The proof chain uses concentration of the empirical CDF to show $|Q_f-q^*_f|\\le \\tilde O(1/\\sqrt{n})$, Lipschitzness of the smoothed set-size loss in $q$, and a H\\\"olderian error bound for the QR loss to connect the penalized problem's solution to the original bilevel problem.","core_discovery":"On the paper's own terms, the central discovery is that conformal training does not have to estimate the quantile threshold from whatever mini-batch happens to be drawn. By making the quantile an explicit scalar $q$ and training it with the pinball loss in a lower-level subproblem while the upper level minimizes a smoothed average prediction-set size, the alignment loss becomes a function of a learned threshold. Under the paper's bi-Lipschitz assumption on conformity scores, Theorem 4.1 bounds the gap between this implicit conformal loss and the population conformal loss by $\\tilde O(1/\\sqrt{n})$ with probability at least $1-\\delta$, independent of batch size. Experiments on CIFAR-100, Caltech-101, and iNaturalist report a 20.46% average reduction in prediction set size over the best prior conformal training baseline at 90% coverage.","pith_inferences":["Extension: the theorem's exact-minimizer assumption leaves open whether the SGD-updated $q_t$ enjoys the same rate; a convergence proof for Algorithm 1 would close the gap and is the natural next step.","Extension: the same bilevel template could be applied to other conformal objectives (conditional coverage, conformal risk control) by swapping the smoothed set-size loss in the upper level while retaining the learned quantile.","Extension: if the quantile update does converge at a batch-dependent rate, DPSM's practical gain may vary with batch size in ways the current bound does not capture; measuring the training-test gap at fixed $n$ and varying $s$ would test this."],"forward_implications":["Conformal training can match the $O(1/\\sqrt{n})$ generalization rate of standard empirical risk minimization rather than the $\\Omega(1/s)$ rate of batch-quantile methods.","The learned-quantile formulation gives smaller prediction sets at the same marginal coverage: 20.46% average reduction across CIFAR-100, Caltech-101, and iNaturalist with ResNet and DenseNet at $\\alpha=0.1$.","The quantile estimation error of DPSM shrinks toward zero during training, giving a tighter empirical learning bound than ConfTr.","The method applies across HPS, APS, and RAPS scoring functions, with the largest gains on Caltech-101 and the HPS score."],"supporting_citations":[{"why":"Defines ConfTr, the stochastic-approximation baseline whose smoothed set-size loss DPSM reuses in the upper level and whose batch-quantile error DPSM aims to remove.","marker":"(Stutz et al., 2021)"},{"why":"Introduces CUT and the O(1/sqrt s) SA-based conformal training bound that Theorem 3.5 refines with an Omega(1/s) lower bound.","marker":"(Einbinder et al., 2022)"},{"why":"Defines APS, one of the conformity scores used in calibration and testing, and the WSC coverage metric.","marker":"(Romano et al., 2020)"},{"why":"Defines RAPS scoring and size-stratified coverage; RAPS is used in the calibration experiments.","marker":"(Angelopoulos et al., 2021)"},{"why":"Introduces quantile regression via pinball loss, the lower-level subproblem whose minimizer gives the learned quantile.","marker":"(Koenker & Bassett Jr, 1978)"},{"why":"Supplies the penalty-based bilevel analysis and H\\\"olderian error bound result used for Corollary 4.6.","marker":"(Chen et al., 2024b)"},{"why":"Provides the standard ERM O(1/sqrt n) generalization bound that DPSM claims to match.","marker":"(Mohri et al., 2018)"},{"why":"Gives the order-statistics derivation used for Proposition 3.4 on the distribution of mini-batch quantiles.","marker":"(Kawaguchi & Lu, 2020)"}],"fun_headline_variants":["Bilevel training shrinks conformal sets 20%","Learned quantile trims prediction set size by 20%","DPSM cuts conformal set size 20% via bilevel optimization","Train quantile, shrink conformal sets: 20% smaller","20% smaller conformal sets via bilevel quantile training"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the stochastic gradient updates in Algorithm 1 drive the scalar quantile to the exact lower-level minimizer $q^*_f$; the paper proves its $O(1/\\sqrt{n})$ bound only for that exact minimizer and leaves convergence of the implemented update as an open challenge.","fun_headline_variants_meta":{"raw":{"variants":["Bilevel training shrinks conformal sets 20%","Learned quantile trims prediction set size by 20%","DPSM cuts conformal set size 20% via bilevel optimization","Train quantile, shrink conformal sets: 20% smaller","20% smaller conformal sets via bilevel quantile training"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000531,"raw_usage":{"total_tokens":2569,"prompt_tokens":969,"completion_tokens":1600,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":585,"completion_tokens_details":{"reasoning_tokens":1510}},"tokens_in":585,"tokens_out":1600,"duration_ms":12285,"temperature":1.0,"reasoning_tokens":1510,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:53:28.893943+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DPSM's Algorithm 1 at fixed batch size $s$ with increasing training sizes $n$ and measure the gap between training and test average set size (or between learned $q_t$ and the dataset-level quantile); if that gap decays like $\\tilde O(1/\\sqrt{s})$ rather than $\\tilde O(1/\\sqrt{n})$, or if $q_t$ fails to approach the dataset-level quantile, the bound does not describe the implemented method.","supporting_citations":[{"cited_title":"and Bassett Jr, G","cited_arxiv_id":null,"evidence_quote":"Introduces quantile regression via pinball loss, the lower-level subproblem whose minimizer gives the learned quantile."},{"cited_title":"and Lu, H","cited_arxiv_id":null,"evidence_quote":"Gives the order-statistics derivation used for Proposition 3.4 on the distribution of mini-batch quantiles."}],"review_version":1}