Min Jae Song: Continuous LWE

Efficiently extracting useful signals from high-dimensional data is a major challenge in machine learning (ML). When a statistical inference task, known to be possible information-theoretically, persistently eludes computationally efficient learning algorithms, the statistician is faced with a perplexing question: is the failure due to lack of algorithmic ingenuity or is the task inherently hard?

My research attempts to answer such questions by establishing connections between lattice-based cryptography and ML. The cross-fertilization of ideas between the two fields has led to advances in understanding the computational complexity of several statistical inference problems, providing answers of both positive and negative nature.

This talk will focus on the negative results, in particular the Continuous Learning with Errors (CLWE) problem which lies at the center of this fruitful connection. CLWE can be seen as a continuous variant of the well-known Learning with Errors (LWE) problem from lattice-based cryptography. As hinted by the close resemblance to LWE, CLWE also enjoys average-case hardness. This has several implications for ML. For example, it shows that estimating the density of Gaussian mixtures is computationally hard. Moreover, it gives rise to “backdoored” Gaussian distributions which have recently been used to plant undetectable backdoors in ML models (Goldwasser et al., 2022).