Theory Seminar

Traditional machine learning methods seek to learn functions that map vector-valued input data to scalar-valued outputs or labels. Increasingly, however, applications in scientific machine learning (SciML) and other areas require models that map vector-valued data to vector-valued data. Such operator learning methods have been critical to recent breakthroughs in computational science, including on AI-driven methods for weather prediction, PDE solving, and more.

In this talk, I will discuss a research program that seeks to understand the sample complexity of operator learning, which is a critical bottleneck in many applications. We focus in particular on the problem of learning linear operators – i.e., matrices. Even this restricted setting leads to many interesting theoretical questions. I will highlight recent work that tackles some of these questions by leveraging tools from randomized numerical linear algebra (RandNLA). I will also discuss our efforts to develop a general learning theory for linear operators.

Cameron Musco is an Associate Professor in UMass Amherst’s Manning College of Information and Computer Sciences, where he is a member of the Theory Group. He studies algorithms, working at the intersection of theoretical computer science, numerical linear algebra, and machine learning. His group’s research is supported in part by an NSF CAREER Award and a Google Research Scholar Award. Before UMass, he completed his Ph.D. in the Theory of Computation Group at MIT, advised by Nancy Lynch, and before MIT, he studied Computer Science and Applied Math at Yale.

We study symmetric encryption of high-dimensional embedding vectors that preserves enough geometric structure to support (approximate) nearest-neighbor search on ciphertexts. Since usual chosen-plaintext attack (CPA) model security is unlikely, we focus on restricted attacks such as single snapshot attacks with limited known plaintexts. Our scheme encrypts a vector by sending it through a secret Isometric transform followed by adding noise, a la LWE. Because a rotation preserves all pairwise distances, the residual structure available to a snapshot adversary is exactly a distance-labeled graph, so plain- text recovery reduces to a constrained, average-case subgraph-isomorphism problem. Our main technical contribution is evidence that this problem resists the dominant algorithmic paradigm, i.e. Ullman’s pruning-and-backtracking.

Charanjit Jutla received his PhD in Computer Science from the University of Texas at Austin in 1990. Since then he has been a Research Staff Member at the IBM T. J. Watson Research Center. His research focuses in the fields of Cryptography, Coding Theory and Complexity Theory. Among his various contributions to cryptography, he invented the first single-pass Authenticated Encryption Scheme. He is the author of several papers and patents in the field of cryptography. He has been on the program committee of various international cryptography conferences.

Abstract TBA

Bio TBA

Abstract TBA

Bio TBA

Abstract TBA

Bio TBA

Abstract TBA

Bio TBA

Abstract TBA

Bio TBA

Abstract TBA

Bio TBA

Abstract TBA

Bio TBA

Abstract TBA

Bio TBA

Abstract TBA

Bio TBA

Abstract TBA

Bio TBA