Invariant Kernels: Rank Stabilization and Generalization Across Dimensions
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.
Code (1)
Similar Papers 제목 키워드 기반
Learning with Operator-valued Kernels in Reproducing Kernel Krein Spaces
Operator-valued kernels have shown promise in supervised learning problems with functional inputs and functional outputs. The crucial (and possibly restrictive) assumption of positive definiteness of operator-valued kern…
Graph Invariant Kernels
We introduce a novel kernel that upgrades the Weisfeiler-Lehman and other graph kernels to effectively exploit high-dimensional and continuous vertex attributes. Graphs are first decomposed into subgraphs. Vertices of th…
Graph ClassificationUse of symmetric kernels for convolutional neural networks
At this work we introduce horizontally symmetric convolutional kernels for CNNs which make the network output invariant to horizontal flips of the image. We also study other types of symmetric kernels which lead to verti…
Saddle-to-Saddle Dynamics Explains A Simplicity Bias Across Neural Network Architectures
Neural networks trained with gradient descent often learn solutions of increasing complexity over time, a phenomenon known as simplicity bias. Despite being widely observed across architectures, existing theoretical trea…
Revisiting Memory Efficient Kernel Approximation: An Indefinite Learning Perspective
Matrix approximations are a key element in large-scale algebraic machine learning approaches. The recently proposed method MEKA (Si et al., 2014) effectively employs two common assumptions in Hilbert spaces: the low-rank…