Rung 1: Math From Scratch

Month 2 | Phase 0: Foundations | ~25–32 hours total

This is the first public artifact you produce, and its job is singular: prove that you understand the mathematics behind what you’re doing rather than just calling library functions. The bar is not “does it work?” — sklearn.decomposition.PCA() works. The bar is “can you explain every line in terms of the underlying linear algebra, and can you prove your implementation is correct?” A hiring manager who opens this repository should finish with zero doubt that you understand eigendecomposition, gradient flow, and the connection between optimization geometry and loss landscape curvature.

What to Build

You are building two implementations in a single GitHub repository, each with full mathematical documentation.

Implementation 1: PCA From Scratch

Build a PCA class using only NumPy — no sklearn, no scipy decomposition shortcuts, no torch.

The implementation must execute this exact mathematical pipeline:

  1. Mean centering: subtract the column-wise mean from the data matrix X (shape: n_samples × n_features)

  2. Covariance matrix: compute C = X_centered.T @ X_centered / (n - 1). The /n-1 is not cosmetic — explain why in your notes.

  3. Eigendecomposition: call np.linalg.eigh(C) — not np.linalg.eig. You must explain in comments: (a) why eigh is correct for symmetric matrices (Hermitian eigenvalue problem), (b) what eigh guarantees about the output that eig does not (real eigenvalues, orthogonal eigenvectors), (c) why this matters for numerical stability.

  4. Sort descending: sort eigenvalues and corresponding eigenvectors by eigenvalue magnitude, largest first.

  5. Select top-k: slice the first k eigenvectors to form the projection matrix W (shape: n_features × k).

  6. Project: compute X_projected = X_centered @ W

  7. Reconstruct: compute X_reconstructed = X_projected @ W.T + mean

Visualizations required (both must be generated by running a script):

  • Scatter plot of 2D synthetic data with the two principal component vectors overlaid as arrows, scaled by their eigenvalues

  • Explained variance ratio bar chart (showing cumulative explained variance as a secondary axis)

  • Reconstruction error curve: plot reconstruction MSE as a function of number of components retained (from 1 to n_features)

  • Side-by-side MNIST digit (28×28): original vs. reconstruction at k=10, k=50, k=100, k=200 components

Implementation 2: Gradient Descent Family From Scratch

Implement all four optimizer variants using only NumPy. Apply them to both a 2D quadratic toy problem (for visualization) and logistic regression on a real dataset.

Optimizers to implement (each in its own class or function, not monolithic):

Optimizer

Key parameters

What to verify

Vanilla GD

lr

Convergence on convex loss

Momentum (SGD + momentum)

lr, beta=0.9

Faster convergence than vanilla, oscillation behavior

RMSProp

lr, rho=0.9, epsilon=1e-8

Adaptive LR behavior, why epsilon matters

Adam

lr=0.001, beta1=0.9, beta2=0.999, epsilon=1e-8

Bias correction in early steps, why it matters

For Adam specifically: implement the bias-corrected moment estimates explicitly and add a comment explaining that without bias correction, the first step would have massively inflated gradient estimates due to zero initialization. This is the part most people skip. Don’t skip it.

Visualizations required:

  • Contour plot of 2D quadratic loss surface with optimization trajectories for all 4 optimizers overlaid (different colors), showing starting point and convergence path

  • Loss vs. iteration curves for all 4 optimizers on the same axes, with logarithmic y-axis

  • Final accuracy on the logistic regression task for all 4 optimizers in a bar chart with error bars (run 3 seeds each)

Datasets to use:

  • Toy 2D: generate a quadratic bowl with f(x,y) = 0.5*(x-2)^2 + 2*(y+1)^2 (asymmetric to show differential convergence behavior)

  • Real: use sklearn.datasets.make_classification(n_samples=1000, n_features=20) — no downloading required

Acceptance Criteria

This rung is complete when every criterion below is satisfied. Not most. Every.

  • git clone <repo> && pip install -r requirements.txt && python scripts/run_pca.py produces all PCA figures. No errors, no warnings, no “please run the notebook first.”

  • python scripts/run_optimizers.py produces all optimizer figures. Same standard.

  • pytest tests/ passes. All tests green.

  • tests/test_pca_correctness.py verifies that your PCA output matches sklearn.decomposition.PCA to within absolute tolerance 1e-5 for eigenvalues and 1e-5 for projected values (accounting for sign ambiguity: abs(your_result) ≈ abs(sklearn_result))

  • tests/test_optimizer_convergence.py verifies that all 4 optimizers converge to loss < 0.1 on the toy quadratic within 500 iterations with lr=0.01

  • Every non-trivial function has a docstring. Every eigendecomposition call, every gradient update, every moment update has an inline comment explaining the mathematical operation.

  • A MATH_NOTES.md file exists (or equivalent README section) containing derivations for: (a) why covariance matrix eigendecomposition gives principal components, (b) the full Adam update rule with bias correction derived from first-moment and second-moment estimation, (c) what “explained variance ratio” means and how to compute it from eigenvalues

  • The repository has ≥ 8 commits — not a single-commit dump. The commit history should tell the story of development.

  • No Jupyter notebooks as primary deliverable. One exploratory notebooks/exploration.ipynb is acceptable but the .py files are what counts.

  • README opens (on GitHub, without scrolling) to: repo title, one-sentence description, two preview images, run instructions in ≤ 5 lines.

Hard stop gate question: If you cannot answer “why is np.linalg.eigh used instead of np.linalg.eig for symmetric matrices, and why does it matter numerically?” without looking it up — the rung is not complete. This is not an obscure fact. It is a direct consequence of the Spectral Theorem for real symmetric matrices.

Repository Structure

ml-from-scratch/
├── README.md                          ← primary signal to employers
├── MATH_NOTES.md                      ← mathematical derivations
├── requirements.txt                   ← numpy, matplotlib, scikit-learn (tests only), pytest
├── pca/
│   ├── __init__.py
│   ├── pca.py                         ← PCA class
│   └── visualization.py               ← all PCA plotting functions
├── optimizers/
│   ├── __init__.py
│   ├── base.py                        ← base optimizer class/interface
│   ├── vanilla_gd.py
│   ├── momentum.py
│   ├── rmsprop.py
│   ├── adam.py
│   └── visualization.py               ← loss curve and contour plotting
├── models/
│   └── logistic_regression.py         ← pure NumPy logistic regression
├── data/
│   └── generators.py                  ← synthetic data generation (no large files)
├── figures/                           ← pre-generated PNGs committed for README display
│   └── .gitkeep
├── scripts/
│   ├── run_pca.py
│   └── run_optimizers.py
├── tests/
│   ├── test_pca_correctness.py
│   └── test_optimizer_convergence.py
└── notebooks/
    └── exploration.ipynb              ← optional, not the primary deliverable

README Opening Template

The first visible content on your GitHub repo page must be:

# ML From Scratch: PCA and Gradient Descent

Implementing Principal Component Analysis and four gradient descent variants
(Vanilla GD, Momentum, RMSProp, Adam) using only NumPy — no sklearn, no
autograd, no shortcuts. Every line is documented against its mathematical basis.

**Purpose:** Demonstrate that I understand what the library calls are doing,
not just that I can call them.

| [PCA demo](figures/pca_components.png) | [Optimizer trajectories](figures/optimizer_contours.png) |
|---|---|
| ![PCA](figures/pca_components.png) | ![Optimizers](figures/optimizer_contours.png) |

## Quick Start
pip install -r requirements.txt
python scripts/run_pca.py        # generates figures/pca_*.png
python scripts/run_optimizers.py # generates figures/optimizer_*.png
pytest tests/                    # verify correctness

## What's Implemented
...

What This Signals to Employers

A senior engineer or hiring manager who opens this repository for 3 minutes should conclude three things:

  1. “This person understands the mathematics” — evidenced by derivations in MATH_NOTES.md and inline mathematical comments

  2. “This person writes reproducible, structured code” — evidenced by the project structure, requirements.txt, and scripts that run without a prayer

  3. “This person can communicate technical work” — evidenced by the README and the quality of the docstrings

This is the foundation signal. It does not get you hired on its own — it prevents elimination in the first 30-second scan. A portfolio without this rung has no legitimate claim to “first principles understanding.” Every subsequent rung is built on the credibility this one establishes.

Time Estimate

Task

Estimated Hours

PCA implementation + debugging + verification

7–9

Optimizer implementations (all 4) + debugging

8–10

Visualization code for both modules

4–5

Tests (correctness + convergence)

2–3

MATH_NOTES.md derivations

3–4

README + repo structure cleanup

2–3

Total

26–34 hours

Practical schedule: ~3 hours per session × 9–11 sessions across Month 2. Do not compress this into a weekend — the distributed practice is where understanding is built.

What Weakens This Rung

These are the specific failure modes that reduce this rung from “strong evidence” to “I built a thing once”:

  • Notebook as final deliverable: immediately signals “I explored, I didn’t engineer.” Notebooks are drafts. The .py files are the product.

  • No tests: a correctness test against sklearn takes 25 lines and proves your implementation is mathematically right. Skipping it implies you don’t know if it is.

  • Thin README: if a hiring manager must open source code to understand what the project does, the README failed its primary job.

  • Missing bias correction in Adam: everyone who copied Adam from a tutorial skipped this. Implementing and explaining it is how you prove you didn’t.

  • Skipping the optimizer trajectory visualization: this is the single most visually impressive artifact in this rung, and it’s also the one that most concisely demonstrates you understand optimization geometry. Skipping it because it’s hard is exactly the wrong decision.

  • Magic numbers without comment: lr=0.001, beta1=0.9, beta2=0.999 with no annotation communicates that you copied a config file. Three lines explaining where these values come from communicates that you read the paper.

  • Single massive commit: tells reviewers the repo was created the night before the interview, not developed over a month. Commit incrementally as you build.

Return to README.md · Next: 02_rung_2_classical_ml_battle.md