Abstract

In this talk I will motivate and discuss solutions to four learning challenges: How to efficiently optimize beyond the class of convex functions; How to get good performance in deep learning despite overfitting training data; How to efficiently count rare items in data; and, How to make predictions when the future is not like the past.

The first result shows how to extend polynomial-time optimization algorithms from the classic case of convex optimization to a broader class of "star-convex" functions, which capture some natural non-convex settings in learning. The algorithm is a randomized adaptation of the ellipsoid algorithm which, unexpectedly, uses information from far outside the feasible region. The second result confronts one of the main challenges in deep learning: understanding why "overparameterized" models that can perfectly fit the training data still have such good performance on new data. We introduce a new notion of implicit regularization that arises by comparing stochastic gradient descent to an Ornstein-Uhlenbeck process. The third result considers the problem of rapidly estimating the frequency of a rare and expensive-to-verify occurrence in a database, such as a data error that might require human judgement to detect. We introduce an adaptive algorithm that abandons further investigation of items that look potentially not-rare, without introducing bias in the estimate. Finally, we consider a fundamental and perennial challenge for machine learning: as opposed to assuming that the test set and training set were drawn from the same distribution, suppose we instead know that some different probabilistic process took place to produce the training data and test data. We introduce a new framework based on a semidefinite-programming relaxation to yield almost-optimal linear estimators in the case of mean estimation in the challenging setting where an adversary chooses data values.