IFT 6169

Theoretical principles for deep learning

Winter 2023 · hybrid, in English

Lectures
Wednesday and Thursday, 9h30-11h15
First class
Thursday, January 12th, 2023
Location
Mila’s Auditorium 2, 6650 Saint-Urbain, first floor (no key card needed); also online
Office hours
Thursday 11:15am-12:00pm, right after class
Instructor
Ioannis Mitliagkas
TAs
Jose Gallego-Posada, Motahareh Sohrabi
Platforms
StudiUM (announcements), Slack (discussion), Gradescope (quizzes and reports)

Description

Research in deep learning produces state-of-the-art results on a number of machine learning tasks. Most of those advances are driven by intuition and massive exploration through trial and error. As a result, theory is currently lagging behind practice. The ML community does not fully understand why the best methods work.

  • Why can we reliably optimize non-convex objectives?
  • How expressive are our architectures, in terms of the hypothesis class they describe?
  • Why do some of our most complex models generalize to unseen examples when we use datasets orders of magnitude smaller than what the classic statistical learning theory deems sufficient?

A symptom of this lack of understanding is that deep learning methods largely lack guarantees and interpretability, two necessary properties for mission-critical applications. More importantly, a solid theoretical foundation can aid the design of a new generation of efficient methods—sans the need for blind trial-and-error-based exploration.

In this class we will go over a number of recent publications that attempt to shed light onto these questions. Before discussing the new results in each paper we will first introduce the necessary fundamental tools from optimization, statistics, information theory and statistical mechanics. The purpose of this class is to get students engaged with new research in the area. To that end, the majority of credit will be given for a class project report and presentation on a relevant topic.

Tentative topics

  • Generalization: theoretical analysis and practical bounds
  • Information theory and its applications in ML (information bottleneck, lower bounds etc.)
  • Generative models beyond the pretty pictures: a tool for traversing the data manifold, projections, completion, substitutions etc.
  • Taming adversarial objectives: Wasserstein GANs, regularization approaches and controlling the dynamics
  • The expressive power of deep networks (deep information propagation, mean-field analysis of random networks etc.)

Prerequisites

This is a graduate class for students who want to engage in theory-driven deep learning research. We will introduce some theoretical tools necessary.

  • Probability
  • Linear algebra
  • Machine learning

Class format and communication

The class is hybrid:

  • In person at Mila’s Auditorium 2 (located at 6650 Saint-Urbain, first floor. No key card needed to access)
  • Online via Zoom
  • Video recordings of lectures will be made available after lectures end.

We will use the class’s Studium to make announcements. We will use a Slack workspace for discussion. Please keep an eye out for an invitation to the Slack. We will use Gradescope for quizzes and report submissions.

If you have something personal/sensitive to discuss, feel free to email me or the TA. Starting your email subject with ‘IFT6169:’ will ensure that your email is not miscategorized.

Registering and auditing

If you want to audit the class, please fill this form. You will get access to the course material, but you will not be able to submit work or be graded.

Evaluation

Component Weight
Class project on a research topic 35%
Paper presentations 25%
Quizzes 20%
Midterm exam 15%
Class participation 5%

Use this LaTeX template for scribing.

Schedule and materials

Introduction

  1. Jan 12

    Class introduction

    slidesold quiz

Crash course in optimization

For the first half of the class we will be closely following the previous iteration of the class.

  1. Jan 18Jan 19

    Basics of convex analysis and gradient descent

    scribed notes

    Reading

    Convex analysis basics from ‘Convex Optimization’ by Boyd, Vandenberghe ([5] under references):

    • Chapter 2 (required: beginning of chapter to 2.1.4, recommended: 2.1.5 to end of section)
    • Chapter 3 (required: beginning of chapter to 3.1, recommended: 3.2, 3.3 and 3.4)

    Convergence proofs: from Chapter 3 of [1] (‘Convex Optimization…’ by S.Bubeck under References)

    • Required: Convergence proof of Theorem 3.2 (note that we studied the unconstrained case. In this case the projection operator PiX(x) is the identity operator)
  2. Jan 25

    The different rates of gradient descent: from Lipschitz to strongly convex

    scribed notes

    Reading

    Convergence proofs from Chapter 3 of [1] (‘Convex Optimization…’ by S.Bubeck under References)

    • Required: Sections 3.1, 3.2, 3.4, with emphasis on the Convergence proof of Theorem 3.12
    • Optional: Section 3.3 and anything related to constrained optimization. Keep in mind that we still discuss in class simplified unconstrained versions of some constrained results from Bubeck. Anything in our scribed notes is also required.
  3. Jan 26

    Black box models and lower bounds

    scribed notes

    Reading
    • Required: [1, Theorem 3.15]
    • Recommended: [6]
  4. Feb 1

    Accelerated methods: Polyak's momentum (the heavy ball method)

    scribed notesslides

    Reading
    • Required: [8], [9, Sections 1, 2, 3, 4]
    • Recommended: [35]
  5. Feb 2

    Nesterov's Accelerated Gradient, Stochastic gradient descent

    scribed notes

    Reading
    • Required: [6], [7, pages 67-76]
    • Required: [1, Section 6 until 6.2], [4, Section 14.3]

Crash course in statistical learning theory

  1. Feb 8

    Stochastic gradient descent

    scribed notes

  2. Feb 9Feb 15

    Elements of statistical learning theory

    scribed notes

    Reading
    • Recommended reading: Section 2 (if you need the intro) and Section 5 of [4].
    • Required reading: Sections 3, 4 and 6 of [4].
  3. Feb 16

    PAC-Bayes bounds

    scribed notes

    Reading
    • Required reading: [12]
    • Recommended reading: Section 31 of [4]
    • Recommended reading (harder): Section 6 of [2]
  4. Feb 22

    Probably Approximately Correct Constrained Learning

    paper

  5. Feb 23

    Midterm exam

  6. Mar 1Mar 2

    Winter break, no class

  7. Mar 8

    Stability and generalization

    scribed notes

    Reading

    Required reading:

    • Main body of the papers [13, 14] without all the proofs
    • The scribed notes provided here, including the covered proofs

    Optional reading: Proofs that are not covered in the scribed notes.

Seminar part of class

  1. Mar 9

    Weighted Sums of Random Kitchen Sinks: Replacing minimization with randomization in learning

    scribed notes

    Reading
    • Recommended reading: Section 16 (Kernel methods) of [4]
    • Required reading: [23]
    • Recommended viewing: video of talk by A. Rahimi. The discussion pertaining to this paper, starts at 31:10 (though the intro might be necessary) and ends at about 48:10.
  2. Mar 15

    Surprising results on the generalization error of neural networks

    Reading
  3. Mar 16
  4. Mar 22Mar 23Mar 29Mar 30Apr 5

    Student presentations

  5. Apr 13

    Neural Tangent Kernel (new lecture, no scribed notes)

    Reading

    Recommended reading on reproducing kernel hilbert spaces:

  6. Apr 19Apr 20

    1-1 discussions on course projects

  7. May 3

    Final poster presentation for projects

Extra material (not scheduled)

  1. Determinantal point processes for ML (guest lecture by Jose Gallego-Posada)

    Reading

Bonus material from past iterations

Older lectures that later material replaced. Not examined.

  1. Dynamical systems, with applications to neural networks (guest lecture by Guillaume Lajoie)

    scribed notes

    Reading

    [31, 32, 33]

  2. Distributional reinforcement learning

    scribed notes

  3. Variance reduction for stochastic optimization

    scribed notes

    Reading

    [22]; Section 5.3 of [21]

  4. Expressivity and universal approximation

    scribed notes

    Reading

    Michael Nielsen’s visual proof; Section 20 to 20.4 of [4]; [40]

  5. Escaping saddle points

    scribed notesslides by Yang Yuan

    Reading

    [27, 28]

  6. Generative models

    scribed notes

    Reading

    [17]

  7. Wasserstein GANs

    scribed notes

    Reading

    [18, 19]

  8. The numerics of GANs

    scribed notes

    Reading

    [20]

  9. Basic results on reinforcement learning

    scribed notes

  10. Reading only (2018):

    Reading

    PacGAN [24]; non-convex optimization [25, 26]; spin glasses, guest lecture by Alex Fribergh [29]; loss surfaces of multilayer networks [30].

References

Numbers in the readings above refer to this list.

  1. Convex Optimization: Algorithms and Complexity, Sebastien Bubeck.
  2. Theory of classification: a survey of some recent advances Stephane Boucheron, Olivier Bousquet and Gabor Lugosi
  3. iPython notebook demonstrating basic ideas of gradient descent and stochastic gradient descent, simple and complex models as well as generalization.
  4. Understanding Machine Learning: From Theory to Algorithms, by Shai Shalev-Shwartz and Shai Ben-David.
  5. Convex Optimization, Stephen Boyd and Lieven Vandenberghe.
  6. Nesterov’s Accelerated Gradient Descent for Smooth and Strongly Convex Optimization, blog post by Sebastien Bubeck.
  7. Introductory lectures on convex optimization, Yurii Nesterov.
  8. Why momentum really works, blog post by Gabriel Goh (this blog post uses a slightly different parametrization of the momentum algorithm. The version we discuss in class, only applies the learning rate on the gradient.)
  9. YellowFin and the Art of Momentum Tuning, SysML 2019, J. Zhang, I. Mitliagkas.
  10. Large-scale Machine Learning and Optimization (class), Dimitris Papailiopoulos, University of Wisconsin.
  11. Advanced Machine Learning Systems (class), Chris De Sa, Cornell University.
  12. A PAC-Bayesian Tutorial with A Dropout Bound, David McAllester.
  13. Stability and generalization, O. Bousquet, A. Elisseeff.
  14. Train faster, generalize better: Stability of stochastic gradient descent, M. Hardt, B. Recht, Y. Singer.
  15. Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data, Gintare Karolina Dziugaite, Daniel M. Roy
  16. Lecture notes on generative learning algorithms, Andrew Ng
  17. Generative Adversarial Nets, Ian Goodfellow et al.
  18. Wasserstein GAN, Martin Arjovsky, Soumith Chintala, Léon Bottou
  19. Read-through: Wasserstein GAN, Alex Irpan
  20. The Numerics of GANs, Lars Mescheder, Sebastian Nowozin, Andreas Geiger
  21. Optimization Methods for Large-Scale Machine Learning, Léon Bottou, Frank E. Curtis, Jorge Nocedal
  22. Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Rie Johnson, Tong Zhang
  23. Weighted Sums of Random Kitchen Sinks: Replacing minimization with randomization in learning, Ali Rahimi, Ben Recht
  24. PacGAN: The power of two samples in generative adversarial networks, Zinan Lin, Ashish Khetan, Giulia Fanti, Sewoong Oh
  25. Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming, Saeed Ghadimi, Guanghui Lan
  26. Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition, Hamed Karimi, Julie Nutini, Mark Schmidt
  27. Escaping From Saddle Points — Online Stochastic Gradient for Tensor Decomposition, Rong Ge, Furong Huang, Chi Jin, Yang Yuan
  28. How to Escape Saddle Points Efficiently, Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, Michael I. Jordan
  29. RANDOM MATRICES AND COMPLEXITY OF SPIN GLASSES, ANTONIO AUFFINGER, GERARD BEN AROUS, AND JIRI CERNY
  30. The Loss Surfaces of Multilayer Networks, Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, Yann LeCun
  31. Learning Long-Term Dependencies with Gradient Descent is Difficult, Y Bengio, P Simard, P Frasconi
  32. On the difficulty of training Recurrent Neural Networks, Razvan Pascanu, Tomas Mikolov, Yoshua Bengio
  33. Opening the Black Box: Low-Dimensional Dynamics in High-Dimensional Recurrent Neural Networks, David Sussillo and Omri Barak
  34. Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto
  35. Course Notes for EE227C (Spring 2018): Convex Optimization and Approximation, Moritz Hardt.
  36. Uniform convergence may be unable to explain generalization in deep learning, Vaishnavh Nagarajan, J. Zico Kolter
  37. Tutorial on Practical Prediction Theory for Classification, John Langford, 2005.
  38. Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data, Gintare Karolina Dziugaite, Daniel M. Roy, 2017.
  39. Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach, Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, Peter Orbanz, 2018.
  40. Representation benefits of deep feedforward, Matus Telgarsky, 2015.

Class bibliography

You can find a large number of recent (mostly) research papers related to the class’s objectives here. You can use those for your in-class paper presentations and projects.