Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks
Authors: David A. R. Robin
Kevin Scaman
Marc Lelarge
Venue: ICLR 2024 poster (2024)
Keywords: Neural networks
theory of deep learning
convergence guarantees
random graphs
algebraic topology
Primary area: learning theory
TL;DR: We define a rich family of models, including sparse versions of all MLPs and convolutional networks, for which we can prove nearly-optimal convergence without overparameterization.

Abstract: We present a framework to define a large class of neural networks for which, by construction, training by gradient flow provably reaches arbitrarily low loss when the number of parameters grows. Distinct from the fixed-space global optimality of non-convex optimization, this new form of convergence, and the techniques introduced to prove such convergence, pave the way for a usable deep learning convergence theory in the near future, without overparameterization assumptions relating the number of parameters and training samples. We define these architectures from a simple computation graph and a mechanism to lift it, thus increasing the number of parameters, generalizing the idea of increasing the widths of multi-layer perceptrons. We show that architectures similar to most common deep learning models are present in this class, obtained by sparsifying the weight tensors of usual architectures at initialization. Leveraging tools of algebraic topology and random graph theory, we use the computation graph’s geometry to propagate properties guaranteeing convergence to any precision for these large sparse models.

RANDOM SPARSE LIFTS: CONSTRUCTION, ANALYSIS AND CONVERGENCE OF FINITE SPARSE NETWORKS
David A. R. Robin INRIA ENS Paris
Kevin Scaman
Mare Lelarge INRIA - ENS Paris
INRIA ENS Paris
PSL Research University
PSL Research University
PSL Research University
ABSTRACT
We present a framework to define large class of neural networks for which, by construction, training by gradient flow provably reaches arbitrarily low loss when the number of parameters grows. Distinct from the fixed-space global optimality of non-convex optimization, this new form of convergence, and the techniques introduced to prove such convergence, pave the way for a usable deep learning convergence theory in the near future, without overparameterization assumptions lating the number of parameters and training samples. We define these architectures from a simple computation graph and mechanism to lift it, thus increasing the number of parameters, generalizing the idea of increasing the widths of multi-layer perceptrons. We show that architectures similar to most common deep learning models are present in this class, obtained by sparsifying the weight tensors of usual architectures initialization. Leveraging tools of algebraic topology and random graph theory, we use the computation graph's 's geometry to propagate properties guaranteeing convergence any precision for these large sparse models.
INTRODUCTION
We consider the supervised learning task, of infering a function f X' from pairs of samples
(x, (xx) E X x V,, with following a distribution DD We restrict our attention to the case X Rd
and y = RR with a parametric model F R" x Rd + IR* approximating the target function as F(O",.) Rd + R for a fixed parameter 8" E R!. The loss L: 8 + E (r..) [[(F((. xx) y is
used to "learn" the parameter 0 IR+ - R by a gradient flow 0,0 = L()) from fg T
In the context of deep learning, contrary to more generic non-convex optimization, we are not intrinsically interested in global minima of the fixe-dimensiion parametric loss L, or in this model F specifically. This optimization is only a means to the end of finding, among family of models Fm R. Rdd + R of varying sizes m E N, one pareel-prrrettr pair (Fn, 0* E RT)) such that Fm (0 = f The ability of families of models, given as neural networks, to "scale up" to consistently avoid optimization issues is what the present theory aims to explain and predict.
Challenges. The class of models empirically known to reach near-zero loss when scaled up is large, and it remains unclear whether is possible to construct a formalism both sufficiently flexible to cover all such neural networks and sufficiently rigid allow non-trivial claims. For two-layer networks of width h with parameters 0 E Rdxh x p Cybenko (1989) and Barron (1993) have shown for various non-linearities a that for any continuous I X - R& with compact domain X' C Rd, and any threshold è E IR, as h - +00, there exists 0 such that sup,, [f(()) (x)]l2 S e. We call the minimal such width h the approximation number hf e) e N. This existence result does not imply that a gradient flow will converge to such a parameter. Nonetheless, the question of whether given architecture enjoys similar approximation properties has sparked much interest over the following decades, with extensions to more layers Leshno et al. (1993), more non-linearities (Pinkus, 1999), convolutional architectures (Cohen & Shashua, 2016), Brüel Gabrielsson, 2020) and outside Euclidean geometry (Kratsios & Bilokopytov, 2020), and with investigations of the link between width and depth (Poggio et al., 2017; Johnson, 2019), 9), and handling of symmetries (Lawrence, 2022). For the harder question of convergence, with two layers, Robin et al. (2022, Proposition 4.6) shows that for any e E R; and E j0, 1.. there exists a learning number hy (f* , 8, 5) N such that if h hi, then under standard initialization schemes, gradient flow will
(Xu et al., 2019;

---

converge to loss value below with probability greater than (1 8). Note that earlier infinite- -witt results hinted at the existence of this number (without assumptions on the sample count), e.g. Chizat & Bach (2018). The problem of focusing on only approximation is that the corresponding learning number could be orders of magnitude larger than the approximation number, since it corresponds to a much stronger property: the target function is not only representable with model, it is learnable with this model. Universal approximation is insufficient to predict which models will perform better in practice, because it fails to quantify the learning number h1, which could be intractably larger than the approximation number hu; in which case at all tractable sizes h E N with hy S h < h1, we would observe models not reaching low loss despite the existence of parameters in dimension h with lower loss. We seek to upper- bound learning numbers when approximation has been established. This size-varying gradient flow point of view is meant to model practical deployment of neural networks, in contrast with works that aim to find global minimum of fixed size by e.g. convex reformulations of two and three layers ReLU networks (Ergen & Pilanci, 2021; Wang ct al., 2021).
To curb the difficulty of constructing bounds for learning numbers with more than two layers, many attempts have focused on the simpler setting of a fixed dataset X E X of n E N training samples and growing model size, and provided (typically asymptotic) bounds for this X, independently of f", by leveraging positive-definitnnss of the neural tangent kernel (NTK) matrix under sufficient overparameterization (Jacot et al., 2018; Du et al., 2018; Ji & Telgarsky, 2020; Chen al., 2021). This allows viewing functions X' - R as contrast, our objective is to derive bounds for fixed f* independently of (thus infinite dimension). to avoid overparameterization assumptions relating number of parameters and samples, so our bounds depend on a specifi)) "complexity" of f", but do not diverge with infinitely many samples.
vectors in RR", by restriction to X. In
Related formalizing works, We obtain convergence guarantees for broad classes of "neural networks" when "lifted", by formalizing precise meaning for these terms, usable in rigorous proofs. The class of neural networks that can be described with this theory is more expressive than the Tensor Programs of Yang & Littwin (2021), in particular because it allows non-linear weight manipulations, and distinct "scaling dimensions" (e.g, embedding dimension versus hidden layer width in transformers, which need not be related). In that sense, the core idea is much closer to the description with Named Tensors of Chiang et al. (2023). Thus the focus is large but finite-size networks, contrary to infinite-width limits. However, the convergence shown applies only to sparse networks (in the sense of Erdös-Renyi, different from the Lottery Ticket (Frankle & Carbin, 2019) use of the term "sparse"). Several ideas used in our proofs are inspired by Pham & Nguyen (2021), which - in the context of non-quantitative mean-field convergence introduce tools show that throughout training, the distribution of weights, albeit finitely supported. has positive density in neighbourhood of any point.
Contributions. We discuss the tangent approximation property in Section 2, and show how implies probably approximately correct convergence when the model size grows. We introduce in Section 3 a formalism to build architectures having by construction a way to lift, and recover usual architectures in this form. We show in Section 4 that when such systems are sparsified at initialization in specific way, then tangent approximation is satisfied, thus PAC-convergence of gradient flows when lifting.
2 CONVERGENCE BY TANGENT APPROXIMATION
Let X CRd be a compact set, and let y = RR. Let F be the set of continuous functions from X' to V. Let 'D be distribution on X. Let / X' - y be continuous function. Let L F R2 be the function L: - EAaD [[][(x)) [x)]] We write for shortness 11.112 / + EAED [[]]
Let (S, 3) be an infinite partially ordered set. For s E S, let G. be a finite set representing "size-s architectures". and let O be knite-dimensione vector space with inner product. of corresponding "weights". For every s E S, let N₂ be a distribution on G, x +.. For every $ E S and E G., let F(s.g) θ, + F be differentiable function. Let S. S be an infinite set, called "admissible set".
We will illustrate constructions with two examples, of (possibly sparse) two-and three-layer networks without biases learn function Rd R. For two layers, S = N is the number of hidden nodes and G. = {0. 1) 1]dx= x {0, 1 1]ox1 the sparsity pattern of the layers. For three layers, S = N22 is the number of hidden nodes of each layer, and G = {0, 1] dxx x {0, 1] {0, 1] x1 the corresponding pattern. A choice of admissible subset- e.g. So = [ $1) E N² so I $1 } of networks whose width increases with depth- - rules out potentially behaved sizes, to formulate statements like "all networks (not ill-behaved) above given size (w.rt. X on S) have property P".
2

---

For E S G,, and any (x, E RR RT. let ( S 6, be the set defined
0 E (N, +
inf uce..
(0) + (F(s.g)(0) u 1'
The function e, is easily seen to be increasing. Let us flesh out some intuition about it. If Ag. + 2, then there exists a choice of weights 0 at size s such that F(s.g)()) approximates f* to error E. This does not guar- antee however that such weights are "learnable". The construction As.g(M; e) with a tiny non-zero x allows for some flexibility: the target is approximable by a lineariza- tion of F(s.g) with a tiny ([ull S k) variation of weights. Hence, As, (N., 5) is much larger than As.g (0, s), but un- der some regularity conditions on Fe.g there should always be a small ball around a point of (0, 8) that is included in As.g (K. E) (see Figure for instance). This regularity is irrelevant for universal approximation theorems, but crucial for learning theorems. The following property is sufficient to get convergence to low loss with high prob- ability. Intuitively, we need tangent approximation with tangent radius k, not for a point Oo. but an entire ball around eo. with a tangent radius allowed to grow affinely with the ball radius. Write B, (Bo, R) = {0 E O, ||0 - Bull S R} the R-ball in θ around cg. Condition C1 (Tangent approximation with high probability). Let (e, E E2, 10. 1].
fo
To doo u
fo
(
Figure 1: Tangent approximation to error (s-ball depicted by dotted line) for fixed s E ES g E G2 with f = F(e.a)- If [ - 1 < E, then 0 E A(0,e)) E). In contrast, @ E A(Ilu]]=)) \ A(0,
There exists e E R2 (a constant intercept) such that for any R E R4 (a maximal radius), there exists 81 (a threshold size) such that for all s E {s E Su s = $13 (admissible sizes above threshold),
P(o.0)~NN. (vr S R, (,, S As.g (c+ (,,) (1-
In words, with a three-layer network, this is satisfied if for an arbitrarily large radius R. there exists a threshold size $1 = (Ho, H1) E N2 such that if so = (ho, h1) is any network size satisfying ho S hi (i.e. 80 E So) and ho > Ho and h1 > H, (i.e. both hidden layers are above the threshold size), then with high probability over a random weight 0, an entire ball B, (0, (0,11 R) around this initialization has tangent approximation. We expect in this setting that we can't 't say anything for networks whose width is not increasing with depth (they could be ill-behaved), but other than that, any configuration above the threshold size has (with high probability) the desirable property of tangent approximation at initialization and on a large ball around the randomly drawn initialization. Therefore if this holds, we can expect that gradient flow will have some desirable properties (granted by tangent approximation) for a long time after initialization, until it eventually exits the ball. The desirable property in question is a "sufficient decrease" property of the loss, materialized by local separable Kurdyka-E.ojasewwic. inequality. Indeed, by parallelogram identity, 2( -2(d (F)()) u, F(0) f*) f= [((() + dF(() u 1+ Moreover, for a gradient flow 0,0 = VV(()) we have d, (e = -Ve 12. Leveraging the variational form of the fo-nrm. we get (Co F)
|dF(()) - u/|2 + (1)
sup,, 4(dF(()- u, F(O) /*2//|lul 2 -CC F (-e), /c ||0 - 0oll) for as long as 0 E (fo. R). The separable structure of this bound with respect to L o F and || Gall. together with the ability to choose R arbitrarily large, is sufficient to conclude.
To get feeling of why this assumption might be satisfied, picture a large sparse network with "diverse enough" sparsity pattern (the clarification of what this means is the subject of this paper). If there exists network, sparse or not, of small size that approximates the target function, then at initialization, there should be a myriad of small subnetworks identical to that approximator inside the large network. If the last layer is linear, then "selecting" convex combination of these outputs is sufficient to reach low loss. Although the output of the large network may differ from the target, there is modification of its last-layer weights that approximates the target function. Lastly, if there many such subnetworks, then a small modification of parameters cannot substantially modify them all if the large network is large enough. The following theorem ensures that tangent approximation is indeed sufficient, the rest of the paper gives a precise meaning to the intuitions of this first section.
Convergence Criterion 1. Let θ be a vector space. The pair (C: : O + R4,, Oo E +) satisfies this criterion with limit error E 14, and constant K E IR. for all 0 : R4 + O such that 0(0) = Oo satisfying 0,0- VL))), it holds Vt E R L (0.) S E + 1/ // kt + 1/c where L(0))² E RR..
3

---

Theorem 2.1 (Probably approximately correct convergence in loss). Let (Eu, óu) R2, x Jo. 1]. If for B0) ~ Ng the variable Lo o F(s.g) (9)) E R4 is bounded uniformly in s with high probability, and if Condition CI is satisfied for parameters (cg, 60), then for any & > Eo and > dg, there exists 31 and (g. 90) ~ No. with probability at least (1 8)), the pair (C o F(s.g),00 06) satisfies Convergence Criterion with error and constant k. This statement is a slight extension of Robin et al. (2022, Proposition 4.6) with nearly identical proof. The main contribution of this paper the construction of the sparsification in the distribution N₂ satisfying by construction the tangent approximation condition when lifting. This includes architectures such as multi-layer pereeptrons, convolutional networks, and attention- mechanisms.
E I3+ and E S such that for all s E So satisfying
PERCEPTRON MODULES
For consistency and shorter notations, we use the co-product symbol [[ for disjoint unions. Formally, for family of sets (Ae)c indexed by c E C, define ILagc A. = Uxec {c, a) a E Ac A surjective function p. Y + V from set Y to a finite set V induces partition of Y into Y, =p'((u) indexed by u E , i.e. there is bijection (a. an isomorphism of sets) Y R LL Y,. It equivalent to specify p or the partition of Y. Given Y. a choice of one element in each part (called a section') is a Ilvvv Y,..
function V - Y such that Vu, s(v) E Y, (i.e. pos Idy). This is also written
Definition 3.1 (Euclidean bundle over a finite set). Let V be finite set. A Euclidean bundle over V is a set Y and partition Ll Y,, such that for any v E V, the set Y, has the structure of dimen-dimeni I--eccorr-ppace equipped with an inner product (i.e. Yo is a Euclidean space).
The simplest example of Euclidean bundle is Y V x IR which "attaches" to each v V the Euclidean space Y, = R. The interesting property of these objects is that all attached vector spaces need not have the same dimension, c.g. R" II &x with V = {0, 13 is Euclidean bundle, whose sections are pairs (u, w) E R" x _*xın We will thus use these objects to describe parameter spaces. Definition 3.2 (Pullbacks of bundles and sections). Ler Lo Y, be a Euclidean bundle over V, and let U be a finite set. Any function π : U - V defines Euclidean bundle π Y = IIuEv Yz(w)) and a function πt" II Y. - Iuuu Y=(uj. called a pullback of sections, n² : s + (sn(w)) nEU
We will use pullbacks to describe how to "make copies" of a space with a function n: + V. This is illustrated in Fig. 2, where from a bundle Y we construct a new bundle having varying number of copies of each space. n² also transports a choice 8 E II Y, to Iwer Yz(u) by "copying over".
R
R² O
R
Y LbEV Yv Z:U-V
(m*) LlEE Yz(u)
R
R
R
Rkxk
Rexk
Figure 2: Illustration of the construction of pullback bundle, with U + V indicated by arrows. The top row is a set V with elements pictured as circles, and bottom row is with 6 elements. The vector spaces attached to each element are depicted next each corresponding circle.
3.1 GENERALIZING MULTI-LAYER PERCEPTRONS TO ARBITRARY COMPUTATION GRAPHS
We use the definition of (finite directed) graph G = (V, E)) finite set V and set E S V V. We write Gi-,,) the parents of u E V in G. and G(v, -) its children, see Appendix A for a summary of notations and Appendix C for details on graphs. With the idea of describing neural networks, take a computation graph whose vertices indicate variables in a program, and specify set of "initial" vertices / corresponding to inputs, and "terminal" vertices T corresponding to each vertex u a vector space y. of "activations at v", and to each edge (u, v) a vector space W(..)) of 'weights"" of the connection from u to v. For more generality, we also use a vector space ((,,,) of pre-activations to represent the intermediary variables before the non -on-liie d. associated to e.
outputs. Then, attach
'The nomenclature is that of algebraic topology, where these objects are common, but no prior knowledge is assumed. The names bundle and section serve only distinguish products/ / co-prodducts with words.
4

---

Definition 3.3 (Perceptron module). Let B (V.E) be a finite directed acyelic graph.
A perceptron module over B is a tuple = ((I,T) 2, W), (M, σ)) composed of
A subset I S V such that I = B(-,t) 2, and subset T V... Three Euclidean bundles, y LwEv Ve, and W LlER We, and 2 L Ze
A family of functions (Me)eer such that M (v,o) ((,))) x y + ((,,))
A family of functions (Ju),evy, such that dy [[ (v,,)) + Vo
We write Param(BB) (B) IeeE We. and PMod () the set of perceptron modules over B.
The definition of perceptron modules (and later their lifts in Def. 3.5) is not restricted to multi-layer perceptrons, and is chosen very general precisely tackle advanced computation graphs (e.g. Fig. 6). In most simple instances, the M map would be regular multiplication (a. b) E I. x R + ab E R, and the map an addition and non con-linearity, e.g. 2 E I + tanh (E+ 2,), summing over parents.
Definition 3.4 (Activation map, or "forward" function, of a perceptron module), Let B = (V, E). A perceptron module B (1I,T) (V,, 2, W), (M, o)) )) E PMod(B) comes equipped with a map
F [
II W. x II y VE1
+II y'
eEE
DEV
with (F (w, ④) + f) defined inductively over V V by fo = D if E I, and of I as
fu ov (MM(u (W(mo)) fu) wEB(-)))
In general, to be usable, it is also mandatory to describe how the inputs are connected. For instance in Fig. 4b with a function c: - grgg b to ensure x + (w, c))) has inputs in TR (n..)))) not TR.
With the Euclidean bundles W = E x R and y = V x R, the restriction to T of this function (w, ②) + [F[B] ur, D)) T has type IR' x I2 - R* where m = #E E is the number of parameters, d = #1 E N the number of inputs, and k: #T E N the number of outputs. The notation with products will become more interesting when the dimension of weights are more unusual.
Blueprint notation. Instead of depicting the acyclic graph B, with lots annotations, we use the following graphical convention. We draw vertices as circles, edges squares, with horizontal arrows to indicate vertex-edge incidence, and vertical arrows from small circles to indicate weights. We annotate each arrow with a vector space (W from a small circle to square, y from a circle to square, Z from a square to a circle), and each shape (circle or square) except initial vertices with function (respectively a and M) whose domain and codomain matches the spaces defined by the incoming and outgoing arrows, cf. Figure 3. We depict terminal (resp. initial) vertices with continuous (resp. dashed) double circle.
Wav
V
Z Zuv
y
Muo
Figure 3: Generic blueprint notation
3.2 LIFTING PERCEPTRON MODULES THROUGH HOMOMORPHISMS
This theory describes complicated functions by constructing a "base" perceptron module B, and then applying "lift" operation (Def. 3.5) to build more powerful module G. impossible to draw due to its large size. The intuition for how to do so is depicted in Fig. 4 with the example of the multi-layer perceptron (MLP), "replicating" vertices vertically to increase the "width". Fig. 4a depicts a perceptron module corresponding to an MLP architecture with two hidden layers, with activation R - R, and
bundle ) V R and weights W E x R. parent summation and non-linearity maps M(..)) R x RR + IR the multiplication (a,b) + ab. No matrices appear on this blueprint. Specifying this module, "width" for each layer, and the connection of inputs, uniquely defines the MLP. Thus we annotate each vertex with an integer in Fig. 4a, to specify the width of the layer in Fig. 4b. The parameter space after lifting becomes x x 2 6 Note how the weight matrices W R3x5 W(1. R and W W(2,3) E 6 arise from the lift. Similarly, for convolution operation for which we would use this lift operation to construct more channels, we expect weight space W(,,)) V x I to give rise to tensors W (a..) E V z Bkxn_ corresponding to n,, input-channels and n, output-channels for that convolution.
5

---

We will give general definition of (sparse) lifts first, the fully-connected example is recovered subcase later. Intuitively, from the same base module of Fig. 4a, we construct the MLP with underlying graph G (from Figure 5a) as a perceptron module. This is done by "copying" nodes to construct layer of hidden nodes in G from the single node in that is copied over. How to perform this copy (i.e. how many times to copy every node and how connect the copied nodes) is specified by G and a homomorphism IT G + B. The vertex map VG VB indicates the number of copies (o E Va yields nodes x (r) VG), and the connectivity pat- tern is indicated by the structure of the graph G (which may be sparse) and the induced edge map π Eg + Eg. This coincides with the transformation depicted in Fig. 4 (dense) and Fig. 5a (sparse). The condition that π is bomomorphism of graphs ensures that this construction is well-defined. When there are many incoming connections vertex e Eg. mapped by æ to a single edge E E.B. such as in Fig. 4b and Fig. 5, the corresponding pre-activation values v(,,v) for (u, π (e) are summed before the computation of the non-linearity.
R R
R
BORTROR Ida
Blueprint notation of the base module B and lift annotation n. VB + N above vertices (see Definition 3.6) for ML.s
g
(b) Graph notation of the fully-connected lift G. the homo- morphism o G B is given by vertical projection to (a)
Figure 4: MLP representing functions IR (n.g.b] E
b
(b) Smaller sparse lift with the same base module B as above. This smaller network (b) is "contained" (strongly, extracted by fibration, in the vocabulary Scction 4) in the larger network (a). The inclusion denoted by a (dark) red coloring of the nodes in (a).
(a) Sparse similar to multi-layer perceptron.
Figure 5: Sparse lift graphs, denoted in the more general Def. 3.5, not covered by Def. 3.6.
Definition 3.5 (Lift of perceptron modules). Ler G = (Va, Eg) and = (V En) be graphs. A homomorphism of graphs æ G - B defines a function x" PMod (B) PMod(G) called "lift",
2, (W,, (M, + ((x (T), ((=-1(),, (T)), (T) V,'' 2, W),, (M,
where for E Eg, Me = Ma(e), for E VG \ ((), o, IuEG(-,)) Z - Vi(() is
o 2 + Oz(e)
2(u,w)
UEE (EE (())
(EB(-((()))
Let be a finite set and Pc : C I. Define LiftPMod(BB, C) as the set of tuples (G, n, where G + B is graph homomorphism, and क -1( C an injection such that pc -
We extend the notation of forward functions G (G, a) c) function F[G]: Param (G) x I )pe(u) IIvevo De as F[G) (w,x) + Flr
LiftPMo((BB, C) by defining the
Recall that the bundle y is equivalent to a family (Da)veV of Euclidean spaces, so the the pullback >" Ln Pr(v) is equivalent to a family ((=')), -'' consistent with the intuition of "copying" activation spaces when replicating nodes (and similarly for Z and W indexed by edges). Validity of this definition (e.g. well-definition of the z-sum) is easy to check, details in Appendix K.1. Our later convergence theorem will only apply to particular sparse lifts, but most common deep learning architectures lift which is maximally connected, yielding dense weight tensors.

---

Definition 3.6 (Fully-comma connected lift), Let B (VB. be a directed acyelic graph.
Let n: VB - N be a function, called the "lifting dimension". ". Define the graph C. = (Vo, Ec) as
Ve= {b, be E VB,i [mol} and Ec { (u, Vc Vc (M(u), T())) EB
with : VC + VB projection to the first coordinate. We call C' the fully-conmected lift of B along n.
Similarly if PM) we call x x'B PMod(C) the fully-commected lift of I along n. IfC = [ [mo] (i.e. an order of inputs has been chosen), then (C, π. Idc) E LiftPMod(BBC)
We can check that the forward function of the lifted module from Fig. 4 is the usual perceptron forward. Indeed, for a vertex U E VB \ LB. and i E [me], we get the activation f(v.)) E V. R as
S(u,s) ov
Σ
M(ww) (Waas) ((ws)) or Σ
Sluss "(uN)KeN))) (E(mal
(w.j)EC(-((v.3))
with u the unique parent of v in B in the last part. In matrix notation, fo To (fu- W W(w.w) E R..
more interesting example. Using the operation AddSoftMul (RR x IR) x Ruxx - R", ((x, v), A) + x + softmax(A) (A) y, where the softmax is taken over each row (and potentially masked), we recover modules similar to the transformer blocks of Vaswani et al. (2017) (see Figure 6).
R
AddSoftMul
R
Add
q
IP
R
R"
R"
R T
R"
R
IR2
R
d
h
R
X
R
II
IR
ReLU
Figure 6: MixingTrransformee X E R2x Y Ruxs weights (top-to-bottom, left-to-right);
(MA. Wv) E R9xk x Rook, MB E 1xx (We, Wx) E Rexd x Raxd Ho E R Rkxh Hi E hxx
Z = X MA + softmax (XX ((X-Wo)-ue (X -x-Wx) (X Wv), Y = Z MB + oZ HH) HI
The first block (X + 2) is a usual self-attention when = and the mixing matrix is M = Lq. the
second block (Z - Y) is residual MLP block when and the mixing matrix is MD Ig.
RANDOM SPARSE LIFTS AND CONVERGENCE OF SPARSE PERCEPTRONS
We start by reviewing the proof ideas for the convergence theorem, give intuition for the definitions.
Split setup & easy recombination. To analyse a large neural network with linear last layer, we split into composition, first of a perceptron module computing deep features (whose number will scale) followed by a linear recombination function (whose input dimension will scale, but output dimension remains fixed). With fixed features, learning the last layer is easy by convexity, in particular if "optimal features" are present then the global optimum of the last layer must have optimal loss.
Coverage property. the perceptron module representing the features sufficiently large, should "contain" a sub-network computing near-optimal features. The usual way to understand this term for a directed graph G (Va, F.)) to select "subgraph", which is graph Vs S VG and E.g C F.g. This is for instance the way such "sub-networr"" is understood in the lottery ticket hypothesis (Frankle & Carbin, 2019). the language of graph theory, this corresponds to an extraction by homomorphism (because the inclusion Vs + VG induces homomorphism of graphs from S to G). These "sub-networks" are in general very different from the larger network, and do not necessarily compute the same functions (it is the lottery ticket hypothesis that they actually do lear similar functions, by a yet-unexplained mechanism). There is in graph theory (and algebraic topology more generally) a different way extract what we could call "strong sub-graph", by
(Vs, E.s) such that
7

---

fibration instead of homomorrhhssm. The inclusion map Vs + VG is fibration of graphs if the following two conditions hold: first, if (u, E Vs x Vg and (u,v) E Eg then (u, v) E Eg (no "removal of edges"); also, if v Vg, then G(-,o) Vs (no "removal of parents"). Intuitively, if S and G are viewed as computation graphs, then removing an incoming edge or removing a parent will change the computation, while removing a child does not. Thus if S is "strong sub-graph" of G, extracted by fibration, we can extract the subgraph then perform a computation in the subgraph and isolate an activation, or we could equivalently perform the computation in the larger graph and then extract the activations associated to the subgraph and isolate the activation of the target vertex. When multi-layer perceptrons are constructed with dense linear layers, a network of width 2n does not contain (in the sense of "strong sub-graphs extracted by fibration) sub-network of width This is because the number of terms in each sum 2n in the large nework, one for each parent of the node considered, which is fully connected to every node of the previous layer. However, fibrations preserve the number of parents, and the smaller network has n terms in each sum, again one for each parent, but there are only such parents at width Nonetheless, we can easily construct networks that do have this property of containing smaller sub-networks by construction, by simply sparsifying the dense layers, similarly to a dropout masking operation that would be performed at initialization and whose mask is held constant throughout training. In these sparse networks, increasing model size cannot hurt (provably) because a large network "contains" (strongly) small sub-network that is computing the same thing as a smaller model. The coverage property that we need is only very slightly stronger: there needs to be certain fraction (or "volume") ") of sub-networks that are near-optimal, not just one, the precise details are in the formal statements of Appendix H.
Local stability of coverage. The existence of sub-networks computing interesting features at initialization is insufficient for a convergence proof, because we intend to train the weights of the large network, and thus we expect the weights to move and have no guarantee that the sub-network will continue to perform a similar computation throughout training. The last ingredient we require is that the large network has a low "outgoing degree" (i.e. each vertex the directed graph has few children), such that there is no vertex whose activation is re-used too much by later vertices, single point of failure that could perturb the entire network if its weights move slightly too much in the wrong direction. Coupled with a covering in volume, this low-degree property implies that there is an entire region of parameters around initialization where we can guarantee that there is a sub-network with near-optimal features, rather than only at the single point of initialization. This implies that at initialization of a very large sparse network, we expect a large number of sub-networks to be near-optimal, and throughout training the number of near-optimal sub-networks can only decrease slowly (due to the low outgoing degree): if sub-network is perturbed enough to no longer be close to an optimal feature, then the last layer can simply switch the associated weight of this sub-network to similar but un- un-perturhed sub-network to recover optimality (acceptable due to easy recombination).
4.1 RANDOM SPARSE LIFTS OF PERCEPTRONS MODULES
From now on, we will only ever consider a single base module with various lifts. Therefore, let B = (VB, be a finite directed acyclic graph. Let E PMod(B) be a perceptron module, and write its components B ((I,, TB). ()), 2, W). o)). We will also keep fixed the number of lifted inputs (comparing modules with different inputs is not very useful anyway). Let n1 In - N. and C = b [ng] (without loss of generality on a finite set C IIbeI C. after ordering Co ~ [mg]).
The first ingredient needed is the presence of linear last layer with fixed output dimension even when the number of nodes in the perceptron module computing the "deep features" tends to infinity.
Definition 4.1 (Perceptron with linear readout). Ler G = (G, x. E LiftPMod C), and k E N. Let LinReadout k) IIvETTa; Pa(e)* & with LinReedduul k) x ILvv(()) Mn(e) + R2
(a, x) --
Σ TET
Σ DEX (b)
(ai. Foly
# (b)
KE(A)
We can now describe the sparsification procedure. Note that the following definition is equivalent to using a fully-connected lift and random dropout mask m, drawn at initialization and fixed during training. We expect the probability distribution chosen on weights W. to be a normal distribution in all applications (thus write it A), but we will only require the assumption that it has full support.
8

---

Definition 4.2 (Random sparse lift), Let VB N be such that na, = =n,, for all b E Ig. Let x: Eg + R., for every e E Eg, let Ne be a probability distribution on We.
Let C (Vc, Ec) be the fully-connected lift of B along with homomorphism π C - B. Let (m Ec + {0,1}, 1], w : EE + π T'W) be independent random variables with distributions m(a,0) Bern (orn)) (x((x) Bernoulli for any (u, v) E Ec, and with We ~ No for EEc.
The random sparse lift of B along (n, A) with distribution N is the tuple (G, wlE), where G = (V. E) the random graph with V = =Vc, = {e E EE | m. = 1}, G is the listed perceptron module G = (G, T, Ide) E LiftPMod(BB.C C) and U|E E Param(G).
For an architecture for which universal approximation has been established (i.e. the approximation "number" ho( E) is finite), we show that we can construct random sparse lifts for which the learning "number" hi (f e, 6) is also finite for failure probabilities 5 0 arbitrarily close to zero. However, in general this "number" is not an integer but an element of N where k E N is the number of scaling dimensions (one per vertex of B). We refer to the network approximating the target function as the witness network, since it is witness for the universal approximation theorem at a given precision.
4.2 CONVERGENCE OF SPARSE PERCEPTRONS
Let X IILEE Pppctu) be compact, D distribution on X, and let f*: X - R* with /| < co. For any G E LiftPMod(B. C), define the loss [[G] Param(G) x LinReadout(G,, k) - R4 as
[[G]: (w, a) + EL-D [||a F[G] f
Let À= Eg + RT. For e E En, let No be a full-support distribution on W. Additionally, de- fine So {n: VB + N vb E LB, nu = =n. Y(a, b) E EB, n4 2 na log ) where ng. =#re (b). We assume B3 has (M, o) maps that are continuously differentiable, to ensure gradients exist and have finite norm. Finally, we assume that for (a, b) E En if a E I then A(a.b) S min(n2/2 (n2/3) //3).
Theorem 4.3 (Probable approximate correctness of random sparse lifts under gradient flow).
Let (z E 1R x J0, 1]. If there exists G* E Lift C) a lifted perceptron module, and parameters (w* aa)) Param((** x LinReadont(G', k) such that [[G'] aa) e, then there exists K E R2, and N1 : VB= + N (a size threshold) such that the following proposition holds:
For all n So such that > N1, with probability at least (1 - 8) over (G, w) a random sparse lift If along (n, X) with distribution N, and a = O E LinReadout (G,k), k), the pair (f[G), (w, a)) satisfies Convergence Criterion 1 with limit error and constant
We give in Appendix J a quantitative version with bounds on N₁ and k as a function of the witness network structure and choice of parameters, allowing for future quantitative research in this direction. Note that this is immediately extended to a loss f + (z. [ll - y with E(z.g) ||l/ < co. Indeed, that is equal to | - 11, E []] for f x H (xX,))=D(Y [Y = z]. Moreover, note that this theorem holds for any s E R and not only near zero. This statement thus truly matches what it means to converge to the infimum of the LiftPMod(B. (B, C) class with large lifts, which should prove most interesting when that architecture is restricted respect certain symmetries by construction.
We believe that the conditions here are interesting because they are easy to verify. (1) The condition that the architecture obtained as a random sparse lift can be satisfied by construction with little restriction on architecture search. (2) The condition that any lift (sparse or dense) with low loss exists can be obtained by universal approximation, or empirically because any network with low loss can serve as witness. Proving or disproving a similar result for dense lifts is left as future work.
We modeled dynamics in continuous-time and considered only convergence in loss. Convergence of parameters will require more assumptions, see e.g. Patel et al. (2022, Section 2). Discrete time results results, see e.g.
will also require more assumptions, but are often obtained by extending continous-ting Even et al. (2023, Theorem 1). We did not assume that D is finitely supported, to facilitate extensions in online learning with test-loss bounds from stochastic gradient estimates on finite samples.
Conclusion. We have shown PAC-convergence of large random sparse lifts under gradient flow to the infimum over all lifts, by introducing a strong formalism to define a large class of neural networks and the tools to track their activations across training to show tangent approximation properties for long enough time. We believe that this direction constitutes promising route to a strong convergence theory for deep learning, with principled architecture design and testable empirical predictions.

---

ACKNOWLEDGEMENTS
The authors acknowledge support from the French government under management of the Agence Nationale de la Recherche, reference ANR-19-P31A-0001 (PRAIRIE 31A Institute).
REFERENCES
Andrew Barron. Universal approximation bounds for superpositions of sigmoidal function. iece trans. on information theory 39, 930-945. Information Theory, IEEE Transactions on, 39:930 945, 06 1993. doi: 10.1109/18.256500.
Rickard Brüel Gabrielsson. Universal function approximation graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural In- formation Processing Systems, volume 33, pp- 19762-19772. Curran Associates, Inc., 2020. URL https: htaps://prrceeednggs wtwpeeeedddinnne.eniieeeeeeeeeee neurips wttppppee..illeepppeeeeeeeeeeeee Sttp:tr33995122dppppr..ee. Paper.pdf.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over-parameteriizaion is sufficient to learn deep relu networks? In International Conference on Learning Representations, 2021. URL https: wwwpreoeew.eeeeeeoooo.poee.ooewe
fortt//ormmm wtwp:n/dddddgddddeadaaa fgd7we_uZa6.
David Chiang, Alexander M Rush, and Boaz Barak. Named tensor notation. Trunsactions on Machine Learning Research, 2023. ISSN 2835-8856. URL pesttps://ppezeveeee net forum?
id-hVi7sHlilx.
Lénaic Chizat and Francis Bach. On the global convergence of gradient descent for over- over--arameeete parameterized models using optimal transport. In S. Bengio. H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and Garnett (eds.), Advances in Neural Information Processing Systems, volume 31.
Curran Associates, Inc., 2018. URL https: /ttpc////////ooeeeeeeeeeee neuri cc/paper_ files/
6d726 6d726-Paper. pdf..
Nadav Cohen and Amnon Shashua. Convolutional rectifier networks as generalized tensor decom- positions. In Proceedings of the 33rd International Conference on International Conference Machine Learning Volume 48, ICML''1,, pp. 955-963. JMLR.org, 2016.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2:303-314, 1989.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2018.
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks via convex programs. In International Conference on Machine Learning. PMLR, 2021.
Mathieu Even, Scott Pesme, Suriya Gunasekar, and Nicolas Flammarion. (s)gd over diagonal linear networks: Implicit regularisation, large stepsizes and edge of stability, 2023.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable
neural networks. International Conference on Learning Representations, 2019. URL https:
//openreview.neee net pppeen/ereeinnet//oooomeodd---dd
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: convergence and generalization neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 8580 8589, 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. International Conference on Learning Representations, 2020. URL https: opw.reviee.eeeeepo/o n forum wiweeiggggryyyeeeee
Jesse Johnson. Deep, skinny neural networks not universal approximators. In International Conference on Learning Representations, 2019. URL https: http:///pppeeeeeeeeee net /forrm??
dd=ryGgSsAcFQ.
10

---

Anastasis Kratsios and levgen Bilokopytov. Non-euclidean universal approximation. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 10635-10646. Curran Associates, Inc., 2020. URL https: http:: /tpp:s////occeeigggeeoee neur htt.sesscc..ppp.ppppppeeeeeeeeee cttppppccccppppeeeeeeeeeaa 2ttpperrrileee/pppe/220000 www.fiespppppeee ppppp//pprr///////////
Hannah Lawrence. Barron's theorem for equivariant networks. In NeurIPS 2022 Workshop on Symmetry and Geometry in Neural Representations, 2022. URL https:://ppette /ppnrevien...e..
net/ Eorum? Be111G__wwEX-XP_1 W.
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feed- forward networks with nonpolynomial activation function can approximate any func- tion. Neural Networks, 6(6):861-867 1993. ISSN 0893-6080. doi: https///di..rr/// rect. cot.ccccccccceeeee
1016/80899-60000005880113333
URL htttps:/www..cceee atriclee/ss//0008000000000000
Wolfgang Mulzer, Five proofs of chernoff's bound with applications, 2018. URL https: pettps://page.
mi. wurberueelllee in de mul www.eeeeeeeeeeee pubbs/ chernoff. .df..
Vivak Patel, Shushu Zhang, and Bowen Tian. Global convergence and stability of stochastic gra- dient descent. In S. Koyejo, S. Mohamed, A. Agarwal. D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. ciates, Inc., 2022. URL 2022 wwlee/illee/eeeeee wttpl//eeeeee44ee0e2eee
Curran Asso- files/paper/ pdf.
wwwiingg....uuuueeeeeeeeeeeennee neurips cc / 60444896966666444499 Paper-
Huy Tuan Pham and Phan-Minh Nguyen. Global convergence of three-layer neural networks in the mean field regime. In International Conference Learning Representations, 2021. URL https: http:s///ppeeeeeeww net/ / fo For corrmmiiie -
Allan Pinkus. Approximation theory of the mip model in neural networks. Acta Numerica, 8:143- 195, 1999. URL https: / api. commanicsccoll...
org/ Corpps ID: :D:1::::::10 66000260.
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when can deep-but not shallow-netwood networks avoid the curse of dimensionality: a review. International Journal of Automation and Computing, 14(5):503-511 2017.
David A. R. Robin, Kevin Scaman, and Mare Lelarge. Convergence beyond the peer-parameterized regime using rayleigh quotients. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Infor- mation Processing Systems, volume 35, pp. 10725-10736. Curran Associates, Inc., 2022. URL https: https://proceedines nerriipss. cc/paper files/ /ptle///pper//22// Pww.raappeeeeeeeeeeeeeee-------e pdr.eenneee............ pdf.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL
www.fflle/ppaeee htt.le//ppppr/2117/ Paper. pdf.
Yifei Wang, Jonathan Lacotte, and Mert Pilanci. The hidden convex optimization landscape of regularized two-layer relu networks: exact characterization of optimal solutions. In International Conference on Learning Representations, 2021.
Robin J. Wilson. Introduction to Gruph Theory, Prentice Hall/Pearson, New York, 2010. ISBN 027372889X 9780273728894. URL https: : www.matti.. www.:/atthseee......... ukk.c..k/vvi.......... papers/wilsongere wilsongraph. .pdf.
ranick/
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https:
//openreview www.nee. net/ forum? forum?ddrryGa 61A5km.
Greg Yang and Etai Littwin. Tensor programs iib: Architectural universality of neural tangent kemel training dynamics. In ICML, volume 139 of Proceedings of Machine Learning Research, pp. 11762-11772, PMLR, 2021.
11

---

A SUMMARY OF NOTATIONS
Table I: Summary of principal notations used in this document
B (V BB)
The base graph, for the base perceptron module
G = (Va, Ea)
The lifted graph when there is only one, the graph of the random sparse lift in the last theorem
G* = (V*,E) E*))
The graph of the witness network, the lifted per- ceptron module achieving the loss threshold.
v(- = {ue Vo (u, Ea) for E VG
The parents (direct ancestors) of vertex in G.
G(u, -) = {u Va (v,u) Ea} for E VG
The children (direct descendants) of in G.
B = ((I.. Tp). (V) 2, (M,r))
The base perceptron module (Definition 3.3). The functions (M. σ)) are continuously differentiable.
C II C. or Pe : + lB
The "meaningful names" of input connections. This is "simplified" to C. {O..... #Co - 1} in the proof without loss of generality, but leaves room for easier implementations. For instance, for single input type Ig {img), lifted to three channels (one per RGB color). meaningful names can be Cimg {r. g, b), instead of {0, 1, 2}.
belp
X S II II ybb bElg cECs
compact subset inputs accessed "by name". With two input types Ig = {img, text), }. lifted as above for the image and to E N tokens for the text with Crext [T]. then Ibse,y Ioee, 3%. Vimg (rig.d} x Vrext" The spaces 3/, can be dis- tinct, e.g. Ving IR 256 and Vext RR with an arbitrary embedding dimension.
(G, TT.c) E (Bft C)
A lifted perceptron module (Definition 3.5). The homomorphism π
B encodes the struc- ture of the lift, the map provides the connection to inputs (e.g. which vertex the r-channel, etc.)
Param BB
II eEEg
We
The parameter space of the base perceptron module E PMod(B). There one (multi- dimensional) weight per edge in the base module. All spaces W. need not have the same dimension.
Pa II nERg
Wa(e)=
II
II
We
The parameter space of lifted perceptron mod- ule G = (G. n, c) LiftPMod(B, C). There is one copy of W. per edge f Fg with क (f) e. The number of edges will grow when scaling up. the dimension of the spaces W. remain fixed.
eEEg SEEc T(}==
F[G]: II Wa(e) Il
3 Ppe(u) II VA(C) vEVo
Forward function of lifted perceptron module (,,e) c) E LifcPMod(BB, C) over G Vo.Ea) with homomorphism æ G B.
cEEg
ueC
== (G,
LinReadout(G,he
II TET(G)
Va(o)* &
Linear readout of perceptron module (i.e. linear last layer), see Definition 4.1.
12

---

Throughout this paper, haen-open intervals are noted a. bf {u E R a < u < b} and [a, b[ = fu E R a a u < b}. We use liberally parenthesis brackets group factors in our proofs, for readability and without any particular distinction. We write "log" for the natural (or base-e) logarithm, i.e. Vu, log logexp(()) exp(u) = u. For time-dependent quantities, we rarely distinguish between index notation and application,
the french notation conventions, in particular 0 N, the open and
for : 18+ + R² function, we write 0₂ = (t) either in index or between parenthesis and use whichever more readable depending on context (only exception when both a function and Oo a constant are defined at the same time, but we take both to coincide anyway) The norm notation ||-Il is used only in finite dimension and always indicates the Euclidean norm ||v]yy v (v, v)v, a.k.a. 2--nrm:: ||u]1 = Σ, uf in an orthonormal basis. On products of Euclidean spaces V and W the corresponding norm is the induced Euclidean norm the product (v, w) Vv
/ ||
Table 2: Summary advanced notations used mostly in the appendix
T(G) = n (TT)) and I(G) (Imn)
The initial and terminal nodes of a lifted percep- tron module G (G, x.,e. E (ift C)..
V(G) Ve and E(G) EG
The vertices and edges of the underlying graph G = (Va, Eg) in a lifted perceptron module G (G, TT, c)
Lift (BB,
H (VH, En)
The other lifted graph when there are two.
S (Vs,Es)
The subgraph of G extracted by fibration.
Gal-.v) = π (a)
The "type-a" parents E VG. with a E VB vertex of the base graph, and G B is the homomorphism indicating "types". In MIPs, the "type" is the index depth of the correspond- ing layer. In more general perceptron modules, the notions of layer and depth cease to be well- defined, they are replaced by the pre- pre-image by of given vertex or edge in the base module.
x II Va(e)
Pullback bundle of activations for a lift (G, CT, E LiftPMod(B,, C). see Definition 3.2.
vEVa
n W' II Wa(e))
2'Z = II Zx(e)
Pullback bundles for weights and pre-activations.
eEBa
<EBc
(m' w)) E II
Wa(e) for
II W bEEb
Pullback of sections (here, weights). This corre- sponds to an intuitive copy, i.e. r="),, Wx(e)-
eEFa
0-: IILEV Dn IL Vols)
Pullback of activations by map e VG + VH.
:
The partial fibration from graph G to graph H, i.e. subgraph S of G such that the inclusion :: - G is a fibration, together with a fibration i S H, see Definition H.1.
(8,4) c.)) - (G*, (.)
The Lifd (B, mo-morhhism from the ran- dom sparse lift to the witness. See Definition F.I.
13

---

B ORGANISATION OF THE APPENDIX
Appendix C recalls the usual definitions for graphs and various types of morphisms between them. Appendix D studies the effect of the constants in the definition of Convergence Criterion I to give some early intuition. Appendix E gives the proof of the probably approximately correct convergence Theorem 2.1, showing how tangent approximation properties are sufficient to get convergence. Appendix F introduces the concept of morphisms of lifted perceptrons. Appendix G shows how to track activations even when weights can move, by leveraging the aforemeentonned morphisms. Appendix H shows how the tangent approximation property can be obtained from covering property. Appendix shows that the covering property previously defined satisfied with high probability in random sparse lifts. Appendix J ties everything together in quantitative version of Theorem 4.3. Appendix K provides all the more cumbersome proofs of well-definition of all concepts introduced in the document. Finally, Appendix L provides the proof of several small technical lemmas for bounding random variables that were used to alleviate the proofs of previous sections.
C GRAPH DEFINITIONS AND LEMMAS
C.I GRAPH DEFINITIONS
We consider the language of graphs known the reader, see Wilson (2010) for thorough introduction otherwise. All graphs we consider are finite directed (see Wilson (2010, Chapter 7) more precisely) and acyclic. We use the following definitions in our proofs.
Definition C.1 (Graph). A (directed) graph a couple (V, E) of a finite V and set E CVV..
The set V is called the set of "vertices", and E the set of "edges". When G = (V, E) is graph, and v E V, we write G(u, -) = { u E (v, u) E F. } the set of out-neighbours of o (also called children), and G(-.o) = [u V (u, v) }} the set of in in-ncighbours of v (also called parents). Definition C.2 (Homomorphism), Let G = (Vg, EG) and H (VH, E②) be graphs. A function p VG - VH a homomorphism of graphs if (u,v) E EG + (p(u), (p()) E Eu
EV,
We write homomorphisms &p G H. by extending naturally the function of vertices to function of edges y Fg + Eu, (u, v) + (yp(u,, :(t)).
It is immediate from the definition that the composition of homomorphisms is also homomorphism.
For our purposes, a directed graph G = (V, E) is acyclic if there exists a total order < on V such that (u, v) F u < This is equivalent to the definition of acyclicity as being "without cycles". Definition C.3 (Fibration). A fibration from graph G = E) to graph H is homomorphism p : + H such that for all u e V, the restriction pla((..) G(-,v) + H(-);((v) bijective.
In words, a fibration a homomorphism that also an isomorphism of in-neighbourhoods.
C.2 FIBRATIONS ARE CLOSED UNDER COMPOSITION
Proposition C.4. sp: G + H and db H + K are fibrations, then vo o G - K is fibration.
Proof. A fibration is a homomorphism that is an isomorphism of in-neighbourhoods. Therefore, since & o sp is a homomorphism by composition, suffices show that it is an isomorphism of in-neighbourhoods. Write G (Va, Ex), H = (VH, EH) and K = (Vx, Ex). Let Ux E Vxx and UG E Ve such that (1/ () Ug. Write TH (p(G) E Vg. By the fibration property of sb, there exists a bijection s: [H
with s = + [--"w)) By the fibration property of sp, there exists a bijection t G(- + H(-, uH) with = pla The composition s sot: G(-, vG) > K(-, ex) ) is a bijection as composition of bijections, remains to check that it coincides with (eb o (p), which is immediate since (s tu) =(t(u)) s(p(w)) = ((p(u)). O
14

---

D CONVERGENCE CRITERION DEPENDENCY ON PARAMETERS
Proposition D.1 (Convergence Criterion weakening).
Let No 1 and Eo I... Let Ki R+ and E1 12, be such that 81 Ko and E1 E0-
[c θ R Oo E @) satisfies Convergence Criterion with limit error &o and constant Ko, then (o) also satisfies Convergence Criterion with limit error en and constant Rt.
This is consistent with the intuition that in Convergence Criterion 1, the constant is form of "speed" (higher speed is more impressive) and a form of "error" (lower error is more impressive).
Proof of Proposition D.I. For any & IR,, let Se R4 R4 Ri
Ry be the function
S (K, k +
Let us show that S, is increasing with respect to e, decreasing with respect to and increasing with respect to Let Ex, E R Ri. Compute the following derivatives and observe their sign
0,S,(K, +1
0 S,K, 3
(t) (nt 1/c)
0
0,S,(k,
(nt + 1/c) 2
1/c)
1/3
20
Now to conclude, let (C, 0o) be a pair satisfying Convergence Criterion 1 with limit error Eo and
constant Kg- Let A R >> θ be such that 6(0) Ou and 0,0 -V Let co L(6)) 3 and t E IR.. By assumption, L(f:) I St (No. Cu, cu). By the study of variations above, (, Eo, co) s (,,,,, co) < (K1, E1, co). Thus for E R., holds L(0,) I S, co). which is the definition of Convergence Criterion with limit error and constant and concludes the proof. O
Bonus: Note that we have also shown increase of S, with respect to so in later proofs it is sufficient show C(O.) < S,(k,,, with an inequality c [(0g) rather than equality.
Definition D.2 (Extended Convergence Criterion). Let e E 4. The pair (L : θ + 1R, Go E +)
satisfies the extended Convergence Criterion with limit error and constant K +00 if for all
0: 12 + θ such that ((0) = 0g satisfying 0,0 = - it holds Vt E 1R,, L(0,) S.
is immediately observed by the previous proposition - and the fact that (K, E,C + s] when [N + +ool that this statement is equivalent to "Convergence Criterion is satisfied with constant too it is satisfied with all finite constants λ E R,," This also consistent with the intuition that the statement of a flow reaching loss with "speed" x be naturally extended statement with "infinite speed" if the flow just reaches loss instantly. Because of this consistency with the previous criterion, we do not in the following distinguish this extension from Convergence Criterion
15

---

E PROBABLE APPROXIMATE CORRECTNESS BY TANGENT APPROXIMATION
Lemma E.1 (Convergence criterion by integration of a separable hurdyka--.ojasiewicr inequality).
Let θ be a vector space, L: θ + 1 a differentiable function, and 0g E G. Let E ER_, R E R., C E R7. for all 0 E O such that |10 - Ooll S R, it holds [V 2 (C(() - - (10 Poll +oll+00 c), Then the pair (L, 0o) satifies Convergence Criterion 1 with limit error Eg = T (1-)))
RC
where T = e/ R + c) 20 1}, and with constant K = 3c (L((0) - =) E R2 U (+00).
for which the right hand side is strictly decreasing with respect K, we can naturally extend its definition to 6 = +oo if the convergence criterion is satisfied for all positive finite which is also equivalent to simply a bound of VI, ((,)) E0- Those are not the most interesting cases anyway, but this stresses the fact that this statement is well-defined in all edge cases. Note also that for fixed c, this statement has ED R-x00
Since Convergence Criterion uses a bound [(0)) I Eo +1///t++
E.
Proof. Let 0: + O be differentiable curve such that ((0) Oo and 0,0- -VC()) Note that ((0)) S & then the conclusion is immediate because [(06) S so and the loss is non-increasing since (C 0), vL2)) 0,0, -Il -II (0,) I| < 0. It remains to tackle only the other case, thus for the remainder of the proof. let us assume [(0)) > E, and in particular E S Ev. then define
T= inf (f E R,+ |10, 0o I R ) nit R, [(6,) > }}).
Radius upper-bound by separable KL integration. Define r : [0. Ti R_ as asr 1110bbull du. Observe that for all / < T, by triangle inequality it holds 110, 0oll S r(1). Therefore,
[V
0, o 0)2 [(6+) -
an ||0.0.1| | (00)) (S1) [V
(rr + c)
(S2) rite (C(),) - +) ($3)
where (S1) is valid because [[,(( > 0 by the initial assumption and restriction to [(0:)) > e,
and (S2) is the initial assumption again, and (S3) uses (c o f), -IVV2( and [(0,) > E.
This corresponds to the inequality 0z( L r) S a. o L cow 0) where Li : + log(s + c) and : s + loggss - =). Integrating the incquality between 0 and T yields the inequality
r: c [oog(r + I.. $ II
log (C(0w) - o)] log ((0)) 6
log 0++
C(6.) E
Thus after taking exponentials on both sides,
C(0n) rt t [(O:)
(1)
Radius bound injection and reintegration. Define the e-discounted loss L O + R+ as L - (L(O) - -e Injecting the radius bound inequality (1) into the initial assumption
< (O))
(C.())))*
a, o 0),, (S1)
a.(Co f), - (1
(52)
(rx + c)²
(S3)
(c (0)))
where (S1) is because for all t < T, it holds C(0,) = L (0)) + E by definition of T, (S2) is the initial assumption coupled with ri 2 ||0, Poll, and (S3) is the injection of the radius bound inequality.
Therefore, let 3/ (c (0o)) Ei. and E u ++ 1u+-1/u² -1/1², We have shown the inequality
0 ( L o 0), +3 +3 9,(C' o0),
-
(C)))
Integrating between 0 and t < T, this yields (0,) + (80)) -3 -kt, thus after inverting E. L (0,) < (B6) -3 + ki)) -1/3
Vt < T,
(2)
Conclusion. We are now ready to conclude by case disjunction. If +0c, Eq (2) immediately implies Convergence Criterion 1. T < +oc, there are two cases to tackle. First, if [(Or) s e, then the bound of Eq (2) holds for ł < T' and is extended to all > T by the non-increasing property [(O,) < ((T)) < ε < Eo, which concludes. Lastly, if ||0 - 0oll = Rt then by inequality (1) we get [(Or) - E Rtc
e (C(O)) -E). E). Therefore [(Or) S T [(bb) + (1 -)- = Eu where 7 c/ (R+c). We conclude this case again by non-increasing extension, which completes the proof.
16

---

Theorem E.2 (Quantitative version of Theorem 2.1). Let (e, E E 10.
If there exists C 10.1] + R+ such that for any s E So and for any E 10. 1] is holds Pl..9mNN [ o F((.,) S C( 2 1,6, and if there exists constants &g < and do such that Condition CI is satisfied with parameters (E), then let E R be the corresponding intercept, let $1 E S be the threshold size associated by Condition CI to radius R = cC(( - óu) - EE)/(E -o)) and let K =3c= -(6-6)) 600-2223 R.
It holds for all E So satisfying = 81, that if (g, 0o) ~ No, then the pair (L ((e.g): On) satisfies Convergence Criterion with limit error and constant K. with probability at least (1 8).
Note that Theorem 2.1 is a direct consequence of Theorem E.2, it thus suffices to prove the latter.
Proof of Theorem E.2. Let 8 So such that 81. Let (g. 0g) N₁.. Let A be the event:
VVr < R. ((0,, r) C Asglc c + r.)o]] By Condition CI. ((A) 2 (1 - 60). Let B be the event: [C F(s.g) (0o) S C(ò 60)]. By boundedness assumption, P(B) 2 1- (8 6o).
Therefore, by union bound, IPAn B) 2 1 P(-A) P(-B) 2 8. Let S be the event
[(C Fis.g): 0b) satisfies Convergence Criterion with limit error e and constant sj. It only remain to show that S S An B, since that will imply P(S)= 2 P(An n B) 2 11 6.
We will do by leveraging Lemma E. Write for shortness C = C(o 50). Let (g,00) E G. O be such that Vr I R, ((0, r) S As.g(c + r. Eo), and L o (()) I C (i.e. both events A and are realised). Let E B(0g Rt), and let us show that the separable Kurdyka--Lojasiewiic bound [ F(s.g))())) 0 E (.,(cctr, let E O, be such that ||u]| S c-tr and || ((s.)) (..
(Co ((.g)) (0)
=o)+/(1le
Poll + c) holds. Letr = ||0 doll. Since
(0) f' < Eo- First, note that if Lo ((s.g) (0) S then the bound holds immediately since the right-hand side is null, thus we can assume in the following that L F(e.g) (0) > En- By the variational form of the 22-nomm
(d(C F(s, 9) (0) - v)² (-d(fo o F(s,g))( w)²
[V o (0)))) = sup vEE,
(3)
|0
|
Then since [(f) = 115 13. we can expand the derivative to
- -d(L o (()) u = - (d(F(s..)) (s.g) (0)) (dF( u)
= 2 dF (s.g) (0) u, F( gs (0) f)
f³)
Lo ((..g) (0) dP (.,)) (0) .ul uIB || (0) + dF(es)) (0) u --
1- 1m
(S1)
Lo ((sm))() - 0-Eo
where (S1) the parallelogram indentity 2(a b) = ||a|| + |b| |a + b11 with the definition of
f. and (S2) is the approximation inequality defining u. Using the positive part (+)+ + max (0, s).
we can thus bound the square of this quantity irrespectively of its sign, as follows
(-a (0) w)² (C F(s.a) (0) e0)
Observing that ||u||| S c r and injecting both of these bounds into Eq (3) concludes the proof of the bound.
separable
Applying now Lemma 1. this implies that the pair (L F(r.g), 0o) satisfies Convergence Criterion I with limit error E = r o F((..g) (Bo) + (1 -)- -) Eo for T = c/(R + c) and constant K1 = -2 (Lo o P(o.g) (0o) - =n)²- By decrease with respect to k and increase with respect to e of the Convergence Criterion bound, it now only remains to show that E S e and K 2 K. The latter is immediate because (C F(v.g) (0o) 5o) < Lo Flgg)) (0o) S C, thus Ki 2 3c -0- K. Then, use the fact that = c/c = (E -n) (C (C- to get S C++
rCC-
E. Li
Thus the pair (L o F(s.e): 6b) satisfies Convergence Criterion I with limit error and constant which completes the proof that S C A B and thus concludes the proof of Theorem E.2.
17

---

F MORPHISMS OF LIFTED PERCEPTRON MODULES TO TRACK ACTIVATIONS
Definition F.1 (Morphism of lifted perceptrons). Let (G, TG. cG) E LiftPMod(B..) C) and (H, Rn, en) E Lidt C). A morphism of lifted perceptrons p (G, (G,TG, cG) - [H,TH,C)) a fibration yp : G such that TG ни o yp and eg = en o..
In other words, a morphism of lifted perceptrons G to H is a correspondance yp between the underlying graphs G and H that preserves the activation-definigg "types" of vertices and edges, and the input connections c, i.c such that the following three diagrams commute
y
VG
VH
EG
EH
lG cG
TH
TH
CH
VB
EB
In the example of Figure 4 and Figure of multi-layer perceptron with three layers, the base graph has VB = {0. 1, 3), and a lifted vertex e E has ((v) = VB if the vertex v is located in layer k. The condition that preserves means that vertex of layer k in G must be mapped to a vertex layer & in H. Mapping across layers would not make much sense, because would not be compatible with the definition of the forward function. Similarly for this example, we have = {r,g. g. b) indicating which of the lifted inputs corresponds to each channel. The mapping must also preserve these connections (map the channel of G to the channel of H, etc.).
Proposition F.2 (LiftPMod MoouPMooo-oopismss preserve activations). Let G E LiodPMod(B, C) and H E LiftPMod (B, C). If G - H is a LiftPMod C)) then for all WG E Param G) and wH E Param(H)) (H), it holds
WG = 40 wH
+ F[G] (wa, = x- o F[H]] (WH,-)
Thus one can transform the graph and weights, then compute the forward, or compute the forward first, then transform the activations and input connections. This property of compatibility of the forward operator and the morphisms of Lift PMod corresponds to the following commutative diagram
(G, wG)
(H, WH)
FII.
FF((-)
for
F[G] (wa,
H (wH.
The proof of this proposition is deferred to Appendix F.1. Intuitively, this proposition states that fibration of graphs compatible with the lift and preserving the weights means that the lifted perceptron modules "compute the same thing". Fibrations are crucial for this property to hold, a homomorphism of graphs for &o would not suffice, thus the restriction to fibrations in the previous definition.
F.1 PROOF THAT MORPHISMS PRESERVE ACTIVATIONS
Proof of Proposition F2. Let G (G, ag. E [if. and H (H, (H, LiftPMod(BB C). Let yp G + H be a fibration such that (To = TH o P) Ve - VB and (cg cH oxp) : (G) + C. Let we E Param(G) G) and wH Param(H), be such that we = 4 wH. Let us show that F[G](wa,)))
8 [[H ) IIee Vpe(a) + llleve Vzo(m)-
Let us check first that these expressions all well defined. As a function of sets o0 Ve + V induces a pullback s² IIwev (r + IIvEVIC) ((()) = II (w) Therefore, the expression yp* F[H](WH, -) is well-defined and has the correct type signature. Similarly for the weights, WH E (aram(H)) = IL Wax(e)- As a function of sets, & Eg - Eµ defines a pullback o-* : IIegE Wry(e) HeeeE W Wxy(pte)) = HL Wia(()) = (aram where the first equality follows from ne मH e ip. Therefore the assumption wG yo wow way is well-formed.
18

---

Let II D pu))- We will proceed by induction topological ordering over Va (available since G is acyclic). Let _ Va be the set of vertices such that
v veUk + [ =)), + ( (wH) r)
Let show that U Ø. By contradiction, if U is not empty, then let v E U be minimal for the total order x. Proceed by case disjunction on (Ta, Va \ TG). For the first case, u e enl. then (P)) Tu. Therefore by definition of the activation map, get the contradiction
[F[G x) (51) |c6=0, (82)
Fea(e)
[c)( (S3)
[[ (84)
[9 (( (85)
where (S1) is the definition of the activation map of lifts (Definition 3.5 and Definition 3.4) for e E Ig. (S2) is the definition of the pullback <g. (S3) follows from cG = cи o s,, (S4) is the same argument (S1) for p(v) Ir, and (S5) the definition of p", which concludes this first case.
For the second case, assume v E U n (Va \ IG). Write for shortness g = F[G] (wa, x) and = F[H r.). The fact that E U implies that Je * he(t)) but the assumption that is minimal in implies that for all u E VG. u < v, then Iu = hp(a)) (otherwise u E U by definition, and thus is not minimal). Writing Ga(-. = - (a) G(-,v) for shortness (resp. Ha(-, "H (a) (-,,))) t)), by definition of activation maps (Def. 3.4) and lift (Def. 3.5),
9r xxa(v) ((E
Σ MEG.(-.N)
Maa(a,e) (werleee))
aEB(-(ao(r))
Now, by definition, : G H being fibration implies that (lla(-.)) -)- H ((()) is a bijection (Definition C.3). Moreover, the fact that Te = R o implies that for all a E B. the restriction of yo also a bijection (- + Ha(- Ha(=,p(v)), Therefore, can replace the terms in the sum one-by-one (note that this is not possible with homomorphism, we need fibration to do this), as follows. Write & -la(-..) the bijection, and rewrite the previous equality
Mac(un) (Iwcl(u.): gu) (-,G)(-,0)
Σ
Jo = Omalv)
(S1)
aEB(-rrc(o))
Mxo(v-1(u).)) (Iuc)u- 9x-1())
Oaa(v)
(S2)
(EHHll-p(vo)
aEB(-rrc(o))
M (anlo(e-(w)ho)) (woc)o- Io- wEHa(-vp(r))
Σ
(S3) anl(o()))
aEB(- cEB(-<xn(((())
Man(u.p(v)) (wxllosto))))))) (EB(-au(((e)))
(nx(p(v))
(84)
(EH)(-vp())
hi((w) (85)
where (S1) is by definition of (S2) is the rewriting of terms reindexed by the bijection, (S3) uses
Tc πH o y, (S4) the assumption that 26 (w)) U by minimality of and cp( ( (u)) a.
applied to -v- (w) (p((s)-(()) h, and rewriting of wa w""H. Finally (S5) is the definition of h, constitutes the contradiction for the second case, thus concludes the induction and the proof. Li
19

---

G TRACKING ACTIVATIONS ACROSS DEFORMATIONS OF WEIGHTS
Definition G.1 (Quantitative continuity). Let G = (Va. EG) be a graph. Let G ((1,T), (V, W, Z), (M,o)) PM)d(G) and w Param(G). Let X S IIlEr Vo.
For any VG. write F, = = o Write g F[G](w",)) such that for E 2 and E VG, we have g.(x)) [F[G][w), .x)] Ve.
[uEaa(-.) W(n,)) Vuu + V.p
For any 1) E IK4 and X, define Lnn Va + R4 inductively as followsfrum [L) x]]p for b E I and propagated to v E Vo
[],,,))),
FF g) Fo gx)())]]
Then write L[G, (n, x) supzex max.eva (n, x))., If X is compact, this constant is finite. sup well.ea(-w) W(,e)
sup sEllucat- 3 ( Vu.llsu-9. [e)
This notion will be used in conjunction with Proposition F.2, which is the reason this convoluted definition is chosen instead of just suupeex sup/j [/
Sg 10 [[]] .) [[G] .2)]lo which is much more simply stated. The construction of Definition G. is such that the constant L is preserved by morphisms, thus we start with two networks with similar weights and morphism between them, can track the evolution of all activations with single constant.
Proposition G.2 (Tracking activations through morphisms and across weight deformations). Let = (G, c) E (idd C) and wg E Param (G) for underlying gruph G (Va, Fa). Let H E LiftPMod(B, C) and wG E Param(H). Let X S Iluec Vnc(w)
Let 1) E R... Assume & G + H is a (ift -)-morhhism such that
Ve E Eg, |[wale - (1p"w n
Then for any E VG it holds supzex [[G][ +),, [[[ ))ما(>> S LIM, wH|(n, X))
Proof of Proposition G.2. To avoid confusions, write the lifted modules G = (G, TG. ca) and H (H, πH, cH). for the underlying graphs G = (Vg, Eg) and (VH, E.). For uy VH, we use the notation [L(7, associated to vertices Vи by Definition G.1 in the construction of L[H, wH](n, (n, X). Let X. For shortness, define F[G] x) and h F[H)( Let us show by induction on v E Va that llg. hp(o))l S [L(,,=)]
To that end, let v E Va be the minimal vertex satisfying l19. how > [[(,, x))p()> for a topological ordering G. If ma(v)= E Ip, then by definition of a lift and forward (resp. Def. 3.5 and Def. 3.4) it holds J. Fea(n) (e)r(((n)) ha(v) which constitutes the contradiction. For the remaining case of Va (LB). let s -la(-.") be the bijection between parents : G(-,u) H(-,{((v) (existence and bijectvity follow from the fact that yo is fibration). Thus,
Iv TT)(o) (( (MMrolunn) (Iwolwoy) )EEC(N))
-amn(p(e) ((Manteroton) (wwolw- 90 sEH(-1((0))
However by assumption we have [1[wala-((0), - (wwle,p(e)) S 7, and by minimality of it holds ((s)
llg (lg)-((s) - h.ll < (L, 2),,- thus by definition of [L =)]p[() as the supremum over such values,
we get l1g. - hp((n)] <
which consitutes the contradiction and concludes the induction. Finally, observing that [L, x)) pp()) I L(H, wH]( 2) concludes the proof.
20

---

(S.4) G - H is said to H FROM A COVERING PARTIAL MORPHISM TO TANGENT APPROXIMATION
H.1 PARTIAL MORPHISMS, A STRONG MEANING OF "SUB-NETWORK"
Definition H.1 (Partial fibration). A partial fibration (S, G H is subgraph S of G such that the inclusion map : S + G is a fibration, together with a fibration : S H.
subgraph of G such that the inclusion :: S G a fibration will lead to an "extraction" of perceptron module from larger module, compatible with forward functions.
Definition H.2 (Partial morphisms of Lift.Modd.
Let (G, TC, cc) E Lift C) and (H, TH,CH) (Lf C). A partial morphism of (ld C) is partial fibration of graphs (S, : G - H. such that the inclusion :: S + G induces a LiftPMod(BB. -)-morphism :: (Gls cals) + (G, TG. cG). and the fibration & : 5 + H induces [Bf -)-morhhism p (S, Tal.. cals) + (H, TH cH).
Definition H.3 (Covering partial matchings).
Let G = (G, aa, ca) LiftPMod(BB. C) and we E (G)ammG).. Let = (H, TH cH) E (B., and WH E (H), over graph H = (VH, EH).
Let VH [0, 1] and n E Rt. A partial (B.PPMoo(B,C))orrrryee be an (o,, covering if it satsfies the following conditions:
Ve E E(S); Ye VH.
|[ wol. - (ep'wllell n
#ip 2 avv) # (TT()))
We write MR[(G, wa), (H, wx)) the set of such partial morphisms from G to H. Additionally, say that (G, wG) has (a, -)-over of (H, wH) if the set of such partial morphisms is not empty.
H.2 TANGENT APPROXIMATION BY CUBNETWORK-MATCHIE
Let us show that the tangent approximation property at a point can be reduced to a covering property. Proposition H.4.
Let G E LiftPMMo (BB C), and let 6, (w",, .a") E Param G) x LinReadout(G, k)). Define the shorthands θ- Param(G) x LinReadout(G, k) and F θ (X - RR) the forward function
F: (w. a) + F[G](w,-) -), with norm I1( a) a)l@ = Exero ||wel| + DEeM),erTc (l |0..0
Let G* = . c.) E LiftPMod(BB... C) and (w* aa)) E Param(G')) x LinReadout(G* ,k) over G+ (V=, Le E Rt, and V + +00, 1]. If (G, w0) has (a, -ovee of (G*, w²), then
inf [[F())) + dF((6) Il ||at F[G*)(10*,) l + + [[G",, w (n; wcB SK
with C* -=======- -iEMM Evev. V# (w))
|| and x ||a"|| + y Eieth) Evev a(v) (x))
|| II
Since L[G*, (1)(),)))))))))))))))))))))))(
= n-6 O, this bound tends to ||a F[G*](w*,,) f in the limit 1 0.
This should be fairly straightforwardly connected the tangent approximation property at 0g. Indeed if [|F[G]]("" error 1 provided 7) taken sufficiently small. The tangent radius x also has manageable form.
1I, < then this property will constitute tangent approximation at 6g with any
Note that this is consistent with the intuition given by Frankle & Carbin (2019): the Lottery Ticket Hypothesis postulates that if a large enough network contains smaller network which achieves low loss (a Lottery Ticket), then the larger network will achieve low loss. The principal distinction with the present discussion - apart from the added generality of generic perceptron modules instead of just multi-layer perceptrons is that Frankle & Carbin (2019) considered dense networks whose "stbonetworks" were extracted by homomorphism, whereas our proof is restricted to extractions by fibration, which is much more restrictive. The overarching intuition carries over even if the details don't 't match, largely because these early postulates were intentionally fuzzy in nature to guide intuition, whereas proofs rigid by design in order yield precise empirical predictions.
21

---

Proof of Proposition H.4. Note first that the function F (w, + a. (wG -) is linear with respect to a, therefore for any b E LinReadout(G. k), it holds dF(w,, a) (0, = b....F.ee Fu, -). Then, from (S. ()) G - G* partial fibration with (a. 11) cover, construct E LinReadout(G,k)
defined for V E (()) by u, = / 80, where 8, = # - (f(1)) # (())
[IF((" + dF(we, aa) (0. u d f IDD
(81) |ldF(w": (a)) (0, - 1 ||u F[G](w"; -) - 1 (S3)
(52)
(4)
+ FFGG[ a² [F(
where (S1) is the fact that for any a, we have F(w", a) a FIG](uP,-) dF(w a²) (0, a). together with linearity of the differential, (S2) is the simplification of the differential, and (S3) is subadditivity of the semi-norm |/-l on the space (X' + R²²) (see Proposition K.2). Let us show that this is valid upper-bound for the infimum in the claim, because [| u al)lle S K. Indeed, by subadditivity of the norm [|(0, u al)lle I [100, u)lle + [I(0,a")]le = ||u]| + ||a%], Moreover,
||]|²
Σ
Σ
||,,,|| = Σ Σ
Σ
1/,,1///5
vE[k] (ET(G)
TE[k] (GT DEP 1(x)
|| 1|2 #T (TT (u)
Σ
Σ
(e[k] WET(G*) (EP-1()) #1- (x(())2 # (T. (u))
|at| #T
|a!|
Σ Σ
Σ
[E[k] (G) #6 (u) # (T., (w)) (S1) iE[K] uET(G*) alu) #t, ( (u))
where (S1) is the covering property ensuring that (p 2 Cip(o) # (T))). Now to bound the second term in Eq. (4), let us show a more convenient rewriting of u (FF x)). Write for shortness for any u E T(G*) ) the average Fu(x) Ever- (u) F[G](w", //,/ # (u).
u [w x)
(un F[G[(w", ()))
(S1)
BETB V
#
(b)
(E(M]
Σ Σ Σ
1
(a FIG
(S2)
DET uēM, ((b) VEP l(u) V HT, (b)
#Ø
[Е[K]
(ai Fa(x))
(83)
TE uER, (b) V # (b)
KE[A]
where (S1) is by defintion of the action, (S2) by definition of uh. and (S3) by linearity. Next, by
Proposition G.2 and subadditivity, we have (x) (("" S LIG w" w7, 2²). Thus,
(at Fa (ww,)(
|| (u=FFG](w", -) -a- FF[G"[("" -) E.,
Σ (E(M)
Σ
beT' uE (b)
W#T (b)
| ll ||F - F (w ,x)]
Σ
< (S1)
E
v |## (b)
iE(M)
BE'In WER, (b)
|
< EE
G w w''((n X)
Σ Σ
RETA]
bETn weR. (b)
# ... (b)
where (S1) is the Cauchy-Schwarz incquality in (T) Thus taking square roots and using the inequality I|-1l2 & I|-IIr, we get |u- (w - at F[ l)lpp S C+ LIG w (1) x).
Reinjecting this inequality into the first bound Eq. (4) concludes the proof.
22

---

I COVERAGE OF RANDOM SPARSE LIFTS
Definition I.1 (a parameter of a perceptron module).
Let GO (G", NT, C.) E Liot C) and w" E Param(G"), with graph G* (V*, EE).
Let : EB > 7. For e E Eg, let No be a full support distribution on We. Let E RT
Define Ozy : :V* > Jo, 1), inductively over u E V",ffrom Oxp (u) = 1/## (=(()) (=( for E T(G"), and propagated, with the notation K.- 21+ 33+#B(-aa.0)) #T, (x. (v)), as follows to V ((+))
1 an(v) Kr (EB(-.3.(0)
II
P (Kia(v); Maxi(()))
II
(w (w(n.)))) an(u)
(x,(u,) (EG
where ka(v)= = # (G*(,,)) (a)) N is the number of "type-a" parents of vertex v in G", P(k; A> is the Poisson density, and for EB, we write Pe We x IR + E the T)
volume of ball as measured by No, i.e. (s, + PoNN. ([lw-slip -
Validity of this definition (e.g. image of the function a) is detailled in Appendix K.2. The form of at vertex (forgetting K,) is intuitively the probability of guessing the correct degree, then the probability that for each parent, both the weight and the corresponding subnetwork match the witness.
Based on the results of Appendix E, we know that it is sufficient for convergence to show tangent approximation on large ball around initialization. For a given lift and choice of parameters, we now know from Appendix H.2 that it is sufficient to show existence of witness extraction (a partial morphism such that weights approximatively match) on that ball. Let us start by showing that at the initial point, there exists witness extraction with high probability, we will extend this to balls later.
Proposition 1.2 (Large random sparse lifts are covering with high probability). Let A: EB + 1R. For EB, let No be a distribution on We with full support.
Let G = (G", C.) E LMod C)) and w" E Param (*)) over graph G== =V* Let 1) E F_. Define an : V* + Jo, 1] the a-parameter associated (G*, w²) by Definition 1.1
Let VB + N such that if LB then n& (b)) Let (G, w) be a random sparse lift of BB /la.s// (aa. log(2)), then along (n, X) with distribution N. for all (a, b) En, na 2 max(X(a,))
[(U)² ub . a(())) 4
P PM (MG (G, (G*, x0*))) 2
II
Σ
exp
dEVaiIs
VET, (b)
where 7 V + 10.10 (1 (((e)
which tends when (nn,(w)a(U)) + to0.
We will write G=(-,v) G* (z. in this proof. Similarly for the graph G. we write Go(-, v) G(-, u) nx n (a) for V.
(a) with a E VB in index because this will appear often
For any vertex VB, define the set Ag = {u E Va, u 3 f} (of "ancestors" of v). Define the filtration (Fo)ev,, induced by the strict total order on VB as the -llgebaa
=
U
U eEEc (())=(a.y)
{me we}
(a.))R y-tb
Conditioning on the o-algebra F, will "freeze" the random variables corresponding to the subset V (()) E As \ {b}), and allow the study in isolation of what happens when adding E Va.
Proof of Proposition 1.2. We will proceed by induction on VB. the vertices of the base graph, using strict total topological order on VB (i.e. such that (u, Eg + u < v), available by acyclicity.
We use the notations from Definition 4.2 of random sparse lifts, with the bernoulli random variables m(a))) (()x(u.n)/Pee (Rr()) and weights (w..)) N w for all (u, v) E Ec, where (Vo, Ec) the fully-connected lift of B along (Definition 3.6) define the random sparse lift (G, w.a).
23

---

Induction hypothesis morphism (S, () : G G such that Vs - π (U), and the following two conditions hold:
For any subset U S VB, define M(U) the set of LB
Ve E E(S), ||w. w (e Wl Sn
E E प,. (U),
(w) 2 a(u) # (II(())
The first condition is identical to the definition of covering matchings, the second is quantified differently (on n.. " (U) not V*), but coincides with the definition when U = VB-
By contradiction, if the claimed inequality does not hold, then let b E VB be the minimal vertex (for the topological order) such that the following inequality holds
(- (-(()²² ali)) (-44 4 no ma-a(i)))
IP (M)()) #0) < II
1 -
Σ
exp
(5)
aEAs\
VER, (a)
Let us show a contradiction (thus that there is no vertex such that this condition holds, thus the inverse inequality holds for any b and in particular it holds for M(VB) B) which matches the claim exactly).
Induction intialization. Let us proceed by case disjunction. If b E LB first, then let us show a contradiction. First, to tackle the edge case, note that M(Ø) * 2 almost surely because it contains (S,4) a partial morphism with the empty graph (no vertices and no edges). Then, let us show that P(M(As) A Ø) 2 P(M(As) \ {b)) + Ø) by the almost-sure extension that follows. Recall for that matter that the function pe C - a partitions C into subsets PC (w) C C indexed by E L Moreover, by construction of random sparse lift, for any E LB. we have π 7 Pc (u). Thus, if (S, p)) M(As \ {b}) for graph S (Vs, Es), construct the extension ((Vs" + (VV**.Es). Vs* = Vs C. (m, (b)) with l'vv io and for E Vs Vs, let y
as (c) c, (v) E n. (b).
This construction is well-defined by injectivity of c, : (I + C. It is also immediately verified that 4 is a fibration because elements of Vs*t \ Vss have no parents (more formally, = G(-,0) = 2). The homomorphism Ts Vs+ - >VB is obtained by restriction TTş n xly Additionally, for every u u, (u), we have #(p+)-l(m) 1 a(u) ##, (x.()) a(u) #T (I, (u)) by definition of a. Thus ((Vs + Es), E
v E Vs* Vs + TTv)=
This concludes the proof that P(M((A, Ap) + Ø) 2 (PM((A, {b}) * Ø). Let us now show why this contradicts the definition of b. If Ao (b) Ø, then the inequality Eq. (5) contradicts
P(M(2)= & Ø) = 1. If on the other hand there is E Ag such that a < b. then a must also satisfy the condition Eq. (5), which contradicts minimality of b. This concludes the case b Ig.
Induction propagation by morphism extension. The case b In has been tackled. Therefore let us assume for the remainder of the proof that b E Vn \ In. The idea is roughly the same as for the previous case, we will work conditionally on Fú and show that we can extend partial morphisms from M(A, \ {b}) to M(As) with a high-enough probability, and use it to form a contradiction.
Intuitively, if (S, sp) M(Asss \ {b}), we want to construct for every E (b) set (x() S - (6) such that j E E, (cp) if we can extend o into partial fibration by mapping j to i, and if this extension continues satisfy both the type conditions and the
condition. We do by considering parents one at a time, then take intersections, and finally show that Ey(p)) is sufficiently large with sufficiently high probability.
Extension (a): single-parent compatibility. For every (5,g) E MMAA \ (b)) a partial morphism with S (Vs, Es), and every a E B3-, let (P)) C (b) be the subset of V defined as
Ga(-,j) Cvs ((Ga(- = G)(-;t)
E (g) e
Vu G.(-. [[ w (.)))) S
With the previous notation of P(k; = ^>x*/At and De (e n) P PunNe - will $ n), define
1
Mso0 = P (+G A(a
P(ab) (w(u.):)) a(u) uEG
II
2
24

---

Observe that this definition is chosen such that a(i) = (ThEB(-M) / ( (i)).
Let us show that (j (P)) M(A (o)). 2 M4,a. For shortness in the writing of this proof, let (- E N and ((.b)) Aaai/// [0. 1]. For subset I C (a) E Va such that #I = k; write ( the set of bijections from to Ga(-,i). Now, observe that by disjunction over such subsets and average over (()). it holds
11 (E) 2
Σ I=-c.(-))
1 #Z(1) (EZ(1)
Σ
1el== II
1 (I ("P (200),)
15 (a)
#S=k
By independence and linearity, we can take the conditional expectation
E
(1 (5, E M(Ab \ [b]),
Σ
Licvs Las (1 {(a))))
-
Σ (EZ(1)
I
+/r= II
Plan) (uic(a).)))1 WET
(S1)
kd
IC (a)
#I=k
2
k Ka,b) (1 ((a.)))
ki
Σ
LIvs
Σ
1 1 Il
P(a.0) (w(s()).))))
($2)
k!
I (a)
(EZ(I)
wEI
# #l=k
* (a,b)
>
1
)( 1
Σ
1
Σ
p II
P(a.)) (wis(N).)))) wEl
(S3)
k!
ICa (()
(EZ(1)
HT
(a.b) A(am)
II (=,)(-.()
P(ay)) (w(n.)))1))
Σ (a)
1igvs Σ
(94) 2 k!
no
(EZ(1)
#I=K
(a.b)
A(a.b)
II P(a,b) (w(asii) aalu) (EG
(85)
k!
Mi.o
where (S1) is linearity of the expectation and independence of m and w. (S2) is a factorization of constants related to m, (S3) is the lower-bound of Proposition L.1 because by assumption n, 2 max(2A(a.b) 2X 2,, log(2)), (S4) is factorization of constants related to w, and (S5) is the
following counting trick:
n L
Σ (0)
Σ (EZ(T)
Σ
1
E
n (S1) Ya, VoK)EE 1(x)
#1
(w))
(S2) n
NEG
II
(a(u) n.a
(S3) n (-G)(-())
II a(u)
GEG)(-.))
where (S1) is lower-bound by exhibition of a subset of terms satisfying the indicator conditions,
(S2) is the counting of such terms, and (S3) is the hypothesis (S,4) E M (Ab) \ (b)) with the a-cover property applied to B)- C (A, (b)).
This concludes the proof of the inequality E (e) (S, M(Ab) \ (b)), Pi,a-
25

---

Extension (b): multi-parent compatibility. Define now E((p) NaE ((EB(- Ex (4)). By condi-
tional independence given Fi of the events (j (P)) indexed by a E B b), we getet
E E (1) ( MM [6)
(8, = EA ( 1 (e) (
II
II E [ (E)E))())))
(S E EM(, (5))
ag Bi ((-b)
Pi.a
aEB(-.b)
Write for shortness 14 -o.een-n- n(-.)) Mi,a recall that a<l)) h (b), and equipped with the inequality E (1)E (S) E (As (6)), 2 p4s let us show that Ex()) is large enough.
Extension (c): probability amplification. The events (j E (x(()); indexed by j E (b) are independent conditionally on Fo. Thus the random variables Xj = (E)((())))) for j E π (b) have Bernoulli distribution and conditional expectation
P (S,)) E M(A (b)). 2 14 >
Let 6 (i) E [0, 1). Since #Fi(+)= = E, X,, we get by amplification (Appendix-Lemmp) L..4) (#)E(()) & (1 - 6,) Hi no (S, E M(Ab \ (b)),
-1)2
exp
- 07 nb p4 = exp (-8 8
71b
(1)) aii)
S cxp
4
We can then get a sower-bound on the probability that all candidate preimage sets Ex(p)) are suffi- ciently large, by union bound (since their cardinals are independent)
E
1 (+E.())(1-66)mm)))
E Fb)
LiE
(b)
21
Σ
(8,xp) E EM(Ad [b}).
iE (b)
r())²
21
Σ
exp
14 a(i)
iE (b)
We will use positive parts (+) in the following handle nicely the case where this is strictly negative.
Extension (d): tackling overlap. Let start by showing that for any partial morphism (S, sp).
LM 2 ((SA)))M(A
II iEx,
(=E.())2(1-6)mmm
(6)
If (S, 1)) E M(A, \ (b}) and if for every i E (b) it holds #E,(g) > (1 8,)p then let
us construct an extension (St +) E M(A)). The difficulty is that the sets (E,(p)); may not be disjoint, thus we must select disjoint subsets of sufficient size to satisfy the covering condition. Choose for every E ... (b) a subset V C Ex((p) such that (Vi); are disjoint, and #V; 2 m//4// # (b).
Proof that such choice is possible is given in Proposition L.6, since if nza(i) 2 1, for = # (b).
# (xp(s)) P
76/4
1
Dbf44
7b/4
2 (1 5.)
nba(1)
P
2
2n,as
P
2P
And if mia(1) 1, then Eq. (5) is immediately contradicted because the right-hand side is zero
26

---

Then, let Vg* V.V, be the extended vertex set and Es UseVs+ Uu (u.v) v) the corresponding edges. Define (VVsUVs Es U Es ) o7) the morphism obtained as lv = and for v E Vi - Vs* * as o (u) = i. By construction of (Vi)., this morphism is a fibration of graphs. Since for all (b).
have #(++)- #V; 2noju/#m ((b) nn mn)) thus the covering condition is satisfied, and therefore ((Vs UVs UsSEES Eu ))pt) E M(As). which conclues the proof of Eq. (6).
Towering.
We can now proceed by using the property that 1 = sup(s ((.)))MM(A)
E [MMAAA [
Fol 2 E
sup 1 (S.))EM((AMM0))) (8.+)
II
Fb
iET," (b)
2 sup E ((SPEEM(AMM)) (S.9)
Fb
RE (b)
= sup (( E (S.²)
II
1 -1
Fb.
LiEn, (8)
r(1)
2 sup (SA)EM())))) (8.4)
1 -
Σ
exp
ne a(i)
4
VET, (b)
T(i)2
2 IM(AN(1))
Σ exp
7bb a(ii)
NE (bb)
Finally, we can conclude by a towering argument
E [IM(AA))F]]
= E
E
[M(A)) Ful]
a(i)) )
(- T()2
2 E
1
Σ
exp
(-4
1MM(A\(6))
4
iER (b)
Σ
T(i)2
Bh a(i)) a(1))
E [[MMAOODD
exp
iεn,
(b)
Σ
Ti)2
na a(i))
exp
4
iEnT (a)
where (S1) is the reverse of inequality Eq. (5) for any VB with < b by minimality of b. This contradicts the inequality Eq. (5) defining b, thus concludes the case E VB \ Ig and the induction. which concludes the proof.
27

---

1.1 BALLWISE RESISTANCE COVERINGS WITH LOW OUT- DEGREE
Recall that we write n² In + N the function n. b - # (b). Proposition I.3.
Let x En + IR. For E En, let No be distribution on We with full support.
C) and w² E Param((")) ), over graph G (V*, E*). Let 1) E R_. Define On V + jo, 1] the a-purameter associated to (G', w²) and 1) by Def. 1.1.
Let G (G,, E Lifi Mood
Let n VB - N such that if b E la then nu = n.. Let (G, w²) be a random sparse lift of B along (n, with distribution N.
Assume that for all (a. EB, if Lg then Ma.b) I min(n (ng /2, (r2/3) and that
V LB, no 28 (R + n)² (1 + A)
q env an/2
where A E(abjEEn (7 (aaM + 1 + log(2) + lo + #EB) log 6)
Then,
[(G, M P(Vw E Blw,, R), Mi ///
(G', w²)) * Ø 1
The proof is deferred to Appendix 1.1.2. Together with Proposition H.4, it should be straightforward to see how this proposition will be used prove the tangent approximation property on an R-ball.
1.1.1 DECOMPOSITION OF BALLWISE COVER VIA LOW-DEGREE PROPERTIES
Lemma 1.4 (Resistance of cover in low out-de graphs). Let R2 and R E R...
Let G = (G", c.) E Lin (Mod (B, C) and w E Param((*) over graph G = (V*,E*).
Let a: V* +10,1] 1] and ler G (G, π. c) e Lift C) and w E Param(G).
Write n VB + N and d : EB + N (vertex count and maximal out-degree of G) defined as
n: n:b E VB + # (b) and d (a, E EB + vEa (a)
sup # (G(r, -)x
Assume that V(a, b) En. my 2 log Tha and that there is a conslant A E suchh such that
2R (1 (1+A)#V2
sup bEVB BE
Σ
d(a,b) na
< A
and
inf bEV
1/2 infrev Oo
Then for every w E Param(() such that || -00lwo1 w0ll
< R it holds
My [[G, w.), (G*, w³]] 2
Ma [GG, w)) (G", w=)) # Ø
Proof of Lemma 1.4. Under the assumption that this is non-empty, choose a partial morphism (S, ()) E M [(G, (G*, w*)] and let us construct an an element of Mar [[G, w), (G*, w=)].
Write 5 = (Vs, Es). We will show that we can extract a subgraph U = (Vu, Fu)) of S such that the inclusion to U + S fibration, and the restriction of yp to U preserves weights (up 27)).
We proceed by induction on b E VB, by defining Us nr Vs
as follows:
Ub
v E ग - Vb) G(-,v) U Un sup aEV
Iml wull S111
uEG(-,r)
a-1b
In words, U2 is the set of vertices of S selected as follows: a vertex selected if all its parents have been selected already, and weights links to its parents have moved no more than 17 from w to w.
The extracted graph is then U = (Vv, Ev). where Vi = Ubev, Ug. and Ey = Es n (Vr X Vt). First, let us check that the inclusion ty U S is fibration, and that the weight-approximmatio
28

---

condition is satisfied. It is immediately verified that it is isomorphism of graphs. Moreover, by
definition of U. if E Vy then U(-,²) = G(-, v) = S(-, v), therefore by is an isomorphism of in-neighborhoods, thus fibration. To check the weight-approximmttinn condition, let e Ev, and observe that it holds by triangle inequality in Wa(e) that
(I(e [)) - (0 w "))lll l|w, - we(e S w| w + 11 we(e S + 21)
Thus, only remains to show that the restriction ølu : Vu - V has sufficient volume. This is little more tedious. We will switch points of view, to count the vertices from Vs that we reject instead of those that we keep. Define (again inductively on E VB):
C
V E - (
3u E G(-,)),
U Ua
aEVn
Wi (U) Eu E 2)), [10 - W(n,))ll > m}
In words, W is the set of vertices in Vs of "type b" that have been rejected because one the corresponding weights had moved much. Similarly, C. the set of vertices in Vs that have been rejected because one of their parents had been rejected (C stands for "chain" rejection). Observe that
Ub (6) Vs) (C.UW))
Therefore #U, 2 # (b) #C #W, Let us bound each term separately.
First, note that if L(G) S V, and Vs. then Uz(s) because G(-,v) Ø.
Regarding #W, since we know by assumption Eeeg 1lw@ well S E.Egll well 2 < R2, but also by definition of Wo that # Wo v/2 EeEF, 1lu w. 112 we can deduce that # W, I R²2 ///².
Regarding #Cs. we will rely on the following forward inclusion:
C. S
U
U
G(v,-)
a-B(-bb) vEC.OW.
therefore can leverage outgoing degree bounds to obtain
#C. S
Σ
(#C. #W.) d(a.6)
(EB(-N))
At this point, it becomes casier stop thinking in integers and cardinals, and switch rates.
Define r: VB + [0. 1] the "rejection rate" r: + (#Ca + #Wa) /nn.. We have shown so far that if E IB. then l 0. Then, dividing the previous inequality by ns on both sides, and rewriting
rb
#W, #Cb
<
Σ
#Ca #Wa ne diam
Σ ra d(a.b) na eEB(-
Thb
nh
-E
Write = 1 inf a/(1 + Ve, Using the second assumption, that 2 R²
1 and the first
assumption E E(a.))EE d(a,t) na
< A, deduce the following bound for
Tb S #Wb
Σ
Fa d(
na nb
R² 172 no
d(a.t) na (b)
Σ
max Ta (a )
71
nb
aEB(-Mb)
S
max Ta aEB(-.b .b)
Hence by Appendix- I.5,, we get max Tb S 8. (1+ A) A)#V < inf
We are now ready check volume conditions on plu U G. Let V*, and b T.(v) Vp.
(pl x (4 (x)) ((C.UW))
29

---

Thus, by using the a-covering property of ip: S - G* and the previous bound rs I a(u)/2,
# ((vll))'(v))
2 # (0- (v)) - (#W, + #C&)
2 (()) 7h - 726
1 (c) Tib
Thus (U, (U,))l)) E M2n
Maf [[G, w), (G*,")),, which concludes the proof.
)²)
Lemma 1.5 (Low out-degree of random sparse lifts), Let n VB + N such that if b E Ig then na #PC 1 (6). Let (G, w) be a random sparse lift of IB
along (n, X) with distribution N.
For any 8 E J0, 11, for (a, b) E #EB, let ((, = 7 na Ma.b) + loog n. + log #EB log d.
It holds
P ((a E EB, sup # (
v D(a.)) 21-6
vE* (()
Write d: EB + N the random variable d: (a, b) E EB + suPuer M(a #(G(U,-) - (6)).
R., Let (a, Eg. and p = \(a,b)/ /aa Define for all (i,j) E [na] x [ns]. independent random Bernoulli variables
Proof of Lemma I.5. Write for shortness
- log(0/#Egp
m(ij)) ~ Bern (p). For i [na]. let X; = Eje(mu) m((r)) Note that these variables have Binomial distribution X2 ~ B (no. Thus from Appendix-Lemma L.2,
PP (XN 2 D(a,)) I exp (-ma D
D(a.6)
M(a.6)
na
where D (a)lp) = a log a p
+ (1 - a) log
1-a I-p'
Observe that D(a,b)/mn A(a,b)/Ma because
p == D(a.))
na
7 7>(a.))
na log n
na N A(a.))
7 7)(a,))
7>1
Thb
((abb)
A(a.b)
{(a
Therefore, we get (S1) by Appendix-Lemma L.3 and (S2) by the previous lower-bound on in
((a,))
\aa,b)
Dia,6)
log (p) + 1 -111
D(a.b)
D
71b
(S1)
(S2)
because log(7) + ~ 1.09 + 0.01 2
Hence so far, we have thus shown that ny
Pia
Aia.d) The
> M log(na) +c. Thus,
(
MM
(a.6)
))
P(xa 2 D(ao)) S exp (-ns D
< exp (- log ni c) = _e-
na
Then let X = supugina] Xa. and observe that by definition of random sparse lift (Def. 4.2), The random variables X and d(a,s) have the same distribution. By union bound,
P (dia.)) 2 D(a.)) = P ((a <
Σ P >
D(am))
Σ
1 c -===e-= c
The
uE[n..]
uE[na]
Then by union bound again, and by definition of the shorthand llog
8
#EB
PP (3(a,b) Eg, d(a.)) D(a,t)) <
Σ
P (d((,,)) 2 D(a,b)) S #E - =
(a.))EB
By negation, it follows PP (v(a,)) Eyg, da, D D(ait) 21-
30

---

1.1.2 PROOF OF BALLWISE COVER RESISTANCE
Proof of Proposition 1.3.
Write d: EB + N the function d: (a, b) E EB + d(a.b) - supvex-1(a) #(((v, -)n=
Let A be the event {M
1/2 [(,, )), (G", wn))") }] + } (a covering exists at initialization). Then, let Ades be the event {Ab E VB, BB) d(a.b) de - A} (the lift has relatively low out-degrec).
na
Degree control. Let us start by showing that ((A 2 8/2. In order to use Lemma I.5, let us show first that for any (a.b) E EB, it holds na 2 2 max > /aasy/ log(2)). By case disjunction on a, first if a E 1g. then on one hand A(a.6) I ng/2 = na/2. and on the other hand ((a I (m./3) /2)/33//2 = (ma/3)1/2 thus Ma. (ogg)) I (2/ (2/log()))mma/)) S n. because 2/ log(2) 2.88 + 0.01 S 3. For the other case, if a & TB, then by dropping extraneous factors in the assumption, aa 2 2 (1 + A)² since # VB 2 1, which concludes because A 2 A(a.)).
For every edge (a. b) E Eg. define ((a,)) = (a + -log nu + log #EB - log(6/2). By virtue of Lemma 1.5, we have
IP b) E EB, d(a S D(a,))) 2 21-6/2 5/2
Moreover, for any b E VB.
na D (a.
na log na
Da (log #EB - log(6/2))
7a(a.)) +
+
4E (( 76
(SL) (E
n2b
Tbb
Σ
7)(a.)) + 1 + #EB log(8/2)
(EB(-M)
Σ The +1+ +ogg + #EB) log(8/2) A
(S3)
cEEB
where (S1) is the definition of Pla.b), (S2) uses twice the assumption that n& 2 na log nhe for every
a E B(-,b), 6), and (S3) is the definition of A. Thus
P (Ade))= 2 P (V(a, b) E EB, d(a,b) S ((a,s)) 2 1 - 8
Initial cover. Let us show now that PP(0or))= 21 1 5/2. By leveraging Proposition 1.2 as (S1), and writing for shortness, when n., (v) = b, as in the proposition, r(u) = na (,, we have
r(U)²
TP (M, (M (G*,, x²)) Ø))
1 Σ
nb am/a(1))
n/2
exp
(S1) DEVaiIa
VÊT, ((b)
T())2
1-
Σ
Σ
exp
a an)2(())
(52)
4
bEV le NEN,
(b)
>
1 Σ
Σ
exp
mo
1
nu
an/2(1)
(S3)
bEV LE VEA, (b)
8
> 1
Σ exp +log
24
(84)
VEV.
2 5/2
where (S2) is union bound, then (S3) uses nn a (v)) 2 4 thus T(N)2 2 (3/4)² 9/16 1/2. and (S4) uses nn - (2) 2 8 (R++)'
(1 + A) VV e 2 8 Z -8 log 24
x
Conclusion. Finally, by using Lemma 1.4 for (S1), and a union bound for (S2), we get the bound /2/// P(VW E B(w,, R), M [(G, (G', w/ ) + Ø) (si)
Pl n )oor) 1-6 6
(82)
31

---

J QUANTITATIVE PAC CONVERGENCE OF RANDOM SPARSE LIFTS
The statement of this theorem references the definitions of Section 4.2.
Theorem J.1. Let (e, E R x 10. Assume that there exists G = ((V*, E parameters (w* a²) Param G*) LinReadout(G", k) such that [[G*] a²)
Lift C) a lifted perceptron module, and T. c.)
Let [(G*)(w", a²) = Eo, and define the constants
|a
C== Σ Σ
(E+
V #T. (Tx
1
8 1 - VEO
17 = sup 17 E L[G', w 1,,, X)
C+
A Σ (7)(a)) + log(2) log (V*
#EB) log 6)
(a.b)EBn
Let 02 : V + >0,011 be the a-parameter associated to (G*,wt and by Def. 1.1. Define
2| 1|
Σ Σ
c=
KE(A] vET(G*) (n/2(v) #T. (Tx(
Let == = 3/ 11 Ler N1 = VB + N be defined for E TB as Ni = # (b) and
WEVBALL (b = (1 4e 1
2 (1+ A))++
C- inf (n)2(()
It holds, for all n E Sq such that n ł N1, that if (G, w) is random sparse lift of B along (n, A) with distribution N, and a = 0 E LinRcadout GondoottG,,,a k), then the pair (C[G), (w, a)) satisfies Convergence Criterion I with limil error and constant 6, with probability at least (1 8).
Theorem 4.3 is a direct consequence of Theorem J.1, is is thus sufficient to prove the latter.
Proof of Theorem J.I. Define 6a [["")(w,, [[''("""")))))))))) Ri the error achieved by the witness. Then, define ε = (Eo + =)/2 |so,e[ the midpoint between the witness error and the target limit error.
Outline. The idea for the proof as follows. First, we use the witness network get tangent approximation to error 6 Eo on a ball around initialization (by Proposition H.4), provided the network large enough to have the witness as subnetwork. This possible because we take n small enough to ensure that the gap between the witness eπror and tangent approximation eπror is no more than (e) - Eo). Then, for a yet unspecified constant R, we leverage Proposition 1.3 set N, large enough such that the witness is subnetwork on an R-baal with probability at least (1 - 5), thus we have tangent approximation with error & < E with high probability. Finally, we set R large enough with respect to the gap (a E1) and the tangent approximation intercept (as per Theorem E.2 and more precisely Lemma 1) to ensure the limit error gradient flows is at most E, and propagate that choice of radius to the definition of N1, which will be sufficient to conclude.
Proof of Condition C1. Let us reconstruct the setting of Section with the definitions of perceptron modules. Let (S, =) be the set S {n VB + N vb E Ig, n. #PC (b)}. with the order n² < n² if and only if vb E VB, < n/. For S, define C (Vc, EE) the fully-connected lift of B along n, and the set G, of lifted modules² ((Vg. Eq), x.C) E LiftPMod C) with vertices Va = Vc. Let θ,, = IeeeR WWe. Define F(n,G) : On, > (X + I the forward function
F (w, = a F[G][w, -). Let us try to show that Condition CI satisfied with parameters (E1, 5) and with intercept c. Let R E R., and let 8y (R)
be defined as follows
R + n) (1+ (1+A)++WY
4b E VB TB.
[R),,
1 inf (n)
Note that there distinct elements of G, which may he isomorphic as graphs.
32

---

Let $1, let (G, w) be random sparse lift along (s, and and a 0 LinReadout k). By Proposition 1.3 and by definition of $1 (R)), with probability at least (1 - 5) over (G, w)), for every w Param(G) such that || - w S R, it holds that (G, w) has a -overr of (G*, w") Furthermore, by Proposition H.4, this implies that for every r R and for every a E LinReedoott(C k) such that [[w, a) - (w aa)) aa)]l S r, writing 0 = (w, a) E O. the proposition
implies that there exists O, with ||u| S c ||a]| S c and such that
()) + (f(),))(0) u- - S + C* LIG w [[,,,,))))) 8
This is nearly the (e1, 6) tangent approximation stated in Condition CI, but the assumption uses a strict inequality. We could proceed by extending the proof of Theorem E.2, but since our bound on the threshold N1 is not tight anyway, we will instead choose to match the assumption exactly. Therefore, define E2 (e + E1) Note that E2 E1, therefore we have shown that Condition CI is
satisfied with parameters (82, 6). Moreover, by an immediate calculation, & - E2 = (e - eo)/4.
Proof of PAC PAC-convergence. Note that holds [[G a²) S fl Il almost surely because a 0. Thus, as per Theorem E.2, set Ro = cll.f*IlB, - E2) and inject that constant Nj = $1 (Ro) Indeed, this matches the definition of N1 because Ro- cl cilss / 22) cll s | 1l/ 5o) This concludes the proof.
K PROOFS OMMITTED FROM THE MAIN TEXT
Here we provide several straightforward checks that the definitions introduced in this document are properly defined. All ideas are relatively simple, but the very general notation can sometimes obscure this simplicity. Lifting in particular requires going back to the definition and carefully checking that every type coincides with what we expect. The MIP examples of Fig. 4 and Fig. 5 can help.
K.1 LIFTING BY HOMOMORPHISM IS WELL DEFINED
Proposition K.1 (Def. 3.5 is well-defined). Let = (V EB) be a finite directed acyclic graph. Let BB (IIg TB), ()), Z. W), (M, o)) E PM) be a perceptron module.
Let = (V, E) be a graph, and π : G + B a homomorphism of graphs.
Then G ((T (IB), x (T)) (TB)), (T" n
n W)), (M, o)) is perceptron module.
Proof. Let us check the conditions of Def. 3.3 one by one. First, G is a directed acyclic graph, because G B is homomorphism and B is directed acyclic graph. Then, TG (TB) C V, and if v E Lo. then π(v) E LB therefore B(-, (v)) = Ø, thus G(-.v) homomorphism. Then Tc = ((TB) S is immediate. The bundles π >",, x Z=,=''> W over respectively V, E, E are well-defined by pullback (Def. 3.2) through æ V - VB viewed as function of sets (respectively π + Eg as a function of sets). It remains check the domains and co-domains of (M, First let (u, v) E E, and observe that
Ø because is
M(a,)) MM((r)) E (Wz(u,)) x V=(x)) Zz(u,o)) ((F")) X (T))), (m²Z)(uu)) (u,)))
Then, V E We have (v) E VB \ because TG = (IB). thus (n() has type signature Tx(x)= IIEER(, ZT(u,e) + Vr(e)- Let = II (T" x (2=2) ()(m,)) and let us show that (2) E (T)) For any a E B(-, we can define Za EuEGG(-Nv) 2n, where Go(-,v) (a) n G(-,v). This sum is well-defined because E (x* (7*2) () ((x()) ((ax(())) and (aa)(()) a vector space. Since Go S G(-,u), the quantity Za a function of Then the check concludes by (2) xx(1)
Va(()) = (л y), by definition. Li
K.2 THE PARAMETER a OF PERCEPTRON MODULE IS WELL DEFINED
Let us check that the parameter defined in Definition 1.1 is well-defined. First, the expression well-formed because the finite directed graph G* is acyclic since it admits a homomorphism T. : G* -> B to acyclic graph. Then, for all E V*, as a product non-negative factors lower than 1, (v( E [o, 1]. Finally, by induction on v, it is immediate that (v) > 0 provided all factors (u.(u,v) (1) (M)) 11) are strictly positive, which is granted by the full-support assumption Nr, (a,r)-
33

---

K.3 SUBADDITIVITY OF THE D-SEMINORM
Proposition K.2. Let DD be a distribution on X' with compact support, and define for I X 4 R=
11:1D: I BEND (x)
Let a X - RR and b: X + R. Then it holds l|a + b|lp & ||a|D + |
Proof. Since both sides of inequality are non-negative, we work directly with squares. By straightforward computation, using Cauchy-Schwarz inequality in R2 then E[AB]² s E[A²] B[B*).
E a + ba [
E || 2( d2) + 1
E |1|a=11 2 0- bb + |
||a]|: 2E | 112 [bx122] + ||b||
S ||a]ß: 2 E I1|a2113
E b1 1 + 100
([aall + [b(l))²
L TECHNICAL LEMMAS
Proposition L.1. Let A E R4,, n MEN, [n]. Ifn 2 max(2), 2X2/ log(2)), (Xggo)))
then
[ (1- Rー
1 2
Proof. Let 102] + RR log(1 (1 - 2) + x. We will start by showing that g(x) 2 2
Indeed by computing the derivatives, g(0) = and g((x) = - 1/(1 - x) so g' g'(0) and
g"(x) -1((1 - x)² Observing that gx(x) 2 -4 for x E [o, 1/2]. and integrating twice following Taylor-Laplace" theorem with integral remainder, get
( = 9(0) (z)(0)( - 0) + [ g (x)s -s) ds
1"
s²
-4(x - s) -4 25
00
-2x
Let us now apply this result to a/n < 1/2.
A
1
X2
log
ng
n
n
7
n
Therefore, moving the À term from the left to the right hand side, and taking exponentials,
1 (1
A n-k
222/n
1
(LL)
n
(S2)
where (S1) uses < 1 - A/n < 1, (S2) is the exponential of the previous inequality, and (S3) the assumption 2 2X² 1og(2) which implies -2X /n log(2).
Lemma L.2. Ler X ~ Bern(n, p) be binomial random variable, and M E R4.
(-n
M
P P))
P(X 2 M) S exp
where D alog + a) log و-
This lemma is Mulzer (2018, Theorem 2.1), which presents and discusses several proofs.
34

---

Lemma L.3. For all (a, 1f. let D (a p) a log a + (1 a) log 1-p It holds
p
a a2p= = a p())lp)= 2 log -11
Proof. Note that it is sufficient to show that log 1-a ス - a. Let f lp, a + +R, u log(1 - u). 1-p
This function has derivative ['(u) 11/(1 - u). For S it holds ('(u) 2 -1/(1 -a). Thus,
1 - log
[]((]] = J ('(u) du 2 1
-1 du p-a
1
Multiplying both members by (1 - a) 2 concludes the proof.
Lemma L.A. Let (Xi)) be independent identically distributed random variables with values in {0. 1) such that [[X,) 2 E [0. Let X = E. X For all & E J0, 16
P(X S (1 10---)1 8)mp) S exp (-568mp)
This lemma is Mulzer (2018, Corollary 4.3).
Proposition L.5. Let S be a finite set with strict total order <. r - B4 be a function such that r(min S) and such that there exist two constants (p. 9) E IR2, such that
e S, Sptt-
maxr(a) 2<8
Then, it holds
maxr(s) Sp. p.p.... (1+ g) #S
Proof. Let x N - RR, be the sequence defined by 2 = and J++1 = p Ty. By quick induction, J& p Eich q². The total ordering of S induces & S S] an increasing map, called numbering S. By induction on [#S] C N, we will show that r(v ((k)) S max Vg. The case h = 0 is immediate because both are null, and for s = + (k + 1) we have
r(s) S p q max ((a) p + maxr(w (t)) S p p
max max x q I2 max isk
e<s
isk
iSk
Now observe that for all k E N. it holds h <pΣ is of <p igk (0 p. (1 + 9)a Thus
max r(s)
max 24 S max (1 q)¹ Sp (1 (1+
#ES
*S#S $5#5
Proposition L.6. Let P and {Eç i [P]] be collection of finite sets. There exists disjoint collection (Vr E [P]} such that for all E [P], it holds both V, S E, and # EE.
Proof. The proof is an application of Hall's marriage theorem. Define the bipartite graph G as follows. Let [P] + N be c: EPP]. Define the left part of the graph as X [e [ca). Uke(py E, For any (i, u) E X (i.e. E [P] and u E [c]] and e E Y. there is an edge ((i. u). e) in G if and only if E E, An X X-perfect matching in G is an injective function M X Y such that (z, (x)) is an edge of G for every x E X. Such a matching yields choice of subsets (V: M([i} x [c:]]]; satisfying the conditions, therefore, let us show that such matching exists by proving Hall's condition: for every W C X, it holds #W I (N))W) where No(W) Y are the neighbours of W in G. Let W C X. Let / (i E [P] 3u, (i, u) E W] Observe that #W < Eier C, < maxeel # E. However by definition G. No(W) = Uler E,
and the right part as
thus we get # W < max # EE S # #(Uler E,) #Nc(W), which concludes the proof.
35

---

M CONVOLUTIONAL EXAMPLE
We give in Figure 7 an example of fully-convolutional neural network to compute functions R 1
+ R. The max operation has signature mum across the feature map, wich is typical of fully-convolutional networks. The lift dimension of the input is 3, which corresponds to the three color channels of RGB images, and the lift dimension of 6 for the hidden layer corresponds to 6 "channels" of activations in the hidden layer.
R - R and computes maxi-
R5x5
R5x5
3
R 16x16
R 12X12
R12x12
F 8888
R
convolution no-pad
ReLU
convolution no-pad
max ReLU
Figure 7: Convolutional perceptron module. Lift dimensions correspond to channels.
N EMPIRICAL OBSERVATIONS RELATED TO THE PRESENT THEORY
We include this section several preliminary experiments evaluate empirical predictions based on this theory. None of these experiments are sufficient in scale or diversity to claim anything consistent across architectures or tasks. However, we hope that these experiments suffice to show that the theory presented here is not entirely vacuous, and that conducting larger and broader experiments to verify and challenge its predictions is direction worth pursuing.
The present theory is limited to continuous-time gradient flow for very large lifts, but we hope that future extensions will tackle time-discettizaton, smaller lifts, and different optimizers. For these reasons, we perform these experiments using an empirical setting closer to the common practices of deep learning, despite the discrepancies that this induces with the theory, to show that it still produces valuable insights even outside its limited application domain at this early stage.
N.1 QUANTILES OF THE FINAL TRAINING LOSS
In the context of one nnee-imensional regression, we train random sparse lifts, with two distinct base modules, and plot quantiles of the final training loss reached as a function of the lift dimension.
N.1.1 DETAILS OF THE EXPERIMENT SETUP
We consider the one-dimensional regression task of learning the target function f" lR. + R, defined as æ +> sin(w x + ip,, with target parameters 2, w 0.5 and yp = 0.42.
The training set consists of n = 10 input points independently sampled uniformly at random from the interval [0, 100), together with the corresponding value for f*. We use the quadratic loss on IR and the models described in the following section. We train each model for 10 iterations with training samples grouped by batches of 10, taken uniformly at random in the training set with replacement, with the Adam optimizer for step size of 10 2 We consider base perceptron modules describing two-layer networks with biases, but with two different activations. For each lift dimension, we plot twenty training for each lift dimension the median of the final training loss in orange, the first and third quartile with a box, and the first and last decile with its whiskers.
N.1.2 BASE PERCEPTRON MODULES STUDIED
We use as models the random sparse lifts defined by Figure for a (-)+ : x + max(0, x) and sin RR + 1- 1J. Note that for two layers, since the input dimension is one and the last layer is a fully-connected linear readout, neither of those models is effectively "sparse", despite being defined random sparse lifts. This coincides with the usual definition of multi-layer perceptron for two layers and activation a : + R, with the additional node above being used to create bias term in the language of perceptron modules. Lift annotations of vertices depicted above the vertex.
36

---

R
R
R
h
R
I
(a.n)) vn++b
Figure 8: One-dimensional two-layer perceptron blueprint with activation
N.1.3 EXPERIMENTAL RESULTS AND INTERPRETATION
We plot in Figure the results of this experiment. We observe that, as predicted by the theory, when the lift dimension increases then all quantiles of the final loss decrease (it is unclear whether they will tend to zero as predicted by the theory. see the discussion with the next figure). We do not observe an "incompressible failure probability", of for instance 10% of networks error regardless of size. We do not observe a significant chance of small networks reaching near-zero loss, despite universality results with low lift dimension. We do not observe across blueprints the same speed of convergence of the eтror to zero with respect to the lift dimension (note the differences scales in Figure 9), on the contrary the two blueprints define two very different families of networks in terms of effective learnability at tractable sizes. We do not observe a "sweet spot" in lift dimension. past which large networks would consistently fail learn or have diverging training loss. All of these observations, despite the notable differences between the experimental setting and the theoretical model (discrete vs continuous time, change of optimizer, etc.), are relatively consistent with the theoretical predictions. This suggests that this type of experiment could be conducted at larger scale to challenge the predictions of this theory.
moving below 1.90 train
Architecture: ReLU MLP
Architecture: Sine-based MLP
10
1.9
1.8
10
1.7
10 2
Final Training emror
Final Training елго
1.6
10 3
1.5
10
1.4
10-1
1.3
10-6
1.2
10
1.1
10-5
10
102
1
10a
103
10
10a
10
10a
10a
10
106
Lift dimension (a.k.a. width)
Lift dimension (a.k.a. width)
Figure 9: Median, inter-quartile range, first and last deciles of final training loss (106 iterations).
Since the measurements in Figure 9 are used as estimates of the limit value reached by the loss, we assess the quality of convergence in Figure 10. We plot the same quantiles of the training loss at 80% and 100% of the total allocated training interations: on one hand, for networks that have converged to critical point, expect these quantiles to be identical since the parameters should not move when
37

---

gradients null; the other hand, if they differ significantly, then the experiment would need to be repeated with an increased training budget to rule these considerations out.
Architecture: ReLU MLP
Architecture: Sine-based MLP
1.9
10
1.8
10-1
Final Training error
Final Training error
1.7
10
1.6
10-3
1.5
10
1.4
10-5 5
1.3
10-6
1.2
10
1.1
10
10
10a
103
10
10a
10c
10a
10a
10a
104
10a
10
Lift dimension (a.k.a. width)
Lift dimension (a.k.a. width)
Figure 10: Superposition of quantiles at 100% and 80% (in red, shifted right) of training.
For lift dimensions lower than 102, the results are similar enough that the measured loss can be understood as the final limit. For higher lift dimensions, this conclusion is not as clear, and other replication experiments would be needed confidently conclude that the observations on these plots are representative of a general behavior of neural networks, rather than only artefacts of this very particular experimental setting. Given the very simple setting, and comparatively very large lift dimensions and training times explored here, these observations remain promisingly similar to the theory's ' predictions.
N.2 SPARSE VERSUS DENSE LIFTS IN CLASSIFICATION
In the context of classification, for the MNIST digit-recognition dataset, we perform experiments with dense and sparse multi-layer perceptrons to check whether there exists fundamental difference which would prevent the extension of this theory to the dense setting.
N.2.1 DETAILS OF THE EXPERIMENT SETUP
We train several models on the MNIST digit recognition dataset, using the cross-entropy loss and the Adam optimizer with a step-size of 10-3 by batches of 100 samples taken with replacement, and measure the test accuracy of the resulting models after 10 training iterations.
RR
R
R
R
R
Ø
X
Ø
784
h
R
h
10
R
R
R
R
R
R2
R
À
2
ReLU
ReLU oI
((H,,))) b)/z/ vn++b
Figure 11: Blueprint of the base perceptron module used for the MNIST experiment. Lift annotations are depicted above the vertices, and inside the boxes for edges (oo indicates dense connection)
For the dense networks, and ReLU activation. We initialize each weight matrix W e gaxm with independent identicaly distributed entries, with gaussian distribution of mean and variance 1 1/n, also known as
three-layer fully connected perceptrons with hidden widths h e N
38

---

"Kaiming He's normal initialization with fan-in mode", and biases with normal distributions. Each "linear" layer computes the function (W, b, 2) + W x + (i.e. without a renormalizing factor).
For sparse networks, identical architectures. We use a lift dimension
random sparse lifts derived from the blueprint of Figure 11, to have nearly-
IN identical for all layers, and a degree parameter R4. We initialize all weights with normal distribution. Consistently with the definition of linear readouts, the last "linear" operation computes the function (W, b, 2)) + (W x// Vh (i.e. with a renormalization factor of vh for the matrix W E 1xx110) We vary À R the expected incoming degree of hidden nodes, and for both dense and sparse models, we use various powers of two for the lift dimension h E N.
N.2.2 EXPERIMENT RESULTS
The results of this experiment are depicted in Figure 12. In the absence of any regularization or data augmentation, or even large hyperparameter scans, we do not expect particularly impressive performance for either family of models, but only look for differences between the two families. At this small scale, differences in accuracy lower than 1% are to be interpreted with care.
We observe in Figure 12 that for similar lift dimensions, sparse networks perform slightly worse and their performance degrades when the sparsity is more extreme. However this drop remains relatively small, for instance
128 there only 3% drop from the dense model to the sparse model with A = 10. For scale, in the first hidden layer of the dense model, there are 784 x h & 10 parameters, while in the corresponding sparse model there are very similar to their dense counterparts, and we do not observe failures to learn (c.g. order of 10% accuracy) even at large lift dimensions. We also plot in Figure 12 the accuracy function of the total number of floating-point parameters, for which the performance is even closer Sparse models appear to outperform dense models with the same number of Koating-point parameters, however this gap In particular, the number of floating-poin parameters does not account for the total storage space of the network, since the connectivity of the sparse network also has be stored (e.g. using one bit per corresponding dense-networt parameter, with naive encoding), which should be accounted for in future larger-scale experiments. We did include large lift dimensions sparse networks this experiment, due to our inefficient implementation of sparse operations with few non-zero entries.
10 Overall the sparse models appear do not observe plateau very low (c.g. 70%) accuracy,
small for conclusions this scale.
MNIST MLP Dense vs Sparse
MNIST MLP Dense vs Sparse
0.99
0.99
0.98
0.98
0.97
0.97
Test-set accuracy
Test-set accuracy
0.96
0.96
0.95
0.95
0.94
0.94
0.93
0.93
Dense MLP
Dense MLP
0.92
Sparse MLP (A=10)
0.92
Sparse MLP (A=10)
Sparse (A=50)
Sparse MLP (A=50)
0.91
0.91
Sparse MLP (A=100)
Sparse MLP (A=100)
0.90
0.90
10a
10a
103
10
10
10
106
107
Lift dimension (a.k.a. width)
Number of poating-poinn parameters
Figure 12: MNIST accuracy of dense and sparse Multi-Layer Perceptrons with ReLU activations
This experiment is overall inconclusive in uncovering fundamental difference betweent the behaviors of sparse and dense lifts. This leaves hope that the current proof of convergence, tailored to the sparse case at the moment, will admit extensions to explain the performance of similar dense networks.
39


Reviews:
[{"review_id": "kSzMWlhAWQ", "reviewer": "Reviewer_9UCJ", "summary": "The paper is on the topic of proving global loss convergence for deep neural networks, which is challenging due to the presence of non-convexities. The paper describes a lifting procedure that generalizes the notion of overparameterization in the usual dense, fully-connected settings (for example in deep fully-connected MLPs). The resulting lifted networks can be sparse (which is a big difference to previous analyses of this type), which then allows for tools from algebraic topology to be used to ensure global convergence.", "questions": "I have not studied the proof in the appendix in detail so my apology if some of these are addressed in the appendix. \n- Do you have to maintain full support of the weight distribution throughout training (seeing that you have an assumption on initialization, similar to Nguyen and Pham, 2020)? If so, does sparsity of the network make maintaining full support harder than in the fully-connected case? \n- Do you think this result can be extended to classification loss (e.g. logistic, exponential loss)? If so, how do you compare your result to existing convergence results for these loss (for instance, Ji and Telgarsky’s 2020 ‘Directional convergence and alignment in deep learning’)\n- It seems from Definition 4.2 that the sparsified graph would have bounded average degree. Is this level of sparsity tight?\n- Small typo: Page 2, last paragraph, “S_0 = {(s_0, s_1) \\in \\mathcal{N}^2 …” should be \\in \\mathbb{N}^2\n- Typo: In section 3, sometimes ‘Euclidean’ is written with a lower case ‘e’. \n- It may make things clearer to add interpretation of each item to Definition 3.3. In particular, I’m not sure what T does at first glance (and it’s only explained later on).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written with clear definitions, motivations, sketches and illustration. I find the view of reducing feed forward neural networks to a simpler base module via directed graph homomorphism very refreshing and may have potential applications in other areas of deep learning theory outside of convergence analysis.\n\nTheoretical results presented are general and quantitative. The paper establishes global convergence of gradient flow (in a particular mode of convergence that exists in literature) for a large class of universal approximators and establishes that the learning number (smallest width sizes such that the network can learn) is not too large. This is applicable to a wide range of feedforward architectures, including those with skip connections or attention/self-attention.\n\nThe random sparse lift construction is interesting in that it is explicit and only requires a low-loss starting architecture (that can be obtained from experiments). Although I understand this is a theory paper, it would still be interesting for future work to try and construct this sparse life empirically to see if there are any gains in performances. \n\nThe assumptions are standard to the best of my knowledge.", "weaknesses": "Sparse networks are not very popular in practice and sparsity seems to be a very crucial part of the proof (to obtain fibration of the good smaller computational graphs in any larger computation graph). This is the main reason I'm hesitant to give higher overall score and contribution score. \n\nThe proof technique seems very targeted to sparse computational graphs where each node does not have a large influence on other nodes and may require a very different way of thinking about deep learning, compared to fully-connected networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "82IueRYE4F", "reviewer": "Reviewer_cG9T", "summary": "The paper introduces a new class of neural networks, in particular multi-layer perceptrons (MLPs), with provable convergence guarantees when the number of parameters is large. The initial architectures are \"lifted\" to large sparse models. Tools from graph theory are used to represent these non-standard architectures in a graphical form and discuss the mapping in between them.", "questions": "In conclusion, it is stated that the theory of this paper gives a route to strong convergence results and **testable empirical predictions**. Is there any justification for how this method can be used for testable empirical predictions in the paper?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The graph-based method to represent neural networks seems powerful. I also enjoyed the idea of giving convergence guarantees for the pair of architecture and parameters where the architecture is built in a way to be within the proximity of the target function where the tangent approximation holds.", "weaknesses": "Although the approach and results look interesting and might be promising, unfortunately, I found the paper incomprehensible. See some specific points below\n\n* The text is way too informal. The first sentence starts with \"trying to learn...\". \n* Already in the first paragraph, $\\theta$ is both an arbitrary variable and the true variable which I found confusing. I'd suggest changing it to \"for some parameter $\\theta^*$\".\n* It is not clear why a long list of citations from approximation theory (page 1) is given since the paper studies convergence. \n* In many places, claims are unjustified. For example, 'the class of neural networks that can be described .. more expressive than Tensor Programs\". Why is that so? It would be OK not to explain this if it was a trivial statement.\n* Informal text: \"full-support type assumption\" on page 2. \n* It is not clear to me how Theorem 2.1 helps the paper. As the authors say, it is a slight extension of Robin et al. 2022 with a very similar proof technique. It would help to add an intuitive explanation of how this result will be used in the paper. \n* I have not seen how the class of architectures introduced here includes/related to convolutional neural networks. \n* The definition of the random sparse lifts (which is in the title of the paper) comes on the last page (Def 4.2). This is very unusual and it makes it nearly impossible to follow up with the text until the last page. I'd kindly suggest arranging the text in the following order: (i) introduce the definitions (only those elements needed for the main theorem) (ii) main theorem (Theorem 4.3) (iii) discuss generalizations to other architectures such as transformers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OSggAqdOXx", "reviewer": "Reviewer_nC6x", "summary": "This paper proposes random sparse lifts for neural networks and shows their convergence under gradient flow", "questions": "1. The discussion in Section 2 seems to suggest that the convergence analysis is an extension of the existing NTK analysis, how does the results in this paper different?\n2. How should one understand the $\\mathcal{C}$ in LiftPMod? The example given in the paper is not very helpful. It would be great if an example of random sparse lift is given for a specific NN architecture, say multi-layer feedforward networks.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "Since the reviewer is not very well versed in this area of research and could not fully follow the technical part of this paper within a short amount of time, the decision should default to the other reviewers.", "weaknesses": "See \"Questions\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dsl0IKLyYA", "reviewer": "Reviewer_ZupD", "summary": "This work proposes a \"lifting\" procedure on a general computational graph. Randomizing over these lifts, the authors show that training converges with high probability.", "questions": "1. What do the authors mean when they say that networks whose width is not increasing with depth \"could be ill-behaved\"?\n\n2. I didn't follow the sentence: \"\"Lastly, if there are many such subnetworks, then a small modification of parameters cannot substantially modify them all if the large network is large enough.\"\n\nAs I am not familiar with the field I cannot give a confident review, although I hope the authors will be able to atleast dispell my concerns about weakness 2 above.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper proposes a really interesting idea which to the best of my knowledge is novel.\n\n2. The authors tackle a notationally dense topic with care and precision, even including a notational glossary in the appendix.\n\n3. Presentation and logical flow are excellent, paper is easy to follow.\n\n4. The theory seems well fleshed out (e.g., showing well-definedness in appendix K), although I did not check the proofs.", "weaknesses": "1. It's a shame that the authors did not include concrete experiments training their lifted models. I would be interested to see empirical tests validating the theory: i.e., actually do $n$ random lifts, train via sgd, and see what percent of the time it converges.\n\n2. I have reservations about assumption A1. The set $A_{s,g}(\\kappa, \\epsilon)$ echoes ideas from neural tangent kernel approximation -- as the authors note, it includes not only weights which are close to $f^*$, but also weights which can be made close to $f^*$ by moving a little bit $u$ in the tangent approximation to the network. The NTK argument justifies this by showing that, under some random initialization, networks are close to their linear approximation as their width goes to infinity. Assumption 1 essentially starts by assuming that the tangent assumption is reasonable, and then states a lower bound on the size of the set of weights that can be made close to $f^*$ by moving in the tangent plane. So in effect they seem to be _assuming_ what NTK analyses _concludes_ from infinite-width scaling. In that light, the fact that this paper claims convergence guarantees for finite-width networks does not seem that impressive.\n\nI am happy to raise my score if either of the above points are adequately addressed, as I actually found the paper quite interesting. I was originally inclined to give a stronger recommendation but my understanding on (2) seems to be a serious limitation.\n\nSmall remark / suggestion: some sentences are somewhat difficult to parse due to length, especially in the intro. For example: \"Distinct from the fixed-space global optimality of non-convex optimization, this new form of convergence, and the techniques introduced to prove such convergence, pave the way for a usable deep learning convergence theory in the near future, without overparameterization assumptions relating the number of parameters and training samples\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)