N. Alon, Y. Matias, and M. Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and system sciences, vol.58, issue.1, pp.137-147, 1999.

J. Audibert and O. Catoni, Robust linear least squares regression, The Annals of Statistics, vol.39, issue.5, pp.2766-2794, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00522534

A. Bellet, A. Habrard, and M. Sebban, A Survey on Metric Learning for Feature Vectors and Structured Data, 2013.
URL : https://hal.archives-ouvertes.fr/hal-01666935

G. Blom, Some properties of incomplete U-statistics, Biometrika, vol.63, issue.3, pp.573-580, 1976.

C. Brownlees, E. Joly, and G. Lugosi, Empirical risk minimization for heavy-tailed losses, The Annals of Statistics, vol.43, issue.6, pp.2507-2536, 2015.

S. Bubeck, N. Cesa-bianchi, and G. Lugosi, Bandits with heavy tail, IEEE Transactions on Information Theory, vol.59, issue.11, pp.7711-7717, 2013.

H. Callaert and P. Janssen, The Berry-Esseen theorem for U-statistics, The Annals of Statistics, vol.6, issue.2, pp.417-421, 1978.

O. Catoni, Challenging the empirical mean and empirical variance: a deviation study, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, vol.48, pp.1148-1185, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00517206

S. Clémençon, A statistical view of clustering performance through the theory of U-processes, Journal of Multivariate Analysis, vol.124, pp.42-56, 2014.

S. Clémençon, G. Lugosi, and N. Vayatis, Ranking and scoring using empirical risk minimization, Proceedings of COLT, 2005.

S. Clémençon, G. Lugosi, and N. Vayatis, Ranking and empirical risk minimization of U-statistics, The Annals of Statistics, vol.36, issue.2, pp.844-874, 2008.

S. Clémençon, I. Colin, and A. Bellet, Scaling-up Empirical Risk Minimization: Optimization of Incomplete U-statistics, Journal of Machine Learning Research, vol.17, pp.1-36, 2016.

L. Devroye, M. Lerasle, G. Lugosi, and R. I. Oliveira, Sub-gaussian mean estimators, The Annals of Statistics, vol.44, issue.6, pp.2695-2725, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01204519

W. Hoeffding, A class of statistics with asymptotically normal distribution, Ann. Math. Stat, vol.19, pp.293-325, 1948.

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

S. B. Hopkins, Sub-gaussian mean estimation in polynomial time, 2018.

D. Hsu and S. Sabato, Loss minimization and parameter estimation with heavy tails, The Journal of Machine Learning Research, vol.17, issue.1, pp.543-582, 2016.

M. Jerrum, L. Valiant, and V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theoretical Computer Science, vol.43, pp.169-188, 1986.

E. Joly and G. Lugosi, Robust estimation of u-statistics, Stochastic Processes and their Applications, vol.126, pp.3760-3773, 2016.

G. Lecué and M. Lerasle, Robust machine learning by median-of-means: theory and practice, 2017.

G. Lecué, M. Lerasle, and T. Mathieu, Robust classification via mom minimization, 2018.

A. J. Lee, U -statistics: Theory and practice, 1990.

M. Lerasle and R. I. Oliveira, Robust empirical mean estimators, 2011.

G. Lugosi and S. Mendelson, Risk minimization by medianof-means tournaments, 2016.

G. Lugosi and S. Mendelson, Sub-gaussian estimators of the mean of a random vector, 2017.

C. Mcdiarmid, On the method of bounded differences, pp.148-188, 1989.

S. Mendelson, On aggregation for heavy-tailed classes. Probability Theory and Related Fields, vol.168, pp.641-674, 2017.

S. Minsker and X. Wei, Robust modifications of u-statistics and applications to covariance estimation problems, 2018.

S. Minsker, Geometric Median and Robust Estimation in Banach Spaces, Bernoulli, vol.21, issue.4, pp.2308-2335, 2015.

A. S. Nemirovsky and D. B. Yudin, Problem Complexity and Method Efficiency in Optimization, 1983.

V. H. Peña and E. Giné, Decoupling: from dependence to independence, 1999.

R. Serfling, Approximation Theorems of Mathematical Statistics, Wiley Series in Probability and Statistics, 1980.

A. Van-der-vaart, Asymptotic Statistics. Cambridge university press, 2000.

R. Vogel, S. Clémençon, and A. Bellet, A Probabilistic Theory of Supervised Similarity Learning: Pairwise Bipartite Ranking and Pointwise ROC Curve Optimization, International Conference in Machine Learning, 2018.
URL : https://hal.archives-ouvertes.fr/hal-02288518