Weekly outline

• General
  

  General

   

  Το μάθημα για το ακ. έτος 2022-23 αποτελείται από δύο μέρη που διεξάγονται παράλληλα. Το πρώτο μέρος γίνεται σε συνδιδασκαλία με το μάθημα "Προηγμένα Θέματα Αλγορίθμων". Για τις αντίστοιχες διαλέξεις και ασκήσεις παρακολουθείτε παράλληλα την σχετική ιστοσελίδα και εγγραφείτε σε αυτήν. 

  Η τρέχουσα σελίδα αφορά το δεύτερο μέρος, που γίνεται για τους μεταπτυχιακούς φοιτητές και για τους ενδιαφερόμενους προπτυχιακούς.

  
  

  Αντικείμενο και Στόχοι

  Το δεύτερο μέρος του μαθήματος εστιάζει στην εκμάθηση και εξάσκηση σε γενικές και αποτελεσματικές στρατηγικές σκέψης, για την επίλυση μαθηματικών/αλγοριθμικών προβλημάτων. Οι στρατηγικές αυτές είναι ιδιαίτερα χρήσιμες για να λύνουμε προβλήματα που απαιτούν καινούργιες ιδέες, και για τα οποία οι γνωστές τεχνικές αποτυγχάνουν (όπως συμβαίνει στην έρευνα). Η εξάσκηση στις στρατηγικές θα γίνει ταυτόχρονα με την εισαγωγή σας σε βασικές έννοιες και αλγορίθμους κυρτής βελτιστοποίησης (convex optimization), καθώς και σε τεχνικές μείωσης διάστασης (dimension reduction). Θα δείτε πώς ευφυείς ιδέες σε αυτές τις περιοχές προκύπτουν φυσιολογικά, εφαρμόζοντας τις στρατηγικές σκέψης που θα μάθουμε. 

  Ο στόχος είναι μετά το τέλος του μαθήματος, να εφαρμόζετε τις στρατηγικές και σε άλλα μαθήματα, στο προσωπικό σας ανεξάρτητο διάβασμα, στην έρευνα, αλλά και στα περαιτέρω δημιουργικά σας εγχειρήματα.

  
  

  Προαπαιτούμενα
  

  Χρειάζεται να έχετε στερεές βάσεις σε γραμμική άλγεβρα, θεωρία πιθανοτήτων, και ανάλυση πολλών μεταβλητών.

  
  

  Διδάσκοντες
  

  • Δημήτρης Φωτάκης, Καθηγητής (fotakis@cs.ntua.gr)
  • Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
  • Θανάσης Λιανέας, Μεταδιδακτορικός Ερευνητής (lianeas@corelab.ntua.gr)
  • Ορέστης Πλευράκης, Μεταδιδακτορικός ερευνητής (or.plevrakis@gmail.com)

  
  

  Ώρες Γραφείου

  
  

  Ορέστης Πλευράκης: Δευτέρα 15:00-16:30, στην αίθουσα 1.1.29, (Παλαιό) Κτήριο Ηλεκτρολόγων.

  
  

  Βοηθοί Διδασκαλίας

  • Αλβέρτος Καλαβάσης, Υ.Δ.
  • Μαριάννα Σπυράκου, Υ.Δ.

  
  

  Διαλέξεις
  

  • Κάθε Τετάρτη, ώρα 15:00-19:00, στο Νέο Κτήριο Ηλεκτρολόγων, Αίθουσα 009. Το δεύτερο μέρος διαρκεί 15:00-16:00.
    
  • Έναρξη δεύτερου μέρους: 22/3/2023.

  
  

  Προβλήματα

  • 1 πρόβλημα/εβδομάδα.
    
  • Deadline: αρχή της επόμενης διάλεξης.
  • Μετά το deadline θα αναρτάται η λύση στο site με εξήγηση του πώς φτάνουμε σε αυτή μέσω των στρατηγικών.
  • Δείτε επίσης αυτό για οδηγίες σχετικές με τα προβλήματα.

  
  

  (Αναμενόμενα) Θέματα Διαλέξεων

  •  Κυρτά σύνολα, κυρτές συναρτήσεις και βασικές ιδιότητες. Θεώρημα  διαχωριστικού υπερεπιπέδου.
  •  Ο αλγόριθμος Gradient Descent και η ανάλυσή του για strongly-convex  και smooth συναρτήσεις.
  •  Cutting Plane μέθοδοι, και επίλυση γραμμικών προγραμμάτων σε πολυωνυμικό  χρόνο.
  •  Singular Value Decomposition.
  •  Power method για υπολογισμό ιδιοτιμών και ιδιοδιανυσμάτων.
  •  Johnson-Lindenstrauss (JL) μετασχηματισμός.
  •  Spectral methods for the Stochastic Block Model

  
  

  Βιβλιογραφία και Συμπληρωματικό υλικό

  Κυρτή βελτιστοποίηση:

  1. Εξαιρετικές σημειώσεις του Amir Ali Ahmadi [link]
  2. S. Boyd and L. Vandenberghe, Convex Optimization [link]
     
  3. N. Vishnoi, Algorithms for Convex Optimization [link]
  4. Yin Tat Lee, S. Vempala, Techniques in Optimization and Sampling [link]

  
  

  Τεχνικές ελάττωσης διάστασης: σημειώσεις αντίστοιχου μαθήματος στο Princeton [link]
  

  Στρατηγικές σκέψης:

  1. Terence Tao, "Ask yourself dumb questions". Κοιτάξτε και εδώ για περαιτέρω συμβουλές του Tao.
  2. Michael Atiyah, "Advice to a young mathematician". Η άποψή του για τη σημασία των παραδειγμάτων έχει ιδιαίτερο ενδιαφέρον.
  3. Ed Burger, Michael Starbird, "The 5 elements of effective thinking" (εφαρμογή τέτοιων στρατηγικών πέρα απο τα μαθηματικά και τη θεωρητική πληροφορική).

  
  

     

  
  

  • Ανακοινώσεις Forum
  • Υποβολή Διαφανειών Παρουσιάσεων Assignment
• 1η Διάλεξη (22/3)
  

  1η Διάλεξη (22/3)

  • Παρουσίαση 1ης διάλεξης File
• 2η Διάλεξη (29/3)
  

  2η Διάλεξη (29/3)

  • 1ο Πρόβλημα Assignment
  • Λύση 1ου Προβλήματος File
  • Παρουσίαση: ελλειψοειδή, κυρτά σύνολα File
  • Σημειώσεις: γραμμική άλγεβρα και κυρτά σύνολα. File
• 3η Διάλεξη (5/4)
  

  3η Διάλεξη (5/4)

  • Σημειώσεις: παραδείγματα κυρτών συνόλων, απόδειξη θεωρήματος διαχωριστικού υπερεπιπέδου File
  • 2η Εργασία Assignment
  • Λύση 2ης Εργασίας File
• 4η Διάλεξη (26/4)
  

  4η Διάλεξη (26/4)

  • 3o Πρόβλημα Assignment
  • Σημειώσεις: ανάλυση, κυρτές συναρτήσεις File
  • Λύση 3ου Προβλήματος File
• 5η Διάλεξη (3/5)
  

  5η Διάλεξη (3/5)

  • 4ο Πρόβλημα Assignment
  • Σημειώσεις: ιδιότητες κυρτών συναρτήσεων, παραδείγματα, και gradient descent File
  • Παρουσίαση: γραμμικός διαχωρισμός και spam filtering File
  • Λύση 4ου Προβλήματος File
• 6η Διάλεξη
  

  6η Διάλεξη

  • 5ο Πρόβλημα Assignment
  • Παρουσίαση 6ης Διάλεξης. Για όγκους στο R^n, δείτε εδώ. File
  • Σημειώσεις: Ελλειψοειδή, Περιστροφές, SVD File
  • Λύση 5ου Προβλήματος File
• 7η Διάλεξη
  

  7η Διάλεξη

  • Σημειώσεις: Ελλειψοειδής Μέθοδος File
• 8η Διάλεξη
  

  8η Διάλεξη

  • Σημειώσεις 1: ΓΠ με εκθετικά πολλούς περιορισμούς File
  • 6ο Πρόβλημα Assignment
  • Σημειώσεις 2: Ελλειψοειδής μέθοδος για κυρτή βελτιστοποίηση File
  • Λύση 6ου Προβλήματος File
• 9η Διάλεξη
  

  9η Διάλεξη

  • 7ο Πρόβλημα Assignment
  • Σημειώσεις: Ελάττωση διάστασης και εκπλήξεις στις υψηλές διαστάσεις File
  • Gaussians and uniform sampling from the sphere URL

    Άψογο βίντεο του 3b1b που εξηγεί γιατί αν θέλουμε να samplάρουμε ένα διάνυσμα ώστε 1) οι συντεταγμένες να είναι ανεξάρτητες τυχαίες μεταβλητές, και 2) το μοναδιαίο να είναι ομοιόμορφα κατανεμημένο πάνω στη σφαίρα, τότε η γκαουσιανή είναι η μοναδική επιλογή! Το σχετικό απόσπασμα είναι 12:48-22:00. To δείχνει για δύο διαστάσεις, αλλά γενικεύεται και για n.  

    
    

• 10η Διάλεξη
  

  10η Διάλεξη

  • Planted Bisection File

    Σημειώσεις που περιλαμβάνουν και την απόδειξη που δεν προλάβαμε να κάνουμε. Σχετικά sections είναι τα 2 έως 8.

  • Απόδειξη του λήμματος των Johnson και Lindenstrauss File