DSA4212 Assignments

DSA4212

Traveling Salesman Problem [90%]

Goal: The Traveling Salesman Problem (TSP) is a classic problem in combinatorial optimization. Given a list of cities and the distances between each pair of cities, the problem is to find the shortest possible route that visits each city exactly once and returns to the origin city. You are tasked with implementing a few methods to solve the TSP and compare their performance. Your report should not include any actual code. Instead, it should describe the problem and provide a discussion of the results. You are encouraged to compare your results with the best known solutions.

Possible References:

Thompson problem [90%]

Goal: The Thompson problem is a classic problem in computational geometry. Consider N = 300 points \(P_1, P_2, \ldots, P_N \in \mathbb{R}^3\) on the unit sphere: for \(1 \leq i \leq N\), we have \(\|P_i\| = 1\). How should these points be placed so that the quantity

\[ E = \sum_{i=1}^{N} \sum_{j=1}^{N} \frac{1}{\|P_i - P_j\|} \]

is minimized. Note that it is the norm, and not the norm squared, in the denominator. Your report should not include any actual code. Instead, it should describe the problem and provide a discussion of the results. You are encouraged to compare your results with the best known solutions.

Possible References:

Image classification with convolutional neural networks [90%]

Goal: Implement a simple convolutional neural network in Python and use it to classify images from the CIFAR-10 dataset. For this purpose, you will implement a small CNN on a GPU (eg. Google Colab) – the actual details of the CNN is not the emphasis of this assignment and you should not spend too much time optimizing the architecture. Instead, you will study:

  • the influence of the choice of optimizer
  • the effect of the learning rate on the speed of convergence and the final test accuracy
  • whether using a learning rate schedule improves performance
  • the effect of the batch size on the speed of convergence and the final test accuracy
  • influence and importance of data augmentation

Your report should not include any actual code. Instead, it should describe your experiments and their results, and provide a discussion of the findings.

Possible References:

Automatic differentiation [90%]

Goal: Implement a simple version of automatic differentiation in Python. Your implementation should be able to easily compute the gradient of the composition of any number of (simple) multivariate functions. While your report should not include any actual code, it should describe the mechanics of your implementation and provide examples of its use.

Possible References:

Collaborative Filtering [90%]

Goal: Implement a collaborative filtering algorithm in Python from scratch – you should not use any high-level library such as surprise since this would defeat the purpose of the assignment. For testing your implementation, you will use the song dataset available here. You are tasked to implement the matrix factorization algorithm discussed in class, propose improvements, and compare your implementations with a number of baselines approaches. The challenge of this assignment is to implement the algorithm in scalable manner.

Natural Evolution Strategies [100%]

The class of algorithms known as NaturalEvolutionStrategies (NES) has demonstrated significant potential in various fields of applied mathematics and machine learning. In this project, you will provide an overview of NES and apply these approaches to three optimization problems of your choice. Your report should not include any actual code. Instead, it should describe what NES are, how they work, and provide a discussion of the results.

Possible References:

Word Embeddings [100%]

Goal: Implement a simple word embedding in Python (from scratch) and use it to find the most similar words to a given word. Your report should not include any actual code. Instead, it should describe how word embeddings work, how you implemented it, and provide a discussion of the results. For this purpose, you need to come up with a dataset, as well as evaluation metrics to assess the quality of your embeddings.

Possible References:

Portfolio Optimization [100%]

Goal: You are tasked with implementing the mean-variance portfolio optimization framework. Your objective is to either maximize returns for a given level of risk or minimize risk for a desired return level. For this assignment:

  • Data Collection: Download historical financial data to estimate the expected returns, volatilities (standard deviations) of asset returns, and the covariance matrix of asset returns. You are required to optimize a portfolio of at least 50 stocks

  • Optimization: You must use the CVXPY Python library to implement and solve the mean-variance optimization. The goal is to determine the optimal portfolio weights that balance risk and return.

    • Efficient Frontier: Calculate and plot the efficient frontier, which represents the set of optimal portfolios for different risk-return trade-offs.
    • Stability of Solutions: Study how stable the solutions are by testing your results across different time windows and datasets. Consider the impact of changes in volatility and return estimates on portfolio stability.

  • Discussion: Reflect on the limitations of the mean-variance framework, particularly with respect to the sensitivity of the results with respect to the inputs.

Shampoo optimizer [100%]

Goal: Shampoo is a very recent second-order-like optimizer that has shown great promise in training deep neural networks such as Large Language Models. The optimizer was named “Shampoo” as it attempts to build a good preconditioner for the optimization problem. The purpose of this assignment is to implement the Shampoo optimizer in Python + Jax and compare its performance with other optimizers such as Adam, SGD, and RMSprop. Your report should not include any actual code. Instead, it should describe how Shampoo works, how you implemented it, and provide a discussion of the results. It is not necessary to understand all the theoretical details of Shampoo, but you should be able to explain the main ideas behind it.

References:
- Shampoo: Preconditioned Stochastic Tensor Optimization
- A New Perspective on Shampoo’s Preconditioner
- SOAP: improving and stabilizing shampoo using adam
- A Distributed Data-Parallel PyTorch Implementation

Transformer architecture [100%]

Goal: Implement a simple transformer in Python and from scratch, ie. not use the Transformer(...) function of a high-level library.

Some examples of simple task that can be used to test the transformer are:

  • Sequence Reversal: reversing a sequences of numbers, [1,3,2,4,5,3] -> [3,5,4,2,3,1].
  • Basic Arithmetic: learning simple arithmetic operation is a surprisingly challenging task for a transformer. For example, given a sequence of numbers and arithmetic operations, the model should output the result of the operations. [1,3,2,"+",9,4,2]->[1,0,7,4]. [1,3,2,"+",9,4,2]->[1,0,7,4]
  • Copying Task: A simple task where the model’s objective is to output the same sequence it receives as input. This might seem trivial but is a good starting point: [1,3,2,4,5,3]->[1,3,2,4,5,3]
  • Sorting Numbers: This can be very challenging for a transformer, especially if the sequence is long. [1,3,2,4,5,3]->[1,2,3,3,4,5]
  • Character-Level Text Generation: Generating text one character at a time, based on a given prompt or starting character.

Your report should not include any actual code. Instead, it should describe how a transformer works, how you implemented it, and provide a discussion of the results.

Possible References:

Topic of your choice

Propose a topic and contact me to discuss it and for approval.