Designed mainly as an advanced (and more theoretically-oriented) version of CSC665 Principles of Machine Learning, students will learn, via the lens of mathematical foundations, how and when machine learning is possible/impossible as well as various algorithms with theoretical guarantees. Specifically, the course offers mathematical formulation of learning environments (e.g., stochastic and adversarial worlds with possibly limited feedback), fundamental limits of learning in these environments, various algorithms concerning sample efficiency, computational efficiency, and generality. Throughout, students will not only learn fundamental mathematical tools upholding the current understanding of machine learning systems in the research community but also develop skills of adapting these techniques to their own research needs such as developing new algorithms.
Linear Algebra or equivalent:
You will need to understand the relationship between linear operators, linear transformations, and matrices
We will make repeated use of matrix decompositions such as the SVD
Multivariate Calculus or equivalent:
Basic probability theory and statistics:
You will need to understand (conditional) expectation and (conditional) independence of random variables.
You will need to have basic concepts on concentration of measures.
You will need a basic programming skills for math such as matlab, julia, or python with numpy/scipy.
Chicheng Zhang, GS 720, chichengz@cs.arizona.edu
Office hour: TBD; The instructor is also available by appointment.
D2L: https://d2l.arizona.edu/d2l/home/824748
Lectures, individual assignments, written exams, projects, in-class discussions.
A successful student will be able to explain the key learning theory concepts and analyze the lower and upper bounds of various machine learning tasks:
For a more granular description of the learning objectives, see the week-by-week schedule and the description of the assignments below.
This course is far from a complete survey of the concurrent topics on machine learning theory due to the sheer volume of recent developments and the fact that those topics require a deep understanding of concepts and fluency in mathematical techniques. That said, this course covers key topics that not only serve as building blocks of advanced machine learning theory but is also relevant in modern research so that the students can directly adapt learned topics to their own research. Students are expected to dedicate a significant amount of time on understanding mathematical concepts and skills outside the classroom.
The expected learning outcomes of the course are:
The UA’s policy concerning Class Attendance, Participation, and Administrative Drops is available at http://catalog.arizona.edu/policy/class-attendance-participation-and-administrative-drop. The UA policy regarding absences for any sincerely held religious belief, observance or practice(http://policy.arizona.edu/human-resources/religious-accommodation-policy) will be accommodated where reasonable. Absences pre approved by the UA Dean of Students (or dean’s designee) will be honored. See the dean of students’s website(https://deanofstudents.arizona.edu/absences) for details.
If you register late for this class, contact me as soon as you do. You will be expected to submit all missed assignments within a week of your registration. It is your responsibility to catch up to the class content.
We will use D2L for communications and discussion. Make sure your D2L account is up to date - class announcements are sent through the website.
The required textbook is “Understanding Machine Learning: From Theory to Algorithms” by Shai Shalev-Shwartz and Shai Ben-David, available at https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning for personal use.
There will be a take-home midterm exam given out on 10/10 (Thu). For the final exam and the project, see the next section.
There will be a total of 7 programming/written assignments paced at around one assignment per week, skipping weeks for the midterm and final. Each assignment will be due at least one week after it is posted. The final project report is due on the last day of class.
A0: Calibration homework
A1: Concentration of measure; the PAC learning framework
A2: VC theory; Rademacher complexity
A3: Support vector machine; boosting
A4: Regularization and stability
A6: Online Convex Optimization
A7: Multi-armed bandits and linear bandits
This course will have a comprehensive written open-book final examination, on 12/18 from 1pm-3pm at PAS 414. Information on the final exam regulations and schedule: https://www.registrar.arizona.edu/courses/final-examination-regulations-and-information http://www.registrar.arizona.edu/schedules/finals.htm
The instructing staff will grade your assignments, project, midterms, and the final exam on a scale from 0 to 100, with the following weights: Assignments: 50% Project: 15% Midterm Exam: 15% Final Exam: 20%
The final grade in the course of the best of a per-class grading curve and overall performance: 90% or better: A; 80% or better: B; 70% or better: C; 60% or better: D; below 60%: F.
Graded homework will be returned before the next homework is due. The homework is due in 10 days, and will be returned to students before the next homework is due. Exams will be returned within two weeks. Grading delays beyond promised return-by dates will be announced as soon as possible with an explanation for the delay.
As a rule, homework will not be accepted late except in case of documented emergency or illness. You may petition the professor in writing for an exception if you feel you have a compelling reason for turning work in late.
Requests for incomplete (I) or withdrawal (W) must be made in accordance with University policies, which are available at http://catalog.arizona.edu/policy/grades-and-grading-system#incomplete and http://catalog.arizona.edu/policy/grades-and-grading-system#Withdrawal, respectively. Dispute of Grade Policy: If you wish to dispute your grade for an assignment, midterm or project, you have two weeks after the grade has been turned in. In addition, even if only you dispute one portion of the grading for that unit, I reserve the right to revisit the entire unit (assignment, midterm, or project).
See Schedule page for details.
The Department of Computer Science is committed to providing and maintaining a supportive educational environment for all. We strive to be welcoming and inclusive, respect privacy and confidentiality, behave respectfully and courteously, and practice intellectual honesty. Disruptive behaviors (such as physical or emotional harassment, dismissive attitudes, and abuse of department resources) will not be tolerated. The complete Code of Conduct is available on our department web site. We expect that you will adhere to this code, as well as the UA Student Code of Conduct, while you are a member of this class.
To foster a positive learning environment, students and instructors have a shared responsibility. We want a safe, welcoming, and inclusive environment where all of us feel comfortable with each other and where we can challenge ourselves to succeed. To that end, our focus is on the tasks at hand and not on extraneous activities (e.g., texting, chatting, reading a newspaper, making phone calls, web surfing, etc.). Students are asked to refrain from disruptive conversations with people sitting around them during lecture. Students observed engaging in disruptive activity will be asked to cease this behavior. Those who continue to disrupt the class will be asked to leave lecture or discussion and may be reported to the Dean of Students. Some learning styles are best served by using personal electronics, such as laptops and iPads. These devices can be distracting to other learners. Therefore, students who prefer to use electronic devices for note-taking during lecture should use one side of the classroom.
The UA Threatening Behavior by Students Policy prohibits threats of physical harm to any member of the University community, including to oneself. See http://policy.arizona.edu/education-and-student-affairs/threatening-behavior-students.
This course will contain material of a mature nature, which may include explicit language, depictions of nudity, sexual situations, and/or violence. The instructor will provide advance notice when such materials will be used. Students are not automatically excused from interacting with such materials, but they are encouraged to speak with the instructor to voice concerns and to provide feedback.
At the University of Arizona we strive to make learning experiences as accessible as possible. If you anticipate or experience physical or academic barriers based on disability or pregnancy, you are welcome to let me know so that we can discuss options. You are also encouraged to contact Disability Resources (520-621-3268) to explore reasonable accommodation. If our class meets at a campus location: Please be aware that the accessible table and chairs in this room should remain available for students who find that standard classroom seating is not usable.
Students are encouraged to share intellectual views and discuss freely the principles and applications of course materials. However, graded work/exercises must be the product of independent effort unless otherwise instructed. Students are expected to adhere to the UA Code of Academic Integrity as described in the UA General Catalog. See http://deanofstudents.arizona.edu/academic-integrity/students/academic-integrity. The University Libraries have some excellent tips for avoiding plagiarism, available at http://new.library.arizona.edu/research/citing/plagiarism.
The University is committed to creating and maintaining an environment free of discrimination; see http://policy.arizona.edu/human-resources/nondiscrimination-and-anti-harassment-policy. Our classroom is a place where everyone is encouraged to express well-formed opinions and their reasons for those opinions. We also want to create a tolerant and open environment where such opinions can be expressed without resorting to bullying or discrimination of others.
UA Academic policies and procedures are available at http://catalog.arizona.edu/policies Student Assistance and Advocacy information is available at http://deanofstudents.arizona.edu/student-assistance/students/student-assistance
Please see http://www.registrar.arizona.edu/personal-information/family-educational-rights-and-privacy-act-1974-ferpa?topic=ferpa for information on confidentiality of student records. This has concrete consequences for you if you give my name as a reference! In other words, if you intend to give my name as a reference, please contact me ahead of time so we can discuss.
Information contained in the course syllabus, other than the grade and absence policy, may be subject to change with advance notice, as deemed appropriate by the instructor.
Where to go, who to call if you’re in crisis:
Resources for sexual assault, relationship violence, and stalking.
24-Hour Hotlines:
Crisis Text Line: Text HOME to 741741 from anywhere in the United States, anytime, about any type of crisis. A live, trained Crisis Counselor receives the text and responds, all from a secure online platform. Find out more about how it works at crisistextline.org.
Suicide Prevention for LGBTQ Youth through the Trevor Project:
Veterans’ Suicide Prevention Lifeline: 1-800-273-TALK (1-800-273-8255)
SAMHSA Treatment Referral Hotline (Substance Abuse): 1-800-662-HELP (1-800-662-4357)
National Sexual Assault Hotline: 1-800-656-HOPE (1-800-656-4673)
Loveisrespect (National Dating Abuse Helpline): Call 1-866-331-9474 (TTY: 1-866-331-8453).
Text LOVEIS to 22522 - you’ll receive a response from a peer advocate prompting you for your question. Go ahead and text your comment or question and we will reply.