CS264: Beyond Worst-Case Analysis

Instructor: Tim Roughgarden (Office hours: Tuesdays 2-3 PM, Gates 474.)

Teaching Assistants:

• Josh Wang (Office hours: Wednesdays 3-5 PM, Gates 460. Email: joshua.wang [at] cs [dot] stanford [dot] edu)

Time/location: 10:30-11:50 AM on Tuesdays and Thursdays in Hewlett 102.

Piazza site: here

Course description: In the worst-case analysis of algorithms, the overall performance of an algorithm is summarized by its worst performance on any input. This approach has countless success stories, but there are also important computational problems --- like linear programming, clustering, and online caching --- where the worst-case analysis framework does not provide any helpful advice on how to solve the problem. This course covers a number of modeling methods for going beyond worst-case analysis and articulating which inputs are the most relevant.

List of topics: instance optimality; perturbation and approximate stability; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); robust analogs of average-case analysis; resource augmentation; planted and semi-random graph models; sparse recovery (like compressive sensing).

Motivating problems drawn from online algorithms, machine learning (topic models, clustering), computational geometry, graph partitioning, scheduling, linear programming, local search heuristics, social networks, hashing, signal processing, and empirical algorithmics.

Prerequisites: undergraduate algorithms (CS161, or equivalent). Prior exposure to linear programming is recommended but not required (review materials will be posted as needed).

Course requirements: Weekly exercise sets. Students have the option to substitute a paper-reading project for 3 of the exercise sets. No late assignments accepted, although we will drop the lowest of your 10 scores.

Previous offering (in 2014): here. Includes lecture videos and lecture notes. Note: the overlap between this and the previous offering will be roughly 50%.

Primer: for a two-hour overview of the entire course, see

• Beyond Worst-Case Analysis, Part 1 and Part 2, Algorithms and Uncertainty Boot Camp, Simons Institute (2016). Slides

Lecture notes

• Lecture 1 (Introduction) [beta version]
• Lecture 2 (Instance Optimality) [beta version]
• Lecture 3 (Resource Augmentation) [beta version]
• Lecture 4 (Parameterized Paging) [beta version]
• Lecture 5 (Parameterized Algorithms) [beta version]
• Lecture 6 (Perturbation-Stable Clustering) [beta version]
• Lecture 7 (Perturbation-Stable Minimum Cuts) [beta version]
• Lecture 8 (Perturbation-Stable Maximum Cuts) [beta version]
• Lectures 9+10 (Spectral Algorithms for Planted Bisection and Clique) [beta version]
• Lectures 11+12 (SDP Algorithms for Semi-Random Bisection and Clique) [alpha version]
• Lecture 13 (Compressive Sensing) 2014 notes and Mary's notes
• Lecture 14 (Exact Relaxations for Clustering) [no notes]
• Lecture 15 (Nonnegative Matrix Factorization) [alpha version]
• Lecture 16 (Random Order Models) [alpha version]
• Lecture 17 (Smoothed Local Search) [beta version]
• Lecture 18 (Pseudopoly = Smoothed Poly) [beta version]
• Lecture 19 (Self-Improving Algorithms) [beta version]
• Lecture 20 (Application-Specific Algorithm Selection) [beta version]

Additional background material:

• Large deviation inequalities: see Lecture 18 of CS261 and/or these notes written by Avrim Blum.
• Linear programming: see Lecture 7 of CS261.
• Eigenvectors and eigenvalues: there are countless sources on the Web, like here. For further discussion in the context of computer science applications, see Lecture 8 (starting in Section 2.7) and Lecture 11 from CS168.
• Linear programming duality: see Lecture 8 and Lecture 9 of CS261.
• Semidefinite and convex programming: see Lecture 18 of CS168 and Lecture 20 of CS261.

Homework:

• Submission instructions: We are using Gradescope for the homework submissions (you should create an account if you don't already have one). Use the course code MBY5R9 to register for CS264. One submission per team (but remember to add the names of all team members).
• A LaTeX template that you can use to type up solutions. Here and here are good introductions to LaTeX.

• Homework #1 (Out Thu 1/12, due midnight Thu 1/19.)
• Homework #2 (Out Thu 1/19, due midnight Thu 1/26.)
• Homework #3 (Out Thu 1/26, due midnight Thu 2/2.)
• Homework #4 (Out Thu 2/2, due midnight Thu 2/9.)
• Homework #5 (Out Thu 2/9, due midnight Thu 2/16.)
• Homework #6 (Out Thu 2/16, due midnight Thu 2/23.)
• Homework #7 (Out Thu 2/23, due midnight Thu 3/2.)
• Homework #8 (Out Thu 3/2, due midnight Thu 3/9.)
• Homework #9 (Out Thu 3/9, due midnight Thu 3/16.)
• Homework #10 (Out Thu 3/16, due midnight Thu 3/23.)

Related workshops: Since this course debuted in 2009, there have been several workshops on the topic:

• 2011 Workshop on Beyond Worst-Case Analysis, at Stanford. Videos for all talks and the panel discussion are online.
• 2014 Workshop on Analysis of Algorithms Beyond the Worst Case at Dagstuhl, Germany. (No talk videos, unfortunately.)
• 2016 Workshop on Learning, Algorithm Design and Beyond Worst-Case Analysis at the Simons Institute in Berkeley. Videos available for all talks.

Detailed schedule and references (under construction):

• Lecture 1 (Tue Jan 10): Introduction. Three motivating examples (caching, linear programming, clustering). Course philosophy. Instance optimality. Further reading:
  • Fagin/Lotem/Naor, Optimal aggregation algorithms for middleware, JCSS '03.

• Lecture 2 (Thu Jan 12): Instance optimality in computational geometry. References:
  • Afshani/Barbay/Chan, Instance-optimal geometric algorithms, FOCS '09.

• Lecture 3 (Tue Jan 17): Online paging. Resource augmentation. Loose competitiveness. References:
  • Sleator/Tarjan, Amortized efficiency of list update and paging rules, CACM '85.
  • Young, On-Line File Caching, SODA '98/Algorithmica '02.
  • General reference for online paging and online algorithms more generally: book by Borodin and El-Yaniv.

• Lecture 4 (Thu Jan 19): Parameterized analysis of online paging. Parameterizing page sequences by their locality. Optimal page fault bounds for LRU. Rigorously separating LRU and FIFO. References:
  • Albers/Favrholdt/Giel, On Paging with Locality of Reference, STOC '02/JCSS '05.
  Related video (from the 2011 workshop on BWCA):
  • Susanne Albers on locality of reference in competitive analysis.

• Lecture 5 (Tue Jan 24): NP-hard problems and what to do about them. The knapsack problem and parameterized approximation bounds. Parameterized algorithms and a polynomial-size kernel for the vertex cover problem. Color-coding and the longest path problem.
  • Parameterized algorithms is a huge field: here is a recent textbook on the topic.

• Lecture 6 (Thu Jan 26): Perturbation stability: clustering is hard only when it doesn't matter.
  • The main result from today's lecture is from Metric Perturbation Resilience. (Makarychev/Makarychev, 2016).
  • The mentioned hardness result is from k-center Clustering under Perturbation Resilience. (Balcan/Haghtalab/White, 2016)
  • For a survey of this area, see Center Based Clustering: A Foundational Perspective. (Awasthi/Balcan, 2014)

• Lecture 7 (Tue Jan 31): When are linear programming relaxations exact? Case study: perturbation-stable instances of the minimum multiway cut problem. References:
  • Makarychev/Makarychev/Vijayaraghavan, Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut, SODA '14.

• Lecture 8 (Thu Feb 2): Exact recovery in perturbation-stable instances of the maximum cut problem. Metric embeddings and Bourgain's Theorem. Improvements via semidefinite programming. References:
  • Makarychev/Makarychev/Vijayaraghavan, Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut, SODA '14.
  • Lecture notes on metric embeddings (Matousek, 2013)
  • Euclidean distortion and the Sparsest Cut (Arora/Lee/Naor, 2006)

• Lecture 9 (Tue Feb 7): Random graphs. Planted models. A spectral algorithm for the planted bisection problem.
  • The planted bisection model is from Graph bisection algorithms with good average case behavior (Bui/Chaudhuri/Leighton/Siper, 1987).
  • The matrix perturbation approach is from Spectral Partitioning of Random Graphs (McSherry, 2001).
  • Our presentation is loosely based on lecture notes of Spielman, here and here.

• Lecture 10 (Thu Feb 9): A little matrix perturbation theory. A spectral algorithm for the planted clique problem.
  • The spectral algorithm for planted clique is from Finding a large hidden clique in a random graph (Alon/Krivelevich/Sudakov, 1998).

• Lecture 11 (Tue Feb 14): Semi-random models and semidefinite programming 1. Case study: minimum bisection. SDP duality.
  • Heuristics for Semirandom Graph Problems (Feige/Killian, 2001)
  • Lecture notes on SDP duality (Gupta, 2011)

• Lecture 12 (Thu Feb 16): Semi-random models and semidefinite programming 2. Finish bisection. Second case study: maximum clique.
  • Finding and certifying a large hidden clique in a semi-random graph (Feige/Krauthgamer, 2000)

• Lecture 13 (Tue Feb 21): (Guest lecture by Mary Wootters.) A taste of compressive sensing. Finding sparse solutions to underdetermined linear systems. When does l1-minimization work? References:
  • Section 4.5 of Moitra's lecture notes.

• Lecture 14 (Thu Feb 23): (Guest lecture by Moses Charikar.) LP and SDP relaxations for k-median and k-means. Exact recovery in the stochastic ball model. Primary reference:
  • Relax, no need to round: integrality of clustering formulations (Awasthi/Bandeira/Charikar/Krishnaswamy/Villar/Ward, 2015)

• Lecture 15 (Tue Feb 28): Exact recovery: topic models and nonnegative matrix factorization.
  • Computing a Nonnegative Matrix Factorization -- Provably (Arora/Ge/Kannan/Moitra, 2012)
  • A Practical Algorithm for Topic Modeling with Provable Guarantees (Arora/Ge/Halpern/Mimno/Moitra/Sontag/Wu/Zhu, 2013)

• Lecture 16 (Thu Mar 2): Random ordering problems. Secretary problems. Case study: online facility location.
  • Online Facility Location (Meyerson, 2011)

• Lecture 17 (Tue Mar 7): Smoothed analysis of local search heuristics. Case study: the 2OPT local search heuristic for TSP in the plane. Reference for lecture:
  • Englert/Roeglin/Voecking, Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP, SODA '07 and Algorithmica.

• Lecture 18 (Thu Mar 9): For binary optimization problems, polynomial smoothed complexity <=> (Las Vegas randomized) pseudopolynomial worst-case complexity. Reference for lecture:
  • Beier/Voecking, Typical Properties of Winners and Losers in Discrete Optimization, STOC '04/SICOMP '06.

• Lecture 19 (Tue Mar 14): Self-improving algorithms. Primary reference:
  • Ailon/Chazelle/Clarkson/Liu/Mulzer/Seshadhri, Self-Improving Algorithms (2008).

• Lecture 20 (Thu Mar 16): Application-specific algorithm selection. Primary reference:
  • A PAC Approach to Application-Specific Algorithm Selection (Gupta/Roughgarden, 2016)