{"id":"b54d9f7f-30d9-4eec-8889-a2767dbea8f1","arxiv_id":"2607.13550","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A modified gradient-boosting algorithm trains one univariate weak learner per iteration for all output targets, giving similar accuracy to XGBoost for multiple quantile regression while cutting runtime by up to roughly 50x.","lead":"This paper introduces a way to speed up gradient boosting when predicting many outputs at once, such as many quantiles of a distribution, by training only one simple model per step instead of one per output. That makes full conditional-distribution prediction practical on ordinary hardware, with accuracy comparable to standard boosted trees but at a fraction of the compute cost.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's K-smoothness requirement excludes the pinball loss used in the paper's core application, leaving the main convergence claim unsupported for the deployed method; the approximate tree-fitting objective widens this disconnect.","rationale":"The paper is transparent about the pinball loss not satisfying the smoothness assumptions, and it does not claim the theorem covers pinball. The reader's conditional verdict already reflects this: the theoretical guarantee is sound but narrow, and the main application rests on empirical evidence. The approximate tree-fitting objective is also acknowledged in Section 4.2, but it means the implemented algorithm is further from the theorem's assumptions. These are scope/limitation concerns rather than internal inconsistencies or fatal flaws, so they do not change the verdict. The proposed experiment would test whether the gap is practically material, which is the appropriate next step before full acceptance.","tokens_in":33583,"tokens_out":12381,"duration_ms":145179,"concrete_test":"Construct a small dataset and take as base learners all stumps on a fixed grid; compute the exact minimum empirical risk over span(h_w)^M by enumeration. Run the released PGB implementation with pinball loss (M=2 quantiles) and record Rhat_n(g_t) over 10^4 iterations. Repeat using a K-smooth surrogate (e.g., Huberized pinball) and also with an oracle weak learner that solves Eq (5) exactly. If the pinball/RSS combination fails to approach the enumerated minimum while the smooth/exact combination does, the concern is confirmed; if all variants converge to the same optimum, the missing smoothness and exact-fit assumptions are not the binding limitation in practice.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5.1 states that pinball loss 'does not meet the usual assumptions that are used in proofs of convergence of gradient boosting (besides being non-differentiable at 0, it notably lacks the K-smoothness property)', and Theorem 3 requires Assumption 6: each loss component is convex and K-smooth. The central application is multiple quantile regression with pinball loss, so the headline convergence guarantee 'lim Rhat_n(g_t) = Rhat_n(g*)' does not apply to the loss used in the paper's main experiments (Sections 5.1, 6). Consequently, the claim that PGB 'reaches the best empirical risk over the span of its base models' is not established for the actual loss used; the empirical speed/quality results carry that weight alone. A second, compounding gap is that Section 4.2 implements trees by minimizing residual sum of squares, an approximate proxy for the exact Eq (5) minimization that Theorem 3 assumes; even under smooth losses the shipped algorithm differs from the analyzed one. Neither gap makes Theorem 3 false, but together they mean the central claim is conditional on an idealized version of the procedure rather than the deployed one.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Parallel Gradient Boosting (PGB), a multi-output boosting procedure that trains a single univariate base learner per iteration by projecting the gradient onto a coordinate direction and then performing a multidimensional line search. The main theoretical result, Theorem 3 (Section 4.1), states that, under separability, convexity and K-smoothness of the loss, symmetry and boundedness of the base models, and per-coordinate compactness, the empirical risk of PGB converges to the minimum attainable over the linear span of the induced multi-output base models. The paper applies PGB to multiple quantile regression with the pinball loss and to conditional density estimation via quantile interpolation and kernel smoothing. Empirically, PGB is reported to match XGBoost in quantile-regression quality while being orders of magnitude faster, and to outperform or match DRF, FlexCode, and LinCDE on simulated and real medical data, with repeated trials and standard deviations reported. Code and an R package are provided.","tokens_in":33955,"tokens_out":6930,"duration_ms":85683,"significance":"If the results hold, PGB is a valuable contribution: it attacks a genuine computational bottleneck of multi-output boosting (one weak learner per target per iteration) with a simple, general construction that does not require specialized base learners. The proof strategy is transparent and the appendix is self-contained; Theorem 3 follows from separability and Corollary 1, and the coordinate-cycling argument is sound. The empirical study is more careful than typical for a methods paper: repeated runs, standard deviations, and comparisons on diverse real datasets. However, the main convergence theorem uses assumptions that exclude the pinball loss on which the paper's central application rests, and the implemented tree-fitting step solves an approximate objective rather than the exact weak-learner problem assumed by the theorem. These gaps mean the headline convergence guarantee currently applies to an idealized version of the procedure, not to the deployed algorithm. The paper's practical speed and quality claims still stand on the experiments, but the theoretical support for the main use case is weaker than the presentation suggests.","major_comments":[{"comment":"The central convergence result does not cover the loss used in the paper's main application. Theorem 3 requires Assumption 6, which says each elementary loss ℓ_m is convex and K-smooth in its second argument. Section 5.1 explicitly states that the pinball loss “does not meet the usual assumptions that are used in proofs of convergence of gradient boosting (besides being non-differentiable at 0, it notably lacks the K-smoothness property).” Since the multiple-quantile-regression experiments in Sections 5.1 and 6 minimize the pinball/WIS loss, the claim lim_{t→∞} R̂_n(g_t)=R̂_n(g*) is not established for the deployed method. The paper should either extend the convergence analysis to nonsmooth convex losses (e.g., via subgradient arguments or smoothing), prove a separate guarantee for the pinball case, or explicitly reframe Theorem 3 as applying only to smooth losses and remove the implicat","section":"§5.1, Theorem 3 (Assumption 6)"},{"comment":"The analyzed algorithm differs from the implemented algorithm in a load-bearing way. Theorem 3 assumes that w_t solves Eq. (5) exactly and that γ_t is a global minimizer of R̂_n(g_{t-1}+h_{w_t}γ). Section 4.2 states that the actual tree fitting minimizes the residual sum of squares ∑(-a_i-h_w(x_i))², which is an approximate proxy for Eq. (5), and that the implementation uses leaf-wise line search. For such approximate weak-learner fits, the update is not guaranteed to give the non-increasing empirical risk that Corollary 1 needs for intermediate steps. Thus even for smooth losses, the proof does not apply to the shipped algorithm. Please state the approximation explicitly, give conditions under which it preserves the descent property, or present Theorem 3 as a result for the exact procedure and provide separate theoretical or empirical justification for the approximation gap.","section":"§4.2, Eq. (5)"}],"minor_comments":[{"comment":"The algorithm box lists a 'differentiable and separable loss function' as input, but the paper's main experiments use the non-differentiable pinball loss. The surrounding text discusses this, but the box should be made consistent, e.g., by using 'suitable separable loss' and noting that nondifferentiable cases are handled in Section 5.1.","section":"Algorithm 1"},{"comment":"The caption says quantile crossing is plotted in red, and the text states that 'more than half of the quantiles are affected' with XGBoost. Please report the exact counts or proportions, and state the number of quantile levels used, to make the comparison reproducible and precise.","section":"Figure 3"},{"comment":"The text says PGB and LinCDE 'perform significantly better' than DRF and FlexCode, and PGB is 'best-performing' in each scenario. Given that the reported error bars overlap in some settings and no formal significance tests are provided, the wording is stronger than the evidence. Add pairwise tests or phrase the conclusions more cautiously.","section":"§6.1, Figure 7"},{"comment":"The scaling formula for F_scaled mixes a condition on the raw c.d.f. taking values in {0,1} with a piecewise rescaling of the interior. Please clarify how the tails are handled before convolution: the text says the resulting p.d.f. is supported on a compact set and then smoothed with a Laplacian kernel, but the exact role of the {0,1} condition in making the c.d.f. absolutely continuous is not fully explained.","section":"§5.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is promising and the theorem appears sound in its own terms, but the mismatch between Assumption 6 and the pinball loss used in the central application is a real gap, as is the discrepancy between the exact weak-learner oracle assumed by Theorem 3 and the approximate RSS-based tree fitting in Section 4.2. These are not fatal—there are credible paths involving smoothing/subgradient analysis or a careful reframing of the claims—but they need to be addressed before the paper can be accepted. I would not reject on these grounds alone; the empirical work and the general PGB idea are solid contributions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. This is a genuine algorithmic contribution: PGB generalizes the one-tree-per-iteration projection trick from SketchBoost and Joly et al. to arbitrary base learners, and the paper delivers a real convergence theorem for smooth separable losses. The authors are also honest that the trick is not new, and they give a proper derivation. The empirical study is solid: repeated runs, standard deviations, and a convincing speedup over XGBoost for multiple quantile regression. The conditional density application is a natural addition.\n\nThe soft spots are the ones you flagged. Theorem 3 requires K-smoothness, and the pinball loss explicitly fails that. So the headline convergence guarantee does not cover the exact loss used in the central application. The paper says this itself, but it means the practical claim that PGB 'reaches the best empirical risk' is not supported for the deployed loss. The empirical results carry that weight. Second, the implementation fits trees by residual sum of squares, not the exact minimization in Equation (5). That is standard in boosting, but it widens the gap between the analyzed algorithm and the shipped one. Neither gap makes the theorem false, but they should be stated more prominently.\n\nI would also push the authors to include a SketchBoost baseline in the speed comparison. Since SketchBoost is the closest multi-output tree method, its absence makes the 'state-of-the-art' claim a bit softer than it could be.\n\nOverall, this paper deserves peer review. The theory is narrow but correct, the empirical work is careful, and the code is available. I would recommend a conditional accept, with the requirement that the authors be explicit about the gap between the convergence theorem and the pinball application, and ideally add the SketchBoost comparison. I'd bring it to a reading group.","headline":"Genuine algorithmic contribution with an honest but narrow convergence theorem; the practical claims rest on the empirical study, and the paper deserves peer review.","tokens_in":34355,"tokens_out":2106,"would_cite":true,"duration_ms":23597,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G08","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Parallel gradient boosting trains all output targets with a single shared descent direction and one base model per iteration, proving convergence to the optimal empirical risk while making conditional distribution estimation via multiple qu","keywords":["parallel gradient boosting","multi-output regression","multiple quantile regression","conditional distribution estimation","gradient boosting convergence","pinball loss","nonparametric conditional density"],"falsifier":"On a simulated dataset with known conditional quantiles, set the base-learner class to stumps and compute the minimum possible weighted interval score over all linear combinations of stumps via linear programming. If PGB with the pinball loss fails to approach that minimum after a very large number of iterations, with the gap remaining non-negligible, then the practical algorithm does not deliver the convergence that Theorem 3 would require, exposing the mismatch between the smooth-loss theory and the pinball application.","tokens_in":1391,"feed_emoji":"⚡","tokens_out":1936,"duration_ms":75399,"temperature":0.7,"pith_summary":"The paper introduces parallel gradient boosting (PGB), a multi-output variant of gradient boosting in which a single univariate base model is trained per iteration and then scaled by a shared direction vector, so the number of targets no longer multiplies the training cost. The central theoretical result is that, for separable losses whose components are convex and smooth, PGB converges in empirical risk to the best predictor in the span of its base models—matching the guarantee of classical multi-output boosting while using only one weak-learner call per step. The authors apply PGB to multiple quantile regression, where training time scales almost independently of the number of quantiles, and show that the resulting conditional distribution estimates are competitive with or better than several nonparametric alternatives, especially with many covariates and mixed or missing data. The paper positions PGB as a general speeding-up layer that can be added to any boosting implementation, with trees as the default base learner but no requirement of tree-specific machinery.","feed_headline":"One shared direction makes multi-output boosting orders of magnitude faster","feed_subtitle":"With one base learner per step, multi-quantile regression becomes cheap while preserving accuracy and proven convergence.","key_machinery":"The engine is the collinear base-model family φ_{w,β}(x) = h_w(x) β, where h_w is any univariate prediction rule and β is a unit vector giving the direction of the update. This factorization separates norm learning from direction selection: only h_w is learned by a weak learner, while β is chosen from the canonical basis in rotation (Equation 9) and refined by a multidimensional line search that sets the step size γ_t in R^M. Lemma 3 shows the span of these collinear models equals the product of univariate spans, which lets the proof reduce the multivariate descent to a separate univariate boosting run per coordinate, with Corollary 1 allowing the risk to stay flat on non-updated coordinates","core_discovery":"The paper's central discovery is that the computationally hard multi-output weak-learner problem—choosing a base model and direction to align with the full gradient—can be replaced by a much simpler two-step procedure without losing the convergence guarantee. At each iteration PGB picks a coordinate direction from the canonical basis (visited infinitely often), fits one univariate model to the projected pseudo-residuals, and then performs a full line search over all M components of the step. Theorem 3 shows that under Assumptions 3, 5 and 6, this procedure drives the empirical risk to the minimum over the span of the collinear base models, because the span of {h_w β} is exactly the M-fold pr","pith_inferences":["If the empirical speed-ups persist for non-smooth losses, the same collinear-direction idea could be applied to other multi-output objectives, such as multiclass classification with hinge-type losses, where the paper's convergence theory does not currently reach.","The per-coordinate line search gives PGB a block-coordinate-descent flavor; interpreting the canonical-basis sampling as a randomized block selection rule could let one import Gauss-Southwell or importance-sampling results to choose directions adaptively with provable rates (the paper only compares these empirically).","Since computation time is nearly independent of M, users could push quantile grids far beyond the paper's rule-of-thumb M≈2√n, trading negligible runtime for smaller CRPS approximation error; the paper's Appendix D suggests gains flatten near M=20, but this was tested only on multimodal circular data.","The shared-splits property suggests PGB might serve as a regularizer in the output direction: because all quantiles share the same tree structure, the effective number of parameters grows more slowly than in separate-per-quantile boosting, which may explain the reduced crossing and could be studied as a form of output-space regularization."],"forward_implications":["PGB makes dense quantile grids affordable: in the baseball experiments, training 128 quantiles with a standard boosting library took more than 50 times longer than one quantile, while PGB's cost stayed nearly flat, enabling finer approximation of conditional distributions.","The convergence theorem applies to any univariate base learner satisfying the symmetry and approximation assumptions, not only trees; the paper demonstrates convergence with linear models on real datasets.","Because all targets share the same splits, PGB produced far fewer quantile crossings than standard boosting on the simulated example, simplifying post-processing.","The conditional distribution estimator built on PGB matches or beats distributional random forests, FlexCode, and LinCDE on most of the ten medical datasets tested, with the largest gains on high-dimensional and missing-data settings.","The isotonic-regression post-processing step is proven (by a cited result) to only improve the weighted interval score, so the correction for quantile crossings is safe."],"fun_headline_variants":["One shared step: single base model for all multi-output targets","Coordinate boosting: fit one model, get all conditional distributions","One model per iteration: parallel boosting for full distributions","One descent direction, one weak learner: multi-output boosting speedup","Parallel boosting fits one model per step for all quantiles"],"cache_read_input_tokens":35840,"weakest_assumption_plain":"The convergence theorem requires each component of the loss to be convex and K-smooth, but the paper's flagship use case—multiple quantile regression—minimizes the pinball loss, which is non-differentiable at zero and lacks K-smoothness, so the formal guarantee does not cover the practical algorithm that delivers the reported speed and accuracy.","fun_headline_variants_meta":{"raw":{"variants":["One shared step: single base model for all multi-output targets","Coordinate boosting: fit one model, get all conditional distributions","One model per iteration: parallel boosting for full distributions","One descent direction, one weak learner: multi-output boosting speedup","Parallel boosting fits one model per step for all quantiles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00232,"raw_usage":{"total_tokens":8811,"prompt_tokens":802,"completion_tokens":8009,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":546,"completion_tokens_details":{"reasoning_tokens":7926}},"tokens_in":546,"tokens_out":8009,"duration_ms":63775,"temperature":1.0,"reasoning_tokens":7926,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T04:51:41.795159+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a simulated dataset with known conditional quantiles, set the base-learner class to stumps and compute the minimum possible weighted interval score over all linear combinations of stumps via linear programming. If PGB with the pinball loss fails to approach that minimum after a very large number of iterations, with the gap remaining non-negligible, then the practical algorithm does not deliver the convergence that Theorem 3 would require, exposing the mismatch between the smooth-loss theory and the pinball application.","supporting_citations":[],"review_version":1}