MATH4267: Deep Learning and Artificial Intelligence Assignment 2023-24

Overview

This assignment has two parts.  In the first part, you will read and summarise a fairly recent paper in deep learning, from a pre-specified list.  In the second part, you will fit a supervised machine learning model to a dataset, submit a set of predicted values for some unknown data.

This assignment is worth a total of 60 Marks, with the following breakdown:

.  30 marks for the paper summary

.  15 marks for your description of what you have done in the prediction task; and

.  15 marks for how well you have managed to predict the unknown outcome

In total, you will submit:

. A report (in PDF format) of ≤ 7 pages covering the response to parts 1 (about 4 pages) and 2 (about 2 pages)

. An R data frame (in .RData format) with your predictions, as specified in part 2.

Please read this assignment through carefully (particularly the ‘Hints and Notes’ sections) before begin- ning.

This assignment is due on 26 April.  Please submit reports and  .RData objects to Ultra. If you have any trouble with uploads, please just e-mail me your report and .RData object before the due date, and I will count it as on time.

1 Part 1

Please choose one of the following papers on which to do the first part of the assignment.  All these papers are from the 2023 International Conference on Machine Learning. Do not worry if you do not fully understand the abstracts.

i.  Chen L, Bruna J. Beyond the edge of stability via two-step gradient updates.  International Confer- ence on Machine Learning 2023 Jul 3. PDF

Gradient Descent (GD) is a powerful workhorse of modern machine learning thanks to its scalability and efficiency in high-dimensional spaces.   Its  ability to find local min- imisers is only guaranteed for losses with Lipschitz gradients, where it can be seen as a ‘bona-fide’ discretisation of an underlying gradient flow.  Yet, many ML setups involv- ing overparametrised models do not fall into this problem class, which has motivated research beyond the so-called  “Edge of Stability” (EoS), where the step-size crosses the admissibility threshold inversely proportional to the Lipschitz constant above.  Perhaps surprisingly, GD has been empirically observed to still converge regardless of local insta- bility and oscillatory behavior.  The incipient theoretical analysis of this phenomena has mainly focused in the overparametrised regime, where the effect of choosing a large learn- ing rate may be associated to a ‘Sharpness-Minimisation’ implicit regularisation within the manifold of minimisers, under appropriate asymptotic limits. In contrast, in this work we directly examine the conditions for such unstable convergence, focusing on simple, yet representative, learning problems, via analysis of two-step gradient updates.  Specifically, we characterize a local condition involving third-order derivatives that guarantees exis- tence and convergence to fixed points of the two-step updates, and leverage such property in a teacher-student setting, under population loss. Finally, starting from Matrix Factor- ization, we provide observations of period-2 orbit of GD in high-dimensional settings with intuition of its dynamics, along with exploration into more general settings.

ii.  Zhang S, Lu J, Zhao H. On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network. International Conference on Machine Learning 2023 Jul 3. PDF

This paper explores the expressive power of deep neural networks through the framework of function compositions.   We demonstrate that the repeated compositions of a single fixed-size ReLU network exhibit surprising expressive power, despite the limited expressive capabilities of the individual network itself.  Specifically, we prove by construction that L2 。g。r 。L1  can approximate  1-Lipschitz continuous functions on [0 , 1]d  with an error O(r − 1/d ), where g is realized by a fixedsize ReLU network, L1  and L1  are two affine linear maps matching the dimensions,  and g。r   denotes  the  r-times  composition  of g. Furthermore, we extend such a result to generic continuous functions on [0 , 1]d  with the approximation error characterized by the modulus of continuity.  Our results reveal that a continuous-depth network generated via a dynamical system has immense approximation power even if its dynamics function is time-independent and realized by a fixed-size ReLU network.

iii.  Draxler F, K¨uhmichel L, Rousselot A, M¨uller J, Schn¨orr C, K¨othe U. On the Convergence Rate of Gaussianization with Random Rotations.  International Conference on Machine Learning 2023 Jul 3. PDF

Gaussianization (Chen & Gopinath, 2000) is a simple generative model that can be trained without backpropagation. It has shown compelling performance on low dimensional data.

As the dimension increases, however, it has been observed that the convergence speed slows down. We show analytically that the number of required layers scales linearly with the dimension for Gaussian input. We argue that this is because the model is unable to capture dependencies between dimensions.  Empirically, we find the same linear increase in cost for arbitrary input p(x), but observe favorable scaling for some distributions. We explore potential speed-ups and formulate challenges for further research.

The following similar paper will be used for example answers to parts 4 and 3 below:

iv. Wang R, Manchester I. Direct parameterization of lipschitz-bounded deep networks.  International Conference on Machine Learning 2023 Jul 3. PDF

This paper introduces a new parameterization of deep neural networks (both fully-connected and convolutional) with guaranteed ℓ2  Lipschitz bounds, i.e.   limited sensitivity to in-   put perturbations. The Lipschitz guarantees are equivalent to the tightest-known bounds   based on certification via a semidefinite program (SDP). We provide a “direct” parameter-   ization, i.e., a smooth mapping from R N onto the set of weights satisfying the SDP-based   bound.  Moreover, our parameterization is complete, i.e.  a neural network satisfies the   SDP bound if and only if it can be represented via our parameterization.  This enables   training using standard gradient methods, without any inner approximation or computa-   tionally intensive tasks (e.g.  projections or barrier terms) for the SDP constraint.  The   new parameterization can equivalently be thought of as either a new layer type (the sand-   wich layer), or a novel parameterization of standard feedforward networks with parameter   sharing between neighbouring layers. A comprehensive set of experiments on image clas-   sification shows that sandwich layers outperform previous approaches on both empirical   and certified robust accuracy. Code is available at https://github.com/acfr/LBDN.

1.1 Tasks

Once you have picked a manuscript, do the following tasks:

1.  Summarise the background to the paper, in your own words, at a level interpretable to your class- mates.  Describe the setting to the paper, and what the paper contributes, in a general setting. Suggest avenues for further research following the conclusions of the paper.  (5 marks)

2.  Suggest a potential new real-world application of the method proposed in the paper. In particular, specify mathematically a quantify that could be increased or decreased by the method, and why this is a good thing.  Describe in detail how the method proposed in the paper applies to the new application.  (5 marks)

3. For the following theorem in the paper that you picked:

Paper i:  Theorem 1

Paper ii:  Theorem 1.1

Paper iii.  Theorem 1

iv. example only Theorem 3.1

Find a use case.   Specify objects of the type used in the theorem, specify specificially what the assumptions you mean in the context of the specific object, and indicate what is ‘surprising’ or ’new’ about the theorem. You may include plots or use code if you like, but this is not mandatory. (10 marks)

4. For each of the following parts of the paper that you picked,  specify  why  the  given  theorem/ proposition/ figure is of interest. You do not need to be as specific as in part 3.  (10 marks)

Paper i.  Proposition 2, Observation 1, Figure 3

Paper ii.  Theorem 1.3, Figure 1, Figure 3

Paper iii. Equation 20, Theorem 2, Figure 4,

iv.  (example only) Equation (9), Theorem 3.2, Figure 1, Table 2

In particular, try and say:

(a) What is being said?

(b) What is the relevance to the overall point of the paper?

(c) Why is what is being said useful to someone who wants to use or apply the overall method?

1.2 Hints and Notes for part 1

Please bear in mind

.  This assignment is intended to get you moderately comfortable reading recent papers in machine learning.

. You will probably come across mathematical ideas you haven’t seen before. Try and look things up online and teach yourself how they work.  If you don’t understand the ideas completely, please do your best with what you do understand.

.  Many (even most) published papers have mistakes or omissions.  Sometimes, key theorems do not actually hold, or key assumptions are missing.  I do not think there are major mistakes in any of the main parts you have been asked to summarise, but there might be. Let me know if you find any.

.  These papers are all recent and complicated. You will probably struggle to understand them entirely. Fear not! You should not have to completely understand them to do a good job on this assignment.

. Focus on the overall message of the paper, which will be summarised in the abstract.  Also, look carefully at definitions, and work out specifically what the relevant theorems/figures/etc mean.  It is often helpful to think about why  definitions use the notation they use:  why does the definition focus on a particular parameter or variable?

. All papers include long supplements, usually with extended proofs. You do not need to read these to do this assignment (unless you are particularly interested).

.  Example answers can be found in the accompanying document.

. If you are struggling to find how to draw a particular symbol in LATEX, then the ‘detexify’ website can help (link)

.  These papers do not necessarily use the same notation as we have been using in class.  Read the notation sections very carefully.

2 Part 2

In this part of the assignment, you will train a supervised machine learning model to a dataset, as well as you can. Please download the following datasets from Ultra:

. training.RData. This is a  .RData object, containing an object called xy_train. Download it to a file (for instance, /Downloads/training.RData). To open it in R, run the following commands:

>  PATH="/Downloads/training.RData"

>  load(PATH)

replacing /Downloads/training.RData with wherever you have saved your  .RData object.

The object xy_train is a data frame containing 10,000 rows and 102 columns.  The columns are called ID, X1, X2, ... , X100, and Y.

. testing.RData. This is also a  .RData object, containing an object called x_test. Download it to a file and open it in R in the same way as for training.RData:

>  PATH="/Downloads/testing.RData"

>  load(PATH)

The object x_test is a data frame containing 10,000 rows and 102 columns.  The columns are called ID, X1, X2, ... , X100, and Y. Column Y is all NAs: this is what you will be trying to predict.

The variable ID is a unique ID number, and Y is either 0 or 1.  Variables X1, X2, ... , and X100 are real numbers.

2.1 Tasks

Your goal is to decide a decision rule which predicts the value of Y, given values of X1, X2, ... , and X100. I will assess your decision rule based on how well you predict the Y values in x_test (the data frame in testing.RData).  The real Y values are hidden, so you will have to learn a decision rule using xy_test (in training.RData), which contains Y values.

The decision rule will be evaluated on the basis of 0-1 loss on x_test, and you will submit a completed data frame similar to x_test, but with your predicted Y values filled in.  You may do this essentially however you like. Please produce:

1. A .RData object containing a dataframe containing (at least) the two columns ID and Y. The values ID should correspond to the IDs in x_test (in testing.RData).  Each value of Y should be 0 or 1. (15 marks)

2.  A 2 page report describing how you chose your decision rule (this can be in the same document as your report for part 1, but the reports themselves should be separate).  (15 marks)

Your report should cover the following:

. Any preliminary analysis

.  Data cleaning,

. Any unsupervised learning,

. Any hyperparameter tuning,

. Your protocol for training and testing sets,

.  The model architecture.

In your report, focus on why you made particular decisions, and why a particular idea could  have helped, even if it ultimately did not.

You may use any machine learning model you like to estimate values of Y. You do  not have to use a neural network, or the keras package, for your final predictions. However, you must must do the following:

1.  Try at least two ways of predicting Y , and compare them in a reasonable way

2. Attempt to use a neural network to predict Y

and describe these in your report.