Convergence Behaviour of Batch Gradient Descent (BGD) vs Stochastic Gradient Descent (SGD)

 

Convergence Behaviour of Batch Gradient Descent (BGD) vs Stochastic Gradient Descent (SGD)

Batch Gradient Descent (BGD)

  • Uses the entire dataset to compute the gradient at each iteration.

  • The loss function decreases smoothly and monotonically (for suitable learning rates).

  • Convergence path is stable and deterministic.

  • For convex loss functions, BGD guarantees convergence to the global minimum.

  • Convergence can be slow per iteration due to high computational cost.

  • Less suitable for very large datasets.

📌 Behavior: Smooth, steady convergence without oscillations.

Stochastic Gradient Descent (SGD)

  • Uses one randomly selected data point per update.

  • The loss function shows fluctuations instead of smooth decrease.

  • Convergence path is noisy and stochastic.

  • Converges in expectation to the minimum, not exactly at every step.

  • Faster initial progress but may oscillate near the minimum.

  • Noise can help escape saddle points and shallow local minima.

📌 Behavior: Fast but zig-zag convergence around the minimum.

Comparison Summary

Aspect            Batch GDStochastic GD
Gradient estimate                Exact    Noisy
Convergence path                Smooth    Zig-zag
Stability                High    Low
Speed per update                Slow    Fast
Final convergence                Exact (convex case)    Approximate
Suitability                Small datasets    Large datasets

Conclusion

Batch Gradient Descent converges smoothly and deterministically to the minimum, while Stochastic Gradient Descent converges faster but with oscillations due to noisy gradient estimates.

Comments

Post a Comment

Popular posts from this blog

Advanced Mathematics for Computer Science HNCST409 KTU BTech Honors 2024 Scheme

About Me Syllabus Advanced Mathematics for Computer Science HNCST409 BTech Honors 2024 Model Question Paper and Answers Module- I Number Theory  Introduction Group , Ring and Fields Divisibility Modular Arithmetic and Congruences Equivalence Relation - Congruence Linear Congruences Solving simultaneous congruences- CRT Modular Inverses      Euclidean algorithm      Extended Euclidean algorithm  Euler’s and Fermat’s little theorem  Euler's Totient Function Prime Numbers and Prime-Power Factorization Fermat and Mersenne Prime Primality Testing and Factorization Wilson's Theorem Pseudo Primes and Carmichael Numbers Primality testing       Miller-Rabin      AKS Galois Field (introduction and basic operations) RSA cryptosystem: key generation - encryption/decryption  Hash functions (introduction) Module - II Optimization Convex and Non Convex sets Convex Hull Identifying convex sets Applicatio...
Read more

AKS Primality Testing

AKS Primality Testing Algorithm Short Description The AKS (Agrawal–Kayal–Saxena) algorithm is a deterministic polynomial-time algorithm used to test whether a given number is prime. Unlike probabilistic methods such as the Fermat or Miller–Rabin tests, AKS always produces a correct result without relying on randomness. Introduced in 2002 by Agrawal, Kayal, and Saxena, this algorithm resolved a long-standing open problem in computer science by proving that primality testing belongs to the complexity class P . 2. Mathematical Foundation 2.1 Fermat’s Little Theorem (Classical) If p p p is prime and a a a is not divisible by p p p : a p ≡ a ( m o d p ) a^{p} \equiv a \pmod{p} This is the basis of many probabilistic tests. ❗ Problem: Some composite numbers (Carmichael numbers) also satisfy this. 3. Key Insight Behind AKS Instead of working with numbers , AKS works with polynomials . AKS Theorem For an integer n > 1 n > 1 n > 1 , n  is prime     ⟺    ( ...
Read more

Galois Field and Operations

  What Is a Galois Field? A Galois Field , or finite field , is a mathematical system with a finite number of elements in which the operations of addition, subtraction, multiplication, and division (except by zero) are well defined and satisfy all field properties. Galois fields are denoted by GF(pⁿ) , where: p is a prime number (called the characteristic) n is a positive integer They are named after Évariste Galois , whose work laid the foundation of modern algebra. Types of Galois Fields 1. Prime Fields: GF(p) A prime field contains exactly p elements : G F ( p ) = { 0 , 1 , 2 , … , p − 1 } GF(p) = \{0, 1, 2, \ldots, p-1\} All arithmetic is performed modulo p . Arithmetic Operations in GF(p) (Mod p Arithmetic) Let us consider GF(7) as an example. 1. Addition (mod p) Add normally and reduce modulo p. 5 + 4 = 9 ≡ 2 ( m o d 7 ) 5 + 4 = 9 \equiv 2 \pmod{7} 2. Subtraction (mod p) Subtract normally and reduce modulo p. 3 − 5 = − 2 ≡ 5 ( m o d 7 ) 3 - 5 = ...
Read more