<commit_before>---
layout: post
title: Do landscape analyses suffice for understanding optimization in deep learning?
date: 2018-3-2 13:00:00
author: <NAME>
visible: True
---

Neural network optimization is fundamentally non-convex, and yet simple gradient-based algorithms seem to consistently solve such problems.
This phenomenon is one of the central pillars of deep learning, and forms a mystery many of us theorists are trying to unravel.


## Landscape Approach

By far the most popular approach for theoretical analysis of optimization in deep learning is based on *landscapes*.
In a nutshell, the idea is to characterize the geometry of the training objective independently of the optimization algorithm, and then show, using very general properties of the algorithm (for example that it locally descends or that it is stochastic), that convergence (hopefully to global minimum) takes place.
One geometric condition established in various settings (see for example [TODO: ADD REFS]) is referred to as *"no poor local minima"*, and means that all local minima are close in their objective values to a global minimum.

[TODO: ADD ILLUSTRATION]

The "no poor local minima" property does not guarantee convergence to global minimum of gradient-based algorithms, as these may get stuck around *saddle points*, i.e. points where the gradient of the objective function vanishes but are not a local minimum.
To disqualify this scenario, another geometric property was defined: "strict saddle".
Formally, this property means that every saddle point has at least one negative eigenvalue to its Hessian.
Informally, it means that at every saddle point, there exists at least one direction of movement that would lead local descent algorithms to quickly slide down from the saddle.

[TODO: ADD ILLUSTRATION]

Several works (e.g. [TODO: ADD REFS]) have established, in different technical settings, that for an objective landscape admitting both "no poor local minima" and "strict saddle" properties, a gradient-based algorithm will converge to global minimum.
These results have been successfully applied to non-convex problems such as tensor decomposition ([TODO: ADD REF]), matrix completion ([TODO: ADD REF]), matrix factorization ([TODO: ADD REF]), matrix sensing ([TODO: ADD REF]), phase retrieval ([TODO: ADD REF]), dictionary learning  ([TODO: ADD REF]) and two layer neural networks with quadratic activation ([TODO: ADD REF]).


## Limitations

The aforementioned problems in which the landscape approach has successfully proven convergence to global minimum for a gradient-based algorithm, can all be viewed as incarnations of *shallow* (two layer) models.
The absence of *deep* (three or more layer) networks in the portfolio of success stories is not coincidental --- unfortunately, even the simplest of such models violate the "strict saddle" property (see [Kawaguchi 2016](https://papers.nips.cc/paper/6112-deep-learning-without-poor-local-minima.pdf) for formal examples).
Consider for example the loss for a fully-connected neural network, at the point where all weights are set to zero (ignore biases for simplicity).
There, if the depth (number of layers) is two or more, the gradient will vanish, and if it is three or more, the Hessian will vanish as well.
Accordingly, unless this point is a local minimum, which will not be the case in any reasonable setting, we obtain a saddle without any negative eigenvalue to its Hessian.

One may argue that violation of the "strict saddle" property by deep models does not necessarily point to a limitation of the general landscape approach, but rather implies that we should come up with alternative geometric conditions that ensure tractable optimization while being met by deep networks.
In a [paper](http://proceedings.mlr.press/v80/arora18a.html) published last ICML (presented in a [previous blog post](http://www.offconvex.org/2018/03/02/acceleration-overparameterization/), <NAME>, <NAME> and I argued that, sometimes, adding (redundant) linear layers to a classic linear model can accelerate gradient-based optimization, without any gain in expressiveness, and despite introducing non-convexity to a formerly convex problem.
Any landscape analysis that relies on properties of critical points (points where the gradient of the objective function vanishes) will have difficulty explaining this phenomenon, as through such lens, nothing is easier to optimize than a convex objective with a single critical point which is the global minimum.

Finally, perhaps the most potent evidence pointing to limitations of the landscape approach in the context of deep learning is the fact that, in many settings, proper initialization seems to play a crucial role in the success of neural network optimization.
This was shown by systematic empirical studies (e.g. [Sutskever et al. 2013](http://proceedings.mlr.press/v28/sutskever13.html)), and lately also by theory (as discussed below).
In its current spirit, the landscape approach typically decouples analysis of objective geometry from particularities of the optimization procedure, including the way it is initialized.
Capturing phenomena by which some initialization schemes result in successful optimization while others fail is somewhat contradictory to such decoupling.


## A Way Out?

The determining role of initialization in gradient-based optimization of deep networks suggests that perhaps a more relevant question than "is the landscape graceful?" is "what is the behavior of specific optimizer *trajectories* emanating from specific initializations?".<commit_msg>Sanjeev comments on optimization-beyond-landscape<commit_after>---
layout: post
title: Do landscape analyses suffice for understanding optimization in deep learning?
date: 2018-3-2 13:00:00
author: <NAME>
visible: True
---

Neural network optimization is fundamentally non-convex, and yet simple gradient-based algorithms seem to consistently solve such problems.
This phenomenon is one of the central pillars of deep learning, and forms a mystery many of us theorists are trying to unravel.

------- START OF CONTENT TO EXCLUDE -------

## Landscape Approach

By far the most popular approach for theoretical analysis of optimization in deep learning is based on *landscapes*.
In a nutshell, the idea is to characterize the geometry of the training objective independently of the optimization algorithm, and then show, using very general properties of the algorithm (for example that it locally descends or that it is stochastic), that convergence (hopefully to global minimum) takes place.
One geometric condition established in various settings (see for example [TODO: ADD REFS]) is referred to as *"no poor local minima"*, and means that all local minima are close in their objective values to a global minimum.

[TODO: ADD ILLUSTRATION]

The "no poor local minima" property does not guarantee convergence to global minimum of gradient-based algorithms, as these may get stuck around *saddle points*, i.e. points where the gradient of the objective function vanishes but are not a local minimum.
To disqualify this scenario, another geometric property was defined: "strict saddle".
Formally, this property means that every saddle point has at least one negative eigenvalue to its Hessian.
Informally, it means that at every saddle point, there exists at least one direction of movement that would lead local descent algorithms to quickly slide down from the saddle.

[TODO: ADD ILLUSTRATION]

Several works (e.g. [TODO: ADD REFS]) have established, in different technical settings, that for an objective landscape admitting both "no poor local minima" and "strict saddle" properties, a gradient-based algorithm will converge to global minimum.
These results have been successfully applied to non-convex problems such as tensor decomposition ([TODO: ADD REF]), matrix completion ([TODO: ADD REF]), matrix factorization ([TODO: ADD REF]), matrix sensing ([TODO: ADD REF]), phase retrieval ([TODO: ADD REF]), dictionary learning  ([TODO: ADD REF]) and two layer neural networks with quadratic activation ([TODO: ADD REF]).


## Limitations

The aforementioned problems in which the landscape approach has successfully proven convergence to global minimum for a gradient-based algorithm, can all be viewed as incarnations of *shallow* (two layer) models.
The absence of *deep* (three or more layer) networks in the portfolio of success stories is not coincidental --- unfortunately, even the simplest of such models violate the "strict saddle" property (see [Kawaguchi 2016](https://papers.nips.cc/paper/6112-deep-learning-without-poor-local-minima.pdf) for formal examples).
Consider for example the loss for a fully-connected neural network, at the point where all weights are set to zero (ignore biases for simplicity).
There, if the depth (number of layers) is two or more, the gradient will vanish, and if it is three or more, the Hessian will vanish as well.
Accordingly, unless this point is a local minimum, which will not be the case in any reasonable setting, we obtain a saddle without any negative eigenvalue to its Hessian.

One may argue that violation of the "strict saddle" property by deep models does not necessarily point to a limitation of the general landscape approach, but rather implies that we should come up with alternative geometric conditions that ensure tractable optimization while being met by deep networks.
In a [paper](http://proceedings.mlr.press/v80/arora18a.html) published last ICML (presented in a [previous blog post](http://www.offconvex.org/2018/03/02/acceleration-overparameterization/), <NAME>, <NAME> and I argued that, sometimes, adding (redundant) linear layers to a classic linear model can accelerate gradient-based optimization, without any gain in expressiveness, and despite introducing non-convexity to a formerly convex problem.
Any landscape analysis that relies on properties of critical points (points where the gradient of the objective function vanishes) will have difficulty explaining this phenomenon, as through such lens, nothing is easier to optimize than a convex objective with a single critical point which is the global minimum.

Finally, perhaps the most potent evidence pointing to limitations of the landscape approach in the context of deep learning is the fact that, in many settings, proper initialization seems to play a crucial role in the success of neural network optimization.
This was shown by systematic empirical studies (e.g. [Sutskever et al. 2013](http://proceedings.mlr.press/v28/sutskever13.html)), and lately also by theory (as discussed below).
In its current spirit, the landscape approach typically decouples analysis of objective geometry from particularities of the optimization procedure, including the way it is initialized.
Capturing phenomena by which some initialization schemes result in successful optimization while others fail is somewhat contradictory to such decoupling.

------- END OF CONTENT TO EXCLUDE -------

## Landscape approach and its limitations
An implicit assumption in many recent papers is that rigorous understanding of deep learning will follow from estabilishing properties of the loss landscape, specifically of critical points (i.e., points where the gradient vanishes). For example, using intuition from Ising models,  a conjecture was made that all local minima are also approximate global optima. This was established in settings such as matrix completion and matrix sensing (cite) that can be viewed as simple shallow nets.  It has also been shown that gradient descent with added noise in each step can evade saddle points (see Rong and Chi's posts..) and arrive at approximate local minima, which under the conjecture would be approximate global optima. 

However, the landscape approach runs into the issue that the landscape of even depth 3 nets undoubtedly have many saddle points, as well as local minima that are far from globally optimal (cite). 

But this landscape-based viewpoint has clear limitations. Proper initialization clearly plays a role, as does properties of the trajectory in the landscape taken by the optimization. Simple changes to the trajectory --e.g. batch normalization---can greatly affect outcomes. 

My [previous blog post](http://www.offconvex.org/2018/03/02/acceleration-overparameterization/), based upon an ICML'18 paper with <NAME> and <NAME>, showed that adding (redundant) linear layers to a classic linear model can accelerate gradient-based optimization, without any gain in expressiveness, and despite introducing non-convexity to a formerly convex problem. Any landscape analysis that relies on properties of critical points alone will have difficulty explaining this phenomenon, as through such lens, nothing is easier to optimize than a convex objective with a single critical point which is the global minimum.


## A Way Out?

The determining role of initialization in gradient-based optimization of deep networks suggests that perhaps a more relevant question than "is the landscape graceful?" is "what is the behavior of specific optimizer *trajectories* emanating from specific initializations?".
{'fraction_non_alphanumeric': 0.05113981762917933, 'fraction_numerical': 0.006914893617021276, 'mean_word_length': 5.0874190564292325, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 2, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6640661', 'n_tokens_mistral': 3098, 'n_tokens_neox': 2830, 'n_words': 1861}