AutoCoreset: An Automatic Practical Coreset Construction Framework
Alaa Maalouf Murad Tukan Vladimir Braverman Daniela Rus
A coreset is a tiny weighted subset of an input set, that closely resembles
the loss function, with respect to a certain set of queries. Coresets became
prevalent in machine learning as they have shown to be advantageous for many
applications. While coreset research is an active research area, unfortunately,
coresets are constructed in a problem-dependent manner, where for each problem,
a new coreset construction algorithm is usually suggested, a process that may
take time or may be hard for new researchers in the field. Even the generic
frameworks require additional (problem-dependent) computations or proofs to be
done by the user. Besides, many problems do not have (provable) small coresets,
limiting their applicability. To this end, we suggest an automatic practical
framework for constructing coresets, which requires (only) the input data and
the desired cost function from the user, without the need for any other
task-related computation to be done by the user. To do so, we reduce the
problem of approximating a loss function to an instance of vector summation
approximation, where the vectors we aim to sum are loss vectors of a specific
subset of the queries, such that we aim to approximate the image of the
function on this subset. We show that while this set is limited, the coreset is
quite general. An extensive experimental study on various machine learning
applications is also conducted. Finally, we provide a ``plug and play" style
implementation, proposing a user-friendly system that can be easily used to
apply coresets for many problems. Full open source code can be found at
\href{https://github.com/alaamaalouf/AutoCoreset}{\text{https://github.com/alaamaalouf/AutoCoreset}}.
We believe that these contributions enable future research and easier use and
applications of coresets.