2014/10/26 by Chang Xu, Xu, Chang, Tongliang Liu +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning in Bioinformatics #Text and Document Classification Technologies
paper · pdf · doi:10.48550/arxiv.1410.6990
openalex publication_date 2014/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We analyze the local Rademacher complexity of empirical risk minimization (ERM)-based multi-label learning algorithms, and in doing so propose a new algorithm for multi-label learning. Rather than using the trace norm to regularize the multi-label predictor, we instead minimize the tail sum of the singular values of the predictor in multi-label learning. Benefiting from the use of the local Rademacher complexity, our algorithm, therefore, has a sharper generalization error bound and a faster convergence rate. Compared to methods that minimize over all singular values, concentrating on the tail singular values results in better recovery of the low-rank structure of the multi-label predictor, which plays an import role in exploiting label correlations. We propose a new conditional singular value thresholding algorithm to solve the resulting objective function. Empirical studies on real-world datasets validate our theoretical results and demonstrate the effectiveness of the proposed algorithm.