Georgia Institute of Technology College of Sciences

Memory bounds for continual learning

Abstract: Continual learning, or lifelong learning, is a formidable current challenge to machine learning. It requires the learner to solve a sequence of k different learning tasks, one after the other, while with each new task learned it retains its aptitude for earlier tasks; the continual learner should scale better than the obvious solution of developing and maintaining a separate learner for each of the k tasks.  We embark on a complexity-theoretic study of continual learning in the PAC framework. We make novel uses of communication complexity to establish that any continual learner, even an improper one, needs memory that grows linearly with k, strongly suggesting that the problem is intractable.  When logarithmically many passes over the learning tasks are allowed, we provide an algorithm based on multiplicative weights update whose memory requirement scales well; we also establish that improper learning is necessary for such performance. We conjecture that these results may lead to new promising approaches to continual learning.

Based on the joint work with Xi Chen and Christos Papadimitriou.

In recent years, there has been increased interest in using quantum computing for the purposes of solving problems in combinatorial optimization. No prior knowledge of quantum computing is necessary for this talk; in particular, the talk will be divided into three parts: (1) a gentle high-level introduction to the basics of quantum computing, (2) a general framework for solving combinatorial optimization problems with quantum computing (the Quantum Approximate Optimization Algorithm introduced by Farhi et al.), (3) and some recent results that my colleagues and I have found. Our group has looked at the Max-Cut problem and have developed a new quantum algorithm that utilizes classically-obtained warm-starts in order to improve upon already-existing quantum algorithms; this talk will discuss both theoretical and experimental results associated with our approach with our main results being that we obtain a 0.658-approximation for Max-Cut, our approach provably converges to the Max-Cut as a parameter (called the quantum circuit depth) increases, and (on small graphs) are approach is able to empirically beat the (classical) Goemans-Williamson algorithm at a relatively low quantum circuit-depth (i.e. using a small amount of quantum resources). This work is joint with Jai Moondra, Bryan Gard, Greg Mohler, and Swati Gupta.

Federated learning is a distributed learning paradigm where multiple agents, each only with access to local data, jointly learn a global model. There has recently been an explosion of research aiming not only to improve the accuracy rates of federated learning, but also provide certain guarantees around social good properties such as total error or fairness. In this talk, I describe two papers analyzing federated learning through the lens of cooperative game theory (both joint with Jon Kleinberg).

In the first paper, we discuss fairness in federated learning, which relates to how error rates differ between federating agents. In this work, we consider two notions of fairness: egalitarian fairness (which aims to bound how dissimilar error rates can be) and proportional fairness (which aims to reward players for contributing more data). For egalitarian fairness, we obtain a tight multiplicative bound on how widely error rates can diverge between agents federating together. For proportional fairness, we show that sub-proportional error (relative to the number of data points contributed) is guaranteed for any individually rational federating coalition. The second paper explores optimality in federated learning with respect to an objective of minimizing the average error rate among federating agents. In this work, we provide and prove the correctness of an efficient algorithm to calculate an optimal (error minimizing) arrangement of players. Building on this, we give the first constant-factor bound on the performance gap between stability and optimality, proving that the total error of the worst stable solution can be no higher than 9 times the total error of an optimal solution (Price of Anarchy bound of 9). 

Relevant Links: https://arxiv.org/abs/2010.00753, https://arxiv.org/abs/2106.09580, https://arxiv.org/abs/2112.00818

Bio:
Kate Donahue is a fifth year computer science PhD candidate at Cornell advised by Jon Kleinberg. She works on algorithmic problems relating to the societal impact of AI such as fairness, human/AI collaboration and game-theoretic models of federated learning. Her work has been supported by an NSF fellowship and recognized by a FAccT Best Paper award. During her PhD, she has interned at Microsoft Research, Amazon, and Google.