  Extreme multi-label classification (XMC) is the problem of finding the
relevant labels for an input, from a very large universe of possible labels. We
consider XMC in the setting where labels are available only for groups of
samples - but not for individual ones. Current XMC approaches are not built for
such multi-instance multi-label (MIML) training data, and MIML approaches do
not scale to XMC sizes. We develop a new and scalable algorithm to impute
individual-sample labels from the group labels; this can be paired with any
existing XMC method to solve the aggregated label problem. We characterize the
statistical properties of our algorithm under mild assumptions, and provide a
new end-to-end framework for MIML as an extension. Experiments on both
aggregated label XMC and MIML tasks show the advantages over existing
approaches.
