View on GitHub

# CS260 [Fall2021] Machine Learning Algorithms

## Overview

This course introduces the foundational theory and algorithms of machine learning. The goal of this course is to endow the student with a) a solid understanding of the foundational concepts of machine learning, and b) the ability to derive and analyze machine learning algorithms. Topics to be covered include empirical risk minimization, PAC learning, Agnostic PAC learning, perceptron, linear regression, nearest neighbors, decision trees, boosting, structural risk minimization, surrogate loss functions, stochastic gradient descent, support vector machines, kernel methods, multi-class classification, and clustering etc. Slides and homework assignments will be released on CCLE and this website. Homework solutions will only be released on CCLE.

## Prerequisites

Two years of college mathematics, including calculus, linear algebra, probability and statistics, and the ability to write computer programs.

## Textbook

Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.

Python

## Logistics

• Time: Monday and Wednesday 12:00PM - 1:50PM
• Location: Zoom
• Instructor: Quanquan Gu (Email: qgu at cs dot ucla dot edu)
• Teaching Assistant:
• Zixiang Chen, Section 1A (Email: chenzx19 at cs dot ucla dot edu)
• Jiafan He, Section 1B (Email: jiafanhe19 at g dot ucla dot edu)
• Lucas Tecot, Section 1C (Email: lucastecot at gmail dot com)
• Office hours:
• The instructor’s office hour is Thursday 9:00am-10:00am, Zoom.
• The TA’s office hour is
• Zixiang Chen, Tuesday 12:00pm-2:00pm, Zoom.
• Jiafan He, Thursday 2:00pm-4:00pm, Zoom.
• Lucas Tecot, Monday and Wednesday 10:00am-11:00am, Zoom.
• Course Website: https://uclaml.github.io/CS260-Fall2021/

Grades will be computed based on the following factors:

• Homework 35%
• Quiz 5%
• Midterm 30%
• Final Project 30%

## Schedule

1 9/27 Introduction (slides)(slides_annotated) Chapter 1, 2.1
2 9/29 Empirical Risk Minimization, PAC Learning (slides)(slides_annotated) Chapter 2 HW1 Out
10/1 TA Session Week 1 (1A slides)(1B slides)(1C slides)
3 10/4 Agnostic PAC Learning (slides)(slides_annotated) Chapter 3
4 10/6 Uniform Convergence (slides)(slides_annotated) Chapter 4
10/8 TA Session Week 2 (1A slides)(1B slides)(1C slides)
5 10/11 Bias-Complexity Tradeoff (slides)(slides_annotated) Chapter 5, 11 HW1 Due, HW2 Out
6 10/13 VC dimension (slides) (slides_annotated) Chapter 6
10/15 TA Session Week 3 (1A slides)(1B slides)(1C slides)
7 10/18 VC dimension Cont. (slides) (slides annotated) Chapter 6, 28
8 10/20 Nonuniform Learnability (slides) (slides annotated) Chapter 7
10/22 TA Session Week 4 (1A slides)(1B slides)(1C slides)
9 10/25 Perceptron/Linear regression (slides)(slides_annotated) Chapter 9 HW2 Due, HW3 Out
10 10/27 Nearest Neighbors (slides) (slides annotated Chapter 19
10/29 TA Session Week 5 (1A slides)(1B slides)(1C slides)
11 11/1 Decision Trees (slides) (slides annotated) Chapter 18 Project Proposal Due
12 11/3 Boosting (slides)(slides annotated) Chapter 10
11/5 TA Session Week 6 (slides on CCLE-Week6) (1A slides)(1B slides)
11/8 Midterm Exam
13 11/10 Convex Learning and SGD (slides)(slides annotated) Chapter 12, 14 HW3 Due, HW4 Out
11/12 TA Session Week7 (1A slides)(1B slides)(1C slides)
14 11/15 Convex Learning and SGD (slides) (slides annotated) Chapter 12, 14
15 11/17 Regularization Stability (slides) (slides annotated) Chapter 13
11/19 TA Session Week 8 (1A slides)(1B slides)(1C slides)
16 11/22 Support Vector Machines (slides) (slides annotated) Chapter 15 HW4 Due, HW5 Out
17 11/24 Kernel Methods (slides) (slides annotated) Chapter 16
11/26 Thanksgiving holidays
18 11/29 Multi-class Classification (slides) (slides annotated) Chapter 17
19 12/1 Clustering (slides) (slides annotated) Chapter 22
12/3 TA Session Week10 (1A slides)(1B slides)(1C slides)
12/6     HW5 Due
12/8 Final Project Presentation
12/12     Project Report/Slides Due

Students are encouraged to read the UCLA Student Conduct Code for Academic Integrity.

## Homework

There will be about 5 homework assignments during the semester as we cover the corresponding material. Homework consists of both mathematical derivation, algorithm analysis and programming. Homework is required to be written in Latex. Latex homework template can be found here. The lowest homework score will be dropped for you.

Unless otherwise indicated, you may talk to other students about the homework problems but each student must hand in their own answers and write their own code in the programming part. You also must indicate on each homework with whom you collaborated and cite any other sources you use including Internet sites. Students cannot use old solution sets for this class or solution manual to the textbook under any circumstances.

Homework assignments will be submitted through Gradescope. You should have received an invite to Gradescope after you get enrolled in this class. Login via the invite, and submit the homework assignments on time.

Please submit your homework on time. Homework is worth full credit before the due date. It is worth zero credit after the due date.

## Exam

There will be one midterm. The exam is a take-home, 24-hours, open-book exam. If you need a makeup exam, please email us by Nov 1st.

## Quiz

There will be 6 in-class pop-up quiz for the purpose of reviewing the newly learned concepts. The quizzes are closed book and closed notes. No electronic aids or cheat sheets are allowed. We will drop the lowest quiz score for you.

## Project

Students are required to do a project in this class. The goal of the course project is to provide the students an opportunity to explore research directions in optimization or machine learning. Therefore, the project should be related to the course content. An expected project consists of • A novel and sound solution to an interesting problem • Comprehensive literature review and discussion • Thorough theoretical/experimental evaluation and comparisons with existing approaches

The best outcome of the project is a manuscript that is publishable in major machine learning conferences (COLT, ICML, NeurIPS, ICLR, AISTATS, UAI etc.) or journals (Journal of Machine Learning Research, Machine Learning).

Instruction can be found here, and template for proposal and final report can be found here.

Please refer to syllabus for more details.