Volume 35: Conference on Learning Theory, 13-15 June 2014, Barcelona, Spain


Editors: Maria Florina Balcan, Vitaly Feldman, Csaba Szepesvári





Maria Florina Balcan, Csaba Szepesvári ; PMLR 35:1-2

Regular Papers

Open Problems

Open Problem: Tightness of maximum likelihood semidefinite relaxations

Afonso S. Bandeira, Yuehaw Khoo, Amit Singer ; PMLR 35:1265-1267

Open Problem: A (missing) boosting-type convergence result for \textscAdaBoost.MH with factorized multi-class classifiers

Balázs Kégl ; PMLR 35:1268-1275

Open Problem: Finding Good Cascade Sampling Processes for the Network Inference Problem

Manuel Gomez-Rodriguez, Le Song, Bernhard Schoelkopf ; PMLR 35:1276-1279

Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold?

Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan ; PMLR 35:1280-1282

Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces

Vitaly Feldman ; PMLR 35:1283-1289

Open Problem: Online Local Learning

Paul Christiano ; PMLR 35:1290-1294

Open Problem: Shifting Experts on Easy Data

Manfred K. Warmuth, Wouter M. Koolen ; PMLR 35:1295-1298

Open Problem: Efficient Online Sparse Regression

Satyen Kale ; PMLR 35:1299-1301

Distribution-independent Reliable Learning

Varun Kanade, Justin Thaler ; PMLR 35:3-24

Learning without concentration

Shahar Mendelson ; PMLR 35:25-39

Uniqueness of Ordinal Embedding

Matthäus Kleindessner, Ulrike Luxburg ; PMLR 35:40-67

Bayes-Optimal Scorers for Bipartite Ranking

Aditya Krishna Menon, Robert C. Williamson ; PMLR 35:68-106

Multiarmed Bandits With Limited Expert Advice

Satyen Kale ; PMLR 35:107-122

Learning Sparsely Used Overcomplete Dictionaries

Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, Rashish Tandon ; PMLR 35:123-137

Community Detection via Random and Adaptive Sampling

Se-Young Yun, Alexandre Proutiere ; PMLR 35:138-175

A second-order bound with excess losses

Pierre Gaillard, Gilles Stoltz, Tim van Erven ; PMLR 35:176-196

Logistic Regression: Tight Bounds for Stochastic and Online Optimization

Elad Hazan, Tomer Koren, Kfir Y. Levy ; PMLR 35:197-209

Higher-Order Regret Bounds with Switching Costs

Eyal Gofer ; PMLR 35:210-243

The Complexity of Learning Halfspaces using Generalized Linear Methods

Amit Daniely, Nati Linial, Shai Shalev-Shwartz ; PMLR 35:244-286

Optimal learners for multiclass problems

Amit Daniely, Shai Shalev-Shwartz ; PMLR 35:287-316

Stochastic Regret Minimization via Thompson Sampling

Sudipto Guha, Kamesh Munagala ; PMLR 35:317-338

Approachability in unknown games: Online learning meets multi-objective optimization

Shie Mannor, Vianney Perchet, Gilles Stoltz ; PMLR 35:339-355

Belief propagation, robust reconstruction and optimal recovery of block models

Elchanan Mossel, Joe Neeman, Allan Sly ; PMLR 35:356-370

Sample Compression for Multi-label Concept Classes

Rahim Samei, Pavel Semukhin, Boting Yang, Sandra Zilles ; PMLR 35:371-393

Finding a most biased coin with fewest flips

Karthekeyan Chandrasekaran, Richard Karp ; PMLR 35:394-407

Volumetric Spanners: an Efficient Exploration Basis for Learning

Elad Hazan, Zohar Karnin, Raghu Meka ; PMLR 35:408-422

lil’ UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits

Kevin Jamieson, Matthew Malloy, Robert Nowak, Sébastien Bubeck ; PMLR 35:423-439

An Inequality with Applications to Structured Sparsity and Multitask Dictionary Learning

Andreas Maurer, Massimiliano Pontil, Bernardino Romera-Paredes ; PMLR 35:440-460

On the Complexity of A/B Testing

Emilie Kaufmann, Olivier Cappé, Aurélien Garivier ; PMLR 35:461-481

Elicitation and Identification of Properties

Ingo Steinwart, Chloé Pasin, Robert Williamson, Siyu Zhang ; PMLR 35:482-526

The sample complexity of agnostic learning under deterministic labels

Shai Ben-David, Ruth Urner ; PMLR 35:527-542

Density-preserving quantization with application to graph downsampling

Morteza Alamgir, Gábor Lugosi, Ulrike Luxburg ; PMLR 35:543-559

A Convex Formulation for Mixed Regression with Two Components: Minimax Optimal Rates

Yudong Chen, Xinyang Yi, Constantine Caramanis ; PMLR 35:560-604

Efficiency of conformalized ridge regression

Evgeny Burnaev, Vladimir Vovk ; PMLR 35:605-622

Most Correlated Arms Identification

Che-Yu Liu, Sébastien Bubeck ; PMLR 35:623-637

Fast matrix completion without the condition number

Moritz Hardt, Mary Wootters ; PMLR 35:638-678

Learning Coverage Functions and Private Release of Marginals

Vitaly Feldman, Pravesh Kothari ; PMLR 35:679-702

Computational Limits for Matrix Completion

Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz ; PMLR 35:703-725

Robust Multi-objective Learning with Mentor Feedback

Alekh Agarwal, Ashwinkumar Badanidiyuru, Miroslav Dudík, Robert E. Schapire, Aleksandrs Slivkins ; PMLR 35:726-741

Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability

Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan ; PMLR 35:742-778

New Algorithms for Learning Incoherent and Overcomplete Dictionaries

Sanjeev Arora, Rong Ge, Ankur Moitra ; PMLR 35:779-806

Online Linear Optimization via Smoothing

Jacob Abernethy, Chansoo Lee, Abhinav Sinha, Ambuj Tewari ; PMLR 35:807-823

Learning Mixtures of Discrete Product Distributions using Spectral Decompositions

Prateek Jain, Sewoong Oh ; PMLR 35:824-856

Localized Complexities for Transductive Learning

Ilya Tolstikhin, Gilles Blanchard, Marius Kloft ; PMLR 35:857-884

On the Consistency of Output Code Based Learning Algorithms for Multiclass Learning Problems

Harish G. Ramaswamy, Balaji Srinivasan Babu, Shivani Agarwal, Robert C. Williamson ; PMLR 35:885-902

Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results

Jiaming Xu, Laurent Massoulié, Marc Lelarge ; PMLR 35:903-920

Lower bounds on the performance of polynomial-time algorithms for sparse linear regression

Yuchen Zhang, Martin J. Wainwright, Michael I. Jordan ; PMLR 35:921-948

Follow the Leader with Dropout Perturbations

Tim Van Erven, Wojciech Kotłowski, Manfred K. Warmuth ; PMLR 35:949-974

Lipschitz Bandits: Regret Lower Bound and Optimal Algorithms

Stefan Magureanu, Richard Combes, Alexandre Proutiere ; PMLR 35:975-999

Sample Complexity Bounds on Differentially Private Learning via Communication Complexity

Vitaly Feldman, David Xiao ; PMLR 35:1000-1019

Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations

H. Brendan McMahan, Francesco Orabona ; PMLR 35:1020-1039

Principal Component Analysis and Higher Correlations for Distributed Data

Ravi Kannan, Santosh Vempala, David Woodruff ; PMLR 35:1040-1057

Compressed Counting Meets Compressed Sensing

Ping Li, Cun-Hui Zhang, Tong Zhang ; PMLR 35:1058-1077

The Geometry of Losses

Robert C. Williamson ; PMLR 35:1078-1108

Resourceful Contextual Bandits

Ashwinkumar Badanidiyuru, John Langford, Aleksandrs Slivkins ; PMLR 35:1109-1134

The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures

Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, James Voss ; PMLR 35:1135-1164

Near-Optimal Herding

Nick Harvey, Samira Samadi ; PMLR 35:1165-1182

Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians

Constantinos Daskalakis, Gautam Kamath ; PMLR 35:1183-1213

Online Learning with Composite Loss Functions

Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres ; PMLR 35:1214-1231

Online Non-Parametric Regression

Alexander Rakhlin, Karthik Sridharan ; PMLR 35:1232-1264

subscribe via RSS

This site last compiled Sat, 11 Mar 2017 19:38:42 +0000
Github Account Copyright © PMLR 2017. All rights reserved.