I am an undergraduate student in applied mathematics with an interest in artificial intelligence. I am currently exploring topics where I could do research. Coming from a mathematical background I am interested in the question: Can we mathematically establish that a certain AI system has the ability to learn a task given some examples of how it should be done? I would like to know what research has been done on this topic and also what mathematical tools could be helpful in answering such questions.


Computational learning theory (CLT or COLT) is devoted to the mathematical and computational analysis of machine learning algorithms, so it is concerned with the learnability (i.e. generalization, bounds, efficiency, etc.) of certain tasks, given a learner (or a learning algorithm), a hypothesis space, data, etc.

CLT can be divided into (at least) two subfields: statistical learning theory (SLT) and algorithmic learning theory (ALT). The most famous CLT frameworks are PAC learning and the VC theory (which extends PAC learning to infinite-dimensional hypothesis spaces).

The following are some good resources you can use to get started with CLT (but you can find more here).

Here's a related question on this site: What sort of mathematical problems are there in AI that people are working on?.


@nbro has already provided a great answer, so i'll just supplement his answer with two specific results:

Minsky, in his 1969 book Perceptrons provided a mathematical proof that showed that certain types of neural networks (then called perceptrons) weren't able to compute a function called the XOR function, thus showing that the mind couldn't be implemented on strictly this structure. Minsky further argued that this result would generalize to all neural networks, but he failed to account for an architectural adaptation known as "hidden layers", which would allow for neural networks to compute the XOR function. This result isn't very relavant in modern times, but the immediate impact of his proof lead to several decades of people ignoring neural networks due to their perceived failings.

Another commonly cited result is the Universal approximation theorem, which shows that a sufficiently wide single layer neural network would be able to approximate (read as: arbitrarily close) any continuous function given appropriate activation function (iirc the activation needed to be non-linear).

You can also consider the research of MIRI, which in a sense is more of a "pure" study of AI than the examples listed above. Their Program Equilibrium via Provability Logic result was pretty interesting, the gist of that paper is that programs can learn to cooperate in a very simple game if they read each other's source code.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.