R. Massih, N. Amini, and . Usunier, Learning with Partially Labeled and Interdependent Data, 2015.

G. Bennett, Probability inequalities for the sum of independent random variables, Journal of the American Statistical Association, vol.57, issue.297, pp.33-45, 1962.

S. Bernstein, On a modification of Chebyshev's inequality and of the error formula of Laplace, Ann. Sci. Inst. Sav. Ukraine, Sect. Math, vol.1, issue.4, pp.38-49, 1924.

S. Boyd and L. Vandenberghe, Convex Optimization, 2004.

R. C. Bradley, Basic properties of strong mixing conditions, a survey and some open questions, Probability Surveys, vol.2, issue.2, pp.107-144, 2005.

H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, The Annals of Mathematical Statistics, vol.23, issue.4, pp.493-507, 1952.

R. K. Fan, L. Chung, and . Lu, American mathematical society, vol.107, 2006.

J. Charles, J. H. Colbourn, and . Dimitz, Handbook of Combinatorial Designs, 2010.

F. Cucker and D. Zhou, Learning Theory: An Approximation Theory Viewpoint, 2007.

P. Erdos and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets, vol.10, pp.609-627, 1975.

T. Evgeniou and M. Pontil, On the v ? dimension for regression in reproducing kernel hilbert spaces, International Conference on Algorithmic Learning Theory, pp.106-117, 1999.

D. Fierens, H. Blockeel, M. Bruynooghe, and J. Ramon, Logical Bayesian networks and their relation to other probabilistic logical models, Inductive Logic Programming, pp.121-135, 2005.

N. Friedman, L. Getoor, D. Koller, and A. Pfeffer, Learning probabilistic relational models, IJCAI, vol.99, pp.1300-1309, 1999.

R. Michael, D. S. Garey, and . Johnson, Computers and Intractibility, A Guide to the Theory of NP-Completeness, 1979.

, Introduction to Statistical Relational Learning, 2007.

C. Zheng, L. Guo, and . Shi, Classification with non-iid sampling, Mathematical and Computer Modelling, vol.54, issue.5, pp.1347-1364, 2011.

W. Hoeffding, A class of statistics with asymptotically normal distributions, Annals of Statistics, vol.19, issue.3, 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.

M. Jaeger, Relational Bayesian networks, Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, pp.266-273, 1997.

S. Janson, Large deviations for sums of partly dependent random variables, Random Structures & Algorithms, vol.24, issue.3, pp.234-248, 2004.

J. Jensen, Sur les fonctions convexes et les inégalités entre les valeurs moyennes, Acta Mathematica, vol.30, issue.1, pp.175-193, 1906.

D. Knoke, Economic networks, 2014.

S. Leinhardt, Social networks: A developing paradigm, 2013.

Y. Regina and . Liu, Bootstrap procedures under some non-iid models, The Annals of Statistics, vol.16, issue.4, pp.1696-1708, 1988.

T. Liu, Learning to rank for information retrieval, Foundations and Trends® in Information Retrieval, vol.3, issue.3, pp.225-331, 2009.

J. Matousek and J. Nesetril, Invitation to Discrete Mathematics, 1998.

S. Dharmendra, E. Modha, and . Masry, Minimum complexity regression estimation with weakly dependent observations. Information Theory, IEEE Transactions on, vol.42, issue.6, pp.2133-2145, 1996.

M. Nykl, K. Je?ek, D. Fiala, and M. Dostal, Pagerank variants in the evaluation of citation networks, Journal of Informetrics, vol.8, issue.3, pp.683-692, 2014.

L. Ralaivola and M. Amini, Entropy-Based Concentration Inequalities for Dependent Variables, Proceedings of the 32 nd International Conference on Machine Learning, pp.1-9, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01211199

L. Ralaivola, M. Szafranski, and G. Stempfel, Chromatic PAC-Bayes Bounds for Non-IID Data: Applications to Ranking and Stationary ?-Mixing Processes, Journal of Machine Learning Research, vol.11, pp.1927-1956, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00415162

A. Ryan, L. K. Rossi, D. W. Mcdowell, J. Aha, and . Neville, Transforming graph data for statistical relational learning, Journal of Artificial Intelligence Research, vol.45, issue.1, pp.363-441, 2012.

R. Edward, . Scheinerman, and . Daniel-h-ullman, Fractional graph theory: a rational approach to the theory of graphs, Courier Corporation, 2011.

J. Shawe-taylor, P. L. Bartlett, R. C. Williamson, and M. Anthony, Structural risk minimization over data dependent hierarchies. Information Theory, IEEE Transactions on, vol.44, issue.5, pp.1926-1940, 1998.

, First, since H is M -bounded, we have that ?M 2 ? g f (z) ? M 2 holds almost everywhere. It follows that |g f ? E z??