M2: Distributed ML Algorithms

M2: Distributed ML Algorithms #

This module applies parallel and distributed computing to ML algorithms. It examines how to divide computation, combine results, and balance communication against useful work during training.

Module coverage:

• Parallel ML Algorithms: CNNs, gradient descent and SGD, SVM, k-means, k-nearest neighbours, decision trees, and random forests.
• Distributed Training Strategies: data parallelism, model parallelism, pipeline parallelism, gradient checkpointing, and mixed-precision training.

Learning Objectives #

• Decompose ML algorithms into independent and dependent work.
• Explain how local results are aggregated and where communication is required.
• Compare distributed execution through Hadoop and Spark.
• Choose training strategies that address compute and memory constraints.

Pages #

Topic Outline #

4. Parallelisation of ML Algorithms #

• Problem decomposition and parallelisation
• Ensemble methods and XGBoost on CPUs
• k-means
• Distributed decision trees and random forests
• Distributed implementations using Spark ML and XGBoost
• Parallel SVM kernel computation using block-wise and MapReduce-style methods

5. Communication-Aware Distributed ML #

• Communication overhead in distributed algorithms
• Distributed k-means and model parallelism
• k-NN: data partitioning, locality-sensitive hashing, and distributed indexing
• KD-tree and Ball-tree indexing versus brute-force MapReduce
• Accuracy–latency trade-offs in approximate k-NN
• Gradient descent and SGD: mini-batch, synchronous, and asynchronous variants

6. Clusters, Hadoop, and Spark #

• Cluster computing with Hadoop and Spark
• Lloyd’s k-means algorithm in MapReduce
• Mini-batch k-means and streaming variants
• Convergence criteria and communication reduction through compressed updates
• CNN data and model parallelism, including layer splitting and tensor slicing
• Mixed precision, pipeline parallelism, and distributed training frameworks

7. Distributed Training Strategies ☆ #

• Data parallelism
• Model parallelism
• Pipeline parallelism
• Gradient checkpointing
• Mixed-precision training

How This Module Connects #

Use M1: Foundations to interpret complexity and speedup. Continue to M3: Scale-Out Systems for the platforms and communication mechanisms that support larger training runs.

ML Workflow

Machine learning Workflow #

Data is the foundation of any machine learning system. Quality of data matters more than model complexity.

Role of Data #

Data determines:

• What patterns the model can learn
• How well it generalises
• Whether bias or noise is introduced

Bad data → bad model (even with perfect algorithms).

Data Preprocessing, wrangling #

Raw data is never ready for training.

Data Issues

• Noise
  • For objects, noise is an extraneous object
  • For attributes, noise refers to modification of original values
  • Use Log or Z Transfer to convert to mean
• Outliers
  • Data objects with characteristics that are considerably different than most of the other data objects in the data set
  • Handle: Use IQR method
  • Find Lower and Upper Bound and replace Outlier with Lower or Upper Bound
• Missing Values
  • Eliminate data objects or variables
  • Handle: Estimate missing values
    • Mean, Median or Mode
    • Prefer Median if there are missing outliers
  • Ignore the missing value during analysis
• Duplicate Data
  • Major issue when merging data from heterogeneous sources
• Inconsistent Codes
  • Find all Unique and transfer all inconsistent to

Data Preprocessing techniques

Multi-Armed Bandit Problem

Multi-Armed Bandit Problem #

The Multi-Armed Bandit (MAB) problem is the simplest setting for studying decision-making under uncertainty.

An agent repeatedly chooses one of \( k \) actions. Each action produces a numerical reward drawn from an unknown distribution. The objective is to maximise the expected total reward over time.

• Multi-armed Bandit Problem - Motivation and Problem Statement
• Incremental solution to the stationary & non-stationary MAB problems
• Exploration vs. Exploitation trade-off
• Bandit Gradient Algorithm as Stochastic Gradient Ascent
• Associative Search

The k-Armed Bandit Problem ☆ #

At every time step:

Parallel and Distributed Algorithms

Parallel and Distributed Algorithms #

Parallelisation divides computational work into parts that can execute concurrently. The purpose is to reduce completion time or increase throughput, but the gain depends on how much work is genuinely independent and how much overhead is introduced.

Course coverage:

1. Systems and performance: execution time, throughput, efficiency, and bottlenecks
2. Speedup—approaches and issues: Amdahl’s Law, serial work, overhead, and load imbalance
3. Data parallelism versus task parallelism versus request parallelism
4. Scale-out clusters: communication cost and its impact on speedup

The worked algorithms also show how divide-and-conquer and matrix operations expose parallel work.

M3: Scale-Out Systems

M3: Scale-Out Systems #

This module examines the platforms, communication patterns, and hardware organisation used to train across larger systems. It extends distributed algorithms into coordinated training services and federated settings.

Module coverage:

• ML Platforms and Frameworks: the Parameter Server model, Spark MLlib, and TensorFlow/PyTorch distributed training.
• Distributed Deep Learning: decentralised SGD, all-reduce, asynchronous parallelism, and large-scale neural networks.
• Federated Learning: training that preserves data privacy, communication efficiency, and hardware utilisation.

Learning Objectives #

• Explain how training platforms organise model state, workers, and updates.
• Compare centralised parameter services with collective communication.
• Assess the effects of bandwidth, latency, locality, and stale updates.
• Relate federated training to data distribution, privacy goals, and communication limits.

Pages and Planned Topics #

The outline below describes the full module scope. Planned topics have no chapter page yet. Chapter 9 currently covers parameter-server execution policies and communication optimisation; collective communication, matrix multiplication, and Local SGD remain to be added from their source material.

Markov Decision Processes

Markov Decision Processes #

A Markov Decision Process (MDP) is the mathematical framework used to describe sequential decision-making in reinforcement learning. It brings together the agent, environment, states, actions, transition dynamics, rewards, returns, policies, and value functions in one model.

A basic bandit asks which action is best in a recurring situation. An MDP goes further: the action taken now can change the next state, which changes the decisions and rewards that become possible later.

Parallel Programming Models

Parallel Programming Models #

Parallel algorithms need hardware that can execute independent work efficiently. Modern systems therefore combine multiple CPU cores, memory hierarchies, threads, instruction pipelines, GPUs, clusters, and specialised matrix processors.

Course coverage:

1. Parallel programming models for expressing independent work
2. MapReduce, task-parallel, and request-parallel patterns
3. Multi-core CPUs and GPGPUs: SIMD, MIMD, SIMT, memory hierarchy, and bandwidth
4. Distributed clusters: CPU-only and GPU-accelerated systems, data sharding, parameter servers, and all-reduce

The hardware sections also cover specialised matrix processors and the performance limits introduced by memory and communication.

Regression (Linear)

Linear Regression #

Linear Regression is a supervised ML method used to predict a numerical target by fitting a model that is linear in its parameters.

In ML , linear models are a core baseline: they’re fast, often surprisingly strong, and usually easy to interpret.

Key takeaway: Linear Regression learns parameters by minimising a squared-error cost. You can solve it directly (closed form) or iteratively (gradient descent), and you can extend it using basis functions and regularisation.

Ordinary Least Squares

February 21, 2026

Direct solution method - Ordinary Least Squares and the Line of Best Fit #

Revision:
OLS is the direct method for linear regression. It finds the best-fit line by minimising the sum of squared residuals without iterative updates.

Direct Method vs Iterative Method ☆ #

Linear regression parameters can be found in two main ways.

flowchart LR
    A["Linear Regression"] --> B["Direct Solution<br/>OLS"]
    A --> C["Iterative Solution<br/>Gradient Descent"]

    B --> B1["Normal Equation"]
    B --> B2["No learning rate"]
    B --> B3["One-shot solution"]

    C --> C1["Learning rate"]
    C --> C2["Repeated updates"]
    C --> C3["Stops after convergence"]

    style A fill:#E1F5FE,stroke:#5b7db1,color:#000
    style B fill:#C8E6C9,stroke:#5f8f6a,color:#000
    style C fill:#FFF9C4,stroke:#b59b3b,color:#000
    style B1 fill:#EDE7F6,stroke:#8a6fb3,color:#000
    style B2 fill:#EDE7F6,stroke:#8a6fb3,color:#000
    style B3 fill:#EDE7F6,stroke:#8a6fb3,color:#000
    style C1 fill:#EDE7F6,stroke:#8a6fb3,color:#000
    style C2 fill:#EDE7F6,stroke:#8a6fb3,color:#000
    style C3 fill:#EDE7F6,stroke:#8a6fb3,color:#000

Why It Is Called “Least Squares” ☆ #

OLS is called least squares because it chooses parameters that make the squared residual errors as small as possible.

Cost Function

February 21, 2026

Cost Function #

Revision:
A cost function converts model error into a single number. Training means changing the model parameters until this number becomes as small as possible.

Why Cost Function Matters in ML ☆ #

A machine learning model needs a way to decide whether one set of parameters is better than another.

For linear regression, every possible value of the parameters gives a different line. The cost function tells us which line is better by measuring how far the predictions are from the true values.