COLT 2017

76 papers

Optimal learning via local entropies and sample compression

Zhivotovskiy Nikita

A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics

Yuchen Zhang, Percy Liang, Moses Charikar

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

Learning Non-Discriminatory Predictors

Blake Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian, Nathan Srebro

Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox

Jialei Wang, Weiran Wang, Nathan Srebro

Ignoring Is a Bliss: Learning with Large Noise Through Reweighting-Minimization

Daniel Vainsencher, Shie Mannor, Huan Xu

On Learning vs. Refutation

Salil Vadhan

The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime

Max Simchowitz, Kevin Jamieson, Benjamin Recht

Fast and robust tensor decomposition with applications to dictionary learning

Tselil Schramm, David Steurer

An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits

Yevgeny Seldin, Gabor Lugosi

Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

Jonathan Scarlett, Ilija Bogunovic, Volkan Cevher

On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities

Alexander Rakhlin, Karthik Sridharan

Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis

Maxim Raginsky, Alexander Rakhlin, Matus Telgarsky

Exact tensor completion with sum-of-squares

Aaron Potechin, David Steurer

Sample complexity of population recovery

Yury Polyanskiy, Ananda Theertha Suresh, Yihong Wu

Fast rates for online learning in Linearly Solvable Markov Decision Processes

Gergely Neu, Vicenç Gómez

Mixing Implies Lower Bounds for Space Bounded Learning

Dana Moshkovitz, Michal Moshkovitz

Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality

Song Mei, Theodor Misiakiewicz, Andrea Montanari, Roberto Imbuzeiro Oliveira

A Second-order Look at Stability and Generalization

Andreas Maurer

Inapproximability of VC Dimension and Littlestone’s Dimension

Pasin Manurangsi, Aviad Rubinstein

Noisy Population Recovery from Unknown Noise

Shachar Lovett, Jiapeng Zhang

Adaptivity to Noise Parameters in Nonparametric Active Learning

Carpentier Alexandra Locatelli Andrea, Kpotufe Samory

Robust and Proper Learning for Mixtures of Gaussians via Systems of Polynomial Inequalities

Jerry Li, Ludwig Schmidt

Fundamental limits of symmetric low-rank matrix estimation

marc lelarge, Léo Miolane

On the Ability of Neural Nets to Express Distributions

Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski, Sanjeev Arora

Sparse Stochastic Bandits

Joon Kwon, Vianney Perchet, Claire Vernade

Bandits with Movement Costs and Adaptive Pricing

Tomer Koren, Roi Livni, Yishay Mansour

Predicting with Distributions

Michael Kearns, Zhiwei Steven Wu

The Hidden Hubs Problem

Ravindran Kannan, Santosh Vempala

A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints

Bin Hu, Peter Seiler, Anders Rantzer

Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes

Lunjia Hu, Ruihan Wu, Tianhong Li, Liwei Wang

Surprising properties of dropout in deep networks

David P. Helmbold, Philip M. Long

Submodular Optimization under Noise

Avinatan Hassidim, Yaron Singer

Nearly-tight VC-dimension bounds for piecewise linear neural networks

Nick Harvey, Christopher Liaw, Abbas Mehrabian

Fast Rates for Empirical Risk Minimization of Strict Saddle Problems

Alon Gonen, Shai Shalev-shwartz

Reliably Learning the ReLU in Polynomial Time

Surbhi Goel, Varun Kanade, Adam Klivans, Justin Thaler

Effective Semisupervised Learning on Manifolds

Amir Globerson, Roi Livni, Shai Shalev-shwartz

Two-Sample Tests for Large Random Graphs Using Network Statistics

Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, Ulrike Von Luxburg

High Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transtition

Gamarnik David, Zadik Ilias

Matrix Completion from $O(n)$ Samples in Linear Time

David Gamarnik, Quan Li, Hongyi Zhang

Memoryless Sequences for Differentiable Losses

Rafael Frongillo, Andrew Nobel

ZigZag: A New Approach to Adaptive Online Learning

Dylan J. Foster, Alexander Rakhlin, Karthik Sridharan

Stochastic Composite Least-Squares Regression with Convergence Rate $O(1/n)$

Nicolas Flammarion, Francis Bach

A General Characterization of the Statistical Query Complexity

Vitaly Feldman

Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization

Moran Feldman, Christopher Harshaw, Amin Karbasi

Generalization for Adaptively-chosen Estimators via Stable Median

Vitaly Feldman, Thomas Steinke

Learning Multivariate Log-concave Distributions

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

Ten Steps of EM Suffice for Mixtures of Two Gaussians

Constantinos Daskalakis, Christos Tzamos, Manolis Zampetakis

Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing

Constantinos Daskalakis, Qinxuan Pan

Depth Separation for Neural Networks

Amit Daniely

Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent

Arnak Dalalyan

Online Learning Without Prior Information

Ashok Cutkosky, Kwabena Boahen

Tight Bounds for Bandit Combinatorial Optimization

Alon Cohen, Tamir Hazan, Tomer Koren

Thresholding Based Outlier Robust PCA

Yeshwanth Cherapanamjeri, Prateek Jain, Praneeth Netrapalli

Towards Instance Optimal Bounds for Best Arm Identification

Lijie Chen, Jian Li, Mingda Qiao

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration

Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, Ruosong Wang

Algorithmic Chaining and the Role of Partial Feedback in Online Nonparametric Learning

Nicolò Cesa-bianchi, Pierre Gaillard, Claudio Gentile, Sébastien Gerchinovitz

Multi-Observation Elicitation

Sebastian Casalaina-Martin, Rafael Frongillo, Tom Morgan, Bo Waggoner

Testing Bayesian Networks

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

Learning Disjunctions of Predicates

Nader H. Bshouty, Dana Drachsler-Cohen, Martin Vechev, Eran Yahav

Rates of estimation for determinantal point processes

Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet, John Urschel

Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo

Nicolas Brosse, Alain Durmus, Eric Moulines, Marcelo Pereyra

Efficient Co-Training of Linear Separators under Weak Dependence

Avrim Blum, Yishay Mansour

The Sample Complexity of Optimizing a Convex Function

Eric Balkanski, Yaron Singer

Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems

Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, Colin White

Computationally Efficient Robust Sparse Estimation in High Dimensions

Sivaraman Balakrishnan, Simon S. Du, Jerry Li, Aarti Singh

The Price of Selection in Differential Privacy

Mitali Bafna, Jonathan Ullman

Efficient PAC Learning from the Crowd

Pranjal Awasthi, Avrim Blum, Nika Haghtalab, Yishay Mansour

Correspondence retrieval

Alexandr Andoni, Daniel Hsu, Kevin Shi, Xiaorui Sun

Homotopy Analysis for Tensor PCA

Anima Anandkumar, Yuan Deng, Rong Ge, Hossein Mobahi

Thompson Sampling for the MNL-Bandit

Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, Assaf Zeevi

Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons

Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, Sanjeev Khanna

Corralling a Band of Bandit Algorithms

Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, Robert E. Schapire

Open Problem: Meeting Times for Learning Random Automata

Benjamin Fish, Lev Reyzin

Open Problem: First-Order Regret Bounds for Contextual Bandits

Alekh Agarwal, Akshay Krishnamurthy, John Langford, Haipeng Luo, Schapire Robert E.

Preface: Conference on Learning Theory (COLT), 2017

Satyen Kale, Ohad Shamir