Exact Stochastic Newton Method for Deep Learning: the feedforward networks case.
Authors: Fares B. Mehouachi
Chaouki Kasmi
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep Learning
Second-order Optimization
Newton Method
Sifrian
Hessian
Exact Stochastic Newton
Saddle-Free Newton
Non-Convex Optimization

Abstract: The inclusion of second-order information into Deep Learning optimization has drawn consistent interest as a way forward to improve upon gradient descent methods. Estimating the second-order update is often convoluted and computationally expensive, which drastically limits its usage scope and forces the use of various truncations and approximations.
This work demonstrates that it is possible to solve the Newton direction in the stochastic case exactly. We consider feedforward networks as a base model, build a second-order Lagrangian which we call Sifrian, and provide a closed-form formula for the exact stochastic Newton direction under some monotonicity and regularization conditions. We propose a convexity correction to escape saddle points, and we reconsider the intrinsic stochasticity of the online learning process to improve upon the formulas.  We finally compare the performance of the developed solution with well-established training methods and show its viability as a training method for Deep Learning.

Under review as a conference paper at ICLR 2022
EXACT STOCHASTIC NEWTON METHOD FOR DEEP LEARNING: THE FEEDFORWARD NETWORKS CASE.
Anonymous authors Paper under double-blind review
ABSTRACT
The inclusion of second-order information into Deep Learning optimization has drawn consistent interest way forward to improve upon gradient descent meth- ods. Estimating the second-order update is computationally expensive, which drastically limits its usage scope and forces the use of various truncations and approximations. This work demonstrates that it is possible to solve the Newton direction in the stochastic case exactly. We consider feedforward networks as a base model, build a second-orde Lagrangian which we call Sifrian, and pro- vide a closed-form formula for the exact stochastic Newton direction under some monotonicity and regularization conditions. We propose convexity correction to escape saddle points, and we reconsider the intrinsic stochasticity of the online learning process to improve upon the formulas. We finally compare the perfor- mance of the developed solution with well-established training methods and show its viability training method for Deep Learning.
Optimization in Deep Learning is mainly dominated by first-order methods built around the central concept of backpropagation (LeCun et al., 1988). Second-order methods have exceptional theoreti- cal properties in deterministic optimization (Boyd et al. 2004; NNcedal & Wright 2006). but such properties do not translate well into the stochastic case (LeCun et al. [012] Bottou et al., 2018).
First-order methods such as the Stochastic Gradient Descent (SGD) (Robbins & Monro 1951) are
relatively simple and have been adaptively improved for Deep Learning (Duchi al. 2011 Tiele-
man & Hinton| 2012) Kingma & Ba 2014 Reddi et al.] 2019 Yao et al. (020). Inherently, second- order methods might seems inadequate for Deep learning due increased computational cost, poor clock-wall performance, and the non-convex nature of Deep Learning (LeCun et al. (012). Further- more, Newton method might even reduce the generalization capabilities of training (Wadia et al.]
2021 Amari et al. 2020). Despite these various limitations, substantial effort was deployed to
include Hessian information into the optimization process (e.g. [Byrd et al.) 2011:] Sihk-Din
ct al. 2014. Byrd et al. | Agarwal et al.) 2017: Berahas et al. [2019]
Anil Anil et al. 2020 Goldfarb
cet al.
2020 Castera et al. (2021). Several approaches exist such as the Gauss-Newton method (e.g
Schraudolph 2002 Botev al. 2017). diagonal approximation of the Hessian (e.g. Bordes al.
2009 Schhaul et al. 2013), iterative low-rank updates such as BFGS (Broyden 1970 Fletcher| 1970,
Goldfarb 1970; Shanno 1970) (see also,[Liu & Nocedal 1989 Schraudolph al. 2007 [aolaa gada et al. [2018), or Hessian-Free methods which combine the fast Hessian matrix multiplication
(Pearlmutter [994) and the conjugate gradient algorithm (e.g. Martens 2010 Martens & Sutskever
2012 Dauphin et al. 2014). The use of the Fisher matrix to capture curvature information in the
space of distributions, instead of the Hessian, is another approach which yields the natural gradient Amari 1998). but suffers from the same computational issues as the Newton method. Within this context K-FAC method (Martens & Grosse 2015] Ba et al. 2016a George et al., 2018) mitigates some of the computational issues of the natural gradient method. In essence, several drawbacks and
flaws limits the adoption of second-order methods as a standard for neural networks training.
In this paper, we propose novel approach to characterize the Newton update which help us derive an exact closed-form solution for the stochastic Newton method. Our method requires a suitable regularization of the neural network and strict monotonicity of the activation functions. We start this paper by introducing useful notations while deriving the well-known backpropagation algorithm for feedforward network. Then we introduce second-order Lagrangian which call Sifrian, that will serve to characterize the Newton direction. We derive four types of equations from the Sifrian, and we provide an exact closed-form solution for the Newton direction in the stochastic case. We

---

Under review as a conference paper at ICLR 2022
further propose saddle-free version of our method, and add randomization process to enhance solution. In the last part of this paper, we show the applicability of our method for Deep Learning through diverse classification tasks using feedforward architectures.
PRELIMINARIES
Deep Learning and neural networks training could be seen optimization problem of an expected loss function over a distribution 'D of labeled samples (x, d). In general, weights and biases (W,9) are the sought-after parameters of the network. The labeled samples distribution D is often unknown, but large number of samples (database (3) allows the approximation of the expected loss with an empirical risk:
min (E(xa)) 1e (W x. d))) + W.
Σ
W B, d (xxl), ,dw))
sid
D. (1)
D
PED
PED
The loss or cost function & is typically a cross entropy function or an 1 norm of the mismatches
between the network outputs and the labels: & (W. (x(e), dd())) x
d(p)
Where
indicates the output layer number. We present more in detail the architecture of Feedforward Neural Network (FNN) hereafter.
1.1 NOTATIONS AND FEEDFORWARD NEURAL NETWORKS (FNN)
In this section, recall the main details of FNNs, which will be used standard model for Deep Learning The notation used throughout this paper similar to notations presented in LeCun et al. 1988). The main equation governing the FNN, a.k.a. the forward model is the following:
(p) F' W 1 Bx).
k [L..m], Pe
where ID is the database, p designs single sample from the database (e.g. single image audio recording), & is the layer number and n is the total number of layers in the network. The initial input for sample p is x(") (e.g. the vectorized input image data). The state variable x(P) is transformed at each layer through a multiplication by a weight matrix We and an addition of a bias vector Sg. The activation function F, which is typically sigmoid Rectified Linear Unit
(RcLU), is applied element wise on the resulting activation vector: a (p) serves introduce non-linearity in the neural network.
We x + Br. and
1.2 THE LAGRANGIAN AND BACKPROPAGATION
The origin of backpropagation could be traced back to the early 1970s and could be derived by casting Deep Learning as a constrained optimization problem. This section is similar LoILeCun al.) (1988). The main novelty in this section is the addition of regularization term dependent on the state variable R(x) to the cost function f admissibility criteria which we define hereafter:
R (x). The regularization has to verify the
Definition 1: A regularization term is admissible if the second derivative of the augmented cost function w.r.t. the state variable is separable and non-null, i.e.:
deR (p) (g) Xm
(p. DD, Y m)) E [1.m]]
8p=q-
(3)
Ox
p.g.k.m
An example of such regularization is the following function:
R(x)
1
(p) x A
(p)
(()
(4)
2
PED
I..n-1
'Convolutional Neural Networks (CNN) a type FNN. The concepts of this paper apply also CNN.
2

---

Under review as a conference paper at ICLR 2022
(A()) are symmetric positive matrices. Such a choice might seem atypical since the regular- p.k ization often concerns the network parameters, mainly the weights or the biases. This "admissible" regularization was introduced for the sole purpose of guaranteeing non-null partial derivative of
the cost & w.r.t the state variable x This last property is essential to solve Equ. 16 We will show
later that such regularization minimizes also the norm of the gradient (Barrett & Dherin 2020 Smith et al. In order to derive the backpropagation algorithm we introduce the following Lagrangian as per the notation of LeCun et al. (1888::
2021)-
[(x, W b) - lR Σ ΣE
x (p) - W [ (p) + 31) ...)
(5)
PEDA=I...
The Lagrangian contains the original cost function, the admissible regularization term, and the prod- uet of the forward equation with the adjoint state vectors (b(-) p.k=
These adjoint vectors are de-
fined for each layer of the network and each sample of the database; however, their values are not fixed yet and will be chosen in a way that simplifies the gradient computation. If the state variable x verifies the forward equations, then the Lagrangian simplifies to the cost function:
[(x (W, (3) W, 3, b) & (x (W,
The total derivative of the previous Lagrangian w.r.t. the weights or biases is the gradient and could be expressed in terms of partial derivatives follows
dd(x(W a.bb
OC OW.
EpED E Em=L.n
dx aW
BC
dln aw:
dW2
8x
dC(x(W B.b
ac
+
EpEd Em=1..n
dsela) dBe
Dc (xc
dla a,3
d3
8p
The partial derivatives of the Lagrangian w.r.t { Bx Ju f I... are straightforward compute. are non-trivial evaluate and the core idea of back-
(x(()) dx(x))
The Fréchet derivatives dW,, dB.
p.k.m
propagation is the selection of the adjoint state variables (b(") (p) which cancels the superfluous p.k
terms. Such simplification achievable if:
ac
0.
0x
(p]
PED, kE[l..n]
Computing the previous partial derivative yields the following backpropagation equation:
HeR
= b 1==1. WT
(p)
b
= 0.
(9)
0x [p]
k+1
0x (p)
1 is the indicator function, and it is equal to one if the underlying condition E is true and null otherwise. The nabla operator V is a diagonal square matrix with an element-wise derivative of its argument (along the diagonal). The resolution of the backpropagation system could be split into a boundary condition and a backward propagation system. Further details could be found in LeCun (p)
et al. (988)). The particular choice of the adjoint state vectors
(b(")
yields a simple
p=D,k=1.n
formula a for the gradient of the cost function:
G
BW.
BC
Σp
VF
a
(p)
b (p)
x
(p)T
(10)
gA
Oc 33
=-E, E,
VF
ag
b (n)
The backpropagation algorithm is fundamental for Deep Learning. It is simple and provides straightforward solution to an otherwise tedious problem to solve. Unfortunately, developing an effi- cient second-order backpropagation method remains elusive. The current state-of-the-art is based on the use of the R R-operator [Pearlmutter] 1994) to compute the product of the Hessian with a given vector without explicitly calculating storing the Hessian (Martens) 2010; Dauphin et al.) 2014 Agarwal et al.) 2017). In the following section, we provide a different framework for backpropaga- tion which allows the characterization of the second-order Newton direction.
A denominator layout notation for derivation used throughout this paper.
3

---

Under review as a conference paper at ICLR 2022
2 THE SIFRIAN AND THE EXACT NEWTON DIRECTION
It is legitimate to wonder if the Lagrangian multipliers method could be replicated for higher-order optimization. We hereafter provide solution for the second-order case and build an equivalent Lagrangian which we call the Sifrian.
2.1 THE SIFRIAN
The Lagrangian is useful to derive the first-order gradient, and it combines the cost function and the forward model multiplied by adjoint variables. Our approach extend the Lagrangian consists in creating function with the forward model, the backward model, and the definition of the gradient. We choose omit the loss function, as its derivation will generate the gradient again. Starting from this paradigm, we introduce the Sifrian
Definition 2:
The Sifrian S the feed-forward network is defined as follows:
S(x, b, W B. G. = -Exp (xx²)
(p) F
(p)
(p)
a
Tk
+ ((bb)) - W FF (a b(z)
+
B8g
St
(p)
2xc 43
(1I)
+ E (Gx + Ep
VF
a
by
(P)T .Nk k-
(piT
+ +(B+ E, VF
(p) a
b (p)
77
The Sifrian includes all the equations generated by the first order backpropagation, multiplied .N. Ns.
by four new adjoint parameters {7((² <(() point (Nocedal & Wright 2006), the Sifrian, describes equilibrium and it has unique null value when all the forward, backward and gradients equations are verified i.e.:
m While the Lagrangian describes a saddle
S(x (W, 3). (W, x),
ig (W, ,. n) = 0. (12)
We call the previous quantity the equilibrated Sifrian, and it is critical to notice its invariance total derivation w.r.t. either the weights or biases (i.e., remains null). Expressing the total derivative of equilibrated Sifrian using partial derivatives yields the following two equations:
dS
AS SW.
Em.p aWa
dscle)
as dbla) aWE
+ Σn.
dG... as aW: DC..
dg... as 0, aW. 8ym.
aW.
8x
(13)
dS
as 89
+ Em.p di,
(sc 8S
aS (P)
+ Σ
dG aS
dgm. as dBg 8G dge = 0.
+
d9,
8x (P)
ab
Similar to first order backpropagation, { (0) (p) NN. mh
we select the new adjoints variables
to circumvent the calculation of any superfluous terms. We
PED, k=1..
make the following choice:
as aw..
as
as 0,
as = 0.
Vm,
G
gm
(14)
(x({)
0b.
In this case, after vectorizing the weight gradient G (and also N₂), and concatenating all their values across all layers, the Equ. [3 could be cast as the following block matrix system:
dc
de
N
G
N n
G g
H
(15)
4/
dj
"The choice of the Sifrian appellation stems from the Arabic word "Sifr", which means zero. "Rien" means also "nothing" in French.
4

---

Under review as a conference paper at ICLR 2022
The matrix that appears in the previous system (H) is the Hessian. Hence the computation of the Newton direction could be achieved by solving the associated system four equations in Equ. [4 The derivation of the four types of Sifrian equation is provided with further details in the Ap- pendix (..I). We report hereafter the equations for piece-wise affine activation functions (e.g.. ReLU Leaky ReL.U). The general case of C² activation function is included in the Appendix A.
(P)T (1) Ep V (7h -- + by X X (O)
+ 11=22.n. be) (p)T
Sh-1 O,
(2) Ep VF (7h²) (p) + +bx = =0,
(3)7%) (p) -ken W VF(P) (p)
k+1 k+1 7++1
+ Em
2x Oxc.
8-5 (()) - -ken Now
VE (() k+1 k+1
0,
(4) (.2)) 11 W& + VF("") (Nex + +7k)
= +m)=
(16)
Comparison with the R-operator: Characterizing the Hessian effect without explicitly comput- ing its values has been proposed by [Pearlmutter] (1994), using an operator R which requires the preselection of a specific direction study its transformation through the Hessian. The Sifrrian formulation can achieve the same goal by relaxing the two gradient constraints from the Sifrian equations and preselecting the values of (N. n)) The product requires forward pass to compute Ç, a backward pass to compute the Sifrian w.r.t. to the weights and biases. The Sifrian formulation derived differently from the R-operator. Nevertheless, it can still fulfill the same role, and is more suitable for inversion, which we will conduct hereafter.
Finally, the sought-after product is provided by the gradient of
2.2 THE EXACT STOCHASTIC NEWTON (ESN)
The resolution of the previous system is intricate the general case. However, if we consider a single sample, i.e., the stochastic and strictly monotonous activation function, then closed- form solution could be derived.
ESN Theorem:
If the cost function is admissibly regularized, the activation function strictly- monotonous piece-wise affine, the first order adjoints (b(2) p.k
are non-null and the curvature of
the output layer {
8P is invertible, then the minimal-rank stochastic Newton second-order Sx (xx! update has closed-fome form solution:
N₂
Øtg Ox(m)
VF 8 b
(17)
7k 1km
VF
(p)
Mta 3x!P)
N2x
(p)
(x 3x(P)
Proof: Under the proposed assumptions, the Sifrian second equation simplifies to * - b
(p)
which starts a cascade of simplifications. The first equations becomes 1 Sh_1 0. The last layer of the third equation yields: 7/00)
(p)
8
Sn.
(p)
0. The remaining equations become:
ax! (x(
1 k==1.n n-1 ox(!!)
BER
+ 1
F
(p) a
b bi+1 = 0.
(18)
ER 0x! 3x!!
at 0x!
VF
a
(p) (Nxx(()
--1
(p)
+ mp 0.
*The Sifrian yields total of 2 [D] 2 equations with equal number of unknowns.
5

---

Under review as a conference paper at ICLR 2022
The Newton weight is matrix, and it is determined through its product with the adjoint vector. Inverting the Newton direction is a degenerate problem, but the minimal rank solution unique, and it is given in Equ. T7 A major issue still remains: the results of the Newton weight do not extend to the first layer (Equ. 18). To circumvent this shortcoming, we introduce an additional layer before the input, which corresponds the identity multiplication and null bias. This layer remains unchanged throughout the optimization process, and we call it the "white layer". This pre-input extension allows the definition of update rule for the first layer.
White layer concept The third equation of the Sifrian allows the characterization of the Newton weight N₂ only between the 2nd and the output (n layers. Such problem is fundamental and it is legitimate to wonder how is it possible for Hessian-Free methods to work for inversion. The answer lays within the regularization/laming (Marquardi) 1970) which covers this structural gap. The important role of the first layer for the Newton method has been highlighted recently by Wadia al. (021). In our case, and in order extend the inversion result the first layer, we just introduce an additional layer before the input, which has the same size as the input, and does not bring any modification, hence the appellation "white layer". The white layer corresponds to matrix multiplication with the identity, null bias, identity activation function and is unchanged during the training.
[Wb=i, bo=03 F(x)=x
[Wi, b.3 [Wo, bn}
X0
~ X0
Main Network
White Layer
Figure White layer extension before the input of the neural network.
Admissible regularization: The ESN solution relies primarily the existence of the term which would be null if not for the admissible regularization, whose effect revolves ul-
Ox!!!!
timately around minimizing the norm of the state variable
x
(p)
Given that the cost function é
p.k
steers the weights/biases to minimize the mismatches, and consequently the adjoints (b&"
then
p.a
the admissible regularization is contributing to the gradient's 's norm minimization (Equ. 10 which
a desirable features for generalization purposes (Barrett & Dherin 2020 Smith et al. 2021>
The "granular" solution: The admissible regularisation could be removed and this would lead to a "gganularr" solution which updates only the bias of the output layer nn. The granular solution is not practical and it is of no use for the neural network training.
Hypotheses relaxation: Some of the hypotheses of the ESN theorem could be relaxed: notably the Moore-Penros: inverse could be used instead. !x! Ox
invertibility of the output curvature:
8
The output curvature is often positive definite and its inversion simple for e.g. it is the identity for an 1 cost function.

---

Under review as a conference paper at ICLR 2022
3 ADJUSTMENT OF THE EXACT STOCHASTIC NEWTON (ESN)
The ESN solution is exact and simple to compute; however, it diverges if implemented as is. In this section, first address the non-convexity issue and adjust the solution to become descent direction. We also explore the stochasticity effect stemming from the samples randomness during the training process and provide enhancement the ESN, For the remainder of this paper assume also that regularization is a of the same form as Equ. We start this section by correcting the concave directions of the ESN.
3.1 ESCAPING THE SADDLES: DESCENT DIRECTION
The minimal rank solution (Equ. (7) has some similarities with the gradient expression (Equ. 10 yet it not a descent direction. To further illustrate this, we consider the inner product of the Newton and the gradient expressions layer by layer. For the weights, the product is always positive:
(Nas G+)
X (p)
2 0.
(19)
However, most of the Newton biases corresponds to ascent directions:
(ms gk) - 1 +k=n
den
(20)
Oxx (p)
oPen OWN aoa
The last layer bias nature depends on the values of the regularization and the error. One of the main advantages of the Sifrian formulation is that we can treat the weights and biases separately and we can exactly pinpoint to the origin of convexxxx: the bias update. We choose build our saddle-free variation by just changing the signs of the ascent direction. This manipulation is straightforward for all layers except the output bias update. The problematic term corresponds to the "granular" solution (i.e., no regularization), which overfits every sample. We chose to keep the "granular" solution as is and switch the sign the remaining term. This guarantees that the update is a descent direction The saddle-free ESN is the following:
VF (F(a DEP)
N
VF
0x
(21)
1mm
V
an
B PP) 8x
06g
+ Nex
(p) 4-1"
8%
8x
The above convexity correction is significantly simpler than the currently existing methods such as the Gauss Newton truncation (e.g. [Schraudolph] (002)) Martens] 2010) or the absolute Hessian (Dauphin et al. 2014). The convexity correction is the first step in improving the ESN. Another intrinsic issue in the above formulation is that we try to optimize a given sample without taking into consideration the yet "unknown" coming samples. The essence of stochasticity in still missing. In the next section, we include such an aspect into the ESN method.
3.2 RANDOMIZATION
The ESN solution we have proposed so far exact but remains deterministic since focuses on training a single pre-selected sample An intrinsic source of stochasticity in online learning stems from the randomness of the streamed samples. As such, it is preferable to use random variables to describe the dynamics of ESN. The two fundamental equations of ESN after discarding the "granu- lar" solution, adding the white layer are:
T
Dēn 8xx
N = O. with YE
(p)
yk (p)
VF
a
(P)
b&
(p)
(22)
N₂ k-1
+ 7h =.
Thiis point could be further justified with first order Taylor development of the loss function.

---

Under review as a conference paper at ICLR 2022
Let's consider f2 ID the set of possible outcomes of the training sample and randomize the sample index p - p. Aside from {N. n) all the vectors in the above system become random
variables. We solve the randomized Equ. 22 using the following least-squares criteria:
( den 0x
argmin (.
dla (p)
(P)T + Yyk
No
+ Nax
mi
(23)
R=D
We changed the ESN into least-squares problem, which is desirable, given the sizeable well- established literature about optimal unbiased estimators for this class of problems (Aitken [936] Kariya & Kurata 2004). The minimisation could be done for each layer separately, which reduces the inverse problem dimensionality. The search for critical points is detailed the Appendix (A.4). and yields the following randomized ESN system which involves Sylvester equation (for N₂):
Ep
(p) T yk yk
N + Var (
Ep
yk
DER Ox
(24)
x
x
+
= O.
X|- is normalized ie. null mean and identity variance. This aspect has been extensively explored in Deep Learning through batch, weight, layer and group normalization (loffe & Szegedy [2015] Salimans & Kingma 2016 Ba et al. 2016bb Wu & He. 2018). Normalizing the state variable corresponds to the following transformation:
We notice that the above system could considerably simplify if the state variables (p)
+ (V
(p) Kk
x
x (p) Ep (x((e))
(25)
The Sylvester equation for the N& could be entirely circumvented, using the proposed Variance- Invariance Theorem described hereafter.
Iaraaace-Ivvariance Theorem: In addition to the hypotheses of the ESN Thereom (Section 2.2 (p) If vk E [1..n] Var (x=1
> 0, then the randomized ESN is invariant to the variances
Var (p) (x which can be substituted with the identity. The randomized ESN system becomes:
N₂ = E
I+
(p) (p) Yk yk
E
YE
(p)
B8g 0x (P)
(26)
7h NgE
The demonstration builds on the invariance the Newton method affine transformations and is detailed step by step in the Appendix (A.5)
Proof:
3.3 DISCUSSION
Expectations and estimators: We used the expectation extensively in this paper to derive the theoretical ESN solution. However, estimators would replace expectation during implementation. The performance and the computational cost would be directly related to the estimators choice: rank batch estimators all possible with different compromises.
one, moving average,
Notes on convergence: Several convergence results for the Newton method exist (e.g Bottou & Le Cun 2005 Byrd et al. 2011 Meng al. 2020). The ESN convergence fits well within the gen- eral framework developed by "Sunhhag et al. (2009). under some mild and non-restrictive conditions.
To batch not to batch: After randomization, ESN could be used in batch mode. However, there are no guarantees that such a solution solves the "batch" Sifrian equations. Therefore, we focus only on using spot or historical data.
A o-field appropriate, but use only random space Q for the sake of simplicity.
8

---

Under review as a conference paper at ICLR 2022
4 RESULTS
We validate the ESN method for FNNs, using a classification task on MNIST dataset (Lecun et al. 1998), and also an autoencoder training with the CURVES dataset (Hinton & Salakhutdinov 22066). Leaky Relu and He initializer (He et al. 2016 Glorot & Bengio 2010) are used for all the training.
Further implementation details are available in the Appendix (A.6) We report the results hereafter:
MNIST
CURVES
a)
b)
10
108
0.8
0.8
Training lass
Validation loss
Training
20"
Validation
0.4
0.4
10
0.2
101²
1 Wk w Www. Mia
Ww Mwwgg
0
50
100
0
50
100
50
100
0
50
100
Epoch
Epoch
Epoch
Epoch
c)
d)
h)
10
10
1
1
Validation loss
Training lesh
0.6
0.6
Training
10.
Validation
0.4
10
0.2
10
10a
10f
10a
10
10a
10
10a
10
Time (4)
Time (s)
Time (s)
Time (4)
SGDMomentum
ADAM
ADAHessian
Figure 2: Training and validation loss as function of both epochs and wall-clock time for clas- sification (MNIST) and autoencoding (CURVES) with one seed. For MNIST classification, the architecture is (784, 256, 32, 10). For CURVES, the autoencoder has the following architecture (784, 216, 64, 6, 64, 216, 784). Constant learning rates are used 0.001 for ADAM (Kingma & Ba 2014) and ADAHessian (Yao et al. 2020) and 0.01 for SGD and ESN.
5 CONCLUSION
This paper showed that it is possible to derive an exact expression of the stochastic second-order up- date for Deep Learning via second-order Lagrangian which we called Sifrian, under some regular- ization constraints. We revisited backpropagation using Lagrange multipliers method and developed a new framework to better understand the mechanics of the Newton method at the stochastic level. This framework yielded unexpected insights how correct the non-convexity, the importance of the first layer, and how to get a closed-form solution. We further proceeded to randomize the solution, to better align the training with its stochastic nature and avoid overfitting. We tested the solution using simple training models; and despite the known limitations of the Newton method, the ESN (Exact Stochastic Newton) solution was able to perform well adaptive methods in non-convex setting. ESN holds great potential but still requires further refinement for batch training, parameters selection and estimators choice. Generalization of this work other type of networks also research venue which needs further investigation.
REPRODUCIBILITY STATEMENT
The results of this paper are reproducible. Commented Matlab code is included in the supplementary material. All experiments are run on a workstation with eight cores 2.6 GHz CPU.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization for machine learning in linear time. The Journal of Machine Learning Research, 18(1):4148 41847784187, 2017.
Alexander C Aitken. Iv.-on least squares and linear combination observations. Proceedings of the Royal Society of Edinburgh, 55:42-48, 1936.
Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):251-
276, 1998.
Shun-ichi Amari, Jimmy Ba, Roger Grosse, Xuechen Li, Atsushi Nitanda, Taiji Suzuki, Denny Wu, and Ji Xu. When does preconditioning help or hurt generalization? arXiv preprint arXiv:2006.1073: 2020.
Rohan Anil, Vineet Gupta, Tomer Koren, Kevin Regan, and Yoram Singer. Scalable second order optimization for deep learning. arXiv preprint arXiv:2002.09018, 2020.
Jimmy Ba, Roger Grosse, and James Martens. Distributed second-order optimization using cronecker-factore upproximations. 2016a.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv:1607.064450, 2016b.
arXiv preprint
David GT Barrett and Benoit Dherin. 2XXi:2009.111622 2020.
Implicit gradient regularization.
arXiv preprint
Albert S Berahas, Majid Jahani, Peter Richtárik, and Martin Takáč. Quasi-newton methods for deep learning: Forget the past, just sample. arXiv preprint arXiv:1901.0980 2019.
Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, and Ping Tak Peter Tang. A progressive batching I-bfgs method for machine learning. In International Conference on Machine Learning, pp. 620-629. PMLR, 2018
Antoine Bordes, Léon Bottou, and Patrick Gallinari. Sgd-qn: Careful quasi-newton stochastic gra- dient descent. Journal of Machine Learning Research, 10:1737-175: 2009.
Aleksandar Botev, Hippolyt Ritter, and David Barber. Practical gauss-newton optimisation for deep learning. In International Conference Machine Learning, pp. 557-565. PMLR, 2017.
Léon Bottou and Yann Le Cun. On-line learning for very large data sets. Applied stochastic models in business and industry, 21(2):137-151, 2005.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-31 311, 2018.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Charles George Broyden. The convergence of class of double-rank minimization algorithms 1. general considerations. IMA Journal of Applied Mathematics, 6(1):76-90, 1970.
Byrd, Gillian Chin, Will Neveitt, and Jorge Nocedal. On the use of stochastic hessian informa- tion in unconstrained optimization. SIAM Journal on Optimization, 21(3):977-995, 2011.
Richard Byrd, Samantha I. Hansen, Jorge Nocedal, and Yoram Singer. stochastic quasi-newton method for large-scale optimization. SIAM Journal on Optimization, 2602):1008-1031 2016.
Camille Castera, Jérôme Bolte, Cédric Févotte, and Edouard Pauwels. An inertial newton algorithm for deep learning. Journal of Machine Learning Research, 22 114):113111 2021.
Yann Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex op- timization. arXiv preprint arXiv: 406.2052.2 2014.
10

---

Under review as a conference paper at ICLR 2022
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Roger Fletcher. A new approach to variable metric algorithms. The computer journal, 13(3):317- 322, 1970.
Thomas George, César Laurent, Xavier Bouthillier, Nicolas Ballas, and Pascal Vincent. Fast approximate natural gradient descent in kronecker-factored eigenbasis. arXiv preprint arXiv:1806.038844 2018.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intellgencee and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings, 2010.
Donald Goldfarb. A family of variable-metric methods derived by variational means. Mathematics of computation, 24 (3(10)))23-26, 1970.
Donald Goldfarb, Yi Ren, and Achraf Bahamou. Practical quasi-newton methods for training deep neural networks. arXiv preprint arXiv:2006. 08877. 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-500 2006.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference machine learning, pp. 448-456. PMLR, 2015.
Takeaki Kariya and Hiroshi Kurata. Generalized least squares. John Wiley & Sons, 2004.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1:Xi::4112.6980 2014.
Y. Lecun, I.. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recog- nition. Proceedings of the IEEE, 86(1 36(11)2277822224 1998. doi: 10. 12995.7667.
Yann LeCun, D Touresky, Hinton, and T Sejnowski. theoretical framework for back- propagation. In Proceedings of the 1988 connectionist models summer school, volume 1, pp- 21-28, 1988.
Yann A LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Robert Müller. Efficient backprop. In Neural nelworks: Tricks of the trade, pp. 9-48. Springer, 2012.
Dong Liu and Jorge Nocedal. the limited memory bfgs method for large scale optimization. Mathematical programming, 45(1):503-528, 1989.
Donald W Marquardt. Generalized inverses, ridge regression, biased linear estimation, and nonlinear estimation. Technometrics, 12(3):591-612, 1970.
James Martens. Deep learning via dessian-free optimization. In ICML, volume 27, pp. 735-742, 2010.
James Martens and Roger Grosse. Optimizing neural networks with krotecker-factoreed approximate curvature. In International conference machine learning, pp. 2418-2417. PMLR, 2015.
James Martens and Ilya Sutskever. Training deep and recurrent networks with hessian-free opti- mization. In Neural networks: Tricks of the trade, pp. 479-535. Springer, 2012.
Si Yi Meng, Sharan Vaswani, Issam Hadj Laradji, Mark Schmidt, and Simon Lacoste-Julien. Fast and furious convergence: Stochastic second order methods under interpolation. In International Conference Artificial Intelligence and Statistics, pp. 3375-1386. PMLR, 2020.

---

Under review as a conference paper at ICLR 2022
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147-160, 1994.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv: 2019.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. Advances neural information processing systems, 29:901- 909,2016 2016.
Tom Schaul, Sixin Zhang, and Yann LeCun. No more pesky learning rates. In International Con- ference on Machine Leurning, pp. 343-351. PMLR, 2013.
Nicol N Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural computation, (4(7):1723-1) 1738, 2002.
Nicol N Schraudolph, Jin Yu, and Simon Günter. A stochastic quasi-newton method for online
convex optimization. In Artificial intelligence and statistics, pp. 436-443, PMLR, 2007.
David F Shanno. Conditioning of quasi-newton methods for function minimization. Mathematics of computation, 14)1466)6776666, 1970.
Samuel L Smith, Benoit Dherin, David GT Barrett, and Soham De. On the origin of implicit regu- larization in stochastic gradient descent. arXiv preprint arXhv:2101.12176, 2021.
Jascha Sohl-Dickstein, Ben Poole, and Surya Ganguli. Fast large-scale optimization by unifying stochastic gradient and quasi-newton methods. In International Conference on Machine Learning, pp. 604-612. PMLR, 2014.
Peter Sunehag, Jochen Trumpf, SVN Vishwanathan, and Nicol Schraudolph. Variable metric stochastic approximation theory. In Artificial Intelligence and Statistics, pp. 560-566. PMLR, 2009.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning. 4(2):26- 31, 2012.
Neha Wadia, Daniel Duckworth, Samuel S Schoenholz, Ethan Dyer, and Jascha Sohl-Dickstein. Whitening and second order optimization both make information in the dataset unusable dur- ing training, and can reduce prevent generalization. In International Conference on Machine Learning. pp. 10617-10629. PMLR, 2021.
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pp. 3-19, 2018.
Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael W Ma- honey. Adahessian: An adaptive second order optimizer for machine learning. arXiv preprint 0011::20006007719, 2020.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 Cº SIFRIAN EQUATIONS
The inner product used in the Sifrian is either the inner product of vectors the trace product for matrices, which are equivalent after vectorization:
(A, B) trace (B" A) vec (B)² vec (A),
(x,y) = x"y = trace (xy").
The derivation is carried through perturbation factorization for e.g.:
as oW
S (W + &WA) - S (W+)
SW
We carry the derivation and we report hereafter the full Sifrian equations for a C activation func- tions:
(p) (p) ((D)T) (1) - Ep V (7% x x-- + 1==2.nb 6x-1
(p)T
Ep 22 p (p)
Nax (p)
+ 1=22. Wish Xt-1
(T)
Σ, VE
( b/ x
(P) (2) E, V2 D2F(""
(p) b
Nix (p)
+ 2.. W (p)
WECk-11 Ep VF(( (7%²² + +b,a)) = 0.
(3) 7/ 1 k+1
VF (p)
1+117+11 + Em
8E8
(PP)
0x
12) ax)
NK+1x(") (p) + m-+11 - W
+1
k+1
+1== +
k+1 k+1 0.
(p)
b
k+
(4)
(p) Sh
-1=2.
VE
(p)
W
(p)
+ VF(
(p) [ 776 0.
A.2 ESN RESOLUTION FOR C2 ACTIVATION FUNCTIONS
The stochastic case for C functions has the same type of simplifications. Comparing the first and second equations:
(1) - Σ, V (p) (1))) (p)T
7ik x=-1 + -1x=2.mbb b
(p)T
Sk-1
+ E, V2F bi Nix (p)
(p)
+ m 11=2. Wx x--1
(p) -pp VF(()) (v1² + +b(b)) (p) 0,
Σp VP(P)
(p) (p)T
b 1-1
(2) Σ, 22 x
(p) (1)
Nux + m7 - 2 Wx
13

---

Under review as a conference paper at ICLR 2022
This yields that 1 = O. The fourth equation state that N + 7 = 0 always null except for the last layer. Let's focus the last layer. Three equations allows to characterize it:
(2) bad (p)
(VP(P))
V2F (p) NNx (p) + mm
(p)
7/
(3) Yn
(p)
(p)
0,
Uxi txx
(4) Çn
VFLP
N Nnx
(p)
7m =
If we assume that the C² has non null second derivative everywhere then, the previous three equa- tions yield specific value of NN (p)
+ mm and also c!
Except the last layer we have: 7k -(( and a similar system to the piecewise afline case could be derived.
A.3 EXAMPLE: A SIMPLE REGULARIZATION
In this section we give a concrete simple example to further explain the ESN method. the case of an cost function and regularization defined by:
R(x)
Σ PED k=1.nn1
Σ
x (p)
x(x )
have the following solution:
VF (2) 1b LOT
N
VF
7
1 k=n
VF
(p) am
I
-x(x)) Nox
The previous solution is straightforward to compute; the first order backpropagation pro- vides all the elements.
It is co-linear with the gradient except for the bias of the last layer.
The adjoints b(²) (P) are impacted by choice of the regularization parameter A.
The minimal rank Newton solution not descent direction. Most of the biases correspond
an ascent direction.
The squared norm division is problematic and will lead to divergent solution if the norm 0. A sufficient
of the backpropagated errors is very small i.c. condition to avoid divergence consists in defining layer by layer regularization such as:
V
F
a
(p)
b(() |
λ--1 x VF
a
(p) [(2)
It is possible to remove the regularization i.e. - O, this yields "granular" solution which states that the second order optimal solution consists in just adjusting the last layer bias with slope corrected error: VF an "
x(()) The granular solution is not suitable for neural network training, overfits every sample.
(a
A.4 PROOF: PROPOSITION RANDOMIZED ESN
We start from the randomized caat--suures criteria.
argmin (N.)) / di (p)
(p)
+ +y
(D)T No
(D)
+
N x
+
m
R=D
[x(p)]
2
14

---

Under review as a conference paper at ICLR 2022
The optimum is critical point i...
0
4k
-0,
ON
dmk
Each layer could be optimized separately which is desirable feature that reduce the dimensionality of the problem. We get the following derivatives:
T
ON, + dd
(P)
aiR !P:
+ Ykk
Ip)T Yk
No
(P)T N& k-1 + m = 0,
(p)T
+
dsl NNx + 17k)
8n
Integration over Ω yields expectations and two sets of equations:
T
E
Yk
(p)
0x
DēR
E
(p) (D)T) yk
Yk
No
N
x-1
(p)
(
+ M.B
x
(p) 0,
N₂
(D)
77
O.
We simplify the system by right multiplying the second equation with E
xk-1
and substracting,we
get:
T
E
Yk
(p)
(p)T Yk
No + No Var (x-1) = =-B
yk
(p)
D6 a
0x
NB
- = 0.
The above expression corresponds Sylvester equation. The last two equations are the main result of the proposition.
A.5 INVARIANCE OF ESN TO NORMALISATION:
In this section we demonstrate that the ESN is invariant normalisation which would allow for simpler resolution of the Sylvester Equation. Such a result is expected for Newton method, we do the demonstration step by step. First let's start by reformulating the forward problem with normalized state variable
==(v (V (x(²²) (xar
(p) x
Ey
x
(0))
Σ
x
m
The original state variable is an affine transformation of the normalized one:
k
EAs(
(P)
+ m
The matrix Σg is symmetric and positive. We assume further that it is definite i.e. invertible in this context. The forward model becomes:
Ens
Σ
m
F
(W
W
m BBx)
The square-root of the variance and the expectation could be absorbed into the weights/biases:
W W Ex-1
B = Bx + Wima----
With the above notations, the forward model becomes:
Exsh (p) + m. F (Wis + 3%)
15

---

Under review as a conference paper at ICLR 2022
We new adjoint u. The Lagrangian becomes:
[(x, W, B) i Σ Σ The derivative w.r.t.
Exs( (P)
(D) me F (Wishi+ + ,
PED k=
(p) should be null, which yields the following backpropagation equation.
ac
(p) En u - W V
(a u
(p)
(p)
diR 0.
0s(p)
(p)
0x (p)
Given the definition of W+ The adjoint equation is the same as the original, hence and the first order adjoint is unmodified. The gradient is slightly modified:
G
ac aw
Ep
F
akk
(p)
uk
(P)
1
(P)T
gk
ac = 03
Ep
VF
ag
(p)
u
(p)
Let's move to the Sifrian:
S(s, u. W Br G¹ "'..g'.''', 77 =x.p ( EES
(Wis/2,+ + (B)) 7/2% (p)
m
+ Exuu (p) - k== W k+1
T TV
(a(p)
(8+1))
(p)
ux+1 + EB
(p)
ax
Dia S2 (p)
+ +5 G/ Ep
F
a
(p)
u sk-1 No¹
(p) (P)T
+ B/ + Ep
F
a u
(p)
The Sifrian equations are:
(1) Σ, VF(2) (7% (m) (p)T + u k- + u u6) (20) 26-1 (19T) 0, (()
(p)T
(2) E, VE(E) (7 + uu =0,
(3) E,>% (p) - Isen W/ k+1
T v
[ pp))
k+1 Yeet (p) + Em Es
9x ax!!!
8:
lpt
Em (p) + licn TVp() (p)
k41
0,
(4) (4) - 1 V W (p)
+ VF(")) (Nis + +m6 = 0.
We follow the same steps of the ESN Theorem demonstration, add the white layer and we remove the granular solution. We finally get the following stochastic system:
T
D6 Tx!
Σx + VVF (2tt1) 4-11 No41 = 0,
(P)
N + vh. = 0.
The randomization yields,
T
E
y
(p) (p)T yk
No. + NgVar (s)) --E
yk
(p) ae
Σx
ox("1
N E
(p) Sk-1
+ + = 0
16

---

Under review as a conference paper at ICLR 2022
The is normalized hence:
Var (p)
Sk kk-1
sk
= 0.
The randomized, ESN with the normalized state variable has the following solution:
T
N
E
I
yk
(p)
(P)T
E
Y
(p)
BEg
ΣN,
0xc
The
We revert to the original variables from Equ.
A.5
add convexity correction and we get the following
solution:
N₂
E
I yk
(p)
E
y
(p)
aēn
0x
7h N
pp) x
A.6 IMPLEMENTATION DETAILS:
In this section specify technical details of our implementation. First, remove the "granular" terms from our solution, since they do overfit each sample by construction.:
N₂ -E
I I+yb
E
y
(p)
Dtn
8x
7h N
ESN is solved for each layer independently, which means that the inverted matrices scale smaller than the empirical Fisher matrix for e.g.. To further illustrate this point, let's consider, for e.g., the feedforward network with layers sizes [784, 256, 32, 10] (MNIST classification): the empirical Fisher matrix would have a size of 210298x210298, while the biggest matrix inver- sion for ESN would be only 256x256. In practice, the computation requires initially
T
pectations
E y
(p)
D6n 8x
E
which could be estimated using exponentially de- 1-1
caying moving averages (Similar to ADAM). The product with the non-centered precision matrix could be approximated in several ways. We list hereafter at least three meth-
E
+ yk
(p)
(p)T)
ods:
Direct method: the non-centered covariance matrix could be estimated using an exponen- tially decaying moving average and inverted directly given the small sizes.
Recursive Least-Squares (RLS): A sliding window could be used to update recursively the estimation N (k) using Sherman-Morrison formula with an initialization of the precision matrix I. Such method is classic of online learning and is similar Kalman filtering.
Rank one method: instead of involving the historical data, the simplest/crudest estimation of the covariance matrix is based on the spot/instantaneous information. The precision matrix could be derived using Sherman Morrison formula (applied once):
Sherman-Morrison
(p) (P) Yk yk
(I+y y yk (P)))
(p)
2
17

---

Under review as a conference paper at ICLR 2022
Probability distribution/weiihtts: It is common to weights in the context of least-squares regression. For Deep Learning. we could increase the importance of samples that are not well assimilated into the network, ie., high errors(or vice-versa). This is possible for e.g. by choosing x
probabilities/weight proportional to errors' norms: w(p)
d
The ESN regression 2
equations become:
T
N - (1(1)) wl0) wll
(p) (p)T y yk
E
wlllyy
(p)
DER !x!
(w (())
7K No
3 [w(t))
Effects of the admissible regularization: We stated in this paper that the admissible regularisa- tion R(x) reduces the norm of the state variable x. To further illustrate this statistical effect, we will use MNIST classification as an example, with regularized and un-regularized (normal) stochastic gradient descent method. For the sake of simplicity we consider the following form of regularisa- tion:
R (x) = Σ E (xx (p)
PED k=
The architecture of the FNN is the same from the experimental section i.e. {784, 256, 32, 10). We
select learning rate of μ 0.001 and various values of À {0, 10 10 10 ",104,10-99 10-
Norm of the state variable
Training Errors
0.5
1.10
2.0
140
1=0.00001
1-0.0001
0.45
2=0.00001
2-0.000
1-0.001
1=0.001
146
1-0.01
0.4
J=0.11
Training Errors
RRMs
138
0.2
136
0.15
0.1
Epoch
Epoch
for different values of = (o, 10 10-3, 10-4 10-53- SGD is used as the training method, The higher values of À reduce further the norm of the state variable x. Training cost is reported in the right side of the figure.
Figure 3: Effect of the admissible regularization on the norm of the state variable Σ
(p) x 2
18


Reviews:
[{"review_id": "mlI3bDJztfA", "reviewer": "Reviewer_3eEq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work extends the 1st order results in (LeCun et al., 1988) to include 2nd order information for feed forward neural nets, and experimentally compares the new 2nd order methods with other neural net training techniques. The Sifrian formulation is interesting and provides new neural net training methods. There is a potential issue for the Sifrian to be hard to solve.\nHowever, the paper requires the existence of a peculiar regularizer, but does not discuss any statistical properties of this regularizer.", "summary_of_the_paper": "The paper considers feed forward networks as a base model, build a second-order Lagrangian which it calls Sifrian,\nand provides a closed-form formula for the exact stochastic Newton direction under some monotonicity and regularization conditions. It proposes a convexity\ncorrection to escape saddle points, and it reconsiders the intrinsic stochasticity of\nthe online learning process to improve upon the formulas.", "summary_of_the_review": "The work extends the 1st order results in (LeCun et al., 1988) to include 2nd order information for feed forward neural nets, and experimentally compares the new 2nd order methods with other neural net training techniques. The Sifrian formulation is interesting and provides new neural net training methods.  There is a potential issue for the Sifrian to be hard to solve. However, the paper requires the existence of a peculiar regularizer, but does not discuss any statistical properties of this regularizer.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dCbIKT9wNQA", "reviewer": "Reviewer_wxhq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall assessment\n==================\n\nOverall, I find the paper hard to read and follow, in particular due to the notations (see section bellow). The introduction of the Sifrian is not really justified (**Q1**). It seems to derive from a splitted problem with auxillary variables but this is never explicited. In particular, I believe there is a link with ADMM training that use such auxillary variable which should be explicited (**Q2**). Moreover, the results only apply to very specific networks and these constraints are not discussed (**Q3**) and the numerical experiments are not really convincing (**Q4**). For these reasons, I feel that the paper is not ready for publication and I recomend rejection.\n\n**Q1:** Overall, I feel that the approach is not well justified in the current manuscript. In the Sifrian, it is unclear why the loss function is omitted? It is also unclear why one can choose in Eq.(14) quantities to be equals to what is proposed. In Eq.(15), it is not clear why $H$ would be the Hessian. Indeed, if $G,g$ were the gradient, it would be the Hessian but here, $G$ and $g$ are variables so it is unclear why it is exactly the Hessian. Overall, I feel that these missing justification is mainly due to an unclear exposition but this makes it very hard to get an intuition on why this method should work.\n\n**Q2:** The proposed approach looks very similar to ADMM training for neural network (see for instance [A]). This paper should be mentionned and the main difference with the proposed method shoudl be highlighted.  Also, could you explain what is the main advantage of the Sifrian compared to the Augmented Lagrangian?\n\n**Q3:** The assumptions for this method are not standard and are scattered across the paper. This makes it hard to know when this method can be applied. Indeed, the specific regularisation, the need for a white layer, a strictly monotonous do not appear in a common place when exposing the contribution. Moreover, the limitation they introduce are not really discuss.\n\n**Q4:** The numerical evalution of the method is not really convincing. The scale of the considered problem is really small (MNIST and CURVE). The proposed method is not performing better than the other methods, neither in iteration or in time. For the other methods, the choice of parameters is not really discussed (for instance, is the `SGDMomentum` method slow on CURVE beccause of the choice of step size). Also, the implementation of the proposed method also include steps that are not discussed in the main manuscript to avoid overfitting, using moving average with an extra parameter. While this probably helps with variance reduction, discussing this in the main part of the paper seems necessary.\n\n\nMinor comments, nitpicks and typos\n----------------------------------\n\n- **M1:** The need for the white layer seems very artificial. I would be surprised that it cannot be removed by specifying this constraint in the Sifrian. \n\n- p.2: note$^1$ -> a CNN is a FNN. It would be better to say that while only dense networks are considered, this also applies to CNN.\n- p.2 _notation $x_p(n)$ -> usually, using exponent notation $x^{(p)}$ for sample number makes it more readable, to avoid collapsing with coordinate selection and layer numbering in the compact notation.\n- p.2 _\"$p$ designs one single pattern\"_ -> $p$ designs a single sample.\n- p.2 _Compact notation_: The 2 sets of notations make it confusing and I think only using the compact notation would make the paper clearer.\n- Definition.1: use a definition environment to make it clearer where the definition starts and stops.\n- Eq.(4): it is not clear immediatly that $x$ is the activation of all layers.\n- p.4 _\"Our approach to extend the Lagrangian consists of\"_ -> \"consits in\".\n- Definition.2: I dont understand why you did not use $b_p$ instead of $\\gamma_p$ to make the notation more consistent with Eq.(5)? I think this is the same term as in the Lagrangian and not changing this would help the reader follow.\n- Eq.(12): I think there is a missing $g(W, \\beta, x, b)$.\n- p.5: _The first equation becomes_ -> Not sure why $b_{p, k}$ disappears and why the indexes  are not `2..n`.\n- p.7: _\"which by construction overfits to every pattern\"_ -> overfits every sample.\n- p.7: _\"The last layer bias nature depend\"_ -> depends.\n- Eq.(25): put variable relatively to which you minimize under the argmin.\n\n\nExtra References\n----------------\n\n[A] Taylor, G., Burmeister, R., Xu, Z., Singh, B., Patel, A. and Goldstein, T., 2016. [_Training neural networks without gradients: A scalable admm approach._](https://arxiv.org/pdf/1605.02026.pdf) In ICML (pp. 2722-2731).\n", "summary_of_the_paper": "This paper proposes a stochastic second order method to train neural network under some specific regularisation criterion. The method is based on the Sifrian, an extension of the Lagrangian that splits the definition of the gradient of each layer's parameter as different constraints with their own multiplier. Solving the best direction from the Sifrian is complicated in the general case but can be done when considering only one sample. This allows for a stochastic algorithm to train the neural network. Finally, some limited  numerical experiments are conducted.", "summary_of_the_review": "Overall, I find the paper hard to read and follow, in particular due to the notations. The introduction of the Sifrian is not really justified (**Q1**). It seems to derive from a splitted problem with auxillary variables but this is never explicited. In particular, I believe there is a link with ADMM training that use such auxillary variable which should be explicited (**Q2**). Moreover, the results only apply to very specific networks and these constraints are not discussed (**Q3**) and the numerical experiments are not really convincing (**Q4**). For these reasons, I feel that the paper is not ready for publication and I recomend rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "J_XyMTOqZCc", "reviewer": "Reviewer_CD8M", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This manuscript is among the many proposals of applying a second-order method to train neural network models. The problem being tackled is for sure of great interest, but unfortunately, this manuscript fails to provide a meaningful solution to this open problem.\nThe major issues of the manuscript include:\n\n1. Both the numerical result and the theoretical contributions are weak. Usually we expect a paper with either a strong theoretical result or outstanding numerical performance. Unfortunately, the numerical results show that the proposed method performs significantly inferior to existing methods, even in terms of the number of epochs and in terms of the training objective, for which usually second-order methods stand out. From the theoretical side, the auxiliary function for deriving the algorithm is not well-motivated, and the derived algorithm, although directly associated with the auxiliary function, has only weak connection with the original objective to minimize.\n\n2. Another issue is that there is no convergence guaantees for the proposed algorithm. The authors claimed that the framework of Sunehag et al. (2009) could be applied, but the assumptions in that work require a unique global minimizer, which is not verifiable at all for neural network models.\n\n3. I also have strong concerns against the claim of escaping saddles in Section 3.1. Usually in nonconvex optimization like the training of neural network models, escaping saddle points is referred to preventing the iterates from trapped in saddle points of the training objective, but the discussion in sec 3.1 is simply discussing how to obtain a descent direction in general. The terminology is quite confusing.\n\n4. Overall speaking, the motivation of the proposed auxiliary function and of the algorithm is weak and the readability of the paper can be significantly improved. It was extremely hard for me to understand what the authors would like to express, but the concepts could actually be made much more intuitive. Even in the preliminary part of introducing backpropagation, the path the authors took is abstruse, while back propagation itself should be a simple concept by viewing from the simple chain rules. The proposed auxiliary function is also hard to understand the intuition behind and its connection with the optimization of the original objective. What the auxiliary function describes and why we want to solve for the point satisfying (12) are not clearly described nor motivated, and clearly its connection to finding a second-order step for the training objective is weak. The modification of the update step to make it a descent one also looks like quite arbitrary, and if the original update direction is \"Newton\", this change for sure destroys the meaning of the derivation.\n\nI have read the authors' responses, and some misunderstandings of the regularizer are clarified. But the quality of the work still remains a huge concern and my reccomendation for this manuscript remains unchanged.\n\n", "summary_of_the_paper": "This manuscript proposes to apply a Newton-type algorithm for training feed-forward neural network models.\nWhen the regularizer added to the optimization problem satisfies certain additional assumptions, the algorithm can be implemented efficiently with additional assumptions on the activation function, including monotonicity and piecewise affinity.\n", "summary_of_the_review": "The manuscript is poorly motivated and not clearly written, and the proposed algorithm has  neither strong numerical nor sound theoretical support.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GUheCP5X44m", "reviewer": "Reviewer_Qnsb", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In summary, my opinion is that the paper falls well short of its claims, for the following reasons:\n\n1) The approximations involved are sometimes crude and often not well motivated. For example:\n- What the authors call \"stochastic case\", is truly the \"batch size = 1\" case. I do not expect training with one data point per update to work in reasonable circumstances.\n- I think approximating the inverse of H by knowing just its product with a single vector is unreasonable. Basically, we know the curvature of the loss along one direction only (which we can't even control)! I don't think there is any point in doing that, one is better served by using standard diagonal approximations of the Hessian or the Fisher matrix, as done in several previous work. In that case we actually know the curvature along several directions.\n- The fact that only the bias, and not the weights, contribute to divergence of the Netwon's update worries me a lot, I don't expect that to happen in any reasonable circumstance. It suggests that all the approximations made are highly unrealistic.\n- Part of the motivation is to go beyond the approximations made in previous work, but the authors end up making them anyway towards the end, e.g. the K-FAC like approximation.\n- The assumption that the effect of variance is negligible in Eq.(27) is completely unjustified.\n\n\n2) The writing of the paper is quite poor, and it goes worse and worse towards the end, with several typos and confusing statements. It looked like the authors struggled to finish the paper in time for the submission deadline. For example:\n- I appreciate that the authors provide Section 1 to remind readers how to derive backpropagation using lagrange multipliers. That is very intuitive, introducing auxiluary variables and lagrange multipliers does not change the final result. However, when moving to section 2, it is completely unclear where the Newton's update comes from.\n- Several sections towards the end of the paper are cunfusing and out of context, such as: \"Probability distribution/weights\", \"Notes on convergence\", \"To batch or not to batch\". \n- Notation and nomenclature are highly confusing. Besides using symbols that are different from standard convention, which is maybe OK, they use confusing wording: \"positive symmetric matrices\" instead of \"positive definite matrices\", \"adjoint state vectors\" instead of \"lagrange multipliers\".\n\n3) Finally, the \"Results\" section: by just looking at the plots, it seems that the proposed method is worse than most of competitors. Even worse, there is no comment or interpretation to make sense of the results.\n\n", "summary_of_the_paper": "This paper claims that it is possible to compute the Newton method's update exactly for deep neural networks (multi-layer perceptrons).\nThe motivation is that Newton's method, as a second-order optimizer that includes loss curvature information, should improve upon first-order optimizers, such as gradient descent, that use only first derivatives (gradient) of the loss. Second order methods tipically converge in a smaller number of iterations, but each update is expensive to compute and that's why they are not widely used in practice.\nIt must be noted that Newton's method is almost never mentioned in the context of Neural Networks (NN), because it is only guaranteed to converge for convex loss functions (which is clearly not the case for NN). However, the authors claim they have some tricks to fix that. ", "summary_of_the_review": "Given the above points 1, 2, and 3 I recommend rejection", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a second-order optimization algorithm for neural nets which extends LeCun's classic Lagrangian framework. The paper derives a method for computing the exact Newton step for a single training example for a multilayer perceptron. It then describes approximations that can be used to extend the method to more examples.

The authors claim to have spotted factual errors in the reviews. However, I've looked into the issues, and I find myself agreeing with the reviewers on each of those points (or, if there are misunderstandings, they result from a lack of clarity in the paper rather than insufficient scientific computing background on the part of the reviewers).

The authors claim to have solved a longstanding problem by giving an efficient method for calculating the stochastic Newton step (for a single training example). However, it's not clear this is very useful; as a reviewer points out, estimating the curvature with a single example can't give a very accurate estimate. Once the method is extended to batches, more approximations are required. I also agree with the reviewers that the later parts of the methods section appear a bit rushed.

As the reviewers point out, in the experimental comparisons, the proposed method seems to underperform SGD with momentum even in terms of epochs, which is the setting where second-order methods usually shine. Other second-order optimizers (e.g. K-FAC) have been shown to outperform first-order methods in terms of both wall clock time and epochs, so epochwise improvement seems like the minimum bar for a second-order optimization paper.
Decision: Reject