Mildly Overparameterized ReLU Networks on Orthogonal Data: Incremental Learning and Implicit Bias
arXiv:2605.27097v1 [cs.LG] 26 May 2026
James Town University of Warwick [email protected]
Etienne Boursier INRIA LMO, Université Paris-Saclay [email protected]
Ben Lewis University of Warwick [email protected]
Matthias Englert University of Warwick [email protected]
Ranko Lazić University of Warwick [email protected] May 27, 2026 Abstract The successful training of neural networks hinges on the use of first order optimization methods, yet the theoretical characterization of these methods remains incomplete. This is especially true in settings with mild overparameterization. In this work, we study the gradient flow dynamics of two-layer ReLU networks from small initialization with orthogonal training data. We prove the limiting flow converges to a saddle-to-saddle jump process as the initialization scale tends to zero, revealing an incremental learning phenomenon in which a new neuron activates at each saddle. This analysis recovers the known result of Dana et al. [2025] that the network interpolates the training data with high probability as soon as m ≳ log(n), where m is the network width and n is the number of training samples. This incremental process characterization also allows us to derive a novel implicit bias result: the learned √ interpolator has a squared ℓ2 -norm scaling as n, which is within a constant factor of the minimal ℓ2 norm interpolator. More broadly, our work provides the first rigorous proof of an incremental learning process for ReLU networks, whilst suggesting mildly overparameterized networks can converge to interpolating solutions whose complexity is of the same order as that of the optimal interpolator.
1
Introduction
Despite the remarkable empirical successes of deep learning [Lipman et al., 2023, Zagoruyko and Komodakis, 2016, Cheng et al., 2016], a precise theoretical understanding of the optimization dynamics of neural networks trained by first-order methods remains elusive. The Neural Tangent Kernel (NTK) framework offered an initial answer, establishing convergence to global minima for overparameterized networks [Jacot et al., 2018, Du et al., 2019, Arora et al., 2019b]. However, NTK operates under large initialization assumptions that cause network features to remain nearly unchanged during training; a regime aptly termed lazy by Chizat et al. [2019], and now understood to be unrepresentative of practice [Fort et al., 2020].
1
In the practically relevant small initialization regime, training induces significant changes in network features, a phenomenon known as feature learning. Theoretical analysis of this regime is considerably more challenging, as the resulting dynamics are highly non-convex. General convergence results exist for linear activation architectures [Arora et al., 2018, Woodworth et al., 2020] and, in the infinite-width limit, for nonlinear networks [Chizat and Bach, 2018, Wojtowytsch, 2020]. These results, however, require either smooth activations or infinite data [Holzmüller and Steinwart, 2022, Boursier and Flammarion, 2025a], and thus do not apply to the canonical case of two-layer ReLU networks. Beyond convergence, a central motivation for studying the small initialization regime is its implicit bias: gradient flow is known to favor sparse or low-complexity solutions that generalize well. For classification, two-layer networks trained to interpolation have been shown to converge to min-norm max-margin estimators [Lyu and Li, 2020, Chizat and Bach, 2020, Ji and Telgarsky, 2020], which coincide with sparse, narrow networks [Safran et al., 2022, Boursier and Flammarion, 2023]. Regression is however arguably more representative of practical training dynamics, as characterizing the implicit bias requires describing the entire trajectory rather than only its asymptotic endpoint after interpolation is achieved. In the regression setting, diagonal linear networks favor sparse estimators [Woodworth et al., 2020], while fully connected linear networks favor low-rank solutions [Saxe et al., 2014, Arora et al., 2019a]. For two-layer ReLU networks, implicit bias in regression remains largely open, and constitutes the focus of this work. Progress has been made by restricting to structured data settings. Among these, orthogonal data has emerged as a natural and tractable setting: Boursier et al. [2022] established convergence of gradient flow to a minimal ℓ2 -norm interpolator, but under an initialization condition requiring exponential overparameterization in the number of training samples. Dana et al. [2025] later showed that mild overparameterization suffices to guarantee convergence to an interpolating solution. However, their analysis leaves the norm of the reached interpolator uncharacterized, and understanding this implicit bias in the mildly overparameterized regime remained open until the present work. Contributions. We prove a precise characterization of the implicit bias of gradient flow when training two-layer ReLU networks on orthogonal data in the mildly overparameterized regime, via a complete analysis of the training trajectory. Interestingly, our analysis reveals an incremental learning phenomenon, illustrated in Figure 1: as initialization scale vanishes, the loss alternates between long idle plateaus and abrupt decreases, each corresponding to the activation of a new neuron. While incremental learning has been characterized for linear networks, our work provides the first such characterization for networks with nonlinear activations. An informal statement of our main result follows, where m refers to the width of the network and n the number of training samples. Theorem 1 (Informal). In the regression setting with orthogonal training data, as initialization scale vanishes, and with high probability over the network initialization, the gradient flow trajectory over a two-layer ReLU network with log(n) ≲ m ≪ exp (n log(2)/2) converges to a piecewise-constant process: the iterates move successively from one saddle of the training loss to another, with each transition corresponding to the creation of a new non-zero neuron. The sequence of visited saddles and transition times can be computed via Algorithm 1 without any actual training of the network. Building on this algorithmic description of the limit dynamics, we derive an upper bound on the parameter ℓ2 -norm of the solution found by gradient flow, showing it is within a constant factor of the minimal ℓ2 -norm interpolator.
1.1
Related work
Incremental Learning. Arpit et al. [2017], Nakkiran et al. [2019] empirically demonstrated that standard optimization of deep learning models follows a simplicity bias, whereby learned representations grow increasingly complex over the course of training. Separately, several works have shown that this complexity does not accumulate continuously, but rather incrementally: new data patterns are absorbed
2
0.8
Loss
0.6 10−2
0.4 0.2
10−3
Neuron norm
10−1
Fraction of data points fitted
1
2
1
0 0 t1 t2 t3 t4 t5 t6 t1 t2 t3 t4 t5 t6 Figure 1: We train a two-layer ReLU network of six neurons on 64 orthonormal data points in 64 dimensions. The initialization scale is small (experimental details in Appendix A.1). Left: During training, the loss (red) shows long periods of little change with sudden drops in between. Those drops correspond to an additional set of data points being fitted (green). The drops in the loss happen at the times independently predicted by algorithm 1, which are indicated by the dashed lines. Right: The norms of the hidden layer of the six neurons during the same training. one at a time [Rahaman et al., 2019, Charton, 2024], giving rise to a characteristic training curve marked by long stagnation plateaus and sharp drops in the loss. The resulting training dynamics can thus be understood as a succession of jumps between saddle points of the loss landscape — a phenomenon sometimes referred to as saddle-to-saddle dynamics [Jacot et al., 2021]. Theoretically characterizing this incremental behavior is challenging because it is specific to the small initialization regime, where networks operate in the rich regime and the resulting dynamics are highly non-convex. For two-layer networks, Kunin et al. [2025] offered high-level intuitions for this regime: during each plateau, a dormant neuron is activated in a manner shaped by the local geometry near the saddle point, after which the activated neurons undergo rapid updates as training transitions to the next plateau. However, these intuitions fall short of a complete and rigorous characterization, which has so far been confined to specific linear activation models: for diagonal linear networks, Berthier [2023], Pesme and Flammarion [2023] precisely characterized the incremental learning dynamics, showing that the estimator’s support grows one coordinate at a time; for linear networks and matrix sensing, Gidel et al. [2019], Jin et al. [2023] established, under favorable data or initialization conditions, that the learned matrix undergoes incremental rank increases throughout training. Our work advances this line of research by providing the first theoretical characterization of incremental learning under gradient flow for networks with non-linear activations, specifically two-layer ReLU networks trained on orthogonal data. In a related vein, Abbe et al. [2023] also studied incremental learning in two-layer networks with non-linear activations; however, their analysis is tailored to a specific activation function and optimization algorithm that depart from standard practice. Training two-layer ReLU networks on orthogonal data. Since a theoretical analysis of two-layer ReLU network training remains out of reach for general data distributions, many works have focused on specific toy settings, such as XOR data [Glasgow, 2024], positively correlated data [Wang and Ma, 2023, Chistikov et al., 2023, Min et al., 2024], or linearly separable data [Phuong and Lampert, 2021, Lyu et al., 2021]. Among these, we focus on the orthogonal data setting, first studied by Boursier et al. [2022], who showed that under small initialization, the parameters converge to a minimal ℓ2 -norm interpolator. However, their analysis requires an initialization condition that is only satisfied in a heavily overparameterized regime, where the number of neurons m is exponential in the number of training points n. Dana et al. [2025] later relaxed this assumption, showing that mild overparameterization m ≳ log(n) suffices to guarantee convergence to a global minimum of the training loss.
3
Yet the question of implicit bias in the mildly overparameterized regime remained open, as Dana et al. [2025] do not characterize the nature of the resulting estimator. Specifically, one may ask: does the network still converge to the minimal ℓ2 -norm interpolator in the mildly overparameterized regime? Boursier et al. [2025] answered this negatively, showing that the minimal ℓ2 -norm interpolator is not reached with high probability as soon as m ≲ 2n . Taken together, these results leave a gap precisely in the mildly overparameterized regime log(n) ≲ m ≲ 2n , which our work fills by characterizing the ℓ2 -norm of the interpolator obtained in this setting. More parameters lead to simpler models. The generalization of overparameterized models remains an active area of research in deep learning theory. A phenomenon of particular interest is double descent [Belkin et al., 2019, Nakkiran et al., 2020], whereby overparameterization beyond the interpolation threshold leads to smaller test error. A likely driver of this behavior is that, as the number of parameters grows, the function represented at convergence becomes simpler [Wilson, 2025], exhibiting for example smaller norm [Belkin et al., 2019], fewer effective parameters [Maddox et al., 2020], or lower Kolmogorov complexity [Goldblum et al., 2024]. Numerous theoretical analyses of this phenomenon have been proposed in recent years, but remain confined to linear regression on random features [Liao et al., 2020, Belkin et al., 2020, Hastie et al., 2022, Mei and Montanari, 2022, Bach, 2024]. Our work establishes such a tendency for two-layer ReLU networks trained on orthogonal data: mildly overparameterized networks converge to interpolators with slightly larger parameter ℓ2 -norm than those found in the heavily overparameterized regime.
2
Setting
We consider a two-layer neural network with the ReLU activation, whose output is given by Pm hθ (x) := j=1 aj σ(wj⊤ x), where m is the network width, σ(z) := max{0, z} is the ReLU function, and θ = (a, W ) are the network d×m parameters, which consist of output weights a ∈ Rm and hidden neurons W ⊤ = (wj )m . We j=1 ∈ R n d consider a training dataset (xi , yi )i=1 , which consists of inputs xi ∈ R and outputs yi ∈ R, satisfying the following assumption. ′ ′ Assumption 1. The training inputs are such that x⊤ i xi′ = 1 (i = i ) for all i, i ∈ [n].
Although restrictive, the orthogonality assumption is a useful test bed for analyzing training dynamics, which can even sometimes be relaxed to general random high dimensional data [Dana et al., 2025]. On the other hand, the norm constraint on the inputs implied by Assumption 1 is solely used for sake of simplicity and could be easily alleviated. Training aims at minimizing the mean squared error loss over the training data, 1 Pn L(θ) := (hθ (xi ) − yi )2 . 2n i=1 For analytical purpose, we consider optimizing this loss function by gradient flow, which approximates (stochastic) gradient descent as the learning rate vanishes to 0: θ̇(t) ∈ −∂L(θ(t)) for almost all t ≥ 0.
(1)
Here, ∂ denotes the Clarke [1975] subdifferential, which allows to define the gradient flow beyond differentiable functions. We direct the reader to Appendix B for further details on the Clarke subdifferential. Note that Assumption 1 and eq. (1) imply that ẇj⊤ (t) xi ∈
1 (yi − hθ(t) (xi )) aj (t) ∂σ(wj⊤ (t) xi ). n 4
Hence, for all i ∈ [n], all j ∈ [m], and almost all t ≥ 0, if a hidden neuron component wj⊤ (t) xi is negative then it must be constant for all t′ ≥ t. Empirically, the same is true with “negative” replaced by “non-positive”,1 so Assumption 2 below restricts our attention to realistic training trajectories, which have that property. Assumption 2. For all i ∈ [n] and all j ∈ [m], if wj⊤ (t) xi = 0 for some t ≥ 0, then wj⊤ (t′ ) xi = 0 for all t′ > t. Note that whilst it is guaranteed that a solution of Equation (1) exists locally, it may not be unique. With Assumption 2, along every solution of the subdifferential inclusion eq. (1), the left-hand side θ̇(t) exists — possibly except at the finitely many time points that are the minima of non-empty sets {t ≥ 0 | wj⊤ (t) xi = 0} — and is equal to the element of the right-hand side −∂L(θ(t)) that is obtained by using only 0 as the subderivative of the ReLU function σ at 0. Hence for simplicity of presentation, we fix the latter choice, i.e., in the remainder of the paper we work with 1 (z > 0) instead of ∂σ(z) and we may use the gradient notation to mean the subgradient obtained with that choice. Boursier et al. [2022] also proved that any other constant definition of the subgradient fails to yield global solutions of Equation (1) in presence of orthogonal data. Finally, we note that Bertoin et al. [2021] suggest that this fixed choice tends to be most efficient in practice. We consider balanced initialization of the parameters, which is specified by an initialization scale α. iid
iid
Assumption 3. For all j ∈ [m] we have aj (0) = α sj and wj (0) = α uj , where sj ∼ U({±1}) and uj ∼ U(Sd−1 ).
Whilst the assumption of strictly balanced initialization is partly to simplify the analysis, the work of Azulay et al. [2021] suggests that balanced initializations encourage bias towards the rich regime. Azulay et al. [2021] also note that the commonly used Xavier initialization [Glorot and Bengio, 2010] is approximately balanced. The balanced initialization simplifies the analysis of the training dynamics, as this weight balancedness will be preserved along training, thanks to the following result. Proposition 1 (Du et al. 2018, Theorem 2.1). For all j ∈ [m] and all t ≥ 0, we have |aj (t)| = ∥wj (t)∥ and sgn(aj (t)) = sj . Proposition 1 also implies that the output layer signs remain constant during training. This allows us to treat separately the data associated with positive or negative labels, as well as the neurons with positive or negative output signs. To this end, we denote for s ∈ {±1}, the set Is := {i ∈ [n] | sgn(yi ) = s} of labels with sign s. Neuron dynamics. Denote the normalized hidden-layer weights by wj := wj /∥wj ∥ (in general we use bars to Pdenote normalized vectors and ∥·∥ to denote the ℓ2 -norm) and define the dynamical vector Dj = − n1 i|w⊤ xi >0 (hθ (xi ) − yi )xi . Equation (1), Proposition 1, and Assumption 2 imply the radial and j tangential dynamics of neurons are given for almost all t ≥ 0 by ȧj (t) = Dj⊤ wj and ẇj (t) = sj Id − wj w⊤ j Dj . Acceleration of time. Our goal is to study the limiting dynamics of the parameters trajectory as the initialization scale α goes to 0. When α → 0, escaping saddle points of the trajectory — starting with the initial one where all parameters are zero — takes an arbitrarily long time. Similarly to Berthier [2023], Pesme and Flammarion [2023], obtaining a non-trivial limit dynamics requires a proper rescaling of time, which is given by the time acceleration t 7→ log(1/α)t. We denote the accelerated parameters by θeα (t) = θ(log(1/α)t). In the following, we omit the superscript as the acceleration by a factor 1 E.g., in PyTorch, the derivative of the ReLU non-linearity at 0 is computed as 0.
5
of log(1/α) is implicit in the tilde notation. The flow defining this rescaled process then satisfies e˙ e θ(t) ∈ − log(1/α)∂L(θ(t)) for almost all t ≥ 0.
3
Limit process
In this section, we provide intuitions for deriving the limit process of the training trajectory as α → 0. We here only provide high level insights, and proving the exact convergence results claimed here requires much more detailed and intricate analyses, that are given in the complete proof of Theorem 2. We build the saddles visited by the limit process and the corresponding jump times recursively. Assume e α→0 that θ(t) −→ θ◦ (t) for almost every t ∈ [0, tk ], where tk is a jump time, and that the limit process has reached the saddle point θ(k) after the k-th jump, i.e., θ◦ (tk ) = θ(k) . The limit process θ◦ (t) will then be constant, equal to the saddle θ(k) on an interval [tk , tk+1 ), and will jump to a new saddle θ(k+1) at a jump time tk+1 to be determined. The initial saddle point is given by θ(0) = 0. Moreover, we will also show recursively that the limit process jumps from a saddle point to another by modifying a single neuron (wj◦ , a◦j ), which is zero before jump time tk+1 , and will reach its final, non-zero value after the jump. Also, all the training points along which the neuron j is active will be fitted after the jump. During that jump, the values of all other neurons remain unchanged. In consequence, the saddle point θ(k) visited by the limit process includes two types of neurons: • unfitted neurons, which are equal to zero, i.e., (wj◦ , a◦j ) = 0; • fitted neurons, which perfectly fit the training points along which they are active: 1 wj◦ ⊤ xi > 0 (hθ(k) (xi ) − yi )2 = 0 for any i ∈ [n]. These neurons will not move further during the remainder of training. Describing the limit process then calls for describing how and when it jumps from a saddle point θ(k) to the next one θ(k+1) . For that and following the heuristics developed by Maennel et al. [2018], Kunin et al. [2025], we will decompose the tangential and radial dynamics of the parameters, using the e e e j , ℓej ) such that w reparameterization (w ej = αℓj w j . This reparameterization captures the right quantities: e j tracks the tangential while w ej is nearly zero for unfitted neurons, its renormalized counterpart w movement of the neuron, which is key to understanding the dynamics in the vicinity of each saddle. The dynamics satisfied by these parameters can then be written as follows: de de ejw e⊤ e⊤ Dj ; wj = log(1/α)sj Id − w ℓj = sj w j j Dj dt dt Around a saddle point θ(k) , note that Dj ≈ 0 for already fitted neurons, which thus do not move anymore. For unfitted neurons, the tangential movement can be seen as gradient ascent/descent of some alignment restricted on the sphere, similarly to observations made by Boursier et al. [2022], Min et al. [2024], Kumar and Haupt [2024]. Because of its log(1/α) scaling, this tangential movement thus (k) occurs instantly as α → 0, such that there exist some vectors Dj and for t ∈ (tk , tk+1 ) (k) e j (t) α→0 w −→ sj Dj . (k)
These vectors Dj correspond to the (normalized) critical points reached by the gradient ascent/descent mentioned above. In the case of orthogonal data, they are simple to compute and are actually given for unfitted neurons by 1 X (k) Dj = 1 wj (0)⊤ xi > 0 1 (sgn yi = sj ) yi xi , n (k) i∈SU
(k)
where SU is the set of training points that are not yet fitted by the network (a rigorous definition of all e j (t) ≈ sj D(k) quantities is given in Algorithm 1 below). Since we have w j , note that the time derivative 6
of the norm exponent then satisfies on (tk , tk+1 ): de (k) . ℓj ≈ Dj dt 2 Consequently, ℓej converges to a piecewise affine process ℓ◦j that starts at −1, owing to our initialization choice, and is defined recursively by: (k)
ℓ◦j (0) = −1;
ℓ◦j (t) = ℓ◦j (tk ) + (t − tk ) Dj
2
for t ∈ [tk , tk+1 ].
Moreover, the next jump happens as soon as one unfitted neuron becomes non-zero (in the limit α → 0). With our reparameterization, this occurs as soon as ℓ◦j (t) ≥ 0 for some unfitted neuron. The jump time tk+1 can then be deduced as the first time for which the exponent ℓ◦j of some unfitted neuron becomes zero, and the corresponding neuron is the one to be updated at jump time tk+1 . In other words, we have the following: (k)
• j⋆
(k)
= arg maxj ℓ◦j (tk )/ Dj
2
(k)
• tk+1 = tk − ℓ◦(k) (tk )/ D (k) j⋆
j⋆
2
is the unfitted neuron that will grow in norm;
is the jump time at which w◦(k) becomes non-zero. j⋆
At jump time tk+1 , the process then leaves the saddle θ(k) , and due to the time acceleration log(1/α), it instantaneously reaches a new critical point of the training loss. Moreover, during this instantaneous jump, only the neuron (w◦(k) , a◦(k) ) of the limit process undergoes a change: it jumps from 0 to the j⋆ j⋆ value minimizing the new training loss over this single neuron, which is given by (k)
wj◦(k) (t) = sj r ⋆
nD (k) j⋆
;
(k)
nD (k) j⋆
a◦j (k) (t) = sj ⋆
r
(k)
nD (k) j⋆
2
for t ≥ tk+1 .
2
Thanks to these high level insights, one can define formally the limit process (θ◦ (t))t≥0 in algorithm 1 below. Importantly, the while loop in algorithm 1 eventually stops after a finite number of iterations p, (p) (p) such that SU ∩ Sj = ∅ for all j ∈ NU . In the following, Assumption 4 will guarantee that we actually (p) stop when SU = ∅, which corresponds to the training loss being zero.
4
Saddle-to-saddle dynamics
In this section, we present our main result. We first require some assumptions to ensure that the network interpolates at convergence, and avoid degenerate cases in the definition of the limit process. Assumption 4. Let A ∈ {0, 1}n×m be the matrix such that Ai,j = 1 wj⊤ (0) xi > 0 and i ∈ Isj . (i) Each row of the mask matrix A is non-zero, each column is non-zero, and its columns are pairwise distinct. (ii) The training outputs (yi )ni=1 are such that they are non-zero, and in each iteration defining the limit process, the arg max in algorithm 1 line 8 is unique. We believe our main result could be extended to the case that columns are not pairwise distinct, at the expense of a more refined analysis, by merging neurons into groups with matching initial activation pattern in a similar manner to Boursier et al. [2022]: neurons which share activation patterns align and grow in the same directions throughout training, and the sum of their squared norms is equal to the squared norm achieved by a single neuron with this activation pattern. In this way, neurons sharing activation patterns form rank-1 sub-networks, so Algorithm 1 may be applied considering an aggregated collection of neurons with matching initial activation pattern as one neuron. 7
Algorithm 1 Construction of the limit process. 1: Input: data (xi , yi )i∈[n] and initial weights (wj (0), aj (0))j∈[m] . 2: ▷ Initialization (0) (0) 3: p ← 0; t0 = 0; NU = [m]; SU = [n] ⊤ 4: Sj = {i ∈ [n] | wj (0) xi > 0 and sgn(yi ) = sgn(aj (0))}; and ℓ◦ j (0) = −1 for any j ∈ [m] 5: ▷ Recursive definition of the jumps (p) (p) 6: while ∃j ∈ NU , SU ∩ Sj ̸= ∅, do ( P (p) 1 yx if j ∈ NU (p) (p) i∈SU ∩Sj i i 7: for any j ∈ [m], Dj = n (p−1) Dj otherwise 8: 9: 10:
(p)
Let j⋆
(p)
∈ arg maxj∈N (p) ℓ◦j (tp )/ Dj U
# neuron to activate
2
(p)
tp+1 = tp − ℓ◦(p) (tp )/ D (p) j⋆ j⋆ 2 (p) ◦ ◦ ℓj (tp+1 ) = min 0, ℓj (tp ) + (tp+1 − tp ) Dj (p+1) (p) (p) NU = NU \ {j⋆ }
11: 12: p ← p + 1; 13: end while 14: ▷ Definition of limit process
and
# jump time
for any j ∈ [m]
2 (p+1) (p) SU = SU \ Sj (p) ⋆
# norm exponent # unfitted neurons and data
15: Let tp+1 = +∞ by convention 16: For any k ∈ [p] and t ∈ [tk , tk+1 ), define θ ◦ (t) = (wj◦ (t), a◦ j (t))j∈[m] as (k)
for any j ∈ NU ,
(wj◦ (t), a◦j (t)) = 0;
(k) for any j ̸∈ NU ,
wj◦ (t) = sj r
(k)
nDj
(k) nDj
and
a◦j (t) = sj
r
(k)
nDj
2
.
2
17: Output: limit process (θ ◦ (t))t≥0 and jump times (t0 , . . . , tp+1 ).
The requirement that each row be non-zero ensures loss minimization. The requirement that each column be non-zero ensures that for each neuron, there exists a direction in which it can grow at initialization to reduce the loss, otherwise such neurons remain small throughout training and can be ignored. Proposition 2 below states that Assumption 4 holds with high probability in the mild log(n) overparameterization regime log(4/3) ≲ m ≪ exp (n log(2)/2). Proposition 2. Let n+ = |I+ | , n− = |I− | and consider the initialization scheme of Assumption 3. m m(m+3) 1 min(n+ ,n− )+1 − . (i) Assumption 4 (i) holds with probability at least 1 − n 43 2 2 (ii) When Assumption 4 (i) holds, the set of tuples (yi )ni=1 excluded by Assumption 4 (ii) has Lebesgue measure zero in Rn . The following result rigorously formulates the sense in which the gradient flow defined by eq. (1) converges, as the initialization scale tends to zero, to the limit process θ◦ . Theorem 2. Under Assumptions 1, 2, 3 and 4, as the initialization scale α tends to 0, the accelerated flow θeα converges to θ◦ , uniformly on every compact subset of R≥0 \ {t0 , t1 , . . . , tp }, where θ◦ and (t0 , t1 , . . . , tp ) are respectively the limit process and jump times defined in algorithm 1. Theorem 2 shows that as the initialization scale decreases, the trajectory of the parameters approximates
8
a jump process between different saddles of the loss function. As each saddle increases the rank of the network by one from the previous saddle, this result shows an example of incremental feature learning. This provides the first complete theoretical characterization of a saddle-to-saddle process in a neural network with realistic assumptions on the architecture and overparameterization. Figure 1 illustrates this convergence towards the incremental limit process θ◦ and additional experiments are provided in appendix A Instead of Assumption 4, the analysis of Boursier et al. [2022] relies on the assumption that there exist at least two neurons j+ , j− such that Ai,j+ = 1 for all i ∈ I+ and Ai,j− = 1 for all i ∈ I− . In this case, algorithm 1 reduces to just two jumps: neuron j+ grows to fit all positive labels, and neuron j− grows to fit all negative labels. Moreover, as explained in appendix D.1, these two jumps are non-interfering: the neurons fitting positive and negative labels evolve independently throughout training. Under mild overparameterization, however, the process is considerably more intricate: fitting positive (resp. negative) labels requires multiple neurons and hence multiple jumps, which may interact with one another. Our proof therefore requires a substantially finer analysis of the dynamics than that of Boursier et al. [2022]. The two main additional difficulties are the following. First, the norm growth of a given neuron exhibits memory across multiple saddles, which is controlled by the term ℓ◦j . Second, when a new neuron is activated, it may still be positively correlated with already fitted samples xi , and one must ensure that its activation does not cause the loss on these samples to increase significantly. Sketch of Proof. The result is proven by an inductive argument on the number of saddles traversed by the flow. The schematic for the proof is depicted in Figure 2 and consists of splitting the dynamics into phases around the jump from saddle k to saddle k + 1, where ε and ε′ are parameters of the proof which may be selected arbitrarily small, giving the desired uniform convergence. • Slow growth phase: For κ ∈ (tk , tk+1 ), τ1 is the first time that w ej (k) 2 = αε . We find that for ⋆ (k) t ∈ [κ, τ1 ] all neurons remain aligned in the directions D . Hence, ℓej increases towards 0 for all j
(k) j ∈ NU , but θe does not change significantly and remains near saddle k until any κ′ ∈ (τ1 , tk+1 ). 2
(k)
′
• Rapid fitting phase: τ3 is the first time that w ej (k) 2 = n D (k) 2 − αε /4 for a small enough ε′ . We j⋆
⋆
(k)
show τ3 − τ1 = O(ε, ε′ ) through checking w ej (k) continues to grow at an exponential rate D (k) 2 by j⋆
⋆
(k)
neither realigning in span(xi | i ∈ SF ). To show this we employ two techniques: first, we split the phase in two, defining τ2 as the first time w ej (k) 2 = η for some convenient η, as having a stronger ⋆
(k)
(k)
bound on neuron j⋆ helps control the loss on fitted data; second, we estimate how much neuron j⋆ (k) realigns in span(xi | i ∈ SF ) in terms of the loss on this data, and then in turn show wj (k) remains ⋆
(k)
aligned in direction D (k) on [τ1 , τ3 ]. j⋆
(k+1)
• Realignment and slow growth: The unfitted neurons j ∈ NU
respond to the change in gradients (k+1)
due to a new set of data being fitted by realigning rapidly in direction Dj which time this alignment remains stable until any time κ′′ ∈ (tk+1 , tk+2 ).
5
by some time τ4 , after
Implicit bias
Boursier et al. [2022] proved that gradient flow converges to a minimum ℓ2 -norm interpolator θopt as the initialization scale tends to zero, which is equivalent to the sum of two neurons that respectively fit the positive and negative labels. However, this norm optimality relies on a specific initialization condition, that assumes that at least one neuron is active along all positively labeled data and another neuron is active along all negatively labeled data. Such a condition only realistically holds in a heavily 9
Slow growth tk κ
κ′
O(ε′ )
O(ε)
Θ(1)
Fast growth τ1
τ2 tk+1
O(ε)
Θ(1)
Realignment
Slow growth
τ3
τ4
κ′′ tk+2
Figure 2: Timeline of the training dynamics about the jump from saddle k to saddle k + 1. The quantities (k) ε and ε′ are parameters of the proof of Theorem 2, τ1 is the beginning of the fast growth of neuron j⋆ , (k) τ3 is the time by which neuron j⋆ has grown to its final norm, and τ4 is the time by which neurons (k+1) in the set NU have realigned. The quantities κ, κ′ , and κ′′ can be viewed as fixed for the proof of convergence. overparameterized regime with m ≳ 2n . Boursier et al. [2025] then proved in a later work that with high probability in the mild overparameterization regime (m ≲ 2n ), gradient flow does not converge towards a minimal ℓ2 -norm interpolator as the initialization scales goes to 0. We yet prove in this section that with mild overparameterization, Algorithm 1 produces with high probability an interpolator that is only larger in ℓ2 -norm than the optimal one by a constant multiplicative factor. We denote in the following by θpred the limiting parameters θ◦ (t) for any t ≥ tp —the definition is independent of the choice of t > tp , thanks to Theorem 2—and by θopt any minimum ℓ2 -norm interpolator. The squared ℓ2 -norms of these parameters are given by 1 ∥θopt ∥22 = 2
s X i | yi >0
yi2 +
s X
yi2
and
i | yi <0
X 1 (p) ∥θpred ∥22 = n Dj . 2 2
(2)
j∈[m]
(p)
where the last jump of the limit process p and Dj are all defined in Algorithm 1. Theorem 3 below upper bounds the norm of the learned interpolator in the mild overparameterization regime as the initialization scale goes to 0. Theorem 3. Let n+ = |I+ |, n− = |I− |, and n̄ = min(n+ , n− ). Under Assumptions 1 and 3, if log(m) = o(n̄1/8 / log(n̄)), then the final output of Algorithm 1 satisfies 1 √ √ ∥θpred ∥22 ≤ 5 n+ + n− max |yi |, 2 i∈[n] with probability at least 1 − exp(−Ω(n̄1/8 )) over the network initialization. Theorem 3 implies that, in the presence of uniformly √ bounded labels, the achieved interpolator in the mild overparameterization regime as α → 0 scales as n. Although this interpolator is not minimal in √ norm, it recovers the n scaling of ∥θopt ∥22 , thanks to Equation (2). Also note that thisp type of bound could be easily extended to random labels, replacing the maxi∈[n] |yi | term by maxi∈[n] E[yi2 ] for, e.g., sub-Gaussian labels. Theorem 3 does not require any lower bound on m as Algorithm 1 is still defined in that case. However, m must be of order at least log(n) to ensure that the achieved estimator interpolates the data, which is guaranteed by Item (i) Assumption 4. The proof of Theorem 3 reflects the incremental nature of Algorithm 1. Each newly added positive (resp. negative) neuron approximately fits half of the remaining positive (resp. negative) labels. Consequently, after about log(n) increments, nearly all data points are fitted. The proof relies on a union bound over all subsets of the first log(n) neurons used to construct the estimator. This approach does not depend on the specific order induced by Algorithm 1. As a result, the bound in Theorem 3 does not capture how 10
the norm of the interpolator decreases as the number of neurons m grows. Establishing such a result remains open, as it would require a more refined analysis that accounts for dependencies between the successive increments in Algorithm 1.
6
Conclusion
In this work, we have provided a complete analysis of the gradient flow dynamics of mildly overparameterized two-layer ReLU networks from small initialization in the special case of orthogonal data. In doing so, we have extended existing convergence results and shown an incremental learning phenomenon. There are several avenues for future research. It would be valuable to extend the proof of saddle-tosaddle dynamics to more general data distributions. Possibilities could include weakly interacting data [Dana et al., 2025] or clustered data with orthogonal centers [Min and Vidal, 2025]. Such work could shed light on incremental learning in more realistic settings. In Theorem 3 on the implicit bias, there is no reference to the width except in the restriction log(m) = o(n̄1/8 / log(n̄)). Future work could seek to precisely quantify the dependence of the learned norm on the network width as one approaches the regime m = exp(n). Doing so would require a more intricate analysis of the dependence of each stage of Algorithm 1 on those that preceded it, which could be of independent interest in analyzing similar sequential algorithms. Acknowledgments and Disclosure of Funding The authors are thankful to Nikolaos Zygouras for insightful discussions. The authors acknowledge the Engineering and Physical Sciences Research Council (EPSRC) and DIMAP research centre at the University of Warwick for partial support. J. Town is supported by the EPSRC through the Mathematics of Systems II Centre for Doctoral Training at the University of Warwick (reference EP/S022244/1). B. Lewis is supported by the EPSRC studentship 2927289. The authors acknowledge the use of the Batch Compute System in the Department of Computer Science at the University of Warwick, and associated support services, in the completion of this work.
References Emmanuel Abbe, Enric Boix Adserà, and Theodor Misiakiewicz. SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics. In COLT, pages 2552–2623, 2023. 3 Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization. In ICML, pages 244–253, 2018. 2 Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit Regularization in Deep Matrix Factorization. In NeurIPS, pages 7411–7422, 2019a. 2 Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. In ICML, pages 322–332, 2019b. 1 Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron C. Courville, Yoshua Bengio, and Simon Lacoste-Julien. A Closer Look at Memorization in Deep Networks. In ICML, pages 233–242, 2017. 2 Jean-Pierre Aubin and Arrigo Cellina. Differential Inclusions: Set-Valued Maps and Viability Theory. Springer, 1984. 20 Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake E. Woodworth, Nathan Srebro, Amir Globerson, and Daniel Soudry. On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent. In ICML, pages 468–477, 2021. 5
11
Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. SIMODS, 6(1):26–50, 2024. 4 Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias–variance trade-off. Proc. Natl. Acad. Sci., 116(32):15849–15854, 2019. 4 Mikhail Belkin, Daniel Hsu, and Ji Xu. Two Models of Double Descent for Weak Features. SIAM J. Math. Data Sci., 2(4):1167–1180, 2020. 4 Raphaël Berthier. Incremental Learning in Diagonal Linear Networks. J. Mach. Learn. Res., 24(171):1–26, 2023. 3, 5 David Bertoin, Jerome Bolte, Sébastien Gerchinovitz, and Edouard Pauwels. Numerical influence of ReLU’(0) on backpropagation. In NeurIPS, 2021. 5 Etienne Boursier and Nicolas Flammarion. Penalising the biases in norm regularisation enforces sparsity. In NeurIPS, 2023. Also in CoRR abs/2303.01353, which contains a correction to Theorem 4. 2 Etienne Boursier and Nicolas Flammarion. Early Alignment in Two-Layer Networks Training is a Two-Edged Sword. J. Mach. Learn. Res., 26:183:1–183:75, 2025a. 2 Etienne Boursier and Nicolas Flammarion. Simplicity bias and optimization threshold in two-layer ReLU networks. In ICML, 2025b. 27 Etienne Boursier, Loucas Pillaud-Vivien, and Nicolas Flammarion. Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs. In NeurIPS, 2022. 2, 3, 5, 6, 7, 9 Etienne Boursier, Matthew Bowditch, Matthias Englert, and Ranko Lazić. Benignity of loss landscape with weight decay requires both large overparametrization and initialization. CoRR, abs/2505.22578, 2025. 4, 10 François Charton. Learning the greatest common divisor: explaining transformer predictions. In ICLR, 2024. 3 Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, Rohan Anil, Zakaria Haque, Lichan Hong, Vihan Jain, Xiaobing Liu, and Hemal Shah. Wide & Deep Learning for Recommender Systems. In DLRS, pages 7—-10, 2016. 1 Dmitry Chistikov, Matthias Englert, and Ranko Lazić. Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs. In NeurIPS, 2023. 3 Lénaïc Chizat and Francis R. Bach. On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport. In NeurIPS, pages 3040–3050, 2018. 2 Lénaïc Chizat and Francis R. Bach. Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss. In COLT, pages 1305–1338, 2020. 2 Lénaïc Chizat, Edouard Oyallon, and Francis R. Bach. On Lazy Training in Differentiable Programming. In NeurIPS, pages 2933–2943, 2019. 1 Frank H. Clarke. Generalized gradients and applications. Trans. Amer. Math. Soc., 205:247–262, 1975. 4, 19 Léo Dana, Francis R. Bach, and Loucas Pillaud-Vivien. Convergence of Shallow ReLU Networks on Weakly Interacting Data. In NeurIPS, 2025. 1, 2, 3, 4, 11 Simon S. Du, Wei Hu, and Jason D. Lee. Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced. In NeurIPS, pages 382–393, 2018. 5 Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient Descent Provably Optimizes Overparameterized Neural Networks. In ICLR, 2019. 1 Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M. Roy, and Surya Ganguli. Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernel. In NeurIPS, 2020. 1
12
Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien. Implicit regularization of discrete gradient dynamics in linear neural networks. In NeurIPS, 2019. 3 Margalit Glasgow. SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem. In ICLR, 2024. 3 Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS, pages 249–256, 2010. 5 Micah Goldblum, Marc Anton Finzi, Keefer Rowan, and Andrew Gordon Wilson. Position: The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning. In ICML, pages 15788–15808, 2024. 4 Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. Ann. Stat., 50(2):949–986, 2022. 4 Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification. In ICCV, pages 1026–1034, 2015. 19 David Holzmüller and Ingo Steinwart. Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent. J. Mach. Learn. Res., 23(181):1–82, 2022. 2 Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In NeurIPS, pages 8580–8589, 2018. 1 Arthur Jacot, François Ged, Berfin Şimşek, Clément Hongler, and Franck Gabriel. Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity. CoRR, abs/2106.15933, 2021. 3 Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. In NeurIPS, 2020. 2 Jikai Jin, Zhiyuan Li, Kaifeng Lyu, Simon S. Du, and Jason D. Lee. Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing. In ICML, pages 15200–15238, 2023. 3 Akshay Kumar and Jarvis Haupt. Directional Convergence Near Small Initializations and Saddles in TwoHomogeneous Neural Networks. TMLR, 2024. 6 Daniel Kunin, Giovanni Luca Marchetti, Feng Chen, Dhruva Karkada, James B Simon, Michael R DeWeese, Surya Ganguli, and Nina Miolane. Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networks. In NeurIPS, 2025. 3, 6 Zhenyu Liao, Romain Couillet, and Michael W. Mahoney. A random matrix analysis of random Fourier features: beyond the Gaussian kernel, a precise phase transition, and the corresponding double descent. In NeurIPS, 2020. 4 Yaron Lipman, Ricky T. Q. Chen, Heli Ben-Hamu, Maximilian Nickel, and Matthew Le. Flow Matching for Generative Modeling. In ICLR, 2023. 1 Kaifeng Lyu and Jian Li. Gradient Descent Maximizes the Margin of Homogeneous Neural Networks. In ICLR, 2020. 2, 20 Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias. In NeurIPS, pages 12978–12991, 2021. 3 Wesley J. Maddox, Gregory W. Benton, and Andrew Gordon Wilson. Rethinking Parameter Counting in Deep Models: Effective Dimensionality Revisited. CoRR, abs/2003.02139, 2020. 4 Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly. Gradient Descent Quantizes ReLU Network Features. CoRR, abs/1803.08367, 2018. 6 Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Commun. Pure Appl. Math., 75(4):667–766, 2022. 4
13
Hancheng Min and René Vidal. Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs. In ICML, 2025. 11 Hancheng Min, Enrique Mallada, and René Vidal. Early Neuron Alignment in Two-layer ReLU Networks with Small Initialization. In ICLR, 2024. 3, 6 Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge University Press, 2nd edition, 2017. 60 Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang, Benjamin L. Edelman, Fred Zhang, and Boaz Barak. SGD on Neural Networks Learns Functions of Increasing Complexity. In NeurIPS, pages 3491–3501, 2019. 2 Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep Double Descent: Where Bigger Models and More Data Hurt. In ICLR, 2020. 4 Scott Pesme and Nicolas Flammarion. Saddle-to-Saddle Dynamics in Diagonal Linear Networks. In NeurIPS, 2023. 3, 5 Mary Phuong and Christoph H. Lampert. The inductive bias of ReLU networks on orthogonally separable data. In ICLR, 2021. 3 Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred A. Hamprecht, Yoshua Bengio, and Aaron C. Courville. On the Spectral Bias of Neural Networks. In ICML, pages 5301–5310, 2019. 3 Itay Safran, Gal Vardi, and Jason D. Lee. On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias. In NeurIPS, 2022. 2 Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In ICLR, 2014. 2 Mingze Wang and Chao Ma. Understanding Multi-phase Optimization Dynamics and Rich Nonlinear Behaviors of ReLU Networks. In NeurIPS, 2023. 3 Andrew Gordon Wilson. Position: Deep Learning is Not So Mysterious or Different. In ICML, pages 82326–82346, 2025. 4 Stephan Wojtowytsch. On the Convergence of Gradient Descent Training for Two-layer ReLU-networks in the Mean Field Regime. CoRR, abs/2005.13530, 2020. 2 Blake E. Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and Rich Regimes in Overparametrized Models. In COLT, pages 3635–3673, 2020. 2 Sergey Zagoruyko and Nikos Komodakis. Wide Residual Networks. In BMVC, 2016. 1
14
Appendix Table of contents A Experiments 15 A.1 Experimental details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 A.2 Additional experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 B Technical background 19 B.1 Clarke subdifferential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 B.2 Time rescaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 C Recap of notations
20
D Proof of Theorem 2 D.1 Basis case and autonomous systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.2 Phase 1: Slow growth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.3 Phase 2a: Growth to constant order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.4 Phase 2b: Fitting of data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.5 Phase 3: Realignment and slow growth . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.6 Final Saddle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.7 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20 22 27 34 43 48 55 57
E Proof of Theorem 3
58
F Auxiliary results 62 F.1 Proof of Proposition 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 F.2 Other auxiliary results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
A
Experiments
A.1
Experimental details
fig. 1 was generated by training a two-layer ReLU network with six neurons on 64 orthonormal data points in 64 dimension. The labels are chosen as the absolute values of standard Gaussian random variables. As explained in appendix D.1, without the sign restriction on the labels, we get two independent processes: neurons with negative output weights will turn and stay in the subspace orthogonal to the space spanned by the data points with positive labels, and vice versa. The sign restriction on the labels therefore helps to more clearly illustrate one of these processes in the plots, as opposed to a loss curve that is the combination of interleaving these two independent processes. The network weights are initialized such that the hidden layer neurons have random directions and ℓ2 norm e−500 and the output weights are e−500 . To avoid numerical issues, we maintain a scaled version of the weights such that they are closer to 1 (i.e., initially scaled by e500 ) and separately track the logarithm of the scale of the weights (initially −500). During training, the stored weights are kept near 1 while the logarithm of the scale is adjusted. The loss is the mean squared error and we train the network with full batch gradient descent and a learning rate of 0.01 until the loss is less than 10−20 . The plots in fig. 1 start at epoch ≈ 0.9 · t1 , For the purposes of the illustration, we consider a data point fitted when the output of the network for that point is at least 50% of the corresponding label. Due to the exponential growth of neuron norms, once the output of a network for a data point reaches such a
15
Neuron norm
100 10−15 10−30 10−45 10−60
t1
t2
t3
t4
t5
t6
Figure 3: The same as the right plot of fig. 1 but with the y-axis on a logarithmic scale. The neuron norms increase exponentially. When new data points are fitted, the rate of this exponential increase reduces for the remaining neurons that were active on at least one of those newly fitted data points. significant proportion of the label, the output of the network at the data point very rapidly closes in on the label value. Therefore, the exact choice of the threshold (here 50%) is somewhat arbitrary but also immaterial in the sense that it does not greatly influence the general picture.
A.2
Additional experiments
For the same training as in fig. 1, fig. 3 shows how the ℓ2 norms of the hidden layer neurons change over time, but with a logarithmic y-axis. This reveals that the norms grow at an exponential rate. At the jump times, when a neuron fits the data on which it is active, that neuron stops growing. Other neurons continue to grow. However, if they were active on some of the same data points as the newly fitted neuron, they are now growing at a slower exponential rate than before the jump time. Therefore, the logarithms of the neuron norms are piecewise linear curves with decreasing slopes. The slopes of these linear segments as well as the jump times are predicted by algorithm 1. Specifically, between jump (p)
times tp and tp+1 , the slope for neuron j is proportional to Dj
2
.
Still for the same training, fig. 4 shows the norm (on a logarithmic scale) and direction (projected onto a random two-dimensional plane) of the six neurons at different points in time. Initially, the norms are very small. The neurons orient themselves in the directions predicted by algorithm 1 and their norm starts to increase exponentially. Just before time t1 , one neuron has a significant norm while the remaining neurons have norms that are still much smaller. Just after time t1 , the neuron directions predicted by algorithm 1 change and the neurons that did not fit any data yet turn quickly towards their new predicted directions. Time t1 approximately corresponds to epoch 507,000. Plot (c) shows the process at epoch 506,000, plot (d) shows it at epoch 508,000, plot (e) shows it at epoch 510,000, and plot (f) shows it at epoch 538,000. Norm minimization. Theorem 3 gives an upper bound on the squared ℓ2 norm of the parameters of the achieved interpolator √ in the mild overparameterization regime. For uniformly bounded labels, this bound is of the order n and therefore of the same order as the minimum norm interpolator. fig. 5 experimentally shows the growth of the squared norm of the parameters of the achieved interpolator versus that of the optimal interpolator, depending on the number n of data points. Specifically, we train a two-layer ReLU network with full batch gradient descent and a learning rate of 0.5. For different n, a network of width m = ⌈ln(10000 · n)/ ln(4/3)⌉ is initialized such that the hidden 16
(a) Near the start
(b) Around time t1 /2
(c) Just before time t1
(d) Just after time t1
(e) A short while after t1
(f) Around time (t1 + t2 )/2
Figure 4: For the same training as in fig. 1, these polar plots show the norm of each neuron (on a logarithmic scale) as well as the direction of the neuron projected onto a random two-dimensional plane, at different points in time. The projections of the neuron directions from the limit process θ◦ (t) predicted by algorithm 1 are indicated by dashed lines.
17
Squared norm
103
achieved squared norm of parameters optimal squared norm of parameters
102
101
102
103
104
105
n Figure 5: We train a two-layer ReLU network with increasing data dimensionality and number of data points n, and plot the square of the norm of of the parameters of the final network as well as that of the optimal interpolator (see eq. (2)). The hidden layer size m increases logarithmically in n, and we use a √ balanced initialization of scale 10−30 / m. Each value plotted is the mean over three runs, with each run using fixed orthogonal inputs and different random labels which are standard Gaussians. We use full batch gradient descent with a learning rate of 0.5 for one million epochs or until the loss reaches 10−10 . The area between the minimum and maximum values is shaded, however they are relatively concentrated. √ neurons have random directions and norm 10−30 / m and the output neurons have a random sign and √ absolute value 10−30 / m. The choice of m ensures that there √ are a sufficient number of neurons to ensure interpolation in a typical training run. The factor 1/ m in the initialization scale ensures that the initial squared norm of the network parameters remains the same regardless of the width of the network. The network is trained on data points corresponding to the n × n identity matrix and labels are drawn from a standard Gaussian distribution. The identity matrix is chosen for computational and memory efficiency, but we note that the training dynamics are rotation invariant and therefore the behavior for the identity matrix is the same as for any other orthonormal basis. Training is run for one million epochs but stopped earlier if the loss reaches 10−10 . We record the squared norm of the parameters of the final network. This is repeated three times with new random initial weights. In fig. 5, we plot the mean values of the squared norms as well the the optimum squared norm ∥θopt ∥22 (see eq. (2)). We also indicate the min/max deviation over the three runs, but this is barely visible due to relatively low variance of the resulting squared norms. In the plot, both axes are logarithmic. The √ straight lines of slope about 1/2 therefore indicate that both squared norms grow proportional to n and that the achieved squared norm is only by a constant factor larger than the optimal one. Larger overparameterization. Our next experiment investigates what happens when we increase the overparameterization for two different initialization schemes. The first initialization scheme is the same as before used √ to produce fig. 5 (i.e., balanced small initialization with hidden layer neuron norms equal to 10−30 / m). The second scheme is a uniform initialization which in our network draws hidden √ He √ layer weights uniformly at random from [−1/ d, 1/ d] and output layer weights uniformly at random √ √ from [−1/ m, 1/ m]. This is the default initialization for linear layers in PyTorch. The experimental details are the same as before, except that n is now fixed at 32 while m is varied and the learning rate is
18
Squared norm
102
101.5
102
103
104
105
m achieved squared norm of parameters (He initialization) achieved squared norm of parameters (small initialization) optimal squared norm of parameters Figure 6: We train two-layer ReLU networks of varying widths m on 32 orthonormal data points in 32 dimensions and labels drawn from the standard Gaussian distribution. We compare √ two initialization schemes: balanced small initialization where hidden neurons have norm 10−30 / m and uniform He initialization [He et al., 2015], which is the default used in PyTorch to initialize linear layers. We train using full batch gradient descent for one million epochs or until the loss reaches 10−10 . Each value plotted is the mean over three runs with new random initial weights. The area between the minimum and maximum values is shaded, however they are relatively concentrated. 1 when using the first initialization scheme and 0.001 when using the second initialization scheme. Each point in the plot of fig. 6 is the mean of three runs with different random initial weights. We also indicate the min/max deviation over the three runs, but this is barely visible due to relatively low variance of the resulting squared norms. We observe that with small initialization, the square ℓ2 norm of the trained network approaches the theoretical optimum as the width of the network increases. This is in contrast to the uniform He initialization, for which the square ℓ2 -norm of the trained network keeps increasing. Compute. The experiment for figs. 1, 3 and 4 takes only about one minute to generate on a standard desktop CPU. Generating fig. 5 takes about 3 hours, and generating fig. 6 takes about 10 minutes, both on a consumer GPU.
B
Technical background
B.1
Clarke subdifferential
We introduce the Clarke subdifferential [Clarke, 1975] and a basic result on the existence of gradient flows using this generalized derivative. Definition 1. The Clarke subdifferential of a locally Lipschitz function f : X → R at the point x ∈ X is defined as the convex set 19
∂f (x) = conv
lim ∇f (xk ) xk → x, f is differentiable at xk .
k→∞
One may see Lyu and Li [2020, Section 3] for further details. We present the following result guaranteeing the local existence of solutions. Theorem 4. [Aubin and Cellina, 1984, Theorem 3, Chapter 2] Let X be a Hilbert space and Q ⊂ R × X be an open subset containing (0, x0 ). Let F be an upper semicontinuous map from Q into the non-empty closed convex subsets of X . We assume that (t, x) 7→ m(F (t, x)) is locally compact, where for A ⊂ X we define m(A) := inf{∥v∥ | v ∈ A}. Then there exist T > 0 and an absolutely continuous function x(·) defined on [0, T ], a solution to the differential inclusion x′ (t) ∈ F (t, x(t));
B.2
x(0) = x0 .
Time rescaling
We provide here some intuition for why it is necessary to rescale time in order for dynamics to occur on a finite timescale as the initialization scale decreases to 0. Fundamentally, it is because gradients become small in the vicinity of critical points and so the dynamics slow down. Note that near to a critical point we may linearize a dynamical system. In the case that this critical point is the origin, which will already give the required scaling to have non-trivial dynamics, we obtain θ̇ ≈ −∇2 L(0)θ, where ∇2 denotes the Hessian. The solution to the linearized dynamics is given by θ(t) = θ(0) exp(−∇2 L(0)t). We can obtain a lower bound on the change in θ by projecting onto the eigenvectors of the Hessian which correspond to positive eigenvalues and assuming the slowest growth rate applies to all these components (i.e., take the smallest positive eigenvalue). Assuming the fastest growth rate in all components (i.e., take the largest positive eigenvalue) will give an upper bound. Concretely, taking min max norms gives ∥P⊥ t) where λmin + θ(0)∥ exp(λ+ t) ≤ ∥θ(t)∥ ≤ ∥θ(0)∥ exp(λ + is the smallest positive 2 max ⊥ eigenvalue of −∇ L(0), λ is the largest eigenvalue, and P+ is the orthogonal projection onto the span of eigenvectors of −∇2 L(0) which correspond to positive eigenvalues. Based on these linearized dynamics, we expect that the escape time, Te , for ∥θ(t)∥ to reach some constant C obeys the bounds 1 1 1 ≤ T ≤ log(C) + log log(C) + log . e λmax ∥θ(0)∥ ∥P⊥ λmin + θ(0)∥ + 1
Supposing that ∥θ(0)∥, ∥P⊥ + θ(0)∥ ∼ α, we see that the required rescaling of time is t 7→ log(1/α)t, as claimed, and we denote the accelerated parameters by θeα (t) = θ(log(1/α)t). Typically, we omit the superscript as the acceleration by a factor of log(1/α) is implicit in the tilde notation. As noted in the ˙ e e main body of the paper, the flow defining this rescaled process is simply θ(t) ∈ − log(1/α)∂L(θ(t)) for almost all t ≥ 0.
C
Recap of notations
For ease of reference, Table 1 collects notation used throughout the paper, including some symbols that appear only in the appendix.
D
Proof of Theorem 2
The proof convergence to the limit process defined in Algorithm 1 is due to a non-asymptotic analysis of the dynamics of all neurons around the jump from saddle k to saddle k + 1. We use this to construct 20
Table 1: Definitions and descriptions of named quantities, collected here from the text. Hyperlinks in the Symbol column take the reader to the first point in the paper where a given symbol is introduced. Symbol
Definition
Description
Is
{i ∈ [n] | sgn(yi ) = s}
The set of data i with sign s, for s ∈ {±1}.
Ai,j
1 wj⊤ (0) xi > 0 and i ∈ Isj
Js
{j ∈ [m] | sgn(aj (0)) = s}
The set of data i on which, at initialization, neuron j is active with correct second-layer weight sign.
The set of neurons j with sign s, for s ∈ {±1}.
t0 = 0
◦ ℓj (tk ) tk+1 = min tk − (k) (k) j∈NU D
tk
The jump times.
j
ℓ◦j (t)
ℓ◦j (0) = −1 ℓ◦j (t) = min
(k) ℓ◦j (tk ) + (t − tk )∥Dj ∥, 0
(k) j⋆
ℓ◦j (tk ) arg min tk − (k) (k) D j∈N
The neuron which fits when moving from saddle k to saddle k + 1.
(0) NU = [m] (k+1) (k) NU = NU \ {j ⋆ }
The set of unfitted neurons at saddle k.
j
U
(k)
NU
(k)
(k)
NF
The set of fitted neurons at saddle k.
[m] \ NU (0)
Sj (k)
Sj
The exponents of the neurons’ norms, where t ∈ [tk , tk+1 ].
= Sj = {i ∈ [n] | Ai,j = 1} (k) S (k) \ S (k) if j ̸= j⋆ (k) j (k+1) j⋆ Sj = (k) S (k) if j = j⋆ j
The set of unfitted data on which neuron j is active with correct second-layer weight at saddle k, and which has not yet been fitted by any other neuron.
(0)
(k)
SU
SU = [n] (k+1)
SU
(k)
(k)
The set of unfitted data at saddle k.
(k)
(k)
SF Dj
(k)
= SU \ Sj ⋆
The set of fitted data at saddle k.
[n] \ SU (k)
Dj
=
The label-weighted sum of data in the (k) set Sj , which is the direction in which neuron j aligns and grows at saddle k.
1 X yi xi n (k) i∈Sj
E (k)
1 X E (k) = − (h e(xi ) − yi )xi n (k) θ
A dynamical vector encoding the loss on data which has already been fitted, 2 with n E (k) directly corresponding to these terms of the loss.
1 X Dj = − (hθe(xi ) − yi )xi n
A dynamical vector encoding the loss on all data on which neuron j is active, with n∥Dj ∥2 directly corresponding to these terms of the loss.
i∈SF
Dj
i∈[n] | wj⊤ xi >0
21
an inductive argument for convergence, with the number of saddles traversed by the flow serving as the parameter of the induction. Specifically, we will assume the following inductive hypothesis on convergence at saddle k: Hypothesis 1 (for k ∈ {0, 1, . . . , p}). Given any κ ∈ (tk , tk+1 ), there exists δ > 0 such that for all ξ > 0, there exists α∗ > 0 such that for all α ∈ (0, α∗ ): (k)
1. ∀j ∈ NU , ℓ◦j (κ) + logα (∥w ej (κ)∥) < ξ. (k)
(k)
2. ∀j ∈ NF , n Dj
− ∥w ej (κ)∥2 < αδ .
(k)
3. ∀i ∈ SF , |hθ(κ) (xi ) − yi | < αδ . e ⊤
(k)
e j (κ)Dj 4. ∀j ∈ [m], w
> 1 − αδ .
In the above, and throughout the proof, we use ∥·∥ to denote the ℓ2 -norm. The reader should note that δ depends on κ in Hypothesis 1; in particular we have limκ→0 δ = 0. This does not present a problem, p since the proof is of convergence on compact subsets of R which exclude (tk )k=1 . Therefore, κ may be viewed as a quantity which is fixed at the beginning of the proof depending on the compact set in question. The following lemma states that on compact intervals not containing a jump time, we have the desired uniform convergence to the limit process under Hypothesis 1. Lemma 1. Suppose that Hypothesis 1 holds for some k ∈ 0, 1, . . . , p − 1. Then given any κ, κ′ > 0 such that tk < κ < κ′ < tk+1 , θeα converges uniformly to θ◦ on [κ, κ′ ]. The following lemma recovers Hypothesis 1 at saddle k + 1. Lemma 2. If Hypothesis 1 holds for some k ∈ {0, 1, . . . , p − 1}, then it holds for k + 1. Each of these lemmas, as well as the final proof of Theorem 2, are provided in Appendix D.7. We deal with the final saddle separately in Appendix D.6 because, although the arguments for uniform convergence on closed intervals contained in (tp , ∞) are essentially the same as those for k < p, it is simpler to account for this case separately.
D.1
Basis case and autonomous systems
We provide here an analysis of the early time dynamics, specifically a proof of the alignment of neurons (0) towards the directions Dj by an arbitrary positive time, where (0)
Dj
:=
1 X Ai,j yi xi , n i∈[n]
and we recall that Ai,j = 1 wj⊤ (0) xi > 0 and i ∈ Isj . This will amount to a proof of a statement similar to the case k = 0 for Hypothesis 1. At this point, it will also be helpful to introduce the vector (k)
Dj
:=
1 X yi xi . n (k) i∈Sj
22
(k)
In the above display, Sj
is recursively defined by (0)
Sj
= {i ∈ [n] | Ai,j = 1} (k) S (k) \ S (k) if j ̸= j⋆ (k) j (k+1) j⋆ Sj = (k) S (k) if j = j⋆ j and denotes the set of data on which neuron j is active at saddle k and on which no neuron in the set (k)
(k)
NF := [m] \ NU
(0)
is active. Note that Sj (as introduced in Algorithm 1) is the same set as Sj . In a similar way to how we define the set of neurons which have fitted their data, we can also define the set of fitted data itself by (k)
(k)
SF := [n] \ SU . (k)
(k)
One may see Algorithm 1 for the construction of the sets NU and SU . Our arguments will use the equations
e a˙ j = log(1/α)w ej⊤ Dj
w e˙ j = log(1/α)e aj Dj ,
where we have Dj = −
1 n
X
(hθe(xi ) − yi )xi .
i∈[n] | w ej⊤ xi >0
As noted in section 2, these equations combined with Proposition 1 and Assumption 2 imply that e j (t)w e⊤ e˙ j (t) = sj log(1/α) Dj (t) − w w (t)D (t) . j j Using these equations, we will ensure that by an arbitrary time κ > 0, all neurons have aligned towards (0) the directions Dj . Furthermore, we will verify by introducing an auxiliary parameter of the proof, κ b, that −ℓej (κ) ≈ −ℓ◦j (κ) with arbitrary precision. The sketch of the proof is to ensure that by any time κ b > 0, the realignment has occurred and then remains stable until time κ. Therefore, the precision of the exponents of the unfitted neurons is controlled by the arbitrary parameter κ b. To state the lemma below, we define for s ∈ {±1} the set of neurons with output sign given by s: Js := {j ∈ [m] | sgn(aj (0)) = s}. q 1 n Lemma 3. For any κ ∈ 0, 4 2L(0) there exists δ > 0 such that for any ξ > 0 there exists α∗ (κ, ξ) > 0 such that for all α ∈ (0, α∗ ) and both signs s ∈ {±1} the following are true: (0) δ e⊤ 1. ∀j ∈ Js , sj w j (κ)D j > 1 − α .
2. ∀j ∈ Js , ∀t ∈ (0, κ), ℓ◦j (t) + logα (∥w ej ∥) < ξ .
23
3. ∀i ∈ I−s , ∀j ∈ Js , w ej⊤ (κ)xi ≤ 0. The monotonicity of the gradient flow means there exists a maximum rate of growth it is possible for any neuron to achieve. Therefore, the upper bound on κ appears as a technicality to ensure that even if a neuron were to have grown at this maximum rate from initialization, it could not have exceeded the threshold α1/2 which we introduce for the purpose of the proof. This kind of argument will be used several times throughout subsequent analyses (see Proposition 3 and its application in the proof of Lemmas 4 to 7). Item 3 Lemma 3 is a particularly important point, because it ensures that neurons deactivate within an arbitrarily short length of time on the data for which Ai,j = 0. Combining this with Assumption 2 will allow us to see that the network splits into two sub-networks, consisting only of neurons with positive (resp. negative) second-layer weight and which are active on data with only positive (resp. negative) labels. This allows us to consider w.l.o.g. the case that sj > 0 for all j ∈ [m] and sgn(yi ) > 0 for all i ∈ [n]. This is explained more precisely after the proof. We stress now that the statement of Lemma 3 does not exactly correspond to the statement of Hyq n pothesis 1, since the interval 0, 41 2L(0) does not correspond to the interval (0, t1 ). However, when uniform convergence to θ◦ is proven, we will apply Lemma 1, and this statement is sufficient to obtain uniform convergence on arbitrary closed intervals contained in (0, q t1 ). Concretely, if we were to con1 n sider a compact set partially or entirely contained in 4 2L(0) , t1 , we could obtain convergence by q 1 n applying Lemma 1 on some interval whose lower endpoint is contained in 0, 4 2L(0) and whose upper endpoint is greater than the maximum of the compact set. ej ∥ ≥ α1/2 }. As a preliminary, we check that κ < τ . On Proof. Define τ := inf{t ≥ 0 | ∃ j ∈ [m] s.t. ∥w [0, τ ],
1 d ∥w ej ∥ ∥w ej ∥ = − log(1/α) dt n r ≤
e⊤ (hθe(xi ) − yi )w j xi
X
(3)
i∈[n] | w ej⊤ xi >0
2L(0) ∥w ej ∥. n
This follows from the Cauchy-Schwarz inequality combined with the fact that L is monotone decreasing, by definition of the gradient flow. Grönwall’s inequality gives that on this interval,
∥w ej (t)∥ ≤ ∥w ej (0)∥α− = α1−
q
q
2L(0) t n
2L(0) t n
.
q where the second inequality is valid for α sufficiently small. Since κ < 41 2L(0) n t, we indeed have κ < τ . We may reverse the inequality and consequently obtain for t ∈ [0, τ ] the lower bound q
∥w ej (t)∥ > α1+ We conclude that for t ∈ [0, κ] 24
2L(0) t n
.
q
α1+
2L(0) t n
< ∥w ej (t)∥ < α1−
q
2L(0) t n
.
(4)
Observe at this point that the signs are symmetric, and so we prove w.l.o.g. the statements for sj = 1. Proof of Item 1. For the claimed alignment, we compute that
⊤ 2 2 1 d e ⊤ (0) (0) e j Dj(0) − w wj Dj ≥ Dj log(1/α) dt X 1 (0) ⊤ e e ⊤ (0) hθe(xi ) x⊤ − i Dj − xi w j w j Dj n ⊤ i|w ej xi >0
(0)
> Dj
2
⊤ 2 e j Dj(0) − 2m Dj(0) α, − w
where the first inequality is from discarding negatively labeled data on which neuron j is active. This is because such data add a positive contribution for α small enough that |hθe(xi )| < |yi |. We then use the fact that f ′ (t) = log(1/α)(a2 − f (t)2 ) is solved by a tanh(a log(1/α)t + t0 ), where t0 is an integration constant. Since the inner product is positive at initialization by definition, t0 is positive. By the fact that tanh is monotone increasing, we obtain a lower bound by discarding this integration constant. This leaves
(0) e⊤ w j Dj >
≥
(0) Dj
2
(0)
Dj
1/2 − 2mα
−
√
2mα
tanh log(1/α)
(0) Dj
2
1/2 ! − 2mα t
√ (0) 2 Dj − 2mα t 1−α ,
√ where above we applied the inequalities 1 − x2 ≥ 1 − x and tanh(x) ≥ 1 − 2 exp(−2x). Note that there √ (0) (0) exists α sufficiently small that for any j, 2 Dj − 2mα > Dj , so for α below this threshold at time t ∈ [0, κ] one has
(0) e⊤ w j (t)Dj >
(0) Dj (0)
> Dj
√
(0)
Dj
1−α − 2mα (0) t D − α1/4 , 1−α j
t
(5)
1 where the second inequality is valid for α ≤ (2m) 2 . This directly implies that for α small enough and q (0) n any κ ∈ 0, 41 2L(0) , there exists δ > 0 such that the alignment of any neuron j with direction Dj is
bounded by below by 1 − αδ at time κ, as required. Note here that δ depends on κ, and α∗ only depends on the data. □ Proof of Item 2. We select some arbitrary κ b ∈ (0, κ). Since κ b < τ , we may insert it into eq. (4) to obtain α
q 2L(0) 1+ κ b n
< ∥w ej (b κ)∥ < α
25
1−
q
2L(0) κ b n
.
(0)
We express this deviation in terms of the quantity ℓ◦j (b κ). We note that −ℓ◦j (b κ) = 1 − Dj
κ b for all
j ∈ [m]. Therefore,
α
q (0) 2L(0) −ℓ◦ κ)+ Dj + κ b j (b n
< ∥w ej (b κ)∥ < α
−ℓ◦ κ)+ j (b
(0)
Dj
q 2L(0) − κ b n
.
Then, eq. (5) gives that for κ b sufficiently small, α may be chosen sufficiently small that for any time t ∈ [b κ, κ] (0)
Dj
(0) D κ b/2 (0) (0) e⊤ . 1−α j <w j (t)Dj ≤ Dj
(6)
Note that by definition of τ , |hθe(xi )| < mα for all i ∈ [n]. Putting this back into eq. (3), we obtain as an upper bound that
∥w ej (κ)∥ < ∥w ej (b κ)∥α <α <α
−
(0)
Dj
+mα (κ−b κ)
q (0) 2L(0) −ℓ◦ κ b−mα(κ−b κ) Dj − j (κ)+ n q (0) 2L(0) −ℓ◦ κ b Dj −2 j (κ)+ n
.
For the lower bound, we get
(0) Dj κ′ /2 (0) ∥w ej (κ)∥ > ∥w ej (b κ)∥ expα − Dj 1−α − mα (κ − κ b) ! ! r (0) ′ 2L(0) D κ /2 (0) (0) Dj α j κ b+ + mα (κ − κ b) > expα −ℓ◦j (κ) + Dj + n >α
−ℓ◦ j (κ)+
(0)
Dj
q 2L(0) κ b +2 n
,
where the final inequality is valid for α sufficiently small. Since κ b is arbitrary, we conclude that given any ξ > 0, we may select α sufficiently small that the deviation of the neurons’ norms from those predicted by the algorithm 1 does not exceed ξ. □ e⊤ Proof of Item 3. We compute that for some yi < 0 such that w j (0)xi > 0, and for t ∈ [0, κ], 1 d e⊤ e⊤ ejw w xi = Dj⊤ xi − Dj⊤ w j xi log(1/α) dt j 1 1 = (yi − hθe(xi )) + n n ≤
1 1 yi − n n
X
v|w ej⊤ xi >0
e⊤ e⊤ yv w j xv w j xi + 2mα.
X v | yv <0, e ⊤ xv >0 w j
26
⊤
e j xi (hθe(xv ) − yv )w ej⊤ xv w
The is obtained by plugging in the bound on the network output. This bound also implies that for α sufficiently small, 1 (yv > 0) (yv − hθt (xv )) > 0, which allowed us to discard the sum over positively labeled data. Since neurons are aligned by time κ b, we conclude using eq. (6) and Proposition 7 that √ κb D(0) /4 log(1/α) d e⊤ j , w j xi ≤ yi + 2α dt n where this holds for α sufficiently small and any t ∈ [b κ, κ]. Therefore, by time 2b κ and for α sufficiently ⊤ e small, wj xi = 0 for all i ∈ / Isj . □ This completes the proof of Lemma 3.
■
From Lemma 3 and Assumption 2, we conclude that given any κ > 0, there exists α∗ sufficiently small that θ+ := (ai , wj )j∈J+ satisfies θ̇+ (t) ∈ −∂L+ (θ+ (t)) for almost all t ≥ κ, where L+ (θ+ ) :=
1 X (hθ+ (xi ) − yi )2 . 2n i∈I+
By the symmetry of the signs, an analogous statement is true of θ− := (ai , wj )j∈J− . Therefore, on the interval [κ, ∞) neurons in the set J+ evolve independently from those in the set J− according to the autonomous systems just described above. Consequently, we can treat the systems θ+ and θ− independently from now on, which we do by assuming w.l.o.g. sj = 1 for all j ∈ [m] and sgn yi = 1 for all i ∈ [n]. We note that with this assumption, Ai,j = 1 w ej⊤ (0)xi > 0 . Similar autonomous systems arguments have been used in Boursier and Flammarion [2025b, Appendix F.3], but are even simpler here, due to the orthogonal data assumption.
D.2
Phase 1: Slow growth
In this stage, we verify that up to a time arbitrarily close to the next jump time, tk+1 , all neurons in (k) (k) (k) the set NU are still small and aligned in the directions Dj , and all neurons in the set NF have not changed significantly. For ε > 0, define the time n (k) e⊤ τ1 := inf t ≥ κ ∃ j ∈ [m] s.t. w ≤ 1 − αε/2 j Dj (k)
or ∃ i ∈ SF s.t. |hθe(xi ) − yi | ≥ αε (k) Dj
or ∃ j ∈ [m] s.t. ∥w ej ∥ > 2 max j∈[m] o^ (k) or ∃ j ∈ NU s.t. ∥w ej ∥ ≥ αε tk+1 . (k)
(7) (8) (9) (10)
The condition ∥w ej ∥ ≤ 2∥Dj ∥ is simply used to ensure that our analysis is restricted to a domain on e which θ is Lipschitz continuous, as this will allow us to apply Rademacher’s theorem to conclude certain functions thereof are differentiable almost everywhere. Our analysis will actually show that this condition does not break, meaning that for α sufficiently small, the gradient n o flow trajectory on [κ, τ1 ] is (k)
restricted to the compact set (w ej )j∈[m] ∥w ej ∥ ≤ 2 Dj 27
for all j ∈ [m] .
In the result below and throughout the account of subsequent phases, we use the notation j ⋆ in place of (k) j⋆ for the neuron which grows to constant order when passing from saddle k to saddle k +1 to improve readability. Assuming Hypothesis 1, we will prove in the lemma below that on the interval [κ, τ1 ], the alignment of all neurons remains stable and the loss on fitted data does not increase significantly. We will also show that provided ε is selected sufficiently small we have ∥w ej ⋆ (τ1 )∥ = αε , meaning neuron ⋆ j is the largest of all of the unfitted neurons at time τ1 . We will also prove that as ε decreases, τ1 approaches tk+1 . Lemma 4. Suppose that Hypothesis 1 holds. Then for all κ ∈ (tk , tk+1 ), there exists ε∗ such that for all ε ∈ (0, ε∗ ) there exists α∗ > 0 such that for all α ∈ (0, α∗ ) the following are true: (k)
1. ∀i ∈ SF , ∀t ∈ [κ, τ1 ], |hθe(xi ) − yi | < αε . (k) e⊤ > 1 − αε/2 . 2. ∀j ∈ [m], ∀t ∈ [κ, τ1 ], w j Dj r r (k) (k) (k) − αε/4 < ∥w ej ∥ < n Dj + αε/4 . 3. ∀j ∈ NF , ∀t ∈ [κ, τ1 ], n Dj
4. tk+1 −
3ε (k) 2 Dj ⋆
< τ1 < tk+1 −
ε (k) 2 Dj ⋆
.
5. ∥w ej ⋆ (τ1 )∥ = αε . (k)
ej ∥) < 2ε . 6. ∀j ∈ NU , ∀t ∈ [κ, τ1 ], ℓ◦j (t) + logα (∥w Proof. Proof of Item 1 Lemma 4. Let δ be such that the conditions of Hypothesis 1 hold. In order to check that |hθe(xi ) − yi | < αε , we will bound the growth in norm of the quantity E (k) = −
1 X hθe(xi ) − yi xi . n (k) i∈SF
To begin this section, it will be useful to note now that
v u u 1 u X ∥Dj ∥ ≤ t (hθe(xi ) − yi )2 n i∈[n]
r ≤
2L(0) , n
(11)
where we have applied the Cauchy-Schwarz inequality and the monotonicity of the gradient flow. We will use this inequality repeatedly. We compute that
28
2 1 1 d d E (k) = E (k) ⊤ E (k) 2 log(1/α) dt log(1/α) dt 2 1 X X 2 ⊤ (k) ⊤ e e⊤ ⊤ (k) Ai,j ∥w ej ∥ xi E + Dj wj wj xi xi E =− n (k) i∈SF
j∈[m]
1 X X ⊤ (k) e⊤ ejw ≤− Ai,j ∥w ej ∥2 Dj⊤ w j xi xi E n (k) i∈SF
j∈[m]
1 X X ⊤ (k) e⊤ ejw ≤− Ai,j ∥w ej ∥2 Dj⊤ w , j xi xi E n (k) (k) i∈SF
(12)
j∈NU
(k)
where the final inequality follows from the fact that for any j ∈ NF , the sum may be written as
2
−
∥w ej ∥ n3
X
X e⊤ e⊤ Ai,j (hθe(xi ) − yi )w Av,j (hθe(xv ) − yv )w j xv j xi ≤ 0.
v∈[n]
(k)
i∈SF
(k)
The above inequality follows from noting that, since we are considering some j ∈ NF , {v ∈ [n] | (k) Av,j = 1} = {i ∈ SF | Ai,j = 1} (such neurons are by definition active only on fitted data) so this is a (k) square. We have therefore only to obtain a bound on the contribution of those j ∈ NU . Note that for e j is a unit vector combined with (11) implies any j ∈ [m], the fact that w
e⊤ |w j Dj | ≤ ∥Dj ∥ ≤
r
2L(0) . n ⊤
(k)
e j xi < Also, we have for any j ∈ NU by (7) and Proposition 7 that w these observations with (10) to obtain
√
2αε/4 on [κ, τ1 ]. We combine
r X 4L(0) 9ε/4 ⊤ (k) 1 1 d E (k) ⊤ E (k) ≤ m α xi E log(1/α) dt n n (k) i∈SF
≤
2m p L(0)α9ε/4 E (k) , n
where we have used the Cauchy-Schwarz inequality in the final line. On a compact domain, ∂L is e is Lipschitz continuous on the domain specified in the bounded. Therefore, the function t 7→ θ(t) definition of τ1 for any fixed α. Since the composition of Lipschitz continuous functions is also Lipschitz continuous, E (k) is Lipschitz continuous on [κ, τ1 ]. Therefore, it is differentiable almost everywhere on [κ, τ1 ], and furthermore has bounded subdifferential at every point in [κ, τ1 ]. In subsequent arguments when we appeal briefly to Rademacher’s theorem for differentiability, it is implicit that this argument has been used. This affords us the bound d 2m p E (k) ≤ L(0) log(1/α)α9ε/4 dt n < α2ε , 29
√ for α sufficiently small. Since |hθeκ (xi ) − yi | ≤ αδ by Item 3 Hypothesis 1, we have E (k) (κ) < αδ / n. Integrating and using this initial condition, we have
E (k) < E (k) (κ) + (t − κ)α2ε αδ < √ + (tk+1 − κ)α2ε n < α3ε/2 , for ε < 2δ and α ≤ (1+tk+11−tk )2/ε . This implies that max |hθe(xi ) − yi | < nα3ε/2 (k)
i∈SF
< αε , for all t ∈ [κ, τ1 ], concluding the proof of this item.
□
Proof of Item 2 Lemma 4. We verify now the stability of alignment of the neurons. We split this into the (k) (k) (k) (k) case j ∈ NF and the case j ∈ NU . For the former, first note that for j ∈ NF , {i ∈ SU | Ai,j = 1} = ∅ by definition. Consequently,
1 Dj < √ α ε . n Inserting this into the differential equation governing tangential dynamics, we get
1 d e ⊤ (k) (k) (k) e⊤ ejw wj Dj = Dj⊤ Dj − Dj⊤ w j Dj log(1/α) dt (k)
≥ −2 Dj
Dj
(k)
>−
2 Dj √ n
αε ,
(13)
We simply integrate, using Item 4 Hypothesis 1 for the alignment value at time κ, to obtain
(k)
(k) (k) e⊤ w > Dj j Dj (k)
> Dj
2 Dj √ 1 − αδ − n 1 − αε/2 ,
(tk+1 − κ) log(1/α)αε
(k)
where the final inequality is again valid for ε and α sufficiently small. For the case j ∈ NU , we first use (k) eq. (10) to bound the network output on data i ∈ SU :
30
hθe(xi ) =
X
⊤ e j xi ∥w ej ∥2 w
j∈[m]
+
< mα2ε .
(14) (k)
(k)
Using this, we estimate the alignment of an arbitrary neuron j ∈ NU with direction Dj
as follows:
⊤ 2 2 1 d e ⊤ (k) (k) e j Dj(k) − w wj Dj = Dj log(1/α) dt 1 X (k) ⊤ e e ⊤ (k) − hθe(xi ) x⊤ D − x w w D j i i j j j n (k) i∈Sj
1 X (k) ⊤ e e ⊤ (k) Ai,j (hθe(xi ) − yi ) x⊤ w w D − D − x j j i i j j n (k) i∈SF
⊤ 2 e j Dj(k) − 2 Dj(k) mα9ε/4 − 2 Dj(k) α5ε/4 − w ⊤ 2 2 (k) e j Dj(k) − α6ε/5 . − w > Dj (k)
> Dj
2
(15)
The first inequality is an application of Corollary 2 to both sums (given (7)) as well as using (14) for the (k) (k) sum over i ∈ Sj and (8) for the sum over i ∈ SF . The second inequality follows for α sufficiently small. The above implies that the solutions of the differential equation f ′ (t) = b(a2 − f (t)2 ), where (k)
a2 = Dj
2
− α6ε/5 and b = log(1/α), furnish us with a lower bound on the alignment. Solutions of (k)
this differential equation approach a limiting value of a monotonically. Since a > Dj − α3ε/5 from √ the inequality 1 − x2 > 1 − x, and Item 4 Hypothesis 1 allows us to lower bound the alignment value at time κ, we have that for all t ∈ [κ, τ1 ], (k) (k) (k) δ 3ε/5 ε/2 e⊤ D > D min 1 − α , 1 − α > D 1 − α , w j j j j for ε and α sufficiently small.
□ (k)
Proof of Item 3 Lemma 4. We check that all the neurons in the set NF cannot change in norm significantly (k) (k) in the first phase. Recall that for j ∈ NF , {i ∈ SU | Ai,j = 1} = ∅. Therefore, the differential equation governing radial dynamics admits the bound
1 d ∥w ej ∥ = Dj⊤ w ej log(1/α) dt ≥ − E (k) ∥w ej ∥. Applying Grönwall’s inequality combined with the initial conditions from Item 2 Hypothesis 1, we get (k) that for any t ∈ [κ, τ1 ] and j ∈ NU ,
31
Z τ1 E (k) ds ∥w ej ∥ ≥ ∥w ej (κ)∥ exp − log(1/α) κ αε > ∥w ej (κ)∥ exp − log(1/α) √ (tk+1 − κ) n ε/2 > ∥w ej (κ)∥ exp −α ≥ ∥w ej (κ)∥ 1 − αε/2 r >
r >
(k)
− αδ 1 − αε/2
(k)
− αε/4 .
n Dj n Dj
(16)
The above inequalities are valid for ε and α sufficiently small. An analogous argument yields the claimed upper bound r ∥w ej (t)∥ <
(k)
n Dj
+ αε/4 . (k)
(k)
Note that this implies that for α sufficiently small, for all j ∈ NF , ∥w ej (t)∥ ≤ 2 Dj with (10), we see that (9) does not break at time τ1 .
. Combining this □
(k)
Proof of Item 6 Lemma 4. To estimate the growth of any neuron j ∈ NU , we compute that 1 d ∥wj ∥ X e⊤ ∥w ej ∥ = − Ai,j (hθe(xi ) − yi )w j xi log(1/α) dt n i∈[n]
>
>
(k)
Dj
(k)
Dj
∥wj ∥ X e⊤ − αε/2 − mα2ε ∥w ej ∥ − Ai,j (hθe(xi ) − yi )w j xi n (k)
− αε/2 − mα2ε ∥w ej ∥ −
√
i∈S / j
2α5ε/4 ∥w ej ∥.
(17)
The first inequality is from the assumption on alignment, (7), combined with the assumed bound on the norms of the unfitted neurons, (10). The second is the combination of this assumed alignment with (7) and (8). The above implies that for α sufficiently small, d (k) ∥w ej ∥ > log(1/α) Dj − 2αε/2 ∥w ej ∥. dt Grönwall’s inequality then gives that for t ∈ [κ, τ1 ],
32
(k) − 2αε/2 (t − κ) ∥w ej ∥ > ∥w ej (τ1 )∥ exp log(1/α) Dj (k)
= ∥w ej (τ1 )∥α (1)
−ℓ◦ j (κ)− Dj
(2)
−ℓ◦ j (κ)− Dj
> α > α
(t−κ)+2αε/2 (t−κ)
− Dj (k)
(t−κ)+ε/3+2αε/2 (tk+1 −κ)
(k)
(t−κ)+ε/2
◦
= α−ℓj (t)+ε/2 . In the above, (1) is from an application of Item 1 Hypothesis 1 with the choice ξ = ε/3 and (2) is valid (k) for α sufficiently small. For the upper bound, we compute in a similar manner that for any j ∈ NU , 1 d ∥wj ∥ X e⊤ Ai,j (hθe(xi ) − yi )w ∥w ej ∥ = − j xi log(1/α) dt n i∈[n] √ (k) < Dj + 2α5ε/4 ∥w ej ∥. Again by Grönwall’s inequality combined with the initial conditions from Hypothesis 1 with ξ = ε/3, we have the bound
(k)
∥w ej ∥ < α
−ℓ◦ j (κ)− Dj
√ (t−κ)−ε/3− 2α5ε/4 (tk+1 −κ)
◦
< α−ℓj (t)−ε/2 .
(18) □ (k)
Proof of Items 4 and 5 Lemma 4. Note that for t, t′ ∈ [tk , tk+1 ], −ℓ◦j (t) − Dj
(t′ − t) = −ℓ◦j (t′ ). Using
(k)
this fact and that ∥w ej ∥ < ε on [κ, τ1 ), we obtain that for all j ∈ NU , ε < −ℓ◦j (τ1 ) +
ε 2 (k)
= −ℓ◦j (tk+1 ) − Dj
ε (τ1 − tk+1 ) + . 2
We have −ℓj ⋆ (tk+1 ) = 0, and hence the upper bound τ1 of
τ1 < tk+1 −
ε (k)
.
(19)
2 Dj ⋆
To verify that neuron j ⋆ is the largest at time τ1 note the upper bound on the neurons’ norms provided by (18) is monotone increasing in t. From this observation followed by inserting the upper bound on τ1 derived in eq. (19), we get
33
ε ∥w ej (τ1 )∥ < expα −ℓ◦j (τ1 ) − 2 (k) D j 1 − 1 ε . < expα −ℓ◦j (tk+1 ) + (k) 2 D⋆
(20) (21)
j
(k)
Note that −ℓ◦j (tk+1 ) > 0 for j ∈ NU \ {j ⋆ }. This implies that for such j the exists α sufficiently small that (k) Dj 1 − 1 ε > ε. −ℓ◦j (tk+1 ) + (k) 2 D⋆ j
(k)
Hence, ∥w ej (τ1 )∥ < αε for j ∈ NU \ {j ⋆ }. This proves that no neuron other than j ⋆ could have ∥w ej (τ1 )∥ = αε for ε sufficiently small, and since no other condition breaks we have ∥w ej ⋆ (τ1 )∥ = αε . We obtain a lower bound on τ1 by considering that (k)
ε > − Dj ⋆
(τ1 − tk+1 ) −
ε 2
imposes the condition
τ1 > tk+1 −
3ε (k)
.
(22)
2 Dj ⋆
Note that by selecting ε sufficiently small depending on κ, we can indeed ensure that τ1 > κ.
□
This completes the proof of Lemma 4.
■
D.3
Phase 2a: Growth to constant order
Next, we deal with the rapid growth of neuron j ⋆ , the account of which is split into two parts. To begin, (k) it will be important to obtain a uniform bound on the norms of neurons in the set j ∈ NU \ {j ⋆ }, in ε much the same way that in the proof of Lemma 4 we had by definition of τ1 that ∥w ej ∥ < α on [κ, τ1 ] or in the proof of Lemma 3 we had ∥w ej ∥ < α1/2 . The idea of the proof is to verify that, given the upper (k) bound on neurons in the set NU \ {j ⋆ } at time τ1 , if these neurons were to subsequently grow at the fastest possible rate, they would still not have exceeded some constant threshold by a certain time after τ1 . Proposition 3. For all κ ∈ (tk , tk+1 ), there exists ε∗ > 0 such that for all ε ∈ (0, ε∗ ) there exists α∗ > 0 such that for all α ∈ (0, α∗ ) the following holds: r n (k) ⋆ ∀j ∈ NU \ {j }, ∀t ∈ τ1 , τ1 + 2 cU , ∥w ej ∥ < αcU , (23) 2L(0) where cU := − 14 maxj ′ ∈N (k) \{j ⋆ } ℓj ′ (tk+1 ). U
34
Proof. Recall that for any j ∈ [m], 1 d ∥w ej ∥ ≤ log(1/α) dt
r
2L(0) ∥w ej ∥. n
(k)
Recall also the upper bound on neurons in the set NU \ {j ⋆ } at time τ1 provided by (20). Using Grönwall’s inequality we obtain from these observations that on the considered interval,
! 2L(0) ∥w ej ∥ ≤ ∥w ej (τ1 )∥ exp log(1/α)(t − τ1 ) n ! r ε 2L(0) ◦ < expα −ℓj (τ1 ) − − (t − τ1 ) 2 n ! r 2L(0) ε ◦ < expα −ℓj (tk+1 ) − − (t − τ1 ) 2 n r
≤ expα ≤ expα < expα
!
ε 1 −ℓ◦j (tk+1 ) − +
max ℓj ′ (tk+1 ) 2 j ′ ∈NU(k) \{j ⋆ } ! ε 1 ◦ max ℓ (tk+1 ) − − 2 j ′ ∈NU(k) \{j ⋆ } j 2 ! 1 − max ℓ◦ (tk+1 ) . 4 j ′ ∈NU(k) \{j ⋆ } j 2
The final inequality is valid for ε sufficiently small, proving the claim.
■
We will throughout the account of several subsequent results assume that ε is selected small enough that ε < cU , meaning that, informally, contributions of order cU can be thought of as negligible relative to those of order ε. We define the quantity (k) r √ Dj ⋆ 1 n (k) η := min √ p , n Dj ⋆ . 2 60 2 4 2L(0) This is a constant threshold which we will use to break the account of the growth of neuron j ⋆ in two. We do so by defining n (k) ε/12 e⊤ τ2 := inf t ≥τ1 w j ⋆ Dj ⋆ ≤ 1 − α
(24)
(k)
or ∃ i ∈ SF s.t. |hθe(xi ) − yi | ≥ αε/6
(25)
(k)
(26)
or ∃ j ∈ [m] s.t. ∥w ej ∥ > 2 max Dj j∈[m] r o^ n or ∥w ej ⋆ ∥ ≥ η τ1 + 2 cU . 2L(0)
35
(27)
We will prove in the lemma below that ∥w ej ⋆ (τ2 )∥ = η, meaning that neuron j ⋆ has grown to constant order. In order to do so, we will verify that the loss on fitted data does not increase significantly during (k) this phase. As a consequence, the alignment of neurons in the set NF ∪ {j ⋆ } remains stable. The use of the constant threshold η is that there is a tradeoff between proving the growth conditions and the stability of the loss on fitted data. Specifically, one must ensure that the growth phase lasts long enough that neuron j ⋆ can grow to constant order. On the other hand, this increases the time interval on which one must control E (k) and increases the coefficients of terms in (12). Introducing this constant threshold, the specific choice of which simply emerges as a consequence of they way we bound E (k) , allows us to balance these two competing aims across both parts of the growth phase. believe that We ⊤ e more delicate arguments when estimating the derivative of the quantity max (k) wj ⋆ xi , which i∈SF
+
controls the extent to which neuron j ⋆ could align in the direction of data which has already been fitted, may allow the account of growth to occur in only only one phase. For instance, the bound when passing to (36) loses a lot of control. q n cU is required to ensure, using Proposition 3, The final stopping condition given by the time τ1 + 2 2L(0) (k)
that we have a uniform bound on all of the neurons in the set NU \ {j ⋆ } on the interval [τ1 , τ2 ]. That we apply this kind of bound is reflective of the fact we do not consider at all the precise alignment or (k) growth rates of the neurons NU \ {j ⋆ } during the growth phases; we only ensure that the duration of these phases is sufficiently short that these neurons do not change significantly. Lemma 5. Suppose the Hypothesis 1 holds. Then for all κ ∈ (tk , tk+1 ), there exists ε∗ > 0 such that for all ε ∈ (0, ε∗ ) there exists α∗ > 0 such that for all α ∈ (0, α∗ ) the following are true: 1. τ2 − τ1 < 2.
3ε (k) Dj ⋆
.
(k) ∀j ∈ NF , ∀t ∈ [τ1 , τ2 ],
r r (k) (k) ε/8 n Dj −α < ∥w ej ∥ < n Dj + αε/8 .
⊤ (k) e j ⋆ xi 3. ∀i ∈ SF , ∀t ∈ [τ1 , τ2 ], maxi∈S (k) w < αε/6 . F
⊤
+
(k)
e j ⋆ Dj ⋆ > 1 − αε/12 . 4. ∀t ∈ [τ1 , τ2 ], w (k)
5. ∀i ∈ SF , ∀t ∈ [τ1 , τ2 ], |hθe(xi ) − yi | < αε/6 . 6. ∥w ej ⋆ (τ2 )∥ = η. We observe at this point that although Item 4 Lemma 5 would seem to imply a statement on realignment with fitted data, we are required in the proof to obtain Item 3 Lemma 5 first in order to prove Item 4 Lemma 5. This is an interesting result of the fact that a bootstrapping argument, in which one would (k) assume some level of alignment of neuron j ⋆ in direction Dj ⋆ and then insert this into (12), leads to (k) too weak a control on E to be able to use this to get the assumed alignment back at the end (and vice versa). This circularity was not an issue in the arguments leading to (15), because in this setting we (k) had a the growth conditions ∥w ej ∥ ≤ αε for all j ∈ NU on the interval [κ, τ1 ]. The reader may also note (k) that our statement includes no control on the alignment of neurons in the set NF . This is because we can simply control the loss on fitted data and use this when needed to estimate the alignment of such neurons across several phases at the end (this will ultimately be done in Lemma 8). We cannot, on the other hand, avoid estimating the norms of such neurons in every phase we describe, since we must prove the flow is restricted to a bounded domain in order to apply Rademacher’s theorem. Proof. We consider the items in the statement of Lemma 5.
36
Proof of Item 1. We bound the phase duration above by examining the growth of neuron j ⋆ . We have that on [τ1 , τ2 ],
1 d ∥w ej ⋆ ∥2 2 log(1/α) dt
X X 1 1 e⊤ e⊤ Ai,j ⋆ (hθe(xi ) − yi )w (hθe(xi ) − yi )w = ∥w ej ⋆ ∥2 − j ⋆ xi − j ⋆ xi n n (k) (k) i∈SF
i∈Sj ⋆
1 X (k) e⊤ > ∥w ej ⋆ ∥2 ∥Dj ⋆ ∥(1 − αε/12 ) − αε/6 − hθe(xi )w j ⋆ xi n (k)
(28)
i∈Sj ⋆
(k) = ∥w ej ⋆ ∥2 ∥Dj ⋆ ∥(1 − αε/12 ) − αε/6 X X 1 ∥w w e⊤ e⊤ e⊤ − ej ⋆ ∥2 w Ai,j ∥w ej ∥2 w j ⋆ xi + j xi j ⋆ xi n ⋆ (k) j̸=j
i∈Sj ⋆
2
≥ ∥w ej ⋆ ∥
∥w ej ⋆ ∥2 (k) ∥Dj ⋆ ∥(1 − αε/12 ) − αε/6 − − mα2cU
(29)
n
∥w ej ⋆ ∥4 (k) > ∥w ej ⋆ ∥2 ∥Dj ⋆ ∥ − αε/13 − . n
(30)
In the above, (28) is from the definition of τ2 (where we have not used the alignment in the estimate of (k) the sum over the fitted data as it is not necessary here) and (29) is from the fact that for any i ∈ Sj ⋆ , (k)
{j ∈ NF | Ai,j = 1} = ∅. A function satisfying the differential inequality f ′ (t) > 2 log(1/α)af (t) − 2 log(1/α)bf (t)2 has a lower bound f (t) >
a exp (2 log(1/α)a(t − C)) a 1 = , b 1 + exp (2 log(1/α)a(t − C)) b α2a(t−C) + 1 (k)
where C is an integration constant. In our case, f = ∥w ej ⋆ ∥2 , a = Dj ⋆
− αε/13 , and b = n1 . We will
obtain an upper bound on this constant C, since this will in turn provide a lower bound on f (t) and hence an upper bound on τ2 . By Item 5 Lemma 4, ∥w ej ⋆ (τ1 )∥2 = α2ε . Simple algebra then gives C < τ1 −
a −2ε −1 bα
log
2a log(α)
.
This implies that for t ∈ [τ1 , τ2 ], f (t) >
a b
1 1 + expα 2a(t − τ1 ) +
Rearranging 37
−2ε −1 log( a ) bα log(α)
.
a b
1 1 + expα
−2ε −1 log( a ) bα 2a(t − τ1 ) + log(α)
< η2
gives
a a 1 −2ε t − τ1 < − 1 − log log α −1 2a log(α) bη 2 b a 1 a −2ε − 1 − log < log α 2a log(α) bη 2 b 3ε , < (k) Dj ⋆ r (k) valid provided α is taken sufficiently small owing to the fact we take η < n Dj ⋆ fixed.
□
Proof of Items 3 and 5. We derive an upper bound on the alignment of neuron j ⋆ with data in the set (k) (k) SF in terms of E (k) . We have for any i ∈ SF 1 1 d e⊤ wj ⋆ xi = − Ai,j ⋆ (hθe(xi ) − yi ) log(1/α) dt n 1 X e⊤ e⊤ Av,j ⋆ (hθe(xv ) − yv )w + j ⋆ xv w j ⋆ xi . n
(31)
v∈[n]
(k)
For the first term, if i ∈ SF , then 1 − (hθe(xi ) − yi ) ≤ E (k) . n
(32) (k)
For the sum, we obtain separate estimates over unfitted and fitted data. For v ∈ Sj ⋆ , recall that by (k) (k) (k) construction of the set NF , {j ∈ NF | w ej⊤ Dj ⋆ > 0} = ∅. Therefore, the only contribution to the (k) network output on such data is from neurons in the set NU . This leads to the inequalities
e⊤ hθe(xv ) − yv = ∥w ej ⋆ ∥2 w j ⋆ xi +
X
e⊤ ∥w ej ∥2 w j xi − yv
(k)
j∈NU \{j ⋆ } 2cU e⊤ < ∥w ej ⋆ ∥2 w − yv j ⋆ xi + mα √ y v < η2 + 2αε/24 + mα2cU (k) n Dj ⋆ 2 η < yv − 1 + αε/25 , (k) n Dj ⋆
38
where (1) is from Proposition 3, (2) is an application of Proposition 7 to (24), and (3) is valid for α sufficiently small. Using the same application of Proposition 7 to (24), we obtain
1 X e⊤ (hθe(xv ) − yv )w j ⋆ xv n (k) v∈Sj ⋆
√ η2 y 1 X v yv − 1 + αε/25 − 2αε/24 < (k) (k) n n Dj ⋆ n Dj ⋆ (k) v∈Sj ⋆ X yv2 η2 − 1 + αε/26 < (k) (k) 2 Dj ⋆ n Dj ⋆ (k) n v∈Sj ⋆ 2 η (k) = Dj ⋆ − 1 + αε/26 , (k) n Dj ⋆
(33)
(k)
where the second inequality is valid for α sufficiently small. For v ∈ SF , we have the obvious inequality e⊤ e⊤ w (k) w j ⋆ xv ≤ max j ⋆ xv . Using the Cauchy-Schwarz inequality gives v∈SF
√ 1 X e⊤ Av,j ⋆ (hθe(xv ) − yv )w n E (k) j ⋆ xv ≤ n (k)
⊤
e j ⋆ xv . max w
(34)
(k) v∈SF
v∈SF
(k)
Inserting (32), (33), and (34) into (31), we obtain that for [τ1 , τ2 ] and i ∈ SF ,
2
η 1 d e⊤ (k) e⊤ − 1 + αε/26 w w ⋆ xi ≤ E (k) + Dj ⋆ j ⋆ xi (k) log(1/α) dt j n Dj ⋆ √ e⊤ e⊤ + n E (k) max w j ⋆ xv w j ⋆ xi . (k)
v∈SF
(k)
Since the above inequalityholds for any i ∈ SF , we have that, when differentiable, the continuous e⊤ function f (t) := max (k) w obeys the differential inequality j ⋆ xi i∈SF
1 f ′ (t) < E (k) log(1/α)
+
1+
√
nf (t)
2
(k)
− Dj ⋆
1 −
η n
2
(k) Dj ⋆
+ αε/26 f (t).
Rademacher’s theorem applies here also, however we must be more careful since the function w 7→ w is not Lipschitz continuous (in fact, it is not even continuous at the origin). However, it is Lipschitz continuous on any set bounded away from the origin. Note that the arguments in the proof of Item 1 Lemma 5 show that neuron j ⋆ is increasing in norm monotonically on [τ1 , τ2 ]. Combining this observation with Item 5 Lemma 4, we have that αε < ∥w ej ⋆ ∥ < η, a domain on which w 7→ w is indeed Lipschitz continuous for α fixed. As the boundedness of the subdifferential on compact domains (note (26) in the definition of τ2 ) implies θe is Lipschitz in t and the composition of Lipschitz continuous functions is Lipschitz continuous (we note max is 1-Lipschitz), we finally get the required 39
differentiability. We use (24) and Proposition 7 to see that f (t)2 < 2αε/12 on [τ1 , τ2 ]. Plugging this back in we have for α sufficiently small 2 √ ε/12 η 1 (k) ε/26 ′ (k) +α f (t). 1 + 2 nα − Dj ⋆ 1 − f (t) ≤ E (k) log(1/α) n Dj ⋆ √ We have the differential inequality f ′ (t) < a E (k) log(1/α)−b log(1/α)f (t), where a = 1 + 2 nαε/12 (k)
and b = Dj ⋆
1−
η2
a log(1/α) E (k) exp(b log(1/α)t). Integration leads to
f (t) < αb(t−τ1 ) f (τ1 ) + a log(1/α)αbt
Z t
α−bs E (k) ds
τ1
<
√
2αε/4 + a log(1/α)αbt
Z t
α−bs E (k) ds
(35)
τ1
<
√
2α
ε/4
Z t + a log(1/α)
E (k) ds,
(36)
τ1
where the second inequality comes from an application of Proposition 7 to the initial condition from Item 2 Lemma 4 and the fact b > 0. We use this bound to derive a differential equation governing the growth of the residual. We must again estimate (12), which we recall states −
2 1 d 1 X X ⊤ (k) ejw e⊤ E (k) ≤ − Ai,j ∥w ej ∥2 Dj⊤ w . j xi xi E log(1/α) dt n (k) (k) i∈SF
j∈NU
(k)
We consider separately the cases j ∈ NU \ j ⋆ and j = j ⋆ . Beginning with the former, Proposition 3 implies ∥w ej ∥2 < α2cU . We simply reuse (11) combined with the Cauchy-Schwarz inequality to obtain −
1 X n (k) i∈SF
X (k)
j∈NU \{j ⋆ }
m ⊤ (k) e⊤ ejw ≤ Ai,j ∥w ej ∥2 Dj⊤ w j xi xi E n
p
2L(0)α2cU E (k) .
(37)
⊤
e j xi | ≤ 1, since we have imposed no assumption on the alignment Note that we have simply estimated |w (k)
of neurons j ∈ NU during this phase. For the contribution of the term corresponding to j = j ⋆ , we have −
′
+αε/26 . Multiplying both sides by exp(b log(1/α)t), we get (exp(b log(1/α)t)f (t)) <
(k)
n Dj ⋆
1 X 1p ⊤ (k) e j⋆ w e⊤ Ai,j ⋆ ∥w ej ⋆ ∥2 Dj⊤⋆ w < 2L(0)η 2 f (t) E (k) , j ⋆ xi xi E n n (k) i∈SF
where we have applied the bound (27) on the norm of neuron j ⋆ in the definition of τ2 and (11) combined with the Cauchy-Schwarz inequality. Substituting in (36), we obtain
40
−
1 X ⊤ (k) e j⋆ w e⊤ Ai,j ⋆ ∥w ej ⋆ ∥2 Dj⊤⋆ w j ⋆ xi xi E n (k) i∈SF
Z t √ ε/4 1p (k) 2 ds E (k) E 2L(0)η 2α + a log(1/α) ≤ n τ1
(38)
Inserting (37) and (38) into (12), we have Z t √ ε/4 d 1p E (k) ds E (k) ≤ 2L(0)η 2 log(1/α) 2α + a log(1/α) dt n τ1 mp + 2L(0) log(1/α)α2cU n Z t 2p 2p < E (k) ds, 2L(0)η 2 log(1/α)αε/4 + 2L(0)η 2 log(1/α)2 n n τ1 where the second inequality is valid for α sufficiently small by increasing the coefficient of the αε/4 √ ε/12 term (recall here that cU > ε) and by using the estimate a = 1 + 2 nα < 2 for α sufficiently small. Differentiability almost everywhere is again due to Rademacher’s theorem. This is a differential Rt inequality of the form F ′′ < pF + q, where F = τ1 E (k) ds. Applying Lemma 10, q √ ′ + F (τ ) exp ( p(t − τ1 )) √ 1 p ! ! r r 2p 2p 4 4 ε/4 ε = 2L(0)ηα + α expα − 2L(0)η(t − τ1 ) n n ! r r (1) 2p 2p 4 4 ε/4 < 2 2L(0)ηα expα − 2L(0)η(t − τ1 ) n n r p (2) 4 p 2 3ε 4 < √ 4 2L(0)ηαε/4 expα − 2L(0)η (k) n n Dj ⋆
F ′ (t) <
(3)
< αε/5 .
(39)
In these workings, (1) is valid for α sufficiently small, (2) follows from inserting the upper bound on √
(k)
D ⋆
j τ2 − τ1 derived in Item 1 Lemma 5, and (3) follows from the fact η < 60√n2 √ 4
2L(0)
.
We are now able to plug (39) back into (35) to estimate
⊤
e j ⋆ xi < max Ai,j ⋆ w
√
(k)
i∈SF
2αε/4 + a log(1/α)αε/5
Z t
αb(t−s) ds
τ1
√
a 2αε/4 + αε/5 1 − αb(t−τ1 ) b < c1 αε/5 ,
=
for some c1 > 0. Item 3 Lemma 5 then follows for α sufficiently small. 41
(40) □
Proof of Item 4. Next, we verify the stability of alignment of neuron j ⋆ . We have ⊤ 2 2 1 d e ⊤ (k) (k) e j Dj(k) − w wj ⋆ Dj ⋆ = Dj log(1/α) dt 1 X (k) ⊤ e e ⊤ (k) hθe(xi ) x⊤ − i Dj − xi w j w j Dj n (k)
(41)
i∈Sj
−
1 X (k) ⊤ e e ⊤ (k) (hθe(xi ) − yi ) x⊤ D − x w w D j j i i j j n (k) i∈SF
⊤ 2 e j ⋆ Dj(k) − w ⋆ 1 X (k) (k) ⊤ e e⊤ ⋆w ⋆D ⋆ hθe(xi ) x⊤ D − x − w ⋆ j i i j j j n (k) 2
(k)
> Dj ⋆
i∈Sj ⋆
(k)
− 2 Dj ⋆
α5ε/24 ,
This bound comes from (25) combined with an application of Corollary 2 to (24). We recall that for (k) 2cU e⊤ i ∈ Sj ⋆ , hθe(xi ) ≤ ∥w ej ⋆ ∥2 w . The growth to constant order of the norm of neuron j ⋆ means j ⋆ xi + mα that the previously used bootstrapping argument, where Corollary 2 was combined with a uniform (k) growth bound, is no longer possible. Instead, from (40), we have that if i ∈ / Sj , then on the interval ε/5 e⊤ . We apply this to see [τ1 , τ2 ], w j ⋆ xi ≤ c1 α 1 X (k) (k) ⊤ e e⊤ ⋆w ⋆D ⋆ − x hθe(xi ) x⊤ D w ⋆ j i j i j j n (k) i∈Sj ⋆
X 1 X ⊤ ⊤ (k) (k) ⊤ e e⊤ e j ⋆ xi + e j xi x⊤ ⋆w ⋆D ⋆ = ∥w ej ⋆ ∥2 w − x Ai,j ∥w ej ∥2 w D w ⋆ j i i j j j n ⋆ (k) j̸=j
i∈Sj ⋆
≤
1 (k) e⊤ ∥w ej ⋆ ∥2 w j ⋆ Dj ⋆ 1 − n
X
e⊤ w j ⋆ xi
2
(k) 2c + 2m Dj ⋆ α U
(k)
i∈Sj ⋆
X 2 1 (k) (k) 2c e⊤ e⊤ = ∥w ej ⋆ ∥2 w w + 2m Dj ⋆ α U j ⋆ Dj ⋆ j ⋆ xi n (k) i∈S / j⋆
(k)
≤ c21 η 2 Dj ⋆
(k)
α2ε/5 + 2m Dj ⋆
α2cU .
(42)
Putting (42) into (41), we have for t ∈ [τ1 , τ2 ] and for α sufficiently small that 2 ⊤ 2 d e ⊤ (k) 1 (k) e j ⋆ Dj(k) wj ⋆ Dj ⋆ > Dj ⋆ − w ⋆ log(1/α) dt (k)
(k)
− c21 η 2 Dj ⋆ α2ε/5 − 2m Dj ⋆ ⊤ 2 2 (k) e j ⋆ Dj(k) > Dj ⋆ − w − α9ε/48 . ⋆ 42
(k)
α2cU − 2 Dj ⋆
α5ε/24
We can now use arguments similar to those employed in√ the proof of Item 2 Lemma 4. From the initial conditions given by item 2 Lemma 4 and the inequality 1 − x2 > 1 − x, we obtain that on [τ1 , τ2 ] the alignment is lower bounded a function converging monotonically to min αε/2 , α9ε/96 . It then follows that for α sufficiently small, (k) (k) e⊤ (1 − αε/12 ). w j ⋆ Dj ⋆ > Dj ⋆
□ (k)
Proof. Proof of Item 2 We verify that the norms of neurons in the set NF did not change significantly on the interval [τ1 , τ2 ], which will lead us to conclude in combination with Proposition 3 that (26) did not fail on this interval. Item 3 Lemma 4 provides upper and lower bounds on the norms of neurons in (k) the set NF at time τ1 . In light of these initial conditions and the bound on the loss on data in the set (k) SF given in (25), identical workings to those yielding (16) give r
(k)
n Dj
− αε/8 < ∥w ej ∥ <
r
(k)
n Dj
+ αε/8
for all t ∈ [τ1 , τ2 ] for α sufficiently small. □ Proof. Proof of Item 6 We have concluded that no condition except for that on the norm of neuron j ⋆ could have broken at time τ2 , therefore ∥w ej ⋆ (τ2 )∥ = η, as claimed. □ This completes the proof of Lemma 5.
D.4
■
Phase 2b: Fitting of data
Define for ε′ > 0 the time n (k) ε′ /2 e⊤ τ3 := inf t ≥τ2 w j ⋆ Dj ⋆ ≤ 1 − α
(43)
′ (k) or ∃ i ∈ SF s.t. |hθe(xi ) − yi | ≥ αε
(k) or ∃ j ∈ NF s.t. ∥w ej ∥ > 2 max j∈[m] (k)
or ∥w ej ⋆ ∥2 ≥ n Dj ⋆
′
− αε /4
(44)
(k) Dj
o^
τ1 + 2
(45) r
n cU 2L(0)
.
(46)
The lemma below provides an account of the phase where neuron j ⋆ fits the data on which is it active. We prove that the alignment of neuron j ⋆ remains stable, the loss on fitted data does not increase significantly, and by the end of the phase neuron j ⋆ has grown very close to its final norm as predicted by Algorithm 1. The proof for this phase is almost identical to that for Phase 2a. Lemma 6. Suppose that Hypothesis 1 holds. Then for all κ ∈ (tk , tk+1 ), there exists ε∗ > 0 such that for all ε ∈ (0, ε∗ ), there exists ε′∗ > 0 such that for all ε′ ∈ (0, ε′∗ ) there exists α∗ such that for α ∈ (0, α∗ ) the following are true:
43
1. τ3 − τ2 < 2.
ε′ (k) Dj ⋆
. r
(k) ∀j ∈ NF , ∀t ∈ [τ2 , τ3 ],
(k) Dj
n
−α
ε′ /2
(k)
r ′ (k) < ∥w ej ∥ < n Dj + αε /2 .
′
3. ∀i ∈ SF , ∀t ∈ [τ2 , τ3 ], |hθe(xi ) − yi | < αε . ⊤ ′ (k) e j ⋆ xi < α5ε /4 . 4. ∀i ∈ SF , ∀t ∈ [τ2 , τ3 ], maxi∈S (k) w +
F
5.
(k) ε′ e⊤ ∀t ∈ [τ2 , τ3 ], w j ⋆ Dj ⋆ > 1 − α . (k)
6. ∥w ej ⋆ (τ3 )∥2 = n Dj ⋆
′
− αε /4 .
Proof. We work out a useful preliminary bound to begin this section. We upper bound the network (k) output on i ∈ Sj ⋆ :
(1)
⊤
e j ⋆ xi ∥w ej ⋆ ∥2 + mα2cU hθe(xi ) < w √ (2) ′ ′ yi (k) < + 2αε /2 n Dj ⋆ − αε /4 + mα2cU (k) n Dj ⋆ (3)
′
< yi − αε /3 .
(47)
Here, (1) is from Proposition 3, (2) is from combining (46) with an application of Proposition 7 to (43), and (3) is valid for α sufficiently small. Proof of Item 1. We estimate the growth of neuron j ⋆ . Similar workings to those which allowed us to obtain (30) in the proof of Item 1 Lemma 5 allow us to conclude that for α sufficiently small, on [τ2 , τ3 ] we have ∥w ej ⋆ ∥2 d 1 (k) ε′ ε′ 2 2 2cU ⋆ ⋆ Dj ⋆ (1 − α ) − α − ∥w ej ∥ > ∥w ej ∥ − mα 2 log(1/α) dt n ∥w ′ ej ⋆ ∥4 (k) > ∥w ej ⋆ ∥2 Dj ⋆ − αε /2 − . n As before, solutions of differential inequality f ′ (t) = 2 log(1/α)af (t) − 2 log(1/α)bf (t)2 for t ∈ [τ2 , τ3 ] have the lower bound f (t) >
a 1 . b α2a(t−C) + 1
From Lemma 5, we have ∥w ej ⋆ (τ2 )∥2 = η 2 , and determining the integration constant yields
f (t) >
a b
1 1 + expα
−2 −1 log( a ) bη 2a(t − τ2 ) + log(α)
Therefore, 44
.
f τ2 +
ε′ (k) Dj ⋆
> a b
1
(1)
1 + expα
2ε′ (k)
Dj ⋆
(k) Dj ⋆
− αε′ /2
−2 −1 log( a ) bη + log(α)
(1) a
1 b 1 + α ε′ ′ a > (1 − 2αε ) b >
(2)
(k)
> n Dj ⋆
′
− αε /4 ,
(48)
which contradicts the definition of τ3 . Inequality (1) comes from noting ab η −2 − 1 is bounded away from 0 as α decreases owing to the fact η is fixed and inequality (2) comes from estimating ab . Note that each of the inequalities above is only valid for α sufficiently small, depending on ε and the data. Necessarily, ′ we have τ3 < τ2 + ε(k) . □ Dj ⋆
Proof of Items 3 and 4. In this section it will again be important to derive a bound on the realignment of (k) neuron j ⋆ with fitted data in terms of the residual on fitted data. We recall that for i ∈ SF , 1 1 d e⊤ wj ⋆ xi = − (hθe(xi ) − yi )1 w ej⊤⋆ xi > 0 log(1/α) dt n 1 X e⊤ e⊤ Av,j (hθe(xv ) − yv )w + j ⋆ xv w j ⋆ xi n v∈[n] ! √ ⊤ ⊤ (k) e j ⋆ xi ) , e j ⋆ xv w 1 + n max w ≤ E (k)
v∈SF
(k)
where we have discarded the sum over v ∈ Sj ⋆ since (47) gives that this adds a negative contribution. ⊤ (k) e j ⋆ xi Since this holds for all i ∈ SF and for all t ∈ [τ2 , τ3 ], we have that f (t) := max (k) w obeys i∈SF
+
the inequality √ ′ 1 f ′ (t) ≤ E (k) 1 + 2 nαε , log(1/α) where again we have estimated f (t)2 by plugging in the assumed bound on alignment. Differentiability almost everywhere follows from Rademacher’s theorem. Integration gives
f (t) <
√
2α
ε/24
√
+ 1 + 2 nα
ε′
Z t log(1/α)
E (k) ds.
τ2
We proceed to estimate (12), which we recall for convenience is 2 d 1 X X 1 ⊤ (k) ejw e⊤ E (k) ≤ − Ai,j ∥w ej ∥2 Dj⊤ w . j xi xi E 2 log(1/α) dt n (k) (k) i∈SF
j∈NU
45
(49)
(k)
(k)
We can again discard the sum over j ∈ NF , leaving only the cases j = j ⋆ and j ∈ NU \ {j ⋆ }. For the latter, we apply Proposition 3 in a similar manner to the previous phase to get −
1 X n (k) i∈SF
X (k)
j∈NU \{j ⋆ }
m ⊤ (k) ejw e⊤ Ai,j ∥w ej ∥2 Dj⊤ w ≤ j xi xi E n
p
2L(0)α2cU E (k) .
(50)
For the case j = j ⋆ , we obtain the estimate
−
1 X ⊤ (k) e⊤ e j⋆ w Ai,j ⋆ ∥w ej ⋆ ∥2 Dj⊤⋆ w j ⋆ xi xi E n (k) i∈SF
≤ n
(k) Dj ⋆
′
− αε /4
r
2L(0) 1 X ⊤ (k) e⊤ Ai,j ⋆ w j ⋆ xi xi E n n (k) i∈SF
(k)
≤ Dj ⋆
p
2L(0)f (t) E (k) .
(51)
where in the final line we apply the Cauchy-Schwarz inequality. Inserting (51) and (50) into (12), we get
Z t p √ ε/24 √ ε′ d (k) (k) (k) 2L(0) log(1/α) 2α + 1 + 2 nα log(1/α) E ≤ Dj ⋆ E ds dt τ2 mp + 2L(0) log(1/α)α2cU n Z t p p (k) (k) 2L(0) log(1/α)αε/24 + 2 Dj ⋆ 2L(0) log(1/α)2 E (k) ds, < 2 Dj ⋆ τ2
for α sufficiently small. Again, we have a differential inequality of the form F ′′ < pF + q, for which we employ Lemma 10:
q √ ′ F (t) < √ + F (τ2 ) exp ( p(t − τ2 )) p 1/2 1/2 p p (k) (k) 2 Dj ⋆ < 2L(0) αε/24 + αε/6 expα − 2 Dj ⋆ 2L(0) (t − τ2 ) 1/2 ′ p ε (k) < αε/25 expα − 2 Dj ⋆ 2L(0) (k) Dj ⋆ ′
(2)
′
< α3ε /2 ,
(52)
provided ε′ is selected sufficiently small depending on ε. We may now plug (52) back into (49) to get that for t ∈ [τ2 , τ3 ],
46
⊤
e j ⋆ xi < max Ai,j ⋆ w
√
(k)
Z t √ ′ 2αε/24 + 1 + 2 nαε log(1/α) E (k) ds
i∈SF
<
τ2
√
√
2αε/24 + 1 + 2 nαε
′
′
log(1/α)α3ε /2
ε′ (k)
Dj ⋆ ′
< α5ε /4 ,
(53)
where the final inequality is valid for ε′ sufficiently small depending on ε and for α sufficiently small. □ (k)
⊤
e j ⋆ xi < Proof of Item 5. To estimate the alignment of neuron j ⋆ , we have from (53) that if i ∈ SF then w 5ε′ /4 α . Combined with (52), we have
⊤ 2 2 1 d e ⊤ (k) (k) e j ⋆ Dj(k) − w wj ⋆ Dj ⋆ = Dj ⋆ ⋆ log(1/α) dt 1 X (k) (k) ⊤ e e⊤ ⋆ − D w w hθe(xi ) x⊤ D − x ⋆ ⋆ ⋆ j j i i j j n (k) i∈Sj ⋆
−
1 X (k) (k) ⊤ e e⊤ (hθe(xi ) − yi ) x⊤ i Dj ⋆ − xi w j ⋆ w j ⋆ Dj ⋆ n (k) i∈SF
⊤ 2 e j ⋆ Dj(k) − w ⋆ 1 X (k) (k) ⊤ e e⊤ ⋆w ⋆D ⋆ − w hθe(xi ) x⊤ D − x ⋆ j j i i j j n (k) 2
(k)
> Dj ⋆
i∈Sj ⋆
(k)
− 2 Dj ⋆
′
α11ε /4 .
(54) (k)
As in the previous section, we apply the bound on the norms of all neurons j ∈ NU \ {j ⋆ } to get 1 X (k) (k) ⊤ e e⊤ hθe(xi ) x⊤ i Dj ⋆ − xi w j ⋆ w j ⋆ Dj ⋆ n (k) i∈Sj ⋆
X 1 X ⊤ ⊤ (k) (k) ⊤ e e⊤ e j ⋆ xi + e j xi x⊤ = ∥w ej ⋆ ∥2 w Ai,j ∥w ej ∥2 w i Dj ⋆ − xi w j ⋆ w j ⋆ Dj ⋆ n ⋆ (k) j̸=j
i∈Sj ⋆
<
1 (k) e⊤ ∥w ej ⋆ ∥2 w j ⋆ Dj ⋆ 1 − n
X
e⊤ w j ⋆ xi
1 (k) e⊤ ∥w ej ⋆ ∥2 w j ⋆ Dj ⋆ n
(k) 2c + 2m Dj ⋆ α U
(k)
i∈Sj ⋆
=
2
X
e⊤ w j ⋆ xi
2
(k) 2c + 2m Dj ⋆ α U
(k)
i∈S / j⋆
(k)
< n Dj ⋆
2
′
(k)
α5ε /2 + 2m Dj ⋆
α2cU ,
47
(55)
where in the final inequality we used (53) and (46). Putting (55) into (54), we have for t ∈ [τ2 , τ3 ] and for α sufficiently small that ⊤ 2 2 ′ 1 d e ⊤ (k) (k) e j ⋆ Dj(k) − w − α2ε . wj ⋆ Dj ⋆ > Dj ⋆ ⋆ log(1/α) dt From the initial conditions provided by Item 4 combined with the inequality for t ∈ [τ2 , τ3 ] (k) (k) e⊤ w j ⋆ Dj ⋆ > Dj ⋆
1 − αε
′
√
1 − x2 > 1 − x, we obtain
,
which implies the required alignment for α sufficiently small. □ (k)
Proof. Proof of Item 2 We verify that the norms of neurons in the set NF did not change significantly on the interval [τ1 , τ2 ], which will lead us to conclude in combination with Proposition 3 that (45) did not fail on this interval. Item 2 Lemma 5 provides upper and lower bounds on the norms of neurons in (k) the set NF at time τ2 . In light of these initial conditions and the bound on the loss on data in the set (k) SF given in (44), identical workings to those yielding (16) give r n
(k) Dj
−α
ε′ /2
r < ∥w ej ∥ <
(k)
n Dj
′
+ αε /2
for all t ∈ [τ2 , τ3 ] for α sufficiently small. □ Proof of Item 6. For this point, we simply note that (48) in the proof of Item 1 Lemma 6 gives that if no (k)
other condition in the definition of τ3 breaks then it must be that ∥w ej ⋆ (τ3 )∥ = n Dj ⋆
′
− αε /4 .
This completes the proof of Lemma 6.
D.5
□ ■
Phase 3: Realignment and slow growth
Define the time
n ′ (k+1) τ4 := inf t ≥τ3 ∃ i ∈ SF s.t. |hθe(xi ) − yi | ≥ αε /6
(56)
(k)
(k)
or ∃ j ∈ NF s.t. ∥w ej ∥ > 2 max Dj j∈[m]
o^
τ3 +
^
(k)
2 r τ1 + 2
(k+1)
3ε (k) Dj ⋆
n cU 2L(0)
. (k+1)
This phase is that during which neurons in the set NU \ {j ⋆ } = NU realign in directions Dj to respond to the fact that neuron j ⋆ has grown to reduce the loss on the data on which it is active. We will find that τ4 = τ3 + 3ε(k) , and combining this with the bounds on the duration of phases 2a 2 Dj ⋆
48
(k+1)
and 2b, we will see that the norms of the neurons in the set NU did not change significantly on the interval [τ1 , τ4 ]. This choice is motivated by the lower bound on τ1 afforded to us by (22), as we can then guarantee that τ4 > tk+1 . The reader may note that in the lemma below, we do not track the alignment (k+1) of neuron j ⋆ , the reason being that it is now a member of the set SF . As noted before Lemma 5, we can avoid laboriously tracking the alignment of all of these neurons throughout each phase, because this is not necessary to ensure the loss on fitted data remains small. Once this has been done, we will be able to estimate the alignment across several phases at once, using the alignment at time τ3 as the initial (k) condition for neuron j ⋆ and the alignment at time τ1 as the initial condition for neurons in the set NF . Lemma 7. Suppose that Hypothesis 1 holds. Then for all κ ∈ (tk , tk+1 ), there exists ε∗ > 0 such that for all ε ∈ (0, ε∗ ) there exists ε′∗ such that for all ε′ ∈ (0, ε′∗ ) then there exists α∗ > 0 such that for all α ∈ (0, α∗ ) the following are true: 1. tk+1 < τ4 < tk+1 +
4ε (k) Dj ⋆
+
ε′ (k) Dj ⋆
.
(k+1)
′
, ∀t ∈ [τ3 , τ4 ], |hθe(xi ) − yi | < αε /6 . r r ′ (k+1) (k) (k) ε′ /8 3. ∀j ∈ NF , ∀t ∈ [τ3 , τ4 ], n Dj −α < ∥w ej ∥ < n Dj + αε /8 2. ∀i ∈ SF
(k+1)
4. ∀j ∈ NU
⊤
(k+1)
e j (τ4 )Dj , w
(k+1)
5. ∀i ∈ NU , ∀t ∈ [τ1 , τ4 ], q (k) 2L(0) ε D + + j 2 n
′
> 1 − αε /15 . ζj (ε, ε′ ) :=
ℓ◦j (t) + logα (∥w e ∥) < ζj (ε, ε′ ), where j ′ 9ε + ε(k) . (k)
2 Dj ⋆
Dj ⋆
Proof. The reader should note it will be convenient to derive the bounds in Item 1 Lemma 7 as consequences of analyses for the other points, as it is not possible to derive the upper and lower bounds at the same time. Proof of Item 2. For an upper bound on τ4 , combining the upper bound on τ1 provided by Item 4 Lemma 4, the upper bound on τ2 provided by Item 1 Lemma 5, and the upper bound on τ3 provided by Item 1 Lemma 6, we conclude that
τ4 < τ1 +
3ε (k) Dj ⋆
< tk+1 +
ε′
+
4ε (k)
+
(k) Dj ⋆
+
Dj ⋆
3ε
(57)
(k)
2 Dj ⋆
ε′ (k)
.
Dj ⋆
As ε and ε′ are arbitrary, we may select these quantities sufficiently small that τ3 + 3ε(k) < τ1 + 2 Dj ⋆ q n 2 2L(0) cU . In this case, we may apply Proposition 3 to bound the norms of the neurons in the set (k)
(k)
NU \ {j ⋆ }. Therefore, we have on [τ3 , τ4 ] the bound ∥w ej ∥ < αcU for all j ∈ NU \ {j ⋆ }. To determine ⋆ the loss on data fitted by neuron j , this observation combined with Item 5 and Item 6 Lemma 6 implies ′ ′ (k) that for i ∈ Sj ⋆ , |hθe(xi ) − yi | ≲ αε /4 . Furthermore, by definition of τ3 , E (k) (τ3 ) < αε . From these facts we conclude that for α sufficiently small, ′
E (k+1) (τ3 ) < αε /5 .
49
We now use arguments similar to those employed in the proof of Item 1 Lemma 4 to control the residual on fitted data. The same reasoning used to obtain (12) leads us to conclude 2 1 1 d E (k+1) ≤ − 2 log(1/α) dt n
⊤ (k+1) ejw e⊤ Ai,j ∥w ej ∥2 Dj⊤ w . j xi xi E
X
X (k+1)
i∈SF
(k+1)
j∈NU
We use Proposition 3 to obtain the estimate mp d E (k+1) ≤ 2L(0) log(1/α)α2cU dt n ′ < αε , where the final inequality is valid for α sufficiently small and differentiability almost everywhere follows from Rademacher’s theorem. Integration yields ′
′
E (k+1) < αε /5 + (τ4 − τ3 )αε . Hence, ′ ′ max |hθet (xi ) − yi | < n αε /5 + ε′ αε (k+1)
i∈SF
′
< αε /6 , as claimed.
□ (k)
Proof. Proof of Item 3 We verify that the norms of neurons in the set NF did not change significantly on the interval [τ3 , τ4 ], which will lead us to conclude in combination with Proposition 3 that the condition on neurons’ norms did not fail on this interval. Item 2 Lemma 6 and Item 6 provide upper and lower (k+1) bounds on the norms of neurons in the set NF at time τ3 . In light of these initial conditions and the (k+1) bound on the loss on data in the set SF given in (56), identical workings to those yielding (16) give r
(k)
n Dj
′
− αε /8 < ∥w ej ∥ <
r
(k)
n Dj
′
+ αε /8
for all t ∈ [τ3 , τ4 ] for α sufficiently small. Since none of the other conditions in the definition of τ4 break, as a result of our analysis so far, we conclude that τ4 = τ3 + 3ε(k) . This leads to the easy lower bound 2 Dj ⋆
τ4 > τ1 +
3ε (k)
2 Dj ⋆
> tk+1 , where the first inequality is by definition of τ2 , τ3 , and τ4 and the second is from the lower bound on τ1 provided by Item 4 Lemma 4 □ 50
Proof of Item 4. We verify that by time τ3 +
(k+1)
3ε (k) 2 Dj ⋆
, the neurons in the set NU
have realigned. We (k+1)
first check that in the interval [τ1 , τ3 ], no such neurons deactivated on the data in the set Sj . We d ⊤ 1 ⊤ recall that dt w ej xi = − n 1 wj xi > 0 log(1/α)(hθt (xi ) − yi ) ∥w ej ∥. By (23), on [τ1 , τ3 ] we had for every (k+1)
i ∈ SU that hθt (xi ) − yi ≤ 0 for α sufficiently small. From the alignment at time τ1 given by Item 2 Lemma 4 we conclude that no deactivation occurred. Similarly to the proof of Lemma 3, we estimate ⊤ 2 2 1 d e ⊤ (k+1) (k+1) e j Dj(k+1) − w w j Dj = Dj log(1/α) dt 1 X (k+1) e e ⊤ (k+1) hθe(xi ) x⊤ − x⊤ − i Dj i w j w j Dj n (k+1) i∈Sj
−
1 n
(k+1) e e ⊤ (k+1) (hθe(xi ) − yi ) x⊤ − x⊤ i Dj i w j w j Dj
X (k+1)
i∈SF
(k+1)
> Dj
2
⊤ 2 e j Dj(k+1) − w (k+1)
(k+1)
′
α2cU − 2 Dj αε /6 ⊤ 2 2 ′ (k+1) e j Dj(k+1) − αε /7 , − w > Dj − 2m Dj
where the final inequality is valid for α sufficiently small. Similar workings to those which led to (5) give τ3 + e⊤ w j
3ε (k) Dj ⋆
2
Dj(k+1)
>
(k+1)
Dj
(k+1)
> Dj
′
− αε /14
1 − expα Dj(k+1) − ε′ /14
3ε (k)
2 Dj ⋆
′
− αε /15 ,
where the final inequality is valid for ε′ selected sufficiently small dependent on ε (and α sufficiently small in turn). □ Proof of Item 5. At this point, we are in a position to estimate the deviation of the norms of the neurons (k+1) j ∈ NU from that predicted by Algorithm 1. A simple Grönwall argument gives that q
2L(0)
n ∥w ej (τ4 )∥ ≤ ∥w ej (τ1 )∥α−(τ4 −τ1 ) r ′ ε 2L(0) 9ε ε , < expα −ℓ◦j (τ1 ) − − + (k) (k) 2 n 2 Dj ⋆ Dj ⋆
(58)
where above we have combined (21) with the upper bound on τ4 −τ1 from (57). Note that |ℓ◦j (t)−ℓ◦j (t′ )| ≤ (k)
Dj
(t − t′ ) for any t, t′ ∈ (tk , ∞). Using (57) again, we get 51
(k)
| − ℓ◦j (τ1 ) + ℓ◦j (τ4 )| < Dj
|τ1 − τ4 | 9ε
(k)
< Dj
(k)
(k+1)
∥w ej (τ4 )∥ < expα −ℓ◦j (τ4 ) −
ε − 2
+
r
(k)
+
Dj
2L(0) n
.
(k)
2 Dj ⋆
Putting (59) back into (58), we conclude that for any j ∈ NU
ε′ Dj ⋆
(59)
and for any t ∈ [τ1 , τ4 ],
!
9ε 2
(k) Dj ⋆
+
′
ε
(k)
Dj ⋆
.
(60)
For the converse inequality, we argue in an identical fashion to obtain
ε ∥w ej (τ4 )∥ > expα −ℓ◦j (τ4 ) + + 2
r
(k)
Dj
+
2L(0) n
!
9ε (k)
+
2 Dj ⋆
ε′ (k)
Dj ⋆
.
(61)
□ This completes the proof of Lemma 7.
■
We can now provide a result from which Lemma 2 follows as a corollary. We will verify that the alignment, norm, and residual conditions propagate forwards after the jump having applied Lemma 7. (k+1) We will also verify that the norms of neurons in the set NU consequently grow at a rate close to that predicted by Algorithm 1 after the jump. Define for any κ′′ ∈ (tk+1 , tk+2 ) the time n ′ (k+1) e⊤ ≤ 1 − αε /32 τ5 := inf t ≥τ4 ∃ j ∈ [m] s.t. w j Dj (k+1)
or ∃ i ∈ SF
′
s.t. |hθe(xi ) − yi | ≥ αε /8
(k+1) or ∃ j ∈ NF s.t. ∥w ej ∥ > 2 max j∈[m] (k+1)
or ∃ j ∈ NU
s.t. ∥w ej ∥ ≥ αε
′
o^
(62)
(k+1) Dj
(63)
κ′′
(64)
This phase is very similar to that described in Appendix D.2, in that it is also a period of slow growth during which the network parameters do not change significantly. Indeed, the structure of the proof is almost identical to that of Lemma 4. Lemma 8. For all κ and κ′′ such that κ ∈ (tk , tk+1 ) and κ′′ ∈ (tk+1 , tk+2 ), there exists ε∗ such that for all ε ∈ (0, ε∗ ) there exists ε′∗ such that for all ε′ ∈ (0, ε′∗ ) there exists α∗ such that for all α ∈ (0, α∗ ) the following are true: 1. τ5 = κ′′ . (k+1)
2. ∀i ∈ SF
′
, ∀t ∈ [τ4 , τ5 ], |hθe(xi ) − yi | < αε /8 .
52
⊤
(k+1)
′
e j Dj 3. ∀j ∈ [m], ∀t ∈ [τ4 , τ5 ], w > 1 − αε /32 r r ′ (k+1) (k) (k) ε′ /10 −α < ∥w ej ∥ < n Dj + αε /10 . 4. ∀j ∈ NF , ∀t ∈ [τ4 , τ5 ], n Dj (k+1)
5. ∀j ∈ NU Lemma 7.
ej ∥) < ζj (ε, ε′ ) + ε′ , where ζj (ε, ε′ ) is as defined in ℓ◦j (t) + logα (∥w
, ∀t ∈ [τ4 , τ5 ],
Proof. Given any κ′′ ∈ (tk+1 , tk+2 ), Item 1 Lemma 7 guarantees that we may select ε and ε′ sufficiently small that τ4 < κ′′ . Assume that this has been done and that α has been selected sufficiently small that all of the conditions of Lemma 7 hold. It remains to check that all of these conditions remain stable for t ∈ [τ4 , κ′′ ]. Proof of Item 2. In a similar manner to workings for pervious phases, we have only to estimate 2 1 d 1 E (k+1) ≤ − 2 log(1/α) dt n
(k+1)
X
X
(k+1)
i∈SF
⊤
(k+1) ejw e j xi x⊤ Ai,j ∥w ej ∥2 Dj⊤ w . i E
(k+1)
j∈NU
(k+1)
From the uniform bound on j ∈ NU ′ mα2ε . Hence,
given by (64), we have for i ∈ SU
that on [τ4 , κ′′ ], |hθe(xi )| <
′ d mp 2L(0) log(1/α)α2ε . E (k+1) ≤ dt n
Integration implies that
′
E (k+1) < αε /6 +
′ mp 2L(0) log(1/α)α2ε (κ′′ − τ4 ). n
Hence, ′ ′ mp 2L(0) log(1/α)α2ε (κ′′ − τ4 ) max |hθe(xi ) − yi | < n αε /6 + (k+1) n i∈SU ′
< αε /8 for α sufficiently small, as required.
□ (k+1)
(k+1)
Proof of Item 3. We again split this argument into the cases j = j ⋆ , j ∈ NF \ {j ⋆ }, and j ∈ NU . (k+1) ⋆ For the case j ∈ NF \ {j }, note that Item 2 Lemma 4 provides an initial condition for the alignment (k+1) (k+1) (k) of these neurons in the directions Dj (since for such neurons, Dj = Dj by construction). We can reuse arguments similar to those which led to (13) to obtain
(k+1)
2 Dj 1 d e ⊤ (k) √ wj Dj > − log(1/α) dt n ′
′
αε /8 ,
given that ∥E (k) ∥ < αε /8 for t ∈ [τ1 , τ5 ]. Integrating over this time interval, we get 53
(k+1)
2 Dj √
(k) (k) e⊤ e⊤ w >w j Dj j (τ1 )Dj −
′
log(1/α)αε /8 (τ5 − τ1 )
n
(k+1)
>
(k+1) Dj (k)
> Dj
1−α
ε/2
2 Dj √ −
′
log(1/α)αε /8 (τ5 − τ1 )
n
′ 1 − αε /9 ,
where the final inequality is valid for α sufficiently small. For the case j = j ⋆ , note that Item 5 Lemma 6 (k) provides an initial condition for the alignment of neuron j ⋆ in the direction Dj ⋆ (where again we have (k+1)
(k)
(k+1)
= Dj ⋆ by construction). Identical reasoning to the case j ∈ NF \ {j ⋆ }, except integrating ⊤ ′ e j (τ3 )Dj(k+1) > Dj(k+1) 1 − αε , gives the desired lower bound from τ3 to τ5 with initial conditions w Dj ⋆
(k+1)
for α sufficiently small. For the case j ∈ NU
, we have
⊤ 2 2 1 d e ⊤ (k+1) (k+1) e j Dj(k+1) = Dj − w wj Dj log(1/α) dt 1 X (k+1) e e ⊤ (k+1) − hθe(xi ) x⊤ − x⊤ i Dj i w j w j Dj n (k+1) i∈Sj
−
1 n
(k+1) e e ⊤ (k+1) Ai,j (hθe(xi ) − yi ) x⊤ − x⊤ i Dj i w j w j Dj
X (k+1)
i∈SF
(k+1)
> Dj
2
⊤ 2 e j Dj(k+1) − w ′
(k+1)
(k+1)
mα129ε /64 − 2 Dj ⊤ 2 2 ′ (k+1) e j Dj(k+1) − αε /8 . > Dj − w − 2 Dj
′
α9ε /64
By similar arguments to previous phases, wehave convergence of alignment monotonically for t ∈ (k+1)
[τ4 , τ5 ] to a value lower bounded by Dj from Item 4 Lemma 7, we conclude that
′
1 − αε /16 . Combining this with the initial conditions
(k+1) (k+1) e⊤ w > Dj j Dj
′
1 − αε /32
for all t ∈ [τ4 , τ5 ] provided α is selected sufficiently small.
□ (k)
Proof. Proof of Item 4 We verify that the norms of neurons in the set NF did not change significantly on the interval [τ4 , τ5 ], which will lead us to conclude in combination with (64) that (63) did not fail on this interval. Item 3 Lemma 7 provides upper and lower bounds on the norms of neurons in the set (k+1) (k+1) NF at time τ4 . In light of these initial conditions and the bound on the loss on data in the set SF given in (62), identical workings to those yielding (16) give r n
(k) Dj
−α
ε′ /10
r < ∥w ej ∥ <
54
(k)
n Dj
′
+ αε /10
for all t ∈ [τ4 , τ5 ] for α sufficiently small. □ (k+1)
Proof of Items 1 and 5. To estimate the growth of any neuron j ∈ NU those which yielded (17) in the proof of Lemma 4 to obtain
, we follow similar arguments to
√ ′ ′ ′ 1 d (k+1) − αε /32 − mα2ε ∥w ej ∥ − 2α9ε /64 ∥w ∥w ej ∥ > Dj ej ∥ log(1/α) dt ′ (k+1) ej ∥. − αε /33 ∥w > Dj Grönwall’s inequality yields for α sufficiently small the inequalities
(k+1)
∥w ej (t)∥ > ∥w ej (τ4 )∥α ◦
− Dj ′
(t−τ4 )+ε′
′
> α−ℓj (t)+ζj (ε,ε )+ε , where in the second inequality we inserted (61). Analogous arguments yield the claimed upper bound ◦
′
′
∥w ej (t)∥ < α−ℓj (t)−ζj (ε,ε )−ε , (k+1)
where we have inserted (60). By construction, for every j ∈ NU , −ℓ◦j (κ′′ ) > 0. Therefore, we may ′ ′′ ε′ select ε and ε sufficiently small that for all such j, ∥w ej (κ )∥ < α . For this choice of ε and ε′ , we ′′ conclude that necessarily τ5 = κ , since none of the other conditions in the definition of τ5 break. □ This completes the proof of Lemma 8.
D.6
■
Final Saddle
We provide a lemma which is a version of Lemma 1 for t > tp . Specifically, we prove uniform convergence under the assumption the conditions of Hypothesis 1 hold at some time κ > tp . Lemma 9. Suppose that for some κ ∈ (tp , ∞), there exists δ > 0 such that for all ξ > 0, there exists α∗ > 0 such that for all α ∈ (0, α∗ ): (p)
1. ∀j ∈ NU , ℓ◦j (κ) + logα (∥w ej (κ)∥) < ξ. (p)
(p)
2. ∀j ∈ NF , n Dj
− ∥w ej (κ)∥2 < αδ .
3. ∀i ∈ [n], |hθ(κ) (xi ) − yi | < αδ . e ⊤
(p)
e j (κ)Dj 4. ∀j ∈ [m], w
> 1 − αδ .
Then given any κ′ ∈ [κ, ∞), θeα converges uniformly to θ◦ on [κ, κ′ ]. Proof. We note that Item 3 Lemma 9 and the monotonicity of the gradient flow imply that for all j ∈ [m] αδ and for all t ∈ [κ, ∞), ∥Dj ∥ < √ . To estimate the change in the network parameters from κ to κ′ , we n have that for each j ∈ [m],
55
1 d αδ ej ∥. ∥w ej ∥ < √ ∥w log(1/α) dt n Grönwall’s inequality gives
αδ ∥w ej ∥ < ∥w ej (κ)∥ exp log(1/α) √ (t − κ) n δ α ′ < ∥w ej (κ)∥ exp log(1/α) √ (κ − κ) n δ/2 < ∥w ej (κ)∥ exp α < ∥w ej (κ)∥ 1 + αδ/2 ,
(p)
where the last two inequalities are small. For j ∈ NU , we obtain that for α valid for α sufficiently 1 ◦ (p) −ℓj (κ) 2 minj∈NU
sufficiently small, ∥w ej ∥ < 2 expα
, by selecting ξ < 12 minj∈N (p) −ℓ◦j (κ) in Item 1 U
(p)
Lemma 9. Noting that for ∈ NU , −ℓ◦j (κ) > 0, we conclude that such neurons converge uniformly to (0)j∈N (p) . Analogous arguments yield the lower bound U
∥w ej ∥ > ∥w ej (κ)∥ 1 − αδ/2 . (p)
For j ∈ NF and α sufficiently small, we use Item 2 Lemma 9 to obtain r n
(k) Dj
−α
δ/3
r < ∥w ej ∥ <
(k)
n Dj
+ αδ/3 .
(65)
(p)
For alignment of neurons j ∈ NF , we obtain
(k)
2 Dj 1 d e ⊤ (k) w j Dj > − √ log(1/α) dt n
αδ .
Simple integration yields
(p)
(p) (p) e⊤ e⊤ w >w j Dj j (κ)Dj −
2 Dj √ n
αδ (t − κ) (p)
>
(p) Dj (p)
> Dj
2 Dj 1−α − √ n δ/2 1−α , δ
αδ (κ′ − κ) (66) (k)
where the final inequality is valid for α sufficiently small. Combining (65) and (66), we get for j ∈ NF 56
(p)
e aj w ej − nDj
2
(p)
= ∥w ej ∥4 + n2 Dj r
(p)
n Dj
<
− 2n
2
(p)
− 2ne aj w ej⊤ Dj !4 + n2 Dj
!2
r
(p) Dj
2
(p)
+ αδ/3
n
(p) Dj
−α
δ/3
1 − αδ/2
< αδ/4 ,
(67)
for α sufficiently small. This yields the required uniform convergence on [κ, κ′ ] for neurons in the set (p) NF . ■
D.7
Proof of Theorem 2
In this section, we prove Lemma 1 and Lemma 2 using the multiphase analysis of the previous subsections. Once these two lemmas are proven, it will be possible to provide a short proof of Theorem 2. The proof of Lemma 1 is a fairly direct application of Lemma 4 (and in the case of the final saddle, the proof is provided in Lemma 9). Proof of Lemma 1. From item 4 Lemma 4, we conclude there exists ε sufficiently small such that there (k) exists α sufficiently small that τ1 > κ′ . For such ε and α, we have by definition of τ1 that for all j ∈ NU (k) and for all t ∈ [κ, κ′ ], ∥w ej ∥ < αε . As a consequence, neurons in the set NU converge uniformly to (k) (0)j∈N (k) . For the neurons in the set NF , we follow similar workings to those leading to (67). The U combination of Item 2 Lemma 4 and Item 3 Lemma 4 imply
(k)
e aj w ej − nDj
2
4
= w ej r <
2
(k)
+ n2 D j (k)
n Dj − 2n
+ αε/4 r
(k) Dj
(k)
− 2ne aj w ej⊤ Dj !4
n
(k)
+ n2 Dj
2
!2 (k) Dj
− αε/4
1 − αε/2
< αε/5 , (k) for α sufficiently small. Therefore, (e aj w ej )j∈N (k) converges uniformly to nDj F
(k)
j∈NF
on [κ, κ′ ].
■
Next, we prove Lemma 2, which recovers Hypothesis 1 at saddle k + 1 and allows us to construct the argument for uniform convergence of the whole process. To prove this lemma, we require that given any any κ′′ ∈ (tk+1 , tk+2 ) (where we will take the convention that tp+1 = ∞), there exists δ ′′ > 0 such that for all ξ ′′ > 0, there exists α∗ > 0 such that for all α ∈ (0, α∗ ): (k+1)
, ℓ◦j (κ′′ ) + logα (∥w ej (κ′′ )∥) < ξ ′′ .
(k+1)
, n Dj
1. ∀j ∈ NU 2. ∀j ∈ NF
(k+1)
3. ∀i ∈ SF
(k+1)
− ∥w ej (κ′′ )∥2 < αδ
′′
′′
δ , |hθ(κ e ′′ ) (xi ) − yi | < α .
57
⊤
(k+1)
e j (κ′′ )Dj 4. ∀j ∈ [m], w
′′
> 1 − αδ .
The proof consists of two applications of Lemma 8: one choice of ε, ε′ in order to get the existence of δ ′′ such that the alignment, norm, and loss conditions all hold at time κ′′ ; the other choice of ε, ε′ in order to get the arbitrary precision of the norms of the unfitted neurons. That the same choice does not work to get all of the points at once is a result of the fact that our analysis ends up linking the alignment, norm, and loss conditions with the precision of the unfitted neurons’ norms, so it is impossible to prove Lemma 2 with a single choice of ε, ε′ (otherwise one would have to have δ ′′ depending on ξ ′′ ). Proof of Lemma 2. Note that Lemma 8 immediately guarantees that for ε0 sufficiently small, for ε′0 sufficiently small, and for α sufficiently small Item 4, Item 2, and Item 3 immediately above all hold with δ ′′ = ε′0 /32. For Item 4 immediately above, we note that Item 5 Lemma 8 states that for ε sufficiently ◦ ′′ ′ ′ small one can choose ε′ sufficiently small that for α sufficiently small, α−ℓj (κ )+ζj (ε,ε )+ε < ∥w ej (κ′′ )∥ < ′′ ′ ′ (k+1) −ℓ◦ (κ )−ζ (ε,ε )−ε j α j . Simply choosing ε1 and ε′1 such that |ζj (ε1 , ε′1 ) + ε′ | < ξ ′′ for all j ∈ NU gives the claim. ■ Finally, we are able to provide a proof of Theorem 2. This proof consists of iteratively concluding uniform convergence on arbitrary closed intervals contained in (tk , tk+1 ) using Hypothesis 1, and then using Lemma 2 to apply the same reasoning to the next interval. Proof of Theorem 2. Let S ⊂ R \ {t0 , t1 , . . . , tp } be a compact set. By compactness, there exists a cover of p S by disjoint closed intervals ([κk , κ′k ])k=0 whose satisfy κk , κ′k ∈ (tk , tk+1 ). We note from endpoints q n Lemma 3 that Hypothesis 1 holds for any κ0 ∈ 0, 14 2L(0) . From Lemma 1, we obtain that for such κ0 and for any κ′0 ∈ (κ0 , t1 ), θe converges uniformly to θ◦ = 0. Furthermore, we have from Lemma 2 that for any κ1 ∈ (t1 , t2 ), Hypothesis 1 also holds. Iterating this argument, we can use Lemma 1 to conclude that there exists αk∗ > 0 such that θe converges uniformly to θ◦ on [κk , κ′k ] with rate αδk for some δk > 0, followed by Lemma 2 to conclude that Hypothesis 1 holds at each κk+1 ∈ (tk+1 , tk+2 ). Since the number of saddles is finite, we may select α ∈ (0, mink∈[p] αk∗ ) so that each application of Lemma 1 and Lemma 2 ∗ holds. This gives the claimed uniform convergence, the rate of which is αδ where δ ∗ = mink∈[p] δk∗ . ■
E
Proof of Theorem 3
We consider in this section the setting where we have only positive labels and condition all the probabilities on the fact that ai > 0 for all i ∈ [m]. The argument generalizes directly to the case of mixed signs, by treating positive and negative labels separately. Recall that Theorem 3 provides a bound on the squared ℓ2 -norm of θpred , which satisfies X 1 (p) ∥θpred ∥2 = n∥Dj ∥2 2 j∈[m] X v u X u yi2 = t j∈[m]
=
(p)
i∈Sj
Xv u u t
k∈[p]
X
yi2 .
(k)
i∈SU ∩S (k) j∗
(1)
(p)
Algorithm 1 relies on a specific ordering of the neurons, given by (j⋆ , . . . , j⋆ ), that depends on both the data and initialization scheme. Instead, our proof here considers a fixed ordering π = (j1 , . . . , jm )
58
that is independent of both data and initialization, and aims at bounding X s X yi2 , k∈[m]
(68)
k ∩S i∈SU jk
where we define similarly the sets SUk in a recursive way, as SU0 = [n],
SUk+1 = SUk \ Sjk
Sj = {i ∈ [n] | Ai,j = 1}, i.e., SUk represent the data points that remain to be fitted after increment k, and Sj refers to the data points with which neuron j is positively correlated. Note that when the ordering π coincides with the one induced by j⋆ on its first p elements, eq. (68) is exactly 12 ∥θpred ∥2 . We thus aim at bounding this quantity with high probability over all possible orderings by a union bound argument, which then directly translates to a bound of 12 ∥θpred ∥2 . Note that when initializing the neurons according toAssumption 3, and conditioning on the fact that2 ai > 0, (Ai,j )j∈[m], i∈[n] are independent Bernoulli 21 variables. For each i ∈ [n], we define Yik = 1 i ∈ SUk , which is the random variable that is equal to 1 if the data point i remains to be fitted after increment k. Obviously, we have n X SUk = Yik . i=1
For a fixed δ ∈ (0, 12 ), we define for each k the events ) ( n n n X X 1 X k−1 k−1 k ≤δ Yi . Yi − Y Gk = 2 i=1 i i=1 i=1 The interpretation of the event Gk —which has high probability, as shown below—is that at iteration k of our incremental algorithm (for the fixed ordering π), the cardinality of the set of unfitted data has almost halved from the previous iteration. Finally, denote for some ρ ∈ (0, 12 ), to be fixed later, k⋆ =
(1 − ρ) log(n) . log(2)
For the remainder of the proof, we assume m ≥ k ⋆ to simplify notation and exposition. The upper bounds extend straightforwardly to the case m < k ⋆ by truncating the estimator considered here. 1 Proposition 4. Given any 0 < ρ < 2 and a fixed deterministic ordering π = (j1 , . . . , jm ), for any δ ∈ ρ log(2) 0, 8(1−ρ) and n, 4 P (∀k ≤ k ⋆ , Gk ) ≥ 1 − 3 log(n) exp − nρ/2 δ 2 . 3
Note that as δ approaches zero here, the probability bound degrades to but the events Gk get more P0, n restrictive, as δ controls the relative distance by which the increments i=1 Yik can deviate from their conditional expectation. 2 In the remaining of the section, we omit the conditioning on a > 0 for ease of exposition. i
59
Proof. By conditioning ⋆
P (∀k ≤ k , Gk ) =
⌊k⋆ ⌋
Y
P (Gk | ∀l ≤ k − 1, Gl ) ,
k=1
Our goal is thus for any k ≤ k ⋆ , to lower bound P (Gk | ∀l ≤ k − 1, Gl ). Note that Yik = Yik−1 · Ai,jk by definition. Since the variables (Ai,j )i,j are independent, Ai,jk is independent from (Ai,jl )l≤k−1 for a fixed ordering3 π. Consequently, ! n n X X k−1 1 k Yi (Ai,jl ) i∈[n] ∼ Bin Yi , . 2 l≤k−1 i=1 i=1 Using the multiplicative Chernoff bound [see, e.g., Mitzenmacher and Upfal, 2017, Corollary 4.6], we have for any δ ∈ (0, 12 ): ! ! n n n n X X 4 1 X k−1 2 1 X k−1 k−1 k P ≤δ (Ai,jl ) i∈[n] ≥ 1 − 2 exp − · Yi − Y Yi Y δ 2 i=1 i 3 2 i=1 i l≤k−1 i=1 i=1 Conditioned on the event {∀l ≤ k − 1, Gl }, we have that n X
Yik−1 ≥ n
i=1
1 −δ 2
k−1 ,
so that the previous inequality becomes, when conditioning on this event,
k−1 ! 4 n 1 −δ δ2 P ( Gk | ∀l ≤ k − 1, Gl ) ≥ 1 − 2 exp − · 3 2 2 k⋆ ! 4 1 ≥ 1 − 2 exp − n −δ δ2 . 3 2 ⋆
Using that for any 0 < x < 21 , (1 − 2x)k ≥ 1 − 2k ⋆ x, we get ⋆
P (∀k ≤ k , Gk ) =
⌊k⋆ ⌋
Y
P (Gk | ∀l ≤ k − 1, Gl ) ,
k=1
4 ≥ 1 − 2k exp − n 3 ⋆
1 −δ 2
k⋆
! δ
2
.
(69)
log(n) Now inserting k ⋆ = (1−ρ) , we obtain that log(2)
n
1 −δ 2
k ⋆
k⋆
⋆
= n2−k (1 − 2δ) (1−ρ)
= n1+ρ−1+ log(2) log(1−2δ) > nρ/2 ,
(70)
3 The choice of a fixed ordering is crucial here. If we were to consider the ordering j induced by Algorithm 1, this independence ⋆ argument would not hold anymore.
60
ρ where we here used the upper bound on δ that gives (1−ρ) log(2) log(1 − 2δ) ≥ − 2 . It will be useful for later to note that similar logic allows us to obtain the following inequality, given {∀k ≤ k ⋆ , Gk }:
n and
1 −δ 2
nρ/2 <
k
n X
≤
n X
Yik ≤ n
i=1 ⌊k⋆ ⌋
Yi
1 +δ 2
k
for any k ≤ k ⋆
< 2 · n2ρ .
(71) (72)
i=1
Putting eq. (70) back into eq. (69), we obtain
4 (1 − ρ) log(n) exp − nρ/2 δ 2 log(2) 3 4 ρ/2 2 > 1 − 3 log(n) exp − n δ . 3
P (∀k ≤ k ⋆ , Gk ) ≥ 1 − 2
■
Proposition 4 demonstrates that with high probability, the cardinality of the set SUk decreases by roughly one half for each of the first k ⋆ iterations. Note that we here worked with a fixed, arbitrary ordering π. However, Algorithm 1 selects a specific ordering π that depends on the data. Corollary 1 provides a union bound over all the possible orderings, guaranteeing that the event {∀k ≤ k ⋆ , Gk } holds with high probability for the ordering π returned by Algorithm 1. log(2) Corollary 1. Given any 0 < ρ < 21 , δ ∈ 0, ρ8(1−ρ) and n ∈ N,
⋆
P (∃ π, k ≤ k , ¬Gk ) ≤ 3 log(n) exp
log(n) 4 ρ/2 2 log (m) − n δ . log(2) 3
Proof. Proposition 4 is established for an arbitrary fixed permutation π. We then apply a union bound ⋆ over all injective mappings from [k ⋆ ] to [m], whose total number is at most mk . Thus we directly obtain from Proposition 4 the bound
⋆ 4 P (∃ π, k ≤ k ⋆ , ¬Gk ) ≤ mk · 3 log(n) exp − nρ/2 δ 2 3 4 = 3 log(n) exp k ⋆ log(m) − nρ/2 δ 2 3 (1 − ρ) log(n) 4 = 3 log(n) exp log (m) − nρ/2 δ 2 . log(2) 3
■
In the following, we work under the event {∀k ≤ k ⋆ , Gk } for the considered permutation π and bound the squared ℓ2 -norm of the estimator returned by Algorithm 1 by splitting it into two terms: that induced by the first k ⋆ iterations of the algorithm, and the remaining ones. Proposition 5. If for all i ∈ [n], |yi | ≤ ymax , then q
∀k ≤ k ⋆ , Gk =⇒
X s k≤k⋆
X
k ∩S i∈SU jk
61
yi2 ≤
1 √ 2 +δ q ymax n. 1 1− 2 +δ
Proof. The bound |yi | ≤ M directly implies that X s X X q SUk ∩ Sjk . yi2 ≤ ymax k≤k⋆
k≤k⋆
k ∩S i∈SU jk
Note that {∀k ≤ k ⋆ , Gk } implies that for any k ≤ k ⋆ , |SUk ∩ Sjk | ≤ n if it holds,
k 1 thanks to eq. (71). So that 2 +δ
⋆
X s k≤k⋆
X
yi2 ≤ ymax
k/2 ⌊k ⌋ √ X 1 n +δ 2 k=1
k ∩S i∈SU jk
q
√
≤ ymax n ·
1 2 +δ q . 1 − 12 + δ
■
Finally, we bound the squared ℓ2 -norm of the remaining increments. Proposition 6. If for all i ∈ [n], |yi | ≤ ymax , then ∀k ≤ k ⋆ , Gk =⇒
X s k>k⋆
X
yi2 < 2ymax n2ρ
k ∩S k∈SU jk
Proof. By subadditivity of the square root, we simply have X s X X yi2 ≤ |yi | k>k⋆
⌊k⋆ ⌋
k ∩S i∈SU jk
i∈SU
⌊k⋆ ⌋
≤ ymax |SU
|. ⌊k⋆ ⌋
Now, thanks to eq. (72), we recall that {∀k ≤ k ⋆ , Gk } implies that |SU proof.
| < 2 · n2ρ , which concludes the ■
1 Combining Propositions 5 and 6 and Corollary 1, we conclude taking ρ = 1/4 and δ = 40 that for any n,
X
√ (p) n∥Dj ∥ ≤ 5ymax n
j∈[m]
with probability at least 1 − 3 log(n) exp
log(n) 4 1/8 log(2) log (m) − 3·402 n
.
This concludes the proof when considering only positive labels and neurons. Theorem 3 directly extends to the general case, by separating positive and negative cases.
F
Auxiliary results
We provide in this section auxiliary results that are useful for our analysis, as well as Proposition 2.
62
F.1
Proof of Proposition 2
Proof of Item (i). The proof is a simple union bound. Indeed, observe that 1) (Ai,j )j∈[m] are independent m i.i.d. Bernoulli 14 variables. Then, the probability for a row i to be zero is exactly 34 , so that the m probability that any row is zero is smaller than n 34 . 2) Conditionally on aj , (Ai,j )i∈[n] areindependent variables, each of them being either the deterministic variable 0 if i ̸∈ Isj , or a Bernoulli 12 i ∈ Isj . Since |Isj | ≥ min(n− , n+ ) almost surely by definition, we min(n− ,n+ ) then have that a column j is zero with probability at most 21 . So that the probability for any 1 min(n− ,n+ ) column to be zero is bounded by m 2 . 3) Note that two non-zero columns j and j ′ are equal if and only if both sgn(aj ) = sgn(aj ′ ) and 1(wj⊤ xi ) = 1(wj⊤′ xi ) for all i ∈ Isj . All these variables are independent Bernoulli 12 , so that a union bound argument again yields that the probability for two non-zero columns to be equal is at most m(m−1) 1 min(n− ,n+ )+1 . 2 2 A union bound on these three events and summing the different terms then yields Item (i) of Proposition 2. □ Proof of Item (ii). Similarly to the proof of Theorem 3, we here fix an arbitrary ordering π = (j1 , . . . , jm ), and define an alternative Algorithm 1 with the fixed ordering π, i.e., SU0 = [n],
SUk+1 = SUk \ Sjk
Sj = {i ∈ [n] | Ai,j = 1}. Similarly, we also define the increment times as t′0 = 0, and for any k ≥ 0: t′k+1 = max(t′k − where
ℓ′jk+1 (t′k )
, t′ ) ∥Djkk+1 ∥ k 1 X Djk = yi xi , n k i∈SU ∩Sj
ℓ′j (0) = −1 and ℓ′j
k+1 where ∥D k
(t′k )
jk+1 ∥
ℓ′j (t) = ℓ′j (t′k ) + (t − t′k )∥Djk ∥ for any t ∈ [t′k , t′k+1 ],
= −∞ when ∥Djkk+1 ∥ = 0 by convention. Note that when π coincides with j⋆ on its first (k)
p elements, we have the equality (t0 , . . . , tp ) = (t′0 , t′p ), as well as ℓ′j (t) = ℓ◦j (t) on [0, tp ] and Djk = Dj for k ≤ p.
From there, we can see all t′k , ℓ′j (t) and ∥Djk ∥ as functions of (y1 , . . . , yn ). Consider two neurons j, j † . Since we assume Assumption 4 (i) holds, the columns of the masking matrix A·,j and A·,j † are both non-zero and distinct; and also consider k such that jl ̸∈ {j, j † } for all l ≤ k, i.e., both neurons j and j † have not been selected by the alternative algorithm in the first k increments. From there, we want to show that the following system of inequalities − ∥Djk ∥ > 0
ℓ′j (t′k ) ∥Djk ∥
and
=−
ℓ′j † (t′k )
,
(73)
max(ℓ′j † (t′k ), ℓ′j (t′k )) < 0
(74)
∥Djk† ∥
only holds on a measure zero set for the values of (y1 , . . . , yn ). Indeed, since the two masking columns are different, there exists some i ∈ [n] such that, w.l.o.g., Ai,j = 1 and Ai,j † = 0. We then have two cases.
63
Either i ∈ SUk , i.e., i remains to be fitted at iteration k. In that case, note that all (t′0 , . . . , t′k ), ℓ′j † and ℓ′ (t′ )
j k (Dj0† , . . . , Djk† ) do not depend on the value yi . On the other hand, − ∥D k ∥ decreases (strictly) with |yi |, j
when eq. (74) holds. Indeed, note that −ℓ′j (t′k ) = 1 −
X
(t′l+1 − t′l )∥Djl ∥
and
v u
u1 ∥Djl ∥ = t
X
n ′
l<k
yi2′ .
l ∩S i ∈SU j
ℓ′ (t′ )
j k so that −ℓ′j (t′k ) decreases with |yi | and is positive, while ∥Djk ∥ increases with it. In consequence, − ∥D k∥ j
is a decreasing function of |yi |, so that for fixed values (yi′ )i′ ̸=i , there is at most one value of |yi | such that the system of eqs. (73) and (74) holds. This implies over all labels that the system of eqs. (73) and (74) can only be satisfied on a zero measure set. The other possible case is when for all i such that Ai,j ̸= Ai,j † , i ̸∈ SUk . In other words, this means that SUk ∩ Sj = SUk ∩ Sj † . By definition of the quantities of interest, if the system of eqs. (73) and (74) holds for k, the following system also holds ℓ′j (tk′ ) = ℓ′j † (t′k ), ∥Djk ∥ > 0
and
(75)
max(ℓ′j † (t′k ), ℓ′j (t′k )) < 0,
(76)
where k ≤ k is the largest integer such that SUk ∩ Sj ̸= SUk ∩ Sj † —indeed, for any k < l ≤ k, we would have Djl = Djl † . Now note that we could have chosen i such that Ai,j ̸= Ai,j † and it is the last such i to be fitted by the algorithm. In that case, we necessarily have i ∈ SUk and we are in a case very similar to the one treated above. We can then show with a similar study—which is even simpler here, as we only have to consider the numerator of the previous fraction—that the system of eqs. (75) and (76) only holds for a zero measure set. We thus have proven that the system of eqs. (73) and (74) only holds on a zero measure set for the values of (y1 , . . . , yn ), for a fixed ordering π, iteration k, and neurons j, j † not yet fitted at iteration k. By doing a finite union, it remains true that this system is only satisfied on a zero measure set for all choices of ordering, iterations and neuron couples. In particular, it holds for some ordering that coincides with (1) (p) the one returned by Algorithm 1 on the first p iterations, i.e., (j⋆ , . . . , j⋆ ). For this specific choice of ordering, we observe that the case of a non-unique minimizer of the loop in Algorithm 1 corresponds to a couple satisfying the system of eqs. (73) and (74), such that both neurons have not fitted yet, which concludes the proof of Item (ii) of Proposition 2. □
F.2
Other auxiliary results
The following result estimates the normalized component of w ej in the direction xi under the assumption (k) that this neuron is aligned in direction Dj . (k) e⊤ Proposition 7. For any j ∈ [m] and k ∈ [p], if w > 1 − α, then for all i ∈ [n], j Dj
e⊤ w j xi −
Proof. Let u =
P
i ui xi and v =
(k) 1 yi ∈ Sj yi n
(k) Dj
P
<
√
2α1/2 .
i vi xi be the representations of two unit vectors in the orthonormal
64
basis given by (xi )di=1 such that u⊤ v > 1 − α. We have for any i0 X (ui0 − vi0 )2 ≤ (ui − vi )2 i
=
X
u2i + vi2 − 2ui vi
i
< 2α. Taking square roots yields |ui0 − vi0 | < (k)
Dj
√
2α1/2 . Recalling that 1
=
X (k)
n Dj
(k) 1 yi ∈ Sj yi xi
i∈[n]
gives the claim.
■
The following result applies the preceding proposition to deduce an inequality which will prove useful in our analysis. ⊤
(k)
e j Dj Corollary 2. If w
> 1 − α, then (k)
x⊤ i Dj
(k) e e ⊤ (k) α1/2 − (x⊤ i w j )(w j Dj ) < 2 Dj
for α sufficiently small. Proof. We simply plug in the bounds from Proposition 7 to obtain √ (k) (k) ⊤e e ⊤ (k) − 2 Dj α1/2 < x⊤ i Dj − (xi w j )(w j Dj ) √ yi (k) < α + 2 Dj α1/2 − α3/2 , n from which the claim follows.
■
Lemma 10. Suppose that the following hold: 1. F ∈ C 1 ([T1 , T2 ]) and F ′ is Lipschitz continuous. 2. F ≥ 0 and F (T1 ) = 0. 3. F ′′ (t) ≤ pF (t) + q for almost every t ∈ [T1 , T2 ], where p, q > 0. Then for every t ∈ [T1 , T2 ], F ′ (t) ≤
q √ √ + F ′ (T1 ) exp( p(t − T1 )). p
Proof. Let G = F + q/p. Then G obeys for almost every t ∈ [T1 , T2 ] the differential inequality G′′ < pG. We compute using this inequality that d √ √ √ √ (G′ + pG) ≤ pG + pG′ = p ( pG + G′ ) . dt Since F ′ is Lipschitz continuous, both F ′ and F are in fact absolutely continuous. Therefore, is absolutely continuous. We may apply Grönwall’s inequality to see that 65
√
pG + G′
√
√ √ pG + G′ ≤ exp ( p(t − T1 )) ( pG(T1 ) + G′ (T1 )) .
Noting that G ≥ F , the imposition of the condition that F ≥ 0 gives √ √ G′ ≤ exp ( p(t − T1 )) ( pG(T1 ) + G′ (T1 )) . Substituting F into the above and using the initial condition F (T1 ) = 0, we get F ′ (t) ≤
q √ ′ + F (T ) exp( p(t − T1 )). √ 1 p
as claimed.
■
66