In section 3.3 of Bottou et al (2018), under the 'intuitive motivation' paragraph, the authors claim that 'a minimiser of empirical risk for the larger set $S$ is clearly given by a minimiser for the smaller set $S_{\text{sub}}$', thereby arguing that the stochastic optimisation is sufficient over batch optimisation. However I am aware that the loss function surface may contain multiple local minima. Is that where the stochastic method might run into trouble?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Batch gradient descent (GD) (or any GD) can run into local minima problem because the algorithm is not exact, it is a heuristic.
The paragraph starts with assuming that $S$ is a collection of the same samples in $S_{sub}$ repeated 10 times. So, the minima don't change. It also states that, in large-scale real data, we don't have exact duplicates, but there is approximate redundancy, thus mimicking the duplication assumed above. And, they say that, due to this redundancy, using all the data in every iteration is inefficient.
The above was my take on the paragraph you mentioned. But, I believe this post can give you some perspective on the noise introduced by SGD and how it may be useful.
-
$\begingroup$ Ah that was my misunderstanding (on how S is related to Ssub). But thanks for the intuitive explanation $\endgroup$ Commented Aug 29, 2021 at 12:07