AuthorsR. Money, J. Krishnan and B. Beferull-Lozano
TitleSparse Online Learning with Kernels using Random Features for Estimating Nonlinear Dynamic Graphs
AfilliationMachine Learning
Project(s)Signal and Information Processing for Intelligent Systems
Publication TypeJournal Article
Year of Publication2023
JournalIEEE Transactions on Signal Processing
Date Published06/2023
Other NumbersPrint ISSN: 1053-587X

Online topology estimation of graph-connected time series is challenging in practice, particularly because the dependencies between the time series in many real-world scenarios are nonlinear. To address this challenge, we introduce a novel kernel-based algorithm for online graph topology estimation. Our proposed algorithm also performs a Fourier-based random feature approximation to tackle the curse of dimensionality associated with kernel representations. Exploiting the fact that real-world networks often exhibit sparse topologies, we propose a group-Lasso based optimization framework, which is solved using an iterative composite objective mirror descent method, yielding an online algorithm with fixed computational complexity per iteration. We provide theoretical guarantees for our algorithm and prove that it can achieve sublinear dynamic regret under certain reasonable assumptions. In experiments conducted on both real and synthetic data, our method outperforms existing state-of-the-art competitors.


This work is a joint collaboration between SimulaMet and University of Agder. This work was supported by the IKTPLUSS INDURB grant 270730/O70 and the SFI Offshore Mechatronics grant 237896/O30 from the Research Council of Norway. 

Citation Key28392

Contact person