Machine Learning Theory (CSCI599)

Spring 2017

This introductory graduate course will focus on developing the core concepts and techniques of machine learning theory. We will examine the inherent abilities and limitations of learning algorithms in well-defined learning models. Specifically, the course will focus on algorithmic problems in supervised learning. The goal of supervised learning is to infer a function from a set of labeled observations. We will study algorithms for learning Boolean functions from labeled examples in a number of models (online learning, PAC learning, SQ learning, learning with noise, etc.).

The course is primarily targeted toward graduate students who want to gain familiarity with algorithmic and statistical tools for machine learning. Advanced undergraduate students with sufficient mathematical maturity are welcome.

Course Information

Instructor: Ilias Diakonikolas

Teaching Assistant: Ehsan Emamjomeh-Zadeh

Lectures: Tuesdays 15:30-18:50, WPH 106.

Prerequisites

Mathematical maturity. Solid background in algorithms, linear algebra, and probability.

Course Outline

Here is an outline of the course material:

Online Learning: Winnow, Best Experts, Weighted Majority

PAC Learning, Relation to Online Learning, Occam's Razor

VC Dimension and Sample Complexity

Learning Decision Trees and DNFs

Boosting

Learning with Noise: Classification Noise, Malicious Noise

Statistical Query Learning

Distribution Dependent Learning, Fourier Transform

Computational Hardness of Learning

Learning with Membership and Equivalence Queries

Other Models of Learning: Semi-supervised Learning, Active Learning

Lectures

Lecture 1 (January 10) Introduction to machine learning theory. Supervised Learning. Introduction to Online Learning.

Lecture 2 (January 17) Online Learning: Winnow algorithm, Perceptron algorithm.

Lecture 3 (January 24) Generic Bounds for Online Learning (halving algorithm, weighted majority), VC dimension. Introduction to PAC learning.

Lecture 4 (January 31) PAC Learning model, online to PAC conversion, Occam's razor, application to learning sparse disjunctions.

Lecture 5 (February 7) Chernoff Bounds, proper versus improper learning, learning 3-term DNFs.

Lecture 6 (February 21) VC dimension, sample complexity of PAC learning.

Lecture 7 (February 28) Weak and Strong Learning. Introduction to Boosting: Schapire's boosting, Adaboost.

Lecture 8 (March 7) PAC Learning with Noise: Random Classification Noise, Malicious Noise.

Lecture 9 (March 21) Statistical Query (SQ) Learning: Simulating SQ Queries in the presence of Random Classification Noise.

Lecture 10 (March 28) Cryptographic Hardness of Learning.

Lecture 11 (April 4) Learning via PTF degree. Introduction to Fourier Analysis.

Lecture 12 (April 11) Fourier Analysis continued. PAC Learning under the Uniform Distribution: Low-Degree Algorithm and Applications.

Course Evaluation

Homework Assignments: There will be 4/5 homework assignments that will count for 60% of the grade. The assignments which will be proof-based, and are intended to be challenging. Collaboration and discussion among students is allowed, though students must write up their solutions independently.

First Homework: [pdf] (due on February 7)

Second Homework: [pdf] (due on February 28)

Third Homework: [pdf] (due on April 4)

Course Project: A part of the course (25% of the grade) is an independent project on a topic related to machine learning theory. Projects can be completed individually or in groups of two students.

The goal of the project is to become an expert in an area related to the class material, and potentially contribute to the state of the art. There are two aspects to the course project. The first is a literature review: Students must decide on a topic and a list of papers, understand these papers in depth, and write a survey presentation of the results in their own words. The second aspect is to identify a research problem/direction on the chosen topic, think about it, and describe the progress they make.

Students must consult with the instructor during the first half of the course for help in forming project teams, selecting a suitable project topic, and selecting a suitable set of research papers.

Students will be graded on the project proposal (5%), the progress report (5%), and the final report (15%).

The remaining part of the grade will be based on class participation (15%).

Readings

The textbook for this course is:

M. Kearns and U. Vazirani. An Introduction to Computational Learning Theory.

An additional textbook (available online) we will use is:

S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms.

Statement on Academic Conduct and Support Systems

Academic Conduct

Plagiarism - passing someone else's ideas as your own, either verbatim or recast in your own words - is a serious academic offense with serious consequences. Please familiarize yourself with the discussion of plagiarism in SCampus in Section 11, Behavior Violating University Standards https://scampus.usc.edu/1100-behavior-violating-university-standards-and-appropriate-sanctions/. Other forms of academic dishonesty are equally unacceptable. See additional information in SCampus and university policies on scientific misconduct, http://policy.usc.edu/scientific-misconduct/.

Discrimination, sexual assault, and harassment are not tolerated by the university. You are encouraged to report any incidents to the Office of Equity and Diversity http://equity.usc.edu/ or to the Department of Public Safety http://capsnet.usc.edu/department/department-public-safety/online-forms/contact-us. This is important for the safety whole USC community. Another member of the university community - such as a friend, classmate, advisor, or faculty member - can help initiate the report, or can initiate the report on behalf of another person. The Center for Women and Men http://www.usc.edu/student-affairs/cwm/ provides 24/7 confidential support, and the sexual assault resource center webpage sarc@usc.edu describes reporting options and other resources.

Support Systems

A number of USC's schools provide support for students who need help with scholarly writing. Check with your advisor or program staff to find out more. Students whose primary language is not English should check with the American Language Institute http://dornsife.usc.edu/ali, which sponsors courses and workshops specifically for international graduate students. The Office of Disability Services and Programs http://sait.usc.edu/academicsupport/centerprograms/dsp/home_index.html provides certification for students with disabilities and helps arrange the relevant accommodations. If an officially declared emergency makes travel to campus infeasible, USC Emergency Information http://emergency.usc.edu/ will provide safety and other updates, including ways in which instruction will be continued by means of blackboard, teleconferencing, and other technology.