Forward and Backward Lifelong Learning with Time-dependent Tasks
Authors: Veronica Alvarez
Santiago Mazuelas
Jose A. Lozano
Venue: Submitted to ICLR 2023 (2023)
Keywords: Lifelong learning
Continual learning
Supervised Classification
Performance Guarantees
Minimax risk classification

Abstract: For a sequence of classification tasks that arrive over time, lifelong learning methods can boost the effective sample size of each task by leveraging information from preceding and succeeding tasks (forward and backward learning). However, backward learning is often prone to a so-called catastrophic forgetting in which a task’s performance gets worse while trying to repeatedly incorporate information from succeeding tasks.  In addition, current lifelong learning techniques are designed for i.i.d. tasks and cannot capture the usual higher similarities between consecutive tasks. This paper presents lifelong learning methods based on minimax risk classifiers (LMRCs) that effectively exploit forward and backward learning and account for time-dependent tasks. In addition, we analytically characterize the increase in effective sample size provided by forward and backward learning in terms of  the tasks’ expected quadratic change. The experimental evaluation shows that LMRCs can result in a significant performance improvement, especially for reduced sample sizes. 

Under review as a conference paper at ICLR 2023
FORWARD AND BACKWARD LIFELONG LEARNING WITH TIME-DEPENDEN TASKS
Anonymous authors Paper under double-blind review
ABSTRACT
For sequence of classification tasks that arrive over time, lifelong learning methods can boost the effective sample size of each task by leveraging informa- tion from preceding and succeeding tasks (forward and backward learning). How- ever, backward learning is often prone to a so-called catastrophic forgetting in which task's 's performance gets worse while trying repeatedly incorporate in- formation from succeeding tasks. In addition, current lifelong learning techniques are designed for i.i.d. tasks and cannot capture the usual higher similarities be- tween consecutive tasks. This paper presents lifelong learning methods based on minimax risk classifiers (LMRCs) that effectively exploit forward and backward learning and account for iime-dependent tasks. In addition, we analytically char- acterize the increase in effective sample size provided by forward and backward learning in terms of the tasks' expected quadratic change. The experimental eval- uation shows that LMRCs can result a significant performance improvement, especially for reduced sample sizes.
INTRODUCTION
In practical scenarios, classification problems (tasks) often have limited sample sizes and arrive sequentially over time. Lifelong learning (also known as continual learning) can boost the effective sample size (ESS) of each task by leveraging information from preceding and succeeding tasks (forward and backward learning) (Ruvolo & Eaton, 2013 Lopez-Paz & Ranzato, 2017 Chen & Liu 2018). The general goal of such approaches is to replicate the humans' ability to continually improve the performance of each task exploiting information acquired from other tasks.
The development of lifelong learning techniques is hindered by the continuous arrival of samples from tasks characterized by different underlying distributions. In particular, backward learning (also known as reverse transfer) often prone to a so-called catastrophic forgetting in which a task's performance gets worse while trying to repeatedly incorporate information from the succeeding tasks (Kirkpatrick et all 2017: Hurtado et al. 22021: Henning et al. 2021h. More generally, lifelong learning methods face a so-called stability-llastiiity dilemma: the excessive usage of information from different tasks can result in a performance decrease while moderate usage does not fully exploit the potential of lifelong learning (Rolnick et al., 2019: Ke all 2021).
Most of lifelong learning techniques are designed for tasks sampled i.i.d. from task environment (Baxter 2000 Maurer et all, 2016 Denevi et all 2019). and current methods cannot capture the usual higher similarities between consecutive tasks. For sequence of tasks that arrive over time, it is common that the tasks are time-dependent and consecutive tasks are significantly more similar. For instance, if each task corresponds to the classification of portraits from a specific time period GGnosar et a 2015), the similarity between tasks markedly higher for consecutive tasks (see Figure []. In the current literature of lifelong learning, only PPentina & Lampert (2015) considers scenarios with time- dime-dependent tasks and analyzes the feasibility of transferring information from the preceding tasks. On the other hand, methods designed for concept drift adaptation (Zhao et all 22020
Tahmasbi et all 1202] Alvarez et all, 2022) account for time-dependent underlying distributions but
only aim to learn the last task in the sequence.
This paper presents lifelong learning methods based minimax risk classifiers (LMRCs). The pro- posed techniques effectively exploit forward and backward learning and account for time-dependent tasks. Specifically, the main contributions presented in the paper are follows.

---

Under review as a conference paper at ICLR 2023
Single-task learning
Forward learning
Forward and backward learning
1910
1970
1980
1990
2010
Female ?
Female
Female
Female
Female ? Male
? Male
Male
Male
Male
For tasks that arrive over time, consecutive tasks are often more similar. Forward and backward learning can exploit such similarities and extract information from preceding and succeding tasks.
Figure I:
The presented LMRCs minimize the worst-case error probabilities over uncertainty sets obtained using information from all the tasks.
We propose learning techniques that can effectively incorporate information from the ever- increasing sequence of tasks and provide performance guarantees for forward and back- ward learning.
We analytically characterize the increase in ESS provided by forward and backward learn- ing in terms of the expected quadratic change between consecutive tasks.
We numerically quantify the performance improvement provided by the presented learning techniques in comparison with existing methods using multiple datasets, different sample sizes, and number of tasks.
Notations Calligraphic letters represent sets; || ||a and || ll denote the 1-norm and the infinity norm of its argument, respectively; v and ih- denote vector inequalities; I[-} denotes the indicator function; and Ep(.) and (-rp(-} denote the expectation and the variance of its argument with respect distribution p. For vector v, e(() and TT denote the i-th component and the transpose of v. Non-linear operators acting on vectors denote component-wise operations. For instance, |v] and 2 denote the vector formed by the absolute value and the square of each component, respectively.
2 PRELIMINARIES
In the following, we denote by X' the set of instances or attributes, y the set of labels or classes, A(Y x y) the set of probability distributions over X' V, and T(X, )) the set of classification rules. A classification task is characterized by an underlying distribution p* E A(X x Y) and supervised classification methods use sample set D (11, = formed by n i.i.d samples from distribution p" to find a classification rule h E T(X.)) ))) with small expected loss p").
In lifelong learning, sample sets D1, Dz.... arrive over time steps 1, 2...... corresponding with dif- ferent classification tasks characterized by underlying distributions Pl, P1.P2.... At each time step k, lifelong learning methods aim to obtain classification rules h1, hh.,... li with small expected losses E(hi, Pi), ((22, p2),..., E(b,, P&)) for the current sequence of & tasks. For instance, overall performance is usually assessed by the averaged error Σ L(b;, P:). As depicted in Fig. M for each j-th task with E 21,2..... k}. lifelong learning methods obtain the classification rule hy leveraging information obtained from sample sets D1, D....., D.. (forward learning) and from sam- ple sets D,+1, D.. D2 (backward learning). Most existing lifelong learning techniques are designed for tasks characterized by distributions P1,P,,.. ... such that the tasks' distributions pt are independent and identically distributed (i.i.d.) random probability measures for i 1,2,... In the following, we propose lifelong learning techniques designed for iimeddepnndent tasks that are characterized by distributions P1, P2...... such that the changes between consecutive distributions P++1 Ps are independent and zero- mean random signed measures for i = 1, 1,2..... Such assump- tion account for usual higher similarities between consecutive tasks; for instance, it implies that
Pitt Pa is mero- random variable with Var Pi} Σj= Var - Pi+j-1) while
2

---

Under review as a conference paper at ICLR 2023
the i.id. case would imply that Pi+* p; is zero-mean random variable with Var(pat pi) Var [ar(P - pr} = 2Var(P1) for any t and i.
As described above, lifelong learning methods consider tasks characterized by different distribu- tions. The methods presented below are based on the framework of minimax risk classifiers (MRCs) (Mazuelas et all 2020 2022al since MRCs utilize general expectation estimates ob- tained from samples with different distributions. MRCs learn classification rules by minimizing the worst-case expected loss against an uncertainty that can include the underlying distribution with high probability. Such uncertainty sets are given by constraints on the expectation of a feature mapping X x + R
u (DEA(X x [ - }}
where denotes mean vector of expectation estimates and X denotes confidence vector. Fea- ture mappings are vector-valued functions over X' x y e.g., one-hot encodings of values from the last layers in neural network (Bengio et al. 2013 Kemker & Kanan, 2018 Mohri et all 2018 Hurtado et al. (202)).
Given the uncertainty set U, MRC rules are solutions of the optimization problem
R(U)=
min max E(h, p) hET(X.)) PEM
(2)
where R(()) denotes the minimax risk and E(h. p) denotes the expected loss of classification rule
h for distribution p. In the following, we utilize the 0-1-loss so that ((h, p) = Ep [I(h(x)) ) * y}}
and the expected loss with respect to the underlying distribution becomes the error probability of
the classification rule. Deterministic MRCs assign each instance arg max ((x, y) 4* where the parameter μ is the solution of the convex optimization problem
X' with the label h(x) e
Evec (x, v)
min 1- - 4 1
max xEA,CCy
|4|
[C|
given by the Lagrange dual of (
MRCs provide bounds for the error probability with respect to the minimax risk R(U) and the smallest minimax risk as described in Mazuelas al. (2020; 2022alb). The smallest minimax risk, denoted by R is the minimax risk corresponding to the ideal case of knowing mean vectors exactly, that is, 1200 the minimax risk corresponding with the uncertainty set oe (p E A(X x )) Ep (1r, = Ep- { (,t,, }) Such minimax risk coincides with the Bayes risk if the underlying distribution is the worst-case distribution uncertainty set given by the true expectation of feature mapping (Mazuclas et all (022s).. If the mean vector of expectation estimates is obtained using a sample set D formed by instance-labed pairs from the same underlying distribution, then the performance bounds of MRCs of the usual order O (1/vn) where is the sample size of D.
In lifelong learning, the baseline approach of single-tast task learning obtains a classification rule hy for nh each j-th task leveraging information only from the sample set D, = {(x).5. )) of size ny. In that case, LMRCs coincide with MRCs for standard supervised elassification that obtain the mean and confidence vectors as
S (Z),))55),
Xj- 3J 8j =j=07/n
o./mm,
T
T2
with a3 an estimate Varp; (ar, y)). e.g., the sample variance of the ny samples. The vector 8j describes the mean squared eиrors (MSEs) of the mean vector components and directly gives the confidence vector X, as shown in
In the following sections, we describe techniques that obtain the mean and MSE vectors using forward and backward learning. Once such vectors are obtained, LMRC methods take the con- fidence vector Xy as in (4) and obtain the classifier parameter μ, for each j-th task solving the convex optimization problem in (3) that can be efficiently addressed using conventional methods (Nesterov & Shikhman, 2015 Tao al. 2019).
3

---

Under review as a conference paper at ICLR 2023
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, characterizes the increase ESS provided by forward learning in terms of the tasks' expected quadratic change and the number of tasks.
3.1 FORWARD LEARNING
The proposed techniques for forward learning account for time-dependent tasks and obtain classifi- cation rules for each task leveraging information from preceding tasks. Let T and 8 denote the mean and MSE vectors for forward learning corresponding the j-th task for E [1, .... kj. The following recursions allow to obtain 5 and 83 for each j-th task using those vectors for the preceding task T 5- 85-1 as
Tj
(--1 -J)
(5)
87-1 + 8,
8j + 1
(6)
8j
8j-1 + d
with y, and 8, given by (4) and 71 Ti. 81 81.
The vector d; assesses the expected quadratic change between consecutive tasks. In the following, the change between consecutive tasks is described by w, 3 - for any {2, 3, ..... k} where 7, Ep, ( y)} is the expectation of the feature mapping with respect to the underlying distribution. If pı - Py-1 are independent and zero-meat for = 2, 3...., then vectors w are also independent and zero-mean for any feature mapping.
Taking d; [f [ [ - }) and of Varp. { (z,y}} for any i, the recursion in (5) provides the unbiased linear estimator of the mean vector T based on Dr. Dy..... D, that has the minimum MSE, while the recursion in (6) provides its MSE (see Appendix (or detailed derivation). Vectors of and df can be estimated online using the sample sets. In particular, of can be estimated as the sample variance, while df can be estimated using sample averages
W TH
d²
Σ (T
W
l=1
where in d1,..., iw are the W + closest indexes to i .k.
Recursions (5)-6) obtain mean and MSE vectors for the j-th task by acquiring information from the j-th sample set D, and retaining information from preceding tasks. Specifically, recursion (5) obtains the mean vector - by adding correction to the sample average ア. This correction is proportional to the difference between ; and J with a proportionality constant that depends on
the MSE vectors 8j -- and the expected quadratic change df. In particular, if 8 8- d. the mean vector is given by the sample average as in single-task learning, and if s, > $ $ d. the mean vector is given by that of the preceding task. Note that for forward learning, each step k. only the vectors for the last task Th and &5 need to be obtained from those of the (k- - 1)-th task. The vectors for the remaining j-th tasks with j E (1.2....,k 1} stay the same at step k (see also Fig. anddd Alg. [below).
3.2 PERFORMANCE GUARANTEES AND EFFECTIVE SAMPLE SIZES
The following result provides bounds for the minimax risk for each task with respect to the smallest minimax risk. For each j-th task, we denote by R the smallest minimax risk and by μ the classifier parameter that determines the optimal minimax rule, as described in Section In addition, we denote by R(U the minimax risk over uncertainty set U determined as in ( using the mean
and confidence vectors T and Xj / S5 provided by 5 and ④
4

---

Under review as a conference paper at ICLR 2023
Theorem 1. Let M and be such that M 2 [[ 8) v(r,y) E & x ) and
w
for j 1,2,........ k and i 2,2,..., .
where o3 denotes the r.v. given by the i-th component of the feature mapping of samples from the (0)
j-th task, (z) denotes the sub-Gaussian parameter of n.v. i... B(el(a-B(=h)) I (a(z))t/22 vt. For any j E {1, 2, ............ k.,, we have that
R(U)) S Rg M(x + y 2 log (2m/0)
|| with prob. at least 1 -
(8)
Vnj
| ||
with ni = =1 and nj 2 ny + n- o tn
for 2 2.
lldy
Proof. See Appendix B
The excess risk inequality decreases as (11 vnj using the forward learning methods pro- posed, while such difference would decrease as (1/ /nz)) using only the information of the j-th task. Therefore, n, in (8) is the ESS of the proposed LMRC method with forward learning. The ESS of each task is obtained by adding a fraction of the ESS for the preceding task to the sample
size. In particular, if d? is large, the ESS given by the sample size, while if de is small, the ESS is given by the sum of the sample size and the ESS of the preceding task.
Other existing methods provide comparable performance bounds (Mohri & Medina 2012 Pentina & Lampent 2015). Such bounds decrease with the number of tasks and increase with the change between consecutive distributions. Specifically, bounds in Proposition of Medina (2012) and in Theorem of Pentinna & Lamperi (2015) are proportional the discrepancy and to the Kullback-Leibler divergence between consecutive distributions. The bound in Manoreemmbboy decreases with the number of tasks and increases with the expected quadratic change de between consecutive distributions. Note that the coefficient ń. in (8) can be taken be small as lóng as the values used for oj and dj are not much lower than the sub-Gaussian parameters of o and wy, re- spectively. In particular, x is smaller than the maximum of M/ m } and 2M/ miny, (dd))) due to the bound for the sub-Gaussian parameter of bounded random variables (see e.g., Section 2. 1.2 in Wainwright (2199).
Theorem[[ the increase in ESS in terms of the ESS of the preceding task. The following result allows to directly quantify the ESS terms of the sample size and the expected quadratic change.
Theorem 2. Let d, o and n be such that d2 2 ||d]] so: || bl 1, and n S n, for j 1,2, k. For any j {1, 2, ..., k:), we have that the ESS in & can be taken so that it satisfies
(1 + 2j-1
2
n
1+
with
(9)
a(l a(1+a)i-11+
nd
In particular, for j 2 2, we have that
j
n 2
+
if
nd
3
j
1
1
nj 2
1+
if
<
nd
<
5v
jz
n 2
1+
if
nd 2 1.
3nd
Proof. See Appendix C
The above theorem characterizes the increase 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 (9) and becomes proportional to j when the expected quadratic change is smaller than 1 1/(22). bellow further illustrates the increase in ESS with respect to the sample size (nz² /n) due forward learning in comparison with forward and backward learning.
5

---

Under review as a conference paper at ICLR 2023
4 FORWARD AND BACKWARD 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 and acquiring information from succeeding tasks. In addition, it characterizes the increase 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, for each task, the sequence of succeeding tasks ever-increasing due the continuous arrival of tasks, while the sequence of preceding tasks is always the same. The repeated usage of information from the succeeding tasks can result a so-called catastrophic forgetting in which the tasks' performance gets worse over time. The techniques proposed below for backward learning effectively increase the ESS over time by carefully accounting for the new information at each step.
4.1 FORWARD AND BACKWARD LEARNING
The proposed techniques for forward and backward learning account for time-dependent tasks and obtain classification rules for each task leveraging information from preceding and succeeding tasks. From preceding tasks, we obtain the forward mean and MSE vectors T .8 using recursions (5) (6. while from succeeding tasks, we obtain the backward mean and MSE vectors ; ,; using recursions
55) G in retrodiction. Specifically, vectors T and $; are obtained using the same recursion as for -J and 87" in 5 6 with $774 d and rz instead of $5 dr. and -5-1-
Let Tet and sj denote the mean and MSE vectors for forward and backward learning correspond- ing to the j-th task for j E {1, .... kj. The following recursions allow to obtain, at each step k, the mean and MSE vectors ; *k and sj for each j-th task using those vectors for forward learning T ,885" and backward learning T j+1 35
T 58
S and
Jj
(T - TT))
(10)
8 + 8 k
j+1
J+1
1
8) *
(11)
8j
8J + dz J+1
with =3. Ta and 8) 8k. Analogously the case of forward learning in Section 3.1 taking
df = R(w?] and of Varp. ( (ar, y)} for any i, the recursion in (IC) provides the unbiased
linear estimator of the mean vector 7 based on D1, D2,.... D, and Djt1,Dj+2.0 D2 that has the minimum MSE, while the recursion in 11 provides its MSE (see Appendix for detailed derivation).
obtain at step the mean and MSE vectors for the j-th task by retaining information from preceding tasks and acquiring information from succeeding tasks. Specifically, recursion (T0) obtains the mean vector - by adding a correction to mean vector of the corre- sponding task ; obtained for forward learning. This correction is proportional to the difference between Tj and T with proportionality constant that depends on the MSE vectors sj $374 and the expected quadratic change d-+1- In particular, if sj < 8741 1
Recursions
+ di the mean vector is given by that of the corresponding task for forward learning, and if 8y > 8 8f + d2 the mean vector is given by that of the succeeding task for backward learning.
4.2
IMPLEMENTATION
This section describes the implementation of the proposed LMRCs with forward and backward learning and its computational and memory complexities.
Figure 2 depicts the flow diagram for the proposed LMRC methodology. The proposed techniques carefully avoid the repeated usage of the same information from the sequence of succeeding tasks.

---

Under review as a conference paper at ICLR 2023
At each step k, new backward mean vectors Ti+i for j = k k 2...; k - are ob- tained for b backward steps, then the forward and backward mean vectors - given by (IO) obtained from the forward mean vectors Tj and the backward mean vectors JH+1- In particular, Tj provides the information from
Tj
T +++1
the preceding tasks 1, .. while T T pro- vides the information from the succeeding tasks j + J + .,....
Figure 2: Diagram for LMRC methodology.
Algorithm I details the implementation of the proposed LMRCs at each step. For & steps, LMRCs have computational complexity O((6 + (1(6+1))mm 1)kmk) and memory complexity ( + k)m) where K the number of iterations used for the convex optimization problem ( is the length of the feature vector, and b is the number of backward steps. In particular. if b O. LMRC carries out only forward learning. The complexity of forward and backward learning increases proportionally 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-Stree StrieSt recursions (see e-g.. Section 7.2 in Anderson & Moore (1979) that can obtain ] from T j+1 as shown in Appendix D
the
Algorithm LMRC at step 1:
Input: D3 from new task and T 8j. T
83 for l: b < & from previous b 1 steps
Output:
M4 for k- - b S S. k, Tk, 8k: Tk
Obtain sample average and MSE vectors Th Tk, s:
8 using the sample set Dę
b Single-task
Estimate the tasks' expected quadratic change di using 7
Obtain the forward mean and MSE vectors Rx 8% using 5
6
b Forward
Take A / and obtain classifier parameter μ4 solving the optimization problem 3 for j = k 1, k ...... - do
Estimate the tasks' expected quadratic change df using 7
Obtain backward mean and MSE vectors T7+1. 87 using
in retrodiction
> Backward
Obtain mean and MSE vectors T .5 using 10
> Forward and backward
Take X1
and obtain classifier parameters μe, solving the optimization problem 3 /5
4.3
PERFORMANCE GUARANTEES AND EFFECTIVE SAMPLE SIZES
The following result provides bounds for the minimax risk for each task with respect to the smallest minimax risk. For each j-th task and step k we denote by R(U5*) the minimax risk over uncer-
tainty set U determined as in (I using the mean and confidence vector T and X provided by 10 and
Theorem 3. Let M, K, and n.j" be in Theorem 1 For any j E (1,2, k), we have that
RiU S RT + M(K + 1)2² 2 log (2m/0)
|| || with prob. at least 8 (12)
nn
|| 10
with m=* = n and n 2 n + nj+1
for j S k - 1, where the backward
|afflse
n
|
ESSs satisfy ni ny and n. 2 ný + mith
To
Proof. See Appendix
To the best of our knowledge, Theorem provides the first performance guarantees for lifelong learning that show positive backward transfer. In particular, the bounds for forward and backward learning provided by inequality (12) are significantly lower than those for forward learning in The- orem II The ESS of each task is obtained by adding a fraction of the ESS for the succeeding task to the ESS of the corresponding task using forward learning. In particular, if de is large, the ESS is given by that with forward learning, while if d? is small, the ESS is given by the sum of the ESS using forward learning and the ESS of the succeeding task.
7

---

Under review as a conference paper at ICLR 2023
Theorem Theoreemsshows the increase in ESS in terms of the ESS with forward learning and the ESS of the succeeding task. The following result allows to directly quantify the ESS in terms of the sample size and the expected quadratic change.
Theorem Let d, y and n be such that d2 2
||
2o. ||o
ac S 1, and n S ny for 1, 2, ... k.
For any j {1, k,,.. we have that the ESS in can be taken so that satisfies
...,
n5 2 1+ (1 (1+a)
a (((4))++1 1 a
with a
ax1 +
a(1 + ())(k-)))+
1 + nd
(13)
In particular, for 2 2, we have that
j(k 5)
] -
j(k -5)
1
Bj 2 nj
2
1+
if
nd
j + 2(k - 5)
j + 2(k - -)
nj n5t 2 ni + 5V d2
n
2 n
1+ 2
if
1
< nd
<
5v
j
n 2 nj
+
2 n
1+
if
nd 2
3d
3nd
Proof. See Appendix
The above theorem characterizes the increase in and backward learning in terms of the tasks' Such increase grows monotonically with the number of preceding tasks j and with the num- ber of succeeding tasks k j as shown in (I3). In addition, it becomes proportional to the total number of tasks l when the expected quadratic change is smaller than 1/(j2n) and 2 k/2. Figure further illustrates the increase in ESS with respect to the sample size (m5**/m) /n) due to forward and backward learning in compari- son with forward learning. Such figure displays the three intervals that are discussed in Theo- rems 2 and 4 In particular, the ESS signifi- cantly increases when nd2 decreases between 1 and 1/j². Note also that in most of the sit- uations, the benefits of backward learning are steps.
ESS provided by
forward change.
expected quadratic
100
13 /
220
1110
20
- n nioo
/
ESSh
10
1100
100 //2
1o //2
10
nd
achieved using only b = k j = 3 backward
Figure 3: ESS increase provided by forward and back- ward lcarning.
5 NUMERICAL RESULTS
This section first compares the classification performance of LMRCss with state-of-the-art techniques using multiple datasets, then we show the performance improvement of the presented LMRC's due forward and backward learning. In the supplementary materials, we provide the code for LMRCs together with additional implementation details and numerical results in Appendix
The proposed method is evaluated using public datasets: "Yearbook" (Ginosar et al. 2015). "Im- ageNet noise" (Mai et al. (2022), "UTKFaces" (Zhang et al.. 2017), "Rotated MNIST" (Jin et all 2021), "DomainNet" (Peng et all, 2019), and "CLEAR" (Lin et al., (2021). These datasets are composed by time-dependent tasks (images with characteristies(uullyyreeee time). The last two datasets are multi-class problems and the rest are binary (see further details in Appendix G.. For all methods, instances are represented by pixel values in "Rotated "NIST" dataset, and by the last layer of the ResNet18 pre-trained network (He et all 2016) in the re- maining datasets. The proposed LMRC method is compared with 4 lifelong learning techniques: gradient episodic memory (GEM) (Lopez-Paz Ranzato, (011)), meta-experience replay (MER) (Riemer et all (018),, efficient lifelong learning algorithm (ELLA) (Ruvolo & Eaton 2013), and elastic weight consolidation (EWC) (Kirkpatrick et all 2017). The hyper-parametery in these meth- ods are set to the default values provided by the authors. LMRCs are implemented using b
that change over
8

---

Under review as a conference paper at ICLR 2023
Table 1: Classification error and standard deviation of the proposed LMRC method in comparison with the state-of-the-ard techniques.
Damaset
Yeurbook
ImageNet
DomiinNe
UTKiaces
Retated MNNST
CLEAR
10
100
100
10
100
10
100
10
100
10
100
39
33
MER
16 03
100 + 01
17 27..005
30 01
38 04
.26
17 09
11
37 = 09
45 10
.00
.85 + .12
45
48
67
-17+11
06
EWC
47 + 85
227 06
47
46 06
75 04
74
12 80
12 00
48 =
40
01
665
42 # .44
.3
13+ 03
28
.10 00
Forward n
Single-task
Forward backward e
Forward It 10
Classriictiion erooriingle tack
Forward 100
Forward and backward
Forward &
100
Forward and backward
100
Classfication ceror
*
Forward and backward 100
6.-
0.1
Number tasks
Sample
(a) Classification error per number of tasks "Yearbook" dataset.
(b) Classification error per sample size in "Year- book" dataset.
Figure Forward and backward learning can sharply boost performance and ESS as tasks arrive.
backward steps and the expected quadratic change d3 is estimated using W in 7 We use the same hyper-parameters for all the results in this section for fair comparison with the state-of-the-art and to show that the techniques presented do not require careful fine-tuning, In Appendix[G] among other additional results, we study the change in classification error and processing time achieved by varying the number b of backward steps.
In the first set of numerical results, we compare the performance of the proposed LMRCs with the state-of-the oo--th--rhrrr art techniques for 10 and 100 samples per task. These numerical results obtained computing the average classification error over all the tasks in 50 random instantiations of data samples. As be observed in Table LMRCs can significantly improve performance in dime-dependent tasks with respect to the state-of-the-arr
In the second set of numerical results, we analyze the contribution of forward and backward learn- ing to the final performance of LMRCs. 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 G for further details). Figure 4a shows the classification error of LMRC method divided by the classification error 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 performance as tasks arrive. In addition, Figure 4b the classification error of LMRC method for different sample sizes with k 10 and k 100 tasks. Such figure shows that forward and backward learning for &o = 100 tasks using n = 10 samples achieves significantly better results than single-tas task learning using 100 samples. In particular, the methods proposed can effectively exploit backward learning that results enhanced classification error all the experimental results.
6 CONCLUSION
The paper proposes LMRCs that effectively perform forward and backward learning and account for iimedeepedentt tasks. LMRCs carefully avoid the repeated usage of the same information from the ever-increasing sequence of succeeding tasks. In addition, the paper analytically characterizes the increase in ESS achieved by the proposed forward and backward learning techniques in terms of the tasks' expected quadratic change and number of tasks. The numerical results assess the performance improvement of LMRC methodology with respect the state-of-the-an using multiple datasets, sample sizes, and number of tasks. The proposed methodology for lifelong learning with time dependent tasks can lead to techniques that further approach the humans' ability to learn from few examples and to continuously improve on tasks that arrive over time.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Verónica Álvarez, Santiago Mazuelas, and Jose A Lozano. Minimax classification under concept drift with multidimensional adaptation and performance guarantees. International Conference on Machine Learning. 2022.
Brian DO Anderson and John B Moore. Optimal Filtering. Prentice- Hall, 1979.
Jonathan Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12: 149-198, 2000.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine ( 2013.
Christopher M Bishop. Puttern recognition and machine learning. Springer, 2006.
Zhiyuan Chen and Bing Liu. Lifelong machine learning. Morgan & Claypool Publishers, second edition, 2018.
Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil. Online-within-oling meta learning. Advances in Neural Information Processing Systems, 2019.
Shiry Ginosar, Kate Rakelly, Sarah Sachs, Brian Yin, and Alexei A Efros. A century of portraits: A visual historical record of american high school yearbooks. IEEE International Conference on Computer Vision Workshops, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. IEEE Conference on Computer Vision and Pattern Recognition, 2016.
Christian Hemning, Maria Cervera, Francesco D' Angelo, Johannes Von Oswald, Regina Traber, Ben- jamin Ehret, Seijin Kobayashi, Benjamin F Grewe, and João Sacramento. Posterior meta-replay for continual learning. Advances in Neural Information Processing Systems, 2021.
Julio Hurtado, Alain Raymond, and Alvaro Soto. Optimizing reusable knowledge for continual learning via metalearning. Advances in Neural Information Processing Systems, 2021.
Xisen Jin, Arka Sadhu, Junyi Du, and Xiang Ren. Gradient-based editing of memory examples for online task-free continual learning. Advances in Neural Information Processing Systems, 2021.
Zixuan Ke, Bing Liu, Nianzu Ma, Hu Xu, and Lei Shu. Achieving forgetting prevention and knowl- edge transfer continual learning. Advances in Neural Information Processing Systems, 2021.
Ronald Kemker and Christopher Kanan. Fearne:: Brain-inspired model for incremental learning.
International Conference Learning Representations, 2018.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwa Barwinska,nnnnnne et al. Overcom- ing catastrophic forgetting neural networks. Proceedings of the National Academy of Sciences, (13):3521-3526. 2017.
Zhiqiu Lin, Jia Shi, Deepak Pathak, and Deva Ramanan. The CLEAR benchmark: Continual learn- ing on real-world imagery. Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
David Lopez-Paz and Mare' Aurelio Ranzato. Gradient episodic memory for continual learning.
Advances in Neural Information Processing Systems, 2017.
Zheda Mai, Ruiwen Li, Jihwan Jeong, David Quispe. Hyunwoo Kim, and Scott Sanner. Online continual learning in image classification: An empirical survey. Neurocomputing, 469:28-51, 2022.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredess The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016.
10

---

Under review as a conference paper at ICLR 2023
Santiago Mazuelas, Andrea Zanoni, and Aritz Perez. Minimax classification with 0-1 loss and performance guarantees. Advances in Neural Information Processing Systems, 2020.
Santiago Mazuelas, Mauricio Romero, and Peter Grünwald. Minimax risk classifiers with 0-1 loss. arXiv preprint, arXiv:2201.06487 2022a.
Santiago Mazuelas, Yuan Shen, and Aritz Pérez. Generalized maximum entropy for supervised classification. IEEE Transactions Information Theoor, 68(4):2530-2550, 2022b.
Mehryar Mohri and Andres Munoz Medina. New analysis and algorithm for learning with drifting distributions. International Conference on Algorithmic Learning Theory, 2012.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar Foundations of machine learning. MIT press, 2018.
Yu Nesterov and Vladimir Shikhman. Quasi- muasi-monotone subgradient methods for nonsmooth convex minimization. Journal of Optimization Theory and Applications, 165(3):917-9400 2015.
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. IEEE International Conference on Computer Vision, 2019.
Anastasia Pentina and Christoph H Lampert. Lifelong learning with non-iid tasks. Advances in Neural Information Processing Systems, 2015.
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.
David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap, and Gregory Wayne. Experience replay for continual learning. Advances in Neural Information Processing Systems, 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. Ima- geNet large scale visual recognition challenge. International Journal of Computer Vision, (3): 21 211-252, 2015.
Paul Ruvolo and Eric Eaton. ELLA: An efficient lifelong learning algorithm. International Confer- ence on Machine Learning. 2013.
Ashraf Tahmasbi, Ellango Jothimurugesan, Srikanta Tirthapura, and Phillip B Gibbons. DriftSurf: stable-staterraactive-sttt learning under concept drift. International Conference Machine Learning, pp. 10064-10064, 2021.
Wei Tao, Zhisong Pan, Gaowei Wu, and Qing Tao. The strength of nesterov's extrapolation in the individual convergence of nonsmooth optimization. IEEE Transactions on Neural Networks and Learning Systems, 3177)2557-2268, 2019.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic von-aayymptoiicvvevpoon Cambridge Univer- sity Press, 2019.
Zhifei Zhang, Yang Song, and Hairong Qi. Age progression/regresion by conditional adversarial autoencoder. IEEE Conference on Computer Vision and Pattern Recognition, 2017.
Peng Zhao, Le-Wen Cai, and Zhi-Hua Zhou. Handling concept drift via model reuse. Machine Learning, 13333)-333-568, 2020.

---

Under review as a conference paper at ICLR 2023
A DERIVATION OF RECURSIONS (5) AND (6) FOR FORWARD LEARNING AND
RECURSIONS 10 AND I FOR FORWARD AND BACKWARD LEARNING
This section shows how recursions in S 66) and recursions in 10
11
are obtained using those
for filtering and smoothing in linear dynamical systems.
The mean vectors evolve over time steps through the linear dynamical system
7 + W
(14)
where, as described in Section 3.1 vectors ; for j (2. ..... k} are independent and zero-mean because Pj- -Pi-1 are independent and zero-mean. In addition, each state variable T is observed each step j through Tj that is the sample average of i.i.d. samples from Pj. so that we have
T Tj + U.
(15)
where By for j .I,k, Therefore, equations (14 and (15) above describe linear dynamical system (state-space model with white noise processes) (Bishon, 2006; Anderson & Moore, 1979. For such systems, the Kalman filter recursions provide the unbiased linear estimator with minimum MSE based on samples corresponding to preceding steps D1, ...... Dj. sions provide the unbiased linear estimator with minimum MSE hased on samples corresponding to preceding and succeeding steps D1, D2...., D₂ (Bishop, 2006, Anndrson & Moore, 1979). Then, equations ( (6) and equations TT. II are obtained after some algebra from the Kalman filter
(1,2...., k) are independent and zero mean, and independent of w, for
and fixed-lag smoother recur-
recursions and fixed-lag smoother recursions, respectively.
B PROOF OF THEOREM
Proof. To obtain bound in (8) we first prove that the mean vector estimate and the MSE vector given by 5 and (6, respectively, satisfy
|r oo (1)
(0)
S / 29, (1) log
2m
2 (1 - 8)
(16)
for any component i = 1,2...., m. Then, we prove that ||
87 10 30 I M/
for j E
||0
11
(1,2,...,Ae) k), where the ESS$ satisfy ni nı and nj" ný + + " | |0
mm for j 2.
||
To obtain inequality 16), we prove by induction that each component = ........ m of the error in
the mean vector estimate 2j 750(0) -T -T,(()
(1) is sub-Gaussian with parameter vy (1) ( < 15 8j
Firstly, for 1, we have that
( = 70 (1) (6) - . (1) = -p000 T(
(1)
Since the bounded random variable ক (i) is sub-Gaussian with parameter a (T (1) ), then the error in the mean vector estimate 2 -1) is sub-Gaussial with parameter that satisfies
11 (0) 2 o ( (1))))
(())
(1)
K
x²
Y11
2 (i) = - ( 7-1
(4) is sub-Gaussian with parameter 75 (1)
I RV 85-1
(3)
for any
i ..2. m. then using the recursions 5 and 6 we have that
29 - (1) Tj 7 TJ (6) 1
(4) + w
(2)
[--1 (8) 710))
(8)
(1)
d2(0)
T--1 (8) + +w/ - - (0)
(
J5= (6) 7/0)
+
(1) + 8j
+ d2(0)
j-11
7-- (6)
(
8
T--1 (1)
7--
12

---

Under review as a conference paper at ICLR 2023
since j T 3- If V3 = Tj
Tj the enror in the mean vector estimate is given by
2j (1)
= j-1
00
(1)
+ 3 7-
(8)
(
5j
(1)
+ 2 - (1)
(1)
7j-1
00
(0)
+ W
(8)
(1)
$
(
7--1
(2)
+ 3
(9
+ 1/
(1)
Tz-1 (0)
5 (1)
(1 (1-38
(1)
3 ( (1)
(0)
(1)
3--1
(c)
(1)
where w/th and of are sub-Gaussian with parameter a (u) (0) and a ( /00 / TTy. respectively, Therefore, we have that 25-(()
(1) is sub-Gaussian with parameter fl (i) that satisfies
② (1) 2
(1) 2 = -(1-- 5 (8) 2
(1 (1) + (1 11- Sj (1) 2
(
2
+
nj
since 23-1- Wj. and v. are independent. Using that 1zz we have that
(1)
S
Ri
85-1
(6)
and the definition of
2
115
(1)
1
R
2
j-1
(1)
+
1
8
2 20)
+
(3)
$f
1
(1)
2
2
1
+ 26)
88
(1)
(17)
(i)
$j $7
(1)
8, (K)
(1)
(1)
(55 (1)
5j
K
+
where 117 is obtained using
6
The inequality in (66 obtained using the union bound together with the Chernoff bound (concen-
tration inequality) (Wainwright, 2019) for the random variables 2/- (i) that are sub- Gaussian with
parameter ny (i)
Now, we prove by induction that, for any j. |V 8 100 S M/ / where the ESSs satisfy ni"
and nj" 2 nj + 15-1 + aen--llddl- for j 2 2. For j = 1, using the definition of 87 in
equation ( we have that for any component
$1 (0)
= (1(1)
-1
n1
71
o
(1)
M
Then, vector " satisfies
M
M
Il 8
M
If I1 Vo 00 S M/
then we have that for any component
(5 ())
-1
1
1
1
1
1
1
n2
+
$
(3)
$ $--1
2
M2
+
de
M
(2
1
A
1
1
M
d
[
13

---

Under review as a conference paper at ICLR 2023
by using the recursion (6 and the induction hypothesis. Then, vector s
satisfies
M
(18)
00
nJ + n
+ dd
The inequality in 88) is obtained because the minimax risk is bounded by the smallest minimax risk as shown in (azueeas et al. 2020: (2022 so that
R(455) - R3 + (I1T)- - 112 120) |155
that leads to 8 using 16 18 and the fact that 1 S 2 2loog (m
C PROOF OF THEOREM 2
Proof. To obtain bound in we proceed by induction. For 1, using the expression for the ESS in ( we have that
11
2
If p holds for the (j 1) -task, then for the j-th task, we have that
| 00
nj" 2 ny + n- | "デー
n + 1 n 1
11
1 n
+ ndd
Rj-1
where the second inequality is obtained because nj 2 n, [|0 I 1, and |d] I d. Using that
(1+a)))-3-1-4 the ESS of the j-th task satisfies
nー-1 2 a[I+a]==-54a
nj 2 n
+ nd?
n
a(1+a)25 225-022-- 340 ndl (1+a)5-4-
1+ (1 (1 all -o
(19)
a(1+a)2)-3-0 a²
(1+a]0
a+l
(1 + 2) -1
n 1 a(1 2- aaa + 1) + a2 + a)--22-00 a3
where 19 is obtained because nd since a
nd 2
nd + +1). (V1
a+i
Now, we obtain bounds for the ESS depending on the value of nd? In the following, the constant represents the golden ratio @ 1.618
1. If ndl < < Vnd S a S Vndao S < similarly as in the previous case, then have that ni satisfies
1+ 2 a(2j 1) ) =
a(2) a(2)-
n
1+
a2 a [22)
2 a(2j 1)
where the first inequality follows because (1 21+-) have that
2/-2 > 1 + a(2 2). Using
G. we
2j
2j
1 j -
n 2 n
+
2 n
1 1+
N n
2 5
[2j
1)
2 +
26
1+
14

---

Under review as a conference paper at ICLR 2023
2. If S ndf
< 1 =1 < vnd < < Vnd because a nd²
2 (V1+ m +1)
V nd v //ne444
2
+4
then we have that nij satisfies
2
1 (1 21+ vnd @ (1 (1+a) (1+ 2 n 1+
(1 + 2)20 1 Vnd Φ (1 + 3)2
nj 2 n 1+
where the first inequality follows because a < v Vnd and the second incquality follows because the expression is monotonically increasing for a and J a. Since (1 + )
1 1 2j-2 we have that
11 Vnd Φ
ny 2 (1+
1+
2 n 1+
V nd Φ2 2 + 25-2
because j 2.
3. If nd 21 +15 nd S a S nd& because a = nd that nj" satisfies
(V1+ nas + 1).
then we have
2
1 (1 (1+1)3-1-110
1 (1+a)8)-31
nj 2 1+
mdZ
(1 (1+a)2)-1
n
1+
nd (1+a)
where the first inequality follows because a S nd& o and the second inequality follows multiplying and dividing by + a and because 1/(1+ +a) < Since the above expression is monotonically increasing for a and a 2 1, we have that
"
(1 1+
nd 22) 220-2+1
1 22)-2 221-2-11
(
1
3 nd Φ
1
because j 2.
D MORE EFFICIENT RECURSIONS FOR FORWARD AND BACKWARD LEARNING
The Rauch-Ti Rauch-Tung- Tung-Striehb smoother recursions Bishop 2006 Anderson & Moore, 1979 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 T together with the MSE vector s) k can be obtained using those vectors for the succeeding task T 7++ 8741
Tj +
-++1-T7
8j + d
87
d++1+
di
5
87 + d;
The above recursions provide the same vector estimate the recursions (10) and 11 in the paper since they are obtained using the Bauch-Tung-Striaes smoother recursions instead of fixed- lag smoother recursions (Bishop, 2006 Anderson Moore, 1979).
E PROOF OF THEOREM
Proof. To obtain bound in 22) we first prove that the mean vector estimate and the MSE vector given by (10) and (1 respectively, satisfy
2 (0) 15 1// 10 20 ( log
2m
P
2 (1 (1-5) 5)
(20)
15

---

Under review as a conference paper at ICLR 2023
for any component i = 1,2,...,m.. m. Then, we prove that || 1oc S M/ V/vy
for j
E
{1. ...,..... k), where the ESSs satisfy nk nk and n. ny + nj+t | se ny i1 for j 2 2.
To obtain inequality 20) we prove that each component i ........ m of the error in the mean
vector estimate 3j 2 k(i) = r30(0) -=((+) is sub-Gaussian with parameter m5-k() I KV &/55 (())
Analogously to the proof of Theorem
I it is proven that each component in the error of the backward
mean vector TJ+1 is sub-Gaussian with parameters satisfying ni+1 I Ki 1 The error in the forward and backward mean vector estimate is given by
25tb(11) -70(0) 17-6(0) = (00(1) - (1)
- (1) j+1 -
(1)
(1)
+
sj+1
+ d3+1
(1)
Tj
where the second equality is obtained using the recursion for rj x (i) (6)
in 10
Adding and subtracting
we have that
2j x0)
(i)
(1)
A-((1) (1)
Tj- (1) 1
2z
(6)
(1)
d3
(1)
7+11"
-3+1
+
3+1
2+1
$j (4)
(00((0)
(2)
2/+1 - T3 (1)
k (1)
(1)
2q
#j+1
$j (1) + $z741 (4)
+ +d3+1
(6)
since w = T.
-ーー and 2j (1) r720(t) Ty ( Then, we have that
55 (1)
2j 27b(6 =2j
( (0)
w 3+1
2371 (9)
())
(21)
$ (1)
+ J+1
(4)
3+1
57 (1)
(0)
2j (8)
(4)
+ 8741
+ 1+1
87 (0)
(2)
23+1 (1)
(7-0
9344
k (1)
d2
(1)
where: 2, 20,
2j+1 (1) and w are sub-Gaussian with parameters Mi (1) S k//5 (0), n (1) S
(5)
(1)
B and (w))") ). respectively. Since , and wy+1 are independent, we have that given by 21 is sub-Gaussian with parameter that satisfies
15 ( 2 1
11 (1)
(10) 2
(6)
k (8)
(1)
j+1
J+1
$7 (6)
2
σ ( (1) )
+ ( ((1 ())
87 (8) + 9741
k (4)
+ J+1
(0)
87 (1)
2
n: 2²85-110 (1)
87 (1)
k (3)
+ d2
*+11
J+1
5 (6)
R (dzt1 (1) + - (1)
87 (8) + 1
k (6)
+ dz
85+1
16

---

Under review as a conference paper at ICLR 2023
Using |
we have that the sub- Sab-Gaussian parameter satisfies
2
-1
(
2 x
x²
1
s7f1
(0)
J+1
(()
j+1
k2 (6)
+
j+1
(1) 2
k (0)
j+1
J+1
(1)
(0)
+ de
(1) x
s+1
3
x² 5)
k()
k2
x²33
8141
(1)
+ j+1
(0)
8jt1 + djt1
(6)
(0)
The inequality in (20 is obtained using the union bound together with the Chernoff bound (concen- tration inequality) (Wainwright, 2019) for the random variables 25 that Lub-Gaussian with parameter 17 ((()
Now, prove that, for any j. |l 8j || S M/ n n5 where the ESSs satisfy ni n ng and
1 for j 2 2. Analogously to the proof of Theorem 1 we [ojll | ofi
nith 2 ni
prove that the backward MSE vector 877 satisfies
ll o S M/ M//njj Then, using that
Il sttillo I M\ Mj+1. have that for every component
(o
n2
$
(3)
8
8Th b (6)
j+1
d2
+1
(1)
M2 1+1
+
d2
j+1
(N)
M
+
M
n2
+
1
10
n
M
15+1
1
Then, obtain
M
11
8 k
10
(22)
12
[1
The inequality in 12 is obtained because the minimax risk is bounded by the smallest minimax risk as shown in (Mazuelas et al., 2020 h2022alb) so that
R(U < 1250 + (1T,3 1 + ||7 11o0) (1 1|,
that leads using and the fact that s 2 (2m²
F PROOF OF THEOREM
Proof. obtain bound 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
11 0c
(1 + 1)))(k)))---111 al1 2
h 2 nj41 + 1342
(1+
+ n
n
12
17

---

Under review as a conference paper at ICLR 2023
Therefore, the ESS obtained with forward an backward learning satisfies
(1+ 1+
1 + ( -
n 2 nj + 1 (1 + ()) - +a) )
alL=a)il--)-i+aa
(((1))))11111 a[1+
a(1 +
ndf
(1+0)((--)) -1
(
a²
(1
1 (1 + 0)) ( -)- - 11 1
n a(1+))( +a
1
a+1
a(1 + a) 2)(
where the second equality follows because nal have that
since
nd ?
(V 1
nde + 1). Then, we
n 2nj" + (1+ (1a))(k-1)) -
a(1 + a) 2( j)- a
((1 + 2))(()))-)))))))))))))))))))))) +
2) 11) a)
(a (1+ (1
a1+ 2(k -1
2nj + n
a(1 + a) +a)
(1 1))
Now, we obtain bounds for the ESS depending on the value value of ndd Such bounds are obtained similarly as in Theorem and we also denote by ø the golden ratio 1.618
1. If nd < < Vnd S a S Vnda s $ S similarly as in the previous case, then we have that n. satisfies
(2 1)) = nj + +n 1+ a(k -1)
h: j
k 2 n + n
nj n + n a + a2(k -
1 2 (k: j)
where the first inequality follows because (1+ + LLaa221 a)2(k (()-())))11 second inequality obtained using a S y.
a(2(k j] 1) and the
< Vnd S a S Vndzo because ndf V 1+ nd
2. If # S ndf <
V Vnd /nd=+4+v/ and then we have that n²th satisfies
2
(1+ (1+a))(k-)) -1 2 nj (1 Vnd ( (((--)) +1
Ti (1 ndl ) 2(k 5)
a (1 (1+a)2(0-1) +1
where the second inequality follows because the ESS is monotonically increasing for a and 2 nd?. Since (1 + V 2 1 2V nd - j) and k 1, we have that
n
nd
1
n
my
Vnd
2 ny + n-
+ Vnd
because a S Vnd
1+ mdz 21 = ndt S S nd& because nd V
+1
3. If nd satisfies
then have that nz
12 - a
1 13
n n 2 n
(( +1 2 n. + 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 & - j 2 and a S ndl
18

---

Under review as a conference paper at ICLR 2023
Table 2: Datasets characteristics.
Dataset
Classes
Samples
Tasks
Yearbook
2
37,921
126
ImageNet Noise
2
12,000
10
DomainNet
4
6,256
FTKe
2
23,500
94
Rotated MNIST
2
70,000
60
CLEAR
3
10,490
10
G 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 oate-of-the-art techniques for different sample sizes; in the second set of additional results, we further show the performance improvement leveraging information from preceding and succeeding tasks with additional datasets; in the third set of additional results, show the classification error and the running time of LMRCs for different hyper-paramen parameter values; and in the fourth set of additional results, evaluate the assumption of change between tasks being independent and zero-mean. In addition, in the folder Implementation LMRC in the supplementary materials we provide the code of the proposed LMRCs with the setting used in the numerical results.
LMRC
The datasets used in Section Russakovsky et al. (0155): Zhang et al.
5 are publicly available in Ginosar et al 2015); (2017); et (2019); et (2021). and
http:///ann: le lecun. com/ exdb/mrr mnins/ The summary of these datasets is provided Table 2 that shows the 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.
The "Yearbook" dataset contains portraits' photographs over time and the goal is predict males and females. Each task corresponds to portraits from one year from 1905 to 2013.
The "ImageNet noise" dataset contains images with increasing noise over tasks and the goal is to predict if an image is bird or snake. The sequence of tasks corresponds to the noise factors [0.0, 0.4, 0.8, 1.2, 1.6, 2.0, 2.4, 3.2, 3.6] (Mai et al., 2022).
The "DomainNet" dataset contains six different domains with decreasing realism and the goal is 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 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 a rotation angle randomly selected from 180() j {1,2,...,,k] and is the number of tasks.
180
degrees where
k
The "CLEAR" dataset contains images with natural temporal evolution of visual concepts in the real world and the goal is to predict if an image is soccer, hockey, or racing. Each task corresponds one year from 2004 to 2014.
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.
The classifier parameters in the numerical results obtained using accelerated subgradient method based on Nesterov approach (Nesterov & Shikhman, 2015: Tao et all (011).. Such subgra- dient method applied to optimization 3 obtains at each step classifier parameters fa from the mean
19

---

Under review as a conference paper at ICLR 2023
Single-task
Forward
0.47
Forward and backward
Classiication crrozt single--guue task
Forward
Forward and buckward
Classificution error
0.36
0.8
Forward
Forward backward
0.
Forward
100
Forward and backward 100
Nomber of tasks
Sample size
(a) Classification per number of tasks using "Do- (b) Classification error per sample size using "Do- mainNet" dataset.
mainNet" dataset.
Figure 5: Forward and backward learning can sharply boost performance and ESS as tasks arrive.
Table 3: Classification enror and standard deviation of the proposed LMRC method in comparison with the sfate-of-the-arr techniques.
IunggeNe noise
DomainNet
MNNST
50
150
50
150
50
150
150
50
150
50
150
GEM
16 16.2 00
.66
36 .l6
.12
65 = 05
497 11
.12 00
.12
.29 # 04
+ .01
88 #: 011
.B8 011
.11
ELLA
43 10
43 08
A7 1: 05
47 04
67 1 05
67 05
18
.17 11
48 1 06
47 1: 05
60 06
80 04
.12
LMRC
110 02
J88 011
10
08
288 08
27 02
10 00
10 00
25 02
20 + 011
.05 02
.04
and confidence vectors T, À using the iterations for 1,2..... K
( + 1) (1)) + a ( 0 - -xsign((((()) 11l + = pl
(23)
0101
(1(1) =i())
where sign(-) denotes the sign function, pll) is the 1-th iterate for μe, 0: 2/(l + 1) and a = 1/(l 1)3/2 are the step sizes and (t(()()) denotes subgradient of (p(-) (e(1) with
Eyec (1, (T
(p))
max #EX,CC)
[C|
In addition, the above subgradient method is implemented using K = 2000 iterations and a warm- start that initializes the classifier parameters in (33) with the solution obtained for the closest task.
In the first set of additional results, we further compare the classification error of LMRCs with the state-of-the -httt--rrtttt techniques. The results in Table in the paper well as Table B obtained com- puting the classification error 50 times for each sample size. Table the paper shows classification for 10 and 100 samples, while Table 3 shows the classification error for 50 and n = 150 samples. As can be observed in Table 3 the performance improvement of LMRCs in comparison with the state-of-the-art techniques for 50 and 150 is similar to that shown in the paper for
10 and 100.
In the second set of additional results, we further illustrate the relationship among classification error, number of tasks, and sample size. Figure in the paper as well as Figure [ are obtained computing the classification error over the sequences of consecutive tasks of length in the dataset. Then, we repeat such experiment 10 times with randomly chosen training sets of size n. (Jettnnds the results for LMRCs using "DomainNet" dataset completing those in the main paper that show the results using "Yearbook" dataset. Figure 5a shows the classification error of LMRC method divided by the classification error single-task learning for different number of tasks with n = 10 and 100 sample sizes. In addition, Figure [5b] shows the classification error of LMRC method for different sample sizes with = 10 tasks. Figures 5a and [5b show similar behavior to Figures 4a and 4h in the paper, respectively. In addition, Figure 6 shows the classification error of LMRCs
20

---

Under review as a conference paper at ICLR 2023
Tak
Step
Step
Skop
(a) Single task.
(b) Forward.
(c) Forward and hackward.
Figure 6: Forward and backward learning can improve performance of preceding tasks.
Table Classification error the proposed LMRC method varying and
Dataset
Yearbonk
ImageNet noise
DomainNet
UTKFaces
Rotated MNIST
CLEAAR
100
10
100
10
100
10
100
10
100
10
100
W
.08
.15
.34
.88
.15
.32
.10
.09
.15
.36
b=1
.14
.10
.15
.09
.36
.29
.10
.10
.36
.22
.10
.05
=
.14
.09
.15
.09
.35
.28
_10
.10
.36
.22
.09
.05
.13
.08
.15
.09
.34
.28
_10
.10
.36
.21
.09
.05
.13
.08
.15
.08
34
.28
.10
-10
.36
.21
.09
.05
.08
.15
.08
34
.28
110
.10
.36
.21
.08
.05
per step and task with single-task learning, forward learning, and forward and backward learning using the "Yearbook" dataset. Such figure shows that forward and backward learning improve performance of preceding tasks, while forward learning and single task learning maintain the same performance over time.
In the third set of additional results, we further assess the change classification error and the running time of LMRCs varying the hyper-parameters. Table 4 shows the classification error of LMRCs varying the values of hyper-paramete for the window size W and the number of backward steps b, completing those in the paper that show the results for W and b 3. As shown in the table, the proposed LMRCs do not require a careful fine-tuning of addition, Table shows the mean running
and similar
performances are obtained by using different values. time per task in seconds of LMRCs for b = 1, 1.2..... backward steps in comparison with the state- of-the-art techniques. Such table shows that the methods proposed for backward learning do not require significant increase in complexity. In addition, Table shows that the running time of the proposed method similar that of other state-of-the-arr methods.
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 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[]showe the averaged partial autocorrelation of the mean vectors components +/- their standard deviations for different lags using "Portraits" and "UTKFaces" datasets. Such figure shows a partial autocorrelation clearly non-zero at lag 1 that reflects dependence between consecutive vectors, described by the assumption of Section
mean vectors. particular,
21

---

Under review as a conference paper at ICLR 2023
Table 5: Running time in seconds of LMRC method in comparison with the state-of-the-art techniques.
Datasct
Yearbook
ImageNet noise
DomainNct
UTKFaccs
Rotated MNIST
CLEAR
10
100
10
100
10
100
10
100
10
100
BLLA
0.066
0.070
0.073
0.073
0.054
0.065
0.059
0.062
0.176
0.198
0.077
0.073
GEM
0.098
0.476
0.010
0.037
0.005
0.020
0.056
0.310
0.180
1.094
0.009
0.034
MER
0.166
3.726
0.079
1.052
0.066
0.900
0.127
3.458
0.211
4.092
0.074
1.063
FWC
0.358
3.031
0.032
0.252
0.018
0.155
0.245
2.246
0.587
5.296
0.031
0.248
LMRC
0.094
0.324
0.259
0.490
0.518
8.463
0.108
0.348
0.135
0.471
0.235
1.310
LMRC
0.105
0.397
0.261
0.531
0.543
8,983
0.115
0.401
0.165
0.599
0.252
1.406
LMRC 3
0.133
0.487
0.284
0.561
0.542
9.514
0.133
0.488
0.209
0.737
0.255
1.469
LMRC
0.167
0.582
0.304
0.585
0.559
9.699
0.156
0.573
0.249
0.877
0.271
1.595
LMRC
0.184
0.664
0.438
0.601
0.571
9.921
0,190
0.664
0.288
1.010
0,360
1.693
autocomelation
Partial autocorelation
15
70
70
Lags
Lags
(a) "Portraits" dataset
(b) "UTKFaces" dataset
Figure Averaged partial autocorrelation of mean vectors components +/- their standard deviations.
22


Reviews:
[{"review_id": "hjnkcQ9PGj", "reviewer": "Reviewer_KxHd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the author(s) used minimax risk classifiers to propose a lifelong method that utilized forward and backward learning for time-dependent tasks. Through Empirical experiments, the author(s) tried to show the advantage of the proposed algorithm.\n\n---", "summary_of_the_review": "I think the topic in this paper is important and this paper is generally well-written; However, there are some unclear aspects in the paper. Maybe it needs the author(s) to clarify them. Thanks.\n", "strength_and_weaknesses": "### Strength:\n\n1. Trying to address the issues of catastrophic forgetting and i.i.d. constraint in current lifelong learning.\n\n2. Providing theoretical guarantees for the proposed algorithm.\n\n3. Performing empirical experiments to validate the performance of the proposed algorithm.\n\n---\n\n### Weaknesses:\n\n1. The theoretical analysis of the proposed algorithm, such as generalization bounds, may require further empirical experiments.\n\n2. Some descriptions in this paper are not so clear.\n\nFor more details, please see the section of \"Clarity, Quality, Novelty And Reproducibility\".\n\n---", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "a4SjEnLseS", "reviewer": "Reviewer_Q8gE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper tackles lifelong learning by improve effective sample size using both forward and backward tasks. This paper assumes that tasks arrive consecutively non-iid but satisfying a martingale assumption. This paper adopts the framework minimax risk classification into the lifelong learning setting. After showing the improvement in effective sample size theoretically, the paper presents numerical experiments to demonstrate the effectiveness of the proposed method. ", "summary_of_the_review": "Although the paper is interesting and somewhat novel, I am concerned about a few settings used/assumed in the paper, as detailed in the weakness section. ", "strength_and_weaknesses": "Strength: This paper presents an interesting framework for lifelong learning, i.e., the lifelong minimax risk classifiers (LMRCs), and the proposed method is novel to me. The theoretical analysis seems solid. \n\nWeakness: I'm concerned about a few settings and assumptions where more justification is needed. \n1. The assumption of $p_{i+1}-p_i$ being independent and zero-mean is only justified by a sentence. However, the validness of such assumption should be discussed more in my opinion, since it is an important assumption to the proposed method. For example, are there any real-life settings where this assumption may hold true (or even approximately being true).\n2. The proposed method relies on the feature map $\\\\Phi$ which is not learnable. However, one would argue that without learning the feature map it is not really doing a proper lifelong learning. \n3. Instead of learning the feature map, the proposed method learns the uncertainty set. How would one know if the leaned uncertainty set is a good one? For example, will the uncertainty set be too big such that the maximization part overpowers the minimization part, and the resulting classifier is not really meaningful? Alternatively, does the method provide a bound on the regular loss function for each task?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AnFSos09Xk", "reviewer": "Reviewer_vTda", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a method based on minimax risk classifiers, termed LMRCs, for lifelong learning with time-dependent classification tasks. The LMRCs exploits forward and backward knowledge transfer based on underlying Gaussian assumptions, with perhaps a frozen pre-trained feature extractor. Theoretical analyses and empirical experimental results are presented.", "summary_of_the_review": "There are so many lifelong learning papers in recent years; please make comparisons and discuss the advantages of the proposed method.  \n\nHow to train the feature mapping $\\Phi(x,y)$ with the presented LMRCs? Is $\\Phi(x,y)$ assumed known/frozen?\n\nIn the paragraph before Eq (3), what's the 0-1-loss? Does that mean you assume 2-category classification tasks throughout the paper?\n\nIn Eqs (4-6), the derivations are based on Gaussian assumptions, right? How do those assumptions affect the forward/backward knowledge transfer in lifelong learning?\n\nIn the experiments, the baseline methods are kind of outdated.\n", "strength_and_weaknesses": "Strength.\n\n(1) The paper is well-written.\n\n(2) The presented theorems and derivations seem to be solid.\n\nWeaknesses.\n\n(1) The related work and the baseline methods in the experiments are kind of outdated.\n\n(2) It seems the presented method assumes one can access all $\\tau_i, i \\in [1,j+d]$ when dealing with the $j$-th task.\n\n(3) It seems the presented method is presented based on a frozen pre-trained feature extractor and simple Gaussian assumptions (\\ie Eqs (5-6) and (10-11) from the Kalman filtering).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject