Invariant Kernels: Rank Stabilization and Generalization Across Dimensions

• URL: http://arxiv.org/abs/2502.01886v1
• Date: Mon, 03 Feb 2025 23:37:43 GMT
• Title: Invariant Kernels: Rank Stabilization and Generalization Across Dimensions
• Authors: Mateo Díaz, Dmitriy Drusvyatskiy, Jack Kendrick, Rekha R. Thomas,
• Abstract summary: We show that symmetry has a pronounced impact on the rank of kernel matrices. Specifically, we compute the rank of a kernel of fixed degree that is invariant under various groups acting independently on its two arguments. In concrete circumstances, including the three aforementioned examples, symmetry dramatically decreases the rank making it independent of the data dimension.
• Score: 7.154556482351604
• License:
• Abstract: Symmetry arises often when learning from high dimensional data. For example, data sets consisting of point clouds, graphs, and unordered sets appear routinely in contemporary applications, and exhibit rich underlying symmetries. Understanding the benefits of symmetry on the statistical and numerical efficiency of learning algorithms is an active area of research. In this work, we show that symmetry has a pronounced impact on the rank of kernel matrices. Specifically, we compute the rank of a polynomial kernel of fixed degree that is invariant under various groups acting independently on its two arguments. In concrete circumstances, including the three aforementioned examples, symmetry dramatically decreases the rank making it independent of the data dimension. In such settings, we show that a simple regression procedure is minimax optimal for estimating an invariant polynomial from finitely many samples drawn across different dimensions. We complete the paper with numerical experiments that illustrate our findings.

Related papers

• Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements [0.0]
  We investigate the sample complexity of recovering tensors with low symmetric rank from symmetric rank-one measurements. We provide a sample complexity based on Fano's inequality, and discuss broader implications for our results for two-layer networks.
  arXiv  Detail & Related papers  (2025-02-07T18:12:32Z)
• Learning Infinitesimal Generators of Continuous Symmetries from Data [15.42275880523356]
  We propose a novel symmetry learning algorithm based on transformations defined with one- parameter groups. Our method is built upon minimal inductive biases, encompassing not only commonly utilized symmetries rooted in Lie groups but also extending to symmetries derived from nonlinear generators.
  arXiv  Detail & Related papers  (2024-10-29T08:28:23Z)
• SymmetryLens: A new candidate paradigm for unsupervised symmetry learning via locality and equivariance [0.0]
  We develop a new, unsupervised symmetry learning method that starts with raw data. We demonstrate that this coupling between symmetry and locality, together with a special optimization technique developed for entropy estimation, results in a highly stable system. The symmetry actions we consider are group representations, however, we believe the approach has the potential to be generalized to more general, nonlinear actions of non-commutative Lie groups.
  arXiv  Detail & Related papers  (2024-10-07T17:40:51Z)
• Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles [55.41644538483948]
  We design a deep-learning algorithm for the discovery and identification of the continuous group of symmetries present in a labeled dataset. We use fully connected neural networks to model the transformations symmetry and the corresponding generators. Our study also opens the door for using a machine learning approach in the mathematical study of Lie groups and their properties.
  arXiv  Detail & Related papers  (2023-01-13T16:25:25Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Learning Linear Symmetries in Data Using Moment Matching [0.0]
  We consider the unsupervised and semi-supervised problems of learning such symmetries in a distribution directly from data. We show that in the worst case this problem is as difficult as the graph automorphism problem. We develop and compare theoretically and empirically the effectiveness of different methods of selecting which eigenvectors should have eigenvalue -1 in the symmetry transformation.
  arXiv  Detail & Related papers  (2022-04-04T02:47:37Z)
• Test Set Sizing Via Random Matrix Theory [91.3755431537592]
  This paper uses techniques from Random Matrix Theory to find the ideal training-testing data split for a simple linear regression. It defines "ideal" as satisfying the integrity metric, i.e. the empirical model error is the actual measurement noise. This paper is the first to solve for the training and test size for any model in a way that is truly optimal.
  arXiv  Detail & Related papers  (2021-12-11T13:18:33Z)
• Probing symmetries of quantum many-body systems through gap ratio statistics [0.0]
  We extend the study of the gap ratio distribution P(r) to the case where discrete symmetries are present. We present a large set of applications in many-body physics, ranging from quantum clock models and anyonic chains to periodically-driven spin systems.
  arXiv  Detail & Related papers  (2020-08-25T17:11:40Z)
• Interpolation and Learning with Scale Dependent Kernels [91.41836461193488]
  We study the learning properties of nonparametric ridge-less least squares. We consider the common case of estimators defined by scale dependent kernels.
  arXiv  Detail & Related papers  (2020-06-17T16:43:37Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution. We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate. Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
  arXiv  Detail & Related papers  (2020-03-02T16:40:36Z)
• Inverse Learning of Symmetries [71.62109774068064]
  We learn the symmetry transformation with a model consisting of two latent subspaces. Our approach is based on the deep information bottleneck in combination with a continuous mutual information regulariser. Our model outperforms state-of-the-art methods on artificial and molecular datasets.
  arXiv  Detail & Related papers  (2020-02-07T13:48:52Z)

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.