In this course we will look at a handful of
ubiquitous algorithms in machine learning. We will cover several classical tools in
machine learning but more emphasis will be given to recent
advances and developing efficient and provable algorithms for
learning tasks. A tentative syllabus/schedule can be found below; the topics
may change based on student interests as well.

**Class transcript:** Keep in mind that the transcript only shows what is actually written in class and are not complete
notes as such.

Lecture notes for multiplicative weights method (lectures 3,4).

Lecture notes for gradient descent (lectures 8,9).

We will use Piazza for the class. Class page is here. You can singup here.

**Assignments:**

Assignment 1. Due October 18th, 10PM via Gradescope.

Assignment 2. Due November 8th, 10PM via Gradescope.

Assigment 3. Due November 21st, 10PM via Gradescope.

Assignment 4. Due December 11, 10PM via Gradescope.

**Prerequisites:** You ** need**
background in linear algebra, probability theory, and algorithms
(all at a typical undergraduate upper-division level) to make the
class fun and interesting for you as well as for me. You can judge
your background with this problem set (not to be submitted). If you have
doubts about this please talk to me right away.

**Course work:** We will have four assignments: 1,2,3 -
16; 4 - 20.

Mid-term - 32. In class on November 20. There will be no make up exams for the class; you have to let me know in the first two weeks if the date is an issue for you.

Optional project: If you so desire, you can substitute the last assignment for an approved project. This can either be a cohesive literature survey of a specific topic, a research project, or an experimental project investigating different algorithms on a specific learning problem; it can even be in the form of participating in some machine learning competitions. Projects finding connections between the course material and their own research interests are strongly encouraged.

The project topic has to be finalized before Nov 29th and will be evaluated on the basis of a five page (one-sided) report (Due by December 14th 5PM PST) which is expected to be at the level of a conference submission. The project can be done in teams of up to two students (the work will have to scale accordingly).

** Assignment submission:** We will use Gradescope for assignments and
they have to be submitted by 10PM on their due date. This
is extremely helpful both for me as well as for you -
you'll get better feedback and will have a digital record of
all your assignments that you can refer to later. Things to keep in mind: 1) Within two weeks of the course,
you should receive a registration link from Gradescope. If you don't
receive it before the first homework, contact me immediately;
this will give you access to the website. 2) Watch this one-minute
video with complete instructions. Follow them to the letter! The
simple guidelines make the process considerably smoother. 3) Make
sure you start each problem of an assignment on a new page. 4) To
generate a PDF scan of the assignments, you can follow the instructions
here; you can also use the
scanners in the library.

**Resources**: There is no required course text. The following links would be useful:

Sanjeev Arora's course.

Elad Hazan's course.

Ankur Moitra's course.

Draft of Foundations of Data Science by Blum, Hopcroft and Kannan.

Amit Chakrabarti's lecture notes on streaming algorithms.

Links to appropriate papers or other online material (typically other lecture notes) will be provided for each lecture.

**Hours & Location**: MW 2-3:50, Boelter Hall
5272. Office hours: Wednesday 10:30 - 11:30, BH 3732H.

The following is a tentative list of topics to be covered.

**Academic honesty**: The students are expected to fully
abide by UCLA's student conduct policies,
including Section 102.01 on academic honesty. You will find a wealth
of helpful materials here,
including the Student
Guide to Academic Integrity. Academic dishonesty will be promptly
reported to the Dean of Students' Office for adjudication and
disciplinary action. Remember, cheating will have significant and
irrevocable consequences for your academic record and professional
future. Please don't cheat.

While collaboration with other students on assignments is fine, you should clearly mention the collaborators. You should make your own slides and when you use content from another source, you should explicitly state so. Under no circumstances may you use code directly from resources on the web without explicitly citing the source.

Lecture notes for multiplicative weights method (lectures 3,4).

Lecture notes for gradient descent (lectures 8,9).

We will use Piazza for the class. Class page is here. You can singup here.

Assignment 1. Due October 18th, 10PM via Gradescope.

Assignment 2. Due November 8th, 10PM via Gradescope.

Assigment 3. Due November 21st, 10PM via Gradescope.

Assignment 4. Due December 11, 10PM via Gradescope.

Mid-term - 32. In class on November 20. There will be no make up exams for the class; you have to let me know in the first two weeks if the date is an issue for you.

Optional project: If you so desire, you can substitute the last assignment for an approved project. This can either be a cohesive literature survey of a specific topic, a research project, or an experimental project investigating different algorithms on a specific learning problem; it can even be in the form of participating in some machine learning competitions. Projects finding connections between the course material and their own research interests are strongly encouraged.

The project topic has to be finalized before Nov 29th and will be evaluated on the basis of a five page (one-sided) report (Due by December 14th 5PM PST) which is expected to be at the level of a conference submission. The project can be done in teams of up to two students (the work will have to scale accordingly).

Sanjeev Arora's course.

Elad Hazan's course.

Ankur Moitra's course.

Draft of Foundations of Data Science by Blum, Hopcroft and Kannan.

Amit Chakrabarti's lecture notes on streaming algorithms.

Links to appropriate papers or other online material (typically other lecture notes) will be provided for each lecture.

The following is a tentative list of topics to be covered.

Learning theory: what and how? (2 lectures)

How to model learning?

PAC model and Generalization

Towards tractable learning models

PAC model and Generalization

Towards tractable learning models

Linearity: the swiss-army
knife (3 lectures)

Best-fit subspaces, low-rank approximations, and Singular Value Decomposition

Applications of SVD

Applications of SVD

Multiplicative weights and
online learning (2 lectures)

Online optimization and regret minimization.

Optimization: the work-horse of learning (3 lectures)

Convexity primer

Learning as optimization

Gradient descent

Stochastic gradient descent

Accelrated gradient descent methods

Learning as optimization

Gradient descent

Stochastic gradient descent

Accelrated gradient descent methods

Regression and its analysis
(2 lectures)

How and when to regress?

Graphical Models (3 lectures)

Basic models and algorithms

Neural networks (2 lectures)

Constant-depth circuits, back propogation, and limitations

The reemergence of neural nets

The reemergence of neural nets

Algorithms for massive data
sets (2 lectures)

Streaming algorithms

Miscellaneous/buffer (1 lecture)

While collaboration with other students on assignments is fine, you should clearly mention the collaborators. You should make your own slides and when you use content from another source, you should explicitly state so. Under no circumstances may you use code directly from resources on the web without explicitly citing the source.