Teaching

I had the opportunity to teach in the Master’s program MPRI. My lectures were conducted under the course Randomness in Complexity, though the topics varied each year.

Fall 2022 – Continuous Methods in Combinatorial Optimization

Course Page

Topics Covered:

  • Basics of optimization. Learning with experts. Algorithmic applications (Plotkin-Shmoys-Tardos, oblivious routings).

  • J-trees, dynamic minimum spanning tree. Fast graph cut approximators using J-trees.

  • Iterative methods for solving linear systems. Preconditioning.

  • Laplacian matrices and linear systems. Equivalence to electrical flows.

  • Matrix Chernoff and spectral sparsification. Augmented tree preconditioners.

  • Algorithmic graph theory using electrical flows. Interior point methods.

Fall 2021 – Algorithmic aspects of Machine Learning Beyond the Worst Case

Co-instructors: Claire Mathieu

Topics Covered:

  • Non-negative matrix factorization. NP-hardness, algorithm for the separable case, application to full rank separable topic modeling.

  • Community detection, stochastic block model, spectral clustering.

  • Dictionary learning. The full rank case. The incoherent, overcomplete case.

  • Approximate dense instances of max cut.

  • Introduction to statistical learning theory. Empirical risk minimization. Optimization and generalization.

  • Stability of stochastic gradient descent.

  • Basics of continuous optimization.

  • Convergence of SGD for overparametrized deep neural networks. Neural tangent kernels.

  • Convex optimization over non-convex domains. Compressed sensing and sparse recovery.

Fall 2020 – Randomness in Complexity

Co-instructors: Michel de Rougemont, Claire Mathieu

Topics Covered:

  • Complexity classes BPP, IP and PCP. Introduction to Testers and streaming algorithms. Blum-Luby-Rubinfeld linearity test, proof with the discrete Fourier transform.

  • Communication complexity, 1-way, deterministic and randomized, public and private coins. Index and Disjointness are hard, using the distributional complexity.

  • Tester for regular languages. Lower bounds for the number of queries for k-linearity and monotonicity, using a reduction to Disjointness.

  • Streaming algorithms - approximation of the $F_0$ and $F_2$ moments. $\Omega(n)$ space lower bounds for $F_{\infty}$. Online algorithms - bipartite matching.

  • The random order model for analyzing online algorithms. Secretary and matroid secretary problems. Online facility location.

  • Pricing with an unknown distribution with bounded valuations, and application to auctions. Instance optimality, definition and analysis.

  • Online paging. Competitive algorithms, deterministic and randomized. From discrete to continuous – weighted online paging via mirror descent. Paper.

  • Sparse recovery. Recovering a sparse signal from few measurements via iterative methods, iterative hard thresholding. General framework - minimizing convex functions over non-convex domains. Matrix completion. Paper, Wikipedia page.