# About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

• What are the minimal conditions we know of under which we can prove that a stochastic gradient based algorithm can convergence to criticality on a non-convex objective?

• Are there any necessary conditions that we know of that the objective, algorithm and the oracle have to satisfy to get convergence?

For example : I would be very interested to know of proofs which do not need to assume that the objective has bounded gradients (or that the function is upperbounded). These look very rare to satisfy in usual learning situations! (What are natural non-convex learning situations which have bounded gradient losses?)

I am not considering methods like NSVRG which allow the algorithm to compute the exact gradients sometimes. I am specifically looking at algorithms where the gradient oracle is the only oracle being invoked and it is necessarily always noisy.

## 2 Answers

I know about a few recent papers that try to find what properties enjoy the parameters found by DNN traing algorithms . Take a look at this paper https://arxiv.org/pdf/1412.0233.pdf . I quote from the abstract : "We study the connection between the highly non-convex loss function of a simple model of the fully-connected feed-forward neural network and the Hamiltonian of the spherical spin-glass model under the assumptions of: i) variable independence, ii) redundancy in network parametrization, and iii) uniformity. ... We conjecture that both simulated annealing and SGD converge to the band of low critical points, and that all critical points found there are local minima of high quality "

There is a lot of recent work on these questions spurred by interest in deep learning and other non-convex optimization tasks. If the objective is differentiable and smooth, then you do not need to assume bounded gradients and there are quite a few assumptions on the noise you can adopt, many of which are reviewed in this paper (conflict of interest declaration: I am one of the authors).

If the objective is not smooth, then all the analysis of SGD I know of assumes bounded subgradients possibly in addition to other regularity properties (see this paper and this more recent one, although the latter does not analyze the vanilla SGD per-se). Note that if you enforce some sort of iterate normalization mechanism, feedforward ReLU networks do have bounded subgradients.