From Complexity to Clarity: Analytical Expressions of Deep Neural Network Weights via Clifford Algebra and Convexity
Authors: Mert Pilanci
Venue: Accepted by TMLR ()

Abstract: In this paper, we introduce a novel analysis of neural networks based on geometric (Clifford) algebra and convex optimization. We show that optimal weights of deep ReLU neural networks are given by the wedge product of training samples when trained with standard regularized loss. Furthermore, the training problem reduces to convex optimization over wedge product features, which encode the geometric structure of the training dataset. This structure is given in terms of signed volumes of triangles and parallelotopes generated by data vectors. The convex problem finds a small subset of samples via $\ell_1$ regularization to discover only relevant wedge product features.  Our analysis provides a novel perspective on the inner workings of deep neural networks and sheds light on the role of the hidden layers.

Published in Transactions on Machine Learning Research (10/2024)
From Complexity to Clarity: Analytical Expressions of Deep Neural Network Weights via Clifford Algebra and Convexity
Mert Pilanci
pilanci@stan ford. edu
Department of Electrical Engineering
Stanford University
wweu www.sstonford.oo www..dedu//eeee edu/rpilanci
Reviewed on OpenReview: htips: // openreview. net/ tet/ forum? id- 6XPuSuEWs
Abstract
In this paper, we introduce novel analysis of neural networks based on geometric (Clifford) algebra and convex optimization. We show that optimal weights of deep ReLU neural networks are given by the wedge product of training samples when trained with standard regularized loss. Furthermore, the training problem reduces to convex optimization over wedge product features, which encode the geometric structure of the training dataset. This structure given in terms of signed volumes of triangles and parallelotopes generated by data vectors. The convex problem finds small subset of samples via & regularization to discover only relevant wedge product features. Our analysis provides novel perspective the inner workings of deep neural networks and sheds light on the role of the hidden layers.
1 Introduction
While there has been a lot of progress in developing deep neural networks (DNNs) to solve practical machine learning problems (Krizhevsky et al. 2012 LeCun et al.] 2015 OpenAI 2023 the inner workings of neural networks is not well understood. A foundational theory for understanding how neural networks work is still lacking despite extensive rescarch over several decades. In this paper, we provide a novel analysis of neural networks based on geometric algebra and convex optimization. We show that weights of deep ReLU neural networks learn the wedge product of subset of training samples when trained by minimizing standard regularized loss functions. Furthermore, the training problem for two-layer and three-layer networks reduces to convex optimization over wedge product features, which encode the geometric structure of the training dataset. This structure is given in terms of signed volumes of triangles and parallelotopes generated by data vectors. By the addition of an additional ReLU layer, the wedge products are iterated to yield a richer discrete dictionary of wedge features. Our analysis provides a novel perspective on the inner workings of deep neural networks and sheds light on the role of the hidden layers.
1.1 Prior work
The quest to undersland the internal workings of neural networks (NNs) has led numerous theoretical and empirical studies over the years. A striking discovery is the phenomenon of 'neural collapse," observed when the representations of individual classes in the penultimate layer of deep neural network tend to point of hear-indistingguisbbbilll
(Papyan et al. 2020). Despite this insightful finding, the underlying mechanism that enables this collapse is yet. to be fully understood. Tinearizations ions and infinite-widch approximations have been proposed to explain the inner workings of neural networks (Jacot et al.) 2018 Chizat et al,, 2019 Radhakrishnan et al. 2023). However, these approaches often simplify the rich non-linear interactions inherent deep networks, potentially missing out on the full spectrum of dynamics and behaviors exhibited during training and inference.
Infinite dimensional convex neural networks were introduced in Bengio et al. 2005 offering insights into
their structure. Following work analyzed optimization and approximation properties of infinite convex neural

---

Published in Transactions on Machine Learning Research (10/2024)
dist, (a, xz)
dist. (a, Aff
(x 22) A (œ) 22)
311 222
JF3
(a) One-dimensional neuron
(b) Two-dimensional neuron
(c) Optimal breaklines in Ik?
Figure 1: An illustration of the geometric interpretation of optimal ReLU neurons.
The break-
lines/ breepbbraasoints pass through subset of special training samples.
networks (Bach 2017
Although these works advanced the understanding of convexity in infinite dimensional NNs, they also highlight the computational challenges inherent in training infinite dimensional models, including solving a finite dimensional non-convex problems to add a single neuron (Bach] 2017). On the other hand, it has been noted that the activation palterns of deep ReLU networks exhibit a structured yet poorly understood simplicity. The work Hanin and Rolnick (2019) highlighted that the actual mumber of activation regions RcLU network learns practice is significantly smaller than the theoretical maximum.
Previous studies Fisher and Jerome relation to l extremal problems, demonstrating the adaptability of spline models to local data characteristics. More recent work (Balcstricro et al. 2018) connected deep networks to spline theory, showing that many deep learning architectures could be interpreted as max-affine spline operators. Approximation properties of ReLU and squared ReLU networks with regularization were studied in Klusowski and Barron (2018). The authors in Savarese et al. 20119) considered infinitely wide univariate ReLU networks and showed that the minimum squared &g norm fit is given by a linear spline interpolation. Another line of work (Parhi and Nowak 2021; 2022) developed a variational framework to analyze functions learned by deep ReLU networks, revealing that these functions belong to space similar to classical bounded variation-type spaces. In similar spirit, connections to kernel Banach spaces via representer theorems were developed in Bartolucei et al. (2023) The work Unser (2019) introduced a general representer theorem that connects deep learning with splines and sparsity. In contrast, our results provide an independent and novel perspective on the optimal weights of a deep neural networks through geometric algebra, and may shed light into the spline theory of deep networks. In particular, the relation between linear splines and one-dimensional ReLU works discovered in Savareee al. (2019) generalized to arbitrary dimension and depth in our work. The key ingredient in our analysis is the use of wedge products, which are not present in any work analyzing neural networks to the best of our knowledge.
1975
Mammen and Van De Geer 1997 have investigated splines in
The relationship between neural networks and geometric structures has been another area of research focus. Convex optimization and convex gcometry viewpoint of neural networks has been extensively studied in recent work PPllani and Ergen 2020 Ergen and Pilanci 2021a Bartan and Pilanci 2021a Ergen and
Pilanci 2021b c Wang and Pilanci 2022 Wang et al., 2021 Ergen et al. 2022a Lacotte and Pilanci 2020;
Bartan and Pilanci 2021b). However, previous works have focused mostly on computational aspects of convex reformulations. This work provides entirely new set of convex reformulations, which are different from the ones in the literature. Two main advantages of our approach are that our results hold for arbitrary depth and dimension, and that they provide a gcometric interpretation and novel closod-form formulas, which can be used to polish any existing deep neural network.
1.2 Summary of results
The work in this paper diverges from other approaches by using Clifford's geometric algebra and convex analysis to characterize the structure of optimal neural network weights. We show that the optimal weights for deep ReLU neural networks can be found via the closed-form formula, Ij. A...Auju known k-blade in geometric algebra, with A signifying the wedge product. For each individual neuron, this expression involves special subset of training samples indexed by (Ji...., J.), which may vary across neurons. Surprisingly,
2

---

Published in Transactions on Machine Learning Research (10/2024)
the entire network training procedure can be reinterpreted as a purely discrete problem that identifies this unique subset for every neuron. Moreover, we show that this problem can be cast as a Lasso variable selection procodure over wedge product features, algebraically encoding the geometric structure of the training datasct.
The Unexpected Neuron Functionality
The conventional belief suggests that artificial neurons optimize their response by aligning with the relevant imput samples (Carter et al.) 2019), notion inspired by the direction-sensitiee neurons observed within the visual cortex (Hubel and Wiesel 1968). However, this interpretation hits dead end in large DNNs, with numerous neurons responding lo unrelated features, making it nearly impossible to understand the specific role of individual neurons O''Mhonyyee et al. 2023). Contrary to this conventional wisdom, our findings reveal that ReLU ncurons are, in fact, orthogonal to a specific set of data points, due to the propertics of the wedge product. As a consequence, these neurons yield a mull output for this distinct subset of training samples, diverging completely from the anticipated alignment. This outcome underscores a nuanced understanding: rather than merely aligning with input samples, the neurons assess the oriented distance relative to the affine hull encapsulated by the special subset of training samples. This concept is visually explained in Figure D (a-b), where ReLU activation in 1D and 2D is interpreted as an oriented distance function. The optimal breaklines of the ReLU neurons, i.c., {x wT x + b = 0), intersect with select group of special training samples, expressed using a simple equation involving wedge products, leading to a zero oulput from the neurons for these instances, as illustrated in Figure [c). This result challenges the traditional interpretations of the role of hidden layers in DNNs, and provides a fresh perspective on the inner workings of deep neural networks. We show for the first time that geometric algebra provides the right set of concepts and tools to work with such oriented distances, enabling the transformation of the problem into a simple convex formulation.
Decoding DNNs with Geometric Algebra
Our results show that within a deep neural network, when an input sample z is multiplied with a trained neuron, it yields the product xf * (xi A... A x.2)- Leveraging geometric algebra, this product can be shown to be equal to the signed distance between r and the linear span of the point set Zar...., Zaa scaled by the length of the neuron. This allows the neurons to mcasure the oriented distance between the input sample and the affine hull of the special subset of samples (see Figure [ for an illustration). Rectified Linear Unit (ReLU) activations transform negative distances, representing inverse orientations, When this operation is extended across collection of neurons within a layer, the layer's output effectively translates the input sample into a coordinate system defined by the affine hulls of a special subset of training samples. Consequently, each layer is fundamentally tied solely to a specific subset of the training data. This subset can be identified by examining the weights of a trained network. Furthermore, with access to these training samples, the entirety of the network weights can be reconstructed using the wedge product formula. Moreover, when this operation is repeated through additional ReLU layers, our analysis reveals a geometric regularity within the space partitioning of the network, highlighting a consistent pattern of translations and interactions with dual vectors (see Figure 7). This geometric elucidation sheds fresh light on the mysterious roles played by the hidden layers in DNNs.
zero.
1.3 Notation
We use lower-case letters for vectors and upper-case letters for matrices. The notation [m] represents integers from to n. We use a multi-index notation to simplify indexing matrices and tensors. Specifically, j = (k: is a multi-index and Σ, denotes the summation operator over all indices included in the multi- index j, i.c., En ".E.s Given a matrix K E R=*x, an ordinary index i E [n], and a multi-index j == (kk)...jkk) where Ji E [d.] Vi E [k], the notation K2y denotes the (i, v(ji,..,, .....))...... js))-th entry of this matrix, where V represents the function that maps indices (Ji,..,, jk) to a one-dimensional index according to a column-major ordering. Formally, we can define v(ji,..,, fa) := (ii - 1) + (i2 - 1)di + (js - 1)d1d2 + t... + Un 1)d We allow the use of multi-index and ordinary indices together, e.g., a,9, ... Uya En "fhrr Uj U.a The notation K₁ denotes the i-th row of K. The notation K.j denotes the j-th
3

---

Published in Transactions on Machine Learning Research (10/2024)
column of K. The p-norm of a d-dimensional vector w for some E (0, oo) is represented by ||w|pp and it is defined as ||e| & (Si= |w;lP)//,, In addition, we use the notation ||w]oo denote the number of non-zero entries of and ||w]| to denote the maximum absolute value of the entries of w. We use the notation B% for the unit p-norm ball I&d given by (w Rd ||llpp S 11. The notation dist(x,)), is used for the minimum Euclidean distance between a vector x Rd and a subset y S Rd. Vol(C) denotes d-volume of a subset C S IRd. The notation (+) is used the positive part of a real number. When applied scalar multiple of pseudoscalar in a geometric algebra Go such as al E Gd, where I = =l, the notation (al)+ (a)+ R represents the positive part of the scalar component of I. We use the notation Vol+ (Vol(-))+ to demole the positive part of signed volumes. We exlend this notation to other functions, e.g,, del+(.) denotes the positive part of the determinant, and dist+ (s-)) denotes the positive part of the Euclidean distance. (S) denotes the Euclidean diameter of a subset S C R Span(S) and Aff(S) denote the linear span and affine hull of set of vectors respectively. We overload scalar functions apply to vectors and matrices element-wise. For instance (X w)++ denotes the ReLU activation applied to each entry of Xw. We use to denote the inequality up to constant factor.
2
Setting and Methodology
2.1 Preliminaries
Consider a deep neural network
f(x) = o(
b()))
(1)
where R R non-linear activation function, W ,.... W(L) are trainable weight matrices, 6(1), .... (22) are trainable bias vectors and x Id is the input. The activation function o(-) operates each clement individually.
Training two-layer ReLU networks
We will begin by examining the regularized training objective for two-layer neural network with ReLU activation function and m hidden neurons.
o (XW,") 1,0,") + +80),)) A m
p³
min wa, W(2) gC2)
Σ Iw
(2)
where X Raxd is the training data matrix, W(1) Rdxm, W(2) Ruxe and ((1) E Rm ((2) IR are trainable weights, f(-.)) is convex loss function, y E R" is vector containing the training labels, and A > 0 is the regularization parameter. Here we use the p-norm in the rogularization of the weights. Initially, we will assume an output dimension of == 1, and we will extend this to arbitrary values of c. Typical loss functions used in practice include squared loss, logistic loss, cross-entropy loss and hinge loss, which are convex functions.
When p 2, the objective
2 reduces to the standard weight decay regularized NN problem
p" min (fo.o Al101/ 0,b
(3)
Here, 0 is a vector containing the weights Wi and Wa in vectorized form and
fe) A x( + 1,666)) ( + 1,)(2)
(4)
where 1n is a vector of ones of length n. When set zero, we refer to the neurons in the first layer the bias-free neurons. When b is not set to zero, refer to the neurons in the first layer as the biased neurons. Note that the bias terms are excluded from the regularization.

---

Published in Transactions on Machine Learning Research (10/2024)
AAU
b
0
a
a
Figure 2: Wedge product of two-dimensional vectors.
Training deep ReLU networks
We will exlend our analysis by also considering the objective in 3 using the deeper network model show in [ It will be shown by a simple induction that the structural results for two-layer networks applies to blocks of layers in arbitrarily deep ReLU networks.
Augmented data matrix
In order to simplify our expressions for the case of p 1, we augment the set of n training data vectors of dimension d by including d additional vectors from the standard basis of Rd and let n d. Specifically, define the augmented data samples as { {r:) U (e: where E Rd represents the original
training data points for 1 < < and e, is the i-th standard basis vector in Rd for i n. We define X = [1,,"" "n+dd""
2.2 Geometric Algebra
Clifford's Geometric Algebra (GA) mathematical framework that extends the classical vector and lincar algebra and provides unified language for expressing geometric const ructions and ideas (Artin] 2016). GA has found applications in classical and relativistic physics, quantum mechanics, electromagnetics, computer graphics, robotics and numerous other fields (Doran and Lasenby 2003 Dorst et al. 2012 GA enables encoding geometric transformations in a form that is highly intuitive and convenient. More importantly, GA unifies several mathematical concepts, including complex numbers, quaternions, and tensors and provides a powerful toolset.
We consider GA over a d-dimensional Euclidean space, denoted as Gd. The fundamental object in Gd the multivector, M (M)o (M)+ ... + (M)a, which is of vectors, bivectors, trivectors, and forth. Here, (M)x denotes the k-vector part of M. For instance, in the two-dimensional space G2, multivector can be written as M basis elements are not just the canonical vectors e1, eg but also the grade-2 element e162.
v + B, where is scalar, is vector, and B is bivector. In this case, the
A key operation in GA is the geometric product, denoted by juxtaposition of operands: ab. For vectors a and b, the geometric product can expressed as ab = a b a b, where denotes the dot product and A denotes the wedge (or outer) product.
The dot product
is scalar representing the projection of onto b. The wedge product A b is bivector representing the oriented area spanned by a and b. In the geometric algebra Gd higher-grade entities (trivectors, 4-vectors, etc.) can be constructed by taking the wedge product of vector with a bivector, a trivector, and so on. A k-blade vectors. For example, the bivector a b is a 2-blade.
k-vector that can be expressed as the wedge product of k
Figure shows important properties of the wedge product in R2:
1. Wedge product of two vectors represents the signed area of the paralleogram spanned by the two vectors. In the left figure, A is represented by the blue parallelogram. When b are two-dimensional vectors, the
5

---

Published in Transactions on Machine Learning Research (10/2024)
(x; ((j)))) (z., -I (2 2z3))
Ti A Ti A 3i12
Zi
yz
32j
Figure 3: Wedge product representation of optimal neural networks in RS.
[a
b1
magnitude of a is equal to this area and is given by det
b1d2/. The sign of the area is determined by the orientation of the vectors: the area is positive when can be rotated counter-clockwise to and negative otherwise.
larby
(22
b2
2. The wedge product is anti-commutative: In the right figure, b is represented by the red parallelogram. Tt has the same area as a -b a, but an opposite orientation. As result, we have a A -a
By considering the half of the parallelogram, the area of the triangle in R² formed by 0, a and b shown by the dashed line in Figure 2 is given by the magnitude of aa A b. The signed area of a generic triangle in R² formed by three arbitrary vectors a, and e is given by
1 -)= ( --ccA--aA--CAtccAA (acbblbbo-(o-o--tttteeoe
which is consequence of the distributive property of the wedge product. Therefore, the signed area of the triangle is half the sum of the wedge products for each adjacent pair in the counter-clockwise sequence a + c a encireling the triangle. In higher dimensions, the scalar part of the wedge product represents signed the volume of a parallelotope spanned by the vectors (soe Figure 3).
The metric signature in Gd over the Euelidean space characterized by all positive signs, indicating that all unit basis vectors mutually orthogonal and have unit Euclidean norm. Let call the standard (Kronecker) basis in d-dimensional Euclidean space ei....,cd, which satisfics ef 1 Vi and eæe = -eje, es Vi A j. The wedge product I é e1 A ... ed G1 ..... ea represents the highest grade element and is defined to be the unit pseudoscalar. The inverse of is defined as I-1 6d .d....1, and satisfies I-'1 = 1. Squaring I, we obtain 1 = (2102)² 6102c102 1, analogous to the unit imaginary scalar in complex numbers, which is a subalgebra of C
The l norm of a multivector defined as the square root of the sum of the squares of the scalar coefficients of its basis k-vectors. For a multivector M it holds that || M)), where Mt is the reversion of M. Mt is analogous complex conjugation and is defined by three properties: (i) (MN)1 Mt εạε362e and 6302. We define the & norm of multivector as the sum of the absolute values of
(ii) (M + +N² M +tt (iii) M M when M is a vector. For instance, (ε1еge3eл) (c) + e2og)t each component. The definition of inner and wedge products can be naturally extended to multivectors. In particular, the inner-product between two l-vectors M = on A Aox and N = 33 A .... Be is defined by the Gram determinant M A det((as, ;,),,=1).
Hodge dual
A k-blade can be viewed as k-dimensional oriented parallelogram. For each such paralleogram, may associate (d - dimimennia orthogonal complement. This duality between k-vectors and (d - k)-vectors

---

Published in Transactions on Machine Learning Research (10/2024)
is established through the Hodge star operator *, For every pair of k-vectors M,N E Go, there exists a unique (d 18-ki -vvectoor xM e Go with the property that
*MAN NM A Aed
.M.N)L
We may also express the Hodge dual k-vector M as *M = MI where I the inverse the unit pscudoscalar. This lincar transformation from d-vectors to - k vectors defined by M +M is the Hodge star operator. An example in G is Ké1 e II- e1eg62e1 e3e2-
Generalized cross product and wedge products
The usual cross product of two vectors is only defined R3 However, the wedge product can be used define a generalized cross product in any dimension. The generalized cross product in higher dimensions is operation that takes in d - vectors in Rd and outputs vector that is orthogonal to all of these vectors. The generalized cross product of the vectors v1 02, ......, Un-1 can be defined via the Hodge dual of ....AA.. (n-1).. It holds that x(1,, o2,.... 1x-1) .1.; O their wedge product as x (V1, .,,,..,,, 1n-1) - +(mn A A...
for all = 1,..., 1. The signed distance of a vector x to the linear span of a collection of vectors 21, T1.... #d-1 can be expressed via the generalized cross product and wedge products as
*( A ... A xa-1)) xa-1)
(r) ................................ 12-1) 1 A. xd-1ll2
This formulation stems from an intuitive geometric principle: the ratio of the volume of parallelotope to the volume of its base P(=....., Td-11)
P(x, #i....,, #dd1),,fd-1), which is spanned by the vectors the parallelotope formed by -1,..., Td-1 alone. This ratio elfectively captures the height of the parallelotope relative to its base, which corresponds to the distance of æ from the subspace spanned by Ii,..., Id-1- Note that the Hodge dual transforms the d-vector in the numerator into a scalar. We provide a subset of other important properties of the generalized cross product in Section 6.1 of the Appendix.
2.3 Convex duality
Convexity and duality plays a key role in the analysis of optimization problems (Boyd and Vandenberghe, 2004). Here, we show how the convex dual of a non-convex neural network training problem can be used to analyze optimal weights.
Convex duals of neural network problems
The non-conne convex optimization problem has a convex dual formulation derived recent work PPlanni and
Ergen 2020
Ergen and Pilanci 2021a given by
p" 2 d max VER"
Ev. s.t.
(uTo(Xw) & X, Vo e Bd
(5)
where we take the network to be bias-free (see Section 8.2 for biased neurons). Here, (3,z) is the convex - sup vT E(g. y) and Be is the unit p-norm ball in d Moreover, it was shown in Pilanci and Ergen (2200) that when is the ReLU activation, strong duality holds, i.e., p² == d", when the number of neurons m exceeds a critical threshold. The value of this threshold can determined from an optimal solution of the dual problem in 5 This result was extended to deeper ReLU networks in Ergen and Pilanci (2021c) and deep threshold activation networks Ergen lt al. )
conjugate of the loss function ((.,)) defined as E (v. y)
Our main strategy analyze the optimal weights is based analyzing the extreme points of the dual constraint set in 5 In the following section, we present main results.

---

Published in Transactions on Machine Learning Research (10/2024)
3 Theoretical Results
3.1 One-dimensional data
We start with the simplest case where the training data is one-dimensional, i... d and the number of training points, n arbitrary.
Theorem 1. For all values of the regularization norm E [1, 00), the two-layer neural network problem in can be recast as the following & E-rreguarrzed convex optimization problem
min (K= lnt,)) + A||=||1
(6)
#ER
TER
where the entries of the matriz K are given by
Kiz- a (1:-2z))
j n
(7)
(zz-n 11in-21)) 24)+ < $ 2n,
and the number of newrons obey 2 1|="|10- An optimal network can be constructed
f(x) = Σ (z - - mz)+ + Σ 5=1
2ttt - x)+ +t"
(8)
3=1
where 2* and t" are optimizers of 6 Remark. It will be revealed in the following sections that the term (a;; - xy)- present in 7 stands for the wedge product ([+)=+>))
^ 1z [+) yielding the positive part of the signed length of the interval [ mr
Appending 1 to the vectors is due to the presence of bias in the neurons. This quantity can also be seen as a directional distance we denote as dist__ (x;, which will be generalized to higher dimensions in the sequel. As we delve into higher dimensional NN problems, the above wedge product expression will be substituted by the positive part of the signed volume of higher dimensional simplices such as triangles and parallelograms. Remark. This result is a refinement of the linear spline characterization of one-dimensional infinitely wide ReLU NNs (Savarese et al. 2019 Parhi and Nowak 2020). The linear spline dictionary is given by the collection of ramp functions {(x -x;)), (2; x)+ 17 which is well-known in adaptive regression splines [Friedmanl 1991). Our work is the first to recognize this dictionary via wedge products, characterize it as finite dimensional Lasso problem, and associate it to volume forms. This enables us generalize the result to higher dimensions and arbitrarily deep ReLU networks. It is important to note that unlike the existing literature infinite neural networks (Bach 2017 Bengio et al. 2005), our characterization of the dictionaries is discrete rather than continuous, enabling standard convex programming.
An important feature of the optimal network in is that the break points are located only at the training data points. In other words, the prediction f(x) piecewise linear function whose slope only may change at the training points with at most n breakpoints. However, since the optimal =* is sparse, the number of pieces is at most ||,*| and can be smaller than n.
We note that convex programs for deep networks trained for one-dimensional data were considered in Ergen et al. 2022b Zeger et al. 20244). Ergen and Pilanci 2021a), it was shown that the optimal solution may not be unique and may contain break points at locations other than the training data points.
However, Theorem ! reveals that at least one optimal solution in the form of (8). In addition, it is shown that the solution is unique when the bias terms are regularized (Boursicr and Flammarion 2023 and skip connection is included. We discuss uniqueness in Section
3.2 Two-dimensional data
We now consider the case d = 2 and use the two-dimensional geometric algebra G². Interestingly, we will observe that the volume of the interval [ı] appearing above generalizes to the volume of triangle. We
8

---

Published in Transactions on Machine Learning Research (10/2024)
C2
C2
Jjj
2 (Tt - Ini (2
2 A Izj
Vi
61
0
Figure 4: rllustration of the matrix K for neural networks without bias (left) and with bias (right) via the triangular area defined in the convex program from Theorem in R
will observe that the & and 6e-reglarrieed problems exhibit certain differences from one another. We start with the f1-regularized problem 1, since the form of the convex program is simpler to state due to the polyhedral nature of the & norm. In the case of = 2, we require mild regularity condition on the dataset to handle the curvature the lg norm.
3.2.1 ( regularization neurons without biases
For p and d d= 2, the two-layer neural network problem without biases be recast the following conves f1 -regularized oplimization problem
Theorem 2.
min ((2,y) x||=||1- *ER"
(9)
Here, the matria E Rūxā is defined as Kij x(x;, 2z)) where
x'x = (x (x)x))+ (A0,, x,
(10)
|
|
provided that the remmber of newrons satisfy m 2 || Here, (0, Iz)) denotes the triangle formed by the path 0 - v; + Zj: and V-l4(-) denotes the positive part of the signed area of this triangle. An optimal network can be constructed as follows:
f(x) Σ 23)(0, 1=1
where =* is optimal solution to (9] The optimal first layer neurons given by scalar multiple of the generalized cross product, x.y *rjz with breaklines x A 2g- O, corresponding lo non-zero 2] for E [m]]
Remark. The optimal hidden neurons given by the generalized cross products, Xæj, orthogonal to the training data points Iÿ for j 1,..., n. Therefore, the breaklines of each ReLU neuron pass through the origin and some data point Σz. Note that (x A 11)+ = (Z1 - = is a ReLU ridge function.
We provide an illustration the matrix K in Figure 4 The signed area of the triangle formed by the path 0 x, + Mi, denoted by the wedge product foz A is positive when this path is ordered counterclockwise and negative otherwise. In this figure, the positive part of this signed area given by Vol, (A, 1 (z; Axz)+ + is non-zero only when I; is to the right of the line passing through the origin and xz. When bias terms are added to the neurons, the matrix K changes as shown in the right panel of Figure as shown in Theorem (see also Section 8.2 in the Supplementary Material).
3.2.2 lg regularization (weight decay) neurons with biases
Now we show that similar results holds for the & regularization (weight decay) for near-optimal solution, also demonstrate the case with biases. We first quantify near-optimality as follows:

---

Published in Transactions on Machine Learning Research (10/2024)
Definition 1 (Near-optimal solutions). We call a set of parameters that achieve the cost p in the two-layer NN objective 3 cooptmall if
p' 1
(11)
where p" is the global optimal value of and 0. Definition (Range dispersion in R²). We call that two-dimensional dataset is e-dispersed for some E (0, 2) if
00+1 - 0:1 (mod ④) S En Vi [n],
(12)
where Og are the angles of the vector x; with respect to the horizontal axis, i.e,
| cos(O,) sin():)]
sorted in increasing order. We call the dataset locally c-dispersed if the above condition holds for the of differences {zz zy}== for all j E [n].
Range dispersion measures the diversity of the normal planes corresponding the training data. Local dispersion holds when the data centered any training sample dispersed. In the left panel of Figure 5 illustrate the range dispersion condition for two-dimensional dataset.
Theorem 3. Suppose that the training set (zi,...,Z,I is locally e-dispersed. For p 2 and 2, an c-optimal network be found via the following conver optimization problem
min ((K2 1t.0) + A||=111.
(13)
=ER(i)
EE
when the reumber of neurons obey 2 1|=*||o- Here, the matrix K (3) is defived as Kij (( T.) for j (j1r52), where
Ax + Ax" x Ax)
(Vol, x', x'xx,,",x")) dist (z, Aff(2' ('',z"²²)),
a(I,x',2")
| x
| 1 x2112
for j (j) The c-optimal neural network can be constructed
f(x)
Σ 2f Rja); j=(nn())
where 2" is an optimal solution to
13
The optimal hidden neurons and biases are given by scalar multiple respeclively, with breaklines (a (x- ( - -1,)) = 0 for j = (ji, j2)
of -f and * A (T -xn)))
corresponding to non-zero 27.
Remark. We note that the form of the near-optimal NN for p= 2 is near identical to the = 1 case, for which the result exact. This discrepancy is due to the polyhedral nature of the dual problem with & regularization (see Figure of of Appendix IT). Tn Section 4, we present numerical evidence that the decision regions of optimal NNs with and p are near identical for small values of X.
3.3 Arbitrary dimensions
Now we consider the gencric case where d and n are arbitrary and we use the d-dimensional geometric algebra Gd. Suppose that X E gaxd is a training data matrix such that rank(X) = without loss of generality, Otherwise, we can reduce the dimension of the problem to rank(X) using Singular Value Decomposition (see Lemma 23 in the Supplementary Material), hence can be regarded as the rank of the data. Since many datasets encountered in machine learning problems close to low rank, this method can be used to reduce the number of variables in the convex programs we will introduce in this section.
10

---

Published in Transactions on Machine Learning Research (10/2024)
3.3.1 { regularization neurons without biases
Theorem 4. The 2-layer neural network problem in 2 when p and biases set zero is equivalent to the sollowing conver Lasso problem
min E (Kz,)) v) + \||2||1,
(14)
provided that the number of newrons satisfy m 2 110 The matriz K is defined as Ksj = Ro 2/ IJa-1 for j = -aa1)...ja.1, where
x² (T 1 F3c-) Vol. u1, ud-1))
k(x, U1 ud-1)
(15)
x (") ... Fjs lll
x (ui A A Add-i)ll
the multi-inder (f1,..., Ja-1) indezes over all combinations of d rows Ih ... Ija-s Rd of X Radd An optimal neural network can be constructed as follows:
f(z)= =
Σ
27 Bn Iza-1)s
where z" is an optimal solution to 14
The optimal neurons are given by a scalar melltiple of the generalized
cross- product x ;Jja-1) non-zero 23 for j = (Ji.-.. 1d-
(Z A A.. ....AAZja.. AZja-)), with breaklines x A AZj, N A.--AAja- = corresponding
We recall that P(x, U1, ... 1 denotes the parallelotope formed by the vectors F, u1 Ud-11 and the positive part of the signed volume of this parallelotope is given by Vol- (P(s,, W1, ud-1)). Remark. The optimal neurons are orthogonal to data points, i.c., x .. ; I2 = 0 for all E (i,.... Ja..)- Therefore, the hidden ReLU neuron is activated on halfspace defined by the hyperplane that passes through data points Tha"" "
The proof of this theorem can be found in Section 9.2 of the Supplementary Material. Remark. We note that the combinations otherwise the volume is zero and corresponding weights can be set to zero. Moreover, the permutations of the indices Zj. .... IJa-1 may only change the sign of the volume Vol(P(I;, Zj,, .... ))a-)))- Therefore, it is sufficient to consider each subset that contain d - 1 linearly independent data points and compute Vol, (+P (2,, Ihi ... 1)) for each subset. The cost enumerating over all size subsets o())).
be taken over d - 1 linearly independent rows of X since
3.3.2
Eg regularization neurons with biases
We begin by defining a paramcter that sets an upper limit on the diameter of the chambers in the arrangement generated by the rows of the training data matrix X.
Definition 3. We define the Maximum Chamber Diameter, denoted as 2(X), using the following equation:
2(X)= =
max 10 VER" || (inn(X))=)sgu(Xe))
|/w v/|2-
(16)
Here w and v are unit-norm vectors Rd, such that the sign of the inner-produce with the data rows are the same.
We call a dataset e-dispersed if (X) S c, and locally edisppersed when the dataset centered any training sample is dispersed, i.e., 9(X 1n7) S Vj E [n].
Remark. The quantity (XX is a genoralization dimensions, and captures the diversity of the ranges of the hyperplanes whose normals are training points {a.)2_ We prove in Section 3.5 that when the data is randomly generated, e.g. i.i.d. from a Gaussian distribution, the maximun chamber diameter (XX) is bounded by (g)2/4 with probability that approaches exponentially fast. In Lemma g of Section 3.5 show that this implies Gaussian data is e-dispersed and
the 2D range dispersion in Definition 2 to arbitrary
locally e-dispersed when Z e 'dd with high probability.
11

---

Published in Transactions on Machine Learning Research (10/2024)
2+++
B
0++1
A
Eπ
0, +
A'
0. W1
B'
Figure 5: (left) An illustration of the angular dispersion condition. The angle between the span of two consecutive vectors I; and Zi+1 is bounded by em. (right) The maximum chamber diameter of this line arrangement the Euclidean distance between and B, ie., 9(X) ||A B|I.
Theorem 5. Consider the following conver optimization problem
Dx == min { (2,y) + A||2|11-
(17)
The matriz K is defined as Kig- m( 2ig ... Lia 1) for bias-free and Kij Ko (Jiis Thi wn Uis 1) for biased neurons where
(x (nAu) A uaaa)) dist (z, Span(u1: ... ud-1))
<(1,, U1 ... ud-1)
|lu1 A A ua-1ll2
Ko( U1 U1.... Ud) ((x - ud) A (u1 ua) A... (ud-1 - ua)) dist+(1, Aff(u1, ..., d))
(1u ua) A A (ua-1- - ua)
and the multi- inder j (fi,...: is indering over all combinations of d rows Fje Fja-1 E Rdd of X Raxd When the marimum chamber diameter satisfies ((X) S e for bias-free neurons or 9 1n S Vj E [m) for biased neurons, for some E (0, 1), have the following approsimation bounds
1
D" Six
p'
(18)
Sp' SP
1 XR"
(19)
Here, p" is the value of the optimal NN objective sponding weight decay regularization term of an optimal NN. Bias-free and biased networks that achieves the cost px in (2) are
2 (with or without bias terms) and R is the corre-
f(x)= Σ
2zK(0S D(ai)) and f(x)
Σ
StRolThh .. Fsa-s),
(=(finnaa-1)
respectively, where z" is optimal solution to 17
Remark. The above result shows that the convex optimization produces near-optimal solution when the chamber diameter is small, which is expected when the number of data points is large.
3.4 Illustrative Calculations in Geometric Algebra
Here we ralustrate applications of the closed-form geometric algebra expressions R2, Consider a datasel with two training samples of dimension two given by
æ1 [|] E1 e2
and 22
[9]
2e9
12

---

Published in Transactions on Machine Learning Research (10/2024)
{ - (z 2z2))
x322
15
Jaja
2
(a) The area of triangle formed by the points 2, 2n and Ty is given by wedge product.
(b) Distance to affine hull is given by wedge product normalized by Euclidean distance.
Figure 6: Wedge product representation of distance to affine hull (a) and triangular area (b).
Theorem for p 1 implies that optinal neuron corresponding to sample is given by the dual * = æ1 We recall that I = E1e2 ed = e1e2 when d = 2, and I = e2e1. Hence, we have *I = ze2e1 in G². Next, recall that for = 1, we augment the training set with two standard basis vectors R2 and obtain { {ei - E2, 2e1 e1, 62). For each training sample, we calculate these neurons as follows
W1 = +ř = (e1 + e2)e2e1 = eleg + e202e1 = - -e c1 tei = -22 +
-221
and
+ā² = 20geae1 2c1.
We find two additional neurons from the augmented training data points ei and e2 as wa 62 and W4 E1 respectively using the same process. This yields 4 neurons, which are orthogonal to {
Thcorem 2 provides the optimal ReLU network with no biases as
Vol(A ū,))+
f(x) ((TTw;)-as
|
ajj
where {a,) are determined via the Lasso problem arg min, Σ (f(r))))) - as described earlier in
Let us illustrate some variants of this network which has no bias terms and trained with p-regularization where p= 1. For the optimal network with bias terms, we replace the volume terms with Vol(A R,. 3)) This volume term has the loop based expansion
2Vol(A(2, (b,) (x: }32)) A (ī ;,)== x Bj. -I A 3zg A A3
8jz A Jij
=x BJ + T.j A AJz + 3 Ax.
In other words, the volume of the triangle formed by vertices x, شز وز can be expanded the wedge
product of consecutive pairs of vectors taken over the loop + 2 2 This is illustrated in Figure
Ga
Let us now illustrate the role of regularization. For the p-reuularized network with p 2, Theorem 3
implies that we replace the volume terms with
dist(r, Aff(z)) #53)) (x - 2zp2 (I - x2,))
(11) dist (is TTn)
|0
Fj2l12
This is illustrated in Figure 6b The change from the volume the distance affine hull is a consequence
of the division by ||, 222l22 which is the length of the base (the line segment Aff 252)) of the triangle Aax t ).
13

---

Published in Transactions on Machine Learning Research (10/2024)
3.5 Data isometry and chamber diameter
Results from high dimensional probability can be used to establish bounds on the chamber diameter of a hyperplane arrangement generated by a random collection of training points. similar analysis was considered in Plan and Vershynin (2014) for the purpose of dimension reduction. We first show that the chamber diameter is small when the training dataset satisfies isometry condition.
Lemma 6 (Isometry implies small chamber diameter). Suppose that the following condition holds
(1 - (lwollull2 [1llll S (1 + c)]lu|12. Vw E TR
(20)
where a E R is fized. Then, the chamber diameter ( defined in 16 is bounded by 4VC.
Next, we show that the isometry condition satisfied when the training dataset generated from random distribution. Consequently, we obtain bound on the chamber diameter of the hyperplane arrangement generated by the random dataset.
Lemma (Random datasets have small chamber diameter). Suppose that I1,-- In NOO, Ia) are n random vectors sampled from the standard d-dimensional multivariate normal distribution and let X = [r ,rn]² Then, the lz diameter (X) satisfies
d 1/4
(X) S
(21)
with probability at least 1 2e/
Remark. We note that the constant 9 in the above lemma can be improved to 1 by using the more re- fined analysis due to Gordon GGordon 1985). Moreover, the result can be extended to sub-Gaussian data distributions. However, we use Lemma since it is simpler and suffices for our purposes.
~N Ta) random vectors sampled from the standard d-dimensional multivariate normal distribution and let X [x ,In]" Suppose that n Z A_Ad. Then, the dataset X is e-dispersed, i.e., 9(X) S E and locally e-dispersed, i.e., ( 1x75) S e Vj E [n] with high probability.
Lemma (Random datasets dispersed and locally dispersed). Suppose that 21,... In ;n
3.5.1 Dvoretzky's Theorem
In this section, we present connection to Dvoretzky's theorem Dvoretzkyy 1959 a fundamental result in functional analysis and high-dimensional convex geomelry [Vershynin] 2011
Theorem 9 (Dvoretzky's Theorem). (Geometric version) Let be a symmetric convex body in R For any 0, there cxisls intersection Cs - C of C by subspace C Rh of dimension k(n,e) + such that
(1-c)B² S Cs S (1++))
where B2 is the n-dimensional Euclidean unit ball.
The above shows that there exists a k-dimensionall lincar subspace such that the interscction of the convex body C with this subspace is approximalely spherical; that is, is contained in ball of radius e and contains ball of radius 1 c
If we represent the lincar subspace in Theorem g via the range of the matrix X and let C be the & ball, it is straightforward to show that Dvoretzky's ' theorem reduces to the isometry condition (6) to a scalar normalization. Therefore, the isometry condition ( can be interpreted as condition to guarantee that the & ball is near-spherical when restricted to the range of the training data matrix.
3.6 Deep neural networks
Consider the deep neural network of L layers composed of sequential two-layer blocks considered Section 2.1 as follows
fo(x) = w(4) (()) ( a (w())... w(1)). ..(().
14

---

p² A min {(fo(X).v) + Σ | Published in Transactions on Machine Learning Research (10/2024)
4 to three-layer ReLU networks and derive their corre- sponding convex Lasso formulation over a larger discrete wedge product dictionary. We first illustrate that our results apply to noural networks of arbitrary depth.
Theorems 12 and 13 in this section extend Theorem
3.6.1 Ep regularization
Suppose that the number of layers, L, is even and consider the non-convex training problem
1/2 m
p² A min (fo(())))) +
W (26-1)
1| + 11 (20 12
(22)
E=
where E Raxd is the training data matrix, y R" a vector containing the training labels, and À > is the regularization parameter. Here, S(X) represents the output. of the deep NN over the training data matrix X given by fe(X) taken over the columns of odd layer weight matrices and rows of even weight matrices, which is consistent with the two-layer network objective in 2 When 2, the regularization term is the squared Frobenius norm of the weight matrices which reduces to the standard weight decay regularization term. We assume that the number of neurons in each layer is sufficiently large to meet the conditions required for applying Theorem two consecutive layers.
Note that the Ep norms in the regularization terms are
Theorem 10 (Structure of the optimal weights for & regularization). The weights of an optimal solution of 22 for p 1 are given by
w =a (x,m) A Az,m) ) and
w/O =a
19 (7
(1) ) for 8= =355,... L. 1=1
(23)
where dj are scalar weights and { a( o.) Here, W( are optimal weights of the l-th layer for the problem 22 and (t) e [n] are certain indices.
(1)
3.6.2 l2 regularization
Consider the training problem
with p 2, which simplifics
(24)
8
Theorem 11 (Structure of the optimal weights for l regularization). Consider an approrimation of the optimal solution of (4 given by
(1) w ajj (x A Ax,m)
and
w/o aj n1
(9) (f A x 10: ) for l. = 2,3, ...,,,,
(25)
where aj are scalar weights, 2!00 A (W (()) and 1(0 E [n] are certain indices. The above weights provide the same loss the optimal solution of (24 Moreover, the regularization term is only factor 2/(1-6 larger than the optimal regularization term, where is an uppper-bound on the chamber
(E)
diameters ((X)) for é= L.., - 2. Here, X = ao..--o-X11... (XW())).. W(e-1)) are the f-th layer activations
of the network given by the weights 25
3.6.3 Interpretation of the optimal weights
A fully transparent interpretation of how deep networks build representations be given using results. We have shown that each optimal neuron followed by ReLU activation measures the positive distance of an
15

---

Published in Transactions on Machine Learning Research (10/2024)
C2
62
C1
(a) Two-layer network with- (b) Three-layer network (c) Two-layer network with (d) Three-layer network out biases
without biases
biases
with biases
Figure 7: Optimal space partitioning of two-layer and three-layer ReLU networks predicted by Theorems 4
and 13 for = 1. The blue lines represent the breaklines of optimal neurons. The red dots represent the training data points. Theorem 13 is provided in Section 3.6
input sample to the linear span (or affine hull, in the presence bias terms) generated by a unique subset of training points using the formula
(a * (z)z A... A...A dist (z, Span T))-))).
The ReLU activation serves as crucial orientation determinant in this context. By nullifying negative signed distances, it effectively establishes a directionality in the space. Geometrically speaking, it delineates the specific side of the affine hull relevant for particular input sample. In intermediate layers, the formula is applied to the activations of the previous layer, which are themselves signed distances to affine hulls of subsets of training data.
Since each layer of the network consists a number of neurons, the activations of the network transforms the input data into series of distances to these unique affine hulls as
dist (a,, Span(r, (o: 2 ))).))...... .... dist. (r. Span(r (ppan(r,m)) (m); I [)]]
Moreover, the information encapsulated within the weights of the network be succinctly represented by the indices _( , ...... ((()) "..,)"(((( These indices highlight the pivotal training samples that effectively determine the geometric orientation of each neuron. The formula essentially implics that the deep
neural network's behavior and decisions are intrinsically tied to specific subsets of the training data, denoted
by these critical indices.
This interpretation not only offers geometric perspective on neural networks but also explains the pivotal role hidden layers play. Each hidden layer is a series of coordinate transformations, represented by the alfine hulls of various data point subsets. As the data progresses through the network, gets transformed and re-encoded, with every neuron contributing to this transformation based on its unique geometric connection the training dataset.
3.6.4 Three-layer networks with bias-free first layer
We first consider the case when the first layer neurons W are size x Vj E [m] for some arbitrary d, and the first layer neurons are bias free, i.e. 88' = OVj [m]. We have the following theorem.
Theorem 12. The three-layer neural network problem when p 1, w:S") gdx1 (0x116f)) OVj [m], set to zero is equivolent to the following conver Lasso problem
min ((<(() 21 k(2) + 1,b. v) + A||2112-
(26)
2,
16

---

Published in Transactions on Machine Learning Research (10/2024)
The matrices KO) and K( are given by
(Z A A x (1 A Ezz A ... A x))
(27)
10 A A Tje 1ll1
Bjs by B3(-1))) Vol+ (P(a., 8is .. Boa-1)) - Vol+(P(I
(28)
|8 A A N8
and
(Vol+ (P( Ty .., 33)-))) Vol
(P(2i, Tyes ay tza-)))
k(2)
(29)
| A A Tza-1 l11
where == (jo. ja- -.-
The mulli-inder (f - ja-1) indezes all combinalions of d veclors from the
set {(z,)==1 (4; - æÿ -= (er 1 and jo E [n]. Each optimal first layer newron weight w E Rd satisfy
equalities of the form
x w (x; 22)) T w
(30)
(31)
of w = 0.
(32)
for a certain set of i,j [n], k [d]. An optimal network can be constructed as follows:
(1 ( A ... Aāi .)4 - (1 A ATg A A A 1)+
f(x) = Σ ş
(33)
|5 A A 83a-1112
(335 AJj i A Aājo 1)+ (x A... A Agu 14))+
+ Σ
222
(34)
| .... A Aza-illi
where z" an optimal solution
26
Remark. In addition the optimal neurons for the two-layer case (Theorem here we obtain additional neurons orthogonal to subset of the data points and their pairwise differences. See Figure 7 for an illustration.
3.6.5 Three-layer networks with biased neurons
We now consider the case when the first layer neurons w(l) are size d x 1 Vj E [m] for some arbitrary dimension d, and the all the three layers contain trainable bias terms. We have the following theorem.
Theorem 13. Consider the three-layer neural network problem when p and w("h) gaxl Vj E [m]. Each optimal first layer neuron weaght-bias pair (w. b) E Rd R satisfy equalities of the form
(x; TT w 0
(35)
(x, ) _ ww 0 ex w
(36)
(37)
o +w 0,
(38)
for certain set of i,j,e E [n], ke [d].
Remark. In addition to the optimal neurons for the two-layer case (Theorem 16 here obtain additional neurons whose breaklines are (ranslations of the alline hull of subset of the data points to certain other data points. See Figure d(d) for an illustration.
Remark. We note that the optimization problem and optimal networks take similar form as in Theorem 12 except that the 24 are replaced by and the bias term b = -a w is added.
17

---

Published in Transactions on Machine Learning Research (10/2024)
3.7 Space partitioning of optimal deep networks
We now illustrate the optimal two-layer neurons predicted by Theorems 4 and compare them with optimal
three-layer neurons (see Theorems 13 12 in the Section 3.6 as regularization tends to zero for unless stated otherwise. Consider the two-dimensional training data {क1 = (1,0), 12 (0, 10.1).23 23 = (-1,
(0,-1)) shown in Figure
In panel (a), consider two-layer ReLU network without biases. Two optimal neurons are (wf x)
(wffx) given by Theorem 2 Their breaklines, w x = 0 and wy = 0, are plotted as blue lines, and pass through the origin and data points, since the optimal neurons are scalar multiples of the Hodge duals of 1-blades formed by data points.
In panel (b), we consider a three-layer ReLU network without biases, and we display all four optimal first layer neurons given by Theorem 12 In addition the neurons with breaklines wi and wh a O, we also have wp x and w a which are translations of the affine hulls, (2) and Aff Aff(22,03) vz), the origin.
In panel (c), we consider two-layer ReLU network with biases regularized with p p= 2, and we display all six optimal neurons given by Theorem Their breaklines pass between each pair of samples, since the optimal neurons are scalar multiples the Hodge duals of 1-blades formed by the differences of data points.
In panel (d), we consider a three-layer ReLU network with biases, and we display all 12 optimal first layer neurons given by Theorem [3 In addition to the breaklines that pass between each pair of samples, we also have translations of all possible affine combinations of size two, e.g., Af) Af, to every data point.
3.8 Vector-output Neural Networks
Consider the vector-output neural network problem in 12 given by
p min WOO
Σ 1=1
(xw + 1b,)w/ y) + I || || 13
(39)
J=1
Here, the matrix Y ga contains the c-dimensional training labels, and (11) E mddm W(2) e mxe and E R" are trainable weights. We have the following extension of the convex progam 14 for vector-output neural networks.
P. A min (KKZY)) + A Σ 1|
(40)
ZEROXO
where Zz is the j-th column of the matrix z. Theorem 14. Define the matriz K as follows
(IgAI 1)
Kig
| ... Ais-illo l1
where the multi-inder' j (ji.....aa)) over all combinations of rows and rank(X). holds that
when 1, the convex problem 40 is equivalent to the non-comuez problem 39 i.e., P. Pe.
when 2, the conver problem
40 is - approzimation of the non-convez problem
39 i.e.,
1 < p. < --v where E (0,
an upper-bound the maximum chamber diameter 9 (X).
An neural network achieving the above approrimation bound can be constructed as follows:
f(x) = Σ 23 (z; A Aij A... A A ,)+
(41)
||05 A Adjaa llp
where Z" is optimal solution to 40
18

---

Published in Transactions on Machine Learning Research (10/2024)
4 Numerical Results
In this section, we introduce and examine a numerical procedure to take advantage of the closed- form formulas in refining neural network parameters and producing a geometrically interpretable network.
4.1 Refining neural network weights via geometric algebra
We apply the characterization of Theorem | which states that the hidden neurons are scalar multiples of {z), A ... A Ija-)), Additionally, they are orthogonal to the r - training data points specified by " ....,,a,, 3js-1, where r represents the rank of the training data matrix.
The inherent challenge lies in identifying the specific subset of the r r- training points needed to form each neuron. Fortunately, this subset can be estimated when we have access to approximate neuron weights, typically acquired using standard non-convex heuristics such as stochastic gradient descent (SGD) or variants such as Adam and AdamW (Kingma and Ba 2014 Loshchilov and Hutter 2018). After obtaining an approximate weight vector for each neuron, we can gauge which subsets of training data nearly orthogonal to the neuron. This is achieved by evaluating the inner- -nnrrpproducts between the neuron weight and all training vectors, subsequently selecting the r r- entries of the smallest magnitude. This refinement, which we term the polishing process, is delineated as follows for each neuron W1...., Wm:
For each j E [m]] (optional: Append 1 to the training samples to account for the neuron bias term)
1. Calculate the inner-product magnitudes: |z] uyl for each i E [m].
2. Identify the r training vectors with the minimal inner-product magnitude, denoted as "h -aa--"
As a result, we have my 1. Thr--..; ----1 This can be done by solving the linear system w Ry = 0 for i i= 1, 1, finding a minimal left singular vector of the matrix [Zf I. and normalizing wy such that ||w,||p
Update the neuron using: Wy (x A Iza-)) =
4. Optimize the weights of the following layer(s).
5. Optimize the scaling factors between consecutive layers (see Supplementary Material 9.13.1|
As a result, each neuron is assigned a closed-form symbolic expression, which only depends on a small subset of training samples.
4.1.1 Computational complexity of polishing
For a dataset of n samples of dimension d, the cost of applying the polishing process to a layer of m neurons is given by O(mnd) + (mmd")) where w is the matrix multiplication exponent, e.g., y = using classical solvers (Gloub and Van Loan 1996) and w S 2.376 using fast matrix multiplication. We note that the latter class of algorithms are not practical for realistic sizes. However, O(md") can be reduced to O(FFmdd log(1/e)) for e-approximate solutions of the linear system, where is the condition mumber. The computational cost is dominated by the calculation of inner products (O(mnd)) for large and the d x d linear system solve (O(md")) for large d.
4.1.2 Toy spiral dataset
Figure g for the 2D spiral dataset and two-layer neural network optimized with squared loss. In the initial panel of this figure, the training curve of a two-layer ReLU neural network from (2) is depicted, considering p = 2 and weight decay regularization set at 3 = 10-5, The datasct, divided into two classcs represented by blue and red crosses, is showcased in the second panel. By resorting to the dual formulation in (5). the global optimum value is computed. Notably, while SGD far from the global optimum, the polishing process enhances the neurons, leading marked improvement in the objective value evidenced by the solid line in the left panel. A comparative visualization of the decision region pre and post-polishing is presented in the subsequent panels, highlighting the enhanced data distribution fit due to the polishing.
19

---

Published in Transactions on Machine Learning Research (10/2024)
Pg Dopsot
Decidion Regien
Vedifed Aagian
109
1.0
1.0
Fot ched
174
160
027
10'
4250
3000
10000
12000
24000
-10
000
19
-05
05
-05
000
10
Figure 8: Comparison of SGD and polishing via goometric algebra in the spiral datasct.
Accuracy karning rase
Training Perplexity
Thain
Test
Test Poliseed
Parplaatty
800000
3.86
Wilselann Accrnsoy Orggnz Wiliadon Acouaayy
2.84
Acoraco Original
0:200
0
1000
2000
3000
4000
5000
6000
7000
8000
Number meurons
(a) 4-layer convolutional neural network
(b) 2-layer autoregressive language model
Comparison of AdamW and polishing CIFAR image classification (a) character-level MLP trained small subset of Wikipedia (b). Section 7.1 in the Supplementary Material contains additional numerical results, including a comprehensive hyperparameter search.
Figure 9:
4.1.3 Real datasets
To illustrate the polishing strategy, we present three examples in Figures and Figure 10
In Figure g (a); we investigate binary image classification on the CIFAR dataset (Krizhevsky and Hinton 2009). A four-layer convolutional network composed of two convolutional layers with 3 x 3 x 32 filters and two fully connected layers with 512 hidden neurons trained to distinguish class 0 (airplane) from class 2 (bird). We train it via AdamW optimizer using default hyperparamcters and varying learning rate using 20 epochs and batch size of 2048. After training, implement the proposed polishing process on the first layer weights. Next, we re-train the second-layer weights while first layer weights are fixed via convex optimization. The resulting average train/vali vrainvvalidttion accuracies are plotted over 5 independent trials to account for the randomness in optimization. We observe that the polishing process improves both the training and Lest accuracy. In Section 7.1 we provide additional results with different hyperparameters.
In Figure 9 (b), repeat the same polishing strategy for small tharacter-based autoregressive language model. We train two-layer ReLU network to predict the next character in sequence of characters from small subset. of Wikipedia consisting of first 650000 characters from the article titled 'Neural network (machine learning)' and other articles linked from the same page. We use the AdamW optimizer with a learning rate of 10-4 and a batch size of 8192. The block size is set to 16 characters. We apply polishing to the first layer weights. Next, we re-optimize the final layer weights while the first layer weights are fixed via convex optimization. The resulting average train/valicn vaalidatin accuracies, along with 1-standard deviation error bars, are plotted over independent trials account for the randomness in optimization. We observe a significant improvement in perplexity after polishing when the number of neurons is large enough. In Section 7.1 5, we provide additional results with different hyperparameters.
20

---

Published in Transactions on Machine Learning Research (10/2024)
Validati on
Validati polished
Train
Norma lized inner product product magnitude
Train polished
10-1
Traln/validation MSE
10:
10
allest inner-product
random neuron
largest inner-preduct neuron
200
300
400
500
600
700
800
900
1000
100
150
200
250
300
350
400
Number neurons
Training data Index
(a) AdamW and polishing train/valldaation errors
(b) Distribution of inner-produc magnitudes
Figure 10: AdamW and polishing via geometric algebra in the Boston Housing dataset.
In Figure 10 we demonstrate the polishing strategy applied within a tabular learning context using the Boston Housing dataset. This dataset consists of 506 samples, each with 13 features representing various attributes of housing in Boston. We use a two-layer neural network with varying number of hidden neurons in the first layer, trained to predict the median value of owner-occupied homes. The network trained using the AdamW optimizer with learning rate of 10-2 and batch size of 16 over 100 epochs. After training, we apply the proposed polishing process to the first layer, followed by re-oplimixing the second- layer weights. The resulting train and validation MSE as well as one standard devation error bars are plotted over 100 independent trials to account for the randomness in optimization. As shown in Figure 10 (a), the polishing process consistently results in improved performance when the number of neurons are sufficiently large, similar to previous cases, demonstrating its robustness across different types of datasets. In Figure 10 (b), we present the distribution of the magnitude of inner-products between the weight vectors of the HtamW-trained first layer before polishing. This plot shows that many inner products are small, the order of 10-2 to 10-3, when the vectors are normalized to have unit. Fuclidean norm. In Figure 39 in Section 7.6 of the Appendix, worse compared to the polishing process. The work Adlam et al. (2020) reports the validation accuracy of kernel ridge regression, NN ensembles and Bayesian NNs,, which all underperform compared to our approach. In the Supplementary Material (Section 7.1 we provide detailed analysis of the effect of changing the hyperparameters and optimizers, including the learning rate, momentum parameters (8, and B8 Adam and AdamW), batch sizes, number of epochs, and also present additional results with fully connected norksrks and other binary classification tasks. We observe that the polishing process consistently improves the quality of the weights, lcading to significant improvement in the accuracy of the network while making the neurons fully interpretable as oriented distance functions via geometric algebra.
present additional plots for traditional methods, showing that they perform
4.2 Comparison of f2 and & regularized neural networks
Tn this section we compare the predictions of optimal neural networks with p-regularized neurons, specifically focusing on = 2 and = 1. In Figure [ we compare the optimal decision boundaries of & and fz regularized NNs on the XOR dataset with n = 4 samples by solving the dual convex problem in (6) can be seen that both models yield the same decision region. Moreover, two distinet breaklines of optimal neurons are plotted. These can be identified the affine hulls of subset of training points.
In Figure 12 compare & and lg regularized neural networks the spiral dataset across varying levels of regularization strength X by solving the convex Lasso formulations. It can be observed that the optimal
21

---

Published in Transactions on Machine Learning Research (10/2024))
norm (p-1),
Ragurarization (p-2),
1.00
posthre decls rog
1.0
the decision region
decition
samples
campie
reigetio surplees
megadiie sumples
0.76
Dessiciin inss
075
breakinus
0.50
0.00
0.50
0.0
-0.76
-075
-1.00
-1.0
-1.00
-0.76
0.25
0.50
-1.00
-0.75
0.26
(a) p p=
(b)
Figure 11: Comparison of & and & regularized neural networks on the XOR dataset. The breaklines of the optimal neurons are shown as dashed lines, representing the affine hulls Aff ([]),,[) and Aff (+=)) which pass through a subset of the training data points.
decision regions differ for large values of X, whereas they become nearly identical for small values of X. This is expected since with small X, the network is forced to interpolate the data points regardless of the type of the regularization norm.
5 Discussion
In this work, we have presented an analysis that uncovers a deep connection between Clifford's geometric algebra and optimal ReLU neural networks. By demonstrating that optimal weights of such networks are intrinsically tied to the wedge product of training samples, our results enable an understanding of how neural networks build representations as explicit functions of the training data points. Moreover, these closed-form functions not only provide theoretical lens to undersland neural networks, but also has the potential to guide new architectures and training algorithms that directly harness these geometric insights.
Computational complexity of global optimization
The computational complexity the polishing process dominated by step 3, which involves solving a linear system or finding a minimal left singular vector. This can done in O(n2r) time using the QR decomposition or the SVD. This process is repeated for each neuron, resulting O(nrrm), where is the number of neurons. In contrast, the complexity of training the neural network global optimal using the convex programs derived in Theorems 4 is O((")n), which is tractable for small Note that for convolutional neural nelworks, the rank is bounded by the spatial size of the filter, which is a small constant (Ergen and Pilanci 2024 Another application where the data is inherently low rank is Noural Radiance Fields (Mildenhall et al. 2021). The exponential complexity in r can not be improved unless P = NP (Pilanci and Ergen 2020 Wang and Pilanci 2023). However, the convex programs can well-approximated by sampling the wedge products, in a similar manner to the randomized sampling employed in convex formulations of NNs (Ergen and Pilanci 2024 2023 Mishkin et al. (2022). Recent work showed that random sampling of polynomially many variables in the convex program (5) provides strong
total complexity of
approximation with only logarithmic gap to the global optimum (Kim and Pilanci 2024 Another work
22

---

Published in Transactions on Machine Learning Research (10/2024)
Regularization with norm (p=1), A=0.01 25 neurons
Regularization with f2 norm (p=2), A=0.01, 10 neurons
1,00
positive decision region
1.00
posilive decision region
negative decision region
negalive decision region
0.75
0.75
samp
negalive samples
0.50
0.50
0.25
0.25
0.00
0.00
0.75
0.75
11.0
-1.00
-1.00
-0.75
-0.50
-0.25
0.00
0.25
0.50
0.75
1.00
-1.00
-0.75
-0.50
-0.25
0.00
0.25
0.50
0.75
1.00
(a) p and x
10-
(a)
and À 10
Regularization with norm (p=1), A= 00000011 neurons
Regularizatio 22 norm (n=2), A=0.000 neurons
1.00
positive decision region
1.00
positive decision region
negative region
negalive region
0.75
posilive samples
0.75
pos
negaliiee samples
nega live samples
0.50
0.50
0.25
0.25
0.00
0,30
-0.25
-0.25
-3.50
-3.50
1.00
1.00
(a) p = and A = 10
(a) = 2 and A = 10
Figure 12:
Comparison of & and &2 regularized neural networks on the spiral datasel. Note that the optimal decision boundaries are different for large values of but become very similar for small values of
Wang et al. 2024 int randomized algorithms for geometric algebra, which is a promising direction to make progress in this area.
Interpretability
Our findings also contribute to the broader challenge of neural network interpretability. The polish- ing process is expected to improve the quality of the weights, leading to a significant improvement in the accuracy of the network while making the nourons fully interpretable as oriented distance functions via geometric algebra. More precisely, after polishing each ReLU neuron precisely outputs (xf (oTw)+ = dist (ar,, Span(s),
=.)-))). This representation similar to that of Support Vector Machines, where the model is defined by weighted combination of training samples. By elucidating the roles hidden layers play in encoding geometric information of training data points through signed volumes, we have taken step towards more transparent and foundational theory of deep learning.
23

---

Published in Transactions on Machine Learning Research (10/2024)
Uniqueness
We note that the optimal weights of a ReLU neural network are not unique, and permutation, merging and splitting operations on the neurons can lead to equivalent networks. However, all globally optimal solutions can be recovered via the set of optimal solutions of the convex program (5) by considering these
three operations (Mishkin and Pilanci 2023 Wang al. 2021). Moreover, under certain assumptions, the convex program for univariate data admits unique solution (Boursier and Flammarion 2023). In addition, all stationary points of the non-convex training objective can be recovered via the convex program when cerlain variables are constrained to be zero (Wang el al. 2021), up to permutation, merging and splitting, An important open question is characterizig the entire optimal set of the convex programs via geometric algebra, which we leave as future work.
Other architectures
Our findings can be extended to several other widely used network architectures. For instance, convolutional neural networks can be transformed into fully connected networks by reshuflling the data matrix, as shown in Ergen and Pilanci (2021d). Some of our results can be directly applied by redefining the training data vectors. This can be extended to deep CNNs with short receptive fields (Brendel and Bethge 2019). For other generic CNNs, the results can be extended by employing the same approach. Additionally, that our results be extended to transformer architectures employing linear ReLU attention, as convex formulations of these networks have been analyzed in Sahiner et al. (2022). Further results for various other neural network architectures are provided in Section of the Appendix.
believe
There are many other open questions for further research. Exploring how these insights apply to state-of-the- art network architectures, or in the context different regularization techniques and variations of activation functions, such as the ones in attention layers, could be of significant interest. While our techniques allow for the interpretation of layer weights in popular pretrained network models, we leave this for further research. Additionally, practical implications of our results, including potential improvements the polishing process remain to be fully explored. Our results also underlines the potential and utility of integrating geometric algebra into the theory of deep learning.
References
Alex Krizhevsky, Πla Sutskever, and Geoffrey E, Hinton. Imagenet classification with deep convolutional neural networks. Advances in newral information processing systems, 25, 2012.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521 (7553) (3755))43344444 436-444, 2015.
R. OpenAL. Gpt-4 technical report. arXiv,, pages
2023.
Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40):24632 24662,, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural langent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in neural information processing systems, 32, 2019.
Adityanarayanan Radhakrishnan, Mikhail Belkin, and Caroline Uhler. Wide and deep neural net- works achieve consistency for classification. Proceedings of the National Academy of Sciences, 120(14): e2208779120, 2023.
Yoshua Bengio, Nicolas Roux, Pascal Vincent, Olivier Delallean, and Patrice Marcotte. Convex neural networks. Advances in neural information processing systems, 18, 2005.
Francis Bach. Breaking the curse of dimensionality with convex neural networks Journal of Machine Learning Research, 18(19):1-53, 2017.
24

---

Published in Transactions on Machine Learning Research (10/2024)
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. Advances in neural information processing systems, 32, 2019.
Stephen D Fisher and Joseph W Jerome. Spline solutions to 11 extremal problems in and several variables. Journal of Approcimation Theory, 13(1):73--8) 1975.
Enno Mammen and Sara Van De Geer. Locally adaptive regression splines. The Annals of Statistics, 25(1): 387-413, 1997.
Randall Balestriero et al. A spline theory of deep learning. In International Conference on Machine Learning. pages 374 383. PMLR, 2018.
Jason M Klusowski and Andrew R Barron. Approximation by combinations relu and squared relu ridge functions with 11 and 10 controls. IEEE Trensactions on Information Theory, 64(12))7649-7656 2018.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667 2690. PMLR, 2019.
Rahul Parhi and Robert D Nowak. Banach space representer theorems for neural networks and ridge splines. Journal of Machine Learning Research, 22(43):1 40, 2021.
Rahul Parhi and Robert D Nowak. What kinds of functions do deep neural networks learn? insights from variational spline theory. SIAM Journal on Mathematics of Data Science, 4(2):464-449, 2022.
Francesca Bartolucei, Ernesto De Vito, Lorenzo Rosasco, and Stefano Vigogna. Understanding neural net- works with reproducing kernel banach spaces. Applied and Computational Harmonic Analysis, 62:194-20 236, 2023.
Michael Unser. A representer theorem for deep neural networks. Journal of Machine Learning Research, 20 (110):1-30, 2019.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. In International Conference on Machine Learning, pages 7695-7705. PMLR, 2020.
Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterized neural networks. The Journal of Machine Learning Research, 22(1):9646 9708, 2021a.
Burak Bartan and Mert Pilanci. Training quantized neural networks to global optimality via semidefinite programming. International Conference on Machine Learning, pages 694 704. PMLR, 2021a.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In International Conference on Machine Learning, pages 3004-3014. PMLR, 2021b.
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks via convex programs. In International Conference on Machine Learning, pages 2993 30-3000. PMLR, 2021c
Yifei Wang and Mert Pilanci. The convex geometry of backpropagation: Neural network gradient flows converge to extreme points of the dual convex program. In International Conference on Learning Repre- sentations, 2022.
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.
Tolga Ergen, Arda Sahiner, Batu Ozturkler, John Panly, Morteza Mardani, and Mert Pilanci. Demystifying batch normalization in relu networks: Equivalent convex optimization models and implicit regularization. International Conference on Learning Representations, 2022a.
Jonathan Lacotte and Mert Pilanci. All local minima are global for two-layer relu neural networks: The hidden convex optimization landscape. arXiv e-prints, 2020.
25

---

Published in Transactions on Machine Learning Research (10/2024)
Burak Bartan and Mert Pilanci. Neural spectrahedra and semidefinite lifts: Global convex optimization of polynomial activation neural networks in fully polynomial-ime. arXiv preprint arXiv:2101.02429 2021b.
Shan Carter, Zan Armstrong, Ludwig Schubert, Tan Johnson, and Chris Olah. Activation atlas. Distall, 4 (3):e15 2019.
David H Hubel and Torsten N Wiesel. Receptive fields and functional architecture monkey striate cortex. The Journal of physiology. 195(1):215-248, 1968.
Laura O' O'Mahony, Vincent Andrearczyk, Hemning Müller, and Mara Graziani. Disentangling neuron repre- sentations with concopt vectors. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pullern Recognition, pages 3769 3774, 2023.
Emil Artin. Geomelric algebra. Courier Dover Publications, 2016.
Chris Doran and Anthony Lasenby. Geometric algebra for physicists. Cambridge University Press, 2003.
Lco Dorst, Chris Doran, and Joan Lasenby. Applications of geometric algebra in computer science and engineering. Springer Science & Business Media, 2012.
Stephen P Boyd and Lieven Vandenberghe. Conver optimization. Cambridge university press, 2004.
Tolga Ergen, Halil Ibrahim Gulluk, Jonathan Lacotte, and Mert Pilanci. Globally optimal training of neural networks with threshold activation functions. In The Eleventh International Conference on Learning Representations, 2022b.
Rahul Parhi and Robert D Nowak. The role of neural network activation functions. IEEE Signal Processing Letters, 97:1779-1783 2020.
Jerome H Friedman. Multivariate adaptive regression splines. The annals of statistics, 19(1):1-61 67, 1991.
Emi Zeger, Yifei Wang, Aaron Mishkin, Tolga Ergen, Emmanuel Candès, and Mert Pilanci. A library of mirrors: Deep neural nets low dimensions are convex lasso models with reflection features. arXiv preprint arXiv:2403.0100 01046, 2024.
Etienne Boursier and Nicolas Flammarion. Penalising the biases in norm regularisation enforces sparsity. Advances in Newral Information Processing Systems, 36:57795-57824, 2023.
Yaniv Plan and Roman Vershynin. Dimension reduction by random hyperplane tessellations. Discrele & Computational Geometry, 51(2):438-400 461, 2014.
Yehoram Gordon. Some inequalities for gaussian processes and applications. Israel Journal of Mathematics, 50:265-2899 289, 1985.
Aryeh Dvoretzky. theorem on convex bodies and applications to banach spaces. Proceedings of the National Academy of Sciences, 45(2):223-22) 226, 1959.
Roman Vershynin. Lectures in geometric functional analysis. Unpublished manuscript. Avoilable at http:///www-persondd. umich. edth/oomann/ppprrs//FFAaaa Saae///FA-booo.o../. GFFA-book. pdf, 3(3):3 3, 2011.
Dicderik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference Learning Representations, 2014.
llya Loshchilov and Frank Hutter. Decoupled weight decay regularization. International Conference on Learning Representations, 2018.
Gene H Gloub and Charles F Van Loan. Matrix computations. Johns Hopkins Universtiy Press, 3rd edtion. 1996.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Master's thesis, University of Toronto, ON, Canada, 2009.
26

---

Published in Transactions on Machine Learning Research (10/2024)
Ben Adlam, Jachoon Lee, Lechao Xiao, Jeffrey Pennington, and Jasper Snoek. Exploring the uncertainty properties of neural networks' implicit priors in the infinite-width limit. arXiv preprint 0rXim22010.07555 2020.
Tolga Ergen and Mert Pilanci. Path regularization: convexity and sparsity inducing regularization for parallel rehu networks. Advances in Neurol Information Processing Systems, 36, 2024.
Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng. Nerf: Representing scenes neural radiance fields for view synthesis. Communications of the ACM, 65(1):99-106, 2021.
Yilei Wang and Mert Pilanci. Polynomial-time solutions for relu network training: A complexity classification via max-cut and zonotopes. arXie preprint arXiw:2311.1097? 2023.
Tolga Ergen and Mert Pilanci. The convex landscape of neural networks: Characterizing global optima and stationary points via lasso models. arXiv preprint 2iv:22312 12657, 2023.
Aaron Mishkin, Arda Sahiner, and Mert Pilanci. Fast convex optimization for two-layer relu networks: Equivalent model classes and cone decompositions. In International Conference on Machine Learning, pages 15770 15816. PMLR, 2022.
Sungyoon Kim and Mert Pilanci. Convex relaxations of relu neural networks approximate global optima in polynomial time. arXiv preprint arXic:2402.03625 2024.
Yifei Wang, Sungyoon Kim, Paul Chu, Indu Subramaniam, and Mert Pilanci. Randomized geometric algebra methods for convex neural networks. arXiv preprint arXiv:2406. 02806, 2024.
Aaron Mishkin and Mert Pilanci. Optimal sets and solution paths of relu networks. In International Conference on Machine Learning, pages 24888 24924. PMLR, 2023.
Tolga Ergen and Mert Pilanci. Implicit, convex regularizers of cnn archilectures: Convex optimization of 2- and 3-layer networks in polytime. International Conference on Learning Representations, 2021d.
Wieland Brendel and Matthias Bethge. Approximating cmns with bag-of-local-featurrs models works sur- prisingly well on imagenet. arXiv preprint arXiv:1904.00760, 2019.
Arda Sahiner, Tolga Ergen, Batu Osturkler, John Pauly, Morteza Mardani, and Mert Pilanci. Unravel- ing attention via convex duality: Analysis and interpretations of vision transformers. Tn International Conference Machine Learning, pages 19050 19088. PMLR, 2022.
Marcel Berger. Geometry I. Springer Science & Business Media, 2009.
Eugene Gover and Nishan Krikorian. Determinants and the volumes of parallelotopes and zonotopes. Linear Algebra and its Applications, 433(1):22 22)-)))0)40, 2010.
Arda Sahiner, Tolga Ergen, John M Pauly, and Mert Pilanci. Vector-output relu neural network problems are copositive programs: Convex analysis of two layer networks and polynomial- algorithms. International Conference on Learning Representations, 2020.
Werner Fenchel and Donald W Blackett. Conver cones, sets, and functions. Princeton University, Depart- ment of Mathematics, Logistics Research Project, 1953.
Hermann Weyl. The elementary theory of convex polyhedra. Contributions to the Theory of Games, page 3, 1950.
Yilei Wang, Tolga Ergen, and Mert Pilanci. Parallel deep neural networks have sero duality gap. In The Eleventh International Conference on Learning Representations, 2022.
27

---

Published in Transactions on Machine Learning Research (10/2024)
6 Appendix
6.1 Generalized cross products
Definition 4. Let E,,..., Id-1 E R4 be a collection of d vectors and let ,r,..., Zd-1
dx
(d-1)
be the matrix whose columns the vectors { The generalized cross product [Begger 21. Id-1 is defined as
2009) of
X x Id-1 x(I1,
xd-1) 2
"A
(42)
1=1
where A; is the square matrix obtained from A by deleting the i-th row and {ei)s is the standard basis of Rd
We next list some properties of the generalized cross product.
The cross product x (I1,,...., Tdd-1 is orthogonal to all vectors #1.-.., Ed-1-
The cross product (Ii,,..., Td-11 equals zero if and only if 21,..., #a-1 are linearly dependent.
The norm of the cross product given by the (d - 1)-volume of the parallclotope spanned by 21;--., #d-1, which defined as
P( (.......,,-))) A
Lar 0 100441114 144
where Fdd- are lincarly independent.
The cross product changes its sign when the order of two vectors is interchanged, i.c., J1 X 82 ... Fa = -2 2ı X ... wa due the determinant expansion of the cross product in (2).
Inner-product with a vector gives the d-volume of the parallclotope spanned by I1,..., Fd-1 and the vector, Le.,
X ( 121...., xa-1)) det x æ1
Td-1] Vol(P(z, Id-1)).
Distance of a vector to the lincar span of a collection of vectors Fi...., Ed-1 is given by
VoI. x2-1)
x 2x411...22111 (x (f....., Ha )|2
dist(z, (efll,,Spa(z....... fa-1)) Vol(P(Z)...., xT-1))
Distance of a vector to the affine hull of collection of vectors Ti, .. Fd given by
Vol (ol Fzz
... 3 Fz
dist(z, (ff())...,;,111
Vol P( Rd 1- - Iza
x(1 Ed.... Ed- 1 xta (x Ia)
(x) Fdd ... Id- I:d]
* ((11 Iz) A (I Iz) (x xz))
[ - xz) ^ (E vaall2
The rejection of vector ir from the affine hull of collection of vectors 31, Rd be written using Geometric Algebra Gd as
(x) ra) N ... (x ra) (x xa)
I ProjAAf
(01 xa) N... A (xaa1 - Ixa)
28

---

Published in Transactions on Machine Learning Research (10/2024)
When d =3, 3, the cross product reduces to the usual cross product of three vectors in R For example,
a
a' bid D'c
b
b = ca' c'a x
c
ab' d'b)
When d 2, the cross product of vector xr rotation by right angle in the clockwise direction in the plane. For example,
a b
b
La
Detailed derivations of these results well as further properties of generalized cross products can be found in Section 8.11 of [Berger] (2009). and their connections to the volumes of parallelotopes and zonolopes can be found Gover and Krikorian (2010).
29

---

Published in Transactions on Machine Learning Research (10/2024)
7 Supplementary Material Additional Numerical Results
7.1 Additional Numerical Results
In this section, we provide additional experiments showcasing the effectiveness of the proposed polishing process in enhancing the performance of neural networks. We consider variely of datasets and architectures, including three-layer fully connected ReLU network, four-layer convolutional neural network, and a two- layer ReLU network for an autoregressive character-level text prediction task. We compare the performance of the polishing process with the standard methods such SGD, Adam and AdamW, and experiment with all hyperparameters, including the learning rate, momentum parameters, number of epochs, and batch size. We also provide a comparison of the decision regions pre and post-polishing, highlighting the enhanced data distribution fit. due to the polishing. It can be observed that the polishing process significantly improves the performance the neural networks, leading to a marked improvement in the objective value and the decision regions, for varicty of datasets and architectures under different optimization hyperparameters.
30

---

Published in Transactions on Machine Learning Research (10/2024)
7.1.1 Image classification and text prediction
We now consider the settings in Figure | and vary the optimization hyperparameters, inchuding the momentum parameter 31 of AdamW, the number of epochs, batch sizes for the four-layer convolutional neural network trained the CIFAR dataset. We consider three different binary classification tasks the CIFAR benchmark, and character level text prediction task on the same subset of Wikipedia.
7.1. Four-layer convolutional neural network for CIFAR class vs class 1 (a) Varying AdamW momentum parameter 31 and number epochs
Accuracy learnng rate
Acouracy
3.06
0.30
3.78
melie Accutayy Pubiece
Vamelien Accutry Pulited
Accenc Oiggnd
Than AzcenKS Ongen
rale
Figure 13: AdamW, 61 = 0.9, bs= epochs=10 10
Figure 14: AdamW B1 0.8, bs 2048, epochs=10 10
Accurccy vs.
Accuracy vs. leaming rote
0.40
0.02
0.35
0.52
0.50
0.54
Wictte Ascercy orginal
0.82
Variiiionn Acoracy Orignal
Valdil Accurayy Nobooo
Trin Accunacy
TeerAccreey hailee
3.000
3002
2304
2.08
000
0.0
Learning
Figure 15: AdamW 81 0.6, bs-2048, epochs=10
Figure 16: Adamw B = 0.9, bs 1024, epochs=
Accuracy vs. learning rate
Accuracy Va. lear learning rasn
0920
6875
6822
0.88
0.94
0.775
melin Bolce Accuracy Polskce Pollited
Valea Accintty
volee en Acueney relited
0.72
Aocunaccc Polihed
Wearing 1utx
Lournig tdt
Figure 17: AdamW & 0.6, bs-2048, epochs=5
Figure 18: AdamW B1 0.9, bs 2002008, epochs-20
31

---

Published in Transactions on Machine Learning Research (10/2024)
7.2. Four-layer convolutional network for CIFAR class 0 class
(a) Varying AdamW momentum paramcter 31 and batch size (bs)
Accuncy
Accurscy
3.00
0.74
buddadinn Hallheed
Tath Accuraty odgital
3.76
Valder Foliteed
Tish Accurcy orginl
Tash Accuray relidaed
Accurcy hillhedd
0.20
6.22
0.000
0.000
0232
Figure 19: AdamW, 0.9, bs-2048, epochs-10
Figure 20: AdamW B1 0.8, bs 20-2 epochs-10
Accuraty leeming rabe
Accuracy leaming
0.88
0.46
0:34
0.42
Waddauen
1.00
Masdaren Accuray Patooo
eaaiinn Accuncer Nisted
0.74
Leareegrate
Figure 21: AdamW 31 0.6, b048,48, epochs=10 (b) Varying number of epochs
Figure 22: AdamW 81 = 0.9, 10=4 epochs=10
0.32
1.55
0.50
Vasdacinn Accuracy haloved
SEIR VEIRIAAAACOEE Accuncyy Nisted
Tot Accurac Oiggnll
6.70
0028
0.008
3.000
Figure 23: AdamW 31 = 0.6, bs- epochs=5
Figure 24: AdamW 81 = 0.9, bs-2048, epochs-20
32

---

Published in Transactions on Machine Learning Research (10/2024)
7.3. Four-layer convolutional neural network for CIFAR class vs class 3
(a) Varying AdamW momentum parameter 31 and batch size (bs) Accurasy vs. learning resl
Accurecy va. leaming rate
3.08
3.02
Leannig 1ite
Leornin rote
Figure 25: AdamW, B = 0.9, bs 2048, epochs-10 10
Figure 26: Adamm B1 0.8, bs 2048, epochs-10 10
Accurcy vs.
Accuracy
0.98
0.85
Va eolic Accuraty Orgend
vale en Accivty Orgins
Tenncuun origna
Then Accency Poinhed
Tanncuu Aulthed
2.000
3300
3:004
0.00
0.000
3.000
0.002
0.004
2006
2008
3.38
Lsarting
Lourning
Figure 27: AdamW 81 0.6, bs-8 epochs=10 (b) Varying number of epochs
Figure 28: AdamW B1 0.9, bs=1024, epochs=10
Accuracy va. leaminng rate
Accuracy vs. learning 1912
0.22
0.30
Valoot Arceic Palide
Leaming rate
Loaming
Figure 29: AdamW 81 0.6, bs 2048, epochs-5
Figure 30: AdamW B1 0.9, bs- 2048, epochs-20
33

---

Published Transactions on Machine Learning Research (10/2024)
In this section, we vary the optimization hyperparameterss including the momentum parameters 31 of AdamW, the number of epochs, batch sizes for a three-layer fully-connected ReLU network with 512 in each hidden layer, trained for binary classification CIFAR dataset. We consider the task of distinguishing class (automobile) from (ship). We display the average accuracies over independent trials for each learning rale.
7.4. Three-layer fully connected ReLU network for CIFAR class vs class
(a) Varying AdamW momentum parameter 31 when B2 0.999 (default), batch size=2048, epochs=5 Acoursay vs laam
Accuracy vs. leaminggag rate
1.05
0.75
665
0.52
3.40
6559
Vil tation Accuracy- falaned
Vel cajes Aecuracy Polindd
Th Accuray- Deginal
Tan Rccunay Degiial
Accuracy
0.0000
0.0002
30000
3.6000
0.0006
0.002
Figure 31: AdamW, 81 0.3
Figure 32: AdamW B1 0.4
Acturccy lesming rate
Accuracy ming rate
0.85
0.52
2.75
3.70
2.05
0662
3.50
0.55
3.90
To Accurcy Orginal
Tann Accuracy orginal
Accurocy
3.30
Accur any Polliied
0.0000
6.000
38000
33600
0.2006
0.002
0.5004
0.0083
0.2010
Figure 33: AdamW 0.5
Figure 34: AdamW 0.6
Accuracy leaming rate
Accurscy leaming rate
0.35
0.22
0.82
0.75
0.75
0.75
0.78
0.5
0.55
0.52
0.58
0.5
eution Acciricy Ongeal
0.55
dateen Accarey Orgiol
Acuracy
Accuacy
0.5
Tra Acurcc Nidiled
0.59
Tram AcCeRcy
0.0000
0000
0064
20006
20006
32020
7,0000
0.0000
0.0044
0006
20006
3.000
Figure 35: AdamW 0.7
Figure 36: AdamW 31 0.9
34

---

Published in Transactions on Machine Learning Research (10/2024)
7.5. Character based language model In this section, we present additional numerical results for the character-basedd autoregressive language model. We compare AdamW with polishing in a small subsct of text from Wikipedia, consisting 52000 characters from the article titled 'Neural network (machine learning): The block size set to 16 characters and the batch size and learning rate is varied.
Mean Training and Test Perplexity Across Runs
Mean Training and Test Perplexity Across Runs
Tast
12
Train Palished
10-
Irain
Test Palishved
7000
Number
Number neurons
Figure 37: Character-level MLP (left) Adam with learning rate 10-4, batch size 2048 and (right) Adamm with learning rate 10 3 batch size 2048.
Mcan Training and Test Perplexity Across Runs
Mcan Traininng and Test Perplexity Acress Runs
12
Train
Tain
Test
Test
Polishhed
Polished
lest Polished
Polished
10
Parploity
Perplesity
4-
1000
2000
3000
4000
5000
6000
7000
8000
1000
2000
3000
4000
5000
6000
7000
8000
Number of neurons
Number of neurons
Figure 38: Character-lovel MLP (left) Adam with learning rate 10-4 batch size 512 and (right) AdamW with learning
rate 10 batch size 2048.
35

---

Published in Transactions on Machine Learning Research (10/2024)
Kernel Ridge Regression Valiorioon
Random Thiin
Kernel Bidge Begression Test
Random Forest Valddaiion in
14
100000000000 MSE
15-
10-
5-
0.00000
0.00002
0.00004
0.00006
0.0000s
0.00010
20
40
100
Regulbrizatin parameter
Number of trees
(a) Kernel ridge regression (Gaussian kernel)
(b) Random forest regression
Figure 39: Comparison of regression models
7.6. Tabular Dataset
In this section, we provide further numerical results using the Boston Housing dataset. In Figure 30 we present the training and validation of MSE of kernel ridge regression using the Gaussian kernel and random forests. We provide one standard deviation error bars for the random forest over the randomness of the construction of trees. It can be seen that the polishing process shown in Figure I0 provides significantly lower validation MSF. In addition, we observed that linear regression and decision trees underperform compared to the kernel ridge regression.
8 Supplementary Material II Variations of the Network Architecture
8.1 Two-dimensional two-layer networks with no bias
Theorem 15. Suppose that the training set (f1....,,,, } is e-dispersed. For = and = 2, an c-optimal wetwork can be found via the following conver oplimization problem:
min ZER"
(K2,y) 1||=||1-
(43)
Here, the matric K E TRax is defined as Kij = k(I;, Rz), where
x(x,,') (x (x^xx)) 2Vol x,,,,,,,')) dist (x. Span(x') (x')),
||ا/||2
|
and the number of newrons obeys 2 || Here, Span(x,) denotes the linear spon of the vector zz.
The e-optimal neural network can be constructed as follows:
f(x) Σ 23)(
(44)
where z" is optimal solution to The optimal hidden neurons are given by scalar multiples of the Hodge duals of 1-blades formed by dala points, *I, XXj, corresponding to non-zero 27.
8.2 Two-dimensional two-layer networks with bias
We now augment the dataset by adding ordinary basis vectors with training points. Let us define 2. = 2 for E [n] Vj and x(22 x, + e* for [n] Ak [d] where e1, e1. ed the canonical basis vectors. We note that this augmentation is only needed in the case of p 1.
36

---

Published in Transactions on Machine Learning Research (10/2024)
Theorem 16. For p p= and d = 2, the two-layer neural network problem with biases is equivalent to the following connex ( -rregularized optimization problem:
min {(K2+ + + A||z|11,
(45)
EER = (2)
EER
provided that the number of newrons obeys m 2 11
Here, the matrix K E ER (())+a) is defined as Kij == rl Bzi 25, F/2
(i))) for (f1, where
x(x,d',"") 2Vol (A x',"))
(46)
1 x 1
(f1:3) mulli-indes M(x,,',a") denotes the triangle formed by the points x, x' ,,,x," x",
x")) 1 ((x - x') (x" x'))
[x + A x" + A 12)
denotes the positive part of the signed volume of this triangle. An optimal neural network can be constructed as follows:
f(z)
Σ 2) 2 22 1i1))
(47)
}=(jida)
where =* is on optimal solution to 45 generalized cross product x(x,,
The optimal hidden neurons are given by scalar mulliples of the + - x 52 ((1)), which are Hodge duals of 1-blades formed by differences of data points, corresponding to non-zero 2) for = (21.2)).
Remark. We note that each RcLU neuron the optimal network has a breakline passing through a pair of training samples Tj and Fjz-
8.3 Two-layer networks with inputs of arbitrary dimension without biases
Theorem 17. Consider the following conver oplimizaliin problem
px min El (22, 3) + A||2|11
(48)
The malria K is defined as Kij = k( En Tjj ,) for = (ji, -a. ja-1), where
(x A A A ud-1)+ dist. (I. Span(u), .... ud-1)),
s(x, Ui,..., ua-1)
|u] A ua-1l12
the multi-index Ja-,..,a-11 is over all combinations of d-1 rows Fiis Dja-1 E Rd of X Ruxd When the mazimumm chamber diameler salisfiss (X) S e for some E (0, 1), we have the following upprozimation bounds
p" S < 1-c p',
(49)
P(1-)A pp' PA pp
RRR
(50)
Here, p" is the value of the optimal NN objective in 2 and R is the corresponding weight decay regulorization term of an optimal NN. A network that achieves the cost Px in 2 is
f(x)
Σ
2zK(Ejo )ia-))
j=(ít (=
where z² an optimal solution
48
For multi-index j (i1.22) where
[n), In d], the entry Kig of the matrix K is given (n
37

---

Published in Transactions on Machine Learning Research (10/2024)
Corollary 18. By taking the limit À + O, we obtain the following interpolation variant of the conver NN problem 48
po = min ||=||1 2: [(K2,y)=
(51)
provided that the constraint ((K2, 0 is feasible. In this case, have
P6 S jo E 1 po:
(52)
given that (X) S where Po A ming {()(())))= |1112.
9 Supplementary Material III Mathematical Proofs
9.1 Proof of Theorem
Consider the dual constraint in which can be rewritten as
sup ws, BEB: 11
Σ vil +6)+15
(53)
Since is scalar, the constraint ||||pp < is equivalent to |w| < for all E oo). An optimal w satisfies w E {-1,+11 since either this constraint is tight or the objective is constant with respect to w. Next, observe that an optimal b is achieved when E + or the objective goes to infinity when b b co. This is because the objective a piecewise linear function b. In the latter case, the objective value is infinite as long as E, 0/2 # O. Therefore, we can rewrite 53) as
max E u1(2, - x,)+1, Σ uzlzy - m)]+} s X and Σ 0 ===0
(54)
We use strong Lagrangian duality to obtain the claimed convex program using Lemma 26 It can be seen that the network given in ( achieves the optimal objective on the training dalaset since f(X) =
[f()), f(x,))) K2* lt".
9.2 Proof of Theorem 2 and Theorem 4
which shows the equivalence of the l-regularized noural network and the Lasso problem in (14. Suppose that the training matrix is of rank Denote the compact Singular Value Decomposition (SVD) of as follows = UEVT where U Raxd and V gaxd are orthonormal matrices and Σ E ddxd Only & diagonal entries of Σ are non-zero and the rest zero. We denote the non-zero diagonal entries of E d., , and the corresponding columns of U and V u1.-.. " and U1, Uk, respectively.
We now present the proof of Theorem and the special case Theorem 2
diagonal matrix with non- non-nveative diagonal entries.
Consider the NN objective ! It can be seen that the projection vf W1; of the hidden neuron weights E [m]] does not affect the objective value for i = k, d. Therefore, the optimal hidden weights are zero in the subspace Uk.1,..., Va due to the norm regularization. In the remaining, we assume that the training matrix X is full column rank and of size n by d r. Otherwise, we can remove the zero singular value subspaces of X via the above argument.
We consider the convex dual of the l--regularized NN problem 14 and focus the dual problem given in 5 when a is the ReLU activation function.
max VE
EE (v,y)
s.t.
max 1o |
(Xw)+I
(55)
S1
The above optimization problem is a convex semi-infinite program which has finite number of variables but infinitely many constraints. Our main strategy is to show that the constraint set can be described by finite number of fixed points by analyzing the extreme points of certain convex subsets.
38

---

Published in Transactions on Machine Learning Research (10/2024)
As shown in Pilanci and Ergen (2020), the constraint [x"(X))+ S A can be analyzed by enumerating the
hyperplane arrangement patterns
(D = ddiag( 0)) w R
where P is the number of distinct hyperplane arrangement patterns and DR E [0,1] is the indicator matrix of the k-th pattern. The number P is finite and satisfies the upper- bound by P S 2 d- = ("7') where r rank(X). Note that we have the identity
(Xw)+ DRxw Vw 1&xW>20 (1 D 00,
which shows that the ReLU activation applied to the vector Xw can be expressed as a linear function whenever w is in the cone (2D; X) 2 0. Using the above paramcterization, we write the subproblem in the constraint of 155 when = as follows
dsub - max je Du
(56)
s.t. ||l|| s 1, (2D - I)X 2 0.
We next claim that the constraint |W]] < is active at the optimum, assuming the objective value is positive, Note that w = is feasible point, which achieves the objective value of zero. Otherwise, we can scale w to satisfy the constraint and increase the objective value. Defining the set
c a ((2D: 1)X 2 0, ||||| = =
we can express the dual subproblem dsub using the set C as follows
duub = max (0,
f0, max x" D'DD Xww, max - - Dr Xw
wec
wEC
Note that the maxima the last two problems are achieved extreme points of C since is a bounded polytope and the objectives are linear functions.
The following lemma provides characterization of the extreme points of the constraint set of the dual subproblem.
Lemma 19. A vector is extreme point of the set C if and only if w E C and
X = 0 and ||l||
(57)
1
x T
where S subset of d linearly independent rows of
The proof of this lemma is given at the end of this subsection. We identify the extreme points via the product follows. After defining the augmented data rows Inti e; where is the i-th standard basis vector, a vector w C is an extreme point of C if w E Span(X (X JEST,) for some subset S of size d - 1 such that bis are linearly independent and || = 1. Since this span is d 1 dimensional subspace, we can X ,esa, Note that the denominator is non-zero since (x, (ry)es are linearly independent and
write as X 1e JeS 2yl1a Xees æ2ll2, which is the non-zero absolute volume of the parallelotope spanned by {x, Jes. Consecutively, we apply this characterization of extreme points to the expression for dab to obtain
daub = max {0.
max oz DaXX ). weV : {EyJies linearly independent, |S| |8|= - d 11
where V 2 {
X X
1X,es*;l1i
39

---

Published in Transactions on Machine Learning Research (10/2024)
Next we note that D = (Xw)+ for w E V S C, which shows that the dual problem d' in 55 is
equivalent to the following problem
max eE
- (v, s.t. (x(())+ EV.
(58)
By applying the characterization of the extreme points, reduce the semi-infinite problem in 55 which
has an infinite number of constraints to problem with finite constraints.
Taking the Lagrangian dual of the above convex problem by introducing dual variables for each of the constraints, we arrive at the & penalized convex problem
min () + A Σ 1zyl-
((ovo(((es:)ees)) using the multi-index notation j 1Xx (1 13l1 IX lh
Here, Ki (NoN? X ((s))-)-(a-))
(Jor (1s...n---)) where jo ranges over {-1, to represent the choice of sign in the expression
X ((z) (ie
txo (
Rescaling the dual variables 2j by x (I .. - we obtain the problem
min ((K2,8) Σ wylzz].
where Kg (jo Vol(P(z),, ... 4))-1))) and wy = x (I) ..., I3a-
Finally, in order to simplify the notation, we take the index set (f1, mi 28-1) over all subsets of {1, (,, n) of size d d-1 1 and redefine the matrix Kj Vol, (P(#)) )) and wy x (Ijr Fja-1 Ill1 This follows from the fact that the Euclidean norm of the cross product, and hence the volume of the parallelotope is zero the whenever the subset of vectors are linearly dependent. Moreover, the index jo E [11.+1} is absorbed into the ordering of the vectors - in the parallelotope, by noting that the sign of the cross product is flipped whenever the ordering two vectors is flipped. This completes the proof Theorem
Next, we provide the proofs of the lemmas used the above proof.
Proof of Lemma We express w -+ = where - 2 0 and w 2 represent the positive and negative part of w respectively. Then, we express the extreme points of the using this lifted representation follows
w+ w-
(2D; - I)(x= xww) 2 O, W4. 2 0, 1 ww + w =1
C²
We next arguc that the extreme points of C can be analyzed via the extreme points of C'. In particular, it holds that
max x² w max weC'
x² =wwwt - w
WEC
for all Rd and maximizer to the former maximization problem be obtained from maximizer (wt, w) to the latter problem by setting w² w w On the other hand, a maximizer (w+, w=) to the latter problem can be obtained from a maximizer w to the former problem by setting w = max (w, 0} and w- = max(-ux 0}. Thorefore, characterizing the extreme points of C is equivalent to characterizing the extreme points of C²
This can be written in matrix notation as follows
(2D;
T)X
-(2n, T)X
w
and
1
1.
0 I
M
40

---

Published in Transactions on Machine Learning Research (10/2024)
Using Lemma 22 the extreme points of the above set are given by the unique solutions of the linear system
Ms
w+
0 :]
1sr
w-
Ms 1ad
where Ms is a submatrix of M such that
E IR is full rank. For any extreme point (w*, w" of C²,
the vector w = w - w is an extreme point C. can be seen that at least d coordinates of (w+ w
are zero
since w = w+ w is the decomposition of w into positive and negative parts. In order to characterize non-zero extreme points, we may assume that not all of the constraints w
2 0 are aclive, since otherwise O. We next show that the rows of Ms linearly independent from the row vector 1 due to the structure of M. Specifically, the top block [22D 1)X -(2D, [)x] has row
w+ -- implying
span orthogonal to 17, and the bottom block O
T 0
0 I consists of canonical basis vectors, for which not
all constraints are active (otherwise this implies independent from 1a.
0), which makes the subset of active rows linearly
We conclude that the non-zcro extreme points of C are given by w = w w E such that
Ms
w
0 1
1sd
where S is subset of 2d - 1 linearly independent rows of M and the above linear system has unique solution. Recall that at least d coordinates of w are zero at any extreme point due to the decomposition Suppose that the vector T (w)+ and w (w) are the positive and negative parts of w respectively.
w w+ w where w
is non-zero extreme point and has d k zero entries for some k Z4,
w w are zero. Mapping this
then 2d 1 kk d-1-1 entries of [22:; - 1)X -22;-11
decomposition back to the usual representation, this implics that an extreme point C has k zero entries and the vector (2).-1)Xu w has d- 1--k k zero entries. Therefore, d- of the constraints
[2D: - -)
w 2 0
are active at non-zero extreme point E C. We conclude that E C is non-zero extreme point of C if and only if
(2D: nX
==0 and ||l|| 1,
[2D: T)X
where R is subset of d - linearly independent rows of the matrix
Finally, we observe that
the constraint (2D: x)x
[x] 0 since (2D, - 7) is a diagonal matrix
w 0 can be substituted by
I
I
R
containing +1 values on the diagonal, and note that linear independence is invariant to this diagonal sign multiplication.
9.3 Proof of Theorem 17
We now present the proof of Theorem 17 which shows the approximate equivalence of the fz-regularized neural
network and the Lasso problem 48
We consider the dual problem in (5 and analyze its constraints,
which are as follows:
max max |1 DD < A se(P) t0
(59)
s.t. ||w||2 < 1, (2D; - I)X 2 0.
41

---

Published in Transactions on Machine Learning Research (10/2024)
Here
(D:)== = [diag(1[Xw) 2 0)) w E {d
are the diagonal hyperplane arrangement patterns.
As in Section 9.2 assume that the training matrix X is full column rank and of size by = r, without loss of generality.
Consider the sub-problem arising in the above constraint given by
d drub (t) A max vz D,Xw w
s.t. |wll2 - 1, (2D; - I)X 2 0.
We define the set
C2(1) a
{ w | -2D; 2 =0
and let d (1)
maxweca(() -b- D.Ww. DxXw. Note that the constraint in 5 is preciscly dt (1) S S d s
A Vi. Our strategy is to show that (t) and (t) can be tightly approximated by polyhedral approxi- -
mation constructed using the extreme rays of the cone {w 1I 2 0}. Consequently, we will be able to obtain an approximation of the dual problem since the dual constraint is
doonst
max max Iu D,Xw] = max max (1), max iE(l..... P)
daun(i)) ie (l.., P)
(60)
iE(l.., weCs
We first focus on a generic instance the problem dtw diuu (1) and C2 = C2(1) for a certain value i. Suppose that the extreme rays the convex polyhedral cone
{w (2D; - 1) 2 20 R
are R1,..., Rs S Rd for some & Z4. Note that by our assumption that X is full column rank, this cone is pointed since it does not contain any nontrivial linear subspace. Let Pis E gd-1 denote the unit norm generators of the extreme rays Ri,..,, R& normalized to unit Euclidean norm. We define the convex sets
p é Conv(pi.....Pp pk) and Po Pk.
We will use the convex set Po as an inner polyhedral approximation Cz. We define the distance of the convex set P from the origin as
dmin A (0,
minn WEP
||w||2-
We have dmin I since Σ, a,pllle $ E, ladllppil2 = E, lasl for any as 2 0 and Σ, a 1, noting that 1pp/l/2
We apply Lemma
20
obtain the following lower and upper bounds on d
max x D max wECs
oT D'Xxw S
max JDDxXw wed=1_p Po
(61)
wEP.
= -d1 max T DrXW. WEP.
Next, we simplify the polyhodral approximation max,ep, o Dw.. Applying Woyl's Facct Lemma (sco Lemma 24 to the cone K = {w (2D; - X) 2 0}, we see that a vector v E K belongs to an extreme lincarly independent rows of the matrix (2D; - J)X orthogonal
ray of K and only there are v. Then, each of the generators of the extreme rays Pl, Pk satisfy pf x, 0, j S where S is subset of linearly independent rows of the matrix X. Using the properties of the generalized cross product identify each generator scalar multiple of the cross product XjEs,I, of the d - linearly
(see 6.1
42

---

Published in Transactions on Machine Learning Research (10/2024)
independent rows 2j of X. Note that the cross product of d - 1 linearly independent vectors is orthogonal to each vector and lies on a one-dimensional linear subspace. Therefore the unit-norm vectors Ps can be identified as p. = + X _ where the sign is chosen so that p. E K, i... P. DRJJIT 2 0 for all E St. ,es,,,,
Next, note that Weyl's Facet Lemma also guarantees that any vector p E K of the form p = X X
11X ,es; is on an extreme ray of K when S a subset of d-1 linearly independent rows of X. When d 2 2, the collection of vectors OU (+ X jes Ij S S [n], dim Span(z, j E S} d - 13 is equivalent to O U (XjestJ S (n-1([n))), where ((-1((n)) denotes all permutations of subsets of [n] with d 1 elements. In order to see this equivalence, observe that the #1 multiplier can be removed when consider permutations since exchanging the order of the two vectors in the cross product changes the sign of the resulting vector. Moreover, we can only consider subsets S of size d - 1, otherwise the vectors are linearly dependent and the cross product is zero. In addition, when the vectors are linearly dependent, the cross product is zero, which is already included in the collection of vectors.
Using this characterization, we can simplify the first optimization problem in 66 by enumerating all unit- norm generators of the extreme rays of the cone K, which can be done by considering all subsets S of d - linearly independent rows of X and taking the cross product of the rows in each subset. Define the set Ds as follows
{
) }uo.
Ds XJES 2j uo.
Then, we have
Xw
max T Dr WE Po
max of DaX max max of =E(Oppt....p.)
(62)
SCP)-a((M)) weKnDs
|wl12
where the last maximization is over d 1 permutations Pa-1 ([n]) of subsets of [n], and w E K Kn Ds. The justification of 62 as follows: In the first equality in 622, we can drop the convex hull of (0.P1.... pk
since the objective linear. In the second equality, we replace the unit norm generators by their expressions given by the cross product and use the fact that D,Xw (Xw)+ for E K. Note that the cross product is zero when the vectors are linearly dependent to simplify the expression of Ds in the last equality above.
Next, we plug-in the expression for th given in the last equality of 62 for d in 60 repeat the same
argument for d (1) which is identical, and use the approximation bound in 61
&const
max DDDDxw (E(1,... P), 11 (ECa(1
max
(63)
d
max so VE(1....PP Ph. -1(+1.-11 SCPa-i(m)) we WEK (1)nD)
max
max
X
|10
|
(64)
where K(i) = (w (2D; - 1)X 2 0}. Noting that
k() = uu (2D:-1)Xw* 0
-
since the union of the chambers of the arrangement is the entire d-dimensional space, maximizing over the index i E {1,... P} and w E n is equivalent to maximizing w over Ds) Dz. Therefore,
we obtain
d d'onst d d,
(65)
where
d
max T sCPa-1((x) wEDs | +
max
(x
X
W
(66)
Using the expression of the dual in
WC have
p d' domn (1)SA
max (v)
(67)
43

---

Published in Transactions on Machine Learning Research (10/2024)
where dronst = dconst (v) is as defined in 63 We then use the inequalities in 65 to get the lower and upper-bounds on the optimal objective as follows
(v)
S max (c)
(68)
d(v)
d(v)
where d(v) = d is as defined in (66
Replacing the duals of the maximization problems in the above equation
using Lemma 25 we obtain
min (K y) dain A| Sp" S PA min mine(KK,)) A||2|11-
(69)
Here, we defined ya as the optimal value of the Lasso objective and K is the matrix defined as follows
x x(II, ..., Id-1) Ki of x| (Z1...., 18-1)l12
(70)
where j == (fi....Ja) a multi-index. The above shows that the optimal value p" corresponding to the NN objective in ( when p 2 is bounded between the convex Lasso program in the right-hand side of 69 and the same convex program with slightly smaller regularization cocfficient follows
Pdmaa S Sp" S PA.
Noting that
E(K Edmandd)) 9) + dmmnn &ddmmnnl 2 min ((K2,)) y) A1|2|12 (dmin 1)Al 2d 2l12
= pix (1 daii )>1 Addmmlll
where Edmard is minimizer of the Lasso problem corresponding to Pdmind- we get the inequalities
px - (1- (1-nnnn Al12 S Pdmmad Sp' Px.
(71)
This shows that the optimality gap is at most (1 - dmii) Adl 11,, where 2dmmn is an optimal solution of the Lasso problem in the left-hand side (69) with regularization coefficient dminn.
We now obtain upper and lower-bounds on px in verms of p" by noting that 65
implies
& S d d S d dconst-
Multiplying both sides by dmin we obtain
dmiaa d donnst I d < dr doonst-
Using the above incqualitics in the dual programs, we get
max (v) < max (v) - (
max dmin donnet (A)
(v).
(72)
d(v)SA
Using the dual of the Lasso program again from Lemma
we obtain
p' min + A||=||1 S SP'-1
(73)
where phy the rind side is defined as
m
m
A min pr.
(XW1, 18,,) Wej. + X Σ
Wi 1 + |2
(74)
W.WW2
44

---

Published in Transactions on Machine Learning Research (10/2024)
for m 2 m" where m" is the number of neurons in an optimal solution of the bidual of 55 when p = 2.
Here, P Pi is the value of the optimal NN objective when the regularization coefficient is set to to the larger
value d dmin X. This value be upper-bounded follows
Pa P S F(WT, + ARWW, W
(75)
= F.W.. W2) + XR(WI, W2) + (d T)AR(WT, W3) P (dmin 1)A W2),
(76)
(77)
where -(.,)) and R(.,)) are the functions in the first (loss) and second (regularization) terms in the objective
74h respectively, and (Wr, W2) is an optimal solution of (74) i.c., we have Px = F(W7, W2)+ + +XR(W,, W3).
Therefore, 73 implies that
p' S min e(Kz,)) A||=||1 S sp' + (d 1)AR(WT, W3)
d d
(78)
where R(WT, W2) ==)==Em= [W7, + is the regularization term corresponding to any optimal solution of 74 The final inequality follows from AR(WT, W2) S p". This shows that the optimality gap of the Lasso solution is at most 1-dmun AR(WI, W2).
dmin
Finally, to simplify the expression of the matrix R given 70 we use the following cross product repre- sentation of the distance to an affine hull (see Supplementary Material)
xT X(I I8-1) dist(z, Aff 21 IT-.1) x (2) 11--
dist(x, Span( -d.
for any 2; 11,,,,.. Id-1 E Rdd where x ((, is the cross product of the vectors I1, T3-1- Combining the bounds 711 and 78 with the lower bound on the minimum distance dmin in terms of the maximum
chamber diameter r from Lemma 21 completes the proof.
9.4 Proof of Theorem 14
The proof parallols the proof of Theorems and 17 Here, we only highlight the main differences.
The convex dual of the problem
40 is given by
p
max VER"
(V,Y s.t. |V (Xo))l S X, Vo E B
(79)
This dual convex program derived in Sahiner et al. 2020), where it also shown that strong duality holds if the number of neurons, m, exceed the critical threshold m", which is the number of neurons in the convex bidual program.
We focus on the dual constraint subproblem in 79 given by
dy-sub max D Xxwll
s.t. ||l| S 1, (2D, - 1) 2.
1 T DyXWi
max w: lullag1
max
s.1. ||l|p S 1, (2D, 1)X w= 2 0.
We note that the above problem has the same form equation 56 and 59 for p = 1 and = 2 respectively, where the vector v plays the role of Vu. The rest of the proof identical for both cases.
Lemma 20 (Archimedean approximation of spherical sections via polytopes). Suppose that Cone ()) n -Cone(P) {0), i.e., Cone(P) does not contain a non-trivial (non-zero dimensional) linear subspace. Then, it holds that
Po C C2 S do Po-
45

---

Published in Transactions on Machine Learning Research (10/2024)
Figure 40: Illustration of the Archimedean approximation in Lemma 20
Proof. The first inclusion follows by noting that Po is a polytope and it is contained in C2 since all of its extreme points 0, P.......,P Pk are contained in the convex set Cz.
In order to prove the second inclusion, first show that C2 Cone(P) n {l|wll S 13. Since Cone is pointed, i.e, Cone (P) -Cone(P) {0}, it is equal to the convex hull of its extreme rays (Theorem 13 of Fenchel and Blackett (1553)) Since the extreme rays of Cone(P) and the extreme rays of the cone {w (2D; T)x 2 0}, are identical and the latter cone is also pointed, these two cones are identical. Therefore, we have C2 = Cone(P) n {|]w|l2 _ 1}.
Next, suppose that there exists some w' E C2. Then, 3t R4, a; 2 0, 0.E, = such that w" = =t a. since w² E Conn(P). Since ||æ*||2 S 1, we have 1 2 ||o ||2 = E| aspill2 Z Lmina [| a:Pi 22 2 min ||w||2 = dmin- From this chain of inequalities, obtain the upper-bound t < dmin' We have w" dmin Po since
w" = Σ a:p: E :Coon(pi.....p.)) E Conv(O,P1,..... E dmin Pu-
Lemma 21 (Diameter of a chamber bounds its distance to the origin). Consider the set C2 {w (2D; I)xw 2 0, ||l|2 1}. Suppose that E R is the fz fi-dimmeter of C2 which is defined as the smallest r 2 0 such that |lw - w2l12 I r for all w1, W2 E Cz. Then
min dmin (EConv().....)))
||1|| 2 1
for any set of ls vectors (ui,..., Ux} Ez.
Proof. Since the éi-diameter of the set C2 upper bounded by r, we first argue that there exists Euclidean ball of radius that contains C2 follows. Suppose that Wh, we are two vectors in C2 that achieve the lg-diameter r, i.e., || well2 Then, the Euclidean ball of radius centered at tu contains Cp since for all C₂ it holds that
||
+ W2
2
[1(w w1) + (w w2)ll2
1 1 w/ ll2 + 2
/ 11 wall Sr.
1
2
Next, note that Conv(u1, 2x) is contained in this ball due to the convexity of the Euclidean ball and since Uk E C2 are contained in this set. Therefore, the minimum norm point
0" = arg min
||ll2
vEConv(th (E
satisfies ||.*|| 2 |/ 2|2 '|0" -01l2 1 ||0" v1l22 --
46

---

Published in Transactions on Machine Learning Research (10/2024)
Proof of Lemmal 7 We use Lemma 2.1 olln and Vershynin 2014)) by taking K equal to the unit Euclidean
sphere in Rd. Since the Gaussian width of this set is bounded by vd, Lemma 2.1 implies that
|x sE Se V2 || =1, m
with probability at least 2e-nni
where a v2/T and E = 4 + u. Rewriting the above inequality
w 1 a S e Aw, multiplying each side by ||le|2 and letting u = / / we observe that the
as - - Twlla
i isometry condition
220 where /v/ a holds with probability at least 1 - 2e 4/2, Invoking Lemma 6
we obtain that the maximum chamber radius is bounded by AVE- 4// 5 s ( which concludes the proof.
Suppose that w1, u2 E C2. Then, wa [w2 + w2) satisfies (2D; - I)X W1, W2 belongs to the set (2D; T)X 0, which is convex. Therefore, have
Proof of Lemma 0
wo 2 0 since
x wal
| w1 + x wzl
(i wn + x. w2) wi + x! w2)
(sign( we (a (aTT[)) w1) sign(a: wey (x) wz)
a wil + 7 | w2l.
where the third equality follows since sign(r; I w1) = sign(x; w2) vi due to the constraints (2D; l)Xw; 20 and (2D; X) 2 0. Note that since || will = Emm |r) w), this implies the identity
X Xwi || + 1 マ Xw2lli-
||waall =
Applying the isometry condition given in 20 to wa and using the above identity, we get
a(1 + bl]wall2 2 X walli
1
| +
[[w2lla
= 2n
2n
1
2 a(1 e)]lw] ll2 aa e) 1
(80)
a11 - 6),
where the incquality
follows from the concentration incquality we have ||wall2 2 (1 + e) and
80
20 applied to and w2. Therefore,
w/ 112 |1 (w)1 + w
wf uf'r
1 )
2 1 4c.
2 1 (+c)
The last inequality holds since
(1- =1 2c + 2 2222 3e 462 (1 + +e) 4c),
for 0. This implies wf'w2 W2 1 8e. Since wi and wa are unit Euclidean norm, we get ||l] w2
2wf wa 16c. Therefore || wall2 < eve.
47

---

Published in Transactions on Machine Learning Research (10/2024)
9.5 Proofs for two-dimensional networks
Proof of Theorem 15 The proof follows by specializing the proof of Theorem 17 to d = 2 and noting that the chamber diameter is controlled by the angle eτ. Consider the triangle corresponding the the chamber where the angular dispersion bound is achieved. Consider the bisector of this angle and observe that the chamber diameter equal 2 (iin(e7/2) (eT/2),, which is upper-bounde by em. Although this provides the approximation factor 1/(1 6x) long as m-
improve this bound by considering direct. Archimedean approximation of the circular section shown in Figure 40 to replace Lemma (00 Specifically, using the
bisector of the angle we also have
Po S C2 S (cos(eT/2))-
which improves Lemma
20
Finally, note that
(cos(E7/2))) 1
for E [0, 1/2], which completes the proof.
Proof skelch of Theorem The proof follows the same steps as in Theorem 17 and
9.6 Proofs for deep neural networks
Proof of Theorem
10 Suppose that an optimal solution of 12 is given by
0- (W (.))).
Define optimal activations of the first two-layer block based on the optimal W+(),, W-(2) above as the matrix Y" (L) by defining
(1) == (Ux
Now, we focus on the first two-layer NN block and consider the following auxiliary problem
(WV(11 w(l2) = arg
min w
1l + !
(81)
W
j=1
S.L. (X =Y
The above problem is in the form of two-layer neural network optimization problem. We now show that W7(1), (2(2)) combined with the rest of the optimal weights (*(3), W=(4) ... w.(L) are also optimal in the optimization problem 24h.. First, note that the outputs of the network, fe- (X) and fo, (X), are identical where 8* an optimal solution and
à = (W-(), (2-(2), (=(3), ... (W*())
since the activations of the first two-layer block are identical. Second, note that the regularization terms R(1) Em || | (1 are also equal since R()) R!" contradicts the optimality of #* in 24 and 2 > R contradicts the optimality of (W)(1), (7(22) in (81
Next, we analyze the remaining layers. We define the optimal activations before and after the E-th two-layer NN block follows
(*(e-1))
ydd= = (XW ... (((
Consider the auxiliary problem for the f-th two-layer block
(W( (((et))) = arg min
[ 13 || (w(e+1)
(82)
w(t
==1
s.t. ((==)
48

---

Published in Transactions on Machine Learning Research (10/2024)
We show that 0e := (W+(1, W ( 17 w(++) ..r").........)) w-(t-)) (e-())))-(())) which equals 0" optimal in (24) except the 8-th and (f+1)-th layer weights are replaced with an optimal solution of (2) is an optimal solution of (24). As in the above case, the outputs of the network, for (X) and fa (X), are identical by construction.
Morcover, the regularization terms R = Ex= [1 I1 + | I3 are also oqual since R(0)
< R
0r
contradicts the optimality of 0" in 24 and R Rg- contradicts the optimality of (W(), w((+1) in 82
since (W(1), W(++)) feasible
82 i.e, o ((==(=(()))=((() ="
Finally, we finish the proof by iteratively applying the above claims invoke the two-layer result given in Theorem 14 Given optimal solution H* of (24), we replace the first two-layer NN block with (W7(), Wr(2))
from 81 while maintaining global optimality with respect to (24). For & = 2,3,..., Ia we repeat this process in pairs of consecutive layers to reach the claimed result.
The proof proceeds similar to the proof of Theorem 10 optimal solution 0% we can replace the first two layers (W+(1), Wa(2)) with (W W(2),, where
Proof of Theorem 11
We first show that given an
m
(W())e)) arg min w W
Σ | 12 || ,.
(83)
o (XW()) ) = y
s.t.
and (1)) == o( By Corollary 18 the weights (W w()) only increase the regularization
Ei= [ 1|++11111 1lw,, | 1| by factor of 1/(1 2 (X)), while producing the identical network output fg (X):
(X)
Next, we analyze the remaining layers one by one. We define the optimal activations before and after the L-th two-layer NN block as follows
X = o(. ((W"))_.. ..((-1)) y = =" o( ... w (-(l- W)((t1)))
Consider the auxiliary problem for the l-th two-layer block
(Wi(9, w((+))) arg min
Σ 1 l2 ||
(84)
= (0)
s.t.
By Theorem 14 replacing the weights W(( w((+1) only increases the regularization term for those weights by a factor of 1/(1 ((xx)) while maintaining the network output fx(X) = fo- (X). We can repeat this process for all l = 3, ..., one by one, i.e. replacing layers 1 and 2, and 3.... (as opposed
pairs
of consecutive weights as in the proof of Thcorem 10), we replace all the weights by incrcasing the total regularization term by factor of at most 2/(1-c, assuming 2(X) S and 2(X*²) < e for E L1, The factor 2 is needed to account for the overlapping weights in the replacement process.
9.7 Proof of Theorem 16 and Theorem 5
The proof closely parallels the proofs of Theorems 17 and The dual problem in 5 when an additional bias term is present takes the form
p
d max DER
(v, s.t. lu (X" + 16)1 < X, Vu E Bd be R.
(85)
As in the proof of Theorem we focus on the dual constraint subproblem
sup Too + 16)1 < A
(86)
WEBé, bER
49

---

Published in Transactions on Machine Learning Research (10/2024)
and observe that the above objective is piecewise linear in b. Moreover, the objective tends to infinity as + oo as long as Σ t # O. Otherwise, an optimal choice for b is - 2 ot for some index j E [ni] for some optimal w²
Therefore, the constraint
86 can be rewritten as two constraints:
max sup
Σ -x, JE w M
and Σ 0 -0=0 0.
(87)
Now, define X = X 11-1, n and observe that the form of the dual constraint is identical to the ones analyzed in Theorems 17 and 4 for each fixed E [nt. We repeat the argument for each E [n], and use the same steps that to obtain the convex programs and approximation result. In particular, when the chamber 1,,
diameters ((X 1,, ) S uniformly for all j E [n],
9.8 Proof of Lemma 8
Lemma 7 immeddatell implies that the random dataset e-dispersed with high probability. We aim to prove that for any j ..,...,,,, the modified dataset. X' = X Ixj satisfies 2(X') I e, Vj E [n] with high
probability. Note that X 1xf is also a set i.i.d Gaussian, except the j-th row, which is all-zeros. Using the same derivation in the proof of Lemma and we have
(1 - 6')lll2 S a(n ( |(x - laf)) wwll S (1 + +')lll Vw E Rd.
(88)
for 5' d/(nn - and some a with probability at least 1- 2- d/22, Taking a union bound over j E [yl], we observe that the above inequality holds simultaneously vj E [x] with high probability at least 1 22e d/2 We set e' = e/2 and obtain that the dataset X is locally e-dispersed with high probability as long as n Z e 4d.
9.9 Additional Lemmas
Lemma 22 (Extreme points of polytopes restricted to affine set). Suppose that A Rexd bE Rd C Rd and d E R are given. A vector E Rdd is an extreme point of C 2 {Ax S b, ch x= d} if and only if there exists subset S of n linearly independent rows of A such that æ is the unique solution of the linear system
As T
0 d
r
(89)
[A T
where the matrir Radd is full rank. Here, As Ixd the submatriz of A obtained by selecting the d - rows indexed by S.
Proof. We first provide proof of the first direction (extreme point = full rank) by contradiction. Let x² be an extreme point of C. We define S as the subset of inequality constraints active at x" and Se as the subset of inequality constraints inactive. More precisely, we have Asx" = 0 and Agox" < for some subset
As
E padd not full rank. Then we S of n rows of and its complement S Suppose that the matrix
may pick v # in the mullspace of this matrix. Define Ij e x² + EU and T2 - x ev, which are feasible for v and Agex* 0. However, this is contradiction since 1a + f0z- = x and 21,02 22 # x² implies that x² not an extreme point of C.
Ag
C for any sufficiently small 0 since
T
We next provide proof of the second direction (full rank = extreme point) by contradiction. Suppose that x² C is point such that Asr = 0 and Agex" < for some subset. S its complement. 8 cT' d,
As T
and the matrix
E gaxd is full row rank. It follows that x² is the unique solution of the linear system
50

---

Published in Transactions on Machine Learning Research (10/2024)
[A c² x [] We will show that x' is an extreme point. Suppose that this is not the case and there
[0]
exists 21, 22 E C distinct from x" such that x² 2 + 222 Then, we have An I 0, Ar S and jAsti Aga2 0. Note that Agæı 0 and Aşı² I together with AASti + = 0 imply that
Agæı Agæ2 0 (In order to see this, suppose that aa < for some row ay of A such that j S.
Then we have jaz xi + jaf x2 < which is a contradiction.). Finally, noting c' = ct x2 = implies that [As]
00'
As
[0]
b
and
C
which is a contradiction since x" is the unique solution of this linear bb
system.
Lemma 23 (Rank reduction). Let us denote the Singular Volue Decomposition (SVD) of X as X UEVT
Σ 0
in compact form, where U Ruxr, E E Rexr and V E Brxd and let X - 1U
U-]
u-
VV v-J denole
0
0
the full SVD of X. Then, the following optimization problems are equivalent
m
P2
min woo.wo
Σ 6XW 11 v)
w 12 |
(90)
m (USN (2) () 3) + A
m
P/ = min
| j 12 + ||
(91)
j=1
i.c., p² - Optimal solutions of
90 and
91
satisfy (V-)T = 0, VTw / and w = 157(2)
Mj E [m].
Proof of Lemma
We define ( a [v v- and plug-in the compact SVD of X in the expres-
sion 90
min &
v) +
>
|
112 + 1 || 1
(92)
b
5-1
where we have || 1 II[V
v- = -
12 + |
It can be seen that wa 0 Vj and
VF w Vj.
9.10
Extreme rays of convex cones
In this subsection, we present some definitions and lemmaa related to extreme rays of convex cones (Fenchel
and Blackett 1953 Weyl 1950).
Definition (Rays). Let be a convex cone in Rd. cone R S K called a my of K if (Ar A A 0). for some x K.
Definition (Extreme rays). Lot K be convex cone in Rdd A ray R= (Dx : X 2 0} S K generated by some vector x is called an extreme ray of K if x not positive linear combination of two linearly independent vectors of K.
Lemma 24 (Weyl's Facet Lemma (Weyl 1950 Define the conver cone K (w Rd w Pt 0
{&) C Rd, where p1,..,,t Pk E Rd collection of vectors. Then, a non-zero vector K is element of an extreme ray of K if and only if din Span(p, I' Pt 0, i E [k:) = d.
9.11 Convex Duality and Lasso
Lemma 25 (Lagrange Dual of Lasso). Suppose that K RaxP is matrix whose columns are given by the vectors ki,...,kpp E _ and À > 0 is regularization parameter. Then, the primal and dual optimization
51

---

Published in Transactions on Machine Learning Research (10/2024)
problems for Lasso are given by
min min((Ke,)) + A||z||1
max 0. 10 A.lAAvv(
-()(v)
(93)
Lemma 26 (Lagrange Dual of Lasso with a bias term). Consider the problem in Lemma 25 with an additional bias term. Then, the primal and dual optimization problems for Lasso are given by
min ( + 1b, v) + A|2lll =
max v. 10" Vzse()
(v)
(94)
Σ +=
Proof. Lemma 25 and are are based on standard application of Lagrangian duality (Boyd and Vandenberghe 2004]. Strong duality holds, i.e., the primal and dual problems have the same value which are both achieved. in both problems since u = in the dual problem strictly feasible for the inequalities due to O.
9.12 Optimizing scaling coefficients
Our characterization of the hidden neurons using geometric algebra in Theorem and 17 determine the direction of optimal neurons. The magnitude of the optimal neuron can be analytically determined. In this section, we show that the optimal scaling coefficients are given by the ratio of the norms of the corresponding weights.
Consider the two-layer neural network training problem given below
p² min WOO,way
Σ (XW + 16,) v) A W (1)
(95)
where the activation function is positively homogeneous, ie., ((ax) (x) for 0. Introducing non- negative scaling coefficients o1,..., Om to scale hidden neuron weight and bias, and dividing the corresponding second layer weight by the same scalar we obtain
p²
min W
oXW ag + 1b, a5 .3)
+ x
| 10 - 11
(96)
b
am....0m 20
Ø=1
j=1
m Σ (XW))" + 16,)w/ v1) v) +1 Σ
min ((()w(1))) b
I (1)
|
|| || 1330,
(97)
O1......00m 20
where the last equality follows from the fact that ((x) (x for a > 0. Through simple differentiation, is straightforward show that the optimal scaling coefficients are given by
( le 1/2
aj
for [m].
(98)
9.13 Proof for three-layer networks with inputs of arbitrary dimension
We consider the scalar output three-layer network
f(x) Σ (a ( + w + ((2)) w/(0) + ((3)
(99)
where w E _dxx w E R9x9, W (3) E R, (1) E R2, ((2) R and ((3) R are trainable weights.
52

---

Published in Transactions on Machine Learning Research (10/2024)
9.13.1 Optimal scaling
We now consider optimizing the scaling coefficients for three-layer neural networks. Lemma 27. Consider the three-layer neural network training problem given below
p² -
min wrr
(XX) + b + b(21)) w b(0) ((0),
(100)
m
(101)
The above problem is equivalent to
m ((WW + +640) (4, + +0(2) - +b(0) + .))
min ,
w ( (102)
vj way ,00, ,022)
Consider scalar non-negative weights aı a2 0z satisfying a1ja2ja3 = for j E [m]. Applying the j term E(-) does not change due to the positive homogeneity of ReLU, Optimizing over these scalars, we obtain
Proof.
scaling w(ll) + wn w/() + 022 (( and W/ (x(3 + asyW( for all j E [m], we observe that the loss
)6 + +6(2) ) ( ((3)
p²
min 015,02)003, ER+ (15022031=1113 =1.jf[m
min WOO ((8) W000,6000, [E
(103)
3
1s + a W
|1, 1 1| + a 1
(104)
3 1=1
min 01 01,.03,03;ER;
min W00 000,000kkk(0
(XW + 60)) (60) - + +b69) bb0.
-
(105)
1y002aa.=11Vvee- mm]
( ( (1)))))))) 1/3
ai ai 02 Caj
(106)
m
min wit) kE(3
(X + +600) 6(2) )_ ((3)
(107)
m
[ 1b (1ll W
(108)
where the inequality follows from the AM-GM inequality, which holds with equality when onj |p for all [m], & e [3]. Finally, we scale w3 by |w ||/(22 11 for all E [m]
and obtain the claimed result.
Next, we present the convex dual of the problem in Lemma 27
Lemma 28. The dual of the problem in 100 is given by
d' max
-2"
(109)
"ER"
1 ===
s.t.
max 1,0
T ((XW()) +600), w()) ((2)) S
(110)
The proof of this lemma parallels the proof of Proposition in Wang al. 2022). where it was also shown that strong duality holds, i.., p" d", as long as the number of neurons, m, is sufficiently large.
53

---

Published in Transactions on Machine Learning Research (10/2024)
9.13.2 Proofs for three-layer networks without bias terms
Proof of Theorem
12 We focus on the maximization subproblem the constraints of the dual problem
We the same steps in the proof of Theorem and 17 to maximize over the layer two and three weights while the first layer weights are fixed, and finally maximize over the first layer weights. This
Lemma 28
yields dual constraints analogous to nested version of (87 given by {Z(u) S B, 1 = 0}, where 2 = 2(v) is given by
8 Σ
2 = max max max
(x)) (<TTw)+ - (x] [)) vi
Σ ==1
( - (x] (wTw)+)+*0 vi
(111)
JE(n || 1
max(2 (2 z(1), ,
max
(112)
Here,
z max max $
(af w)+ (x] vi for +-1,
(113)
jE(n) |=||1=1
and
(0 = max max
Σ (( ((x5w)+ w - wx+ vs for (-1,+1}.
(114)
JE(N |=|
We focus z() since the analysis for Z(-1), (((1),x(-11) (() are identical except small changes. Using hyper- plane arrangements of the matrix X, we can write the above problem as
z
max jEIM),E[[]] 1E
max
(DenaTT DkjsajJ w) Ui
(115)
where Di,.... Dp are the P diagonal matrices of the hyperplane arrangement of X and DRu is the i-th diagonal element of the matrix DE. Here Ck is defined as Cs = {w Rd (2D, 1)Xw 2 0}. Now note that Dis = 0 implies that
DRnaf w Diijas w - -1, S..
Therefore, we can write the above problem as
max KE|P
max
Doa (I, w Dujjz 3 w) vi
(116)
wEC W 1=1
max [P
max WECx, W 1==1
oT Dr (Xw Dags Luy w)
(117)
Now we split the above problem into two subproblems by considering the values of Daj-
2(1) max (M,
(118)
where
Mi max
max je(n) Dzy=1 w wcCx. / w|ll=1
DDD ((X )
(119)
and
M2 max
3 Dr.Xw.
(120)
Note that (D&Xw)+ D&Xw, which used to simplify the expression for M2. Now we focus the subproblem M1, by considering the hyperplane arrangements of the matrix X 1xy. Suppose that the
54

---

Published in Transactions on Machine Learning Research (10/2024)
diagonal arrangement patterns of the matrix X - 1xy are given by Hs1.... HyG, and the corresponding convex cones are given by Ff1,-.,,fe Then, we can write the subproblem M1 as
max Mi JM i
max
v² H - 1z) w..
(121)
We also rewrite the subproblem M2 using the same hyperplane arrangements for reasons that will become clear later.
max M2 S wF Ce
max
v² D&Xw..
(122)
Using Lemma
19
we can rewrite the subproblems using the extreme points
Ejke = Ext (Txe) where Tzkt == FfenCe n fwo |w]| 1}.
(123)
as follows
M1
max
max WEE
Dr (Xw Dus)lafw)
(124)
#EEEM
and
M2 =
max jeln)AeIPP.eellI.D..=oooo
max v Dr (Xw- - Dkjj 1x) w) +
(125)
Then, we can write
2(1) wax.axaMaa M2)
D' (Xw Dkis 103 w)
max jc| WEEsRe
max
Σ (1a) w))+ (0) +)
max (E
We now apply the characterization of extreme points from Lemma
19 which shows that
X 12
Ejkt = w E Tike C Rd SS C [m] 1, Mw 0, :
rank(MM = d =d-13
where Tyke is defined in 123 Now we note that for each fixed j [n], the sets {Fş Cx]ke(M)eee are chambers hyperplane arrangements that exhaustively partition Idd, Taking a union over all chambers as the tuple (k: range over [P] [G] gives the entire space Rd Therefore, we have
z
Σ (a w) (2fw)+ 44. 1=1
max jE[m] WEE/CR CRd
where E is defined as
X
E/ w Wd 3S [m),8] = 1, Mw = 0, : =
X - la
rank(M) = -d-1
I
As in the proof of Theorem we identify the elements of the set E/ using the generalized cross product and obtain the following characterization of Z
Z
max jE(n], WEWER
Σ (wf (x)))+)) Us.
where Wj is defined as W3 A {
(5. Jis linearly independent, 18|=d: d -1=-11 and the set of
1xces0911
vectors {a (1) 2n+d are the union of )i (xr - ,, and {e:]a-
The arguments for 2 (1) hold in the same way, and we obtain the following characterization of the dual problem. Using the convex duality of Lasso from Lemma 25 we obtain the claimed convex bidual problem, and the optimal solution is given by the extreme points of the set W,.
55

---

Published in Transactions on Machine Learning Research (10/2024)
9.13.3 Proofs for depth three networks with biases
Proof of Theorem
Consider the dual constraint subproblem
2 max JE[n] 1|
((of w + D)+ - (1² w + b)+)+
(126)
We now focus the maximization with respect to the scalar b when the vector and the index j are fixed. Observe that the objective is piecewise linear function of b, when all other variables are fixed. Therefore, it suffices to check the break points and when B + -00 or 3 + co. The break points are when b such that x! w + for some i E [n]. When B + oo we have
(a w + b)+ - (afj w + b)+ क w + wff b = (x;-- - xz)"" w
for some j.j E [n]. Then, we rewrite the above problem as
z bb) = max (2 2
where T are the maximum value over the break points b xx² w for each i E [n] and 2 is the maximum value when - oc as given below.
(b)
max jE jE(M),EE(n) wilsl
max
Σ (((#; - ((1:;-x)) x)) ((1)) xz)" (e)"w)+++++
(127)
and
_ max max
Σ ((r: - xry) vr) w) Us
JELN ||]||==
Finally we note that by re-labeling the data points as I; f- Ij Dg for some E [m], the problem 2 is equivalent the maximization problem analyzed in the proof of Theorem 12 The rest of the proof closely follows the proof of Theorem 12 and we obtain the claimed result.
56


Reviews:
[{"review_id": "y7PSjutMJ0", "reviewer": "Reviewer_tihS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- To the best of my knowledge the use of Clifford algebra in analyzing neural networks is novel and could pave the way for a new means of analyzing neural networks. \n- The paper provides good evidence for the utility of this insight on real neural networks. \n- The results in the paper hold for both shallow and deep neural networks with different types of regularization.\n\n**Weaknesses**\n- Optimal solutions are only obtained for the $\\ell_1$ regularized case. This is not is not really standard in training neural networks. It would be nice if the paper could provides some insights on the difficulties of proving a similar result in the case $\\ell_2$ regularization. \n- While the optimal neurons are shown to be k-plane products of subsets of the training data it’s still not clear which subset is utilized.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a novel analysis of solutions to the neural network training problem using Clifford algebra and convex optimization. The paper provides closed form expressions for the optimal solutions of $\\ell_1$ regularized neural networks and approximate solutions to $\\ell_2$ regularized ReLU neural networks. This shows that the optimal neurons depend only on a subsets of the training data through their wedge products. The results hold for both shallow and deep networks of arbitrary dimension both with and without biases. Finally, the paper uses these insights to provide an algorithm for “polishing” the neurons of an approximately optimal neural network trained with SGD based on the analysis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think the paper is good and I am willing to accept as is however, I do have a few suggestions which might strengthen it.\n\n- It’s not clear how these results can be translated to the weights of neural network. For example in Theorem 2 the function is expressed as a linear combination of these generalized cross products. Not as ReLU ridge functions. (I think there is an explicit expression for the weights in the proof of Theorem 2 but it would be nice to state it in the main body).\n\n- Some discussion on why the proof is limited to an approximate solution in the case of $\\ell_2$ regularization.\n\n- Fig. 3 shows the break points for the optimal neurons for different architectures. I think it would be interesting to see whether this is what is actually learned when training a neural network on a simple 2D problem.\n\n- What is $\\beta$ in the proof of Theorem 1? Should this be $b$?", "broader_impact_concerns": "This work is primarily theoretical and does not pose any ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VSCXVf1k92", "reviewer": "Reviewer_XQUN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths>:**\n1. The use of geometric algebra to analyze neural networks is a novel and potentially transformative perspective, providing closed-form solutions for optimal weights.\n2. The paper establishes a clear connection between neural networks, convex optimization, and geometric structures, offering new insights into the role of hidden layers and activation patterns.\n3. The analysis is grounded in rigorous mathematical formulations, with detailed derivations and proofs provided for key theorems.\n4. The study extends its analysis across various dimensions and neural network depths, making it broadly applicable.\n5. The results offer a clear geometric interpretation of neural network operations, enhancing the understanding of neuron functionalities.\n\n**Weaknesses:**\n\n1. The use of Clifford algebra and the mathematical depth may be challenging for practitioners without a strong background in advanced mathematics.\n2.  While theoretical insights are well-developed, the paper lacks extensive empirical validation on diverse datasets and architectures, which is crucial for demonstrating practical applicability.\n3. The practical implications of implementing the proposed convex optimization approach on large-scale neural networks are not fully explored.\n4. The assumptions and specific settings required for the theoretical results might limit the generalizability across different types of neural network architectures.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a novel approach to understanding deep neural networks using geometric algebra (specifically, Clifford algebra) and convex optimization. It demonstrates that optimal weights of deep ReLU neural networks can be derived through the wedge product of training samples. The study reframes the training of neural networks as a convex optimization problem over wedge product features, capturing the geometric structure of the dataset. This approach provides insights into the inner workings of deep networks, particularly in terms of hidden layers and neuron functionality.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Detailed comments**\n\n1. The paper effectively sets up the problem and highlights the novelty of the approach. However, it could benefit from a more detailed discussion on the practical implications and potential applications of the proposed method.\n2. The literature review is comprehensive, situating the paper within existing research on neural network interpretability, geometric analysis, and convex optimization. However, a more explicit comparison with other interpretability methods could be beneficial.\n3. The introduction of wedge products and their application in neural networks is well-explained, but additional examples or visualizations could aid in understanding.\n4. The reduction of neural network training to a convex optimization problem is innovative. However, the practical implications of this transformation, especially regarding computational efficiency, are not fully addressed.\n5. The derivations and proofs are robust, but some sections, particularly involving higher-dimensional spaces, may be difficult for readers unfamiliar with the mathematical background.\n6. The numerical examples provided are insightful, but the paper would benefit from more extensive experimentation on real-world datasets. This would help validate the theoretical findings and assess the method’s performance compared to traditional training methods.\n7. The discussion around the geometric interpretation of neurons and the role of hidden layers is compelling and provides valuable insights.\n8. The paper briefly mentions limitations but could elaborate on potential challenges and future research directions, particularly regarding scalability and integration with existing neural network frameworks.\n\nI recommend acceptance of this paper if the authors can revise the manuscript with the following point.\n\n1. Include more experiments on diverse datasets and architectures to substantiate the theoretical claims and assess practical performance.\n2.  Discuss the computational efficiency and potential overhead of implementing the proposed convex optimization approach in practice.\n3. Consider adding more supplementary materials or visual aids to help readers without a background in geometric algebra understand the concepts.", "broader_impact_concerns": "This paper presents a promising and novel approach to understanding neural networks through the lens of geometric algebra and convex optimization. With additional empirical validation and practical insights, it could significantly impact the field of neural network interpretability.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Zph1b99Ztu", "reviewer": "Reviewer_Zaq9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper presents a clear and unified characterization of optimal networks, well-written and easy to follow.\n- The derivation from low-dimensional to high-dimensional cases and from two-layer to deep networks is step-by-step and easy to follow.\n- The interpretation of how neural networks extract representations of data is interesting, refreshing, and novel, based on insights from geometric Cliffor algebra and optimization theory.\n\nWeaknesses:\n\nThe paper’s formulation of regularization term is a bit uncommon. Some experimental details are lacking. There are some errors or inconsistencies in notations.\nSee detailed comments below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an analytical characterization of optimal weights of neural networks using mathematical tools in geometric algebra and optimization. \nAnalyzing ReLU networks with arbitrary depth and width, the paper shows that the optimal weights of a neuron can be expressed by a wedge product of a subset of training samples.\nThis in turn provides an interpretation of neural networks - each neuron calculates the positive distance of the input sample to an affine hull generated by a subset of training points (when using $\\ell_2$ regularization).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Below are some questions and suggestions for the authors to consider.\n\nMajor comments:\n\n- Eq. (2) and (20):\nThe regularization term is the squared sum of the $p$-norm of the weights with some special partition, which seems not a common regularization term in machine learning (except for when $p=2$, which reduces to the $\\ell_2$ regularization). \nCould the authors provide some insights on this?\n\n- The results in the paper show an interesting resemblance to support vector machines, where the optimal solution is defined by a subset of training samples. \nIn SVM, the support vectors, a subset of training samples, define the decision boundary. \nIn this paper, the optimal weights and breaklines of each neuron are also defined by a subset of training samples.\nCould the authors provide some insights on the connection between the two?\n\n- Section 4.1, CIFAR experiment:\n\"After training, we implement the proposed polishing process on the first layer, and re-train the second-layer weights via convex optimization.\"\nHow is the retraining via convex optimization performed? Does the first/second layer refer to the first/second fully-connected layer? \nIn addition, I'm wondering why retraining is necessary. How's the network's performance without retraining?\n\n- How would the analytical results generalize to convolutional layers? Convolutional layer weights are shared across spatial locations, and are sparse if written as a matrix. It's hard to imagine how the optimal weights can be written as a wedge product of training samples in this case.\n\n- In the numerical experiments, I'm curious about the distribution of inner product magnitude between training points and trained weights. \nThe theory says that the optimal weight is orthogonal to a subset of training samples. \nIn the experiments, are the values of the inner product magnitude much smaller for the first $r-1$ samples than the rest?\n\n- I'm curious about the distribution of the subsets of training points defining the optimal weights of each neuron. \nFor a single neuron, are the defining samples all from the same class?\nDo all training points appear equally frequently as defining samples?\nCould the author provide some insights on this?\n\n\nOther minor comments:\n\n- Theorems 6 and 7:\nAre some assumptions missing? Is there any assumption on $m$, $d$, or $c$?\n\n- Below Eq. (17):\nThe definition of $\\kappa$ and $\\kappa_b$ is a bit confusing, because in the text, the subscript ends at $d-1$, but in the definition, it ends at $d$.\n\n- Sec 2.3: Why is $w \\in \\R^d$? If $\\ell$ is a loss function and we have $\\ell(w, y)$, should it be the same dim as $y \\in \\R^n$?\n\n- In Eq (13): It seems that $Z \\in \\R^{\\tilde{n} \\times \\tilde{n}}$ should be $z \\in \\R^{\\tilde{n} \\choose 2}$.\n\n- It might be helpful to explain in Sec 2.2 how $\\ell1$ norm is defined for a multivector.\n\n- Theorem 6: \"The weights of an optimal solution of (22)\" - The equation number refers to a future equation. Should be 20?\n\n- Section 3.5:\nFor the two-layer network, the optimal neurons in the first layer are shown. For the three-layer network, which layer's optimal neurons is being referred to?\n\n- Fig 4(a):\nIs the learning rate on x-axis for the pretraining stage or the re-training stage?\n\n- Repitition:\n\"In our notation, lower-case letters are employed to represent vectors, while upper-case letters denote matrices. We use lower-case letters for vectors and upper-case letters for matrices.\"", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel approach to understanding deep neural networks by leveraging Clifford algebra and convex optimization techniques. All reviewers highlighted the significance and originality of the proposed methods. The use of Clifford algebra offers a new perspective that has not been explored before and can serve as a valuable tool for follow-up work. The main theorems are clearly presented and illustrated with good numerical examples. The results are derived for univariate, multivariate, shallow, and deep settings, providing a comprehensive analysis.

One reviewer noted that while some results, such as the univariate case, are not entirely new, and the optimal neurons for the multivariate case are derived for regularized neural networks, which are less common in practice, the overall contributions remain valuable. The polishing algorithm suggests potential practical advantages of this theory.

Based on the positive evaluations from the reviewers and the potential impact on the field, I recommend accepting the paper.
Decision: Accept (poster)