  This paper proposes the Doubly Compressed Momentum-assisted stochastic
gradient tracking algorithm $\texttt{DoCoM}$ for communication-efficient
decentralized optimization. The algorithm features two main ingredients to
achieve a near-optimal sample complexity while allowing for communication
compression. First, the algorithm tracks both the averaged iterate and
stochastic gradient using compressed gossiping consensus. Second, a momentum
step is incorporated for adaptive variance reduction with the local gradient
estimates. We show that $\texttt{DoCoM}$ finds a near-stationary solution at
all participating agents satisfying $\mathbb{E}[ \| \nabla f( \theta ) \|^2 ] =
\mathcal{O}( 1 / T^{2/3} )$ in $T$ iterations, where $f(\theta)$ is a smooth
(possibly non-convex) objective function. Notice that the proof is achieved via
analytically designing a new potential function that tightly tracks the
one-iteration progress of $\texttt{DoCoM}$. As a corollary, our analysis also
established the linear convergence of $\texttt{DoCoM}$ to a global optimal
solution for objective functions with the Polyak-{\L}ojasiewicz condition.
Numerical experiments demonstrate that our algorithm outperforms several
state-of-the-art algorithms in practice.
