AIM Workshop on the Mathematics of Ranking

This webpage disseminates information for the AIM Workshop on the Mathematics of Ranking. The workshop will take place August 16 to August 20, 2010 at the American Institute of Mathematics in Palo Alto.

AIM also maintains a separate page for participants at:

• http://www.aimath.org/WWN/mathofranking/

AIM's public announcement can be found at:

• http://www.aimath.org/ARCC/workshops/mathofranking.html

On this page, you will find lists of:

• slides

• scribe notes

• reading materials

• suggested problems

• participants

Slides (more to come)

• Monday
  • Social Choice: Kenneth Arrow
  • Voting: Donald Saari

• Tuesday
  • Statistics: Devavrat Shah
  • Decision Science: Thomas Saaty

• Wednesday
  • Linear Algebra: Amy Langville, David Gleich
  • Optimization: Dorit Hochbaum
  • Graph Theory: Lek-Heng Lim

• Thursday
  • Machine Learning: Shivani Agarwal, Yoram Singer, Nicolas Vayatis, Lester Mackey

• Friday
  • Machine Learning: Yacov Crammer, Cynthia Rudin, Kevin Small, Purnamrita Sarkar
  • Game Theory: Yinyu Ye
  • Representation Theory: Michael Orrison, Risi Kondor
  • Statistics: Tong Zhang
  • Finance: Peter Bartlett

Scribe notes (more to come)

• scribe notes for Monday afternoon

• scribe notes for Risi Kondor's tutorial on Tuesday

• scribe notes for Wednesday afternoon

• scribe notes for Risi Kondor's tutorial on Thursday (with inputs from Mike Orrison)

Background reading materials

If you have any articles that you would like us to include in the list below, please do send either of us (lekheng@uchicago.edu, shivani@mit.edu) the PDF files or URLs. Caveat: One or two would be great, but not more than five please. Highlighted authors are expected to be at the workshop.

• S. Agarwal, D. Dugar, S. Sengupta, Ranking chemical structures for drug discovery: A new machine learning approach," J. Chem. Inf. Model., 50 (2010), no. 5, pp 716–731.

• S. Agarwal P. Niyogi, "Generalization bounds for ranking algorithms via algorithmic stability," J. Mach. Learn. Res., 10 (2009), pp. 441–474.

• S. Agrawal, Z. Wang, Y. Ye, "Parimutuel betting on permutations," pp. 126–137 in: Internet and Network Economics (WINE '08), Lecture Notes in Computer Science, 5385, Springer, Berlin, 2008.

• N. Ailon, M. Mohri, "Preference-based learning to rank," Machine Learn., 8 (2010), nos. 2–3, pp. 189–211.

• K. Arrow, "A difficulty in the concept of social welfare," J. Polit. Econ., 58 (1950), no. 4, pp. 328–346.

• S. Clémençon, G. Lugosi, N. Vayatis, "Ranking and empirical minimization of U-statistics," Ann. Statist., 36 (2008), no. 2, pp. 844–874.

• S. Clémençon, N. Vayatis, "Ranking the best instances," J. Mach. Learn. Res., 8 (2007), pp. 2671–2699.

• D. Cossock, T. Zhang, "Statistical analysis of Bayes optimal subset ranking," IEEE Trans. Inform. Theory, 54 (2008), no. 11, pp. 5140–5154.

• K. Crammer, Y. Singer, "Online ranking by projecting," Neural Comput., 17 (2005), no. 1, pp. 145–175.

• Z. Daugherty, A. Eustis, G. Minton, M. Orrison, "Voting, the symmetric group, and representation theory," Amer. Math. Monthly, 116 (2009), no. 8, pp. 667–687.

• P. Diaconis, S. Goel, S. Holmes, "Horseshoes in multidimensional scaling and local kernel methods," Ann. Appl. Stat., 2 (2008), no. 3, pp. 777–807.

• J. Duchi, L. Mackey, M. Jordan, "On the consistency of ranking algorithms," Proc. Internat. Conf. Mach. Learn. (ICML '10), 27 (2010), pp. 327–334.

• C. Dwork, R. Kumar, M. Naor, D. Sivakumar, "Rank aggregation methods for the web," Proc. Internat. Conf. World Wide Web (WWW '01), 10 (2001), pp. 613–622.

• C. Eschenbach, F. Hall, R. Hemasinha, S. Kirkland, Z. Li, B. Shader, J. Stuart, J. Weaver, "Properties of tournaments among well-matched players," Amer. Math. Monthly, 107 (2000), no. 10, pp. 881–892.

• D. Gleich, Models and Algorithms for PageRank Sensitivity, Ph.D. Thesis, Stanford University, Institute for Computational and Mathematical Engineering, September 2009.

• D. Hochbaum, A. Levin, "Methodologies and algorithms for group-rankings decision," Manag. Sci., 52 (2006), no. 9, pp. 1394–1408.

• J. Huang, C. Guestrin, X. Jiang, L. Guibas, "Exploiting probabilistic independence for permutations," Proc. Internat. Conf. AI Stat. (AISTAT '09), 12 (2009), pp. 248–255.

• S. Jagabathula, D. Shah, "Recoverability conditions for rankings under partial information," Proc. NIPS Workshop Adv. Ranking, 2009.

• X. Jiang, L.-H. Lim, Y. Yao, Y. Ye, "Statistical ranking and combinatorial Hodge theory," Math. Program., Special Issue on Optimization in Machine Learning, to appear.

• A. Klementiev, D. Roth, K. Small, "Unsupervised rank aggregation with distance-based models," Proc. Internat. Conf. Mach. Learn. (ICML '08), 25 (2010), pp. 472–479.

• R. Kondor, M. Barbosa, "Ranking with kernels in Fourier space," Proc. Conf. Learn. Theory (COLT '10), 23 (2010), pp. 451–463.

• A. Langville, C. Meyer, "Deeper inside PageRank," Internet Math., 1 (2004), no. 3, pp. 335–380.

• J. Morton, L. Pachter, A. Shiu, B. Sturmfels, O. Wienand, "Convex rank tests and semigraphoids," SIAM J. Discrete Math., 23 (2009), no. 3, pp. 1117–1134.

• R. Rivest, E. Shen, "An optimal single-winner preferential voting system based on game theory," preprint, (2010).

• C. Rudin, "The p-norm push: A simple convex ranking algorithm that concentrates at the top of the list," J. Mach. Learn. Res., 10 (2009), pp. 2233–2271.

• D. Saari, "Geometry of Voting," Chapter 27 in K. Arrow, A. Sen, K. Suzumura (Eds), Handbook of Social Choice and Welfare, II, North-Holland, Amsterdam, 2010.

• T. Saaty, "Rank according to Perron: A new insight," Math. Mag., 60 (1987), no. 4, pp. 211–213.

• T. Saaty, "Decision-making with the AHP: Why is the principal eigenvector necessary," European J. Oper. Res., 145 (2003), no. 1, pp. 85–91.

• P. Sarkar, A. Moore, "Fast dynamic reranking in large graphs," Proc. Internat. Conf. World Wide Web (WWW '09), 18 (2009), pp. 31–40.

Suggested problems for discussion

Additional problems are still welcomed. Please write to either of us (lekheng@uchicago.edu, shivani@mit.edu).

• Shivani Agarwal

• David Gleich & Amy Langville

• Srikanth Jagabathula & Devavrat Shah

• Risi Kondor

• Ravi Kumar

• Ron Rivest

• Yuan Yao

• Tong Zhang

Participants

• Shivani Agarwal, Computer Science, Massachusetts Institute of Technology

• Kenneth Arrow, Economics, Stanford University

• Peter Bartlett, Computer Science, University of California, Berkeley

• Natth Bejraburnin, Mathematics, University of California, Berkeley

• Sandeep Chandana, Electrical and Computer Engineering, University of Calgary

• Yacov Crammer, Electrical Engineering, Technion – Israel Institute of Technology

• Jeffrey Doker, Mathematics, University of California, Berkeley

• David Gleich, Informatics and Decision Sciences, Sandia National Labs

• Dorit Hochbaum, Industrial and Systems Engineering, University of Southern California

• Susan Holmes, Statistics, Stanford University

• Srikanth Jagabathula, Computer Science, Massachusetts Institute of Technology

• Xiaoye Jiang, Computational and Mathematical Engineering, Stanford University

• Risi Kondor, Center for the Mathematics of Information, California Institute of Technology

• Ravi Kumar, Search Technologies, Yahoo! Research

• Amy Langville, Mathematics, College of Charleston

• Michael Levitt, Structural Biology, Stanford University

• Lek-Heng Lim, Statistics, University of Chicago

• Han Liu, Computer Science, Carnegie Mellon University

• Lester Mackey, Computer Science, University of California, Berkeley

• Mehryar Mohri, Computer Science, New York University

• Jason Morton, Mathematics and Statistics, Pennsylvania State University

• Michael Orrison Jr, Mathematics, Harvey Mudd College

• Deepti Pachauri, Computer Science, University of Wisconsin, Madison

• Cynthia Rudin, Sloan School of Management, Massachusetts Institute of Technology

• Donald Saari, Mathematics, University of California, Irvine

• Thomas Saaty, Katz Graduate School of Business, University of Pittsburgh

• Purnamrita Sarkar, Computer Science, Carnegie Mellon University

• Bryan Shader, Mathematics, University of Wyoming

• Devavrat Shah, Computer Science, Massachusetts Institute of Technology

• Anne Shiu, Mathematics, Duke University

• Yoram Singer, Google Research

• Kevin Small, Computer Science, Tufts University

• Vikram Tankasali, Indian Institute of Science

• Ngoc Mai Tran, Statistics, University of California, Berkeley

• Nicolas Vayatis, Mathematics, Ecole Normale Supérieure de Cachan

• Yuan Yao, Statistics, Peking University

• Yinyu Ye, Management Science and Engineering, Stanford University

• Tong Zhang, Statistics, Rutgers University