COLT 2004

46 papers

A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering Shai Ben-David

A Function Representation for Learning in Banach Spaces Charles A. Micchelli, Massimiliano Pontil

A General Convergence Theorem for the Decomposition Method Nikolas List, Hans Ulrich Simon

A New PAC Bound for Intersection-Closed Concept Classes Peter Auer, Ronald Ortner

A Statistical Mechanics Analysis of Gram Matrix Eigenvalue Spectra David C. Hoyle, Magnus Rattray

An Improved VC Dimension Bound for Sparse Polynomials Michael Schmitt

An Inequality for Nearly Log-Concave Distributions with Applications to Learning Constantine Caramanis, Shie Mannor

Bayes and Tukey Meet at the Center Point Ran Gilad-Bachrach, Amir Navot, Naftali Tishby

Bayesian Networks and Inner Product Spaces Atsuyoshi Nakamura, Michael Schmitt, Niels Schmitt, Hans Ulrich Simon

Boosting Based on a Smooth Margin Cynthia Rudin, Robert E. Schapire, Ingrid Daubechies

Concentration Bounds for Unigrams Language Model Evgeny Drukh, Yishay Mansour

Consistency in Models for Communication Constrained Distributed Learning Joel B. Predd, Sanjeev R. Kulkarni, Harold Vincent Poor

Convergence of Discrete MDL for Sequential Prediction Jan Poland, Marcus Hutter

Data Dependent Risk Bounds for Hierarchical Mixture of Experts Classifiers Arik Azran, Ron Meir

Deterministic Calibration and Nash Equilibrium Sham M. Kakade, Dean P. Foster

Graphical Economics Sham M. Kakade, Michael J. Kearns, Luis E. Ortiz

Inferring Mixtures of Markov Chains Tugkan Batu, Sudipto Guha, Sampath Kannan

Kernelizing Sorting, Permutation, and Alignment for Minimum Volume PCA Tony Jebara

Learning a Hidden Graph Using O(log N) Queries per Edge Dana Angluin, Jiang Chen

Learning Classes of Probabilistic Automata François Denis, Yann Esposito

Learning Intersections of Halfspaces with a Margin Adam R. Klivans, Rocco A. Servedio

Learning Monotonic Linear Functions Adam Kalai

Learning over Compact Metric Spaces Ha Quang Minh, Thomas Hofmann

Local Complexities for Empirical Risk Minimization Peter L. Bartlett, Shahar Mendelson, Petra Philips

Minimizing Regret with Label Efficient Prediction Nicolò Cesa-Bianchi, Gábor Lugosi, Gilles Stoltz

Model Selection by Bootstrap Penalization for Classification Magalie Fromont

On the Convergence of MDL Density Estimation Tong Zhang

On the Convergence of Spectral Clustering on Random Samples: The Normalized Case Ulrike von Luxburg, Olivier Bousquet, Mikhail Belkin

On the Learnability of E-Pattern Languages over Small Alphabets Daniel Reidenbach

Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary H. Brendan McMahan, Avrim Blum

Oracle Bounds and Exact Algorithm for Dyadic Classification Trees Gilles Blanchard, Christin Schäfer, Yves Rozenholc

Perceptron-like Performance for Intersections of Halfspaces Adam R. Klivans, Rocco A. Servedio

Performance Guarantees for Regularized Maximum Entropy Density Estimation Miroslav Dudík, Steven J. Phillips, Robert E. Schapire

PExact = Exact Learning Dmitry Gavinsky, Avi Owshanko

Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability Nader H. Bshouty

Regret Bounds for Hierarchical Classification with Linear-Threshold Functions Nicolò Cesa-Bianchi, Alex Conconi, Claudio Gentile

Regularization and Semi-Supervised Learning on Large Graphs Mikhail Belkin, Irina Matveeva, Partha Niyogi

Reinforcement Learning for Average Reward Zero-Sum Games Shie Mannor

Replacing Limit Learners with Equally Powerful One-Shot Query Learners Steffen Lange, Sandra Zilles

Sparseness Versus Estimating Conditional Probabilities: Some Asymptotic Results Peter L. Bartlett, Ambuj Tewari

Statistical Properties of Kernel Principal Component Analysis Laurent Zwald, Olivier Bousquet, Gilles Blanchard

Suboptimal Behavior of Bayes and MDL in Classification Under Misspecification Peter Grünwald, John Langford

The Budgeted Multi-Armed Bandit Problem Omid Madani, Daniel J. Lizotte, Russell Greiner

The Optimal PAC Algorithm Manfred K. Warmuth

Toward Attribute Efficient Learning of Decision Lists and Parities Adam R. Klivans, Rocco A. Servedio

Towards a Characterization of Polynomial Preference Elicitation with Value Queries in Combinatorial Auctions (Extended Abstract) Paolo Santi, Vincent Conitzer, Tuomas Sandholm