Triadic-OCD: Asynchronous Online Change Detection with Provable Robustness, Optimality, and Convergence

Yancheng Huang, Kai Yang, Zelin Zhu, Leian Chen
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:20382-20412, 2024.

Abstract

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 $\epsilon$-optimal point is derived. Extensive experiments have been conducted to elucidate the effectiveness of the proposed method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-huang24ad, title = {Triadic-{OCD}: Asynchronous Online Change Detection with Provable Robustness, Optimality, and Convergence}, author = {Huang, Yancheng and Yang, Kai and Zhu, Zelin and Chen, Leian}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {20382--20412}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/huang24ad/huang24ad.pdf}, url = {https://proceedings.mlr.press/v235/huang24ad.html}, abstract = {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 $\epsilon$-optimal point is derived. Extensive experiments have been conducted to elucidate the effectiveness of the proposed method.} }
Endnote
%0 Conference Paper %T Triadic-OCD: Asynchronous Online Change Detection with Provable Robustness, Optimality, and Convergence %A Yancheng Huang %A Kai Yang %A Zelin Zhu %A Leian Chen %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-huang24ad %I PMLR %P 20382--20412 %U https://proceedings.mlr.press/v235/huang24ad.html %V 235 %X 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 $\epsilon$-optimal point is derived. Extensive experiments have been conducted to elucidate the effectiveness of the proposed method.
APA
Huang, Y., Yang, K., Zhu, Z. & Chen, L.. (2024). Triadic-OCD: Asynchronous Online Change Detection with Provable Robustness, Optimality, and Convergence. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:20382-20412 Available from https://proceedings.mlr.press/v235/huang24ad.html.

Related Material