CSE 525: Randomized algorithms and probabilistic analysis

Autumn, 2016

Professor: James R. Lee

Office hours: Wed 3-4pm, CSE 640

TA: Alireza Rezaei (arezaei@cs)

Office hours: Thurs 12-1pm, CSE 021

Class email list: cse525a_au16@uw

Class discussion board

Lectures

Note that the "bonus material" is not required reading. It's there if you're interested in learning more about the topic of the lecture and its broader applications.

class topic notes bonus material
28-Sep Some basics pdf Schwartz-Zippel Lemma
3-Oct Linearity of expectation pdf Incidence geometry and sum-product estimates
5-Oct Second moments pdf Sinclair's lecture on random k-SAT: Lec 1, Lec 2
10-Oct More on second moments pdf See Chapter 5 of Lyons-Peres,
Cover time of the discrete torus
12-Oct Chernoff bounds and randomized rounding pdf Concentration inequalities: A non-asymptotic theory of independence
17-Oct Routing in the hypercube pdf
19-Oct NO CLASS (affiliates)
24-Oct Martingales and Azuma's inequality pdf
26-Oct More martingales, chromatic number pdf
31-Oct Random tree embeddings pdf
2-Nov Bourgain's embedding pdf Matousek's lecture notes on metric embeddings
7-Nov Dimension reduction pdf
9-Nov Compressive sensing pdf The Effectiveness of Convex Programming in the Information and Physical Sciences (youtube)
14-Nov Random walks and electrical networks pdf Doyle & Snell's book on this topic
16-Nov Cover times pdf
21-Nov Markov chains and mixing times pdf
23-Nov
28-Nov Bubeck: Stochastic gradient descent
30-Nov Bubeck: Stochastic gradient II (starts 10 minutes late at 1:40pm!)
5-Dec
7-Dec

Course overview

Randomness is a powerful and ubiquitous tool in algorithm design and data analysis. This is especially true in a world overrun by data. No efficient algorithm can possibly take a high-fidelity view of all of it. But often we don't have to; uncertainty plays the dual roles of blessing and curse. And in our darkest high-dimensional hour, "concentration of measure" allows us to extract information without first knowing where to look.

Sometimes the signal is everywhere. Sometimes we only need a glimpse of the truth to head in the right direction. Sometimes a random direction suffices.

Evaluation and grading

  • weekly/bi-weekly homeworks (60%)
  • two take-home exams and/or possible project (40%)

Syllabus (approximate)

  • Discrete probability
    • The probabilistic method
    • Linearity of expectation
    • Variance and the 2nd moment method
    • Lovasz Local Lemma
    • Martingales
    • Chernoff and Hoeffding-Azuma inequalities
  • High-dimensional geometry and statistics
    • Concentration of measure
    • Dimension reduction
    • Locality sensitive hashing
    • Nearest-neighbor search
    • Restricted isometry and compressive sensing
  • Information and entropy
    • Measures of information
    • Max-entropy approximation
    • Sparsification via sampling
    • Multiplicative weights update and boosting
    • Online stochastic gradient descent
  • Markov chains and convergence to equilibrium
    • Random walks
    • Eigenvalues and rapid mixing
    • Expander graphs
    • Markov chain Monte Carlo
    • Approximate counting

Where & when:
Mon & Wed, 1:30-2:50
CSE 403

Homeworks:

You may discuss problems with your classmates, but when you write down the solutions, you should do so by yourself. You can use the internet and books for reference material but you must cite every source that you consulted (the name of the book or web page suffices). You should also cite any classmates with whom you discussed solutions.

All homework should be turned in electronically to the Dropbox by the due date for the assignment. Homework should either be typeset or written very neatly and scanned.

Late HW policy: I will allow one (slightly) late homework per person (e.g., to accomodate for a paper deadline). This must be arranged beforehand.

Note on Bonus problems: These problems are usually quite challenging. If you do some of them, I will be impressed. But they are in no way required (or even suggested) for obtaining a good grade in the course.

[ Dropbox for assignments ]

  • HW 1: Out 3-Oct, due 9-Oct before class
  • HW 2: Out 10-Oct, due Fri 21-Oct at midnight
  • HW 3: Out 24-Oct, due Mon 31-Oct before class
  • HW 4: Out 31-Oct, due Mon 7-Nov before class
  • HW 5: Out 16-Nov, due Wed 23-Nov before class

Exams:

Useful books: