Martingale Posterior Neural Networks for Fast Sequential Decision Making
Authors: Gerardo Duran-Martin
Leandro Sánchez-Betancourt
Alvaro Cartea
Kevin Patrick Murphy
Venue: NeurIPS 2025 poster ()
Keywords: online learning
neural bandits
sequential decision making
Kalman filtering
frequentist
bayes
martingale posterior
Primary area: probabilistic_methods
TL;DR: Scalable online training of neural networks using frequentist filtering with martingale-posterior-inspired posteriors for sequential decision making.

Abstract: We introduce scalable algorithms for online learning of neural network parameters and Bayesian sequential decision making.
Unlike classical Bayesian neural networks,
which induce predictive uncertainty through a posterior over model parameters,
our methods adopt a predictive-first perspective based on martingale posteriors.
In particular, we work directly with the one-step-ahead posterior predictive, which we
parameterize with a neural network and update sequentially with incoming observations.
This decouples Bayesian decision-making from parameter-space inference:
we sample from the posterior predictive for decision making,
and update the parameters of the posterior predictive via fast, frequentist Kalman-filter-like
recursions. 
Our algorithms operate in a fully online, replay-free setting, providing principled uncertainty quantification without costly posterior sampling.
Empirically, they achieve competitive performance–speed trade-offs in non-stationary contextual bandits and Bayesian optimization,
offering 10–100 times faster inference than classical Thompson sampling while maintaining comparable or superior decision performance.

Martingale Posterior Neural Networks for Fast Sequential Decision Making
Gerardo Duran-Martin' Leandro Sánchez-Betancourt! Álvaro Cartea
Kevin Murphy
Oxford-Man Institute of Quantitative Finance
2 Mathematical Institute, University of Oxford Google Deepmind
gerardo . duran -tran-nartin ox ox. (leandro. sanchezbetancourt, alvaro aara kpmurphy@google..cm
Abstract
We introduce scalable algorithms for online learning of neural network parameters and Bayesian sequential decision making. Unlike classical Bayesian neural net- works, which induce predictive uncertainty through posterior over model parame- ters, our methods adopt a predictive- first perspective based on martingale posteriors. In particular, we work directly with the one-step-ahead posterior predictive, which we parameterize with neural network and update sequentially with incoming observations. This decouples Bayesian decision-making from parameter- spacc inference: we sample from the posterior predictive for decision making, and update the parameters of the posterior predictive via fast, frequentist Calman-filter-1l recursions. Our algorithms operate fully online, replay-free setting, providing principled uncertainty quantification without costly posterior sampling. Empir- ically, they achieve competitive serformance-spedd trade-offs in non-stationary contextual bandits and Bayesian optimization, offering 10-100 times faster infer- ence than classical Thompson sampling while maintaining comparable or superior decision performance.
Introduction
In various sequential decision-making problems, such as Bayesian optimization and contextual bandits, uncertainty quantification and efficient belief updates essential for balancing exploration and exploitation. A prominent Bayesian approach Thompson sampling (TS) [52], which samples from the posterior over model parameters and evaluates the corresponding predictive function (e.g.. reward or surrogate) for decision-making.
Various works combine Bayesian uncertainty with the expressiveness of neural networks for sequential decision making [5, 51]. These methods, often called Bayesian neural networks (BNNs), typically approximate the posterior over model parameters (e.g.. via variational inference) and then use this posterior for downstream tasks. However, BNNs often rely on misspecified priors and likelihoods [33], which often degrade predictive performance [60] and result in slower inference than non-Bayesian alternatives [35].
These limitations are especially problematic in online settings where updates and decisions must be made quickly, such as in recommender systems, adaptive control, financial forecasting, and large-scale Bayesian optimization [55, 43, 45, 6, 59].
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To address these problems, we present class of algorithms for Bayesian sequential decision making inspired by the predictive-firs philosophy of the martingale posterior framework [20, 26]. Our approach operates in fully online setting: the one-step-ahead posterior predictive is parameterized by neural network, updated directly from real observations via frequentist Kalman filter-style recursions, and sampled once per step for decision making. This avoids the need for costly posterior inference, while still supporting uncertainty and sampling-basee sequential decision making.
The parameters defining the predictive density are updated with a single-pass frequentist Kalman filter-style methods, which resemble online natural gradient steps [48] and require no replay buffer (copies of past observations, which one typically uses for multiple inner-iterations). We explore three structured covariance strategies: LRKF applies low-rank updates to all layers; HiLoFi applies a full-rank update to the last layer and low-rank update to the hidden layers; LoLoFi applies low-rank updates to both. HiLoFi and LoLoFi are inspired by last-layer Bayesian methods [25], and offer different tradeoff's between computational efficiency and expressiveness.
Decision making performed by sampling directly from the posterior predictive, resulting in 10 to 100 times faster inference than that of classical TS, even when compared with structured posteriors that use diagonal plus low-rank covariances [8]. Our algorithms scale million-parameter networks, maintain constant-time updates, and operate in fully online, streaming-compatin settings. In addition, our methodology supports any acquisition strategy, such as classical TS or expected improvement.
In summary, our probabilistic method for training neural networks enjoys the following properties: (i) efficient closed-form updates (no Monte Carlo sampling required); (ii) sample efficiency through low-rank Kalman filter-like updates which do not require the specification of posterior density; (iii) closed-form uncertainty-aware predictions via the posterior predictive.
We evaluate the performance of our methods across range of sequential decision-making tasks. In non-stationary neural contextual bandits, our methods achieve the highest performance at the lowest computational cost compared to that of baselines. In stationary settings such as Bayesian optimization, our approach matches the performance of replay- -uffer methods while achieving Pareto-efficient tradeoffs between runtime and performance. Our code is available at https:// gi thub. com/ gerdm/ /ta///attt/a iigalen posterior-neurrr networks.
A complete summary of the notation used throughout the paper is in Appendix A.
2 Problem statement
We consider a sequential-decinn -dcctiioi--eiiiionn-- decision--mainng agent that at time observes a context-action pair x; = (ct, a:) with context c R.D: (possibly empty) and action a, E A C R... The environment returns a reward (or observation) according to
Yt ~ Penv (. [x:),
E RD,
(I)
which depends only on the context-action pair xt. We use the notation y/ when the outcome is scalar (Dy = 1) and ye when it is vector-valued (Dy > 1).
This formulation covers, e.g., Bayesian optimization (c, empty and a, the query location), multi- armed bandits (c, empty and a, the chosen arm), and contextual bandits (c, non-empty and a, the chosen arm). also serves as a proxy representation for multi-arma bandits by letting the components of y, encode per-arm signals or auxiliary outcomes.
We write D,- = (x,, y:) for a datapoint and DI.t (Di,... ..... ).) for the dataset. Here, we assume that Panv is unknown, but we approximate it through the observation model
V = f(O, xx) + e.,
(2)
with e, a zero-mean random vector with covariance matrix R, E MM (R), f neural network, and 0, E TR. Do unknown time-varying model parameters.
The agent maintains a belief state b, that summarizes its knowledge of the environment after observing Dia This belief defines a parametric approximation to the one-step-ahead posterior predictive
Pb. (y1+1 (141) 2 p( Øt+1, P1a).
(3)

---

Our objective is to maintain b, via efficient, single-pass frequentist updates and to use the predictive Pb. (yt+1 2t+-1) for probabilistic, sample-based sequential decision making, In this sense, combine frequentist recursive parameter estimation with Bayesian decision making via the posterior predictive.
Background
3.1
Tools for sequential decision making
A central challenge in sequential decision making is the agent balances whether use its current knowledge of the environment (exploitation) or to acquire new information to improve future decisions (exploration) [3].
tradeoff, where an
For example, when solving Bayesian neural contextual bandit problems [51] with the classical Thompson sampling (TS) algorithm [52], an agent samples a parameter vector from the posterior distribution (or an approximation [50]), evaluates the reward function under this sampled parameter for each action, and selects the action with the highest sampled reward.
Here, we propose novel approach that avoids sampling from (high- (ingh-iimensioaa) parameter posteriors often found in Bayesian neural networks. Instead, we work directly with the posterior predictive distribution defined by the current belief state b,. For each candidate action, sample possible outcome from (3) and then choose the action with the highest sampled reward. The belief b, is subsequently updated via frequentist recursions (Section 3.2).
Table highlights the key differences between our predictive sampling approach and classical TS. The essential distinction is whether uncertainty is represented in parameter space (TS) or directly in outcome space (our approach). Algorithm shows our predictive sampling procedure contextual
Step
Predictive sampling (Our approach)
Classical
Sample
Posterior predictive at each action
Posterior over model parameters
Evaluate
N/A
Sampled parameters reward function
Select action
Argmax over sampled rewards
Argmux over sampled rewards
M+++1 Penv (- 2x++1)
V+++1 Penv (- ax++1
Update helief
Frequentist update (e.g., Algorithm 2)
Bayesion posterior update over parameters
Table I: Comparison between Bayesian predictive sampling (our approach) and classical Thompson
sampling. Differences highlighted in bold.
bandits. At each decision- makinn step, the agent samples rewards from the predictive distribution for each action, selects the action with the highest sampled reward, observes the reward from the environment, and updates its belief state.
Algorithm Predictive sampling for sequential decision making in contextual bandits.
Require: b, // belief state obtained time L
Require: C++11
context
Require: [b ()) // posterior predictive density parameterized by
I: for all E A do
2: & (Ct+1, a.)
3: Úr. Po, (-
5: a++1 f- arg max 1++1,a
6: met1 t (c++1, a(+1)
7: M++ ~ Pone(- 2 // observe outcome
b +- Ubdatte(., Mc4,, 21+1) // e.g, Algorithm
9: Return (b141. belief and revard
3.2 Extended Kalman filtering for online learning and sequential decision making
To maintain and update the belief state b, we adapt ideas from the frequentist perspective of the extended Kalman filter (EKF). Here, b, = (0 Σ.), Ozje Ar Vias Ar arg min B[llo:

---

A yr:ell2 is the best linear unbiased predictor (BLUP) of 0,, and Σ, = Var(O; Oaje) is the erro-vaaiiacce-ovatiiin (EVC) matrix of the estimate. The initial belief state bo = (0. En) is given.
Next, we partition the neural network parameters into last-layer weights and hidden-layer weights: 0, (Le, hi), with L E R (last layer) and h, E Rh (hidden layers) that 0. (byp. heje), and fle, x.) e o(x; he) R, where o(x, h2) is the hidden-layer feature map of the neural network.
To obtain closed-fow foosed-form updates, we linearize the neural network around the previous parameter estimate 0/-1/--1 (f--1]t-1; 1)- and make a random-walk assumption for the model parameters 8 = 0,-1 + uy, with Var(u,) = Q E M (R). This assumption prevents uncertainty collapse, adaptation in non-stationary environments, and numerical stability (see e.g., [46] or Section 2.6.4 in [13]..
With the above assumptions, we obtain the linearized state-space model
0: 0:-1 Us
(4)
y: - f(4-1]t-1 h xx)) + Le (--1/t-1) (he, h1-1(t-1) Et:
(5)
where et is zero-mean random variable with Varler] R. E M L.
(ef(4-1jt-1:: h,-1jt-111 1jt-; xx) E (R), and H, Vnf(er-Ije1 11-1p-11, 2e) are the Jaco- bians of the neural network w.r.t. the last and hidden layers respectively.
Updates. The state-space model defined by (4)-(5) allows for recursive estimation of b, via Kalman- like updates. See Appendix for details.
Posterior predictive model. At each timestep the mne-step-ahead posterior predictive induced by the state-space model (4)-(5), given the belief state b, and under the assumption p(e,) (ee 0, R2) is
Pb. (3t+1 x(+1) N yi+1 f(Orje,
J++1 E, JT
R aleatoric
(6)
epistemic
where J, = [L, H.]. Here, the covariance of the posterior predictive decomposes into epistemic uncertainty (from parameter uncertainty under the linearization) and aleatoric uncertainty (from observation noise R,). The condition R. E M)t(R) ensures that (6) defines proper Gaussian density.
3.3 Martingale posteriors
Our notion of Bayesian uncertainty is inspired by the martingale posterior framework [20], which interprets Bayesian uncertainty through missing data [26]. In the original setting, one imagines imputing an infinite sequence of future observations: statistics computed on these extended datasets form a martingale, and under mild conditions they converge.
However, in sequential decision making, however, given the context-action pair 2z+1. the only missing data, is the next observation yt++1 from the environment. In our case, uncertainty is quantified to guide decisions: Vt+11 (or partial observation of it, in the bandit setting) is always revealed before the next step. Thus, rather than simulating an infinite sequence future steps, we focus entirely on the one-step-ahead posterior predictive Pb, (y++1 1z+1).
4 Method
The standard EKF strategy for online learning presented in Section 3.2 does not scale to large neural networks because the memory cost is ODD,²) and the compute cost is O(Dø"). A number of approaches have been proposed to tackle this issue (see Section 6 for details). Our method leverages the frequentist perspective filtering to derive low-rank updates and the Bayesian interpretation of filtering to make sequential decisions through the posterior predictive.

---

4.1 Algorithm
Consider the linearized model (5), with initial conditions
E(Lo] Lojo=
E h hojo- Var(Lo) Ee,o Var(ho) CJ Co.
(7)
for known Co E Man DD, [R), 0oo E PR, Σe,0 E M,x (R), and Rojo E Re, Next, assume that fort 2 1, the last layer parameters f1 and the hidden layer parameters h1s follow the dynamics
L, P-1 ue h; h + Uh,t:
(8)
where i: and Ia are zero-mean independent noise variables with covariance matrices Qe ge and Qh. Ih, with ge 2 0 and gh 0. Our method maintains belief state for the state-space model represented by b, = (leles haje: Se, C.). where Lyjs E RRPa the estimate for model parameters in the last layer, helec E DD is the estimate for model parameters in the
1/2
hidden layers. -,-1 E MM, (R) is the Cholesky EVC factor for the covariance of the last layer, and C, Ma, DDD (R) is the low-rank EVC factor for the hidden layers.
Updates. Given 1 the updated Ozje- (Beje: haje) follows directly from the EKF equations which takes the form Ozj= = 0 1 + K, where c, y/ Dr is the error or innovation term, and K, is the gain matrix. Because the block-diagonal assumption, it can be shown that K, is decoupled into last-layer-only and a hidden-layers-oni. submatrices.
Next, applying the EKF EVC update b yields the dense matrix Σ, E MM (IR which couples the effects from the last and hidden layers. To obtain block diokodiigon matrix with components 1/2 (Ee, Ct), we consider a two-stage approximation. The first stage replaces E, with surrogate
covariance matrix Σ, that avoids the interaction between the hidden layer parameters and the synthetic dynamics qh.t; the second stage approximates the surrogate matrix with the best block-diagonal approximation whose first block (for last-layer parameters) are of rank De and the second block (for hidden-layer parameters) are rank-d,- Finally, to maintain numerical stability and low-memory updates, we track the Cholesky factor for the last layer and low-rank factor for the hidden layers,
1/2 i.e., 1/2 diag(C,, Σe, ). In this sense, estimation of the factors for the last-layer and the hidden layer follows the sequence
E, 1/2 diag( (C,, Σg, ).
112
Σ
Algorithm shows single step of LiFi. The derivation Appendix D.1.
The following proposition shows the upper bound of the the per-step error incurred by HiLoFi
Proposition 4.1 (Covariance approximation error). At time t, the per-step approximation error of HiLoFé under the linearized SSM (5) is bounded by
Dr Σ
EEe Éejelle S Th Ep + Ge,t Eg,sure +
2 R,KKK 11
(9)
A=
where Ei,surr =
+ |K,,H, Ex ()x) Dn k= are smallest (Dn, dn) eigenvalues of E,
II(I Ke L.) (I Ke, L.)T and
Remark 4.2. Proposition 4.1 shows that the per-step error in the HiLoFi approximation bounded by: (i) the neglected terms by each surrogate matrix, (ii) the low-rank approximation for the covariance of the hidden layers, and (iii) the cross-terms from the blocks in the off-diagonal Note, however, that the bound does not account for error due linearization of the neural network. One could minimize the above lower bound by setting Jh.t = qe, = 0. However, this may result in lower per-step performance. See Appendix G. for an example of the main sources of emor. See Appendix E.4 for a proof.
Posterior predictive model. After every update, the posterior predictive model used for sequential decision making
Pb. (ge+1 T++1) -N (ye [(lee, hije F(41), Lep Ee + Hen En, + Ret1).
(10)
5

---

Algorithm Single update step of HiLoFi. The notation QR(BI,.... , denotes the Cholesky factor- ization matrix _X-1 B BR, where Bş is an upper-triangular Cholesky factor; see Appendix C. for details. The function Pa(AA1..., Aς) returns a d x D matrix which is the best rank-d approximation of the matrix _k-1 A7 As; see Appendix C.2 for details.
Require: R₁ // measurement variance
Require: (ge.z, (h.:) // dynamics covariance for last layer and hidden layers
Require: (Yi; 2t) observation and context ceattexttcction pair
Require: b
10-11-1,,4-11--- 11 Cc-1) // previous belief
// predict step
1: y: (44--1c-1,
2: L. Vef(Cr-|ttb 11-1 21)
3: H. Vaf(e--1e-1; 111-11-1 x+)
// innovation (one-step-ahead error) and Cholesky innovation variance
6 < y) -- ÿt
5: S. = Qr - L,, v VTa LJ Cc-1 HJ, Vh,, Hi, R, ?
// gain for hidden layers
6: Va, <- S, S, S,
7: KT. + Vn. C.-1 C + th.t Va.
// gain for last layer
Ve. < S. S// S, I
9: K,,- + Ve, E qe. Ve.
//
update step
10: baj -h-11111 + Kn,tt
11: lut &- 8--11-1 +
+ Ketti
1/ EVC low-rank and Cholesky update step
12: C. Paniton. (Co-1 (I- Kn, Ho) / kh.t)
13: Ee, <- QR (De--1s (1- (e), R. "T,)
1/2 Return b, = (lic,ter Se, Ct) // updated belief
D2y)). A full breakdown The computational complexity of HiLoFi is O(D2 (D)+Dy) Dn, (d, of the computational complexity and its relationship other methods is in Appendix D.2.
Variants. Whenever the output layer or the input to the last layer is high dimensional, we perform a low-rank approximation the last-layer to reduce computational costs. We call this variant LoLoFi. Its computational complexity is O(D," + Dndn.") See Appendix F.1 for details.
purely low-rank version of our method, which we call LRKF, is discussed in Appendix F.2. This method uses a single low rank covariance matrix approximation for all parameters in the neural network. An етгог analysis LRKF in the linear setting is presented in Appendix F.2.1. In the experiments, we find that this approach performs worse than that of HiLoFi, which is not surprising. also has lower performance than LoLoFi (at least on the contextual bandit problem in section 5.2), presumably because modeling the last layer separately allows to use a different subspace for the low rank approximation the output layer weights.
5 Experiments
In this section, we evaluate method, First, consider one-dimensional example "in-hetween" uncertainty, to illustrate the behavior of the method. We then compare its performance to that of other methods across the following sequential decision-making tasks:
(I) MNIST for classification as a bandit problem: This is an online high-dimensional classifi- cation problem, which study contextual bandit problem.
(II) Recommender systems: This challenging real-world problem with non-stationary data. Here, tackling exploration-cxplooittion tradeoff is key.

---

(III) Bayesian optimization: The goal of this task is to find the maximum of an unknown blackbox function g [0, [0. + R. This is a static inference problem where sample efficiency and uncertainty quantification are crucial.
For each of the above tasks, we assess the various methods on predictive performance and wall- clock time. All experiments were run on TPU v4-8. An additional experiment demonstrating the scalability of LRKF to multi-million-prrmmett neural networks for online classification is provided in Appendix G.2.
We consider the following variants of our framework. High-rank low-rank filter (HiLoFi): Our main method that uses full rank for last layer and low rank for hidden layers. Low-rank low-rank filter (LoLoFi): A version of our method that uses low-rank matrices for last and hidden layers. We only consider LoLoFi in task (II), due to the relatively large dimension of the last layer. Low-rank square-root Kalman Filter (LRKF): This is special case of our method, described in Appendix F.2, that uses a single low-rank covariance for all the parameters. This illustrates the gains from modeling the final layer separately.
As existing baselines, we consider the following. Diagonal plus low-rank precision (LoFi) [8]: a fully online method that models the precision matrix using a low-rank plus diagonal matrix, and uses the same linearization scheme as us. Gaussian processes (GP) [62]: a standard approach to modeling predictive uncertainty. We only include GPs in the low-dimensional tasks in (III) because of scalability limitations. Variational Bayesian last layer (VBLL) [5]: a partially Bayesian method that requires access to the full dataset (or replay buffer), and performs multiple optimization steps per update. See Appendix F.3 for details. Online variational Bayesian last-layer (OnVBLL): a straightforward modification of the VBLL method with a first-in frest-in-first-or first-out (FIFO) buffer and no regularization. Last-layer Laplace approximation with FIFO buffer (LLL) [11]: a method that uses Laplace approximation on the last layer, with FIFO replay buffer and multiple inner updates per time step. Unless otherwise stated, we train the parameters of the neural network with the Adam optimization algorithm [44].
5.1 In-between uncertainty
Problem description. In this experiment, we test the ability of HiLoFi to capture the in-between uncertainty [21] after single pass of the data. This concept refers to how well model captures uncertainty in regions of input space that lie between, or away from, observed data. Intuitively, we expect uncertainty be higher in such unexplored areas. This behavior is important for Bayesian decision-making problems for effictive balancing of exploration and exploitation. We consider the one-dimensional dataset introduced in [58].
Model. We use an MLP with hidden layers and 128 units per layer, and we employ an ELU activation function.
Results. Figure shows the evolution of the posterior predictive mean and the posterior predictive variance as a function of the number of seen observations. We see that HiLoFi behaves in an intuitively sensible way, showing more uncertainty away from the data, just like Gaussian process. See Appendix G.5 for the performance of other methods (specifically LRKF and VBLL) on this problem, well an ablation study that illustrates the effect of changing rank.
5.2 MNIST
Problem deseription. We consider the MNIST contextual bandit task introduced by [49], where the agent is presented with an image and must choose one of possible classes as an action, and then gets binary feedback, based on whether its prediction was correct not; we refer to this as the incomplete information case. additional experiment on online classification in Appendix G.I.I.
Model. The predictive model (for the 10 label logits or the per-action rewards) is represented using modified LeNet5 CNN architecture [39] with ELU activation function.
7

---

num. obs =
num, obs = 5
num. obs 10
10
0
-10
num. obs
15
num. obs 30
num. obs
45
10
0-
-10
num. obs 50
num. obs 100
obs 120
10
0-
-10
-0.5
0.0
0.5
0055
0.0
0.5
-0.5
0.0
0.5
Figure 1: In-between uncertainty induced by HiLoFi as a function of the processed observations.
Exploration Methods. We consider two exploration strategies: Classical TS and our proposed predictive-sampling (PS) as outlined in Table 1. Additional results comparison TS, PS, and e-greedy are in Appendix G.1.3.
Inference methods. We compare LLL, LRKF, LoFi, and HiLoFi. For LLL, use the online last-layer variant from [11], without hyperparameter re-optimization at each timestep. Choice for hyperparameters are detailed Appendix G.1.3.
Bandit results. Figure 2 shows the average cumulative reward over 10 runs of the contextual bandit version of MNIST. We observe that the top three performing methods are HiLoFi, LoLoFi, and LRKF. This outcome is expected because HiLoFi employs full-rank covariance matrix in the last layer, which is better than low-rank approximation of the covariance matrix associated with the last layer (LoLoFi), or low-rank covariance to model all dependencies across layers (LRKF). For further results showing regret and comparison using E-greedy, see Appendix G.1.3.
0.8
HiLoFFpBaeyes
oR-peayes
average reward
0.6
JAKF-p8ayes
Lofi-pBayes
0.4
Lafi-TS
LLL-pBayes
LLL-TS
0.2
5000
15000
20000
25000
30000
35000
40000
num. observations
Figure 2: Cumulative average reward for the bandit MNIST problem.
Next, Table 5.2 reports the average cumulative reward and total runtime (over 10 trials) for each method, comparing posterior predictive sampling (pBayes) with Thompson sampling (TS). Overall,
Agent
(pBayes)
(pBayes)
RilaFi
31,167.7
LoLaFs
LRXP
78.354.9
2.51
LoF1
23,184.5
23.304.3
4.76
38
13,922.3
191.55
Table 2: Performance comparison of Bayesian decision-making strategies: posterior predictive sampling (pBayes) vs. Thompson sampling (TS). Rewards are cumulative and averaged over 10 runs; time is in minutes.
pBayes is consistently faster across all methods. For the two agents where both approaches are applicable (LoFi and LLL), the average cumulative reward nearly identical for LoFi, while pBayes clearly outperforms TS for LLL. However, TS incurs a much higher runtime due to the need to sample repeatedly from the high-dimensional posterior over model parameters, whereas pBayes only requires sampling in the comparatively www-dimensionl outcome space (one dimension per

---

arm/class). Finally, as expected, HiLoFi achieves the best performance, followed by LoLoFi and then LRKF. This performance hierarchy comes cost in runtime: HiLoFi is slower than LoLoFi, which in turn is slower than LRKF.
5.3 Recommender systems
Problem description. We study the performance of the methods the Kuairec dataset of [22], which is derived from a real-world, non-stationary, video recommender system. This dataset used study non-stationary contextual bandits in [65].
Dataset. We group rows the dataset (for a given user) in blocks the 10 next videos that the user saw. For the features, consider the log(1 x) transform of like count, share count, play count, comment count, complete play count, follow count, reply comment count, and download count. For the target variable, we use the log(1 x) transform of the watch ratio [0, oc).
Model.
The reward model is a neural network with an embedding layer (one per video/arm), and dense layer for all features. We join the embedding layer and the dense layer, and we then consider three-hidden-layer neural network (50 units per layer, ELU activations), and linear output unit.
Algorithm. We perform sequential Bayesian inference using the relevant method, and then use TS choose the action at each step (see Section 3.1). The choice hyperparameters is in G.3.
Results. Figure shows the average daily reward (left panel) and the rumning time of each method (right panel). We observe that HiLoFi has the highest average daily reward with second lowest running time. On average, LRKF and LoFi have similar performance, however, LoFi has higher running time. Next, VBLL has higher average daily reward than OnVBLL, but it is slower. For in-depth analysis the results see Appendix G.3.
running time (min.
101
daily
00
0.8
HLoR
LRKF
loF
OONBLL
VBLL
Hllon
IRKE
loF
DIBBLL
VBLL
Figure 3:
Recommender system results. Left: average daily reward. Right: running time.
5.4 Bayesian optimization
Problem description. Following [5]. evaluate the competing methods classical Bayesian optimization (BO) tasks, where the goal to maximize an unknown function g [0, 1 - with surrogate model trained sequentially on past observations.
Model. We employ a three-layer MLP (180 units per layer, ELU activations) as the surrogate for all neural-based methods. For the GP baseline, we use Matérn-5/2 kernel with lengthscale 0. and 20-point buffer reduce computational cost. While performs better when hyperparameters are tuned during training [28], this incurs much higher computational costs, so we do not pursue it here. The choice of hyperparameters is detailed in Appendix G.4.
Datasets. We consider seven benchmark functions commonly used in BO [5]: Ackley (2D, 5D, 10D, 50D). Branin (2D). Hartmann (6D), and DrawNN (50D and 200D). These span range of dimensionalities and multi-modaliiies, and are standard in evaluating global optimal performance. For all methods, except for DrawNN, we sample a function from the posterior predictive and evaluate on a fixed set of candidate points generated using Sobol sequence [54] to find its maximum. Instead, for Drawnn functions, we use projected gradient descent, implemented with the Jaxopt library [4], to optimize the sampled function directly over the continuous domain [0, 1].

---

Algorithm. We perform sequential Bayesian inference using the relevant method, and then choose the next query point at each step using TS (see Section 3.1). Figure 12 in the Appendix shows the results using the expected improvement algorithm [29].
Results. Figure 4 (left) shows the final best value on the vertical axis (higher is better), and the amount of run time on the horizontal axis (lower is better). The number of steps for each dataset are the x-axis in Figure 11 Appendix G.4. Figure (right) shows the tradeoff between performance (measured by rank) and compute time. Our method is on the Pareto frontier for a range of tradeoffs between time and performance; furthermore, across tasks, the performance and compute time of HiLoFi dominates (better performance and less compute time) those from competing methods except from VBLL (higher performance) and LRKF (lower compute time). Thus, HiLoFi offers strong tradeoffs between compute time and performance. For further analyses and results see Appendix G.4.
HiloFi
GP
LoF
LRKF
VBLL
ONVBLL
LLL
Ackley2
Ackley5
Ackley10
Ackley50
time
-0.6
best
-1.0
-7.5
-.88
10a
10
10a
10
10
10
Branin
Hartmann
Nndraw50
Nndraw200
200
-2.5
2.0
-5.0
1.5
100
1000
2
-7.5
500
10a 2 10
time
time
time
Figure 4: Left panel: Performance across all BO benchmark functions. For time, lower is better. For performance, higher is better. The dashed lines correspond to the results for our method, so methods that are above and to the left are better. Right panel: Time versus performance tradeoff plots.
6 Related work
briefly review deterministic approaches for approximate online parameter inference. Several methods maintain diagonal plus low-rank (DLR) structures for efficient covariance updates, including L-RVGA [36], SLANG [47], and LoFi [8]. Low-rank Kalman filtering has also been explored in state-space models [53], though with stronger restrictions the rank relative to measurement dimension. Beyond low-rank, FOO-VB [64] exploits Kronecker-structuree approximations, while offline methods explore similar ideas for scaling BNNs [41, 56, 34]. Another direction builds the lottery ticket hypothesis [42, 38], restricting learning to sparse or wiw-dimensional subspaces. Examples include the subspace neural bandit [15] and PULSE [7], which pre-train projection matrices offline before online adaptation.
7 Conclusion and future work
We introduced predictive-firs firstt approach for efficient online training of neural networks, based on linearization and structured low-rank approximations of error covariances. Our three variants achieve strong performance-runtine trade-offs, with HiLoFi particularly effective in high-dimensional, non- stationary settings. Limitations include the lack of fixed-lag smoothing, sensitivity to linearization and outliers [14, 37), and reliance hyperparameters. Future work includes extending our approach to fully-online reinforcement learning [18].
We view contributions primarily methodological, with no particular ethical concerns.
Acknowledgements
We thank the TPU Research Cloud program for providing the compute resources used our experiments, and James Harrison for helpful comments.
10

---

References
[1] Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Luca Pesce, and Ludovic Stephan. Repetita iuvant: Data repetition allows sgd learn high-dimennional multi-index functions. arXiv preprint arXiv:2405, 15459, 2024.
[2] Gianluca Bencomo, Jake Snell, and Thomas L Griffiths. Implicit maximum a posteriori filtering via adaptive optimization. In The Twelfth International Conference on Learning Representations, 2024.
[3] Oded Berger- Tal. Jonathan Nathan, Ehud Meron, and David Saltz. The exploration-explotaee dilemma; a multidisciplinary framework. PloS one, 9(4):95563,, 2014.
[4] Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares- López, Fabian Pedregosa, and Jean-Phie chillpiiipppe Vert. Efficient and modular implicit differentiation. arXiv preprint arXiv: 105. 1513,, 2021.
[5] Paul Brunzema, Mikkel Jordahn, John Willes, Sebastian Trimpe, Jasper Snoek, and James Harrison. Bayesian optimization via continual variational last layer training. arXiv preprint arXiv:2412.09477, 2024.
[6] Álvaro Cartea, Fayçal Drissi, and Pierre Osselin. Bandits for algorithmic trading with signals. Available at SSRN 4484004, 2023.
[7] Álvaro Cartea, Gerardo Duran-Martin, and Leandro Sinchez-Betancond Detecting toxic flow. arXiv preprint arXiv:23/2.05887, 2023.
[8] Peter G. Chang, Gerardo Durán-Martín, Alex Shestopaloff, Matt Jones, and Kevin Patrick Murphy. Low-rank extended Kalman filtering for online learning of neural networks from streaming data. In Sarath Chandar, Razvan Pascanu, Hanie Sedghi, and Doina Precup, editors, Proceedings of The 2nd Conference on Lifelong Learning Agents, volume 232 of Proceedings of Machine Learning Research, pages 1025-1071. PMLR, 22-25 Aug 2023.
[9] Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka 7deborová, and Florent Krzakala. The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents. arXiv preprint arXlw:2402.03220, 2024.
[10] Achiya Dax. Low-rank positive approximants of symmetric matrices. Advances in Linear Algebra & Matrix Theory, 4(3):172-185, 2014.
[11] Erik Daxberger, Agustinus Kristiadi, Alexander Immer, Runa Eschenhagen, Matthias Bauer, and Philipp Hennig. Laplace redux-effortlesss Bayesian deep learning. Advances in neural information processing systems, 34:20089-20103 2021.
[12] DeepMind, Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Antoine Dedicu, Claudio Fantacci, Jonathan Godwin, Chris Jones, Ross Hemsley, Tom Hennigan, Matteo Hessel, Shaobo Hou, Steven Kapturowski, Thomas Keck, Iurii Kemaev, Michael King, Markus Kunesch, Lena Martens, Hamza Merzic, Vladimir Mikulik, Tamara Norman, George Papamakarios, John Quan, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Laurent Sartran, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Miloš Stanojević, Wojeiech Stokowiec, Luyu Wang, Guangyao Zhou, and Fabio Viola. The DeepMind JAX Ecosystem, 2020. URL: http://github. com/ google crrogle-deepe deepmind.
[13] Gerardo Duran-Martin. Adaptive, robust and scalable bayesian filtering for online learning. arXiv preprini arXiv:2505.00726 2025.
[14] Gerardo Duran-Martin, Matias Altamirano, Alex Shestopaloff, Leandro Beeanhout, Jeremias Knoblauch, Matt Jones, Lrancois-Xavies Briol, and Kevin Patrick Murphy. Outlier- robust Kalman filtering through generalised Bayes. In International Conference on Machine Learning, pages 22138-12171. PMLR, 2024.

---

[15] Gerardo Duran-Martin, Aleyna Kara, and Kevin Murphy. Efficient online Bayesian inference for neural bandits. In International conference on artificial intelligence and statistics, pages 6002-6021. PMLR, 2022.
[16] Gerardo Duran-Martin, Leandro Sánchez-Betancourt, Alexander Y Shestopaloff, and Kevin Murphy, A unifying framework for generalised bayesian online learning in non-stationary environments. Trunsactions on Machine Learning Research, 2025.
[17] Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 133):211-218, 1936.
[18] Mohamed Elsayed, Gautham Vasan, and A Rupam Mahmood. Streaming deep reinforcement learning finally works. arXiv preprint arXiv:2410. 2024.
[19] Randall L Eubank. A Kalman filter primer. Chapman and Hall/CRC, 2005.
[20] Edwin Fong, Chris Holmes, and Stephen G Walker. Martingale posterior distributions. Journal of the Royal Statistical Society Series B: Statistical Methodology, 85(5):1357-139) 2023.
[21] Andrew YK Foong, Yingzhen Li, José Miguel Hermández-Lobat, and Richard E Turner. 'in-between' uncertainty in Bayesian neural networks. arXiv preprint arXiv: /906. /537, 2019.
[22] Chongming Gao, Shijun Li, Wenqiang Lei, Jiawei Chen, Biao Li, Peng Jiang, Xiangnan He, Jiaxin Mao, and Tat-Seng Chua. Kuairec: A fully-observed dataset and insights for evaluating recommender systems. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, CIKM '22, page 540-550, 2022.
[23] Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
[24] Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimization. International Conference on Machine Learning. pages 1842-1855 PMLR, 2018.
[25] James Harrison, John Willes, and Jasper Snoek. Variational bayesian last layers. arXiv preprint arXiv:2404.11599 2024.
[26] Chris Holmes and Stephen G Walker. Statistical inference with exchangeability and martin- gales. Philosophical Transactions of the Royal Society A. 38112227) 2023.
[27] Jeffrey Humpherys, Preston Redd, and Jeremy West. A fresh look at the Kalman filter. SIAM review, 54(4):801-88) 823, 2012.
[28] Carl Hvarfner, Erik Orm Hellsten, and Luigi Nardi. Vanilla Bayesian optimization performs great in high dimensions. arXiv preprint arXiv:2402.02229, 2024.
[29] Donald R Jones, Matthias Schonlau, and William Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13:455-492, 1998.
[30] Matt Jones, Peter Chang, and Kevin P Murphy. Bayesian online natural gradient (bong). Advances in Neural Information Processing Systems, 37:131104-13111 2024.
[31] Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024. URL:
cttps://kelleerjrddan .i gitggtthhhuu thub. i
[32] Mohammad Emtiyaz Khan and Håvard Rue. The Bayesian learning rule. Journal of Machine Learning Research, 24(281):1 2023.
[33] Jeremias Knoblauch, Jack Jewson, and Theodoros Damoulas. An optimization- centrrc view on bayes' rule: Reviewing and generalizing variational inference. Journal of Machine Learning Research, 23(132): 2022.
[34] Agustinus Kristiadi, Runa Eschenhagen, and Philipp Hennig. Posterior refinement improves sample efficiency bayesian neural networks. Advances Neural Information Processing Systems, 35:30333-30346, 2022.
12

---

[35] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
[36] Mare Lambert, Silvère Bonnabel, and Francis Bach. The limited-memory recursive variational Gaussian approximation (1-rvga). Staristics and Computing. 33(3):70, 2023.
[37] William Laplante. Matias Altamirano, Andrew Duncan, Jeremias Knoblauch, and François- Xavier Briol. Robust and conjugate spatio-temporal gaussian processes. arXiv preprint arXiv:2502.02450, 2025.
[38] Brett W. Larsen, Stanislav Fort, Nic Becker, and Surya Ganguli. How many degrees of freedom do we need to train deep networks: a loss landscape perspective. arXiv preprint arXiv:2107.05802 2022.
[39] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE,
1998.
[40] Jason D Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low- dimensional polynomials with sgd near the information-theoreiic limit. Advances in Neural Information Processing Systems, 37:58716-555 1655656, 2024.
[41] Jongscok Lee, Matthias Humt, Jianxiang Feng, and Rudolph Tricbel. Estimating model uncertainty of neural networks in sparse information form. In International Conference Machine Learning, pages 5702-5713, PMLR, 2020.
[42] Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. arXiv preprint (rXiv:1804008836 2018.
[43] Zhuoran Liu, Leqi Zou, Xuan Zou, Caihua Wang, Biao Zhang, Da Tang, Bolin Zhu, Yijie Zhu, Peng Wu, Ke Wang, et al. Monolith: real time recommendation system with collisionless embedding table, arXiv preprint arXiv:2209.0766 2022.
[44] llya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 171.5:/111.05100 2019.
[45] Thomas M McDonald, Lucas Maystre, Mounia Lalmas, Daniel Russo, and Kamil Ciosek. Impatient bandits: Optimizing recommendations for the long-term without delay. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1687- 1697, 2023.
[46] Raman Mehra. Approaches to adaptive filtering. IEEE Transactions on automatic control, 17(5):693 698, 2003.
[47] Aaron Mishkin, Frederik Kunstner, Didrik Nielsen, Mark Schmidt, and Mohammad Emtiyaz Khan. Slang:
Fast structured covariance approximations for Bayesian deep learning with natural gradient. Advances in neural information processing systems, 31, 2018
[48] Yann Ollivier. Online natural gradient Kalman filter. Electronic Journal of Statistics, 12(2):2930- - 2961, 2018.
[49] Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides. Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvari. Satinder Singh, et al. Behaviour suite for reinforcement learning. arviv preprint arXiv: 0908.0368, 2019.
[50] My Phan, Yasin Yadkor,, and Justin Domke, Thompson sampling with approximate inference. In NIPS, August 2019. URL: /tsttss//papeeee nips cttccccppaco pttppp/pppp/////eepappppppaa Paper.
[51] Carlos Riquelme, George Tucker, and Jasper Snock. Deep Bayesian bandits showdown: An empirical comparison of Bayesian deep networks for Thompson sampling. arXiv preprint 1rXiv:1802.09122 09227, 2018
[52] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. tutorial on Thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
13

---

[53] Jonathan Schmidt, Philipp Hennig, Jörg Nick, and Filip Tronarp. The rank-reduced Kalman filter: Approximate dynamical-low-ree filtering in high dimensions. Advances in Neural Information Processing Systems, 36:61364-61376, 2023.
[54] Madeline E. Scyphers, Justine E.C. Missik, Haley Kujawa, Joel A. Paulson, and Gil Bohrer. Bayesian optimization for anything (BOA): An open-source framework for accessible, user- friendly bayesian optimization. 182:106191.
[55] Weiwei Shen, Jun Wang, Yu-Gang Jiang, and Hongyuan Zha. Portfolio choices with orthogonal bandit learning. In IJCAI, volume 15, pages 974-980, 2015.
[56] Marcin Tomczak, Siddharth Swaroop. and Richard Turner. Efficient low rank gaussian varia- tional inference for neural networks. In H. Larochelle, M. Ranzato, Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4610- 4622. Curran Associates, Inc., 2020. URL: https::/ neurips ctcaps.cc/pp// cc/paper_ salles/aper//0010 /tt http:///e/...e..aaaaaaaa44444450 aaa Paper Paper.pdf.
[57] Kevin Tracy. A square-root Kalman filter using only qr decompositions. arXiv preprint arXiv:2208. 06452, 2022.
[58] Joost Van Amersfoort, Lewis Smith, Andrew Jesson, Oscar Key, and Yarin Gal. On fea- ture collapse and deep kernel learning for single forward pass uncertainty. arXiv preprint arXiv:2102. 1409/ 2021.
[59] Harrison Waldon, Fayçal Drissi, Yannick Limmer, Uljad Berdica, Jakob Nicolaus Foerster, and Álvaro Cartea. Dare: The deep adaptive regulator for control of uncertain continuous-ting ttie systems. In ICML 2024 Workshop: Foundations of Reinforcement Learning and Control- Connections and Perspectives, 2024.
[60] Florian Wenzel, Kevin Roth, Bastiaan Veeling, Jakub Swiatkowski, Linh Tran, Stephan Mandt, Jasper Snoek, Tim Salimans, Rodolphe Jenatton, and Sebastian Nowozin. How good is the bayes posterior in deep neural networks really? In International Conference on Machine Learning, pages 10248-10259. PMLR, 2020.
[61] Jing Xu, Jiaye Teng, Yang Yuan, and Andrew Yao. Towards data-algorithm dependent general- ization: case study overparameterized linear regression. Advances in Neural Information Processing Systems, 36:79698-79733 2023.
[62] Zhitong Xu, Haitao Wang, Jeff M Phillips, and Shandian Zhe. Standard Gaussian process all you need for high-dimensional Bayesian optimization. In The Thirteenth International Conference on Learning Representations, 2024.
[63] Renato Zanetti and Kyle J DeMars. Joseph formulation of unscented and quadrature filters with application consider states. Journal of Guidance, Control, and Dynamics, 3606):1860-1864, 2013.
[64] Chen Zeno, Itay Golan, Elad Hoffer, and Daniel Soudry. Task-agnostic continual learning using online variational bayes with fixed-point updates. Neurul Computation, 33(1 33(11):31393317 2021.
[65] Zheqing Zhu, Yueyang Liu, Xu Kuang, and Benjamin Van Roy. Non-stationary contextual bandit learning via neural predictive ensemble sampling. arXiv preprint arX17:2310.07786, 2023.
14

---

Appendix
Notation
16
B Extended Kalman filtering for online learning
17
Linear algebra results
18
C.I Sum of Cholesky matrices
18
C.2 Singular value decomposition given sum of low-rank-matrices
19
HiLoFi-furte further details
D.1 Derivation of HiLoFi
21
D.2 Computational complexity
22
Proofs
22
E,1
Proof of Proposition D.1
22
E,2 Proof of Proposition D.2
23
E.3 Proof of Proposition D.3
24
E,4 Proof of Proposition 4.1
26
Further algorithms
26
El
LoLoFi
26
F22 Low-rank Kalman filter (LRKF)
26
F3
Replay-bufee variational Bayesian last layer (OnVBLL)
31
G Additional experiments
32
G.I Online classification and sequential decision making the MNIST dataset
32
G.2 Online classification using LRKF the CIFAR-10 dataset
35
G.3 Bandits as recommendation systems
36
G.4 Bayesian optimization
37
G.5 In-between uncertainty
38
15

---

A
Notation
Symbol
Deseription
E norm.
Frobenius norm.
Du Dæ EN
Dimension of observations / inputs. Number of parameters for the hidden layer/ last layer. Total number of neural network parameters.
Da, De E N
Do = Dn + De
N(x S)
Multivariate Gaussian density evaluated æ with mean m and covariance matrix S.
Penv (y|x)
Unknown data- genteratnggting process for conditioned on Posterior predictive model for y, conditioned on æ, and param- eterized by b.
Py m)
Mmx.. (R.)
Space of m-by-r real-valued matrices. Space of mn-dimensional positive definite (pd) matrices.
Ma (IR)
M
Space of m-ddimensional positive semidefinite (psd) matrices. D-dimensional identity matrix.
LD
S1/2
trian-triangular Cholesky decomposition of the pd matrix S.
2. (ct,
Inputs with context C₁ E Pe (possibly empty) and action ae A RD=
ye R
Scalar measurements, rewards, or observations obtained timestep t.
Ye E Ru
Measurements, rewards, or observations obtained timestep Datapoint at time t.
Dj = (Fe: yt)
Mi:t U11 ..... 1k
Time-ordered collection of vectors 14 E R
DE. (D....., D.)
Dataset at time
LE DL
Last layer parameters.
h E Ph.
Hidden layer parameters.
(L, h) E Do
Collection all neural network parameters.
[(0,z) [(e, h x) E Bv
Neural network output with parameters 0 and inputs æt.
e, E CR
Zero-mean noise with covariance R, M (R). Zero-mes dynamics noise with variance Q M (R).
W. E 2o
ge.1 2 0
Last-layer dynamics.
(h,1 2 0
Hidden-lat layer dynamics.
u E R Pe
Zero-mean mean dynamics noise last layer parameters with vari- ance q Inz-
ULd Rh
Zero- mean dynamics noise of hidden- parameters with variance Qb, ID,.
Lyp E R Dt
Frequentist estimate for l given Di:e. Frequentist estimate for h, given Dr... Frequentist estimate for θ given Di. Error variance-covan covariance matrix.
heje E R Pr
O:1 (lete, heje) E Do
E. = Var(e: Oq1e)
gesoritmm-dependent surrogate covariance matrix to E,,
Σ. = arg minl
Eyje Σ
Best rank-d approximation the surrogate covariance matrix Σ.
C. E (R)
Rectangular matrix (d x D) matrix such that CJ C, Σ,
L. (el test R141)
Jacobian of neural network w.r. parameters in last layer. Jacobian neural network w.r.t. parameter hidden layers.
H(11 = Vnf(lej hnes x++1)
CR(B....., B²)
Cholesky factorization of Σx= B. Bи. where each By is an upper-triangulh Cholesky factor (see Appendix C.I).
Pa(AI..... Ax) E MaxD(()
Best rank-d approximation of Σx= AJ, At, with A E Má, (R), da S D.
E (R)
Best rank-d approximation of EK_ A Aa + a Ip, with > 0 (see Appendix C.2).
16

---

B Extended Kalman filtering for online learning
Here, we explain in more detail the background of the EKF for online learning presented in Section 3.2. To make this section self-contained, we repeat parts of the material introduced in that section. Let us assume that y₁ e. (( h4) + Ct, where et is zero-mean random variable with observation covariance R2 MD (R). Given starting vector dg. we assume that model parameters 0, (L,, he) E RD and observations E RD> evolve according to the state-space model
0. = 0 + ut.
(11)
y: f(O,, x()) et:
where We E DD is a zero-mean random vector with known dynamics covariance Q₂ E EM (R), and e E Dw is zero-mean random vector with known observation covariance R, M,D, (T).. As before, we assume Cov(Og, ex) = for all E N and Cov(ue, ex) = for L, N. We now consider a first-order approximation of f around 0 1/-1 that is,
yt = f(0--11-1: xz) J, (0, - 0 11-1 + ex
(12)
where 01-1|t-1 = 14-11-11 11 11-1)-113 is given, and J. [L. H.) with L. Vel(Ei-1((-1 h 2x) and H. = Vnl(Ce- h a2t)
Following frequentist approach to the Kalman filter [27] and given the starting latent random vector Oojo == do. we seek to obtain sequential updates for the best (L²) linear estimate of the expected
value 0; given data ylat- We formalize this in the following proposition.
Proposition B.1. Let k. t N and let yo. Or follow the SSM (12). The solution to the optimization problem
arg max AEMeDe P (3)
E [1 A 11
(13)
the matrix Aipp given by
Aijk = Cov(Or, y1a) Var(y
(14)
The best linear unbiased predictor (BLUP) for model parameters O,, given observations Yi.k is
0..k- Aiik Yi:k.
(15)
and the error variance covariance (EVC) matrix is defined as
Enjk = Var(O.) Aqi, Var(y1:) All
(16)
Proposition B.2. Under the SSM (12), the BLUP and the EVC can be written in the form of Kalman filtering predict and update equations. Here, the predict equations are
0-t111 02-1/1-15
(17)
Egj-1 E.-1/-1 +i,
and the update equations are
Offt = Oct-11 + Ec.
(18)
Egje (I - -i) Epi-i (I-, J.). K, R,K.K
with
6, Y1 -1(00-111-1, 1.),
K, Σ1p-1 J. S-1
(19)
S: J, J7 + R.-
Proof. The proof follows from the linear form of (12), Lemmas 2.1 to 2.3, and Theorem 4.2 in [19].
17

---

Remark B.3. The update equations in (18) are recursive and characterize estimate of the unknown latent state and the estimated eтror estimation through the first two moments. Furthermore, the update for the covariance in (18) is in Joseph form [63] and is known to be numerically stable. In our method, we leverage these two facts to target low-rank EVC through a second-step optimization that has cannericallystabbee updates.
Corollary B.4 (Kalman filter as a Bayesian posterior), Assume a Gaussian density for the initial parameters pl (p) (0s Oojo: Σojo) and for the noise term p(ex) = (ex 0, Re). The BLUP tee and the EVC Σeje are the parameters of the Gaussian that characterize the posterior of model parameters 0, given V1:t. more precisely,
p(O, (1a) = (o 0, (r)e)
(20)
As a consequence, the posterior predictive for the next observation in the sequence is
plye (uely1=-1)= / N vv [((0 1 m4) J.( 0. Osje-1); Rτ) p(0, D1=-1)dd.
(21)
-Ny ((00))1100-)),, J. Eq--15 + R.).
C Linear algebra results
C.1 Sum of Cholesky matrices
Here, we generalize the result found in [57] to any set of K >> 2 matrices, which we use to derive the method LRKF, HiLoFi, and LoLoFi.
Proposition C.1 (QR of sum of Cholesky matrices), Let A. i E 21, 1} be collection of (D x D) positive definite matrices and let A.2² the upper-triangular Cholesky decomposition of A, Let M be the stacked (DI x D) matrix given by
1/2
A /
=
(22)
A 1/2
It follows that
R Σ A
(23)
where R is component the QR decomposition of M.
Proof. We see that
MT M A
(24)
Consider the QR decomposition of M
M = QR,
(25)
with Q an orthogonal matrix and R and upper-triangular matrix.
Then,
RA RTRRR-QQQ----E
(26)
As consequence, note that the square root of the matrix A + + A is the upper-triangular matrix in the QR decomposition of M.
Remark In what follows, denote the result of obtaining the R matrix of the QR decomposition of the row-stacked matrices A, 1/2 for E [I, by
@R(A 1/2
A 1/2
(27)
18

---

C.2 Singular value decomposition given sum of wow-rank--matries
Proposition C.2 (SVD of sum of low-rank matrices). Let A, for ,I, be MD (R) positive semi-definite matrices such that A W? Wa where W, RaxD and d < D. The best rank-d approximation of the sum is
EA,JJ.J
(28)
t=N
where J = V E RRdxD, Sia are the top d singular values and V contains the right singular vectors of the stacked N x D) matrix given by
W
W₂
N
(29)
W
Proof. Let A, for {1, NN be M (R) matrices with A, W/W, W, E R and < D. Form the matrix N given by
W1
W₂
N
USVT
(30)
W N_
where US is its full singular value decomposition, with U E RaNxdN S E RdNND and V E DxD Then
N
AA==
Σ W,W,=
f=1 1=1
(USSV))(USVV) US
(31)
=
Hence E, A; has eigenvectors V and eigenvalues given by the diagonal entries of S By the symmetric-matrrix form of the Eckart-Young theorem [17, 10], its best rank-d approximation in Frobenius norm is
diag(of..... o2. 0, .......) VT.
(32)
Writing S., diag(oi..... Oa) E RaxD one checks
V diaggoo?
0 0, VT (S.a VT) (S.a VT) = JT
(33)
where
J = S.a VT RaDD
(34)
S. diag (o (o.....,0a G.)
and {ox} are the singular vectors Σm An
Takeaway. Proposition C.2 shows that form the best rank-d approximation of Σ A, does not need to assemble or carry out the SVD the full D D sum. Instead, one stacks the low-rank factors into
Wi
N
E (
(35)
W
and compute a reduced SVD (or symmetric eigendecomposition)) of the small (dN) x (dN) Gram matrix NNT This costs
O((dN)3D (dN)* ~ O(LN2D) when dN < D.
(36)
19

---

versus the (DD)) required for a full SVD on the D x D sum. Moreover, memory and computation scale with d and dN rather than with the large dimension because all operations involve only the (dN) x D matrix N and the d D factor J.
In what follows, we denote the result of obtaining the best rank-d approximation matrix of the SVD) decomposition the stw-kt matrices w for E {1,..., by
Pa(W WN).
(37)
Corollary C.3. If the sum of matrices of the form
N
Σ A aID
(38)
with >> O, then the best rank-d approximation is of the form
N
A + a ~ J +q
J +q
(39)
where
J4 = Sid.to VT RdxD
S == diag (Vor + +g. q....., v22+
(40)
and {ar are the top-d singular values of En= An.
Proof. From (31) in Proposition C.2 obtain
Σ
V +al)) VT = Vs. VT,
(41)
1=1
where
S diag(o} a...., ob a).
(42)
Let
S+a diag (Vof aa a..... vob +a
(43)
then
Σ
A, VS VT
(44)
(VS
=J -J
Takeaway. If the sum of matrices can be written as the sum multiplied low-rank factors plus an additional identity matrix times constant, then, computation of the best rank d-matrix in low-rank factor can be obtained by performing SVD over the low-rank factors and modifying the singular values include the term
In what follows, we denote the result obtaining the best rank-d approximation matrix of SVD decomposition of the row-stacked matrices w-!/² for i E {1...., .N) plus an identity times real-valued number a > 0 as
Pa,ta ( Wx).
(45)
20

---

D HiLoFi- further details
D.1 Derivation of HiLoFi
Consider the linearized model
Y/ (f1-1|r-1, 1/-1 2n) + Le (--1/t-1) + Hh h1-1((-1) et,
(46)
where 4-11|-- l|e-1 and 1/1-1 are given.
We start the algorithm by initialising the beliefs about the last layer parameters l and the hidden layer parameters h. We set
Eleol - Eojo=
[b = hojos Var(Lo) Ee,o. Var(ho) = CC Co.
(47)
for known Co E MMax x D. (R), hojo E RR,,, Σe, E MDt(R) and Loo E De, Next, we assume that for 2 1, the latent last layer parameters f and the hidden layer parameters h1:t follow the dynamics
e, = ---1-- Ugge h = h + Untt.
(48)
where ug,1a and u4,1: are zero-mean independent noise variables' with dynamics covariance matrices Var ue,r) = Qe E M (R) and Var(un.) Qh E .M Dr (R). For simplicity and to exploit efficient linear algebra techniques for belief updates, we assume Qe qe,:LD and Qh, = ID, A simple choice is to set Qs = oI to avoid forgetting past data; see e.g., [16].
Proposition D.1 (Predict step). With the SSM assumption (48), the approximate covariance Var(ez-1 1(-1(t-1) Σe,1-1 and the approximate covariance Var(h h(-1((-))
C Ct-1, the predict step becomes
hajr-1 1/1-11
fa/e-1 l, 11-1/1-15
(49)
Eedlt-1 = Σp,111 + ge In
En = CT_, C--1 + -hat In.
The proof of Proposition D.I is in Appendix E.I.
Proposition D.2 (Variance of the innovation). The upper Cholesky decomposition of innovation variance takes the form
s//² = (SeL LI v L,, C.-1 HJ, v HJ, RR!²)
(50)
where L, and H. are defined in Section 3.2.
The proof of Proposition D.2 is in Appendix E.2.
Next, update step for the BLUP resembles EKF update, while the EVC update approximates block-diagon diigonia covariance: the last layer block is full-rank, and the hidden layer blocks are low-rank. To maintain numerical stability and low-memory updates, track the Cholesky factor for the last layer and low-rank factor for the hidden layers. The Cholesky factor is taken from surrogate matrix that avoids computing full MDex (RR) matrix by neglecting the artificial dynamics covariance qe.c- The low-rank component for hidden layers is approximated via two-step process: (i) a fast surrogate predicted covariance, and (ii) a rank Dn, projection error. Like the Cholesky factor, the surrogate covariance in (i) reduces the computational cost of dynamics noise, which does not reflect the system's 's true dynamics. However, we retain some information from the dynamics noise to update all hidden layer parameters. Step (ii) enables a fast update rule, crucial for overparameterized neural networks [38]. We detail this step in the following proposition.
Proposition D.3 (Kalman gain, update BLUP, and update EVC). Define the gain matrices
K h1t Vr.CC + qr Vt.te
KT = Ee. + qe, e,s
(51)
where VA. = S 1/2 S. T/22 He, and Ve, = 1/2 T/ L. The updated BLUP for the last layer parameters and hidden layer parameters
haje = h4-1/t11 + KA, Es,
Bys = l--11-11 + Ke, E:.
(52)
lie. Cov(ue,, un.) = 0 for all i,j (1....,'..
21

---

The approximate posterior covariance Egje is the best blokk-diggodd approximation (in Frobenius norm) of the surrogate matrix Etit given by
(1D, (1D,- E -K,tt Re, R
Ke, UD K,,, Ce-1 (R) KK,, B.,k, ttn..
that has full rank for the last layer and rank for the hidden layer. This results in a Cholesky factor for the last-layer covariance given by
1112 = QR
R 1/2KK..)
(53)
and a low-rank factor for the hidden layers given by
C = =PPaatt (Cz-1 (I,,,, R2 R2/KKh..))
(54)
The proof is in Appendix E.3.
D.2 Computational complexity
We now compare the computational complexity of the algorithms employ. Recall that De, Drs and Dy are the number of parameters in the last layer, hidden layers, and the size of the output layer, respectively. As before, Dg De + Dr. The dimensions de, dh. with de < De and dn < Dr. the low-dimensional subspaces for the last and hidden layers, respectively, and d = de + dn.
The computational complexity of our algorithm when using full-rank in the last layer is O(De (De D2))² + Dr (da + )) For low-dimensional outputs, this is O + Dndn 2). For high- dimensional outputs, we may choose to use low-rank approximation for the last layer (which we call LoLoFi) this reduces the cost to O (de +2y)² ) Dr. (dh, )2))), which is linear in Dø The primary computational bottlenecks in our method are the calculations for the Kalman gain of the hidden and last layers, with costs ((2 D₁ 2yy) and O De Dy respectively. This efficiency arises because ///2 is upper triangular, allowing the system ST/² s./² V J for V to be solved in ( Dr. 22²)) as opposed to ODD, 3). Additionally, approximating the covariance matrix via truncated SVD incurs cost of O(,, (d, - D₂)² + (dn + 23) + dn (d,, + Dy) Dr.,, as detailed in Figure 8.6.1 in [23]. Finally, the corresponding cost for the last layer is O(De (De + 2)
Among related methods. the closest to in terms of computational costs variational Bayes approaches such as the Slang method [47]. the L-RVGA method [36], and the LoFi method [8]. In particular, LoFi uses the linearized Gaussian updates (similar the ones in this paper), but approximates the precision matrix using a diagonal-plus-Ion rank (DLR) form. The appeal for DLR precision matrices is twofold. First, they enable the application of the Woodbury identity, leading to predict step of cost O(De d + d3) and an update step of O (d + D2 = O(De (d + Dy) + Dr (d + Dyy Second, incorporating positive diagonal terms ensures the matrix is positive definite, so that valid posterior Gaussian density is defined.
Although HiLoFi and LoFi have the same asymptotic complexity, LoFi incurs additional practical overhead due to three key operations absent in HiLoFi: (1) the inversion of a (d Dy) rectangular matrix, (2) the inversion of a d rectangular matrix, and (3) the Cholesky decomposition of a d rectangular matrix. These operations increase the actual per-step computational time, which in our example, scales at about one second per additional rank. This behaviour shown in the empirical comparison across HiLoFi, LRKF, and LoFi in the online classification setting (Figure 6, Appendix G.I).
E Proofs
E.1
Proof of Proposition D.1
Proof. Following Proposition B.2, the predicted mean takes the form
1-11/=11
0zt-11 = 01-1111=
(55)
h 1
22

---

Next, the predicted posterior covariance takes the form
Eift-1 = Et-1/1 1/-11 + Qr.
(56)
where
2t-1t-1 1--1
Var(Or-1 - -1-11(t-1)
Var(L,-1 l (t-1
Cov(le-1 ly- 11-11t-1,, h1-1 11-11111
(ov(thu11 111-111-11 1- 1111--1)
Var 11-111-1).
Σt,1-1
Cov(Li-1 11-1je-1, h2-1 1/-1
Cov(h:-1 - -1 -1- 11-1
W Wi-1
(57)
Next,
Cov(le-1 - -1-1011,,
h
h2-1((1)
(1(()-1,11111))
t-1
t-1
Cov
to +
Σ
Ue, ho + Σ
Whit
(58)
rm1
1-1
Cov ho)
+
Cov(Lo, uh,r) +
Cov(ue,, ho) +
Σ
Coviue, Ub,
r=1r=l
0,
which follows from the assumptions about the SSM. Then
Σt11k11 diag( E C. C2-1).
(59)
and
E11-1 = E,-1|t11 + Q:
(60)
diag - + ae ID. C C.-1 + 9h ID.).
Given that Σg,-- is approximated at through Êe,11 and En 1 is approximated at t through CT Ct, we obtain
En1-1 R + Ip
+ ge
(61)
E1j-1hh 2 C_ C.-1 + 9h Ipe
E.2 Proof of Proposition D.2
Proof. By definition of and Proposition B.2, the innovation takes the form
E, = y: -f(( h1 x2.)
J.( 0: - +
(62)
L, (le l/-=1) + H, (h, h( ex-
23

---

Next, the variance of the innovation is
S: Var((e)
Var (Ir (Ee lajc-1) + H. (h: heje-1) + Et)
L. Var(ee - L + H, Var(h, - h + Var(e,
L, De,ele-1 L H. 2h.tee11 H. + R.
L, Σe, L + ge, L, L + H. Cj C.H. + th H, H? + R.
(63)
I 1/12 1/2
Vee L!
=
L [
1//2
V Ly HCL Vhh H, RT/2
C--1 HT
Vie. L
R R/12
-T S1/2
with
//2² On e.lte L, Ve. L C--1 HJ, Vhh, HT, R. R.!²).
(64)
E.3
Proof of Proposition D.3
Proof. First, by Proposition B.2, the Kalman gain matrix is given by
K, J] ST
(65)
Next, following Proposition D.I and Proposition D.2, we rewrite the Kalman gain as
L
K, diag( -e C C.-1)
S
H.
L, S,
= diag(22 Me,t C C.-1)
H.S
(66)
Eeale-1 Lg S.
C C--1 S-1
Ket Kkn
where
Ke, = [L, L, LL, Eeste-1)
(67)
K = L, W., WT
From the above and Proposition D.1 the updated covariance matrix takes the form
Σeje = (I K, K,),) E1i-11 (I K.J.) + K, K,R.K. KT
(68)
where
I K, J
I
0
Kedt
[L H.
0
IDa
Kr.c
ID
0
Ke, L,
Ke H, Knd H.
(69)
0
Ina
Kn,t Lt
ID,
Ke Lt
He
Kn,t Lt
Ip, Kn H.
24

---

the predicted error covariance Ejje-1 is
0
E1p-1= =
(70)
0
En,e1-11
and
Kett Khntt
K2 R
R² [
k
(71)
Ke,t Rr K.
Ke R2 KJ Kn R₁ R,,
KA. R₁ K
Thus,
E
(LD Ke, Le) (DD, L.) R,, R,, Khy R, K
Ke, M.. (Lo, Kh. H. En 100, Kn Hoy Kn, Ri KJ
(72)
Next, we consider the following surrogate covariance matrix which modifies the second block- diagonal entry
Eg
R (To, H. H.) R,K,, +om,
(73)
It then follows that
Σg 0
Σe,r Enat =
min
Ezfe -
Σn
Ee, Eninnk )
(74)
arg min
iEee -elle + [Ent En + Ke, R, K. KT
Eg, Sgrrak(k(
with
Σe, (ID, Ke, Le) - Ke, L.) + Ke, R; KT
(75)
Σn, (ID, Kh, C, CIDI(ID. - Kn H.) + KA. R. K, + 1h.ID..
Then, Σn Σg,t and En, e is given by the first d, principal components Σn,t-
Next, we find the update rule for the Cholesky and low-rank factors. First, the EVC for the last layer takes the form
Le, Ke Lt) Eecee11 (I Ke, Lt)
Ke,.RKK.
Kett Le) Eecele-1 (I Ke Le
+ Ke,t RT/²2 R!/² R2]/KK]
=
(76)
= (1 (1-KerLi) Ln)
Ket
T/2 E
Ke Kee RT/2|
1/2 (I (I-Ke,:
Edft-1
Ke Eir)
R. R./2KT
so that
Σg On
[2e--11-1 (I (e-Ke,tie L.)'
R R!! KJ R/2KKT
(77)
Then, the EVC covariance for the hidden layers (lower right block (oakk-diagoaa)) is
Σn, (1- Kn, H.) CL C.-1 K-KeeHi) Kn, RT//2 R
KT. + tr.t IDz
C--1 (I Kn, Kn.cH.))
(I Kn, Hi) C Kn RT/2|
(78)
+ ghheeID
R R///KK] KT
= -C Ö + qrot ID
25

---

Finally, by Corollary C.3, the best rank-d low-rank factor is
C2 = Pdn.-gn. (Ci-1 (I-Kes, Kh,t H.) "e E MM(dnDD)xDD (R).
(79)
So that
En, C. C..
(80)
E.4
Proof of Proposition 4.1
Proof. We seek to bound
|Eq Elple
(81)
Following the arguments from Proposition F.3, we obtain
E Egelle $ Σ Enje ll + Eqje Eeje ll+
(82)
Eaur
Eproo
where
Esurr 9h.t (2 ( + qe,t |1I- KetLi, Le) (I- Ke, Ke,L,, L.) |
(83)
and
Eproj = | C Cille + 2 2,,, R, K
(84)
Given that C, C2 is the best rank-d approximation of Σn,1, it follows from similar derivation to (107) that
D Σ
En,e C. C+IlF=
X
(85)
where { k= +1 are bottom (D,, - dr) eigenvalues Σ,.
Further algorithms
F.
LoLoFi
Algorithm 3 shows a single step of LoLoFi. The low-rank factor for last layers Ce,0 E M, and the low-rank factor for the hidden layers Ch, E MM Dr. (R) chosen at initialization.
F.2 Low-rank Kalman filter (LRKF)
Inspired by [57]. we derive a novel version of the low-rank Kalman filter which is (i) more com- putationally efficient, (ii) simple implement, and (iii) provably optimal (in terms of Frobenius norm). We call this the LRKF method. Instead of keeping track Σn or S,, we keep track of
low-rank factor for the covariance, and compute the Cholesky factor for the innovation variance s Algorithm 4 summarizes the predict and update steps for LRKF. Next we turn to the derivation.
We assume the model parameters 0 and the observations y follow
0, 0,-1 Ut:
(86)
y: H; O, + ex,
where Var(e,) = R, is known and H, is the known projection matrix. Both, e, and u, are zero- aero-mean random vectors.
In the Kalman filter update equations, the so-called posterior mean and covariances are given by
μ, M:-1 K, (y) 9.).
(87)
Σ, = Var - p,);
26

---

Algorithm 3 Single step of LoLoFi for online learning for / 2 1.
Require: R, // measurement variance
Require: (ge,: 9h,t) dynamics covariance for last layer and hidden layers
Require: (y:: 22. // observation and input
Require: bi-1 (e--11t-1 11--1 Ct.-11, Chac-1) // previous belief
// predict step
1: Yt
2: L. VeJ(e(-1102) 1 Ut)
3: H.- = (nf(f--l(-1 111-1-11, Ttt)
// innovation (nwrationnneesste-aheeeee error) and Cholesky innovation variance
4: 4 y1 Dr
5: S//2 + -n Ce, L, v TE, LT, Ch,t-1 HJ, Th H!, R R,
// gain for hidden layers
6: Vn, + S- S, 1/2
T H,
7: K, h,t +- Vn,
Vn, Ch.t-1 h + Th Vn,t
// gain for last layer
8: Ve, + S- //
9: K + Ve, E q2 Ve,
K Ve, Cea-1 C + get Ve,
mean update step
11: haj + 1 Kn,cEt
litt t 1--11t11 Ke,tt
// low-rank updates
13: Ce.e t Pdertre. (Ce--1 (1- (-KKetii) R. R2/2K),)))
14: Ch,t Paniton.r (h2,-1 (I -I-Knc Hi)) R (R,,))
15: Return b, (lets hales Ce Cha))
where Ao is given.
9. H. Hoj-111 = H:
K, (arree) = Bi--HHS,7
E, = y: H, 1
(88)
S, H, Exj-1 H R.
R. Var(e,).
The memory requirements of the posterior covariance is O(D?), with D number of parameters. This makes unfeasible to store for moderately-sizer neural networks.
Thus, to reduce the computational cost, we maintain the best rank d approximation of the covariance matrix by
Enj W/ W.
(89)
where W. E Rd the best rank-d approxiaaiin to E, (in Frobenius norm sense). Furthermore, maintain numerically stable method, we work with the Cholesky of the innovation variance. In effect, this is a variant square-root low-rank Kalman filter method. We explain the details of this method below.
The predict step equations are given by
PMj-1 = 14-11
(90)
Σ E = C C,-1 + I.
(91)
27

---

Proposition F.1 (Kalman gain and innovations). The variance S; of the innovation is
S: = H, E H + R.
= H, (Cl-1 C.-1 + I H.
+ R.
= H. CJ C. + q: H. H. + R,
C, H
(92)
- H. C Vo.H: R
R
S//
with S, given by
S. =R= Vq. HHHHI R,
(93)
where 2n returns the R matrix from the QR decomposition row-stacked arguments and R is the upper-trianguaar Cholesky decomposition of R4. The Kalman gain is given by
K, = E, t-1 H S,'
(S H; Eq(-1)
(94)
H. (C T 4 ID)))
Proposition F.2 (Update step). The updated mean is
14 Mije- + K -
9t).
(95)
The update covariance Eap approximated through a two-step procedure: first, a surrogate covariance that ignores the cross-term effect of K, H, on the artificial noise covariance qt, and second, best rank-d approximation (in Frobenious norm) to the surrogate matrix takes the low-rank form
E.g1 C Cc.
(96)
with
C, Pu (I (1- H.), R. k?/K E (R).
(97)
the low-rank (rectangular decomposition) matrix.
Proof. The updated covariance mean follows directly from (18).
The updated covariance is
E, = -I- K, H.) E (I -I- K, H,H + K, R.K
= (I K, H,) (CL) C,-1 + q ID.)
(I K, H K, R. T/2 R R 122K
(I LI-K,H H.) (CL, C. + q
(I K, H K, R.
1/2 R 1/2KT
= [I- H,) CL K, R,
C.- K, H.) R /T.
+ qt (I- K, HI) (I-K, H,
(98)
Next, we consider the surrogate EVC matrix
C (I K, H, R. /
Σ (1 K, H.) CL K, R..
+ IQIID
(99)
C. Č + qLI
where
C (I H,)
E Rid+o)xD
(100)
R 1/2K
Next, the best rank-d matrix is
28

---

Σ 2 /
E = arg min
Emank(E)
F
C C. + qi ID. --/
(101)
min Emaan(())dd
= C. C2,
where
C₁ = Pd,+ge (C.-1 (I H,, R KT
E MMxxDo (R)
(102)
the best d-dimensional low-rank matrix given the stacked matrices C2 and the dynamics covariance gt-
Proposition F.3. The per-step error induced by the approximation of the covariance at time L is bounded by
Dg
|| Die EE1lF S ae (2 Kr HollF K. H. H()
Σ k=d+1
(103)
where {Ax [ are the bottom (Da d) eigenvalues of Σ.
Proof. We seek bound
E2e EejllF,
(104)
where Enj given by (98) and E.je is given by (101). We first note that Enee Ene = Σ - ( + (Eeee E(1())
(105)
where Edjs is the surrogate covariance matrix (99). Then,
Erje Eqjelle S Enjt IIr++ + Egje Eeje l|F
(106)
-Eauer
Eproj
The norm for Eproj follows directly from the definition of the low-rank approximation. Let USV V be the SVD decomposition of Σgee and US.a V be the SVD decomposition of Egj- Here, = diag(A1..... AD.) and S = diaig(ii.......... Ad, .., 0) are the singular values (eigenvalues) of the matrices Egee and Enj respectively, ordered in descending order. Then,
E E |F
|US VT US VT
UU - S.a) Vr
Trii(UUS S.) (U S.)) VT)
VTTTU S. VTV S.)) UT]
TTi((S S.a) ViV (S Sw)) UTU
(107)
Tri(S S.
Do
x2
k=d+1
where Da are the bottom (Da d) eigenvalues of Σ,
Next, upper bound for the norm Esurr is as follows
Exurr ||F
EEee Eqel
liqe (I - K, H2) (I- K, H₂) I|IF
(108)
q: [I, H.) H,) (K, H,) (K, H|
S a: (II,K, H,) l| + K; H, 11).
29

---

Algorithm 4 Predict and update steps in the low-rank Kalman filter (LRKF)
Require: // measurement variance
Require: 9: // dynamics covariance
Require: (y:: mt)) // observation and input
Require: b (14-1, Ct-1) previous belief // predict step
1: Dr < h(),,zz)
2: H; Voh(((-11:3))
// innovation and (Cholesky) innovation variance
3: 6 6 Yt Yt
4: s//2 t On(C, V V.R.. H., R
// gain matrix
5: V, T,tS S/-1 S
S,
H
6: K +- V, C--1 C. C q: Vi // low-rank update
// mean and low-rank factor updatees
7: 14 t 14-1 + Kg
8: C. Pa Ct-1 (I-K, H, R!
9: Return b, (Hg C,) // updated belief
F.211 Error analysis for LRKF
Below, we analyze the single-step error incurred by LRKF without dynamics in the model parameters and scalar linear model, i.e., O, = 0,-1
0 and y/- OT æ. + e, with Varles] r
Proposition F.4. Consider the linear model
yt xt + Ct:
where e, zero-mean with Var[e:] 22, and let E,-1 Var(f 0--1jt-)). Let Σt-1 denote the rank-d covariance used by LRKF, and define
Tt
mink x. 1 x. 1
(> E = V: 0 1|t-11
Zz.
Then the one-step difference between the BLUP (full-rank update) and the rank-d LRKF update satisfies
(1 70
+ 01 (E 11eel13
10/ - 02jel2 S Icel od41 (
(109)
Here 0n (E 2 ... aD oD Ee-1) are the singular values of E,-1 Oepe is the BLUP, and Oue is the
rank-d LRKF estimate.
In this setting, the surrogate covariance introduced by LRKF is unnecessary, and Σ, = C,C, reduces the best rank-d approximation of the EVC matrix Σ,- Var(@ 1)-1)t1) As Proposition F.4 shows, single step of LRKF deviates from the dense (i.e., full-KF) update by factor governed entirely by the rank truncation. time I, the residual ét, the maximum eigenvalue σD (E,-)) 1), and the feature are all fixed. Consequently, the only way to tighten the bound and reduce the gap to the full update is to increase the chosen rank
Proof. We first note that
O/:: 01-1j1-1 + K,er,
(110)
0g1:
0,-1/1-1 K,
with
Σ,- 2t
K,
S, x/ Σ,_ Bt 72
S
(11I)
Σ, 1 00
K;
$, a.
E, 34 + 12.
S
30

---

Then
E1-1 Dt
Σ1-1 Et
K, K,
St
Se
(112)
(En-1
Σ1-1 1)
1 1
St
St
St
Thus,
(Et-1
Σ - 2t
1
1
|00: 0qjll2 ||(,, K.) Eell2 S Eer
Σ
at
S
S
Se
(II)
(113)
Bound for (I).
(E,11
E1-1)
E E,-1l1a ||01ll2 0d+1(2r-1
|eee|2
S.
[Sc]
7t
2
where we used Eckart Eckart-Young Young-Mirsky [17] and [S,] 2 == min E, 1,- 1r x. 1111 +
Bound for (II).
Since
1 S, Sel
x (Et-1 Ex-1)x
10 Σ1-1 Σ1-1
S 5,
[S, Sy1
S.
72
obtain
(1I) - E, 161- |,0/||2
102112 Σ Σ,-1 12
Σ
11
x 113
oa+
(E,-1)
78
Since |i,-1122 σ1 (E this becomes
(II) < 01 (1
| 11 Ja+1 (44+1(E11)
78
Plugging the bounds for (I) and (II) into (113) yields
1
(
||= 12
|/00ee Osjella S |ea| aat (E.-1) ||
-
Ft.
7
claimed.
F.3 Replay-buffer variational Bayesian last layer (OnVBLL)
The VBLL method has explicit posterior predictive
ply e, E. R) = N' (y et (h, x+), eT (h, x)) (x),xx) (
1 RR)
Building [25, 5]. observe that for any given q()) = Ni( e, E), lower-bound for the marginal log-likelihood of a single datapoint given by
log p(v It, h. R) 2
x e, h R.]
(h, xx) Tr (R- log.N (y: l (hh x.), R) / E
(114)
Following [33, 32, 30] a generalized posterior with function given by
(e, h, R, E) 9--1 (e, h, R. E) exp(-L, h, R. E)).
(115)
31

---

Estimation of the posterior mean (MAP filtering) involves estimating
L, hr R2, E, arg max (l, h, R, R) E.
(116)
which can be done implicitly through adaptive optimization methods as shown in [2]. Next, to improve the performance, we consider a replay-buffee buffer which has been shown to be much more efficient than doing fully-online SGD [1, 9, 40]. This assumption breaks with the fully-online assumption, but good contender in sequential decision making problems in stationary environments.
G Additional experiments
G.1 Online classification and sequential decision making on the MNIST dataset
The results in Section 5.2 consider the LeNet5 convolutional neural network (CNN) architecture [39]. In this architecture, the last layer is 80-dimensional and the output layer 10-dimensional, which corresponds to each of the 10 possible classes. Applying HiLoFi in this setting would need the storage and update of an 800 x 800 covariance matrix and 800-dimensional mean vector. Sequential update of the Cholesky representation of this covariance matrix, although feasible, takes most of the computational cost computational cost of the layer layer. Another reason to prefer LoLoFi over HiLoFi in this setting that the rank of the last layer is 800-dimensional, whereas the rank for the hidden layers is 50 dimensional. This corresponds to overparametrized linear regression, which has been shown to have some pathologies in the offline setting [61].
single step of HiLoFi. Given this, here we consider LoLoFi to offset the
As simpler baseline, which does not model uncertainty, we consider Muon (muon) [31], which special case of the Shampoo optimizer [24]. This is quasi second-order optimization method that scalable and shows strong empirical performance. We use the implementation in the Optax library [12]. Unlike the other methods, it only computes a point estimate, so we cannot use it for computing the posterior predictive. We use this method for the e-greedy bandit in Appendix 1.1.3 and as an additional choice of optimizer in Section G.I.I.
G.1.1 Online classification on the MNIST dataset
In this experiment, we consider the problem online learning and classification on the MNIST dataset using the LeNet5 CNN. We use the optimizers detailed in Section 5.2. We take the data Di. with T 60, 000 and D, (Iz, 3t). where x, is (28 28 x 1) array and y: {0, 1] one-hot- encoded vector such that (gt) = 1 if x, represents the digit i and 0 otherwise. At every timestep t l...., T each agent is presented the image x, which it has to classify. A predicted classification is made through the prediction yttt-1 = f(M x2) with p = E Dia-1] and then updates its beliefs given the (true) reward yt-
Having the BLUP over parameters Oqp-11 = E[O, Dia-i), the linearized model has mean and variance
m On, x)) softmax(((0),
m, = m(0 x.) + Vem x) ml-1); 5; diag(m((0)c-1::2) + m (f v.) (0) + EIy
(117)
This moment-matee matehed linearization corresponds, in the Bayesian setting, to Gaussian likelihood whose first and second moments match that of a Multinomial distribution. This representation was introduced in the context of online learning in [48].
In (117), diag(e) ) is function that takes as input the vector e E Thm and outputs diagonal matrix with entries diag(v)ss = n, 5(i j), and the term E >> O is a small constant that ensures non-zero variance.
Online learning results. Figure 5 shows the 5000-step rolling mean of the one-step-ahest classifi- cation outcome (one for correct, zero for incorrect) using the various learning algorithms. We observe that there is no clear difference between the methods. This shows that one can tackle this complete information problem without needing to model uncertainty. This is not the case in the incomplete information case that study in any of the experiments presented in Section 5.
32

---

HiLofi
LoLoFi
rolling accuracy
LRKF
Adamw
0.90
Muon
0.85
10000
20000
30000
40000
50000
60000
obs
Figure 5: Rolling one-step-ahead accuracy for the MNIST dataset.
Figure 6 shows the one-step-ahead accuracy of the last 000 images and the running time of processing all 60, 000 images for HiLoFi, LoLoFi, LRKF, and LoFi as a function of their rank. For LoLoFi, we fix the rank of the last layer be 50 and vary the rank of the hidden layers. We observe
0.985
100
running time
80
HiLoFi
accuracy
LRKF
60
LoFi
0.975
LoLofi
40
0.970
20
40
60
80
100
20
40
60
80
100
rank
rank
Figure 6: Results of MNIST for online classification. Left panel: accuracy function of rank.
Right panel: running time as a function of rank.
that for low-ranks up to dimension 20, LoFi faster than both LoLoFi and LRKF, However, the running time of LoFi increases much more rapidly (as function of rank) than either LoLoFi and LRKF, This consequence the computational costs associated with points (1,2,3) Appendix D.2. Next, we observe that the running time of LoLoFi is sightly above LRKF for varying rank; this is because of the double approximation one for the last layer. Finally, observe that HiLoFi is the method with highest computational cost this experiment. This is due the high-dimensionality of the last-layer, relative to the rest of methods.
the covariance matrix: one for the hidden layers and another
Lastly, we observe that all methods increase their performance as function of rank, albeit marginally, The method that most benefit from an increase in performance in HiLoFi. We hypothesize that this is due to the total rank of the hidden layer, relative to the rank of the last layer, which in this experiment is 800.
G.1.2 Error analysis for LRKF
The top panel of Figure 7 shows the rolling mean for the two sources of approximation error in the covariance matrix for the LRKF method (detailed in Proposition F.3), well as the rolling one- step-ahead accuracy. We observe that, on average, both sources of error decrease over time and accuacy of LRKF improves over time. Here, the only sources of error are the surrogate error and the low-rank error. This because LRKF does distinguish between last-layer and hidden-layer parameters.
33

---

0.015
0.0330
low-rank error
surrogate
0.010
0.0325
0.005
0.0320
0
20000
40000
60000
20000
40000
60000
0.98
LRKF
rolling(500)
accuracy
0.95
0.90
0.85
10000
20000
30000
40000
50000
60000
num. steps
Figure 7: Top: upper bound error for the surrogate error and the low-rank approximation. Bottom: 5, 000-step rolling one-step-ahead accuracy for the MNIST dataset.
G.1.3 MNIST multi-armed bandit
Here, present further results from Section 5.2 More precisely, we study the multi-armed bandit approach to solving the MNIST classification problem.
Choice of hyperparameters. The hyperparameters for this experiment For Adamw and muon (used in e-greedy and in conjunction with LLL), we use a learning rate of 10-4. and 0.05 For Adamw, we take inner iterations and a buffer size of one and for muon, we take inner iteration and a buffer size of one. Next, HiLoFi considers a rank of 50 for the hidden parameters, take qh.t 10 and ge 10-6 The initial covariances Σn,0 and Σe,0 are both initialized as identity times factor of 10 Similarly, LoLoFi is initialized with rank in the last-layer to be 100. For LRKF, we consider rank of 50, En is initialized as the identity matrix, and d: 10-6 Finally, for LoFi, we also considered rank 50; then, following the experiments in [8], we considered the initial covariance to be aI, with exp(-8) (8 (this corresponds low-rank comprised of matrix of zeros and diagonal terms, all a); lastly, the dynamics covariance is = O.
chosen as follows:
with HiLoFi, but
All initial model parameters from the neural network are shared across methods and trials.
Regret analysis. Below, we present results considering regret. Here, the reward is either 1, if the classification is done correctly and 0 otherwise. Let y/ {0, be the reward obtained at time t, and Yt.a be the value of arm a. Then the regret obtain at time / given by
(max Vr. vt) =
Vr
Figure 8 shows the average regret (across 10 trials) for HiLoFi, LoLoFi, LRKF, LoFi, and LLL. Here, we consider e-greedy variants for HiLoFi, LoLoFi, and LRKF. Next, TS with LLL and Adamw optimizer is denoted adamw-TS. TS. TS with LLL and muon optimizer is denoted muon-TS, e-greedy with Adamw optimizer is the denoted adamw-eps, and e-greedy with muon optimizer is denoted muon-eps.
Time-regret analysis. Figure shows the total running time to run the ten trials in the r-axis, regret around one-standard deviation in the y-axis. We observe Adamw and muon are the methods with lowest performance and lowest relative cumulative reward for either e-greedy or TS using LLL. Next, observe that LRKF is faster than LoLoFi, and LoLoFi is faster than HiLoFi. This result
34

---

eps
LoFiipBays
30000
NiLofi-peees
Lafi-TS
regret
FLoRESLite-eps
... adamw-eps
20000
LoLoe--BBaee
adante-pBaye
LRKF-eps
adamw-TS
LRKF-pBayes
muon-eps
10000
loFi-eps
5000
10000
15000
20000
25000
30000
35000
40000
num. observations
Figure 8: Total running time for experiments (z-axis) versus average regret across ten trials (3-axis).
35000
agent
30000
HiLofi
LoLoFi
25000
LRKF
LoFi
20000
adamw
15000
muon
sampling
10000
PS
10a
10a
104
TS
time (s)
Figure 9: Total running time for experiments (I-axis) (y-axis).
relative cumulative reward
expected and is explained in Appendix D.2. We also observe that LoFi with c-greedy matches LoLoFi with PS in time; however, LoLoFi has lower regret. We conjecture that this result due to explicit modeling of the last layer done for LoLoFi.
Finally, we observe that for all methods, e-greedy faster than TS. This is because e-greedy only requires the evaluation of the posterior predictive mean, whereas TS samples from the posterior predictive, which in turn requires building the posterior predictive covariance shown in (10).
G.2 Online classification using LRKF the CIFAR-10 dataset
In this Section, we study the ability of LRKF to scale to milliondimeensionll parameters for online classification the CIFAR-10 dataset. We consider VGG-style convolutional networks of different capacity. Both follow the pattern of stacked 3 x convolutions, ELU activations. We summarize the architectures below We follow similar setup as that of Appendix G.I.I. We take
Model
Conv Blocks
Dense Layers
Params
VGG
64 x 2 + 128 2 256
256 256
1.7M
VGG+Block 64 x 2 + 128 x 2 > 256 + 512 x
256 + 256
4.7M
Table 3: Summary of the two VGG-style architectures used in our experiments. "C x n" denotes
convolutional layers with C channels.
the data D1.r with = 10, 000 and D. = (x,, y:), where æ is a (32 x 32 x 3dmdimension array and yı E {0, 1} 10 one-hot encoded vector such that yı- At every timestep t 1..... . each agent presented the image I, which it has to classify. A predicted classification is made through the prediction 3tjr-1 f 2x) with M E Di 1] and then updates its beliefs given the (true) reward y:- Updates are done as outlined in Appendix G.I.I.
35

---

Table shows the one-step- -head accuracy for LRKF for ranks 1, 5, and 10. These results show
Model
LRKF-1
LRKF-5
LRKF-10
VGG (1.7M)
0.3355
0.3384
0.3379
VGG+Block (4.7M)
0.3129
0.3141
0.3148
AdamW (baseline)
VGG: 0.3442
VGG+Block: 0.3097
Table 4: Online classification results on CIFAR-I0 using LRKF with varying ranks (1, 5, 10), compared against AdamW baselines. Lower values are better.
that LRKF scales reliably to multi-million parameter networks while maintaining stable performance across different low-rank configurations. This highlights the broader applicability of approach (including HiLoFi and LoLoFi) to large-scale architectures in vision and related domains where sequential decision making needed.
G.3 Bandits as recommendation systems
Further results from Section 5.3
Choice byperparameters. In this experiment, agents shared rank 20. The choice of hyperparameters for LLL, LoFi, VBLL, and OnVBLL were chosen following analysis of performance on the first 10, 000 observations of the datasets. In particular, we tried Bayesian optimization techniques, but found that manual tuning of hyperparameters on the first 10, 000 observations yielded higher overall performance.
For OnVBLL, we considered a buffer size of 10, regularization weight of 1.0, and 50 inner iterations. For VBLL, we considered a buffer size of 1000, a regularization weight of 10 10-3, and 100 inner iterations.
Next, for HiLoFi, take Oh.t = ge. 0.0 and set the initial covariances be the identity. Next, for LRKF, we take ge = and identity matrix as initial covariance.
Further results. Figure 10 shows the daily cumulative reward for all methods. To produce this plot, we sum the cumulative rewards for all users at the end of each day and then perform a cumulative sum the end-of-day reward. We observe that HiLoFi obtains the highest daily cumulative reward.
Scaled daily cumulative reward
25
HiLoFi
LoFi
OnVBLL
20
LRKF
VBLL
15
10
5
0
06
13
20
27
03
10
17
24
31
Aug 2020
Sep
Figure 10: Daily cumulative reward.
The method with second highest daily cumulative reward LRKF, closely followed by LoFi and VBLL. However, shown in Figure 3, LRKF is more than an order of magnitude faster than VBLL.
36

---

From Figure 10 and Figure 10, we observe that the top performing methods in this experiment are HiLoFi and LRKF. However, LRKF is slightly faster than HiLoFi relative to all other methods.
G.4
Bayesian optimization
Further results from Section 5.4
Choice of hyperparameters. We fix hyperparameters across methods to ensure fairness and reproducibility. For rank-based methods, we use rank of 50, Methods requiring buffers (e.g., LLL, OnVBLL) use FIFO replay buffer of size 20, with 50 inner iterations per update. VBLL uses the full dataset and 100 iterations per step.
Where applicable, aleatoric uncertainty is discarded (R, 0) isolate epistemic effects. We consider equal learning rates across optimizer- based methods (e.g., LLL, OnVBLL) at 10 In filtering- based methods (e.g.. HiLoFi, LoFi), this learning rate corresponds the initial hidden-layer covariance; we set the final-layer prior variance to I, emphasising epistemic modelling in the output layer. Hyperparameters for VBLL (Wishart scale, regularization weight) follow prior work [5].
Per-step results. Figure 11 shows the median performance and the interquartile range of the best value found by each method for all test datasets. We observe that VBLL, OnVBLL, and HiLoFi
HiLofi
GP
LoFi
LRKF
VBLL
OnVBLL
LLL
Ackley2
Ackley5
Ackley10
Ackley50
22
best value
-4
-65
8.55
6
7.0
3.70
-7
8.85
-8
-8.0
9900
x10
Branin
Hartmann
x100
Nndraw50
x10
Nndraw200
2.5
2.4
best value
2.0
1.6
0.9
1.5
0.8
0.6
1.0
0.0
0.3
observations
observations
observations
observations
Figure 11: Bayesian optimization benchmark on stationary environments.
among the top performers for all datasets. Next, LLL is the least performant method for the low-dimensional datasets, but among the top performers for Nndraw50 and the top perfomer in Nndraw200..
Next, Figure 12 shows the median performance and the interquartile range of the best value found by each method for all test datasets using expected improvement.
G.4.1 NN Draw
Here, we provide further results for the performance of HiLoFi and LRKF for the Bayesian optimiza- tion problem the DrawNN dataset.
Figure reports the best value found over the course of the optimization as function of iteration, for different ranks. We observe that increasing the rank generally improves performance, with higher ranks yielding sharper improvements early the search that compound into stronger final results. This comes with trade-off between computational cost and the ability to capture uncertainty more effectively, as illustrated in Table 5, which reports the final performance and running time across ranks. We observe that both performance and running time generally increase with rank.
37

---

HiLoR
LoFi
LRKF
VBLL
ONVBLL
LLL
Ackley2
Ackley5
Ackley10
Ackley50
-6.
best value
44
6
-7.0
-6-
8.85
-7.5
-8
88
8800
99.00
20
40
50
100
50
100
25
50
75
100
x10
Branin
Hartmann
x10
Nndraw50
x10
Nndraw200
2.5
DESt: value
2.0
1.00
0.75
1.5
0
0.50
-2
0.25
20
40
20
30
100
150
200
150
300
450
600
num. observations
num. observations
num. observations
num. observations
Figure 12: Bayesian optimization benchmark on stationary environments. Query points are chosen
using expected improvement.
NN Draw 200 HiLoFi
Rank
26.67s
050 29.55s
1000
150 42.79s
best value
200 53.06s
800
600
200
iteration
Figure 13: Solid lines show the median best value over 20 runs, and shaded regions denote the interquartile range.
Finally, Figure 14 shows the best value obtained during optimization as function of the number of observations, for different ranks using LRKF. Compared to HiLoFi, LRKF requires substantially higher ranks to achieve similar median performance. For instance. performance is comparable at rank 300 for LRKF (73s) and rank 200 for HiLoFi (under 50s). This demonstrates that explicitly modeling the last layer in full rank, as done in HiLoFi, yields more favorable accuracy-efficiency trade-off.
G.5 In-between uncertainty
In this experiment, we test the ability of HiLoFi to capture the in-between uncertainty [2.]] after single pass of the data. We consider the one-dimensional dataset introduced in [58] (Figure 1). For this experiment, we consider four hidden-layer MLP with 128 units per layer and ELU activation function.
Result for HiLoFi. We take (h.t ge. 0, initial covariances for last and hidden layers to be identity times 1/2, and R, = 0.0, which corresponds having no aleatoric uncertainty in the data generating process.
38

---

Rank
Time (s)
Final ybest
26.226
656.558
10
38.4492
630.556
20
28.8612
670.913
50
30.6409
684.009
100
34.5302
782.205
110
35.1504
774.416
120
39.2540
007.298
130
38.2288
846.218
140
39.1417
848.219
150
40.7939
864.806
160
42.1907
911.116
170
44.5485
900.566
180
45.5640
864.260
190
47.1553
911.262
200
48.2127
921.062
Table 5: Performance metries across different low-rank configurations.
NN Draw 200 LRKF
Rank
1200
001
010 19.76s
050 20.25s
1000
100 23.82s
best value
200 29.235
600
400
200
300
tteration
Figure 14: Bayesian optimization on the NNDraw dataset using LRKF. Solid lines show the median best value over 20 runs, and shaded regions denote the interquartile range.
Figure 15 shows the posterior predicted mean surrounded by the two-standard deviation posterior predictive for various ranks in the hidden layer.
We observe that a rank of is not able to capture any uncertainty around the region with no observations; however, as increase the rank, we observe that the posterior predictive becomes less and less confident about the true value of the mean on regions without data.
Next, Figure 16 shows the evolution of the posterior predictive mean and the posterior predictive variance as a function of the number seen observations.
We observe that the uncertainty around the posterior predictive mean is wide (covering the limit from -10 to 10) and starts to decrease after 10 observations. By 30 observations, the uncertainty is narrower over regions where data has been observed, and by 120 observations, most of the posterior predictive uncertainty on regions where no data has been observed.
Result for LRKF mean surrounded by two-standard deviation posterior predictive for various ranks. contrast to HiLoFi, we observe that LRKF requires much higher rank to capture reasonable level of in-between uncertainty. The panel for rank is empty because the posterior predictive (with R. = 0) psd, so it is not defined.
We repeat the experiment above for LRKF. Figure 17 shows the posterior predicted
39

---

rank=1
rank=5
rank=10
10
-10
rank=20
rank=50
rank=100
10
-10
-0.5
0.0
0.5
-0.5
0.0
0.5
-0.5
0.0
0.5
X
X
X
Figure 15: In-between uncertainty of the posterior predictive induced by HiLoFi function of rank.
num. obs 1
num. obs = 5
num. obs = 10
10
-10
num. obs 15
num. obs = 30
num. obs 45
10
0
-10
num. obs
50
num. obs
100
num. obs
120
10
0
-10
-0.5
0.0
0.5
-0.5
0.0
0.5
-0.5
0.0
0.5
Figure 16: In-between uncertainty of the posterior predictive induced by HiLoFi as a function of observations.
An important distinction between LRKF and HiLoFi is the HiLoFi considers full-rank covariance matrix in the last layer. Despite this, LRKF with rank 200 (which shows some notion of uncertainty) requires around 3 times more coefficients in the covariance than HiLoFi with rank 50 in the hidden layers.
We show the evolution of the posterior predictive mean and variance with rank 200 of LRKF function seen observations in Figure 18.
We see that the evolution of the posterior predictive resembles that of HiLoFi, but at the cost of 3 times more number of coefficients the covariance.
Result for VBLL. We contrast the result of HiLoFi with the offline VBLL method. For VBLL, the data is presented all at once and we perform full-batch gradient descent using Adamw with learning rate 10-3, Figure 19 shows the posterior predictive mean and two standard deviations around the posterior mean, as well as the loss curve for various epochs.
We observe that VBLL takes around 10d epochs converge, whereas HiLoFi takes only one. We emphasize that each epoch in VBLL considers all datapoints once, so the gradient update more informative, whereas for HiLoFi, the method only gets to observe the data once and in sequence.
40

---

rank 10
rank=20
rank=50
10
-10
rank=100
rank=200
rank=500
10
-10
-0.5
0.0
0.5
-0.5
0.0
0.5
-0.5
0.0
0.5
X
X
X
Figure 17:
In-between uncertainty of the posterior predictive induced by LRKF function of rank.
num. obs = 1
num. obs = 5
num. obs = 10
10
0
-10
num. obs 15
num. obs = 30
num. obs 45
10
-10
num. obs 50
num. obs
100
num. obs 120
10
0
-10
-0.5
0.0
0.5
-0.5
0.0
0.5
-0.5
0.0
0.5
Figure 18: In-between uncertainty of the posterior predictive induced by LRKF as a function of seen observations.
This highlights the efficiency our method to produce approximate posterior predictives that can be used online.
41

---

posterior predictive
loss
10
epochs
0
-18
10
epochs
10
-1
epochs
10a
100
0
-10
10
epochs
1000
0
10
-10
10a
epochs
10000
10
0
100
0
-10
-0.5
0.0
0.5
109
101
102
103
104
x
num. epochs
Figure 19:
In-between uncertainty of the posterior predictive induced by VBLL as a function of number of epochs.
42

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The frequentist and Bayesian approaches to filtering are introduced in Section 3.2 and detailed in Appendix B. Our method and its assumptions are detailed in Section
4. Mathematical proofs of our claism are collected in Appendix E. Experiments and comparisons to other methods validating the experimental claims are provided in Section 5. The motivation and contribution for our method provided in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Limitations the method are discussed in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
43

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The main assumptions of the methods we introduced are detailed in Section 3.2 and Appendix B. The proof of Proposition D. is in Appendix 1, the proof of Proposition D.2 is in Appendix E.2, the proof of Proposition D.3 in Appendix E.3, and the proof of Proposition 4.1 is in Appendix E.4. Further propositions and proofs for the LRKF are stated and proved in Appendix F.2.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: To facilitate reproducibility of the methods we present, Algorithm 4 details LRKF, Algorithm 2 details HiLoFi, and Algorithm 3 details LoLoFi. The experiments are detailed in Section 5, which mentions the dataset and the neural architecture used. Further information (such as hyperparameter selection) for all experiments is detailed in Appendix G. Furthermore, we provide code reproduce the results in the anonymized link in the introduction.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
44

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All our datasets are open source and available at the mentioned sources in Section 5. Preprocessing of the data is detailed in Section and Appendix G. Detailed pscudocode for the methods we introduce are detailed Algorithm for LRKF, Algorithm 2 for HiLoFi, and Algorithm 3 for LoLoFi. Furthermore, we provide code to reproduce the results the anonymized link in the introduction.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips. cc/ Sealiiigguiee//Coeee
issiinolscccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ /niis. wwtpccppppllcc..ceccc.c httpc//ggiide//oeeuumiiii SCodeeubmissiiiiieeeeeee ssionsolicyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The training and test details are in Section and Appendix G.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
45

---

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are reported and explained for all experiments in Section 5 and Appendix G. For the experiment in Section 5.2, suitable error bars are deferred Figure in Appendix G.1.3 as including them in the main figure would have made it overly cluttered and difficult to interpret.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Compute workers are detailed in Section 5. An estimate of the running time to replicate the results with the compute used are provided in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics attps://neuus http://uurriisccppuuupe hc/ppulicc/thiisSuieeeee ines?
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics, and the research conducted in the paper conforms, in every respect, with these guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
46

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Potential societal impacts are acknowledged in Section 7.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
The methods developed in this paper are general- purpose tools for online learning and sequential decision-makien We do not believe they pose high risk of misuse, and therefore specific safeguards were necessary.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
47

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All assets used, whether code, data, models have been properly cited in the main text.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Assets are detailed the introduction of the main text. We include all details to reproduce our methods and the licence is provided within the code. Consent was not required.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper did not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
48

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper did not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.MM policy (https: http:///eeuu/eeeeeeee wttppsscccc/ooeeeeeeeeee http://s...cccoeeeeeee////////// /LLM) for what should or should not be described.
49


Reviews:
[{"review_id": "fhllCscwmn", "reviewer": "Reviewer_K1Y3", "summary": "The paper proposes a class of scalable algorithms for sequential training of neural networks. The method sequentially computes best linear unbiased prediction (frequentist parameter estimate) and construct a pseudo posterior predictive using a Gaussian approximation with a block-diagonal error variance-covariance estimate and proceeds in an online fashion. The method is shown to achieve a good balance between speed and accuracy for a variety of online learning problems.", "questions": "1. If one is not interested in the uncertainty of the parameters, but rather of the predictions, why use a Bayesian model at all? For contextual bandits, example would be UCB-type algorithms. Since you are not constructing the full posterior, but approximating it as a normal by plug-in mean and variance frequentist estimates, what purpose does Bayesian inference serve in the work?\n2. I am a bit worried about the setup. Do you assume the parameters at each time $\\{\\theta_t\\}$ related in any way (as often done in hierarchical models for borrowing strength)? If not, what connects the observations at different time points? In your example of contextual bandit, the underlying $\\theta$ is assumed to be fixed (not depending on time), only the estimate $\\hat{\\theta}_t$ depends on time - since all previous observations (say from same arm) are connected through that parameter. Can the authors clarify the setup here. In the case you assume a linear dynamic evolution (as in Section 3.2), how sensitive is the algorithm to misspecification of this dynamics?\n3. For the bandit experiments, did you compare the results with a usual TS? Or maybe a high-dimensional version if the contexts are high-dimensional?\n4. Using a point estimate (for example MAP) and using it for sequential learning in Bayesian models, through the posterior predictive, has been proposed in the literature - for example (i) Sequential Algorithm for fast fitting of DPM models [Zhang, Nott, Yau, Jasra], (ii) Fast Bayesian Inference in DPM models [Wang, Dunson], (iii) Scalable nonparametric Bayesian learning for dynamic velocity fields [Chakraborty, Guha, Lei, Nguyen] - how does your work differ in essence from these. It might be good to include some of these references.\n5. Proposition 4.1 gives some idea - but can you elaborate on the role of the following $R_t, q_{\\ell,t}, q_{h,t}$ on the overall algorithm? It seems these are hyper parameters - a discussion on the tuning might be good.\n6. Can the method be used in probabilistic models where the observation noise is not additive? Or its variance unknown (related to point 5)\n7. Proposition 4.1 - even when no low-rank structure is utilized, there is no consistent estimation of $\\Sigma$ as $t\\to\\infty$ - can you comment on why this is true?\n8. Can you say something about the estimation quality of the BLUP, characterize $\\Vert \\theta_t - \\hat{\\theta}_t\\Vert$? Or at least the predictive accuracy?", "limitations": "See the questions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper is well written (although the notations are a bit too much) and the extensive experiments demonstrate promise to the proposed methodology. The only concern is novelty (since both sequential estimation by approximate posterior)", "was_revised": true, "final_justification": "score updated", "rebuttal": "Thank you for your review.\n\nWe believe the statement in your Strengths/Weaknesses section was left incomplete. That said, we hope our responses address your concerns.\n\nTo clarify novelty: we introduce a constant‑cost, Kalman‑style update that keeps a single theta estimate for a neural network and enables Bayesian decisions via the posterior predictive. Unlike prior cited DPM/iHMM work (i-iii above), we target tractable online neural‑learning and sequential decision‑making.\n\nWe appreciate the formatting suggestions. We will add a table of notation, remove numbering on comments in Algorithm 1, and use \"parameter\" only.\n\n**R1.1: Why Use a Bayesian Model If You Don’t Model Parameter Uncertainty?**\n\nWe adopt the martingale posterior view [Holmes2023], in which the posterior predictive drives sequential decisions and the belief state is updated separately. Although classical TS samples parameters, it is ultimately outcome uncertainty that drives exploration. Our method captures this directly via the posterior predictive.\n\nThis new approach has several advantages:\n\n* It enables Thompson sampling (TS)-style exploration without sampling from a high-dimensional posterior (which comes at a 10-100x speedup with comparable or increased performance. See R1.4)  \n* It supports plug-and-play non-Bayesian learning updates while retaining Bayesian decision logic, e.g., using HiLoFi. \n\nAs you mention, UCB and also Expected improvement are valid alternatives; we include an EI example in Figure 11 (Appendix).\n\nWe will emphasize this framing more clearly. Specifically:\n* Rename the paper to \"Martingale Posterior Neural Networks for Fast Sequential Decision Making\",  \n* Update the abstract and introduction,  \n* Add a new pseudoalgorithm to illustrate the sampling + frequentist update loop.\n\nFor contextual bandits with one model per arm, the pseudoalgorithm is\n```\n// Define posterior predictive parameterised by belief state b\n// and having inputs: the context ‘x’ and action ‘a’.\ndef p(· | x, a, b):\n    ...\n\nFor each a in actions:\n   // belief state:\n   // need not define a valid posterior or consider two moments only\n    b(t, a) = (mu(t, a), Sigma(t, a))\n\nFor all a in actions:\n    // sample from Bayesian posterior predictive \n    ŷ(t, a) ~ p(· | x(t), a, b(t, a))\n\na_next = argmax_a[ŷ(t, 1), ..., ŷ(t, A)]\n\n// frequentist update (e.g., HiLoFi)\nb(t+1, a_next) = update(b(t, a_next), y(t, a_next))\n```\n\n**R1.2 Do you assume the parameters at each time related in any way?** \n\nWe do not use a hierarchical model for \"borrowing strength\". Instead, we assume that the parameters evolve according to a random walk, (Line 94), i.e., $\\theta_t = \\theta_{t-1} + u_t$, with $var(u_t) = q I_D$.\n\nThis assumption is common in adaptive filtering and online learning (see e.g. [Ismail1996] and [Chang2023]) and provides a simple way to ensure adaptivity and numerical stability.\n\nIn the special case where $q=0$, and without a low-rank assumption, we recover a static parameter model and our estimate $\\theta_{t|t}$ is simply the Bayesian posterior mean given data up to time t, i.e., $\\theta_{t|t} = E[\\theta | y_{1:t}]$.\n\n**R1.3 How sensitive is the algorithm to misspecification of this dynamics?**\n\nThe dynamics $\\theta_t = \\theta_{t-1} +  u_t$ are misspecified by design. They are intended to serve as a regularisation mechanism for adaptivity and numerical stability, rather than reflecting the true data generating process. This dates back to, e.g., [Mehra1970].\n\nTo empirically assess sensitivity, we conducted a new experiment on the DrawNN Bayesian Optimization benchmark mentioned in the paper (using 600 steps). We varied both the hidden layer ($q_h$) and last-layer ($q_\\ell$) dynamics for HiLoFi across several values and report the final maximum value found (averaged over 10 runs).\n\n|qh/qh|0.0|1e-06|1e-05|0.0001|0.001|\n|---|---|---|---|---|---|\n|0|911.023|925.541|903.86|856.529|850.668|\n|1e-06|908.951|877.041|902.752|906.037|915.497|\n|1e-05|885.912|858.062|902.754|883.262|882.13|\n|0.0001|880.655|905.342|877.899|861.019|895.526|\n|0.001|834.449|791.294|823.188|809.964|809.104|\n\nThe results are robust. Some tuning helps but no catastrophic failure was observed. We’ll include these results in the revision.\n\n**R1.4 For the bandit experiments, did you compare the results with a usual TS?**  \nThank you for the suggestion.\n\nGiven an arm $a$,  standard TS samples $\\hat{\\theta} \\sim p(\\theta | D_{1:t})$ and uses $\\hat{y}\\_{t+1} = f(\\hat{\\theta}, x\\_{t+1}, a)$ to make decision. In predictive TS (pBayes), we sample directly from $\\hat{y}_{t+1} \\sim p(y |x\\_{t+1}, \\theta\\_{t|t}, a)$.\nIn the revised paper, we expand our MNIST bandit experiment to compare standard TS with pBayes approach.\n\nWe find that pBayes is 10-100x faster, than classical TS, while also giving comparative or higher cumulative reward. The speedup stems from sampling a low-dimensional predictive distribution instead of a high-dimensional parameter posterior, even when that posterior has a structured form (e.g., diagonal-plus-low-rank, as in LoFi).\n\nThe table below shows the results of comparing standard TS (LoFi, Laplace) and predictive TS (HiLoFi, LoFi, Laplace) on the \tMSNIST bandit task.\n\n|method|reward|time(min)|\n|---|---|---|\n|HiLoFi-pBayes|31,168|8.43|\n|LoFi-TS|23,304|38.90|\n|LoFi-pBayes|23,185|4.76|\n|Laplace-TS|7,202|191.54|\n|Laplace-pBayes|13,922|1.36|\n\n\n**R1.5 How does your use of posterior predictive with point estimates differ from prior MAP-based approaches in the literature**\n\nThe works suggested above (i-iii) use MAP‐plug‑in updates for nonparametric mixture models (iHMMs/DPMs) to accelerate posterior inference. Our approach departs in three key ways:\n\n1. Those papers maintain a growing set of mixture components, whereas we keep and update only one global parameter vector $\\theta_{t|t}$ that (possibly) evolves over time.\n2. We target neural networks trained sequentially, with constant-time per update. These settings are not addressed by the cited DPM literature.  \n3. We tackle the problem of sequential decision making using so-called Martingale posteriors, which is not considered in cited works.\n\nIn the revised section, we reference each of the papers you mention and emphasize that our approach is a single-estimate parametric approach for online learning and sequential decision making.\n\n**R1.6 Can you elaborate on the roles of R, q(ell), and q(h), and how they should be tuned?**\n\n$R_t$ is the heteroskedastic noise process. Its purpose is to downweight the update information arising from natural variation of the observations y. This parameter can be estimated using an exponentially-weighted moving variance or in a burn-in period, as we do in the experiments.\n\nThe q-values, $q_\\ell$ and $q_h$,  are parameters for adaptation and stability:\n\n* $q_\\ell$  is the speed of adaptation for the last layer and  \n* $q_h$ is the speed of adaptation for the hidden layers.\n\nAs a rule of thumb: $q_h \\leq q_\\ell$ because, for a neural network, the capacity of the hidden layers is much greater than that of the last layer. In our experiments, these parameters are estimated during an initial phase or using alternative methods such as those in, e.g., [Titsias2023]\n\n**R1.7 Can the method be used in probabilistic models where the observation noise is not additive? Or its variance unknown (related to point 5)**  \nOur method could be employed in parametric probabilistic models where the observation noise is not additive, however, these are better suited for sampling-based methods, similarly, for unknown variance, one can use methods such as [Agamennoni2012].\n\n**R1.8 Consistency of Proposition 4.1 when no low-rank structure is used**    \nIf no low-rank structure is used, then we would couple all layers and there is no need to use the \"surrogate matrix\" (shown in Equation (94),  L787 in the Appendix) required for the low-rank projection. Hence, the approximation error would be zero (by definition).\n\n**R1.9 Can you say something about the estimation quality of the BLUP?**   \nWhile little can be said about the true $\\theta$, we can bound the estimation error by comparing a low-rank approximation (e.g., LRKF) against a full-rank update. In the linear regression case $y\\_t = \\theta^\\intercal x\\_t + e\\_t$ with fixed $\\theta$ and known $var(e\\_t) = r$, let $\\Sigma\\_{t-1}$ be the full-rank covariance  The one-step parameter difference between the BLUP using full-rank and using a rank-d update is upper bounded by:\n\n$$\n\\\\|\\theta\\_{t|t}-\\hat{\\theta}_{t|t}\\\\|\\_2 \\leq |\\epsilon\\_t| \\sigma\\_{d+1}(\\Sigma\\_{t-1})\\\\|x\\_t\\\\|_2 \\left( \\frac{1}{\\gamma\\_t} \\+ \\frac{\\sigma\\_{1}(\\Sigma\\_{t-1})\\\\|x\\_t\\\\|_2^{2}}{\\gamma\\_t^{2}} \\right), $$\n\nHere, $\\sigma\\_{d+1}(\\Sigma_{t-1})$ is the first discarded singular value and $\\sigma\\_1(\\Sigma_{t-1})1$ is the largest singular value, $\\theta_{t|t}$ is the BLUP computed using the full rank and $\\hat{\\theta}_{t|t}$ is the BLUP with rank-d LRKF update, $\\gamma\\_t  =\\max\\\\{x\\_t^{\\intercal}\\Sigma\\_{t-1}x\\_t, x\\_t^{\\intercal}\\widehat\\Sigma\\_{t-1}x\\_t\\\\} \\+ r$, and\n$\\epsilon_t = y\\_t - \\theta\\_{t-1|t-1}^\\intercal x\\_t$.\n\nWe can see that if $d=D$, then the error is zero. In general, having a fixed  innovation and features, the error grows linearly with the first discarded singular value. A derivation will be provided in the revised text.\n\n[Holmes2023] Holmes & Walker (2023). Statistical inference with exchangeability and martingales, Phil. Trans. R. Soc. A.  \n[Ismail1996] Ismail & Principe (1996). Equivalence between RLS algorithms and the ridge regression technique, IEEE Conf.  \n[Chang2023] Chang et al. (2023). Low-rank EKF for NN learning, Conf. on Lifelong Learning Agents.  \n[Mehra1970] Mehra (1970). Adaptive filtering approaches, IEEE CDC.  \n[Titsias2023] Titsias et at. (2023). Kalman filter for online classification of non-stationary data arXiv:2306.08448  \n[Agamennoni2012] Agamennoni et al. (2012) Approximate inference in state-space models with heavy-tailed noise, IEEE Transactions on Signal Processing"}, {"review_id": "OZdpqgrm5A", "reviewer": "Reviewer_U5Um", "summary": "This paper proposes a hybrid frequentist–Bayesian approach for online learning and Bayesian inference. It uses Kalman filtering to recursively update neural network parameters and their associated uncertainty, and employs Bayesian predictive sampling for decision-making. The key idea is to avoid expensive posterior inference over network parameters by instead focusing on modeling predictive uncertainty directly. The method is fully online and single-pass, requiring no replay buffers or offline retraining. The authors evaluate their approach on three sequential decision-making tasks, spanning contextual bandits and Bayesian optimization, and demonstrate that it achieves a competitive trade-off between speed and accuracy.", "questions": "What is the benefit of combining frequentist Kalman-style updates with Bayesian predictive sampling?\n\nWhy is the shift from uncertainty in parameters to uncertainty in predictions helpful for decision-making?\n\nWhy is Kalman filtering, especially the extended variant, a natural fit for online neural network training?\n\nWhy is replay buffer an issue in GP?", "limitations": "Yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe combination of frequentist Kalman-style updates with Bayesian predictive sampling in a fully online, replay-buffer-free neural-network framework is novel and well-motivated. This method is also scalable to applications including bandits, Bayesian optimization, and classification. The experiment evaluations are comprehensive.\n\n\nWeaknesses: \n\nThe paper has several issues that limit its clarity and broader accessibility. \n\nIt frequently assumes familiarity with key terminology (e.g., “replay buffer,” “in-different uncertainty”) without proper explanation. For instance, it mentions “replay-buffer approaches for Bayesian optimization” without specifying what they are (likely referring to GPs), nor does it clarify how replay buffers are costly in such methods. \n\nThe sentence “we focus on uncertainty in predictions rather than parameters” appears in the decision-making section without clearly explaining that this predictive uncertainty is used for downstream decisions (e.g., via Thompson Sampling), and why this shift of focus is beneficial in practice. \n\nThe connection between uncertainty quantification and decision-making needs to be made more explicit. Similarly, the purpose of Figure 2—contrasting full-feedback and partial-feedback settings—should be more clearly stated. \n\nAll experiment plots lack sufficient explanation. The term “performance” in Figure 5's caption is confusing as there is both \"time performance\" and \"rank performance\" in the right panel of Figure 5. The left panel of Figure 5 lacks error bars without justification or clarification of what uncertainty is being reported.", "was_revised": true, "final_justification": "Most of my questions are addressed during rebuttal and discussions. But since there is a change of title, abstract, and introduction, I expect there would be a fair amount of updates.", "rebuttal": "Thank you for your review and thoughtful suggestions. Your comments have helped improve the accessibility of our paper. We summarize the revisions and respond to your questions below.\n\nWe clarify that replay-buffer methods store data for repeated use in training (e.g., BNNs) or inference (e.g., GPs). While we don’t claim these methods are inherently costly, our approach avoids them entirely, which makes our method suitable for privacy-sensitive or streaming settings.\n\nFurthermore, in the revised version of the text, we introduce the notion of “in-between” uncertainty, originally discussed by \\[Foong2019\\]. This concept refers to how well a model captures uncertainty in regions of input space that lie between, or away from, observed data. Intuitively, we expect uncertainty to be higher in such unexplored areas. This behavior is important for Bayesian decision-making problems, where it supports effective balancing of exploration and exploitation.\n\nWe have also made the connection between uncertainty quantification and sequential decision making more explicit (please see R2.1 and R2.2 below).\n\nFinally, we will improve figure explanations. For Figure 5, the left panel shows best final value vs. runtime; the right panel shows rank across tasks. Error bars are included in Figure 10 (Appendix) and are referenced in the main text (L28).\n\n**R2.0 Changes to paper**  \nA key revision was to clarify the separation between the Bayesian predictive sampling and the frequentist update. To that end, we made the following changes\n\n* Renamed the paper to \"Martingale Posterior Neural Networks for Fast Sequential Decision Making\", which more succinctly expresses what we are doing: modelling uncertainty in predictions, rather than parameters. (Following \\[Holmes2023\\])  \n* Revised the text to make the role of the posterior predictive in decision-making more explicit. In particular, we now mention that our approach allows us to make Bayesian decision making in a more efficient way than the prior-times-likelihood approach.  \n* Introduced a new pseudoalgorithm to illustrate the key predict-act-update in contextual bandits and Bayesian optimization. For contextual bandits with one model per arm, the pseudoalgorithm has the form \n\n\n```\n// Define posterior predictive parameterised by belief state b\n// and having inputs: the context ‘x’ and action ‘a’.\ndef p(· | x, a, b):\n    ...\n\nFor each a in actions:\n   // belief state:\n   // need not define a valid posterior or consider two moments only\n    b(t, a) = (mu(t, a), Sigma(t, a))\n\nFor all a in actions:\n    // sample from Bayesian posterior predictive  \n    ŷ(t, a) ~ p(· | x(t), a, b(t, a)) \n\na_next = argmax_a[ŷ(t, 1), ..., ŷ(t, A)]\n\n// frequentist update (e.g., HiLoFi)\nb(t+1, a_next) = update(b(t, a_next), y(t, a_next))\n```\n\nThis illustrates how Bayesian decision-making via the posterior predictive is combined with constant-cost frequentist updates.\n\n## Questions\n\n**R2.1 What is the benefit of combining frequentist Kalman-style updates with Bayesian predictive sampling?**  \nThe Kalman-style frequentist update provides a lightweight alternative to a posterior parameter update. Instead of tracking the full posterior, we use the predictive distribution directly for sampling-based decision making (Thompson-sampling style). This achieves efficient online learning without sacrificing exploration-exploitation quality.\n\nThis style of separating the update of model parameters from the model used to make predictions (the posterior predictive) has been called the martingale posterior [Holmes2023]. In the new version of the paper, we changed the title to \"Martingale Posterior Neural Networks for Fast Sequential Decision Making\", modified the introduction, and modified abstract to make this distinction more explicit.\n\n**R2.2 Why is the shift from uncertainty in parameters to uncertainty in predictions helpful for decision making?**  \nBayesian neural networks typically rely on priors and likelihoods that are misspecified or chosen for convenience [Knoblauch2022], which can degrade predictive performance [Wenzel2020] and make posterior sampling significantly slower than non-Bayesian alternatives like deep ensembles [Lakshminarayanan2017]. Moreover, these priors often involve subjective parameter distributions with no real-world interpretation [Holmes2023].\n\nBy shifting focus to predictive uncertainty, we bypass the need for such priors and instead work directly with the posterior predictive, which is a lower-dimensional and more tractable object for decision-making.\n\nWe introduced a new experiment on the MNIST bandit, where we observe that predictive sampling achieves comparable or better cumulative reward than traditional TS, while being up to 100x faster in high-dimensional models. We clarify this distinction and its practical benefits in the revised text. \n\nThe results are shown in the table below\n\n| method | reward  | time (min) |  \n|:---------------|--------:|-----------:|  \n| HiLoFi-pBayes  |  31,168 |    8.43 |  \n| LoFi-TS  |  23,304 |   38.90 |  \n| LoFi-pBayes |  23,185 |   4.76 |  \n| Laplace-TS  | 7,202 |  191.54 |  \n| Laplace-pBayes |  13,922 |   1.36 |\n\n**R2.3 Why is Kalman filtering, especially the extended variant, a natural fit for online neural network training?**  \nThe (Extended) Kalman Filter is a form of second-order optimizer, equivalent to natural gradient descent. In practice, this means that each update is more sample-efficient than \"rank-one\" updates like, e.g., Adam  \n[Yann2018] [Khan2023] [Jones2024].\n\nWe clarify this in the main text.\n\n**R2.4 Why is replay buffer an issue in GP?**  \nWe do not claim replay buffers are inherently problematic. Instead, we emphasize that our method sidesteps this entirely. This is valuable in domains where data cannot be revisited (e.g., for privacy reasons [Tenenbaum2021]), where input distributions change over time (rendering stale data misleading [Chang2023]), or where the inputs are high-dimensional observations [Harrison2024]. \n\nWe will make sure to remark this observation in the revised text.\n\n----\n\n[Knoblauch2022] Knoblauch, Jeremias, Jack Jewson, and Theodoros Damoulas. \"An optimization-centric view on Bayes' rule: Reviewing and generalizing variational inference.\" Journal of Machine Learning Research 23.132 (2022): 1-109.  \n[Wenzel2020] Wenzel, Florian, et al. \"How good is the bayes posterior in deep neural networks really?.\" arXiv preprint arXiv:2002.02405 (2020).  \n[Lakshminarayanan2017] Lakshminarayanan, Balaji, Alexander Pritzel, and Charles Blundell. \"Simple and scalable predictive uncertainty estimation using deep ensembles.\" Advances in neural information processing systems 30 (2017)  \n[Yann2018] Ollivier, Yann. \"Online natural gradient as a Kalman filter.\" (2018): 2930-2961.  \n[Khan2023] Khan, Mohammad Emtiyaz, and Håvard Rue. \"The Bayesian learning rule.\" Journal of Machine Learning Research 24.281 (2023): 1-46.  \n[Jones2024] Jones, Matt, Peter Chang, and Kevin Murphy. \"Bayesian online natural gradient (BONG).\" Advances in Neural Information Processing Systems 37 (2024): 131104-131153.  \n[Tenenbaum2021] Tenenbaum, Jay, et al. \"Differentially private multi-armed bandits in the shuffle model.\" Advances in Neural Information Processing Systems 34 (2021): 24956-24967.  \n[Chang2023] Chang, Peter G., et al. \"Low-rank extended Kalman filtering for online learning of neural networks from streaming data.\" Conference on Lifelong Learning Agents. PMLR, 2023.  \n[Harrison2024] Harrison, James, John Willes, and Jasper Snoek. \"Variational Bayesian last layers.\" arXiv preprint arXiv:2404.11599 (2024).  \n[Holmes2023] Holmes, Chris C., and Stephen G. Walker. \"Statistical inference with exchangeability and martingales.\" Philosophical Transactions of the Royal Society A 381.2247 (2023): 20220143.  \n[Foong2019] Foong, Andrew YK, et al. \"'In-Between'Uncertainty in Bayesian Neural Networks.\" arXiv preprint arXiv:1906.11537 (2019)."}, {"review_id": "RYYt3uJGR3", "reviewer": "Reviewer_41Eo", "summary": "- The paper proposes HiLoFi, which is a scalable method for maintaining uncertainty estimates of model parameters in online learning. The method uses a full-rank posterior over the final layer parameters with a low-rank approximation for hidden layers.\n- The method can be broken down into using EKF for iterative updates and uncertainty estimation (which doesn’t necessarily yield a proper distribution on the parameter space), and using a Bayesian approach to construct a valid posterior distribution for the target space.\n- Theoretical guarantees on low-rank approximation error are provided, and experiments are performed on several datasets.", "questions": "- In Figure 2, it seems that LoLoFi achieves better performance than HiLoFi. Do the authors have any hypothesis on why this happens?\n\n- Intuition: why only separates the last layer (in a 3-layer MLP, for example, it may be insufficient to evaluate the method's performance when more or fewer layers use a full rank error matrix)? Are there ablation experiments for a larger number of layers?\n\n- For proposition 4.1, are there empirical validations for this error bound? Can the rank d_h be dynamically tuned to trade off accuracy and compute?", "limitations": "The ML model architecture choices are modest. This leaves questions about whether HiLoFi scales to models used in domains like protein design, large-scale NLP, or vision.\n\nAs mentioned in the weaknesses section, in many online learning scenarios, especially in scientific domains, samples are expensive but time is not the main constraint. It would be useful to see:\n\n- Whether HiLoFi (and its underlying TS algorithm) offers superior sample efficiency over other acquisition approaches.\n- How trade-offs between low-rank approximation fidelity and sample utility are managed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The paper is clearly written: the methodology is sound, and step-by-step derivations are given to the methods to make them understandable. \n\n- The algorithm lowers the computational burden of online learning—I can imagine it being used in situations where previous methods with GP would simply fail to fit, or BNNs that would take too long to train. \n\nWeaknesses\n\n- I would say that there is insufficient exploration of scalability to deeper or wider networks. Most tested architectures, 3-layer MLPs or shallow CNNs, do not reflect the scale encountered in harder tasks (e.g., protein engineering, molecular design).\n\n- Also, in many real-world online tasks, the bottleneck is not computation time but sample efficiency. The paper does not discuss this tradeoff explicitly (it is quite crucial for many online applications like robotics or experimental design).", "was_revised": true, "final_justification": "The authors' newly conducted experiments addresses the majority of my concerns.", "rebuttal": "Thank you for reviewing our paper. \n\n**R3.0**  \nWe agree with your assessment.  \nIn the new version of the paper, we discuss the tradeoff between sample efficiency and computation time and mention that our method is designed to tackle problems in which computation-time is the main bottleneck. This is often the case in domains such as finance [Cartea2023], recommender systems [Duran-Martin2022], and Bayesian optimization where the number of acquired datapoints is reasonably large [Brunzema2024].\n\nWe also clarify in the revised version that our approach separates frequentist learning from Bayesian prediction. The model maintains a predictive distribution for decision making, updated via HiLoFi, without relying on full posterior inference. This is now reflected in the paper’s title and illustrated through added pseudocode and an additional comparison of \"classical\" TS and our \"predictive TS\" approach  (pBayes).\n\nThe pseudocode for our proposed predictive TS in a multiarmed contextual bandit problem is given below.\n\n```\n// Define posterior predictive parameterised by belief state b\n// and having inputs: the context ‘x’ and action ‘a’.\ndef p(· | x, a, b):\n    ...\n\nFor each a in actions:\n   // belief state:\n   // need not define a valid posterior or consider two moments only\n    b(t, a) = (mu(t, a), Sigma(t, a))\n\nFor all a in actions:\n    // sample from Bayesian posterior predictive  \n    ŷ(t, a) ~ p(· | x(t), a, b(t, a)) \n\na_next = argmax_a[ŷ(t, 1), ..., ŷ(t, A)]\n\n// frequentist update (e.g., HiLoFi)\nb(t+1, a_next) = update(b(t, a_next), y(t, a_next))\n```\n\nBelow we show results for the MNIST contextual bandit task, comparing traditional TS against our pBayes approach. Note that HiLoFi does not admit a full posterior over parameters, so we report pBayes results only. For LoFi and Laplace methods, which support both TS and pBayes, we report both.\n\n| method | reward  | time (min) |  \n|:---------------|--------:|-----------:|  \n| HiLoFi-pBayes  |  31,168 |    8.43 |  \n| LoFi-TS  |  23,304 |   38.90 |  \n| LoFi-pBayes |  23,185 |   4.76 |  \n| Laplace-TS |  7,202 |  191.54 |  \n| Laplace-pBayes |  13,922 |   1.36 |\n\nIn summary: Sampling from the posterior, as required by TS, is dramatically slower, while offering little or no performance gain. For example, Laplace-TS takes 190 minutes vs. 1.4 minutes for pBayes, with much worse reward. Even LoFi-TS is nearly 10X slower than LoFi-pBayes with similar results. pBayes clearly offers a superior speed-performance trade-off.\n\nNote that the  significant increase in speedup is because sampling, at every step, from a 10-dimensional multivariate Gaussian is much more computationally tractable than sampling from a D-dimensional multivariate Gaussian (even if the covariance structure is diagonal-plus-low-rank, as is the case for LoFi).\n\nWe have also introduced a new experiment with larger number of parameters ~4million (see R3.2 below) to address concerns about model scalability.\n\n## Questions\n\n**R3.1 In Figure 2, it seems that LoLoFi achieves better performance than HiLoFi. Do the authors have any hypothesis on why this happens?**\n\nThe purpose of Figure 2 is to show that when uncertainty modeling is less critical (e.g., a full-information setting), modelling the last layer explicitly performs on-par with other scalable approaches.\n\nIn particular, LoLoFi outperforms HiLoFi in some cases because higher-rank models require more steps to stabilize the covariance update. With more degrees of freedom and full-information updates, convergence takes longer. In this case, lower-rank update procedures can outperform in full-information settings.\n\nWe clarify this in the revised paper.\n\n**R3.2 Intuition: why only separates the last layer? Are there ablation experiments for a larger number of layers?**  \nApplying full-rank updates only to the last layer is a common design choice in scalable uncertainty methods and has shown strong empirical results in bandit and Bayesian deep learning settings \\[Harrison2024, Riquelme2018\\].\n\nThat said, we agree this warrants empirical support. We conducted a new experiment applying LRKF to VGG-style architectures with up to 4.7M parameters on CIFAR-10 after 10,000 observations. The results below show stable online classification accuracy across different low-rank approximation levels (ranks 1, 5, and 10):\n\n| model    | num. params     | accuracy (one-step-ahead) |\n|----------|-----------|----------|\n| VGG-1    | 1.7M      | 0.3355   |\n| VGG-5    | 1.7M      | 0.3384   |\n| VGG-10   | 1.7M      | 0.3379   |\n| \\+VGG-1   | 4.7M      | 0.3129   |\n| \\+VGG-5   | 4.7M      | 0.3141   |\n| \\+VGG-10  | 4.7M      | 0.3148   |\n\nFor comparison, a single-pass AdamW baseline achieves 0.3442 for VGG and 0.3097 for \\+VGG.\n\nThese results demonstrate that LRKF scales to multi-million parameter networks while maintaining stable performance across low-rank configurations. This supports the broader applicability of our approach (including HiLoFi and LoLoFi) to large-scale architectures in vision and related domains.\n\nIn the revised paper, we also include an additional experiment of the \"in-betwen uncertainty\" plot as we increase the number of layers of the MLP used.\n\n**R3.3 For proposition 4.1, are there empirical validations for this error bound? Can the rank d\\_h be dynamically tuned to trade off accuracy and compute?**  \nYes, please see Figure 7 in the Appendix where we show surrogate and low-rank error as well as rolling accuracy. These plots indicate that the error per step remains stable, and learning proceeds steadily across time.\n\nAs a rule of thumb, increasing d\\_h leads to better performance, with running time increasing at a roughly linear rate. This trend is illustrated in Figure 6 (MNIST bandit). Furthermore, Figure 13 shows that higher d\\_h improves the quality of in-between uncertainty estimates.\n\nTo make this point clearer,  we have also introduced a new ablation study on Bayesian optimization on the DrawNN dataset. Here,  we vary d\\_h and report the relationship between performance and compute cost:\n\n| rank d\\_h | time (s) | final best value |  \n|----------|----------|------------------|  \n| 1        | 27.5     | 656.6            |  \n| 10       | 38.1     | 630.6            |  \n| 20       | 27.6     | 670.9            |  \n| 50       | 29.4     | 684.0            |  \n| 100      | 32.6     | 782.2            |  \n| 110      | 35.5     | 774.4            |  \n| 120      | 39.5     | 807.3            |  \n| 130      | 38.6     | 846.2            |  \n| 140      | 39.6     | 848.2            |  \n| 150      | 38.2     | 864.8            |\n\nThe table above reports the performance of HiLoFi on the DrawNN dataset (Bayesian optimization), showing runtime in seconds and the final best value (averaged over 20 runs). As shown, both runtime and performance increase approximately linearly with d\\_h, reinforcing the trade-off discussed above.\n\n\n\nWe clarify these point in the revised paper (including this new experiment), emphasizing that d\\_h offers a practical trade-off between accuracy and compute, depending on available resources.\n\n---\n\n[Cartea2023] Cartea, Álvaro, Fayçal Drissi, and Pierre Osselin. \"Bandits for algorithmic trading with signals.\" Available at SSRN 4484004 (2023).  \n[Duran-Martin2022] Duran-Martin, Gerardo, Aleyna Kara, and Kevin Murphy. \"Efficient online bayesian inference for neural bandits.\" International conference on artificial intelligence and statistics. PMLR, 2022.  \n[Brunzema2024] Brunzema, Paul, et al. \"Bayesian optimization via continual variational last layer training.\" arXiv preprint arXiv:2412.09477 (2024).  \n[Harrison2024] Harrison, James, John Willes, and Jasper Snoek. \"Variational Bayesian last layers.\" arXiv preprint arXiv:2404.11599 (2024).  \n[Riquelme2018] Riquelme, Carlos, George Tucker, and Jasper Snoek. \"Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling.\" arXiv preprint arXiv:1802.09127 (2018)."}, {"review_id": "SUgE0uAqnr", "reviewer": "Reviewer_YaKM", "summary": "This paper aims to improve the efficiency of online learning by applying the extended Kalman filtering to estimate the latent parameters. The proposed algorithm uses a recursive update of the best linear unbiased predictor and its associated error variance-covariance. Variants of the method that rely on full/low-rank approximation are considered and the tradeoff between accuracy and speed is demonstrated through a set of experiments.", "questions": "1. Why do you focus on uncertainty in predictions rather than uncertainty in parameters? How does this approach compare to the traditional TS?\n2. Can you provide an intuitive explanation of Figure 1, the in-between uncertainty induced by HiLoFi?\n3. It might be helpful to plot the cumulative regret as well, which is a more standard metric of online learning, for the bandit MNIST problem.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper introduces a novel approach for online learning based on linearization and low-rank approximations of error covariance matrices, with favorable computational efficiency.\nIt provides a comprehensive evaluation of the proposed methods, and the experimental results seem intuitive.\nThe proposed framework can be useful for solving contextual bandit problems, which have many real-world applications such as the recommender system.  \n\nWeakness:\nWhile the paper establishes certain theoretical guarantees (Proposition 4.1), it is a little hard to gauge the tightness of the bound and the result does not seem to be very informative of the actual performance of the algorithm. \nIt looks like HiLoFi has a relatively high variance among the other methods in the recommender system task.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper and for your thoughtful questions.\n\nRegarding the theoretical bound in Proposition 4.1: while it is not tight, it is useful in practice for diagnosing model behavior. In particular, it helps assess whether the approximation error per step stabilizes over time. This behavior can be seen in Figure 7, where the surrogate error remains bounded throughout. Moreover, it shows that the two-step approximation incurs additive error, meaning that the errors from each approximation stage do not compound over time. We clarify this in the revised text.\n\n## Questions\n\n**R4.1.1 Why do you focus on uncertainty in predictions rather than uncertainty in parameters?**   \nA major drawback of many Bayesian neural network methods is that they make use of misspecified priors and likelihoods, often chosen for convenience [Knoblauch2022]. These choices can lead to degraded predictive performance [Wenzel2020] and make posterior sampling slower than non-Bayesian alternatives (e.g., deep ensembles). [Lakshminarayanan2017]\n\nBy contrast, focusing directly on uncertainty in predictions avoids the need to define priors over \"subjective probability distribution on parameters that may have no real-world interpretation\", as noted by [Holmes2023]. Furthermore, sampling from the posterior predictive is typically much lower-dimensional and a more tractable object for decision making.\n\nWe also observe improved performance over classical TS in deep neural networks, as demonstrated in a new experiment included in the revised version (See, R4.1.2 below for results).\n\nWe clarify these points in the revised text.\n\n\n**R4.1.2 How does this approach compare to the traditional TS?**\n\nIn traditional TS, one samples $\\hat{\\theta} \\sim p(\\theta | D_{1:t})$ and uses $\\hat{y}_{t+1} = f(\\hat{\\theta}, x\\_{t+1}, a)$ to make decisions. This requires the specification and sampling of a posterior over model parameters.\n\nIn our predictive Bayes (pBayes) approach, one samples $\\hat{y}\\_{t+1} \\sim p(y | x_{t+1}, \\theta_{t|t})$ directly and use methods like HiLoFi/LoLoFi/LRKF to update the belief state $\\theta\\_{t|t}$ (and also $\\Sigma\\_{t|t}$ for the methods we consider) .This decoupling enables faster and more stable exploration-exploitation behavior.\n\nWe clarify this distinction in the revised text, include pseudocode for the martingale-based predictive Bayes approach, and add a new experiment comparing against classical TS.\n\nThe pseudocode for our proposed predictive TS in a multiarmed contextual bandit problem is given below.\n\n```\n// Define posterior predictive parameterised by belief state b\n// and having inputs: the context ‘x’ and action ‘a’.\ndef p(· | x, a, b):\n    ...\n\nFor each a in actions:\n   // belief state:\n   // need not define a valid posterior or consider two moments only\n    b(t, a) = (mu(t, a), Sigma(t, a))\n\nFor all a in actions:\n    // sample from Bayesian posterior predictive  \n    ŷ(t, a) ~ p(· | x(t), a, b(t, a)) \n\na_next = argmax_a[ŷ(t, 1), ..., ŷ(t, A)]\n\n// frequentist update (e.g., HiLoFi)\nb(t+1, a_next) = update(b(t, a_next), y(t, a_next))\n```\n\nIn the table below, we show results for the MNIST contextual bandit task, comparing traditional TS against our pBayes approach. Note that HiLoFi does not admit a full posterior over parameters, so we report pBayes results only. For LoFi and Laplace methods, which support both TS and pBayes, we report both.\n\n| method         | cumulative reward | minutes | regret  |\n|----------------|-------------------|---------|---------|\n| HiLoFi-pBayes  | 31,167.7           | 8.43168 | 8,832.3  |\n| LoFi-ts        | 23,304.3           | 38.9005 | 16,695.7 |\n| LoFi-pBayes    | 23,184.5           | 4.76253 | 16,815.5 |\n| Laplace-ts     | 7,201.9            | 191.542 | 32,798.1 |\n| Laplace-pBayes | 13,922.3           | 1.36025 | 26,077.7 |\n\nIn summary: Sampling from the posterior, as required by TS, is dramatically slower, while offering little or no performance gain. For example, Laplace-TS takes 190 minutes vs. 1.4 minutes for pBayes, with much worse reward. Even LoFi-TS is nearly 10X slower than LoFi-pBayes with similar results. pBayes offers a superior speed-performance trade-off.\n\nNote that the  significant increase in speedup is because sampling, at every step, from a 10-dimensional multivariate Gaussian is much more computationally tractable than sampling from a D-dimensional multivariate Gaussian (even if the covariance structure is diagonal-plus-low-rank, as is the case for LoFi).\n\nWe add this new experiment with results in the revised text.\n\n**R4.2 Can you provide an intuitive explanation of Figure 1, the in-between uncertainty induced by HiLoFi?**  \nThank you for this suggestion.\n\nFigure 1 illustrates how explicitly modeling the last layer in full rank increases predictive uncertainty in regions without training data, where higher uncertainty is expected. Compared to fully low-rank methods (e.g., LRKF; see Figure 15 in the Appendix), HiLoFi forms more meaningful uncertainty estimates with fewer observations in these unseen regions.\n\nThis provides a better balance between expressiveness of uncertainty and computational cost, which is important for managing the exploration-exploitation trade-off in sequential decision making.\n\n**R4.3 It might be helpful to plot the cumulative regret as well, which is a more standard metric of online learning, for the bandit MNIST problem.**  \nThank you for this suggestion. In the revised version of the paper, we include cumulative regret plots for the Bandit MNIST problem.\n\n---\n\n[Knoblauch2022] Knoblauch, Jeremias, Jack Jewson, and Theodoros Damoulas. \"An optimization-centric view on Bayes' rule: Reviewing and generalizing variational inference.\" Journal of Machine Learning Research 23.132 (2022): 1-109.  \n[Wenzel2020] Wenzel, Florian, et al. \"How good is the bayes posterior in deep neural networks really?.\" arXiv preprint arXiv:2002.02405 (2020).  \n[Lakshminarayanan2017] Lakshminarayanan, Balaji, Alexander Pritzel, and Charles Blundell. \"Simple and scalable predictive uncertainty estimation using deep ensembles.\" Advances in neural information processing systems 30 (2017)  \n[Holmes2023] Holmes, Chris C., and Stephen G. Walker. \"Statistical inference with exchangeability and martingales.\" Philosophical Transactions of the Royal Society A 381.2247 (2023): 20220143."}]

Author rebuttal:

Meta-review: This paper primarily makes an algorithmic contribution towards the very relevant and practical problem of learning neural network models along with a notion of uncertainty. The performance evaluation of the proposed approach, based on extended Kalman filtering for a creatively set up model of a dynamically evolving neural network together with computationally friendly low-rank approximations, is chiefly empirical. The approach is geared especially towards enabling efficient randomization for posterior-sampling style algorithms for sequential decision making.

The initial reviews saw the referees raising several questions and requesting clarifications on various aspects. These included the necessity for Bayesian inference for learning predictive output distributions as oppposed to conventionally learning the posterior over the network parameters, comparison to other related work that uses point estimates in the context of sequential Bayesian learning, the motivation for using a novel random-walk model for the evolving network parameters, sensitivity of the algorithm to misspecification, explanations for terms used without adequate definition (e.g., 'replay buffer approaches'), more insight about 'martingale posteriors', and the comparison of the suggested approach with the vanilla version of Thompson sampling involving maintenance of uncertainty in parameter space. 

The authors and reviewers engaged in lengthy and patient discussions to clarify many of these points, which was noted positively by several reviewers, and for which I thank all the reviewers and authors. The discussion period also saw the authors include the results of additional experiments and ablations related to benchmarking prediction errors for architectures with more neural layers, and measuring the computational cost incurred by the proposed scheme. 

Overall, most of the reviewers lean positive on this paper to varying degrees, with one reviewer being (borderline) negative; however, many of the questions raised by the reviewers have been adequately addressed by the authors. After going through the paper and the discussions post review, I am inclined to recommend acceptance in view of the fact that the paper proposes a conceptually new approach, based on a linear dynamical systems view, towards prediction with uncertainty quantification for neural pipelines, and hope that these ideas can spur more innovation both on the theoretical front (refined studies of error bounds and their improvement) and on the practical front (more extensive empirical evaluation on real-world datasets) to perhaps result in a method competitive with the current state of the art.
Decision: Accept (poster)