Master M2 MVA: Convex Optimization, Algorithms and Applications.

Description

The objective of this course is to learn to recognize, transform and solve a broad class of convex optimization problems arising in various fields such as machine learning, finance or signal processing. The course starts with a basic primer on convex analysis followed by a quick overview of convex duality theory. The second half of the course is focused on algorithms, including first-order and interior point methods, together with bounds on their complexity. The course ends with illustrations of these techniques in various applications.

Course organization

  • Location and time: 13:00 - 16:00, salle Dussane, ENS Paris, 45 rue d'Ulm, 75005 Paris.

    • Oct. 2022: 3, 10, 17, 31. (Warning: the Oct. 31 will be offline. Please follow the “Applications, SDP Applications and l1 Penalties” videos offline.)

    • Nov. 2022: 7, 14.

Organisation

The course will be live but course videos from 2020 are available below.

Notes

Program

The course is split in three parts.

  • Modeling

    • Convex sets, functions and problems

    • Duality

  • Algorithms

    • Interior point methods

    • Complexity

    • First-order methods, acceleration

  • Applications

    • Machine learning and statistics

    • Signal processing

    • Combinatorial problems

    • Finance

References

Exercices

Many of the exercises are taken from the textbook by Boyd et Vandenberghe. We will be using Gradescope to grade assignments. In order to submit your work, you must create a Gradescope account. Please ensure you do so with your full name. You will then be able to join the course using course number Y7GDY6 and use “√©cole normale sup√©rieure” as the school (with accents). Late homework will not be graded.

  • DM1: Due Monday October 17 before class. Homework 1

  • DM2: Due Monday October 31 before class. Homework 2

  • DM3: Due Monday November 28. Homework 3. Please submit your code on Gradescope. Please submit your code as a PDF. For Jupyter notebooks, this can be done by downloading the notebook as a PDF. Otherwise a screenshot of your code is acceptable. Please ensure the theoretical results, plots and comments on numerical results are easily identifiable and clearly readable. For numerical exercises, you can use either Julia, Python or MATLAB.

Exam

Final exam, on Monday Dec. 5 2022, 13:00-16:00, salle 1G58 (grand amphi) ENS Paris-Saclay.
Closed book. You are allowed one page of notes (recto-verso). The exam will be mostly focused on chapters 1-5 of the textbook (up to duality) Final exam 2016.