2021/06/13 by Alberto Bietti, Bietti, Alberto, Luca Venturi +3 · 1 citation
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2106.07148
openalex publication_date 2021/06/13 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Many supervised learning problems involve high-dimensional data such as\nimages, text, or graphs. In order to make efficient use of data, it is often\nuseful to leverage certain geometric priors in the problem at hand, such as\ninvariance to translations, permutation subgroups, or stability to small\ndeformations. We study the sample complexity of learning problems where the\ntarget function presents such invariance and stability properties, by\nconsidering spherical harmonic decompositions of such functions on the sphere.\nWe provide non-parametric rates of convergence for kernel methods, and show\nimprovements in sample complexity by a factor equal to the size of the group\nwhen using an invariant kernel over the group, compared to the corresponding\nnon-invariant kernel. These improvements are valid when the sample size is\nlarge enough, with an asymptotic behavior that depends on spectral properties\nof the group. Finally, these gains are extended beyond invariance groups to\nalso cover geometric stability to small deformations, modeled here as subsets\n(not necessarily subgroups) of permutations.\n