∎

11institutetext: Dean Lee 22institutetext: Facility for Rare Isotope Beams and
Department of Physics and Astronomy
Michigan State University, East Lansing, MI 48824, USA
22email<EMAIL_ADDRESS>
# Chiral Effective Field Theory after Thirty Years:
Nuclear Lattice Simulations

Dean Lee

(Received: date / Accepted: date)

###### Abstract

The introduction of chiral effective field theory by Steven Weinberg three
decades ago has had a profound and lasting impact on nuclear physics. This
brief review explores the impact of Weinberg’s work on the field of nuclear
lattice simulations. Rather than a summary of technical details, an effort is
made to present the conceptual advances that made much of the recent progress
possible.

###### Keywords:

chiral effective field theory lattice simulations nuclear structure nuclear
scattering and reactions nuclear thermodynamics

##  1 Introduction

The author first learned of Weinberg’s chiral effective field theory
Weinberg:1990rz ; Weinberg:1991um ; Weinberg:1992yk  from the Loeb lectures
that Weinberg delivered at Harvard in 1993. While the author was a first-year
graduate student at the time and didn’t follow all the details, he appreciated
the bold conclusion that there was an underlying hierarchy of nuclear forces.
Weinberg was showing which of the many possible nuclear forces were most
important at low energies. There was, however, some uncertainty if Weinberg’s
proposed hierarchy could withstand the combinatorial enhancement of higher-
body forces in larger nuclei and many-body systems. While the field has made
great strides since then, this fundamental question still remains unresolved
and is an active area of research today. This article is a brief review
dedicated to the memory of the inspirational physicist and pioneer we lost in
2021.

##  2 Early lattice calculations

The idea of combining lattice simulations with effective field theory is quite
natural. The lattice grid provides a short-distance regulator that can be used
for an effective field theory. The earliest lattice calculations of nuclear
systems were posed in momentum space Brockmann:1992in . While this formulation
of the lattice action makes the kinetic energy simple, it has the
computational disadvantage that interaction terms require a summation over
many momentum modes. The earliest lattice calculations using a spatial lattice
studied the equation of state of nuclear matter with single-site and nearest-
neighbor interactions Muller:1999cp . Meanwhile, chiral perturbation theory
for pions with lattice regularization was developed at around the same time
Shushpanov:1998ms ; Lewis:2000cc , and there were also lattice formulations of
chiral symmetry involving static baryons Chandrasekharan:2003wy .

The first lattice calculations involving dynamical nucleons with chiral
effective field theory appeared in Ref. Lee:2004si . In that paper, pions were
also treated as dynamical fields that coupled to the nucleon fields. While
pion-nucleon interactions produced the required pion-exchange interactions
among the nucleons, they also altered the properties of individual nucleons
such as the nucleon mass and the pion-nucleon coupling strength. These
interactions of the dynamical pions were problematic since they were being
iterated to all orders without their corresponding short-distance
counterterms. Because of these complications, attention turned to simulations
of pionless effective field theory, which didn’t have such problems Lee:2004qd
; Lee:2005is ; Lee:2005it ; Borasoy:2005yc . At the same time, several groups
started applying lattice effective field theory to cold atoms and dilute
neutron matter using pionless effective field theory Chen:2003vy ;
Bulgac:2005pj ; Burovski:2006 ; Wingate:2006wy ; Abe:2007fe . This review,
however, focuses on nuclear lattice simulations using chiral effective field
theory.

Later it was realized that the problems with the pions could be cured by
removing the time derivative of the pion field from the lattice action
Borasoy:2006qn . The resulting pion fields then only had spatial correlations
without temporal correlations and produced the desired pion-exchange chiral
potentials without modifying single nucleon properties and pion-nucleon
vertices. This first study considered chiral effective field theory at leading
order. The basic building block of the calculation is the Euclidean-time
transfer matrix, $M$. $M$ is defined as the normal-ordered exponential of the
lattice Hamiltonian $H$ over one time lattice step,

$M=:\exp[-H\alpha_{t}]:,$ (1)

where $\alpha_{t}$ is the ratio of the time lattice spacing, $a_{t}$, to the
spatial lattice spacing, $a$. In the following, lattice units are used where
all quantities are multiplied by powers of the spatial lattice spacing to make
dimensionless combinations. One considers an initial state $|\Psi_{i}\rangle$
and final state $|\Psi_{f}\rangle$ that each have nonzero overlap with the
nuclear state of interest. By multiplying by powers of $M$ upon
$|\Psi_{i}\rangle$, the lowest energy state that couples to $|\Psi_{i}\rangle$
is enhanced. The projection amplitudes take the form

$Z_{f,i}(L_{t})=\langle\Psi_{f}|M^{L_{t}}|\Psi_{i}\rangle.$ (2)

By calculating the ratio $Z_{f,i}(L_{t})/Z_{f,i}(L_{t}-1)$ for large $L_{t}$,
one can determine the energy of the lowest energy state. By using more than
one initial and final state, a matrix of projection amplitudes can be used to
compute excited states as well.

##  3 Auxiliary fields and symmetries

Auxiliary fields are used to generate the short-range nuclear interactions.
The auxiliary field method can be viewed as a Gaussian integral formula
connecting the exponential of the two-particle density, $\rho^{2}$, to the
integral of the exponential of the one-particle density, $\rho$,

${:\exp\left(-\frac{c\alpha_{t}}{2}\rho^{2}\right):}=\sqrt{\frac{1}{2\pi}}\int^{\infty}_{-\infty}ds\,{:\exp\left(-\frac{1}{2}s^{2}+\sqrt{-c\alpha_{t}}s\rho\right):}\;.$
(3)

The normal ordering symbols $::$ indicate placing all annihilation operators
to the right and all creation operators to the left, along with the
corresponding minus sign for each operator order interchange. The normal
ordering ensures that the operator products of the creation and annihilation
operators behave as classical anticommuting Grassmann variables. Auxiliary
fields are introduced at every lattice site to produce the required two-
particle interactions Hubbard:1959ub ; Stratonovich:1958 ; Koonin:1986 .
Auxiliary fields can also be used to produce higher-body interactions
Chen:2004rq ; Korber:2017emn . The pion fields are treated in a manner similar
to the auxiliary fields, except that the pion fields also have nontrivial
correlations across different spatial lattice sites.

The amplitude for an $A$-body system is the determinant of an $A\times A$
matrix of single-nucleon amplitudes. The resulting lattice calculations
consist of computing matrix determinants for all possible values of the
auxiliary fields. These calculations are done using Markov Chain Monte Carlo
sampling, and it is important that the determinant is not fluctuating strongly
in sign or complex phase. Fortunately, the fact that the two S-wave nucleon-
nucleon channels have approximately equal strength gives rise to Wigner’s
approximate SU(4) symmetry Wigner:1936dx  of the low-energy nuclear
interactions. This approximate SU(4) symmetry for the attractive S-wave
interactions suppresses the sign and phase oscillations of the matrix
determinants. This has been studied in several papers, some of which also
consider inequalities that can be proven as a consequence Lee:2004ze ;
Lee:2004hc ; Chen:2004rq ; Lee:2007eu ; Hoffman:2016jqv .

The direct simulations of the higher-order terms in chiral effective field
theory cause problems with sign and phase oscillations. Some efforts were made
to mitigate this problem using extrapolation methods Lahde:2015ona , and
others have taking a variational approach Wlazlowski:2014jna . But most of the
efforts avoid this problem by computing high-order terms using perturbation
theory Borasoy:2007vk ; Epelbaum:2009rkz ; Epelbaum:2009zsa ; Epelbaum:2009pd
; Epelbaum:2010xt ; Lahde:2013uqa ; Li:2018ymw . In order to determine all the
unknown short-range operator coefficients, it is necessary to compute nucleon-
nucleon phase shifts on the lattice. While this can be done using Lüscher’s
finite volume method Luscher:1986pf , the spherical wall method was found to
provide greater accuracy for nucleon-nucleon scattering, especially for
coupled partial-wave channels Borasoy:2007vy ; Lu:2015riz ; Bovermann:2019jbt
. In addition to higher-order corrections in chiral effective field theory,
corrections needed to restore Galilean invariance have also been introduced
Li:2019ldq .

Numerous calculations of nuclear structure and many-body systems have been
performed, in particular the structure of alpha cluster states such as the
Hoyle state in 12C Epelbaum:2011md ; Epelbaum:2012qn ; Epelbaum:2012iu ;
Shen:2021kqr  as well as states in 16O Epelbaum:2013paa . As most other ab
initio methods have difficulty computing such highly-correlated alpha cluster
states, these works provide strong scientific justification for continuing
efforts in lattice chiral effective field theory. One important aspect of such
calculations is the removal lattice artifacts from the final results. Towards
this end, there have been several developments to restore rotational symmetry
Lu:2014xfa ; Stellin:2018fkj  as well as remove finite-volume corrections from
bound state calculations Bour:2011ef ; Koenig:2011vaa ; Davoudi:2011md ;
Korber:2015rce ; Konig:2017krd .

##  4 Adiabatic projection method

In order to compute nuclear scattering and reaction observables, a method
called the adiabatic projection method was developed Pine:2013zja ;
Rokash:2015hra ; Elhatisari:2016hby  and used to perform ab initio
calculations of alpha-alpha scattering Elhatisari:2015iga . The adiabatic
projection method constructs a low-energy effective theory for clusters of
particles that is exact in the limit of large Euclidean time. Consider a set
of two cluster states labelled according to their spatial separation vector R.
The initial wave functions are wave packets which, for large $|{\bf R}|$,
factorize into a product of two individual clusters,

$|{\bf R}\rangle=\sum_{{\bf r}}|{\bf r}+{\bf R}\rangle_{1}\otimes|{\bf
r}\rangle_{2}.$ (4)

The summation over $\bf{r}$ produces states with total momentum equal to zero.
The initial cluster states are binned together according to radial distance
and angular momentum. This produces radial position states with angular
momentum quantum numbers labelled as $|R\rangle^{J,J_{z}}$.

The next step is to multiply by powers of the transfer matrix in order to form
“dressed” cluster states that approximately span the set of low-energy
cluster-cluster scattering states in the periodic box of the lattice system.
After $n_{t}$ time steps, the dressed cluster states are

$|R\rangle^{J,J_{z}}_{n_{t}}=M^{n_{t}}|R\rangle^{J,J_{z}}.$ (5)

These dressed cluster states are then used to compute matrix elements of the
transfer matrix $M$,

$\left[M_{n_{t}}\right]^{J,J_{z}}_{R^{\prime},R}=\
^{J,J_{z}}_{\\!\\!\quad{n_{t}}}\langle
R^{\prime}|M|R\rangle^{J,J_{z}}_{n_{t}}.$ (6)

Since such states are not orthogonal, it is also necessary to compute the norm
matrix

$\left[N_{n_{t}}\right]^{J,J_{z}}_{R^{\prime},R}=\
^{J,J_{z}}_{\\!\\!\quad{n_{t}}}\langle R^{\prime}|R\rangle^{J,J_{z}}_{n_{t}}.$
(7)

The “radial adiabatic transfer matrix” is defined as the matrix product

$\left[{M^{a}_{n_{t}}}\right]^{J,J_{z}}_{R^{\prime},R}=\left[N_{n_{t}}^{-\frac{1}{2}}M_{n_{t}}N_{n_{t}}^{-\frac{1}{2}}\right]^{J,J_{z}}_{R^{\prime},R},$
(8)

and a spherical hard wall boundary of radius $R_{W}$ is imposed. For large
$n_{t}$, the standing waves of the radial adiabatic transfer matrix can be
used to determine the elastic phase shifts. By including additional channels,
the radial adiabatic transfer matrix can be used to compute inelastic
reactions as well as capture reactions Rupak:2013aue .

##  5 Pinholes for structure and thermodynamics

The amplitude for each auxiliary field configuration involves quantum states
which are superpositions of many different center-of-mass positions.
Therefore, information about density correlations relative to the center of
mass is not straightforward to obtain. The pinhole algorithm solves this
problem by computing a classical probability distribution for the positions of
the nucleons Elhatisari:2017eno . Let $\rho_{i,j}({\bf n})$ be the density
operator for nucleons with spin $i$ and isospin $j$ at lattice site n,

$\rho_{i,j}({\bf n})=a^{\dagger}_{i,j}({\bf n})a_{i,j}({\bf n}).$ (9)

The normal-ordered $A$-body density operator is defined as

$\rho_{i_{1},j_{1},\cdots i_{A},j_{A}}({\bf n}_{1},\cdots{\bf
n}_{A})=\;:\rho_{i_{1},j_{1}}({\bf n}_{1})\cdots\rho_{i_{A},j_{A}}({\bf
n}_{A}):.$ (10)

The $A$-body density operator is inserted in the middle of the Euclidean-time
lattice simulations. The amplitude will vanish unless there are $A$ nucleons
that exactly match the spatial positions ${\bf n}_{1},\cdots{\bf n}_{A}$ and
spin-isospin indices $i_{1},j_{1},\cdots i_{A},j_{A}$. The spatial positions
and spin-isospin indices can be viewed as “pinholes” in an otherwise
impenetrable wall, and the pinhole positions and indices are updated using
Monte Carlo sampling. This is shown in Fig. 1. The pinhole algorithm has been
used to compute the density distributions of protons and neutrons in various
nuclei Elhatisari:2017eno ; Lu:2018bat .

Figure 1: Schematic drawing of nucleons and corresponding pinholes in the
pinhole algorithm

In the area of nuclear thermodynamics, there have been recent lattice
calculations of spin and density correlations of neutron matter at nonzero
temperature Alexandru:2020zti . A modified version of the pinhole algorithm
called the pinhole trace algorithm was also developed for first principles
calculations of nuclear thermodynamics Lu:2019nbg . In the pinhole trace
algorithm, the trace over $A$-nucleon states is computed in position space,

${\rm Tr}\;O=\frac{1}{A!}\sum_{i_{1},j_{1},{\bf n}_{1}\cdots i_{A},j_{A},{\bf
n}_{A}}\langle 0|a_{i_{A},j_{A}}({\bf n}_{A})\cdots a_{i_{1},j_{1}}({\bf
n}_{1})\,O\,a^{\dagger}_{i_{1},j_{1}}({\bf n}_{1})\cdots
a^{\dagger}_{i_{A},j_{A}}({\bf n}_{A})|0\rangle.$ (11)

The pinhole trace algorithm was used to predict the liquid-vapor critical
point in symmetric nuclear matter and probe alpha cluster formation as a
function of temperature and density Lu:2019nbg .

##  6 Nuclear forces and quantum phase transitions

In addition to calculations using the most accurate lattice interactions
available, there has also been a concerted effort to understand the most
important characteristics of the nuclear force that determine the properties
of nuclear binding. In Ref. Elhatisari:2016owd , it was shown that nuclear
physics resides near a quantum phase transition between a nuclear liquid and a
Bose-Einstein condensate of alpha clusters. By changing the range and locality
of the nuclear force, one can traverse from one phase to the other. The
definition of locality here is that the nuclear interaction is diagonal with
respect to particle position. In contrast, a nonlocal interaction is one that
is off-diagonal with respect to nucleon positions. Fig. 2 shows the phase
diagram of the ground state of symmetric nuclear matter as a function of a
parameter $\lambda$ that controls the strength of the local part of the
nuclear interactions. The vertical axis is the energy relative to the
corresponding multi-alpha-particle threshold.

Figure 2: Phase diagram of the ground state of symmetric nuclear matter as a
function of the interpolating parameter $\lambda$ that controls the strength
of the local part of the nuclear interactions.

The mechanism for this dependence on range and locality arises from a
competition between attractive nuclear forces and the Pauli repulsion between
identical nucleons Rokash:2016tqh ; Kanada-Enyo:2020zzf . The radius of the
alpha particle sets a characteristic length scale where the Pauli repulsion
between identical nucleons in symmetric nuclear matter becomes strong. The
fact that nature appears to sit rather close to the quantum phase transition
can be understood as arising from the phenomenological coincidence that the
nucleon-nucleon interaction has an interaction range that is comparable to the
radius of the alpha particle. These findings were used to determine the
simplest possible microscopic nuclear force that could accurately reproduce,
on average, the ground state properties and charge radii of light and medium
mass nuclei as well as neutron matter Lu:2018bat . The interaction was
surprisingly simple and, except for the Coulomb interaction, respected
Wigner’s SU(4) symmetry. This approximate SU(4) symmetry can be understood as
resulting from an approximate spin-isospin exchange symmetry that appears when
the number of colors in quantum chromodynamics is large Kaplan:1995yg ;
Kaplan:1996rk ; Banerjee:2001js ; CalleCordon:2009ps ; Timoteo:2011tt ;
RuizArriola:2016vap ; Lee:2020esp . In Ref. Lee:2020esp , a derivation is
given for the observations in Ref. Timoteo:2011tt ; RuizArriola:2016vap  that
there is an optimal resolution scale, corresponding to a momentum cutoff scale
of about $500$ MeV, where spin-isospin symmetry is manifest. These findings
provide new insights into why chiral effective field theory performs
remarkably well for momentum cutoff values near this scale. They also provide
new insights into the success of nuclear lattice simulations, which rely on
the approximate spin-isospin symmetry to keep sign and phase oscillations
small.

##  7 Summary and Emerging Directions

Detailed reviews of lattice effective field theory can be found in Ref.
Lee:2008fa ; Drut:2012a ; Lahde:2019npb . This brief review gives an overview
of progress in nuclear lattice simulations using chiral effective field
theory. Nuclear lattice simulations is just one of many different methods to
address the few-body and many-body problem in nuclear physics. Perhaps its
most important feature is that its strengths and weaknesses are very different
from those of other approaches and thus provides valuable new information. For
example, nuclear lattice simulations is able to probe correlations in alpha
cluster states and compute nuclear thermodynamics without much difficulty.

This review started with the early history of nuclear lattice simulations, and
it discussed the auxiliary field formalism and the importance of symmetries in
keeping sign and phase oscillations in check. The adiabatic projection method
for nuclear scattering and reactions was reviewed, as well as the pinhole
algorithm for structure and the pinhole trace algorithm for thermodynamics. It
also presented a discussion of the connection between nuclear forces and
nuclear binding and the proximity of a quantum phase transition.

There are many new directions in nuclear lattice simulations now under active
development. The first lattice calculations using body-centered cubic lattices
were recently completed Song:2021yst . Lattice calculations were able to
determine the condensate fraction of a superfluid in the unitary limit
He:2019ipt , and the first lattice calculations of hypernuclei were performed
Frame:2020mvv  using impurity lattice Monte Carlo Bour:2014bxa . The
combination of lattice simulations with eigenvector continuation holds promise
for calculating higher-order without relying on perturbation theory
Frame:2017fah ; Frame:2019jsw ; Demol:2019yjt ; Demol:2020mzd ; Sarkar:2020mad
. All of these developments, as well as others still in progress, show that
the field of nuclear lattice simulations using chiral effective field theory
is progressing and growing in relevance.

###### Acknowledgements.

The author is grateful to Jose Manuel Alarcón, Buḡra Borasoy, Lukas Bovermann,
Jiunn-Wei Chen, Dechuan Du, Joaquín Drut, Serdar Elhatisari, Evgeny Epelbaum,
Dillon Frame, Rongzheng He, Youngman Kim, Nico Klein, Sebastian König, Hermann
Krebs, Timo Lähde, Ning Li, Bing-Nan Lu, Yuanzhuo Ma, Ulf-G. Meißner, Michelle
Pine, Alexander Rokash, Gautam Rupak, Avik Sarkar, Thomas Schäfer, Shihang
Shen, Gianluca Stellin, Young-Ho Song, and all the members of the Nuclear
Lattice Effective Field Theory Collaboration for their deep insights and
productive collaboration. Special thanks also to Ulf-G. Meißner for his
careful reading and comments on this review. Funding is gratefully
acknowledged by the U.S. Department of Energy (DE-SC0013365 and DE-SC0021152)
and the Nuclear Computational Low-Energy Initiative (NUCLEI) SciDAC-4 project
(DE-SC0018083) as well as computational resources provided by the Oak Ridge
Leadership Computing Facility through the INCITE award “Ab-initio nuclear
structure and nuclear reactions”, the Gauss Centre for Supercomputing e.V.
(www.gauss-centre.eu) for computing time on the GCS Supercomputer JUWELS at
Jülich Supercomputing Centre (JSC), the National Supercomputing Center at the
Korea Institute for Science and Technology Information, and the high-
performance computing centers at RWTH Aachen University and Michigan State
University.

## References

  * (1) Abe, T., Seki, R.: Lattice calculation of thermal properties of low-density neutron matter with nn effective field theory.  Phys. Rev. C79, 054,002 (2009)
  * (2) Alexandru, A., Bedaque, P., Berkowitz, E., Warrington, N.C.: Structure Factors of Neutron Matter at Finite Temperature.  Phys. Rev. Lett. 126(13), 132,701 (2021).  DOI 10.1103/PhysRevLett.126.132701
  * (3) Banerjee, M.K., Cohen, T.D., Gelman, B.A.: The Nucleon nucleon interaction and large N(c) QCD.  Phys. Rev. C 65, 034,011 (2002).  DOI 10.1103/PhysRevC.65.034011
  * (4) Borasoy, B., Epelbaum, E., Krebs, H., Lee, D., Meißner, U.G.: Lattice Simulations for Light Nuclei: Chiral Effective Field Theory at Leading Order.  Eur. Phys. J. A 31, 105–123 (2007).  DOI 10.1140/epja/i2006-10154-1
  * (5) Borasoy, B., Epelbaum, E., Krebs, H., Lee, D., Meißner, U.G.: Two-particle scattering on the lattice: Phase shifts, spin-orbit coupling, and mixing angles.  Eur. Phys. J. A 34, 185–196 (2007).  DOI 10.1140/epja/i2007-10500-9
  * (6) Borasoy, B., Epelbaum, E., Krebs, H., Lee, D., Meißner, U.G.: Dilute neutron matter on the lattice at next-to-leading order in chiral effective field theory.  Eur. Phys. J. A 35, 357–367 (2008).  DOI 10.1140/epja/i2008-10545-2
  * (7) Borasoy, B., Krebs, H., Lee, D., Meißner, U.G.: The Triton and three-nucleon force in nuclear lattice simulations.  Nucl. Phys. A 768, 179–193 (2006).  DOI 10.1016/j.nuclphysa.2006.01.009
  * (8) Bour, S., Koenig, S., Lee, D., Hammer, H.W., Meißner, U.G.: Topological phases for bound states moving in a finite volume.  Phys. Rev. D 84, 091,503 (2011).  DOI 10.1103/PhysRevD.84.091503
  * (9) Bour, S., Lee, D., Hammer, H.W., Meißner, U.G.: Ab initio Lattice Results for Fermi Polarons in Two Dimensions.  Phys. Rev. Lett. 115(18), 185,301 (2015).  DOI 10.1103/PhysRevLett.115.185301
  * (10) Bovermann, L., Epelbaum, E., Krebs, H., Lee, D.: Scattering phase shifts and mixing angles for an arbitrary number of coupled channels on the lattice.  Phys. Rev. C 100(6), 064,001 (2019).  DOI 10.1103/PhysRevC.100.064001
  * (11) Brockmann, R., Frank, J.: goo.  Phys. Rev. Lett. 68, 1830–1833 (1992)
  * (12) Bulgac, A., Drut, J.E., Magierski, P.: Spin 1/2 Fermions in the unitary regime: A Superfluid of a new type.  Phys. Rev. Lett. 96, 090,404 (2006).  DOI 10.1103/PhysRevLett.96.090404
  * (13) Burovski, E., Prokof’ev, N., Svistunov, B., Troyer, M.: The Fermi Hubbard model at unitarity.  New Journal of Physics 8(8), 153 (2006).  DOI 10.1088/1367-2630/8/8/153
  * (14) Calle Cordon, A., Ruiz Arriola, E.: Serber symmetry, Large N(c) and Yukawa-like One Boson Exchange Potentials.  Phys. Rev. C 80, 014,002 (2009).  DOI 10.1103/PhysRevC.80.014002
  * (15) Chandrasekharan, S., Pepe, M., Steffen, F.D., Wiese, U.J.: Nonlinear realization of chiral symmetry on the lattice.  JHEP 12, 035 (2003).  DOI 10.1088/1126-6708/2003/12/035
  * (16) Chen, J.W., Kaplan, D.B.: A Lattice theory for low-energy fermions at finite chemical potential.  Phys. Rev. Lett. 92, 257,002 (2004).  DOI 10.1103/PhysRevLett.92.257002
  * (17) Chen, J.W., Lee, D., Schäfer, T.: Inequalities for light nuclei in the Wigner symmetry limit.  Phys. Rev. Lett. 93, 242,302 (2004).  DOI 10.1103/PhysRevLett.93.242302
  * (18) Davoudi, Z., Savage, M.J.: Improving the Volume Dependence of Two-Body Binding Energies Calculated with Lattice QCD.  Phys. Rev. D 84, 114,502 (2011).  DOI 10.1103/PhysRevD.84.114502
  * (19) Demol, P., Duguet, T., Ekström, A., Frosini, M., Hebeler, K., König, S., Lee, D., Schwenk, A., Somà, V., Tichai, A.: Improved many-body expansions from eigenvector continuation.  Phys. Rev. C 101(4), 041,302 (2020).  DOI 10.1103/PhysRevC.101.041302
  * (20) Demol, P., Frosini, M., Tichai, A., Somà, V., Duguet, T.: Bogoliubov many-body perturbation theory under constraint.  Annals Phys. 424, 168,358 (2021).  DOI 10.1016/j.aop.2020.168358
  * (21) Drut, J.E., Nicholson, A.N.: Lattice methods for strongly interacting many-body systems.  J. Phys. G: Nucl. Part. Phys. 40(4), 043101 (2013).  DOI 10.1088/0954-3899/40/4/043101
  * (22) Elhatisari, S., Epelbaum, E., Krebs, H., Lähde, T.A., Lee, D., Li, N., Lu, B.n., Meißner, U.G., Rupak, G.: Ab initio Calculations of the Isotopic Dependence of Nuclear Clustering.  Phys. Rev. Lett. 119(22), 222,505 (2017).  DOI 10.1103/PhysRevLett.119.222505
  * (23) Elhatisari, S., Lee, D., Meißner, U.G., Rupak, G.: Nucleon-deuteron scattering using the adiabatic projection method.  Eur. Phys. J. A 52(6), 174 (2016).  DOI 10.1140/epja/i2016-16174-2
  * (24) Elhatisari, S., Lee, D., Rupak, G., Epelbaum, E., Krebs, H., Lähde, T.A., Luu, T., Meißner, U.G.: Ab initio alpha-alpha scattering.  Nature 528, 111 (2015).  DOI 10.1038/nature16067
  * (25) Elhatisari, S., et al.: Nuclear binding near a quantum phase transition.  Phys. Rev. Lett. 117(13), 132,501 (2016).  DOI 10.1103/PhysRevLett.117.132501
  * (26) Epelbaum, E., Krebs, H., Lahde, T.A., Lee, D., Meißner, U.G.: Structure and rotations of the Hoyle state.  Phys. Rev. Lett. 109, 252,501 (2012).  DOI 10.1103/PhysRevLett.109.252501
  * (27) Epelbaum, E., Krebs, H., Lähde, T.A., Lee, D., Meißner, U.G.: Viability of Carbon-Based Life as a Function of the Light Quark Mass.  Phys. Rev. Lett. 110(11), 112,502 (2013).  DOI 10.1103/PhysRevLett.110.112502
  * (28) Epelbaum, E., Krebs, H., Lähde, T.A., Lee, D., Meißner, U.G., Rupak, G.: Ab Initio Calculation of the Spectrum and Structure of 16O.  Phys. Rev. Lett. 112(10), 102,501 (2014).  DOI 10.1103/PhysRevLett.112.102501
  * (29) Epelbaum, E., Krebs, H., Lee, D., Meißner, U.G.: Ground state energy of dilute neutron matter at next-to-leading order in lattice chiral effective field theory.  Eur. Phys. J. A 40, 199–213 (2009).  DOI 10.1140/epja/i2009-10755-0
  * (30) Epelbaum, E., Krebs, H., Lee, D., Meißner, U.G.: Lattice chiral effective field theory with three-body interactions at next-to-next-to-leading order.  Eur. Phys. J. A 41, 125–139 (2009).  DOI 10.1140/epja/i2009-10764-y
  * (31) Epelbaum, E., Krebs, H., Lee, D., Meißner, U.G.: Lattice calculations for A=3,4,6,12 nuclei using chiral effective field theory.  Eur. Phys. J. A 45, 335–352 (2010).  DOI 10.1140/epja/i2010-11009-x
  * (32) Epelbaum, E., Krebs, H., Lee, D., Meißner, U.G.: Lattice effective field theory calculations for A = 3,4,6,12 nuclei.  Phys. Rev. Lett. 104, 142,501 (2010).  DOI 10.1103/PhysRevLett.104.142501
  * (33) Epelbaum, E., Krebs, H., Lee, D., Meißner, U.G.: Ab initio calculation of the Hoyle state.  Phys. Rev. Lett. 106, 192,501 (2011).  DOI 10.1103/PhysRevLett.106.192501
  * (34) Frame, D., He, R., Ipsen, I., Lee, D., Lee, D., Rrapaj, E.: Eigenvector continuation with subspace learning.  Phys. Rev. Lett. 121(3), 032,501 (2018).  DOI 10.1103/PhysRevLett.121.032501
  * (35) Frame, D., Lähde, T.A., Lee, D., Meißner, U.G.: Impurity Lattice Monte Carlo for Hypernuclei.  Eur. Phys. J. A 56(10), 248 (2020).  DOI 10.1140/epja/s10050-020-00257-y
  * (36) Frame, D.K.: Ab Initio Simulations of Light Nuclear Systems Using Eigenvector Continuation and Auxiliary Field Monte Carlo.  Other thesis (2019)
  * (37) He, R., Li, N., Lu, B.N., Lee, D.: Superfluid Condensate Fraction and Pairing Wave Function of the Unitary Fermi Gas.  Phys. Rev. A 101(6), 063,615 (2020).  DOI 10.1103/PhysRevA.101.063615
  * (38) Hoffman, M.D., Loheac, A.C., Porter, W.J., Drut, J.E.: Thermodynamics of one-dimensional SU(4) and SU(6) fermions with attractive interactions.  Phys. Rev. A 95(3), 033,602 (2017).  DOI 10.1103/PhysRevA.95.033602
  * (39) Hubbard, J.: Calculation of partition functions.  Phys. Rev. Lett. 3, 77–80 (1959).  DOI 10.1103/PhysRevLett.3.77
  * (40) Kanada-En’yo, Y., Lee, D.: Effective interactions between nuclear clusters.  Phys. Rev. C 103(2), 024,318 (2021).  DOI 10.1103/PhysRevC.103.024318
  * (41) Kaplan, D.B., Manohar, A.V.: The Nucleon-nucleon potential in the 1/N(c) expansion.  Phys. Rev. C 56, 76–83 (1997).  DOI 10.1103/PhysRevC.56.76
  * (42) Kaplan, D.B., Savage, M.J.: The Spin flavor dependence of nuclear forces from large n QCD.  Phys. Lett. B 365, 244–251 (1996).  DOI 10.1016/0370-2693(95)01277-X
  * (43) Koenig, S., Lee, D., Hammer, H.W.: Non-relativistic bound states in a finite volume.  Annals Phys. 327, 1450–1471 (2012).  DOI 10.1016/j.aop.2011.12.015
  * (44) König, S., Lee, D.: Volume Dependence of N-Body Bound States.  Phys. Lett. B 779, 9–15 (2018).  DOI 10.1016/j.physletb.2018.01.060
  * (45) Koonin, S.E.: Auxiliary-field Monte Carlo methods.  Journal of Statistical Physics 43(5-6), 985–990 (1986).  DOI 10.1007/BF02628325
  * (46) Körber, C., Berkowitz, E., Luu, T.: Sampling General N-Body Interactions with Auxiliary Fields.  EPL 119(6), 60,006 (2017).  DOI 10.1209/0295-5075/119/60006
  * (47) Körber, C., Luu, T.: Applying Twisted Boundary Conditions for Few-body Nuclear Systems.  Phys. Rev. C 93(5), 054,002 (2016).  DOI 10.1103/PhysRevC.93.054002
  * (48) Lähde, T.A., Epelbaum, E., Krebs, H., Lee, D., Meißner, U.G., Rupak, G.: Lattice Effective Field Theory for Medium-Mass Nuclei.  Phys. Lett. B 732, 110–115 (2014).  DOI 10.1016/j.physletb.2014.03.023
  * (49) Lähde, T.A., Luu, T., Lee, D., Meißner, U.G., Epelbaum, E., Krebs, H., Rupak, G.: Nuclear Lattice Simulations using Symmetry-Sign Extrapolation.  Eur. Phys. J. A 51(7), 92 (2015).  DOI 10.1140/epja/i2015-15092-1
  * (50) Lähde, T.A., Meißner, U.G.: Nuclear Lattice Effective Field Theory: An introduction, vol. 957.  Springer (2019).  DOI 10.1007/978-3-030-14189-9
  * (51) Lee, D.: Inequalities for low-energy symmetric nuclear matter.  Phys. Rev. C 70, 064,002 (2004).  DOI 10.1103/PhysRevC.70.064002
  * (52) Lee, D.: Pressure inequalities for nuclear and neutron matter.  Phys. Rev. C 71, 044,001 (2005).  DOI 10.1103/PhysRevC.71.044001
  * (53) Lee, D.: Spectral convexity for attractive SU(2N) fermions.  Phys. Rev. Lett. 98, 182,501 (2007).  DOI 10.1103/PhysRevLett.98.182501
  * (54) Lee, D.: Lattice simulations for few- and many-body systems.  Prog. Part. Nucl. Phys. 63, 117–154 (2009).  DOI 10.1016/j.ppnp.2008.12.001
  * (55) Lee, D., Borasoy, B., Schäfer, T.: Nuclear lattice simulations with chiral effective field theory.  Phys. Rev. C 70, 014,007 (2004).  DOI 10.1103/PhysRevC.70.014007
  * (56) Lee, D., Schäfer, T.: Neutron matter on the lattice with pionless effective field theory.  Phys. Rev. C 72, 024,006 (2005).  DOI 10.1103/PhysRevC.72.024006
  * (57) Lee, D., Schäfer, T.: Cold dilute neutron matter on the lattice. I. Lattice virial coefficients and large scattering lengths.  Phys. Rev. C 73, 015,201 (2006).  DOI 10.1103/PhysRevC.73.015201
  * (58) Lee, D., Schäfer, T.: Cold dilute neutron matter on the lattice. II. Results in the unitary limit.  Phys. Rev. C 73, 015,202 (2006).  DOI 10.1103/PhysRevC.73.015202
  * (59) Lee, D., et al.: Hidden Spin-Isospin Exchange Symmetry.  Phys. Rev. Lett. 127(6), 062,501 (2021).  DOI 10.1103/PhysRevLett.127.062501
  * (60) Lewis, R., Ouimet, P.P.A.: Lattice regularization for chiral perturbation theory.  Phys. Rev. D 64, 034,005 (2001).  DOI 10.1103/PhysRevD.64.034005
  * (61) Li, N., Elhatisari, S., Epelbaum, E., Lee, D., Lu, B., Meißner, U.G.: Galilean invariance restoration on the lattice.  Phys. Rev. C 99(6), 064,001 (2019).  DOI 10.1103/PhysRevC.99.064001
  * (62) Li, N., Elhatisari, S., Epelbaum, E., Lee, D., Lu, B.N., Meißner, U.G.: Neutron-proton scattering with lattice chiral effective field theory at next-to-next-to-next-to-leading order.  Phys. Rev. C 98(4), 044,002 (2018).  DOI 10.1103/PhysRevC.98.044002
  * (63) Lu, B.N., Lähde, T.A., Lee, D., Meißner, U.G.: Breaking and restoration of rotational symmetry on the lattice for bound state multiplets.  Phys. Rev. D 90(3), 034,507 (2014).  DOI 10.1103/PhysRevD.90.034507
  * (64) Lu, B.N., Lähde, T.A., Lee, D., Meißner, U.G.: Precise determination of lattice phase shifts and mixing angles.  Phys. Lett. B 760, 309–313 (2016).  DOI 10.1016/j.physletb.2016.06.081
  * (65) Lu, B.N., Li, N., Elhatisari, S., Lee, D., Drut, J.E., Lähde, T.A., Epelbaum, E., Meißner, U.G.: $AbInitio$ Nuclear Thermodynamics.  Phys. Rev. Lett. 125(19), 192,502 (2020).  DOI 10.1103/PhysRevLett.125.192502
  * (66) Lu, B.N., Li, N., Elhatisari, S., Lee, D., Epelbaum, E., Meißner, U.G.: Essential elements for nuclear binding.  Phys. Lett. B 797, 134,863 (2019).  DOI 10.1016/j.physletb.2019.134863
  * (67) Luscher, M.: Volume Dependence of the Energy Spectrum in Massive Quantum Field Theories. 2. Scattering States.  Commun. Math. Phys. 105, 153–188 (1986).  DOI 10.1007/BF01211097
  * (68) Muller, H.M., Koonin, S.E., Seki, R., van Kolck, U.: Nuclear matter on a lattice.  Phys. Rev. C 61, 044,320 (2000).  DOI 10.1103/PhysRevC.61.044320
  * (69) Pine, M., Lee, D., Rupak, G.: Adiabatic projection method for scattering and reactions on the lattice.  Eur. Phys. J. A 49, 151 (2013).  DOI 10.1140/epja/i2013-13151-3
  * (70) Rokash, A., Epelbaum, E., Krebs, H., Lee, D.: Effective forces between quantum bound states.  Phys. Rev. Lett. 118(23), 232,502 (2017).  DOI 10.1103/PhysRevLett.118.232502
  * (71) Rokash, A., Pine, M., Elhatisari, S., Lee, D., Epelbaum, E., Krebs, H.: Scattering cluster wave functions on the lattice using the adiabatic projection method.  Phys. Rev. C 92(5), 054,612 (2015).  DOI 10.1103/PhysRevC.92.054612
  * (72) Ruiz Arriola, E.: Low Scale Saturation of Effective NN Interactions and Their Symmetries.  Symmetry 8(6), 42 (2016).  DOI 10.3390/sym8060042
  * (73) Rupak, G., Lee, D.: Radiative capture reactions in lattice effective field theory.  Phys. Rev. Lett. 111(3), 032,502 (2013).  DOI 10.1103/PhysRevLett.111.032502
  * (74) Sarkar, A., Lee, D.: Convergence of Eigenvector Continuation.  Phys. Rev. Lett. 126(3), 032,501 (2021).  DOI 10.1103/PhysRevLett.126.032501
  * (75) Shen, S., Lähde, T.A., Lee, D., Meißner, U.G.: Wigner SU(4) symmetry, clustering, and the spectrum of 12C (2021)
  * (76) Shushpanov, I.A., Smilga, A.V.: Chiral perturbation theory with lattice regularization.  Phys. Rev. D 59, 054,013 (1999).  DOI 10.1103/PhysRevD.59.054013
  * (77) Song, Y.H., Kim, Y., Li, N., Lu, B.N., He, R., Lee, D.: Quantum Many-Body Calculations using Body-Centered Cubic Lattices (2021)
  * (78) Stellin, G., Elhatisari, S., Meißner, U.G.: Breaking and restoration of rotational symmetry in the low-energy spectrum of light alpha-conjugate nuclei on the lattice I: ${}^{8}\mathrm{Be}$ and ${}^{12}\mathrm{C}$.  Eur. Phys. J. A 54(12), 232 (2018).  DOI 10.1140/epja/i2018-12671-6
  * (79) Stratonovich, R.L.: On a method of calculating quantum distribution functions.  Soviet Phys. Doklady 2, 416–419 (1958)
  * (80) Timoteo, V., Szpigel, S., Ruiz Arriola, E.: Symmetries of the Similarity Renormalization Group for Nuclear Forces.  Phys. Rev. C 86, 034,002 (2012).  DOI 10.1103/PhysRevC.86.034002
  * (81) Weinberg, S.: Nuclear forces from chiral lagrangians.  Phys. Lett. B251, 288–292 (1990)
  * (82) Weinberg, S.: Effective chiral lagrangians for nucleon - pion interactions and nuclear forces.  Nucl. Phys. B363, 3–18 (1991)
  * (83) Weinberg, S.: Three body interactions among nucleons and pions.  Phys. Lett. B295, 114–121 (1992)
  * (84) Wigner, E.: On the Consequences of the Symmetry of the Nuclear Hamiltonian on the Spectroscopy of Nuclei.  Phys. Rev. 51, 106–119 (1937).  DOI 10.1103/PhysRev.51.106
  * (85) Wingate, M.: Field theoretic study of a cold Fermi gas in the unitary limit.  PoS LAT2006, 153 (2006).  DOI 10.22323/1.032.0153
  * (86) Wlazłowski, G., Holt, J.W., Moroz, S., Bulgac, A., Roche, K.J.: Auxiliary-Field Quantum Monte Carlo Simulations of Neutron Matter in Chiral Effective Field Theory.  Phys. Rev. Lett. 113(18), 182,503 (2014).  DOI 10.1103/PhysRevLett.113.182503


* Coley (1999) Coley, A.A.  Dynamical systems in cosmology.  In Proceedings of the Spanish Relativity Meeting (ERE 99), 1999, [gr-qc/9910074].
  * Paliathanasis and Leon (2020) Paliathanasis, A.; Leon, G.  Asymptotic behavior of N-fields Chiral cosmology.  The European Physical Journal C 2020, 80.
  * Övgün et al. (2018) Övgün, A.; Leon, G.; Magaña, J.; Jusufi, K.  Falsifying cosmological models based on a non-linear electrodynamics.  Eur. Phys. J. C 2018, 78, 462, [arXiv:gr-qc/1709.09794].
  * Hernández-Almada et al. (2020) Hernández-Almada, A.; Leon, G.; Magaña, J.; García-Aspeitia, M.A.; Motta, V.  Generalized Emergent Dark Energy: observational Hubble data constraints and stability analysis.  Mon. Not. Roy. Astron. Soc. 2020, 497, 1590–1602, [arXiv:astro-ph.CO/2002.12881].  https://doi.org/10.1093/mnras/staa2052.
  * Leon et al. (2021) Leon, G.; Magaña, J.; Hernández-Almada, A.; García-Aspeitia, M.A.; Verdugo, T.; Motta, V.  Barrow Entropy Cosmology: an observational approach with a hint of stability analysis.  JCAP 2021, 12, 032, [arXiv:astro-ph.CO/2108.10998].
  * Hernández-Almada et al. (2021) Hernández-Almada, A.; Leon, G.; Magaña, J.; García-Aspeitia, M.A.; Motta, V.; Saridakis, E.N.; Yesmakhanova, K.; Millano, A.D.  Observational constraints and dynamical analysis of Kaniadakis horizon-entropy cosmology 2021.  [arXiv:astro-ph.CO/2112.04615].
  * Hernández-Almada et al. (2022) Hernández-Almada, A.; Leon, G.; Magaña, J.; García-Aspeitia, M.A.; Motta, V.; Saridakis, E.N.; Yesmakhanova, K.  Kaniadakis-holographic dark energy: observational constraints and global dynamics.  Mon. Not. Roy. Astron. Soc. 2022, 511, 4147–4158, [arXiv:astro-ph.CO/2111.00558].
  * Uchaikin (2013) Uchaikin, V.V.  Fractional derivatives for physicists and Engineers; Higher Education Press, 2013.
  * Roberts (2014) Roberts, M.D.  Fractional Derivative Cosmology.  SOP Trans. Theor. Phys. 2014, 1, 310, [arXiv:gr-qc/0909.1171].
  * Vacaru (2010) Vacaru, S.I.  New Classes of Off-Diagonal Cosmological Solutions in Einstein Gravity.  Int. J. Theor. Phys. 2010, 49, 2753–2776, [arXiv:math-ph/1003.0043].  https://doi.org/10.1007/s10773-010-0468-1.
  * Vacaru (2012a) Vacaru, S.I.  Fractional Nonholonomic Ricci Flows.  Chaos Solitons Fractals 2012, 45, 1266–1276, [arXiv:math.DG/1004.0625].  https://doi.org/10.1016/j.chaos.2012.06.011.
  * Vacaru (2012b) Vacaru, S.I.  Fractional Dynamics from Einstein Gravity, General Solutions, and Black Holes.  Int. J. Theor. Phys. 2012, 51, 1338–1359, [arXiv:math-ph/1004.0628].  https://doi.org/10.1007/s10773-011-1010-9.
  * El-Nabulsi (2005) El-Nabulsi, R.A.  Fractional unstable Euclidean universe.  Electron. J. Theor. Phys. 2005, 2, 1–11.
  * El-Nabulsi (2007a) El-Nabulsi, R.A.  Accelerated universe dominated by holographic dark energy, supergravity inflationary potential.  Rom. J. Phys. 2007, 52, 163–170.
  * El-Nabulsi (2007b) El-Nabulsi, R.A.  Cosmology with a fractional action principle.  Rom. Rep. Phys. 2007, 59, 763–771.
  * El-Nabulsi (2008) El-Nabulsi, R.A.  Increasing effective gravitational constant in fractional ADD brane cosmology.  Electron. J. Theor. Phys. 2008, 5, 0103–106.
  * Hewitt and Wainwright (1992) Hewitt, C.G.; Wainwright, J.  Dynamical systems approach to tilted Bianchi cosmologies: Irrotational models of type V.  Phys. Rev. D 1992, 46, 4242–4252.  https://doi.org/10.1103/PhysRevD.46.4242.
  * Nilsson and Uggla (1996) Nilsson, U.; Uggla, C.  Spatially selfsimilar locally rotationally symmetric perfect fluid models.  Class. Quant. Grav. 1996, 13, 1601–1622, [gr-qc/9511064].  https://doi.org/10.1088/0264-9381/13/6/024.
  * Goliath et al. (1998) Goliath, M.; Nilsson, U.S.; Uggla, C.  Timelike selfsimilar spherically symmetric perfect fluid models.  Class. Quant. Grav. 1998, 15, 2841, [gr-qc/9811065].  https://doi.org/10.1088/0264-9381/15/9/028.


# Hierarchical Coded Gradient Aggregation Based on Layered MDS Codes

M. Nikhil Krishnan1, Anoop Thomas2, Birenjith Sasidharan3
This work was supported by faculty seed grants from the Indian Institute of
Technology Palakkad, Kerala, India (to M. N. Krishnan) and the Indian
Institute of Technology Bhubaneswar, Odisha, India (to A. Thomas). M. N.
Krishnan also acknowledges the support from the DST-INSPIRE fellowship. B.
Sasidharan is on leave of absence from the Government Engineering College,
Barton Hill (APJAK Technological University), Kerala, India. 1Department of
Data Science, IIT Palakkad
2School of Electrical Sciences, IIT Bhubaneswar
3 Department of Electrical and Computer Systems Engineering, Monash University
email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The growing privacy concerns and the communication costs associated with
transmitting raw data have resulted in techniques like federated learning,
where the machine learning models are trained at the edge nodes, and the
parameter updates are shared with a central server. Because communications
from the edge nodes are often unreliable, a hierarchical setup involving
intermediate helper nodes is considered. The communication links between the
edges and the helper nodes are error-prone and are modeled as
straggling/failing links. To overcome the issue of link failures, coding
techniques are proposed. The edge nodes communicate encoded versions of the
model updates to the helper nodes, which pass them on to the master after
suitable aggregation. The primary work in this area uses repetition codes and
Maximum Distance Separable (MDS) codes at the edge nodes to arrive at the
Aligned Repetition Coding (ARC) and Aligned MDS Coding (AMC) schemes,
respectively. We propose using vector codes, specifically a family of layered
MDS codes parameterized by a variable $\nu$, at the edge nodes. For the
proposed family of codes, suitable aggregation strategies at the helper nodes
are also developed. At the extreme values of $\nu$, our scheme matches the
communication costs incurred by the ARC and AMC schemes, resulting in a
graceful transition between these schemes.

##  I Introduction

Modern machine learning applications operate on a large amount of data that is
generated at the edge/client nodes. Typically, the learning models are trained
on a central server, and the data collected at the edge nodes is transmitted
to the server. The above method has two serious shortcomings. The amount of
data is huge and transmitting such data involves a lot of communication costs
for the edge nodes, which are often constrained by power and bandwidth. The
second shortcoming is with respect to data privacy and there is a growing
concern over sharing raw data with the central server. These factors have led
to the development of the Federated Learning (FL) framework[1, 2, 3, 4],
wherein models are trained directly on the edge devices and only model updates
are transmitted to the server. Since only the updates are transmitted, the
technique significantly reduces transmission costs and mitigates privacy
concerns.

Gradient descent is a widely used algorithm for training machine learning
models. Synchronous gradient descent over centralized data using multiple
worker nodes is well-studied, and algorithms to improve the computation time
have been proposed in the literature (for instance, see [5, 6, 7, 8, 9]). The
current paper considers synchronous gradient descent over a decentralized data
set in the FL setting. The data sets are available only locally at the edge
nodes, which compute gradients over their respective data sets. The computed
gradients are then shared with a central server for a global model update. The
edge nodes are often power-constrained and may only be available
intermittently. As a result, the communications between edge nodes and the
central server are unreliable. Hence, to assist the edge nodes, hierarchical
systems are considered in [10, 11]. In this paper, we adopt the hierarchical
coded gradient aggregation strategy proposed in [10], where intermediate
helper nodes support the edge nodes in communicating the computed gradient
vectors to the central server. Each edge node computes the gradient over its
data set and transmits coded fragments of the gradient to all the helper
nodes. These coded fragments are obtained using a suitable linear code,
referred to as the client code. The transmissions from edge nodes to the
helper nodes are assumed to be unreliable and this scenario is modeled by
introducing straggling links. Typically, the helper nodes have more computing
and communication resources and hence the transmissions between the helper
nodes and the central server are assumed to be error-free. Moreover, to reduce
communication costs, the helper nodes communicate the received gradient
vectors to the central server possibly after an aggregation step.

The paper [10] proposes two hierarchical coded gradient aggregation schemes
that use two different client codes; the Aligned Repetition Coding (ARC)
scheme, based on repetition codes and the Aligned MDS Coding (AMC) scheme,
based on Maximum Distance Separable (MDS) codes. The ARC scheme allows
reducing the helper-to-master communication cost while performing poorly with
respect to the edge-to-helper communication cost. The AMC scheme, on the other
hand, aims at reducing the edge-to-helper communication cost to the lowest
possible value. In a scheme proposed in [12] that makes use of pyramid
codes[13], it is possible to achieve a reduction in helper-to-master
communication cost at the expense of edge-to-helper communication cost, by
tuning a certain parameter of the scheme.

We observe that previous works have solely considered scalar codes as client
codes. Vector codes, a more general coding framework that permits to have
vectors as code symbols, have been proved useful in other contexts such as
design of low-complexity MDS codes [14], regenerating codes [15] etc. In the
present work, we propose to use vector codes as client codes and they turn out
to do well here as well. In the remainder of this section, we describe the
system model, formalize the problem setting and present a summary of our main
results.

###  I-A System Model

We begin with some notation. Let $\mathbb{Z}$ denote the set of all integers.
For $i,j\in\mathbb{Z}$, we have $[i:j]\triangleq\\{x\in\mathbb{Z}\mid i\leq
x\leq j\\}$. As a special case, we use $[j]$ to indicate the set $[1:j]$.
Given a matrix $A$, we use $A(i,j)$ to denote the element which lies in row
$i$ and column $j$.

There is a central server or a master $M$ aiming to compute an optimal vector
$w^{*}\in\mathbb{R}^{p}$ (i.e., there are $p$ parameters for the learning
model) based on data samples available locally at $n_{e}$ edge (client) nodes.
Let $D$ denote the collection of all data samples distributed across edge
nodes. The function $\sum_{x\in D}\ell(w,x)$ is to be minimized to compute the
optimal $w^{*}$, where $\ell(.)$ is an underlying loss function. The
minimization can be done by carrying out a gradient descent algorithm in which
every iteration $t$ involves an update rule of $w^{t+1}=w^{t}-\mu\sum_{x\in
D}\nabla\ell(w^{t},x)$, where $\mu$ is the learning rate. Let $D=D_{1}\cup
D_{2}\cup\cdots\cup D_{n_{e}}$ be a partition of data samples, where $D_{i}$
denotes the subset of data samples available at the $i$-th edge node $E_{i}$.
We can then write the (global) gradient as $\underline{g}:=\sum_{x\in
D}\nabla\ell(w^{t},x)=\sum_{i=1}^{n_{e}}\sum_{x\in
D_{i}}\nabla\ell(w^{t},x)=\sum_{i=1}^{n_{e}}\underline{g}_{i}$, and we define
$\underline{g}_{i}\in\mathbb{R}^{p}$ as the local gradient available at the
$i$-th edge node.

In the hierarchical model, the $n_{e}$ edge nodes
$E_{1},E_{2},\ldots,E_{n_{e}}$ are connected to the master via $n_{h}$ helper
nodes $H_{1},H_{2},\ldots,H_{n_{h}}$. Every edge is connected to every helper,
and every helper in turn to the master. This is illustrated in Fig. 1. A
helper is not just a router, but can as well process the messages it receives,
and pass them to the master. For this reason, they are also called
aggregators. The links from helpers to the master are assumed to be perfectly
reliable, whereas those from edges to helpers are not. We consider the
following adversarial channel model between edge nodes and helpers. Among the
$[n_{h}]$ links available to each edge node (one link to each helper node), up
to $s\in[n_{h}-1]$ can straggle or fail. Each helper node communicates to the
master the observed erasure (straggler) pattern, represented by a binary
vector of length $n_{e}$. The master constructs an erasure matrix ${\cal E}$,
an $n_{e}\times n_{h}$ binary matrix, where ${\cal E}(i,j)=1$ if and only if
the link between edge $E_{i}$ and helper $H_{j}$ has failed. The erasure
matrix ${\cal E}$ is passed to all the helpers. Thus, all helpers and the
master have full knowledge of the erasure matrix.

Figure 1: The hierarchical coded gradient aggregation setting with $n_{e}$
edge nodes and $n_{h}$ helper nodes.

While the gradient vectors are indeed real vectors, they are often quantized
and represented by a vector over a finite field. The effect of quantization on
the convergence of training and other related issues forms a separate line of
research [16, 17, 18], which is not of interest in this paper. We henceforth
assume that all the mathematical operations are over finite fields.
Specifically, we set $\underline{g},\underline{g}_{i}\in\mathbb{F}^{p}$, where
$\mathbb{F}$ is the finite field over which the client code is defined.

Let alphabet $\mathbb{A}\triangleq\mathbb{F}^{d}$, where $d$ is a parameter
dependent on the client code being used. An edge $E_{i}$ generates
$\underline{c}_{i,j}\in\mathbb{A}^{b_{i,j}}$ as a function of
$\underline{g}_{i}$ and transmits $\underline{c}_{i,j}$ to $H_{j}$, for every
$j\in[n_{h}]$. We assume that every edge node uses the same function in this
process. We shall restrict to linear functions over $\mathbb{F}$ and also fix
$b_{ij}=b$ for every $i,j$. We describe the computation of
$\underline{c}_{i,j}$ in terms of a linear code ${\cal C}$ over $\mathbb{F}$.
The code ${\cal C}$ is referred to as the client code.

Let $\Omega(s)$ denote the set of all erasure matrices with $s$ straggling
links per edge node. Assume that an erasure matrix $\epsilon\in\Omega(s)$ has
occurred and is known to all the helpers. Given an $\epsilon\in\Omega(s)$,
every helper node $H_{j}$ invokes a function ${\cal A}_{j}$ that maps
$\\{\underline{c}_{i,j}\mid i\in[n_{e}],\epsilon(i,j)=0\\}$ to a vector
$\underline{v}_{j}\in\mathbb{A}^{m_{j}(\epsilon)}$ and transmits
$\underline{v}_{j}$ to the master. The collection of functions ${\cal
A}=({\cal A}_{1},{\cal A}_{2},\ldots,{\cal A}_{n_{h}})$ is referred to as an
aggregation strategy. We emphasize that both $\mathcal{A}_{j}$ and
$m_{j}(\epsilon)$ depend on the realization $\epsilon$ of the erasure matrix.
The messages $\\{\underline{v}_{j}\\}$ to the master are assumed to be
transmitted over error-free links. The master makes use of
$\\{\underline{v}_{j}\mid j\in[n_{h}]\\}$ to compute
$\underline{g}=\sum_{i=1}^{n_{e}}\underline{g}_{i}$. The $2$-tuple $({\cal
C},{\cal A})$ is referred to as a scheme for coded gradient aggregation.

###  I-B Communication Costs

Communication costs are quantified by the number of transmitted symbols from
the field $\mathbb{F}$, normalized by the number of parameters (gradient
vector size) $p$. An edge node transmits $b$ symbols over the alphabet
$\mathbb{A}\triangleq\mathbb{F}^{d}$ to every helper. Therefore, we define the
communication cost from edge to helpers as:

$\displaystyle C_{\text{EH}}$ $\displaystyle=$
$\displaystyle\frac{n_{h}db}{p}.$

Assume that helpers employ an aggregation strategy ${\cal A}$. Since
$m_{j}(\epsilon)$ is a function of the erasure matrix $\epsilon$, the
communication cost from helpers to the master in turn, is a function of
$\epsilon$ and is defined as:

$\displaystyle C_{\text{HM}}(\epsilon)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n_{h}}\frac{dm_{j}(\epsilon)}{p}.$

If we impose a uniform probability distribution over $\Omega(s)$, the average
communication cost from helpers to the master can naturally be defined as:

$\displaystyle C_{\text{HM},\text{av}}=\ \mathbb{E}[C_{\text{HM}}(\epsilon)]\
=\
\frac{1}{|\Omega(s)|}\sum_{\epsilon\in\Omega(s)}\sum_{j=1}^{n_{h}}\frac{dm_{j}(\epsilon)}{p}.$

Alternatively, one may pursue a worst-case approach and define the
communication cost from helpers to the master as:

$\displaystyle
C_{\text{HM}}=\max_{\epsilon\in\Omega(s)}\sum_{j=1}^{n_{h}}\frac{dm_{j}(\epsilon)}{p}.$

In this paper, we shall adopt the worst-case approach in our analysis of
communication costs. Since $C_{\text{HM}}$ itself is a function of
$\mathcal{C}$ and $\mathcal{A}$, we also observe that it may be meaningful to
define the min-max cost:

$\displaystyle C_{\text{HM}}^{*}$ $\displaystyle=$
$\displaystyle\min_{{\left(\mathcal{C},\cal A\right)}}C_{\text{HM}}.$

However, we will not be pursuing this direction in the current paper.

###  I-C Our Contributions

  * •

We propose the use of vector codes (i.e., $b\geq 1$) as client codes for the
hierarchical coded gradient aggregation framework. In particular, we explore
the idea of layering numerous short-block-length MDS codes to create a vector
code (for this reason, we will refer to the resultant client code as a layered
code). We attribute this idea to the work [19], which used it in the context
of distributed storage systems (DSSs). In the DSS literature, this idea is
known [20] to result in optimal operating points on a storage overhead vs.
repair bandwidth trade-off curve.

  * •

The proposed layered code is parameterized by $\nu\in[n_{h}-s]$. Our code is
equivalent to that used in the ARC scheme at $\nu=1$, while at $\nu=n_{h}-s$,
the code reduces to that used in the AMC scheme.

  * •

We propose a novel aggregation strategy, which results in achieving
intermediate operating points between the ARC and AMC schemes by trading off
$C_{\text{HM}}$ for $C_{\text{EH}}$. For instance, see Fig. 2. While a few
intermediate points close to the AMC are provided in [12], our proposed scheme
achieves a graceful transition between the extreme points.

Figure 2: The tradeoff existing between $C_{\text{EH}}$ and $C_{\text{HM}}$.
Here, $n_{h}=10$, $s=2$ and $n_{e}=50$. Our scheme has a certain parameter
$\nu\in[8]$. As $\nu$ increases, the operating point moves from right to left
in the curve (trading off $C_{\text{HM}}$ for reducing $C_{\text{EH}}$).

##  II The Layered Coding Scheme

The scheme referred to as the layered coding scheme consists of a client code
${\cal C}_{\nu}$ and an aggregation strategy ${\cal A}_{\nu}$. Unlike
previously known schemes with scalar codes, we propose to use a vector code as
the client code, i.e., with $b\geq 1$.

###  II-A Description of ${\cal C}_{\nu}$

Let the parameters of the system model $(p,n_{e},n_{h},s)$ be given. Fix the
parameter $\nu\in[n_{h}-s]$ and set $L={n_{h}\choose\nu+s}$ and
$\lambda=L\nu$. Here, $L$ denote the number of layers (to be defined shortly).
We choose the alphabet of the client code $\mathbb{A}=\mathbb{F}^{d}$ where
$d=\frac{p}{\lambda}$. The client code ${\cal C}_{\nu}$ is a vector code and
its construction is described by providing the explicit mapping from a message
$\underline{g}_{i}\in\mathbb{F}^{p}$ to a codeword array
$\underline{c}_{i}\in\mathbb{A}^{b\times n_{h}}$. Here $b$ is the
subpacketization level of the vector code and its value will be evident soon.
The mapping from $\underline{g}_{i}$ to $\underline{c}_{i}$ is described in
three steps:

  1. 1.

The vector $\underline{g}_{i}$ is partitioned into $\lambda$ subvectors
$\\{\underline{g}^{(\ell)}_{i,j}\mid j\in[\nu],\ell\in[L]\\}$ each belonging
to $\mathbb{A}$. Let ${\bf G}$ denote a $\nu\times(\nu+s)$ generator matrix of
a $[\nu+s,\nu]$-MDS code $C_{\text{MDS}}$ over $\mathbb{F}$. Then for every
$\ell\in[L]$, we define:

$\displaystyle[\underline{c}^{(\ell)}_{i,1}\ \underline{c}^{(\ell)}_{i,2}\
\cdots\ \underline{c}^{(\ell)}_{i,\nu+s}]=[\underline{g}^{(\ell)}_{i,1}\
\underline{g}^{(\ell)}_{i,2}\ \cdots\ \underline{g}^{(\ell)}_{i,\nu}]{\bf G}.$

  2. 2.

In this step, we shall arrange the symbols
$\\{\underline{c}^{(\ell)}_{i,j}\mid j\in[\nu+s],\ell\in[L]\\}$ in an $L\times
n_{h}$ array with certain cells left blank. Each row of this array is referred
to as a layer, and thus there are $L$ layers. A cell of the array is indexed
by a $2$-tuple $(x,y)$, where $x\in[L]$ denotes the row number and
$y\in[n_{h}]$ is the column number. Let
$\mathcal{H}=\\{\mathcal{H}_{1},\mathcal{H}_{2},\ldots,\mathcal{H}_{L}\\}$
denote the set of all $(\nu+s)$-element subsets of $[n_{h}]$ arranged in a
lexicographic order. Every $\mathcal{H}_{\ell}\in\mathcal{H}$ is denoted by
$\mathcal{H}_{\ell}=\\{\mathcal{H}_{\ell,1},\mathcal{H}_{\ell,2},\cdots,\mathcal{H}_{\ell,\nu+s}\\}$
such that
$\mathcal{H}_{\ell,1}<\mathcal{H}_{\ell,2}<\cdots<\mathcal{H}_{\ell,\nu+s}$.
Then $\underline{c}^{(\ell)}_{i,j}$ is placed on the
$(\ell,\mathcal{H}_{\ell,j})$-th cell of the array.

  3. 3.

By construction, there are precisely ${n_{h}-1\choose\nu+s-1}$ layers at which
the array is filled up for every column $j$. We obtain the $(b\times n_{h})$
codeword array $\underline{c}_{i}$ by omitting unfilled cells of the $(L\times
n_{h})$ array generated in the previous step, where
$b={n_{h}-1\choose\nu+s-1}$.

This completes the description of encoding $\underline{g}_{i}$ into
$\underline{c}_{i}$ and clearly it is a 1-1 correspondence. Since the codeword
array involves a layering of MDS codewords, the code is referred to as a
layered code with parameter $\nu$. The edge node can complete the encoding
process to generate $\underline{c}_{i}$ and transmit the $j$-th column
$\underline{c}_{i,j}\in\mathbb{A}^{b}$ to the helper $H_{j}$. Alternatively,
the edge node $E_{i}$ can start transmission even before computing the entire
codeword array. This is possible because the coded symbols are generated
layer-by-layer, and once encoding within a layer is finished, those symbols
can be transmitted to respective helpers. The algorithm followed by each edge
node to transmit the codeword array in this manner is given in Alg. 1.

1

2Let $\mathbf{G}\in\mathbb{F}^{\nu\times(\nu+s)}$ denote a generator matrix of
a $[\nu+s,\nu]$-MDS code.

3for  _$\ell\in[{n_{h}\choose\nu+s}]$_ do

// Encoding

4 Edge node $E_{i}$ generates $\nu+s$ coded fragments
$\\{\underline{c}^{(\ell)}_{i,j}\\}_{j\in[\nu+s]}$ in the following manner:
$[\underline{c}^{(\ell)}_{i,1}\ \ \underline{c}^{(\ell)}_{i,2}\ \ \cdots\ \
\underline{c}^{(\ell)}_{i,\nu+s}]=[\underline{g}^{(\ell)}_{i,1}\ \
\underline{g}^{(\ell)}_{i,2}\ \ \cdots\ \
\underline{g}^{(\ell)}_{i,\nu}]\mathbf{G}.$

// Transmission

5 Edge node-$i$ transmits the coded fragment $\underline{c}^{(\ell)}_{i,j}$ to
helper node $\mathcal{H}_{\ell,j}$ $\forall j\in[\nu+s]$.

Algorithm 1 Algorithm used by edge node $E_{i}$ to transmit coded gradient
symbols

####  II-A1 An Example

An example for the encoding process up to the second step is given in Fig. 3
for system parameters $(n_{h}=4,s=1)$. The code parameter $\nu$ can take
values in $\\{1,2,3\\}$, and the process is explained for each $\nu$. For each
$\nu$, a systematic code $\mathcal{C}_{\nu}$ is considered by the edge nodes.
The symbols $p_{i,1}^{(\ell)},\ell\in[L]$ are the parity symbols generated by
the code. The third step is omitted as it just involves stacking all non-empty
cells of the array.

$\hskip 28.45274pt(\nu=1)$ | $1$ | $2$ | $3$ | $4$
---|---|---|---|---
$[g_{i,1}^{(1)}]$ | $g_{i,1}^{(1)}$ | $p_{i,1}^{(1)}$ |  |
$[g_{i,1}^{(2)}]$ | $g_{i,1}^{(2)}$ |  | $p_{i,1}^{(2)}$ |
$[g_{i,1}^{(3)}]$ $\xrightarrow[]{[2,1]{\ C_{\text{MDS}}}}$ | $g_{i,1}^{(3)}$ |  |  | $p_{i,1}^{(3)}$
$[g_{i,1}^{(4)}]$ |  | $g_{i,1}^{(4)}$ | $p_{i,1}^{(4)}$ |
$[g_{i,1}^{(5)}]$ |  | $g_{i,1}^{(5)}$ |  | $p_{i,1}^{(5)}$
$[g_{i,1}^{(6)}]$ |  |  | $g_{i,1}^{(6)}$ | $p_{i,1}^{(6)}$

$\hskip 28.45274pt(\nu=2)$ | $1$ | $2$ | $3$ | $4$
---|---|---|---|---
$[g_{i,1}^{(1)}\ g_{i,2}^{(1)}]$ | $g_{i,1}^{(1)}$ | $g_{i,2}^{(1)}$ | $p_{i,1}^{(1)}$ |
$[g_{i,1}^{(2)}\ g_{i,2}^{(2)}]$ $\xrightarrow[]{[3,2]{\ C_{\text{MDS}}}}$ | $g_{i,1}^{(2)}$ | $g_{i,2}^{(2)}$ |  | $p_{i,1}^{(2)}$
$[g_{i,1}^{(3)}\ g_{i,2}^{(3)}]$ | $g_{i,1}^{(3)}$ |  | $g_{i,2}^{(3)}$ | $p_{i,1}^{(3)}$
$[g_{i,1}^{(4)}\ g_{i,2}^{(4)}]$ |  | $g_{i,1}^{(4)}$ | $g_{i,2}^{(4)}$ | $p_{i,1}^{(4)}$

$\hskip 28.45274pt(\nu=3)$ | $1$ | $2$ | $3$ | $4$
---|---|---|---|---
$[g_{i,1}^{(1)}\ g_{i,2}^{(1)}\ g_{i,3}^{(1)}]$ $\xrightarrow[]{[4,3]{\ C_{\text{MDS}}}}$ | $g_{i,1}^{(1)}$ | $g_{i,2}^{(1)}$ | $g_{i,3}^{(1)}$ | $p_{i,1}^{(1)}$

Figure 3: The encoding at edge node $E_{i}$ as the parameter $\nu$ varies. In
each matrix, a column represents the helper node to which transmission
happens, and the row represents the layer. Observe that $b=3$ for $\nu\in[2]$
and $b=1$ for $\nu=3$. Here $n_{h}=4$ and $s=1$. Thus,
$\nu\in[n_{h}-s]\triangleq[3]$.

###  II-B Description of ${\cal A}_{\nu}$

The aggregation strategy is tailored for the proposed layered code ${\cal
C}_{\nu}$ and aggregation is performed in each layer.

Suppose an $(n_{e}\times n_{h})$ erasure matrix $\epsilon\in\Omega(s)$ has
occurred, and $\epsilon(i,j)$ denotes the $(i,j)$-th entry of $\epsilon$. Let
${\cal E}_{i}=\\{j\mid\epsilon(i,j)=1\\}\subseteq[n_{h}]$ denote the subset of
helpers that failed to receive transmissions from $E_{i}$. Recall that
$\underline{c}_{i}\in\mathbb{A}^{b\times n_{h}}$ can be viewed as an $(L\times
n_{h})$ array in which each row is called a layer. The $(\ell,j)$-th cell
contains one of the $\underline{c}_{i,l}^{(\ell)}$’s if $j\in{\cal H}_{\ell}$,
or else is empty.

At every helper $H_{j}$, aggregation involves computing partial sums of coded
symbols belonging to the same layer, but coming from different edges. Let us
fix $\ell\in[L]$ with an associated subset ${\cal H}_{\ell}\subseteq[n_{h}]$.
In what follows, we first develop some notation and subsequently explain the
aggregation for layer $\ell$. Set $\alpha={\nu+s\choose s}$, and let ${\cal
S}^{(\ell)}=\\{{\cal S}^{(\ell)}_{1},{\cal S}^{(\ell)}_{2},\ldots,{\cal
S}^{(\ell)}_{\alpha}\\}$ be the collection of $s$-element subsets of ${\cal
H}_{\ell}$. We assume a lexicographic ordering on the set ${\cal S}^{(\ell)}$.
Next, we define a relation among the set of edges as follows; an edge $E_{a}$
is related to $E_{b}$ if ${\cal E}_{a}\cap{\cal H}_{\ell}={\cal
E}_{b}\cap{\cal H}_{\ell}$. By slight abuse of notation, we shall as well say
$a$ is related to $b$ in the same manner. Clearly, it is an equivalence
relation, and it splits $[n_{e}]$ into a partition ${\cal I}^{(\ell)}=\\{{\cal
I}^{(\ell)}_{1},{\cal I}^{(\ell)}_{2},\ldots,{\cal
I}^{(\ell)}_{\Delta^{(\ell)}}\\}$ where it is clear that $\Delta^{(\ell)}\leq
n_{e}$. Finally we define a mapping $\phi:{\cal I}^{(\ell)}\rightarrow{\cal
S}^{(\ell)}$ as:

$\displaystyle\phi({\cal I}^{(\ell)}_{\delta})$ $\displaystyle=$
$\displaystyle\min\Psi({\cal I}^{(\ell)}_{\delta}),$

where $\Psi({\cal I}^{(\ell)}_{\delta})=\\{{\cal S}^{(\ell)}_{r}\mid{\cal
H}_{\ell}\cap{\cal E}_{i}\subseteq{\cal S}^{(\ell)}_{r}\text{ for some
}i\in{\cal I}^{(\ell)}_{\delta}\\}$ is a subset of ${\cal S}^{(\ell)}$. Since
${\cal E}_{a}\cap{\cal H}_{\ell}\subseteq{\cal H}_{\ell}$ and $|{\cal
E}_{a}\cap{\cal H}_{\ell}|\leq|{\cal E}_{a}|\leq s$ for any $a\in[n_{e}]$, the
set $\Psi({\cal I}^{(\ell)}_{\delta})$ is always non-empty. The minimum is
thus well-defined by the lexicographic ordering. Hence, $\phi$ is well-defined
as well. Let us use $\phi({\cal I}^{(\ell)})$ to denote the image of $\phi$ in
${\cal S}^{(\ell)}$ and $\phi^{-1}({\cal S}^{(\ell)}_{a})$ to denote the pre-
image of any ${\cal S}^{(\ell)}_{a}\in\phi({\cal I}^{(\ell)})$. Let us define:

$\displaystyle\beta^{(\ell)}=|\phi({\cal I}^{(\ell)})|$

as the size of the image of $\phi$. Since $|{\cal I}^{(\ell)}|\leq n_{e}$ and
$|{\cal S}^{(\ell)}|=\alpha$, clearly
$\beta^{(\ell)}\leq\min\\{n_{e},\alpha\\}$. Without loss of generality we
enumerate $\phi({\cal I}^{(\ell)})$ as ${\cal S}^{(\ell)}_{1},{\cal
S}^{(\ell)}_{2},\ldots,{\cal S}^{(\ell)}_{\beta^{(\ell)}}$.

We note that ${\cal I}^{(\ell)}_{\delta}$ is a subset of edges whereas ${\cal
S}^{(\ell)}_{a}=\phi({\cal I}^{(\ell)}_{\delta})$ is a subset of helpers. Thus
the mapping $\phi$ associates a set of edges to a set of helpers, and thereby
plays an important role in identifying which helpers should aggregate symbols
from which edges. With all notations in place, we provide the aggregation
algorithm ${\cal A}_{\nu,j}$ employed by $H_{j}$ as a pseudo-code in Alg. 2.
The algorithm generates $\underline{v}_{j}$ to be transmitted as its output,
and the value of variable $m$ at the end of execution is precisely
$m_{j}(\epsilon)$.

1

2Erasure matrix $\epsilon$ is observed. Initialize $\underline{v}_{j}$ as
empty vector, $m=0$.

3for  _$\ell\in 1,2,\ldots L$_ do

4 Compute ${\cal S}^{(\ell)}$, ${\cal I}^{(\ell)}$ and $\phi({\cal
I}^{(\ell)})$

5 Set $\beta^{(\ell)}=|\phi({\cal I}^{(\ell)})|$

6 for  _$a\in 1,2,\ldots,\beta^{(\ell)}$_ do

7

8 if  _$j\in{\cal H}_{\ell}\setminus S^{(\ell)}_{a}$_ then

9 Compute ${\cal I}=\cup_{I\in\phi^{-1}(S^{(\ell)}_{a})}I$

10 $m\leftarrow m+1$

// aggregate symbols from ${\cal I}$

11 Compute $v_{j,m}=\sum_{i\in{\cal I}}\underline{c}^{(\ell)}_{i,j}$

// append $v_{j,m}$ to $\underline{v}_{j}$

12 $\underline{v}_{j}\leftarrow\left[\underline{v}_{j};v_{j,m}\right]$

13

14

Algorithm 2 Strategy ${\cal A}_{\nu,j}$ adopted by $H_{j}$ to generate
aggregated symbols

####  II-B1 An Example

Let $(n_{e}=7,n_{h}=6,s=2)$ and the code has parameter $\nu=2$. Consider layer
$\ell$ that is described in (3).

$\displaystyle\begin{array}[]{|c|c|c|c|c|c|}\hline\cr 1&2&3&4&5&6\\\ \hline\cr
g_{i,1}^{(\ell)}&g_{i,2}^{(\ell)}&p_{i,1}^{(\ell)}&p_{i,2}^{(\ell)}&&\\\
\hline\cr\end{array}$ (3)

Observe that ${\cal H}_{\ell}=\\{1,2,3,4\\}$. Let the erasure matrix
$\epsilon$ be as given in (12).

$\displaystyle\begin{array}[]{c|c|c|c|c|c|c|}\cline{2-7}\cr&1&2&3&4&5&6\\\
\hline\cr E_{1}&0&0&0&0&1&1\\\ \cline{2-7}\cr E_{2}&0&0&0&0&1&1\\\
\cline{2-7}\cr E_{3}&0&0&0&1&1&0\\\ \cline{2-7}\cr E_{4}&0&0&1&1&0&0\\\
\cline{2-7}\cr E_{5}&0&0&1&1&0&0\\\ \cline{2-7}\cr E_{6}&1&1&0&0&0&0\\\
\cline{2-7}\cr E_{7}&1&1&0&0&0&0\\\ \cline{2-7}\cr\end{array}$ (12)

Then the partition of edges ${\cal I}^{(\ell)}$ consists of ${\cal
I}^{(\ell)}_{1}=\\{1,2\\}$, ${\cal I}^{(\ell)}_{2}=\\{3\\}$, ${\cal
I}^{(\ell)}_{3}=\\{4,5\\}$ and ${\cal I}^{(\ell)}_{4}=\\{6,7\\}$. They are
mapped to ${\cal S}^{(\ell)}$, the set of 2-element subsets of ${\cal
H}_{\ell}$ as $\phi({\cal I}^{(\ell)}_{1})=\\{1,2\\}:={\cal S}^{(\ell)}_{1}$,
$\phi({\cal I}^{(\ell)}_{2})=\\{1,4\\}:={\cal S}^{(\ell)}_{2}$, $\phi({\cal
I}^{(\ell)}_{3})=\\{3,4\\}:={\cal S}^{(\ell)}_{3}$ and $\phi({\cal
I}^{(\ell)}_{4})=\\{1,2\\}={\cal S}^{(\ell)}_{1}$. We have $\beta^{(\ell)}=3$.
The aggregation at $H_{1}$ is done by executing ${\cal A}_{\nu,1}$. It can be
seen that Line 6 is true only while picking ${\cal S}^{(\ell)}_{3}=\\{3,4\\}$,
and $\phi^{-1}({\cal S}^{(\ell)}_{3})=\\{\\{4,5\\}\\}$. Therefore, the current
layer $\ell$ appends $c_{4,1}^{(\ell)}+c_{5,1}^{(\ell)}$ to
$\underline{v}_{1}$.

##  III Worst-Case Communication Costs

###  III-A Calculation of $C_{\text{EH}}$

It is straightforward to compute

$\displaystyle C_{\text{EH}}$ $\displaystyle=$
$\displaystyle\frac{n_{h}db}{p}\ =\
\frac{n_{h}}{p}\cdot\frac{p}{\nu{n_{h}\choose\nu+s}}\cdot{n_{h}-1\choose\nu+s-1}$
$\displaystyle=$ $\displaystyle\frac{\nu+s}{\nu}.$

###  III-B Calculation of $C_{\text{HM}}$

Let the scheme be chosen with parameter $\nu$, and an erasure matrix
$\epsilon$ be given. In Alg. 2, at most one symbol is generated inside the
inner for loop at Line 5. Furthermore, if we consider $\\{{\cal A}_{\nu,j}\mid
j\in[n_{h}]\\}$, then the if condition at Line 6 is true for exactly $\nu$ of
the $\mathcal{A}_{\nu,j}$’s, when $\ell$ is kept as a constant. By counting
the number of times Line 8 is executed in all of $\\{{\cal A}_{\nu,j}\mid
j\in[n_{h}]\\}$ in two different ways, we obtain:

$\displaystyle\sum_{j=1}^{n_{h}}{m_{j}(\epsilon)}$ $\displaystyle=$
$\displaystyle\sum_{\ell\in[L]}\nu\beta^{(\ell)}$ $\displaystyle\Rightarrow\ \
\ C_{\text{HM}}(\epsilon)$ $\displaystyle=$
$\displaystyle\frac{d\nu\sum_{\ell\in[L]}\beta^{(\ell)}}{p}\ =\
\frac{1}{L}\sum_{\ell\in[L]}\beta^{(\ell)},$ (13)

since $d=p/L\nu$. It may be noted that $\beta^{(\ell)}$ depends on the erasure
matrix $\epsilon$ though it is not made explicit in its notation. The next
lemma estimates the worst-case quantity $C_{\text{HM}}$.

######  Lemma 1.

Let $(p,n_{e},n_{h},s)$ be given. For a layered coding scheme with parameter
$\nu$,

$\displaystyle C_{\text{HM}}$ $\displaystyle\leq$
$\displaystyle\min\left\\{n_{e},{\nu+s\choose s}\right\\}.$ (14)

###### Proof.

In Sec. II-B, it is established that
$\beta^{(\ell)}\leq\min\left\\{n_{e},{\nu+s\choose s}\right\\}$ for any
$\ell$, independent of the erasure matrix $\epsilon$. Substituting in (13),
the bound follows. ∎

In the following, we will argue that the bound in (14) is indeed tight when
there is a sufficiently large number of edges. Assume $n_{e}\geq{n_{h}\choose
s}$. Consider the erasure matrix $\epsilon^{*}$ in which every possible
erasure pattern occurs in at least one edge. Then for every layer $\ell$,
there is at least an edge $i$ for which ${\cal H}_{\ell}\cap{\cal E}_{i}={\cal
E}_{i}={\cal S}^{(\ell)}_{r}$ for every $r\in[\alpha]$. This implies that
$\phi$ is an onto function and as a result,
$\beta^{(\ell)}=\alpha={\nu+s\choose s}$ for the erasure matrix
$\epsilon^{*}$. Substituting this in (13) and by Lemma 1, we have the
following theorem.

######  Theorem 2.

Let $(p,n_{e},n_{h},s)$ be given. Let $\nu\in\\{1,2,\ldots,n_{h}-s\\}$. If
$n_{e}\geq{n_{h}\choose s}$, then for a layered coding scheme with parameter
$\nu$,

$\displaystyle C_{\text{HM}}$ $\displaystyle=$ $\displaystyle{\nu+s\choose
s}.$ (15)

For $\nu=1$, our client code is equivalent to that of the ARC scheme proposed
in [10] and achieves $C_{\text{EH}}=s+1$. On the other end, when
$\nu=n_{h}-s$, it reduces to that of the AMC scheme and achieves
$C_{\text{EH}}=\frac{n_{h}}{n_{h}-s}$. In addition, when the parameter $\nu$
is varied over $[n_{h}-s]$, we achieve a graceful transition from the ARC
scheme to the AMC scheme. For instance, we illustrate this transition in Fig.
2 when $(n_{e}=50,n_{h}=10,s=2)$.

## References

  * [1] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-Efficient Learning of Deep Networks from Decentralized Data,” in _Proc. International Conference on Artificial Intelligence and Statistics (AISTATS)_ , vol. 108, 2017, pp. 1273–1282.
  * [2] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated Learning: Challenges, Methods, and Future Directions,” _IEEE Signal Processing Magazine_ , vol. 37, no. 3, pp. 50–60, 2020.
  * [3] A. Reisizadeh, A. Mokhtari, H. Hassani, A. Jadbabaie, and R. Pedarsani, “FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization,” in _Proc. International Conference on Artificial Intelligence and Statistics (AISTATS)_ , vol. 108, 2020, pp. 2021–2031.
  * [4] L. Zhao, Q. Wang, Q. Zou, Y. Zhang, and Y. Chen, “Privacy-Preserving Collaborative Deep Learning With Unreliable Participants,” _IEEE Transactions on Information Forensics and Security_ , vol. 15, pp. 1486–1500, 2020.
  * [5] R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient Coding: Avoiding Stragglers in Distributed Learning,” in _Proc. International Conference on Machine Learning (ICML)_ , vol. 70, 2017, pp. 3368–3376.
  * [6] M. Ye and E. Abbe, “Communication-Computation Efficient Gradient Coding,” in _Proc. International Conference on Machine Learning (ICML)_ , vol. 80, 2018, pp. 5610–5619.
  * [7] S. Li, S. M. M. Kalan, Q. Yu, M. Soltanolkotabi, and A. S. Avestimehr, “Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding,” _CoRR_ , vol. abs/1805.09934, 2018.
  * [8] A. Reisizadeh, S. Prakash, R. Pedarsani, and A. S. Avestimehr, “Tree Gradient Coding,” in _Proc. IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 2808–2812.
  * [9] M. N. Krishnan, E. Hosseini, and A. Khisti, “Sequential Gradient Coding for Packet-Loss Networks,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 3, pp. 919–930, 2021.
  * [10] S. Prakash, A. Reisizadeh, R. Pedarsani, and A. S. Avestimehr, “Hierarchical Coded Gradient Aggregation for Learning at the Edge,” in _Proc. IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 2616–2621.
  * [11] L. Liu, J. Zhang, S. Song, and K. B. Letaief, “Client-Edge-Cloud Hierarchical Federated Learning,” in _Proc. IEEE International Conference on Communications (ICC)_ , 2020, pp. 1–6.
  * [12] B. Sasidharan and A. Thomas, “Coded Gradient Aggregation: A Tradeoff Between Communication Costs at Edge Nodes and at Helper Nodes,” _IEEE Journal on Selected Areas in Communications_ , vol. 40, no. 3, pp. 761–772, 2022.
  * [13] C. Huang, M. Chen, and J. Li, “Pyramid Codes: Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems,” in _Proc. IEEE International Symposium on Network Computing and Applications (NCA)_ , 2007, pp. 79–86.
  * [14] M. Blaum, J. Bruck, and A. Vardy, “MDS array codes with independent parity symbols,” _IEEE Transactions on Information Theory_ , vol. 42, no. 2, pp. 529–542, 1996.
  * [15] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” _IEEE Transactions on Information Theory_ , vol. 56, no. 9, pp. 4539–4551, 2010.
  * [16] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic, “QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding,” in _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 30, 2017, pp. 1709–1720.
  * [17] J. Acharya, C. De Sa, D. Foster, and K. Sridharan, “Distributed Learning with Sublinear Communication,” in _Proc. International Conference on Machine Learning (ICML)_ , vol. 97, 2019, pp. 40–50.
  * [18] N. Shlezinger, M. Chen, Y. C. Eldar, H. V. Poor, and S. Cui, “Federated Learning with Quantization Constraints,” in _Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020, pp. 8851–8855.
  * [19] C. Tian, B. Sasidharan, V. Aggarwal, V. A. Vaishampayan, and P. V. Kumar, “Layered Exact-Repair Regenerating Codes via Embedded Error Correction and Block Designs,” _IEEE Transactions on Information Theory_ , vol. 61, no. 4, pp. 1933–1947, 2015.
  * [20] B. Sasidharan, N. Prakash, M. N. Krishnan, M. Vajha, K. Senthoor, and P. V. Kumar, “Outer bounds on the storage-repair bandwidth trade-off of exact-repair regenerating codes,” _International Journal of Information and Coding Theory_ , vol. 3, no. 4, pp. 255–298, 2016.