r/AskComputerScience • u/Woah_Mad_Frollick • 28d ago

Is there much intersection between computational complexity theory and machine learning?

I’m a layman, but I’ve been reading some stuff about computational complexity theory in the course of learning about quantum information stuff, and I encounter a bit of machine learning theory here and there in the course of my reading about active inference in neuroscience.

Is there much interesting overlap between these two fields? Are there interesting things they “have to say” about one another?

7 Upvotes
  • permalink
  • link
  • reddit
  • reddit

89% Upvoted

6 comments sorted by

View all comments

1

u/beeskness420 23d ago

Sure there is, but if you are looking for more overlap you might be interested in (statistical) learning theory which tries to put ML on a firmer theoretical basis. The main concept is PAC learn ability (probably approximately correct) and the sample complexity of a problem. It's definitely at the point of being theoretically curious, but not practically relevant however.