Veranstaltung |
Wochentag |
Termin |
Ort |

042527 (Übung: 042528) | Montag (Übung: Mittwoch) | 10.15 - 12.00 | Otto-Hahn-Str. 12 - Raum 1.056, Campus Nord |

- Module description: pdf
- Language: English
- Lecturer: Dr. Sangkyun Lee
- Attendance to Übung is REQUIRED.
- Office Hour (lecturer): Thursday 13:00-14:00, LS8, OH 12, Raum 4.023 (or by appointments)

The schedule is quite tight due to my relocation in Feb 2017. We'll consider a way to compensate the tight schedule (to be discussed in the class)

- Midterm: 19.12.2016 (Mon)
~~21.12.2016 (Wed)~~in-class : MIN, AVG, MAX = 26, 38.25, 49 - Final exam: 16.02.2017 (Thurs 10:15-13:00 OH12 R1.056) : MIN, AVG, MAX = 22, 40.9, 47.5

In this lecture we will learn theories and algorithms of numerical optimization. We study the mathematical structure of various optimization problems to design efficient algorithms. The structure is investigated by accessing the zero-th order (function values), the first order (derivatives), and the second order information (Hessians) about the objective function, as well as by looking into the geometry of constraints. We discuss constrained and unconstrained optimization problems in continuous spaces, focusing on understanding motivations behind technical details and analyzing convergence rate / algorithm complexity algorithms. Fundamental concepts such as optimality and duality will be discussed in detail, which also become popular tools to better understand algorithms in many areas including machine learning, data mining, and statistics. The importance of smoothness and convexity will be elaborated, especially in connection to regularization problems in high dimensions. Some advanced topics from non-smooth, large-scale, or matrix optimization will be included if time permits. Homework assignments will be given to check theoretical and practical understanding of techniques. Some assignments would involve programming in the Julia language. Tutorials about the language will be given in Ubung for newbies.

The aim of this lecture is to provide students with understanding of fundamental concepts and techniques in optimization in an advanced level, so that students can understand and see how to use and design efficient numerical optimization algorithms for their own research problems.

- Numerical Optimization, J. Nocedal and S. Wright, 2nd Ed, Springer, 2006
- Introductory Lectures on Convex Optimization, Y. Nesterov, Springer, 2004
- Nonlinear Programming, D. P. Bertsekas, 2nd Ed., Athena Scientific, 2003 (2nd printing)
- Convex Optimization, S. Boyd and L. Vandenberghe, Cambridge, 2004 [pdf]

- Lecture notes (incrementally updated): [pdf]

- (17.10) Lecture 0: Introduction
- > (optional reading) Intro to compressed sensing pdf
- For other lectures, see the schedule on the calendar below
- (12.12) Stochastic gradient descent link
- (09.01) Proximal gradient descent link
- (01.02) ADMM link
- (06.02) Duality link

- (19.10) Introduction to Julia
- (26.10) Intro to JuMP 1/2
- (2.11) Intro to JuMP 2/2

- [15] Papers (you must reserve the paper to present by email. First-come first-served).
- > Robust Stochastic Approximation Approach to Stochastic Programming, SIOPT 2009: the idea has been already discussed in class: do in-depth comparison between classical vs. robust
- > ADAGRAD, JMLR 2011
- > SAG, NIPS 2012 (reserved by Kevin)
- > SDCA, JMLR 2013 (reserved by Lea)
- > SVRG, NIPS 2013
- > SAGA, NIPS 2014 (reserved by Lukas Heppe)
- > ADAM, ICLR 2015 (reserved by Thilo)
- > Stochastic quasi-Netwon, AISTATS 2007
- > SFO, ICML 2014 (reserved by Stefan Hesse)

- Fully theoretical discussion will be difficult and not helpful. I suggest some theoretical + inituitive explanation + discuss performance

- [+5 Extra] Optionally, show a demo using your own Julia implementation (e.g. showing the benefit of the algorithm), and make your code as open-source on github.

- Each paper talk will be graded for up to 15 (+5 optional) points

- The following will be more difficult to understand

- ... or you can choose a paper with similar topics

- [10] Julia topics:
- Advanced language features, debugging, parallelization, GPU computing, or even plotting data. Some interesting topics can be found from JuliaCon 2016 videos.

- Each Julia talk will be graded for up to 10 points

- A homework will be given approx. every two weeks. Some will require implementing algorithms in Julia.
- Exercise questions are at the end of each chapter of the lecture notes.
- Homeworks will NOT be graded: you don't need to submit your homeworks
- You need to present at least 2 correction solutions at homework discussions, in total: this is REQUIRED for passing Ubung and being qualified for the final exam. I will ask volunteers at each discussion session, but you can tell me beforehand what you want to present
- Dicussion of homework questions with other students is strongly encouraged. You can ask for help to other students if you have difficulties.

- > Homework 1 (due 9.11, NOT 2.11): exercises 1.4, 2.1(a), 2.2, and 2.3. And solve the Sudoku problem using JuMP (my Sudoku solution)
- > Homework 2 (due 23.11): exercises 3.1, 3.2, 4.1, 4.4, 4.5. In addition, 3.3 and 4.2 (since we've almost solved 3.1. I'll still ask for volunteers for 3.1. Updated 09.11) Some Julia solutions
- > Homework 3 (due 14.12): exercises 5.2, 6,1, 6.2, 8.1, 8.2, 8.3 (MNIST data set: download)
- > Homework 4 (due 18.1): ex 10.1, 10.2, 11.1, 11.2, 12.1
- > Homework 5 (due 25.1): ex 12.2, 12.3, 12.4, 12.5 (lecture note is updated)
- > Homework 6 (due 8.2): ex 12.4, 13.1, 14.1, 14.2, 14.3