- S. Dasgupta, Coarse sample complexity bounds for active learning. Advances in Neural Information Processing Systems (NIPS), 2005.
- S. Dasgupta, A. Kalai, and C. Monteleoni, Analysis of perceptron-based active learning. Eighteenth Annual Conference on Learning Theory (COLT), 2005.
- M.-F. Balcan, A. Beygelzimer, J. Langford, Agnostic active learning. ICML 2006.
- S. Fine, Y. Mansour, Active Sampling for Multiple Output Identification. COLT 2006.
- See also the NIPS 2005 Workshop on Foundations of Active Learning.

- H. Daume, J. Langford, D. Marcu, Search-based Structured Prediction.
- B. Taskar, V. Chatalbashev, D. Koller and C. Guestrin. Learning Structured Prediction Models: A Large Margin Approach. ICML 2005.
- There has also been work on more traditional k-way
classification. See, e.g.,
- T. Zhang, Statistical analysis of some multi-category large margin classification methods, JMLR, 2004.
- A. Tewari and P. Bartlett, On the consistency of multiclass classification methods, COLT, 2005.
- J. Langford and A. Beygelzimer, Sensitive Error Correcting Output Codes, COLT 2005.

- A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. Agnostically Learning Halfspaces. FOCS 2005. (Link points to Adam Kalai's home page. Scroll down for paper & ppt)
- W. S. Lee, P. L. Bartlett, and R. C. Williamson. Efficient agnostic learning of neural networks with bounded fan-in. IEEE Trans Info Theory, 1996.

- J. Jackson, An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution. Journal of
Computer and System Sciences 55(3), 1997.
N. Bshouty, J. Jackson, and T. Tamon, More Efficient PAC-learning of
DNF with Membership Queries Under the Uniform
Distribution. Proceedings of the 12th Annual Workshop on Computational
Learning Theory, 1999.

These papers show how to use membership queries to learn DNF formulas respect to the uniform distribution. Combination of fourier analysis with boosting and a clever analysis of the distributions produced. - N. Bshouty and E. Mossel and R. O'Donnell and R. Servedio,
Learning DNF from Random Walks. 44th Annual Symposium on Foundations
of Computer Science (FOCS), 2003, pp. 189-198.

Improves on above results by replacing membership queries with passive observation of a random walk on {0,1}^n. That is, you get to observe a sequence of examples where each new example is a random neighbor of the previous one.

**Computational hardness results:** Some recent papers:

- V. Feldman, P. Gopalan, S. Khot, A. Ponnuswami. New Results for Learning Noisy Parities and Halfspaces, FOCS 2006.
- V. Feldman, Optimal Hardness Results for Maximizing Agreements with Monomials, CCC 2006.
- V. Guruswami and P. Raghavendra, Hardness of learning halfspaces with noise. FOCS 2006.

- P.L. Bartlett, M.I. Jordan, J.D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-156, 2006.
- T.Zhang, Statistical behavior and consistency of classification methods based on convex risk minimization.
- I.Steinwart, How to compare different loss functions and their risks.

- P. Auer, N. Cesa-Bianchi, Y. Freund, R. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM J. Comput. 32(1): 48-77 (2002).
- V. Dani and T. Hayes, Robbing the bandit: Less regret in online geometric optimization against an adaptive adversary. SODA 2006.
- A. Blum and Y. Mansour, From External to Internal Regret. COLT 2005.

**Learning in Markov Decision Processes:** See Michael Kearns's home
page and Yishay
Mansour's home page for a number of good papers.
Also Sham Kakade's thesis.

**PAC-Bayes bounds, shell-bounds, other methods of obtaining
confidence bounds.** Some papers:

- D. McAllester, Simplified PAC-BAyesian Margin Bounds. COLT 2003.
- A. Ambroladze, E. Parrado-Hernandez, J. Shawe-Taylor, Tighter PAC-Bayes Bounds. NIPS 2006.
- J. Langford and D. McAllester. Computable Shell Decomposition Bounds. COLT 2000.

**Learning in Graphical Models (Bayes Nets)**

Last modified: Fri Mar 9 21:21:27 EST 2007