Positive Semidefinite Supermartingales and Randomized Matrix Concentration Inequalities

• URL: http://arxiv.org/abs/2401.15567v3
• Date: Mon, 26 Feb 2024 05:12:46 GMT
• Title: Positive Semidefinite Supermartingales and Randomized Matrix Concentration Inequalities
• Authors: Hongjian Wang, Aaditya Ramdas
• Abstract summary: 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.
• Score: 35.61651875507142
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present new concentration inequalities for either martingale dependent or exchangeable random symmetric matrices under a variety of tail conditions, encompassing now-standard Chernoff bounds to self-normalized heavy-tailed settings. These inequalities are often randomized in a way that renders them strictly tighter than existing deterministic results in the literature, are typically expressed in the Loewner order, and are sometimes valid at arbitrary data-dependent stopping times. Along the way, we explore the theory of positive semidefinite supermartingales and maximal inequalities, a natural matrix analog of scalar nonnegative supermartingales that is potentially of independent interest.

Related papers

• Sharp Matrix Empirical Bernstein Inequalities [30.14855064043107]
  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.
  arXiv  Detail & Related papers  (2024-11-14T15:27:18Z)
• A Result About the Classification of Quantum Covariance Matrices Based on Their Eigenspectra [0.0]
  We find a non-trivial class of eigenspectra with the property that the set of quantum covariance matrices corresponding to any eigenspectrum in this class are related by symplectic transformations. We show that all non-degenerate eigenspectra with this property must belong to this class, and that the set of such eigenspectra coincides with the class of non-degenerate eigenspectra.
  arXiv  Detail & Related papers  (2023-08-07T09:40:09Z)
• The extended Ville's inequality for nonintegrable nonnegative supermartingales [30.14855064043107]
  We rigorously present an extended theory of nonnegative supermartingales requiring neither integrability nor finiteness. We derive a key maximal inequality foreshadowed by Robbins, which we call the extended Ville's inequality. We derive an extension of the method of mixtures, which applies to $sigma$-finite mixtures of our extended nonnegative supermartingales.
  arXiv  Detail & Related papers  (2023-04-03T17:28:51Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• 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)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  This paper theoretically derives a unified form of JMMD that is easy to optimize. From the revealed unified JMMD, we illustrate that JMMD degrades the feature-label dependence that benefits to classification. We propose a novel MMD matrix to promote the dependence, and devise a novel label kernel that is robust to label distribution shift.
  arXiv  Detail & Related papers  (2021-01-25T09:46:14Z)
• Statistics of the Spectral Form Factor in the Self-Dual Kicked Ising Model [0.0]
  We show that at large enough times the probability distribution agrees exactly with the prediction of Random Matrix Theory. This behaviour is due to a recently identified additional anti-unitary symmetry of the self-dual kicked Ising model.
  arXiv  Detail & Related papers  (2020-09-07T16:02:29Z)
• Metrizing Weak Convergence with Maximum Mean Discrepancies [88.54422104669078]
  This paper characterizes the maximum mean discrepancies (MMD) that metrize the weak convergence of probability measures for a wide class of kernels. We prove that, on a locally compact, non-compact, Hausdorff space, the MMD of a bounded continuous Borel measurable kernel k, metrizes the weak convergence of probability measures if and only if k is continuous.
  arXiv  Detail & Related papers  (2020-06-16T15:49:33Z)
• On Random Matrices Arising in Deep Neural Networks. Gaussian Case [1.6244541005112747]
  The paper deals with distribution of singular values of product of random matrices arising in the analysis of deep neural networks. The problem has been considered in recent work by using the techniques of free probability theory.
  arXiv  Detail & Related papers  (2020-01-17T08:30:57Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  We develop a relative error bound for nuclear norm regularized matrix completion. We derive a relative upper bound for recovering the best low-rank approximation of the unknown matrix.
  arXiv  Detail & Related papers  (2015-04-26T13:12:16Z)

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.