LTI
LTI

Seminar: The Multiplicative Weights Update Method

  • Leitung:
    Prof. Dr. Harald Räcke
  • Modul:
  • Bereich:
    2 SWS Seminar im Bereich Informatik III (Theoretische Informatik)
  • Summary

    The multiplicative weights update method is a meta-algorithm that maintains a distribution over a certain set (e.g. of candidate solutions to a problem) and then uses a multiplicative update rule to changes these weights. This method has been rediscovered in various different forms in many very diverse application areas within mathematics and computer science. It is used in machine learning, game theory, online algorithms, theoretical biology, convex optimization, linear programming and approximation algorithms. In this seminar we will cover this algorithm in its various forms and extensions and learn how it can be applied to specific application areas.

    The seminar talks can be presented in German or English, depending on the preference of the students.


Topics

  1. Machine Learning I
    [R 96], [L 88]
  2. Machine Learning II: Boosting
    [S 90]
  3. Online Decision Making
    [AH 05], [AHK 12], [Z 03]
  4. Biology
    [MP 15], [CLPV 14]
  5. Game Theory
    [GK 95], [FS 99]
  6. Geometry
    [CW 89], [C 00], page 6 and 124
  7. Approximation Algorithms
    [Y 95]
  8. Optimization
    [Y 01]
  9. Solving Multicommodity Flows
    [GK 98]

Literature

  • [AH 05]
    Amit Agarwal and Elad Hazan
    Efficient algorithms for online game playing and universal portfolio management
    ECCC, 2005.
  • [MP 15]
    Reshef Meir and David Parkes
    Sex, Evolution, and the Multiplicative Weights Update Algorithm
    AAMAS, 2015.
  • [CLPV 14]
    Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani
    Algorithms, games, and evolution
    PNAS 2014.
  • [R 96]
    Raúl Rojas
    Neural Networks -- A Systematic Introduction (ISBN 978-3-540-60505-8)
    • Chapter 3 Weighted networks - the perceptron
    • Chapter 4 Perceptron learning of Neural Networks
    Springer 1996.
  • [C 00]
    Bernard Chazelle
    The Discrepancy Method
    Cambridge University Press 2000.
  • [L 88]
    Nick Littlestone
    Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm
    Machine Learning 285–318(2), 1988.
  • [S 90]
    Robert E. Schapire
    The strenghs of weak learnability
    Machine Learning 197-227(5), 1990.
  • [CW 89]
    Bernard Chazelle and Emo Welzl
    Quasi-optimal range searching in spaces of finitet VC-dimension
    Discrete and Computational Geometry, 1989
  • [Z 03]
    Martin Zinkevich
    Online convex programming and generalized infinitesmal gradient ascent
    ICML, 2003.
  • [AHK 12]
    Sanjeev Arora, Elad Hazan, and Satyen Kale
    The Multiplicative Weights Update Method: a Meta-Algorithm and Applications
    Theory of Computing, 2012.
  • [Y 95]
    Neal E. Young
    Randomized rounding without solving the linear program
    SODA 1995.
  • [Y 01]
    Neal E. Young
    Sequential and parallel algorithms for mixed packing and covering
    FOCS 2001.
  • [GK 98]
    Naveen Garg, Jochen Könemann
    Faster and simpler algorithms for multicommodity flow and other fractional packing problems.
  • [GK 95]
    Michael D. Grigoriadis, and Leonid G. Khachiyan
    A Sublinear-Time Randomized Approximation Algorithm for Matrix Games
    Oper. Res. Lett., 1995.
  • [FS 99]
    Yoav Freund and Robert E. Schapire
    Adaptive Game Playing Using Multiplicative Weights
    Games and Economic Behavior, 1999.

July 2022: Jens Quedenfeld completed his doctoral degree.

June 2022: Maximilian Janke completed his doctoral degree.

March 2022: Alexander Eckl completed his doctoral degree.

June 2021: Leon Ladwig completed his doctoral degree.

February 2020: The Program Committee of SWAT 2020 is chaired by Susanne Albers.

February 2020: Susanne Albers is invited speaker at the ACM India Annual Event.

ESA/ALGO 2019 will be organized by Susanne Albers and her group.

May 2019: Susanne Albers is invited speaker at the symposium 50 Years Informatics

July 2019: Susanne Albers is invited speaker at SIROCCO 2019, Italy.

December 2017: Susanne Albers will give keynote address at the Graduation Day, Department of Computer Science at RWTH Aachen University.

April 2017: New Research Training Center AdONE, funded by the German Research Foundation.

Susanne Albers receives ERC Advanced Grant. Press release of the Bavarian State Ministry of the Sciences, Research and the Arts.

August 2016: Susanne Albers is keynote speaker at Euro-Par 2016, Grenoble.

Susanne Albers, Nicole Megow and Andreas S. Schulz will organize MAPSP 2017.

Juni 2016: Susanne Albers gives an invited lecture at the Academy of Sciences and Literature, Mainz.

September 2015: Susanne Albers is invited speaker at MPI-INF – 25th Anniversary. The program features several Turing Award winners, Leibniz Prize winners, Humboldt Prize winners and ERC Grant winners.

June 2015: Susanne Albers is keynote speaker at the 31st International Symposium on Computational Geometry (SOCG15), Eindhoven.

June 2015: Susanne Albers is invited speaker of the tutorial on Network Creation Games: How Does the Internet Form? organized by Erik D. Demaine (MIT) and MohammadTaghi Hajiaghayi (University of Maryland). 16th Conference on Electronic Commerce (EC15), Portland, Oregon.

Lehrstuhl für Algorithmen und Komplexität
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707

E-Mail
News