Assignments

Let be a finite-dimensional vector space over , and let be a linear operator (representing a recurrent weight matrix).

• Proof: Prove that if the spectral radius , then for all , regardless of the norm chosen.
• Application: Consider a Recurrent Neural Network (RNN) with a linear activation function . Using the result above, formally explain why the state vector decays to zero if all eigenvalues of lie inside the unit circle.
• Extension: Why does the Spectral Theorem (Axler Ch 7) imply that for symmetric (Hermitian) weight matrices, the operator norm is exactly equal to the largest eigenvalue? How does this simplify the analysis of gradient explosion?

The "Manifold Hypothesis" suggests data lies on low-dimensional subspaces. SVD is the tool to find them.

• Derivation: Starting from the Spectral Theorem for the positive operator , rigorously derive the Singular Value Decomposition for an arbitrary operator .
• Low-Rank Approximation: Prove the Eckart-Young-Mirsky theorem for the Frobenius norm: The best rank- approximation of a matrix is given by truncating its SVD to the top singular values.

• Volume Concentration: Derive the formula for the volume of a -dimensional hypersphere of radius . Prove that as , the volume of the unit sphere concentrates at the equator (or that the ratio of the sphere's volume to the enclosing cube's volume goes to zero).
• Implication: In a short essay, explain how this "curse of dimensionality" affects nearest-neighbor search in vector databases (a key component of RAG systems). Why does Euclidean distance lose meaning in 1000-dimensional spaces?

The Softmax function is central to the Transformer's attention mechanism.

• Derivation: Derive the Jacobian matrix where .
• Expression: Show that , or in vector notation, .
• Properties: Prove that this Jacobian is symmetric. What does the term subtract from the diagonal? (Hint: Relate this to probability mass conservation).

• Hessian Analysis: For a loss function , write the second-order Taylor expansion around a point .
• Saddle Points: Explain mathematically why a critical point where the Hessian has both positive and negative eigenvalues is a saddle point.
• Implementation: Create a synthetic 2D surface . Implement "Newton's Method" optimization . Show via simulation how Newton's method fails or behaves chaotically near the saddle point compared to standard Gradient Descent.

Implement Kahn's Algorithm to determine a valid execution order.

• The "Live Interval" Problem: The "Live Interval" of a tensor starts when it is produced and ends when its last consumer finishes.
• Goal: Find a topological ordering that minimizes the maximum total memory active at any instant.
• Algorithm: This is an NP-hard problem. Implement a Greedy Heuristic: At each step, if multiple nodes are ready to execute, choose the one that frees the most memory (or increases live memory the least).

• Testing: Generate random DAGs (N=100, N=1000). Compare the peak memory usage of your optimized schedule versus a random valid schedule.
• Blog Component: Explain how topological sorting determines the order of CUDA kernel launches and how "operator fusion" (merging nodes) could further reduce memory overhead.

Implement the standard triple-loop algorithm.

• Tiled Implementation: Implement "Block Matrix Multiplication."
• Block Size Determination: Determine the optimal block size based on your CPU's L1 cache size (e.g., 32kb).
• Analysis: Explain why tiling reduces cache misses (Theoretical analysis of arithmetic intensity).

Use AVX2 (x86) or NEON (ARM) intrinsics to compute 8 floats at a time in the inner loop.

• Performance Testing: Run matrix sizes .
• Metrics: Plot GFLOPS (Giga-Floating Point Operations Per Second) for: Naive vs. Tiled vs. Tiled+SIMD vs. NumPy (Reference).
• Cache Analysis: Use a tool like perf (Linux) or Instruments (Mac) to measure "L1-dcache-load-misses."

• Consider the Ridge Regression objective: .
• Dual Solution: Prove that the optimal weights lie in the span of the data points . Derive the "Dual Solution" involving the Gram matrix .
• Kernel Insight: Explain why this allows us to use infinite-dimensional feature spaces via the "Kernel Trick" without ever computing the coordinates explicitly.

• Kernel Ridge Regressor: Implement a Kernel Ridge Regressor in Python using only NumPy.
• RBF Kernel: Use the RBF (Gaussian) Kernel: .
• Experiment: Train on a non-linear dataset (e.g., a sine wave with noise). Show how changing (bandwidth) shifts the model from High Bias (underfitting) to High Variance (overfitting).

• Synthetic Data: Generate synthetic data from 3 overlapping Gaussian distributions.
• Visualization Setup: Prepare for creating an animation (GIF) showing the Gaussian contours shifting to fit the data over time.

• E-Step: Calculate the "responsibilities" (posterior probability that point belongs to cluster ).
• M-Step: Re-estimate means, covariances, and mixing coefficients using the responsibilities.
• Convergence: Plot the Log-Likelihood of the data over iterations. It must be monotonically increasing (prove this property in your write-up).

Create an animation (GIF) showing the Gaussian contours shifting to fit the data over time. This is a perfect asset for your technical blog.

Wrap NumPy arrays. Implement __add__, __mul__, matmul, relu, transpose.

As operations are performed, dynamically build a graph of Tensor objects.

• backward() Method: Implement backward() which performs a topological sort and propagates gradients using the Chain Rule.
• Broadcasting: Handle broadcasting correctly in the backward pass (summing out gradients along broadcasted dimensions). This is the hardest part.

• MNIST Training: Train a 3-layer MLP on the MNIST digits dataset using your engine.
• Accuracy Goal: Achieve >90% accuracy.

Implement the Adam optimizer from scratch within your framework.

Implement RoPE (as used in LLaMA) instead of absolute sinusoidal embeddings. This requires complex number manipulation of query/key vectors.

Ensure your attention mechanism correctly masks future tokens (the lower-triangular mask).

Input Indices → Embedding → N Layers (Attn + FFN + Norm) → Logits.

• Model Size: Train a "baby GPT" (~10M parameters).
• Dataset: Use the "TinyShakespeare" dataset.
• Implementation: Implement the tokenizer, data loader, and training loop from scratch.

Implement a sampling loop with "Temperature" and "Top-k" sampling.

Visualize the attention weights of your trained model. Show specific examples where a head attends to the previous word vs. the beginning of a sentence.

• The Problem: Standard Softmax reads data, computes exponentials, writes to memory, reads back, sums, divides, writes back. This is memory inefficient.
• The Fusion: Write a kernel that keeps the row data in SRAM (Shared Memory), computes the exponential and the sum in one go, and writes only the final result.

Compare the throughput (GB/s) of your Triton kernel against torch.softmax for varying tensor sizes.

Implement a simplified "FlashAttention" forward pass in Triton (tiling the matrices).

• Simulation: Use torch.multiprocessing to spawn processes (simulating 2 GPUs).
• Model Replication: Initialize the same model on both processes.
• Data Splitting: Split a data batch in half.

• All-Reduce Operation: Use dist.all_reduce to sum the gradients across processes.
• Weight Update: Update weights after synchronization.

• Correctness Check: Show that the weights on Rank 0 and Rank 1 remain identical after 100 steps.
• Communication Analysis: Write a report on the communication overhead. If the model size is and network bandwidth is , what is the theoretical latency of an All-Reduce step?

Create (or download) a small dataset of pairs: where the winner is polite and the loser is rude.

• Loss Function: Implement the DPO loss:
• Reference Model: Manage the memory to keep a frozen copy of the reference model for probability computation.

Qualitative analysis. Show prompts where the base model is rude and the DPO model is polite.

Define the linear variance schedule .

Train a U-Net to predict the noise added to an image at timestep .

Implement the reverse process to generate digits from pure Gaussian noise.

Create a grid visualization showing the "reverse diffusion" process step-by-step, turning static into a number.

Select a research paper from the last 12 months (NeurIPS/ICLR).

• Code: Is the model architecture exactly as described?
• Hyperparameters: Are learning rates, batch sizes, and initialization seeds documented?
• Data: Is the train/test split clean? (Avoid data leakage).
• Compute: Report the GPU hours required.

• Reproduction: Re-implement the paper from scratch.
• Results: Reproduce the main results table.
• Ablation: Change one thing (e.g., activation function, initialization) and measure the effect.

Write a high-quality blog post explaining the intuition, the math, and the implementation hurdles.