CoChat
Sign Up
PreprintCited by 1

The DOI matches its DataCite record.

On the Sample Complexity of Learning under Invariance and Geometric Stability

Bietti, Alberto, Venturi, Luca, Bruna, Joan·2021·arXiv
DOI 10.48550/arxiv.2106.07148arXiv 2106.07148
Open this paper in CoChat — free account

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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2106.07148

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 29

  1. K. Atkinson and W. Han. Spherical harmonics and approximations on the unit sphere: an introduction, volume 2044. Springer Science & Business Media, 2012.
  2. F. Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research (JMLR), 18(1):629-681, 2017.
  3. A. Bietti. Approximation and learning with deep convolutional models: a kernel perspective. arXiv preprint arXiv:2102.10032, 2021. · arXiv
  4. A. Bietti and F. Bach. Deep equals shallow for ReLU networks in kernel regimes. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
  5. A. Bietti and J. Mairal. Group invariance, stability to deformations, and complexity of deep convolutional representations. Journal of Machine Learning Research (JMLR), 20(25):1-49, 2019.
  6. J. Bruna and S. Mallat. Invariant scattering convolution networks. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 35(8):1872-1886, 2013.
  7. A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
  8. Y. Cho and L. K. Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems (NIPS), 2009.
  9. C. Ciliberto, F. Bach, and A. Rudi. Localized structured prediction. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
  10. N. Cohen and A. Shashua. Inductive bias of deep convolutional networks through pooling geometry. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
  11. F. Cucker and S. Smale. On the mathematical foundations of learning. Bulletin of the American mathematical society, 39(1):1-49, 2002.
  12. S. S. Du, Y. Wang, X. Zhai, S. Balakrishnan, R. Salakhutdinov, and A. Singh. How many samples are needed to estimate a convolutional neural network? In Advances in Neural Information Processing Systems (NeurIPS), 2018.
  13. C. Efthimiou and C. Frye. Spherical harmonics in p dimensions. World Scientific, 2014.
  14. B. Elesedy and S. Zaidi. Provably strict generalisation benefit for equivariant models. In Proceedings of the International Conference on Machine Learning (ICML), 2021.
  15. A. Favero, F. Cagnetta, and M. Wyart. Locality defeats the curse of dimensionality in con- volutional teacher-student scenarios. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
  16. S. Fischer and I. Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research (JMLR), 21(205):1-38, 2020.
  17. T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
  18. Z. Li, Y. Zhang, and S. Arora. Why are convolutional nets more sample-efficient than fully- connected nets? In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
  19. J. Mairal, P. Koniusz, Z. Harchaoui, and C. Schmid. Convolutional kernel networks. In Advances in Neural Information Processing Systems (NIPS), 2014.
  20. E. Malach and S. Shalev-Shwartz. Computational separation between convolutional and fully-connected networks. In Proceedings of the International Conference on Learning Repre- sentations (ICLR), 2021.
  21. S. Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10):1331-1398, 2012.
  22. S. Mei, T. Misiakiewicz, and A. Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory (COLT), 2021.
  23. H. N. Mhaskar and T. Poggio. Deep vs. shallow networks: An approximation theory perspective. Analysis and Applications, 14(06):829-848, 2016.
  24. L. Petrini, A. Favero, M. Geiger, and M. Wyart. Relative stability toward diffeomorphisms indicates performance in deep nets. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
  25. L. Pillaud-Vivien, A. Rudi, and F. Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
  26. T. Poggio, H. Mhaskar, L. Rosasco, B. Miranda, and Q. Liao. Why and when can deep-but not shallow-networks avoid the curse of dimensionality: a review. International Journal of Automation and Computing, 14(5):503-519, 2017.
  27. A. J. Smola, Z. L. Ovari, and R. C. Williamson. Regularization with dot-product kernels. In Advances in Neural Information Processing Systems (NIPS), 2001.
  28. J. Sokolic, R. Giryes, G. Sapiro, and M. Rodrigues. Generalization error of invariant classi- fiers. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
  29. M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.

Cited by

Metadata

Authors
Bietti, A., Venturi, L., & Bruna, J.
Venue
arXiv
Publisher
arXiv
Published
2021
DOI
10.48550/arxiv.2106.07148
arXiv
2106.07148
References
0
Type
Preprint
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review