A Case for Library-Level $k$-Means Binning in Histogram Gradient-Boosted Trees
Authors: Asher Labovich
Venue: Accepted by TMLR ()

Abstract: Modern Gradient Boosted Decision Trees (GBDTs) accelerate split finding with histogram-based binning, which reduces complexity from $O(N\log N)$ to $O(N)$ by aggregating gradients into fixed-size bins. However, the predominant quantile binning strategy—designed to distribute data points evenly among bins—may overlook critical boundary values that could enhance predictive performance. In this work, we consider a novel approach that replaces quantile binning with a $k$-means discretizer initialized with quantile bins, and justify the swap with a proof showing how, for any $L$-Lipschitz function, k-means maximizes the worst-case explained variance of Y obtained when treating all values in a given bin as equivalent. We test this swap against quantile and uniform binning on 33 OpenML datasets plus synthetics that control for modality, skew, and bin budget. Across 18 regression datasets, k-means shows no statistically significant losses at the 5% level and wins in three cases—most strikingly a 55% MSE drop on one particularly skewed dataset—even though k-means' mean reciprocal rank (MRR) is slightly lower (0.65 vs 0.72). On the 15 classification datasets the two methods are statistically tied (MRR 0.70 vs 0.68) with gaps $\leq$0.2 pp. Synthetic experiments confirm consistently large MSE gains—typically $>$20% and rising to 90% as outlier magnitude increases or bin budget drops. We find that k-means keeps error on par with exhaustive (no-binning) splitting when extra cuts add little value, yet still recovers key split points that quantile overlooks. As such, we advocate for a built-in bin_method=$k$-means flag, especially in regression tasks and in tight-budget settings such as the 32–64-bin GPU regime—because it is a "safe default" with large upside, yet adds only a one-off, cacheable overhead ($\approx$ 3.5s per feature to bin 10M rows on one Apple M1 thread).

Published in Transactions on Machine Learning Research (09/2025)
A Case for Library-Level k-Means Binning in Histogram Pradient-Boosted Trees
Asher Labovich Deportment of Applied Mathematics, Brown University
asher law.oaachbboourreec
Reviewed on OpenReview: https: // openreview. net/ forum? id- UoTrLLspJa
Abstract
Modern Gradient Boosted Decision Trees (GBDTs) accelerate split finding with histogram- based binning, which reduces complexity from O(N log N) to O(N) by aggregating gradients into fixed-size bins. However, the predominant quantile binning strategy- designeyddssigned to distribute data points evenly among bins may overlook critical boundary values that could enhance predictive performance. In this work, consider novel approach that replaces quantile binning with k-means discrctizer initialized with quantile bins, and justify the swap with a proof showing how, for any L-Lipschitz function, k-means maximizes the worst-case explained variance of Y obtained when treating all values in a given bin as equivalent. We test this swap against quantile and uniform binning on 33 OpenML datasets plus synthetics that control for modality, skew, and bin budget. Across 18 regression datasets, k-means shows strikingly particularly skewed dataset even though k-means' mean reciprocal rank (MRR) is slightly lower (0.65 0.72). On the 15 classification datasets the two methods are statistically tied (MRR 0.70 vs 0.68) with gaps <0.2 pp. Synthetic experiments confirm consistently large MSE gains typically 20% and rising to 90% as outlier magnitude increases or bin budget drops. We find that k-means keeps error on par with exhaustive mio-binning) splitting when extra cuts add little value, yet still recovers key split points that quantile overlooks. As such, we advocate for a built-in bin method=k-means flag, especially in regression tasks and in tight-budget scttings such as the 32-64-bin GPU regime-because it is safe default. with large upside, yet. adds only one-olf, cacheable overhead (r< 3.5s per feature to bin 10M rows on one Apple M1 thread).
statistically significant losses at the 5% level and wins in three 55% MSE drop
1 Introduction
Gradient Boosted Decision Trees (GBDTs) are ensemble learning methods that have achieved state-of-the-art results on a wide range of tasks. By iteratively fitting new decision trees to the "pseudo-residuuls' of a loss function, GBDTs combine many weak learners (e.g. individual decision trees) into a strong predictor (Friedman, 2001). Since the seminal work of Friedman on gradient. boosting, the technique has become a de facto choice for structured data problems. Because GBDTs require only a twice-difforentiabl loss function, they are especially useful for non-standard prediction problems, such as ranking or quantile regression (Burges, 2010). Modern implementations like XGBoost, LightGBM, and CatBoost have popularized GBDTs by offering order-of-mannitude computational speed-ups with excellent accuracy (Chen & Guestrin, 2016) (Ke et al., 2017) (Prokhorenkova et al., 2019). These systems have been widely adopted to win Kaggle and other ML competitions, often outperforming deep learning on tabular data (Grinsztaju et al., 2022).
In formal terms, GBDT algorithms wish to minimize an arbitrary twice-differentiable loss function by maintaining an ensemble-bate based predictor F, comprised of a series of CART trees. At each round t calculates first and second-order statistics

---

Published in Transactions on Machine Learning Research (09/2025)
@ Fi-1 (x.) gi
h, 8 L Fi-1
(F4)
(x4)
and then fits simple CART tree to maximize split-gain gain criterion. The optimal weight for leaf / is calculated
Eie 9i
1i Die
and the model is updated as =(-1))= + (()eaf((x) Parameters 1 and À correspond to the learning rate and L. regularization respectively, and are chosen by the user prior to training.
A key method for optimizing these algorithms is their use of histogram-based binning for splitting continuous features. Traditional decision tree algorithms sort feature values to find split points, which is computationally expensive logNlog per feature initially, and O(N) for split-finding) and thus intractable for large datasels. To allow training on datasets sometimes too large to fit into memory, modern GBDT algorithms bucket continuous feature values into discrete bins and accumulate gradients per bin during training. This approximation drastically reduces computation and memory overhead while maintaining similar accuracy as exhaustive splitting. In particular, histogram- based models require only ((N) scans for histogram building (and only O## bins) for split-fidiig), with no sorting needed. Major state-of-the-art algorithmss, like XGBoost, LightGBM, and CatBoost, all use similar histogram-binning methods, though with small differences in implementation. These innovations allow GBDTss to effectively scale to datasets with millions or billions of instances.
In state-of-tho-art histogram-based GBDT librarics, the dofault choice is quantile binning: thresholds are placed so that every bin holds roughly the same number of observations, barring duplicate values. This equal-frequency distribution is popular because it preserves the rank order of values and often yields split quality comparable to those obtained by exhaustive-search algorithms. However, quantile binning sometimes mask rare but inffuential values. For example, in a sample of one million observations with one thousand extreme outliers, 255-bin quantile scheme would pool those outliers with 3000 ordinary points, blunting a potentially important boundary.
A natural alternative is to utilize some method of unsupervised clustering to isolate important points prior to training. One such example is via 1-D k-means clustering (Iloyd, 1982), which explicitly minimizes within-bin variance and can place cuts at rare yet influential values. We therefore compare Lloyd k-means clustering with quantile initialization' with quantile binning as well as uniform (equal-width) binning to characterize the regimes-tor tail mass, multi-modalite and bin budget-unde under which each discretizer is preferable and to test whether a simple k-mcans swap can boost accuracy without compromising training speed.
We find that uniform equal-width cuts seldom rival quantile, whereas k-means almost always draws level with quantile and occasionally provides a marked boost. Across 18 real-world regression datasets, k-means never performs worse than quantile at the 5% level and cuts MSE by more than half on the most skewed case, though it has a slightly lower MRR (0.65 vs 0.72). When we repeat the sweep with the 63-bin budget recommended for GPU training (Zhang et al., 2017), k-means posts five wins and raises its best-case drop to 68% MSE (Table 5), though quantile achieves two small (< 2%) wins.
In 15 classification datasets quantile and k-means are stal tied (MRR 0.68 vs 0.7) with gaps S 0.2 percentage points (pp) (pf)-differences that are essentially negligible. Synthetic regression benchmarks tell the same story: when outliers dominate or when bin budget is low, k-means often cuts error by more than 20% and can reduce error by as much as 90% in some cases. Taken together, our findings show that k-means stays within statistical noise of exhaustive splitting when the bin budget is generous, yet often uncovers critical split points that quantile missos.
To our knowledge, no open-source GBDT package (XGBoost, LightGBM, CatBoost) offers a k-means discretizer, and the literature lacks any systematic test of alternative unsupervised binning schemes. We
Appendix D benchmarks two other globally-optimal discretizers, MILP-optimal (Navas-Palencia, 2022) and 1-D k-means (Wang Song, 2011). These methods either have unreasonable computational requirements or merge features down 25 bins, significantly harming accuracy.
2

---

Published in Transactions on Machine Learning Research (09/2025)
therefore conduct the first large-scale benchmark (33 OpenML datasets plus controlled synthetics) and show that this drop-in option can significantly cut regression MSF in skewed datasets or in low-bin scenarios while adding only a one-off, cacheable preprocessing cost of 2 3.5s per feature to bin 10 M rows on a single Apple M1 thread- making a bin_ sin__ethod= k -means flag an immodiately actionable upgrade for commercial GBDT libraries.
2 Related Work
In recent years, gradient-boosted decision trees (GBDTs) have become the dominant choice for large-scale tabular prodiction thanks to highly optimized "histogram' implementations that reduce time complexity from ONN log N) to ((N) per feature by pre- breebinnig contimuous imputs. LightGBM introduced leaf-wise growth together with GPU-friendly, histogram-based training to parallelize histogram-buulding and split-finding on large datasets (Ke al., 2017). XGBoost introduces a weighted quantile sketch to obtain approximate split points that are e-accurate even on distributed data (Chen & Guestrin, 2016). CatBoost further refines this pipeline with ordered boosting and efficient handling of categorical features, yielding state-of-the-art accuracy on many public benchmarks (Prokhorenkova et al., 2019). Scikit-lcarn, package for casy application of ML algorithms, recently added HistGradi entBoosting as a re-implementation of these histogram algorithms for GBDTs, providing a convenient baseline for academic comparisons (Pedregosa et al., 2018).
Although the histogram abstraction is now standard, the binning step itself has attracted surprisingly little study. All three major from equal-frequency (quantile) cuts. Their main differences lie elsewhere: (1) XGBoost replaces the naive O(N log N) per-feature sort with weighted quantile sketch a streaming algorithm that yields e-accurate percentiles in O(N) time and sub-linear memory, allowing for distributed quantile binning (Chen & Guestrin, 2016); (2) Light GBM applies gradient- one-side sampling (GOSS) after bins are formed, keeping rows with large gradients to speed up tree growth (Ke et al., 2017); (3) CatBoost introduces ordered boosting and specialized handling of categorical features (Prokhorenkova et al., 2019). Thus, despite diverse engineering optimizations, the underlying assumption that frea-ffee bins are "good enough" " remains largely unchallenged.
LightGBM, and CatBoost- st.ill build their histograms
Adaptive data-driven binning has been explored in other settings. Early entropy-based cuts (Fayyad & Irani, 1993) and MDL-guided binning (Dougherty et al., 1995) found that supervised partitions improve decision-tree trree and Naive-Baycs accuracy over equal-width binning in classification scttings. In federated settings, Ong et al. (2020) begin with equal-mass bins and dynamically merge or split them using gradient entropy to keep communication costs fixed. Our work is largely orthogonal these settings: we study libvary-level 2, unsupervised binning that can serve as the starting point for any Aitoogram-GBDDD pipeline, federated or c Although k-means is unsupervised, its arrfanco-minimizing objective lets it capture label-relevant tails that equal-mass schemes often smooth over, thus recovering portion of the gains previously attributed only to supervised or adaptive methods.
In summary, while histogram GBDTs have matured along multiple engineering directions, the underlying assumption that equal-frequency bins are universally adequate has remained laryely unchallenged. Our work provides the first systematic comparison between quantile, k-means and uniform binning on 33 real-world tasks and controlled synthetic suite, revealing areas where simple k-means swap yields substantial accuracy gains with negligible overhead.
3 Theoretical Motivation
Although our contribution is primarily empirical, we provide a short analysis showing that for any L.-Lipschitz larget J, k-means binning maximizes the tightest possible lower bound on the explained variance of Y obtained when treating all values in given bin equivalent.
BBy "library-level" refer modifications that live inside the CBDT library itself (o.g. LightGBM, XGBoost). The only exposure to the end user extra option to specify the bin_nethod no scparate preprocessing script or data-pipeline changes are required. However, we do conduct small benchmarking experiment in Appendix D which includes a supervised binning method.
3

---

Published in Transactions on Machine Learning Research (09/2025)
Throughout this section work in the population (distributional) setting: K K-binning is measurable partition B = (Bi, Bxk of the feature domain, and we write тj IP(X E By). Given centers {c,,... CK) the k-means quantization (binning) objective is to minimize
K Σ
ny - B,)
For any fixed partition B, the objective is minimized with respect to the centers when Gj E| E By]; substituting yields
Ty Var (X X BB)
Because the optimization is taken jointly over all measurable B and the centers Cı, CK: population-level k-means is therefore eractly the problem of minimizing the expected within-bin variance across all K partitions. This mirrors the familiar sample version, where k-means minimizes the within-cluster variance the observed data points (Lloyd, 1982).
Lemma 1 (Paired- difference identity). Let Z be square-integrable random variable and let 7' d 7 be an independent copy of Z. Then
1 - B[((3-2j4
Var(Z)
(1)
Proof. By independence and identical distribution,
E E -
22)
B + - 2F(2?'
(3)
2E 2 (E(Z)²²
(4)
2 Var(Z)
Dividing both sides by yields (1)
Theorem 1. Let rundom variables (X, Y) with finile second moments salisfy a L-Lipschilz continnous model Y = f(X) +e with [[c] = 0, e e X, Var(c)==d) Then, k-means binning chooses the bins which marimize the tightest possible lower bound on the explained variance of Y.
Proof. Fixing integer K and measurable binning B as (Bi, B2,..., BRY, define nj = P(X Bj). We write [y = Σj= Ry9j and Var,(g,) ΣØ= ( - E,,1,,) as the expectation/variance some function of g across bins under {
For regression, have that the explained variance of given binning B is
Y X E ByI E(y] B
(6)
Var, ( e B,)) Var(Y) Var(Y X B,)
(7)
4

---

Published in Transactions on Machine Learning Research (09/2025)
By the law of total variance. Since Y and X fixed before bin choice, the explained variance is maximized when Ry[Var(Y]X E By)] is minimized. Using Lemma and the I-Liischitz property of f, we have that
Var(Y E BB)
(9)
- B₁]
(10)
[l(((X) (xx))=++---- +c B,]=
(11)
[((((X)) - E BOy
(12)
1
B[( B X E B²]+
(13)
Va E +O)
(14)
Consoquently,
E, Var(Y X E B,) < E Var(X X E B,) + = Larx(VV E B,]1
Since k-means minimizes E, [arr(X(X|X By)] (as shown earlier), it minimizes this upper bound and therefore maximizes a lower bound on the explained variance of Y. Since this bound strict when BX (proof in Appendix A), this the tightest possible lower bound on the explained variance of
Since exact k-means binning impractical for large datasets*, in Section we replace it with Lloyd's algorithm via scikit-learn, which offers a fast heuristic approxination to the exact k. We find that this theoretical justification carries over when using Lloyd's algorithm on real-world datasets, with k-means binning often obtaining the lowest realized error.
4 Experiments
We evaluate our discretizers 33 OpenML tasks and suite of controlled synthetic benchmarks. An anonymized reproducibility package-sovv source code, logs, and result tables-is provided for reviewers (sce the Links section).
4.1 Real-world benchmarks
4.1.1 Methodology
Datasets. To ensure replicable results we evaluate our models on the OpenML (Vanschoren et al., 2014) benchmark suite described in Grinsztaju et al. (2022) (study_ _id 336 for regression, 337 for binary classifica- tion), dropping task from each track (HIGGS, ZURICH DELAYS) due to computational constraints. The remaining 18 regression and 15 classification tasks span 10 106 instances and 2 420 numeric features. Appendix B lists observations and features for each dataset.
Binning schemes. We compare three discretizers: quantile (Li default), uniform (equal-width), k-means (Lloyd with quantile seeding). Unless noted otherwise, all binning schemes use B = 255 bins (the common default in LightGBM and seikit-learn, among others).
In all real-world benchmark tables, we also list an "exhaustive search' column, which checks all possible split thresholds without using binning. Because that variant. enumerates all possible split thresholds (O(N) per
"Appendix D presents brief benchmark of the 1-D Byrammic-rugraamminng formulation of optimal k-meaus (Wang & Song, 2011). The method's computational cost high that becomes impractical for histogram-based CBDTs, offering realistic apceracc advantage over Lloyd's algorithm.
5 Appendix E. reports ablation the GPU-reommmedded budget, 63, as described in Zhang al. (2017).
5

---

Published in Transactions on Machine Learning Research (09/2025)
node), it is impractically slow large datasets but serves practical upper-bound reference to quantify the accuracy degradation attributable to binning itself.
In Appendix D, we present a brief benchmark of two further binning schemes and show that neither achieves an attractive apped-accuracy trade-off.
Learners and tuning. Commercial-grade librarics such as LightGBM, XGBoost, and CatBoost apply additional preprocessing layers e.g. Li's exclusive-feature bundling, XGBoost's weighted quantile sketch (Ke et al., 2017) (Chen & Guestrin, 2016). These steps re-executed even when the input has already been pre-binned to 255 distinct values, producing a second, library-specific histogram that blurs the effect we wish to measure. To isolate the contribution of the enternal discretizer itself, we therefore run all main-paper wwweeooosinnggggeeeeeeeeeeeee
experiments with scikit-learn's 's vanilla our bins exactly as supplied. In a supplementary run with XGBoost (Appendix F) configured to bypass its internal quantile sketch-we we observed similar results on representative regression datascts, suggesting that the choice of baseline model does not influence our conclusions.
where the model consumes
For every (dataset, binning, learner) triple we run 30-trial RandomizedSearchhV with 5-fold CV on hyper- parameters shown in Appendix C. Each experiment is repeated over 20 random train/test splits (80/20) to estimate variability.
Compute resources. All real-world experiments were conducted on an academic slurm cluster, on 48-core Intel Xeon Platinum 8268 CPUs @ 2.90 GHz The experiments ran 120h wall-clock, doing 1792 core-hours of work, and peaking at 7.7GB memory. Additional exploratory runs on the same cluster amounted to no more than 10k CPU-hours ( 6 x the final sweep), confirmed from Slurm accounting over the project. period.
Metrics and statistics. We report mean squared error (MSE) for regression and ROC-AUC for binary classification. Regression MSE values span several orders of magnitude, so each row of our results table presents them in scientific notation with the common exponent factored out on the left of the dataset name (e.g. 'BRAZILIAN HOUSES (10-))"). This keeps the numeric columns directly comparable across datasets.
To provide a scale-free summary metric, we compute a macro-averagee better). For each dataset the three histogram methods (exhaustive scarch excluded) are ranked; the reciprocal rank is then averaged over datasets, with each dataset contributing one vote.
reea--reiproocl-raank (MRR, 1 is
Paired two-sided t-tests (n=20 splits) compare the top-ranked discretizer with the runner-up (exhaustive scarch excluded) on each dataset. All resulting p-values are jointly adjusted with the Benjamini- procedure (Benjamini & Hochberg, 1995); cells that stay significant the a = 0.05 level after this correction are bolded.
In Appendix H mirror all experimental tables including those in Appendices E and F and add the standard error across random seeds.
4.1.2 Results
Tables 2a and 2b report mean test-set scores averaged over 20 random 80:20 splits, with per-dataset winners flagged by paired (-tests, as described in section 4.1.1.
Regression (18 tasks) Although k-means attains a slightly lower MRR compared to quantile binning (0.65 vs. 0.72), it is never statistically outperformed by either quantile or uniform binning at the 5% significance level across all evaluated datasets. However, k-means wins outright in 3 datascts, most strikingly by 55%, on the BRAZILIAN HOUSES dataset. Its other wins range from 1-2%. BRAZILIAN HOUSES is especially unique, because it contains the most highly skewed input dataset (averaged by column) among those in the benchmark. In addition, the extreme predictor values (e.g. high property tax) coincide with extreme target values (rent price), so isolating these points is crucial. Across the full regression suite, k-means performs 2 0.3% worse than the exhaustive split method on just three datasets; of those, quantile performs statistically significantly worse than
6

---

Published in Transactions on Machine Learning Research (09/2025)
k-means two (and significantly better on none). This suggests that k-means retains almost all of the predictive value of exhaustive splitting when extra cuts add little value, yet still recovers key tail-driven split-points that quantile overlooks. In section 4.2, we conducted in-depth analysis into this relationship between k-means performance and highly-skewed data.
Zhang et al. (2017) recommend using a budget of B = 63 when training GBDTs on a GPU; in Appendix E, we rerun the regression suite to analyze this scenario. Under this tighter budget, k-means now holds an 8% lead on CPU ACT and widens its lead on BRAZILIAN HOUSES to 66%, while quantile gains a statistically significant 2.5% lead on SUPERCONDUCT and a 0.5% lead on DIAMONDS. In Appendix E, hypothesize two mechanisms for quantile's small wins in the low-bin regime: (1) k-means may spend a larger proportion of a small bin budget isolating extremes that may not be label-relevant, and (2) coarser histograms also introduce greater variance, so edge-label aligument can occur by chance.
Classification (15 tasks). Quantile and k-means achieve virtually identical MRR (0.68 vs. 0.70). Quantile attains stalistically significant wins on two datasets (5% level), while k-means claims none; however, even in those two cases the advantage is at most 0.2 pp practically negligible.
Notably, the effect of k-means is much smaller for classification than it is for regression. The core difference is that baseline classification losses are bounded, whereas squared-error in regression grows without limit. When many distinct, widely spaced numeric values fall into the same bin, a tree must assign them single prediction. In regression that prediction is their mean, so any extreme value in the bin incurs squared error that grows with its distance from the mean; a few such outliers can dominate the total MSE. In binary classification, collapsing diverse values has a softer effect: the tree assigns the bin a single class- probabiity.... For given bin, the worst accuracy it can give is 0.5 (predicting majority class for all), and the worst log-loss is In 2 (predicting 0.5 for all) - both fixed, finite penalties that do not explode with feature magnitude. Thus isolating rare, label-relevant extreme points with k-means dramatically lowers regression MSE but mudges classification metrics by only a few hundredths.
We also pre- binned three representative regression datasets with either quantile or our k-means cuts (B 255) and trained XGBoost using its exact (i.e. exhaustive) tree builder. As Appendix F shows, k-means retains existing ties while reducing MSE on BRAZILIAN HOUSES by 64%, confirming the lift translates unchanged to a rainstream GBDT engine when using exhaustive no-histogram methods.
These patterns large gains when label-relevant tails exist or when bin budget is low-loowse suggest histogram resolution and outlier mass are the controlling factors. We investigate those mechanisms systematically via the synthetic suite in section 4.2.
4.2 Synthetic diagnostics
We complement the real-world benchmarks with a controlled suite of five synthetic studies that probe exactly when k-means binning beats equal-frequency cuts. All runs share the same generator (Alg. 1) which computes target as the sum of 3 columns combined with Gaussian noise and allows independent control of outlier mass, outlier magnitude, multi-modality, bin budget B, and sample size n. We split the dataset into 80/20 train-test and run scikit-learn's
We keep the seikit-learn defaults (100 trees, learning-rase maating-ratt-- = 0.01) for consistency, and simply raise the depth to 5 and set subsample = 0.8 to give the model adequate capacity and standard stochastic regularization without masking the binning effects.
Each cell in Figs. 1 reports the mean relative MSE reduction
MSEquantile - MSE
A% 100x
MSEquantile
over 50 i.i.d. dataset/split draws (stars mark cells where the two methods perform statistically significantly
different at the 95% confidence level, after performing Benjamini-Hochborg falso-discovery-ratt correction). Quantile statistically ties or loses to k-means across all of our experiments, with losses as high as 90% in certain cases.
7

---

Published in Transactions on Machine Learning Research (09/202)
Dataset Name
Quantile
Uniform
k-means
Exhaustive
Regression (MSE)
cpu _act
cpu_act (10")
5.043
5.094
4.965
5.092
pol (10')
3.337
3.337
3.337
3.347
elevators (10-6)
4.861
4.842
4.862
4.881
wine qualet (10-1)
4.096
4.089
4.128
4.117
Ailerons (10-*)
2.518
2.526
2.523
2.519
houses (10-²)
5.274
5.358
5.283
5.292
house 16H (10=1)
3.338
3.674
3.415
3.262
diamonds (10-²)
5.458
5.602
5.464
5.459
Brazilian houses (10-3)
5.382
20.272
2.433
2.156
Bike Balke__harrngg Sharing_Demandd (10*)
9.697
9.697
9.697
9.694
uyc-taxi-grreu-deo2211e (10-1)
L.553
1.959
1.522
1.320
(10-3)
3.183
3.217
3.175
3.206
sulfur (10-4)
1.649
4.698
4.663
4.779
medical medical_chargess (10-²)
6,686
7.153
6.600
6.581
MiamiHousing2016 (10-2)
2.259
2.291
2.264
2.309
superconduct (10*)
1.012
1.036
1.015
1.038
yprop _1 (1004)
9.457
9.481
9.464
9.474
abalone (10%)
4.775
4.788
4.767
4.759
Regression MRR
0.72
0.43
0.65
Classification (ROC AUC)
credit electricity
0.857
0.827
0.857
0.857
0.950
0.918
0.948
0.960
cavertype
0.933
0.931
0.932
0.931
pol
0.999
0.999
0.999
0.999
house 16H
0.951
0.947
0.951
0.950
MagicTelescope
0.931
0.931
0.931
0.930
bank-marketing
0.886
0.886
0.886
0.886
MiniBooNE
0.983
0.967
0.983
0.982
eye movements
0.705
0.709
0.709
0.718
Diabetes130US
0.647
0.647
0.647
0.647
jannis
0.868
0.867
0.868
0.867
default-of-coe ofreultt-f-rredit--e oewto--eettttddddldiiieeee card-clienss
0.781
0.779
0.781
0.780
Bioresponse
0.861
0.859
0.860
0.858
california
0.967
0.962
0.967
0.966
heloc
0.798
0.798
0.798
0.798
Classification MRR
0.68
0.41
0.70
Table 1: Summary of quantile, uniform, and k-means binning 33 real-world regression and classification datasets.

---

Published in Transactions on Machine Learning Research (09/2025)
Compute Resources. All synthetic experiments were executed MacBook Pro (Apple M1 Pro, 8 threads, 16 GB RAM, macOS 15.0). They completed in about 1.55 hours of wall-clock time, used roughly 4.6 core-hours in total, and never exceeded 0.5 GB of memory. Preliminary experiments roughly tripled this compute cost. These compute costs are essentially negligible in comparison to the much larger compute requirements of lesting on real-world benchmarks.
(1) Varying outlier mass and magnitude. Figure Ia fixes single Gaussian mode and varies the fraction of outlicrs (0-5%) against their scale 3, drawing cach outlier from an exponential tail with scale parameter B E (5, 10, 15, 20}. With just 1% outliers, k-means outperforms quantile by more than 50% regardless of outlier scale, though the gain increases with scale (at 200, the gain is 75%). Gains slightly plateau as the tail fraction nears 5,, suggesting that the most extreme advantages stem from a smaller, label-relevant tail as 'outliers' fill greater portion of the dataset, quantile tends to isolate them more effectively, though still not as well as k-means does.
(2 Multi-modality. Figure 1b fixes the outlier mass at 1% and varies the number of density modes against the outlicr scale 3. Although we expected k-means to perform better on multi-modal data, by isolating each mode, we instead see small, if any, improvements as the number of modes increase. This suggests that isolating outliers more important a GBDT's performance than isolating modes, even when modes are well-separated. Regardless, when outliers exist, the k-means gain remains large (40-80%) for all mode counts, rising with 3: even with 10 well-separated peaks 20o tail still yields 70%+ error reduction.
Figure 1e keeps the tail magnitude fixed (3 5) and increases both the mode count and the outlier fraction. We see a similar pattern here as in experiment (1): as outliers constitute a larger fraction of the dataset, the k-means gap decreases as quantile already allocates bins to the larger tail. At the bottom row, when there are no lirrsers, we see confirmation that with B 255, quantile isolates tails of multiple normal distributions as effectively as k-means does.
Together, experiments (3)- show that multi-modality has little effect the k-means gap, neither providing benefit. to k-means nor diluting existing gaps in the presence of outliers.
(4) Sample size. Figure 2a varies the effective histogram resolution by increasing the sample size while keeping B 255. With no outliers, the two methods perform within 3%. However, with even 1% outliers, bin budget comes into play; when each bin contains 64-128 observations, the data are quantized coarsely and k-means cuts error by nearly 90%. This gap collapses (though, still exists) as the binner quantizes data more smoothly.
(5) Bin Budget B. Couversely, Fig. 2b fixes the sample size while varying the number of bins. Here, the binning methods differ even without outliers; k-means outperforms quantile on a pure normally dataset by 43% when using only 16 bins. With significant outliers, we see similar results as in experiment. (4); k-means outperforms quantile by nearly 90% when outliers constitute 1-5% with 16-32 bins. The top row corresponds to a data set drawn entirely from exponential distribution. Despile its heavy right-hand tail, it behaves similar to the Mau--Gans case especially once the bin budget exceeds about 64 indicating that h-means' advantage is triggered by the presence of a small, label-relevant tail alongside a dense bulk, not by heavy-tailedness per se.
Key take-aways from the synthetic suite.
1. Safe default. Even in the pure- Gaussian settings (0% outliers) k-means never statistically under- performs and sometimes improves MSE by 2-3%, thanks to slightly finer cuts in the sparse tails that quantile assigns a single bin.
Huge upside when small tail drives the target. With only 1% of samples lying 10-20a above the bulk, k-means cuts error by 50-90% (experiments 1-3), and the gain remains large even when that tail co-exists with up to twenty well-separated modes.
9

---

Published in Transactions on Machine Learning Research (09/2025)
3. Most valuable at coarse histograms. Even in low-skew datasets, k-means outperform quantile when the bin budget is tight (32-64 bins or 80-120 observations per bin in experiments 4-5); as cells hold fewer samples, the two schemes converge. Thus k-means binning is especially useful whenever memory or pass constraints force a low-rcsolution histogram.
(1) Single mode deta: outlier "traction" vs. outler "scale!
(2) 1 % outliers: mult-modality vs. outtler size
50%
607
S3ame trction jurfers/ hotell
Kumber denally
0.2
001
0.0
10
15
10
20
Ouster scale
Outler scale
(a) (1) Single-mode data: outlier scale B (cols) vs.
(b) (2) Fixed outlier freq. 1%; outlier scale (cols) vs. multi-modality (rows)
outlier fraction (rows)
Foxed outlier
outtier
0.65
0.04
(S4 U007 po HOLD SHOPPTE
Skew macter
L0M 121. 100al
0.03
0.0
0%
(c) (3) Fixed outlier scale & = 5 outlier freq. (cols) vs. multi-modality (rows)
Figure 1: Synthotic exporiments 1-3: relative MSE reduction (A%) of k-means over quantile binning. Each cell averages 50 runs; greener is better.
5 Computational Efficiency
Before training a model, GBDT packages that utilize histogram- biinninnniiinnnggnni discretize each continuous feature into a small fixed budget of bins (B = 255 default for CPU training in many packages). Once the edges are set, tree growing scans bins rather than individual samples, so the cost of computing split gains falls from (nn) to O(B) for every discretizer quantile, wiutl, or our k-means. The model training complexity is therefore identical; the only extra work is the onc-off bin-construction pass. Because discretization happens before model training, libraries can offer caching of bin edges if users plan to run multiple models on the training set for example, if they conducting a hyperparameter search.
10

---

Published in Transactions on Machine Learning Research (09/2025)
Bin size oudier
(5) number outlier
90%
0.05
exponential
0.0%
0.04
Skie Tradfon
(90) wwwpemooaa
boutieens
0.03
0.2--
30%
0.01
0.01
6.0
0%
-0%
128
16
32
256
Observations per sin
Number of bim
Figure 2: Synthetic experiments 5: effect of histogram resolution. Left: variable sample size at fixed bin budget. Right: variable bin budget at fixed sample size.
Figure 3 benchmarks the bin-construction pass single-thread Apple M1 for uniformly distributed data ranging from 10a to 107 rows. Times are per leature; lo estimale wall-clock cost for d columns, multiply the reported value by d, as both 1-D binning methods and GBDTs scale linearly in d. Equal-width and quantile curves remain close across the range, suggesting essentially equivalent big-O time complexity and constant factor. k-means with quantile seeding follows the same slope but with a higher intercept: on ten million rows quantile finishes 2s, whereas k-means requires 5.5s; at one million rows the gap is a more 0.3s. We also experimented with k-means++ seeding (Arthur Vassilvitskii, 2007), but saw no meaningful accuracy improvement over k-means with quantile seeding. Since the extra O(nk) initialization pass in k-means+ made preprocessing substantially slower, decided to quantile seeding throughout.
We note that quantile, uniform, and quantile-sceded k-means consume less than one-third of total training time. This will remain the case regardless the number of features d, since both binning and GBDT training itself scale linearly in d. In addition, as the cost to bin is incurred once and can cached, the extra 3.5 seconds per feature on 10M+ row datascts are negligible in practice-cspecially relative the strong error reduction we observe on skewed regression tasks. For datasets that exceed available RAM, streaming 1-D k-means variant (Sculley, 2010) be substituted without changing the API; leave evaluating this option truly massive tables to future work.
6 Conclusion
This work revisited a seemingly innocuous design choice that underlies all modern histogram-based GBDT implementations: how should one place the bin boundaries? Our systematic study across 33 real-world tasks, a five-factor synthetic suite, and a new lower-bound theorem, shows that the long-standing default of equal-frrquency cuts not sacrosanct.
We find that, in datasets with small, label-relevant toils, or in scenarios with low bin budgets, k-means can cut error significantly, sometimes by more than half. In particular, find that k-means matches exhaustive splitting in benign cases and consistently outperforms quantile whenever tails or tight bin budgets make histograms too coarse.
Because training time after binning is identical for all binning methods, the only extra cost. is a one-off, cacheable preprocessing pass essentially negligible at roughly 3.5s for 10M rows on a single Apple MIl thread.
In short, today's 'ont-size-fit-all" quantile cuts leave easy accuracy on the table. A single new op- tion bin methoo=k-means would cost. nothing at training time, remain fully backward-compatibll, and
11

---

Published in Transactions on Machine Learning Research (09/2025)
Execution-time scaling of binning methods
10
Quartlc
mennns (kmesns-- in
10
K-monn (quentio int;
XCPoost
Execution time (s)
10
10
10
10
10k
100k
1M
10M
Number of observations
Figure 3: Wall-clock time to bin/ ttaitain a model on a single continuous feature on a single MI CPU thread (log-log scale).
yield double-digit accuracy gains in common scenarios with skewed targets or tight bin budgets, such as the 32-64-bin GPU setting.
We therefore recommend that mainstream GBDT libraries expose tau__ethod=--meaae option and adopt it as the default whenever the bin budget is constrained, as on GPUs.
7 Limitations and Future Work
We deliberately ran our study with scikit-learn's 'vanilla' histogram GBDT, eliminating all library-specific preprocessing. A small replica (found in Appendix F) using XGBoost's exact method shows the same pattern, but a full integration into production pipelines e.g. LightGBM's exclusive-feature bundling, XGBoost's 's quantile sketch, CatBoost's ordered targets-remaing an engineering task for future work. Our results therefore speak most directly to library maintainers, who can offer bin methoo=k--eeans flag once these code paths are updated.
As shown throughout, k-means outperforms quantile most when datasets have a small, label-relevant tail or when bin budget is tight. If the tail information can already be reconstructed from other features, or if the target changes sharply at unknown boundarics inside a dense bulk (c.g. a normally distributed predictor with a step change at x = n), the advantage shrinks considerably. Likewise, if users have access to large bin budgets, they should expect to see smaller gaps between k-means and quantile binning.
12

---

Published in Transactions on Machine Learning Research (09/2025)
References
David Arthur and Sergei Vassilvitskii. k-means+++: the advantages of careful seoding. In Proceedings of the Bighteenth Annual ACM-SIAM Symposium on Discrete. Algorithms, SODA '07, pp. 1027 1035, USA, 2007. Society for Industrial and Applied Mathematics. ISBN 9780898716245.
Yoav Benjamini and Yosef Hochberg. Controlling the false discovery rate: A practical and powerful approach to multiple testing. Journal of the Royal Statistical Society, Series B (Methodological), 57(1):289 300, 1995. ISSN 00359246. URL http://www www.ow.......................... jstor. org/stablee/346101.
Christopher J. C. Burges. From ranknet. lambdarank to lambdamart: An overview. 2010. URL https://api. semanticscholar
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, pp. 785 794. ACM, August 2016. doi: 10.1145/2993 01145//2939722299977557 URL http: http///xx..d httx/xxxxiiooo////ooo/////oooodd wtw../.....11//39992222999339990
James Dougherty, Ron Kohavi, and Mehran Sahami. Supervised and unsupervised discretization of continuous features. In International Conference on Machine Learning, 1995. URL
org/CorpusID:220 2267766..
Usama M. Fayyad and Keki B. Irani. Multi-interval discretization of contimuous-valued attributes for classification learning. In International Joinl Conference on Arlificial Intelligence, 1993. URL https: //tpp. semppticcmmi
Jerome H. Friedman. Greedy function approximation: gradient boosting machine. Annals of Statistics, 29: 1189 1232, 2001. CRL attps://appt wemanticscholaatt Iil.aaarrrrrr/ooooIIIIIIII :
Léo Grinsztajn, Edouard Oyallon, and Gaël Varoquaux. Why do tree-based models still outperform deep learning on tabular data?, 2022. URL httpp//////adto.o/aaaaa///////// 08815.
Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL. https: //poccedd/ss neurips...... wwurips.cc/paper Papele pdf.
S. Lloyd. Least squares quantization in pem. JEEE Transactions on Information Theory, 28(2):129-137,
1982. doi: 10.1109/TTT..1982105664
Guillermo Navas-Palencia Optimal binning: mathematical programming formulation, 2022. URL https: //aardv.oorg/as//200...oo
Yuya Jeremy Ong, Yi Zhou, Nathalie Baracaldo, and Heiko Ludwig. Adaptive cettoorra-bbased gradient boosted trees for fedcrated learning, 2020. URL https://arxii: /tt/a/aaw.....a//////a/aaaa 06670.
Fabian Pedregosa, Gaäl Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Andreas Müller, Joel Nothman, Gilles Louppe, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Édouard Duchesnay. Scikit-learn: Machine learning in python, 2018. URL 1201.0490.
/
Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. Catboost: unbiased boosting with categorical features, 2019. URL https://arxiv. wttp///wwwwrg//////.....o 09516.
D. Sculley. Web-scale k-means clustering. Proceedings of the 19th International Conference on World Wide Web, WWW '10, pp. 1177-1178, New York, NY, USA, 2010. Association for Computing Machinery, ISBN 9781605587998. doi: 10. 00.114/1772690.1777 URL https: //tttps://di.... meeei.org/1... 114..1115//7779900 1772862.
13

---

Published in Transactions on Machine Learning Research (09/2025)
Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo. Openml: networked science in machine learning. ACM SIGKDD Eaplorations Newsletter, 15(2):49 60, June 2014. ISSN 1931-0153. doi: 10.1145264419902241188 URL http: dow. www....g//..0 115..0111/1//211.2888888. 2641198.
Pauli Virtanen, Ralf Gommers, Travis F. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Wockesser, Jonathan Bright, Stéfan J. van der Walt, Matthow Brett, Joshua. Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, J Carey, Ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henrikson, A. Quintero, Charles R. Harris, Anne M. Archibald, António H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261 272, 2020. doi: 10.1038/s4 05988//4552-01--06666
H Wang and M Song. Ckmeans. 1d.dp: Optimal k-means clustering in one dimension by dynamic programming.
The R journal, 3(2):29-33 33, 2011.
Huan Zhang, Si Si, and Cho-Jui Hsieh. Cpu-acceleration for large-scale tree boosting, 2017. URL https: warxii.org/ablll..... 1706/ 08359.
14

---

Published in Transactions on Machine Learning Research (09/2025)
A Proof of Strictness for Linear Model
We begin the proof in Section 3, with the additional assumption that Y == =B8 + e. In particular, the proof remains the same up until (12), wherein it continues as follows:
-[J(X) - ((X)) E Bj) + +0²
(15)
- E Bj] -0²
(16)
Var E 0o²
(17)
Consequently,
Ey Var(Y X E B,)] Ey [B2 Var(X X E B₃) + Var(XXX B,)] + o²
Since k-means binning minimizes [aa E B,),, also maximizes the explained variance Y obtained when treating all values in given bin equivalent.
B Dataset Description
The following table describes obsorvations and features from each datasct. For a given datasct, we calculate the skew by averaging the skew of each of the columns. These datasets range from 10 10 observations, and up to 400+ features. We calculate skew using the default scipy Fisher-Pearsee sample skewness (scipy. stats skew, bias=True). Recomputing with the unbiased variant (bias=False) changes values by 0.005, leaving all printed numbers unchanged.
Dataset
Skew
#Obs
Feeat.
epu_act act
5.40
8 392
22
pol
4.78
15000
27
Dataset
Skew
#Obs
# #Feat
elevators
-0.60
16599
17
wine quality
1.36
6497
12
credit
20.17
16714
11
Ailcrons
0.60
13750
34
electricity
12.07
38 474
8
houses
2.23
20
covertype
0.28
566 602
11
house 16H
6.14
22784
pol 17
5.34
10082
27
diamonds
1.03
53940
7
house 16H
5.78
13 488
17
Brazilian houses
30.23
10692
9
MagicTeeessope
0.58
13376
11
Bike_ Siea_SSarnn Demand
0.06
17379
7
bank-marketing
3.65
10578
8
nyc-taxi-green-20116
2.56
581 835
10
MiniBooNE
-11.68
72 998
51
house_sale
2.40
21 613
16
Higgs
1.56
940 160
25
sulfur
-0.03
10081
eye movements
3.18
7008
21
medical medical_chaages
5.02
163 065
Diabetes130US
5.48
71 090
8
MiamiHousing2006
0.93
13932
14
jannis
-0.22
570
55
superconduct
0.67
21 263
80
default-credit-carrd
5.55
13272
21
yprop_4 __ abalone
-0.29
8 885
43
Bioresponse
6.95
3434
420
0.62
4177
8
california
19.56
634
9
murich__transee
1.00
5 3665 575
heloc
-0.32
10000
23
Regression datasets
(b) Classification datasets
Table 2: Dataset characteristics. Boldface marks the datasets excluded from the final beuchmark due to computational limits.
15

---

Published in Transactions on Machine Learning Research (09/2025)
C Hyper-parameter Search Space
Before tuming, draw each trial's configuration from the distributions in Table 3. Thirty trials give good trade-off between search cost and performance.
Table 3: Randomized search space for GradientBossinggeereesso Each of the 30 trials in RandomizedSearchot draws one value from every distribution. Distributions follow scipy stats (Vir- tanen et al., 2020) notation: uniform (loc, scale) samples from [loc, loc + scale).
hyyer-paramettr
Distribution / range
# Estimators Learning rate
(20, 300)
loguniform(1n) (10-3, 0.5)
Max depth
randint (3,
Subsample
uniform 0.5)
Max features
uniform (0.form(0.5.00m 0.5)
Small Benchmark for Alternative Binners
Although the body of the paper focuses on quantile, uniform and Lloyd k-means, we ran a miniature benchmark to gauge the price of more optimal schemes. In particular, we compared
MILP optimal regression binning (Navas-Palencia, 2022).
1-D k-means solved by dynamic programming (Wang & Song, 2011), and
the two fast baselines (quantile and Lloyd-k-means k-means).
Given the extended training time of 1-D k-means, restricted the test small (ABALONE, 4177 x 8) and medium (DIAMONDS, 53 9400+..0 x 7) dataset. All runs use the hyper-paramcter grid in Appendix C. Binning time is reported per split; the full 30 x 5 CV grid therefore costs 150x the numbers shown.
Abalone (0.22s to train)
Diamonds (1.82s to train)
Binning Method
Binning time (s) MSE (10")
Binning time (s) MSE (10 3)
Quantile
0.003
4.76
0.03
5.30
k-means
0.028
4.65
0.39
5.36
MTLP
0.161
5.42
0.19
8.80
1-D k-means optimal
0.559
4.73
6.75
5.31
Table 4: Wall-clock preprocessing time (single M1 thread) and test MSE for two representative datascts.
Average time to train GBDT on pre-binned data listed next to each dataset's name.
Take-away.
MILP-optimal runs in a reasonable time but often merges features down to & 25 bins, hurting accuracy; DP k-means matches Lloyd on error but >15x slower (and >2x slower than training itself). Therefore, neither option is competitive for large-scale histogram GBDT training.
E Real-world Benchmark with Low Bin Budget
To understand the effect bin budget on real-world datasets, we conducted equivalent experiments as described section 4.1 with B 63. In LightGBM's GPU implementation, Zhang ct al. (2017, p.7, p.13) note that using fewer bins (6-bit packing with one reserved value, i.c., usable bins) can increase available per-workgroup workload and reduce local memory requirements, both of which speed up training. They
16

---

Published in Transactions on Machine Learning Research (09/2025)
report significant speedups at this setting, rerun real-world regression suite with B=63 to reflect the GPU-relevant regime and report those results below.
Note specifically the new gaps in the CPU ACT and Pol datasets (10% and 2.7% respectively), and the even larger gap on BRAZILIAN HOUSES (68%). Quantile now wins on two datasets, by < 3%. We hypothesize two mechanisms for quantile's two small wins in the low-bin regime. First, k-means can allocate the same number of bins to extreme values of the total budget which can sometimes be counterproductive if the tails not label-relevant. Second, quantile binning may simply win by chance in low-bin regimes, model performance becomes sensitive to dataset quirks, so accidental alignments between bin edges and label structure can drive small empirical wins.
higher B, but when В is small those bins consume much larger proportion
Table 5: Summary of quantile, uniform, and k-means bimning on 18 real-world regression datasets, with bin budget B 63. Bolded values imply statistical significance over the second-best method at p 0.05, after application of Benjamini Benjamini-Hochberg across all real-world benchmarks.
Dataset Name
Quantile Uniform
k-means
Exhaustive
Regression (MSE)
cpu act (109)
5.579
5.416
5.140
5.092
pol (10')
3.483
3.556
3.421
3.347
elevators (10-9)
4.936
4.927
4.859
4.881
wine _uueeetuutta_aaaeaa (10-1)
4.142
4.168
4.114
4.117
Ailerons (10-8)
2.529
2.525
2.510
2.519
houses 21
5.451
6.030
5.409
5.292
house_ 16H (10-1)
3.419
3.881
3.398
3.262
diamonds (10-2)
5.501
5.810
5.526
5.459
Brazilian houses (10-3)
6.507
34.465
2.222
2.156
Bike Sharing Demand (103)
Charing_Demandd
9.694
9.693
9.675
9.694
nye-taxi-groen-de-- (10-1)
1.767
2.268
1.763
1.320
house sales (10-2)
3.195
3.322
3.189
3.206
sulfur (10-4)
5.089
4.627
4.589
4.779
medical medicall_harres (10-3)
7.365
13.980
6.737
6.584
MiamiHHousing2016 (10-2)
2.267
2.312
2.289
2.309
superconduct (104)
9.931
10.825
10.193
10.383
yprop (10-a)
9.425
9.432
9.435
9.474
abalone (10")
4.775
4.837
4.790
4.759
Regression MRR
0.59
0.39
0.85
F Re-running Representative Datasets on XGBoost
To confirm that our experiments carry over to commercial GBDT algorithms, we compared our k-means binner with quantile and uniform on three representative regression datascts. We find that k-means achieves greater win on BRAZILIAN HOUSES, while remaining statistically indistingnishable from quantile (a 0.05) CPU Acr and SUPERCONDUCT.
17

---

Published in Transactions on Machine Learning Research (09/2025)
Table 6: Summary of binning methods (B = 255) on three real-world representative regression datasets using XGBoost's exact (exhaustive) method. Bolded values imply statistical significance over the second-best method at p 0.05, after application of Benjamini Hochberg across all real-world benchmarks.
Dataset Name
Quantile
Uniform
k-means
Exhaustive
Regression (MSE)
cpu act (10")
5.047
5.204
5.454
5.631
Brazilian houses (10-3)
4.555
19.303
1.655
1.639
superconduct (102)
1.003
1.038
1.014
1.032
G Synthetic-Data Generator
Algorithm shows the procedure used to create the five diagnostic suites discussed in Section 4.2. We motivated this algorithm as a combination of the simplest building blocks that yield the distributional features we wanted to probe (multi-modality and label-rclevant outlicrs).
First, Gaussian mixture with n modes components creates controllable number of modes. We fix dist=4 that adjacent modes share Re 2.5% of their mass enough to avoid empty bins while keeping the peaks distinct.
Second, we standardize each feature to equalize scale before any outliers are introduced.
Third, an exponential distribution of size applied to a p_out fraction of samples generates controllable outlier magnitude and frequency.
Finally, simple linear target (y = 2,x; X maps to extreme Y).
E, Xij + ()) ensures the exponential tails are label-relevant (i.e. extreme
Algorithm MAKESYNTH (Nobs: feeast Modees: dist, Pout: 3)
1: b Generate input matrix X 2: for j +-1 to Tifest do
for 1 to nobs do
Draw mode index m; Uniform(1,.... Dmmodes].
Set mean Mm, from linspace(O, O, dist (Nmodes 1), Rmodes) Xij ~ NN(mm.: 1).
6:
7:
end for
8:
& Standordize features and inject outliers
Hi + mean(X.s)
10:
Jj < std(X,))
11:
for x to noba do Xis-Ms a;
12:
Xij
13:
With prob. Pout replace Xiz +- Xij + Exp(9)
14: end for
15: end for
16: Generate linear target with small noise
17: Y1
> Metos Xiá Si E, ~ (00,0.113
18: return X, y)
Variability of Experiments
Here we provide copies of all previous experimental tables the main as well as in the appendix, with standard errors of the mean across random states included. As before, bolded values imply statistical significance over the second-best method at. p 0.05, after application of Benjamini-Hochberg.
18

---

Published in Transactions on Machine Learning Research (09/202))
H.1 255-bin results
Dataset Name
Quantile
Uniform
k-means
Exhaustive
Regression (MSE)
cpu_act act (10%)
5.043 (0.170)
5.094 (0.105)
4.965 (0.107)
5.092 (0.122)
pol (10')
3.337 (0.086)
3.337 (0.086)
3.337 (0.086)
3.347 (0.088)
elevators (10-9)
4.861 (0.067)
4.842 (0.063)
4.862 (0.068)
4.881 (0.068)
Sine_qualtty (10-1)
1.096 (0.050)
4.089 (0.046)
4.128 (0.054)
4.117 (0.053)
Ailerons (10-5)
2.518 (0.022)
2.526 (0.021)
2.523 (0.020)
2.519 (0.021)
houses (10-2)
5.274 (0.047)
5.358 (0.046)
5.283 (0.046)
5.292 (0.040)
house_ 16T 110-1)
3.338 (0.111)
3.674 (0.133)
3.415 (0.136)
3.262 (0.132)
diamonds (10-3)
5.458 (0.020)
5.602 (0.021)
5.464 (0.022)
5.459 (0.022)
Brazilian houses (10-3)
5.382 (1.087)
20.272 (0.520)
2.433 (0.625)
2.156 (0.576)
like__hhainng Sharing_Demand Demand (10*)
9.697 (0.041)
9.697 (0.041)
9.697 (0.041)
9.694 (0.042)
nyc-taxiigreen-dee2201 (10-)
1.553 (0.011)
1.959 (0.008)
1.522 (0.010)
1.320 (0.016)
house__sakee 310-2)
3.183 (0.021)
3,217 (0.022)
3.175 (0.022)
3.206 (0.020)
sulfur (10-4)
4.649 (0.361)
4.698 (0.407)
4.663 (0.358)
4.779 (0.383)
medical charges (10 (10-3)
6.686 (0.035)
7.153 (0.042)
6.600 (0.036)
6.581 (0.035)
MiamiHHuuinn2016 (10-2)
2.259 (0.032)
2.291 (0.034)
2.264 (0.032)
2.309 (0.031)
superconduct (10?)
1.012 (0.013)
1.036 (0.014)
1.015 (0.014)
1.038 (0.013)
yprop_ 41 (10-4)
9.457 (0.530)
9.481 (0.534)
9.464 (0.532)
9.474 (0.527)
abalone (109)
4.775 (0.066)
4.788 (0.062)
4.767 (0.068)
4.759 (0.068)
Regression MRR
0.72
0.43
0.65
Classification (ROC AUC)
credit electricity covertype pol
0.857 (0.001)
0.827 (0.001)
0.857 (0.001)
0.857 (0.001)
0.950 (0.001)
0.918 (0.001)
0.948 (0.001)
0.960 (0.001)
0.933 (0.003)
0.931 (0.003)
0.932 (0.003)
0.931 (0.003)
0.999 (0.000
0.999 (0.000!)
0.999 (0.000') )
0.999 (0.000*)
house__00 16H
0.951 (0.001)
0.947 (0.001)
0.951 (0.001)
0.950 (0.001)
MagicTelescope
0.931 (0.001)
0.931 (0.001)
0.931 (0.001)
0.930 (0.001)
bank-marketing
0.886 (0.001)
0.886 (0.001)
0.886 (0.001)
0.886 (0.001)
MiniBooNE.
0.983 (0.000)
0.967 (0.000t)
0.983 (0.000*)
0.982 (0.000*)
eye movements
0.705 (0.003)
0.709 (0.003)
0.709 (0.003)
0.718 (0.003)
Diabetes130US
0.647 (0.001)
0.647 (0.001)
0.647 (0.001)
0.647 (0.001)
jannis
0.868 (0.001)
0.867 (0.001)
0.868 (0.001)
0.867 (0.001)
deffaul-oo-crediiccarddddtttss
0.781 (0.002)
0.779 (0.002)
0.781 (0.002)
0.780 (0.002)
Bioresponse
0.861 (0.002)
0.859 (0.002)
0.860 (0.002)
0.858 (0.002)
california
0.967 (0.000*)
0.962 (0.001)
0.967 (0.000*)
0.966 (0.000*)
heloc
0.798 (0.002)
0.798 (0.002)
0.798 (0.002)
0.798 (0.002)
Classification MRR
0.68
0.41
0.70
Table 7: Summary of quantile, uniform, and k-means binning on 33
regression and classification
datasets. Standard errors included in parentheses. Standard errors that round to 0.000 are marked t and are all < 0.0005.
19

---

Published in Transactions on Machine Learning Research (09/2025)
H.2 63-bin results
Table 8: Summary of quantile, uniform, and k-means binning on 18 real-world regression datasets, with bin
budget B = 63. Standard errors included in parentheses.
Datasct Name
Quantile
Uniform
k-means
Exhaustive
Regression (MSE)
epu epu_act act (109)
5.579 (0.203)
5.416 (0.145)
5.140 (0.126)
5.092 (0.122)
pol (10t)
3.483 (0.087)
3.556 (0.087)
3.421 (0.084)
3.347 (0.088)
elevators (10-9)
4.936 (0.060)
4.927 (0.061)
4.859 (0.062)
4.881 (0.068)
wine quall_u (10-1)
4.142 (0.054)
4.168 (0.049)
4.114 (0.051)
4.117 (0.053)
Ailerons (10-8)
2.529 (0.021)
2.525 (0.021)
2.510 (0.019)
2.519 (0.021)
houses (10-2)
5.451 (0.042)
6.030 (0.046)
5.409 (0.046)
5.292 (0.040)
house 16H (10-1)
3.419 (0.135)
3.881 (0.130)
3.398 (0.126)
3.262 (0.132)
diamonds (10-2)
5.501 (0.021)
5.810 (0.019)
5.526 (0.021)
5.459 (0.022)
Brazilian houses (10-3)
6.507 (1.208)
34.465 (0.850)
2.222 (0.640)
2.156 (0.576)
Bike Sharing Demand (10*)
9.694 (0.046)
9.693 (0.046)
9.675 (0.044)
9.694 (0.042)
nyc-taxi-grett 2 (10-1)
1.767 (0.011)
2.268 (0.007)
1.763 (0.013)
1.320 (0.016)
house house__saees (10-2)
3.195 (0.024)
3.322 (0.028)
3.189 (0.022)
3.206 (0.020)
sulfur (10-1)
5.089 (0.379)
4.627 (0.389)
4.589 (0.349)
4.779 (0.383)
medical charges (10-3)
7.365 (0.032)
13.980 (0.126)
6.737 (0.037)
6.584 (0.035)
MiamiiHousing2066 (10-2)
2.267 (0.031)
2.312 (0.033)
2.289 (0.029)
2.309 (0.031)
superconduct (10!)
9.931 (0.131)
10.825 (0.131)
10.193 (0.139)
10.383 (0.133)
yprop_4 1_ (10-1)
9.425 (0.535)
9.432 (0.538)
9.435 (0.531)
9.474 (0.527)
abalone (10%)
4.775 (0.067)
4.837 (0.066)
4.790 (0.065)
4.759 (0.068)
Regression MRR
0.59
0.39
0.85
H.3 XGB results
Table 9: Summary of binning methods (B = 255) on three real-world representative regression datasets using
XGBoost. Standard errors included in parentheses.
Dataset Name
Quantile
Uniform
k-means
Exhaustive
Regression (MSE)
cpu_act (10")
5.047 (0.145)
5.204 (0.166)
5.454 (0.193)
5.631 (0.229)
Brazilian houses (10-3)
4.555 (0.913)
19.303 (0.445)
1.655 (0.407)
1.639 (0.393)
superconduct (102)
1.003 (0.022)
1.038 (0.022)
1.014 (0.021)
1.032 (0.021)
20


Reviews:
[{"review_id": "tG7xvczf31", "reviewer": "Reviewer_DMQN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors show that using K-means to select bins in histogram gradient-boosted trees leads to significantly improved accuracy for regression on datasets with a large (but not too large) set of outliers, or when the number of bins is quite limited.  They also show that performance is very similar to the state-of-the-art binning technique (quantile binning) when there are very few outliers or when the number of bins is less constrained.  Furthermore, it is shown that on classification tasks, K-means binning also performs very similarly to quantile binning.  Finally the authors' approach is efficient in terms of computing time.  Extensive experiments on OpenML datasets and carefully constructed synthetic datasets are used to justify these claims.  The authors also show that using K-means maximizes a tight lower bound on the explained variance of the target variable assuming a noisy L-Lipschitz relationship between features and target.\n\nIn summary, the authors have proposed a practical method for improving histogram gradient-boosted trees.  The evidence is clear and convincing, and the paper is well written.  I am convinced that K-means should be included as a binning technique for Gradient-Boosted Decision Trees in widely-used machine learning libraries.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Table 1 provides a comparison of the different binning techniques for a wide range of OpenML datasets.  Figures 1 and 2 show the performance gain of using K-means over quantile binning for carefully constructed datasets where the outlier properties, and the number of bins are controlled.  These experiments show precisely when K-means leads to huge improvements over quantile binning and clear, intuitive explanations for why this is the case accompany the empirical results.\n\nThe theoretical motivation section provides a clear proof for the fact that K-means maximizes a tight lower bound on the explained variance of the target variable.  While an analysis of how this affects the performance of gradient-boosted trees is not included, I view this result on explained variance as a good motivation for the work.", "audience_yn": "Yes", "audience_explanation": "The Gradient-Boosted Decision Trees approach is successful and widely used.  Binning the feature values is an excellent way to speed up the algorithm for large datasets.  The authors show their approach achieves significant improvements over the current state-of-the-art in relevant settings, without performance loss in other settings.  Furthermore, the authors' approach is efficient in terms of computing time, and does not create significant overhead compared to existing binning approaches.  I am convinced that K-means should be included as a binning technique for Gradient-Boosted Decision Trees in widely-used machine learning libraries.", "requested_changes": "The following changes are recommended, and none of them (other than correcting critical typos) are essential in my opinion.\n\n1. It would be nice to include an explanation and example of the gradient-boosted decision tree algorithm.  It is more reader-friendly when a paper is self-contained.\n\n2. Explain what atomic unit means.\n\n3. Explain the notation $\\text{E}_j[]$ and $\\text{Var}_j[]$.\n\n4. Explain the meaning of K-means on a probability distribution in the theoretical motivation.  Many readers are likely to only have seen K-means work on a set of data points.\n\n5. Explain why K-means minimizes the expected variance of $X$ or give a reference.  \n\n6. Indicate what version of ROC-AUC you are using when there are multiple classes.\n\n7. The regression MRR's in Table 1 do not match the MRR's reported in Discussion 4.1.2.  I believe this is a simple typo.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZVpfaGsv9N", "reviewer": "Reviewer_M918", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new histogram binning scheme for gradient boosted trees. Histogram binning of continuous features is used to reduce to complexity of learning splits on continuous features, Conventionally the bins used for this are uniform or quantile-based, with the latter often being the default. The authors question this choice and seek to find a more utile histogram binning scheme. To that end, they propose the use of 1-D K-means binning to bin continuous features. Specifically, they opt for k-means binning learned via Lloyd’s algorithm, initialized with quantiles instead of the optimal dynamic programming algorithm for performing 1-D K-means.\n\nThe utility of the proposed scheme is demonstrated on a variety of real regression and classification datasets. Additional studies on synthetic datasets are used to determine the settings wherein K-means binning is more performant.  \n\n**Strengths:**\n\nThe paper proposes a simple, but novel idea, to improve the performance of Gradient Boosted Decision Trees (GDBTs), a widely used machine learning technique. The performance of K-means histogram binning was benchmarked against quantile and uniform binning across a wide set of regression and classification datasets. Each of the methods was accompanied by extensive hyperparameter tuning and cross-validation. This lends credence to the presented findings, especially given the use of statistical tests to ascertain if the presented findings are statistically significant.\nThe study on synthetic data is also very welcome, as the authors have sought to demonstrate why K-means binning is so much more performant on some real-world datasets. Moreover, the choice of model for synthetic data is not overly simplistic, which lends further credence to their findings. \n\n**Weaknesses:**\n\nI do not believe there are any glaring weaknesses in this work but there are several questions that should be answered in a subsequent revision.\n\n1.\tThe added cost of K-means binning lies in the pre-training stage where continuous features are binned into histograms. This unsurprisingly is more expensive than quantile or uniform binning – does this cost become prohibitive for datasets with a lot of features? If yes, what is the upper bound on the feature space for K-means binning to be a viable alternative to quantile binning?\n2.\tWhat is the motivation for using mean reciprocal rank (MRR) as a metric? It is also not clear how this is computed for each of the presented sets of results.\n3.\tWhat measure of skew did you use in Appendix B?", "claims_and_evidence_yn": "Yes", "claims_explanation": "K-means histogram binning was benchmarked against quantile and uniform binning across a wide set of regression and classification datasets. The results were further evaluated using statistical significance tests to ascertain which of the data points are meaningful performance improvements. Studies on synthetic data are also used to demonstrate the data regime in which the proposed histogram binning scheme is more performant than uniform and quantile histogram binning.", "audience_yn": "Yes", "audience_explanation": "The proposed K-means binning histogram binning scheme is a simple modification to GDBTs, which are a commonly used machine learning technique. In the case of improved performance, this could be easily adopted by machine learning practitioners.", "requested_changes": "**Critical changes:**\n\n1.\tIt is not clear what “library-level” on Page 3 means.\n2.\tGiven the extensive hyperparameter tuning conducted, the reported results should have accompanying error bounds (or some measure of variability). This will also solidify the conclusions made about the statistical significance of the difference in performance across binning schemes.\n3.\tSpecify the measure of skew that you used in Section B (Tables 2a and 2b).\n4.\tMotivating the design choices and parameter specification in Algorithm 1 is important, as the conclusions made from the study on synthetic data are predicated on this data being somewhat realistic. \n\n**Suggested changes:**\n\n1.\tClarifying what “pp” means on Page 2 to improve clarity.\n2.\tResults with the exhaustive split search are reported in Tables 1, 2, 5 and 6, presumably as a baseline. However, those results are not discussed anywhere in the text. \n3.\tWhat is the intuition behind K-means binning with k-means++ initialization performing worse than quantile-based initialization?", "broader_impact_concerns": "I do not have any broader impact concerns with this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3J4sWPzdYs", "reviewer": "Reviewer_JvQy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "*Core Contributions*\n\n1. Challenges GBDT Binning Heuristics: Identifies that quantile binning—the decades-old default in major libraries (XGBoost, LightGBM, CatBoost)—overlooks critical split points in skewed distributions.\n\n2. Proposes K-Means Binning: Replaces quantile binning with k-means discretization (initialized by quantiles), proving it:\n    Maximizes worst-case explained variance for L-Lipschitz functions (Lemma 1).\n    Recovers label-relevant boundaries quantile binning misses.\n\n3. Empirical Validation:\n    \n3.1 Real-world: On 18 regression datasets, k-means never underperforms quantile binning (5% significance) and achieves 55–66% MSE reductions on skewed data.\n    \n3.2 Synthetic: Controls for skew/modality/bin budget, showing >50–90% MSE gains when outliers exist and bins are scarce (e.g., GPU-friendly 16–64 bins).\n\n3.3 Classification: Statistically tied with quantile binning (15 datasets).\n\n3.4 Practical Implementation: Advocates for a bin_method=k-means flag in GBDT libraries—negligible overhead (3.5s for 10M rows), cacheable, and especially valuable for regression/GPU regimes.\n\n\n*Key Strengths*\n\n1. Theoretical Rigor: Lemma 1 elegantly links k-means to explained variance maximization. Explains why k-means wins: Isolates label-relevant extremes while quantile oversmooths tails.\n2. Experimental Thoroughness:\n33 real datasets + controlled synthetics covering skew, modality, bin budgets.\nGPU-relevant tests (B= 16–64 bins) showing up to 90% MSE gains.\nValidates results across libraries (scikit-learn, XGBoost).\n3. Practical Impact:\nPositions k-means as a \"safe default\": No losses, large upside.\nMinimal overhead: One-time cost (≈ 3.5s for 10M rows) with cacheability.\n4. Insightful Analysis:\nExplains performance gap: Regression MSE is unbounded → outliers dominate errors; classification losses are bounded.\nSynthetic suite isolates causality (e.g., outliers + low bins → 90% gains).\n\n *Key Weaknesses*\n\n1. Limited Real-World Regression Wins: Only 3/18 datasets show significant k-means improvements. While \"no losses\" is strong, the upside is concentrated (Brazilian Houses dominates).\n2. Unexplained Quantile Wins in Low-Bin Regime: Quantile binning outperformed k-means on 2 datasets at B= 63 bins. No hypothesis given (e.g., symmetric data?).", "claims_and_evidence_yn": "Yes", "claims_explanation": "Based on a comprehensive review of the theoretical proof, methodology, results, and synthetic diagnostics, the submission's core claims are strongly supported by accurate, convincing, and clear evidence. Here's a breakdown:\n\n\n1. Claim: K-means binning outperforms quantile binning in regression, especially on skewed data/low-bin budgets.\nEvidence:\n55–66% MSE reduction on Brazilian Houses (highly skewed real-world data).\n>50–90% MSE gains in synthetic tests with outliers + coarse bins (Figs. 1a, 2b).\nNo significant losses on 18 regression datasets (BH-corrected p>0.05).\n8–66% gains under GPU-relevant bin budgets (B= 63).\nStrength: Rigorous real-world benchmarks + controlled synthetics isolate causality.\n\n2. Claim: K-means is a \"safe default\" (no downside, large upside).\nEvidence:\n0 significant losses vs. quantile across 33 datasets.\n2–43% gains even in \"favorable\" settings (pure Gaussians, ample bins).\nNegligible overhead (3.5s for 10M rows).\nStrength: Statistical neutrality proven via 20 splits + BH correction.\n\n3. Claim: K-means maximizes worst-case explained variance for L-Lipschitz functions.\nEvidence:\nLemma 1 (paired-difference identity) rigorously proves the theoretical foundation.\nSynthetic tests confirm k-means isolates label-relevant extremes (e.g., 20σ outliers).\nStrength: Theory aligns with empirical gains on skewed data.\n\n4. Claim: Classification performance is neutral.\nEvidence:\nMRR tie (0.70 vs. 0.68) on 15 classification tasks.\nMax 0.2 pp AUC gap (statistically significant but practically negligible).\nStrength: Bounded-loss explanation (log-loss ≤ ln2) justifies neutrality.", "audience_yn": "Yes", "audience_explanation": "Key Audience Segments That Would Care:\n\n1. GBDT Library Developers (e.g., XGBoost/LightGBM/CatBoost teams):\nThe proposal for a bin_method=k-means flag is a low-effort, high-impact change (negligible overhead, no losses, large regression upside).\nGPU-optimization focus (16–64 bins) directly addresses hardware constraints in modern ML.\n2. Practitioners Working on Skewed or High-Stakes Regression:\nFinance, healthcare, or scientific domains often deal with heavy-tailed data (e.g., rare extreme events). The 55–90% MSE reductions on such data are compelling.\nThe \"safe default\" argument reduces adoption friction: no tuning needed, no downside.\n3. Theoreticians Studying Efficient ML:\nThe explained-variance maximization proof (Lemma 1) offers a principled justification for k-means binning’s efficacy.\nSynthetic experiments provide a controlled framework for studying binning’s impact on model performance.\n4. Researchers in Tabular Data Learning:\nExposes a long-overlooked assumption in GBDTs: quantile binning’s hegemony.\nDemonstrates that simple algorithmic swaps can rival complex innovations (e.g., neural nets for tabular data).", "requested_changes": "Strengthen the work:\n\n1. Explain Quantile's Low-Bin Wins\n\nIssue: Quantile significantly outperformed k-means on Superconduct (+ 2.5%) and Diamonds (+ 0.5%) at B= 63 bins (Sec 4.1.2).\n\nAction: Add 1–2 sentences hypothesizing why.\n\n2. Clarify MRR Calculation\n\nIssue: Ambiguity in whether MRR is macro-averaged (per-dataset) or weighted by dataset size.\n\n3. Justify Synthetic \"100% Outliers\" Label\n\nIssue: Misleading term for exponentially distributed data (outliers imply rarity).\n\n4. Address GPU Motivation Gap\n\nIssue: Claims GPU relevance but lacks citation for quantile binning as a bottleneck.\n\nAction: Cite some work for support.", "broader_impact_concerns": "No", "additional_comments": "No", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)