When Can We Learn from Noisy Logical Data? Parameterized Complexity of Approximate Concept Fitting in Description Logics

Chang Lu, Yizheng Zhao, Renate Schmidt
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:3979-3998, 2026.

Abstract

SAT-based bounded fitting—searching for a smallest logical concept that correctly classifies all given examples—yields sample-efficient {PAC} learning for structured hypothesis classes such as description logic (DL) concepts. Yet this paradigm is fundamentally brittle: it demands realizability, and a single mislabeled example can render the underlying SAT instance unsatisfiable. While agnostic learnability follows from finite VC-dimension of bounded-size concept classes, the real barrier is computational: minimizing misclassifications over all concepts of bounded size is NP-hard. We study this barrier through parameterized complexity. We introduce ApxFit(k,t)—the problem of deciding whether there exists a DL concept of size at most $k$ that misclassifies at most $t$ out of $m$ examples—and establish a complexity landscape for fragments of $\mathcal{ALC}$ whose operator sets contain $\{\sqcap,\exists\}$ or $\{\sqcup,\forall\}$: the problem is W[2]-hard parameterized by concept size $k$ (even for $t{=}0$), yet lies in XP parameterized by outlier count $t$ for any fixed $k$. Algorithmically, we lift bounded fitting from SAT to partial weighted MAX-SAT and combine it with structural risk minimization, yielding the first noise-tolerant DL concept learner with formal agnostic generalization guarantees.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-lu26a, title = {When Can We Learn from Noisy Logical Data? Parameterized Complexity of Approximate Concept Fitting in Description Logics}, author = {Lu, Chang and Zhao, Yizheng and Schmidt, Renate}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {3979--3998}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/lu26a/lu26a.pdf}, url = {https://proceedings.mlr.press/v337/lu26a.html}, abstract = {SAT-based bounded fitting—searching for a smallest logical concept that correctly classifies all given examples—yields sample-efficient {PAC} learning for structured hypothesis classes such as description logic (DL) concepts. Yet this paradigm is fundamentally brittle: it demands realizability, and a single mislabeled example can render the underlying SAT instance unsatisfiable. While agnostic learnability follows from finite VC-dimension of bounded-size concept classes, the real barrier is computational: minimizing misclassifications over all concepts of bounded size is NP-hard. We study this barrier through parameterized complexity. We introduce ApxFit(k,t)—the problem of deciding whether there exists a DL concept of size at most $k$ that misclassifies at most $t$ out of $m$ examples—and establish a complexity landscape for fragments of $\mathcal{ALC}$ whose operator sets contain $\{\sqcap,\exists\}$ or $\{\sqcup,\forall\}$: the problem is W[2]-hard parameterized by concept size $k$ (even for $t{=}0$), yet lies in XP parameterized by outlier count $t$ for any fixed $k$. Algorithmically, we lift bounded fitting from SAT to partial weighted MAX-SAT and combine it with structural risk minimization, yielding the first noise-tolerant DL concept learner with formal agnostic generalization guarantees.} }
Endnote
%0 Conference Paper %T When Can We Learn from Noisy Logical Data? Parameterized Complexity of Approximate Concept Fitting in Description Logics %A Chang Lu %A Yizheng Zhao %A Renate Schmidt %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-lu26a %I PMLR %P 3979--3998 %U https://proceedings.mlr.press/v337/lu26a.html %V 337 %X SAT-based bounded fitting—searching for a smallest logical concept that correctly classifies all given examples—yields sample-efficient {PAC} learning for structured hypothesis classes such as description logic (DL) concepts. Yet this paradigm is fundamentally brittle: it demands realizability, and a single mislabeled example can render the underlying SAT instance unsatisfiable. While agnostic learnability follows from finite VC-dimension of bounded-size concept classes, the real barrier is computational: minimizing misclassifications over all concepts of bounded size is NP-hard. We study this barrier through parameterized complexity. We introduce ApxFit(k,t)—the problem of deciding whether there exists a DL concept of size at most $k$ that misclassifies at most $t$ out of $m$ examples—and establish a complexity landscape for fragments of $\mathcal{ALC}$ whose operator sets contain $\{\sqcap,\exists\}$ or $\{\sqcup,\forall\}$: the problem is W[2]-hard parameterized by concept size $k$ (even for $t{=}0$), yet lies in XP parameterized by outlier count $t$ for any fixed $k$. Algorithmically, we lift bounded fitting from SAT to partial weighted MAX-SAT and combine it with structural risk minimization, yielding the first noise-tolerant DL concept learner with formal agnostic generalization guarantees.
APA
Lu, C., Zhao, Y. & Schmidt, R.. (2026). When Can We Learn from Noisy Logical Data? Parameterized Complexity of Approximate Concept Fitting in Description Logics. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:3979-3998 Available from https://proceedings.mlr.press/v337/lu26a.html.

Related Material