Optimization Algorithms SGD Adam Rmsprop

# Optimization Algorithms: SGD, Adam & RMSprop

## Introduction & Motivation

Optimizers: update parameters via gradients. SGD: momentum reduces noise; Nesterov accelerates. Adam: adaptive learning rates per parameter; practical default. RMSprop: per-parameter scaling; intermediate between SGD and Adam. Applications: all neural networks; choice impacts convergence speed and final performance.

Motivation: Raw gradient descent slow; momentum/adaptive rates speed convergence, escape saddles.

Applications: Deep learning training, hyperparameter selection.

---

## Core Concepts & Theory

### SGD with Momentum

Velocity accumulates; oscillations dampen; faster convergence.

### Adam (Adaptive Moment Estimation)

First and second moment estimates; per-parameter learning rates; robust.

### RMSprop

Adaptive learning rate via root mean square gradient; prevents overshooting.

---

## Mathematical Formulation

SGD with Momentum:
$$v_t = \beta v_{t-1} + g_t$$
$$ heta_t = heta_{t-1} - \alpha v_t$$

where β ≈ 0.9, α = learning rate.

Adam:
$$m_t = \beta_1 m_{t-1} + (1-\beta_1) g_t$$
$$v_t = \beta_2 v_{t-1} + (1-\beta_2) g_t^2$$
$$\hat{m}_t = \frac{m_t}{1-\beta_1^t}, \quad \hat{v}_t = \frac{v_t}{1-\beta_2^t}$$
$$ heta_t = heta_{t-1} - \alpha \frac{\hat{m}_t}{\sqrt{\hat{v}_t} + \epsilon}$$

RMSprop:
$$v_t = ho v_{t-1} + (1- ho) g_t^2$$
$$ heta_t = heta_{t-1} - \alpha \frac{g_t}{\sqrt{v_t} + \epsilon}$$

---

## Advanced Theory & Extensions

### AdaBound

Combines adaptive and SGD-like behavior; bridges gap.

### AdamW

Weight decay decoupled from learning rate; better regularization.

### Lookahead

Meta-optimizer wrapper; stabilizes oscillatory optimizers.

---

## Computational Considerations

SGD: O(1) per parameter; minimal overhead.

Adam: O(1) per parameter; maintain two moments.

RMSprop: O(1) per parameter; maintain second moment only.

---

## Practical Implementation Strategies

### Learning Rate Schedule

Warm-up then decay; cosine annealing common.

### Momentum β

Typically 0.9; higher for noisier gradients.

### Adam Defaults

β₁=0.9, β₂=0.999, ε=1e-8; robust across tasks.

---

## Benchmark Datasets & Evaluation

CIFAR-10: SGD with momentum standard; Adam faster initial convergence.

ImageNet: SGD achieves higher final accuracy; Adam popular in practice.

BERT: Adam default; momentum SGD slower for transformers.

---

## Key Challenges & Limitations

### Adam Generalization

Overfits on some tasks; test performance lower than SGD.

### Learning Rate Sensitivity

Adaptive rates reduce tuning burden; still requires decay schedule.

### Computational Overhead

Adam 2× memory (two moments); matters for large models.

---

## Hyperparameter Tuning

Learning rate α: 1e-4 to 1e-2; dataset dependent.

Momentum β: 0.9 standard; 0.95-0.99 for CNNs.

β₂ (Adam): 0.999 standard; rarely tuned.

---

## Real-World Applications & Case Studies

Vision: SGD achieves best final accuracy; Adam faster early.

NLP: Adam standard for BERT, GPT training.

Reinforcement Learning: Adam reduces instability.

---

## Integration with Other Methods

Optimizer + Learning Rate Schedule → coupled dynamics.

Optimizer + Gradient Clipping → stability in RNNs.

---

## Summary & Key Takeaways

Optimization via SGD, Adam, and RMSprop balance convergence speed and final performance through momentum and adaptive learning rates.

Principles:
1. Momentum: velocity reduces noise, accelerates.
2. Adaptive rates: per-parameter scaling; Adam most robust.
3. Learning rate scheduling: decay essential.
4. SGD: best final accuracy; Adam faster initial.
5. Choice task-dependent; Adam safe default.

---

---

## Appendix: Practical Labs

### Lab 1: SGD with Momentum

import torch
import numpy as np

class SGDMomentum:
 def __init__(self, params, lr=0.01, momentum=0.9):
 self.params = params
 self.lr = lr
 self.momentum = momentum
 self.velocities = [torch.zeros_like(p) for p in params]

 def step(self):
 for p, v in zip(self.params, self.velocities):
 if p.grad is None:
 continue
 v.mul_(self.momentum).add_(p.grad, alpha=1)
 p.data.add_(v, alpha=-self.lr)

# Test
np.random.seed(42)
params = [torch.randn(10, 10, requires_grad=True)]
optimizer = SGDMomentum(params, lr=0.01)

for _ in range(5):
 loss = params[0].sum()
 loss.backward()
 optimizer.step()
 optimizer.velocities[0].zero_()
 params[0].grad.zero_()

assert torch.isfinite(params[0]).all(), "Parameters should be finite"
print("✓ SGD momentum working")

if __name__ == "__main__":
 print("Lab 1: SGD - PASSED")

### Lab 2: Adam Optimizer

import torch
import numpy as np

class Adam:
 def __init__(self, params, lr=0.001, beta1=0.9, beta2=0.999, eps=1e-8):
 self.params = params
 self.lr = lr
 self.beta1 = beta1
 self.beta2 = beta2
 self.eps = eps
 self.m = [torch.zeros_like(p) for p in params]
 self.v = [torch.zeros_like(p) for p in params]
 self.t = 0

 def step(self):
 self.t += 1
 for p, m, v in zip(self.params, self.m, self.v):
 if p.grad is None:
 continue
 m.mul_(self.beta1).add_(p.grad, alpha=1-self.beta1)
 v.mul_(self.beta2).add_(p.grad ** 2, alpha=1-self.beta2)

 m_hat = m / (1 - self.beta1 ** self.t)
 v_hat = v / (1 - self.beta2 ** self.t)

 p.data.add_(m_hat / (v_hat.sqrt() + self.eps), alpha=-self.lr)

# Test
np.random.seed(42)
params = [torch.randn(10, 10, requires_grad=True)]
optimizer = Adam(params, lr=0.001)

for _ in range(5):
 loss = params[0].sum()
 loss.backward()
 optimizer.step()
 params[0].grad.zero_()

assert torch.isfinite(params[0]).all(), "Parameters should be finite"
print("✓ Adam working")

if __name__ == "__main__":
 print("Lab 2: Adam - PASSED")

### Lab 3: RMSprop Optimizer

import torch
import numpy as np

class RMSprop:
 def __init__(self, params, lr=0.01, rho=0.99, eps=1e-8):
 self.params = params
 self.lr = lr
 self.rho = rho
 self.eps = eps
 self.v = [torch.zeros_like(p) for p in params]

 def step(self):
 for p, v in zip(self.params, self.v):
 if p.grad is None:
 continue
 v.mul_(self.rho).add_(p.grad ** 2, alpha=1-self.rho)
 p.data.add_(p.grad / (v.sqrt() + self.eps), alpha=-self.lr)

# Test
np.random.seed(42)
params = [torch.randn(10, 10, requires_grad=True)]
optimizer = RMSprop(params, lr=0.01)

for _ in range(5):
 loss = params[0].sum()
 loss.backward()
 optimizer.step()
 params[0].grad.zero_()

assert torch.isfinite(params[0]).all(), "Parameters should be finite"
print("✓ RMSprop working")

if __name__ == "__main__":
 print("Lab 3: RMSprop - PASSED")

### Lab 4: Optimizer Comparison

import torch
import numpy as np

def compare_optimizers(initial_params, n_steps=100):
 """Compare convergence speed of optimizers"""
 results = {}

 for opt_name in ['SGD', 'Adam', 'RMSprop']:
 params = [p.clone().detach().requires_grad_(True) for p in initial_params]

 if opt_name == 'SGD':
 optimizer = torch.optim.SGD(params, lr=0.01, momentum=0.9)
 elif opt_name == 'Adam':
 optimizer = torch.optim.Adam(params, lr=0.001)
 else:
 optimizer = torch.optim.RMSprop(params, lr=0.01)

 losses = []
 for _ in range(n_steps):
 loss = (params[0] ** 2).sum()
 optimizer.zero_grad()
 loss.backward()
 optimizer.step()
 losses.append(loss.item())

 results[opt_name] = losses

 return results

# Test
np.random.seed(42)
initial = [torch.randn(10, 10)]

results = compare_optimizers(initial, n_steps=100)

assert len(results) == 3, "Should compare 3 optimizers"
for opt, losses in results.items():
 assert len(losses) == 100, "Should have 100 steps"
 assert losses[-1] < losses[0], "Loss should decrease"
 assert all(np.isfinite(l) for l in losses), "All losses finite"

print("✓ Optimizer comparison working")

if __name__ == "__main__":
 print("Lab 4: Comparison - PASSED")