We consider the problem of learning a one-hidden-layer neural network: we assume the input x is from Gaussian distribution and the label $y = a \sigma(Bx) + \xi$, where a is a nonnegative vector and  $B$ is a full-rank weight matrix, and $\xi$ is a noise vector. We first give an analytic formula for the population risk of the standard squared loss and demonstrate that it implicitly attempts to decompose a sequence of low-rank tensors simultaneously.
        
        Inspired by the formula, we design a non-convex objective function $G$ whose landscape is guaranteed to have the following properties:
       
        1. All local minima of $G$ are also global minima.
        2. All global minima of $G$ correspond to the ground truth parameters.
        3. The value and gradient of $G$ can be estimated using samples.
        
        With these properties, stochastic gradient descent on $G$ provably converges to the global minimum and learn the ground-truth parameters. We also prove finite sample complexity results and validate the results by simulations.

Statistical machine learning uses data to make inferences about the distribution from which that data was drawn. A key challenge is to prevent overfitting -- that is, inferring a property that only occurs in the data by chance and is not reflected in the underlying distribution. The problem of overfitting is exacerbated by adaptive re-use of data; if we have previously used the same data, then we can no longer assume that it is "fresh" when used again, as the later analysis may now depend on the data via the outcome of the earlier analysis.

This talk will discuss the use of information-theoretic stability as a method to prevent overfitting when data is re-used adaptively. Intuitively, an algorithm is stable if it "learns" very little about each individual datum (which does not preclude learning about the data as a whole). I will discuss how techniques from the differential privacy literature can be used to construct stable algorithms to perform data analysis tasks and how stability protects against overfitting.

Recent years have seen astounding progress both in theory and practice of nonconvex optimization. Carefully designed nonconvex procedures simultaneously achieve optimal statistical accuracy and computational efficiency for many problems. Due to the highly nonconvex landscape, the state-of-the-art results often require proper regularization procedures (e.g. trimming, projection, or extra penalization) to guarantee fast convergence. For vanilla algorithms, however, the prior theory usually suggests conservative step sizes in order to avoid overshooting.

This talk uncovers a striking phenomenon: even in the absence of explicit regularization, nonconvex gradient descent enforces proper regularization automatically and implicitly under a large family of statistical models. In fact, the vanilla nonconvex procedure follows a trajectory that always falls within a region with nice geometry. This "implicit regularization" feature allows the algorithm to proceed in a far more aggressive fashion without overshooting, which in turn enables faster convergence.  We will discuss several concrete fundamental problems including phase retrieval, matrix completion, blind deconvolution, and recovering structured probability matrices, which might shed light on the effectiveness of nonconvex optimization for solving more general structured recovery problems.

We consider the problem of bandit optimization, inspired by stochastic optimization and online learning problems with bandit feedback. In this problem, the objective is to minimize a global loss function of all the actions, not necessarily a cumulative loss. This framework allows us to study a very general class of problems, with applications in statistics, machine learning, and other fields. To solve this problem, we analyze the Upper-Confidence Frank-Wolfe algorithm, inspired by techniques for bandits and convex optimization. We give theoretical guarantees for the performance of this algorithm over various classes of functions, and discuss the optimality of these results.

In the last few years we have seen remarkable progress in machine learning in large part due to neural networks trained on large data. While shallow methods, in particular methods based on positive definite kernels, show excellent results on smaller data sets, their performance suffers at large scale. It turns out that some of this lack of performance can be attributed to the computational limitations of kernel learning. The span of smooth kernel functions (such as Gaussians) is dense in the space of all functions and theoretically any function can be approximated arbitrarily well. However, the space of functions reachable within a fixed computational budget is quite limited. This can be formalized in terms of the fat shattering dimension and other measures of complexity. This computational barrier turns out to be related to the smoothness of the kernel and to the types of computations available for large data. One way to address this issue is by constructing new, less smooth kernels, designed for efficient computation. The resulting algorithms show significant improvements over the state of the art in large scale kernel methods, typically at a fraction of the computational budget reported in the literature. Finally, we hope that deeper understanding of kernel-based learning can also shed light on the success of neural networks.

Based on joint work with Siyuan Ma.