Conference on Learning Theory June 25–June 27, 2012 — Edinburgh, Scotland

Towards Minimax Policies for Online Linear Optimization with Bandit Feedback

- Sébastien Bubeck, Nicolo Cesa-Bianchi and Sham M. Kakade

Consistency of nearest neighbor classification under selective sampling

- Sanjoy Dasgupta

(weak) Calibration is Computationally Hard

- Elad Hazan and Sham Kakade

Near-Optimal Algorithms for Online Matrix Prediction

- Elad Hazan, Satyen Kale and Shai Shalev-Shwartz

PAC-Bayesian Bound for Gaussian Process Regression and Multiple Kernel Additive Model

- Taiji Suzuki

A Conjugate Property between Loss Functions and Uncertainty Sets in Classification Problems

- Takafumi Kanamori, Akiko Takeda and Taiji Suzuki

Rare Probability Estimation under Regularly Varying Heavy Tails

- Mesrob Ohannessian and Munther Dahleh

Random Design Analysis of Ridge Regression

- Daniel Hsu, Sham Kakade and Tong Zhang

Reconstruction from anisotropic random measurements

- Mark Rudelson and Shuheng Zhou

$L_1$ Covering Numbers for Uniformly Bounded Convex Functions

- Adityanand Guntuboyina and Bodhisattva Sen

Toward a noncommutative arithmetic-geometric mean inequality

- Benjamin Recht and Christopher Re

Unsupervised SVMs

- Omri Weinstein, Edo Liberty, Shachar Lovett, Roy Schwartz and Zohar Karnin

Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions

- Rocco Servedio, Li-Yang Tan and Justin Thaler

Distance Preserving Embeddings for General n-Dimensional Manifolds

- Nakul Verma

A Method of Moments for Hidden Markov Models and Multi-view Mixture Models

- Animashree Anandkumar, Daniel Hsu and Sham Kakade

Computational Bounds on Statistical Query Learning

- Vitaly Feldman and Varun Kanade

Autonomous Exploration For Navigating In MDPs

- Shiau Hong Lim and Peter Auer

The Optimality of Jeffreys Prior for Online Density Estimation and the Asymptotic Normality of Maximum Likelihood Estimators

- Fares Hedayati and Peter Bartlett

Toward understanding complex spaces

- Mikhail Belkin, Qichao Que, Yusu Wang and Xueyuan Zhou

Kernels based tests with non-asymptotic bootstrap approaches for two-sample problems

- Magalie Fromont, Béatrice Laurent, Matthieu Lerasle and Patricia Reynaud-Bouret

Differentially Private Online Learning

- Prateek Jain, Pravesh Kothari and Abhradeep Thakurta

Active Learning Using Smooth Relative Regret Approximations with Applications

- Nir Ailon, Ron Begleiter and Esther Ezra

The best of both worlds: stochastic and adversarial bandits

- Sébastien Bubeck and Aleksandrs Slivkins

New Bounds for Learning Intervals with Implications for Semi-Supervised Learning

- David Helmbold and Philip Long

Distributed Learning, Communication Complexity and Privacy

- Maria-Florina Balcan, Avrim Blum, Shai Fine and Yishay Mansour

Divergences and Risks for Multiclass Experiments

- Dario Garcia Garcia and Robert C. Williamson

Tight Bounds on Proper Equivalence Query Learning of DNF

- Lisa Hellerstein, Devorah Kletenik, Linda Sellie and Rocco Servedio

Generalization Bounds for Online Learning Algorithms with Pairwise Loss Functions

- Yuyang Wang, Roni Khardon, Dmitry Pechyony and Rosie Jones

Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model

- Kamalika Chaudhuri, Fan Chung and Alexander Tsiatas

Exact Recovery of Sparsely-Used Dictionaries

- Daniel Spielman, Huan Wang and John Wright

Learning of DNF Expressions from Fourier Spectrum

- Vitaly Feldman

Analysis of Thompson Sampling for the multi-armed bandit problem

- Shipra Agrawal and Navin Goyal

Learning Valuation Functions

- Maria-Florina Balcan, Florin Constantin, Satoru Iwata and Lei Wang

A Correlation Clustering Approach to Link Classification in Signed Networks

- Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale and Giovanni Zappella

Differentially Private Convex Optimization for Empirical Risk Minimization with Applications to High-dimensional Regression

- Daniel Kifer, Adam Smith and Abhradeep Thakurta

Competitive Classification and Closeness Testing

- Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan and Ananda Theertha Suresh

A Characterization of Scoring Rules for Linear Properties

- Rafael Frongillo and Jacob Abernethy

Unified Algorithms for Online Learning and Competitive Analysis

- Niv Buchbinder, Shahar Chen, Joseph Naor and Ohad Shamir

Robust Interactive Learning

- Maria-Florina Balcan and Steve Hanneke

Learning Functions of Halfspaces using Prefix Covers

- Parikshit Gopalan, Adam Klivans and Raghu Meka

Online Optimization with Gradual Variations

- Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin and Shenghuo Zhu