Weekly outline

• General
  

  General

  Οι συναντήσεις του Corelab study group για το ακαδ. έτος 2023 - 2024 γίνονται κάθε Δευτέρα 15:00 - 17:00. 

  Εδώ θα ανακοινώνονται το πλάνο διαλέξεων καθώς και ενδεικτική και πρόσθετη βιβλιογραφία για κάθε διάλεξη.  

  • Ανακοινώσεις Forum
• Monday, 16 October
  

  Monday, 16 October

  Βιβλιογραφία για Bandits:

  • Introduction to Multi-Armed Bandits [Slivkins]: https://arxiv.org/pdf/1904.07272.pdf
    
  • Bandit Algorithms [Lattimore & Szepesvari]: https://tor-lattimore.com/downloads/book/book.pdf

  
  

  Εισαγωγή & Stochastic Bandits:

  • Κεφάλαιο 1 από Slivkins
    
  • Κεφάλαια 4, 5, 6, 7 από Lattimore & Szepesvari
    
• Monday, 23 October
  

  Monday, 23 October

  Full feedback mode, Regret analysis, Adversarial reward,

  Majority vote Algorithm. 

  Weighted Majority Algorithm.

  Lecture Notes:
  

  1. https://www.cs.umd.edu/~slivkins/CMSC858G-fall16/Lecture7_part1.pdf
     
  2. https://www.cs.umd.edu/~slivkins/CMSC858G-fall16/lecture7_part2.pdf
• Monday, 30 October
  

  Monday, 30 October

  Hedge. Exp3.
  

  Lecture Notes:

  1. https://www.cs.umd.edu/~slivkins/CMSC858G-fall16/lecture7_part2.pdf
     
  2. https://www.cs.umd.edu/~slivkins/CMSC858G-fall16/lecture8-both.pdf

  
  

  Βιβλιογραφία:

  
  

  1. Κεφάλαια 5, 6 από Slivkins
  2. Κεφάλαιο 11 από Lattimore & Szepesvari
     
• Monday, 6 November
  

  Monday, 6 November

  Βιβλιογραφία για Online Convex Optimisation:
  

  A Modern Introduction to Online Learning [Orabona]: https://arxiv.org/pdf/1912.13213.pdf
  
  

  Introduction, Online Subgradient Descent, Lower Bound for Online Linear Optimisation: Κεφάλαια 1, 2, 5.1 από Orabona
  
• Monday, 13 November
  

  Monday, 13 November

  Follow the Regularized Leader:

  Lecture Notes:

  • https://itcs.sufe.edu.cn/_upload/article/files/ab/9a/36a9f16d43af80af46a4bee8a4e4/a6219795-a4bf-4081-89f2-75d351f97562.pdf
    
  • https://itcs.sufe.edu.cn/_upload/article/files/ab/9a/36a9f16d43af80af46a4bee8a4e4/d2f406a7-23e5-4248-b6b5-d455192d628f.pdf

  
  

  Βιβλιογραφία:

  • Κεφάλαια 7.1, 7.2 από Orabona
    
• Monday, 20 November
  

  Monday, 20 November

  Follow the Perturbed Leader [Kalai & Vempala]:
  

  https://www.sciencedirect.com/science/article/pii/S0022000004001394
  
• Monday, 27 November
  

  Monday, 27 November

  Introduction to Prophet Inequalities

  
  

  • Σημειώσεις Roughgarden για το κλασικό Prophet Inequality και τη σύνδεση του με Revenue near-optimal μηχανισμούς: https://timroughgarden.org/f13/l/l6.pdf

  
  

  • Παρουσίαση Lucier: https://courses.engr.illinois.edu/cs580/fa2021/Slides/prophet.pdf

  
  

  • To paper [Rubinstein, Wang, Weinberg] που πετυχαίνει το 1/2 αλλά με ένα δείγμα: https://arxiv.org/abs/1911.07945
• Monday, 4 December
  

  Monday, 4 December

  Βιβλιογραφία για Approximation Algorithms:

  • The Design of Approximation Algorithms [Williamson & Shmoys]: 
    https://www.designofapproxalgs.com/
    

  
  

  Εισαγωγή στο (metric) uncapacitated facility location

  Εισαγωγή στο primal dual 

  Κεφάλαια: 4.5, 5.8, 7.1 (αναφορά) από [Williamson & Shmoys]

  
  
• Monday, 11 December
  

  Monday, 11 December

  Approximate Nearest Neighbor

  Section 3.2 από αυτό το paper: https://theoryofcomputing.org/articles/v008a014/v008a014.pdf
  

  Πιο formally η ιδέα των random hyperplanes στο section 3 αυτού του paper: https://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf
  
• Monday, 18 December
  

  Monday, 18 December