Abstract

Two central challenges in multi-label learning are the high cost of acquiring fully labeled data and the need to enforce hard logical constraints among labels. In many practical scenarios, however, complementary labels – i.e., labels indicating classes to which a sample does not belong – are available at a significantly lower cost, motivating the development of methods that learn efficiently and effectively from such weak supervision. At the same time, it is often necessary to ensure that model predictions comply with domain-specific requirements expressed as hard logical constraints. Enforcing these constraints is typically computationally demanding, which calls for approaches that are both effective and efficient. To the best of our knowledge, no prior work has jointly examined – both from practical and theoretical perspectives – the problem of learning from complementary labels in the presence of hard logical constraints, which is the focus of this work. In particular, we show through both empirical and theoretical analyses that complementary labels and hard logical constraints constitute two forms of weak supervision that can be simultaneously leveraged during learning. From an empirical standpoint, we systematically investigate different combinations of multi-label complementary learning methods and constraint-aware strategies across multiple datasets and learning algorithms. We vary the number of samples, the number of complementary labels, and the strength of the constraints, and evaluate performance using several metrics, including accuracy, number of constraint violations, and informativeness of the constraints. From a theoretical standpoint, we derive generalization bounds based on statistical learning theory to characterize how the sample size, the number of complementary labels, and the strength of constraint information jointly influence generalization performance.

Short Bio

Luca Oneto, born in 1986 in Rapallo, Italy, completed his BSc and MSc in Electronic Engineering at the University of Genoa in 2008 and 2010, respectively. In 2014, he earned his PhD in Computer Engineering from the same institution. From 2014 to 2016, he worked as a Postdoc in Computer Engineering at the University of Genoa, where he then served as an Assistant Professor from 2016 to 2019. Luca co-founded the company ZenaByte s.r.l. in 2018. In 2019, he became an Associate Professor in Computer Science at the University of Pisa, and from 2019 to 2024, he held the position of Associate Professor in Computer Engineering at the University of Genoa. Currently, he is a Full Professor in Computer Engineering at the University of Genoa. He has been coordinator and local responsible in numerous industrial, H2020, and Horizon Europe projects. He has received prestigious recognitions, including the Amazon AWS Machine Learning Award and the Somalvico Award for the best young AI researcher in Italy. His primary research interests lie in Statistical Learning Theory and Trustworthy AI. Additionally, he focuses on data science, utilizing and improving cutting-edge machine learning and AI algorithms to tackle real-world problems.