Bandit Change-Point Detection for Real-Time Monitoring High-Dimensional Data Under Sampling Control

References

• Agrawal, S., and Goyal, N. (2012), “Analysis of Thompson Sampling for the Multi-Armed Bandit Problem,” in Proceedings of the 25th Annual Conference on Learning Theory, pp. 39.1–39.26.
   Google Scholar
• Agrawal, S., and Goyal, N. (2013), “Thompson Sampling for Contextual Bandits with Linear Payoffs,” in Proceedings of the 30th International Conference on Machine Learning, pp. 127–135.
   Google Scholar
• Anantharam, V., Varaiya, P., and Walrand, J. (1987), “Asymptotically Efficient Allocation Rules for the Multiarmed Bandit Problem with Multiple plays-Part I: IID Rewards,” IEEE Transactions on Automatic Control, 32, 968–976. DOI: 10.1109/TAC.1987.1104491.
   Web of Science ®Google Scholar
• Bass, T. (1999), “Multisensor Data Fusion for Next Generation Distributed Intrusion Detection Systems,” in Proceedings of the IRIS National Symposium on Sensor and Data Fusion (Vol. 24), pp. 24–27.
   Google Scholar
• Basseville, M., and Nikiforov, I. V. (1993), Detection of Abrupt Changes: Theory and Application, Englewood Cliffs, NJ: Prentice Hall.
   Google Scholar
• Bubeck, S., and Cesa-Bianchi, N. (2012), “Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit Problems,” Foundations and Trends[textregistered] in Machine Learning, 5, 1–122. DOI: 10.1561/2200000024.
   Google Scholar
• Cao, Y., Wen, Z., Kveton, B., and Xie, Y. (2019), “Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit,” in The 22nd International Conference on Artificial Intelligence and Statistics, pp. 418–427. PMLR.
   Google Scholar
• Chan, H. P. (2017), “Optimal Sequential Detection in Multi-Stream Data,” The Annals of Statistics, 45, 2736–2763. DOI: 10.1214/17-AOS1546.
   Web of Science ®Google Scholar
• Chapelle, O., and Li, L. (2011), “An Empirical Evaluation of Thompson Sampling,” in Advances in Neural Information Processing Systems, pp. 2249–2257.
   Google Scholar
• Cho, H., and Fryzlewicz, P. (2015), “Multiple-Change-Point Detection for High Dimensional Time Series via Sparsified Binary Segmentation,” Journal of the Royal Statistical Society, Series B, 77, 475–507. DOI: 10.1111/rssb.12079.
   Google Scholar
• Chu, L., and Chen, H. (2019), “Asymptotic Distribution-Free Change-Point Detection for Multivariate and Non-Euclidean Data,” The Annals of Statistics, 47, 382–414. DOI: 10.1214/18-AOS1691.
   Web of Science ®Google Scholar
• Ding, Y., Elsayed, E. A., Kumara, S., Lu, J.-C., Niu, F., and Shi, J. (2006), “Distributed Sensing for Quality and Productivity Improvements,” IEEE Transactions on Automation Science and Engineering, 3, 344–359. DOI: 10.1109/TASE.2006.876610.
   Web of Science ®Google Scholar
• Ghatak, G. (2020), “A Change-Detection based Thompson Sampling Framework for Non-stationary Bandits,” IEEE Transactions on Computers, 70, 1670–1676. DOI: 10.1109/TC.2020.3022634.
   Web of Science ®Google Scholar
• Gittins, J., Glazebrook, K., and Weber, R. (2011), Multi-Armed Bandit Allocation Indices, Chichester: Wiley.
   Google Scholar
• Gordon, L., and Pollak, M. (1995), “A Robust Surveillance Scheme for Stochastically Ordered Alternatives,” The Annals of Statistics, 23, 1350–1375. DOI: 10.1214/aos/1176324712.
   Web of Science ®Google Scholar
• Kaufmann, E., Cappé, O., and Garivier, A. (2016), “On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models,” The Journal of Machine Learning Research, 17, 1–42.
   Web of Science ®Google Scholar
• Lai, T. L. (1995), “Sequential Changepoint Detection in Quality Control and Dynamical Systems,” Journal of the Royal Statistical Society, Series B, 57, 613–644. DOI: 10.1111/j.2517-6161.1995.tb02052.x.
   Google Scholar
• Lai, T. L. (1998), “Information Bounds and Quick Detection of Parameter Changes in Stochastic Systems,” IEEE Transactions on Information Theory, 44, 2917–2929.
   Web of Science ®Google Scholar
• Lai, T. L., and Robbins, H. (1985), “Asymptotically Efficient Adaptive Allocation Rules,” Advances in Applied Mathematics, 6, 4–22. DOI: 10.1016/0196-8858(85)90002-8.
   Web of Science ®Google Scholar
• Li, J. (2019), “A Two-stage Online Monitoring Procedure for High-Dimensional Data Streams,” Journal of Quality Technology, 51, 392–406. DOI: 10.1080/00224065.2018.1507562.
   Web of Science ®Google Scholar
• Li, J. (2020), “Efficient Global Monitoring Statistics for High-Dimensional Data,” Quality and Reliability Engineering International, 36, 18–32. DOI: 10.1002/qre.2557.
   Web of Science ®Google Scholar
• Li, J., and Jin, J. (2010), “Optimal Sensor Allocation by Integrating Causal Models and Set-Covering Algorithms,” IIE Transactions, 42, 564–576. DOI: 10.1080/07408170903232597.
   Web of Science ®Google Scholar
• Li, W., Xiang, D., Tsung, F., and Pu, X. (2020), “A Diagnostic Procedure for High-Dimensional Data Streams via Missed Discovery Rate Control,” Technometrics, 62, 84–100. DOI: 10.1080/00401706.2019.1575284.
   Web of Science ®Google Scholar
• Liu, K., Mei, Y., and Shi, J. (2015), “An Adaptive Sampling Strategy for Online High-Dimensional Process Monitoring,” Technometrics, 57, 305–319. DOI: 10.1080/00401706.2014.947005.
   Web of Science ®Google Scholar
• Liu, K., Zhang, R., and Mei, Y. (2019), “Scalable Sum-shrinkage Schemes for Distributed Monitoring Large-Scale Data Streams,” Statistica Sinica, 29, 1–22.
   Web of Science ®Google Scholar
• Lorden, G. (1971), “Procedures for Reacting to a Change in Distribution,” The Annals of Mathematical Statistics, 42, 1897–1908. DOI: 10.1214/aoms/1177693055.
   Google Scholar
• Mei, Y. (2010), “Efficient Scalable Schemes for Monitoring a Large Number of Data Streams,” Biometrika, 97, 419–433. DOI: 10.1093/biomet/asq010.
   Web of Science ®Google Scholar
• Mei, Y. (2011), “Quickest Detection in Censoring Sensor Networks,” in Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on, pp. 2148–2152. IEEE.
   Google Scholar
• Nabhan, M., Mei, Y., and Shi, J. (2021), “Correlation-Based Dynamic Sampling for Online High-dimensional Process Monitoring,” Journal of Quality Technology, 53, 289–308. DOI: 10.1080/00224065.2020.1726717.
   Web of Science ®Google Scholar
• Pandelis, D. G., and Teneketzis, D. (1999), “On the Optimality of the Gittins Index Rule for Multi-armed Bandits with Multiple Plays,” Mathematical Methods of Operations Research, 50, 449–461. DOI: 10.1007/s001860050080.
   Web of Science ®Google Scholar
• Pollak, M. (1985), “Optimal Detection of a Change in Distribution,” The Annals of Statistics, 13, 206–227. DOI: 10.1214/aos/1176346587.
   Web of Science ®Google Scholar
• Pollak, M. (1987), “Average Run Lengths of an Optimal Method of Detecting a Change in Distribution,” The Annals of Statistics, 15, 749–779.
   Web of Science ®Google Scholar
• Poor, H. V., and Hadjiliadis, O. (2008), Quickest Detection, Cambridge: Cambridge University Press.
   Google Scholar
• Robbins, H. (1952), “Some Aspects of the Sequential Design of Experiments,” Bulletin of the American Mathematical Society, 58, 527–535. DOI: 10.1090/S0002-9904-1952-09620-8.
   Web of Science ®Google Scholar
• Robbins, H. (1985), “Some Aspects of the Sequential Design of Experiments,” in Herbert Robbins Selected Papers, pp. 169–177. Springer.
   Google Scholar
• Roberts, S. (1966), “A Comparison of Some Control Chart Procedures,” Technometrics, 8, 411–430. DOI: 10.1080/00401706.1966.10490374.
   Web of Science ®Google Scholar
• Scott, S. L. (2010), “A Modern Bayesian Look at the Multi-Armed Bandit,” Applied Stochastic Models in Business and Industry, 26, 639–658. DOI: 10.1002/asmb.874.
   Web of Science ®Google Scholar
• Shiryaev, A. N. (1963), “On Optimum Methods in Quickest Detection Problems,” Theory of Probability & Its Applications, 8, 22–46.
   Google Scholar
• Tartakovsky, A., Nikiforov, I., and Basseville, M. (2014), Sequential Analysis: Hypothesis Testing and Changepoint Detection, Boca Raton, FL: Chapman and Hall/CRC.
   Google Scholar
• Thompson, W. R. (1933), “On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples,” Biometrika, 25, 285–294. DOI: 10.1093/biomet/25.3-4.285.
   Google Scholar
• Viswanath, B., Bashir, M. A., Crovella, M., Guha, S., Gummadi, K. P., Krishnamurthy, B., and Mislove, A. (2014), “Towards Detecting Anomalous User Behavior in Online Social Networks,” in 23rd USENIX security symposium (USENIX security 14), pp. 223–238.
   Google Scholar
• Wang, A., Xian, X., Tsung, F., and Liu, K. (2018), “A Spatial-Adaptive Sampling Procedure for Online Monitoring of Big Data Streams,” Journal of Quality Technology, 50, 329–343. DOI: 10.1080/00224065.2018.1507560.
   Web of Science ®Google Scholar
• Wang, Y., and Mei, Y. (2015), “Large-Scale Multi-Stream Quickest Change Detection via Shrinkage Post-change Estimation,” IEEE Transactions on Information Theory, 61, 6926–6938. DOI: 10.1109/TIT.2015.2495361.
   Web of Science ®Google Scholar
• Wu, Y. (2019), “A Combined SR-CUSUM Procedure for Detecting Common Changes in Panel Data,” Communication in Statistics: Theory and Methods, 48, 4302–4319. DOI: 10.1080/03610926.2018.1494285.
   Web of Science ®Google Scholar
• Xian, X., Wang, A., and Liu, K. (2018), “A Nonparametric Adaptive Sampling Strategy for Online Monitoring of Big Data Streams,” Technometrics, 60, 14–25. DOI: 10.1080/00401706.2017.1317291.
   Web of Science ®Google Scholar
• Xian, X., Zhang, C., Bonk, S., and Liu, K. (2021), “Online Monitoring of Big Data Streams: A Rank-based Sampling Algorithm by Data Augmentation,” Journal of Quality Technology, 53, 135–153. DOI: 10.1080/00224065.2019.1681924.
   Web of Science ®Google Scholar
• Xie, Y., Huang, J., and Willett, R. (2013), “Change-Point Detection for High-Dimensional Time Series with Missing Data,” IEEE Journal of Selected Topics in Signal Processing, 7, 12–27. DOI: 10.1109/JSTSP.2012.2234082.
   Web of Science ®Google Scholar
• Xie, Y., and Siegmund, D. (2013), “Sequential Multi-Sensor Change-Point Detection,” The Annals of Statistics, 41, 670–692. DOI: 10.1214/13-AOS1094.
   Web of Science ®Google Scholar
• Yang, S., Santillana, M., and Kou, S. C. (2015), “Accurate Estimation of Influenza Epidemics Using Google Search Data via Argo,” Proceedings of the National Academy of Sciences, 112, 14473–14478. DOI: 10.1073/pnas.1515373112.
   PubMed Web of Science ®Google Scholar
• Zhang, C., and Hoi, S. C. H. (2019), “Paritally Observable Multi-Sensor Sequential Change Detection: A Combinatorial Multi-armed Bandit Approach,” in Proceedings of the Thirty-Third AAAAI Conference on Artificial Intelligence (AAAI-19) (Vol. 33), pp. 5733–5740. DOI: 10.1609/aaai.v33i01.33015733.
   Google Scholar
• Zhang, N. R., and Siegmund, D. O. (2012), “Model Selection for High-Dimensional, Multi-Sequence Change-Point Problems,” Statistica Sinica, 22, 1507–1538. DOI: 10.5705/ss.2010.257.
   Web of Science ®Google Scholar
• Zhao, Q. (2019), Multi-Armed Bandits: Theory and Applications to Online Learning in Networks (Synthesis Lectures on Communication Networks), San Rafael, CA: Morgan & Claypool Publishers. DOI: 10.2200/S00941ED2V01Y201907CNT022.
   Google Scholar
• Zou, C., and Qiu, P. (2009), “Multivariate Statistical Process Control Using Lasso,” Journal of the American Statistical Association, 104, 1586–1596. DOI: 10.1198/jasa.2009.tm08128.
   Web of Science ®Google Scholar
• Zou, C., Wang, Z., Zi, X., and Jiang, W. (2015), “An Efficient Online Monitoring Method for High-Dimensional Data Streams,” Technometrics, 57, 374–387. DOI: 10.1080/00401706.2014.940089.
   Web of Science ®Google Scholar