Swati Padmanabhan

Research Abstract:

Recent works in dimensionality reduction for regression tasks have introduced the notion of sensitivity, an estimate of the importance of a specific datapoint in a dataset, offering provable guarantees on the quality of the approximation after removing low-sensitivity datapoints via subsampling. However, fast algorithms for approximating sensitivities, which we show is equivalent to approximate regression, are known for only the $\ell_2$ setting, in which they are popularly termed leverage scores. In this work, we provide the first algorithms for approximating $\ell_p$ sensitivities and other summary statistics of a given matrix. In particular, for a given $n \times d$ matrix, we compute $\alpha$-approximation to its $\ell_1$ sensitivities at the cost of $n/\alpha$ sensitivity computations. For estimating the total $\ell_1$ sensitivity (i.e. the sum of $\ell_1$ sensitivities), we provide a novel recursive algorithm that computes a constant factor approximation at the cost of roughly $\sqrt{d}$ sensitivity computations, with no polynomial dependence on $n$. For $p=1$, we show that this analysis cannot be improved for our algorithm. Furthermore, we estimate the maximum $\ell_1$ sensitivity up to a $\sqrt{d}$ factor in $O(d)$ sensitivity computations. We also generalize these results to $\ell_p$ norms. Lastly, we experimentally show that for a wide class of structured matrices in real-world datasets, the total sensitivity can be quickly approximated and is significantly smaller than the theoretical prediction, demonstrating that real-world datasets have on average low intrinsic effective dimensionality. -- Joint work with David P. Woodruff (CMU) and Richard Q. Zhang (Google DeepMind).

Bio:

Swati Padmanabhan is currently a postdoctoral researcher at MIT EECS, where she works with Ali Jadbabaie and Suvrit Sra on the theory of optimization algorithms in the context of machine learning. She completed her PhD from the University of Washington, Seattle, advised by Yin Tat Lee, where she worked on developing efficient algorithms for conic, nonsmooth, and online optimization. Prior to her PhD, she did research on rapid diagnostic tools for malaria and worked as a signal processing engineer in the audio and medical electronics industries.