Numerical Optimization
Veranstaltung |
Wochentag |
Termin |
Ort |
042527 (Übung: 042528) |
Montag (Übung: Mittwoch) |
10.15 - 12.00 |
Otto-Hahn-Str. 12 - Raum 1.056, Campus Nord |
Lecture Information
- 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)
Exams:
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
Registration form:
link
Content:
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.
Aims:
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.
References:
- 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:
The lecture notes will be updated: check before each lecture. Questions / correcting errors will be welcomed.
See the calendar below for lecture topics and schedule.
- 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
Ubung:
Student Presenation
Each student can give a presentation (30-45min) about the following papers or some features of Julia.
- [15] Papers (you must reserve the paper to present by email. First-come first-served).
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
- > 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)
The following will be more difficult to understand
- > ADAM, ICLR 2015 (reserved by Thilo)
- > Stochastic quasi-Netwon, AISTATS 2007
- > SFO, ICML 2014 (reserved by Stefan Hesse)
... 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
Homeworks:
- 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
Lecture Schedule:
The schedule may change, so please check often. Please ignore the lecture times on the calendar.