Multifold Confidence Intervals in Collaborative Mean Estimation (ColME) Using Sample Statistics

1. Problem Definition

The paper addresses the challenge of Collaborative Mean Estimation (ColME) in decentralized, heterogeneous environments, such as the Internet of Things (IoT) and Federated Learning (FL).

• Context: Agents (devices) generate data from personalized distributions. While collaboration accelerates learning, agents can only benefit from sharing data with others belonging to the same similarity class (i.e., agents sharing the same underlying data distribution).
• The Core Challenge: In online settings, the similarity classes are unknown a priori. Agents must identify which neighbors belong to their class in real-time.
• Limitations of Existing Methods: Previous ColME approaches (e.g., standard ColME, C-colME, B-colME) rely primarily on confidence intervals (CIs) of the sample mean to determine similarity. This fails in complex scenarios where:
  1. Different classes have similar means but different variances.
  2. Different classes have similar means and variances but different distribution shapes (e.g., Gaussian vs. Uniform).
• Goal: Develop a framework that utilizes higher-order statistics (variance and kurtosis) to construct multifold confidence intervals, enabling accurate class separation even when means are indistinguishable.

2. Methodology

The proposed framework introduces a unified procedure for estimating sample mean, sample variance, and sample kurtosis locally and collaboratively, without relying on the final mean estimate during the variance/kurtosis calculation phase.

A. Mean-Independent Variance Estimation

To avoid circular dependency (where variance estimation requires the mean, which is the unknown target), the author proposes a mean-invariant estimator:

• Difference Variable: Define $d_a(t) = x_a(t) - x_a(t-1)$. Since the true mean $\mu_a$ is constant, $E[d_a(t)] = 0$.
• Variance Relation: $E[d_a(t)^2] = 2\sigma^2$.
• Estimator: The variance is estimated using the squared differences of consecutive samples:
  $$\hat{\sigma}_a^2(t) = \frac{1}{2t} \sum_{\tau=1}^{t} (x_a(\tau) - x_a(\tau-1))^2$$
• Collaboration: Agents can share these difference-based statistics within their neighborhood to improve accuracy, even if their means differ, because the difference variable has a zero mean for all agents.

B. Kurtosis Estimation

Similarly, the paper derives a method to estimate the central fourth moment and kurtosis ($\kappa$) without explicit knowledge of the mean:

• Relation: $E[(x(t) - x(t-1))^4]$ relates to the fourth central moment and variance.
• Estimator:
  $$\hat{\kappa}_a(t) = \frac{1}{2t\hat{\sigma}_a^4(t)} \sum_{\tau=1}^{t} (x_a(\tau) - x_a(\tau-1))^4 - 3$$
• This allows distinguishing distributions with identical means and variances but different tail behaviors (e.g., Gaussian $\kappa=3$ vs. Uniform $\kappa=1.8$).

C. Multifold Confidence Intervals

The paper constructs a multidimensional similarity check using three simultaneous confidence intervals:

1. Mean CI: $I_a(t) = [\bar{x}_a(t) \pm \beta_\delta(t)]$
2. Standard Deviation CI: $I_\sigma^a(t) = [\hat{\sigma}_a(t) \pm \beta_\delta(t)]$
3. Kurtosis CI: $I_\kappa^a(t) = [\hat{\kappa}_a(t) \pm z_\delta \sqrt{24/t}]$

Decision Rule: Two agents are considered to be in the same similarity class if all three corresponding confidence intervals intersect. If any pair of intervals (Mean-Mean, SD-SD, or Kurtosis-Kurtosis) fails to intersect, the link is pruned.

D. Weighted Graphs for Robustness

To prevent "false pruning" (disconnecting agents prematurely due to statistical noise) while maintaining fast convergence, the authors introduce weighted graphs:

• Edge weights are determined by a Gaussian kernel based on the distance between statistics relative to the confidence interval width.
• The weight is the minimum of the weights derived from mean, variance, and kurtosis distances.
• This allows agents to remain connected with reduced influence if they are near the boundary of a confidence interval, rather than being abruptly disconnected.

3. Key Contributions

1. Mean-Independent Variance/Kurtosis Estimators: Novel online estimators that do not require the true mean, enabling real-time variance and kurtosis calculation in decentralized settings.
2. Multifold Confidence Intervals: A theoretical extension of ColME that incorporates standard deviation and kurtosis into the similarity detection mechanism. This solves the "identical mean, different distribution" problem.
3. Theoretical Bounds: Derivation of the standard error for the sample standard deviation and kurtosis estimators, providing the mathematical basis for the confidence interval widths.
4. Adaptive Graph Pruning: A mechanism to dynamically identify and remove "wrong links" (connections between different classes) based on the fastest-converging statistic (mean, variance, or kurtosis) for specific class pairs.

4. Results and Numerical Verification

The paper validates the theory through extensive numerical simulations involving $N=1000$ agents using B-colME (Message-Passing) and C-colME (Consensus-Based) algorithms.

• Scenario 1: Similar Means, Different Variances:
  • Setup: Two classes with means $\approx 1.0$ but standard deviations $1.2$ vs. $1.8$.
  • Result: Mean-based CIs required $T_{sep} \approx 4265$ steps to separate. Variance-based CIs separated classes in $T_{sep} \approx 416$ steps. The proposed method achieved oracle-level Mean Squared Error (MSE) rapidly by leveraging the variance difference.
• Scenario 2: Similar Means & Variances, Different Distributions:
  • Setup: Classes with similar means and variances, but one is Bernoulli ($\kappa=1$) and the other is a sum of uniforms ($\kappa=2.7$).
  • Result: Mean and Variance CIs failed to separate the classes for a long time ($T_{sep} > 7000$). Kurtosis-based CIs successfully separated them at $T_{sep} \approx 502$.
• Scenario 3: Multiclass (4 Classes):
  • Setup: A complex mix where different pairs of classes were separable only by mean, variance, or kurtosis.
  • Result: The multifold approach successfully identified all four distinct classes. The weighted graph approach further improved convergence speed, reaching the oracle solution region around $t=1000$ (compared to $t=2000$ for unweighted graphs).
• Convergence: In all cases, the Mean Squared Error (MSE) of the proposed method converged to the "Oracle" solution (the theoretical best case where classes are known perfectly), significantly outperforming local-only estimation.

5. Significance

• Overcoming Heterogeneity: This work bridges a critical gap in Federated Learning and decentralized IoT systems. It enables collaboration in scenarios where traditional methods fail because agents cannot distinguish between "similar" and "dissimilar" peers based solely on average values.
• Higher-Order Statistics: By integrating kurtosis, the framework can detect subtle distributional differences (e.g., heavy tails vs. light tails) that are invisible to mean and variance estimators.
• Practical Applicability: The mean-independent nature of the variance/kurtosis estimators makes the algorithm robust for online, real-time applications where the true mean is constantly evolving or unknown.
• Scalability: The use of graph-based interactions (B-colME/C-colME) ensures the method scales to large networks without the computational burden of all-to-all communication.

In summary, the paper provides a rigorous mathematical framework and empirical proof that multifold confidence intervals (combining mean, variance, and kurtosis) are essential for robust collaborative learning in highly heterogeneous, decentralized environments.