Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Randomness in Complexity (24h, 3 ECTS)

Course manager: Frédéric Magniez (IRIF)

Course Outline 2020-2021

Main topics

  • Algorithmic aspects of Machine Learning beyond worst case

Teachers in 2021-22


  • 10 lectures of 2.5 hours each (see schedule)
  • Lectures will be on Friday 13h15, room 1002, starting September 17.
  • Course Language: Some lectures will be in English, and others in French with English upon request. Homework assignments and exams will be available in English and can be written in either English or French.
  • The final course grade will be the average of two grades:
    1. One grade results from a 3-hour final exam on November 26 at 12h45 in Room 2035. The exam questions will be written in English and the answers may be written in French or in English, at the preference of the student taking the exam. All handwritten notes are allowed during the exam, as well as printouts of course notes provided on this webpage.
    2. The other grade evaluates a report and presentation on December 3rd at 12:45 in Room 2035 on a topic to be chosen by the student mid-course from a list of possible topics. The students will work in pairs. It can be in French or in English, at the preference of the students.
  • Some optional one homework assignment will be given during the course.


The common thread of the course is the use of randomness in algorithms and complexity. This year, the course will center on topics relevant to theoretical machine learning.

Lectures Outline (TBA)

  1. September 17: Non-negative matrix factorization: NP-hardness [1], algorithm for the separable case [2], application to full rank separable topic modeling [3].
  2. September 24: Non-negative matrix factorization (continued).
  3. October 1: Community detection, Block stochastic model, spectral clustering [4].
  4. October 8: Dictionary learning. The full rank case [5]. The incoherent, overcomplete case [6].
  5. October 15: Approximate dense instances of max cut [7].
  6. October 22: Introduction to statistical learning theory. Empirical risk minimization. Optimization and generalization [8].
  7. October 29: Stability of stochastic gradient descent [9].
  8. November 5: Basics of continuous optimization [10].
  9. November 12: Convergence of SGD for overparametrized deep neural networks. Neural tangent kernels [11].
  10. November 19: Convex optimization over non-convex domains. Compressed sensing and sparse recovery [12].

[1] S. Vavasis. On the complexity of nonnegative matrix factorization. SIAM Journal on Optimization, pages 1364-1377, 2009.
[2] Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra: Computing a Nonnegative Matrix Factorization - Provably. SIAM J. Comput. 45(4): 1582-1611 (2016).
[3] Sanjeev Arora, Rong Ge, Yoni Halpern, David M. Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu: Learning topic models - provably and efficiently. Commun. ACM 61(4): 85-93 (2018).
[4] F. McSherry. Spectral partitioning of random graphs. In FOCS, pages 529–537, 2001.
[5] D. Spielman, H. Wang and J. Wright. Exact recovery of sparsely-used dictio- naries. Journal of Machine Learning Research, 2012.
[6] Sanjeev Arora, Rong Ge, Ankur Moitra: New Algorithms for Learning Incoherent and Overcomplete Dictionaries. COLT 2014: 779-806.
[7] Sanjeev Arora, David R. Karger, Marek Karpinski: Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. J. Comput. Syst. Sci. 58(1): 193-210 (1999).
[8] Moritz Hardt: Generalization in Overparametrized Models. Beyond the Worst-Case Analysis of Algorithms, Chapter 22.
[9] Moritz Hardt, Benjamin Recht, Yoram Singer: Train faster, generalize better: Stability of stochastic gradient descent. ICML 2016.
[10] Sébastien Bubeck: Convex Optimization: Algorithms and Complexity.
[11] Simon S. Du, Xiyu Zhai, Barnabas Poczos, Aarti Singh. Gradient Descent Provably Optimizes Over-parameterized Neural Networks. ICLR 2019.
[12] Prateek Jain, Ambuj Tewari, Purushottam Kar: On Iterative Hard Thresholding Methods for High-dimensional M-Estimation. NIPS 2014.

Relevant Courses


Basics of complexity theory (classes P, NP, etc.), of undergraduate-level algorithms, and of probability theory.


Internships in the area of Randomness in Complexity are available. Please contact the Algorithms and Complexity group of IRIF


Équipe pédagogique

S. PérifelMCParis 7IRIF
M. de RougemontPRParis 2IRIF
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA