Anomaly Detection in a Multi-System Setting: Theoretical and Computational Objectives

• Applicant: Professorin Dr. Alexandra Carpentier, until 9/2017
• Subject Area: Mathematics ; Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2015 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 270421702

• Final Report Year: 2024

Final Report Abstract

Anomaly detection is an interdisciplinary domain, borrowing elements from mathematics, computer science, and engineering. The main aim is to develop efficient techniques for detecting anomalous behaviour of systems. In the classical scenario a monitor receives data from a system and compares this data to a reference system with some single “normal” behaviour. Ideally no strong assumptions are made on the nature of anomalous behaviours, so the problem of anomaly detection is by essence a non parametric problem. Here I propose to study a more complex scenario, which will be referred to as multi-system anomaly detection. In this setting, reference systems can have a variety of “normal” behaviours, and moreover, there are many systems under the monitor’s surveillance, and the monitor must allocate its resources wisely among them. In this situation new theoretical and computational challenges arise. The overall objective of this proposal is to find efficient methods to solve the problem of multisystem anomaly detection. This aim will be reached by addressing the following sub-objectives. First, we will generalise the theoretical framework of anomaly detection to the broader setting of multi-system anomaly detection. Second, multi-system anomaly detection methods will be developed, by taking ideas from the non parametric testing field and applying them to the new framework. Third, we will study optimal monitoring strategies for cases where the multiple systems cannot be monitored simultaneously. Here, it is important that the monitor allocates its resources among the systems in a way that is as efficient as possible. To this end, sequential and adaptive sampling methods that target the anomaly detection problem will be designed. Since anomaly detection is a non parametric problem, elements in the theory of non parametric confidence sets will be used. Finally, the newly developed methods will be applied to practical problems: a methodological example in extreme value theory, an econometric application for speculative bubble detection and two applications in a Brain Computer Interface framework.

Publications

• “An optimal algorithm for the thresholding bandit problem.” In: International Conference on Machine Learning. PMLR. 2016, pp. 1690–1698
  A. Locatelli; M. Gutzeit & A. Carpentier
  
• “Learning relationships between data obtained independently.” In: Artificial Intelligence and Statistics. PMLR. 2016, pp. 658–666
  A. Carpentier & T. Schlüter
  
• “Tight (lower) bounds for the fixed budget best arm identification bandit problem.” In: Conference on Learning Theory. PMLR. 2016, pp. 590–604
  A. Carpentier & A. Locatelli
  
• “Adaptivity to noise parameters in nonparametric active learning.” In: Proceedings of the 2017 Conference on Learning Theory, PMLR. 2017
  A. Locatelli; A. Carpentier & S. Kpotufe
  
• “Two-sample tests for large random graphs using network statistics.” In: Conference on Learning Theory. PMLR. 2017, pp. 954–977
  D. Ghoshdastidar; M. Gutzeit; A. Carpentier & U. von Luxburg
  
• Adaptive confidence sets for matrix completion. Bernoulli, 24(4A).
  Carpentier, Alexandra; Klopp, Olga; Löffler, Matthias & Nickl, Richard
  
• Constructing Confidence Sets for the Matrix Completion Problem. Springer Proceedings in Mathematics & Statistics, 103-118.
  Carpentier, A.; Klopp, O. & Löffler, M.
  
• Minimax Euclidean separation rates for testing convex hypotheses in $\mathbb{R}^{d}$. Electronic Journal of Statistics, 12(2).
  Blanchard, Gilles; Carpentier, Alexandra & Gutzeit, Maurilio
  
• “Adaptivity to smoothness in x-armed bandits.” In: Conference on Learning Theory. PMLR. 2018, pp. 1463–1492
  A. Locatelli & A. Carpentier
  
• “An adaptive strategy for active learning with smooth decision boundary.” In: Algorithmic Learning Theory. PMLR. 2018, pp. 547–571
  A. Locatelli; A. Carpentier & S. Kpotufe
  
• Adaptive estimation of the sparsity in the Gaussian vector model. The Annals of Statistics, 47(1).
  Carpentier, Alexandra & Verzelen, Nicolas
  
• Minimax L 2-Separation Rate in Testing the Sobolev-Type Regularity of a function
  M. Gutzeit
  
• Minimax Rate of Testing in Sparse Linear Regression. Automation and Remote Control, 80(10), 1817-1834.
  Carpentier, A.; Collier, O.; Comminges, L.; Tsybakov, A. B. & Wang, Yu.
  
• Uncertainty Quantification for Matrix Compressed Sensing and Quantum Tomography Problems. Progress in Probability, 385-430.
  Carpentier, Alexandra; Eisert, Jens; Gross, David & Nickl, Richard
  
• “Active multiple matrix completion with adaptive confidence sets.” In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 1783–1791
  A. Locatelli; A. Carpentier & M. Valko
  
• “Rotting bandits are no harder than stochastic ones.” In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 2564–2572
  J. Seznec; A. Locatelli; A. Carpentier; A. Lazaric & M. Valko
  
• Two-sample hypothesis testing for inhomogeneous random graphs. The Annals of Statistics, 48(4).
  Ghoshdastidar, Debarghya; Gutzeit, Maurilio; Carpentier, Alexandra & von Luxburg, Ulrike
  
• “Linear bandits with stochastic delayed feedback.” In: International Conference on Machine Learning. PMLR. 2020, pp. 9712–9721
  C. Vernade; A. Carpentier; T. Lattimore; G. Zappella; B. Ermis & M. Brueckner
  
• Estimating minimum effect with outlier selection. The Annals of Statistics, 49(1).
  Carpentier, Alexandra; Delattre, Sylvain; Roquain, Etienne & Verzelen, Nicolas
  
• Optimal sparsity testing in linear regression model. Bernoulli, 27(2).
  Carpentier, Alexandra & Verzelen, Nicolas
  
• Total variation distance for discretely observed Lévy processes: A Gaussian approximation of the small jumps. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 57(2).
  Carpentier, Alexandra; Duval, Céline & Mariucci, Ester
  
• Estimation of the ℓ2-norm and testing in sparse linear regression with unknown variance. Bernoulli, 28(4).
  Carpentier, Alexandra; Collier, Olivier; Comminges, Laetitia; Tsybakov, Alexandre B. & Wang, Yuhao
  
• Local minimax rates for closeness testing of discrete distributions. Bernoulli, 28(2).
  Lam-Weil, Joseph; Carpentier, Alexandra & Sriperumbudur, Bharath K.
  
• Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials. Mathematical Statistics and Learning, 5(1), 1-54.
  Chhor, Julien & Carpentier, Alexandra
  
• Optimal multiple change-point detection for high-dimensional data. Electronic Journal of Statistics, 17(1).
  Pilliat, Emmanuel; Carpentier, Alexandra & Verzelen, Nicolas
  
• “Online Learning with Feedback Graphs: The True Shape of Regret
  T. Kocak & A. Carpentier