Prospective Learning: Learning for a Dynamic Future

Authors: ashwin  de silva
rahul  ramesh
rubing  yang
siyu  yu
joshua t vogelstein
pratik  chaudhari
equal  contribution
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:36:47

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.

Main paper: 
 introduction: 
 All learning is for the future. Learning involves updating decision rules or policies, based on past experiences, to improve future performance. Probably approximately correct (PAC) learning has been extremely useful to develop algorithms that minimize the risk-typically defined as 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 is neither testable nor believed to be true in practice. The future is 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 to 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 we lack a first-principles framework to address problems where data distributions and goals may change over time in such a way that the optimal hypothesis is time-dependent. And as a consequence, machine learning-based AI today is brittle to changes in distribution and goals.This paper develops a theoretical framework called "Prospective Learning" (PL). Instead of data arising from an 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 t ∈ N to output an infinite sequence of predictors, which it uses for making predictions on data at all future times t ′ > t. 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 a deployed machine learning system. The designer of this system desires to optimize-not the risk upon the past training data, or the risk 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 is 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, 7] . 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.• Section 2 defines Prospective Learning (PL) as an approach to 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 3 and Appendix A put prospective learning in context relative to existing ideas in the literature to address changes in the data distribution. • Section 4 takes steps towards a theoretical foundation for prospective learning. We define 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 5 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 data. In contrast, a 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. 
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. 1 (left) for schematic illustration). Data. Let the input and output at time t be denoted by x t ∈ X and y t ∈ Y respectively. Let z t = (x t , y t ). We will model the data as a stochastic process Z ≡ (Z t ) t∈N defined on an appropriate probability space (Ω, F, P). At time t ∈ N, denote past data by z ≤t ≡ (z 1 , . . . , z t ) and future data by z >t ≡ (z t+1 , . . . ). We will find it useful to distinguish between the realization of the data, denoted by z ≤t , and the corresponding random variable, Z ≤t .Hypothesis class. At each time t, a prospective learner selects an infinite sequence h ≡ (h 1 , . . . , h t , h t+1 , . . . ) which it uses to make predictions on data at any time in the future. Each element of this sequence h t : X → Y and therefore h t ∈ Y X . 1 The hypothesis class H is the space of such hypotheses, h ∈ H ⊆ (Y X ) N . 2 We will again use the shorthand h ≤t ≡ (h 1 , . . . , h t ). We will sometimes talk about a "time-agnostic hypothesis" which will refer to a hypothesis such that h t = h t ′ for all t, t ′ ∈ N. Observe that this makes our setup different from the standard setup in PAC learning where the learner selects a single hypothesis in Y X . One could also think of prospective learning as using a single time-varying hypothesis h : N × X → Y, i.e., the hypothesis takes both time and the datum as input to make a prediction.Learner. A prospective learner is a map from the data received up to time t, to a hypothesis that makes predictions on the data over all time (past and future): (X × Y) t → (Y X ) N . The learner gives as output a hypothesis h(z ≤t ) ∈ H. Unlike a PAC learner, a prospective learner can make different kinds of predictions at different times. This is a crucial property of prospective learning. In other words, after receiving data up to time t, the hypothesis selected by the prospective learner can predict on samples at any future time t ′ > t.Prospective loss and risk. The future loss incurred by a hypothesis h isEQUATIONwhere ℓ : N × Y × Y → [0, 1] is a bounded loss function. 3 Prospective risk at time t is the expected future loss4 EQUATIONwhere we assume that h is a random variable and h ∈ σ(Z ≤t ) where σ(•) denotes the filtration (an increasing sequence of sigma algebras) of the stochastic process Z. We have used the shorthandE[Y | x] for E[Y | X = x].Observe that we have conditioned the prospective risk of the hypothesis h upon the realized data z ≤t . We can take an expectation over the realized data, to obtain the expected prospective riskE [R t (h)] = R t (h) d P Z ≤t .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 a time t asEQUATIONwhich is the minimum achievable prospective risk by any learner that observes data z ≤t . We define the Bayes optimal learner as any learner that achieves a Bayes optimal risk at every time t ∈ N. In certain contexts, one might be interested in the limiting prospective Bayes risk as t → ∞.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 t we have X t = 1, Y t ∈ {0, 1}. We will also focus on the time-invariant zero-one loss ℓ(t, ŷ, y) = δ(ŷ ̸ = y) for all t, here δ is the Dirac delta function. Fig. 1 shows example realizations of the data for each scenario. Scenario 1 (Data is independent and identically distributed). Formally, this consists of stochastic processes where P Z t ′ |Z ≤t = P Zt for all t, t ′ ∈ N. As an example, consider Y t ∼ Bernoulli(p) for some unknown parameter p ∈ [0, 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. 5Scenario 2 (Data is independent but not identically distributed). This consists of stochastic processes whereP Zt|Z ≤t = P Zt for all t ∈ N. Consider Y t ∼ Bernoulli(p) if t is odd, and Y t ∼ Bernoulli(1 -p) if t 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 time-agnostic hypothesis can only perform at chance level. But a 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 1 in Fig. 1 ), or when the learner does not know that the data distribution Bernoulli probability p = 0.2, the maximum-likelihood estimator (MLE) in blue uses a time-agnostic hypothesis ht(Xt) = 1(pt > 0.5) where pt = t -1 t s=1 ys, ties at pt = 0.5 are 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 (orange) that alternates between two predictors at even and odd times converges to Bayes risk. Variants of this learner that use less information from the stochastic process (green does not know that the data distributions at even and odd times are tied, red does not know that the distribution shifts at every time-step) also converge to Bayes risk, but more slowly. Scenario 3: For θ = 0.1 and γ = 0.9 in the discounted prospective risk, the MLE estimator (blue) again performs at chance levels. A prospective learner that computes an estimate of the transition probability of the two-state Markov chain to estimate P(Y t ′ | yt) for future times t ′ > t converges to Bayes risk. Scenario 4: For θ0 = θ1 = 0.1, the MLE estimator (blue) performs at chance levels. A prospective learner that uses a variant of Q-learning (described in the text and Appendix B.3) converges to the prospective Bayes risk. changes at every time step (Variant 2 in Fig. 1 where we implemented a generalized likelihood ratio 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/meta-learning [12] . Scenario 3 (Data is neither independent nor identically distributed). Formally, this scenario consists of general stochastic processes. As an example, consider a Markov processP(Y t+1 = k | Y t = k) = θ with two states k ∈ {0, 1} and Y 1 ∼ Bernoulli(θ).The invariant distribution of this Markov process is P(0) = 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 a slightly different loss than the one in Eq. (1) to writeEQUATIONfor some γ ∈ [0, 1). In this example, we can calculate the prospective Bayes risk analytically; see Appendix B.2. For γ = 0.9, θ = 0.1 and the zero-one loss, limiting prospective Bayes risk is 0.357. Now consider a learner which computes the MLE of the transition matrix Γ t ′ -t t . It calculatesP(Y t ′ | y t ) = pt ′ where [1-p t ′ , pt ′ ] = Γ t ′ -t t [1-y t , y t ]⊤ and uses the hypothesis h t ′ (X t ′ ) = 1(p t ′ > 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 4 (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 to address such scenarios. For θ 0 , θ 1 ∈ [0, 1], consider a Markov decision process (MDP) P(Y t+1 = j | Y t = j ′ , h t+1 (1) = k) = θ k if j = j ′ and 1 -θ k otherwise. I.e., the prediction h t+1 (X t+1 ) = k (recall that X t = 1 for all times) is the decision and the MDP remains in the same state with probability θ k . 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(Y t ′ | y t ) like Scenario 3 above to predict on future data at time t ′ . See Appendix B.3. Prospective risk of this learner converges to Bayes risk in Fig. 1 . This scenario is closely related to reinforcement learning [15] .3 How is prospective learning related to other learning paradigms? 6Distribution shift. Prospective learning [16] is equivalent to PAC learning [17] in Scenario 1 when data is IID. Situations when this assumption may not be valid are often modeled as a distribution shift between train and test data [2] . Techniques such as propensity scoring [18, 19] or domain adaptation [20, 21] reweigh or map the train/test data to get back to the IID setting; techniques like domain invariance [22, 1] 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 t )} 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 a 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 a finite number of tasks. Much of continual or lifelong learning [14, 13] focuses on "task-incremental" and "class-incremental" 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] [27] [28] [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 data-neither of these emphasizes prospection. There is a rich body of work on 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 a consistent estimator using the finite past Z 1:t [33] [34] [35] . This is also true for regression [36, 37] , when the true hypothesis f * s.t. Y t = f * (X t ) is fixed. In other words, Bayes risk R * t in Theorem 1 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 X for consistent inductive (predict at time t ′ > t using data up to t), self-adaptive (predict at time t ′ using Z ≤t and X t+1:t ′ ) and online learning [39, 40] (predict at t ′ using Z ≤t ′ ). 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 et al. [42] give algorithmic guarantees for several online estimation problems in this setting.The true hypothesis in PL 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 ⊆ Y X , we define the notion of a hypothesis class that consists of sequences of predictors, i.e., subset of (Y X ) 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 a 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 a causal-state representation called an ϵ-machine is the minimal sufficient statistic for prediction. 
theoretical foundations of prospective learning: 
 Definition 1 (Strong Prospective Learnability). A family of stochastic processes is strongly prospectively learnable, if there exists a learner with the following property: there exists a time t ′ (ϵ, δ) such that for any ϵ, δ > 0 and for any stochastic process Z from this family, the learner outputs a hypothesis h such that P [R t (h) -R * t < ϵ] ≥ 1 -δ, for any t > t ′ . This definition is similar to the definition of strong learnability in PAC learning with one key difference. Prospective Bayes risk R * t depends upon the realization of the stochastic process z ≤t up to time t. In PAC learning, it would only depend upon the true distribution of the data. Not all families of stochastic processes are strongly prospectively learnable. We therefore also define weak learnability with respect to a "chance" learner that predicts E[Y ] and achieves a prospective risk R 0 t .7 Definition 2 (Weak Prospective Learnability). A family of stochastic processes is weakly prospectively learnable, if there exists a learner with the following property: there exists an ϵ > 0 such that for any δ > 0, there exists a time t ′ (ϵ, δ) such that for any stochastic process Z from this family,P R 0 t -R t (h) > ϵ ≥ 1 -δ, for any t > t ′ .In PAC learning for binary classification, strong and weak learnability are equivalent [47] in the distribution agnostic setting, i.e., when strong and weak learnability is defined as the ability of a 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 a time-agnostic empirical risk minimization (ERM)-based learner. In PAC learning, ERM selects a hypothesis that minimizes the empirical loss on the training data. It outputs a time-agnostic hypothesis, i.e., using data, say, z ≤t 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., h t = h t ′ for any t, t ′ ∈ N for all predictors h ∈ H. Given data z ≤t , a learner that returns ĥ = arg minEQUATIONis called a time-agnostic empirical risk minimization (ERM)-based learner. Time-agnostic ERM in prospective learning may use a time-dependent loss ℓ(s, hs(xs), 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 is 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 as defined here will return predictors that are different than those of standard ERM that uses a time-invariant loss.Proposition 1. There exist stochastic processes for which time-agnostic ERM is not a weak prospective learner. There also exist stochastic processes for which time-agnostic ERM is a weak prospective learner but not a strong one.See Appendix E for the proof. We do not know yet whether (or when) strong and weak learnability are equivalent for prospective learning. 
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 a sufficiently large sample size. This statement holds if (a) there exists a 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 1 is an analogous result for prospective learning.Theorem 1 (Prospective ERM is a strong prospective learner). Consider a finite family of stochastic processes Z. If we have (a) consistency, i.e., there exists an increasing sequence of hypothesis classesEQUATIONwhere h ∈ H t is a random variable in σ(Z ≤t ), and (b) uniform concentration of the limsup, i.e.,EQUATIONfor some γ t → 0 and u t → ∞ with u t ≤ t (all uniform over the family of stochastic processes), then there exists a sequence i t that depends only on γ t such that a learner that returns ĥ = arg minEQUATIONis a strong prospective learner for this family. We define prospective ERM as the learner that implements Eq. ( 8) given train data z ≤t . Appendix E.2 provides a proof, it builds upon the work of Hanneke [38] . The first condition, Eq. ( 6), is analogous to 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 {H t } ∞ t=1 . 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 t, prospective ERM in Eq. ( 8) selects the best hypothesis ĥ ∈ H t8 for future times t ′ > t, that minimizes an empirical estimate of the limsup using the training data z ≤t . Prospective ERM can exploit the difference between the latest datum in the training set with time t and the time for which it makes predictions t ′ by selecting specific sequences inside the hypothesis class H t . For example, in Scenario 2 it can select sequences where alternating elements can be used to predict on data from even and odd times. Remark 1 (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 s and the datum xs. Suppose we use a hypothesis class where each predictor is a neural network, this could be a multi-layer perceptron or a convolutional neural network. The training set z ≤t consists of inputs xs along with corresponding time instants s and outputs ys. To implement prospective ERM, we modify the network to take (s, xs) as input (using any encoding of time, we discuss one in Section 6) and train the network to predict the label ys. In Eq. ( 8) we can set u it ≡ t, doing so only changes the sample complexity. At inference time, this network is given the input (t ′ , x t ′ ) to obtain the prediction y t ′ . Note that if prospective ERM is implemented in this fashion, the learner need not explicitly calculate the infinite sequence of predictors. 9Corollary 1. 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 we need an increasing sequence of hypothesis classes H 1 ⊆ H 2 . . . ). We could have chosen H t = H t ′ for all t, t ′ ∈ N to set up Theorem 1. But since the learner does not have a lot of data at early times, it should use a small hypothesis class. Just like PAC learning, the sequence (γ t ) t∈N in Eq. ( 7) determines the convergence rate of a prospective learner. Therefore, using a monotonically increasing sequence of hypothesis classes is useful to ensure a good sample complexity. Theorem 2. Consider a finite family of stochastic processes Z. If there exists a countable hypothesis class H such thatEQUATIONfor any stochastic process Z ∈ Z, where h ∈ H is a random variable in σ(Z ≤t ), then there exist H t , u t , and γ t such that the two conditions of Theorem 1 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. 
experimental validation: 
 This section demonstrates that we can implement prospective ERM on prospective learning problems 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 or not (Scenarios 2 and 3). Recall that Scenario 1 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-Leader minimizes the empirical risk calculated on all past data and is a no-regret algorithm [52] . We note that while this is a popular online learning algorithm, we do not implement the algorithm in an 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 t. 10 We calculate the prospective risk of the predictor returned by these methods; note that they do not output a time-varying predictor and consequently, these methods output a 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 (MLP) for synthetic data and MNIST, and a convolutional neural network (CNN) for CIFAR-10.For prospective ERM the sequence of predictors is built by incorporating time as an additional input to an MLP or CNN as follows. For frequencies ω i = π/i for i = 1, . . . , d/2, we obtain a ddimensional embedding of time t as φ(t) = (sin(ω 1 t), . . . , sin(ωd/2t), cos(ω 1 t), . . . , cos(ωd/2t)). This is similar to the position encoding in Vaswani et al. [55] . A predictor h t (•) uses a neural network that takes as input, an embedding of time φ(s), and the input xs to predict the output ys for any time s ∈ 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 ≡ (h 1 , . . . , ). Training setup. We use the zero-one error 1{ŷ ̸ = 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 R t (h) in Eq. ( 2) of the hypothesis created by these learners for a particular realization of the stochastic process z ≤t . For each prospective learning problem, we generate a sequence of 50,000 samples. Learners are trained on data from the first t time steps (z ≤t ) 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-CIFAR10 [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 a 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. 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, we consider two binary classification problems ("tasks") where the input is one-dimensional. Inputs for both tasks are drawn from a uniform distribution 10 There are many algorithms in the existing literature that the reader may think of as reasonable baselines. We have chosen a representative and relevant set here, rather than an exhaustive one. For example, online metalearning approaches are close to online-SGD; 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 t ′ given past data y ≤t without taking covariates X t ′ or some exogenous variables X ≤t into account, (ii) can usually only make predictions for a pre-specified future context window [54] , and (iii) work for low-dimensional signals (unlike images).on the set [-2, -1] ∪ [1, 2] . Ground-truth labels correspond to the sign of the input for Task 1, and the negative of the sign of the input for Task 2. For MNIST and CIFAR-10 we consider 4 tasks corresponding to data from classes 1-5, 4-7, 6-9 and 8-10 in the original dataset, i.e., 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 1 in task 1, class 4 from task 2 and class 6 from task 3 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. Instantaneous and prospective risks for problems constructed using synthetic data (see text) across 5 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 at later times and both instantaneous 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 all 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 a far worse prospective risk. Observe that Follow-the-Leader (blue) performs as well, or better, as 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 an online fashion; in practice it is often difficult to tune online learning methods effectively [57] . 116.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 twodimensional 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-10. Using these tasks, we construct problems where the data distribution is governed by a stochastic process which is a hierarchical hidden Markov model (Scenario 3). After every 10 time-steps, a different Markov chain governs transitions among tasks (one Markov chain for tasks 1 and 2, and another for tasks 3 and 4, as shown in Fig. 3 ). These choices ensure that the stochastic process does not have a stationary distribution. 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 a number of baseline algorithms do not achieve a low prospective risk. Stochastic processes in these problems corresponding to Scenario 3 do 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.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 time-agnostic hypothesis (Follow-the-Leader) does not achieve a good prospective risk, unlike prospective ERM. Appendix G discusses additional experiments for Scenario 3 for different kinds of Markov chains. 
discussion: 
 Prospective learning, as we see it, is a paradigm of learning that characterizes many real-world 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-based systems fail to track changes in 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 in which prospective learning based methods will outperform PAC learning, remains to be seen.This work was funded by grants from the National Science Foundation (IIS-2145164, CCF-2212519) and the Office of Naval Research (ONR) N00014-22-1-2255. RR was funded by a fellowship from AWS AI to Penn Engineering's ASSET Center for Trustworthy AI. ADS was supported by a 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 differentboth 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 is 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 .1 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-distribution. Loss characterizes whether the assumed loss function is instantaneous or time-varying. 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), or after each task arrives (task sequential), or one data sample at a time (sequential). The answers are given for typical settings, further details are available in the paragraphs below. PAC learning [59] is a special case of prospective learning when the stochastic process is timeinvariant (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 B.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.In transfer learning [21] , including domain (covariate) shift (adaptation) [20, 60] , and out-ofdistribution (OOD) [61] learning, there are two distributions, a source and a 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).Meta-learning [62, 63] is similar to multi-task learning [64] , and includes as special cases zeroshot [65] and few-shot learning [66] . Here, the data are Task IID, meaning that the distribution within a 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, as opposed to all future (unknown) distributions as in prospective learning.A.4 . . . lifelong learning?Lifelong (continual) learning [14, 13, 68] is 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 a fixed hypothesis could have done up until now. Also, in online learning, the environment is often adversarial.A.6 . . . forecasting?Forecasting [71] , time-series or sequential analysis [72, 73] assume the data follow a stochastic process, much like prospective learning often does (e.g., Scenarios 2 and 3), and therefore, the number of optimal hypothesis can be equal to 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 a 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, as evidenced in sequential Monte Carlo.A.7 . . . reinforcement learning?Reinforcement learning (RL) [15] is only concerned with situations where there is a control element, 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 are instantaneous. 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 h * t ̸ = h * t ′ for some t ̸ = t ′ . 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 not impact Z t ′ at all? We only ever incur the current loss, that is, ℓ(t, h t (x t ), y t ). So, it 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 to 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. It 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] .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 1. 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 1 where the learner returns the hypothesis h t ′ = h t = threshold(p t > 0.5) for all t ′ > t, where pt = 1 t t s=1 ys is the maximum likelihood estimator (MLE). Alternatively, if we assume a prior distribution Beta(α, β) over p, then the resulting maximum a posteriori (MAP) estimate is pt =α+ t s=1 zs-1 α+β+t-2 .We define a second prospective learner based on MAP that returns the sequence ĥ≥t = ( ĥt , ĥt , • • • ), where ĥt = threshold(p t > 0.5) for all future times beyond t. If the prior distribution has a small divergence with respect to the true posterior distribution, then the second learner converges faster to the Bayes optimal risk; for a poor choice of prior, the convergence is slower. However, in such situations, we show that we can modify the MAP-based learner to use prospection and incorporate "time" to result in faster convergence to the Bayes risk.Let y 1 , . . . , y t be the IID sample sequence observed up to time t. The idea here is to compute the rate of change ∆p(t) of the MAP estimate at time t which is given by, ∆p(t) = MAP(y 1 , . . . , y t ) -MAP(y 1 , . . . , y t-1 ) (10) Taking expectation on both sides of Equation ( 10), and plugging in pt = MAP(y 1 , . . . , y t ) for the true parameter p, we construct the following estimate for ∆p(t).∆p(t) = (α -1) + tp (α -1) + (β -1) + t - (α -1) + (t -1)p (α -1) + (β -1) + t -1Using this rate of change, we may forecast the estimate p t ′ at time t ′ > t as follows. We refer to this as the prospective MAP estimate. Based on it, we set the hypothesis to be h t ′ = threshold(p t ′ > 0.5) for all future times beyond t. In Figure A.1, we plot the prospective risk the MLE, MAP, and prospective MAP-based learners. Due to an unfavorable prior, the MAPbased learner converges slowly. However, prospective MAP-based learner manages to leverage its forecasting to achieve a faster convergence rate despite having the same prior as the MAP. This shows that we can indeed benefit from prospection even in the IID case.pt ′ = pt + t ′ -1 s=t ∆p(s)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 t+1 = 0 | Y t = 0) = θ 0 and P (Y t+1 = 1 | Y t = 1) = θ 1 , i.e., the transition matrix isΓ = θ 0 1 -θ 0 1 -θ 1 θ 1 .The probability distribution at time t ′ is given by Γ t ′ -t (z t , 1 -z t ) T . The eigenvalues of the transitionY 0 Y 1 θ 0 1 -θ 0 θ 1 1 -θ 1 Figure A.2:Markov chain describing the evolution of data matrix are λ 1 = 1 and λ 2 = θ 0 + θ 1 -1 with the corresponding eigenvectors being (1, 1) ⊤ and (θ 0 -1, 1 -θ 1 ) ⊤ . Diagonalizing Γ we getΓ t ′ -t = 1 θ 0 -1 1 1 -θ 1 λ t ′ -t 1 0 0 λ t ′ -t 2 1 θ 0 -1 1 1 -θ 1 -1 = 1 (2 -θ 0 -θ 1 ) 1 -θ 1 + (1 -θ 0 )λ t ′ -t 2 (1 -θ 0 ) -λ n 2 1 + θ 1 + (1 -θ 0 )λ t ′ -t 2 (1 -θ 0 ) + λ n 2 .which implies that the probability distribution of the state at time t ′ isπ t ′ = 1 (2 -θ 0 -θ 1 ) 1 -θ 1 1 -θ 0 + λ t ′ -t 2 ((1 -θ 0 )(1 -z t ) -(1 -θ 1 )z t ) (2 -θ 0 -θ 1 ) 1 -1 .Hence, the optimal sequence of hypotheses is h * ≥t+1 = (h * t+1 , h * t+2 , . . . ), whereh * t ′ = arg max i∈{0,1} π t ′ (i)with Bayes risk equal toR * t = lim T →∞ 1 T s=t min i∈{0,1} π ′ t (i).This reduces toR * t = 1 (2 -θ 0 -θ 1 ) min(1 -θ 0 , 1 -θ 1 );the second term in the expression of π t ′ vanishes as T → ∞. If θ 0 = 0.9 and θ 1 = 0.5, then R * t = 1/6.If we restrict our attention to the case where θ 0 = θ 1 , the discounted Bayes risk reduces to(1 -γ) ∞ s=t+1 γ s-t-1 ℓ(h * s ) = (1 -γ) ∞ s=t+1   γ s-t-1 2 - γ s-t-1 λ s-t 2 2   = (1 -γ) 1 2(1 -γ) - |λ 2 | 2(1 -|λ 2 |γ)Substituting θ 0 = θ 1 = 0.1, the discount risk for γ = 0.9 is 0.357.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 it. Scenario 1, Scenario 2, Scenario 3 fall into the first category which is the primary emphasis of our paper. Scenario 4 presents a 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 t-1 , the action is h t and the next state is Y t . The reward at the t th time-step is r(t, h t+1 , y t+1 ) = 1 {h t+1 = y t+1 } as a result of selecting action h t+1 given that the previous output was y t , and next output y t+1 . The learner estimates the transition matrix corresponding to the MDP for each decision h t+1 (X t+1 ) ∈ {0, 1} using a similar procedure as that of Scenario 3,∀k ∈ {0, 1} : Γt (k) = θk 1 -θk 1 -θk θkwhere θ ≡ θt ∈ [0, 1] 2 after t time steps. Using this estimate of Γt , the learner solves for the value function (corresponding to the discounted prospective risk) that satisfiesQt (y t , h t+1 ) = y∈{0,1} P(Y t+1 = y | Y t = y t , h t+1 = h) = Γt(ht+1)y t ,y r(t, h t+1 , y) + γ max h Qt (y, h)The value function can be solved using value iteration, iteratively until convergence. For a given Γ, Banach's fixed point theorem guarantees this procedure will converge to the 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 at time t ′ is arg max h Q(y t ′ , h). However, unlike reinforcement learning, we do not know y t ′ for t ′ > t and we must instead make a sequence of decisions using state y t . The sequence of decision made by the learner is ĥ>t = ( ĥt+1 , . . . ) whereπ⊤ t ′ = π ⊤ t t ′ s=t+1Γt ( ĥs-1 ), π t = (1 -y t , y t ) ⊤ , i.e., π t ′ is the estimated distribution over the state at time t ′ , andĥt ′ +1 = arg max h π ⊤ t ′ Qt (•, h).In Fig. 1 , we have used θ 0 = θ 1 = 0.1 and a discount factor γ = 0.9. We find that this learner approaches the Bayes risk (0.357 which we calculate in Appendix B.2).Like we discussed in Scenario 3, in order to prospect meaningfully for some stochastic processes, we might need to consider a discounted future loss, e.g., the one in Eq. ( 4). Theorem 1 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ℓ (τ ) t (h, Z; γ) = 1 -γ 1 -γ τ +1 t+τ s=t+1 γ s-t-1 ℓ(hs(xs), ys),where ℓ : Y × Y → [0, 1] is a bounded loss function and 0 < γ < 1 is a constant. In general, we can use a probability measure µ (τ ) supported on integers {1, . . . , τ } to write the loss asEQUATIONThe averaged loss in Eq. ( 1) corresponds to µ (τ ) s = 1/τ for all s. The discounted loss above corresponds to µ (τ )s = 1-γ 1-γ τ +1 γ s-1 .In prospective learning, we are interested in the case when τ → ∞ and therefore let us definelt (h, Z; µ) = lim sup τ →∞ ℓ (τ ) t (h, Z; µ (τ ) ).where µ denotes the collection {µ (τ ) } ∞ τ =1 . We can define R t (h; µ) and R * t (µ) for this discounted loss using similar expressions as those in Eqs. ( 2) and (3). For clarity, let us use the notation R t (h, 1/τ ) ≡ R t (h) and R * t (1/τ ) ≡ R * t for the prospective risk and prospective Bayes risks corresponding to the averaged loss corresponding to µ (τ ) s = 1/τ .Corollary 2 (Prospective ERM is a strong learner with discounted losses). Let the assumptions of Theorem 1 hold. If there exists a constant c > 0 such that ∀Z ∈ Z,EQUATIONi.e., if gap in 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 in Eq. (8) (implemented with the averaged loss) is a strong prospective learner, i.e., its discounted risk R t ( ĥ, µ) converges to the discounted Bayes risk R * t (µ).Proof. The assumption in Eq. ( 12) ensures thatP R t ( ĥ, µ) -R * t (µ) ≥ cϵ ≤ P R t ( ĥ, 1/τ ) -R * t (1/τ ) ≥ ϵ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.A corresponding Theorem 2 also holds for the discounted future loss. Note that Theorems 1 and 2 also hold in a slightly general setting when the measure µ (τ ) (ω) is a random variable that depends upon the realization of the stochastic process ω ∈ Ω.Suppose we have a stochastic process such that Z t ∼ p (t mod T ) for some known period T , i.e., data is independent across time but not identically distributed, and the loss function ℓ(t, •, •) is timeinvariant. Scenario 2 is a special case with T = 2. Assume that we can find a countable hypothesis class G that contains the Bayes plug-in estimator for each p t with t ∈ {1, . . . , T }. Then H T = {h : h t+T = h t and h t ∈ G ∀t} satisfies Eq. ( 9), and it is also countable. This implies consistency and uniform concentration of the limsup for sequences in some sub-classes {H t } ∞ t=1 that expands to H T . Note that even if we do not know the period, we can still implement prospective ERM using the hypothesis class ∪ T ∈N H T ; this is a countable set. Prospective ERM is therefore a strong prospective learner if the period T is bounded. Remark 4 (Implementing prospective ERM for periodic processes). If G has a finite VCdimension, choosing H t = H T for any t > T as the increasing sequence of hypothesis classes in Theorem 1 guarantees the existence of limm→∞ 1 m m s=1 ℓ(s, hs(xs), ys). We can therefore choose u t = t in Eq. ( 7) and thereby select ĥ = arg min in Eq. (8) . For H t = H T 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 {z sT +k } ∞ s=0 , k ∈ {1, ..., T }. Observe that this is precisely the prospective learner we used for the example in Scenario 2 and Fig. 1 . Remark 5 (Sample complexity of prospective ERM for a periodic process). We can calculate the sample complexity by exploiting the relatedness of the different distributions in the periodic process. First assume t > T , i.e., at least one sample from each distribution is available. We again pick H t = H T for all t > T . Let us assume that ĥt ∈ G for all times t. Let C ≡ C(ϵ/16, G T ) denote the covering number of a hypothesis class of T -length sequences of hypotheses G T = {(h, . . . , h) : h ∈ G} using balls of radius ϵ/16 with respect to loss ℓ. Then, using Baxter [84, Theorem 4] we can show that, ifEQUATIONthen for prospective ERM in Eq. ( 8) we haveE R t ( ĥ) ≤ lim t→∞ E inf h∈H T R t (h) + 2ϵ,with probability at least 1 -δ. The sample complexity in Eq. ( 13) is dominated by the first term in the curly brackets; Baxter [84, Lemma 5] shows that C(ϵ, G T ) ≤ (C(ϵ, G)) T . Sample complexity of prospective ERM grows at most linearly with the period T , as one would expect. Remark 6 (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 t ∈ R and outputs Y t ∈ {-1, 1}. Suppose Y t ∼ Bernoulli(0.5). The distribution P(X t | Y t = y) is a Gaussian with mean yµ + ∆(t mod T ) and variance σ 2 . In words, for even times t, the mean of the Gaussians are shifted to the right by ∆. Consider the time-invariant squared error loss ℓ(s, ŷ, y) = (ŷ -y) 2 . Choose (c, ∞ ) : c ∈ 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 et al. [61] for FLD can be used to show that if H t = {(h, h, . . . ) : h ∈ G} for all times t, then a time-agnostic ERM has riskG = {1 A : A ∈ {(-∞, c),E R t ( ĥ) → 1/2 [Φ (∆/(2σ) -µ/σ) + Φ (-∆/(2σ) -µ/σ)] ,where Φ is the Gauss error function. But if H t = {(h 1 , h 2 , h 1 , h 2 , . . . ) : h 1 , h 2 ∈ G} for all times t, then prospective ERM can achieve Bayes riskE R t ( ĥ) = Φ -tµ/(2σ)(t/2(t/2 + 1)) -1/2 → Φ(-µ/σ) = E R * t .Remark 7 (Hidden Markov Models (HMMs)). Suppose Z is sampled from an HMM whose hidden states evolve according to a k th -order time-homogeneous Markov process with a finite state space. Select a hypothesis class H k that consists of sequences h ∈ H k such that each h satisfies ∀t ∈ N : h t ∈ G and, ∀t 1 , t 2 ∈ N : if h t1+s = h t2+s ∀s ∈ {1 . . . , k} , then h t1+k+1 = h t2+k+1 . This is the hypothesis class that contains sequences of predictors that depend only on the past k predictors. If we assume, as above, that G is countable, then so is H k . And it also satisfies Eq. ( 9) because of the k th -order Markov property. We can therefore implement prospective ERM using H k as the hypothesis class. Observe that in the case when the Markov process underlying the HMM is deterministic, our example models the output from an auto-regressive language model that uses greedy decoding. The length of the context window is k, the hidden state of the HMM is the logit at each step (the next hidden state is a deterministic function of the previous k ones), and the output of the HMM Z t is the next token. Our theory therefore shows that the output of such a model is prospectively learnable if the learner has access to the sequence of tokens. P 1 (X = x) = P 2 (X = x) = 1 2 ∀x, P 1 (Y = 1 | X = x) = θ if x = 1 1 -θ if x = -1, P 2 (Y = 1 | X = x) = 1 -θ if x = 1 θ if x = -1,In other words, the inputs have the same marginals but the labels are flipped between P 1 and P 2 . Consider a stochastic process Z such that Z 2t+1 ∼ P 1 and Z 2t ∼ P 2 where t ∈ N.Let G be any hypothesis class and let ℓ(s, ŷ, y) = 1(ŷ ̸ = y) be the time-invariant zero-one loss. The time-agnostic learner uses a sequence of hypotheses h ≡ (h t ) where h t = h t ′ ∀ t, t ′ ∈ N to make predictions at all times. The future loss islt (h, Z) = lim τ →∞ 1 2τ t+2τ s=t+1 ℓ(s, hs(Xs), Ys) = R 1 (h) + R 2 (h) = 1 2 ,almost surely; here R 1 (h) and R 2 (h) are risks on data from distributions P 1 and P 2 at odd and even times, respectively. The last equation follows from the fact that R 1 (h) = 1 -R 2 (h) because the labels are flipped. Prospective Bayes risk is zero if the hypothesis class G contains the Bayes optimaly = 0 y = 1 y = 0 y = 1 -1 1 1 -1 P 1 P 2 Figure A.3:A simple stochastic process that is not weakly prospectively learnable.hypotheses for each of the two distributions. The future loss evaluates to 1/2 for all realizations and so does the prospective risk. The prospective risk of a 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.-1 1 1 -1 P 1 P 2 0 0 y = 0 y = 1P 1 (X = x) = P 2 (X = x) = 1 3 ∀x, P 1 (Y = 1 | X = x) = θ if x ≤ 0 1 -θ if x = 1, P 2 (Y = 1 | X = x) = 1 -θ if x ≥ 0 θ if x = -1.Inputs are supported on the set {-1, 0, 1} this time. Again consider a stochastic process Z such that Z 2t+1 ∼ P 1 and Z 2t ∼ P 2 for t ∈ N. For a time-agnostic learner, since its hypothesis h at each time step has to predict incorrectly at x = 0, we haveR 1 (h) + R 2 (h) ≥ 1 3 . The future loss is lt (h, Z) = lim τ →∞ 1 2τ t+2τ s=t+1 ℓ(s, h(Xs), Ys) = R 1 (h) + R 2 (h) ≥ 1 3 .almost surely. It follows that the prospective risk R t (h) ≥ 1 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 ŷ = ±1 with equal probability has R 0 t = 0.5. If the data contains samples for x ∈ {-1, 1}, ERM will select a hypothesis that minimizes the empirical risk which necessitates that h(1) = 0 and h(-1) = 1. Therefore R 1 (h) + R 2 (h) ≤ 1 3 + ϵ, since h predicts correctly at x = ±1, and incorrectly at x = 0 exactly one of the two distributions. The constant ϵ can be chosen to be ∝ t -1/2 after receiving data from t timesteps. The probability with which we do not get samples at x = 1 or at x = -1, is 2 × 3 -t . Therefore the probability that R 1 (h) + R 2 (h) ≤ 1 3 + ϵ is at least 1 -3 -t+1 after t time steps. This learner is therefore better than the chance learner whose risk is R 0 t and it is a weak prospective learner. This shows that there exist stochastic processes that are weakly prospective learnable using time-agnostic ERM but not strongly.We first show that for each Z ∈ Z, if Eqs. ( 6) and ( 7) holds, then the risk of estimator in Eq. ( 8) converges in probability to the Bayes optimal, i.e.P R t ( ĥ(t) ) -R * t < ϵ → 1.By takingt = max t : P R t ( ĥ(t) ) -R * t < ϵ ≥ 1 -δ ∀t ′ ≥ t, Z ∈ Zwe 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 a random hypothesis h (t) ∈ σ(Z ≤t ) converging to the Bayes optimal risk under the consistency assumption. First we define the shorthandem(h) ≡ 1 m m s=1ℓ(s, hs(Xs), Ys).Lemma 3. For a stochastic process Z, for an increasing sequence of hypothesis H 1 ⊆ H 2 ⊆ . . . such that the consistency condition in Eq. ( 6) is satisfied, for any u t satisfying u t ≤ t, u t → ∞, there exists h (t) ∈ σ(Z ≤t ), a H t -valued random variable, such thatEQUATIONalmost surely.Proof. By Eq. ( 6), there exists h (t) ∈ σ(Z ≤t ), a H t -valued random variable such thatlim t→∞ E R t (h (t) ) -R * t = 0Here, h (t) ∈ σ(Z ≤t ) means that h (t) is constant on the set {Z ≤t = z ≤t }. By the assumption on h (t) , we haveR t (h (t) ) ≥ inf h∈Ht R t (h) ≥ R * t almost surely. We can choose a sub-sequence {j k }, such that E R j k (h (j k ) ) -R * j k ≤ 4 -k .For all random variables h (t) satisfying the above assumption, the bounded convergence theorem implies thatE[R t (h (t) ) -R * t ] = E E lim sup em(h (t) ) | Z ≤t -R * t = E E lim i→∞ sup ui≤m≤∞ em(h (t) ) | Z ≤t -E R * t = lim i→∞ E E sup ui≤m≤∞ em(h (t) ) | Z ≤t -R * tIn particular, this implies that for any integer k there exists an integer i k such thatE E sup ui k ≤m≤∞ em(h (j k ) ) | Z ≤j k -R * j k ≤ E R j k (h (j k ) ) -R * j k + 4 -k ≤ 2 × 4 -k .By the definition of limsup, we haveE sup ui≤m≤∞ em(h (t) ) | Z ≤t ≥ E lt (h (t) , Z) | Z ≤t ≥ R * tand therefore we can use Markov's inequality to get∞ k=0 P E sup ui k ≤m≤∞ em(h (j k ) ) | Z ≤j k -R * j k > 2 (1/2)-k ≤ ∞ k=0 1 2 (1/2)-k E E sup ui k ≤m≤∞ em(h (j k ) ) | Z ≤j k -R * j k ≤ ∞ k=0 2 2 (1/2)-k 4 -k < ∞.Therefore, by Borel-Cantelli lemma, with probability one, there exists a (random) integer k 0 such that for all k ≥ k 0 ,E sup ui k ≤m≤∞ em(h (j k ) ) | Z ≤j k -R * j k ≤ 2 (1/2)-kWe will now scale i k , j k by some integer k t such that i kt , j kt ≤ t. This ensures that u i k t ≤ u t and H i k t ⊆ H t . This scaling is necessary to relate the "empirical estimate" of the lim sup of ĥ to the actual lim sup of h (t) . To that end, definek t = max{k ∈ N ∪ {0} : max{i k , j k } ≤ t}.Since i k ≤ ∞ and j k ≤ ∞, we also have lim t→∞ k t = ∞. Let α t = 2 (1/2)-kt and notice that α t → 0. We can construct an integer-valued random variable t 0 such that for all t ≥ t 0 , we have k t ≥ k 0 , and therefore E   sup ui k t ≤m≤∞ em(h (j k t ) ) | Z ≤j k t   -R * j k t ≤ α t . Now choose h (t) = h (j kem(h (t) ) | Z ≤j k t -R * j k t ≤ E   sup ui k t ≤m≤∞ em(h (t) ) | Z ≤j k t   -R * j k t ≤ α t Since α t → 0, we have E sup ut≤m≤∞ em(h (t) ) | Z ≤j k t -R * j k t → 0 a.s.Again using the bounded convergence theorem,E sup ut≤m≤∞ em(h (t) ) | Z ≤t -R * t → 0 a.s.Now we continue the proof of Theorem 1 by exploiting the convergence of the empirical lim sup to the true lim sup. We construct a sub-sequence of integers i t such that γ it in Eq. ( 7) decays exponentially. Markov's inequality implies that∞ t=0 P max h∈Hi t lt (h, Z) -max ui t ≤m≤it em(h) > √ γ it ≤ ∞ t=0 1 √ γ it E max h∈Hi t lt (h, Z) -max ui t ≤m≤it em(h) ≤ ∞ t=0 √ γ it < ∞.By the Borel-Cantelli lemma, with probability one, there exists t 1 ∈ N, random, and Let {h (t) } ∞ t=1 , where h (t) ∈ σ(Z ≤t ) is a H it -valued random variable chosen as in Lemma 3 with H t chosen to be H it and u t chosen to be u it . Since ĥ(t) ∈ σ(Z ≤t ), with probability one, for t ≥ t 2 , lt ( ĥ(t) , Z) ≤ max ui t ≤m≤t em( ĥt 1 ∈ F , such that ∀t ≥ t 1 , max h∈Hi t lt (h, Z) -max ui t ≤m≤it em(h) ≤ √ γ it . Let j t = max{t ′ : i t ′ ≤(t) ) + √ γ it ≤ max ui t ≤m≤t em(h (t) ) + √ γ it ≤ sup ui t ≤m≤∞ em(h (t) ) + √ γ it .Hence,E lt ( ĥ(t) , Z) | Z ≤t -E sup ui t ≤m≤∞ em(h (t) ) | Z ≤t → 0almost surely. By Lemma 3, we have,E l( ĥ(t) , Z) | Z ≤t -R * t → 0almost surely. Hence, by the bounded convergence theorem,0 = E lim t→∞ E l( ĥ(t) , Z) | Z ≤t -R * t = lim t→∞ E E l( ĥ(t) , Z) | Z ≤t -R * t which implies that P R t ( ĥ(t) ) -R * t ≥ δ ≤ 1 δ E E l( ĥ(t) , Z) | Z ≤t -R * t → 0.We have therefore proved that ĥ(t) is a strong prospective learner.This construction follows closely with Hanneke [85, Section 4], and we omit some details here. For finite class H of sequence of hypothesis, we give a possible choice of u t withEQUATIONfor all process Z in the finite family Z. For a data sequence z = {zs = (xs, ys)} ∞ s=0 and a hypothesis sequence h ∈ H, we defineEQUATIONu h t (z) = max{u ∈ {1, . . . , t} : t ≥ t h u (z)}, u H t (z) = min h∈H u h t (z);note that H is finite and therefore the minimum exists. For the stochastic process Z, letu H t (δ, Z) = max u ∈ {1, . . . , t} : P z∼Z (u H t (z) ≥ u) = 1 -δ , u t (Z) = max s ∈ N ∪ {0} : u H t (2 -u , Z) ≥ u , u t = min {u t (Z) : Z ∈ Z}Since Z is finite, we have u t → ∞. And we also have ∀Z ∈ Z,P u H t (Z) ≥ u t ≥ 1 -2 -ut ,By Borel-Cantelli Lemma, this construction gives a sequence u t s.t. Eq. ( 15) holds, i.e. ∀Z ∈ Z, Suppose {H t } ∞ t=1 is a sequence of non-empty finite sets of hypothesis sequences, and {γ t } ∞ t=1 is a sequence in (0, ∞) with γ 1 ≥ 1. Then for any finite family Z, we can extend this construction to get a choice of u t , H t and γ t such that Eq. ( 7) holdsE max h∈Ht lt (h, Z) -max ut≤m≤t em(h) ≤ γ t .Since we have a u t for a given hypothesis class H, for each i ∈ N, we can construct a sequence{u i,t } ∞ t=1 such that lim t→∞ u i,t = ∞, u i,t < t and ∀Z ∈ Z, lim t→∞ E sup t ′ ≥t max h∈Hi lt (h, Z) - max ui,t≤m<n ′ em(h) = 0.j t = max i ∈ {1, . . . , t} : ∀i ′ ≤ i, sup t ′′ ≥t E sup t ′ ≥t ′′ max h∈H i ′ lt (h, Z) - max u i ′ ,t ′′ ≤m≤t ′ em(h) ≤ γ i ′ ∀Z ∈ Z and t i = min t : j t ≥ i, u i,t > u i-1,ni-1 .If i t = max {i : t i < t}, then we have i t → ∞, and for u i = u i,ti we haveE max h∈Hi t lt (h, Z) -max ui t ≤m≤t em(h) ≤ γ it .Since H is countable, we can choose a sequence of finite hypothesis classes H t such that ∪ t∈N H t = H. By choosing u t = u it , with H t = H it , and γ t = γ it , we now have a possible choice for u t , H t and γ t in Theorem 1.Training setup. Each learner receives a t-length sequence of samples z ≤t 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 t ′ > t 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 z ≤t , a time-aware hypothesis class minimizes the empirical prospective risklt (h, Z) = 1 t t s=1ℓ(s, hs(xs), ys);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 cosine-annealed learning rate. The networks are trained at a learning rate of 0.1 for the synthetic tasks, and learning rate of 0.01 for MNIST and CIFAR. The weight-decay is set to 1 × 10 -5 . The images from MNIST and CIFAR-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.Evaluation We estimate the prospective risk of each learner using a Monte Carlo estimate. For a given training dataset z ≤t , we estimate a sequence predictors h ≡ (h t ) which we use to make predictions on future samples. We wish to approximate the prospective risk (Equation ( 2)) for the estimated sequence of predictors. We do so, for a single future realization z >t of this process, which yields the estimateRt (h) = 1 (T -t) T s=t+1ℓ s, hs(x j s ), y j s ) .In our 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 5 random seeds. We considered the following architecture choices for the time-agnostic restropective algorithms like ERM that ignore time and the ordering associated with the samples in z ≤t .Retrospective-MLP/CNN. 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 a small convolutional network with 0.12M parameters. It comprises of 3 convolution layers (kernel size 3 and 80 filters) interleaved with max-pooling, ReLU, batch-norm layers, with a fully-connected classifier layer.Prospective ERM with MLP and CNNs. In order to incorporate time into the hypothesis class, we consider an embedding function φ : R R d takes raw time as an input and returns a d-dimensional vector denoted as the time-embedding. In our experiments, we define φ : R → R d as a function that maps t → (sin(ω 1 t), . . . , sin(ωd/2t), cos(ω 1 t), . . . , cos(ωd/2t)), where, ω i = π/i, i = 1, . . . , d/2 to the be the collection of angular frequencies. We briefly discuss the rationale for this choice in We make our classifiers a function of time by including time t as an input the neural network. This allows the network to vary its hypothesis over time. For MLPs, we concatenate the input with its corresponding time-embedding φ(t) 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) .Frequencies for embedding time In the original Transformer architecture, Vaswani et al. [55] use a position-embedding using the frequencies ω i = 1/10000 2i/d i = 1, . . . , d/2. There are two key differences: (1) We use the absolute time t instead of the relative position, (2) We use the angular frequencies 2π/i. In Figure A.7 (right), we illustrate the time-embeddings 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 MLPs and CNNs that use the frequencies from Vaswani et al. [55] perform poorly on the MNIST task for Scenario 2 and 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-Leader does not achieve a low prospective risk. Bayes risk for MNIST and CIFAR-10 problems is calculated by assuming that Bayes risk on individual tasks is zero.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 For a task defined on a stationary Markov process, the Bayes risk is trivial and can be achieved by a hypothesis that doesn't change over time. 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, both follow-the-leader and prospective ERM approach the Bayes risk. The stationary distribution has an equal probability of seeing either task and a fixed hypothesis can achieve Bayes risk on this problem.H Large language models may not be good prospective learnersIt is an interesting question whether LLMs which are trained using auto-regressive likelihoods with Transformer-based architectures can do prospective learning. To study this, we used LLama-7B [86] and Gemma-7B [87] to evaluate the prospective risk for Scenarios 1 to 3. The prompt contains a few samples from the stochastic process (sub-sequences of (Y t ) consisting of 0s and 1s) 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 in Appendix H.1; we also experimented with a few variants of these prompts. 38th Conference on Neural Information Processing Systems (NeurIPS 2024).We will use some non-standard notation in this paper. In particular, a hypothesis h will always refer to sequence of predictors h ≡ (h1, . . . , ht, ht+1, . . . ). This helps us avoid excessively verbose mathematical expressions.When we say that "learner selects a hypothesis" in the sequel, it will always mean that the learner selects an infinite sequence from within the hypothesis class H.The limsup is guaranteed to exist if ℓ is bounded. If the series converges, we can use 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 a 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.We 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 a posteriori estimator.Also see Appendix A for a more elaborate discussion.We can also define weak learnability 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.Note that this hypothesis class has infinite sequences, Ht ⊆ Y X N .Hereafter, when we write ERM in empirical studies, we will mean a learner that approximates ERM via stochastic gradient descent.For CNNs on CIFAR-10, if one concatenates the time embedding directly to 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 1 is true in general.As we discussed in Scenario 3, prospective Bayes risk can be trivial in situations when the stochastic process has a stationary distribution. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

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.
questions: 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.

Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations Research, 63(5):1227–1244, 2015.
limitations: 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.
paper_summary: paper_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.  
---
This 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.  

notes from reading the paper: 
  -Prospective learning is time-aware alternative to PAC learning.  
  -Paper shows failure cases of PAC learning on some simple problems and also establishes some new algorithms on MNIST/CIFAR variants.  
  -Prospective learning assumes data is drawn from an unknown stochastic process.  
  -Data defined as z_t = (x_t, y_t).  
  -Prospective learner maps from history of data to sequence of hypotheses on all time steps.  
  -Only focus on expected future loss, and not risk.
strength_weakness: strength_weakness: -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.
questions: 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: 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).
paper_summary: paper_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.
strength_weakness: strength_weakness: - Paper fails to explain how training on unlabeled data would be yield in the proposed paradigm.
- 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.
- 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.
questions: 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: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
- 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).
questions: 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?

2.- 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?

3.- 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.

4.- 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?

5.- 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$?

6.- 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: limitations: The authors discuss the limitations of their work.

Comments: title: Gentle reminder
Rebuttal by Authors pt. 2
Rebuttal by Authors Pt. 2
comment: Thanks to the authors for addressing my concerns. I am satisfied with the above clarifications.
Thank you for your detailed answer to my questions! I am satisfied with the feedback and maintain my score, in favor of accepting the paper.
We thank the reviewers for their feedback. We eagerly await your response to our rebuttal and would love an opportunity to discuss your concerns. If you think our rebuttal is satisfactory, we would be grateful if you could increase your score.
Thanks to the authors for the clear responses to my concerns. I've decided to raise my score and confidence. Nice work!
Thank you for taking the time to respond to our rebuttal. We are glad that your concerns were addressed. If you are satisfied with our response, we would be grateful if you could raise your score and champion the acceptance of our paper.

> **The old data distribution had a steady-state distribution, which had a higher Bayes risk—why is this?**  
> **What is the difference between the original scenario 3 experiment in Section 5 and the new one?**

Consider the following example. Suppose we have a Markov chain corresponding to switching between two tasks $P\_1$ and $P\_2$ with a transition matrix \[\[0.2, 0.8\], \[0.8, 0.2\]\], i.e., if the data at the current timestep was drawn from $P\_1$, in the next timestep, data will be drawn from the task $P\_2$ with probability 0.8. The steady-state distribution of this Markov chain is \[0.5, 0.5\]. In other words, as the Markov chain approaches the steady-state distribution (which happens asymptotically), the prospective learner loses the ability to predict which state the Markov chain will be at some future time $t’$. The prospective risk in Eqn. (1) takes the limit $\\tau \\to \\infty$.

Suppose now that task $P\_1$ has classes $\\{1, 2\\}$ and task $P\_2$ has classes $\\{2, 1\\}$, i.e., the labels are flipped, then the prospective Bayes risk is trivially 0.5. If the classes do not “clash”, i.e., $P\_1 \\equiv \\{1, 2\\}$ and $P\_2 \\equiv \\{3, 4\\}$, then notice that a learner that predicts both $\\{1, 3\\}$ for inputs corresponding to ground-truth classes 1 and 3, and both $\\{2, 4\\}$ for inputs from ground-truth classes 2 and 4 will achieve zero prospective risk. Therefore, a trivial Bayes risk in prospective can come from (a) the Markov chain having a steady-state distribution, and (b) clashes of the classes between the tasks.

In the Scenario 3 example in the original submission, we had chosen an example where both (a) and (b) were occurring. The stationary distribution for Figure 3 was a weighted mixture of the distributions of the 4 tasks created from the CIFAR10 dataset (transition matrix is $\\Gamma\_4$ on Line 740 in Appendix C) and tasks were the ones given on Line 728 in Appendix C (which do “clash”). As a result, no single hypothesis can simultaneously achieve low risk on data from all 4 tasks. Hence, no hypothesis can achieve a low risk on the stationary distribution, in other words the prospective Bayes risk is high.

On the other hand, the example in the rebuttal PDF considers a hierarchical HMM which does not have a stationary distribution. The hierarchical HMM transition every 10 steps across two sets of communicating states. As a result, the distribution in the future is predictable, and there exists a hypothesis that achieves a low prospective risk on this distribution. 

> **Would the time-agnostic MLP model be able to solve the task if some context information (e.g., the current task ID) were given as input?**

Yes. However, task boundaries are not available in prospective learning.

> **Are you providing any context information to the time-aware model?**

No. There is no contextual information available to the time-aware learner.

> **If not, is the time-aware model somehow inferring the hidden state of the data generation process?** 

Yes. Think of how an ideal prospective learner might work: it would observe the data at each time-step, use an algorithm like Baum-Welch to estimate the transition matrix for the tasks and build a hypothesis for each unique task. For inference at time $t’$, it would predict the distribution over tasks at time $t’$ based on the data observed up to time $t$, and use a hypothesis corresponding to the most likely task, or sample the hypothesis with a probability proportional to its corresponding task being present at time $t’$. This is of course the ideal prospective learner, and it would converge to the Bayes risk under standard assumptions (e.g., consistency of the Baum-Welch estimates).

It is interesting that in Theorem 1, we could show that time-aware ERM can also converge to the Bayes risk. This is precisely because it is doing something equivalent to inferring the hidden state of the data generating process.

We will include this discussion as a remark at the end of Section 4\.

> **keeping that experiment and using the new one to clearly point out why we see a different result now would be really helpful for the reader.**

We will keep the original example of Scenario 3 and contrast it with the new example. We agree that this should be very useful to the reader.

> **Also, it seems that the labels in Fig. 5 are swapped.**

Indeed. We apologize for the oversight. We will fix it.

> **Q5: Thanks, this makes sense now, and I guess it is related to the explanation in Q4?**

Yes, discounting the risk changes the problem to effectively have a finite horizon. If the Markov chain does not mix by the end of this effective time-horizon, the prospective Bayes risk can be non-trivial even if the tasks clash.
Thanks to the authors for addressing my concerns. I'm generally satisfied with the clarifications provided, but I do have a few additional comments:

In Q4: What is the difference between the original scenario 3 experiment in Section 5 and the new one? The old data distribution had a steady-state distribution, which had a higher Bayes risk—why is this? Is it because the hidden state defining the task distribution was changing constantly, but the overall sampling process was in steady-state? Is the new configuration and the results shown in Fig. 5 designed to create a significant period within training (10 timesteps) with a specific hidden state, and then clearly switch between hidden states to generate a meaningful learning signal? I did my best to rephrase what I understood from the rebuttal—is the explanation along these lines?

Would the time-agnostic MLP model be able to solve the task if some context information (e.g., the current task ID) were given as input? Are you providing any context information to the time-aware model? If not, is the time-aware model somehow inferring the hidden state of the data generation process? If so, that would be useful to highlight as an advantage of the proposed method.

The fact that the originally presented model was not able to learn the task properly based on the structure of the task is not a flaw in itself. In fact, keeping that experiment and using the new one to clearly point out why we see a different result now would be really helpful for the reader.

Also, it seems that the labels in Fig. 5 are swapped.

Q5: Thanks, this makes sense now, and I guess it is related to the explanation in Q4?
> **Q5) 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 \= 1 if each hypothesis is only influenced by its own time step what is the problem with having a gamma=1**

This is a good point. Yes, future loss at time $t’$ is not affected by the current hypothesis at time $t$. We choose the discounting factor to emphasize some of the real world scenarios that only want to predict the near future. In Scenario 3, for a mixing Markov chain, choosing $\\gamma=1$ can give trivial solutions; after the Markov chain mixes completely, there are no long-term predictable patterns. However, in the near future when the chain has not mixed completely, time-aware ERM can exploit the correlations for prospective learning. One can restrict the time-horizon in prospective learning by simply cutting off time at some large value, or by discounting the loss.

> **Q6) 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.**

> **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).**

This is a very good idea and we are very thankful for it. We will update Appendix A in the camera ready version with formal connections to existing ideas in the field. This will allow us to explicitly compare the different problem setups. If this content expands beyond the scope of this present paper on prospective learning, we are very keen on writing a separate manuscript. This can be very valuable to our field.
>  **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**

We thank the reviewer for pointing us to this, and we will cite this in our paper. In the linked paper, the authors introduce an auxiliary loss during training that forces the model to predict the next $n$-tokens at once. But for inference, they only perform next-token prediction. In “our prospective transformer”, we have the network predict the outcome of a future datum, given past data in context. During inference, both networks (prospective and auto-regressive) in our work are capable of making predictions arbitrarily far into the future. This was made possible by the choice of the positional (time) embedding we use in these models, which is different from the ones used in language modeling.

All this said, please see the common response to all reviewers which discusses our proposed modifications to the experimental parts of this paper. 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). There is no need to use the prospective or auto-regressive Transformer to implement prospective learning like we had initially done in the submission. We will therefore remove the method named “prospective Transformer” in the camera ready version of the paper.

We will summarize this response as a footnote and cite the paper that you have linked to.