Digging Deeper into the Best of NeurIPS 2019
Introduction
The Conference on Neural Information Processing Systems (NeurIPS) is more than just a conference. It‘s an intellectual gathering point, a nexus for the exchange of ideas that shape the future of artificial intelligence. Since its inception in 1987, NeurIPS has consistently attracted the brightest minds in AI and served as a showcase for groundbreaking research.
Mirroring the explosive growth of AI over the last decade, attendance at NeurIPS has surged, crossing 6,000 in-person attendees for the first time in 2019, with another 5,000 joining online. To put this growth in perspective, the first NeurIPS in 1987 had just 119 attendees!
As the field has matured, NeurIPS has been the venue for seminal works that have stood the test of time. Yann LeCun‘s 1989 paper on handwritten digit recognition with backpropagation foreshadowed the deep learning revolution. Cortes & Vapnik introduced support vector machines at NeurIPS 1995. Hinton & Salakhutdinov showcased the potential of unsupervised pretraining in 2006, paving the way for the dominance of deep learning.
Continuing this tradition of celebrating impactful work are the NeurIPS best paper awards. Let‘s dive deep into the 2019 winners and extract lessons that we can carry forward.
Best Paper
The 2019 best paper, "Distribution-Independent PAC Learning of Halfspaces with Massart Noise", makes significant progress on a classic problem in computational learning theory.
In the Probably Approximately Correct (PAC) learning model, we seek to bound the sample complexity – the number of training examples needed to achieve a target accuracy level – of learning a concept class. A halfspace is a binary classifier representable by a hyperplane in the input space. Massart noise flips each label independently with probability less than 1/2.
Formally, the paper considers learning a halfspace $h_{\mathbf{w}}(\mathbf{x}) = \text{sign}(\langle \mathbf{w}, \mathbf{x} \rangle)$ using samples $(\mathbf{x}_i, y_i)$ drawn from a distribution $\mathcal{D}$ on $\mathbb{R}^d \times {\pm 1}$ such that:
$$
\mathbb{P}{(\mathbf{x}, y) \sim \mathcal{D}}[y \neq h{\mathbf{w}^*}(\mathbf{x})] \leq \eta
$$
The goal is to find $\hat{\mathbf{w}}$ such that $\mathbb{P}{\mathbf{x} \sim \mathcal{D}{\mathcal{X}}}[h{\hat{\mathbf{w}}}(\mathbf{x}) \neq h{\mathbf{w}^*}(\mathbf{x})] \leq \epsilon$ using $\text{poly}(d, 1/\epsilon)$ samples.
The key challenge is that the distribution $\mathcal{D}$ is unknown and arbitrary. Most prior work assumed a specific distribution (like Gaussian) to obtain complexity bounds. The authors develop a new algorithm achieving the optimal sample complexity for learning halfspaces with Massart noise under any distribution.
At a high level, the algorithm proceeds in three stages:
- Identify a low-dimensional subspace containing the optimal halfspace by considering pairwise correlations between examples.
- Solve a sequence of convex programs to find a halfspace with small 0-1 loss on a clean subset of examples.
- Apply additional filtering to the hypothesis to ensure small error on the noisy distribution.
This approach leverages a number of sophisticated tools from high-dimensional probability and empirical process theory. But the end result is a remarkably sample-efficient PAC learner for a natural noise model and concept class.
The techniques introduced may find further applications in other distribution-free learning settings. More broadly, this work illustrates the value of studying simple, well-motivated models and pursuing the fundamental limits of learning.
New Directions
The inaugural Outstanding New Directions award went to "Uniform convergence may be unable to explain generalization in deep learning". This thought-provoking paper questions a common assumption underlying much of learning theory.
Uniform convergence is a powerful tool from statistical learning theory. Roughly speaking, it states that if a hypothesis class has small empirical risk (training error) on a sufficiently large sample, then it will also have small population risk (test error). PAC-Bayes theory extends this idea to random hypothesis classes.
Uniform convergence seems like a natural approach to explaining generalization in deep learning. Neural networks have huge capacity and can fit even random labels, yet still achieve small test error when trained on real data. Intuitively, this seems to suggest some kind of uniform convergence property.
However, the authors present strong empirical evidence that uniform convergence fails to explain generalization in several basic settings:
- For overparameterized neural networks trained on MNIST, test error decreases with more training data, but uniform convergence bounds become vacuous.
- Adding label noise causes training error to increase, but test error remains small. Uniform convergence bounds are again vacuous.
- Theoretical generalization bounds are orders of magnitude larger than the actual generalization gap (difference between train and test error).
These results are demonstrated via a combination of experiments and simple mathematical constructions. For instance, the authors show how to add a small amount of structured noise to MNIST labels in a way that preserves the original labels but forces any learning algorithm to memorize the noise.
If uniform convergence doesn‘t explain generalization, what does? The authors suggest several possible alternatives to investigate, such as forms of implicit regularization induced by the optimization algorithm, or stability notions weaker than uniform convergence.
This paper has sparked significant discussion and follow-up work. Some researchers have proposed mechanisms to partially rescue uniform convergence. Others have taken up the challenge of developing alternative theories. What‘s clear is that our current foundations need re-examination and that generalization in deep learning remains a crucial open problem.
Moving forward, it seems fruitful to further probe our theoretical frameworks with carefully designed empirical tests. The interplay between practical experiments and conceptual insights is key to progress. We may need to let go of cherished assumptions and embrace a diversity of approaches – much like the flexible, overparameterized models we seek to understand.
Test of Time
A decade ago, NeurIPS 2009 featured a paper that deeply influenced the field of stochastic optimization. Lin Xiao‘s "Dual Averaging Method for Regularized Stochastic Learning and Online Optimization" introduced a unifying algorithmic framework with wide-ranging impact.
Stochastic gradient descent (SGD) is the dominant optimization workhorse for large-scale machine learning. But incorporating regularization into SGD, especially non-smooth regularizers like the sparsity-inducing L1 norm, poses both practical and theoretical challenges.
Xiao‘s key innovation was to operate in the dual space, maintaining a running average of all subgradients and only moving to the primal space to output the final solution. The dual averaging update takes the form:
$$
\begin{aligned}
z_{t+1} & = z_t + gt \
x{t+1} & = \arg\minx \left{ \langle z{t+1}, x \rangle + \beta_t \psi(x) + \eta_t h(x) \right}
\end{aligned}
$$
where $g_t$ is a subgradient at $x_t$, $\psi$ is the original objective, $h$ is a regularizer, and $\beta_t, \eta_t$ are step size parameters.
For certain regularizers like the L1 norm, the primal update can be computed efficiently via soft thresholding. The paper proves regret bounds for dual averaging comparable to those of SGD.
The generality of the dual averaging framework has inspired numerous extensions and applications. Notable examples include composite objective mirror descent for regularized problems on curved spaces, adaptive variants like AdaGrad for sparse gradients, and online matrix completion.
One lesson from this work is the value of taking a step back and unifying ideas. Dual averaging provides a single lens through which to view many prior algorithms, and consequently offers a launch pad for new innovations. We can all benefit from occasionally zooming out to see the broader themes that connect our problem domains.
Another takeaway is that theoretical insights can drive practical progress. The dual averaging paper is not merely an abstract result, but has directly influenced the design of optimization methods used every day. As we push the boundaries of machine learning, it‘s worth investing in the core algorithmic and mathematical foundations that form the building blocks of our field.
Reflections
Reflecting on these award-winning works, a few themes emerge. All three papers question conventional wisdom in some way, whether by pursuing distribution-free learning, probing the foundations of generalization, or unifying disparate optimization techniques. They also balance theoretical depth with practical relevance, grounding their insights in empirical evidence.
NeurIPS as a whole exemplifies these qualities, bringing together diverse perspectives and promoting dialogue between theory and practice. Despite its growth in size, the conference remains an intimate venue for exchanging ideas. Where else can you find Turing Award winners mingling with rising undergrads, or hear back-to-back talks on the intricacies of overparameterized models and the latest in robotic grasping?
Moreover, NeurIPS continues to evolve along with the field. The increasing presence of research from developing countries enriches the intellectual discourse. Socially aware initiatives like the Black in AI and Women in Machine Learning workshops celebrate diversity and broaden participation. As AI plays an ever larger role in society, the conference grapples directly with important issues like fairness, accountability, and transparency.
Looking ahead, it‘s hard to predict exactly where AI research is headed. But if the 2019 best papers are any indication, the future is bright. By staying grounded in real-world challenges while pushing the boundaries of what‘s possible, by building on foundations while questioning assumptions, and by bringing together the best minds to share their passion and creativity, NeurIPS will undoubtedly remain a driving force in AI for many years to come.
