Conference Schedule Jump to: Wednesday, Thursday, Friday, Saturday, Sunday Wednesday 30 June 14.00-20.00 Registration   Day 1 - Thursday 1 July 08.30-09.20 Registration 09.20-09.30 Welcome 09.30-10.30 Invited talk: Michael Kearns Game Theory, Automated Trading and Social Networks 10.30-11.00 Coffee Session: Economics and Game Theory (chair: John Shawe-Taylor) 11.00-11.25 Towards a Characterization of Polynomial Preference Elicitation with Value Queries in Combinatorial Auctions Paolo Santi, Vincent Conitzer, Tuomas Sandholm 11.25-11.50 Graphical Economics Sham Kakade, Michael Kearns, Luis Ortiz 11.50-12.15 Deterministic Calibration and Nash Equilibrium Sham Kakade, Dean Foster 12.15-12.40 Reinforcement Learning for Average Reward Zero-Sum Games Shie Mannor 12.40-14.00 Lunch Session: Online Learning (chair: Peter Auer) 14.00-14.25 Polynomial time Prediction Strategy with almost Optimal Mistake Probability Nader Bshouty 14.25-14.50 Minimizing Regret with Label Efficient Prediction Nicolo Cesa-Bianchi, Gabor Lugosi, Gilles Stoltz 14.50-15.15 Regret Bounds for Hierarchical Classification with Linear-Threshold Functions Nicolo Cesa-Bianchi, Alex Conconi, Claudio Gentile 15.15-15.40 Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary H. Brendan McMahan, Avrim Blum 15.40-16.10 Coffee Session: Inductive Inference (chair: Dana Angluin) 16.10-16.35 Learning classes of Probabilistic Automata Francois Denis, Yann Esposito 16.35-17.00 On the learnability of E-pattern languages over small alphabets Daniel Reidenbach 17.00-17.25 Replacing limit learners with equally powerful one-shot query learners Steffen Lange, Sandra Zilles 18:30-20:30 Reception with food Day 2 - Friday 2 July 09.00-10.00 Invited talk: Moses Charikar Algorithmic Aspects of Finite Metric Spaces Session: Probabilistic Models (chair: Rocco Servedio) 10.00-10.25 Concentration Bounds for Unigrams Language Model Evgeny Drukh, Yishay Mansour 10.25-10.50 Inferring Mixtures of Markov Chains Tugkan Batu, Sudipto Guha, Sampath Kannan 10.50-11.15 Coffee Session: Boolean Function Learning (chair: Jeff Jackson) 11.15-11.40 PExact = Exact Learning Dmitry Gavinsky, Avi Owshanko 11.40-12.05 Learning a Hidden Graph Using O(log n) Queries per Edge Dana Angluin, Jiang Chen 12.05-12.30 Toward Attribute Efficient Learning of Decision Lists and Parities Adam Klivans, Rocco Servedio 12.30-14.00 Lunch Session: Empirical Processes (chair: Robert Williamson) 14.00-14.25 Learning over Compact Metric Spaces Minh Ha Quang, Thomas Hofmann 14.25-14.50 A function representation for learning in Banach spaces Massimiliano Pontil, Charles Micchelli 14.50-15.15 Local Complexities for Empirical Risk Minimization Peter Bartlett, Shahar Mendelson, Petra Philips 15.15-15.40 Model selection by bootstrap penalization for classification Magalie Fromont 15.40-16.10 Coffee Session: MDL (chair: Shai Ben-David) 16.10-16.35 Convergence of Discrete MDL for Sequential Prediction Jan Poland, Marcus Hutter 16.35-17.00 On the Convergence of MDL Density Estimation Tong Zhang 17.00-17.25 Suboptimal Behavior of Bayes and MDL in Classification under Misspecification Peter Grunwald, John Langford 18:30-20:30 Reception with food 20:00-20:30 Open problems session   The Budgeted Multi-armed Bandit Problem Omid Madani, Daniel J Lizotte, Russel Greiner   Perceptron-like Performance for Intersections of Halfspaces Adam R Klivans, Rocco A Servedio   The Optimal PAC Algorithm Manfred K Warmuth 20:30-22:00 Business meeting Day 3 - Saturday 3 July 09.00-10.00 Invited talk: Stephen Boyd Convex Opimization, Semidefinite Programming, and Recent Applications Session: Generalisation I (chair: Robert Schapire) 10.00-10.25 Learning Intersections of Halfspaces with a Margin Adam Klivans, Rocco Servedio 10.25-10.50 A General Convergence Theorem for the Decomposition Method Hans Simon, Niko List 10.50-11.15 Coffee Session: Generalisation II (chair: Adam Klivans) 11.15-11.40 Oracle bounds and exact algorithm for dyadic classification trees Gilles Blanchard, Christin Schäfer, Yves Rozenholc 11.40-12.05 An Improved VC Dimension Bound for Sparse Polynomials Michael Schmitt 12.05-12.30 A new PAC-bound for intersection-closed concept classes Peter Auer, Ronald Ortner 12.30-14.00 Lunch Session: Clustering and Distributed Learning (chair: Thore Graepel) 14.00-14.25 A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering Shai Ben-david 14.25-14.50 Data Dependent Risk Bounds For Hierarchical Mixture of Experts Classifiers Arik Azran, Ron Meir 14.50-15.15 Consistency in Models for Communication Constrained Distributed Learning Joel Predd, Sanjeev Kulkarni, H. Vincent Poor 15.15-15.40 Towards convergence of spectral clustering on random samples Ulrike von Luxburg, Olivier Bousquet, Mikhail Belkin 15.40-16.10 Coffee Session: Boosting (chair: Nigel Duffy) 16.10-16.35 Performance Guarantees for Regularized Maximum Entropy Density Estimation Miroslav Dudik, Steven J. Phillips, Robert E. Schapire 16.35-17.00 Learning Monotonic Linear Functions Adam Kalai 17.00-17.25 Boosting Based on a Smooth Margin Cynthia Rudin, Robert E. Schapire, Ingrid Daubechies 18:30-20:30 Reception with food 20:30-22:00 Impromptu session Day 4 - Sunday 4 July Session: Kernels and Probabilities 08.30-08.55 Bayesian Networks and Inner Product Spaces Hans Simon, Atsuyoshi Nakamura, Michael Schmitt, Niels Schmitt 08.55-09.20 An Inequality for Nearly Log-concave Distributions with Applications to Learning Constantine Caramanis, Shie Mannor 09.20-10.45 Bayes and Tukey Meet at the Center Point Ran Gilad-Bachrach, Amir Navot, Naftali Tishby 10.45-10.10 Sparseness vs Estimating Conditional Probabilities: Some Asymptotic Results Peter Bartlett, Ambuj Tewari 10.10-10.40 Coffee Session: Kernels and Kernel Matrices 10:40-11.05 A Statistical Mechanics Analysis of Gram Matrix Eigenvalue Spectra David C Hoyle, Magnus Rattray 11.05-11.30 Statistical Properties of Kernel Principal Component Analysis Laurent Zwald, Olivier Bousquet, Gilles Blanchard 11.30-11.55 Kernelizing Sorting, Permutation and Alignment for Minimum Volume PCA Tony Jebara 11.55-12.20 Regularization and Semisupervised Learning on Large Graphs Mikhail Belkin, Irina Matveeva, Partha Niyogi Jump to: Wednesday, Thursday, Friday, Saturday, Sunday