Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Norm
Authors: Huiming Zhang
Haoyu Wei
Guang Cheng
Venue: Submitted to ICLR 2023 (2023)
Keywords: non-asymptotic inference
uncertainty quantification
concentration inequality
multi-armed bandit

Abstract: In non-asymptotic statistical inferences, variance-type parameters of sub-Gaussian distributions play a crucial role. However, direct estimation of these parameters based on the empirical moment generating function (MGF) is infeasible. To this end, we recommend using a sub-Gaussian intrinsic moment norm [Buldygin and Kozachenko (2000), Theorem 1.3] through maximizing a series of normalized moments. Importantly, the recommended norm can not only recover the exponential moment bounds for the corresponding MGFs, but also lead to tighter Hoeffiding's sub-Gaussian concentration inequalities. In practice, intrinsic moment norm can be robustly and consistently estimated via a simple plug-in approach. Our theoretical results are applied to non-asymptotic analysis, including the multi-armed bandit.

Under review as a conference paper at ICLR 2023
TIGHT NON-ASYMPTOTIC INFERENCE VIA SUB-GAUSSIAN IN- TRINSIC MOMENT NORM
Anonymous authors Paper under double-blind review
ABSTRACT
In non-asymptotic statistical inferences, variance-type parameters of sub-Gaussian distributions play a crucial role. However, direct estimation of these parameters based on the empirical moment gen- erating function (MGF) infeasible. To this end, we recommend using a sub-Gaussian intrinsic moment norm [Buldygin and Kozachenko (2000), Theorem 1.3] through maximizing series of normalized moments. Importantly, the recommended norm can not only recover the exponential moment bounds for the corresponding MGFs, but also lead to tighter Hoeffiding's 's sub-Gause Gaussian concentration inequalities. In practice, we propose an intuitive way of checking sub-Gaussian data with a finite sample size by the sub-Gaussian plot. Intrinsic moment norm be robustly esti- mated via simple plug-in approach. Our theoretical results are applied to non-asymptotic analysis, including the multi-armed bandit.
INTRODUCTION
With the advancement of machine learning techniques, computer scientists have become more interested in establish- ing rigorous error bounds for desired learning procedures, especially those with finite sample validity (Wainwright
Z & Chen 2021; Yang et al. 2020). In specific settings, statisticians, econometricians, engineers and physi-
cist have developed -smmttytt inferences to quantify uncertainty in data; see Romano & Wolf (2000); Chassang
(2009) Arlot et al. (2010); Yang et al. (2020); Horowitz & Lee (2020) Armstrong & Kolesár (2021)
(2021 ) Zheng & Cheng (2021): : Lucas et al. (2008); Owhadi et al. (2033): Wang (2020). Therefore, the concentration based statistical in-
ference has received a considerable amount of attention, especially for bounded data (Romano & Wolf 2000 Auer
et al. 2002, Hao et al. 2019: Wang et al.) 2021 Shiu (022) and Gaussian data (Arlot et al. 20100 Duy & Takeuchi
2022 Bettache et al.) [022 Feng et al. (021). For example, Hoeffding's inequality be applied to construct non-
asymptotic confidence intervals based on bounded data")
However, in reality, it may be hard know the support of data its underlying distribution. In this case, misusing Hoeffding's 's inequality (Hoeffding) 1963) for unbounded data will result in a notably loose confidence interval (CI); see Appendix A. Hence, is common practice assume that data follow sub-Gaussial distribution (Kahane) 1960). By the Chernoff inequality?] we have P(X 2 t) I inf s>0{ confidence interval relies on how we upper bound the moment generating function (MGF) E exp(sX} for all s > O. This can be further translated into the following optimal variance proxy of sub-Gaussian distribution.
A t 2 O. Hence, tightness of a
Definition 1. A E.. X is sub-Gaussian (sub-G) with a variance proxy o² [denoted as X ~ subG(a")) if its MGF satisfies E exx(ttX) < exp(o2t /2) for all t E R. The lab-Gaussian parameter Jope (X) defined by the optimal variance proxy (Chow, 1966):
dape (X) = inf {02 >0 0: Eexp(tX) I exp(o221/2), Vte = 2 rept 2log Exxp(tx))
(1)
Note that o² (X) > Var X; see (4) in Appendix
Var X, it is called strict sub-Gaussianity (Arbel et al. 2020). Based on Theorems 1.5 in Buld ggin & Kozachenko (2000), we have
A.2 When - (X)
7
P (X t) < exp
P
Xi 2
< 2exp
(2)
2 op (X)
2 "Σ dop (X,)
'Recently, Phan et al. 2022) obtained a sharper result than Hoeffding's 's inequality for bounded data. For simplicity, consider centered random variable (I...) with zero throughout the paper for all sub- Gaussian

---

Under review as a conference paper at ICLR 2023
for independent sub-Grvvs X and [X;]_-1 The above inequality 2 provides the tightest upper bound over the form P(X > 1) S exp(-CIp) (or P() Em= X
> 1) S exp(-CI²)) for some positive constant C via Chernoff inequality.
Given {x,) اiيا subG(o opt (X)). a straightforward application of gives an non-asymptotic 100 a CI
EX 0 (,, + ope (X) / 1ogg22((///)
(3)
A naive plug-in estimate of 2 opt (X) = 2 supp log [og - exx((tX)) AAreel et 2020 is
opt (X) == SER logg| - EE exp(LX,)]]
(4)
However, two weaknesses of 44) substantially hinder its application: (i) the optimization result is unstable due to the possible non-convexity of the objective function; (ii) exponentially large is required to ensure the variance term Var(n Σ exp(txX,) not to explode when t is large. In Section 3, we present some simulation evidence.
On the other hand, we are aware of other forms of variance-type parameter. For instance, van der Vaart & Well- ner (1996) introduced the Orlicz norm as ||X May = inf(c > 0 : E [exp([X]%/c> I 2}. frequently used in empirical process theory. Additionally, /Vershynin (2010) suggested a norm based on the scale of moments as
| = maxc>2 k (-//((E in Page 6 of Buldygin & Kozachenko (2000). However, shown in Table 1 and Appendix T both types of norm fail to deliver sharp probability bounds even for striet sub-G distributions, such as the standard Gaussian distribution and symmetric beta distribution.
Table 1: Comparison of sub-Gaussian norms || || for centralized and symmetric X.
norm
shorp for P[] 2 f)
sharp MGF bound
hulflength (1 6).C1
easy to estimate
(X)
Yos [2exp]- 2 //02, (X))
Yes (oxp (X) + 31
//2 (2log(2/6)eanl) (X)
No
X Ulug
Yes (2 exp(
/ 1x11x11 12 1|H
v2
No [exp|(2||| X 1wog 1
v [2log(2/8]] (lwg /v2
No
X llag
No 12exp]
+/(2=|IX1),
No |exp/
Yes
Xlla (Def
Yes (2oxp
(-5 /1/1111111
Yes [exp 11 5
(2log(2/6]]
Yes
1.1 CONTRIBUTIONS
In light of the above discussions, advocate the use of the intrinsic moment norm in the Definition the construc- tion of tight non-asymptotic Cls. There are two specific reasons: (i) it approximately recovers tight inequalities (2) (ii) it can be estimated friendly (with closed form) and robustly.
The following definition 2 is from Page 6 and Theorem 1.3 in Buldygin & Kozachenko (2000).
Definition 2 (Intrinsic moment norm). || == max
k (2k)
E. 2xx22111(2)) 12(k)) = max;21 (28 121- EX26111(22))
From the sub-G characterization (see Theorem 2.6 in Wainwright (0199). ||X]| < 3o iff oope (X) Do for any zero- mean E.. X. Hence, the finite intrinsic moment norm of a.v. A ensures sub-Gaussianite (satisfying Definition
Our contributions in this paper can be summarized as follows.
By || we achieve a sharper Hoeffding-type inequality under asymetric distribution; see Theorem b
2. Compared to the normal approximation based Berry-Esseen (B-E) bounds, our results are more applicable to data of extremely small sample size. We illustrate Bernoulli observations with the comparison of two types of CIs based on the B-E-corrected CLT and Hoeffding's inequality in Figure see Appendix [A details.
3. A novel method called sub-Gaussian plot is proposed for checking whether the unbounded data are sub- Gaussian. We introduce plug-in and robust plug-in estimators for || lla. and establish finite sample theories.
4. Finally, we employ the intrinsic moment norm estimation in the non-asymptotic inference for bandit prob- lem: Bootstrapped -Cg-algorithm for multi-armed bandits. This algorithm is shown to achieve feasible error bounds and competitive cumulative regret unbounded sub-Gaussian data.
'e point out that conservative and inconsistent estimator 2 infrea Begnn-'>a exp(tX.))/t² was proposed in statistical physics literature (Wang 2020).
2

---

Under review as a conference paper at ICLR 2023
433a +0.02
de13 -0.075
2412 0.1
Confowonteng
30
Figure 1: CIs via Hoeffding's inequality (red line) and B-E-corrected CLT (blue line). describes deficiency of B-E-corrected CLT under small sample, and it suggests that a simple Hoeffding's inequality can even perform better.
2 SUB-GAUSSIAN PLOT AND TESTING
Before estimating [X ll. the first step is to verify X is indeed sub-G given its i.id. copies {X1 Corollary 7.2 (b) in Zhang Chen (2021) shows for I.S. X; sp (X)) (without independence assumption)
P(maxisis) X, Jppt (X) 2(log j + +))
exp(-1),
which implies maxigis; X; Op Op(vlogj). Moreover, we will show the above rate is indeed sharp for class of unbound sub-G r.v.s characterized by the lower intrinsic moment norm below.
Definition 3 (Lower intrinsic moment norm). The lower intrinsic moment norm for a sub-G X is defined as
| == mimmmi 1111 -Ex 1/(22)
1)!!
By the method Theorem of Zhang& Zhou (2020), we obtain the following the tight rate result with a lower bound.
Theorem 1. (a). If || 0 for i.i.d. symmetric sub-G r.v. {X+) X, then with probability least 1
|
X A 221log + log
log log (X) - log log
max ISiS
8
2
where C(X) is constant defined in Lemmal below: (b) if X is bounded variable, then ||X||a =
The upper bound follows from the proof of (5) similarly. The proof of lower bound relies on the sharp reverse Chernoff inequality from Paley-Zygnan Zygmund inequality (see|aaley & Zygmund| (1932)).
Lemma 1 (A reverse Chernoff inequality). Suppose
| foror symmetric sub-G X. For t > 0, then
P(X 2 (x exp( - 4 1 1|
22 8 -11
1XI
1I 21| & 4|X - IXI
where C(X)= =
(0,
Theorem of Zhang & Zhou (020) does not optimize the constant in Paley- -eygmuZ inequality. In contrast, our Lemma [ has an optimal constant; see Appendix C for details.
propose a novel sub- mub-Gaussian plor check whether i.i.d data {X;} )2 follow a sub-G distribution. Suppose that for each j. (X independently sampled from the empirical distribution F (x) 1 En 1(X, x) of {X.} Specifically, plot the order statis- tics (maxisis) X 1 on the plane coordinate axis, where x axis represents vlog + and y axis the value of
Sub-Gaussian plot under unbounded assumption By Theorem
n
"Sub-G G plot can only be applied to data with enough samples. When is very small, there is not enough information to suggest unbounded trends. We roughly treat the data bounded r.v. for very small and there is no need use sub-C G plot in this case.
3

---

Under review as a conference paper at ICLR 2023
maxisigs X;. We check whether those points have linear tendency at the boundary: the more they are close to the tendency beeline, the more we can trust the data are uub--Gasssin.
The Figure 2 shows sub-suuaeee Sub--aussian plot of (0,, 1) and Exp(1). It can be seen that uub-Gaussian plot of N(0, 1) shows linear tendency the boundary, while Exp(1) shows quadratic tendency the boundary. For the quadratic tendency, note that if {X,, } have heavier tails such as sub-exponentiality. then maxigis) X; Op (log.) instead of the order ( (looooo))) see Corollary 7.3 in Zhang & Chen 2021
sub-Goussian plat standard Gaussian
sub-Gaussian plat of standard exponential
12.00
V0
Nog UT
Figure 2: sub-Gaussian plot of standard Gaussian and standard exponential distribution for n = 1000. Left: The two dot lines indicate the points drop in triangle region with high probability. Right: The points in the case of exponential distribution approximately live curve triangle region with quadratic trends.
3 FINITE SAMPLE PROPERTIES OF INTRINSIC MOMENT NORM
In this section, we characterize two important properties of the intrinsic moment norm that are used in constructing non-asymptotic confidence intervals.
3.1 BASIC PROPERTIES
Lemma below establishes that the intrinsic moment norm is estimable.
Lemma 2. For sub-G X, we have arg maxme2N
E (m- 1j!!
< where 2N = {2, ..... is the even number set.
Lemma Paaama?ensinn ensure that for any sub-Gaussian variable X, its intrinsic moment
be computed
|X == maxmE2N
EX 1y
1/m
= max
(2k 1y
Ex22
1/(2k)
with some finite xx < oc.
This is an important property that other norms may not have. The X X achieves its optimal point at Io oo; see Example 3 in Appendix
1r = max k /12 for Gaussian
A.2.1 As for o pp (X) sup
log[E exp()
unclear that its value can be achieved at a finite Note that kx 1, one has || Var(X).
Next, we present an example in calculating the values of kx. Denote Exp(1) as the truncated standard exponen- tial distribution on [0, .)] with the density as f(x) de [ZE|0,MM1
Example 1. X U[-a,a) a), kx 1 for any E R; X Exp(1) [0.277|| E Exp(1 (Exp(1)]oo2.75)) kx 2; X Exp(1)] h.3 E Exp(1)) (0.3y. kx 3. Indeed, for any fixed ko E N, construct truncated exponential ZR. X = Exp(1) [0 such that kx ko by properly adjusting the truncation level M.
3.2 CONCENTRATION FOR SUMMATION
In what follows, we will show another property of || ll that it recovers nearly tight MGF bounds in Definition More powerfully, it enables to derive the sub-G Hoeffding's inequality 2
4

---

Under review as a conference paper at ICLR 2023
Theorem 2. Suppose that (XiR== are independent kv.s with maXie[]] |Xile < cc. We have
(a). If X, symmetric about zero, then [tx, S exp |Xx /2] for any t R, and
POE X,| _ 2xxp |I [x1.) $20
(b). If X, is not symmetric, then Eexp (1X;)
(| / for any E R, and
P P X 2 s) - expp (12/1)()))))))))))1)))))))) [
$20 0.
Theorem a) is an existing result in Theorem 2.6 of Wainwright 2019). For Theorem b(b,, we obtain v 11/112 1.19, while Lemma 1.5 in Buldygin & Kozachenko (0000) obtained Eexp(tX,) I exp (v3.
for R with v3.1 ss 1.32. Essentially, V17/12 > appears for asymmetric variables, since I|- +la is defined by comparing Gaussian variable G that symmetric. A technical reason for this improvement is that lle does not need Stirling's 's approximation for attaining a sharper MGF bound when expanding the exponential function by Taylor's formula. To show the tightness of Theorem (()), in Fig Appendix C
we gives some comparisons with opt (X), /17/ / lla /2 X ll 1|/ /v2 and vVar X in terms of confidence length in Table 1 when X is Bernoulli or beta distribution.
4 ESTIMATION OF THE INTRINSIC MOMENT NORM
A first thought estimate || l|a is by the plug-in approach. Although kx is proven be finite in Lemma 2 its (possibly large) exact value is still unknown in practice. Instead, we use a non-decreasing index sequence [kn) to replace kx in the estimation. Hence, we suggest a plug-in feasible estimator
1/(2k)
1
|
max Igksan
x?
(6)
(2k:
1)!! 1=1
Deriving the non-asymptotic property of the [a is not easy task: the maximum point k(Ka) arg maxis 1ę2K- n Σm= x22 will change with the sample size even Kn is fixed.
To resolve this, we first examine the oracle estimator defined as | = x2 E._ X2 1/2kx
Here,
based on Orlicz norm | := inf(! > 0 Eexp(()19/19 s 2} of sub- Weibull r.v. Y with 0 > 0 Hao et al.
2019 Zhang& & Wei 2022). we present the non-asymptotic concentration of ||Xll around it ture value | |..
Proposition 1. Suppose {X lid. X and X satisfies || oc, then any > 0.
|Xll 2kx - ||
s Il C( {V= + 22 A(Kx)) "1
}) 2 1-22
where the constant r Rs 1.78, and the constant functions C(-) and A(-) are defined in Appendix
C
||x11 in The exponential-moment condition | < oc is too strong for the error bound of || 2kx Proposition 1 although it has exponential decay probability 1 2exp(-1).
Except for the direct plug-in estimator, here we resort to the median-of-means (MOM, Page244 in Nemirovskij & Yudin (1983)) as the robust plug-in estimator of intrinsic moment norm. Let m and be a positive integer such that n mb and let BI...., Bù be a partition of [n] into blocks of equal cardinality m. For any s E [b]. let P.. X = m EieB, X; for independent data {X,);² - The MOM version intrinsic moment norm estimator defined as
{ [[((2A- 11)0 -Ip& x (
X 11.0 = max med
ISk5R, <E(b]
||x 1 is not robust. MOM estimators with b > 1 have two merits: (a) it only needs finite moment conditions, but the exponential concentration bounds are still
As stated in Proposition the naive plug-in estimator ||xilc
5

---

Under review as a conference paper at ICLR 2023
achieved; (b) it permits some outliers in the data. Non- Non-asymptotic inferences require to bound for ||X exactly by feasible estimator | up to a sharp constants. Next, we establish a high- teieh-pobbbbiityy upper bound for the estimated norm, if the data has O I outlier assumptions as follows.
(M.1) Suppose that the data {= contains n no inliers {Xiher drawn iidd according to target distribution, and there are no distributional assumptions on na outliers {Xi)eeo
(M.2) b bo + bs. where bo is the number of blocks containing least one outliers and by is the number of sane blocks containing no outliers. Let & == no/n be the fraction of the outliers and The < 2- Assume "b
here exists fraction function ny()) for sane block such that by 2 ry(e)b for a function nn(c) E (0, 1).
To serve for error bounds in the presence of outliers, (M.2) considers the specific fraction function of the polluted inputs; see Laforgue et al. 2222)) Define g kmm (ox) and (k.m(os) as the sequences for any m E N and S k S Kn:
Jh. (Tk) == 1- Ex /(2 1)!!
1/(2K)
max ISKSKn
-22mm/n(e)
+ EX /2k 1)!1] 1/(2k)
(8)
and 9s.m (0%) = (2mm/
1/2
12/(2kk) 1. We obtain a robust and non-asymptotic CI for ||
Theorem 3 (Finite sample guaranteed coverage). Suppose Var S of for a sequence { we have
P(lxxles
In.m [k.m(ox)]~1|XX[1e) } > -n-in 2bm(()((1 mier)
S
max ISkSa
and P[]X 2 [1 + maxisksn, Im.
> 1- Kin - 20m(()( mnle) 12 for Kn 2 xx under (M.2..
Theorem ensures the concentration of the estimator || when Kn 2 kx under enough sample. If n((e)) = with 0, then the data are i.i.d., which have no outlier, and outlier assumptions in M. 1.1-M.2 can be dropped in Theorem When the data is i.i.d. Gaussian vector, Proposition 4.1 in Auer et al. (2002) also gave high-probabilityy estimated upper bound for fn-norm of the vector of Gaussian standard deviations, our result for intrinsic moment norm.
In practice, the block number b can be taken by the adaptation method based on the Lepski method (Depersin & Lecué 2022). To guarantee high probability events in Theorem 3 it required that the index sequence K, should not be very large for fixed b. The larger Kn needs larger b in blocks BI...., B,. In the simulation, we will see that increasing index sequence Kn with slow rate will lead a good performance.
Finally, we compare our two estimators (6) and 7 well as the estimator 4 in Figure 3 We consider the standard
Gaussian and Rademacher variable distributed X, in the two case we have [ = o p (X) = Var(X) = 1. The following figure shows the performance of three estimators under sample n 10 to 1000 with Kn, just chosen [log n... For the MOM method, we use five blocks in this simple setting. For a more complex case, one can use Lepski's method to choose (see Page & Grünewälder (2021)). but some considerable computation cost may be introduced. From F3 we know that the performance of the MOM estimator is best, while the naive estimator { is worst. For the high-quality data of extremely small sample size. we can apply the leave-one-out Hodges-Lehmann method (Rousseeuw & Verboven 2002) for further numerical improvement; see Appendix B for details.
5 APPLICATION IN MULTI-ARMED BANDIT PROBLEM
In the multi-armed bandit problem (MAB), player chooses between K different slot machines (an K-armet ban- dit), each with a different unknown random reward r.v.s {Y S R, while each realization of a fixed arm & is independent and shares the same distribution. Further, we assume the rewards are sub-Gaussian, i.e.
|| mella < oo,
k E [K].
(9)
Our goal is to find the best arm with the largest expected reward, say Yr.. by pulling arms In each round t e [T'] the player pulls an arm (an action) A, [K]. Conditioning on {A, = k). we define the observed reward
(Yr,cheery Pk- The goal of the exploration in MAB is to minimize the cumulative regret after T steps:
Lid.
6

---

Under review as a conference paper at ICLR 2023
Standard Goussian
Standard Gaussian with 0.5% Cauchy Noise
25
15
Esiraaed Vauu
Extmaaedd Vake
Radermishhe her
Rademacher with 0.5% Cauchy Nolee
MCM
cdiiated romm
cstmaadd nom
MMW MW Man
0.5
Figure DE represents the naive plug-in estimator (6. MOM represents the MOM estimator 7 and OP is the estimator plug-in naive estimator (4) for the optimal variance proxy.
Regr (Y, = (ee ,AA,, ie. the performance of any exploration strategy {Achem The exploration
performance is better, if we have smaller Regr (Y, A). Without loss of generality, we assume t* = 1. We seek to evaluate the expected bounds from the decomposition (see Lemma 4.5 Lattimore Szepesvári (2020)).
Regr Reg, (Y, -K Ef (A+ - =
(10)
where F. is taken on the randomness of the player's actions {At) and A for arm [1] The upper bound of Reg, is called problem-indeppendnt if the regret bound depends on the distribution of the data and does not rely on the gap Ak.
141 μog is the sub-optimality gap
For each iteration t, (t) == card < < A, k} be the number of pull for arm k until time t during the bandit process. Then if define Y (e()) Tall)
1 ErstA, Yk,r as the running average the rewards of arm k time f. Suppose we obtain 100(1 8)% CI VTt( -xx)))xx) (t), Y TT(1) ct())) for l4 from tight concentration inequality. Therefore, we confidently reckon that the reward of arm hoping to maximize the reward with high probability for finite This upper confidence bound (UCB, Auer et al. (2002)) algorithms. And many works based on this methods appears recently, for example, НHа et al. (2099) use bootstrap method with the second order correction to give algorithm with the explicit regret bounds for sub- Gaussian rewards. However, many existent algorithms contain unknown norms for the random rewards, they are actually infeasible. And Theorem 4 is example with explicit regret bound. For instance, the algorithm Hao et al.) (2019) needs to use the unknown Orlicz-norm of Y 14k in the algorithm. Thus, it is actually infeasible in practice.
T2(0 + (t),,, and play the arm A, = k.
Fortunately, estimator solve this problem. Suppose that Y₁- M4 is symmetric around zero, by one-side version of Theorem
2 2 the (9) implies that for all & and all t, P(Y Tu(1) > μ4 + | - mello Th()) log 1) < 5. Let sub-
sample size my and block size by be positive integer such that (t) myby for MOM estimators YYx Mx m Bl in
7

---

Under review as a conference paper at ICLR 2023
Section 3. Theorem 3 (a) guarantee that true norms can be replaced by MOM-estimated norms such that P(Y Tx(1) -
IYe-pa l
V (2))) log !) 1 - 8 ky, exp(-bx/8) if nn(e) 1 with 0.
1-0(1)
If the UCB algorithm is correctly applied, for finite (t))), with high probability, we will pull the best arm.
In practice, we nearly not know any knowledge about the data. As a flexible way of uncertainty qualification, the multiplier bootstrap (Arlot et al.) 2010) enables mimicking the non-asymptotic properties of the target statistic by reweighing its summands of the centralized empirical mean. The multiplier bootstrapped quantile for the i..d. observation Y, (Y:)== is the (1 a---uantile of the distribution of Ei=w, WY; YY,), which is defined as
qo (Y, Y a, w) == inf E R P EE- wi(Y, F,,) > Sa),
where {w;) } are bootstrap random weights independent of Y,: We denote the statisties (Y something satisfying PY, ((Y,, EYil 2 (Y)) S
Algorithm 1: Bootstrapped UCB
Input: Pa Pa(Yrio (t)) is given by (II) for { = 1...., K do
Pull each arm once to initialize the algorithm. end
for t K +...,, do Set a confidence level a E (0, 1). Calculate the boostrapped quantile Ja/2 (Y,(()))))))))) YIu(E), w) with the Rademacher bootstrapped weights w independent with any Y.
Pull the arm
A argmax UCBE(() argmax (T) + 9a/2((TT Y Tucts w) KE(K]
2log(4/0)
Po Y (T)))).
Txtl]
kE[K]
Receive reward YA.- end
Motivated by Hao al. (2019), design Algorithm I based on estimators of the UCB. It guarantees relatively small regret by bootstrapped threshold Yo /2 - (t)) w) adding a concentration based second-order correction @a (e)))) that is specified in Theorem In the following regret bounds, we assume the mean reward from the k-th μ4 is known. In practice, it can be replaced by robust estimator, and obtain the results of MOM estimator.
Theorem 4. Consider a K -armed sub-G bandit under (9) and suppose that Yv. us is symmetric around zero. For any round T, according moment conditions in Theorem choosing Go (o(())))))
lolg(4//a) \Y MAk Bullby.G 1/2 (1) -
To (Yn())
(11)
T
re-scaled version of MOM estimator l| px B with block number by satisfying the moment assumptions
CUCBII and CUUB22] in Appendix C Fix a confidence level 4/T2, if the player pull an arm A, [K] according to Algorithm 1, then we have the croblem-dependde regret of Algorithm I is bounded by
K A + (4T +
K
Reg, S 16(2 + V2)2 max | 1x.12 log Σ k=2
25 25-22-11520 16v2
+ +8)
A
KE KE[K]
where DE is the sub-optimality gap. Moreover, let ui maxk E|K] Mhn mink Mag be the range over the rewards, the
regret
Regr <8(2 + 22)
IYg mellav TK + (4T 27 16v2 + K
KE
From Theorem we know that the regret of our method achieve minimax rate log T for problem-dependen problem and / KT for wwwplpem-iiddeedddeee case (see Tao al. (2022)). so Algorithm can be seen optimal algorithm.
8

---

Under review as a conference paper at ICLR 2023
Compared with the traditional vanilla UCB, we do improve the constant. When Y2 ~ ((p, 1), the constant factor in regret bound in Auer et al. 20022 is 256, which is larger than 16(2 + 22 in our theorem.
When the UCB has unknown sub-G parameters, Theorem 4 first studies feasible UCB algorithm with sub-G param- eter plugging estimation. Many previous UCB algorithms based on non- asymmtoticc inference in the literature assume that the sub-G parameter a preset constant, see algorithm Hao et al. (2019) for instance.
Next, we give an simulation for Theorem in two sub-G cases to verify the performance of estimated norms. Similar to Hao al. (2019): Wang et al. (2020), we design the three methods as follows:
1. Use our method (Y (T())) with Estimated Norm in Theorem
Use Asymptotic Naive varphi @ (((a)) satisfying P( T2(1) - ukl S (((Ia(0)) + a by CLT, i.e.
(()) 0 h/2)///2//// Te(() with oR T.E E (Ya, YIa())² as the estimated
standard deviation;
Regard all the unbounded rewards as bounded r.v. and Hoeffding's inequality (wrongly use Hoesfdiigg s inequality) construct yp, i.e. &0( ((T))) mmxx (Yx min(Yn 1ox(2/a)
27,(1
And for our detailed MAB simulation, we consider as follows, in each case, the number of arms is assigned as K 5,
and (Ji.... ......... 145) (0.1, 0.01, 0.02, 0.01, 0.01)
EG1. Y ((Kk.1a)
EG2. YR 0.9N (1%, 196) 0.1N (19-)1 where 44 == M4.
Gaussian
Gaussian Mixture
tyee
Typ
Anymonvii lake Varple
Asymatttie Narve Varchi
estimuteed form
Datimsted Norm
Wrorgly Use ttaetiiing
1.0
0.5
0.0
400
Round
Round
Figure 4: The regret of MAB with sub-G rewards under three methods. æ-axis represents the round and y-axis is the cumulative regret.
As we can see, EGI and EG2 are both Lab-Gaussian rewards. In the simulation, μl is assigned sightly small for bounded max; Ab. which is standard-setting in the MAB problem (see the condition of Corollary in Wang et al.) (2020) for instance). The simulation results are shown in Figure 4 which illustrates that our method outperforms the other two methods under the unbounded sub-Gaussian rewards and small sample T E [1, 150). In the Gaussian case, Algorithm 1 can also give better results compared with the CLT-based UCB when the round is relatively small. For the Gaussian mixture case, the algorithm based on the intrinsic moment norm has smaller regret than the other methods under T E [1, 800].
REFERENCES
Julyan Arbel, Olivier Marchal, and Hien D Nguyen. On striet sub-gaussianity, optimal proxy variance and symmetry for bounded random variables. ESAIM: Probability and Statistics, 24:39-55, 2020.
9

---

Under review as a conference paper at ICLR 2023
Sylvain Arlot, Gilles Blanchard, Etienne Roquain, et al. Some nonasymptotic results on resampling in high dimension, i: confidence regions. The Annals of Statistics, 38(1):51-82, 2010.
Timothy B. Armstrong and Michal Kolesár. Finite-sample optimal estimation and inference on average treatment effects under unconfoundedness. Econometrica, 89(3):141-11177, 2021.
Peter Auer, Nicolo Cesa-Bianche and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
Nayel Bettache, Cristina Butucea, and Marianne Sorba. Fast nonasymptotic testing and support recovery for large sparse toeplitz covariance matrices. Journal of Multivariate Analysis, pp. 104883, 2021.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
Valerif Vladimirovich Buldygin and IU V Kozachenko. Metric characterization of random variables and random processes, volume 188. American Mathematical Soc., 2000.
Sylvain Chassang. Non-asymptotic tests of model performance. Economic Theory, 41(3):495-514, 2009.
YS Chow. Some convergence theorems for independent random variables. The Annals of Mathematical Statistics, 37 (6):1482-149)) 1966.
Jules Depersin and Guillaume Lecué. Robust sub-gause gaussian estimation of a mean vector in nearly linear time. The Annals of Statistics, 50(1):511-5366 2022.
Vo Nguyen Le Duy and Ichiro Takeuchi. Exact statistical inference for the wasserstein distance by selective inference. Annals of the Institute Statistical Mathematics, 2022.
Yihao Feng, Ziyang Tang, na zhang, and qiang liu. Non-asymptotic confidence intervals of off-policy evaluation: Primal and dual bounds. In International Conference on Learning Representations, 2021.
Evarist Giné and Richard Nickl. Mathematical foundations of infinit-ddimensiona statistical models. Cambridge university press, 2016.
Botao Hao, Yasin Abbasi Yadkori, Zheng Wen, and Guang Cheng. Bootstrapping upper confidence bound. In Ad-
vances in Neural Information Processing Systems, volume 32, pp. 12123-12133, 2019.
Tim Hesterberg. Bootstrap. Wiley Interdisciplinary Reviews: Computational Statistics, 3(6) 2011.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal the American Statistical Association, 58(301):13-30, 1963.
Joel Horowitz and Sokbae Lee. Inference in class of optimization problems: Confidence regions and finite sample bounds on errors coverage probabilities. Cemmap, Centre for Microdata Methuods and Practice, The Institute for Fiscal., 2020.
Lean-Pierre Kahane. Propriétés locales des fonctions à séries de fourier aléatoires. Studia Mathematica, 19(1):1-25. 1960.
Michael Kearns and Lawrence Saul. Large deviation methods for approximate probabilistic inference. In Proceedings of the Fourleenth conference on Uncertainty in artificial intelligence, pp. 311-319, 1998.
Aryeh Kontorovich. Concentration in unbounded metric spaces and algorithmic stability. In International Conference on Machine Learning, pp. 28-36. PMLR, 2014.
Pierre Laforgue, Guillaume Staerman, and Stephan Clémençon. Generalization bounds in the presence of outliers: a median-of-means study. International Conference on Machine Learning, pp. 5937-5947. PMLR, 2021.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Leonard J Lucas, H Owhadi, and M Ortiz. Rigorous verification, validation, uncertainty quantification and certification through concentration-of-maassee inequalities. Computer Methods Applied Mechanics and Engineering, 197(51- (2):459146099 2008.
10

---

Under review as a conference paper at ICLR 2023
Olivier Marchal, Julyan Arbel, et al. On the sub-gaussianity of the beta and dirichlet distributions. Electronic Com- munications in Probability, 22, 2017.
Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency opti- mization. 1983.
Houman Owhadi, Clint Scovel, Timothy John Sullivan, Mike McKerns, and Michael Ortiz. Optimal uncertainty quantification. Siam Review, 55(2):271-345, 2013.
Stephen Page and Steffen Grünnewälder. The goldenshluger-lepski method for constrained least-squares estimators over rkhss. Bernoulli, 27(4):2241-2266, 2021.
REAC Paley and Antoni Zygmund. note on analytic functions in the unit circle. Mathematical Proceedings of the Cambridge Philosophical Society, volume 28, pp. 266-272 Cambridge University Press, 1932.
My Phan, Philip Thomas, and Erik Learned-Miller. Towards practical mean bounds for small samples. In ICML 2021: 38th International Conference on Machine Learning, pp. 8567-8576, 2021.
Phillippe Rigollet and Jan-Christian Hütter. High dimensional statistics. Lecture notes for course 185997, 2019.
Joseph P Romano and Michael Wolf. Finite sample nonparametric inference and large sample efficiency. Annals of Statistics, pp. 756-778, 2000.
Peter J Rousseeuw and Sabine Verboven. Robust estimation very small samples. Computational Statistics Data Analysis, 40(4))741-758, 2002.
Irina Gennad' evna Shevtsova. On the absolute constants in the berry-essees esseen inequality and its structural and nonuni- form improvements. Informatiaa i Ee Primeneniya, 7(1):224-125, 2013.
Daniel Shiu. Efficient computation of tight approximations to chernoff bounds. Computational Statistics, pp. 1-15, 2022.
Youming Tao, Yulian Wu, Peng Zhao, and Di Wang. Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pp. 1546-1574. PMLR, 2022.
A. W. van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics. Springer, 1996.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 101ivv:011.3022 2010.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
Chi-Hua Wang, Yang Yu, Botao Hao, and Guang Cheng. Residual bootstrap exploration for bandit algorithms. arXiv preprint wxiv:2002.08446, 2020.
Jie Wang, Rui Gao, and Yao Xie. Two-sample test using projected wasserstein distance. In Proc. ISIT, volume 21, 2021.
Yan Wang. Sub-gaussian and subexponential fluctuation-respons inequalities. Physical Review E, 102(5):052105, 2020.
Andreas Winkelbauer. Moments and absolute moments of the normal distribution. arXiv preprint arXiv: 420.4430, 2012.
Yun Yang, Zuofeng Shang, and Guang Cheng. Non-asymptotic analysis for nonparametric testing. In Conference Learning Theory, pp. 3709-3755. PMLR, 2020.
Anru R Zhang and Yuchen Zhou On the non-asymptotic and sharp lower tail bounds of random variables. Stat, 9(1) e314, 2020.
Huiming Zhang and Song Xi Chen. Concentration inequalities for statistical inference. Communications Mathe- matical Research, 37(1):1-85, 2021.
11

---

Under review as a conference paper at ICLR 2023
Huiming Zhang and Haoyu Wei. Sharper sub-weibull concentrations. Mathematics, 10(13):222,, 2022.
Yao Zheng and Guang Cheng. Finite-time analysis of vector autoregressive models under linear restrictions. Biometrika, 108(2)4699489, 2021.
Anatolii Zolotukhin, Sergei Nagaev, and Vladimir Chehotarev. On a bound of the absolute constant in the berry-esseen inequality for iid bernoulli random variables. Modern Stochastics: Theory and Applications, 5(3):885 4100, 2018.
12


Reviews:
[{"review_id": "y-g6WyKqfc", "reviewer": "Reviewer_HA7B", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper shows that finite-sample bounds on sub-Gaussian random variables can be derived in terms of a particular norm -- the intrinsic moment norm.  They present (consistent and robust) estimators for the intrinsic moment norm and use these as plug-in estimates to obtain (approximate) confidence intervals.  They use this approach in an upper-confidence bound approach to multi-armed bandits, where it seems to work better than some baseline methods.", "summary_of_the_review": "The paper has some interesting ideas, but the main results are not really non-asymptotic guarantees.  The paper would benefit from an explanation of how to use these results in practice to get finite-sample guarantees.  Also, the presentation could be made more clear.", "strength_and_weaknesses": "Strengths:\n* The intrinsic moment norm is very interesting, and its connection to finite-sample bounds for sub-Gaussians is an underexplored area.\n* Some of the results in the paper come with rigorous theoretical guarantees.\n\nWeaknesses:\n* Overall, I found the paper difficult to follow.  A lot of technical results are presented with relatively few explanations.  I understand the space limitations of this venue, but even still the material in the main text jumps around considerably.  For example, the first figure referenced in the main text is Figure 3.  \n* Finite-sample bounds are, in my opinion, mainly useful if they can give concrete guarantees.  For example, if we _know_ a variable is bounded, we may use Hoeffding's inequality to generate confidence intervals that are guaranteed to have at least our desired coverage.  In contrast, we generally do not know the intrinsic moment norm of data, and hence need to estimate it from the data.  Then, the main result of the paper in terms of using the intrinsic moment norm for tail bounds relies on Theorem 3.  Theorem 3 guarantees consistency (an asymptotic property) but for finite samples is only quantitative in terms of the $g$ sequences, which seem difficult to know a priori.   This ends up causing the tail bounds to have an asymptotic flavor -- they are correct up to a (unknowable) factor that shrinks as the sample size gets large.  Unless I am missing something, this seems to undercut the main point of using finite-sample bounds.\n* Along a similar line as the previous comment, I was confused by the motivation for having a robust estimator of the intrinsic moment norm.  I suppose the assumption is that outliers are somehow corrupted data that we want to ignore.  If instead, outliers are actually a part of the data generating mechanism then the examples  in Figure 3 (mixtures with a Cauchy) are no longer sub-Gaussian.  It would be good to better motivate why, if we do not know the intrinsic moment norm and need to estimate it from the data, we would also be confident enough to make assumptions M.1 and M.2, and hence decide that any outliers in our data are true outliers and not just heavy tails.\n* I found the sub-Gaussian plots a nice and intuitive way of visualizing sub-Gaussian distributions, but I am not sure how useful they are in practice.  As above, finite-sample guarantees are nice for small samples, but to judge whether a plot looks linear or not would require many, many observations from the distribution.  Even in Figure 2, I'm not entirely sure that I would be able to say whether the left or right figures look linear if the red dotted lines were not present.  I also think that the axis labels (Value and sqrt_log_j) in Figure 2 could be improved.\n* There were numerous typos throughout the paper and appendix (too many to list here, but e.g., \"the Hoeffding's inequality\" in the main text, and \"varinace\" in Figure 6).  These, overall, did not interfere with my understanding of the material, but the paper would certainly benefit from some copy editing.\n* It would be good to include empirical results about the coverage properties of confidence intervals produced using estimated intrinsic moment norms.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ti3cgDQVXFc", "reviewer": "Reviewer_W7v5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper provides a method to estimate a sub-Gaussian distribution's variance-type parameters. ", "summary_of_the_review": "I think the missing paper is missing a part on how to determine whether the distribution is sub-Gaussian do begin with, which seems rather important.", "strength_and_weaknesses": "* Strength\n\nThis paper addresses the problem of estimating a sub-Gaussian distribution's variance-type parameters, which is less studied.\n\n* Weakness\n\nThis paper attempts to estimate a distribution's sub-Gaussian variance-type parameters. But how do we know if the distribution is not heavy tailed to begin with? What happens if the method is used (incorrectly) on a heavy tailed distribution (e.g. completely Cauchy)?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JIOdDd6_WN", "reviewer": "Reviewer_2Ndd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of constructing tight non-asymptotic confidence intervals for sub-gaussian random variables. To achieve this, the authors propose to use a sub-gaussian intrinsic moment norm, which can be robustly estimated using a simple plug-in approach. The paper then applies the analysis for multi-armed bandits, derives  matching regret upper bounds. ", "summary_of_the_review": "My decision is mostly based on how significant the contribution is for the machine learning community. I recommend rejecting this paper as I am not convinced that proposed method has significant contribution to multi-armed bandit setting, which is the application this paper considers. Please correct me if I missed anything important. I am happy to adjust my score based on how well the authors answer the questions in the rebuttal. \n\n", "strength_and_weaknesses": "The paper is well-written. I try to check the derivations as much as I can given the limited time, and I don't find any major problem. \n\nHowever, I am not an expert on statistics and therefore I cannot judge the paper in terms of novelty and how significant the contribution is. I sincerely apology for this. Also, if the authors want to submit this paper to a machine learning conference, I think ICLR might not be the best place, maybe it’s more suitable for COLT, ALT and AISTATS? \n\nMy major concern is how significant the contribution is to the machine learning community. I have the following questions. \n\n1. In the experiment the reward gaps are fixed. Maybe it’s better to show the performance under different reward gaps? It’s especially interesting to see how the algorithm performs with different minimum reward gap.\n\n2. How does the proposed algorithm compare to common baselines such as UCB and Thompson Sampling? \n\n3. Could the proposed method be applied to linear bandits? Or can it be applied to problems where UCB and TS have limitations? \n\n4. From the theoretical perspective, how does Theorem 4 improve over the regret bound of UCB? I believe it’s at most a constant improvement as UCB is both minimax and instance-dependent optimal. It’s still great to see the regret bound of the proposed method if it achieves better practical results than UCB and Thompson Sampling, but the author needs to show that. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject