Title: Progressive Purification for Instance-Dependent Partial Label Learning. Abstract: Partial-label learning (PLL) aims to train multi-class classifiers from instances with partial labels (PLs)---a PL for an instance is a set of candidate labels where a fixed but unknown candidate is the true label. In the last few years, the instance-independent generation process of PLs has been extensively studied, on the basis of which many practical and theoretical advances have been made in PLL, while relatively less attention has been paid to the practical setting of instance-dependent PLs, namely, the PL depends not only on the true label but the instance itself. In this paper, we propose a theoretically grounded and practically effective approach called progressive purification (POP) for instance-dependent PLL: in each epoch, POP updates the learning model while purifies each PL by progressively moving out false candidate labels for the next epoch of the model training. Theoretically, we prove that POP enlarges the region where the model is reliable by a promising rate, and eventually approximates the Bayes optimal classifier with mild assumptions; technically, POP is flexible with arbitrary losses and compatible with deep networks, so the previous advanced PLL losses can be embedded in it and the performance is often significantly improved.