Nonconvex Optimization, Landscape Analysis, and Saddle Escape¶
Job: develop the nonconvex landscape (critical / strict saddle / spurious), the neural network loss / NTK, the saddle escape (perturbed GD / SGD), and the homotopy / annealing — with the strict saddle escape as the worked example.
Core¶
The nonconvex landscape¶
| Landscape / critical / strict saddle | Description |
|---|---|
| Landscape | the critical points (the \(\nabla f=0\)), the saddles, the local min, the spurious |
| Strict saddle | the Hessian \(\nabla^2 f\) the negative direction (\(\lambda_{\min}<0\)), the GD the escape (Lee et al.) |
| Spurious minima | the nonconvex the local (not the global), the spurious (the ML) |
The geometric / loss landscape of neural networks¶
| Neural network / NTK / mode connectivity | Description |
|---|---|
| Neural network landscape | the nonconvex, the spurious minima, the mode connectivity (the ML mathematics) |
| NTK / lazy training | the kernel regime, the convex (the Jacot–Gabriel–Hongler) |
| Mode connectivity | the minima the connected (the Garipanet et al.) |
The saddle escape and the perturbed GD¶
| Saddle escape / perturbed GD / SGD | Description |
|---|---|
| Perturbed GD | \(x_{k+1}=x_k-\eta\nabla f+\xi_k\) (the noise \(\xi_k\), the Jin–Netrapalli–Jordan the polynomial escape) |
| SGD | \(x_{k+1}=x_k-\eta g_k\) (the \(g_k\) the stochastic gradient, the stochastic processes) |
| Acceleration | the Nesterov the acceleration (the nonconvex the rate) |
The homotopy / continuation and the global¶
| Homotopy / annealing / Metropolis | Description |
|---|---|
| Homotopy / continuation | \(\min f_t\) the \(t\) from \(0\) to \(1\) (the continuation, the global) |
| Simulated annealing | the \(T\) the temperature, the Metropolis (the statistical mechanics / Gibbs) |
| Global | the homotopy / the annealing the global (the nonconvex the escape) |
See it¶
Strict saddle escape and the perturbed GD. The strict saddle: the Hessian \(\nabla^2 f\) has a negative direction (\(\lambda_{\min}<0\)), the GD \(x_{k+1}=x_k-\eta\nabla f\) the escape (the Lee et al.: the GD the strict saddle the escape, the a.e. the initial). The perturbed GD: \(x_{k+1}=x_k-\eta\nabla f+\xi_k\) (the noise \(\xi_k\), the Jin–Netrapalli–Jordan the escape the polynomial time). The key point: the strict saddle the GD the escape, the perturbed the polynomial — the nonconvex the saddle the escape the GD.
Check¶
Show that the GD escapes the strict saddle a.e., and the perturbed GD in polynomial time.
The strict saddle: \(\nabla^2 f\) the \(\lambda_{\min}<0\) (the negative direction), the GD \(x_{k+1}=x_k-\eta\nabla f\). The Lee et al.: the GD the stable set the measure zero (the GD the escape the a.e.). The perturbed: \(x_{k+1}=x_k-\eta\nabla f+\xi_k\) (the \(\xi_k\) the noise), the Jin–Netrapalli–Jordan: the polynomial time the escape (the \(\varepsilon\) the noise, the \(O(\mathrm{poly}(n,1/\varepsilon))\) the escape). So the strict saddle the GD the escape, the perturbed the polynomial.
Explain the NTK / lazy training and the convex regime for the neural network.
The NTK: the neural tangent kernel \(K(x,x')=\langle\nabla_\theta f(x;\theta),\nabla_\theta f(x';\theta)\rangle\) (the Jacot–Gabriel–Hongler, the kernel regime). The lazy training: the \(\theta\) the small change (the \(\theta_t\approx\theta_0\), the \(f(x;\theta_t)\approx f(x;\theta_0)+\langle\nabla f, \theta_t-\theta_0\rangle\) the linear), the convex (the kernel the convex, the ML mathematics). The mode connectivity: the minima the connected (the Garipanet et al., the low-loss the path). So the NTK the lazy the convex, the mode connectivity the landscape.
Pitfalls¶
- The strict saddle the GD escape (the a.e., the perturbed the polynomial) — the strict the escape, the non-strict the open.
- The NTK the lazy (the kernel the convex, the \(\theta\) the small) — the lazy the convex, the non-lazy the nonconvex.
- The spurious minima (the nonconvex the local not the global) — the spurious the nonconvex, the global the homotopy / annealing.
- The simulated annealing (the Metropolis the \(T\), the statistical mechanics) — the annealing the global, the \(T\) the temperature.
Refs¶
- Lee–Jordan–Simchowitz, "Gradient descent only converges to stable critical points" (2016); Jin–Netrapalli–Jordan, "Accelerated gradient descent escapes saddle points faster" (2017)
- Jacot–Gabriel–Hongler, "Neural tangent kernel" (2018); the lazy training
- Garipanet et al., "Mode connectivity" (2018); the loss landscape
Next¶
Opt index · Foundations · Conic & SDP · Variational & Monotone · Online & Stochastic · ML mathematics