Random Feature Representation Boosting
Authors: Nikita Zozoulenko
Thomas Cass
Lukas Gonon
Venue: ICML 2025 poster (2025)
Keywords: random features
gradient boosting
gradient representation boosting
residual neural networks
resnets
tabular data
supervised learning
random feature neural networks
Primary area: general_machine_learning->representation_learning
TL;DR: We construct deep residual random feature networks using boosting theory, achieving superior accuracy and efficiency.

Abstract: We introduce Random Feature Representation Boosting (RFRBoost), a novel method for constructing deep residual random feature neural networks (RFNNs) using boosting theory. RFRBoost uses random features at each layer to learn the functional gradient of the network representation, enhancing performance while preserving the convex optimization benefits of RFNNs. In the case of MSE loss, we obtain closed-form solutions to greedy layer-wise boosting with random features. For general loss functions, we show that fitting random feature residual blocks reduces to solving a quadratically constrained least squares problem. Through extensive numerical experiments on tabular datasets for both regression and classification, we show that RFRBoost significantly outperforms RFNNs and end-to-end trained MLP ResNets in the small- to medium-scale regime where RFNNs are typically applied. Moreover, RFRBoost offers substantial computational benefits, and theoretical guarantees stemming from boosting theory.

Random Feature Representation Boosting
Nikita Zozoulenko'
Thomas Cass Lukas Gonon 12
Abstract
and speed across various tasks (Bolager et al., 2023; Demp- ster et al., 2023; Gattiglio et al., 2024; Prabhu et al., 2024).
We introduce Random Feature Representation Boosting (RFRBoost), novel method for con- structing deep residual random feature neural net- works (RFNNs) using boosting theory. RFRBoost uses random features at each layer to Iearn the functional gradient of the network representation, enhancing performance while preserving the con- vex optimization benefits of RFNNs. In the case of MSE loss, we obtain closed-form solutions to greedy layer-wise boosting with random features. For general loss functions, we show that fitting random feature residual blocks reduces to solving quadratically constrained least squares problem. Through extensive numerical experiments on tab- ular datasets for both regression and classification, we show that RFRBoost significantly outperforms RFNNS and end-to-end trained MLP ResNets in the small- to medium-scale regime where RFNNS are typically applied. Morcover, RERBoost offers substantial computational benefits, and theoretical guarantees stemming from boosting theory.
Recent theoretical work on Fourier RFNNs has shown that deep residual RFNNS can achieve lower generalization er- rors than their single-layer counterparts (Kammonen et al., 2022). Current theory and algorithms for training deep RFNNs, however, are limited to the Fourier activation func- tion (Davis et al., 2024), and uses ideas from control theory to sample from optimal weight distributions. While skip connections have been crucial the success of deep end- to-end-trained ResNets (He al., 2015), introducing them into general RFNNs is not straightforward, naively stack- ing random layers may degrade performance. In this paper, we introduce random feature representation boosting (RFRBoust), a novel method for constructing deep ResNet RENNs. Our approach not only significantly improves per- formance, but also retains the highly tractable convex op- timization framework inherent RFNNs, with theoretical guarantees stemming from boosting theory.
ResNets have traditionally been studied from two primary perspectives. The first views a ResNet p,, defined by
(x(x) = 1 (z) + ge (x))
(I)
as an Euler discretization of dynamical system (x) gr (1, (D)))t (E, 2017). Here 9: represents residual block at layer f, often expressed as 9i (x) = Ao (B.+b). This frame- work was later generalized to the setting of neural ODEs (Chen et al., 2018; Dupont et al., 2019; Kidger et al., 2020; 2021; Walker et al., 2024). The second point of view is that of gradient boosting, where a ResNet can be seen as an ensemble of weak, shallow neural networks of varying sizes, (x) Σt- tion (1) (Veit et al., 2016). This led to the development of gradient representation boosting (Nitanda & Suzuki, 2018; Suggala et al., 2020), which studies residual blocks via func- tional gradients in the space of square integrable random vectors L (n). where μ is the distribution of the data.
1. Introduction
Random feature neural networks (RFNNs) are single- hidden-layer neural networks where all model parameters are randomly initialized or sampled, with only the linear output layer being trained. This approach presents compu- tationally efficient alternative to neural networks trained via stochastic gradient descent (SGD), avoiding the challenges associated with non-convex optimization and vanishing/- exploding gradients. Despite their simplicity, RFNNs and related random feature models have strong provable gen- eralization guarantees (Rahimi & Recht, 2008b; Rudi & Rosasco, 2017; Lanthaler & Nelsen, 2023; Cheng et al., 2023), and have demonstrated -fate-of-the-art performance
- 9t 9: (.)) derived by unravelling equa-
EEqual last authors. 'Department of Mathematics, Imperial College London. UK SShooo of Computer Science, University of St. Gallen, Switzerland. Correspondence to: Nikita Zozoulenko <n.zozoolenko236 imperial.c.ukk:
A key challenge in extending RFNNs tectures lies in the crucial role of the residual blocks 9e when they are composed of random features. If the magnitude of It is too small, the initial representation 4, dominates, ren- dering the added random features ineffective. Conversely, if 9e is too large, information from previous layers can be lost. This problem is not merely one of scale; ideally each
deep ResNet archi-
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Random Feature Representation Boosting
residual block should approximate the negative functional gradient of the loss with respect to the network representa- tion. However, random layers are not guaranteed to possess this property. Unlike end-to-end trained networks where SGD with backpropagation can adjust all network weights to learn an appropriate scale and representation, RFNNS lack comparable mechanism because their hidden layers are fixed. We address this issue by using random features at each layer of the ResNet to learn mapping to the functional gradient of the training data, enabling tractable learning of optimal random feature residual blocks via analytical solu- tions or convex optimization.
Boosting for Neural Networks: Applications of boost- ing for neural network first appeared in AdaNet (Cortes et al., 2017), which built network graph using boosting to minimize a data-dependent generalization bound. Huang et al. (2018) introduced an AdaBoost-inspired algorithm for sequentially learning residual blocks, boosting the fea- ture representation rather than the class labels. Nitanda & Suzuki (2018; 2020) proposed using Fréchet derivatives in L (N) to learn residual blocks that preserve small func- tional gradient norms, motivated by Reproducing Kernel Hilbert Space (RKHS) theory and smoothing techniques. GrowNet (Badirli et al., 2020) constructs an ensemble of neural networks in the classical sense of gradient boosting the labels, not as a ResNet, but by concatenating the fea- tures of previous models to the next weak learner. Suggala et al. (2020) introduced gradient representation boosting, which studies layer-wise training of ResNets by greedily or gradient-greedily minimizing risk function, and gives modular excess risk bounds based on Rademacher complex- ities. Yu et al. (2023) used gradient boosting to improve the training of dynamic depth neural networks. Finally, Emami Martinez-Muñor (2023) constructed a network neuron-by-neuron using gradient boosting.
1.1. Contributions
Our paper makes the following contributions:
We propose a novel method for constructing deep ResNet RFNNs, overcoming the limitations of naively stacking random features layers. RFRBoost supports arbitrary random features, extend- ing beyond classical random Fourier features.
Introducing RFRBoost:
Analytical Solutions and Algorithms: For MSE loss, we derive closed-form solutions to greedy layer-wise boosting using random features by solving what we term "sandwiched least squares problems", special case of generalized Sylvester equations. For general losses, we show that fitting random feature residual blocks is equivalent to solving quadratically con- strained least squares problem.
Random feature models: Random feature models use fixed, randomly generated features to map data into a high dimensional space, enabling efficient linear learning. These methods encompass a broad class of models studied under various names, including random Fourier features (Rahimi & Recht, 2007; Sriperumbudur & Szabo, 2015; Li al., 2019; Kammonen et al., 2022; Davis al., 2024), extreme learning machines (Huang et al., 2004; 2012; Huang, 2014), random features or RFNNS (Huang et al., 2006; Rahimi & Recht, 2008a;b; Rudi & Rosasco, 2017: Carratino et al., 2018: 8; Yehudai & Shamir, 2019; Mei & Montanari, 2022; Bolager et al., 2023; Lanthaler & Nelsen, 2023; Ayme et al., 2024). reservoir computing (Jaeger, 2001; Lukoševičius
Theoretical Guarantees: We provide a regret bound for RFRBoost based on Rademacher complexities and established results from boosting theory.
Through numerical experi- ments on 91 tabular regression and classification tasks from the curated OpenML repository, we demonstrate that Roost significantly outperforms both single- layer RENNs and end-to-end trained MLP ResNets, while offering substantial computational advantages.
Empirical Validation:
Jaeger, 2009; Gallicchio et al., 2017: Grigoryeva & Ortega, 2018; Tanaka et al., 2019; Hart et al., 2020; Gonon et al., 2023; 2024), kernel methods (Kar & Karnick, 2012; Sinha & Duchi, 2016; Sun et al., 2018: Szabo & Sriperumbudur, 2019; Cheng et al., 2023; Wang et al., 2024; Wang & Feng,
1.2. Related literature
2024), and scattering networks (Bruna & Mallat, 2013; Cot- ter & Kingshury, 2017: Oyallon et al., 2019; Trockman et al., 2023). Recently, RFNNs and related approaches have demonstrated exceptional performance in both speed and accuracy across a wide variety of applications. These include solving partial differential equations (Nelsen & Stu- art, 2021; Gonon, 2023; Gattiglio et al., 2024; Neufeld & Schmocker, 2024). online learning (Prabhu et al., 2024), time series classification (Dempster et al., 2020; 2023), and in mathematical finance (Jacquier & Zuric, 2023; Herrera et al., 2024). RFNNS have also been explored in the context of quantum computing (Innocenti et al., 2023; Gonon &
Boosting aims to build a strong ensem- ble weak learners via additive modelling of the objective function, dating back to the 1990s with the development of AdaBoost (Freund & Schapire, 1997). Gradient boost- ing, introduced as a generalization of boosting, supports general differentiable loss functions (Mason et al., 1999; Friedman et al., 2000; Friedman, 2001), and includes popu- lar frameworks such as XGBoost (Chen& & Guestrin, 2016), LightGBM (Ke et al., 2017), and CatBoost (Prokhorenkova et al., 2018). These models typically use decision trees as weak learners and are widely considered the best out-of-ther the box models for tabular data (Grinsztajn et al., 2022).
Classical Boosting:
2

---

Random Feature Representation Boosting
Jacquier, 2023; Martínez-Peña & Ortega, 2023; Xiong et al., 2024), and in relation to random neural controlled differen- tial equations and state-space models (Cuchiero et al., 2021; Cirone et al., 2023; 2024; Biagini et al., 2024).
2.2. Gradient Representation Boosting
Unlike classical boosting, which boosts in target space, neu- ral network gradient representation boosting aims to addi- tively learn a feature representation by modelling F via F = (X) = W.T (X)),, where +; = Σ 18, is a gradient boosted feature representation and W, E IR Dxd is the top-level linear predictor. In other words, gradient repre- sentation boosting seeks to learn the feature representation D additively to build a single strong predictor, rather than constructing F, as ensemble of weak predictors (Huang et al., 2018; Nitanda & Suzuki, 2018; 2020; Suggala et al., 2020). For a depth t ResNet +, defined recursively as
2. Functional Gradient Boosting
In this section we introduce notation and give a brief overview of classical gradient boosting (Mason al., 1999; Friedman, 2001), and its connection to deep ResNets via gradient representation boosting (Nitanda & Suzuki, 2018; 2020; Suggala et al., 2020).
Let (X ~ j be a random sample with its corresponding probability measure μ. Denote by X ~ jux the features in 12, with targets Y JY in Rd, and py|x=r the conditional law. Let j = n Ei= ((..,))) be the empirical measure of u. We will work the Hilbert space T.2 (u)), with inner The concept of functional gradient plays key role in gradient boosting:
i D1 m//e(
(2)
we see by unravelling (2), that the weak learners It are of the form 9: h2 (x( These functions Ii are sometimes referred to as weak feature transformations. Prior work has employed shallow neural networks as 9t. trained greedily layer-by-layer with SGD (see references above). In the setting of gradient representation boosting we denote the risk as R(W, Φ) = Ey [<(WT ((X). Y)]. and the functional gradient with respect to the feature representation $ is
product given by (f.g) (P(() = E,,((.9))
Definition 2.1. Let H be Hilbert space. A function f + Ri is said to be Frechet differentiable at h E H if there exists a bounded linear operator ff= U -> H. for some open neighbourhood U C H of such that
F2R E Eyixx [Wa,l(WT [ Y)).
f(h 9) = f(h) + (g. (f(h)) + ((1g)
Let R(W, +) be the empirical risk, W the hypothesis set of top-level linear predictors, and G. the set of weak feature transformations. As outlined by Suggala et al. (2020), there are two main strategies for training ResNets via gradient representation boosting, which we describe below.
for g E U. The element V (h) is often referred to as the functional gradient of f at h, or simply the gradient.
2.1. Traditional Gradient Boosting
Let:: Rd x Rd -> TK be sufficiently regular loss function. Traditional gradient boosting seeks to minimize the risk
1.) Exact-Greedy Layer-wise Boosting: At boosting step I, the model is updated greedily by solving the joint opti- mization problem
R(F)- = E,, [((F(X), by additively modelling F' e (g) within a space of weak learners G, typically a set
W₁, St argmin R(W, Φ.-1 + +g), WEW.SEG.
(3)
of decision trees (Friedman, 2001; Chen & Guestrin, 2016).
iteratively updates an estimate F. = E. na,9s based on a first-order expansion of the risk:
leading to the update $; = 0 + 79+- This approach is feasible when W and g are jointly optimized by SGD. For general ResNets, this translates to gr = he (e(2d-1), where hy is a shallow neural network (i.e., a residual block) and W the top-level linear predictor.
R(F++ Rs R(F,) + (g. VR(P)))
To minimize the risk based on this approximation, a new weak learner 1 is fit to the negative functional gradient, (FF(F)) and the ensemble is then updated: F++1 = F; + 70++19++1 where 7), 04+1 > 0 are the global and local learning rates. The functional gradient can be shown to be equal to
However, in the context of random feature ResNets, using SGD for the joint optimization in Equation (3) undermines the computational benefits inherent to the random feature approach. As will be demonstrated in Section 3, by restrict- ing 9t to a simple residual block gt = A ( with fi representing random features and A, a linear map, we can derive closed-form analytical solutions for two-stage approach to the optimization problem (3). This speeds up training and removes the need for hyperparameter tuning of the scale of the random features ft at each individual layer.
VR(F)(x) = - (O(((e))))
and is easily computed for empirical measures f I Ei ((..)))) using the empirical risk R(F.. The method for fitting It+1 varies between implementations and depends on the class of weak learners, as seen in modern approaches like XGBoost (Chen& & Guestrin, 2016) which incorporates second-order information.
2.) Gradient-Greedy Layer-wise Boosting: An alternative to directly minimizing the risk by solving (3), which can be
3

---

Random Feature Representation Boosting
intractable depending on the loss I and the family of weak learners, is to follow the negative functional gradient. At boosting iteration i, this approach approximates the risk using the first-order functional Taylor expansion:
RFRBoost at layer t
Loss
Linear
4, 2 ndifi
Top-level linear predictor and loss
R(W, 4 9) R(W, ) (g. R2, 9) Lpw (4)
A new weak learner It E Gr is fit by minimizing the empiri-
Learn mapping A with boosting
cal inner product (g; Vo 9 1)-1)) 1.) The depth
t feature representation is obtained by 2, - + 79t.
and the top-level predictor is then updated:
Random features ft
W = argmin R(W, $,). WEW
The gradient-greedy approach for constructing ResNets has remained relatively unexplored in the literature. Suggala et al. (2020), who introduced both strategies in the context of end-to-end trained networks, only mention in passing that the gradient-greedy strategy performed worse comparatively. We believe this might be at- tributed to the functional direction of g failing to be properly preserved during training with SGD. Specifically, when is chosen from the family g = h( 1), where h is a shallow neural network, minimizing (g. V R2 2,-1)) up (R) via SGD might increase ( without ensuring that aligns with the functional gradient in LP(P), Since the first-order approximation (4) only holds for g with small functional norm, we argue that this objective should instead be minimized under the constraint |ا LP)) random feature setting, show in Section 4 that it leads to the muudient-grects ap- proach outperforming the exact-greedy strategy.
Potential Challenges:
Figure I. Diagram of random feature representation boosting.
3.1. Random Feature Layer
With random feature layer, mean any mapping which produces a feature vector ft E RP, which will not be trained after initialization. This is in contrast to end-to-end trained networks, where all model weights are adjusted continu- ously during training. A common choice for fc is a ran- domly sampled dense layer, f(()) = ( with activation function and weight matrix B, RRxD To enhance the expressive power of RFRBoost, we allow the random features ft to be functions of both the input data and the previous ResNet layer's output (x), similar to GrowNet (Badirli et al., 2020) and ResFGB-FW (Nitanda & Suzuki, 2020). Figure 1 provides a visual representation of the RFRBoost architecture. Specifically, in our experi- ments tabular data, we let the random feature layer be (xx = a (concatt( (,1 Ca+)). The initial mapping p can for instance be random fixed linear projection, or the identity. Instead of initializing B, and C. i.i.d., we use SWIM random features (Bolager et al., 2023) in our exper- iments (see Appendix E for more details). Note however that RFRBoost supports arbitrary types of random features, not only randomly initialized sampled dense layers.
In our incorporate this constraint and
3. Random Feature Representation Boosting
Our goal to construct a random feature ResNet of the form
Φ = f. + n/A.
where fi (:),))) E Rp are random features, A, E RRDxP is a linear map, is input data, and v) > 0 is the learning rate. We propose to use the theory of gradient representation boosting (Suggala et al., 2020) to derive opti- mal expressions for A,. We consider three different cases where A₁ is either a scalar (learning optimal learning rate), a diagonal matrix (learning dimension learning rate), or a dense matrix (learning the functional gradient). Note that the scalar and diagonal cases assume that p p= D.
3.2. Exeety Case for Mean Squared Error Loss
Recall that in the exact-greedy layer-wise paradigm. the ob- jective at layer & is find a function gr G. that additively and greedily minimizes the empirical risk R(W,, 4 + 9:) for some linear map W, E W, given ResNet feature repre- sentation -,-1. We propose using functional gradient boost- ing to construct a residual block of the form 9r = A,fi, where A₁ E dx is a linear map. and fe is a random feature layer. We consider the cases where A, is a sealar
This section is outlined as follows: We first define ran- dom feature layer. We then analyze the case of MSE loss ((r, u) = _ oz - v1ia.. deriving closed-form solutions for layer-wise exact greedy boosting with random features. We then explore the cradient-greedd approach, which supports any differentiable loss function.
4

---

end for Random Feature Representation Boosting
multiple of the identity, a diagonal matrix, or general dense matrix. The procedure is outlined below:
Algorithm 1 Greedy RFRBoost MSE Loss
Input: Data (Ti, W T layers, learning rate 17, l regularization X, initial representation Pu-
Step 1: Generate random features f. fz (),11(z))
Wo f- argmin 1. Ei l1y. W @o(
which may depend on both the raw training data x and the activations at the previous layer 1x)) Using MSE loss, we find that
W
for = 1 to do
Generate random features S&, = [e( 8 1z-1
A argmin R(W-11 1-11 + Af((E))
Compute residuals r; < y/ - W 1- c- (Ii²)
A
Solve sandwiched least squares
A 4- argmin 1 Ei= I|+ W A Ase, + 1
argmin A
llus W.I1 + Af((
Build ResNet layer D. f 22-1 + n.A.S
Update top-level linear regressor
argmin A
||re - W Aft
(5)
W₂ 4 argmin 1 En= l1y: W T (x;))) +AIWI
(|):]|++
W
where D1 W are the residuals of the model at layer L- 1. We term problems of the form (5) sand- wiched least squares problems, for which Theorem 3.1 below provides the existence of closed-form analytical solu- tions which are fast to compute.
Output: ResNet ty and regressor head Wr-
Algorithm 2 Gradient RFRBoost General Loss Input: Data (ri, ) loss I, T layers, learning rate 1), Eg regularization X, initial representation to.
Step 2: After computing A,, we obtain the depth represen- tation 4; = Φ1-1 + AeJi,. The top-level linear regressor Wo+1 is then updated via multiple least squares:
Wo t argmin J W
n >i LW (o(x))) y:)
for t = 1 to T do Generate random features St, = St(xi; 1
W.- argmin _
Σ Iy W P..
(6)
Gradient G, + Wi-1 Wi (
Wew
Fit gradient Ar + --l.setssssuueee squares(fs Solve line search with convex solver
Talle" 2)
VTG
In practice, l regularization is added to equations (5) and (6). Steps and are repeated for T layers. The complete procedure is detailed in Algorithm 1.
0z < -argmmnn : - ((WT((( ( + fe).
Build ResNet layer D, + Φ + not Update top W. <- argmin A/2 Em= I( D. d.(2s))
Theorem 3.1. Let r2 E R2, W E RD E B. for all i E [n]. Let X > O. Consider the setting of scalar A, diagonal A, and dense A RDxx, Write Z E NN and xd for the stacked data and residual matrices. Then the minimum of
W
end for
Output: ResNet T and top linear layer WT.
R E Nxd
Proof. See Propositions A.1 to A.3 in the Appendix.
((A) = n Σ r.
W Azill² + ||AA
3.3. Gradient Boosting Random Features
is in the scalar, diagonal, and dense case attained at
While the greedy approach provides optimal solutions for MSE loss, many applications require more general loss func- tions, such as cross-entropy loss for classification. In such cases, we turn to the gradient-greedy strategy. Recall that in this setting, we aim to minimize the first-order functional Taylor expansion of the risk:
(R, ZW)F
Ascalar
| 2 P n'x
Adiag = (WWT& o 2Z z - didadaWWW (WR Z),
Adense U U WR WWRTZV ZV 2 ANN1
R(W: + g) R(W, b) + (g. V2R(W, ()
()) (w):
which holds for functions g with small L (n)-norm. As discussed in the context of general gradient representa- tion boosting, a potential issue with directly minimizing (g. (W, (2) is that g might learn to maximize its magnitude without following the direction of the functional gradient. To address this, we constrain the problem to en- sure that g maintains a unit norm in T.P (7). If we restrict g
+ diag (A )) x diag(A 1
VT.
where 11 is the Frobenius norm, C denotes element-wise division, 8 is the outer product, 1 is a matrix of ones, and WWT = UT and Z π z = VV are spectral decompositions.
5

---

Random Feature Representation Boosting
residual blocks of the form g = AS, where A E RDxP is linear map, and f E TRP random features, then solving the constrained L2 (2) -inner product minimization problem becomes equivalent to solving quadratically constrained least squares problem. See Appendix B for the proof.
Step 3: Update the feature representation $ Φ(-1 +
1, and the top-level linear predictor
We = argmin R(W, Φ+))
WeW
using appropriate convex minimizer depending on the specific loss function, such as L-BFGS. The full gradient- greedy procedure is detailed in Algorithm 2.
Theorem 3.2. Let ū - Ei= (gsa)) be the empirical measure of the data. Then
(ff. V2R( 4)) LP(
argmax X such that || A
3.4. Theoretical Guarantees
A key advantage of using RFRBoost to construct ResNets over traditional end-to-end trained networks is that RFR- Boost inherits strong theoretical guarantees from boosting theory. We analyze RERBoost within the theoretical frame- work of Generalized Boosting (Suggala et al., 2020), where excess risk bounds have been established in terms of modu- lar Rademacher complexities of the family of weak learners G. at each boosting iteration f. These bounds are based on the (3, e)-weak learning condition, defined below.
the solution to the quadratically constrained least squares problem
1
minimize
V Af(x))
subject to
1
which in particular has the closed form analytical solution
Definition 3.3 (Suggala et al. (2020)). Let 8 E (0, 1] and 2 O. We say that 94+1 satisfies the (8, e)- -weak learning condition if there exists a g E G441 such that
Vn G FFF(FFF)) FY-
|G]
Frabenias
(g.- Vv.WV, +b))) 1P(4)
when F has full rank, where F E RTX is the feature matrix, and G E B is the matrix given by G.. (V2R(W, (x))))
+ V2R(W, 2 kP(
3 Supges (191l19(())
Intuitively, this condition states that there exists a weak feature transformation in Ge+1 that is negatively correlated with the functional gradient. In the sample-splitting setting, where each boosting iteration uses an independent sample of size = [n/T], , we derive the following regret bound for RFR Boost. This bound describes how the excess risk decays compared to optimal predictor T and ñ vary.
The procedure for using Gradient RERBoost at layer & to build random feature ResNet b is outlined below (see also Figure l):
Step 1: Generate random features ft- Compute the data matrix of the functional gradient G.,j = (V2 (V2R(W,,,, (r=)((=)),) For MSE loss, this is given by
Theorem 3.4. Let I be L-Lipschitz and M-smooth with respect to the first argument. For a matrix W, let Xm) and Amax denote its smallest and largest Consider RFRBoost
MSE (W,- 1. v:)),
singular values, respectively. with the hypothesis set of linear predictors W { ( nxdd Amin (W) > >n > 0, Xmax A1). and weak feature transformations Gr A tanh (anh(BB,11(t))) fying the (B.cakkweak learning condition. Let the boosting learning rates be mp = ct= for some E (8t1. 1) and c >> O. Then T-layer RFRBoost satisfies the following risk bound for any W* D², and a E (0,3(1 - -6) with probability at least 1 over datasets of size n:
and for negative cross-entropy loss by
G (Wo 11 ey.))
far
(A)x Amax (B) < d1 satis-
where is the softmax function, and ey, is the one-hot vector for label yr. For full derivation, see Appendix C. We then fit A, by fitting fi-1 to the negative normalized functional gradient- |C
VRC via multiple least squares, according to Theorem B. In practice we also include & regularization.
Step 2: Find the optimal amount of say a4 via line search
T
R(Wr, 2T) S R(W*, Φ0) +2
n6ct
02 = argmin R(W,,,, D, + aAff)))
a>u
- x (1 +
T log
+
1
0
using Theorem 3.1 for MSE loss, or via a suitable convex optimizer such as Newton's 's method for cross-entropy loss.
Ta
6

---

Random Feature Representation Boosting
where the constant C does not depend on T, n, and 8.
is well-established methodology for comparing multiple a algorithms across multiple datasets (Demsar, 2006; Gareía & Herrera, 2008; Benavoli et al., 2016).
Proof. See Appendix D.
Baseline Models: We compare RFRBoost, a random feature ResNet, against several strong baselines, including end- to-end (E2E) trained MLP ResNets, single-layer random feature neural networks (RENNs), ridge regression, logistic regression, and XGBoost (Chen & Guestrin, 2016). The E2E ResNets are trained using the Adam optimizer (Kingma & Ba, 2015) with cosine learning rate annealing, ReLU activations, and batch normalization. While XGBoost is a powerful gradient boosting model, it differs fundamentally from RFRBoost. XGBoost ensembles large number of weak decision trees (up to 1000 in our experiments) to build a strong predictor. RFRBoost, on the other hand, uses gradient representation boosting to construct a small number of residual blocks, followed by a single linear predictor. For RFRBoost and RFNNs we use SWIM random features with tanh activations, as detailed in Appendix E. In the regression setting, we evaluate three variants of RFRBoost: using a scalar, diagonal, or dense A matrix. When using dense A, we set the initial mapping Do to the identity; otherwise, Po(x)) is a randomly initialized dense layer. For classification, we use the gradient-greedy variant of RFRBoost with LBFG-S as the convex solver. We use the official implementation of XGBoost, and implement all other baseline models in PyTorch (Paszke et al., 2019).
For similar results in the literature, see for instance Suggala et al. (2020), Corollary 4.3.
3.5. Time Complexity
The serial time complexity of RFRBoost with MSE loss, assuming tabular data and dense random features, is O(T[N(D² + Dd + p² + pD) + D + dD² + y + Dy as derived from Algorithm 2. Here N is the dataset size, D is the dimension of the neural network representation, d is the output dimension of the regression task, p is the number of random features, and T is the number of layers (boosting rounds). The computation is dominated by matrix operations, which are well-suited for GPU acceleration. The classification case follows similarly.
4. Numerical Experiments
In this section, we compare RFRBoost against set of base- line models on wide range of tabular regression and classi- fication datasets, as well as on a challenging synthetic point cloud separation task. All our code is publicly available at https: //ggt/ubg.tthtetg http////////t.ttoooooooet.....a.
Hy plyerparameter:: All hyperparameters are tuned with Optuna in the innermost fold, using 100 trials per outer fold, model, and dataset. For ridge and logistic regression, we tune the lg regularization. For the neural network-based models, we fix the feature dimension of each residual block to 512 and use 1 to 10 layers. For E2E networks, we tune the hidden size, learning rate, learning rate decay, number of epochs, batch size, and weight decay. For RFRBoost, we tune the lg regularization of the linear predictor and func- tional gradient mapping, the boosting learning rate, and the variance of the random features. For RFNNs, we tune the random feature dimension, random feature variance, and &2 regularization. For XGBoost, we tune the & and & regular- ization, tree depth, boosting learning rate, and the number of weak learners. For a detailed list of hyperparameter ranges, along with an ablation study comparing SWIM random fea- tures to i.i.d. Gaussian random features, we refer the reader to Appendix E.
4.1. Tabular Regression and Classification
We experiment on all datasets of the curated OpenML. tabular regression (Fischer et al., 2023) and clas- sification (Bischl et al., 2021) benchmark suites with 200 or fewer features. This amounts to a total of 91 datasets per model. Due to the large number of datasets, we limit ourselves to 5000 observations per dataset. We preprocess each dataset by ooe encoding all categorical variables and normalizing all numerical features to have zero mean and variance one.
Datasets:
We use nested 5-fold cross- validation (CV) procedure to tune and evaluate all mod- els, run independently for each dataset. The innermost CV is used to tune all hyperparameters, for which we use the Bayesian hyperparameter tuning library Optuna (Akiba et al., 2019). For regression, we use MSE loss, and for classification, we use cross-entropy loss. All experiments are run on a single CPU core on an institutional HPC clus- ter, mostly comprised of AMD EPYC 7742 nodes. We report the average test scores for each model, as well as mean training times for single fit. The average relative rank of each model is presented in a critical difference di- agram, indicating statistically significant clusters based on a Wilcoxon signed-rant -ank test with Holm correction. This
Evaluation Procedure:
Results: Summary results for regression and classification
are presented in Tables I to 2 and Figures 2 to 3, respectively. Full dataset-wise results are reported in Appendix E. We find that RFRBoost ranks higher than all other baseline models. For regression tasks, the muudient-greedy version of RFR- Boost outperforms the exact-greedy variant, contrary the observations of Suggala et al. (2020) for SGD-trained gra- dient representation boosting. This difference likely arises
7

---

Random Feature Representation Boosting
Table Average RMSE and single-core CPU fit times the
Table 2. Average accuracies and single-core CPU fit times on the OpenML classification datasets.
OpenML regression datasets.
MODEL
MEAN RMSE
FrT TIME (S)
MODEL
MEAN AcC
FiT TIME (S)
GRADIENT RERBOOST
0.408
1.688
RERBOOST
0.853
2.519
GREEDY RERBOOST Adense
0.408
2.734
XGBOOST
0.853
3.859
GREEDY RERBOOST Ading
0,415
1,631
E2E MLP RESNET
0.851
20.881
GREEDY RERBOOST Ascelar
0.434
1.024
RFNN
0.845
1.189
XGBOOST
0.394
1,958
LOGISTIC REGRESSION
0.821
0.165
E2E MLP RESNET
0.412
19.309
RENN
0.434
0.053
RIDGE REGRESSION
0.540
0.001
Logistic Regression
RFRBoost E2E MLP ResNet XGBoost
RFNN
Ridge gegessionn
2.45
RERBoost Gresdy Aseres
RFNN
Greedy AFRBoost Aucaer
XGacost
F2E MLP ResNet
Greedy RF RBott Asus
Figure 3. Critical difference diagram based on pairwise relative rank of test accuracy. Bars indicate no significant difference (a 0.05). The average rank is displayed for each model.
Figure 2. Critical difference diagram based on pairwise relative rank of test RMSE. Bars indicate no significant difference 0.05). The average rank is displayed for each model.
Table 3. Average test accuracies the concentric circles point cloud separation task, averaged across 10 runs.
because the SGD-based approach does not incorporate the LP(x) (μ4)-norm constraint during training, which is crucial for preserving the functional direction of the residual block. The test scores follow the ordering Adense > Adiag Ascalars demonstrating that RFRBoost is more expressive when map- ping random feature layers to the functional gradient, rather than simply stacking random feature layers. While XGBoost achieves slightly lower RMSE than RFRBoost, it performs worse in terms of average rank. Moreover, RFRBoost sig- nificantly outperforms both RENNs and E2E MLP ResNets, while being order of magnitude faster to train than the lat- ter. Although the reported training times are CPU-based, our implementation suggests both methods would benefit sim- ilarly from GPU acceleration, making the presented times
MODEL
MEAN Acc
STD DEV
RFRBoOST
0.997
0.002
RENN
0.887
0.037
E2E MIP RESNET
0.732
0.144
LOGISTIC REGRESSION
0.334
0.023
AFRBOOST
EZE MLP ResNet
representative.
4.2. Point Cloud Separation
Input
t-1
t-2
t-3
We evaluate RFRBoost on a challenging synthetic dataset originating from the neural ODE literature (Sander et al., 2021). The dataset consists of 10,000 points sampled from concentric circles, and the task is linearly separate (i.e. classify) the concentrie circles while restricting the ResNet hidden size to 2, see Figure 4. We compare RoRBoost to E2E MLP ResNets, while also presenting classification results for logistic regression and RENNs in Table 3. All models were trained with cross entropy loss, using a 5- fold CV grid search for hyperparameter tuning. For F2E
Figure 4. Point cloud separation of test data at cach layer.
MLP ResNets, the learning rate tuned, while for the other models, only the &, regularization of the classification head was tuned. The hidden size, residual block feature dimension, and activation function was fixed at 2, 512, and tanh, respectively, for all models. See Appendix E.3 for more details.
8

---

Random Feature Representation Boosting
Notably, the RFNN, which uses SWIM random features to map the initial 2-dimensional input to a higher-dimensional space before applying linear classifier, fails to classify all points correctly. RFRBoost, in contrast, achieves near- perfect linear separation by first mapping the random fea- tures to the functional gradient of the network representation, before applying a 2-dimensional linear classifier. This result somewhat surprising because RFRBoost does not rely on explicit Fourier features or a learnt radial basis, demonstrat- ing the power of gradient representation boosting. It further illustrates how RFRBoost can solve problems that are in- tractable for E2E-trained networks and RFNNs. Figure 4 shows that the E2E MLP ResNet correctly separates only two of the nine concentric rings, similar to the failure to converge observed by Sander et al. (2021).
rived closed-form solutions for greedy layer-wise boosting with MSE loss, and presented general fitting algorithm for arbitrary Ioss functions based on solving a quadrati- cally constrained least squares problem. Through extensive numerical experiments on tabular datasets for both regres- sion and classification, we demonstrated that RFRBoost significantly outperforms traditional RFNNS and end-to-end trained MLP ResNets in the small- to medium- scale regime where RFNNS are typically applied, while offering substan- tial computational advantages, and theoretical guarantees stemming from boosting theory. RFRBoost represents a sig- nificant step towards building powerful, stable, efficient, and theoretically sound deep networks using untrained random features. Future work will focus on extending R RFRBoost to other domains such as time series or image data, exploring different types of random features and momentum strate- gies, implementing more efficient GPU acceleration, scaling to large datasets, and using RFRBoost as an initialization strategy for large-scale end-to-end training.
4.3. Experiments on Larger-scale Datasets
To complement our experiments on the OpenML_benchmark suite, we conducted additional full-scale evaluations on four larger datasets (two with ~000 samples, two with ~500k samples) to assess performance and scalability in larger data regimes. Full experimental details, including dataset splits, hyperparameter grids, and plots of training time and pre- dictive performance versus training set size, are provided in Appendix E.5. We find that RFRBoost significantly out- performs traditional single-layer RFNNs across all tested datasets and training sizes, particularly as dataset size in- creases, highlighting its effectiveness in leveraging depth for random feature models. While RFRBoost performs strongly against E2E trained networks in peddium-sized data regimes, our findings indicate that E2E networks and XGBoost even- tually outperform RFRBoost as dataset size increases on 3 out of 4, and out of datasets, respectively. We hy- pothesize that using RFRBoost as an initialization strategy, followed by end-to-end fine-tuning, could be a promising di- rection to further enhance the performance of deep networks.
benchmark
A Acknowledgements
TC has been supported by the EPSRC Programme Grant EP/S026347/1. NZ has been supported by the Roth Schol- arship at Imperial College London, and acknowledges con- ference travel support from G-Research. We acknowl- edge computational resources and support provided by the Imperial College Research Computing Service (DOI: 10. 14 69 hppc/222)). the authors have applied Creative Commons Attribution (CC BY) licence to any Author Accepted Manuscript ver- sion arising.
2232). For the purpose of open access,
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
We leave this to future work.
5. Conclusion
References
This paper introduced RFRBoost, a novel method for con- structing deep residual random feature neural networks (RFNNs) using boosting theory. RFRBoost addresses the limitations of single-layer RENNS by using random fea- tures to learn optimal ResNet-like residual blocks that ap- proximate the negative functional gradient at each layer of the network, thereby enhancing performance while re- taining the computational benefits of convex optimization for RFNNs. This procedure can be viewed as performing functional gradient descent on the network neurons, which has connections to gradient boosting theory, as opposed to classical SGD which performs gradient descent on the network weights and biases. In our framework, we de-
Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '19, pp. 2022-22233111 2631, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450362016.
Allen-Zhu, Z., Li, Y., and Liang, Y. Learning and gener- alization in overparameterized neural networks, going beyond two layers. In Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc.,

---

Random Feature Representation Boosting
2019.
Cheng, T. S., Lucchi, A., Kratsios, A., Dokmanić, I., and Belius, D. A theoretical analysis of the test error of finite-rank kernel ridge regression. In Advances in Neural Information Processing Systems, volume 36, pp. 4767- 4798. Curran Associates, Inc., 2023.
Ayme, A., Boyer, C., Dieuleveut, A., and Scornet, E. Ran- dom features models: a way to study the success of naive imputation. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Pro- ceedings of Machine Learning Research, pp. 2108-2134. PMLR, 21-27 Jul 2024.
Cirone, N. M., Lemercier, M., and Salvi, C. Neural signa- ture kernels as unfnite-widtt--eeph---iiiii of controlled resnets. In Proceedings of the 40th International Confer- ence on Machine Learning, ICML'23. JMLR.org, 2023.
Badirli, S., Liu, X., Xing, Z., Bhowmik, A., Doan, K., and Keerthi, S. S. Gradient boosting neural networks: Grownet, 2020.
Cirone, N. M., Orvieto, A., Walker, B., Salvi, C., and Lyons, T. Theoretical foundations of deep selective state-space models. In The Thirty-eighth Annual Conference on Neu- ral Information Processing Systems, 2024.
Benavoli, A., Corani, G., and Mangili, F. Should we really use post-hoc tests based on mean-ranks? Journal of Machine Learning Research, 17,5):1-10, 2016.
Cortes, C.,, Gonzalvo, X., Kuznetsov, V., Mohri, M., and Yang. S. AdaNet: Adaptive structural learning of artificial neural networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceed- ings of Machine Learning Research, pp. 874-883. PMLR, 06-11 Aug 2017.
Bertin-Mahieux, T. Year Prediction MSD.
UCI Machine Learning Repository, 2011. DOI:
Biagini, F., Gonon, L., and Walter, N. Universal randomised signatures for generative time series modelling, 2024.
Cotter, F. and Kingsbury, N. Visualizing and improving scattering networks. In 2017 IEEE 27th International Workshop on Machine Learning for Signal Processing (MISP), pp. 1-6, 2017.
Bischl, B., Casalicchio, G., Feurer, M., Gijsbers, P., Hutter, F. Lang, M., Mantovani, R. G., van Rijn, J. N., and Van- schoren, J. OpenML benchmarking suites. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
Cuchiero, C.,, Gonon, L.., Grigoryeva, L., Ortega, J.-P., and Teichmann, J. Expressive power of randomized signature. In Advances in Neural Information Processing Systems, 2021.
Blackard, J. Covertype. UCI Machine Learning Repository, 1998. DOI: https://bi..rg//10244////2/
Bolager, E. L., Burak, I., Datar, C., Sun, Q., and Dietrich, Sampling weights of deep neural networks. In Advances in Neural Information Processing Systems, volume 36, pp. 63075-63116. Curran Associates, Inc., 2023.
Davis, O., Geraci, G., and Motamed, M. Deep learning without global optimization by random fourier neural networks, 2024.
Dempster, A., Petitjean, F., and Webb, G. I. Rocket: ex- ceptionally fast and accurate time series classification using random convolutional kernels. Data Mining and Knowledge Discovery, 34(5):1454 1495, 2020. ISSN 1573-756X.
Bruna, J. and Mallat, S. Invariant scattering convolution networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):182211866 2013.
Carratino, L., Rudi, A., and Rosasco, L. Learning with sgd and random features. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Dempster, A., Schmidt, D. F., and Webb, G. Hydra: com- peting convolutional kernels for fast and accurate time scries classification. Data Mining and Knowledge Dis- covery, 1779,1877--88 Sep 2023. ISSN 1573-756X.
Chen, R. T. Q., Rubanova, Y., Bettencourt, J., and Duvenaud, D. K. Neural ordinary differential equations. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
Demšar, J. Statistical comparisons of classifiers over multi- ple data sets. Journal of Machine Learning Research, 7 (1): 2006.
Dupont, E., Doucet, A., and Teh, Y. W. Augmented neural odes. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Chen, T. and Guestrin, C. Xgboost: A scalable tree boost- ing system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, pp. 785-794, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781458 1504442222...
E, W. A proposal on machine learning via dynamical sys- tems. Communications in Mathematics and Statistics. (1):1-11, Mar 2017. ISSN 2194-671X.
10

---

Huang. G.-B., Zhou, H., Ding, X., and Zhang, R. Extreme Random Feature Representation Boosting
Emami, S. and Martinez-Muñoz, G. Sequential training of neural networks with gradient boosting. IEEE Access, 11: 42738-42750, 2023.
Grinsztajn, L.,, Oyallon, E.,, and Varoquaux, G. Why do tree- based models still outperform deep learning on typical tabular data? In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871088.
Fischer, S. F., Feurer, M., and Bischl, B. OpenML-CTR23 a curated tabular regression benchmarking suite. In AutoML Conference 2023 (Workshop). 2023.
Hart, A., Hook, J., and Dawes, J. Embedding and approx- imation theorems for echo state networks. Neural Ner- works, 128:234-2444 2477 2020. ISSN 0893-6080.
Freund, Y. and Schapire, R. E. A decision decision-theoretic general- ization of on-line learning and an application to boosting.
Journal of Computer and System Sciences, 55(1):119-
139, 1997. ISSN 0022-0000.
He, K., Zhang, X., Ren, S., and Sun, Deep residual learning for image recognition. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), PP. 770-778, 2015.
Friedman, J., Hastie, T., and Tibshirani, R. Additive logistic regression: a statistical view of boosting (With discussion and a rejoinder by the authors). The Annals of Statistics, 28(2):337 - 407,201 2000.
Herrera, C., Krach, F., Ruyssen, P., and Teichmann, J. Opti- mal stopping via randomized neural networks. Frontiers of Mathematical Finance, 3 3(1):31-777 2024.
Friedman, J. H. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5):1188 1232, 2001.
Huang, F., Ash, J., Langford, J., and Schapire, R. Learning deep ResNet blocks sequentially using boosting theory. In Proceedings of the 35th International Conference on Muchine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2058-2061 PMLR, 10-15 Jul 2018.
Gallicehio, C., Micheli, A., and Pedrelli, L.. Deep reservoir computing: critical experimental analysis. Neurocom- puting, 268:87-99, 2017. ISSN 0925-2312. Advances in artificial neural networks, machine learning and computa- tional intelligence.
Huang. G.-B. An insight into extreme learning machines:
Gareía, S. and Herrera, An extension on "statistical comparisons of classifiers over multiple data sets" for all pairwise comparisons. Journal of Machine Learning Research, 9(89))2677-2694, 2008
Random neurons, random features and kernels. Cognitive Computation, 6:376-390, 09 2014.
Huang, G.-B., Zhu, Q.-Y., and Siew, C.-K. Extreme learning machine: new learning scheme of feedforward neural networks. In 2004 IEEE International Joint Conference Neural Networks (IEEE Cat. No.04CH37541), vol- ume 2, pp. 985-990 vol.2, 2004.
Gattiglio, G., Grigoryeva, L., and Tamborrino, M. Randnet- parareal: time-parallel PDE solver using random neural networks. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Huang, G.-B., Chen, I.., and Siew, C.-K. Universal ap- proximation using incremental constructive feedforward networks with random hidden nodes. IEEE Transactions on Neural Networks. 17(4):879 892, 2006.
Gonon, L. Random feature neural networks learn black- scholes type pdes without curse of dimensionality. Jour- nal of Machine Learning Research, 24(189):11511 2023.
Gonon, L. and Jacquier, A. Universal approximation theo- rem and eтror bounds for quantum neural networks and quantum reservoirs, 2023.
learning machine for regression and multiclass classifica- tion. IEEE Transactions Systems, Man, and Cybernet- ics, Part B (Cybernetics), (2(2):513-522 2012.
Gonon, L., Grigoryeva, L., and Ortega, J.-P. Approximation bounds for random neural networks and reservoir systems. The Annuls of Applied Probability, 33(1):28 69, 2023.
Innocenti, L., Lorenzo, S., Palmisano, I., Ferraro, A., Pater- nostro, M., and Palma, G. M. Potential and limitations of quantum extreme learning machines. Communications Physics, 6(1):118, May 2023. ISSN 2399-3650.
Gonon, L., Grigoryeva, L., and Ortega, J.PP. Infinite- dimensional reservoir computing. Neural Networks, 179: 106486, 2024. ISSN 0893-6080.
Jacquier, A. and Zuric, Z. Random neural networks for rough volatility, 2023.
Grigoryeva, L. and Ortega, J.PP. Universal discrete-time reservoir computers with stochastic inputs and linear read- outs using non- homooennuuuuu state-affine systems. Jour- nal of Machine Learning Research, 19(24):1-44 400, 2018.
Jaeger, H.
The" echo state" approach to analysing and training recurrent neural wethorks-with an erratum note'. Bonn, Germany: German National Research Center for

---

Random Feature Representation Boosting
Information Technology GMD Technical Report, 148, 01 2001.
Information Processing Systems, volume 12. MIT Press, 1999.
Kammonen, A., Kiessling. J., Plecháč, P., Sandberg, M., Szepessy, A., and Tempone, R. Smaller generalization error derived for a deep residual neural network com- pared with shallow networks. IMA Journal of Numerical Analysis, 43(5))2585-26333 09 2022. ISSN 0272-4979.
Mei, S. and Montanari, A. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
Middlehurst, M., Ismail-Fawar A., Guillaume, A., Holder, C., Guijo-Rubio, D., Bulatova, G., Tsaprounis. L., Mentel, L., Walter, M., Schäfer, P., and Bagnall, A. aeon: a python toolkit for learning from time series. Journal of Muchine Learning Research, 25(289):1-10, 2024.
Kar, P. and Karnick, H. Random feature maps for dot prod- uet kernels. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, vol- ume 22 of Proceedings of Machine Learning Research, pp. 583-591, La Palma, Canary Islands, 21-23 Apr 2012. PMLR.
Nelsen, N. H. and Stuart, A. M. The random feature model for input-output maps between banach spaces. SIAM Journal on Scientific Computing, 43(3):A3212-A3244, 2021.
Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma, W., Ye, Q., and Liu, T.-Y. Lightgbm: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems, volume 30. Curran As- sociates, Inc., 2017.
Neufeld, A. and Schmocker, P. Universal approximation property of banach space-valued random feature models including random neural networks, 2024.
Kidger, P., Morrill, J., Foster, J., and Lyons, T. Neural controlled differential equations for irregular time series. In Advances in Neural Information Processing Systems, volume 33, pp. 6696-6707, Curran Associates, Inc., 2020.
Nitanda, A. and Suzuki, T. Functional gradient boosting based on residual network perception. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3819-3828 PMLR, 10-15 Jul 2018.
Kidger, P., Foster, J., Li, X., and Lyons, T. J. Neural sdes as infinite-dimensiona gans. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. PMLR, 18- 18-24 Jul 2021.
Nitanda, A. and Suzuki, T. Functional gradient boosting for learning residual-like like networks with statistical guarantees. In Proceedings of the Twenty Third International Con- ference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 2981-2991. PMLR, 26-28 Aug 2020.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In Proceedings of the International Confer- ence on Learning Representations (ICLR), 2015.
Oyallon, E., Zagoruyko, S., Huang, G., Komodakis, N., Lacoste-Julien, S., Blaschko, M., and Belilovsky, E. Scat- tering networks for hybrid representation learning. IEEE Transactions Pattern Analysis and Machine Intelli- gence, 41(9))2208 222222222221,,,, 2019.
Lanthaler, S. and Nelsen, N. H. Error bounds for learn- ing with vector-valued random features. In Advances in Neural Information Processing Systems, volume 36, pp. 71834-71861. Curran Associates, Inc., 2023.
Li, Z., Ton, J..F., Oglic, D., and Sejdinovic, D. Towards unified analysis of random Fourier features. In Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp. 3905-3914, PMLR, 09-15 Jun 2019.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L.,, Desmaison, A., Köpf, A., Yang, F.,, Vetioo, Z.., Rai- son, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. PyTorch: an imperative style, peroopeefo deep learning library. Curran Associates Inc., Red Hook, NY, USA, 2019.
Lukoševičius, M. and Jaeger, H. Reservoir computing ap- proaches to recurrent neural network training. Computer Science Review, 3(3):127-1499 2009. ISSN 1574-0137.
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, E. Scikit-learn: Machine learning in python. J. Mach. Learn. Res., 12(mull)282552255 2830, November 2011. ISSN 1532- 4435.
Martfnez-Peña, R. and Ortega, J.PP. Quantum reservoir computing in finite dimensions. Phys. Rev. E, 107:035306, Mar 2023.
Mason, L., Baxter, J., Bartlett, P., and Frean, M. Boosting algorithms as gradient descent. In Advances in Neural
12

---

Random Feature Representation Boosting
Prabhu, A., Sinha, S., Kumaraguru, P., Tom, P., Sener, O., and Dokania, P. K. Random representations outperform online continually learned representations. In The Thirty- eighth Annual Conference on Neural Information Pro- cessing Systems, 2024.
Szabo, Z. and Sriperumbudur, B. On kernel derivative ap- proximation with random fourier features. In Proceedings of the Twenty-Second International Conference on Artifi- cial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 827-836. PMLR, 16- 18 Apr 2019.
Prokhorenkova, I.,, Gusev, G., Vorobev, A., Dorogush, A. V., and Gulin, A. Catboost: unbiased boosting with categor- ical features. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. (639-6649, Red Hook, NY, USA, 2018. Curran Associates Inc.
Tanaka, G., Yamane, T., Héroux, J. B., Nakane, R., Kanazawa, N., Takeda, S., Numata, H., Nakano, D., and Hirose, A. Recent advances in physical reservoir com- puting: A review. Neural Networks, 115:100-123, 2019.
ISSN 0893-6080.
Rahimi, A. and Recht, B. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
Trockman, A., Willmott, D., and Kolter, J. Z. Understanding the covariance structure of convolutional filters. In The Eleventh International Conference on Learning Repre- sentations, 2023.
Rahimi, A. and Recht, B. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008a.
Veit, A., Wilber, M. J., and Belongie, S. Residual networks behave like ensembles of relatively shallow networks. Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
Rahimi, A. and Recht, B. Uniform approximation of func- tions with random bases. In 46th Annual Allerton Con- ference on Communication, Control, and Computing, pp. 555 561, 2008b.
Walker, B., McLeod, A. D., Qin, T., Cheng, Y., Li, H., and Lyons, T. Log neural controlled differential equations: The lie brackets make a difference. In Forty-first Interna- tional Conference on Machine Learning, 2024.
Wang. C. and Feng, X. Optimal kernel quantile learning with random features. In Proceedings of the 41st In- ternational Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 50419-50452. PMLR, 21-27 Jul 2024.
Rudi, A. and Rosasco, L. Generalization properties of learn- ing with random features. In Advances in Neural Informa- tion Processing Systems, volume 30. Curran Associates, Inc., 2017.
Sander, M. E., Ablin, P., Blondel, M., and Peyré, G. Momen- tum residual neural networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. PMLR, 18 18-24 Jul 2021.
Wang. C., Bing, X., HE, X., and Wang, C. Towards theo- retical understanding of learning large-scale dependent data via random features. In Forty-first International Conference on Machine Learning, 2024.
Xiong, W., Facelli, G., Sahebi, M., Agnel, O., Chotibut, T., Thanasilp, S., and Holmes, Z. On fundamental aspects of quantum extreme learning machines, 2024.
Sinha, A. and Duchi, J. C. Learning kernels with random features. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
Yehudai, G. and Shamir, O. On the power and limitations of random features for understanding neural networks. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Sriperumbudur, B. and Szabo, Z. Optimal rates for ran- dom fourier features. In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
Yu, H., Li, H., Hua, G., Huang, G., and Shi, H. Boosted dynamic neural networks. In Proceedings of the Thirty-Sevente AAAI Conference on Artificial Intelli- gence and Thirty-Fifth Conference on Innovative Appli- cations of Artificial Intelligence and Thirteenth Sympo- sium on Educational Advances in Artificial Intelligence, AAAT23IAATT3/EAAT22 AAAI Press, 2023. ISBN 978-1-57735-888-0.
Suggala, A., Liu, B., and Ravikumar, P. Generalized boost- ing. In Advances in Neural Information Processing Sys- fems, volume 33, pp. 8787-8797. Curran Associates, Inc., 2020.
Sun, Y., Gilbert, A., and Tewari, A. But how does it work in theory? linear svm with random features. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
13

---

uniquely attained at Random Feature Representation Boosting
A. Analytic Solutions to Sandwiched Least Squares Problems
In this section, we derive the analytic closed form expressions of the sandwiched least squares problems presented in Theorem 3.1. We use NumPy notation for element and row indexing, i.c. X is matrix, then X; denotes the i'th of X. || || denotes the Frobenius norm.
Proposition A.1 (Scalar case). Let R E Ruxd W E Dxd A AER, R, and X E RnXD. Let > 0. Then the minimum of
J(A) Σ
R3 W TTW AX + +
1=1
(R, X
+E (W X,, R.)
Ascalar
|XW + nd
1 HE |W +
Proof. We first rewrite the objective JAA using the Frobenius norm
- -IIAAW R + AA3. T
J(A)
Differentiating with respect to A E R and setting J'( 0 gives
0 J'() 2 (XW) (AXW R) 22A
- A||WII +nA R)
from which the result follows by factoring out A. Note that the second derivative
(A) | 2A >
n
hence the problem is convex and the local minima is the unique global minima.
Python NumPy code for this is
XM (
top np- sum (R * XW)
3 bot = np. sum (XW XW) /
A top / (bot + 12_reg)
Proposition A.2 (Diagonal case). Let R Raxd W E Dxd A = ap) E RDD
and X E RaxD Let
Then the minimum of
J(A) = Σ R. WT T + A11
-
uniquely attained by the solution the system of linear equations
b= (C+AAA
where
C= WWT O X
b diag ( (WR... X).
14

---

Random Feature Representation Boosting
Proof. We expand (A) and find that
J(A) = [ aD)
RR - TAX + +|AlB
(Rs - W [aIN....... (R, 1 apXiol)) + ExEt ok
Differentiating with respect to specific ax gives
@J(ai, ([([i,,..... .... an)
1
2WWx))))) (R, 22--W W-- aa 2xaz
Dak
(WAX) R =
(WeXLe) W AX; + Xak
i=1
Σ
Aay
This implies that the value of A which minimizes the objective is the solution to the system of linear equations given by
b = (C)A
where for k,j E [D]
Ck. = Σ ( WiXiss
6y Σ R
W.X.
1=1
Simplifying obtain that
C WWT θ X
b b= diag (agg(WW) (WR R X).
This solution is unique since the objective is strictly convex with hessian given by 2 + 2XI.
Python code for this is
b np. meant ( (R B W.TI * X, axis=0)
C = (W @ W.I) * (X.T 8 X)
A np siwaag.sooveeeeeeeooooe.eeeeelee (C + 12_ reg np.eye (D), D)
Proposition A.3 (Dense case). Let E Badd W R Dxd A Dxp, and X RuXD Let > Then the minimum of
J(A)
r W Az; 2 +
X
i=1
k=
W AXT
R RT + A
uniquely obtained by solving the system of linear equations given by
WR x = WW AX X + XnA,
which can be solved using the spectral decompositions WWT = UT and X VANVT,
Ateenee U u
U-UTRRT W XV (An1 diag(A") diag(A dlag(A>))) (A>)))
where 2) denotes element-wir wise division, is the outer product, and 1 matrix of ones.
15

---

Random Feature Representation Boosting
Proof. Using the gradient chain rule find that
0 = (A(A)
2 W AX RR + 22A
WR X W
Letting WWT UA and x VAXVT be spectral decompositions, and setting Ā UTAV AV see that
UV AW AA* + AnA.
By inspecting this equation element-wise find that
LUTWR' XV)N= = A An. + AnArg
which implies that
Ax. = WR XV).. AW. AX + N2
from which the conclusion follows after change basis A U ÄVT The solution is unique since the problem is strictly convex, which is easily proved using the convexity of the Frobenius norn and the linearity of the matrix expressions involving A, together with the strict convexity of the regularization term.
Python code for this is
Sw, U np. 1 dinalg.eight (W 8 W.T)
SX, V = np. www.llin.i.ii.... eigh (X.7 8 X)
(U.I Nww R.T 8 X V)
(n*lambda_rew reg SM(:, None] KSX [None, :])
A u a 1 V.I
B. Functional Gradient Inner Product
In this section we prove Theorem 3.1, showing that minimizing the LL (p) inner product under a norm constraint for simple random feature residual block is equivalent to solving quadratically constrained least squares problem. We the same matrix notation in Appendix A.
Theorem B.1. Let μ n Ei= 8z, be an empirical measure, h E (4), and f e Lī(ps). Then solving
argmin AERPxP such that [AAll 1. (e..))
(h, Af)
is equivalent to solving the quadratically constrained least squares problem
subject to
{ =1
In particular, when F is full rank, we obtain the closed form solution
A Vn H F)F
|
where Raxp and H E RAXD are the matrices given by F., = {(z) and Hi M(x.))
16

---

Random Feature Representation Boosting
Proof. Using the definition of the L2(p (n)
norm for empirical measures, we find that
(Ma,), - Σ n
(h, Af n
(Hs AF))
(
Furthermore, the constraint can be expressed as
| P (m...)
|Af(=))) Σ |AF|1 =1,
Σ
(8)
with equality instead of inequality, since we always obtain a bigger inner product in magnitude by normalizing by ||AAl2p Minimizing (7) subject to (8) is equivalent to solving a constrained least squares problem, since we can write
- - ABI 1
Σ Σ - 1=1
AF)) I|BBI
where we see that the first term || [H; ||2 is constant w.r.t A, and the third term gives the constraint. Hence, minimizing the constrained least squares problem equivalent to maximizing the inner product, and the solution to the original problem is obtained by multiplying the least squares solution by -1 since we are interested in the argmin rather than the argmax.
Continuing, solve the quadratically constrained least squares problem, we introduce the Lagrangian
1 H
J(A
AFF/ - V/
AFF -1
n1
H AF 1 -n ( IAFT 1/ -1)
n
Differentiating with respect to A gives
-2 (H - AF AF - AF F. 0 VIJ((,
2
n
which implies that
(TF=(1-M)AFT)
and
1
A=
F)F
1- V
1
HUA-VV
1-
assuming that v # 1 and that F is of full rank, with SVD decomposition F UAVT. The constraint becomes
n || 11
HU
12
1)2 レン H
therefore - = + ||]
/n The solution to the constraint least squares problem is obtained by using the positive sign, hence
the solution the original problem is given by the negative sign.
If 1, then H F 0, implying that (H; AFd) 0 for all matrices A. Hence the same closed-fome solution holds in this case too.
Remark B.2. It is clear from the proof how to augment the expression for A when F is not of full rank. However, in practice we instead use ridge regression for increased numerical stability. A similar result as the above can be proven for ridge regression, albeit with a more complicated expression for A involving non-trivial combinations of A and We omit this detail here, and simply use ridge regression in practice. Note also that F(FT F) can be expressed as a pseudo- pseudo-inverse inverse of F, after suitable transpositions of the matrices involved.
17

---

Random Feature Representation Boosting
C. Gradient Calculations
For completeness, we derive the functional gradient used in BradientRFRRBoot,, for MSE loss, categorical cross-entropy loss, and binary cross-entropy loss. Recall that the functional gradient, in all cases, is given by
V2R(W, (x)
[WV L(W (()),
where V, denotes the gradient with respect to the i'th argument.
C.1. Mean Squared Error Loss
For regression, mean squared error loss (1,, 2/110 yll?. In this case, find that
Vil(I, = r y.
hence
V2R(W, = [ WV ((x), Y)
= =Erxx= [WW ((r) - Y)].
When 1 = Di (2,30) is an empirical measure, the above reads in matrix form as
G = wwwwwwx -WY
where X E R and Y E Raxd are the matrices given by X, (x;) and Y (vi)..
C.2. Binary Cross-Entropy Loss
Denote the binary cross-entropy (BCE) loss as (xx, y) yy (z)( (1 y) log(1 ((x),, where o(z)= = Ite the sigmoid function. The gradient of the BCE loss with respect to the logit (xx) is
al(x,)) v) (z(x) o(x) + 1-
o<x) - y
o-z(z) α(x) axx)
Using the chain rule together with the fact that d'(x) = ox)) - =(x)) gives that
vil(z,9)= 0l(x,y) v) 0a a(p(z)) y. do(x)) dx
whence we obtain
(2)( Epyxx=x (W(((WT (())) - v)]
C.3. Categorical Cross-Entropy Loss
The analysis for the multi-class case is similar the binary case. The cross-entropy loss 1 RK x (1,..., K} - (0) for logits with true label is given by
(xx = - (og(s((z))
where s is the softmax function defined by
exp(xx)
sy(x) ΣK exp(x;)
18

---

Random Feature Representation Boosting
We aim prove that Vil(a, p(z) ey. where by RRK the one-hot vector for y. To this, consider for any
1 s k S K the following:
0(( v)
(1)()
ark
0ok
d
(x) doy sy(x)
① exp(sTy)
(x) dax プラ= exp(x;)
kk
exp(ex) "
أ-ر exp(x;) - exp(x,) exp(xx)
(x)
Σ exp(2;)) )²
(Iy=kSy(x) ()g(()s(((x))
Sy (x)
sx(T) ly=k
Since this holds for all k, have that
Vil(x,y) s(x) Ey.
Then.
(2 p WV (()), Prixe= (WssW ((x)) ey
When μ = Ei= (z,,):) is an empirical measure, the above reads in matrix form as
G ( -
where P(X)= Baak is the matrix given by P(X)i sx (xx))) and Ey E Raak the matrix given by (Fy) )i,k: 1 =k-
D. Excess Risk Bound
In this section we study the excess risk bound of RFRBoost the framework of Generalized Boosting (Suggala et al., 2020). We take a slightly different approach in our proofs which streamlines the process: instead bounding the - |/ norm the rows of the weight matrices, we instead bound the maximum singular values mmxx
D.I. Preliminaries
We repeat the following definition from Section 3. Definition D.1 (Suggala et al. (2020)). Let (0, and 2 0. We say that Go+1 satisfies the (8, e)-aakk learning condition if there exists G such that
(g. V2R(W,, k1)) LP6))
+ V>R(WW, Bell
B Suppger4
||g|| (لاااا
Consider the sample-spliting variant of boosting, where at each boosting iteration we use an independent sample of size - ((..). denote the empirical measure of the 1-th independent sample. The risk bounds in
ア = =n/T. T. Let μr Σn the sequel depend on Rademacher complexities related to the class of weak feature transformations G, and set of linear predictors W, which we define below:
R(W.G. = E, sup
Pi W s(xr,)la)
WeW gEg:
19

---

Random Feature Representation Boosting
RGG)) B, sup = geG,
Pid [o(=,,,))
i=
where P.j are Rademacher random variables, that is, independent random variables taking values 1 and -1 with equal probability.
The excess risk bound of RFRBoost is based on the following result:
Theorem D.2 (Suggala et al. (2020)). Suppose that the loss 1 L-Lipschitz and M-smooth with respect to the first argument. Let the hypothesis set of linear predictors W be such that all W E: W satisfy Amia (WTWWWWW W) o 0 and Amax (WT)) S mmx Moreover, suppose for all that Gt satisfies the (3,ek)-waak learning condition for pt, and that all E Se are bounded with supx Ilg(X)ll2 S R. Let the boosting learning rates (no) be тΙt ct for some s E (842 1) and e >> 0. Then both the exact-greedy and prudient-greedy representation boosting algorithms of Section 2.2 satisfy the following risk bound for any W*, 2", and a E (0, (0,3(1- 8)), with probability at least Ô over datasets of size n.:
(8+1
T log n
R(WT, PT) S R(W", 4-) ;0)+ +
+ 2
LRR(W LDR(G)) + +
Ta
We aim to apply the excess risk bound of Theorem D.2 in the setting of RFRBoost. For simplicity, we consider only the traditional ResNet structure where the random feature layer fz(x) = (nn((B((())) only takes as input the previous layer of the ResNet and not the raw features. This corresponds to the weak feature transformation hypothesis class
G. {h o o 11- h H}
where H. is the set of simple residual blocks
H = {I + A Atanh(Ba Bx) (A) and Amax (B) bounded by A].
Here Amax denotes the maximum singular value. We will use the properties that ||Al|a A, ||A S AVD. ||A S A
[| & AvD, and B I X. Here As denotes the k-th row of A, and || Ipp the ép vector norm or matrix spectral norm.
To prove Theorem 3.4, need compute the Rademacher complexities of RFRBoost, and verify that our class of weak learners satisfy all the assumptions of Theorem D.2. The only critical assumption check is that sup xex 11 (x))2 is bounded. This is the case for our particular model class, since llge(z)llz ||AAI|2l| tanh B, S AyP. which follows from basic properties of vector and matrix norms.
||A tanh B, (z)ll2 S
The following lemma will prove useful for the computation of the Rademacher complexity of RFRBoost.
Lemma D.3 (Allen-Zhh AhllnnZZuuee et al. (2019), Proposition 1.) Let a R + R be a 1-Lipschitz function. Let FI,..., Fm be sets of functions X + R and suppose for each j E [m] there exists function f3 E F, satisfying supzex (of & R. Then
F
+ Σ
(5 : 1lll C, E.. ||l|a S
satisfies
m
CRlogm
R(F) < 24
Σ R(F,) +0 +0
Vni
j=1
D.2. RFRBoost Rademacher Computations
The proof follows along similar lines as Suggala et al. (2020), however, our hypothesis class is larger and the proof has to be adjusted accordingly. Our proof additionally differs by bounding the hypothesis class by the largest singular values rather than & norms, which we believe more natural and leads more representative bounds.
20

---

Random Feature Representation Boosting
Lemma D.4. Under the assumptions of Theorem 3.4, the Rademacher complexity R(Ge) satisfies
RGG - =0 (DDi (Dg(D)
Vn
Using basic properties of the supremum, Hölder's inequality, Hoeffding's inequality, and Lemma D.3, obtain the following:
Proof.
R(G,) E,
sup
Pi.e (Z),))
gegt
1=1
1
E
sup gE9,
72
D
E
sup BEROX Dx Ama (n))
(A (an((
km
1
\Vplogp vni
2 D
E
sup
Pi, (By, T, f
+ DO
BERPXD
j=1
1=1
Ann (B)
</plogy" Vii
<2A/DDVDE DIE
Σ
Pi 2 p (2e,t)
+ DO
4XGDDvD log D
</plogp' Vn.
100 (1 DO
Vū
DNjpDD D log (Dett + DO
(VDlog(p) Vni
(1-8)v
=o PDd log D)
The second inequality follows from Lemma D.3 and the fact that tanh bounded by 1. The third inequality uses Hölder's 's inequality, and the fourth follows from Hoeffding's inequality for bounded random variables. Finally, the fifth inequality follows from the fact that (x) s st-1 I1grlloon < Ayat² Φ = 4, 1 + 7/-9--
I- derived from the recursive definition of
Lemma D.5. Under the assumptions of Theorem 3.4, the Rademacher complexity R(W, 9t) satisfies
R(W.G.) = O podDà log(D)t--s
n
21

---

Random Feature Representation Boosting
Proof. We proceed similarly in the previous result, and obtain that
RWW, 9.) = Rp p
sup
MLs [WT [otaalll)l
gEgt
WE
12
1=1 j=1
$
E
sup WEW 72 gESt
Pis (W, (
jml
do ( (Aivp)) (AVVDD log D
(lemma) 2\1d
Ep
sup Σ
Vn
geb. i=1
pDd log( D)t
Xp xPVpD log D
< (prew result) 2d1d0
+ do
Vn
Vn
( pdDD' log(D)t
-o
Vni
Here we additionally used the fact that sup, [ax( sup, ((k,, tanh(Bo;:))():)) S À1 /D for Lemma D.3.
We obtain Theorem 3.4 by combining Theorem D.2 with Lemma D.5 and Lemma D.4, and using the bound that sup, 11( S Ayp.
E. Experimental Setup
This section provides additional details of the experimental setup, SWIM random features, evaluation procedures, baseline models, and hyperparameter ranges used in our numerical experiments.
E.I. SWIM Random Features
In our experiments, we use SWIM random features (Bolager et al., 2023) for initializing the dense layer weights, as opposed to traditional i.i.d. initialization. Let X' denote the input space and activation function. A SWIM layer is formally defined as follows:
Definition E.1 (Bolager al. (2023)). Let ((x E IRP represent the features of a neural network for input æ X. Consider dense layer + (Aa + b) to be added top of 4, where A "I b R and H is the number of neurons in the (2)
new layer. Let (x. - = C X' x X be pairs of training data points. Let
Φ (x (2)) (x (1)
A;
b. = - (Ac, (xx))) C1,
(9)
{2 1 (x (1) 1|2
where 6i and 02 are fixed constants. We say that æ + a (Ax + b) is a pair-sampled layer if the rows of the weight matrix A and the biases b are of the form (9).
The pairs of points (z("), 2 ( can be sampled uniformly based training data date-depe sampling scheme. In experiments, we adopt the gradient-based approach by Bolager et al. (2023). Pairs of data points are sampled at each layer + of the ResNet approximately proportional to
1 f(x ( (1) x (3) (0((1)) - (xx(3) +e
(10)
where e > and f is the true target function, i.c., the mapping z; to the true label yı = fx;;). Specifically, to avoid quadratic time complexity in dataset size we first consider the points x;!") 1,..., n, and then uniformly generate (1)
n offset points 2222) = Zetj.- We then sample H points from these proportional to q(.. ()). This ensures the sampling
procedure remains linear with respect to dataset size n.
22

---

Random Feature Representation Boosting
The constants ei and 02 are chosen such that the pre-activated neurons are symmetric about the input point ($(x))) + ((x) ))/2. /2. For general inputs, the pre-activation neuron j sampled layer is
(Al(a) + b)j = (A,, (())) (A,, ((2) (1 61
(2(1) (0) - ((x) ), ((x) - (1xx C1:
( (2) |12 ||2
and specifically, when applied to = and zj
(1)
get
(Ao(x,) b)j -1;
(A((11)))) b)j 02 C1
Thus, as suggested by Bolager al. (2023), setting C2 201 centers the pre-activation symmetrically about the mean (o(z) (1) + (xx (2x(2) //2. Intuitively, this facilitates the creation decision boundary between the two chosen points. The constant 0g what we refer as the SWIM scale in the hyperparameter section.
E.2. Model Architectures and Hyperparameter Ranges for OpenML Tasks
detail the hyperparameter ranges used when tuning all baseline models for the 91 regression and classification tasks of the curated OpenML benchmark suite. The hyperparameter tuning was conducted using the Bayesian optimization library Optuna (Akiba et al., 2019), with 100 trials per outer fold, model, and dataset, using an inner 5-fold cross validation. The specific ranges for each model are presented in Table 4.
Table 4. Hyperparameter ranges for OpenML experiments
MODEL
HYPERPARAMETER
RANGE
E2E MLP RESNET
N.LAYERS
TO
LR
10 TO 10 (LOG SCALE)
END LR FACAOOOOR
0.01 1.0 (LOG SCALE)
N.EPOCHS
10 SO (LOG SCALE)
LEIGHTDDECA
10 TO 10 (LOG SCALE)
BATCH_SIZE
128, 256, 384, 512
HIDDEN
16 TO 512 (LOG SCALE)
FEATURE
FIXED AT 512
RERBOOST
N.LAYERS
TO (LOG SCALE)
L2.LINPRED
10 TO 10 (LOG SCALE)
L2_GIT 1._GHAA
10-5 TO 10 (LOG SCALE)
BOOST
0.1 TO (L.G SCALE)
SWIM SCALE
0.25 TO 2.0
FEATURE DIM
FIXED AT 512
RFNN
L2 REG FEATURE DIM
10 TO 10 (LOG SCALE)
16 TO 512 (LOG SCALE)
SWIM SCALE
0.25 2.0
RIDGE/LOGUSTIC REGRESSION
L.2 REG
10 TO 10 (LOG SCALE)
XGBooST
ALPHA
10 3 TO 10 2 (L.OG SCALE)
LAMBDA
10 TO 100 (LOG SCALE)
LEARNING RATE
0.01 TO 0.5 (LOG SCALE)
N.ESTIMATORS
50 TO 1000 (LOG SCALE)
MAX_DEPTH
TO 10
For the E2E MLP ResNet, "hidden_dim" refers to the dimension D of the ResNet features ((x) E R,, and the feature dimension denotes the number of neurons the residual block (also known as bottleneck size, which was also fixed for
23

---

Random Feature Representation Boosting
RFRBoost). The residual blocks are structured sequentially as follows: [dense(hidden dim, feature_ding _dim), batchnorm, relu, dense(feature dim, hidden dim), batchnorm]. An additional upscaling layer used to match the input dimension the "hidden_dim"
We used the Acon library (Middlchurst et al., 2024) to generate the critical difference diagrams in Section 4.1. Below, we provide full dataset-wise results in Tables to for each model and dataset used in the evaluation, averaged across all folds. Figures and visualize these results using scatter plots overlaid with woxiker-whiskers plots, providing insight into the distribution and variability of performance across datasets. We refer the reader the critical difference diagrams for rigorous statistical comparison of model rankings across all datasets.
Table 5. Test classification scores OpenML datasets.
Dataset
Logistic Regression
E2E MLP
RFRBoost
RFNN
XGBoost
ID
ResNet
0.974 (0.005)
0.996 (0.002)
0.989 (0.004)
0.996 (0.001)
0.997 (0.002)
0.768 (0.005)
0.912 (0.008)
0.890 (0.009)
0.944 (0.009)
0.903 (0.015)
0.878 (0.033)
0.981 (0.006)
0.979 (0.004)
0.934 (0.042)
0.931 (0.031)
14
0.812 (0.011)
0.844 (0.017)
0.804 (0.018)
0.828 (0.020)
0.830 (0.008)
15
0.964 (0.016)
0.966 (0.011)
0.963 (0.017)
0.964 (0.015)
0.960 (0.012)
16
0.948 (0.004)
0.974 (0.009)
0,945 (0.008)
0.973 (0.007)
(0.016)
18
0.728 (0.010)
0.739 (0.010)
0.727 (0.010)
0.739 (0.007)
0.721 (0.017)
22
0.815 (0.012)
0.837 (0.004)
0.812 (0.011)
0.840 (0.017)
0.795 (0.012)
23
0.512 (0.054)
0,551 (0.038)
0.553 (0.044)
0.532 (0.035)
0.547 (0.022)
28
0.970 (0.005)
0.991 (0.003)
0.980 (0.006)
0.989 (0.005)
0.978 (0.004)
29
0.854 (0.017)
0.854 (0.024)
0.845 (0.024)
0.852 (0.027)
0.862 (0.026)
31
0.761 (0.023)
0.762 (0.028)
0.756 (0.028)
0.743 (0.039)
0.744 (0.031)
32
0.946 (0.002)
0.993 (0.003)
0.990 (0.002)
0.992 (0.001)
0.986 (0.003)
37
0.762 (0.020)
0.758 (0.027)
0.760 (0.032)
0.767 (0.025)
0.762 (0.034)
38
0.968 (0.005)
0.979 (0.005)
0.977 (0.004)
0.977 (0.004)
0.988 (0.004)
44
0.931 (0.007)
0.950 (0.004)
0.936 (0.009)
0.941 (0.009)
0.952 (0.002)
0.983 (0.006)
0.983 (0.010)
0.980 (0.010)
0.976 (0.016)
0.995 (0.007)
54
0.801 (0.026)
0.849 (0.018)
0.829 (0.021)
0.843 (0.015)
0.772 (0.019)
151
0.760 (0.015)
0.796
0.784 (0.015)
0.792 (0.010)
0.847 (0.013)
182
0.861 (0.009)
0.909 (0.007)
0.908 (0.007)
0.911 (0.009)
0.913 (0.006)
188
0.641 (0.057)
0.664 (0.049)
0.643 (0.031)
0.635 (0.038)
0.652 (0.029)
307
0.838 (0.012)
0.993 (0.002)
0.972 (0.016)
0.989 (0.010)
0.924 (0.031)
458
0.994 (0.000)
0.994 (0.007)
0.993 (0.006)
0.988 (0.013)
0.990 (0.006)
469
0.187 (0.023)
0.188 (0.028)
0.196 (0.021)
0.193 (0.028)
0.178 (0.031)
1049
0.908 (0.012)
0.910 (0.013)
0.904 (0.008)
0.907 (0.014)
0.919 (0.009)
1050
0.894 (0.013)
0.889 (0.010)
0.898 (0.010)
0.892 (0.006)
0.890 (0.007)
1053
0.808 (0.009)
0.807 (0.011)
0.806 (0.012)
0.810 (0.011)
0.809 (0.014)
1063
0.841 (0.023)
0.845 (0.039)
0.833 (0.024)
0.841 (0.020)
0.839 (0.021)
24

---

Random Feature Representation Boosting
Table 6. Test classification scores OpenML datasets.
Dataset
Logistic Regression
E2E MLP
RFRBoost
RFNN
XGBoost
ID
ResNet
1067
0.853 (0.019)
0.855 (0.018)
0.858 (0.015)
0.855 (0.016)
0.853 (0.012)
1068
0.925 (0.008)
0.927 (0.016)
0,928 (0.009)
0.928 (0.010)
0.935 (0.012)
1461
0.902 (0.008)
0.902 (0.005)
0.904 (0.009)
0.900 (0.006)
0.903 (0.005)
1462
0.988 (0.005)
1.000 (0.000)
1.000 (0.000)
1.000 (0.000)
0.997 (0.004)
1464
0.766 (0.039)
0.791 (0.037)
0.794 (0.046)
0.769 (0.048)
0.783 (0.043)
1475
0.478 (0.005)
0.545 (0.010)
0.534 (0.012)
0.570 (0.005)
0.601 (0.008)
1480
0.715 (0.037)
0.703 (0.017)
0.703 (0.011)
0,671 (0.033)
0.684 (0.020)
1486
0.943 (0.006)
0.949 (0.003)
0.946 (0.004)
0.950 (0.006)
0.959 (0.003)
1487
0.935 (0.012)
0.945 (0.012)
0.945 (0.012)
0.944 (0.009)
0.940 (0.011)
1489
0.748 (0.010)
0.876 (0.015)
0.864 (0.005)
0.906 (0.005)
0.903 (0.006)
1494
0.873 (0.016)
0.882 (0.016)
0.868 (0.018)
0.878 (0.015)
0.873 (0.010)
1497
0.701 (0.009)
0.929 (0.005)
0.907 (0.008)
0.944 (0.007)
0.998 (0.001)
1510
0.977 (0.004)
0.974 (0.008)
0.974 (0.014)
0.961 (0.023)
0.961 (0.013)
1590
0.850 (0.005)
0.858 (0.010)
0.856 (0.010)
0.851 (0.009)
0.865 (0.013)
4534
0.938 (0.007)
0.952 (0.010)
0.949 (0.003)
0.960 (0.009)
0.956 (0.008)
4538
0.478 (0.014)
0.554 (0.017)
0.513 (0.014)
0.606 (0.014)
0.660 (0.017)
6332
0.735 (0.031)
0.791 (0.024)
0.763 (0.009)
0.791 (0.023)
0.796 (0.021)
23381
0.626 (0.040)
0.640 (0.030)
0.624 (0.034)
0.566 (0.048)
0.612 (0.041)
23517
0.505 (0.010)
0..1600.009
0.502 (0.017)
0.489 (0.013)
0.500 00.012)
40499
0.997 (0.001)
0.997 (0.001)
0.992 (0.000)
0.999 (0.001)
0.985 (0.004)
40668
0.752 (0.017)
0.775 (0.014)
0.759 (0.019)
0.777 (0.010)
0.800 (0.014)
40701
0.867 (0.003)
0.936 (0.002)
0.923 (0.004)
0,951 (0.009)
0.953 (0.003)
40966
0.994 (0.005)
0.999 (0.002)
0.989 (0.007)
0.997 (0.002)
0.984 (0.016)
40975
0.932 (0.007)
0.997 (0.004)
0.977 (0.006)
0.999 (0.001)
0.994 (0.004)
40982
0.718 (0.028)
0.752 (0.016)
0.758 (0.024)
0.755 (0.028)
0.800 (0.018)
40983
0.971 (0.003)
0.986 (0.002)
0.987 (0.003)
0.988 (0.004)
0.983 (0.003)
40984
0.901 (0.009)
0.934 (0.012)
0.930 (0.007)
0.927 (0.011)
0.929 (0.011)
40994
0.961 (0.018)
0.957 (0.019)
0.957 (0.019)
0.946 (0.015)
0.944 (0.021)
41027
0.685 (0.004)
0.812 (0.007)
0.798 (0.012)
0.844 (0.007)
0.838 (0.006)
25

---

Random Feature Representation Boosting
1.0
0.8
Accuracy
0.6
0.4
0.2
Logistic Regression
RFRBooSt
RFNN
E2E MLP ResNet
XGBoost
Figure 5. Scatter and box-and-whiskers plot of classification accuracy across all OpenML datasets. Each dot corresponds to a single dataset, and box plots summarize distribution each model.
0.8
RMSE (lower is better)
0.6
0.4
0.2
0.0
Ridge Regression
Greedy RFRBoost Ascalar
Greedy RERBooSt Adiag
Greedy RERBoost Adense
Gradient RERBoost
RFNN
E2E MLP ResNet
XGBoost
Figure 6. Scatter and box-and- whiskeris plot of regression RMSE across all OpenML datasets. Each dot corresponds single dataset, and box plots summarize the distribution for each model.
26

---

Random Feature Representation Boosting
Table 7. Test RMSE scores on OpenMI. regression datasets.
Greedy
Greedy RFRBoost
Greedy RFRBoost
E2E
Dataset ID
Ridge
Gradient RFRBoost
RFRBoost
RFNN
ML.
XGBoost
Regression
Ascalar
Adiag
Adense
ResNet
41021
0.233 (0.012)
0.233 (0.013)
0.232 (0.013)
0.231 (0.012)
0.231 (0.011)
0.232 (0.012)
0.265 (0.011)
0.249 (0.011)
44956
0.647 (0.020)
0.631 (0.018)
0.621 (0.019)
0.615 (0.019)
0.616 (0.020)
0.622 (0.022)
0.614 (0.023)
0.633 (0.020)
44957
0.688 (0.033)
0.362 (0.026)
0.246 (0.017)
0.238 (0.011)
0.233 (0.013)
0.347 (0.021)
0.316 (0.026)
0.197 (0.015)
44958
0.595 (0.010)
0.239 (0.019)
0.205 (0.010)
0.193 (0.016)
0.191 (0.027)
0.246 (0.022)
0.246 (0.025)
0.039 (0.011)
44959
0.589 (0.026)
0.304 (0.007)
0.275 (0.013)
0.277 (0.012)
0.286 (0.018)
0.305 (0.015)
0.311 (0.011)
0.245 (0.026)
44960
0.290 (0.028)
0.069 (0.013)
0.050 (0.005)
0.049 (0.005)
0.049 (0.006)
0.088 (0.024)
0.200 (0.027)
0.037 (0.007)
44962
0,446 (0.063)
0.448 (0.062)
0.448 (0.062)
0,446 (0.063)
0.447 (0.062)
0.447 (0.063)
0.474 (0.069)
0,452 (0.067)
44963
0.841 (0.011)
0.784 (0.005)
0.773 (0.020)
0.749 (0.008)
0.752 (0.005)
0.783 (0.013)
0.703 (0.017)
0.694 (0.010)
44964
0.521 (0.017)
0.443 (0.018)
0.406 (0.013)
0.395 (0.012)
0.398 (0.009)
0.443 (0.014)
0.369 (0.005)
0.340 (0.010)
44965
0.883 (0.066)
0.867 (0.071)
0.873 (0.077)
0.860 (0.075)
0.858 (0.070)
0.871 (0.077)
0.864 (0.075)
0.839 (0.081)
44966
0.719 (0.082)
0.724 (0.085)
0.718 (0. (0.084)
0.719 (0.082)
0.721 (0.080)
0.726 (0.075)
0.731 (0.079)
0.720 (0.080)
44967
0.786 (0.06 (
0.788 (0.071)
0.790 (0.08 068)
0.788 (0.065)
0.784 (0.067)
0.795 (0.069)
0.814
0.789 (0.056)
44969
0.409 (0.011)
0.084 (0.027)
0.027 (0.007)
0.022 (0.002)
0.025 (0.002)
0.061 (0.022)
0.058 (0.015)
0.086 (0.003)
44970
0.645 (0.042)
0.609 (0.044)
0.610 (0.044)
0.618 (0.035)
0,615 (0.040)
0.603 (0.045)
0,616 (0.029)
0,622 (0.043)
44971
0.840 (0.028)
0.789 (0.018)
0.779 (0.022)
0.780 (0.017)
0.777 (0.021)
0.785 (0.024)
0.729 (0.009)
0.685 (0.015)
44972
0.796 (0.036)
0.776 (0.028)
0.775 (0.030)
0.768 (0.026)
0.767 (0.030)
0.774 (0.026)
0.777 (0.029)
0.722 (0.012)
44973
0.602 (0.007)
0.287 (0.013)
0.235 (0.008)
0.194 (0.007)
0.194 (0.004)
0,284 (0.016)
0.177 (0.007)
0.244 (0.008)
44974
0.457 (0.014)
0.214 (0.013)
0.184 (0.015)
0.153 (0.008)
0.152 (0.007)
0.211 (0.012)
0.158 (0.012)
0.126 (0.012)
44975
0.026 (0.008)
0.027 (0.008)
0.026 (0.008)
0.026 (0.008)
0.026 (0.008)
0.026 (0.008)
0,056 (0.012)
0.109 (0.003)
44976
0.270 (0.004)
0.192 (0.007)
0.177 (0.009)
0.170 (0.005)
0.170 (0.006
0.196 (0.009)
0.161 (0.006)
0.192 (0.007)
44977
0.590 (0.021)
0.525 (0.019)
0.517 (0.016)
0.508 (0.019)
0.506 (0.021)
0.525 (0.018)
0.486 (0.020)
0.446 (0.022)
44978
0.242 (0.016)
0.149 (0.005)
0,145 (0.007)
0.146 (0.006)
0.148 (0.007)
0.149 (0.006)
0.142 (0.004)
0.134 (0.011)
44979
0.252 (0.015)
0.163 (0.015)
0.148 (0.012)
0.142 (0.010)
0.140 (0.010)
0.165 (0.013)
0.145 (0.011)
0.142 (0.011)
44980
0.766 (0.022)
0.430 (0.008)
0.324 (0.007)
0 (0.008)
0.317 (0.007)
0.438 (0.022)
0,275 (0.010)
0.457 (0.031)
44981
0.914 (0.017)
0.913 (0.016)
0.913 (0.017)
0.912 (0.017)
0.913 (0.017)
0.914 (0.017)
0.636 (0.015)
0.611 (0.006)
44983
0.431 (0.004)
0.263 (0.012)
0,250 (0.013)
0.247 (0.016)
0.244 (0.014)
0.257 (0.010)
0.235 (0.019)
0,229 (0.014)
44984
0.689 (0.023)
0.660 (0.023)
0.658 (0.024)
0.656 (0.022)
0.657 (0.023)
0.659 (0.023)
0.656 (0.023)
0.656 (0.023)
44987
0.334 (0.035)
0.233 (0.020)
0.194 (0.024)
0.183 (0.026)
0.192 (0.036)
0.246 (0.019)
0.229 (0.057)
0 (0.020)
44989
0.308 (0.010)
0.293 (0.009)
0.287 (0.006)
0.276 (0.012)
0.274 (0.013)
0.295 (0.009)
0.304 (0.016)
0.263 (0.005)
44990
0.404 (0.009)
0.395 (0.009)
0.396 (0.008)
0.395 (0.009)
0.393 (0.009)
0.399 (0.010)
0.405 (0.008)
0.399 (0.008)
44993
0.799 (0.017)
0.776 (0.020)
0.773 (0.017)
0.770 (0.018)
0.769 (0.019)
0.775 (0.017)
0.787 (0.018)
0.773 (0.019)
44994
0.265 (0.016)
0.215 (0.011)
0.216 (0.009)
0.215 (0.007)
0.216 (0.008)
0.216 (0.009)
0.231 (0.013)
0.225 (0.010)
45012
0.448 (0.027)
0.343 (0.020)
0.339 (0.019)
0.330 (0.018)
0.330 (0.017)
0.341 (0.016)
0,351 (0.022)
0,331 (0.021)
45402
0.621 (0.023)
0.526 (0.024)
0.507 (0.017)
0.499 (0.017)
0.497 (0.019)
0.532 (0.019)
0.474 (0.030)
0.502 (0.029)
E.3. Point Cloud Separation Task
For the point cloud separation task, we use the same model structure as in the OpenMI. experiments, but fix the number of ResNet layers 3 residual blocks. We additionally fix the activation to tanh and feature dimension 512 for all models. Further architectural details and learning rate annealing strategies are consistent with those described in Section 4.1 and Appendix E.2. The SWIM scale was fixed at 1.0 for all random feature models. We use 5,000 randomly sampled data points for training and validation, and leave the remaining 5,000 for the final test set.
The hyperparameter configurations for RFRBoost, E2B MLP ResNet, RFNN, and logistic regression are detailed below in Table 8.
27

---

Random Feature Representation Boosting
Table 8. Hyperparameter ranges for the point cloud separation task.
MODEL
HYPERPARAMETER
VALUES
RERBOOST
L2,CLS
CLS
[1. 1E-1, 1E-2, 1E-3, IE-4, 1E-5]
L.,GHA
IE-4
HIDDEN DIIM
2
FEATURE. DIM
512
BOOST LR
1.0
USE_BATCHNORM
TRUE
RENN
L2 CLS
[1. 1E-1, 1E-2, 1E-3, 1E-4, 1E-5] 512
FEATURE DIM
LOGISTIC REGRESSION
1.2
[1, 1E-1, 1E-2, 1E-3, 1R-4]
E2E MLP RESNET
LR
[1E-1, IE-2, 1E-3, 1E-4, 1E-5]
HIDDEN DIM
2
FEATURE
512
N N.EPOCHS
30
END LR FFACORR
0.01
WEIGHT DECAY
1E-5
BATCH SIZE
128
E.4. SWIM vs i.i.d Ablation Study
In this section, we present small ablation study comparing SWIM random features to standard i.i.d. Gaussian random features across OpenML regression and classification tasks. The evaluation procedure is the same as presented in Section 4.1, the only change being that the SWIM scale parameter is replaced by an i.i.d. scale parameter, ranging logarithmically from 0.1 10 for all models. Pairwise comparisons for each model variant are visualized in Figures represents dataset and compares the performance of SWIM and i.i.d. features. Summary statistics, including average RMSE/accuracy, number of dataset-wise wins, and average training time, reported in Tables 9 to 10.
8, where each point
Overall, performance differences between SWIM and i.i.d. features are small but consistent. For regression, WWIM-based models achieve lower mean RMSE across all variants, and win on 22 out of 34 datasets in the best case (Greedy RFRBoost Adense. For classification, accuracy is nearly identical across methods, though i.i.d. features slightly outperform SWIM in the total number of wins (32 out 56). SWIM-based methods typically incur slightly higher training time, reflecting the additional structure in their initialization. These results suggest that while SWIM can offer marginal gains in accuracy or RMSE, the benefits must be balanced against training efficiency.
Table 9, Comparison of SWTM vs i.i.d. feature initialization OpenMI. regression tasks.
MODEL
VARIANT
MEAN RMSE
WINS
FIT TIME (S)
RENN
SWIM
0.434
20
0.053
LLD.
0.441
14
0.029
GRADIENT RERBOOST
SWIM
0.408
18
1.688
LLD.
0.415
16
1.816
GREEDY RERBOOST Adense
SWIM
0.408
22
2.734
LLD.
0.416
12
2.667
GREEDY RERBOOST Ading
SWIM
0.415
19
1.631
L.D.D
0.415
15
1.490
GREEDY RERBOOST Aweslar
SWIM
0.434
22
1.024
L.D.D
0.443
12
0.720
28

---

Random Feature Representation Boosting
Table 10. Comparison of SWIM vs iid. feature initialization OpenML classificatton tasks.
MODEL
VARIANT
MEAN ACCURACY
WINS
FIT TIME (s)
RENN
SWIM
0.845
25
1.189
L.I.D.
0.844
31
0.634
GRADIENT RERBOOST
SWIM
0.853
32
2.519
L.I.D.
0,850
24
2.350
RERBoost
RFNN
SWIM wins: 32, i.f.d. wins: 24, ties:
wins: 25,
wins: 31, ties:
1.0
grught of
I.I.d. wins here
0.9
M.d.d here
1l.d Accuracy
iidd Accuracy
0.7
0.7
0.6
0.6
0.5
0.5
SWIM wins here
SWIM wins here
0.3
0.2
0.4 SWIM Accuracy
SWIM Accuracy
Figure 7. Comparison of classification accuracy using SWIM versus i.idd Gaussian random features across OpenML datasets. Each scatter plot compares accuracy per-dataset basis for different model variants. Points below the diagonal indicate better performance with SWIM.
29

---

Random Feature Representation Boosting
Gradient RERBoost
RENN
SWIM wins: 18, L..d. wins: 16, ties:
SWIM wins: 20, L.dd. wins: 14, ties:
SWIM wins here
SWIM wins here
l.d. RMSE
0.6
1.d. RMSE
0.6
L.d.
f.d.
0.2
0.4
0.6 SWIM RMSE
0.8
1.0
0.2
0.4
0.6 SWIM RMSE
0.8
1.0
Greedy RFRBoost Ascaler
Greedy RFRBoost Agieg
SWIM wins: 22, L..dd wins: 12, ties:
SWIM wins: 19, 1.i.d. wins: 15, ties:
SWIM wins here
SWIM wins here
1..d RMSE
0.6
RMSE
0.4
0.4
go
I...d. wins here
L... wins here
0.2
0.2
0.4
0.6
1.0
RMSE
Greedy RERBoost Agense 22, i.i.d. wins: 12,
SWIM wins here
0.6
i.d.
L...d wins here
0.2
0.2
0.4
0.6
0.0
1.0
SWIM RMSE
Figure 8. Comparison of RMSE using SWIM versus i.i.d. Gaussian random features across OpenML regression tasks. Each scatter plot compares RMSE per dataset for different model variants. Points above the diagonal indicate better performance with SWIM.
30

---

Random Feature Representation Boosting
E.5. Supplementary Larger-Scale Experiments
To further assess the scalability and performance of RFRBoost relative baseline models, we conducted experiments on four larger datasets: two of the largest from the OpenML Benchmark suite used in this work (each with approximately 100k samples
classification: ID 23517; one regression: ID 44975), and two widely-used benchmark datasets with approximately 500k samples (one classification: CoverType (Blackard, 1998); one regression: YearPredictionMSD (YPMSD) (Bertin-Mahiiux, 101
For these larger-scale evaluations, we employed a hold-out test set strategy. Hyperparameters for each model were selected via a grid search performed on a 20% validation split of the training data. The models considered are consistent with those in Section 4.1: E2E MLP ResNet, Gradient RFRBoost, Logistic/Ridge Regression, RFNN, and XGBoost. To analyze performance trends with increasing data availability, models trained exponentially increasing subsets of the training data, starting from 2048 samples (2 up to the maximum available training size for each dataset.
For the OLenML datasets, the test sets were defined as 33% (ID 23517, classification) and 11% (ID 44975, regression) of the total instances, resulting in a maximum training set size of approximately 64,000 instances (216). For YPMSD (regression), we adhered to the designated split: the first 463,715 examples for training and the subsequent 51 1,630 examples for testing. For CoverType (classification), we used the standard train test split provided by the popular Python machine learning library Scikit-learn (Pedregosa al., 201 1). yielding 464,809 training and 1 116203 test instances.
The hyperparameter grids used for each model in these experiments are detailed in Table 11. To account for variability, each experiment was repeated 5 times with different random seeds for each model. All experiments were carried out on single NVIDIA RTX 6000 (Turing architecture) GPU.
Table 11. Hyperparameter grid for the larger-scale experiments.
MODEL
HYPERPARAMETER
VALUES
RERBOOST
L2 CLS
[IE-1, 1E-2, 1E-3, 1B-4, 1B-5J [1. 6,
N LAYERS
FEATURE_DIM
512
BOOST_IR
1.0
RENN
L2
[IE-1, 1E-2, 1E-3, 16-4, LB-5] 512
FEATURE
LOGISTIC/RIDGE REGRESSION
L2
[IE-1, 1E-2, 1E-3, 16-4]
XGBOOST
LR
10.1, 0.033, 0.01] [250, 500, 1000] 3, 10] 1.0
N N.ESTIMATORS
MAX_DEPTH
LAMBDA
E2E MLP RESNET
LR
[IE-1, 1F-2, 1F-3]
N_EPOCHS
[10, 20,30] 30]
FEATURE DIM
512
END LR FACTOR
0.01
WEIGHT DECAY
1E-5
BATCH_SIZE
256
The model training times and predictive performance (RMSE for regression, accuracy for classification) as a function of training set size are presented in Figure 9 and Figure 10, respectively. Regarding training times shown in Figure 9, Ridge/Logiitti Regression and RFNNS consistently exhibit the fastest training, as expected. RFRBoost consistently trains faster than both XGBoost and the E2E MLP ResNets across all datasets. Notably, on the OpenML ID 23517 dataset, RFRBoost trains faster than the single-layer RENN. This may be attributed to RFNNs fitting a potentially very wide random feature layer directly to the output targets (logits regression values), which can be computationally intensive. In contrast, RoRBoost constructs a comparatively shallow representation layer-wise with random feature residual blocks, where only the final, potentially lower-dimensional, representation is mapped to the output targets. In some scenarios, this may lead to lower computational times.
Considering the predictive performance shown in Figure 10, RFRBoost consistently and significantly outperforms the
31

---

Random Feature Representation Boosting
baseline single-layer RENN across all datasets and training sizes, demonstrating its effectiveness in using depth for random feature models to increase performance. This improvement is particularly pronounced the larger CoverType and YPMSD datasets, underscoring the benefit of RFRBoost's s deep, layer-wise construction. However, in the larger data regimes E2E trained MLP ResNets and XGBoost generally achieve superior predictive performance. The OpenML ID 23517 dataset stands out, however, as RFRBoost and Logistic Regression not only exhibit lower variance but also achieve the best overall performance. Furthermore, we find that XGBoost significantly underperforms on OpenML ID 44975 compared to all other baseline models. Given RFRBoost's strong performance relative to computational cost and its ability to construct meaningful deep representations, exploring its use as an initialization strategy for subsequent fine-tuning of end-to-end trained networks presents promising avenue for future research, potentially further enhancing the performance of E2E models.
Model Training
Model Training
CoverType
10
RFNN
RERBoost
10a
RfRBoost
XGBoost
XGBoast
10
Fidge
Logistic Regression
10
Training time
Training Time
10a
10a
10-4
10.
10-2
20
234
2-5
235
233
222
2
233
235
230
237
2.9
Training Sizo
Model Training Time on OpenML ID 44975
Model Training Time on OpenML ID 23517
RFNN
10a
10a
E2E MLP ResNet
Logistic Regression
RFNN
Training Time
101
AFRBoost
Training
10a
EZE MLP ResNet
Ridge
10-4
10a
10
10:1
23
232
233
2
2
2
23
222
2
2
235
2
Training Set Size
Training Set Size
Figure 9. Model training time (scconds, log scale) versus training set size on larger datasets. Lines represent the mean training time over 5 runs, and shaded areas indicate 95% confidence intervals.
32

---

Random Feature Representation Boosting
Model
CoverType
0.90
RFNN
RfR3ccst
RFRBoost
XGBoast
XGBoost
Ridge
Logistic Regnession
0.90
0.86
Acuracy
0.85
RMSE (twer
0.84
0.75
211
2-2
214
235
2
217
240
2
211
2.3
244
215
2
210
2.9
Set
Model Performance on OpenML ID 44975
Model Performance on OpenML ID 23517
RFMN
0.16
E2E MLP Resflet
0.14
0.525
Ridge
0.12
RASE (lower beteri
0.520
0.30
Accurecy
0.08
0.515
0.06
RFNN
0.04
E2E MLP ResNet
0.02
0.505
Logistic Regression
212
233
2
2
2.1
212
2
2
2
2
Training Set Size
Training Set Size
Figure 10. Model predictive performance (RMSE for regression, accuracy for classification) versus training set size on larger datasets. Lines represent the performance over 5 runs, and shaded indicate 95% confidence intervals.
33


Reviews:
[{"review_id": "flbX6lU4R7", "reviewer": "Reviewer_fxoT", "summary": "This paper studies the problem of boosting random features and its connection to ResNets. At stage $t$, a new group of random features $f_t = f_t(\\Phi_{t-1})$ are generated and added to the previous stage's features $\\Phi_t = \\Phi_{t-1} + \\Delta_t f_t$ where the matrix $\\Delta_t$ gets optimized and the readout weights are also optimized. The authors study constraining $\\Delta_t$ in various ways, optimization routines are derived for square and convex losses at the readout, and some theory is provided. In the last section, the method is compared to XGBoost, standard random feature methods, an end-to-end trained ResNet, and ridge regression applied to OpenML regression and classification tasks.", "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": "We sincerely thank Reviewer fxoT for their careful reading and constructive feedback. Below, we provide detailed responses to each of the points raised.\n\n**On Critical Difference Diagrams:** To facilitate a meaningful comparison across all baseline models and RFRBoost variants, we use the Wilcoxon signed-rank test with Holm correction, as mentioned in Sec. 4.1 Evaluation Procedure. This statistical test assesses significant pairwise differences between models, and the average relative ranks and statistically significant groupings are presented visually in critical difference diagrams (Figures 2 and 3). If two models are connected by bars, then the difference between the two methods is not statistically significant. This is a well-established methodology for comparing multiple algorithms across multiple datasets [Demšar, 2006; Benavoli et al., 2016] and is standard practice within the broader statistical learning and data mining literature (see also the enthusiasm of Reviewer JjfD regarding the use of Wilcoxon signed-rank test). We aim to explain this in more detail in the revised manuscript.\n\n**Presentation of Results Tables:** We agree that presenting only mean scores limits the interpretation of the results. To address this, we will incorporated your suggestion of creating scatter plots overlaid with box-and-whiskers plots to visualize the distribution and variability of performance across all 91 datasets for each method. The critical difference diagrams (Figures 2 and 3) complement this by indicating which observed differences in relative rank are statistically significant. Furthermore, we will add a section to the Appendix with complete dataset-wise results for each model. All regression targets have been normalized to have 0 mean and variance 1 (Section 4.1), hence the results should be relatively comparable.\n\n**Dataset Size & Scalability:**\nPlease see `Dataset Size and Scalability' in the response to Reviewer XEnQ.\n\n**SWIM initialization vs iid:** We performed experiments using both iid random features and SWIM initialized random features. We initially presented only the SWIM results in the main paper due to slightly superior empirical performance and the 8 page space constraint. In the revised manuscript, we will add an ablation study with pairwise plots directly comparing RFRBoost with iid features versus SWIM features, quantifying the (small) difference in performance. For example, SWIM features only beat iid features 51 out of 91 times.\n\n**How were the methods implemented?** We will add this missing detail to the revised manuscript. All baseline models were implemented in PyTorch, and RFRBoost in particular was implemented following Algorithms 1 and 2. We used LBFG-S as the minimizer for log likelihood loss, and standard torch linear algebra routines for the (sandwiched) least squares, following our derived formulas in the Appendix. E2E ResNets were trained with Adam as described in Section 4.1. The full code is currently contained in the supplementary material and we will additionally release it in a public repository upon acceptance. \n\n**Pseudoinverse:** Thanks for this remark. We will point out the alternative expression in terms of the pseudoinverse in the revised version.\n\n**Theoretical Regret Bound:** Our regret bound in Theorem 3.4 is of the same order as similar results in the literature, e.g. Suggala et al (2020) Corollary 4.3. We will make this clearer in the revised manuscript.\n\nMinor comments:\n\n**Notational confusion: $\\nabla_i, \\Delta_i, \\partial_i$:** \nOur original motivation for using $\\Delta_t$ stemmed from the connection to the discrete time step in the Euler discretization view of ResNets (Eq. 1). Recognizing the ambiguity, we have replaced $\\Delta_t$ (the linear map within the residual block) with $A_t$ throughout the paper. We have also ensured that the text in Section 2 and Appendix B/C clearly specifies when partial derivatives or gradients are taken with respect to specific function arguments.\n\n**Line 111 $W_t$ shape:** Thanks for spotting this. We will correct the dimensions in the revised manuscript.\n\n**Lines 204-207 'diagonal $\\Delta_t$':** We have improved the text to make it clearer that we only consider $\\Delta_{\\text{diag}}$ and  $\\Delta_{\\text{scalar}}$ in the case when hidden size is equal to feature dimension size $D=p$. The dense case is free of this restriction, allowing for rectangular matrices.\n\n**Sandwiched Least Squares:** We have modified the paper to properly address the 'sandwiched least squares' problems as Generalized Sylvester Equations.\n\n**Usage of 'amount of say':** While \"amount of say\" is standard terminology used in the classical boosting literature, notably in AdaBoost [Freund & Schapire, 1997], we understand it may be unfamiliar to a broader audience. We have adopted your suggestion and replaced it with \"line search step size\" or similar phrasing for improved clarity.\n\n---\n\nWe hope these responses and revisions address your concerns adequately.", "claims_and_evidence": "A number of tables are shown comparing the mean RMSE and fit times (across tasks) for the different methods. In general, the proposed method is close to as fast as XGBoost and shows similar performance. However, I have some issues with how the data are presented:\n* Fig 2 and 3 \"critical difference diagrams\" are not discussed within the text as far as I can see. I am not familiar with this method of presenting data. This needs to be explained, since I don't know what I'm seeing here.\n* Tables 1 and 2 are presented without any error bars on the RMSE or time numbers. The reader cannot evaluate whether these differences are significant or not. Since these numbers summarize performance over a large number of datasets (91 across both tables), we don't know how things vary here. \n* Rather than summary tables like 1 & 2, it would be better to see the entire distribution of RMSE and fit time on all tasks. This could be shown with a plot of accuracy versus method with all datasets plotted as points and perhaps a box and whisker on top. I'm not familiar with how regression targets are generated in the OpenML datasets, but if these are of drastically different scales then summarizing this with mean RMSE will be misleading. \n* The methods are meant to be scalable, however the authors restrict their study to datasets with less than 200 features and restrict themselves to 5000 observations per dataset. I'm not sure this is justified! If the fit times are as small as are reported, it seems reasonable to at least test a few larger datasets.", "methods_and_evaluation_criteria": "The method is only used with SWIM random features. These seem pretty specialized. How much do the results depend on this? These features depend on the previous layer features and data, but many people are interested in random feature models with, say, iid random Gaussian weights. Can you comment on whether the method works with these?\n\nI think the OpenML datasets that are used seem fine. The point cloud separation task is pretty standard from the classification literature, but other \"point cloud separation\" data could be chosen as well.\n\nI have listed other critiques of the evaluation above.", "theoretical_claims": "I checked the math for the least-squares problems that were solved for Theorem 3.1 I didn't find any issues. For Theorem 3.2, it could be simplifying to write the expression for the optimal $\\Delta$ in terms of the pseudoinverse. If you change your definitions $F \\to F^T$ and $G \\to G^T$ then you get that \n$$\\Delta = \\frac{\\sqrt{n}}{ \\| G \\|_F} G F^\\dagger$$\nwhich is pretty evident from the minimization problem.\n\nI'm not sure how useful the theoretical guarantee (Thm 3.4) is. I'm not sure if this is vacuous or not. How does this compare to other methods, for instance those in the Suggala et al (2020) paper that is referenced?", "experimental_designs_or_analyses": "Listed above in claims/evidence\n\nHow were the methods implemented?", "relation_to_broader_scientific_literature": "There seems to be a pretty good review of the existing literature, at least to my knowledge.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "My main concern with the paper is that I think the presentation of the experimental results is weak. If strengthened, I think the paper would be much better supported. Perhaps too much of the paper is taken up by Section 2 discussing all the various boosting methods.", "other_comments_or_suggestions": "I have a number of small issues that I hope the authors will address here:\n* Notation $\\Delta_i$, $\\partial_i$ is confusing and not standard to me. I believe the authors are indicating \"in terms of the second argument\" but should explain this notation.\n* Line 111 right col: $W_t$ shape $C \\times d$ isn't consistent with the $D \\times d$ you use later. \n* Lines 204-207 left col: Unclear what you mean by \"diagonal matrix\" for $Delta_t$ since it is rectangular. In general, how do $D$ and $d$ compare?\n* Lines 232-233 left col: The language \"sandwiched least squares\" is evocative, but these solutions are known as \"generalized Sylvester equation\" solutions of the form $\\sum_i A_i X B_i = C$ for unknown $X$. This could be worth mentioning.\n* (throughout) I found the language \"find amount of say\" kind of distracting and unnecessary. I think you are just doing a line search; you might rephrase as \"solve line search\".", "questions_for_authors": "Given above", "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": "6iZcWQFTZJ", "reviewer": "Reviewer_VGvF", "summary": "The paper introduces Random Feature Representation Boosting (RFRBoost), a novel approach that combines random feature neural networks (RFNNs) and gradient boosting theory to construct deep residual neural network models. The main idea is to build a deep ResNet structure using random feature layers that explicitly approximate the functional gradient of the network representation. This technique allows the resulting models to maintain computational efficiency while offering theoretical guarantees and improved performance.", "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": "We sincerely thank you for your thorough and positive assessment of our work and for your valuable comments. Below, we address your questions:\n\n**Empirical validation primarily focuses on tabular data:** The main question we set out to answer in our paper was whether one could build deep random feature neural networks (RFNNs) that significantly improve the performance of single-layer RFNNs while retaining their computational benefits. Since traditional RFNNs, using dense random projections, are primarily designed for tabular data, our paper focused on this domain. A careful study on tabular data is a necessary first step before looking at structured data like images or sequences, that would necessitate more complex random feature structures (e.g., random convolutional kernels or recurrent structures). Integrating such major architectural changes introduces complexities that make it difficult to address thoroughly within a single theory and within the scope of this single paper. We therefore consider this a valuable avenue for future research.\n\n**Q: The paper hypothesizes briefly that this improvement may arise due to the constraint on the functional gradient norm, but it lacks deeper analytical or empirical exploration of why this occurs.**\n\nWe appreciate the request for further clarification, however we are not quite sure what \"improvement\" here is referring to. We give two possible interpretations:\n\n1: Regarding the empirical observation in Table 1 where the gradient-greedy approach slightly outperforms the exact-greedy approach for regression tasks, we hypothesise that this could be due to an implicit regularisation effect. The gradient-greedy method, by focusing only on aligning with the functional gradient direction (under a norm constraint), might avoid overfitting compared to the exact-greedy method which directly minimizes the loss at each step. Providing a rigorous theoretical analysis of this phenomenon is challenging and would likely require fundamentally new tools, making it an interesting direction for future theoretical work.\n\n\n2: Regarding why our gradient-greedy approach succeeds while Suggala et al. (2020) observed it performed worse for medium-sized SGD-trained networks, we refer to our discussion at the end of Section 2.2. The crucial difference lies in how the gradient step is implemented. Our gradient-greedy approach (Algorithm 2 and Theorem 3.2) explicitly solves an optimization problem constrained to find the unit-norm functional direction of the residual block $g$ that best aligns with the negative functional gradient $-\\nabla \\widehat{R}$ (see Theorem 3.2). This ensures that the learned residual block $g$ points in the correct direction in function space, allowing for a valid functional first-order approximation used in boosting (Eq. 4). In contrast, standard SGD training of a residual block to minimize the functional inner product $\\langle g, \\nabla_2 \\widehat{R} \\rangle_{L_2^D({\\mu})}$ does not inherently enforce a constraint on the functional norm. We believe incorporating an explicit norm constraint, focusing on finding the optimal *direction*, is key to the success of the gradient-greedy strategy in our random feature setting.\n\n\n\n**Dataset Size and Scalability:** Please see `Dataset Size and Scalability' in response to Reviewer XEnQ.\n\n\n**Originality and Contribution** \nWe respectfully disagree that our contribution is merely an integration of established components. While random features, residual blocks, and boosting are known concepts, successfully constructing *deep* RFNNs presents unique and significant challenges, since naively stacking random layers has been observed to degrade performance. Our key contribution is providing the first principled framework for building deep RFNNs using *any general* random feature type by rigorously using ideas from gradient representation boosting (which differs from classical gradient boosting). The use of random features within this framework is not just an implementation detail; it is fundamental to enabling the computational efficiency and theoretical analysis central to RFRBoost. This includes the closed-form solutions of Theorem 3.1, and the theory leading to the quadratically constrained least squares problem of Theorem 3.2.\n\n\n\n\n\n**Reviewer Comment: No supplementary material:**  We would like to clarify that supplementary material containing the Python code for our model implementations (RFRBoost, baselines) and experimental procedures was provided with our submission. We commit to making this code publicly available in a repository upon acceptance to ensure full reproducibility.\n\n---\n\nWe hope these clarifications adequately address your comments and further highlight the contributions of our work.", "claims_and_evidence": "Overall, the claims made in this papers are supported well. Yet, additional clarification (or empirical validation) may be beneficial:\n\n1. Empirical validation primarily focuses on tabular datasets and one synthetic point-cloud dataset. This leaves unaddressed the applicability and performance on more structured or complex data (e.g., image, sequential, time-series).\n\n2. The paper hypothesizes briefly that this improvement may arise due to the constraint on the functional gradient norm, but it lacks deeper analytical or empirical exploration of why this occurs.\n\n3. While experimental evidence clearly supports improved computational efficiency relative to MLP ResNets, the scalability to larger or high-dimensional datasets remains unclear.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I did not check the correctness of the proofs in the Appendix. However, I have gone through the statement and claims in the main text of the paper, which looks good to me.", "experimental_designs_or_analyses": "The experimental design and analyses presented in the paper were thoroughly reviewed for soundness and validity. Overall, the methodology employed by the authors is strong and convincing, particularly with their selection of datasets. The authors utilized a broad and diverse set of 91 benchmark tabular datasets sourced from OpenML, providing a comprehensive basis for evaluating the proposed method. Furthermore, they adopted a rigorous nested 5-fold cross-validation strategy, effectively minimizing biases related to hyperparameter tuning and yielding reliable estimates of model generalization. Bayesian optimization with Optuna for hyperparameter tuning further enhances the rigor of their evaluation process.", "relation_to_broader_scientific_literature": "The key contributions of Random Feature Representation Boosting (RFRBoost) relate closely to existing literature on random feature neural networks (RFNNs), residual neural networks (ResNets), and gradient boosting theory. It integrates these approaches with gradient boosting concepts, which traditionally optimize ensembles of weak predictors (e.g., AdaBoost, Gradient Boosting Machines, XGBoost), but here, uniquely, optimize residual blocks within deep networks. Conceptually, the method builds upon recent theoretical advances that connect ResNets to gradient boosting and neural ordinary differential equations, generalizing these insights to deep RFNN architectures.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Although the method creatively combines random feature methods and gradient boosting, the primary conceptual ingredients—random features, residual blocks, and gradient boosting—are individually well-established. Thus, the originality of the contribution primarily arises from integration rather than fundamentally novel ideas.\n\nThe evaluation predominantly focuses on tabular datasets, limiting the significance of the method for broader machine learning contexts. Without evidence on structured datasets such as images, graphs, or sequential data, the broader significance of the proposed method remains unclear.\n\nThe surprising empirical advantage of gradient-greedy over exact-greedy approaches is not deeply analyzed theoretically or experimentally. Thus, despite its significance, the paper misses the opportunity to clarify why this approach works better, limiting conceptual clarity and interpretability.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "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": "zZreMJutMW", "reviewer": "Reviewer_XEnQ", "summary": "This paper studies an area of \"Extreeme learning\" where the weights of a non-linear transformation are set without any gradient calculations. In this instances, a Residual Network connection is used to derive the math for setting the procedure in a deep randomized network for MSE prediction problems specifically. The results improve upon  prior approaches in the space and show tentatively close RMSE to XGboost.\n\n\n--- Post Rebuttal ---\n\nI still support this paper. I hope the larger scale results are done for camera ready, the preliminary results are encouraging.", "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": "We appreciate your valuable comments and thoughtful points raised, especially the positive feedback regarding experimental rigour. We address your points below.\n\n**Are results MSE only?:** We apologize if this was unclear. Regression tasks are reported in Table 1 and Figure 2, while classification tasks (cross-entropy loss) are reported in Table 2 and Figure 3. We will revise the text in Section 4.1 to explicitly state that the regression and classification results are presented separately. Additionally, we will also add scatter/box-and-whiskers plots to better display the variability of the models, an ablation study for SWIM vs iid features, and full dataset-wise results in the Appendix.\n\nRFRBoost supports any convex loss function, and the main body of the paper was developed with this in mind. The exact-greedy analytical solution are a special case for MSE loss, but the gradient-greedy algorithm of Sec 3.3 and Algo. 2 supports general convex loss function. More importantly, in the gradient-greedy case we argued why previous work on SGD-based representation boosting overlooked the crucial detail of constraining the functional norm of the residual block to unit norm. This is essential to obtain a valid functional Taylor approximation of the risk, and we proved in Theorem 3.2 how to efficiently calculate and incorporate this constraint when using random features. This step provably involves solving a constrained least squares problem (where the functional gradient vector depends on the convex loss), which is where the MSE confusion might have stemmed from.\n\n\n**References on CNNs and scattering networks:** We thank the referee for pointing out this related field of study. We will incorporate these topics into the related works section in the revised manuscript. We agree that there is no immediate way to include these in experimentation as they concern image data. However, this is an interesting and important direction for future research to build upon the foundational work presented in our paper.\n\n\n**Code Blocks:** We are glad you found the embedded Python code snippets helpful for clarity and reproducibility. Following your suggestion, we have added corresponding code examples for the gradient calculation in Appendix C.\n\n**Dataset Size and Scalability:**\nThe decision to truncate datasets at 5000 observations stemmed primarily from computational resource constraints, balanced against the desire to experiment on a large number (91) of diverse datasets. Note that this threshold is substantially larger than the median dataset size (approx. 2400) within the OpenML Benchmark Suite. The primary computational bottlenecks were the E2E ResNet, and the rigorous nested 5-fold cross-validation procedure with Optuna (requiring 5*100 fits per dataset fold per model). Conducting such extensive evaluation on 91 datasets at their full size was computationally infeasible for us. However, we argue that evaluating performance on datasets of this scale is valuable, as this regime is highly relevant for many practical applications and is a common domain for RFNNs and extreme learning machines. Restricting dataset size is not uncommon in published papers (e.g. Bolager et al. 2023); we aimed for transparency by stating it directly in the main paper, rather than leaving this to the appendix.\n\nTo further address scalability we will:\n\n* Add an analysis of the computational complexity of Algorithms 1 and 2, noting its scaling behaviour $O(NTD^2p^2d)$ for training.\n\n* Add experiments in the Appendix where RFRBoost and baselines are trained on larger datasets using increasing fractions of the data (e.g., 10k, 25k, 50k, 100k, 200k, 400k samples, Covertype, YP-MSD). These will be displayed in a plot with number of samples on the X axis, and results/time on Y, to demonstrate scaling behaviour.\n\nScaling RFRBoost efficiently to datasets with millions of rows would likely require distributed computing paradigms such as MapReduce and implementation optimizations beyond the scope of this initial work, which we identify as an important direction for future research.\n\n\n**Terminology:** We have replaced the phrase \"law of the data\" with \"distribution of the data\". The original phrasing, while common in some areas of theoretical statistics, might be less familiar to the broader machine learning audience, and we have revised the manuscript accordingly.\n\n\n\n\n**Sensitivity of Parameters:** \nWe observed that optimal hyperparameters were highly dataset-dependent for *all* models, including XGBoost, ridge/logistic regression, E2E MLP ResNets, and RFRBoost. This variability motivated our use of a rigorous nested 5-fold CV scheme coupled with Optuna for hyperparameter tuning, ensuring a fair comparison on all datasets. Anecdotally, we observed a general trend where RFRBoost performance tended to improve with increasing depth, whereas the optimal E2E MLP ResNets depth was more varied.\n\n\n\n---\n\n\nWe hope these responses adequately address your questions.", "claims_and_evidence": "The theory appears sound but I have not checked it in detail. The experimental methodology is very thorough in a way that we can ensure the comparisons being made are valid (Finally, someone uses the Wilcoxon signed rank test for model comparisons in an ML paper!). However, sub-sampling all datasets to <=  5k observations significantly weakens the strength of the conclusions.", "methods_and_evaluation_criteria": "The scope of considered datasets is reasonable and the large number of datasets is good.", "theoretical_claims": "I have not the time to check the theory, but the appendix seems to have step-by-step derivations. I'm particularly thankful for the inclusion of \"Python code for this is\" blocks in much of the appendix, a refreshing balance of math and code exposition. I'd encourage the authors to add this to the C.3. Categorial Cross-Entropy section as well for completeness and so that others may experiment with classification problems (indeed, it is a little saddening they were not included at the onset).", "experimental_designs_or_analyses": "I have checked all the experiments. The average reader ay not appreciate the difficulty of problem 4.2, and including results of resents of varying size trained with normal Adam to demonstrate how much computational/representational power to perform such separation would be beneficial in educating the less-informed. \n\nWhile I understand the use of sub-sampling due to 91 datasets being used, including at least _some_ datasets with multiple larger sizes of varying orders of magnitude will majorly strengthen this work (e.g., benefit as datset sizes increase? Accuracy? Runtime? Lots of questions to answer).", "relation_to_broader_scientific_literature": "Not only are extrem learning machines useful in their own right, but they expose interesting scientific questions about network initialization strategies and the scope of what SGD at large can and is needed to learn and achieve good performance. I'm quite surprised that such high performance can be obtained without any active gradient steps or iterative calculations on a per-layer basis, which is fundamentally interesting in its own right.", "essential_references_not_discussed": "I'm broadly familiar with basic extreme learning literature. I think discussing the related work in randomized/non-learned convolutional filters for CNNs would significantly improve the article and provide less enlightened readers with a better scope of the possible future works. In particular, Scattering networks perform the same task for CNNs specifically, and while I see no trivial path to including them in experimentation, I think they help establish the broader interest in this field of work:\n\nSee: \n* Andreux, M., Angles, T., Exarchakis, G., Leonarduzzi, R., Rochette, G., Thiry, L., Zarka, J., Mallat, S., Andén, J., Belilovsky, E., Bruna, J., Lostanlen, V., Chaudhary, M., Hirn, M. J., Oyallon, E., Zhang, S., Cella, C., & Eickenberg, M. (2020). Kymatio: Scattering transforms in python. Journal of Machine Learning Research, 21(2012), 2012–2017.\n* Bruna, J., & Mallat, S. (2013). Invariant Scattering Convolution Networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8), 1872–1886. https://doi.org/10.1109/TPAMI.2012.230\n* Cotter, F., & Kingsbury, N. G. (2017). Visualizing and improving scattering networks. In N. Ueda, S. Watanabe, T. Matsui, J.-T. Chien, & J. Larsen (Eds.), 27th IEEE International Workshop on Machine Learning for Signal Processing, MLSP 2017, Tokyo, Japan, September 25-28, 2017 (pp. 1–6). IEEE. https://doi.org/10.1109/MLSP.2017.8168136\n* Mallat, S. (2012). Group Invariant Scattering. Communications on Pure and Applied Mathematics, 65(10), 1331–1398. https://doi.org/10.1002/cpa.21413\n* Oyallon, E., Belilovsky, E., & Zagoruyko, S. (2017). Scaling the Scattering Transform: Deep Hybrid Networks. 2017 IEEE International Conference on Computer Vision (ICCV), 5619–5628. https://doi.org/10.1109/ICCV.2017.599\n* Oyallon, E., Zagoruyko, S., Huang, G., Komodakis, N., Lacoste-Julien, S., Blaschko, M., & Belilovsky, E. (2019). Scattering Networks for Hybrid Representation Learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(9), 2208–2221. https://doi.org/10.1109/TPAMI.2018.2855738\n* Trockman, A., Willmott, D., & Kolter, J. Z. (2022). Understanding the Covariance Structure of Convolutional Filters (No. arXiv:2210.03651). arXiv. https://doi.org/10.48550/arXiv.2210.03651", "other_strengths_and_weaknesses": "See the above discussion.", "other_comments_or_suggestions": "Some of the early exposition is a bit hard to follow and lacks explanation. E.g., what is a \"law of the data\"? The notation makes it unclear when something is a _function_ vs. a weight matrix (e.g., $f_t$ looks like a function but isn't!). Making the notation more consistent in something like \"greek for functions\" or some other style would help.", "questions_for_authors": "* Can you run XGBoost and your best proposed methods on more of the fulll-sized datasets and report per-dataset and aggregate results? In both accuracy and runtime would be very valuable. \n* It seems like all experiments are MSE only, even though cross-entropy is stated to exist. Please clarify? Such problems should be presented as distinct groups rather than merged if both were done. \n* If you saved the results, can you report the sensitivity of XGBoost and your method with respect to the hyper-parameters? e.g., are there \"reliable defaults\" for your method you observe empirically, or evidence of less fluctuation due to using the approach?", "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": "xcAZ5MtYyR", "reviewer": "Reviewer_JjfD", "summary": "This paper introduces a Random Feature Representation Boosting method which uses random features at each layer and iteratively optimizes the functional gradient of the network representation. Experiments shows it outperforms traditional RFNNs and end-to-end trained MLP ResNets.", "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": "Thank you for taking the time to review our work and for your comments. Below, we address your questions and clarify the novelty and key differences of our work.\n\n**Q: What are the main differences between Random Feature Representation Boosting and existing Functional Boosting? Are dense Random Feature Representation Boosting and Functional Gradient Boosting the same?**\n\nWe appreciate the opportunity to clarify the distinctions. There are crucial differences between RFRBoost and what might be considered 'Existing Functional Gradient Boosting' (FGB), particularly the classical form used in methods like XGBoost.\n\n\n* **Boosting Target (Label Space vs. Feature Space):** Classical FGB, as outlined in our Section 2.1, typically operates in *label space*. It iteratively adds weak learners (like decision trees) to directly improve the model's prediction $F_t(x)$ by fitting the gradient of the loss with respect to the current prediction. In contrast, RFRBoost operates in the framework of *Gradient Representation Boosting* (GRB), detailed in Section 2.2. GRB boosts in *feature space*, iteratively building a deep residual-neural-network-like feature representation $\\Phi_t(x)$ by adding residual blocks $g_t$ that approximate the functional gradient of the loss with respect to the neural network representation itself. The final prediction is then made by a **single** linear model $W^T \\Phi_T(x)$ trained on the final representation. RFRBoost in the $\\Delta_{dense}$ regime is not equivalent to classical gradient boosting, because only a single linear model is trained on the boosted ResNet feature representation, rather than an ensemble of such models as in traditional gradient boosting.\n\n* **Random Feature Residual Blocks $g_t$:** While the theory of GRB allows for general function classes $g_t$, RFRBoost specifically uses fixed random features, allowing for optimized computations and specialized theoretical results. More specifically, we have $g_t = A_t f_t$, where $f_t = f_t(x, \\Phi_{t-1}(x))$ is generated using random weights, and only the linear map $A_t$ is trained using linear methods. This is fundamentally different from previous GRB methods that train bigger neural networks end-to-end as residual blocks using SGD. Our use of fixed random features is what enables efficient computational routines and allows for analytical solutions as per Theorems 3.1 and 3.2, while retaining the theoretical guarantees stemming from GRB (Theorem 3.3), and significantly improving performance (Section 4.1). A specific contribution within our gradient-greedy approach is the incorporation of a unit-norm constraint when learning $g_t$, differing from related literature. This ensures we correctly identify the optimal direction for the residual block in function space, which is crucial for the validity of the functional Taylor approximation of the risk. The special setting of random features is what allowed us to prove that this can be obtained by solving a constrained least squares problem (Theorem 3.2).\n\n**Q: Can you provide insights into why XGBoost achieves a lower RMSE in regression tasks?**\n\nIt is challenging to pinpoint a single definitive reason why XGBoost achieves slightly lower RMSE than RFRBoost in our experiments, as RFRBoost and XGBoost operate under fundamentally different paradigms as explained above. (Note however that while XGBoost achieves a slightly lower RMSE than RFRBoost, it performs worse in terms of average rank.)\n\nXGBoost uses classical gradient boosting (Section 2.1) to construct a large ensemble, comprising hundreds or thousands of decision trees. It learns by fitting trees to the residual errors (gradients) in label/logit space. Its strengths lie in its ability to capture complex interactions via hierarchical, axis-aligned splits and regularization techniques tailored for trees.\n\nRFRBoost, conversely, uses gradient representation boosting (Section 2.2) to build a deep feature representation $\\Phi_T(x)$ using random projections, followed by a single linear predictor. Its inductive bias stems from the nature of the random features used (e.g., dense projections with tanh activation in our experiments) and the layer-wise boosting process in feature space.\n\nPotential factors contributing to the observed difference on these specific benchmarks might be due to different inductive biases of the different approaches, ensembling vs using a single predictor, or difference in regularization of discrete trees versus continuous (logistic) regression targets. \n\n---\n\nWe hope this clarifies the methodological distinctions and provides context for the performance comparison. We aim to make this clearer in the revised paper.", "claims_and_evidence": "My question is what is the main differences between Random Feature Representation Boosting and Existing Functional Boosting, My understanding is the dense version of  Random Feature Representation Boosting is actually equal to Functional Gradient Boosting. And in latter evaluation, dense version performs better than the scalar and diag version.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Theoretical results show that RFRBoost aligns with the theoretical framework of Generalized Boosting, satisfying its weak learning conditions and risk bound guarantees.", "experimental_designs_or_analyses": "Can you provide insights into why XGBoost achieves a lower RMSE in regression tasks?", "relation_to_broader_scientific_literature": "This paper tries to extends boosting theory beyond function approximation to feature representation learning, integrating random feature methods with layer-wise boosting.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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: ## Summary
The paper introduces Random Feature Representation Boosting (RFRBoost), a method that combines random feature neural networks and gradient boosting theory to construct deep residual neural network models. It outperforms traditional RFNNs and end-to-end trained ResNets, and improves computational efficiency and performance compared to XGBoost and other methods.

## Strengths
- Utilized 91 benchmark tabular datasets from OpenML for comprehensive evaluation.
- Adopted a rigorous nested 5-fold cross-validation strategy to minimize hyperparameter tuning biases.
- RFRBoost integrates existing literature on RFNNs, ResNets, and gradient boosting theory.
- Uniquely optimizes residual blocks within deep networks, enhancing model generalization.
- Builds upon recent theoretical advances connecting ResNets to gradient boosting and neural ordinary differential equations.

## Weaknesses
- The paper's experimental results presentation is weak.
- The paper's section on various boosting methods is overly extensive.
- The method combines random feature methods and gradient boosting, but its originality comes from integration rather than novel ideas.
- The evaluation primarily focuses on tabular datasets, limiting its significance for broader machine learning contexts.
- The paper fails to analyze the empirical advantage of gradient-greedy over exact-greedy approaches, limiting conceptual clarity and interpretability.

## Conclusions

Based on the reviews, the author feedback and postrebuttal reviews, the paper is a weak accept for ICML since the experimental validation is the weakest part of the paper. The paper should include more experiments since the new figures provided does not show clearly an improvement over the baselines
Decision: Accept (poster)