6
$\begingroup$

Given a linear model

$$y = X\beta + \epsilon$$

we can estimate parameters $\hat{\beta}$ using two different ways - ordinary least squares (OLS) and gradient descent (GD). Both of them boil down to minimizing mean squared error (MSE) by finding its global minimum. The difference is that while OLS finds exact solution, GD iteratively approaches it, but may never find exact answer.

For OLS we have usual set of parameter estimates, most notably standard error $SE(\hat{\beta})$. But in some cases OLS is not an option (e.g. data matrix is too large), so we have to use GD.

I'm trying to figure out:

  1. Does it make sense at all to apply SE to parameters learned using gradient descent?
  2. If so, how do we calculate it? Do other dependent things like t-statistic and significance test take the usual form?
  3. What about stochastic gradient descent (SGD)? Is there any hope to assess its parameters?

For common reference:

$\endgroup$
  • $\begingroup$ You could maybe use the profile likelihood near the optimum to get the individual standard errors. $\endgroup$ – Glen_b -Reinstate Monica Oct 14 '14 at 0:09
  • $\begingroup$ Thanks, @Glen_b, it seems to be a good approach. Though, I need to upgrade my skills in this area, so I'll take some time to learn more about profile likelihood and hopefully come back with complete solution. $\endgroup$ – ffriend Oct 14 '14 at 20:35
2
$\begingroup$

I found that bootstrap gives estimates that are pretty close to those from OLS, but works with literally any training algorithm.

Bootstrap is a kind of Monte Carlo method and roughly boils down to repeated sampling with replacement from original dataset and collecting values of a target statistic. Having a set of statistic values, it becomes trivial to calculate their mean and standard error. G. James et al. provide experimental evidence of closeness of OLS and bootstrap results. Without further explanation, I'm giving a link to their excellent work (see pages 187-190 for bootstrap explanation and 195-197 for experiments):

$\endgroup$
-1
$\begingroup$

Gradient descent(ascent) is an iterative process usually employed during function approximation to solve parameters of a non-linear function. OLS wholly involves linear equations which are strictly additive and not multiplicative based on powers, log(), exp(), etc. Thus, OLS does not need to be solved iteratively, and only a one-step matrix operation, i.e., $\boldsymbol{\beta}=(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$, is required for obtaining the coefficients.

$\endgroup$
  • $\begingroup$ Sure, unless you data matrix $\mathbf{X}$ has billions of rows. GD and, in particular, Stochastic GD, is more flexible than OLS and is extremely useful for analyzing amounts of data that do not fit into main memory. That's why I find it important to have SD estimation not only for OLS, but for GD too. $\endgroup$ – ffriend Apr 12 '15 at 13:25
  • $\begingroup$ For billions of records, I would cluster the dataset first, and then run regression with cross-validation. There may also be some non-linearity among the records, so a neural network might be best, since the NN and its learned connection weights would form the equation. The biggest problem with (more than) hundreds of thousands of records is misclassification error. $\endgroup$ – JoleT Apr 12 '15 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.