Distributed and Asynchronous Methods for Semi-supervised Learning

Konstantin Avrachenkov (1) , Vivek S. Borkar (2) , Krishnakant Saboo (2)

1 MAESTRO - Models for the performance analysis and the control of networks
2 IIT Bombay - Indian Institute of Technology Bombay

We propose two asynchronously distributed approaches for graph-based semi-supervised learning. The first approach is based on stochastic approximation, whereas the second approach is based on randomized Kaczmarz algorithm. In addition to the possibility of distributed implementation, both approaches can be naturally applied online to streaming data. We analyse both approaches theoretically and by experiments. It appears that there is no clear winner and we provide indications about cases of superiority for each approach.

Domaines: Réseaux et télécommunications [cs.NI]

Konstantin Avrachenkov, Vivek S. Borkar, Krishnakant Saboo. Distributed and Asynchronous Methods for Semi-supervised Learning. Bonato, Anthony; Graham, Fan Chung; Pralat, Pawel. Algorithms and Models for the Web Graph: 13th International Workshop, WAW 2016, Montreal, QC, Canada, December 14―15, 2016, Proceedings, 10088, Springer International Publishing, pp.34--46, 2016, Lecture Notes in Computer Science, 978-3-319-49787-7. ⟨10.1007/978-3-319-49787-7_4⟩. ⟨hal-01400117⟩