Papers
Complexity Theoretic Limitations on Learning DNF’s
Amit Daniely, Shai Shalev-Shwartz
Adaptive Learning with Robust Generalization Guarantees
Rachel Cummings, Katrina Ligett, Kobbi Nissim et al.
A Light Touch for Heavily Constrained SGD
Andrew Cotter, Maya Gupta, Jan Pfeifer
On the Expressive Power of Deep Learning: A Tensor Analysis
Nadav Cohen, Or Sharir, Amnon Shashua
Provably manipulation-resistant reputation systems
Paul Christiano
Pure Exploration of Multi-armed Bandit Under Matroid Constraints
Lijie Chen, Anupam Gupta, Jian Li
On the Approximability of Sparse PCA
Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein
Delay and Cooperation in Nonstochastic Bandits
Nicol‘o Cesa-Bianchi, Claudio Gentile, Yishay Mansour et al.
Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
Alexandra Carpentier, Andrea Locatelli
Multi-scale exploration of convex functions and bandit convex optimization
Sébastien Bubeck, Ronen Eldan
Dropping Convexity for Faster Semi-definite Optimization
Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi
Aggregation of supports along the Lasso path
Pierre C. Bellec
Basis Learning as an Algorithmic Primitive
Mikhail Belkin, Luis Rademacher, James Voss
Noisy Tensor Completion via the Sum-of-Squares Hierarchy
Boaz Barak, Ankur Moitra
Information-theoretic thresholds for community detection in sparse networks
Jess Banks, Cristopher Moore, Joe Neeman et al.
On the low-rank approach for semidefinite programs arising in synchronization and community detection
Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski
Instance-dependent Regret Bounds for Dueling Bandits
Akshay Balsubramani, Zohar Karnin, Robert E. Schapire et al.
Learning Combinatorial Functions from Pairwise Comparisons
Maria-Florina Balcan, Ellen Vitercik, Colin White
An Improved Gap-Dependency Analysis of the Noisy Power Method
Maria-Florina Balcan, Simon Shaolei Du, Yining Wang et al.
Highly-Smooth Zero-th Order Online Optimization
Francis Bach, Vianney Perchet
Reinforcement Learning of POMDPs using Spectral Methods
Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar
Learning and 1-bit Compressed Sensing under Asymmetric Noise
Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab et al.
Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models
Bernardo Ávila Pires, Csaba Szepesvári
An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits
Peter Auer, Chao-Kai Chiang
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes
Nima Anari, Shayan Oveis Gharan, Alireza Rezaei