Why is gradient descent inefficient for large data set?

Question

Let's say our data set contains 1 million examples, i.e., $x_1, \ldots, x_{10^6}$, and we wish to use gradient descent to perform a logistic or linear regression on these data set.

What is it with the gradient descent method that makes it inefficient?

Recall that the gradient descent step at time $t$ is given by:

$$w_{t+1} = w_{t} + \eta_t \nabla f(x)$$

where $f$ is the loss function.

I am not seeing anything out of the ordinary with the above step that causes the algorithm to be inefficient. Is it the computation of $\nabla f(x)$? Couldn't this operation be pre-computed, i.e., each $\frac{\partial f}{\partial x}$ already computed, and simply evaluate them at each data point $x_i?$

Answer 1

It would help if you provided a context to the claim that the gradient descent is inefficient. Inefficient relative to what?

I guess that the missing context here is the comparison to stochastic or batch gradient descent in machine learning. Here's how to answer the question in this context. You are optimizing the parameters of the model, even hyperparameters. So, you have the cost function $\sum_{i=1}^n L(x_i|\Theta)$, where $x_i$ - your data, and $\Theta$ - vector of parameters, and $L()$ - loss function. To minimize this cost you use gradient descent over the parameters $\theta_j$: $$ \frac{\partial}{\partial \theta_j}\sum_{i=1}^nL(\Theta|x_i)$$

So, you see that you need to get the sum over all data $x_{i=1,\dots,n}$. This is unfortunate, because it means that you keep looping through the data for each step of your gradient descent. That's how the batch and stochastic gradient descent comes up: what if we sampled from the data set, and calculated the gradient on a sample, not the full set? $$ \frac{\partial}{\partial \theta_j}\sum_{k=1}^{n_s}L(\Theta|x_k)$$ Here, $n_s$ is the number of observations in the sample $s$. So, if your sample is 1/100th of the total set, you speed up your calculations by 100 times! Obviously, this introduces the noise, which lengthens the learning, but noise is decreases at rate of $\sqrt n$ while calculation amount increases at $n$, so this trick may work.

Alternatively, insteado waiting until full sum $\sum_{i=1}^n$ is calculated, you could split this into batches, and do a step for each batch $\sum_{s=1}^M\sum_{i_s=1}^{n_s}$. This way you would have done M steps by the time the sum over entire data set is calculated. These would be noisier steps, but noise cancels out over time.

Answer 2

There are two ways in which gradient descent may be inefficient. Interestingly, they each lead to their own method for fixing up, which are nearly opposite solutions. The two problems are:

(1) Too many gradient descent updates are required.

(2) Each gradient descent step is too expensive.

In regards to (1), comparing gradient descent with methods that take into account information about the second order derivatives, gradient descent tends to be highly inefficient in regards to improving the loss at each iteration. A very standard method, Newton's Method, generally takes much fewer iterations to converge, i.e. for logistic regression, 10 iterations of Newton's Method will often have lower loss than the solution provided by 5,000 iterations of gradient descent. For linear regression, this is even more extreme; there's a closed form solution! However, as the number of predictors gets very large (i.e. 500+), Newton's Method/directly solving for linear regression can become too expensive per iteration due to the amount of matrix operations required, while gradient descent will have considerably less cost per iteration.

In regards to (2), it is possible to have such a large dataset that each iteration of gradient descent is too expensive to calculate. Computing the gradient will require $O(nk)$ operations ($n $ = sample size, $k$ = number of covariates). While $n = 10^{6}$ is not a problem at all on modern computers for values of $k < 100$, certainly something like $n = 10^{12}$, $k = 10^3$ will be. In this case, methods that approximate the derivative based on smaller subsets of the data are more attractive, such as stochastic gradient descent.

I say that these fixes are nearly opposite, in that something like Newton's method is more costly but more efficient (in terms in of change in loss) per update, while stochastic gradient descent is actually less efficient but much computationally cheaper per update.

Answer 3

First let me suggest an improvement to your notation. In particular, let's denote the loss function by $L(w)$ rather than $f(x)$. Using the letter $L$ is simply a personal preference of mine since it reminds me that we're dealing with the Loss. The more substantive change is making it clear that the loss is a function of the weights $w$ rather than the data $x$. Importantly, the gradient is with respect to $w$ not $x$. So $$ \nabla L(w) = \left(\frac{\partial L}{\partial w_1}, \dots, \frac{\partial L}{\partial w_D} \right), $$ where $D$ is the dimensionality of your data.

Despite the fact that we should think of the loss as a function of the weights $w$, any reasonable loss function will still depend on the entire dataset $x$ (if it didn't, it wouldn't be possible to learn anything from the data!). In linear regression, for example, we typically use the sum-of-squares loss function $$ L(w) = \sum_{i=1}^N (y_i - w^Tx_i)^2. $$ So evaluating the gradient $\nabla L(w)$ for a particular set of weights $w$ will require a sum over all $N$ points in the dataset $x$. If $N = 10^6$, then every incremental step in the gradient descent optimization will require on the order of a million operations, which is quite expensive.

Answer 4

Short answer: Calculating gradient needs to sum over all the data points. If we have large amount of data, then it takes a long time.

I have a detailed answer here.

How could stochastic gradient descent save time comparing to standard gradient descent?

---

On the other hand, always keep in mind there are direct methods in addition to iterative methods (gradient decent). If we want to solve a least square problem, direct method can be super efficient. For example, QR decomposition. If we do not have too many features, it is very fast.

When you verify it, it may surprise you: 5 million data points with 2 features, Solving the linear regression / least square takes couple of seconds!

x=matrix(runif(1e7),ncol=2)
y=runif(5e6)
start_time <- Sys.time()
lm(y~x)
end_time <- Sys.time()
end_time - start_time
# Time difference of 4.299081 secs

Answer 5

Although the two examples you mentioned are usually convex I'll add one point about non-convex problems. In my opinion there are two main reason why (batch) gradient descent might be considered "inefficient". The first point about the computational effort of calculating the gradient of a "large" sum of functions has already been very clearly outlined in the other answers. For non-convex problems however GD has the problem of usually getting stuck in a "close" local minimum. This minimum might be very bad in comparison to the global minimum. SGD or mini-batch GD have the "advantage" of wandering around (at least partially) randomly and thus might have the chance of finding a better local minimum. See this CV answer here. Or this other CV post outlining how randomness might be beneficial.