Concentration Inequalities for Exchangeable Tensors and Matrix-valued Data
We study concentration inequalities for structured weighted sums of random data, including (i) tensor inner products and (ii) sequential matrix sums. We are interested in tail bounds and concentration inequalities for those structured weighted sums under exchangeability, extending beyond the classical framework of independent terms. We develop Hoeffding and Bernstein bounds provided with structure-dependent exchangeability. Along the way, we recover known results in weighted sum of exchangeable random variables and i.i.d. sums of random matrices to the optimal constants. Notably, we develop a sharper concentration bound for combinatorial sum of matrix arrays than the results previously derived from Chatterjee's method of exchangeable pairs. For applications, the richer structures provide us with novel analytical tools for estimating the average effect of multi-factor response models and studying fixed-design sketching methods in federated averaging. We apply our results to these problems, and find that our theoretical predictions are corroborated by numerical evidence.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Positive Semidefinite Matrix Supermartingales
We explore the asymptotic convergence and nonasymptotic maximal inequalities of supermartingales and backward submartingales in the space of positive semidefinite matrices. These are natural matrix analogs of scalar nonn…
EconometricsvalidConcentration inequalities for correlated network-valued processes with applications to community estimation and changepoint analysis
Network-valued time series are currently a common form of network data. However, the study of the aggregate behavior of network sequences generated from network-valued stochastic processes is relatively rare. Most of the…
Time SeriesTime Series AnalysisConcentration inequalities under sub-Gaussian and sub-exponential conditions
We prove analogues of the popular bounded difference inequality (also called McDiarmid's inequality) for functions of independent random variables under sub-gaussian and sub-exponential conditions. Applied to vector-valu…
regressionVector-valued self-normalized concentration inequalities beyond sub-Gaussianity
The study of self-normalized processes plays a crucial role in a wide range of applications, from sequential decision-making to econometrics. While the behavior of self-normalized concentration has been widely investigat…
Concentration inequalities for high-dimensional linear processes with dependent innovations
We develop concentration inequalities for the $l_\infty$ norm of vector linear processes with sub-Weibull, mixingale innovations. This inequality is used to obtain a concentration bound for the maximum entrywise norm of …
Time Series