COLT 2014

60 papers

A Convex Formulation for Mixed Regression with Two Components: Minimax Optimal Rates Yudong Chen, Xinyang Yi, Constantine Caramanis

A Second-Order Bound with Excess Losses Pierre Gaillard, Gilles Stoltz, Tim van Erven

An Inequality with Applications to Structured Sparsity and Multitask Dictionary Learning Andreas Maurer, Massimiliano Pontil, Bernardino Romera-Paredes

Approachability in Unknown Games: Online Learning Meets Multi-Objective Optimization Shie Mannor, Vianney Perchet, Gilles Stoltz

Bayes-Optimal Scorers for Bipartite Ranking Aditya Krishna Menon, Robert C. Williamson

Belief Propagation, Robust Reconstruction and Optimal Recovery of Block Models Elchanan Mossel, Joe Neeman, Allan Sly

Community Detection via Random and Adaptive Sampling Se-Young Yun, Alexandre Proutière

Compressed Counting Meets Compressed Sensing Ping Li, Cun-Hui Zhang, Tong Zhang

Computational Limits for Matrix Completion Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz

Density-Preserving Quantization with Application to Graph Downsampling Morteza Alamgir, Gábor Lugosi, Ulrike von Luxburg

Distribution-Independent Reliable Learning Varun Kanade, Justin Thaler

Edge Label Inference in Generalized Stochastic Block Models: From Spectral Theory to Impossibility Results Jiaming Xu, Laurent Massoulié, Marc Lelarge

Efficiency of Conformalized Ridge Regression Evgeny Burnaev, Vladimir Vovk

Elicitation and Identification of Properties Ingo Steinwart, Chloé Pasin, Robert C. Williamson, Siyu Zhang

Fast Matrix Completion Without the Condition Number Moritz Hardt, Mary Wootters

Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians Constantinos Daskalakis, Gautam Kamath

Finding a Most Biased Coin with Fewest Flips Karthekeyan Chandrasekaran, Richard M. Karp

Follow the Leader with Dropout Perturbations Tim van Erven, Wojciech Kotlowski

Higher-Order Regret Bounds with Switching Costs Eyal Gofer

Learning Coverage Functions and Private Release of Marginals Vitaly Feldman, Pravesh Kothari

Learning Mixtures of Discrete Product Distributions Using Spectral Decompositions Prateek Jain, Sewoong Oh

Learning Sparsely Used Overcomplete Dictionaries Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, Rashish Tandon

Learning Without Concentration Shahar Mendelson

Lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits Kevin G. Jamieson, Matthew Malloy, Robert D. Nowak, Sébastien Bubeck

Lipschitz Bandits: Regret Lower Bound and Optimal Algorithms Stefan Magureanu, Richard Combes, Alexandre Proutière

Localized Complexities for Transductive Learning Ilya O. Tolstikhin, Gilles Blanchard, Marius Kloft

Logistic Regression: Tight Bounds for Stochastic and Online Optimization Elad Hazan, Tomer Koren, Kfir Y. Levy

Lower Bounds on the Performance of Polynomial-Time Algorithms for Sparse Linear Regression Yuchen Zhang, Martin J. Wainwright, Michael I. Jordan

Most Correlated Arms Identification Che-Yu Liu, Sébastien Bubeck

Multiarmed Bandits with Limited Expert Advice Satyen Kale

Near-Optimal Herding Nick Harvey, Samira Samadi

New Algorithms for Learning Incoherent and Overcomplete Dictionaries Sanjeev Arora, Rong Ge, Ankur Moitra

On the Complexity of A/B Testing Emilie Kaufmann, Olivier Cappé, Aurélien Garivier

On the Consistency of Output Code Based Learning Algorithms for Multiclass Learning Problems Harish G. Ramaswamy, Balaji Srinivasan Babu, Shivani Agarwal, Robert C. Williamson

Online Learning with Composite Loss Functions Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres

Online Linear Optimization via Smoothing Jacob D. Abernethy, Chansoo Lee, Abhinav Sinha, Ambuj Tewari

Online Non-Parametric Regression Alexander Rakhlin, Karthik Sridharan

Open Problem: A (missing) Boosting-Type Convergence Result for AdaBoost.MH with Factorized Multi-Class Classifiers Balázs Kégl

Open Problem: Efficient Online Sparse Regression Satyen Kale

Open Problem: Finding Good Cascade Sampling Processes for the Network Inference Problem Manuel Gomez-Rodriguez, Le Song, Bernhard Schölkopf

Open Problem: Online Local Learning Paul F. Christiano

Open Problem: Shifting Experts on Easy Data Manfred K. Warmuth, Wouter M. Koolen

Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold? Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan

Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces Vitaly Feldman

Open Problem: Tightness of Maximum Likelihood Semidefinite Relaxations Afonso S. Bandeira, Yuehaw Khoo, Amit Singer

Optimal Learners for Multiclass Problems Amit Daniely, Shai Shalev-Shwartz

Principal Component Analysis and Higher Correlations for Distributed Data Ravi Kannan, Santosh S. Vempala, David P. Woodruff

Resourceful Contextual Bandits Ashwinkumar Badanidiyuru, John Langford, Aleksandrs Slivkins

Robust Multi-Objective Learning with Mentor Feedback Alekh Agarwal, Ashwinkumar Badanidiyuru, Miroslav Dudík, Robert E. Schapire, Aleksandrs Slivkins

Sample Complexity Bounds on Differentially Private Learning via Communication Complexity Vitaly Feldman, David Xiao

Sample Compression for Multi-Label Concept Classes Rahim Samei, Pavel Semukhin, Boting Yang, Sandra Zilles

Stochastic Regret Minimization via Thompson Sampling Sudipto Guha, Kamesh Munagala

The Complexity of Learning Halfspaces Using Generalized Linear Methods Amit Daniely, Nati Linial, Shai Shalev-Shwartz

The Geometry of Losses Robert C. Williamson

The More, the Merrier: The Blessing of Dimensionality for Learning Large Gaussian Mixtures Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, James R. Voss

The Sample Complexity of Agnostic Learning Under Deterministic Labels Shai Ben-David, Ruth Urner

Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations H. Brendan McMahan, Francesco Orabona

Uniqueness of Ordinal Embedding Matthäus Kleindessner, Ulrike von Luxburg

Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan

Volumetric Spanners: An Efficient Exploration Basis for Learning Elad Hazan, Zohar Shay Karnin, Raghu Meka