| 2015 | Competing with the Empirical Risk Minimizer in a Single Pass. | Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford |
| 2015 | Vector-Valued Property Elicitation. | Rafael M. Frongillo, Ian A. Kash |
| 2015 | Variable Selection is Hard. | Dean P. Foster, Howard J. Karloff, Justin Thaler |
| 2015 | From Averaging to Acceleration, There is Only a Step-size. | Nicolas Flammarion, Francis R. Bach |
| 2015 | Learning and inference in the presence of corrupted inputs. | Uriel Feige, Yishay Mansour, Robert E. Schapire |
| 2015 | Faster Algorithms for Testing under Conditional Sampling. | Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, Ananda Theertha Suresh |
| 2015 | Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering. | Justin Eldridge, Mikhail Belkin, Yusu Wang |
| 2015 | Contextual Dueling Bandits. | Miroslav Dudk, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, Masrour Zoghi |
| 2015 | Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems. | Yash Deshpande, Andrea Montanari |
| 2015 | S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification. | Gautam Dasarathy, Robert D. Nowak, Xiaojin Zhu |
| 2015 | A PTAS for Agnostically Learning Halfspaces. | Amit Daniely |
| 2015 | Truthful Linear Regression. | Rachel Cummings, Stratis Ioannidis, Katrina Ligett |
| 2015 | On-Line Learning Algorithms for Path Experts with Non-Additive Losses. | Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Manfred K. Warmuth |
| 2015 | Open Problem: The landscape of the loss surfaces of multilayer networks. | Anna Choromanska, Yann LeCun, Grard Ben Arous |
| 2015 | Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery. | Peter Chin, Anup Rao, Van Vu |
| 2015 | Learnability of Solutions to Conjunctive Queries: The Full Dichotomy. | Hubie Chen, Matthew Valeriote |
| 2015 | Sequential Information Maximization: When is Greedy Near-optimal? | Yuxin Chen, S. Hamed Hassani, Amin Karbasi, Andreas Krause |
| 2015 | Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification. | Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng |
| 2015 | On the Complexity of Learning with Kernels. | Nicol Cesa-Bianchi, Yishay Mansour, Ohad Shamir |
| 2015 | Optimum Statistical Estimation with Strategic Data Sources. | Yang Cai, Constantinos Daskalakis, Christos H. Papadimitriou |
| 2015 | The entropic barrier: a simple and optimal universal self-concordant barrier. | Sbastien Bubeck, Ronen Eldan |
| 2015 | Bandit Convex Optimization: \(\sqrt{T}\) Regret in One Dimension. | Sbastien Bubeck, Ofer Dekel, Tomer Koren, Yuval Peres |
| 2015 | Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions. | Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, Alexander Rakhlin |
| 2015 | Minimax Fixed-Design Linear Regression. | Peter L. Bartlett, Wouter M. Koolen, Alan Malek, Eiji Takimoto, Manfred K. Warmuth |
| 2015 | Open Problem: Restricted Eigenvalue Condition for Heavy Tailed Designs. | Arindam Banerjee, Sheng Chen, Vidyashankar Sivakumar |