Author response (Part 2/2)
**3. A refined definition for unbiased compressor**
While we are following the convention in literature, we are glad to provide a more precise definition for unbiased compressors stuided in the manuscript to clarify the reviewer's confusion. In fact, an unbiased compressor with finite bits exists if and only if the following conditions hold:
- **The valid input value must be bounded.** It's clear that using finite bits cannot provide an unbiased estimate for arbitrarily large (or small) values.
- **The valid non-zero input must be bounded away from zero.** Since the compression uses finite bits, there exists the smallest distance that bounds all possible input values away from 0.
Given the above conditions, we will modify the classical definition of unbiased compressor as follows:
**Assumption 2’**
We assume unbiased compressors $\\{C_i\\}_{i=1}^n$ satisfy
\begin{equation}
\mathbb{E}[C_i(x)]=x,\quad\mathbb{E}[\\|C_i(x)-x\\|^2]\le\omega\\|x\\|^2,
\end{equation}
for a constant $\omega\ge0$ and any input $x\in\mathcal{X}\subset\mathbb{R}^d$, where $\mathcal{X}$ satisfies the following condition: **There exists positive constants $0<\epsilon_m<M$ so that it holds for all $ x=(x_1,\cdots,x_d)^\top\in\mathcal{X}$ that $|x_i|\in\\{0\\}\cup[\epsilon_m,M]$, $i=1,\cdots,d$.**
We believe it is a proper definition because
- **It is well justified in practice.** The inputs of compressors under machinery computations; therefore, their maximum value and non-zero lower bound are constrained by the computation precision of machines. For instance, when performing computations using float32, the resulting values are bounded above by approximately 3.4e38 and away from zero by at least about 1.18e-38 if non-zero.
- **It is consistent with unbiased compressors proposed in previous works.** Natural compression [14] is a good unbiased compression scheme, following which we can provide a concrete example of unbiased compressors satisfying Assumption $2^\prime$:
Letting $\mathcal{C}(0)=0$ and
\begin{equation}
\mathcal{C}(t)=\left\\{
\begin{array}{2} sign(t)\cdot2^{\lfloor\log_2|t|\rfloor}, &\text{with } p(t),\\\\
sign(t)\cdot2^{\lceil\log_2|t|\rceil}, &\text{with } 1-p(t),
\end{array}
\right.
\end{equation}
where $t\ne0$ and probability $p(t)=\frac{2^{\lceil\log_2|t|\rceil}-|t|}{2^{\lfloor\log_2|t|\rfloor}}$, it's clear that $d(2+\lceil\log_2(\lceil\log_2(M)\rceil-\lfloor\log_2(\epsilon_m)\rfloor+1)\rceil)$ bits are sufficient for constructing such a compressor that satisfies Assumption $2^\prime$ with $\omega=1/8$.
- **It does not affect the theoretical results of our work.**
-- **Upper bound**. Since the convergence criterion $\epsilon$ is typically much larger than the machine precision $\epsilon_m$ (e.g.,1.18e-38), the distortion incurred by finite bits has little effect on the ideal computations in the real space. In this case, all inputs of the compressors, which are calculated by machinery computations, naturally fall into the valid input set $\mathcal{X}$ we consider. As a result, machine precision $\epsilon_m$ does not affect our established upper bound for ADIANA. In fact, it is convection in optimization literature to ignore the effect of machine precision on the convergence rate and complexity.
-- **Lower bound**. In our paper, we established the lower bound for $\inf_{A\in\mathcal{A}}\sup_{C_i \in \mathcal{U}\_\omega} T(A, \\{C_i\\})$ where $\mathcal{A}$ is the class of algorithms defined in Definition 1, $\mathcal{U}\_\omega$ is the class of unbiased compressor defined in Assumption 2, and $T(A, \\{C_i\\})$ is the convergence complexity achieved with algorithm $A$ and compressors $C_i$'s. When we consider the new class of unbiased compressor $\mathcal{U}\_\omega^\prime$ specified by Assumption $2^\prime$, it is easy to see that $\mathcal{U}\_\omega \subseteq \mathcal{U}\_\omega^\prime$. Let $T_L$ be the lower bound of $\inf_{A\in\mathcal{A}}\sup_{C_i \in \mathcal{U}\_\omega} T(A, \\{C_i\\})$, it naturally holds that
\begin{equation}
T_L \le\inf_{A\in\mathcal{A}}\sup_{C_i \in \mathcal{U}\_\omega} T(A, \\{C_i\\}) \le \inf_{A\in\mathcal{A}}\sup_{C_i \in \mathcal{U}'\_\omega} T(A, \\{C_i\\})
\end{equation}
In other words, our established lower bound also holds for the new class of unbiased compressors defined by Assumption $2^\prime$.
Since the upper bound and lower bound are not affected by the newly introduced compressor assumption up to machine precision $\epsilon_m$, they still nearly match each other. In other words, the modified family of unbiased compressors does not affect our theoretical results.
**Summary**
We really appreciate the sharp observation and useful suggestions proposed by the reviewer. It is actually a common issue in literature, and it can be practically addressed by considering finite-bit inputs only. We hope this can resolve the reviewer's concerns, and we are looking forward to the follow-up discussions.