Generalized additive models via direct optimization of regularized decision stump forests
Authors: Magzhan Gabidolla
Miguel Á. Carreira-Perpiñán
Venue: ICML 2025 poster (2025)
Keywords: generalized additive models
interpretability
decision forests
Primary area: general_machine_learning->supervised_learning

Abstract: We explore ensembles of axis-aligned decision stumps, which can be viewed as a generalized additive model (GAM). In this model, stumps utilizing the same feature are grouped to form a shape function for that feature. Instead of relying on boosting or bagging, we employ alternating optimization to learn a fixed-size stump forest. We optimize the parameters of each stump exactly through enumeration, given the other stumps are fixed. For fixed stump splits, the leaf values are optimized jointly by solving a convex problem. To address the overfitting issue inherent in naive optimization of stump forests, we propose effective regularization techniques. Our regularized stump forests achieve accuracy comparable to state-of-the-art GAM methods while using fewer parameters. This work is the first to successfully learn stump forests without employing traditional ensembling techniques like bagging or boosting.

Generalized Additive Models via Direct Optimization of Regularized Decision Stump Forests
Magzhan Gabidolla!
Miguel Á. Carreira-Perpiñán'
Abstract
feature interactions, they can be visualized by plotting each shape function fa(zaa), making them highly interpretable.
We explore ensembles of axis-aligned decision stumps, which can be viewed as a generalized ad- ditive model (GAM). In this model, stumps utiliz- ing the same feature are grouped to form a shape function for that feature. Instead of relying on boosting or bagging, we employ alternating opti- mization to learn a fixed-size stump forest. We optimize the parameters of each stump exactly through enumeration, given the other stumps are fixed. For fixed stump splits, the leaf values are optimized jointly by solving a convex prob- lem. To address the overfitting issue inherent in naive optimization of stump forests, we pro- pose effective regularization techniques. Our reg- ularized stump forests achieve accuracy compara- ble to state-of-the-arr GAM methods while using fewer parameters. This work is the first to suc- cessfully learn stump forests without employing traditional ensembling techniques like bagging or boosting.
Recently, GAMs have seen renewed interest in the machine learning community. One effective approach to construct- ing GAMs is through a forest of decision stumps. Because a stump (depth-one, axis-aligned decision tree) uses only single feature, those using the same feature za can be grouped, and this forms shape function fa(rs) for that one feature zig As building blocks for GAMs, stumps have the advantage of being flexible in choosing the feature, and during learning they can adapt to the data distribution by using more of themselves for more complex shapes while choosing less the simpler ones.
Boosting and bagging are by far the most widely used meth- ods for learning tree ensembles, including stump forests. A recent, state-of-the-art implementation of GAMs, Ex- plainable Boosting Machine (EBM), is based on these tech- niques of boosting and bagging. However, unlike the major- ity of established methods in machine learning, these tech- niques do not optimize a desired objective function over parametric model of fixed size. Because no explicit ob- jective function nor a learning problem is defined, they are more difficult to be analyzed theoretically, and have guarantees of optimality. The way tree ensembles learned using boosting and bagging is in stark contrast to the vast majority of established models in machine learn- ing such as SVMs and neural networks. These are learned by defining an optimization problem over parameters of a fixed-sized model, and using an algorithm (e.g. gradient de- scent) optimize it. In this paper, we propose, for the first time, learn stump forests using this established machine learning paradigm: we define an objective function over a fixed number of stumps and optimize all parameters itera- tively from an initial point (random, or an existing forest, which makes possible to retrain the forest at any time in the future, e.g. with updated data). Since these models are non-differentiable, gradient-based methods are not applica- ble: instead, effectively employ alternating optimiza- tion. Despite their simplicity, optimized stump forests are highly susceptible to overfitting. We analyze this behavior, and propose effective regularization based on the complex- ity of resulting GAM shape functions. Our optimized, reg-
1. Introduction
Machine learning has become increasingly prevalent, with many widely used, accurate methods being black box in na- ture such as tree ensembles and neural networks. Simpler models such as decision trees and rules, are usually less accurate, but have the advantage of being intelligible and interpretable. They are especially important for mission- critical systems such as in healtheare where models must be trusted. The focus of our paper is on one particularly important class of interpretable methods, a generalized ad- ditive model (GAM), which learns (nonlinear) functions over each individual feature, and additively combines them: F(x)= = fi (x1) +...+............. . f(r)). Because these do not model
'Dept. of Computer Science and Engineering, University of California, Merced, USA. Correspondence to: Miguel Á. Carreira- Perpiñáán emcarreira- wwwppnan@uumeerreeeeeoooooooo
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Generalized additive models via direct optimization of regularized decision stump forests
ularized stump forests achieve state-of of-the-ant--a-- art performance on multiple regression and classification benchmarks.
narizing features based on all possible thresholds, and train- ing a linear model with fo-penalty on these transformed features to obtain piecewise constant GAMs. Their feature binarization can be viewed as creating all possible stumps, and selecting them with fo-penalty. In our approach we control the number of stumps explicitly using an Eo-like constraint.
After discussing related work in section 2, we explain the alternating optimization algorithm for stump forests in sec- tion 3. We then analyze the overfitting problem and pro- pose regularization methods in section 4. Our experiments, detailed in section 5, validate the proposed methods on re- gression and classification benchmarks, demonstrating im- proved results over existing state-of state-of-the-art methods. Ad- ditionally, we highlight the inherent interpretability of GAM model through a case study on car price prediction.
Bagging and boosting are by far the most widely used methods to learn tree ensembles. Bagging is based on the idea of variance reduction by aggregating multiple diverse models trained on different bootstrap samples (Breiman, 1996). Boosting adds base learners sequentially with each added tree trying to improve the overall ensemble accuracy (Freund & Schapire, 1997). This can be done more effectively using an approximate form of gradient descent in function space, gradient boosting (Friedman, 2001). Traditionally, bagged or boosted tree ensembles have used suboptimal, greedy recursive partitioning algorithm to learn the individual trees, such as CART (Breiman et al., 1984), and used uxis-aligned trees. More recently, tree en- sembles have been constructed by using more powerful tree models (such as oblique trees) that are properly optimized, which can be done using the Tree Alternating Optimization (TAO) algorithm (Carreira-Perpináán & Tavallali, 2018). This results in a forest of significantly improved accuracy but using fewer and smaller trees, for both classification and regression (Carreira-Perpiñáal & Zharmagambetov, 2020; Zharmagambetov & Carreira- Perrpiaa,, 2020; Gabidolla & Carreira-Perpiniin 2022; Gabidolla et al., 2022). AdaBoost, the first practical boosting algorithm, has been especially successful with decision stumps (Freund & Schapire, 1996; Viola & Jones, 2004). How- ever, bagging and boosting, considered as learning methods for decision forests, operate very differently from what the majority of methods in machine learning do, namely to define a parametric model of fixed size and structure and to train it by optimizing well-defined objective function over all its parameters.
2. Related Work
Generalized additive models have a rich history in statis- ties (Hastie & Tibshirani, 1986). As shape functions, splines are used almost exclusively, and with many dif- ferent variations, including cubic splines, penalized B- splines (Eilers & Marx, 1996), and thin plate regression splines (Wood, 2003). Backfitting (Breiman & Friedman, 1983; Hastic & Tibshirani, 1986), a form of alternating optimization, and penalized (iteratively reweighted) least squares are commonly used to learn these GAMs. Select- ing the placement and number of knots (a point where two spline segments meet) has been open problem, with many different methods proposed to handle this (Breiman, 1993; Ruppert, 2002; Filers & Marx, 2010). In our ap- proach, the placement of knots is determined on the fly as a subproduct of the optimization, where stumps choose an optimal feature/threshold pair. Apart from splines, non-parametric methods based on trend filtering have been explored as shape functions (Petersen et al., 2016; Sadhanala & Tibshirani. 2019). We refer the reader to the books (Hastie & Tibshirani, 1990; Wood, 2017) for a more comprehensive treatment of GAMs in statistics literature.
More recently, other models for GAMs have been ex- plored in the machine learning community. Lou al. (2012) performed experimental comparison of different algorithms and shape functions for GAMs, and found out that ensembles of trees based on boosting and bag- ging produce most accurate results. Follow-up work (Lou et al., 2013) extended this to model pairwise interac- tions. Agarwal et al. (2021) used neural networks with spe- cial activation functions model each of the ID shapes in single
Very few works exist that follow this common learning paradigm with tree ensembles. Sorokina et al. (2007) pro- posed a Grove, an additive model of a fixed small num- ber of regression trees, where each tree is axis-aligned and is trained suboptimally using greedy recursive partitioning on the residuals of the other trees. Carreira-Perpitáán et al. (2023) consider fixed-size forests of general types of trees, such as axis-aligned or oblique, where a well-defined ob- jective function is optimized over all the forest parameters. This is done via alternating optimization over each indi- vidual tree (Forest Alternating Optimization (FAO)), where each tree is itself trained using TAO. In addition, step is applied optimize all the leaves jointly (given that all the decision nodes' parameters are fixed), technique first used by Friedman & Popescu (2008). However, both of these ap-
GAMs. Radenovic et al. (2022) proposed to shared basis neural network to model all the shape func- tions and further extended them to pairwise interactions. Ibrahim et al. (2023) used soft decision trees to model both univariate and bivariate shapes, and imposed structural sparsity constraints on the number of terms. Given the differentiability of neural networks and soft decision trees, end-to-end 4GD-based optimization methods were used to learn all these GAMs. Liu et al. (2022) used the idea of bi-
2

---

Generalized additive models via direct optimization of regularized decision stump forests
proaches suffer from overfitting, and they both ultimately resort ensembling mechanism of either bagging or averaging. In our approach we use simpler forests, based on stumps. We control the overfitting behavior with ap- propriate regularization terms without any ensembling tech- niques. The way we optimize the stump forest can be seen as a particular case of FAO, but we can train each stump directly, without the need for TAO.
not applicable. However, we can effectively apply alter- nating optimization: the parameters of one stump, while keeping the others fixed, can be optimized exactly; the pa- rameters of all the leaf values {ui, [[] while keeping the splits { Ta ) fixed, can also be optimized exactly. More specifically, alternating optimization consists of the following steps:
Individual stumps. The optimization problem (3) over a given stump s(-: 0,) when others are fixed is mine, 2 Σx= (Bn VVn Euzz s(x,; (.)) - sxx.; 0,)]². This is a standard regression problem over a stump but with targets corresponding to the residuals. It can be solved exactly through enumeration over each (fea- ture, threshold) pair as in traditional decision tree algo- rithms.
3. Direct Optimization of Stump Forests
To keep notation simple we use regression to introduce the problem. Assume we have a training set of N (in- stance, target) pairs: Bn))= C RD x R. Let s(x; 0): R. >> be a decision stump with 4 learnable parameters: 0 { T, J"). & E {l...., . Dj is a fea- ture index to split, r E R is threshold value, p², 1 IR are the left and right leaf prediction values. The predictive function of a stump s(x; 0) works by comparing 2e with r, and outputting either p² if xg < T, or xº otherwise:
All leaf parameters. Once the splits {Øe, Te Te)T are fixed, the problem (3) simplifies to a linear regression on features corresponding stump partitions. To this, we can rewrite the predictive function of a stump using an indicator function:
s(x: 0) = Su', is <T
(1)
1r, if if T..
(xx 0) = p² Ixs < T) + p² [zzs 2 T). With this notation, the objective function over all leaves is:
stump forest [x; θ) is defined as a sum of T stumps: F(x; +) = u Ei= sxx 0t), with E R being a bias term. Since each stump uses only one feature, we can re- group the stumps by feature indices, and obtain an additive model:
N Σ n=1
T pg (Inóe < Te) uh (IInde 2 Tc)
]²
min p. P
Yn
PTT 2
T Fxx: 0) = + Σ 01) = + Σ Σ
D
s(x;
Since in this step all the splits (δr. Ti TT are fixed, the indicator functions I(.) are just constants multiply- ing the unknowns {14, |T]TT= that appear linearly in- side the squared error. And so, eq. 4 a simple linear regression problem on features induced by the stump splits, and can also be solved exactly and efficiently.
t=1
d=1 1: di=d
D
= + Σ fa(xa)
(2)
d=1
where a shape function fa(za) of d's feature is a sum of stumps that use feature d: fa(xa) = Er or=d (x; 0.). Since dealing with constant leaf predictor stumps, the shape function fa(xa) is also piecewise constant func- tion with piece intervals corresponding to the stump thresh- olds. Viewing Fx; +) as both a stump forest and an addi- tive model will be important for our final learning method. Let us now first consider the learning problem of stumps forests without any regularization. For regression, we min- imize a squared error:
Starting with initial stump forest parameters (e.g. random), we can repeatedly optimize each stump individually, and all the leaves jointly. Because each such optimization step exactly solves the problem over its subset of parameters, this guarantees a monotonic decrease of the error. And since the total number of possible stump splits are finite, and since the algorithm either decreases the error or leaves it unchanged, this guarantees convergence in a finite num- ber of steps (assuming there are no cycles between states). While there are potentially many ways to order these al- ternating optimization steps, such as performing the step over all leaves after each individual stump step, or even do- ing everything in random order, in our experiments we use the following simple approach: first optimizing all leaves jointly, then optimizing the individual stumps in fixed or- der (from to T), and repeating this until convergence.
min
Un F(x,;;)) 2
(3)
Unlike in forward stagewise additive modeling of boosting, where stumps are added greedily to the forest, we want to directly optimize problem (3). Because stumps define a don-iifferentiable function, gradient-based methods are
3

---

Generalized additive models via direct optimization of regularized decision stump forests
GB iterations
4
200
400
800
800
1000
1200
0.57
3.5
opt-stumps test
3.5
0.56
Initializing from
200 GB stumps
3-
0.55
opt-stumps
Enuse
GB test
0.54
GB
2.5
2.5
GB train
0.58
Optimization
2
opt opt-stumps train
opt opt-sturnps train
0.52
1.5
1.5
0.51
0
200 Optimization steps
400
600
800
1000
0
100
200
300
400
500
20
40
60 80
100
number stumps
E -1-rouhheess penalty
Figure/ 1. Left: Comparison of stump forest optimization against the greedy approach of gradient boosting (GB) in train error for the California Housing dataset. GB uses learning rate of I, i.e., no shrinkage. Optimization step corresponds to either the step over all leaves over the individual stumps. Middle: Overfitting problem of optimized stump forests the epuact dataset. Here GB avoids overfitting by using a learning rate 0.3. Right: By penalizing the f1-discontinuity we obtain stump forests with better generalization (epuact datasct).
Opt-stumps
Regularized opt-stumps
GB-stumps 1.0
GB-stumps 17 = 0.1
0.5
-0.5
-0.5
-0.5
-0.5
-1
-1
0.2
0.4
0.5
0.5
0.0
0.0
0.2
0.4
0.0
X
X
Figure 2. Illustration on a simple ID regression problem. The learned shape functions are in bluc. GB uses 1000 stumps with learning rates 0.1 and 1.0. Our optimization method uses 100 stumps. Ground truth targets are from sine function plotted in light red.
4. Overfitting and Regularization
dle plot of fig. 1 illustrates that as the number of stumps increases, the test error also rises. Initially, this is not sur- prising, as higher number of stumps results in more flex- ible model, which can naturally lead overfitting. How- ever, gradient boosting with small learning rate (i.e., shrinkage parameter) can produce stump forests that are much larger, yet generalize much better. In the middle plot of fig. 1, for example, the GB with 500 stumps have con- siderably better test error than any of the optimized stump forests, whose best test error at around 200 stumps.
The alternating optimization method just described for stump forests is very effective at minimizing the objective function. The left plot of fig. shows how it is possible to take 200 greedily added decision stumps (in a gradient boosting (GB) way with learning rate of 1), and opti- mize it significantly with the proposed algorithm it matches the performance of more than 1000 GB stumps (the red vs the blue curves in the plot). Because GB works by greedily adding stumps, without revisiting the previous parameters, it produces much suboptimal results. In the left plot of fig. 1, we can also observe the importance of jointly optimizing all the leaves: the sharp decreases in the red curve correspond to the optimization steps over all the leaf parameters. Since leaves account for half of the number of parameters, these significant drops in error should not be surprising (it would also be desirable to optimize multiple stump splits jointly, but since their search space grows ex- ponentially with the number of stumps, this would make it computationally infeasible).
that
To understand better the overfitting problem, we use sim- plc ID regression task where the resulting models can be easily visualized. The ground truth function is a (in(2...) We generate 100 training points with added Gaussian noise to the targets. An optimized 100 stump forest achieves nearly 0 train error, and is visualized in the leftmost plot in fig. 2. Clearly, the learned model exhibits poor gener- alization, it overfits the training data by interpolating all the noise, resulting in very wiggly and discontinuous function. This can be partly attributed to the model's high flexibility: with a sufficiently large number of stumps, the training set can be perfectly fit. Additionally, the model can operate very locally, where a few stumps can significantly
Despite being simple model with relatively few parame- ters, an optimized stump forest tends to overfit the training data and exhibit poor generalization performance. The mid-
4

---

Generalized additive models via direct optimization of regularized decision stump forests
alter the output in localized region of the imput while leav- ing the rest unchanged. Given the model's high flexibility and locality, such overfitting could be expected. (GB with- out shrinkage also suffers from overfitting, but with small learning rate it does not. See the right two plots in fig. 2. This simple shrinkage method is very fundamental for the success of GB, and the theoretical understanding of still remains unclear.)
lasso (Tibshirani et al., 2005) where the difference between neighboring coefficients is penalized, and in & trend filter- ing for nonparametric regression (Kim et al., 2009).
Another regularization term that we propose is to penal- ize the deviation from the mean (or bias) for each of the leaf predictions: Ei= (u) - -2)² + (uy - -)² This en- courages all stumps to be equally important, and can pre- vent stumps from being very dominant locally. This is con- ceptually similar to the idea of regularizing the leaf values proposed in (Johnson & Zhang, 2013), and currently imple- mented in popular gradient boosting decision tree libraries such as XGBoost and LightGBM. But instead of penalizing the actual leaf values we want to penalize their deviation from the bias. GB usually fits trees to the zero mean targets (by setting the initial constant prediction to the mean of the target), and so this type of similar regularization could al- ready be happening in XGBoost.
Regularization is fundamental technique to control over- fitring. Since we know that stump forests define an ad- ditive model whose underlying geometry is shape func- tion per each feature, we can include regularization terms based on these shape functions. Such regularization will involve more global view of the model, thus can help in ad- dressing the high flexibility and locality of stump forests. We define roughness
discontinuity penalty function r((Te, phc 1z ) d;=a): (R-))) - Rz that takes stumps grouped on the same feature d (specifically, their 3 parame- ters: threshold r, left and right leaf predictions μ¹ and ,²), and outputs some measure of discontinuity of the shape function (d) resulting from the stumps. Its domain is the set of triplets of size at most T, as there are at most T stumps: Pr (IR) = {S C R |S| < T}. As rough- ness penalty r(-) we use an & sum of discontinuities. To express it, let us first derive the explicit form of the shape function fa(xa) from the set of stumps. Assume, without loss of generality, that the parameters (Te, 14, 14 |T are of the stumps that use feature d, and that their threshold values are sorted Ti < .... < Tra Then the leftmost constant piece of the resulting shape function fa(#a) is 30 = -Ee p4: which corresponds to the left leaf predictions of all stumps (because for Id E (-o0, r). all stumps will route xa to their left child). The next leftmost piece is then Bi = 1 + Σt2 n/. More generally, the value of the i's piece from the left is defined as 3 = Ei=1 po + Ei m4. The shape function fa(za) overall consists of the Ta- + 1 constant pieces with values Bu..... .r,,.. from left to right, and with their starting intervals being -0, .I. .... suming all the stumps use a different threshold r). With the shape function explicitly defined, we can now express the following roughness penalty:
With these two types of regularization, our final objective function is:
N Σ
D
min-
Un - F(xx; 0)1 +
Σ
θ 2
n=1
d=1
T
+ a
-1) +(E -2)²) Σ E1
(5)
The hyperparameter À controls the strength of the rough- ness/disconiinuity penalty, and we experimentally find that it is the more important one. The hyperparameter a con- trols the deviation from the bias, and plays less important role than A. We do not tune it, and use a fixed value of a = 0.1.
Now, for this regularized, more involved objective function, the alternating optimization steps from section are still applicable, but with some changes:
Individual stumps This is still solved exactly through enumeration over each (feature, threshold) pair but now the optimal values of the two leaves changes. The split finding algorithm will take into account the reg- ularization terms when evaluating each possible split. For each potential split, the optimization problem over Iit and Mr is (for simplicity we show when
TT, (as-
T Σ
T(TT, T4
1B+1 - 8/l.
(4)
0): min $ Ener (Un - 11)² + 1 Ene ,1, + X |14 - 14//- Let ÿt and J. denote the sample means of the left and right partitions, = Øt - Dr. and let ni and nir be the number of points in each. The optimal values of μt, Mr are:
This penalizes the E, difference between the two consec- utive constant pieces of the shape function fa(zz). It is exactly zero when the shape function fa(za) constant, and is large value if fa(za) is very wiggly and discon- tinuous. It can be viewed as first order discrete deriva- tive of the shape function fa(zz). Another possibility is to penalize the ls measure of discontinuity, but we ex- perimentally observe the & difference producing better re- sults. A similar type of smoothness penalty occurs in fused
Hr = MI 01-
if X(_
Mi = Tt + 1r =r
if
< - X
14 = jrr
otherwise.
(6)
5

---

Generalized additive models via direct optimization of regularized decision stump forests
All leaf parameters. Now two regularization terms will be added to the problem (4):
input training set, initial forest F(:: ①) of T stumps,
roughness penalty X, deviation from bias penalty repeat
T
Mi (Inds < <Tt
]²
2
Optimize all leaves jointly by solving the convex problem (7)
min PAP
Un
1im
2
+ My (Inde 2 Tc)
n=
1=1
for tort=10 to To
+
r( My. ol=d)
Optimize the individual stump s(; 0+)
d=1
through enumeration
until convergence
+ a Σ (14 1)2 (m% 1))2) (7)
return optimized forest F(;
Figure 3. Pseudocode for Optimized Regularized Stump Forests.
The optimization variables μt {ule 14 1=7--1 appear ei- ther linearly or quadratically in the regularization, and the whole problem still remains convex. Instead of de- veloping a specialized algorithm for this problem, we use a generic convex solver. In our experiments, we model the problem using this high-level formulation, and rely on CVXPY (Diamond & Boyd, 2016) to trans- late it into a form acceptable a solver. In our ex- periments we use the MOSEK solver inside CVXPY. To accelerate training, instead of performing the opti- mization over the stump leaves, we can do it over the actual constant pieces of GAMs. That is, we switch from the stump forest representation to its equivalent GAM form. This change reduces the number of opti- mization variables by a factor of two. After solving for the constant pieces of the GAM, we convert the result back to the stump forest representation. The leftmost stump has leaf values 1 = fn and 1 = 33. For sub- sequent stumps with index i > 0 we set the left leaf to 4 = 0 and the right leaf to 1e = 3. - - 1- In other words, the left leaf is always O, and the right leaf cap- tures the difference between adjacent constant values. It is straightforward to verify that this reconstruction yields function equivalent to the original GAM.
We compare with the following established baselines for GAMs: explainable boosting machines (EBM) (Lou et al., 2013), gradient boosting (GB) with stumps, traditional cubic splines (implementation in Python (Servén & Brummitt, 2018)), neural additive models (NAM) (Agarwal et al., 2021). fused lasso additive models (FLAM) (Petersen et al., 2016), and FastSparse that learns piecewise constants GAMs with lo-penalty on specially bi- narized features. We tune the important hyperparameters of all the baselines on a holdout set, and with the best found hyperparameters we repeat the experiment 5 times on dif- ferent training/test splits to report mean and standard devia- tion. In our method, ORSF, for regression problems we use the squared error, and for binary classification we use the cross entropy loss with the logistic link function. The spe- cific details of the implementation, code, hyperparameter values and the datasets are provided in appendix C.
Table 1 shows the results on regression datasets. Across all the problems, regularized stump forests achieve com- petitive accuracy as some of the established of baselines for GAMs. Importantly, among the tree/stump based methods, our approach uses far fewer number of parameters than the GB, and especially, EBM. Boosting methods work by greedily adding trees/stumps with a small learning rate, typically requiring many boosting iterations to converge. This results in large number of trees/stumps and corresponding GAM shape functions with many con- stant pieces. In contrast, our approach properly optimizes stump forest and controls its complexity with regulariza- tion. As result, hundreds of well-optimized stumps in our method match the performance of the thousands of stumps in GB and the tens of thousands of trees in EBM.
The proposed regularization terms control effectively the overfitting problem. In the right plot of fig. 1 we can ob- serve how penalizing the f--disconinnutyy helps in reducing the gap between training and test errors, and the resulting models are more accurate than the GB on the test set. In the second (from the left) plot in fig. 2 we see how these regu- larizations help produce smoother stumps forests in the ID example. We refer to our Optimized Regularized Stump Forests as ORSF. We provide its pseudocode in fig. 3.
Table 2 presents results on classification problems. The general trend is qualitatively similar to the regression case. Interestingly, traditional cubic splines show much better results here, often outperforming GB and EBM results. Splines have rich history in statistics and possess many good theoretical properties. They also use much fewer number of parameters (degrees of freedom) while still be- ing accurate. In the literature of GAMs, the importance of splines cannot be neglected.
5. Experiments
5.1. Comparison on Benchmarks
Our experimental results consistently show the improved accuracy of optimized stump forests across multiple bench- marks in both classification and regression tasks. More of- ten than not, our optimized forests require fewer number of stumps, and thus fewer number of parameters overall.
6

---

Generalized additive models via direct optimization of regularized decision stump forests
Table Train and test RMSE, model size (number parameters) and training time (average + standard deviation over runs) for different GAMs. N refers to the dataset size. D is the feature dimension. Green color is the best test error. and blue is the second best.
Dataset
ORSF
GB
EBM
Splines
NAM
FLAM
FastSparse
Cpuact N= D=21
train
2.12110.01
2.20+1004
0.002
2.53
3.38
2.88 2.99.10.05
2.76=00.3
test
2.37=00.03
2.43+00.6
2.50=00.5
2.69-00.66
3,41
2.91-0.17
size
642.10
1.3
16.6k
271:13
134KL0
17.9
119.14
time (s)
9,4
46:-17
39:22
0.:10.03
99
85122
3.8=0.5
Wine
train x10-2
65.70++0.15
68, 68.13+00.27
66.73+0.27
0.299
74,40+0.16
67.39.L0.21
68.01+0.25
N=6.5k
test x10-2
00.02+00.66
70.92+00.51
70.12+0.339
71,79+
76.07+2.111
70.19:H0.84
71.77+00.33
D=11
size
724::12
770
3.9k=11
197+7
70.
5041+11
182:+4
time (8)
6,0+00.3
2.87=00588
1.34
56-116
64
53113
0.57=0.07
Housing 2=
train x10-2
51.84:10.16
54,24
52.70-10.04
53,37.10,21
7..56
55.08:10.20
54.62.10.20
x10
54.80::0.65
56.15
55.23=0.68
55,49=0.61
0..23
56.24410.74
56,29
D=8
size
1,4
2,4
7.2k
528
51.0k
118
579.19
time (s)
13.6
42:18
36:22
37:12
175.22
73:22
0.73
Diamond
train x00
9.95=0002
10,07=0.05
10.11=0.003
10,02=00.02
13.53
11.75.10.03
10.01+00.02
N=54k
test x10*
10.15+00.08
10.19+0..08
10.23+0.06
10.96
13,59+0025
11.70:L0.12
10.17+0.099
D=26
size
934-116
1182
3.4k
273+:24
86k
4139-H12
516111
time (s)
25.1
140+:58
20#22
42+00.4
708+2
805
45=10
Year N=423k
train
9.12-10.03
9.30
7.53
9.14
10.02
9.14
test
9,30-10.01
9,,50
9.82-20002
9,38-0003
10.22-1000
out time
9.29-0.01
D=90
size
13791.0.8
1490
368K
2158
573k
> 2 days
2601
time (s)
1402.1.43
4368
4262:1433
36181145
8858
973.165
FPS
train
55.40+10.09
55,48
55.42=00.09
$5.41
56,23-+0110
55,411:0.09
N=101k
test
55.41+0.34
55.45+0033
55.42+0.34
55,42-0.34
55.62-00.24
out of time
55,42++-.34
D=100
size
983+:37
824 1803-446
12
111+1
28
> 2 days
1250+
time (s)
798+-21
655-84
2043#22
4397=110
625++10
epuact, training set
epuact, validation set
FICO, training set
FICO, validation set
75
ours, 0
ours, À =
Validation 0/1 accuracy (%)
ours, 10
ours, À 10
ours, 20
ours, À 20 18,4
Training RMSE
2.3
fs. 10
Validation RMSE
fs. 7 10
Training 0/1 accuracy
2.2
[s. 10
2.7
1s.
10TH
73
73
fs. 0
2.6
72
" ours, = 0
ours, À =
72
2.5
a ours, 10
ours, À 10
71
ours, = 20
-ours, À -0
2.4
? 10 -
fs. ? 10 10-3
71
10
[s, 7 10-5
23
fs, Exp-1.0
fs. Exp-1.0
1.7
2.2
70
69
200
400
600
800
1000
200
400
600
800
1000
50
100
150
200
100 150
200
model size
model size
model size
model size
Figure 4. Comparison on CPU Activity regression and FICO classification datasets of the regularization paths generated by our method versus FastSparse (fs).
5.2. Regularization Paths over Number of Stumps
as multiple fo-penalty values often result in the same solu- tion. contrast, our method provides more direct control over model size through the number of stumps T, effec- tively enforcing an to constraint. Our regularization path includes 100 distinct models, though only 50 are displayed in the figure to maintain clarity, More detailed results of this comparison is available in Appendix fig. 7 and fig. 8.
In our approach, we construct "regularization" path by starting with small number of stumps and incrementally adding more, re-optimizing the entire model at each step. In fig. 4, we compare the regularization paths of our method with those of FastSparse, which generates its path by vary- ing a sequence of fo-penalty parameters. On the epuact re- gression task, our method achieves superior generalization performance, benefiting from the é roouhgeessss regulariza- tion penalty. For the FICO dataset, the performance of both methods is comparable. It is worth noting that although both methods generate 100 models along the regularization path, FastSparse typically produces fewer unique models,
5.3. Effect of Different Regularizations
In fig. 5, we examine the individual effects of three dif- ferent types of regularizations on stump forests using the CPU activity dataset. As expected, all regularization meth- ods exhibit typical behavior: increasing the regularization
7

---

Generalized additive models via direct optimization of regularized decision stump forests
Table As Table
for classification datasets. The enror a 0/1 misclassificatiin (%)
Dataset
ORSF
GB
EBM
Splines
NAM
FLAM
FastSparse
Letter
train
15.94 16.40+0.52
16.38
16.12:+0.20
15.87=1.144 16.55=0.70
21.54
17.94
15,88
20
test
16.88=00.41
16.63++0.2
22,53++1.88
17.95
16.57+
D=16
size 133++13
450+
502+
224
68k+0
510-22
399+5
time
14.9=0.2
32:#3
31
58422
153:10
71:1
18:2
Churn
train
18.88 10.19
19.00.1..23
1..00
10.18
22.59
19.85=0.18
18.88 10.10
N=7.0k
test
19.28.10.29
19.32.10.37
19.47:0.51
19.32:10.48
21.69
20.30=:0888
19.87
D=45
size
1294:5
6444-48
7292:111
40410.04
120K
13.7k
105+:8
time (8)
6.8.10.4
3.11
15.11
0.5.0.033
120.12
113:2
0.59.10.07
FICO
train
04.8
26.54=00.15
26.37=+0.10
26.79+00.15
28.23+:0.41
27.15
25.87++0.16
N=10k
test
27.33:10.04
27.62.10.30
27.33
27.35
18.08
27,64+0.52
27,80
D=23
size
550.128
1002.166
3680.19
83.11
130K
3791
196.110
time
7.8+0.1
1.6+0.6
74002
1.96:00110
180
61+1
1.74::0.12
LJCNN
train 4.42+00.05
4.56=+0.07
+.50
0.44
7.51
6.86
4.84
N=50k
test
4.95
5.10=0.15
5.00
4,92+0.20
7,48
7.14
5.52+-021
D=22
size 414:1:33
918:21
12.3K
266:10.5
10IK
824
883:118
time
46:+1
148#+24
19+0
153+:40
501
24916
47+1
Covtype
train
22.50.10.03
22.56110.02
22.46.10.02
22.48-10.02
26.16.0.50
22.49110.02
N=581k
test
20.71
22.77::0.10
22.68:10.12
22.72:10.10
26.08
of time
22.68::0.100
D=54
size
504
1090.132
6402.L4
403.11
170k
> 2 days
841
time (8)
10911116
1202.149
32511
15624.184
5373
2763-1177
Bank
train
9.814
10.00=00.03
9.75+-0.05
9.79-10.04
10,09=00.08
11.27-10.04
9.79-L0.04
N=11k
test
9783+00117
9,99+0.13
9.91+0.17
9.88+0.12
0.87=0022
11.23
9.86+ 14
D=62
size
231+t4
530+115
1103
95::2
174k
1182+11
64:t4
time
4712
3417
4013
22::2
662:110
916
19.6133.
Test
2.89
Train
2.8g
2.8g
2.6
2.6
2.6
2.4
2.4
2.2
2.2
Test Train
Test Train
20
2
0
20
100
10
30
0
20
40
60
E1-discontimiity rogularization.
fa-discontinuity regularization, À
deviation regularization.
Figure 5. The effect of different regularization types in stump forests for the cpuact dataset. The number of stumps T 200. For our final method use the combination of E1-discontinuity and the deviation from the bias regularizations.
penalty initially results in high test error due overfitting, followed by decrease the lowest test error indicating the best generalizable models, and finally, an increase in test етror due to underfitting as the penalty becomes too strong. We can also observe the good ranges of the hyper- parameter values, for example, the deviation from the bias penalty typically favors small values of the penalty parame- ter a. When comparing the importance of these methods on the test error, the & fi-roughness penalty usually produces models with the lowest test eитог than the other two. In our main experiments we use the combination ε didiiscontyyuity and the deviation from the bias regularizations.
Used Car Data set, which features used car listings in UK, grouped by different manufactures. To avoid the large number of car make/model categories when visualizing, we focus on the following popular models: BMW 3 series, Mercedes C Class, Volkswagen Golf, Ford Focus, Hyundai Tueson and Toyota Yaris. The total number of training points is 15,200 with additional 3,800 instances used for testing. The following features describe a given car: the year of manufacture, mileage (a total number of miles trav- eled), amount of yearly tax, miles per gallon (MPG), en- gine size, make/model, transmission type and fuel type. The first features are numerical, and the last 3 are categorical.
5.4. Case Study: Car Price Prediction
We train our forest with 700 stumps and a roughness penalty of X 60. The model achieves a mean absolute error (MAE) of $1,600 on the test set. Considering the av-
To showease the interpretability stump forest additive models, we use the problem of predicting the price of used car. From the Kaggle platform obtain 100,000 UK
8

---

Generalized additive models via direct optimization of regularized decision stump forests
x10
110
0.5
Price. (5)
0.5
Frsqurtc
0.5
4..
10.5
-1.6
2002
2006
Year
2010
2014
2018
Mileage
x10P
-15
200
Tax
400
600
100 MPG
150
200
X10"
190
Price, (9)
Price,
Hyunda Tucoon
Monedes C
Fond Foxus
Toyotu Yans
VW Colf
Automalic
BMW 3
Manual
Dieeel
Patol
0.5
Engine size
Model
Transmission type
Fuel type
Figure 6. Visualization of the resulting additive model shape functions from our optimized stump forests for the UK used car dataset. For
the numerical features, the light red bars show the histogram the training points with the frequency values given on the right y-axis.
erage price is f16,900 with standard deviation of $7,600 on the whole dataset, this error margin is relatively accept- able. And the model is much more accurate than a linear regression which has a test MAE of E2,200. Most impor- tantly, we can visualize the entire model plots for the 8 used features in fig. 6, and interpret it. There also constant bias term, but we eliminate it by distributing its value to the 3 categorical features.
model, we can understand it, and possibly even debug and correct the parameters and/or the dataset. This example on car price prediction clearly demonstrates the inherent in- terpretability of additive models. Appendix figs. 9 and 10 show the shape functions for the other GAMs, EBM and PyGAM. Overall, the general trend in EBM shapes is quite similar to the ones obtained by method and also be- ing similar in accuracy (around 2,200 test RMSE), although it generated an overly noisy curve for the mileage feature. PyGAM, on the other hand, generates very smooth curves, and behaves quite unpredictably in regions with less or no data.
We expect newer cars to be more expensive, and the shape function of the year feature generally confirms this expec- tation. There is an unexpected negative correlation with prices for the years 1999-2001, but this anomaly is due to having only six listings from those years. Another cru- prices is mileage; typically, cars with higher mileage are cheaper. The shape function for mileage supports this relationship. However, there is an unusual slight drop in price around 50,000 miles. closer examination of the dataset reveals an outlier: a Mercedes C-Class with 52,700 miles listed at f2.140, whereas the normal price for this model is about $00,000. Miles per gallon (MPG), which characterizes fuel consumption, is an- other significant predictor variable. Its shape function gen- crally shows a negative relationship with price. In the train- ing set, we find newer Mercedes C-Class cars with engine sizes of 4.0 and 6.3 that have low MPG but are very expen- sive. Additionally, there are noisy points with mislabeled MPGS, such eight newer BMW Series cars with MPG of 8.8, which should have been 30.0. Regarding cate- gorical features, the distribution of prices within each cate- gory appears to be reasonable: luxury brands like Mercedes and BMW are more expensive, cars with manual transmis- sions tend to be cheaper, and hybrid fuel types are usually more expensive. Overall, by visualizing and analyzing the
cial feature in predicting
6. Conclusion
We have presented a novel approach to learning forests of axis-aligned decision stumps, with its equivalent view of generalized additive model. Instead of bagging and boost- ing, we use alternating optimization to learn a fixed-size stump forest. This makes it possible to optimize exactly at each step the stump parameters by enumeration and jointly optimize the leaf values by solving a convex problem. To mitigate overfitting, we introduce effective regularization techniques that take into account the global smoothness func-
of the model when viewed piecewise-constee tion. These regularized stump forests exceed the accuracy of state-of sfate-of-the-arr GAM methods, yet with fewer parame- ters. Our approach is pioneering in that learns stump forests without the need for traditional ensembling tech- niques such as bagging or boosting, and in that it can be initialized from existing forest, thus making retraining possible. A possible future research direction is define global amoothness-based regularization methods to learn more general, parametric decision forest of a fixed size.

---

Generalized additive models via direct optimization of regularized decision stump forests
Acknowledgements
Diamond, S. and Boyd, S. CVXPY: A Python-embedded modeling language for convex optimization. J. Machine Learning Research, 17(83):1-5,200
Work partially supported by NSF award IIS-2007147.
Impact Statement
Eilers, P. H. C. and Marx, B. D. Flexible smoothing with B- splines and penalties. Statistical Science, 11(2)889-21, May 1996.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Eilers, P. H. C. and Marx, B. D. Splines, knots, and penalties. WIREs Computational Statistics, 2(6):637- 653, September 2010.
References
Freund, Y. and Schapire, R. A decision-theoretic general- ization of on-line learning and an application to boosting, J. Computer and System Sciences, 55(1):119-139) 1997.
Agarwal, R., Melnick, L., Frosst, N., Zhang, X., Lengerich, B., Caruana, R., and Hinton, G. E. Neural additive mod- els: Interpretable machine learning with neural nets. In Ranzato, M., Beygelzimer, A., Liang, P., Vaughan, J. W., and Dauphin, Y. (eds.), Advances in Neural Information Processing Systems (NeurIPS), volume 34. MIT Press, Cambridge, MA, 2021.
Freund, Y. and Schapire, E. Experiments with new boosting algorithm. In Saitta, L.. (ed.), Proc. of the 13th Int. Conf. Machine Learning (ICML'96), pp. 148-156, Bari, Italy, July 3-6 1996.
Breiman, L. Fitting additive models to regression data: Di- agnostics and alternative views. Computational Statis- tics and Data Analysis, 15(1):13-45 January 1993.
Friedman, J. H. Greedy function approximation: A gradi- ent boosting machine. Annals of Statistics, 29(5):1 189- 1232, 2001.
Breiman, L. and Friedman, J. H. Estimating optimal trans- formations for multiple regression and correlation. Amer. Stat. Assoc., 80(391) ((8891) (with comments, pp. 598-55888 619), September 1983.
Friedman, J. H. and Popescu, B. E. Predictive learning via rule ensembles. Annals of Applied Statisties, 2(3):166 954, September 2008
Gabidolla, M. and Carreira- Perpiñán, M. Á. Pushing the envelope of gradient boosting forests via globally- optimized oblique trees. In Proc. of the 2022 IEEE Computer Society Conf. Computer Vision and Patten Recognition (CVPR'22), pp. 285-294, New Orleans, LA. June 19 24 2022.
Breiman, J. Bagging predictors. Machine Learning, 24 (2): August 1996.
Breiman, L. J., Friedman, J. H., Olshen, R. A., and Stone, J. Classification and Regression Trees. Wadsworth, Belmont, Calif,, 1984.
Carreira-Perpiñán, M. Á. and Tavallali, P. Alternating op- timization of decision trees, with application to learn- ing sparse oblique trees. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Gar- nett, R. (eds.), Advances in Neural Information Process- ing Systems (NeurIPS), volume 31, pp. 1211-1221. MIT Press. Cambridge, MA, 2018.
Gabidolla, M.. Zharmagambetov, A., and Carreira- Perpiñán, M. Á. Improved multiclass AdaBoost using sparse oblique decision trees. In Int. J. Conf. Neural Net- works (IJCN' 22),, Padua, Italy, July 18-22 2022.
Hastie, T. and Tibshirani, R. J. Generalized additive mod- els. Statistical Science, 1(3):297-318 (with comments), August 1986.
Carreira-Perpihán, M. Á. and Zharmagambetov, A. Ensem- bles of bagged TAO trees consistently improve over ran- dom forests, AdaBoost and gradient boosting. In Proc. of the 2020 ACM-IMS Foundations of Data Science Confer- ence (FODS 2020), pp. 35-46, Seattle, WA, October 19- 20 2020.
Hastie, T. J. and Tibshirani, R. J. Generalized Additive Models. Number 43 in Monographs on Statistics and Ap- plied Probability. Chapman & Hall, London, New York, 1990.
Ibrahim, S. Afriat, G., Behdin, K., and Mazumder, R. GRAND-SLAMIN' interpretable additive modeling with structural constraints. In Oh, A., Naumann, T. Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information P Processing Sys- tems (NeurIPS), volume 36. MIT Press, Cambridge, MA, 2023.
Carreira-Pente Perpiñán, M. Á., Gabidolla, M., and Zharmagam- betov, A. Towards better decision forests: Forest Alter- nating Optimization. In Proc. of the 2023 IEEE Com- puter Society Conf. Computer Vision and Pattern Recog- nition (CVPR'23), pp. 7589-7598, Vancouver, Canada, June 18-22 2023.
10

---

Generalized additive models via direct optimization of regularized decision stump forests
Johnson, and Zhang, Learning nonlinear functions using regularized greedy forest. IEEE Trans. Pattern Analysis and Machine Intelligence, 366))992-44 May 2013.
Sorokina, D., Caruana, R., and Riedewald, M. Additive groves of regression trees. In Kok, J. N., Koronacki, J., López de Mántaras, R., Matwin, S., Mladenic, D., and Skowron, A. (eds.), Proc. of the 18th European Conf. Machine Learning (ECMI-07)) pp- 323-334, Warsaw, Poland, September 17-21 2007.
Kim, S.-J., Koh, K., Boyd, S., and Gorinevsky, D. & trend filtering. SIAM Review, (2)33339-360 2009.
Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., and Knight, K. Sparsity and smoothness via the fused lasso. J. Statistical Society B, 67(1):91-108, February 2005.
Lichman, M.
UCI machine learning repository.
http:/ /t////areee aaraarccvvveeeeeeeeeeeeaeeeeeeee ics. wec.suciieese edumm 2013.
Liu, J., Zhong, C., Seltzer, M., and Rudin, C. Fast sparse classification for generalized linear and additive mod- els. In Camps- Valls, G., Ruiz, F. J. R., and Valera, (eds.), Proc. of the 25th Int. Conf. Artificial Intelligence and Statistics (AISTATS 2022), pp. 9304 9333, Online, March 28-30 2022.
Viola, P. and Jones, M. J. Robust real-time face detection.
Int. J. Computer Vision, 57(2):137-154, May 2004.
Wood, S. N. Thin plate regression splines. J. Statistical
Society B, 65(1):95-114, February 2003.
Wood, S. N. Generalized Additive Models: An Introduc- tion with R. Texts in Statistical Science. Chapman & Hall/CRC, second edition, 2017.
Lou, Y., Caruana, R., and Gehrke, J. Intelligible models for classification and regression. In Proc. of the 18th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Min- ing (SIGKDD 2012). pp. 150-158, August 21-24 2012.
Zharmagambetov, A. and Carreira-Perpinaal M. Á. Smaller, more accurate regression forests using tree al- ternating optimization. In Daumé III, H. and Singh, A. (eds.), Proc. of the 37th Int. Conf. Machine Learn- ing (ICML 2020), pp. 11398 1 1408, Online, July 13-18 2020.
Lou, Y., Caruana, R., Gehrke, J., and Hooker, G. Accu- rate intelligible models with pairwise interactions. In Proc. of the 19th ACM SIGKDD Inf. Conf. Knowledge Discovery and Data Mining (SIGKDD 2013), pp. 623- 631, Chicago, II. August 11 14-14220 2013.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, É. Scikit-learn: Machine learning in Python. J. Machine Learning Research, 12:2825-2836 October 201 1. Avail- able online at https: /tap:s:://cciiee scikit- learn. org.
Petersen, A., Witten, D., and Simon, N. Fused lasso ad- ditive model. Journal of Computational and Graphical Statistics, 25(4):1005-1022 2016.
Radenovic, F., Dubey, A., and Mahajan, D. Neural basis models for interpretability. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Sys- tems (NeurIPS), volume 35, pp. 8414 8426. MIT Press, Cambridge, MA, 2022.
Ruppert, D.
Selecting the number of knots for penalized splines. Journal of Computational and Graphical Statis- tics, 1 11(4):335-755 111355-777,Ja0 January 2002.
Sadhanala, V. and Tibshirani, J. Additive models with trend filtering. Annals of Statistics, 4766):303233688, 2019.
Servén, D. and Brummitt, C. pyGAM: Generalized addi- tive models Python, 2018.

---

Generalized additive models via direct optimization of regularized decision stump forests
A. Limitations
In this paper we focus only on univariate shape functions fa( but using bivariate interactions fyy (Zz, 2y) could provide more accurate results. However, such pairwise terms are somewhat less interpretable, and the total number of such terms grows quadratically with the feature dimension. Perhaps extending this work to include 2epth-2 trees that model bivariate interactions can be one possible future direction. One possible limitation is in comparison with traditional splines that typically use fewer number of parameters. However, tree/stump-bastt based methods tend to be more accurate as demonstrated here, and in the previous literature (Lou et al., 2012). And compared with models of the same family of stumps/trees (GB and EBM), our models are much smaller.
B. A Additional Experiment Results
Fold 1
Fold 2
Fold 3
Fold 4
Fold 5
ouus, A
0
oours,
10
2.0
2.0
2.
Validation RMSE
rours,
A
20
2.8
fs. ?
10
2.8
2.8
2.8
2.8
Is.
10
227
Ispaty
2.7
2.7
2.7
2.7
2.6
2.6
2.6
2.6
2.5
2.5
2.5
2.4
2.4
23
2.3
2.3
2.8
2.3
22
2.2
2.2
2.2
22
1000
600
model size
model size
model size
model size
model size
25
ours, A=
0
2.5
25
2.5
2.5
6
2.4
<ours, 10
2.4
2.4
2.4
2.4
oours.
20
RMSS
I'.
10
2.3
2.3
2.3
fs. 7
10
Training 1
fs,
0
2.1
2.1
2.1
2
2
2
1.9
1.9
1.9
1.9
1.9
1.8
1.8
1.8
1.8
1.7
1.7
200
400
600
800
1000
200
400
600
800
1000
200
400
600
300
1000
200
400
600
800
1000
200
400
600
800
1000
model size
model size
model size
model size
model size
Figure 7. Five-fold cross-validation comparison the CPU Activity regression dataset of the regularization paths generated by our method versus FastSparse (Is). In our approach, the regularization path is constructed by starting with an empty forest and incrementally adding 5 stumps at time, re-optimizing the entire forest at cach step using our algorithm. We present three curves corresponding to different values of the roughness penalty parameter À E {0, 10, 203. For FastSparse, we show results for three different values of the parameter 7 E (0, 10 5 31.-3. We set the num Lim__aame Lambda parameter to 100 and max_ leop__supoot_____ ssiiee_s_eeee to 1000, which generates a regularization path across 100 different lambda_0 values. However, the actual number of unique models produced by FastSparse is typically lower, as multiple values lambda_0 often lead to the same model. In contrast, our method allows for more direct control over model size via the number of stumps T, effectively imposing an lo constraint. Our regularization path consists of 100 distinct models, although only 50 are shown in the figure to avoid visual clutter. The model size here is defined as the number of thresholds times 2 (a constant piece value and threshold) plus for the bias.
C. Experiment Details
For all algorithms, including ours, we tune the important hyperparameters on holdout set, and with the best found hyperparameters perform 5 experiments different train/test splits to report mean and standard deviation.
Implementation of our algorithm We implement our algorithm in the combination of Python and C++. The optimiza- tion step over each stump is implemented in C++. The convex problem of joint leaf fitting is implemented in Python. We use the CVXPY open source Python package (Diamond & Boyd, 2016) to model the leaf fitting problem using high-level formulation, and rely on the library to convert/compile it into a specific solver form. As a convex solver inside CVXPY, we use MOSEK, a large scale optimization software. We use CVXPY version 1.4.3, and MOSEK version 10.1. We per-
12

---

Generalized additive models via direct optimization of regularized decision stump forests
Fold
Fold
Fold 3
Fold
Fold
75
75
75
75
Validation NO aecurr Suuraay (%0
73
72
72
72
72
oours, -ours.
0
71
71
IS. 10
10
IS, Exp-LO
69
69
69
100
150
200
80
100
150
200
50
100
150
200
100
150
200
50
100
150
200
model size
model size
model size
model size
model Size
Training 0f1 accuracy (56)
74
74
74
23
73
73
73
73
ours, À
ourr,
0
72-
72
72
ours,
Is.
Exp-LO LO
100
150
200
60
100
150
200
50
100
150
200
100
150
200
50
100
150
200
model size
model
model
model size
model size
FICO classification dataset. For our method, we generate regularization path by incrementally adding one stump at time and re-optimizing the current forest using algorithm, continuing until the forest contains 100 stumps. To reduce visual clutter, we display only 50 points from our regularization path. For FastSparse (fs), following Fig.8 from their paper, report results for logistic loss with two different values of y {10->, 10-3), and for exponential loss with penalty=IO. We run the regularization path with num_ 1ambda=100 and similarly as with fig. 7, we obtain a fewer number of unique models because multiple values Lambda produce the same result.
Figure Same setup as Fig. but applied
x10*
x101
0.5
0.5
Price (
0.6
0.5
0-
-15
-0.5
2002
2006
Year
2010
2014
2018
Mileage
X10
-1.8
200
Tax
400
600
MPG
100
100
1110
1990
1900
1000
Price, (5)
Price,
00.5
BMW
Mercedes
Foed Foens
Hyandal
Loyeta
VW Golf
Automaaic
Semi- Auto
brid
Potol
Engine size
Model
Transmission type
2
Fuel type
Figure 9. As fig. 6, but for EBM shape functions.
form grid search on the following hyperparameter values: number of stumps 1200, 400, 600, 800), roughness penalty = (2.0, 4.0, 6.0} for classification datasets, À = {20.0, 40.0, 60.0) for regression datasets. We do not tune the deviation from bias hyperparameter a, and use the fixed value a = 0.1. As an initial stump forest we use stumps with random parameters.
13

---

Generalized additive models via direct optimization of regularized decision stump forests
x10
10000
Frequecicy
Price.
2002
2006
Year
2010
2014
2010
Mileage
x10
200
Tax
400
500
100 MPG
190
200
x'10
1900
1900
Price, (8)
Price
600
BMW
Merodtes
Fool Focus
Myandal
VW Goll
1200
Automatic
Semi Auto
Hybeid
Penoi
Engine size
Model
Transmission type
Fuel type
Figure 10. As fig. 6, but PyGAM shape functions.
Hardware Except the Neural Additive Model (which is trained on a GPU), all experiments are performed on a CPU Intel(R) Xcon(R) CPU E5-2699 v3 @ 2.30GHz, 128 GB RAM.
The specific details of the baselines and tuned hyperparameters:
Gradient Boosting (GB): we use the scikit-learn's 's implementation: GradientBoosiingRRgersso and GradientBoosting: Classifier (Pedregosa et al., 2011). We set the maximum depth to and perform grid search on the learning rate (0.01, 0.05, 0.1, 0.3}. We set the number of boosting iterations (n_est imators) to a very high number (10%), and use early stopping based on validation set with iter no ho__hhaggeeeeee equal 100. The version of the scikit-learn 1.4.2.
Explainable Boosting Machine (EBM):
the official implementation from the interpret Python library'. We perform grid search on the following hyperparameter values: learning_rater (0.005, 0.01, 0.05), max_binss (512, 1024, 2048), mim_miimsaaann s_ : (2, 4, 8). We set the interactions parameter to 0 to use only univari- __leff:
ate terms, max rounds is set to 25 000 with eearl_sstoppilleeeeeaaeeaaaeeape poouddddnnrruds 50. The version of the interpret package is 0.
Splines:
we use the PyGam package² in Python. We perform grid search on the following hyperparameters: strength of the smoothing penalty = (0.001, 0.01, 1, 10, 100, 1000, }. and the number knots = {10, 20, 50, 100). The version the PyGam package is 0.9.1.
Neural Additive Model (NAM):
we use the paper's (Agarwal et al., 2021) official implementation'. As in their paper, we try two types of architectures: MLP with 64-64-32 ReLU layers and 1024 Exu layer. We perform grid search on the following hyperparameters: dropout (0.0, 0.1. 0.3, 0.5), weight decay {10 -6 10-5 10 10-4), learning rate (0.001, 0.01, 0.1). We use a batch size of 1024 and train for 100 epochs. Only for this baseline we train it on an NVIDIA TITAN GPU,
F Fused Lasso Additive Model (FLAM): is nonparametric model that uses discrete first derivative matrix to penalize the roughness of the piecewise constant predictions. We use the official implementation" in R. We set the a parameter to as feature selection is not the goal here, and only tune the roughness penalty from their default range of 50 values.
additive aediiive_models
f1am/ index, html
14

---

Generalized additive models via direct optimization of regularized decision stump forests
FastSparse: We use the Python package
fastsparsegams.
We use the method
convert_cone crontinnouu_d__to tt___tttbiinrr_ttt binarize the features. We perform grid-search the fol- lowing values of hyperparametens: algorithm= = [CD, CDPISI], mts__lp.ap_pppppppea support_sizee = [10, 100, 1000, 10000), and the 100 À values in regularization path (we set n.um 1 ambda 100, and scan through the model. lambda values after training). For the pene Ity parameter, we use I.O. For classification, we use Logist i as the loss,
Estimation of the number of parameters. For piecewise-constant models (ours, GB and EBM), we estimated the number parameters as the number of constant pieces times 2 summed over each shape function. This is because we must store the piece value, and where the piece ends. For the neural networks (NAM), we just report the number of parameters in the network architecture. And for the FLAM, because it is non-parametric, we report the size of the training set, more specifically, the number of unique feature values summed over per each dimension.
Regression dataset description:
Cpuact The goal is to estimate the percentage of time CPU operates in user mode. The fea- tures are various statistics related to memory and other activities. Source is the Delve project: cs. ttt.rottt...eeeeeeeeee///aaaaaaa
Wine The task is to predict the wine quality from 0 (very bad) to 10 (very excellent) based on the attributes as acidity, sugar, chlorides, etc. Obtained from the UCI ML repository (Lichman, 2013).
Housing California Housing dataset, standard regression benchmark. fetch_cal wel.callforiaa hourssiaahhuiii function.
Obtained through the scikit-learn's
Diamond The task is to predict the price of diamond based the characteristies of clarity, carat weight, etc. We download it from the OpenML dataset repository: https:// http:://www.opemm...m.m wttp://eerrcittypeaaataaaaaee sortruuuuss waw.:mmssddd222sstttssseeee
Year predicting the release year of song from audio features. Obtained from the UCI ML Repository (Lichman, 2013).
FPS the goal is ties of a CPU, GPU and the game itself. https://wwi openml. "userbenchmark" source, and discard the "fpsbenchmark" source. We also drop the columns with missing values. We perform one-hot-encoding for the categorical variables.
predict the frames-per-second in video games based Sourced from the OpenMI. repository: We only use the
characteris-
ve& ve&viddia weeeii=44277 id=42737.
Classification dataset description:
Letter English letter recognition task, available in the UCI ML Repository (Lichman, 2013). We convert into binary classification by combining the letters A-M into one class and the rest to the other class.
Churn The binary classification task to predict which customer will churn. The features are various characteristics the customer. Obtained from Kaggle:
https:/ //www//www/////////////////. kaggle e com
FICO Dataset from the Explainable Machine Learning Challenge. The task to predict whether a consumer pays the credit on time is overdue. The features come from an anonymized credit bureau data. Obtained from the official website:
https:/ c/cmmommmnttt/cc yty fico. com/s explainable-maeeeeeee haw.le--machieeeeaainnneeeeee www.eeennnnchaaallleeeee lengee.
IJCNN The dataset comes from an IJCNN 2001 competition. We obtain it from the LIBSVM binary dataset collection: https:/ /wwww csie ntu. edu. http://cjlinniibbwntttr httettoooosddatttteeeeeeee datasetttsssseseeeeesseeaesse sobintry..iirarrrrre iirry html.
Covtype Classification task of pixels into forest cover types based on attributes such as elevation, aspect, soil-type, slope, etc. We turn it into binary classification by the majority class vs the rest. Sourced from the UCI ML Repository (Lichman, 2013).
Bank the task to predict whether marketing campaign of banking institution is successful or not. The features are various characteristies of customer. Obtained from the UCI ML Repository (Lichman, 2013).
15


Reviews:
[{"review_id": "ajrhmW7ihK", "reviewer": "Reviewer_wGmH", "summary": "The paper introduces a method to fit decision tree stumps per feature, which can be interpreted as a generalized additive model. To mitigate overfitting, the authors propose a smoothness constraint that is optimized jointly with the stump parameters. Unlike approaches such as EBMs that greedily add decision tree stumps, this method requires fewer stumps because it globally optimizes stump placement according to the data. Consequently, the method avoids the need for ensemble strategies like bagging and boosting. The experiments demonstrate comparable performance to Explainable Boosting Machines and other baselines, but using a more straightforward fitting procedure.", "questions": "", "limitations": "", "rating": 4, "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": "Thank you for providing us with a very valuable and insightful review! We greatly appreciate your effort in reviewing our paper.\n\n* **Modeling discontinuities.** You are absolutely right that NAMs (as well as traditional cubic splines) are limited in their ability to capture sharp discontinuities in shape functions. This is a significant limitation in many real-world tabular datasets, where such discontinuities are common due to thresholds, categorical splits, or other sharp nonlinearities in the data. One of the key advantages of the stump-based shape functions, similar to those used in EBMs, is their natural ability to represent abrupt changes locally in the function without inducing unnecessary smoothness. This is also a likely reason why NAMs tend to underperform in our experiments on tabular datasets. We really appreciate your pointing this out, we will incorporate this discussion more explicitly in the introduction to better highlight this advantage of our method.\n\n* **Reaching a global optimum** Although we do not formally prove this result, and cannot easily find a definitive reference establishing it, the problem of learning an optimal decision stump forest appears to be computationally intractable in general. Intuitively, it resembles the well-known best subset selection problem, which is NP-hard. Each decision stump is specified by a feature index and a threshold. However, selecting the best set of $T$ stumps entails choosing an optimal subset of $T$ feature-threshold pairs from a combinatorially large candidate space. For a dataset with $N$ samples and $D$ features, there are $O(ND)$ such candidates, leading to a total search space of size $\\binom{ND}{T}$. This exponential growth in possibilities suggests that the overall problem may be NP-hard, implying that finding a globally optimal solution in polynomial time is unlikely in the general case.\n\n* **Theoretical properties.** Nevertheless, our proposed alternating optimization algorithm has important theoretical properties. Specifically, each optimization step is guaranteed to monotonically decrease the overall objective, and the algorithm converges to a local optimum where no single alternating optimization step can further improve the solution (quite similar to the k-means clustering algorithm). The traditional ensembling methods of boosting and bagging do not provide these type of theoretical guarantees, and lack a well-defined global objective, unlike our more principled optimization framework. The ability of our approach to take an initial stump forest, and optimize it further has the additional advantage of warm-starting behavior: the model can be initialized from an existing forest, such as one derived from any piecewise constant GAM (more on this in our rebuttal to reviewer owkV), and further refined. This also allows for efficient model updates when new training data becomes available (more on this in our rebuttal to reviewer owkV).\n\n* **Shape functions of the other methods.** In https://anonymous.4open.science/r/pdf_to_anon-1CD8/icml25_rebuttal_figures.pdf or https://drive.google.com/file/d/1Xso8hwFd9rB_XqAzH6H8ri7vUbrXEaq6/view?usp=sharing, in figs. 2 and 3, we provide the shape functions for EBM and PyGAM. Overall, the general trend in EBM shapes is quite similar to the ones obtained by our method and also being similar in accuracy (around 2,200 test RMSE), although it generated an overly noisy curve for the mileage feature. PyGAM, on the other hand, generates very smooth curves, and behaves quite unpredictably in regions with less or no data.\n\n* **Pairwise interactions.**  (Lou et al., 2013) uses a two-step approach for building GA$^2$M: first, building univariate shapes, then modeling and including pairwise interactions on the residuals using a variation of depth-2 decision trees. Indeed, we can directly apply a similar strategy, and extend our method to model pairwise interactions. But we believe that it is possible to extend the proposed alternating optimization method to learn an ensemble of both decision stumps and depth-2 trees. Naive implementation of this idea could result in overfitting, and the regularization terms of our current approach is not directly applicable to depth-2 trees. Defining effective regularization techniques for these more complex tree ensembles can be an important future research direction.\n\n* **Distribution of thresholds on the \"year\" feature.** The \"year\" feature is highly discretized, with only 22 unique values ranging from 1999 to 2020. In the higher-density range (2013–2020), nearly all possible thresholds are utilized. In contrast, some thresholds are skipped in lower-density regions—for example, 2005 and 2008 are not used. While decision stumps may appear to concentrate in regions with more data, their distribution is ultimately determined by the optimization process rather than simply by feature density.", "claims_and_evidence": "Yes, all claims of the paper are well supported.", "methods_and_evaluation_criteria": "Yes, all considered benchmarks are classic benchmarks to consider in the GAM literature.", "theoretical_claims": "-", "experimental_designs_or_analyses": "The experimental design seems solid. The hyperparameters of each baseline are optimized using a grid search over several hyperparameters. ORSF performs well throughout", "relation_to_broader_scientific_literature": "This paper proposes a new method of fitting decision tree stumps, which is not a novel model class to be used in GAMs as they are also used prominently in EBMs. However, the fitting procedure discussed by the authors is novel as far as I know. It's intuitive as it globally optimizes the loss function.", "essential_references_not_discussed": "I am not aware of any missed references.", "other_strengths_and_weaknesses": "### Positive:\n- The framing of learning the decision tree stumps using a global optimization approach rather than a greedy method is well motivated. The problem with overfitting is illustrated well and the proposed regularizer is intuitive to understand.\n- Unlike Neural Additive Models the proposed approach can easily model discontinuities in the shape functions like EBMs which NAMs struggle to. I think the authors could emphasize this even more because discontinuities can often occur in tabular data and the GAM should be able to represent this.\n- The paper is well written and easy to understand.\n\n\n### Weaknesses:\n- Could you provide a theoretical justification or discussion about whether the proposed alternating optimization approach can reliably reach a global optimum?\n- Could you also show the shape functions of the other methods for comparison?\n- You might consider incorporating pairwise interactions by applying the same strategy used by EBMs to identify dominant pairwise effects (Lou et al., 2013). Using similar pairwise effects would allow an additional comparison point with EBMs.\n\n### References:\n- Lou, Y., Caruana, R., Gehrke, J., & Hooker, G. (2013, August). Accurate intelligible models with pairwise interactions. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 623-631).", "other_comments_or_suggestions": "-", "questions_for_authors": "My understanding is that your method implicitly places more stumps in regions with higher data density, which is typically the case. However, Figure 5 (feature \"year\") shows a surprisingly uniform distribution of thresholds. Could you clarify why this occurs?\n\n## update after rebuttal\n- The authors addressed all of my questions and looking at the other two reviews I have no further questions.", "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": "", "extra_scores": {}}, {"review_id": "ZnBA18OmCK", "reviewer": "Reviewer_r73Z", "summary": "This paper proposes an alternating optimization method for training an additive model composed of decision stumps. The optimization procedure alternates between two steps: (1) selecting a feature and determining the optimal split value for a decision stump, and (2) jointly optimizing all coefficients through a convex optimization solver. The method incorporates a regularization term to penalize the roughness of the coefficients, which helps control model complexity. The authors claims that their approach effectively reduces the number of stumps while maintaining both training and test performance.\n\n## update after rebuttal\n\nI want to thank the authors for replying to my second round rebuttal comments. I have also read the reviews and rebuttal comments by other two reviewers.\n\nThe mathematics behind individual stump optimization makes sense to me. This should be included in the paper (at least in the Appendix) during revision.\n\nThe new plot on the FICO dataset (Figure 2) included in the anonymous link also looks reasonable to me. This figure should be included during revision. I think the reason for FastSparse of having a larger support size than I expected is on your Fold 4, somehow the sparsity wasn't optimized around 20 features. This wasn't my experience, but maybe it has something to do with your particular 5CV split or the feature binarization preprocessing step.\n\nSince my major concerns are addressed, I no longer have a big problem against this paper getting accepted. I am raising my evaluation to score of 3, above the acceptance threshold.", "questions": "", "limitations": "", "rating": 3, "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": "Thanks for providing an insightful and constructive review! We greatly appreciate your effort in reviewing our paper.\n\n* **Claim on novelty.** To be precise, the only place we make a claim of doing something for the first time is with respect to ***learning stump forests with good generalization without ensembling techniques of boosting and bagging***.  At no point do we claim \"to be the first to introduce a generalized additive model\". Regarding reference [1], we acknowledge it as an important and relevant contribution. However, the main focus of [1] is not about decision stumps/trees but about learning sparse linear classifiers efficiently. The GAMs in [1] are introduced by learning a linear model on transformed features, where continuous variables are replaced with a set of binary indicators based on thresholds. We will include [1] in our literature review. We have already conducted empirical comparisons with [1] and updated our results table accordingly (see below).\n\n* **Unconvincing improvements compared to splines.** We acknowledge the concern regarding the magnitude of performance improvements. However, we would like to emphasize that GAMs, constrained to be sums of univariate functions, are inherently limited in their expressive power. Consequently, even an oracle, i.e., a globally optimal GAM, may yield only modest gains in predictive performance. Expecting substantial improvements over existing GAM variants may therefore be unrealistic given the inherent limitations of the model class. \n\n  On regression datasets, spline-based methods consistently underperform compared to stump- or tree-based approaches. As noted by Reviewer wGmH, a key advantage of piecewise constant GAMs over smooth methods like cubic splines is their ability to capture discontinuous shape functions and abrupt changes, which is an important characteristic for modeling tabular data. Another limitation of traditional splines lies in selecting the placement and number of knots (i.e., points where two spline segments meet). For example, PyGAM places the same number of knots for each feature, whereas in our method, the distribution of stumps is determined dynamically during optimization.\n\n* **Suboptimal solutions of alternating optimization.** To clarify, our algorithm performs *exact* optimization over the four parameters of one stump at a time: the feature index, threshold value, and the left and right leaf predictions. After a full pass through all stumps, all leaf predictions are globally optimized given the current split parameters. While the method may appear simple and may be perceived as lacking sophistication, it is in fact highly effective at minimizing error. For instance, as shown in the left plot of Figure 1, just 200 optimized stumps achieve the same error level as 1000 greedily added stumps. \n\n* **No theoretical claims or guarantees on solution quality.** As we elaborate in our rebuttal to reviewer wGmH, our algorithm has important theoretical properties: monotonic decrease of the objective at each iteration and convergence to a local optimum.\n\n* **Absence of strong baseline comparisons.** Our method operates within the class of GAMs, and as such our experimental comparisons include all the state-of-the-art methods (e.g. EBMs) within this model class. Other reviewers have acknowledged that the chosen baselines are appropriate and sufficient for evaluating our contributions within this context. In this rebuttal, we have also included an additional comparison with FastSparse.\n\n* **Additional comparisons.** We have run the methods from [1, 2, 3], and reported the results in Tables 1–4 of the rebuttal PDF: https://anonymous.4open.science/r/pdf_to_anon-1CD8/icml25_rebuttal_figures.pdf or https://drive.google.com/file/d/1Xso8hwFd9rB_XqAzH6H8ri7vUbrXEaq6/view?usp=sharing. Full experimental details are provided in the table captions. [1] generally delivers strong performance across many datasets while maintaining small model sizes and fast training times. We can also leverage the solution from [1] to warm-start our stump forests and achieve even more accurate results (see more in our rebuttal to owkV). In contrast, [2] and [3] were significantly slower to train; we had to apply subsampling and feature binarization to obtain usable results. While these tree-based models are interpretable, direct comparisons with them are outside the scope of our work, which focuses specifically on GAMs.\n\n* **Writing improvement.**  Thank you for the helpful suggestions regarding the writing. We will carefully incorporate these recommendations to improve clarity, conciseness, and overall readability in the final version of the paper.\n\n* **Selection of hyperparameters.** As we state in line numbers 555 to 563 of appendix, we perform grid-search over $\\lambda = \\{2.0, 4.0, 6.0\\}$ for classification datasets, $\\lambda = \\{20.0, 40.0, 60.0\\}$ for regression datasets. We use a fixed value of $\\alpha = 0.1$, as it plays less significant role.", "claims_and_evidence": "The claims made in the paper lack rigorous support from the experimental results. The authors assert novelty in their approach to generalized additive models, yet prior literature already presents similar methodologies and much more impressive achievements. Specifically, the claim that this is the first paper to introduce such a model is incorrect—relevant prior work should be acknowledged (see references). Furthermore, the reported performance improvements are unconvincing. Based on results in Tables 1 and 2, when considering standard deviations, the proposed method performs comparably to existing approaches in both training and test settings. However, the baseline spline-based method achieves significantly smaller model sizes. This raises concerns about the practical significance of the proposed contribution, as the problem appears to be more effectively addressed by existing methods.", "methods_and_evaluation_criteria": "The proposed alternating optimization method could lead to suboptimal solutions. In each iteration, the approach selects a feature and a corresponding split value while keeping the coefficients fixed. This rigid structure can lead to suboptimal feature and split choices, making the optimization process less refined. While such a method may offer some improvements over existing approaches, it lacks sophistication and does not provide guarantees on solution quality.\n\nThe evaluation criteria used in the paper align with standard machine learning practices, as they include training and test performance, model size, and training time. However, a critical issue is the absence of strong baseline comparisons. The experiments should include comparisons with state-of-the-art methods for both linear regression and graphical model selection to ensure a fair assessment of the proposed approach’s effectiveness.", "theoretical_claims": "There is no theoretical claim in this paper.", "experimental_designs_or_analyses": "The experimental design and analyses are standard practices in the ML community.", "relation_to_broader_scientific_literature": "This paper is related to the broad research topics of interpretable machine learning, boosting, and decision trees. The key difference, compared with the boosting literature, is that historical stumps are allowed to be optimized over and over again.", "essential_references_not_discussed": "The paper omits several essential references related to generalized additive models and decision tree-based methods. Specifically, the authors claim to be the first to introduce a generalized additive model, but prior work has already developed such models with competitive performance and significantly fewer parameters. The following paper should be cited:\n\n1. Fast Sparse Classification for Generalized Linear and Additive Models by Jiachang Liu, Chudi Zhong, Margo Seltzer, Cynthia Rudin, AISTATS 2022.\n\nAdditionally, the authors fail to compare their method against state-of-the-art decision tree-based models. The only comparisons provided are with basic tree models, which do not reflect the latest advancements in the field. The following papers present scalable and optimal sparse decision trees that should be considered:\n\n2. Generalized and Scalable Optimal Sparse Decision Trees by Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, Margo Seltzer, ICML 2020.\n\n3. Optimal Sparse Regression Trees by Rui Zhang, Rui Xin, Margo Seltzer, Cynthia Rudin, AAAI 2023.\n\nThese papers demonstrate that classification and regression trees can be constructed with fewer than 30 variables while maintaining performance comparable to much larger tree-based models developed using older methodologies. A thorough comparison with these methods is necessary to properly contextualize the contributions of this paper.", "other_strengths_and_weaknesses": "The writing requires significant improvement. Many sections are overly verbose and lack substantive content. Certain passages could be condensed or moved to the appendix for better readability. For example, from lines 209 to 252, the authors spend nearly a full page deriving the objective function in Equation 5. However, this section reads more like a stream of consciousness than a structured derivation. Instead, the paper should present Equation 5 concisely at the beginning of the section, followed by a brief yet clear explanation.\n\nOverall, the clarity and conciseness of the writing should be improved. The exposition is currently too wordy, making it difficult to follow the main contributions efficiently. Refining the explanations and eliminating redundancy would significantly enhance the readability and impact of the paper.", "other_comments_or_suggestions": "Some experimental details, such as Lines 301–315 (right column), should be moved to the appendix. This section is overly detailed and does not contribute significantly to the main narrative. The main text should focus on the core contributions, while dataset descriptions and minor experimental details can be placed in supplementary material.", "questions_for_authors": "1. How did you select the hyper parameters $\\lambda$ and $\\alpha$ in Equation 5, the objective function? To me, hand-picking the values does not seem like a rigorous approach of doing this.\n\n2. Can you run [1, 2, 3], report results on datasets listed in Table 1 and 2, and make a comparison during rebuttal?", "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": "", "extra_scores": {}}, {"review_id": "UoJPOunhVt", "reviewer": "Reviewer_owkV", "summary": "The authors propose an alternative framework to train GAM models with piecewise constant shape functions based on an alternating optimisation algorithm. A specific regularization strategy is proposed to deal with the issue of overfitting when directly optimizing this type of models.\nThe authors find that this approach is competitive with other boosting based approaches to optimize the same type of models.", "questions": "", "limitations": "", "rating": 4, "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": "Thank you for providing us with a very valuable and insightful review! We greatly appreciate your effort in reviewing our paper.\n\n* **Convergence to global optimum.** The problem of learning an optimal decision stump forest is computationally intractable in general. Even in the case of 1D splines, finding optimal knot positions is known to be NP-hard [1]. Therefore, guaranteeing convergence to a global optimum in polynomial time is unlikely. Our algorithm guarantees a monotonic decrease in the objective function at each iteration and converges to a local optimum. We expand on this discussion in our rebuttal to wGmH.\n\n* **Slow rate of convergence.** Our optimization space includes both continuous and discrete components. The continuous part, the leaf values, is optimized exactly by solving a convex problem. The discrete part involves the split parameters of the stumps. Alternating optimization is one of the most effective approaches for such problems. For instance, the well-known k-means algorithm also alternates between discrete and continuous updates and is rarely hindered by slow convergence in practice. In our experiments, the algorithm typically converges within around 5 iterations, where one iteration is defined as a full pass over all stumps and an update of all leaf parameters.\n\n* **Limited representation capacity.** We acknowledge and agree with the observation regarding the limited representation capacity of GAMs, and that there may be limited room for improvement over existing baselines. While it is true that on datasets like Covertype, GAMs perform notably worse than high-capacity models, there are also cases, such as the cpuact dataset, where GAMs achieve accuracy comparable to models like XGBoost. The key strength of GAMs lies in their interpretability and their ability to provide meaningful insights into the data. This is particularly valuable in sensitive domains like healthcare, where understanding model behavior is crucial [2].\n\n* **Training time improvement.** The majority of our time during this research project was devoted to analyzing the behavior of the algorithm and exploring various strategies to address the overfitting. Comparatively little time was initially spent on improving runtime performance. During the rebuttal period, we revisited the formulation of the leaf-fitting problem and focused on optimizing its efficiency.\n\n  Instead of optimizing over the stump leaf parameters, we now directly optimize over the constant piece values of the GAM shape functions. That is, we switch from the stump forest representation to its equivalent GAM form. This change reduces the number of optimization variables by a factor of two. Additionally, by rewriting the convex problem in CVXPY using a different set of atomic functions, we were able to switch the underlying solver to OSQP (Operator Splitting Quadratic Program). In line with your suggestion, this allows us to cast the problem as a standard quadratic program while still using CVXPY to handle the transformation, with minimal overhead. These changes result in a significant improvement in training time, by a factor of 5 to 20 depending on the dataset.\n\n  After solving for the constant pieces of the GAM, we convert the result back to the stump forest representation. Specifically, let the shape function for feature $d$ be $f_d(x_d)$ which consists of the $T_d+1$ constant pieces with values $\\beta_0, \\dots, \\beta_{T_d+1}$ from left to right. The leftmost stump has leaf values  $\\mu^l_0 = \\beta_0$ and $\\mu^r_0 = \\beta_1$. For subsequent stumps with index $i > 0$ we set the left leaf to $\\mu^l_i = 0$ and the right leaf to $\\mu^r_i = \\beta_i - \\beta_{i-1}$.  In other words, the left leaf is always 0, and the right leaf captures the difference between adjacent constant values. It is straightforward to verify that this reconstruction yields a function equivalent to the original GAM. The updated Tables 1 and 2 (https://anonymous.4open.science/r/pdf_to_anon-1CD8/icml25_rebuttal_figures.pdf or https://drive.google.com/file/d/1Xso8hwFd9rB_XqAzH6H8ri7vUbrXEaq6/view?usp=sharing) reflect the significantly improved training times achieved through this new formulation.  Now, our method is among the fastest to learning accurate piecewise constant GAMs.\n\n* **Warm starting ability.** Another independent strategy to accelerate training and potentially improve accuracy is to initialize the optimization from stronger starting points. During the rebuttal period, we incorporated an additional baseline, FastSparse, which efficiently produces reasonably accurate piecewise constant GAMs. Using these models for initialization led to even faster convergence and slightly improved accuracy on several datasets.\n\n[1] G. Beliakov, \"Least squares splines with free knots: global optimization approach\", in Applied Mathematics and Computation, 2004.\n\n[2] R. Caruana et al., \"Intelligible Models for HealthCare: Predicting Pneumonia Risk and Hospital 30-day Readmission\", KDD 2015.", "claims_and_evidence": "As far as I am concerned, the authors make no unsupported claims.\n\nI think, however, that the authors could clarify that even though their method converges, assuming no cycles, there is no guarantee of convergence to the global optimum solution. Furthermore, there is no guarantee on the rate of this convergence. This type of method could converge very slowly in problems with narrow \"diagonal\" valleys where alternating minimization makes little progress with each iteration.", "methods_and_evaluation_criteria": "In my opinion, the methods and evaluation make sense for the problem at hand.", "theoretical_claims": "There are no proofs or theoretical claims.", "experimental_designs_or_analyses": "The choice of baselines and the experimental setup all seem adequate.", "relation_to_broader_scientific_literature": "GAM models that rely on piecewise constant shape functions, such as Explainable Boosting Machines, are arguably SoTA within this model class. This work proposes a new approach to train models using the same type of shape function, through directly optimizing the splits of a stump forest rather than the boosting approach of EBM.", "essential_references_not_discussed": "None that I am aware.", "other_strengths_and_weaknesses": "### Strengths\n\nThe authors put a great effort in the presentation of the paper. Everything is clearly explained, with plenty of insightful figures that illustrate the main points.\n\nFurthermore, the proposed approach, while somewhat reminiscent of backfitting, is interesting and original, presenting a significant enough departure from how similar piece-wise constant models are typically trained.\n\n### Weaknesses\n\nMy overall interpretation of the results is that GAM models seem rather limited in their representation capacity given their rigid model structure, and there isn't much to be gained in the choice of different families of shape functions or how they are fit.\nParticularly, for all of the models learning piecewise constant shape functions, the differences in performance seem small, specially when comparing with black-box models that don't follow the GAM structure.\nAs an example, a standard GBDT (with deeper trees) achieves < 3% error on Covtype. This makes the small differences between GAM models, all of which achieve ~22% error, seem inconsequential in practice.\n\nAs such, while I value work on interpretable models, I don't see this work as having a particularly large impact, specially given that it seems significantly slower to fit than alternatives.\n\n**Post rebuttal note:** Considering the authors' efforts in optimizing their algorithm and the significant speedups they achieved, this pointed weakness is no longer applicable and the argument for adopting the proposed algorithm becomes considerably more compelling.", "other_comments_or_suggestions": "None", "questions_for_authors": "(**RESOLVED**) 1. As the authors point out as a possible point of improvement, it seems to me that the optimization of the leaf values could be formulated as a standard quadratic program. Perhaps calling a solver directly would forego the overhead of CVXPY and speed up the training process which is one the weaker points of the algorithm. If a substantial speed up could be achieved I would be willing to raise my score to a clear accept.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a new method for fitting generalized additive models using decision stumps, by jointly optimizing all model parameters. This results in much smaller models than alternative methods such as EBMs, while providing competitive predictive performance. Additional improvements and experiments during the rebuttal period show runtime similar and often faster than for EBMs.
This is an interesting new angle on fitting piecewise constant GAMs, which compares favorably with existing methods.
Decision: Accept (poster)