หัวใจสำคัญของการเรียนรู้ของเครื่องคือ การทำให้โมเดลมีความครอบคลุม"ทั่วไป" (general) มากขึ้นจากประสบกาณ์ที่ได้มา การทำให้ทั่วไปมากขึ้นนี้จะทำให้เครื่องสามารถพยากรณ์หรือทำงานกับตัวอย่างข้อมูลที่ไม่เคยเห็นมาก่อนได้อย่างแม่นยำมากขึ้น บางครั้ง ข้อมูลชุดสอนก็มาจากการสุ่มและผู้เรียนรู้จะต้องทำให้โมเดลมีความครอบคลุมทั่วไปมากขึ้นเพื่อจะได้ทำการพยากรณ์ข้อมูลใหม่ๆได้อย่างถูกต้องเพียงพอ

การวิเคราะห์เชิงคำนวณของการเรียนรู้ของเครื่อง และการวัดประสิทธิภาพการเรียนรู้ เป็นอีกสาขาหนึ่งทางวิทยาศาสตร์คอมพิวเตอร์สายทฤษฎีที่รู้จักกันในชื่อ ทฤษฎีการเรียนรู้เชิงคำนวณ อย่างไรก็ตาม ทฤษฎีก็ไม่สามารถรับประกันประสิทธิภาพของอัลกอริทึมได้เพราะข้อมูลนั้นมีจำกัดและอนาคตมีความไม่แน่นอน แต่ทฤษฎีก็สามารถบอกขอบเขตบนความน่าจะเป็นได้ว่า ประสิทธิภาพน่าจะอยู่ในช่วงใด นอกจากนี้ นักวิทยาศาสตร์ด้านนี้ยังได้ศึกษาดูต้นทุนทางเวลาและความเป็นไปได้ของการเรียนรู้ของเครื่องด้วย โดยการคำนวณที่ถือว่าเป็นไปได้ในการเรียนรู้นั้นจะต้องสามารถเรียนรู้ได้ในเวลาโพลิโนเมียล