Home

Advanced Algorithms


Course Code

CS3958

Session

Fall 2021

Instructor(s)

Chihao Zhang, Assistant Professor (tenure-track)

John Hopcroft Center for Computer Science


Shanghai Jiao Tong University




Description

In the year of 2021, the course is divided into three parts:

    1. Basic Tools in Probabilistic Analysis.

        I will talk about concentration inequalities, martingales, and optional stopping theorem.
 

     2. Optimization

    Starting from some motivating problems in online decision-making, I will cover some basic concepts and tools in convex optimization, online learning, and most importantly, the connection between optimization algorithms and the geometry of the underlying problem.
 

    3. Sampling

        I will introduce Markov chains and the Markov chain Monte Carlo (MCMC) algorithm. Based on this, a few applications in theoretical computer science and data science will be discussed. Finally, I will talk about the connection between the convergence of Markov chains and geometry as well.

        If time permits, I will discuss some close connections between optimization and sampling algorithms, mainly from the perspective of discretizing certain differential equations.

© John Hopcroft Center for Computer Science, Shanghai Jiao Tong University
分享到

地址:上海市东川路800号上海交通大学软件大楼专家楼
邮箱:jhc@sjtu.edu.cn 电话:021-54740299
邮编:200240