Gradient Descent Variants Batch Mini-Batch Stochastic
# Gradient Descent Variants: Batch, Mini-Batch & Stochastic
## Introduction & Motivation
Gradient descent update policy: determines optimization trajectory. Batch GD: full dataset per step; stable but slow. Stochastic GD: single sample per step; noisy but cheap. Mini-batch: balance stability and efficiency; practical standard. Applications: all supervised learning; fundamental to deep learning.
Motivation: Batch: exact gradient, stable. SGD: cheap updates, escape saddles via noise. Mini-batch: best of both.
Applications: Neural network training, online learning.
---
## Core Concepts & Theory
### Batch Gradient Descent
Update on full dataset; exact gradient; O(N) per step.
### Stochastic Gradient Descent
Update on single sample; noisy gradient; O(1) per step.
### Mini-Batch Gradient Descent
Update on K samples; balanced variance-bias; O(K) per step.
---
## Mathematical Formulation
Batch GD:
$$ heta_t = heta_{t-1} - \alpha
abla L( heta_{t-1}; X, y)$$
where loss computed on all N samples.
SGD:
$$ heta_t = heta_{t-1} - \alpha
abla L( heta_{t-1}; x_i, y_i)$$
single sample (i_t random).
Mini-batch:
$$ heta_t = heta_{t-1} - \alpha \frac{1}{|B|} \sum_{i \in B}
abla L( heta_{t-1}; x_i, y_i)$$
batch size |B| typically 32, 64, 128.
---
## Advanced Theory & Extensions
### Variance Reduction
SVRG: stochastic variance reduced gradient; lower variance than SGD.
### Importance Sampling
Weight samples by gradient magnitude; prioritize harder examples.
### Cyclic Learning Rates
Vary batch size during training; dynamic mini-batch.
---
## Computational Considerations
Batch: O(N) per step; GPU efficient.
SGD: O(1) per step; poor GPU utilization.
Mini-batch: O(K) per step; K=power of 2 optimal; GPU sweet spot.
---
## Practical Implementation Strategies
### Batch Size Selection
64-256 typical; larger for large datasets, 32 for small.
### Shuffling
Shuffle data before each epoch; reduce variance.
### Gradient Accumulation
Simulate larger batch via multiple small steps; memory efficient.
---
## Benchmark Datasets & Evaluation
CIFAR-10: Batch size 128 standard.
ImageNet: Batch size 256 per GPU; distributed batch size up to 32k.
MNIST: Small batches (32) sufficient; low variance needed.
---
## Key Challenges & Limitations
### Batch Size Effect
Large batch: faster per-step, fewer steps. Small batch: noisy, more steps.
### Generalization Gap
Large batch: worse generalization; training-test gap widens.
### Learning Rate Coupling
Optimal LR depends on batch size; linear scaling rule.
---
## Hyperparameter Tuning
Batch size: 32, 64, 128, 256; powers of 2 optimal.
LR scaling: α' = α * (batch_size' / batch_size).
Gradient accumulation: Simulate batch via 2-4 accumulation steps.
---
## Real-World Applications & Case Studies
ResNets: Batch size 256; distributed across GPUs.
BERT: Batch size 256-512 per GPU; accumulated.
Reinforcement Learning: Small batch (32) for sample efficiency.
---
## Integration with Other Methods
Batch Size + Learning Rate → coupled scaling relationship.
Batch Size + Noise → implicit regularization.
---
## Summary & Key Takeaways
Gradient descent variants balance computational efficiency and convergence stability via batch size selection, with mini-batch as practical standard.
Principles:
1. Batch GD: exact, stable; slow, GPU poor.
2. SGD: cheap, noisy; escapes saddles naturally.
3. Mini-batch: balances efficiency and stability.
4. Batch size ∝ GPU memory; 64-256 typical.
5. LR scales with batch size; empirical validation needed.
---
---
## Appendix: Practical Labs
### Lab 1: Gradient Estimation Variance
import torch
import numpy as np
def gradient_variance(X, y, model, batch_sizes=[1, 32, 256]):
"""Compare gradient variance across batch sizes"""
variances = {}
for bs in batch_sizes:
grads = []
n_batches = min(100, len(X) // bs)
for b in range(n_batches):
idx = np.arange(b * bs, min((b + 1) * bs, len(X)))
X_batch = X[idx]
y_batch = y[idx]
output = model(X_batch)
loss = ((output - y_batch) ** 2).mean()
loss.backward()
grad_norm = torch.cat([p.grad.flatten() for p in model.parameters()]).norm().item()
grads.append(grad_norm)
model.zero_grad()
variances[bs] = np.var(grads)
return variances
# Test
np.random.seed(42)
X = torch.randn(1000, 10)
y = torch.randn(1000, 1)
model = torch.nn.Linear(10, 1)
variances = gradient_variance(X, y, model, batch_sizes=[1, 32, 128])
assert all(v > 0 for v in variances.values()), "Variances should be positive"
assert variances[1] > variances[128], "Smaller batch should have higher variance"
print("✓ Gradient variance working")
if __name__ == "__main__":
print("Lab 1: Variance - PASSED")### Lab 2: Convergence Speed vs Batch Size
import torch
import numpy as np
def train_with_batch_size(X, y, batch_size, n_epochs=50):
"""Train model and return convergence curve"""
model = torch.nn.Sequential(
torch.nn.Linear(10, 32),
torch.nn.ReLU(),
torch.nn.Linear(32, 1)
)
optimizer = torch.optim.SGD(model.parameters(), lr=0.01)
losses = []
for epoch in range(n_epochs):
for b in range(0, len(X), batch_size):
idx = slice(b, min(b + batch_size, len(X)))
output = model(X[idx])
loss = ((output - y[idx]) ** 2).mean()
optimizer.zero_grad()
loss.backward()
optimizer.step()
with torch.no_grad():
full_loss = ((model(X) - y) ** 2).mean().item()
losses.append(full_loss)
return losses
# Test
np.random.seed(42)
X = torch.randn(500, 10)
y = torch.randn(500, 1)
losses_bs32 = train_with_batch_size(X, y, batch_size=32)
losses_bs128 = train_with_batch_size(X, y, batch_size=128)
assert len(losses_bs32) == 50, "Should have 50 epochs"
assert losses_bs32[0] > losses_bs32[-1], "Loss should decrease"
assert all(np.isfinite(l) for l in losses_bs32), "All finite"
print("✓ Convergence comparison working")
if __name__ == "__main__":
print("Lab 2: Convergence - PASSED")### Lab 3: Gradient Accumulation
import torch
import numpy as np
def gradient_accumulation_step(X, y, model, accumulation_steps=4):
"""Simulate larger batch via gradient accumulation"""
optimizer = torch.optim.SGD(model.parameters(), lr=0.01)
batch_size = len(X) // accumulation_steps
optimizer.zero_grad()
for acc_step in range(accumulation_steps):
idx = slice(acc_step * batch_size, (acc_step + 1) * batch_size)
output = model(X[idx])
loss = ((output - y[idx]) ** 2).mean() / accumulation_steps
loss.backward()
optimizer.step()
return loss.item() * accumulation_steps
# Test
np.random.seed(42)
X = torch.randn(128, 10)
y = torch.randn(128, 1)
model = torch.nn.Linear(10, 1)
loss = gradient_accumulation_step(X, y, model, accumulation_steps=4)
assert np.isfinite(loss), "Loss should be finite"
assert loss > 0, "Loss should be positive"
print("✓ Gradient accumulation working")
if __name__ == "__main__":
print("Lab 3: Accumulation - PASSED")### Lab 4: Learning Rate Scaling
import torch
import numpy as np
def linear_lr_scaling_rule(base_lr, base_batch_size, new_batch_size):
"""Linear scaling rule: LR scales with batch size"""
return base_lr * (new_batch_size / base_batch_size)
# Test
np.random.seed(42)
base_lr = 0.001
base_bs = 32
new_lrs = {
64: linear_lr_scaling_rule(base_lr, base_bs, 64),
128: linear_lr_scaling_rule(base_lr, base_bs, 128),
256: linear_lr_scaling_rule(base_lr, base_bs, 256),
}
assert new_lrs[64] == 0.002, "LR should double for 2× batch"
assert new_lrs[128] == 0.004, "LR should 4× for 4× batch"
assert all(np.isfinite(lr) for lr in new_lrs.values()), "All finite"
print("✓ LR scaling working")
if __name__ == "__main__":
print("Lab 4: Scaling - PASSED")