Batch Gradient Descent

1. What is Batch Gradient Descent?

In Batch Gradient Descent, we do not update the weights after every individual training example.

Instead:

We process the entire training dataset, calculate the total gradient, and then update the weights once.

The basic idea is:

$$\boxed{ \text{All training examples} \rightarrow \text{Calculate total gradient} \rightarrow \text{Update weights} }$$

This complete process is called one iteration, or commonly one epoch when the entire training dataset has been processed.

---

2. Why do we need Batch Gradient Descent?

Suppose we have $N$ training examples:

$$(x_1,t_1),(x_2,t_2),\ldots,(x_N,t_N)$$

For each example, the neuron produces:

$$y_d$$

and has error:

$$e_d=t_d-y_d$$

If we change the weights immediately after every example, the direction of the update is based on only one example.

Instead, Batch Gradient Descent asks:

What direction will reduce the total error over the entire training dataset?

Therefore, we calculate the total error:

$$\boxed{ E=\frac{1}{2}\sum_{d=1}^{N}(t_d-y_d)^2 }$$

and find the gradient of this total error.

---

3. Mathematical derivation

For a linear neuron:

$$y_d=\sum_{i=1}^{n}w_ix_{di}+b$$

The total squared error is:

$$\boxed{ E=\frac{1}{2}\sum_{d=1}^{N}(t_d-y_d)^2 }$$

The derivative with respect to $w_i$ is:

$$\frac{\partial E}{\partial w_i} = -\sum_{d=1}^{N}(t_d-y_d)x_{di}$$

Therefore, gradient descent gives:

$$w_i^{new} = w_i^{old} -\eta\frac{\partial E}{\partial w_i}$$

Substituting the gradient:

$$\boxed{ w_i^{new} = w_i^{old} + \eta\sum_{d=1}^{N}(t_d-y_d)x_{di} }$$

Similarly, for the bias:

$$\boxed{ b^{new} = b^{old} + \eta\sum_{d=1}^{N}(t_d-y_d) }$$

This is the mathematical form of Batch Gradient Descent for the linear unit.

---

4. Algorithm

The algorithm can be written as:

BATCH-GRADIENT-DESCENT(training_examples, η)

Initialize w1, w2, ..., wn and b

Repeat until termination condition is met:

    Initialize:
        Δwi ← 0
        Δb ← 0

    For each training example (x, t):

        Calculate:
            y ← Σ wi xi + b

        Calculate error:
            e ← t - y

        For each weight wi:
            Δwi ← Δwi + η e xi

        Δb ← Δb + η e

    Update weights:
        wi ← wi + Δwi

    Update bias:
        b ← b + Δb

Notice the important point:

The weights are not updated inside the training-example loop.

They are updated only after all training examples have been processed.

---

5. Simple example

Suppose we have three training examples:

Example	$x$	$t$
1	1	2
2	2	4
3	3	6

Suppose initially:

$$w=1,\qquad b=0$$

and

$$\eta=0.1$$

Example 1

$$y=1(1)+0=1$$ $$e=t-y=2-1=1$$

Weight change:

$$\Delta w=0.1(1)(1)=0.1$$

---

Example 2

Using the same original weight $w=1$:

$$y=1(2)=2$$ $$e=4-2=2$$ $$\Delta w=0.1(2)(2)=0.4$$

Accumulated:

$$\Delta w=0.1+0.4=0.5$$

---

Example 3

$$y=1(3)=3$$ $$e=6-3=3$$ $$\Delta w=0.1(3)(3)=0.9$$

Total:

$$\Delta w=0.1+0.4+0.9=1.4$$

Only now do we update:

$$w_{\text{new}}=1+1.4=2.4$$

So:

$$\boxed{w=2.4}$$

The important observation is that all three examples contributed to one weight update.

---

6. Why is this called "Batch"?

The word batch means the complete set of training examples.

Suppose we have:

$$N=10,000$$

training examples.

In Batch Gradient Descent:

$$\boxed{ 10,000\text{ examples} \rightarrow 1\text{ weight update} }$$

Then the process repeats for the next epoch:

$$\boxed{ 10,000\text{ examples} \rightarrow 1\text{ weight update} }$$

---

7. Batch vs Single-example Update

This is an important distinction for students.

Single-example / Online update

For every example:

$$(x_d,t_d)$$

calculate $y_d$, calculate the error, and immediately update:

$$\boxed{ w_i\leftarrow w_i+\eta(t_d-y_d)x_{di} }$$

So:

$$\boxed{ 1\text{ example}\rightarrow1\text{ update} }$$

Batch Gradient Descent

Process all examples first:

$$\boxed{ w_i\leftarrow w_i+ \eta\sum_{d=1}^{N}(t_d-y_d)x_{di} }$$

So:

$$\boxed{ N\text{ examples}\rightarrow1\text{ update} }$$

---

8. Advantages of Batch Gradient Descent

1. Stable and consistent direction

Because the gradient is calculated using all training examples, the update direction is based on the complete dataset.

This generally makes the optimization path smoother.

---

2. Less noisy updates

With one training example, the update can be strongly influenced by that particular example.

Batch Gradient Descent considers:

$$\boxed{\text{all examples}}$$

so individual examples have less influence on the direction of a single update.

---

3. Exact gradient of the training loss

For the chosen loss function, Batch Gradient Descent calculates the gradient of the entire training dataset loss:

$$\boxed{ \nabla E= \sum_{d=1}^{N}\nabla E_d }$$

Thus, the update follows the true gradient of the empirical training loss.

---

4. Deterministic updates

If the dataset and learning rate remain unchanged, processing the same dataset produces the same gradient and therefore the same update.

This makes it relatively easy to analyze and understand mathematically.

---

5. Good for understanding gradient descent

For teaching the concept of gradient descent, Batch Gradient Descent is particularly useful because students can clearly see:

$$\boxed{ \text{Total Error} \rightarrow \text{Gradient} \rightarrow \text{Weight Update} }$$

---

9. Disadvantages of Batch Gradient Descent

1. Computationally expensive for large datasets

Suppose there are:

$$1,000,000$$

training examples.

A single update requires processing all one million examples.

Therefore:

$$\boxed{ \text{Large dataset} \Rightarrow \text{large computation per update} }$$

---

2. Requires more memory

The complete batch may need to be available for computing the gradient, especially in straightforward implementations.

For very large datasets, this can be inconvenient.

---

3. Slow parameter updates

The weights are updated only after the complete dataset has been processed.

With a very large dataset, the model may have to process a lot of data before making even one update.

---

4. Not ideal for continuously arriving data

Suppose new training examples are continuously arriving.

Batch Gradient Descent is less convenient because it is designed around repeatedly processing a defined training set.

---

10. Comparison with other approaches

This leads naturally to three important forms of gradient descent:

Method	Examples used for one update	Weight updates
Batch Gradient Descent	Entire dataset	1 per epoch
Stochastic Gradient Descent (SGD)	1 example	$N$ per epoch
Mini-batch Gradient Descent	Small batch	$N/B$ per epoch

For example, if:

$$N=1000$$

and mini-batch size:

$$B=100$$

then:

$$\frac{1000}{100}=10$$

updates are made per epoch.

---

11. Visual intuition

Think of the error surface as a mountain landscape.

Batch Gradient Descent:

$$\boxed{ \text{Look at all training examples} \rightarrow \text{Determine overall downhill direction} \rightarrow \text{Take one step} }$$

SGD:

$$\boxed{ \text{Look at one example} \rightarrow \text{Take a step} \rightarrow \text{Look at another example} \rightarrow \text{Take another step} }$$

Mini-batch:

$$\boxed{ \text{Look at a small group} \rightarrow \text{Take a step} \rightarrow \text{Next group} \rightarrow \text{Take a step} }$$

---

12. Summary

Batch Gradient Descent calculates the gradient using all training examples and updates the weights only once after the entire training dataset has been processed.

Mathematically:

$$\boxed{ w_i \leftarrow w_i+ \eta\sum_{d=1}^{N}(t_d-y_d)x_{di} }$$

and

$$\boxed{ b \leftarrow b+ \eta\sum_{d=1}^{N}(t_d-y_d) }$$

The central idea is:

$$\boxed{ \text{Entire dataset} \rightarrow \text{Total gradient} \rightarrow \text{One update} }$$

This is also a very natural bridge from the delta rule to mini-batch gradient descent and backpropagation in MLPs.