COLT 2014

60 papers

Online Non-Parametric Regression

Alexander Rakhlin, Karthik Sridharan

Online Learning with Composite Loss Functions

Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres

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

Constantinos Daskalakis, Gautam Kamath

Near-Optimal Herding

Nick Harvey, Samira Samadi

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

Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, James Voss

Resourceful Contextual Bandits

Ashwinkumar Badanidiyuru, John Langford, Aleksandrs Slivkins

The Geometry of Losses

Robert C. Williamson

Compressed Counting Meets Compressed Sensing

Ping Li, Cun-hui Zhang, Tong Zhang

Principal Component Analysis and Higher Correlations for Distributed Data

Ravi Kannan, Santosh Vempala, David Woodruff

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

H. Brendan McMahan, Francesco Orabona

Sample Complexity Bounds on Differentially Private Learning via Communication Complexity

Vitaly Feldman, David Xiao

Lipschitz Bandits: Regret Lower Bound and Optimal Algorithms

Stefan Magureanu, Richard Combes, Alexandre Proutiere

Follow the Leader with Dropout Perturbations

Tim van Erven, Wojciech Kotłowski, Manfred K. Warmuth

Lower Bounds on the Performance of Polynomial-time Algorithms for Sparse Linear Regression

Yuchen Zhang, Martin J. Wainwright, Michael I. Jordan

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

Jiaming Xu, Laurent Massoulié, marc lelarge

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

Harish G. Ramaswamy, Balaji Srinivasan Babu, Shivani Agarwal, Robert C. Williamson

Localized Complexities for Transductive Learning

Ilya Tolstikhin, Gilles Blanchard, Marius Kloft

Learning Mixtures of Discrete Product Distributions using Spectral Decompositions

Prateek Jain, Sewoong Oh

Online Linear Optimization via Smoothing

Jacob Abernethy, Chansoo Lee, Abhinav Sinha, Ambuj Tewari

New Algorithms for Learning Incoherent and Overcomplete Dictionaries

Sanjeev Arora, Rong Ge, Ankur Moitra

Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability

Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan

Robust Multi-objective Learning with Mentor Feedback

Alekh Agarwal, Ashwinkumar Badanidiyuru, Miroslav Dudík, Robert E. Schapire, Aleksandrs Slivkins

Computational Limits for Matrix Completion

Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz

Learning Coverage Functions and Private Release of Marginals

Vitaly Feldman, Pravesh Kothari

Fast matrix completion without the condition number

Moritz Hardt, Mary Wootters

Most Correlated Arms Identification

Che-Yu Liu, Sébastien Bubeck

Efficiency of conformalized ridge regression

Evgeny Burnaev, Vladimir Vovk

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

Yudong Chen, Xinyang Yi, Constantine Caramanis

Density-preserving quantization with application to graph downsampling

Morteza Alamgir, Gabor Lugosi, Ulrike Luxburg

The sample complexity of agnostic learning under deterministic labels

Shai Ben-David, Ruth Urner

Elicitation and Identification of Properties

Ingo Steinwart, Chloé Pasin, Robert Williamson, Siyu Zhang

On the Complexity of A/B Testing

Emilie Kaufmann, Olivier Cappe, Aurélien Garivier

An Inequality with Applications to Structured Sparsity and Multitask Dictionary Learning

Andreas Maurer, Massimiliano Pontil, Bernardino Romera-Paredes

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

Kevin Jamieson, Matthew Malloy, Robert Nowak, Sébastien Bubeck

Volumetric Spanners: an Efficient Exploration Basis for Learning

Elad Hazan, Zohar Karnin, Raghu Meka

Finding a most biased coin with fewest flips

Karthekeyan Chandrasekaran, Richard Karp

Sample Compression for Multi-label Concept Classes

Rahim Samei, Pavel Semukhin, Boting Yang, Sandra Zilles

Belief propagation, robust reconstruction and optimal recovery of block models

Elchanan Mossel, Joe Neeman, Allan Sly

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

Shie Mannor, Vianney Perchet, Gilles Stoltz

Stochastic Regret Minimization via Thompson Sampling

Sudipto Guha, Kamesh Munagala

Optimal learners for multiclass problems

Amit Daniely, Shai Shalev-shwartz

The Complexity of Learning Halfspaces using Generalized Linear Methods

Amit Daniely, Nati Linial, Shai Shalev-shwartz

Higher-Order Regret Bounds with Switching Costs

Eyal Gofer

Logistic Regression: Tight Bounds for Stochastic and Online Optimization

Elad Hazan, Tomer Koren, Kfir Y. Levy

A second-order bound with excess losses

Pierre Gaillard, Gilles Stoltz, Tim van Erven

Community Detection via Random and Adaptive Sampling

Se-Young Yun, Alexandre Proutiere

Learning Sparsely Used Overcomplete Dictionaries

Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, Rashish Tandon

Multiarmed Bandits With Limited Expert Advice

Satyen Kale

Bayes-Optimal Scorers for Bipartite Ranking

Aditya Krishna Menon, Robert C. Williamson

Uniqueness of Ordinal Embedding

Matthäus Kleindessner, Ulrike Luxburg

Learning without concentration

Shahar Mendelson

Distribution-independent Reliable Learning

Varun Kanade, Justin Thaler

Open Problem: Efficient Online Sparse Regression

Satyen Kale

Open Problem: Shifting Experts on Easy Data

Manfred K. Warmuth, Wouter M. Koolen

Open Problem: Online Local Learning

Paul Christiano

Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces

Vitaly Feldman

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

Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan

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

Manuel Gomez-Rodriguez, Le Song, Bernhard Schoelkopf

Open Problem: A (Missing) Boosting-type Convergence Result for AdaBoost.MH with Factorized Multi-class Classifiers

Balázs Kégl

Open Problem: Tightness of maximum likelihood semidefinite relaxations

Afonso S. Bandeira, Yuehaw Khoo, Amit Singer