John Langford

Phone: 914-948-1871
E-mail: jl@hunch.net
Web: http://hunch.net/~jl/

Research Interests

I want to solve machine learning. In a solved form, machine learning is automatic, robust, scalable, and easily used for many problems. In the last several years, we have made great progress in this direction.

Education

Employment History

Microsoft Research, New York, NY May 2012-present Principal Research Scientist

Yahoo! Research, New York, NY June 2006-April 2012 Senior Research Scientist

TTI-Chicago, Chicago, IL September 2003 - May 2006 Research Assistant Professor

IBM, TJ Watson, Yorktown, NY September 2002 - August 2003 Herman Goldstine Fellow

University of Pennsylvania, Philadelphia, PA June 2002 - August 2002 Postdoc with Michael Kearns

Activities

Blog: Machine Learning (Theory)
Tutorial: Learning to Search at HLT-NAACL 2015 and ICML 2015.
Tutorial: Learning to Interact at NIPS 2013.
Class: Large Scale Machine Learning
Tutorial: Scaling up Machine Learning at KDD 2011.
Tutorial: Learning through Exploration Video at ICML 2010 and KDD 2010.
Workshop: Organizer Cores, Clusters, and Clouds at NIPS 2010.
Tutorial: Active Learning Video at ICML 2009.
Tutorial: Reductions in Machine Learning Video at ICML 2009
Workshop: Organizer Principles of Learning Problem Design at NIPS 2007
Tutorial: Learning Reductions IJCAI2005 and MLSS 2005
School: Organizer Machine Learning Summer School Chicago 2005
Workshop: Organizer (Ab)Use of Bounds NIPS 2004
Workshop: Organizer Machine Learning Reductions TTI-Chicago, 2003
Tutorial: Practical Prediction Theory for Classification ICML2003 and MLSS 2005

Service

General Chair: ICML 2016
Program Chair: ICML 2012
New York ML Symposium co-organizer: 2008 2009 2010 2011 2012 2014 2015 2016
Area chair/Senior PC: ICML 2004 NIPS 2006 ICML 2007 ICML 2009 ICML 2010 KDD 2010 NIPS 2010 ICML 2011 and other since.
Program committee: ICML 2003, 2005 & 2008, SODA 2008, AAAI 2005, AAAI 2007ALT 2004, UAI 2007 AIStat 2005 COLT 2008 COLT 2009 and others
Reviewing: NIPS 2001, 2002, 2003, 2005 & 2007, AAAI 2002, MLJ, JMLR, JAIR, JCSS, TCS, JACM, and others

Mentoring

I have worked with many students over time. In all cases, I try to learn something from them as well.
  1. Jacob Abernethy (Professor, University of Michigan)
  2. Alekh Agarwal (Research Scientist, MSR-NYC)
  3. Luis von Ahn (*) (Professor Carnegie Mellon)
  4. Ashwinkumar Badanidiyuru (Research Scientist, Google)
  5. Nina Balcan (*) (Professor Carnegie Mellon)
  6. Arindam Banerjee (*)(Professor UMinnesota)
  7. Kai-Wei Chang (Professor, University of Virginia)
  8. Carl Burch (*) (Google)
  9. Anna Choromanska (*) (Professor, NYU)
  10. Hal Daume (*) (Professor U Maryland)
  11. Varsha Dani (Research Professor U New Mexico)
  12. Nick Hopper (*) (Professor UMinnesota)
  13. Daniel Hsu (*) (Professor, Columbia)
  14. Nikos Karampatziakis (*) (Microsoft)
  15. Matti Kääriäinen (*) (Nokia?)
  16. Sham Kakade (*) (University of Washington)
  17. Adam Kalai (*) (Microsoft Research)
  18. Akshay Krishnamurthy (Professor, University of Massachusetts, Amherst)
  19. Nicolas Lambert (Professor Stanford)
  20. Lihong Li (Microsoft Research)
  21. Haipeng Luo (Postdoc MSR)
  22. Joseph O'Sullivan (ex-Google :-)
  23. Pradeep Ravikumar (Professor UTAustin)
  24. Ruslan Salakhutdinov (Professor Carnegie Mellon)
  25. Matthias Seeger (*) (Amazon)
  26. Vin de Silva (*) (Professor Pomona)
  27. Alex Strehl (*) (Facebook)
  28. Jennifer Wortman Vaughan (Microsoft Research)
  29. Vandi Verma (*) (JPL)
  30. Yevgeniy Vorobeychik (Vanderbilt University)
  31. Eric Weiwiora (UCSD)
  32. Bianca Zadrozny (*) (Professor UFF)
  33. Martin Zinkevich (Google Research)
(*) = on work which became part of their thesis

Select Publications

  1. Ron Bekkerman, Misha Bilenko, and John Langford (Editors) Scaling Up Machine Learning, Cambridge University Press, 2011.
  2. Miroslav Dudík, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, Tong Zhang: Efficient Optimal Learning for Contextual Bandits, UAI 2011
  3. Alina Beygelzimer, Sham Kakade, and John Langford Cover Trees for Nearest Neighbor, ICML-2006 [Pat Goldberg Best Paper Award in Computer Science, Electrical Engineering, and Mathematics]
  4. Luis von Ahn, Manuel Blum, Nick Hopper and John Langford CAPTCHA: Using Hard AI Problems for Security Eurocrypt 2003
  5. Josh Tenenbaum, Vin de Silva and John Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction . Science 290, pages 2319-2323, 2000 isomap site

Papers, forthcoming

  1. Alekh Agarwal, Sarah Bird, Markus Cozowicz, Luong Hoang, John Langford, Stephen Lee, Jiaji Li, Dan Melamed, Gal Oshri, Oswaldo Ribas, Siddhartha Sen, Alex Slivkins, A Multiworld Testing Decision Service.

All Publications, appended

Research Programs

Much of my work can be organized into coherent programs.
  1. Creating and using tight sample complexity bounds for evaluation and machine learning algorithm design. This was my thesis work, and a small program of work by others has grown out of it.
  2. Learning Reductions. We transform complex learning problems into simple ones and then use good algorithms for the simple ones to solve the complex problems. Here we designed the method of analysis as well as the algorithms, and again a small program of work by others is growing out of it.
  3. Scalable learning. The goal here is to scale up learning algorithms in all ways. We have addressed scaling in the number of parameters, the number of examples, and the number of labels.
  4. Active Learning. We proved that active learning was possible in the same noisy settings as supervised learning and eventually refined the algorithm to efficiently use any supervised algorithm as an oracle.
  5. Contextual Bandits. In many real-life situations, we only get feedback about choices taken rather than choices not taken, as is assumed in normal supervised learning. This requires a ground-up rethink of what machine learning means. We have developed evaluators (equivalent to test sets in supervised learning), optmized the use of exploration information, developed exponentially faster algorithms, and created a system for learning.
  6. Vowpal Wabbit is an open source machine learning system which encodes some of the above. VW has many unique features which makes is a useful tool for advanced prediction, large scale, and interactive settings.

Patents

  1. US20130290223 A1 Method and system for distributed machine learning
  2. US 20130268374 Learning Accounts
  3. US 20150213510 A1 Framework that facilitates user participation in auctions for display advertisements
  4. US 20160105351 A1 Application Testing
  5. 8108323 Distributed Personal Spam Filtering
  6. 8174974 VOLUNTARY ADMISSION CONTROL FOR TRAFFIC YIELD MANAGEMENT
  7. 8006157 Resource-light method and apparatus for outlier detection
  8. 8032535 Personalized web search ranking
  9. US 2012/0016642 CONTEXTUAL-BANDIT APPROACH TO PERSONALIZED NEWS ARTICLE RECOMMENDATION
  10. US 2010/0057546 SYSTEM AND METHOD FOR ONLINE ADVERTISING USING USER SOCIAL INFORMATION
  11. US 2010/0010891 METHODS FOR ADVERTISEMENT SLATE SELECTION
  12. US 2009/0265227 Methods for Advertisement Display Policy Exploration
  13. US 2005/0091524 Confidential fraud detection system and method
  14. US 2010/0131496 PREDICTIVE INDEXING FOR FAST SEARCH

References

Avrim Blum (Phd advisor) avrim+@cs.cmu.edu
Michael Kearns mkearns@cis.upenn.edu
Robert Schapire schapire@cs.princeton.edu
Sanjoy Dasgupta dasgupta@cs.ucsd.edu
Preston McAfee preston@mcafee.cc
Prabhakar Raghavan pragh@acm.org
Citizenship
  • U.S.
Awards

Publications, All

  1. Kai-Wei Chang, He He, Hal Daumé III, John Langford, Stephane Ross, A Credit Assignment Compiler for Joint Prediction NIPS 2016.
  2. John Langford, Mark Guzdial, The solution to AI, what real researchers do, and expectations for CS classrooms. Commun. ACM 59(6): 10-11 (2016).
  3. Alina Beygelzimer, Hal Daumé III, John Langford, Paul Mineiro: Learning Reductions That Really Work. Proceedings of the IEEE 104(1): 136-147 (2016)
  4. Haipeng Luo, Alekh Agarwal, Nicolò Cesa-Bianchi, John Langford: Efficient Second Order Online Learning via Sketching. NIPS 2016.
  5. Akshay Krishnamurthy, Alekh Agarwal, John Langford: Contextual-MDPs for PAC-Reinforcement Learning with Rich Observations. NIPS 2016.
  6. Alina Beygelzimer, Daniel J. Hsu, John Langford, Chicheng Zhang: Search Improves Label for Active Learning. NIPS 2016.
  7. John Langford, Mark Guzdial, The arbitrariness of reviews, and advice for school administrators. Commun. ACM 58(4): 12-13 (2015).
  8. Nicolas S. Lambert, John Langford, Jennifer Wortman Vaughan, Yiling Chen, Daniel M. Reeves, Yoav Shoham, David M. Pennock An axiomatic characterization of wagering mechanisms. J. Economic Theory 156: 389-416 (2015).
  9. Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daumé III, John Langford: Learning to Search Better than Your Teacher. ICML 2015: 2058-2066.
  10. Hal Daumé III, John Langford, Kai-Wei Chang, He He, Sudha Rao: Hands-on Learning to Search for Structured Prediction. HLT-NAACL 2015: 1.
  11. Anna Choromanska, John Langford: Logarithmic Time Online Multiclass prediction. NIPS 2015: 55-63
  12. Tzu-Kuo Huang, Alekh Agarwal, Daniel J. Hsu, John Langford, Robert E. Schapire: Efficient and Parsimonious Agnostic Active Learning. NIPS 2015: 2755-2763.
  13. John Langford, Mark Guzdial Finding a research job, and teaching CS in high school. Commun. ACM 57(10): 10-11 (2014).
  14. Alekh Agarwal, Olivier Chapelle, Miroslav Dudík, John Langford: A Reliable Effective Terascale Linear Learning System, Journal of Machine Learning Research 15(1): 1111-1133 (2014).
  15. Ashwinkumar Badanidiyuru, John Langford, Aleksandrs Slivkins: Resourceful Contextual Bandits. COLT 2014: 1109-1134
  16. Alekh Agarwal, Daniel J. Hsu, Satyen Kale, John Langford, Lihong Li, Robert E. Schapire Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits. ICML 2014: 1638-1646
  17. Alekh Agarwal, Alina Beygelzimer, Daniel J. Hsu, John Langford, Matus J. Telgarsky Scalable Non-linear Learning with Adaptive Polynomial Expansions. NIPS 2014: 2051-2059
  18. Stephane Ross, Paul Mineiro, and John Langford, Normalized Online Learning, UAI 2013.
  19. Miroslav Dudík, Dumitru Erhan, John Langford, Lihong Li: Sample-efficient Nonstationary Policy Evaluation for Contextual Bandits. UAI 2012: 247-254
  20. John Langford: Parallel machine learning on big data. ACM Crossroads 19(1): 60-62 (2012)
  21. Lihong Li, Wei Chu, John Langford, Taesup Moon, Xuanhui Wang: Unbiased offline evaluation of contextual-bandit Algorithms with Generalized Linear Models, JMLR 2012
  22. John Langford, Ruben Ortega: Machine learning and algorithms; agile development. Commun. ACM 55(8): 10-11 (2012)
  23. John Langford, Lihong Li, R. Preston McAfee, Kishore Papineni: Cloud control: voluntary admission control for intranet traffic management. Inf. Syst. E-Business Management 10(3): 295-308 (2012)
  24. John Langford, Joelle Pineau: Proceedings of the 29th International Conference on Machine Learning (ICML-12). CoRR abs/1207.4676 (2012)
  25. Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, Robert E. Schapire: Contextual Bandit Learning with Predictable Rewards, AIStats 2012.
  26. Alina Beygelzimer, John Langford, David Pennock: Learning Performance of Prediction Markets with Kelly Bettors, AAMAS 2012
  27. Ron Bekkerman, Misha Bilenko, and John Langford (Editors) Scaling Up Machine Learning, Cambridge University Press, 2011.
  28. Daniel Hsu, Nikos Karampatziakis, John Langford, Alexander J. Smola: Parallel Online Learning, in Scaling Up Machine Learning, Cambridge University Press, 2011.
  29. Miroslav Dudík, John Langford, Lihong Li: Doubly Robust Policy Evaluation and Learning, ICML 2011
  30. Miroslav Dudík, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, Tong Zhang: Efficient Optimal Learning for Contextual Bandits, UAI 2011
  31. Nikos Karampatziakis, John Langford: Online Importance Weight Aware Updates, UAI 2011
  32. John Langford, Lihong Li, Preston McAfee, Kishore Papineni: Cloud Control: Voluntary Admission Control for Intranet Traffic Management, Information Systems and e-Business Management
  33. Lihong Li, Wei Chu, John Langford, Xuanhui Wang: Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms, WSDM 2011 [Best Paper Award]
  34. Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, Robert E. Schapire: Contextual Bandit Algorithms with Supervised Learning Guarantees, Journal of Machine Learning Research, Proceedings Track 15 (AISTATS 2011): 19-26 (2011) [Notable Paper Award]
  35. Alina Beygelzimer, Daniel Hsu, John Langford, Tong Zhang: Agnostic Active Learning Without Constraints, NIPS 2010
  36. Alexander L. Strehl, John Langford, Lihong Li, Sham Kakade: Learning from Logged Implicit Exploration Data, NIPS 2010
  37. Lihong Li, Wei Chu, John Langford, Robert E. Schapire: A contextual-bandit approach to personalized news article recommendation, WWW 2010
  38. John Langford: Efficient Exploration in Reinforcement Learning. Encyclopedia of Machine Learning 2010: 309-311
  39. John Langford Open Problem: Robust Efficient Conditional Probability Estimation, COLT 2010.
  40. John Langford, Lihong Li, Yevgeniy Vorobeychik, Jennifer Wortman: Maintaining Equilibria During Exploration in Sponsored Search Auctions, Algorithmica 58(4): 990-1021 (2010). Conference version in WINE 2007.
  41. Alina Beygelzimer, John Langford, Pradeep D. Ravikumar: Error-Correcting Tournaments, ALT 2009
  42. Kilian Q. Weinberger, Anirban Dasgupta, John Langford, Alexander J. Smola, Josh Attenberg: Feature hashing for large scale multitask learning, ICML 2009
  43. Alina Beygelzimer, Sanjoy Dasgupta, John Langford: Importance weighted active learning, ICML 2009
  44. John Langford, Ruslan Salakhutdinov, Tong Zhang: Learning nonlinear dynamic models, ICML 2009
  45. Alina Beygelzimer, John Langford: The offset tree for learning with partial labels, KDD 2009
  46. Martin Zinkevich, Alexander J. Smola, John Langford: Slow Learners are Fast, NIPS 2009
  47. Daniel Hsu, Sham Kakade, John Langford, Tong Zhang: Multi-Label Prediction via Compressed Sensing, NIPS 2009
  48. Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, Alexander L. Strehl: Conditional Probability Tree Estimation Analysis and Algorithms, UAI 2009
  49. Nicholas J. Hopper, John Langford, and Luis von Ahn: Provably Secure Steganography, Crypto 2002. Journal version: IEEE Transactions on Computers 58(5): 662-676 (2009)
  50. Maria-Florina Balcan, Alina Beygelzimer, John Langford: Agnostic active learning, ICML 2006. Journal version: JCSS 75(1): 78-89 (2009)
  51. Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alexander J. Smola, S. V. N. Vishwanathan: Hash Kernels for Structured Data, Journal of Machine Learning Research 10: 2615-2637 (2009)
  52. Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alexander J. Smola, Alexander L. Strehl, Vishy Vishwanathan: Hash Kernels, Journal of Machine Learning Research - Proceedings Track 5 (AISTATS 2009): 496-503 (2009)
  53. John Langford, Lihong Li, Tong Zhang: Sparse Online Learning via Truncated Gradient, NIPS 2008. Journal version: Journal of Machine Learning Research 10: 777-801 (2009)
  54. Hal Daumé III, John Langford, Daniel Marcu: Search-based structured prediction, Machine Learning 75(3): 297-325 (2009)
  55. Nicolas S. Lambert, John Langford, Jennifer Wortman, Yiling Chen, Daniel M. Reeves, Yoav Shoham, David M. Pennock: Self-financed wagering mechanisms for forecasting, EC 2008. [Winner of an Outstanding Paper Award]
  56. John Langford, Alexander L. Strehl, Jennifer Wortman: Exploration scavenging, ICML 2008
  57. Sharad Goel, John Langford, Alexander L. Strehl: Predictive Indexing for Fast Search, NIPS 2008
  58. Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin: Robust reductions from ranking to classification, COLT 2007. Journal version: Machine Learning 72(1-2): 139-153 (2008)
  59. John Langford, Tong Zhang: The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information. NIPS 2007
  60. Alexander L. Strehl, Lihong Li, Eric Wiewiora, John Langford, Michael L. Littman: PAC model-free reinforcement learning, ICML 2006
  61. Alina Beygelzimer, Sham Kakade, and John Langford Cover Trees for Nearest Neighbor, ICML-2006 [Pat Goldberg Best Paper Award in Computer Science, Electrical Engineering, and Mathematics]
  62. Naoki Abe, Bianca Zadrozny, John Langford: Outlier detection by active learning, KDD 2006
  63. John Langford, Roberto Oliveira, Bianca Zadrozny: Predicting Conditional Quantiles via Reduction to Classification, UAI 2006
  64. Jacob Abernethy, John Langford, Manfred Warmuth Continuous Experts and the Binning Algorithm, COLT 2006
  65. John Langford and Bianca Zadrozny Relating Reinforcement Learning Performance to Classification Performance ICML 2005
  66. Matti Kääriäinen and John Langford A Comparison of Tight Generalization Bounds ICML 2005
  67. Matti Kääriäinen, John Langford: A comparison of tight generalization error bounds. ICML 2005
  68. Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford, and Bianca Zadrozny Error limiting reductions between classification tasks ICML 2005
  69. Alina Beygelzimer, John Langford, and Bianca Zadrozny Weighted One Against All AAAI 2005
  70. John Langford and Alina Beygelzimer Sensitive Error Correcting Output Codes COLT 2005
  71. Luis von Ahn, Nick Hopper, and John Langford Covert Two-Party Computation STOC 2005
  72. John Langford and Bianca Zadrozny Estimating Class Membership Probabilities Using Classifier Learners AISTAT 2005
  73. John Langford Tutorial on Practical Prediction Theory for Classification JMLR 2005
  74. Arindam Banerjee and John Langford An Objective Evaluation Criterion for Clustering KDD 2004
  75. Naoki Abe, Bianca Zadrozny, and John Langford An Iterative Method for Multi-class Cost-sensitive Learning KDD 2004
  76. Peter Grünwald and John Langford Suboptimal Behavior of Bayes and MDL in Classification under Misspecification COLT 2004. Journal version: Machine Learning 66(2-3): 119-149 (2007)
  77. Luis von Ahn, Manuel Blum, Nick Hopper and John Langford CAPTCHA: Using Hard AI Problems for Security Eurocrypt 2003
  78. Luis von Ahn, Manuel Blum and John Langford: Telling humans and computers apart automatically. Commun. ACM 47(2): 56-60 (2004)
  79. Sham Kakade, Michael Kearns, John Langford, and Luis Ortiz, Correlated Equilibria in Graphical Games, ACM EC 2003.
  80. Bianca Zadrozny, John Langford, and Naoki Abe Cost Sensitive Learning by Cost-Proportionate Example Weighting ICDM 2003
  81. Avrim Blum and John Langford PAC-MDL Bounds COLT 2003
  82. Sham Kakade, Michael Kearns, and John Langford Exploration in Metric State Spaces ICML2003
  83. John Langford and John Shawe-Taylor PAC-Bayes and Margins. NIPS-2002
  84. Sham Kakade, John Langford Approximately Optimal Approximate Reinforcement Learning ICML-2002
  85. John Langford: Combining Trainig Set and Test Set Bounds. ICML 2002: 331-338
  86. John Langford, Martin Zinkevich, Sham Kakade Competitive Analysis of the Explore/Exploit Tradeoff ICML-2002
  87. John Langford Generic Quantum Block Compression (at xxx.lanl.gov and Phys. rev. A.) May 2002
  88. Sebastian Thrun, John Langford, and Vandi Verma, Risk Sensitive Particle Filters, NIPS2001.
  89. John Langford and Rich Caruana, (Not) Bounding the True Error NIPS2001
  90. John Langford, Matthias Seeger, and Nimrod Megiddo. An Improved Predictive Accuracy Bound for Averaging Classifiers ICML2001
  91. Josh Tenenbaum, Vin de Silva and John Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction . Science 290, pages 2319-2323, 2000 isomap site
  92. John Langford and David McAllester. Computable Shell Decomposition Bounds. COLT2000 and JMLR 5: 529-547 (2004)
  93. Joseph O'Sullivan, John Langford, Rich Caruana and Avrim Blum. FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness. ICML2000
  94. John Langford and Avrim Blum 1999. Microchoice Bounds and Self Bounding learning algorithms. COLT99 also, Machine Learning Journal 51(2): 165-179 (2003)
  95. Avrim Blum, Adam Kalai, and John Langford 1999. Beating the Holdout: Bounds for KFold and Progressive Cross-Validation. COLT99
  96. S. Thrun, John Langford, and Dieter Fox 1999. Monte Carlo Hidden Markov Models: Learning Non-Parametric Models of Partially Observable Stochastic Proecesses. ICML99
  97. Avrim Blum and John Langford: Probabilistic Planning in the Graphplan Framework, ECP 1999.
  98. Avrim Blum, Carl Burch, and John Langford: On Learning Monotone Boolean Functions, FOCS 1998.