Byzantine-Tolerant Distributed Coordinate Descent. Data, D. & Diggavi, S. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 2724–2728, 2019. IEEE. doi abstract bibtex We study distributed coordinate descent (CD) in the master-worker architecture under adversarial attacks, where the data is partitioned (across the parameter space) and distributed among m worker nodes (t of which can be maliciously corrupt), which update some coordinates of their part of the parameter vector, in parallel and iteratively, using CD updates, with the help of the master. We propose a method based on data encoding and real error correction to combat the adversary. Our method can tolerate up to ⌈m-1/2⌉ corrupt nodes, which is information-theoretically optimal. Our design gives a trade-off between the resiliency t, the required redundancy, and the computation at master and worker nodes. For example, with constant overhead in the storage and computational complexity over that required by the plain distributed CD, we can tolerate up to m/3 corrupt nodes. We design a sparse encoding scheme, which yields low encoding complexity.
@inproceedings{data2019byzantine,
abstract = {We study distributed coordinate descent (CD) in the master-worker architecture under adversarial attacks, where the data is partitioned (across the parameter space) and distributed among m worker nodes (t of which can be maliciously corrupt), which update some coordinates of their part of the parameter vector, in parallel and iteratively, using CD updates, with the help of the master. We propose a method based on data encoding and real error correction to combat the adversary. Our method can tolerate up to ⌈m-1/2⌉ corrupt nodes, which is information-theoretically optimal. Our design gives a trade-off between the resiliency t, the required redundancy, and the computation at master and worker nodes. For example, with constant overhead in the storage and computational complexity over that required by the plain distributed CD, we can tolerate up to m/3 corrupt nodes. We design a sparse encoding scheme, which yields low encoding complexity.},
author = {Data, Deepesh and Diggavi, Suhas},
booktitle = {2019 IEEE International Symposium on Information Theory (ISIT)},
organization = {IEEE},
pages = {2724--2728},
tags = {conf,SDL,DML},
title = {Byzantine-Tolerant Distributed Coordinate Descent},
type = {4},
doi = {10.1109/ISIT.2019.8849217},
year = {2019}
}
Downloads: 0
{"_id":"nWH2Xm6nwG5HA4wwj","bibbaseid":"data-diggavi-byzantinetolerantdistributedcoordinatedescent-2019","author_short":["Data, D.","Diggavi, S."],"bibdata":{"bibtype":"inproceedings","type":"4","abstract":"We study distributed coordinate descent (CD) in the master-worker architecture under adversarial attacks, where the data is partitioned (across the parameter space) and distributed among m worker nodes (t of which can be maliciously corrupt), which update some coordinates of their part of the parameter vector, in parallel and iteratively, using CD updates, with the help of the master. We propose a method based on data encoding and real error correction to combat the adversary. Our method can tolerate up to ⌈m-1/2⌉ corrupt nodes, which is information-theoretically optimal. Our design gives a trade-off between the resiliency t, the required redundancy, and the computation at master and worker nodes. For example, with constant overhead in the storage and computational complexity over that required by the plain distributed CD, we can tolerate up to m/3 corrupt nodes. We design a sparse encoding scheme, which yields low encoding complexity.","author":[{"propositions":[],"lastnames":["Data"],"firstnames":["Deepesh"],"suffixes":[]},{"propositions":[],"lastnames":["Diggavi"],"firstnames":["Suhas"],"suffixes":[]}],"booktitle":"2019 IEEE International Symposium on Information Theory (ISIT)","organization":"IEEE","pages":"2724–2728","tags":"conf,SDL,DML","title":"Byzantine-Tolerant Distributed Coordinate Descent","doi":"10.1109/ISIT.2019.8849217","year":"2019","bibtex":"@inproceedings{data2019byzantine,\n abstract = {We study distributed coordinate descent (CD) in the master-worker architecture under adversarial attacks, where the data is partitioned (across the parameter space) and distributed among m worker nodes (t of which can be maliciously corrupt), which update some coordinates of their part of the parameter vector, in parallel and iteratively, using CD updates, with the help of the master. We propose a method based on data encoding and real error correction to combat the adversary. Our method can tolerate up to ⌈m-1/2⌉ corrupt nodes, which is information-theoretically optimal. Our design gives a trade-off between the resiliency t, the required redundancy, and the computation at master and worker nodes. For example, with constant overhead in the storage and computational complexity over that required by the plain distributed CD, we can tolerate up to m/3 corrupt nodes. We design a sparse encoding scheme, which yields low encoding complexity.},\n author = {Data, Deepesh and Diggavi, Suhas},\n booktitle = {2019 IEEE International Symposium on Information Theory (ISIT)},\n organization = {IEEE},\n pages = {2724--2728},\n tags = {conf,SDL,DML},\n title = {Byzantine-Tolerant Distributed Coordinate Descent},\n type = {4},\n doi = {10.1109/ISIT.2019.8849217},\n year = {2019}\n}\n\n","author_short":["Data, D.","Diggavi, S."],"key":"data2019byzantine","id":"data2019byzantine","bibbaseid":"data-diggavi-byzantinetolerantdistributedcoordinatedescent-2019","role":"author","urls":{},"metadata":{"authorlinks":{}},"html":""},"bibtype":"inproceedings","biburl":"https://bibbase.org/network/files/e2kjGxYgtBo8SWSbC","dataSources":["hicKnsKYNEFXC4CgH","jxCYzXXYRqw2fiEXQ","wCByFFrQMyRwfzrJ6","yuqM5ah4HMsTyDrMa","YaM87hGQiepg5qijZ","n9wmfkt5w8CPqCepg","soj2cS6PgG8NPmWGr","FaDBDiyFAJY5pL28h","ycfdiwWPzC2rE6H77"],"keywords":[],"search_terms":["byzantine","tolerant","distributed","coordinate","descent","data","diggavi"],"title":"Byzantine-Tolerant Distributed Coordinate Descent","year":2019}