extfieldsofstudy:
Computer Science
Mathematics

text:
Directional convergence and alignment in deep learning

In this paper, we show that although the minimizers of cross-entropy and related classification losses are off at infinity, network weights learned by gradient flow converge in direction, with an immediate corollary that network predictions, training errors, and the margin distribution also converge. This proof holds for deep homogeneous networks -- a broad class of networks allowing for ReLU, max pooling, linear, and convolutional layers -- and we additionally provide empirical support not just close to the theory (e.g., the AlexNet), but also on non-homogeneous networks (e.g., the ResNet). If the network further has locally Lipschitz gradients, we show that these gradients converge in direction, and asymptotically align with the gradient flow path, with consequences on margin maximization. Our analysis complements and is distinct from the well-known neural tangent and mean-field theories, and in particular makes no requirements on network width and initialization, instead merely requiring perfect classification accuracy. The proof proceeds by developing a theory of unbounded nonsmooth Kurdyka-Lojasiewicz inequalities for functions definable in an o-minimal structure, and is also applicable outside deep learning.

Introduction
Recent efforts to rigorously analyze the optimization of deep networks have yielded many exciting developments, for instance the neural tangent (Jacot et al., 2018;Du et al., 2018;Allen-Zhu et al., 2018) and mean-field perspectives (Mei et al., 2019;Chizat and Bach, 2018). In these works, it is shown that small training or even testing error are possible, often by making the network width large.
Practitioners run their optimization methods as long as their computational budget allows (Shallue et al., 2018); by contrast, the above theories, with finite width networks, only hold for some finite amount of time. This leaves open a possibility that the prediction surface can continually change as the number of optimization passes increase; indeed, perhaps most worrisomely, if the data can be perfectly classified, then the parameters are guaranteed to diverge in norm to infinity (Lyu and Li, 2019). Even on simple data, as in Figure 1, the prediction surface continues to change after perfect classification is achieved, and even with large width is not close to the maximum margin predictor from the neural tangent regime. Since the prediction surface continually changes, so do the generalization behavior, adversarial stability, and other crucial properties of the predictor.
In this paper, we resolve this worry by guaranteeing stable convergence behavior of deep networks as training proceeds, despite this growth of weight vectors to infinity. Concretely: 1. Directional convergence: the parameters converge in direction, which suffices to guarantee convergence of many other relevant quantities, such as the prediction margins.

2.
Alignment: under an additional differentiability condition, the gradients also converge in direction, which implies margin maximization in a few settings.   Figure 1a shows the prediction surface reached by freezing activations, which is also the prediction surface of the corresponding Neural Tangent Kernel (NTK) maximum margin predictor (Soudry et al., 2017). Figure 1b shows the same network, but now without frozen activations, at the first moment with perfect classification. Training this network much longer converges to Figure 1c.
linear, convolution, ReLU, and max-pooling layers), but homogeneity rules out some components such as skip connections and biases, which all satisfy definability. We consider binary classification with either the logistic loss log (z) := ln(1 + e −z ) (binary cross-entropy) or the exponential loss exp (z) := e −z , and a standard gradient flow (infinitesimal gradient descent) for non-differentiable non-convex functions via the Clarke subdifferential. We start from an initial risk smaller than 1 /n, where n denotes the number of data samples; in this way, our analysis handles the late phase of training, and can be applied after some other analysis guarantees risk 1 /n.
Under these conditions, we prove the following result, without any other assumptions about the distribution of the parameters or the width of the network (cf. Theorem 3.1).
The curve swept by Wt / Wt has finite length, and thus Wt / Wt converges.
Our main corollary is that prediction margins converge (cf. Corollary 3.2), meaning the normalized per-example values yiΦ(xi;Wt) / Wt L , where y i is the label and Φ(x i ; W t ) is the prediction on example x i . These quantities are central in the study of generalization of deep networks, and their stability also implies stability of many other useful quantities (Bartlett et al., 2017;Jiang et al., 2019Jiang et al., , 2020. As an illustration of directional convergence and margin convergence, we have plotted the margin values for all examples in the standard cifar data against training iterations in Figure 2; these trajectories exhibit strong convergence behavior, both within our theory (a modified homogeneous AlexNet), and outside of it (DenseNet).
Regarding our analysis, the first key point is that directional convergence of gradient flows is false in general; for instance, the homogeneous Mexican Hat function satisfies all our assumptions except definability, but its gradient flow does not converge in direction, instead it spirals (Lyu and Li, 2019). To deal with similar pathologies in many branches of mathematics, the notion of functions definable in some o-minimal structure was developed; these are rich classes of functions built up to limit oscillatory and related bad behavior. Within this literature, the gradient conjecture of René Thom asks when the existence of lim t→∞ W t = z further implies lim t→∞ (Wt−z) / Wt−z exists, and was established in various definable scenarios by Kurdyka et al. (2000aKurdyka et al. ( , 2006 via related Kurdyka-Lojasiewicz inequalities (Kurdyka, 1998). The underlying proof ideas can also be used to analyze lim t→∞ Wt / Wt when the weights go to infinity, but we have to extend their analysis to handle our loss functions log and exp , since they include the exponential function which is not covered by prior work. Using the Clarke subdifferential and results from (Bolte et al., 2007;Davis et al., 2020), we further handle non-differentiable functions. These tools are applicable outside of deep learning.

Second result: gradient alignment
Our second contribution, in section Section 4, is that if the network has a locally Lipschitz gradient, then the gradients also converge, and are aligned to the gradient flow path (cf. Theorem 4.1).
The gradient flow path, and the gradient of the risk along the path, converge to the same direction.   Figure 2a shows "H-AlexNet", a homogeneous version of AlexNet as described in the main text (Krizhevsky et al., 2012), which is handled by our theory. Figure 2b shows a standard DenseNet (Huang et al., 2017), which does not fit the theory in this work due to skip connections, biases, and batch norm, but still exhibits convergence of margins, giving a tantalizing open problem.
As a practical consequence of this, recall the use of gradients within the interpretability literature, specifically in saliency maps (Adebayo et al., 2018): if gradients do not converge in direction then saliency maps can change regardless of the number of iterations used to produce them. As a theoretical consequence, directional convergence and alignment imply margin maximization in a variety of situations: this holds in the deep linear case, strengthening prior work (Gunasekar et al., 2018;Ji and Telgarsky, 2018a), and in the 2-homogeneous network case, with an assumption taken from the infinite width setting (Chizat and Bach, 2020), but presented here with finite width.

Further related work
Our analysis is heavily inspired and influenced by the work of Lyu and Li (2019), who studied margin maximization of homogeneous networks, establishing monotonicity of a smoothed margin, a quantity we also use. Their work left open directional convergence, alignment, and global margin maximization.
Another closely related line of work is on implicit bias and margin maximization (Soudry et al., 2017;Ji and Telgarsky, 2018b), which proves directional convergence for certain linear prediction problems, but as a consequence of a stronger unique global maximum margin property; the work here therefore provides a re-proof and re-interpretation. Many implicit bias works explicitly assume (and do not prove) directional convergence and some version of alignment (Gunasekar et al., 2018;Chizat and Bach, 2020), and some works without these assumptions still left directional convergence open.

Experimental overview
The experiments in Figures 1 and 2 are performed in as standard a way as possible to highlight that directional convergence is a reliable property; full details are in Appendix A. Briefly, Figure 1 uses synthetic data and vanilla gradient descent (no momentum, no weight decay, etc.) on a 10,000 node wide 2-layer network and its Neural Tangent Kernel classifier. Figure 2 uses standard cifar firstly with a modified homogeneous AlexNet and secondly with an unmodified DenseNet, respectively inside and outside our assumptions. SGD was used on cifar due to training set size.

Preliminaries and assumptions
In this section we first introduce the notions of Clarke subdifferentials and o-minimal structures, and then use these notions to describe the network model, gradient flow, and Assumptions 2.1 and 2.3. Throughout this paper, · denotes the 2 (Frobenius) norm, and · σ denotes the spectral norm.
Locally Lipschitz functions and Clarke subdifferentials. Consider a function f : If f is locally Lipschitz, it holds that f is differentiable a.e. (Borwein and Lewis, 2000, Theorem 9.1.2). The Clarke subdifferential of f at x ∈ D is defined as which is nonempty convex compact (Clarke, 1975). Vectors in ∂f (x) are called subgradients, and let∂f (x) denote the unique minimum-norm subgradient: If f is continuously differentiable at x, then ∂f (x) = {∇f (x)} and∂f (x) = ∇f (x). We will use the Clarke subdifferential to define the gradient flow (without differentiability), and our analysis will use∂f in many places that seem to call on ∇f .
O-minimal structures and definable functions. Formally, an o-minimal structure is a collection S = {S n } ∞ n=1 , where S n is a set of subsets of R n which includes all algebraic sets and is closed under finite union/intersection and complement, Cartesian product, and projection, and S 1 consists of finite unions of open intervals and points. A set A ⊂ R n is definable if A ∈ S n , and a function f : D → R m with D ⊂ R n is definable if its graph is in S n+m . More details are given in Appendix B.
Many natural functions and operations are definable. First of all, definability of functions is stable under algebraic operations, composition, inverse, maximum and minimum, etc. Moreover, Wilkie (1996) proved that there exists an o-minimal structure where polynomials and the exponential function are definable. Consequently, definability allows many common layer types in deep learning, such as fullyconnected/convolutional/ReLU/max-pooling layers, skip connections, the cross entropy loss, etc.; moreover, they can be composed arbitrarily (cf. Lemma B.2).
, where x i ∈ R d are features and y i ∈ {−1, +1} are binary labels, and a predictor Φ(·; W ) : R d → R with parameters W ∈ R k . We make the following assumption on the predictor Φ. Assumption 2.1. For any fixed x, the prediction W → Φ(x; W ) as a function of W is locally Lipschitz, L-positively homogeneous for some L > 0, and definable in some o-minimal structure including the exponential function.
♦ As mentioned before, homogeneity means that Φ(x; cW ) = c L Φ(x; W ) for any c ≥ 0. This means, for instance, that linear, convolutional, ReLU, and max-pooling layers are permitted, but not skip connections and biases. Homogeneity is used heavily throughout the theoretical study of deep networks (Lyu and Li, 2019).
Given a decreasing loss function , the total loss (or unnormalized empirical risk ) is given by where p i (W ) := y i Φ(x i ; W ) are also locally Lipschitz, L-positively homogeneous and definable under Assumption 2.1. We consider the exponential loss exp (z) := e −z and the logistic loss log (z) := ln(1 + e −z ), in which case L is also locally Lipschitz and definable.
Gradient flow. As in (Davis et al., 2020;Lyu and Li, 2019), a curve z from an interval I to some real space R m is called an arc if it is absolutely continuous on any compact subinterval of I. It holds that an arc is a.e. differentiable, and the composition of an arc and a locally Lipschitz function is still an arc. We consider a gradient flow W : [0, ∞) → R k that is an arc and satisfies Our second assumption is on the initial risk, and appears in prior work (Lyu and Li, 2019). Assumption 2.3. The initial iterate W 0 satisfies L(W 0 ) < (0). ♦ As mentioned before, this assumption encapsulates our focus on the "late training" phase; some other analysis, for instance the neural tangent kernel, can be first applied to ensure L(W 0 ) < (0).
The following chain rule is important in our analysis. It is basically from (Davis et al., 2020, Theorem 5.8 and Lemma 5.2), though we detail how their proof handles our slight extension in Appendix B.2.
Lemma 2.4. Given a locally Lipschitz definable f : D → R with an open domain D, for any interval I and any arc z : I → D, it holds for a.e. t ∈ I that Moreover, for the gradient flow in eq. (2.2), it holds for a.e.

Directional convergence
We now turn to stating our main result on directional convergence and sketching its analysis. As Assumptions 2.1 and 2.3 imply W t → ∞ (Lyu and Li, 2019), we study the normalized flow W t := W t / W t , whose convergence is a formal way of studying the directional convergence of W t . As mentioned before, directional convergence is false in general (Lyu and Li, 2019), but definability suffices to rule it out. Throughout, for general nonzero W , we will use W := W/ W . A direct consequence of Theorem 3.1 is the convergence of the margin distribution (i.e., normalized outputs). Due to homogeneity, for any nonzero W , we have p i (W )/ W L = p i ( W ), and thus the next result follows from Theorem 3.1.
Corollary 3.2. Under Assumptions 2.1 and 2.3, for exp and log , it holds that p i (W t )/ W t L converges for all 1 ≤ i ≤ n.
Next we give a proof sketch of Theorem 3.1; the full proofs of the Kurdyka-Lojasiewicz inequalities (Lemmas 3.9 and 3.10) are given in Appendix B.3, while the other proofs are given in Appendix C.

Technical results
The smoothed margin introduced in (Lyu and Li, 2019) is crucial in our analysis: given W = 0, let Next we characterize the Clarke subdifferentials of α andα. Lemma 3.4. For any nonzero W ∈ R k , we havē The two quantities α and β are strongly related.
Lemma 3.5. For ∈ { exp , log } and any W satisfying L(W ) < (0), it holds that and let ζ t denote the length of the path swept by W t = W t / W t from time 0 to t. Lyu and Li (2019) proved thatα t is nondecreasing with some limit a ∈ (0, ∞), and W t → ∞. We invoke a standard but sophisticated tool from the definability literature to aid in proving ζ t is finite: formally, a function Ψ : [0, ν) → R is called a desingularizing function when Ψ is continuous on [0, ν) with Ψ(0) = 0, and continuously differentiable on (0, ν) with Ψ > 0. Now we can state the next result, which is crucial in establishing Theorem 3.1.
Lemma 3.6. There exists R > 0, ν > 0 and a definable desingularizing function Ψ on [0, ν), such that for a.e. large enough t with W t > R andα t > a − ν, it holds that for some constant c > 0.
To prove Theorem 3.1 from here, let t 0 be large enough so that the conditions of Lemma 3.6 hold for all t ≥ t 0 : then we have lim t→∞ ζ t ≤ ζ t0 + cΨ (a −α t0 ) < ∞, and the path length is finite.
Below we sketch the proof of Lemma 3.6, which is based on a careful comparison of dα t / dt and dζ t / dt. Given any function f which is locally Lipschitz around a nonzero W , let denote the radial and spherical parts of∂f (W ) respectively. We have the following result.
Lemma 3.9. Given a locally Lipschitz definable function f with an open domain D ⊂ x x > 1 , for any c, η > 0, there exists ν > 0 and a definable desingularizing function Ψ on [0, ν) such that On the other hand, if ∂ ⊥α (W t ) / ∂ rα (W t ) ≤ c 1 W t L/3 , then using Lemmas 3.3 to 3.5 we can show that It then follows from eq. (3.8) that dα t / dζ t = Ω W t 4L/3 ∂α (W t ) . In this case we give the following Kurdyka-Lojasiewicz inequality, which implies Lemma 3.6.
Lemma 3.10. Given a locally Lipschitz definable function f with an open domain D ⊂ x x > 1 , for any λ > 0, there exists ν > 0 and a definable desingularizing function Ψ on [0, ν) such that 4 Alignment between the gradient flow path and gradients Below we first sketch the proof of Theorem 4.1, with full details in Appendix D, and then in Section 4.2 present a few global margin maximization consequences, which are proved in Appendix E.

A proof sketch of Theorem 4.1
First recall that lim t→∞ α(W t )/ W t L = a, and then Lemmas 3.3 and 3.5 imply In other words, the inner product between ∇α(W t )/ W t L−1 and W t converges. Now consider θ t , which is also the angle between W t and ∇α(W t ) due to Lemma 3.3. By (Lyu and Li, 2019, Corollary C.10), given any > 0, there exists a time t such that θ t < . The question is whether such a small angle can be maintained after t . This is not obvious since as W t → ∞, the smoothed margin α(W t ) asymptotes to the exact margin min 1≤i≤n p i (W t ), which may be nondifferentiable, even with smooth p i , due to nondifferentiability of the minimum. Consequently, the exact margin may have discontinuous Clarke subdifferentials, and since the smoothed margin asymptotes to it, it is unclear whether θ t → 0.
To handle this, the key to our analysis is the potential function J (W ) := ∇α(W t ) 2 / W t 2L−2 . Suppose at time t, it holds that ∇α(W t )/ W t L−1 , W t is close to aL, and θ t is very small. If θ t becomes large again at some t > t, it must follows that J (W t ) is much larger than J (W t ). We prove that this is impossible, by showing that and thus Theorem 4.1 follows. The proof of eq. (4.3) is motivated by the dual convergence analysis in (Ji and Telgarsky, 2019), and also uses the positive homogeneity of ∇p i and ∇ 2 p i (which exist a.e.).

Main alignment consequence: margin maximization
A variety of (global) margin maximization results are immediate consequences of directional convergence and alignment. Here are two examples: deep linear networks, and squared ReLU networks. Deep linear networks predict with Φ(x i ; W ) = A L · · · A 1 x i , where the parameters W = (A L , . . . , A 1 ) are organized into L matrices. This setting has been considered in the literature, but the original work assumed directional convergence, alignment and a condition on the support vectors (Gunasekar et al., 2018); a follow-up dropped the directional convergence and alignment assumptions, but instead assumed the support vectors span the space R d (Ji and Telgarsky, 2018a).
Thanks to directional convergence and alignment, the proof boils down to writing down the gradient expression for each layer and doing some algebra.
A more interesting example is a certain 2-homogeneous case, which despite its simplicity is a universal approximator; this setting was studied by Chizat and Bach (2020), who considered the infinite width case, and established margin maximization under assumptions of directional convergence and gradient convergence. It is not clear if the results here directly fill those assumptions, since infinite width networks are not obviously definable. Instead, here we consider the finite width case.
Following (Chizat and Bach, 2020 whereby p i (W ) = j ϕ ij (w j ), and Φ, p i , and ϕ ij are all 2-homogeneous and definable. (The "(−1) j " may seem odd, but is an easy trick to get universal approximation without outer weights.) Proposition 4.6. Consider the setting in eq. (4.5) along with L(W 0 ) < (0) and x i ≤ 1.
1. (Local guarantee.) s ∈ R m with s j (t) := wj (t) 2 / Wt 2 satisfies s →p ∈ ∆ m (probability simplex on m vertices), and θ j →θ j withθ j = 0 if s j = 0, and a = lim 2. (Global guarantee.) Suppose the covering condition: there exist t 0 and > 0 with Then margins are approximately (globally) maximized: where P(S d−1 ) is the set of signed measures on S d−1 with mass at most 1.
The first part characterizes the limiting margin as the maximum margin of a linear problem obtained by taking the limiting directions (θ j ) m j=1 and treating the resulting ϕ ij (θ j ) as features. The quality of this margin is bad if the limiting directions are bad, and therefore we secondly consider a case where our margin is nearly as good as the infinite width global max margin value as defined by (Chizat and Bach, 2020, eq. (5)); see discussion therein for a justification of this choice.
The covering condition deserves further discussion. In the infinite width setting, it holds for all > 0 assuming directional convergence (Chizat and Bach, 2020, Proof of Theorem D.1), but cannot hold in such generality here as we are dealing with finite width. Similar properties have appeared throughout the literature: Wei et al. (2018, Section 3) explicitly re-initialized network nodes to guarantee a good covering, and more generally (Ge et al., 2015) added noise to escape saddle points in general optimization problems.

Concluding remarks and open problems
In this paper, we established that the normalized parameter vectors Wt / Wt converge, and that under an additional assumption of locally Lipschitz gradients, the gradients also converge and align with the parameters.
There are many promising avenues for future work based on these results. One basic line is to weaken our assumptions: dropping homogeneity to allow for DenseNet and ResNet, and analyzing finite-time methods like (stochastic) gradient descent (and moreover their rates of convergence). We also handled only the binary classification case, however our tools should directly allow for cross-entropy.
Another direction is into further global margin maximization results, beyond the simple networks in Section 4.2, and into related generalization consequences of directional convergence and alignment.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pages 9461-9471, 2018.

A Experimental setup
The goal of the experiments is to illustrate that directional convergence is a clear, reliable phenomenon. Below we detail the setup for the two types of experiments: contour plots in Figure 1, and margin plots in Figure 2 (with ResNet here in Figure 3).
Data. Figure 1 used two-dimensional synthetic data in order to capture the entire prediction surface; data was generated by labeling points in the plane with a random network (which included a bias term), and then deleting low-margin points. Then, when training from scratch to produce the contours, data was embedded in R 3 by appending a 1; this added bias made the maximum margin network much simpler. Figure 2 used the standard cifar dataset in its 10 class configuration (Krizhevsky, 2009). There are 50,000 data points, each with 3072 dimensions, organized into 32 × 32 images with 3 color channels.

Models.
A few simple models both inside and outside our technical assumptions were used. All code was implemented in PyTorch (Paszke et al., 2019). Figure 1 worked with a style of 2-layer network which appears widely throughout theoretical investigations: specifically, there is first a wide linear layer (in our case, 10, 000 nodes), then a ReLU layer, and then a layer of random signs which is not trained. This simple architecture is still a universal approximator with non-convex training. Figures 1b and 1c trained this network, which can be written as x → j s j max 0, w j , x , where s j ∈ ±1 are fixed random signs and (w j ) m j=1 are the trainable parameters. Figure 1a trained the corresponding NTK (Jacot et al., 2018;Du et al., 2018;Allen-Zhu et al., 2018;Zou et al., 2018), meaning the linear predictor obtained by freezing the network activations, which thus has the form x → j v j , x s j 1 w j , x ≥ 0 , where (w j ) m j=1 from before are now fixed, and only (v j ) m j=1 are trained. , but with biases disabled in order to give a homogeneous network. The network ultimately consists of ReLU layers, max pooling layers, linear layers, and convolutional layers, and is 5-homogeneous. In particular, H-AlexNet satisfies all conditions we need for directional convergence.
The two models outside the assumptions were DenseNet (cf. Figure 2b and ResNet (cf. Figure 3), used unmodified from the PyTorch source, namely by invoking torchvision.models.densetnet121 and torchvision.models.resnet18 with argument num classes=10. Training. Training was a basic gradient descent (GD) for Figure 1, and a basic stochastic gradient descent (SGD) for Figures 2 and 3 with a mini-batch size of 512; there was no weight decay or other regularization, no momentum, etc.; it is of course an interesting question how more sophisticated optimization schemes, including AdaGrad and AdaDelta and others, affect directional convergence and alignment. Experiments were run to accuracy 10 −8 or greater in order to train significantly past the point L(W 0 ) < (0) from Assumption 2.3, and to better depict directional convergence.
To help reach such small risk, the main ideas were to rewrite the objective functions to be numerically stable, and secondly to scale the step size by 1 /L(Wt−1), which incidentally is consistent with gradient flow on α with exponential loss, and is moreover an idea found across the margin literature, most notably as the step size used in AdaBoost (Freund and Schapire, 1997). This can lead to some numerical instability, so the step size was reduced if the norm of the induced update was too large, meaning the norm of the gradient times the step size was too large. A much more elaborate numerical scheme was reported by Lyu and Li (2019, Appendix L), but not used here.
One point worth highlighting is the role of SGD, which seems as though it should have introduced a great deal of noise into the plots, and after all is outside the assumptions of the paper (which requires gradient flow, let alone gradient descent). Though not depicted here, experiments in Figure 2 were also tried on subsampled data and full gradients, and Figure 1 was tried with SGD in place of GD; while gradient descent does result in smoother plots, the difference is small overall, leaving the rigorous analysis of directional convergence with SGD as a promising future direction.
Margin plots. A few further words are in order for the margin plots in Figures 2 and 3.
While margins are well-motivated from generalization and other theoretical perspectives (Bartlett et al., 2017;Jiang et al., 2019Jiang et al., , 2020, we also use margin plots as a visual surrogate for prediction surface contour plots from Figure 1, but now for high-dimensional data, even with high-dimensional outputs. In particular, Figures 2 and 3 track the prediction surface but restricted to the training set, showing, in a sense, the output trajectory for each data example. Since the output dimension is 10 classes, we convert this to a single real number via the usual multi-class margin ( In the case of homogeneous networks, it is natural to normalize this quantity by W t L ; for the inhomogeneous cases DenseNet and ResNet, no such normalization is available. Therefore, for consistency, at each time t, margins were normalized by the median nonnegative margin across all data. To show the evolution of the margins most clearly, we sorted margins according to the final margin level, and used this fixed data ordering for all time; as a result, lines in the plot indeed correspond to trajectories of single examples. Moreover, we indexed time by the log of the inverse risk, namely ln n /L(Wt) in our notation. While this may seem odd at first, importantly it washes out the effect of small step-sizes and other implementation choices; and crucially disallows an artificial depiction of directional convergence by choosing rapidly-vanishing step sizes.

B Results on o-minimal structures
An o-minimal structure is a collection S = {S n } ∞ n=1 , where each S n is a set of subsets of R n satisfying the following conditions: 1. S 1 is the collection of all finite unions of open intervals and points.
2. S n includes the zero sets of all polynomials on R n : if p is a polynomial on R n , then x ∈ R n p(x) = 0 ∈ S n .
3. S n is closed under finite union, finite intersection, and complement.
4. S is closed under Cartesian products: if A ∈ S m and B ∈ S n , then A × B ∈ S m+n . 5. S is closed under projection Π n onto the first n coordinates: if A ∈ S n+1 , then Π n (A) ∈ S n .
Given an o-minimal structure S, a set A ⊂ R n is definable if A ∈ S n , and a function f : D → R m with D ⊂ R n is definable if the graph of f is in S n+m . Due to the stability under projection, the domain of a definable function is definable. In the following we consider an arbitrary fixed o-minimal structure.

B.1 Basic properties
A convenient way to construct definable sets and functions is to use first-order formulas: • If A is a definable set, then "x ∈ A" is a first-order formula.
• If φ(x, y) is a first-order formula where x ∈ R n and y ∈ R m , and A ⊂ R n is definable, then ∀x ∈ Aφ(x, y) and ∃x ∈ Aφ(x, y) are first-order formulas.
Given a first-order formula, the set of free variables which satisfy the formula is definable (Van den Dries and Miller, 1996, Appendix A). The following basic properties of definable sets and functions can then be shown (see (Van den Dries and Miller, 1996;Coste, 2000;Lê Loi, 2010)).
1. Given any α, β ∈ R and any definable functions f, g : D → R, we have αf + βg and f g are definable. If g = 0 on D, then f /g is definable. If f ≥ 0 on D, then f 1/ is definable for any positive integer .
2. Given a function f : D → R m , let f i denote the i-th coordinate of its output. Then f is definable if and only if all f i are definable.
3. Any composition of definable functions is definable.
4. Any coordinate permutation of a definable set is definable. Consequently, if the inverse of a definable function exists, it is also definable.
6. Any combination of finitely many definable functions with disjoint domains is definable. For example, the pointwise maximum and minimum of definable functions are definable.
The proofs are standard and omitted. To illustrate the idea, we give a proof of the following standard result on the infimum and supremum operation.
Lemma B.1. Let A ⊂ R n+1 be definable and Π n denote the projection onto the first n coordinates. Suppose inf y (x, y) ∈ A > −∞ for all x ∈ Π n (A), then the function from Π n (A) to R given by is definable. Consequently, we have: 1. Let f : D → R be definable and bounded below, and g : D → R m be definable. Then h : g(D) → R given by h(y) := inf x∈g −1 (y) f (x) is definable.
2. Let f : D f → R and g : D g → R be definable and bounded below, then their infimal convolution h : 3. A function f : D → R is definable if and only if its epigraph is definable.
4. Given a definable set A, the function d A (x) := inf y∈A x − y is definable, which implies the closure, interior and boundary of A are definable.
5. The lower-semicontinuous envelope of a definable function is definable.
Proof. Note that the set A := (x, y) x ∈ Π n (A), and ∀(x, y ) ∈ A, y ≤ y is definable, since it is given by the following first-order formula: Similarly, the set A u := (x, y) x ∈ Π n (A), and ∀(x, y ) ∈ A , y ≥ y is definable, and thus so is A ∪ A u , which is the graph of the desired function. Now we prove the remaining claims.
1. Let G f denote the graph of f , and G g denote the graph of g. We can just apply the main claim to the following definable set: 2. First, the Minkowski sum of two definable sets A and B is definable: Then we can just apply the main claim to the Minkowski sum of the graphs of f and g.
3. Let G f denote the graph of f . If G f is definable, then the epigraph is definable: If the epigraph is definable, then G f is definable due to the main claim.
4. We can just apply the main claim to the set (x, r) : ∃y ∈ A x − y = r .
The closure of A is just d −1 A (0). The interior of A is the complement of d −1 A c (0). The boundary is the difference between the closure and interior. 5. The epigraph of the lower-semicontinuous envelope of f is the closure of the epigraph of f .
As another example, note that the types of networks under discussion are definable.
Lemma B.2. Suppose there exist k, d 0 , d 1 , . . . , d L > 0 and L definable functions (g 1 , . . . , g L ) where g j : then all h j are definable. It suffices if each output coordinate of g j is the minimum or maximum over some finite set of polynomials, which allows for linear, convolutional, ReLU, max-pooling layers and skip connections.
Proof. The definability of h j can be proved by induction using the fact that definability is preserved under composition. Next, note that the minimum and maximum of a finite set of polynomials is definable. Lastly, note that each output coordinate of linear and convolutional layers can be written as a polynomial of their input and the parameters; each output coordinate of a ReLU layer is the maximum of two polynomials; each output of a max-pooling layer is a maximum of polynomials. Skip connections are allowed by the definition of h j .
Below are some useful properties of definable functions.

Proposition B.3 ((Lê Loi, 2010, Exercise 2.7)). Given a definable function
Proof. We consider lim x→a + f (x) where a ∈ R; the other cases can be handled similarly. If lim x→a + f (x) does not exist, then there exists k ∈ R such that lim sup x→a + f (x) > k > lim inf x→a + f (x). In other words, for any > 0, there exists x 1 , x 2 ∈ (a, a + ) such that f (x 1 ) > k and f (x 2 ) < k. However, since g := f − k is definable on (a, b), it holds that g −1 (−∞, 0) , and g −1 (0), and g −1 (0, ∞) are all definable, and thus they are all finite unions of open intervals and points. It then follows that there exists 0 > 0 such that g = f − k has a constant sign (i.e., > 0, = 0 or < 0) on (a, a + 0 ), which is a contradiction.
Lemma B.5. Given a C 1 definable curve γ : [0, ∞) → R n such that lim s→∞ γ(s) exists and is finite, it holds that the path swept by γ has finite length.
Proof. Let z := lim s→∞ γ(s). Since z − γ(s) is definable, either it is 0 for all large enough s, or it is positive for all large enough s. In the first case, since γ is C 1 , it has finite length. In the second case, Theorem B.4 implies that there exists an interval [a, ∞) on which z − γ(s) > 0 and d z − γ(s) / ds < 0, and thus γ (s) > 0. Let The existence of the above limits is guaranteed by Proposition B.3. Note that u, v is equal to Since γ (s)/ γ (s) → v, given any > 0, for large enough s it holds that γ (s)/ γ (s) , v ≥ 1 − , and thus which implies that u = v. Since > 0 was arbitrary, then which implies that γ has finite length.
The following Curve Selection Lemma is crucial in proving the Kurdyka-Lojasiewicz inequalities.
Lemma B.7 (Curve Selection at Infinity). Given a definable set A ∈ R n , a definable function f : A → R, and a sequence x i in A such that lim i→∞ x i = ∞ and lim i→∞ f (x i ) = y, there exists a positive constant a and a C 1 definable curve ρ : [a, ∞) → A such that ρ(s) = s, and lim s→∞ f ρ(s) = y.

B.2 Clarke subdifferentials
Here is a standard result on the definability of (Fréchet) derivatives: given a definable function f : D → R with an open domain D, the set is definable, since it is given by the following first-order formula: Similarly to the gradients, the following result holds for the Clarke subdifferentials.
is also definable. Now by Carathéodory's Theorem, Γ is given by It then follows from Lemma B.1 that x → ∂ f (x) and x →∂f (x) are definable.
Next we discuss Lemma 2.4. Its first part is proved in (Davis et al., 2020, Theorem 5.8) when D = R n and I = [0, ∞), but actually holds in general as verified below. Note that for any t ∈ I excluding the endpoints, since f is locally Lipschitz, there exists a neighborhood U of z(t) on which f is K-Lipschitz continuous. Let g denote the infimal convolution of f | U and K · . It follows that g is definable (Lemma B.1) and K-Lipschitz continuous on R n , and f = g on U (Borwein and Lewis, 2000, Exercise 7.1.2). Take an interval [a, b] t with rational endpoints such that z [a, b] ⊂ U , and define the absolutely continuous curvez : [0, ∞) → D as z(t) = z(a + t) for t ∈ [0, b − a], andz(t) = z(b) for t > b − a. Applying (Davis et al., 2020, Theorem 5.8) to g andz gives that the chain rule holds for f and z a.e. on [a, b]. Since this holds for any t ∈ I, and there are only countably many intervals with rational endpoints, it follows that the chain rule holds a.e. for f and z on I. The second claim of Lemma 2.4 can be proved in the same way as (Davis et al., 2020, Lemma 5.2).

B.3 Kurdyka-Lojasiewicz inequalities
Asymptotic Clarke critical values. To prove the Kurdyka-Lojasiewicz inequalities, we need the notion of asymptotic Clarke critical values, introduced in (Bolte et al., 2007). Given a locally Lipschitz function f : D → R with an open domain D, we say that a ∈ R ∪ {+∞, −∞} is an asymptotic Clarke critical value of f if there exists a sequence ( We have the following result regarding the asymptotic Clarke critical values of a definable function, which is basically from (Bolte et al., 2007, Corollary 9). To state the proof in a bit more detail, (Bolte et al., 2007, Corollary 9) shows that if f is lower semicontinuous and f > −∞, then f has finitely many asymptotic Clarke critical values. To get Lemma B.9, we just need to apply (Bolte et al., 2007, Corollary 9) to the lower semi-continuous envelopes of f | f −1 ((0,∞)) and −f | f −1 ((−∞,0)) .
Proof. Since f is definable, f (D) is also definable, and thus is a finite union of open intervals and points. It follows that either there exists > 0 such that (0, ) ∩ f (D) = ∅, in which case the claim trivially holds; otherwise we are free to choose > 0 such that (0, ) ⊂ f (D). In the second case, define φ : (0, ) → R as By Lemmas B.1 and B.8, φ is definable. Lemma B.9 implies that there are only finitely many asymptotic Clarke critical values on (0, ), and thus there exists ∈ (0, ) such that on (0, ) there is no asymptotic Clarke critical value and φ(z) > 0. Now consider the definable set Since the left hand side of eq. (B.11) is definable, it can actually be nonzero only for finitely many s, and thus is equal to 0 on some interval (0, µ) where µ ≤ ω.

Now for any
The unbounded setting. The unbounded setting is more complicated: to show directional convergence, we need two Kurdyka-Lojasiewicz inequalities (cf. Lemmas 3.9 and 3.10), depending on the relationship between the spherical and radial parts of∂f . Given a locally Lipschitz definable function f : D → R with an open domain D ⊂ x x > 1 , recall that∂ r f (x) and∂ ⊥ f (x) denote the radial part and spherical part of∂f (x) respectively, which are both definable. Given , c, η > 0, let In any o-minimal structure, U ,c,η is definable if η is rational. Now we prove Lemma 3.9, a Kurdyka-Lojasiewicz inequality on some U ν,c,η , using ideas from (Kurdyka et al., 2006, Proposition 6.3).
Proof of Lemma 3.9. Similarly to the proof of Lemma B.10, we only need to consider the case where there exists > 0 such that (0, ) ⊂ f (D). Without loss of generality, we can assume η is rational, since otherwise we can consider any rational η ∈ (0, η). Therefore U ,c,η is definable, and so is f (U ,c,η ). If there exists > 0 such that f (U ,c,η ) ∩ (0, ) = ∅, then Lemma 3.9 trivially holds; therefore we assume that there exists > 0 such that f (U ,c,η ) = (0, ). By Lemma B.9, we can also make small enough so that there is no asymptotic Clarke critical value on (0, ). Define φ : (0, ) → R as Since there is no asymptotic Clarke critical value on (0, ), it holds that φ(z) > 0.
Consider the definable set  Sinceρ(s) is a C 1 definable curve on the unit sphere, Proposition B.3 and Lemma B.5 imply that
Proof of Lemma 3.10. We first assume that λ is rational, and later finish by handling the real case with a quick reduction. Consider the definable mapping ξ λ : R n \ {0} → R n \ {0} given by Note that ξ −1 λ = ξ 1/λ . If y = ξ λ (x), then x = ξ 1/λ (y), which has the Jacobian Note that g is locally Lipschitz and definable with an open bounded domain. Therefore Lemma B.10 implies that there exists ν > 0 and a definable desingularizing function Ψ on [0, ν) such that Ψ g(y) ∂ g(y) ≥ 1 for any y ∈ g −1 (0, ν) . Let x = ξ −1 λ (y), it holds that g is differentiable at y if and only if f is differentiable at x, and by the definition of Clarke subdifferential, Therefore eq. (B.12) implies that and thus max 1, which finishes the proof for rational λ. To handle real λ > 0, we can apply the above result to any rational λ ∈ (λ/2, λ).

C Omitted proofs from Section 3
We first give some results on Clarke subdifferentials. The following is a generalization of Euler's homogeneous function theorem, which can also be found in (Lyu and Li, 2019, Theorem B.2), but with an additional requirement of a chain rule.
Lemma C.1. Suppose f : R n → R is locally Lipschitz and L-positively homogeneous for some L > 0, then for any x ∈ R n and any x * ∈ ∂f (x), x, x * = Lf (x).
Proof. Let D denote the set of x where f is differentiable. For any nonzero x ∈ D , it holds that Since f is L-positively homogeneous, f (x + δx) = (1 + δ) L f (x), and thus which implies x, ∇f (x) = Lf (x). This property trivially holds if 0 ∈ D . Now consider an arbitrary x ∈ R n . For any sequence x i in D such that lim i→∞ x i = x and lim i→∞ ∇f (x i ) = x * , it holds that Since ∂f (x) consists of convex combinations of such x * , Lemma C.1 holds.

Next we prove Lemmas 3.3 and 3.4
Proof of Lemma 3.3. Note that L is differentiable at W if and only if α is differentiable at W , and when both gradients exist, the chain rule and inverse function theorem together imply that whereby the first claim follows from the definition of Clarke subdifferential. To prove the second claim, the chain rule for Clarke subdifferentials (Clarke, 1983, Theorem 2.3.9) implies that and thus Lemma C.1 ensures for any W * ∈ ∂α(W ), which finishes the proof.
Proof of Lemma 3.4. Note that given W = 0, α is differentiable at W if and only ifα is differentiable at W , and when both gradients exist, By the definition of Clarke subdifferential, for any nonzero W , The first claim of Lemma 3.4 holds since for any W ∈ ∂α(W ), by Lemma 3.3, To prove the second claim, note that since ∂α(W ) and ∂α(W ) have fixed radial parts, the norms of the whole subgradients are minimized if and only if the norms of their spherical parts are minimized. Due to eq. (C.2), the norms of the spherical parts of ∂α(W ) and ∂α(W ) are minimized simultaneously, and the second claim follows.
Next we characterize the relationship between α and β. We need the following technical result on exp and log . Define σ : R + → R by and π : R n → R by Note that α(W ) = π p(W ) where p(W ) = p 1 (W ), . . . , p n (W ) .
Proof. For exp (z) = e −z , we have σ(z) = z ln(z), while for log (z) = ln(1 + e −z ), we have σ(z) = (1 − e −z ) ln(e z − 1). In both cases lim z→0 σ(z) = 0, and σ is convex on 0, (0) , which implies super-additivity. Turning to concavity of π, in the case of exp , it is a standard fact in convex analysis that the function π(v) = − ln n i=1 exp(−v i ) is concave (Borwein and Lewis, 2000, Exercise 3.3.7). For log , note that We want to show that ∇ 2 π(v) 0, or equivalently By definition, we need to show that for any z ∈ R n , Note that for a, b > 0, we have e a+b − 1 > (e a − 1) + (e b − 1), which implies Also note that e −vi (v i ) = (v i ) 2 , and thus Using Lemma C.5, we can prove Lemma 3.5.
Next we prove Lemma 3.7.
Proof of Lemma 3.7. Lemma 2.4 implies that for a.e. t ≥ 0, First note that Assumption 2.3 implies that W 0 > 0, and moreover Lyu and Li (2019, Lemma 5.1) proved that d W t / dt > 0 for a.e. t ≥ 0, and thus W t is increasing and W t ≥ W 0 > 0. Now we have for a.e. t ≥ 0, By Lemmas 3.3 to 3.5, both ∂ rα (W t ), W t and −∂ r L(W t ), W t are nonnegative, and thus Lemmas 3.3 and 3.4 also imply that∂ ⊥α (W t ) and −∂ ⊥ L(W t ) point to the same direction, and thus Now consider W t and ζ t . Since W t is an arc, and W t ≥ W 0 > 0, it follows that W t is also an arc. Moreover, for a.e. t ≥ 0, Since W t is an arc, d W t / dt and d W t / dt are both integrable, and by definition of the curve length, and for a.e. t ≥ 0 we have Finally we prove Lemma 3.6, which directly implies Theorem 3.1.

D Omitted proofs from Section 4
We first give the following technical result.
Lemma D.1. Suppose f : R n → R is L-positively homogeneous for some L > 0 and has a locally Lipschitz gradient at all nonzero x ∈ R n . Then ∇f is (L − 1)-positively homogeneous: given any nonzero x and c > 0, it holds that If ∇f is differentiable at a nonzero x, then for any c > 0, it holds that On the other hand, by homogeneity, which proves the claim. The homogeneity of ∇ 2 f when it exists can be proved in the same way.
To get K σ , note that for any x = 1, there exists an open neighborhood U x of x on which ∇f is K x -Lipschitz continuous, and thus the spectral norm of ∇ 2 f is bounded by K x when it exists. All the U x form an open cover of the compact unit sphere, and thus has a finite subcover, which implies the claim.
Below we estimate various quantities using Lemma D.1. Proof. Since p i (W ) is continuous, it is bounded on the unit sphere. Because it is L-positively homogeneous, p i (W )/ W L is bounded on R k . Lemma 3.5 implies that β(W ) − 2 ln(n) − 1 ≤ α(W ) ≤ min 1≤i≤n p i (W ), and it follows that β(W )/ W L is bounded.
Recall the definition of J : If all ∇p i are locally Lipschitz, then J is also locally Lipschitz. We further have the following result.
Lemma D.3. Under the same conditions as Lemma D.2, for any W satisfying L(W ) < (0) and any W * ∈ ∂J (W ), for some constant K > 0, where θ denotes the angle between W and −∇L(W ).
Proof. Let D denote the set of W where all ∇p i are differentiable, and let S 0 denote the set of W where L(W ) < (0). We only need to prove the lemma on D ∩ S 0 , since for any W ∈ S 0 it follows from (Clarke, 1983, Theorem 2.5.1) that Below we fix an arbitrary W ∈ D ∩ S 0 . All the partial derivatives below with respect to p i are evaluated at p(W ) := (p 1 (W ), . . . , p n (W )). Recall that where π is defined in eq. (C.4). Since ∇p i are also differentiable at W , we have Now for any W ∈ D ∩ S 0 , we have (recall that W = W/ W ) and thus Comparing eqs. (D.4) and (D.5), first note that since π is concave by Lemma C.5, and moreover Therefore eq. (D.5) is upper bounded by Let ∇ r α(W ) and ∇ ⊥ α(W ) denote the radial and spherical part of ∇α(W ), respectively. Let θ denote the angle between W and ∇α(W ). Lemmas 3.3 and 3.5 imply that W, ∇α(W ) = Lβ(W ) > 0, and thus θ is between 0 and π/2. Now Lemma D.1 and the proof of Lemma C.1 imply that and thus by Lemma 3.3, In addition, the proof of Lemma 3.5 shows that π(p) 1 ≤ 2, and Lemma D.1 ensures that ∇ 2 f σ has a uniform bound K σ on the unit sphere, therefore Combining eqs. (D.5) to (D.9) gives Invoking Lemma D.2 then gives for some constant K > 0.
The following result helps us control θ t .
Lemma D.10. Under the same condition as Lemma D.2 and Assumption 2.3, it holds that Proof. Recall thatα t = α(W t )/ W t L is nondecreasing with a limit a, and thus dα t / dt is integrable. Now Lemmas 3.3, 3.4 and 3.7 imply that and moreover Since β(W t )/ W t L is bounded due to Lemma D.2, the proof is finished.
Now we can prove Theorem 4.1.
Moreover, using eq. (D.12), for any t > t 2 , and thus Since is arbitrary, we have lim t→∞ θ t = 0. If all p i are C 2 , then the above proof holds without definability: it is only used in eq. (D.12) to ensure the chain rule, which always holds for C 2 functions. E Global margin maximization proofs for Section 4.2 This section often works with subscripted subsets of parameters, for instance per-layer matrices (A 1 (t), . . . , A L (t)), or per-node weights (w 1 (t), . . . , w m (t)); to declutter slightly, we will drop "(t)" throughout when it is otherwise clear.
First, a technical lemma regarding directional convergence and alignment properties inherited by these subsets of W t . This will be used in both the deep linear case and in the 2-homogeneous case.
Lemma E.1. Suppose the conditions for Theorems 3.1 and 4.1 hold. Let (U 1 (t), . . . , U r (t)) be any partition of W t , and set s j (t) := U j (t) L / W t L . Then s(t) converges to somes, and for each j, and moreovers j > 0 implies Proof. First note that s(t) converges since W t / W t converges, and alignment grants By directional convergence (cf. Theorem 3.1), alignment (cf. Theorem 4.1), and Cauchy-Schwarz, which starts and ends with −1 and is thus a chain of equalities. Applying eq. (E.2) and he equality case of Cauchy-Schwarz to each j withs j > 0, and thus The preceding statements used L(W ); to obtain the analogous statements with α(W ), note since < 0 that For the final claim, note Theorem 4.1 and eq. (4.2) imply that and whens j > 0, Applying the preceding lemma to network layers, we handle the deep linear case as follows.
Proof of Proposition 4.4. For convenience, write A j instead of A j (t) when time t is clear, and also u := A j · · · A 1 and ∇ u L(W ) = i (y i u T x i )y i x i . By this notation, where (A L · · · A j+1 ) T is a column vector, and (A j−1 · · · A 1 ∇ u L(W )) T is a row vector, and moreover A j , ∇ Aj L(W ) = u, ∇ u L(W ) , where this last inner product does not depend on j.
Applying the subset-alignment of Lemma E.1 to layers (A j , . . . , A 1 ) gives, for each j, wherebys j is independent of j, which can only means 2/L j = 1/L > 0 for all j, but more importantly A j (t) → ∞ for all j. By Lemma E.1, this means all layers align with their gradients.
Next it is proved by induction from A L to A 1 that there exist unit vectors v 0 , . . . , v L with v L = 1 and A j / A j = v j v T j−1 . The base case A L holds immediately, since A L is a row vector, meaning we can choose v L := 1 and v L−1 := A T L / A L since A L converges in direction. For the inductive step A j with j < L, note Since v j is a fixed unit vector and since ∇ Aj L(W ) converges in direction, the row vector part of the above expression must also converge to some fixed unit vector v T j−1 , namely where v j−1 := − lim t→∞ A j−1 · · · A 1 ∇ u L(W ) A j−1 · · · A 1 ∇ u L(W ) .
Since A j and −∇ Aj L(W ) asymptotically align as above, then Aj / Aj → v j v T j−1 . Now consider v 0 and u, where it still needs to be shown that v 0 = u/ u . To this end, note whereby u/ u = v 0 . By a similar calculation, which means u/ u asymptotically satisfies the optimality conditions for the optimization problem min w ≤1 1 A L · · · A 1 i A L · · · A 1 y i x T i w , which is asymptotically solved by the unique maximum margin vectorū, which is guaranteed to exist since the data is linearly separable thanks to L(W 0 ) < (0).
Before moving on to the 2-homogeneous case, we first produce another technical lemma, which we will use to control dual variables q i (t) := ∂α/∂p i (W t ), which also appear in Proposition 4.6.
Lemma E.3. Every accumulation pointq of q(t) t ∈ N satisfiesq ∈ ∆ n and iq i W W , Proof. By Lemmas 3.3 and 3.5, Moreover, since lim z→∞ log (z) exp(z) = 1 and since a > 0 and W t → ∞, then q(t) is asymptotically within the simplex, meaning lim t→∞ min q ∈∆n q(t)−q = 0. Consequently, every accumulation pointq of {q(t) : t ∈ N} satisfiesq ∈ ∆ n , and iq i lim With this in hand, we can handle the 2-homogeneous case.
Consequently, this means that eithers j > 0 and lim t→∞ i q i (t)ϕ ij (θ j (t)) = a, or elses j = 0 and by the choiceθ j = 0 then lim t→∞ i q i (t)ϕ ij (θ j (t)) = 0. In particular, this meanss j > 0 iffθ j attains the maximal value a, meanings satisfies the Sion primal optimality conditions for the saddle point problem over the fixed points (θ 1 , . . . ,θ m ) (Chizat and Bach, 2020, Proposition D.3). Now consider the dual variables q i (t) = ∂α/∂p i (W t ). By Lemma E.3, any accumulation pointq is an element of ∆ n and moreover is supported on those examples i minimizing p i (W ), which meansq satisfies the Sion dual optimality conditions for the margin saddle point problem again over fixed points (θ 1 , . . . ,θ m ) (Chizat and Bach, 2020, Proposition D.3). Thus applying the Sion Theorem over discrete domain (θ 1 , . . . ,θ m ) to the primal-dual optimal pair (s,q) gives q i (t)s j (t)ϕ ij (θ j (t)) = iq i js j ϕ ij (θ j (t)).