The "sample size" you're talking about is referred to as batch size, $B$. The batch size parameter is just one of the hyper-parameters you'll be tuning when you train a neural network with mini-batch Stochastic Gradient Descent (SGD) and is data dependent. The most basic method of hyper-parameter search is to do a grid search over the learning rate and batch size to find a pair which makes the network converge.
To understand what the batch size should be, it's important to see the relationship between batch gradient descent, online SGD, and mini-batch SGD. Here's the general formula for the weight update step in mini-batch SGD, which is a generalization of all three types. [2]
$$
\theta_{t+1} \leftarrow \theta_{t} - \epsilon(t) \frac{1}{B} \sum\limits_{b=0}^{B - 1} \dfrac{\partial \mathcal{L}(\theta, \textbf{m}_b)}{\partial \theta}
$$
- Batch gradient descent, $B = |x|$
- Online stochastic gradient descent: $B = 1$
- Mini-batch stochastic gradient descent: $B > 1$ but $B < |x|$.
Note that with 1, the loss function is no longer a random variable and is not a stochastic approximation.
SGD converges faster than normal "batch" gradient descent because it updates the weights after looking at a randomly selected subset of the training set. Let $x$ be our training set and let $m \subset x$. The batch size $B$ is just the cardinality of $m$: $B = |m|$.
Batch gradient descent updates the weights $\theta$ using the gradients of the entire dataset $x$; whereas SGD updates the weights using an average of the gradients for a mini-batch $m$. (Using the average as opposed to a sum prevents the algorithm from taking steps that are too large if the dataset is very large. Otherwise, you would need to adjust your learning rate based on the size of the dataset.) The expected value of this stochastic approximation of the gradient used in SGD is equal to the deterministic gradient used in batch gradient descent. $\mathbb{E}[\nabla \mathcal{L}_{SGD}(\theta, \textbf{m})] = \nabla \mathcal{L}(\theta, \textbf{x})$.
Each time we take a sample and update our weights it is called a mini-batch. Each time we run through the entire dataset, it's called an epoch.
Let's say that we have some data vector $\textbf{x} : \mathbb{R}^D$, an initial weight vector that parameterizes our neural network, $\theta_0 : \mathbb{R}^{S}$, and a loss function $\mathcal{L}(\theta, \textbf{x}) : \mathbb{R}^{S} \rightarrow \mathbb{R}^{D} \rightarrow \mathbb{R}^S$ that we are trying to minimize. If we have $T$ training examples and a batch size of $B$, then we can split those training examples into C mini-batches:
$$
C = \lceil T / B \rceil
$$
For simplicity we can assume that T is evenly divisible by B. Although, when this is not the case, as it often is not, proper weight should be assigned to each mini-batch as a function of its size.
An iterative algorithm for SGD with $M$ epochs is given below:
\begin{align*}
t &\leftarrow 0 \\
\textrm{while } t &< M \\
\theta_{t+1} &\leftarrow \theta_{t} - \epsilon(t) \frac{1}{B} \sum\limits_{b=0}^{B - 1} \dfrac{\partial \mathcal{L}(\theta, \textbf{m}_b)}{\partial \theta} \\
t &\leftarrow t + 1
\end{align*}
Note: in real life we're reading these training example data from memory and, due to cache pre-fetching and other memory tricks done by your computer, your algorithm will run faster if the memory accesses are coalesced, i.e. when you read the memory in order and don't jump around randomly. So, most SGD implementations shuffle the dataset and then load the examples into memory in the order that they'll be read.
The major parameters for the vanilla (no momentum) SGD described above are:
- Learning Rate: $\epsilon$
I like to think of epsilon as a function from the epoch count to a learning rate. This function is called the learning rate schedule.
$$
\epsilon(t) : \mathbb{N} \rightarrow \mathbb{R}
$$
If you want to have the learning rate fixed, just define epsilon as a constant function.
- Batch Size
Batch size determines how many examples you look at before making a weight update. The lower it is, the noisier the training signal is going to be, the higher it is, the longer it will take to compute the gradient for each step.
Citations & Further Reading:
- Introduction to Gradient Based Learning
- Practical recommendations for gradient-based training of deep architectures
- Efficient Mini-batch Training for Stochastic Optimization
Best Answer
If batch consists of $n$ samples, then you use each $x_i$ to predict each $y_i$, calculate the error to judge how much wrong are you about the prediction, and then aggregate the errors for all the samples (average them).
No. You cannot use $x_i$ to predict $y_j$ for $i\ne j$. If yo have data on car models and want to predict the brand, then information about cars 1, 2, and 3 does not tell you anything about brand of car 4. You use each $x_i$ to predict $y_i$, then use the information about the error you made to update the weights.
You average the errors, then use them to update the weights. For each of the samples your model uses same weights, then you predict and use the overall error to update the weights.
I cannot comment on particular case, but as about computation time, you can run into two kinds of problems: either the batch is too large, or it is too small. If it is too big, it may be the case that you won't be able to train the model since it wouldn't fit your computer's (and graphical card's) memory. It can happen that the data and weights will fit the memory, but not much will be left for computations and it will slow everything down. On another hand, if your sample is too small, then you are wasting resources. With high-quality libraries for statistical computations like TensorFlow etc., they are designed to efficiently carry mathematical operations (especially on GPUs), so doing things like matrix multiplication is easy for them. This means that repeating the same operation multiple times (for-loop over samples) can be slower then calculating everything all-at-once. That is why choosing optimal batch size may save you computation time.