Advanced Algorithms (Fall 2021)

General Information

Instructor:

Chihao Zhang

Time:

Monday
12:55 - 15:40

Location:

East Middle Hall (东中院) 2-206

Office Hour:

Monday
7:00 pm - 10:00 pm
Software Building 1402-2

References

See topics and references

Lecture Notes

[Dec 27][notes] Discretizing Langevin Dynamics, see the paper of Dalalyan
[Dec 20][notes] Diffusion, Fokker-Planck Equation, Langevin Dynamics
[Dec 13][notes] Volume Estimate, Ball Walk, Isoperimetric Inequality (See Chapter 9 of Lee & Vempala's book)
[Dec 06][notes] Canonical Paths, Flow Method (See Lecture 11 and Lecture 12 of Sinclair's course)
[Nov 29][notes] Relaxation Time, Graph Expansion, Cheeger’s Inequality
[Nov 22][notes] Reversible Chains, Metropolis Algorithm, Spectral Decomposition
[Nov 15][notes] Proof of FTMC, Mixing Time, Applications of Coupling
[Nov 08][notes] Discrete Markov Chains, Fundamental Theorem of Markov Chains, Coupling
[Nov 01][notes] Online (Stochastic) Gradient Descent, Strongly Convex, Learning with Expert Advice
[Oct 25][notes] Online Learning, Convex Optimization, Gradient Descent
[Oct 18][notes] Multi-Armed Bandit, Explore-then-Commit, Upper-Confidence-Bound
[Oct 11][notes] Stopping Time, Optional Stopping Theorem
[Sep 27][notes] Martingale, Azuma-Hoeffding, McDiarmid
[Sep 18][notes] Concentration Inequalities
[Sep 13][notes] Introduction to the Course, Review of Probability