COLT 2016: THE 29TH ANNUAL CONFERENCE ON LEARNING THEORY

A
Agarwal, Shivani	When Can We Rank Well from Comparisons of $O(n\log n)$ Non-Actively Chosen Pairs?
Agrawal, Shipra	An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
Aliakbarpour, Maryam	Learning and Testing Junta Distributions
Alon, Noga	Sign rank versus VC dimension
Anandkumar, Animashree	Reinforcement Learning of POMDPs using Spectral Methods Efficient approaches for escaping higher order saddle points in non-convex optimization
Anari, Nima	Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes
Auer, Peter	An algorithm with nearly optimal pseudo-regret \\for both stochastic and adversarial bandits
Avila Pires, Bernardo	Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models
Awasthi, Pranjal	Efficient algorithms for learning and 1-bit compressed sensing under asymmetric noise
Azizzadenesheli, Kamyar	Reinforcement Learning of POMDPs using Spectral Methods
B
Bach, Francis	Highly-Smooth Zero-th Order Online Optimization
Balcan, Maria-Florina	An Improved Gap-Dependency Analysis of the Noisy Power Method Learning Combinatorial Functions from Pairwise Comparisons Efficient algorithms for learning and 1-bit compressed sensing under asymmetric noise
Balsubramani, Akshay	Instance-dependent Regret Bounds for Dueling Bandits
Bandeira, Afonso S.	On the low-rank approach for semidefinite programs arising in synchronization and community detection
Banks, Jess	Information-theoretic thresholds for community detection in sparse networks
Barak, Boaz	Noisy Tensor Completion via the Sum-of-Squares Hierarchy
Belkin, Mikhail	Basis Learning as an Algorithmic Primitive
Bellec, Pierre C.	Aggregation of supports along the Lasso path
Bhojanapalli, Srinadh	Dropping Convexity for Faster Semi-definite Optimization
Blais, Eric	Learning and Testing Junta Distributions
Boumal, Nicolas	On the low-rank approach for semidefinite programs arising in synchronization and community detection
Bubeck, Sébastien	Multi-scale exploration of convex functions and bandit convex optimization (Best Paper Award)
C
Carpentier, Alexandra	Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
Cesa-Bianchi, Nicolo'	Delay and Cooperation in Nonstochastic Bandits
Chan, Siu On	On the Approximability of Sparse PCA
Chaudhuri, Kamalika	The Extended Littlestone’s Dimension for Learning with Mistakes and Abstentions
Chen, Lijie	Pure Exploration of Multi-armed Bandit Under Matroid Constraints
Cheng, Xiang	Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning
Chiang, Chao-Kai	An algorithm with nearly optimal pseudo-regret \\for both stochastic and adversarial bandits
Christiano, Paul	Provably manipulation-resistant reputation systems (Best Student Paper Award)
Cohen, Nadav	On the Expressive Power of Deep Learning: A Tensor Analysis
Cotter, Andrew	A Light Touch for Heavily Constrained SGD
Cummings, Rachel	Adaptive Learning with Robust Generalization Guarantees
D
Daniely, Amit	Complexity theoretic limitations on learning DNF's
Devanur, Nikhil R.	An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
Diakonikolas, Ilias	Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
Du, Simon	An Improved Gap-Dependency Analysis of the Noisy Power Method
E
El Alaoui, Ahmed	Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning
Eldan, Ronen	Multi-scale exploration of convex functions and bandit convex optimization (Best Paper Award)
Eldan, Ronen	The Power of Depth for Feedforward Neural Networks
F
Flesch, Janos	Online Learning and Blackwell Approachability in Quitting Games
Florescu, Laura	Spectral thresholds in the bipartite stochastic block model
Foster, Dean	Online Sparse Linear Regression
G
Gao, Ziyuan	Preference-based Teaching
Garivier, Aurélien	Optimal Best Arm Identification with Fixed Confidence Maximin Action Identification: A New Bandit Framework for Games
Ge, Rong	Efficient approaches for escaping higher order saddle points in non-convex optimization
Gentile, Claudio	Delay and Cooperation in Nonstochastic Bandits
Gupta, Anupam	Pure Exploration of Multi-armed Bandit Under Matroid Constraints
Gupta, Maya	A Light Touch for Heavily Constrained SGD
H
Haghtalab, Nika	Efficient algorithms for learning and 1-bit compressed sensing under asymmetric noise
Hajek, Bruce	Semidefinite Programs for Exact Recovery of a Hidden Community
Hazan, Elad	Online Learning with Low Rank Experts
Hess, Tom	Interactive Algorithms: from Pool to Stream
Hütter, Jan-Christian	Optimal rates for total variation denoising
J
Jain, Prateek	Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm
Jamieson, Kevin	Best-of-K Bandits
Jin, Chi	Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm
Jordan, Michael	Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning Gradient Descent only Converges to Minimizers
K
Kakade, Sham	Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm
Kale, Satyen	Online Sparse Linear Regression
Kane, Daniel	Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
Karloff, Howard	Online Sparse Linear Regression
Karnin, Zohar	Instance-dependent Regret Bounds for Dueling Bandits
Kaufmann, Emilie	Optimal Best Arm Identification with Fixed Confidence Maximin Action Identification: A New Bandit Framework for Games
Koolen, Wouter M.	Online Isotonic Regression Maximin Action Identification: A New Bandit Framework for Games
Koren, Tomer	Online Learning with Low Rank Experts
Kotlowski, Wojciech	Online Isotonic Regression
Kuznetsov, Vitaly	Time Series Prediction and Online Learning
Kyrillidis, Anastasios	Dropping Convexity for Faster Semi-definite Optimization
L
Laraki, Rida	Online Learning and Blackwell Approachability in Quitting Games
Lattimore, Tor	Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
Lazaric, Alessandro	Reinforcement Learning of POMDPs using Spectral Methods
Lee, Jason	Gradient Descent only Converges to Minimizers
Li, Jian	Pure Exploration of Multi-armed Bandit Under Matroid Constraints
Li, Lihong	An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
Ligett, Katrina	Adaptive Learning with Robust Generalization Guarantees
Livni, Roi	Online Learning with Low Rank Experts
Locatelli, Andrea	Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
M
Makarychev, Konstantin	Learning Communities in the Presence of Errors
Makarychev, Yury	Learning Communities in the Presence of Errors
Malek, Alan	Online Isotonic Regression
Mansour, Yishay	Online Learning with Low Rank Experts Delay and Cooperation in Nonstochastic Bandits
Massoulie, Laurent	On the capacity of information processing systems
Minora, Alberto	Delay and Cooperation in Nonstochastic Bandits
Mohri, Mehryar	Time Series Prediction and Online Learning
Moitra, Ankur	Noisy Tensor Completion via the Sum-of-Squares Hierarchy
Moore, Cristopher	Information-theoretic thresholds for community detection in sparse networks
Moran, Shay	Sign rank versus VC dimension
Morgenstern, Jamie	Learning Simple Auctions
Mossel, Elchanan	Density Evolution in the Degree-correlated Stochastic Block Model
N
Neeman, Joe	Information-theoretic thresholds for community detection in sparse networks
Netrapalli, Praneeth	Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm Information-theoretic thresholds for community detection in sparse networks
Nissim, Kobbi	Adaptive Learning with Robust Generalization Guarantees
O
Oveis Gharan, Shayan	Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes
P
Papadimitriou, Christos	Cortical Computation via Iterative Constructions
Papailliopoulos, Dimitris	On the Approximability of Sparse PCA
Perchet, Vianney	Online Learning and Blackwell Approachability in Quitting Games Online learning in repeated auctions Highly-Smooth Zero-th Order Online Optimization
Perkins, Will	Spectral thresholds in the bipartite stochastic block model
Petti, Samantha	Cortical Computation via Iterative Constructions
Pfeifer, Jan	A Light Touch for Heavily Constrained SGD
R
Rademacher, Luis	Basis Learning as an Algorithmic Primitive
Rajkumar, Arun	When Can We Rank Well from Comparisons of $O(n\log n)$ Non-Actively Chosen Pairs?
Ramdas, Aaditya	Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning
Recht, Ben	Best-of-K Bandits Gradient Descent only Converges to Minimizers
Rezaei, Alireza	Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes
Ries, Christoph	Preference-based Teaching
Rigollet, Philippe	Online learning in repeated auctions Optimal rates for total variation denoising
Risteski, Andrej	How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
Roth, Aaron	Adaptive Learning with Robust Generalization Guarantees
Roughgarden, Tim	Learning Simple Auctions
Rubinfeld, Ronitt	Learning and Testing Junta Distributions
Rubinstein, Aviad	On the Approximability of Sparse PCA
Russo, Daniel	Simple Bayesian Algorithms for Best Arm Identification
S
Sabato, Sivan	Interactive Algorithms: from Pool to Stream
Sanghavi, Sujay	Dropping Convexity for Faster Semi-definite Optimization
Schapire, Robert	Instance-dependent Regret Bounds for Dueling Bandits
Shalev-Shwartz, Shai	Complexity theoretic limitations on learning DNF's
Shamir, Ohad	The Power of Depth for Feedforward Neural Networks
Sharir, Or	On the Expressive Power of Deep Learning: A Tensor Analysis
Shashua, Amnon	On the Expressive Power of Deep Learning: A Tensor Analysis
Sidford, Aaron	Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm
Simchowitz, Max	Best-of-K Bandits Gradient Descent only Converges to Minimizers
Simon, Hans	Preference-based Teaching
Sra, Suvrit	First-order Methods for Geodesically Convex Optimization
Steinhardt, Jacob	Memory, Communication, and Statistical Queries
Stewart, Alistair	Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
Szepesvari, Csaba	Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models
T
Telgarsky, Matus	Benefits of depth in neural networks
V
Valiant, Gregory	Memory, Communication, and Statistical Queries
Vempala, Santosh	Cortical Computation via Iterative Constructions
Vijayaraghavan, Aravindan	Learning Communities in the Presence of Errors
Vitercik, Ellen	Learning Combinatorial Functions from Pairwise Comparisons
Volkovich, Ilya	A Guide to Learning Arithmetic Circuits
Voroninski, Vladislav	On the low-rank approach for semidefinite programs arising in synchronization and community detection
Voss, James	Basis Learning as an Algorithmic Primitive
W
Wager, Stefan	Memory, Communication, and Statistical Queries
Wainwright, Martin	Asymptotic behavior of $\ell_q$-based Laplacian regularization in semi-supervised learning
Wang, Yining	An Improved Gap-Dependency Analysis of the Noisy Power Method
Weed, Jonathan	Online learning in repeated auctions
White, Colin	Learning Combinatorial Functions from Pairwise Comparisons
Wu, Yihong	Semidefinite Programs for Exact Recovery of a Hidden Community
Wu, Zhiwei Steven	Adaptive Learning with Robust Generalization Guarantees
X
Xu, Jiaming	Density Evolution in the Degree-correlated Stochastic Block Model Semidefinite Programs for Exact Recovery of a Hidden Community
Xu, Kuang	On the capacity of information processing systems
Y
Yehudayoff, Amir	Sign rank versus VC dimension
Yu, Adams Wei	An Improved Gap-Dependency Analysis of the Noisy Power Method
Z
Zhang, Chicheng	The Extended Littlestone’s Dimension for Learning with Mistakes and Abstentions
Zhang, Hongyang	Efficient algorithms for learning and 1-bit compressed sensing under asymmetric noise
Zhang, Hongyi	First-order Methods for Geodesically Convex Optimization
Zilles, Sandra	Preference-based Teaching
Zoghi, Masrour	Instance-dependent Regret Bounds for Dueling Bandits

Disclaimer | Powered by EasyChair Smart Program