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.

The purpose of this talk is to discuss our recent work on multi-frequency quasi-periodic cocycles, establishing continuity (both in cocycle and jointly in cocycle and frequency) of the Lyapunov exponent for non-identically singular cocycles. Analogous results for one-frequency cocycles have been known for over a decade, but the multi-frequency results have been limited to either Diophantine frequencies (continuity in cocycle) or SL(2,C) cocycles (joint continuity). We will discuss the main points of our argument, which extends earlier work of Bourgain.

The last decade has witnessed great interest in the study of divisors of graphs and a fascinating combinatorially-rich picture has emerged. The class of break divisors has attracted particular attention, for reasons both geometric and combinatorial. I will present several representation-theoretic results in this context.

I will demonstrate how certain quotients of polynomial rings by power ideals, already studied by Ardila-Postnikov, Sturmfels-Xu, Postnikov-Shapiro amongst others, arise by applying the method of orbit harmonics to break divisors. These quotients then naturally afford symmetric group representations which are not entirely understood yet. By describing the invariant spaces of these representations in terms of break divisors, I will answer a combinatorial question from the setting of cohomological Hall algebras.

Fruitful interactions between arithmetic geometry and dynamical systems have emerged in recent years. In this talk I will illustrate how insights from complex dynamics can be employed to study problems from arithmetic geometry. And conversely how arithmetic geometry can be used in the study of dynamical systems. The motivating questions are inspired by a recurring phenomenon in arithmetic geometry known as `unlikely intersections' and conjectures of Pink and Zilber therein. More specifically, I will discuss work toward understanding the distribution of preperiodic points in subvarieties of families of rational maps.