{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T00:51:43Z","timestamp":1784767903880,"version":"3.55.0"},"reference-count":42,"publisher":"MIT Press","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Neural Computation"],"published-print":{"date-parts":[[2016,4]]},"abstract":"<jats:p>Pairwise learning usually refers to a learning task that involves a loss function depending on pairs of examples, among which the most notable ones are bipartite ranking, metric learning, and AUC maximization. In this letter we study an online algorithm for pairwise learning with a least-square loss function in an unconstrained setting of a reproducing kernel Hilbert space (RKHS) that we refer to as the Online Pairwise lEaRning Algorithm (OPERA). In contrast to existing works (Kar, Sriperumbudur, Jain, &amp; Karnick, 2013 ; Wang, Khardon, Pechyony, &amp; Jones, 2012 ), which require that the iterates are restricted to a bounded domain or the loss function is strongly convex, OPERA is associated with a non-strongly convex objective function and learns the target function in an unconstrained RKHS. Specifically, we establish a general theorem that guarantees the almost sure convergence for the last iterate of OPERA without any assumptions on the underlying distribution. Explicit convergence rates are derived under the condition of polynomially decaying step sizes. We also establish an interesting property for a family of widely used kernels in the setting of pairwise learning and illustrate the convergence results using such kernels. Our methodology mainly depends on the characterization of RKHSs using its associated integral operators and probability inequalities for random variables with values in a Hilbert space.<\/jats:p>","DOI":"10.1162\/neco_a_00817","type":"journal-article","created":{"date-parts":[[2016,2,19]],"date-time":"2016-02-19T00:18:45Z","timestamp":1455841125000},"page":"743-777","source":"Crossref","is-referenced-by-count":35,"title":["Online Pairwise Learning Algorithms"],"prefix":"10.1162","volume":"28","author":[{"given":"Yiming","family":"Ying","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, State University of New York at Albany, Albany, NY 12222, U.S.A."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ding-Xuan","family":"Zhou","sequence":"additional","affiliation":[{"name":"Department of Mathematics, City University of Hong Kong, Kowloon, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","reference":[{"key":"B1","first-page":"441","volume":"10","author":"Agarwal S.","year":"2009","journal-title":"J. of Machine Learning Research"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1950-0051437-7"},{"key":"B3","volume":"26","author":"Bach F.","year":"2013","journal-title":"Advances in neural information processing systems"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1162\/153244303321897690"},{"key":"B5","author":"Bellet A.","year":"2014","journal-title":"Robustness and generalization for metric learning"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-66451-9"},{"key":"B7","author":"Bottou L.","year":"2008","journal-title":"Advances in neural information processing systems, 20"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-015-5499-7"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.833339"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-009-9109-9"},{"key":"B11","first-page":"1109","volume":"11","author":"Chechik G.","year":"2010","journal-title":"J. of Machine Learning Research"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1214\/009052607000000910"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-01-00923-5"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511618796"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-004-0134-1"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1142\/S0219530514500110"},{"key":"B17","author":"Joachims T.","year":"2002","journal-title":"Proceedings of the Eighth ACM International Conference on Knowledge Discovery and Data Mining"},{"key":"B18","first-page":"441","volume":"28","author":"Kar P.","year":"2013","journal-title":"Journal of Machine Learning Research, WICP"},{"key":"B19","author":"Lin J. H.","journal-title":"Journal of Machine Learning Research"},{"key":"B20","first-page":"2651","volume":"7","author":"Micchelli C. A.","year":"2006","journal-title":"J. of Machine Learning Research"},{"key":"B21","first-page":"2481","volume":"7","author":"Mukherjee S.","year":"2006","journal-title":"J. of Machine Learning Research"},{"key":"B22","first-page":"519","volume":"7","author":"Mukherjee S.","year":"2006","journal-title":"J. of Machine Learning Research"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176988477"},{"key":"B25","first-page":"1373","volume":"13","author":"Rejchel W.","year":"2012","journal-title":"J. of Machine Learning Research"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729586"},{"issue":"1","key":"B27","first-page":"71","volume":"28","author":"Shamir O.","year":"2013","journal-title":"Journal of Machine Learning Research, WICP"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-004-0160-z"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-006-0659-y"},{"key":"B30","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-77242-4","author":"Steinwart I.","year":"2008","journal-title":"Support vector machines"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.881713"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2332531"},{"key":"B33","first-page":"13.1","volume":"23","author":"Wang Y.","year":"2012","journal-title":"Journal of Machine Learning Research, W&CP"},{"key":"B34","author":"Wang Y.","year":"2013","journal-title":"Online learning with pairwise loss functions"},{"key":"B35","first-page":"207","volume":"10","author":"Weinberger K. Q.","year":"2009","journal-title":"J. of Machine Learning Research"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-004-0155-9"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-006-0663-2"},{"key":"B38","first-page":"1","volume":"13","author":"Ying Y.","year":"2012","journal-title":"J. of Machine Learning Research"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-006-0237-y"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.883632"},{"key":"B41","author":"Ying Y.","journal-title":"Applied and Computational Harmonic Analysis"},{"key":"B42","author":"Zhao P.","year":"2011","journal-title":"Proceedings of the 28th International Conference on Machine Learning (ICML)"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/NECO_a_00817","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T12:30:49Z","timestamp":1748781049000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/28\/4\/743-777\/8160"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["10.1162\/NECO_a_00817"],"URL":"https:\/\/doi.org\/10.1162\/neco_a_00817","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"value":"0899-7667","type":"print"},{"value":"1530-888X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4]]}}}