Approximation Rates and VC-Dimension Bounds for (P)ReLU MLP Mixture of Experts
Authors: Anastasis Kratsios
Haitz Sáez de Ocáriz Borde
Takashi Furuya
Marc T. Law
Venue: Accepted by TMLR ()

Abstract: Mixture-of-Experts (MoEs) can scale up beyond traditional deep learning models by employing a routing strategy in which each input is processed by a single ``expert'' deep learning model. This strategy allows us to scale up the number of parameters defining the MoE while maintaining sparse activation, i.e., MoEs only load a small number of their total parameters into GPU VRAM for the forward pass depending on the input. In this paper, we provide an approximation and learning-theoretic analysis of mixtures of expert MLPs with (P)ReLU activation functions. We first prove that for every error level $\varepsilon>0$ and every Lipschitz function $f:[0,1]^n\to \mathbb{R}$, one can construct a MoMLP model (a Mixture-of-Experts comprising of (P)ReLU MLPs) which uniformly approximates $f$ to $\varepsilon$ accuracy over $[0,1]^n$, while only requiring networks of $\mathcal{O}(\varepsilon^{-1})$ parameters to be loaded in memory. Additionally, we show that MoMLPs can generalize since the entire MoMLP model has a (finite) VC dimension of $\tilde{O}(L\max\{nL,JW\})$, if there are $L$ experts and each expert has a depth and width of $J$ and $W$, respectively.

Published in Transactions on Machine Learning Research (01/2025)
Approximation Rates and MLP Mixture of Experts
Bounds for (P)
A nastasis Kratsios Vector Institute and McMaster University, Canada
kratsion www.oaattmmmmatttommmmmmm
Haitz Sáez de Ocáriz Borde
chri67044 fox. ac. uk
Oxford Universiby, United Kingdom
Takashi Furuya
takashi furshhiffrryo00101 @ggmail. com
Shimane University, Japan
Mare T. Law
marel@nvvddaa.cmm
NVIDIA, Canada
Reviewed on OpenReview: https: // openreview. net/ forum? id= oeg2ncuSPz
Abstract
ofxture-of-Expprts (MoEs) can scale up beyond traditional deep learning models by employ- ing routing strategy in which each input is processed by single "expert" deep learning model. This strategy allows us to scale up the number of parameters defining the MoE while maintaining sparse activation, i.c., MoEs only load a small number of their total parameters into GPU VRAM for the forward pass depending on the input. In this paper, we provide an approximation and learning theoretic analysis mixtures expert MultiLayer Perceptrons (MLPs) with (e)ReLU activation functions. We first prove that for every error level > and every Lipschitz function f [0, 1]" + R, one can construct MoMLP model (a Mixture-o--Expers comprising of (P)ReLU MLPs) which uniformly approximates f to accuracy over [0, 1]"", while only requiring networks of O(E-1) parameters to be loaded in memory. Additionally, we show that MoMLPs can generalize since the entire MoMLP model has a (finite) VC dimension of Ö(L max JW)), , if there are L experts and each expert has a depth and width of J and W, respectively.
carning-theoretic
1 Introduction
With the advent of large foundation models, scaling deep learning models beyond the capacity of a single machine has become increasingly important. Mixture of Experts (MoE) models offer a solution to this challenge through a sparse activation strategy. In MoEs, each input is first routed to one of many expert deep learning models and then processed by that expert. This approach allows MoEs to scale effectively while maintaining low or constant computational cost during the forward pass, only subset of the overall model needs to be loaded into GPU video random-access memory (VRAM) for given input. This has led to MoEs such as Mixtral (Jiang et al., 2024), Gemini (Google, 2023), and several others, e.g. (Jacobs et al., 1991; Jordan & Xu, 1995; Meila & Jordan, 2000; Shazeer et al., 2017; Gun et al., 2020; Tepikhin et al., 2021; Fedus et al., 2022; Barham et al., 2022; Majid Tudisco, 2024), to become a viable solution in scaling up large language models (Radford al., 2018: Brown et al., 2020). However, the analytical and statistical foundations of MoEs in deep learning are less understood compared to their empirical investigations.
This paper adds to the theoretical understanding of this subject by studying MoEs whose experts are (small) multilayer perceptrons (MLPs) with Rel activation function (MoMLPs). A key feature of MoEs is that they can maintain a small/fied /fxee computational cost during the forward pass, for any given input e [0, 1]",

---

experts {fli= Published in Transactions on Machine Learning Research (01/2025)
even if the overall model complexity may be large. Our main result (Theorem 4.1) analyzes the complexity of MoFs when uniformly approximating an arbitrary Lipschitz (Tebesgue) almost-everyw continuously differentiable function f: [0, 1|" + _ by an MoMLP with (P)ReLU activation function to any prespecified error & >>0 O. We focus on the trade-off between the maximum mumber of parameters loaded into VRAM by any expert model { while predicting from any given input, against the total number of experts required to maintain that constant number of activated paramcters in the forward pass. Summarized Table 1, our main result shows that a constant active complexity in the forward pass can be maintained among all experts, but at the cost of an exponentially large number of and regions of specialization {Ci Our complexity estimates are approximately optimal as they nearly match the Vapnik- Chervonenkis (VC) lower bounds derived in Shen et al. (2021). That is, the uniform approximation of an arbitrary such f on [o, with an an error of e > 0, requires at least ((s-n/2) tolal model parameters (Yarotsky, 2018; Kratsios Papon, 2022; Shen et al., 2021; 2022b). It is here where MoEs have an advantage since not all of their parameters need to be loaded into active memory for any given input; thus, MoEs are genuinely sparsely activated.
It is important to note that the results recorded in Table represent the worst-case scenario, meaning they pertain to the most challenging target function within the class of a-Hölder functions. Approximating such a function necessarily requires a large number of experts in the MoE to achieve the desired accuracy, similar to how very large MLPs would be theoretically required. Nevertheless, in practice, one typically does not encounter worst-case functions. MoEs can still perform well even with a small number of experts in the mixture model and relatively few parameters per expert. It is worth noting, however, that analyzing worst-cste scenarios is an interesting research question, separate from the worst-case analysis addressed in this manuscript.
From the statistical learning perspective, a key property of MoEs (e.g. the top MoMLP model) is that they can maintain a given level of activation in the forward pass while the entire MoE model can maintain a finite VC-dimension (Thcorem 4.2). This is key, for instance, in classification applications, as the fundamental theorem of PAC learning (see e.g. (Shalev-Shwarlz & Ben-David, 2014, Theorem 6.7) or the results of Blumer et al. (1989); Hanneke (2016); Brukhim et al. (2022)) implies that such machine learning model generalizes beyond the training data if and only if it has finite VC dimension.
Summary of Contributions Table summarizes main contributions, both to the approximation theory and learning theory of MoE models, in the context of the toy mixture of (P)ReLU MLP models. All results illustrate the trade-off between individual (expert) complexity and the complexity shared across the set of experts when uniformly approximating a target o-Hölder function; 0 < a 1.
Our approzimation theorem (Theorem 4.1) records the number of parameters required to perform a uniform approximation on a digh-dimensiona Euclidean space on [0, The first result juxtaposes the complexity of each expert (PReLUU MLPP) against the total number of experts required to achieve given level of approximation accuracy. The user controls the number of experts vs. the complexity of each expert using hyperparameter E I. As shown in Table 1. Small values of < 0 encode the "few large experts regime", whereas large values of 0 < capture the "many small experts regime".
Our statistical learning guarantee result (Theorem 4.2) yields a bound on the VC dimension of the entire class of MoEs with just enough approximation power to perform this approximation. As summarized in Table 1, the result quantitatively shows the degradation of model generalization as the number of experts increases; i.c r becomes large.
Observe that, setting r r= 2 in Table 1, yields for ReLU MLPs derived in Yarotsky (2017); the optimality of which is expressed in terms of VC dimension in Shen et al. (2022b). Likewise, the VC dimension of the MoMLP is roughly cqual to that of ReLU MLPs computed in Bartlett et al. (2019).
2
Related Work
Deep Learning Models with Few Parameters in Active Memory. Deep learning models with highly oscillatory
activation functions (Yarotsky & Zhevnerchuk, 2020; Yarotsky, 2021;
2

---

Published in Transactions on Machine Learning Research (01/2025)
Table 1: No. Parameters and VC-Dimension of MoMLP with no. experts-to sxpertsto-ezperte compleiiy parumeter E (-oo, ]: performing an 0 < E S approximation of an a-Hölder function f [0. 1J" + I; n E N. When 2 0 more model complexity distributed across many "small experts". When r < 0, fewer experts define the MoE and, as a result, each expert MLP must depend on more parameters such that the entire MoE obtain an accurate approximation of the target function. We also record the total number of parameters defining the MoMLP, including those which are not loaded in the forward pass but can be stored offine.
Parameter
Estimate
No. Parameters Per Expert
((max(1,E-7)
No. Experts
0 ((max(1, 21//2//111//))
Parameters MoMLP (Offline)
( (1, r max (1, ( 22//))1/a3)
VC Dimension MoE
Ö max (n, 2/// 1/0} maxx(22/nn1//4) {-),))))
Zhang et al., 2022) are known to achieve dimension-free approximation rates, thus effectively require a (relatively) feasible number of parameters to be loaded into VRAM during the forward pass. As we will see in Proposition 4.4, many of these models have an infinite VC dimension even when they are restricted to having a bounded depth and width; see Jiao et al. (2023, Lemma 3.1) for ReLU-Sin-2" netwoorss.. Their unbounded VC dimension implies that the classifiers implemented by these models do not generalize classification problems. ceteiimmmaiiotttoeettte optima
Thus, the real performance of these models does not need to achieve the since they can only learn from finite number of noisy training instances. Alternatively, a feasible number of parameters in deep learning models with standard activation functions may be guaranteed by restricting classes of behaved target functions such as Barron functions (Barron, 1993). functions of mixed-smoothnee (Suzuki, 2018), highly smooth functions (Mhaskar, 1996; Galimberti et al., 2022; Gonon et al., 2023; Opschoor et al., 2022), convex functions (Bach, 2017), functions with compositional structure (Mhaskar et al., 2017), or other restricted classes. However, there are generally no guarantees that target function encountered in practice has the necessary structure for these desired approximation theorems to hold.
Universal Approximation in Deep Learning. Several results have recently considered the expression power of deep learning models. These include universal approximation guarantees for MLPs (Cybenko, 1989;
Hornik et al., 1989; Lu et al., 2017; Suzuki, 2018; Yarotsky, 2017; 2018; Voigtlacnder & Petersen, 2019;
Boleskei et al., 2019; Gühring el al., 2020; De Ryck el al., 2021; DeVore et al., 2021; Daubechies al., 2022; Kratsios & Zamanlooy, 2022; Zhang al., 2022; Opschoor al., 2022; Zamanlooy & Kratsios, 2022; Shen et al., 2022b; Cuchiero al., 2023; Voigtlaender, 2023; Benth et al., 2023; Mao & Zhou, 2023; Yang & Zhou, 2024), CNNs (Petersen & Voigtlaender, 2020; Yarotsky, 2022), spiking neural networks (Neuman & Petersen, 2024), residual neural networks (Tabuada & Gharesifard, 2021), transformers (Yun et al., 2019; 2020; Kratsios & Papon, 2022; Fang et al., 2023), random neural networks (Gonon et al., 2023), recurrent neural network models (Grigoryeva & Ortega, 2018; Gonon & Ortega, 2021; Hutter et al., 2022; Galimberti et al., 2022; hoon Song et al., 2023), and several others. In each these cases, one typically considers the expressivity of a single "export" model and not a mixture thercof. Our analysis can be customized to any of these settings to yield analogues of Theorem 4.1.
Foundations of MoEs. MoE models have been heavily studied since their inception. Most results have focused on identifying the correct expert to best route any given input to (Teicher, 1960; 1963; Wang et al., 1996), the construction of effective routing mechanisms (Wang el al., 2017) selection (Wang et al., 1996), MoE training (Larochelle et al., 2009; Akbari et al., 2024), statistical convergence guarantees for classes of MoEs (Chen, 1995; Ho et al., 2022), robustness guarantees for such models (Puigcerver et al., 2022), amongst several other types of guarantees. However, our knowledge, there are no available approximation guarantees for MoF or VC-dimension bounds for deep-learning- based MoFs. Thus, our results would be adding to the approximation theoretic foundations of MoE models well as to the statistical foundations of deep-learning- based MoEs.
3

---

Published in Transactions on Machine Learning Research (01/2025)
Prototypes and Partitioning. Each region in our learned partition of the imput space is associated with a representative point therein called a prototype. Prototypes (also called landmarks) are routinely used in image classification (Mensink et al., 2012), few-shot learning (Snell et al., 2017; Cao et al., 2020), dimensionality reduction (Law et al., 2019), in complex networks Reeller-Resse & Nargang, 2023), and geometric deep learning (Ghadimi Atigh et al., 2021) to tractably encode massive structures. They are also standard in classical clustering algorithms such as K-medoids or K-means, wherein the part associated with each medoid (resp. centroid) defines a Voronoi cell or Voronoi region (Voronoi, 1908). Moreover, while partitioning is commonly employed in deep learning for various purposes, such as proving universal approximation theorems (Yarotsky, 2017; Lu et al., 2021b; Gühring & Raslan, 2021) or facilitating clustering- based learning (Zamanlooy & Kratsios, 2022; Trask et al., 2022; Ali & Nouy, 2023; Srivastava et al., 2022), existing approaches typically involve loading the entire model inlo VRAM. Our approach, however, differs by relying on a learned partition of the input space, where each part associated with a distinct small neural network. Importantly, the complete set of networks forming the MoMLPs does not need to be simultancously loaded into VRAM during training inference.
Paper Overview. Our paper is organized follows. Section 3 contains preliminary notation, definitions, and mathematical background required for the formulation of our main results. Section 4 contains our main approximation (Theorem 4.1) and learning theoretic (Theorem 4.2) guarantees. Section 5 dives into the details of why MoEs can achieve arbitrary precision while maintaining a feasible active computational complerity by explaining the derivation of our main approximation theorem; the details of which are relegated to Appendix B. A technical version (Theorem 5.3) of our main approximation guarantee is then presented, which allows for the approximation of continuous functions of arbitrarily low regularity and for the organization of the experts defining the MoMLP via decision tree implementing the indicator function to a Voronoi diagram of [9, 1]d. Section 6 contains technical derivations of our main results well experimental elucidation of the benefit of MoEs, and specifically the toy MoMLP model.
3 Preliminaries
We standardize our notation, define the necessary mathematical formalisms to state our main results and define our toy MoE Model.
Notation We use the following notation: for any fig: R R, we write f E O(g) if there exist xo E R and M 2 0 such that for each x 2 Do we have [f(z) < Mg(xv). Similarly, we write f E 2ggg) to denote the
relation g E O(). The ReLU activation function given for every x E R by ReLU(<) = max (a, 0}. For
each n N_ and C C R", the indicator function le of C is defined by: for each x E R set Ie(x) 1 if E C and is 0 otherwise.
3.1 Background
Multi-Layer Perceptrons We will consider MLPs with trainable PReLU activation functions. Definition 3.1 (Trainable PReLU). We define the trainable PReLU activation function o : :R + R for each input and each parameter y as follows:
(x)x) def a(x,7) def x
if 2 0, otherwisc.
72
PReLU generalizes ReLU since ReLU(x) = oz(2), and it makes the hyperparameter y of Leaky ReLU learnable. We will often be applying our trainable activation functions womponent-wise. For positive integers
n, m, we denote the set of n x m matrices by R=xm More precisely, we mean the following operation defined for any N E N, 7 E N with ith entry denoted as 7. and x E RRA, by
N Ogy T def (a%, (x:))
4

---

Published in Transactions on Machine Learning Research (01/2025)
We now define the class of multilayer perceptions (MLPs), with trainable activation functions. Fix J N and a multi-index [d] def (do,..., ds+1), and let P((d) = Ej dj(d/+1 1 + 2). We identify any vector E IR P(d)) with
0 + (A 600, ,,),)))))))) y(0) and (A (6), ((0)) R x R R
(1)
We recursively define the representation function of a [d] dimeennnni network by for j = 0, J....,J-1
P((4) x Ro e (0,z) fo(x) def A x + 6(0)
x (i+t) def ORUB (A x9ح + b(i)) (0)
(2)
We denote by NN [d] the family of [d] adleeimenio mullilayer perceptrons (MLPs), (fobDERP(a) described by equation 2. The subset of NVV(a consisting of networks Sa with each 7( (1,0) in equation 2 is denoted by NN and consists of the familiar deep ReLU MLPs. The set of ReLU MLPs with depth J and width W is denoted by NN = Uia NV [d): where the union is taken over all multi-indices [d] = [do....,d .dy with n do, m ds+1, do....,, d,- W, and J J.
VC dimension Let F be set of functions from a subset X [ R2 to f0, 1}; i.c. binary classifiers on X. The set F shatters (in the classical sense) k-point subset {x C X if F can represent every possible set of labels on those k-points; i.e. if # ((f(x:)) E (0.1)* F]
As in Shen et al. (2022b), extend the definition of shattering from binary classifiers to real-valued functions as follows. Let JF be a set of functions from [0, 1]" to R. The set J is said to shatter a k-point set } S X if
(1,00) f:: fEF]
(3)
shatters it, i.e. if all possible classifiers on {x:)==1 are imple- mentable in the sense that (1 o ff f F = f0, 1) (m))::;; here (1) = 1 if >> 0 and equals to 0 otherwise. Denoted by VC(F), the VC dimension of F is the cardinality of the largest k-point subset shattered by F. If we say that FF has an infinite VC dimension (over X). One can show, see Bartlett al. (2019), that the VC-dimension of any such F is roughly the same as the pseudo-dimension of Pollard (1990) for small modification of F.
P
unbounded, then
P5
VC dimension measures the richness of a class of functions. For example, in Harvey et al. (2017, Theorem 1), the authors showed that the set of MLPs with ReLU activation function with LE N layers, width and W e N4 satisfying > O(L) C2, where C 640, satisfics
VC(NNW.LL) 12(w WL logz (W/L))
Load Network Attribttdd to Nearest Protorype to
(4)
Nearly matching upper bounds are in Bartlett et al. (2019).
-> ff(()
Definition: Our Toy Mixture of Experts Model We study the following toy MoE. model, where each expert ReL MLP specializes
Figure 1: 1) The distance from each input to all prototypes Pi,...,Ps (t 8) is queried. 2) The network (fz in the figure) as- signed to the nearest prototype (p2), loaded onto the GPU and used for prediction.
distinct region of the input domain [0, 1]". the sets
Informally, these regions Ci,..., Ce correspond of closest points (Voronoi cells) from finite set. of proto- types/landmarks p1,-...P in [0, 1]", as illustrated in Figure 1. Associated to each region C, is a single expert MLP f. with ReLU activation function responsible for approximating the
5

---

Published in Transactions on Machine Learning Research (01/2025)
target function only thereon. Here, the sparse gating procedure which routes any given input x E [0, 1] to the expert corresponding to the nearest prototype Pt is implemented by a (finite) rouling tree T (V, F)) whose nodes V are points in [0, 1J" and leaves (terminal nodes) are the points Pt....,Pt.
We now formally define the classes of MoMLPs.
Definition 3.2 (MoMLPs). Let J, W, L, n E N and fix an activation function a E C(R). The set of MoMLPs with at-most leaves, depth J, and width W, denoted by N.P. Le,. consists of all functions f R." -> R satisfying f Σ Ic. where for fI....,fr. ft. E NNPPRe and distinct prototypes PI. E R"; inducing the Voronoi colls {C:H-m where
c CACCG 328
(5)
where for i = 1,..., L the (non-disjoint) cells are
0 {i E [0,
|| p:ll = min ||= pjll]-
(6)
je()......)
The Routing Trees The structure in any MoMLP is any tree with root node R" and leaves given by the pairs {(pt, fi) or equivalently (:) The purpose of any such tree is simply to efficiently route an input I2" to one of the L "leaf networks" (the experts) fi....,fu using ([)og(L)) queries; to identify which Voronoi cells {CiY/n the point x is contained in. We leave the precisc set of querics exccuted by the routing tree T abstract so as to allow for maximal design freedom. However, we do ask that T encodes a decision tree executing a sequence of queries at each node along a branch which implements the following function, routing any x [0, 1]d to its nearest cell in the disjoint Voronoi cells {Gi}; Le. T implements
Rdd 3 x Σ Lea, E [4].
1=1
Example (Toy Implementation of equation on Real Line). Set d 1, consider the prototypes [1/8,3/8, 5/8, 7/8), and queries (z) def I(xx-11 < |z - 3/44), (2,) def I( - 1/8] < |x - 3x-3/))), and f2.2 det. I[[ 5/8] < |-- 1---77 7/81). The docision tree in Algorithm 1 implements equation 7.
Remark 3.3 (Partitioning in equation 5 in classical computer science). The partitioning technique used to define equation 5 is standard, see e.g. Krauthgamer et al. (2005, Proof of Lemma 1.7; page 846). It is employed to ensure disjointness of the Voronoi cells; this guarantees that no input is assigned multiple prototypes. To keep notation tidy, we use NPP (resp. NW.,), to abbreviate NP),, J.W.m.m (resp. NW....,,) whenever and are clear from the context.
4 Main Results
A Agorith 1: Routing Tree from Exam- ple 1.
We first present our main approximation theoretic guarantee, which gives complexity estimates for mixtures of MLPs with trainable PReLU activation ion functions when uniformly approx- imating arbitrary Freall--Hllde function on the closed unit ball of R", defined by (0, 1) def E ||=||| < 13.
1
if 91,1 = 1 then
2
22,1 = 1 then
3
Index +-
else
Index 2
Our rates depend on a "number of experts-to-expor complex- ity trade-off parameter" r E I which determines how fast the overall MoE complexity scales, in terms of the number of ex- perts and the complexity of each expert, as the approximation error becomes small. Sctting r < 0 implics that more model complexity will be loaded into each expert MLP and there will be fewer experts defining the MoE. In contrast, setting r > 0 loads less complexity each expert MLP at the cost of more 13 end if experts in the MoE. In particular, when r 0, each expert will have constant complexity even when the approximation error becomes arbitrarily small.
6
end if
7 clsc
if 22,2 1 then
Index +- 2
else 10
11
Index + 3
12
end if
6

---

Published in Transactions on Machine Learning Research (01/2025)
Theorem 4.1 (Trado-Off: No. Expert vs. Expert Complexity). Suppose that satisfies Definition 3.1. Fir
"namber of eaperts-lo-enne expert complenity trade-off parameter" R. For every a- o-Hööder map f (0, 1) - I with S and each approzimation error E O, there a p E M4, binary tree T = (V.E) E) with leaves C am 0 - (0, x I& and a family of MLPs with (P)ReLU activation function {fe defined by parameters and mapping R" to IR" satisfying:
| well E 00s5/a-2r//) (0.1) (1,
max
min
and for each x E (,, and = 1,..., .....,,,,,,, L, is 1100 - will < 5 then
llf(z) - fe. (x)] <E.
The depth and width of each fo. and the number of leaves, height, and number of nodes required to build the binary tree are all recorded in Table 1.
A more general version of Theorem 4.1 is presented below Theorem 5.3. In this version of our main approximation theorem, the target function be any arbitrary continuous function defined on non-empty compact subset of R", and the routing tree can be v-ary for any natural number 2 2.
Next, we demonstrate that the MoML.P model can generalize and generate functions that are PAC-learnable, thanks to its finite VC dimension. This property, however, breaks down in MLP models with super-expressive activation functions.
Theorem 4.2 (VC-Dimension Bounds for MoMLPs - MoMLPs Can Generalize). Let J. W, L, n E N4. Then VC (NAPReLL J.W.L.n.1))
is of OL Log(2 max log(), JW? JW?
(8)
In particular, VC L.W. < co.
4.1 Discussion
Trade-off between Number of Experts and Expert Complexity. Our results suggest that, theoretically, successful MoE models may not need each expert to be highly overparameterized if there enough experts. This hypothesis is ablated experimentally in Section 6 in the context of irregular function approximation in low-dimension space; which is equivalent to high-dimensional regular function approximation (sce Appendix C for discussion on this later point).
Pruning. Additionally, one might consider the option of pruning a sizable model, conceivably trained on a GPU with a larger VRAM, for utilization on a smaller GPU during inference as an alternative our method. Nevertheless, in frameworks like PyTorch, pruning does not result in reduction of operations, acceleration, diminished VRAM memory usage. Instead, pruning only masks the original model weights with zeros. The reduction in model size occurs only when saved in offline memory in sparse mode, which, in any case, is not significant concern.
Logarithmic number of queries via trees. For many prototypes, as in our main guarantee, the MoMLPs only need to evaluate the distance between the given input and a logarithmic number of prototypes specifically, one for each level in the tree-wree given machine never processes the exponential number of prototypes, and only [K)] prototypes are ever queried for any given input; when trees are y-ary (as in Theorem 5.3), and where K denotes the number of protolypes. Since we consider that protolypes are queried separately and before loading MoMLPs, we do not take them into account when counting the number of learnable parameters. Moreover, the size of our prototypes is nogligible in our experiments.
using deep binary trees to hierarchically refine the Voronoi cells. Thus, a
Functions which can be approximated by MoEs with small numbers of experts. Our theoretical analysis adopts worst-case perspective, focusing on the most fifficut-to-approxing given a-Hölder class. Consequently, the number of experts in the MoE can become very large. However, this is often not the case in practice or in our experiments presented in Section 6. We anticipate that favorable
function within a
7

---

Published in Transactions on Machine Learning Research (01/2025)
Table VC Dimension the MoMLPs, ReLU MLP, and MLP model with Expre-xxreesivve Activation function of
Shen et al. (2022a). All models have depth J, width W, and (when applicable) L leaves; where J, W, L, n E N
Model
VC Dim
Ref.
MoML.Ps
0 loog(T))) log(T), Joglo)
Thrm 4.2
ReLU MLP
OJJW2
Bartlett et al. (2019)
Super-Expresse
Prop 4.4
approximation guarantees can be achieved with only small number of expert ReLU MLPs, each having limited number of non-zero parameters. Similar to the approximation theory for ReLU MLPs, expect this to hold when the target function is sulficiently smooth, such as functions belonging to certain Besov spaces (Suzuki, 2018; Gühring & Raslan, 2021; Siegel & Xu, 2022), or when the function's 's structure aligms well with that of deep neural networks (Mhaskar et al., 2017; Cheridito et al., 2021b). Exploring these scenarios represents an interesting research direction that complements the worst-case analysis presented this manuscript.
4.2 Application: Controlling The Complexity in VRAM maintaining a Finite VC Dimension
Expeer-xppessive Activation Functions Have Infinite VC-Dimension. We complement the main result of Bartlett al. (2019) by demonstrating that the class of unstable MLPs (Shen et al., 2022a) possesses infinite VC dimension, even when they have finite depth and width. Thus, while they may serve gold standard from the perspective of approximation theory, they should not be considered benchmark gold standard from the viewpoint of learning theory.
We consider mild extension of the exper-exp activation function of Shen et al. (2022a). This parametric extension allows it to implement the identity map on the real line as well as the original super-cxpressive activation function thereof.
Definition 4.3 (Trainable Super-Expressie Expressive Activation Function). A trainable action function o R x + R is of super-expressive type if for all 7 E R
on : 7x (1-
where a² R R. is given by
mod(2))
(-0,0)))))
(9)
|x
Proposition 4.4 (MLPs with Super-Expressive Activation Do Not Generalize). Let F be the set of MLPs with activation function in Definition 4.3, depth at-most 15, and width at-most 36m(2n + 2). Then VC(F) oo.
The VC dimension bounds for the standard MLP model, MLP with a super-expressive activation function as proposed by Shen et al. (2022a), and the MoMLP model are summarized Table 2.
5 Overview of Derivation
We now overview the proof of our main result and its full technical formulation. These objectives require us recall definitions from the analysis of metric spaces, which were not required in the statement of our main result but which are required when overviewing our proof.
5.1 Technical Definitions
The metric ball in (X, d) of radius at N' is denoted by (z), det. {2 X: d(x,2) <r). < metric space (X, d) called doubling, if there is N_ for which every metric ball in (X,d) can be covered
A
8

---

Published in Transactions on Machine Learning Research (01/2025)
by at most C' metric balls of half its radius. The smallest such constant is called (X, d)'s doubling number, and is here denoted by C(x,a)- Though this definition may seem abstract at first, Heinonen (2001, Theorem 12.1) provides an almost familiar characterization of all doubling metric spaces; indeed, K. is doubling metric space and only can be identified via a suitable invertible map' with a subset of some Euclidean space. Every subset of RR, for any E N+, is a doubling metric space; see Robinson (2011, Chapter 9) for details. Example 2 (Subsets of Euclidean Spaces), Fix a dimension E N.. The doubling number of any subset of Euclidean space is at most 2n+1
In what follows, all logarilhms will be taken base 2, unless explicitly stated otherwise, i.e. log, base for given v E N- and log = logz- As in Petrova & Wojtaszezyk (2023, page 762), the radius of a subset A C IR", denoted by rad(A), is defined by
rad(A) def. inf sup || all- a
(10)
The diameter of any such set A, denoted by diam(AA, satisfies the inequality diam(() S 2 2rad(A).
Finally, let us recall the notion of uniformly continuous function. Fix n, m E N4 and let X C R". Let w: : [0, oo) + [0, oo) be a monotonically increasing function which is continuous al 0 and satisfies w - 0.
Such an w is called modulus of continuity. A function f - R= is said be w-uniformly continuous if
ff(x) f(vil S ((1 10--)1) -ll)
holds for all y X. We note that every continuous function is uniformly continuous if X is compact and that its modulus of contimuity may depend on X. Furthermore, note that every (a, L)-Höderr function is uniformly continuous with modulus of continuity w()) = Lt
5.2 Helping to Explain MoEs via Proof Sketch
Lemma 5.1 (Size of Tree Whose Nodes Form 8-net of Compact Subset of R²). Let K. be compact subset of R whose doubling ramber is C. Fix E N with 2 2, and 0 < å I rad(K). There exiits an v-ary
tree T del. (V, F.) with leaves L C satisfying
max min ||x - 2/| BEK FEL
(11)
Purthermore, the number of leaves L def. #G, height, and total reumber of nodes #V of the Iree T are
(i) Leaves: at most L ul lox(C) (1+1og(8 ddiam(K))))
(8) Height: [c log(C)) [1 log(6 -ogg@11aa diam (IC)))]:
(ml) Nodes: At most wle lox(C) loo (ia))())) 11_1
clog(C) log(A diam(()))
where
del.
1/ l/g)
At each node of the tree, we will place an MLP which only locally approximates the target function on little ball of suitable radius (implied by the tree valency and height h) of lemma 5.1. Le. by the storage space we would like to allocate to our MoMLP model. The next step of the proof relies on mild extension of the quantitative universal approzimation theorem in Shen et al. (2022a); Lu et al. (2021a) to the multivariate case, as well as an extension of the multivariate approximation result of Acciaio et al. (2023, Proposition 3.10) beyond the Hölder case.
Lemma 5.2 (Vector- Valued Universal Approximation Theorem with Explicit Diameter Dependence). Let n, m E N with n 2 3, K. C R" be compact set of radius 8 2 O, f Rm be uniformly continuous with striclly monolone continuous modulus of continuily w. Lei a an activation function as in Desinitions 4.3
IS called quasi-symmetric maps, Heinonen (2001, page 78).
28ee Robinson (2011, Lemma 9.2) and the brief computations the proof of Robinson (2011, Lemma 9.4).

---

Published in Transactions on Machine Learning Research (01/2025)
3.1. For each > O, there crists an MLP fo :R - m with trainable activation function satisfying the uniform estimate
sup llf(x) fo(x)l e. aek:
The depth and width of f are recorded in Table 3.
Table 3: Complexity of the MLP fo in Lemma 5.2. See Table 7 in Appendix A for more detailed estimates.
Activation o
Super Expressive 4.3
PReLU 3.1
Depth (J)
((1)
(((6/w 0(1)
Width (max, dz)
(
Combining Lemmata 5.1 and 5.2 we obtain Theorem 4.1. We now present the technical version Theorem 4.1. This result allows distributed neural computing using v-ary trees and allows for the approximation general uniformly continuous target functions.
Theorem 5.3 (Trade-Off: No. Expert vs. Expert Complexity Technical Version Theorem 4.1). Suppose that a satisfies Definition 3.1. Let K. be a compact subset of R whose doubling number is C. Fir an "number of caperts-lo-empert complecity trade-off parameter" For every uniformly continuous map f K. 12 with modulus of continuity and each approzimation error 0, p e N+, there is an v-ary tree T det. (V.E) with leaves det. ([v,,0,)<= C E2 and a family of MLPs with (P)ReLU activation function {fo defined by p parameters mapping IK to R" satisfying:
TR and "valency porameter"
N with 2 2.
(|x-v:h ws|l < E g22//n
max min (o.0.))C
w
zER
2
131 (nm)
and for each x E K. and i l,..., L, if ||ee vill < 8 then
llf(x) - (o)(l)) <E
The depth and width of each fo, and the number of leaves, height, and number of nodes required to build the v-ary tree are all recorded in Table
6 Does one Need Overparameterized Experts if there are Enough Experts?
We evaluate our approach in two standard machine learning tasks: regression and classification. We experimentally show that MoMLPs, which distribute predictions over multiple neural networks, are competitive with single large neural network containing many model parameters all the MoMLPs combined. This is desirable in cases where the large neural network does not fit into the memory of single machine. On the contrary, the MoMLP model can be trained by distributing each MoMLPP on separate machines (or equivalently serially on single machine). Inference can then be performed by loading only single MoMLP at time into the GPU.
6.1 Regression
We first consider regression, where the goal is to approximate non-convex synthetic functions often used for performance test problems. In particular, we choose 1-dimensional Hölder functions, as well as Ackley (Ackley, 1987) and Rastrigin (Rastrigin, 1974) functions, whose formulations are detailed in Appendix D.1.
1D Hölder Functions. We illustrate our primary finding, as encapsulated in Theorem 4.1, by leveraging 1-dimensional functions characterized by very low regularity. This choice is motivated by the jagged structure inherent in such functions, necessitating exponentially higher sampling frequency compared to smooth
10

---

Published in Transactions on Machine Learning Research (01/2025)
Comparison Functions of Low High Hölder Reguiarity
1.5
ro (Hig Reg. Smooth)
1.0
(Browrian Motion)
(Low Reg. Rough)
0.5
-1.0
-1.5
0.0
0.2
0.4
0.6
0.8
1.0
Nigure2 2: Visual Comparison of Functions with High (a 1) Low (a Hölder regularity. of the function (green) is approximately differentiable almost everywhere, meaning it does not osculate much locally and thus is simple approximate. If & 0, the function may be nowhere differentiable and jagged; its extreme details make it difficult to approximate.
50
60
-05
13
(a) Ground truth Ackley (b) Ground truth Rastrigin
-14
(6) Predicted Ackley
(d) Predicted Rastrigin
(e) log MSF
( log MSE
Figure 8: Comparison of ground truth and predicted results for 2D Ackley and Rastrigin functions over the domain 1]..
functions for achieving accurate reconstruction. Indeod, this crucial sampling step forms the foundation of many quantitative universal approximation theorems (Yarotsky, 2017; Shen et al., 2021; Kratsios & Papon, 2022). As elaborated in Appendix C, approximating well-behaved (Tipschitz) function in d dimensions poses a challenge equivalent to approximating a highly irregular function (1/d-Hölder) in a single dimension. A visual representation of a 1 1/d-Hölder function is presented in Figure 2, excmplified by the trajectory of fractional Brownian motion with Hurst parameter of a = 1/d. formal definition available Appendix C.
2D and 3D Functions. We select the Ackley and Rastrigin functions, with their respective 2D representations showcased in Figure 3, as widely recognized benchmarks in the field of optimization.
Evaluation protocol. We consider the setup where the domain of a function that we try to approximate is the n-dimensional closed set [a, b)". For instance, we arbitrarily choose the domain [o, 1] when n = 1, and [-1, when n 2 2. Our training and test samples are the s" vertices of the regular grid defined on [a, 6)". At each run, 80% of the samples are randomly selected for training and validation, and the remaining 20% for testing. During training, for a given and fixed set of K prototypes p (pI..... .Pk), we assign each training
11

---

Published in Transactions on Machine Learning Research (01/2025)
sample to its nearest prototype Pk and associated neural network fu. We learn the prototypes explained in Appendix D.2. For simplicity, we set the number of prototypes to K = 4; we also set 10, 000 if n = 1, = 150 if n 2 be found in Appendix D.
2 (i.e., 150²= = 22, 500 samples), and = 30 if n = 3 (i.e., 27, 000 samples). More details can
Test performance. In Table 4, we present the mean squared error obtained on the test set across 10 random initializations and various splits of the training tetiiing/eetttteee test sets. The baseline consists of a single neural network with the same overall architecture as each MoMLP but possesses as many parameters as all the MoMLPs combined. In all instances, the MoMLP model demonstrates significant performance advantage compared to the bascline. Figure 3 illustrates the predictions generated by our MoMLPs, showcasing the capability of our approach to achieve a good approximation of the ground truth functions.
6.2 Classification
Datasets. We evaluate classification on standard image datasets such CIFAR-10 (Krizhevsky & Hinton, 2010), CIFAR-100 100, and Food-101 (Bossard et al., 2014), which consist of 10, 100, and 101 different classes, respectively. We use the standard splits of training/ traningg//stttta test sets: the datasets include (per category) 5,000 training and 1,000 test images for CIFAR-10, 500 training and 100 test images for CIFAR-100, and 750 and 250 for Food-101.
Training. Our MoMLP model takes input latent DINOv2 encodings (Oquab et al., 2023) of images from the aforementioned datasets. Each sample x E R corresponds to DINOv2 embedding (i.e., n 768). Additionally, we set the prototypes as centroids obtained through the standard K-means clustering on the DINOv2 embedding space. The replacement of our original prototype learning algorithm is sensible in this context, as we operate within a structured latent space optimized through self-supervised learning using large-scale compute and datasets.
Due to the potential class imbalance in the various Voronoi cells formed by the prototypes, we utilize two variations of the cross-entropy loss for each MoMLP fr. The first variation, termed unweighted, assigns equal weight to all categories. The weighted variation assigns weight that is inversely proportional to the distribution of each category in the Voronoi cell defined by the prototype pk-
Test performance. We present the Lest classification accuracy over 10 different runs (with random initialization) of both the baseline and our MoMLPs in Table 5. The weighted version performs slightly better on datasots with a large number of categorics. Nonetheless, our approach achieves comparable results with the baseline (i.e., no difference with statistical significance), effectively decomposing the prediction across multiple smaller models while requiring less VRAM per neural network. We report the same type of experiment on the CIFAR datasets at the pixel level in Appendix D.4.
6.3 Discussion
Our experiments in the above subscctions demonstrate that MoMLPs can outperform match the performance of a single large neural network with the same overall architecture and equivalent total number of parameters, which aligns with our theoretical insights. This advantage is particularly significant in scenarios where single large neural network cannot be stored on given machine or cluster due to its high VRAM requirements, a common challenge in the context of large language models and other recent large-scale models. While this work focuses on smaller-scale experiments, we believe our theoretical framework represents an important initial step toward addressing and understanding these challenges from a mathematically principled perspective.
Table 4: Test mean squared error (average and standard deviation) for the different functions of the regression task.
ID Hölder
2D Ackley
3D Ackley
2D Rastrigin
3D Rastrigin
MoMLPs (ours)
0.057 1 0.085
0.00015 - 0.00006
0.00068 + 0.00010
0.0480 + 0.0073
1.0062 + 0.0446
Baseline
0.128 + 0.012
0.08723 = 0.01059
0.09303 = 0.03156
3.0511 + 0.3581
8.0376 = 4.0499
12

---

Published in Transactions on Machine Learning Research (01/2025)
Table Test classification accuracy using DINOv2 features as imput (average and standard deviation).
Dataset
CIFAR-10
CIFAR- 100
Food-101
Ours (weighted)
98.40 = 0.05
90.01 + 0.11
91.86 + 0.10
Ours (unweighted)
98. 42 = 0.04
89.62 + 0.25
91.79 + 0.16
Bascline
98.45 = 0.06
89.85 + 0.17
91.45 +: 1.09
The concept of decomposing single large neural network into multiple smaller models that run in parallel has been successfully applied in domains such as computer vision, as demonstrated in works like (Ren el al., 2024; Song et al., 2024). However, existing studies in the literature are largely empirical and application-focuse focuseed, lacking the theoretical approximation rates provided by our work.
7 Conclusion
We presented approximation- and statistical foundations for MoEs by analysing the MoMLP model. We found that MoML.Ps can achieve arbitrary uniform approximation accuracy of continuous functions on compact subsets of Euclidean space while maintaining feasible number of parameters in active VRAM memory (Theorem 5.3). However, this naturally comes at the cost of requiring exponential mumber of experts. We obtain upper bounds on the VC dimension of the MoMLP model (Theorem 4.2), akin to the results of Bartlett et al. (2019) for ReLU MLPs, showing that deep-learning- based MoEs can generalize.
8 Acknowledgment and Funding
The authors thank Gabriel Conant, James Lucas, and Rafid Mahmood for their helpful feedback while preparing the manuscript.
AK acknowledges financial support from an NSERC Discovery Grant No. RGPPN-2023-044 and their McMaster Startup Funds. AK also acknowledges that resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring wectoriistiitttteilaaaaatt httpm//ttttttt///prrtosss/////tt
the Vector Institute support from an EV travel grant.
HSOB acknowledges financial
References
Beatrice Acciaio, Anastasis Kratsios, and Gudmund Pammer. Designing universal causal deep learning models: The geometric (hyper) transformer. Mathematical Finance, 2023.
Ackley. A Connectionisl Machine for Genelic Hillclömbiing. The Springer International Series Engineering and Computer Science. Springer US, 1987. ISBN 9780898382365, URL https://books. ca/books? 1d=p3hQAAAAMAAJ.
Hassan Akbari, Dan Kondratyuk, Yin Cui, Rachel Hornung, Huisheng Wang, and Hartwig Adam. Alternating gradient descent and mixture--f-experts for integrated multimodal perception. Advances Neural Information Processing Systems, 36, 2024.
Mazen Ali and Anthony Nouy. Approximation theory of tree tensor networks: tensorized univariate functions. Consir. Approz., 58(2):463 544, 2023. ISSN 0176-4276,1432-0944 1432-0940. doi: 10.1007//000365-222--02222 URL attpp://doii org/ 10. 100.1000//0000 10000000//00000000000002220
Francis Bach. Breaking the curse of dinensionality with convex neural networks. Journal of Machine Learning Research, 18(19):1-53, 2017.
Paul Barham, Aakanksha Chowdhery, Jeff Dean, Sanjay Ghemawat, Steven Hand, Daniel Hurt, Michael Isard, Hycontack Lim, Ruoming Pang, Sudip Roy, et al. Pathways: Asynchronous distributed dataflow for 2022.
ml. Proceedings of Machine Learning and Systems,
13

---

Published in Transactions on Machine Learning Research (01/2025)
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3):930-94) 945, 1993.
Peter Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodinension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, (1l:):2225-23111 2019.
Fred Espen Benth, Nils Detering, and Luca Galimberti. Neural networks in fréchet spaces. Annals of Mathematics and Artificial Intelligence, 91(1):75-103, 2023.
Yoav Benyamini and Joram Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathemalical Sociely Colloquium Publications. American Mathemalical Society, Providence, RI, 2000, ISBN 0-8218-0535-4. doi: 00.1090/coll/044 URL https: //tp:://dooioee org/10.g//..... 111111.110//1111//0000
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapuik- Chervonenkis dimension. J. Assoc. Comput. Mach., 36(4):929 965, 1989. ISSN 0004-5411,1557-7335X doi: 241145/76339.775
URL https: org/ 10. 1145/76359.... 163717
Helmut Boleskei, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. Optimal approximation with sparsely connected deep neural networks. SIAM Journal Mulhemalics of Dala Science, 1(1):8 45, 2019.
Lukas Bossard, Matthieu Guillaumin, and Lue Van Gool. Food-101 mining discriminative components with random forests. In Computer Vision-ECCY 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part VT 13, pp. 446-461. Springer, 2014.
Stephen Boyd and Lieven Vandenberghe. Conver optimization. Cambridge University Press, Cam- bridge, 2004. ISBN 0-521-83378-7. doi: 10.1017/CH097705110044 URL https://dbi.orr//00. CB09780511804441.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances neural information processing systems, 33:1877-1901, 2020.
Nataly Brukhim, Daniel Carmon, Trit. Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 943-955. IEEE, 2022.
Tianshi Cao, Mare T Law, and Sanja Fidler. A theoretical analysis of the number of shots in few-shot learning. In International Conference on Learning Representations, 2020. URL https://openteview.ner net// Forum?id-Hlggernry
Jiahua Chen. Optimal rate of convergence for finite mixture models. The Annals of Slatistics, pp. 221 221-233, 1995.
Patrick Cheridito, Armulf Jentzen, and Florian Rossmannek. Efficient approximation of high-dimensional functions with neural networks. IEFE Transactions on Newral Networks and Learning Systems, 2021a.
Patrick Cheridito, Arnulf Jentzen, and Florian Rossmannek. Efficient approximation of high-dimensional functions with neural networks. IEEE Transactions on Newral Networks and Learning Systems, 33(7): 3079-3093, 2021b.
Gabriel Conant. Upper bound ve-dimension of partitioned class. MathOverflow, 2023. URL https: //mathoverflow net/q/461604.
httpo/orrr..oo..et///446666000 URL.https://mathoone http:/mmaatvvrtow.c.cee httpeeeewwwo.ee///////e// 461166 (version: 2024-01-05).
Christa Cuchiero, Philipp Schmocker, and Josef Teichmann. Global universal approximation of functional input maps weighted spaces. arXiv preprint ar xrx::22006.055 0000000000333,, 2023.
George Cybenko. Approximation by superpositions sigmoidal function. Mathematics of control, signals and systems, 2(4):303 314, 1989.
14

---

Published in Transactions on Machine Learning Research (01/2025)
Ingrid Daubechies, Ronald DeVore, Simon Foucart, Boris Hanin, and Guergana Petrova. Nonlinear approxi- mation and (deep) relu networks. Construclive Approzimation, 55(1):127-172, 2022.
Tim De Ryck, Samuel Lanthaler, and Siddhartha Mishra. On the approximation of functions by tanh neural networks. Newral Networks, 143:732-700 -50, 2021.
Ronald DeVore, Boris Hanin, and Guergana Petrova. Neural network approximation. Acta Numerica, 30: 327 444, 2021.
Zhiying Fang, Yidong Ouyang, Ding-Xuan Zhou, and Guang Cheng. Attention enables zero approximation error, 2023. URL https://openreviess http:/pppeereeeee...tterrrrrrra bb4Ydcrr.
Herbert Federer. Colloquium lectures on geometric measure theory. Bull. Amer. Moth. Soc., 1978.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. Journal of Machine Learning Research, 23(10)): 39, 2022.
Luca Galimberti, Anastasis Kratsios, and Giulia Livieri. Designing universal causal deep learning models: The case of infiitt-diimensional dynamical systems from stochastic analysis. arXiv preprint arXiv:2210.188
2022.
Mina Ghadimi Atigh, Martin Keller- Resser, and Pascal Mettes. Hyperbolic busemann learning with ideal prototypes. Advances in Neural Information Processing Systems, 34:103 115, 2021.
Lukas Gonon and Juan-Pablo Ortega. Fading memory echo state networks are universal. Neural Networks, 138:10 13, 2021.
Lukas Gonon, Lyudmila Grigoryeva, and Juan-Pablo Ortega. Approsimation bounds for random neural networks and rescrvoir systems. The Annals of Applied Probability, 33(1):28-60 69, 2023.
Google. Gemini. Google, 2023. URL
Lyudmila Grigoryeva and JubnoPablo Ortega. Universal discrete-time reservoir computers with stochastic imputs and lincar readouts using non-homogencous stato-affine systems. Journal of Machine Learning Research, 19(24):1 40, 2018.
Ingo Gühring and Mones Raslan. Approximation rates for neural networks with encodable weights in smoothness spaces. Neural Networks, 134:107-1300 2021.
Ingo Gühring, Gilla Kutyniok, and Philipp Petersen. Error bounds for approximations with deep relu neural networks in w 8, P norms. Analysis and Applications, 18(05):803- -199,,594444 2020.
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang. Retrieval augmented language model pre-training. In International conference on machine learning, pp.
PMLR, 2020.
Steve Hanneke. The optimal sample complexity of PAC learning. J. Mach. Learn. Res., 17:Paper No. 38, 15, 2016. ISSN 0092-443,,1533-7922
Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension bounds for piecewise linear neural networks. In Conference on learning theory, pp. 1064 1068. PMLR, 2017.
Juha Heinonen. Lectures analysis metric spaces. Universitext. Springer-Verlag, New York, 2001.
Nhat Ho, Chiao-Yo Yu Yang, and Michael 1 Jordan. Convergence rates for gaussian mixtures of experts. Journal of Machine Learning Research, 23(333):1 81, 2022.
Chang hoon Song. Gconho Hwang, Jun ho Lec, and Myungjoo Kang. Minimal width for universal property of deep rnn. Journal of Machine Learaing Research, 24(121):1- 41, 2023.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Newral networks, 2(5):359-366 1989.
15

---

Published in Transactions on Machine Learning Research (01/2025)
Clemens Hutter, Recep Gtil, and Helmut Böleskei. Metric entropy limits recurrent neural network learning of linear dynamical systems. Applied and Compulational Harmonic Analysis, 59:198-22 -23, 2022.
Robert A Jacobs, Michael Jordan, Steven Nowlan, and Geoffrey E Hinton. Adaptive mixtures of local experts. Neural compulation, 3(1):79 87, 1991.
Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, et al. Mixtral of experts. arXiv preprint arXiv:2401.0400 2024.
Yuling Jiao, Yanming Lai, Xiliang Lu, Fengru Wang, Jerry Zhijian Yang. and Yuanyuan Yang. Deep neural networks with Rel---sin-exponentia activations break curse of dimensionality in approximation on Hölder class. SIAM J. Math. Anal, 55(4) 3649, 2023. ISSN 1086-1410,1095-77 doi: 10.1137/21M1444311 URL https://doi. orge 10. 1137/21M144431X
Michael I Jordan and Lei Xu. Convergence results for the em approach to mixtures of experts architectures. Neural networks, 8(9):1409 1431, 1995.
Heinrich Jung. Ueber die kleinste kugel, die eine räumliche figur cinschliesst. Journal für die reine und angewandle Mathemalik, 123:241 257, 1901. URL
Martin Keller-Ressel and Stephanie Nargang. Strain-minimiking hyperbolic network embeddings with landmarks. Journal of Complez Networks, 11(():enad002, 2023.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ar preprinl arXiv:1412.6980 6980, 2014.
Anastasis Kratsios and Léonie Papon. Universal approximation theorems for differentiable geometric deep learning. The Journal of Machine Learning Research, 23(1):8896 18886-68968, 2022.
Anastasis Kratsios and Behnoosh Zamanlooy. Do relu networks have an edge when approximating compactly- supported functions? Transactions Machine Learning Research, 2022.
R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal., 15(4))839 858, 2005. ISSN 0016-443X11400-88 doi: 10.1007/ 100039-005-0577-6 URL attps://don http:///oo..o/////// 00000/00009-0000000000
Alex Krizhevsky and Geoff Hinton. Convolutional deep belief networks on d0far-10. Unpublished manuscript, 40(7):1-9, 2010.
Hugo Larochelle, Yoshua Bengio, Jérôme Louradour, and Pascal Lamblin. Exploring strategies for training deep neural networks. Journal of machine learning research, 10(1), 2009.
Mare T Law, Jake Snell, Amir massoud Farahmand, Raquel Urtasun, and Richard Zemel. Dimensionality reduction for representing the knowledge of probabilistic models. In International Conference on Learning Representations, 2019.
Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen. (GS)hard: Scaling giant models with conditional computation and automatic sharding. In International Conference on Learning Representations, 2021. URL https: ///peerrevwwwnee//ooooteeee www.///ooun.ddggeeeeeeeeeee
llya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. URL https: //tppe/////eeeeiieee... wttp://www....eeeeoooooe/det//ea
Jianfeng Lu, Zuowci Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation for smooth functions.
SIAM J. Malh. Anal., 53(5):5465 5506, 2021a. ISSN 0036-14110,1995-71544 doi: 10.1137 22033499914 URL https://doi, httb::://do.oor/1..... 113.1.01111/2221449555.
16

---

Published in Transactions on Machine Learning Research (01/2025)
Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijum Zhang. Deep network approximation for smooth functions.
STAM J. Math. Anal., 53(5):5465555506 5506, 2021b. ISSN 1886-1410,1095-7133 doi: 10. 2011/3// URL https://doi. org/10. 100.1111//2011469555
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural
networks: A view from the width. Advances in neural information processing systems, 30, 2017.
Harris Abdul Majid and Francesco Tudisco. Mixture of neural operators: Incorporating historical information for longer rollouts. In ICLR 2024 Workshop on Al4DiferentialEqutions In Science, 2024.
Tong Mao and Ding- Xuan Zhou. Rates of approximation by relu shallow neural networks. Journal of Complexity, 79:101784, 2023.
Marina Meila and Michael I Jordan. Learning with mixtures of trees. Journal of Machine Learning Research, 1(Oct):1-48, 2000.
Thomas Mensink, Jakob Verbeek, Florent Perronnin, and Gabriela Csurka. Metric learning for large scale image classification: Generalizing to new classes near-zero cost. In Computer Vision- ECCV 2012: 12th European Conference on Computer Vision, Florence, Itay, October 7-13, 2012, Proceedings, Part II 12, pp. 488 501. Springer, 2012.
Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. When and why are deep networks better than shallow ones? In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
Hrushikesh N Mhaskar. Neural networks for optimal approximation of smooth and analytic functions. Newral computation, 8(1):164-177, 1996.
A. Martina Neuman and Philipp Christian Petersen. Efficient learning using spiking neural networks equipped with affine encoders and decoders, 2024.
Joost AA Opschoor, Ch Schwab, and Jakob Zech. Exponential relu dnn expression of holomorphic maps in high dimension. Constructive Approzimation, 55(1):537-582, 2022.
Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Mare Szafranice, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, et al. Dinov2: Learning robust visual features without supervision. arXiv preprint arXiv:2304.07190 2023.
Philipp Petersen and Felix Voigtlaender. Equivalence of approximation by convolutional neural networks and fully-connected networks. Proceedings of the American Mathematical Society, 14674) 2020.
Guergana Petrova and Przemyst Wojtaszezyk. Lipschitz widths. Constr. Approz., 57(2):759-80) 2023. ISSN 176-44276,1432-094 doi: 101107//000055:22200577555 URL https:///oi. org/10.1007/ 000365-022-000 09576-3.
David Pollard. Empirical processes: theory and applications, volume of NSF-CBMS Regional Conference Series in Probobility and Statistics. Institute of Mathematical Statistics, Hayward, CA; American Statistical Association, Alexandria, VA, 1990. ISBN 0-940600-16-11
Joan Puigcerver, Rodolphe Jenatton, Carlos Riquelme, Pranjal Awasthi, and Srinadh Bhojanapalli. On the
adversarial robustness of mixture of experts. Advances in Newral Information Processing Systems, 35: 9660-9671, 2022.
Alec Radford, Karthik Narasimhan, Tim Salimans, llya Sutskever, et al. Improving language understanding by generative pre-training, 2018.
Leonard Androvvič Rastrigin. Systems of extremal control. Nauka, 1974.
Xuanchi Ren, Jiahui Huang, Xiaohui Zeng, Ken Museth, Sanja Fidler, and Francis Williams. Xcube: Large- scale 3d generative modeling using sparse voxel hicrarchies. In Proceedings of the IEEE/CVF Conference Computer Vision and Pottern Recognition, 2024.
17

---

Published in Transactions on Machine Learning Research (01/2025)
James C. Robinson. Dimensions, embeddings, and attractors, volume 186 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2011. ISBN 978-0-521-89805--8
Shai Shalev-Shwartz and Shai Bev-David. Understanding machine learning: From theory to algorithms.
Cambridge university press, 2014.
Noam Shazeer, Azalia, Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoe Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gate gaate mixture-of-experts layer. orXie preprint XXXu::701.0653 2017.
Zuowei Shen, Haizhao Yang, and Shijun Zhang, Deep network with approximation error being reciprocal of width to power of square root of depth. Neural Compulation, 33(4):1005 1036, 2021.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation: Achioving arbitrary accuracy with fixed number of neurons. The Journal of Machine Learning Research, 23(1):1265) -653-12712, 2022a.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approximation rate of relu nel in terms of width and depth. Journal de Mathêmatiques Pures Appliquées, 157:101-183 2022b.
Jonathan W Siegel and Jinchao Xu. High-order approximation rates for shallow neural networks with cosine and reluk activation functions. Applied and Computational Harmonic Analysis, 58:1-20 26, 2022.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning, Advances in neural information processing systems, 30, 2017.
Yanke Song, Jonathan Lorraine, Weili Nie, Karsten Kreis, and James Lucas. Multi-student diffusion distillation for better one-step generators, 2024. URL https://arxiv org/ ab///400..2..... 2247b.2374..
Shivin Srivastava, Kenji Kawaguchi, and Vaibhav Rajan. Expertnct: clustering, 2022.
symbiosis of classification and
Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. arXiv preprint arXic:1810.0800 2018.
Paulo Tabuada and Bahman Gharesifard. Universal approximation power of deep residual neural networks via nonlinear control theory. In International Conference on Learning Representations, 2021. URL https:// wtwp:/eee/fouunieee/ dideummmmiid-om IXhmY16R33
Henry Teicher. On the mixture of distributions. The Annals of Mathematical Statistics, 31(1):55-73, 1960.
Henry Teicher. Identifiability of finite mixtures. The annals of Mathematical statistics, pp. 1265 1269, 1963.
Nathaniel Trask, Amelia Henriksen, Carianne Martinez, and Eric Cyr. Hierarchical partition of unity networks: fast multilevel training. In Bin Dong, Qianxiao Li, Lei Wang, and Zhi-Qin John Xu (ods.), Proceedings of Mathematical and Scientific Machine Learning, volume 190 of Proceedings of Machine Learning Research, html.
pp. 271-286 PMLR, 15-17 Aug 2022. URL https://proceeednng mmr. mlr wwtppp/eee/s//eeeei/eeeeee
Felix Voigtlaender. The universal approximation theorem for complex-valued neural networks. Applied and Computational Harmonic Analysis, 64:33-40 61, 2023.
Felix Voigtlaender and Philipp Petersen. Approximation in 1p (4) with deep relu neural networks. In 2019 13th International conference on Sampling Theory and Applications (AampTA), pp. 1-4. TEFE, 2019.
Georges Voronoi. Nouvelles applications des paramètres continus à la théorie des formes quadratiques. deuxième mémoire. recherches sur les parallélloèdres primitifs. Journal für die reine und angewandte Mathematik (Crelles Journal), 1908(134):198-25) 287, 1908.
Peiming Wang, Martin L Puterman, lain Cockburn, and Nhu Le. Mixed poisson regression models with covariate dependent rates. Biometrics, pp. 381-400, 1996.
18

---

Published in Transactions on Machine Learning Research (01/2025)
Xin Wang, Fisher Yu, Zi-Yi Dou, Trevor Darrell, and Joseph E. Gonzalez. SkipNet: Learning Dynamic Routing in Convolutional Networks. CVPR, 2017.
Yunfei Yang and Ding-Xuan Zhou. Optimal rates of approximation by shallow reluk neural networks and applications to nonparametric regression. Constructive Approzimation, pp- 1-32, 2024.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Newral Networks, 94:103-114 2017.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 639 649. PMLR, 06 09 Jul 2018. URL ittps://proceedigg mlr. ppess//v55yyrrottkyy html.
Dmitry Yarotsky. Elementary superexpressive activations. In International Conference on Machine Learning, pp. 11932 11940. PMLR, 2021.
Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Approzimation, 55(1):407-474, 2022.
Dmitry Yarotsky and Anton Zhevnerchuk. The phase diagram of approximation rates for deep neural networks. Advances in neural information processing systems, 33:13005 13015, 2020.
Chulhce Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-lo-sequenee functions? arXiv preprint
2019.
Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar.
O (n) connections are expressive enough: Universal approximability of sparse transformers. Advances in Neural Information Processing Systems, 33:13783-13794, 2020.
Behnoosh Zamanlooy and Anastasis Kratsios. Learning sub-patterns in piecewise continuous functions. Neurocomputing, 480:192-211, 2022.
Shijun Zhang, Zuowei Shen, and Haizhao Yang. Deep network approximation: Achieving arbitrary accuracy with fixed number of neurons. Journal of Machine Learning Research, 23(276):1 60, 2022.
19

---

Published in Transactions on Machine Learning Research (01/2025)
A Detailed Tables And Rates
Table 6: Complexity of Feedforward Neural Network fo and the v-ary routing tree in Theorem 5.3. Here log(v)
See Table 8 in Appendix A for more detailed estimates.
Parameter
Estimate
Depth (J)
0(max(1,e=7))
Width (max, dy)
((1)
No. Experts
O [max{(1, 2//0 /
Routing Complexity
((max(1, log(s (s))))
Toble 7: Complexity of the MLP fo in Lemma 5.2.
Activation Ø
Super Expressive 4.3
PReLU 3.1
Depth (J)
15m
19 + 2n +11
(e/10)/
623/2
)m12))
Width (max, d,)
36n(2n + 1) m
16 max (mnxx,n.33 3) +
Table 8: Complexity of Feedforward Neural Network fo and the v-ary tree in Theorem 5.3. Here log(v)
Parameter
Estimate
Depth (J)
(19 2n + 11(=-1]
Width (maxy dz)
16 max m 0 Je logg (1+log(e (1 diam(()))/ (2w-1
No. Experts (No. Leaves)
(/2m)1/2
Height (Routing Complexity)
Cc (og(C)) + log( 2n/n diam (K)) (2w-1
131 (nm) (1mm1/73
tog(C))1+tog 2r/w asam(t)) aw
131 (umm)7/2
111
Nodes
o
(log((C) (1+log( 2w/m dlam(K)))/w
131 (am) 172
B Appendix: Proofs
B.1 Proof of Theorem 4.1
Proof of Lemma 5.1. Since IC is a doubling metric space then, (Acciaio et al., 2023, Lemma 7.1), for cach
0, there exist .,...., EN E K. satisfying
|| xill 8 and N₂ < C [lg((daa((X)))/1]
max min zER -l....
In particular, since the doubling number of IC is C, we have the upper-bound
N₂ S C' Clog(5 diam(K))
(12)
An elementary computation shows that the complete v-ary tree of height has leaves and total pertices/nodess
V. given by
A+1 1
h and V
(13)
h
20

---

Published in Transactions on Machine Learning Research (01/2025)
Taking the formulation of L given in equation 13, to be the least integer upper bound of the right-hand side of equation 12, which is itself an upper-bound for No, and solving for h yields:
= log, (C) log(o diam (iam(
(14)
where the integer ceiling was applied since must be an integer.
Let L be any set v² points in K. containing the set { Let T = EV be any complete binary tree with leaves C; note that, L CVV. By construction, and the computation in equation 13, T has vh leaves and nodes.
For completeness, we include minor modification of the proof of Acciaio el al. (2023, Proposition 3.10), which allows for the approximation of uniformly continuous functions of arbitrarily low regularity. The original formulation of that result only allows for a-Hölder function.
Proof of Lemma 5.2. If f(x) c for some constant <> 0, then the statement holds with the neural network f(z) = c, which can be represented as equation with [d] = (n, m)), where A is the matrix for all j, and the "c" in equation is taken to be this constant Therefore,
henceforth only need to consider the case where f is not constant. Let us observe that, if we pick some x² E K, then for any multi-index [d]] and any neural network fo E NN fo(x) f(x*) NN since NV is invariant to cost-composition by affine functions. Thus, we represent fo(x)= - fxx²) = for (x); for some 0* E RP((4), Consequently:
[1((()) - f(x')) - (x) 11f(2)) fo(2)]] = O.
sup zER
Therefore, without loss of gencrality, we assume that f(x") 0 for some x² K. By Benyamini & Lindenstrauss (2000, Theorem 1.12), there exists w-uniformly continuous map F: R" + R" extending f.
Step 1 - Normalizing f to the Unit Cube: First, we identify a hypercube "nestling" JC. To this end, let
= diam(X)) V 2(n + 1)*
n
(15)
By Jung's Theorem (see Jung (1901)), there exists xo E R" such that the closed Euclidean ball Ball d.) (zro rx) contains K. Therefore, by Hölder's inequality, we have that the n-dimensional hy- percube [Io rx1, zo + rx1] 3contains B(Rr,da) (2o, rx), where i = (1. R". Consequently,
K [m0 rx1, 0o + 1. Let f def Fl Fl lino-rk l.ooteel)) then f E C( - rxl, no + 1x R!)) is an w-uniformly continuous extension of f to [xo rkl, + rxl].
Since IC has at least two distinct points, then Fx > O. Hence, the affine function
T:R" 3 E + (2rk) (x zo + rxl) E Rd
is well-defindd, invertible, not identically O, and maps (mo - rx rx i] to [0, 1Ja. A direct computation
shows that g def. f T is also uniformly continuous, whose modulus of continuity : (0) o0) is given by
der = w(rk () @11)
(16)
for all E [0, oc). Furthermore, since for each = 1, ...... m. define pi: IR. 3 - y E R. Since each pi, is 1-Lipschitz then, for each 1,... m, the map gi del pj, og: [0, 11mh + is also @-uniformly contimuous. By orthogonality, we also note that g(x) Em gi (xx) e;, for each RR" where e1,..., em is the standard orthonormal basis of m,; i.e. the 7th coordinate of ej is if and only if i = j and 0 is otherwise.
Step 2 Constructing the Approximator: For i == I,...,m, m, let Poss E NNN (dzp] for some multi-index
For at y RR we denote by [r. the hypercube defined by II [...v]-
21

---

Published in Transactions on Machine Learning Research (01/2025)
[dco] dd) with n-dimensional inpul layer and I-dimensional outpul layer, i.e. de and dy 1, and let g E P(( be the parameters defining faos. Since the pre-compasition by affine functions and the post-compasition by linear functions of neural networks in NN [dc) are again neural netsorks in MN [d(a], we have that I001) = feco o T- belongs to NN Denote the standard basis of R by {4hm1.
We compute:
m Σ
sup =Ek
f(x)
fai (z)e
==1
m Soco (z)e,
[(x)
Σ i=1
sup seK
f(x) Σ
for (z)ez
sup
26[20 -
1=1
fo T T(x) Σ foc o T o T(x)e,
sup
Σ 9:(u) C uE[0,1]"
Σ Iaw (w)es
sup
S Svm m max max (u; " isism
Iot: (w)l.
(17)
Fix É > 0, to be determined below. For each i i= 1....,.. m, depending on which assumption satisfies, (Shen et al., 2022b, Theorem 1.1) (resp. (Shen et al., 2022a, Theorem 1) if a is as in Definition 9) imply that there is a neural network with activation function o* R + R satisfying
max (g:(u) - 90c (u) < 1)
(18)
Furthermore, the depth and width of these MLPs can bounded above on a case-by-case basis as follows:
If a satisfies Definition 4.3 then, setting each = 0 implies that oo(x)) a (x), as defined in equation 9; thus
jo < 11 and max d, S 36n(2n + +) ISiSRO
In this case, we set E del e/Vm; we have used Shen et al. (2022a, Theorem 1).
(ii) satisfies Definition 3.1 then, setting each 7 = 1 implies that oo(x) ReLU(x)) def max (0, 20 yielding
2rx
n/2
J < 18 2n + 11
and max d, S 16 max 3) (SiJJ))
(e/(131
in this case, we have employed Shen et al. (2022b, Theorem 1.1).
In either case, the estimate in equation 17 yields
max #EN
f(x)
Σ 1=1
Poco (x) CE
22

---

Published in Transactions on Machine Learning Research (01/2025)
Step 3 - Assembling into an MLP: Let 91 92 denote the component-wist composition of univariate function I1 with multivariate function f2-
If the activation function a is either in Definitions 4.3 or 3.1, then it trivially implements the identity lR on R by setting 0; i.c. 01 = Iz.. Consequentially, for any ho E N+, if I& denotes the x k-identity matrix, then Igo 4 E WN with P((d) 2k, and [ 1 = lgt. Therefore, mutatis mutandis, WN satisfies the e-identity requirement with c 2, as defined in Cheridito et al. (2021a, Definition 4). From there, mutatis mutandis, we may apply Cheridito et al. (2021a, Proposition 5). Thus, there is a multi-index [d] = (do....,d.) with do = n and d = m, and a network fo E EVWi implementing 2i facges ei, i.e.
Sucie = So.
such that fo's depth and width are bounded-above, on a case-by-case basis, by
(i) If a satisfies Definition 4.3 then, setting each 0
J 115m m
and max 1515J0)
dj S36n(2n + 1) + m.
In this case, we set & del e/Vm.
(ii) satisfies Definition 3.1 then, setting each 7 yields
2rk
Sm 19 + 2n 11
(e/ vm
and max d $16 max(n, 3) + m. 15/5
Incorporating the definition of rx in equation 15 and employing the inequality diam(K) S 2 rad((K) completes the proof.
Lemma B.1 (Trade-Off: No. Expert vs. Expert Complexity). Let K. be compact subsel of RR whose doubling number is and a uniformly continuous map f K. Rm with modulus of continuity w.
Fix with v 2 2, 0 8 S rad(K), and 0. Suppose that satisfies Definition 3.1. There erists E N4 and a v-ary tree T (V, with leaves L def. {(v,, 0,) C.C. x RP satisfying
max min =Ek (v.O,)EL
|| - 1 < 6.
(19)
Purthermore, for each E IC and each i == 1,..., L, if || Usll < 5 then
[1((x) - (x)) <E.
We have the following estimates:
(i) Depth. Depth of each fo. is 19 2n 11
((+1))/ ((04))/P=-(6///11/// (s/(8l//m)) ) 1//1
1/2 1/2
(it Width. Width of each fo, is 16 max(n, (n. 3} +
(i Leaves: at most L ul log(C) (1+log(8 ' ddiam(K))]]
Formaall, it satisfies what is the 1-identity requirement, thus it satisfies the e-identity requirement all integers e However, the authors Cheridito al. (2021a) do not explicitly consider the extremal case where
23

---

Published in Transactions on Machine Learning Research (01/2025)
(tv) Height: [e log(C) log(6- diam (
(t) Nodes: At most I bo (emm)))))+)
[log()) diamm((())) diam(()))
where def -og(u)-1
Proof of Lemma B.1. Consider the tree T given by Lemma 5.1. For each leaf es of Tf we apply Lemma 5.2 to deduce the existence of an MLP fe, with explicit depth and width estimates given by that lemma, satisfying the uniform estimate
max 56
llf(x) - fe, (z))l <E
(20)
Let T be the same tree as T with leaves identified with {(u; 8:))
We now prove our main technical version, namcly Theorem 5.3, which directly implics the special case recorded in Theorem 4.1.
Proof of Theorem 5.3 (and this Theorem 4.1). Applying Lemma B.1 with given as the solution of
//3/2
n/2
////2
n/2 =
(21)
(n (0////->\//110 (mm))1/2)
(2n (s/131 131 (nm))1/2)
Solving equation 21 for implies that it is given by
2r/
g
8 w-
2
131 131 (m2)
This completes the proof.
Proof of Theorem 4.1. Setting K- (0, 1), r 1/2, w(1) Lt, and thus (1) L-1 (1/a, in Theorem 5.3 yields the conclusion. Finally, by the computation in Example 2, have that C < 2n+1; thus, log(C) (n + () < 2n. Noting that c 1/ (2) = completes the proof.
Remark B.2. The constant hidden under the big O in is 1 log(L, (82mm))
B.2 Proofs of Theorem 4.2
We the following lemma and its proof due to Gabriel Conand.
Lemma B.3 (Conant (2023)). Fiz n, L, N4. Let H be non-empty set of functions from R" to {0, 1) of VC dimension at-most d. Let Cp be the set of all ordered partitions (Voronoi diagrams) (Ci) covering R", where L S L, and for which there erist distinct pr.... PE. E Rn such that: for each l 1,...,
G def. Ō ONUC.
s<l
(22)
C def. (r E ERE || pill = min
||x pall].
s=1....
Let Hr be the set of functions from R to {0, 1} of the form
Σ
Ic
1=1
where i E N with L S L, fi...., E H, and (ci) E Cr. Then, the VC dimension of H, satisfies VC(Hz,) 8T (2, 1.))² (max 2(n 1) 1) log(3T. -3))).
24

---

Published in Transactions on Machine Learning Research (01/2025)
Proof of Lemma B.3. Let first fix our notation. Each zu E R {0} and e R defines halfspace in R" given by HS...t del {- E :": (wo, æ) I t} (see (Boyd Vandenberghe, 2004, Section 2.2.1) for details). We denote set of all halfspaces in I= by HSn det {HS Bro E R" {0) Et RR. Consider the set C(L) of all C S R" of the form
L-1 C= XI
(23)
1=1
for some positive integer 2 < L S max 43 and Xi.... Xi- HSn
Step Reformulation
Set of Sets
By definition of the powerset 2 of the set I", each subset A C R" can be identifies with a function (classifier) from ER to {0, 1} via the bijection mapping any X E 2 to the binary classifier Ix (i.c. the indicator function of the set X). Using this bijection, we henceforth identify both H and Hr. with subsets of the powerset 2R"
Under this identification, the class Hr, can be represented as the collection of subsets of R of the form
L
X x= U H Hin.,
(24)
1=1
where E N satisfics L < L, and for each = 1, 1..... we have Hi E H and (CI),, E Ct is of the form equation 22 for some distincl points pI,...;PP Pł. E R
Step 2 - VC Dimension of Voronoi Diagrams with at-most Cells
An element of (Ci)/11 of Cr. is, by definition, a Voronoi diagram in Rn and thus, Boyd Vandenberghe (2004, Exercise 2.9) implies that each CI...., Cj is the intersection of L L halfspaces; i.e. Ci...., C₁ E C(L) (see equalion 23). Since Ct. = {n Hi ID E N4 Hi...., Hj E HS, < L} then Blumer et al. (1989,
Lemma 3.2.3) implies that
VC(C2) VCCCS, (I. 1og(3L-33 22(n + 1) (L -1) log(3L 33; the second incquality in equation 25 holds since VC(HS,,) + 1 by Shalev-Shwartz & Ben-David (2014, Theorem 9.3).
(25)
Step& 3 - VC Dimension of The Class He
Define H. HCL(L) def nHnC H H and C e C(L)). Again using Blumer et al. (1989, Lemma 3.2.3), we have
VC(HnC(L) <2 (CC(H) VC(C(L)))) 2 log(6)
<4log(6) (C(X((VC))) <4log(6) maxxfd,2(n + 1) (L - log(3L 3)1).
(26)
Consider the set A. det {UE Hi Le i L, 4I 1. L. H. E HnC(L)). Applying Blumer et al. (1989, Lemma 3.2.3), one final time yields
VC (Hl <2 (HNC(L)) L Llg(
(27)
(lo((6) ( (axx (d, 2(n + 1) (L (L-1) 1) - -3))) log(31-33))) SBL log(maxx2, 2))² max (d. 2(n + 1) (L 1) log - 3)}}
log())
(28)
(29)
where equation 28 held by the estimate equation 26. Finally, since VC(A) S VC(B) whenever A B for any set B then since Hg H. then equation 27-equation 29 yields the desired conclusion.
We may now derive Theorem 4.2 by merging Lemma B.3 and one of the main results of Bartlett et al. (2019).
25

---

Published in Transactions on Machine Learning Research (01/2025)
Proof of Theorem 4.2. Let n, J,W.L E N+ and consider the (non-empty) set of real-valued functions
NN J, By definition of the VC dimension of a set of real-valued functions, given circa equation 3, we have
VC (NNTWWM))
J.W.,.)) Jel VC o NN (NWW,,)) 1.Wi,.1)
VC (CPPJW VC e PPPR J.W.L.m.1..
(30)
By Bartlett et al. (2019, Theorem 7), we have that
(o.)) P 1.W.,.)) S D def. [ (J+ W2 log2 (e4(J+1) W (e22(e2(J 1)W)]]
(31)
Therefore, applying Lemma B.3 with 7 (I10,00) NN J.W.n.1) yiclds the estimate
D", VC (H o N.W.W,...... & 8L log(maxx (2, 2 (max D*, 2(n + () 1) log(3L -3))
(32)
Combining equation 32 and the definition equation 30 yiclds the bound. In particular,
VC (NPP)WLL..)) J.W.m.1) E (LLog(()) max(nL JW3 (W)))
yielding the second conclusion.
B.3 Proof of Proposition 4.4
Proof. We argue by contradiction. Suppose that F has finite VC dimension VC(F). Then, Shen al. (2022b, Theorem 2.4) implies that there exists 1-Lipschitz map f : 1] R such that does not exist strictly positive E (0, VC(F)-1/n//) satisfying such that
inf sup 1f(x) [(x) s. fer =E[0.1]-
(33)
However, Shen et al. (2022a, Theorem 1) implies that, for every 1-Lipschitz function, in particular for and for each there exists fe satisfying
sup 1fe(x) - f(x) SE
(34)
=E[0,]]
Setting VC(F)-1/v/1 yields a contradiction as equation 33 and equation 34 cannot both simultaneously true. Therefore, FF has infinite VC dimension.
C The Curse of Irregularity
We now explain why learning Hölder functions of low regularity (()d))))Hööler) functions on the real line segment [0, is equally challenging as lcarning regular functions (1-Lipschitz) on [0, 1]"
C.1 Hölder Functions
Fix n, m E and let C " non-empty and compact of diameter D. Fix < L 2 0, and let
f : X Rm be (a, Hööder continuous, meaning
[I((x) - f(y)l L|Ix - y/" y11
holds for each x, y E X. For any 120 and < 1, we denote set all (a, L)-Hölder functions from X' to R is denoted by ( 11" R: L).
We focus the class of locally Hölder functions since they are generic, i.e. universal, amongst. all continuous functions by the Stone Weierstrass theorem. In this case, Hölder functions are sufficiently rich to paint
26

---

Published in Transactions on Machine Learning Research (01/2025)
full picture of the hardness to approximate arbitrary Hölder functions either by MLPs against the proposed model.
In contrast to smaller generic function classes, such as polynomials, Hölder functions provide more freedom in experimentally visualizing our theoretical results. This degree freedom is the parameter a, which modulates their regularity. a tends 0 the Hölder functions become complicated and when a = the Rademachhr--Seppaane theorem, see Federer (1978, Theorems 3.1.6 and 3.1.9) characterizes Lebesgue almost-cvery differentiable functions as locally (1, L)-Hölder maps. Note that (1, L)-Hölder functions are also called L- L-Lipschitz maps and, in this case, L = supz [ where the supremum is taken over all points where f is differentiable and where llop is the operator norm.
C.2 The Curse of Irregularity
The effect of low Hölder regularity, i.c. when R 0, has the same effect as high-dimensionality on the approximability of arbitrary a-Hölder functions. This is because any real-valued bodee/hyyothesii class F1 of functions on I& approximating an arbitrary (2. H--Höder functions By Shen et al. (2022b, Theorem 2.4), we have the lower minimax bound: for each E > 0 we have "the curse of irregularity"
sup inf sup If(z) - f(x)) SE VC(F)) E (((="))
(35)
fEF 05
where the supremum is taken over all f E (1, 1], R; 1). The familiar curse of dimensionality also expresses the hardness to approximate an arbitrary 1-Lipschitz ((1, H)-Hölr thus relatively regular, function on [o, 1]". As above, consider any model/hye hypothesis class F2 of real-valued maps on Id then, again using Shen et al. (2022b, Theorem 2.4), one has the lower-bound
sup inf sup [If(x) - f(x))] SE VC(5) E ((==A) f (E(0
(36)
where the supremum is taken over all f ([0, R; 1). Comparing equation 35 and equation 36, we
find that the difficulty of uniformly approximating arbitrary low-regularity ((3, 1) Hö-Hölr function 1-dimensional domain is roughly just as complicated approximating relatively regular (1-Lipschitz) function on a high-dimenssoonll domain.
Incorporating these lower bounds with the lower-bound in equation 4, we infer that the minimum number layers (L) and minimal width (W) of cach MLP approximating low-regularity function on the low-dimensional domain [0, 1] is roughly the same the minimal number of layers and width of an MLP approximating high-regularity map the hime-dimeasionnl domain [0, 1]n.
D Experimental details
We include here experimental details, we refer to the source code in the supplementary material for more details. We first outline the algorithm used to train the MoMLP MoE model. We then provide details on the trained architecture and hyperparameter details in the implementation.
D.1 Definitions of the Ackley and Rastrigin functions
Let. us note x = (x1,..., T E Rn the n-dimensional representation of a sample, we use the following formulation the Ackley function:
Ar)ley(z:) = 20 + exp(1) - a exp
Σ
exp
1 Σ cos (osT2,)))))
(37)
where a = 20 and ==03. 0.2. We also use the following formulation of the Rastrigin function:
Rastrigin(z) =
Σ
x
10 n
Σ cos (2
(38)
1=1
27

---

Published in Transactions on Machine Learning Research (01/2025)
D.2 Training Algorithm
We now provide an explanation for the training algorithm. As discussed, we miligate down the algorithm into two parts: discovering the prototypes and training the networks. Conceptually, the prototypes define where in the input space the networks are located, or in other words, where in the input space we expect cach of the networks to have the best performance. During inference, we will route a given input to the appropriate network based on its nearest prototype. In essence, each network learns to approximate a specific region of the overall input domain.
Discovering prototypes. In principle, may not know how to partition the imput space. One approach is to utilize standard clustering algorithms like K-means, but this might be subopt for the downstream task unless we are already operating in a structured latent space, such as those found in pre-trained models (further discussion on this is available in Section 6). Another way is to learn it via gradient descent by optimizing the location of the prototypes for a specific task by following the gradient of the downstream loss. At the beginning of training, we have Fx) = (.. [x())) which contains a collection of K randomly initialized shallow or small networks (i.e., much smaller than our MoMLPs described later). In this first step, we assume that we are able to load all randomly initialized networks into our GPU memory. In particular, this is true because we use small networks with few paramcters, which we will later "decpen" in the next stop def.
by adding additional hidden layers. We initialize the prototypes = (pi...., .K) randomly from a uniform distribution within the bounds of our training dataset input samples. We use the following expression {p
train the location of our prototypes 1K in Ee by minimizing the energy:
Σ (N.J)ED
{(softmax ( || - ())
(39)
where the loss l is task-specific; for example, one could use mean squared error for regression and cross-entropy for classification. The softmax weights the importance of the prediction of cach of the MoMLPs in F for a
given input 5r, a function of the input's distance to the protolypes, ||x - p def, (II= p1 pnll,-... || pk II)- Both the locations of the prototypes and the shallow randomly initialized neural networks assigned to them are optimized.
Deepening the Networks. After the initial training phase, we enhance the networks by incorporating additional layers. Specifically, we introduce linear layers with weights initialized to the identity matrix and bias set to zero, just before the final output layer of each network. To encourage gradient flow in these new layers during the subsequent training stage, we slightly perturb this initialization with small Gaussian noise. This approach is driven by the fact that in the second training stage, each MoMLP can be optimized in a distributed manner. Consequently, we can work with larger networks without the need to load all of them simultaneously into our GPU, allowing for more model parameters. During the first stage, we have already optimized our networks alongside the prototype locations, converging towards a minimum. By initializing the networks with the new layers close to the identity, we can ensure that their output at the start of the second stage of training is similar to that produced by the original networks. This allows us to smoothly continue the optimization process from the point where we previously halted.
MoMLP Training. Once prototype locations have been fixed we can independently train MoMLPs f1....,fr fx by minimizing for all h E (1,...,')) K):
Σ
((f(()))))
(40)
SEargminne (3.....) (le-py1)
over all the networks. We optimize the MoMLP network fa for training data points that are closest to prototype ps- The training procedure is summarized in Algorithm 2.
Inference. At inference time, each test sample æ is assigned to its nearest prototype pk where k e arg min {||z py |}} and the prediction is made by the k-th MoMLP ft.
jE(L....)
Comparison to Standard Distributed Training. One can distribute the complexity of feodforward models by storing each of their layers in offline memory and then loading them sequentially into VRAM
28

---

Published in Transactions on Machine Learning Research (01/2025)
Algorithm 2: MoMLPs Training.
Require:
Training data def.
(1 no. of prototypes K N+, loss function
Discovering Prototypes:
(F.p) arg min
Σ
(softmax (xlp) F()).9)
Fi
(aacc
Deepen networks:
For - K:
fx + deepen(ft)
MoMLP Training:
For k I,...,,K K:
f arg min fn
Σ
((fa(z).v)
(2.0)ED
kEarg miny (1=-py1))
return MoMLP parameters {fa and protolype locations (pe H
during the forward pass. This does avoid loading more than O(Width) active parameters into VRAM at any given time, where Width denotes the width the feedforward model. However, doing so implies that all the model parameters are ultimately loaded during the forward pass. This contrasts with the MoMLP model, which requires (Iogg,(K) Width Depth) ) to be loaded into memory during forward pass; where Width and Depth are respectively the largest width and depth of the MLP at any leaf of the tree defining a given MoMLP, and K denotes the number of prototypes. However, in the forward pass, one loads (c-n//2 parameters for the best worst-case MLP while only On log(1/s)/e) are needed in the case of the MoMLPs. The number of parameters here represents the optimal worst-case rates for both models (see Table 8 and Theorem 5.3).
D.3
Architectures and hyperparameters
Lastly, we detail the model architectures and hyperparameters used in our experiments.
D.3.1 MoMLPs
We set the width of our MoMLPs to 1000. In other words, each hidden layer of our MoMLPs contains linear matrix of size w x w.
In the regression task, our MoMLPs contain hidden layers and we use a learnable PRcLU as activation function. For training, we use the Adam (Kingma & Ba, 2014) optimizer with a learning rate of 1074 and the default Pytorch hyperparameters.
In the classification lask, we follow the setup of Oquab al. (2023) and use AdamW (Loshchilov & Hutter, 2019) the optimizer with learning rate of 10-3 and the default parameters from PyTorch. Our MoMLPs consist of four hidden layers for the classification task, and we apply BatchNormid before the PRcLU activation function.
D.3.2 Baseline
The baseline shares the same architecture the MoMLPs described above. However, if we let K denote the number of prototypes and assume that vK is natural number, the width of the baseline is wvK, ensuring that the total number of hidden parameters matches that of all the MoMLPs combined. In our experiments, we set K 4, so VK= 2
D.4 Additional classification experiment
Instead of using the DINOv2 features input to our model, we also conducted an experiment where the 32 x 32 CIFAR RGB images were vectorized into 3072-dimensional vectors, which were then used as input to
29

---

Published in Transactions on Machine Learning Research (01/2025)
our model (recall that 32 x 32 x 3 3072). The elements of these vectors were normalized to lie within the interval [0,1].
The accuracy scores, reported in Table 9, demonstrate that the performance of our approach is comparable to that of the baseline while requiring less VRAM per expert. It is important to note, however, that since we are using standard MLPss, the reported scores are lower than those achievable with neural networks specifically designed for computer vision tasks.
Table Test classification accuracy using the vectorized RGB images as input (average and standard deviation).
Dataset
CIFAR-10
CIFAR-100
Ours (weighted)
46.79 0.91
20.82
0.29
(unweighted)
Baseline
47.36 1.58
19.01
3.42
30


Reviews:
[{"review_id": "rya7HcJWqH", "reviewer": "Reviewer_pxj4", "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\nThe biggest strength of this paper is the clarity of narrative, as well as great teaching outcomes. I learned a lot. The authors rigorously looked at several aspects of the MoMLPs, and provided great theoretical contributions. While they have rather small scope, they are still of interest to TMLR audience.\n\n## Weaknesses\n1. The biggest concern about this paper is the lack of practical utility. At least an empirical study verifying the claims of approximation result would be great. I would encourage authors to work w/o DINO embeddings, and show that the results actually hold w/o pre-training. On CIFAR, DINO embeddings are very strong due to ImageNet pretraining. \n\n2. Another weakness of the paper is that the authors claim mixture of experts bringing benefit because one does not need to load the whole set of experts into memory. At the same time, their results (as well as the empirical results from other works in the field) show that one does not need to have many experts. This is a logical flaw, and it has to be fixed. \n\n3. Statistical analysis of the results is  missing", "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 looks at VC dimension  and approximation rates of Mixture of Experts MLPs with (P)ReLU activations through the prism of data prototypes. One of the most interesting results presented in the paper, in my opinion, is that the approximation quality degrades with the large number of small experts. A small number of heavy experts seems to be theoretically justified.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I suggest that the authors move experimental results into the main paper, and show qualitatively how their theoretical results related to approximation quality and the number of experts hold in practice. This experiment should not use any DINO embeddings. For such small data as CIFAR, a convent + regular neural net should (training from scratch).\n\n2. Another important request that I have, is to address the logical flaw between the claims and the results. \n\n3. Add statistical analysis when assessing results (e.g. models in Table 8 have no statistical difference)", "broader_impact_concerns": "This work has no ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9uuRQkv8Mt", "reviewer": "Reviewer_imma", "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 this is one of the few papers studying the theoretical foundations of MoE models. As this model is becoming more common with larger deep learning systems this theory can be used to influence the design and implementation of MoE models.\n- The paper is clear and well written.\n\n### Weaknesses\n- The only weakness of the paper is the simplicity of the setting considered. Although this is somewhat okay since this is taking the first theoretical step to understand mixtures of MLPs.", "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 provides an approximation and learning theoretic analysis of mixtures of experts MLPs with trainable \\(P\\)ReLU activations. They prove that any Lipschitz function on [0,1] can be approximated uniformly, arbitrarily well with MoML]\nP requiring only $O(\\epsilon^{-1})$ parameters. The also provide generalization bounds based on the VC dimension of the MoMLP models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Can you clarify what $\\mathcal{K}$ is in the statement of Theorem 4.1.\n- In the statement of Theorem 4.1 is the activation function learnable and does the $\\alpha$ in the activation function correspond to the $\\alpha$ of the $\\alpha$-Holder function being approximated?\n- I would suggest moving some of th empirical results from Apendix D to demonstrate how the theory connects to practice. Even in this toy experiments.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "W0gYkTISUO", "reviewer": "Reviewer_y48i", "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\nThe authors provide a valuable analysis of the tradeoff between No. experts and the complexity of each expert. Such analysis is very important not only for theoretically understanding MoE models, but for practically designing large-scale MoE models.\n\n---\n\n**Weakness:**\n\n1 The analysis does not consider how the Lipschitz parameter affects the tradeoff between No. expert and expert complexity\n\nIt is odd that Theorem 4.1 did not consider the Lipschitz parameter as a factor in affecting the tradeoff between No. expert and expert complexity. The target objective function should play a role in the analysis. However, I believe it is missing in the current version.\n\n2 The introduction of $r$ lacks sufficient explanation\n\nI am confused about the role of $r$ in the analysis. The authors need to provide a clear explanation regarding the \"number of experts-to-expert complexity trade-off parameter.\" It is hard to interpret and understand what this parameter is describing. \n\n2.1 What is $r = 0$?\n\nAccording to the conclusion, such as in Table 1, if $r=0$, the number of parameters per expert will be 1. However, it is unclear what case corresponds to $r=1$, such as what the objective function will be when $r=0$. Can the authors provide more explanations on this?", "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 provides a theoretical analysis of a mixture of MLP models in approximating any Lipschitz function. In particular, the authors theoretically analyze the trade between No. experts needed and the complexity of each expert. Such analysis is critical for understanding the practicality of large-scale MoE models. As described in the paper, it can be beneficial to maintain a low complexity for each model during inference. Therefore, it is crucial to demystify the overall MoE scale with each model's size and objective functions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1 Include the Lipschitz parameter in the analysis, or clearly explain why it can be ignored.\n\n2 More explanations on $r$, and how it connects to the actual objective function or the MoE models to be analyzed", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The consensus is quite positive on this paper. All reviewers note the redactional quality as well as the interesting results on a rather new field of study. There is some slight concern concerning the quality of the experiments or the actual practicality of the results. But given the theoretical orientation of the paper, this is not a major issue. However one reviewer still has issues with some seemingly important definition (r); maybe the authors can have a last thought on this before final publication.
Therefore, given the overall positive comments by the reviewers on this paper that looks at a young subject, I recommend publication.
Decision: Accept (poster)