Title: On SGD's Failure in Practice: Characterizing and Overcoming Stalling,
Abstract: Stochastic Gradient Descent (SGD) is widely used in machine learning problems
to efficiently perform empirical risk minimization, yet, in practice, SGD is
known to stall before reaching the actual minimizer of the empirical risk. SGD
stalling has often been attributed to its sensitivity to the conditioning of
the problem; however, as we demonstrate, SGD will stall even when applied to a
simple linear regression problem with unity condition number for standard
learning rates. Thus, in this work, we numerically demonstrate and
mathematically argue that stalling is a crippling and generic limitation of SGD
and its variants in practice. Once we have established the problem of stalling,
we generalize an existing framework for hedging against its effects, which (1)
deters SGD and its variants from stalling, (2) still provides convergence
guarantees, and (3) makes SGD and its variants more practical methods for
minimization.