One-Pass Feature Evolvable Learning with Theoretical Guarantees
Authors: Cun-Yuan Xing
Meng-Zhang Qian
Wu-Yang Chen
Wei Gao
Zhi-Hua Zhou
Venue: ICML 2025 poster (2025)
Keywords: Feature Evolvable Learning
Kernel Ortho-Mapping
Online Learning
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: This paper proposes a one-pass feature evolvable learning method with theoretical guarantees, introducing the Kernel Ortho-Mapping (KOM) discrepancy to characterize and exploit relationships between evolving feature spaces.

Abstract: Feature evolvable learning studies the scenario where old features will vanish and new features will emerge when learning with data streams, and various methods have been developed by utilizing some useful relationships from old features to new features, rather than re-training from scratch. In this work, we focus on two fundamental problems: How to characterize the relationships between two different feature spaces, and how to exploit those relationships for feature evolvable learning. We introduce the Kernel Ortho-Mapping (KOM) discrepancy to characterize relationships between two different feature spaces via kernel functions, and correlate with the optimal classifiers learned from different feature spaces. Based on this discrepancy, we develop the one-pass algorithm for feature evolvable learning, which requires going through all instances only once without storing the entire or partial training data. Our basic idea is to take online kernel learning with the random Fourier features and incorporate some feature and label relationships via the KOM discrepancy for feature evolvable learning.  We finally validate the effectiveness of our proposed method both theoretically and empirically.

One-Pass Feature Evolvable Learning with Theoretical Guarantees
Cun- Xing" 1 Meng-Zhang Qian
Wu-Yang Chen Wei Gao Zhi-Hua Zhou'
Abstract
we need deploy new sensors since old sensors will wear out, i.c., features corresponding to old sensors vanish but features corresponding to new sensors emerge.
Feature evolvable learning studies the scenario where old features will vanish and new features will emerge when learning with data streams, and various methods have been developed by utilizing some useful relationships from old features to new features, rather than re-training from scratch. In this work, we focus on two fundamental problems: How to characterize the relationships between two different feature spaces, and how to exploit those relationships for feature evolvable learning. We introduce the Kernel Ortho- Ortho-Mapping (KOM) dis- crepancy to characterize relationships between two different feature spaces via kernel functions, and correlate with the optimal classifiers learned from different feature spaces. Based on this dis- crepancy, we develop the one-pass algorithm for feature evolvable learning, which requires going through all instances only once without storing the entire or partial training data. Our basic idea is to take online kernel learning with the random Fourier features and incorporate some feature and label relationships via the KOM discrepancy for feature evolvable learning. We finally validate the effectiveness of our proposed method both theoretically and empirically.
Feature evolvable learning has been proposed to study the scenarios, where old features will vanish and new features will emerge when learning with streaming data. Recent years have witnessed increasing attention on this direction (Zhang al., 2016; Hou et al., 2019; Beyazit al., 2019; Gu et al., 2022: Hou et al., 2023; Schreckenberger et al., 2023; Chen & Liu, 2024). For feature evolvable learning, it is crucial to update model adaptively to accommodate new feature space but retain information of old feature space.
Various methods have been developed for feature evolvable learning by utilizing useful relationships from old features to new features, rather than re-training from seratch (Hou & Zhou, 2018; Zhang et al., 2020; Dong et al., 2022; Hou et al., 2022; Lian et al., 2023; Sajedi & Razzazi, 2024). This is helpful to prevent unnecessary wastes of computational resources and useful information from previous models over old features, and sometimes we may not collect sufficient training data to learn a stable model over new feature space,
Despite successes on the designs of practical algorithms, there are still some fundamental problems unsolved for feature evolvable learning. For example, how to present formalization on the relationship characterization between different feature spaces, as well as correlations with model performance. Another problem is how utilize useful relationships and information improve the performance for feature evolvable learning from theoretical view.
1. Introduction
Conventional machine learning generally works with the assumption that the data comes from a fixed feature space (Valiant, 1984; Shalev-Shwartz Ben-David, 2014; Good- fellow al., 2016; Mohri al., 2018; Alpaydin, 2021). In some real-world applications, however, we may face more open scenarios; for example, we deploy sensors to collect data in an environmental monitoring task, and each sensor corresponds to a feature. Due to finite lifespan of sensors,
This work focuses on the one-pass algorithm for feature evolvable learning with theoretical guarantees, and the main contributions can be summarized as follows:
We introduce the Kernel Ortho Mapping (KOM) dis- crepancy to characterize the relationships hetween two different feature spaces via kernel functions, which essentially reflects kernels' gap under the rotational invariance. We compare our KOM discrepancy with prior characterizations such kernel alignment and & distance (Cristianini et al., 2001; Romero et al., 2015).
'Equal contribution NNational Key Laboratory for Novel Soft- Technology, Nanjing University, China; School of Artificial Intelligence, Nanjing University, China. Correspondence to: Wei Gao <gaow @ www.@@ju..cdcco nju.edu.en>>
Based on the KOM discrepancy, we develop the one- pass algorithm for feature evolvable data streams, which requires going through all instances only once
Proceedings of the 4dnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
without storing the entire or partial training data, Our basic idea is to take online kernel learning with the random Fourier features and incorporate feature and label relationships via the KOM discrepancy'.
Feature evolution
Old feature space x(I
New feature space X
Instances x! from
Previous stage
old feature space x
Evolving stage
Time
Instances (a:;
from feature spaces x(1) and x
Theoretically, we establish the intrinsic relationship between the KOM discrepancy and optimal classifiers learned from different feature spaces, and present the convergence analysis to show better regret bounds via some good model initializations and relationships from old feature space and models.
Instances æ; from new feature space x(2)
Current stage
Figure 1. An illustration of feature evolvable stream.
with yi E (-1,+1), by minimizing the following loss
We finally conduct extensive experiments to validate the effectiveness of our OPFES method in comparison with the kate-of-theear methods on feature evolvable learning, i.e., method achieves better performance and the fastest convergence simultaneously.
1 Σ
he E arg min
E(h, (2;, y1)) + 1
hEH
where E(he, (xz 3)) = max(0, 1 - y Based on the representer theorem (Schölkopf & Smola, 2002), we have
The rest of this work is constructed follows:
Section 2 presents some preliminaries. Section 3 characterizes the relationship between two different feature spaces. Section 4 develops the OPFES method. Section 5 conducts extensive experiments. Section 6 concludes with future work.
he (xx))) = Σ a2 m;)) and |
Σ aaa,K(a;;
This shows that online kernel learning requires storing the entire training sample Sr, which makes it difficult for the large-scale datasets (Shen et al., 2019; Hong & Chae, 2021).
2. Preliminaries
Online kernel learning with random Fourier features has been an efficient way for large-scale online kernel learn- ing (Rahimi & Recht, 2007; Lu al., 2016), which approxi- mates high (or infinite) dimensional mapping sp(.) with the finte-aiieniional random Fourier features. Specifically, we approximate the kernel function of IC as
Feature evolvable learning studies evolvable feature spaces over time, where old features will vanish and new features will emerge. Let X(I & and ( S Rd44 be the old and new feature spaces, respectively. Feature evolvable learning includes three stages as follows:
K( mz)) = (vp(as) (p(=s))
[1] from the old Previous stage: receive instances x. space ( for / . ,T;
Σ pluu))((z un b,)o(z), un ux) (1)
Evolving stage: receive instances zz!" and [2] from the old space x and new space X respectively, for /. = Ti + 1, 1, ,., Ti + Ta with small positive Tai
where o(æ, ((,,,,,)) = cos((e u) + b), and p(-) is the spectral density function of K. Here, random vectors un are sampled i.i.d. from standard normal distribution N(0, Ia), and by are randomly selected independently and uniformly over [0, 2mr] For shift-invariant kernel K( 22), we have
Current stage: receive instances from the new space x for = Ti + Te 1,... ,Ti + T. + T2.
/ k(x) exp((i(((i) -i(x, u\) (2))((2)))) (2 JR"
p(u)
Figure presents an illustration single feature evolvable learning (Hou al., 2017: 2022; Lian et al., 2023), and we could make similar analysis for multiple cases.
where i is the imaginary unit. By random Fourier features, we can approximate a kernel classifier
Let -(.,-) -) be a positive-definte and symmetric kernel with mapping 4 X' + H from feature space X' to an RKHS H.. This work focuses on the ihirt-invariant kernels K((11, x22) = л(x; 222), such as Gaussian kernel and Laplacian kernel (Schölkopf & Smola, 2002).
h(x:) (1 (px))) ~ (wc, =(x)))
where the mhite-dimensional approximated vector
z 2(x) (v p/uu))((x un b1), Vı(ua)ó(æ, u. ba))
Online kernel learning trains classifiers h,.... .r hr IH from streaming sample Sy ((x1, y1),... (#r, vr))
We update the classifier according to Fourier online gradient descent (Lu et al., 2016) follows:
The code available at g thub. com hamm/Wllee httm//elxxing/ggppe
ut w - 7. (le
(2)
2

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
where 7y is the stepsize and loss function
Definition 3.1. We define Kernel Ortho-Mapping (KOM)
discrepancy between K.U4 and K: over sample Sn
4(W;-1) (W) vi) + 2 w |
É(S,, KLl, (C miin UEl,
{| K
K
p/Va]
This work focuses on random Fourier feature technique over shift-invariant kernels, and it is natural to make similar approximation and online algorithm for other kernels such as polynomial kernel (Pennington et al., 2015) and linear kernel (Wacker et al., 2024).
In this definition, the empirical kernel mapping is introduced to deal with different dimensionalities of kernel mappings as done by Schölkopf & Smola (2002) and Marukatat (2016), and the minimum is taken for the uniqueness of kemel mapping from rotational invariance.
We introduce some notations throughout this work. Bold uppercase and lowercase letters denote matrices and vectors, respectively. We denote by || ||p the Ep ---norm of a vector, and || || and -I Il. denote the Frobenius norm and nuclear norm of a matrix, respectively. Denote by ||- |ls the Hilbert- Schmidt norm of an operator, which an extension of the Frobenius norm in Hilbert space. Let (w,)==1 be the x n concatenation matrix of vectors "1.-.. Un E Rd
Lemma 3.2. We have the closed-form solution for the KOM discrepancy (in Definition 3.1) )
& (Sn, x(91)
= (T+(K!") + K(l)//n 2/| KIll KRIlI 1/2
Let Ig be d x identity matrix, and diag(v) is diagonal matrix with diagonal elements v. Denote by La and Oa d-dimensional vectors with all-one and all-zero elements, respectively. Let Let (1,, Σ) be a Gaussian distribution with parameters fe and Σ. Let Uu = {U E Rdxd, UUT = Ia} be the set of d xx orthogonal matrices, and v V is the square root of eestiiie-emmddefiitee matrix A, i.e. VAVA A.
The detailed proof is given in Appendix A. and the basic idea is to take the polar decomposition and upper bound the trace of an orthogonal matrix over Un.
For loss function (h, (xx y)) max(0, y)h(2)) we define the optimal kernel classifiers over sample S, in the old and new feature spaces follows:
Ih arg min M
E(h()) (xr, y.))
A (1 Inm. (3) + 2
3. On the Exploration of Feature Relationship
In this section, we introduce a general framework on the characterization of relationship between different feature spaces based on kernel functions, while previous studies can be viewed as some special selections of different kernels (Hou al., 2017; 2021; Zhou al., 2024). We further correlate it with the distance between classifiers trained from different feature spaces and then develop the one-pass learning algorithm for optimization.
where A = 1 and k = 2 correspond to the old and new fea- ture spaces, respectively. We measure the gap between two optimal classifiers 1:.") and h!?) over sample Sp, as follows:
1 Σ
n (a..3)
(4)
We now present the first main result to correlate our KOM discrepancy with two optimal classifiers as follows:
3.1. Charactering Relationship between Feature Spaces
Theorem 3.3. Given sample Sn, we have
Our basic idea is to map the original raw feature spaces into Reproducing Kernel Hilbert Spaces (RKHSs) with kernel functions, which could provide plentiful and implicit non- linear representations for original feature spaces.
Ps. (N!! (NPP) S FE(S,, (ct,,,,))ee)) (2rE(S ( K141, ((1,,))))
for two kernels KCM)) and KC bounded by r2, where X is the regularization parameter in Eqn. (3).
We focus on positive-definite kernel functions AC(A] and KC12] over old feature space 2 and new feature space x121,
respectively. For S, = {(x])) xx] ),,........... (a% (?))) with at
In this theorem, we upper bound the distance between two optimal classifiers with our KOM discrepancy, and this may shed some new insights to develop feature evolvable learning algorithms based on our KOM discrepancy, which essentially measures the relationships between two different feature spaces. The detailed proof of Theorem 3.3 given in Appendix A.2, which linearizes the kernel classifiers via empirical kernel mapping and constructs KOM discrepancy.
[1] x²11 and x; x12), we define their Gram matrices
K(A = Kg14 (ar [4]
16 a
for 4: = 1,2.
nxn
For K(1I and xCP) we introduce a new distance to measure the difference between two feature spaces as follows.
3

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
Dataset reuters
Dataset pol
Dataset splice
Dataset german
Dilfernnce Pr.
Diffcrunce Ps.
Difference ps:
KBM Sueepes datans Algrean
Difference Ps.
KCM Eurpewo
0.5
05
Alguaea
KOM diserepancy
1.13
1.2
KOM discropancy 8
0.07
.5
Number of instances
1.5%
2.36
Ak
6k Number of instances
Figure 2. Illustrations of the relationship between & and Ps...
Figure 3. An illustration of the difference between two optimal classifiers on two feature spaces, by optimizing KOM discrepancy and previous kernel alignment and & distance, respectively.
Theorem 3.3 is limited to binary classification, while it is casy to make a similar analysis for multi-class learning (Crammer& & Singer, 2002) and regression (Murphy, 2012).
Lemma 3.5. For two normalized kernel matrices KD1 and K with || |K[ F S r2, we have
Figure 2 presents intuitive illustration on the relationship between KOM discrepancy E(S,,AA()) k((2) and classifiers' difference ~s. (M!") I) via Gaussian kernels over datasets pol and reuters. As can see, Ps.. (hi.) /0_2)) is positively relevant to KOM discrepancy E(S, (,)),, i.e., the bigger the KOM discrepancy (S,,,, KII,, ACte)), the larger the distance Ps., with our Theorem 3.3 empirically.
E(S,, (PP)) S 1/21 A(K)),(())
The l2 distance has also been used align the features of two kernel mappings (Romero et al., 2015: Heo et al., 2019), which solves finiteddimensional kernel mapping "o from the following optimization problem:
This is nicely in accordance
Our KOM discrepancy is defined over the sample S, in Definition 3. We can also define the KOM discrepancy w.r.t. distribution D over x111 x x as follows
Golll arg E
Σ
(x!!") - ( (ao 112
Here, function space F C (4pl2) Rdd + Ruiim (p }. and rلlll is the cnite-dimensional mapping of kernel K(ll.
E(D,K!"",,
= =min UEll
ED [I (xll)( (
The & distance has been successfully applied for feature evolvable learning. For example, Hou et al. (2017; 2022) selected linear kernels K(l) and KcP), while Chen & Liu (2024) considered Gaussian kernel AC11] and Mahalanobis kernel X.P), We can also present the following relationship between the KOM discrepancy and lz distance, and the detailed proof is given in Appendix A.5.
where L/ is unitary operator set on a real Hilbert space. We present the following convergence analysis.
Theorem 3.4. Let KDA and K be two kernels bounded by r For 8 E (0, 1) and for some constant eı > O, we have, with probability at least 1 - ô over sample Sn
Lemma 3.6. For kernel KLL with mapping sol1,, we have
((S,, E(D, K(D x(PP||
sarv (c,,))))))
1 2 In 8
(8(Sm,,(.,, k(e1)) < 1 (m.!")
n
The detailed proof is presented in Appendix A.3, in which the main techniques include McDiarmid's inequality (Mc- Diarmid al., 1989) and operator Khintchine's inequality in non-commutative probability (Vershynin, 2018).
where kernel K(t2 [2] (21))) ((p (xx (2) 22 (2))
(z+
Figure 3 presents an illustration of the difference between two optimal classifiers over two feature spaces by optimiz- ing our KOM discrepancy, previous Eg distance and kernel alignment, respectively. Here, we focus on simple linear mapping spaces on two datasets splice and german, and the trends are similar for other datasets.
Relevant to previous relationship characterizations
Kernel alignment has been used to characterize relationship between two kernels (Cristianini et al., 2001; Cortes et al., 2012; Zhou et al., 2024), which essentially calculates the cosine similarity between two Gram matrices K(A)] and K
From Figure 3, it is observable that we could get smaller difference between two optimal classifiers by optimizing the KOM discrepancy, rather than kernel alignment and l distance. Therefore, our KOM discrepancy presents a better characterization of relationships between different feature spaces via kernel functions, and this is partially consistent with Lemma 3.5 and Lemma 3.6.
Tr(K K(2I)
A(K( k(2)
|
|F
We could present the following relationship between our KOM discrepancy and kernel aligmment, and the detailed proof is given in Appendix A.4.

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
Algorithm 1 One-pass optimization of Eqn. (6)
1-th round (1 Ti + 1), we update M and w(0) w.r.t.
Input: Streaming sample s/c number of iterations TMs,
instances 2.4 and x;; respectively, as
Output: Spectral density pl7 (Txx)
and stepsize TJM
kd
(t) = mil
(t-1) + +pl1 (u ) 21
(7)
1: Initialize M(T)) = 0, v (Ti) 0 and p' 1/d2
(I) =
u (1-1) + (Ø 121)
(8)
tk
2: for lo Ti + 1, ... Ti + To do
(1) with 0. ó(x;" .uj"
.641) and o ca ,
3: Update M and v(t)) according to Eqns. (7)-(8)
4: end for
We finally take the mirror descent method (Bubeck, 2015; Hazan et al., 2016) to solve Eqn. (6).
5: fo 1, Tas do
6: Calculate q (l-11) exp(- (
7: Update pl)) // /////::
Algorithm presents the details of our proposed method, and we have the convergence analysis as follows.
8: end for
9: return: Spectral density p! (Tx)
Theorem 3.7. For Algorithm 1, have
Tx
3.2. One-Pass Optimization for our KOM discrepancy
- -(p') S 0
1 TM
-
VTM
During the evolving stage, we reach a streaming sample S/. ( +1 +1:+++1117 .1+1).. (= (*f+I,, - +1++,,) and get the kernel 1c(2 learned from the previous stage. Motivated
by setting stepsize qM O(VIndd2/ d2/TTs), where f(-) is defined by Eqn. (6) and p" E arg minpes f(p).
by Theorem 3.3, we learn the kernel KC2l by minimizing the
The detailed proof is given in Appendix B, which presents an operation to preserve convexity and then derives the convergence analysis of mirror descent on a simplex.
KOM discrepancy as follows
min
((S)) 1CP), k(R1) K
(5)
4. The OPFES Approach
For steaming sample s/gl it is not allowed to store kernel Gram matrices in memory, and we can not directly optimize the above optimization as in (Cortes et al., 2012; Liu, 2024).
This section presents the one-pass optimization for feature evolvable learning in the current stage as shown in Figure 1. Our idea is to incorporate feature and label information from previous relationships and stages, and reuse prior models, rather than re-training a new model from scratch.
We present one-pass optimization for Eqn. (5) via random Fourier features. The basic idea is to transform the original optimization into a convex problem on a simplex, and then solve it w.r.t. streaming data S For the spectral density (u) ),.. ppl) (x)))
i) Incorporation of feature information via kernel (C(2
[2] )) of K(2l, approximate
Notice that the kernel K(P] is learned by minimizing the KOM discrepancy in Section 3. We could train an online kernel model based on x((2,, which incorporate implicitly some information from old feature space.
the KOM discrepancy by random Fourier features as
((S(e) T. Ac(U,,c()
(Tr(Kl4)) + (p. v) - M||Mdiag( (aadiag((/))ll//// /D)ll
Specifically, we reach example (ze we) in the t-th round for Tj + Te + < t < T; + Te + T2, and learn an online model h, (xxl2) based on kernel Kd2l as follows
where M (onulddxdd and (w1, 02 ... maa)) with
Ti+To Σ (u
TiT.. j 2 and Σ
[2] (az (2) = (un 1 (xx
i=f+1
=T++
where 2 (2 (6 (u 22l 2)22//22 u (22) ) 1
Here, 2! = d(x 11 ".""'""')) 2/ = o(x Pl u (
Here, take the representer theorem (Schölkopf & Smola, 2002) and random features approximation from Eqn. (1), We take online gradient descent with stepsize
and di and d2 are the numbers of random Fourier features of kernels K11ll and Kl21, respectively. From random features approximation, Eqn. (5) is essentially equivalent to
7! as
w [ = w
[2]
Tf [2] [3] u [2]
(9)
1 min f(p) (p.v) v) ||Mdiag (VD)). A
(6)
2
where the loss function e!! (w! is given by
where A- = {p: p 2 0. 0.11p11 = 13. For Eqn. (6), we
initialize M (T.) = [0]a, xd, and (T.) Odg, and in the
max {0. 1 - (w 2 (x
22 }زز +
|
2
5

---

We begin with the upper bounds for prediction difference between wh and wi++ via our KOM discrepancy, and One-Pass Feature Evolvable Learning with Theoretical Guarantees
ii) Incorporation of label information via ideal kernel
Algorithm 2 The OPFES method
Input: Feature evolvable stream sample Sr, +r,+T,+1 kernel K stepsize [i] [2] and r/. sensitivity parameter Initialize: w/)" =
For label information, exploit the ideal kernel from kernel selections (Cristianini et al., 2001; Kwok et al., 2003). Essentially, the ideal kerne is helpful to learn models with correct predictions for training data (Cristianini et al., 2001). We define the ideal kernel K over feature space X121 as
Output: classifier +T.+T.++T
Obtain random Fourier features (ul .0 ) and [2] 21
(ug .b 2 6)) via Eqn. (1)
[] 1C" ( D ) = yoy for i,j E (Ti + +1. Te).
2: for t = 1, 1.... Ti do
Update wi by online gradient descent in Eqn. (2) 4: end for
[1]
We can not obtain the ideal kernel matrix owing to streaming data. Our idea learn a new kemnel K' aligning with the ideal kernel K"* incorporate label information, i.c.,
5: Obtain p and p' from Algorithm 1 []
Compute w 4T. by Equ. (11)
K' arg min (
7: for 1. Ti + T. 1, Ti T. + T2 do
Update w and wo by Eqns. (9)-(10), respectively
Update the combined classifier h4 by Eqn. (12)
In the 1-th round, we learn a new online model by representer theorem and random features approximation again, i.e..
10: end for
11: return: classifier hy, +T,+T
(11z = (w), 2 (x?2))
where 22(x1=1) = ((r' 112 , (y )= with the density p' of kernel KC. Given stepsize T/. we update
in the current stage, respectively. From (Hou al., 2021), we combine two models, for t Ti + Te + 1,
w = w/11 V (wo
(10)
hx(x)²)) we (w [2] 2122 =0=1(x=!)) (
+ (1 - wi) x² (s! (
(12)
where the loss function ((0(11) is given by
where wi relevant to sensitivity parameter y > 0, i.e.,
max (0, 1 ye (e z (ar ((( })}
X 2
1
w
Wi yel 2l (mo
iii) Previous model reuse
W1-16
(1 wt- 1) Te (w!)
We exploit some good model initializations in the current stage, rather than re-training from scratch. Our basic idea is to obtain a new model on the space spanned by 2=² which takes similar predictions with the previous model.
Algorithm 2 presents the detailed description of our OPFES approach, which goes through all instances only once with- out storing the entire or partial training data, while previous methods require storing the entire dataset or partial dataset (Orabona al., 2008; Jin al., 2010; Hou et al., 2021; 2022; He et al., 2021a; Wu al., 2023).
Specifically, we consider the model for the new feature space via orthogonal transformation
[2] w TT+T_ = U. U.W
(11)
Theoretical guarantee
where U. is in the set of
argmin Ueua,
{ (1)ttt))
(x
12
the detailed proof presented in Appendix C.2.
Lemma 4.2. For bounded kernels, we have, for previous [2]
In the following, we present an effective solution for U., and the detailed proof given in Appendix C.I.
[1] model w and reused model w WT TT. from Eqn. (11),
Proposition 4.1. We have U, = VWT for the optimal solution in Eqn. (11), where V and W are left and right sin- gular vectors of +T) / (M]) in Algorithm 1.
1 Ti Σ
(w 2 (1!
12]
2 (x)
(2)
(wT
T, 1=
S < K( x(Hl /X,
Based previous analysis, we should learn and update two online kernel models !0!2) and wi from Eqns. (9) and (10)
where is the regularization parameter in Eqn. (3).
6

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
Table 1. Details of datasets
Dataset
Inst.
Feat.
Dataset
Inst.
Feat.
Dataset
# Inst.
Feat.
Dataset
Inst.
Feat.
Dataset
Inst.
Feat.
jungle
2351
87
svmguide1
7089
4
elevators
16599
nomao
34465
118
higgs
98049
28
splice
3175
60
usps
9298
25
magic
19020
10
adult
48842
108
miniboone
130064
50
bioresponse
3751
1776
aileron
13750
40
letter
20000
acoustic
78823
50
ijenn1
141691
22
christine
5418
1636
pol
15000
44
house
22784
16
runwalk
88588
6
covtype
581012
54
Denote by the optimal model in the current stage
where 11-1 is the indicator function, which returns 1 if the argument is true, and O otherwise.
[2] w0 E
arg min c (L)(
T: Tr +72
Σ
p (w)
T2 +1+++
Theorem 4.4 shows that the cumulative error rate of our OPFES method converges the minimum of the cumulative loss of two classifiers. The detailed proof is presented in Appendix C.4, and the basic idea is to construct a potential function and apply Hoeffding's 's lemma (Hoeffding, 1963).
and the cumulative loss
T++Ta+T Σ
C T2 t=Ti +T++1
dl2 (10 )
= max f0, 1 y/ (w, z (xx ())}} + 1//2. with e!2 (w) (w)
5. Empirical Study
be a streaming sample drawn i.i.d from a distribution. For Algorithm 2, we have Theorem 4.3. For kernels K(dl and K( with bound r2, and for 8 E (0, 1). the following holds with probability at least 1 - 8 over sample ST,
Let ST. { (cx
[o y1) 1))
We conduct experiments on 20 datasets?, and the details are summarized in Table 1. Most of the datasets have been well-studied for previous feature evolvable learning, and all features have been scaled to [0. 1j. We compare our OPFES with tate-offthh--a methods on feature evolvable learning.
align-FESL: Feature evolvable method of random features and kernel alignment for feature and label relationships (Sinha & Duchi, 2016).
1/2
-
(20
12))
4r²
3 V
v Xv
+
r
r
c222
(
1
1
6
1/2
rff-ROGD: Feature evolvable method of random features and Eg distance for feature relationships (Lu et al., 2016);
+ AvT2
|Ti
+
VT.
VT2
where& E = E X(1,,,,, and co > 0 is some constant.
rff-FESL: Online ensemble of rff-ROGD and random feature models learned from scratch (Hou et al., 2021);
Theorem 4.3 gives the convergence analysis for Algorithm We obtain tighter bound as for smaller KOM discrepancy, i.e., closer relationship between old and new feature spaces. It is also useful to exploit information and model from old
ker-ROGD: Feature evolvable method with kernel model and l2 distance for feature relationships (Hou et al., 2021);
ker-FESL: Online ensemble of ker-NOGD and kernel models learned from scratch (Hou et al., 2021);
feature space theoretically, because of tighter bounds as
for larger Ti and T'.. The detailed proof' is given in Ap- pendix C.3, which is motivated from regret analysis (Hazan et al., 2016), generalization bounds via Rademacher com-
lin-ROGD: Feature evolvable method with linear models and lg distance for feature relationships (Hou et al., 2017);
plexity (Bartlett Mendelson, 2002), some online-to-batch conversion techniques Biesa-Biannch et al., 2004).
lin-FESL: Online ensemble of lin-ROGD and a linear model learned from scratch (Hou al., 2017);
Denote by the cumulative loss for w'
OCDS: Capricious streaming method with a linear model via generative graphical model (He et al., 2021b).
c = T2
1 1 Σ
T ((w)),
T To
with (((w) = m0 1, - ve (w, z' (xt))} + Al| |||w0|//2 We also analyze the cumulative error rate for Algorithm 2.
For each dataset, we randomly split the feature space into old feature space x111] and new feature space x with almost equal number of features, following (Gu et al., 2022; Ni et al., 2024). We set T. = 1000 for datasets with a size larger than 10000; otherwise, set T. as 10% of the dataset's size. We also set Ti and T2 as half of the amount of dataset
Theorem 4.4. For kernels xC22 and 1C! with bound 2² and
for parameter y v 2 + 3r /2), we have
T T+TT
Lyrhe (z) (2)) < 0]
Σ
< min { (C)) 2,, }+
2 In
T2
To
Dowwloadedd from OpenMI. and UCT datasets repository
+1+
7

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
Table 2. Cumulative error rate (CER) evaluation of our OPFES and compared methods (tean=tstd), e/o indicates that our OPFES is significantly better/worse than the corresponding algorithms (pairwise t-tests at 95% significance level).
Dataset
Our OPFES
dign--FEL.
rff-FESL
ift-ROGD
ker-FESL.
ker ker-ROGD
lin-
lin- In-ROGD
OCDS
jungle
.0097 = 0017 .099 = .0288
.0161 + 0035 0246 + .0699
.276
.055
.0299
0061 .1044
01152
.1411
01:44
.1106
.0138
splice
30700 + .0799 .3126 + .0136
.3244 + .0877 3662 + .2155 .4122
.1600
.4240
.0188 .347 + .0097 .,307
.0213
.3547
.0156
bioresponse
.7633 = .0177 .2921 + .006.
.3051 + .013 .4285 + .0122 3690
.0096
.4544
:: .0116 .2938 + .0093+
.3684
.0102
.2951
.01122
christine
3192 + .095 .3205
+ .0000
.3316 + .1080 .3503 + .0022
.3858
.00%6
.4506
+ 00117 .343 + .0098
.3439
+ .0088
.3663 + .01 16
svmguide1
.1611 = 0052
.1617
= .0066
.1632 + .005 .2295 + _0107 .1900
= .0061
.2116 = .0500
.2399 + .0062-
.2151
= .0102
.2112 =: .0070
usps
.1684 = 0044 .1875
4: .0073*
.1658 +. .0051
.2184 + .0061 .2267
.00844
.2857
1: .0033
.2654
.0081
.2839
.0033+
.2746
.0085.
alleron
19663 0034 .2144
+ .0081 .2139 + 0059
.2344 + .0088
.2531
.0076
.2523
+ 00766 .2466
.0066*
.2465
00666
.3026
.0047
pol
.0654 0036 .0092
.0044
.068661
+ .00200 .8007 + .0025 .08655
.0025
.0956
.0034
.1484
.0035+
.1655
.0041
.1515
.0038
elevators
2/22 0039
.2119
= .0088
.2167
= 0037
.2119 + .01000 .263
.0012-
.3003
.051 .3033
0013
.3045
10:10
.3073
.00:12
magic
.154 # 0039
.2206
+ .009.
.2121
+ .0:6
.2434 + .0000
.2666
.0033
.3119
+ .0074 .2533
.00000
.2988
.0073
.2554
.0045
letter
.1354 + .0033
.1568
+ .0086
.1557 + 0037
.2311 + .0666 .3139
.0600
.3373
+ .0076 .380
.0038
.3565 + .0071
.3300 + .0034
house
1819 = 00-10
.1927
+ 00030 1191 + 00 .2001 + .0930
.2598
= _0110. .2577 + .0113 2222
+ 00000
.2588 = .0120
.2853 = .0037
nomao
.8466 = 0026
.0680
+ .0024 .0788 + 00170 .0845 # .0041 .1302
= .003+
.1355 + 0002 .880
+ 0019
.1107
= .0039
.0882 + .0023+
adult
.1875 = 0023
.1912
+ .0027 .1906 + 00000 .1932 = .0029
.2277
= .0019
.2218
+ .0031 .2050
.0033
.2036
.0012
.2303
.0026.
acoustic
.3074
.0244
.5227
# .0036 .2967 +: .0040005.....
.2977
+ .00430
.4168
.0073*
.4107
.0072
.4321
.0079
.4317
.0075
.4666
.0022
runwalk
2602 0033
.2890
= .0055
.2578 + 00166
.3496
+ .1.00
.3558
.0021
.4355
0061
.4445
0021
.4963
0003*
.4972
.0027
higgs
.9946 = .0015
.4135
+ .001 .3803 + 40044 .3507
+ .00000
.4377
= .0054
.4570 + .0055
.4309 + .0028
.4481
.0139
.4366
.0021
miniboone
.1002 = 0036
.2801 = .001 .1729 + .029 .1603 + .0029
.2488
.0017
.2181 = 0017
.2381 1 .009.
.2381 = .039
.2803
.0011
ijenn1
.6166 = .0110.111...
.0746
+ .0088
.0673
+: 00080
.0747
:: .0083*
.0957
= .0009
.0957
+: .009
.0951 +: 0007
.0957
= .0009
.0957
+ .0009
covtype
.3822 + .0088 .3813
+ .025. .3783
+ .0000
.3795
+ .00.2. .4095
= .0025
.4093
+ 0025
.790
+ 0007
.390
+ 00044
.3722
.0007
Win/Tie/lLoss
15/5/0
14/3/3
17/1/2
20/0/00
20/0/0
20/0/00
20/0/0
20/0/0
size subtracting T.. For ker-ROGD and ker-FESL, we set the buffer size to 10% of dataset size and consider reservoir sampling as done by Hou et al. (2021).
Table 3. Ablation studies for OPFES method (mean=std): (i) OPFES without KOM discrepancy; (ii) OPFES without ideal kerne; (ii) OPFES without initialization from previous model.
For rff- rff-ROGID rff- FFS-,,,,, align-FESI. and our OPFES, we fix the dimensionality of random Fourier feature as 1000. In
Datasets
OPFES
(i)
(ii)
Pol
.054
.0036
.1290 + .001
.6644
.009
.1418 = .0072
House
.1819
00333
.1966
00022
.1957 1 0004
2250
00133+
the previous stage, we employ Gaussian kernels with widths in 2 26:6) for all methods. For OPFES, we set TM 1000 of the optimal stepsize from Theorem 3.7. The stepsize T is constrained within 10 -0:2- /Vi, and the regularization parameter X is selected from 10 10:1]_ For OCDS, a and , are chosen form 101-3:0] by cross validations.
Noman
.6466
.0026
.0333 + 0028
.0750 + .0447
.1875 + 00050.
Adult
.1873 = .0123
.0133 : .0035* .1988 : .0033 .2133 = 00061
Our OPFES achieves better and comparable performance in contrast to rff- Fff-FESL, except for datasets acoustic, runwalk, and higgs. This is partially because of the class-imbalance problem on the three datasets, which results in the hardness of learning ideal kernel KC for label information and the degrade of learning performance of base learners w'.
The performance of the compared methods is evaluated by 50 times each dataset with random partitions and random ordering in the previous, evolving and current stages, where the cumulative error rate (CER) is obtained by averaging over these 50 runs, as summarized in Table 2.
Table 3 presents the ablation study of OPFES to verify the effectiveness of KOM discrepancy, ideal kernel and initializations from previous models. Due to pages limit, we consider four datasets Pol, House, Nomao and Adult, while the trends are similar for other datasets. It is clear that the performance of our OPFES will decrease drastically without the consideration of KOM discrepancy and good initializations. Ideal kernel takes limited improvement from label correlation, in particularly for dataset Pol, where K( possibly takes comparable performance to K:!
is observable that, from Table 2, our OPFES method takes significantly better performance than three linear methods lin-ROGD, lin-FESL, and OCDS, since these methods rely on simple linear classifiers and lg distance to characterize feature relationships. Our OPFES outperforms ker- NOr-ROGD, ker-FESL, rOf- most times because of exploration on feature relationships via our KOM discrepancy, while other methods fix Gaussian or Mahalanobis kernels.
Our OPFES is also better than align-FESL, since the KOM discrepancy is more effective in capturing some feature relationships than kernel alignment, shown in Lemma 3.5.
Figure 4 presents the convergence analysis of cumulative error rate for our OPFES. It evident that our OPFES takes faster convergence than other methods in the current stage,
8

---

One-Pass Feature Evolvable Learning with Thcoretical Guarantees
Our OPFES
algi-FFSL.
IE-ROIG
risFESL
ler-ROGD
ka--FSSL
*
li-RDDD
lin-FESL.
OCDS
bioresponse
usps
ailcron
pol
.29
CER
CER
39
21
0.3k
0.0k
0.9K
1.3k
0.9k
188
2.7%
3,6k
1.4k
2.8%
4.2k
1.6k
1.3k
1
4.5%
6.0k
Namber of instances
Number of instances
Number of instances
Number of instances
magic
letter
house
nomao
A2
.2
.66
CER
32
22
201
.22
.18
100
9.
Number of instances
Number of instances
Number of instances
Number instances
Figure Cumulative error rate (CER) versus the number of instances in the current stage our OPFES and compared methods, The lower the curve, the faster the convergence.
jungle
splice
jungle
splice
0.10
0.45
0.15
0.36
CER
0.10
0.30
0.30
.2k
4k
66
8k
1k
2%k
4k
.kk
1k
1.5k
Skc
1k
1.5k
2k
Evolving stage longth adult
Evolving stage longth
Random feature dimensionality
Rondom fearure dimensionulity
acoustic
adult
acoustic
0.26
0.38
CER
0.20
0.22
0.34
0.19
0.31
0.18
0.30
0.18
0.29
1.5k
Evolving stage length
Evolving stage longth
Random feature dimensiomality
Random feature dimensionality
Figure 5. Cumulative error (CER) versus the length of evolv- ing stage for our OPFES.
Figure 6. Cumulative error rate (CER) versus the dimensionality of random Fourier features for our OPFES.
between two feature spaces via kernel functions, and then theoretically correlate it with optimal classifiers learned from different feature spaces. Based on this discrepancy, we develop one-pass algorithm for feature evolvable learning without storing the entire or partial training data. We verify the effectiveness of our porposed OPFES both theoretically and empirically. An interesting future work is to apply our KOM discrepancy to deep learning via neural tangent kernel, and exploit more effective tools to characterize the feature relationships for feature evolvable learning.
partially because our OPFES can exploit feature relation- ships between two feature spaces and label information. It is observable that our method obtains lower cumulative error rates in the beginning of the current stage, indicating the importance of good model initializations from the evolving stage, which is consistent with Theorem 4.3.
Figure 5 empirically illustrates the influences of the evolving stage length T. in Algorithm 2. is evident that larger Te could yield better performance, because of more available instances in training to capture feature relationships and label information, which is consistent with our theoretical analysis in Theorem 4.3. We finally present the influence of dimensionality of random Fourier features for our OPFES on datasets in Figure 6, and trends are similar on other datasets. It is clear that our OPFES obtains stable perfor- mance we set the dimensionality larger than 1000, while smaller dimensionality could yield heavy information loss.
A Acknowledgements
The authors want to thank the reviewers for their helpful comments and suggestions. This research was supported by National Key R&D Program of China (2021ZD01 (7720011802)) and NSFC (62376119).
Impact Statement
6. Conclusion
This paper presents work whose goal is to advance the field of Machine Learning especially Feature Evolvable Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
This work focuses on two fundamental problems on feature evolvable learning. We propose the Kernel Mapping (KOM) discrepancy to characterize intrinsic relationships

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
References
Hazan, E. al. Introduction online convex optimization. Foundations and Trends()) in Optimization, 2(3-4):157- 325, 2016.
Alpaydin, E. Machine Learning. MIT Press, 2021.
Banerjee, A., Guo, X., and Wang, H. On the optimality of conditional expectation as bregman predictor. IEEE Transactions on Information Theory, 510))2664-2669,
He, Y. Dong, J., Hou, B.-J., Wang, Y., and Wang, Online learning in variable feature spaces with mixed data, In Proceedings of IEEE International Conference on Data Mining, pp. 181-190, Auckland, New Zealand, 2021a.
2005.
Bartlett, P. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
He, Y., Wu, B., Wu, D., Beyazit, E., Chen, S., and Wu, X. Toward mining capricious data streams: A generative approach. IEEE Transactions on Neural Networks and Learning Systems, 32(3):222--12400 2021b
Beyazit, E.,, Alagurajah, J., and Wu, X. Online learning from data streams with varying feature spaces. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pp. 3232-3233322 Honolulu, HI, 2019.
Heo, B., Kim, J., Yun, S., Park, H., Kwak, N., and Choi, J. Y. A comprehensive overhaul of feature distillation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1921-1930, Seoul, Korea, 2019.
Bhatia, R. Matrix Analysis. Springer Science & Business Media, 2013.
Hoeffding, W. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301): 1963.
Boyd, S. and Vandenberghe, Convex Optimization. Cam- bridge University Press, 2004.
Bubeck, S. Convex optimization: Algorithms and complex- ity. Foundations and Trends()) in Machine Learning, 8: 231-357, 2015.
Hong, S. and Chae, J. Distributed online learning with multiple kemnlls. IEEE Transactions Neural Networks and Learning Systems, 34(3): 2021.
Cesa- Sia--Binchhi, N., Conconi, A., and Gentile, C. On the gen- eralization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 2009):2050-2077, 2004.
Hou, B.-J., Zhang, L., and Zhou, Z.-H. Learning with feature evolvable streams. In Advances Neural In- formation Processing Systems 30, pp. 1417-1427, Long Beach, CA. 2017.
Chen, and Liu, S. A novel learning method for feature evolvable streams. Evolving Systems, 15:1-19, 2024.
Hou, B.-J., Yan, Y.-H., Zhao, P., and Zhou, Z.HH. Storage fit learning with feature evolvable streams. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pp- 7729-7736, Virtual Event, 2021.
Cortes, C., Mohri, M., and Rostamizadeh, A. Algorithms for learning kernels based on centered alignment. Journal of Machine Learning Research, 13(1):795-88) 828. 2012.
Hou, B.-... Zhang, L.. and Zhou, Z.-H. Prediction with unpredictable feature evolution. IEEE Transactions on Neural Networks and Learning Systems, 33((0):5706- 5715, 2022.
Crammer, K. and Singer, Y. On the learnability and design of output codes for multiclass problems. Machine learning, 47:201-233 2002.
Cristianini, N., Kandola, J., Elisseeff, A., and Shawe-Taye Taylor, On kernel-target alignment. Advances in Neural Information Processing Systems 14, pp. 367-373, Van- couver, Canada, 2001.
Hou, C. and Zhou, Z.-H. One-pass learning with incre- mental and decremental features. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(11): 2776-2792, 2018
Dong, J., Cong, Y., Sun, G., Zhang, T., Tang, X., and Xu, X. Evolving metric learning for incremental and decremental features. IEEE Transactions on Circuits and Systems for Video Technology, 32(4):2200-2002, 2022.
Hou, C., Zeng. L.-L.,, and Hu, D. Safe classification with augmented features. IEEE Transactions Puttern Anal- ysis and Machine Intelligence, 41 41(9):2176-2192 2019.
Hou, C., Fan, R., Zeng, L.-L.,, and Hu, Adaptive fea- ture selection with augmented attributes. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 45 (8)99306-332) 2023.
Goodfellow, I., Bengio, Y., and Courville, A. Deep Learning. MIT Press, 2016.
Gu, S., Qian, Y., and Hou, C. Incremental feature spaces learning with label scarcity. ACM Transactions on Knowl- edge Discovery from Data, 16(6):1-22 2022.
Jin, R., Hoi, S. C., and Yang, Online multiple kernel learn- ing: Algorithms and mistake bounds. In Proceedings of
10

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
the 21 International Conference on Algorithmic Learn- ing Theory, pp- 11033900444 Canberra, Australia, 2010.
Schölkopf, B. and Smola, A. J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, 2002.
Kwok, T. et al. Learning with idcalized kernels. In Proceedings of the 20th International Conference on Ma- chine Learning. pp. 400-407, Washington, DC, 2003.
Schreckenberger, C., He, Y., Lüdtke, S., Bartelt, C.,, and Stuckenschmidt, H. Online random feature forests for learning in varying feature spaces. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, pp. Washington, DC, 2023.
Lian, H., Wu, D., Hou, B.-J., Wu, J., and He, Y. Online learning from evolving feature spaces with deep varia- tional models. IEFE Transactions on Knowledge and Data Engineering, 36(8):4144 4162, 2023.
Shalev-Shwartz, S. and Ben-David, S. Understanding Ma- chine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Liu, X. Incomplete multiple kernel alignment maximization for clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, (6(3):1412-1424, 2024.
Shen, Y., Chen, T., and Giannakis, G. B. Random feature- based online multi-kemel learning in environments with unknown dynamics. Journal of Machine Learning Re- search, 20(22): 2019.
Lu, J., Hoi, S. C., Wang, J., Zhao, P., and Liu, Z.-Y. Large scale online kernel learning. Journal of Machine Learning Research, 17(47):1-43) 2016.
Sinha, A. and Duchi, J. C. Learning kernels with random features. In Advances in Neural Information Processing Systems 29, pp. 1298-1306, Barcelona, Spain, 2016.
Marukatat, S. Kernel matrix decomposition via empirical kernel map. Pattern Recognition Letters, 77:50-57, 2016.
McDiarmid, C. et al. On the method of bounded differences. Surveys Combinatorics, 141(():148-115) 188, 1989.
Valiant, L. G. A theory of the learnable. Communications of the ACM, 27(11):1134-112, 1984.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of Machine Learning. MIT Press, 2018.
Vershynin, R. High-dimensional Probability: An Intro- duction with Applications in Data Science. Cambridge University Press, 2018.
Murphy, K. P. Machine Learning: A Probabilistic Perspec- five. MIT Press, 2012.
Wacker, J., Kanagawa, M., and Filippone, M. Improved ran- dom features for dot product kernels. Journal of Machine Learning Research, 25(235):1-75, 2024.
Ni, H., Gu, S., Fan, R., and Hou, C. Feature incremental learning with causality. Pattern Recognition, 146:1 10033, 2024.
Watson, G. A. Characterization of subdifferential of some matrix norms. Linear Algebra Appl, 170(1):33 1992.
Orabona, F. Keshet, J., and Caputo, B. The projectron: A bounded bessed perceptron. In Proceedings of the 25th International Conference on Machine Learning. pp. 720-727, Helsinki, Finland, 2008
Wu, D., Zhuo, S., Wang, Y., Chen, Z., and He, Y. Online sepi-super learning with mix-typed streaming fea- tures. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, pp. 4720 4728, Washington, DC, 2023.
Pennington, J., Yu, F. X. X., and Kumar, S. Spherical random features for polynomial kernels. In Advances in Neural Information Processing systems 28, pp. 1846- 1854, Montreal, Canada, 2015.
Zhang, Q., Zhang, P., Long, G., Ding, W., Zhang, C., and Wu, X. Online learning from trapezoidal data streams. IEEE Transactions on Knowledge and Data Engineering, 28( 28010))2709-2223.99 2016.
Rahimi, A. and Recht, B. Random features for scale kernel machines. Advances in Neural Information Pro- cessing Systems 20, pp. 1177-1184, Vancouver, Canada, 2007.
Zhang. Z.- Zhao, P., Jiang, Y., and Zhou, Z.-H. Learn- ing with feature and distribution evolvable streams. In Proceedings of the 37th International Conference Ma- chine Learning, pp. 11317-1 1327, Virtual Event, 2020.
Romero, A., Ballas, N., Kahou, S. E., Chassang, A., Gatta, C., and Bengio, Y. Fitnets: Hints for thin deep nets. In Proceedings of 3rd International Conference on Learning Representations, pp. 1-14, San Diego, 2012015.
Zhou, Z. Shen, Y., Shao, S., Gong, L., and Lin, S. Rethink- ing centered kernel alignment in knowledge distillation. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, pp. 5680-5688 Jeju, South Korea, 2024.
Sajedi, R. and Razzazi, M. Data stream classification in dy- namic feature space using feature mapping. The Journal of Supercomputing, 1049):2003-12061 2024.

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
A. Proofs for Kernel Ortho-Mapping Discrepancy
A.1. Proof of Lemma 3.2
For Frobenius norm and orthogonal matrix U E Un, we have
| VK
Tr (VKIJ K(2) ( (VKIJ v Kil)
Tr(K(4)+ Tr(K( 2 (U VKII
(13)
The minimization of Kernel Ortho-Mapping (KOM) (in Definition 3.1) is equivalent to the following optimization:
Tr (UT VKK VKK))
max UEM
(14)
Denote by VK K! and X = x V VKKK 2 K There exists V E Un such that X V(X|,
which is a polar decomposition of X. We then have
Tr (UT (UT KUTKKPWKK
Tr (U Tr (U'V
Denote by W = U V. We take the eigen-decomposition | = PDP for orthogonal P and diagonal matrix D with non-negative elements from the semi-positive definiteness of | From the cyclic invariance of matrix trace, we have
Tr
U K k")) Tr (WPDPT) Tr (DPTWP) WP)
Denote by W = PP another unitary matrix in Un. The optimization problem in Eqn. (14) can solved by
T DD.WA W.. = Tr(D).
{ Tr [W))=
max Eld,
max W EUA.
where the last equality holds from W = I,. From nuclear norm and matrix trace of positive semi-definite matrix, we have
Tr(D) Ir (VVKKKKIKK kK = Σ V os (KIKK/KKKK = Σ (o(KK//KB = ||| V
which completes the proof by combining with Eqn. (13).
A.2. Proof for Theorem 3.3.
We begin with the empirical feature mapping follows:
Lemma A.1. Let K be the Gram matrix w.E.t. kernel K. and sample S = {x1, Enh, and consider eigen decomposition
K = SDST, For kernel classifier h((x) = Σi=ı azKl(a,,, æ²), we have
h(x,) = (w.SVDS ei)
with = SVDS T Σ ajes
where e; denotes unit vector of the i-th element being 1.
Proof. From eigen decomposition K SDST we have
K(æ;, æ.) = Kij (SDS = (SVDS e, T SVDS e
and this gives one data-dependent feature mapping of XC as & x + SVDST e, (Schölkopf & Smola, 2002). For kernel classifier h(x:) Σラ= ( we have
x2
n
h(w:)) Σ ansK(2,, m0))
SSVDS T
a an SVDS Te) (W,SVDSTT) ei), j=1
which completes the proof.
12

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
Proof of Theorem 3.3. From Lemma A.I, the kernel learning problem in Eqn. (3) be equivalently linearized as
[k] w
E arg min wik EIR
R (wolt))
+ 11 || for k 1,2,
(15)
where
R R (w (
Σ max 0, - y/ (wolt), (z. }}}
and cplit are the empirical kernel mappings of k(k,,, For two classifiers and from strong convexity of Eqn. (15), we have
2
12 (w! !
[]]
(20!)
(21)
2
w0
+
+
2 w.
w0
w.
2
2
[2]
R (w!2) (2))
[2
A (w0! !
w
+
+
w.
w
w
2
2
2
2
This holds that, from 1-I --psehhitz continuous hinge loss and Canchy-Schwarz inequality.
[1]
[2]
(10 P1) nele (w) )) + (1 ne (xo!"))
W. wt
l (ww! (x!"" e ((w!!) (2) )) y/
1
(w!
( (0) )). )).
((w!") ابيي )), v/
nd
i=1
w.
[i]
+
w
22
6 (z:"") ( - (2)
(16)
nd
For //ob 1|2 + |1w0 1|,, we have the following constraints on w [s]
from the KKT condition of Eqn. (15)
wh!l
[k]
ge ga E m {0.1 ys w0. (ax ) E [nd] for k == 1,2,
nX
where A()) is the sub-gradient operator. We can upper bound || + 11 S 2r/A from
[k] w.
- Di
O max {o, - ys ( (nn (a) 1 }}}}}
0i (ox, (1))
||2
max
g:
nd
2
(2. 1|2- We observe that empirical kernel mapping is unitarily invariant in Lemma A.1, i.e., we have (p(x;) ()(x,) (U<(zz)) (U)((z;)) for U e U4 and i, [n]]. and the i-th column of U K is also a legal empirical kernel mapping of each æ. This follows that, for KOM discrepancy,
remains to bound Σi
||4ا (co!
2
Σ (x(
||,
n min U,,U,
[| -V VKeUU, V
from the unitary invariance of Frobenius norm. From Eqn. (16), have
[1]
2
2r (Sn, KC k(2l)
w
w.
<
X2
13

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
and we bound the difference between two optimal classifiers
1 (x) ) 11 (cc:")
wo!"! و (a!!"))
w!! (ac
(w!l) (2.
(w..) (2ll (a: (a!")) + { (w. (( (2o. ,3 (c, (a.?))
(ac
| | wh! + !0
الاه (a! (xx 1
2
X 2r At4, + A (xx)"))
from equivalent linearization of kernel classifier and bounded norm for optimal classifier. We finally have
Ps. (no ,
x v 2T1, ((T)) + nd
(x:"))
( (2)
x ((Ss,, v /r2E(S,, K111, K(11,K111) K(e1)
which completes the proof.
A.3. Proof of Theorem 3.4
We begin with some useful lemmas as follows:
Lemma A.2. For a distribution D X11 x 2212, we have
S(D,K(0,,xe))
min Uell V Ep [|| [1pl")))1))) - (212))
Eo (2 ]1l. 1/2
(Ed (2 xl1 + x (- x(اا)
Proof. For Hilbert-Schmidt norm, we have
Ep (c.1)) - (20
2
HS
ED | x (1) + x- (x 12] _e(2)
2ED
1 2 (x) Up
= Ep ((lll (x!!)) ال"')) + 22] 12| x
2Ep Tr (pl [2] (x 2) Up!"))]
Ep (-""1 ( + (* x111
T
(EED
where the last inequality holds from the linearity of operator trace w.r.t expectation, and independence between U and D. We complete the proof from the similar derivations as in the proof of Lemma 3.2.
Lemma A.3 (Perturbation bound for singular values (Bhatia, 2013)). For n x n real matrices A and B, we have
(. o, < -A-BI.
where o, (A) and or (B) are their respective i-th singular values, i.e., 01 (A 2 ... (A) and 0 (B) 2 ... on (B). Lemma A.4 (McDiarmid's inequality (McDiarmid al., 1989)). Let X1, X2, Xn, be independent random variables taking values in set A, and f A + R satisfies
sup Xa. XeA
N2, .n) f(X2,X2,.". ,X,-1, X141, Sa
14

---

One-Pass Feature Evolvable Learning with Thcoretical Guarantees
for every E [n]. Then, for > have
2t
Pr[f(X1, Xz, X,) El X Xn.) f) & exp
Lemma A.5. Les K1 and x(2) be two kernels bounded by r². For samples S {(x xz! )
(ah x!²)) and
St S. M.a( _ } u {(*k) _ ( (I E [n]). we have
KII
KP -
|
KP
S 2r
where K[4 and K Gram malrices w.r. kernel K. over Sn and Sn respectively, and define K22 and K similarly.
Proof. From Lemma A.3, we have
Km
K
K
K
22
KL
K
K
21/
K
KIN
K
| K
K
o
KII
aos( K(2I
Kuy KRII
Σ oe(
Kul K()
oo(V K [1) (1))
min
oil (
KII
K
C.V
KBy
KRI)
( KRI)
oz K
K
KRM)
U.Velln
min Ueu,
{ll
VKll
UVK!)!
VKl |1. |
min Vel,,
- VKHL]]}
(17)
We now prove that there is an Ú E Un such that the difference between VK and ÜVK!) lies only in the k-th column. Denote by [ÜVK[]] I i.e., the k-th column of ÚvK(" The existence of Ü Un is equivalent solving the following underdetermined system of n equations with variables
[1]
I (2)()
v. (v K(1),)
for i [n]][(}}
(18)
[x (z+ 1|
1/2
From the full-rank Gram matrix K there exists a solution vo for the system in Eqn. (18) because of equations with variables. By setting do. we have an Ü Un such that the difference between v KlJJ and U K[] lies only in the k-th column. This follows that, from the nuclear norm of the rank-1 matrix,
- -VVK") / /
< [[[[K""]] -ÜV
[V KP] || S 27
min UEU
This completes the proof from Eqn. (17) and similar analysis for minvez,, |l (V VVKe l...
Lemma A.6 NNommcommueetive Khintchine inequality, (Vershynin, 2018)), For independent Rademacher random variables "1,t"* Enn and for real matrices XI,..., .x. of the same size, have
E
x
S C' max
C'ax
Xxx
Σ
X x
for some positive constant C.
Lemma A.7. For independent Rademacher random variables E1, .. En and for real matrices XI, ... ", of the same size with E| [||]=] < 20, we have
E
> x,
E
2E
Σ xX
15

---

2 6 One-Pass Feature Evolvable Learning with Theoretical Guarantees
Proof. Let {Xi,... inequality, have
X
denote an independent copy of the sequence (X1,-
X From i.idd assumption and Jensen's
E X X X.,
[x.])
X
E
Xi])
E3'
X
X
X1, X.
X1, X
XI. X
X
Xn
]1
E X
Σ (X; - E(X.)) - - (Xx))(X))
E X.
Σ (:
-x,)
X1. X.,
We also have, from the triangle inequality of nuclear norm and symmetry of Rademacher random variables,
[1
Σ
X
x3)
Σ
E (
X()
X X
X
X
Xn
X
X
1=1
1=1
S
E X1
Σ xxX;
Σ e; X
Σ x
X
X
X
X
X
which completes the proof.
Proof of Theorem 3.4. By triangle inequality, we have
E(Sn, x(P))) E(D, E(D,K!l) 1x111,1,1111 .c.2i)
s S(Sn,,ll) ((ll) Es, [(S K1, K2)) + Ess ((Sm, K1,,, E(D, -
(19)
Concentration analysis
Random analysis
For sample S with the k-th instance replaced by (ar [11r oxkk / from Sn, we have
(E(S,, KC11,
xx211) xcT1,,
s A (KII |,) (a a((") - xa!" ,.ll + (a xe)
(x a mP s 6r
from bounded kernel and Lemma A.5. Based on the McDiarmid's inequality (Lemma A.4), the following holds with probability at least 1 1-6 ō,
E(Sn, (il,,,R - Ess, [(S,,, x111,, x(R))] s 3r
2 In n
(20)
For the second term in Eqn. (19), consider the random matrix analysis with nuclear norm (Vershynin, 2018). Denote by and operator X; = (4p 1l (ax) (an $//n, and we have
[ (x.l))) (2))
Es.
Tr(K]))) ED[ [k) [|])]] for ke [2]
This follows that, from the linearity of expectation and Lemma A.3,
(11,,, Es. K11, K(1 x((e))
2 Es..
Σ 12 (2c
| ||,
< 2Es,
n Σ
الll (ac! (z
(ze
!
4E
Σ xX
16

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
where "1,"1 6n are independent Rademacher random variables. From X;
(vpl1((a))
(a:
! )pp
21 (sc. $)/n, we have
(a.
[1] , x ) sp
(x)) ) 2 (x. ) )T (x)
/p(2
T o
(x) )p
11)
(x)
+
X,X,
n²
This follows that, by the sub-additivity square root w.r.t nuclear norm and some algebraic calculations,
X
(a x!!")
v022(x (z)
2
1 v2
Σ $ 22 (-!
V ②
y2
n
vn
71
where we use
V ④
1|. =
|8
Ep
( 11
(zx (z) ||. s Ep
(()))
sm²
and
n (2!
Σ d (x) (0
rr
Σ ulll (
(x)
"1)]"
S V
S Svr?
and, from linearity of expectation and relationship between nuclear norm and operator norm for rank-1 operator,
JCI (o!") ) ( (o))
r
Σ (x (a
(
S Vnr².
Similarly, we can present the same upper bounds for Σm= X, X, This follows that, from Lemmas A.6 and A.7,
1 + v2
E(D,K Es..
sc
nn +
r.
(21)
We complete the proof from Eqns. (20) and (21), and triangle inequality.
A.4. Proof of Lemma 3.5
From (Bhatia, 2013), we have IIVA- VB S VIA
A
B Bl.., and this follows that, for KOM discrepancy,
K(,,, <
Kt
KL2
1 | -K
We further have, for normalized kernel matrices,
KII- KPllI_ V
KII
KPI/
KiLl|
K ||
| ||F
|
||
2 (T(KK()1)
KP [
) S 5r A(K!), K()))
+
n
|
|K]]
|
|
which completes the proof.
17

---

One-Pass Feature Evolvable Learning with Thcoretical Guarantees
A.5. Proof of Lemma 3.6 Denote by dim( for simplicity. For sample Sn {x ,nn. we write ( i=1
P
(p 12 (12
and p (a!1)( " i=1
and we also have their respective Gram matrices K T plu and K(2 p
piel, remains prove
min UEu
{
||=] - -
p1)
If d, then there exists matrix
E Un from Lemma A.1 and the unitary invariance of Frobenius norm, such that
p
P
pllv - pl v
p
K
We also have
p p12
min Well,
{|l
VKKWW
VKL
F
for some W Un with VK W = -PI.T. V.
If n > d, then we have, similarly to the proof of Theorem A.2,
|
1(2
min WElda
{||P |
w - p12]T
|,} Tr(K(ll) + Tr(K))) -2 P
and this follows that, from the unitary invariance of the nuclear norm,
U p
|[000
p!l
p12 Onx(n-a) = VKK])K =||vK[iVkP|].
0 (n-d)xn
We finally have, from Lemma 3.2,
w W (E(S), ((l,,,,((,,,x(11)) - Σ و (z! (1 2 }
min
Weld
which completes the proof.
B. Proof of Theorem 3.7
We begin with two useful lemmas as follows:
Lemma B.1. The sub- gradiend of fp) in Eqn. (6) is given by
v - diag(N (M' T UVTT/
where and are left and right singular vectors matrices of Mdiag( /D).
Proof. We set X = M. with the singular value decomposition X = =UEV. Following (Watson, 1992), the sub-gradien
of |X] is given by
X||. = {UVT + W/W e Rdixd, U WV = 0, || =
Obviously, T is sub-gradient by taking W 0, and we have
0| O|
0x
adiag(
= (MTTMUUVT/VL
0p
0x
Odiag(
Op
which completes the proof.
18

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
This proposition shows that singular value decomposition is required compute the sub-gradient of f(()) in each iteration, which is computationally expensive. However, Mdiag( has low rank structure with the rank no more than min(Te, d d2} because evolving stage T. is usually small compared to dj and de in our setting. This could drastically reduce the computational cost on singular value decomposition.
Proof of Theorem 3.7. From Eqn. (6), we have
1 with s(p, W)
1 Tr (Ru)) 2
((p) = min Welfr,
{g(p, W)}
V VK
o 2l (p) (
2
where KD] = E
[1] 1. J.b/ /d T.XT. and o = 1 xd2- Hence, f(p) a convex function w.r.t. p from the convexity of minwerr, g(p, W) in (Boyd & Vandenberghe, 2004).
In Algorithm 1, we select
d2
hp)) = Σ
Ps (l - 1),
and we have the corresponding Bregman divergence
(x(pl = h(p) h(g) - (Vh()).))) - ②) for P.qEA.
From the Fenchel conjugate, we also have
h 00) = sup {0t p h(pp} and (0) = arg max (0 hpp)) PER
2
and define Dr- (p)lg) = ht" (p) h" hr(g)) - (Vh" q) similarly. In Algorithm 1, we rewrite mirror descent iteration as
0 = Vi- (Vi(p(t-11) - Th (1 with g (t-1) E (((((-))))
Let p' E arg milppe f(p) and 0 = Vh(p"). For Bregman divergence (Banerjee et al., 2005), we have
Dp- (1-(0 = Dn- (0(t0 + (g - - (vh-(0 vi-(0))) + Dn- ((())))))))))
and
(0( - - (7 -hh(00)) (o) = (1 (p(t-1)- p²)
For convex f and g (1-1) E ()((((-1)), we have s(x(1)) [(x)) S (T(()) - -p*). and
T-- -(p(-\)-((p"))
- f(p"))] < Dr. Dn. (oi--)1))))
D..((1') 11) Dn- (0(0-)))10(0))
Summing from = to Tm, we have
Tmm
1 Tm
Σ Te -(p)) s Dr. (0(")()))))
Σ t=1
(10 11 In d2 +
Σ
Te
2
0
(22)
2
[=1
where the norm - || is defined on h² and D₁. (0)) D (p (1)pp)))
For each t e [Tm]. we project Pt onto P = {p E A: || 2 e) for a small e > 0. We consider the singular value decomposition Mdiag( / p()) U. and denote by u. = U.,... This follows that
|uelooo
max (MU.) < max :E|da]
(12) < ST.de
sElds
from Lemma B.1 and orthogonality of V. Hence, we have, from the conjugation between & and for norm,
1 s Te
1 + vdz
< |001/00
(23)
19

---

One-Pass Feature Evolvable Learning with Theoretical Guarantees
and this follows that, from Eqns. (22)-(23) and by selecting stepsize Tt
T
1 Σ (1 ((p")
In d2 TTm m
The
(
v 12
v
1
2
This completes the proof by setting V 21nd2/ (ImFol1 + vd2/c)).
C. Analysis for OPFES
C.1. Proof of Proposition 4.1
Let dj and d2 be the dimensionalities of random features of KC! and IC?,, respectively. Denote by
z
[6] To (2,+1) E R.X. and z (21++))mm E Rdxx..
[k] To
For di 2 d2, we can rewrite the optimization for Eqn. (11) as
U E arg min U
{
Uz z
F
where Ud, xd, (U E Redadd;; UUT have an equivalent optimization as
Idg] is the set of semi-orthogonal matrices. From the proof of Lemma 3.2, we
{ (UM (UM (T)) diag( vp(TT))
max Uellaxxdt xd;
Let (Ti diag( vlT)))) VEW be the singular value decomposition with left and right singular vector matrices
V E Udgxd, and W E Udg. respectively. Denote by S = UV, and have, from cyclic invariance of matrix trace,
{ (T:(UVWT)}- max
max UEllaxxa;
Tr
SEllaz
We get the maximum when S = Idz and the optimal solution set for U is given by
U. E (WV + QV- Q E Rd xd2
(24)
For dj < d2, we have the equivalent optimization of Eqn. (11) as
U E arg min UT elaaxxa
{
UZ z 5
}
We also take the singular value decomposition of ( Te) Ta diag( / /p Tar)) with V E Ud, and WT E Ud, xd2, respectively.
For = T UUV E Rdd xd, we similarly have the optimal solution set for as
U. E WVT + (1 wWT Q Q 1Rd
(25)
From Eqns. (24) and (25), = WVT is always an optimal solution for Eqn. (11) by setting Q = 0.
C.2. Proof of Lemma 4.2
For E T + 1,7 + Tel, we have, by simple calculations and Cauchy-Schwarz Schwarz inequality,
(w (1) z (z. {w ( = =1 )
= [ب x = )) - ( U.. 20! 2 (zx
< K (w z!'l (ac!"") - U. (200) <
1o اi || (,0
U. -==121 U.
(x)) [2) 111
20

---

One-Pass Feature Evolvable Learning with Thcoretical Guarantees
This follows that, by summing from T1 + to 71 Te.
| Ti+To
1 To
(wo, x (x)
(w +T.
(c0 -
Σ U.z2"(a!")) - x 2101(x!
To
i=i++
V2 min Uellax44
{|u. (2"((())))) TitI.
Titte | 1r V2E(5 Kl //121)/
=
AvTe
T1+
where the second inequality holds from Lemma C.5 and Cauchy-Schwarr Schwarz inequality, and the equality holds from the unitary invariance of Frobenius norm.
C.3. Proof of Theorem 4.3
We first introduce some useful lemmas.
Lemma C.1 (Hoeffding's ss bounds (Hoeffding, 1963)), Let X2, ,x,, be independent random variables in [a, b), and
X E X1/n. For t O, we have
1 exp (- (b-a)²
2nt2
Lemma C.2 (Generalization bound of kernel methods (Mohri et al., 2018)), Given S= i.i.d from the distribution 'D Let K : X X - R be kernel bounded by r2, and 4p(:) is the feature mapping of K. and let H = (x + (w, ((x)) ||w lla A} for some A 2 O. For loss function [e(w, (x,2)) S M and ö E (0, 1), the following holds with probability at least 8 for h E H.
".....,x,,, (Zn. 9n33 drawn
T
1
R(h)= S R2(h) + 2 ( V + +M
2n In
8
where R(h) ((a.y))D((((u (x. y)) and (s(h)= -i fww, (x,, y1 //n
Lemma C.3 (Online to batch conversion (Cesa-Biance et al., 2004)). Let ST drawn i..dd from D, l a loss bounded by M and hi.... ht the sequence of hypotheses generated by an online algorithm. For 8 E (0, 1), the following holds with probability least 1 - 5,
yr)} y be sample
(e T Σ he( We ]
2n (1/5)
E
S
Σ ((h((1e). My
(X) be a sample and B be a closed convex set with projection lI arg eB || w'll ||. For strongly convex loss function E with bounded gradient w.E.t w, i.e., || W l(w, (Iu, y.)) s G for w E B and t E (T). For the update rule w.
Lemma C.4. Let ST (xx1)));;
Ve(we, (xt, y1 (t)))/X Xt) with wo, un E B, we have
1 T
1 T
G2 G1+
Σ (wi, (Ze, v:))
Σ 1=1
Elw, (zI, <
T
2XT
Proof. Denote by V. V Vwl(wi, (Ie, v1)) for simplicity. For X- >-strnggyy convex functions, we have
|| - 2 <
|lar; - w/|2 - -2 (ve, w. w) + V.l
|wm - w0|2 - 2 E(we, (x)) l(w. (xt, vc)) + =2 1110 - -0)1= + + + Vell
x (1 \rt))lux w1 27: (f(wr, v:), - l(w, (Ir, v()) + + Vel12.
This follows that
tr --- |w: w/l2
1
|| w|| G.
(ww,, v1)) E(w, (2.,
27.
21

---

One-Pass Feature Evolvable Learning with Thcoretical Guarantees
We have, by summing = to T, and setting Tı 1/(1 with 1/70- O.
2 (e(wr, (Zt, t=1
ve)) (i)) [(w, (It, v())
wi w|l
1 1 T5
- 2) G
Σ [=1
G
T
G² A
(1+ITT)
TC-1
At
t=1
t=1
which completes the proof.
Lemma C.S. Let ST {(a11 u1) )...... (arT.y7) (r)] } be a sample. For kernel function K(xx, x) S r², we have classifiers
"., , generated by online kernel learning with (b) max 1 V;h((x;), 03 / /2. We have
1
((K)))
Σ T
1 T
((h)) 4r² (1+ In
T
XT
where he arg min 1E E (T)
Proof. By setting Tr = 1/(At) and ho = O, we rewrite the update rule as
(1 (1- h dt
h4
with gt [[ych((x)) < 1ly))((x.)
(26)
where (p(x;) is the feature mapping of K. Hence, we have
and | s x g
h4
from 1/j) = i/t for -
- 1. We complete the proof from Eqn. (26) and Lemma C.4.
From Lemma C.5, we have the following corollary.
Corollary C.6. For online kernel learning the previous stage (Figure 1), we have
r X
and
1 T
Σ
[I]
Lemma C.7. Civen Sn {<x ya),... (XT, )r and for kernel K. bounded by x2 and classifier ho E H. let by, ... .Irr be classifiers generated by online kernel learning with l(b, (1,,( (x. max yy(((x)) 0} + A|ll|///2 and O. For h4 arg men E (h). we have
1 Σ
2r I/o hall
(bb)
((hh))
<
T
T
VT
Proof. For the norm in RKHS, we have
[he+1 h. 11 |t, - vl(e))))) n111 = 11ke - n..1 + 2 -2 (he- - h.),
and this follows that, from convex loss function (h(e)) (h.)). S Vl((he) T (h+ hw).
- (h |1,, h 11he11 h1 + [ve((h))1
2n
We have, by summing from = to 1
11:0 - hr 12
Σ (ee(he) (bhh)))
+ 2nr
21
which completes the proof by setting 7) Iih 1..1l / (rVT).
22

---

One-Pass Feature Evolvable Learning with Thcoretical Guarantees
Lemma C.8. Given samples $
(1)) and S
{3 3/ 1 with ||al|2 S v, denote by
1
fl
{ (w v:)) + A ||
un
E
arg min wER*
R1(w))
n1
n1 H2z
W2
E
arg min
Ry(w)= =
Σ
((w, (2i vi)) + 2
|
WERd
122
i=
For ô E (0, 1), the following holds with probability at least --
p²
1
1
(w(w)) R2(20))
-
+
In
121
n2
Proof. We introduce a new function
52) R1 (wft) R2(w05))
and consider the sample S1 = S1 M((x un)) U (2kk ve for ls [m1]. From Cauchy-Schward inequality and I-Lipschitz hinge loss, we have
(2) - f(S1, S2)1 [w (w+t) S r [| w A [w w
10f112-112 + - S 2r || ww'll2 1l
where the norm of optimal classifiers satisfy
2r
[ 112 S K.
||00" ll2 S
and ||w + w0' ll2
X
from the KKT condition as in the proof of Theorem 3.3. From strong convexity, we have
(w 2 (wj) + A
1 wf and ((w Ri (2w(") ) + A 2 ||1b - -
(27)
and this follows that,
| - wor' worf S
1 (10f") - (w]) R2' (wi) + ii's (wott)
1 (((ww( (xx, vk)) - ((wi, (Ix, vb)) + f(wi, (2'2 vk6) Muwit (2 (2k.v/))) s __
| wo/1/2
= Ani
An
Hence, we have, from Eqn. (27),
2,2
[S -(S
An
We could make a similar analysis for S2. This completes the proof from Lemma A.4.
Proof of Theorem 4.3. For and 2, we introduce some notations as follows:
Ro, (k)
Σ
T
((
[k]
[H] (2r yc)) +
À
w
[k]
Ti
2
2
Ti+T.
2
Ro. (w)(k))
Σ
[w (xc .v:)) +
[k]
w
T-
2
2
t=
RTy (k)
2:
T+T
((w (ar [M] y.))
x
1
2
+
T
13. From the i.i.d assumption, it is natural to consider samples on new feature space x22) in the previous stage and on old feature space 2 in the current stages respectively.
Denote by (+) = (
| (zt
yr)) + A|| w [4|
23

---

One-Pass Feature Evolvable Learning with Thcoretical Guarantees
We have, from Lemma C.5 and strong convexity,
cP.
[2) (nw!")
) 2r
2
[TT
A
Ti+
2
-Rey (uo
(28)
X72
and we also have Rry (win
RTg (10
21 + Zz + Z3 + 24 + 75 + Zo + 27, where
71 RT, (1.,,
Rt. (101)+
[2]
Zz Rr. tir.
Rr. (wo Zz Rr. (ur (21)
Rr, (wo)i)
T
71
Z4 = Rr; (un)tt)
Zs = T ((( - (w0 Zs - Ro, (wo/1)) Ros (w)
Ti
Z7 Roy (uo/
Riy
(wr) 12
From the iid assumption for evolving and current stage, the following holds with probability at least 1 - 8/6,
Z1 < E[Z1]
+
max (all), ()Ex)))))))))))1 (e xy
{e
{e(
(w (2]
TT (2x (aall,.))
..))
2T
1
2T:
In
8
6
(
In 6
(29)
2T.
272
from Lemma C.1 and Corollary C.6. Similarly, the following holds with the probability as least 5/6,
Z3 S E Z[Z]]
+
max x))xxy
{e
[2] (11 (ao (..,.))))
In(1/52)
(
12
+1) +
In(1/82)
(30)
(an
2T.
2Tg
From Lemma 4.2 and Theorem 3.4, the following holds with the probability at least 8/6,
1 T.+T.
L (w [I] (z. (xx"".1) .2)) 6 [w]++I. (of vr)
Ze
Te
1 T.+T.
(w x 20x (w (TT, x x121(z²,21)
Te t=+
r r K(1,,, ((21
S (CD, + car 1 6 8 Te
<
In
(31)
From Lemma C.3, the following holds with the probability at least 8/6.
22 In(6/8)
24 S
( +1)
V
(32)
2T,
and we have, from Lemma C.5,
2 1n(1 + +Ti
4
Zs <
(33)
X
AvTi
From Lemma C.8, the following holds with a probability least 1
8/6,
?
6
Zo <
In
(34)
A
Ti
Tz
8
24

---

One-Pass Feature Evolvable Learning with Thcoretical Guarantees
From Theorem 3.3 and Theorem 3.4, the following holds with a probability least 1 8/6,
Ti T++..
+T2
Z7
T2 +
1
(2 Timi
12]
(2 - (w 2. |
+
A
2
T2"
T
T2+
2
[3]
+
21 T2
2
À
T E(S Ty
K3011 ((1)), + r
X
2r KIl1, 12211
+r
T
22
T E(S
(111) + X V 2r 255
2r
A
P2
r 8 D k , + 2 2r (D, Kll x(l), +0
(D
In(6/6)
(35)
T2
From Eqns. (29)-(35) and union bounds, the following holds with probability at least
5,
[2] (rr(w RT, (w)
22
x² A
6
E +
23
(36)
T
for some constant c with (1 - 8/6)0 2 8. We complete the proof by combining Eqn. (28) and Eqn. (36).
C.4. Proof of Theorem 4.4
For simplicity, we reindex the time-step of samples in the current stage as t= 1, TT. Denote by l,, the loss for the i-th base learner the 1-th iteration with [2). and Li, is the corresponding cumulative loss. We define the potential function
Φ = In Σ exp( -ras)
and this follows that, from - < - x x2 and In(1 + +x) S
8. - ----1= 1 exp(-7f1,))
)
) ?
Σ
w exp( (771a)
7 2 exp( -
i==
(1 74,, + +z2(,,)
In
1 1- (wo, Li) + Σ weshih S (wo, Re) + 72 Σ Cr..G.
7
where wi (W W1,2), l, (f,,1 (,22,, and the last equality holds from Eqn. (12). We have, by summing over t [T2].
T2 Σ
T2
(er L.) 5 4o DT, +
Wr, 1,1
1=1
1=1
1=1
1n2 1 In (exp(_>LT,,.e) + 7
ln2 Lrz + 7
We
Wr
7 7
7
t=1
1=1
1=1 i=1
where LT2 min;e(1.2) L. We have, by rearranging and from Theorem 4.3,
T2
1n2
- 1n2 + 7T2 1+
3r2
Wi (x) - min Cr2.a _
+
Cr
111
?
21
1=1
which completes the proof by setting 7 21n2/((1 (1++122223/)))))
25


Reviews:
[{"review_id": "TZJOLRBSB4", "reviewer": "Reviewer_UGGx", "summary": "This paper tackles the problem of feature evolvable learning in streaming data settings, where features may vanish and emerge over time—a scenario that arises in applications like sensor networks or dynamic monitoring systems. The authors propose a new metric, the Kernel Ortho-Mapping (KOM) discrepancy, which quantitatively characterizes the relationship between two evolving feature spaces via kernel functions.\n\nThey then develop a one-pass online learning algorithm, called OPFES, that:\n\nLeverages random Fourier features for efficient kernel approximation,\n\nIntegrates prior model knowledge via KOM-based mappings,\n\nReuses both feature and label relationships from the previous feature space without retaining training data.\n\nThe theoretical contributions include:\n\nA bound between KOM discrepancy and the difference in predictions from classifiers trained in two distinct feature spaces (Theorem 3.3),\n\nGeneralization error bounds (Theorem 4.3),\n\nRegret guarantees for their mirror descent-based optimization procedure (Theorem 3.7).\n\nEmpirically, OPFES consistently outperforms a suite of state-of-the-art methods across 20 real-world datasets, demonstrating both lower cumulative error rates and faster convergence.", "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": "", "claims_and_evidence": "The primary claims are:\n\nKOM discrepancy better captures relationships between evolving feature spaces than kernel alignment or ℓ₂-distance.\n\nOPFES achieves state-of-the-art performance in both accuracy and convergence speed.\n\nTheoretical convergence and regret bounds are valid under the assumed setting.\n\nEvidence:\n\nThe KOM discrepancy is supported by both a theoretical upper bound (Theorem 3.3) and empirical correlation analyses (Figures 2 and 3).\n\nExperimental results across 20 datasets (Table 2, Figures 4–5) substantiate the superior performance of OPFES.\n\nThe convergence of their optimization strategy is justified through mirror descent analysis (Theorem 3.7), and prediction deviation is bounded through KOM discrepancy (Lemma 4.2).\n\nEvaluation: Claims are well-supported with theoretical derivations and extensive experiments. There are no overtly problematic claims, though practical scenarios with high noise or extremely non-stationary distributions could be addressed more thoroughly.", "methods_and_evaluation_criteria": "The authors use appropriate methods:\n\nRandom Fourier Features for scalable kernel learning,\n\nKOM discrepancy for measuring evolution of feature spaces,\n\nMirror descent on the simplex for optimizing spectral density.\n\nEvaluation criteria—Cumulative Error Rate (CER) and convergence speed—are suitable for online learning benchmarks. The use of diverse datasets and baselines strengthens the empirical evaluation. Te-splitting strategy and buffering policies are transparent and consistent with prior work.", "theoretical_claims": "Several key theoretical results are presented:\n\nTheorem 3.3: Bounded classifier divergence via KOM discrepancy.\n\nTheorem 3.4: Generalization guarantee for empirical KOM discrepancy.\n\nLemma 3.5, 3.6: Relationship of KOM discrepancy with kernel alignment and ℓ₂-distance.\n\nTheorem 3.7: Mirror descent convergence rate for KOM optimization.\n\nTheorem 4.3: Generalization bound for OPFES.\n\nThese are grounded in solid theoretical tools—e.g., McDiarmid’s inequality, matrix norm inequalities, polar decomposition, and Rademacher complexity. The proofs (referenced in appendices) appear consistent and technically correct from inspection of their assumptions and derivations.\n\n\n\nTheorem 3.3: Bounded Classifier Divergence via KOM Discrepancy - The derivation is consistent with prior work on RKHS norm bounds and empirical classifier discrepancy measures.\n\nTheorem 3.4: Generalization of Empirical KOM Discrepancy  - The proof also incorporates non-commutative Khintchine-type inequalities, which are non-trivial but correctly referenced.\n\nLemma 3.5: KOM discrepancy is upper bounded by a function of 1 minus the kernel alignment. - Lemma 3.5 leverages normalized Gram matrices and a cosine similarity-based interpretation.\n\nLemma 3.6: KOM discrepancy is also upper bounded by the average ℓ₂ deviation between kernel mappings. - Lemma 3.6 mimics regularization path analyses and is essentially a generalization of kernel regression upper bounds.\n\n\nTheorem 4.3: Generalization Bound for OPFES\nClaim: Provides an excess risk bound for the OPFES predictor w.r.t. the optimal classifier in the current stage, incorporating the KOM discrepancy.\n\nValidation:\n\nCombines regret analysis (Hazan et al., 2016) with generalization error bounds using Rademacher complexity.\n\nProper use of online-to-batch conversion techniques is evident.\n\nThe bound reflects interplay between past information (via T1 ,Te ) and the KOM discrepancy, offering useful theoretical insights.", "experimental_designs_or_analyses": "The experiments are well-designed:\n\n20 datasets from OpenML/UCI.\n\nComparisons with 8 strong baselines (e.g., rff-FESL, align-FESL).\n\nMultiple performance metrics: CER, convergence speed, sensitivity to Fourier dimension.\n\nStatistical significance tests (t-tests) confirm robustness.\n\nThe setup (T1, Te, T2 split; kernel and hyperparameter tuning) is explicitly stated. However, more insight into variance across random splits or ablation of individual components (e.g., only using KOM without label alignment) could enhance the experimental depth.", "relation_to_broader_scientific_literature": "The paper builds on a rich literature in:\n\nOnline kernel learning (Lu et al., 2016; Shen et al., 2019),\n\nFeature evolvable streams (Hou et al., 2017; 2021; 2022),\n\nKernel alignment (Cristianini et al., 2001),\n\nℓ₂-mapping in transfer learning (Romero et al., 2015).\n\nIt adds a new formal metric (KOM) that generalizes and theoretically bounds earlier methods (alignment, ℓ₂-distance). The approach synthesizes kernel theory with online convex optimization, contributing novel algorithmic and theoretical insights.", "essential_references_not_discussed": "The paper is generally well-cited. However:\n\nIt omits Rahimi and Recht (2007), who formally introduced Random Fourier Features, although Bochner’s theorem is referenced.\n\nMore recent works on deep kernel transfer learning or meta-learning over kernel spaces could be relevant for contextual breadth, especially if extensions to deep networks are envisioned.\n\nIn the context of evolving data streams, work on concept drift detection (e.g., Gama et al., 2014) might be conceptually adjacent and worth mentioning.", "other_strengths_and_weaknesses": "Strong Theoretical Proofs - The integration of kernel theory, generalization analysis, and convex optimization underpins the theoretical soundness. Convergence, generalization, and transferability are all rigorously treated.\n\nEmpirical Breadth and Depth - Evaluation across 20 diverse datasets, paired with statistical testing and convergence analysis, validates the model’s robustness and practical effectiveness.\n\nInterpretability via Kernel Metrics-  KOM provides not just an operational tool but a theoretical lens for understanding how and why models transfer across evolving feature spaces.\n\nWeakness :\nNo Analysis for Adversarial or Disjoint Feature Evolutions - While the KOM discrepancy is effective under smooth transitions, its applicability under non-overlapping feature spaces or adversarial drift remains unexplored. For example, when new features are independent of the old, KOM may offer no meaningful signal, yet the algorithm is still applied.\n\nUnclear Role of Label-Based Ideal Kernel Under Imbalance- The paper proposes using an ideal kernel 𝐾∗(𝑥𝑖,𝑥𝑗)=𝑦𝑖𝑦𝑗    to align labels in the evolving stage. But, This approach assumes balanced label distributions, which do not hold for several datasets (e.g., acoustic, runwalk). The approach is sensitive to noisy or ambiguous labels, potentially destabilizing kernel alignment.\n\n\nScalability Beyond Fourier Features- While random Fourier features are scalable, they are limited for high-dimensional structured domains (e.g., graphs, sequences). Extension to non-stationary kernels or deep kernel surrogates is a natural direction not yet addressed. (Perhaps opened up for future direction)", "other_comments_or_suggestions": "The pseudocode could benefit from a clearer distinction between training phase and transfer phase. \nAppendix A, Lemma Proofs:\nThe paper shall consider including (in main or appendix) sensitivity plots for learning rate, gamma1, and gamma2. The Bayesian optimization results could be volatile depending on the dataset.", "questions_for_authors": "How does the OPFES framework behave in scenarios where the new feature space is statistically independent from the old one (i.e., KOM discrepancy is large or near-maximal)?\n\nGiven that the ideal label kernel 𝐾∗(𝑥𝑖,𝑥𝑗)=𝑦𝑖𝑦𝑗   assumes balanced and clean labels, how does your method adapt when labels are noisy or highly imbalanced (e.g., acoustic, runwalk datasets)?\n\nCan the authors provide ablation studies separating the contributions of (i) KOM discrepancy, (ii) label kernel alignment, and (iii) model reuse from previous stages?\n\nWhat is the runtime overhead (in wall-clock time and computational complexity) of the mirror descent procedure used to optimize KOM in comparison to other ensemble or retraining approaches?\n\nDoes your method generalize to non-shift-invariant kernels or structured inputs (e.g., graph, sequence kernels)?", "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": {"ethical_review_concerns": "Not applicable."}}, {"review_id": "l7j76sYuSg", "reviewer": "Reviewer_AX8j", "summary": "The paper focuses on \"feature evolvable learning\" -- a setting in which features are being learned during a data stream, with new features learnt over time. The goal is not to retrain the model from scratch but to transfer from an older feature space to a new feature space. Similar problems have been studied in the past in the context of online continual learning. \nThe paper proposes a new measure (KOM) to quantify/characterize differences between feature spaces -- using kernel functions. \nIt also proposes an algorithm called OPFES to learn features in this evolvable manner without storing all training data.", "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": "[Q1] One main weakness of the paper is that it does not leverage the power of deep learning … a follow-up work could consider the Neural Tangent Kernel framework that has been developed for the approximate analysis of neural networks…\n\n[A1] We will clarify that this work tries to answer two fundamental problems on feature evolvable learning following previous settings [Hou et al., 2021; Chen et al., 2024], and it is interesting to leverage the power of deep learning for further work, where we could incorporate deep learning technique via random features of Neural Tangent Kernel [Zandieh et al., 2021], and distinguish representations from two network structures [Kornblith et al., 2019].\n\n[Q2] One possible improvement, mostly in terms of presentation, is to somehow explain the insights and steps of the OPFES algorithm a bit more— maybe through a visual illustration.\n\n[A2] We will consider a visual flowchart to outline the main (previous, evolving, and current) stages of the OPFES algorithm and explain how feature information and label information are incorporated via our KOM discrepancy and how the model is updated in a one-pass manner using random Fourier features.\n\n[Q3] How does OPFES deal with partial feature overlap between the old and new feature spaces? For example, some features may persist while others disappear.\n\n[A3] We will clarify that this work focuses on the non-overlap between old and new feature spaces, following previous feature evolvable learning [Hou et al., 2017; Zhou et al., 2022], and it is interesting to consider some partial feature overlaps, for which we could learn two relevant models by exploiting correlation from two feature spaces as in [Hou et al., 2016; Ye et al., 2018; Gu et al., 2024].\n\nWe will add relevant references on online and unsupervised continual learning [Lange et al., 2021; Wickramasinghe et al., 2023; Wang et al., 2024].", "claims_and_evidence": "The main claim of the paper can be stated as: it is possible to do feature evolvable learning in a streaming manner (one-pass over the data)  using a new metric called Kernel OrthoMapping (KOM) discrepancy, which captures the relationship between old and new feature spaces.\n\nThe paper provides sufficient evidence for this claim, through theoretical results, algorithm development (OPFES) and several experimental results.", "methods_and_evaluation_criteria": "The paper is strong methodologically, using mathematical analysis when it is appropriate to do so, designing systematic experiments, and being thorough in how it states its claims.", "theoretical_claims": "In my opinion, the main theoretical results of the paper are:\n1) Theorem 3.3 giving an upper bound (in terms of KOM) for the differences between optimal classifiers trained on old vs new feature spaces\n2) Theorem 3.4, which gives a convergence result, showing how the empirical KOM discrepancy approximates its distributional counterpart.\n\nI admit that I have not checked the proofs of the theoretical claims -- as this was one of urgent reviews I had to provide.", "experimental_designs_or_analyses": "The paper is quite thorough and systematic in its experimental study. The main result in that portion of the paper is to show that the OPFES outperforms other feature evolvable learn methods (such as random fourier-based or kernel-based) on many different datasets.", "relation_to_broader_scientific_literature": "The paper also relates to the broader literature of learning theory as well as to continual learning.", "essential_references_not_discussed": "I think that the paper is missing some references from the continual learning literature -- in the context of deep learning. Some of those papers also consider this stream-based setup -- even though the do not use the term \"feature evolvable learning\". Instead they use terms such as \"online continual learning\" or \"unsupervised online continual learning\".", "other_strengths_and_weaknesses": "One main weakness of the paper is that it does not leverage the power of deep learning. As the authors also mention at the very end, a follow-up work could consider the Neural Tangent Kernel framework that has been developed for the approximate analysis of neural networks -- to examine how the KOM approach can be applied there.", "other_comments_or_suggestions": "One possible improvement, mostly in terms of presentation, is to somehow explain the insights and steps of the OPFES algorithm a bit  more -- maybe through a visual illustration.", "questions_for_authors": "how does OPFES deal with partial feature overlap between tthe old an new feature spaces? For example, some features may persist while others disappear?", "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": "oHO2t4CW6N", "reviewer": "Reviewer_XL9p", "summary": "This work proposes \"One-Pass Feature Evolvable Learning\" (i.e. OPFES), this is a method for handling streaming data where old features vanish and new features emerge. The core contribution is the kernel ortho-mapping discrepancy as $E\\left(S\\_n, K^{(1)}, K^{(2)}\\right)=\\min \\_{U \\in \\mathrm{U}\\_n} \\frac{1}{\\sqrt{n}}\\left\\\\|U \\sqrt{K^{(1)}}-\\sqrt{K^{(2)}}\\right\\\\|\\_F$, which quantifies the transformation between two feature spaces via kernel embeddings. Using this discrepancy, the OPFES adaptively learns a new feature space in a single pass without retaining past data, leveraging random Fourier feature approximations and mirror descent optimization. The authors establish regret bounds, proving that classifier discrepancy $\\rho\\left(h_*^{(1)}, h_*^{(2)}\\right)$ is upper-bounded by $O\\left(E\\left(S_n, K^{(1)}, K^{(2)}\\right) / \\lambda\\right)$. Empirically, OPFES outperforms kernel-alignment and $\\ell_2$-based baselines in binary classification tasks.", "questions": "", "limitations": "", "rating": 1, "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": "[Q1] The KOM discrepancy can be understood as a measure of the difference between two sets of kernel mappings…Orthogonal Procrustes Problem ... KOM is superior to kernel alignment and $\\ell_2$ distance…no real theoretical argument …\n\n[A1] We will clarify that the KOM discrepancy presents the first general framework to characterize correlations between two features spaces, and previous feature evolvable methods can be viewed as some special selections of different kernels [Hou et al. 2017, 2022; Chen&Liu 2024]. This discrepancy is motivated by orthogonal procrustes problem [Gover&Dijksterhuis 2004], which originated in matrix approximation problem in linear algebra, irrelevant to kernel functions.\n\nWe will also clarify that Lemma 3.6 verifies the superiority of our KOM discrepancy in contrast to $\\ell_2$ distance, and Lemma 3.5 presents the relationship between the KOM discrepancy and kernel alignment. Those theoretical results are verified empirically in Figure 3 and Table 2.\n\n[Q2] The min-max formulation over unitary transformations U… why enforce rotational constraints in the first place…affine transformations? nonlinear shifts...\n\n[A2] We will clarify that enforcing orthogonal rotations aims to guarantee closed-form solution for KOM discrepancy (Lemma 3.2) and Gram matrix w.r.t kernel functions in feature evolvable learning. Such formulation shows better characterizations between feature spaces than prior feature evolvable methods, and it is interesting to exploit other transformations.\n\n[Q3] …theorem 3.3 states that the difference between optimal classifiers in different feature spaces is upper-bounded by the KOM discrepancy…some bound on classifier discrepancy…seems loose...\n\n[A3] We will clarify that Theorem 3.3 presents the first theoretical result to correlate performance of classifiers with relationships (KOM discrepancy) between feature spaces, and we do not find tighter bounds before for feature evolvable learning. The proof includes linearization of kernel classifier via empirical kernel mapping, perturbation analysis of strongly convex loss and construction of KOM discrepancy. \n\n[Q4] …theoretical results in paper are only valid for a very narrow setting. A vast number of feature evolvable problems (…) are regression tasks…for other functions like cross-entropy or…\n\n[A4] We will clarify that our theoretical results focuses on binary classifications, since mostly feature evolvable learning considers classification tasks [Hou et al.,2017; Zhang et al., 2020; Hou et al., 2021; Lian et al., 2022; Schreckenberger et al., 2023]. Our results can be generalized to regression and multi-class tasks with other functions, by considering online gradient descent with random features for other functions and generalizing ideal kernel for regression and multiclass tasks as in [Wang et al., 2015].\n\n[Q5] Is that possible to extend OPFES to multiclass classification…non-SVM loss functions…\n[A5] We will clarify that our OPFES can be extended for multiclass classification by considering multiclass loss functions and ideal kernel as in [Wang et al., 2015]. We will also clarify that our KOM discrepancy is defined on Gram matrices of kernel functions, which can be used for non-SVM loss functions since it is irrelevant to loss functions and learning tasks.\n\n[Q6] …storing past data is infeasible, but many real-world applications do store partial data in buffers…why not allow a sliding window approach that keeps recent data…\n\n[A6] We will clarify that this work focuses on one-pass learning for large-scale data, which goes through all instances only once without storing training data as online learning [Crammer et al., 2005; Carvalho & Cohen, 2006; Cesa-Bianchi & Lugosi, 2006; Gao et al., 2013]. It is feasible to store partial data in buffers with some sliding window, which is called min-batch learning. Generally, min-batch learning requires more storage and computational costs than one-pass learning.\n\n[Q7] How does OPFES perform with different kernel choices…kernel width…In Figure 6 why is the CER not monotonically decreasing as…\n\n[A7] We will add a figure to show that OPFES achieves stable performance over a range of kernel widths in $[2^{-8}, 2^8]$. We will also clarify that, in Figure 6, most CERs are monotonically decreasing as the random Fourier feature dimensionality increases, except for four datasets, where the algorithm is slightly overfitting due to relatively fewer features and algorithmic randomness.\n\n[Q8] All results rely on shift-invariant kernels (like Gaussian, Laplacian)…a strong restriction as many real-world kernels (e.g., polynomial, string kernels, graph kernels)…\n\n[A8] We will clarify that this work focuses on the shift-invariant kernels such as Gaussian kernel, which has been commonly-used in online kernel learning [Kivinen et al., 2001; Orabona et al., 2008; Hong et al., 2023], and we make similar analysis for other kernels functions (polynomial and graph kernels) by random feature approximation.", "claims_and_evidence": "see Strengths And Weaknesses", "methods_and_evaluation_criteria": "see Strengths And Weaknesses", "theoretical_claims": "The proofs in this manuscript are somewhat sloppy. Despite spending considerable time analyzing them, I find it difficult to fully verify their correctness. The authors frequently provide detailed proofs for simple results while glossing over more complex derivations.", "experimental_designs_or_analyses": "The experiments (benchmarks, analysis, ...) make sense and be supportive to me.", "relation_to_broader_scientific_literature": "This work is a follow-up in the field spanned by e.g. [1-3]\n\n[1] Zhang et al., ICML 2020: “Learning with Feature and Distribution Evolvable Streams”​\n\n[2] Hou et al., AAAI 2021: “Storage Fit Learning with Feature Evolvable Streams”​\n\n[3] Schreckenberger et al., AAAI 2023: “Online Random Feature Forests for Learning in Varying Feature Spaces”", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "- The KOM discrepancy can be understood as a measure of the difference between two sets of kernel mappings (or Gram matrices). Conceptually, it is closely related to existing methods, such as the well-known Orthogonal Procrustes Problem. Therefore, it does not constitute a novel contribution. The paper claims that KOM is superior to kernel alignment and ell_2 distance, but the comparison is only empirical, there's no real theoretical argument showing why this discrepancy should be preferred.\n\n-  The min-max formulation over unitary transformations $U$ is mathematically elegant, but practically, why enforce rotational constraints in the first place? Many feature transformations in real-world apps are not merely orthogonal rotations. what about affine transformations? nonlinear shifts? Meanwhile the authors justify their empirical kernel mapping with methods from (Schölkopf & Smola 2002), but the assumption that two kernel feature spaces should be mapped in an orthogonal-preserving way is tenuous at best. Kernel alignment methods are widely used in community because they are more flexible, while kom enforces an artificial constraint that has no strong empirical motivation.\n\n\n- I also think the connection between KOM discrepancy and classifier performance is weak; theorem 3.3 states that the difference between optimal classifiers in different feature spaces is upper-bounded by the KOM discrepancy. However, this is trivial, as any well-defined measure of feature space similarity will yield some bound on classifier discrepancy. The actual bound itself seems loose, i.e. there’s no guarantee that minimizing KOM results in an `actually good' model.\n\n- Lastly, the theoretical results in paper are only valid for a very narrow setting. A vast number of feature evolvable problems (like in paper section 1) are regression tasks, yet the proposed algorithm is useless in these scenarios. And the vast majority of real-world scenarios where feature spaces change involve more than two classes. It’s also unclear if the results hold for other functions like cross-entropy or other margin-based losses e.g., logistic regression.", "other_comments_or_suggestions": "- line 667: shouldn't the $\\partial(\\cdot)$ represent subdifferentials? because the $\\boldsymbol{g}$ in your KKT condition belongs to a set\n\n- do your $c_1$, $c_2$ in Theorem A.4 share the same meaning as in Theorem 3.4, 4.3? similarly, the $c$ in Definition C.5, Lemma C.6, and proof of Lemma D.6\n\n- Theorem A.15, $\\lambda$ is the parameter from Eqn. (20)\n\n- proof of Lemma A.17, why we need the convexity of $H$? we could simply verify that $H(x)/x$ is a nondecreasing function when $x\\geq 0$\n\n- Lemma C.4 should be $\\hat{R}\\_1\\left(\\boldsymbol{w}\\_{1 *}\\right)-\\hat{R}\\_2\\left(\\boldsymbol{w}\\_{2 *}\\right)\\leq...$\n\n- line 1458, what is the definition of $m_1$?\n\n- line 1545: two empirical estimates", "questions_for_authors": "- Is that possible to extend OPFES to multiclass classification? is your KOM discrepancy even meaningful for non-SVM loss functions, like kernelized ridge?\n\n- You claim that storing past data is infeasible, but many real-world applications do store partial data in buffers. Could you comment on, why not allow a sliding window approach that keeps recent data, instead of forcing a single-pass update?\n\n\n- How does OPFES perform with different kernel choices, does it collapse if the kernel width is set incorrectly? In Figure 6 why is the CER not monotonically decreasing as the random Fourier feature dimensionality increases?\n\n- All results rely on shift-invariant kernels (like gaussian, laplacian), which is somehow a strong restriction as many real-world kernels (e.g., polynomial, string kernels, graph kernels) do not share that property. Could the key claims potentially extend to these settings, and if not, what is the difficulty?", "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": "3P4u4BIkKS", "reviewer": "Reviewer_WCDh", "summary": "This paper tackles online learning in feature-evolving streams where old features vanish and new ones emerge. They propose OPFES, a one-pass algorithm that processes data without storage. It combines online kernel learning with random Fourier features to adaptively capture evolving data patterns and introduces a kernel ortho-mapping discrepancy framework through kernel functions to quantify cross-feature space relationships. Theoretical analysis establishes a regret bound for the algorithm, while empirical evaluations compare cumulative error rates across methods. Experiments confirm OPFES' superior performance and efficiency in managing real-time feature evolution, offering both practical streaming solutions and theoretical guarantees for feature-evolvable learning 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": "[Q1] The scenario of the OPFES algorithm that can be applied is a little bit limited. The feature space can only change once during the whole learning process.\n\n[A1] We will clarify that this work focuses on one feature evolution as in [Hou et al., 2021], and we can consider multiple feature evolutions similarly, that is, we learn feature relationships one by one as for evolving feature space, and maintain a model for every feature space via online ensemble.\n\n[Q2] This article only considers hinge loss without analyzing other loss functions...What effect will it have on the theorems in this article if we substitute the loss function with MSE, logistic loss, or exponential loss …\n\n[A2] We will clarify that this work focuses on one-pass learning with hinge loss, motivated from [Shalev-Shwartz et al., 2011, Lu et al., 2016], and it is feasible to generalize to other convex and Lipschitz-continuous loss functions, such as MSE, logistic loss and exponential loss, in which we need to take different Lipschitz constant and Fourier online gradient descent w.r.t. other loss functions.\n\n[Q3] Are the methods in this paper applicable to general kernel functions? The methods in this paper are found on shift-invariant kernels. I'm especially interested in whether they can be applied to general kernels.\n\n[A3] We will clarify that this work considers the shift-invariant kernels such as Gaussian kernel, which has been commonly-used in online kernel learning [Kivinen et al., 2001; Orabona et al., 2008; Takizawa et al., 2019; Ghari et al., 2022], and it is interesting to generalize to other kernels by considering similar approximation with random feature techniques.", "claims_and_evidence": "The claims made in the submission are well-supported by both theoretical analysis and empirical results. The paper introduces the Kernel Ortho-Mapping (KOM) discrepancy to characterize relationships between different feature spaces and establishes theoretical guarantees linking KOM discrepancy to classifier performance. The proposed one-pass feature evolvable learning algorithm is backed by regret analysis and convergence proofs, ensuring a solid theoretical foundation. Additionally, the empirical validation includes extensive experiments on multiple datasets, demonstrating the effectiveness and efficiency of the proposed method compared to existing approaches.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are well-suited for feature evolvable learning. The Kernel Ortho-Mapping (KOM) discrepancy effectively characterizes relationships between evolving feature spaces, and the one-pass learning algorithm is efficient for streaming data. The evaluation uses diverse benchmark datasets and cumulative error rate (CER), ensuring relevance and comparability to prior work. Comparisons with state-of-the-art methods further validate the approach. Overall, the methodology and evaluation align well with the problem setting.", "theoretical_claims": "In the review process, I examined several key proofs in the paper to ensure their correctness. The proofs of Lemmas 3.2 and 3.5 are mathematically rigorous, leveraging properties of Frobenius norms and matrix decompositions effectively. The proof of Theorem 3.3 is sound, demonstrating the relationship between the KOM discrepancy and the gap between optimal classifiers, using empirical kernel mappings and linearization techniques.\n\nHowever, the proof of Theorem 3.4, which involves probabilistic bounds, requires careful consideration of concentration inequalities and random matrix theory. While the steps appear logical, the complexity of the proof necessitates a thorough verification of the application of McDiarmid's inequality and operator Khintchine's inequality to ensure the bounds are correctly derived. Overall, the proofs are generally well-structured, but the probabilistic aspects could benefit from additional clarity to fully confirm their correctness.", "experimental_designs_or_analyses": "The experimental design in the study is commendable for its thoroughness and rigor. The use of multiple datasets and comparison with leading methods effectively showcases the versatility and robustness of the OPFES approach. The random splitting of feature spaces and the integration of random Fourier features highlight a sophisticated strategy for managing dynamic feature sets.\n\nThe parameter choices, including the buffer size and step sizes, are judiciously selected to optimize performance and computational efficiency. The study's comprehensive evaluation and statistical analyses provide strong support for the validity and effectiveness of the OPFES method. The positive outcomes and clear methodologies contribute significantly to advancing the field, demonstrating a well-executed experimental design.", "relation_to_broader_scientific_literature": "The paper's key contributions are deeply intertwined with the broader scientific literature on feature evolvable learning, focusing on efficient adaptation to dynamic feature spaces in streaming data. By introducing the Kernel Ortho-Mapping (KOM) discrepancy, the study builds on prior work in kernel alignment and extends the understanding of feature relationships. The development of a one-pass algorithm aligns with the need for efficient online learning methods, leveraging random Fourier features for scalable kernel approximation. The approach integrates existing frameworks for adapting to evolving features, offering a theoretically grounded and practically applicable method that addresses the computational and adaptive challenges in dynamic feature spaces. The paper's contributions advance the field by providing a novel and comprehensive solution to the challenges of feature evolvable learning.", "essential_references_not_discussed": "No. Given that the paper appears to cite a comprehensive range of related works in the field, it is likely that the authors have covered the essential literature in feature evolvable learning. While the paper covers foundational work, discussing recent innovations in dynamically adjusting kernel functions could help readers understand how the proposed method fits into the current trends and innovations in adapting kernels to changing data scenarios.", "other_strengths_and_weaknesses": "Strengths:\n1.The concept of kernel ortho-mapping discrepancy introduced in this paper is novel. Unlike most existing methods that rely on static feature spaces, which struggle to handle the evolving nature of feature-adaptive data streams, the proposed approach effectively captures information across different stages. By leveraging ortho-mapping discrepancy with kernel functions, the authors establish relationships between distinct feature spaces, enabling more efficient and effective learning.\n2.The theoretical framework of this paper is well-developed and rigorous. They present the convergence result of kernel ortho-mapping discrepancy and utilize it to the regret analysis of the feature evolvable stream setting. The final theorem reveals the key factors influencing model convergence in this setting, which are consistent with empirical observations. \n3.The proposed one-pass learning framework is well-designed, and the integration of online kernel learning with random Fourier features ensures both memory and computational efficiency. This approach enables the model to process large-scale datasets in a streaming manner without the need to store the full or partial training data. Such a design is particularly valuable for real-world applications that involve continuous data streams, making it highly practical and scalable.\n\nWeaknesses:\n1. The scenario of the OPFES algorithm can be applied is a little bit limited. The feature space can only change once during the whole learning process. \n2. This article only considers hinge loss without analyzing other popular loss functions. The theoretical analysis is based on hinge loss, and the online learning process focuses on hinge loss as well. This article could be improved if more types of loss functions can be added to this algorithm.", "other_comments_or_suggestions": "The notation in part “Previous Model Reuse” could be simplified for better readability. Besides, it would be better if the implementation detail of compared methods are presented in Appendix.", "questions_for_authors": "1.Are the methods in this paper applicable to general kernel functions? The methods in this paper are founded on shift-invariant kernels. I'm especially interested in whether they can be applied to general kernels.\n2.Why does the article restrict the loss function to hinge loss only? What effects will it have on the theorems in this article if we substitute the loss function with MSE, logistic loss or exponential loss? Will the learning procedure in the OPFES algorithm still be effective for other loss functions?", "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": "mZHTxBVP4t", "reviewer": "Reviewer_2L3u", "summary": "This work focuses on the online learning scenario with a special assumption of the environment: the feature space evolves, where old features vanish and new features emerge during the process of online learning. This work considers to characterize the feature relationship via kernel function, and proposes the KOM discrepancy (Kernel Ortho-Mapping Discrepancy) as a difference measure between two feature spaces, which equals the minimum difference between the empirical mappings of two kernel functions. Based on the proposed KOM discrepancy, the authors develop the OPFES approach, which consists of the online learning process covering all three stages in feature evolvable data stream. The OPFES approach includes the traditional online kernel learning as well as the online optimization of the proposed KOM discrepancy. The authors verify the superiority of the proposed OPFES approach both theoretically and empirically. They provide regret bound for the proposed OPFES approach, and the experimental result shows the promising performance of the OPFES approach.", "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": "[Q1] …whether it is necessary to adopt random Fourier features, or are there other kernel approximation methods that are compatible with the OPFES approach?\n\n[A1] We will clarify that we take random Fourier features to avoid storing the entire and partial data, since kernel function $k(x_1,x_2)$ is defined on a pair of instances, and previous online kernel learning requires to store partial and entire training data [Kivinen et al. 2001; Orabona et al. 2012; Ghari & Shen 2024]. We will clarify that the random Fourier features technique has been a popular approximation with theoretical guarantee [Rahimi & Recht, 2007; Avron et al., 2017; Likhosherstov et al., 2022], and it is interesting to exploit other approximations.\n\n [Q2] What is the relationship between feature evolvable learning and multi-modal learning? Can it be viewed as an online version of multi-modal learning... \n\n[A2] We will clarify that our work focuses on the general feature spaces without constraints on the types of feature spaces as in [Hou et al., 2017; Zhang et al., 2020], and it can be directly used for two-modal learning. For multi-modal (more than two modals) learning, this problem becomes rather difficult since we should consider multiple and combinatorial correlations for multiple models.\n\n[Q3] Is it possible to apply other non-linear models, i.e., neural networks, to the feature evolvable data stream learning scenario with the proposed KOM discrepancy?\n\n[A3] We will clarify that this work considers different non-linear models by selecting different kernel functions, such as Gaussian kernels. It is interesting to consider deep neural networks, and we could take the NTK technique [Jacot et al., 2018; Novak et al., 2022] to analyze neural networks with the KOM discrepancy.", "claims_and_evidence": "Yes. The claims made in this submission is well-supported. The authors claim that the proposed OPFES approach is superior to other methods, and present both theoretical and empirical evidence. They give a regret bound to show that the OPFES approach benefits from the minimization of KOM discrepancy and the previous obtained kernel model. Besides, they conduct extensive experiments to show that the performance is overall better than other online learning methods with or without the modification for feature evolvable data streams.", "methods_and_evaluation_criteria": "Yes. The proposed methods and criteria make sense for the problem. In online learning, it is quite common to feed online learning algorithm with data instances from traditional benchmark datasets in random order to simulate the online learning process, which is also adopted in this paper. Besides, the cumulative error rate is also a widely used criteria in online learning scenario.", "theoretical_claims": "Yes. I checked the detailed proofs of two main theorems in the appendix, and I believe that the proofs are correct. For Theorem 3.3, the authors incorporate the empirical kernel mapping to derive the finite-dimensional kernel mapping, and consider to bound the difference of linear SVMs under the finite-dimensional feature mapping. The proof of Theorem 3.3 is straightforward and easy to follow. \nFor another important theorem, Theorem 4.3, the proof basically follows traditional regret analysis of online SVM method, but uses Theorem 3.3 to generalize traditional regret bound to feature evolvable scenario. The proof technique is interesting and correct.\nFor other theorems in this paper, I roughly checked the proof. The ingredients are similar, and the proofs seem to be correct.", "experimental_designs_or_analyses": "Yes. The experimental designs are sound. The authors first introduce other compared methods, and gives a detailed discussion on the parameter settings of each method. They then compare the cumulative error rate of these methods, which is a very important criteria for online learning methods, and they give some analysis on the experimental result. They also conduct experiment on different dimensionalities of random Fourier feature to show that the algorithm benefits from moderately large number of features. The experimental result is overall convincing.", "relation_to_broader_scientific_literature": "This work has great impact on the area of online learning with feature evolvable streams, or even on multi-model learning if it were to be accepted. Previous works on this area mostly consider linear feature relationships, while this paper proposes to incorporate kernel mapping and describe the feature relationship as the proposed KOM discrepancy. The proposed discrepancy is not limited to linear relationship, which pushes the performance boundary forward for algorithms handling feature evolvable data streams. Benefit from the KOM discrepancy, the authors propose OPFES method and achieve the state-of-the-art performance among other representative algorithms, which mostly consider linear relationship between different feature spaces.", "essential_references_not_discussed": "The authors do not miss any important related works. I am familiar with online learning, and I think that the authors have already cited all important works in this area. \nThe paper mentions many famous online learning algorithms, e.g., online SVM, online kernel SVM, etc. The authors also compare the proposed method with previous state-of-the-art algorithms like the variations of FESL and OCDS. \nSince this paper also gives some theoretical analysis of the proposed OPFES approach, I also checked the related works in this area. I found that the regret bound in this paper achieves O(1/\\sqrt{T}) rate, which is comparable with the state-of-the-art result in online learning scenario with strongly convex loss function. The related theoretical works are also cited in this paper.", "other_strengths_and_weaknesses": "The detailed strengths of this work are as follows:\n1. This work is well-written and it is easy to follow. Besides, the authors also uploaded the source code in the supplementary material, which further enhances the reproducibility. \n2. This paper shows a relatively good originality. The scenario of online learning with changing feature spaces was introduced a couple of years ago and many algorithms were proposed. However, existing methods only focus on linear transform between feature spaces, yet without theoretical guarantee on the regret of the online learning algorithm. The authors introduce the KOM discrepancy to characterize the relationships between old and new feature spaces, which considers non-linear and more complicated relations compared with most existing algorithms. In addition, they theoretically demonstrate that the difference between the performances of two optimal kernel classifiers can be upper-bounded by KOM discrepancy, and reaches better regret bounds based on this theorem. \n2. This paper has solid theoretical and empirical analysis and is significant to some extent. It theoretically shows that the model learned in the old stage can help achieve fast convergence and better regret in the new stage, which is inspiring and interesting to further develop more practical learning algorithms for this scenario. The empirical result also verifies the superiority of the OPFES method, and is convincing for me.\n\nDespite the strengths above, I have some concerns on this work:\nThe notations used in this paper are a bit confusing, with a large number of subscripts and superscripts that significantly affect the readability of the text. This complexity makes it challenging for readers to follow the main arguments and mathematical formulations. I recommend simplifying the notation wherever possible to enhance clarity.", "other_comments_or_suggestions": "The clarity of this work could be further improved if the authors were to summarize all the notation used in this paper in a table. Current notations are a little bit confusing. Despite the excellent work, it did take me a long time to understand each notation.", "questions_for_authors": "1. It seems that the OPFES approach is highly dependent on the random Fourier feature representation of kernel functions. I would like to know whether it is necessary to adopt random Fourier features, or there are other kernel approximation methods that are compatible with the OPFES approach?\n2. What is the relationship between feature evolvable learning and multi-model learning? Can it be viewed as an online version of multi-model learning? For example, in the previous stage only images can be observed, and in the current stage only text description is available.\n3. Is it possible to apply other non-linear models, i.e., neural networks, to the feature evolvable data stream learning scenario with the proposed KOM discrepancy?", "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: In this paper, the authors introduce a Kernel Ortho-Mapping discrepancy to characterize relationships between two different feature spaces via kernel functions and correlate it with the optimal classifiers learned from different feature spaces. Based on this discrepancy, the authors develop a one-pass algorithm for feature evolvable learning. They provide both theoretical analysis and experimental results in this paper. 

After the rebuttal period, four of five reviewers are positive towards this paper. While Reviewer XL9p kept their negative rating. After reading the paper and discussions, I think this is overall an interesting paper. However, I partially agree with Reviewer XL9p. For example, Reviewer XL9p pointed out, "the scope of the theoretical analysis is narrow and limited to binary classification using hinge loss and shift-invariant kernels" and "lacking supporting evidence that their method can be extended." The authors' response is not enough. They should adjust their claim and be careful about their conclusions. Considering all of these, I recommend "weak accept."
Decision: Accept (poster)