4.10.20 · D1Gradient descent and variants — convergence analysis
Intuition Ek idea jo sab kuch chalata haiGradient descent bas fog mein pahad se neeche lugna hai: sabse steep neeche ki slope feel karo, usi taraf step lo, repeat karo. Saari convergence theory ek sawaal ka bookkeeping hai — kitna bada step safe hai, aur hum bottom tak kitni tez pahunchte hain? — aur jawab poori tarah se is baat pe depend karta hai ki pahad kitna curved hai.
Yeh page toolbox hai. Parent note symbols ki barish tezi se karta hai. Yahan hum har ek symbol zero se earn karte hain — pehle saadhe alfaaz, phir ek picture, phir kyun yeh topic us ke bina nahi chal sakta . Koi bhi cheez use hone se pehle build ki jaati hai. Upar se neeche padho; har item sirf upar waali cheez pe lean karta hai.
Kisi bhi symbol se pehle, mental picture fix karo.
f f : R n → R f location do — n ek height number deta hai.
R n n ( x , y ) n = 2 → R
Picture (figure s01): n = 2 ( x , y ) f sabse neeche hisse ke neeche baitha ho.
Intuition Figure s01 padhoWhite curve f x f ( x ) x ⋆ f ⋆
Topic ko yeh kyun chahiye: baad mein aane waala har symbol is landscape ko describe karta hai — uski slope, uski curvature, uska lowest point. Agar tum landscape nahi dekh rahe, toh algebra sirf shor hai.
Kyun chahiye: har convergence bound x ⋆ door ya f ⋆ upar height gap ke roop mein measure hoti hai. Yeh finish line hain.
Ek location x ∈ R n vector hai: origin se us floor-point tak ek arrow.
∥ v ∥ v = ( v 1 , … , v n ) ∥ v ∥ = v 1 2 + v 2 2 + ⋯ + v n 2 . length (Pythagoras n
Picture: 2D mein, ∥ ( 3 , 4 ) ∥ = 9 + 16 = 5
Kyun chahiye: convergence ka matlab hai "gap chhota hota ja raha hai". Yeh kehne ke liye ki kuch chhota ho raha hai, hume use measure karna hoga — aur ∥ x k − x ⋆ ∥
∥ v ∥ ∣ v ∣ ∥ v ∥ ek number hai, absolute values ki list nahi. Yeh saare coordinates ko square-root-of-sum-of-squares ke through combine karta hai.
Definition Dot product (inner product)Do vectors u , v ∈ R n u ⊤ v = u 1 v 1 + u 2 v 2 + ⋯ + u n v n . ⊤ u ⊤ v u dot v " padh sakte ho.
Picture (figure s02): u ⊤ v = ∥ u ∥ ∥ v ∥ cos θ θ measure karta hai ki do arrows kitna same direction mein point karte hain : jab aligned ho toh maximum, jab perpendicular ho toh zero, jab opposite ho toh negative.
Intuition Figure s02 padhoBlue arrow u v θ v shadow u u ⊤ v /∥ u ∥ v u
Topic ko yeh kyun chahiye: ek direction mein slope ek dot product hai (∇ f ⊤ u u
Kyun chahiye: yeh ek line hai jo prove karti hai ki − ∇ f
Yahan show ka star hai.
Definition Partial derivative∂ x i ∂ f i sirf x i Taylor's Theorem and the Fundamental Theorem of Calculus dekho.)
∇ f ( x ) ∇ f ( x ) = ( ∂ x 1 ∂ f , … , ∂ x n ∂ f ) . ∇
Picture (figure s03): kisi bhi floor-point pe, ∇ f arrow hai jo floor plane mein lie karta hai aur steepest uphill direction mein point karta hai, aur uski length batata hai ki woh climb kitni steep hai. Toh − ∇ f downhill ki taraf point karta hai — woh direction jisme hum step lete hain.
Intuition Figure s03 padhoWhite rings contours hain — equal height ki floor-curves, jaise ek topographic map. Pink arrow (+ ∇ f − ∇ f
Intuition Steepest descent− ∇ f u directional derivative ∇ f ( x ) ⊤ u u ∇ f
Kyun chahiye: poora update rule x k + 1 = x k − η ∇ f ( x k )
Definition Stationary point:∇ f ( x ⋆ ) = 0 pehchante hain ki hum pahunch gaye.
Definition Step size (learning rate)η η > 0 kitni door hum har move mein − ∇ f η η
Definition Iteration indexk x k k = 0 , 1 , 2 , … x 0 x k k x k + 1 time stamp hai, coordinate nahi.
Kyun chahiye: "step kitna bada (η k yahi topic ka central question hai. Dono symbols har bound mein rehte hain.
Slope batata hai kaun si taraf neeche hai; curvature batata hai slope khud kaise badlata hai — aur curvature hi decide karta hai problem kitni mushkil hai.
∇ 2 f ( x ) gradient kaise murtaa hai jab tum move karte ho — ek point pe landscape ki "bendiness". 1D mein yeh sirf f ′′ ( x )
Definition Positive semidefinite matrixEk symmetric matrix M positive semidefinite hai (likho M ⪰ 0 v ⊤ M v ≥ 0 har direction v ke liye. M kabhi neeche curve nahi karti — koi bhi direction chuno aur woh jo curvature batayega woh ≥ 0 > 0 v = 0 positive definite : ek bowl jo har direction mein strictly upar curve karti hai, koi flat channel nahi.
Intuition Yeh itna matter kyun karta hai"Har direction mein upar curve karna" exactly wahi hai jo ek point ko genuine bottom banata hai na ki saddle ya ridge. Hessian ki positive semidefiniteness algebraic tarika hai yeh kehne ka ki "yeh sach mein ek valley hai".
Definition Matrix orderingA ⪯ B A ⪰ B A ⪯ B A B defined hai us idea se jo humne abhi build kiya:
A ⪯ B ⟺ B − A ⪰ 0 ⟺ v ⊤ ( B − A ) v ≥ 0 for all v . A ⪯ B B A
∇ 2 f ⪯ L I curvature kabhi L kisi bhi direction mein (I ∇ 2 f ⪰ μ I curvature kam se kam μ hai har direction mein.
Picture (figure s04): sach ki curved surface ko do parabolas ke beech trap karo — neeche μ L
Intuition Figure s04 padhoWhite curve sach wali f sabse gentle allowed curvature μ sabse steep allowed curvature L μ I ⪯ ∇ 2 f ⪯ L I
Kyun chahiye: yeh do sandwiching bounds (μ L sirf yahi facts hain jo convergence proofs use karti hain. Sab kuch — safe step size, speed — is sandwich se squeeze hota hai. Single valley guarantee karne wali convexity (μ ≥ 0 Convex Functions and Optimization dekho.
L f L L ∥∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥. Lipschitz Continuity hai gradient pe apply hua. Saadhe alfaaz: slope wildly nahi bhag sakti — uska change L ∇ 2 f ⪯ L I L
Kyun chahiye: L safe step size set karta hai (Section 7 mein derive hoga). Kyunki curvature ≤ L η ≈ 1/ L
μ f μ μ > 0 μ kam se kam itni tez upar curve kare: ∇ 2 f ⪰ μ I μ = 0
Kyun chahiye: μ bottom ki taraf ek definite pull deta hai, jo convergence ko slow O ( 1/ k ) ρ k
Ab hum woh danger line derive kar sakte hain jo parent note baar baar cite karta hai, sirf L
Intuition Ek-line takeawaySteepness L 2/ L itna zyada overshoot karta hai jitna shuru hua tha — aur amplify hota rehta hai. Safe steps ( 0 , 2/ L ) ≈ 1/ L
Kyun chahiye: yahi precise reason hai ki L μ safe step size control karta hai, aur yeh parent note ke full convergence rates ka seed hai.
Definition Eigenvector aur eigenvalue (symmetric matrix ke liye)Kisi matrix M eigenvector ek special direction v M M v = λ v λ eigenvalue hai.
Ek key fact: ek symmetric matrix (jaise har Hessian) ke paas eigenvectors ka ek poora set hota hai jo mutually perpendicular hain, aur har ek ke along matrix sirf apne eigenvalue se plain multiplication ki tarah act karta hai. Ise diagonalization kehte hain — axes ko eigenvectors ke saath line up karna messy matrix ko simple stretch factors ki list mein badal deta hai. Eigenvalues and the Condition Number dekho.
Intuition Eigenvalues ka hamare bowl ke liye kya matlab haiAxes ko Hessian ke eigenvectors ke saath line up karo aur bowl ek clean stack of 1D parabolas ban jaati hai — ek per axis — jisme eigenvalue λ i curvature hai. Ek L μ [ μ , L ] μ L
Definition Condition numberκ = L / μ ≥ 1 valley kitni stretched hai . κ = 1 κ = 100
Picture: round bowl → bottom tak seedha shot. Lamba ravine → narrow direction ke across zig-zag karte hue long axis mein barely move karna.
Definition Contraction / convergence rateρ ρ ∈ [ 0 , 1 ) har step mein rakhi gayi error ka fraction hai: ∥ x k + 1 − x ⋆ ∥ ≤ ρ ∥ x k − x ⋆ ∥ ρ ρ ⋆ = κ + 1 κ − 1 η
Kyun chahiye: κ ρ κ κ Nesterov Acceleration dekho.
∫ 0 1 ( ⋯ ) d t x y t 0 1 FTC — aur yahi "curvature ≤ L
E [ ⋅ ] E [ g ] g average value . SGD mein gradient g k average sach wale gradient ke barabar hai: E [ g k ] = ∇ f ( x k )
∇ 2 f ⪯ L I poora curvature matrix afford kar sako, tum har direction ko apni curvature se rescale kar sakte ho — woh Newton's Method (second-order methods) hai. GD uska sasta cousin hai jo sirf slope use karta hai.
Function f maps R^n to a height
Vector length norm measures the gap
Gradient grad f = steepest uphill arrow
Dot product and Cauchy-Schwarz
Update rule step of size eta
Positive semidefinite = curves up everywhere
L smoothness upper curvature
mu strong convexity lower curvature
Step below two over L stays stable
Descent Lemma via integral
Condition number kappa = L over mu
Eigenvalues = curvatures on perpendicular axes
Gradient Descent convergence analysis
Right side cover karo aur aage badhne se pehle har ek yaad karo.
f : R n → R Ek location (n
x ⋆ f ⋆ Lowest point ki location, aur wahan ki height.
∥ v ∥ v 1 2 + ⋯ + v n 2 ; arrow ki straight-line length.
Topic ko ∥ ⋅ ∥ Shrinking gap ∥ x k − x ⋆ ∥
u ⊤ v Do arrows kitna same direction mein point karte hain: ∥ u ∥∥ v ∥ cos θ
Cauchy–Schwarz state karo. ∣ u ⊤ v ∣ ≤ ∥ u ∥∥ v ∥
∇ f Partials ka vector; floor plane mein steepest-uphill arrow.
Hum − ∇ f Directional slope ∇ f ⊤ u u ∇ f
η η > 2/ L Step size; factor ∣1 − η L ∣ > 1
2 1 L x 2 η = 1/ L Factor 1 − η L 0
Hessian ∇ 2 f Second derivatives ka matrix — landscape ki curvature/bendiness.
"Positive semidefinite" (M ⪰ 0 v ⊤ M v ≥ 0 v
∇ 2 f ⪯ L I L I − ∇ 2 f ⪰ 0 L
L ∥∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥ L
μ ∇ 2 f ⪰ μ I μ > 0 μ
Hessian ka eigenvalue geometrically kya hai? Uske perpendicular eigenvector axes mein se ek ke along curvature.
κ L / μ ≥ 1
Descent Lemma state karo aur uska kaam bolo. f ( y ) ≤ f ( x ) + ∇ f ( x ) ⊤ ( y − x ) + 2 L ∥ y − x ∥ 2
Rate ρ Har step mein rakhi gayi error ka fraction; chhota matlab zyada tez (ρ ⋆ = κ + 1 κ − 1
E [ g k ] = ∇ f ( x k ) Noisy SGD gradient average mein sach wala gradient hai.
