COMP 677: Graduate Seminar in Learning Theory

Instructor: Maryam Aliakbarpour

Time: Wednesdays 4-5pm
Class: Duncan Hall 1075
Office hour: by appointment (email)
Email: maryama [at] rice [dot] edu


Schedule

Date Material Assignment
08/23/2023 Lecture 1
Private Testing of Distributions via Sample Permutations
Please fill out this form.
Due Monday, August 28, 2023, 11:59pm (CDT).
08/30/2023 Lecture 2
Notes on concentration of random variables
Estimation of Entropy in Constant Space
Assignment 1 (OPTIONAL) on canvas
Due Wednesday, August 30, 2023, 4:00pm (CDT).
09/06/2023 When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
PAC Learning model review
See Chapter 1 of Kearns and Vazirani's book
Assignment 2 on canvas
Due Wednesday, September 6, 2023, 4:00pm (CDT).
09/13/2023 Memory-Sample Tradeoffs for Linear Regression with Small Error Assignment 3 on canvas
Due Wednesday, September 13, 2023, 4:00pm (CDT).
09/20/2023 Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness Assignment 4 on canvas
Due Wednesday, September 20, 2023, 4:00pm (CDT).
Project abstract on Canvas
Due Wednesday, September 20, 2023, 11:59pm (CDT).
See project guidelines for more details.
09/27/2023 Robust Estimation of Discrete Distributions under Local Differential Privacy Assignment 5 on canvas
Due Wednesday, September 27, 2023, 4:00pm (CDT).
10/04/2023 When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? Assignment 6 on canvas
Due Wednesday, October 4, 2023, 4:00pm (CDT).
10/11/2023 Lecture 8 Reading: Chapter 4 of this book
10/18/2023 Lecture 9 Reading: Chapter 6 of this book
Project mid-point evaluation on canvas
Due Wednesday, October 18, 2023, 11:59pm (CDT).
See project guidelines for more details.
10/25/2023 Lecture 10 Reading: Chapter 6 of this book
11/01/2023 Computational-Statistical Gaps in Reinforcement Learning Assignment 7 on canvas
Due Wednesday, November 1, 2023, 4:00pm (CDT).
11/08/2023 Detecting Correlations with Little Memory and Communication Assignment 8 on canvas
Due Wednesday, November 8, 2023, 4:00pm (CDT).
11/15/2023 Project presentations
11/22/2023 No class (Thanksgiving holiday)
11/29/2023 Project presentations



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.