N. Alon, S. Ben-david, N. Cesa-bianchi, and D. Haussler, Scale-sensitive dimensions, uniform convergence, and learnability, Journal of the ACM, vol.44, issue.4, pp.615-631, 1997.

B. Samy, D. Krzysztof, J. Thorsten, K. Marius, and V. , Extreme Classification (Dagstuhl Seminar 18291), Dagstuhl Reports, vol.8, issue.7, pp.62-80, 2019.

M. Anthony, Uniform convergence and learnability, 1991.

M. Anthony and P. L. Bartlett, Neural Network Learning: Theoretical Foundations, 1999.

R. Babbar, Machine Learning Strategies for Large-scale Taxonomies, 2014.
URL : https://hal.archives-ouvertes.fr/tel-01551786

K. I. Babenko, On the entropy of a class of analytic functions, Nauchn. Dokl. Vysshei Shkoly Ser. Fiz. Mat. Nauk, issue.2, pp.9-16, 1958.

P. L. Bartlett, The sample complexity of pattern classification with neural networks: The size of the weights is more important than the size of the network, IEEE Transactions on Information Theory, vol.44, issue.2, pp.525-536, 1998.

P. L. Bartlett, S. Boucheron, and G. Lugosi, Model selection and error estimation, Machine Learning, vol.48, pp.85-113, 2002.

P. L. Bartlett, O. Bousquet, and S. Mendelson, Local Rademacher complexities, The Annals of Statistics, vol.33, issue.4, pp.1497-1537, 2005.

P. L. Bartlett, D. J. Foster, and M. Telgarsky, Spectrally-normalized margin bounds for neural networks, Advances in Neural Information Processing Systems, pp.6240-6249, 2017.

P. L. Bartlett, S. R. Kulkarni, and S. E. Posner, Covering numbers for real-valued function classes, IEEE Transactions on Information Theory, vol.43, issue.5, pp.1721-1724, 1997.

P. L. Bartlett and P. M. Long, More theorems about scale-sensitive dimensions and learning, COLT'95, pp.392-401, 1995.

P. L. Bartlett and S. Mendelson, Rademacher and Gaussian complexities: Risk bounds and structural results, Journal of Machine Learning Research, vol.3, pp.463-482, 2002.

P. L. Bartlett and J. Shawe-taylor, Generalization performance of support vector machines and other pattern classifiers, Advances in Kernel Methods -Support Vector Learning, vol.4, pp.43-54, 1999.

S. Ben-david, N. Cesa-bianchi, D. Haussler, and P. Long, Characterizations of learnability for classes of 0,..., n-valued functions, Journal of Computer and System Sciences, vol.50, issue.1, pp.74-86, 1995.

A. Berlinet and C. Thomas-agnan, Reproducing Kernel Hilbert Spaces in Probability and Statistics, 2004.

B. C. Berndt, Ramanujan's Notebooks, Part I, 1985.

S. Bernstein, The Theory of Probabilities, 1946.

L. Breiman, J. H. Friedman, R. Olshen, and C. J. Stone, Classification and regression trees, 1984.

C. Cortes and V. N. Vapnik, Support-vector networks, Machine Learning, vol.20, pp.273-297, 1995.

L. Devroye, L. Györfi, and G. Lugosi, A Probabilistic Theory of Pattern Recognition, 1996.

Ü. Do?an, T. Glasmachers, and C. Igel, A unified view on multi-class support vector classification, Journal of Machine Learning Research, vol.17, issue.45, pp.1-32, 2016.

H. H. Duan, Bounding the fat shattering dimension of a composition function class built using a continuous logic connective, The Waterloo Mathematics Review, vol.2, issue.1, pp.1-21, 2012.

R. M. Dudley, A course on empirical processes, 1982.

R. M. Dudley, Universal Donsker classes and metric entropy, The Annals of Probability, vol.15, issue.4, pp.1306-1326, 1987.

R. M. Dudley, Uniform central limit theorems, 1999.

R. M. Dudley, E. Giné, and J. Zinn, Uniform and universal Glivenko-Cantelli classes, Journal of Theoretical Probability, vol.4, issue.3, pp.485-510, 1991.

M. Farooq and I. Steinwart, Learning rates for kernel-based expectile regression, 2017.

W. Feller, An introduction to probability theory and its applications, vol.2, 2008.

E. Giné and J. Zinn, Some limit theorems for empirical processes, The Annals of Probability, vol.12, issue.4, pp.929-989, 1984.

V. Goodman, Some probability and entropy estimates for Gaussian measures, Probability in Banach Spaces 6, pp.150-156, 1990.

L. A. Gottlieb, A. Kontorovich, and R. Krauthgamer, Efficient classification for metric data, IEEE Transactions on Information Theory, vol.60, issue.9, pp.5750-5759, 2014.

A. J. Grove, N. Littlestone, and D. Schuurmans, General convergence results for linear discriminant updates, Machine Learning, vol.43, pp.173-210, 2001.

Y. Guermeur, VC theory of large margin multi-category classifiers, Journal of Machine Learning Research, vol.8, pp.2551-2594, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00203093

Y. Guermeur, A generic model of multi-class support vector machine, International Journal of Intelligent Information and Database Systems, vol.6, issue.6, pp.555-577, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00596175

Y. Guermeur, L p -norm Sauer-Shelah lemma for margin multi-category classifiers, Journal of Computer and System Sciences, vol.89, pp.450-473, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01371331

Y. Guermeur, Combinatorial and Structural Results for gamma-Psi-dimensions, 2018.

Y. Guo, P. L. Bartlett, J. Shawe-taylor, and R. C. Williamson, Covering numbers for support vector machines, IEEE Transactions on Information Theory, vol.48, issue.1, pp.239-250, 2002.

A. Gupta, R. Krauthgamer, and J. Lee, Bounded geometries, fractals, and low-distortion embeddings, p.534, 2003.

D. Haussler, Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension, Journal of Combinatorial Theory, Series A, vol.69, issue.2, pp.217-232, 1995.

W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association, vol.58, pp.13-30, 1963.

S. M. Kakade, S. Shalev-shwartz, and A. Tewari, Regularization techniques for learning with matrices, Journal of Machine Learning Research, vol.13, pp.1865-1890, 2012.

M. J. Kearns and R. E. Schapire, Efficient distribution-free learning of probabilistic concepts, Journal of Computer and System Sciences, vol.48, issue.3, pp.464-497, 1994.

A. N. Kolmogorov, Certain asymptotic characteristics of completely bounded metric spaces, Doklady Akademii Nauk SSSR, vol.108, issue.3, pp.385-388, 1956.

A. N. Kolmogorov and V. M. Tikhomirov, -entropy and -capacity of sets in functional spaces, vol.17, pp.277-364, 1961.

V. Koltchinskii, Rademacher penalties and structural risk minimization, IEEE Transactions on Information Theory, vol.47, issue.5, pp.1902-1914, 2001.

V. Koltchinskii and D. Panchenko, Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, vol.30, pp.1-50, 2002.

V. Koltchinskii, On the central limit theorem for empirical measures. Theory of probability and mathematical statistics, vol.24, pp.71-82, 1981.

A. Kontorovich and R. Weiss, Maximum margin muliclass nearest neighbors, ICML'14, 2014.

A. Krizhevsky, I. Sutskever, and G. E. Hinton, Imagenet classification with deep convolutional neural networks, Advances in neural information processing systems, pp.1097-1105, 2012.

J. Kuelbs and W. V. Li, Metric entropy and the small ball problem for gaussian measures, Journal of Functional Analysis, vol.116, issue.1, pp.133-157, 1993.

T. Kühn, Covering numbers of Gaussian reproducing kernel Hilbert spaces, Journal of Complexity, vol.27, issue.5, pp.489-499, 2011.

V. Kuznetsov, M. Mohri, and U. Syed, Multi-class deep boosting, NIPS 27, pp.2501-2509, 2014.

M. Ledoux and M. Talagrand, Probability in Banach Spaces: Isoperimetry and Processes, 1991.

Y. Lei, Ü. Do?an, A. Binder, and M. Kloft, Multi-class SVMs: From tighter data-dependent generalization bounds to novel algorithms, NIPS 28, pp.2026-2034, 2015.

P. Massart, Some applications of concentration inequalities to statistics, vol.9, pp.245-303, 2000.

A. Maurer, A vector-contraction inequality for Rademacher complexities, International Conference on Algorithmic Learning Theory, pp.3-17, 2016.

C. Mcdiarmid, On the method of bounded differences, London Mathematical Society Lecture Note Series, vol.141, pp.148-188, 1989.

S. Mendelson, Rademacher averages and phase transitions in Glivenko-Cantelli classes, IEEE Transactions on Information Theory, vol.48, issue.1, pp.251-263, 2002.

S. Mendelson, A few notes on statistical learning theory, 2003.

S. Mendelson and R. Vershynin, Entropy and the combinatorial dimension, Inventiones mathematicae, vol.152, pp.37-55, 2003.

M. Minsky, S. Papert, . Mcculloch, and W. Pitts, A Logical Calculus of the Ideas Imminent in Nervous Activity, Bulletin of Mathematical Biophysics, vol.5, pp.115-133, 1943.

M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of Machine Learning, 2012.

K. Musayeva, F. Lauer, and Y. Guermeur, Rademacher complexity and generalization performance of multi-category margin classifiers, Neurocomputing, vol.342, pp.6-15, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01941089

B. K. Natarajan, On learning sets and functions, Machine Learning, vol.4, pp.67-97, 1989.

B. Neyshabur, S. Bhojanapalli, D. Mcallester, and N. Srebro, Exploring generalization in deep learning, Advances in Neural Information Processing Systems, pp.5947-5956, 2017.

B. Neyshabur, S. Bhojanapalli, and N. Srebro, A PAC-Bayesian approach to spectrallynormalized margin bounds for neural networks, 2017.

D. Pollard, Convergence of Stochastic Processes, 1984.

D. Pollard, Empirical processes: theory and applications, NSF-CBMS regional conference series in probability and statistics, 1990.

T. Popoviciu, Sur les équations algébriques ayant toutes leurs racines réelles. Mathematica, vol.9, pp.129-145, 1935.

J. R. Quinlan, Induction of decision trees, Machine learning, vol.1, issue.1, pp.81-106, 1986.

F. Rosenblatt, The perceptron: a probabilistic model for information storage and organization in the brain, Psychological review, vol.65, issue.6, p.386, 1958.

M. Rudelson and R. Vershynin, Combinatorics of random processes and sections of convex bodies, Annals of Mathematics, vol.164, issue.2, pp.603-648, 2006.

N. Sauer, On the density of families of sets, Journal of Combinatorial Theory, Series A, vol.13, issue.1, pp.145-147, 1972.

S. Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific Journal of Mathematics, vol.41, issue.1, pp.247-261, 1972.

N. Srebro, K. Sridharan, and A. Tewari, Smoothness, low noise and fast rates, Advances in neural information processing systems, pp.2199-2207, 2010.

I. Steinwart and A. Christmann, Support vector machines, 2008.

I. Steinwart and C. Scovel, Fast rates for support vector machines using Gaussian kernels, The Annals of Statistics, vol.35, issue.2, pp.575-607, 2007.

S. Szarek, On the best constants in the Khinchin inequality, Studia Mathematica, vol.2, issue.58, pp.197-208, 1976.

M. Talagrand, The Glivenko-Cantelli problem, ten years later, Journal of Theoretical Probability, vol.9, issue.2, pp.371-384, 1996.

M. Talagrand, New concentration inequalities in product spaces, Inventiones mathematicae, vol.126, issue.3, pp.505-563, 1996.

M. Talagrand, Vapnik-Chervonenkis type conditions and uniform Donsker classes of functions, The Annals of Probability, vol.31, issue.3, pp.1565-1582, 2003.

M. Talagrand, Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems, 2014.

V. M. Tikhomirov, Certain asymptotic characteristics of completely bounded metric spaces, Doklady Akademii Nauk SSSR, vol.117, pp.191-194, 1957.

A. W. Van-der-vaart and J. H. Van-zanten, Adaptive Bayesian estimation using a Gaussian random field with inverse gamma bandwidth, The Annals of Statistics, pp.2655-2675, 2009.

A. W. Van-der-vaart and J. A. Wellner, Weak Convergence and Empirical Processes, With Applications to Statistics, Springer Series in Statistics, 1996.

V. N. Vapnik, Statistical Learning Theory, 1998.

V. N. Vapnik, A. Ya, and . Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and its Applications, pp.264-280, 1971.

A. R. Vitale, Some comparisons for Gaussian processes, Proceedings of the American Mathematical Society, pp.3043-3046, 2000.

A. G. Vitushkin, The absolute ?-entropy of metric spaces, Doklady Akademii Nauk, vol.117, pp.745-747, 1957.

R. C. Williamson, A. J. Smola, and B. Schölkopf, Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators, IEEE Transactions on Information Theory, vol.47, issue.6, pp.2516-2532, 2001.

T. Zhang, Covering number bounds of certain regularized linear function classes, Journal of Machine Learning Research, vol.2, pp.527-550, 2002.

T. Zhang, Statistical analysis of some multi-category large margin classification methods, Journal of Machine Learning Research, vol.5, pp.1225-1251, 2004.

Y. Zhang, J. Lee, M. Wainwright, and M. I. Jordan, On the learnability of fully-connected neural networks, In Artificial Intelligence and Statistics, pp.83-91, 2017.

D. Zhou, The covering number in learning theory, Journal of Complexity, vol.18, issue.3, pp.739-767, 2002.