In federated learning, communication cost is often a critical bottleneck to\nscale up distributed optimization algorithms to collaboratively learn a model\nfrom millions of devices with potentially unreliable or limited communication\nand heterogeneous data distributions. Two notable trends to deal with the\ncommunication overhead of federated algorithms are gradient compression and\nlocal computation with periodic communication. Despite many attempts,\ncharacterizing the relationship between these two approaches has proven\nelusive. We address this by proposing a set of algorithms with periodical\ncompressed (quantized or sparsified) communication and analyze their\nconvergence properties in both homogeneous and heterogeneous local data\ndistribution settings. For the homogeneous setting, our analysis improves\nexisting bounds by providing tighter convergence rates for both strongly convex\nand non-convex objective functions. To mitigate data heterogeneity, we\nintroduce a local gradient tracking scheme and obtain sharp convergence rates\nthat match the best-known communication complexities without compression for\nconvex, strongly convex, and nonconvex settings. We complement our theoretical\nresults and demonstrate the effectiveness of our proposed methods by several\nexperiments on real-world datasets.\n