UC Berkeley

The purpose of this thesis is to address the following simple question:

How do we design efficient algorithms to solve optimization or machine learning problems where the decision variable (or target label) is a set of unknown cardinality?

In this thesis we show that, in some cases, optimization and machine learning algorithms designed to work with single vectors can be directly applied to problems involving sets. We do this by invoking a classical trick: we lift sets to elements of a vector space, namely an infinite-dimensional space of measures. While this idea has been explored extensively in theoretical analysis, we show that it also generates efficient practical algorithms.