اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدConcentration Inequalities for Bounded Random Vectors
303
0
0.0
(
0
)
تأليف
Xinjia Chen
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We derive simple concentration inequalities for bounded random vectors, which generalize Hoeffdings inequalities for bounded scalar random variables. As applications, we apply the general results to multinomial and Dirichlet distributions to obtain multivariate concentration inequalities.
قيم البحث
اقرأ أيضاً
Consider $n$ complex random matrices $X_1,ldots,X_n$ of size $dtimes d$ sampled i.i.d. from a distribution with mean $E[X]=mu$. While the concentration of averages of these matrices is well-studied, the concentration of other functions of such matric
es is less clear. One function which arises in the context of stochastic iterative algorithms, like Ojas algorithm for Principal Component Analysis, is the normalized matrix product defined as $prodlimits_{i=1}^{n}left(I + frac{X_i}{n}right).$ Concentration properties of this normalized matrix product were recently studied by cite{HW19}. However, their result is suboptimal in terms of the dependence on the dimension of the matrices as well as the number of samples. In this paper, we present a stronger concentration result for such matrix products which is optimal in $n$ and $d$ up to constant factors. Our proof is based on considering a matrix Doob martingale, controlling the quadratic variation of that martingale, and applying the Matrix Freedman inequality of Tropp cite{TroppIntro15}.
We prove a non-asymptotic concentration inequality for the spectral norm of sparse inhomogeneous random tensors with Bernoulli entries. For an order-$k$ inhomogeneous random tensor $T$ with sparsity $p_{max}geq frac{clog n}{n }$, we show that $|T-mat
hbb E T|=O(sqrt{n p_{max}}log^{k-2}(n))$ with high probability. The optimality of this bound up to polylog factors is provided by an information theoretic lower bound. By tensor unfolding, we extend the range of sparsity to $p_{max}geq frac{clog n}{n^{m}}$ with $1leq mleq k-1$ and obtain concentration inequalities for different sparsity regimes. We also provide a simple way to regularize $T$ such that $O(sqrt{n^{m}p_{max}})$ concentration still holds down to sparsity $p_{max}geq frac{c}{n^{m}}$ with $k/2leq mleq k-1$. We present our concentration and regularization results with two applications: (i) a randomized construction of hypergraphs of bounded degrees with good expander mixing properties, (ii) concentration of sparsified tensors under uniform sampling.
We propose a new approach for deriving probabilistic inequalities based on bounding likelihood ratios. We demonstrate that this approach is more general and powerful than the classical method frequently used for deriving concentration inequalities su
ch as Chernoff bounds. We discover that the proposed approach is inherently related to statistical concepts such as monotone likelihood ratio, maximum likelihood, and the method of moments for parameter estimation. A connection between the proposed approach and the large deviation theory is also established. We show that, without using moment generating functions, tightest possible concentration inequalities may be readily derived by the proposed approach. We have derived new concentration inequalities using the proposed approach, which cannot be obtained by the classical approach based on moment generating functions.
In this paper, we study the asymptotic thin-shell width concentration for random vectors uniformly distributed in Orlicz balls. We provide both asymptotic upper and lower bounds on the probability of such a random vector $X_n$ being in a thin shell o
f radius $sqrt{n}$ times the asymptotic value of $n^{-1/2}left(mathbb Eleft[| X_n|_2^2right]right)^{1/2}$ (as $ntoinfty$), showing that in certain ranges our estimates are optimal. In particular, our estimates significantly improve upon the currently best known general Lee-Vempala bound when the deviation parameter $t=t_n$ goes down to zero as the dimension $n$ of the ambient space increases. We shall also determine in this work the precise asymptotic value of the isotropic constant for Orlicz balls. Our approach is based on moderate deviation principles and a connection between the uniform distribution on Orlicz balls and Gibbs measures at certain critical inverse temperatures with potentials given by Orlicz functions, an idea recently presented by Kabluchko and Prochno in [The maximum entropy principle and volumetric properties of Orlicz balls, J. Math. Anal. Appl. {bf 495}(1) 2021, 1--19].
We obtain moment and Gaussian bounds for general Lipschitz functions evaluated along the sample path of a Markov chain. We treat Markov chains on general (possibly unbounded) state spaces via a coupling method. If the first moment of the coupling tim
e exists, then we obtain a variance inequality. If a moment of order 1+epsilon of the coupling time exists, then depending on the behavior of the stationary distribution, we obtain higher moment bounds. This immediately implies polynomial concentration inequalities. In the case that a moment of order 1+epsilon is finite uniformly in the starting point of the coupling, we obtain a Gaussian bound. We illustrate the general results with house of cards processes, in which both uniform and non-uniform behavior of moments of the coupling time can occur.
الأسئلة المقترحة
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
