Learning Theory Book

	Towards a characterization of polynomial preference elicitation with value queries in combinatorial auctions	1
	Graphical economics	17
	Deterministic calibration and Nash equilibrium	33
	Reinforcement learning for average reward zero-sum games	49
	Polynomial time prediction strategy with almost optimal mistake probability	64
	Minimizing regret with label efficient prediction	77
	Regret bounds for hierarchical classification with linear-threshold functions	93
	Online geometric optimization in the bandit setting against an adaptive adversary	109
	Learning classes of probabilistic automata	124
	On the learnability of E-pattern languages over small alphabets	140
	Replacing limit learners with equally powerful one-shot query learners	155
	Concentration bounds for unigrams language model	170
	Inferring mixtures of Markov Chains	186
	PExact = exact learning	200
	Learning a hidden graph using O(log n) queries per edge	210
	Toward attribute efficient learning of dicision lists and parities	224
	Learning over compact metric spaces	239
	A function representation for learning in banach spaces	255
	Local complexities for empirical risk minimization	270
	Model selection by bootstrap penalization for classification	285
	Convergence of discrete MDL for sequential prediction	300
	On the convergence of MDL density estimation	315
	Suboptimal behavior of bayes and MDL in classification under misspecification	331
	Learning intersections of halfspaces with a margin	348
	A general convergence theorem for the decomposition method	363
	Oracle bounds and exact algorithm for dyadic classification trees	378
	An Improved VC dimension bound for sparse polynomials	393
	A new PAC bound for intersection-closed concept classes	408
	A framework for statistical clustering with a constant time approximation algorithms for K-median clustering	415
	Data dependent risk bounds for hierarchical mixture of experts classifiers	427
	Consistency in models for communication constrained distributed learning	442
	On the convergence of spectral clustering on random samples : the normalized case	457
	Performance guarantees for regularized maximum entropy density estimation	472
	Learning monotonic linear functions	487
	Boosting based on a smooth margin	502
	Bayesian networks and inner product spaces	518
	An inequality for nearly log-concave distributions with applications to learning	534
	Bayes and tukey meet at the center point	549
	Sparseness versus estimating conditional probabilities : some asymptotic results	564
	A statistical mechanics analysis of Gram matrix eigenvalue spectra	579
	Statistical properties of kernel principal component analysis	594
	Kernelizing sorting, permutation, and alignment for minimum volume PCA	609
	Regularization and semi-supervised learning on large graphs	624
	Perceptron-like performance for intersections of halfspaces	639
	The optimal PAC algorithm	641
	The budgeted multi-armed bandit problem	643