在計算機科學中，計算學習理論（或只是學習理論）是人工智能的一個子領域，致力于研究機器學習算法的設計和分析。

機器學習的理論成果主要涉及一種被稱為監督學習的歸納學習。在監督學習中，一個算法被賦予了以某種有用方式標記的樣本。例如，樣本可能是對蘑菇的描述，而標簽可能是蘑菇是否可以食用。該算法采用這些先前標記的樣本，并使用它們來誘導一個分類器。這個分類器是一個為樣本分配標簽的函數，包括算法以前沒有見過的樣本。監督學習算法的目標是優化一些性能指標，如最小化在新樣本上的錯誤數量。除了性能界限外，計算學習理論還研究學習的時間復雜性和可行性。在計算學習理論中，如果一個計算可以在多項式時間內完成，就被認為是可行的。有兩種時間復雜性的結果。正面結果--表明某類函數可以在多項式時間內學習。負面結果--表明某些類別不能在多項式時間內學習。負面結果往往依賴于普遍認為但尚未證實的假設，如：。計算復雜性--P≠NP（P與NP的問題）；密碼學--存在單向函數。