Duke University
COMPSCI 590.04
Machine Learning Algorithms
Spring 2021
Overview
Algorithms and machine learning are two grand success stories of modern computer science. But, how do they interact? How does our knowledge of algorithms help design machine learning tools? Conversely, how do advances in machine learning impact the design of algorithms? We will explore these questions from the perspective of theoretical computer science in this course.
Course Staff
Instructors
Debmalya Panigrahi debmalya@cs.duke.edu
(Part-time) Graduate Teaching Assistants (TAs)
Keerti Anand kanand@cs.duke.edu
Mo Zhou mozhou@cs.duke.edu
Syllabus
Basics
Basic concepts
VC dimension
The PAC framework
Basic Learning Tasks
Classification
Regression
Basic Optimization Algorithms
Gradient Descent
ML as a tool for Better Algorithms: Learning-Augmented Algorithms
Mitigating Uncertainty
Online Algorithms with Predictions
Consistency, Robustness, and Graceful Degradation
Optimization from Samples
Beyond Worst-case Algorithm Design
Algorithm selection
Online Learning
Smoothed complexity
Algorithms as a tool for Better Machine Learning: The Theory of Deep Learning
Basics of Neural Networks
Optimization
Escaping saddle points
Landscape analysis
Neural Tangent Kernel
Generalization
Implicit Bias
Generalization bounds
Interpolation/double descent