Prospective Learning: Learning for a Dynamic Future
Authors: Ashwin De Silva
Rahul Ramesh
Rubing Yang
Siyu Yu
Joshua T Vogelstein
Pratik Chaudhari
Venue: NeurIPS 2024 poster (2024)
Keywords: Distribution Shifts
Learning Theory
Primary area: learning_theory
TL;DR: We incorporate time into the PAC framework, demonstrating both theoretically and empirically that time-aware empirical risk minimization outperforms time-agnostic methods for certain problems where the data distribution varies predictably over time.

Abstract: In real-world applications, the distribution of the data, and our goals, evolve over time. The prevailing theoretical framework for studying machine learning, namely probably approximately correct (PAC) learning, largely ignores time. As a consequence, existing strategies to address the dynamic nature of data and goals exhibit poor real-world performance. This paper develops a theoretical framework called
"Prospective Learning" that is tailored for situations when the optimal hypothesis changes over time. In PAC learning, empirical risk minimization (ERM) is known to be consistent. We develop a learner called Prospective ERM, which returns a sequence of predictors that  make predictions on future data.  We prove that the risk of prospective ERM converges to the Bayes risk under certain assumptions on the stochastic process  generating the data. Prospective ERM, roughly speaking, incorporates time as an input in addition to the data. We show that standard ERM as done in PAC learning, without incorporating time, can result in failure to learn when distributions are dynamic. Numerical experiments illustrate that prospective ERM can learn synthetic and visual recognition problems constructed from MNIST and CIFAR-10. Code at https://github.com/neurodata/prolearn.

Prospective Learning: Learning for a Dynamic Future
Ashwin De Silva"
Rahul Ramesh
Rubing Yang*.
Siyu Yu!
Joshua T. Vogelstein 1.1
Pratik Chaudhari
Equal Contribution
Email: (Idesilv2, syu80, jovo I @ jhu.edu, (rahulram, rubingy, pratikac| @upenn.edu
Abstract
real-world applications, the distribution of the data, and our goals, evolve over time. The prevailing theoretical framework for studying machine learning, namely probably approximately correct (PAC) learning, largely ignores time. As a consequence, existing strategies to address the dynamic nature of data and goals exhibit poor real-world performance. This paper develops a theoretical framework called "Prospective Learning" that is tailored for situations when the optimal hypothesis changes over time. In PAC learning, empirical risk minimization (ERM) is known to be consistent. We develop learner called Prospective ERM, which returns a sequence of predictors that make predictions on future data. We prove that the risk of prospective ERM converges to the Bayes risk under certain assumptions on the stochastic process generating the data. Prospective ERM, roughly speaking, incorporates time an input in addition to the data. We show that standard ERM as done in PAC learning, without incorporating time, can result in failure to learn when distributions are dynamic. Numerical experiments illustrate that prospective ERM can learn synthetic and visual recognition problems constructed from MNIST and CIFAR-10. Code https//ggghub..commnuuuoaaaaaa/p
Introduction
All learning is for the future. Learning involves updating decision rules policies, based on past experiences, to improve future performance. Probably approximately correct (PAC) learning has been extremely usefuul to develop algorithms that minimize the risk tak-ccliilllyy defined the expected loss-on unseen samples under certain assumptions. The assumption, that samples are independent and identically distributed (IID) within the training dataset and at test time, has served us well. But it neither testable nor believed to be true in practice. The future always different from the past: both distributions of data and goals of the learner may change over time. Moreover, those changes may cause the optimal hypothesis to change over time as well. There are numerous mathematical and empirical approaches that have been developed address this issue, e.g., techniques for being invariant to [1], or adapting to, distribution shift [2], modeling the future as a different task, etc. But lack first-pricipples framework address problems where data distributions and goals may change over time in such way that the optimal hypothesis is time-dependent. And as consequence, machine learning-based AI today is brittle to changes in distribution and goals.
This paper develops theoretical framework called "Prospective Learning" (PL). Instead of data arising from unknown probability distribution like in PAC learning, prospective learning assumes that data comes from an unknown stochastic process, that the loss considers the future, and that the optimal hypothesis may change over time. A prospective learner uses samples received up to some time i E N to output an infinite sequence of predictors, which it uses for making predictions on data at all future times e' > f. We discuss how prospective learning is related to existing problem formulations in the literature in Section 3 and Appendix A.
Why should one care about prospective learning? Imagine deployed machine learning system. The designer of this system desires to optimize-taeee not the risk upon the past training data, or the risk 38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

on the immediate future data but the risk on all data that the model will make predictions upon in the future. As data evolves, e.g., due to changing trends and preferences of the users, the optimal hypothesis to make predictions also changes. Time is the critical piece of information if the system designer to achieve their goals. Both in the sense of how far back in time a particular datum was recorded, and in the sense of how far ahead in the future this system will be used to make predictions. The designer must take time into account to avoid retraining the model periodically, ad infinitum. Biology is also rich with examples where systems seem to behave prospectively. The principle of allostasis, for example, states that regulatory processes of living things anticipate the needs of the organism and prepare to satisfy these needs before, rather than after, they arise [3]. For example, mitochondria increase their energy production to anticipate the demands of muscles [4], neural circuits anticipate changes in sensory stimuli and the task (i.e., predictive coding [5]), and individual organisms optimize their actions with respect to anticipated changes in their environments [6, 7J. These regulatory principles were learned early in evolutionary time so they must be important. In short, the world-including our internal drives- changes all the time, and learning systems must anticipate (that is, prospect) these changes to thrive.
Contributions
Section 2 defines Prospective Learning (PL.) as approach address problems where the optimal hypothesis may evolve over time (due to shifts in distributions and/or goals of the learner). It also provides illustrative examples of PL.
Section and Appendix A put prospective learning in context relative to existing ideas in the literature address changes in the data distribution.
Section 4 takes steps towards a theoretical foundation for prospective learning. We de- fine strongly learnability (i.e., there exists a prospective learner whose risk is arbitrarily close to the Bayes optimal learner) and weakly learnability (i.e., there exists a prospective learner whose risk is better than chance) [8]. Empirical risk minimization (ERM) without incorporating time, can result in failure to strongly, or even weakly, learn prospectively [9]. Section introduces prospective empirical risk minimization, and proves that it can learn prospectively under certain assumptions on the stochastic process and loss.
Section 6 demonstrates that our prospective learners can prospectively learn several canonical problems constructed using synthetic, MNIST [10] and CIFAR-10 1- [11] data. In contrast, number of existing algorithms, including ERM, online and continual learning algorithms, fail. Appendix H demonstrates that current large language models, which use Transformer-based
architectures trained using auto-regressive losses, fail to learn prospectively.
2 A definition of prospective learning
A prospective learner minimizes the expected cumulative risk of the future using past data. Such a learner is defined by the following key ingredients (see Fig. (left) for schematic illustration).
Data. Let the input and output at time be denoted by æt E X and yt E y respectively. Let (Ze)ee defined on an appropriate probability space (Ω, F, PP). At time t E N, denote past data by age = (z1...., 22) and future data by Pyt = (Z++1, We will find useful to distinguish between the realization of the data, denoted by Fgt: and the corresponding random variable, Zge.
2t = (fe, 9t). We will model the data as a stochastic process
Hypothesis class. At each time t, a prospective learner selects an infinite sequence = (hi,..., he, h..1....) ) which it uses to make predictions on data at any time in the future. Each element of this sequence h : X' + y and therefore hr E y 1 The hypothesis class H is the space of such hypotheses, l H C ( We will again use the shorthand l&g (hi.... hx). We will sometimes talk about a "time-agnostic hypothesis" which will refer to a hypothesis such that br = by for all i, t E N. Observe that this makes our setup different from the standard setup in PAC learning where the learner selects a single hypothesis in y One could also think of prospective learning as using single time-varying hypothesis h N x X Y, i.e., the hypothesis takes both time and the datum as input to make a prediction.
Learner. A prospective learner is map from the data received up time f. to hypothesis that makes predictions on the data over all time (past and future): (X' x y> + x The learner gives
We will use some non-standard notation in this paper. In particular, a hypothesis h will always refer to sequence of predictors ht- = (lu...., Av, he.1....). This helps avoid excessively verbose mathematical expressions.
'When we say that "leamer selects hypothesis" in the sequel, it will always mean that the learner selects an infinite sequence from within the hypothesis class H.

---

as output a hypothesis h(zgg)) E H. Unlike a PAC learner, a prospective learner can make different kinds of predictions at different times. This is crucial property of prospective learning. In other words, after receiving data up to time f, the hypothesis selected by the prospective learner can predict on samples at any future time 1' > t. Prospective loss and risk. The future loss incurred by hypothesis h is
1+T
(h, Z) = lim sup
Σ s=t+1
(X.), Ys),
where future loss"
[0, 1] is bounded loss function."
Prospective risk at time is the expected
Rh) E (La Z) =ga] = f Z) Zlzg1
where we assume that h is random variable and h o(Zgt) where o(-) denotes the filtration (an increasing sequence of sigma algebras) of the stochastic process Z. We have used the shorthand E|y xr] for E[Y X w). Observe that we have conditioned the prospective risk of the hypothesis upon the realized data zgg.. We can take an expectation over the realized data, to obtain the expected prospective risk
E [R)] - ( (l)
Prospective Bayes risk is the minimum risk achievable by any hypothesis. In PAC learning, it is a constant that depends upon the (fixed) true distribution of the data and the risk function. In prospective learning, the optimal hypothesis can predict differently at different times. We therefore define the prospective Bayes risk at time 2 as
R inf (Zg()
(h),)
which is the minimum achievable prospective risk by any learner that observes data Ege. We define the Bayes optimal learner as any learner that achieves a Bayes optimal risk at every time E N. In certain contexts, might be interested in the limiting prospective Bayes risk t cc.
2.1 Different prospective learning scenarios with illustrative examples
We next discuss four prospective learning scenarios that are relevant to increasingly more general classes of stochastic processes. Our goal is to illustrate, using examples, how the definitions developed in the previous section capture these scenarios. We will assume that for all times / we have X, 1, Yi E {0, 1}. We will also focus on the time-invariant zero-one loss E(t, ÿ. y) = 8(ÿ & y) for all f, here 8 is the Dirac delta function. Fig. shows example realizations of the data for each scenario.
Scenario 1 (Data is independent and identically distributed). Formally, this consists of stochastic processes where 1z,. = P'z, for all 1, E N. As an example, consider Y, ~ Bernuuli(p) for some unknown parameter p E [o, 1). Prospective Bayes risk is equal to min(p. 1 - p) in this case. A time-agnostic hypothesis, for example one that thresholds the maximum likelihood estimator (MLE) of the Bernoulli probability, converges to the limiting prospective Bayes risk."
Scenario (Data independent but not identically distributed), This consists of stochastic processes where P Pz.|Zg. Fz, for all t E N. Consider Y; Bernoull(pp) if is odd, and Y, Bemoulli(1 - p) if i is even, i.e., data is drawn from two different distributions at alternate times. Prospective Bayes risk is again equal to min(1 p. p) in this case. A tume-agnostic hypothesis can only perform at chance level. But prospective learner, for example one that selects a hypothesis that alternates between two predictors at even and odd times, can converge to prospective Bayes optimal risk. We can also construct variants, e.g., when the relationship between the Bernoulli probabilities are not known (Variant in Fig. 1), or when the learner does not know that the data distribution changes at every time step (Variant 2 in Fig. where we implemented generalized likelihood ratio
'The limsup is guaranteed exist if & is bounded. If the series converges, can lim instead. "There are many real world scenarios where expected future loss may not be sufficient for good performance, e.g., for portfolio managements or inference by biological learners who optimize for balance between value and risk. Moreover, the risk functional could, in general, also change over time. In this paper, we will focus only on the expected future loss.
*e show an interesting observation in Appendix B.1: if the prior of a Bayesian learner is different from the true Bernoulli probability, then prospective learning can improve upon the maximum posteriori estimator.
3

---

Scorar 1 Futures
Sconario
Scemario 3
Scemani
Past
Part
Pasuress
Past
Futures
Past
Pusures
Patectal Fatume (tud)
Beabool Post (oud
Daca
dettris bel data
disrisubed data
1ee dote Nathow chain
Markoy sio proued
Passeediiee rak
Prottedtte
0.4
02
0.2
Time
Prospect vs leamer
Varin122
Variant
Bays Rik
Chance
Figure 1: A schematic for prospective learning (left) and realizations of the examples for the four scenarios (top right); dots denote Is and empty spaces denote Os for Y, E [0, 13 with X, = for all times f. Prospective risk of learners at different times is shown in the bottom panels and discussed in Section 2.1. Scenario 1: For Bernoulli probability p 0.2, the maximum likelihood estimator (MLE) in blue uses time-agnostic hypothesis (X,) (p. 0.5) where Pr- = E Va. ties at P. 0.5 broken randomly. The risk of this learner converges to the Bayes risk. Scenario 2: For Bernoulli probability p 0.2, the MLE estimator (blue) performs at chance levels. A prospective learner (red) that alternates hetween two predictors at even and odd times converges to Bayes risk. Variants of this learner that use less information from the stochastic process (purple does not know that the data distributions at even and odd times are tied, green does not know that the distribution shifts at every time-step) also converge to Bayes risk, but more slowly. Scenario 3: For 0 0.1 and y = 0.9 in the discounted prospective risk, the MLE estimator (blue) again performs at chance levels. prospective learner that computes an estimate of the transition probability of the two-state Markov chain to estimate P(Yx ye) for future times t' > converges to Bayes risk. Scenario 4: For fg = 82 = 0.1, the MLE estimator (blue) performs chance levels. A prospective learner that uses a variant of Q-learning (deseribed in the text and Appendix B.3) converges to the prospective Bayes risk.
test to determine whether the distribution changes). The risk of these variants also converges to prospective Bayes risk, but they need more samples because they use more generic models of the stochastic process. This scenario is closely related to (online) multitask/metta-lamiin
[12].
Scenario (Data is neither independent nor identically distributed). Formally, this scenario consists of general stochastic processes. As an example, consider Markov process P(Y = k Y; = k) = 8 with two states & E {0. 1} and Yi ~ Bernoulli()). The invariant distribution of this Markov process is P(O)- P(1) 1/2. Prospective Bayes risk is also equal to 1/2. For stochastic processes that have a invariant distribution, it is impossible to predict the next state infinitely far into the future and therefore it is impossible to prospect. The prospective Bayes risk is trivially chance levels. In such situations, the learner could consider losses that are discounted over time. For example, one could use slightly different loss than the one in Eq. (1) to write
(h, 2) = (1 - >) Em 1 - ((h,
for some 7 E 10. In this example, we can calculate the prospective Bayes risk analytically: see Appendix B.2. For y 0.9, 0 = 0.1 and the zero-one loss, limiting prospective Bayes risk is 0.357. Now consider learner which computes the MLE of the transition matrix 1 -t, It calculates P(Y: (v) = Pr where [1- 2r] = ry -f [1 - y1 T and uses the hypothesis by (Xe) = 1(pr > 0.5) (ties broken randomly). We can see in Fig. 1 that this learner converges to the prospective Bayes risk. This example shows that if we model the changes in the data, then we can perform prospective learning. This scenario is closely related to certain continual learning problems [13, 14].
Scenario (Future depends upon the current prediction). Problems where predictions of the learner affect future data are an interesting special case of Scenario 3. Prospective learning can also be used address such scenarios. For 0,.01 01 E [0, 1]. consider a Markov decision process (MDP) P(Y++1 = = Yú = j'. (1)1(1) k) 0g if j j' and 1 02 otherwise. Le., the prediction (X,+4) = (recall that X for all times) is the decision and the MDP remains in the same state with probability 0g. Prospective Bayes risk for this example is the same as that of the example in Scenario 3. We can construct a prospective learner using a variant of Q-learning to first estimate the hypothesis and then estimate the probability P(Yr y1) like Scenario 3 above to predict on future data at time f'. See Appendix B.3. Prospective risk of this learner converges to Bayes risk Fig. 1. This scenario is closely related to reinforcement learning [15].

---

3 How is prospective learning related to other learning paradigms?
Distribution shift. Prospective learning [16] is equivalent to PAC learning [17] in Scenario 1 when data is IID. Situations when this assumption Technniues may not be valid are often modeled as distribution shift between train and test data [2]. Techniques such as propensity scoring [18, 19] or domain adaptation [20, 21] reweigh map the train/test data to get back to the IID setting; techniques like domain invariance [22, I] build a statistic that is invariant to the shift. Typically, the loss is unchanged across train and test data. If the set of marginals (P(Z)) of the stochastic process only has two elements, then PL is equivalent to the classical distribution shift setting. But otherwise, in PL., data is correlated across time, distributions (marginals) can shift multiple times, and risk changes with time. Multi-task, meta-, continual, and lifelong learning. A changing data distribution could be modeled as sequence of tasks. Depending upon the stochastic process, different concepts are relevant, e.g., multi-task learning [23] is useful for Scenario 2 and Appendix D when there are finite number of tasks. Much of continual or lifelong learning [14, 13] focuses on "iakkinncrementa"" and relass-increment settings [24], in which the learner knows when the task switches. PL does not make this assumption, and therefore, the problem is substantially more difficult. "Data-incremental" (or task-agnostic) setting [25], is similar to PL. But the main difference is the goal: continual or lifelong learning seeks to minimize past error. As a consequence, continual learning methods are poor prospective learners; see Section 6. Online meta-learning [26-29] is close to task-agnostic continual learning, except that the former models tasks as being sampled IID from some distribution of tasks. Due to this, one cannot predict which task is next, and therefore cannot prospect.
Sequential decision making and online learning. PL builds upon works on learning from streaming data. But our goals are different. For example, Gama et al. [30] minimize the error on samples from a stationary process; Hayes et al. [31] minimize the error on a fixed held-out dataset or on all past neither of these emphasizes prospection. There is rich body of work sequential decision making, e.g., predicting a finite-state, stationary ergodic process from past data [32]. Even in this simple case, there does not exist consistent estimator using the finite past Z1: [33-35]. This is also true for regression [36, 37], when the true hypothesis f s.t. Yi- fXe) is fixed. In other words, Bayes risk RC in Theorem may be non-zero in PL. even for finite-state, stationary ergodic processes. Hanneke [38] lifts the restriction on stationarity and ergodicity. They obtain conditions on the input process for consistent inductive (predict at time 1' t using data up to t), self-adaptive (predict at time i' using Zge and X(+1=)) and online learning [39, 40] (predict at t' using Zge). They prove the existence of a learning rule that is consistent for every X that admits self-adaptive learning. If X is "smooth", i.e., input marginals have a similar support over time, then ERM has a similar sample complexity as that of the IID setting [41]. Haghtalab al. [42] give algorithmic guarantees for several online estimation problems in this setting.
The true hypothesis in PI. can change over time. This is different from the continual learning setting where we can find a common hypothesis for tasks at all time [43], and this is why our proofs work quite differently from existing ones in the literature. Instead of a hypothesis class H. S ) we define the notion of a hypothesis class that consists of sequences of predictors, i.e., subset of (2 N.
we can do ERM in this new space. Instead of consistency of prediction as in Hanneke [38]. we give guarantees for strong learnability, i.e., convergence of the ERM risk to the Bayes risk.
Information theory. There are also works that have sought to characterize classes of stochastic processes that can be predicted fruitfully. Bialek et al. [44] defined notion called predictive information (closely related to the information bottleneck principle [45]) and showed how it is related to the degrees of freedom of the stochastic process. Shalizi and Crutchfield [46] showed that -ausal-state representation called an e-machine is the minimal sufficient statistic for prediction.
Theoretical foundations of prospective learning
Definition (Strong Prospective Learnability). A family of stochastic processes is strongly prospectively learnable, if there exists learner with the following property: there exists time d'(e, 6) such that for any e, 5 > 0 and for any stochastic process Z from this family, the learner outputs a hypothesis h such that P RR(
R < <) 2 ó, for any t> t'.
This definition is similar to the definition of strong lcarnability in PAC learning with one key difference. Prospective Bayes risk R; depends upon the realization of the stochastic process zgr up to time f. In PAC learning, it would only depend upon the true distribution of the data. Not all
AAlso see Appendix A for a more elaborate discussion.
5

---

families of stochastic processes are strongly prospectively learnable, We therefore also define weak learnability with respect to a "chance" learner that predicts B[y] and achieves a prospective risk st.."
Definition (Weak Prospective Learnability). A family of stochastic processes is weakly prospec- tively learnable, if there exists a learner with the following property: there exists an e >> 0 such that for any > O, there exists a time ('(c, 6) such that for any stochastic process from this family,
R (1) > {] 2 1 6, for any / > L'.
In PAC learning for binary classification, strong and weak learnability are equivalent [47] in the distribution agnostic setting, i.c., when strong and weak learnability is defined as the ability of learner to learn any data distribution. But even in PAC learning. if there are restrictions on the data distribution, strong and weak learnability are not equivalent [48]. This motivates Proposition 1 below. Before that, we define time-agnostic empirical risk minimization (ERM)- based learner. In PAC learning, ERM selects a hypothesis that minimizes the empirical loss the training data. It outputs time-agnostic hypothesis, i.e., using data, say, &g. standard ERM returns the same predictor for future data from any time t' > t. There is a natural application of ERM to prospective learning problems, defined below.
Definition 3 (Time-agnostic ERM). Let H. be a hypothesis class that consists of time-agnostic predictors, i.e., 14 by for any L E N for all predictors le E H. Given data Egt, a learner that returns
i = arg min hEH
Σ (1s,a)(
(5)
is called time-agnostic empirical risk minimization (ERM)-based learner.
Time-agnostic ERM in prospective learning may use a time-dependent loss f(s, (a(s))) ys) upon the training data. This ERM is not very different from standard ERM in PAC learning (when instantiated with the hypothesis class that consists of sequences of predictors, that we are interested here). If data is IID (Scenario 1), then there no information provided by time in the training samples. But if there are temporal patterns in the data, take Scenarios 2 and 3 or Scenario 4 as examples, then time-agnostic ERM defined here will return predictors that are different than those of standard ERM that uses a time-invariant loss.
There exist stochastic processes for which time-agnostic ERM is not a weak prospec- rive learner. There also exist stochastic processes for which time-agnostic ERM is weak prospective learner but not a strong one.
Proposition 1.
See Appendix for the proof. We do not know yet whether (or when) strong and weak learnability are equivalent for prospective learning.
5 Prospective Empirical Risk Minimization (ERM)
In PAC learning, the hypothesis returned by ERM using the training data can predict arbitrarily well (approximate the Bayes risk arbitrarily well with arbitrarily high probability), with sufficiently large sample size. This statement holds if (a) there exists hypothesis in the hypothesis class whose risk matches the Bayes risk asymptotically, and (b) if risk on training data converges to that on the test data sufficiently quickly and uniformly over the hypothesis class [49, 50). Theorem is an analogous result for prospective learning.
Theorem 1 (Prospective ERM is a strong prospective learner). Consider finite family of stochastic processes Z. If we have (a) consistency, i.e. there exists an increasing sequence of hypothesis classes Hi C H2 C ... with each H. S (2 such that VZ E 2,
lim E inf Re(h) R² =0
(6)
t-+00
NEE,
where h. E He is a random variable in (Z and (b) uniform concentration of the limsup, i.e., N7 EZ Z,
max h
Le Z)
max MI S Sm
Σ Us (s
S Tt,
"We can also detine weak lcarnability with respect to the prospective risk of a particular learner, even one that is not prospective. This may be useful to characterize learning for stochastic processes which do not admit strong learnability.

---

for some "H - 0 and on + so with us S L (all uniform over the family of stochastic processes), then there exists sequence in that depends only on Tt such that a learner that returns
h = arg min max
Σ (a
(8)
bEH4 Mhe SmSt TIL
is strong prospective learner for this family. We define prospective ERM as the learner that implements Eq. (8) given train data agt-
Appendix E.2 provides proof, it builds upon the work of Hanneke [38]. The first condition, Eq. (6), is analogous the consistency condition in PAC learning. In simpler words, it states that the Bayes risk can be approximated well using the chosen sequence of hypothesis classes {7₂ ) The second condition, Eq. (7). is analogous to concentration of measure in PAC learning, it requires that the limsup in Eq. (1) is close to an empirical estimate of the limsup (the second term inside the absolute value in Eq. (7)). At each time 4, prospective ERM in Eq. (8) selects the best hypothesis h E Hi for future times E' > t, that minimizes an empirical estimate of the limsup using the training data z<1- Prospective ERM can exploit the difference between the latest datum in the training set with time f and the time for which it makes predictions e' by selecting specific sequences inside the hypothesis class H4. For example, in Scenario can select sequences where alternating elements can be used to predict on data from even and odd times.
Remark (How to implement prospective ERM?). An implementation of prospective ERM is therefore not much different than an implementation of standard ERM, except that there are two inputs: time: and the datum zs. Suppose we use hypothesis class where each predictor is a neural network, this could be a multi-layer perceptron or convolutional neural network. The training set zge consists of inputs vs along with corresponding time instants s and outputs ys- To implement prospective ERM, we modify the network to take (s) as input (using any encoding of time, we diseuss one in Section 6) and train the network to predict the label ys- In Eq. (8) we can set Mi = t, doing so only changes the sample complexity. At inference time, this network is given the input (t', xx)) to obtain the prediction yy. Note that if prospective ERM implemented in this fashion, the learner need not explicitly calculate the infinite sequence of predictors. 9
Corollary There exist stochastic processes for which time-agnostic ERM is not a strong prospective
learner, but prospective ERM is a strong learner.
Remark 2 (Why need an increasing sequence of hypothesis classes Hi H....). We could have chosen He = Hy for all 1, E N to set up Theorem 1. But since the learner does not have a lot of data at early times, it should use small hypothesis class. Just like PAC learning, the sequence (Te keN in Eq. (7) determines the convergence rate of a prospective learner. Therefore, using a monotonically increasing sequence of hypothesis classes is useful to ensure good sample complexity.
Theorem Consider a finite family of stochastic processes z. If there exists a countable hypothesis class H such that
lim 10000
E
inf (h)
At, -0
(9)
KEE
for any stochastic process Z E Z, where h E H is a random variable in a (Z<1), then there exist He. us, and ztt such that the two conditions of Theorem are satisfied for this family.
Appendix E.3 provides a proof. This theorem provides a concrete example for which the assumptions of Theorem 1 are satisfied. In PAC learning, one first proves uniform convergence for a finite hypothesis class. This can then be used to, say, calculate the sample complexity of ERM, or extended to infinite hypothesis classes using constructions such as VC-dimension and covering numbers [51]. The above theorem should be understood in the same spirit. It is a step towards characterizing the sample complexity of prospective learning.
Appendix C proves an analogue of Theorem 1 for prospective learning problems with discounted losses. Appendix D provides illustrative examples of prospective ERM for periodic processes and hidden Markov processes. For periodic processes, we can also calculate the sample complexity.
$ Note that this hypothesis class has infinite sequences, H, S ()x*) N
Hereafter, when we write ERM in empirical studies, we will mean learner that approximates ERM via stochastic gradient descent.
7

---

6 Experimental Validation
This section demonstrates that we can implement prospective ERM on prospective learning prob- lems constructed on synthetic data, MNIST and CIFAR-10. In practice, prospective ERM may approximately achieve the guarantees of Theorem 1. We will focus on the distribution changing, independently not (Scenarios 2 and 3). Recall that Scenario is the same as the IID setting used in standard supervised learning problems. Scenario 4 is more involved (see an example in Appendix B.3) and, therefore, we leave more elaborate experiments for future work. We discuss experiments that check whether large language models can do prospective learning in Appendix H.
Learners and hypothesis classes. Task-agnostic online continual learning methods are the closest algorithms in the literature that can address situations when data evolves over time. We use the following three methods.
(i) Follow-the-Lcaad minimizes the empirical risk calculated on all past data and is no-regret algorithm [52]. We note that while this is a popular online learning algorithm, we do not implement the algorithm in online fashion.
(ii) Online SGD fine-tunes the network using new data in an online fashion. At every time-step, weights of the network are updated once using the last eight samples.
(iii) Bayesian gradient descent [53] is an online continual learning algorithm designed to address situations where the identity of the task is not known during both training and testing, i.e., it implements continual learning without knowledge of task boundaries.
These three methods are not explicitly designed for prospective learning but they are designed to address the changing data distribution z. 1.'0 We calculate the prospective risk of the predictor returned by these methods; note that they do not output time-varying predictor and consequently, these methods output time-agnostic hypothesis. As a result, when we evaluate the prospective risk of these methods, we use the same hypothesis for all future time. For all three methods, we use a multi-layer perceptron (MIP) for synthetic data and MNIST, and convolutional neural network (CNN) for CIFAR-10. 10.
For prospective ERM the sequence of predictors is built by incorporating time an additional input to an MLP or CNN as follows. For frequencies wi = x/i for I,..., d/2, we obtain a d- dimensional embedding of time as (() (sin(w1 ..... sin (waz/z)) cos((1 (), ................................ cos(wa/zz)). This is similar to the position encoding in Vaswani et al. [55]. A predictor hee()) uses a neural network that takes input, embedding of time p0s),, and the input us to predict the output ys for any time E N. Using such an embedding of time is useful in prospective learning because, then, one need not explicitly maintain the infinite sequence of predictors h (h1,-..:).
Training setup. We use the zero-one error 1 A y) to calculate prospective risk for all problems; all learners are trained using a standard surrogate of this objective, the cross-entropy loss. For all experiments, for each time t, we calculate the prospective risk Re(h) in Eq. (2) of the hypothesis created by these learners for a particular realization of the stochastic process age. For each prospective learning problem, we generate sequence of 50,000 samples. Learners are trained on data from the first t time steps (z<e) and prospective risk is computed using samples from the remaining time steps. Except for online SGD and Bayesian gradient descent, learners corresponding to different times are trained completely independently. See Appendix F for more details.
Remark 3 (Why we do not use existing benchmark continual learning scenarios). The tasks constructed below resemble continual learning benchmark scenarios such as Split-MNIST or Split- CI [56] where data from different distributions are shown sequentially to the learner. However, there are three major differences. First, in these existing benchmark scenarios, data distributions do not evolve in a predictable fashion, and prospective learning would not be meaningful. Second, existing scenarios consider fixed time horizon. We are keen on calculating the prospective risk for much longer horizons whereby the differences between different learners are easier to discern; our experiments go for as large as 30,000 time steps. Third, our tasks have the property that the Bayes optimal predictor changes over time.
1hTheee are many algorithms in the existing literature that the reader may think of as reasonable baselines. We have chosen representative and relevant set here, rather than an exhaustive one. For example, online meta- learning approaches are close to online-SGin
since the learner fine- tunes on the most recent data. Algorithms in the literature on time-series (i) focus on predicting future data, say, Y. given past data yş: without taking covariates X, or some exogenous variables X into account, (ii) can usually only make predictions for a pre- pre-specified future context window [54], and (iii) work for owwddimensional signals (unlike images).
8

---

6.1 Prospective learners for independent but not identically distributed data (Scenario 2)
We create tasks using synthetic data, MNIST and CIFAR-10 datasets to design prospective learning problems when data are independent but not identically distributed across time (Scenario 2).
Dataset and Tasks. For the synthetic data, consider two binary classification problems ("tasks") where the input is one-dimensional. Inputs for both tasks are drawn from a uniform distribution -
on the set 1-2,- - [1. 2]. Ground-truth labels correspond to the sign of the input for Task 1, and the negative of the sign of the imput for Task 2. For MNIST and CIFAR-10 10 we consider 4 tasks corresponding data from classes 1-5, 4-7, 6-9 and 8-10 in the original dataset, i... the first task considers classes 1-5 labelled 1-5 respectively, the second task considers classes 4-7 labelled 1-4, the third task considers classes 6-9 labeled 1-4 and the last task considers labels 8-10 labelled 1-3. In other words, images from class in task 1, class 4 from task 2 and class from task are all assigned the label 1. For the prospective learning problem based on synthetic data, the task switches every 20 time steps. For MNIST and CIFAR-10. the data distribution cycles through the 4 tasks, and the distribution of data changes every 10 time-steps. For more details, see Appendix F.
MNIST
1.00
TaskA-
Prosgadive Risk
Task
0.75
T
1.0
0.50
0.25
Instentanerait
0.5-
0.00
2000
4000
Task
Time (t)
0.0
200
400
600
800
10000
1.00
CIFAR Scenario
Chance
1.0
Prospective Risk
0.75
Bayesian GD
Online-SGD
Prospective
0.50
0.5
Follow-Ihe-leader
0.25
Prospective
0.0
0.00
Beyes Risk
200
400
600
800
10000
0
10d00
20000
30000
Time
Time
Figure 2: Prospective ERM achieve good instantaneous and prospective risk in Scenario 2. Left: Instantaneous and prospective risks for problems constructed using synthetic data (see text) across random seeds (which govern the sequence of samples and the weight initializations of neural networks). Instantaneous risk spikes when the task switches for many online learning baseline algorithms. In contrast, prospective ERM has minimal spikes later times and both instantancous and prospective risks eventually converge to zero. Right: Prospective risk for different baseline algorithms and prospective ERM for tasks constructed using MNIST and CIFAR-10 for Scenario 2. In three cases, the risk of prospective ERM approaches Bayes risk while online learning baselines considered here do not achieve a low prospective risk. For comparison, the chance prospective risk is 0.5 for synthetic data and 0.742 for MNIST and CIFAR-10 tasks.
Fig. 2 shows that prospective ERM can learn problems when data are independent but not identically distributed (Scenario 2). For prospective learning problems constructed from synthetic data, the risk of prospective ERM converges to prospective Bayes risk over time. For the MNIST and CIFAR-10 prospective problems, the prospective learning risk drops precipitously. In contrast, online learning baselines discussed above achieve far worse prospective risk. Observe that Follow-the Leader (blue) performs as well, or better, online SGD and Bayesian GD. This is not surprising, while ERM models corresponding to each time t were trained independently, networks corresponding to online SGD and Bayesian GD were training in online fashion; in practice it is often difficult to tune online learning methods effectively [57].
6.2 Prospective learners when data are neither independent nor identically distributed (Scenario 3)
Dataset and Tasks. For synthetic data, we construct 4 binary classification problems with two- dimensional input data (see Fig. 3 and caption for details). For CIFAR-10 and MNIST, we consider four tasks corresponding to the classes 1-5, 4-7, 6-9 and 8- Using these tasks, we construct
For CNNs on CIFAR- 10, if one concatenates the time embedding directly the input images as opposed to concatenating to a layer before softmax, like it is done here, the prospective risk in Fig. 2 (right) is much higher (worse by almost 0.2. See Fig. A.6). The implementation details of time embedding do matter when implementing prospective learners in practice, even if' Theorem is true in general.

---

02
Task
Task 2
Task
Task 4
0.2
Every stops
Class
Figure 3: Left: For MNIST and CIFAR-IO, consider tasks corresponding to the classes 1-5, 4-7, 6-9 and 8-10. Using these tasks, we construct Scenario problems corresponding to stochastic process which a hierarchical hidden Markov model. After every 10 time-steps, a different Markov chain governs transitions among tasks (one Markov chain for tasks I and 2. and another for tasks 3 and 4). This ensures that the stochastic process does not have stationary distribution. Right: For synthetic data, the 4 tasks are created using two-dimensional input data as shown pictorially above. The four parts the input domain are {(x1,22) 1 < 01, < 2), (211 x2) 1 S x1 S 2, and 2 S æ22 S - ((21 - S I1, 22 S -1} and {(T1, x2): : -2 S œ1 S -1 and 1 < x2 S 2}. Colors indicate classes. The hicrarchical hidden Markov model for transitions among the tasks is identical to the MNSIT and CIFAR-10 setting shown on the left.
Synthetic Scenario 3
MNIST Scenario 3
CIFAR Scenario 3
1.0
1.0
0.8
0.8
Prospective Risk
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
2000
4000
2000
4000
10000
20000
30000
Time (t)
Time (t)
Time (t)
Followche-eadder
Prospective
Bayesian
Bayes Risk
Chance
Figure 4: Prospective ERM can achieve good prospective risk in Scenario 3. Prospective risk across 5 random seeds (which govern the sequence of samples and the weight initializations of neural networks). In all three cases, the risk of prospective ERM approaches Bayes risk while number of baseline algorithms do not achieve a low prospective risk. Stochastic processes these problems corresponding to Scenario not have an invariant distribution. This is why a time-agnostic hypothesis (ERM) that is constructed by the baseline algorithms does not achieve a good prospective risk.
problems where the data distribution is governed by a stochastic process which is a hierarchical hidden Markov model (Scenario 3). After every 10 time-tteps, a different Markov chain governs transitions among tasks (one Markov chain for tasks and 2, and another for tasks 3 and 4, as shown in Fig. 3). These choices ensure that the stochastic process does not have stationary distribution." As Fig. 4 shows, prospective ERM can prospectively learn problems when data is both independent and not identically distributed (Scenario 3. Stochastic processes in these problems corresponding to Scenario 3 do not have a stationary distribution. This is why a tine-agnostic hypothesis (Follow-the the--the-eeer Leader) does not achieve good prospective risk, unlike prospective ERM. Appendix G discusses additional experiments for Scenario 3 for different kinds of Markov chains.
7 Discussion
Prospective learning, scenarios which are currently modeled using much stronger (and less accurate) assumptions. These simplifying assumptions have certainly enabled progress in machine learning. But systems deployed built upon these approaches have proven to be extremely fragile in certain real-world settings. Today's machine learning-base based systems fail track changes the data. They certainly do not model how biological organisms learn robustly and effectively over time. We believe characterizing which kinds of stochastic processes are prospectively learnable under which kinds of time-sensitive loss functions will be an important next theoretical step. Developing algorithms, from the perspective of prospective learning, which have theoretical guarantees in practice, will be another next step. Finally, building algorithms that scale and can therefore be deployed in real-world systems, will be important to demonstrate the utility of this approach. The precise real-world applications which prospective learning based methods will outperform PAC learning, remains to be seen.
it, is paradigm of learning that characterizes many real-world
12 As we discussed in Scenario 3, prospective Bayes risk can be trivial in situations when the stochastic process has stationary distribution.
10

---

References
[1] Ben Blum-Smith and Soledad Villar. Machine learning and invariant theory. arXiv preprini arXiv:2209. 14991, 2023.
[2] Joaquin Quiñonero- Candell,,,, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. Mit Press, 2022.
[3] Peter Sterling. Allostasis: model of predictive regulation. Physiology & behavior, 106(1): 5-15, April 2012. doi: 10.1016/j.hhysbch... physbch.2011111 1.06.004.
[4] Xianhua Wang, Xing Zhang, Di Wu, Zhanglong Huang, Tingting Hou, Chongshu Jian, Peng Yu, Fujian Lu. Rufeng Zhang, Tao Sun, et al. Mitochondrial flashes regulate ATP homeostasis in the heart. Elife, 6:e23908, 2017.
[5] Yanping Huang and Rajesh Cognitive science, 2(5):580-599) -93, September 2011.
Rao. Predictive coding. Wiley interdisciplinary reviews.
[6] Martin EP Seligman, Peter Railton, Roy Baumeister, and Chandra Sripada. Navigating into the future or driven by the past. Perspectives on psychological science, 8(2):119-141, 2013.
[7] Martin E P Seligman, Peter Railton, Roy F Baumeister, and Chandra Sripada. Homo Prospectus, volume 384. Oxford University Press, New York, NY, US, June 2016. ISBN 97801993 0988199937449,
[8] M Kearns and L Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. Journal of the ACM, 1994.
[9] Gábor Lugosi and K Zeger. Nonparametric estimation via empirical risk minimization. IEEE transactions on information theory / Professional Technical Group on Information Theory, 41 (3):677-687, May 1995. doi: 10.1109/18.382011
[10] Yann LeCun, Bernhard E Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel. Handwritten digit recognition with back- propagation network. In Advances in Neural Information Processing Systems, pages 396 404, 1990.
[11] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, April 2009.
[12] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pages 1126-1135, 2017.
[13] Joshua T Vogelstein, Jayanta Dey, Hayden S Helm, Will Le Ronak D Mehta, Tyler M Tomita, Haoyin Xu, Ali Geisa, Qingyang Wang, Gido M van de Ven, Chenyu Gao, Weiwei Yang, Bryan Tower, Jonathan Larson, Christopher M White, and Carey E Priebe. A simple lifelong learning approach. arXiv [cs.Al], April 2020.
[14] Rahul Ramesh and Pratik Chaudhari. Model Zoo: A Growing "Brain" That Learns Continually. In Proc. of International Conference of Learning and Representations (ICLR), 2022.
[15] Richard S Sutton and Andrew G Barto. Introduction to Reinforcement Learning. Camgridge: MIT Press, March 1998.
[16] Ashwin De Silva, Rahul Ramesh, Pratik Chaudhari, and Joshua T Vogelstein. Prospective Learning: Principled Extrapolation to the Future. In Proc. of Conference on Lifelong Learning Agents (CoLLAs), 2023.
[17] Vladimir Vapnik. Principles of risk minimization for learning theory. Advances neural information processing systems, 4, 1991.
[18] Deepak Agarwal, Lihong Li, and Alexander Smola. Linear-time estimators for propensity scores. In Proceedings of the Fourteenth International Conference Artificial Intelligence and
11

---

Statistics, pages 93-100, 2011.
[19] Rasool Fakoor, Jonas Mueller, Zachary C. Lipton, Pratik Chaudhari, and Alexander J. Smola. Time- Varying Propensity Score to Bridge the Gap between the Past and Present. In ICLR, 2024.
[20] H Daume, III. Frustratingly Easy Domain Adaptation. In Proceedings of the 45th Annual Meeting of the Association of Compulational Linguistics, 2007.
[21] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1): 151-175, 2010.
[22] Martin Arjovsky. Out of distribution generalization machine learning. PhD thesis, New York University, 2020.
[23] J. Baxter. A Model of Inductive Bias Learning. Journal of Artificial Intelligence Research, 12: 149-198, March 2000. ISSN 1076-9757.
[24] Gido M Van de Ven and Andreas S Tolias. Three scenarios for continual learning, arXiv preprint arXiv:1904.07734 2019.
[25] Matthias De Lange and Tinne Tuytelaars. Continual prototype evolution: Learning online from non-stationary data streams. In Proceedings of the IEEE/CVF international conference computer vision, pages 8250-8259, 2021.
[26] Sebastian Thrun and Lorien Pratt. Learning to learn: Introduction and overview. In Learning to learn, pages 3-17. Springer, 1998.
[27] Guneet S Dhillon, Pratik Chaudhari, Avinash Ravichandran, and Stefano Soatto. A baseline for few-shot image classification. Proc. of International Conference of Learning and Representations (ICLR), 2020.
[28] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In International conference on machine learning, pages 1126-115 1135. PMLR, 2017.
[29] Rasool Fakoor, Pratik Chaudhari, Stefano Soatto, and Alexander J Smola. Meta-Q- Meta-Q-Le In Proc. of International Conference of Learning and Representations (ICLR), 2020.
[30] Joao Gama, Raquel Sebastiao, and Pedro Pereira Rodrigues. On evaluating stream learning algorithms. Machine learning, 90:317-346 2013.
[31] Tyler L Hayes, Kushal Kafle, Robik Shrestha, Manoj Acharya, and Christopher Kanan. Remind your neural network prevent catastrophic forgetting. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part VIII 16, pages 466 483. Springer, 2020.
[32] Thomas M. Cover. Open problems in information theory. JEEE USSR Joint Workshop on Information Theory, 1975.
[33] David Harold Bailey. Sequential schemes for classifying and predicting ergodic processes. Stanford University ProQuest Dissertations Publishing, 1976.
[34] Boris Yakovlevich Ryabko. Prediction random sequences and universal coding. Problems of Information Theory, 24(2):87-96, 1988.
[35] D. Ornstein. Guessing the next output of a stationary process. Israel Journal of Mathematics, 30(3):292 296. 1978.
[36] Gusztav Morvai, Sidney Yakowitz, and Laszlo Gyorfi. Nonparametric inference for ergodic, stationary time series. The Annals of Statistics, 24(1):370-37,, 1996.
12

---

[37] A.B. Nobel. Average reward reinforcement learning: Foundations, algorithms, and empirical results. IEEE Transactions on Information Theory, 49(1):83-98, 2003.
[38] Steve Hanneke. Learning whenever learning is possible: Universal learning under general stochastic processes. J. Mach. Learn. Res., 22:130:1-130:166 2021.
[39] Alexander Rakhlin and Karthik Sridharan. Lecture notes on online learning. _ectss_ooott..ttee 2008.
[40] Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trendy@ in Machine Learning, 4(2):107-194, 2012.
[41] Adam Block, Alexander Rakhlin, and Abhishek Shetty. On the performance of empirical risk minimization with smoothed data, 2024.
[42] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adversaries. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pages 953, 2022. doi: 10.1109/FOCS52999. 2021 2021.00095.
[43] Liangzu Peng. Paris Giampouras, and Rene Vidal. The ideal continual learner: An agent that never forgets. In Proceedings of the 40th International Conference on Machine Learning, 2023.
[44] William Bialek, Ilya Nemenman, and Naftali Tishby, Predictability, complexity, and learning. Neural computation, 13(11):2409-2463 2001.
[45] Naftali Tishby, Fernando C. Pereira, and William Bialek. The information bottleneck method. Proc. of the 37-Th Annual Allerton Conference on Communication, Control and Computing, pages 368-377, 1999.
[46] Cosma Rohilla Shalizi and James P Crutchfield. Computational Mechanics: Pattern and Prediction, Structure and Simplicity. Journal of stutistical physics, 104(3):817-879, August 2001. doi: 10. 10.102//A:1010000 101338991000
[47] Robert E Schapire. The strength of weak learnability. Machine learning, 5:197-227, 1990.
[48] Michael
Kearns.
Thoughts
Hypothesis
Boosting.
1988.
[49] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapmik-chervonenkis dimension. Journal of the ACM (JACM), 36(4): 1989.
[50] Noga Alon, Shai Ben- Nicolò Cesa- BisncBi and David Haussler. Scale-sensitive di- mensions, uniform convergence, and learnability. Journal of the ACM, 44(4):615-631, July 1997.
[51] Vladimir N Vapnik. Statistical learning theory. Adaptive and Cognitive Dynamic Systems: Signal Processing, Learning, Commun ications and Control. John Wiley & Sons, Nashville, TN September 1998.
[52] Nicolo Cesa- Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[53] Chen Zeno, Itay Golan, Elad Hoffer, and Daniel Soudry. Task agnostic continual learning using online variational bayes. arXiv preprint arXiv: 10123, 2018.
[54] Bryan Lim, Sercan Ö Ank, Nicolas Loeff, and Tomas Plister. Temporal Fusion Transformers for interpretable multi-horizon time series forecasting. International journaa of forecasting, 37 (4):1748-1764, October 2021.
[55] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez. Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Informa- tion Processing Systems, 2017.
13

---

[56] Friedemann Zenke, Ben Poole. and Surya Ganguli. Continual learning through synaptic intelligence. In International Conference on Machine Learning, pages 3987-3995, 2017.
[57] Hao Li, Pratik Chaudhari, Hao Yang, Michael Lam, Avinash Ravichandran, Rahul Bhotika, and Stefano Soatto. Rethinking the Conference of Learning and Representations (ICLR), 2020.
for fine-tuning. In Proc. of International
[58] Tilmann Gneiting and Matthias Katzfuss. Probabilistic forecasting. Annu. Rev. Stat. Appl., 1(1): 125-151, January 2014.
[59] Leslie Valiant. Probably Approximately Correct: Nature's 's Algorithmss for Learning and Pros- pering in a Complex World. Basic Books, June 2013. ISBN 9780465032716.
[60] Masashi Sugiyama, Matthias Krauledat, and Klaus-Robert Müller. Covariate Shift Adaptation by Importance Weighted Cross Validation. Journal of machine learning research: JMLR, (May):985-10055, 2007. ISSN 1532-4435 URL http: //ww///wwwwwo/ jww..jmww...........//../..m parg/apers/
(asiumm//suiiymmaaa a/ wt/g/uggyyeo yama077..07..... pdf.
[61] Ashwin De Silva, Rahul Ramesh, Carey Priche, Pratík Chaudhari, and Joshua T Vogelstein. The value of outttf-distributtoon data. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, 2023, URL https: https:htt//ooett pttp:///eoccceeee.e/ooom. mlr .pres//
pages 7366-7389, v202/de- sil aala..l..........m............ html.
[62] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learming Research, pages 1126-1135, International Convention Centre, Sydney, Australia,
2017. PMLR.
[63] Andreas Maurer and Tommi Jaakkola. Algorithmic stability and meta-learning Journal of Machine Learning Research, 6(6), 2005.
[64] Jonathan Baxter. model of inductive bias learning. J. Artif. Intell. Res., 12(1):149 198, March
2000.
[65] Bernardino Rorera-Paredes and Philip Torr. An embarrassingly simple approach to zero-shot learning. In International Conference on Machine Learning, pages 2152 2161. PMLR, June 2015. URL httpp::/pproceeeeeee
mlr, wal.r.pres///ee.. press/v37 wawomeraappreeee1555 html.
[66] Jake Snell, Kevin Swersky, and Richard Zemel. learning. Advances in neural information processing systems, 30, 2017. ISSN 1049- 5258. URL https: httts::/pprceeddnngg www.rddnnnnnnnninnnneoeeeee cc/pappr_aaeeeeeeeeeeeeee supperffiles files www.ss/aaeeeeeeeeeeeeaaaaaaaaeee httppppppp/////////// 115aa677746112222224444eaaccoo/2
Prototypical networks for few-shot
Abstract.
[67] Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine.
Online Meta-Learning
In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1920-1930. PMLR, 2019.
[68] Sebastian Thrun. Lifelong learning algorithms. In Learning to learn, pages 181-209. Springer, 1998.
[69] Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2011.
[70] Mehryar Mohri. Foundations of machine learning, 2018.
[71] Fotios Petropoulos, Daniele Apiletti. Vassilios Assimakopoulos, Mohamed Zied Babai, De- von K Barrow, Souhaib Ben Taieb, Christoph Bergmeir, Ricardo J Bessa, Jakub Bijak, John E Boylan, Jethro Browell, Claudio Carnevale, Jennifer Castle, Pasquale Cirillo, Michael
14

---

Clements, Clara Cordeiro, Fernando Luiz Cyrino Oliveira, Shari De Baets, Alexander Doku- mentov, Joanne Ellison, Piotr Fiszeder, Phillip Hans Franses, David Frazier, Michael Gilliland, M Sinan Gönül, Paul Goodwin, Luigi Grossi, Yael Grushka-
Mariangela Guidolin, Massimo Guidolin, UIrich Gunter, Xiaojia Guo, Renato Guseo, Nigel Harvey, David F Hendry, Ross Hollyman, Tim Januschowski, Jooyoung Jeon, Victor Richmond R Jose, Yanfei Kang, Anne Kochler, Stephan Kolassa, Nikolaos Kourentzes, Sonia Leva, Feng Li, Konstantia Litsiou, Spyros Makridakis, Gael M Martin, Andrew B Martinez, Sheik Meeran, Theodore Modis, Konstantinos Nikolopoulos, Dilek Önkal, Alessia Paccagnini, Anastasios Panagiotelis, loannis Panapakidis, Jose M Pavía, Manuela Pedio, Diego J Pedregal, Pierre Pinson, Pa- tricia Ramos, David E Rapach, James Reade, Bahman Rostami- Rostami-Tabar, Michal Rubaszek, Georgios Scrmpinis, Han Lin Shang, Evangelos Spiliotis, Aris A Syntetos, Priyanga Dilini Talagala, Thiyanga S Talagala, Len Tashman, Dimitrios Thomakos, Thordis Thorarinsdottir, Ezio Todini, Juan Ramón Trapero Arenas, Xiaoqian Wang, Robert I. Winkler, Alisa Yusupova, and Florian Ziel. Forecasting: theory and practice. International journal of forecasting, 38(3):705-87) 871, July 2022. ISSN 0169-2070. doi: 10.10166j.ifforecast2221.111 https://ww.scceenceee www.:eccieeececc....m http://tcw......a.aaaaaaaaa////a
URL
[72] B K Ghosh and P K Sen. Handbook of Sequential Analysis (Statistics: A Series of Textbooks and Monographs). CRC Press, edition, April 1991. ISBN 9780824784089. URL https:
//play. Sapay-gooe google. e com/ sttoeebookket /ttp:/aallddddddddddaeeeee
[73] Nicolo press, 2006.
and Gábor Lugosi. Prediction, learning, and games. Cambridge university
[74] Chen, Yulia Rubanova, Bettencourt, and D Duvenaud. Neural ordinary differential equations. Neural Information Processing Systems, 31:6572 65822, June 2018.
[75] Ailing Zeng, Muxi Chen, Lei Zhang, and Qiang Xu. Are Transformers effective for time series forecasting? Proceedings of the AAAI Conference Artificial Intelligence. AAAI Conference on Artificial Intelligence, 37(9): 111-111128,1 June 2023.
[76] Alexander L Strehl, Lihong Li, and Michael L Littman. Reinforcement learning in finite MDPs: PAC analysis. Journal of machine learning research: JMLR, 10184):2413-2444 2009, ISSN 1532-4435,1533-7999 Sareh1199a/strehh095.. pdf.
URL https:/ htops://wwww... jwwr. org/ wttppppppss/ooommeelllll
[77] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv [cs.LG], May 2020. URL http: //arxiv. wwwg/rgg/////eeeeeeeeoooeeeeeeee
aaa//b///000 01643.
[78] Saurabh Kumar, Henrik Marklund, Ashish Rao, Yifan Zhu, Hong Jun Jeon, Yueyang Liu, and Benjamin Van Roy. Continual learning computationally constrained reinforcement learning. arXiv preprint urXiv:2307.04333 04445, 2023.
[79] Annie Chen, Archit Sharma, Sergey Levine, and Chelsea Finn. You only live once: Single-life reinforcement learning. Advances Neural Information Processing Systems, 15:44784114797, 2022.
[80] Alex Sherstinsky. Fundamentals of recurrent neural network (RNN) and long short-term memory (LSTM) network. Physica D, 404(132306):132306 March 2020.
[81] Mantas Lukoševičius and Herbert Jaeger. Reservoir computing approaches to recurrent neural network training. Comput. Sei. Rev., 3(3):127-149, August 2009.
[82] Carl Edward Rasmussen and Christopher K Williams. Gaussian processes for machine learning. Adaptive Computation and Machine Learning Series. MIT Press, London, England, June 2019.
[83] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279-292, 1992.
15

---

[84] Jonathan Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 19:149--198. 2000.
[85] Steve Hanneke. Learning whenever learning is possible: Universal learning under general stochastic processes. The Journal of Machine Learning Research, 22(1):5751-5866, 2021.
[86] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint urXiv2230.099288, 2023.
[87] Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rívière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on gemini research and technology. arXiv preprint arXiv:2403.08299 2024.
[88] Yue Deng, Wenxuan Zhang, Sinno Jialin Pan, and Lidong Bing. Multilingual jailbreak chal- lenges in large language models. arXiv preprint arXiv:2310.06-777 2023.
[89] Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint 12.00:2/ 2021.
[90] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-2488 2022.
16

---

Acknowledgement
This work was funded by grants from the National Science Foundation (IS-21141164, CCF-2212519) and the Office of Naval Research (ONR) 100014-22-1-2555 RR was funded by a fellowship from AWS Al to Penn Engineering's 's ASSET Center for Trustworthy AL ADS was supported by fellowship from the Mathematical Institute for Data Science (MINDS) at JHU. We are grateful to all those who provided helpful feedback on earlier drafts of this work, including Marlos Machado.
A Isn't this just...
When we describe prospective learning to people the first time, they often wonder how it is different- both conceptually and formally-from other previously established learning frameworks. In fact, for many of them, the English language descriptions are seemingly identical to those which describe prospective learning. However, the English language often imprecise and this has created a lot of confusion among both theoreticians and practitioners as to the precise differences, potential benefits and pitfalls, between different learning frameworks. Here, we provide detailed formal distinctions between prospective learning and other related learning frameworks. Table A. summarizes the key distinctions between several machine learning frameworks, with further details provided below. The key difference between prospective learning and all other learning frameworks mentioned below is that in prospective learning, the hypothesis can make an inference (or take an action) arbitrarily far in the future. Certain versions of forecasting also have that property (probabilistic forecasting [58]), but forecasting has several other distinctions.
Table A.1: Comparison of different machine learning frameworks in terms of the distributional assumptions on the data. Task IID indicates that data within a task are IID, and that tasks are IID from some meta- meta-distribution. Loss characterizes whether the assumed loss function is instantancous or time-vare tmeevarying. Optimal hypothesis indicates the total possible number of different optimal hypotheses (assuming each hypothesis has a unique risk). Data availability indicates whether the data are available all at once (in batch), after each task arrives (task sequential), or one data sample at time (sequential). The answers are given for typical settings, further details are available in the paragraphs below.
Framework
Data Distribution
Loss
Optimal hypotheses
Data Availability
PAC Learning
IID
Instantaneous
Batch
Transfer Leaming
Change Point
Instantaneous
1-2
Batch
Meta Learning
Task IID
Instantaneous
# Tasks
Butch/Sequential
Lifelong Learning
Task IID
Instantancous
Tasks
Task Sequential
Online Learinng
None
Instantaneous
Sequential
Forecusting
Stochastic Process
Fixed horizon
Time steps
Butch/Sequential
Reinforcement Learning
Markov Decision Process
vary-ng
Sequential
Prospective Learning
Stochastic (Decision) Process
Instant. Timmevvrri-
#Time steps
Any
A.1
...PAC learning?
PAC learning [59] is a special case of prospective learning when the stochastic process is time- invariant (meaning the data are IID) and the loss is fixed. Also, it is only concerned with batch data. It is an interesting question as to whether prospective learning as we have defined here is useful for IID data. We do not know yet in general. In Appendix 1. we provide a simple example where prospection turns out to be beneficial, even in the IID setting. More broadly, we wonder whether the viewpoint proposed in this paper might lead to novel algorithms for solving learning problems on IID data that do not have closed form solutions.
A.2 transfer learning?
In transfer learning [21], including domain (covariate) shift (adaptation) [20, 60], and out-of- distribution (OOD) [61] learning, there are two distributions, source and target distribution; thus, the distribution changes only once, rather than potentially once per time step. Depending on whether the goal is to perform well only on the target, or both the source and the target, there are one or two optimal hypotheses. Also, that the distribution has changed is often known (though not always, as in OOD learning).
17

---

A.3 ...meta-learning?
Meta-learning [62, 63] is similar to multi-task learning [64], and includes special cases zero- shot [65] and few-shot learning [66]. Here, the data are Task IID, meaning that the distribution within task is IID, and the distribution of tasks themselves is also IID, rendering it impossible to predict future distributions very well (the best one could do is guess the next task is whichever task is most likely). Typically, that the task/distribution changes is known, but not always. In classical meta-learning, data are available in one batch, but in online meta-learning, data are sequentially available [67]. The goal is to perform well on the next (unknown) distribution, opposed to all future (unknown) distributions as in prospective learning.
A.4 ... ...liffllon learning?
Lifelong (continual) learning [14, 13, 68] nearly identical to online meta-learning [67]. However, the data are typically available in one batch per task. The goal is also a bit different, rather than performing well on the next distribution, in lifelong learning, the goal is also to continue performing well on previous distributions. Often, the learner is aware that the distribution shifted [24], but not always [25].
A.5 online learning?
A key property of online learning [69] is that there are no distributional assumptions [70], and therefore, the goal is not about generalization error. Instead, performance is evaluated relative to the best fixed hypothesis could have done up until now. Also, in online learning. the environment is often adversarial.
A.6 ...foccsstning?
Forecasting [71], time-series or sequential analysis [72, 73] assume the data follow stochastic process, much like prospective learning often does (e.g., Scenarios 2 and 3), and therefore, the number of optimal hypothesis can be equal the number of time steps. However, in forecasting, the loss is associated with a fixed (pre-specified) horizon, or several horizons [54]. Forecasting also often assumes parametric model, but not always [74, 75]. Probabilistic forecasting [58] can also predict arbitrarily far in the future by iteratively updating its probabilistic forecasts. However, this is prone to numerical errors, evidenced in sequential Monte Carlo.
A.7 ... reinforceemmet learning?
Reinforcement learning (RL) [15] is only concerned with situations where there is control el- ement, that is, the hypothesis chooses an action (which potentially impacts future distributions), rather than merely an inference (which does not). Thus, it excludes Scenarios 2 and 3. Moreover, RL theory focuses on Markov Decision Processes [76], whereas PL operates on larger classes of stochastic decision processes, including non-Markov processes (e.g., see examples of non-Markov stochastic processes in Scenario 3). Depending on context, PL also considers loss functions that instantancous. Classical RL assumes data are sequentially available, yet offline RL operates in batch mode [77]. Perhaps most importantly, in classical RL, the optimal hypothesis (policy) is not time-varying, though recent generalizations are forthcoming [78]. Also, in RL, there are typically many episodes, whereas in prospective learning there is only a single episode (though single-episode RL is also forthcoming [79]).
To elaborate on the first point above, assume that our decisions do not impact the future, but the optimal hypothesis is time-dependent, that is hj * hT for some # f'. Why would we care about the risk for any t' > t (like RL, but not like online/continual learning), given that our decision at time t does impact Ze at all? We only ever incur the current loss, that is, f(t, he(x))) yr). So, would seem that as long as we minimize this current loss, there is no reason to care about any future loss. First note that minimizing the expected cumulative future loss is sufficient for minimizing the loss averaged over a finite future horizon, this is formally shown in Corollary 2. But more importantly, these two problem settings are rather different. Minimizing the prospective risk (expected cumulative future loss) forces the learner to learn/model all the different modes of variation in the data. Missing even a small (low energy) mode of variation can lead large prospective risk. If the learner only seeks to minimize the current loss, it need not have any representation of how data evolves over time. will not be a good prospective learner. Recall that online learners (which minimize the current loss) have large worst case regret. Prospective learning effectively evaluates the regret over the infinite future horizon. The two settings are closely related if data evolves slowly, as argued in Fakoor et al. [19].
18

---

A.8 r..uurereent neural networks?
Recurrent neural networks (RNNs), including Long Short Term Memory (LSTM) networks [80], as well as echo state machines and liquid state machines (and other reservoir computing techniques [81]] and Gaussian Processes [82] seem like they are solving prospective learning problems. Indeed, they are all reasonable architectures for satisfying the conditions of Theorem Insofar as they do satisfy those conditions, then they are indeed prospective learners.
B
Calculations for scenarios in Section 2.1
B.1 Can learning benefit from prospection in the IID scenario?
Consider Scenario where the learner returns the hypothesis hy h = threshold(ft > 0.5) for all f' > where Pr: = Ex= is the maximum likelihood estimator (MLE). Alternatively, if we assume prior distribution Beta(a, (3) over p. then the resulting maximum a posteriori (MAP)
2-1-1-2- estimate is ++2 2,- We define second prospective learner based on MAP that returns
the sequence h2. (he, :..,, where he (hreshold(fr > 0.5) for all future times beyond t. If the prior distribution has small divergence with respect the true posterior distribution, then the second learner converges faster to the Bayes optimal risk; for poor choice of prior, the convergence show that
is slower. However, in such situations, prospection and incorporate "time" to result in faster convergence to the Bayes risk.
modify the MAP-based learner to
Let , ye be the IID sample sequence observed up to time The idea here compute the rate of change Ap(t) of the MAP estimate at time which is given by,
Ap(t) MAP()1, vi) MAP( .e--1
(10)
Taking expectation both sides of Equation (10), and plugging in P. MAP()).... ...... Ut) for the true parameter p, we construct the following estimate for Ap(t).
(a 1) tp
(a (1-
Ap(t)
(a - (3-
(a- 11-1111)---1
Using this rate change, we may forecast the estimate py at time 1' follows.
pv Pr. +
Ap(s)
Scenario 1 Independent and identicalyy distributed data
1.0
MLE
MAP (prior a 12. 16)
0.8
Prospective risk
proMAp (prior a 12, B 16)
Bayes risk
0.6
Chance
0.4
0.2
0.0
10 Time (t)
15
Figure A.1: Prospective risk of MLE (blue), MAP (purple), prospective MAP (red) and random- chance (orange) based learners with respect to time. Both MAP and prospective MAP estimators assume prior distribution of (12 16) over p.
We refer to this as the prospective MAP estimate. Based on it, we the hypothesis to be hy threshold(f.. > 0.5) for all future times beyond f. In Figure A.1, we plot the prospective risk the MIE, MAP, and prospective MAP-based learners. Due to an unfavorable prior, the MAP. based learner converges slowly. However, prospective MAP-based learner manages to leverage its forecasting achieve faster convergence rate despite having the same prior the MAP. This shows that we can indeed benefit from prospection even in the IID case.
19

---

B.2 Bayes risk for a Markov chain
We would like to compute the prospective Bayes risk, when the evolution of the samples is governed
by a Markov transition matrix where P(Y++1 = 0 Yt = 0) = 8n and P(Yc-1 = V2 = 1) = 01, i.e. the transition matrix is
Bo 0 01
1 80
The probability distribution at time e' is given by p -t (2), 1 - 20)² The eigenvalues of the transition
11
6
0
Figure A.2: Markov chain describing the evolution of data
matrix are = 1 and A2 6n + 0 with the corresponding eigenvectors being (1,1) T)_ and (0n - 1,1- 01) Diagonalizing we get
1d
1 0o 1
1
80 - 1-01
1 0
A -1
[
01
1- 01 + (1 -0)
(1 (1- 00) XB
22 0p-
01)
1+0 (1 00)
(1- 0o) X3
which implies that the probability distribution of the state at time t is
1 01 80
1 - ((1 (1) 21) (1 01)a))
Te' - - 01) Hence, the optimal sequence of hypotheses is h = (hi+1, 1442: where
(2 12-66 00 01)
-11
h arg max (() (e(0.1)
with Bayes risk equal to R limy T Σx st minie (0.1) (1). This reduces to
RC
01) min 0, 01);
the second term in the expression of vanishes as T + co. If 0n 0.9 and 0 0.5, then R 1/6. we restrict our attention to the case where On 81, the discounted Bayes risk reduces to
(1-y) Σ
x---1 = (1-1)
7 g-t-1
X/
(1 =(1-7) 2(1 7)
A2
2
2(1
1A2 7)
#=++1
s=++1
Substituting 0g- 01 = 0.1, the discount risk for 7 = 0.9 is 0.357.
B.3
Prospective learning in Scenario 4 when the future depends upon the current prediction
There are two types of prospective learners-one that passively observes the environment and makes inferences and another that acts on the environment and influences
Scenario 1, Scenario Scenario 3 fall into the first category which is the primary emphasis of our paper. Scenario presents prospective learning problem where the learner can influence the future realizations of the stochastic process through its decisions.
Our prospective learner is inspired from reinforcement learning, where the current state is y-1, the action is he and the next state is Yz. The reward at the thh time-step is r(f, ht-1. vt+1) 1 (he41 = yt+1}
result selecting action he+1 1 given that the previous output was yts and next output 31+1. The learner estimates the transition matrix corresponding to the MDP for each decision hX41(X++1) {0, 1} using a similar procedure as that of Scenario 3,
0
1 0
Vks E (0.1): (((K)
8
0%
20

---

where 0 = d, E [0, 1J2 after I time steps. Using this estimate of f', the learner solves for the value function (corresponding the discounted prospective risk) that satisfies
Qe(yt,lut1)
Σ WE (0.1)
P(1+1 =1-1==1: Vi yt, hut1 hi) (T(t, (441.)) + mmax (v,
=f, (he44h)))
The value function can be solved using value iteration, iteratively until convergence. For given f', Banach's fixed point theorem guarantees this procedure will converge to optimal value function in the tabular setting [83]. Once we have the Q-values Qt, we can use it to take actions. The optimal action time e' is arg max, Q(w, h). However, unlike reinforcement learning, we not know ye for t' > and we must instead make sequence of decisions using state yt- The sequence of decision made by the learner is h
(he+1....) where
Ry
II (1 s=t+1
W; = (1 yr, U6) iie. Ty is the estimated distribution over the state time t', and
h141 arg max n. Qe(, h).
In Fig. 1, we have used 9o 01 0.1 and discount factor 0.9. We find that this learner approaches the Bayes risk (0.357 which we calculate in Appendix B.2).
C Prospective ERM for discounted losses
Like we discussed in Scenario 3, in order to prospect meaningfully for some stochastic processes, we might need to consider discounted future loss, e.g., the one in Eq. (4). Theorem was proved only for the averaged future loss in Eq. (1). Here, we sketch out the proof of an analogous theorem for the discounted loss. Let
(1-
(h,
8-1-1 ((h)(r)))
8=t+1
where x:yxy 00, 1] is a bounded loss function and 0 < y < 1 is a constant. In general, we can use a probability measure (r()) supported on integers [1.....T} to write the loss as
4 Z:H
Σ (7) (h)s))) s=t+1
(11)
The averaged loss in Eq. (1) corresponds to (155) = 1/r for all s. The discounted loss above
corresponds to (!?") (1-7
prospective learning, we are interested in the case when r + oo and therefore let us define
(, Z:p) lim sup el (T). 7-000
where denotes the collection 1,2 We can define (e(1;;) p) and Ri (j)) for this discounted loss using similar expressions those in Eqs. (2) and (3). For clarity, let use the notation Re (h, 1/7) (h(h) and Rt (1/r) = R2 for the prospective risk and prospective Bayes risks corresponding to the averaged loss corresponding to u = 1/T.
Corollary (Prospective ERM is strong learner with discounted losses). Let the assumptions of Theorem hold. If there exists constant >> 0 such that VZ E Z,
(h (x) S (R, 1/7) R[(1TT) VEEN Hi.
(12)
ie.. if gap the risk for the discounted loss is dominated uniformly by the gap in the risks for the averaged loss (over all realizations of the stochastic process), then prospective ERM implemented Eq. (8) (implemented with the averaged loss) a strong prospective learner, iee. its discounted risk Rd (h, u) converges to the discounted Bayes risk H2 (1)).
21

---

Proof. The assumption in Eq. (12) ensures that
P ([rch..)) RI (m) 2 <t) s
1/7) 1
26)
for any and t. The right hand-side is shown to converge to zero in the proof of Theorem 1 and therefore the left-hand side also converges to zero.
corresponding Theorem 2 also holds for the discounted future loss. Note that Theorems 1 and also hold a slightly general setting when the measure (x²)) (w) a random variable that depends upon the realization of the stochastic process w ft.
D An illustrative example of prospective ERM
Suppose we have stochastic process such that Z, ~ Pit mod T) for some known period T, i.e., data is independent across time but not identically distributed, and the loss function ftt,,, -.- is time- invariant. Scenario is a special case with = 2. Assume that we can find countable hypothesis class 9 that contains the Bayes plug-in estimator for each pt with 1 E (I....,T) T). Then Hr (h: : T = h2 and h2 E G Vt) satisfies Eq. (9), and is also countable. This implies consistency and uniform concentration of the limsup for sequences in some sub-classes {He))=1 that expands to Hr- Note that even if we do not know the period, we can still implement prospective ERM using the hypothesis class UTeN this is countable set. Prospective ERM is therefore strong prospective learner if the period 1' is bounded.
Remark 4 (Implementing prospective ERM for periodic processes). If G has a finite VC- dimension, choosing H₂ = Hr for any t > as the increasing sequence of hypothesis classes in Theorem guarantees the existence of limm-+oo E E(s, (oss)) ys). We can therefore choose us = t in Eq. (7) and thereby select
1 (ss (o(
i arg min NEW,
in Eq. (8). For Hi My selected above for the periodic process, this is identical to Eq. (5), In other words, implementing prospective ERM for a periodic process boils down to solving T different time-agnostic ERM problems, each using data {= precisely the prospective learner we used for the example in Scenario 2 and Fig. 1.
& (1, T). Observe that this is
Remark 5 (Sample complexity of prospective ERM for periodic process). We calculate the sample complexity by exploiting the relatedness of the different distributions in the periodic process. First assume L > T, i.e., least one sample from each distribution is available. We again pick Hi = Hr for all t >> T. Let us assume that h E G for all times t. Let C C(e/16, g") denote the covering number of hypothesis class of T-length sequences of hypotheses G ((h,...,h) h)) h E 9} using balls of radius e/16 with respect to loss &. Then, using Baxter [84, Theorem 4] we can show that, if
4C(e,
16T
12 max
द log
(13)
8
2
then for prospective ERM in Eq. (8) we have
E [e](
S
lim
IE
Re((i) ACHr
inf
+ 2e,
10000
with probability least 1 1-6 8. The sample complexity in Eq. (13) is dominated by the first term in the curly brackets; Baxter [84, Lemma 5] shows that C(e, G s (C(c, ())² Sample complexity of prospective ERM grows most linearly with the period T', one would expect.
Remark (Exact sample complexity for a periodic binary classification with one-dimensional Gaussian inputs). Let the period of the stochastic process be T = 2 with inputs X. E and outputs Y. E (-1,1). Suppose Y; ~ Bernoull((.5)). The distribution (Xx, Y, y) is a Gaussian with mean y/ A(t mod T') and variance o², In words. for even times the mean of the Gaussians are shifted to the right by A. Consider the fime-invarian squared error loss É(s, ÿ. y) (ø - y)². Choose G ==1 {1A: : E ((-oc, c): no): e E [R}}} to be the set of predictors for Fisher's linear discriminant (FLD); the prospective learner selects each element of its hypothesis from g. The calculations in
De Silva al. [61] for FLD can be used to show that if H. = {(h, h h....) E G) for all times t, then a time-agnostic ERM has risk
E [h) 1/2 (A/(2T) - -//0///////--))))))/ + + (-A/(20) -1/o)],
22

---

where 4 is the Gauss error function. But if Ha (111,41, hi, h2....) ). 11 E 9 for all times 4 then prospective ERM can achieve Bayes risk
(h) = (-tm/(26) 1)) 1))-1/2 ((-w/o) [R]]]
Remark 7 (Hidden Markov Models (HMMs)). Suppose Z is sampled from an HMM whose hidden states evolve according to -ddordee -on-ennogess Markov process with finite state space. Select a hypothesis class Hg that consists of sequences E My such that each à satisfies
Vt N: A1 E & and,
11,, N: if ht hi Vs E (1.....k) k). then hes +h++11 htg+
This is the hypothesis class that contains sequences of predictors that depend only on the past predictors. If we assume, as above, that G is countable, then is Mg. And it also satisfies Eq. (9) because of the -orde Markov property. We can therefore implement prospective ERM using H4 as the hypothesis class. Observe that in the case when the Markov process underlying the HMM deterministic, our example models the output from an auto rego-segressive language model that uses greedy decoding. The length of the context window is k, the hidden state of the HMM is the logit each step (the next hidden state deterministic function of the previous &s ones), and the output of the HMM Z is the next token. Our theory therefore shows that the output of such model is prospectively learnable if the learner has access to the sequence tokens.
E
Proofs
E.1 Proof of Proposition
Let X' = (-1,1} and y {0, 13- Consider two distributions and (Fig. A.3):
P1(X = x) = P2(X =
Ve,
0
if x
Pi = 1|
0
if
1,
1 A
if r
Pa(Y = x=
if fr -1
In other words, the inputs have the same marginals but the labels are flipped between Pi and Pa. and Zze ~ P2 where E N. Let G be any hypothesis class and let l(s, ú. = 1 * y) be the time-invariant zero-one loss. The agnostii learner uses a sequence of hypotheses (Iu) where = by v, make predictions at all times. The future loss is
Consider stochastic process Z such that Z2e+1
E+22T
(h, Z) lim
Σ ((s,ho(Xe)) = (h) R2(h) 8=1+1
2T
almost surely; here R; (h) and R2(h) risks data from distributions Pi and odd and even times, respectively. The last equation follows from the fact that (h) = 1 - (h) because the labels are flipped. Prospective Bayes risk zero if the hypothesis class G contains the Bayes optimal hypotheses for each of the two distributions. The future loss evaluates to 1/2 for all realizations and does the prospective risk. The prospective risk of hypothesis sequence that makes random predictions (zero or one with equal probability at each instant) is also 1/2. This stochastic process is not weakly prospective learnable.
0
Figure A.4: A simple stochastic process that weakly but not strongly prospectively learnable.
P
Pr
==0
y
Figure A.3: A simple stochastic process that is not weakly prospectively learnable.
23

---

Now consider the two distributions shown in Fig. A.4,
P =X= Pa(X x)
Ve,
3
if x - 0
P1( 1 1| 2)
if = L, 1 1 0
if 2 0 1 0
PY 1 1 X 2)
=
Inputs are supported on the set {-1,0, 1} this time. Again consider a stochastic process Z such that Z2c+1 Pi and Zz: P2 for E N. For time-agnostic learner, since its hypothesis h at each time step has to predict incorrectly at = 0, we have R1 (/) + (h) 2 3. The future loss is
(1h,
lim 700 2T
((s, Y.) R1 (b))) 3 s=++1
Σ
almost surely. follows that the prospective risk (e)h) 2 3/ for any hypothesis. Prospective Bayes risk is again zero and therefore this stochastic process is not strongly prospectively learnable. It is however weakly learnable.
A hypothesis that predicts 9 = 11 with equal probability has n2 0.5. If the data contains samples for æ E {-1, ERM will select hypothesis that minimizes the empirical risk which necessitates that l(1) = 0 and 4 ()11) 1. Therefore R1 (1) + B2() < 3 +e, since à predicts correctly at J = +1, and incorrectly x = 0 exactly one of the two distributions. The constant can be chosen be 1/2 after receiving data from timesteps. The probability with which we not get samples at æ or at 1 1 3 3-3+++1 after time steps. This learner is therefore better than the chance learner whose risk is St and it a weak prospective learner. This shows that there exist stochastic processes that are weakly prospective learnable using time-agnostic ERM but not strongly.
1, is 2 3 Therefore the probability that R1) R2(h) S 3 + is at least
E.2 Proof of Theorem
We first show that for each 7 Z, if Eqs. (6) and (7) holds, then the risk of estimator in Eq. (8) converges in probability the Bayes optimal, i.e.
P (((a())))
< 1. Rt
By taking
t= max { t (Ro(h(()) - R2 < 2 1 w' w'24,E2)
<
we can trivally show that the strong prospecitve learnability of estimator in Eq. (8) holds over the family Z.
We first state a lemma that gives a choice of random hypothesis h(9) o( converging to the Bayes optimal risk under the consistency assumption. First we define the shorthand
Cm (1) = m h(,,))
Lemma 3. For stochastic process Z, for an increasing sequence of hypothesis Hi S H2 .... such that the consistency condition in Eq. (6) is satisfied, for any satisfying uı I t, - there exists (44) E oZgr), M4-valled random variable, such that
sup Ue 500
em (0) Zze - Rt +
(14)
almost surely.
Proof. By Eq. (6), there exists (() E c((g))) Hi-valued random variable such that
[1) Rt =
lim 4000
24

---

Here, A()) E (Z(zs) means that ((() is constant on the set (Zgr zge). By the assumption on (() we have
heH, (e(h inf Re(h) 2 Ri
almost surely. We can choose a sub-sequence (ikh) such that E [Ry, (h(w)) Hijs - < For all random variables (1)) satisfying the above assumption, the bounded convergence theorem implies that
B[Re(h!()) Ri]]
13
lim sup em (1) Z5g
Ri
13
E
lim
sup Smgro
em (m((1(())
Zzz
IE [R]]]
10000
lim
E
E
sup
em (1)
Zzz
R2
In particular, this implies that for any integer there exists an integer in such that
E
E sup
Cm (m) B3
Rie
E RR (1
RRje +4 $2x4
Sm
By the definition of limsup, we have
(1)) Zge
2 2 (E( 2) Z5i 2
sup
and therefore we can use Markov's inequality to get
E
sup
em (m)l) -zsin
- 1.j. > 2(1/2)-
Biy Imi0o
F.
T
sup em(libul) Dic 500
Rij
2(1/2)
k=0
00
X..
2(1/2)
k=0
Therefore, by Borel-Cantelli lemma, with probability one, there exists a (random) integer kn such that for all 2 kp.
E sup em (he)e))
Zgin
R2 S 2(122)
Mig Smc
We will now scale ig. ju by some integer hy such that Jk, S t. This ensures that Wix S me and Ma, C H4. This scaling is necessary to relate the "empirical estimate" of the lim sup of h to the actual lim sup of (t), To that end, define
k = maxfk E NU max jk) tt.
Since in S do and js S xc, we also have limu--so = cc. Let au 2(1/2) and notice that az - We can construct an integer-valued random variable to such that for all 2 to, we have hy 2 ko, and therefore
sup usp, Sm
em (hibi) Zzim
Rie, au-
Now choose (1) ((mne) for every & E N. Since jk. I t, we have Hin, S Hi and (ZZs,,,) 5 (7 This implies that ((ine) is an He-valued random variable and ((a)) a((z))) Also, since i,, < and {u 1 non-decreasing, we have uik, S Ut for all t Hence, with probability one, Vt 2 tg.
E
em (n Smc
sup
Zsin
Rír, SE
sup usg, Smcoc
em (1) Zzjjn
- RS < at
25

---

Since og - 0, we have
sup My Sm
cm (1)))) Zisik
Rig -t a.s.
Again using the bounded convergence theorem,
I
sup Soc
(m())))
Ri - a.8.
Now we continue the proof of Theorem by exploiting the convergence the empirical lim sup to the true lim sup. We construct sub-sequence of integers such that %i in Eq. (7) decays exponentially. Markov's 's inequality implies that
max NEHi,
(e 2)
max
em em(h))
wis Smsh.
-
E8 max NEH:
Ee 2)
max
cm em(h))
<0.
ui Smsk
By the Borel-Cantelli lemma, with probability one, there exists 1 E 1., random, and 1 E F, such that vt 2 41
max hEM
Z) max Ui, Smsi,
em
S Th:
Let jt max by f), then have ij. - 0o. Since ij, S f, have
& (h, Z)
max em (m()) _ (e 2) "iy Smst
max Wiy,
Cm (h).
SmSin
Construct a random variable 12 such that Vt 2 12, we have je 2 4 Hence, we have for all 2 f2.
max NEH
Ee(h.
mig Smst cm(l1)
max em (hi
$ max he hEHlg
Eeh,, 2)
max wiye
cm (m))
Smsk,,
I VTy."
Let it ij. and notice that since we have it - we also have it S t. This gives sub-sequence that depends only on n.. Then, with probability one, Vt 2 le
max bEH,
Ee(h, 2)
max us Smst
em (m(h)) S TT.
Let (o where (0)) (Zgg)) is a Hi, -aalued random variable chosen as in Lemma 3 with Hr chosen to be Hi, and un chosen to be ui. Since ((1) (Z(g)) with probability one, for t t2.
((( 2) < max em (h) + w
my Smst
em (h) + /v
max
Mr, Smgt
(1) -TT..
sup
My, Sm
Hence,
E ( 2) Zgg
em (1(( Zzg +0
sup
Ui, 5m500
almost surely. By Lemma 3, we have,
E (1) 2) Z50] - R2 +
26

---

almost surely. Hence, by the bounded convergence theorem,
lim 00000
(E (((())))
2) Z ni)
lim
E [(th Z50 mi]
t1000
which implies that
P [ 172 2 8)
E E E(h (1) 2) 1g(
Hi
+ 0.
We have therefore proved that (0) strong prospective learner.
E.3 Proof of Theorem 2
This construction follows closely with Hanneke [85, Section 4], and omit some details here. For finite class H of sequence of hypothesis, we give a possible choice of 24 with
lim E
sup max (h,, Z)
max em em((h)
=.
(15)
#2e hEH
for process the finite family 2. For a data sequence a (=e- = (8.. and hypothesis sequence h H. we define
(2) min IEN:t2u
sup 55m
(m) v max (m) + 2 uSmse'
and
ur (z) max v E fI, 1) (2))
ue [/((z) (z)
min uf (z);
NEW
note that H is finite and therefore the minimum exists. For the stochastic process Z, let
up (6, 2) max {u E (L.....() Fazz (u, (z) 2u) = 1 -6. 8).
(Z) max {s E NU (0) uu (2 2) 2 2
Wt min (2r Z ) Since is finite, we have 4t + cc. And we also have ZZ E Z,
(Z) mx) 2 1-2 -
By Borel-Cantelli Lemma, this construction gives a sequence un s.t. Eq. (15) holds, i.e. VZ E Z, Suppose [ is sequence of non-empty finite sets of hypothesis sequences, and (xx) is a sequence in (0, co) with 71 2 1. Then for any finite family Z, we can extend this construction to get choice of un, H4 and "h such that Eq. (7) holds
max hEH.
Ee 2)
max cm((h)) S 5n.
Smst
Since we have for given hypothesis class H. for each N, construct sequence (u such that tom ui,t = co, ui,t < and ZZ E Z,
lim E sup Eeh,, Z)
emc(h) =0
usst an Smen
Now let
de max E fl,...,,) :):
:i Vi <ú, sup F2tt
sup max P DEH,
max u Smsy (m())
S 2 E 2
and
min {t je 2 ui, 11-1,m4-13 If max (i:4 < 1). then we have - Do, and for us = ustt, we have
E
L, Z)
max uy, Sm
em (11)
S
Since H is countable, we can choose sequence of finite hypothesis classes He such that Use H. By choosing H, = Niy with H4, Hi and 7/ = ni we now have a possible choice for ut, H4 and x in Theorem 1.
27

---

F Experimental Setup
F.I Training and evaluation
Training setup. Each learner receives a t-length sequence of samples age drawn from the stochastic process, as the training data. Upon training, the learner is expected to make predictions on future samples that correspond to times > up to a fixed horizon T. At each future time t', we do not train (modify the weights) using samples after time t (because we do not have them, but we will make predictions on these samples). Given samples zge, a time-aware hypothesis class minimizes the empirical prospective risk
((h 2) =) Σ (aaa))))))
For an MLP or CNN, hs corresponds to a network that takes time s as input.
Hyper-parameters All the networks are trained using stochastic gradient descent (SGD) with Nesterov's momentum and of 0.1 for the synthetic tasks, and learning rate of 0.01 for MNIST and CIFAR. The weight-decay is set to x 10 The images from MNIST and CIFAR-10 10 are normalized to have mean 0.5 and standard deviation 0.25. The models were trained for 100 epochs, which is many epochs after achieving a training accuracy of 1.
learning rate. The networks trained at learning rate
Evaluation We estimate the prospective risk of each learner using Monte Carlo estimate. For a given training dataset zg(, we estimate a sequence predictors = (ht) which we use to make predictions future samples. We wish approximate the prospective risk (Equation (2)) for the estimated sequence of predictors. We do so, for a single future realization zye of this process, which yields the estimate
(h) (T- s=1+1
Σ (s.ha((=)).)))
In experiments, T' 50,000 for CIFAR-10 and MNIST while T 10,000 for the synthetic data experiments. For a single learning algorithm, we compute the empirical prospective risk at 15-40 different time steps which results in a significant number of GPU hours in order to plot the learning curves. For every time step, we compute the mean and standard deviation of the empirical prospective risk using random seeds.
F22 Architectural Details
Softmax
FG
FC + ReiU
Softmax
FC
layers
Conyy ReLU
FC ReLU
FC - ReiUU
Max pool
Inputs
Time encoding
enceding
Cont:: i ReLU
Time
Time
Inputs
Prospective-MLP
Prospective-CNN
Figure A.5: Schematic illustration prospective-MLL MLP and prospective-CNI
We considered the following architecture choices for the time-agnostic restropective algorithms like ERM that ignore time and the ordering associated with the samples #<t-
A multi-layer perceptron (MLP) with two hidden layers with 256 units is used for the synthetic tasks and the MNIST task. For CIFAR- 10, we use a small convolutional network with 0. 12M parameters. comprises of convolution layers (kernel size 3 and 80 filters) interleaved with max-pooling, ReLU, batch-norm layers, with fully-connected classifier layer.
Retrospective-MIIPCCC
28

---

Prospective ERM with MLP and CNNs. In order to mecrporate time into the hypothesis class, we consider an embedding function y + ved that takes raw time as an imput and returns d-dimensional vector denoted as the time-embedding. In our experiments, we define yp R - RR as function that maps
cus(wa)))))
where, wi T/é, == -==.,..,,d"" 2 to the be the collection of angular frequencies. We briefly discuss the rationale for this choice in Figure A.7. In experiments,
d = 50.
We make our classifiers a function of time by including time t as an imput the neural network. This allows the network vary its hypothesis over time. For MLPs, we concatenate the input with its corresponding time-embedding gtt) which is fed as input. For the CNN (see Figure A.5), we add the time-embedding to the output of the convolutional layers instead of concatenating it to the inputs. We also tried concatenating the time-encoding to the inputs of the CNN but found that it performed poorly in both scenarios 2 and 3 (see Figure A.6).
CIFAR Scenario 2
CIFAR Scanario
0.8
Follow-the-laaee
0.8
Follow the-leader
Prospectize Rick
Crine-SGD
Prospective
Prospective Risk
Prospective
OrlDnw-SGD
0.8
Bayesian
0.6
Bayestan
Prospective (variant 2)
Prospective Ivoriant 2)
0.-
Prospective (MLP)
0.4
Prospective (MLP)
Chance
0.0
0
10000
20000
30000
10000
20000
30000
Time (1)
Time
Figure A.6: Prospective risk of the CNN architecture on CIFAR-10 for scenarios 2 and 3. The performance of
the CNN architecture is significantly worse when the time-embedding is concatenated to the input (variant 2).
Frequencies for embedding time In the original Transformer architecture, Vaswani et al. [55] use a position-embedddnng using the frequencies differences: (1) We use the absolute time instead of the relative position, (2) We use the angular frequencies 2r/ In Figure A.7 (right), we illustrate the dime-embedding when we use the two different choices for angular frequencies. For d 128, we find that the frequencies from Vaswani et al. [55] result in slowly changing features which makes it less suitable for our task, i.e., many of the dimensions are constant over time which makes many of the dimensions uniformative for the task. In our experiments, we found out that MIPs and CNNs that use the frequencies from Vaswani et al. [55] perform poorly on the MNIST task for Scenario 2 and 3. Time-ambedding matricas
1/100002i/d i = ,d/. There are two key
Original Transformer
Ours
20
Dimestion
40-
Dimumsion
109
120
129
100
150
200
250
300
350
50
Time
Figure A.7: The time-embeddings computed using (1) frequencies from Vaswani et al. [55] (left), and (2) the frequencies from proposed in our work (right).
G Additional experiments for Scenario 3
We conduct more experiments on prospective learning problems in addition to the ones in Section 6.2.
G.1 Markov chain with periodic resets
Dataset and Tasks. For synthetic data, we consider the 2 binary classification problems described in Section 6. For CIFAR-IO and MNIST, we consider tasks corresponding the classes 1-5, and the classes 1-5 but with each class y relabeled to (y + 1) (moo 5). Using these tasks, we construct Scenario problems corresponding to a stochastic process which is a hidden Markov model on two states. The tasks are governed by a Markov process with transition matrix P(S++1 k S k) 0.1, where S, is the task at time t. Additionally after every time-steps, the state of the Markov chain reset to the first task. This ensures that the stochastic process does not have stationary distribution.
29

---

Similar to the previous experiments, for each problem, we generate a sequence of 50,000 samples. Leamers are trained on data from the first time steps (zgg)) and prospective risk is computed using samples from the remaining time steps.
Learners and hypothesis classes. For this scenario, we conduct experiments using follow-the- leader and prospective ERM. Both methods use MLPs for synthetic and MNIST tasks, and a CNN for the CIFAR-10 task. Note that prospective ERM uses an embedding of time as input in addition to the datum. Training and evaluation setup is identical to that of Scenario 2.
Synthetic Scenario 3
MNIST Scenario
CIFAR Scenario 3
1.0
1.0
1.0
0.8
0.8
0.8
Prospecive Risk
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.0
0.0
0.0
10000
5000
7500
10000
10000
20000
30000
Time (1)
Time (1)
Time (t)
Follwwthe-lesdeer
Prospective
Bayes Risk
Chance
Figure A.8: Prospective ERM can achieve good prospective risk in Scenario 3. We plot the prospective risk across 5 random seeds (which govern the sequence of samples and the weight initialization of the neural networks). In all three cases, the risk of prospective ERM approaches Bayes risk while Follow-the- eaader does achieve low prospective risk. Bayes risk for MNIST and CIFAR-10 10 problems is calculated by assuming that Bayes risk on individual tasks is zero.
As Figure A.8 shows, prospective ERM can also prospectively learn problems in Scenario 3 when data neither independent nor identically distributed.
G.2 Stationary Markov chain
Dataset and Tasks. For synthetic data, consider the 2 binary classification problems described in Scction 1. For CIFAR-IO and MNIST, we consider tasks corresponding to the classes 1-5, and the classes 1-5 but with each class y relabeled (v + 1) mod Using these tasks, construet Scenario problems corresponding to a stochastic process which is a hidden Markov model on states. The tasks are governed by a Markov process with transition matrix P(S++1 k St k) 0.1, where S₃ is the task at time t. Unlike the previous subsection (Figure A.8), in this experiment, the Markov chain equilibriates to the stationary distribution. Similar to the previous experiments, for each problem, we generate a sequence of 50,000 samples. Learners are trained on data from the first t time steps (zga) and prospective risk is computed using samples from the remaining time steps.
Learners and hypothesis classes. For this scenario, we conduct experiments using follow-the- leader and prospective ERM. Both methods use MLPs for the synthetic and MNIST tasks, and CNN for the CIFAR-10 task. Note that prospective ERM uses an embedding of time as input in addition to the datum. Training is identical to that of Scenario 2. For evaluation, we compute the empirical prospective risk in Fig. A.9 and empirical discounted prospective risk in Fig. A.10.
H Large language models may not be good prospective learners
It is an interesting question whether LLMs which are trained using auto-regressive likelihoods with Transformer-basel architectures
do prospective learning. To study this, we used LLama-7B [86] and Gemma-7B [87] to evaluate the prospective risk for Scenarios to 3. The prompt contains a few samples from the stochastic process (sub-sequences of (Y:) consisting of Os and Is) and an English language description of the family of stochastic processes that generated the samples. The LLM is tasked with completing the prompt with the next 20 most likely sequence of samples.
Selecting the appropriate prompt LLMs can be brittle and are known to generate different completions depending on if the prompt was in English, Thai or Swahili [88]. This makes it difficult to evaluate prospective learning in LLMs. Therefore, in our experiments, we do not describe prospective risk or other details about prospective learnability in the prompt. We simply describe the data generating process and some samples from this process in the prompt and prompt the model to generate the most likely completion. The prompts are described in detail Appendix H. we also experimented with a few variants of these prompts.
30

---

Synthetic Scenario
CIFAR
1.0
1.0
1.0
0.8
0.8
0.8
Prospective Risk
0.6
0.4
0.2
0.2
0.2
0.0
0.0
0.0
2500
5000
7500
10000
0
2500
5000
7500
10000
10000
20000
30000
Time (t)
Time (1)
Time
Follow-th-loadder
Prospective
Bayes Risk
Chanos
Figure A.9: For task defined stationary Markov process, the Bayes risk trivial and be achieved by hypothesis that doesn't change over time. plot the prospective (which govern the sequence of samples and the weight initialization of the neural networks). In all three cases, both follow-the-leade and prospective ERM approach the Bayes risk. The stationary distribution has an equal probability of seeing cither task and fixed hypothesis achieve Bayes risk on this problem.
across random seeds
Synthelic Scenario 3
MNIST Scenario
CIFAR Scenario 3
1.0
1.0
1.0
Discounted prospective Risk
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.0
0.0
0.0
10000
5000
7500
10000
10000
20000
30000
Time (1)
Time (1)
Time (1)
Folowthe-leader
Prospective
Risk
Chance
Figure A.10: Both prospective ERM and thelewe- achieve similar discounted prospective risks (with discount factor 0.95). We plot the discounted prospective risk across 5 random seeds. Both follow-the- leader and prospective ERM achieve similar discounted risks. Note that the error bars are larger since the risk is computed over fewer samples, i.e., the discount factor reduces the effective number of test data points.
0.6
Scenario (p=0.9)
Scenario (p=0.9)
Scenario 3 (p=0.90)
Llama-7b
Discounted prospective risk
0.8
0.5
Gemma-7b
0.6
Prospective
Prospective risk
Bayes risk
Chance
0.4
0.2
0.2
0.1
0.0
0.0
0.0
Time (1)
Time (1)
Time
Figure A.11: The prospective risk LLMs when evaluated on the three scenarios, when averaged over draws of the training data. The LLM does not improve with more data unlike prospective MLE-leamer. This suggests that LLMs are incapable of prospection.
We use greedy decoding to generate a sequence of tokens, i.e., the token with the highest probability sampled at every step. We vary the number of time-steps in the prompt from 100 which corresponds to the amount of training data. For particular value of time I, we generate 20 more tokens and compute (an estimate of) prospective risk this completion; this is the test data. We report the prospective risk computed on 100 different realizations of the stochastic process, i.e., each point Fig. A. the prospective risk on the next samples, averaged over 100 realizations of the training data. In Fig. A. we find that LLMs do not obtain better prospective risk with more
31

---

Gemma
Liama
Probability
We prompt LLMs to generate the outcomes 10 Bernoulli trials with = 0. 75. We plot the probability of generating token 1 over all possible sequences of 10 Beroullii trials and find that the outcomes are generated with probabilities that range from 0 to with an average of 0.5. Ideally. the token should should always generated with p 0.75, i.c., the LLMs cannot simulate outcomes of Bernoulli distribution.
Figure A.12:
samples, i.c. Llama-7B and Gemma-7B do not seem to be doing prospective learning. It is quite surprising that they do not achieve Bayes risk even on independent and identically distributed data. We note that these experiments do not definitively answer whether LLMs can learn prospectively.
Can LLMs generate outcomes of sequence of Bernoulli trials? We prompted an LLM to generate a sequence of Os and Is sampled from a Bernoulli distribution with probability = 0.75. We then plot the probability of generating each 0 for all sequences of length 10 in Fig. A.12. Ideally, the strip plot would be concentrated around 0.25 for O and 0.75 for 1, i.e., Os should be generated with frequency close 0.25. However, find this is not the generating sequence of Bernoulli trials. This provides some context to the results discussed above. to be doing prospective learning, but they cannot even sample from Bernoulli distribution under these experimental conditions." 13
and LLMs seem incapable of
LLMs do
H.1 Prompts for testing prospective learning in LLMs
We use the following 3 prompts to generate sequence of predictions using in LLama-7B and Gemma-7B. We found that the LLMs always generated sequence of Os and Is and we did need to post-process the response change how the tokens were sampled. We generate 20 samples using greedy decoding; the language models are executed with the weights in 16-bit precision. We tried few different variants for providing prompts to the LLM, e.g., by adding spaces between the Is and Os, the results are qualitatively similar.
Scenario
Consider the following sequence outcomes generated from a single Bernoulli distribution.
11101011111011111111111
The next 20 most likely outcomes are:
Scenario 2
Consider the following sequence of outcomes generated by Bernoulli distributions, where all even outcomes are generated by a Bernoulli distribution with parameter "p" and odd outcomes generated from Bernoulli distribution with parameter '1-p'.
10000000000000000000000000000000
The next 20 most likely sequence of outcomes are:
verbose compared to those of Llama-7B and Gemma- 7B. ChatGPT responded correctly to Scenario perhaps as result of using scratchpad [89, 90] for generating the results of intermediate steps of the algorithm. But did not achieve a small prospective risk for Scenarios and 3. Gemini and GPT-4o refused to give complete response to Scenario 3 and only outlined the sequence of steps, albeit correctly.
Reespoosses of ChatGPT-ture and GPT-4o
32

---

Scenario 3
Consider the following sequence of states generated by a Markov process with states (0, 1): 10101101010101111110
The next 20 most likely outcomes are:
To make the LLM generate sequence of Bernoulli trials with probability 0.75, used the following prompt.
Bernoulli trials
Generate outcomes of 10 Bernoulli trials where generated with probability 0.25 and with probability 0.75
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide the list of contributions in Section with pointers this section from the introduction.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Section 7 discusses the limitations of our theoretical and empirical results.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
We have developed substantial new theoretical results in this paper. They are discussed Section All mathematical claims, illustrative examples, and remarks come with elaborate proofs, both in the main paper and the Appendix.
Justification:
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We use standard visual recognition datasets along with illustrative examples on synthetic tasks. All information to reproduce our experiments, c.g., datasets, network architectures, and training procedures, is provided in Appendix F. All the code that used to conduct the experiments has been made public.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the code that used conduct the experiments has been made public.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We have conducted extremely thorough train/test splits, and tuned hyper- parameters manually across multiple runs. This information is provided in Appendix F.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For all the learning algorithms considered in every experiment in our paper, we compute empirical prospective and instantaneous risks over multiple random seeds, at 15-40 different time steps. This makes our results extremely rigorous and reproducible. All experimental results in the paper come with error bars assuming Normal distribution for the relevant quantities.
34

---

8. Experiments Compute Resourees
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We have conducted experiments this problem for close to 1.5 years. In addition to the experimental results that are discussed here, there substantial number of secondary experiments, failed attempts, that not reported. All the experiments in this paper approximately takes ~ 200 GPU hours to run.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /nw.rpsrrr..p/// cctpppp...ccpcccccooo httppp////rrpps..pppl//l////////
ines?
Answer: [Yes]
Justification: We did not use human subjects or participants in these experiments. All our datasets are public ones that are used very commonly in the published literature, or synthetically generated. We do not anticipate societally harmful consequences of this research.
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is foundational work and it is not tied to any particular application deployment. We do not anticipate negative social impact. Down the line, when this line of research matures and it is deployed for making predictions of positive social impacts, e.g., prospective learning may enable us to deploy ML models without having retrain them data changes over time. This improves performance because it prevents the predictions from deteriorating, but it also leads to other benefits in terms of economic and computational resources necessary to serve ML models.
users, anticipate lot
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We only use existing public datasets (appropriatcly cited in the paper) and synthetic data.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We only use existing public datasets (appropriately cited in the paper) and synthetic data. No new assets created from this paper.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification: No assets are created this paper.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
35

---

Answer: [NA]
Justification: No crowdsourcing experiments or research with human subjects.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing experiments or research with human subjects.
36


Reviews:
[{"review_id": "HIurnAOukj", "reviewer": "Reviewer_NX2Q", "summary": "The paper develops a new theoretical framework to address machine learning problems where data distributions and objectives evolve over time. Unlike the traditional PAC learning framework that assumes static distributions, this paper introduces \"Prospective Learning\" (PL), which models data as a stochastic process and emphasizes minimizing future risk based on past data. This approach integrates time as a crucial element in learning goals and algorithm design.", "questions": "When comparing with online learning and sequential decision making, the author emphasize that the optimal hypothesis can change over time. However, there has been a line of literature (e.g., see Besbes et al. 2015 and related literature) studying the so-called “dynamic regret” and non-stationary online learning, where the optimal hypothesis can change every round. This line of work proposes various conditions to characterize the learnability and complexity of non-stationary online learning, such as the variation of the loss function. I think a comparison of prospective learning and non-stationary online learning should be added into the paper.\n\nOmar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations Research, 63(5):1227–1244, 2015.", "limitations": "The authors discuss the limitations of the paper while more discussion on comparison to dynamic regret and non-stationary online learning, finite-sample guarantees, and computational complexity, should be added. The paper is primarily theoretical and does not have direct societal consequence.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I like the fact that the paper considers fundamental problem and very general framework, inspired by motivating examples such as biological systems. There are many solid contributions. First, the paper formally defines PL by incorporating time into the hypothesis class, distinguishing it from PAC learning, and characterizes the stochastic processes that are either strongly or weakly prospectively learnable, offering theoretical guarantees for PL under reasonable assumptions. Second, it proposes a \"time-aware\" version of ERM, showing that factoring in time during hypothesis selection can solve prospective learning problems that traditional ERM methods, which ignore time, cannot. Lastly, the paper includes numerical experiments on datasets like MNIST and CIFAR-10, illustrating that time-aware learners significantly outperform their time-agnostic counterparts in dynamic environments. The paper is well-written and the main messages are quite clear.", "weaknesses": "The theoretical results are primarily asymptotic, and the applicability to finite-sample settings requires further investigation. In the definition of the prospective risk around (1), the limit is taken to the infinity. In reinforcement learning there are both asymptotic regret with a discounted factor (which looks similar to the definition in the paper) as well as finite-sample regret. Is it possible to develop some results for finite-sample, or having to rely on asymptotic is a limitation of the current framework?\n\nImplementing time-aware ERM and scaling it to modern large-scale ML and popular models may be challenging, particularly for deep architecture, big data, and real-time applications. The paper would benefit from a more detailed discussion on the computational complexity and practical considerations of the proposed methods. Comments on either computational complexity from the theory side or practical scalability from the application side are welcomed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments and valuable suggestions. We are glad that they recognize that prospective learning addresses a fundamental problem. And we are glad that they recognize the theoretical and experimental contributions of our work. If the Reviewer thinks our responses are satisfactory, we would be very grateful if they can increase their score.\n\n> **The theoretical results are primarily asymptotic, and the applicability to finite-sample settings requires further investigation. In the definition of the prospective risk around (1), the limit is taken to the infinity. In reinforcement learning there are both asymptotic regret with a discounted factor (which looks similar to the definition in the paper) as well as finite-sample regret. Is it possible to develop some results for finite-sample, or having to rely on asymptotic is a limitation of the current framework?**\n\nThe result in Theorem 1 is about the asymptotics. In Remark 2, we do provide a sample complexity bound for prospective learning of periodic processes. As future work, we are indeed exploring sample complexity of prospectively learning more general stochastic processes such as Hidden Markov models.\n\nThe limit as $\\\\tau \\\\to \\\\infty$ on Line 80 in the definition of prospective risk is different from assuming an asymptotically large number of samples in Theorem 1\\. Line 80 uses the infinite horizon risk for the following reason. In prospective learning, if one uses a finite time horizon, then it becomes similar to a multi-task learning problem. This is investigated in works like \\[27, 28, 29\\] cited in the paper. We focussed on the infinite horizon prospective learning problem to force the learner to model the evolution of the stochastic process. We appreciate the Reviewer’s point. For some processes, e.g., Markov processes that reach a steady-state distribution, it is not possible to prospect arbitrarily far into the future. For such processes, we have to use a discounted prospective risk (mentioned on Line 82). We have now proved a corollary of Theorem 1 for discounted risks, which we will add to the main paper. We will also cite the finite-sample regret bounds from the RL literature.\n\n> **Implementing time-aware ERM and scaling it to modern large-scale ML and popular models may be challenging, particularly for deep architecture, big data, and real-time applications. The paper would benefit from a more detailed discussion on the computational complexity and practical considerations of the proposed methods. Comments on either computational complexity from the theory side or practical scalability from the application side are welcomed.**\n\nWe have figured out a few minor changes to the experimental section of the paper since the deadline. Please see the common response to all Reviewers for these proposed changes.\n\nTime-aware ERM is actually quite easy to implement. It is simply a network that is trained on a dataset of inputs (t, X\\_t) to predict the outputs Y\\_t. Any MLP, CNN, or an attention-based network can be repurposed to use this modified input using an encoding of time (Line 326). In practice, perhaps the only thing one must be careful about is that the encoding of time should be sufficiently rich to incorporate all past data. In other words, we are interested in an absolute encoding of time, unlike Transformers where position encoding is used only within the context window. This is easy to achieve using a large number of logarithmically-spaced Fourier frequencies, or a binary encoding time in minutes/seconds, like we have shown in the experiments.\n\nWe will add the above response as a remark in the paper.\n\n> **When comparing with online learning and sequential decision making, the author emphasize that the optimal hypothesis can change over time. However, there has been a line of literature (e.g., see Besbes et al. 2015 and related literature) studying the so-called “dynamic regret” and non-stationary online learning, where the optimal hypothesis can change every round. This line of work proposes various conditions to characterize the learnability and complexity of non-stationary online learning, such as the variation of the loss function. I think a comparison of prospective learning and non-stationary online learning should be added into the paper.**\n\n> **Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations Research, 63(5):1227–1244, 2015\\.**\n\nThank you for the reference. We will clarify the distinction in the camera ready version.\n\nAlthough in both cases the optimal hypothesis changes over time, the stochastic approximation problem studied in Besbes et al. 2015 and the prospective learning problem studied in this paper are somewhat different. The former optimizes over stochastic processes X\\_t to minimize a dynamical regret, finding the stochastic approximation of the optimal point of the regret, while the latter optimizes over hypothesis class H\\_t to find the best hypothesis.\n\n> **More discussion on comparison to dynamic regret and non-stationary online learning, finite-sample guarantees, and computational complexity, should be added**\n\nWe appreciate the reviewer’s constructive feedback and we will expand the paper to include a detailed discussion on the topics above. Our plan is to expand the FAQ to discuss these ideas and formally compare prospective learning to these ideas.", "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": "", "extra_scores": {}}, {"review_id": "9IQCBCO5NC", "reviewer": "Reviewer_2cje", "summary": "Update: I read the rebuttal and I found it convincing, especially the explanation of the main theorem of the paper.  Additionally, the time-aware ERM idea based on time-conditioning sounds nice.  \n---\nThis paper proposes a prospective learning framework in which a sequence of future hypotheses is produced using all examples which have already been observed over the course of training.  In principle, this framework allows for problems where the data is drawn from a stochastic process which introduces temporal correlations and non-identical distributions over time steps.  The theory introduced for this seems interesting, but I don't see any particularly surprising results.  In particular, I don't see any constructive results establishing a benefit for using the \"prospective transformer\" as opposed to the other methods, such as conditioning on the time step.  Finally, the experimental setups seem very simplistic and contrived, and the conclusions of the experiments seem muddled.  \n\nnotes from reading the paper: \n  -Prospective learning is time-aware alternative to PAC learning.  \n  -Paper shows failure cases of PAC learning on some simple problems and also establishes some new algorithms on MNIST/CIFAR variants.  \n  -Prospective learning assumes data is drawn from an unknown stochastic process.  \n  -Data defined as z_t = (x_t, y_t).  \n  -Prospective learner maps from history of data to sequence of hypotheses on all time steps.  \n  -Only focus on expected future loss, and not risk.", "questions": "-Do you think it could be possible to use reinforcement learning (games) to get a more natural application for your framework?  For example, in a game like montezuma's revenge, the agent should get farther over the course of training and will be able to see new challenges and new parts of the environment.", "limitations": "-The proposed \"prospective transformer\" I believe is not new, but was explored here (and I believe in many earlier papers as well), yet I don't see that these were cited (https://arxiv.org/pdf/2404.19737).", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-The paper is very nicely written and the idea is presented cleanly and clearly.  \n\n  -The topic of improving learning in non-stationary environments and framing this problem well, is very important.", "weaknesses": "-The experimental settings seem very artificial.  Additionally, the difference between the methods is unclear in terms of performance, and none of them generally achieve the bayes optimal performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We are glad that they find our theoretical contributions to be important for learning in non-stationary environments. We believe we have addressed all your concerns in the response below. If you think these responses are satisfactory, we would be very grateful if you can update your score.\n\n> **The theory introduced for this seems interesting, but I don't see any particularly surprising results. In particular, I don't see any constructive results establishing a benefit for using the \"prospective transformer\" as opposed to the other methods, such as conditioning on the time step**\n\nLet us argue why Theorem 1 is somewhat remarkable. Consider a general stochastic process (does not have to be periodic, or reach a steady-state distribution). Theorem 1 says that in spite of such a general setting, given samples from the process up to time $t$, we can build a sequence of hypotheses that can be used for any time in the future. Just like standard empirical risk minimization (ERM) allows one to build a hypothesis that can be used for any test datum drawn from the same distribution, Theorem 1 allows us to learn any stochastic process using a procedure that is conceptually quite similar to ERM, except that the predictor takes time as input. The consistency of standard ERM is one of the first results of PAC learning—and a cornerstone result. Theorem 1 is a similar result for prospective learning. It is a definitive first step on this important problem.\n\nWe have made some minor modifications to the experimental parts of this paper since the deadline. Please see the common response to all reviewers above.\n\nIn the context of your question, we have now figured out how to exactly implement a time-aware ERM in Eqn (5). It is simply a network that is trained on a dataset of inputs (t, X\\_t) to predict the outputs Y\\_t. Any MLP, CNN, or an attention-based network can be repurposed to use this modified input using an encoding of time (Line 326). In particular, there is no need to use an auto-regressive loss like we had initially done in the NeurIPS submission.\n\nTheorem 1 directly suggests this practical solution. Roughly speaking, for a practitioner who wishes that their models do not degrade as data changes over time, our paper proves, theoretically and empirically, that appending time to the train and test input data is sufficient. We suspect this is a big deal.\n\n> **The experimental settings seem very artificial. Additionally, the difference between the methods is unclear in terms of performance, and none of them generally achieve the bayes optimal performance.**\n\nThis is a theoretical paper. We have constructed a, more or less, exhaustive set of “scenarios” (IID data in Scenario 1, independent but not identically distributed data in Scenario 2,  neither independent nor identically distributed data in Scenario 3, and situations where past predictions affect future data in Scenario 4). Our goal while doing so is to study precisely the performance of our proposed time-aware ERM and some baseline methods. In particular, we can calculate the Bayes risk for the experiments in Fig 1\\. This is the gold standard for any method.\n\nWhen using non-synthetic data, our experimental scenarios are quite similar to those in existing papers on continual learning. The gold standard for experiments on non-synthetic data would be Oracle, which is a learner that knows exactly the distribution from which the test datum at any future time $t’$ is sampled; the risk of Oracle is therefore even “better” than Bayes risk. As we see, the training curves in Fig. 2 do converge to the risk of Oracle over time.\n\nIn Scenario 2, time-aware ERM achieves Bayes risk while time-agnostic methods only achieve trivial risk. This shows that time-agnostic methods fail to solve even a simple synthetic problem.\n\nIn our original Scenario 3, the transition matrix for the Markov chain of the hidden states was chosen to be such that the chain could converge to a steady-state distribution. As we discussed on Lines 125-139, prospective learning is only meaningful in these settings if one uses a discounted loss. Our experiments were using the non-discounted loss, and therefore the prospective risk of time-aware ERM was converging to the trivial risk. Time-agnostic ERM converges to the trivial risk for Scenario 3, in general.\n\nWe have rectified the situation now using a different hidden Markov chain which does not have a steady-state distribution. See Fig. 5 in the PDF Rebuttal. Time-aware ERM for the modified Scenario 3 does converge to the Bayes risk over time.\n\n> **Do you think it could be possible to use reinforcement learning (games) to get a more natural application for your framework? For example, in a game like montezuma's revenge, the agent should get farther over the course of training and will be able to see new challenges and new parts of the environment.**\n\nThis is a very good idea. In our Scenario 4, we have discussed the long term risk of a Markov Decision Process. We also developed an interesting “algorithm” for this in Appendix F. In broad strokes, this setting is similar to the problem in Montezuma’s revenge where future data depends upon past decisions. We have not instantiated the learner for Scenario 4 in experiments on non-synthetic data yet. This is mostly because the current algorithm in Appendix F involves learning both the value function and forecasting the future data, this would be difficult to pull off together. We plan to investigate this in the future.", "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": "", "extra_scores": {}}, {"review_id": "pZgKR2B2zc", "reviewer": "Reviewer_wUXj", "summary": "The paper focuses on new paradigm of learning called \"prospective learning\" oppose to Probably Approximately Correct (PAC) paradigm which is how current AI systems are being designed. PAC is time agnostic given the data while PL is time-aware. The paper clearly outlines different scenarios of PL with examples and distinguishes the proposed paradigm with others. Also, showcases experimental validation of PL in different scenarios.", "questions": "- If Data-incremental learning is more closer to the problem formulation of PL, then how does multiple epochs are handled across all three cases of data type (IID, non-IID, etc)?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is clearly written and easy to follow\n- Paper seems to pose a new realistic paradigm of learning which is incorporates time components compared to traditional paradigm which is time-agnostic.\n- The paper has strong theoretical background.", "weaknesses": "- Paper fails to explain how training on unlabeled data would be yield in the proposed paradigm.\n- The authors also don't consider the real world natural scenario of non-IID data where the data is a continuous video whose stochastic process will be unknown.\n- Paper lacks explanation on how PL would handle or prevent catastrophic forgetting since it is arises from the distribution shift with time in PAC paradigm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments on our work. We are glad that they recognize our theoretical contributions. \n\n> **Paper fails to explain how training on unlabeled data would be yield in the proposed paradigm.**\n\nThis is a good question. We have been inspired by the work of Steve Hanneke \\[1\\]. They develop some results for the so-called “self-adaptive setting” where in addition the past data ($z\\_{\\\\leq t}$ in our notation), the learner also has access to future inputs $\\\\{x\\_s: t \\\\leq s \\\\leq t’\\\\}$ when it makes a prediction at time $t’$. Hanneke showed that there exist optimistically universal learners for the self-adaptive setting. In simple words, if a stochastic process can be self-adaptively learned strongly, then there exists a learner which does so. Just like our Theorem 1, their result is a consistency result.\n\nHanneke does not consider the setting where the true hypothesis changes over time, which is what we are interested in. But we believe that their work gives us a nice foundation to build upon as we try to understand how to use unlabeled future data for prospective learning. This is part of future work. We will mention this in the discussion.\n\n\\[1\\] Hanneke, Steve. \"Learning whenever learning is possible: Universal learning under general stochastic processes.\" *Journal of Machine Learning Research* 22.130 (2021): 1-116.\n\n> **The authors also don't consider the real world natural scenario of non-IID data where the data is a continuous video whose stochastic process will be unknown.**\n\nIn fact, prospective learning is ideally suited to address problems with non-IID data, e.g., situations where one is modeling data from a video. The reason for this is as follows.\n\nTheorem 1 works for general stochastic processes. It does not need to know the class of the stochastic process, e.g., whether it is a Markov chain, or a hidden Markov model etc. This is why we think it is quite remarkable. Theorem 1 says that in spite of such a general setting, given samples from the process up to time $t$, we can build a sequence of hypotheses that can be used for any time in the future. Just like standard empirical risk minimization (ERM) allows one to build a hypothesis that can be used for any test datum drawn from the same distribution, Theorem 1 allows us to learn any stochastic process using a procedure that is conceptually quite similar to ERM, except that the predictor takes time as input. The consistency of standard ERM is one of the first results of PAC learning—and a cornerstone result. Theorem 1 is a similar result for prospective learning. Just like standard ERM makes certain assumptions about the concentration of the empirical loss and the learner’s hypothesis class, Theorem 1 also makes assumptions about consistency and concentration in Eqns. (3-4). These are rather standard, and quite benign, assumptions.\n\nReal-world stochastic processes, e.g., images in a video, may or may not satisfy the conditions of Theorem 1\\. This is no different from how real-world data may or may not satisfy the assumptions of standard PAC learning. We cannot easily verify the assumptions of PAC learning in practice (whether the hypothesis class contains a model which achieves zero population loss equal to Bayes error, and whether we have uniform concentration of the empirical loss to the test loss). And similarly, assumptions of prospective learning may be difficult to verify in practice. But this does not stop us from implementing PAC learning. And similarly, one can implement prospective learning for video data.\n\nThe most important practical recommendation of our paper for implementations on video data is that the architecture should encode the time of each image frame, i.e., implement time-aware ERM in Eqn. (5).\n\n> **Paper lacks explanation on how PL would handle or prevent catastrophic forgetting since it is arises from the distribution shift with time in PAC paradigm.**\n\nCatastrophic forgetting in PAC learning occurs when future training data has a different distribution than past data. This is exactly the setting addressed in prospective learning. In simple words, the central idea of our paper is that if the distribution of data changes in a predictable fashion, then prospective learning can prevent catastrophic forgetting. To give an example, if the stochastic process is periodic, i.e., there is a finite number of distinct distributions that are seen as a function of time, then time-aware ERM in Theorem 1 selects a sequence of hypotheses, one element is assigned to each of these marginal distributions. And given a test datum at a particular future time, the learner simply selects the appropriate predictor for that time. Standard PAC learning would not be able to address such periodic shifts because it does not model changes over time.\n\n> **If Data-incremental learning is more closer to the problem formulation of PL, then how does multiple epochs are handled across all three cases of data type (IID, non-IID, etc)?**\n\nProspective learning enforces no computational constraints on the learner. This is different from other settings where one might be interested in such constraints, e.g., for computational reasons in data incremental learning, or for biological reasons in continual learning. A prospective learner is allowed to train on all past data for as many epochs as necessary. To clarify, as mentioned in footnote 7 on Page 8, we do not do any continual updates for any of the experiments.", "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": "", "extra_scores": {}}, {"review_id": "S4XEzv9zIx", "reviewer": "Reviewer_Zv5g", "summary": "In this work, the authors formalize the notion of “prospective learning”, which considers that the data to be learned are sampled from a stochastic process, rather than being sampled from a fixed distribution. Perspective learning considers time by giving a set of hypotheses for each time step during inferences instead of just one fixed hypothesis as in the probably approximately correct (PAC) framework. The authors give a theoretical framework (similar to the one developed in PAC) to characterize under which condition a stochastic process can be learned by a time-aware (prospective learning) model. These are explained through their mathematical formulation and simple examples that highlight the main features of a stochastic process to determine if they can be “prospectively learned” or not. Finally, the authors perform a set of experiments, as real-world cases analogies of the simple examples, and show how time-aware prospective models can learn (or not) the tasks as described by their theory.", "questions": "1.- In definition 2 “Weak prospective learnability”, is a stochastic process “weakly learnable” if a model with a sequence of hypotheses can perform above chance with an arbitrarily low probability? Is it enough it exists one $t$ where this is true to consider it weakly learnable?\n\n2.- Does the concept of aliasing apply when the hypothesis class is not enough to cover a periodic stochastic process as in example 1? On the other hand, would you see some redundancy in optimal hypotheses if this family is larger than the ones needed to describe the stochastic process?\n\n3.- In section 2.1, I found a bit confusing the distinction between MLE and time-aware MLE models. Both models use MLE to find the solution and the difference is just how the hypothesis space is constructed. If this is correct, I would recommend changing it to “time-agnostic” vs “time-aware” or something along these lines.\n\n4.- What is the intuition for the time-aware models not being able to solve scenario 3 in the experiments (section 5)? This is quite surprising considering that transformer architectures for example are auto-regressive and that there is some temporal structure that could be learned. Could you clarify what is the task structure, and how information is being given to the model, how is trained?\n\n5.- A model with a class of hypotheses that change over time can learn prospectively if there is some temporal structure that can be exploited, but each risk term in equation 5 is instantly dependent on the current hypothesis, so the performance in the future is not affected by the current time step hypothesis. Why then might it be beneficial to decrease the discount factor $\\gamma$? if each hypothesis is only influenced by its own time step what is the problem with having a $\\gamma=1$?\n\n6.- Considering Appendix A (FAQs), I believe a clearer connection between prospective learning and related concepts could be established by explicitly comparing their optimization objectives, training procedures, and problem structures. While this would undoubtedly be a significant undertaking, given the lack of standardized descriptions in these related fields, and likely beyond the scope of this work to address every single one, it would be a valuable contribution to readers' confusion.", "limitations": "The authors discuss the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- This manuscript gives a useful theoretical base for understanding and describing a very intuitive concept of learning considering time, instead of a static data generator distribution. The theoretical framework allows for guarantees of function approximation by a class of time-varying hypotheses, provides a solution in explicit form for a binary classification problem with Gaussian inputs, and also analyzes the complexity of learning a specific type of process (periodic process).\n- Furthermore, the authors can land their theoretical work in very simple illustrative examples, making the work easier to understand. This are followed by very well executed larger scale experiment to verify if their theoretical assumptions and simple example conclusions hold for more complex settings.\n- The work presented has been thoroughly studied from theoretical and experimental fronts, with a coherent narrative to explain an intuitive consideration that has been used in practice for a while in machine learning (as it is similar to RL, or meta-learning, but not the same).\n- Their Appendix (FAQs) was very helpful in explaining how this framework relates to other work around meta-learning or continual learning. On this front, they also highlight how other methods or problem setups complement their introduced concept.", "weaknesses": "- The complexity of the theoretical framework might make it challenging for some readers to follow. Despite this, the authors do seem to try to bridge the gap by providing explanations and building intuition around the theoretical developments. The appendix is particularly helpful in this regard.\n- Following the previous comment, the clarity of the experimental results (section 5) seems to fall short compared to the well-developed theory part. The results for scenario 3 require further investigation, as they seem unexpected based on the theoretical predictions in the simple examples.\n- While the appendix discusses how this intuition relates to existing concepts in RL and meta-learning, the \"plain English\" explanation, as they refer to it, can be further improved by drawing more formal connections between their framework and these established areas (See question below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments and valuable suggestions. We are glad that they have found the theoretical and experimental fronts of our work to be thorough. We also appreciate the positive aspects of our work, they have mentioned: (1) prospective learning as a useful theoretical foundation to describe including time in learning problems, (2) simple experiments that illustrate the theoretical findings, (3) well-executed large-scale experiments verifying the theoretical claims, and (4) clear descriptions of how prospective learning is related to other learning paradigms.\n\nWe have addressed the remaining comments and questions below. If our responses are satisfactory, we would be very grateful if you can champion the fresh perspective explored in our work.\n\n> **The clarity of the experimental results (section 5\\) seems to fall short compared to the well-developed theory part. The results for scenario 3 require further investigation, as they seem unexpected based on the theoretical predictions in the simple examples.**\n\nWe agree that some of the experiments were not sufficiently fleshed out in the original submission. Specifically, in Scenario 3, we chose a hidden Markov model for the data where the Markov chain corresponding to the data distributions had a steady-state distribution. As we discussed on Lines 125-139, we need to discount the prospective risk over time for prospective learning to be meaningful for stochastic processes which can reach a steady-state distribution. Therefore, although the original experiments seem unappealing at first because the prospective risk is trivial, the learner does converge to the Bayes risk and this actually follows the theory completely—just that the Bayes risk is trivially large for the example we chose.\n\nWe have fixed this now by choosing a hierarchical hidden Markov model where the process cannot reach a steady-state distribution. Please see the update experiment in Fig. 5 in the Rebuttal PDF.\n\n> **Q1) In definition 2 “Weak prospective learnability”,.......  Is it enough it exists one time point t where this is true to consider it weakly learnable?**\n\nYou are correct. We will fix the definition. For a process to be weakly-learnable, there must exist a time $t’$ such that for all times $t\\>t’$, the inequality on risks holds.\n\n> **Q2) Does the concept of aliasing apply when the hypothesis class is not enough to cover a periodic stochastic process as in example 1? On the other hand, would you see some redundancy in optimal hypotheses if this family is larger than the ones needed to describe the stochastic process?**\n\nGreat question\\! When the hypothesis space is not rich enough, i.e., there does not exist a hypothesis whose prospective risk matches the Bayes risk, then time-aware ERM learns the optimal hypothesis in the hypothesis class (best-in-class). This can lead to aliasing. For example, if data is drawn from a periodic process with period 5 and the hypothesis only contains sequences with period at most 3, then the prospective risk of even the best in class hypothesis can be trivial due to aliasing. On the other hand, if the hypothesis class is too large for the uniform concentration assumption in Theorem 1 to hold, then the risk of time-aware ERM might not converge to Bayes risk.\n\nThe above paragraph is about hypothesis-class-based aliasing. There is another form of aliasing that can occur, this is due to sampling. Suppose we have a periodic process, but the samples we observe from it are received at a rate lower than the Nyquist rate. Models trained on such samples will suffer from aliasing. Sampling-based aliasing can also occur if the resolution of the time encoding is not sufficient. In simpler words, if the time instant of each datum is not recorded precisely, then the time-aware ERM learner might not see high-frequency fluctuations in the data stream. This is similar to how audio quality drops if an MP3 file is sub-sampled below 44.1 kHz.\n\nIn general, the answer to your question is similar to the corresponding answer one might give for PAC learning. We need some inductive bias for learning to be possible. This inductive bias can come from guessing the period (either directly, or searching for the correct period like we do in structured risk minimization), or from guessing the required resolution of the time encoding (one might need to record time in seconds for high-frequency data, but only in weeks for visual recognition data).\n\n> **Q3) Both models use MLE to find the solution and the difference is just how the hypothesis space is constructed. If this is correct, I would recommend changing it to “time-agnostic” vs “time-aware” or something along these lines.**\n\nWe agree that it is confusing. We will fix this to say “time-agnostic ERM” vs. “Prospective ERM”.\n\n> **Q4) What is the intuition for the time-aware models not being able to solve scenario 3 in the experiments (section 5)? This is quite surprising considering that transformer architectures for example are auto-regressive and that there is some temporal structure that could be learned.**\n\nIn Scenario 3, we had chosen a hidden Markov model for the data where the Markov chain corresponding to the data distributions had a steady-state distribution. As we discussed on Lines 125-139, we need to discount the prospective risk over time for prospective learning to be meaningful for stochastic processes which can reach a steady-state distribution. The prospective risk does converge to the Bayes risk—just that the Bayes risk is trivially large for the example we chose.\n\nPlease see the updated experiment in Fig. 5 in the Rebuttal PDF.\n\nTo clarify the experimental setup in Scenario 3, we generated hidden states of an HMM using a transition matrix $\\\\Gamma\\_4$ on Line 740 in Appendix C. Each hidden state corresponds to a specific distribution/task, in our case, a set of classes, detailed on Line 728 in Appendix C. Data are drawn from this distribution/task.", "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": "", "extra_scores": {}}]

Author rebuttal:
### **Common response to all Reviewers**

We thank the reviewers for lending their expertise to assess our work and for helping us improve it. We are glad that the reviewers are positively inclined towards this work. The find that the problem is fundamental, and our paper presents a general framework with strong theory [NX2Q, wUXj, Zv5g], the problem is important, the paper is well-written [2cje, wUXj], the work is thorough with illustrative examples [Zv5g]. Individual responses to each reviewer are included below.

Based on Reviewer feedback, we will make the following changes to the manuscript to improve the experimental parts of the paper.

**New experiments on Scenario 3 (neither independent nor identically distributed data).**  
For Scenario 3, we had chosen a Hidden Markov Model where the Markov chain corresponding to the data distribution had a steady-state distribution. As we discussed on Lines 125-139, one needs to discount the prospective risk over time for learning to be meaningful for such processes. Experiments on CIFAR-10 in Fig. 3 did not use discounting and that is why the prospective risk was high. The experiment was correct, just that even the Bayes risk for this process is quite large (see Lines 125-139).

In Fig 5 in the Rebuttal PDF, using synthetic data, we set up a hierarchical HMM where the underlying Markov chain has two communicating sets of states, and the chain transitions across these sets deterministically after 10 timesteps. This process does not have a steady state distribution. And like our theory suggests, time-aware ERM (renamed to Prospective ERM) converges to the Bayes risk. We will add this figure to the paper. We will also conduct a similar experiment using a hierarchical HMM on CIFAR-10 data to replace Fig. 3; we expect the results to be similar to those in Fig. 5.

**Comparing time-aware ERM with other continual learning algorithms.**  
Prospective learning is designed to address situations when data, and the optimal hypothesis, evolves over time. Task-agnostic online continual learning methods are the closest algorithms in the literature that can work in this setting. We implemented (a) Follow The Leader, (b) Online SGD, and (c) online variational Bayes [1]. These algorithms are not designed for prospective learning but they are designed to address the changing data distribution $t$. The setup is identical to that of Fig. 2 in the paper, i.e., Scenario 2 with independent but not identically distributed data. As Fig. 4 in the Rebuttal PDF shows, on tasks constructed from both synthetic and MNIST data, these baseline algorithms achieve trivial prospective risk. Even the average risk on *past data* for these baselines is trivial (0.5 for synthetic data, 0.75 for MNIST). This experiment suggests that these three methods cannot handle changing data distributions. Even if there are only two distinct distributions of data, and these changes are predictable. In contrast, the prospective risk of Time-MLP converges to zero over time.

Fig. 4 in Rebuttal PDF will replace Fig. 2a and 2b in the current manuscript. We will conduct a similar experiment on CIFAR-10 to replace Fig. 2c.

See footnote 7 on Page 8 in the paper. In our experiments, for every time $t$ we use 3 training datasets that are realizations of $z\_{\\leq t}$ and calculate the prospective risk on 100 realizations of $Z\_{\> t}$. For a time-horizon of 400, this entails 1,200 trained models for each method. This is why we could not finish similar experiments on CIFAR-10. But we will add them to the camera ready.

[1] Zeno, Chen, et al. Task agnostic continual learning using online variational Bayes. arXiv:1803.10123 (2018).

**Cleaning up the different learners. There will be only two methods: Time-agnostic and Time-aware ERM (renamed to Prospective ERM); Auto-regressive and prospective Transformer will be moved to the Appendix.**  
We have now figured out a way to exactly implement a time-aware ERM (will be renamed to Prospective ERM) in Eqn (5). Theorem 1 suggests that we must simply use a network that is trained on a dataset of inputs $(t, X\_t)$ to predict the outputs $Y\_t$. Any MLP, CNN, or an attention-based network can be repurposed to use this modified input using an encoding of time (Line 326). In particular, there is no need to use an auto-regressive loss, or fit a prospective Transformer like we had initially done in the manuscript. Roughly speaking, for a practitioner who wishes that their models do not degrade as data changes over time, our paper proves, theoretically and empirically, that appending time to the train and test input data is sufficient.

We will therefore move experiments that use auto-regressive and prospective Transformers in Fig. 2 and 3 to the Appendix. Continual learning baselines will be added to those figures instead, as discussed above.

**Large language models may not be good prospective learners**  
It is an interesting question as to whether LLMs which are trained using auto-regressive likelihoods with Transformer-based architectures can do prospective learning. To study this, we used LLama-7B and Gemma-7B to evaluate the prospective risk for Scenarios 1 to 3\. The prompt contains a few samples from the stochastic process (sub-sequences of $(Yt)$ consisting of 0s and 1s) and an English language description of the family of stochastic processes that generated the data. The LLM is tasked with completing the prompt with the next 20 most likely samples. The data and evaluation setup is identical to Fig. 1 in the paper. As Fig. 6 in the Rebuttal PDF shows, prospective risk does not improve over time for any of the LLMs. In contrast, risk of the time-aware MLE in Fig. 1 in the main paper or Fig. 6 in the Rebuttal converges to the Bayes risk. These results will be added to Section 5.

We believe these changes to the experimental section will improve the quality of our paper. We are very thankful to the Reviewers for suggesting some of these changes.

Meta-review: This paper introduces "prospective learning" as a theoretical framework to address distributions evolving over time following a stochastic processes. The authors quantify processes that are prospectively learnable and prove time-aware ERM can solve them. This work takes an interesting step toward ML systems that incorporate time-varying distributions.

The reviewing team has raised several important feedback, including i) clarifying connections to non-stationary online learning, continual learning, RL, and meta-learning and ii) improving the clarity of the experimental results and adding additional baselines such as continual learning methods. The paper will be significantly strengthened by incorporating them in the camera-ready version.
Decision: Accept (poster)