Triadic-OCD: Asynchronous Online Change Detection with Provable Robustness, Optimality, and Convergence
This work addresses the need for robust and efficient change detection in applications like security in smart grids and intrusion detection, offering a novel asynchronous distributed approach to mitigate practical limitations.
The paper tackles the problem of online change detection (OCD) in data streams, where prior methods assume precise system parameters, which is often impractical. It proposes a triadic-OCD framework that achieves provable robustness, optimality, and convergence, with extensive experiments demonstrating its effectiveness.
The primary goal of online change detection (OCD) is to promptly identify changes in the data stream. OCD problem find a wide variety of applications in diverse areas, e.g., security detection in smart grids and intrusion detection in communication networks. Prior research usually assumes precise knowledge of the system parameters. Nevertheless, this presumption often proves unattainable in practical scenarios due to factors such as estimation errors, system updates, etc. This paper aims to take the first attempt to develop a triadic-OCD framework with certifiable robustness, provable optimality, and guaranteed convergence. In addition, the proposed triadic-OCD algorithm can be realized in a fully asynchronous distributed manner, easing the necessity of transmitting the data to a single server. This asynchronous mechanism could also mitigate the straggler issue that faced by traditional synchronous algorithm. Moreover, the non-asymptotic convergence property of Triadic-OCD is theoretically analyzed, and its iteration complexity to achieve an $ε$-optimal point is derived. Extensive experiments have been conducted to elucidate the effectiveness of the proposed method.