https://people.csail.mit.edu/hmobahi/pubs/aaai_2015.pdf

University of Michigan - Ann Arbor

The underlying premise:
- In high dimensional feature spaces, there is a very large likelihood of encountering multiple local minima. 
- This is compounded with the fact that the feature space isn’t well behaved i.e. an inevitable presence of plateaus, saddle points affecting the magnitude of the gradient along with the direction of the gradient not pointing towards the approximate region of lower cost.

Thus, being able to initialize parameters in a region smaller than the feature space itself and one that behaves well enough for the descent to lead to a reasonable solution is powerful. This is exactly what continuation methods try to achieve.

Continuation Methods

The goal to minimize the cost function $J(\Theta)$ is achieved with the following adaptation. A set of cost functions {$J^{(0)},...,J^{(n)}$} with increasing difficulty are constructed such that $J^{(0)}$ is the easiest to optimize and $J^{(n)}=J(\Theta)$ has the highest level of difficulty.

What does “easier to optimize” mean?
- It means that it is relatively more well-behaved i.e. smoother over the same region.

This gets us a good initial start point for $J^{(i+1)}$. Continuing this would result in getting us very close to solving the $J(\Theta)$ optimization problem.

How do we get cost functions to behave well in the same region?
- By “blurring” out the cost function $J(\Theta)$ i.e. by approximating $J^{(i)}(\Theta)=\mathop{\mathbb{E}}_{\Theta^{’}\sim\mathcal{N}(\Theta_{‘};\Theta,\sigma^{(i)2})}J(\Theta^{‘})$ via sampling. The intended effect is that the non-convex problem starts to look like a convex one. 

It is important to note that this method generally does not get us the global minima but does get us a superior local minima.


Goal of Continuation Methods

So is this the solution to optimizing all non-convex problems?
- Not really. In theory, the effect that a complex non-convex feature space has on the application of the continuation method would result in a very large number of objective functions which, as a result, would make the problem computationally intractable. (NP-hard optimization problems remain NP-hard even in this case).
- Another factor to consider is that non-convex problems might remain non-convex whatever the extent of blurring in some cases. E.g. $J(\Theta)=-\Theta^{T}\Theta$.
- The pitfall of blurring from the intuitive standpoint works here as well i.e. blurring out space could lead to a false convex and in turn force the solution path to inferior local minima.

The initial problem with large feature spaces was believed to be that of the local minima and issues like saddle points, etc that surround them. But, high-dimensional spaces behave very differently. The bigger problem that surrounds them is that of sparsity. 

Continuation methods as a solution to all non-convex problems?

So, can continuation methods still be of use?
Yes. they do really well at:
-  reducing estimation variance (The intuitive effect of blurring applies here too) in the gradients, 
- almost eliminate flat regions and 
- improve the conditioning of the Hessian matrix thereby reducing instability.

The real utility of continuation methods

Curriculum learning is an approach in machine learning where tasks are sequentially structured so that their complexity gradually increases. This allows models to master simpler tasks first, which prepares them for more complex challenges as their skills develop. It is utilized as a method to mitigate the impact of sparse rewards in reinforcement learning by providing an organized path of learning.

Learn Before

Related