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


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 "


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.