COLT 2017

76 papers

A General Characterization of the Statistical Query Complexity Vitaly Feldman

A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics Yuchen Zhang, Percy Liang, Moses Charikar

A Second-Order Look at Stability and Generalization Andreas Maurer

A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints Bin Hu, Peter Seiler, Anders Rantzer

Adaptivity to Noise Parameters in Nonparametric Active Learning Carpentier Alexandra Locatelli Andrea, Kpotufe Samory

Algorithmic Chaining and the Role of Partial Feedback in Online Nonparametric Learning Nicolò Cesa-Bianchi, Pierre Gaillard, Claudio Gentile, Sébastien Gerchinovitz

An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits Yevgeny Seldin, Gábor Lugosi

Bandits with Movement Costs and Adaptive Pricing Tomer Koren, Roi Livni, Yishay Mansour

Computationally Efficient Robust Sparse Estimation in High Dimensions Sivaraman Balakrishnan, Simon S. Du, Jerry Li, Aarti Singh

Corralling a Band of Bandit Algorithms Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, Robert E. Schapire

Correspondence Retrieval Alexandr Andoni, Daniel Hsu, Kevin Shi, Xiaorui Sun

Depth Separation for Neural Networks Amit Daniely

Effective Semisupervised Learning on Manifolds Amir Globerson, Roi Livni, Shai Shalev-Shwartz

Efficient Co-Training of Linear Separators Under Weak Dependence Avrim Blum, Yishay Mansour

Efficient PAC Learning from the Crowd Pranjal Awasthi, Avrim Blum, Nika Haghtalab, Yishay Mansour

Empirical Risk Minimization for Stochastic Convex Optimization: $O(1/n)$- and $O(1/n^2)$-Type of Risk Bounds Lijun Zhang, Tianbao Yang, Rong Jin

Exact Tensor Completion with Sum-of-Squares Aaron Potechin, David Steurer

Fast and Robust Tensor Decomposition with Applications to Dictionary Learning Tselil Schramm, David Steurer

Fast Rates for Empirical Risk Minimization of Strict Saddle Problems Alon Gonen, Shai Shalev-Shwartz

Fast Rates for Online Learning in Linearly Solvable Markov Decision Processes Gergely Neu, Vicenç Gómez

Fundamental Limits of Symmetric Low-Rank Matrix Estimation Marc Lelarge, Léo Miolane

Further and Stronger Analogy Between Sampling and Optimization: Langevin Monte Carlo and Gradient Descent Arnak Dalalyan

Generalization for Adaptively-Chosen Estimators via Stable Median Vitaly Feldman, Thomas Steinke

Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization Moran Feldman, Christopher Harshaw, Amin Karbasi

High Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transtition Gamarnik David, Zadik Ilias

Homotopy Analysis for Tensor PCA Anima Anandkumar, Yuan Deng, Rong Ge, Hossein Mobahi

Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization Daniel Vainsencher, Shie Mannor, Huan Xu

Inapproximability of VC Dimension and Littlestone’s Dimension Pasin Manurangsi, Aviad Rubinstein

Learning Disjunctions of Predicates Nader H. Bshouty, Dana Drachsler-Cohen, Martin Vechev, Eran Yahav

Learning Multivariate Log-Concave Distributions Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

Learning Non-Discriminatory Predictors Blake Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian, Nathan Srebro

Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, Sanjeev Khanna

Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, Colin White

Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization Jonathan Scarlett, Ilija Bogunovic, Volkan Cevher

Matrix Completion from $O(n)$ Samples in Linear Time David Gamarnik, Quan Li, Hongyi Zhang

Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox Jialei Wang, Weiran Wang, Nathan Srebro

Memoryless Sequences for Differentiable Losses Rafael Frongillo, Andrew Nobel

Mixing Implies Lower Bounds for Space Bounded Learning Dana Moshkovitz, Michal Moshkovitz

Multi-Observation Elicitation Sebastian Casalaina-Martin, Rafael Frongillo, Tom Morgan, Bo Waggoner

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, Ruosong Wang

Nearly-Tight VC-Dimension Bounds for Piecewise Linear Neural Networks Nick Harvey, Christopher Liaw, Abbas Mehrabian

Noisy Population Recovery from Unknown Noise Shachar Lovett, Jiapeng Zhang

Non-Convex Learning via Stochastic Gradient Langevin Dynamics: A Nonasymptotic Analysis Maxim Raginsky, Alexander Rakhlin, Matus Telgarsky

On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities Alexander Rakhlin, Karthik Sridharan

On Learning vs. Refutation Salil Vadhan

On the Ability of Neural Nets to Express Distributions Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski, Sanjeev Arora

Online Learning Without Prior Information Ashok Cutkosky, Kwabena Boahen

Open Problem: First-Order Regret Bounds for Contextual Bandits Alekh Agarwal, Akshay Krishnamurthy, John Langford, Haipeng Luo, Robert E. Schapire

Open Problem: Meeting Times for Learning Random Automata Benjamin Fish, Lev Reyzin

Optimal Learning via Local Entropies and Sample Compression Zhivotovskiy Nikita

Predicting with Distributions Michael Kearns, Zhiwei Steven Wu

Preface: Conference on Learning Theory (COLT), 2017 Satyen Kale, Ohad Shamir

Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes Lunjia Hu, Ruihan Wu, Tianhong Li, Liwei Wang

Rates of Estimation for Determinantal Point Processes Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet, John Urschel

Reliably Learning the ReLU in Polynomial Time Surbhi Goel, Varun Kanade, Adam Klivans, Justin Thaler

Robust and Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities Jerry Li, Ludwig Schmidt

Sample Complexity of Population Recovery Yury Polyanskiy, Ananda Theertha Suresh, Yihong Wu

Sampling from a Log-Concave Distribution with Compact Support with Proximal Langevin Monte Carlo Nicolas Brosse, Alain Durmus, Éric Moulines, Marcelo Pereyra

Solving SDPs for Synchronization and MaxCut Problems via the Grothendieck Inequality Song Mei, Theodor Misiakiewicz, Andrea Montanari, Roberto Imbuzeiro Oliveira

Sparse Stochastic Bandits Joon Kwon, Vianney Perchet, Claire Vernade

Square Hellinger Subadditivity for Bayesian Networks and Its Applications to Identity Testing Constantinos Daskalakis, Qinxuan Pan

Stochastic Composite Least-Squares Regression with Convergence Rate $O(1/n)$ Nicolas Flammarion, Francis Bach

Submodular Optimization Under Noise Avinatan Hassidim, Yaron Singer

Surprising Properties of Dropout in Deep Networks David P. Helmbold, Philip M. Long

Ten Steps of EM Suffice for Mixtures of Two Gaussians Constantinos Daskalakis, Christos Tzamos, Manolis Zampetakis

Testing Bayesian Networks Clement L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

The Hidden Hubs Problem Ravindran Kannan, Santosh Vempala

The Price of Selection in Differential Privacy Mitali Bafna, Jonathan Ullman

The Sample Complexity of Optimizing a Convex Function Eric Balkanski, Yaron Singer

The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime Max Simchowitz, Kevin Jamieson, Benjamin Recht

Thompson Sampling for the MNL-Bandit Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, Assaf Zeevi

Thresholding Based Outlier Robust PCA Yeshwanth Cherapanamjeri, Prateek Jain, Praneeth Netrapalli

Tight Bounds for Bandit Combinatorial Optimization Alon Cohen, Tamir Hazan, Tomer Koren

Towards Instance Optimal Bounds for Best Arm Identification Lijie Chen, Jian Li, Mingda Qiao

Two-Sample Tests for Large Random Graphs Using Network Statistics Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, Ulrike Luxburg

ZigZag: A New Approach to Adaptive Online Learning Dylan J. Foster, Alexander Rakhlin, Karthik Sridharan