In this talk, I will discuss the prediction properties of techniques commonly used to scale up kernel methods and Gaussian processes. In particular, I will focus on data dependent and independent sub-sampling methods, namely Nystrom and random features, and study their generalization properties within a statistical learning theory framework. On the one hand I will show that these methods can achieve optimal learning errors while being computational efficient. On the other hand, I will show that subsampling can be seen…

Henry L. Rietz, the first president of IMS, published his book “Mathematical Statistics” in 1927. One review wrote in 1928: “Professor Rietz has developed this theory so skillfully that the ’workers in other fields’, provided only that they have a passing familiarity with the grammar of mathematics, can secure a satisfactory understanding of the points involved.” In this lecture, I would like to promote the good tradition of mathematical statistics as expressed in Rietzs book in order to gain insight…

Consider an n by n linear system Ax=b. If the right-hand side of the system is known up to a certain error, then in process of the solution, this error gets amplified by the condition number of the matrix A, i.e. by the ratio of its largest and smallest singular values. This observation led von Neumann and his collaborators to consider the condition number of a random matrix and conjecture that it should be of order n. This conjecture was…

Eigendecomposition of quadratic forms guaranteed by the spectral theorem is the foundation for many important algorithms in computer science, data analysis, and machine learning. In this talk I will discuss our recent work on generalizations from quadratic forms to a broad class of functions based on an analogue of the spectral decomposition in an orthogonal basis. We call such functions ``orthogonally decomposable". It turns out that many inferential problems of recent interest including orthogonal tensor decompositions, Independent Component Analysis (ICA),…

View PDF

Consider the problem of estimating the entries of a large matrix, when the observed entries are noisy versions of a small random fraction of the original entries. This problem has received widespread attention in recent times. I will describe a simple estimation procedure, called Universal Singular Value Thresholding (USVT), that works for any matrix that has "a little bit of structure". Surprisingly, this simple estimator achieves the minimax error rate up to a constant factor. The method is applied to…

Abstract: We consider the problem of influence maximization in fixed networks, for both stochastic and adversarial contagion models. In the stochastic setting, nodes are infected in waves according to linear threshold or independent cascade models. We establish upper and lower bounds for the influence of a subset of nodes in the network, where the influence is defined as the expected number of infected nodes at the conclusion of the epidemic. We quantify the gap between our upper and lower bounds…