Generalization error bounds for learning to rank: Does the length of document lists matter?

@InProceedings{pmlr-v37-tewari15,
  title = 	 {Generalization error bounds for learning to rank: Does the length of document lists matter?},
  author = 	 {Tewari, Ambuj and Chaudhuri, Sougata},
  booktitle = 	 {Proceedings of the 32nd International Conference on Machine Learning},
  pages = 	 {315--323},
  year = 	 {2015},
  editor = 	 {Bach, Francis and Blei, David},
  volume = 	 {37},
  series = 	 {Proceedings of Machine Learning Research},
  address = 	 {Lille, France},
  month = 	 {07--09 Jul},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v37/tewari15.pdf},
  url = 	 {https://proceedings.mlr.press/v37/tewari15.html},
  abstract = 	 {We consider the generalization ability of algorithms for learning to rank at a query level, a problem also called subset ranking. Existing generalization error bounds necessarily degrade as the size of the document list associated with a query increases. We show that such a degradation is not intrinsic to the problem. For several loss functions, including the cross-entropy loss used in the well known ListNet method, there is no degradation in generalization ability as document lists become longer. We also provide novel generalization error bounds under \ell_1 regularization and faster convergence rates if the loss function is smooth.}
}