Descriptive Complexity of Learning

• Applicant: Professor Dr. Martin Grohe
• Subject Area: Theoretical Computer Science
• Term: from 2017 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 389872375

Descriptive complexity theory explains the computational complexity ofalgorithmic problems in terms of the language resources required todefine the problems. In this project, we extend the descriptivecomplexity approach to machine learning problems: we aim to understandefficient learnability in terms of the descriptive complexity of themodel, that is, the language resources required to define thehypotheses to be learned.This work may serve as a foundation for a more declarative approach tomachine learning, where the model (the hypothesis class) isseparated from the solver (the optimisation algorithm computing thebest hypothesis).Applications of our framework can most likely be found in logic-affineareas such as automated verification and database systems, and we willexplore such applications.

• DFG Programme: Research Grants