Algorithmic Gaussianization in Machine Learning

Randomized algorithms play a central role in analyzing high-dimensional data and training machine learning models. This includes stochastic optimization algorithms, as well as randomized sketching and sampling methods for dimensionality reduction. While providing remarkable computational gains, algorithmic randomness has another important consequence, namely, transforming complex datasets into data distributions which, in a sense, smooth out their higher-order structure. This effect — which we refer to as Algorithmic Gaussianization since the prime example of it is the classical Gaussian embedding — provides both benefits and challenges in utilizing randomized algorithms. On the one hand, it unlocks a wealth of theoretical insights into the performance of those algorithms, such as convergence rates and bias-variance trade-offs, which help practitioners in designing an effective machine learning pipeline. On the other hand, higher-order properties, such as a clustering structure, can be crucial to understanding complex data and models, and this information may not be preserved by randomized algorithms that Gaussianize the data. In this talk, I will introduce the concept of Algorithmic Gaussianization, focusing on the settings of stochastic optimization and dimensionality reduction as motivating examples. Along the way, I will highlight two families of randomized algorithms with Gaussianizing properties: (1) a sketching method called Leverage Score Sparsified (LESS) embeddings; and (2) an importance sampling method called Determinantal Point Processes (DPP).