Non-convex pitfalls and restarts

When there is more than one valley

Most interesting models are not convex. Their objectives have several local minima, saddle points and flat plateaus, and gradient descent simply rolls into whichever valley it starts in. Take $f(x)=x^4-3x^2+x$. Its derivative $4x^3-6x+1$ vanishes at $x=-1.301$, $x=0.170$ and $x=1.131$. The first and last are minima with $f=-3.514$ and $f=-1.070$, and the middle one is a hump between them. Descent with a small step from $x_0=2$ ends at $1.131$, which is only a local minimum, and from $x_0=-2$ it ends at $-1.301$, the global one. Two starts as close as $x_0=0.1$ and $x_0=0.2$, on either side of the hump at $0.170$, end in different valleys.

Saddle points are the other trap. There the gradient is zero but the Hessian has eigenvalues of both signs, so the function falls in some directions and rises in others. In high dimensions most stationary points are saddles, and plain gradient descent slows to a crawl near them. Momentum, noise from mini-batches and second-order information all help it escape. Plateaus, where the gradient is tiny over a wide region, look like convergence but are not.

The standard remedy is to restart. Run the optimiser from $K$ different starting points and keep the result with the lowest objective value. If each start independently lands in the global valley with probability $p$, then at least one of $K$ starts does so with probability $1-(1-p)^K$. For $p=0.2$ and $K=10$ this is $0.893$, and reaching $99\%$ takes $K\ge\ln0.01/\ln0.8=20.6$, so 21 starts. Better starting points help too: a solution from a convex relaxation, yesterday's calibration, or a grid search over the few parameters that matter most.

• Local minima: descent ends in the valley where it starts, so the start decides the answer.
• Saddles and plateaus: zero or tiny gradient without a minimum; momentum and noise help.
• Restarts: $K$ starts succeed with probability $1-(1-p)^K$; keep the best objective value.

Lab · what's graded

• The global minimum value15 pts
• Starting at x = 215 pts
• Two close starts15 pts
• Success of random restarts15 pts
• How many restarts15 pts
• Near a saddle point10 pts
• Comparing restart results15 pts