ProML: Progressive Multi-label Learning

Yi Kou; Jieting Wang; Yuhua Qian

cs.LGOct 11, 2026

ProML: Progressive Multi-label Learning

Authors: Yi Kou, Jieting Wang, Yuhua Qian

Organizations: Institute of Big Data Science and Industry, the School of Artificial Intelligence, and the Key Laboratory of Evolutionary Science Intelligence of Shanxi Province, Shanxi University, Taiyuan 030006, Shanxi, China

Abstract

Multi-label learning typically pursues model construction through the joint optimization of label fitting, correlation modeling, and structural regularization. While empirically effective, such a coupled paradigm imposes multiple learning objectives on a single predictive parameter matrix, forcing it to simultaneously fit observed labels and encode structural priors. This coupling may induce ill-conditioned optimization geometry, increase hyper-parameter sensitivity, and complicate capacity control. To address the these issues, this paper proposes a Progressive Multi-Label Learning (ProML) framework, which decouples direct label fitting from predictor learning via the introduction of an auxiliary predictive variable. This auxiliary variable admits a closed-form solution, yielding an equivalent profiled objective in which the supervised fitting term is scaled by a trade-off parameter. This result provides a unified view of ProML and conventional coupled learning, with the latter recovered as a limiting case. We theoretically analyze the optimization geometry of ProML and show that, under quadratic positive semidefinite structural regularization, ProML attenuates the dominant curvature of the fitting term, enlarges the stable learning rate range, and provides a controllable fidelity-regularization trade-off. Further, we instantiate the ProML for multi-label feature selection task by integrating global-local label priors and row-sparse regularization. Extensive experiments and controlled optimization analyses on 12 benchmark datasets empirically corroborate the theoretical analysis and demonstrate the robust and competitive performance of the proposed method.

Figures & tables

Fig. 1: The loss landscapes and optimization trajectories of (a) GMLL and (b) ProML. For ProML, the additional profiling parameter is set to $\mu=0.046$ . Under these otherwise identical settings, the figure provides a visual comparison of the optimization landscapes and trajectories induced by the two formulations. The curves represent the optimization paths, and the yellow dots and green stars denote the starting points and the obtained optima, respectively.

Fig. 2: Condition-number evolution of ProML on the Emotions dataset. The blue curve shows

\kappa(\mathbf{H}_{P})

as a function of the decoupling parameter

\!\mu\!

, and the red dashed line denotes the GMLL condition number

\kappa(\mathbf{H}_{G})

. As

\!\mu\!\to\!0,s\!\to\!0^{+}

, ProML approaches the structural regularization dominated regime with

\!\kappa(\mathbf{H}_{P})\!\to\!\kappa(\boldsymbol{C})

. As

\!\mu\!\to\!\infty,s\!\to\!1^{-}

, ProML recovers GMLL and

\kappa(\mathbf{H}_{P})\!\to\!\kappa(\mathbf{H}_{G})

Fig. 3: Projected optimization trajectories with a super-critical learning rate on the Emotions dataset. The learning rate is set above the critical threshold of GMLL but remains within the stable range of ProML, i.e. , $\!\eta_{\mathrm{crit}}^{G}\!<\!\eta\!:=\!1.3\!\times\!\eta_{crit}^{G}\!<\!\eta_{\mathrm{crit}}^{P}\!$ . In this setting, GMLL oscillates along the high-curvature direction and escapes to a high-loss region, while ProML maintains stable descent toward the optimum. Since $\eta$ has not reached the optimal learning rate for ProML, the rate of decline is slow.

Fig. 4: Normalized loss and gradient-norm trajectories with a super-critical learning rate on the Emotions dataset. When learning rate is set to

\!\eta\!:=\!1.3\!\times\!\eta_{crit}^{G}

, both the loss and gradient-norm of GMLL exhibit explosive growth, while ProML maintains a stable decay throughout the entire training process. The zoom-mode factors explain this contrast: the largest-curvature component is amplified by approximately

1.60

per iteration for GMLL, but contracted by approximately

0.807

per iteration for ProML.

Fig. 5: Visualization of the effective hypothesis class contraction. The gray dotted sphere indicates that the original parameter space remains unchanged. The blue and orange spheres denote the GMLL effective hypothesis class $\mathcal{F}_{G}$ with radius $B_{1}$ and the ProML effective hypothesis class $\mathcal{F}_{P}$ with radius $B_{s}\!=\!s\cdot B_{1}$ , respectively, where $s\!=\!\mu/(1\!+\!\mu)$ . This radius contraction leads to the empirical Rademacher complexity bound $\hat{\mathfrak{R}}_{S}(\mathcal{F}_{P})\!\leq\!\hat{\mathfrak{R}}_{S}(\mathcal{F}_{G})$ .

No.	Dataset	Samples	Features	Labels	Type
1	Cal500	502	68	174	Music
2	Emotions	593	72	6	Music
3	Birds	645	260	20	Audio
4	Image	2000	294	5	Image
5	Scene	2407	294	6	Image
6	Yeast	2417	103	14	Biology

TABLE I: Description of Datasets

Id	Datasets	Hamming Loss ( $\downarrow$ )
Id	Datasets	ML-KNN	JFSC	MDFS	GLFS	GRROOR	MLACO	ProFS
1	Emotions	0.212 $\pm$ 0.018	0.212 $\pm$ 0.015	0.221 $\pm$ 0.014	0.226 $\pm$ 0.022	0.224 $\pm$ 0.025	0.244 $\pm$ 0.006	0.212 $\pm$ 0.012
2	Cal500	0.139 $\pm$ 0.007	0.138 $\pm$ 0.003	0.141 $\pm$ 0.001	0.142 $\pm$ 0.001	0.140 $\pm$ 0.001	0.143 $\pm$ 0.001	0.137 $\pm$ 0.003
3	Birds	0.057 $\pm$ 0.003	0.055 $\pm$ 0.006	0.054 $\pm$ 0.001	0.053 $\pm$ 0.002	0.056 $\pm$ 0.003	0.067 $\pm$ 0.002	0.053 $\pm$ 0.007
4	Image	0.179 $\pm$ 0.008	0.186 $\pm$ 0.012	0.185 $\pm$ 0.006	0.207 $\pm$ 0.012	0.200 $\pm$ 0.023	0.196 $\pm$ 0.010	0.183 $\pm$ 0.013
5	Scene	0.114 $\pm$ 0.017	0.111 $\pm$ 0.004	0.134 $\pm$ 0.008	0.125 $\pm$ 0.017	0.128 $\pm$ 0.030	0.122 $\pm$ 0.009	0.111 $\pm$ 0.003

TABLE II: Prediction performance of each conventional comparing algorithm (mean

\pm

std) in terms of Hamming Loss and Ranking Loss , where the best results are highlighted in boldface .

Evaluation metric	$F_{F}$	Critical value ( $\alpha=0.05$ )
Hamming loss	6.2124	2.239
Ranking loss	9.3295
One-error	21.1356
Coverage	9.3948
Average precision	13.2730

TABLE III: Summary of Friedman statistics

F_{F}

w.r.t. conventional methods

Panel of Figure 9 — Fig. 6: Comparison of ProFS and conventional comparing algorithms on the five evaluation metrics.

Panel of Figure 10 — Fig. 7: Comparison of ProFS against six conventional comparing algorithms with the Nemenyi test .

Id	Datasets	Hamming Loss ( $\downarrow$ )
Id	Datasets	ML2G	ML2G-S	MFSRD	ACML	MAHR	LSDF	ProML-S	ProML
1	Emotions	0.208 $\pm$ 0.013 $\circ$	0.211 $\pm$ 0.014 $\circ$	0.257 $\pm$ 0.031 $\bullet$	0.201 $\pm$ 0.010 $\circ$	0.216 $\pm$ 0.017 $\bullet$	0.184 $\pm$ 0.011 $\circ$	0.230 $\pm$ 0.010 $\bullet$	0.212 $\pm$ 0.012
2	Cal500	0.850 $\pm$ 0.002 $\bullet$	0.850 $\pm$ 0.002 $\bullet$	0.140 $\pm$ 0.030 $\bullet$	0.137 $\pm$ 0.004 $\circ$	0.967 $\pm$ 0.003 $\bullet$	0.138 $\pm$ 0.003 $\bullet$	0.147 $\pm$ 0.003 $\bullet$	0.137 $\pm$ 0.003
3	Birds	0.053 $\pm$ 0.005 $\bullet$	0.053 $\pm$ 0.005 $\bullet$	0.057 $\pm$ 0.048 $\bullet$	0.052 $\pm$ 0.007 $\circ$	0.058 $\pm$ 0.007 $\bullet$	0.047 $\pm$ 0.006 $\circ$	0.073 $\pm$ 0.006 $\bullet$	0.053 $\pm$ 0.007
4	Image	0.199 $\pm$ 0.008 $\bullet$	0.197 $\pm$ 0.007 $\bullet$	0.212 $\pm$ 0.066 $\bullet$	0.200 $\pm$ 0.004 $\bullet$	0.202 $\pm$ 0.007 $\bullet$	0.160 $\pm$ 0.009 $\circ$	0.201 $\pm$ 0.012 $\bullet$	0.183 $\pm$ 0.013
5	Scene	0.120 $\pm$ 0.005 $\bullet$	0.119 $\pm$ 0.003 $\bullet$	0.141 $\pm$ 0.025 $\bullet$	0.110 $\pm$ 0.002 $\circ$	0.129 $\pm$ 0.003 $\bullet$	0.080 $\pm$ 0.005 $\circ$	0.115 $\pm$ 0.003 $\bullet$	0.111 $\pm$ 0.003

TABLE IV: Prediction performance of each asymmetric-related comparing algorithm (mean

\pm

std) in terms of Hamming Loss and Ranking Loss , where

\bullet

\circ

indicates whether ProFS is superior/inferior to the other method.

Panel of Figure 12 — Fig. 8: Comparison of ProFS and asymmetric-related comparing algorithms on the five evaluation metrics.

Panel of Figure 13 — Fig. 9: Comparison of ProFS against seven asymmetric-related comparing algorithms with the Nemenyi test .

Evaluation metric	ProFS against ProF2S
Hamming loss	win[9.8e-4]
Ranking loss	win[4.9e-4]
One-error	win[2.2e-2]
Coverage	win[9.3e-3]
Average precision	win[3.9e-3]

TABLE V: Wilcoxon signed-ranks test for ProFS and ProF2S

Panel of Figure 15 — Fig. 10: Sensitivity analysis. The value of CV is based on the right $y$ -axis, while the other four metrics are based on the left one.

Panel of Figure 16 — Fig. 11: Convergence curves on various datasets.

Evaluation metric	$F_{F}$	Critical value ( $\alpha=0.05$ )
Hamming loss	25.5509	2.219
Ranking loss	37.2567
One-error	10.6099
Coverage	28.7916
Average precision	29.0565

TABLE VI: Summary of Friedman statistics

F_{F}

w.r.t. asymmetric-related methods

Fig. 12: Ablation results of the proposed method on five datasets in terms of five metrics.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Id	Datasets	One-Error ( $\downarrow$ )
Id	Datasets	ML-KNN	JFSC	MDFS	GLFS	GRROOR	MLACO	ProFS
1	Emotions	0.292 $\pm$ 0.030	0.310 $\pm$ 0.008	0.321 $\pm$ 0.020	0.320 $\pm$ 0.037	0.323 $\pm$ 0.057	0.368 $\pm$ 0.020	0.243 $\pm$ 0.058
2	Cal500	0.116 $\pm$ 0.015	0.118 $\pm$ 0.027	0.137 $\pm$ 0.019	0.128 $\pm$ 0.020	0.102 $\pm$ 0.006	0.130 $\pm$ 0.001	0.109 $\pm$ 0.030
3	Birds	0.361 $\pm$ 0.012	0.366 $\pm$ 0.042	0.380 $\pm$ 0.016	0.378 $\pm$ 0.022	0.408 $\pm$ 0.036	0.479 $\pm$ 0.016	0.333 $\pm$ 0.050
4	Image	0.350 $\pm$ 0.010	0.345 $\pm$ 0.033	0.362 $\pm$ 0.025	0.424 $\pm$ 0.053	0.415 $\pm$ 0.097	0.404 $\pm$ 0.034	0.342 $\pm$ 0.023
5	Scene	0.312 $\pm$ 0.048	0.278 $\pm$ 0.012	0.380 $\pm$ 0.031	0.357 $\pm$ 0.084	0.400 $\pm$ 0.165	0.303 $\pm$ 0.037	0.273 $\pm$ 0.009

Appendix

TABLE XII.1: Prediction performance of each conventional comparing algorithm (mean

\pm

std) in terms of One Error and Coverage , where the best results are highlighted in boldface .

Id	Datasets	One Error ( $\downarrow$ )
Id	Datasets	ML2G	ML2G-S	MFSRD	ACML	MAHR	LSDF	ProF2S	ProFS
1	Emotions	0.315 $\pm$ 0.065 $\bullet$	0.317 $\pm$ 0.087 $\bullet$	0.350 $\pm$ 0.154 $\bullet$	0.268 $\pm$ 0.048 $\bullet$	0.314 $\pm$ 0.055 $\bullet$	0.241 $\pm$ 0.012 $\bullet$	0.292 $\pm$ 0.055 $\bullet$	0.243 $\pm$ 0.058
2	Cal500	0.588 $\pm$ 0.214 $\bullet$	0.608 $\pm$ 0.188 $\bullet$	0.118 $\pm$ 0.031 $\bullet$	0.115 $\pm$ 0.033 $\bullet$	0.004 $\pm$ 0.005 $\circ$	0.126 $\pm$ 0.020 $\bullet$	0.295 $\pm$ 0.032 $\bullet$	0.109 $\pm$ 0.030
3	Birds	0.296 $\pm$ 0.032 $\circ$	0.295 $\pm$ 0.021 $\circ$	0.395 $\pm$ 0.121 $\bullet$	0.295 $\pm$ 0.039 $\circ$	0.389 $\pm$ 0.057 $\bullet$	0.429 $\pm$ 0.061 $\bullet$	0.335 $\pm$ 0.037 $\bullet$	0.333 $\pm$ 0.050
4	Image	0.369 $\pm$ 0.038 $\bullet$	0.362 $\pm$ 0.028 $\bullet$	0.435 $\pm$ 0.101 $\bullet$	0.348 $\pm$ 0.008 $\bullet$	0.373 $\pm$ 0.007 $\bullet$	0.277 $\pm$ 0.019 $\circ$	0.368 $\pm$ 0.041 $\bullet$	0.342 $\pm$ 0.023
5	Scene	0.297 $\pm$ 0.011 $\bullet$	0.297 $\pm$ 0.011 $\bullet$	0.406 $\pm$ 0.040 $\bullet$	0.258 $\pm$ 0.015 $\circ$	0.352 $\pm$ 0.012 $\bullet$	0.208 $\pm$ 0.017 $\circ$	0.283 $\pm$ 0.012 $\bullet$	0.273 $\pm$ 0.009

Appendix

TABLE XII.2: Prediction performance of each asymmetric-related comparing algorithm (mean

\pm

std) in terms of One Error and Coverage , where o/x indicates whether ProFS is superior/inferior to the other method.

Fig. XIII.1: Comparison between GMLL and ProML across five evaluation metrics. Here, the standard regularization term

\mathcal{R}(\boldsymbol{W})=\|\boldsymbol{W}\|_{F}^{2}

is employed.

Fig. XIII.2: Comparison between GMLL and ProML across five evaluation metrics. Here, the standard regularization term

\mathcal{R}(\boldsymbol{W})=\|\boldsymbol{W}\|_{1}

is employed.

Multi-Label Classification

Multi-label classification assigns several potentially related tags to each example, from medical findings and topics to objects and user interests.

See all 135 papers

Calibrated Disambiguation for Partial Multi-label Learning
Oct 13, 2026Zhuoming Li, Yuheng Jia, Mi Yu +1Multi-Label Classification Noisy-Label Learning
School of Computer Science and Engineering, Southeast University · China Telecom Cloud Computing Corporation, Beijing 100088, China
Feature-Label Modal Alignment for Robust Partial Multi-Label Learning
Apr 10, 2026Yu Chen, Weijun Lv, Yue Huang +4Multi-Label Classification Learning with Noisy Labels
School of Automation, Guangdong University of Technology, Guangzhou 510006, China · Shenzhen Key Laboratory of Visual Object Detection and Recognition, Harbin Institute of Technology, Shenzhen 518055, China · School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510275, China
Bringing Clustering to MLL: Weakly-Supervised Clustering for Partial Multi-Label Learning
Apr 10, 2026Yu Chen, Weijun Lv, Yue Huang +2Multi-Label Classification Learning with Noisy Labels
School of Automation, Guangdong University of Technology

Oct 13, 2026J/K move · Enter open · S save

Calibrated Disambiguation for Partial Multi-label Learning

Zhuoming Li, Yuheng Jia, Mi Yu, Zicong Miao

School of Computer Science and Engineering, Southeast University · China Telecom Cloud Computing Corporation, Beijing 100088, China

Multi-Label Classification Noisy-Label Learning Curriculum Learning

Open paper AskPDF arXiv

Partial multi-label learning (PML) aims to train a classifier on datasets whose instances are over-annotated with not only relevant labels but also irrelevant labels, which is common when datasets are collected from crowd-sourcing platform. Existing works primarily approach it from a curriculum learning perspective, leveraging the memorization effect to disambiguate noisy labels and produce robust predictions. However, these methods are based on non-adaptive weighting functions and lack theoretical guidance for optimal weighting. To overcome these issues, a calibrated disambiguation model named PML-CD is proposed. We first formulate the optimal weighting function for curriculum-based disambiguation, which is equivalent to the calibration of the model's predicted confidences, thus providing guidance for curriculum designing. To obtain the optimal weighting function from PML dataset during the training, a transferable calibrator is designed, which takes the histogram of positive samples' confidences as input, and outputs the optimal curriculum weighting for training. Prototype alignment regularization is also proposed to promote the model's performance. Experiments conducted on Pascal VOC, MS-COCO, NUS-WIDE and CUB have verified that our method outperforms existing state-of-the-art PML methods.

Abstract

Multi-Label Classification

Explore similar work

Calibrated Disambiguation for Partial Multi-label Learning

Feature-Label Modal Alignment for Robust Partial Multi-Label Learning

Bringing Clustering to MLL: Weakly-Supervised Clustering for Partial Multi-Label Learning