Gradient compression is a widely-established remedy to tackle the communication bottleneck in distributed training of large deep neural networks (DNNs). Under the error-feedback framework, Top-k sparsification, sometimes with k as little as 0.1% of the gradient size, enables training to the same model quality as the uncompressed case for a similar iteration count. From the optimization perspective, we find that Top-k is the communication-optimal sparsifier given a per-iteration k element budget. We argue that to further the benefits of gradient sparsification, especially for DNNs, a different perspective is necessary -- one that moves from per-iteration optimality to consider optimality for the entire training. We identify that the total error -- the sum of the compression errors for all iterations -- encapsulates sparsification throughout training.

We use the notation G= (V,E) to represent unweighted graphs, and G= (V,E,w) for weighted graphs. We use lowercase letters u,v to refer to vertices in V, and given a vertex v, we use dG(v) to refer to its degree in graph G. We use capital letters S,T to represent subsets of vertices, and given a vertex set S V, we use |S|to refer to its cardinality, S:= V \S to refer to its complement, and G[S] to refer to the subgraph of Ginduced by vertex set S. Furthermore, given two disjoint vertex sets S,T, we use wG(S,T):= P Given a graph G = (V,E), we use T to refer to a hierarchical clustering (tree) of the vertex set V, and costG(T) to refer to the cost of this clustering in graph G. Without loss of generality, we restrict our attention to just full binary hierarchical clustering trees, since the optimal tree is binary [20].

Neural Information Processing Systems http://nips.cc/

We identify that the total error -- the sum of the compression errors for all iterations -- encapsulates sparsification throughout training.