IMFD students present papers at COLT
May 2023.- “Find a witness or shatter: the landscape of computable PAC learning” is the title of the work by IMFD researchers and international postdoctoral fellows 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 faculty member of 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 theory and artificial intelligence.
Every year, since 1988, the Association for Computational Learning (ACL) organizes this event, which will hold its 36th edition in Bangalore, India next July and, as in previous occasions, features presentations of the best research in the field.
As the ACL notes, 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, the organization adds, COLT places emphasis on “rigorous mathematical analysis using techniques from various related fields, such as probability, statistics, optimization, information theory, and geometry”. Furthermore, ACL notes, while learning theory has theoretical roots, it also stands out for placing “a strong emphasis on efficient computation”.
Precisely, that is the focus of the research titled “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. “It provides, within a given framework, a brilliant and clean characterization of what can be learned and what cannot be learned. However, it achieves 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 venue to showcase results like these”, he states.
Cristóbal Rojas, who is also a researcher at Cenia, adds that PAC learning is a framework where “one can clearly establish what the general learning problem consists of, which allows it to be studied from a mathematical point of view. In this framework, the input of the general problem consists of a dataset and a class of possible models, and the goal is to assess whether that class is good for that data. If it is, it means that within the class there are functions that approximate the observed data well, and that have a high probability of correctly approximating data not yet observed. Furthermore, there must exist an algorithm that looks at the data and finds the function that best ‘explains’ it in this sense”.
In this research area, the academic adds, there are several key elements: “First, how much data the algorithm has to look at, how efficient it is, and whether it has access to the amount of data needed to find the function. There was a theory that characterized the relationship between those parameters, but it did not concern itself with the fact that the operation that looks at the data and finds the function that approximates it has to be an algorithm; it was formulated within an abstract framework where that operation was performed by any function whatsoever”. More recently, Rojas notes, researchers began to study what happens when it is “required that this operation be computable by an algorithm. There the picture became somewhat more complicated and there were partial results; there was no complete understanding of the relationship between the different parameters. And in particular there were three open questions, which had appeared in previous studies presented at the same COLT conference”.
According to the IMC UC faculty member, what the team of researchers did was “answer those questions and thereby 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 achievable by algorithms”. Rojas adds that the work serves mainly as a conceptual understanding of “how different parameters relate to each other”. So, if one wants to study a specific problem, this serves as a guide for the modeling decisions that need to be made. In addition, it establishes a framework for having reasonable expectations regarding what one expects from the specific application”.
The contribution of the postdoctoral fellows
Beyond having gotten the paper accepted at a conference of the caliber of COLT 2023, Cristóbal Rojas highlights the contribution of the team of postdoctoral students from Russia, Italy, and Poland. “It was a project in which they came together as a team. Together we found the topic and the questions. Then we got to work and it turned out to be exactly a topic we felt comfortable with. I mostly encouraged them to keep going and contributed on a few things, in addition to helping write the final draft. But they did the hard work”, the academic comments.
In this regard, Alexander Kozachinskiy notes that the group that produced the paper includes people with “training in different areas, such as dynamical systems, logic, and Kolmogorov complexity. Moreover, we are learning about machine learning and artificial intelligence in an unconventional way. It’s interesting and challenging, and I hope it has a positive influence on the research”.
One of the additional goals of the study is for it to positively contribute to the organizations where the postdoctoral students work. Like Alexander, Valentino Delle Rose is part of IMFD and CENIA, while Tomasz Steifer is a member of IMFD. “The expectation of these centers is that part of the work they do contributes to the goals of these institutions, which initially lie outside the base training they bring. In a way, we are asking them to step outside their comfort zone and start studying these problems. In fact, we were lucky to find what we analyze in the paper, because it sits right at the intersection of what they and I know well and this learning theory or machine learning, which is one of the topics of all these institutes”, Rojas explains. “The idea is to keep finding bridges and connections to get further into this new topic, learn more, and find ways to export our expertise into that field. Also, the more we move in that direction, the more interesting it will become for students, because these are the trending topics behind all the new technologies”.
The relevance of COLT
The fact that the study produced by the postdoctoral students and academic Cristóbal Rojas was accepted at COLT is a significant achievement, notes Cristóbal Guzmán, IMC UC faculty member and PhD in algorithms, combinatorics, and optimization. “Compared to events such as, for example, NeurIPS, COLT is more of a niche conference. Only around 100 papers are accepted and there are no more than 500 participants, so the quality of the publications is much higher. In my experience, it is much harder to get a paper accepted at COLT than at other conferences, since there is a particular requirement regarding the theoretical contribution of a work”, comments the researcher, who is a senior member of the COLT program committee.
Source: IMC UC