{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T08:00:46Z","timestamp":1772265646529,"version":"3.50.1"},"reference-count":53,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2023,6,4]],"date-time":"2023-06-04T00:00:00Z","timestamp":1685836800000},"content-version":"am","delay-in-days":246,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Pattern Recognition"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1016\/j.patcog.2022.108688","type":"journal-article","created":{"date-parts":[[2022,4,10]],"date-time":"2022-04-10T10:01:43Z","timestamp":1649584903000},"page":"108688","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":4,"special_numbering":"C","title":["Sample complexity of rank regression using pairwise comparisons"],"prefix":"10.1016","volume":"130","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1261-3758","authenticated-orcid":false,"given":"Berkan","family":"Kad\u0131o\u011flu","sequence":"first","affiliation":[]},{"given":"Peng","family":"Tian","sequence":"additional","affiliation":[]},{"given":"Jennifer","family":"Dy","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1114-3539","authenticated-orcid":false,"given":"Deniz","family":"Erdo\u011fmu\u015f","sequence":"additional","affiliation":[]},{"given":"Stratis","family":"Ioannidis","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.patcog.2022.108688_bib0001","series-title":"Advances in Neural Information Processing Systems (NeurIPS)","first-page":"41","article-title":"Learning a distance metric from relative comparisons","author":"Schultz","year":"2004"},{"key":"10.1016\/j.patcog.2022.108688_bib0002","series-title":"International Conference on World Wide Web (WWW)","first-page":"791","article-title":"Mining interesting locations and travel sequences from GPS trajectories","author":"Zheng","year":"2009"},{"key":"10.1016\/j.patcog.2022.108688_bib0003","series-title":"ACM Conference on Recommender Systems (RecSys)","first-page":"117","article-title":"OrdRec: an ordinal model for predicting personalized item rating distributions","author":"Koren","year":"2011"},{"key":"10.1016\/j.patcog.2022.108688_bib0004","series-title":"Conditional Logit Analysis of Qualitative Choice Behavior","author":"McFadden","year":"1973"},{"issue":"11","key":"10.1016\/j.patcog.2022.108688_bib0005","doi-asserted-by":"crossref","first-page":"1496","DOI":"10.1287\/mnsc.45.11.1496","article-title":"On the relationship between inventory costs and variety benefits in retail assortments","volume":"45","author":"van Ryzin","year":"1999","journal-title":"Manage. Sci."},{"key":"10.1016\/j.patcog.2022.108688_bib0006","series-title":"International Conference on Knowledge Discovery & Data Mining (KDD)","first-page":"1809","article-title":"A severity score for retinopathy of prematurity","author":"Tian","year":"2019"},{"key":"10.1016\/j.patcog.2022.108688_bib0007","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.neunet.2019.06.004","article-title":"Classification and comparison via neural networks","volume":"118","author":"Y\u0131ld\u0131z","year":"2019","journal-title":"Neural Netw."},{"key":"10.1016\/j.patcog.2022.108688_bib0008","series-title":"Asian Conference on Machine Learning (ACML)","first-page":"599","article-title":"Variational inference from ranked samples with features","author":"Guo","year":"2019"},{"issue":"11","key":"10.1016\/j.patcog.2022.108688_bib0009","doi-asserted-by":"crossref","first-page":"2338","DOI":"10.1016\/j.ophtha.2016.07.026","article-title":"Plus disease in retinopathy of prematurity: a continuous spectrum of vascular abnormality as a basis of diagnostic variability","volume":"123","author":"Campbell","year":"2016","journal-title":"Ophthalmology"},{"issue":"11","key":"10.1016\/j.patcog.2022.108688_bib0010","doi-asserted-by":"crossref","first-page":"2345","DOI":"10.1016\/j.ophtha.2016.07.020","article-title":"Plus disease in retinopathy of prematurity: improving diagnosis by ranking disease severity and using quantitative image analysis","volume":"123","author":"Kalpathy-Cramer","year":"2016","journal-title":"Ophthalmology"},{"issue":"4","key":"10.1016\/j.patcog.2022.108688_bib0011","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1037\/0033-295X.112.4.881","article-title":"Absolute identification by relative judgment","volume":"112","author":"Stewart","year":"2005","journal-title":"Psychol. Rev."},{"key":"10.1016\/j.patcog.2022.108688_bib0012","series-title":"Asian Conference on Machine Learning (ACML)","first-page":"283","article-title":"Ordinal random fields for recommender systems","author":"Liu","year":"2014"},{"issue":"3\/4","key":"10.1016\/j.patcog.2022.108688_bib0013","doi-asserted-by":"crossref","first-page":"324","DOI":"10.2307\/2334029","article-title":"Rank analysis of incomplete block designs: I. The method of paired comparisons","volume":"39","author":"Bradley","year":"1952","journal-title":"Biometrika"},{"issue":"4","key":"10.1016\/j.patcog.2022.108688_bib0014","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1037\/h0070288","article-title":"A law of comparative judgment","volume":"34","author":"Thurstone","year":"1927","journal-title":"Psychol. Rev."},{"key":"10.1016\/j.patcog.2022.108688_bib0015","series-title":"International Conference on World Wide Web (WWW)","first-page":"613","article-title":"Rank aggregation methods for the web","author":"Dwork","year":"2001"},{"key":"10.1016\/j.patcog.2022.108688_bib0016","doi-asserted-by":"crossref","first-page":"108138","DOI":"10.1016\/j.patcog.2021.108138","article-title":"Top-rank convolutional neural network and its application to medical image-based diagnosis","volume":"120","author":"Zheng","year":"2021","journal-title":"Pattern Recognit."},{"key":"10.1016\/j.patcog.2022.108688_bib0017","series-title":"Symposium on Discrete Algorithms (SODA)","first-page":"268","article-title":"Noisy sorting without resampling","author":"Braverman","year":"2008"},{"key":"10.1016\/j.patcog.2022.108688_bib0018","series-title":"Advances in Neural Information Processing Systems (NeurIPS)","first-page":"2240","article-title":"Active ranking using pairwise comparisons","author":"Jamieson","year":"2011"},{"key":"10.1016\/j.patcog.2022.108688_bib0019","series-title":"Allerton Conference on Communication, Control, and Computing (Allerton)","first-page":"776","article-title":"Ranking: compare, don\u2019t score","author":"Ammar","year":"2011"},{"key":"10.1016\/j.patcog.2022.108688_bib0020","series-title":"Advances in Neural Information Processing Systems (NeurIPS)","first-page":"2474","article-title":"Iterative ranking from pair-wise comparisons","author":"Negahban","year":"2012"},{"key":"10.1016\/j.patcog.2022.108688_bib0021","series-title":"International Conference on Machine Learning (ICML)","first-page":"11","article-title":"Stochastically transitive models for pairwise comparisons: statistical and computational issues","author":"Shah","year":"2016"},{"key":"10.1016\/j.patcog.2022.108688_bib0022","series-title":"Conference on Learning Theory (COLT)","first-page":"1376","article-title":"When can we rank well from comparisons of O(nlog(n)) non-actively chosen pairs?","author":"Rajkumar","year":"2016"},{"key":"10.1016\/j.patcog.2022.108688_bib0023","series-title":"Advances in Neural Information Processing Systems (NeurIPS)","first-page":"1475","article-title":"Minimax-optimal inference from partial rankings","author":"Hajek","year":"2014"},{"issue":"2","key":"10.1016\/j.patcog.2022.108688_bib0024","first-page":"193","article-title":"The analysis of permutations","volume":"24","author":"Plackett","year":"1975","journal-title":"J. R. Stat. Soc. Ser. C"},{"key":"10.1016\/j.patcog.2022.108688_bib0025","series-title":"International Conference on Machine Learning (ICML)","first-page":"498","article-title":"Parameter estimation for generalized Thurstone choice models","author":"Vojnovic","year":"2016"},{"key":"10.1016\/j.patcog.2022.108688_bib0026","first-page":"137","article-title":"An active learning algorithm for ranking from pairwise preferences with an almost optimal query complexity","volume":"13","author":"Ailon","year":"2012","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"10.1016\/j.patcog.2022.108688_bib0027","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1287\/opre.2016.1534","article-title":"Rank centrality: ranking from pairwise comparisons","volume":"65","author":"Negahban","year":"2017","journal-title":"Oper. Res."},{"key":"10.1016\/j.patcog.2022.108688_bib0028","series-title":"Advances in Neural Information Processing Systems (NeurIPS)","first-page":"172","article-title":"Fast and accurate inference of Plackett\u2013Luce models","author":"Maystre","year":"2015"},{"key":"10.1016\/j.patcog.2022.108688_bib0029","series-title":"International Conference on Machine Learning (ICML)","first-page":"70","article-title":"Accelerated spectral ranking","author":"Agarwal","year":"2018"},{"issue":"3","key":"10.1016\/j.patcog.2022.108688_bib0030","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1137\/130945508","article-title":"Testing probability distributions using conditional samples","volume":"44","author":"Canonne","year":"2015","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.patcog.2022.108688_bib0031","series-title":"Symposium on Foundations of Computer Science (FOCS)","first-page":"355","article-title":"Active classification with comparison queries","author":"Kane","year":"2017"},{"issue":"2","key":"10.1016\/j.patcog.2022.108688_bib0032","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","article-title":"On the uniform convergence of relative frequencies of events to their probabilities","volume":"16","author":"Vapnik","year":"1971","journal-title":"Theory Probab. Appl."},{"key":"10.1016\/j.patcog.2022.108688_bib0033","series-title":"Advances in Neural Information Processing Systems (NeurIPS)","first-page":"4796","article-title":"Sample and computationally efficient learning algorithms under s-concave distributions","author":"Balcan","year":"2017"},{"issue":"6","key":"10.1016\/j.patcog.2022.108688_bib0034","doi-asserted-by":"crossref","first-page":"1777","DOI":"10.1137\/060649057","article-title":"Agnostically learning halfspaces","volume":"37","author":"Kalai","year":"2008","journal-title":"SIAM J. Comput."},{"issue":"6","key":"10.1016\/j.patcog.2022.108688_bib0035","doi-asserted-by":"crossref","first-page":"1808","DOI":"10.1214\/aos\/1017939240","article-title":"Smooth discrimination analysis","volume":"27","author":"Mammen","year":"1999","journal-title":"Ann. Stat."},{"key":"10.1016\/j.patcog.2022.108688_bib0036","series-title":"Conference on Learning Theory (COLT)","first-page":"152","article-title":"Learning and 1-bit compressed sensing under asymmetric noise","author":"Awasthi","year":"2016"},{"key":"10.1016\/j.patcog.2022.108688_bib0037","series-title":"Conference on Learning Theory (COLT)","first-page":"1","article-title":"Efficient active learning of sparse halfspaces","volume":"vol.\u00a075","author":"Zhang","year":"2018"},{"key":"10.1016\/j.patcog.2022.108688_bib0038","series-title":"AAAI Conference on Artificial Intelligence (AAAI)","first-page":"2436","article-title":"Inductive pairwise ranking: going beyond the nlog(n) barrier","author":"Niranjan","year":"2017"},{"key":"10.1016\/j.patcog.2022.108688_bib0039","series-title":"International Conference on Artificial Intelligence and Statistics (AISTATS)","first-page":"748","article-title":"Rank aggregation and prediction with item features","author":"Chiang","year":"2017"},{"issue":"Nov","key":"10.1016\/j.patcog.2022.108688_bib0040","first-page":"463","article-title":"Rademacher and gaussian complexities: risk bounds and structural results","volume":"3","author":"Bartlett","year":"2002","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"10.1016\/j.patcog.2022.108688_bib0041","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1051\/0004-6361:20066170","article-title":"Why your model parameter confidences might be too optimistic. Unbiased estimation of the inverse covariance matrix","volume":"464","author":"Hartlap","year":"2007","journal-title":"Astron. Astrophys."},{"key":"10.1016\/j.patcog.2022.108688_bib0042","series-title":"The Elements of Statistical Learning","author":"Friedman","year":"2001"},{"issue":"6","key":"10.1016\/j.patcog.2022.108688_bib0043","doi-asserted-by":"crossref","first-page":"1135","DOI":"10.1214\/aos\/1176345632","article-title":"Estimation of the mean of a multivariate distribution","volume":"9","author":"Stein","year":"1981","journal-title":"Ann. Stat."},{"issue":"3","key":"10.1016\/j.patcog.2022.108688_bib0044","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0167-7152(94)90121-X","article-title":"Siegel\u2019s formula via Stein\u2019s identities","volume":"21","author":"Liu","year":"1994","journal-title":"Stat. Probab. Lett."},{"issue":"1","key":"10.1016\/j.patcog.2022.108688_bib0045","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1002\/rsa.10073","article-title":"An elementary proof of a theorem of Johnson and Lindenstrauss","volume":"22","author":"Dasgupta","year":"2003","journal-title":"Random Struct. Algorithms"},{"key":"10.1016\/j.patcog.2022.108688_bib0046","series-title":"Weak Convergence and Empirical Processes: with Applications to Statistics","author":"Wellner","year":"2013"},{"issue":"301","key":"10.1016\/j.patcog.2022.108688_bib0047","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding","year":"1963","journal-title":"J. Am. Stat. Assoc."},{"key":"10.1016\/j.patcog.2022.108688_bib0048","series-title":"Compressed Sensing: Theory and Practice","first-page":"210","article-title":"Introduction to the non-asymptotic analysis of random matrices","author":"Vershynin","year":"2012"},{"issue":"52","key":"10.1016\/j.patcog.2022.108688_bib0049","first-page":"1","article-title":"A tail inequality for quadratic forms of subgaussian random vectors","volume":"17","author":"Hsu","year":"2012","journal-title":"Electron. Commun. Probab."},{"issue":"3","key":"10.1016\/j.patcog.2022.108688_bib0050","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0890-5401(89)90002-3","article-title":"A general lower bound on the number of examples needed for learning","volume":"82","author":"Ehrenfeucht","year":"1989","journal-title":"Inf. Comput."},{"key":"10.1016\/j.patcog.2022.108688_bib0051","series-title":"Conference on Learning Theory (COLT)","first-page":"288","article-title":"Active and passive learning of linear separators under log-concave distributions","author":"Balcan","year":"2013"},{"issue":"2","key":"10.1016\/j.patcog.2022.108688_bib0052","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1006\/inco.1994.1097","article-title":"Predicting {0, 1}-functions on randomly drawn points","volume":"115","author":"Haussler","year":"1994","journal-title":"Inf. Comput."},{"key":"10.1016\/j.patcog.2022.108688_bib0053","series-title":"High-Dimensional Probability: An Introduction with Applications in Data Science","author":"Vershynin","year":"2018"}],"container-title":["Pattern Recognition"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0031320322001698?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0031320322001698?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T17:04:31Z","timestamp":1758474271000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0031320322001698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10]]},"references-count":53,"alternative-id":["S0031320322001698"],"URL":"https:\/\/doi.org\/10.1016\/j.patcog.2022.108688","relation":{},"ISSN":["0031-3203"],"issn-type":[{"value":"0031-3203","type":"print"}],"subject":[],"published":{"date-parts":[[2022,10]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Sample complexity of rank regression using pairwise comparisons","name":"articletitle","label":"Article Title"},{"value":"Pattern Recognition","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.patcog.2022.108688","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2022 Elsevier Ltd. All rights reserved.","name":"copyright","label":"Copyright"}],"article-number":"108688"}}