Distributed Constrained Recursive Nonlinear Least-Squares Estimation: Algorithms and Asymptotics

Anit Kumar Sahu, Soummya Kar, José M. F. Moura, H. Vincent Poor

Abstract

This paper addresses the problem of recursive nonlinear least squares parameter estimation in multi-agent networks. In this setting, individual agents sequentially observe an independent and identically distributed (i.i.d.) time-series consisting of a nonlinear function of a true but unknown parameter, corrupted by noise. We propose a distributed recursive estimator of the consensus + innovations type, denoted as $\mathcal{CIWNLS}$. Under the proposed framework, agents update their parameter estimates at each observation sampling epoch by simultaneously processing the latest locally sensed information (innovations) and the parameter estimates from neighboring agents (consensus). Under weak conditions on network connectivity and a global observability criterion, we demonstrate that the algorithm leads to consistent parameter estimates at every agent. Furthermore, the estimator achieves order-optimal convergence rates, matching the pathwise convergence of a centralized nonlinear least squares estimator. We establish the asymptotic normality of the estimate sequence and evaluate the asymptotic covariance to benchmark performance against centralized alternatives.

Introduction

In modern large-scale systems—such as smart power grids, distributed sensor networks, and the Internet of Things (IoT)—data is generated across geographically dispersed agents. Traditionally, parameter estimation required a centralized fusion center to collect and process all raw data. However, this approach faces significant hurdles: communication bottlenecks due to high bandwidth requirements, privacy concerns regarding raw data sharing, and the risk of a single point of failure.

While linear distributed estimation is well-understood, many physical sensing models are inherently nonlinear. Furthermore, parameters are often subject to physical or logical constraints (e.g., a power voltage must stay within a specific range). This paper introduces $\mathcal{CIWNLS}$, a distributed algorithm designed to handle nonlinear, constrained estimation while maintaining the efficiency of a decentralized architecture.

The $\mathcal{CIWNLS}$ Algorithm

The core of the proposed approach is the Consensus + Innovations mechanism. Each agent in the network maintains a local estimate of the parameter and updates it recursively as new data arrives. The update consists of two primary components:

  1. Consensus: The agent communicates with its immediate neighbors to incorporate their estimates. This collaborative step ensures that information propagates through the network, allowing agents to overcome "local unobservability"—a situation where an individual sensor's data is insufficient to identify the full parameter vector.
  2. Innovations: The agent processes its own latest local observation using a gradient-descent-like step to correct its estimate based on real-time data.

To handle constraints, the algorithm incorporates a Local Projection step. After the consensus and innovation updates, the estimate is projected back onto a pre-defined feasible set $\Theta$. This ensures that the estimates remain physically or logically valid throughout the estimation process.

Mixed Time-Scales

A critical feature of $\mathcal{CIWNLS}$ is the use of decaying weight sequences. Unlike "diffusion" algorithms that use constant step sizes and often result in residual steady-state errors, $\mathcal{CIWNLS}$ employs mixed time-scales. By carefully balancing the decay rates of the consensus and innovation terms, the algorithm ensures that the influence of neighbors and local data is optimized over time, leading to asymptotic consistency.

Theoretical Contributions

The paper provides a rigorous mathematical foundation for the algorithm's performance:

  • Consistency: The authors prove that as long as the network remains connected and the system is "globally observable" (meaning the combined information of all agents is sufficient to identify the parameter), every agent's estimate will converge to the true value almost surely.
  • Order-Optimality: A major finding is that the error in the $\mathcal{CIWNLS}$ estimator decays at a rate of $1/\sqrt{t}$. This is the same rate achieved by a centralized estimator that has instantaneous access to all data across the entire network. This makes the distributed approach "order-optimal" in terms of convergence speed.
  • Asymptotic Normality: The paper establishes that the estimation error follows a normal distribution as time approaches infinity. This allows for the analytical evaluation of the asymptotic covariance, providing a metric to compare the distributed estimator's precision against the centralized gold standard.

Simulation and Results

The theoretical findings were validated using synthetic simulations involving a random geometric network of 10 agents. The agents observed a 5-dimensional parameter through nonlinear trigonometric functions, with the parameter constrained to a specific box in $\mathbb{R}^5$.

Key results from the simulation include:

  • Performance Gap: The distributed $\mathcal{CIWNLS}$ estimator exhibited an error variance only ~1.76 dB higher than the optimal centralized estimator. This small performance trade-off is a significant achievement given the massive reduction in communication overhead.
  • Computational Efficiency: Unlike previous distributed methods that required the exchange of large $M \times M$ matrices, $\mathcal{CIWNLS}$ only requires agents to communicate their $M \times 1$ parameter vectors, making it highly scalable for high-dimensional problems.

Conclusion

$\mathcal{CIWNLS}$ provides a robust framework for nonlinear parameter estimation in decentralized networks. By achieving order-optimal convergence rates and maintaining computational simplicity, it bridges the gap between local sensing and centralized processing. Future work may focus on adaptive gain refinement to further close the 1.76 dB performance gap and applying these techniques to real-world challenges such as distributed robotic localization and environmental monitoring.

Summary updated

Abstract

This paper focuses on the problem of recursive nonlinear least squares parameter estimation in multi-agent networks, in which the individual agents observe sequentially over time an independent and identically distributed (i.i.d.) time-series consisting of a nonlinear function of the true but unknown parameter corrupted by noise. A distributed recursive estimator of the \emph{consensus} + \emph{innovations} type, namely $\mathcal{CIWNLS}$, is proposed, in which the agents update their parameter estimates at each observation sampling epoch in a collaborative way by simultaneously processing the latest locally sensed information~(\emph{innovations}) and the parameter estimates from other agents~(\emph{consensus}) in the local neighborhood conforming to a pre-specified inter-agent communication topology. Under rather weak conditions on the connectivity of the inter-agent communication and a \emph{global observability} criterion, it is shown that at every network agent, the proposed algorithm leads to consistent parameter estimates. Furthermore, under standard smoothness assumptions on the local observation functions, the distributed estimator is shown to yield order-optimal convergence rates, i.e., as far as the order of pathwise convergence is concerned, the local parameter estimates at each agent are as good as the optimal centralized nonlinear least squares estimator which would require access to all the observations across all the agents at all times. In order to benchmark the performance of the proposed distributed $\mathcal{CIWNLS}$ estimator with that of the centralized nonlinear least squares estimator, the asymptotic normality of the estimate sequence is established and the asymptotic covariance of the distributed estimator is evaluated. Finally, simulation results are presented which illustrate and verify the analytical findings.
BibTeX
@article{sahu2016distributed,
  author = {Anit Kumar Sahu and Soummya Kar and José M. F. Moura and H. Vincent Poor},
  title = {{Distributed Constrained Recursive Nonlinear Least-Squares Estimation: Algorithms and Asymptotics}},
  journal = {IEEE Trans. Signal Inf. Process. Over Networks},
  year = {2016},
  url = {https://openreview.net/forum?id=AEDLj1LQbW8},
}
Figure