Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Multi-label classification: do Hamming loss and subset accuracy really
  conflict with each other?   Various evaluation measures have been developed for multi-label
classification, including Hamming Loss (HL), Subset Accuracy (SA) and Ranking
Loss (RL). However, there is a gap between empirical results and the existing
theories: 1) an algorithm often empirically performs well on some measure(s)
while poorly on others, while a formal theoretical analysis is lacking; and 2)
in small label space cases, the algorithms optimizing HL often have comparable
or even better performance on the SA measure than those optimizing SA directly,
while existing theoretical results show that SA and HL are conflicting
measures. This paper provides an attempt to fill up this gap by analyzing the
learning guarantees of the corresponding learning algorithms on both SA and HL
measures. We show that when a learning algorithm optimizes HL with its
surrogate loss, it enjoys an error bound for the HL measure independent of $c$
(the number of labels), while the bound for the SA measure depends on at most
$O(c)$. On the other hand, when directly optimizing SA with its surrogate loss,
it has learning guarantees that depend on $O(\sqrt{c})$ for both HL and SA
measures. This explains the observation that when the label space is not large,
optimizing HL with its surrogate loss can have promising performance for SA. We
further show that our techniques are applicable to analyze the learning
guarantees of algorithms on other measures, such as RL. Finally, the
theoretical analyses are supported by experimental results.

20
The categories of this paper are: acc-phys
28
The categories of this paper are: alg-geom
11
The categories of this paper are: hep-lat
22
The categories of this paper are: chao-dyn
33
The categories of this paper are: plasm-ph
0
The categories of this paper are: hep-ph
21
The categories of this paper are: adap-org
24
The categories of this paper are: dg-ga
25
The categories of this paper are: patt-sol
31
The categories of this paper are: ao-sci
2
The categories of this paper are: math
35
The categories of this paper are: mtrl-th
9
The categories of this paper are: nlin
32
The categories of this paper are: atom-ph
5
The categories of this paper are: gr-qc
4
The categories of this paper are: cond-mat