Simple Relative Deviation Bounds for Covariance and Gram Matrices

• URL: http://arxiv.org/abs/2410.05754v1
• Date: Tue, 8 Oct 2024 07:28:56 GMT
• Title: Simple Relative Deviation Bounds for Covariance and Gram Matrices
• Authors: Daniel Barzilai, Ohad Shamir,
• Abstract summary: We provide non-asymptotic, relative deviation bounds for the eigenvalues of empirical covariance and gram matrices. Our results provide sharper control across the spectrum.
• Score: 34.99810116340191
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide non-asymptotic, relative deviation bounds for the eigenvalues of empirical covariance and gram matrices in general settings. Unlike typical uniform bounds, which may fail to capture the behavior of smaller eigenvalues, our results provide sharper control across the spectrum. Our analysis is based on a general-purpose theorem that allows one to convert existing uniform bounds into relative ones. The theorems and techniques emphasize simplicity and should be applicable across various settings.

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)
• A general error analysis for randomized low-rank approximation with application to data assimilation [42.57210316104905]
  We propose a framework for the analysis of the low-rank approximation error in Frobenius norm for centered and non-standard matrices. Under minimal assumptions, we derive accurate bounds in expectation and probability. Our bounds have clear interpretations that enable us to derive properties and motivate practical choices.
  arXiv  Detail & Related papers  (2024-05-08T04:51:56Z)
• The Inductive Bias of Flatness Regularization for Deep Matrix Factorization [58.851514333119255]
  This work takes the first step toward understanding the inductive bias of the minimum trace of the Hessian solutions in deep linear networks. We show that for all depth greater than one, with the standard Isometry Property (RIP) on the measurements, minimizing the trace of Hessian is approximately equivalent to minimizing the Schatten 1-norm of the corresponding end-to-end matrix parameters.
  arXiv  Detail & Related papers  (2023-06-22T23:14:57Z)
• Quantitative deterministic equivalent of sample covariance matrices with a general dependence structure [0.0]
  We prove quantitative bounds involving both the dimensions and the spectral parameter, in particular allowing it to get closer to the real positive semi-line. As applications, we obtain a new bound for the convergence in Kolmogorov distance of the empirical spectral distributions of these general models.
  arXiv  Detail & Related papers  (2022-11-23T15:50:31Z)
• On the Importance of Gradient Norm in PAC-Bayesian Bounds [92.82627080794491]
  We propose a new generalization bound that exploits the contractivity of the log-Sobolev inequalities. We empirically analyze the effect of this new loss-gradient norm term on different neural architectures.
  arXiv  Detail & Related papers  (2022-10-12T12:49:20Z)
• 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)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• On Uniform Convergence and Low-Norm Interpolation Learning [25.96459928769678]
  We show that uniformly bounding the difference between empirical and population errors cannot show any learning in the norm ball. We argue we can explain the consistency of the minimal-norm interpolator with a slightly weaker, yet standard, notion: uniform convergence of zero-error predictors in a norm ball.
  arXiv  Detail & Related papers  (2020-06-10T16:49:28Z)
• The semiring of dichotomies and asymptotic relative submajorization [0.0]
  We study quantum dichotomies and the resource theory of asymmetric distinguishability using a generalization of Strassen's theorem on preordered semirings. We find that an variant of relative submajorization, defined on unnormalized dichotomies, is characterized by real-valued monotones that are multiplicative under the tensor product and additive under the direct sum.
  arXiv  Detail & Related papers  (2020-04-22T14:13:26Z)

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.