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

Question

• 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.

Answer 1

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 (i.e. if the gradient is Lipschitz), then you do not need to assume bounded gradients and there are quite a few assumptions on the noise you can adopt, and they are reviewed (with convergence results) in Khaled and Richtárik (2020) (conflict of interest: I'm a coauthor of this paper).

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 Davis and Drusvyatskiy (2019) and Zhang et al. (2020), 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.

Unfortunately, even neural networks with differentiable losses are not globally smooth. For Adam and AdaGrad, it turns out that you do not need global smoothness as Défossez et al. (2020) show. There are a lot more results specifically for neural networks, but I will refrain from mentioning them since your question was about general assumptions.

Answer 2

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 "