Discussion on the paper ‘A review of distributed statistical inference’

Abstract

Distributed statistical inferences have attracted more and more attention in recent years with the emergence of massive data. We are grateful to the authors for the excellent review of the literature in this active area. Besides the progress mentioned by the authors, we would like to discuss some additional development in this interesting area. Specifically, we focus on the balance of communication cost and the statistical efficiency of divide-and-conquer (DC) type estimators in linear discriminant analysis and hypothesis testing. It is seen that the DC approach has different behaviours in these problems, which is different from that in estimation problems. Furthermore, we discuss some issues on the statistical inferences under restricted communication budgets.

Keywords:

• Divide and conquer
• linear discriminant analysis
• hypothesis testing
• normal mean

1. Linear discriminant analysis

Linear discriminant analysis (LDA) is a classical classification method (Anderson, 2003). For simplicity, we consider the two-sample problem, assuming that $X\sim N_p({\mu }_1,\mathrm{\Sigma }),Y\sim N_p({\mu }_2,\mathrm{\Sigma }),$where ${\mu }_i\in {\mathbb{R}}^p,i=1,2$ are the mean vectors with ${\mu }_1\ne {\mu }_2$ and $\mathrm{\Sigma }\in {\mathbb{R}}^{p\times p}$ is the covariance matrix. Furthermore, assume that observations come either from X with probability ${\pi }_1$ or from Y with probability ${\pi }_2$ such that ${\pi }_1+{\pi }_2=1$. For a new observation Z, Fisher's linear discriminant rule is defined as follows: (1) $\psi \left(Z\right)=\mathbb{1}\left\{\right(Z-{\mu }_a{)}^{\mathrm{\top }}\mathrm{\Theta }{\mu }_d>\log \left({\pi }_1/{\pi }_2\right)\},$(1) where ${\mu }_a=({\mu }_1+{\mu }_2)/2$, ${\mu }_d={\mu }_1-{\mu }_2$, and $\mathrm{\Theta }={\mathrm{\Sigma }}^{-1}$ represents the precision matrix, and $\mathbb{1}\{\cdot \}$ is the indicator function. Suppose that $\{X_i,i=1,\dots ,N_1\}$ and $\{Y_i,i=1,\dots ,N_2\}$ are the independently and identically distributed copies of X and Y, respectively. Let $N=N_1+N_2$ be the total sample size and suppose that N>p. For i = 1, 2, denote ${\hat{\mu }}_i$ as the sample means, and ${\hat{\mathrm{\Sigma }}}_i$ as the sample covariance using observations $X_i$'s and $Y_i$'s, respectively. Then the estimators of ${\mu }_a,{\mu }_d$ and Θ can be defined respectively as follows $\begin{array}{rl}{\hat{\mu }}_a& =({\hat{\mu }}_1+{\hat{\mu }}_2)/2,{\hat{\mu }}_d={\hat{\mu }}_1-{\hat{\mu }}_2,\\ \hat{\mathrm{\Theta }}& =({\hat{\mathrm{\Sigma }}}_{\mathrm{p}\mathrm{o}\mathrm{o}\mathrm{l}}{)}^{-1},\end{array}$where ${\hat{\mathrm{\Sigma }}}_{\mathrm{p}\mathrm{o}\mathrm{o}\mathrm{l}}=\left(N_1/N\right){\hat{\mathrm{\Sigma }}}_1+\left(N_2/N\right){\hat{\mathrm{\Sigma }}}_2$ denotes the pooled sample covariance matrix. Then the empirical version of $\psi \left(Z\right)$, denoted as $\hat{\psi }\left(Z\right)$, can be derived by plugging in the above estimators into (1(1) $\psi \left(Z\right)=\mathbb{1}\left\{\right(Z-{\mu }_a{)}^{\mathrm{\top }}\mathrm{\Theta }{\mu }_d>\log \left({\pi }_1/{\pi }_2\right)\},$(1) ).

In a distributed setting, one has a central machine (or hub) and many local machines. Suppose that data are split randomly and evenly, and are stored at K local machines. Denote by $\{X_i^{\left(k\right)},i=1,\dots ,N_1/K\}$ and $\{Y_i^{\left(k\right)},i=1,\dots ,N_2/K\}$ the samples from two classes on the k-th local machine $k=1,\dots ,K$. Tian and Gu (2017) considered sparse LDA in the high dimensional regime in the case of ${\pi }_1={\pi }_2=1/2$, under the assumption that $\text{β}=\mathrm{\Theta }{\mu }_d$ is a sparse vector. They proposed a one-shot estimator, which is communication efficient and attains the same convergence rate as the global estimator if $K=O(\sqrt{N/\log p}/max\{s,s^{\prime }\left\}\right)$, where s and $s^{\prime }$ stand for the sparsity of some parameters.

Li and Zhao (2021) considered the distributed LDA without sparsity assumption under the settings where $p/N\to 0$ and $Kp/N\to r\in [0,1)$. Note that to compute ${\hat{\mathrm{\Sigma }}}^{-1}$, one needs to transfer p by p matrices to the central machine, of which the communication costs can be expensive. Li and Zhao (2021) proposed a two-round estimator and a one-shot estimator, defined as follows.

Denote by ${\hat{\mu }}_i^{\left(k\right)}$ the estimator of ${\mu }_i$ with data at the kth machine, for $i=1,2,$ and $k=1,\dots ,K$. The one-shot estimator considers the following decision rule, (2) $\begin{array}{rl}& {\psi }_{\mathrm{o}\mathrm{n}\mathrm{e}}\left(Z\right)=\mathbb{1}\{Z^{\mathrm{\top }}\left(K^{-1}\sum _{k=1}^K{\hat{\mathrm{\Theta }}}^{\left(k\right)}{\hat{\mu }}_d^{\left(k\right)}\right)\\ & -K^{-1}\sum _{k=1}^K({\hat{\mu }}_a^{\left(k\right)}{)}^{\mathrm{\top }}{\hat{\mathrm{\Theta }}}^{\left(k\right)}{\hat{\mu }}_d^{\left(k\right)}>\log (N_1/N_2\left)\right\},\end{array}$(2) where ${\hat{\mathrm{\Theta }}}^{\left(k\right)}=({\hat{\mathrm{\Sigma }}}_{\mathrm{p}\mathrm{o}\mathrm{o}1}^{\left(k\right)}{)}^{-1}$ is the pooled sample covariance matrix using the data at the kth machine, ${\hat{\mu }}_a^{\left(k\right)}=({\hat{\mu }}_1^{\left(k\right)}+{\hat{\mu }}_2^{\left(k\right)})/2$ and ${\hat{\mu }}_d^{\left(k\right)}={\hat{\mu }}_1^{\left(k\right)}-{\hat{\mu }}_2^{\left(k\right)}$. Note that ${\hat{\mathrm{\Theta }}}^{\left(k\right)}$ and ${\mu }_i^{\left(k\right)}$ can be computed with the data only at the kth machine and that it is sufficient to transmit the vectors ${\hat{\mathrm{\Theta }}}^{\left(k\right)}{\hat{\mu }}_d^{\left(k\right)}\in {\mathbb{R}}^p$ and the scalars $({\hat{\mu }}_a^{\left(k\right)}{)}^{\mathrm{\top }}{\hat{\mathrm{\Theta }}}^{\left(k\right)}{\hat{\mu }}_d^{\left(k\right)}$ for all k to the hub. The two-round estimator is an improved version of ${\psi }_{one}\left(Z\right)$, just replacing the local estimators ${\hat{\mu }}_a^{\left(k\right)},{\hat{\mu }}_d^{\left(k\right)}$ in (2(2) $\begin{array}{rl}& {\psi }_{\mathrm{o}\mathrm{n}\mathrm{e}}\left(Z\right)=\mathbb{1}\{Z^{\mathrm{\top }}\left(K^{-1}\sum _{k=1}^K{\hat{\mathrm{\Theta }}}^{\left(k\right)}{\hat{\mu }}_d^{\left(k\right)}\right)\\ & -K^{-1}\sum _{k=1}^K({\hat{\mu }}_a^{\left(k\right)}{)}^{\mathrm{\top }}{\hat{\mathrm{\Theta }}}^{\left(k\right)}{\hat{\mu }}_d^{\left(k\right)}>\log (N_1/N_2\left)\right\},\end{array}$(2) ) by the global ones ${\hat{\mu }}_a,{\hat{\mu }}_d$ with an additional round of communication. In fact, by transferring ${\hat{\mu }}_i^{\left(k\right)}$'s to the central hub, we can obtain ${\hat{\mu }}_i=K^{-1}\sum _{k=1}^K{\hat{\mu }}_i^{\left(k\right)}$ and consequently ${\hat{\mu }}_a=({\hat{\mu }}_1+{\hat{\mu }}_2)/2$ and ${\hat{\mu }}_d={\hat{\mu }}_1-{\hat{\mu }}_2$.

Li and Zhao (2021) compared the classification accuracy of the global estimator with those of distributed ones. They showed that when $K=o\left(N/p\right)$, both the two-round estimator and the one-shot estimator can be as good as the global one under mild conditions. Moreover, they found if $Kp/N\to r\in [0,1)$ and ${\pi }_1={\pi }_2$, the two-round estimator can be as good as the global one, but the one-shot estimator is inferior to the global one. This is an interesting result, since when $Kp/N\to r>0$, ${\hat{\mathrm{\Sigma }}}_{\mathrm{p}\mathrm{o}\mathrm{o}\mathrm{l}}^{\left(k\right)}$ is not a consistent estimator of Σ by the random matrix theory. Therefore, at the price of more communication cost, the two-round estimator achieves better statistical efficiency.

2. Hypothesis testing of the mean vectors

In this section, we discuss the DC approach in the one-sample testing problem in the distributed system. We observe that DC type test statistics always lead to the loss of power, which is different from that of point estimation where the DC type estimator can be as good as the global one.

Suppose that $X\in {\mathbb{R}}^p$ is a random vector with $E\left(X\right)=\mu$. For a given vector ${\mu }_0$, consider the hypothesis testing problem $H_0:\mu ={\mu }_0\mathrm{v}.\mathrm{s}.H_1:\mu \ne {\mu }_0.$Suppose that X follows the normal distribution $N(\mu ,\mathrm{\Sigma })$ with unknown covariance matrix Σ. Let $\{X_i,i=1,\dots ,n\}$ are independent and identically distributed copies of X. In the setting of p<n, the classical test statistic is Hotelling $T^2$ (Anderson, 2003), defined as follows, $T^2=(n-1)(\overline{X}-{\mu }_0{)}^{\mathrm{\top }}\hat{\mathrm{\Theta }}(\overline{X}-{\mu }_0),$where $\overline{X}$ denotes the sample mean and $\hat{\mathrm{\Theta }}=(\hat{\mathrm{\Sigma }}{)}^{-1}$ with $\hat{\mathrm{\Sigma }}$ being the sample covariance matrix. In high dimensional cases with p>n, the sample covariance matrix is singular and the Hotelling $T^2$ test statistic is not well defined. Many works are developed to extend the Hotelling $T^2$ to large or high dimensional regimes (Bai & Saranadasa, 1996; Srivastava & Du, 2008; Wang et al., 2015, etc.).

Du and Zhao (2021) considered the distributed version of these test statistics. Specifically, based on the DC approach, they extended the Hotelling $T^2$ statistics under the setting $Kp/n\to r\in [0,1)$ and the nonparametric test statistics of Wang et al. (2015) for high dimensional settings. The ratio of the communication cost of deriving the global test statistics over that of the distributed test statistics is of order $O\left(p^2\right)$ in the case of $Kp/n\to r\in [0,1)$, and $O\left(p\right)$ in high dimensional regimes.

They compared the power of distributed statistics with those of global ones, showing that the distributed test statistics are less efficient than those of the global ones whenever K>1. Denote by ${\text{β}}_d\left(n\right)$ and ${\text{β}}_g\left(n\right)$ the powers of the distributed and global test statistics as the function of sample size n, respectively, and define $n_g/n_d$ such that ${\text{β}}_d\left(n_d\right)={\text{β}}_g\left(n_g\right)$ as the relative efficiency. The asymptotic relative efficiencies of distributed test statistics have the order $1/\sqrt{K}$.

Hence, the story of the DC approach in the hypothesis problem above is quite different from that of the point estimation, where the mean square error (MSE) of the DC estimators can be as good as that of global ones (Lee et al., 2017; Volgushev et al., 2019; Zhang et al., 2013, etc.). On the other hand, Shi et al. (2018) and Banerjee et al. (2019) showed that, in some nonstandard problems, the DC estimators converge at a rate much faster than the global ones. These results show the different behaviours of the DC approach in statistical inferences.

3. Statistical inferences under a restricted communication budget

As discussed before, it is seen that the DC method is communication efficient compared with the global one. But the statistical efficiencies of DC estimators are inferior to the global ones in many cases. To improve the efficiency of the DC estimators, some iterative methods are proposed in the literature at the price of more communication costs. This leads to an interesting problem of how to implement statistical inferences with the given communication budgets.

For the distributed mean estimation, Garg et al. (2014) proved the bounds of the bits in communication required to achieve the minimax square loss. Zhang et al. (2013) and Braverman et al. (2016) found the minimax rate when estimating the mean vector with a restricted communication cost. Cai and Wei (2020) discussed the estimation of the mean vector of a Gaussian distribution with the restriction on communication budget.

However, how to handle the statistical problems with the restricted budget in other settings is an interesting problem for future work. For example, for the hypothesis testing problem discussed in Section 2, how to design test statistics that can achieve good statistical efficiency under a given communication budget needs further investigation.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Correction Statement

This article has been republished with minor changes. These changes do not impact the academic content of the article.