| 2016 | Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables. | Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart |
| 2016 | Complexity Theoretic Limitations on Learning DNF's. | Amit Daniely, Shai Shalev-Shwartz |
| 2016 | Adaptive Learning with Robust Generalization Guarantees. | Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, Zhiwei Steven Wu |
| 2016 | A Light Touch for Heavily Constrained SGD. | Andrew Cotter, Maya R. Gupta, Jan Pfeifer |
| 2016 | On the Expressive Power of Deep Learning: A Tensor Analysis. | Nadav Cohen, Or Sharir, Amnon Shashua |
| 2016 | Provably manipulation-resistant reputation systems. | Paul F. Christiano |
| 2016 | Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture. | Lijie Chen, Jian Li |
| 2016 | Pure Exploration of Multi-armed Bandit Under Matroid Constraints. | Lijie Chen, Anupam Gupta, Jian Li |
| 2016 | On the Approximability of Sparse PCA. | Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein |
| 2016 | Delay and Cooperation in Nonstochastic Bandits. | Nicol Cesa-Bianchi, Claudio Gentile, Yishay Mansour, Alberto Minora |
| 2016 | Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem. | Alexandra Carpentier, Andrea Locatelli |
| 2016 | Multi-scale exploration of convex functions and bandit convex optimization. | Sbastien Bubeck, Ronen Eldan |
| 2016 | Dropping Convexity for Faster Semi-definite Optimization. | Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi |
| 2016 | Aggregation of supports along the Lasso path. | Pierre C. Bellec |
| 2016 | Basis Learning as an Algorithmic Primitive. | Mikhail Belkin, Luis Rademacher, James R. Voss |
| 2016 | Noisy Tensor Completion via the Sum-of-Squares Hierarchy. | Boaz Barak, Ankur Moitra |
| 2016 | Information-theoretic thresholds for community detection in sparse networks. | Jess Banks, Cristopher Moore, Joe Neeman, Praneeth Netrapalli |
| 2016 | On the low-rank approach for semidefinite programs arising in synchronization and community detection. | Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski |
| 2016 | Instance-dependent Regret Bounds for Dueling Bandits. | Akshay Balsubramani, Zohar S. Karnin, Robert E. Schapire, Masrour Zoghi |
| 2016 | Learning Combinatorial Functions from Pairwise Comparisons. | Maria-Florina Balcan, Ellen Vitercik, Colin White |
| 2016 | An Improved Gap-Dependency Analysis of the Noisy Power Method. | Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, Adams Wei Yu |
| 2016 | Highly-Smooth Zero-th Order Online Optimization. | Francis R. Bach, Vianney Perchet |
| 2016 | Open Problem: Approximate Planning of POMDPs in the class of Memoryless Policies. | Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar |
| 2016 | Reinforcement Learning of POMDPs using Spectral Methods. | Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar |
| 2016 | Learning and 1-bit Compressed Sensing under Asymmetric Noise. | Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Hongyang Zhang |