SPB Git

spb/wp28_uqo

Public
4.4 KB · 20 lines latex
1\section{Exact analysis in the exponential model and sharpness}\label{sec:exact}23Let $X_i \sim \mathrm{Exp}(\theta_0)$ in the rate parametrization. The average log-likelihood is $L_n(\theta) = \log\theta - \theta\bar X_n$, so $\thetahat_n = 1/\bar X_n$, $g_n(\theta) = 1/\theta - \bar X_n$ and $H_n(\theta) = -1/\theta^2$. The model is trivial for distributed inference, since $\sum_{i\in D_k}X_i$ is a sufficient statistic that any worker can upload, and the Hessian does not depend on the data, so that single-machine curvature is exact. It is used here because every quantity in \cref{sec:construction,sec:results} has a closed form, which makes it possible to check the assumptions, the constants and the boundary behaviour rather than assume them. The following statements are proved in \cref{app:exp} from the Gamma and Beta moments and verified symbolically in the replication package.45\begin{theorem}[Exact exponential identities and boundary behaviour]\label{thm:exponential}6Let $n\bar X_n \sim \mathrm{Gamma}(n,\theta_0)$, $\psi(x) = \theta_0 - \theta_0^2 x$ and $R_n = \thetahat_n - \theta_0 - n^{-1}\sum_i\psi(X_i) = (1-\theta_0\bar X_n)^2/\bar X_n$.7\begin{enumerate}[label=(\roman*)]8\item For $n > 2$: $\E\thetahat_n = \theta_0\,n/(n-1)$, $\Var\thetahat_n = \theta_0^2 n^2/((n-1)^2(n-2))$, $\E R_n = \theta_0/(n-1) = \theta_0\sum_{a\ge1}n^{-a}$ and $\E R_n^2 = \theta_0^2(3n+2)/(n(n-1)(n-2))$, with $\sup_{n\ge3}n^2\E R_n^2/\theta_0^2 = 33/2$. Hence \cref{ass:lin,ass:bias} hold for every $r$ with $n_0 = 3$, $C = 33\theta_0^2/2$ and $b_a = \theta_0$.9\item For any pattern with $m/s_r > 1$: $\E\Jr{r,k} - \theta_0 = \theta_0\sum_j w_j s_j/(m - s_j) = \betar\theta_0 m^{-r}(1 + O(m^{-1}))$; in particular $\E\Jr{2,k} - \theta_0 = -2\theta_0/((m-1)(m-2))$ and $\E\Jr{3,k} - \theta_0 = 8\theta_0/((m-1)(m-2)(m-4))$.10\item For $m > 4$: $\Var\Jr{2,k} = \theta_0^2\, m^2(m^2 - 6m + 17)/((m-4)(m-2)^2(m-1)^2) = \theta_0^2(m^{-1} + 4m^{-2} + O(m^{-3}))$, the same first two terms as $\Var\thetahat_m$; the variance cost of the half-block correction is $O(m^{-3})$ in this model.11\item Newton identities: $\mathcal N_N(x) = 2x - x^2\bar X_N$ and $\mathcal N_N(x) - \thetaN = -(x - \thetaN)^2/\thetaN$ exactly; after $q$ steps $\mathcal N_N^{q}(x) - \thetaN = -(x-\thetaN)^{2^q}/\thetaN^{2^q-1}$. The iteration converges iff $0 < x < 2\thetaN$ and diverges to $-\infty$ otherwise ($x = 2\thetaN$ maps to $0$ and stays there).12\item Boundary: if $m \to \infty$ and $K/N^{\alphafr{r}{q}} \to c \in (0,\infty)$, then $\sqrt N(\iter{r}{q} - \thetaN) \pto -\theta_0(\betar c^{r})^{2^q}$ for $q \ge 1$ and $\pto \betar\theta_0 c^r$ for $q = 0$; for $(r,q) = (2,1)$ the limit is $-4\theta_0 c^4$, so that $\sqrt N(\iter{2}{1} - \theta_0) \dto \mathcal N(-4\theta_0c^4, \theta_0^2)$.13\item Necessity: if $m \to \infty$ and $K/N^{\alphafr{r}{q}} \to \infty$, then $\sqrt N\,\abs{\iter{r}{q} - \thetaN} \pto \infty$.14\end{enumerate}15\end{theorem}1617Items (v)--(vi) show that the exponent of \cref{thm:frontier} is sharp for the construction in this model: the small-$o$ cannot be weakened to $O$, and beyond the frontier the estimator is not $\sqrt N$-consistent for $\thetaN$. Three qualifications matter. The boundary regime $m \asymp N^{1/(2^{q+1}r)}$ is extremely slow to reach---for $(2,1)$, $m \asymp N^{1/8}$, so that $m \le 16$ for all $N \le 2^{24}$---and the finite-$m$ bias $-2\theta_0/((m-1)(m-2))$ exceeds its asymptotic form $-2\theta_0 m^{-2}$ by a factor $m^2/((m-1)(m-2))$ that is $1.5$ at $m = 6$; \cref{sec:mc} therefore reports both the limit and the exact finite-$m$ prediction. The sharpness is for this estimator family: it is not a lower bound over all distributed procedures, as pooling $\sum_i X_i$ shows. And the signs alternate: $\beta_2 = -2 < 0 < \beta_3 = 8$, so the higher-order pilot over-corrects where the half-block pilot under-corrects, a reason why finite-sample accuracy is not monotone in $r$.1819Item (iv) also gives an explicit failure gallery. Because the weights have negative entries, $\Jr{r,k}$ can be negative when a sub-block average is small; the pilot then lies outside the basin $(0, 2\thetaN)$ with positive probability for every finite $m$, and the Newton iteration diverges rather than converges. The probability is negligible for $m \ge 32$ and visible for $m \le 8$ in \cref{sec:mc}, where such replications are reported, not discarded. A production implementation would damp or project the step; the theory above describes the undamped map.20
Files · 1ae646dc989aa524829d12cef2c3022d9e30261f
Menu

Theme