Reviews: A no-regret generalization of hierarchical softmax to extreme multi-label classification

Summary: This work investigates Probabilistic Label Trees (PLTs) in solving extreme multi-label classification (XMLC). The theoretical analysis shows PLT is a no-regret algorithm for precision@k, and the algorithmic improvement combines PLT and fastText to efficiently handle extreme multi-label text classification problems, with a clustering-based tree structure building strategy. This paper is comphrensive and well-written, including extensive experiments. The theory part formally shows PLT outputing k labels with highest marginal probabilities is consistent with precision@k, given zero-regret node classifiers. The authors also provide some negative result on heuristic strategies, one is that pick-one-label heuristic is suboptimal in terms of precision@k, and another is that building Huffman trees for PLT does not minimize computational cost.