Novel Contributions: Our main contributions are: (a) the development of a (non-trivial) data-dependent

We thank the reviewers for their valuable time and thoughtful feedback. Our method also has a provably log-time prediction algorithm, enabling almost real-time predictions. We next use label partitioning to improve over NMF-GT for larger datasets (Table 2). We do mention that for Mediamill and RCV1x there were no clear label partitions. We thank the reviewers for these suggestions.