Duke University

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.

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