| 1999 | Approximation Algorithms for Clustering Problems. | David B. Shmoys |
| 1999 | Further Results on the Margin Distribution. | John Shawe-Taylor, Nello Cristianini |
| 1999 | On PAC Learning Using Winnow, Perceptron, and a Perceptron-like Algorithm. | Rocco A. Servedio |
| 1999 | Drifting Games. | Robert E. Schapire |
| 1999 | Learning Specialist Decision Lists. | Atsuyoshi Nakamura |
| 1999 | PAC-Bayesian Model Averaging. | David A. McAllester |
| 1999 | Reinforcement Learning and Mistake Bounded Algorithms. | Yishay Mansour |
| 1999 | Microchoice Bounds and Self Bounding Learning Algorithms. | John Langford, Avrim Blum |
| 1999 | Additive Models, Boosting, and Inference for Generalized Divergences. | John D. Lafferty |
| 1999 | An Apprentice Learning Model (extended abstract). | Stephen Kwek |
| 1999 | Boosting as Entropy Projection. | Jyrki Kivinen, Manfred K. Warmuth |
| 1999 | On the Intrinsic Complexity of Learning Recursive Functions. | Efim B. Kinber, Christophe Papazian, Carl H. Smith, Rolf Wiehagen |
| 1999 | Linear Relations between Square-Loss and Kolmogorov Complexity. | Yuri Kalnishkan |
| 1999 | On a Generalized Notion of Mistake Bounds. | Sanjay Jain, Arun Sharma |
| 1999 | Multiclass Learning, Boosting, and Error-Correcting Codes. | Venkatesan Guruswami, Amit Sahai |
| 1999 | Covering Numbers for Support Vector Machines. | Ying Guo, Peter L. Bartlett, John Shawe-Taylor, Robert C. Williamson |
| 1999 | Viewing all Models as "Probabilistic". | Peter Grnwald |
| 1999 | Regret Bounds for Prediction Problems. | Geoffrey J. Gordon |
| 1999 | Learning Fixed-Dimension Linear Thresholds from Fragmented Data. | Paul W. Goldberg |
| 1999 | The Robustness of the | Claudio Gentile, Nick Littlestone |
| 1999 | Extension of the PAC Framework to Finite and Countable Markov Chains. | David Gamarnik |
| 1999 | Estimating a Mixture of Two Product Distributions. | Yoav Freund, Yishay Mansour |
| 1999 | An Adaptive Version of the Boost by Majority Algorithm. | Yoav Freund |
| 1999 | Minimax Regret Under log Loss for General Classes of Experts. | Nicol Cesa-Bianchi, Gbor Lugosi |
| 1999 | On Learning in the Presence of Unspecified Attribute Values. | Nader H. Bshouty, David K. Wilson |