Chapter 3 of 16

Mathematical Foundations of Optimization

Search spaces, objective functions, and gradient descent from scratch

18 min read

Created ৬ আগ, ২০২৬

ভূমিকা

এই course-এর প্রতিটা algorithm, সব mechanics-এর নিচে, আসলে একটাই সাধারণ সমস্যার সমাধান করে: একটা function-কে minimize করে এমন input খুঁজে বের করা। Grid search, random search, Bayesian optimization — এদের মধ্যে বেছে নেওয়ার আগে একটা shared vocabulary দরকার: search গাণিতিকভাবে আসলে কী।

Optimization কী?

Optimization হলো অনেক সম্ভাব্য choice-এর মধ্য থেকে সবচেয়ে ভালোটা খোঁজার প্রক্রিয়া, যেখানে "ভালো" মাপা হয় কোনো numeric score দিয়ে। Shower-এর গরম-ঠান্ডার knob ঘুরিয়ে সবচেয়ে comfortable তাপমাত্রা খুঁজে নেওয়া মানে optimization করা: একটা function আছে (comfort, knob position-এর function) এবং সেটা maximize করার input খুঁজছেন।

আনুষ্ঠানিকভাবে:

Optimization Problem

x^* = \arg\min_{x \in \mathcal{X}} f(x)

HPO-র context-এ $\mathcal{X}$ হলো hyperparameter search space আর $f$ হলো validation loss। কিন্তু একই mathematics inner loop-কেও (model parameter train করা) govern করে — তাই ভালোভাবে বুঝলে দুই জায়গাতেই কাজে লাগে।

Objective, Loss, আর Cost Function

এই তিনটা term বিভিন্ন textbook আর library-তে বেমানানভাবে ব্যবহার হয়, যা সত্যিকারের বিভ্রান্তি তৈরি করে।

Objective, loss, আর cost function — এই course-এ terminology
Term	এই course-এ অর্থ
Objective function	সবচেয়ে সাধারণ term: optimization procedure যা minimize বা maximize করছে। Loss, cost, accuracy, বা business metric — যা হোক।
Loss function	একটা single training example-এ error, যেমন ℓ(ŷᵢ, yᵢ) = (ŷᵢ − yᵢ)² একটা datapoint-এর জন্য।
Cost function	একটা পুরো dataset-এ loss-এর aggregate (সাধারণত গড়), যেমন L(θ) = (1/n)∑ᵢ ℓ(ŷᵢ, yᵢ)। Inner training loop আসলে এটাই minimize করে।

Casual practice-এ

বেশিরভাগ library documentation আর paper-এ "loss function" মানে cost function। এটা জানলে কোনো সমস্যা নেই — পার্থক্যটা জানুন, কিন্তু আতঙ্কিত হবেন না।

Search Space-এর ধরন

$\mathcal{X}$ search space কয়েক রকম হতে পারে, আর পার্থক্যটা অনেক গুরুত্বপূর্ণ — কোন optimization algorithm উপযুক্ত তা নির্ধারণ করে।

Continuous search space। Learning rate বা regularization strength যেকোনো real মান নিতে পারে, যেমন $\lambda \in [10^{-6}, 10^{2}]$ । Continuous space-এ calculus-ভিত্তিক reasoning সম্ভব: objective function-এর gradient হিসাব করা যায়।

Discrete search space। Random forest-এর tree সংখ্যা শুধু integer হতে পারে। Categorical search space হলো special case — কোনো natural ordering নেই, যেমন activation function যেটা ReLU, tanh, বা sigmoid হতে পারে।

Conditional search space। কিছু hyperparameter শুধু অন্য hyperparameter-এর নির্দিষ্ট মানে meaningful। যেমন SVM-এর $\gamma$ (gamma) শুধু kernel='rbf' হলে relevant, 'linear' হলে নয়।

Continuous

যেমন learning rate ∈ [10⁻⁵, 1] — gradient-based reasoning সম্ভব

Discrete

যেমন number of trees ∈ {10, ..., 500} — integer, ordered

Categorical

যেমন activation ∈ {ReLU, tanh} — values-এর মধ্যে কোনো natural ordering নেই

Conditional

যেমন γ শুধু kernel=rbf হলে প্রাসঙ্গিক — অন্য hyperparameter-এর মানের উপর নির্ভরশীল

বাস্তব HPO search space-এ সাধারণত চার ধরনের মিশেল থাকে। এটাই HPO-কে চ্যালেঞ্জিং করে তোলে: search space কোনো সহজ $\mathbb{R}^d$ -এর box নয়।

হাতে করা উদাহরণ: Gradient Descent

Optimization concrete করে বোঝার জন্য machine learning-এর সবচেয়ে মৌলিক algorithm দিয়ে ছোট একটা সমস্যা ধাপে ধাপে সমাধান করি: gradient descent। যদিও gradient descent সাধারণত inner loop-এ (model parameter fit করতে) ব্যবহার হয়, এটা হাতে করলে এমন intuition তৈরি হয় যা Bayesian optimization-সহ সব HPO algorithm-এ সরাসরি transfer করে।

ধরুন objective:

Toy Quadratic Objective

f(x) = (x - 3)^2 + 1

ধাপ ১: Derivative। Derivative যেকোনো point-এ slope বলে দেয়:

$f'(x) = 2(x - 3)$

$f'(x) > 0$ হলে function বাড়ছে — $x$ কমাতে হবে। $f'(x) < 0$ হলে কমছে — $x$ বাড়াতে হবে।

ধাপ ২: Update rule। Gradient descent "slope-এর বিপরীত দিকে যাও" কে formal করে:

Gradient Descent Update Rule

x_{t+1} = x_t - \eta \, f'(x_t)

ধাপ ৩: হাতে iterate। $x_0 = 0$ , $\eta = 0.3$ দিয়ে শুরু:

Gradient descent — মাত্র ৪ ধাপে x* = 3-এর কাছে পৌঁছে গেল
t	xₜ	f′(xₜ) = 2(xₜ − 3)	xₜ₊₁
0	0.000	−6.000	0.000 − 0.3(−6.000) = 1.800
1	1.800	−2.400	1.800 − 0.3(−2.400) = 2.520
2	2.520	−0.960	2.520 − 0.3(−0.960) = 2.808
3	2.808	−0.384	2.808 − 0.3(−0.384) = 2.923
4	2.923	−0.154	2.923 − 0.3(−0.154) = 2.969

মাত্র ৪ ধাপে $x_t = 2.969$ — সত্যিকারের minimum $x^* = 3$ -এর খুব কাছে। Algorithm শুধু প্রতিটা point-এ slope-এর বিপরীত দিকে হাঁটছে, step size নিয়ন্ত্রণ করছে learning rate।

নিজে try করুন

η = 1.1 দিয়ে এই table আবার তৈরি করুন। দেখবেন xₜ minimum overshoot করে ক্রমশ বড় হতে থাকে — "LR too high" behavior-এর গণিত এটাই।

def gradient_descent(x0=0.0, eta=0.3, n_steps=10):
    """f(x) = (x - 3)^2 + 1 minimize করো gradient descent দিয়ে।"""
    x = x0
    for t in range(n_steps):
        grad = 2 * (x - 3)          # f'(x) = 2(x - 3)
        x = x - eta * grad          # update rule
        print(f"Step {t+1}: x = {x:.4f}, f(x) = {(x-3)**2 + 1:.4f}")
    return x
 
gradient_descent(eta=0.3)   # ভালো — converge করে
gradient_descent(eta=1.1)   # বেশি — diverge করে
gradient_descent(eta=0.01)  # কম — ধীরে converge করে

এই code চালালে তিনটা qualitatively আলাদা regime সরাসরি দেখা যায়।

HPO-র সাথে সংযোগ

Gradient descent শুধু model training-এ লাগে মনে হলেও, দুটো connection HPO-তেও এটাকে essential করে:

কিছু HPO algorithm সরাসরি gradient ব্যবহার করে। Gradient-based hyperparameter optimization continuous hyperparameter-এর সাপেক্ষে validation loss differentiate করে — শক্তিশালী কিন্তু computationally demanding।

বেশিরভাগ HPO algorithm objective-কে black box মানে। $f(\lambda)$ evaluate করতে একটা পুরো training run লাগে — সস্তা analytical gradient নেই। Bayesian optimization — পরের chapter-এ আসছে — ঠিক এই constraint-এর মধ্যে efficiently search করার জন্য তৈরি: $f$ -এর একটা সস্তা surrogate model বানিয়ে সেটার gradient-like information ব্যবহার করে।

Gradient descent হাতে বোঝা মানে হলো এই mental model তৈরি রাখা — যা পরে exact slope ছাড়াই landscape navigate করার algorithm গুলো বুঝতে সাহায্য করবে।

মূল বিষয়গুলো

Key Takeaways

Optimization = objective function + search space + সেরা point খোঁজার নিয়ম।
Loss (per-example), cost (aggregate), আর objective (general) — সম্পর্কিত কিন্তু আলাদা term।
Search space continuous, discrete, categorical, বা conditional হতে পারে — বাস্তবে সাধারণত চারটার মিশেল।
Gradient descent slope-এর বিপরীত দিকে হাঁটে, step size নির্ধারণ করে learning rate; বেশি বড় হলে overshoot আর oscillation।
বেশিরভাগ HPO algorithm objective function-এর gradient পায় না — expensive black box মানে।

সাধারণ ভুল

Minimization আর maximization গুলিয়ে ফেলা

Gradient descent minimize করে। Objective যদি accuracy হয় (maximize করতে হবে), তাহলে negative accuracy minimize করুন। Sign ভুল হলে খুবই common bug।

Log-uniform বনাম uniform search space বেছে নেওয়া

Learning rate-এর মতো hyperparameter-এর জন্য uniform range [0.001, 0.1] মানে বেশিরভাগ sample 0.1-এর কাছে পড়ে, 0.001-এর কাছে খুবই কম। Log-uniform space প্রতিটা decade-এ সমান sample দেয়। Learning rate আর regularization strength-এর জন্য প্রায় সবসময় log-uniform ব্যবহার করুন।

Interview Corner

Quick Check

1. Learning rate অনেক বেশি হলে gradient descent-এ কী হয়?

2. বেশিরভাগ HPO algorithm কেন objective function-কে 'black box' মানে?

বাস্তবে কোথায় লাগে

এই chapter-এর vocabulary — objective function, search space, gradient, convergence — প্রতিটা HPO tool-এর documentation-এ পাওয়া যাবে। Optuna যখন বলে "minimize the objective," বা W&B যখন "search space" দেখায়, বা Ray Tune যখন "early stopping based on the loss curve" বর্ণনা করে — তখন এই chapter-এর ধারণাগুলোই ব্যবহার হচ্ছে। এই language-এ স্বাচ্ছন্দ্য হলে পরের প্রতিটা tool অনেক সহজে pick up করা যাবে।