COLT 2015

76 papers

A Chaining Algorithm for Online Nonparametric Regression Pierre Gaillard, Sébastien Gerchinovitz

A PTAS for Agnostically Learning Halfspaces Amit Daniely

Achieving All with No Parameters: AdaNormalHedge Haipeng Luo, Robert E. Schapire

Adaptive Recovery of Signals by Convex Optimization Zaïd Harchaoui, Anatoli B. Juditsky, Arkadi Nemirovski, Dmitry Ostrovsky

PDF

Algorithms for Lipschitz Learning on Graphs Rasmus Kyng, Anup Rao, Sushant Sachdeva, Daniel A. Spielman

PDF

An Almost Optimal PAC Algorithm Hans Ulrich Simon

PDF

Bad Universal Priors and Notions of Optimality Jan Leike, Marcus Hutter

PDF

Bandit Convex Optimization: \(\sqrt{T}\) Regret in One Dimension Sébastien Bubeck, Ofer Dekel, Tomer Koren, Yuval Peres

PDF

Batched Bandit Problems Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg

PDF

Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering Justin Eldridge, Mikhail Belkin, Yusu Wang

PDF

Competing with the Empirical Risk Minimizer in a Single Pass Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford

PDF

Computational Lower Bounds for Community Detection on Random Graphs Bruce E. Hajek, Yihong Wu, Jiaming Xu

PDF

Contextual Dueling Bandits Miroslav Dudík, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, Masrour Zoghi

PDF

Convex Risk Minimization and Conditional Probability Estimation Matus Telgarsky, Miroslav Dudík

PDF

Correlation Clustering with Noisy Partial Information Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

PDF

Cortical Learning via Prediction Christos H. Papadimitriou, Santosh S. Vempala

PDF

Efficient Learning of Linear Separators Under Bounded Noise Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Ruth Urner

PDF

Efficient Representations for Lifelong Learning and Autoencoding Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala

PDF

Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng

PDF

Escaping from Saddle Points - Online Stochastic Gradient for Tensor Decomposition Rong Ge, Furong Huang, Chi Jin, Yang Yuan

PDF

Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, Alexander Rakhlin

PDF

Exp-Concavity of Proper Composite Losses Parameswaran Kamalaruban, Robert C. Williamson, Xinhua Zhang

PDF

Fast Exact Matrix Completion with Finite Samples Prateek Jain, Praneeth Netrapalli

PDF

Fast Mixing for Discrete Point Processes Patrick Rebeschini, Amin Karbasi

PDF

Faster Algorithms for Testing Under Conditional Sampling Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, Ananda Theertha Suresh

PDF

First-Order Regret Bounds for Combinatorial Semi-Bandits Gergely Neu

PDF

From Averaging to Acceleration, There Is Only a Step-Size Nicolas Flammarion, Francis R. Bach

PDF

Generalized Mixability via Entropic Duality Mark D. Reid, Rafael M. Frongillo, Robert C. Williamson, Nishant A. Mehta

PDF

Hierarchical Label Queries with Data-Dependent Partitions Samory Kpotufe, Ruth Urner, Shai Ben-David

PDF

Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints Alexander Rakhlin, Karthik Sridharan

PDF

Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems Yash Deshpande, Andrea Montanari

PDF

Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery Thomas Steinke, Jonathan R. Ullman

PDF

Label Optimal Regret Bounds for Online Local Learning Pranjal Awasthi, Moses Charikar, Kevin A. Lai, Andrej Risteski

PDF

Learnability of Solutions to Conjunctive Queries: The Full Dichotomy Hubie Chen, Matthew Valeriote

PDF

Learning and Inference in the Presence of Corrupted Inputs Uriel Feige, Yishay Mansour, Robert E. Schapire

PDF

Learning Overcomplete Latent Variable Models Through Tensor Methods Animashree Anandkumar, Rong Ge, Majid Janzamin

PDF

Learning the Dependence Structure of Rare Events: A Non-Asymptotic Study Nicolas Goix, Anne Sabourin, Stéphan Clémençon

PDF

Learning with Square Loss: Localization Through Offset Rademacher Complexity Tengyuan Liang, Alexander Rakhlin, Karthik Sridharan

PDF

Low Rank Matrix Completion with Exponential Family Noise Jean Lafond

PDF

Lower and Upper Bounds on the Generalization of Stochastic Exponentially Concave Optimization Mehrdad Mahdavi, Lijun Zhang, Rong Jin

PDF

Max vs Min: Tensor Decomposition and ICA with Nearly Linear Sample Complexity Santosh S. Vempala, Ying Xiao

PDF

MCMC Learning Varun Kanade, Elchanan Mossel

PDF

Minimax Fixed-Design Linear Regression Peter L. Bartlett, Wouter M. Koolen, Alan Malek, Eiji Takimoto, Manfred K. Warmuth

PDF

Minimax Rates for Memory-Bounded Sparse Linear Regression Jacob Steinhardt, John C. Duchi

PDF

Norm-Based Capacity Control in Neural Networks Behnam Neyshabur, Ryota Tomioka, Nathan Srebro

PDF

On Consistent Surrogate Risk Minimization and Property Elicitation Arpit Agarwal, Shivani Agarwal

PDF

On Convergence of Emphatic Temporal-Difference Learning Huizhen Yu

PDF

On Learning Distributions from Their Samples Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, Ananda Theertha Suresh

PDF

On the Complexity of Bandit Linear Optimization Ohad Shamir

PDF

On the Complexity of Learning with Kernels Nicolò Cesa-Bianchi, Yishay Mansour, Ohad Shamir

PDF

On-Line Learning Algorithms for Path Experts with Non-Additive Losses Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Manfred K. Warmuth

PDF

Online Density Estimation of Bradley-Terry Models Issei Matsumoto, Kohei Hatano, Eiji Takimoto

PDF

Online Learning with Feedback Graphs: Beyond Bandits Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, Tomer Koren

PDF

Online with Spectral Bounds Zohar Shay Karnin, Edo Liberty

Open Problem: Learning Quantum Circuits with Queries Jeremy Kun, Lev Reyzin

PDF

Open Problem: Online Sabotaged Shortest Path Wouter M. Koolen, Manfred K. Warmuth, Dmitry Adamskiy

PDF

Open Problem: Recursive Teaching Dimension Versus VC Dimension Hans Ulrich Simon, Sandra Zilles

PDF

Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs Arindam Banerjee, Sheng Chen, Vidyashankar Sivakumar

PDF

Open Problem: The Landscape of the Loss Surfaces of Multilayer Networks Anna Choromanska, Yann LeCun, Gérard Ben Arous

PDF

Open Problem: The Oracle Complexity of Smooth Convex Optimization in Nonstandard Settings Cristóbal Guzmán

PDF

Optimally Combining Classifiers Using Unlabeled Data Akshay Balsubramani, Yoav Freund

PDF

Optimum Statistical Estimation with Strategic Data Sources Yang Cai, Constantinos Daskalakis, Christos H. Papadimitriou

PDF

Partitioning Well-Clustered Graphs: Spectral Clustering Works! Richard Peng, He Sun, Luca Zanetti

PDF

Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem Junpei Komiyama, Junya Honda, Hisashi Kashima, Hiroshi Nakagawa

PDF

Regularized Linear Regression: A Precise Analysis of the Estimation Error Christos Thrampoulidis, Samet Oymak, Babak Hassibi

PDF

S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification Gautam Dasarathy, Robert D. Nowak, Xiaojin Zhu

PDF

Second-Order Quantile Methods for Experts and Combinatorial Games Wouter M. Koolen, Tim van Erven

PDF

Sequential Information Maximization: When Is Greedy Near-Optimal? Yuxin Chen, S. Hamed Hassani, Amin Karbasi, Andreas Krause

PDF

Simple, Efficient, and Neural Algorithms for Sparse Coding Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra

PDF

Stochastic Block Model and Community Detection in Sparse Graphs: A Spectral Algorithm with Optimal Rate of Recovery Peter Chin, Anup Rao, Van Vu

PDF

Tensor Principal Component Analysis via Sum-of-Square Proofs Samuel B. Hopkins, Jonathan Shi, David Steurer

PDF

The Entropic Barrier: A Simple and Optimal Universal Self-Concordant Barrier Sébastien Bubeck, Ronen Eldan

PDF

Thompson Sampling for Learning Parameterized Markov Decision Processes Aditya Gopalan, Shie Mannor

PDF

Truthful Linear Regression Rachel Cummings, Stratis Ioannidis, Katrina Ligett

PDF

Variable Selection Is Hard Dean P. Foster, Howard J. Karloff, Justin Thaler

PDF

Vector-Valued Property Elicitation Rafael M. Frongillo, Ian A. Kash

PDF