Everyone is welcome to attend the N&O seminar of Aleksandar Nikolov with the title: 'Proportional Volume Sampling and Approximation Algorithms for Optimal Design'.
Abstract:
We study optimal design problems in which the goal is to choose a set of noisy linear measurements in order to obtain the most accurate estimate of an unknown parameter vector. The noise in each measurement is IID normal, and the goal is to minimize some objective that quantifies the uncertainty of the maximum likelihood estimate of the unknown vector. We study the A- and the D-optimal design variants where the objective is, respectively, to minimize the average variance of the error, and to minimize the volume of the confidence ellipsoid. We introduce the proportional volume sampling algorithm to obtain nearly optimal bounds in the asymptotic regime when the number k of measurements made is significantly larger than the dimension d, and also obtain the first approximation algorithms whose approximation factor does not degrade with the number of possible measurements when k is small. We will also hint at how these results extend to more complicated combinatorial constraints !
on the set of measurements that are allowed to be made.
More generally, our techniques apply to problems in which we are given a set of rank-1 PSD matrices, and the goal is to select, subject to combinatorial constraints, some subset of them whose sum is large, as captured by an appropriate objective. Besides optimal design, such problems arise naturally in the study of determinantal point processes, of sparse spectral approximations of graphs and matrices, and of column selection for low-rank approximation.
Joint work with Mohit Singh and Uthaipon Tao Tantipongpipat.
