allensmile/optml_course

EPFL Course - Optimization for Machine Learning - CS-439

EPFL Course - Optimization for Machine Learning - CS-439

Official coursebook information

Lectures: Fri 13:15-15:00 in BC01

Exercises: Fri 15:15-17:00 in BC01

This course teaches an overview of modern mathematical optimization methods, for applications in machine learning and data science. In particular, scalability of algorithms to large datasets will be discussed in theory and in implementation.

Team

• Instructor: Martin Jaggi [email protected]
• Assistants:
  • Anastasia Koloskova [email protected]
  • Sai Praneeth Karimireddy [email protected]
  • Thijs Vogels [email protected]
  • Nicolas El Maalouly [email protected]

Contents:

Convexity, Gradient Methods, Proximal algorithms, Subgradient Methods, Stochastic and Online Variants of mentioned methods, Coordinate Descent, Frank-Wolfe, Accelerated Methods, Primal-Dual context and certificates, Lagrange and Fenchel Duality, Second-Order Methods including Quasi-Newton Methods, Derivative-Free Optimization.

Advanced Contents:

Parallel and Distributed Optimization Algorithms

Computational Trade-Offs (Time vs Data vs Accuracy), Lower Bounds

Non-Convex Optimization: Convergence to Critical Points, Alternating minimization, Neural network training

Program:

Nr	Date	Topic	Materials	Exercises
#1	22.2.	Introduction, Convexity	notes, slides	lab01
#2	1.3.	Gradient Descent	notes, slides	lab02
#3	8.3.	Projected Gradient Descent	notes, slides	lab03
#4	15.3.	Projected, Proximal and Subgradient Descent	notes, slides	lab04
#5	22.3.	Subgradient, Stochastic Gradient Descent	notes, slides	lab05
#6	29.3.	SGD, Non-Convex Optimization	notes, slides	lab06
#7	5.4.	Non-Convex Opt., Newton's Method	notes, slides	lab07
#8	12.4.	Newton & Quasi-Newton	notes, slides	lab08
.	19.4.	easter vacation		-
.	26.4.	easter vacation		-
#9	3.5.	Frank-Wolfe	notes, slides	lab09
#10	10.5.	Coordinate Descent	notes, slides	lab10
#11	17.5.	Duality, Gradient-free methods, Applications	notes, slides	lab11
#12	24.5.	Opt for ML in Practice	notes, slides
#13	31.5.	Mini-Project week

Exercises:

The weekly exercises consist of a mix of theoretical and practical Python exercises for the corresponding topic each week (starting week 2). Solutions to theory exercises are available here, and for practicals in the lab folder.

Mini-project:

An optional mini-project will focus on the practical implementation: Here we encourage students to investigate the real-world performance of one of the studied optimization algorithms or variants, helping to provide solid empirical evidence for some behaviour aspects on a real machine-learning task. The project is optional and done in groups of 2-3 students. If students decide to do the project, and if their project grade exceeds their exam grade, it will count 20% to the final grade. Project reports (3 page PDF) are due May 31st. Here is a detailed project description.

Assessment:

Final written exam in exam session, 20.06.2019 from 08h15 to 11h15 (PO01 Polydôme). Format: Closed book. Theoretical questions similar to exercises. You are allowed to bring one cheat sheet (A4 size paper, both sides can be used), either handwritten or 11 point minimum font size. For practice: exam of 2018.

Links to related courses and materials

• CMU 10-725
• Berkeley EE-227C

Recommended Books

• Convex Optimization: Algorithms and Complexity, by Sébastien Bubeck (free online)
• Convex Optimization, Stephen Boyd and Lieven Vandenberghe (free online)
• Introductory Lectures on Convex Optimization, Yurii Nesterov (free online)