{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:25:33Z","timestamp":1772252733072,"version":"3.50.1"},"reference-count":49,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2018,2,7]],"date-time":"2018-02-07T00:00:00Z","timestamp":1517961600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1650913"],"award-info":[{"award-number":["CCF-1650913"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1538746"],"award-info":[{"award-number":["CMMI-1538746"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1442635"],"award-info":[{"award-number":["CCF-1442635"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Sequential change-point detection when the distribution parameters are unknown is a fundamental problem in statistics and machine learning. When the post-change parameters are unknown, we consider a set of detection procedures based on sequential likelihood ratios with non-anticipating estimators constructed using online convex optimization algorithms such as online mirror descent, which provides a more versatile approach to tackling complex situations where recursive maximum likelihood estimators cannot be found. When the underlying distributions belong to a exponential family and the estimators satisfy the logarithm regret property, we show that this approach is nearly second-order asymptotically optimal. This means that the upper bound for the false alarm rate of the algorithm (measured by the average-run-length) meets the lower bound asymptotically up to a log-log factor when the threshold tends to infinity. Our proof is achieved by making a connection between sequential change-point and online convex optimization and leveraging the logarithmic regret bound property of online mirror descent algorithm. Numerical and real data examples validate our theory.<\/jats:p>","DOI":"10.3390\/e20020108","type":"journal-article","created":{"date-parts":[[2018,2,7]],"date-time":"2018-02-07T12:20:29Z","timestamp":1518006029000},"page":"108","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Sequential Change-Point Detection via Online Convex Optimization"],"prefix":"10.3390","volume":"20","author":[{"given":"Yang","family":"Cao","sequence":"first","affiliation":[{"name":"H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA"}]},{"given":"Liyan","family":"Xie","sequence":"additional","affiliation":[{"name":"H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6777-2951","authenticated-orcid":false,"given":"Yao","family":"Xie","sequence":"additional","affiliation":[{"name":"H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA"}]},{"given":"Huan","family":"Xu","sequence":"additional","affiliation":[{"name":"H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA"}]}],"member":"1968","published-online":{"date-parts":[[2018,2,7]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Siegmund, D. (1985). Sequential Analysis: Tests and Confidence Intervals, Springer.","DOI":"10.1007\/978-1-4757-1862-1"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Chen, J., and Gupta, A.K. (2000). Parametric Statistical Change Point Analysis, Birkhauser.","DOI":"10.1007\/978-1-4757-3131-6"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1080\/07474946.2013.751834","article-title":"Change-points: From sequential detection to biologu and back","volume":"23","author":"Siegmund","year":"2013","journal-title":"Seq. Anal."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Tartakovsky, A., Nikiforov, I., and Basseville, M. (2014). Sequential Analysis: Hypothesis Testing and Changepoint Detection, CRC Press.","DOI":"10.1201\/b17279"},{"key":"ref_5","unstructured":"Granjon, P. (2018, February 06). The CuSum Algorithm\u2014A Small Review. Available online: https:\/\/hal.archives-ouvertes.fr\/hal-00914697."},{"key":"ref_6","unstructured":"Basseville, M., and Nikiforov, I.V. (1993). Detection of Abrupt Changes: Theory and Application, Prentice Hall Englewood Cliffs."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2917","DOI":"10.1109\/18.737522","article-title":"Information bounds and quick detection of parameter changes in stochastic systems","volume":"44","author":"Lai","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1422","DOI":"10.1214\/009053605000000183","article-title":"Nonanticipating estimation applied to sequential analysis and changepoint detection","volume":"33","author":"Lorden","year":"2005","journal-title":"Ann. Stat."},{"key":"ref_9","unstructured":"Raginsky, M., Marcia, R.F., Silva, J., and Willett, R. (July, January 28). Sequential probability assignment via online convex programming using exponential families. Proceedings of the IEEE International Symposium on Information Theory, Seoul, Korea."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"5544","DOI":"10.1109\/TIT.2012.2201375","article-title":"Sequential anomaly detection in the presence of noise and limited feedback","volume":"58","author":"Raginsky","year":"2012","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Peel, L., and Clauset, A. (2015, January 25\u201330). Detecting change points in the large-scale structure of evolving networks. Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), Austin, TX, USA.","DOI":"10.1609\/aaai.v29i1.9574"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1109\/TSIPN.2017.2696264","article-title":"Detecting weak changes in dynamic events over networks","volume":"3","author":"Li","year":"2017","journal-title":"IEEE Trans. Signal Inf. Process. Over Netw."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi, N., and Lugosi, G. (2006). Prediction, Learning, and Games, Cambridge University Press.","DOI":"10.1017\/CBO9780511546921"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1561\/2400000013","article-title":"Introduction to online convex optimization","volume":"2","author":"Hazan","year":"2016","journal-title":"Found. Trends Optim."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2815","DOI":"10.1016\/j.jspi.2008.03.016","article-title":"Minimax optimality of the Shiryayev-Roberts change-point detection rule","volume":"138","author":"Siegmund","year":"2008","journal-title":"J. Stat. Plan. Inference"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1023\/A:1010896012157","article-title":"Relative loss bounds for on-line density estimation with the exponential family of distributions","volume":"43","author":"Azoury","year":"2001","journal-title":"Mach. Learn."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1093\/biomet\/41.1-2.100","article-title":"Continuous inspection schemes","volume":"41","author":"Page","year":"1954","journal-title":"Biometrika"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1897","DOI":"10.1214\/aoms\/1177693055","article-title":"Procedures for reacting to a change in distribution","volume":"42","author":"Lorden","year":"1971","journal-title":"Ann. Math. Stat."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1379","DOI":"10.1214\/aos\/1176350164","article-title":"Optimal stopping times for detecting changes in distributions","volume":"14","author":"Moustakides","year":"1986","journal-title":"Ann. Stat."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1137\/1108002","article-title":"On optimum methods in quickest detection problems","volume":"8","author":"Shiryaev","year":"1963","journal-title":"Theory Probab. Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1109\/TAC.1976.1101146","article-title":"A generalized likelihood ratio approach to the detection and estimation of jumps in linear systems","volume":"21","author":"Willsky","year":"1976","journal-title":"IEEE Trans. Autom. Control"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1111\/j.2517-6161.1995.tb02052.x","article-title":"Sequential changepoint detection in quality control and dynamical systems","volume":"57","author":"Lai","year":"1995","journal-title":"J. R. Stat. Soc. Ser. B"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1081\/SQA-200038994","article-title":"Likelihood ratio identities and their applications to sequential analysis","volume":"23","author":"Lai","year":"2004","journal-title":"Seq. Anal."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1080\/07474940802446244","article-title":"Sequential change-point detection procedures that are nearly optimal and computationally simple","volume":"27","author":"Lorden","year":"2008","journal-title":"Seq. Anal."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1214\/aos\/1176350373","article-title":"Average run lengths of an optimal method of detecting a change in distribution","volume":"15","author":"Pollak","year":"1987","journal-title":"Ann. Stat."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1214\/009053605000000859","article-title":"Sequential change-point detection when unknown parameter are present in the pre-change distribution","volume":"34","author":"Mei","year":"2006","journal-title":"Ann. Stat."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1137\/S0040585X97T987235","article-title":"Sequential joint detection and estimation","volume":"59","author":"Yilmaz","year":"2015","journal-title":"Theory Probab. Appl."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"5311","DOI":"10.1109\/TSP.2016.2582469","article-title":"Sequential joint detection and estimation: Optimum tests and applications","volume":"64","author":"Li","year":"2016","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2000","DOI":"10.1109\/JSAC.2014.141105","article-title":"Sequential joint spectrum sensing and channel estimation for dynamic spectrum access","volume":"32","author":"Yilmaz","year":"2014","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"5129","DOI":"10.1109\/TSP.2010.2050482","article-title":"Joint detection and estimation of multiple objects from image observations","volume":"58","author":"Vo","year":"2010","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1109\/JSTSP.2010.2040104","article-title":"Optimal joint target detection and parameter estimation by MIMO radar","volume":"4","author":"Tajer","year":"2010","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1109\/18.382015","article-title":"Optimal simultaneous detection and estimation under a false alarm constraint","volume":"41","author":"Baygun","year":"1995","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"4215","DOI":"10.1109\/TIT.2012.2184260","article-title":"Joint detection and estimation: Optimum tests and applications","volume":"58","author":"Moustakides","year":"2012","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Kotlowski, W., and Gr\u00fcnwald, P. (2011, January 9\u201311). Maximum likelihood vs. sequential normalized maximum likelihood in on-line density estimation. Proceedings of the Conference on Learning Theory (COLT), Budapest, Hungary.","DOI":"10.1109\/ITW.2012.6404734"},{"key":"ref_35","unstructured":"Anava, O., Hazan, E., Mannor, S., and Shamir, O. (2013, January 12\u201314). Online learning for time series prediction. Proceedings of the Conference on Learning Theory (COLT), Princeton, NJ, USA."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1214\/aoms\/1177730197","article-title":"Optimum character of the sequential probability ratio test","volume":"19","author":"Wald","year":"1948","journal-title":"Ann. Math. Stat."},{"key":"ref_37","first-page":"1347","article-title":"Approximation of density functions by sequences of exponential families","volume":"19","author":"Barron","year":"1991","journal-title":"Ann. Stat."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000001","article-title":"Graphical models, exponential families, and variational inference","volume":"1","author":"Wainwright","year":"2008","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0167-6377(02)00231-6","article-title":"Mirror descent and nonlinear projected subgradient methods for convex optimization","volume":"31","author":"Beck","year":"2003","journal-title":"Oper. Res. Lett."},{"key":"ref_40","unstructured":"Nemirovskii, A., Yudin, D., and Dawson, E. (1983). Problem Complexity and Method Efficiency in Optimization, Wiley."},{"key":"ref_41","first-page":"107","article-title":"Online learning and online convex optimization","volume":"4","year":"2012","journal-title":"Found. Trends\u00ae Mach. Learn."},{"key":"ref_42","unstructured":"(2018, February 06). The Implementation of the Code. Available online: http:\/\/www2.isye.gatech.edu\/~yxie77\/one-sampleupdate-code.zip."},{"key":"ref_43","unstructured":"Agarwal, A., and Duchi, J.C. (2018, February 06). Stochastic Optimization with Non-i.i.d. Noise. Available online: http:\/\/opt.kyb.tuebingen.mpg.de\/papers\/opt2011_agarwal.pdf."},{"key":"ref_44","unstructured":"Alqanoo, I.M. (2014). On the Truncated Distributions within the Exponential Family, Department of Applied Statistics, Al-Azhar University\u2014Gaza."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"670","DOI":"10.1214\/13-AOS1094","article-title":"Sequential multi-sensor change-point detection","volume":"41","author":"Xie","year":"2013","journal-title":"Ann. Stat."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1214\/10-AOAS400","article-title":"Detecting simultaneous variant intervals in aligned sequences","volume":"5","author":"Siegmund","year":"2011","journal-title":"Ann. Appl. Stat."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Lipster, R., and Shiryayev, A. (1989). Theory of Martingales, Springer.","DOI":"10.1007\/978-94-009-2438-3"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Duchi, J., Shalev-Shwartz, S., Singer, Y., and Chandra, T. (2008, January 5\u20139). Efficient projections onto the \u21131-ball for learning in high dimensions. Proceedings of the International Conference on Machine learning (ICML), Helsinki, Finland.","DOI":"10.1145\/1390156.1390191"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"6926","DOI":"10.1109\/TIT.2015.2495361","article-title":"Large-scale multi-stream quickest change detection via shrinkage post-change estimation","volume":"61","author":"Wang","year":"2015","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/2\/108\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:54:08Z","timestamp":1760194448000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/2\/108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,7]]},"references-count":49,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2018,2]]}},"alternative-id":["e20020108"],"URL":"https:\/\/doi.org\/10.3390\/e20020108","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints201709.0001.v1","asserted-by":"object"}]},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,7]]}}}