অধ্যায় 29 — Gradient-Based Optimization

📖 একটি ছোট গল্প

কুয়াশায় ঘেরা পাহাড়ে নামার সবচেয়ে নিরাপদ উপায় — পায়ের নিচে slope অনুভব করে যেদিকে নিচু সেদিকে এক পা। বারবার। একসময় উপত্যকা। এটাই gradient-based optimization-এর সম্পূর্ণ philosophy।

First-Order Methods

θ ← θ − η · ∇L(θ)

Batch GD: full dataset gradient — accurate, slow, memory-heavy।
SGD: একটি sample — noisy, fast, escape local min।
Mini-batch SGD: 32-512 sample — standard practice।

Second-Order Methods

Newton's Method

θ ← θ − H⁻¹ ∇L(θ)

Quadratic convergence কিন্তু Hessian compute (O(n²)) ও invert (O(n³)) — neural net-এ infeasible।

Quasi-Newton (BFGS, L-BFGS)

Hessian approximate করে gradient history থেকে — classical ML-এ popular, deep learning-এ rare।

Step Size & Convergence

η খুব ছোট → slow convergence।
η খুব বড় → oscillation/divergence।
Smooth convex function: η < 2/L (L = Lipschitz constant of ∇L)।
Line search: প্রতিটি step-এ optimal η খুঁজে বের করা — costly।
Adaptive: Adam, RMSProp — per-parameter step size।

💡 ইনসাইট

Convergence rate: GD on smooth convex = O(1/T), strongly convex = O(ρ^T), Newton = quadratic।

Momentum

v ← β·v + ∇L(θ), θ ← θ − η·v

পূর্ব gradient-এর "velocity" বহন করে — narrow ravine-এ oscillation কমায়, plateau-তে speed বাড়ায়।β = 0.9 common।

Nesterov Accelerated Gradient (NAG)

"Look-ahead" gradient — momentum-এর পর position-এ gradient compute করে।

Python Implementation

pythonPython · NumPy

import numpy as np

# Minimize f(x,y) = x^2 + 10y^2 (ill-conditioned)
def f(p): return p[0]**2 + 10*p[1]**2
def grad(p): return np.array([2*p[0], 20*p[1]])

def gd(eta, steps=50):
    p = np.array([5.0, 5.0])
    for _ in range(steps):
        p = p - eta * grad(p)
    return f(p)

def momentum(eta, beta=0.9, steps=50):
    p = np.array([5.0, 5.0]); v = np.zeros(2)
    for _ in range(steps):
        v = beta*v + grad(p)
        p = p - eta*v
    return f(p)

print(f"GD       eta=0.05 → loss={gd(0.05):.4f}")
print(f"GD       eta=0.09 → loss={gd(0.09):.4f}  (oscillation)")
print(f"Momentum eta=0.05 → loss={momentum(0.05):.4f}")

# Mini-batch SGD on linear regression
np.random.seed(0)
N, D = 1000, 5
X = np.random.randn(N, D); true_w = np.random.randn(D)
y = X @ true_w + 0.1*np.random.randn(N)

w = np.zeros(D); eta = 0.05; batch = 32
for epoch in range(20):
    idx = np.random.permutation(N)
    for i in range(0, N, batch):
        b = idx[i:i+batch]
        g = (X[b].T @ (X[b] @ w - y[b])) / batch * 2
        w -= eta * g

print(f"\n||w - w*|| = {np.linalg.norm(w - true_w):.4f}")

AI/ML সংযোগ

সব neural net training = first-order optimization variant।
Momentum + adaptive LR = Adam = modern default।
Newton/L-BFGS = small problem (logistic regression), large-scale ML নয়।
SGD-এর noise = implicit regularization, flat minima খুঁজে পায়।

Common Mistakes

LR কখনো tune না করে default ব্যবহার করা।
Mini-batch shuffle না করা → biased gradient।
Momentum β খুব বড় (0.99+) → overshoot।
Newton's method neural net-এ apply করার চেষ্টা — Hessian infeasible।

Practice Tasks

Rosenbrock function-এ GD, GD+Momentum, NAG compare করুন।
Ill-conditioned quadratic-এ momentum কতগুণ fast তা মাপুন।
Batch size 1, 32, 256, full — convergence speed/quality plot করুন।

Assignment

MNIST-এর উপর একটি 2-layer MLP train করুন তিনটি optimizer দিয়ে: vanilla SGD, SGD+momentum, NAG। প্রতিটির train/val curve plot করুন। কোনটি দ্রুত converge করল এবং কেন — বিশ্লেষণ লিখুন।

Interview Questions

SGD-এর "noise" কেন কখনো ভালো?
Newton's method neural net-এ কেন ব্যবহার হয় না?
Momentum শারীরিকভাবে কী represent করে?
Convergence rate Big-O notation-এ GD vs Newton?

Mini Project

"Optimizer Race Visualizer" — 2D loss surface-এ ৫টি optimizer-এর path animate করুন: GD, Momentum, NAG, RMSProp, Adam। User function ও start point বদলাতে পারে।

Summary · সারসংক্ষেপ

Gradient-based optimization = first-order (cheap, scalable) ও second-order (fast, expensive)।
Step size = success-এর সবচেয়ে critical hyperparameter।
Momentum = ill-conditioned problem-এ savior।
Mini-batch SGD = modern deep learning-এর default।

✨ পরবর্তী পদক্ষেপ

Chapter 30-এ Adam, RMSProp, SGD — adaptive optimizer-এর গণিত।