
Main topics
Teachers in 202122
Organization
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:
One grade results from a 3hour 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.
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 midcourse 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.
September 17: Nonnegative matrix factorization: NPhardness [1], algorithm for the separable case [2], application to full rank separable topic modeling [3].
September 24: Nonnegative matrix factorization (continued).
October 1: Community detection, Block stochastic model, spectral clustering [4].
October 8: Dictionary learning. The full rank case [5]. The incoherent, overcomplete case [6].
October 15: Approximate dense instances of max cut [7].
October 22: Introduction to statistical learning theory. Empirical risk minimization. Optimization and generalization [8].
October 29: Stability of stochastic gradient descent [9].
November 5: Basics of continuous optimization [10].
November 12: Convergence of SGD for overparametrized deep neural networks. Neural tangent kernels [11].
November 19: Convex optimization over nonconvex domains. Compressed sensing and sparse recovery [12].
[1] S. Vavasis. On the complexity of nonnegative matrix factorization. SIAM Journal on Optimization, pages 13641377, 2009.
[2] Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra: Computing a Nonnegative Matrix Factorization  Provably. SIAM J. Comput. 45(4): 15821611 (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): 8593 (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 sparselyused 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: 779806.
[7] Sanjeev Arora, David R. Karger, Marek Karpinski: Polynomial Time Approximation Schemes for Dense Instances of NPHard Problems. J. Comput. Syst. Sci. 58(1): 193210 (1999).
[8] Moritz Hardt: Generalization in Overparametrized Models. Beyond the WorstCase 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 Overparameterized Neural Networks. ICLR 2019.
[12] Prateek Jain, Ambuj Tewari, Purushottam Kar: On Iterative Hard Thresholding Methods for Highdimensional MEstimation. NIPS 2014.
The following is a coherent list of courses on the thematic 'Algorithms and Complexity'.
Basics of complexity theory (classes P, NP, etc.), of undergraduatelevel algorithms, and of probability theory.

Beyond the WorstCase Analysis of Algorithms, edited by Tim Roughgarden, Cambridge University Press, 2020
F. Magniez  DR  CNRS  IRIF 
C. Mathieu  DR  CNRS  IRIF 
S. Périfel  MC  Paris 7  IRIF 
A. Rosen  DR  CNRS  IRIF 
M. de Rougemont  PR  Paris 2  IRIF 
A. Vladu  CR  CNRS  IRIF 
