In game-theoretic formulations of prediction problems, a strategy makes a decision, observes an outcome and pays a loss. The aim is to minimize the regret, which is the amount by which the total loss incurred exceeds the total loss of the best decision in hindsight. This talk will focus on the minimax optimal strategy, which minimizes the regret, in three settings: prediction with log loss (a formulation of sequential probability density estimation that is closely related to sequential compression, coding,…

Principal components is a true workhorse of science and technology, applied everywhere from radio frequency signal processing to financial econometrics, genomics, and social network analysis. In this talk, I will review some of these applications and then describe the challenge posed by modern 'big data asymptotics' where there are roughly as many dimensions as observations; this setting has seemed in the past full of mysteries. Over the last ten years random matrix theory has developed a host of new tools…

The problem of finding large average submatrices of a real-valued matrix arises in the exploratory analysis of data from disciplines as diverse as genomics and social sciences. This talk will present several new theoretical results concerning large average submatrices of an n x n Gaussian random matrix that are motivated in part by previous work on biomedical applications. We will begin by considering the average and distribution of the k x k submatrix having largest average value (the global maximum),…

Motivated by machine learning problems over large data sets and distributed optimization over networks, we consider the problem of minimizing the sum of a large number of convex component functions. We study incremental gradient methods for solving such problems, which process component functions sequentially one at a time. We first consider deterministic cyclic incremental gradient methods (that process the component functions in a cycle) and provide new convergence rate results under some assumptions. We then consider a randomized incremental gradient…

Shape constraints such as monotonicity, convexity, and log-concavity are naturally motivated in many applications, and can offer attractive alternatives to more traditional smoothness constraints in nonparametric estimation. In this talk we present some recent results on shape constrained estimation in high and low dimensions. First, we show how shape constrained additive models can be used to select variables in a sparse convex regression function. In contrast, additive models generally fail for variable selection under smoothness constraints. Next, we introduce graph-structured…

While simple supervised learning problems like binary classification and regression are fairly well understood, increasingly, many applications involve more complex learning problems: more complex label and prediction spaces, more complex loss structures, or both. The first part of the talk will discuss recent advances in our understanding of such problems, including the notion of convex calibration dimension of a loss function, unified approaches for designing convex calibrated surrogates for arbitrary losses, and connections between supervised learning and property elicitation. The…