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