Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Concentration Inequalities for Vector-Valued Lipschitz Functions
152
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We derive two upper bounds for the probability of deviation of a vector-valued Lipschitz function of a collection of random variables from its expected value. The resulting upper bounds can be tighter than bounds obtained by a direct application of a classical theorem due to Bobkov and G{o}tze.
rate research
Read More
We present novel martingale concentration inequalities for martingale differences with finite Orlicz-$psi_alpha$ norms. Such martingale differences with weak exponential-type tails scatters in many statistical applications and can be heavier than sub-exponential distributions. In the case of one dimension, we prove in general that for a sequence of scalar-valued supermartingale difference, the tail bound depends solely on the sum of squared Orlicz-$psi_alpha$ norms instead of the maximal Orlicz-$psi_alpha$ norm, generalizing the results of Lesigne & Volny (2001) and Fan et al. (2012). In the multidimensional case, using a dimension reduction lemma proposed by Kallenberg & Sztencel (1991) we show that essentially the same concentration tail bound holds for vector-valued martingale difference sequences.
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 matrices 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 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.
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 time 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.
We establish concentration inequalities in the class of ultra log-concave distributions. In particular, we show that ultra log-concave distributions satisfy Poisson concentration bounds. As an application, we derive concentration bounds for the intrinsic volumes of a convex body, which generalizes and improves a result of Lotz, McCoy, Nourdin, Peccati, and Tropp (2019).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
