To keep it simple, this figure shows the basic idea.

https://i.imgur.com/a2I4EGY.png

# Introduction
This research examines the way that the brain's motor system carries out movement tasks by looking at the trajectory of human subjects' arms during (mostly) reaching and pistol-aiming movements. The authors' observation was that even though subjects were able to reliably to carry out these movements, the way in which they did so (i.e the trajectory of their arm) varied considerably between trials.

Previous models for motor coordination suggest that the brain strictly separates motor planning and motor execution. That is to say, the brain decides in advance, how to move its limbs in order to carry out a task and then follows that sequence to complete a movement. However this model doesn't make sense given that the motor system is still able to complete movements even in the presence of unforeseen perturbations.

Instead, the authors propose a theory for motor coordination based on stochastic optimal feedback control. They suggest that motor coordination is implemented as a feedback control loop where both the motor signals and the sensory feedback are subject to noise and transmission delay. To complete a movement, the motor system comes up with an optimal feedback control law which iteratively calculates the motor outputs throughout a given task based on the instantaneous state of the system. The system defines this 'optimal control law' as being that which maximises task performance while minimising the total effort expended in carrying out the movement.

# Method
The authors ran simulations for simple movement tasks. They used optimal control laws to drive the simulations and then compared the results with measurements taken from human subjects doing the same movement tasks. It was found that the simulations showed the same variability in their joint trajectories along task-irrelevant dimensions as the human subjects in the practical experiments. 

# Results
This research concluded that the control algorithm implemented by the motor system can be explained by the principle of minimal intervention defined in the optimal control framework. The principle of minimal intervention dictates that control effort should only expended on state dimensions that are relevant for completing the task at hand. This minimises the total control effort and avoids the possibility of degrading task performance by attempting to correct irrelevant errors with noisy control signals.

The idea of the paper is to use reinforcement learning methods to learn a step size adaption rule to be used with evolutionary strategies.

The authors use SARSA \cite{Rummery:1994} to learn a step size adaption. Their goal is to learn an adaption rule similar to the $1/5$ success rule \cite{schwefel1995evolution-and-o}, which updates the step size every $n$ mutations. It checks the number of successes over the preceding $10n$ mutations. If the number is less than $2n$ the step lengths are multiplied by a factor $0.85$ otherwise they are divided by $0.85$.
SARSA learns a policy which decides (after every $n$ mutations) to either divide the step size; multiply the step size or keep the step size constant (using the same adaption factor of $0.85$)

They evaluate their approach on the Rosenbrock function in several dimensions as well on optimization of the sphere. The optimization is terminated as soon as the optimized function value is smaller than a threshold $f < 10 ^{-10}$. If this criterion is not met within $N$ generations, the run is counted as not converged.

The authors consider four reward funcions to learn the desired policy:
$$\begin{array}{ll}
R_1(s_t)=\left\{
\begin{array}{ll}
+1&\mathrm{SR}\;\mathrm{increased}\\
\;\;\;0&\mathrm{SR}\;\mathrm{unchanged}\\
-1&\mathrm{SR}\;\mathrm{decreased}
\end{array}\right\. &
R_2(s_t)=f_{s_t} - f_{s_{t-1}}\\
R_3(s_t)=\mathrm{sgn}(f_{s_t} - f_{s_{t-1}})&
R_4(s_t)=||x_{s_t}-x_{s_{t-1}}||\cdot\mathrm{sgn}(f_{s_t} - f_{s_{t-1}})
\end{array}$$
where SR is the convergence rate,  $R(s_t)$ is the reward at step $t$, $s_t$ the current state, $s_{t-1}$ the state at which the previous reward was computed and $x_{s_t}$ the point at which $f$ is evaluated at time step $t$. Additionally they constrain the step size to lie in the interval $\left[10^{-15}, 10^{15}\right\]$, giving a reward of $-1$ if the step size is out of bounds.

With their experiments they demonstrated that they could learn a policy that is very close to the $1/5$ rule.
The combined RL-ES approach converged slower (e.g. $R_1$ $3$ to $7$ times slower on the Sphere function and $R_2\approx 3$times slower) than the pure ES approach and the following table shows that different rewards lead to different convergence rates.

Problem | $N$ | $R_1$ conv. rate |$R_2$ conv. rate |$R_3$ conv. rate |$R_4$ conv. rate
---------:|:------:|------------------------:|----------------------:|-----------------------:|-----------------------:
Sph 1D| $10^4$| $0.72$|$1.00$|$0.96$|$1.00$
Sph 5D| $10^4$| $0.64$|$0.98$|$0.94$|$0.99$
Sph 20D| $10^4$| $0.50$|$0.92$|$0.90$|$0.94$
Sph 80D| $10^5$| $0.57$|$1.00$|$0.99$|$1.00$
Ros 2D| $10^6$| $0.63$|$0.99$|$0.80$|$1.00$
Ros 5D| $10^7$| $0.77$|$1.00$|$0.77$|$1.00$

where $N$ is the number of generations within which the optimized function value has to be lower than $10^{-10}$.

The authors demonstrated in a small setting that they were able to learn a well tested adaptation rule. They demonstrated neatly that the choice of the reward function is crucial in learning and that similar rewards can lead to very different results. 

The authors present an iterative approach for optimizing policies with guaranteed monotonic improvement.
TRPO is similar to natural policy gradient methods and can be applied effectively in optimization of large nonlinear policies.

\cite{KakadeL02} gave monotonic improvement guarantees for mixture of policies $\pi_{new}(a|s)=(1-\alpha)\pi_{old}(a|s) + \alpha\pi'(a|s)$ where $\pi'=\mathrm{arg}\max_{\pi'}L_{\pi_{old}}(\pi')$ is the approximated expected return of a policy $\pi'$ in terms of the advantage over $\pi_{old}$, as $\eta(\pi_{new})\geq L_{\pi_{old}}(\pi_{new}) - \frac{2\epsilon\gamma}{(1-\gamma)^2}\alpha^2$ with $\eta$ the true expected return and $\epsilon$ the maximally expected advantage.

The authors extend this approach to be applicable for all stochastic policy classes by replacing $\alpha$ with a distance measure between two policies $\pi_{new}$ and $\pi_{old}$.
As distance measure they use the maximal Kullback–Leibler divergence $D_{KL}^{\max}(\pi_{new},\pi_{old})$ and show that $\eta(\pi_{new})\geq L_{\pi_{old}}(\pi_{new}) -CD_{KL}^{\max}(\pi_{new},\pi_{old})$, with $C= \frac{4\epsilon\gamma}{(1-\gamma)^2}$.

From this follows, that one is guaranteed to improve the true objective $\eta$ when performing the following maximaization $\mathrm{maximize}_\pi\left[L_{\pi_{old}}(\pi)-CD_{KL}^{\max}(\pi,\pi_{old})\right]$. In practice however $C$ would only allow for small steps. Thus constraining $\mathrm{maximize}_\pi L_{\pi_{old}}(\pi)$ subject to $D_{KL}^{\max}(\pi,\pi_{old}) \leq \delta$ allows for larger steps in a **Trust Region**

Due to the large number of constraints this problem is impractical to solve, which is why the authors replace the maximum KL divergence with approximated average KL.

TRPO then works as follows:
 1. Use a rollout procedure to collet a set of state-action-pairs wit Monte Carlo estimates of their $Q$-Values
 2. Average over the samples to construct the estimate objective $L_{\pi}$ as well as the constraint
 3. Approximately solve the constrained optimization problem to update the policy parameters.
 They use the conjugate gradient algorithm followed by a linesearch.

Their experiments support the claim that TRPO is able to effectively optimize large nonlinear policies.

# Main Results (tl;dr)
## Deep *Linear* Networks
1. Loss function is **non-convex** and non-concave
2. **Every local minimum is a global minimum**
3. Shallow neural networks *don't* have bad saddle points
4. Deep neural networks *do* have bad saddle points

## Deep *ReLU* Networks
* Same results as above by reduction to deep linear networks under strong simplifying assumptions
* Strong assumptions:
  * The probability that a path through the ReLU network is active is the same, agnostic to which path it is.
  * The activations of the network are independent of the input data and the weights.

## Highlighted Takeaways
* Depth *doesn't* create non-global minima, but depth *does* create bad saddle points.
* This paper moves deep linear networks closer to a good model for deep ReLU networks by discarding 5 of the 7 of the previously used assumptions. This gives more "support" for the conjecture that deep ReLU networks don't have bad local minima.
* Deep linear networks don't have bad local minima, so if deep ReLU networks do have bad local minima, it's purely because of the introduction of nonlinear activations. This highlights the importance of the activation function used.
* Shallow linear networks don't have bad saddles point while deep linear networks do, indicating that the saddle point problem is introduced with depth beyond the first hidden layer.

Bad saddle point
: saddle point whose Hessian has no negative eigenvalues (no direction to descend)

Shallow neural network
: single hidden layer

Deep neural network
: more than one hidden layer

Bad local minima
: local minima that aren't global minima

# Position in Research Landscape
* Conjecture from 1989: For deep linear networks, every local minimum is a global minimum: [Neural networks and principal component analysis: Learning from examples without local minima (Neural networks 1989)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.408.1839&rep=rep1&type=pdf)
  * This paper proves that conjecture.
* Given 7 strong assumptions, the losses of local minima are concentrated in an exponentially (with dimension) tight band: [The Loss Surfaces of Multilayer Networks (AISTATS 2015)](https://arxiv.org/abs/1412.0233)
* Discarding some of the above assumptions is an open problem: [Open Problem: The landscape of the loss surfaces of multilayer networks (COLT 2015)](http://proceedings.mlr.press/v40/Choromanska15.pdf)
  * This paper discards 5 of those assumptions and proves the result for a strictly more general deep nonlinear model class.

# More Details

## Deep *Linear* Networks
* Main result is Result 2, which proves the conjecture from 1989: every local minimum is a global minimum.
* Not where the strong assumptions come in
* Assumptions (realistic and practically easy to satisfy):
  * $XX^T$ and $XY^T$ are full rank
  * $d_y \leq d_x$ (output is lower dimension than input)
  * $\Sigma = YX^T(XX^T )^{−1}XY^T$ has $d_y$ distinct eigenvalues 
  * specific to the squared error loss function
* Essentially gives a comprehensive understanding of the loss surface of deep linear networks

## Deep ReLU Networks
* Specific to ReLU activation. Makes strong use of its properties
* Choromanska et al. (2015) relate the loss function to the Hamiltonian of the spherical spin-glass model, using 3 reshaping assumptions. This allows them to apply existing random matrix theory results. This paper drops those reshaping assumptions by performing completely different analysis.
* Because Choromanska et al. (2015) used random matrix theory, they analyzed a random Hessian, which means they need to make 2 distributional assumptions. This paper also drops those 2 assumptions and analyzes a deterministic Hessian.
* Remaining Unrealistic Assumptions:
  * The probability that a path through the ReLU network is active is the same, agnostic to which path it is.
  * The activations of the network are independent of the input data and the weights.

# Related Resources
* [NIPS Oral Presentation](https://channel9.msdn.com/Events/Neural-Information-Processing-Systems-Conference/Neural-Information-Processing-Systems-Conference-NIPS-2016/Deep-Learning-without-Poor-Local-Minima)