A Vector Bernstein Inequality for Self-Normalized Martingales

Ingvar Ziemann · 2024

Read A Vector Bernstein Inequality for Self-Normalized Martingales by Ingvar Ziemann (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-20949.txt.

Description

Abstract We prove a Bernstein inequality for vector-valued self-normalized martingales. We first give an alternative perspective of the corresponding sub-Gaussian bound due to Abbasi-Yadkori et al. (2011) via a PAC-Bayesian argument with Gaussian priors. By instantiating this argument to priors drawn uniformly over well-chosen ellipsoids, we obtain a Bernstein bound.

Catalog record

CREATORIngvar Ziemann
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-20949

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Vector Bernstein Inequality for Self-Normalized Martingales Ingvar Ziemann Abstract We prove a Bernstein inequality for vector-valued self-normalized martingales. We first give an alternative perspective of the corresponding sub-Gaussian bound due to Abbasi-Yadkori et al. (2011) via a PAC-Bayesian argument with Gaussian priors. By instantiating this argument to priors drawn uniformly over well-chosen ellipsoids, we obtain a Bernstein bound. 1 Tail Bounds for Self-Normalized Martingales Deviation inequalities for self-normalized martingales play a key role in obtaining guarantees for linear regression in interactive and sequential decision-making tasks, such as learning an autoregression or regret minimization in linear bandits. The most prevalent version of such an inequality currently in use is due to Abbasi-Yadkori et al. (2011) and rests on the method of pseudo-maximization popularized by Peña et al. (2009) , dating back to Robbins and Siegmund (1970) . Comparing their result to the central limit theorem, their bound is nearly optimal but depends on the sub-Gaussian variance proxy instead of the actual variance. In this note, we overcome this issue by casting the pseudo-maximization technique through the lens of the PAC-Bayesian inequality. The present approach simplifies classical pseudo-maximization by relegating the complexity of evaluating exponential integrals against the smoothing distribution to the computation of a generic Kullback-Liebler divergence term. This allows us to generalize the argument of Abbasi-Yadkori et al. (2011) but without access to globally defined moment generating function bounds. Let us now proceed by describing the setting of our result and that of Abbasi-Yadkori et al. (2011) . Fix a filtration \mathcal{F}_{0:\infty} and two square-integrable processes: X_{1:\infty} , taking values in \mathbb{R}^{d} , and W_{1:\infty} , taking values in \mathbb{R} . For each T\in\mathbb{N} , let X_{1:T} be adapted to \mathcal{F}_{0:T-1} and W_{1:T} to \mathcal{F}_{1:T} with \mathbf{E}[W_{k}|\mathcal{F}_{k-1}]=0 for every k\in\mathbb{N} . For t\in\mathbb{N} , we define: \vskip-8.0ptS_{t}\triangleq\sum_{k=1}^{t}W_{k}X_{k}\quad\textnormal{and}\quad V_{t}\triangleq\sum_{k=1}^{t}X_{k}X_{k}^{\mathsf{T}} (1.1) and are interested in bounds on the random walk S_{T} in the random Mahalanobis norm \|S_{T}\|_{(V_{T}+\Gamma)^{-1}}^{2}=S_{T}^{\mathsf{T}}(V_{T}+\Gamma)^{-1}S_{T} for some fixed positive semidefinite matrix \Gamma\succeq 0 . This is called a self-normalized martingale . Under the assumption that W_{k} is \mathcal{F}_{k-1} -conditionally \sigma_{\mathrm{subG}}^{2} -sub-Gaussian for each k\in\mathbb{N} , 1 1 1 \mathbf{E}\left[\exp\left(\lambda W_{k}\right)\big|\mathcal{F}_{k-1}\right]\leq\exp\left(\frac{\lambda^{2}\sigma_{\mathrm{subG}}^{2}}{2}\right),\>\forall k\in\mathbb{N}. Abbasi-Yadkori et al. (2011) show that for every stopping time \tau ( \in\mathcal{F}_{0:\infty} ) and with probability 1-\delta : \|S_{\tau}\|_{(V_{\tau}+\Gamma)^{-1}}^{2}\leq\sigma_{\mathrm{subG}}^{2}\times\left[\log\left(\frac{\det(V_{\tau}+\Gamma)}{\det(\Gamma)}\right)+2\log(1/\delta)\right]. (1.2) Their approach rests on an elegant application of the pseudo-maximization technique developed by Peña et al. (2009) , dating back to Robbins and Siegmund (1970) . While elegant, the result of Abbasi-Yadkori et al. (2011) has one shortcoming as compared to classical asymptotics: the linear dependence on the conditional variance proxy \sigma_{\mathrm{subG}}^{2} as opposed to the conditional variance, \sigma_{\mathrm{var}}^{2}\triangleq\sup\{\mathbf{E}[W_{k}^{2}|\mathcal{F}_{k-1}]|\textnormal{ a.s., }k\in{T}\} . The traditional fix to this in the literature on concentration inequalities is to invoke a Bernstein-type bound on the moment generating function (MGF) of the W_{k} instead of a Hoeffding type of bound. Unfortunately, directly combining a Bernstein MGF bound with the pseudo-maximization technique does not lead to analytically tractable upper bounds as it requires the evaluation of an exponential integral over a bounded domain (an ellipsoid). Moreover, previous attempts at establishing Bernstein bounds (via methods orthogonal to pseudo-maximization) for vector-valued self-normalized martingales suffer from extraneous logarithmic dependencies and have significantly looser constants ( Zhao et al., 2023 , see for instance) . In this note, we provide an alternative perspective on the proof of ( 1.2 ), where, instead of computing the exponential integral directly, we invoke the variational characterization of Kullback-Liebler divergence via the PAC-Bayesian lemma to relegate this difficulty to the calculation of said divergence. Beyond Gaussian priors, this turns out to be significantly simpler than the evaluation of an exponential integral. It allows us to modularize the proof strategy of Abbasi-Yadkori et al. (2011) and replace their Gaussian prior with uniform ellipsoidal priors that are suitable in combination with exponential inequalities that only hold for a restricted domain (contrast this with Hoeffding MGF bounds being valid for all \lambda ). The rest of this note is organized as follows. We state our main result immediately below and then proceed to discuss its consequences. Its proof is given in Section 2.2 . Preliminaries relating to our application of the PAC-Bayesian lemma are given in Section 2 where we also provide a proof of ( 1.2 ) as a warm-up. Auxiliary lemmata are proven in Section 3 . 1.1 The Result To apply a Bernstein MGF bound, we will require some additional boundedness assumptions. Namely, we posit that: |W_{k}|\leq B_{W}\quad\textnormal{and}\quad X_{k}X_{k}^{\mathsf{T}}\preceq B_{X}^{2},\qquad\forall k\in\mathbb{N} (1.3) for a positive scalar B_{W} and a positive definite matrix B_{X} . Theorem 1 . Fix \delta,\varepsilon,\nu\in(0,1) , a stopping time \tau with respect to \mathcal{F}_{0:\infty} , a positive semidefinite matrix \Gamma\succeq 0 , a positive definite matrix V\succ 0 and assume that ( 1.3 ) holds. Define \alpha\triangleq\left(\frac{\sqrt{e}(1+\nu)\|S_{\tau}\|_{(V_{\tau}+\Gamma)^{-1}V(V_{\tau}+\Gamma)^{-1}}}{\nu\sqrt{d+2}}-1\right)\vee 0. Then as long as V_{\tau}+\Gamma\succeq e(1+\nu)^{2}V\succeq(1+\nu)^{2}\varepsilon^{-1}(d+2)B_{W}^{2}B_{X}^{2} we that with probability at least 1-\delta : \|S_{\tau}\|_{(V_{\tau}+\Gamma)^{-1}}^{2}\leq\left(\frac{(1+\alpha)^{2}}{1+2\alpha}\times\frac{1}{1-\varepsilon}\right)\times\sigma_{\mathrm{var}}^{2}\times\left[\log\left(\frac{\det(V_{\tau}+\Gamma)}{\det(V)}\right)+2\log(1/\delta)\right]. (1.4) Remarks on Theorem 1 : 1. When \Gamma=0 , requiring \alpha=0 in Theorem 1 can be thought of as a burn-in requirement, restricting the Bernstein inequality to cases in which the corresponding least squares error is sufficiently small. Typically, \alpha=0 once the sample size is large enough as \|S_{\tau}\|_{V_{\tau}^{-2}}^{2} is the norm-squared error of the least squares estimator in the model Y_{k}=\langle\theta_{\star},X_{k}\rangle+W_{k} up to time \tau . When S_{\tau} is not too large, the variance proxy \sigma_{\mathrm{subG}}^{2} in ( 1.2 ) can thus be replaced by the variance term \sigma_{\mathrm{var}}^{2} with just a little overhead in \varepsilon . 2. For \Gamma\succeq\varepsilon^{-1}e^{-1}(d+2)B_{W}^{2}B_{X}^{2} (corresponding instead to ridge regression) one may choose V=\Gamma and use ( 1.2 ) to control \alpha at the cost of an inflated failure probability ( \delta to 2\delta ). 3. Together, \varepsilon and \nu control the sharpness of the multiplicative constants of the bound. In the large sample regime, these can often both be allowed to tend to 0 . 4. The bound can be put in a more convenient form by making use of either of the two numerical inequalities (1+2\alpha)^{-1}(1+\alpha)^{2}\leq(1+\alpha^{2})\wedge(1+\frac{1}{2}\alpha) . 5. Using Theorem 1 instead of the result in Abbasi-Yadkori et al. (2011) sharpens existing bounds for least squares estimators with martingale difference noise, allowing one to achieve optimal dependence in \sigma_{\mathrm{var}}^{2} . See e.g. the proof structure laid out in Ziemann et al. (2023, Section 1.2) . 6. These improvements also potentially extend to refining linear bandit analyses, previously motivating the results in Abbasi-Yadkori et al. (2011) and Zhao et al. (2023) . 2 PAC-Bayesian Bounds Let \rho and \pi be two probability measures supported on a set \Lambda\subset\mathbb{R}^{d} . Recall that \mathrm{d}_{\mathrm{KL}}(\rho,\pi)\triangleq\int_{\Lambda}\log\left(\frac{d\rho}{d\pi}\right)d\rho\in[0,+\infty] is the Kullback-Leibler divergence between \rho and \pi . Our analysis in the sequel rests on the well-known PAC-Bayesian lemma, stated below. Lemma 1 (PAC-Bayesian deviation bound) . Let \Lambda be a subset of \mathbb{R}^{d} , and Z(\lambda) , \lambda\in\Lambda , be a family of real-valued random variables. Assume that \mathbf{E}[\exp Z(\lambda)]\leq 1 for every \lambda\in\Lambda . Let \pi be a probability distribution on \Lambda . Then for all u\in[0,\infty): \mathbf{P}\left(\forall\rho:\,\int_{\Lambda}Z(\lambda)\mathrm{d}\rho(\lambda)\leq\mathrm{d}_{\mathrm{KL}}(\rho,\pi)+u\right)\geq 1-e^{-u}, (2.1) where \rho spans all probability measures on \Lambda . We will instantiate the PAC-Bayesian lemma with Z(\lambda) as the quadratic form (and with t=\tau) Z(\lambda)=\langle\lambda,S_{t}\rangle-\frac{1}{2}\|\lambda\|_{V_{t}}^{2}=\frac{1}{2}\|S_{t}\|_{V_{t}^{-1}}^{2}-\frac{1}{2}\|\lambda-V_{t}^{-1}S_{t}\|_{V_{t}}^{2}. (2.2) To account for the fact that the Mahalanobis norm appearing in ( 1.2 ) includes

Read the complete text