Time-Uniform Confidence Spheres for Means of Random Vectors
Authors: Ben Chugg
Hongjian Wang
Aaditya Ramdas
Venue: Accepted by TMLR ()

Abstract: We study sequential mean estimation in $\mathbb{R}^d$. In particular, we derive time-uniform confidence spheres---\emph{confidence sphere sequences} (CSSs)---which contain the mean of random vectors with high probability simultaneously across all sample sizes. 
Our results include a dimension-free CSS for log-concave random vectors, a dimension-free CSS for sub-Gaussian random vectors, and 
CSSs for sub-$\psi$ random vectors (which includes sub-gamma, and sub-exponential distributions). Many of our results are optimal. For sub-Gaussian distributions we also provide a CSS which tracks a time-varying mean, generalizing Robbins' mixture approach to the multivariate setting.  Finally, we provide several CSSs for heavy-tailed random vectors (two moments only). Our bounds hold under a martingale assumption on the mean and do not require that the observations be iid. Our work is based on PAC-Bayesian theory and inspired by an approach of Catoni and Giulini.

Published in Transactions on Machine Learning Research (05/2025)
Time-Uniform Confidence Spheres for Means of Random Vectors
Ben Chugg
benchugg@eema eduu. kinwang@ema edu aramdas cramdas@cma.. edu
Hongjian Wang
Aaditya Ramdas
Departments of Statistics and Machine Learning
Carnegie Mellon Universily
Reviewed on OpenReview: https: // openreview. net/ forum? id= 2NSb3c.JE03
Abstract
We study sequential mean estimation in R. In particular, we derive time-uniform confidence spheres- confidence sphere sequences (CSSs) which contain the mean of random vectors with high probability simultancously across all sample sizes. Our results include a dimension- free CSS for log-concave random vectors, dimension-free CSS for sub-Gaussian random vectors, and CSSs for sub-t random vectors (which includes sub-gamma, Poissoissonn, and sub-exponential distributions). Many of our results are optimal. For sub-Gaussian distribu- tions we also provide CSS which tracks time-varying mean, generalizing Robbins' mixture approach to the multivariate setting. Finally, we provide several CSSs for heavy-tailed ran- dom vectors (two moments only). Our bounds hold under a martingale assumption on the mean and do not require that the observations be iid. Our work is based on PAC-Bayesian theory and inspired by an approach of Catoni and Giulini.
1 Introduction
We consider the classical problem of estimating the mean of random vectors in nonparametric settings. Perhaps unlike traditional approaches however, we would like to perform this task sequentially. That is, we are interested providing estimates of the mean which hold uniformly across time as more data arrives. To formalize, let (Xt) be a stream iid random vectors in X' Rd with mean j drawn from some unknown distribution P. Our goal is construct non-trivial sequence of sets, (Ci) C₁ Rdd such that
P1:31:pE P C.) > a
(1)
for some predetermined E (0,1). In R1, such a sequence is often called confidence sequence (CS). We will use the more general term confidence sphere sequence (CSS) to highlight that we are working in higher dimensions, and because our sets C, are spherical as opposed to, say, ellipsoidal. CSs and CSSs are contradistinction to confidence intervals (CIs) the latter hold only at fixed times t = n determined prior receiving any samples, while the former hold simultaneously at all stopping times. Consoquently, they are often described time-uniform or as anytime-valid, Importantly, CSs and CSSs obviate the need to deploy union bounds to gain uniformity over the sample size. This is attractive for tasks in which data continuously monitored during collection and which may call for data-dependent stopping times, two properties disallowed by fixed-time constructions such as confidence intervals (where it is known as p-hacking).
The study of CSs was pioneered by Darling, Robbins, Siegmund, and Lai the decade from 1967-76 (Darling and Robbins, 1967; Lai, 1976). While further inquiry laid somewhat dormant for several decades afterwards, they have recently regained interest due to novel mathematical techniques and applicability to sequential decision-makee making. Indeed, CSs are used by several companies for A/B testing and adaptive experimentation. We refer the reader to Howard et al. (2021); Waudby-Smith and Ramdas (2023) for more history and modern work on this topic.
F..g. see Adobe (2023), Evidently (2023), and Netflix (Lindon et al., 2022).

---

Published in Transactions on Machine Learning Research (05/2025)
Thus far, most work on CSs for the mean of random observations has been in the scalar setting (with some exceptions discussed below). However, estimating higher-dimensional means arises naturally in wide variety of tasks in statistics and machine learning, including multi-armed bandits (Dani et al., 2008; Abbasi- Yadkori et al., 2011), regression (Lai and Wei, 1982; Vidaurre ct al., 2013), covariance estimation (Kuchibhotla and Chakrabortly, 2022), stochastic optimization (Feldman et al., 2017); and anomaly detection (Rousseeuw and Hubert, 2018), to name few. Advances time-uniform confidence regions for estimators can therefore translate to sequentially-valid versions of such tasks.
In this work we construct CSSs by means of PAC-Bayesian analysis (introduced below), inspired by the original work of Catoni and Giulini (2017; 2018) which is in the fixed-time setting. We combine their insights with recent work which provides a general framework for understanding how and when PAC-Bayesian bounds can be made time-uniform (Chugg et al., 2023). The resulting synthesis yields a general method for constructing CSSs under a varioty of distributional assumptions.
A concise summary of our results is given in Table 1 and their relationship to the existing literature is explored in Table? 2. All bounds are closed-form and easily computable. In more detail, our contributions are:
Sub- Bab-Gaussian bounds. Theorem 2.2 provides a CSS for conditionally sub-Gaussian distributions. The width of the CSS depends on the trace and norm of the covariance matrices instead of the dimension of the ambient. space (d). Such "dimension-free" bounds are desirable when the data are expected to lie on some low-dimensional manifold, i.., when the effective dimension is less than d. Theorem 2.3 leverages Theorem 2.2 to provide a CSS whose width shrinks at the optimal itcrated- logarithu rate. Theorem 2.16 provides a CSS when the mean changes with time, generalizing a result of Robbins (1970) to the multivariate setting. For technical reasons to be discussed later, this final result is not dimension-free.
2. Log-concave bounds. Theorem 2.8 provides a dimension-free CSS for distributions with log- concave densities (and more generally for distributions with bounded 1-Orlicz norm) which include Laplace, logistic, Dirichlet, gamma, and beta distributions. This extends recent result of Zhiv- otovskiy (2024). Theorem 2.9 then extends Theorem 2.8 to provide bound which shrinks at an iterated-lgaarithm rate.
3. Sub-1 bounds. While sub-Gaussianity and log-concavity are particularly popular distributional classes, there are many other light-tailed conditions one can consider. Theorem 2.12 provides a CSS for conditionally sub-1 random vectors for super-Gaussian vi-functions (which includes sub- Poisson, sub-exponential, and sub-gamma distributions). A bound for general eiffnnctons is given by Theorem A.3. The downside of considering such a general class is that these CSSs are not dimension-free. Theorems 2.14 and 2.15 deploy Theorem 2.12 obtain iterated-logarithm rates for sub-gamma and sub-exponential distributions.
4. Heavy-tailed bounds. We provide several results for hcavy-tailed distributions under only second moment assumption. Theorems 3.2 and 3.5 provide two semi-empirical CSSs (in the sense of being adaptive to the observed values). Theorem 3.5 is lighter but holds only under conditional symmetry assumption. Theorem 3.7 provides a time-uniform extension of the dimension-free Catoni- Giulini estimator (Catoni and Giulini, 2018) and Theorem 3.8 provides an itorated-logarithm version of Theorem 3.7. All bounds stated in this section are dimension-free.
1.1 Related work
Given its centrality to many statistical procedures, estimating the mean of random vectors is well studied topic. For sub-Gaussian random vectors in the fixed-time setting, state-of thett--rtttet concentration comes from Hsu ct al. (2012). Our result has the same asymptotics (it is off by Hsu et al.'s result by an non- leading additive factor), but is time-uniform and handles martingaleedepeeddnne. We also improve on more classical bounds for isotropic sub- Gaussiasn random vectors obtained via covering arguments (e.g., Rigollet and Hütter, 2023, Thcorem 1.19). Meanwhile, for heavy-tailed distributions, it known that the sample mean (and weighted variants) have suboptimal performance (Catoni, 2012). This led to the development of alternatives such median-of-means (Lugosi and Mendelson, 2019b; Minsker, 2015) and threshold-based
2

---

Published in Transactions on Machine Learning Research (05/2025)
Result
Dim
Condition
Dim-free&
Martingale? !
CF
LILS
n.
opt
Thm. E.2
||llll bounded
Thm. 2.2
d >
E--su--Gaussaan
Cor. 2.5
d a
E-sub-Gaussian
Thm. 2.3
>
T-sub-Gaussian
Thm. 2.16
d j
dy-uu-Gaussiann
Thm. 2.8
d 3
Log-comcave/fnite finite +n-norm
Thm.
Log-ooncave/fniiee 41-norm
Cor. A.1
d x
Log-concave/ finite -n-norm
Thm. 2,12, A.3
d >
Σi-sub-e
Thm. 2.14
3
E-sub-gamma
Thm. 2.15
d >
E-sub-exponential
Cor. 2.5
d >
E-sub-exponential
Thm.
1
B|] & v2
Cor. 3.3, 3.4
d
B[x v2
Thm. 3.5
d d>l
||||X||| & o², sym.
Thm. d31
Thm. 3.8 d=1
Table I: A roadmap of the results in this work. 42 refers to the 1-Orlicz norm; see Section 2.2. "sym." stands for conditionally symmetric, meaning that the observations obey X, - ~ -(X,- "Dim-free" stands for dimension-fres and "martingale" for martingale-eppeddence (i.e., Assumption 2). "CF" stands for closed-form form, meaning the bound does not require numerical methods solve. "LIL" refers sequential bound with iterated logarithm rates and "n opt" refers to bound that are optimized for particular sample size
estimators (Catoni and Giulini, 2018), the latter of which we will make time-uniform in Theorem 3.7. We refer to Lugosi and Mendelson (2019a) for a survey fixed-time mean estimation under heavy tails.
In the sequential setting, the theory of "self-normalized processes" (de la Peña et al., 2004; 2009) has been leveraged to give anytime-valid confidence ellipsoids under nub-Gaussian assumptions (Abbasi-Yadkori et al., 2011; Faury et al., 2020). This line of work is focused on bounding the self-normalized quantity |/2=1/ for S, = Ei= c,X, where e, is the scalar noise of an online regression model, X, are multivariate observations, and 1 variance process. This setting is quite distinet from our own, which seeks non-self- normalized bounds and does not have both observations and noise components. Section 2.5 provides brief discussion of how some of our bounds can be adapted to anisotropic distributions. This yields bounds in the Mahalanobis norm with respect to the variance but these results remain distinct from self nelmaloodl bounds. Whitehouse et al. (2023) give a general treatment of time-umiform self-normalized bounds which extends beyond regression but it remains incomparable to our own work. Morcover, the results of Abbasi- Yadkori et al. (2011); Whitehouse et al. (2023) only apply to sufficiently light-tailed distributions, and not the more general heavy-tailed settings we consider in Section 3.
Meanwhile, Manole and Ramdas (2023) provide anytime bounds on the mean of random vectors using reverse submartingales. Their bounds achieve the optimal iterated-logarithm rate of Vlog log(t)/t (Darling and Robbins, 1967). Their results are most comparable our results for isotropic sub-exponential distributions, they do not hold under heavy tails and are not dimensioon-nndeeeddeer slightly more general distributional assumptions, as Manole and Ramdas (2023) work only with iid data. We will further discuss the relation to their work in Section 2, but suffice it to say here that we can employ a geometric "stitching method" (a common tool in sequential analysis), yielding a bound which matches this optimal rate and has smaller constants. As for anytime bounds under heavy-tails, Wang and Ramdas (2023) provide CSs for scalar random variables which hold under a finite k-tth moment assumption for (1,2).
We are also able to handle
Much closer to the spirit our work are the papers of Zhivotovskiy (2024), Nakakita et al. (2024), and Giulini (2018). All three use the same variational principle that is at the heart of our method to study the concentration singular values of light-tailed random matrices (Zhivotovskiy, 2024), the means of heavy- tailed random matrices (Nakakita et al., 2024), and to estimate the Gram operator in Hilbert spaces (Giulini,
3

---

Published in Transactions on Machine Learning Research (05/2025)
Condition
Our result
Comparison
[A]
C
dd]
Notes
sub- Gaussian
Cor, 2.5
Hsu et al. (2012), Thm.
Off by a factor & 2
sub- Gaussian
Cor. 2.5
Rigollet and Hütter (2023), Thm. 1.19
/
sub- Gaussian
'Thm. 2,16
Waudby-Smith et al. (2024), Thm. 2.2
Non-asymp, holds in Rd
log-coneave
Cor. A.1
Zhivotavskly (2024); Prop. 3
sub-t
Thm. 2.12
Manole and Ramdas (2023), Cor. 23
Handles anisotropy
sub-exponential
Cor. A.1
Manrer and Pontil (2021), Prop. 7
sub-exponential
Thm. 2.15
Manole and Ramdas (2023), Sec. 4.7
finite 2nd moment
Thm. 3.7
Catoni and Giulini (2018), Prop. 2.1
finite 2nd moment
Thm. 3.7
Lugosi and Mendelson (2019b), TThm 1
Not sub-Gaussian, (*)
finite 2nd moment
Thm. 3.7
Minsker (2015), Thm. 3.1
Table 2: Comparison of our results with relevant bounds in the literature. More commentary on the rela- tionship is provided in the text. Boxed letters indicated that our result improves over the existing result by adding [A] valieeieevlllidiyy improving the [C]onstants, or weakening the [Djependence assumptions among the obscrvations. (*) indicates that the cstimators are built under different assumptions: we assume a bound on the raw second moment while they assume a bound on the centered second moment.
2018). While the underlying ierspective is similar to our own, our goals are distinct. Moreover, these authors work in the fixed-time setting and none handle martingale dependence. Despite these differences, however, we believe that these three papers along with our own suggest that the variational approach to concentration is a promising research avenue.
Finally, recent work by Duchi and Haque (2024) shows that any fixed-time estimator can be converted into a sequential estimator with loss of an iterated logarithm factor (i.e., O(log log ()) via "doubling trick." Their construction employs a union bound over fixed-time estimators applied at times
2 l 1. At times j E (2*, 2 one continues to use the estimator for time 2* This is an insightful theoretical construction for obtaining optimal rates, and we compare our results with their bound in Sections 2.1 and 3.3. However, we note that it does have drawbacks. First, it is stated only for iid data. Second, it is not sequential in the practical sense that a data analyst would like. Indeed, if data collection stops at time t = 2 -1,, then observations. The estimators proposed here can be updated after every time step, thus using all available data. This results in bounds that are often lighter than fixed-time bounds augmented with the doubling trick (see Figures and 2).
we must discard 2 -
1.2 Background and approach
Let us introduce some technical tools. A (forward) filtration F = (Fe) is a sequence of o-fields such that F. C Fe+1, t > 1. In this work we always take F, = (X Xx), the o-field generated by the first observations. A stochastic process S = (Si) adapted to (J.) if St is F, mcasurable for all (meaning that S, depends on X1,-.. X,...., ,x),, and prediclable if S, is Fi-1 measurable for all 1 (meaning that S, depends only XI,...,Xe..
A P-martingale is integrable stochastic process M = (Me)ca1 that is adapted to F, such that Ep[M++ [F.] M, for all t. If '=' is replaced with '<', then M is a P-supermartingall.
Our results rely on PAC-Bayesian theory which has emerged as successful method to bound the generaliza- tion gap of randomized predictors in statistical learning (Shawe- Taylor and Williamson, 1997; McAllester, 1998). As the name suggests, PAC-Bayesian bounds employ the "probably approximately correct" (PAC) learning framework of Valiant (1984) but addressed from a Bayesian perspective. Roughly speaking, rather than bounding the worst case risk, PAC-Bayesian bounds place with prior over the parameter space θ, and provide uniform guarantees over all "posterior" distributions. Instead of containing measure of the com- plexity of θ, the bounds involve divergence term between the prior and posterior. We refer the unfamiliar reader to Guedj (2019) and Alquier (2024) for an introduction to such bounds and their applications.
For our purposes, the important feature of PAC-Bayesian bounds is the uniformity over posterior distribu- tions. The insight of Catoni and Giulini (2018) is to translate this uniformity of distributions into a bound on {0, c) across all i sd-1, where c is the error of the estimator. Such a bound translates immediately into confidence sphere. Recently, uniformity over posteriors was extended uniformity over posteriors and time by Chugg et al. (2023).
4

---

Published in Transactions on Machine Learning Research (05/2025)
Proposition 1.1 (Corollary of Theorem 4, Chugg et al., 2023). For each 0 E θ assume that Q(0) (Qx(0)):31 is noneegative supernartingale with inilial value 1. Consider a prior distribulion v over O (chosen before seeing the data). Then, with probability at least 1 - a, we have that simultaneously for all times t > and posteriors p E (O)),
/ log (c(0)p(d)) < DKL(elle) + log(1/a).
(2)
Hero, (O) is the set of distributions over e and (-I(-II-) is the KL divergence, which we recall is defined p
as DKL. (pllv) le log de dp p v and oo otherwisc. The uniformity over time and postcriors refers
to the form P(Vt, Vp. So log (()))) < DKL(Pll) + log(1/a)) > a of the above bound, where the quantifiers are inside the probability.
At its core, our approach involves judicious selection of θ Q, family of posteriors {p} and then applying Gaussian distributions over the
Proposition 1.1. We will consider either uniform, truncated Gaussian, parameter space O, which we will take to be either subset of g == {ar E Rd ||=||| = 1}, Bd := {> E Rd ||||| & 1), or Rd. The choice of Ô is driven by the availability of appropriate supermartingales over O We will typically choose supermartingales Qx(0) to be functions of Eige (0, f((,)) μ)) for some functions fi, with the aim of obtaining bounds on supaesa-1 (0, - = (f.().). - +)ll which will furnish a CSS.
For example, for iid X1, X2.... which are Ganssinnn the process defined by M. I1g exp(A(0, X; - n4 - (0, } for any À > 0 is a nonnegative supermartingale for all 0 E R4. Let Po be Gaussian with mean 0 and covariance La for some scalar 3 > 0. Applying Proposition 1.1 to (M)()) with θ= Rdd prior v= Po and posteriors Pa for all 0 E gdd11, we obtain that P((v > 1, E $ Eis, M00 -) < t (0.E0) (0. 8/2+ +8/2+log(1/o)) 3 1- a, where we're we've calculated (pollellv) = 8/2. Us- ing that supges" (0, X; - -1) = |X - sill and noting that Ep (0, Σd) (0. Σd) - Tr(E)/3 < | TB(E./B, find that with probability 1 - a, for all t 1,
| Σ x, m| 1ett
A 2
E Tr(E) +
3/2 + log(1/a)
<
(3)
1
The parameters 8, > 0 may then be chosen to optimize the width of the bound. Subsequent sections will expand on this example, relaxing both the distributional and dependence assumptions among the observa- tions, and introducing various methods to ensure the width of the bound shrinks to zero over time (either via stitching or predictable plug-ins). Throughout, the norm ||-Il should be taken to be the (-norm l|:112 when applied to vectors, and the operator norm when applied to matrices.
1.3 Assumptions
The most common assumption in the literature is that the data are independently and identically distributed (iid). This the case in most prior work on estimating means (cf. Catoni and Giulini, 2017; Lugosi and Mendelson, 2019b; Devroye et al., 2016; Joly et al., 2017).
Assumption 1. X1, X2,.. are iid with mean μ.
In this work, are able to weaken this condition. We enforce only that the data stream has a constant conditional mean μ. This allows for more "adversarial" distributions, and is particularly relevant in several bandit and online learning settings in which the iid assumption does not hold.
Assumption 2. X2,.. have constant conditional mean [[X,F=-]] = μ.
Of course, Assumption implies Assumption 2. Assumption 2 is common in work on CSs, lypically because they rely on (super) martingales which naturally enable such flexibility. We will often refer to Assumption 2 as martingale-dependenae While Abbasi- Yadkori et al. (2011) and Whitchouse et al. (2023) also work under more general conditions than iid data, we are- as far as we are aware-tlle first do so in multivariate, heavy-tailed settings.
5

---

Published in Transactions on Machine Learning Research (05/2025)
2 Light-tailed random vectors
2.1 Sub-Gaussian bounds
We say that X is E-ssub-Gaussian for some Fi-meaurrble PSD matrix E, if
Eylexp X, - 14) (w) (.0) 1 for all 0 E Rd and X E R,
(4)
where & (A) = 22/2 and Σ is PSD. The subscript "N" refers to the tail condition of a normal distribution and can be contrasted with other tail conditions investigated in Section 2.3. Unlike typical notions of sub- Gaussianity, (4) allows (Ex) to be (Fi)-adapled sequence, not simply a predictable sequence. This allows Mg to depend, for instance, on X.. E.g., if [x; [ oo, then may take E; = $ (Z pll2+ Eig, [[|| -1 (see Lemma 3 part (f) in Howard al. 2020). This example cannot be handled if Mg must be measuraae...l..
We note that many authors impose isotropic conditions on the distribution when defining sub- uub-Gaussianity meaning that they take Σ, = of of.a. la. However, allowing for anisotropy will enable us to give several dimension- free bounds that will depend on D, instead of d. As discussed in the introduction, such results are desirable when the data have low intrinsic dimension compared to the dimension of the ambicnt space. In Appendix A.1 we give the resulting bound when the distribution isotropic (i.e., E, = of la).
Remark 2.1. The inequality in (4) is often written as holding for all 0 g instead of 0 E Rd. The statements arc, of course, equivalent (though they cease to be for different ei-functions; see Section 2.3) but we wrote (4) as we did to highlight that we can take parameter space θ = Hd. To elaborate, (4) naturally defines a supermartingale for each 0 E Rdd When applying Proposition 1.1, we can thus use Gaussians as the prior and posterior distributions as opposed to restricting ourselves to uniform distributions or truncated Gaussians as in Sections 2.2 and 2.3.
Let P9 be a Gaussian with mcan 1) and covariance B- for some real B B>< 0. The process defined by -I exp(>; A (0, X; - uu) - (>:) E,0)} is a nonnegative P-supermartingale for all 0 E H by (4). Applying Proposition 1.1 to this family of processes with prior po and posteriors pa for & s one obtains the following result. The details may be found in Appendix C.I.
Theorem 2.2. Let (Xi)1z1 be conditionally (Et)- (Zi)-sub-Gaussian Gaussian and salisfy Assumplion 2. Let (At) be predictable sequence in (0, oc) and for B > O. Then, with probability - ax, sirealtaneously for all 2 1,
Aig Eisrdi
/
Eigr (N + +B-1 Tr(,,) + 3/2 + log(1/a)
1
Eigedi d
Let us turn straightaway to the question of how to choose /3 and d above. If sup, |Ea|l < || < xo and sup, Tr(E,) & Tr(2) < xo, then consider taking
2 2 (T) log(1/a) and A = V ff( log(t +1
B
(5)
Σ
where fz(E)= = ||||| + TT( Using that Eig (ogg( + 1))-1/2 = vt/log(t) and (igr (oclloo((++)))))))) + 1))
x
log log(t), we see that the width of the CSS in Theorem 2.2 is
δ ( (TT)) + |Σ] log(1 (og()/)) logt
(6)
where Ô hides itcrated logarithm factors. If sup, Eell or sup, Tr(E,) are unbounded, then we cannot guaran- tee that the width will shrink to zero. We can obtain iterated logarithm rates (iee. log log instead of log 1) in (6) with a technique known as stitching (Howard et al., 2021). This is similar to the doubling technique of Duchi and Haque (2024), but relics on applying Theorem 2.2 in each epoch, thus resulting an estimator which is updatod at every timestep, and not just at times 2t. Details may be found in Appendix B. Note that Theorem 2.3 posits that Σ, Σ for all f, thus assuming that Σ is non-random.
6

---

Published in Transactions on Machine Learning Research (05/2025)
10
Theaem
Thooran 2
Theorem 2
109
Han nl, w/ dombling, TTx(2)) -Tr)
Han w/ dombling
Hsu et al, w/ doubling, TTx(2)) =TT(2))//
CSS width
or W/ union bound
CSS with
Hau et al. w/ dombling, Tr(22) =TTr(E)/110
Hsu et al. w/ doubling, T=(E") se
10
10-1
0
20000 40000
60000
80000
100000
20000
40000
60000
80000
100000
Comparison of Theorem 2.2 and its stitched version, Theorem 2.3, against the results of Hsu et al. (2012). The latter is made time-uniform two ways: by a union bound (dotted orange line) and by the doubling technique of Duchi and Haque (2024) (dotted purple). We begin the plotting the width t= = 150 for scale purposes. We fix ||||= 1 and take Tr(E) 5. Right: A comparison of estimators with iterated logarithm rates. We plot Theorem 2.3 against the bound of Hsu et al. given iterated logarithm rates via Duchi and Haque for various ratios of Tr(E?) to Tr(E). As Tr(E?) shrinks Theorem 2.3 starts to be dominated by the bound of Hsu et al.. Simulation details can be found in Appendix D.
Figure Left:
Theorem 2.3. Let (Xt)131 be conditionally E-sub-Gaussian Gaussian and satisfy Assumption 2. Then, with proba- bility 1 a, simultancously for all > 1,
Tr + 1.682
[=]](oo((..65/a) + 2 log(log2(1) +1)
7
Σ X; SEL
1
< 1.21
t
t
Figure plots the width of the CSSs Theorems 2.2 and 2.3. We compare our results to the stale-of-the-art fixed-time result of Hsu al. (2012) (described below; see (9)), which we make time-uniform in two ways: via naive union bound, and by the doubling technique of Duchi and Haque (2024). As expected, naive union bound is outperformed by all other bounds. Theorem 2.3 uniformly dominates Theorem 2.2 at all time steps, Neither Hsu et al. with doubling nor Theorem 2.3 uniformly dominate the other, except for small values /Tr(),, in which case the former begins to dominate. Note however that Tr(>²) > 2 Tr())[>]] (soe Lemma C.1 in Appendix C.1), so that values of
I+Vd close to zero require large dimension.
Remark 2.4. A dissatisfying aspect of Theorem 2.2 result is that. is fixed while Σ, can vary. Ideally, one could allow 8 to be a function of t and take 3r x v Tr(,,). In fact, such choice is possible if Σ, is predictable-the general version of Proposition 1.1 stated in Chugg et al. (2023) allows us to choose predictable posteriors. However, since the covariance of the prior is fixed, this stralegy results in factor of d in the KT-ddvergence. Our bounds are therefore most useful when upper bounds on both Tr(E,) and ||E|] across all are known, in which case B and D can be optimized as above.
Fixed-time optimization. Next, let us instantiate Theorem 2.2 optimized for a specific time t = n with Σ, Σ for all Some elementary calculus suggests that setting
8 ++20 (oglo/((/a) n (T + +|IE|)
2 (Tr(E) log(1/0)
=
8:
results in the optimal width of the boundary. This gives:
Corollary 2.5. Let (X1)211 be E-sub- Ssub-Gaussian and satisfy Assumption 2. Fix some n E N. Then, with
probability ax simullaneouslyy for all 1. > 1,
Σ x, 1=1
< ( 1
+ vn
(VTHZ)) + /2 1 11g()
(8)
2t
7

---

Published in Transactions on Machine Learning Research (05/2025)
Corollary 2.5 may strike the reader as somewhat odd at first glance. The bound is optimized for particular sample size but remains valid at all times due to the time-uniformity of Theorem 2.2. However, the bound is tightest at & = n and the width does not to go zero as t + oc. Thus while it is time-uniform bound, it is most useful at sample sizes that are close to n. It might be compared to Freodman-style incqualities (Freedman; 1975) (which hold for all & n), or de la Pêna style inequalities (de Peña, 1999) (which hold for all t z but also do not shrink to zero).
Hsu et al. (2012) prove that for iid Gaussian random vectors ,,, Xn, with probability 1 1- a,
トリ H X₁ 2 < m
Tr(E) + 2 log(1/a) + 2r/T((2>)))))))) log(1/a)
n
Instantiating Corollary 2.5 at t = n. we see that the width of (8) differs from (9) by replacing /2 log(1/a) with 2 Tr(x3) log(1/a) (this is clear after writing v TT((E) + (21 =
V (r(EE) + 2 | log log(1/o) + 2 [||| log(1/o))- The bound in (8) is therefore somewhat slightly looser than (9) at 1 = n, but the bounds differ by at most a factor of two as demonstrated by the following lemma. Despite this looseness, we emphasize that our bound holds under martingale dependence, is sequential, and performs better than a sequentialized version of (9) in many regimes (sce Figure 1).
Lemma 2.6. Let Wn, be the right hand side of (8) at = n. and let Hn be the right hand side of (9). Then W, 2.
Proof. We have vnW, = (T((E) + (1 < 2 max (T(E))))...))))))))))())) (2]2)]og((/)) Further, note that Vūlln / /I((2) 2||iا|| log(L/a) + 2/ log)/// v /Tr + 2 log (1/)). Using that max Vaa, vbJ & +b completes the argument.
When == ,²1, = Corollary 2.5 improves the constants in a classical concentration result. for sub-Gaussian + 20 /lg((///) Vn
random vectors, which states that, with probability 1 1- a, || Σ, X; - All < (Rigollet and Hütter, 2023, Theorem 1.19). We also remark that Jin et al. (2019) study concentration Caa-ssuub--auuiaanityyy.. When their result is translated into our
under the weaker assumption of so-called setting, one obtains that with probability 1 - a, 1/4 Σ, X, All = O(a / dd (log(2//)//n). This is worse than Corollary 2.5, though in general the two bounds are incomparable, holding for different assumptions.
2.2 Log-concave distributions and finite Orlicz norm
If P is a distribution whose density f(x) can be written as f(x) = exp()(x)) for some concave function & then we say that is a log-concave distribution. Many popular distributions are log-concave: the Gaussian, Laplace, logistic, uniform, Dirichlet, gamma, and beta distributions being several examples. Here we extend a recent observation of Zhivotovskiy (2024) and demonstrate that all log-coneave distributions admit a dimension-free CSS.
In fact, we deal with distributions slightly more general than log- concave distributions. We consider sequences of obscrvations (Xt)121 with a finite conditional -0-Orlicz norm:
( X, Ep(X,| < (8,
for all e R
(10)
where we recall that for a scalar-valued random variable Y,
||l|,, = inf {e 0:>0:
2
In (10), Σ is assumed to be PSD and deterministic (unlike the mab--aasssian case). If is log-concave, then Adamezak et al. (2010, Lemma 2.3) demonstrates that it obeys (10). 2 For Gaussians, the constant C= 2 (in fact, C 2 for all symmetric distributions, see Adamezak et al. 2010). Sub-exponential distributions
Thhey state the result for all E gd-1, but this easily seen to equivalent to (10).
8

---

Published in Transactions on Machine Learning Research (05/2025)
also satisfy (10). Indeed, (10) is another way to define sub-exponential distributions, and the results in this section thus provide dimension-free CSSs for such distributions. However, for isolropic sub-exponential distributions, the results are sub-optimal compared to those in the next section (Theorem 2.15 in particular). We will comment more on the relationship in Section 2.3.
Unlike sub-Gaussian distributions, the log-concave condition does not immediately imply supermartingale which we can deploy in Proposition 1.1. Instead we consider a process which has the form II (0) log E exp (f)} which is martingale whenever log log ((exp((,(()) is finite. In order to bound this log-mgf term, we appeal to the following lemma, which is standard but proved explicitly by Zhivotovskiy (2024, Lemma 2) (sce also Howard et al. 2020, Proposition 1).
Lemma 2.7. For scalar random variable Y such that ||Y - -YYl,, < 00, we have
Eexp(A(Y -YY) < exp (4221141--10) SAPII--YYIE EYIle.): for all [A|E 2 -YYI
We deploy Lemma 2.7 with Y (0). It's tempting to consider g:(0) - (0, u) and to mimic the approach used in the sub-Caussian case. Unfortunately, this strategy breaks down because (8 X2 -1))) -1)ll may be arbitrarily large for certain choices of 0, thus rendering Temma 2.7 inapplicable for any X. Therefore, we cannot use Gaussian distributions in Proposition 1.1 as was done in the sub-Gaussian case. Instead, following an approach used by Zhivotovskiy (2024) in the case of random matrices, we use a truncated Gaussian with a well-chosen radius. This, combined with a clever choice of g)))) allows us to provide the following dimension-free bound. The details may be found in Appendix C.I. Let us define the function (w) VTr(E)u + /V/EI for u > 0.
Theorem 2.8. Let (Xt)1a1 satisfy (10) and Assumption 2. Let (De) be predictable sequence taking volues in (0, 1). Then with probability 1 a, simultaneously for all t to 1,
Eige A.X;
2Chr
X3 (4Chs(lo((2aa)
Eigid de
14
(11)
Note that while log-concavity implies that some such C exists, the bounds are unusable without knowledge of C. This similar to needing to know the uub-Gaussian constant or variance bound order to be able to construct finite-sappl--valle valid confidence intervals.
Noting that lxx(() is monotone, our bound recovers the one by Zhivotovskiy (2024) at t= with A 1: 2Chs(1)) + 4Chs (log(//a)) & 6Chh5(ogg2//o (2/()))gg(())))))) assuming & 2e-1, Further, following arguments in that work, this can be seen to be optimal in terms of dependence on log(1/a), Tr(),, and ||]] Theorem 2.8 is also related to Maurer and Pontil (2021, Proposition 7.1), which uses entropy methods to prove that 1 E, X2 - ~ Xe||||X||ll
Ilallo, (/Tog((/0)// for iid X,...., Xn, One can show that ||||X|a|lo, VTr(E), so this bound is of the same order as ours, the width of which we now analyze.
Consider
by (Ux)
hy ()t +1)
where ua :- log(2/a). a < -1, then Az(ua)hs(1)
(vTr(E)ua + Ua
Tr(E) [Σ|]
= =Tr(E) + (ua + (a)) Tr (Σ) Σ + ua Σ
< Tr(E) 3ua TT(E) Σ||
where the inequality follows from un > 1 and Tr(E) > |Σ|| With these choices, the CSS in Theorem 2.8 has width
ō (cv (V (T<E))
logt
+ u. T+E)EE
(12)
9

---

Published in Transactions on Machine Learning Research (05/2025)
where C is the log-concave constant. Here we've once again used the fact that (igg( 1))- x log logt 1/2 x vt log/. f. As in the sub-Gaussian case, we can also use stitching to provide a bound which shrinks at the optimal iterated logarithm rate. The details may be found in Appendix B.
and Eige (v Vlg((i + 1))-1/²
Theorem 2.9. Let (X))ea1 satisfy (10) and Assumption 2. For any a E (0,1) and t 3 1, set ra(() == 2 llg((og22))) + +) 1)0g3/333//) Then, with probability l-a, simultaneously for all t such thatt > ( (1)
Eise ApXi Σ Eisld Ai
< 6.730 hy: (1)))))r(r)()) (1)) 6.73C| Tr(E) + (1) T+())
11
(13)
t
2.3 Sub-u/ distributions
Other light-tailed conditions on random vectors can be captured by assuming the log- OGF is bounded by some CGF-like function. More precisely, we assume that there exists a function ab : [0, Amax) - R for some Amax E (0,00) such that
Ep - - "A Eu))-r- <1 for all v E gg-1
(14)
and all X E [0, Amax)) Condition (14) is called a sub-i process by Howard et al. (2020) and Whitehouse al. (2023). As in the sub-Gaussian case, assumee that M, is PSD and Fi-messurable (ie., (2x) is (Fo)adapted not only predictable). Different choices of &o recover common distributions (terminology is borrowed from Howard et al. (2020); we take 1/0=00);
1. v ;= 22/2 for X E [0, Amax) results in a sub-exponential distribution (sub-Gaussies if Amax = 00). In this case we say that (Xt) is (Ee, emaxxssub--expooennal.
2r 2. (r),o(A) 2T-cx for c E R and Amax 1/max(c, 0} results in a sub-gamma distribution (in the sense that wG.. is an upper bound on the CGF of a gamma random variable). In this case we say that (Xt) is (Ee, -ubaaaaa.
3. (A),(()) = (ec) - cλ - 1)/c² for c e R and Amax = oo results in a sub-Poisson distribution (in the sense that vp..c is the CGF of a centered unit-rate Poisson random variable). In this case we say that (Xt) is (E,, subs-Possoo....
(AE,c(A) = (-log(1 - ed) ex)/c² for E R where Amax 1/maxfe, 0} results in a sub-neg- exponential distribution (WE,e the CGF of a centered unit-rate negalive-exponential random variable). 3 In this case say that (Xt) is
In general, to indicate that (X₂) satisfies (14) for some fi-functin,, we will say it is (E,)-sub-bh. The five y f-functions are all (upper bounds on) the CGF of various random variables. Further, all are (a) twice differ- entiable and (b) obey (0) = lim (x(x) = O. We will thus call any function which satisfies (a) and (b) CGF-like. In what follows we will mainly focus on CGF-like functions that are Super-Gaussion (Whitehouse et al., 2023). Formally, we say v6 is super-Gaussian Gaussian if X (X)/22 is nondecreasing. Informally, this implies that sb grows at least as quickly as the CGF of standard normal random variable. All of the ul-functions enumerated above are super-Gaussin
When restricting our attention super-Gaussian CGF-like functions, (14) holds for all v in the unit ball Bd as opposed only the unit sphere gd-1 see Lemma 2.10. This allows us to use uniform distributions over the ball in Proposition 1.1. For 16 functions that are not super- Gaussian, we can instead use the von Mises-Fisher distribution (Mardia et al., 2000) over the sphere. This, however, results in bounds with slightly worse dimension dependence and worse constants. Since most &b functions of interest are super-Ga the result for non-super- Gaussiin va is given in the Appendix; see Theorem A.3.
Lemma 2.10. Let (Xt) be sub)-sub-u where vb is super- Gaussian Then (14) holds for all E Bd.
Many authors call WEg the CGF of an exponential distribution (Howard al., 2020; 2021; Whitehouse et al., 2023), but want to reserve the term sub-exponential for vy with finite Amax- Hence we use the term negaaiieeexpomenttal ial instead.
10

---

Published in Transactions on Machine Learning Research (05/2025)
Proof. Let v be super-Gaussinn Observe that for any 0 E B
(A)
X
therefore (>|101)) < ([)]) Consequently, letting 0 0/100| St-1,
exp(A< X; - n1) - (A.) |,0)} (xpp\>11001 Xx; -1) - -0)-()))) [0,
< (o0p)):10|((00.2 - - (0-A011101) E,
Since > A Amax, follows that (0) is upper bounded by
Mc(0) II exp μ (0 E,0)).
which defines nonnegative supermartingale by (14), proving the claim.
Remark 2.11. While (14) superficially resembles the sub- Gaussian condition (4) for & = vN, (14) holds only for all vectors in the unit sphere. The natural isotropic condition for general & is suP Eplexp X₁- F)|FF-1] & (A))- When Amax = oo then such a definition naturally exlends to all vectors in Rdd and is equivalent to (the isotropic version of) (4). For finite Amax: however, such an extension does not hold, so we work with (14) instead. This necessitates using different distributions in Proposition 1.1.
Suppose & is super-Gaussian. Let Pe be the uniform distribution over the ball centered at 0 E (1 - c) with radius e. Let be the uniform distribution over the ball centered at with radius Observe that Pa < The KL-divergence between Pa and is
DKL(PollV)= = - Jen+to
dpo (0) po(d0) dv
log
f log eBd40
vol(Bd) vol(eIBd)
Po (d0) dlog -
(15)
where vol(A) is the volume of set A Rd, whence vol(B²) 4/2 44/ (T (dd/2+1) and vol(c =
1). We note that using uniform distributions in conjunction with PAC-Bayes arguments was also used by Lee et al. (2024) when developing confidence sequences for GLMs. Applying Proposition 1.1 to the family of processes (M)(0))zz defined by
(())) II exp (A, - 1)) (0.) E,0)),
(16)
each of which is a nonnegative P-supermartingale by (14), gives the following result. The proof may be found in Appendix C.1. The closest result to the following bound is Manole and Ramdas (2023, Corollary 23), which gives a bound for isotropic sub-i processes. Their result is stated in terms of the inverse of the convex conjugate of th, (1)+)-1,, which makes a direct comparison of the bounds challenging. However, for common functions, (zi²)- (z)) behaves as V for small x, making their result consistent with Theorem 2.14 below.
Theorem 2.12. Let (Xt)121 be Eq-suub-b and salisfy Assumplion Suppose is super- Gaussian. Let (A:) be predictable sequence in (0, \max)) Fir < < Then, with probability 1- a, for all 2
Eige Eigedi di
Eise
log(1/a)
<
(17)
(1 (1-e) +) E.
11

---

The proof Published in Transactions on Machine Learning Research (05/2025)
A reasonable default value for is 1/2, but it may be further optimized depending on the relative size of d, at and sup, The explicit dependence of (17) on d means that, unlike Theorem 2.2, Theorem 2.12 is not dimension-free We are unaware of dimension- frree concentration results for general sub-t processes, or even for sub-gamma processes. The dependence on d instead of vd in the above CSS may seem worrying at first glance, but can be rectified by an appropriate choice of X1- Suppose that sup, |- & |>||| For CGF-like v, choosing
(lgg(1/0 /c) + log(1/0) ||]|| [og((
X
(18)
gives bound that shrinks as D(v|E=|(d log(1/a) log(t/)))) as shown by the following lemma. is provided in Appendix C.1.
Lemma 2.13. Let (Xe)e21 be Ep-sub-ip for any CGF-like vb Let We denole the right hand side of (17) and log(t)/t).
suppose that sup, Ex|| ||]||- Then, choosing de as in (18) gives W. =
As in Sections 2.1 and 2.2, we may use Theorem 2.12 to obtain a bound which achieves optimal iterated- logarithm rates. The details may be found in Appendix B. We focus on sub-gamma random vectors (i.e., & = ta,a). This is mostly without loss of generality, as Howard et al. (2020) demonstrate that any CGF--lik & obeys & & aFG,e for some a, > 0; see Howard et al. (2020, Proposition 1).
Theorem 2.14. Let (Xt)ez1 be (IEE)), -)------uuumaa for some e E R and satisfy Assumption 2. Then, for all (0, 1), with probability at least a, simultaneously for all t > 1,
| Σ X1 M -
Σ | (log(1/a) + log log(t) d)
$
(19)
Further, for sub-exponential random vectors (i.e., v Un and Amax oo) we can obtain the following bound with explicit constants. For 1/55, this result is directly comparably to (and lighter than) that of Manole and Ramdas (2023) which, to our knowledge, was previously the tightest known result for sequential concentration of sub-cxponential random vectors. Morcover, our result holds under martingale dependence and allows for anisotropy, which theirs does not. The details are again Appendix B.
Theorem 2.15. Let (Xt)121 be 1. Then, for all a E 10, with probobility at least 1 a, simullaneously for all 2b | 1/2 / /dlog(1// (1)e) + log(1.65/0 + log(logz(() +1,
and satisfy Assumption 2. Fix < <
1 Σ AE
1.71
Σ (log (log(1.65/o) + log log(log22( (t) 1) + dlog(1/c))
X1
1
(20)
Let us compare Theorem 2.15 to Theorem 2.9 for isotropic sub-exponential random vectors, i.e., Σ IaIa Let Ta (t) = log(1/a) + log(log(t)). The numerator of the CSS in Theorem 2.15 scales as a /Taa(t) (t) + d and
that in Theorem 2.9 scales as / /dvrr((() + ra (d) a worse rate. Of course, Theorem 2.9 holds for more general distributions. Fixed-time optimization of Theorem 2.15 can be found in Appendix A.3.
2.4 Time-varying means under sub- Gaussianity
Here we drop Assumption 2 and instead allow 14 = E[X,[F,-1] change with time. We are interested in understanding the behavior of Ex;r - ui)l Our bounds thus far have resulted from applying Proposi- tion 1.1 to familics of supermartingales involving predictable free paramcters x that we may optimize as a function of L. This approach does not work when the means are changing, roughly because it doesn't I allow us to isolate (X, - 4z). Instead, we use an approach known as the "method of mixtures," " which involves defining a supermartingale (0, A), for each in some set A C R, and then integrating over a well-choson distribution म: Mf) := SYEA (,, ()x(d)). Fubini's theorem implies that the resulting process (M)) is again nonnegative supermartingale.
12

---

Published in Transactions on Machine Learning Research (05/2025)
The method of mixtures is one of the best known techniques for producing time- bounds, dating back at least to Darling and Robbins (1968). In particular, using a two-sided Gaussian mixture, which we do here, was pioneered by Robbins (1970). It has also been used in modern work (cf. Kaufmann and Koolen, 2021; Howard et al., 2021; Waudby-Shin Smith et al., 2024). Of course, not all mixtures will result in a tractable process (M)) (analyticall) or compulationally)). This is doubly true in our case, because our arguments rely on isolating the term (0, X; p)- Therefore, even implicit bounds that might be approximated computationally in the scalar setting do not serve us well. (See for instance Howard et al. (2021) who study using one- and two-sided Gaussian mixtures, Gamma mixtures, one and two-sided beta binomial mixtures, and others.)
When (Xt) are conditionally sub-Gaussian, can obtain closed-form bound on Eisr(X; mi) using a two-sided Gaussian mixture distribution as т. For technical reasons elucidated in the proof, we can only consider random vectors that are oy-sub-Gaussian (meaning that (4) holds with E, = =a) This leads to a bound with width depending on vd instead of E..
Theorem 2.16. Let (Xt)ea1 be condilionally o.-sub- Gaussian where X, has conditional mean pa- Sel H, = Eigt of. Then, for any > 0, E 10, and E (0,1), have that with probability 1 a, simaltancously for all t > 1,
1 t i
Σ
[X; m2) & 1 1- cV
2(1 + H2.H) a²t²
(dlog(1/c) + log [VI+ (H+HHH/))))
(21)
The proof is provided in Appendix C.1. Like Theorem 2.12, we must rely uniform distributions in the PAC-Bayes argument (note the prior and posterior used in Proposition 1.1 is distinct from the mixing distribution used in the method of mixtures), which accounts the dimension-deeenddenee of the bound. One should compare our bound to Robbins' original mixture (see Robbins, 1970, Equation (17), or Waudby-Snith et al., 2024, Equation (8) for a version closer in spirit and notation to our work here).
2.5 Obtaining confidence ellipsoids
Let us end this section by briefly discussing how the techniques developed thus far can be used to obtain bounds in the Mahalanobis norm instead of the & norm. We use sub-Gaussian random vectors our primary example. If (Xt)ez are E-sub-Gaussian, then the random vectors D-1/2X, are l-sub-Gaussian. That is, Ejexp(A(0, E-/ - p)) thv (2) F--1 < 1 for all A E R. Theorem 2.3 thus implics the following CSS: with probability 1 a, simultancously for all > 1,
Σ X; P
=
1
E
1/2x,
E-112
1
Σ
iE
d
log(1.65/a) + 2 (log (0 (t) 10++1 +1)
< 1.21
1.682V
(22)
Confidence ellipsoids can be desirable because their shape reflects the variance of the distribution. However, the drawback is that in order to be explicitly computed, the variance Σ must be both known and fixed. We note that the bound above is distinct in flavor from the self-normalized bounds studied by Abbasi- Yadkori et al. (2011), de la Peña (1999), and Whitchouse et al. (2023). Such bounds aim to achieve self- celf-normalization with respect to accumulated and possibly random variance process as opposed to fixed covariance matrix. Bounds similar to (22) can be obtained for other E-sub-y conditions, following the techniques in Section 2.3.
3 Heavy-tailed random vectors
In this section suppose the random vectors (X,) are less well-behaved. We assume only that there exists finite second moment:
|||||||
< o² < co, vt 1.
(23)
Note that this condition implies that the norm of the mean j is bounded by |[[ < E|||X||FF= <
"| & Tdeally, one would prefer that (23) gets replaced by bound the centered moment
13

---

Published in Transactions on Machine Learning Research (05/2025)
EpliXX -u1 Unfortunately, our techniques in this section do not allow for such constraint so, like Catoni and Giulini (2018) we satisly ourselves with (23).
In this section present three main results: two semi-empirical CSSs (Theorems 3.2 and 3.5) and a sequential version of the Catoni-Giulini estimator (Theorem 3.7). All of these CSSs are dimension-free. Throughout this section, we let po be a Gaussian with mean & and variance I-1 Set Dn = Cor(X.
3.1 A first semi-empirical CSS
Our first result based on the following supermartingale derived using an incquality furnished by Delyon (2009, Proposition 12); see also Howard et al. (2020, Lemma 3). Variants of the resulting process have been studied by Wang and Ramdas (2023, Lemma 5) in the context of CSs, and both Haddouche and Guedj (2023, Lemma 1.3) and Chugg et al. (2023, Corollary 17) in the context of FAC-Bayesian bounds.
Lemma 3.1. Suppose (Xt)131 P where P is any distribution obeying (23) and Assumption Let
(0) (0, X; -1). For each fired 0 E IRd, the process S(0) (S,(0)) is a nonnegative P-supermartingale, where (0) ligs exp (0)
2 (X) + 2 2,0
Mixing over θ = Idd with prior Po and posteriors pa, 0 E gd-1, we obtain the following theorem, which is proved in Appendix C.2 (along with Lemma 3.1).
Theorem 3.2. Let (Xt) ~ P for any P obeying (23) and Assumption 2. Let (Ax) be a predictable sequence in (0, co). For any B > O, vector x, and matrix A, set
sp(x)= (1
1 3 (1|=1| + v)², and wa(A) = |||||| Tr(A) B
83(x)= = (1 + [|== + r)2 and (A) = ||||| + TMAa/B. Then, for any E (0, 1), with probability 1 - ax for all t 1,
Eige
+ 3/2 + log(Laa) / Eisr Xp (X,( 2w0 (En) Eiged -H
6 Eigt A;
Eige A
Theorem 3.2 is semi-cmpirical in the sense that it depends both the values |X,]]| but also on ||,,| and Tr(E.). To explicitly compute the bound, therefore, would require knowledge of these values. Still, a known bound on the variance is required for nonasymptotic concentration of unbounded random variables (even in the scalar case), so fully empirical bounds are impossible.
Vsup, Tr(E.) (which is finite because is finite) and A V log(1/a) Folgo so that the expected width of the CSS in Theorem 3.2 scales as O(vyTog(() log(1/a)/t). (Here we've used that Note that this bound on the width only holds in expectation and this appears to be unavoidable: in general, with exactly two moments and no more, the empirical variance term may not concentrate.
We suggest setting
wa (E.) = (X)= O(v)).
Scalar setting. It is perhaps worth noting that in the univariate setting, Theorem 3.2 complements Lemma 6 in Wang and Ramdas (2023). They develop a confidence sequence for scalar-valued, heavy-tailed random variables by using a process similar to that described in Lemma 3.1. Instead of upper bounding μ by the raw second moment, however, they solve quadratic equation to obtain anti-confidence sequence for μe, and their final CS results from taking the complement. Theorem 3.2, meanwhile, results in a slightly looser but more digestible CS.
Corollary 3.3. Let X2... be scalar random variables with second moment 2² and conditional mean μ = F. Let (Ae) be predictable sequence in (0). Then, for any a E (0, 1), with probability a, for all t $>1 1,
Eise diXi Eigedi di
Eigo A + +0)² + 20 1/2 + log(1/a)
<
3 Eiss X
Eigel. d:
14

---

Published in Transactions on Machine Learning Research (05/2025)
We note that despite Corollary 3.3 being closed-form, it may perform worse than the bound of Wang and Ramdas (2023) in practice. First, as noted, to achieve closed-form bound we deploy some inequalities which loosens the bound. Second, the right hand side may not concentrate. Indeed, we should not expect the sample mcan to have sub-Ganssian tail behavior around the true mean.
Considering the fixed-time setting with n observal ions and setting X; = ===== gives the following CI for heavy-tailed random variables.
/o0o(1/o)+1122 2ne
Corollary 3.3
Corollary 3.4. Let Np be scalar random variables with second moment v² and conditional mean / = Fe-)- Then, for any a E (0, 1), with probability 1 a,
log(1/a) n
Σ Eisn (11x) + v)2
X M E SEA
71
TBU
3.2 A semi-empirical CSS under symmetry
Let us present second semi-empirical bound for heavy-tailed random vectors. We assumee that the vectors (X1)121 are conditionally symmetric around the conditional mcan μ,, i.c., X₁ X (XX--)]FFFa and also have two moments. Using supernartingale identified in de la Peña (1999, Lemma 6.1), we may obtain a result reminiscent of Theorem 3.2 but without the term wa and with tighter constants. Theorem 3.5 is proved in Appendix C.2.
Theorem 3.5. Let (Xt)121 ~ P for any obeying the moment bound (23) and Assumption 2. Suppose the vectors are also conditionally symmetric: X, p - ((x-x)) F)) for all > 1. For any positive predictable sequence (Xc) and any E (0, 1), with probability
a, for all f >> 1,
Eier Eiseds
m -m|
Eisr X211 + u)² + 112 + log(1/o)
Eisode d
Of course, one may obtain results analogous to Corollaries 3.3 and 3.4 for Theorem 3.5. We omit these for brevity. A similar discussion as above on how set d applies here.
3.3 A sequential Catoni-Giulini estimator
Now we proceed to a sequentially-valid version of the estimator originally proposed by Catoni and Giulini (2018). To motivate it, observe that the theorems given thus far rely on the estimators fhg = E, X, A However, is known that such simple linear combinations of samples such as the (possibly weighted) empir- ical average have sub-optimal finite-sample performance under heavy tails (Catoni, 2012). Other estimators are therefore required. To begin, for sequence of positive scalars (Ae), define the threshold function
th((x)) = (Ael A1
(24)
A |z||
Our estimator will be
ee Eigr (x,h;
(25)
Eise
The analysis proceeds by separating the quantity (0, tXe( 14) into two terms:
(0, (X, - n) =(0, the -10t
tXt) -ught (0, p n))
(26)
(5)
(3))
where 14th = [X) The second term is dealt with by the following technical lemma, which is proved Appendix C.2. Intuitively, the result follows from the fact that tx) shrinks æ towards the origin by an amount proportional d
Lemma 3.6. Term (ii) of (26) obeys: suppegs 1 (0, 1thh 11) 1114t zall 2
15

---

Published in Transactions on Machine Learning Research (05/2025)
Width of CSS for heavy-tails
Width of CSS for heavy-tails
10
GMab w/ ub
TMoM w/ dbl
GMcM w/ ab
Themem 11 Theorem
GMaM w/ dhl
Theorem
GMOM w/ dbl
TMcM w/ ub
Theorem
C25 Whlth
Width
10'
100
10P
0
20000 40000
G0nOC
80C00
100000
20000 40000
G0000
80000
100000
Figure 2: Left: Comparison between our sequential Catoni-Giulin estimator (Theorem 3.7), geometric median-of-meanss (GMoM) (Minsker, 2015), and tournament median-offmeans (TMoM) (Lugosi and Mendel- son, 2019a). We make the MoM estimators time-uniform in two ways: with a naive union bound (solid lines), and via the doubling method Duchi and Haque (2024) (DH Doubling). Even though it has optimal (fixed- time) rates, the TMoM estimator suffers because of large constants. Right: A closer look at the performance of GMoM estimator compared to Theorem 3.7. We assume that a practitioner knows either Tr(E) or x² (knowing both would imply knowledge of [|e]]), hence we set Tr(E) = 6² in the figures in order to compare their multipliers in the bound. Again, we make the GMoM time-uniform via (i) union bound, and (ii) Duchi- Baahi-Hqque doubling. Simulation details can be found in Appendix D.
To handle term (i) of (26), we appeal to PaC-Bayesian techniques. Notice that the process (U(0))²21
defined by (0) le. (xp(Axf((0) log E exp((x, where f((0) (0, tX,) nnth) is nonnegative P-martingale for any E Rd. Applying Proposition 1.1 with the prior Po and posteriors Pa: d E gd-1 provides a bound on supaega-: Eis (1,0, (X,( - -uth), which in turn furnishes the following theorem. The details are Appendix C.2.
Theorem 3.7. Let (Xt)ea obey [1I & 2² and salisfy Assumption 2. Fir B > 0. Then, for any E (0, 1), with probability at least 1 - a, for all t t 1,
v2 1e + Eise + log(1/a)
Eigr Xxth
1 x
(27)
Eiso
Eise>1 d
We find 8 4 to be reasonable choice in practice. Consider setting X, /lottt/ As dis- cussed in Section 2, Eist 1/slogi x log log(t) and Eise V/Vilggs x /t/log(t), so the width of (27) scales as O(//oool1))))) 1/1). In the fixed time setting, ideal estimators are sub nau-Ganssian (Lugosi and Mendelson, 2019a, Equation (3.1)), in the sense that they have rate O(y [Tx])lop(////// + (T()))))) (where we assume that Σ is constant over time). For us, setting À = X; x /lo((//0//// for all yields a slightly larger rale of log(///)/)) This is no surprise: it is well-known that the Catoni-Giulini estimator is not sub- Gab-sasssinn, hence the development of the tournament pediian-of-meatt (TMoM) estimator (Lugosi and Mendelson, 2019b).
We also provide a stitched version of Theorem 3.7 which achieves iteraled logarithm rates. The details are in Appendix B.5.
Theorem 3.8. Let (Xt)121 obey E||| & 2² and satisfy Assumption Let (8m)ma1 be sequence of posilive scalars such that 3m is F (osg(mm) -predictable. Then, with probabilily ax, simulloneously for all 2
log, log, (3 (8 (t) /2 logg1.65////.. + log (log, (f) + 1))
11 < <1.69u>
(28)
Eier X
b
where Am 2exp(2/xp2/)) 33m 2) +
16

---

Published in Transactions on Machine Learning Research (05/2025)
Here, (3m) is a sequence of optimizable constants, though only at geometrically spaced time steps, not every time step. Root-finding may be used to find the optimal value of 8m at some value of 6, though we find that in practice this does not improve the bound much over setting 8n = 4 for all m.
We compare various estimators in Figure 2. The TMoM estimator suffers as a result of large constants, wash- ing out its asymptotic benefits for reasonable sample sizes. Similarly to the experiments in Section 2.1, the TMoM estimator was made time-uniform in two ways: via naive union bound, and using the doubling tech- nique of Duchi and Haque (2024). Theorem 3.7 outperforms both. We also compare Theorem 3.7 to the geo- metric median-of-ment means (GMoM) estimator (Minsker, 2015) which achieves rate of O V (T((E) log(1/a)n) in the fixed-time setting. We make it time-uniform in the same two ways as TMoM. GMoM has signifi- cantly smaller constants than the TMoM estimator, making it much closer to Theorem 3.7 in practice, and sometimes beating it. The stitched Catoni- Ganniii estimator, Theorem 3.8, dominates other estimators.
4 Summary
We have provided a general framework to derive nonparametric, time-uniform confidence sequences for the mean of a multivariate distribution under martingale dependence using PAC-Bayesian techniques. Our re- sults light-tailed regimes include dimension-free bounds for sub-Gaussian and log-concave random vectors, bounds for general sub-g distributions, and bound for tracking the time-varying mean of sub-Gaussian distributions. Our results in the heavy-tailed regime include two semi-empirical bounds and sequentially- valid version of the Catoni-Giulini estimator. We give bounds that achieve optimal iterated-logarithm rates, and also bounds that are optimized for particular sample sizes.
References
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Newral Information Processing Systems, 24, 2011. 2, 3, 5, 13
Radoslaw Adamezak, Alexander Litvak, Alain Pajor, and Nicole Tomenak-Jaegerman Quantitative es- limates of the convergence of the empirical covariance matrix in log-concave ensembles. Journal of the American Mathematical Society, 23(2):533-56) 2010.
Adobe.
https:// adobe. wwwoe.com//aeeeeee com/docs/ pantiics-platffommmussssii httpa//ggw...oooooo/////////aaaa
Adobe Experimentation Panel.
atml?lang=en 2023. [Online:
accessed 13- 33-October-2025, 1
Pierre Alquier. User-friendly introduction to PAC-Bayes bounds. Foundations and Trends in Machine Learning, 2024. 4
Olivier Catoni. Statistical learning theory and stochastic. optimization: Ecole d'Eté de Probabilités de Saint- Flour, XXXI-2001, volume 1851. Springer Science & Business Media, 2004. 33
Olivier Catoni. Challenging the empirical mean and empirical variance: deviation study. In Annales de I'IHP Probabilités et statistiques, volume 48, pages 1148-1185, 2012. 2, 15
Olivier Catoni and aariia Giulini. Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression. Xiv preprint arXiv: 02747, 2017. 2,
Olivier Catoni and Iaria Giulini. Dimension-free PAC-Bayesian bounds for the estimation of the mean of random vector. (Almost) 50 Shades of Bayesian Learning: PAC-Bayesiar Trends and Insights. NeurIPS Workshop., 2018. 2, 3, 4, 14, 15, 34
Ben Chugg, Hongjian Wang, and Aaditya Ramdas. A unified recipe for deriving (time-uniform) PAC-Bayes bounds. Journal of Machine Learning Research, 2023. 2, 4, 5, 7, 14, 33
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit. feedback. 21st Annual Conference Learning Theory, 2008. 2
DA Darling and Herbert Robbins. Some further remarks on inequalities for sample sums. Proceedings of the National Academy of Sciences, 60(4):1175-1182 1182, 1968. 13
17

---

Published in Transactions on Machine Learning Research (05/2025)
Donald A Darling and Herbert Robbins. Confidence sequences for mean, variance, and median. Proceedings of the National Academy of Sciences, 58(1 ((1():66-60) 68, 1967. 1, 3
Victor H. de la Peña. A general class of exponential inequalities for martingales and ratios. The Annals of Probability, 27(1):537-556 1999. 8, 13, 15, 33
Victor H de la Peña, Michael J Klass, and Tze Leung Lai. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. Annals of Probobiliby, 2004. 3
Victor H de la Peña, Tze Leung Lai, and Qi-Man Shao. Self-normalized processes: Limit theory and Statistical Applications. Springer, 2009. 3
Bernard Delyon. Exponential inequalities for sums of weakly dependent variables. Electronic Journal of Probability, 2009. 14,
Luc Devroye, Matthieu Lerasle, Gabor Lugosi, and Roberto Oliveira. Sub-Ganssian mean estimators. The Annals of Statistics, 2016. 5
John Duchi and Saminul Haque. An information--heorelicc lower bound in time-uniform estimation. In The Thirty Seventh Annual Conference on Learning Theory, pages 1486-1500. PMLR, 2024. 4, 6, 7, 16, 17, 36
Evidently. How Evidently calculates results. https://docs. aws amazon. com www.eoooccaaaeeee htt/:///nnncooaaaatalalaaaeeeeee
2023]. http:///loooaaaaaa--i.tttttlta-e
html, 2023. [Online; accessed 13-October-
Xiequan Fan, lon Grama, and Quansheng Liu. Exponential inequalities for martingales with applications. Electromic Journal of Probabilily, 20:1 22, 2015. 37, 38
Louis Faury, Marc Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for
logistic bandits. In International Conference on Machine Learning, pages 3052-3060. PMLR, 2020. 3
Vitaly Feldman, Cristobal Guzman, and Santosh Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. In Proceedings of the Quenly-Eighule Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1265 1277. SIAM, 2017. 2
Ronald Aylmer Fisher. Dispersion sphere. Proceedings of the Royal Socicty of London. Series A. Mathematical and Physical Sciences, 217(1130)2295-30) 1953. 22
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-115 1975. 8
Ilrraa Giulini. Robust dimension-free Gram operator estimates. Bernoulli, (J44B)388643925) 2018. 3
David Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Transactions on Information Theory, 57(3):1548 1566, 2011. 37, 39
Benjamin Guedj. A primer on PAC-Bayesian learning. In Proceedings of the second congress of the French Mathematical Society, volume 33, 2019. 4
Maxime Haddouche and Benjamin Guedj. PAC-Bayes generalisation bounds for hcavy-tailed losses through supermartingales. Transactions on Machine Learning Research, 2023. 14
Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys, 17:257-317, 2020. 6, 9, 10, 12, 14, 30, 33, 37, 40
Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasject Sckhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Stalislics, 49(2), 2021. 1, 6, 10, 13, 23, 37
Daniel Hsu, Sham M Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17:1, 2012. 2, 4, 7, 8, 36
Chi Jin, Pranceth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. A short note on concentration inequalities for random vectors with subGaussian norm. Xrx preprint Xve: 1902. 03736, 2019. 8
18

---

Published in Transactions on Machine Learning Research (05/2025)
Emilien Joly, Gábor Lugasi, and Roberto Imbuzeiro Oliveira. On the estimation of the mean of random vector. Flectronic Journal of Statistics, 11(1):440, 2017. 5
Emilie Kaulmann and Wouter M Koolen. Mixture martingales revisited with applications sequential tests
and confidence intervals. The Journal of Machine Learning Reseorch, 22(1):11140 11183, 2021. 13
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex optimization. International Conference on Machine Learning, pages 1895-1904. PMLR, 2017. 37, 39
Arun Kumar Kuchibhotla and Abhishek Chakrabortty. Moving beyond sub-Gaussianity in high-dimensional statisties: Applications in covariance estimation and linear regression. Information and Inference: A
Journal of the IMA, 11(4):1389-144 1456, 2022. 2
Tze Leung Lai. On confidence sequences. The Annals of Statistics, pages 265 280, 1976.
Tze Leung Lai and Ching Zong Wei. Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems. The Annals of Statistics, 10(1):154-100 1982. 2
Junghyun Lee, Se- Young Yun, and Kwang-Suna Jun. A unified confidence sequence for generalized linear models, with applications to bandits. Advances in Neural Information Processing Systems, 37:124640- 124685, 2024. 11
Michael Lindon, Chris Sanden, and Vaché Shirikian. Rapid regression detection in software deployments through sequential lesting. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3336 3346, 2022. 1
Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 19(5):1145-1199, 2019a. 3, 16, 37
Gábor Lugosi and Shahar Mendelson. Sub-Gaussian estimators of the mean of random vector. The Annals of Statistics, 47(2):783 794, 2019b. 2, 4, 5, 16
Tudor Manole and Aaditya Ramdas. Martingale methods for sequential estimation of convex functionals and divergences. IEEE Transactions on Information Theory, 2023. 3, 4, 11, 12
Kanti V Mardia, Peter E Jupp, and KV Mardia. Directional statistics, volume 2. Wiley Online Library, 2000. 10, 22
Diego Martinez-Tabenn Taboada and Aaditya Ramdas. Empirical Bernstein in smooth Banach spaces. arXiv preprint arXi:2249.060600 2024. 37
Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample variance penalization. arXiv preprint xrxi::9907.3740, 2009. 39
Andreas Maurer and Massimiliano Pontil. Concentration inequalities under sub- Lub-Gaussian and sub- exponential conditions. Advances in Neural Information Processing Systems, 34:7588 7597, 2021. 4, 9
David A McAllester. Some PAC-Bayesian theorems. In Proceedings of the eleventh annual conference on Computational learning theory, pages 230-234, 234, 1998. 4
Stanislav Minsker. Geometric median and robust estimation in banach spaces. Bernoulli, (4() 23355 2015. 2, 4, 16, 17
Shogo Nakakita, Pierre Alquier, and Masaaki Imaizumi. Dimension-free bounds for sums of dependent matricos and operators with heavy-tailed distributions. Electronic Journal of Statistics, 18(1):1100-119, 2024. 3
Philippe Rigollet and Can-Christian Hütter. High-dimensional statistics. MIT Lecture Notes, 2023. 2, 4, 8,
21
19

---

Published in Transactions on Machine Learning Research (05/2025)
Herbert Robbins.
Statistical methods related to the law of the iterated logarithm. The Anmals of Mothe- matical Stalistics, 41 (5):13997-1409 1970. 2, 13
Peter J Roussoeuw and Mia Hubert. Anomaly detection by robust statistics. Wiley Intendisciplinary Reviews: Data Mining and Knowledge Discovery, 122)= 2018. 2
John Shawe- Taylor and Robert Williamson. PAC analysis of a Bayesian estimator. In Proceedings of the Tenth Annual Conference on Computational Leurning Theory, pages 9, 1997.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11)11134-1149 1984. 4
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, vol- ume 47. Cambridge university press, 2018. 21
Diego Vidaurre, Concha Bielza, and Pedro Larranaga. survey of 11 regression. International Statistical Review, 81(3):361 387, 2013.
Hongjian Wang and Aaditya Ramdas. Catoni-style confidence sequences for heavy-tailed mean estimation. Stochastic Processes and their Applications, 2023. 3, 14, 15
Yoko Watamori. Statistical inference of Langevin distribution for directional data. Hiroshima Mathematical Journal, 26(1):25-74, 1996. 22
Ian Waudby-Snin Smith and Aaditya Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Sociely, Series B (with discussion). 2023. 1, 37, 39, 40
Ian Waudby-Smith, David Arbour, Ritwik Sinha, Edward H Kennedy, and Aaditya Ramdas. Time-uniform central limit theory and asymptotic confidence sequences. The Annals of Statistics, 52(6))2613 2640, 2024. 4, 13
Justin Whitehouse, Steven Wu, and Aaditya Ramdas. Time-mniform self-comncentration for vector-valued processes. arXiv preprint 3rXi:22310.09100, 2023. 3, 5. 10, 13
Nikita Zhivotovskly. Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle. Electronic Journal of Probabilily, 29:1 28, 2024. 2, 3, 4, 8, 9, 28
20

---

Published in Transactions on Machine Learning Research (05/2025)
A Additional results
A.1 Sub-Gaussian distributions
Isotropic case. Let us instantiate Theorem 2.2 in the isotropic case, meaning that Eg = of la for some scalar dr. Then ||S|]| = of and Tr(E;) = ofd. Taking 3 and d as in (5), i.e,
B + (1/a) B v (2dlog(1/a) and x = V ( log(t +)
where o² > sup, of gives width of
δ Vo + log(1/a)
log l
(29)
We note that the factor of v very natural in the isotropic case as, intuitively, the variance spread evenly in all directions and thus scales with the dimension. See, e.g., Vershynin (2018, Theorem 3.1.1) Rigollet and Hütter (2023, Theorem 1.19) for the same vdd dependence.
A.2 Log- concave distributions
Fixed-time optimization. Following the approach in Section 2.1, let consider optimizing our log- concave bound for fixed time / n. Consider laking
2hx (log(2/0) nhy(1) (1)
A = An =
if is large enough such that upper bounded by Applying Theorem 2.8 and using the upper bound (1)r))s11) gives the following result. Again, the bound is tightest at time but remains valid all other times. We unaware of previous fixed-time concentration results for log-concave distributions against which we can compare Corollary A.1.
Corollary A.1. Let (Xt)²2 satisfy (10) and Assumplion 2. Fix any n and a E (0,1) such that n > h2s(() where 1og(2/o)). Then, with probubility 1 a, simultaneously for all t > 1,
Eige AxX, Eiged di
2n (v
12 2 +
1
20
(T(E) + 3ra 3 TrE
(30)
A.3 Sub-u distributions
Fixed-time optimization. Again, following the approach in Section 2.1, let us consider (E, b)- exponential random vectors for constant E Ez Applying Theorem 2.12 at fixed-time with
2d 2dlog(1/e) + 22))222lgggg log((1/a)
||||n
gives the following analogue of Corollary 2.5 in the sub-exponential setting.
Corollary A.2. Let X1....,XX Xx be conditionally (E, B) -bbeeeeerpoottt and satisfy Assumption 2. Fix e 1). Then, with probability - 6, simultaneously for all t 2 1,
| x a
1 +
1 vn
Σ (d log(1/a))
(31)
I-e
As in Corollary 2.5, this bound is tightest at f but remains timo-uniform. At n, taking = 1/2 we obtain width 2 2/2 log(1/a)/n, which has the optimal dependence on d, n, and || for isotropic sub-exponential random vectors.
21

---

Published in Transactions on Machine Learning Research (05/2025)
Sub-u bounds for non super-Gaussial v. Theorem 2.12 gave CSS for sub- distributions with Gave--Gaussian 1b. While most common & functions are super-Gaussian, not all are. For example, consider (B),,a(A) = ca log (in the sense that BBB.dd the CGF of a centered random variable supported on -c and d). It's therefore worth providing a result which holds for general y functions, both super- super-Gaussian and non-super-Gaussiae
ce +d for c, > 0 and Amax = co. This characterizes a sub- nab-Bernuulli distribution
ctd
The key to deriving Theorem 2.12 noticing that Sausr-a & allows to transform the dcfinition of sub-u distribution (14) from statement involving vectors in gd-1 to vectors in B This allowed us to use uniform distributions over the ball when applying Proposition 1.1. If ab is not Super-Gaussien then such a transformation isn't possible. We must therefore work with distributions that are defined on the unit sphere. This leads us to the von Mises-Fisher distribution. Before we expound on the details of this distribution, let. us state the result enables.
Theorem A.3. Suppose (X1)s21 for Xt E IRd d 2, are sub-i and satisfy Assumption 2. Let (Ae)aaa be predictable sequence in [0, Amax). Then, with probability at least 1 a, for all > 1,
Eige A,X; Eigedi de
/
va (A)) + 2vd vdlog(1/a)
11
(32)
Notice that unlike Theorem 2.12, the dimension dependence in Theorem A.3 multiplies the width of the bound. That, combined with the prefactor of 3/2 typically leads to looser bounds than Theorem 2.12, so we encourage practitioners to use the latter when possible.
Let us now introduce the von-Mises Fisher (vMF) distribution (Fisher, 1953) (also known as Langevin distri- butions, Watamori, 1996). For x E g6-1, the vMF distribution has density >(x; 9, x) = Ca(is) exp(x(0, x)), where Ca(s)= <d/2-1/ function of the first kind of order and x > 0 is scalar "concentration parameter'. The expected value of the vMF distribution obeys
(k)] is the normalization constant. Here, Ie is the modified Bessel
E B = [ (y(d8; 0, k) = As(x)
(33)
ga-1
where Aa(x) (1)2())//a/2-1(()).. The vMF can be obtained by starting with multivariate Gaussian and then conditioning on observations with unit norm. We refer to Mardia et al. (2000) for more on the vMF distribution, and for a general introduction to the field of *directional statistics," which considers distributions on the sphere. Moreover, Temma C.2 in Appendix C proves that
& 2nAx(x).
(34)
For an idca of its magnitude, Lemma C.3 proves that VdAa(Vd) E (2/3,1), 1). The vMF is only well-defined for d > 2 so we restrict ourselves to this setting. We will often write 7o(+) 7(;0,, x), leaving the implicit.
Proof of Theorem A.3. We apply Proposition 1.1 with prior 7(: 1, k) and posteriors 7(; 0, x) for all 8 E gd-1 to the process defined by (f) = Il exp X; - 11 ().) E, This gives that with probability a, for all 2>1 1,
Σ1 N a
J (0, (0,X,- ()ro(d0) < Σ ((ii) I 3e-1
(0. (0.00))))(d)) + 2x log(1/a).
34-1
Using (33) and upper bounding E,)), as |l the above display becomes
Σ Aa(m) m) (A.))E, + log(1/a). VEA
Dividing both sides by Aa(k) Eise Aos taking a supremum over E gd-1, and then taking k = vd and applying Lemma C.3 gives the result.
22

---

Published in Transactions on Machine Learning Research (05/2025)
B Stitched bounds with LIL rate
Here demonstrate how to achieve CSSs which shrink at rate of ((y/lo(log(())/t) and proving Theo- rems 2.3, 2.9, 2.14, 2.15, and 3.8. This is done via "stitching," " which is a common technique in the literature on confidence sequences and originates in Howard et al. (2021). Stitching involves applying distinct bounds over geometrically spaced epochs. Bounds in each epoch can be engineered to be tighter than a bound uniform over time. The bounds are then carefully combined together using a union bound. To proceed, we define our "stitching function" as
f(m) (m + (2)), where ((2)
Σ k ~ 1.645. k=1
(35)
Note that EmE0 E(m) = In what follows, any function l could be used such that Em.o E(m) but here we fix a particular choice for convenience.
B.1 Stitched Sub-Gamma Bound
Here consider the sub-ih bounds of Section 2.1 with e5(A) ()),
2(1-aa) CE RR We assume that
1
== Σ, for all t. Apply Theorem 2.12 in each epoch [ 2m+1) with a constant parameter Am and am- We obtain that with probability Omm
(Am)) + dllo((1/c) Tm =: =:)m(t),
Xx - P Σ ig
E
AA E [2Th 2m+!).
(36)
1-
Amt
where Tm = log(l/am). Taking a union bound gives that with probability 1 - >m Om, simultaneously for all t > 1:
1 Σ x, istt
gml(), where & logg(t) m + 1.
We take am a/l(m) that E O'm The remaining work resides in ensuring that gm(() shrinks at the desired iterated logarithm rate. We take
[dlog[1/e) (e/e +m Im
Am --
n Σ|
where
2 c /c2 2/u
/ (n)
Then 2rm/t / 2 mm/22 2 Tm/t so
d dlog(1/e) + Tm
< (A)m) < d dllo(L//)) + Tm
[
/||11
and since a (u) is increasing in u,
[dlog(1/c) 1/) +mm
2m ||ll
c+ v 2t 2 d dlog(1/e))
Therefore,
dlog(1/e)+rm
dllo(1//) + rm
1 1-e (t) <
2m
(loo((1/e) + Tm
1 --c
23

---

Published in Transactions on Machine Learning Research (05/2025)
1-e c vo+
21 ΣD
(llg((//)) + rm
dloo(1//) Tm
2t
Since e is a constant and is dominated asymptotically by alog(L/()rm we have (taking e = 1/2 for simplicity).
|||
E||
ddlog(2) mm
[ log(1/a) + log log
(m))) - V d2lo((2) Tm
t
Then notice that
Im log(1/a) + log({(m)) < log(1/a) + llog(log2 + 1) + log(1.65),
where we've used that & (t). It remains only to check that our choice of Am is legal, i.e. A < 1/c. Using that ob is increasing, we have
(2 + 2rm
Am & w-
||>1|
which is less than 1/c iff v[+1[21//doo)2 + Fmm, which holds for all >
B.2 Stitched sub-exponential bound
Here prove Theorem 2.15. Let (A) X2/2 for all |A|< 1/b. Here we make the same choices we did above, but the analysis can be tighter. In this case, (u) 22u so
dloo(1//)) +
Am
2m ||||
and
1
Am [||
dloo(1/c) + Tm
(t)())
1-c 2
Amt
| (dlog(1 +mm)
1
2m
1-6
2m
[ (d 1/c) + pm)
+
2t
1.71
(dlog(1/)) rm)
Finally, recall that we need to ensure that Am < 1/b, which holds if > 26y
d'og' d 1/))+mm
[>]
B.3 Stitched sub- Gaussian bound
Let /s(E) = ||Я|| + Tr(E)/3. Similarly to what was done above, applying Theorem 2.2 in each epoch
[2mh, 2m+l) with parameters Am, am, and Pm gives
tux (2m ( Dm (E) + Bm/ + Tm =: (t), E [2mh (,,,),
X1
<
(37)
tAm
where rm = lom(1/am) As before we set am = a/l(m) and we take
8m
I'm Tr(E)
Am
and 3m ov
m2 Tr(E)*
|
24

---

Published in Transactions on Machine Learning Research (05/2025)
Then, noting that 2 < Am & /28mm/ Vt Tr(E), we have
AmsBm (2)
Bm// 2
gm
tAm
J Bm
Tr(E)
I'
Tr(E)
2t Tr(2))
2
8m
Bm||211
Tr(E)
(r(
I'
Tr(E)
2t Tr(E)
2
+
V
Bm
I' |>||
mm
1
Tr(E))
V22
2
Optimizing over gives 2// and bounding I' as above gives the desired result.
B.4 Stitched log-concave bound Our strategy is the same in the previous sections. In this case we have
Im (t) 2Chn:11)a + 4Chss(og((2/an)) Amt
Consider taking
hy (log( (log(2/am)) (2/am))
Am = V
h5:(1)2m
for some > 0 to be determined later. Then, using that 2 < t and 2 > 2/t,
hy (1())/)((og((//m)) 2
4C Vis(1)) (log( (2/ (2/mmm )mm
9ml(1) = /
kt
2 4C
2C 1 kVt)
Optimizing over gives x 21/4 which case we obtain
gm & 6.73CV hx
where
log(2/am) & log(2((logg())) (4))/o)
< log (2 (I) + 1)2 1.65/a) 2log(logg (1) 11 + log(3.3/a).
Recalling that for u > 1, hy(1)hz(u) & Tr(E)/u uy Tr(E) furnishes the claimed iterated logarithm rate and proves Theorem 2.9.
B.5 Stitched Natoni-Giulin bound Let A,, 2 2xpp2233 2) 1. Following the strategy above, here have
Im (1) u2 A2 A2,t t Bmm + I' 0² Am
Bm/2 Tm Am
Am1
Take
Bm/ 2 + m'
Am C1
1.2 Am 2m
25

---

Published in Transactions on Machine Learning Research (05/2025)
for some 0. Then
Am (am33m/ 1 Vm
1
2m Am (3m 2 + Ti
9m (t) = cV
+
2
12
2m (Bmo/ 12 rm))
(Bmo/ Am
Am
2 + rem)
< v
CV
c
b
Am (mnmm/ 12 Vm
< 1.690
if we take c= 2-1/1
C Omitted proofs
Lemma C.1. Let E E RRddd be coveriance matrix. Then
2| + Vd TT(E)
Tr(E²)
<
< |||
(38)
Proof. Let Σ have eigenvalues e1 > 62 ... ed- The second inequality is easy: Tr(E") Eisiga & 61 Diga = [r]] As for the first incquality, let u -=1 Ercied be the average of the smallest eigenvalues. Using Jensen's inequality, write
T+(E9) Eisiga Tr(E)
c + (d 1)u²
5()).
Σ Engied
e1 + (d 1)u
The minimum of f for 0 occurs at u c1(Vd+1)/(dd giving f(u²) 201 21 which proves the claim.
Lemma C.2. The Kullback-Leihe divergence from 7(90, x) to x(),, salisfies
D(a( 2nAa(s).
Proof. Let X ~ k). By direct calculation,
((] x)) E log (X:011 x) E [m(0)] - do. x)] = k(01 10. Aa()))))
7(;;0,
Since both 0, 91 are on the unit sphere sd-1, the inner product (01 fo. 02) upper bounded by 2, which concludes the proof.
Lemma C.3. For any d > 1, 3 vdAa(Vo) < 1 where Aa(k) is the vMF constant.
Proof. Note that,
Emzo Vd. (Vd/2)2m1d1
VdA.(Vo)
ml(mm-d/++)
D mm=
(vd/2)am4dpz-
(m+
Denote the th summands of the numerator and denominator by
Vd (Vd/2)2m+d/2
[Vd/222m+d//
W(m,d d)
V(m, d) ml mm d/2)
m! T d/2
m==
Then,
W(m,d)
= d/2 & 1,
V(m,d)
m d/2
26

---

Published in Transactions on Machine Learning Research (05/2025)
equality only when 0. Therefore,
d/2 VdAa(vd) 2m=0 (mm, d)
m+d/2
<
2m= V(m, d)
Further, observe that
W(m,d) 2mmm + 1).
+ 11d)
Therefore
Em= 2m (m, d)
VdAa(Va) = V(O, d) >m V ((m,d)
and
1
V(0,d) + Em= V(m,d) V(0.d)+ + +E V(m, d)
VdAa(Va)
Em=1 2mm (m, d)
2
V(O.d) + $2 -
3
dV
2 2
Thus we conclude that 3 < VdAa(vd) < for all 121.
C.1 Proofs for Section 2
Proof of Theorem 2.2 By definition of sub-Gaussianity (4), if X2... P are Eessub-Gaussian, then the process (H)())) where
x H1( = II exp X, - -1) i
Σ,0) }.
is a supermartingale for all Rd. Lot Pe be Gaussian centered at & with covariance I- Applying Proposition 1.1 with the prior Po and family of posteriors Pa, 1 gd-1, we obtain that with probability a, simultancously for all & 3 and 0 E gd-1,
|E A,, p)po(d0) < E
Σ
X (6, po))) (po(po)) + log(1/a)
2
ig'
2 E00 E,0) 3 Tr(E,)) + B
log(1/a),
i
where we've used the formula
(N,, E1)1 E2))
'T+(: + (02 - 01, 0,, - 01)) d + log
Σg
(39)
The symmetry of the Gaussian distribution implies that [ Noticing that (0, E,0) & |E4]], we obtain that with probability a, simultancously for all 1,
- - (1) Ar(0, X; - 14)
Σ (Xx, ige
10) = sup A1 - -4) aesu
ist
X 2
(1E,)+33-1 TYE),) + 3 + +log !
which, after rearranging, is the claimed inequality.
27

---

Published in Transactions on Machine Learning Research (05/2025)
Proof of Theorem 2.8 We take our parameter space in Proposition 1.1 to be θ = IR.. Let Gaussian with mean 0 and covariance 8-1E and let Pu be truncated Gaussian with mean E /1/2gd-1, covariance "- and radius r > O. Being slightly loose with notation and writing dp, for the density of Pa the density of the truncated normal can be written as
d2 1[1 ull & r) dp dp
Z
where Z is some normalizing constant and Pa. is the usual non-truncated Gaussian. We follow Zhivotovskiy (2024) in our calculation of the KL-divergence for truncated Gaussians. For vector ///ggd1,, the KL-divergence between truncated normal and v is therefore
f log
1 dpu (0)
(KL(P,ll))
Pu (df)
Z dv
log
+
(-10- u. u)) + (0, BE (0)
%
1
3
log
(2 1)) - (u, E (0,,E~uu)) (d))
8(u, E E- llog
(1) B
log
7
2'
where we' ve used that E1/20 for some & E gd-1 80 (u, Σ -- ul) (0,0) = 1. We also have Z
Pr(110 - w|l < r) where f ~ Pu. Equivalently, Z = Pr([|Y|
& r) where Y is normal with mean 0 and
covariance 8 B- Hence 1 Z = Pr[[||]| > r) < E Y 11 3 Tr())/r² Thus, taking r (r(-)
yields Z > 1/2 and we obtain
DKL & log(2) + 3
(40)
2
Now, consider the process (L)) defined as
(f)
II
exp A (0, - loo Elexp Art0, 1/1x)_-/)2x)) Fr-11)
(41)
1
which is a nonnegative martingale with initial value as long as
log exp (0= <0.
(L.(0) is product of exponentials, each with expected value 1.) We want to use Lemma 2.7 to bound this term. Note that by the log-concavity condition, we have
-
(00, [1,0-112x,) -000)EE(00-1/)-EE0000
= 1--1200 - -w/l <c100
Moreover, 0 Pu. then by definition of the truncated Gaussian and using that |||||== || VIEII
||||| < r + ||l|| <
Ir = Lg.
Combining this with Lemma 2.7 we obtain
log E [exp Ae (<(00--1/2x) < Ae 1-1 1
(42)
if
PA/S
2CL9*
28

---

Published in Transactions on Machine Learning Research (05/2025)
(Note that the first term on the right hand side of (42) comes from the mean 11)1 that lives the left hand side in Lemma 2.7.) Now, applying Proposition 1.1 with (0) and using (42) gives that with probability 1 - a, for all E 2//2gd-1 and t 1,
Σ
E X1),,,,,,,,
Σ AE
log E exp
15- Pul(0) + 2
+ log
Σ Au + 1C Σ igt
12 + 8 + log
2
a
where the final line uses that Ps is symmetric hence (00 - 1/2 p) (dd) (u.E 12) From here, since / for some d E gd-1, the above inequality rearranges to read
Σ M - 1 < 1Et
3
x + 2
+ log
igt
2 Consider setting A 2C 1 where 0 < X, < Since & was arbitrary in the above display, we obtain that with probability 1-a, a, for all t t 1.
Eisedos Eised:
2CL is B log(2/a)
11
Eisr 7
Set = 12g(2/a) and consider choosing 3 = 20, in which case Lg Tr(E) + v [ hy(1) and the above display becomes
Eist Eisid
2C(1 (T(E) + VED E ii X
4C + -
Eieo
Eigl X 2Chs((1) Eigr X2 + 4Chx(u)
Eiee d
Eig Xi
which is the desired bound.
Proof of Theorem 2.12 By Lemma 2.10 we may apply Proposition 1.1 with the process defined by
M,(0 II (6 /b) - (A,)
for all 0 E Bd (not just for all 0 E gd-1 as is suggested by (14)). Let be a uniform distribution centered at
1 E (1 (1-1) c Bd with radius e. Proposition 1.1 gives that with probability - a- for all & E (1 - o)--11
Σ No 10.x (doo & Σ ((a) ( (0,100))o(()) + d log ( + log ig!
- ④
where we've used the KL-divergence as calculated in (15). If 0 ~ po then ||||| < ||0||| + & 1 by definition of Po and (0, E,0) & sup8, (0, Exd) & Eil. Moreover, since pa is symmetric,
Σ As / (0, (d)po(dd)
sup 0E(1- 98(1-))81-1 12
Xe(X; 11)
sup 0E(1-e)S1-1
29

---

Published in Transactions on Machine Learning Research (05/2025)
= (1 -c) .) Σ 1x,x -w) m0
FE
Therefore, with probability 1 a, for all 3 1,
A
Eise (AA + log(1/a)
Σi A
11
(i A
which is the desired result.
Proof of Lemma 2.13 If vb is CGF-like, then Howard et al. (2020, Proposition 1) shows that there exists
some a, c such that
a²²
(a) E (A)
2(1 - cA)
If A ( 0, then
a
11000
ct2
Therefore, we may write (Ae))/b (Ar) = My for some ur that goes to 0 as t + co. Therefore,
E ((A)EE Σ (bAe))
(A)
vN((,))
Σ (x)))
44
$ llg + 1)
S (d + r) log log(t).
Hence,
W₂ = Eiso |2: + log(1/o)
(1-)) A
+ r) log log(t) + d +
V [d 1/e) + r)t/log(t]122]
[Σ] (d + r) logt
which is the desired rate.
Proof of Theorem 2.16 Let X, be conditionally C.-sub-Gaussie That is,
A200 sup Ep(exp(A(v, X, [+)) & exp v
(43)
2
Note that we allow the sub-Gaussian parameter to change at each timestep. From (43) it follows that the process defined by
M, = II exp X10.X. m4) X²07
2
is nonnegative P-supermartingale for all E R. We will consider the supermartingale resulting from mixing over Gaussian:
M(( = /
(A)
(44)
30

---

Published in Transactions on Machine Learning Research (05/2025)
where is the density of univariate Gaussian with mean 0 variance a². To compute Mc(0) let D.(0) Eise (0, X₁ px), H. Eist of, and write
M.(0) 1
/ exp AD1(0)
X²
X
2 He
exp
dd
2T JAER
2a²
/
2Aa 2Aa² X2 H1a²)
av2n 2T
JAER
cxp
2a
dd.
Put 4 = 1+ Haa² and 122 = a² (0) and note that these are constants with respect to A. Rewrite the above 88
X²u + 2A01
M.(0)
exp
da
2v
AER
2a²
(A2 2Ave u1) Yd
exp
av2n
AER
2a /uee
1
(A vr/ue)² + (Ur/Ue)2
av
AEER
exp
2a /ue
dd
(A - 12/ue)2
exp
dx
aV
2T
XER
2a /
(2a2u4
exp
VuI
2a²u,
= exp
log (4))
22a2u
2
where the penultimate equality follows because the integrand is proportional to the density of Gaussian with mean vt/u u and variance a² //e. We conclude that
M. = exp { a² D(() log v1 + a2 11+ 2(1 +22H.)
(45)
is a nonnegative P-supermartingale. We can now apply Proposition 1.1 with uniform distributions as we did for sub-u distributions in Section 2.3. Let Pa be uniform distribution over the unit sphere of radius centered at (1 e)Sa-1, Using (15) bound the KL-divergence, we obtain that for all & E gd-1, with probability 1 a, simultancously for all 1,
d2
/ log / a3 Hipoo(d)) + + dloo(1//)) log(1/a) -8d-1
Jon. 2(1 a2, (d(0) &
(46)
log =log a (//( + log(1/a)..
We work with (43) instead of the more general definition in (4) because do not want the right hand side to depend on A. If it did then H, would be function of 0, and the integral on the left hand side of (46) would become too complex to solve in closed-form. Continuing with the proof, since He is not a function of 0, the above display rearranges to read
f (d))) < 2(1 a2H,) (dlog(1/c)+ + logell/))+o((oHoHHt ((++o2H,/a))
a²
Taking square roots of both sides, Jensen's inequality implies that
[.n. (((0))o(d)) <
(21 a²
(2 (2 a2. (dlog(1/c) + log (VI++ (1++22H//a))
1/2
Recalling the definition of (0) and integrating the left hand side as in the proof of Theorem 2.12 we obtain that with probability a, simultaneously for all & 1:
2( 221++a + d²Hi) (dlog(1/e) log( (VII+V>HH,00
1/2
(X m
< 1-e
a²
31

---

Published in Transactions on Machine Learning Research (05/2025)
Dividing both sides by t completes the proof.
C.2 Proofs for Section 3
Proof of Lemma 3.1 Delyon (2009, Equation (52)) demonstrates that for all x E R, expp(==22/0) & 1 + x + /²/3. If we take I = (0), then applying expectations (w.r.t. P) yields
12 exp X1x xx(0) |
|
Ep
+ X (00) + A?
(1)x
X +
3 [x & exp { A { 101
From here, note that
Ep ==
= Ep(0T (X; (X,, -1)
= =rEEr((X - -1) [F:-1]0 = =0 20.
Applying this the display above and rearranging yields that
Ep exp xxxx(())
X² x
X²
(0, Σd) Fi-1 < 1L,
6
3
which in turn implies that S()) is supermartingale.
Proof of Theorem 3.2 Tet Pa be a Gaussian with mean and covariance 3- Apply Proposition 1.1 the supermartingale in Lemma 3.1. We obtain that with probability 1 a, for all > and gd-1,
> M / (d))
X2 / x² 2,,0, + B/2 + log(1/a).
<
6
Now, let Mj be the matrix (X; - H)(x T and write
/ x²(0))o(a0)= = 0J M.Opo(d0)
= TT M20 + (T(M)
< || 3-TT((M)
= ||X: - (1 + 1-1)
< (I)x|ll + 1) + 1-1).
Morcover;
J (8. UT Σ. 8 < E TT"T)
Putting this all together, we obtain that with probability 1 - for all & E gd-1 and all t >> 1,
[ + --- + f log (1)
Σ xxx((1) < (1+8-1
6 [| + 2)
Noticing that supremum over all E gd-1 of the left hand side equals through by Eige X gives the result.
Eisr di(X, - W)| and then dividing
32

---

Published in Transactions on Machine Learning Research (05/2025)
Proof of Theorem 3.5 Suppose that X, is conditionally symmetric around the conditional mean μ for all /. > 1. This implies that for all 0 E IRd, (0, X₁ - (1) ~ -0, X, - Fi) de la Peña (1999, Lemma 1) (see also Howard et al., 2020, Lemma 3) shows that for conditionally symmetric random variables (Y))z11 with mean O, the process given by Ilg exp(A,Y, - /22, is a nonnegative supermartingale. Consider this process with Y (0, - p)), and applying Proposition 1.1 with prior Po and posteriors pa. 1 E Sd-1 (with covariance 8-1 as usual) we obtain that with probability 1 - a, simultaneously for all & > 1,
J Σ Ar - (dP) & IE
(0, X2 - po + + log(1/a).
2
Then, in the proof of Theorem 3.2 above, we note that
f - ()) (1+ bb
() (1|x;]I + u)?.
Therefore, we obtain that with probability 1 - at, simultancously for all t > 1,
X (1|x,1 |l + u) + -2 log(l/a))
Σ (0, n) < 1
sup
0E84-1 1
Taking B completes the proof.
Proof of Lemma 3.6 First, let us observe the relationship
0 0< a aAl
< a
Va > 0.
This easily seen by case analysis. Indeed, for a ž 1, we have (a A 1)/a 1/a and 1/a < & a. For 1, we have - (a 1)/a = 1 0 &
Now, let
I|
ax (X) = X|XI|
and note that the above analysis demonstrates that
(((X))1|=11 a(X) X||X|--
(47)
Therefore,
(0, 14 14) (X. B[X])
[X((XX) 1)(0,) X)
[E)((X) (1, X)
by (47) and Schwar-Schwarz | =
E 2
by assumption.
This proves the claim.
Proof of Theorem 3.7 First let us state the PAC-Bayesian theorem upon which we rely. The following,
due to Chugg et al. (2023, Corollary 15), is time- sime-uniormm extension of the bound by Catoni (2004, Equation (5.2.1)). is based on applying Proposition 1.1 to the supermartingale defined by U.(0) II (x) log (x))))((()))
Lemma C.4. Let (Xt)121 P and let (f: : over θ Then, with probability over P, for all > 1 and all distributions p over O
R} be a sequence of measuroble functions. Fix a prior
Σ Σ ((Xx,
Σ igt
log E, (x.00 (x.0) p(d0) + DKI(Pll)) + log
1
33

---

Published in Transactions on Machine Learning Research (05/2025)
As stated in Section 3, apply Lemma C.4 with the functions f) (, th, - ,4)) Keeping in mind that Eo- (0, th;((;)) ) = (1, tX;) 14",, we obtain that with probability 1 simultaneously for all t > 1,
sup
E (X.) 1 E
log B (
3 + log : 2
(48)
#E34-1
Drspo
Our second technical lemma, following Catoni and Giulini (2018), helps bound the right hand side of the above.
Lemma C.5. For all >
log E (oh1(eah(000-44)))=- |F-1) & i 2222221142 XNP
Brupo
Proof. To begin, notice that Jensen's inequality gives
/ log E (o)x(2xnn(x))aaa)
v Po(d0)
xaP
& log /
E { x.)) po(d0)
Xap
{ 2 (x.th,)))))) 22)) xx) pd(0))
= log E
XNP
Ai (0,t - /4th) + x [t; - -1/h11
= log Eexp
2
where the final line uses the usual closod-form expression the multivariate Gaussian MGF. Define the functions on
(1 (e" 1),
and
92(x) - (E" - 1),
2
(with (0) - (0) 1 by continuous extension). Both 9n and g2 are increasing. Notice that
c h - (2(2) gl (y)
(49)
Consider setting x and y to be the two terms in the CGF above, i.e.,
= \; (x;(()) - 11th);
X 23
th; (X) - 14; 112
where we recall that & gd-1, Before applying (49) we would like to develop upper bounds on æ and Observe that
[t)]| = |||X| A
X < A
and consequently,
1 < || = [Xt)h(()) < (X),
by Jensen's 's incquality. Therefore, by Cauchy-Schwarz and the triangle inequality,
tell0|||th: --4' (x(lith; || & 2.
34

---

Published in Transactions on Machine Learning Research (05/2025)
Via similar reasoning, can bound y
X
2
y <
28 (X)II + ||4 ||
< B
Finally, substituting in these values of x and y to (49), taking expectations, and using the fact that 91 and 92 are increasing gives
E exp (0,thh(() m1") +
23 |tth 12"11) Fi-11
1
1 1, (X) / | + 92 (2) 12 K10 tx) -17")
Xfe²
E[|| ([|lth;())) - 14, (3== [F,11]
+ 91
6
2/3
< 1 + g2 (2)
E1 ( - 11 | F 1| + 9n
2
X
tx)) - -1,hh (F
2
3
2,3
where we' ve used that Elth;(X), n4 [= = 0. Denote by X' an iid copy of X. Using the notation
E. E-11--- = B[- we can bound the norm as follows:
E- || (X) - 11th 1²1 = E (x)) - ||4.111
- 1
[1th;(())1 - 2(th, (X), + (..,
[|th((3]11= 2 (x), ([th,(())155-)))
E
x
+
E
[1thh 11 Fi-1
1 E
- [lthh(x)-th,(xx (x), [1
2 x.X'
1
[[X-x(1([FF]]
E
x,X'
= -E-1I|X ||X - 1 < E| v
where the first inequality uses the basic fact from convex analysis that, for a closed a convex set D C R" and any x, RT,
[x] [y)yl < x yll,
where II is the projection onto D. Putting everything together thus far, we have shown that
f log E { (2)(00tth(x)))44))
F
po(O
1302
2
X7e2
< log
1 92 (2)
2
3
2/3
X702
2
X7e²
92 (2)
+ 91
2
2
B
23
(2/1822
4
1 - 18021888
which is the desired inequality.
To obtain the main result, we apply Lemnaas C.5 and 3.6. For all & E Sd-1
Σ X (0, n)) Σ t(((t ,1th) + (0, 14th -b)) 11)
35

---

Published in Transactions on Machine Learning Research (05/2025)
tx,
-/2
0²
X2
EE!
1
12 +22
Σ
x
+
+
log
4
2
iist
< 2/
26
22 +1
Σ
X +
log
1
i
Noting that
sup thx, - /) = DES4
Σ
(xtt -
iE1
and dividing through by Eigr A gives the desired result.
D Simulation Details
Code can be found at http://ghhu...oo//hhggg/////////
Let us first describe the result of Duchi and Haque (2024), enabling us to transform any fixed-Lime estimator into sequential estimator which loses only an -eraated-ogarithhm factor. Let nn = ",, be an estimator of the mcan f which satisfies the following deviation incquality for iid observations X1,.... X,: For all n >> 1,
PP PI - A|1> F(log(L/a).n)) a,
(50)
for some function F - (0, oo). Then
Pr(ak: ||ū25 - ull> ((log(22k2/6ox 2x///),,21)) 2)) & a,
(51)
implying that the estimator defined
The
if 2*,
fic-1
otherwise,
satisfies time-uniform bound which suffers only an iterated logarithm penalty (plus some constants) over the original. We call this "doubling strategy," " the estimator is updated every 2 timesteps, k E N. Tn order to plot the boundary, at every time step t, if t = 2 for some k, we plot F(log( 1.2 //// 2*), and herrewise we plot the previous value of the boundary.
Let us turn to the experimental details.
Section 2.1. The bound in Theorem 2.2 is implemented with the parameters
2 (T)) log(1/)) X =
B + 2 2ogg1111))
3
Σ
+ 10ct)*
Theorem 2.3 is implemented directly as stated. We compute the bound of Hsu et al. (2012) as in (9), making it time-uniform via one of two methods: Either a union bound (taking a = a<((12 + 1) at each timestep t), or by the doubling method of Duchi and Haque (2024) above. In the left hand side of Figure we use Tr(E2) Tr(E) |E||= (eg distributions with identity covariance matrix). In the figure the right hand side, we fix | 1, Tr(E3) 10 and vary Tr(E).
Scction 3.3. For Theorem 3.7 we use 8 = 4 and
log(1/a)
A
20 log(t + 10e4)*
36

---

Published in Transactions on Machine Learning Research (05/2025)
We use the following bound on the tournament median-of-means estimator: With probability 1-6,
Amax log(2/5)
Tr(
p M max 240|
.600
(52)
For the geometric modian-of-means estimator, the tightest constants we could find come from the survey of Lugosi and Mendelson (2019a), which gives the following bound: With probability 1
1 Mll 4V Tr(2)) (oggl1/)))))))) (1g))))) +1)
(53)
For the GMoM estimator we fix |_||= 1 and set Tr(E) = 5 and x² 5 for all estimators. We set Tr - x² for the reasons discussed in the caption, namely we are interested in how the bounds behave as functions of their multipliers on the know variance second moment bound.
E Empirical-Bernstein bound
Suppose there exists some B E R+ such that supxex |X] & B. In this section we present an empirical- Bernstein bound, meaning a bound whose width adapts to the observations themselves, not on any a priori upper bound thereof like traditional Hoeffding or Bernstein bound. The reason we present the bound in the appendix that the width of the CSS is dimennioo--eeendeett. This is suboptimal as there exists a dimension- independent Bernstein bound for bounded random vectors (Gross, 2011; Kohler and Lucchi, 2017). Indeod, very recently, Martinez-Taboodaa and Randas (2024) gave dimension-free empirical Bernstein bound in smooth Banach spaces (using different techniques). Whether a variational approach exists to providing a dimension-free free empirical Bernstein bound remains an open question.
For any t, let jıs := ; Eisi X; be the empirical mean at time t, and define the function (A) = [log(1 - A) \| for X E 1). The following supermartingale is a multivariate analogue of that used by Waudby-Snin and Ramdas (2023, Eqn. (13)) to construct CSs, which in turn is based off of work by Howard al. (2020; 2021) that generalized a lemma by Fan et al. (2015). The proof is in Appendix C.
Lemma E.1. Suppose (Xt)ea1 satisfies sup, |||||| & B and Assumption 2. Let (Ae)121 be a predictable sequence in [0, 1). For each 0 E gd-1, the process (0) = (Ni(0)) is a nonnegative P-supermortingale, where
A 00 X₁ - 1) 2B
VE((d) (2B)² (0, -M-1))
(0) = II
exp
Proof. Fan et al. (2015, Equation (4.11)) demonstrates that for all > -1 and A E [0, 1),
expfAe <
(54)
where we recall that th (A) [log(1 A) + - - log(1 - A). In order to demonstrate that (Nr(O) is a
P-NSM, it suffices to demonstrate that
(de()e)
Ep
exp
(0, Xt - p))
(0, X₁ - 100--11-)3 TT-1)²² (2B)²
Fi-1 <
2B
for all t >> 1. Inspired by a trick of Howard et al. (2021, Section A.8), set
X, 1
P4
2
2B
and observe that Y, 8;-1 2 (X, - -1t-1) Then,
2B (0,X, -1) (2((2))
Xx
(2B)² X. - p
exp
{1e(0, Y.) -VE():))0 Y, 5, )
exp
37

---

Published in Transactions on Machine Learning Research (05/2025)
exp {o, - ()(()) exp((d(0,
Since ||0]| = 1 we have, by construction,
1 - (1Ix+1l + 11m 1
110, Yt 8--1\1 & 2B
since 11- is an average of vectors each with norm at most B. Therefore, we may apply (54) with v (0, Yi - 61-1), which, paired with the display above yields
(ee (2B)² (0, - 12-1)) EL+ Ar ------)-1 (0,())
exp 2B (0, X, n)
Taking expectations and noticing that Ep (Y/FFe---11 = 0 ggives
Ae (0 X, - -11 - (Xe)
(2B)² X, - )1-1) Frr1]
Ep cxp
2B
< (1
(6, 6,-1)) 1)) exp(A, (0, 1))) 1
where the final inequality uses the fact that + x < ex for all R. This completes the proof.
The "- " can be replaced by any predictable estimate, and is particularly important ingredient which even in the scalar setting does not immediately follow from Fan et al. (2015), but it critically changes the bound's dependence from [|| to E[||X - =ll²). Applying Proposition 1.1 to the supermartingale defined above and using uniform distributions as our priors and posteriors, we obtaín the following.
Theorem E.2. Suppose (Xe)1ş1 ~ P for any P obeging supx~p ||X||| & 1/2 and Assumption 2. Let (dt)est be a prediclable sequence in (0, and for any 0 < e <. 1. Then, for all a E (0, 1), with probubility at least a, simultaneously for all > 1,
Eigs X,X; 1
Eige (E(())) - 11-1112 - dlog(1/c) log
Eigrd Ai 11
<
(55)
(1-e) Eise
Proof. As in Section 2.3, let Pa be a uniform distribution over Bd with radius centered at 0 E (1 (1-e)8d-1 and let v be the uniform distribution over gd-1, (We note that we can consider uniform distributions over the ball because th is super- Gaussian,, see the discussion in Section 2.3 and Lemma 2.10.) Applying Proposition 1.1 to (0) from Lemma E.1 gives that with probability 1 - a, for all t > and all & E (1 - c)
Ae X, n1) = / gu
Σ
10, X; p)po(dd)
111
Σ
WE({,) X, (a=)) + (po(l)))e) + log(1/o)
- - po) + dlog(1//)) + log(1/a)
(x - - (log(1 log(//)
1s
That is, with probability 1 - a, for all t> 1,
Σ> (X, - -1)) < Σ ( dlog(1/e) + log(1/o).
sup
dE(1-cj94-1
i51
The left hand side is equal to (1 - o)
2 Ar(Xi - m||l Dividing by Σ, A results in the bound:
Eisr diXe /1 EigoN do
Exse ( (Ai)l 11-2112 + dlog(1/c) log(1/a)
11 <
(1 - c) Eiser
which is the desired result.
38

---

Published in Transactions on Machine Learning Research (05/2025)
Empiriaal Bernstein Width
Empirical Bernstein Width
6 10-1
W
1.0
Berustein- Unilorm
W
Berustein Mixture
Widtlt
x 10
CSS Width
0.6
Mixture
Mixture 2
Unif
0.4
2 10-1
6.2
0.0
20000
40000
600C)
S0000
2000
1000
8000
8000
10000
Figure 3: Left: The width of our empirical Bernstein CI as n - oo, which approaches its asymptotic width We. We use a = 0.05, d = 2, and random vectors comprised of two Beta(10,10) distributed random vari- ables. Right: Performance of our empirical Bernstein bound compared to the multivariate (non-empirical) Bernstein bound baseline, with oracle access to the true variance. Shaded areas provide the standard de- viation across 100 trials. The distributions are mixtures of betas and binomials. Mixture 2 has the lowest variance. As the variance decreases our empirical bounds get tighter and approach the tighest known oracle bounds (black and red dotted lines) (Gross, 2011; Kohler and Lucchi, 2017).
Theorem E.2 immediately yields empirical-Bernstein Cls when instantiated al a fixed time n. For intuition, note that eA((A) x X2/2 for small A, so for X; x 1/Vá for all i, the denominator is v while the numerator's first term does not depend on n. More interesting though the dependence on the variance. Below we analyze the asymptotic width of the CI under iid data when taking A; = /2dlo((1/))222lggg (ttpl///))22llg/a//a///a//
where t = + Eigo || jill² is an empirical estimate of the variance o² =2= V(X) = E[||X n1l2]. The width Wn,
(the RHS of (55)) obeys
VnW, -
/ (dlooolll/))) (2lg)))2+22l(1111 2lo((1/o).
(56)
Therefore, the width the bound scales with the true unknown variance. This can seen as a genera of known results in d = to multivariate settings. Indeed, in the scalar setting, the empirical-Berrstein bound of Waudby-Smith and Ramdas (2023, Theorem 2) gives asymptotic width of a log and that of Maurer and Pontil (2009) scales as logg/////) We might also compare our result to oracle Bernstein bounds in the multivariate setting, which assume knowledge of the variance. Kohler and Lucchi (2017), based on previous work by Gross (2011), show that if (Xt) are iid, then with probability a, 1. Eisn X, u
Bernstein
(8lom(1/a)+ Note that this bound has no dimension--eependeee
In the sequential setting, applying this result with d /d=bog(L/al/tlog results in a width scaling as o(B (og())))) where Ō hides iterated logarithm factors. Combined with the insights in the Exed-time setting explored above, we suggest taking Ae x /4+hog(//al//__ denominator is required to ensure the rale is Vlog(!/l. We emphasize that our bounds hold for all pre- dictable sequences (Ae) in (0, 1), but the precise selection matters for the asymptotic width and the empirical performance.
The extra log(t) in the
E.1 Asymptotic width
Here we study the asymptotic width our empirical Bernstein confidence intervals and demonstrate that they scale with the true variance over time.
We assume the data are iid. Let o² = V(X) = E||| - ml13]. Fix sample size n, let 6%
1 E ||x T--1l1 and consider
(dlog(1/c) + (llolo/())))))
X
Vt 4
oi_nn
39

---

Published in Transactions on Machine Learning Research (05/2025)
for constant Here define 0g = 1. Our goal is to show that there exists such that vnW,, n: where Wn is the width of the empirical-Bernsterr quantity T-r /2d (2dlog(/e)) 2 log(1/a). Our proof follows similar steps to Waudby-Smith and Ramdas (2023, Appendix E.2) who prove the result in the scalar setting. Most of the relevant mechanics still go through, however.
interval in Theorem E.2, converges almost surely to the
We build up the result via sequence of lemmas.
Lemma E.3. ã converges to x² almost surely.
Proof. Decompose th as follows:
1
2
X 11-111
| μ + p --1-1
i=1
Σ
|x
mll +
2
Σ
(X, M, Pi-1) + 1 Σ |l 111
(57)
==1
1=1
Now, by the SLLN, the first sum converges to o² almost surely. As for the second sum, write
2 Σ Xx p.p p.p-Ma 11-1)
2 71
2
X Hll| 74-1l
ill a.a. 0,
n
where almost sure convergence follows from combining the following three observations: (i) If the absolute value a sequence converges to zero, then the sequence converges to zero; (ii) If a sequence converges to a value, then its partial sums converge to that value; (iii) P:-1 converges to μ a.s., so by continuous mapping theorem || - 1 0. The third sum in (57) converges almost surely to 0 for the same reason. This completes the proof.
Lemma E.4. Eien (h:)) 111 converges to (ddlog(1/e) + log(1/o)) almost surely.
Proof. Define the function (A.) = X//8. The "H" stands for Hoefdding, and the notation borrowed from
Howard et al. (2020). Now, Waudby-Smith and Ramdas (2023) demonstrate that vz(()
40)x( + 1 as À - 0.
Therefore, we write th (b()))/n(())) 4 + 4u, where U, + 0 + oo, since X; Lemma E.3, we can write o² 2// 1 + un for some un a.s. O. Therefore,
a.s. > 0. Furthermore, by
(E()d) Vn (2:) WH (M:)) - -Aa- 11-1
bE(Ai)IX, - 11
Xf||X 11 mz)
c(dlog(1// (1ee) + log(1/a))
|X - ū 11=111
(1 + +))
2n
0
1=1
c(dlog(1/c) + log(1/a))
|X 1=111 2
(1 + ue (1 + v.).
2n
o²
Write (1 (++)((1+ + v1) + wi where Wt 0.3. 0. Then, the above sum becomes
Σ K1(1 + w;) addlog(1/e /c) + log(1/))) 1
Σ
Xr pi pi-1 1 wi)
20²
n
((dlog(1/c) + log(1/a))
10 + w
202
40

---

Published in Transactions on Machine Learning Research (05/2025)
c(dlog(1/e) + (1/a))
since in - 0² by Lemma E.3 and wy 0.3. 0.
Lemma E.5.
Eign A converyes eldlog(1/c) <(dlo((/))+log(//o)) almost surely. Vn
+
d²
Proof. Via similar reasoning as above, we can write 0/0; + 1+ us for some u, و. 0. (Here we've employed the continuous mapping theorem on Lemma E.3.) Therefore,
cldlog(1/e) + log(1/a))
A
07-171
v cc(dlog(1// log 11/a))
o²
22
dddoog(//e) + log(1/a))
where we used the fact that if a sequence converges to value then so too do its partial sums.
Now, let
W₂ Eige (1- Eise
- 111 dlog(1/c) log
(58)
(1 - t) Eiee A
be the width of our CI in Theorem E.2. We have
VnW, Eiso (n()))) 111 + d dloo(1//) log 4
11 <) Eise d;
0.a. (ddoog(1/e (1/e) + log (/(x)) log( l/e) + log(1/a)
(1 - c(d
+ log /a)//a²
log
Ve 1
2 Ve
Minimizing over gives e = 2, in which case we obtain
VnW
v /2dlog(1/e) (1/a)
1 -
41


Reviews:
[{"review_id": "nVwt40q3fS", "reviewer": "Reviewer_qnnE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n- A list of confidence sphere sequences (CSSs) in different settings, based on a common framework.\n- Good clarity and well organized results.\n\nCons:\n- I could not identify any notable weaknesses. See below for minor remarks.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors constructed confidence sphere sequences (CSSs) based on PAC-Bayes theory in non-parametric settings. The results are dimension free and include both sub-Gaussian and heavy tailed multivariate distributions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Proposition 1.1. There is no Theorem 1 in Chugg et al 2023. And there is no proof of proposition 1.1 in the appendix.\n\nIntroduction, mention applications of CSSs and its background in machine learning.\n\nMost theorems are probabilistic bounds, are there any related deterministic bounds?\n\nThe last paragraph on page 4. Give an example of applying proposition 1.1 and get a CSS.", "broader_impact_concerns": "NA (the paper is of theoretical nature).", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JUXw0Ld3Jm", "reviewer": "Reviewer_VL2T", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well written, and the description in Section 1.2/1.3 has enhanced the overall presentation and also clearly demonstrated the main contribution. This work provided results for various important distribution classes, including sub-Gaussian, log-concave, general light tailed, and heavy-tailed distributions, and many of the derived confidence sphere sequences are shown to be favorably comparable with existing ones under different situations. The technique also seems to be quite general and different choices of the martingale and posterior might influence the final bound's tightness and complexity.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of estimating the mean of multivariate data in a sequential manner and demonstrates a general framework to derive the nonparametric, time-uniform confidence sequences under martingale dependence using PAC-Bayesian techniques.\n\nThe main contribution is the application and extension of PAC-Bayesian techniques with the recent results on time-uniform bounds, which allows to derive the confidence sphere sequences under different distributional assumptions through choices of the specific martingale construction and family of posteriors thus weakening the iid data requirement to the martingale dependency.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Should it be \"The bound in (8) is therefore somewhat slightly looser\" instead of \"The bound in (5)\" in the 4th to the last line on Page 7?", "broader_impact_concerns": "There is no concern here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3RF2VXDqrQ", "reviewer": "Reviewer_MUwX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- The paper is quite exhaustive in terms of the different settings it covers.\n- I looked at the proof of a good part of the main results (apart from appendix A and some of the variants) and it seems to be sound as far as I understand. However, there are a few imprecisions (see the requested changes section.)\n- The main proof technique, based on the uniform-in-time PAC-Bayesian bounds, is very interesting. The use of these relatively new PAC-Bayesian bounds in this context is quite ingenious. Can you maybe discuss whether you are the first to use the theorems of (chugg et al.) for confidence bounds?\n- The heavy-tailed bounds seems to be the first such bounds in a multivariate settings.\n\n\n**Weaknesses**\n\n- The proof technique for the sub-$\\psi$ setting involves dealing with uniform distributions, which induces a dimension dependence of the proposed bounds. However, this seems to be also the case in the literature in such settings.\n- Some results suffer from the curse of dimensionality, even though it seems that this is sometimes impossible to avoid.\n- There are a lot of different settings and results, which might lose the reader a bit and harms the readability.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper confidence sequences for means of random vectors. As opposed to confidence intervals, confidence sequences hold uniformly over time. As the study is done in a multivariate setting, these sequences take the form of confidence sphere, ie, $P(\\forall t,~ \\Vert \\hat{\\mu} - \\mu \\Vert \\leq c_t) \\geq 1 - \\alpha$. \nThis work is motivated by the fact that few results exist in 1D and by potential applications to bandits and stochastic optimization.\nInspired by previous work, the authors use a PAC-Bayesian approach of the problem proposed by Catoni and Giulini, which they extend by using the recently proposed uniform-in-time bounds of (Chugg et al.) which they nicely combine with the variational representation of the norm as $\\Vert x \\Vert = \\sup_{\\theta \\in S^{d-1}} \\langle \\theta, x \\rangle$ through the uniformity of PAC-Bayesian bounds over the posterior distribution. This allows them to derive explicit bounds in four main settings listed below. It is to be noted that most of the result are obtained under the assumption of conditionally constant mean vector.\n\n- Subgaussian, log-concave, sub-$\\psi$ bounds: Under a conditional subgaussian assumption with adapted covariance several confidence bounds around a linear estimator of the mean. These result recover existing bounds up to an absolute constant factor but are in addition time-uniform and adapted to sequences and martingale dependence.\nThe authors then study two possible relaxations of the subgaussian assumption through log-concave and the so-called sub-$\\psi$ conditions and again recover existing results as particular cases of their theorems.\n\n- Extension to time-varying means: The authors extend the so-called method of mixtures to handle the case where the conditional mean of the random vectors is also time-varying. This is a very nice extension of the results although it might suffer from the same curse of dimensionality as the sub-$\\psi$ case.\n\n- An extension from spehre to ellipsoidal confidence is briefly discussed.\n\n- Heavy-tailed bounds: Finally, the authors prove several bounds in the case where only a finite second-order moment is assumed. The proposed bounds are dimension-free and again extend known results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In order to improve the readability of the paper, I would strongly suggest including to the main text a table to compare some of your main results with existing results in the literature. Indeed, for a non-expert of confidence bounds, it is hard to grasp which results are completely new and which are less original.\n- Similarly, I believe the large number of results and variants of the results might render the paper a bit hard to read, so maybe some results (like the instantiation at $t=n$ or some stitching results) could be only discussed in the appendix, or mentioned through a table in the main text. Similarly, the discussion of all the possible cases of sub-$\\psi$ distributions page 10 might be moved to the appendix.\n\nRegarding the theoretical claims and proofs, I noticed the following imprecisions, which should be addressed:\n- Can you detail more the proof of Lemma 2.6, I am not sure to understand the lower bound on $H_n$, unless I misunderstood the notations. The same remark apply to the bound on the function $h_\\Sigma(u)$.\n- The notion of uniform distribution with radius $r$ is not clearly defined, you should mention that you mean uniform over a ball.\n- There is a confusion between balls and spheres. For instance in section 1, the notation $S^{d-1}$ refers to the sphere of radius 1 while in equation 16 the same notation is clearly used for a ball (otherwise there is no absolute continuity). Moreover I believe the formula for the volume is wrong and $\\pi^d$ should be replaced by $\\pi^{d/2}$.\n- Proof of them 3.5: there is a square missing in the second line (first term), it seems to be just a typo.\n- Proof of Lemma 3.6: i think you don't need to invoke Jensen and just use the assumption of bounded variance.\n- Do you need to use 2 pages to reprove Lemma B.3? You mention that it follows from existing work.\n- Proof of them 2.8: there is a confusion in the definition of $\\bar{\\rho}_u$, is it truncated or not? Words are missing in the first sentences of this proof. In the KL computation, why is the last step an inequality (it is equal)? In the second line of the Kl estimation, there is a minus sign missing in the integrated. At the end of the proof there is a conflict of notation with $u$.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper astutely uses time-uniform PAC-Bayesian bounds to the problem of confidence sphere estimation. The authors prove results including for heavy-tailed random vectors. This should attract some interest in the community. Congratulations on a fine piece of work.
Decision: Accept (poster)