COLT 2001

41 papers

A General Dimension for Exact Learning José L. Balcázar, Jorge Castro, David Guijarro

A Generalized Representer Theorem Bernhard Schölkopf, Ralf Herbrich, Alexander J. Smola

A Leave-One-Out Cross Validation Bound for Kernel Methods with Applications in Learning Tong Zhang

A Sequential Approximation Bound for Some Sample-Dependent Convex Optimization Problems with Applications in Learning Tong Zhang

A Theoretical Analysis of Query Selection for Collaborative Filtering Wee Sun Lee, Philip M. Long

Adaptive Strategies and Regret Minimization in Arbitrarily Varying Markov Environments Shie Mannor, Nahum Shimkin

Agnostic Boosting Shai Ben-David, Philip M. Long, Yishay Mansour

Bounds on Sample Size for Policy Evaluation in Markov Environments Leonid Peshkin, Sayan Mukherjee

Data-Dependent Margin-Based Generalization Bounds for Classification Balázs Kégl, Tamás Linder, Gábor Lugosi

Discrete Prediction Games with Arbitrary Feedback and Loss Antonio Piccolboni, Christian Schindelhauer

Efficiently Approximating Weighted Sums with Exponentially Many Terms Deepak Chawla, Lin Li, Stephen Scott

Estimating a Boolean Perceptron from Its Average Satisfying Assignment: A Bound on the Precision Required Paul W. Goldberg

Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces Jürgen Forster, Niels Schmitt, Hans Ulrich Simon

Further Explanation of the Effectiveness of Voting Methods: The Game Between Margins and Weights Vladimir Koltchinskii, Dmitriy Panchenko, Fernando Lozano

Geometric Bounds for Generalization in Boosting Shie Mannor, Ron Meir

Geometric Methods in the Analysis of Glivenko-Cantelli Classes Shahar Mendelson

How Many Queries Are Needed to Learn One Bit of Information? Hans Ulrich Simon

Intrinsic Complexity of Learning Geometrical Concepts from Positive Data Sanjay Jain, Efim B. Kinber

Learning Additive Models Online with Fast Evaluating Kernels Mark Herbster

Learning Monotone DNF from a Teacher That Almost Does Not Answer Membership Queries Nader H. Bshouty, Nadav Eiron

Learning Rates for Q-Learning Eyal Even-Dar, Yishay Mansour

Learning Regular Sets with an Incomplete Membership Oracle Nader H. Bshouty, Avi Owshanko

Learning Relatively Small Classes Shahar Mendelson

Limitations of Learning via Embeddings in Euclidean Half-Spaces Shai Ben-David, Nadav Eiron, Hans Ulrich Simon

On Agnostic Learning with 0, *, 1-Valued and Real-Valued Hypotheses Philip M. Long

On Boosting with Optimal Poly-Bounded Distributions Nader H. Bshouty, Dmitry Gavinsky

On Learning Monotone DNF Under Product Distributions Rocco A. Servedio

On the Synthesis of Strategies Identifying Recursive Functions Sandra Zilles

On Using Extended Statistical Queries to Avoid Membership Queries Nader H. Bshouty, Vitaly Feldman

Optimizing Average Reward Using Discounted Rewards Sham M. Kakade

Pattern Recognition and Density Estimation Under the General I.i.d. Assumption Ilia Nouretdinov, Volodya Vovk, Michael V. Vyugin, Alex Gammerman

Potential-Based Algorithms in Online Prediction and Game Theory Nicolò Cesa-Bianchi, Gábor Lugosi

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results Peter L. Bartlett, Shahar Mendelson

Radial Basis Function Neural Networks Have Superlinear VC Dimension Michael Schmitt

Robust Learning - Rich and Poor John Case, Sanjay Jain, Frank Stephan, Rolf Wiehagen

Smooth Boosting and Learning with Malicious Noise Rocco A. Servedio

Strong Entropy Concentration, Game Theory, and Algorithmic Randomness Peter Grünwald

Toward a Computational Theory of Data Acquisition and Truthing David G. Stork

Tracking a Small Set of Experts by Mixing past Posteriors Olivier Bousquet, Manfred K. Warmuth

Ultraconservative Online Algorithms for Multiclass Problems Koby Crammer, Yoram Singer

When Can Two Unsupervised Learners Achieve PAC Separation? Paul W. Goldberg