COLT 2008

51 papers

A Query Algorithm for Agnostically Learning DNF? Parikshit Gopalan, Adam Kalai, Adam R. Klivans

Adapting to a Changing Environment: The Brownian Restless Bandits Aleksandrs Slivkins, Eli Upfal

Adaptive Aggregation for Reinforcement Learning with Efficient Exploration: Deterministic Domains Andrey Bernstein, Nahum Shimkin

Adaptive Hausdorff Estimation of Density Level Sets Aarti Singh, Robert D. Nowak, Clayton D. Scott

Almost Tight Upper Bound for Finding Fourier Coefficients of Bounded Pseudo- Boolean Functions Sung-Soon Choi, Kyomin Jung, Jeong Han Kim

An Efficient Reduction of Ranking to Classification Nir Ailon, Mehryar Mohri

An Information Theoretic Framework for Multi-View Learning Karthik Sridharan, Sham M. Kakade

Beyond Gaussians: Spectral Methods for Learning Mixtures of Heavy-Tailed Distributions Kamalika Chaudhuri, Satish Rao

Combinatorial Prediction Markets Robin Hanson

Combining Expert Advice Efficiently Wouter M. Koolen, Steven de Rooij

Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization Jacob D. Abernethy, Elad Hazan, Alexander Rakhlin

Concentration Inequalities Gábor Lugosi

Density Estimation in Linear Time Satyaki Mahalanabis, Daniel Stefankovic

Dimension and Margin Bounds for Reflection-Invariant Kernels Thorsten Doliwa, Michael Kallweit, Hans Ulrich Simon

Does Unlabeled Data Provably Help? Worst-Case Analysis of the Sample Complexity of Semi-Supervised Learning Shai Ben-David, Tyler Lu, Dávid Pál

Extracting Certainty from Uncertainty: Regret Bounded by Variation in Costs Elad Hazan, Satyen Kale

Finding Metric Structure in Information Theoretic Clustering Kamalika Chaudhuri, Andrew McGregor

Geometric & Topological Representations of Maximum Classes with Applications to Sample Compression J. Hyam Rubinstein, Benjamin I. P. Rubinstein

High-Probability Regret Bounds for Bandit Online Linear Optimization Peter L. Bartlett, Varsha Dani, Thomas P. Hayes, Sham M. Kakade, Alexander Rakhlin, Ambuj Tewari

How Local Should a Learning Method Be? Alon Zakai, Yaacov Ritov

Improved Guarantees for Learning via Similarity Functions Maria-Florina Balcan, Avrim Blum, Nathan Srebro

Injective Hilbert Space Embeddings of Probability Measures Bharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Gert R. G. Lanckriet, Bernhard Schölkopf

Learning Acyclic Probabilistic Circuits Using Test Paths Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, Lev Reyzin

Learning Coordinate Gradients with Multi-Task Kernels Yiming Ying, Colin Campbell

Learning from Collective Behavior Michael J. Kearns, Jennifer Wortman

Learning in the Limit with Adversarial Disturbances Constantine Caramanis, Shie Mannor

Learning Mixtures of Product Distributions Using Correlations and Independence Kamalika Chaudhuri, Satish Rao

Learning Random Monotone DNF Under the Uniform Distribution Linda Sellie

Learning Rotations Adam M. Smith, Manfred K. Warmuth

Linear Algorithms for Online Multitask Classification Giovanni Cavallanti, Nicolò Cesa-Bianchi, Claudio Gentile

Minimizing Wide Range Regret with Time Selection Functions Subhash Khot, Ashok Kumar Ponnuswami

Model Selection and Stability in K-Means Clustering Ohad Shamir, Naftali Tishby

More Efficient Internal-Regret-Minimizing Algorithms Amy Greenwald, Zheng Li, Warren Schudy

On the Equivalence of Weak Learnability and Linear Separability: New Relaxations and Efficient Boosting Algorithms Shai Shalev-Shwartz, Yoram Singer

On the Margin Explanation of Boosting Algorithms Liwei Wang, Masashi Sugiyama, Cheng Yang, Zhi-Hua Zhou, Jufu Feng

On the Power of Membership Queries in Agnostic Learning Vitaly Feldman

On-Line Sequential Bin Packing András György, Gábor Lugosi, György Ottucsák

Online Learning of Maximum P-Norm Margin Classifiers with Bias Kosuke Ishibashi, Kohei Hatano, Masayuki Takeda

Optimal Stragies and Minimax Lower Bounds for Online Convex Games Jacob D. Abernethy, Peter L. Bartlett, Alexander Rakhlin, Ambuj Tewari

Polynomial Regression Under Arbitrary Product Distributions Eric Blais, Ryan O'Donnell, Karl Wimmer

Regret Bounds for Sleeping Experts and Bandits Robert D. Kleinberg, Alexandru Niculescu-Mizil, Yogeshwer Sharma

Relating Clustering Stability to Properties of Cluster Boundaries Shai Ben-David, Ulrike von Luxburg

Sparse Recovery in Large Ensembles of Kernel Machines On-Line Learning and Bandits Vladimir Koltchinskii, Ming Yuan

Stochastic Linear Optimization Under Bandit Feedback Varsha Dani, Thomas P. Hayes, Sham M. Kakade

Teaching Dimensions Based on Cooperative Learning Sandra Zilles, Steffen Lange, Robert Holte, Martin Zinkevich

The Catch-up Phenomenon in Bayesian Inference Peter Grunwald

The Learning Power of Evolution Vitaly Feldman, Leslie G. Valiant

The True Sample Complexity of Active Learning Maria-Florina Balcan, Steve Hanneke, Jennifer Wortman

Time Varying Undirected Graphs Shuheng Zhou, John D. Lafferty, Larry A. Wasserman

Unsupervised Learning for Natural Language Processing Dan Klein

When Random Play Is Optimal Against an Adversary Jacob D. Abernethy, Manfred K. Warmuth, Joel Yellin