# Rademacher Complexity Bounds for a Penalized Multiclass Semi-Supervised Algorithm

arXiv: https://arxiv.org/abs/1607.00567 · HTML: https://mlsanity.com/paper/1607.00567/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2016.

## Built on by (most cited first, 15 of 15)

- [Self-Training: A Survey](https://mlsanity.com/paper/2202.12040/) (2022)
- [FlatMatch: Bridging Labeled Data and Unlabeled Data with Cross-Sharpness for Semi-Supervised Learning](https://mlsanity.com/paper/2310.16412/) (2023)
- [Fine-grained Generalization Analysis of Vector-valued Learning](https://mlsanity.com/paper/2104.14173/) (2021)
- [Fine-grained Generalization Analysis of Structured Output Prediction](https://mlsanity.com/paper/2106.00115/) (2021)
- [Long-term drought prediction using deep neural networks based on geospatial weather data](https://mlsanity.com/paper/2309.06212/) (2023)
- [Multi-class Probabilistic Bounds for Self-learning](https://mlsanity.com/paper/2109.14422/) (2021)
- [Self-Training of Halfspaces with Generalization Guarantees under Massart Mislabeling Noise Model](https://mlsanity.com/paper/2111.14427/) (2021)
- [Multi-class Classification with Fuzzy-feature Observations: Theory and Algorithms](https://mlsanity.com/paper/2206.04311/) (2022)
- [Self-Improvement as Coherence Optimization: A Theoretical Account](https://mlsanity.com/paper/2601.13566/) (2026)
- [Learning over No-Preferred and Preferred Sequence of Items for Robust Recommendation (Extended Abstract)](https://mlsanity.com/paper/2202.13240/) (2022)
- [Inference and Optimization for Engineering and Physical Systems](https://mlsanity.com/paper/2208.13880/) (2022)
- [DRIFT: A Federated Recommender System with Implicit Feedback on the Items](https://mlsanity.com/paper/2304.09084/) (2023)
- [Deep Learning with Partially Labeled Data for Radio Map Reconstruction](https://mlsanity.com/paper/2306.05294/) (2023)
- [Unsupervised Domain Adaptation with Deep Neural-Network](https://mlsanity.com/paper/2307.05601/) (2023)
- [Cost-Sensitive Unbiased Risk Estimation for Multi-Class Positive-Unlabeled Learning](https://mlsanity.com/paper/2510.25226/) (2025)

## Abstract (arXiv)

We propose Rademacher complexity bounds for multiclass classifiers trained with a two-step semi-supervised model. In the first step, the algorithm partitions the partially labeled data and then identifies dense clusters containing kappa predominant classes using the labeled training examples such that the proportion of their non-predominant classes is below a fixed threshold. In the second step, a classifier is trained by minimizing a margin empirical loss over the labeled training set and a penalization term measuring the disability of the learner to predict the kappa predominant classes of the identified clusters. The resulting data-dependent generalization error bound involves the margin distribution of the classifier, the stability of the clustering technique used in the first step and Rademacher complexity terms corresponding to partially labeled training data. Our theoretical result exhibit convergence rates extending those proposed in the literature for the binary case, and experimental results on different multiclass classification problems show empirical evidence that supports the theory.