A. Bibliography, . Alekh, J. Martin, . Wainwright, C. John et al., Distributed dual averaging in networks, Advances in Neural Information Processing Systems, pp.550-558, 2010.

B. , R. , M. Bilenko, and J. Langford, Scaling Up Machine Learning, 2011.

B. , A. , and A. Habrard, Robustness and Generalization for Metric Learning, In: Neurocomputing, vol.151, issue.1, pp.259-267, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01075370

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

A. Bellet, H. Amaury, and M. Sebban, Metric Learning, Synthesis Lectures on Artificial Intelligence and Machine Learning, vol.6893, issue.1, 2015.
DOI : 10.1109/ICDM.2011.95

URL : https://hal.archives-ouvertes.fr/hal-01121733

B. , P. , and J. Tressou, Incomplete generalized U-Statistics for food risk assessment, In: Biometrics, vol.62, issue.1, pp.66-74, 2006.
URL : https://hal.archives-ouvertes.fr/hal-01068794

P. Bianchi, On-line learning gossip algorithm in multi-agent systems with local decision rules, 2013 IEEE International Conference on Big Data, 2013.
DOI : 10.1109/BigData.2013.6691548

URL : https://hal.archives-ouvertes.fr/hal-00869498

P. Bianchi and J. Jérémie, Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization, IEEE Transactions on Automatic Control, vol.58, issue.2, pp.391-405, 2013.
DOI : 10.1109/TAC.2012.2209984

URL : https://hal.archives-ouvertes.fr/hal-00816500

B. , G. , and K. Bleakley, Statistical Inference on Graphs, Statistics & Decisions, vol.24, pp.209-232, 2006.

B. Bollobás, Modern Graph Theory, 1998.
DOI : 10.1007/978-1-4612-0619-4

B. , S. , O. Bousquet, and G. Lugosi, Theory of Classification: A Survey of Some Recent Advances, ESAIM: Probability and Statistics 9, pp.323-375, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00017923

P. Brémaud, Markov chains: Gibbs fields, Monte Carlo simulation, and queues, 1999.
DOI : 10.1007/978-1-4757-3124-8

B. M. Brown and D. G. Kildea, Reduced $U$-Statistics and the Hodges-Lehmann Estimator, The Annals of Statistics, vol.6, issue.4, pp.828-835, 1978.
DOI : 10.1214/aos/1176344256

URL : http://doi.org/10.1214/aos/1176344256

C. , Q. , Z. Guo, and Y. Ying, Generalization Bounds for Metric and Similarity Learning, 2012.

C. , S. , G. Lugosi, and N. Vayatis, Ranking and scoring using empirical risk minimization, Proceedings of COLT, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00104851

C. , S. , and S. Robbiano, Building confidence regions for the ROC surface, 2014.

C. , S. , S. Robbiano, and N. Vayatis, Ranking Data with Ordinal Labels: Optimality and Pairwise Aggregation, Machine Learning 91.1, pp.67-104, 2013.

C. , S. , and N. Vayatis, Tree-based ranking methods, IEEE Transactions on Information Theory, vol.559, pp.4316-4336, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00268068

C. , S. Gàbor, L. , and N. Vayatis, Ranking and Empirical Minimization of U-statistics, Ann. Stat, vol.36, issue.2, pp.844-874, 2008.

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

D. , A. G. Anand, D. Sarwate, and M. J. Wainwright, Geographic Gossip: Efficient Averaging for Sensor Networks, IEEE Transactions on Signal Processing, vol.563, pp.1205-1216, 2008.

D. , J. Alekh, A. Martin, and W. , Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling, IEEE Trans. Autom. Control, vol.573, pp.592-606, 2012.

F. , J. , T. Hastie, and R. Tibshirani, The Elements of Statistical Learning, 2009.

F. , D. K. , and S. V. Nagaev, Probability Ineaqualities for Sums of Independent Random Variables, pp.643-660, 1971.

G. , E. , and J. Zinn, Some limit theorems for empirical processes, The Annals of Probability 12.4, pp.929-989, 1984.

G. , W. , and R. Serfling, Convergence rates for U-statistics and related statistics, Ann. Stat, vol.1, issue.1, pp.153-160, 1973.

H. , J. A. , and B. J. Mcneil, The meaning and use of the area under a receiver operating characteristic (ROC) curve, In: Radiology, vol.143, issue.1, pp.29-36, 1982.

H. , S. M. Stephen, T. Hedetniemi, L. Arthur, and . Liestman, A survey of gossiping and broadcasting in communication networks, In: Networks 18.4, pp.319-349, 1988.

H. , D. G. , and D. J. Thompson, A generalization of sampling without replacement from a finite universe, pp.663-685, 1951.

J. , R. , S. Wang, and Y. Zhou, Regularized Distance Metric Learning: Theory and Algorithm, Advances in Neural Information Processing Systems 22, pp.862-870, 2009.

J. Björn, R. Maben, and M. Johansson, A Randomized Incremental Subgradient Method for Distributed Optimization in Networked Systems, In: SIAM J. Optimiz, vol.203, pp.1157-1170, 2010.

J. , R. , and T. Zhang, Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Advances in Neural Information Processing Systems 26, pp.315-323, 2013.

T. Kanungo, A local search approximation algorithm for k-means clustering, Computational Geometry, vol.28, pp.2-3, 2004.
DOI : 10.1016/j.comgeo.2004.03.003

URL : https://doi.org/10.1016/j.comgeo.2004.03.003

K. , S. José, and M. Moura, Distributed consensus algorithms in sensor networks with imperfect communication: Link failures and channel noise, IEEE Transactions on Signal Processing, vol.57, issue.1, pp.355-369, 2009.

R. Karp, Randomized rumor spreading, Proceedings 41st Annual Symposium on Foundations of Computer Science, pp.565-574, 2000.
DOI : 10.1109/SFCS.2000.892324

URL : http://cone.informatik.uni-freiburg.de/pubs/rumor.pdf

K. , D. Alin, D. , and J. Gehrke, Gossip-Based Computation of Aggregate Information, pp.482-491, 2003.

A. Kumar, A Binary Classification Framework for Two-Stage Multiple Kernel Learning, 2012.

L. Roux, N. , M. W. Schmidt, and F. Bach, A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets, Advances in Neural Information Processing Systems 25, pp.2672-2680, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00674995

L. , M. , and M. Talagrand, Probability in Banach Spaces, 1991.

L. , S. Angelia, and N. Nedi´c, Asynchronous gossip-based random projection algorithms over networks, IEEE Trans. Autom. Con- trol, 2015.

L. , S. Angelia, N. Nedi´c, and R. Maxim, Decentralized Online Optimization with Global Objectives and Local Communication, 2015.

L. , W. Huaiyu, D. , and Y. Zhang, Location-Aided Fast Distributed Consensus in Wireless Networks, IEEE Transactions on Information Theory, vol.5612, pp.6208-6227, 2010.

M. , H. B. , and D. R. Whitney, On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other, Annals of Mathematical Statistics, vol.18, issue.1, pp.50-60, 1947.

M. , D. , and D. Shah, Fast Distributed Algorithms for Computing Separable Functions, IEEE Trans. Inf. Theory, vol.547, pp.2997-3007, 2008.

N. Nedi´c and A. , Asynchronous broadcast-based convex optimization over a network, Automatic Control, IEEE Transactions on 56.6, pp.1337-1351, 2011.

N. , A. Asuman, and O. , Distributed subgradient methods for multi-agent optimization, IEEE Transactions on Automatic Control, vol.54, issue.1, pp.48-61, 2009.

N. Nedi´c, A. , and A. E. Ozdaglar, Distributed Subgradient Methods for Multi-Agent Optimization, IEEE Transactions on Automatic Control, vol.54, issue.1, pp.48-61, 2009.
DOI : 10.1109/TAC.2008.2009515

G. Papa, C. Stéphan, and A. Bellet, SGD Algorithms based on Incomplete U-statistics: Large-Scale Minimization of Empirical Risk, Advances in Neural Information Processing Systems 28, pp.1027-1035, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01214667

P. , K. , and J. Suykens, Gossip Algorithms for Computing U-Statistics, pp.48-53, 2009.

P. , V. De-la, and E. Giné, Decoupling: from Dependence to Independence, 1999.

R. , S. Angelia, N. Nedi´c, and V. Veeravalli, Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization, pp.516-545, 2010.

D. Shah, Gossip Algorithms, Foundations and Trends in Networking 3.1, pp.1-125, 2009.
DOI : 10.1561/1300000014

T. , Y. Tsianos, . Konstantinos, L. Sean, and R. Michael, Sampling algorithms Springer Series in Statistics Push- Sum Distributed Dual Averaging for convex optimization, 2006.

D. J. Watts, H. Steven, and . Strogatz, Collective dynamics of 'small-world'networks " . In: Nature 393, pp.440-442, 1998.

W. , E. Asuman, and O. , Distributed Alternating Direction Method of Multipliers, IEEE CDC, pp.5445-5450, 2012.

W. , K. Q. , and L. K. Saul, Distance Metric Learning for Large Margin Nearest Neighbor Classification, Journal of Machine Learning Research, vol.10, pp.207-244, 2009.