Finite Sample Guarantees for Distributed Online Parameter Estimation with Communication Costs
This work addresses the need for finite-sample guarantees in distributed online learning, which is incremental as it builds on existing asymptotic or regret-based approaches.
The paper tackles the problem of distributed online parameter estimation by proposing an algorithm that enables agents to improve accuracy through neighbor communication, providing non-asymptotic error bounds and demonstrating a trade-off with communication costs, including a numerical validation.
We study the problem of estimating an unknown parameter in a distributed and online manner. Existing work on distributed online learning typically either focuses on asymptotic analysis, or provides bounds on regret. However, these results may not directly translate into bounds on the error of the learned model after a finite number of time-steps. In this paper, we propose a distributed online estimation algorithm which enables each agent in a network to improve its estimation accuracy by communicating with neighbors. We provide non-asymptotic bounds on the estimation error, leveraging the statistical properties of the underlying model. Our analysis demonstrates a trade-off between estimation error and communication costs. Further, our analysis allows us to determine a time at which the communication can be stopped (due to the costs associated with communications), while meeting a desired estimation accuracy. We also provide a numerical example to validate our results.