May 2023.- “Find a witness or shatter: the landscape of computable PAC learning” is the title of the work of the IMFD researchers and international postdocs from the Institute of Mathematical and Computational Engineering of the P. Universidad Católica de Chile (IMC UC), Valentino Delle Rose, Alexander Kozachinskiy and Tomasz Steifer, together with the academic from the same unit, Cristóbal Rojas, will present at the Conference on Learning Theory (COLT), considered one of the most important in the world in machine learning and artificial intelligence theory.

Every year, since 1988, the Association for Computational Learning (ACL, for its acronym in English) organizes this event, which will celebrate its 36th version in Bangalore, India next July and, as on previous occasions, considers the presentation of the best research in this field.

As the ACL points out, learning theory is a discipline “dedicated to the study of the design and analysis of machine learning algorithms. In particular, such algorithms aim to make accurate predictions or representations based on observations. For this reason, adds the entity, COLT emphasizes “rigorous mathematical analysis using techniques from various related fields, such as probability, statistics, optimization, information theory and geometry.” In addition, ACL indicates, although it has theoretical roots, learning theory is also notable for placing “a strong emphasis on efficient computing.”

This is precisely the focus of the research entitled “Find a witness or shatter: the landscape of computable PAC learning”, which addresses a theoretical framework known as “Probably approximately correct learning” or “PAC learning”. Alexander Kozachinskiy, PhD in Mathematics from Moscow State University, Russia, and who is also a postdoctoral researcher at IMFD and the National Center for Artificial Intelligence (CENIA), explains that PAC learning is a milestone in learning theory. “He delivers, in a given framework, a brilliant and clean characterization of what can and cannot be learned. However, it does this at the cost of ignoring the computational cost of learning. The theory that deals with that cost is called ‘computational learning theory’. Our paper contributes to that field and COLT is the most important place to show results like these”, he indicates.

Cristóbal Rojas, who is also a researcher at Cenia, adds that PAC learning is a framework where “it is possible to clearly establish what the general learning problem consists of, which makes it possible to study it from a mathematical point of view. In this framework, the input to the general problem consists of a data set and a class of possible models, and the goal is to test whether that class is good for that data. If it is, it means that within the class there are functions that approximate well the observed data, and that have a high probability of correctly approximating data not yet observed. In addition, there must be an algorithm that looks at the data and finds the function that best ‘explains’ it in this sense”.

In this area of research, adds the academic, there are several key elements: “First, how much data does the algorithm have to look at, how efficient is it, and does it have access to the amount of data necessary to find the function. There was a theory that characterized the relationship between those parameters, but it didn’t care about the part where the operation that looks at the data and finds the function that approximates it has to be an algorithm; it was made in an abstract framework where that operation was performed with any function”. More recently, says Rojas, they began to study what happens when they “demand that this operation can be calculated by an algorithm. There the panorama was a bit complicated and there were partial results; there was not a complete understanding of the relationship between the different parameters. And in particular there were three open questions, which had come up in previous studies presented at the same COLT conference.”

According to the IMC UC professor, what the research team did was “answer these questions and with that close the theory regarding what is called ‘computable PAC learning’, which is the same theory as before, but taking into account the fact that we want it to be able to be done by algorithms.” Rojas adds that the work mainly serves as a conceptual understanding of “how different parameters are related.” So, if one wants to study a specific problem, this works as a guide for the modeling decisions that have to be made. In addition, it sets a framework to have reasonable expectations regarding what one expects from the specific application.

The contribution of postdocs

Beyond having achieved that the paper was accepted at a conference of the level of COLT 2023, Cristóbal Rojas highlights the contribution of the team of postdoctoral students from Russia, Italy and Poland. “It was a job in which they established themselves. Together we found the theme and the questions. Then we got to work and it turned out that it was just a topic in which we felt comfortable. More than anything, I encouraged them to continue and contributed to some things, in addition to helping in writing the final draft. But the hard work was done by them”, comments the academic.

In this regard, Alexander Kozachinskiy points out that in the group that prepared the paper there are people with “training in different areas, such as dynamic systems, logic and Kolmogorov complexity. Also, we are learning about machine learning and artificial intelligence in an unconventional way. It is interesting and challenging and I hope that this will influence the research in a positive way.”

One of the additional objectives of the study is to contribute positively to the organizations where postdoctoral students work. Like Alexander, Valentino Delle Rose is part of the IMFD and CENIA, while Tomasz Steifer is a member of the IMFD. “The expectation of these centers is that part of the work they do pays tribute to the objectives of these institutions, which at first are outside the basic training that they bring. In a way, we are asking you to step out of your comfort zone and start looking at these issues. In fact, we were lucky to find what we analyzed in the paper, because it is right between what they and I know well and this learning theory or machine learning that is one of the topics of all these institutes”, explains Rojas. “The idea is to continue finding bridges and connections to get more involved in this new subject, learn more and find a way to export our expertise to that field. Also, the more we move towards that side, the more interesting it will become for students because they are the topics that are in fashion and are behind all the new technologies”.

The relevance of COLT

The fact that the study prepared by the postdoctoral students and the academic Cristóbal Rojas has been accepted at COLT is a significant achievement, says Cristóbal Guzmán, IMC UC professor and PhD in algorithms, combinatorics and optimization. “Compared to events like, for example, NeurIPS, COLT is more of a niche conference. Only about 100 papers are accepted and the participants do not exceed 500, so the quality of the publications is much higher. In my experience, it is much more difficult to have a paper accepted at COLT than at other conferences, since there is a particular requirement regarding the theoretical contribution of a paper”, comments the researcher, who is a senior member of the COLT program committee

IMC UC