Gradient Coding with Iterative Block Leverage Score Sampling
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911932860071936 |
|---|---|
| author | Charalambides, Neophytos Pilanci, Mert Hero, Alfred |
| author_facet | Charalambides, Neophytos Pilanci, Mert Hero, Alfred |
| contents | We generalize the leverage score sampling sketch for $\ell_2$-subspace embeddings, to accommodate sampling subsets of the transformed data, so that the sketching approach is appropriate for distributed settings. This is then used to derive an approximate coded computing approach for first-order methods; known as gradient coding, to accelerate linear regression in the presence of failures in distributed computational networks, \textit{i.e.} stragglers. We replicate the data across the distributed network, to attain the approximation guarantees through the induced sampling distribution. The significance and main contribution of this work, is that it unifies randomized numerical linear algebra with approximate coded computing, while attaining an induced $\ell_2$-subspace embedding through uniform sampling. The transition to uniform sampling is done without applying a random projection, as in the case of the subsampled randomized Hadamard transform. Furthermore, by incorporating this technique to coded computing, our scheme is an iterative sketching approach to approximately solving linear regression. We also propose weighting when sketching takes place through sampling with replacement, for further compression. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_03096 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Gradient Coding with Iterative Block Leverage Score Sampling Charalambides, Neophytos Pilanci, Mert Hero, Alfred Information Theory Distributed, Parallel, and Cluster Computing Information Retrieval Machine Learning Numerical Analysis 65B99, 65F10, 65F20, 65F45, 65F55, 68W20, 68W25, 94A20, 68P30, 68P20 G.1.2; G.1.3; G.1.6; G.3; E.4 We generalize the leverage score sampling sketch for $\ell_2$-subspace embeddings, to accommodate sampling subsets of the transformed data, so that the sketching approach is appropriate for distributed settings. This is then used to derive an approximate coded computing approach for first-order methods; known as gradient coding, to accelerate linear regression in the presence of failures in distributed computational networks, \textit{i.e.} stragglers. We replicate the data across the distributed network, to attain the approximation guarantees through the induced sampling distribution. The significance and main contribution of this work, is that it unifies randomized numerical linear algebra with approximate coded computing, while attaining an induced $\ell_2$-subspace embedding through uniform sampling. The transition to uniform sampling is done without applying a random projection, as in the case of the subsampled randomized Hadamard transform. Furthermore, by incorporating this technique to coded computing, our scheme is an iterative sketching approach to approximately solving linear regression. We also propose weighting when sketching takes place through sampling with replacement, for further compression. |
| title | Gradient Coding with Iterative Block Leverage Score Sampling |
| topic | Information Theory Distributed, Parallel, and Cluster Computing Information Retrieval Machine Learning Numerical Analysis 65B99, 65F10, 65F20, 65F45, 65F55, 68W20, 68W25, 94A20, 68P30, 68P20 G.1.2; G.1.3; G.1.6; G.3; E.4 |
| url | https://arxiv.org/abs/2308.03096 |