CS264: Beyond Worst-Case Analysis

Instructor: Tim Roughgarden (Office hours: Mondays after class, Gates 474.)

Teaching Assistants:

• Rishi Gupta (Office hours: Wednesdays 3:30-5:30, Gates 460. Email: rishig "at" cs.stanford.edu)

Time/location: 2:15-3:30 PM on Mondays and Wednesdays in 200-219.

Piazza site: here

Course description: This course has two intertwined goals. The first goal is to survey several important computational problems for which the traditional worst-case analysis of algorithms is ill-suited, because it fails to differentiate meaningfully between different solutions, recommends an empirically "wrong" solution over the "right" one, or gives excessively pessimistic performance predictions. The second goal is to study systematically alternatives to worst-case analysis that nevertheless enable rigorous and robust guarantees on algorithm performance.

List of topics: instance optimality; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); average-case analysis; robust distributional analysis; resource augmentation; planted and semi-random graph models.

Motivating problems drawn from online algorithms, machine learning, computational geometry, graph partitioning, scheduling, linear programming, hashing, and auction theory.

Prerequisites: undergraduate algorithms (CS161, or equivalent).

Course requirements: Weekly exercise sets. Students have the option to substitute a paper-reading project for some of the exercise sets. No late assignments accepted.

Lecture videos and notes

• Lecture 1 (Introduction):   Video    Notes (beta version)
• Lecture 2 (Instance-Optimality):   Video    Notes (beta version)
• Lecture 3 (Resource Augmentation):   Video   Notes (beta version)
• Lecture 4 (Parameterized Paging):   Video   Notes (beta version)
• Lecture 5 (Recoverable Value):   Video   Notes (beta version)
• Lecture 6 (Stable Clustering):   Video    Notes (beta version)
• Lecture 7 (Single-Link++):   Video    Notes (beta version)
• Lecture 8 (Recovering Graphs Cuts)   Video    Notes (beta version)
• Lecture 9 (Compressive Sensing)   Video    Notes (beta version)
• Lecture 10 (Planted Graph Models)   Video    Notes (beta version)
• Lecture 11 (LP Decoding)   Video    Notes (beta version)
• Lecture 12 (LP Decoding/Smoothed Simplex)   Video    (see Lectures 11 and 13 for notes)
• Lecture 13 (Smoothed Local Search)   Video    Notes (old, to be updated)
• Lecture 14 (Smoothed Pareto Curves)   Video    Notes (beta version)
• Lecture 15 (Pseudopoly = Smoothed Poly)   Video    Notes (beta version)
• Lecture 16 (Hashing + Pseudorandom Data)   Video    Notes (old, to be updated)
• Lecture 17 (Self-Improving Algorithms)   Video    Notes (old, to be updated)
• Lecture 18 (Pricing Using Samples)   Video    Notes (beta version)
• Lecture 19 (Random Permutations)   Video    Notes (beta version)
• Lecture 20 (Distributions=>Instance-Optimality)   Video    Notes (beta version)
• The CS264 Top 10 List

Homeworks:

• Submit your homeworks here.
• A LaTeX template that you can use to type up solutions. Here and here are good introductions to LaTeX.

• Homework #1 (Out Wed 9/24, due midnight Wed 10/1.)
• Homework #2 (Out Wed 10/1, due midnight Wed 10/8.)
• Homework #3 (Out Wed 10/8, due midnight Wed 10/15.)
• Homework #4 (Out Wed 10/15, due midnight Wed 10/22.)
• Homework #5 (Out Wed 10/22, due midnight Wed 10/29.)
• Homework #6 (Out Wed 10/29, due midnight Wed 11/5.)
• Homework #7 (Out Wed 11/5, due midnight Wed 11/12.)
• Homework #8 (Out Wed 11/12, due midnight Wed 11/19.)
• Homework #9 (Out Wed 11/19, due midnight Wed 12/3.)
• Homework #10 (Out Wed 12/3, due midnight Wed 12/10.)

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

• 2011 Workshop on Beyond Worst-Case Analysis, at Stanford. Note 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.)

Detailed schedule and references:

• Lecture 1: Three motivating examples. Pros and cons of worst-case analysis. Instance optimality. References:
  • Fagin/Lotem/Naor, Optimal aggregation algorithms for middleware, JCSS '03.

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

• Lecture 3: The algorithm analysis toolbox. 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.

• Lecture 4: Case studies in parameterized analysis (Part 1). 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 videos (from the 2011 workshop on BWCA):
  • Susanne Albers on locality of reference in competitive analysis.
  • Alex Lopez-Ortiz on the parameterized analysis of online algorithms.

• Lecture 5: Case studies in parameterized analysis (Part 2). Approximation algorithms for the maximum-weight independent set problem. The recoverable value. A tour d'horizon of common input- and solution-based parameters for different types of data. Main reference:
  • Feige/Reichman, Recoverable Values for Independent Sets, ICALP '11.
  Additional reference:
  • Feige/Immorlica/Mirrokni/Nazerzadeh, PASS Approximation: A Framework for Analyzing and Designing Heuristics, APPROX '09.
  Related videos:
  • Nicole Immorlica on PASS approximation.
  • Ryan Williams on backdoors in SAT instances.
  • Andrew Goldberg on computing shortest paths in networks with low "highway dimension".
  • A taste of fixed-parameter tractability, via the Vertex Cover problem (Coursera videos): Part 1 and Part 2

• Lecture 6: Stable clustering, part 1. The k-median problem and the BBG algorithm. Reference:
  • Balcan/Blum/Gupta, Clustering under Approximation Stability, JACM '13.
  Related video:
  • Avrim Blum on stable clustering.

• Lecture 7: Stable clustering, part 2. Single-link++ recovers the optimal solution in perturbation-stable k-median instances. References:
  • Awasthi/Blum/Sheffet, Center-based Clustering under Perturbation Stability, IPL '11.

• Lecture 8: Exact recovery. When are linear programs exact? Case studies: the minimum s-t cut and multiway cut problems. References:
  • Makarychev/Makarychev/Vijayaraghavan, Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut, SODA '14.

• Lecture 9: 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.
  • Lee's blog posts on the fact that random subspaces are almost Euclidean with high probability: Part 1 and Part 2.

• Lecture 10: Planted and semirandom models for clique and graph partitioning. References:
  • Feige/Killian, Heuristics for Semirandom Graph Problems, JCSS '01.

• Lecture 11: LP decoding of LDPC codes. References:
  • Feldman/Malkin/Servedio/Stein/Wainwright, LP Decoding Corrects a Constant Fraction of Errors, IEEE Transactions on Information Theory, 2007.

• Lecture 12: Finish LP decoding of LDPC codes (see Lecture 11 notes). Introduction to smoothed analysis (see Lecture 13 notes). Spielman-Teng from 30000 feet (see Lecture 13 notes). References:
  • Viderman, LP decoding of expander codes: a simpler proof, 2012.
  General references on smoothed analysis:
  • Spielman/Teng, Smoothed analysis: an attempt to explain the behavior of algorithms in practice, CACM '09.
  • The smoothed analysis homepage.
  Related video:
  • Dan Spielman on smoothed analysis.
  • Shang-Hua Teng on smoothed analysis.

• Lecture 13: 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 14: Smoothed analysis of Pareto curves. Application: the Knapsack problem has polynomial smoothed complexity. Reference for lecture:
  • Beier/Roeglin/Voecking, The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization, IPCO '07.
  Related video:
  • Ankur Moitra on smoothed analysis of Pareto curves.

• Lecture 15: 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 16: Pseudorandom data and hashing. Why simple hash functions work as well as fully random ones in practice. References:
  • Mitzenmacher/Vadhan, Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream, SODA '08.
  • See also this later version, with Chung.
  Related video:
  • Michael Mitzenmacher on (among other things) pseudorandom data.

• Lecture 17: Self-improving algorithms. References:
  • Ailon/Chazelle/Comandur/Liu, Self-Improving Algorithms, SODA '06.
  • Clarkson/Seshadhri, Self-improving Algorithms for Delaunay Triangulations, SCG '08.
  • More recent combined version.
  Related video:
  • C. Seshadhri on self-improving algorithms.

• Lecture 18: Pricing to maximize expected revenue with an unknown distribution. References:
  • Dhangwatnotai/Roughgarden/Yan, Revenue Maximization with a Single Sample, EC '10.
  • Huang/Mansour/Roughgarden, Making the Most of Your Samples, 2014.
  Related videos:
  • Qiqi Yan on prior-independent auctions.
  • Your instructor on prior-independent auctions.

• Lecture 19: The random permutation model. Applications to online network design and secretary problems. References:
  • Garg/Gupta/Leonardi/Sankowski, Stochastic Analyses for Online Combinatorial Optimization Problems, SODA '08.
  • Babaioff/Immorlica/Kleinberg, Matroids, Secretary Problems, and Online Mechanisms, SODA '07.
  Related video:
  • Anupam Gupta on stochastic analyses of network design problems.

• Lecture 20: From unknown input distributions to restricted instance optimality. Case study: regret bounds for online decision-making. References:
  • Blum/Mansour, Learning, Regret Minimization, and Equilibria, Sections 4.3-4.4.2 (in the AGT book).
  • Kalai/Vempala, Efficient Algorithms for On-line Optimization, JCSS '05.