{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,8]],"date-time":"2023-11-08T00:41:56Z","timestamp":1699404116049},"reference-count":39,"publisher":"MIT Press","issue":"12","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,11,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In this study, we have developed an incremental machine learning (ML) method that efficiently obtains the optimal model when a small number of instances or features are added or removed. This problem holds practical importance in model selection, such as cross-validation (CV) and feature selection. Among the class of ML methods known as linear estimators, there exists an efficient model update framework, the low-rank update, that can effectively handle changes in a small number of rows and columns within the data matrix. However, for ML methods beyond linear estimators, there is currently no comprehensive framework available to obtain knowledge about the updated solution within a specific computational complexity. In light of this, our study introduces a the generalized low-rank update (GLRU) method, which extends the low-rank update framework of linear estimators to ML methods formulated as a certain class of regularized empirical risk minimization, including commonly used methods such as support vector machines and logistic regression. The proposed GLRU method not only expands the range of its applicability but also provides information about the updated solutions with a computational complexity proportional to the number of data set changes. To demonstrate the effectiveness of the GLRU method, we conduct experiments showcasing its efficiency in performing cross-validation and feature selection compared to other baseline methods.<\/jats:p>","DOI":"10.1162\/neco_a_01619","type":"journal-article","created":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T21:31:48Z","timestamp":1697491908000},"page":"1970-2005","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":0,"title":["Generalized Low-Rank Update: Model Parameter Bounds for Low-Rank Training Data Modifications"],"prefix":"10.1162","volume":"35","author":[{"given":"Hiroyuki","family":"Hanada","sequence":"first","affiliation":[{"name":"Center for Advanced Intelligence Project, RIKEN, Tokyo 103-0027, Japan hiroyuki.hanada@riken.jp"}]},{"given":"Noriaki","family":"Hashimoto","sequence":"additional","affiliation":[{"name":"Center for Advanced Intelligence Project, RIKEN, Tokyo 103-0027, Japan noriaki.hashimoto.jv@riken.jp"}]},{"given":"Kouichi","family":"Taji","sequence":"additional","affiliation":[{"name":"Department of Mechanical Systems Engineering, Nagoya University, Nagoya 464-8603, Japan taji@nagoya-u.jp"}]},{"given":"Ichiro","family":"Takeuchi","sequence":"additional","affiliation":[{"name":"Department of Mechanical Systems Engineering, Nagoya University, Nagoya 464-8603, Japan"},{"name":"Center for Advanced Intelligence Project, RIKEN, Tokyo 103-0027, Japan ichiro.takeuchi@mae.nagoya-u.ac.jp"}]}],"member":"281","published-online":{"date-parts":[[2023,11,7]]},"reference":[{"issue":"1","key":"2023110721560071000_bib1","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF02006187","article-title":"Fast stepwise procedures of selection of variables by using AIC and BIC criteria","volume":"5","author":"An","year":"1989","journal-title":"Acta Mathematicae Applicatae Sinica"},{"key":"2023110721560071000_bib2","volume-title":"Incremental gradient, subgradient, and proximal methods for convex optimization: A survey","author":"Bertsekas","year":"2015"},{"key":"2023110721560071000_bib3","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"Boyd","year":"2004"},{"key":"2023110721560071000_bib4","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199","article-title":"LIBSVM: A library for support vector machines","volume-title":"ACM Transactions on Intelligent Systems and Technology","author":"Chang","year":"2011"},{"issue":"3","key":"2023110721560071000_bib5","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1137\/S089547980343641X","article-title":"Row modifications of a sparse Cholesky factorization","volume":"26","author":"Davis","year":"2005","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"2023110721560071000_bib6","article-title":"UCI Machine Learning Repository","author":"Dheeru","year":"2017"},{"issue":"4","key":"2023110721560071000_bib7","first-page":"667","article-title":"Safe feature elimination for the lasso and sparse supervised learning problems","volume":"8","author":"El Ghaoui","year":"2012","journal-title":"Pacific Journal of Optimization"},{"key":"2023110721560071000_bib9","first-page":"333","article-title":"Mind the duality gap: Safer rules for the lasso","volume-title":"Proceedings of the 32nd International Conference on Machine Learning","author":"Fercoq","year":"2015"},{"key":"2023110721560071000_bib10","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1145\/2783258.2783349","article-title":"Monitoring least squares models of distributed streams","volume-title":"Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Gabel","year":"2015"},{"key":"2023110721560071000_bib11","first-page":"357","article-title":"Incremental learning algorithms and applications","volume-title":"Proceedings of the 24th European Symposium on Artificial Neural Networks","author":"Gepperth","year":"2016"},{"key":"2023110721560071000_bib12","first-page":"1139","article-title":"A Swiss army infinitesimal jackknife","volume-title":"Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics","author":"Giordano","year":"2019"},{"key":"2023110721560071000_bib13","volume-title":"Matrix computations","author":"Golub","year":"1996","edition":"3rd"},{"issue":"6","key":"2023110721560071000_bib14","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.1109\/TNNLS.2016.2514360","article-title":"Label propagation via teaching- to-learn and learning-to-teach","volume":"28","author":"Gong","year":"2017","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"issue":"2","key":"2023110721560071000_bib15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/1031049","article-title":"Updating the inverse of a matrix","volume":"31","author":"Hager","year":"1989","journal-title":"SIAM Review"},{"key":"2023110721560071000_bib16","article-title":"Efficiently evaluating small data modification effect for large-scale classification in changing environment","volume-title":"Proceedings of the 32nd AAAI Conference on Artificial Intelligence","author":"Hanada","year":"2018"},{"key":"2023110721560071000_bib17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-06409-2","volume-title":"Convex analysis and minimization algorithms II: Advanced theory and bundle methods","author":"Hiriart-Urruty","year":"1993"},{"issue":"493","key":"2023110721560071000_bib18","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1198\/jasa.2011.tm10113","article-title":"VIF regression: A fast regression algorithm for large data","volume":"106","author":"Lin","year":"2011","journal-title":"Journal of the American Statistical Association"},{"key":"2023110721560071000_bib19","first-page":"289","article-title":"Safe screening with variational inequalities and its application to lasso","volume-title":"Proceedings of the 31st International Conference on Machine Learning","author":"Liu","year":"2014"},{"key":"2023110721560071000_bib20","doi-asserted-by":"crossref","first-page":"1785","DOI":"10.1145\/2939672.2939844","article-title":"Safe pattern pruning: An efficient approach for predictive pattern mining","volume-title":"Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Nakagawa","year":"2016"},{"key":"2023110721560071000_bib21","first-page":"811","article-title":"Gap safe screening rules for sparse multi-task and multi-class models","volume-title":"Advances in neural information processing systems","author":"Ndiaye","year":"2015"},{"key":"2023110721560071000_bib22","doi-asserted-by":"crossref","DOI":"10.1007\/b98874","volume-title":"Numerical optimization","author":"Nocedal","year":"1999"},{"key":"2023110721560071000_bib23","first-page":"1382","article-title":"Safe screening of non-support vectors in pathwise SVM computation","volume-title":"Proceedings of the 30th International Conference on Machine Learning","author":"Ogawa","year":"2013"},{"key":"2023110721560071000_bib24","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1145\/2783258.2783347","article-title":"Quick sensitivity analysis for incremental data modification and its application to leave-one-out CV in linear classification problems","volume-title":"Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Okumura","year":"2015"},{"key":"2023110721560071000_bib25","volume-title":"Introduction to radial basis function networks","author":"Orr","year":"1996"},{"key":"2023110721560071000_bib26","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/B978-0-444-88621-7.50011-6","article-title":"Least squares modifications with inverse factorizations: parallel implications","volume":"1","author":"Pan","year":"1990","journal-title":"Advances in Parallel Computing"},{"issue":"4","key":"2023110721560071000_bib27","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1111\/rssb.12374","article-title":"A scalable estimate of the out-of-sample prediction error via approximate leave-one-out cross-validation","volume":"82","author":"Rad","year":"2020","journal-title":"Journal of the Royal Statistical Society Series B: Statistical Methodology"},{"key":"2023110721560071000_bib28","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex analysis","author":"Rockafellar","year":"1970"},{"key":"2023110721560071000_bib29","first-page":"496","article-title":"A case study of incremental concept induction","volume-title":"Proceedings of the 5th AAAI National Conference on Artificial Intelligence","author":"Schlimmer","year":"1986"},{"key":"2023110721560071000_bib30","first-page":"1577","article-title":"Simultaneous safe screening of features and samples in doubly sparse modeling","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Shibagaki","year":"2016"},{"key":"2023110721560071000_bib31","first-page":"1666","article-title":"Regularization path of cross-validation error lower bounds","volume-title":"Advances in neural information processing systems","author":"Shibagaki","year":"2015"},{"key":"2023110721560071000_bib32","first-page":"515","article-title":"A system for incremental learning based on algorithmic probability","volume-title":"Proceedings of the 6th Israeli Conference on Artificial Intelligence, Computer Vision and Pattern Recognition","author":"Solomonoff","year":"1989"},{"issue":"1","key":"2023110721560071000_bib33","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1111\/j.1467-9868.2005.00490.x","article-title":"Sparsity and smoothness via the fused lasso","volume":"67","author":"Tibshirani","year":"2005","journal-title":"Journal of the Royal Statistical Society: Series B (Statistical Methodology)"},{"key":"2023110721560071000_bib34","first-page":"523","article-title":"Scaling SVM and least absolute deviations via exact data reduction","volume-title":"Proceedings of the 31st International Conference on Machine Learning","author":"Wang","year":"2014"},{"key":"2023110721560071000_bib35","first-page":"1053","article-title":"A safe screening rule for sparse logistic regression","volume-title":"Advances in neural information processing systems","author":"Wang","year":"2014"},{"key":"2023110721560071000_bib36","first-page":"1070","article-title":"Lasso screening rules via dual polytope projection","volume-title":"Advances in neural information processing systems, 26","author":"Wang","year":"2013"},{"issue":"1","key":"2023110721560071000_bib37","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1109\/TIP.2015.2495260","article-title":"Efficient algorithms for convolutional sparse representations","volume":"25","author":"Wohlberg","year":"2016","journal-title":"IEEE Transactions on Image Processing"},{"issue":"5","key":"2023110721560071000_bib38","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1109\/TPAMI.2016.2568185","article-title":"Screening tests for lasso problems","volume":"39","author":"Xiang","year":"2017","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2023110721560071000_bib39","volume-title":"Safe screening for support vector machines.","author":"Zimmert","year":"2015"},{"key":"2023110721560071000_bib40","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/j.ins.2020.11.031","article-title":"Fast stepwise regression based on multidimensional indexes","volume":"549","author":"\u017boga\u0142a-Siudem","year":"2021","journal-title":"Information Sciences"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/35\/12\/1970\/2168822\/neco_a_01619.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/35\/12\/1970\/2168822\/neco_a_01619.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,7]],"date-time":"2023-11-07T21:56:32Z","timestamp":1699394192000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/35\/12\/1970\/117832\/Generalized-Low-Rank-Update-Model-Parameter-Bounds"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,7]]},"references-count":39,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2023,11,7]]},"published-print":{"date-parts":[[2023,11,7]]}},"URL":"https:\/\/doi.org\/10.1162\/neco_a_01619","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"value":"0899-7667","type":"print"},{"value":"1530-888X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,12]]},"published":{"date-parts":[[2023,11,7]]}}}