Concentration Inequalities For U-processes And Applications To Learning Theory

Preference learning and learning to rank have caused great attention in machining learn-ing and information retrieval. In the view of statistical learning theory, we investigate the generalization ability of learning algorithm based on the theory of U-processes.In our dissertation we pursue two closely related research direction: concentration in-equalities for the suprema of U-processes and upper bound for learning algorithms based on empirical risk minimization. Concentration inequalities provide probability bounds on how a random variable deviates from some value (e.g. its expectation). In statistical learning theory, concentration inequalities for the suprema of empirical processes is a main math tool. Our initial motivation for studying concentration inequalities for the suprema of U-processes is the preference learning problem that can be considered as empirical risk minimization. The suprema of U-processes and empirical processes have similarities and differences, one of sim-ilarities is some functionals defined on product measurable spaces, it is naturally to think that the entropy method that is used to proof the concentration inequalities for empirical processes is also used to proof the concentration inequalities for U-processes. The differences is that U-processes has dependence structure, this barrier leads to some technical difficulties. We use decoupling principle to break these dependence structure.The main research works in this dissertation can be summarized as followings:Firstly, we proof three kinds of concentration inequalities:·concentration inequalities for U-processes with degenerate kernel,· concentration inequalities for U-processes with non-degenerate kernel,· concentration inequalities for weakly dependent random variables. we consider two kind of approach for handling complex problems involving dependent vari-ables. On the one hand, though U-processes contains dependence structure, it is still consid-ered as some functionals defined on product spaces. We combine the entropy method with the decoupling theorem to derive the first two concentration inequalities. The first is proofed by two stage and used to investigate the statistical learning. The second inequality is similar to concentration inequality for centered empirical processes. Finally, we define the generalized self-bounding functions and give a concentration inequality for generalized self-bounding functions. On the other hand, it builds on the dependency graph according to the dependen-cies random variables, we decompose dependency graph by the notion of fractional covers of graphs. To establish these bounds, we make use of the results of i.i.d and the fractional chromatic number of the dependency graph to obtain concentration for dependent structure.Secondly, we show that the pairwise loss function is closely related to concentration inequalities for U-processes, and also to the theory of Rademacher chaos processes, we study a number of problems based on empirical risk minimization for U-processes which is related to preference learning and learning to rank. We develop two approaches to this problem via peeling methods and obtain abstract excess risk bound, this framework is general and allows a user to apply it directly instead of deriving bounds in each risk minimization problem. As a result, we get the bounds of excess risk of preference learning and risk bounds of Magnitude-Preserving ranking algorithms.