<p>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 <a href="https://arxiv.org/abs/2002.03329" rel="nofollow noreferrer">Khaled and Richtárik (2020)</a> (conflict of interest: I'm a coauthor of this paper). </p>

<p>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 <a href="https://arxiv.org/abs/1803.06523" rel="nofollow noreferrer">Davis and Drusvyatskiy (2019)</a> and <a href="https://arxiv.org/abs/2002.04130" rel="nofollow noreferrer">Zhang et al. (2020)</a>, 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. </p>

<p>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 <a href="https://arxiv.org/abs/2003.02395" rel="nofollow noreferrer">Défossez et al. (2020)</a> 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.</p>

CC BY-SA 4.0
2020-02-19T18:05:31.423Z
2020-03-13T12:42:32.877Z
2020-03-13T12:42:32.877Z
rka
<p>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 <a href="https://arxiv.org/pdf/1412.0233.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1412.0233.pdf</a> . 
I quote from the abstract : "We study the connection between <strong>the highly
non-convex loss function</strong> of a simple model of the <strong>fully-connected feed-forward neural network</strong>  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 <strong>simulated annealing and SGD converge to the band of low critical points</strong>, and that <strong>all critical points found there are local minima of  high  quality</strong> " </p>

CC BY-SA 4.0
2019-01-21T21:05:27.730Z
2019-01-21T21:05:27.730Z
Popescu Claudiu
<ul>
<li><p>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? </p></li>
<li><p>Are there any necessary conditions that we know of that the objective, algorithm and the oracle have to satisfy to get convergence? </p></li>
</ul>

<p>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?) </p>

<hr>

<p>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. </p>

<machine-learning><lg.learning><pac-learning><stochastic-process>
About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives
gradstudent
# About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

(Asked by: username_0 on 2018-11-25)

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

**Tags:** machine-learning, lg.learning, pac-learning, stochastic-process


---

## 2 answers

### Answer by username_1 on 2020-02-19. Score: 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)](https://arxiv.org/abs/2002.03329) (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)](https://arxiv.org/abs/1803.06523) and [Zhang et al. (2020)](https://arxiv.org/abs/2002.04130), 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)](https://arxiv.org/abs/2003.02395) 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 by username_2 on 2019-01-21. Score: 0

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** "


---

