Loading...

Distributed Machine Learning with Communication Constraints

Tavassolipour, Mostafa | 2019

2955 Viewed
  1. Type of Document: Ph.D. Dissertation
  2. Language: Farsi
  3. Document No: 52672 (19)
  4. University: Sharif University of Technology
  5. Department: Computer Engineering
  6. Advisor(s): Manzuri Shalmani, Mohammad Taghi; Motahari, Abolfazl
  7. Abstract:
  8. It is of fundamental importance to find algorithms obtaining optimal performance for learning of statistical models in distributed and communication limited systems. In this thesis, we aim at characterizing the best learning strategies over distributed datasets such that the communications between storing machines are minimized. We have addressed two problems in distributed setting: learning of Gaussian processes, and structure learning of Gaussian Graphical Models (GGM). The performance of the proposed methods are analyzed theoritically and verified experimentally. The experimental results show that with spending few bits the proposed distributed methods have close performance to the centralized case.To obtain an efficient scheme for learning of Gaussian processes, we first address a very basic problem: how many bits are required to estimate the innerproducts of some Gaussian vectors across distributed machines? Using information theoretic bounds, we obtain an optimal solution for the problem which is based on vector quantization. Two suboptimal and more practical schemes are also presented as substitutes for the vector quantization scheme. The optimal solution is obtained by the rate-distortion theory. We have shown that the minimum distortion is obtained when the data are compressed according to the muliplication of local covariance matrices. We have also provided several experiments to compare our distributed Gaussian process learning methods with the state-of-the-art. The experimenal results show the proposed methods outperform by consuming few bits.The structure learning of GGMs is studied for tree and non-tree sparse structures.We have presented a set of communication efficient strategies, which are theoretically proved to convey sufficient information for reliable learning of the structure. In particular, our analyses show that even if each machine sends only the signs of its local data samples to the central node, the tree structure can still be recovered with high accuracy. In the tree case, the wellknown Chow-Liu algorithm yields the maximum likelihood structure. We have proposed a distributed version of the Chow-Liu algorithm and shown it can recover the underlying graph structure with high probability. Precisely, we have shown that the probability of incorrect tree estimation decreases exponentilly by the sample size. The provided error bound is also tight in the exponent.The most popular methods for estimating sparse structure of GGM are lassobased methods. We have shown that if the signs of data are only available, then the obtained structure by lasso is correct with probability converging to one. We have also shown that for a sufficiently large sample size, the roposed method can estimate the true signs of the non-zero entries of the recision matrix. Moreover, we have proposed an uncoded method in which the local datasets are transfered without any channel coding to the receiver machine through a Gaussian channel. Then, the receiver machine estimates the structure by the received data. For this case, we have provided bounds for the error probability and the sample size. All the theoritical resuls are also examined experimentally on real and synthetic datasets
  9. Keywords:
  10. Distributed Learning ; Gaussian process ; Structural Learning ; Gaussian Graphical Model ; Information Theory ; Communication Cost

 Digital Object List

 Bookmark

...see more