Learning with U-Statistics: Large-Scale Risk Minimization and Decentralized Algorithms

Many useful empirical statistics, such as the sample variance
and the Area Under the Curve (AUC), are computed by averaging over all
d-tuples of observations. These are known as U-statistics, and are also
used as risk measures in many machine learning problems such as ranking,
metric learning and clustering. I will first describe some contributions
on scaling up the minimization of such risk functionals to large
datasets using sampling and stochastic optimization. In a second part, I
will briefly introduce the problem of learning in a decentralized
network, where each agent holds a subset of the dataset, and present
gossip algorithms for estimation and learning with U-statistics in this
setting.