optimizationমাঝারি⏱ 9 মিনিট

Convex Optimization — উত্তল অপ্টিমাইজেশন

Convex Optimization

🥣

মুরাদের বাটি আর গর্তের গল্প

ধর তোর বন্ধু মুরাদ একটা মার্বেল নিয়া খেলতেছে। সে একটা বাটি (bowl) তে মার্বেল ফেলল — মার্বেল গড়ায়া গড়ায়া সবচেয়ে নিচে (minimum) চলে গেল। এইটা convex surface — যেদিক থেকেই ছাড়ো, মার্বেল always তলানিতে যাইব। কিন্তু যদি ডিমের ট্রে-তে মার্বেল ফেলে? তাইলে একটা খোপে (local minimum) আটকায়া যাইতে পারে — তলানি (global minimum) না পায়া!

বাটি = Convex function — একটাই minimum, সবসময় পাবি। ডিমের ট্রে = Non-convex function — অনেক local minimum, global minimum পাওয়া কঠিন! গুরু বলে — 'ML-এ যদি loss function convex হইত, সব সমস্যা সহজ হইত। কিন্তু neural network non-convex — তাই SGD, Adam লাগে!'

সংজ্ঞা

একটা function f convex হয় যদি যেকোনো দুইটা point-এর মধ্যে straight line function-এর curve-এর উপরে বা তাতে থাকে। Convex function-এর যেকোনো local minimum-ই global minimum। Optimization guarantee পাওয়া যায়।

Convexity condition — দুই point-এর মাঝে function value line-এর নিচে থাকে

\[f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda) f(y), \quad \forall \lambda \in [0,1]\]

ব্যাখ্যা

Convex vs Non-Convex

Convex: MSE loss, logistic regression loss — একটাই valley, gradient descent always global minimum পায়। Non-convex: Neural network loss — অনেক valley, পাহাড়, saddle point। তাই training tricky।

\[\text{MSE} = \frac{1}{N}\sum(y - w^Tx)^2 \quad \text{(convex in } w\text{)}\]

Gradient কেন কাজ করে Convex-এ

Convex function-এ gradient সবসময় global minimum-এর দিকে point করে। মুরাদের বাটিতে মার্বেল যেদিকে ঢালু সেদিকে গড়ায় — সেইটাই gradient direction। Non-convex-এ ভুল valley-তে আটকায়া যাইতে পারে।

\[\nabla f(x^*) = 0 \implies x^* \text{ is global minimum (for convex } f\text{)}\]

Convexity Check

Second derivative (Hessian) দিয়া check করা যায়। যদি Hessian matrix positive semi-definite হয় (সব eigenvalue ≥ 0) তাইলে function convex।

\[\nabla^2 f(x) \succeq 0 \quad \forall x \implies f \text{ is convex}\]

Linear Regression-এর Convex Loss

1D data: x=[1,2,3], y=[2,4,5]। Model: ŷ = wx। MSE loss L(w)-এর minimum কোথায়? দেখাও L(w) convex।

Step 1: Loss function লেখ

MSE = (1/3)[(2-w)² + (4-2w)² + (5-3w)²]

\[L(w) = \frac{1}{3}[(2-w)^2 + (4-2w)^2 + (5-3w)^2]\]

Step 2: Expand করো

ভিতরে expand করলে w²-এর coefficient positive — মানে convex!

\[L(w) = \frac{1}{3}[w^2 + 4w^2 + 9w^2 - 4w - 16w - 30w + 4 + 16 + 25] = \frac{14w^2 - 50w + 45}{3}\]

Step 3: Derivative = 0

dL/dw = 0 solve করো

\[\frac{dL}{dw} = \frac{28w - 50}{3} = 0 \implies w = \frac{50}{28} \approx 1.786\]

Step 4: Second derivative check

d²L/dw² = 28/3 > 0 — positive মানে convex! Global minimum confirmed।

\[\frac{d^2L}{dw^2} = \frac{28}{3} > 0 \quad \checkmark \text{ convex!}\]

উত্তর:

w ≈ 1.786 তে global minimum। L(w) convex কারণ d²L/dw² > 0 everywhere। বাটির তলানি পাওয়া গেল! Linear regression-এর closed-form solution এই কারণেই possible।

ML-এ কোথায় লাগে?

💡

মনে রাখার ট্রিক

Convex = মুরাদের বাটি — মার্বেল ছাড়ো, তলানিতে যাইব guaranteed। Non-convex = ডিমের ট্রে — ভুল গর্তে আটকায়া যাইতে পারে! Linear regression = বাটি, Neural network = ডিমের ট্রে!

#convex#optimization#gradient-descent#hessian#global-minimum#loss-landscape