NeurIPS 2019 is underway in Vancouver, and the committee has just recently announced this years Outstanding Paper Awards.

Before looking at those selected as outstanding, you might want to first have a look at all of the conferences selected papers for 2019.

The Outstanding Paper Committee selection criteria, directly from NeurIPS:We asked the Outstanding Paper Committee to choose from the set of papers that had been selected for oral presentation.

Before looking at the papers, they agreed on the following criteria to guide their selection.

They also agreed on some criteria that they would like to avoid:Finally, they determined it appropriate to introduce an additional Outstanding New Directions Paper Award, to highlight work that distinguished itself in setting a novel avenue for future research.

Selections are presented below, with simplified paper abstracts coming from the NeruIPS Outstanding Paper Awards webpage.

Outstanding Paper Award Distribution-Independent PAC Learning of Halfspaces with Massart Noise, by Ilias Diakonikolas, Themis Gouleakis, Christos Tzamos The paper studies the learning of linear threshold functions for binary classification in the presence of unknown, bounded label noise in the training data.

It solves a fundamental, and long-standing open problem by deriving an efficient algorithm for learning in this case.

This paper makes tremendous progress on a long-standing open problem at the heart of machine learning: efficiently learning half-spaces under Massart noise.

To give a simple example highlighted in the paper, even weak learning disjunctions (to error 49%) under 1% Massart noise was open.

This paper shows how to efficiently achieve excess risk equal to the Massart noise level plus epsilon (and runs in time poly(1/epsilon), as desired).

The algorithmic approach is sophisticated and the results are technically challenging to establish.

The final goal is to be able to efficiently get excess risk equal to epsilon (in time poly(1/epsilon)).

Outstanding New Directions Paper AwardUniform convergence may be unable to explain generalization in deep learning, by Vaishnavh Nagarajan, J.

Zico Kolter The paper presents what are essentially negative results showing that many existing (norm based) bounds on the performance of deep learning algorithms don’t do what they claim.

They go on to argue that they can’t do what they claim when they continue to lean on the machinery of two-sided uniform convergence.

While the paper does not solve (nor pretend to solve) the question of generalisation in deep neural nets, it is an “instance of the fingerpost’’ (to use Francis Bacon’s phrase) pointing the community to look in a different place.

Honorable Mention Outstanding Paper AwardNonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses, by Ananya Uppal, Shashank Singh, Barnabas Poczos The paper shows, in a rigorous theoretical manner, that GANs can outperform linear methods in density estimation (in terms of rates of convergence).

Leveraging prior results on wavelet shrinkage, the paper offers new insight into the representational power of GANs.

Specifically, the authors derive minimax convergence rates for non-parametric density estimation under a large class of losses (so-called integral probability metrics) within a large function class (Besov spaces).

Reviewers felt this paper would have significant impact for researchers working on non-parametric estimation and GANs.

Fast and Accurate Least-Mean-Squares Solvers, by Alaa Maalouf, Ibrahim Jubran, Dan Feldman Least Mean-Square solvers operate at the core of many ML algorithms, from linear and Lasso regression to singular value decomposition and Elastic net.

The paper shows how to reduce their computational complexity by one or two orders of magnitude, with no precision loss and improved numerical stability.

The approach relies on the Caratheodory theorem, establishing that a coreset (set of d2 + 1 points in dimension d) is sufficient to characterize all n points in a convex hull.

The novelty lies in the divide-and-conquer algorithm proposed to extract a coreset with affordable complexity (O(nd + d5 log n), granted that d.. More details