COMP 605: Graduate Seminar in Learning Theory

Instructor: Maryam Aliakbarpour

Time: Wednesdays 4-5:15pm
Class: Keith-Wiess 130
Office hour: by appointment (email)
Email: maryama [at] rice [dot] edu


Description

Machine learning and data analysis have revolutionized many scientific fields and industrial sectors. Much of this success hinges on the vast amount of digital data generated and collected in today's world. However, as we navigate this data-driven frontier, we face novel challenges emerging from the scale and societal implications of data usage.

In this seminar, our focus is on studying new algorithmic advancements developed for learning algorithms within the context of these challenges. We will explore computational models with limitations in memory or time, which are more compatible with practical settings, and investigate the algorithmic solutions to fundamental learning problems in such models. An intriguing question we'll address is whether increasing the volume of data can compensate for memory or time constraints.

Another major topic in our seminar is the societal considerations of individuals' data usage such as privacy and fairness. We will investigate new technical methods to design efficient algorithms while preserving the privacy of individuals who participated in the data, with a particular focus on differential privacy. Additionally, we will examine recent advancements in algorithmic fairness.

Throughout this seminar, we will consider fundamental problems in learning theory and study them within the context of these challenges. Our primary goal is to acquaint ourselves with state-of-the-art findings in the field while gaining proficiency in foundational technical tools applicable to theoretical research endeavors.


Schedule

Date Material Assignment
08/28/2024 Course Overview, Differential Privacy
Slieds
09/04/2024 PAC Learning
Notes
Fill out this form and presentation sign up sheet.
Due on Thursday, September 15, 11:59pm (CT)
09/11/2024 Distribution testing: Uniformity testing
Notes
Assignment 1 on canvas
Due Wednesday, September 18, 2024, 4:00pm (CDT).
09/18/2024 Reading: What Can We Learn Privately?
Notes
09/25/2024 Reading: Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates Assignment 2 on canvas
Due Wednesday, September 25, 2024, 4:00pm (CDT).
10/02/2024 Reading: The Composition Theorem for Differential Privacy
10/09/2024 Readings: A learning theory approach to noninteractive database privacy
Small database mechanism discussed in Section 4 of the Dwork and Roth privacy book
10/16/2024 Reading: Smooth Sensitivity and Sampling in Private Data Analysis
10/23/2024 Readings: Understanding the Sparse Vector Technique for Differential Privacy
Differential privacy under continual observation
Sparse vector technique discussed in Section 4 of the Dwork and Roth privacy book
10/30/2024 Reading: Learning Monotone Functions from Random Examples in Polynomial Time
11/06/2024 Reading: Robust Estimators in High-Dimensions Without the Computational Intractability
11/13/2024 Reading: A New Approach for Testing Properties of Discrete Distributions
11/20/2024 Reading: Agnostically Learning Halfspaces
11/27/2024 No class (Thanksgiving)
12/04/2024 Project presentations