# Privacy-Aware Compression for Federated Data Analysis

Kamalika Chaudhuri*  Meta AI, USA. *Equal contribution.  Chuan Guo  Meta AI,
USA. *Equal contribution.  Mike Rabbat  Meta AI, USA. *Equal contribution.

###### Abstract

Federated data analytics is a framework for distributed data analysis where a
server compiles noisy responses from a group of distributed low-bandwidth user
devices to estimate aggregate statistics. Two major challenges in this
framework are privacy, since user data is often sensitive, and compression,
since the user devices have low network bandwidth. Prior work has addressed
these challenges separately by combining standard compression algorithms with
known privacy mechanisms. In this work, we take a holistic look at the problem
and design a family of privacy-aware compression mechanisms that work for any
given communication budget. We first propose a mechanism for transmitting a
single real number that has optimal variance under certain conditions. We then
show how to extend it to metric differential privacy for location privacy use-
cases, as well as vectors, for application to federated learning. Our
experiments illustrate that our mechanism can lead to better utility vs.
compression trade-offs for the same privacy loss in a number of settings.

##  1 Introduction

Federated data analytics is a framework for distributed data analysis and
machine learning that is widely applicable to use-cases involving continuous
data collection from a large number of devices. Here, a central server
receives responses from a large number of distributed clients, and aggregates
them to compute a global statistic or a machine learning model. An example is
training and fine-tuning a speech-to-text model for a digital assistant; here
a central server has a speech-to-text model, which is continuously updated
based on feedback from client devices about the quality of predictions on
their local data. Another example is maintaining real-time traffic statistics
in a city for ride-share demand prediction; here, a central server located at
the ride-share company collects and aggregates location data from a large
number of user devices.

Most applications of federated data analysis involve two major challenges –
privacy and compression. Since typical use-cases involve personal data from
users, it is important to maintain their privacy. This is usually achieved by
applying a local differentially private (LDP) algorithm (Duchi et al., 2013;
Kasiviswanathan et al., 2011) on the raw inputs at the client device so that
only sanitized data is transmitted to the server. Additionally, since the
clients frequently have low-bandwidth high-latency uplinks, it is also
important to ensure that they communicate as few bits to the server as
possible. Most prior work in this area (Girgis et al., 2021; Kairouz et al.,
2021; Agarwal et al., 2021) addressed these two challenges separately – first,
a standard LDP algorithm is used to sanitize the client responses, and then
standard compression procedures are used to compress them before transmission.
However, this leads to a loss in accuracy of the client responses, ultimately
leading to a loss in estimation or learning accuracy at the server. Moreover,
each of these methods requires a very specific communication budget and is not
readily adapted to other budgets.

In this work, we take a closer look at the problem and propose designing the
privacy mechanism in conjunction with the compression procedure. To this end,
we propose a formal property called asymptotic consistency that any private
federated data analysis mechanism should possess. Asymptotic consistency
requires that the aggregate statistics computed by the server converge to the
non-private aggregate statistics as the number of clients grows. If the server
averages the client responses, then a sufficient condition for asymptotic
consistency is that the clients send an unbiased estimate of their input.
Perhaps surprisingly, many existing mechanisms are not unbiased, and thus not
asymptotically consistent.

We first consider designing such unbiased mechanisms that, given any
communication budget $b$, transmit a continuous scalar value that lies in the
interval $[0,1]$ with local differential privacy and no public randomness. We
observe that many existing methods, such as truncated Gaussian, lead to biased
solutions and asymptotically inconsistent outcomes if the inputs lie close to
an end-point of the truncation interval. Motivated by this, we show how to
convert two existing local differentially private mechanisms for transmitting
categorical values – bit-wise randomized response (Warner, 1965) and
generalized randomized response – to unbiased solutions.

We then propose a novel mechanism, the Minimum Variance Unbiased (MVU)
mechanism, that given $b$ bits of communication, exploits the ordinal nature
of the inputs to provide a better privacy-accuracy trade-off. We show that if
the input is drawn uniformly from the set $\\{0,1/(2^{b}-1),\ldots,1\\}$, then
the MVU mechanism has minimum variance among all mechanisms that satisfy the
local differential privacy constraints. We show how to adapt this mechanism to
metric differential privacy (Andrés et al., 2013) for location privacy
applications. To adapt it to differentially private SGD (DP-SGD; Abadi et al.
(2016)), we then show how to extend it to vectors within an $L_{p}$-ball, and
establish tight privacy composition guarantees.

Finally, we investigate the empirical performance of the MVU mechanism in two
concrete use-cases: distributed mean estimation and private federated
learning. In each case, we compare our method with several existing baselines,
and show that our mechanism can achieve better utility for the same privacy
guarantees. In particular, we show that the MVU mechanism can match the
performance of specially-designed gradient compression schemes such as
stochastic signSGD (Jin et al., 2020) for DP-SGD training of neural networks
at the same communication budget.

##  2 Preliminaries

In private federated data analysis, a central server calculates aggregate
statistics based on sensitive inputs from $n$ clients. The statistics might be
as simple as the prevalence of some event, or as complicated as a gradient to
a large neural network. To preserve privacy, the clients transmit a sanitized
version of their input to the server. Two popular privacy notions used for
sanitization are local differential privacy (Duchi et al., 2013;
Kasiviswanathan et al., 2011) and metric differential privacy (Andrés et al.,
2013).

###  2.1 Privacy Definitions

######  Definition 1.

A randomized mechanism $\mathcal{M}$ with domain
$\operatorname*{dom}(\mathcal{M})$ and range
$\operatorname*{range}(\mathcal{M})$ is said to be $\epsilon$-local
differentially private (LDP) if for all pairs $x$ and $x^{\prime}$ in the
domain of $\mathcal{M}$ and any
$S\subseteq\operatorname*{range}(\mathcal{M})$, we have that:

$\Pr(\mathcal{M}(x)\in S)\leq e^{\epsilon}\Pr(\mathcal{M}(x^{\prime})\in S).$

Here $\epsilon$ is a privacy parameter where lower $\epsilon$ implies better
privacy. The LDP mechanism $\mathcal{M}$ is run on the client side, and the
result is transmitted to the server. We assume that the clients and the server
do not share any randomness. It might appear that a local DP requirement
implies that a client’s response contains very little useful information.
While each individual response may be highly noisy, the server is still able
to obtain a fairly accurate estimate of an _aggregate property_ if there are
enough clients. Thus, the challenge in private federated data analysis is to
design protocols — privacy mechanisms for clients and aggregation algorithms
for servers — so that client privacy is preserved, and the server can obtain
an accurate estimate of the desired statistic.

A related definition is metric differential privacy (metric-DP)
(Chatzikokolakis et al., 2013), which is also known as geo-
indistinguishability (Andrés et al., 2013) and is commonly used to quantify
location privacy.

######  Definition 2.

A randomized mechanism $\mathcal{M}$ with domain
$\operatorname*{dom}(\mathcal{M})$ and range
$\operatorname*{range}(\mathcal{M})$ is said to be $\epsilon$-metric DP with
respect to a metric $d$ if for all pairs $x$ and $x^{\prime}$ in the domain of
$\mathcal{M}$ and any $S\subseteq\operatorname*{range}(\mathcal{M})$, we have
that:

$\Pr(\mathcal{M}(x)\in S)\leq e^{\epsilon
d(x,x^{\prime})}\Pr(\mathcal{M}(x^{\prime})\in S).$

Metric DP offers granular privacy that is quantified by the metric $d$ –
inputs $x$ and $x^{\prime}$ that are close in $d$ are indistinguishable, while
those that are far apart in $d$ are less so.

###  2.2 Problem Statement

In addition to balancing privacy and accuracy, a bottleneck of federated
analytics is communication since client devices typically have limited network
bandwidth. Thus, the goal is to achieve privacy and accuracy along with a
limited amount of communication between clients and servers. We formalize this
problem as follows.

######  Problem 3.

Suppose we have $n$ clients with sensitive data $x_{1},\ldots,x_{n}$ where
each $x_{i}$ lies in a domain $\mathcal{X}$, and a central server $S$ seeks to
approximate an aggregate statistic $\mathcal{T}_{n}$. Our goal is to design
two algorithms, a client-side mechanism $\mathcal{M}$ and a server-side
aggregation procedure $\mathcal{A}_{n}$, such that the following conditions
hold:

  1. 1.

$\mathcal{M}$ is $\epsilon$-local DP (or $\epsilon$-metric DP).

  2. 2.

The output of $\mathcal{M}$ can be encoded in $b$ bits.

  3. 3.

$\mathcal{A}_{n}(\mathcal{M}(x_{1}),\ldots,\mathcal{M}(x_{n}))$ is a good
approximation to $\mathcal{T}_{n}(x_{1},\ldots,x_{n})$.

Prior works addressed the communication challenge by making the clients use a
standard local DP mechanism followed by a standard quantization process. We
develop methods where both mechanisms are designed together so as to obtain
high accuracy at the server end.

###  2.3 Asymptotic Consistency

We posit that any good federated analytics solution
$(\mathcal{M},\mathcal{A}_{n})$ where $\mathcal{M}$ is a client mechanism and
$\mathcal{A}_{n}$ is the server-side aggregation procedure should have an
asymptotic consistency property. Loosely speaking, this property ensures that
the server can approximate the target statistic $\mathcal{T}_{n}$ arbitrarily
well with clients. Formally,

######  Definition 4.

We say that a private federated analytics protocol is asymptotically
consistent if the output of the server’s aggregation algorithm
$\mathcal{A}_{n}(\mathcal{M}(x_{1}),\ldots,\mathcal{M}(x_{n}))$ approaches the
target statistic $\mathcal{T}_{n}(x_{1},\ldots,x_{n})$ as
$n\rightarrow\infty$. In other words, for any $\alpha,\delta>0$, there exists
an $n_{0}$ such that for all $n\geq n_{0}$, we have:

$\Pr(|\mathcal{A}_{n}(\mathcal{M}(x_{1}),\ldots,\mathcal{M}(x_{n}))-\mathcal{T}_{n}(x_{1},\ldots,x_{n})|\geq\alpha)\leq\delta$

While the server can use any aggregation protocol $\mathcal{A}_{n}$, the most
common is a simple averaging of the client responses –
$\mathcal{A}_{n}(\mathcal{M}(x_{1}),\ldots,\mathcal{M}(x_{n}))=\frac{1}{n}\sum_{i}\mathcal{M}(x_{i})$.
It is easy to show the following lemma.

######  Lemma 5.

If $\mathcal{M}(x)$ is unbiased for all $x$ and has bounded variance, and if
$\mathcal{A}_{n}$ computes the average of the client responses, then the
federated analytics solution is asymptotically consistent.

While asymptotic consistency may seem basic, it is surprisingly not satisfied
by a number of simple solutions. An example is when $\mathcal{M}(x)$ is a
Gaussian mechanism whose output is truncated to an interval $[a,b]$. In this
case, if $x_{i}=a$ for all $i$, the truncated Gaussian mechanism will be
biased with $\mathbb{E}[\mathcal{M}(x_{i})]>x_{i}$, and consequently the
server’s aggregate will not approach $a$ for any number of clients.

Some of the recently proposed solutions for federated learning are also not
guaranteed to be asymptotically consistent. Examples include the truncated
Discrete Gaussian mechanism (Canonne et al., 2020; Kairouz et al., 2021) as
well as the Skellam mechanism (Agarwal et al., 2021). While these mechanisms
are unbiased if the range is unbounded and there are no communication
constraints, their results do become biased after truncation.

###  2.4 Compression Tool: Dithering

A core component of our proposed mechanisms is dithering – a popular approach
to quantization with a long history of use in communications (Schuchman, 1964;
Gray and Stockham, 1993), signal processing (Lipshitz et al., 1992), and more
recently for communication-efficient distributed learning (Alistarh et al.,
2017; Shlezinger et al., 2020). Suppose our goal is to quantize a scalar value
$x\in[0,1]$ with a communication budget of $b$ bits. We consider the $B=2^{b}$
points $G=\\{0,\frac{1}{B-1},\frac{2}{B-1},\dots,1\\}$ as the quantization
lattice; _i.e._ , the $B$ points uniformly spaced by $\Delta=1/(B-1)$.
Dithering can be seen as a random quantization function
$\operatorname*{Dither}:[0,1]\rightarrow G$ that is unbiased, _i.e._ ,
$\mathbb{E}[\operatorname*{Dither}(x)]=x$.111When the number of grid points
$B$ is clear from the context, we simply write $\operatorname*{Dither}(x)$ to
simplify notation; otherwise we write $\operatorname*{Dither}_{B}(x)$ to
indicate the value of $B$. Moreover, the distribution of the quantization
errors $\operatorname*{Dither}(x)-x$ can be made independent of the
distribution of $x$.

While there are many forms of dithered quantization (Gray and Stockham, 1993),
we focus on the following. If $x\in[\frac{i}{B-1},\frac{i+1}{B-1})$ where
$0\leq i\leq B-1$, then $\operatorname*{Dither}(x)=\frac{i}{B-1}$ with
probability $(B-1)(\frac{i+1}{B-1}-x)$, and
$\operatorname*{Dither}(x)=\frac{i+1}{B-1}$ with probability
$(B-1)(x-\frac{i}{B-1})$. A simple calculation shows that
$\mathbb{E}[\operatorname*{Dither}(x)]=x$ and moreover that the variance is
bounded above by
$\mathbb{E}[(\operatorname*{Dither}(x)-x)^{2}]\leq\Delta^{2}/4$. This
procedure is equivalent to the _non-subtractive_ dithering scheme
$\operatorname*{Dither}(x)=\min_{q\in G}|q-(x-U)|$, where $U$ is uniformly
distributed over the interval $[-\Delta/2,\Delta/2]$; see, e.g., (Aysal et
al., 2008, Lemma 2).

##  3 Scalar Mechanisms

We consider Problem 3 when the input $x_{i}$ is a scalar in the interval
$[0,1]$, and the statistic222To simplify notation, we drop the subscript $n$
from statistics $\mathcal{T}_{n}$ and aggregation functions $\mathcal{A}_{n}$,
when the number of clients $n$ is clear from the context. $\mathcal{T}$ is the
average $\frac{1}{n}\sum_{i=1}^{n}x_{i}$. Our server side aggregation protocol
will also output an average of the client responses. Our goal now is to design
a client-side mechanism $\mathcal{M}$ that is $\epsilon$-local DP, unbiased,
and can be encoded in $b$ bits.

#### Notation.

The inputs to our client-side mechanism $\mathcal{M}$ are: a continuous value
$x\in[0,1]$, a privacy parameter $\epsilon$ and a communication budget $b$.
The output is a number $i\in\\{0,\ldots,B-1\\}$ where $B=2^{b}$, represented
as a sequence of $b$ bits. Additionally, we have an alphabet
$A=\\{a_{0},\ldots,a_{B-1}\\}$ shared between the clients and server; a number
$i$ transmitted by a client is decoded as the letter $a_{i}$ in $A$. The
purpose of $A$ is to ensure unbiasedness.

###  3.1 Strategy Overview

Algorithm 1 Strategy for privacy-aware compression

1: Input: $x\in[0,1]$, privacy budget $\epsilon$, communication budget
$b=b_{\text{out}}$, input bit-width $b_{\text{in}}$.

2: Offline phase:

3: Let $B_{\text{out}}=2^{b},B_{\text{in}}=2^{b_{\text{in}}}$.

4: Construct sampling probability matrix $P\in\mathbb{R}^{B_{\text{in}}\times
B_{\text{out}}}$ and output alphabet
$A=\\{a_{0},\ldots,a_{B_{\text{out}}-1}\\}$ to satisfy $\epsilon$-DP and
unbiasedness constraints.

5: Online phase:

6:
$i=(B_{\text{in}}-1)\cdot\operatorname*{Dither}(x)\in\\{0,1,\ldots,B_{\text{in}}-1\\}$.

7: Draw $j\in\\{0,\ldots,B_{\text{out}}-1\\}$ from the categorical
distribution defined by probability vector $P_{i}$.

8: Return $a_{j}$.

Our privacy-aware compression mechanism operates in two phases. In the offline
phase, it selects an input bit-width value $b_{\text{in}}$ and pre-computes an
output alphabet $A$ and a sampling probability matrix
$P\in\mathbb{R}^{B_{\text{in}}\times B_{\text{out}}}$, where
$B_{\text{out}}=2^{b},B_{\text{in}}=2^{b_{\text{in}}}$. Both $P$ and $A$ are
shared with the server and all clients. In the online phase, the client-side
mechanism $\mathcal{M}$ first uses dithering to round an input $x\in[0,1]$ to
the grid $\\{0,\frac{1}{B_{\text{in}}-1},\ldots,1\\}$ while maintaining
unbiasedness, and then draws an index $j$ from the categorical distribution
defined by the probability vector $P_{i}$, where
$i=(B_{\text{in}}-1)\cdot\operatorname*{Dither}(x)$. The client then sends
$a_{j}$ to the server. Algorithm 1 summarizes the procedure in pseudo-code.
Note that the strategy generalizes to any bounded input range by scaling $x$
appropriately.

In order for $\mathcal{M}$ to satisfy $\epsilon$-DP and unbiasedness, we must
impose the following constraints for the sampling probability matrix
$P=[p_{i,j}]$ and output alphabet $A=\\{a_{j}\\}_{j=0}^{B_{\text{out}}-1}$:

Row-stochasticity:
$\displaystyle\quad\sum_{j=0}^{B_{\text{out}}-1}p_{i,j}=1\quad\forall i$ (1a)
Non-negativity: $\displaystyle\quad p_{i,j}\geq 0\quad\forall i,j$ (1b)
$\epsilon$-DP: $\displaystyle\quad p_{i^{\prime},j}e^{-\epsilon}\leq
p_{i,j}\leq p_{i^{\prime},j}e^{\epsilon}\quad\forall i\neq i^{\prime}$ (1c)
Unbiasedness:
$\displaystyle\quad\sum_{j=0}^{B_{\text{out}}-1}a_{j}p_{i,j}=\frac{i}{B_{\text{in}}-1}\quad\forall
i.$ (1d)

Conditions (1a) and (1b) ensure that $P$ is a probability matrix. Condition
(1c) ensures $\epsilon$-DP, while condition (1d) ensures unbiasedness. Note
that these constraints only define the feasibility conditions for $P$ and $A$,
and hence form the basis for a broad class of private mechanisms. In the
following sections, we show that two variants of an existing local DP
mechanism Randomized Response Warner (1965) – bit-wise Randomized Response and
generalized Randomized Response – can be realized as special cases of this
family of mechanisms.

###  3.2 Unbiased Bitwise Randomized Response

Randomized Response (RR) (Warner, 1965) is one of the simplest LDP mechanisms
that sanitizes a single bit. Given a bit $y\in\\{0,1\\}$, the RR mechanism
outputs the $y$ with some probability $p$ and the flipped bit $1-y$ with
probability $1-p$. If $p=\frac{1}{1+e^{-\epsilon}}$, then the mechanism is
$\epsilon$-local DP.

Unbiased Bitwise Randomized Response Mechanism. The RR mechanism does not
directly apply to our task as it is biased and applies to one bit. We obtain
unbiasedness by using the output alphabet
$A=\\{-\frac{1}{e^{\epsilon}-1},\frac{e^{\epsilon}}{e^{\epsilon}-1}\\}$, and
repeat the one-bit mechanism $b$ times on each bit of $x$, with a privacy
budget of $\epsilon/b$ each time. It is not hard to see that unbiased RR with
$b=1$ is a special case of Algorithm 1. For $b>1$, we can construct the
resulting probability matrix $P$ by applying unbiased RR to each bit
independently and similarly obtain the resulting output alphabet $A$.

We prove in Appendix A that Unbiased Bitwise Multiple RR satisfies
$\epsilon$-local DP and is unbiased.

###  3.3 Unbiased Generalized Randomized Response

Generalized Randomized Response is a simple generalization of the one-bit RR
mechanism for sanitizing a categorical value $x\in\\{1,\ldots,K\\}$. The
mechanism transmits $x$ with some probability $p$, and a draw from a uniform
distribution over $\\{1,\ldots,K\\}$ with probability $1-p$. The mechanism
satisfies $\epsilon$-local DP when
$p=\frac{e^{\epsilon}-1}{K+e^{\epsilon}-1}$.

Unbiased Generalized Randomized Response. We can adapt Generalized RR to our
task by dithering the input $x$ to the grid
$\\{0,\frac{1}{B_{\text{out}}-1},\ldots,1\\}$ where
$B_{\text{out}}=2^{b_{\text{out}}}$, and then transmitting the result using
Generalized RR. Alternatively, we can derive the sampling probability matrix
$P=\frac{e^{\epsilon}-1}{B_{\text{out}}+e^{\epsilon}-1}I_{B_{\text{out}}}+\frac{1}{B_{\text{out}}+e^{\epsilon}-1}$,
where $I_{B_{\text{out}}}$ is the identity matrix. However, this leads to a
biased output. To address this, we change the alphabet to
$A=\\{a_{0},a_{1},\ldots,a_{B_{\text{out}}-1}\\}$ such that unbiasedness is
maintained. Specifically, for any $i\in\\{0,\ldots,B_{\text{out}}-1\\}$, we
need to ensure that when the input is $\frac{i}{B_{\text{out}}-1}$, the
expected output is also $\frac{i}{B_{\text{out}}-1}$, which reduces to the
following equation:

$a_{i}\cdot\frac{e^{\epsilon}-1}{B_{\text{out}}+e^{\epsilon}-1}+\sum_{j=0}^{B_{\text{out}}-1}a_{j}\cdot\frac{1}{B_{\text{out}}+e^{\epsilon}-1}=\frac{i}{B_{\text{out}}-1}.$

Writing this down for each $i$ gives $B_{\text{out}}$ linear equations,
solving which will give us the values of $a_{0},\ldots,a_{B_{\text{out}}-1}$.
We establish the privacy and unbiasedness properties of Unbiased Generalized
RR in Appendix A. A similar unbiased adaptation was also considered by Balle
et al. (2019).

Figure 1: Optimized sampling probability matrix $P$ (top row) and output
alphabet $A=\\{a_{0},\ldots,a_{B_{\text{out}}-1}\\}$ (bottom row) of the MVU
mechanism with $b_{\text{in}}=b_{\text{out}}=3$ for $\epsilon=1,3,5,10$. At
$\epsilon=1$, the DP constraint forces entries in each column to be similar,
and the unbiasedness constraint causes the magnitude of $a_{j}$ to be large.
At $\epsilon=10$, the weaker DP constraint allows the optimal $P$ matrix to
become close to the identity matrix and $a_{j}\approx j/(B-1)$.

###  3.4 The MVU Mechanism

A challenge with Unbiased Bitwise RR and Unbiased Generalized RR is that both
algorithms are not intrinsically designed for ordinal or numerical values,
which may result in poor accuracy upon aggregation. We next propose a new
method that improves estimation accuracy by reducing the variance of each
client’s output while retaining unbiasedness and hence asymptotic consistency.

Our proposed method – the _Minimum Variance Unbiased_ (MVU) mechanism –
addresses this problem by directly minimizing the variance of the client’s
output. This is done by solving the following optimization problem:

$\displaystyle\min_{\begin{subarray}{c}p\in[0,1]^{B_{\text{in}}\times
B_{\text{out}}}\\\ a\in\mathbb{R}^{B_{\text{out}}}\end{subarray}}$
$\displaystyle\quad\sum_{i=0}^{B_{\text{in}}-1}\sum_{j=0}^{B_{\text{out}}-1}p_{i,j}\left(\frac{i}{B_{\text{in}}-1}-a_{j}\right)^{2}$
(2) subject to $\displaystyle\quad\text{Conditions }\eqref{eq:row-
stochastic}-\eqref{eq:unbiased}.$

The objective in (2) measures the variance of the output of the mechanism when
the input $i$ is uniformly distributed over the set
$\\{0,\frac{1}{B_{\text{in}}-1},\dots,1\\}$. Conditions (1a)-(1d) ensure that
the MVU mechanism is $\epsilon$-DP and unbiased, hence satisfying requirements
for our task.

Solving the MVU mechanism design problem. We solve (2) using one of two
approaches depending on size of the probability matrix $P$ and $\epsilon$. For
smaller problems and when $\epsilon$ is not too small, we use a trust region
interior-point solver (Conn et al., 2000). As $\epsilon$ approaches $0$, the
problem becomes poorly conditioned and we only approximately solve the problem
by relaxing the unbiasedness constraint (1d). In this case we use an
alternating minimization heuristic where we alternate between fixing the
values $a_{j}$ and solving for $p_{i,j}$, and holding $p_{i,j}$ fixed and
solving for $a_{j}$, while incorporating constraint (1d) as a soft penalty in
the objective. Each of the corresponding subproblems is a quadratic program
and can be solved efficiently. Figure 1 shows examples of the MVU mechanism
for $b_{\text{in}}=b_{\text{out}}=3$ and $\epsilon\in\\{1,3,5,10\\}$ obtained
using the trust region solver.

Relationship between DP and compression. The MVU mechanism highlights an
intriguing connection between DP and compression. Since the mechanism hides
information in the input $x$ by perturbing it with random noise, as
$\epsilon\rightarrow 0$, fewer bits are required to describe the noisy output
$\mathcal{M}(x)$. In the limiting case of $\epsilon=0$, all information is
lost and the output can be described by zero bits. In Appendix B, we
demonstrate this argument concretely by showing that as $\epsilon\rightarrow
0$, the marginal benefit of having a larger communication budget decreases.

##  4 Extensions

We now show how to extend the MVU mechanism to obtain privacy-aware and
accurate compression mechanisms for metric-DP and vector spaces.

###  4.1 Metric DP

In location privacy, client devices send their obscured locations to a central
server for aggregation. Metric DP (Definition 2) is a variation of LDP that
applies to this use-case. We are given a position $x$ and a metric $d$ which
measures how far apart two positions are. Our goal is to output a private
position $x^{\prime}$ so that fine-grained properties of $x$ (such as, exact
address, city block) are hidden, while coarse-grained properties (such as,
city, or zip-code) are preserved.

We show how to adapt the MVU mechanism to metric DP. For simplicity, suppose
that we measure position on the line, so $x\in[0,1]$. We modify Condition (1c)
to instead satisfy the metric DP constraint with respect to the metric $d$:

$p_{i^{\prime},j}e^{-\epsilon
d(i/(B_{\text{in}}-1),i^{\prime}/(B_{\text{in}}-1))}\leq p_{i,j}\leq
p_{i^{\prime},j}e^{\epsilon
d(i/(B_{\text{in}}-1),i^{\prime}/(B_{\text{in}}-1))}.$ (3)

Thus we can get an MVU mechanism for metric DP by solving the modified
optimization problem in (2) and following the same procedure in Algorithm 1.

###  4.2 Extension to Vector Spaces

We next look at extending the MVU mechanism to vector spaces. Specifically, a
client now holds a $d$-dimensional vector $\mathbf{x}$ in a domain
$\mathcal{X}\subseteq\mathbb{R}^{d}$, and its goal is to output an
$\epsilon$-local DP version that can be communicated in $bd$ bits. The domain
$\mathcal{X}$ is typically a unit $L_{p}$-norm ball for $p\geq 1$.

A plausible approach is to apply the scalar MVU mechanism independently for
each coordinate of $\mathbf{x}$. While this will provide the optimal accuracy
for $p=\infty$, for $p<\infty$, the client’s variance will be higher. A second
approach is to extend the MVU mechanism directly to $\mathcal{X}$ by using an
alphabet $A\times A\times\ldots\times A=A^{d}$ and then solving the
corresponding optimization problem (2). Unfortunately this is computationally
intractable even for moderate $d$.

Instead, we show how to obtain a more computationally tractable approximation
when $\mathcal{X}$ is an $L_{p}$-ball. We are motivated by the following
lemma.

######  Lemma 6.

Let $\mathcal{X}$ be the unit $L_{p}$-ball with diameter $\Delta$. Suppose
$\mathcal{M}$ is an $\epsilon$-metric DP scalar mechanism with
$d(y,y^{\prime})=|y-y^{\prime}|^{p}$. Then, the mechanism
$\mathcal{M}_{d}:\mathcal{X}\rightarrow\mathbb{R}^{d}$ that maps $\mathbf{x}$
to the vector
$(\mathcal{M}(\mathbf{x}_{1}),\ldots,\mathcal{M}(\mathbf{x}_{d}))$ is
$\epsilon\Delta^{p}$-local DP. Additionally, if $\mathcal{M}$ is unbiased,
then $\mathcal{M}_{d}$ is unbiased as well.

Lemma 6 suggests the following algorithm: Use the MVU mechanism for
$\epsilon$-metric DP with $d(y,y^{\prime})=|y-y^{\prime}|^{p}$ for each
coordinate, then combine to get an $\epsilon$-local DP solution for vectors
with $L_{p}$-sensitivity $\Delta$. Since
$\|\cdot\|_{\infty}\leq\|\cdot\|_{p}$, each coordinate of $\mathbf{x}$ lies in
a bounded range $[-\Delta,\Delta]$, so we can scale $\mathbf{x}$ by
$\mathbf{x}^{\prime}\leftarrow(\mathbf{x}+\Delta)/2\Delta$ so that all entries
belong to $[0,1]$ and the MVU mechanism can be applied to
$\mathbf{x}^{\prime}$. Note that this scaling operation changes the
$L_{p}$-sensitivity to $1/2$.

This solution is computationally tractable since we only need to solve an
optimization problem for the scalar MVU mechanism – so involving $\approx
B_{\text{out}}^{2}=2^{2b_{\text{out}}}$ variables and constraints (instead of
$\approx 2^{2b_{\text{out}}d}$). We investigate how this mechanism works in
practice in Section 5.

###  4.3 Composition using Rényi-DP

Repeated applications of the MVU mechanism will give an additive sequential
privacy composition guarantee as in standard $\epsilon$-DP. We next show how
to get tighter composition bounds for the MVU mechanism using RDP accounting
as in Mironov (2017).

Suppose that
$\mathbf{x},\mathbf{x}^{\prime}\in\\{0,1/(B_{\text{in}}-1),\ldots,1\\}^{d}$
are quantized $d$-dimensional vectors, and let $Q_{0},Q_{1}$ be the output
distributions of the mechanism $\mathcal{M}$ for inputs
$\mathbf{x},\mathbf{x}^{\prime}$, respectively. By the definition of Rényi
divergence (Rényi, 1961),

$D_{\alpha}(Q_{0}||Q_{1})=\frac{1}{\alpha-1}\sum_{l=1}^{d}\log\sum_{j=0}^{B_{\text{in}}-1}\frac{p_{\mathbf{i}_{l},j}^{\alpha}}{p_{\mathbf{i}_{l}^{\prime},j}^{\alpha-1}},$

where $\mathbf{i},\mathbf{i}^{\prime}\in\\{0,1,\ldots,B_{\text{in}}-1\\}^{d}$
are such that $\mathbf{x}=\mathbf{i}/(B_{\text{in}}-1)$ and
$\mathbf{x}^{\prime}=\mathbf{i}^{\prime}/(B_{\text{in}}-1)$. Let $D^{\alpha}$
denote the $B_{\text{in}}\times B_{\text{in}}$ matrix with entries
$D^{\alpha}_{i,i^{\prime}}=\frac{1}{\alpha-1}\log\sum_{j=0}^{B_{\text{in}}-1}p_{i,j}^{\alpha}/p_{i^{\prime},j}^{\alpha-1}$.
Then, computation of the $\alpha$-RDP parameter for $\mathcal{M}$ can be
formulated as the following combinatorial optimization problem:

$\max_{\mathbf{i},\mathbf{i}^{\prime}\in\\{0,1,\ldots,B_{\text{in}}-1\\}^{d}}\>\sum_{l=1}^{d}D^{\alpha}_{\mathbf{i}_{l},\mathbf{i}_{l}^{\prime}}\quad\text{s.t.
}\>\|\mathbf{i}-\mathbf{i}^{\prime}\|_{p}^{p}\leq(B_{\text{in}}-1)^{p}\Delta^{p}.$

This optimization problem is in fact an instance of the _multiple-choice
knapsack problem_ (Sinha and Zoltners, 1979) and admits an efficient linear
program relaxation by converting the integer vectors
$\mathbf{i},\mathbf{i}^{\prime}$ to probability vectors, _i.e._ ,

$\displaystyle\max_{\mathbf{p}\in\mathbb{R}^{d\times B_{\text{in}}\times
B_{\text{in}}}}$ $\displaystyle\quad\sum_{l=1}^{d}\langle
D^{\alpha},\mathbf{p}_{l}\rangle_{F}$ (4) subject to
$\displaystyle\quad\sum_{l=1}^{d}\langle
C,\mathbf{p}_{l}\rangle_{F}\leq(B_{\text{in}}-1)^{p}\Delta^{p}$
$\displaystyle\quad\sum_{i,j}(\mathbf{p}_{l})_{ij}\leq 1\text{ and
}\mathbf{p}_{l}\geq 0\;\forall l,$

where $\langle\cdot,\cdot\rangle_{F}$ denotes Frobenius (vectorized) inner
product and $C$ denotes the distance matrix with entries $C_{ij}=(i-j)^{p}$.
This LP relaxation can still be prohibitively expensive to solve for large $d$
since $\mathbf{p}$ contains $dB_{\text{in}}^{2}$ variables. Fortunately, in
such cases, we can obtain an upper bound via the greedy solution; see Appendix
A for the proof.

######  Lemma 7.

Let $(i^{*},j^{*})=\operatorname*{\arg\,\max}_{i,j}D^{\alpha}_{ij}/C_{ij}$ and
let $d_{0}=(B_{\text{in}}-1)^{p}\Delta^{p}/C_{i^{*}j^{*}}$. Then (4) $\leq
d_{0}D_{i^{*}j^{*}}^{\alpha}$.

To summarize, for composition with RDP accounting at order $\alpha$, we can
either solve the LP relaxation in (4) or compute the greedy solution to obtain
an upper bound for $D_{\alpha}(P||Q)$, and then apply the usual composition
for RDP.

Figure 2: Distributed mean estimation for scalar data with LDP
$\epsilon=1,3,5$. The MVU mechanism with budget $b=1$ recovers the CLDP
mechanism and the two curves coincide, while with $b=3$ MVU attains a low
variance across all input values compared to the baseline mechanisms. See text
for details.

##  5 Experiments

We evaluate the MVU mechanism on two sets of experiments: Distributed mean
estimation and federated learning. Our goal is to demonstrate that MVU can
attain a better privacy-utility trade-off at low communication budgets
compared to other private compression mechanisms. Code to reproduce our
results can be found in the repo
https://github.com/facebookresearch/dp_compression.

###  5.1 Distributed mean estimation

In distributed mean estimation (DME), a set of $n$ clients each holds a
private vector $\mathbf{x}_{i}\in\mathbb{R}^{d}$, and the server would like to
privately estimate the mean
$\bar{\mathbf{x}}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}$.

#### Scalar DME.

We first consider the setting of scalar data, _i.e._ , $d=1$. For a fixed
value $x\in[-1,1]$, we set $\mathbf{x}_{i}=x$ for all $i=1,\ldots,n$ with
$n=100,000$ and then privatize them before taking average. We measure the
squared difference between the private estimate and $\bar{\mathbf{x}}=x$,
which is coincidentally the variance of the mechanism at $x$. The baseline
mechanisms that we evaluate against are (unbiased) Bitwise Randomized Response
(bRR), (unbiased) Generalized Randomized Response (gRR), the communication-
limited local differentially private (CLDP) mechanism (Girgis et al., 2021),
and the Laplace mechanism without any compression. The CLDP mechanism uses a
fixed communication budget of $b=1$, whereas for bRR and gRR we set $b=3$, and
for MVU we set $b=1,3$.

Figure 2 shows the plot of input value $x$ vs. variance of the private
mechanism at $x$. Interestingly, MVU with $b=1$ recovers the CLDP mechanism
for $\epsilon=1,3,5$, while MVU with $b=3$ is consistently the lowest variance
private compression mechanism. For larger $\epsilon$, it is evident that the
variance of both gRR and MVU are comparable or even slightly lower that of the
Laplace mechanism, even when compressing to only $b=3$ bits in their output.

Figure 3: Distributed mean estimation for $n=10,000$ data vectors with
$L_{1}$\- (left) and $L_{2}$-sensitivity (right). Error bars represent
standard deviation across $10$ repeated runs with different private vectors.
Methods that are $(\epsilon,\delta)$-DP use the same value of
$\delta=1/(n+1)$. The MVU mechanism can attain an MSE close to that of the
Laplace and Gaussian mechanisms while compressing the output to only $b=3$
bits per coordinate.

#### Vector DME.

We next look at vector data with $d=128$ and $n=10,000$. We draw the sensitive
vectors from two distinct distributions333We intentionally avoided zero-mean
distributions since some of the private mechanisms converge to the all-zero
vector as $\epsilon\rightarrow 0$.: (i) Uniform at random from $[0,1]^{d}$ and
then normalize to $L_{1}$-norm of 1; and (ii) Uniform over the spherical
sector $\mathbb{S}^{d-1}\cap\mathbb{R}_{\geq 0}^{d}$. In these settings, the
vectors $\mathbf{x}_{i}$ have $L_{1}$\- and $L_{2}$-sensitivity of 1,
respectively.

For baselines, we consider the CLDP mechanism (Girgis et al., 2021), the
Skellam mechanism (Agarwal et al., 2021), the Laplace mechanism (for setting
(i) only), and the Gaussian mechanism (for setting (ii) only). Both the
Skellam and the Gaussian mechanisms are $(\epsilon,\delta)$-DP for $\delta>0$.
For a given $\epsilon>0$, we set $\delta=1/(n+1)$ and choose the noise
parameter $\mu$ for the Skellam mechanism using the optimal RDP conversion,
and the noise parameter $\sigma$ for the Gaussian mechanism using the
analytical conversion in Balle and Wang (2018). For communication budget, we
set $b=3$ for MVU and $b=16$ for Skellam (which requires a large $b$ in order
to prevent truncation error). The CLDP mechanism does not allow flexible
selection of communication budget, and instead outputs a _total_ number of
$\log_{2}(d)+1$ bits for the $L_{1}$-sensitivity setting, and
$b=\log_{2}(d)+1=8$ bits _per coordinate_ for the $L_{2}$-sensitivity setting.
See Appendix B for a more detailed explanation.

Figure 3 shows the mean squared error (MSE) for privately estimating
$\bar{\mathbf{x}}$ across different values of $\epsilon$. In the left plot
corresponding to the $L_{1}$-sensitivity setting, MVU can attain MSE close to
the Laplace mechanism at a greatly reduced $b=3$ bits per coordinate. In
comparison, CLDP and Skellam attain MSE that is more than an order of
magnitude higher than Laplace.

The right plot corresponds to $L_{2}$-sensitivity. Here, the MVU mechanism
(dark green line) is significantly less competitive than the baselines. This
is because the $L_{2}$-metric DP constraint for the MVU mechanism forces rows
of the sampling probability matrix $P$ to be near-identical, hence is near-
singular and does not admit a well-conditioned unbiased solution. To address
this problem, we instead optimize the MVU mechanism to satisfy $L_{1}$-metric
DP and use the Rényi accounting in Section 4.3 to compute its RDP guarantee,
then apply RDP-to-DP conversion to give an $(\epsilon,\delta)$-DP guarantee at
$\delta=\frac{1}{n+1}$. The light green line shows the performance of the
$L_{1}$-metric DP mechanism, which now slightly outperforms both CLDP and
Skellam at a much lower communication budget of $b=3$. These results
demonstrate that the MVU mechanism attains better utility vs. compression
trade-off for vector data as well.

Figure 4: DP-SGD training with Gaussian mechanism, stochastic signSGD and MVU
mechanism on MNIST (left) and CIFAR-10 (right). Each point corresponds to a
single hyperparameter setting, and dashed line shows Pareto frontier of
privacy-utility trade-off. MVU mechanism outperforms signSGD at the same
communication budget of $b=1$.

###  5.2 Private SGD

Federated learning (McMahan et al., 2017) often employs DP to protect the
privacy of the clients’ updates. We next evaluate the MVU mechanism for this
use case and show that it can serve as a drop-in replacement for the Gaussian
mechanism for FL protocols, providing similar DP guarantees for the client
update while reducing communication.

In detail, for MNIST and CIFAR-10 (Krizhevsky et al., 2009), we train a linear
classifier on top of features extracted by a scattering network (Oyallon and
Mallat, 2015) similar to the one used in Tramer and Boneh (2020); see Appendix
B for details. The base private learning algorithm is DP-SGD with Gaussian
gradient perturbation (Abadi et al., 2016) and Rényi-DP accounting. The
private compression baselines are the MVU mechanism with budget $b=1$ and
stochastic signSGD (Jin et al., 2020) – a specialized private gradient
compression scheme for federated SGD that applies the Gaussian mechanism and
outputs its coordinate-wise sign. Similar to the distributed mean estimation
experiment with $L_{2}$-sensitivity, we optimize the MVU mechanism to satisfy
$L_{1}$-metric DP and then compute its Rényi privacy guarantee as in Section
4.3.

Figure 4 shows the privacy-utility trade-off curves. We sweep over a grid of
hyperparameters (see Appendix B for details) for each mechanism and plot the
resulting $\epsilon$ and test accuracy as a point in the scatter plot. The
dashed line is the Pareto frontier of optimal privacy-utility trade-off. The
result shows that MVU mechanism outperforms signSGD—a specially-designed
gradient compression mechanism for federated learning—at nearly all privacy
budgets with the same communication cost of _one bit per coordinate_. We
include an additional result for a small convolutional network in Appendix B,
where we observe similar findings.

##  6 Related Work

Federated data analysis with local DP is now a standard solution for analyzing
sensitive data held by many user devices. A body of work (Erlingsson et al.,
2014; Kairouz et al., 2016; Acharya et al., 2019) provides methods for
analytics over categorical data. The main methods here are Randomized Response
(Warner, 1965), RAPPOR (Erlingsson et al., 2014) and the Hadamard Mechanism
(Acharya et al., 2019). Chen et al. (2020) shows that the Hadamard Mechanism
uses near-optimal communication for categorical data.

In work on federated statistics or learning for real-valued data, Cormode and
Markov (2021) provides asymptotically consistent algorithms for transmitting
scalars. They propose to first sample one or a subset of indices of bits in
the fixed-point representation of the input, and then apply randomized
response independently to each of these bits. Girgis et al. (2020) provides
mechanisms for distributed mean estimation from vectors inside unit $L_{p}$
balls. Unlike our method, which provides a near-optimal solution under any
given communication budget, their methods use specific communication budgets
and are not readily generalizable to any budget $b$. Finally, Amiri et al.
(2021) propose to obtain a quantized DP mechanism by composing subtractive
dithering with the Gaussian mechanism, and doing privacy accounting that
factors in both. In contrast, we simply use (non-subtractive) dithering to
initially obtain a fixed-point representation, and then design a mechanism to
quantize and provide DP.

A large body of work focuses on federated optimization methods with compressed
communication (Konečnỳ et al., 2016; Horváth et al., 2019; Das et al., 2020;
Haddadpour et al., 2021; Gorbunov et al., 2021). While most propose biased
compression methods (e.g., top-$k$ sparsification), such approaches require
the use of error feedback to avoid compounding errors (Seide et al., 2014;
Stich and Karimireddy, 2020). However, error feedback is inherently
incompatible with DP (Jin et al., 2020), unlike our MVU mechanism.

##  7 Conclusion and Limitations

We introduce the MVU framework to jointly design scalar compression and DP
mechanisms, and extend it to the vector and metric-DP settings. We show that
the MVU mechanism attains a better utility-compression trade-off for both
scalar and vector mean estimation compared to other approaches in the
literature. Our work shows that co-designing the compression and privacy-
preserving components can lead to more efficient differentially private
mechanisms for federated data analysis.

#### Limitations.

Our work presents several opportunities for further improvement. 1. For vector
dithering, Appendix B shows that the input vector’s norm can increase by a
small additive factor. Our current solution of conditional random dithering
introduces a small but non-negligible bias. Future work on unbiased norm-
preserving vector dithering may be able to alleviate this issue. 2. Optimizing
the MVU mechanism for large values of the input/output bit width
$b_{\text{in}}$ and $b_{\text{out}}$ can be prohibitively expensive, even with
the alternating minimization heuristic. In order to scale the solution to
higher-dimensional vectors, further effort in designing more efficient
solutions for the MVU mechanism may be needed. 3. While our work focuses on
local differential privacy, it may be possible to combine our approach with
secure aggregation protocols to derive central differential privacy
guarantees. However, since the MVU mechanism is not additive, further analysis
is required to characterize the distribution of the aggregate for our
mechanism, which we leave for future work.

## Acknowledgements

We thank Graham Cormode, Huanyu Zhang, and anonymous reviewers for insightful
comments and suggestions that helped shape our final draft.

## References

  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , pages 308–318, 2016.
  * Acharya et al. (2019) Jayadev Acharya, Ziteng Sun, and Huanyu Zhang.  Hadamard response: Estimating distributions privately, efficiently, and with little communication.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 1120–1129. PMLR, 2019.
  * Agarwal et al. (2021) Naman Agarwal, Peter Kairouz, and Ziyu Liu.  The skellam mechanism for differentially private federated learning.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Alistarh et al. (2017) Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic.  QSGD: Communication-efficient SGD via gradient quantization and encoding.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2017.
  * Amiri et al. (2021) Saba Amiri, Adam Belloum, Sander Klous, and Leon Gommans.  Compressive differentially-private federated learning through universal vector quantization.  In _AAAI Workshop on Privacy-Preserving Artificial Intelligence_ , 2021.
  * Andrés et al. (2013) Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi.  Geo-indistinguishability: Differential privacy for location-based systems.  In _Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security_, pages 901–914, 2013.
  * Aysal et al. (2008) T. Can Aysal, Mark J. Coates, and Michael G. Rabbat.  Distributed average consensus with dithered quantization.  _IEEE Trans. Signal Processing_ , 56(10):4905–4918, Oct. 2008.
  * Balle and Wang (2018) Borja Balle and Yu-Xiang Wang.  Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising.  In _International Conference on Machine Learning_ , pages 394–403. PMLR, 2018.
  * Balle et al. (2019) Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim.  The privacy blanket of the shuffle model.  In _Annual International Cryptology Conference_ , pages 638–667. Springer, 2019.
  * Canonne et al. (2020) Clément L Canonne, Gautam Kamath, and Thomas Steinke.  The discrete gaussian for differential privacy.  _Advances in Neural Information Processing Systems_ , 33:15676–15688, 2020.
  * Chatzikokolakis et al. (2013) Konstantinos Chatzikokolakis, Miguel E Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi.  Broadening the scope of differential privacy using metrics.  In _International Symposium on Privacy Enhancing Technologies Symposium_ , pages 82–102. Springer, 2013.
  * Chen et al. (2020) Wei-Ning Chen, Peter Kairouz, and Ayfer Ozgur.  Breaking the communication-privacy-accuracy trilemma.  _Advances in Neural Information Processing Systems_ , 33:3312–3324, 2020.
  * Conn et al. (2000) Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint.  _Trust Region Methods_.  SIAM, 2000.
  * Cormode and Markov (2021) Graham Cormode and Igor L. Markov.  Bit-efficient numerical aggregation and stronger privacy for trust in federated analytics.  _arXiv preprint arXiv:2108.01521_ , Aug. 2021.
  * Das et al. (2020) Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topcu.  Faster non-convex federated learning via global and local momentum.  _arXiv preprint arXiv:2012.04061_ , 2020.
  * Duchi et al. (2013) John C Duchi, Michael I Jordan, and Martin J Wainwright.  Local privacy and statistical minimax rates.  In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , pages 429–438. IEEE, 2013.
  * Erlingsson et al. (2014) Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova.  Rappor: Randomized aggregatable privacy-preserving ordinal response.  In _Proceedings of the 2014 ACM SIGSAC conference on computer and communications security_ , pages 1054–1067, 2014.
  * Girgis et al. (2021) Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh.  Shuffled model of differential privacy in federated learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2521–2529. PMLR, 2021.
  * Girgis et al. (2020) Antonious M Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh.  Shuffled model of federated learning: Privacy, communication and accuracy trade-offs.  _arXiv preprint arXiv:2008.07180_ , 2020.
  * Gorbunov et al. (2021) Eduard Gorbunov, Konstantin P. Burlachenko, Zhize Li, and Peter Richtarik.  MARINA: Faster non-convex distributed learning with compression.  In _International Conference on Machine Learning_ , pages 3788–3798, 2021.
  * Gray and Stockham (1993) Robert M. Gray and T. G. Stockham.  Dithered quantizers.  _IEEE Trans. Information Theory_ , 39(3):805–812, May 1993.
  * Haddadpour et al. (2021) Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi.  Federated learning with compression: Unified analysis and sharp guarantees.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , pages 2350–2358, 2021.
  * Horváth et al. (2019) Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik.  Stochastic distributed learning with gradient quantization and variance reduction.  _arXiv preprint arXiv:1904.05115_ , 2019.
  * Jin et al. (2020) Richeng Jin, Yufan Huang, Xiaofan He, Huaiyu Dai, and Tianfu Wu.  Stochastic-sign sgd for federated learning with theoretical guarantees.  _arXiv preprint arXiv:2002.10940_ , 2020.
  * Kairouz et al. (2016) Peter Kairouz, Keith Bonawitz, and Daniel Ramage.  Discrete distribution estimation under local privacy.  In _International Conference on Machine Learning_ , pages 2436–2444. PMLR, 2016.
  * Kairouz et al. (2021) Peter Kairouz, Ziyu Liu, and Thomas Steinke.  The distributed discrete gaussian mechanism for federated learning with secure aggregation.  In _International Conference on Machine Learning_ , pages 5201–5212. PMLR, 2021.
  * Kasiviswanathan et al. (2011) Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  _SIAM Journal on Computing_ , 40(3):793–826, 2011\.
  * Konečnỳ et al. (2016) Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon.  Federated learning: Strategies for improving communication efficiency.  _arXiv preprint arXiv:1610.05492_ , 2016.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Lipshitz et al. (1992) Stanley P. Lipshitz, Robert A. Wannamaker, and John Vanderkooy.  Quantization and dither: A theoretical survey.  _Journal of the Audio Engineering Society_ , 40(5):355–375, May 1992.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pages 1273–1282. PMLR, 2017.
  * Mironov (2017) Ilya Mironov.  Rényi differential privacy.  In _2017 IEEE 30th computer security foundations symposium (CSF)_ , pages 263–275. IEEE, 2017.
  * Oyallon and Mallat (2015) Edouard Oyallon and Stéphane Mallat.  Deep roto-translation scattering for object classification.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 2865–2873, 2015.
  * Papernot et al. (2020) Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Ulfar Erlingsson.  Tempered sigmoid activations for deep learning with differential privacy.  _arXiv preprint arXiv:2007.14191_ , page 10, 2020.
  * Rényi (1961) Alfréd Rényi.  On measures of entropy and information.  In _Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics_ , volume 4, pages 547–562. University of California Press, 1961.
  * Schuchman (1964) Leonard Schuchman.  Dither signals and their effect on quantization noise.  _IEEE Trans. Communication Technology_ , 12(4):162–165, Dec. 1964.
  * Seide et al. (2014) Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu.  1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs.  In _Fifteenth Annual Conference of the International Speech Communication Association_ , 2014.
  * Shlezinger et al. (2020) Nir Shlezinger, Mingzhe Chen, Yonina C. Eldar, H. Vincent Poor, and Shuguang Cui.  UVeQFed: Universal vector quantization for federated learning.  _IEEE Trans. Signal Processing_ , 69:500–514, Dec. 2020\.
  * Sinha and Zoltners (1979) Prabhakant Sinha and Andris A Zoltners.  The multiple-choice knapsack problem.  _Operations Research_ , 27(3):503–515, 1979.
  * Stich and Karimireddy (2020) Sebastian U. Stich and Sai Praneeth Karimireddy.  The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication.  _Journal of Machine Learning Research_ , 21(237):1–36, 2020.
  * Tramer and Boneh (2020) Florian Tramer and Dan Boneh.  Differentially private learning needs better features (or much more data).  _arXiv preprint arXiv:2011.11660_ , 2020.
  * Warner (1965) Stanley L Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  _Journal of the American Statistical Association_ , 60(309):63–69, 1965.
  * Wu and He (2018) Yuxin Wu and Kaiming He.  Group normalization.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 3–19, 2018.

##  Appendix A Proofs

###### Proof.

(Of Lemma 5) Observe that in this case:

$\displaystyle\mathbb{E}(\mathcal{A}_{n}(\mathcal{M}(x_{1}),\ldots,\mathcal{M}(x_{n}))$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}(\mathcal{M}(x_{i}))$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}x_{i}=\mathcal{T}(x_{1},\ldots,x_{n}).$

Additionally,

$\mathbb{E}\left[\left(\mathcal{A}_{n}(\mathcal{M}(x_{1}),\ldots,\mathcal{M}(x_{n}))-\frac{1}{n}\sum_{i}x_{i}\right)^{2}\right]=\frac{1}{n}\sum_{i}\mathbb{E}(\mathcal{M}(x_{i})-x_{i})^{2}.$

If $\mathcal{M}$ has bounded variance, then the variance of
$\mathcal{A}_{n}(\mathcal{M}(x_{1}),\ldots,\mathcal{M}(x_{n}))$ diminishes
with $n$. The rest of the lemma follows by an application of the Chebyshev’s
inequality. ∎

###### Proof.

(Of Lemma 6) The proof generalizes the argument that the Laplace mechanism
applied independently to each coordinate is differentially private for vectors
with bounded $L_{1}$-sensitivity. Let $\mathbf{x}\in\mathbb{R}^{d}$ with
$\|\mathbf{x}\|_{p}\leq\Delta$, and let $Q_{0},Q_{1}$ be density functions for
the output distributions of $\mathcal{M}$ with or without the input
$\mathbf{x}$. Then for any output value $\mathbf{z}$:

$\displaystyle\frac{Q_{0}(\mathbf{z})}{Q_{1}(\mathbf{z})}$
$\displaystyle=\prod_{i=1}^{d}\frac{Q_{0}(\mathbf{z}_{i})}{Q_{1}(\mathbf{z}_{i})}$
$\displaystyle\leq\prod_{i=1}^{d}\exp(\epsilon\mathbf{x}_{i}^{p})\quad\text{since
$\mathcal{M}$ is $\epsilon$-metric DP w.r.t.
$d(y,y^{\prime})=|y-y^{\prime}|^{p}$}$
$\displaystyle=\exp\left(\epsilon\sum_{i=1}^{d}\mathbf{x}_{i}^{p}\right)\leq\exp(\epsilon\Delta^{p}).$

The reverse inequality can be derived similarly. Unbiasedness follows from the
fact that $\mathcal{M}$ is unbiased for each dimension $i=1,\ldots,d$. ∎

###### Proof.

(Of Lemma 7) Let $\mathbf{p}$ be a feasible solution for (4). Let $\odot$ and
⊙-1 denote element-wise product and inverse, respectively. Then:

$\displaystyle\sum_{l=1}^{d}\langle D^{\alpha},\mathbf{p}_{l}\rangle_{F}$
$\displaystyle=\sum_{l=1}^{d}\langle C\odot(D^{\alpha}\odot
C^{\odot-1}),\mathbf{p}_{l}\rangle_{F}$
$\displaystyle\leq\sum_{l=1}^{d}\langle(D_{i^{*}j^{*}}^{\alpha}/C_{i^{*}j^{*}})C,\mathbf{p}_{l}\rangle_{F}$
$\displaystyle\leq(D_{i^{*}j^{*}}^{\alpha}/C_{i^{*}j^{*}})(B-1)^{p}\Delta^{p}$
$\displaystyle=d_{0}D_{i^{*}j^{*}}^{\alpha}.$

∎

######  Theorem 8.

Unbiased Bitwise Randomized Response satisfies $\epsilon$-local DP and is
unbiased.

###### Proof.

By standard proofs of the Randomized Response mechanism, transmitting bit $j$
of $z$ is $\epsilon/b$-differentially private. The entire procedure is thus
$\epsilon$-differentially private by composition.

To show unbiasedness, first we observe that $\mathbb{E}[z]=x$. Additionally,
let us write $z=\sum_{j=0}^{b-1}2^{-j}z_{j}$. The transmitted number $t$ is
decoded as $t=\sum_{j=0}^{b-1}2^{-j}t_{j}$. Thus, if
$\mathbb{E}[t_{j}]=z_{j}$, then the entire algorithm is unbiased. Observe
that:

$\displaystyle\mathbb{E}[t_{j}]$
$\displaystyle=a_{0}+(a_{1}-a_{0})\mathbb{E}[y_{j}]$
$\displaystyle=a_{0}+(a_{1}-a_{0})\left(z_{j}\cdot\frac{1}{1+e^{-\epsilon/b}}+(1-z_{j})\cdot\frac{e^{-\epsilon/b}}{1+e^{-\epsilon/b}}\right)$
$\displaystyle=z_{j}.$

where the last step follows from some algebra. The theorem follows by noting
that $\mathbb{E}[z]=x$ from properties of dithering. ∎

######  Theorem 9.

Unbiased Generalized Randomized Response satisfies $\epsilon$-local DP and is
unbiased.

###### Proof.

The proof of privacy follows from standard proofs of the privacy of the
Generalized RR mechanism. To prove unbiasedness, observe that when
$z=\frac{i}{B-1}$, the expected output is $a_{i}$ with probability
$\frac{e^{\epsilon}}{B+e^{\epsilon}-1}$ and $a_{j}$ for $j\neq i$ with
probability $\frac{1}{B+e^{\epsilon}-1}$. From Equation 3.3, this expectation
is also $\frac{i}{B-1}=z$. Additionally, from properties of the dithering
process, $\mathbb{E}[z]=x$. The unbiasedness follows by combining these two. ∎

##  Appendix B Experimental Details

###  B.1 Vector dithering

The optimization program in the MVU Mechanism operates on numbers on a
discrete grid, which are obtained by dithering. In the scalar case, we use the
standard dithering procedure on an $x$ in $[0,1]$. For vectors, we use
coordinate-wise dithering on each coordinate. While this leads to an unbiased
solution, it might increase the norm of the vector. We show below that the
increase in norm is not too high.

######  Lemma 10.

Let $v$ be a vector such that $\|v\|\leq 1$ and $v_{i}\in[-1,1]$ for each
coordinate $i$. Let $v^{\prime}$ be the vector obtained by dithering each
coordinate of $v$ to a grid of size $B$ (so that the difference between any
two grid points is $\Delta=\frac{2}{B-1}$). Then, with probability $\geq
1-\delta$,

$\|v^{\prime}\|^{2}\leq\|v\|^{2}+\sqrt{2}\|v\|\Delta\log(4/\delta)+d\Delta^{2}/4+\sqrt{2d}\Delta\log(4/\delta).$

###### Proof.

Let $\Delta=\frac{2}{B-1}$ be the difference between any two grid points. For
a coordinate $i$, let $v_{i}=\lambda_{i}+a_{i}$ where $\lambda_{i}$ is the
closest grid point that is $\leq v_{i}$ and $a_{i}\geq 0$. We also let
$v^{\prime}_{i}=\lambda_{i}+Z_{i}$; observe that by the dithering algorithm,
$Z_{i}\in\\{0,\Delta\\}$, with $\mathbb{E}[Z_{i}]=a_{i}$. Additionally,
$Var(Z_{i})\leq\frac{\Delta^{2}}{4}$.

Additionally, we observe that
$\|v^{\prime}_{i}\|^{2}=\sum_{i}(\lambda_{i}+Z_{i})^{2}=\sum_{i}\lambda_{i}^{2}+2\lambda_{i}Z_{i}+Z_{i}^{2}$.
By algebra, we get that:

$\|v^{\prime}\|^{2}-\|v\|^{2}=\sum_{i}(Z_{i}^{2}-a_{i}^{2})+\sum_{i}2\lambda_{i}(Z_{i}-a_{i})$

We next bound these terms one by one. To bound the second term, we observe
that $\mathbb{E}[Z_{i}]=a_{i}$ and apply Hoeffding’s inequality. This gives
us:

$\Pr(\sum_{i}\lambda_{i}Z_{i}\geq\sum_{i}\lambda_{i}a_{i}+t)\leq
2e^{-t^{2}/2\sum_{i}\lambda_{i}^{2}\Delta^{2}}$

Plugging in $t=\sqrt{2\sum_{i}\lambda_{i}^{2}}\Delta\log(4/\delta)$ makes the
right hand side $\leq\delta/2$. To bound the first term, we again use a
Hoeffding’s inequality.

$\Pr(\sum_{i}Z_{i}^{2}\geq\sum_{i}\mathbb{E}[Z_{i}^{2}]+t)\leq
2e^{-t^{2}/2d\Delta^{2}}$

Plugging in $t=\sqrt{2d}\Delta\log(4/\delta)$ makes the right hand side
$\leq\delta/4$. Therefore, with probability $\geq 1-\delta$,

$\|v^{\prime}\|^{2}\leq\|v\|^{2}+\sqrt{2\sum_{i}\lambda_{i}^{2}}\Delta\log(4/\delta)+\sum_{i}(\mathbb{E}[Z_{i}]^{2}-a_{i}^{2})+\sqrt{2d}\Delta\log(4/\delta)$

Observe that $\mathbb{E}[Z_{i}^{2}]-a_{i}^{2}=Var(Z_{i})\leq\Delta^{2}/4$;
additionally, $\sum_{i}\lambda_{i}^{2}\leq\|v\|^{2}$. Therefore, we get:

$\|v^{\prime}\|^{2}\leq\|v\|^{2}+\sqrt{2}\|v\|\Delta\log(4/\delta)+d\Delta^{2}/4+\sqrt{2d}\Delta\log(4/\delta)$

The lemma follows. ∎

In practice, given an _a priori_ norm bound $\|v\|\leq R$ for all input
vectors $v$, we estimate a scaling factor $\gamma\in[0,1]$ and apply dithering
to the input $\gamma v$ so that $\|\operatorname*{Dither}(\gamma v)\|\leq R$
with high probability. This can be done by choosing a confidence level
$\delta>0$ and solving for
$\sup\\{\gamma\in[0,1]:\|\operatorname*{Dither}(\gamma v)\|\leq R\text{ w.p.
}\geq 1-\delta\\}$ via binary search. Since dithering is randomized, we can
perform rejection sampling until the condition
$\|\operatorname*{Dither}(\gamma v)\|\leq R$ is met. Doing so incurs a small
bias that is insignificant in practical applications. We leave the design of
more sophisticated vector dithering techniques that simultaneously preserve
unbiasedness and norm bound for future work.

###  B.2 Connection between DP and compression

We highlight an interesting effect on the required communication budget as a
result of adding differentially private noise. Figure 5 shows the optimized
sampling probability matrix $P$ for the MVU mechanism with a fixed input
quantization level $b_{\text{in}}=5$ and various values of $b_{\text{out}}$.
As $b_{\text{out}}$ increases, the overall structure in the matrix $P$ remains
nearly the same but becomes more refined. Moreover, in the bottom right plot,
it is evident that the marginal benefit to MSE becomes lower as
$b_{\text{out}}$ increases. This observation suggests that for a given
$\epsilon$, having more communication budget is eventually not beneficial to
aggregation accuracy since the amount of information in the data becomes
obscured by the DP mechanism and hence requires fewer bits to communicate.

Figure 5: Optimized sampling probability matrix $P$ for the MVU mechanism with
$b_{\text{in}}=5$ and different values of $b_{\text{out}}$. The bottom right
plot shows that the marginal benefit of the communication budget
$b_{\text{out}}$ to MSE becomes lower as $b_{\text{out}}$ increases.

###  B.3 Distributed mean estimation

For the vector distributed mean estimation experiment in Section 5.1, the
different private compression mechanisms used different values of the
communication budget $b$. We justify the choice of $b$ as follows.

####  $L_{1}$-sensitivity setting.

CLDP outputs a _total_ number of $\log_{2}(d)+1=8$ bits, which is lower than
that of both Skellam and MVU and cannot be tuned. Skellam performs truncation
to the range $\\{-2^{b-1},2^{b-1}-1\\}$ after perturbing the quantized input
with Skellam noise, and hence requires a value of $b$ that is large enough to
prevent truncation error. We intentionally afforded Skellam a large budget of
$b=16$ so that truncation error rarely occurs, and show that even in this
setting MVU can outperform Skellam in terms of estimation MSE. For MVU, we
chose $b_{\text{in}}=9$, which is the minimum value required to avoid a large
quantization error, and $b=b_{\text{out}}=3$.

####  $L_{2}$-sensitivity setting.

CLDP uses a communication budget of $b=\log_{2}(d)+1=8$ _per coordinate_ and
is not tunable. We used the same $b=16$ budget for Skellam as in the
$L_{1}$-sensitivity setting. For MVU, we chose $b_{\text{in}}=5$ and
$b=b_{\text{out}}=3$ for both the $L_{1}$\- and $L_{2}$-metric DP versions,
which results in a communication budget that is lower than both CLDP and
Skellam. For the $L_{1}$-metric DP version, we found that optimizing MVU to
satisfy $(\epsilon/2)$-metric DP with respect to the $L_{1}$ metric results in
an $(\epsilon^{\prime},\delta)$-DP mechanism with
$\epsilon^{\prime}\approx\epsilon$ and $\delta=1/(n+1)$ after optimal RDP
conversion.

###  B.4 Private SGD

In Section 5.2, we trained a linear model on top of features extracted by a
scattering network444We used the Kymatio library
https://github.com/kymatio/kymatio to implement the scattering transform. on
the MNIST dataset. In addition, we consider a convolutional network with
$\tanh$ activation, which has been found to be more suitable for DP-SGD
(Papernot et al., 2020). We give the architecture details of both models in
Tables 2 and 2.

Layer | Parameters
---|---
ScatterNet | Scale $J=2$, $L=8$ angles, depth 2
GroupNorm (Wu and He, 2018) | 6 groups of 24 channels each
Fully connected | 10 units

Table 1: Architecture for scatter + linear model.

Layer | Parameters
---|---
Convolution $+\tanh$ | 16 filters of $8\times 8$, stride 2, padding 2
Average pooling |  $2\times 2$, stride 1
Convolution $+\tanh$ | 32 filters of $4\times 4$, stride 2, padding 0
Average pooling |  $2\times 2$, stride 1
Fully connected $+\tanh$ | 32 units
Fully connected $+\tanh$ | 10 units

Table 2: Architecture for convolutional network model.

#### Hyperparameters.

DP-SGD has several hyperparameters, and we exhaustive test all setting
combinations to produce the scatter plots in Figures 4 and 6. Tables 4 and 4
give the choice of values that we considered for each hyperparameter.

Hyperparameter | Values
---|---
Batch size | $600$
Momentum | $0.5$
# Iterations $T$ | $500,1000,2000,3000,5000$
Noise multiplier $\sigma$ for Gaussian and signSGD | $0.5,1,2,3,5$
$L_{1}$-metric DP parameter $\epsilon$ for MVU | $0.25,0.5,0.75,1,2,3,5$
Step size $\rho$ | $0.01,0.03,0.1$
Gradient norm clip $C$ | $0.25,0.5,1,2,4,8$

Table 3: Hyperparameters for DP-SGD on MNIST.

Hyperparameter | Values
---|---
Batch size | $500$
Momentum | $0.5$
# Iterations $T$ | $1000,2000,3000,5000,10000,15000$
Noise multiplier $\sigma$ for Gaussian and signSGD | $0.5,1,2,3,5$
$L_{1}$-metric DP parameter $\epsilon$ for MVU | $0.25,0.5,0.75,1,2,3,5$
Step size $\rho$ | $0.01,0.03,0.1$
Gradient norm clip $C$ | $0.25,0.5,1,2,4,8$

Table 4: Hyperparameters for DP-SGD on CIFAR-10.

#### Result for convolutional network.

Figure 6 shows the comparison of DP-SGD training with Gaussian mechanism,
stochastic signSGD, and MVU mechanism with $b=1$. The experimental setting is
identical to that of Figure 4 except for the model being a small convolutional
network trained end-to-end. We observe a similar result that MVU recovers the
performance of signSGD at equal communication budget of $b=1$.

Figure 6: DP-SGD training of a small convolutional network on MNIST with
Gaussian mechanism, stochastic signSGD and MVU mechanism. Each point
corresponds to a single hyperparameter setting, and dashed line shows Pareto
frontier of privacy-utility trade-off.


$\displaystyle-i\sum_{k=0}^{n-1}[A_{u}^{(k-n)},F_{z\bar{z}}^{(-k)}]+2i\sum_{k=0}^{n}[A_{[z}^{(k-n)},F_{u|\bar{z}]}^{(-k)}]$
$\displaystyle B_{rz\bar{z}}^{(-n)}$
$\displaystyle=(1-n)F_{z\bar{z}}^{(1-n)}-\partial_{z}F_{r\bar{z}}^{(-n)}+\partial_{\bar{z}}F_{rz}^{(-n)}+2i\sum_{k=2}^{n}[A_{[z}^{(k-n)},F_{r|\bar{z}]}^{(-k)}],\qquad
n\geq 2$ (300)

##  Appendix D YM e.o.m. and recursive relations in flat Bondi coordinates

Metric:

$ds^{2}=-2dudr+2r^{2}dzd\bar{z}$ (301)

Equations of motion:

$\mathcal{E}_{\mu}:=D^{\nu}\mathcal{F}_{\nu\mu}=\nabla^{\nu}\mathcal{F}_{\nu\mu}-i[\mathcal{A}^{\nu},\mathcal{F}_{\nu\mu}]\in
C^{\infty}_{r}(M)$ (302)

The YM equations of motion in flat Bondi at order $1/r^{n}$, with
$n\in\mathbb{N}$, are:

$\displaystyle E_{\mu}^{(-n)}$
$\displaystyle=-\partial_{u}F^{(-n)}_{r\mu}+\tilde{\delta}_{\mu}^{\rho}(n-1)F^{(1-n)}_{u\rho}+2\partial_{(z}F_{\bar{z})\mu}^{(2-n)}$
(303)
$\displaystyle\quad+2i\sum_{k=0}^{n}\left([A^{(k-n)}_{(u},F^{(-k)}_{r)\mu}]-[A^{(k-n)}_{(z},F^{(2-k)}_{\bar{z})\mu}]\right),$

where $\tilde{\delta}_{\mu}^{\nu}(n)$ is defined in (81).

###### Proof.

From (77):

$\displaystyle\mathcal{E}_{\mu}$
$\displaystyle=g^{\nu\rho}D_{\rho}\mathcal{F}_{\nu\mu}$ (304)
$\displaystyle=-2D_{(u}\mathcal{F}_{r)\mu}+2r^{-2}D_{(z}\mathcal{F}_{\bar{z})\mu}$
(305)
$\displaystyle=2\left(-\partial_{(u}\mathcal{F}_{r)\mu}+\Gamma^{\rho}_{ur}\mathcal{F}_{\rho\mu}+\Gamma^{\rho}_{\mu(u}\mathcal{F}_{r)\rho}+i[\mathcal{A}_{(u},\mathcal{F}_{r)\mu}]\right)$
(306)
$\displaystyle\quad+2r^{-2}\left(\partial_{(z}\mathcal{F}_{\bar{z})\mu}-\Gamma^{\rho}_{z\bar{z}}\mathcal{F}_{\rho\mu}-\Gamma^{\rho}_{\mu(z}\mathcal{F}_{\bar{z})\rho}-i[\mathcal{A}_{(z},\mathcal{F}_{\bar{z})\mu}]\right)$
$\displaystyle=2\left\\{-\partial_{(u}\mathcal{F}_{r)\mu}+r^{-1}/2(\mathcal{F}_{uz}\delta_{z\mu}+\mathcal{F}_{u\bar{z}}\delta_{\bar{z}\mu})+i[\mathcal{A}_{(u},\mathcal{F}_{r)\mu}]\right\\}$
(307)
$\displaystyle\quad+2r^{-2}\left\\{\partial_{(z}\mathcal{F}_{\bar{z})\mu}-r\mathcal{F}_{u\mu}-r^{-1}\mathcal{F}_{(z\bar{z})}\delta_{r\mu}-r/2(\mathcal{F}_{zu}\delta_{z\mu}+\mathcal{F}_{\bar{z}u}\delta_{\bar{z}\mu})-i[\mathcal{A}_{(z},\mathcal{F}_{\bar{z})\mu}]\right\\}$
$\displaystyle=-2\left(\partial_{(u}\mathcal{F}_{r)\mu}-i[\mathcal{A}_{(u},\mathcal{F}_{r)\mu}]\right)-2r^{-1}\mathcal{F}_{ur}\delta_{r\mu}+2r^{-2}\left(\partial_{(z}\mathcal{F}_{\bar{z})\mu}-i[\mathcal{A}_{(z},\mathcal{F}_{\bar{z})\mu}]\right)$
(308)

Thus, $\forall n\in\mathbb{N}$:

$\displaystyle E_{\mu}^{(-n)}$
$\displaystyle=r^{n}\mathcal{P}_{-n}(\mathcal{E}_{\mu})$ (309)
$\displaystyle=-r^{n}\left\\{\partial_{u}\mathcal{P}_{-n}(\mathcal{F}_{r\mu})+\partial_{r}\mathcal{P}_{1-n}(\mathcal{F}_{u\mu})-2i\mathcal{P}_{-n}([\mathcal{A}_{(u},\mathcal{F}_{r)\mu}])\right\\}$
(310)
$\displaystyle\quad-2r^{n-1}\mathcal{P}_{1-n}(\mathcal{F}_{ur})\delta_{r\mu}+2r^{n-2}\left\\{\partial_{(z}\mathcal{P}_{2-n}(\mathcal{F}_{\bar{z})\mu})-i\mathcal{P}_{2-n}([\mathcal{A}_{(z},\mathcal{F}_{\bar{z})\mu}])\right\\}$
$\displaystyle=-\partial_{u}F_{r\mu}^{(-n)}+(n-1)F_{u\mu}^{(1-n)}-2F_{ur}^{(1-n)}\delta_{r\mu}+2\partial_{(z}F_{\bar{z})\mu}^{(2-n)}$
(311)
$\displaystyle\quad+2i\sum_{k=0}^{n}[A_{(u}^{(k-n)},F_{r)\mu}^{(-k)}]-2i\sum_{k\in\mathbb{N}}[A_{(z}^{(2+k-n)},F_{\bar{z})\mu}^{(-k)}]$
$\displaystyle=-\partial_{u}F_{r\mu}^{(-n)}+(n-3)F_{ur}^{(1-n)}\delta_{r\mu}+(n-1)F_{uz}^{(1-n)}\delta_{z\mu}+(n-1)F_{u\bar{z}}^{(1-n)}\delta_{\bar{z}\mu}$
(312)
$\displaystyle\quad+2\partial_{(z}F_{\bar{z})\mu}^{(2-n)}+2i\sum_{k=0}^{n}\left([A_{(u}^{(k-n)},F_{r)\mu}^{(-k)}]-[A_{(z}^{(k-n)},F_{\bar{z})\mu}^{(2-k)}]\right)$

∎

The components are:

$\displaystyle E_{u}^{(-n)}$
$\displaystyle=\partial_{u}F_{ur}^{(-n)}-2\partial_{(z}F_{u|\bar{z})}^{(2-n)}-i\sum_{k=0}^{n}\left([A_{u}^{(k-n)},F_{ur}^{(-k)}]-2[A_{(z}^{(k-n)},F_{u|\bar{z})}^{(2-k)}]\right)$
(313) $\displaystyle E_{r}^{(-n)}$
$\displaystyle=(n-3)F_{ur}^{(1-n)}-2\partial_{(z}F_{r|\bar{z})}^{(2-n)}+i\sum_{k=0}^{n}\left([A_{r}^{(k-n)},F_{ur}^{(-k)}]+2[A_{(z}^{(k-n)},F_{r|\bar{z})}^{(2-k)}]\right)$
(314) $\displaystyle E_{z}^{(-n)}$
$\displaystyle=-\partial_{u}F_{rz}^{(-n)}+(n-1)F_{uz}^{(1-n)}-\partial_{z}F_{z\bar{z}}^{(2-n)}$
(315)
$\displaystyle+i\sum_{k=0}^{n}\left(2[A_{(u}^{(k-n)},F_{r)z}^{(-k)}]+[A_{z}^{(k-n)},F_{z\bar{z}}^{(2-k)}]\right)$
(316) $\displaystyle E_{\bar{z}}^{(-n)}$
$\displaystyle=-\partial_{u}F_{r\bar{z}}^{(-n)}+(n-1)F_{u\bar{z}}^{(1-n)}+\partial_{\bar{z}}F_{z\bar{z}}^{(2-n)}$
(317)
$\displaystyle+i\sum_{k=0}^{n}\left(2[A_{(u}^{(k-n)},F_{r)\bar{z}}^{(-k)}]-[A_{\bar{z}}^{(k-n)},F_{z\bar{z}}^{(2-k)}]\right)$
(318)

The first three orders are:

$\displaystyle E_{\mu}^{(0)}$
$\displaystyle=-\partial_{u}F_{r\mu}^{(0)}+2i[A_{(u}^{(0)},F_{r)\mu}^{(0)}]$
(319) $\displaystyle E_{\mu}^{(-1)}$
$\displaystyle=-\partial_{u}F_{r\mu}^{(-1)}-2F_{ur}^{(0)}\delta_{r\mu}+2i\left([A_{(u}^{(-1)},F_{r)\mu}^{(0)}]+[A_{(u}^{(0)},F_{r)\mu}^{(-1)}]\right)$
(320) $\displaystyle E_{\mu}^{(-2)}$
$\displaystyle=-\partial_{u}F_{r\mu}^{(-2)}+\tilde{\delta}_{\mu}^{\rho}(1)F_{u\rho}^{(-1)}+2\partial_{(z}F_{\bar{z})\mu}^{(0)}-2i[A_{(z}^{(0)},F_{\bar{z})\mu}^{(0)}]+2i\sum_{k=0}^{2}[A_{(u}^{(k-n)},F_{r)\mu}^{(-k)}]$
(321)

###  D.1 Light-cone gauge

E.o.m. in light-cone gauge (87) with fall-off (88):

$\displaystyle E_{u}^{(-n)}$
$\displaystyle=\partial_{u}F_{ur}^{(-n)}-2\partial_{(z}F_{u|\bar{z})}^{(2-n)}+2i\sum_{k=0}^{n-2}[A_{(z}^{(2+k-n)},F_{u|\bar{z})}^{(-k)}],\qquad
n\geq 2$ (322) $\displaystyle E_{r}^{(-n)}$
$\displaystyle=(n-3)F_{ur}^{(1-n)}-2\partial_{(z}F_{r|\bar{z})}^{(2-n)}$ (323)
$\displaystyle\quad+i\sum_{k=2}^{n-2}\left([A_{r}^{(k-n)},F_{ur}^{(-k)}]+2[A_{(z}^{(2+k-n)},F_{r|\bar{z})}^{(-k)}]\right),\qquad
n\geq 4$ $\displaystyle E_{z}^{(-n)}$
$\displaystyle=-\partial_{u}F_{rz}^{(-n)}+(n-1)F_{uz}^{(1-n)}-\partial_{z}F_{z\bar{z}}^{(2-n)}$
(324)
$\displaystyle\quad+i\sum_{k=0}^{n-2}\left([A_{r}^{(k-n)},F_{uz}^{(-k)}]+[A_{z}^{(2+k-n)},F_{z\bar{z}}^{(-k)}]\right),\qquad
n\geq 2$ $\displaystyle E_{\bar{z}}^{(-n)}$
$\displaystyle=-\partial_{u}F_{r\bar{z}}^{(-n)}+(n-1)F_{u\bar{z}}^{(1-n)}+\partial_{\bar{z}}F_{z\bar{z}}^{(2-n)}$
(325)
$\displaystyle\quad+i\sum_{k=0}^{n-2}\left([A_{r}^{(k-n)},F_{u\bar{z}}^{(-k)}]-[A_{\bar{z}}^{(2+k-n)},F_{z\bar{z}}^{(-k)}]\right),\qquad
n\geq 2$

####  D.1.1 Recursive formula for the gauge vector

Starting from the equations above, it is possible to find recursive formulas
for $A_{\mu}^{(-n)}$ by following the very same steps described in paragraph
3.2.1. Since the comments and considerations presented there still hold, we
simply list the results:

$\displaystyle A_{r}^{(-2)}$
$\displaystyle=2\partial_{u}^{-1}\left(\partial_{(z}A_{\bar{z})}^{(0)}-i\partial_{u}^{-1}[A_{(z}^{(0)},\partial_{u}A_{\bar{z})}^{(0)}]\right)$
(326) $\displaystyle A_{r}^{(-n)}$
$\displaystyle=\frac{1}{n-2}\partial_{u}^{-1}\left[2\partial_{(z}F_{r|\bar{z})}^{(1-n)}-i\sum_{k=2}^{n-1}\left([A_{r}^{(k-n-1)},F_{ur}^{(-k)}]+2[A_{(z}^{(1+k-n)},F_{r|\bar{z})}^{(-k)}]\right)\right],\quad
n\geq 3$ (327) $\displaystyle A_{z}^{(-n)}$
$\displaystyle=\frac{1}{2n}\bigg{\\{}-\partial_{z}A_{r}^{(-n-1)}+i\sum_{k=2}^{n+1}[A_{z}^{(k-n-1)},A_{r}^{(-k)}]$
(328)
$\displaystyle\quad+\partial_{u}^{-1}\bigg{[}\partial_{z}F^{(1-n)}_{z\bar{z}}-i\sum_{k=0}^{n-1}\left([A^{(k-n-1)}_{r},\partial_{u}A_{z}^{(-k)}]+[A^{(1+k-n)}_{z},F^{(-k)}_{z\bar{z}}]\right)\bigg{]}\bigg{\\}},\quad
n\geq 1$

that, in a more compact form, read

$\displaystyle A_{r}^{(-2)}$
$\displaystyle=2\partial_{u}^{-2}\left(D_{(z}\partial_{u}\mathcal{A}_{\bar{z})}\right)^{(0)}$
(329) $\displaystyle A_{r}^{(-n)}$
$\displaystyle=\frac{1}{n-2}\partial_{u}^{-1}\left[2\left(D_{(z}\mathcal{F}_{r|\bar{z})}\right)^{(1-n)}-i\left([\mathcal{A}_{r},\partial_{u}\mathcal{A}_{r}]\right)^{(-n-1)}\right],\qquad
n\geq 3$ (330) $\displaystyle A_{z}^{(-n)}$
$\displaystyle=-\frac{1}{2n}\big{\\{}(D_{z}\mathcal{A}_{r})^{(-n-1)}-\partial_{u}^{-1}\big{(}(D_{z}\mathcal{F}_{z\bar{z}})^{(1-n)}-i([\mathcal{A}_{r},\partial_{u}\mathcal{A}_{z}])^{(-n-1)}\big{)}\big{\\}},\qquad
n\geq 1.$ (331)

###  D.2 Radial gauge

E.o.m. in radial gauge (131) with fall-off (132):

$\displaystyle E_{u}^{(-n)}$
$\displaystyle=\partial_{u}F_{ur}^{(-n)}-2\partial_{(z}F_{u|\bar{z})}^{(2-n)}$
(332)
$\displaystyle\quad-i\sum_{k=0}^{n-1}[A_{u}^{(k-n)},F_{ur}^{(-k)}]+2i\sum_{k=0}^{n-2}[A_{(z}^{(2+k-n)},F_{u|\bar{z})}^{(-k)}],\qquad
n\geq 2$ $\displaystyle E_{r}^{(-n)}$
$\displaystyle=(n-3)F_{ur}^{(1-n)}-2\partial_{(z}F_{r|\bar{z})}^{(2-n)}+2i\sum_{k=2}^{n-2}[A_{(z}^{(2+k-n)},F_{r|\bar{z})}^{(-k)}],\qquad
n\geq 4$ (333) $\displaystyle E_{z}^{(-n)}$
$\displaystyle=-\partial_{u}F_{rz}^{(-n)}+(n-1)F_{uz}^{(1-n)}-\partial_{z}F_{z\bar{z}}^{(2-n)}$
(334)
$\displaystyle\quad+i\sum_{k=0}^{n-1}[A_{u}^{(k-n)},F_{rz}^{(-k)}]+i\sum_{k=0}^{n-2}[A_{z}^{(2+k-n)},F_{z\bar{z}}^{(-k)}],\qquad
n\geq 2$ $\displaystyle E_{\bar{z}}^{(-n)}$
$\displaystyle=-\partial_{u}F_{r\bar{z}}^{(-n)}+(n-1)F_{u\bar{z}}^{(1-n)}+\partial_{\bar{z}}F_{z\bar{z}}^{(2-n)}$
(335)
$\displaystyle\quad+i\sum_{k=0}^{n-1}[A_{u}^{(k-n)},F_{r\bar{z}}^{(-k)}]-i\sum_{k=0}^{n-2}[A_{\bar{z}}^{(2+k-n)},F_{z\bar{z}}^{(-k)}],\qquad
n\geq 2$

####  D.2.1 Recursive formula for the gauge vector

Following the same line of reasoning of paragraph 3.3.1 we obtain

$\displaystyle A_{u}^{(-1)}$
$\displaystyle=2\partial_{(z}A_{\bar{z})}^{(0)}-2i\partial_{u}^{-1}[A_{(z}^{(0)},\partial_{u}A_{\bar{z})}^{(0)}]$
$\displaystyle A_{u}^{(-n)}$
$\displaystyle=-\frac{2}{n}\left(\partial_{(z}A_{\bar{z})}^{(1-n)}+\sum_{k=1}^{n-1}\frac{ik}{1-n}[A^{(1+k-n)}_{(z},A_{\bar{z})}^{(-k)}]\right),\quad
n\geq 2$ $\displaystyle A_{z}^{(-n)}$
$\displaystyle=\frac{1}{2}\partial_{u}^{-1}\bigg{(}\partial_{z}A_{u}^{(-n)}+\frac{1}{n}\partial_{z}F^{(1-n)}_{z\bar{z}}-\frac{i}{n}\sum_{k=1}^{n}[A_{z}^{(k-n)},(2n-k)A_{u}^{(-k)}+F^{(1-k)}_{z\bar{z}}]\bigg{)},\quad
n\geq 1.$

Some recursive formulas for the field strength are

$\displaystyle F_{ur}^{(-2)}$
$\displaystyle=2\left(\partial_{(z}A_{\bar{z})}^{(0)}-i\partial_{u}^{-1}[A_{(z}^{(0)},\partial_{u}A_{\bar{z})}^{(0)}]\right)$
(336) $\displaystyle F_{ur}^{(-n)}$
$\displaystyle=-2\left(\partial_{(z}A_{\bar{z})}^{(2-n)}+\sum_{k=1}^{n-2}\frac{ik}{2-n}[A^{(2+k-n)}_{(z},A_{\bar{z})}^{(-k)}]\right),\qquad
n\geq 3$ $\displaystyle F_{rz}^{(-n)}$
$\displaystyle=-\frac{1}{2}\partial_{u}^{-1}\left(\partial_{z}(F_{ur}^{(-n)}+F_{z\bar{z}}^{(2-n)})-i\sum_{k=2}^{n}[A_{z}^{(k-n)},\frac{2n-k-1}{k-1}F_{ur}^{(-k)}+F_{z\bar{z}}^{(2-k)}]\right),\quad
n\geq 2$ (337)

The first two equations above can be recast in the more compact form

$\displaystyle F_{ur}^{(-2)}$
$\displaystyle=2\partial_{u}^{-1}\left(D_{(z}\mathcal{F}_{u|\bar{z})}\right)^{(0)}$
(338) $\displaystyle F_{ur}^{(-n)}$
$\displaystyle=\frac{2}{n-2}\left(D_{(z}\mathcal{F}_{r|\bar{z})}\right)^{(1-n)},\qquad
n\geq 3.$ (339)

Finally, it is easy to prove that

$F_{uz}^{(-n)}=\frac{1}{n}\left[(D_{u}\mathcal{F}_{rz})^{(-n-1)}+(D_{z}\mathcal{F}_{z\bar{z}})^{(1-n)}\right].$
(340)

## References

  * (1) S. Nagy, J. Peraza, and G. Pizzolo, “A General Hierarchy of Charges at Null Infinity via the Todd Polynomials”, arXiv:2405.06629 [hep-th].
  * (2) A. Strominger, “Lectures on the Infrared Structure of Gravity and Gauge Theory”, arXiv:1703.05448 [hep-th].
  * (3) S. Pasterski, M. Pate, and A.-M. Raclariu, “Celestial Holography”, in Snowmass 2021.  11, 2021.  arXiv:2111.11392 [hep-th].
  * (4) A.-M. Raclariu, “Lectures on Celestial Holography”, arXiv:2107.02075 [hep-th].
  * (5) S. Weinberg, “Infrared photons and gravitons”, Phys. Rev. 140 (1965) B516–B524.
  * (6) F. E. Low, “Bremsstrahlung of very low-energy quanta in elementary particle collisions”, Phys. Rev. 110 (1958) 974–977.
  * (7) A. Strominger, “Asymptotic Symmetries of Yang-Mills Theory”, JHEP 07 (2014) 151, arXiv:1308.0589 [hep-th].
  * (8) A. Strominger, “On BMS Invariance of Gravitational Scattering”, JHEP 07 (2014) 152, arXiv:1312.2229 [hep-th].
  * (9) T. He, P. Mitra, A. P. Porfyriadis, and A. Strominger, “New Symmetries of Massless QED”, JHEP 10 (2014) 112, arXiv:1407.3789 [hep-th].
  * (10) M. Campiglia and A. Laddha, “New symmetries for the Gravitational S-matrix”, JHEP 04 (2015) 076, arXiv:1502.02318 [hep-th].
  * (11) M. Campiglia and J. Peraza, “Generalized BMS charge algebra”, Phys. Rev. D 101 (2020) no. 10, 104039, arXiv:2002.06691 [gr-qc].
  * (12) M. Campiglia and J. Peraza, “Charge algebra for non-abelian large gauge symmetries at O(r)”, JHEP 12 (2021) 058, arXiv:2111.00973 [hep-th].
  * (13) A. Strominger, “On BMS Invariance of Gravitational Scattering”, JHEP 07 (2014) 152, arXiv:1312.2229 [hep-th].
  * (14) V. Lysov, S. Pasterski, and A. Strominger, “Low’s Subleading Soft Theorem as a Symmetry of QED”, Phys. Rev. Lett. 113 (2014) no. 11, 111601, arXiv:1407.3814 [hep-th].
  * (15) W. Donnelly and L. Freidel, “Local subsystems in gauge theory and gravity”, JHEP 09 (2016) 102, arXiv:1601.04744 [hep-th].
  * (16) A. J. Speranza, “Local phase space and edge modes for diffeomorphism-invariant theories”, JHEP 02 (2018) 021, arXiv:1706.05061 [hep-th].
  * (17) L. Freidel, M. Geiller, and D. Pranzetti, “Edge modes of gravity. Part III. Corner simplicity constraints”, JHEP 01 (2021) 100, arXiv:2007.12635 [hep-th].
  * (18) L. Freidel, M. Geiller, and D. Pranzetti, “Edge modes of gravity. Part II. Corner metric and Lorentz charges”, JHEP 11 (2020) 027, arXiv:2007.03563 [hep-th].
  * (19) L. Freidel, M. Geiller, and D. Pranzetti, “Edge modes of gravity. Part I. Corner potentials and charges”, JHEP 11 (2020) 026, arXiv:2006.12527 [hep-th].
  * (20) L. Freidel, “A canonical bracket for open gravitational system”, arXiv:2111.14747 [hep-th].
  * (21) L. Ciambelli, R. G. Leigh, and P.-C. Pai, “Embeddings and Integrable Charges for Extended Corner Symmetry”, Phys. Rev. Lett. 128 (2022) , arXiv:2111.13181 [hep-th].
  * (22) L. Freidel, R. Oliveri, D. Pranzetti, and S. Speziale, “Extended corner symmetry, charge bracket and Einstein’s equations”, JHEP 09 (2021) 083, arXiv:2104.12881 [hep-th].
  * (23) L. Freidel, D. Pranzetti, and A.-M. Raclariu, “Sub-subleading soft graviton theorem from asymptotic Einstein’s equations”, JHEP 05 (2022) 186, arXiv:2111.15607 [hep-th].
  * (24) L. Ciambelli and R. G. Leigh, “Isolated surfaces and symmetries of gravity”, Phys. Rev. D 104 (2021) no. 4, 046005, arXiv:2104.07643 [hep-th].
  * (25) M. Geiller, “Celestial $w_{1+\infty}$ charges and the subleading structure of asymptotically-flat spacetimes”, arXiv:2403.05195 [hep-th].
  * (26) M. Geiller and C. Zwikel, “The partial Bondi gauge: Further enlarging the asymptotic structure of gravity”, SciPost Phys. 13 (2022) 108, arXiv:2205.11401 [hep-th].
  * (27) J. Peraza, “Renormalized electric and magnetic charges for O(rn) large gauge symmetries”, JHEP 01 (2024) 175, arXiv:2301.05671 [hep-th].
  * (28) S. Nagy and J. Peraza, “Radiative phase space extensions at all orders in r for self-dual Yang-Mills and gravity”, JHEP 02 (2023) 202, arXiv:2211.12991 [hep-th].
  * (29) E. C. G. Stueckelberg, “Interaction energy in electrodynamics and in the field theory of nuclear forces”, Helv. Phys. Acta 11 (1938) 225–244.
  * (30) B. Sahoo and A. Sen, “Classical and Quantum Results on Logarithmic Terms in the Soft Theorem in Four Dimensions”, JHEP 02 (2019) 086, arXiv:1808.03288 [hep-th].
  * (31) S. Pasterski, “A comment on loop corrections to the celestial stress tensor”, JHEP 01 (2023) 025, arXiv:2205.10901 [hep-th].
  * (32) L. Donnay, K. Nguyen, and R. Ruzziconi, “Loop-corrected subleading soft theorem and the celestial stress tensor”, JHEP 09 (2022) 063, arXiv:2205.11477 [hep-th].
  * (33) S. Agrawal, L. Donnay, K. Nguyen, and R. Ruzziconi, “Logarithmic soft graviton theorems from superrotation Ward identities”, JHEP 02 (2024) 120, arXiv:2309.11220 [hep-th].
  * (34) S. Choi, A. Laddha, and A. Puhm, “Asymptotic Symmetries for Logarithmic Soft Theorems in Gauge Theory and Gravity”, arXiv:2403.13053 [hep-th].
  * (35) M. Campiglia and A. Laddha, “Loop Corrected Soft Photon Theorem as a Ward Identity”, JHEP 10 (2019) 287, arXiv:1903.09133 [hep-th].
  * (36) S. Atul Bhatkar, “Ward identity for loop level soft photon theorem for massless QED coupled to gravity”, JHEP 10 110, arXiv:1912.10229 [hep-th].
  * (37) J. A. Todd, “The arithmetical invariants of algebraic loci”, Proceedings of the London Mathematical Society s2-43 (1938) no. 1, 190–225.
  * (38) L. Freidel, F. Hopfmüller, and A. Riello, “Asymptotic Renormalization in Flat Space: Symplectic Potential and Charges of Electromagnetism”, JHEP 10 (2019) 126, arXiv:1904.04384 [hep-th].
  * (39) L. Freidel, D. Pranzetti, and A.-M. Raclariu, “On infinite symmetry algebras in Yang-Mills theory”, JHEP 12 (2023) 009, arXiv:2306.02373 [hep-th].
  * (40) K. Kampf, J. Novotny, J. Trnka, and P. Vasko, “Goldstone bosons on celestial sphere and conformal soft theorems”, JHEP 12 (2023) 135, arXiv:2303.14761 [hep-th].
  * (41) T. He, P. Mitra, and K. M. Zurek, “A Diamond of Infrared Equivalences in Abelian Gauge Theories”, arXiv:2405.12303 [hep-th].
  * (42) M. Campiglia and A. Laddha, “Asymptotic charges in massless QED revisited: A view from Spatial Infinity”, JHEP 05 (2019) 207, arXiv:1810.04619 [hep-th].
  * (43) I. Bakas, “The Large n Limit of Extended Conformal Symmetries”, Phys. Lett. B 228 (1989) 57.
  * (44) A. Strominger, “$w_{1+\infty}$ Algebra and the Celestial Sphere: Infinite Towers of Soft Graviton, Photon, and Gluon Symmetries”, Phys. Rev. Lett. 127 (2021) no. 22, 221601, arXiv:2105.14346 [hep-th].
  * (45) C. N. Pope, L. J. Romans, and X. Shen, “The Complete Structure of W(Infinity)”, Phys. Lett. B 236 (1990) 173–178.
  * (46) D. B. Fairlie and J. Nuyts, “Deformations and Renormalizations of $W$(infinity)”, Commun. Math. Phys. 134 (1990) 413–420.
  * (47) C. N. Pope, “Lectures on W algebras and W gravity”, in Summer School in High-energy Physics and Cosmology, pp. 827–867.  12, 1991.  arXiv:hep-th/9112076.
  * (48) W. Bu, S. Heuveline, and D. Skinner, “Moyal deformations, W1+∞ and celestial holography”, JHEP 12 (2022) 011, arXiv:2208.13750 [hep-th].
  * (49) R. Bittleston, S. Heuveline, and D. Skinner, “The celestial chiral algebra of self-dual gravity on Eguchi-Hanson space”, JHEP 09 (2023) 008, arXiv:2305.09451 [hep-th].
  * (50) R. Bittleston, G. Bogna, S. Heuveline, A. Kmec, L. Mason, and D. Skinner, “On AdS4 deformations of celestial symmetries”, JHEP 07 (2024) 010, arXiv:2403.18011 [hep-th].
  * (51) T. R. Taylor and B. Zhu, “w1+$\infty$ Algebra with a Cosmological Constant and the Celestial Sphere”, Phys. Rev. Lett. 132 (2024) no. 22, 221602, arXiv:2312.00876 [hep-th].
  * (52) A. Kmec, L. Mason, R. Ruzziconi, and A. Yelleshpur Srikant, “Celestial $Lw_{1+\infty}$ charges from a twistor action”, arXiv:2407.04028 [hep-th].
  * (53) R. Monteiro, “Celestial chiral algebras, colour-kinematics duality and integrability”, arXiv:2208.11179 [hep-th].
  * (54) E. Himwich, M. Pate, and K. Singh, “Celestial operator product expansions and w1+∞ symmetry for all spins”, JHEP 01 (2022) 080, arXiv:2108.07763 [hep-th].
  * (55) A. Lipstein and S. Nagy, “Self-Dual Gravity and Color-Kinematics Duality in AdS4”, Phys. Rev. Lett. 131 (2023) no. 8, 081501, arXiv:2304.07141 [hep-th].
  * (56) M. Carrillo Gonzalez, A. Lipstein, and S. Nagy, “Self-Dual Cosmology”, to appear .
  * (57) T. Adamo, L. Mason, and A. Sharma, “Celestial $w_{1+\infty}$ Symmetries from Twistor Space”, SIGMA 18 (2022) 016, arXiv:2110.06066 [hep-th].
  * (58) C. N. Pope, X. Shen, K. W. Xu, and K.-j. Yuan, “SL(infinity,R) symmetry of quantum W(infinity) gravity”, Nucl. Phys. B 376 (1992) 52–74.
  * (59) L. Freidel, D. Pranzetti, and A.-M. Raclariu, “Higher spin dynamics in gravity and w1+$\infty$ celestial symmetries”, Phys. Rev. D 106 (2022) no. 8, 086013, arXiv:2112.15573 [hep-th].
  * (60) K. V. Kuchar, “Does an unspecified cosmological constant solve the problem of time in quantum gravity?”, Phys. Rev. D 43 (1991) 3332–3344.
  * (61) S. Nagy, A. Padilla, and I. Zavala, “The Super-Stückelberg procedure and dS in pure supergravity”, Proc. Roy. Soc. Lond. A 476 (2020) no. 2237, 20200035, arXiv:1910.14349 [hep-th].
  * (62) S. Bansal, S. Nagy, A. Padilla, and I. Zavala, “Unimodular vs Nilpotent Superfield Approach to Pure dS Supergravity”, JHEP 01 (2021) 146, arXiv:2010.13758 [hep-th].
  * (63) G. Barnich and C. Troessaert, “Aspects of the BMS/CFT correspondence”, JHEP 05 (2010) 062, arXiv:1001.1541 [hep-th].
  * (64) G. Barnich, “A Note on gauge systems from the point of view of Lie algebroids”, AIP Conf. Proc. 1307 (2010) no. 1, 7–18, arXiv:1010.0899 [math-ph].
  * (65) G. Barnich and P.-H. Lambert, “Einstein-Yang-Mills theory: Asymptotic symmetries”, Phys. Rev. D 88 (2013) 103006, arXiv:1310.2698 [hep-th].
  * (66) A. Fiorucci, Leaky covariant phase spaces: Theory and application to $\Lambda$-BMS symmetry.  PhD thesis, Brussels U., Intl. Solvay Inst., Brussels, 2021.  arXiv:2112.07666 [hep-th].
  * (67) Y. Hamada and G. Shiu, “Infinite Set of Soft Theorems in Gauge-Gravity Theories as Ward-Takahashi Identities”, Phys. Rev. Lett. 120 (2018) no. 20, 201601, arXiv:1801.05528 [hep-th].
  * (68) Z.-Z. Li, H.-H. Lin, and S.-Q. Zhang, “Infinite Soft Theorems from Gauge Symmetry”, Phys. Rev. D 98 (2018) no. 4, 045004, arXiv:1802.03148 [hep-th].
  * (69) M. Campiglia and J. Peraza, “Charge algebra for non-abelian large gauge symmetries at O(r)”, JHEP 12 (2021) 058, arXiv:2111.00973 [hep-th].
  * (70) E. Casali, “Soft sub-leading divergences in Yang-Mills amplitudes”, JHEP 08 (2014) 077, arXiv:1404.5551 [hep-th].
  * (71) M. Henneaux and C. Teitelboim, “The Cosmological Constant and General Covariance”, Phys. Lett. B 222 (1989) 195–199.
  * (72) F. Cachazo and A. Strominger, “Evidence for a New Soft Graviton Theorem”,. (4, 2014) , arXiv:1404.4091 [hep-th].
  * (73) O. Fuentealba, M. Henneaux, and C. Troessaert, “Logarithmic supertranslations and supertranslation-invariant Lorentz charges”, JHEP 02 (2023) 248, arXiv:2211.10941 [hep-th].
  * (74) M. Campiglia and S. Nagy, “A double copy for asymptotic symmetries in the self-dual sector”, JHEP 03 (2021) 262, arXiv:2102.01680 [hep-th].
  * (75) T. Adamo and U. Kol, “Classical double copy at null infinity”, Class. Quant. Grav. 39 (2022) no. 10, 105007, arXiv:2109.07832 [hep-th].
  * (76) P. Ferrero, D. Francia, C. Heissenberg, and M. Romoli, “Double-Copy Supertranslations”, (2, 2024) , arXiv:2402.11595 [hep-th].
  * (77) P. Mao and W. Zhao, “Note on the asymptotic structure of Kerr-Schild form”, JHEP 01 (2022) 030, arXiv:2109.09676 [gr-qc].
  * (78) H. Godazgar, M. Godazgar, R. Monteiro, D. Peinador Veiga, and C. N. Pope, “Asymptotic Weyl double copy”, JHEP 11 (2021) 126, arXiv:2109.07866 [hep-th].
  * (79) A. Guevara, E. Himwich, M. Pate, and A. Strominger, “Holographic symmetry algebras for gauge theory and gravity”, JHEP 11 (2021) 152, arXiv:2103.03961 [hep-th].
  * (80) L. Ciambelli and R. G. Leigh, “Universal Corner Symmetry and the Orbit Method for Gravity”,. (7, 2022) , arXiv:2207.06441 [hep-th].
  * (81) M. Bianchi, S. He, Y.-t. Huang, and C. Wen, “More on Soft Theorems: Trees, Loops and Strings”, Phys. Rev. D 92 (2015) no. 6, 065022, arXiv:1406.5155 [hep-th].
  * (82) Z. Bern, G. Chalmers, L. J. Dixon, and D. A. Kosower, “One loop N gluon amplitudes with maximal helicity violation via collinear limits”, Phys. Rev. Lett. 72 (1994) 2134–2137, arXiv:hep-ph/9312333.
  * (83) G. Mahlon, “Multi - gluon helicity amplitudes involving a quark loop”, Phys. Rev. D 49 (1994) 4438–4453, arXiv:hep-ph/9312276.
  * (84) Z. Bern, L. J. Dixon, D. C. Dunbar, and D. A. Kosower, “One loop selfdual and N=4 superYang-Mills”, Phys. Lett. B 394 (1997) 105–115, arXiv:hep-th/9611127.
  * (85) Z. Bern, L. J. Dixon, M. Perelstein, and J. S. Rozowsky, “One loop n point helicity amplitudes in (selfdual) gravity”, Phys. Lett. B 444 (1998) 273–283, arXiv:hep-th/9809160.
  * (86) R. Monteiro, R. Stark-Muchão, and S. Wikeley, “Anomaly and double copy in quantum self-dual Yang-Mills and gravity”, arXiv:2211.12407 [hep-th].
  * (87) A. Ball, S. A. Narayanan, J. Salzer, and A. Strominger, “Perturbatively exact w1+∞ asymptotic symmetry of quantum self-dual gravity”, JHEP 01 (2022) 114, arXiv:2111.10392 [hep-th].
  * (88) J. Mago, L. Ren, A. Y. Srikant, and A. Volovich, “Deformed $w_{1+\infty}$ Algebras in the Celestial CFT”, SIGMA 19 (2023) 044, arXiv:2111.11356 [hep-th].
  * (89) S. Banerjee, H. Kulkarni, and P. Paul, “Celestial OPE in self-dual gravity”, Phys. Rev. D 109 (2024) no. 8, 086017, arXiv:2311.06485 [hep-th].
  * (90) R. Monteiro, “From Moyal deformations to chiral higher-spin theories and to celestial algebras”, JHEP 03 (2023) 062, arXiv:2212.11266 [hep-th].


# Reply to arXiv:2203.14555

Margaret Hawton  Department of Physics, Lakehead University, Thunder Bay, ON,
Canada, P7B 5E1

###### Abstract

This comment refutes the claim made by A. Jadczyk and A.M. Schlichtinger in
arXiv:2203.14555 that the photon position operator with commuting components
proposed in 1999 does not have the properties required for a photon position
operator.

All of the statements in JadezykSchliechtinher  relating to photon position
operators with commuting components (PPOCC) are incorrect since they are based
on the assumption of spherically symmetry that is appropriate for massive
particles but not for the photon. The symmetry of a particle’s states is
determined by Wigner’s little group that can be boosted to give all acceptable
states. For mass positive definite particles this little group is the three-
dimensional rotation group, while for the zero mass photons it is a single
rotation that can be called $\widehat{J}_{3}$ and two generators of gauge
transformations. This is discussed in Weinberg  and WignerLittleGroup . The
mathematical proofs referred to in paragraphs 1 and 2 of the Introduction to
JadezykSchliechtinher  and the properties referred to in its Abstract are
based on the assumption of spherical symmetry and hence do not apply to the
photon.

There is no mathematical or logical error in WignerLittleGroup , HawtonBaylis
or HawtonPosOp . The contents of these refereed and published papers is
completely consistent with the Poincaré algebra
$\left[\widehat{J}_{i},\widehat{J}_{j}\right]=i\hbar\epsilon_{ijk}\widehat{J}_{k},$
$\left[\widehat{J}_{i},\widehat{K}_{j}\right]=i\epsilon_{ijk}\widehat{K}_{k},$
$\left[\widehat{K}_{i},\widehat{K}_{j}\right]=-i\hbar\epsilon_{ijk}\widehat{J}_{k},$
$\left[\widehat{J}_{i},\widehat{P}_{j}\right]=i\hbar\epsilon_{ijk}\widehat{P}_{k},$
$\left[\widehat{K}_{i},\widehat{P}_{j}\right]=i\hbar\delta_{ij}\widehat{H},$
$\left[\widehat{K}_{i},\widehat{H}\right]=-i\hbar\widehat{P}_{i},$
$\widehat{J}_{i},\widehat{H}=\left[\widehat{P}_{i},\widehat{H}\right]=\left[\widehat{P}_{i},\widehat{P}_{j}\right]=0$
for $i=1,2,3$ satisfied by the conserved total momentum, total angular
momentum and boost operators. There is no separation into spin and orbital
angular momentum and no position operator in this general Poincaré algebra
because these physical quantities are not conserved. In WignerLittleGroup  and
HawtonBaylis  a realization of the Lie algebra of the Poincaré group” is
specified in which total angular momentum is separated into its extrinsic and
intrinsic parts as
$\widehat{\mathbf{J}}=\widehat{\mathbf{x}}^{\left(\chi\right)}\times\hbar\mathbf{k}+\widehat{\mathbf{J}}^{\left(0,\chi\right)}$
where $\widehat{\mathbf{x}}^{\left(\chi\right)}$ is a PPOCC and
$\widehat{\mathbf{J}}^{\left(0,\chi\right)}$ is the intrinsic angular
momentum.

Prior to the work described above it was assumed that photon position
eigenvectors, like those describing massive particles, are spherically
symmetric. As discussed in the first paragraph this assumption is not
appropriate for photons. Ref. HawtonPosOp  is just a contruction of the PPOCC
that proves its existence. The symmetry of its eigenvectors and its
implementation of the Poincaré algebra is discussed in HawtonBaylis  and its
relationship to the Wigner little group is established in WignerLittleGroup .

## References

  * (1) A. Jadczyk and A.M. Schlichtinger, ”A comment on the ”Photon position operator with commuting components”, arXiv:2203.14555
  * (2) S. Weinberg, The quantum theory of fields, Vol. I, Foundations, Cambridge (1995), Sections 2.5 and 5.9
  * (3) M. Hawton and V. Debierre, ”Photon position eigenvectors, Wigner’s little group and Berry’s phase”, J. Math. Phys. 60, 052104 (2019)
  * (4) M. Hawton and W. E. Baylis, ”Photon position operators and localized bases,” Phys. Rev. A 64, 012101 (2001); ”Angular momentum and the geometrical gauge of localized photon states,” 71, 033816 (2005)
  * (5) M. Hawton, ”Photon position operator with commuting components,” Phys. Rev. A 59, 954-959 (1999); ”Photon wave functions in a localized coordinate space basis,” Phys. Rev. A 59, 3223-3227 (1999)