Convergence Bounds for Compressed Gradient Methods with Memory Based Error Compensation
Sarit Khirirat, Sindri Magnússon, Mikael Johansson
Abstract
The veritable scale of modern data necessitates information compression in parallel/distributed big-data optimization. Compression schemes using memory-based error compensation have displayed superior performance in practice, however, to date there are no theoretical explanations for these observed advantages. This paper provides the first theoretical support for why such compression schemes yields higher accuracy solutions in optimization. Our results cover both gradient and incremental gradient algorithms for quadratic optimization. Unlike previous works, our theoretical results explicitly quantify the accuracy gains from error compensation, especially for ill-conditioned problems. Finally, the numerical results on linear least-squares problems validate the benefit of error compensation and demonstrate tightness of our convergence guarantees.
BibTeX
@inproceedings{icassp2019_convergencebound,
title = {Convergence Bounds for Compressed Gradient Methods with Memory Based Error Compensation},
author = {Sarit Khirirat and Sindri Magnússon and Mikael Johansson},
booktitle = {ICASSP 2019},
year = {2019}
}