Modern convolutional networks, incorporating rectifiers and max-pooling, are neither smooth nor convex. Standard guarantees therefore do not apply. Nevertheless, methods from convex optimization such as gradient descent and Adam are widely used as building blocks for deep learning algorithms. This paper provides the first convergence guarantee applicable to modern convnets. The guarantee matches a lower bound for convex nonsmooth functions. The key technical tool is the neural Taylor approximation – a straightforward application of Taylor expansions to neural networks – and the associated Taylor loss. Experiments on a range of optimizers, layers, and tasks provide evidence that the analysis accurately captures the dynamics of neural optimization. The second half of the paper applies the Taylor approximation to isolate the main difficulty in training rectifier nets: that gradients are shattered. We investigate the hypothesis that, by exploring the space of activation configurations more thoroughly, adaptive optimizers such as RMSProp and Adam are able to converge to better solutions.
1 INTRODUCTION
Deep learning has achieved impressive performance on a range of tasks (LeCun et al., 2015). The workhorse underlying deep learning is gradient descent or backprop. Gradient descent has convergence guarantees in settings that are smooth, convex or both. However, modern convnets are neither smooth nor convex. Every winner of the ImageNet classification challenge since 2012 has used rectifiers which are not smooth (Krizhevsky et al., 2012; Zeiler & Fergus, 2014; Simonyan & Zisserman, 2015; Szegedy et al., 2015; He et al., 2015). Even in convex settings, convergence for nonsmooth functions is lower-bounded by 1/ √ N (Bubeck, 2015).
The paper’s main contribution is the first convergence result for modern convnets, Theorem 2. It applies to any neural net with a loss convex in the output of the net. The idea is simple: backprop constructs linear snapshots (gradients) of a neural net’s landscape; section 2 introduces neural Taylor approximations which
are used to construct Taylor losses as convex snapshots closely related to backprop. The online convex optimization framework (Zinkevich, 2003) then gives 1/ √ N convergence to the Taylor optimum, matching the lower bound in (Bubeck, 2015). Section 2.3 investigates the Taylor optimum and regret terms empirically. We observe that convergence to the Taylor optimum occurs at 1/ √ N in practice.
The nonsmoothness of rectifier nets is perhaps underappreciated. Fig. 1 shows a piecewise-linear (PL) function and its gradient. The gradient is discontinuous or shattered. Shattering is problematic for accelerated and Hessian-based methods which speed up convergence by exploiting the relationship between gradients at nearby points (Sutskever et al., 2013). The success of these methods on rectifier networks requires explanation since gradients at (nearby) points on different sides of a kink are not related. Further, the number of kinks grows exponentially with network depth (Pascanu et al., 2014; Telgarsky, 2016).
Section 3 addresses the success of adaptive optimizers in rectifier nets.1 Adaptive optimizers normalize gradients by their root-mean-square; e.g. AdaGrad, RMSProp, Adam and RadaGrad (Duchi et al., 2011; Hinton et al., 2012; Kingma & Ba, 2015; Krummenacher et al., 2016). Dauphin et al. (2015) argue that RMSProp is successful because it approximates the equilibriation matrix√
diag(H2) which approximates the absolute Hessian |H| (Dauphin et al., 2014). However, the argument is at best part of the story when gradients are shattered.
The only way an optimizer can estimate gradients of a shattered function is to compute them directly. Effective optimizers must therefore explore the space of smooth regions – the bound in theorem 2 is only as good as the optimum over the Taylor losses encountered during backprop. Observations 1 and 2 relate smooth regions in rectifier nets and the Taylor losses to configurations of active neurons. We hypothesize that root-mean-square normalization increases exploration through the set of smooth regions in a rectifier net’s landscape. Experiments in section 3.3 confirm the hypothesis.
1.1 COMPARISON WITH RELATED WORK
Researchers have applied convex techniques to neural networks. Bengio et al. (2006) show that choosing the number of hidden units converts neural optimization into a convex problem, see also Bach (2014). A convex multi-layer architectures are developed in Aslan et al. (2014); Zhang et al. (2016). However, these approaches have not achieved the practical success of convnets. In this work, we analyze convnets as they are rather than proposing a more tractable, but potentially less useful, model. A Taylor decomposition for neural networks was proposed in Montavon et al. (2015). They treat inputs as variable instead of weights and study interpretability instead of convergence.
Our results are closely related to Balduzzi (2016), which uses game-theoretic techniques to prove convergence in rectifier nets. The approach taken here is more direct and holds in greater generality.
2 CONVERGENCE OF NEURAL NETWORKS
Theorem 2 uses techniques and concepts from online convex optimization, which provide worst-case bounds in adversarial settings. We relate adversarial methods to deep learning through the Taylor loss.
Intuitively, backprop searches a vast nonconvex landscape with a linear flashlight (Taylor losses are a more sharply focused convex flashlight, see A.4). The adversary is the landscape: from backprop’s perspective its geometry is an unpredictable external force. The Taylor losses are convex problems that backprop de facto optimizes – the gradients of the actual and Taylor losses are identical. The Taylor optimum improves when, stepping over a kink, backprop shines its light on a new (better) region of the landscape (fig. 2). Regret quantifies the gap between the Taylor optimal loss and the losses incurred during training.
1For simplicity, we restrict to fully connected rectifier (ReLU) nets. The results also apply to convolutions, max-pooling, dropout, dropconnect, maxout, PReLUs and CReLUs (Srivastava et al., 2014; Wan et al., 2013; Goodfellow et al., 2013; He et al., 2015; Shang et al., 2016).
2.1 ONLINE CONVEX OPTIMIZATION
In online convex optimization (Zinkevich, 2003), a learner is given convex loss functions `1, . . . `N . On the nth round, the learner predicts Wn prior to observing `n, and then incurs loss `n(Wn). Since the losses are not known in advance, the performance of the learner is evaluated post hoc via the regret, the difference between the incurred losses and the optimal loss in hindsight:
Regret(N) := N∑ n=1 [ `n(Wn)︸ ︷︷ ︸
losses incurred by learner − `n(V∗)︸ ︷︷ ︸ optimal-in-hindsight
] where V∗ := argmin
V∈H [ N∑ n=1 `n(V) ] .
An algorithm has no-regret if limN→∞ Regret(N)/N → 0 for any sequence of losses with bounded gradients. For example, Kingma & Ba (2015) prove that Adam has no-regret: Theorem 1 (Adam has no-regret, (Kingma & Ba, 2015)). Suppose the the losses `n have bounded gradients ‖∇W `n(W)‖2 ≤ G and ‖∇W `n(W)‖∞ ≤ G for all W ∈ H and suppose that the weights chosen by the algorithm satisfy ‖Wm −Wn‖2 ≤ D and ‖Wm −Wn‖∞ ≤ D for all m,n ∈ {1, . . . , N}. Then Adam satisfies
Regret(N)/N ≤ O ( 1/ √ N ) for all N ≥ 1. (1)
The regret of gradient descent, AdaGrad (Duchi et al., 2011), mirror descent and a variety of related algorithms satisfy (1), albeit with different constant terms that are hidden in the big-O notation. Finally, the 1/ √ N rate is also lower-bound. It cannot be improved without additional assumptions.
2.2 NEURAL TAYLOR APPROXIMATION
Consider a network with L − 1 hidden layers and weight matrices W := {W1, . . . ,WL}. Let x0 denote the input. For hidden layers l ∈ {1, . . . , L − 1}, set al = Wl · xl−1 and xl = s(al) where s(·) is applied coordinatewise. The last layer outputs xL = aL = WL ·xL−1. Let pl denote the size of the lth layer; p0 is the size of the input and pL is the size of the output. Suppose the loss `(f , y) is smooth and convex in the first argument. The training data is (xd, yd)Dd=1. The network is trained on stochastic samples from the training data on a series of rounds n = 1, . . . , N . For simplicity we assume minibatch size 1; the results generalize without difficulty.
We recall backprop using notation from Martens et al. (2012). Let Jab denote the Jacobian matrix of the vector a with respect to the vector b. By the chain rule the gradient decomposes as
∇Wl ` ( fW(x0), y) = J
E L · JLL−1 · · ·Jl+1l︸ ︷︷ ︸
δl
⊗xl−1 = JEL︸︷︷︸ ∇f `(f ,y) · JLl ⊗ xl−1︸ ︷︷ ︸ ∇Wl fW(x0)=:Gl
(2)
where δl = JEl is the backpropagated error computed recursively via δl = δl+1 ·J l+1 l . 2 The middle expression in (2) is the standard representation of backpropagated gradients. The expression on the right factorizes the backpropagated error δl = JEL · JLl into the gradient of the loss JEL and the Jacobian JLl between layers, which describes gradient flow within the network.
The first-order Taylor approximation to a differentiable function f : R → R near a is Ta(x) = f(a) +f ′(a) · (x−a). The neural Taylor approximation for a fully connected network is as follows. Definition 1. The Jacobian tensor of layer l, Gl := JLl ⊗ xl−1, is the gradient of the output of the neural network with respect to the weights of layer l. It is the outer product of a (pL × pl)-matrix with a pl−1-vector, and so is a (pL, pl, pl−1)-tensor.
Given Gl and (pl× pl−1)-matrix V, the expression 〈Gl,V〉 := JLl ·V ·xl−1 is the pL-vector computed via matrix-matrix-vector multiplication. The neural Taylor approximation to f in a neighborhood of Wn, given input xn0 , is the first-order Taylor expansion
Tn(V) := fWn(x n 0 ) + L∑ l=1 〈 Gl,Vl −Wnl 〉 ≈ fV(xn0 ).
Finally, the Taylor loss of the network on round n is T n(V) = `(Tn(V), yn). 2Note: we suppress the dependence of the Jacobians on the round n to simplify notation.
The Taylor approximation to layer l is Tnl (Vl) := fWn(xn0 ) + 〈 Gl,Vl −Wnl 〉 . We can also construct the Taylor approximation to neuron α in layer l. Let the pL-vector JLα := J L l [ :, α] denote the Jacobian with respect to neuron α and let the (pL × pl−1)-matrix Gα := JLα ⊗ xl−1 denote the Jacobian with respect to the weights of neuron α. The Taylor approximation to neuron α is Tnα(Vα) := fWn(x n 0 ) + 〈 Gα,Vα −Wnα 〉 .
The Taylor losses are the simplest non-trivial (i.e. non-affine) convex functions encoding the information generated by backprop, see section A.4.
The following theorem provides convergence guarantees at mutiple spatial scales: network-wise, layer-wise and neuronal. See sections A.2 for a proof of the theorem. It is not currently clear which scale provides the tightest bound. Theorem 2 (no-regret relative to Taylor optimum). Suppose, as in Theorem 1, the Taylor losses have bounded gradients and the weights of the neural network have bounded diameter during training. Suppose the neural net is optimized by an algorithm with Regret(N) ≤ O( √ N) such as gradient descent, AdaGrad, Adam or mirror descent.
• Network guarantee: The running average of the training error of the neural network satisfies
1
N N∑ n=1 ` (fWn(x n 0 ), y
n)︸ ︷︷ ︸ running average of training errors ≤ min V
{ 1
N N∑ n=1 T n(V) } ︸ ︷︷ ︸
Taylor optimum
+ O ( 1√ N ) ︸ ︷︷ ︸ Regret(N)/N . (3)
• Layer-wise / Neuron-wise guarantee: The Taylor loss of [layer-l / neuron-α] is T nl/α(Vl/α) := `(T n l/α(Vl/α), y n). Then,
1
N N∑ n=1 ` (fWn(x n 0 ), y
n)︸ ︷︷ ︸ running average of training errors ≤ min Vl/α
{ 1
N N∑ n=1 T nl/α(Vl/α) } ︸ ︷︷ ︸
layer-wise/neuronal Taylor optimum
+ O ( 1√ N ) ︸ ︷︷ ︸ Regret(N)/N . (4)
The global optima of neural nets are not computationally accessible. Theorem 2 sidesteps the problem by providing a guarantee relative to the Taylor optimum. The bound is path-dependent; it depends on the convex snapshots encountered during backprop. In particular, the theorem does not preclude convergence to poor local optima. If the optimizer encounters Taylor losses with poor solutions then the bound remains high even as regret tends to zero.
2.3 EMPIRICAL ANALYSIS OF ONLINE NEURAL OPTIMIZATION AND REGRET
This section empirically investigates the Taylor optimum and regret terms in theorem 2 on two tasks:
Autoencoder trained on MNIST. Dense layers with architecture 784 → 50 → 30 → 20 → 30 → 50→ 784 and ReLU non-linearities. Trained with MSE loss using minibatches of 64. Convnet trained on CIFAR-10. Three convolutional layers with stack size 64 and 5× 5 receptive fields, ReLU non-linearities and 2 × 2 max-pooling. Followed by a 192 unit fully-connected layer with ReLU before a ten-dimensional fully-connected output layer. Trained with cross-entropy loss using minibatches of 128.
For both tasks we compare the optimization performance of Adam, RMSProp and SGD (figure 6). Learning rates were tuned for optimal performance. Additional parameters for Adam and RMSProp were left at default. For the convnet all three methods perform equally well: achieving a small loss and an accuracy of ≥ 99% on the training set. However, SGD exhibits slightly more variance. For the autoencoder, although it is an extremely simple model, SGD with the best (fixed) learning rate performs significantly worse than the adaptive optimizers.
The neuronal and layer-wise regret are evaluated for each model. At every iteration we record the training error – the left-hand-side of eq. (4). To evaluate the Taylor loss, we record the input to the neuron/layer, it’s weights, the output of the network and the gradient tensor Gl. After training, we
minimize the Taylor loss with respect to V to find the Taylor optimum at each round. The regret is the difference between the observed training loss and the optimal Taylor loss. The figures show cumulative losses and regret. For illustrative purposes we normalize by 1/ √ N : quantities growing at √ N therefore flatten out. Figure 3(a) compares the average regret incurred by neurons in each convolutional layer of the convnet. Shaded regions show one standard deviation. Dashed lines are the regret of individual neurons – importantly the regret behaviour of neurons holds both on average and individually. Figs 3(b) and 3(c) show the regret, cumulative loss incurred by the network, the average loss incurred and the Taylor optimal loss for neurons in layers 1 and 2 respectively.
Fig. 4 compares Adam, RMSProp and SGD. Figure 4(a) shows the layer-wise regret on the convnet. The regret of all of the optimizers scales as √ N for both models, matching the bound in Theorem 2. The additional variance exhibited by SGD explains the difference in regret magnitude. Similar behaviour was observed in the other layers of the networks and also for convnets trained on MNIST. Figure 4(b) shows the same plot for the autoencoder. The regret of all methods scales as √ N (this also holds for the other layers in the network). The gap in performance can be further explained by examining the difference between the observed loss and Taylor optimal loss. Figure 4(c) compares these quantities for each method on the autoencoder. The adaptive optimizers incur lower losses than SGD. Further, the gap between the actually incurred and optimal loss is smaller for adaptive optimizers. This is possibly because adaptive optimizers find better activation configurations of the network, see discussion in section 3. Remarkably, figures 3 and 4 confirm that regret scales as √ N for a variety of optimizers, datasets, models, neurons and layers – verifying the multi-scale guarantee of Theorem 2. A possible explanation for why optimizers match the worst-case (1/ √ N ) regret is that the adversary (that is, the
landscape) keeps revealing Taylor losses with better solutions. The optimizer struggles to keep up with the hindsight optimum on the constantly changing Taylor losses.
3 OPTIMIZATION AND EXPLORATION IN RECTIFIER NETWORKS
Poor optima in rectifier nets are related to shattered gradients: backprop cannot estimate gradients in nearby smooth regions without directly computing them; the flashlight does not shine across kinks. Two recent papers have shown that noise improves the local optima found during training: Neelakantan et al. (2016) introduce noise into gradients whereas Gulcehre et al. (2016) use noisy activations to extract gradient information from across kinks. Intuitively, noise is a mechanism to “peer around kinks” in shattered landscapes.
Introducing noise is not the only way to find better optima. Not only do adaptive optimizers often converge faster than vanilla gradient descent, they often also converge to better local minima.
This section investigates how adaptive optimizers explore shattered landscapes. Section 3.1 shows that smooth regions in rectifier nets correspond to configurations of active neurons and that neural Taylor approximations clamp the configuration of active neurons – i.e. the convex flashlight shines on smooth regions in the landscape. Section 3.2 observes that adaptive optimizers incorporate an exploration bias and hypothesizes that the success of adaptive optimizers derives from exploring the set of smooth regions more extensively than SGD. Section 3.3 evaluates the hypothesis empirically.
3.1 THE ROLE OF ACTIVATION CONFIGURATIONS IN OPTIMIZATION
We describe how configurations of active neurons relate to smooth regions of rectifier networks and to neural Taylor approximations. Recall that the loss of a neural net on its training data is ˆ̀(W) = 1D ∑D d=1 ` ( fW(x d), yd ) . Definition 2. Enumerate the data as [D] = {1, . . . , D} and neurons as [M ]. The activation configuration A(W) is a (D ×M) binary matrix representing the active neurons for each input. The set of all possible activation configurations corresponds to the set of all (D ×M) binary matrices. Observation 1 (activation configurations correspond to smooth regions in rectifier networks). A parameter value exhibits a kink in ˆ̀ iff an infinitesimal change alters the of activation configuration, i.e. ˆ̀ is not smooth at W iff there is a V s.t. A(W) 6= A(W + δV) for all δ > 0.
The neural Taylor approximation to a rectifier network admits a natural description in terms activation configurations. Observation 2 (the Taylor approximation clamps activation configurations in rectifier networks). Suppose datapoint d is sampled on round n. Let 1k := A(Wn)[d,layer k] be the pk-vector given by entries of row d of A(Wn) corresponding to neurons in layer k of a rectifier network. The Taylor approximation Tnl is
Tnl (Vl) =
( l+1∏ k=L Wnk · diag(1k−1) ) ︸ ︷︷ ︸
clamp subsequent layers weights and activations
· (Vl −Wnl ) ·
( 1∏
k=l−1 diag(1k) ·Wnk ) · xn0︸ ︷︷ ︸
clamp preceding layers weights and activations
which clamps the activation configuration, and weights of all layers excluding l.
Observations 1 and 2 connect shattered gradients in rectifier nets to activation configurations and the Taylor loss. The main implication is to conceptually factorize neural optimization into hard (finding “good” smooth regions) and easy (optimizing within a smooth region) subproblems that correspond, roughly, to finding “good” Taylor losses and optimizing them respectively.
3.2 RMS-NORMALIZATION ENCOURAGES EXPLORATION
Adaptive optimizers based on root-mean-square normalization exhibit an up-to-exponential improvement over non-adaptive methods when gradients are sparse (Duchi et al., 2013) or low-rank (Krummenacher et al., 2016) in convex settings. We propose an alternate explanation for the performance of adaptive optimizers in nonconvex nonsmooth settings.
Let ∇` := 1D ∑D d=1∇ `d denote the average gradient over a dataset. RProp replaces the average gradient with its coordinatewise sign (Riedmiller & Braun, 1993). Hinton and Tieleman observed that normalizing by the root-mean-square recovers sign(∇`) =
∑D d=1∇ `d√∑D d=1(∇ `d)2
, where (∇ `d)2 is the square taken coordinatewise. An alternate characterization of the signed-gradient is
Observation 3 (signed-gradient is a maximizer). Suppose none of the coordinates in∇` are zero. The signed-gradient satisfies
sign(∇`) = argmax x∈Bp∞
{ ‖x‖1 : 〈 x,∇` 〉 ≥ 0 } , where Bp∞ = {x ∈ Rp : max
i=1,...,p |xi| ≤ 1}.
The signed-gradient therefore has two key properties. Firstly, small weight updates using the signedgradient decrease the loss since 〈∇`, sign(∇`)〉 > 0. Secondly, the signed-gradient is the update that, subject to an `∞ constraint, has the largest impact on the most coordinates. Viewing the signedgradient as changing weights – or exploring – maximally suggests the following hypothesis:
Hypothesis 1 (RMS-normalization encourages exploration over activation configurations). Gradient descent with RMS-normalized updates (or running average of RMS) performs a broader search through the space of activation configurations than vanilla gradient descent.
3.3 EMPIRICAL ANALYSIS OF EXPLORATION BY ADAPTIVE OPTIMIZERS
Motivated by hypothesis 1, we investigate how RMSProp and SGD explore the space of activation configurations on the tasks from section 2.3; see implementation details in A.6.
For a fixed parameters W, the activation configuration of a neural net with M neurons and D datapoints is represented as a (D × M) binary matrix, recall definition 2. The set of activation configurations encountered by a network over N rounds of training is represented by an (N,D,M) binary tensor denoted A where An := A[n, :, :] := A(Wn). Figure 5 quantifies exploration in the space of activation configurations in three ways:
5(a): Hamming distance plots mink<n ‖An − Ak‖2F , the minimum Hamming distance between the current activation configuration and all previous configurations. It indicates the novelty of the current activation configuration.
5(b): Activation-state switches plots 1tot ∑N−1 n=1 ∥∥An[d, :] − An−1[d, :]∥∥2F , the total number of times each data point (sorted) switches its activation state across all neurons and epochs as a proportion of possible switches. It indicates the variability of the network response.
5(c): Log-product of singular values. The matrix A[ :, :,m] specifies the rounds and datapoints that activate neuronm. The right column plots the log-product of A[ :, :,m]’s first 50 singular values for each neuron (sorted).3 It indicates the (log-)volume of configuration space covered by each neuron. Note that values reaching the bottom of the plot indicate singular values near 0.
We observe the following.
RMSProp explores the space of activation configurations far more than SGD. The result holds on both tasks, across all three measures, and for multiple learning rates for SGD (including the optimally tuned rate). The finding provides evidence for hypothesis 1.
RMSProp converges to a significantly better local optimum on the autoencoder, Fig. 6. We observe no difference on CIFAR-10. We hypothesize that RMSProp finds a better optimum through more extensive exploration through the space of activation configurations. CIFAR is an easier problem and possibly requires less exploration.
Adam performs targeted exploration. Adam achieves the best performance on the autoencoder. Surprisingly, it explores substantially less than RMSProp according to the Hamming distance and activation-switches, although still more than SGD. The singular values provide a higher-resolution analysis: the ±40 most exploratory neurons match the behavior of RMSProp, with a sharp dropoff
3The time-average is subtracted from each column of A[ :, :,m]. If the response of neuron m to datapoint d is constant over all rounds, then column A[ :, d,m] maps to (0, . . . , 0) and does not contribute to the volume.
from neuron 60 onwards. A possible explanation is that momentum encourages targeted exploration by rapidly discarding avenues that are not promising.
4 DISCUSSION
Rectifier convnets are the dominant technology in computer vision and a host of related applications. Our main contribution is the first convergence result applicable to convnets as they are used in practice, including rectifier nets, max-pooling, dropout and related methods. The key analytical tool is the neural Taylor approximation, the first-order approximation to the output of a neural net. The Taylor loss – the loss on the neural Taylor approximation – is a convex approximation to the loss of the network. Remarkably, the convergence rate matches known lower bounds on convex nonsmooth functions (Bubeck, 2015). Experiments in section 2.3 show the regret matches the theoretical analysis under a wide range of settings.
The bound in theorem 2 contains an easy term to optimize (the regret) and a hard term (finding “good” Taylor losses). Section 3.1 observes that the Taylor losses speak directly to the fundamental difficulty of optimizing nonsmooth functions: that gradients are shattered – the gradient at a point is not a reliable estimate of nearby gradients.
Smooth regions of rectifier nets correspond to activation configurations. Gradients in one smooth region cannot be used to estimate gradients in another. Exploring the set of activation configurations may therefore be crucial for optimizers to find better local minima in shattered landscapes. Empirical results in section 3.3 suggest that the improved performance of RMSProp over SGD can be explained in part by a carefully tuned exploration bias.
Finally, the paper raises several questions:
1. To what extent is exploration necessary for good performance?
2. Can exploration/exploitation tradeoffs in nonsmooth neural nets be quantified?
3. There are exponentially more kinks in early layers (near the input) compared to later layers. Should optimizers explore more aggressively in early layers?
4. Can exploring activation configurations help design better optimizers?
The Taylor decomposition provides a useful tool for separating the convex and nonconvex aspects of neural optimization, and may also prove useful when tackling exploration in neural nets.
Acknowledgements. We thank L. Helminger and T. Vogels for useful discussions and help with TensorFlow. Some experiments were performed using a Tesla K80 kindly donated by NVidia.
A APPENDIX
A.1 BACKGROUND ON CONVEX OPTIMIZATION
A continuous function f is smooth if there exists a β > 0 such that ‖∇ f(x) − ∇ f(y)‖2 ≤ β · ‖x− y‖2 for all x and y in the domain. Rectifiers are not smooth for any value of β. Nonsmooth convex functions. Let X ⊂ Rp be a convex set contained in a ball of radius R. Let ` : X → R be a convex function. Section 3.1 of (Bubeck, 2015) shows that projected gradient descent has convergence guarantee
`
( 1
N N∑ n=1 wn
) − `(w∗) ≤ O ( 1√ N ) where wn are generated by gradient descent and w∗ := argminw∈X `(w) is the minimizer of `. It is also shown, section 3.5, that
min 1≤n≤N
`(wn)− `(w∗) ≥ Ω (
1√ N ) where the weights are in the span of the previously observed gradients: wn ∈ span{∇ `(w1), . . . ,∇ `(wn−1)} for all n ∈ {1, . . . , N}. The gradient of a convex function increases monotonically. That is〈
∇ `(w)−∇ `(v),w − v 〉 ≥ 0
for all points w,v where the gradient exists. Gradients at one point of a nonsmooth convex function therefore do contain information about other points, although not as much information as in the smooth case. In contrast, the gradients of nonsmooth nonconvex functions can vary wildly as shown in Fig. 1.
Smooth convex functions. In the smooth setting, gradient descent converges at rate 1N . The lower bound for convergence is even better, 1N2 . The lower bound is achieved by Nesterov’s accelerated gradient descent method.
A.2 PROOF OF THEOREM 2
Proof. We prove the network case; the others are similar. The Taylor loss has three key properties by construction:
T1. The Taylor loss T n coincides with the loss at Wn: `(fWn(x n 0 ), y n) = T n(V)|V=Wn
T2. The Taylor loss gradient T n coincides with the loss gradient at Wn: ∇W `(fWn(xn0 ), yn) = ∇V T n(V)|V=Wn
T3. The Taylor losses are convex functions of V because `(f , y) is convex in its first argument and convexity is invariant under affine maps. If ` is a convex function, then so is g(x) = `(Ax+ b), where A ∈ Rm×n and b ∈ Rm.
By T1, the training loss, i.e. the left-hand side of (3), exactly coincides with the Taylor losses. By T2, the gradients of the Taylor losses exactly coincide with the errors computed by backpropagation on the training losses. That is, the training loss over n rounds is indistinguishable from the Taylor losses to the first order:
losses: 1
N N∑ n=1 ` (fWn(x n 0 ), y n) = 1 N N∑ n=1 T n (Wn)
gradients: ∇W
( 1
N N∑ n=1 ` (fWn(x n 0 ), y n)
) = ∇W ( 1
N N∑ n=1 T n (Wn) ) We can therefore substitute the Taylor losses in place of the training loss (fW(x0), y) without altering either the losses incurred during training or the dynamics of backpropagation (or any first-order method).
Since the Taylor losses are convex, the bound holds for any no-regret optimizer following (Zinkevich, 2003).
A.3 PROOF OF OBSERVATIONS IN SECTION 3
Proof of observation 1.
Proof. The loss `(f , y) is a smooth function of the network’s output f by assumption. Kinks in ˆ̀(W) = 1D ∑D d=1 ` ( fW(x d), yd )
can therefore only arise when a rectifier changes its activation for at least one element of the training data.
Proof of observation 2. Note that the rectifier is ρ(a) = max(0, a) with derivative ρ′(a) = 1 if a > 0 and ρ′(a) = 0 if a < 0.
Proof. Recall that the Taylor approximation to layer l is
Tnl (Vl) := fWn(x n 0 ) + 〈 Gl,Vl −Wnl 〉 = fWn(x n 0 ) + J L l · (Vl −Wnl ) · xnl−1
= fWn(x n 0 ) + ( l+1∏ k=L Jkk−1 ) · (Vl −Wnl ) · xnl−1
The Jacobian of layer k is the function Jk+1k (ak) = Wk+1 · diag ( s′(ak) ) which in general varies nonlinearly with ak. The Taylor approximation clamps the Jacobian by setting it as constant.
For a layer of rectifiers, s(·) = ρ(·), the Jacobian Jk+1k = Wk+1 · diag ( ρ′(ak) ) is constructed by zeroing out the rows of Wk+1 corresponding to inactive neurons in layer k. It follows that the
Taylor loss can be written as
Tnl (Vl) = ( l+1∏ k=L Wnk · diag(1k−1) ) · (Vl −Wnl ) · xnl−1
Finally, observe that
xnl−1 =
( 1∏
k=l−1 diag(1k) ·Wnk
) · xn0
since diag(1k) ·Wnk · xnk−1 = diag ( ρ′(ak) ) ·Wnkxnk−1 = ρ(Wnk · xnk−1).
Proof of observation 3.
Proof. Immediate.
A.4 COMPARISON OF TAYLOR LOSS WITH TAYLOR APPROXIMATION TO LOSS
It is instructive to compare the Taylor loss in definition 1 with the Taylor approximation to the loss. The Taylor loss is
` ( Tn(V), yn ) = ` ( fWn(x n 0 ) + L∑ l=1 〈 Gl,Vl −Wnl 〉 , yn ) In contrast, the Taylor approximation to the loss is
Tn` (V) = ` ( fWn(x n 0 ), y n )︸ ︷︷ ︸
loss incurred on round n
+ L∑ l=1 〈 JEL ·Gl︸ ︷︷ ︸
δl
,Vl −Wnl 〉 = `n + L∑ l=1 〈 ∇Wl `,Vl −Wnl 〉 .
The constant term is the loss incurred on round n; the linear coefficients are the backpropagated errors.
It is easy to see that the two expressions have the same gradient. Why not work directly with the Taylor approximation to the loss? The problem is that the Taylor approximation to the loss is affine, and so decreases without bound. Upgrading to a second order Taylor approximation is no help since it is not convex.
A.5 DETAILS ON EXPERIMENTS ON REGRET
See section 2.3 for the architecture of the autoencoder and convnet used. The hyperparameters used for different optimizers are as follows: the autoencoder uses learning rate η = 0.001 for RMSprop and η = 0.01 for Adam, while the convnet uses learning rate η = 0.0005 for RMSprop and η = 0.0002 for Adam. All other hyperparameters are kept at their literature-standard values.
Fig. 6 shows the training losses obtained by the convnet on CIFAR-10 and the autoencoder on MNIST.
The gradient tensor Gl is not computed explicitly by TensorFlow. Instead, it is necessary to compute the gradient of each component of the output layer (e.g. 10 in total for a network trained on CIFAR10, 784 for an autoencoder trained on MNIST) with respect to Wl and then assemble the gradients into a tensor. When the loss is the squared error, the Taylor optimal at round n can be computed in closed form. Otherwise we use SGD.
A.6 DETAILS ON EXPERIMENTS ON EXPLORATION
Given matrix or vector A or a, the squared Frobenius norm is
‖A‖2F = M,N∑ m,n=1 A2m,n and ‖a‖2F = N∑ n=1 a2n.
The Hamming distance between two binary vectors a and b can be computed as ‖a− b‖2F . For tractability in the convnet, we only record activations for 1% of the CIFAR dataset, and at most 10000 units of each convolutional layer. We record the full network state on all inputs for the autoencoder. The singular value plots in figure 5 are calculated only on the first 50 epochs.
This paper develops a theoretical guarantee for the convergence of the training error. The result is quite general that covers the training of a wide range of neural network models. The key idea of the paper is approximate the training loss by its linear approximation. Since its linearity in the variables (thus convex), the authors plug in results that has been developed in the literature of online learning. 
This paper has good novelty in using the Taylor approximation thus greatly simplifying the analysis of the behaviour of the model. However, there are two problems about the main result of this paper, Theorem 2.
1. It is not clear if the Taylor optimum would converge or not. 
As noticed by the authors, the upper bound is path dependent. Appendix 3 tries to claim that this Taylor optimum indeed converges, but the proof is buggy. In the proof of Lemma 2, it is proved that the difference between two sequential Taylor optimum is approaching 0. Note that this is actually weaker than being Cauchy sequence and insufficient to guarantee convergence.
2. The lefthand side of Equation (3) (I will denote it by L3 in this review) is not equivalent to training error. 
An upper bound on this average error is not sufficient to guarantee the convergence of the training error neither. Take the gradient descent for example (thus each minibatch x_0^n is the whole training set), the convergence of the training error should be lim_{n -> \infty} l(f_{w^n}(x_0^n), y^n). The convergence of L3 is necessary but not sufficient to imply the convergence of the training error.
Another concern about Theorem 2 (but it is minor compared to the two problems mentioned above) is that to achieve the O(1/\sqrt{n}) rate, the algorithm has to pick a particular learning rate. Larger or smaller learning rate (in the order of n) will lead to significantly worse regret. But in the experiments of the paper, the learning rates are not picked according to the theorem.
Overall, this paper has a good motivation and good novelty. It could be further developed into a good paper. But due to the two problems and a buggy proof mentioned above, I think it is not ready for publish yet.