Sharp Matrix Empirical Bernstein Inequalities

• URL: http://arxiv.org/abs/2411.09516v1
• Date: Thu, 14 Nov 2024 15:27:18 GMT
• Title: Sharp Matrix Empirical Bernstein Inequalities
• Authors: Hongjian Wang, Aaditya Ramdas,
• Abstract summary: We present two sharp empirical Bernstein inequalities for symmetric random matrices with bounded eigenvalues. By sharp, we mean that both inequalities adapt to the unknown variance in a tight manner.
• Score: 30.14855064043107
• License:
• Abstract: We present two sharp empirical Bernstein inequalities for symmetric random matrices with bounded eigenvalues. By sharp, we mean that both inequalities adapt to the unknown variance in a tight manner: the deviation captured by the first-order $1/\sqrt{n}$ term asymptotically matches the matrix Bernstein inequality exactly, including constants, the latter requiring knowledge of the variance. Our first inequality holds for the sample mean of independent matrices, and our second inequality holds for a mean estimator under martingale dependence at stopping times.

Related papers

• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Log-majorization and matrix norm inequalities with application to quantum information [2.7195102129095003]
  We show an extension of Araki's log-majorization and apply it to the $alpha$-$z$-R'enyi divergence in quantum information. The paper includes an appendix to correct the proof of the author's old result on the equality case in the norm inequality for the weighted geometric mean.
  arXiv  Detail & Related papers  (2024-02-25T11:33:46Z)
• Positive Semidefinite Supermartingales and Randomized Matrix Concentration Inequalities [35.61651875507142]
  We present new concentration inequalities for either martingale dependent or exchangeable random symmetric matrices under a variety of tail conditions. These inequalities are often randomized in a way that renders them strictly tighter than existing deterministic results in the literature.
  arXiv  Detail & Related papers  (2024-01-28T04:22:43Z)
• A class of 2 X 2 correlated random-matrix models with Brody spacing distribution [0.0]
  A class of 2 X 2 random-matrix models is introduced for which the Brody distribution is the eigenvalue spacing distribution. The random matrices introduced here differ from those of the Gaussian Orthogonal Ensemble (GOE) in three important ways.
  arXiv  Detail & Related papers  (2023-08-03T03:11:54Z)
• Split-kl and PAC-Bayes-split-kl Inequalities [15.63537071742102]
  We name a split-kl inequality, which combines the power of the kl inequality with the ability to exploit low variance. For Bernoulli random variables the kl inequality is tighter than the Empirical Bernstein, for random variables taking values inside a bounded interval the Empirical Bernstein inequality is tighter than the kl. We discuss an application of the split-kl inequality to bounding excess losses.
  arXiv  Detail & Related papers  (2022-06-01T18:42:02Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Can Single-Shuffle SGD be Better than Reshuffling SGD and GD? [77.82009268160053]
  We conjecture that the means of matrix products corresponding to with- and without-replacement variants of SGD satisfy a series of spectral norm inequalities. We present theorems that support our conjecture by proving several special cases.
  arXiv  Detail & Related papers  (2021-03-12T04:34:45Z)
• Concentration inequality for U-statistics of order two for uniformly ergodic Markov chains [0.0]
  We prove a concentration inequality for U-statistics of order two for uniformly ergodic Markov chains. We show that we can recover the convergence rate of Arcones and Gin'e who proved a concentration result for U-statistics of independent random variables and canonical kernels.
  arXiv  Detail & Related papers  (2020-11-20T15:14:34Z)
• Leveraged Matrix Completion with Noise [84.20092979053119]
  We show that we can provably recover an unknown $ntimes n$ matrix of rank $r$ from just about $mathcalO(nrlog2 (n))$ entries. Our proofs are supported by a novel approach that phrases sufficient optimality conditions based on the Golfing Scheme.
  arXiv  Detail & Related papers  (2020-11-11T16:25:45Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.