Convergence of a Normal Map-based Prox-SGD Method under the KL
  Inequality
Andre Milzarek Junwen Qiu
In this paper, we present a novel stochastic normal map-based algorithm
($\mathsf{norM}\text{-}\mathsf{SGD}$) for nonconvex composite-type optimization
problems and discuss its convergence properties. Using a time window-based
strategy, we first analyze the global convergence behavior of
$\mathsf{norM}\text{-}\mathsf{SGD}$ and it is shown that every accumulation
point of the generated sequence of iterates $\{\boldsymbol{x}^k\}_k$
corresponds to a stationary point almost surely and in an expectation sense.
The obtained results hold under standard assumptions and extend the more
limited convergence guarantees of the basic proximal stochastic gradient
method. In addition, based on the well-known Kurdyka-{\L}ojasiewicz (KL)
analysis framework, we provide novel point-wise convergence results for the
iterates $\{\boldsymbol{x}^k\}_k$ and derive convergence rates that depend on
the underlying KL exponent $\boldsymbol{\theta}$ and the step size dynamics
$\{\alpha_k\}_k$. Specifically, for the popular step size scheme
$\alpha_k=\mathcal{O}(1/k^\gamma)$, $\gamma \in (\frac23,1]$, (almost sure)
rates of the form $\|\boldsymbol{x}^k-\boldsymbol{x}^*\| = \mathcal{O}(1/k^p)$,
$p \in (0,\frac12)$, can be established. The obtained rates are faster than
related and existing convergence rates for $\mathsf{SGD}$ and improve on the
non-asymptotic complexity bounds for $\mathsf{norM}\text{-}\mathsf{SGD}$.