CSCI 6220/4030 Randomized Algorithms, Fall 2018

Overview

Randomized Algorithms are the state of the art in contemporary algorithm design. They are usually simple, sometimes even easy to analyze, and they work well in practice. This course provides an introduction to basic concepts in the design and analysis of randomized algorithms.

Course Logistics

A more detailed version of the syllabus is available as an archival pdf.

Instructor: Alex Gittens (gittea at rpi dot edu)

Lectures: MTh 10am-11:50am; Darrin 239

Office Hours: MTh 12pm-1pm, or by appointment; Lally 316

Course Text: (Recommended, not required) Probability and Computing, by M. Mitzenmacher and E. Upfal.

Grading Criteria:

• Homeworks, 50%
• In-class Pop Quizzes, 25%
• Project, 25%

Students are expected to have writing supplies on hand in each class to complete the in-class pop quizzes. If you are an athlete or for some other reason are not able to attend each class, make alternative arrangements with the instructor in the first two weeks of the course.

Letter grades will be computed from the semester average. Lower-bound cutoffs for A, B, C and D grades are 90%, 80%, 70%, and 60%, respectively. These bounds may be moved lower at the instructors discretion.

Topics

We will largely follow Mitzenmacher and Upfal, replacing the more ML-focused content with alternative material.

• Events and Probabilities
• Discrete Random Variables
• Moments and Deviations
• Chernoff and Hoeffding Bounds
• Balls, Bins, and Graphs
• Randomized Data Structures: Treaps, Skip Lists, Hash Tables, Bloom Filters
• The Probabilistic Method
• Markov Chains and Random Walks
• Continuous Distributions and Poisson Processes
• Normal Distribution and Dimensionality Reduction
• Monte Carlo Method
• Coupling
• Martingales
• Streaming Algorithms

Lecture Schedule

• Lecture 1: Course logistics, Randomized Algorithms, Las Vegas and Monte Carlo algorithms, 8 standard uses for randomness, Probability spaces
• Lecture 2: Probability spaces (recap), Axioms of probability, Nontriviality of sigma-algebras for continuous state spaces, Indicator random variables, Bernoulli and Binomial distributions
• Lecture 3: Random variables (cont'd), CDFs, PDFs, Sampling from random variables, Conditional probabilities, Law of total probability, Karger's Mincut algorithm
• Lecture 4: More efficient Karger's algorithm (recursive), Random vectors and joint distributions, Multivariate Gaussians, Marginal distributions, Conditional distributions
• Lecture 5: Reservoir sampling, Independent random variables, Expectation and its properties, Geometric random variables, Coupon collector problem
• Lecture 6: Conditional expectation, Moments, Variance, Markov's inequality, Chebyshev's inequality
• No lectures the week of September 24
• Lecture 7: Kaczmarz algorithm as an application of conditional expectation, Randomized linear-time median algorithm
• Lecture 8: Randomized linear-time median algorithm, Central Limit Theorem, Berry--Esseen
• Lecture 9: Tail Sum Formulae, Cramer-Chernoff methodology, Moment Generating Functions, statement of Chernoff bounds for Poisson trials
• Lecture 10: Proof of Chernoff bound for Poisson trials, Set balancing
• Lecture 11: Randomized Oblivious Routing
• Lecture 12: Randomized Oblivious Routing and Introduction to Treaps
• Lecture 13: Treaps and Introduction to Skip-Lists
• Lecture 14: Skip-Lists and introduction to Hashing
• Lecture 15: Prime Modular Hashing, Knuth Multiplicative Hashing, and introduction to Binary Multiplicative Hashing
• *Lecture 16: Binary Multiplicative Hashing
• *Lecture 17: Fingerprinting, Schwartz-Zippel Theorem, Perfect Matching in Bipartite Graphs
• *Lecture 18: Tutte Polynomial, Randomized Test for Perfect Matching, Monte Carlo algorithm for Perfect Matching
• *Lecture 19: Modular Prime Fingerprinting, Rabin-Miller algorithm for string matching
• *Lecture 20: Probabilistic Method: Kernel Ridge Regression as motivation for Low-Rank approximation in ML, Caratheodory Theorem and Approximate Caratheodory Theorem
• *Lecture 21: Johnson-Lindenstrauss Transform and Dimensionality Reduction
• *Lecture 22: Introduction to Markov Chains and examples

Corresponding optional readings

• Lectures 1 to 5: MU17 pages 3--11, section 1.5, Chapter 2, section 8.1, subsections 9.1.1--9.1.2
• Lecture 6: MU17 sections 3.1--3.3
• Lecture 7: MU17 section 3.5; Strohmer and Vershynin. A randomized Kaczmarz algorithm with exponential convergence
• Lecture 8: MU17 section 3.5, section 9.3
• Lecture 9: MU17 Lemma 2.9, section 4.1, section 4.2 (up to and including the statement of Theorem 4.4)
• Lecture 10: MU17 section 4.2, section 4.3, section 4.4
• Lecture 11: MU17 the introduction to section 4.6 and subsection 4.6.1
• Lectures 12-13: Jeff Erickson's notes on treaps and skiplists (caution: he uses min-heaps, whereas we used max-heaps in our lectures)
• Lectures 14-15: Jeff Erickson's notes on hashing. You can also look through the MU17 sections on hashing: the brief portion of 5.5 before 5.5.1 introduces hashing, and section 15.3 covers uniformity/universality, prime modular hashing, and perfect hashing.

Homeworks

All assignments must be typed (preferably in LaTeX) and are due at the start of class (defined as the first 10 minutes). Late assignments will not be accepted, unless you contact the instructor at least two days before the due date to receive a deferral. Deferrals will be granted at the instructor’s discretion, of course.

• HW1: Probability Theory Assigned Monday September 10, due Thursday September 20. Start early, and ask questions about both the content and your write-ups.
• HW2 Assigned Monday September 24, due Tuesday October 9. I am out of town the week of September 24; for this week (only) I will answer questions via email in lieu of my office hours.
• HW3 Assigned Tuesday October 9, due Monday October 22.
• HW4 Assigned Monday October 22, due Monday November 5. For your convenience: hw4.tex. Skip question 6 (unless you want to do it), as we will not see the requisite ideas for the proof until the class immediately before the homework is due.
• HW5 Assigned Tuesday November 13, due Monday November 26. For your convenience: hw5.tex.
• HW6 Assigned Thursday November 29, due Thursday December 10. For your convenience: hw6.tex.

Project

The details here may change over the next few weeks, so check back regularly.

In teams of two to three individuals, you will give a 20 minute presentation of an interesting or cool result or an algorithm (or class of algorithms) from a course-relevant technical or survey paper to the class; if your research is relevant, that could also be the topic of your presentation. This can be material that requires no background beyond general knowledge of CS, or more niche/applied knowledge; in the latter case, you should quickly explain the relevant concepts and background. See the "Giving Talks" and "Reading Papers" slide decks from the CS RPI Graduate Skills Seminar.

Content: address the following points.

• Who are the authors, and the date and venue of publication?
• What is the problem that is addressed (pick one, if the paper addresses more than one), and why is it interesting or useful?
• What is the main result of the paper?
• Describe the result or algorithm and motivate it intuitively.
• What is the cost (time, space, or some other metric) of this algorithm, and how does it compare to prior algorithms for the same problem? (and similarly, for non-algorithmic rsults)
• What performance guarantees, if any, are provided for the algorithm?
• Give an accurate description of the analysis given in the paper: in simple cases this may be a tour through the entire argument; when this is not possible, focus on explaining a core lemma/theorem that supports the claim of the paper.
• Provide an empirical evaluation of the algorithm: compare its performance to reasonable baselines, and explore relevant aspects of the algorithm (its variability, sensitivity to relevant properties of the input, etc.). If presenting a non-algorithmic result and it is possible, provide some experimental evidence of its sharpness or lack thereof.

An extremely biased sample of viable project ideas that is not at all representative of all your choices: the kmeans++ algorithm, coresets for geometric or ML problems, triangle counting in graphs; one of Karp's theorems for probabilistic recurrences; some application of The Power of Two Random Choices; random fourier features for kernel approximation in machine learning; fast-mixing Markov Chains for low-rank matrix approximation; one of the many stochastic approaches to optimization of sums of functions; rounding approaches for approximating solutions to LPs, QPs, or SDPs; compressed sensing; matrix completion; formation of minimal spanning trees; min-hash; count-min; how to fake multiply by a Gaussian matrix; an application of MCMC methods; etc. These selections are just examples, feel free to make entirely different choices.

Grading Rubric

• On-time team formation and paper selection, 10%
• Discussion of paper with me, 40%
• In-class presentation, 40%
• On-time deliverables, 10%

Deliverables: these should be submitted in a single github/gitlab repo for each project. Due December 3.

• Well-documented cross-platform code for reproducing your experimental evaluations. Julia, Python, R, and C++/C are acceptable.
• A pdf slide deck with appropriately typeset math and legible figures that addresses all of the above points.

Deadlines

• By October 29, have formed your groups and identified and obtained my approval for your paper selection.
• By the end of the week of November 19, all of your group must discuss your paper in a meeting with me, answering the questions I have pointed out above, and justifying your choice of empirical evaluations and baselines. I highly suggest you actually have your experiments done so we can discuss them. Schedule this meeting at least the week before, so we don't have everyone trying to meet with me on Thursday.
• December 3 or 6, give your 20 minute in-class presentation.

Supplementary Materials

• Supplement for homework 3, on tail bounds for gaussian random variables, and some implications of the asymptotic CLT.
• Supplement for the treap lectures, with a corrected proof that the expected height of a treap is logarithmic in the number of keys.