On the Sample Complexity of Learning with Geometric Stability
- URL: http://arxiv.org/abs/2106.07148v1
- Date: Mon, 14 Jun 2021 03:51:16 GMT
- Title: On the Sample Complexity of Learning with Geometric Stability
- Authors: Alberto Bietti, Luca Venturi, Joan Bruna
- Abstract summary: We study the sample complexity of learning problems where the target function presents such invariance and stability properties.
We provide non-parametric rates of convergence for kernel methods, and improvements in sample complexity by a factor equal to the size of the group.
- Score: 42.813141600050166
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many supervised learning problems involve high-dimensional data such as
images, text, or graphs. In order to make efficient use of data, it is often
useful to leverage certain geometric priors in the problem at hand, such as
invariance to translations, permutation subgroups, or stability to small
deformations. We study the sample complexity of learning problems where the
target function presents such invariance and stability properties, by
considering spherical harmonic decompositions of such functions on the sphere.
We provide non-parametric rates of convergence for kernel methods, and show
improvements in sample complexity by a factor equal to the size of the group
when using an invariant kernel over the group, compared to the corresponding
non-invariant kernel. These improvements are valid when the sample size is
large enough, with an asymptotic behavior that depends on spectral properties
of the group. Finally, these gains are extended beyond invariance groups to
also cover geometric stability to small deformations, modeled here as subsets
(not necessarily subgroups) of permutations.
Related papers
- Lie Group Decompositions for Equivariant Neural Networks [12.139222986297261]
We show how convolution kernels can be parametrized to build models equivariant with respect to affine transformations.
We evaluate the robustness and out-of-distribution generalisation capability of our model on the benchmark affine-invariant classification task.
arXiv Detail & Related papers (2023-10-17T16:04:33Z) - Gradient-Based Feature Learning under Structured Data [57.76552698981579]
In the anisotropic setting, the commonly used spherical gradient dynamics may fail to recover the true direction.
We show that appropriate weight normalization that is reminiscent of batch normalization can alleviate this issue.
In particular, under the spiked model with a suitably large spike, the sample complexity of gradient-based training can be made independent of the information exponent.
arXiv Detail & Related papers (2023-09-07T16:55:50Z) - Statistical Guarantees of Group-Invariant GANs [13.084804346845816]
Group-invariant generative adversarial networks (GANs) are a type of GANs in which the generators and discriminators are hardwired with group symmetries.
This work presents the first statistical performance guarantees for group-invariant generative models, specifically for GANs.
arXiv Detail & Related papers (2023-05-22T22:13:12Z) - The Exact Sample Complexity Gain from Invariances for Kernel Regression [37.74032673086741]
In practice, encoding invariances into models improves sample complexity.
We provide minimax optimal rates for kernel ridge regression on compact manifold.
Our results hold for any smooth compact Lie group action, even groups of positive dimension.
arXiv Detail & Related papers (2023-03-24T20:47:31Z) - Equivariant Representation Learning in the Presence of Stabilizers [13.11108596589607]
EquIN is suitable for group actions that are not free, i.e., that stabilize data via nontrivial symmetries.
EquIN is theoretically grounded in the orbit-stabilizer theorem from group theory.
arXiv Detail & Related papers (2023-01-12T11:43:26Z) - Equivariant Disentangled Transformation for Domain Generalization under
Combination Shift [91.38796390449504]
Combinations of domains and labels are not observed during training but appear in the test environment.
We provide a unique formulation of the combination shift problem based on the concepts of homomorphism, equivariance, and a refined definition of disentanglement.
arXiv Detail & Related papers (2022-08-03T12:31:31Z) - Local versions of sum-of-norms clustering [77.34726150561087]
We show that our method can separate arbitrarily close balls in the ball model.
We prove a quantitative bound on the error incurred in the clustering of disjoint connected sets.
arXiv Detail & Related papers (2021-09-20T14:45:29Z) - Group Equivariant Conditional Neural Processes [30.134634059773703]
We present the group equivariant conditional neural process (EquivCNP)
We show that EquivCNP achieves comparable performance to conventional conditional neural processes in a 1D regression task.
arXiv Detail & Related papers (2021-02-17T13:50:07Z) - Asymptotic Analysis of an Ensemble of Randomly Projected Linear
Discriminants [94.46276668068327]
In [1], an ensemble of randomly projected linear discriminants is used to classify datasets.
We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator.
We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
arXiv Detail & Related papers (2020-04-17T12:47:04Z) - Invariant Feature Coding using Tensor Product Representation [75.62232699377877]
We prove that the group-invariant feature vector contains sufficient discriminative information when learning a linear classifier.
A novel feature model that explicitly consider group action is proposed for principal component analysis and k-means clustering.
arXiv Detail & Related papers (2019-06-05T07:15:17Z)
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.