4.10.20
Socho tum ek foggy pahaadi par khade ho aur sabse neeche pahunchna chahte ho. Tum door tak nahi dekh sakte, lekin tum feel kar sakte ho ki sabse steep neeche kaun si direction hai — woh hai − ∇ f Gradient descent (GD) bilkul yehi hai. Convergence ki saari theory ek hi sawaal ka jawab deti hai: har kadam kitna bada hona chahiye, aur hum kitni jaldi bottom tak pahunchte hain? "
Definition Gradient descentEk differentiable function f : R n → R x k + 1 = x k − η ∇ f ( x k ) η > 0 step size (learning rate) hai.
YEH direction KYU? Saare unit directions u ∇ f ( x ) ⊤ u u = − ∇ f ( x ) /∥∇ f ( x ) ∥ − ∇ f steepest descent ki direction hai.
Kuch bhi prove karne ke liye, hume control karna hoga ki f
L f L L ∥∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥. f ∇ 2 f ( x ) ⪯ L I L
μ f μ ∇ 2 f ( x ) ⪰ μ I μ > 0 kam se kam utni tezi se upar curve karti hai jitna curvature μ μ = 0
Ratio κ = L / μ ≥ 1 condition number hai — yahi sab kuch control karta hai.
ISKA MATLAB KYA HAI: f
Toh η = 1/ L hamesha decrease hota hai (kabhi diverge nahi hota) — isliye 1/ L
Method
Step / idea
Rate (strongly convex)
GD full gradient, η = 2/ ( μ + L )
( κ + 1 κ − 1 ) k
Heavy-ball / Momentum β ( x k − x k − 1 ) ( κ + 1 κ − 1 ) k
Nesterov accelerated GD lookahead gradient
O ( ( 1 − κ 1 ) k ) O ( 1/ k 2 )
SGD stochastic gradient (ek sample)
O ( 1/ k ) η k → 0
Intuition Momentum GD se behtar KYU haiGD ek narrow valley ke across oscillate karta hai (bada κ average out karta hai aur valley floor ke saath accelerate karta hai — κ κ
Worked example 1D quadraticf ( x ) = 2 1 a x 2 ∇ f = a x L = μ = a κ = 1 x k + 1 = ( 1 − η a ) x k Yeh step KYU? η ⋆ = 2/ ( μ + L ) = 1/ a = 0 ek hi step mein converge ho jaata hai. Perfectly conditioned problems trivial hote hain.
Worked example Anisotropicf ( x , y ) = 2 1 ( x 2 + 100 y 2 ) 1 100 μ = 1 , L = 100 , κ = 100 ρ ⋆ = 101 99 ≈ 0.98 Yeh step KYU? Har iteration error ko sirf 2% shrink karta hai — GD crawl karta hai. Momentum deta hai 100 + 1 100 − 1 = 11 9 ≈ 0.82
Worked example Logistic regression ke liyeη f L L = 4 1 λ m a x ( X ⊤ X ) KYU? Hessian 4 1 X ⊤ D X D ⪯ I η = 1/ L
Common mistake "Bada learning rate = hamesha faster."Kyun sahi lagta hai: bade steps har iteration mein zyada ground cover karte hain.
Fix: agar η > 2/ L ∣1 − η L ∣ > 1 diverge karta hai (outward oscillate). Drop term η ( 1 − L η /2 ) η = 2/ L negative bhi ho jaati hai. Speed sirf ( 0 , 2/ L ) ≈ 1/ L
Common mistake "Convexity akela fast (linear) convergence deta hai."Kyun sahi lagta hai: convex problems ka unique min hota hai, easy lagta hai.
Fix: plain convexity sirf O ( 1/ k ) ρ k strong convexity (μ > 0 x 4 μ = 0
Common mistake "SGD ke liye constant step size use karo aur woh converge ho jaayega."Kyun sahi lagta hai: full-batch GD ke liye perfectly kaam karta hai.
Fix: gradient noise kabhi vanish nahi hoti, toh constant η ∝ η σ 2 η k
Recall Feynman: ek 12-saal ke bachche ko samjhaoSocho tum ek moti fog mein ek pahaadi se ball roll kar rahe ho. Tum sirf apne pairo ke neeche ka slope feel kar sakte ho, toh sabse steep taraf kadam lete ho aur repeat karte ho. Agar tumhare steps bahut bade hain toh tum valley ke across fly karoge aur doosri side par bounce karoge (diverge). Agar "bilkul sahi" hain toh tum smoothly neeche slide ho jaoge. Ek lamba patla valley annoying hota hai — tum zig-zag karte ho — jab tak ki tumhare paas ek asli rolling ball jaisa thoda momentum nahi hota, jo path ko smooth karta hai. Bumpy fog (noisy slope readings = SGD) matlab hai ki tumhe neeche ke paas chhote aur chhote steps lene chahiye, warna tum uske aas-paas jittery rehte rahoge.
Mnemonic Step-size & rate"Two-over-L se neeche raho, theek ho; One-over-L par, monotone descent."
Rate mnemonic: "GD mein κ κ (condition number ka square root lena = momentum ka gift).
Gradient descent update rule kya hai? x k + 1 = x k − η ∇ f ( x k )
− ∇ f Cauchy–Schwarz se, ∇ f ⊤ u u u = − ∇ f /∥∇ f ∥
L ∥∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥ ∇ 2 f ⪯ L I
μ ∇ 2 f ⪰ μ I μ > 0
Descent lemma state karo. f ( y ) ≤ f ( x ) + ∇ f ( x ) ⊤ ( y − x ) + 2 L ∥ y − x ∥ 2
η = 1/ L f ( x k + 1 ) ≤ f ( x k ) − 2 L 1 ∥∇ f ( x k ) ∥ 2
Smooth convex f f ( x k ) − f ⋆ ≤ 2 k L ∥ x 0 − x ⋆ ∥ 2 = O ( 1/ k )
Strongly convex quadratics ke liye optimal step size? η ⋆ = 2/ ( μ + L )
GD ka best contraction factor (strongly convex)? ρ ⋆ = κ + 1 κ − 1 = L + μ L − μ
Quadratics par GD converge karne ke liye η 0 < η < 2/ L
Momentum rate kaise improve karta hai? κ ko
κ se replace karta hai: factor
κ + 1 κ − 1 .
Smooth convex (non-strong) f O ( 1/ k 2 )
SGD ko decaying step size KYU use karni chahiye? Constant η ∝ η σ 2 ∑ η k = ∞ , ∑ η k 2 < ∞
Condition number κ κ = L / μ ≥ 1 κ
1/L set karne se milta hai
Condition number kappa = L/mu
