John Langford

11 Dale Avenue
Ossining, NY 10562

Home: 914-923-5241

Research Interests

I am particularly interested in learning theory but my interests are broad. I have also worked on machine learning, planning, reinforcement learning, steganography, quantum computing, spam detection and some systems-related topics.


Refereed Publications

  1. John Langford and John Shawe-Taylor PAC-Bayes and Margins. Neural Information Processing Systems (NIPS2002)
  2. Sham Kakade, John Langford Approximately Optimal Approximate Reinforcement Learning International Conference on Machine Learning (ICML2002)
  3. John Langford, Martin Zinkevich, Sham Kakade Competitive Analysis of the Explore/Exploit Tradeoff International Conference on Machine Learning (ICML2002)
  4. Nick Hopper, John Langford, and Luis von Ahn Provably Secure Steganography Crypto 2002
  5. Sebastian Thrun, John Langford, and Vandi Verma, Risk Sensitive Particle Filters, Neural Information Processing Systems (NIPS2001).
  6. John Langford and Rich Caruana, (Not) Bounding the True Error Neural Information Processing Systems (NIPS2001)
  7. John Langford, Matthias Seeger, and Nimrod Megiddo. An Improved Predictive Accuracy Bound for Averaging Classifiers International Conference on Machine Learning (ICML2001)
  8. Josh Tenenbaum, Vin de Silva and John Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction . Science 290, pages 2319-2323, 2000 isomap site
  9. John Langford and David McAllester. Computable Shell Decomposition Bounds. Computational Learning Theory (COLT2000)
  10. Joseph O'Sullivan, John Langford, Rich Caruana and Avrim Blum. FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness. International Conference on Machine Learning (ICML2000)
  11. John Langford and Avrim Blum 1999. Microchoice Bounds and Self Bounding learning algorithms. COLT99 journal draft accepted at Machine Learning Journal
  12. Avrim Blum, Adam Kalai, and John Langford 1999. Beating the Holdout: Bounds for KFold and Progressive Cross-Validation. Computational Learning Theory (COLT99)
  13. S. Thrun, John Langford, and Dieter Fox 1999. Monte Carlo Hidden Markov Models: Learning Non-Parametric Models of Partially Observable Stochastic Proecesses. International Conference on Machine Learning (ICML99)
  14. Avrim Blum, Carl Burch, and John Langford, 1998. On Learning Monotone Boolean Functions Proceedings of the 39th Annual Symposium on Foundations of Computer Science FOCS '98.
  15. Avrim Blum and John Langford Probabilistic Planning in the Graphplan Framework. European Conference on Planning (ECP), 1999.

Employment History

IBM, TJ Watson, Yorktown, NY September 2002 - Present Research on many topics

University of Pennsylvania, Philadelphia, PA June 2002 - August 2002 Research with Michael Kearns on game theory and reinforcement learning

Carnegie Mellon, Pittsburgh, PA September 1997 - May 2002 PhD in machine learning theory.

ATnT Shannon Labs, Florham Park, NJ Summer 2001 "Summer Manager"
Learning theory and sample complexity bounds

IBM, Almaden, CA Summer 2000 Summer research with Shiv Vaithyanathan and Nimrod Megiddo
Hidden markov models for parsing and PAC Averaging bounds.

California Institute of Technology, Pasadena, CA, summer 1997 Research with Shuki Bruck and Yaser Abu-Mustafa
Researched the Support Vector machine algorithm and the application of learning bounds to it.

California Institute of Technology, Pasadena, CA, summer 1996 Research supported by SURF
Developed a Monte Carlo generator for theorized Heavy Majorana Neutrinos in an e+e- collider.

California Institute of Technology, Pasadena, CA, summer 1995 Researcher for Mani Chandy
Developed a Games Archetype which can be used with a board evaluation function to create 2 player perfect information games quickly.

California Institute of Technology, Pasadena, CA, summer 1994 Researcher supported by SURF
Implemented a new version of the Parti-game algorithm by Andrew Moore and explored its use.

  • Algorithm development and analyses specializing in probabilistic algorithms and machine learning.
  • Machine learning including Neural Nets, Bayes Nets, Decision Trees, Hidden Markov Models and Support Vector Machines.
  • U.S.

Nonresearch interests

camping and hiking
I enjoy running around in the woods.
Soccer and Fencing.
Playing games
Role playing games
strategy games
Dissecting and understanding any of the above


Avrim Blum (Phd advisor)
Department of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213-3891
Michael Kearns
Department of Computer and Information Science
University of Pennsylvania
Moore School Building/GRW, Room 555
200 South 33rd Street
Philadelphia, PA 19104-6389
Naoki Abe
(914) 945-3872
John Shawe-Taylor
Department of Computer Science
Royal Holloway, University of London
TW20 0EX, UK
Rich Caruana
4157 Upson Hall
Computer Science
Cornell University
Ithaca, NY 14853
Manuel Blum
Department of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213-3891