| 2018 | $\ell_1$ Regression using Lewis Weights Preconditioning and Stochastic Gradient Descent. David Durfee, Kevin A. Lai, Saurabh Sawlani |
| 2018 | A Data Prism: Semi-verified learning in the small-alpha regime. Michela Meister, Gregory Valiant |
| 2018 | A Direct Sum Result for the Information Complexity of Learning. Ido Nachum, Jonathan Shafer, Amir Yehudayoff |
| 2018 | A Faster Approximation Algorithm for the Gibbs Partition Function. Vladimir Kolmogorov |
| 2018 | A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation. Jalaj Bhandari, Daniel Russo, Raghav Singal |
| 2018 | A General Approach to Multi-Armed Bandits Under Risk Criteria. Asaf B. Cassel, Shie Mannor, Assaf Zeevi |
| 2018 | Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent. Chi Jin, Praneeth Netrapalli, Michael I. Jordan |
| 2018 | Accelerating Stochastic Gradient Descent for Least Squares Regression. Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford |
| 2018 | Action-Constrained Markov Decision Processes With Kullback-Leibler Cost. Ana Busic, Sean P. Meyn |
| 2018 | Active Tolerant Testing. Avrim Blum, Lunjia Hu |
| 2018 | Actively Avoiding Nonsense in Generative Models. Steve Hanneke, Adam Tauman Kalai, Gautam Kamath, Christos Tzamos |
| 2018 | Adaptivity to Smoothness in X-armed bandits. Andrea Locatelli, Alexandra Carpentier |
| 2018 | Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations. Yuanzhi Li, Tengyu Ma, Hongyang Zhang |
| 2018 | An Analysis of the t-SNE Algorithm for Data Visualization. Sanjeev Arora, Wei Hu, Pravesh K. Kothari |
| 2018 | An Estimate Sequence for Geodesically Convex Optimization. Hongyi Zhang, Suvrit Sra |
| 2018 | An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization. Tim Roughgarden, Joshua R. Wang |
| 2018 | An explicit analysis of the entropic penalty in linear programming. Jonathan Weed |
| 2018 | Approximate Nearest Neighbors in Limited Space. Piotr Indyk, Tal Wagner |
| 2018 | Approximation beats concentration? An approximation view on inference with smooth radial kernels. Mikhail Belkin |
| 2018 | Averaging Stochastic Gradient Descent on Riemannian Manifolds. Nilesh Tripuraneni, Nicolas Flammarion, Francis R. Bach, Michael I. Jordan |
| 2018 | Best of both worlds: Stochastic & adversarial best-arm identification. Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon, Alan Malek, Michal Valko |
| 2018 | Black-Box Reductions for Parameter-free Online Learning in Banach Spaces. Ashok Cutkosky, Francesco Orabona |
| 2018 | Breaking the $1/\sqrtn$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time. Cheng Mao, Ashwin Pananjady, Martin J. Wainwright |
| 2018 | Calibrating Noise to Variance in Adaptive Data Analysis. Vitaly Feldman, Thomas Steinke |
| 2018 | Certified Computation from Unreliable Datasets. Themis Gouleakis, Christos Tzamos, Manolis Zampetakis |
| 2018 | Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018. Sébastien Bubeck, Vianney Perchet, Philippe Rigollet |
| 2018 | Conference on Learning Theory 2018: Preface. Sébastien Bubeck, Philippe Rigollet |
| 2018 | Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing. Oren Mangoubi, Nisheeth K. Vishnoi |
| 2018 | Counting Motifs with Graph Sampling. Jason M. Klusowski, Yihong Wu |
| 2018 | Cutting plane methods can be extended into nonconvex optimization. Oliver Hinder |
| 2018 | Detecting Correlations with Little Memory and Communication. Yuval Dagan, Ohad Shamir |
| 2018 | Detection limits in the high-dimensional spiked rectangular model. Ahmed El Alaoui, Michael I. Jordan |
| 2018 | Efficient Algorithms for Outlier-Robust Regression. Adam R. Klivans, Pravesh K. Kothari, Raghu Meka |
| 2018 | Efficient Contextual Bandits in Non-stationary Worlds. Haipeng Luo, Chen-Yu Wei, Alekh Agarwal, John Langford |
| 2018 | Efficient Convex Optimization with Membership Oracles. Yin Tat Lee, Aaron Sidford, Santosh S. Vempala |
| 2018 | Efficient active learning of sparse halfspaces. Chicheng Zhang |
| 2018 | Empirical bounds for functions with weak interactions. Andreas Maurer, Massimiliano Pontil |
| 2018 | Exact and Robust Conformal Inference Methods for Predictive Machine Learning with Dependent Data. Victor Chernozhukov, Kaspar Wüthrich, Yinchu Zhu |
| 2018 | Exponential Convergence of Testing Error for Stochastic Gradient Methods. Loucas Pillaud-Vivien, Alessandro Rudi, Francis R. Bach |
| 2018 | Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms. Ilias Diakonikolas, Jerry Li, Ludwig Schmidt |
| 2018 | Faster Rates for Convex-Concave Games. Jacob D. Abernethy, Kevin A. Lai, Kfir Y. Levy, Jun-Kun Wang |
| 2018 | Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning. Gal Dalal, Gugan Thoppe, Balázs Szörényi, Shie Mannor |
| 2018 | Fitting a Putative Manifold to Noisy Data. Charles Fefferman, Sergei Ivanov, Yaroslav Kurylev, Matti Lassas, Hariharan Narayanan |
| 2018 | Fundamental Limits of Weak Recovery with Applications to Phase Retrieval. Marco Mondelli, Andrea Montanari |
| 2018 | Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints. Wenlong Mou, Liwei Wang, Xiyu Zhai, Kai Zheng |
| 2018 | Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints. Yanjun Han, Ayfer Özgür, Tsachy Weissman |
| 2018 | Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk. Paul Hand, Vladislav Voroninski |
| 2018 | Hardness of Learning Noisy Halfspaces using Polynomial Thresholds. Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket |
| 2018 | Hidden Integrality of SDP Relaxations for Sub-Gaussian Mixture Models. Yingjie Fei, Yudong Chen |
| 2018 | Incentivizing Exploration by Heterogeneous Users. Bangrui Chen, Peter I. Frazier, David Kempe |
| 2018 | Information Directed Sampling and Bandits with Heteroscedastic Noise. Johannes Kirschner, Andreas Krause |
| 2018 | Iterate Averaging as Regularization for Stochastic Gradient Descent. Gergely Neu, Lorenzo Rosasco |
| 2018 | Langevin Monte Carlo and JKO splitting. Espen Bernton |
| 2018 | Learning Mixtures of Linear Regressions with Nearly Optimal Complexity. Yuanzhi Li, Yingyu Liang |
| 2018 | Learning Patterns for Detection with Multiscale Scan Statistics. James Sharpnack |
| 2018 | Learning Single-Index Models in Gaussian Space. Rishabh Dudeja, Daniel Hsu |
| 2018 | Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification. Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, Benjamin Recht |
| 2018 | Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability. Belinda Tzen, Tengyuan Liang, Maxim Raginsky |
| 2018 | Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance. Yanjun Han, Jiantao Jiao, Tsachy Weissman |
| 2018 | Log-concave sampling: Metropolis-Hastings algorithms are fast! Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, Bin Yu |
| 2018 | Logistic Regression: The Importance of Being Improper. Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, Karthik Sridharan |
| 2018 | Lower Bounds for Higher-Order Convex Optimization. Naman Agarwal, Elad Hazan |
| 2018 | Marginal Singularity, and the Benefits of Labels in Covariate-Shift. Samory Kpotufe, Guillaume Martinet |
| 2018 | Minimax Bounds on Stochastic Batched Convex Optimization. John C. Duchi, Feng Ruan, Chulhee Yun |
| 2018 | More Adaptive Algorithms for Adversarial Bandits. Chen-Yu Wei, Haipeng Luo |
| 2018 | Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities. Timothy Carpenter, Ilias Diakonikolas, Anastasios Sidiropoulos, Alistair Stewart |
| 2018 | Non-Convex Matrix Completion Against a Semi-Random Adversary. Yu Cheng, Rong Ge |
| 2018 | Nonstochastic Bandits with Composite Anonymous Feedback. Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour |
| 2018 | Online Learning: Sufficient Statistics and the Burkholder Method. Dylan J. Foster, Alexander Rakhlin, Karthik Sridharan |
| 2018 | Online Variance Reduction for Stochastic Optimization. Zalan Borsos, Andreas Krause, Kfir Y. Levy |
| 2018 | Online learning over a finite action set with limited switching. Jason M. Altschuler, Kunal Talwar |
| 2018 | Open Problem: The Dependence of Sample Complexity Lower Bounds on Planning Horizon. Nan Jiang, Alekh Agarwal |
| 2018 | Open problem: Improper learning of mixtures of Gaussians. Elad Hazan, Roi Livni |
| 2018 | Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models. Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, Lenka Zdeborová |
| 2018 | Optimal Single Sample Tests for Structured versus Unstructured Network Data. Guy Bresler, Dheeraj Nagaraj |
| 2018 | Optimal approximation of continuous functions by very deep ReLU networks. Dmitry Yarotsky |
| 2018 | Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methods. Yan Shuo Tan, Roman Vershynin |
| 2018 | Privacy-preserving Prediction. Cynthia Dwork, Vitaly Feldman |
| 2018 | Private Sequential Learning. John N. Tsitsiklis, Kuang Xu, Zhi Xu |
| 2018 | Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure. Matthew S. Brennan, Guy Bresler, Wasim Huleihel |
| 2018 | Restricted Eigenvalue from Stable Rank with Applications to Sparse Linear Regression. Shiva Prasad Kasiviswanathan, Mark Rudelson |
| 2018 | Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem. Andre Wibisono |
| 2018 | Size-Independent Sample Complexity of Neural Networks. Noah Golowich, Alexander Rakhlin, Ohad Shamir |
| 2018 | Small-loss bounds for online learning with partial information. Thodoris Lykouris, Karthik Sridharan, Éva Tardos |
| 2018 | Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent. Niangjun Chen, Gautam Goel, Adam Wierman |
| 2018 | Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form. Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, Praneeth Netrapalli |
| 2018 | Subpolynomial trace reconstruction for random strings \{and arbitrary deletion probability. Nina Holden, Robin Pemantle, Yuval Peres |
| 2018 | Testing Symmetric Markov Chains From a Single Trajectory. Constantinos Daskalakis, Nishanth Dikkala, Nick Gravin |
| 2018 | The Externalities of Exploration and How Data Diversity Helps Exploitation. Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, Zhiwei Steven Wu |
| 2018 | The Many Faces of Exponential Weights in Online Learning. Dirk van der Hoeven, Tim van Erven, Wojciech Kotlowski |
| 2018 | The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity. Vishesh Jain, Frederic Koehler, Elchanan Mossel |
| 2018 | The Vertex Sample Complexity of Free Energy is Polynomial. Vishesh Jain, Frederic Koehler, Elchanan Mossel |
| 2018 | Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. Paul Beame, Shayan Oveis Gharan, Xin Yang |
| 2018 | Underdamped Langevin MCMC: A non-asymptotic analysis. Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, Michael I. Jordan |
| 2018 | Unleashing Linear Optimizers for Group-Fair Learning and Optimization. Daniel Alabi, Nicole Immorlica, Adam Kalai |