Minimax Forward and Backward Learning of Evolving Tasks with Performance Guarantees
Authors: Veronica Alvarez
Santiago Mazuelas
Jose A. Lozano
Venue: NeurIPS 2023 poster (2023)
Keywords: Concept drift
Continual learning
Minimax classification
Performance guarantees
TL;DR: This paper presents incremental minimax risk classifiers that account for evolving tasks and effectively exploit forward and backward learning.

Abstract: For a sequence of classification tasks that arrive over time, it is common that tasks are evolving in the sense that consecutive tasks often have a higher similarity. The incremental learning of a growing sequence of tasks holds promise to enable accurate classification even with few samples per task by leveraging information from all the tasks in the sequence (forward and backward learning). However, existing techniques developed for continual learning and concept drift adaptation are either designed for tasks with time-independent similarities or only aim to learn the last task in the sequence. This paper presents incremental minimax risk classifiers (IMRCs) that effectively exploit forward and backward learning and account for evolving tasks. In addition, we analytically characterize the performance improvement provided by forward and backward learning in terms of the tasks’ expected quadratic change and the number of tasks. The experimental evaluation shows that IMRCs can result in a significant performance improvement, especially for reduced sample sizes.

Minimax Forward and Backward Learning of Evolving Tasks with Performance Guarantees
Verónica Álvarez!
Santiago Mazuelas 1.2
Jose A. Lozano 1.3
BBasque Center of Applied Mathematics (BCAM)
IKKERBSSQUE-BaSqquee Foundation for Science 3 University of the Basque Country UPV/EHU {valvarez, smazuelas, j jlozano) @bcamath...hhco..c..aa..a.....ha org
Abstract
For a sequence of classification tasks that arrive over time, is common that tasks are evolving in the sense that consecutive tasks often have higher similarity. The incremental learning of growing sequence of tasks holds promise to enable accu- rate classification even with few samples per task by leveraging information from all the tasks in the sequence (forward and backward learning). However, existing techniques developed for continual learning and concept drift adaptation are ei- ther designed for tasks with iime-independent similarities or only aim to learn the last task the sequence. This paper presents incremental minimax risk classifiers (IMRCs) that effectively exploit forward and backward learning and account for evolving tasks. addition, we analytically characterize the performance improve- ment provided by forward and backward learning in terms of the tasks' expected quadratic change and the number of tasks. The experimental evaluation shows that IMRCs result in significant performance improvement, especially for reduced sample sizes.
Introduction
In practical scenarios, is often of interest to incrementally learn a growing sequence of classifica- tion problems (tasks) that arrive over time. In such sequence, it is common that tasks evolving in the sense that consecutive tasks often have higher similarity. Examples of evolving tasks are the classification of portraits from different time periods [1] and the classification of spam emails time (2): in these problems, the similarity between consecutive tasks (portraits consecutive time periods and emails from consecutive years) is significantly higher (see Figure 1 The incremental learning of a growing sequence of tasks holds promise to significantly improve performance by lever- aging information from different tasks. Specifically, at each time step, information from preceding tasks can be used to improve the performance of the last task (forward learning) and, reciprocally, the information from the last task can be used improve the performance of the preceding tasks (backward learning) 31.) Such transfer of information can enable accurate classification even in cases with reduced sample sizes, thus significantly increasing the effective sample size (ESS) of each task. However, exploiting the benefits of forward and backward learning is challenging due the continuous arrival of samples from tasks characterized by different underlying distributions (d-8)
Techniques developed for concept drift adaptation (aka learning in dynamic scenario) designed for evolving tasks but only aim to learn the last task in the sequence. In particular, methods based on learning rates learn the last task by slightly updating the classification rule for the preceding task [12 13); and methods based on sliding windows learn the last task by using a set of stored
samples from the most recent preceding tasks [14 15 In concept drift adaptation, each time
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

1970
1980
1990
2000
U4
U3
U
U2
P3
P4
P1
Single-task learning
Forward learning
Forward and backward learning
Figure I: Tasks that arrive time are characterized different underlying distributions and consecutive tasks often have higher similarity. The black line represents the evolution the underlying distributions that characterize different tasks. IMRCs minimize the worst-case error probability over uncertainty sets L4; that can include the underlying distribution A single task uncertainty set (blue hexagons) can be obtained leveraging information only from the corresponding task, while forward uncertainty set (green hexagons) can be obtained leveraging information from preceding tasks. Then, the proposed methodology obtains forward and backward uncertainty sets (red hexagons) leveraging information from all the tasks the sequence.
step only the last task is considered of interest, and is learned leveraging information from the most recent preceding tasks since they are the most similar to the last task.
Techniques developed for continual learning (aka lifelong learning)
17 20 aim to learn the 4
whole sequence of tasks but existing methods are designed for situations where tasks' similarities do not depend on the time steps when tasks are observed. In particular, methods based on dynamic architectures learn shared parameters using samples from all the tasks together with task specific parameters using samples from the corresponding task (6. [2]]; and methods based on replay learn parameters using pool of stored samples from all the preceding tasks together with the samples from the last task [5. 7 Existing methods for continual learning are not designed for evolving tasks and consider scenarios in which the order of the tasks the sequence is not relevant. In the current literature of continual learning, only [21] considers scenarios with evolving tasks but focus on the theoretical analysis of transferring information from the preceding tasks.
This paper presents incremental minimax risk classifiers (IMRCs) that determine classification rules minimizing worst-case eтror probabilities over uncertainty sets that can contain the sequence of evolving underlying distributions. The proposed techniques can effectively exploit forward and backward learning by obtaining uncertainty sets that get smaller using information from all the tasks (see [.. Specifically, the main contributions presented in the paper are as follows.
We propose forward learning techniques that recursively use the information from preced- ing tasks reduce the uncertainty set of the last task.
We propose forward and backward learning techniques that use the information from the last task to further reduce the sequence of uncertainty sets obtained with forward learning.
We analytically characterize the increase in ESS provided by the presented methods in terms of the expected quadratic change between consecutive tasks and the number of tasks.
We numerically quantify the performance improvement provided by IMRCs in comparison with existing techniques using multiple datasets, sample sizes, and number of tasks.
Notations Calligraphic letters represent sets; ||- and || >/ denote the 1-norm and the infinity norm of its argument, respectively; and denote vector inequalities; I[-} denotes the indicator function; and Ep(-} and V-r,(-} denote the expectation and the variance of its argument with respect to distribution p. For a vector v, (t)) and vT denote its i-th component and transpose. Non-linear operators acting on vectors denote component-wi 2 denote the vector formed by the absolute value and the square of each component, respectively. For the reader's convenience, we also provide Table in Appendix Ala list with the main notions used in the paper and their corresponding notations.
operations. For instance, v and

---

2
Preliminaries
This section first formulates the problem of incrementally learning a growing sequence of tasks, and describes evolving tasks in comparison with the time- dine-independent assumption common in continual learning. Then, we briefly describe MRCs that determine classification rules by minimizing the worst-case error probability over uncertainty set.
2.1 Problem formulation
In the following, denote by X' the set of instances attributes, Y the set of labels classes, ( x ))) the set of probability distributions over X x V and T(X,, )) the set of classification rules. classification task is characterized by underlying distribution p" E A(X' y), and standard supervised classification methods use a sample set = {(T;,)))) }= formed by n i.i.d samples from distribution p" find a classification rule h 3() with small expected loss E(h,p")
In the addressed settings, sample sets D1. D2... arrive over time steps 1, corresponding with different classification tasks characterized by underlying distributions Pt, P2.P2..... P2..... Incremen- tal learning aims to continually learn over time the growing sequence of tasks exploiting informa- tion acquired from all the tasks. At each time step k learning methods obtain classification rules h1, .y..... hy for the current sequence of l tasks using the new sample set Dj and certain informa- tion retained from step k 1. The performance of learning methods assessed each time step k by quantifying the performance in the current k tasks. For instance, overall performance can be as- sessed by the averaged error h شド= E(hy, Pý) with E(h,, Pý) the expected loss of the classification rule hy for distribution Py.
Evolving tasks considered by methods for concept drift adaptation, but existing continual learn- ing methods are designed for scenarios where tasks' similarities do not depend on the time steps when tasks are observed. These scenarios are usually mathematically modeled assuming that the tasks' distributions P1, p.,... are independent and identically distributed (i.i.d)) 188 19). In this paper, we develop techniques designed for evolving tasks that can be mathematically modeled as- suming that the changes between consecutive distributions zero-mean (evolving task assumption). The assumption in this paper is not stronger than the usual i.idd assumption and can better describe evolving tasks; their main difference is considering inde- pendent changes between consecutive distributions instead of independent distributions. Note that with independent distributions the difference between the distributions of the i-th and the (i + f)-th tasks has zero mean and variance War (pi++ pi} = Var(Pt+1 - p.} = 2aar(p1 [p1} that does not depend on t. On the other hand, with independent changes between consecutive distributions, the difference between the distributions of the i-th and the (i + t)-th tasks has zero mean and variance
Pi, P2,... are independent and
Var(p:+e - p.} = EE= Var(pi+s Pi+s-1} that increases with t. Appendix further describes how the assumption used in the paper more appropriate for evolving tasks than the conventional i..d. assumption using real datasets.
2.2 Minimax risk classifiers
The methods presented in the paper are based on robust risk minimization 22 23
instead of em- pirical risk minimization since training samples corresponding to different tasks follow different distributions. In particular, the worst-case expected loss against an uncertainty set given by constraints on the expectation of feature mapping &
utilize MRCs [24, (25) that learn classification rules by minimizing
X x y + R
- U fp A(Xx)) (E - {}
where t denotes mean vector of expectation estimates and À denotes a confidence vector. Feature mappings are vector-valued functions over X' x V, e.g., one-hot encodings of labels (26) with in- stances represented by values from the last layers neural network g 27 or by random Fourier
features (RFF) [28.]] 29
Given the uncertainty set 4, MRC rules are solutions of the optimization problem
R(U)
min max E(h, p) heT(X.)) pEl
(2)
3

---

where R(U) denotes the minimax risk and ((h, p) denotes the expected loss of classification rule for distribution p. In the following, we utilize the 0-1-loss so that ((h,)) Ep (I(h(x) * y} and the expected loss with respect to the underlying distribution becomes the error probabil- ity of the classification rule. Deterministic MRCs assign each instance x E X with the label h(r:) arg maxyey ((x,)) ")""=² where the parameter μ is the solution of the convex optimization problem
Eyec ((z,8)
min 1 1- ++ NEX,CCy
max
A
(3)
|C|
given by the Lagrange dual of (2 124 25).
The baseline approach of single-task learning obtains a classification rule hú for each j-th task leveraging information only from the sample set Dj = (5,,)) given by ny samples from distribution Pj. In that case, IMRCs coincide with MRCs for standard supervised classification that obtain the mean and confidence vectors as
n T (a))) X
85 8)
(4)
n2J
Thj
with 5 an estimate of Varp, (ar,, y)}, e.g., the sample variance of the ny samples. The vector 8j describes the mean squared emrors (MSEs) of the mean vector components and directly gives the confidence vector A shown in (4)
MRCs provide bounds for the minimax risk R(U)) in terms of the smallest minimax risk de- scribed in [24. 25 30). The smallest minimax risk is that corresponding to the ideal case of knowing mean vectors exactly, that is, the minimax risk corresponding with the uncertainty set ug {p E A(X' x y) (x,, = To) given by the expectation T = Ep, (I y)}. In the baseline approach of single-task learning. if Rşe and 1z.0 denote the smallest minimax risk and the MRC parameter corresponding with U with probability at least 1 - 5 we have that
M(x + M(x+
1) log(2m//))
R()) S RT
|
(5)
where M and are such that [1 y)1l S. M for any (x. y) X' y and subG( 3 kojj s-bG(-) denotes the sub-Gaussian parameter of the argument components, and D, denotes the ran- dom variable given by the feature mapping of samples from the j-th task. Inequality (5) is obtained using the bounds in (25) together with the Chernoff bound (31] for sub-Gaussian variables.
In the following sections, we describe techniques that obtain the mean and MSE vectors using for- ward and backward learning. Once such vectors are obtained, IMRC methods obtain the classifier parameter μ4 for each j-th task solving the convex optimization problem in (3) that can be efficiently addressed using conventional methods 32
3 Forward learning with performance guarantees
This section presents the recursions that allow to obtain mean and MSE vectors for each task retain- ing information from preceding tasks. In addition, it characterizes the increase in ESS provided by forward learning in terms of the tasks' expected quadratic change and the number of tasks.
3.1 Forward learning
Let 77 andd 8 denote the mean and MSE vectors for forward learning corresponding to the j-th task. The following recursions allow to obtain T, and s, for each j-th task using the vectors for the preceding task 1: 8 as
1
T
T
8 + 8, + d [T-] T,), 8j -
(6)
8j
8 8--1
d
with 7 and 8j given by
4 and - T and 8T = 81-

---

The vector de assesses the expected quadratic change between consecutive tasks described by wi - Taking di = [ and o = Varp { (z, y)} for any i, the first recur- sion in (6 provides the unbiased linear estimator of the mean vector ? based on D1. Dz..... Dj that has the minimum MSE, while the second recursion in (6) provides its MSE (see Appendix for a detailed derivation). Vectors of and de can be estimated online using the sample sets. In particular, ? can be estimated as the sample variance, while di can be estimated using sample averages as
(T
T where io, .i,..., w are the closest indexes to i E (1,2,..... .,k. (7) W
Recursions in (6) obtain mean and MSE vectors for the j-th task by using information from pre- ceding tasks and the j-th sample set Dj. Specifically, the first recursion in (6) obtains the mean vector Tj by adding a correction the sample average T. This correction is proportional the difference between j and و with proportionality constant that depends on the MSE vectors
s,. 8 and the expected quadratic change df. In particular, s < 83-1 + d.. the mean vector is given by the sample average as in single-task learning, and if 8, > $3-1 + df. the mean vector is given by that of the preceding task. Note that for forward learning, at each step only the vectors for the last task Tx and $ need to be obtained from those of the (k- 1)-th task, the vectors for the remaining tasks stay the same as at step k (see also Fig. 2 and Alg. [bllow)
3.2 Performance guarantees and effective sample sizes with forward learning
The following result provides bounds for the minimax risk for each task using forward learning. Theorem 1. Le be the uncertainty set given by |I using the mean and confidence vectors ; and ,j- = V33 provided by (6), and let k be such that subG( I Kar and subG (w,) 3 kd j = 1, 2...., k. Then, under the evolving task assumption of Section we have with probability
least 1 8 that
R(UJ) S + M(K + 1) 2 log (2m/d)
|100 ||, for any j (1,2....,A)
(8)
| 00 +2
with ni = nn and nj 2 ny + nーー1 5
for 2 2.
0c
[dj
Proof. See Appendix C
The value n. in (8) is the ESS of the proposed IMRC method with forward learning since the bound in K coincides with that of single-task learning in 55) if the sample size for the j-th task is nj. The ESS of each task is obtained by adding fraction of the ESS for the preceding task to the sample size. In particular, if d? is large, the ESS is given by the sample size, while if df is small, the ESS given by the sum of the sample size and the ESS of the preceding task.
The bound in K shows that recursions in (6) do not need to use very accurate values for o, and dj- Specifically, the coefficienty x in ( can be taken to be small as long as the values used for oj and d, are not much lower than the sub- Gaussian parameters of Φ and Wj. respectively. In particular,
is smaller than the maximum of M/ miny. (6) } and 2M/ miny, ( due to the bound for the Lub-Gaussian parameter of bounded random variables (see e.g., Section 2. 2.1.2 2 in [31]).
Theorem Isoows shows the increase in ESS in terms of the ESS of the preceding task. The following result allows to directly quantify the ESS in terms of the tasks' expected quadratic change and the number of tasks.
Theorem 2. If |dd loc < d2, M < 1, and n, 2 n for j = 1,,2... we have that the ESS can be taken so that satisfies
... k. then for any j E (1,2,..., kk.
+ (1 + + - -1-
a(1 + Haj-j11 - 11--)-111110 a
2
n
with
(9)
nd
In particular, if nd? < 1//2², we have that n. 2 n (1 1
Proof. See App
5

---

The above theorem characterizes the merrasee in ESS provided by forward learning in terms of the tasks' expected quadratic change. Such increase grows monotonically with the number of preceding tasks/ j as shown in ( and becomes proportional to when the expected quadratic change is smaller than n/)) Figureß further illustrates the increase in ESS with respect the sample size (nz) /m) due forward learning in comparison with forward and backward learning.
4 Forward and backward learning with performance guarantees
This section presents the recursions that allow to obtain mean and MSE vectors for each task lever- aging information from all the tasks. In addition, it characterizes the increase in ESS provided by forward and backward learning in terms of the tasks' expected quadratic change and the number of tasks.
Backward learning is more challenging than forward learning since the new task provides additional information for preceding tasks at each time step. while the information from preceding tasks is always the same. The techniques proposed below for backward learning effectively increase the ESS over time by carefully accounting for the new information each step.
4.1 Forward and backward learning
At each step k. the proposed techniques learn to classify each j-th task leveraging information obtained from the j preceding tasks (tasks {1,2, .....))) and from the k succeeding tasks (tasks fj+1.j+2.... k)). From preceding tasks, we obtain the forward mean and MSE vectors ; 8j using recursions in (6), while from succeeding tasks, we obtain the backward mean and MSE vectors TJ² *T using recursions in (6) retrodiction. Specifically, vectors TJ and 85* are obtained
using the recursion as for TJ and 8j in (6 with 8I-1, di+1, and J++1 instead of df. and 7--1-
Let Te and 8 denote the mean and MSE vectors for forward and backward learning correspond- ing to the j-th task for j E f1,2,...,k! MSE vectors r and 85 for each j-th task using those vectors for forward learning T 8y and backward learning T T $341
k}. The following recursions allow to obtain the mean and
-1
1 87
7, Tj.
-,
8
(10)
8
+ j+1
8j+1 + d; 1+1
with Tk = Tk, of 8% and T =
8k Analogously to the case of forward and o = Varp. { (x.v) for any i, the first recursion in (10) provides the unbiased linear estimator of the mean vector T3 based on D1, D2...., Dj and Dj+1, D............. D3 that has the minimum MSE, while the second recursion in (10 provides its MSE (see Appendix for a detailed derivation).
learning in Section 3.1 taking di - =
Recursions in (T)) obtain at step & the mean and MSE vectors for the j-th task by retaining infor- mation from preceding tasks and acquiring information from the new task. Specifically, the first recursion in (10) obtains the mean vector , - by adding correction to the mean vector of the cor- responding task ; obtained for forward learning. This correction proportional the difference between T and - j+1 with proportionality constant that depends on the MSE vectors sy" *8741 and the expected quadratic change d In particular, if 8 < $ + dz 1 the mean vector is given by that of the corresponding task for forward learning, and if $j > 8 $ + dz+i, the mean vector is given by that of the next task for backward learning.
4.2 Implementation
This section describes the implementation of the proposed IMRCs with forward and backward learn- ing and its computational and memory complexities.
Figure depicts the flow diagram for the proposed IMRC methodology. The presented techniques carefully avoid the repeated usage of the same information from the sequence

---

of tasks. At each step k. the IMRC method obtains forward mean vector Tk for the k- th task leveraging information from preceding tasks using the forward mean vector Tk-1 and the sample average T-. Reciprocally, backward mean vectors J for each j-th task are obtained leveraging information from the k-th task through the sample average Tk- Then, the forward and backward mean vectors T5" are obtained from the forward mean vec- T tors - and the backward mean vectors Tj+1" In particular, ;j provides the information from the preceding tasks 1, ........ ; j. while T544 pro- vides the information from the succeeding tasks j ++1,, j + 2.......
3+1
T++1
......... k. At each step k, the IMRC method obtains forward and backward mean vectors - for j = - b, - b + I,...,k k with the number of backward steps. In partic- ular, if b = 0, IMRC carries out only forward learning. Note that, at each step k, the proposed IMRC methods only need to retain the forward mean vectors 7i and sample averages T, for j = k- 6, k- b+ kk....,k
j-1
T j+1
Figure 2: Diagram for IMRC methodology.
Algorithm IMRC at step k
Input:
D₁ from new task, and T,, 8j. T5 8j for k b k from previous b 1 steps Output: fe for k - b S j I k. Tk, St; TE 8k
Obtain sample average and MSE vectors Th Tk. st
Sk using sample set Dx b Single-task
Estimate the tasks' expected quadratic change di using
Obtain the forward mean and MSE vectors Tx 8h using 6
b. Forward
Take A = / 8 and obtain classifier parameter M4 solving the optimization problem for j = k 1, k 2.....
b do Estimate the tasks' expected quadratic change df using 7
Obtain backward mean and MSE vectors T 1 8741 using ④ in retrodiction
> Backward
Obtain mean and MSE vectors T s5 using (10
Forward and backward
Take A,m V 88 and obtain classifier parameters Mj solving the optimization problem 3
Algorithm details the implementation of the proposed IMRCs at each step. For & steps, IMRCs have computational complexity (((b+ 1) mm) and memory complexity O((b k)m) where K is the number of iterations used for the convex optimization problem (3) m is the length of the feature vector, and is the number of backward steps. The complexity of forward and backward learning increases proportionally to the number of backward steps that can be taken to be rather small, as shown in the following. Even more efficient implementations can be obtained using Rauch-Tung- Striebel recursions (see e.g., Section 7.2 344 that can used obtain TJ from T =k as shown in Appendix
4.3 Performance guarantees and effective sample sizes with forward and backward learning
The following result provides bounds for the minimax risk for each task using forward and backward learning
Theorem 3. Let U be the uncertainty set given by ① using the mean and confidence vector
T and 21 = V 1 provided by 10b, and let x and ny be as Theorem I Then, under the evolving task assumption of Section 2 we have with probability at least 5 that
| for any E 21, A)) (11) B(U S R27 + M(K + 1) 2 log (2m/0)
nn n
7

---

|
with no = " and nith 2 nn + +nj+l |aaf|
for j S k - 1, where the backward
njzi || mm
110
ESSs satisfy ni ne and n5 k 2 ny + nsfi |
Proof. See Appendix
Theorem 3 shows that the methods proposed can increase ESS of each task by leveraging informa- tion from all the tasks. In particular, the bounds for forward and backward learning provided by inequality (IT) are significantly lower than those for forward learning in Theorem [I The ESS of each task is obtained by adding fraction of the ESS for the next task to the ESS of the correspond- ing task using forward learning. In particular, if df is large, the ESS is given by that with forward learning, while if df is small, the ESS is given by the sum of the ESS using forward learning and the ESS of the next task.
Theorem shows the increase in ESS in terms of the ESS with forward learning and the ESS of the next task. The following result allows to directly quantify the ESS in terms the tasks' expected quadratic change and the number of tasks.
Shows
Theorem | xcc d², .M < 1, and n, 2 n for j = 1.2,...... 2...,.... .k....,, then for any E (1, ..)
we have that the ESS in can be taken so that it satisfies
(1 + a) 2 l
(1+ a1+
2
n
with
a(1 + (2)
a(1 ( a)) +a
1
+ ndF
(12)
In particular, for j 2 2, we have that
j(k- - 9)
1-1
3(k - 9)
n 2 nz + n2
2 12
if
nd
< j
j+ 2(k -]
3
j + 2(k -
1
2
n5 2 njj +
5V de
1+
5v nd?
if
j
nd
<1
1
2
n5 2 nij +
1
if
nd > 1.
3d
3nd2
Proof. See Appendix G
The above theorem characterizes the increase in ESS provided by forward and backward learning.
This increase grows monotonically with the number of pre- ceding tasks j and with the number of succeeding tasks k as shown in (12 In addition, it becomes proportional to the total number of tasks A when the expected quadratic change is smaller than 1/(j2n) and 2 k/2. Figure Ba further illustrates the increase in ESS with respect to the sample size (m /n) due to forward and backward learning in compari- son with forward learning. As the figure shows, the increase in ESS can be classified into three regimes depending on the sample size n and the expected quadratic change d2. The ESS is only
100
mio/u
nio 13 /n
nioo in
211
+ nivoo/ /T.
ESSA
nito //v
- min0 /n
marginaly larger than the sample size for size- ble values of ndf (large samples sizes drastic changes in the distribution); the ESS quickly in- creases when nd? becomes small (reduced sam- ple sizes and moderate changes in the distribu- tion); and the ESS becomes proportional to the total number of tasks & if ndt is rather small (very small sample sizes and very slow changes in the distribution).
10
10
nd2
Figure 3: ESS increase provided by forward and back- ward learning.

---

Table Classification error, standard deviation, and running time of the proposed IMRC methad in comparison
with existing techniques using v = samples per task.
Method
GEM [
MER (17)
ELLA [1]
EWC [6]
Condor [9]
DriftSurf (10)
AUE [16]
IMRC
Yearbook (
.18 4 033
.16 = .03
.45 + 001
.47 4 .05
.14 +
.33 4 02
.33 = 002
.13 .04
noise [35]
.39 + 08
.17 = .03
.48 + .0
.47 + .04
.16 + .02
.48 + 02
.48 = 02
.15 .03
DomainNet [6
.69 + 05
.38 +
.67 + 05
.75 +: .04
.45 + 04
.3 02
.33
.34 4
UTKFaces [37]
.12 + 00
.17 + .99
.19 + .12
.12 + .00
.23 + 400
.12 00
.12 .00
.10 + .01
R. MNIST
.36 06
.37
.88 05
.48 4: 001
.45 .02
.8 02
.48 -
.36
CLEAR [32]
.57 + 10
.10 .03
61 .6
.65 + .03
.35 + .00
.33 .0
.33 = 01
.09 + .03
Supply
.66 011
.47 =
A1 .07
.47 .0
.36 + .01
.45 02
.45 =
10:::0
Usenet1 [40]
.88 + 02
.88 .12
.39 + 05
.48 + .02
.48 + .02
.40 + 001
.40 + .01
.32 .03
Usenet2 [40)
.66 +001
.33 .01
.39
.48 + .02
.42 +1
.35 + .0
.39 .03
.33
German [1
136
.38
.33
.11
.41 +
.36 00
.35
.34
Spam [2]
.25 1/
.13 = .02
.28 1
.33 4
+ .22
.24 203
.25 .03
.13 : .01
Covert. [10]
.09
.13 .01
.09 .00
.10 .0
Ave. running time
0,238
0.250
0,055
0.313
0.184
0.128
0.044
0.275
5 Numerical results
This section first compares the classification performance of IMRCs with existing techniques us- ing multiple datasets, then we show the performance improvement the presented IMRCs due to forward and backward learning. In Appendix H we provide additional implementation details and numerical results. The implementation of the proposed IMRCs is available on the web https:// http:////w.cccc.ellaaannggggooio
for wewooo-iiieeeeetaa...e satrrmenttal-eeannnng lew.ningnnneeeeeeeee Neurr--euIPPSS 2023
The proposed method is evaluated using 12 public datasets composed by evolving tasks [IO (1, Six datasets are formed by images with paaracteristicsquulittfrlllll
that change over time; while the rest are formed by tabular data that are segmented by time (see further details in Appendix[[]. For instance, each task in the "Yearbook" dataset corresponds to portrait's photographs from one year from 1905 to 2013 and the goal is to predict males and females; and each task the "CLEAR" dataset corresponds to images with natural temporal evolution of visual concepts per year from 2004 to 2014 and the goal to predict if an image soccer, hockey, or racing. For the image datasets, instances are represented by pixel values in "Rotated MNIST" dataset, and by the last layer the ResNet18 pre-trained network [42] in the remaining datasets; while for the tabular datasets, instances are represented by 200 RFFs 228 29 with scaling parameter o² = 10.
The proposed IMRC method is compared with 7 of -eth--ttttchhque:: 2 techniques of contin- ual learning based on experience replay 17). technique of continual learning based on regular- ization [6]. a technique of continual learning based on dynamic architectures [4], 2 techniques of concept drift adaptation based on weight factors (9. [6]. and technique of concept drift adaptation
based on sliding windows [1d]. The syper-parametert in all methods are set to the default values provided by the authors. IMRCs are implemented using b = 3 backward steps and the expected quadratic change de is estimated using W = 2 in 7 In Appendix H among other additional re- sults, we study the change classification error and processing time achieved by varying the number b of backward steps.
In the first set of numerical results, compare the performance of the proposed IMRCs with existing techniques using n = 10 samples per task. These numerical results are obtained computing the average classification error over all the time steps and tasks in 50 random instantiations of data samples. As can be observed in Table [ IMRCs can significantly improve performance in evolving tasks with respect existing methods. Certain techniques of continual learning or concept drift adaptation achieve top performance in specific datasets, but the performance improvement of the methods presented are realized over general datasets with evolving tasks. The results for n 10 samples per task in Table[ complemented with results for 50, 100, and 150 samples per task in Tables 4 5 and in Appendix [ These results show that the improved performance of IMRCs compared to the mate-of-the-al techniques is similar for different sample sizes. In addition, Table shows that the average running time per task of IMRC methods is similar to other ofate-of-the-art methods.

---

Forward
Single lask
Forward backward
Forward K 10
Clussilication erronbingie task
-
Forward 100
Forward and backward à: 10
Forward 100
Forward and backward 100
Forward and backward à 100
Classfficttion
0.1
30
Number of tasks
Sample size
(a) Classification error per number of tasks in "Year- (b) Classification eтror per sample size in "Year- book" dataset.
book" dataset.
Figure 4: Forward and backward learning can sharply boost performance and ESS as tasks arrive.
In the second of numerical results, we analyze the contribution of forward and backward learn ing to the final performance of IMRCs. In particular, we show the relationship among classification error, number of tasks, and sample size for single-task, forward, and forward and backward learn- ing. These numerical results are obtained averaging, for each number of tasks and sample size, the classification errors achieved with 10 random instantiations of data samples in "Yearbook" dataset (see Appendix H for further details). Figure 4a shows the classification error of IMRC method di- vided by the classification eтror of single-task learning for different number of tasks with n 10 and n 100 sample sizes. Such figure shows that forward and backward learning can significantly improve the performance IMRCs as tasks arrive. In addition, Figure 4b shows the classification error of IMRC method for different sample sizes with & 10 and k: 100 tasks. Such figure shows that IMRCs with forward and backward learning for a 100 tasks and n 10 samples achieve significantly better results than single-task learning using = 100 samples. In particular, the ex- periments show that the methods proposed can effectively exploit backward learning that results in enhanced classification error in all the experimental results.
6
Conclusion
The paper proposes IMRCs that effectively exploit forward and backward learning and account for evolving tasks by using sequence of uncertainty sets that contain the true underlying distribu- tions. In addition, the paper analytically characterizes the increase in ESS achieved by the proposed techniques in terms the tasks' expected quadratic change and number of tasks. The numerical results assess the performance improvement of IMRCs with respect to existing methods using multi- ple datasets, sample sizes, and number of tasks. The proposed methodology for incremental learning with evolving tasks can lead to techniques that further approach the humans' ability to learn from few examples and continuously improve on tasks that arrive over time.
Acknowledgments
Funding in direct support of this work has been provided by projects PID2022-137063ND 100.
CNS2022-135203. and CEX2021-001142-S funded by MCIN/AEI/IO, HLINAAE//1..1003//// 13039/501 10001 1033 and the European Union "NextGenerationEU"/PP BCAM Severo Ochoa accreditation CEX2021-001 140-S----- MICIN AEI/ 10. 33039//0110000000000 funded by the Ministry of Science and Innovation, and programes ELKARTEK, IT1504-22, and BERC-2022-2025 funded by the Basque Government.

---

References
[1] Shiry Ginosar, Kate Rakelly, Sarah Sachs, Brian Yin, and Alexci Efros. A century of por- traits: A visual historical record of american high school yearbooks. In IEEE International Conference on Computer Vision Workshops, 2015.
[2] Tegiyot Singh Sethi and Mehmed Kantardzic. On the reliable detection of concept drift from streaming unlabeled data. Expert Systems with Applications, 82, 2017.
[3] Zhiyuan Chen and Bing Liu. Lifelong machine learning. Morgan & Claypool Publishers, second edition, 2018.
[4] Paul Ruvolo and Eric Eaton. ELLA: Conference Machine Learning, volume 30, 2013.
An efficient lifelong learning algorithm. In International
[5] David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. In Advances in Neural Information Processing Systems, volume 30, 2017.
[6] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, An- drei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabssa-BBrwwingg et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, (13), 2017.
[7] Christian Henning, Maria Cervera, Francesco D' A'Angl,,, Johannes Von Oswald, Regina Tra- ber, Benjamin Ehret, Seijin Kobayashi, Benjamin F Grewe, and João Sacramento. Posterior meta-replay for continual learning. In Advances in Neural Information Processing Systems, volume 34, 2021.
[8] Julio Hurtado, Alain Raymond, and Alvaro Soto. Optimizing reusable knowledge for continual learning via metalearning. In Advances in Neural Information Processing Systems, volume 34, 2021.
[9] Peng Zhao, Len Cai, and Zhi-Hua Zhou. Handling concept drift via model reuse. Machine Learning, 109(3), 2020.
[10] Ashraf Tahmasbi, Ellango Jothimurugesan, Srikanta Tirthapura, and Phillip B Gibbons. Drift- Surf: suable--tate/rcactiv--ttte learning under concept drift. In International Conference on Machine Learning, volume 38, 2021.
[11] Verónica Álvarez, Santiago Mazuelas, and Jose Lozano. Minimax classification under con- cept drift with multidimensional adaptation and performance guarantees. In International Con- ference on Machine Learning, volume 39, 2022.
[12] Jyrki Kivinen, Alexander Smola, and Robert C Williamson. Online learning with kernels. IEEE Trunsactions on Signal Processing, 52(8), 2004.
[13] Francesco Orabona, Joseph Keshet, and Barbara Caputo. The projectron: a bounded kemne- based perceptron. International Conference on Machine Learning, volume 25, 2008
[14] Albert Bifet and Ricard Gavalda. Learning from time-changing data with adaptive windowing. In SIAM International Conference on Data Mining, 2007.
[15] Cuong V Nguyen, Yingzhen Li, Thang D Bui, and Richard E Turner. Variational continual learning. In International Conference on Learning Representations, 2018
[16] Dariusz Brzezinski and Jerzy Stefanowski. Reacting to different types of concept drift: The accuracy updated ensemble algorithm. IEEE Transactions on Neural Networks and Learning Systems, 25(1), 2013.
[17] Matthew Riemer, Ignacio Cases, Robert Ajemian, Miao Liu, Irina Rish, Yuhai Tu, and Gerald Tesauro. Learning to learn without forgetting by maximizing transfer and minimizing interfer- ence. International Conference on Learning Representations, 2018.
[18] Andreas Maurer, Massimiliano Pontil, and Bernardino Comera-Paredes, The benefit of multi- task representation learning- Journal of Machine Learning Research, 17(81), 2016.

---

[19] Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil. Online-within- online meta learning. In Advances in Neural Information Processing Systems, 2019.
[20] Ju Xu and Zhanxing Zhu. Reinforced continual learning. In Advances in Neural Information Processing Systems, volume 31, 2018.
[21] Anastasia Pentina and Christoph H Lampert. Lifelong learning with non-iid tasks. In Advances in Neural Information Processing Systems, volume 28, 2015.
[22] Farzan Farnia and David Tse. minimax approach to supervised learning. In Advances in Neural Information Processing Systems, volume 29, 2016.
[23] Rizal Fathony, Anqi Liu, Kaiser Asif, and Brian D. Ziebart. Adversarial multiclass classifica- tion: A risk minimization perspective. In Advances in Neural Information Processing Systems, volume 29, 2016.
[24] Santiago Mazuelas, Andrea Zanoni, and Aritz Perez. Minimax classification with 0-1 loss and performance guarantees. In Advances in Neural Information Processing Systems, volume 33, 2020.
(25] Santiago Mazuelas, Mauricio Romero, and Peter Grünwald. Minimax risk classifiers with 0-1 loss. Journal of Machine Learming Research, 24(208):1-48, 2023.
[26] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learn- ing. MIT press, 2018.
[27] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8), 2013.
[28] Jing Lu, Steven CH Hoi, Jialei Wang. Peilin Zhao, and Zhi- Yong Liu. Large scale online kernel learning. Journal of Machine Learning Research, 17(1), 2016.
[29] Yanning Shen, Tianyi Chen, and Georgios B Giannakis. Random feature-basee online multi- kernel learning in environments with unknown dynamics. The Journal of Machine Learning Research, 20(1), 2019.
[30] Santiago Mazuelas, Yuan Shen, and Aritz Pérez. Generalized maximum entropy for supervised classification. IEEE Transactions on Information Theory, 68(4), 2022.
[31] Martin Wainwright. High-dimensional statistics: A asymptymt viewpoint. Cambridge University Press, 2019.
[32] Yu Nesterov and Vladimir Shikhman. Quasi-monotone subgradient methods for nonsmooth convex minimization. Journal of Optimization Theory and Applications, 165(3), 2015.
[33] Wei Tao, Zhisong Pan, Gaowei Wu, and Qing Tao. The strength of Nesterov's 's extrapolation in the individual convergence of nonsmooth optimization. IEEE Transactions on Neural Net- works and Learning Systems, (7),2019.
[34] Brian DO Anderson and John B Moore. Optimal Filtering.
Prentice-Hall, 1979.
[35] Zheda Mai, Ruiwen Li, Jihwan Jeong, David Quispe, Hyunwoo Kim, and Scott Sanner. Online continual learning in image classification: An empirical survey. Neurocomputing, 469, 2022.
[36] Xingchao Peng. Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In IEEE International Conference on Computer Vision, 2019.
[37] Zhifei Zhang, Yang Song, and Hairong Qi. Age progression/regression by conditional adver- sarial autoencoder. In IEEE Conference on Computer Vision and Pattern Recognition, 2017.
[38] Xisen Jin, Arka Sadhu, Junyi Du, and Xiang Ren. Gradient- editing of memory examples for online task-free continual learning. In Advances Neural Information Processing Systems, volume 34, 2021.
12

---

[39] Zhiqiu Lin, Jia Shi, Deepak Pathak, and Deva Ramanan. The CLEAR benchmark: Continual learning on real-world imagery. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
[40] Ioannis Katakis, Grigorios Tsoumakas, and loannis Vlahavas. An ensemble of classifiers for coping with recurring contexts in data streams, 2008.
[41] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[42] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, In IEEE Conference on Computer Vision and Pattern Recognition, 2016.

---

A Main notations used in the paper.
In this section we summarize the notations used in the paper. Table2]shows the notation used for the mean vector, the confidence vector, the MSE vector, the ESS, the uncertainty set, and the minimax risk using single task, forward, backward, and forward and backward learning.
Table Main notations used in paper
Single task
Forward
Backward
Forward and Backward
Mean vector
T
Confidence vector
X
MSE vector
8j
8j
8j
$5
ESS
ny
nith
n
Uncertainty set
Uj
U )
Uj
U
Minimax risk
R(U;)
R(U
k(
B Derivation of recursions in (6) for forward learning and recursions in (T0) for forward and backward learning
This section shows how recursions in L6 and recursions in (10) are obtained using those for filtering and smoothing in linear dynamical systems.
The mean vectors evolve over time steps through the linear dynamical system
w
(13)
where vectors w for j E (2, are independent and zero-mean because Pj Pj-1 are independent and zero-mean. In addition, each state variable T is observed at each step j through Ty that is the sample average of i.idd samples from py, so that we have
T
+ Uj
(14)
where vectors U, for j (1, k} are independent and zero mean, and independent of w for j E (1,2,...,k) k]. Therefore, equations (3) and (14 above describe a linear dynamical system (state-space model with white noise processes) (34] For such systems, the Kalman filter recur- sions provide the unbiased linear estimator with minimum MSE based on samples corresponding preceding steps D1, D2..... Dj. and fixed-lag smoother recursions provide the unbiased linear estimator with minimum MSE based on samples corresponding to preceding and succeeding steps D1, D2,.... .,.,, D3 [34]. Then, equations in (6) and equations in (10) obtained after some algebra from the Kalman filter recursions and fixed-lag smoother recursions, respectively.
C Proof of Theorem
Proof. To obtain bound in x we first prove that the mean vector estimate and the MSE vector given by (6) satisfy
P 11500(0) - -0 s k2/20 log
28
2m
2 (1 8)
(15)
8
for any component i = ..2...., m. Then, we prove that ||
8j 8o < M/ n
for j E
1 am
2.., k}. where the ESSs satisfy ni = nı and n, 2 ny + +
for j 2 2.
|o +
||d
To obtain inequality 15). prove by induction that each component 1,2
of the error in
the mean vector estimate 2, 750(0) -T, (4) is sub-Gaussian with parameter nj 12 8 (1) Firstly, for j 1, we have that
(i)
710 (6) -i (6) (p)(1) -1
(1)
14

---

Since the bounded random variable 1100 is nab-Gaussian with parameter o ( the mean vector estimate 2 is sub-Gaussian with parameter that satisfies
) then the error in
( (
2
K
o
K x²01 (1)
R1
If 2z-1 -
リー (0) is sub-Gaussian with parameter nz-1 (0)
I ni 8--1 (6)
for any
i = 1.2...., m. then using the recursions in (6) we have that
3/ 2) = イ) 200( - Tj = T (1)
T--1 + w
(1)
[--1 (2) -T²
(6)
+ t2)(0)
J-1
-- (8) + +w/ T (0)
(9)
+
1
(7-1 -0 -
(8)
(1) + 83
(1)
+ dd
8
J-1
(1)
-- (6) + + T- (0)
$
(
(0)
(
since w/ = = 5-1 If 0 = Tj-
3 the error in the mean vector estimate is given by
(1)
2j 10 (1) 00 (1)
(
(1)
0c (6)
+ 1/ 15- ())
(
3-1
+ 3 1
$ (1)
r--1
00
(4)
+ w)
(2)
T--1
(1)
(3)
+ 3
(1) ()) - - (0)
+12
5j (0
(1)
(1)
(1)
(0)
I
(1)
W
(2)
(
where w/²) and bj are aub-Gaussian with parameter aw (0) Therefore, we have that =0
and o (o)
/ /VTy. respectively.
(f) is sub-Gaussian with parameter Mi
( that satisfies
2())) 2
(15)00) 2 = 1
(8) 2
(1)
2 + ))
Sj (1)
(1) 2 S x
o
1
+
(2)
n2
since 2z-1, Wj. and V. are independent. Using that 11-1 we have that
(8)
55
(4)
and the definition of K.
(1)
2
(i)
2
(1)
2
(()
11
(0)
2 S
1
3
88
(1)
1
87
dz (1)
R²
(
(
nJ
8 (1)
2
-1
(1)
<
1
x2
1
+
d2(1) (1)
8
(16)
(t)
(1)
(1)
8)
(1)
(0, (0))
1 $7
2
(1) +
R²
5j
where (16) is obtained using the second recursion in (
The inequality in (15) is obtained using the union bound together with the Chernoff bound (concen-
tration inequality) [1| for the random variables z-((()
(4) that are sub-Gaussian with parameter 115" (i)
Now, we prove by induction that, for any j. 87 100 S M/ /nz" where the ESSs satisfy n; = 721
| loo
and n. 2 ny + n 1o
for 2 For j = 1, using the definition of sj in the
15

---

second recursion in ( we have that for any component
(s)
71
$1
2
M
0
Then, vector 81 satisfies
M
M
Il
ST
R1
If V1lys
15-111000
S M/
then we have that for any component
(0)
1
1
1
1
1
n1 +
$
(8)
$j-1
d (9)
(2)
M1
+
d2(()
M2
de(c)
5-
"
M
1
M
d
by using the second recursion in (6) and the induction hypothesis. Then, vector 8j satisfies
M
(17)
n + カーー
The inequality in 8 is obtained because the minimax risk bounded by the smallest minimax risk shown in 24 25 30 that
R(U))
S R3 + (11T)- - 1l + 1loo)
(4)
that leads to using
15 and the fact that S 2 log (mm
D Proof of Theorem
Proof. To obtain bound in proceed by induction. For 1, using the expression for the ESS in (8, we have that
ni n2 2 n. 9 holds for the (j 1) ttak,, then for the j-th task, we have that
n 2 n, + nーー
n + 11-- n = n
1 + nd
where the second inequality is obtained because ny n. ||ا 1ml0 I 1, and || S d. Using that
2ラー1 2 n (1 a(1+a)= 3ta
(1+a)2 8 -1-0 the ESS of the j-th task satisfies
nj 2 n 1+ (1aly-
+ nd
= n
1+
a(1+a 340
(1o,) 15 2-1 + ndfa
14 al1-aa33
11
14 (11+a))--3-0
(18)
a²
(1+a)--
a+1
(1 a 2
= n 11 a(1 +a)) ala + 1) + a2 + a3--22 a2
where (8) is obtained because ndl o² क+ं since nd
un
(1++ nd +
Now, we obtain bounds for the ESS if nd f In the following, the constant á represents the golden ratio o 1.618
16

---

nd < 5
nd S a I Vnd & 9 1
because a
nd
( nise +1) =
2
ndd 1nd nd
then we have that "j" satisfies
a(2) 1 "j 2 n 1+ a a 1) ) = (1 1
2j 3j--2
2 (2 -
where the first inequality follows because (1+a) 1+ a+a - 2). Using a S g. we have that
2
2
2 n 1 1 1
ny 2 1 2+ 92j
1
2 - 26
1+
E
More efficient recursions for forward and backward learning
The Rauch- Tunhh--Tun--niin Sttrieell smoother recursions 34 allow to obtain forward and backward mean and MSE vectors directly from those vectors for the succeeding task. Specifically, for each j-th task, the mean vector = together with the MSE vector s7th can be obtained using those vectors for the succeeding task =k j+1+ j+1 as
3
=k (+t1
TJ)
8
+
-1
1 8j
1
d
8, + d;
j+1
The above recursions provide the same mean vector estimate as the recursions in (T)) in the pa- per since they are obtained using the Rauch-Tuse Tung--ttriel smoother recursions [34].
Stricbel smoother recursions instead of fixed-lag
F Proof of Theorem 3
Proof. To obtain bound in we first prove that the mean vector estimate and the MSE vector given by (IO) satisfy
PP
Th (1)
7 s kg/ / 20 log
2m
2 (1 (1-6)
(19)
for any component i = 1.2....,a
m. Then, we prove that ||s 1lo I M/ n for j E
|| |
(1, where the ESSs satisfy ni ny and nith nj + nj+1
" 1
for j 2 2.
To obtain inequality 19). prove that each component 2, mn of the enror in the mean
vector estimate 2) (i) = ppo(1) ( lub-Gaussian with parameter 77 x+ < KVy sy/sJat =(()
Analogously to the proof of [ is proven that each component the error of the backward
mean vector T is sub-Gaussian with parameters satisfying n N /// The error in the forward and backward mean vector estimate is given
2 r00(0) 75 174(0) =r5 (()(1) T3
T (()
T-, (1)
89
(6)
+ 8 j+1
+ ++
(
17

---

where the second equality is obtained using the recursion for x- in 10)
Adding and subtracting
(9)
(1)
5+1
we have that
(4)
(()
7.00 (1)
T (1)
1j+1 Tj (1)
(()
2)
2/
(1)
k (1)
+ d3
(6)
[+1
+
j+1
3+1
81 (1)
= 2j (1)
(700(()
(0)))
-
-j41 - 13 (0)
(1)
$j (8) + 0341 k (X)
+ +d3
(6)
+
j+1
5+1
since w = 700 5-1 and 2j (1) r300 Tj
Then, we have that
07 (i)
2j x0)
2j (1) (i)
33
(1)
+ W j++ 2
(2)
(1)
)
(20)
$7 (i) 9341 (1)
+ +dz+1
(1)
57 (1)
$1 (6)
1
3/ (1)
(w(()
(ijt1 - -2+11
(1)
8j (1) + 8+1
k (1) + +dt11
(i)
8j
(1)
+
j+1 + d (1)
k (2)
( 2j+1 (1) and w are sub-Gaussian with parameters ni (1) S kk (8), n (1) S
where 2
"V 8541 and (w)) ) respectively. Since 27, . and w,+1 are independent, we have that
25 2 given by 20 is sub-Gaussian with parameter that satisfies
11 k 2
(1)
()5(0) (i) 2
1
57 (1)
(4)
d3
(1)
j+1
J+1
8 (1)
σ [w) (1)
+ (n==t(10)
8j (0)
k (1)
d2
(3)
8 8+1
$j (1)
1
2
8j (1)
(1)
$7 (1) k (8)
(1)
+ J+1
5j (1)
x²2 (dit1 (5) + 9541 9 (9)
87 (1)
k (4)
dz
(1)
1+1
Using the second recursion in (10) we have that the nub-Gaussian parameter satisfies
x (
2
(n)))())) 1
1
1
k2
34+1
(4)
+
d2
3+1
(4)
k()
8j41
(+(+)
+ J+1
d2 (1)
x2
(6)
+ d2
(6)
1+
k
+ d3
(1)
x2 x207/(1)
(4)
541 J+1
(5x(00)
2
x2 x200
8 + d= (2)
The inequality in (9) is obtained using the union bound together with the Chernoff bound (con- centration inequality) 31 for the random variables 2516(() that are sub-Gaussian with parameter
18

---

Now, we prove that, for any j. 11 | S M/ /j where the ESSs satisfy ni "gg and
|
3 2 ny + o "7+i o
for j 2 2. Analogously to the proof of Theorem I we prove that the backward MSE vector 83+1 k
satisfies
|V S M/ n Then, using that
yl 87till I M/ V nJ+1 we have that for every component
(15m(()) -1
n2
(3)
8) 8 (6)
de
(1)
2
M12 s+1
+
d?
(1)
j+1
j+1
j+1
M
n
de +1 M
Z
M
+
1
n
2541
10
Then, we obtain
M
11
k
1000
(21)
12
The inequality in is obtained because the minimax risk is bounded by the smallest minimax risk shown in 24 25 30
that
R(U
- R5 + (11T) 1 + ||2 1loo) || |1,
that leads to using
19
21 and the fact that S /2 22og 2mm
G Proof of Theorem
Proof. To obtain bound 12 we use the ESS obtained with forward learning Theorem 2 and obtained with backward learning. Analogously to the proof of Theorem 2 we prove that the ESS obtained backward learning satisfies
(1
(1 22((
n 1i+1
1
|
j+l bl + n 2+
a(1 + a))
Therefore, the ESS obtained with forward an backward learning satisfies
n 2 n + 1 (1 + a) 111-)1111--1111-- (1+ n 11 ((
(1+a)
-1
allta)atr 30
1+
a(1 + a ((6-))))))1111 a
ndf
= n + (1 (1+ (1+
a²
[ (1
az 2(k 2
1+
a(l 2(k +a
a+1
a(1 + a ())(6-))--11
where the second equality follows because nd have that
since a = nd²
(V 4
not + 1). Then, we
?
(1 a))k-)))))))
nj 2nj + nl a(1+ +a
(11 2( + +
2(k- ) 110 +1)
(a + (1
2nj" + (1 [1 -
a(1 + 2)-) (1+1)(1+ (1+ +1
Now, we obtain bounds for the ESS depending on the value value nd2. Such bounds are obtained similarly as in Theorem 2 and we also denote by ó the golden ratio 1.618...
19

---

1. If nd? < x + vnd <a I vnd
S & 1
because
+
nd.
+ 1
ndd + 4 + v
Vnd
nd
nd
2
2
then we have that ny satisfies
1
- j)) a
b: j
k j
nj - 2 + n n a2 -j = "j + +1 1 + aak j]
2 11
+ +
1 2 (h: j)
where the first inequality follows because (1 + a) a))((k-))))))))))) second inequality obtained using a S y.
+ a(2(k: - j) 1) and the
2. 3 S nd < + S v vo S a S Vnd Φ because
+ +1
nd ndd + 4 + V v
nd?
nd?
2
2
then we have that n satisfies
(1 + (1+ -1 12 (1 + nd) 2((--1) 1) - n a (1 + /nd ) +1
n k n a))
where the second inequality follows because the ESS is monotonically increasing for a and a 2 ndf. Since (1 + Vnd2 ((kk))( 2 + nd (k- and k- jj 1, we have that
n
nd
1
2 nn
2 nj
+ n
a Vnd
1 + vnd
because a S Vndé
3. If nn 21 21 nd S a S nd& because a = nd V
1+ ndz
then we have that nit
satisfies
12
1 13
n5 22( +1 2 n3 + n
nd2 Φ5
where the first inequality follows because the ESS is monotonically increasing for and a 2 1 and the second inequality is obtained using k- - j 2 and a S nd&
H
Additional numerical results and implementation details
In this section we describe the datasets used for the numerical results Section we provide further details for the numerical experimentations carried out, and include several additional results. Specif- ically, in the first set of additional results, we evaluate the classification performance of the proposed method in comparison with state-of-the-art techniques for different sample sizes; in the second set of additional results, we further show the performance improvement leveraging information from all the tasks in the sequence with additional datasets; in the third set of additional results, we show the classification error and the running time of IMRCs for different hyper- parameter values; and in the fourth set of additional results, independent and zero-mean In addition, in the folder Implementation Litereennttiio__MRRRGG IMRC in the supplementary materials we provide the code of the proposed IMRCs with the setting used in the numerical results.
evaluate the assumption of change between tasks being
In Section 5 we use 12 publicly available datasets [ 37, 36 39 10.
2] and http:://yan The summary of these datasets is provided in Table 3 that shows the
lecun. com/ exdb/mnist. number of classes, the number of samples, and the number of tasks. In the following, we further describe the tasks and the time-dependency of each dataset used.
20

---

degrees where The "Yearbook" dataset contains portraits' photographs over time and the goal is to predict males and females. Each task corresponds portraits from one year from 1905 2013.
The "ImageNet noise" dataset contains images with increasing noise over tasks and the goal is to predict an image is a bird or a snake. The sequence tasks corresponds to the noise factors [0.0, 0.4, 0.8, 1.2, 1.6, 2.0, 2.8, 2.2, 3.6, [35].
The "DomainNet" dataset contains six different domains with decreasing realism and the goal to predict if an image is an airplane, bus, ambulance, or police car. The sequence of tasks corresponds to the six domains: real, painting, infograph, clipart, sketch, and quickdraw.
The "UTKFaces" dataset contains face images in the wild with increasing age and the goal is to predict males and females. The sequence of tasks corresponds to face images with different ages from 0 to 1 116 years.
The "Rotated MNIST" dataset contains rotated images with increasing angles over tasks and the goal is to predict if the number in an image is greater than 5 or not. Each j-th task
corresponds to rotation angle randomly selected from 1801 1) 1801
j E (1.2..... and k is the number of tasks.
The "CLEAR" dataset contains images with a natural temporal evolution of visual concepts and the goal is to predict if an image is soccer, hockey, racing. Each task corresponds to one year from 2004 to 2014.
The "Power Supply" dataset contains three year power supply records from 1995 to 1998 and the goal is to predict which hour the current power supply belongs to. We relabel into binary classification according to pm. or am. as [0].
The "Usenet" dataset is splitted into Usenetl and Usenet2 which both contains stream of messages from different 20 newsgroups that are sequentially presented to a user and the goal is to predict the personal interests.
The "German" dataset contains information about people who take credit by a bank and the goal is classify each person as good or bad credit risks.
The "Spam" dataset contains emails and the task is to predict if an email is malicious spam email or legitimate email.
The "Covertype" dataset contains cartographic variables of forest area obtained from US Forest Service (USFS) and the goal is to predict the forest cover type.
The samples in each task are randomly splitted in 100 samples for test and the rest of the samples for training. The samples used for training in the numerical results are randomly sampled from each group of training samples in each repetition.
we compare the results of IMRC methods with state-of-thh- -het-tttteee-t---ehiuuus (5. 6 9 10 66. In the following, we briefly describe each method used.
In Section
GEM method [5] is a technique developed for continual learning. The method provided by Lopez-Paz & Ranzato learns each new task using stochastic gradient descent with inequality constraints given by the losses of preceding tasks. Such constraints avoid the increase of the loss of each preceding tasks.
MER method [7] is technique developed for continual learning. The method provided by Riemer al. learns each new task using sample sample sets that include random samples of preceding tasks. Such samples of preceding tasks are stored a memory buffer.
ELLA method [4] a techniques developed for continual learning. The method provided by Ruvolo & Faton learns each new task transferring knowledge from shared basis of task models.
EWC method [6] is technique developed for continual learning. The method provided by Kirkpatrick et al. learns each new task regularizing the loss with regularization parameters given by the Fisher information.
Condor method [9] is technique developed for concept drift adaptation. The method provided by Zhao al. an ensemble method that adapts to evolving tasks by learning weighting the models in the ensemble at each time step.
21

---

Table Datasets characteristics.
Dataset
Classes
Samples
Tasks
Yearbook W1
2
37,921
126
ImageNet Noise [35]
2
12,000
10
DomainNet [36]
4
6,256
6
UTKFace [37]
2
23,500
94
Rotated MNIST 33
2
70,000
60
CLEAR [39]
3
10,490
Power Supply [10]
2
29,928
Usenetl [40]
2
1,500
5
Usenet2 440
2
1,500
5
German 41
2
1,000
3
Spam 2
2
6,213
20
Covertype [10]
2
581,012
1,936
Single-task
Forward
0.42
Forward and backward
Clasiileation croor/iingle- Jo-taak
Forward
Forward backward
Classification error
0.8-
Forward 10
Forward and hackward 10
Forward 100
03
Forward and backward 100
Nomber of tasks
Sumple size
(a) Classification error per number of tasks using "Do- (b) Classification error per sample size using "Do- mainNet" dataset.
mainNet" datasct.
Figure 5: Forward and backward learning can sharply boost performance and ESS as tasks arrive.
DriftSurf method 10 is technique developed for concept drift adaptation. The method adapts evolving tasks by using a drift detection method.
provided by Tahmasbi Such method allows to restart new model when change in the distribution is detected.
AUE method [16] is a technique developed for concept drift adaptation. The method pro- vided by Brzezinski & Stefanowski is ensemble method that adapts to evolving tasks by incrementally updating all classifiers in the ensemble and weighting them with non-linear error functions.
The classifier parameters in the numerical results are obtained using an accelerated subgradient method based Nesterov approach [32] (3).. Such subgradient method applied optimization (3) obtains at each step classifier parameters μu from the mean and confidence vectors т, X using the iterations for I 1.2....,
all + 1) = u()) + al (T - Asign(((()))
(22)
4al 1) p((+ 01+ 1) (m(1) -ū(())
where sign(-) denotes the sign function, uu() is the 1-th iterate for μ., 0: 2/(l + 1) and = 1/(1 1)3/2 are the step sizes and (p)((())) denotes subgradient of up-)) ull) with
Eyec ((x y)
((4)
max CEX,CC)
C
In addition, the above subgradient method is implemented using 2000 iterations and a warm- start that initializes the classifier parameters in (2) with the solution obtained for the closest task.
22

---

Table 4: Classification error and standard deviation of the proposed IMRC method in comparison with existing techniques for n = 50 samples per task.
Method
GEM
MER
ELLA
EWC
Condor
DriftSurf
AUE
IMRC
Yearbook
.16 -
.11 .01
.43 .10
=
.11 .02
.29 002
+
.10 .02
noise
.16 .66
.10 011
.47 .05
=
.10 1 .22
.48 02
.10 4 .02
DomainNet
.65 +
.29 .02
.67
.75 +
.45 .01
.32 .0
+32
.28 + .03
UTKFacee
.12 - .00
.11 .09
.18
.12
.14 .02
.12 .0
.12
.10 .00
R. MNIST
.29 + .04
.13
.48 +05
444
.4
.48 .02
.48 +22
.25 + .02
CLEAR
.08 + .01
.09 .04
+60
644
.35 .01
.3 00
+30
.05 + .02
P. Supply
.47 17 .03
.47 .02
.35
.47 02
.36 .11
.4 01
.40 100
.28 + .01
Usenetl
.47 .00
.66 .22
32
.48 02
.45 .2
.39 .01
.39 :00
.30 + 001
Usenet2
.35 .01
.32 .22
.22 32 .01
42 05
.35 02
.27 = .01
.30 :01
.32 32 .01
German
.34
.3 01
31 11 .01
.30 + 01
.3
.00 = .01
.30 +.1
.28 .01
Spam
.09 .02
.23
=
.1
.32
.33
.08
Covert.
.09 1
.11 11.01
02
00
.08
Table 5: Classification error and standard deviation of the proposed IMRC method in comparison with the existing techniques for samples per
Method
GEM
MER
ELLA
EWC
Condor
DriftSuff
AUE
IMRC
Yearbook
.17 .03
.10 .01
.43 = .02
.27 .06
.09 .01
.27 + .02
.27 .01
.08 :: .02
1. noise
.13+ .07
.10 .01
.47 + .04
.46 + .06
.09 .01
.48 + .02
.48 = .02
.09 + .01
DomainNet
.53 .10
.26 + .04
.67 = .05
.74 .05
.44 .00
.32 .0
.32 = .00
.28 + .01
UTKFaaes
.12. .00
.11 +:01
.17 +111
.12 .00
.11 = .01
.12 .00
.12 + .00
.10 .00
R. MNIST
.28 + .02
.45 +
.47 + .05
.40 .01
.41 = .01
.48 + .02
.48 .02
.21 + .00
CLEAR
.09 + .02
.05 02
60 + .5
62 04
.3 .01
.33 .0
.34 .00
.05 + .02
Supply
.47 .02
.48
.37
.46 00
.6 .00
.37
.38 .02
.25 :
Usenetl
.02
.46 464.00
.35
.7
40
.01
.30 ::
Usenet2
:
.35
.35
32 .22
+
.02
.30
German
.3 .01
29.
29 .01
.0 01
30 001
.29 .0
.32 001
.29 1 .00
Spam
.07 + .01
.08 +.1
.26 05
.17 ,2
.10 .02
.32
.3 .01
.08 + .00
Covert.
.08 = .00
.08 000
.11
00
.08 + 00
.07 02
.09 +
.09 00
.08 + .00
Table 6: Classification error and standard deviation of the proposed IMRC method in comparison with the existing techniques for 150 samples per task.
Method
GEM
MER
ELLA
EWC
Condor
DriftSurf
AUE
IMRC
Yearbook
.16 + .03
.10 .01
43 + .08
.22 + .02
.09 .01
.23 + .01
.23 + .01
.08 + .01
I. noise
.12 - .03
.07 + 001
.47 + .04
.45 + .07
.09 + 001
.48 = .02
.48 : .22
.08 001
DomainNet
.49 + .10
.28 + .02
.67 .05
.74 + .05
.43 01
.32 + .00
.32 .00
.27 .02
UTKFaces
.12
.11 .01
.17
-
01
.12 .0
.20
.10 .00
MNIST
.27 1:
.47 .05
+
.41 02
.02
+
.20
CLEAR
.08 4:
.05 .02
.60 .04
.60 =
.36 01
.33 .00
.33 .00
.04 .01
P. Supply
.47
.48 .02
.0 .01
.47 01
.6 01
36 .0
.36 01
.24 .00
Usenetl
.4 .02
.1 .03
.29
.88 -0
43 02
.39 + 00
+39
.29 +
Usenet2
344.00
.29 .00
261
.22 .11
.24 02
.6 00
.28 384000
.31 31 00
German
.30 .00
.25
.30 + 02
+1+000
.99 .01
+
.28
Spam
.07 + .01
.07
23
.13 02
11 02
.2 .11
.3
.07 + 00
Covert.
.08 + .00
.08 00
.10
.08 + 00
.07 02
.09 00
.08 .00
23

---

Thik
Step
Step
Seep
(a) Single task.
(b) Forward.
(c) Forward and backward.
Figure 6: Forward and backward learning improve performance of preceding tasks.
Table 7: Classification error of the proposed IMRC method varying W and b.
Harareearameter
W =
W
b
4
b=
Sample size
10
100
10
100
10
100
10
100
10
100
10
100
100
10
100
Yearbook
.13
.08
.13
.09
.13
.09
.14
.10
.09
.14
.13
.08
.13
.08
.13
.08
ImageNet noise
.15
.15
.08
DomainNet
.34
.28
.32
.27
.33
.28
.66
.29
.35
.28
.34
.28
.34
.28
.34
.28
UTKFaces
.10
.10
.10
.10
.10
.10
.10
.10
.10
.10
.10
.10
Rotated MIIST
.36
.21
.35
21
36
36
.22
36
.36
.21
.36
.21
.36
.21
CLEAR
.09
.05
.09
.05
.09
.06
.10
.05
.09
.05
.09
.05
.09
.05
.08
.05
Weather
.31
311
.31
.31
.31
Power Supply
.30
25
300
.55
.30
.25
.32
.27
.1
.26
.30
.25
.30
.25
.30
.25
Usenetl
.32
.30
.33
.32
.30
.32
.30
.32
.30
Usenet2
.33
.30
.34
311
.34
.31
.34
.30
.33
.30
.33
.30
.33
.30
.32
.30
German
.34
.29
.34
.29
.34
.29
.34
.29
.29
.29
.34
.29
.34
.29
Spam
.13
.08
.14
.08
.13
.08
.14
.13
.13
.08
.07
.07
Covertype
.08
.08
.08
.08
.08
.08
.08
.08
.08
.08
.08
.08
.08
.08
.08
.08
In the first set of additional results, we further compare the classification error of IMRCs with the state-of-the-art techniques. The results in Table ① in the paper as well Tables S and are obtained computing the classification error 50 times for each sample size. Table [ in the paper shows classification errors for n 10 samples, while Tables error for = 50, ble [ the performance improvement IMRCs comparison with state-of-the-arr techniques for n = 50, n 100, and = 150 is similar to that shown in the paper for = 10.
and G show the classificatinn 150 samples, respectively. As can be observed in Ta-
100, and
In the second set of additional results, further illustrate the relationship among classification eгror, number of tasks, and sample size. Figure 4 in the paper as well as Figure S are obtained computing the classification error over all the sequences of consecutive tasks of length in the dataset. Then, we repeat such experiment 10 times with randomly chosen training sets of size Figure extends extendss the results for IMRCs using "DomainNet" dataset completing those in the main paper that show the results using "Yearbook" dataset. Figure 5a shows the classification error of IMRC method divided by the classification error of single-task learning for different number of tasks with n = 10 and IMRC method for different sample sizes with à: = tasks. Figures 55 (5 similar behavior to Figures 4a and 4b in the paper, respectively. In addition, Figure 6 shows the classification ervor of IMRCs per step and task with single-task learning, forward learning, and forward and backward learning using the "Ycarbook" dataset. Such figure shows that forward and backward learning can improve performance of preceding tasks, while forward learning and single task learning maintain the same performance over time.
100 sample sizes. In addition, Figure shows the classification eтror of
In the third set additional results, further assess the change in classification error and the running time of IMRCs varying the hyper-pant parameters. Table 7 shows the classification eтror of IMRCs varying the values of dyper-parameter for the window size W and the number of backward steps b, completing those in the paper that show the results for W = 2 and b 3. As shown in the table, the proposed IMRCs not require careful fine-tuning of hyper-parameterr and similar performances are obtained by using different values. In addition, Table shows the mean running

---

Table Running time of IMRC method in comparison with the -iatt-oo--hheaatt--cch--n--g -rchhheiuue.s
MER
Sample size a
16
100
10
100
10
100
10
100
10
100
10
100
10
100
10
100
10
100
Yeurbook
0,088
0.475
0.166
3.725
0.006
0.070
0.358
3,051
0.085
0.324
0.105
0.397
0.133
0.657
0.167
0.582
0.185
0.064
Imngeeeet
0.07
0.079
1.052
0.033
0.252
0.531
0.254
0.561
0.438
0.603
DonsiaNe:
0.005
0.00
0.06
0.900
0.054
0.865
0.018
0.155
0.518
8.463
0.543
8.933
0.542
9,514
0.539
9,509
0.571
9.921
UTKFaccs
0.127
5.58
2.346
Rotaed MNIST
0.180
1095
0.211
4.092
0.176
0.198
0.587
5.296
0.135
0.471
0.165
0.599
0.209
0.737
0.349
0.877
0.288
1.100
0.074
1.063
0.248
1.405
0.255
1.595
0.360
Power Supply
0.331
0.169
0.025
0.249
0.007
0.006
0.190
1.987
0.241
0.768
0.257
0.540
0.291
1,025
0.351
1.309
0.425
1.404
Usenel
0014
0.13
0.115
0.088
0.012
0.117
0.320
0.990
0.324
0.934
0.966
0.946
0.968
0.980
0.400
Usene12
0.012
0.113
0.117
1.194
1.218
0.322
1.772
0.002
0.009
0011
0.114
0.010
0.011
0.000
0.004
0.260
0.770
0.266
0.773
0.808
0.773
0.466
1.110
0.606
1.796
Spam
Covertype
1,084
3.124
2,194
6.451
0.057
0,080
2,201
6,438
0.139
0.585
0.166
0.697
0.211
0.850
0.244
1,005
0.278
1.15
Running time per taak
Rasminn time [H]
Regnniiig Time
002 16
Samjlle size
Number
80
Number tasks
Yearbook dataset
(b) Yearbook dataset for 10
(c) Yearbook dataset for 100
Figure 7: Running time per task varying the sample size, the number of tasks, and the number of backward steps.
time per task in seconds of IMRCs for b = ........ 5 backward steps in comparison with the state- of-the-art techniques that learn sequence of tasks. Such table shows that the methods proposed for backward learning do not require significant increase in complexity. and the running time of the proposed method is similar to that of other ofate-ofthhe-ar methods. Figure Z further assesses the running time of IMRCs for b = 1, 2, ...., 5 backward steps varying the sample size and the number of tasks. Such figure shows that the running time of IMRCs increases moderately and linearly with the number of backward steps and the number of tasks.
In the fourth set of additional results, we evaluate the assumption of change between tasks being independent and zero-mean by assessing the partial autocorrelation of mean vectors. In particular, the partial autocorrelation at any lag would be zero if tasks are i.i.d.; while the partial autocorrelation at lag is larger than zero if tasks satisfy the assumption of Section [2] Figure 8 shows the averaged partial autocorrelation of the mean vectors components +/- their standard deviations for different lags using "Yearbook" and "UTKFaces" datasets. Such figure shows partial autocorrelation clearly non-zero at lag 1 that reflects dependence between consecutive mean vectors, as described by the assumption of Section
Partil mltonns
Partial atiios
8.0
Lags
Lags
(a) "Yearbook" dataset
(b) "UTKFaces" dataset
Figure 8: Averaged partial autocorrelation of mean vectors components +/- their standard deviations.
25


Reviews:
[{"review_id": "0wtRY0jAYs", "reviewer": "Reviewer_qXgD", "summary": "Though class-incremental learning has been studied the most as a default setting for continual learning, task-incremental study could be crucial for other areas. This paper focuses particularly on the case where tasks being introduced over time are interrelated under specific conditions. Under the supervised learning framework, the task distributions $p_t$ (of instances and labels at any time t) are independent and identically distributed, which would be a strong and less-realistic condition. In contrast, this paper covers the case where the difference of two consecutive task distributions is independent, making the difference between two distant tasks have increasing variance over time. Then the authors propose Incremental Risk Minimization Classifier (IMRC) method that effectively leverage forward and backward learning algorithms, improving the performance against existing methods on various datasets, sample sizes, and the number of tasks. ", "questions": "(1)\tProviding comprehensive details about different tasks and their distinctive characteristics helps readers better understanding the contributions of the paper beyond the theoretical excitement. Formalizing the time-evolving task with an independence assumption on consecutive task difference sounds exceptional. It will be great to know how much this assumption is agreed and violated on individual tasks on experiments.\n\n(2)\tIn addition to (1), accessing real examples or qualitative explanations about hard cases (that were not successful in the previous approaches, but exceptionally successful with the current IMRC) will be useful. For example, it seems IMRC is distinguished notably from other algorithms on P. Supply, Usenet1, and Spam datasets. Understanding the rationale will be insightful.\n\n(3)\tMost importantly, run-time trade-off for doing backward process must be measured for making the provable guarantees practically effective. As the trade-off would change for different number of tasks and sample sizes, practitioners require better guidance.\n", "limitations": "No specific limitations are described or probed.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "(1)\tThe paper formally defines a non-trivial task-incremental learning setting whose assumption is more realistic than the earlier approach.\n\n(2)\tThe paper analytically shows performance guarantees and effective sample sizes as well as forward and backward learning algorithm.\n\n(3)\tThe paper addresses empirical improvement on multiple datasets against existing state-of-the-art algorithms.\n", "weaknesses": "(1)\tCurrent draft is rarely self-contained. Readers must read the appendix frequently. Minimally, having explanations about methods and datasets in Table 1 would significantly increase the readability.\n\n(2)\tRun-time trade-off of considering the backward (possibly per different sample sizes) are missing. \n\n(3)\tCharacteristics of each experimental dataset: how much they agree and disagree the independence assumption across consecutive task distributions are missing.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Explanations about methods and datasets**\n\nIn the final version of the paper, we will further describe the methods and datasets used in Table 1 to make the main paper more self-contained as suggested by the reviewer. Specifically, we will include the following comments on the datasets and methods.\n\nThe proposed method is evaluated using 12 public datasets composed by evolving tasks  [9, 1, 34–41]. Six datasets are formed by images with characteristics/quality/realism that change over time: tasks in the Yearbook dataset correspond to portraits from different years over more than a century; tasks in the ImageNet noise dataset correspond to images with increasing noise factors; tasks in the DomainNet dataset correspond to images with decreasing realism; tasks in the UTKFaces dataset correspond to face images with increasing ages; the Rotated MNIST dataset contains rotated images with increasing angles; and tasks in the CLEAR dataset correspond to images with a natural temporal evolution of visual concepts. The rest of the datasets are formed by streams of tabular data that are segmented by time: the Power Supply dataset contains power supply records over time; the Usenet datasets contain a stream of messages from different newsgroups that are sequentially presented to a user; the German dataset contains information of bank clients over time; the Spam dataset contains malicious and not malicious emails received over time; and the Covertype dataset contains cartographic information of a forest area over time. \n\nIn Section 5, we compare the results of IMRC methods with 7 state-of-the-art-techniques [4, 16, 3, 5, 8, 9, 15]: GEM method [4] is a technique developed for continual learning based on experience replay and learns each new task using a stochastic gradient descent with inequality constraints given by the losses of preceding tasks; MER method [16] is a technique developed for continual learning based on experience replay and learns each new task using sample sets that include stored samples from preceding tasks; EWC method [5] is a technique developed for continual learning based on regularization and learns each new task using regularization parameters based on the relevance for preceding tasks; ELLA method [3] is a technique developed for continual learning based on dynamic architectures and learns each new task transferring knowledge from a shared basis of task models; Condor method [8] is a technique developed for concept drift adaptation based on weight factors and adapts to evolving tasks by weighting the models in an ensemble at each time step; AUE method [15] is a technique developed for concept drift adaptation based on weight factors and adapts to evolving tasks by incrementally updating all classifiers in an ensemble and weighting them with non-linear error functions; and DriftSurf method [9] is a technique developed for concept drift adaptation based on sliding windows and adapts to evolving tasks by restarting the model when a change in the distribution is detected.\n\n**The assumption in the paper more accurate describes evolving tasks than the usual i.i.d. assumption**\n\nWe will show that the assumption in the paper can better describe datasets with evolving tasks than the usual i.i.d. assumption as described in the general response. Specifically, Figure 2 in the attached pdf shows the averaged partial autocorrelation of the mean vectors components +/- their standard deviations for different lags using Power Supply, Covertype, and R. MNIST datasets. Such results complement those using Yearbook and UTKFaces datasets presented in Figure 7 in the current Appendix G. Figure 7 in Appendix G and Figure 2 in the attached pdf clearly show that the paper's assumption better describes evolving tasks than the usual i.i.d. assumption. Note that in the i.i.d. case the partial autocorrelation at lag 1 would be 0, while such figures show a partial autocorrelation clearly non-zero at lag 1.\n\n**IMRCs are especially successful in Power Supply, Usenet1, and Spam datasets**\n\nAs the reviewer points out, IMRCs significantly improve performance in comparison with other algorithms on Power Supply, Usenet1, and Spam datasets. Such datasets are used as benchmarks in concept drift adaptation [9, 39, 41]  and have a markedly strong similarity between consecutive tasks. As described in the first response, the Power Supply dataset contains power supply records over time; the Usenet1 dataset contains a stream of messages from different news-groups that are sequentially presented to a user; and the Spam dataset contains malicious and not malicious emails received over time. Existing techniques designed for continual learning do not account for evolving tasks, and existing techniques designed for concept drift adaptation do not exploit backward learning. IMRCs are successful in the datasets cited by the reviewer because the methods proposed account for evolving tasks and effectively exploit forward and backward learning.\n\n**Running times for different backward steps, number of tasks, and sample sizes**\n\nThe running time of IMRCs increases moderately with the number of backward steps and the number of tasks as described in the general response. Figures 1(a) and 1(d) in the attached pdf show the average running time per task for different numbers of backward steps and sample sizes using Yearbook and Spam datasets; and Figures 1(b), 1(c), 1(e), and 1(f) in the attached pdf show the running time for different numbers of backward steps, number of tasks, and sample sizes $n = 10$ and $n = 100$ using Yearbook and Spam datasets. Such results complement those presented in Table 6 in the current Appendix G. These results and the analysis in Section 4.2 show that the complexity of IMRCs increases linearly with the number of backward steps and the number of tasks. "}, {"review_id": "H6Xuvt9tHn", "reviewer": "Reviewer_3qiG", "summary": "The papers studies a specific case of continual learning over a sequence of tasks. Authors extend the typical i.i.d. assumption of task meta-distribution to the case where only the differences between subsequent task distributions are assumed to be independent and zero-mean. Under this assumption, they devise two versions of a minimax risk classifier and prove performance guarantees that improve upon single-task bounds by relying on effective sample size instead of just the number of samples in a task. The effective sample size is no smaller than the single task size and can be larger if the quadratic change between consecutive tasks behaves in a favorable way, e.g. decreasing over time. The authors also present an experimental study of the proposed algorithms and show that it either improves the baseline performance or achieves similar one across 12 datasets.", "questions": "The following things would help with the presentation:\n* The notations used are overloaded (e.g. by using double superscripts)  and sometimes are hard to follow. The paper would benefit from a small table with all notations in one place.\n* Experiments present the result for samples size of 10 without any additional comments on exact value of 10. Appendix shows that the general conclusion is valid irrespective of the sample size, so it would be good to highlight that.\n* The main assumption on the task distribution needs to be made more precise and explicit in the theorems (introduce assumptions separately and then refer to it in theorems). A discussion on how realistic it is and providing more than one example would go a long way.\n* Theoretical analysis needs a discussion on different regimes where the ESS improvements would be realised and what they mean for the task distributions process. Authors do have a short discussion of that after Theorem 4, but it lacks the connection between different regimes of nd^2 and process properties. For example, $nd^2 \\leq \\frac{1}{j^2}$ translates into a rather fast convergence requirement of the task distribution process.\n* It would be great to discuss what happens to the algorithm when the main assumption breaks. Does it go back to single task performance? How would one figure this out in practice?", "limitations": "The limitation of the approach are not adequantly discussed. I’ve made a few suggestion in the questions section on how to address that.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "### Originality\nThis is a novel approach that relies on independent differences between subsequent task distributions rather than on the typical i.i.d. assumption.\n\n### Quality\n* Paper studies the presented algorithm theoretically and experimentally.\n* Illustrative theoretical guarantees that are always no worse than a single task with a clear influence of the task distribution properties in the form of effective sample size.\n* Experiments uses 12 different datasets and cover 7 baselines.\n* Authors provide insights into impact of number of tasks and number of samples on the performance of different variants of the algorithm.\n\n### Clarity\nThe paper is well written and easy to follow in general. \n\n### Significance\nThere are numerous ways of how i.i.d. assumption can be relaxed and paper studies one of them. The significance will rely on how close the new assumption is to practical scenarios. From experimental setup it seems to be a rather specific case that relies too much on exact task ordering, thus I would expect the paper to have average impact from theoretical point of view, but quite limited impact in practice.", "weaknesses": "The paper doesn’t have major weaknesses. There are things that can be improved in the presentation and discussing limitations, which I cover in questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Table with main notations used in the paper**\n\nIn the final version of the paper we will include Table 2 in the attached pdf that shows the main notations used. Specifically, such table shows the notation used for the mean vector, the confidence vector, the MSE vector, the ESS, the uncertainty set, and the minimax risk. In addition, symbols without superscript represent variables obtained using single task learning; symbols with right harpoon superscript represent variables obtained using forward learning; symbols with left harpoon superscript represent variables obtained using backward learning; and symbols with right left harpoon superscript represent variables obtained using forward and backward learning. Due to space constraints, we will include the table in the appendices and will reference it in the Notation paragraph.\n\n**IMRCs are successful irrespective of the sample size**\n\nWe will follow the reviewer's suggestion and highlight that the improved performance of IMRCs compared to the state-of-the-art techniques is similar irrespective of the sample size. We will clarify that the results for $n = 10$ samples per task in Table 1 in the main paper are complemented with results for $n = 50, 100$, and $150$ samples per task in Tables 4, 5, and 6 in Appendix G. These results show that the improved performance of IMRCs compared to the state-of-the-art techniques is similar for different sample sizes.\n\n**More formally describe the paper's assumption and reference to it in theorems**\n\nWe will follow the reviewer's suggestion and more formally describe the assumption in Section 2, as follows. Most existing continual learning techniques are designed for tasks characterized by distributions $\\mathrm{p}_1, \\mathrm{p}_2, ...$ such that the tasks’ distributions $\\mathrm{p}_i$ are independent and identically distributed (i.i.d.) for $i = 1, 2, ...$. In the following, we propose techniques designed for evolving tasks that are characterized by distributions $\\mathrm{p}_1, \\mathrm{p}_2, ...$ such that the changes between consecutive distributions $\\mathrm{p}\\_{i+1} - \\mathrm{p}_i$ are independent and zero-mean for $i = 1, 2, ..$. In addition, we will refer to such assumption as the ''evolving tasks assumption'' in Section 2 and in theorems.\n\n**Suitability of the assumption in the paper for evolving tasks and additional examples**\n\nThe assumption in the paper describes scenarios in which the underlying distributions change as a random walk with independent increments. This type of assumption is often used to describe processes such as stock prices. The assumption in the paper can better describe real-world datasets with evolving tasks than the usual i.i.d. assumption, as described in the general response and shown in Figure 7 in the current Appendix G and Figure 2 in the attached pdf. We will also include other example of evolving tasks in the introduction and describe the evolving aspect of the datasets used in the experimentations, as follows.\n\nExamples of evolving tasks are the classification of portraits from different time periods [1] and the classification of spam emails over time [41]; in these problems, the similarity between consecutive tasks (portraits of consecutive time periods and emails from consecutive years) is significantly higher. \n\nThe proposed method is evaluated using 12 datasets composed by evolving tasks  [9, 1, 34–41]. Six datasets are formed by images with characteristics/quality/realism that change over time: tasks in the Yearbook dataset correspond to portraits from different years over more than a century; tasks in the ImageNet noise dataset correspond to images with increasing noise factors; tasks in the DomainNet dataset correspond to images with decreasing realism; tasks in the UTKFaces dataset correspond to face images with increasing ages; the Rotated MNIST dataset contains rotated images with increasing angles; and tasks in the CLEAR dataset correspond to images with a natural temporal evolution of visual concepts. The rest of the datasets are formed by streams of tabular data that are segmented by time: the Power Supply dataset contains power supply records over time; the Usenet datasets contain a stream of messages from different newsgroups that are sequentially presented to a user; the German dataset contains information of bank clients over time; the Spam dataset contains malicious and not malicious emails received over time; and the Covertype dataset contains cartographic information of a forest area over time. \n\n**Discussion on regimes of the ESS improvements**\n\nIn the updated version of the paper we will further discuss the regimes of the ESS improvements shown in Theorem 4 and Figure 3, as follows. The increase in ESS can be classified into three regimes depending on the relationship between the task index $j$, the sample size $n$, and the expected quadratic change $d^2$. The ESS becomes proportional to the total number of tasks $k$ if $nd^2$ is rather small (very small sample sizes or very slow changes in the distribution); the ESS quickly increases when $nd^2$ becomes small (reduced sample sizes and moderate changes in the distribution); and the ESS is only marginaly larger than the sample size for sizeble values of $nd^2$ (large samples sizes or drastic changes in the distribution).\n\n**IMRCs' behavior when the similarity between consecutive tasks is small**\n\nIMRCs are designed for situations where consecutive tasks are significantly more similar and the expected quadratic change ($d^2$) between consecutive tasks is small. If, instead, this expected quadratic change is large we would have that the forward and forward and backward mean vectors in equations (6) and (10), respectively, become the mean vector of single task learning, as hinted by the reviewer. Such cases can be detected in practice because the estimate for $d^2$ in equation (7) would become large. Then, in these cases, the performance of IMRCs becomes the performance of single task learning. "}, {"review_id": "uEAwSe3qRG", "reviewer": "Reviewer_V6pS", "summary": "This paper presents a novel method to tackle continual learning, called IMRCs which is able to exploit forward and backward learning to account for evolving tasks. The authors provide theoretical guarantees on the performance of IMRCs in terms of the tasks' expected quadratic change and the number of tasks. Authors compared the proposed method with prior work on multiple datasets, sample sizes, and number of tasks.", "questions": "- Authors mention they used the original hyper parameters for the baseline. But given that some methods such as MER, GEM, EWC which were introduced on image data, cannot be taken as is and applied to tabular datasets without tuning hyper parameters. How did the authors make sure of a fair comparison? Note that results for some methods such as GEM and MER are somewhat equal to those from EWC (Table 1) but in vision applications this is not expected and EWC is always outperformed by every single memory-based method.", "limitations": "No.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+  The idea seems interesting and performance guarantee in the context of continual learning is a promising research direction. \n+ A thorough theoretical analysis of IMRCs is provided.", "weaknesses": "- My main concern about this paper is the experimental section. The diversity of the datasets and experiments with different sample sizes is a plus but at the same time it is different from the common continual learning setting in the literature and the baselines are outdated whereas the field of continual learning is rapidly growing and there has been numerous works developed between 2021 and now. \n\n- The paper does not discuss the computational complexity of IMRCs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Computational complexity of IMRCs**\n\nIn the final version we will further discuss the computational complexity of IMRCs, the running time for different number of backward steps and number of tasks, and the running time in comparison with the state-of-the-art methods, as described in the general response. \n\n**Scope of the paper and experimental comparisons with the rapidly growing set of algorithms for continual learning**\n\nAs the reviewer points out, the field of continual learning is rapidly growing. This paper aims to present methodological contributions that enable to effectively exploit forward and backward learning and account for evolving tasks. The proposed IMRCs determine classification rules minimizing worst-case error probabilities over uncertainty sets that can contain the sequence of evolving underlying distributions. Specifically, we propose forward learning techniques that recursively use the information from preceding tasks to reduce the uncertainty set of the last task, and we propose forward and backward learning techniques that use the information from the last task to further reduce the sequence of uncertainty sets obtained with forward learning. In addition, we describe the performance guarantees of the methods introduced and analytically characterize the increase in ESS provided by the presented methods in terms of the expected quadratic change between consecutive tasks and the number of tasks. The main contributions in the paper are in terms of new methodological approaches and theoretical analysis of the methods presented. The paper also includes sizeable experimental results with multiple datasets and baseline methods, but an exhaustive experimental comparison that include the most recent techniques is beyond the scope of the paper.\n\nThe existing techniques for concept drift adaptation are designed for evolving tasks but only aim to learn the last task in the sequence, while the existing techniques for continual learning aim to learn the whole sequence of tasks but are designed for situations where tasks’ similarities do not depend on the time steps when tasks are observed. The methodology proposed fills this gap in the existing literature and present techniques that simultaneously learn a sequence of tasks and account for evolving tasks.\n\n**Hyper-parameters for the baselines and comparison methods**\n\nAs described above, the main goal of the paper is to present methodological contributions that enable to learn a sequence of evolving tasks; rather than improving performance in comparison with the most recent state-of-the-art methods in each specific dataset. While hyper-parameter fine-tuning is a crucial step in achieving the best possible results, it often involves a significant amount of computational resources and extensive experimentation. Given the focus on methodological contribution, we demonstrate the effectiveness of the techniques introduced by using default hyper-parameters for all datasets, methods, and sample sizes. \n\nEWC is outperformed by GEM and MER in most of vision datasets such as Yearbook, I. noise, DomainNet, R. MNIST, and CLEAR datasets. For the tabular datasets, results for GEM and MER are somewhat equal to those from EWC. This fact can be due to the strong similarity between consecutive tasks in later datasets that have been often used as benchmarks for concept drift adaptation. Note that GEM, MER, and EWC are designed for situations where tasks’ similarities do not depend on the time steps when tasks are observed so that their performance is expected to be similarly deficient in situations where the tasks' similarities between consecutive tasks are markedly higher. "}, {"review_id": "UCD9eqJMqR", "reviewer": "Reviewer_spbD", "summary": "IMRCs (Incremental Minimax Risk Classifiers) are a technique for incremental learning of a growing sequence of classification tasks. The key feature of IMRCs is their ability to exploit the similarity between consecutive tasks by leveraging both forward and backward learning.\nForward learning utilizes information from preceding tasks to improve the classification performance of the current task. It recursively updates the mean and mean squared error (MSE) vectors by considering the difference between the current task and the preceding task. Backward learning, on the other hand, uses information from the current task to improve the classification performance of preceding tasks.", "questions": "See weakness part.", "limitations": "N/A", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) IMRCs leverage the evolving nature of tasks in a growing sequence. By utilizing both forward and backward learning, IMRCs effectively exploit the similarity between consecutive tasks. \n\n(2) By leveraging information from preceding and succeeding tasks, IMRCs can incorporate additional knowledge and enhance classification performance.\n\n(3) IMRCs minimize the worst-case error probabilities over uncertainty sets. This means that they provide robust classification performance, even in the face of uncertainty or variations in the underlying distributions of tasks.", "weaknesses": "(1) The forward and backward learning processes, along with the uncertainty set updates, can require significant computational resources and time. How about the training time compared to other methods?\n\n(2) The selection of appropriate uncertainty sets can be challenging and may require prior knowledge or assumptions about the task distributions. \n\n(3)  The authors assume that the distributional changes between tasks (p2-p1, p3-p2, ...) are independent and have a mean of 0. How can IMRCs be extended or modified to handle scenarios with non-zero-mean changes between consecutive tasks or explore novel tasks outside the existing sequence?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Complexity of IMRCs and running time in comparison with other methods and for different backward steps**\n\nIn the final version of the paper, we will show that the running time of IMRCs is similar to other state-of-the-art techniques and increases moderately with the number of backward steps and the number of tasks, as described in the general response. Figures 1(a) and 1(d) in the attached pdf show the average running time per task for different number of backward steps and sample sizes using Yearbook and Spam datasets; and Figures 1(b), 1(c), 1(e), and 1(f) in the attached pdf show the running time for different number of backward steps, number of tasks, and sample sizes $n = 10$ and $n = 100$ using Yearbook and Spam datasets. Such figures complement those presented in Table 6 in the current Appendix G. These results show that the complexity of IMRCs increases linearly with the number of backward steps and the number of tasks in agreement with the analysis in Section 4.2.\n\n**The assumption in the paper is not stronger than the usual i.i.d. assumption**\n\nIn this paper, we develop techniques designed for evolving tasks that can be mathematically modeled assuming that the changes between consecutive distributions $\\mathrm{p}_{2} - \\mathrm{p}_1, \\mathrm{p}_3 - \\mathrm{p}_2, \\ldots$ are independent and zero-mean. Specifically, the assumption in the paper describes scenarios in which the underlying distributions change as a random walk with independent increments, so that it can more accurately describe evolving tasks. For instance, such type of assumption is often used to describe processes such as stock prices. The assumption in the paper differs from the usual i.i.d. assumption but is not necessarily stronger. The main difference between both assumptions is that with the random walk assumption each difference between consecutive distributions is independent of the others, while with the i.i.d. assumption each distribution $\\mathrm{p}_i$ is independent of the others.\n\n**Mean of changes between consecutive distributions**\n\nIMRCs can be modified to handle scenarios with non-zero-mean changes between consecutive distributions. If $m_j$ is the mean of the change between the $j$-th and the $(j-1)$-th task, then the mean vectors evolve over time steps through the linear dynamical system\n$$\\boldsymbol{\\tau}_j^\\infty = \\boldsymbol{\\tau}\\_{j-1}^\\infty + \\boldsymbol{w}_j$$ where vectors $\\boldsymbol{w}_j$ for $j \\in \\{2, 3, \\ldots, k\\}$ are independent and mean $m_j$. Then, we can obtain recursions for mean and MSE vectors after some algebra from the Kalman filter recursions and fixed-lag smoother recursions. Such recursions are given by the recursions in the paper subtracting the expectation of changes between consecutive distributions.\n\nIMRCs can be used in scenarios with an ever-increasing sequence of tasks. For each new task in the sequence, IMRCs obtain mean and MSE vectors for the new task using forward learning recursions, and then obtain mean and MSE vectors for each task in the sequence using forward and backward learning recursions. "}, {"review_id": "UEhYhevVXf", "reviewer": "Reviewer_C5UC", "summary": "This paper presents an incremental minimax risk classifier (imrc) to effectively utilize forward and reverse learning and explain evolutionary tasks. Furthermore, the performance improvements provided by forward and backward learning can also be described analytically based on the expected quadratic changes of the task and the number of tasks.", "questions": "1. The setting of the task in the article mainly starts from the high similarity continuous task, so whether the high similarity continuous learning has practical application, and whether this method can have a broad development prospect in the future technology development.\n2. In the article, it is necessary to more clearly describe the task premise, between the similarity in the similarity continuous learning and the evolution in the evolutionary tasks, and then describe the clarity and rationality, why the similar continuous tasks are more consistent with the evolutionary principles.\n3. In the article, I learned the role of positive learning and reverse learning in the experiment, but I want to know whether reverse learning alone is feasible, whether positive learning has an inhibitory effect on reverse learning?\n4. In Figure 1 of the article, although the meaning of the expression can be roughly understood, the graph line is a little confused, especially the meaning of the black line is unclear.\n5. In Figure 2 of the article, the meaning of j in the first red square and k in the second red square is not clear, and the symbols introduced in the text in Article 4.2 are inconsistent with the flow chart symbols in Figure 2, which is easy to confuse the readers' memory.\n", "limitations": "see questions", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "In the article, the effects and limitations of IMRCs are verified by rich experiments, and using IMRCs can better use forward and reverse learning to explain the evolutionary tasks and improve the effective sample size.", "weaknesses": "However, there are some deficiencies in the ablation aspect, and the experimental volume is relatively small.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**The assumption in the paper can better describe datasets with evolving tasks than the usual i.i.d. assumption**\nThe paper's assumption describes scenarios in which the underlying distributions change as a random walk with independent increments. This type of assumption is often used to describe processes such as stock prices. The paper's assumption can better describe datasets with evolving tasks than the usual i.i.d. assumption, as described in the general response and shown in Figure 7 in Appendix G and Figure 2 in the attached pdf. We will also include other example of evolving tasks in the introduction and describe the evolving aspect of the datasets used in the experimentations, as follows. \n\nExamples of evolving tasks are the classification of portraits from different time periods [1] and of spam emails over time [41]; in these problems, the similarity between consecutive tasks (portraits and emails of consecutive time periods) is significantly higher. \n\nThe proposed method is evaluated using 12 datasets composed by evolving tasks. Six datasets are formed by images with characteristics that change over time: tasks in the Yearbook dataset correspond to portraits from different years over more than a century; tasks in the ImageNet noise dataset correspond to images with increasing noise factors; tasks in the DomainNet dataset correspond to images with decreasing realism; tasks in the UTKFaces dataset correspond to face images with increasing ages; the Rotated MNIST dataset contains rotated images with increasing angles; and tasks in the CLEAR dataset correspond to images with a natural temporal evolution of visual concepts. The rest of the datasets are formed by streams of tabular data that are segmented by time: the Power Supply dataset contains power supply records over time; the Usenet datasets contain a stream of messages from different newsgroups that are sequentially presented to a user; the German dataset contains information of bank clients over time; the Spam dataset contains malicious and not malicious emails received over time; and the Covertype dataset contains cartographic information of a forest area over time. \n\n**Feasibility of backward learning**\nThe proposed IMRC method allows to do backward learning alone since backward mean and MSE vectors are obtained recursively from those for the succeeding task. We obtain the backward mean and MSE vectors using forward learning recursions in retrodiction. These vectors could then be used to obtain IMRCs parameters solving the optimization problem (3). In addition, the backward ESS in Theorem 3 shows the performance improvement of the backward learning techniques. Such ESS shows that backward learning can achieve similar positive transfer as forward learning. Theorem 3 also shows that forward and backward learning results in higher ESS. Such qualitative consequences of the theoretical results are corroborated by the numerical results in Section 5 and Appendix G, for instance in Figures 4, 5, and 6. Such figures show the average classification error of single-task learning, forward learning, and forward and backward learning. Therefore, such results show that forward and backward learning improves performance in comparison with forward learning.\n\n**Additional explanations of Figure 1**\nFollowing the reviewer's suggestion, the updated caption of such figure will more clearly describe its contents, including the meaning of the black line. Figure~1 in the paper shows an example of evolving tasks and how the proposed techniques can adapt to evolving tasks and effectively exploit forward and backward learning. The example of evolving tasks is the classification of portraits from different decades; in this problem, the similarity between consecutive tasks is significantly higher. The black line in the figure represents the evolution of the underlying distributions that characterize different task (black dots). IMRCs minimize the worst-case error probability over uncertainty sets that can include the underlying distribution. For each task, the proposed methodology obtains a single task uncertainty set (blue hexagons) leveraging information only from the corresponding task (blue arrows), and a forward uncertainty set (green hexagons) from the forward uncertainty set for the preceding task (green arrows) and the single task uncertainty sets. Then, we obtain forward and backward uncertainty sets (red hexagons) from the forward and backward uncertainty sets for the succeeding tasks (red arrows) and the forward uncertainty sets. Such transfer of information significantly increases the ESS of each task that is represented by the size of the uncertainty set since decreasing uncertainty sets increases the ESS.\n\n**Additional explanations of symbols used in Figure 2**\nWe thank the Reviewer for finding out the typo of j in the first red square and k in the second red in Figure 2. We will fix it in the new version of the paper. In addition, we will clarify the symbols used in Figure 2 and in Section 4.2. Figure 2 in the paper depicts the flow diagram for the proposed IMRC methodology for each j-th task, while the text in Section 4.2 describes the procedure for the proposed IMRC methodology at each step k. The IMRC method obtains, for each j-th task, forward mean vector $\\tau_j^\\rightharpoonup$ leveraging information from preceding tasks and the sample average $\\tau_j$. Reciprocally, backward mean vectors $\\tau\\_{j+1}^{\\leftharpoondown k}$ for each j-th task are obtained leveraging information from the k-th task through the sample average $\\tau_k$. Then, the forward and backward mean vectors $\\tau_j^{\\rightleftharpoons k}$ are obtained from the forward mean vectors and the backward mean vectors. Note that the forward mean vector and sample average are obtained for each j-th task at step j. Then, at each step k, the IMRC method obtains forward mean vector for the k-th task and obtains the forward and backward mean vectors for each j-th task."}]

Author rebuttal:
In the responses below we are confident to have addressed all the comments and questions made by the reviewers. Please let us know if you have any additional inquiry so that we can completely clarify any aspect in the paper during the rebuttal period.

We plan to use the extra page allowed to clarify the questions raised by the reviewers as described in the responses below. In this general response, we clarify the two main questions raised by the reviewers regarding the running time of the methods proposed and the assumption for evolving tasks. 

**Running times in comparison with other methods and for different backward steps**

Table 6 in Appendix G and Table 1 in the attached pdf show that the running time of the IMRC method is similar to other state-of-the-art methods, and Table 6 in Appendix G and Figure 1 in the attached pdf show that the running time of IMRCs increases moderately with the number of backward steps. Specifically, Table 1 in the attached pdf shows the average running time per task of IMRCs in comparison with the state-of-the-art methods and Figure 1 in the attached pdf shows that the complexity increases linearly with the number of backward steps and the number of tasks. Such results complement those presented in Table 6 in the current Appendix G and agree with the theoretical analysis in Section 4.2. This analysis shows that, for $k$ steps, IMRCs have computational complexity $\mathcal{O}((b+1)Kmk)$ and memory complexity $\mathcal{O}((b+k)m)$ where $K$ is the number of iterations used for the convex optimization problem~(3), $m$ is the length of the feature vector, and $b$ is the number of backward steps.

**The assumption in the paper more accurate describes evolving tasks than the usual i.i.d. assumption**

Figure 7 in Appendix G and Figure 2 in the attached pdf show that the assumption in the paper can better describe datasets with evolving tasks than the usual i.i.d. assumption. We evaluate the paper's assumption of change between consecutive tasks being independent and zero-mean by assessing the partial autocorrelation of mean vectors. Partial autocorrelations are the usual tool to assess if a process is a random walk (see Section 4 in Cowpertwait and Andrew V. Metcalfe (2009)). In particular, the partial autocorrelation at any lag would be zero if tasks are i.i.d.; while the partial autocorrelation at lag 1 is larger than zero if tasks satisfy the assumption of Section 2. Figure 7 in the current Appendix G and Figure 2 in the attached pdf show the averaged partial autocorrelation of the mean vectors components +/- their standard deviations for different lags. Such figures show a partial autocorrelation clearly non-zero at lag 1 that reflects a dependence between consecutive mean vectors in accordance with the assumption of Section~2.

Paul SP Cowpertwait and Andrew V. Metcalfe. Introductory time series with R. Springer Science \& Business Media, 2009.

Meta-review: All reviewers found the work interesting and relevant. After the author’s response, the reviewers were mostly satisfied and did not see the need for further clarifications. Ultimately, all reviewers recommended acceptance.
Decision: Accept (poster)