Randomized Algorithms

Randomized algorithms use random choices to achieve better average-case performance, simpler implementations, or solutions to problems where deterministic approaches are impractical.

Two types:

• Las Vegas — always correct, randomness affects runtime (e.g., randomized quicksort)
• Monte Carlo — may be wrong with bounded probability, always terminates (e.g., approximate counting)

Key techniques in ML:

Random projection (Johnson-Lindenstrauss lemma)

• Project from $\mathbb{R}^d \to \mathbb{R}^k$ with a random matrix: distances are preserved up to $(1 \pm \epsilon)$ if $k = O(\log n / \epsilon^2)$
• Used for dimensionality reduction, sketching, and random features for kernel approximation

Reservoir sampling

• Sample $k$ items uniformly from a stream of unknown length in $O(k)$ memory
• Used in data loading: random sampling from datasets too large to fit in memory

Stochastic methods

• Stochastic Gradient Descent — random mini-batches instead of full gradient
• Dropout — random neuron masking as regularization
• Monte Carlo Methods in RL — estimate value functions by random rollouts
• Stochastic depth — randomly drop entire layers during training

Hashing tricks

• Feature hashing — map features to fixed-size vector with random hash → Hash Tables
• MinHash — estimate Jaccard similarity between sets in constant time; used for deduplication
• Count-Min Sketch — approximate frequency counting in $O(1)$ space per update; useful for token frequency estimation at scale

Why randomness helps: deterministic algorithms can get stuck in worst cases. Randomness smooths over adversarial inputs and often converts $O(n^2)$ worst cases into $O(n \log n)$ expected cases.

See also: Stochastic Gradient Descent, Monte Carlo Methods in RL, Hash Tables