Research map / Label-efficient and robust learning / Recognition and long-tail
Generalization Analysis for Label-Specific Representation Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives Rademacher-complexity generalization bounds for label-specific representation learning (LSRL) using a new vector-contraction inequality for l-infinity Lipschitz losses, with bounds nearly independent of the number of labels.
Problem
Generalization analysis of label-specific representation learning in multi-label classification; existing multi-label bounds depend linearly or square-root on the number of labels and preserve coupling among label components, so they do not apply to LSRL.
Approach
A novel vector-contraction inequality for losses Lipschitz w.r.t. the l-infinity norm, combined with a projection function class that decouples per-label components, yields bounds of order eO(1/sqrt(n)) with no (log-only) dependence on the number of labels c; specialized bounds are then derived for k-means (LIFT), Lasso (LLSF), and DNN/GCN (CLIF) LSRL methods.
Key results
- General LSRL function class bound (Theorem 1) has no polynomial dependence on the number of labels c, up to logarithmic terms, with rate eO(1/sqrt(n)).
- k-means LSRL (LIFT) bound (Theorem 2) has rate eO(sqrt(K/n)), independent of the number of labels, matching the clustering lower bound up to log terms.
- Lasso-based LSRL (LLSF) bound under decomposable loss scales as eO(c/sqrt(n)) because the loss Lipschitz constant is (3+2B)c; with Hamming, subset or ranking loss the c dependence can be removed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed ℓ∞-Lipschitz vector-contraction inequality and decouple label components | General LSRL · General LSRL | generalization bound: O(c/√n) and O(√(c/n)) -> eO(1/√n), with no dependency on c, up to logarithmic terms | Helped |
| Use k-means clustering to construct label-specific representations | LIFT · k-means clustering-based LSRL | generalization bound: eO(√(K/n), which is independent on the number of labels | Helped |
| Use Lasso-based label-specific representations with Decomposable loss | LLSF · Lasso-based LSRL | generalization bound: eO(c/√n); with Hamming, Subset or Ranking loss, dependency on c can be improved from linear to independent, up to logari | Mixed |
| Use DNN-based label-specific representations with a GCN over the label graph | CLIF · DNN-based LSRL | generalization bound: eO(1/√n), independent on c, up to logarithmic terms | Helped |
| Increase the depth of the GCN | DNN-based LSRL · DNN-based LSRL | generalization performance | Hurt |
| Increase the maximum node degree of the label graph | DNN-based LSRL · DNN-based LSRL | generalization bound: linearly dependent on the maximum node degree | Hurt |
Surprising findings
- Under decomposable loss, the Lasso-based LSRL bound still depends linearly on c, unlike the other losses.
Limitations
- Purely theoretical; no empirical validation of the bounds.
- Bounds for the Lasso-based method with decomposable loss still grow linearly with c.
- Convergence rate with respect to n is not faster than eO(1/sqrt(n)); authors note tighter rates as future work.
Experimental setup
Metrics: generalization bound Rademacher complexity dependency on number of labels
Baselines: O(c/sqrt(n)) bounds (Maurer 2016) O(sqrt(c/n)) bounds (Wu and Zhu 2020; Wu et al. 2021a) Wu et al. 2021b l-infinity bound
Builds on: vector-contraction inequality (Maurer 2016) Lei et al. 2019 l-infinity Lipschitz multi-class bounds Wu et al. 2021 multi-label generalization bounds LIFT LLSF CLIF
Closest papers by meaning
- Generalization Analysis for Multi-Label Learning (ICML 2024 · similarity 0.91)
- Tight and Fast Bounds for Multi-Label Learning (ICML 2025 · similarity 0.89)
- Theory-Driven Label-Specific Representation for Incomplete Multi-View Multi-Label Learning (NeurIPS 2025 · similarity 0.87)
- InterLUDE: Interactions between Labeled and Unlabeled Data to Enhance Semi-Supervised Learning (ICML 2024 · similarity 0.85)
- Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings (ICML 2025 · similarity 0.85)
- Correlation-Induced Label Prior for Semi-Supervised Multi-Label Learning (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.