text:
Zipper Codes

Zipper codes are a framework for describing spatially-coupled product-like codes. Many well-known codes, such as staircase codes and braided block codes, are subsumed into this framework. New types of codes such as tiled diagonal and delayed diagonal zipper codes are introduced along with their software simulation results. Stall patterns that can arise in iterative decoding are analyzed, giving a means of error floor estimation.

This paper provides a general overview of zipper codes, organized as follows. The structure and main ingredients of a zipper code are discussed in Sec. II. Several important code families that can be described as zipper codes are given in Sec. III. Software simulation results for a few example zipper code designs are given in Sec. IV. Finally, "stall patterns," a type of error event for zipper codes, are discussed and analyzed in Sec. V.
Throughout this paper, we will assume that all codes are defined over the binary field F 2 = {0, 1}; however, analogous formulations can be made for the non-binary case. For any positive integer q, we let [q] = {0, 1, . . . , q − 1}. The cardinality (number of elements) of a finite set A is denoted as |A|.

A. Constituent Codes, Buffer, Zipping Pair
Let C 0 , C 1 , . . . be any sequence of binary linear constituent codes indexed by i ∈ N, where the ith code has length n i and dimension k i . Denote any (fixed) information set of C i as I i ⊆ [n i ]; necessarily |I i | = k i . Codeword symbols in positions indexed by I i are called information symbols of C i , while codeword symbols in the complementary positions (indexed by [n i ]\I i ) are called parity symbols. In practice, we will usually have C i in systematic form, in which case I i = [k i ] (the first k i positions of a codeword hold information symbols and the last n i − k i positions hold parity symbols).
A buffer associated with a given sequence of constituent codes is any sequence of binary row vectors c = c 0 , c 1 , . . . such that c i ∈ F ni 2 for each i ∈ N. Thus, a buffer is a sequence of rows, with the ith row having n i positions, possibly (but not necessarily) forming a codeword of C i . For any i ∈ N and any j ∈ [n i ] the jth symbol of the ith row of c is denoted as c i,j ; this symbol is said to have position (i, j) within buffer c. For purposes of initialization (i.e., to establish suitable boundary conditions), we extend the set of buffer positions to allow for negative row indices by defining c i,j = 0 for all i < 0 and all j ∈ N. Thus if we refer to a buffer symbol with a negative row index, that symbol necessarily has value zero. When i < j we will say that row i is older than row j (or, equivalently, that row j is newer than row i).
As illustrated in Fig. 1, we will partition each row of a buffer c as follows. For each i ∈ N, let A i ⊆ I i be any The filled regions show the location of parity symbols. The two tiles connected by arrows represent the two coordinates prescribed by the interleaver map. In this example, we have φ(13, 2) = (1,12) and c 13,2 = c 1,12 = 1. Each row is a codeword of C. Rows with lower row indices correspond to "older" rows while those with higher indices are regarded as "newer." soon see, only real symbols are transmitted over the channel; each virtual symbol of a constituent codeword is a copy of a real symbol from some other constituent codeword. When C i is in systematic form, we will usually take A i = [m i ] for some m i ≤ k i , thus designating the first m i positions as virtual positions. Let denote the positions of the virtual symbols and the real symbols, respectively. We refer to (A, B) as a zipping pair. The set {c i,j : (i, j) ∈ A} is called the virtual buffer, and the set {c i,j : (i, j) ∈ B} is called the real buffer. The set B * = B ∪ {(i, j) : i ∈ {−1, −2, . . .}, j ∈ N} is an index set for an extended real buffer where negative row indices are permitted. As already noted, symbols located in rows with a negative row index have value zero.

B. Interleaver Map
An interleaver map associated with a zipping pair (A, B) is any function φ : A → B * . For each virtual position (i, j) ∈ A, the interleaver map gives a real position φ(i, j) ∈ B * from which to copy a symbol.
We will often be interested in the row index from which a real symbol is copied. To this end, we define coordinate functions φ 1 and φ 2 such that φ(i, j) = (φ 1 (i, j), φ 2 (i, j)). Thus φ 1 (i, j) returns the row index from which the virtual symbol at position (i, j) is copied. If φ 1 (i, j) < 0, then the copied symbol is necessarily zero.
Equipped with a sequence C 0 , C 1 , . . . of constituent codes, a zipping pair (A, B), and an interleaver map φ, we say that a buffer c = c 0 , c 1 , . . . forms a valid zipper codeword if 1) c i,j = c φ(i,j) for all (i, j) ∈ A, and 2) c i ∈ C i for all i ∈ N. In other words, each virtual symbol of a valid zipper codeword must be a copy of a real symbol as prescribed by the interleaver map φ, and each row of a valid zipper codeword must be a codeword of the corresponding constituent code. Fig. 1 illustrates a zipper codeword in a zipper code specified in terms of a sequence of constituent codes having fixed length n = n i = 14 and fixed dimension k = k i = 11. The constituent codes are assumed to be in systematic form, so that parity symbols fall into the last r = n − k = 3 positions in each row. The first m i positions in each row are the virtual positions, while the last n − m i positions are the real positions. Note that m i is permitted to vary from row to row. As illustrated, the interleaver map φ determines the position at which to look up the value of a virtual symbol.
It is clear that the interleaver map determines the degree of coupling among the various constituent codes. We will usually focus on interleaver maps that are periodic and causal.
To support a ν-periodic interleaver map, we will require that the zipping pair (A, B) is also ν-periodic in the sense that n ν+i = n i , and A ν+i = A i for all i ∈ N. Most often we will then also have C ν+i = C i for all i ∈ N. Definition 2. An interleaver map φ is said to be causal if φ 1 (i, j) ≤ i for all (i, j) ∈ A and strictly causal if the inequality is strict.
In other words, under a causal interleaver map, virtual symbols are never copied from later rows.
Some important classes of zipper codes (such as staircase codes) have the property that each real symbol is copied exactly once into some virtual position, i.e., the inverse image φ −1 (i, j) of every real position (i, j) ∈ B under mapping by φ is a singleton set {(i , j )} for some (i , j ) ∈ A. In this situation we refer to the interleaver map as being bijective.

C. Encoding Zipper Codes
Recall that I i ⊆ [n i ] denotes an information set with |I i | = k i for the constituent code C i of length n i and dimension k i , and that A i ⊆ I i is an index set for the virtual positions of the ith buffer row c i . To encode c i , we assume that all rows c j with j < i have already been encoded. This will be true even for c 0 , since previous rows are then all-zero by assumption. Under the assumption of a causal interleaver map, the encoding of zipper codes is easily accomplished by the following procedure: 1) Fill in the positions indexed by B i ∩ I i with message symbols. 2) Fill in the virtual symbols by duplicating symbols from the positions prescribed by the interleaver map, i.e., for by assumption, c φ(i,j) is a symbol from a row already encoded, or a symbol from the current row which was input in the first step.) 3) Complete the row by filling in the parity symbols in positions indexed by [n i ] \ I i using an appropriate encoder for C i , thereby fulfilling the condition that c i ∈ C i . In the zipper code of Fig. 1, for example, the shaded tiles in row i are filled with symbols drawn from previous rows, the unshaded tiles correspond to message symbols, and the filled tiles correspond to parity symbols computed using the encoder for C i .

D. Code Rate
We will always assume that only the symbols in the real buffer, i.e., in positions indexed by B, are transmitted over the channel, in some well-defined order from oldest to newest. The symbols in the virtual buffer, which are needed for purposes of encoding and decoding, are not transmitted. As usual, let m i = |A i | denote the number of virtual symbols in row i. Under the assumption of that only the real buffer is sent, the rate of a zipper code is given as where, assuming the limits exist, For example, staircase codes with staircase block size m × m uses a fixed constituent code of length 2m and dimension k. Thus, n = 2m, k = k, and m = m, thereby achieving a rate R = k m − 1 (assuming k m > 1).

E. Decoding
Suppose that we transmit real symbols in positions indexed by B. At the receiver we can form a buffer c by filling in the real positions from symbols received at the output of the channel, and filling in virtual positions by copying real received symbols as prescribed by the interleaver map φ. We generally assume a hard-decision channel, i.e., we assume that the channel outputs are elements of F 2 , though it is possible to consider more general situations with various amounts of reliability information in the form of erasures or log-likelihood ratios. The received buffer c is not necessarily a zipper codeword, since, due to channel noise or other impairments causing detection errors, the rows aren't necessarily codewords of the corresponding constituent codes. Ideally, the aim of the decoder would be to recover a valid zipper codeword while making as few changes to c as possible. However, such optimal minimum Hamming distance decoding is often too complicated to implement, so in practice some form of iterative decoding is used, making changes to the rows one at a time using the constraints imposed only by the constituent code that constrains that row, and usually revisiting each row a number of times.
Decoding is typically performed within a sliding window of M consecutive rows c i−M +1 , c i−M +2 , . . . , c i from the received buffer. Many of the virtual symbols in these rows will, however, be copies of symbols from outside the sliding window (which, ideally, will have been corrected by previous decoding iterations). The decoder operates by decoding the rows within the decoding window. When the decoder performs correction operations (flipping the value of one or more bits in a row), all copies of the affected bits within the decoding window (as determined by the interleaver map) will also need to be flipped. After a number of iterations have been performed, the sliding window can be advanced (by one or, more usually, several rows), and the corrected information symbols leaving the window can be delivered as the decoder output. Numerous variations of this basic scheme are possible.
In one round of so-called exhaustive decoding, every row in the decoding window is visited (exactly once) by the corresponding constituent decoder. Each bit is decoded (in a round) as many times as it appears in the window. Exhaustive decoding can be performed in serial fashion (one row at a time), or in parallel (usually under the constraint that decoders operating in parallel don't operate on the same bits).
In one round of so-called pipelined decoding, only a subset of the rows in the decoding window (every Lth row, say, for some parameter L) are visited by constituent decoders. This method may be faster than exhaustive decoding, but, depending on the interleaver map, some bits may not be visited by a decoder at all. Thus, pipelined decoding is suitable only for certain types of interleaver maps that ensure that as many bits as possible are visited by the constituent decoders. Similar to exhaustive decoding, pipelined decoding can be done in series or parallel.
Under both of these decoding methodologies, decoding can be performed in multiple rounds, until no more errors can be corrected or until some maximum number of allowed decoding rounds is reached.
Additional strategies can also be applied to these decoding procedures.
In chunk decoding, rather than advancing the sliding window one row at a time, the window is advanced only after a specified number of new rows, called a chunk, is received.
In decoding with fresh/stale flags, a "fresh/stale" status indicator is maintained for each buffer row. The indicator is set to "fresh" whenever a change is made to the row (for example, if the row is newly arrived, or a bit has been flipped in that row due to a correction elsewhere); otherwise, after a decoding it is set to "stale". In each iteration, decoders can skip over stale rows (since nothing has changed in that row since the previous iteration, and therefore the row has either been corrected or has been determined to be uncorrectable).
In decoding with periodic truncation, a fraction of the message positions are reserved to be set to known values (for example, zero). The known symbols do not need to be transmitted, as they can be filled in perfectly at the receiver. One approach would be to alternate between sending data in, say, J consecutive rows, and not sending data (or, more precisely, sending only parity symbols) in τ consecutive rows. We call J and τ the transmission length and truncation length, respectively. This method is a generalization of staircase code "termination" discussed in [26], and is a form of code "shortening" as defined in coding theory. The shortened code will have a lower code rate than the zipper code from which it is derived.
In dynamic decoding, the decoder is implemented with a number of constituent decoders that can operate in parallel and that can be assigned dynamically (according to a scheduling module) to the rows to be decoded. Equipping a decoding engine with the flexibility to assign decoders to the rows where work needs to be done results in increased hardware utilization (reduced computational idling). Dynamic decoding can achieve similar decoding performance with fewer computational resources than without dynamic decoding [27].

III. EXAMPLES
This section gives some examples of related spatiallycoupled codes that can be described as zipper codes. Due to space constraints, only a few codes will be described in detail, but other codes that can be described as zipper codes include those in [5]- [9].

A. Staircase Codes
Staircase codes [3] are characterized by having an infinite sequence of matrices of size m × m: S 0 , S 1 , . . . such that, for each i ∈ N, every row of S T i S i+1 is a codeword of a systematic constituent code C of length 2m, where S T i is the transpose of S i . The initial block S 0 is all zero (and not transmitted). The codes are so named because the sequence of matrices form a staircase-like pattern when arranged as shown in Fig. 2 (left), in which each row and each column must be a codeword of C, and where the dark-filled regions hold parity symbols.
Staircase codes correspond to zipper codes with a fixed (systematic) constituent code C of length 2m, and a zipping pair with A i = [m] for all i ∈ N, i.e., the virtual positions comprise the first m positions in each row. The interleaver map φ is m-periodic and defined to perform a transposition operation, i.e., The resulting buffer then forms the pattern shown in Fig. 2 (right).

B. Braided Block Codes
Braided block codes [4] are a type of convolutional code whose codewords can be represented as a subarray of an infinite two dimensional array constrained by two interacting constituent codes, one providing constraints on rows and the other providing constraints on columns. An example of a codeword from a rate 1/7 tightly braided block code from [4] is shown in Fig. 3 (left). In this example, each row and each column in the diagram must form a codeword of the binary This tightly braided block code corresponds to a zipper code with fixed (7, 4) Hamming constituent code. The zipping pair is defined so that A i = [3] when i is even, and A i = [4] when i is odd. The interleaver map is given as where the last case corresponds to copying an information symbol from the row above. In this example, only evennumbered rows contain an information symbol. The name "zipper code" derives from the buffer pattern formed in this example.

C. Diagonal Zipper Codes
In this subsection, we introduce two interleaver maps that couple the bits of a zipper code in a regular ("hardwarefriendly") fashion. These interleaver maps generalize those of staircase codes.
1) Tiled Diagonal Zipper Codes: Tiled diagonal zipper codes are a generalization of staircase codes that are defined defined in terms of w × w "tiles" of symbols, a fixed (systematic) constituent code C with length 2Lw, and a zipping pair with A i = [Lw] (so that virtual positions comprise the first Lw positions in each buffer row), where the parameter L is a positive integer. The interleaver map is defined so that each w × w tile within the virtual buffer is the transpose of some w × w tile within the real buffer, as illustrated in Fig. 4. Fig. 4. Tiled diagonal zipper code with L = 3, tile size w×w, and interleaver map as described in (2).
To specify the interleaver map precisely, we must introduce a coordinate system for tiles. For a buffer c, for any s ∈ [2L] and for any q ∈ N, let The w ×w matrix T q,s is a tile located within the buffer whose top left entry has position (wq, ws). When s < L, such a tile comprises only virtual symbols, and therefore it is called a virtual tile; otherwise it is a real tile. For fixed q, the set of tiles {T q,s : s ∈ [2L]} are said to form the qth tile row.
For any s ∈ [L] (indexing a virtual tile), we would like to have T q,s = T T q−s−1,L+s . Thus the first virtual tile in tile row q is the transpose of the first real tile located one tile row earlier, the second virtual tile in tile row q is the transpose of the second real tile located two tile rows earlier, and so on. The interleaver map that accomplishes this task is given as φ(wq + i, ws + j) = (w(q − s − 1) + j, w(L + s) + i). (2) Fig. 4 shows an example of a tiled diagonal zipper code with L = 3.
When w = 1 (the case of 1 × 1 tiles) tiled diagonal zipper codes recover the interleaving pattern of the continuously interleaved BCH (CI-BCH) codes described in [6]. When L = 1, tiled diagonal zipper codes are staircase codes.
2) Delayed Diagonal Zipper Codes: Delayed diagonal zipper codes are variants of tiled diagonal zipper codes with w = 1 and an added "delay" in the interleaver map. Specifically, the interleaver map is given by where the positive integer δ is the delay parameter. When δ = 1, the interleaver map is identical to the interleaver map (2) with w = 1. Fig. 5 illustrates the buffer of a delayed diagonal zipper code with m = 8. As will show in Section V, the introduction of delay in the interleaver map reduces the multiplicity of minimal stall patterns. Delayed diagonal zipper codes can be generalized to the case of w×w tiles, with w > 1, in the obvious way.

IV. DESIGN EXAMPLES
In this section, we present software simulation results for several tiled diagonal and delayed diagonal zipper code design examples.

A. Simulation Setup
We simulate transmission of zipper codewords over a binary symmetric channel with crossover probability p. This corresponds to binary antipodal signalling over an additive white Gaussian noise channel (Bi-AWGN) with hard-decision detection, but it may also model other communications scenarios that give rise to independent and symmetrically distributed bit errors. The Shannon limit at rate R for such a channel is the largest crossover probability p for which it is theoretically possible to communicate at rate R (bit/channel use) with arbitrarily small probability of error. For the Bi-AWGN, this value of p is achieved at some particular signal-to-noise ratio (SNR). A code of finite length will achieve sufficiently small error probability only at some crossover probability smaller than the Shannon limit, corresponding to a larger Bi-AWGN SNR. The "gap to the Shannon limit" is then defined as the difference (in decibels) between the Bi-AWGN SNR corresponding to the Shannon limit and the Bi-AWGN SNR at which the code achieves sufficiently small error probability.
By "sufficiently small error probability" we mean a postcorrection (post-FEC) bit error rate (BER) of 10 −15 or smaller. As we cannot reliably measure such low error rates in any reasonable amount of time using software simulations, we use a least-squares fit linear extrapolation (on the log-log scale) of our measured error rates, in order to estimate the BSC crossover probability p * at which the post-FEC BER achieves 10 −15 .
In all of our design examples, we use shortened t-errorcorrecting (n, k) BCH constituent codes, where n = 2m. We made no attempt to optimize the positions at which the code is shortened. The virtual buffer and the real buffer both have width m. We use a causal, periodic, bijective interleaver map that implements a diagonal or delayed diagonal zipper code.
Decoding is performed using exhaustive decoding, with at most five rounds per window of size M rows (thus containing M m real symbols). We use chunk decoding with chunk size m, fresh/stale flags, and periodic truncation with transmission length J = 995m and τ = 5m.

B. Varying Decoding Window Sizes
We simulated a rate 0.97 tiled diagonal zipper code with w = 1 and m = 1200, (corresponding to a CI-BCH code [6]) having a (2400, 2364, t = 3) shortened BCH constituent code, over varying decoding window sizes. As shown in Fig. 6, we observe an improvement in the decoding performance as well as disappearing error flare as we increase the decoding window sizes. This is due to the fact that larger decoding windows provide each symbol with a larger number of decoding rounds. However, as expected, we see a diminishing return as the window size increases, with only slight improvement when increasing the decoding window size from 4m 2 = 5.76 Mb to 5m 2 = 7.20 Mb. Simulation results for a variety of different tiled diagonal zipper codes indicate that choosing the window size near 5m 2 gives nearly best possible decoding performance.

C. Different Code Rates
As shown in Fig. 7, we simulated the decoding of tiled diagonal zipper codes with tile size w = 1 having different code rates, as summarized in Table I. The decoding window size was set to 5m 2 in all cases. We see that the gap to the Shannon limit decreases as the rate increases, which is consistent with the theoretical analysis of [12].

D. Tiled Diagonal and Delayed Diagonal Zipper Codes
We simulated rate 0.967 codes with m = 1000, based on a (2000, 1967, t = 3) shortened BCH constituent code, with 5 Mb decoding window size. Various tiled and delayed diagonal zipper codes having a variety of tile sizes w and delay parameter δ, as summarized in Table II, were simulated. Performance curves for the tiled diagonal codes are shown in Fig. 8 and those for the delayed diagonal codes are shown in Fig. 9.
In both cases, increasing w or δ helps improve the decoding with an improvement to the gap to the Shannon limit of 0.028 ∼ 0.039 dB when compared to the δ = w = 1 case. A stall pattern analysis for tiled diagonal and delayed diagonal zipper codes, which may provide theoretical justification for these performance improvements, is given in Sec. V.

E. Performance versus Complexity
Let us define the performance of a zipper code as its gap to the Shannon limit at 10 −15 output bit error rate, and its complexity as the decoding radius t of its constituent code. (A more appropriate complexity measure might be t 2 , as it is known that the power consumption of a Berlekamp-Masseybased BCH decoder circuits grows as O(t 2 ) [35].) Fig. 10   performance versus complexity for various rate 0.96 diagonal zipper codes. As expected, the gap to the Shannon limit is reduced by increasing the complexity of the constituent code, but with diminishing returns.

V. STALL PATTERN ANALYSIS
This section will describe how error events in zipper decoders are characterized via error and stall patterns. For simplicity, throughout this section we will be focusing on zipper codes whose interleaver maps are bijective.

A. Graph Representation of Zipper Codes
Due to the spatially-coupled structure of zipper codes, it can be helpful to describe them as codes defined on graphs. Following the notation of Sec. II, we consider a zipper code corresponding to constituent code sequence C 0 , C 1 , . . ., with respective information sets I 0 , I 1 , . . .. For each i ∈ N, the virtual symbols in the ith row of a buffer are indexed by the set A i ⊆ I i . Fix a bijective interleaver map φ = (φ 1 , φ 2 ). Let be the set of row indices from which the virtual symbols in row i are copied (excluding any negative row indices).
Define a graph G = (V, E) whose vertex set V = N is the set of natural numbers, and whose edge set The vertices then correspond to constituent codes, with an edge joining two vertices if the corresponding codes have a symbol in common. Parallel edges are permitted, thus we interpret the edge set as a multiset (a set in which elements may have multiplicity greater than one). The number of edges between two vertices is then equal to the number of symbols that the corresponding codes have in common. Allowing for parallel edges, the degree of vertex i is equal to n i , the blocklength of C i , unless some virtual symbols in row i are copied from rows with negative row index, in which case the corresponding edges are missing. Vertices m, m + 1, m + 2, . . . therefore have degree n = 2m. The graph of a tiled diagonal zipper code with m = 4, w = 1 is shown in Fig. 11.
Graph representations for zipper codes in which symbols are copied more than once (i.e., when the interleaver map is non-bijective) can be defined by appealing to hypergraphs (in which hyperedges comprise more than two vertices), to a bipartite representation such as a factor graph, or by introducing additional constituent repetition-code constraints. We will not pursue such representations in this paper.

B. Error and Stall Patterns
Recall that B is a set containing the positions of all real symbols in a buffer. An error pattern S ⊆ B is any nonempty subset of B containing the positions of erroneous symbols in the real part of a received buffer. For any error pattern S, we define to be the complete set of positions of errors and their duplicates in the virtual set, and we define π(S * ) = {i : (i, j) ∈ S * } to be the set of affected rows.
For simplicity, throughout this section we assume that the constituent code is identical for all rows, i.e., C i = C with decoding radius t i = t for all i ∈ N. In addition, we assume that we use a genie-aided, miscorrection-free constituent decoder. Such a decoder is able to correct up to t errors in a row, but always fails to decode (never miscorrecting) when the number of errors in a row exceeds t. We assume that this genie-aided decoder visits rows in a decoding window as many times as is needed, reducing the error pattern size until no further correction is possible. Should some errors remain after this decoding procedure, we call the remaining errors a stall pattern. In a stall pattern, we must have at least t + 1 errors in every remaining affected row.
We will consider only strictly causal interleaver maps that induce at most one shared symbol between any two distinct rows of a zipper code. This means that the resulting graph is simple, i.e., it contains no parallel edges or self-loops. Each edge of a such a simple graph corresponds to one codeword symbol. We refer to such an interleaver map as scattering.

C. Decoding on a Graph
Assuming a scattering interleaver map, an error pattern S can be represented as a subgraph of the graph representing the zipper code. If the zipper code has graph representation G = (V, E), the graph representation of S is G S = (V S , E S ), where V S = π(S * ) ⊆ V (i.e., the vertex set of S contains vertices corresponding to the rows affected by S) and E S = {{i, j} : (i, k) ∈ S, j ∈ φ −1 1 (i, k)} (i.e., the edges in E s correspond to symbols in error). From this construction, the number of edges in G S is exactly the cardinality of S. We call |S| = |E S | the size of the error pattern S.
Suppose that the constituent code C can correct up to t errors. The action of the genie-aided decoder can then be described as an edge-peeling process in the error pattern graph G S = (V S , E S ): 2) Repeat step 1 until either the graph is empty or all remaining vertices have degree t + 1 or higher. This procedure will terminate either in an empty graph (successful decoding), or in a (t + 1)-core of G S -the largest induced subgraph of G S with the property that all vertices have degree at least t + 1. Sometimes, though not always, the (t + 1)-core will form a (t + 2)-clique, i.e., a subgraph of G S comprising t + 2 vertices all of which are neighbours (a complete subgraph). Such a pattern is uncorrectable by the genie-aided decoder. More generally, we call G S a stall pattern if each vertex in G S has degree at least t + 1, making it uncorrectable.
The following example illustrates error and stall patterns in both array and graph representations. Example 2. Consider a zipper code with a constituent code C capable of correcting t = 2 errors. Suppose that we receive an error pattern with seven errors as shown in Figure 12. Since rows 1, 3, 6, and 8 have at least 3 errors each, we cannot correct them. However, we can still correct row 4, which has only one error. Thus we will remove the error from row 4 and its corresponding entry in row 6, or equivalently, we remove vertex 4 and its incident edges. However, the remaining errors cannot be corrected and so those errors form a stall pattern. The 4-clique formed by vertices 1, 3, 6, and 8 is a stall pattern and it is also the 3-core of the error pattern graph from which we started.

D. Properties of Stall Patterns of Zipper Codes
The following theorem bounds the size of a stall pattern in a zipper code with a bijective and scattering interleaver map. Theorem 1. A stall pattern S for a zipper code with a terror-correcting constituent code and having a bijective and scattering interleaver map satisfies |S| ≥ 1 2 (t + 1)(t + 2). Proof: Let G S = (V S , E S ) be the graph representation of stall pattern S, and let v be any vertex in V S . Then, since Hence, there must be at least deg(v) + 1 ≥ t + 2 vertices in G S with each vertex having degree t + 1 or higher. By the handshaking lemma of graph theory, we have |S| = |E S | ≥ (t+1)(t+2) 2 .
It is worth noting that 1 2 (t+1)(t+2) is precisely the number of edges of a complete graph with t + 2 vertices. In fact, we will now show that the existence of a (t + 2)-clique in the graph representation of the zipper code is a necessary and sufficient condition for the existence of a stall pattern of size 1 2 (t + 1)(t + 2). Proposition 1. Let G = (V, E) be the graph representation of a zipper code with a t-error-correcting constituent code and a bijective and scattering interleaver map. Then the code has a stall pattern S of size 1 2 (t + 1)(t + 2) if and only if G contains a (t + 2)-clique.
Proof: (⇐) Every (t + 2)-clique corresponds to a stall pattern of size 1 2 (t + 1)(t + 2). (⇒) Suppose by way of contradiction that a stall pattern S of size 1 2 (t + 1)(t + 2) has a graph G S with more than t + 2 vertices. The average degree of the vertices is then less than 2|S|/(t + 2) = t + 1, which implies implies that V S contains at least one vertex of degree t or lower, contradicting the fact that S is a stall pattern. On the other hand, if G S contains fewer than t + 2 vertices, then there exists a vertex in V S with degree greater than t + 1, which is impossible in a simple graph.
An example of an interleaver map that yields a stall pattern of size 1 2 (t + 1)(t + 2) is the tiled diagonal zipper code with tile size 1 (or delayed diagonal with delay 1). Fig. 13 shows an example of a tiled diagonal zipper code with w = 1, m = 3, t = 2.
Theorem 1 can be generalized to strictly causal nonscattering interleaver maps that allow constituent codes to have up to b bits in common, so that the resulting graph representation has up to b parallel edges connecting any two vertices.
Theorem 2. For a zipper code with t-error-correcting constituent code having a strictly causal interleaver map that allows up to b parallel edges between any pair of vertices in its graph, the number of errors in a stall pattern is at least Proof: Any vertex in a stall pattern graph must have at least (t + 1)/b neighbours. The result then follows from the same argument as in the proof of Theorem 1.

E. Error Floor Approximation
The presence of stall patterns creates so-called "error floors" in the performance curves of zipper codes. We may approximate the location of the error floor using a union bound technique similar that used in [3]. We consider a decoding window of size M × m, and denote the set of all stall patterns in the decoding window to be S. We determine the error floor estimate by enumeration of S, evaluating (an upper bound on) the probability that the particular error pattern arises at the output of a binary symmetric channel with crossover probability p. This then gives Suppose that we could determine exactly the sizes of stall patterns that can occur in a decoding window. We could then rewrite (3) as where L denotes the set of all stall-pattern sizes that can occur in the decoding window of size M m and N denotes the number of occurrences of stall patterns of size . Note that since we only consider stall patterns that can fit in the decoding window, we have ≤ M m.
The possible sizes and the number of occurrences of stall patterns of certain size depend on the interleaver map. For example, it is possible to construct stall patterns of size 1 2 (t + 1)(t+2) in tiled diagonal zipper codes with tile size 1, but not in staircase codes, whose smallest stall pattern size is (t + 1) 2 [3], [36].
Given a decoding window, a set L of possible stall pattern sizes that can fit in the window, and crossover probability p, we call the stall patterns of size * ∈ L to be dominant if N * p * ≥ N p for all ∈ L. In general, the minimum-sized stall patterns may not be dominant since it is possible that the multiplicity of larger stall patterns causes a dominant N p term. However, for sufficiently small p, we can assume that stall patterns of minimum size are dominant. The error floor can be then further approximated as the contribution of just the minimum-sized stall patterns, i.e., the right hand side of (4) is approximately N * p * , where * = min L.

F. Eliminating Small-Sized Stall Patterns of Diagonal Zipper Codes
We will now describe a few strategies to eliminate stall patterns of size 1 2 (t + 1)(t + 2) in tiled and delayed diagonal zipper codes. 1) Tiled Diagonal: Our first observation is that we can reduce the multiplicity stall patterns of size 1 2 (t + 1)(t + 2) by increasing the tile size. To see this, we will first count the occurrences of stall patterns of size 1 2 (t+1)(t+2). Denote the tile size as w and assume that m = wL, M = wK (K > L), and L ≥ t + 1. In order to construct a stall pattern of size 1 2 (t + 1)(t + 2), we first pick t + 1 tiles from the same row. We then select a row index at which to place the errors. For each of the t + 1 tiles, pick one column index at which to place an error. Those errors will correspond to errors in t + 1 other rows. The positions of the remaining 1 2 t(t + 1) errors in those rows are then forced. Thus, the number of stall patterns of size 1 2 (t + 1)(t + 2) is given by Having larger tile size will make the values for K and L lower assuming that the decoding window size is fixed. This will in turn reduce the multiplicity of stall patterns of size 1 2 (t + 1)(t + 2) given by (5). Furthermore once L ≤ t, it is impossible to form a stall pattern of size 1 2 (t + 1)(t + 2). 2) Delayed Diagonal: In delayed diagonal zipper codes, the occurrences and size of the minimum-sized stall patterns depends on δ. In particular, we will show that having larger delay reduces the multiplicity of stall patterns of size 1 2 (t + 1)(t + 2).
Proposition 2. For a delayed diagonal zipper code with terror-correcting constituent code and delay parameter δ, there exists a stall pattern of size 1 2 (t + 1)(t + 2) if and only if δ ≤ m−1 t . Proof: Without loss of generality, let the first affected row index of the stall pattern be zero. (⇐) We claim that we can form a stall pattern of size 1 2 (t + 1)(t + 2) whose set of row indices is given by I = {0, δ, 2δ, . . . , (t + 1)δ}. To see this, first observe that (t + 1)δ = tδ + δ ≤ m + δ − 1. The neighbours of row i in the full zipper code graph are then indexed by Thus, i + (t + 1)δ ≤ max(N (i)) and max{0, i − (t + 1)δ} ≥ min(N (i)), so I ⊆ N (i) for all i ∈ I. It follows that the rows in I are connected with each other and so it is possible to form a (t + 2)-clique from I. (⇒) Let I = {0, i 1 , . . . , i t+1 } with 0 < i i < . . . < i t+1 be the row indices of a stall pattern of size 1 2 (t + 1)(t + 2). Then it must be true that . . . i t+1 ≥ i t + δ ≥ (t + 1)δ.
In a decoding window with M rows, the number of possible combinations is therefore at most M m − tδ + t t + 1 .
Example 3. Figure 14 shows the number of stall patterns of size 1 2 (t + 1)(t + 2) involving the first row of the decoding window in delayed diagonal zipper codes for m = 1000 and t = 3, 4, 5. Observe that when δ = 1 and t = 3, there are 1000 4 ≈ 4.14 × 10 10 possible configurations involving the first row. However, there is only one possible configuration for δ = 333 and stall patterns of size 1 2 (t + 1)(t + 2) do not exist for δ ≥ 334.

VI. CONCLUSIONS
Zipper codes provide a convenient framework for describing a wide variety of product-like spatially-coupled codes. Such codes are of interest in high-throughput communication systems because they can be decoded iteratively using lowcomplexity power-efficient constituent decoders while achieving a gap to the Shannon limit on the binary symmetric channel of 0.5 dB or less at high code rates. We have introduced tiled diagonal and delayed diagonal interleaver maps that couple the constituent codes in regular (hardware-friendly) patterns. These interleaver maps provide flexibility in trading off decoding window size and code performance. A combinatorial analysis of stall patterns that arise with such interleaver maps shows that increasing tile size or delay can indeed have a beneficial effect on reducing the error floor of the code.
Further research on zipper codes is needed to address the design of interleaver maps that give rise to codes with large minimum Hamming distance or large dominant stall-pattern size. Tradeoffs between code performance and decoding latency should be better characterized. Can soft-decision (or soft-aided) decoding methods be introduced without excessive increase in decoding complexity and decoder power consumption? No doubt many further interesting questions can be formulated.


An Information-Theoretic Approach to Transferability in Task Transfer Learning

Task transfer learning is a popular technique in image processing applications that uses pre-trained models to reduce the supervision cost of related tasks. An important question is to determine task transferability, i.e. given a common input domain, estimating to what extent representations learned from a source task can help in learning a target task. Typically, transferability is either measured experimentally or inferred through task relatedness, which is often defined without a clear operational meaning. In this paper, we present a novel metric, H-score, an easily-computable evaluation function that estimates the performance of transferred representations from one task to another in classification problems using statistical and information theoretic principles. Experiments on real image data show that our metric is not only consistent with the empirical transferability measurement, but also useful to practitioners in applications such as source model selection and task transfer curriculum learning.

Introduction
Transfer learning is a learning paradigm that exploits the relatedness between different learning tasks in order to gain certain benefits, e.g. reducing the demand for supervision ([1]). In task transfer learning, we assume that the input domain of the different tasks are the same. Then for a target task T T , instead of learning a model from scratch, we can initialize the parameters from a previously trained model for some related source task T S (Figure 1). For example, deep convolutional neural networks trained for the ImageNet classification task have been used as the source network in transfer learning for target tasks with fewer labeled data [2], such as medical image analysis [3] and structural damage recognition in buildings [4]. An imperative question in task transfer learning is transferability, i.e. when a transfer may work and to what extent. Given a metric capable of efficiently and accurately measuring transferability across arbitrary tasks, the problem of task transfer learning, to a large extent, is simplified to search procedures over potential transfer sources and targets as quantified by the metric. Traditionally, transferability is measured purely empirically using model loss or accuracy on the validation set ([5, 6, 7]). There have been theoretical studies that focus on task relatedness ([8, 9, 10, 11]). However, they either cannot be computed explicitly from data or do not directly explain task transfer performance. In this study, we aim to estimate transferability analytically, directly from the training data.
We quantify the transferability of feature representations across tasks via an approach grounded in statistics and information theory. The key idea of our method is to show that the expected log-loss of using a feature of the input data to predict the label of a given task under the probabilistic model can be characterized by an analytically expression, which we refer as the H-score of the feature. H-score is particularly useful to quantify feature transferability among tasks. Using this idea, we define task transferability as the normalized H-score of the optimal source task feature with respect to the target task.
As we demonstrate in this paper, the advantage of our transferability metric is threefold. (i) it is theoretically driven and has a strong operational meaning rooted in statistics and information theory; (ii) it can be computed directly and efficiently from the input data, with fewer samples than those needed for empirical learning; (iii) it can be shown to be strongly consistent with empirical transferability measurements.

Measuring Feature Effectiveness
Let X and Y denote the input and output space respectively. Denote the transferred feature representation by f : X → R k .
For a classification task, let h f : X × Y → [0, 1] |Y| be a predictor function with the log-loss function L(f (x), y) for a given (x, y) sample. The traditional machine learning approach uses stochastic gradient descent to minimize L(h) = E X,Y [L(f (x), y)]. We will show that the optimal log loss when f is given can be characterized analytically using concepts in information theory and statistics.
Definition 1. The Divergence Transition Matrix (DTM) of discrete random variables X and Y is a |Y| by |X | matrixB with entriesB y,x = Using concepts in Euclidean information geometry, it is shown in [12] that under a local assumption, for a given feature dimension k, (1) reveals a close connection between the optimal log-loss and the modal decomposition ofB. In consequence, it is reasonable to measure the classification performance with B − ΨΦ T 2 F given f (X). i.e. Since Φ is fixed, we can find the optimal Ψ , Ψ * by taking the derivative of the objective function with respect to Ψ: (2) Substituting (2) in the Objective of (1), we can derive the following close-form solution for the log loss: (3) The first term in (3) does not depend on f (X), therefore it is sufficient to use the second term to estimate classification performance with transferred feature f . We can further rewrite ||BΦ(Φ T Φ) − 1 2 || 2 F as follows and denote it as the H-score.
Definition 2. Given data matrix X ∈ R m×d and label Y , let f (X) be a k-dim, zero-mean feature function. The H-Score of f with respect to a task with joint probability P Y X is: The derivation of (4) can be found in Section 1 of the Supplementary Material 1 . This formulation can be intuitively interpreted from a nearest neighbor perspective. i.e. a high H-score implies the inter-class variance cov(E P X|Y [f (X)|Y ]) of f is large, while feature redundancy tr(cov(f (X))) is small. Comparing to finding the optimal log-loss through gradient descent, H-score can be computed analytically and only requires estimating the conditional expectation E[f (X)|Y ] from sample data. Moreover, H(f ) has an operational meaning that characterizes the asymptotic error probability of using f (X) to estimate Y in the hypothesis testing context. (See Section 2 in the Supplementary Material for details).
The upper bound of H(f ) is obvious from its first definition: We call features that achieve this bound the minimum error probability features for a given task.

Transferability
Next, we apply H-score to efficiently measure the effectiveness of task transfer learning. We will use subscripts S and T to distinguish variables for the source and the target tasks.
Definition 3 (Task transferability). Given source task T S , target task T T and pre-trained source feature f S (x), the transfer- is the minimum error probability feature of the target task.
This definition implies 0 ≤ T(S, T ) ≤ 1. With a known f , computing H-score from m sample data only takes O(mk 2 ) time, where k is the dimension of f (x) for k < m. The majority of the computation time is spent on computing the sample covariance matrix cov(f (X)).
The remaining question is how to obtain H T (f Topt ) efficiently. This question has been addressed in [13], which shows that ||B T || 2 ], where f and g are the solutions of the HGR-Maximum Correlation problem.
ρ(X; Y ) = sup Eq. (6) can be solved efficiently using the Alternating Conditional Expectation (ACE) algorithm [14] for discrete X , or using the neural network approach based on Generalized Maximal HGR Correlation [15] for a generic X . The sample complexity of ACE is only 1/k of the complexity of estimating P Y X directly [16]. This result also applies to the Generalized HGR problem due to their theoretical equivalence. A common technique in task transfer learning is finetuning, which adds before the target classifier additional free layers, whose parameters are optimized with respect to the target label. For the operational meaning of transferability to hold exactly, we require the fine tuning layers consist of only linear transformations. Nevertheless, later we will demonstrate empirically that this transferability metric can still be used for comparing the relative task transferability with fine-tuning. In many cases though, the computation of H T (f opt ) can even be skipped entirely, such as the problem below: Definition 4 (Source task selection). Given N source tasks T S1 , . . . , T S N with labels Y S1 , . . . , Y S N and a target task T T with label Y T . Let f S1 , . . . , f S N be optimal representations for the source tasks. Find the source task T Si that maximizes the testing accuracy of predicting Y T with feature f Si .
We can solve this problem by selecting the source task with the largest transferability to T T . In fact, we only need to compute the numerator in the transferability definition since the denominator is the same for all source tasks, i.e. argmax i T(S i , T ) = argmax i H(f Si ).

Experiments
In this section, we present validation results and potential application of our transferability metric on real image data. (For implementation details, see Section 3 of the Supplementary Material.)

Validation of transfer performance
We validate H-score and transferability definitions in a transfer learning problem from ImageNet 1000-class classification (ImageNet-1000) to Cifar 100-class classification (Cifar-100). Figure S2.a compares the H-score and empirical performance of transferring from five different layers (4a-4f) of the ResNet-50 model pretrained on ImageNet1000. As H-score increases, log-loss of the target network decreases almost linearly while the training and testing accuracy increase, which validates the relationship between the expected log-loss and H-score. The training and testing accuracy are also positively correlated with H-score. It also shows that H-score can be applied for selecting the most suitable layer for fine-tuning in transfer learning.
We further tested our transferability metric for selecting the best target task for a given source task. In particular, we constructed 4 target classification tasks with 3, 5, 10, and 20 object categories from the Cifar-100 dataset. We then computed the task transferability from ImageNet-1000 (using the feature representation of layer 4f) to the target tasks. In Figure2.b, we observe a similar behavior as the H-score in the case of a single target task in Figure 2.a, showing that transferability can directly predict the empirical transfer performance.

Task transfer for 3D scene understanding
Next, we apply our transferability metric to solve the source task selection problem among 8 image-based recognition tasks for 3D scene understanding using the Taskonomy dataset [6]. We also compared the task transferability ranking based on H-score with the ranking using task affinity, an empirical transferability metric proposed by [6] with non-linear fine tuning.
For a fair comparison, we use the same trained encoders in [6] to extract source features with dimension k = 2048. It's worth noting that, six of eight tasks have images as their output. To compute the transferability for these pixel-to-pixel tasks, we cluster the pixel values of the output images in the training data into a palette of 16 colors and then compute the H-score of the source features with respect to each pixel. The transferability of the task is computed as the average of the H-scores over all pixels. For larger images, H-score can be evaluated on super pixels instead of pixels to improve efficiency.  Fig. 3: Ranking comparison between transferability and affinity score.
Pairwise Transfer Results. Source task ranking results using transferability and affinity are visualized side by side in Figure 3, with columns representing source tasks and rows representing target tasks. For classification tasks (the bottom two rows in the transferability matrix), the top two transferable source tasks are identical for both methods. Similar observations can be found in 2D pixel-to-pixel tasks (top two rows). A slightly larger difference between the two rankings can be found in 3D pixel-to-pixel tasks, especially 3D Occlusion Edges and 3D Keypoints. Though the top four ranked tasks of both methods are exactly the four 3D tasks. It could indicate that these low level vision tasks are closely related to each other so that the transferability among them are inherently ambiguous. We also computed the ranking correlations between transferability and affinity using Spearman's R and Discounted Cumulative Gain (DCG). Both criterion show positive correlations for all target tasks. The correlation is especially strong with DCG as higher ranking entities are given larger weights.
To show the task relatedness, we represent each task with a vector consisting of H-scores of all the source tasks for the given task, then apply agglomerative clustering over the task vectors. As shown in the dendrogram in Figure 3, 2D tasks and most 3D tasks are grouped into different clusters, but on a higher level, all pixel-to-pixel tasks are considered one category compared to the classifications tasks. Higher Order Transfer. A common way for higher order transfer is to concatenate features from multiple models in deep neural networks. Our transferability definition can be easily adapted to such problems. Figure 4 shows the ranking results of all combinations of source task pairs for each target task. For all tasks except for Edge3D and Depth, the best seond-order source feature is the combination of the top two tasks of the first-order ranking. We examine the exception in Figure 5, by visualizing the pixel-by-pixel H-scores of first and second order transfers to Depth using a heatmap (lighter color implies a higher H-score). Note that different source tasks can be good at predicting different parts of the image. The top row shows the results of combining tasks with two different "transferability patterns" while the bottom row shows those with similar patterns. Combining tasks with different transferability patterns has a more significant improvement to the overall performance of the target task.

Task transfer learning curriculum
A potential application of our transferability metric is developing an optimal task transfer curriculum, a directed acyclic graph over tasks that specifies the order in which to obtain labeled data for each task. For each task in the curriculum, an optimal feature representation can be learned using both its raw input and the representations of its parent tasks to improve  training efficiency. We use a heuristic based on the minimum spanning tree of a task graph, whose edge weights are inversely correlated with the larger transferability score between two tasks. Fig. 7.a shows the task curriculum for the eight tasks in Section 4.2. Furthermore, we did a similar experiments on a collection of binary object classification tasks using the NUS-WIDE multi-label dataset [17] (Fig. 7.b). We set a threshold to find the most salient transfers and the resulting curriculum is in line with human perception.

Conclusion
In this paper, we presented H-score, an information theoretic approach to estimating the performance of features when transferred across classification tasks. Then we used it to define a notion of task transferability in multi-task transfer learning problems, that is both time and sample complexity efficient. Our transferability score successfully predicted the performance for transfering features from ImageNet-1000 classification task to Cifar-100 task. Moreover, we showed how the transferability metric can be applied to a set of diverse computer vision and image-based recognition tasks using the Taskonomy and NUS-WIDE datasets. In future works, we will investigate properties of higher order transferability, developing more scalable algorithms that avoid computing the H-score of all task pairs. We also hope to design better task curriculum for task transfer learning in practical applications.
("TRI") provided funds to assist the authors with their research but this article solely reflects the opinions and conclusions of its authors and not TRI or any other Toyota entity.
[ [4] Yuqing Gao and Khalid M Mosalam, "Deep transfer learning for image-based structural damage recognition," Computer-Aided Civil and Infrastructure Engineering.
Supplementary Material S1 Derivation of Equation (4) First, we need to introduce some additional notations. Let X, x, X and P X represent a random variable, a value, the alphabet and the probability distribution respectively. √ P X denotes the vector with entries P X (x) and [ √ P X ] ∈ R |X |×|X | denotes the diagonal matrix of √ P X . For joint distribution P Y X , P Y X ∈ R |Y|×|X | represents the probability matrix. Given k feature functions f i : X → R, i = 1, ..., k, let f (x) = [f 1 (x), ..., f k (x)] ∈ R k be the feature vector of x, and F = [f (x 1 ) T , ..., f (x |X | ) T ] T ∈ R |X |×k be the feature matrix over all elements in X .
The left hand side of Equation (4) can be expressed as Since any feature function can be centered by subtracting the mean, without the loss of generality, we assume E[f (X)] = 0.
Using the one-to-one correspondence between Φ and F , i.e. Φ = √ P X F ∈ R |X |×k , we have = cov(f (X)) (7) The DTM matrixB introduced in Definition 1 can be written in matrix notation: where 1 is a column vector with all entries 1 and length |Y|. It follows that, =cov (E[f (X)|Y ]) (8) By substituting (7) and (8)

S2 Operational Meaning of H-Score
In this section, we will show that H-score characterizes the asymptotic probability of error in the hypothesis testing context. We will start with some background on error exponents from statistics, then explain how to estimate it using informa- Fig. S1: The binary hypothesis testing problem. The blue curves shows the probility density functions for P 1 and P 2 . The rejection region A c and the acceptance region A are highlighted in red and blue, respectively. The vertical line indicates the decision threshold.
tion geometry. Finally, we will show how computing H-score is in fact estimating the error exponent of a feature function on the sample data.

S2.1 Error Exponent and Hypothesis Testing
Consider the binary hypothesis testing problem over m i.i.d.
x m with the following hypotheses: Let P x m be the empirical distribution of the samples. The optimal test, i.e., the log likelihood ratio test log(T ) = log P1(x m ) P2(x m ) can be stated in terms of information-theoretic quantities as follows: where D is the Kullback-Leibler (KL) divergence operator.
Further, using Sannov's theorem, we have the asymptotic probability of type I error: where P * 1 = argmin P ∈A c D(P ||P 1 ) and A c (T ) = {x m : D(P x m ||P 2 ) − D(P x m ||P 1 ) < 1 m log T } represents the rejection region. Similarly, the asymptotic probability of type II error is where P * 2 = argmin P ∈A D(P ||P 2 ) and A = {x m : D(P x m ||P 2 ) − D(P x m ||P 1 ) > 1 m log T } represents the acceptance region (See Figure S1). Using the Bayesian approach for hypothesis testing, the overall error probability of the log likelihood ratio test is defined as: P (m) e = αP 1 + βP 2 and the best achievable exponent in the Bayesian probability of error (a.k.a. error exponent) is defined as: Error exponent E expresses the best rate at which the error probability decays as sample size increases for a particular hypothesis testing problem. See [18] for more background information on error exponents and its related theorems.

S2.2 Estimating Error Exponents
Suppose P 1 and P 2 are sampled from the -neighborhood erence distributon P 0 , and let φ 1 , φ 2 ∈ R |X | be vectors defined as: for i = 1, 2. The following lemma express the optimal error exponent E using φ 1 and φ 2 : Lemma 1. Under the local assumption defined earlier, the best achievable error exponent of the binary hypothesis testing problem with probabilities P 1 and P 2 is: where is a constant [16].
While the above lemma characterizes the asymptotic error probability distinguishing P 1 and P 2 based on the optimal decision function, most decision functions we learn from data are not optimal, as P 1 and P 2 are unknown. Given sample data x m and an arbitrary feature function f : X → R, which could be learned from a pre-trained model, the error exponent of the decision function based on f is reduced in a way defined by the following Lemma: Lemma 2. Given a zero-mean, unit variance feature function f : X → R and i.i.d. sampled data x m , the error probability of a mismatched decision function of the form l = 1 m m i=1 (f (x (i) )) has an exponent This lemma characterizes the error probability of using a normalized feature of the input data to solve a learning task by a linear projection of this feature between the input and output domains. Note that normalizing features to zero-mean and unit variance results in an equivalent decision function with a different threshold value, thus we can apply Lemma 2 to any features without the loss of generality. Further, it's obvious that the reduced exponent E f is maximized when ξ = φ 1 − φ 2 , and the optimal value is exactly the optimal error exponent E in Lemma 1. To estimate the reduced error exponent for multi-dimensional features, we present the kdimensional generalization of Lemma 2 below: Lemma 3. Given k normalized feature functions f (x) = [f 1 (x), . . . , f k (x)], such that E[f i (X)] = 0 for all i, and cov(f (X)) = I , we define a k-d statistics of the form l k = (l 1 , ..., l k ) where l i = 1 m m l=1 f i (x (l) ). Let ξ 1 , . . . , ξ k be k vectors with entries ξ i (x) = P X (x)f i (x) , 0 ≤ i ≤ k. Then the error exponent of l k is The proof of this Lemma can be found in [12].

S2.3 H-score and Error Exponents
Now we return to the binary classification problem. Using Lemma 3, we will show the linear relationship between Hscore and error exponents.
Theorem 1. Given P X|Y =0 , P X|Y =1 ∈ N X (P 0,X ) and fea- Proof. By Lemma 3, the L.H.S. of the equation can be written =c H(f ) The last equation uses the fact cov(f (X)) = I.

S3 Experiment Details
S3.1 Experiment 4.1 Experiment Setup. The training data for the target task in this experiment consists of 20, 000 images randomly sampled from the Cifar-100 dataset [19]. It is further split 9:1 into a training set and a testing set.
We first extracted features of the Cifar-100 training images from five different layers (4a -4f) of the ResNet-50 model pretrained on ImageNet-1000 [20]. Then we computed the H-score and the empirical transfer performance of each feature function for the Cifar-100 task. To compute the empirical performance, we trained the transfer network using stochastic gradient descent with batch size 20, 000 for 100 epochs. Result Discussion. As shown in Fig. 2.a of the main paper, transfer performance is better when an upper layer of the source networks is transferred. This could be due to the inherent similarity between the target task and the source task, such that the optimal representation learned for one task can still be suitable for the other. For the experiment of selecting the best target task (Fig. 2.b), we used the same network as the former experiment to compute the empirical transfer performance with batch size 64 for 50 epochs.
In addition, we validated H-score under different target sample sizes between 5-50K. Fig. S2 shows that target sample size does not affect the relationship between H-score and logloss, which further demonstrates that the H-score computation is sample efficient.
The Taskonomy dataset [6] contains 4,000,000 images of indoor scenes collected from 600 buildings. Every image has annotations for 26 computer vision tasks. For the transferability experiment, we randomly sampled 20, 000 images as the target task training data, and selected eight supervised tasks, shown in Table S1.  [6] trained a fully supervised network with an encoder-decoder structure. When testing the transfer performance from source task T S to target task T T , the encoder output of T S is used for training the decoder of T T . For a fair comparison, we used the same trained encoders to extract source features. The output dimension of all encoders are 16 × 16 × 8 and we flattened the output into a vector of length 2048. To reduce the computational complexity, we also resized the ground truth images into 64 × 64. Label Quantization. Fig. S3 illustrates the resizing and quantization process of a pixel-to-pixel task label. During the quantization process, we are primarily concerned with two factors: computational complexity and information loss. Too much information loss will lead to bad approximation of the original problem. On the other hand, having little information loss requires larger label space (cluster size) and higher computation cost. To test the sensitivity of the cluster size, we use cluster centroids to recover the ground truth image pixel-by-pixel. The recovery results for 3D occlusion edge detection is shown in Figure S4. When the cluster size is N = 5 (right), most detected edges in the ground truth image (left) are lost. We found that N = 16 strikes a good balance between recoverability and computation cost. Comparison of H-scores and Affinities. Table S2 presents the numerical values of the transferability and affinity scores between every pair of tasks, with columns representing source tasks and rows representing target tasks. This table is in direct correspondence with the ranking matrices in Fig. 3 of the main paper. For each target task, the upper row shows our results while the lower one shows the results in [6]. Score values are included in parenteses.
Here we present some detailed results on the comparison between H-score and the affinity score in [6] for pairwise transfer. The results of transferring from all tasks to the two classification tasks (Object Class. and Scene Class.) are shown in Figure S5; The results of transferring to Depth is shown in S6. We can see in general, although affinity and transferability have totally different value ranges, they tend to agree on the order of the top few ranked tasks.  Computing Efficiency. We ran the experiment on a workstation with 3.40 GHz ×8 CPU and 16 GB memory. Each pairwise H-score computation finished in less than one hour including preprocessing.

S3.3 Experiment 4.3
Data and Tasks. The NUS-WIDE dataset [17] contains 161,789 web images for training and 107,859 images for evaluation. Its tag set consists of 81 concepts, among which we selected two subsets, shown in Table S3. One subset contains 36 common concepts including scenes, animals and objects; The other subset contains only animal concepts. The NUS-WIDE dataset provides six types of low-level features. In this   Feature Extraction and Data Preprocessing. We consider the prediction of each concept as an unbalanced binary classification task and train a 4-layer fully-connected neural network ( Fig. S7) with batch-size 2048 for 50 epochs. For an arbitrary target task, the layer 3 activation output of the source models are used to calculate the H-scores. Task Transfer Curriculum. Given n tasks T 1 , . . . , T n , first we compute the pairwise transferability matrix M ∈ R n×n using H-score, where M (i, j) = H T j (f T j ) for all 1 ≤ i, j ≤ n. We assume that the task-specific features are close to optimal, such that H Tj (f Tj ) ≈ H Tj (f Tj opt ). Then by Definition 3, M (i, j) ≈ T(T i , T j ). Using the transferability matrix, we define an undirected graph G over the tasks, where the edge weight between node i and node j is defined by Parameter α defines the threshold to filter out less related task pairs, as the transferred representation in these cases contribute very little to the training of the target task. If G is connected, the minimum spanning tree outputs a set of task pairs that maximizes the total transferability with n − 1 pairwise transfers. If G is not connected, we have a minimum spanning forest that represents several task groups that can be learned independently. Finally, we recover the transfer directions on the minimum spanning tree from the transferability matrix. For the subset with 36 common concepts in the NUS-WIDE experiment, we found that when α = 0, i.e. no edges are filtered, 33 of the 35 edges in the resulting tree indicate transfers to concept 'sky' from other concepts. This phenomenon is reasonable in that sky and other concepts coexist in images with a high probability. To demonstrate the most significant task relationships, we set edge threshold α to be the 2.3 percentile of all weights, resulting in the minimum spanning tree in Fig. 7 of the main paper. On the other hand, edge filtering is not needed for the Taskonomy tasks and the animal concepts in the NUS-WIDE experiment, since most tasks are transferable to a similar extent. Therefore we chose α = 0 in these cases.

S4 Related Works
Transfer learning. Transfer learning can be devided into two categories: domain adaptation, where knowledge transfer is achieved by making representations learned from one input domain work on a different input domain, e.g. adapt models for RGB images to infrared images [21]; and task transfer learning, where knowledge is transferred between different tasks on the same input domain [22]. Our paper focus on the latter prolem. Empirical studies on transferability.
[5] compared the transfer accuracy of features from different layers in a neural network between image classification tasks. A similar study was performed for NLP tasks by [7]. [6] determined the optimal transfer hierarchy over a collection of perceptual indoor scene understanidng tasks, while transferability was measured by a non-parameteric score called "task affinity" derived from neural network transfer losses coupled with an ordinal normalization scheme. Task relatedness. One approach to define task relatedness is based on task generation. Generalization bounds have been derived for multi-task learning [8], learning-to-learn [9] and life-long learning [10]. Although these studies show theoretical results on transferability, it is hard to infer from data whether the assumptions are satisfied. Another approach is estimating task relatedness from data, either explicitly [23,24] or implicitly as a regularization term on the network weights [25,26]. Most works in this category are limited to shallow ones in terms of the model parameters. Representation learning and evaluation. Selecting optimal features for a given task is traditionally performed via feature subset selection or feature weight learning. Subset selection chooses features with maximal relevance and minimal redundancy according to information theoretic or statistical criteria [27,28]. The feature weight approach learns the task while regularizing feature weights with sparsity constraints, which is common in multi-task learning [29,30]. In a different perspective, [13] consider the universal feature selection problem, which finds the most informative features from data when the exact inference problem is unknown. When the target task is given, the universal feature is equivalent to the minimum error probability feature used in this work.


extfieldsofstudy:
Computer Science
Mathematics

text:
Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descent

Coded distributed computation has become common practice for performing gradient descent on large datasets to mitigate stragglers and other faults. This paper proposes a novel algorithm that encodes the partial derivatives themselves and furthermore optimizes the codes by performing lossy compression on the derivative codewords by maximizing the information contained in the codewords while minimizing the information between the codewords. The utility of this application of coding theory is a geometrical consequence of the observed fact in optimization research that noise is tolerable, sometimes even helpful, in gradient descent based learning algorithms since it helps avoid overfitting and local minima. This stands in contrast with much current conventional work on distributed coded computation which focuses on recovering all of the data from the workers. A second further contribution is that the low-weight nature of the coding scheme allows for asynchronous gradient updates since the code can be iteratively decoded; i.e., a worker's task can immediately be updated into the larger gradient. The directional derivative is always a linear function of the direction vectors; thus, our framework is robust since it can apply linear coding techniques to general machine learning frameworks such as deep neural networks.

Introduction
The majority of machine learning problems take the form: find a function h w0,...,w k in some family of hypothesis functions H that are parameterized over the w 0 , ..., w k which (1) where the D i are the datapoints, the x i are the input features, and the y i are the output features.
If the h w0,...,w k are smoothly parameterized by the w 0 , ..., w k , then this is usually accomplished by performing gradient descent on the summation of loss functions of the form l i (w) = l(h w (x (i) ), y (i) ) to compute i.e., find the w that best fits D. For example, one of the most common loss functions, l(f, y) = 1 2 ||f − y|| 2 , gives us the mean squared error and the ubiquitous method of least squares.
If the dataset D has many datapoints D i then the overall computation, or job, is distributed as tasks amongst workers, which model a distributed network of computing devices. This solution creates a new problem; stragglers and other faults can severely impact the performance and overall training time. An emerging technique is to use distributed coded computation to mitigate stragglers and other failures in the network. Many of the current algorithms only encode the data; this paper proposes further encoding the directional derivatives as well in such a way that allows for asynchronous gradient updates using low weight codes. Furthermore the number of weights usually grow quite large as well 1 , which necessitates a "2D" coding scheme which codes both the data and the derivatives.

Related Work
The two algorithms which we use to benchmark our algorithm are Gradient Coding  and K-Asynchronous Gradient Descent (Dutta et al., 2018b;; however, many of the design of our coding scheme is also influenced by the works in , (Yu et al., 2017), and (Dutta et al., 2020).

GRADIENT CODING
In the gradient coding Gradient Coding  scheme the main idea is to encode the derivatives with respects to the data partitions ∂ ∂Di from Eq. (1); since the loss function in Eq. (2) splits up into a sum of smaller loss functions, l i , in terms of the partitions, D i , linear codes can be efficiently applied to the gradients ∂ ∂Di . This work has gone on to spawn many works (Atallah & Rahnavard, 2018;Charles & Papailiopoulos, 2018;Ye & Abbe, 2018;Halbawi et al., 2018;Ozfatura et al., 2019b;Karakus et al., 2019;Ozfatura et al., 2019a;Horii et al., 2019;Raviv et al., 2020;Reisizadeh et al., 2019a;Maity et al., 2019;Bitar et al., 2019;Amiri & Gündüz, 2019;Reisizadeh et al., 2019b;Sasi et al., 2020;Wang et al., 2021;Ozfatura et al., 2020;Bitar et al., 2020;Zhang & Simeone, 2021); gradient coding is currently a vibrant topic of research. The main improvements of our coding scheme over the state of the art in Gradient Coding is that our code: can perform asynchronous coded updates, allows the backpropagation itself to be coded (which greatly reduces the communication complexity for high dimensional data), our code has 0 encoding and decoding overhead in terms of multiplications, and has an overall reduction in the redundancy of data/memory overhead.

ASYNCHRONOUS GRADIENT DESCENT
The main idea in Asynchronous Gradient Descent (Ferdinand et al., 2017;Dutta et al., 2018b;Ferdinand & Draper, 2018;Ferdinand et al., 2020;Dutta et al., 2021) is to simply perform a gradient update when whenever a specified number, k, workers have returned. The name "asynchronous" comes from the eponymous concept in distributed computing where communication rounds are not synchronized.

GENERAL CODED DISTRIBUTED FUNCTION COMPUTATION SCHEMES
The main idea in , (Yu et al., 2017), and (Dutta et al., 2020) is that one can distribute large matrix multiplications amongst workers and encode the smaller block matrix operations. The works initiated much research in distributed coded matrix multiplication (Dutta et al., 2020;Lee et al., 2017;Baharav et al., 2018;Dutta et al., 2018a;Wang et al., 2018;Soto et al., 2019;Dutta et al., 2019;Das & Ramamoorthy, 2019;Hong et al., 2021). Further work has been extended to include batch matrix multiplication as well (Yu et al., 2019;Jia & Jafar, 2020;Soto et al., 2022). The main drawback of these (multi-)linear methods is the non-linear activation functions; in particular, these methods can only encode the linear computations between the layers of a network. Another interesting approach is to attempt to encode the neural network itself (Kosaian et al., 2018;; however, this approach suffers from long training times dues to combinatorial explosion of different fault patterns is there are enough stragglers.

Contribution
The main contributions of this paper are to introduce a novel coding scheme for gradient descent that: allows for asynchronous gradient updates, maximizes the amount of information contained by random subsets of vectors, minimizes the weight of the code, compresses the gradient in a manner that scales well with the number of nodes, and achieves a lower a communication complexity and memory (storage) overhead with respect to the state of the art. Another improvement of our algorithm over the state of the art is to consider the correct information metric; all of the other coding schemes assume that the Hamming distance is the correct metric, which does not consider the natural (differential) geometry of the gradient. We will show that the correct distance is the one given by the real projective space 2 RP n . Furthermore, we will show that our coding scheme, i.e., our choice of coefficients, maximizes the amount of information returned by the workers and furthermore has zero decoding overhead (in terms of multiplications) since the master can just directly add and subtract the results returned by the workers without needing to decode the information.

Background
We quickly give some important definitions and background from coding theory, information theory, and geometry. In coded distributed computing an erasure code is a pair of functions C = (E, D) where the workers tasks are given by the encoding procedure θ 0 , ...,θ n−1 := E {θ 0 , ..., θ k } and a decoding procedure for some family of fault-tolerant subsets, F C , such that If F C consists of all the m-subsets (for some integer r) of θ 0 , ...,θ n−1 , then C can correct any r := n − m erasures or stragglers; furthermore, if r = n − k then the code is a maximum distance separable (MDS) code. If the encoder E is given by a generator matrix G C , i.e., if then C is called a linear code. The weight of a linear code is the maximum number of 0's in the rows of the matrix G C ; the importance of the weight metric stems from the fact that it measures the amount of work that the workers do since the rows of G C are the worker tasksθ i . Thus, in order to avoid confusion we will use t to denote the weight of the code as well as the number of tasks that each worker does; equivalently t is the number of data partitions on the workers. To further simplify notation we abuse notation and use C in place of G C and E C when the context is clear.
A potential point of confusion is that the θ need not be the weights w of the h w . This is because the derivative of loss function L also implicitly takes the data D i as an input; this is an important insight used in all gradient coding algorithms. One of the key insights of this paper is to allow the coded gradient to be linear combinations of both ∂ ∂Di and the ∂ ∂wi . An important notational convention is that we let the D i be partitions (or batches) of the data set instead of just datapoints as is common in the gradient coding literature; in particular, D 0 , ..., D t−1 denotes a partitioning of the dataset into t pieces.
The reason for the name "maximum distance separable code" is that an MDS maximizes the distances between the codewords E {θ 0 , ..., θ k } using the Hamming distance; in particular, maximum distance separable means that the code wordsθ ∈ C have achieve the maximum max C :code on Θ minθ ,θ ∈C d(θ,θ ) where d is the Hamming distance. There are two problems with this approach: the first is that MDS codes in this context require arbitrarily large amount of work, i.e., they have a large weight, and the second is that the classical discrete MDS codes are using the wrong metric. This paper proposes to use the metric given by the projective geometry 3 on the space of derivatives. Here we mean maximum distance separable with respect to the distance function d(θ, θ ) = min{arccos θ ,θ , arccos −θ,θ }.

General Overview of the Design Principles
Consider the case where there are two derivatives and we wish to create two parity tasks using only summation and subtraction in the encoding procedure. Such a code is given by the following generator matrix which adds fault tolerance to the job I = 1 0 0 1 with the parity tasks P = . This code has the serendipitous property of having negligible decoding complexity and negligible communication complexity! For example, if the master receives ∇ in the directionθ 3 = 1 √ 2 (θ 0 + θ 1 ), then the master can decrease both θ 0 and θ 1 by the value returned by W 2 , i.e.,θ 2 , if the master receives ∇ in the directionθ 2 = 1 √ 2 (θ 0 − θ 1 ), then the master can decrease θ 0 and increase θ 1 by the value returned by W 3 , i.e., θ 3 . The master need only perform 2 additions/subtractions, and more generally (see Eq. 4) if there are t "sub-tasks" the master only needs to perform t additions/subtractions. The multiplication by 1 √ 2 can be subsumed by the learning rate; thus, our code has zero multiplication overhead. Furthermore, this information can be communicated using only one float, since the master knows which direction/worker the derivative was computed from.

What is the Optimal Choice of Directions?
Looking at Fig. 1, we see that the code G is MDS in the sense that it maximizes the independence between the vectors. Equivalently 4 G minimizes the confusion between codewords or minimizes the mutual information between codewords; thereby maximizing the entropy or the information content. As we will soon see this has the effect of allowing lossy low-distortion compression for larger codes. A second contribution of this paper is to show how to preserve an approximate MDS property for larger codes which allows for this form of compression.
In what sense does C being MDS imply fault tolerance? The following example illustrates one kind of error which the code is immune to: Consider the case where two workers return the derivatives in the directionsθ = By inspecting the second diagram in Fig. 1, it is easy to see that lim →0θ → −θ, so that lim →0 arccos θ ,θ → π.We will also show that the Figure 1. The code C is MDS with respect to the the distance between the codewords. It is easy to see that −θi carries the same information asθi and it is therefore inefficient to include it since it is a form of replication coding. Likewise we should not include a vector that makes a small angle withθi for the same reason. The geometry of this problem is that of RP 1 , i.e., the real protective line. This is because the directionsθ and −θ are information theoretically equivalent. The second figure displays the relationship betweenθ andθ . Asθ becomes more linearly independent fromθ it begins to carry more novel information that cannot be inferred fromθ. At the "greenest" extremesθ andθ become statistically independent which is the maximum entropy configuration. Maximum entropy is equivalent (see Fn. 4) to maximum information about the θi.
error in the derivative can get bigger and bigger as → 0.

Motivating Example: Base Case of LWPD Codes
The last example did not allow us to show the more general lossy compression phenomenon that can occur for more general codes. Also we will soon prove that it is impossible to have MDS codes for large dimensions where the workers perform a small amount of work 5 . In a sense, k = 2 is a very special case. Therefore before showing the general compression phenomenon, let us show how to compress the derivative for k = 4. 1 2 ||h − y|| 2 , u input features x i , and space of hypothesis functions , H is the space of multinomial logistic regression functions (however, this procedure will work for any feed-forward deep neural network, see Fig. 2). Similarly to the previous design we can give the following directions to the workers however, this time we let ∂ ∂θ0 ="the derivative of the first half of the output nodes with respect to the first half of the dataset", ∂ ∂θ1 ="the derivative of the second half of the output nodes with respect to the first half of the dataset", ∂ ∂θ2 ="the derivative of the first half of the output nodes with respect to the second half of the dataset", and ∂ ∂θ3 ="the derivative of the second half of the output nodes with respect to the second half of the dataset". We can see that "lossy" part of the lossy compression is that the 4 workers don't necessarily return the gradient perfectly, but we will later prove that they return a pretty good approximation of it. However, we had a second further lossy compression step to our code; we give workers 5 and 6 the data partitions D 2 , D 3 and give workers 7 and 8 the data partitions D 1 , D 4 instead of giving these workers all of the partitions as the code in Eq. 3 suggests.

General Code Construction
We first show how to construct what we will denote as a [n, k, t]-projective derivative code, or [n, k, t]-code, for n = 2 m , k = 2 l and t = 2 p , i.e., n, k, t are all powers of 2, and then show how to use "cyclic" and "toroidal" permutations to construct the code for more general k, n; however, the t is always chosen to be a power of two for reasons that will soon become clear. The parameter n is the number of workers, k the number of derivatives/features, and t is the number of sub-tasks that each worker will perform; i.e., the number of derivatives per worker. Figure 2. The different ways to partition the backpropagation gradient. The first partition shows how to partition the gradient for a simple neural network with no hidden nodes. The two other partition corresponds to a more general deep-neural network with hidden nodes. The last partition shows how to apply the recursive step in Alg. 2.

The Characteristic Vectors
To construct the code we first construct the characteristic vectors from the following family of functions χ α : F p 2 −→ C, defined by the lambda expression where α, β ∈ F p 2 are defined as binary strings of length t and α, β is the dot product on α, β ∈ F p 2 , which is equivalent to taking the bit-wise AND 6 of α and β and then taking the XOR 7 of the result. In particular, α, β is defined as It is an elementary fact of representation theory that the vectors, √ 2 p χ α correspond to the irreducible representations of F p 2 in C and are therefore an orthogonal basis see Thm. 6 of (Serre, 2012) or Thm. 2.12 of (Fulton & Harris, 1991). One can also prove this fact by direct computation using discrete Fourier analysis see ch. 4 of (Tao & Vu, 2006). 6 AND is the logical conjunction, denoted by ∧, i.e., a ∧ b = 1 if a = b = 1 and a ∧ b = 0 otherwise. The bit-wise AND of two sequences α = α0...αp−1, β = β0...βp−1 is α ∧ β = (α0 ∧ β0)(α1 ∧ β1)...(αp−1 ∧ βp−1) 7 XOR is the exclusive or, denoted by ⊕, i.e., a ⊕ b = 1 if a = b and a ⊕ b = 0 if a = b.

Construction for Powers of Two
If we identify the binary strings α, β with the integers that they represent and let X (t) be the matrix defined coordinatewise by the equation where p = log(t) and χ α : F p 2 −→ C and let L (t) and R (t) be the matrices defined by the equation then we can define C (2k,k,t) , the generator for the [2k, k, t]code, as

Lightweight Projective Derivative Codes
where 8 s is the ratio of tasks to sub-tasks, θ (t) i is the sequence of sub-tasks θ it through θ (i+1)t−1 , andθ (t) i is similarly defined as a sequence of t consecutive workers. Equivalently if we define the "'rectangles" R (t) u,v as then we can define C (2k,k,t) coordinate -wise as It is straightforward to prove the following beautiful property Lemma 3.1. The matrices X (t) satisfy the following recursion relation Proof. This is a direct consequence of Thm. 10 in (Serre, 2012).
An alternative is the weaker statement 9 "X (2) is a Hadamard matrix and the tensor product of two Hadamard matrices is a Hadamard matrix" whose proof can be found in (Huffman & Pless, 2003).

DATA-&-GRADIENT-PARTITION FOR POWERS OF TWO
Similar to the example given in Sec. 2.2 we give the workersθ i the data partition given by Alg. 1. The

Algorithm 1 Data Partition Assignment
Input: data D, code parameters (n, k, t) Partition the data D into D 0 , .., D k−1 idea behind Alg. 1 is simple; we give the first worker 8 Equivalently, we can write these definitions as s = k t and θ (t) i = θitθit+1...θ (i+1)t−1 9 Although a weaker statement it suffices to to prove the claim of optimally,i.e., Thm. 4.5.
Data[θ 0 ] = D 0 , ..., D t−1 , and the second worker Data[θ 1 ] = D t , ..., D 2t−1 , and so on up to worker k, at which point we give the workers k, ..., n a cyclic shift of the previous assignment, e.g, worker k gets Data[θ k ] = D t 2 , ..., D t+ t 2 . The procedure for partitioning and encoding the gradients, Alg. 2, is slightly more involved; however, the main idea is illustrated in Fig. 2. The main intuition behind Alg. 2 is to

Algorithm 2 Gradient Partition Assignment
Input: network x, z 0 , ..., z m , y, code parameters (n, k, t) Set C := C (n,k,t) Partition y into t groups y (i) where y (0) = (y 0 , ..., y t−1 ); . . . ; Recursively call "Gradient Partition Assignment" on the network x, z 0 , ..., z m parameters (n, k, t) as in Fig. 2 to encode grad[θ i ] according to row i in C by repeatedly splitting the (non-zero-)row by t end for end if encode the gradient in the manner in which backpropagation occurs; this allows for the iterative decoding/gradient update at the master node, which in turn allows for asynchronous gradient updating.

Construction for General Parameters
Given some general (n, k, t) we construct the matrix C (n ,k ,t) , where n and k are the next nearest powers of 2 (repeating rows if necessary) and use a "2-D" permutation algorithm similar to (Fan et al., 2020) to distribute the sub-tasks in each round; however our algorithm uses more general (prime number) step-sizes chosen in each round and the permutations now occur in "higher dimensions 10 ." In particular; we now use a similar procedure to permute tasks amongst workers if n and k are not powers of 2. For example if we have n = 6 workers and k = 3 tasks we can add extra virtual tasks θ 3 = θ 0 , θ 4 = θ 1 , . . . , θ x = θ x%3 and perform the following toroidal permutations on C (5,3,2) so that at round r worker i performs task θ i+5r%n and similarly at round r we have t i = θ i+r%k .
More generally we find a displacement d equal to an (odd) prime number that is co-prime 11 to k and we let worker i performs task θ i+dr%n at round r and let t i = θ i+r%k at round r. This allows gives the following statistical uniformity lemma: Lemma 3.2. If the displacement, d, is equal to an (odd) prime number that is co-prime to k then the blue rectangle in (the general form of) Eq. 5 will visit every entry in the matrix with every possible pattern of X (t) and every cyclic permutation of the t i contained inside of the blue rectangle.
Proof. The leftmost point of the blue rectangle is equal to (i, i) + r(1, d) ≡ (i + r, i + dr) mod Z/n Z × Z/kZ. By the Chinese remainder theorem (see (Ireland & Rosen, 1982) or (Dummit & Foote, 2003)) (1, d) is a generator of mod Z/n Z × Z/kZ since d is coprime to 1, k, and n .

Theoretical Analysis
In this section we give a theoretical comparison of the algorithms, see Table 1, and we prove theorems regarding the existence and non-existence of codes with certain properties. The following theorem, i.e., Thm. 4.1, shows that Hammingdistance MDS coding schemes must have the workers do an arbitrarily large amount of work. We then later show that our codes are approximately MDS with respects to the projective geometry metric which maximize the amount of information sent back by the workers 12 while keeping the rectangle (see Eq. 5) is visited. 11 Although it is notoriously hard to find a prime divisor of number, it is surprisingly easy to find a prime non-divisor. This easy to see since one can just test divisibility by 2,3,5,... and since the product of the first primes less than 100 is approximately equal to 2 120 this will halt very quickly, i.e. it will halt in less than 25 steps for k < 2 120 since there are only 25 primes less than 100.
12 This is because large angles gives us large conditional entropy. amount of work done by the workers as low as possible; i.e., there are approximately projective-MDS that have weights t = 2, ..., n.
Theorem 4.1. If the parameters (n, k, t) satisfy t ≤ n − k then there is no Hamming-distance MDS (n, k)-code for the derivatives.
Proof. If A(C) i ="number of rows of weight i", then Theorem 7.4.1 in (Huffman & Pless, 2003) gives us that an MDS will have A(C) i = 0 for i ≤ n − k.
In particular; the proof of Thm. 4.1 can be strengthened to say that: Corollary 4.2. In an MDS (n, k)-coding scheme A(C) i = 0, for i ≤ n − k, where A(C) i = 0 is the weight distribution of a code.
The importance of Cor. 4.2 is made clear through the following interpretation: Corollary 4.3. In an MDS (n, k)-coding scheme all of the workers must do at least n − k amount of work.
However a simple observation of the construction given in Sec. 3.2 gives us that: Theorem 4.4. There exists (n, k, t)-LWPD codes for any t ≥ 2.
The next theorem proves that under the projective distance we have that our code achieves approximately maximal distance.
Theorem 4.5. The family (n, k, t)-code are approximately MDS (n, k)-code for the derivatives in the projectivedistance for n ≤ 2k.
Proof. By Lem. 3.2 it suffices to prove this for powers of two. The distance between any vectors is arccos 1 2 = π  vector; the distance is equal to the maximum π 2 for all other vectors.
The proof of Thm. 4.5 gives us that the distance between any two codewordsθ,θ is bounded above by d(C) = minθ ,θ∈C d(θ,θ) = π 3 and thus in term of percentages of the optimal π 2 we have π 2 − d(C) of the "theoretical" optimal distance; however there can be no code that achieves the "theoretical" optimal distance: Theorem 4.6. The percentage in Eq. 6 cannot be made 100%; i.e., there are no projective MDS codes for n > k which achieve distance π 2 .
Proof. If this statement was false there would be n + 1 linearly independent vectors in n-dimensional space, F n .
An interesting fact about the bound given by Thm. 4.5 is that is a constant independent of the dimension of the code and thus it scales well for larger and larger number of workers.

Experimental Results
The experiments were run on AWS Spot Instances; the workers are AWS EC2 c5a.large instances (compute optimized) and master is an AWS EC2 r3.large instance (Memory Optimized). The experimental procedure was written using Mpi4py (Dalcín et al., 2005;2008) in Python. We used a modification of the code in  written by the first author of  to implement Gradient Coding (GC) as well as the random data generation; the implementation only supported logistic regression and we generalized it to support multinomial logistic regression (i.e., more than one class). The software in  used a Gaussian mixture model of two distributions to create input features for the logistic model; we generalized it to allow for an arbitrary number of Gaussian distributions in the mixture to create a robust data set. To be as fair as possible in our comparison with K-Asynchronous Gradient descent (K-AC) (Dutta et al., 2018b) we made setup for K-AC nearly identical with the exception of the coding scheme; i.e., K-AC and LWPD used the exact same data partitions and same number of k workers in the k-asynchronous batches.
We ran experiments with 8 workers, 16 workers, and 32 workers (see Fig. 3). The testing error (i.e., the workers do not train on the test data) is plotted against the time. In all of the experiments we ran LWPD codes converged far faster; however, it often overfitted and sometimes the other algorithms would eventually get a lower test error. There are two possible explanations for this: either LWPD converges so much faster than the other algorithms that they never get a chance to overfit or the noise that initially helps LWPD find a very quick solution eventually causes it to stay some distance from the optimal solution. There is evidence for both of these possibilities because there are experiments were the other algorithms do not catch up to LWPD; see Sec. A for more results.
We have modified and re-ran our experiments to allow for deep neural networks (see Fig. 4). The new architecture had ReLU activations at the hidden nodes, Softmax at the output nodes, and cross entropy as the loss function. The experiments were run using Mpi4py on AWS Spot Instances with AWS EC2 c5a.large for the workers and AWS EC2 r3.large for the master. The original authors' implementation of Gradient Coding did not support deep neural networks and thus we simply compared with K-Asynchronous Gradient descent for these experiments. Both the updated and original experiments contained stragglers and highlighted the asynchronous nature of the algorithm, since we used Amazon Spot instances, which are the most unreliable but cost-efficient machines that Amazon AWS can offer.
In our experimental setup, all workers compute training loss individually. These plots should not be considered a centralized measure of model performance because the data set is decentralized. Thus, plotting training metrics does not make as much sense as, for example, visualizing the testing/validation set error or loss. Furthermore, we were guided by the intuition that the validation error is the more important measure, since it measures how well the algorithm or model can perform on data it has not seen.
The experimental data plots show test loss (y-axis) versus the time elapsed (x-axis). The test loss refers to the error on the validation set (which the model is not trained on) and thus overfitting occurs when the training loss continues to decrease, but the generalization error stops decreasing and eventually begins to grow. In our experiments, we observed that other methods reach similar convergence point much later in terms of number of iterations. One hypothesis is that our gradient coding approach offers faster training. A second possible explanation comes from the lossy compression of our algorithm. We trade off error for runtime. Our hypothesis is that the noise coming from the trade-off is beneficial in that it prevents us from being stuck in any potential saddle point.

Conclusion and Open Problems
We propose LWPD codes which allow for asynchronous gradient updates by maximizing the amount of information contained by random subsets of vectors and minimizing the weight of the code. Our code compresses the gradient in a manner that scales well with the number of nodes (and the dimension of the data) and achieves a lower a communication complexity and memory overhead with respect to the state of the art. Another improvement of our algorithm over the state of the art is our discovery of the correct information metric; all of the other coding schemes assume that the Hamming distance is the correct metric, which does not consider the natural (differential) geometry of the gradient. Furthermore, we showed that our code was very efficient since the master can just directly add and subtract the results returned by the workers without needing to decode the information. We proved many of the complexity guarantees theoretically and also provided much empirical evidence for the performance. For future work we would like to strengthen the theoretical results by proving stronger complexity bounds as well as further investigating the effect of noise (or lossy compression) on the performance; it seems that at first the lossy compression is a great help but eventually it causes over fitting.