Local vs global minima - maxima — Hinglish notes

1.2.9 · AI-ML › Calculus & Optimization Basics

Overview

Local aur global extrema ka difference samajhna machine learning mein bahut zaroori hai, kyunki gradient descent aur doosre optimization algorithms local minima mein phans sakte hain, aur hum best possible solution nahi dhundh paate. Ye concept explain karta hai ki neural network training itni mushkil kyun hai aur kyun hum random restarts, momentum, aur adaptive learning rates jaise techniques use karte hain.

Figure — Local vs global minima - maxima

Core Concepts

First-Principles Derivation

Hum Extrema Kaise Identify Karte Hain?

Step 1: Necessary Condition (Critical Points)

Kisi bhi local extremum par, agar $f$ differentiable hai, toh gradient zero hona chahiye:

$\nabla f (x^{*}) = 0$

Kyun? Maano $x^{*}$ ek local minimum hai lekin $\nabla f (x^{*}) \neq = 0$ . Toh ek direction $d = - \nabla f (x^{*})$ exist karta hai jahan $f$ decrease karta hai (gradient ki definition se). Us direction mein thoda move karne par: $x^{*} + ϵ d$ se $f (x^{*} + ϵ d) < f (x^{*})$ milta hai chhote $ϵ > 0$ ke liye, jo is baat se contradict karta hai ki $x^{*}$ ek minimum hai.

Lekin: $\nabla f = 0$ necessary toh hai lekin sufficient nahi. Critical points minima, maxima, ya saddle points ho sakte hain.

Step 2: Second-Order Condition (Critical Points Classify Karna)

Ek function $f : R^{n} \to R$ ke liye, Hessian matrix compute karo:

$H_{ij} = \frac{\partial ^{2} f}{\partial x _{i} \partial x _{j}}$

Ek critical point $x^{*}$ par:

Local minimum: $H$ positive definite hai (saare eigenvalues $> 0$ )
Local maximum: $H$ negative definite hai (saare eigenvalues $< 0$ )
Saddle point: $H$ ke eigenvalues mixed sign ke hain

Ye kyun kaam karta hai? $x^{*}$ ke paas second-order Taylor expansion hai:

$f (x^{*} + h) \approx f (x^{*}) + \nabla f (x^{*})^{T} h + \frac{1}{2} h^{T} H h$

Kyunki $\nabla f (x^{*}) = 0$ :

$f (x^{*} + h) - f (x^{*}) \approx \frac{1}{2} h^{T} H h$

Agar $H$ positive definite hai: $h^{T} H h > 0$ sabhi $h \neq = 0$ ke liye → function saari directions mein increase karta hai → local min
Agar $H$ negative definite hai: ulta → local max
Agar mixed eigenvalues hain: kuch directions mein increase, kuch mein decrease → saddle

Step 3: Local aur Global Mein Fark Karna

Global optimality ke liye koi local test nahi hota. Tumhe ye karna hoga:

Saare critical points dhundho
Har jagah $f$ evaluate karo
Boundaries check karo (agar domain bounded hai)
Saari values compare karo — sabse chhota global minimum hai

ML mein ye mushkil kyun hai? Neural networks mein millions of parameters hote hain, jo exhaustive search ko impossible bana deta hai. Hum optimization algorithms aur empirical tricks par rely karte hain.

Worked Examples

Worked example Example 1: One-Dimensional Function

$x \in [- 1, 3]$ par $f (x) = x^{3} - 3 x^{2} + 2$ consider karo.

Step 1: Critical points dhundho $f^{'} (x) = 3 x^{2} - 6 x = 3 x (x - 2)$ Critical points: $x = 0, x = 2$

Ye step kyun? Hume $f^{'} (x) = 0$ chahiye taaki pata chale kahan slope flat hai (extrema ke liye necessary condition).

Step 2: Second derivative test $f^{''} (x) = 6 x - 6$

$x = 0$ par: $f^{''} (0) = - 6 < 0$ → local maximum
$x = 2$ par: $f^{''} (2) = 6 > 0$ → local minimum

Ye step kyun? $f^{''}$ ka sign batata hai ki function upar ki taraf curve karta hai (minimum) ya neechay ki taraf (maximum).

Step 3: Critical points aur boundaries par evaluate karo

$f (- 1) = - 1 - 3 + 2 = - 2$
$f (0) = 2$ (local max)
$f (2) = 8 - 12 + 2 = - 2$ (local min)
$f (3) = 27 - 27 + 2 = 2$

Result: Global minimum $- 2$ hai (jo $x = - 1$ aur $x = 2$ dono jagah achieve hota hai). Global maximum $2$ hai, aur ye do points par achieve hota hai: interior local max $x = 0$ aur right endpoint $x = 3$ . Toh $x = 0$ yahan ek global maximum hai — bas unique nahi. Ye ek subtle point illustrate karta hai: ek local extremum global extremum bhi ho sakta hai, aur global extrema unique nahi hone chahiye.

Worked example Example 2: Two-Dimensional Loss Surface

$f (x, y) = x^{2} + y^{2} - 2 cos (2 π x) - 2 cos (2 π y)$ consider karo (ek simplified Rastrigin function).

Step 1: Is function mein oscillating cosine terms ki wajah se bahut saare local minima hain.

Intuition: $x^{2} + y^{2}$ term ek parabolic bowl create karta hai (origin par ek global min). Cosine terms "bumps" add karte hain jo multiple valleys create karte hain.

Step 2: Gradient compute karo $\nabla f = [2 x + 4 π sin (2 π x) 2 y + 4 π sin (2 π y)]$

Ye step kyun? Hume critical points chahiye jahan dono partial derivatives zero hon.

Step 3: Critical points wahan hote hain jahan:

$2 x + 4 π sin (2 π x) = 0$
$2 y + 4 π sin (2 π y) = 0$ In equations ke multiple solutions hain! Jaise $(0, 0)$ ek hai (jahan $sin (0) = 0$ ), lekin approximately $(0.5, 0)$ aur kaafi aur bhi hain.

Step 4: Evaluate karo

$f (0, 0) = 0 - 2 - 2 = - 4$ ← global minimum
Doosre critical points zyada values dete hain (local minima)

Ye kyun matter karta hai: Agar gradient descent $(1.5, 1.5)$ se start kare, toh wo $(1, 1)$ ke paas ek local minimum mein phans sakta hai aur kabhi $(0, 0)$ par global minimum tak nahi pahunch paata.

Worked example Example 3: Neural Network Loss Landscape

Ek neural network ka loss $L (w)$ weights $w$ ke function ke roop mein non-convex hota hai jisme:

Countless local minima hain (non-linear activations ki wajah se)
Saddle points hain (high dimensions mein local minima se zyada common)
Ek global minimum hota hai (sabse kam achievable loss)

Practical implication:

Random initialization se start karke, SGD $w_{t + 1} = w_{t} - η \nabla L (w_{t})$ follow karta hai
Ho sakta hai ek local minimum par converge ho jaye jisme training loss = 0.15 ho
Global minimum mein training loss = 0.08 ho sakta hai
Hum techniques jaise momentum, learning rate schedules, aur multiple random restarts use karte hain taaki kharab local minima se baah nikalein

Ye step kyun? Ye samajhna explain karta hai ki identical architectures sirf initialization aur optimization hyperparameters ki wajah se alag-alag final accuracies kyun achieve kar sakti hain.

Common Mistakes

Connections to Machine Learning

Gradient Descent Convergence:

Chhote learning rate ke saath vanilla gradient descent ek local minimum (ya saddle point) par converge karta hai
Non-convex problems mein global minimum milne ki koi guarantee nahi
Links to: Gradient Descent, Learning Rate Tuning

Optimization Algorithms:

Momentum accumulated velocity se shallow local minima escape karne mein madad karta hai
Simulated annealing aur genetic algorithms landscape explore karne ke liye randomness use karte hain
Adam optimizer har parameter ke liye learning rates adapt karta hai
Links to: Momentum and Nesterov, Adam Optimizer

Loss Surface Geometry:

High-dimensional spaces mein exponentially zyada saddle points hote hain
Mode connectivity: alag local minima aksar connected low-loss paths par hote hain
Links to: Loss Landscape Visualization, Neural Network Optimization

Regularization Effects:

L2 regularization loss landscape ko "smoother" banane ke liye modify karta hai
Sharp local minima ko broader basins mein convert kar sakta hai, generalization mein madad karta hai
Links to: Regularization Techniques, Generalization in Deep Learning

Active Recall Practice

Recall Ek 12-Saal ke Bachche ko Explain Karo (Feynman Technique)

Socho tum ek video game khel rahe ho jisme aankhon par patti hai aur tum ek bade park mein — jo hills aur valleys se bhara hai — ka sabse neecha point dhundh rahe ho. Tum sirf feel kar sakte ho ki tumhare paon ke neecha zameen upar ki taraf slope ho rahi hai ya neechay ki taraf.

Local minimum ek chhoti si dip dhundne jaisa hai — shayad ek chhotaa sa puddle. Agar tum us puddle se koi bhi qadam lete ho, toh tum upar jaate ho, toh lagta hai ye sabse neecha point hai. Lekin park ke doosri taraf ek bada sa lake ho sakta hai jo kaafi neecha ho — wahi global minimum hai.

Machine learning mein, "park" wo saare possible tarike hain jisme tum apni AI ki brain (neural network ke numbers) set kar sakte ho. "Height" wo mistakes hain jo AI karta hai. Hum sabse neecha point (sabse kam mistakes) chahte hain, lekin hamara algorithm (neechay qadam lene jaisa) ek puddle mein phans sakta hai lake dhundne ki bajaye.

Isliye AI training tricky hai — hume clever tricks chahiye taaki wo park ka zyada hissa explore kare, na ki pehla neecha spot milte hi ruk jaye!

Socho: "LEGOs se banate waqt, tum ek chhota tower bana sakte ho (local max) lekin ye miss kar sakte ho ki zyada pieces explore karte toh ek bada castle (global max) bana sakte the."

Flashcards

#flashcards/ai-ml

Local minimum kya hota hai? :: Wo point jahan function ki value apne neighborhood ke saare nearby points se kam hoti hai, lekin zaroori nahi ki overall sabse kam ho.

Global minimum kya hota hai?

Wo point jahan function apni poori domain mein absolute lowest value achieve karta hai.

Kisi point ke local extremum hone ke liye necessary condition kya hai?

Gradient zero hona chahiye:

\nabla f (x^{*}) = 0

(jisse wo critical point banta hai).

Hessian ka use karke critical point ko classify kaise karte hain?

Eigenvalues check karo — positive definite (saare positive) matlab local min, negative definite matlab local max, mixed signs matlab saddle point.

Gradient descent local minima mein kyun phans sakta hai?

Wo sirf local gradient information ke basis par neechay ke qadam leta hai, isliye pehle local minimum par converge ho jaata hai bina poore landscape ko explore kiye.

Kya har local minimum global minimum bhi hota hai?

Nahi — sirf convex functions mein. Non-convex functions (jaise neural networks) mein, local minima ke values global minimum se zyada ho sakti hain.

Kya ek local extremum global extremum bhi ho sakta hai?

Haan — ek interior local extremum global extremum ke saath coincide kar sakta hai, aur global extrema unique nahi hone chahiye (ye multiple points par achieve ho sakte hain, jaise ek interior point aur ek endpoint).

Saddle point kya hota hai?

Ek critical point jahan Hessian ke positive aur negative dono eigenvalues hote hain — function kuch directions mein decrease karta hai aur kuch mein increase, isliye ye na min hai na max.

High-dimensional optimization mein saddle points itne common kyun hain?

High dimensions mein, ye chance ki saare eigenvalues ek hi sign ke hon (saare positive ya saare negative), exponentially kam ho jaata hai, jo saddle points ko local minima se zyada probable banaata hai.