Seminar: Machine Learning and Optimization
This is a seminar series, whose topic changes every term.
Please register in ZEuS for the Seminar
Current Seminar:
Summer 2024: Introduction to Online Nonstochastic Control
Based on the book "Introduction to Online Nonstochastic Control", Elad Hazan, 2022 (link)
Control theory is the engineering science of manipulating physical systems to achieve desired functionality. Its history is centuries old, and it spans rich areas from the mathematical sciences. A brief list includes differential equations, operator theory and linear algebra, functional analysis, harmonic analysis, and more. However, it mostly does not concern modern algorithmic theory and computational complexity from computer science. The advance of the deep learning revolution has brought to light the power and robustness of algorithms that are based on gradient methods.
This Seminar concerns this exact observation: how can we exploit the differentiable structure in natural physical environments to create efficient and robust gradient-based algorithms for control?
The answer we give is not to apply gradient descent to any existing algorithm. Rather, we rethink the paradigm of control from the start. What can be achieved in a given dynamical system, whether known or unknown, fully observed or not, linear or non-linear, and without assumptions on the noise sequence? This is a deep and difficult question that we fall short of answering. We do, however, propose a different way of answering this question: we define the control problem from the point of view of an online player in a repeated game. This gives rise to a simple but powerful framework called nonstochastic control theory. The framework is a natural fit to apply techniques from online convex optimization, resulting in new, efficient, gradient based control methods.
This seminar will provide an introduction to the concept or Online Nonstochastic Control, which requires a solid mathematical concepts related to convex optimization and Markov decision processes.
We will roughly cover the following topics:
Dynamical systems
Markov Decision Processes
Linear Dynamical Systems
Optimal Control of Linear Dynamical Systems
Policy classes for dynamical systems
Online Nonstochatic Control
Policy Classes for Partially Observed LDS
Online Nonstochastic Control with Partial Observation
Online Nonstochastic System Identification
Learning in Unknown LDS
Spectral Filtering
This seminar will be based on the following book:
"Introduction to Online Nonstochastic Control", Elad Hazan, 2022 (link)
Prerequisites
Calculus and linear algebra: Familiarity with basic matrix manipulations and concepts from calculus (e.g., differentiability, gradient, continuity)
Pleasure with mathematically rigorous statements: Sufficient mathematical maturity regarding proof techniques (direct proof, proof by contradiction, composition)
Basic knowledge on probability: Familiarity with the following concepts: event, random variable, probability density function, cumulative distribution function, conditional probability, independence, expected value, variance, etc.
Logistics
Seminar: Fridays 10:00 - 11:30, room L829
Grade: Based on your presentation and prepared report (6-8 pages)
Schedule
Friday 12.04: Introduction (book chapter 1) - Tobias Sutter & distribution of topics
Friday 19.04: Dynamical Systems (book chapter 2) - Tobias Sutter
Friday 26.04: Self study preparation time
Friday 03.05 Self study preparation time
Friday 10.05: Topic 1: Markov Decision Processes (book chapter 3) - Jonas Dickhoefer
Friday 17.05: Topic 2: Linear Dynamical Systems (book chapter 4) - Pranjal Kandjhari
Friday 24.05: Topic 3: Optimal Control of Linear Dynamical Systems (book chapter 5) - Jan Reichle
Friday 31.05: break - no seminar
Friday 07.06: break - no seminar
Friday 14.06: Topic 4: Policy Classes for Dynamical Systems (book chapter 6) - Askar Bozcan
Friday 21.06: break - no seminar
Friday 28.06: Topic 5: Online Nonstochastic Control (book chapter 7) - Thomas Beha
Friday 05.07: Topic 6: Policy Classes for Partially Observed LDS (book chapter 8) - tbd
Friday 12.07: Topic 7: Online Nonstochastic Control with Partial Observation and System Identification (book chapters 9 & 10) - tbd
Friday 19.07: Topic 8: Learning in Unknown LDS (book chapter 11) - tbd
Previous Seminars:
Topic for Summer 2023: Introduction to Online Convex Optimization
Based on Introduction to Online Convex Optimization, Elad Hazan, 2021 (link)
Online Convex Optimization (OCO) considers optimization as a process. In many practical applications, the environment is so complex that it is not feasible to lay out a comprehensive theoretical model and use classical algorithmic theory and mathematical optimization. It is necessary, as well as beneficial, to take a robust approach, by applying an optimization method that learns as more aspects of the problem are observed. This view of optimization as a process has become prominent in various fields, which has led to spectacular successes in modeling and systems that are now part of our daily lives.
The growing body of literature of machine learning, statistics, decision science, and mathematical optimization blurs the classical distinctions between deterministic modeling, stochastic modeling, and optimization methodology. This seminar continues this trend by studying a prominent optimization framework whose precise location in the mathematical sciences is unclear: the framework of online convex optimization (OCO), which was first defined in the machine learning literature. The metric of success is borrowed from game theory, and the framework is closely tied to statistical learning theory and convex optimization.
This seminar will provide an introduction to the concept or Online Convex Optimization, which requires a solid mathematical concepts related to convex optimization and Markov decision processes.
We will roughly cover the following topics:
Basic concepts in convex optimization (provided by myself during the first two weeks)
First order algorithms for online convex optimization
Second order methods
Regularization
Bandit convex optimization
Projection-free algorithms
Games, duality and regret
Learning theory, generalization and online convex optimization
Learning in changing environments
Boosting and regret
This seminar will be based on the following book:
1) Introduction to Online Convex Optimization, Elad Hazan, 2021 (link)
Prerequisites
Calculus and linear algebra: Familiarity with basic matrix manipulations and concepts from calculus (e.g., differentiability, gradient, continuity)
Pleasure with mathematically rigorous statements: Sufficient mathematical maturity regarding proof techniques (direct proof, proof by contradiction, composition)
Basic knowledge on probability: Familiarity with the following concepts: event, random variable, probability density function, cumulative distribution function, conditional probability, independence, expected value, variance, etc.
Logistics
Seminar: Fridays 10:00 - 11:30, room P601
Grade: Based on your presentation and prepared report (5-8 pages)
Schedule
Friday 14.04: Introduction (book chapter 1) - Tobias Sutter & distribution of topics
Friday 21.04: Basic concepts of convex optimization (book chapter 2) - Tobias Sutter
Friday 28.04: Self study preparation time
Friday 05.05 Topic 1: First order algorithms for online convex optimization (book chapter 3) - Tobias Sutter
Friday 12.05: Topic 2: Second order methods (book chapter 4) - Tobias Sutter
Friday 19.05: Topic 3: Regularization (book chapter 5) - Tobias Sutter
Friday 26.05: Topic 4: Bandit convex optimization (chapter 6) - Eva Isakeit
Friday 02.06: break - no seminar
Friday 09.06: Holidays
Friday 16.06: Topic 5: Projection-free algorithms (chapter 7) - Annika Treutle
Friday 23.06: Topic 6: Games, duality and regret (chapter 8) - Daniel Schwarzkopf
Friday 30.06: Topic 7: Learning theory, generalization and online convex optimization (chapter 9) - Christopher Ries
Friday 07.07: Topic 8: Learning in changing environments (chapter 10) - Manuel Schmidt
Friday 14.07 Topic 9: Boosting and regret (chapter 11) - Tobias Sutter
Friday 21.07: Special guest lecture - tbd
Topic for Winter 2022/2023: An Introduction to Reinforcement Learning
To define reinforcement learning (RL) it is first necessary to define automatic control. Examples in your everyday life may include the cruise control in your car, the thermostat in your air-conditioning, refrigerator and water heater, and the decision making rules in a modern clothes dryer. There are sensors that gather data, a computer to take the data to understand the state of the “world” (is the car traveling at the right speed? Are the towels still damp?), and based on these measurements an algorithm powered by the computer spits out commands to adjust whatever needs to be adjusted: throttle, fan speed, heating coil current, or ... More exciting examples include space rockets, artificial organs, and microscopic robots to perform surgery. The dream of RL is automatic control that is truly automatic; without any knowledge of physics or biology or medicine, an RL algorithm tunes itself to become a super controller: the smoothestride into space, and the most expert micro-surgeon!
This Seminar will provide an introduction to the concept or RL, which requires a solid mathematical understanding of the underlying optimal control problem and Markov decision processes.
We will roughly cover the following topics:
Control crash course (provided by myself during the first two weeks)
Markov Decision processes
Dynamic Programming
Temporal Difference Learning
Q-Learning
Variants of Q-Learning
Advanced topics
This seminar will be based on the following two books:
1) Control Systems & Reinforcement Learning, Sean Meyn, 2022 (link)
2) Reinforcement Learning: An Introduction, Richard Sutton & Andrew Barto, 2015 (link)
Prerequisites
Calculus and linear algebra: Familiarity with basic matrix manipulations and concepts from calculus (e.g., differentiability, gradient, continuity)
Pleasure with mathematically rigorous statements: Sufficient mathematical maturity regarding proof techniques (direct proof, proof by contradiction, composition)
Basic knowledge on probability: Familiarity with the following concepts: event, random variable, probability density function, cumulative distribution function, conditional probability, independence, expected value, variance, etc.
Logistics
Seminar: Mondays 15:15 - 16:45, room P601
Grade: Based on your presentation and prepared report
Schedule (tbd)
Monday 24.10: Control crash course by Tobias Sutter & distribution of topics
Monday 31.10: Control crash course by Tobias Sutter
Monday 7.11: Self study preparation time
Monday 14.11 Self study preparation time
Monday 21.11: Markov Decision Processes (Meyn Section 7.1, Sutton&Barto Section Section 3) by Tim Kleinlein
Monday 28.11: Dynamic Programming (Sutton&Barto Section 4) by Matthias Heni
Monday 5.12: Watkin's Q-learning (Meyn Section 9.6, Sutton&Barto Section 6.5) by Samet Taskin
Monday 12.12: Interlude on Dynamic Programming by Tobias Sutter
Monday 19.12: Q-learning variants (Sarsa - Barton&Sutton Section 6.4, Double Q-learning - Barton&Sutton Section 6.7) by David Katterman
Monday 26.12: Break
Monday 2.1: Break
Monday 9.1: Stochastic Approximation (Meyn Section 8) by Vincent Uhse
Monday 16.1: no seminar
Monday 23.1 Special guest lecture - Regularized Q-learning through Robust Averaging by Peter Schmitt-Förster
Monday 31.1: Special guest lecture - A Robust Optimisation Perspective on Counterexample-Guided Repair of Neural Networks by David Boetius
Topic for Summer 2022: Fairness and Machine Learning - Limitations and Opportunities
In the last years, Machine Learning has made impressive progress and has entered socio-technical systems such as video surveillance and automated resume screening. At the same time, there has been increased public concern about the impact of digital technology on society. These two trends have led to the emergence of fairness, accountability and transparency in socio-technical system as a rapidly growing research field.
This Seminar aims to address the issue of fairness in algorithmic decision making in a principled manner. While we will not have an all-encoompassing formal definition of fairness, we will study current practices of Machine Learning aiming to achieve specific notations of fairness.
We will roughly cover the following topics:
Introduction
Classification
Causality
Testing Discrimination in Practice
A Broader View of Discrimination
Advanced Topics
The textbook we will use for this seminar is FAIRNESS AND MACHINE LEARNING Limitations and Opportunities by Solon Barocas, Moritz Hardt, Arvind Narayanan
Logistics
Seminar: Friday 11:45 - 13:15, room L829
Grade: Based on your presentation and prepared report
Schedule
Friday 15.4: No seminar (Good Friday)
Friday 22.4: Self study read Chapter 1 (Introduction) of the fairness book (p. 9 - p. 32)
Friday 29.4: Frist Seminar event - lecture provided by Tobias Sutter & distribution of topics
Friday 6.5 Lecture by Tobias Sutter on classification (report)
Friday 13.5: Self study preparation time
Friday 20.5: Self study preparation time
Friday 27.5: Causality 1 (p.77 - 97) by Andreas Kahabka (report)
Friday 3.6: Causality 2 (p.97-119) by Julian Bauer (report)
Friday 10.6: Part 1: Traditional tests for discrimination (p.119-136) by Jonas Bachmann (report)
Friday 17.6: Break
Friday 24.6: Part 2: Testing discrimination in algorithmic settings (p.136-154) by Jan de Boer (report)
Friday 1.7: A broader view on discrimination (p.157-187) by Theodor Gutschlag (report)
Friday 8.7: Self study - Datasets (p.187-219)
Friday 15.7 Special guest lecture by Felix Petersen
Friday 22.7: Advanced topics (reading material to be provided) by David Boetius (report)