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

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

TL;DR

This paper introduces CIWNLS, a distributed algorithm that allows a network of agents to estimate a hidden parameter from nonlinear, noisy observations. By combining local "innovations" with neighbor "consensus" and a projection step for constraints, the algorithm achieves the same convergence rate as a centralized "all-knowing" estimator while significantly reducing communication overhead.

What Problem Does This Paper Address?

In many modern systems—like power grids, sensor networks, or the Internet of Things—data is produced across a vast network of agents. Traditionally, estimating a parameter (like the state of a power grid) requires sending all raw data to a central fusion center. This is problematic because:

  1. Communication Bottlenecks: Sending raw data from every sensor is energy-intensive and slow.
  2. Privacy/Security: Agents may not want to share their local models or raw data.
  3. Local Unobservability: A single sensor often doesn't have enough information to estimate the full parameter on its own (the "local unobservability" problem).

While linear distributed estimation is well-studied, many real-world sensing models are nonlinear and the parameters are often constrained to a specific feasible set (e.g., physical limits). This paper tackles the challenge of designing a recursive (online) algorithm that handles these nonlinearities and constraints while remaining mathematically "optimal."

Methods

The authors propose the CIWNLS (Consensus + Innovations Weighted Nonlinear Least Squares) algorithm. Each agent maintains a local estimate and updates it in two main steps:

  1. Consensus + Innovations Update: The agent adjusts its estimate based on two factors:
  2. Consensus: It looks at the estimates of its immediate neighbors and moves closer to their average. This spreads information across the network.
  3. Innovations: It performs a gradient-descent-like step using its own latest local observation to correct its estimate.
  4. Local Projection: To ensure the estimate remains physically or logically valid, the agent projects the updated estimate back onto a pre-defined feasible set $\Theta$.

What’s New? Unlike "diffusion" algorithms that use constant step sizes (leading to residual errors), CIWNLS uses decaying weight sequences (mixed time-scales). The consensus and innovation terms decay at different rates, which the authors prove is essential for achieving "order-optimal" convergence—meaning the distributed network eventually performs as well as a centralized system.

Datasets

The paper relies on synthetic simulations to validate the theoretical proofs:

  • Network Topology: A random geometric network of 10 agents.
  • Sensing Model: Agents observe the parameter through nonlinear trigonometric functions (sine waves).
  • Constraints: The parameter is constrained to a specific 5-dimensional box in $\mathbb{R}^5$.
  • Comparison: The results are benchmarked against the Centralized WNLS (the gold standard) and non-collaborative (purely local) estimation.

Key Insights and Ideas

  • The Power of Connectivity: As long as the network is connected and the system is "globally observable" (the sum of all sensors' information is enough to identify the parameter), every single agent will eventually reach the correct estimate, even if they are locally "blind."
  • Order-Optimality: The authors prove that the error in CIWNLS decays at a rate of $1/\sqrt{t}$. This is the same rate achieved by centralized estimators that have access to all data at all times.
  • Mixed Time-Scales: The "secret sauce" is the specific decay rates for the weights. By balancing how fast agents listen to their neighbors versus their own sensors, the algorithm avoids the stability issues common in nonlinear distributed systems.
  • Asymptotic Normality: The paper establishes that the estimation error follows a normal distribution as time goes to infinity. This allows engineers to calculate the "confidence" or "covariance" of the estimates.

Key Results

  • Consistency: Mathematically proved that all agents' estimates converge to the true parameter value almost surely.
  • Performance Gap: In simulations, the distributed CIWNLS showed a loss of only ~1.76 dB in terms of error variance compared to the centralized optimal estimator.
  • Efficiency: The algorithm is shown to be significantly more computationally efficient than previous "asymptotically efficient" distributed methods, which required agents to communicate large matrices ($M \times M$) instead of just the parameter vector ($M \times 1$).

Limitations and Future Work

  • Suboptimal Covariance: While the rate of convergence is optimal, the actual value of the asymptotic covariance is slightly higher than a centralized estimator. The authors use "suboptimal" innovation gains to keep the algorithm simple and fast.
  • Known Covariance: The current proof assumes agents know their local noise statistics (covariance matrices) beforehand.
  • Future Directions: The authors suggest exploring adaptive gain refinement to close the 1.76 dB gap with centralized systems and applying these techniques to specific problems like distributed localization in robotics.

Summary updated

Abstract

This paper focuses on recursive nonlinear least-squares parameter estimation in multiagent networks, where the individual agents observe sequentially over time an independent and identically distributed time-series consisting of a nonlinear function of the true but unknown parameter corrupted by noise. A distributed recursive estimator of the consensus + innovations type, namely 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 (innovations) and the parameter estimates from other agents (consensus) in the local neighborhood conforming to a prespecified interagent communication topology. Under rather weak conditions on the connectivity of the interagent communication and a global observability criterion, it is shown that, at every network agent, CIWNLS 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 that requires access to all the observations across all the agents at all times. To benchmark the performance of the 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 that 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},
}

Loading related content...

Figure