Reinforced stochastic gradient descent for deep neural network learning
Haiping Huang Taro Toyoizumi





physhuang@gmail.com
RIKEN Brain Science Institute, Wako-shi, Saitama
351-0198, Japan

taro.toyoizumi@brain.riken.jp
 RIKEN Brain
Science Institute, Wako-shi, Saitama 351-0198, Japan



Stochastic gradient descent (SGD) is a standard optimization method to minimize a training error with respect to network parameters in modern neural network learning. However, it typically suffers from proliferation of saddle points
in the high-dimensional parameter space.
Therefore, it is highly desirable to design an efficient algorithm to escape from these saddle points and reach a parameter region of better generalization capabilities. Here, we propose a simple extension of SGD, namely reinforced SGD, which
simply adds previous first-order gradients in a stochastic manner with a probability that increases with learning time. As verified in a simple synthetic dataset, this method
significantly accelerates learning compared with the original SGD. Surprisingly, it dramatically reduces over-fitting effects, even compared with state-of-the-art
adaptive learning algorithm—Adam. For a benchmark handwritten digits dataset, the learning performance is comparable to Adam, yet with an
extra advantage of requiring one-fold less computer memory. The reinforced SGD is also compared with SGD with fixed or adaptive momentum parameter and Nesterov's momentum, which shows that the 
proposed framework is able to reach a similar generalization accuracy with less computational costs. Overall, our method introduces stochastic memory into gradients, which plays an important role in understanding how gradient-based training algorithms can work
and its relationship with generalization abilities of deep networks.




 Reinforced stochastic gradient descent for deep neural network learning
    Taro Toyoizumi
    December 30, 2023
=======================================================================



§ INTRODUCTION


Multilayer neural networks have achieved state-of-the-art performances in image recognition <cit.>, speech recognition, and even natural
language processing <cit.>. This impressive success is based on a simple powerful stochastic gradient descent (SGD) algorithm <cit.>, and its variants. 
This algorithm estimates gradients of an error function based on mini-batches of an entire dataset. Gradient noise caused by mini-batches helps exploration of parameter space to
some extent. However, the parameter space is highly non-convex for a typical deep network training, and finding a good path for SGD to improve generalization ability of deep neural
networks is thus challenging <cit.>. 

As found in standard spin glass models of neural networks <cit.>, a non-convex error surface is accompanied by exponentially many local minima, which hides the (isolated) global
minima and thus makes any local
search algorithms easily get trapped. In addition, the error surface structure of deep networks might behave similarly to random Gaussian error surface <cit.>, which demonstrates that
critical points (defined as zero-gradient points) of high error have a large number of negative eigenvalues of the corresponding
Hessian matrix. Consistent with this theoretical study, empirical studies on deep network training <cit.> showed that
SGD is slowed down by a proliferation of saddle points with many negative curvatures and even plateaus (eigenvalues close to zero in many directions). The prevalence of
saddle points poses an obstacle to attain better generalization properties for a deep network, especially for SGD based on first-order optimization, while second-order optimization relying on
Hessian-vector products is more computationally expensive <cit.>. The second order method that relies on positive-definite curvature approximations, can not follow directions
with negative curvature, and is easily trapped by saddle points <cit.>.

In this paper, we show a heuristic strategy to overcome the plateaus problem for SGD learning. We call this strategy reinforced SGD (R-SGD), which provides
a new effective strategy to use the gradient information, i.e., to update one network parameter, an instantaneous gradient is reinforced by (accumulated) previous gradients with an 
increasing reinforcement probability that grows with learning time steps. In other words, the reinforcement may be turned off, and then only the instantaneous gradient is used for learning. 
This kind of stochastic reinforcement enhances the exploration of parameter space. The excellent performance of R-SGD is
verified first on training a toy fully-connected deep network model to learn a simple non-linear mapping generated by a two-layer feedforward network, and then on a benchmark handwritten digits dataset <cit.>, 
in comparison to both vanilla backpropagation (BackProp) <cit.> and state-of-the-art Adam algorithm <cit.>. In the benchmark dataset, we also clarify the performance difference between R-SGD and SGD with 
fixed or adaptive momentum parameter <cit.> and Nesterov's momentum <cit.>.




§ FULLY-CONNECTED DEEP NETWORKS


We consider a toy deep network model with L layers of fully-connected feedforward architecture. 
Each layer has n^k neurons (so-called width of layer k). We define the input as n^1-dimensional vector 𝐯, 
and the weight matrix 𝐖^k specifies the symmetric connections between layer k and layer k-1. The symmetry means that the same connections are used to backpropagate the error during
training.
A bias parameter can also be incorporated into the weight matrix by assuming an additional constant input. 
The output at the final layer is expressed as:

    𝐲=f_L(𝐖^Lf_L-1(𝐖^L-1⋯ f_2(𝐖^2𝐯))),

where f_k(·) is an element-wise sigmoid function for neurons at layer k, defined as f(x)=1/1+e^-x, unless otherwise specified (e.g., ReLU activation funtion).
The network is trained to 
learn the target mapping generated randomly as {𝐯^m,𝐲_*^m}_m=1^M, where the input is generated 
from a standard normal distribution with zero mean and unit variance, and the target label y_* is generated according to 
the non-linear mapping y_*=f(𝐖_g𝐯), in which each entry of the data-generating matrix 𝐖_g 
follows independently a standard normal distribution as well. The deep network is trained to learn this non-linear mapping (continuous target labels) from a set of examples. 
We generate a total of 2M examples, in which the first M examples are used for training and the last M examples are used for testing
to evaluate the generalization ability of the learned model.

In simulations, we use deep network architecture of L=4 layers to learn the target non-linear mapping, in which the network is thus specified by n^1-n^2-n^3-n^4, 
with n^1 indicating the dimension of the input data and n^L the dimension of the output. We use this simple toy setting to test
our idea first, and then the idea is further verified in the handwritten digits dataset.






§ BACKPROPAGATION AND ITS VARIANTS


We first introduce the vanilla BackProp <cit.> for training the deep network defined in Sec. <ref>. 
We use quadratic loss (error) function defined as E=1/2ϵ^ Tϵ, where ^ T denotes a vector (matrix) transpose operation, and ϵ defines 
the difference between the target and actual outputs as ϵ=𝐲_*-𝐲. To backpropagate the error, 
we also define two associated quantities: one is the state of neurons at k-th layer defined by 𝐬^k (e.g., 𝐬^L=𝐲, 𝐬^1=𝐯), and the other is the weighted-sum input 
to neurons at k-th layer defined by 𝐡^k≡𝐖^k𝐬^k-1. Accordingly, we define two related gradient vectors:


    δ^k   ≡∂ E/∂𝐬^k,
    κ^k   ≡∂ E/∂𝐡^k,


which will be used to derive the propagation equation based on the chain rule. It is straightforward to 
derive κ^L=-ϵ∘𝐲', where ∘ indicates the element-wise multiplication, and 𝐲' is the derivative
of the non-linear transfer function with respect to its argument.
By applying the chain rule, we obtain the weight update equation for the top layer as

    Δ𝐖^L=-ηκ^L(𝐬^L-1)^ T,

where η is the learning rate, and the remaining part is the gradient information, which indicates
how a small perturbation to the weight affects the change of the error computed at the top (output) layer.

To update the weight parameters at lower layers, we first derive the propagating equations for gradient vectors as follows:


    δ^k   =(𝐖^k+1)^ Tκ^k+1,
    κ^k   =δ^k∘(𝐟_k)',


where k≤ L-1.
Using the above backpropagation equation, the weight at lower layers is updated as:

    Δ𝐖^k=-ηκ^k(𝐬^k-1)^ T,

where k≤ L-1.
The neural state used to update the weight parameters comes from a forward pass from the input vector to the output vector at the top layer.
A forward pass combined with a backward propagation of the error forms the vanilla BackProp widely used in training deep networks given the labeled data <cit.>. 
To improve the training efficiency, one usually divides the entire large dataset into a set of mini-batches, each of which is used to get the average gradients across the examples within that mini-batch.
One epoch corresponds to a sweep of the full dataset. The learning time is thus measured in units of epochs. For one epoch, the weight is actually updated for M/B times (B is the size of a mini-batch).
This process is usually termed SGD. 

Here, we briefly introduce two kinds of SGD with momentum techniques. The first one is the SGD with momentum (SGDM). The learning equation is revised as


    ν_t   =ρ_tν_t-1+𝐠_t,
    Δ𝐖_t   =-ην_t,


where 𝐠_t≡∇_𝐖E(𝐖_t-1) denotes the gradient estimated from the average over examples within the current mini-batch,
and ρ_t is the momentum
parameter, which can be either prefixed (ρ_t=ρ in the classical SGDM) or varied over learning steps (t).

The second one is Nesterov's accelerated gradient (NAG) <cit.>, which first implements a partial update to 𝐖_t, and then uses the updated 𝐖_t to evaluate gradients, i.e.,


    ν_t   =ρ_tν_t-1-η𝐠'_t,
    Δ𝐖_t   =ν_t,


where 𝐠'_t≡∇_𝐖E(𝐖_t-1+ρ_tν_t-1). Note that the partial update takes an extra computational cost of T_maxM/B|𝐖|, where T_max denotes 
the maximal number of epochs, and |𝐖| denotes the total amount of network parameters.



§ REINFORCED STOCHASTIC GRADIENT DESCENT

In the above vanilla BackProp, only current gradients are used to update the weight matrix. Therefore in a non-convex optimization, the backpropation gets easily stalled by the plateaus or
saddle points on the error surface, and it is hard to escape from these regions. During training, gradients may be very noisy with large fluctuations. 
If update directions along some weight components are stochastically allowed to accumulate the history of
gradient information, while other directions still follow the current gradients, the learning performance may be boosted. This stochastic rule of turning on accumulation may help
SGD to handle the uncertainty of updating the weights. We will test this idea in the following deep neural network learning.

To enable SGD to use previous gradient information, we define a stochastic process for updating modified gradient 𝐠̃_t used at each learning step as follows:

    (𝐠̃_t)_i←
                                   (𝐠_t)_i,    with prob. 1-Γ(t),
    
                                   (𝐠_t)_i+(𝐠̃_t-1)_i,    with prob. Γ(t).

where the stochastic reinforcement is independently applied to each weight component, and 𝐠̃_t-1 contains information
about the history of the evolving gradients, and the current gradients are reinforced by the previous accumulated gradients with a reinforcement probability defined by
Γ(t). The stochastic rule in Eq. (<ref>) is a switch-like (all-or-none) event; its smooth averaged version given 𝐠̃_t-1 is 𝔼[𝐠̃_t|𝐠̃_t-1]=𝐠_t+Γ(t)𝐠̃_t-1, where
Γ(t) is equivalent to ρ_t in SGDM with time-dependent momentum parameter. 
Using adaptive momentum parameter is important in 
boosting the learning performance of SGDM. However, the switch-like property is able to reach a better or equivalent test accuracy with fewer training steps.
Comparisons will be made on the handwritten digits dataset.



Eq. (<ref>) is a very simple way to re-use the previous gradient information, and forms the key component of R-SGD.  We first choose Γ(t)=1-γ^t, where γ=γ_0e^-λ t_ ep. γ_0 and λ are prefixed constants, and 
t_ ep refers to the learning time in units of epochs. Γ(t) can be rewritten as 1-e^-t/τ_ R, where τ_ R≡-1/lnγ_0-λ t_ ep setting the time scale of the dynamics of the reinforcement probability.
γ_0 is usually fixed to a value very close to one, and λ takes a small value. 
Therefore the current gradient has an increasing probability to be reinforced by the previous gradients, and retains its instantaneous value otherwise. This reinforcement probability is not 
the unique choice, e.g., 1-a_0/(t+1)^b_0 (a_0 and b_0 are constants) is also a candidate (discussed in Sec. <ref>).
 We show a typical trace of the reinforcement probability and γ in Fig. <ref> (a), 
and will test effects of hyper-parameters (γ_0,λ) on training dynamics in Sec. <ref>. Note that by setting (γ_0,λ)=(1,0), one recovers the vanilla BackProp.
In all simulations, we use an exponentially-decaying learning rate η_t_ ep=η_t_ ep-1β^t_ ep, where
η_0=0.8 and β=0.999, with a minimal learning rate of 0.02, unless otherwise specified. R-SGD is summarized in algorithm <ref>.

The gradient used in R-SGD may be the accumulated one (over an unfixed or stochastic number
  of consecutive steps), which
  contains short or long-term memory of previous gradient information (Fig. <ref> (b)). Hence, the step-size is
  a sum of previous gradients over a memory length ℒ, which follows a probability P_t(ℒ) decaying with ℒ (Fig. <ref> (b)). This stochastic process is summarized by
  

    Δ𝐖_t^ R-SGD   =-η_t∑_l=t-ℒ^t𝐠_l,
    ℒ   ∼ P_t(ℒ)=(1-Γ(t-ℒ))exp(∑_l=t-ℒ+1^tlnΓ(l)),


where the prefactor indicates the probability that the memory is cleaned before accumulation. This probability is normalized since ∑_ℒ=0^tP_t(ℒ)=1-∏_l=0^tΓ(l)=1, where
Γ(0)=0. In the SGDM, the momentum term is deterministically added to the learning step size with coefficient ρ_t (Eq. (<ref>)). Unfolding this process, we obtain the step-size as
 
    Δ𝐖_t^ SGDM=-η_t∑_l=1^t(∏_l'=l+1:l≠ t^tρ_l'+δ_l,t)𝐠_l,

where δ_l,t is a Kronecker delta function, and each gradient is weighted by a value smaller than one. 

To show the efficiency of R-SGD, we also compare its performance with that of a state-of-the-art stochastic optimization algorithm, namely adaptive moment estimation (Adam) <cit.>.
Adam performs a running average of gradients and their second raw moments, which are used to adaptively change the learning step-size. We use heuristic 
parameters of Adam given in <cit.>, except that η_0=0.01 with the lowest value set to 0.001. Large η_0 as we use in R-SGD does not work
in our simulations for Adam.









§ RESULTS AND DISCUSSION




 §.§ Learning performance in simple synthetic dataset



We first test our idea in the simple synthetic dataset described in Sec. <ref>. We use a 4-layer deep network architecture as 100-400-200-10. Training examples are divided into
mini-batches of size B=100. In simulations, we use the parameters 
(γ_0,λ)=(0.9995,0.0001), unless otherwise specified. Although the chosen parameters are not optimal to achieve the best performance, we still observe the outstanding performance of R-SGD.
In Fig. <ref> (a), we compare the vanilla BackProp with R-SGD. We clearly see that the test performance is finally improved at 100-th
epoch by a significant amount (about 77.5%). Meanwhile, the training error is also significantly lower than that of BackProp. A salient feature of R-SGD is that,
at the intermediate stage, the reinforcement strategy guides SGD to escape from possible plateau regions of high error surrounding saddle points, and finally reach a region of
very nice generalization properties. This process is indicated by the temporary peak in both training and test errors for R-SGD. Remarkably, even before or after this peak, there are a few less
significant fluctuations in both training and test errors. These fluctuations play an important role in the exploration of the parameter space.


Compared to state-of-the-art Adam, R-SGD still improves the final test performance by a significant
amount (about 49.1%, see Fig. <ref> (b)). Note that Adam is able to decrease both training and test errors very quickly, but the decrease becomes
slow after about 40 epochs. In contrast, R-SGD keeps decreasing both errors by a more significant amount than Adam, despite the presence of slightly significant fluctuations. Another key feature of Fig. <ref> (b) is that, a region in the parameter space with low training error does not generally have low test error. The 
training error reached by R-SGD is clearly higher than that of Adam, but the network architecture learned by R-SGD has nicer generalization property. This observation is
consistent with a recent study of maximizing local entropy in deep networks <cit.>.









We then study the effects of reinforcement parameters (γ_0,λ) on the learning performance, as shown in Fig. <ref>.
If the exponential decay rate λ is large, R-SGD over-fits the data rapidly at around 17 epochs. This is because, γ
decays rapidly from γ_0, and thus a stochastic fluctuation at earlier stages of learning is strongly suppressed, which limits severely
the exploration ability of R-SGD in the high-dimensional parameter space. In this case, R-SGD is prone to get stuck by bad
regions with poor generalization performances. However, maintaining the identical small decay rate, we find that a larger value of γ_0 leads to a smaller test error (inset of Fig. <ref>). For relatively large values of
γ_0, the learning performance is not radically different. 


We also study the effects of training data size (M) on the learning performances.
Clearly, we see from Fig. <ref>, the test error decreases with the training data size as expected. R-SGD outperforms the
vanilla BackProp, and even Adam. 

For the simple toy model, SGDM with fixed momentum parameter could outperform
  Adam with a careful optimization of momentum parameter (e.g., ρ_t=0.9 ∀ t), but R-SGD still outperforms the classical SGDM (fixed momentum parameter) by about 14.3% when M=1000. By adaptively changing the momentum parameter whose value is the same as
  the reinforcement probability of R-SGD (i.e., a smooth averaged version of R-SGD),
  SGDM can reach a similar performance to that of R-SGD. Because the synthetic data in the toy model is relatively simple and the reinforcement
  probability used in the synthetic data is rapidly saturated to one (Fig. <ref> (a)), it is difficult to show the performance difference between R-SGD and SGDM with the adaptive momentum parameter. Therefore, for MNIST classification
  task in the next section, we use the reinforcement probability of Γ(t)=1-1/√(t+1), which does not rapidly approach one, and compare R-SGD with different variants of momentum-based SGD.




 §.§ Learning performance in MNIST dataset


Finally, we evaluate the test performance of R-SGD on MNIST dataset. The MNIST handwritten digits dataset contains
60000 training images and an extra 10000 images for testing. Each image is one of ten handwritten digits (0 to 9) with 28×28 pixels.
Therefore the input dimension is n^1=784. For simplicity, we choose the network structure as 784-100-200-10.

Although the reinforcement probability specified by (γ_0,λ) we used in the synthetic dataset works on the MNIST dataset (see an example in Fig. <ref> (c)), we found that the reinforcement probability Γ(t)=1-1/√(t+1) works better (shortening the training time to reach a lower generalization error) for MNIST dataset, and furthermore, this choice does not saturate
the reinforcement probability to one within the explored range of learning time (Fig. <ref>), which offers a nice candidate to demonstrate the performance difference between R-SGD and SGDM.
Fig. <ref> shows that R-SGD improves significantly over BackProp, reaching
a similar test performance to that of Adam with moderate training data size (M=10K). R-SGD achieves a test error of 0.0535±0.0021, compared with BackProp reaching
0.1047±0.0020, and Adam reaching 0.0535±0.0016 (as in Table <ref>). The test error is averaged over five independent runs (different sets of training and test examples).
Note that, as training size increases (e.g., M=15K), the test performance of R-SGD becomes slightly better than that of Adam (Table <ref>). Adaptive methods such as Adam often show faster initial progress, but their performances get quickly trapped by a test error plateau <cit.>. In contrast, as shown in the inset of Fig. <ref>, R-SGD as a non-adaptive method is able to 
reach a lower test error by taking a few more epochs (note that Adam needs more computer memory to store the uncentered variance of the gradients).
 




  
  As shown in Fig. <ref> (a), SGDM with adaptive momentum parameter reaches a higher test error than R-SGD, which confirms that the switch-like event plays an
  important role in guiding R-SGD to a good region. In R-SGD, the reinforcement along some weight components is turned off 
  with a finite probability, then along these directions, only the current gradients are used (the same as those used in BackProp). But the reinforcement may be turned on along 
  these directions once again during training. In contrast, for SGDM, the momentum term with adaptive momentum parameter is always applied to update 
  all weight components during training. This mechanism difference leads to different test performances observed in Fig. <ref> (a). The training dataset may change the error surface in practice. It seems that
  the performance of R-SGD is robust to this change (Table <ref>). NAG with adaptive momentum parameter ρ_t=Γ(t) learns quickly but gets trapped by a slightly higher test error. In addition,
  a single epoch in NAG takes an extra computational cost of M/B|𝐖| due to the partial update.
  
  For fixed-momentum-parameter SGDM (ρ_t does not change over time, unlike the reinforcement probability in R-SGD), the learning performance gets worse (Fig. <ref> (b)).
  When applied to a deep network with ReLU activation and cross-entropy as the objective function, R-SGD still shows competitive performance (Fig. <ref> (c)).
  
  


We also use bilinear interpolation method to qualitatively analyze the test error surface of the three algorithms (BackProp, R-SGD and Adam). Using the bilinear interpolation method <cit.>, one can
visualize the error surface in 3D subspace spanning four high-dimensional weight configurations. These four weight configurations defined as {𝐖_i}_i=1^4 are chosen either from
one learning trajectory or from solutions obtained starting from four different random initializations. Based on these four configurations, the error function is varied as a function of a new
constructed weight matrix specified by 𝐖=β(α𝐖_1+(1-α)𝐖_2))+(1-β)(α𝐖_3+(1-α)𝐖_4), where α∈[0,1] and β∈[0,1] are two control parameters.
Results are shown in Fig. <ref> for one trajectory interpolation. BackProp decreases the test error slowly, and finally reaches a plateau and get stuck there.
Adam decreases the error very quickly, and reaches a more apparent and lower plateau than that of BackProp. Remarkably, R-SGD first decreases the error quickly, which is followed by a plateau. The
plateau is then passed and finally R-SGD reaches a region with less apparent flatness. Interpolation results of four different solutions are shown in Fig. <ref>.
Clearly, BackProp can get stuck by different solutions of different qualities, depending on initializations. Both Adam and R-SGD can reach solutions of nearly the same
quality, despite different initializations. However, the subspace looks sharper for R-SGD than for Adam. This rough analysis by using bilinear interpolation
method implies that the high dimensional topology of weight space seen by the three algorithms might be intrinsically different. However, to characterize necessary properties of a good region with nice
generalization capabilities requires a theoretical understanding of the entire high dimensional weight space in terms of analyzing some non-local quantity. Establishing a theoretical 
relationship between learning performances of various SGD algorithms and the intrinsic structure of the error surface is still an extremely challenging task in future studies.



 
 


§ CONCLUDING REMARKS



  In this paper, we propose a new type of effective strategy to guide SGD to overcome the plateau problem typical in deep neural network learning.
  This strategy takes into account previous (accumulated) gradient information in a probabilistic way when updating current weight matrix. It introduces a stochastic reinforcement to
  current gradients, and thus enhances the exploration ability of the original SGD. This strategy is essentially different from an independently random noise added to the gradient during
  the learning process <cit.>. In fact, we add time-dependent Gaussian noise to gradients during training in our simulations using default hyper-parameters <cit.>, whose performance could
  not be comparable to that of R-SGD within 100-epochs training (or it requires longer convergence time). 
  
  A similar reinforcement strategy has been used in a single layer neural network with discrete weights <cit.>, where local fields in a belief propagation equation are
  reinforced. In our work, we study deep neural networks with continuous weights, and thus the gradients are reinforced. 
 The reinforced belief propagation is conjectured to be
  related to local entropy maximization <cit.> in discrete neural networks. Whether R-SGD reshapes the original non-convex error surface in some way, such that searching for
  a parameter region of good-quality is facilitated, remains an interesting open question. We leave this for future work. 
  
  In the current setting, the learning performance of R-SGD is comparable to (in MNIST) or even better than that of Adam (in the synthetic dataset), which requires one-fold more computer memory to store the uncentered variance of
  the gradients. The learning step-size of Adam is adaptively changed, which means that the step-size is automatically tuned to be closer to zero when
  there is greater uncertainty about the direction of the true gradient <cit.>, while R-SGD uses the stochastic reinforcement of the gradient information to
  deal with this kind of uncertainty, and shows comparable and even better performance.
  
  A recent study argued that adaptive learning methods such as Adam generalize worse than SGD or SGDM on CIFAR-10 image classification tasks <cit.>.
  It is thus very interesting to evaluate the performance of R-SGD on more complicated deep network model and complex datasets, 
  which are left for future systematic studies.
  
  R-SGD may be 
  able to avoid vanishing or exploding gradient problem typical in training a very deep network <cit.>, probably thanks to accumulation of gradients used stochastically. 
  In addition, it may take effect in recurrent neural network training <cit.>.
  In fact, previous gradient information at each step can be
  weighted before accumulation according to its importance in guiding SGD. This is a very interesting direction for future studies on fundamental properties of R-SGD.
  












We are grateful to the anonymous referee for many constructive comments.  H.H. thanks Dr. Alireza Goudarzi for a lunch discussion which later triggered the idea of this work. This work was supported by the program for Brain Mapping by Integrated Neurotechnologies
for Disease Studies (Brain/MINDS) from Japan Agency for Medical Research and development, AMED, and by RIKEN Brain Science Institute.



10

Hinton-2012imag
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton.
Imagenet classification with deep convolutional neural networks.
In P. Bartlett, F.c.n. Pereira, C.j.c. Burges, L. Bottou, and K.q.
  Weinberger, editors, Advances in Neural Information Processing Systems
  25, pages 1106–1114, 2012.

DL-2016
Ian Goodfellow, Yoshua Bengio, and Aaron Courville.
Deep Learning.
MIT Press, Cambridge, MA, 2016.

robbins-1951
Herbert Robbins and Sutton Monro.
A stochastic approximation method.
Ann. Math. Statist., 22:400–407, 1951.

Bengio-2010
Xavier Glorot and Yoshua Bengio.
Understanding the difficulty of training deep feedforward neural
  networks.
In Yee W. Teh and D. M. Titterington, editors, Proceedings of
  the Thirteenth International Conference on Artificial Intelligence and
  Statistics (AISTATS-10), volume 9, pages 249–256, 2010.

Huang-2014
Haiping Huang and Yoshiyuki Kabashima.
Origin of the computational hardness for learning with binary
  synapses.
Phys. Rev. E, 90:052813, 2014.

Baldassi-2016
Carlo Baldassi, Christian Borgs, Jennifer T. Chayes, Alessandro Ingrosso, Carlo
  Lucibello, Luca Saglietti, and Riccardo Zecchina.
Unreasonable effectiveness of learning neural networks: From
  accessible states and robust ensembles to basic algorithmic schemes.
Proceedings of the National Academy of Sciences,
  113(48):E7655–E7662, 2016.

Bray-2007
Alan J. Bray and David S. Dean.
Statistics of critical points of gaussian fields on large-dimensional
  spaces.
Phys. Rev. Lett., 98:150201, 2007.

Fyo-2007
Yan V. Fyodorov and Ian Williams.
Replica symmetry breaking condition exposed by random matrix
  calculation of landscape complexity.
Journal of Statistical Physics, 129(5):1081–1116, 2007.

Lecun-2014
A. Choromanska, M. Henaff, M. Mathieu, G. Ben Arous, and Y. LeCun.
The loss surfaces of multilayer networks.
ArXiv e-prints 1412.0233, 2014.

Dau-2014
Y. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and
  Y. Bengio.
Identifying and attacking the saddle point problem in
  high-dimensional non-convex optimization.
ArXiv e-prints 1406.2572, 2014.

Ge-2015
R. Ge, F. Huang, C. Jin, and Y. Yuan.
Escaping From Saddle Points — Online Stochastic Gradient for
  Tensor Decomposition.
ArXiv e-prints 1503.02101, 2015.

Ba-2017
Jimmy Ba, Roger Grosse, and James Martens.
Distributed Second-Order Optimization using Kronecker-Factored
  Approximations.
ICLR-2017, 2017.

Lecun-1998
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.
Gradient-based learning applied to document recognition.
Proceedings of the IEEE, 86:2278–2324, 1998.

Back-1988
Rumelhart David E., Hinton Geoffrey E., and Williams Ronald J.
Learning representations by back-propagating errors.
Nature, 323:533–536, 1986.

Adam
D. Kingma and J. Ba.
Adam: A method for stochastic optimization.
ArXiv e-prints 1412.6980, 2014.

Suts-2013
Ilya Sutskever, James Martens, George E. Dahl, and Geoffrey E. Hinton.
On the importance of initialization and momentum in deep learning.
In Proceedings of the 30th International Conference on
  International Conference on Machine Learning - Volume 28, ICML'13, pages
  1139–1147, 2013.

nag-2013
Y. Nesterov.
Introductory lectures on convex optimization: A basic course,
  volume 87.
Springer US, 2004.

Stra-2009
Hugo Larochelle, Yoshua Bengio, Jérome Louradour, and Pascal Lamblin.
Exploring strategies for training deep neural networks.
J. Mach. Learn. Res., 10:1–40, 2009.

EGD-2016
P. Chaudhari, A. Choromanska, S. Soatto, Y. LeCun, C. Baldassi,
  C. Borgs, J. Chayes, L. Sagun, and R. Zecchina.
Entropy-SGD: Biasing Gradient Descent Into Wide Valleys.
ArXiv e-prints 1611.01838, 2016.

wilson-2017
A. C. Wilson, R. Roelofs, M. Stern, N. Srebro, and B. Recht.
The Marginal Value of Adaptive Gradient Methods in Machine
  Learning.
ArXiv e-prints 1705.08292, 2017.

Im-2016
D. Jiwoong Im, M. Tao, and K. Branson.
An Empirical Analysis of Deep Network Loss Surfaces.
ArXiv e-prints 1612.04010, 2016.

Neel-2015
A. Neelakantan, L. Vilnis, Q. V. Le, I. Sutskever, L. Kaiser,
  K. Kurach, and J. Martens.
Adding gradient noise improves learning for very deep networks.
ArXiv e-prints 1511.06807, 2015.

Chau-2015
P. Chaudhari and S. Soatto.
The effect of gradient noise on the energy landscape of deep
  networks.
ArXiv e-prints 1511.06485, 2015.

Zecchina-2006
A. Braunstein and R. Zecchina.
Learning by message passing in networks of discrete synapses.
Phys. Rev. Lett, 96:030201, 2006.

Baldassi-2015
Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and
  Riccardo Zecchina.
Subdominant dense clusters allow for simple learning and high
  computational performance in neural networks with discrete synapses.
Phys. Rev. Lett., 115:128101, 2015.

Ben-2012
R. Pascanu, T. Mikolov, and Y. Bengio.
On the difficulty of training Recurrent Neural Networks.
ArXiv e-prints 1211.5063, 2012.




