{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T13:44:37Z","timestamp":1774878277660,"version":"3.50.1"},"reference-count":35,"publisher":"MIT Press - Journals","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Neural Computation"],"published-print":{"date-parts":[[2014,3]]},"abstract":"<jats:p> Learning an appropriate (dis)similarity function from the available data is a central problem in machine learning, since the success of many machine learning algorithms critically depends on the choice of a similarity function to compare examples. Despite many approaches to similarity metric learning that have been proposed, there has been little theoretical study on the links between similarity metric learning and the classification performance of the resulting classifier. In this letter, we propose a regularized similarity learning formulation associated with general matrix norms and establish their generalization bounds. We show that the generalization error of the resulting linear classifier can be bounded by the derived generalization bound of similarity learning. This shows that a good generalization of the learned similarity function guarantees a good classification of the resulting linear classifier. Our results extend and improve those obtained by Bellet, Habrard, and Sebban ( 2012 ). Due to the techniques dependent on the notion of uniform stability (Bousquet &amp; Elisseeff, 2002 ), the bound obtained there holds true only for the Frobenius matrix-norm regularization. Our techniques using the Rademacher complexity (Bartlett &amp; Mendelson, 2002 ) and its related Khinchin-type inequality enable us to establish bounds for regularized similarity learning formulations associated with general matrix norms, including sparse L<jats:sup>1<\/jats:sup>-norm and mixed (2,1)-norm. <\/jats:p>","DOI":"10.1162\/neco_a_00556","type":"journal-article","created":{"date-parts":[[2013,12,9]],"date-time":"2013-12-09T17:12:13Z","timestamp":1386609133000},"page":"497-522","source":"Crossref","is-referenced-by-count":20,"title":["Guaranteed Classification via Regularized Similarity Learning"],"prefix":"10.1162","volume":"26","author":[{"given":"Zheng-Chu","family":"Guo","sequence":"first","affiliation":[{"name":"College of Engineering, Mathematics and Physical Sciences, University of Exeter, EX4 4QF, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yiming","family":"Ying","sequence":"additional","affiliation":[{"name":"College of Engineering, Mathematics and Physical Sciences, University of Exeter, EX4 4QF, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143854"},{"key":"B2","first-page":"287","volume-title":"Proceedings of the 21st Annual Conference on Learning Theory","author":"Balcan M.-F.","year":"2008"},{"key":"B4","first-page":"937","volume":"6","author":"Bar-Hillel A.","year":"2005","journal-title":"Journal of Machine Learning Research"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1162\/153244303321897690"},{"key":"B3","first-page":"1871","volume-title":"Proceedings of the 27th International Conference on Machine Learning","author":"Bellet A.","year":"2012"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1162\/153244302760200704"},{"key":"B9","first-page":"1109","volume":"11","author":"Chechik G.","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"B8","first-page":"747","volume":"10","author":"Chen Y.","year":"2009","journal-title":"Journal of Machine Learning Research"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1214\/009052607000000910"},{"key":"B11","first-page":"247","volume-title":"Proceedings of the 27th International Conference on Machine Learning","author":"Cortes C.","year":"2010"},{"key":"B12","first-page":"239","volume-title":"Proceedings of the 27th International Conference on Machine Learning","author":"Cortes C.","year":"2010"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273523"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0537-1"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2006.167"},{"key":"B15","first-page":"862","volume-title":"Advances in neural information processing systems, 22","author":"Jin R.","year":"2009"},{"key":"B17","first-page":"1865","volume":"13","author":"Kakade S. M.","year":"2012","journal-title":"Journal of Machine Learning Research"},{"key":"B16","first-page":"793","volume-title":"Advances in neural information processing systems, 21","author":"Kakade S. M.","year":"2008"},{"key":"B19","first-page":"1998","volume-title":"Advances in neural information processing systems","author":"Kar P.","year":"2011"},{"key":"B20","first-page":"215","volume-title":"Advances in neural information processing systems, 24","author":"Kar P.","year":"2012"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1015362182"},{"key":"B22","first-page":"1295","volume-title":"Proceedings of the 29th International Conference on Machine Learning","author":"Kumar A.","year":"2012"},{"key":"B23","first-page":"27","volume":"5","author":"Lanckriet G. R. G.","year":"2004","journal-title":"Journal of Machine Learning Research"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20212-4"},{"key":"B25","first-page":"1049","volume":"9","author":"Maurer A.","year":"2008","journal-title":"Journal of Machine Learning Research"},{"key":"B26","volume-title":"Surveys in combinatorics","author":"McDiarmid C.","year":"1989"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth141"},{"key":"B29","first-page":"308","volume-title":"Advances in neural information processing systems, 13","author":"Smola A. J.","year":"2001"},{"key":"B30","volume-title":"Statistical learning theory","author":"Vapnik V. N.","year":"1998"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553510"},{"key":"B32","first-page":"1473","volume-title":"Advances in neural information processing systems, 17","author":"Weinberger K. Q.","year":"2005"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2012.10.001"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1162\/0899766053491896"},{"key":"B35","first-page":"505","volume-title":"Advances in neural information processing systems","volume":"15","author":"Xing E. P.","year":"2002"},{"key":"B36","first-page":"2205","volume-title":"Advances in neural information processing systems","volume":"22","author":"Ying Y.","year":"2009"},{"key":"B37","first-page":"2214","volume-title":"Advances in neural information processing systems, 22","author":"Ying Y.","year":"2009"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/NECO_a_00556","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:40:13Z","timestamp":1615585213000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/26\/3\/497-522\/7962"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["10.1162\/NECO_a_00556"],"URL":"https:\/\/doi.org\/10.1162\/neco_a_00556","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"value":"0899-7667","type":"print"},{"value":"1530-888X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,3]]}}}