Fiches de cours 2017-2018


Advanced Topics in Machine Learning


Lecturer(s) :

Cevher Volkan




Every 2 years


Every 2 years. Next time: Spring 2018


This course describes theory and methods to address three key challenges in data sciences: estimation, prediction, and computation. We use convex analysis and methods as a common connecting theme, and illustrate the main ideas on concrete applications from machine learning and signal processing.


Lecture 1

Overview of the course. Learning-based compressive subsampling. Introduction to submodularity, examples, and properties.

Lecture 2

Discrete optimization. Submodular function maximization. The greedy algorithm. Relations between submodularity and convexity. The Lovazs extension.

Lecture 3

Introduction to structured sparsity. Convex relaxation by biconjugation. Structured sparsity via submodular functions.

Lecture 4

Integer and linear programming. Structured sparsity via totally unimodular constraints. Robust submodular function maximization. The Saturate algorithm.

Lecture 5

Stochastic optimization. Stochastic subgradient method. Stochastic proximal method. Stochastic accelerated methods.

Lecture 6

Variance reduction. Coordinate descent methods for smooth objectives.

Lecture 7

Coordinate descent methods for composite functions. Coordinate descent primal-dual algorithms. Randomized Linear Algebra. Randomized matrix decompositions. Comparison to classical methods.

Lecture 8

Randomized Linear Algebra. Row extraction method. Power method. Column selection methods. Stochastic quasi-Newton Method.

Lecture 9

Introduction to statistical learning theory. Statistics vs statistical learning. Approximation error. Excess risk, Hoeffding's inequality.

Lecture 10

Concentration of measure inequalities. Chernoff-type bounds. Azuma-Hoeffding inequality. Bounded differences inequality.

Lecture 11

Uniform Convergences in Statistical Learning Theory. Classical VC Theory for Binary Classification.

Lecture 12

Project presentations.''''''''''


Optimization, machine learning, signal processing, statistics.

Learning Prerequisites

Required courses

Multivariable calculus, linear algebra.

Recommended courses

Probability theory.

Learning Outcomes

By the end of the course, the student must be able to:

Assessment methods




In the programs

  • Electrical Engineering (edoc), 2017-2018
    • Semester
    • Exam form
    • Credits
    • Subject examined
      Advanced Topics in Machine Learning
    • Lecture
      36 Hour(s)
    • Practical work
      40 Hour(s)

Reference week

Exercise, TP
Project, other


  • Autumn semester
  • Winter sessions
  • Spring semester
  • Summer sessions
  • Lecture in French
  • Lecture in English
  • Lecture in German