Local Rademacher Complexity for Multi-label Learning
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Label LearningSimilar Papers 제목 키워드 기반
The Impact of Unlabeled Patterns in Rademacher Complexity Theory for Kernel Classifiers
We derive here new generalization bounds, based on Rademacher Complexity theory, for model selection and error estimation of linear (kernel) classifiers, which exploit the availability of unlabeled samples. In parti…
Generalization BoundsModel SelectionSemi-supervised Vector-valued Learning: Improved Bounds and Algorithms
Vector-valued learning, where the output space admits a vector-valued structure, is an important problem that covers a broad family of important domains, e.g. multi-task learning and transfer learning. Using local Radema…
Multi-class ClassificationMulti-Label LearningMulti-Task LearningTransfer LearningTransductive Rademacher Complexity and its Applications
We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in …
Transductive LearningLocal Rademacher Complexity Bounds based on Covering Numbers
This paper provides a general result on controlling local Rademacher complexities, which captures in an elegant form to relate the complexities with constraint on the expected norm to the corresponding ones with constrai…
Permutational Rademacher Complexity: a New Complexity Measure for Transductive Learning
Transductive learning considers situations when a learner observes $m$ labelled training points and $u$ unlabelled test points with the final goal of giving correct answers for the test points. This paper introduces a ne…
Learning TheoryTransductive Learning