1.2.8
Intuition Ek-sentence ideaEk function convex hai agar uske graph pe koi bhi do points ko connect karne wali straight line kabhi graph ke neeche nahi jaati — matlab yeh ek single valley (bowl) jaisi dikhti hai. Optimization convex functions ko isliye pasand karta hai kyunki koi bhi local minimum automatically global minimum hota hai , toh gradient descent kabhi "trap" nahi ho sakta.
Machine learning mostly ek loss function L ( θ ) minimize karna hai. Poora game yeh hai: aisi parameters θ
Agar L convex hai: essentially ek hi basin hai. Slope ke saath neeche jaao → guaranteed best answer milega. (Linear/logistic regression, SVM.)
Agar L non-convex hai: multiple valleys, ridges, saddle points. Neeche jaana tumhe ek bekar valley (ek bura local minimum ) mein fansa sakta hai. (Neural networks.)
Toh "convex vs non-convex" batata hai tumhari optimization kitni mushkil hai aur jo answer tumhara converge hua usp trust kar sakte ho ya nahi .
Ek set C convex hai agar koi bhi do points x , y ∈ C C λ ∈ [ 0 , 1 ] λ x + ( 1 − λ ) y ∈ C
Definition Convex function (master definition)f convex hai agar apne domain mein sabhi x , y λ ∈ [ 0 , 1 ] f ( λ x + ( 1 − λ ) y ) ≤ λ f ( x ) + ( 1 − λ ) f ( y ) Left side = beech wale point par f curve par .
Right side = ( x , f ( x )) ( y , f ( y )) seedhi chord par ki value.
"Curve chord ke neeche (ya uske upar) rehti hai." Agar x = y < ho, toh yeh strictly convex hai.
Concave = inequality ko flip karo (≥ − f
Midpoint λ = 2 1 f ( 2 x + y ) ≤ 2 f ( x ) + f ( y ) .
Ek differentiable f ⟺ har tangent line ke upar rehta hai:
f ( y ) ≥ f ( x ) + ∇ f ( x ) ⊤ ( y − x ) ∀ x , y .
Intuition Yeh equivalent kyun haiEk tangent "instant chord" hai. Agar har chord curve ke upar hai, toh ek endpoint ko x f ∇ f = 0 zaroor global min hota hai: tangent flat hai, aur sab kuch flat line ke upar baitha hai.
Twice-differentiable f
1D: convex ⟺ f ′′ ( x ) ≥ 0 Multivariate: convex ⟺ Hessian ∇ 2 f ( x ) positive semidefinite (PSD) hai, matlab v ⊤ ∇ 2 f ( x ) v ≥ 0 v
Hum dikhate hain: agar f ′′ ( x ) ≥ 0
Step 1 — Taylor with exact remainder. x y c f ( y ) = f ( x ) + f ′ ( x ) ( y − x ) + 2 1 f ′′ ( c ) ( y − x ) 2 . Yeh step kyun? Taylor's theorem ek exact expression deta hai, curvature term ko isolate karta hai.
Step 2 — Remainder ko bound karo. Kyunki f ′′ ( c ) ≥ 0 ( y − x ) 2 ≥ 0 2 1 f ′′ ( c ) ( y − x ) 2 ≥ 0. Yeh step kyun? Yahi unknown term hai; nonnegative curvature ise nonnegative banati hai.
Step 3 — Conclude karo.
f ( y ) ≥ f ( x ) + f ′ ( x ) ( y − x ) . Yeh step kyun? Yahi exactly Lens 2 hai — graph tangent ke upar — isliye convex. ■
f ( x ) = x 2 f ′′ ( x ) = 2 ≥ 0 x Strictly convex. x = 0 Yeh step kyun? Constant positive second derivative ⇒ hamesha upar curve karta hai ⇒ bowl.
f ( x ) = x 3 f ′′ ( x ) = 6 x x < 0 x > 0 ≥ 0 x = 0 inflection point hai (ek saddle-jaisa flat spot), minimum nahi.
Yeh step kyun? f ′′
f ( x , y ) = x 2 + y 2 ∇ 2 f = [ 2 0 0 2 ] 2 , 2 > 0 Yeh step kyun? Har jagah PSD Hessian ⇒ har direction mein convex.
f ( x , y ) = x 2 − y 2 [ 2 0 0 − 2 ] 2 , − 2 not convex. Origin ek saddle point hai: x y Yeh step kyun? Ek negative eigenvalue PSD ko khatam kar deta hai; ek negative direction neeche bend karti hai.
f ( x ) = e x f ( x ) = − log x d x 2 d 2 e x = e x > 0 d x 2 d 2 ( − log x ) = 1/ x 2 > 0 x > 0
f ′′ ( x 0 ) ≥ 0 f Kyun sahi lagta hai: second-order test mein f ′′ ≥ 0 Fix: convexity ke liye f ′′ ≥ 0 har jagah chahiye, sirf ek point par nahi. x 3 f ′′ ( 0 ) = 0 Puri domain check karo.
Common mistake "Gradient descent hamesha global minimum dhundh leta hai."Kyun sahi lagta hai: har textbook picture mein (usually ek bowl!) aisa hota hi hai.
Fix: yeh guarantee sirf convex losses ke liye hai. Non-convex neural nets par, GD local minima mein settle ho sakta hai ya saddle points ke paas reng sakta hai. (Practice mein high-dim nets mein bahut kam bure local minima hote hain, lekin guarantee gone hai.)
Common mistake "Ek local min ek local min hai; convex ho ya nahi, same cheez hai."Kyun sahi lagta hai: locally landscape bilkul same dikhti hai.
Fix: convexity ek global property hai jo local ko global se jorti hai. Convex f
Common mistake "Concave aur convex opposites hain, toh ek function ek ya doosra hoga."Kyun sahi lagta hai: words ek dichotomy jaisi lagte hain.
Fix: zyaadatar functions na hi convex na hi concave hote hain (jaise sin x dono hote hain.
Convex function definition (inequality form) f ( λ x + ( 1 − λ ) y ) ≤ λ f ( x ) + ( 1 − λ ) f ( y ) λ ∈ [ 0 , 1 ]
Convexity ka geometric meaning Graph par koi bhi do points ko join karne wala line segment graph par ya uske upar rehta hai (bowl shape).
1D mein second-order convexity test f ′′ ( x ) ≥ 0 x
Multivariate convexity test Hessian ∇ 2 f ( x ) v ⊤ H v ≥ 0
Convexity ka key optimization payoff Har local minimum ek global minimum hai (stationary point ⇒ global min).
Kya x 3 Nahi — f ′′ = 6 x x = 0
Kya x 2 + y 2 Haan — Hessian = diag ( 2 , 2 )
x 2 − y 2 Hessian eigenvalues 2 , − 2
Kaunse functions convex AUR concave dono hote hain? Sirf affine (linear + constant) functions.
Neural nets mein non-convex loss kyun hoti hai? Nonlinear activations ki composition multiple minima/saddles banati hai ⇒ Hessian har jagah PSD nahi.
First-order convexity condition f ( y ) ≥ f ( x ) + ∇ f ( x ) ⊤ ( y − x )
Recall Feynman: ek 12-saal ke bachche ko samjhaoSocho ek skateboard ramp. Ek convex ramp ek smooth U-shaped bowl hai: chahe marble kahan bhi girao, woh hamesha ek hi sabse neeche wale point par roll karke aata hai. Easy — tum fasa nahi sakte. Ek non-convex ramp ek bumpy skate park hai jisme bahut saare dips hain. Tumhara marble ek chhote dip mein ruk sakta hai jo sabse gahra nahi hai, yeh sochke "main ho gaya!" jabki ek aur gehri valley seedha pahaad ke paar baithti hai. Convex = ek honest bowl; non-convex = fake bottoms wali tricky landscape.
Mnemonic Yaad rakhne ka tarika"Convex = Curve Cups Coffee." Ek convex curve upar ki taraf cups karti hai (coffee ☕ pakadti hai, f ′′ ≥ 0 neeche ki taraf caves in karti hai (spill ho jaati hai). Aur "local = global" sirf convex world mein hota hai.
ML minimizes loss L theta
Chord definition f of avg <= avg of f
Convex single valley bowl
Gradient descent finds best
Linear/logistic regression SVM
Tangent line f above tangent
