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