Sharp Matrix Empirical Bernstein Inequalities
Authors: Hongjian Wang
Aaditya Ramdas
Venue: NeurIPS 2025 poster ()
Keywords: random matrix
empirical bernstein inequality
concentration inequality
Primary area: theory
TL;DR: Two closed-form empirical Bernstein inequalities that are as sharp as the non-empirical ("oracle") Bernstein inequality for matrices.

Abstract: We present two sharp, closed-form empirical Bernstein inequalities for symmetric random matrices with bounded eigenvalues. By sharp, we mean that both inequalities adapt to the unknown variance in a tight manner: the deviation captured by the first-order $1/\sqrt{n}$ term asymptotically matches the matrix Bernstein inequality exactly, including constants, the latter requiring knowledge of the variance. 
Our first inequality holds for the sample mean of independent matrices, and our second inequality holds for a mean estimator under martingale dependence at stopping times.

Sharp Matrix Empirical Bernstein Inequalities
Hongjian Wang
Aaditya Ramdas
Department of Statistics and Data Science Carnegie Mellon University Pittsburgh, PA 15213 hjnwang@cmu, edu
Department of Statistics Data Science Carnegie Mellon University Pittsburgh, PA 15213 aramdas@cmu, edu
Abstract
We present two sharp, closed-form empirical Bernstein inequalities for symmetric random matrices with bounded cigenvalues. By sharp, mean that both inequal- ities adapt to the unknown variance tight manner: the deviation captured by the first-order 1/ /i term asymptotically matches the matrix Bernstein inequality exactly, including constants, the latter requiring knowledge of the variance. Our first inequality holds for the sample mean of independent matrices, and our second inequality holds for mean estimator under martingale dependence at stopping times.
Introduction
We are interested in nonasymptotic confidence sets for the common mean of independent or martingale-dependent bounded random matrices that optimally adapt to the unknown underlying variance. We first review the scalar case to set some context.
1.1 Background: Scalar Empirical Bernstein Inequalities
The classical Cennett-Bernsteee inequality (see Lemma 5 Audibert et al. (2009]: also Appendix B.J states that, for the average X, of independent random scalars XI...., X,, with common expected value fa I,X;, common almost sure upper bound Xx]] < B, and second moment upper bound
EX² < no²
B log(1/a)
20 log(1/a)
P Xn.
& a.
3n
It is clear that remains true if the assumptions are centered instead: [X ml < B and Σ Var(X,) no?. A crucial feature of ① is that if o² x EX² < B², the deviation is dominated by the "variance term" e (Vn-lo² (og(lo)log((/a) log(l/a))
tighter than the "boundedness term" O (lon-B)log((/aa that dominates if Hoeffding inequality [1663 is applied instead in the absence of the variance bound a
In practice, often knows B but has prior access the possibly much smaller a. Thus, such bounds are usually only used in theoretical analysis, but not to practically construct confidence bounds for the mean. For the latter task, so-called nonasymptotic empirical Bernstein (EB) inequalities therefore of particular interest. These inequalities often only assume the almost sure upper bound B of the random variables and are agnostic and adaptive the true variances Var(X,), to the effect
that the final deviation is still dominated by asymptotically è (Vn-lo² log log(1/a)) variance
term, instead of O(vn" n 12 (olog((/a) from Hoeffding's s inequality under the same boundedness assumption.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Scalar EB inequalities are derived from two very different types of techniques. First, union bound between non-empirical ("oracle") Bernstein inequality and a concentration inequality on the sample variance, which is employed by early empirical Bernstein results (Audibert et al. 2009 Maurer and
Pontil| 2009 For example, for i.i.d.. [0, 10] -bounded .I...., X
and their Bessel coorel-e sample 2009 Theorem 4] prove the EB inequality
variance n> Maurer and Pontil
2 log(2/a) + 7 7log(2/0)
P
X
< a.
(2)
3(n - 1)
Second, the self- normalization martingale techniques Howard et al. [001] Theorem 4] and Waudby Smith and Ramdas (2023), which enable sharper rates, stopping time-vai valid concentration, martingale dependence, and variance proxy by predictable estimates other than the sample variance. For example,
Waudby-Smith and Ramdas [2023] Theorem 2, Remark 1] prove the following EB inequality for [0. 1|-
bounded random variables XI,.... X, with common conditional mean
E XI,
X;-1]:
log((1/o)) (I
P
An
E a
(3)
Above, fi, a particular weighted average of XI...., X.. and Vn = V(a, Xi,..... .,,). a quantity depending on the sample and that converges 0² almost surely in the + oo limit, if XI,..., have a common conditional variance o².
These exact terms will become clear when present matrix result later in Section 4 (taking 1), but one can already notice the important fact that (3) matches ①T asymptotically without requiring known variance bound: letting D, /2 log(1/a)V/: be the deviation term of 3
VnD,, + log(L/a)o
Beaettttn inequality (I's 's deviation term. A one-sided scalar EB inequality is said to be sharp if its deviation term D, satisfies the oracular limit (4): its first order term, including constants, asymptotically matches the oracle Bernstein incquality which requires knowledge of o². We see that while (3) is sharp, (2) is not sharp.
limit also attained by the oracle
Indeed, these two methods are inherently different and as argued convincingly by Howard et al. [2021] Appendix A.8]: the latter's s avoidance of the union bound produces a better concentration. Waudby-Smith and Ramdas (2023) were the first ones to prove that their EB inequality is sharp, pointing out that the union bound-based inequalities are not sharp (but only slightly so). We further discuss this issue in Appendix B.2 showing that one can make the Maurer-Pontil inequality (2) sharp by using a smarter union bound, but it still is empirically looser than B3. Other EB inequalities have been proved in the literature in between the above sets of papers, but they even looser than the original, so we omit them.
1.2 Our Contributions: Matrix Empirical Bernstein Inequalities
Exponential concentration inequalities for the sum of independent matrices are in general much harder obtain. Tropp 2012 Theorem 6. proved series of BenneettBerrnttinn inequalities for the average X, of independent x d symmetric matrices X XI..-- X,, with common mean EX; M, common eigenvalue upper bound Amax (X;) & B, and Σi EX 3 nV. For example, the Bennett-type result implies the following (II being the spectral norm),
B Blog(d/a)
2 2log(//a)]l
P
Amax
X
M)
(5)
3n
n
The analogy between and 5
is straightforward to notice, including matching constants. See Appendix B for some remarks on these two empirical Bernstein results and a proof of (5).
We
shall explore some of the techniques by Tropp [012) later when developing our results.
The main contribution of the current paper in analogy to the two methods in the scalar case mentioned earlier. First, we generalize the union
empirical Bernstein inequalities for matrices derived
bound and plug-in techniques by Audibert et al. 2009) Maurer and Pontil 2009 matrices and obtain:
'This was originally proved by Waudby- Smith and Ramdas 2023 under i.i.d. assumption. We prove it under
martingale dependence in matrix result.

---

Proposition 1.1 (Theorem 3.1 of this paper. shortened). Let n be even and Xi...., Xn be i.i.d. symmetric matrices with eigenvalues [0. 1] and mean M. Let V be the paired sample variance n-
(X11 x2)² + (X3 xx)² + +..+ (X -x,)), Then,
V || log nd
(n-1)
log(nd/a))
P Amax X - M)
O
< aa
(6)
Second, we provide a faithful generalization of to the matrix case which we informally state as follows.
Proposition 1.2 (Corollary 4 of this paper, shortened), Let X1, X,, be symmetric matri- ces with eigenvalues in [0. and common conditional mean M , X.-1). For an appropriate weighted average M,. of Xi....; Xn and an appropriate sample variance proxy Un,a v(a, X1,-..; X,)
2 2 llog(d/a)vna
P Amax((Mn
- MM) >
& a.
(7)
Further, [X:} have a common conditional variance V, Un.a converges almost surely to V
The detailed description of M,, and Un,a will be furnished in Section As in the scalar case, we say a one-sided matrix EB inequality is sharp if its deviation term D, satisfies
VnDa a /llo(d//a)lVi
(8)
does that of the oracle inequality 5 We that both results above are sharp matrix empirical Bernstein inequalities. is also worth remarking that both (3) and our matrix generalization 7 are special fixed-time cases of some time-uniform concentration inequalities that control the tails of all {in)ne [M,) simultaneously, enabling sequential analysis. This will become clear develop our results.
In applications e.g. covariance estimation, our matrix EB inequalities can lead to tremendous improve- ments over the oracle matrix Bernstein inequality (5). To the best of our knowledge, the only other matrix EB inequality in the literature is the contemporaneous result by Kroshnin and Suvorikoval 22024, Corollary 3.5], which is not sharp. Besides the work cited above, some other authors have empirical Bernstein inequalities. These include EB inequalities for vectors by CCugg et al. [202]]. for Banach space elements by |Martinez Taboada
also contributed to the literature of Bernstein
and Ramdas 2024): time-uniform oracle matrix Bernstein inequality by Howard al. [021];
dimension-free version of (5) by Minsker (2017]: and another oracle matrix Bernstein inequality by |Mackey al. (2014). Some of these will be discussed in Section We also diseuss some
other closed-fore scalar EB inequalities by Tolstikhin and Seldin [2013] Mhammedii et al. (2019)
Mhhammei] 2021 Jang al. [2023]. OOrbooaa and Jun [2024). Shekhar and Ramdas [2033 in
Appendix
2 Preliminaries
Notation Let Sa denote the of all d x d real-valued symmetric matrices, which is the only class of matrices considered in this paper. These matrices are denoted by bold upper-case letters A, B, etc. For / C IR, we denote by S the set of all real symmetric matrices whose eigenvalues are all in I. s(0000, the set of positive semidefinite and (0).)))) the set of positive definite matrices are simply denoted by S and S++ respectively. The Loewner partial order is denoted <, where A < B means is positive definite. We use Amax to denote
B A is positive semidefinite, and A < B means the largest eigenvalue of a matrix in Sa. and || || its spectral norm, i.e., the largest absolute value of cigenvalues. As is standard in matrix analysis, a scalar- to-scll function f canonically with matrix tos-tto-mmattt oo-marrix function St St. following the definition
is identified
(9) Matrix powers * logarithm log X, and exponential exp X are common examples. It worth noting
f U diag/Ai..... U UT di) f(x)
that the monotonicity of f + J is usually not preserved when lifted to f S - S in the =
3

---

order. The matrix logarithm, however, is monotone. On the other hand, for any monotone f f + J, the function tr o f S + I. is always monotone.
We work on a filtered probability space (2, P) where F (F [ a filtration, and we assume Fo = (2. We say a process X == {Xn] is adapted if X,, is Fx Fn-measurable for all integers n 0 or sometimes n e 1; predictable if X, is Fa Fmes-uuusurrble for all integers n e 1.
Nonnegative Supermartingales Many of the classical concentration inequalities for both scalars and matrices are derived via Markov's inequality. Howard et al. [2020] pioneered using Ville's 's inequality for nonngative supermartingales to construct time-uniform concentration inequalities. An adapted scalar-valued process {_xn hn3o is called a nonnegative supermartingale if X,, > 0 and E[X,+1| [r)] Xn for all > (all such inequalities are intended the P-almost sure sense). Let us state the following two well-known forms of Ville's inequality, both generalizing Markov's inequality.
Lemma 2.1 (Ville's inequality). Let {Xn] be a nonnegative supermartingale and {Yn3 be an adapted process such that Yn & for all n. For any a E (0, 1].
IP (supn20 Yn 3 Xo/a) aa.
(10)
Equivalently. for any stopping time
P(Y > Xo/a) & a
(11)
MGF method cannot be directly applied to the sum of independent random matrices due to exp(A A + B) j (exp A (exp B) in general. [Tropp [012 introduced the method of controlling the trace of the matrix CGF via inequality due to Lieb [973]. The Lieb-Tropp method is later furthered by Howard et al. [2020] in turn to construct a nonnegative supermartingale for matrix martingale differences. We slightly generalize it as follows.
Matrix CGF Supermartingales The Chernoff-Crame
Lemma 2.2 (Lemmaa 4 in Howard et al. [2020), rephrased and generalized). Let {Zn} be an Sa- valued, adapted martingale difference sequence. Let {Cn] be an Sa-valued adapted process, {C₂} be an Sa-valued predictable process. If
B(exp(Z,, Cn)) exxp(C,),,
(12)
holds for all n, then the process
Ln= = tr exp (E Z; -E= C)))
(13)
a nonnegative supermartingale. Further,
Ln > exp (Amax (E Z.) Amax CE (C. C))))
(14)
We remark that in the supermartingale 13 since the empty sum is the zero matrix, Lo = tr exp = trI d. This will translate into the log(d)- dtyypp dimension dependence in our bounds. The above lemma is proved in Appendix A.3
3 First Matrix EB Inequality: Plug-In
The scalar EB inequality (2 by Maurer and Pontil 2009 Theorem 4] is derived via a union bound between the non-empirical Bennett-Bernstein inequality (1) and lower tail bound the Bessel- corrected sample standard deviation. We slightly deviate from their construction by restricting the sample size n to even numbers (discarding observation if n is odd) and considering the following "paired" variance estimator
1 - 11
V
Xx) + X,) (X,-1 (0,-1-
(15)
Our first matrix EB inequality follows from applying the non-empirical matrix Bennett-Bernstein inequality twice, to the sample average and the paired variance estimator above.
Theorem 3.1 (First matrix empirical Bernstein inequality). Let n > 2 be even and XI,..., Xn be ( -valued independent random matrices with common mean M and variance V. We denote by

---

Xn their sample average and by V their paired variance estimator defined in 15 (0,1) 1),
Then, for any
P (Amax (X, - -M)
D E a,
(16)
where
V (log (a- Ty-1ya) (log 2nd
log nd
2 V
log nd [n-1ja
+ {V3 +
Dmeel
in-1)a
(17)
3n
n
Further, if X1,..... Xn are ii.dd.
lim VDD v 1oog(d/// [VI, almost surely. n2000
(18)
Proof Sketch. The inequality follows from the following lower tail bound on |
P [VII < 12
(V
1
log(2d/a)
> 1-a,
(19)
/2
n
and the matrix Bennett-Bernstee inequality full proof can be found in Appendix A.4 A.4
5 via an a arn - 1)/n /n + a/n union bound. The
The first order term of the deviation radius 17 matches the oracle matrix Bernstein inequality 5
|V log(d/a) variance term. More importantly, the match is precise both being the θ (Vn (V=-1IV
asymptotically, as is indicated by the limit (18) of /nDmmeb., It is therefore sharp matrix EB inequality by our standard. Indeed, this owes much the imbalanced the union bound in the proof; if a balanced, or more generally n-independent split was employed, the limit would become / /ogog(Cd/o V for some constant C > instead. A balanced split, however, exactly what Maurre and Pontil [2009] do in their scalar EB inequality (as well as Kroshnin and Suvorikova| [2024] concurrently in their matrix EB inequality), ), leading to the intraloaarithmic factor C as shown in (2). This non-sharpness of the scalar Maurer-Pontil inequality (2). we remark, can be avoided as well by switching to the a(n 1) 1)/n a/n imbalanced split instead, which leads to both theoretical sharpness and significant boost in large-sample empirical performance. We write it down formally and perform comparative simulations in Appendix B.2
a(n -1)/n -1///aa///////n +a/n split in
Beyond sharpness, the second order term of the deviation radius [7 also has the same rate as the oracle matrix Berntein inequality (5) up to a logarithmic factor in n. both being the boundedness term that decays as Ó(n-1 ) as the sample size grows. The second order term of (1 also matches the second order term of the sharpened Maurer-Pontil inequality derived in Appendix B.2 with only slight inflation of the constant. We remark that Maurer and Pontil (009 employ self- bouddiinnnng technique on the "classical" Bessel-corrected scalar sample variance 0% and we are not aware such technique exists for random matrices, leading us to opt for the paired sample variance (15). In Appendix B.3 we derive an alternative Maurer-Ponte Pontil-style matrix EB inequality using the classical matrix Bessel-correcte corrected sample variance and bound it via the matrix Efron-Stein technique due to Paulin et al. 20166). The resulting matrix EB inequality is still sharp due to the similar first order term, but its second order term inflates from Ó(n -1) to Ó(n (3/1) and has slightly worse empirical performance.
4 Second Matrix EB Inequality: The Supermartingale Method
Our second matrix EB inequality avoids the analysis of the sample variance via the exponential supermartingale technique and opens up for dependent matrices. Let us, following Howard et al.
2020 2021 J. Waudby-Smine Smith and Ramdas [2023), define the function v/r [0, 1) - [0, xc) as (p(())
log(1 7) 7. The symbol WE is from the fact that it is the cumulant generating function (CGF) of a centered standard exponential distribution. The following lemma matrix
generalization of Howard et al. [202]] Appendix A.8], which we prove in Appendix A.5
5

---

Lemma 4.1. Let {X,,, y be an adapted sequence of Sa-valued random matrices with conditional means B(X,|Fn- Mn. Further, suppose there is a predictable and integrable sequence of Sa-valued random matrices {Xn} such that Amin (X, xn) 3 -1. Let
En exp(Tnn (X.. -Xn) (X Xn))), Fn exp(1n &n)), where }na predictable (0, 1)-valued scalars. Then,
(20)
EEE, Fn-1)) Fn.
(21)
We are now ready to state in full our matrix empirical Bernstein inequality based on the self- normalization technique. The following theorem is stated as combination of three tools: negative supermartingale, a time-uniform concentration inequality, and an equivalent concentration incquality at a stopping time.
Theorem 4.2 (Time-uniform and stopped matrix empirical Bernstein inequalities). Let (X,,) be an adapted sequence of Sa-valued random matrices with conditional means E B(X,)Fn-1) = M,. Let
[xn] be sequence of predictable and integrable Sa-valued random matrices such that Amin (X,: Xn) 2- -1 almost surely. Then, for any predictable (0, 1) 1)-valued sequence }rn
R EnxX: M,) - Σ (e(%))(X 8.)²
mmab2
exp
(22)
is supermartingale. Denote by X, the weighted average X1 t w.r.t. the positive weight sequence }.n... Then, for any 1).
ntt"4
log(d/a) Amax
(Er (E(TT)((; X,)²)
there exists n > 1, Amax X M₁,)
& aG
21 +
770
(23)
and for any stopping time T, a E (0,1),
log(d/a) + Amax
(ET t (b(()) - xx,12)
P
Amax
X -.-M)
(24)
71 + +
Proof. Due to Lemma
4.1 we can apply Lemma
2.2 with Zn =ma (X,, - -M,)) Cn = =7n(8
M,) + (7m))((X,, X,) )² and C²2 7n (M, X,.) to that
meb2 tr exp
[ n Ci (X, MM) El ve(+)( -8,))
(25)
is a supermartingale, which upper bounds
exp Amax
Ei (X, M.) -mmax
En the (x))))
-x)
(26)
Applying Lemma 2.1 to (26). the desired result follows from rearranging.
Before we remark on the uncompromised Theorem 4.2 let us write down its fixed-time, fine-tuned special case of (24) with
and conditionally homoscedastic observations. This shall justify the "empirical Bernstein" " name bears.
Corollary 4.3 (Second matrix empirical Bernstein inequality). Suppose a E (0, 1). Let XI..... X, be adapted s -valued random matrices with constant conditional mean M [EX; 1i and constant conditional variance V E((X M) Let X, Define the following variance proxies
X.) and X,
5 5log(d/o)
V
I
V
1xx
JP = |
(27)
k

---

and set 7/s
(loo(d//)) for ly..., nu Then,
< a, where D log(d/a) + Amax (Ei=1 ( - -x,-)
P
(Xmax
X
M)
Dmbb2)
n1 + 7n
(28)
Further, asymptotically,
lim VrDmm V log(d/a)][V)
almost surely.
(29)
We prove Corollary 4.3 in Appendix A.6 The asymptotic behavior (29) of deviation bound D is satisfying as it adapts, to, without knowing, the true variance V. In particular, if the assumption
on the known spectral bound is X 11:.... X, E Sla.b) as opposed to the 5/0.1] stated in Corollary 4.3
one can apply the result to X1-a X to obtain the same b-a
b-a
log(d/a)[V]]
(30)
asymptotic deviation which is free of b
The three kinds of result stated in Theorem 4.2 are for potentially different purposes. The super- martingale (22 is best sequential test for the null
Ho E(X,,
Mrull for all m
(31)
by setting each M, M The time-unifore concentration inequality 23 be used to construct
a "confidence sequence" on the common conditional mean M = E(X,, F -1); that is, a sequence of
confidence balls B, (M's E Sa X || & Pm such that P(M 0, B,) > a, leading to the stopped concentration inequality (2) which is valid confidence ball a fixed stopping time
B,. We also remark that it is possible to sharpen the confidence ball B, at fixed stopping time
by an priori randomization, due to a recent result by [Raddas and Manole 2024 Theorem 4.1] called "uniformly randomized Ville's inequality". That is, letting U ~ Unif(o, independent from the filtration F, one may replace the log(d/a) term in (24) with the strictly smaller log(Ud/o))
The meesuuuae term X, in Theorem 4.2 is best understood as "plug-in prediction" of the next observation X,. Indeed, whereas the inequality holds under all choices of X,, the smaller the "prediction error" (X; x.) the tighter the bound. Thus one may set X; to be the sample average from X to X,-1, which is exactly what is done in Corollary
On the other hand, if the sample size is not fixed in advance and infinite sequence of i.i.d. (or homoscedastic more generally) observations 1,; X to construct a tight time-uniform concentration bound powerful sequential test, recommend setting the weight sequence f%n as follows: for each sample size n, temporarily assume that a sample size of n is fixed in advance, compute the optimal choice of weight on X,, under this fixed sample size, and %n this optimal 2log(d/a) ne.-1
choice of weight. This will lead vanishing sequence of 7n sequence, we see the choice of weighted average
Under this weight
x,
(E(7)
EE vE(x))X
(32)
iml (E(T7)
more reasonable as the weighted sum of squares En wh (7) x))² is minimized by the weighted average
8 En_ 1e(7))
(33)
カ= the (7:)
Of course, as long as X,, is any convex combination of X X the condition Amin (X,, x,,) -1 met when (X,) all take values in s|0.1| Finally, as a reprise the shortened version Proposition 1.2 stated the opening, the "approprioate variance proxy" Un.a v(a, XI, X., is simply
log log(d/a) Amax (Eih, the 1E(7) xx-1)?)
2
Un.a
+ ... 7n
2 llg(d/a)
(34)

---

which converges almost surely to | under conditional homoscedasticity due to 29
5
Comparisons
5.1
Self-Normalized EB Inequalities for Scalars and Vectors
Our Theorem 4.2 and Corollary 4.3 owe much to the techniques developed by Waudby-Smin and Ramdas [2023 T Theorem 2 and Remark 1] in the scalar case (who in turn build on the earlier result
by Howard al. [2021] Theorem 4] via the "predictable mixing" sequence { In particular, when d = I. our statements match (including constants) exactly the scalar empirical Bernstein
inequality counterparts by WWaudby-Smith and Ramdas [2023]: : Our supermartingale (22) coincides
with Equation (13) in Waudby-Smith Smith and Ramdas [2023]] our time-uniform concentration bound
23 becomes identical to Theorem 2 in Waudby- -mmthh and Ramdas [2023]; and our fixed-time
asymptotics (29) recovers Equation (17) in Waudby- -mithhh and Ramdas [2023). We also note that
Waudby-Smith and Ramdas 2023] assume i.i.d.ness to obtain the fixed-time asymptotics, which,
according to our result, can be relaxed to martingale dependence.
As can be expected, applying vector bound to matrices (by flattening) will lead to very suboptimal result. The colf-normalized empirical Bernstein inequality for vectors due to CCugg et al. (2025 Corollary 5] implies the following for matrices whose Frobenius norm bounded by 1/2, for all & 0.1,
log log(1/a)0f, aa.
MM, M > 3.25
(35)
n
Here, 03 converges almost surely to the vectorized variance E E with i.i.d. matrices. Since everything (assumption and result) is in the Frobenius norm, however, translating the result into the spectral norm will incur dimensional dependence polynomial in d.
Finally, we note that the self-normalized empirical Bernstein inequality for Banach spaces due to Tarbinez-Taboada Taboada and Ramdas [2024] is not applicable as S. equipped with the spectral norm is not a 2-smmooth Banach space.
5.2 Non-Empirical Matrix Bernstein and Hoeffding Inequalities
As we state in the opening and elaborate further in Appendix B.1 Tropp [2012] The- orem 1.4] proves the following matrix
inequality under the assumptions
gax Amax (X,) < 1 and TM
1= EX2 I nV:
B Blog(d/a) 2 2log(d/a)][V
P PAmma Xn EX,)
D & a, Dtb
(36)
3n
n
We that with i.i.d. matrices with variance V, vnD converges to v log log(d/o) V which is the same limit that both mnDm and /nnDmeb2 converge to, stated (18) and (2). Therefore, our empirical Bernstein inequalities provide a confidence region fully adaptive to the unknown variance V and match in asymptotics this oracle Bernstein result which requires V to be known. Both are thus sharp EB inequalities. Assumption-wise, is important to note that it is fair to compare
our X, [0.1] assumption their Amaxx (X;) & 1 assumption; no constant is glossed over in making this comparison when and two-sided bound is sought. To see this, the bound by (Tropp) 2012
Theorem 1.4] can be applied to X, M... ... X,, M, and it takes X E s00.1 to ensure both
Amax [1 - M)
< and Amax ( (-X, + M) < hold.
Mackey et al. 2014 Corollary 5.2] also obtain matrix Bernstein inequality. However, as they acknowledge in the paper, their bound is strietly looser than the bound by Tropp [2012] Theorem 1.4).
The bound by Minsker [2017] Theorem 3.1] under the same assumption reads
B log(d /a) + / B log" (d'/a) + 18n log ('/d
IP (Amaxe (X,- EX,) > mmb) & a,
Dmb
3n
(37)
where d' 14tr 14Lr(V)/IVi) which decides the dimension-free virtue of their result. Matrix Bernstein inequalities that are either untiime-vaid empirical remain open problem.
8

---

Finally, we quote the tightest known Hoeffding type inequalities for matrices in the literature. Mackey
al. [2014, Corollary 4.2] shows that independent X I...... Xn satisfy (X; EX,)² surely, then
B almost
2 B log(d/a)
Amaxx (Xn, EX,)
a.
(38)
n
A time-uniform extension can be achieved by applying Lemma 3(h) in Howard et al. 2020 but its fixed-time corollary remains identical as (38). The squared boundedness assumption (X; EX =
B implies X; EX; S/-1IB|
|B||| I'2 //B||/
it is a stronger assumption than the boundedness assumption we make in Corollary 4.3 Further, since (Xę - EX,)² B implies Var(X;) = B and in practice this gap can be arbitrarily large, we see that our empirical Bernstein inequality is asymptotically tighter and the worst that can happen is a degradation this, already tightest, matrix Hoeffding bound, when || Var(X;) 2 |B]]
The advantage of matrix EB inequalities becomes clearer when consider the recurring application example in the matrix concentration literature: covariance matrix estimation.
Example 5.1 (Adaptive covariance estimation). Let X1, ................................ Xn, be i.d. random vectors in R with || & 1 almost surely, mean EX1 = and covariance matrix B(X, = Σ. Since
Amax (xxx)) tr(X,x)) xx <
(39)
we can invoke either of the two matrix EB inequalities (Theorem 3.1 or Corollary 4.3 with X; x and M = Σ to construct confidence sets for that are adaptive to the unknown 4th moment E 12 x
In comparison, covariance estimation bounds derived via (5) or its variants always have the unknown |Σ]| term in the radius of the concentration, from bounding the 4th moment E[||X; x|=X, = X(X,X;]) = Σ [Tropp 2015 Howard et al. 2021]. To turn them into nonasymptotic confidence sets, further boundedness argument |>]]] & is required, essentially reducing the Bernstein bound to Hoeffding bound which can be arbitrarily loose. The sharpness of our EB EB-baaed methods immediately benefits the downstream applications of covariance estimation in e.g. machine learning and signal processing.
5.3 Simulation
We compare the terms, Dmebl of the first matrix empirical Bernstein inequality as in (17), and Dmme22 of the second matrix empirical Bernstein inequality as in (8) divided by that of the oracle matrix Beneettneee inequality 1th in (36). We set to .05, thus comparing the tightness of one-sided 95%-confidence sets (or equivalently, the spectral diameters of two-sided 90%-confiience sets). The i..dd random matrices are generated from fixed orthonormal projections with d = 3, each with an independent Unif fo eigenvalue. The comparison displayed in Table We see that while for both matrix EB inequalities, the deviations relative to the oracle Bernstein are proved to converge as increases, our second matrix EB inequality achieves such "oracular convergence" at a much faster rate. A comparison in the scalar case can be found in Appendix B.2 which conveys a similar message.
Sample Size (n)
Dmeel /Dtb
Dime22 / Lbb
100
2.612
1.397
1,000
1.589
1.105
10,000
1.214
1.022
100.000
1.072
1.007
1 1,000,000
1.024
1.002
Table Relative lengths of 95% one-sided confidence sets by two sharp matrix empirical Bernstein inequalities compared to the (oracle) matrix Bennett-Bernsted inequality (5).

---

Summary
We provide two new matrix concentration inequalities in this paper. The first one is based on the union bound method, and characterizes, in terms of the paired sample variance, the concentration of the sample mean of independent symmetric matrices with bounded largest eigenvalues, common mean, and common variance. The second one is ceff-normalized, time-uniform concentration inequality for the weighted sum of martingale difference symmetric matrices with bounded largest eigenvalues, which when weighted properly. becomes an empirical Bernstein inequality that echoes many of the previous pall--ormmliied-tyye empirical Bernstein inequalities for scalar, vectors, and Banach space elements.
These matrix EB inequalities have different advantages: the first is conceptually simpler, requires only the sample mean and sample variance, and is computationally easier (both needing (nn) steps but the first one having smaller constants); the second EB is empirically tighter across all sample sizes, allows martingale dependence, and has a time-uniform version. According to our simulation, the second matrix EB inequality's confidence set only 10.5% larger compared the oracle Bernstein inequality under sample size of 1,000; and 2.2% under a sample size of 10,000. On the other hand, our two matrix EB inequalities both have closed-form expression, and they match in asymptotics the best non empirical matrix Bernstein inequality in the literature, as they only depend (in the large sample limit) on the true variance of the matrices which is not required be known in our bounds, but required in non-empirical bounds. We expect future work to address the challenging problem of unifying our methods with those of the dimension-fee matrix Bernstein inequality by Minsker 20177]
Acknowledgments and Disclosure of Funding
We thank Diego Martinez-Taboadaa and Arun Kumar Kuchibhotla for helpful discussions. We thank an anonymous referee for pointing out an improvement for Section
References
P. Alquier. User-friendly introduction to PAC-Bayes bounds. Foundations and Trends in Machine Learning, 17(2):174-303, 2024. ISSN 1935-8237. doi: 10.1561/2200000000.
J.-Y. Audibert, R. Munos, and C. Szepesvári. Exploration tradeoff using variance estimates multi nuldi-armed bandits. Theoretical Computer Science, 410(19):1866-1902, 2009.
B. Chugg, H. Wang, and A. Ramdas. Time-uniform confidence spheres for means of random vectors. Transactions Machine Learning Research, 2025. ISSN 2835-8856. URL https //openreviex nwt htc//formmeee 2NS33333J3
X. Fan, Grama, and Q. Liu. Exponential inequalities for martingales with applications. Electronic Journal of Probability, 20:1 - 22, 2015. doi: 10. 10.1214/EJP.v20-3499
P. Hall and C. C. Heyde. Martingale Limit Theory and its Application. Academic press, 2014.
W. Hoeffding, Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963.
S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon. Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys, 17:257-317, 2020.
S. R. Howard, A. Ramdas, J. McAuliffe, and Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055-1080 2021.
K. Jang. K.-S. Jun, I. Kuzborskij, and F. Orabona. Tighter pac-bayes bounds through coin-betting, In G. Neu and L. Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2260.2264. PMLR, 12-15 Jul 2023.
A. Kroshnin and A. Suvorikova. Bernstein-type and bennett-type inequalities for unbounded matrix martingales. arXiv preprint arXhv:2411.0787,, 2024.
10

---

E. H. Lieb. Convex trace functions and the Wigner- Yanase- conjecture. Les rencontres physiciens-mattie maatemitinnnn de Prasbourg-RCP253 19:0-35, 1973.
L. Mackey, M. I. Jordan, R. Chen, B. Farrell, and A. Tropp. Matrix concentration inequalities via the method of exchangeable pairs. The Annals of Probability, 42(3):906 945, 2014. doi: 10.1214/13-AOPS9)
D. Martinez- Martinez-Taboada Taboada and A. Ramdas. Empirical Bernstein in smooth Banach spaces. arXiv preprint arXiv:2409.06000 2024.
A. Maurer and M. Pontil. Empirical Bernstein bounds and sample variance penalization. 22nd Annual Conference on Learning Theory, 2009.
Z. Mhammedi. Risk-monotonicity in statistical learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393.
Z. Mhammedi, P. Grünwald, and B. Guedj. PAC-Bayes un-expected Bersstein inequality. Advances in Neural Information Processing Systems, 32, 2019.
Minsker. On some extensions of Bernstein's 's inequality for self-adjoint operators. Statistics & Probability Letters, 127:111-119, 2017. ISSN 0167-7152. doi: 10.1016/j.sl..217..3..00
Orabona and K.-S. Jun. Tight concentrations and confidence sequences from the regret of universal portfolio. IEEE Transactions on Information Theory, 70(1):436-455, 2024. doi: 10. 10.110900 109/TT. 2023.3330187.
D. Paulin, L.. Mackey, and A. Tropp. Efron-Stein inequalities for random matrices. The Annals of Probability, 44(5):3431 - 3473, 2016. doi: 10.1214/15-AP1154,
A. Ramdas and T. Manole. Randomized and exchangeable improvements of Markov's s, Chebyshev's and Chernoff's inequalities. Statistical Science (to appear), 2024.
S. Shekhar and A. Ramdas. On the near-optimality of betting confidence sets for bounded means. arXiv preprini arXiv:2310.015.. 2023.
I. O. Tolstikhin and Y. Seldin. AAC-Bays-eempirrcal--Bmmne tou, M. Welling, Z. Ghahramani, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
inequality. In C. Burges, L. Bot-
A. Tropp. User-friendly tail bounds for sums random matrices. Foundations of Computational Mathematics, 12:389-434, 2012.
J. A. Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230, 2015.
I. Waudby-Smith and A. Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B: Statistical Methodology, 86(1):1-27, 02 2023. ISSN 1369-7412. doi: 10. 001109//jsss///kad000.

---

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

---

Justification:
We provide full assumptions in our theorem statement and proofs after the statement and sometimes in Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We describe our simulation set-up in Section 5.3. While we leave some room unspecified (e.g. we do not specify the "3 fixed orthonormal projections"), the algorithms are invariant under the alternation of these minor choices.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
13

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Simulation codes are provided as Supplementary Material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ mripss.cc/ubllic/gui.eee CoodeSumeeieeeeee ssi iessonPolll molyicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See submitted codes.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The simulations were only once and are reported as is without repetition, as we believe these results are compelling enough to demonstrate the empirical difference between methods.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
14

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: We do not find necessary to disclose such information as computation is less of concern.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We adhere to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Theory.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
15

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not expect matrix mean estimation methods to be subject to such misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
16

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing human subjects involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing human subjects involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
17

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: We occasionally have the Grammarly Chrome extension on during the writing of this paper; and Google Colab Al-powered inline completions on when implementing simulations. We do not use LLMS otherwise.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, ntn-standard components.
Please refer to our LLM policy htteee///earrpoecccc///feerrrrrs for what should or should not be described.
18

---

A Additional Proofs
A.1 Technical Lemmas
The following lemma converts bounds |a 1--b bl va Vb.
Lemma A.1. Let a, d and D la b/. Then,
D DJ va + (VDA
2vb - P
(40)
Proof. Suppose a > since the bound trivial otherwise. First, by the subadditivity of the square root, va vb+D & Vb VD. Second, D = (Va - vb)( vb) 7 (Va 2b) so
vā < vb+ 2V5' Third, D = (Vā - vb)(va+ vb) > (Va - vb) s vb+ Taking minimum completes the proof.
The following lemma bounds the difference of squares of two matrices. Lemma A.2. Ler A, be two symmetric matrices.
||A
B²| < B||||||
B + |A - -
Proof.
B A B|
|
[B (A B))² BB| |B(A B) (A B)B (A B
B|
+
A
B
The following lemma characterizes the smoothness of th((x) = log(1 - -x) - at O.
Lemma A.3. When 0 & x & 2//5, vE()) x².
Proof. Let g(x) = vhr (x:) x22
The claim follows from g"(x) = x) -2 2 for x
[0, v 2/5), and g(0) = 0, gl /( 2/5) <
The following transfer rule Tropp 2012
Equation 2.2] is commonly used in deriving matrix bounds. Lemma A.4. Suppose I C R and f.g R satisfies fxx & g(x), then, f(X) 3 ( any
X E S/.
is well well-known that if X and Y are scalar random variables such that < X < Y almost surely for some constant and that E|| < oo, it follows that E| < do well, and E.X EY. This type of "implied integrability" appears frequently in scalar concentration bounds. Let us prove its symmetric matrix extension for the sake of self-containedness.
Lemma A.5 (Dominated integrability). Let X and Y be Sd sle,eo) -value random matrices for some e E R such that X < Y almost surely. Further, suppose EY exists. Then, so does E.X. and EX- EY
Proof. Let us prove that each element Xij of the random matrix X is integrable. Note that for any deterministic E Rdd v TXv & VT almost surely. First, taking (0, ...., .0......111. 0, 1,100, 11. 0)T, we have
Yv
c < <x & YYs almost surely,
(41)
concluding that the diagonal element К3Л must be integrable (since Yj² is). Next, taking 0, 0, T, we have
2c < 2X,, Xx+ X3, < 2Y + +Y + Y, almost surely,
(42)
concluding that 2X, X + X33 must be integrable (since 2Y + Yo + Y3ş is). Therefore, the off-diagonal element Xij is integrable since X;+ and Xjj are.
Now that we have established the existence of TXX, is clear that EX < EY since for any v E Rd v (EX)v= E(v Xv) & YYv v (EY)v.
19

---

A.2 Strong Consistency of the Matrix Sample Variance
We show in this section that the matrix sample mean and variance are strongly consistent under martingale dependence, which prepares us for the upcoming proof of Corollary 4.3 First. we provide the following matrix martingale strong law of the large numbers which, we remark, holds for non-square matrices as well.
Lemma A.6 (Matrix martingale SLLN), Let Let = Ei= Z₁ be a matrix martingale and (Un) an increasing positive predictable process on F. For any E [1,2], on the set
lim Un
Σ "f (an]/oommmZn))FFFFF < x0
(43)
the process U converges to O almost surely. Here, norm(-) (-) is any matrix norm.
Proof. Since matrix norms are mutually equivalent, it suffices to prove the case where norm A) is the max norm max;,j |A,yle By the scalar martingale SLLN (Hall and Heyde 2014 Theorem 2.18). we see that all entries of S, converge to 0 almost surely.
L
This immediately implies the following convergence result of the matrix sample mean and variance, where we take norm(-) to be the usual spectral norm ||
Corollary A.7 (Strong consistency of the matrix sample mean). Let {X,} be adapted to F with con- stant conditional mean E[X,,|_--1 M and 6 (0, 1]. " n -= oo almost surely, then the sample mean X,, converges to M almost surely.
X,, -M]] ( Fn
Proof. It follows directly from Lemma A.6
The assumption Σx=n -n [ M| 16 [=,1) oo is satisfied when, for example, all matrices are uniformly bounded or have common (1 + 6)th conditional moment upper bound. Corollary A.8 (Strong consistency of the matrix sample variance). Let X., be adapted to F with constant conditional mean E[X,, [n M and conditional variance E[(Xn [n-] V. Further, assume that
n 1- --1--B[IIX,
BIIX,, ||, [Fn-1) 0o
(44)
1=
almost surely for some 8 E (0, 1]. Then, the sample variance
1 n 71
V,
Xx xx,)²
(45)
converges to V almost surely.
Proof. Define Q = E Fn-1l = M + V. First, X, + M almost surely due to the constant
variance with Corollary A.7 Using the inequality ||A + B|| 1+6 <
|||| < 2 (I 1|
[ (due to triangle and Jensen inequalities), we have
8
8
8
Σ n 1111-E]||
Q|| 1+6 [ 1
1--1522
X, || 2-26
F
+
n
26 Q 1-4
<0.
(46)
So by Corollary A.7
Q 1 x? - Q
(47)
i=1
almost surely. Therefore,
V. Qn -Xx,)² - V
(48)
almost surely as well, due to continuity.
Again, the assumption Σm n - =IJJ, |2+2 {r, < 00 is satisfied when, for example, all matrices are uniformly bounded or have common (2 + 28)th conditional moment upper bound.
20

---

A.3
Proof of Lemma 2.2
Proof. Due the monotonicity of log, the condition 12 impliee
log E(exp C.) C.
(49)
Now recall Lieb's concavity theorem [Lieb] (S) (0, oo)) is concave. Therefore,
1973 : for any H Sa, the map X + tr e + log
X)
n-1
n-1
B(Ln|Fo-1) =B tr exp
Σ Z, -
Σ (C+ - C,, + loge Zn 2m -Cn Fi-11)
(50)
:=1
(Jensen's 's inequality)
n-1
n-1 Σ
< trexp
Σ
Z
C C, + Elg Cr -ou F
(51)
==1
(by and monotonicity of trace)
(99
n-1
n-1 -
<
exe
Σz. 1=1
Z.
-), C₁ = Ln-
(52)
i=1
concluding the proof that } is supermartingal. Finally, observe that
In trexp
Σ (C+
(53)
i=1
i=1
tre
Zi
Amax
Σ +C+)
Cy)
(54)
i=1
i==
Amax exp
Zi Amax
Σ (C, (C,+CC) CP)
1
(55)
exp Amax
Σ Zj Amax
[C,, + C.))
I
(56)
Amuax [ + C₁) ))
exp
Amax
Σ Zi
(57)
concluding the proof.
11
A.4 Proof of Theorem
3.1
Proof. Note that 2 is the sample average of n/2 independent random matrices, each with eigen- values in [0, 1), of common mean 2V and second moment upper bound
| X2) < [[, X2) = V||
(58)
Thus applying the Matrix Bernstten inequality (5) on 2V see that
2 llo((2//)
8 log((2/a))
PP 12V; 2
<
(59)
3n
Therefore, with probability least a,
log(2d/a)
2 log((d/a))lV))
|IV |VII & IV VI
(60)
3n
1
Denote by g the constant
V + 4 which satisfies
v2 g.
The above implies that if
3g
|V| g² log(2d/a)
log log(2d/a)[V]
2 log (2d/a)
92 log (2)da) V
V - III
(61)
21

---

which in turn implies that, via Lemma A.1
g2 log (2//a)
|V|I 1/2
(62)
71
Since the above also holds if [V| <
we see that the inequality above holds with probability at least - regardless of the true value of [V Integrating the inequality above into the matrix Cennett-Bernstein inequality
g log(2d/a),
(
via an a ( 1)/n + a/nn union bound, we arrive at
Arna X M)
log Da
log in In-1jo
|1V 1/2 +
log(2nd/a)
(63)
3rc
V2
71
with probability at least 1 a. This concludes the proof. The asymptotics the strong law of large numbers and the continuity the spectral norm.
18
follows simply from
A.5 Proof of Lemma
Proof. Recall that the (7) = - log(1 - 7) - 7/ An inequality by Fan et al.
2015 quoted by Howard
al.
2021 Appendix A.8] states that, for all 7 < and -1,
exp(15 - -E()))²²)) 1 +
(64)
Since Xn, Xn S 1,x)
apply the transfer rule (Lemma A.4 replacing the scalar above by the matrix X, Xn, and plugging in 7 = 70 E (0,
exp(7n (X,, 8x.) (o(())))))))))).)))) - X,,)) 3 1 11+++00 mm Mn (X. &.).
(65)
Lemma A.5 then guarantees the integrability of the left hand side, and that
E exp(Tin (X,. - 8.)) -bbe(7))((,, - -8,)3) Fn-1) E 7r,,,, -x &x) (n-n))
(66)
=1 (M, 8,,) 3 exp(1n (M, &n)),
(67)
where in the final step concludes the proof.
the transfer rule again with + & exp(x) for all x R. This
A.6 Proof of Corollary
Proof. First, is straightforward that Amax X;
x,-1) > -1 for every i = 1,... n since both X; applicable. Let us prove the two claims about the Recall that
and x take values in 100.1] so Theorem 4.2
deviation bound mebb2 under 9i- = V nd
(do(
5 llog(d/))
V. I
V
h Σ x X
Th = V
(68)
==1
3
Amax
(69)
T:
==1
Let us compute the almost sure limit limn--so Dibbe surely due to Corollaries A.7 and A.8
First, the following limits hold almost
lim X M,
lim
V
lim Up
[V]
(70)
k-+00
k-000
80000
Let us compute the limit
X X
lim
(71)
n
n
U
To do this, we observe that
n
M) 2
V
lim
(72)
n-+00
22

---

almost surely due to Corollary
A.7
Bounding the difference
X
X
2
X 2)
(73)
1/11
IV
i=1
(X; x -x-, IM
+ | -
(74)
T
(Lemma
A.2
(75)
2 2 M
| - M + - M
X - -I
(76)
U,-1
X -1
M|| <
|
M| < 2)
(77)
6 X -
M|
1 Σ
- - -V 0.
(78)
Vi-1
i=1
Therefore, we see that
X(-1)²
(X, - X1-1)3
s, = Amax
+1
(79)
n2
U1-1
[V|
12
U/-1
almost surely.
We can now use the expansion vn(()) = Dk=2 z¹
to obtain,
E
lim sup mmeme
(80)
1=500
log(d/o)= + Amax
Ei thP
2 logid/o)
(X: x²-
n0,-1
lim sup
(81)
n-500
71 n
2 logld//a) 8,-1
log(d/a) Amax
E1=1
2 logid/a) net
(X, xx-1))
lim sup
(82)
+0000
1 Eiml
2logld/o)
n
Pi-1
Amax
Ei 1
(v
2log(d/o) no--
(X, -x--1
lim sup
(83)
2 log(d/a)
km
10
Ei=1
Tk.n
Let us prove that lim Tk.n for all A: > 3. To see that,
En=
&
1
V
2 log (d/aa)
X
X
Li=1
k
1
(V
2 2log(d/a)
no;
Tk 5
(84)
V
2 log(d/a)
E V
2 2log(d/a)
14-1
k
(2log(d/a))
2
k/2
(85)
1/2
71
1=1
23

---

Since the boxed terms converge to non-zero quantities, we see that Ta,n converges to 0 due to the term. Therefore,
lim sup mebb
(86)
2-000
log(d/a) + Amax
Ei=l
log(d//o)
2
(X,
-x1-1)²
n
lim sup
(87)
n 20000
= ni
1
log log(a//)
1z-1
log(d/a)
1 Amax
-X-1)
81-1
= lim sup
(88)
+0000
2
1 +
2
(89)
Similarly, one can show that lim inf v DnDmeee remark that the proof above strengthens that of Waudby Smith and Ramdas 2023 Lemmas 4-8]. 0
2 logíd/a V
concluding the proof. We
B
Additional Concentration Inequalities
B.1 Remarks on the Scalar (T) and Matrix (5)
Inequalities
Non-empirical Bernstein inequalities typically stated in terms of the upper bound of the tail probability P(S, ES, 2 t). These are derived via Bennett-type inequalities via controlling the function
(+)
huw) = (1 + u) log(1 + u) -
(90)
2(1+u/3
We, for statistical purposes however, are interested in deviation bounds under fixed error probability a. The Bennett-to-Bernstein conversion (+) looser than the following inequality.
Lemma B.1. For all x > (x) < /2x 2/3.
A proof of this polynomial upper bound on h can be found from Equation (45) onwards in Audibert et al. [2009) Tropp [0012 Theorem 6. first states matrix Bennett bound in terms of the h function,
then uses (*) to obtain closed-formed matrix Bernstein bound, both controlling the tail probability (Pmmax (S,, ESS)) > t). Let us use Lemma B. to recover fixed-error a bound whose tightness between the matrix Bennett and the matrix Bernstein, which we already recorded in the paper as (5)
Proposition B.2 (Matrix Bennett- Beneetttn inequality (5) Let X, be the sample average of inde- pendent d x d symmetric matrices X X.....: X, with common mean EX;- = M, common eigenvalue upper bound Amax (X:) & B, and E i=1 EX VV. For any 0
B Blo(d//o)
llogld/a)]l
P Amax (Xn - M)
< a.
(91)
3n
Proof. Due Tropp 2012 Equation (i) in Proof of Theorem 6.1],
ndmax (V)
Bt Xmmax (V)
P Panux X M) > < d exp
(92)
B²
Setting the right hand side a, we obtain via Lemma B.I
1. Amax (V) (V) h-
B (1
(log(d/a)B2
Amax (V)
(1
2 log (d/a) ndmaxx (V)
log(d/a)
(93)
n (V)
B
3nduaax (V)
which readily leads the bound 5
B Blog(d/a)
12 log(d/cn Amax
Amna
X M)
+
$ aa
(94)
3n
n
We also remark that the scalar case
is when d = 1.

---

B.2 Sharp Maurer-Pontil Inequality
Maurer and Pontil [2009] Theorem 4] derived scalar empirical Bernstein inequality which we quote as (2), by union bound between scalar Bennett- Bernstein inequality and a tail bound on the sample variance. However, their balanced union bound split a a/2 + a/2 leads to the looser log(2/1) term. This causes the confidence interval to be 10.9675% longer when 0.05 in the large sample limit. We slightly modify their proof below to obtain a sharp EB inequality for scalars.
Proposition B.3. Let XI....,X, be [0, 1l-bounded independent random scalars with common mean I and variance o², We denote by X, n their sample average and o the Bessel-corrected sample variance, Then, for any (0, IP (X.. n. ps pn)) & az, where
(log (n- (log =)
log (n-1)a
n 20 log (n (n-1ja + 21
Pn.
(95)
3n
n(n 1)
Further, with ii.d .I...., X
lim Vnp,. 220² log(1/a), n-+00
almost surely.
(96)
Proof. By Bennett-Bernstein inequality
log (1//)/a)
20 log
X,
(97)
3n
The deviation of a from o² is controlled by self-bounding concentration inequality [Maurer and Pontil 2009 Theorem 7],
2 2og 1/a)
IP o ān >
< a.
(98)
The desired bound thus follows from a(n 1)/n a/n union bound.
Sample Size (n)
Original MP
Sharp MP
Self-normalized
100
2.120
2.256
1.527
1,000
1.441
1.476
1.081
10,000
1.214
1.169
1.017
100,000
1.144
1.059
1.005
1,000,000
1.121
1.021
1.002
Table 2: Lengths of 95% one-sided confidence intervals of three empirical Bernstein inequalities
divided by that of the (oracle)
inequality ([). "Original MP" stands for the result of Maurer and Pontil 22099 Theorem 4]: "Sharp MP" sharpened result Proposition B.3 and
"Self-normalized" the result by Waudby-Smith and Ramdas 2023 Theorem 2, Remark 1J.
As can be seen from the simulation with tniffo..j-disriibuee random variables displayed Table 2 our sharpened EB inequality leads to significant improvement for large samples. Still, the EB inequality based on the self-normalized technique by /Howard al. [202T), |Waudby-Smm and Ramdas 2023 has much smaller gap compared to the oracle Bernstein inequality.
B.3 First Matrix EB Inequality with the Classical Sample Variance
Recall in Section we proved the first matrix EB inequality by applying the matrix Gennett-Bernsteii inequality (5) twice, once on the sample average and once on the paired sample variance V The latter step differs from the scalar result by |aureer and Pontil| (2009) which uses self-bounding technique on the classical Bessel-corrected sample variance. Intuitively however, the classical matrix Bessel-corrected sample variance for X XI,...,
Σ nin 1) Igicjgn
(X,
xx,)
(99)
25

---

should have a better convergence rate to the population variance V than V full U-statistic. This fact is captured by the self- boludiouniig concentration inequality Maurer and Pontil (009 employ in the scalar case. For matrices, however, the best analysis V, we are aware of comes from the Efron-Stein technique due to Paulin et al. [016], which leads to the following variant of Theorem 3.1
Theorem B.4 (First matrix empirical Bernstein inequality, classical sample variance). Let be S ((0,1) -valuud independent random matrices with common mean M and variance V.
Xn XI,...,
We denote by X, their sample average and V,, the Bessel-correcn sample variance. Then, for any
(0,1).
IP (Amax (X, MM) Dmbblc) az,
(100)
where
Dmeelc
nd 2 log (n-1)a n
|/,11//2 +V
log (2nd/a)
1/4) ) 2 (2log(2nd/a))
+
log nd (n-1)a
(101)
2n V..ll
71
Further, if "I...., Xn are i.idd
lim VnDmeble = 2 (2lg(d/a)][VI almost surely. n+000
(102)
Proof. We view the classical sample variance V. E S!0.1| as a bounded matrix function of indepen- dent variables X,,..., X,. Let V be the sample variance by replacing X, with an i.i.d. copy X The Efron-Stent Stein variance proxy of Vn satisfies
1 =
BI n
V
Xa)
(103)
2n
V E s/1//111/ml We now invoke the Efron-Stein
which can be noted from the fact that each
n
tail bound, Corollary 5.1 from Paulin et al. 2016 to see that for any t 0,
n1l2
IIII V t) < P(V v. t)
2d exp
(104)
2
Setting the right hand side to a, we obtain, with probability at least at
2 log (od/())/)
| - II <
(105)
n
which, due Lemma A.1
implies that
log( log(2d/a) (2d/a)
2 (2log(2d/a) 1/4
|/
VV 1/2
(106)
2n V
n
Integrating the inequality above into the matrix Bennett- Beretttt-Brstenn inequality (5) via an a(n 1)/n + a/n union bound concludes the proof. The asymptotics (102) follows simply from the strong consistency of the sample variance and the continuity of the spectral norm.
We extend the previous simulation shown in Table I with this additional matrix EB inequality. As can be seen from Table 3 using the sample variance leads to a slightly larger confidence set despite the asymptotics (T02) suil being sharp. We leave it to future work whether an improved analysis of the classical matrix sample variance better than (105) can lead to Maurer-Pontil-ste matrix EB inequality that beats Theorem 3.1
C Other Scalar EB Inequalities
wealth of scalar empirical Bernstein inequalities exists the learning theory literature, especially under the PAC-Bayes (Alquier) 2024 setup. These are concentration inequalities on the poste- rior expected deviation, valid simultaneously over posterior distributions. We provide brief bibliographical remark in this section.
26

---

Sample Size (n)
Dimes /
Dmmele D
Dimeb / D
100
2.612
3.057
1.397
1,000
1.589
1.874
1.105
10,000
1.214
1.313
1.022
100,000
1.072
1.109
1.007
1,000,000
1.024
1.037
1.002
Table 3: Relative lengths of 95% one-sided confidence sets by three sharp matrix empirical Bernstein
inequalities compared to the (oracle) matrix Bennett-Bernsiee inequality (5). This table includes an additional column for Dmeble on top of Table
PAC-Bayes EB inequality was proved by Tolstikknn and Seldin (2013) using technique comparable
Audibert al. (2009), Maurer and Pontil [2009]: they used union bound to combine an oracle Bernstein-style PAC-Bayes bound and sample variance PAC-Bayes bound. When taking degenerate parameter space (i.e. singleton prior and posterior distributions), one recovers an EB inequality for [0, 1]-bounded i.i.d. random variables, with larger constant on the n 1/2 n/1/2 term compared to (). therefore not sharp by our standard. An alternative to EB inequalities called the "un-expected Bernstein inequality" introduced by Mhammeeii et al. 20T9), which "together with the standard Bernstein inequality imply [sic] a version of the empirical Bernstein inequality with slightly worse factors" [Mhammedi al.) [2019] Appendix GJ. A much tighter, time-uniform PAC-Bayes EB inequality was later proved by Jang et al. [023 Corollary 4J. much similar to the "betting" technique of Wauddy-Smithh and Ramdas [2033 However, no sharp fixed-time EB inequality was proved by [aang et al. [2023]. A similar PAC-Bayes time-uniform result was obtained by Mhhameedi [2021] Theorem 6], also suffering from non-sharpness when instantiated fixed-time.
We finally quote a recent study by [hhekhar and Ramdas [0233 that compares various scalar EB inequalities via their first- and second-order expansions. They show that class of betting-driven
confidence intervals, including those proposed by Waudby-Smith and Ramdas (2033) (other than (3) and the recent universal portfolio-based bound by OOraoona and Jun [024 have minimax optimal rate that outperforms even the sharpness criterion 4 for scalar EB incqualities. However, these confidence sets are in closed form, and remains open problem (even in the scalar case) there are closed-form empirical inequalities that achieve so.
27


Reviews:
[{"review_id": "pLo0g6dkNL", "reviewer": "Reviewer_CtZ1", "summary": "The paper considers the question of proving matrix empirical Bernstein-type concentration inequalities. In its simplest form, the Bernstein inequality is a well-known bound that is used to reason about the empirical mean of independent random variables with common mean and bounded support that satisfy a second moment condition. The second moment condition involves a variance bound $\\sigma^2$ which is usually not known in practical settings.\nThere are a number of generalizations and stronger versions of this result that one can consider. First, it is important to consider ``empirical\" versions of this inequality, where the unknown bound $\\sigma^2$ is replaced by an estimate for the variance. This has the advantage that the deviation of the empirical mean from the true mean can then be quantified precisely, instead of being expressed as a function of the unknown variance bound. Another generalization involves going beyond independent random variables, and considering various kinds of dependencies. Finally, it is worth considering generalizations from scalars to vectors and matrices.\nThe present work gives empirical Bernstein-type concentration inequalities for matrices, both for independent random matrices and for random matrices that exhibit a martingale dependence. Both inequalities exhibit sharp constants.", "questions": "Can the authors provide a more detailed discussion of the challenges involved in proving the results? Also, can they give more concrete examples of problems where using these concentration bounds would yield significant benefits?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I think this is an interesting work, but I have some concerns regarding its overall merit. For that reason, I will try to discuss both positive and negative aspects of the work below.\n\nStrengths:\n1) The main results are interesting in their own right. Indeed, having empirical versions of standard concentration inequalities generalized to the matrix setting and with sharp constants constitutes an interesting contribution to the literature.\n2) The writing is generally accessible.\n\nWeaknesses:\n1) It is mentioned that it is generally harder to establish concentration results for random matrices, compared to how hard it is to achieve this for random variables or vectors. However, I felt there was not an adequate discussion of the technical challenges that the authors encountered when attempting to establish the results in this work. Instead, it felt like the results mostly follow some approaches which have appeared in prior work (e.g., Audibert et al. [2009], ], Maurer and Pontil [2009], Tropp [2012], etc).\n2) No application of the results is given. The paper makes the case about the importance of the result based on the fact that empirical versions of concentration inequalities are generally useful in practice, and that constants are sharp. However, I feel the authors could have made a stronger case about the importance of the results, by a giving a concrete application.\nOverall, I do not consider this to be a bad paper by any means, but I think it might be a bit marginal. I am voting borderline accept for the time being.\n\nJ.-Y. Audibert, R. Munos, and C. Szepesvari. Exploration–exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876–1902, 2009.\n\nA. Maurer and M. Pontil. Empirical Bernstein bounds and sample variance penalization. In 22nd Annual Conference on Learning Theory, 2009.\n\nJ. A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12:389–434, 2012.", "was_revised": true, "final_justification": "Based on the authors' response, I have greater appreciation for the significance and originality of the work than before. However, that does not change my overall rating, which is still borderline accept.", "rebuttal": "## The challenges involved in proving the results\n \nWe agree with the reviewer that the *first* EB inequality echos much of the prior effort made by Audibert, Maurer and Pontil, Tropp etc. Still, we argue that the correct variance bound, Eqn.(61), is not straightforward to obtain, as many naive approaches would end up leading to worse bounds (one of such approaches is recorded in Appendix B.3).\n\nOur *second* EB inequality is very non-trivial. Though the scalar version is well-established, it takes much insight to see the scalar self-normalizing technique is applicable to matrices (Lemma 4.1) in a way that is compatible with Lemma 2.2. For example, Howard et al. did not realize such compatibility --- their work contains numerous matrix bounds, even a weaker version of our Lemma 4.1, but not our second matrix EB inequality.\n\n\n## Concrete examples\n\nA recurring example of application in the matrix concentration inequality literature is *estimating the covariance matrix* $\\Sigma = \\mathbb E x_1 x_1^t$ for mean-zero bounded vectors $x_1, \\dots, x_n$. See Chapters 1.6.2 to 1.6.4 of J.A. Tropp's monograph _An Introduction to Matrix Concentration Inequalities_ for a classical solution using the (oracle) matrix Bernstein inequality; and Corollary 5 in Howard et al. (2021, cited) for a time-uniform confidence sequence in a similar spirit.\n\n\nIn both examples, however, the concentration inequality involves the unknown $\\| \\Sigma \\|$ term itself on the right hand side (i.e. radius) that comes from bounding the variance $\\operatorname{Var}( x_1 x_1^t)$ via a basic boundedness argument. Further boundedness argument on $\\| \\Sigma \\|$ is needed if one wants a *closed-form confidence sets for $\\Sigma$*, and such an argument essentially reduces the \"Bernstein\" bound to a Hoeffding bound, and can be arbitrarily loose.\n\nOur EB inequality completely avoids this issue. The radius of the confidence set is a empirical quantity adaptive to $\\operatorname{Var}( x_1 x_1^t)$.\n\n\nWe have added this example in our paper."}, {"review_id": "vUiWEhPWeN", "reviewer": "Reviewer_FjiK", "summary": "The paper generalizes scalar empirical Bernstein inequalities to the matrix case. Known scalar empirical Bernstein inequalities give a bound on the deviation of the sample mean from the true mean in terms of the empirical variance for i.i.d. samples, or a bound on the deviation of a particular weighted average from the conditional mean in terms of some empirical quantity in the general case. For matrices, a Bernstein type inequality bounds the largest eigenvalue of the centralized average of n i.i.d symmetric matrices in terms of some matrix V that upper bounds the matrices variance w.r.t. to the Loewner partial order. Empirical variants are notoriously harder to attain. The authors formulate a couple of sharp matrix Bernstein empirical inequalities, where sharp means that its deviation terms approache the non-empirical Bernstein inequality deviation term a.s. including constants.", "questions": "In eq. (58), where does the factor 2 in the parentheses originate from? This is an average of dxd matrices, so shouldn't be d/alpha instead of 2d/alpha?", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: the paper is clear and concise, the discussion on the problem, known results and contributions of the paper are thorough.\nWeaknesses: I am not convinced that the results are significant enough, and find the originality of the paper to be lacking. For example, I would like to see more convincing arguments why empirical Bernstein inequalities for matrices are important. In the scalar problem, the empirical inequality allows one to obtain an empirical confidence interval for the true mean given the sample average, when the true variance is unknown. Can something similar be said about the matrix case? As far as originality, it seems to me that the proofs are derivative of previous works, e.g., Theorem 3.1. is obtained by applying the matrix Bennett-Bernstein inequality twice and using the union bound in a non-trivial way.", "was_revised": true, "final_justification": "The authors convincing rebuttals and discussion with the reviewers improved my opinion of the paper.", "rebuttal": "## Why empirical Bernstein inequalities for matrices are important.\n\n\nIn answer to the reviewer's question if the matrix EB inequalities provide, like their scalar siblings\n\n> An empirical confidence interval for the true mean given the sample average, when the true variance is unknown\n\nour Theorem 3.1 does exactly that, where the \"confidence interval\" is now a confidence sphere in the spectral distance.\n\nFurther, the importance of matrix EB inequalities lies in their application. A recurring example of application in the matrix concentration inequality literature is *estimating the covariance matrix* $\\Sigma = \\mathbb E x_1 x_1^t$ for mean-zero bounded vectors $x_1, \\dots, x_n$. See Chapters 1.6.2 to 1.6.4 of J.A. Tropp's monograph _An Introduction to Matrix Concentration Inequalities_ for a classical solution using the (oracle) matrix Bernstein inequality; and Corollary 5 in Howard et al. (2021, cited) for a time-uniform confidence sequence in a similar spirit.\n\n\nIn both examples, however, the concentration inequality involves the unknown $\\| \\Sigma \\|$ term itself on the right hand side (i.e. radius) that comes from bounding the variance $\\operatorname{Var}( x_1 x_1^t)$ via a basic boundedness argument. Further boundedness argument on $\\| \\Sigma \\|$ is needed if one wants a *closed-form confidence sets for $\\Sigma$*, and such an argument essentially reduces the \"Bernstein\" bound to a Hoeffding bound, and can be arbitrarily loose.\n\nOur EB inequality completely avoids this issue. The radius of the confidence set is a empirical quantity adaptive to $\\operatorname{Var}( x_1 x_1^t)$.\n\n\nWe have added this example in our paper.\n\n## The factor 2 in (58)\n\nWe need a two-sided bound (as opposed to the one-sided inequality (5)) here. So we split the $\\alpha$ two-way, apply (5) twice, and take a union bound."}, {"review_id": "ZCaGoY9SZX", "reviewer": "Reviewer_bmYk", "summary": "This paper proposes two sharp, closed-form empirical Bernstein inequalities for symmetric random matrices with bounded eigenvalues. The first inequality (Theorem 3.1) applies to the sample mean of independent matrices and uses a paired sample variance estimator. The second (Theorem 4.2 and Corollary 4.3) extends to martingale-dependent sequences.", "questions": "1. Could you suggest any potential applications of the matrix EB inequalities? e.g. for bandit problems or PAC-Bayesian bounds. Including such applications might make this paper more suitable for machine learning conferences.\n\n2. Can you prove that the second EB inequality is sharper than the first one for iid matrices, or only empirically so?\n\n3. Is there a techinical difficulty in extending the first EB inequality to odd numbers? What is the difference between paired sample variance and sample variance in order to give a bound?\n\n4. On the techinical side, what is the main difficulty in extending EB inequality to matrices?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is technically sound, and proves novel matrix Empirical Bernstein inequalities that are asymptotically tight. However, the authors only suggest that the matrix EB inequalities can be used to obtain tighter confidence interval, and do not relate it to machine learning problems, so I believe that it is out of the scope of NeuIPS2025 and should be submitted to statistics journals or conferences instead.", "was_revised": true, "final_justification": "I find the technical analysis convincing and have revised my score accordingly. However, the paper's impact is still limited by the absence of examples in machine learning to demonstrate the importance of the proposed inequalities.", "rebuttal": "## Application\n\nA recurring example of application in the matrix concentration inequality literature is *estimating the covariance matrix* $\\Sigma = \\mathbb E x_1 x_1^t$ for mean-zero bounded vectors $x_1, \\dots, x_n$. See Chapters 1.6.2 to 1.6.4 of J.A. Tropp's monograph _An Introduction to Matrix Concentration Inequalities_ for a classical solution using the (oracle) matrix Bernstein inequality; and Corollary 5 in Howard et al. (2021, cited) for a time-uniform confidence sequence in a similar spirit.\n\n\nIn both examples, however, the concentration inequality involves the unknown $\\| \\Sigma \\|$ term itself on the right hand side (i.e. radius) that comes from bounding the variance $\\operatorname{Var}( x_1 x_1^t)$ via a basic boundedness argument. Further boundedness argument on $\\| \\Sigma \\|$ is needed if one wants a *closed-form confidence sets for $\\Sigma$*, and such an argument essentially reduces the \"Bernstein\" bound to a Hoeffding bound, and can be arbitrarily loose.\n\nOur EB inequality completely avoids this issue. The radius of the confidence set is a empirical quantity adaptive to $\\operatorname{Var}( x_1 x_1^t)$.\n\n\nWe have added this example in our paper.\n\n## Out of scope for NeurIPS\n\nBesides the application of covariance estimation (which is itself a frequently visited topic in NeurIPS, see e.g. \"Robust gaussian covariance estimation in nearly-matrix multiplication time\" by Li and Ye, \"Differentially private covariance estimation\" by Amin et al.) mentioned above, the following is an incomplete list of application-driven papers published in NeurIPS that have employed the oracle matrix Bernstein inequality:\n\n- \"Provable Non-linear Inductive Matrix Completion\" by Zhong et al.\n- \"Support Recovery in Sparse PCA with Incomplete Data\" by Lee et al.\n- \"Distributed estimation of the inverse hessian by determinantal averaging\" by Derezinski and Mahoney.\n\nWhile these papers usually focus on using the matrix Bernstein as an analysis tool, our paper brings uncertainty quantification tools to these applications.\n\n\n\n## Can you prove that the second EB inequality is sharper than the first one for iid matrices, or only empirically so?\n\n\nOn the one hand, both inequalities are \"sharp\" by our definition in Eqn.(8). It is indeed an empirical observation that the second EB inequality is tighter than the first. There is some understanding of why this is the case in the scalar setting by a very involved analysis of the second-order term (the 1/n term); see the cited arXiv preprint by Shekhar and Ramdas. \n\n\n## Paired sample variance vs. vanilla sample variance\n\nWhile it is still possible to obtain *sharp* matrix EB bounds using the vanilla sample variance, existing analysis always suffers from an unsatisfactory lower-ordered term. Such examples include our Appendix B.3, as well as the cited concurrent work by Kroshnin and Suvorikova (a constant 15 exists in their bound).\n\nWe acknowledge that the lack of sharp analysis of the vanilla sample variance does not indicate that it is a worse estimator itself. As we mention in the paper, we \"leave it to future work whether an improved analysis of the classical matrix sample variance better than (104) can lead to a Maurer-Pontil-style matrix EB inequality that beats Theorem 3.1.\"\n\n## Main difficulty in extending EB inequality to matrices\n\n\nFor the first EB inequality, the correct variance bound, Eqn.(61), is not straightforward to obtain, as many less involved approaches would end up leading to worse bounds (one of such approaches is recorded in Appendix B.3).\n\nFor the second EB inequality, though the scalar version is well-established, it takes much insight to see the scalar self-normalizing technique is applicable to matrices (Lemma 4.1) in a way that is compatible with Lemma 2.2. For example, Howard et al. did not realize such compatibility --- their work contains numerous matrix bounds, even a weaker version of our Lemma 4.1, but not our second matrix EB inequality."}, {"review_id": "j9akGM1Tfm", "reviewer": "Reviewer_ZodG", "summary": "The paper proves two empirical Bernstein inequalities for sums of symmetric random matrices, extending the empirical Bernstein bounds from the scalar to the matrix setting. Suppose $T_\\alpha$ satisfies $\\Pr(\\lambda_{\\max}(\\sum_i X_i) \\geq T_\\alpha) \\leq \\alpha$, where $X_i$'s are mean-zero symmetric matrices. The standard (non-empirical) matrix Bernstein inequality gives\n$$\nT_\\alpha = \\sqrt{\\frac{2\\log(d/\\alpha) \\|V\\|}{n}} + O\\left(\\frac{\\log(1/\\alpha)}{n}\\right),\n$$\nwhere $V = \\frac{1}{n} \\sum_i \\mathbb{E} X_i^2$, and each $-I \\preceq X_i \\preceq I$. In the empirical versions, the unknown variance $V$ is replaced with a data-dependent estimator.\n\nSpecifically, the paper shows show that\n$$\nT_\\alpha = \\sqrt{\\frac{2 \\log(nd/((n-1)\\alpha)) \\Vert V_n^\\ast \\Vert }{n}} + O\\left( \\frac{\\log(nd/\\alpha)}{n} \\right),\n$$\nwhere $V_n^* = \\frac{1}{n} \\sum_{i\\ \\text{odd}} (X_i - X_{i+1})^2$ is the paired sample variance. This result is shown to be sharp asymptotically. The sharpness is obtained through an unbalanced union bound, improving on the scalar case of Maurer and Pontil. \n\nThe paper also proves a second empirical Bernstein inequality under martingale dependence, generalizing the classical matrix Freedman inequality. The technique is based upon the self-normalized supermartingales due to Waudby-Smith and Ramdas (2023) but generalized to the matrix case.", "questions": "Can you comment more on Kroshnin and Suvorikova’s result? Their result contains an \\hat{z} term but that is just 1 in many cases. If you only want a bound that is tight in order (without the \\hat{z} term in Kroshnin and Suvorikova’s result) instead of having sharp constants, is there a simpler proof?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper generalizes the classical matrix Bernstein/Freedman inequalities to the empirical case and obtains sharp bounds. \n\nWeaknesses: Previous work of Kroshnin and Suvorikova seems to have a good bound with much simpler proofs. I do not find this paper's improvement very important in applications (unless one cares a lot about the constants).", "was_revised": false, "final_justification": "", "rebuttal": "## More comment on Kroshnin and Suvorikova\n\nTheir EB inequality is not \"sharp\" by our definition in Eq.(8). Just as the scalar Maurer-Pontil bound can be sharped by an imbalance $\\alpha$ split (Appendix B.2), the KS inequality can be similarly sharpened.\n\nHowever, even sharpened, the bound (as the reviewer aptly pointed out) suffers from a large constant of 15 in its lower-order term.\n\nTo us, the main insight from KS is its analysis (Lemma 4.9) on the vanilla matrix sample variance (unlike our paired one). It exhibits another facet of the trade-off together with our appendicized analysis of the vanilla sample variance (Eqn.(105)): they avoid the $n^{-3/4}$ term at the price of a large constant in the $n^{-1}$ term.\n\nStill, as we mentioned, we still hope future work to address \"whether an improved analysis of the classical matrix sample variance better than (104) can lead to a Maurer-Pontil-style matrix EB inequality that beats Theorem 3.1.\"\n\nWe finally note that the KS paper was concurrent work to ours, using complementary techniques (and with different goals)."}]

Author rebuttal:

Meta-review: This paper presents two empirical Bernstein-type inequalities for symmetric random matrices. The bounds are non-asymptotic, do not require prior knowledge of the variance, and are sharp, including the constants.

Four reviews were collected. All reviewers highlighted the importance and significance of the results, particularly the technical contributions. The AC concurs with this assessment and regards the paper as a significant breakthrough on an old yet important problem in statistics. The sharpness of the derived bounds, both for the sample mean of independent i.i.d. matrices and for their martingale-dependent variants, is especially noteworthy.

Some reviewers expressed concerns about the applicability of the results, but the authors provided satisfactory responses to address these points.
Decision: Accept (poster)