Organizer:
Andre Wibisono (
andre.wibisono@yale.edu)
Description:
Optimization and sampling are fundamental tasks in machine learning and computer science.
In machine learning, the problem of learning from data can often be formulated as optimizing some objective function which encodes the goal of learning, or as sampling from the posterior distribution of a probabilistic model to make inference.
These tasks are often performed in competition or coordination with other agents,
and tools from game theory are essential for understanding the global behavior of the algorithms.
This reading group will explore the basic landscape of problems in optimization, sampling, and game theory, as motivated by machine learning applications.
We will explore algorithms to solve these problems, and study their convergence guarantees under structural conditions such as convexity or isoperimetry.
We will also study how to design better algorithms via passage to continuous time.
We will explore the space of dynamics in continuous time to solve these problems, where the analysis often becomes simpler and exposes the fundamental structures of the problems.
We will then study how to implement these dynamics as algorithms with provable convergence guarantees;
this is often a challenging step that requires a careful control of the errors using geometric or functional inequalities.
We will explore open questions in these areas and work on them throughout the semester.
Possible topics:
Dynamics and discretization;
convexity and smoothness;
gradient flow and gradient descent;
natural gradient flow and mirror descent;
accelerated gradient descent;
Bregman Lagrangian and accelerated flows;
Wasserstein metric and Otto calculus;
Langevin dynamics;
entropy and Fisher information;
isoperimetry and log-concavity;
min-max optimization;
optimistic and extragradient methods
Target audience:
Beginning graduate students and advanced undergraduates with strong mathematical background who want to learn about research in theoretical machine learning.
Format:
The reading group will meet weekly for 2 hours.
Each session will be a combination of a board talk and a problem-solving session.
Students are expected to be active participants in the reading group.
Students will take turns giving talks on background topics or presenting papers on state-of-the-art results.
Students will get hands-on experience with the common proof techniques by solving a series of problems.
Students will study some open problems during the semester, and either make progress on them or understand their difficulty.
To maintain interactivity, attendance may be limited.
Pre-Questions:
As an example of the questions we will study, see these
pre-questions.
To indicate interest in joining the reading group, please
solve at least 4 of the pre-questions (you can solve as many as you'd like).
Please do not discuss these questions or collaborate with anyone before you submit your solution.
(We will discuss the questions together in the reading group, but this is to gauge your individual skills.)
How to participate:
If you want to participate in the reading group regularly, please do the following: