0
$\begingroup$

I'm familiar with numerical optimization in Engineering context. I have taken several graduate level engineering optimization and operations research courses. I'm beginning to learn machine learning. One of the constant optimization methods that keeps coming up is Stochastic Gradient Descent (SGD) or mini-batch Gradient Descent. I'm confused on why need SGD besides it supposedly handles big data "efficiently".

As a background, Lets say if we would like to fit a function $f$ to data and we have to estimate $w$ vector that minimizes an objective function $f(w)$ and for the a data set with $i=1...n$ rows.

Stochastic gradient descent (can be presented as follows for each $i^{th}$ row in the data you estimate $w$ for each row or group of rows:

$w_i := w_i - \eta \nabla f(w_i)$ for each $i$, where $\eta$ is pre-specified learning rate.

There are variations of this, where instead of each $i$ you fit to randomly sampled "batch" of data and this called "mini-batch" gradient descent.

In traditional gradient descent, the learning rate $\eta$ is replaced by step length $\alpha^k$ where you find a "close enough" optimal in search direction using some simple line search techniques such as "backtracking" or "strong wolfe line search" and you apply to the whole dataset. In traditional gradient descent the optimal $w^*$ is estimated as follows:

$w^{k+1} := w^k - \alpha^k \nabla f^k(w^k)$ for all $i$ and $k$ is the number of iterations until which the convergence is achieved using some criteria such as $|\nabla f^{k} - \nabla f^{k+1}| < 0.001$.

Here is my question:

Why do we specify learning rate $\eta$ in the SGD, can we simply use line search techniques to optimize $\eta$, i.e.,simply replace $\eta$ with $\alpha^k$ as in traditional gradient descent? Computational cost is not quite high for estimating $\eta$ using approximate line search.

$\endgroup$
9
  • $\begingroup$ We have lots of coverage of (3): stats.stackexchange.com/search?q=bfgs+neural+network $\endgroup$ – Sycorax Aug 12 '20 at 15:17
  • $\begingroup$ I wonder why someone would vote to close as it "needs more focus", I have removed the BFGS part of my question. $\endgroup$ – forecaster Aug 12 '20 at 15:19
  • $\begingroup$ If you read the text below "needs more focus," you can see that it says "This question currently includes multiple questions in one. It should focus on one problem only." $\endgroup$ – Sycorax Aug 12 '20 at 15:24
  • $\begingroup$ I can read the test: The "one" problem is optimization problems in machine learning and SGD is more specific question addressing the problem. I'm so glad that there is high bar ( # of votes to close the question) for closing questions, otherwise this website would not have any questions. $\endgroup$ – forecaster Aug 12 '20 at 15:37
  • 1
    $\begingroup$ (1) We have scant few questions containing keywords from either of your questions. I didn’t find duplicates for either. (2) Asking two questions together when each is answered individually elsewhere is still a duplicate question. (3) If you have questions about how to use this website or how duplicates work or how closure works, you can ask about it in meta. $\endgroup$ – Sycorax Aug 12 '20 at 16:03

Your Answer

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

Browse other questions tagged or ask your own question.