Lower error bounds for the stochastic gradient descent optimization algorithm: Sharp convergence rates for slowly and fast decaying learning rates

Understand

The stochastic gradient descent (SGD) optimization algorithm plays a central role in a series of machine learning applications.

• The scientific literature provides a vast amount of upper error bounds for the SGD method.
• Much less attention as been paid to proving lower error bounds for the SGD method.
• It is the key contribution of this paper to make a step in this direction.