This course is a continuing line of topics from CSC 665 Section 2 Machine Learning Theory that delve into online learning and multi-armed bandits (but the knowledge from ML theory is not required). The students will learn, via the lens of mathematical foundations, how and when machines can learn in an online manner. 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 sequential decision making 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:
Multivariate Calculus or equivalent:
Basic probability theory and statistics:
Lectures, individual assignments, written exams, projects, in-class discussions.
A successful student will be able to explain the key concepts of online learning, convex optimization, and the bandit feedback, and analyze lower and upper bounds of the achievable performance of the various online learning tasks and algorithms. Main topics include:
This course is far from a complete survey of the concurrent topics on online learning and multi-armed bandits 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 online learning 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 is: * To be able to understand the concept of the key performance measure called ‘regret’, and how online learning is able to deal with adversarial data (i.e., non-stochastic). * To be able to list the common loss classes and their achievable regret bounds and explain why accelerated rates are available for some classes. * To be able to explain how online mirror descent and follow the regularized leader is different, and when one is better than the other. * To be able to identify the key problem parameters that govern the regret rates for each problem. * To be able to explain the key challenge in the bandit feedback. * To be able to articulate how various bandit problems pose different challenges and what the achievable regret rates are. * To be able to explain how the pure exploration is different from the regret minimization in multi-armed bandits. * To be able to describe the landscape of online learning and list a few open problems researchers are currently working on.
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.
There is no designated textbook for this course. Much of the course materials will be based on the following materials (in the order of appearance in class schedule):
This course will have a weekly review quiz (1-2 questions) that is relatively easy but requires reviewing the learned material.
There will be two written homework assignments:
This course will not have a final examination.
Each student will select a paper among the provided list of papers and present it for an hour. The presentation must include a clear exposition of the problem being addressed, the solution the paper proposes, a comparison of the solution with similar studies, key technical details and proofs, and possible extensions and open problems. To receive full credit for class participation, students must attend and participate in the discussion of all classes. Students should contact the instructor regarding absences for make-up.
The instructing staff will grade your assignments, project, and the final exam on a scale from 0 to 100, with the following weights:
The final grade in the course of the best of a per-class grading curve and overall performance:
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:
The National Suicide Prevention Lifeline is a 24-hour, toll-free, confidential suicide prevention hotline available to anyone in suicidal crisis or emotional distress. By dialing 1-800-273-TALK (8255), the call is routed to the nearest crisis center in our national network of more than 150 crisis centers. The Lifeline’s national network of local crisis centers provides crisis counseling and mental health referrals day and night.
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.