Sparse and low-rank multivariate Hawkes processes.

*(English)*Zbl 07255081Summary: We consider the problem of unveiling the implicit network structure of node interactions (such as user interactions in a social network), based only on high-frequency timestamps. Our inference is based on the minimization of the least-squares loss associated with a multivariate Hawkes model, penalized by \(\ell_1\) and trace norm of the interaction tensor. We provide a first theoretical analysis for this problem, that includes sparsity and low-rank inducing penalizations. This result involves a new data-driven concentration inequality for matrix martingales in continuous time with observable variance, which is a result of independent interest and a broad range of possible applications since it extends to matrix martingales former results restricted to the scalar case. A consequence of our analysis is the construction of sharply tuned \(\ell_1\) and trace-norm penalizations, that leads to a data-driven scaling of the variability of information available for each users. Numerical experiments illustrate the significant improvements achieved by the use of such data-driven penalizations.

##### MSC:

68T05 | Learning and adaptive systems in artificial intelligence |

PDF
BibTeX
Cite

\textit{E. Bacry} et al., J. Mach. Learn. Res. 21, Paper No. 50, 32 p. (2020; Zbl 07255081)

Full Text:
Link

##### References:

[1] | E. Bacry, S. Delattre, M. Hoffmann, and J.-F. Muzy. Modelling microstructure noise with mutually exciting point processes.Quantitative Finance, 13(1):65-77, 2013. · Zbl 1280.91073 |

[2] | E. Bacry, I. Mastromatteo, and J.-F. Muzy. Hawkes processes in finance.Market Microstructure and Liquidity, 01(01):1550005, 2015. |

[3] | E. Bacry, S. Ga¨ıffas, I. Mastromatteo, and J.-F. Muzy. Mean-field inference of hawkes point processes. Journal of Physics A: Mathematical and Theoretical, 49(17):174006, 2016a. · Zbl 1354.62004 |

[4] | E. Bacry, S. Ga¨ıffas, and J.-F. Muzy. Concentration inequalities for matrix martingales in continuous time. Probability Theory and Related Fields, 170:525-553, 2016b. |

[5] | E. Bacry, M. Bompaire, P. Deegan, S. Ga¨ıffas, and S. V. Poulsen. tick: a python library for statistical learning, with an emphasis on hawkes processes and time-dependent models.Journal of Machine Learning Research, 18(214):1-5, 2018. · Zbl 06982970 |

[6] | P. L. Bartlett and S. Mendelson. Empirical minimization.Probability Theory and Related Fields, 135(3): 311-334, 2006. · Zbl 1142.62348 |

[7] | A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems.SIAM Journal of Imaging Sciences, 2(1):183-202, 2009. · Zbl 1175.94009 |

[8] | P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of lasso and Dantzig selector.Ann. Statist., 37(4):1705-1732, 2009. · Zbl 1173.62022 |

[9] | C. Blundell, K. A Heller, and J. M. Beck. Modelling reciprocating relationships with hawkes processes. In NIPS, pages 2609-2617, 2012. |

[10] | M. Bompaire.Machine Learning based on Hawkes processes and Stochastic Optimization. PhD thesis, CMAP, Ecole polytechique, EDMH, 2018. |

[11] | M. Bompaire, E. Bacry, and S. Ga¨ıffas. Dual optimization for convex constrained objectives without the gradient-lipschitz assumption.arXiv preprint arXiv:1807.03545, 2018. |

[12] | E. J. Cand‘es and T. Tao. Decoding by linear programming.IEEE Transactions on Information Theory, 12 (51):4203-4215, 2004. · Zbl 1264.94121 |

[13] | E. J. Cand‘es and T. Tao. The power of convex relaxation: Near-optimal matrix completion.IEEE Transactions on Information Theory, 56(5), 2009. |

[14] | R. Crane and D. Sornette. Robust dynamic classes revealed by measuring the response function of a social system.Proceedings of the National Academy of Sciences, 105(41), 2008. |

[15] | N. Daneshmand, M. Rodriguez, L. Song, and B. Sch¨olkpof. Estimating diffusion network structure: Recovery conditions, sample complexity, and a soft-thresholding algorithm.ICML, 2014. |

[16] | M. Argollo de Menezes and A.-L. Barab´asi. Fluctuations in network dynamics.Phys. Rev. Lett., 92:028701, Jan 2004. doi: 10.1103/PhysRevLett.92.028701. URLhttp://link.aps.org/doi/10.1103/ PhysRevLett.92.028701. |

[17] | C. DuBois, C. Butts, and P. Smyth. Stochastic blockmodeling of relational event dynamics. InProceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, pages 238-246, 2013. |

[18] | M. Gomez-Rodriguez, J. Leskovec, and B. Sch¨olkopf. Modeling information propagation with survival theory.ICML, 2013. |

[19] | N. R. Hansen, P. Reynaud-Bouret, and V. Rivoirard. Lasso and probabilistic inequalities for multivariate point processes. Technical report, Arvix preprint, 2012. · Zbl 1375.60092 |

[20] | A. G. Hawkes. Spectra of some self-exciting and mutually exciting point processes.Biometrika, 58(1):83-90, 1971. · Zbl 0219.60029 |

[21] | T. Iwata, A. Shah, and Z. Ghahramani. Discovering latent influence in online social activities via shared cascade poisson processes. InProceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 266-274. ACM, 2013. |

[22] | V. Koltchinskii.Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: SaintFlour XXXVIII-2008, volume 2033. Springer, 2011. · Zbl 1223.91002 |

[23] | V. Koltchinskii, K. Lounici, and A. B. Tsybakov. Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion.The Annals of Statistics, 39(5):2302-2329, 2011. · Zbl 1231.62097 |

[24] | J. Leskovec.Dynamics of large networks. PhD thesis, Machine Learning Department, Carnegie Mellon University, 2008. |

[25] | J. Leskovec, L. Backstrom, and J. Kleinberg. Meme-tracking and the dynamics of the news cycle. InProceedings of the 15th ACM SIGKDD. ACM, 2009. |

[26] | A. S. Lewis. The convex analysis of unitarily invariant matrix functions.Journal of Convex Analysis, 2(1): 173-183, 1995. · Zbl 0860.15026 |

[27] | S. W. Linderman and R. P. Adams. Discovering latent network structure in point process data.arXiv preprint arXiv:1402.0914, 2014. |

[28] | P. Massart.Concentration inequalities and model selection, volume 1896. Springer, 2007. · Zbl 1170.60006 |

[29] | G. O. Mohler, M. B. Short, P. J. Brantingham, F. P. Schoenberg, and G. E. Tita. Self-exciting point process modeling of crime.Journal of the American Statistical Association, 2011. · Zbl 1396.62224 |

[30] | Y. Ogata. The asymptotic behaviour of maximum likelihood estimators for stationary point processes.Annals of the Institute of Statistical Mathematics, 30(1):243-261, 1978. · Zbl 0451.62067 |

[31] | Y. Ogata. On lewis’ simulation method for point processes.Information Theory, IEEE Transactions on, 27 (1):23-31, 1981. · Zbl 0449.60037 |

[32] | Y. Ogata. Space-time point-process models for earthquake occurrences.Annals of the Institute of Statistical Mathematics, 50(2):379-402, 1998. · Zbl 0947.62061 |

[33] | M. R. Pino, L. Landesa, J. L. Rodriguez, F. Obelleiro, and R. J. Burkholder. The generalized forwardbackward method for analyzing the scattering from targets on ocean-like rough surfaces.IEEE Transactions on Antennas and Propagation, 47(6):961-969, 1999. |

[34] | F. Ricci, L. Rokach, and B. Shapira.Introduction to recommender systems handbook. Springer, 2011. · Zbl 1214.68392 |

[35] | E. Richard, S. Ga¨ıffas, and N. Vayatis. Link prediction in graphs with autoregressive features.Journal of Machine Learning Research, 2014. |

[36] | M. Rodriguez, D. Balduzzi, and B. Sch¨olkopf. Uncovering the temporal dynamics of diffusion networks. ICML, 2011. |

[37] | J. A. Tropp. User-friendly tail bounds for sums of random matrices.Foundations of Computational Mathematics, 12(4):389-434, 2012. · Zbl 1259.60008 |

[38] | S. Van De Geer.Empirical Processes in M-estimation, volume 105. Cambridge university press Cambridge, 2000. · Zbl 1179.62073 |

[39] | S.-H. Yang and H. Zha. Mixture of mutually exciting processes for viral diffusion. InICML, 2013. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.