One-dimensional System Arising in Stochastic Gradient Descent

Abstract

We consider SDEs of the form $d{X}_t=|f(X_t)|/t^{\gamma }dt+1/t^{\gamma }d{B}_t$, where $f(x)$ behaves comparably to $|x{|}^k$ in a neighborhood of the origin, for $k\in [1,\infty )$. We show that there exists a threshold value $:=\tilde{\gamma }$ for $\gamma$, depending on $k$, such that when $\gamma \in (1/2,\tilde{\gamma })$ then $\mathbb{P}(X_n\to 0)=0$, and for the rest of the permissible values $\mathbb{P}(X_n\to 0)>0$. The previous results extend for discrete processes that satisfy $X_{n+1}-X_n=f(X_n)/n^{\gamma }+Y_n/n^{\gamma }$. Here, $Y_{n+1}$ are martingale differences that are a.s. bounded. This result shows that for a function $F$, whose second derivative at degenerate saddle points is of polynomial order, it is always possible to escape saddle points via the iteration $X_{n+1}-X_n=F^{\prime }(X_n)/n^{\gamma }+Y_n/n^{\gamma }$ for a suitable choice of $\gamma$.

References in corpus (5)

• A survey of random processes with reinforcement
• How to Escape Saddle Points Efficiently
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Escaping Saddles with Stochastic Gradients