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.

  • $\begingroup$ We have lots of coverage of (3): stats.stackexchange.com/search?q=bfgs+neural+network $\endgroup$
    – Sycorax
    Commented Aug 12, 2020 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
    Commented Aug 12, 2020 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
    Commented Aug 12, 2020 at 15:24
  • 2
    $\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
    Commented Aug 12, 2020 at 16:03
  • 1
    $\begingroup$ I just found a NIPS2019 paper "Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates" while googling your question. The paper develops a stochastic variant of the Armijo rule for the SGD used in overparametrized models. I am not familiar with this area, but I guess it is related. $\endgroup$
    – Miles N.
    Commented Aug 31, 2022 at 6:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.