Open: does SGD find global minima of deep networks?
ProofResearch⏱ ResearchDL TheorySGDopen problemsgdnon-convexglobal minimum
Problem
Give conditions on a network architecture, a data distribution and a step-size schedule — conditions that a network actually used in practice satisfies — under which stochastic gradient descent provably converges to a global minimiser of the training loss. Or exhibit a practically relevant setting in which it provably does not.
This is an open problem. It is stated here so you can see where the guarantees stop.
This is an open problem. Nobody has a solution, and none is hidden below — what is recorded is the state of the argument. Progress on it would be publishable.
What is known
This problem is open. What follows is an account of what has been proved, what has only been measured, and where the argument stops — not a solution, because there is not one.
Related problems
All problems| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| Implicit bias of gradient descent on underdetermined least squares | DL Theory | Proof | 30 min | ||
| Non-convex gradient descent reaches an approximate stationary point | Optimization | Proof | 30 min | ||
| SGD on convex Lipschitz objectives | SGD | Proof | 30 min | ||
| What fitting random labels rules out | DL Theory | Proof | 30 min | ||
| Fit a scaling law and derive the compute-optimal allocation run | DL Theory | Coding | 3 hours |