Optimize multiple linear regression with gradient descent

The Linear Regression objective is given by $$J(\theta) = \frac{1}{2}\sum_{i = 1}^N\Big(h(x^{(i)})- y^{(i)}\Big)^2$$ and we assumed that the hypothesis function has the form $$h(x) = \sum_{i = 0}^n\theta_i x_i = \theta^\top x$$ Consider the case when the hypothesis is instead given by $$h_\phi(x) = \sum_{i = 0}^m\theta_i \phi(x)_i = \theta^\top \phi(x)$$ where $$\phi : \mathbb{R}^n \mapsto \mathbb{R}^m$$ is an arbitrary feature map. Work out the gradient descent step for this new hypothesis function

Solution For one training sample the error is given by \begin{align*} J(\theta)&= \frac{1}{2}(h_\theta(x) - y)^2\\ &=\frac{1}{2}(\theta^\top\phi(x) - y)^2 \end{align*} The gradient step is $$\theta_j = \theta_j - \alpha\frac{\partial J(\theta)}{\partial \theta_j}$$ and the gradient is \begin{align*} \frac{\partial J(\theta)}{\partial \theta_j} &= (h_\phi(x) - y)\frac{\partial }{\partial \theta_j}(h_\phi(x) - y)\\ &= (h_\phi(x) - y)\frac{\partial }{\partial \theta_j}\Big(\sum_{i = 0}^m\theta_i\phi(x)_i - y\Big)\\ &=(h_\phi(x) - y)\phi(x)_j \end{align*} Hence $${\color{red}\theta_j} := \theta_j + \alpha (y - h_\phi(x))\phi(x)_j\tag{1}$$

My questions

1. In (1), shouldn't we write $${\color{red}\theta_{j+1}}$$ instead of $${\color{red}\theta_{j}}$$?
2. Do we always use gradient descent with one single training example? Is it possible to use a batch or the whole training set to compute a step.
3. If yes to 2. what would be the mathematical form? / If no to 2. is it because it mathematically not possible/hard or is it because it computacionaly too expensive?

Edit

The step using the whole training set can be computed as \begin{align*} \frac{\partial J(\theta)}{\partial \theta_j} &= \frac{\partial}{\partial \theta_j} \sum_{i = 1}^N\frac{1}{2}(h_\theta(x)^{(i)} - y^{(i)})^2\\ &= \sum_{i = 1}^N\frac{\partial}{\partial \theta_j}\frac{1}{2}(h_\theta(x)^{(i)} - y^{(i)})^2\\ &=\sum_{i = 1}^N(h_\phi(x)^{(i)} - y^{(i)})\phi(x)_j \end{align*} Hence $$\theta_j := \theta_j + \alpha \sum_{i = 1}^N(h_\phi(x)^{(i)} - y^{(i)})\phi(x)_j$$

(1): $$\theta$$ is an $$m$$-dimensional vector, and $$\theta_j$$ is referring to its $$j$$-th component. Equation (1) simply means reset the $$\theta_j$$ to be the right hand side. To avoid confusion, this can be written as $$\theta_j^{(t+1)} = \theta_j^{(t)} + \ldots$$ so that the step count is in the superscript.

(2): No, you can use any batch size (including the whole training set) to perform a step. Using the whole training set for each step is called batch gradient descent. Choosing smaller batch sizes (such as a single training example) is called stochastic gradient descent if training examples are randomly chosen on each step. I would say that batch gradient descent is more common, especially for linear regression.

(3): It is not mathematically hard, because the sum and derivative can be interchanged: $$\frac{\partial J(\theta)}{\partial \theta_j} = \frac{\partial}{\partial \theta_j} \sum_{i=1}^N \frac{1}{2} (h_{\phi}(x^{(i)}) - y)^2 = \sum_{i=1}^N \frac{\partial}{\partial \theta_j} \frac{1}{2} (h_{\phi}(x^{(i)}) - y)^2$$ You already know how to compute each term in the sum, so you just have to add them all together. However, if $$N$$ is extremely large (like a million), then computing this sum is prohibitive.

When $$\phi$$ is the identity function, then this is the usual least squares problem. Notice that this has a closed form solution (see "Solving the least squares problem"). In other words, you don't have to use gradient descent at all! I'm not sure if a similar trick works for your case, but it would be interesting to try.

• Many thanks for your comment @pbn990. I tried to devlop more your answer (3) in my edit, but it looks wrong as $\alpha$ now multiplies a sum. What would be the correct devlopped answer for the computation of the gradient step with the whole training set?
– ecjb
Jan 1, 2020 at 16:57
• Hi, it looks correct to me... the sum is still a scalar quantity so there is nothing wrong with multiplying it by $\alpha$!
– user446766
Jan 1, 2020 at 17:00