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.

A longstanding question in deep learning theory asks why gradient descent (GD) finds good solutions in non-convex neural-network optimization landscapes. One compelling theory is that overparameterization makes the optimization landscape benign, leading GD to find global optima. These global convergence guarantees have even been proven rigorously in some settings for infinite-width neural networks. In this talk, I’ll address the question of when such infinite-width convergence guarantees can be transferred to finite-width 2-layer networks. I’ll show that whenever the convergence rate of the infinite-width network is faster than 1/t^2, comparable guarantees can be attained in finite-width networks. A key takeaway of our result is that whenever the convergence rate of the infinite-width, population-loss dynamics is faster than 1/t^2 , we can attain a loss of ϵ with only poly(d/ϵ) neurons, training samples, and GD steps.

My talk will be about the problem of dividing a set of indivisible items among agents with differing preferences over these items. The goal of this problem is to compute an allocation that maximizes some objective usually related to fairness and/or efficiency. I will focus on the objective of Nash welfare, which is widely regarded as an objective that (almost) perfectly balances fairness and efficiency.

Despite its popularity, the approximability of max Nash welfare allocations still remains an open question with there being a gap between the best approximation algorithm and the best inapproximability result. I will discuss the following two results making progress on this open question from both directions:

(1) I will present an \((e^{1/e} - c)\)-approximation algorithm for maximizing Nash welfare for some small constant \(c\). (2) I will show that the max Nash welfare is inapproximable by a factor of 1.076 unless the unique games conjecture is false.

A simple way to search a large collection of vectors is to connect them in a graph and follow edges toward points closer to the query. Methods based on this idea work remarkably well in practice, but when can we prove that they are fast? In this talk, I will discuss two recent projects approaching this question from different directions.

First, I will show that a broad class of greedy graph-based search methods can require a linear number of distance computations in the worst case, even if we only want an approximate nearest neighbor. However, adding extra vertices, called Steiner points, changes the picture: we can use them to simulate locality-sensitive hashing and obtain sublinear query time.

The second project starts with a geometric question: given a set of points, can we choose two of them so that splitting the dataset according to which one is closer gives two reasonably balanced parts? We show that this is always possible in Euclidean space, with balance depending polynomially on the dimension. The key is a connection to self-approaching sequences—sequences whose points become progressively closer to every other point. I will explain this connection and how it leads to navigable graphs with routing time polynomial in the dimension and logarithmic in the dataset size, using a variant of greedy routing.

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