A teoria da aprendizagem computacional é a analise complexidade computacional do algoritimo de aprendizado de máquina. É a interseção da teoria da computação e aprendizado de máquina.
Os resultados teóricos em aprendizado de máquina tendem principalmente lidar com um tipo de aprendizado indutivo chamado aprendizado supervisionado. Em aprendizagem supervisionada, é dado amostras de um algoritmo que são rotulados de alguma forma útil. Por exemplo, as amostras podem ser as descrições de cogumelos, e as etiquetas podem ser ou não os cogumelos que são comestível. O algoritmo toma estas amostras previamente rotuladas e os usam para induzir um classificador. Este classificador é uma função que atribui etiquetas para as amostras incluindo as amostras que nunca foram vistos anteriormente pelo algoritmo. O objetivo do algoritmo de aprendizado supervisionado é otimizar alguma medida de desempenho, tais como minimizar o número de erros cometidos em novas amostras.
Além dos limites de desempenho, a teoria de aprendizagem computacional estuda a complexidade de tempo e viabilidade de aprendizagem. Na teoria da aprendizagem computacional, um cálculo é considerado viável se ele pode ser feito em um tempo polinomial. Existe dois tipos de resultados de complexibilidade de tempo:
Os resultados negativos muitas vezes dependem se geralmente se acredita, mas ainda a hipóteses não comprovadas, tais como:
Há várias abordagens diferentes da teoria de aprendizagem computacional. Estas diferenças são baseadas em fazer suposições sobre a Inferência princípios usados para generalizar a partir de dados limitados. Isto inclui diferentes definições Probabilidade (veja Probabilidade de frequência, Probabilidade epistemológica) e premissas diferentes sobre a geração de amostras.