{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:10Z","timestamp":1750220650467,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,2,9]],"date-time":"2020-02-09T00:00:00Z","timestamp":1581206400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["61601290"],"award-info":[{"award-number":["61601290"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"<jats:p>Social Internet of Things has recently become a promising paradigm for augmenting the capability of humans and devices connected in the networks to provide services. In social Internet of Things network, crowdsourcing that collects the intelligence of the human crowd has served as a powerful tool for data acquisition and distributed computing. To support critical applications (e.g., a recommendation system and assessing the inequality of urban perception), in this article, we shall focus on the collaborative ranking problems for user preference prediction from crowdsourced pairwise comparisons. Based on the Bradley--Terry--Luce (BTL) model, a maximum likelihood estimation (MLE) is proposed via low-rank approach in order to estimate the underlying weight\/score matrix, thereby predicting the ranking list for each user. A novel regularized formulation with the smoothed surrogate of elementwise infinity norm is proposed in order to address the unique challenge of the coupled the non-smooth elementwise infinity norm constraint and non-convex low-rank constraint in the MLE problem. We solve the resulting smoothed rank-constrained optimization problem via developing the Riemannian trust-region algorithm on quotient manifolds of fixed-rank matrices, which enjoys the superlinear convergence rate. The admirable performance and algorithmic advantages of the proposed method over the state-of-the-art algorithms are demonstrated via numerical results. Moreover, the proposed method outperforms state-of-the-art algorithms on large collaborative filtering datasets in both success rate of inferring preference and normalized discounted cumulative gain.<\/jats:p>","DOI":"10.1145\/3372407","type":"journal-article","created":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T06:49:13Z","timestamp":1581317353000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Ranking from Crowdsourced Pairwise Comparisons via Smoothed Riemannian Optimization"],"prefix":"10.1145","volume":"14","author":[{"given":"Jialin","family":"Dong","sequence":"first","affiliation":[{"name":"ShanghaiTech University and University of Chinese Academy of Sciences, Shanghai, China"}]},{"given":"Kai","family":"Yang","sequence":"additional","affiliation":[{"name":"ShanghaiTech University and University of Chinese Academy of Sciences, Shanghai, China"}]},{"given":"Yuanming","family":"Shi","sequence":"additional","affiliation":[{"name":"ShanghaiTech University, Shanghai, China"}]}],"member":"320","published-online":{"date-parts":[[2020,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"P. A. Absil R. Mahony and R. Sepulchre. 2009. Optimization Algorithms on Matrix Manifolds. Princeton University Press.  P. A. Absil R. Mahony and R. Sepulchre. 2009. Optimization Algorithms on Matrix Manifolds. Princeton University Press.","DOI":"10.1515\/9781400830244"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOS1032"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2018.2827303"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124314"},{"key":"e_1_2_1_5_1","volume-title":"Proc. Conf. Learn. Theory (COLT\u201916)","author":"Bandeira Afonso S.","year":"2016","unstructured":"Afonso S. Bandeira , Nicolas Boumal , and Vladislav Voroninski . 2016 . On the low-rank approach for semidefinite programs arising in synchronization and community detection . In Proc. Conf. Learn. Theory (COLT\u201916) . 23--26. Afonso S. Bandeira, Nicolas Boumal, and Vladislav Voroninski. 2016. On the low-rank approach for semidefinite programs arising in synchronization and community detection. In Proc. Conf. Learn. Theory (COLT\u201916). 23--26."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/100818327"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00231-6"},{"volume-title":"In Proc. IEEE Conf. Inform. Science and Systems (CISS\u201915)","author":"Sonia","key":"e_1_2_1_8_1","unstructured":"Sonia A. Bhaskar and Adel Javanmard. 2015. 1-bit matrix completion under exact low-rank constraint . In In Proc. IEEE Conf. Inform. Science and Systems (CISS\u201915) . IEEE, 1--6. Sonia A. Bhaskar and Adel Javanmard. 2015. 1-bit matrix completion under exact low-rank constraint. In In Proc. IEEE Conf. Inform. Science and Systems (CISS\u201915). IEEE, 1--6."},{"key":"e_1_2_1_9_1","unstructured":"Srinadh Bhojanapalli Behnam Neyshabur and Nati Srebro. 2016. Global optimality of local search for low rank matrix recovery. In Adv. Neural. Inf. Process. Syst. (NIPS\u201916). 3873--3881.  Srinadh Bhojanapalli Behnam Neyshabur and Nati Srebro. 2016. Global optimality of local search for low rank matrix recovery. In Adv. Neural. Inf. Process. Syst. (NIPS\u201916). 3873--3881."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7908-2604-3_16"},{"key":"e_1_2_1_11_1","volume-title":"RTRMC: A Riemannian trust-region method for low-rank matrix completion. In Adv. Neural. Inf. Process. Syst. (NIPS\u201911). 406--414.","author":"Boumal Nicolas","year":"2011","unstructured":"Nicolas Boumal and Pierre-Antoine Absil . 2011 . RTRMC: A Riemannian trust-region method for low-rank matrix completion. In Adv. Neural. Inf. Process. Syst. (NIPS\u201911). 406--414. Nicolas Boumal and Pierre-Antoine Absil. 2011. RTRMC: A Riemannian trust-region method for low-rank matrix completion. In Adv. Neural. Inf. Process. Syst. (NIPS\u201911). 406--414."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drx080"},{"key":"e_1_2_1_13_1","volume-title":"a Matlab toolbox for optimization on manifolds. J. Mach. Learn. Res. 15 (Jan","author":"Boumal Nicolas","year":"2014","unstructured":"Nicolas Boumal , Bamdev Mishra , P.-A. Absil , and Rodolphe Sepulchre . 2014. Manopt , a Matlab toolbox for optimization on manifolds. J. Mach. Learn. Res. 15 (Jan . 2014 ), 1455--1459. Retrieved from http:\/\/www.manopt.org. Nicolas Boumal, Bamdev Mishra, P.-A. Absil, and Rodolphe Sepulchre. 2014. Manopt, a Matlab toolbox for optimization on manifolds. J. Mach. Learn. Res. 15 (Jan. 2014), 1455--1459. Retrieved from http:\/\/www.manopt.org."},{"volume-title":"Convex Optimization","author":"Boyd Stephen","key":"e_1_2_1_14_1","unstructured":"Stephen Boyd and Lieven Vandenberghe . 2004. Convex Optimization . Cambridge University Press . Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press."},{"key":"e_1_2_1_15_1","first-page":"3","article-title":"Rank analysis of incomplete block designs: I. the method of paired comparisons","volume":"39","author":"Bradley Ralph Allan","year":"1952","unstructured":"Ralph Allan Bradley and Milton E. Terry . 1952 . Rank analysis of incomplete block designs: I. the method of paired comparisons . Biometrika 39 , 3 - 4 (Dec. 1952), 324--345. Ralph Allan Bradley and Milton E. Terry. 1952. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika 39, 3-4 (Dec. 1952), 324--345.","journal-title":"Biometrika"},{"volume-title":"Recovery of sparse signals via convex programming. California Inst","author":"Candes Emmanuel","key":"e_1_2_1_16_1","unstructured":"Emmanuel Candes and Justin Romberg . 2005. &ell;1-magic : Recovery of sparse signals via convex programming. California Inst . Technol ., Pasadena, CA . Emmanuel Candes and Justin Romberg. 2005. &ell;1-magic: Recovery of sparse signals via convex programming. California Inst. Technol., Pasadena, CA."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2018.2821706"},{"key":"e_1_2_1_18_1","volume-title":"Proc. Int. Conf. Mach. Learn. (ICML\u201915)","author":"Chen Yuxin","year":"2015","unstructured":"Yuxin Chen and Changho Suh . 2015 . Spectral MLE: Top-k rank aggregation from pairwise comparisons . In Proc. Int. Conf. Mach. Learn. (ICML\u201915) . 371--380. Yuxin Chen and Changho Suh. 2015. Spectral MLE: Top-k rank aggregation from pairwise comparisons. In Proc. Int. Conf. Mach. Learn. (ICML\u201915). 371--380."},{"key":"e_1_2_1_19_1","volume-title":"Wainwright","author":"Chen Yudong","year":"2015","unstructured":"Yudong Chen and Martin J . Wainwright . 2015 . Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.03025 (2015). Yudong Chen and Martin J. Wainwright. 2015. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.03025 (2015)."},{"key":"e_1_2_1_20_1","first-page":"3","article-title":"1-bit matrix completion","volume":"3","author":"Davenport Mark A.","year":"2014","unstructured":"Mark A. Davenport , Yaniv Plan , Ewout van den Berg , and Mary Wootters . 2014 . 1-bit matrix completion . Inf. Inference 3 , 3 (Sep. 2014), 189--223. Mark A. Davenport, Yaniv Plan, Ewout van den Berg, and Mary Wootters. 2014. 1-bit matrix completion. Inf. Inference 3, 3 (Sep. 2014), 189--223.","journal-title":"Inf. Inference"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2016.2539100"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2017.2765699"},{"volume-title":"International Conference on Artificial Intelligence and Statistics. 1057--1066","author":"Heckel Reinhard","key":"e_1_2_1_23_1","unstructured":"Reinhard Heckel , Max Simchowitz , Kannan Ramchandran , and Martin J. Wainwright . 2018. Approximate ranking from pairwise comparisons . In International Conference on Artificial Intelligence and Statistics. 1057--1066 . Reinhard Heckel, Max Simchowitz, Kannan Ramchandran, and Martin J. Wainwright. 2018. Approximate ranking from pairwise comparisons. In International Conference on Artificial Intelligence and Statistics. 1057--1066."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2018.2801559"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2015.2409151"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488693"},{"key":"e_1_2_1_27_1","volume-title":"On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Unpublished Manuscript","author":"Kakade Sham","year":"2009","unstructured":"Sham Kakade , Shai Shalev-Shwartz , and Ambuj Tewari . 2009. On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Unpublished Manuscript ( 2009 ). Sham Kakade, Shai Shalev-Shwartz, and Ambuj Tewari. 2009. On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Unpublished Manuscript (2009)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2567970"},{"key":"e_1_2_1_29_1","volume-title":"Proc. Conf. Learn. Theory (COLT\u201916)","author":"Lee Jason D.","year":"2016","unstructured":"Jason D. Lee , Max Simchowitz , Michael I. Jordan , and Benjamin Recht . 2016 . Gradient descent only converges to minimizers. In 29th Annu . Proc. Conf. Learn. Theory (COLT\u201916) . 1246--1257. Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. 2016. Gradient descent only converges to minimizers. In 29th Annu. Proc. Conf. Learn. Theory (COLT\u201916). 1246--1257."},{"volume-title":"Proc. 53rd Annu. Allerton Conf. Commun., Control, Comput. IEEE, 1473--1479","author":"Lu Yu","key":"e_1_2_1_30_1","unstructured":"Yu Lu and Sahand N. Negahban . 2015. Individualized rank aggregation using nuclear norm regularization . In Proc. 53rd Annu. Allerton Conf. Commun., Control, Comput. IEEE, 1473--1479 . Yu Lu and Sahand N. Negahban. 2015. Individualized rank aggregation using nuclear norm regularization. In Proc. 53rd Annu. Allerton Conf. Commun., Control, Comput. IEEE, 1473--1479."},{"key":"e_1_2_1_31_1","volume-title":"Proc. Int. Conf. Mach. Learn. (ICML\u201911)","author":"Meyer Gilles","year":"2011","unstructured":"Gilles Meyer , Silvere Bonnabel , and Rodolphe Sepulchre . 2011 . Linear regression under fixed-rank constraints: A Riemannian approach . In Proc. Int. Conf. Mach. Learn. (ICML\u201911) . Gilles Meyer, Silvere Bonnabel, and Rodolphe Sepulchre. 2011. Linear regression under fixed-rank constraints: A Riemannian approach. In Proc. Int. Conf. Mach. Learn. (ICML\u201911)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00180-013-0464-z"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1150189"},{"key":"e_1_2_1_34_1","volume-title":"Proc. Int. Conf. Artificial Intelligence and Statistics (AISTATS\u201917)","author":"Park Dohyung","year":"2017","unstructured":"Dohyung Park , Anastasios Kyrillidis , Constantine Caramanis , and Sujay Sanghavi . 2017 . Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach . In Proc. Int. Conf. Artificial Intelligence and Statistics (AISTATS\u201917) . Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, and Sujay Sanghavi. 2017. Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach. In Proc. Int. Conf. Artificial Intelligence and Statistics (AISTATS\u201917)."},{"key":"e_1_2_1_35_1","volume-title":"Proc. Int. Conf. Mach. Learn. (ICML\u201915). 1907","author":"Park Dohyung","year":"1916","unstructured":"Dohyung Park , Joe Neeman , Jin Zhang , Sujay Sanghavi , and Inderjit S. Dhillon . 2015. Preference completion: Large-scale collaborative ranking from pairwise comparisons . In Proc. Int. Conf. Mach. Learn. (ICML\u201915). 1907 -- 1916 . Dohyung Park, Joe Neeman, Jin Zhang, Sujay Sanghavi, and Inderjit S. Dhillon. 2015. Preference completion: Large-scale collaborative ranking from pairwise comparisons. In Proc. Int. Conf. Mach. Learn. (ICML\u201915). 1907--1916."},{"volume-title":"Proc. Int. Conf. Mach. Learn. (ICML\u201905)","author":"Jasson D.","key":"e_1_2_1_36_1","unstructured":"Jasson D. M. Rennie and Nathan Srebro. 2005. Fast maximum margin matrix factorization for collaborative prediction . In Proc. Int. Conf. Mach. Learn. (ICML\u201905) . 713--719. Jasson D. M. Rennie and Nathan Srebro. 2005. Fast maximum margin matrix factorization for collaborative prediction. In Proc. Int. Conf. Mach. Learn. (ICML\u201905). 713--719."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0068400"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0123483"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2017.2773600"},{"key":"e_1_2_1_40_1","first-page":"199","article-title":"Simple, robust and optimal ranking from pairwise comparisons","volume":"18","author":"Shah Nihar B.","year":"2017","unstructured":"Nihar B. Shah and Martin J. Wainwright . 2017 . Simple, robust and optimal ranking from pairwise comparisons . J. Mach. Learn. Res. 18 , 199 (Jan. 2017), 1--199. Nihar B. Shah and Martin J. Wainwright. 2017. Simple, robust and optimal ranking from pairwise comparisons. J. Mach. Learn. Res. 18, 199 (Jan. 2017), 1--199.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2598574"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.88568"},{"key":"e_1_2_1_43_1","volume-title":"Zemel","author":"Volkovs Maksims","year":"2012","unstructured":"Maksims Volkovs and Richard S . Zemel . 2012 . Collaborative ranking with 17 parameters. In Adv. Neural. Inf. Process. Syst. (NIPS\u2019 12). 2294--2302. Maksims Volkovs and Richard S. Zemel. 2012. Collaborative ranking with 17 parameters. In Adv. Neural. Inf. Process. Syst. (NIPS\u201912). 2294--2302."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/MWC.2016.7721739"},{"key":"e_1_2_1_45_1","volume-title":"Smola","author":"Weimer Markus","year":"2008","unstructured":"Markus Weimer , Alexandros Karatzoglou , Quoc V. Le , and Alex J . Smola . 2008 . Cofi rank-maximum margin matrix factorization for collaborative ranking. In Adv. Neural. Inf. Process. Syst. (NIPS\u2019 08). 1593--1600. Markus Weimer, Alexandros Karatzoglou, Quoc V. Le, and Alex J. Smola. 2008. Cofi rank-maximum margin matrix factorization for collaborative ranking. In Adv. Neural. Inf. Process. Syst. (NIPS\u201908). 1593--1600."},{"key":"e_1_2_1_46_1","first-page":"6","article-title":"Modeling the parameter interactions in ranking SVM with low-rank approximation","volume":"31","author":"Xu Jun","year":"2018","unstructured":"Jun Xu , Wei Zeng , Yanyan Lan , Jiafeng Guo , and Xueqi Cheng . 2018 . Modeling the parameter interactions in ranking SVM with low-rank approximation . IEEE Trans. Knowl. Data Eng. 31 , 6 (Jun. 2018), 1181--1193. Jun Xu, Wei Zeng, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. 2018. Modeling the parameter interactions in ranking SVM with low-rank approximation. IEEE Trans. Knowl. Data Eng. 31, 6 (Jun. 2018), 1181--1193.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2017.2694844"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3372407","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3372407","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:21Z","timestamp":1750197741000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3372407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,9]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3372407"],"URL":"https:\/\/doi.org\/10.1145\/3372407","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2020,2,9]]},"assertion":[{"value":"2019-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}