PIMS-CORDS SFU Operations Research Seminar: Eitan Levin

Classical algorithms are defined on inputs of different sizes. In contrast, data-driven algorithms, that is, algorithms learned from some data, may only be defined on inputs of the same size as the data. What does it mean for an algorithm to be defined on infinitely-many input sizes? How do we describe such algorithms, and how do we parametrize and search over them?

In this talk, we tackle these questions for convex optimization-based algorithms. Describing such algorithms reduces to describing convex sets. These, in turn, are often "freely" described, meaning that their description makes instantiation in every dimension obvious. Examples include unit balls of standard norms defined on vectors of any size, graph parameters defined for graphs of any size, and (quantum) information theoretic quantities defined for distributions on any number of (qu)bits.

We show that such free descriptions of convex sets arise from two ingredients. First, group invariance and the recently-identified phenomenon of representation stability. Second, embeddings and projections relating different-sized problem instances. We combine these ingredients to obtain parametrized families of infinitely instantiable convex sets. To extend a set learned from data in a fixed dimension to higher ones, we identify consistency conditions relating sets in different dimensions that are satisfied in a variety of applications, and obtain parametrizations respecting these conditions. Our parametrizations can be obtained computationally.