On the Expressive Power of Mixture-of-Experts for Structured Complex Tasks
Authors: Mingze Wang
Weinan E
Venue: NeurIPS 2025 spotlight ()
Keywords: mixture-of-experts
expressive power
approximation rate
compositional sparsity
low-dimensional manifold
Primary area: theory

Abstract: Mixture-of-experts networks (MoEs) have demonstrated remarkable efficiency in modern deep learning. Despite their empirical success, the theoretical foundations underlying their ability to model complex tasks remain poorly understood.
In this work, we conduct a systematic study of the expressive power of MoEs in modeling complex tasks with two common structural priors: low-dimensionality and sparsity.
For shallow MoEs, we prove that they can efficiently approximate functions supported on low-dimensional manifolds, overcoming the curse of dimensionality.
For deep MoEs, we show that $\mathcal{O}(L)$-layer MoEs with $E$ experts per layer can approximate piecewise functions comprising $E^L$ pieces with compositional sparsity, i.e., they can exhibit an exponential number of structured tasks.
Our analysis reveals the roles of critical architectural components and hyperparameters in MoEs, including the gating mechanism, expert networks, the number of experts, and the number of layers, and offers natural suggestions for MoE variants.

On the Expressive Power of Mixture-of-Experts for Structured Complex Tasks
Mingze Wang
School of Mathematical Sciences, Peking University, Beijing, China mingzewangōstu, pwu.ppu.eeee edu.cn
Weinan E
Center for Machine Learning Research and School of Mathematical Sciences, Peking University, Beijing, China Al for Science Institute, Beijing, China weinan@math, pku. edu. en
Abstract
Mixture-of-experts networks (MoEs) have demonstrated remarkable efficiency in modern deep learning. Despite their empirical success, the theoretical foundations underlying their ability to model complex tasks remain poorly understood. In this work, we conduct a systematic study of the expressive power of MoEs in modeling complex tasks with two common structural priors: low- www-dimensionaltyy and sparsity. For shallow MoEs, we prove that they can efficiently approximate functions sup- ported on low-dimenn low-dimensional manifolds, overcoming the curse of dimensionality. For deep MoEs, we show that (T.)-laye MoEs with experts per layer can approxi- mate piecewise functions comprising EL pieces with compositional sparsity, i.e., they can exhibit an exponential number structured tasks. Our analysis reveals the roles of critical architectural components and hyperparameters in MoEs, including the gating mechanism, expert networks, the number experts, and the number layers, and offers natural suggestions for MoE variants.
Introduction
Mixture-of-experts (MoE) models (Jacobs et al., 1991; Jordan and Jacobs, 1994) have recently achieved significant success in deep learning, particularly as core architectural component of modern large language models (LLMs) (Abdin et al., 2024; Yang et al., 2024b; Liu et al., 2024; Cai et al., 2025). These models have demonstrated strong capabilities across a wide range of complex and diverse tasks, including mathematical reasoning, logical inference, language understanding, and code generation. Despite their empirical success, the theoretical foundations underlying MoEs remain poorly understood, especially in their capacity to efficiently model complex tasks.
In both machine learning and applied mathematics, it is widely recognized that although real-world tasks may appear complex, they often exhibit latent structures. Two prominent structural priors are: (1) low-dimensional structure: high-dimensional data typically lies on a manifold of much lower intrinsic dimension; (2) sparse structure: meaningful signals tend to admit sparse representations in suitable bases or dictionaries. These structural priors have motivated numerous influential algorithms, including dimensionality reduction (Tenenbaum et al., 2000), sparse regression via Lasso (Tibshirani, 1996), compressed sensing (Donoho, 2006), and neural network pruning and compression techniques.
In this work, we investigate the expressive power of MoE networks for modeling complex tasks that exhibit either low-dimensional or sparse structure. Our contributions are summarized follows:
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Shallow MoE networks. We prove that shallow MoE networks can efficiently approximate functions supported on low-dimensional manifold. Theoretically, this task reduces to collection of simpler approximation subproblems localized on low-dimensional subregions, along with an assignment problem that maps each input to the appropriate region. We show that shallow MoE networks naturally implement this procedure, thereby avoiding the curse of dimensionality. Our analysis reveal the complementary roles of the two core components in MoE: expert networks approximate localized subfunctions, while the gating mechanism ensures correct input-to-expert assignment. Additionally, the analysis offers practical suggestions on MoE variants, such as the nonlinear gating, altermating MoE architectures with equivalent expressivity, and low-dimensional expert networks with auto-encoding.
Deep MoE networks. We formalize complex tasks as piecewise functions, and focus on a broad class of structured tasks exhibiting compositional sparsity: where each subtask depends on only small subset of input coordinates, and the overall task is hierarchial composition of these subtasks. We demonstrates that a depth- can efficiently approximate piecewise functions with E- distinct pieces, i.e, it can exhibit an exponential number of structured tasks. Moreover, our analysis elucidates the distinct roles of network depth T. (which enables hierarchical composition) and expert count E. (which enables subtask specialization).
O (L) MoE network with E expert per layers
Unified insights. Our theoretical results reveal that MoE networks can effectively discover the underlying structure priors in the complex tasks (such as low-dimensionality or sparsity), and subsequently decompose them into simpler subproblems, each solved by specialized experts.
2
Related Works
Theoretical understanding of MoE. Chen et al. (2022) analyzed the training dynamics of shallow MoE networks with softmax gating on clustered datasets, emphasizing the importance of expert nonlinearity and data structure. (Baykal et al., 2022) showed that sparsely activated networks can achieve approximation performance comparable to dense networks, and offered a computationally efficient alternative. Dikkala et al. (2023) examined the impact of learnable routing mechanisms in MoEs, establishing their benefits. Li et al. (2024) investigated MoE in continual learning, using overparameterized linear regression to show their adaptability across tasks. A comprehensive survey of recent theoretical advances is presented in Mu and Lin (2025). In contrast to these prior works, we focus the expressive power of both shallow and deep MoE networks for broad classes of structured functions.
Low-dimensional structure. The manifold hypothesis posits that high-dimensional data in real world (e.g., images, speech, and text) typically lies on a manifold of much lower intrinsic dimensionality than the ambient space. This perspective motivates various algorithmic approaches: (i) Dimensionality reduction techniques (Tenenbaum et al., 2000; Roweis and Saul, 2000; Belkin and Niyogi, 2003), which aim to uncover and utilize such low-dimensional structures. (ii) Representation learning methods like Autoencoders and Variational Autoencoders (Hinton and Salakhutdinov, 2006; Kingma et al., 2013), which seek compact and informative representations aligned with low-dimensional manifold.
Sparse structure. It is widely believed that meaningful signals often admit sparse representations in appropriate bases or dictionaries. This principle underpins many influential algorithms, such as Lasso (Tibshirani, 1996), Compressed Sensing (Donoho, 2006; Candès and Wakin, 2008), and Sparse Coding (Olshausen and Field, 1996; Elad and Aharon, 2006), which have been widely applied across domains.
From a theoretical standpoint, the prevalence of sparsity and cow-dimensionality has inspired recent studies on the expressive power of deep networks under structural assumptions. For example, Mhaskar and Poggio (2016); Poggio (2023) analyzed dense neural networks approximating functions with compositional sparsity, demonstrating how sparsity mitigates the curse of dimensionality (Bellman, 1966; Bach, 2017). Wang et al. (2024) studied the expressivity of Transformer models (Vaswani et al., 2017) for modeling long but sparse memories, showing the model's capacity to overcome the curse of memory. Shaham et al. (2018); Chen et al. (2019) examined the approximation power of dense networks for functions supported on dow-dimensional manifolds. In contrast to these works, we

---

investigates the expressive power of MoE networks in approximating complex functions exhibiting either sparse or cow-dimesiional structure.
Preliminaries
Basic notations. Let / 12 - RR be continuous func- tion defined on compact set S2. Its Loo norm defined as ll supwen [x)). We use standard asymptotic notations (()))((-)) (-)) :) to hide the constants indepen- dent of the primary problem size (lypically denoted by m),
Gatlng
and the notations (-), _2))) (-) further hide logarithmic factors. For positive integer let [n)] {I. }. For a, E R, define a/b = min(a, a, b] and a aVb max b).
Figure 1: Illustration of MoE layer.
3.1
MoE networks
MoE components.
An MoE layer consists of two primary components:
Expert networks: collection of E expert networks, each implemented as dense feedforward
ReLU neural network: f()), .... f(F) Rd Fdo..
Gating network: A gating function g Rd - R.. In most existing MoE models (Fedus
et al., 2022; Du et al., 2022; Yang et al., 2024a), g is linear due to its simplicity and empirical efffcctiveness: g(x) WRæ, where WR IR Exde.
MoE operation. Given an input E R an MoE layer performs the following operations, as illustrated in Figure 1:
Expert selection. The gating network computes routing scores g(x) R.E, and selects the top-K experts with the highest scores:
K arg (gp)()
where arg TzpK(z) returns the indices of the K largest entries of z.
Expert computation and aggregation. Each selected expert i E computes its output ((k (æ). The final output a weighted combination:
Σ (x(x) (x) KEK
y
where the weight are defined via ax (x)
exp(as (x))
Ejek (x)]
Notably, only K expert networks activated per input. Without loss of generality, we focus
throughout this paper on the case K 1, as the extension arbitrary K < E is straightforward.
Hypothesis class L.L.E. We define H, as the class of depth-L. neural networks composed of stacked L MoE layers:
h(4) (L-1)) o (2))
(1)
where each (9) is MoE layer consisting of a linear gating network (()) and E expert networks ((f,e) (e E [F), each being an l-layer, mn-width dense ReLU neural network.
3.2 Classical approximation results
Approximation error notation. Let CPFN (f) denote the _ approximation error of target function f: + R using l-layer, m-width dense ReLU neural networks.
çK space. Let D, K N, and C R be compact. The space CK (Ω) consists of all functions f such that
[[ = max
|10fflaa()) <
(2)
os
3

---

where f denotes the partial derivatives of order B (31.-... .BD) E ZP. The space of smooth functions is defined as 2 (12) NKEN CK (St). Additionally, the smoothness exponent of F + defined as
k (ff) sup(K :: e (*))
The following result summarizes the classical approximation rate of two-layer ReLU networks for CK functions (Mao and Zhou, 2023; Yang and Zhou, 2024):
Theorem 3.1. Let D, K N, and Ω C RD be compact. For any f E C* (9t and m E N, there exits two-layer ReLU neural network fm with m hidden neurons such that
(0 (0(m=#)) $), (
if < 2
EPEN (f) |f fmlle (0) &
otherwise.
When the smoothness of the target function is relatively low, i.e., K < D, the approximation rate ( $) reveals that two-layer networks suffer from the curse of dimensionality (CoD).
Theory for Shallow MoE Networks
this section, we study the efficiency of shallow MoE networks approximating functions supported on a low-dimensional manifold M.
4.1 Manifold in Euclidean Space
Let M be a d-dimensional smooth manifold embedded in R. We begin by reviewing several standard definitions. Definition 4.1 (Chart and Atlas).
M
R
Up
A chart for M is pair (U, Φ) such that U C M is open and Φ U - Rdd where is a homeomorphism (i.e., bijective, & and ø-1 are both continuous). U is called coordinate neighborhood, and á is the associated coordi- nate map.
62
12"
R
O2(U1z)
Figure 2: A d-dimensional manifold M in IR.
An atlas of M is collection Oa)leA of charts such that U.a.UUa = M.
An atlas {(U., oa) boEA is called smooth for any overlapping charts (Uas Pa) and (Ua', Par), the transition maps da o/ and &ar o are smooth functions.
Definition 4.2 (Smooth manifold). The manifold M called smooth if it has a smooth altas.
We now introduce the partition of unity, which divide the manifold into regular subregions.
Definition 4.3 (Partition of unity). Let (Ua) be open cover of .. A partition of unity of M w.r. this cover a family of nonnegative smooth functions Pa -M- - [o, 1] for a E A such that:
(i) for all a E A. Pa has compact support and supp(pa) Ua:
(ii) for every x E M, only finitely many Pa (ar) are nonzero;
(iii) for æ E M. E.EA (a)
Theorem 4.4 (Existence of a partition of unity). Ler JaEA be an open cover of a smooth manifold M. Then there exists partition of unity {Pa]aEA of M w.r.t. {Ua]
We next define the smoothness of function defined on manifold.
Definition 4.5 (Function on the manifold). Let function f M - IR, and {(U,, dh Joe be a smooth atlas of M. Its smoothness s(f) defined by x()) infae x(S oz smoothness of each o o-1 is defined as Equation (3).
-1 )), where the

---

In this paper, we focus smooth compact manifolds. Due to the compactness of M. its atlas consists of finite collection of charts, denoted by {(U,, (e)) Additionally, we can let (U,) c
[0, 1].. By Theorem 4.4, there exists a corresponding partition of unity (ei)E(F)
Compact smooth manifolds admit an atlas with strong geometric regularity as below, which is detailed in Appendix A.
Example 4.6 (Highly regular atlas). Let M a compact smooth manifold. Then there exists highly smooth atlas {(U,, &)) dejE such that each map Φ; U; + [0, 1] is linear function. Thus, each o; satisfies n((de) (when viewed as function in IR PR:
Motivated by this example, we define broad class of regular atlas: Definition 4.7 (Regular atlas). atlas {(U, (e))) of compact manifold M is called regular, if each map o, has the smoothness k((r) D+3
4.2 Theoretical results and insights
Theorem 4.8 (Main result). Let M be a compact, d-dimensional smooth manifold in RR, with regular atlas {(U,, di)e (Definition 4.7). Let the target function f M - R. Then for any m 3 (EE)), there exists a depth-2 MoE network E Hy with E experts per layer, each being is 3-layer m-width dense networks, such that:
|| - 1 (1) & max CFFN
(flu))
3,m (E(E)
max (E[B]
OFFN 2.m
+ mAX E
2,m
CFFN (b:)
|lf o, "1'1lo
approximate a low dimensional function
apprxiimate high-order order smooth map
6mm m
<td U.)
< max [E
Theorem 4.8 demonstrates that 2 MoE networks can efficiently approximate functions supported on diw-dimensional manifolds. The total approximation error decomposes into two components: (i) approximation of low-dimensional target functions flu: Φ "s; 's; (ii) approximation of smooth coordinate maps o, 's. Both subproblems are significantly simpler than approximating the original high-dimensional function directly, enabling MoE networks overcome the curse of dimensionality.
Table 1: Comparison of approximation rates between shallow MoE and shallow dense networks. For MoF, m is the width of each expert networks; for dense networks, m the width of the hidden layer.
Shallow MoE networks (Theorem 4.8) Shallow dense networks (Theorem 3.1)
max ①
<(lle,) A1
Ô (mm=
20 A1
SE [S]
Improved efficiency over dense networks. Table highlights the superior approximation efficiency of MoEs. In the regime where the target f has limited smoothness, i.e., x(f) < D, dense networks suffer from the curse of dimensionality, as the approximation rate k(f)) deteriorates with ambient dimension D. In contrast, MoE networks achieve rates governed by the intrinsic dimension d < D and local smoothness <(flu;)= > x(J), thereby substantially improving approximation efficiency and achieving faster approximation rate: ((fle,ed") A D
Key insight. The proof of Theorem 4.8 (deferred to Appendix A) reveals several insights into the mechanisms of MoE networks:
MoE. networks achieve efficient approximation by decomposing a complex approximation problem into multiple localized approximation subproblems, well simple assignment task.
Recall that depth-2 MoE (Eq. (1)) comprises expert networks and a gating mechanism. Their distinct roles are as follows:
5

---

Expert networks (f(2.)) in Layer 2): these components efficiently approximate the d- dimensional local target function flu, o o. and the smooth chart map di. They directly influence the overall approximation error and benefit from increased width m.
Routing mechanism (Layer 1 and gating in Layer 2): these components work together to exactly assign each input to its correct expert f(2.0, The first MoE layer h(4) behaves like dense model, approximating the smooth partition functions p Then the Layer-2 gating network g(o) selects the expert corresponding to the region U, such that E Ug. This exact assignment is nontrivival, please refer to the proof for details.
Corollary 4.9 (Special case, highly regular atlas). Let M be compact, d-dimensional smooth manifold in IRP, with a highly regular atlas {(U;, (i) (Example 4.6). Let the target function
f: M + R. Then for any m E (I(E)), there exists a depth-2 MoE network V E HH2 with É experts per layer, each a 2-layer m-width dense network, such that:
- -VVlL. < max EE
2.1
o oflu,007
mmax [E
Ó(m m
nt).
appreximate low diveediensiaall fanction
Compared to Theorem 4.8, Corollary 4.9 applies to more structured setting in which the local coordinate maps O; are linear and thus thus do not require approximation. This eliminates the second term in the error bound, and reduces each expert to 2-layer dense network.
Comparison with prior works Shaham et al. (2018); 8); Chen et al. (2019). These works show that dense networks can also efficiently approximate functions low-dimensional manifolds. However, their analyses require additional regularity assumptions on manifolds, which enables explicit constructions of coordinate charts and partition functions. In contrast, our Theorem 4.8 does not require such explicit formulations, applying to a broader class of smooth regular manifolds. More importantly, MoEs offer fundamental computational advantage: while dense networks activate all parameters for every input, MoEs selectively activate only a single expert per input. To achieve comparable approximation accuracy, the number of activated parameters in dense networks is roughly E times greater than that in MoEs, as dense networks must simultaneously approximate all E subproblems.
4.3 Practical Suggestions
Beyond theoretical guarantees, our analysis also offers several practical suggestions into the design
of MoE architectures.
Incorporating nonlinearity into gating is critical. Our theoretical results indicate that accurate input-to-expert assignment requires approximating the partition functions pt. which are generally nonlinear. Since standard gating function is linear and lacks the capacity to model nonlinear Pi. an additional MoE (or dense) layer needed prior to gating to approximate Pt. If the router incorporates sufficient nonlincarity, e.g., two-layer ReLU routing network, it can directly model complex partitions, reducing the depth and number of parameters. For instance, in Thcorem 4.8, the required depth will reduce from 2 to 1, because the nonlincarity in router eliminates the need for preceding MoE layer. Similarly, in Theorem 5.2, the required depth will reduce from 2L to L. Therefore, a more direct and potentially more efficient alternative is incorporate nonlinearity directly into the gating network, eliminating the need for a preceding MoE layer. This observation is consistent with recent empirical findings (Zuo et al., 2021; Liu et al., 2022; Nguyen al., 2024; Akbarian et al., 2024; Le et al., 2024), which demonstrate that nonlinear gating functions improve MoE performance.
Alternating MoE architectures with equivalent expressive power. In our construction, the first MoE layer actually serves as a standard dense layer with width ((E2) to approximate the partition functions Pt. This insight motivates alternative architectures with comparable expressive power: (i) MoE-dense alternating networks. natural variant consists of alternating dense and MoE layers, e.g.. moee h dense, This design extends naturally to deeper architectures. This design has been adopted in practice by GShard (Lepikhin et al., 2020) and GLAM (Du et al., 2022). (ii) Shared + routed experts per MoE layer. Another common MoE variant incorporates experts. This structure is empirically adopted in modern MoE architectures such as Qwen2 (Yang al., 2024b) and DeepSeek (Liu et al., 2024).
shared expert alongside E routed
Low--dimensional expert networks via autoencoding. Our analysis also suggests a more structured and interpretable design for expert networks in MoE. Typically, each expert is implemented as dense

---

network with input dimension D and width (D), resulting in O(D²) parameters. However, our theory motivates replacing each expert f(21.) with a composition flow o Enc. where: Enc RD _ R an encoder approximating the smooth coordinate chart U. [0. 1] flow : IR low-dimensional dense network approximating = This design reduces the number of trainable parameters in each expert to # (Enn)) + (dd)) which is significantly smaller than ((D²) when < D. Moreover, this decomposition aligns with the manifold structure of the target function, improving interpretability. To support encoder learning, one can incorporate standard reconstruction loss Eg |Dec (eccE()c))) x11 using a decoder Dec. We leave empirical validation of this theoretically motivated architecture for future work.
is
5 Theory for Multi-layer MoE Networks
Piecewise ffunctions as multiple tasks. Modern LLMs are capable performing a wide range of tasks, such mathematics, logical reasoning, language understanding, and code generation. From a mathematical perspective, each task can be viewed as a function defined on a task-specific input domain. In practice, these tasks often differ, which are supported distinct regions ".,, S2,, with distinct corresponding tasks fi Ω4 - R. Therefore, performing N tasks can be naturally modeled as approximating piecewise function: f(x) f((),, if Ωt i [N]. While each f; may be high-order smooth within its region Ω4 the global function f may exhibit only low-order smoothness the interfaces between adjacent regions.
Key question. Theorem 4.8 shows that depth-2 MoE network with E experts per layer can efficiently approximate piecewise function comprising E' pieces (flu,, E [E") (each handled by a different expert). natural question then arises for deep MoE networks:
How many distinct pieces be efficiently modeled by a deep MoE network?
A naive limitation. As illustrated above, it is intuitive to associate each expert with a distinct task. depth-L MoE with experts per layer contains (LE)) experts in total, implying capacity to model at most (LL)) distinct regions if each expert is used independently.
Overview of our result: beyond the naive limitation. Surprisingly, this limitation can be overcome when the target function exhibits compositional sparsity. We will show that:
D(pth-O(L) MoE networks with E experts per layer can efficiently approximate a piecewise function comprising EL pieces, provided the function satisfies compositional sparsity structure.
This demonstrates that MoE networks can model an exponential number of structured tasks (far surpassing the native limitation O(LE)) by exploiting structured sparsity in the function.
5.1 Piecewise function with compositional sparsity
Warm-up: Piecewise function on EL unit cubes with compositional sparsity. Let the domain be M [0, EJS, naturally partitioned into EL unit cubes. Con- sider the following target function:
f(x) = (f1, (21), (2,,, ... fL. (ZL)), where i {j [E] E [-- 1,1. VI [4]. (4)
3
Here, each subfunction (subtask) fi.; is defined on the interval U1 = i] and f is defined piecewise over EL regions: U., ... Uig, where [F),1 [Z]). The function f in Eq. (4) exhibits both:
Figure 3: Illustration Eq. (4): a piece-
wise function f with compositional sparsity on 32 = unit cubes. The function f(z) f1,s, (2.1))
is composed from sub-
functions: f1,((2) i(i - 2)(2 - and f2,((z) = iii
Sparsity: each subfucntion fi, depends only the coordinate Fı, not on the full input æ.
== 1)a on
a E i 1, i] for E [3]. Although is smooth within each region, it is only 0-order
Compositionality: the function f is a hierarchical composition of L selective subfunctions.
continuous on [0, 3] x 3)
7

---

Consider Notably, although there are only LE subfunctions, their composition yields E distinct functions across the domain.
Product manifold. We now extend the above formulation to general manifolds. Consider product manifold M MM x M2 x ... Mr, where each Mr compact dy-dimensional manifold in IR,, and Ei= di < D. Each imput æ M can be written as a = (x).'.. ; ,1.) with at Mi-
By compactness, each submanifold M, admits finite smooth atlas {(U),,, oi (E(E)) and an associated partition of unity he(R) (by Theorem 4.4). Without loss of generality, we can let E1 =... EL, denoted by E.
General form: piecewise function on product manifold with compositional sparsity. the target function class admit the form
f(x) Sonn
Coun(i,s (1,s, in (22) ... Stai (xt.)), where {j E [E] x Utz), AI [4].
(5)
Here, each subfunction (subtask) fi. is defined on the local subregion U1 C. MM, and fout composes their outputs. This extends Eq. (4) from Euclidean coordinates øι E [0, E] to manifold-base coordinates æ E M₁. Since fout typically be approximated by dense neural network, assume fout = id (the identity map) for simplicity.
We now illustrate this formulation with concrete example.
Table 2: Semantic interpretation subregions Example 5.1
Mi Math domain
M2: Language domain
U1,1: Geometry
U2.1 English
U1 Algebra
22.2: French
U1.3 Analysis
U2.3: German
Example 5.1. Let M= M1 M2, where each Mj is partitioned into three subregions: M1 U1,1 U U12 U U1,3, M2 U2 U U2.2 U U2.3, with the interpretations given in Table 2. Each subfunction fI, solves the specific type of math problem (e.g.. geometry), while each f2,, handles text comprehension in a specific language (e.g.. English). The full function defined via Eq. (5) encodes 3 compositional tasks of the form:
"Understand and solve the [language type] [math type] problem it".
For example, if Φ U1,1 and 22 E U2 then f corresponds to the task "understand and solve the English geometry problem".
5.2 Theoretical results and insights
We now present our main theoretical result regarding the expressive power of deep MoE networks for approximating piecewise functions with compositional sparsity.
Theorem 5.2 (Main result). Let the targel function f be of the form (5), which comprises F.L pieces. For each E [T.). assume that the atlas {UUss ((s))ee(E) of M; is regular (Definitoon 4.7). Then there exists depth-2L 2L MoE network V E H2LLB with m 2 2 Q(E2), such that:
/ 1/ VI & max max oFFN (Jis) (E[L] (E[E)
33m
cFFN
2,m. (fu. oT.)
CFNN (OL.)) 2,m
max max [E[L] SE[E]
max max [ELL] [E(E:]
((((0_114))
approximate a low dimensiinni fanction
approximate smooth map
< max max θ x(f [E] EE
'To ensure is well-defined overlapping charts, assume ft,(wi) fio(wa)) Van E U, Unn #

---

Theorem 5.2 establishes that depth-2L MoE network with E experts per layer can efficiently approximate piecewise function with E" pieces, provided the function exhibits compositional sparsity. The approximation error consists of two components: (i) approximation of local low- dimensional subfunctions fI, 001 - (ii) approximation of smooth coordinate maps Φr, The resulting
approximation rate is maxie[4] m Ô Ó(m
<Uh.,, 13) which avoids the curse of dimenisonality.
In the special case L = 1, this result recovers Theorem 5.2.
Key insight. The proof (deferred to Appendix B) reveals the following intuitions:
Each pair of MoE layers implements subtasks, and depth-2T. architecture enables hierarchical composition of F. tasks.
For each E [Z., the (21 - s-st and 21-th layers approximate the F subfunctions ft,i,ii E [E]) defined on the manifold charts U1. E M, and assign an to their correct experts, following the same mechanism as in Theorem 4.8.
Stacking J. such MoE blocks composes these representations hierarchically, approximating the final function i (#1),... SL.t (æL)).
Illustration via Example 5.1. In Example 5.1 with L, = 2 and E = 3 (3 subregions for each of math and language). Theorem 5.2 shows that depth-4 MoE network with 3 experts per layer can express all 3 x 3 = 9 tasks of the form "understand and solve the [language type] [math type] problem". Concretely,
Experts in Layer 2 (math) implement f2, for i = 1, corresponding to "solving geometry/ algebra/analysis problems", respectively.
Experts in Layer 4 (language) implement f4,; for 2, corresponding "understanding EnglisshFrrench/Germaa respectively.
Layer and the gating in Layer 2 together perform routing for æ Layer and the gating in Layer 4 together perform routing for æ2.
Theorem 5.3 (Warmup case). Let the target function f be of the form (4). Then there exists a depth-2L MoE network V E H2,,, with m 2 (EE), such that:
|| - (M) & max max [E[L] LE(E)
CPFN (Ji.s
max max O m ((fa((())))))))) LE LJ EE
2,m
approximaate I-dimensional function
Compared to Theorem 5.2, this result requires only: (i) shallower expert networks (2-layer instead of 3-layer), (ii) smaller expert width (m > (E(E) instead of ??(E?)) due to the simple geometry (Euclidean cubes).
Although each subfunction may have high-order smoothness (x(ft..) >> 1), the composite function f exhibit only low-order smoothness (e.g., x(ʃ) 0, 1) due low-order regularity at the interfaces between adjacent regions. As a result, directly approximating the global function f is inefficient. A natural and efficient approach is decompose the approximation problem into localized subproblems, each defined on simple subregion with high regularity. Our constructive MoE networks can provably achieve this approach.
6 Experimental Validation
To support our main theoretical results, we conduct two new experiments, each aligned with one of our key insights. The experimental details are shown in Appendix C.
Experiment I. Shallow MoEs for low-dimensional functions. To validate our theoretical insight in Section (Theorem 4.8): shallow MoE networks can efficiently approximate functions supported on low-dimensional manifolds and overcome the curse of dimensionality.
Specifically, we consider the low-dimensional manifold M = (æ E EDD P = 0, Vi > 2) embedded in TR. with > 2. The target function f((x) sin() + cos(3.r2, defined on M. As model, consider "I 11-4-MoE", I-layer MoE comprising I router and 4 experts, where cach

---

expert is a two-layer ReLU network with hidden width 10. To validate whether MoE can overcome the curse of dimensionality, we vary the input dimension D E {16, 32, 64, 128).
As shown in Table 3, one can see that: as increases, the test error of MoE does not increase significantly and remains stable. This supports insight that shallow MoEs efficiently approximate functions on low-dimensional manifolds and avoid the curse of dimensionality.
Table 3: (Results of Experiment 1) The test error of 1-4-MoF under different input dimensions D).
input dim D
16
32
64
128
test error
3.40e-4
3.38e-4
3.17e-4
3.42e-4
Experiment II. Deep MoEs for piecewise functions. To verify our theoretical insight in Section 5: depth-O(L) MoE networks with E experts per layers can efficiently approximate piecewise functions with E.. distinct pieces.
As defined in our Figure 3, we consider the piecewise function / with compositional sparsity defined over 32 = 9 unit cubes. As the model, we consider "2-3-MoF"" (a 2-layer MoE. comprising routing layers and 2 expert layers with 3 experts each): To illustrate the role of depth, we also consider shallow " "1-6-MoE", with comparable parameter count. Each expert is a two-layer ReLU FFN with hidden width E {16, 32, 64, 128J. To validate whether 2-3-MoE and 1-6-MoE can approximate this target, we vary the hidden width m.
The results, shown in Table 4, illustrate that: (i) As m increases, 2-3-MoE achieves rapidly decreasing error. This supports that the depth-2 MoE with experts per layers can efficiently approximate this piecewise function with 3 distinct pieces; (ii) In contrast, 1-6-MoE exhibits a performance plateau, revealing its limited expressive power. This highlights the crucial role of depth in modeling such compositional structures.
Table 4: (Results of Experiment II) The test error of the 2-3-MoE and 1-6-MoE under different hidden width
hidden width m of experts
16
32
64
128
test error of 2-3-MoB
8.32e-5
1.4le-5
4.73e-6
2.59e-6
test error of 1-6-MoE
7.96e-5
2.17e-5
2.65e-5
4.60e-5
7 Conclusion and Future Work
In this work, we provide theoretical study the expressive power of MoE networks for modeling structured complex tasks. For shallow MoE networks, we show that they can efficiently approximate functions supported on low-dimensional manifolds, overcoming the curse of dimensionality. For deep MoE networks, establish that, when the target exhibits compositional sparsity structure, they can approximate piecewise functions consisting of exponentially many distinct pieces, effectively modeling an exponential number of tasks.
Beyond compositional sparsity. Our analysis focuses on compositional sparsity, a structure that is both theoretically rich and practically relevant. However, real-world problems may involve other forms of sparsity, such as group sparsity, graph sparsity, or temporal sparsity. Characterizing the expressive power of deep MoE networks under these alternative structures is important direction for future work.
Training dynamics analysis. While our study addresses the approximation capabilities of MoF networks, a critical open question is whether such expressive solutions can be found via training algorithms such as stochastic gradient descent. Analyzing the training dynamics of MoE networks is considerably more challenging than in dense architectures, due to auxiliary bad-balancing objectives and the use of non-differentiable Top-K routing.
Acknowledgments
Mingze Wang is supported by Young Scientists (PhD) Fund of the National Natural Science Founda- tion of China (No. 124B2028).
10

---

References
Marah Abdin, Jyoti Aneja, Hany Awadalla, Ahmed Awadallah, Ammar Ahmad Awan, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Jianmin Bao, Harkirat Behl, et al. Phi-3 technical report: A highly capable language model locally on your phone. arXiv preprint arXiv:2404. /4219, 2024.
Pedram Akbarian, Huy Nguyen, Xing Han, and Nhat Ho. Quadratic gating functions in mixture of experts: A statistical insight. arXiv preprint arXiv:2410.11222 2024. 6
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681, 2017.
Cenk Baykal, Nishanth Dikkala, Rina Panigrahy, Cyrus Rashtchian, and Xin Wang. A theoretical view on sparsely activated networks. Advances in Neural Information Processing Systems, 35: 30071-30084 2022. 2
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373-1333 2003.
Richard Bellman. Dynamic programming. Science, 153(3731):34 1966. 2
Weilin Cai, Juyong Jiang, Fan Wang, Jing Tang, Sunghun Kim, and Jiayi Huang. A survey on mixture of experts in large language models. IEEE Transuctions Knowledge and Data Engineering, 2025. 1
Emmanuel Candès and Michael Wakin. An introduction to compressive sampling. IEEE signal processing magazine, 25(2):21-30, 2008. 2
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep relu networks for functions on low dimensional manifolds. Advances in neural information processing systems, 32, 2019. 6, 21
Zixiang Chen, Yihe Deng, Yue Wu, Quanquan Gu, and Yuanzhi Li. Towards understanding mixture of experts in deep learning. arXiv preprint arXiv:2208.0288 2022. 2
Nishanth Dikkala, Nikhil Ghosh, Raghu Meka, Rina Panigraby. Nikhil Vyas, and Xin Wang. On the benefits of learning to route in mixture-of eixterr-of-experts models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 9376-93966 2023. 2
David L Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4):1289-133)
2006. 1, 2
Nan Du, Yanping Huang, Andrew M Dai, Simon Tong, Dmitry Lepikhin, Yuanzhong Xu, Maxim Krikun, Yanqi Zhou, Adams Wei Yu, Orhan Firat, et al. Glam: Efficient scaling of language models with mixture-of-eppers. In International conference on machine learning, pages 5547-5569. PMLR, 2022. 3. 6
Michael Elad and Michal Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image processing, 15(12)337363377 3745, 2006. 2
Herbert Federer. Curvature measures. Transactions of the American Mathematial Society, 93(3): 418-491, 1959. 21
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 1-39,, 2022. 3
Geoffrey E Hinton and Ruslan Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 513 2
Robert A Jacobs, Michael I Jordan, Steven J Nowlan, and Geoffrey E Hinton. Adaptive mixtures of local experts. Neural computation, 3(1):79 87, 1991.
Michael Jordan and Robert A Jacobs. Hierarchical mixtures experts and the em algorithm. Neural computation, 111)111 1994.

---

Diederik P Kingma, Max Welling, et al. Auto-encoding variational bayes, 2013. 2
Minh Le, Huy Nguyen, Trang Nguyen, Trang Pham, Linh Ngo. Nhat Ho, et al. Mixture of experts meets prompt-based continual learning. Advances in Neural Information Processing Systems, 37: 119025-119062, 2024.
Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen. Gshard: Scaling giant models with conditional computation and automatic sharding. arXiv preprint arXiv:2006.16660 2020. 6
Hongho Li, Sen Lin, Lingjie Duan, Yingbin Liang, and Ness B Shroff. Theory on mixture-of-experts in continual learning. arXiv preprint arXiv:2406. 16437, 2024. 2
Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. Deepseek-v3 technical report. arXiv preprini arXiv:2412.19437, 2024. 1,6
Rui Liu, Young Jin Kim, Alexandre Muzio, and Hany Hassan. Gating dropout: Communication- efficient regularization for sparsely activated transformers. In International Conference on Machine Learning, pages 13782-13 13792. PMLR, 2022. 6
Tong Mao and Ding-Xuue Xuan Zhou. Rates of approximation by relu shallow neural networks. Journal of Complexity, 79:101784, 2023. 4
Hrushikesh N Mhaskar and Tomaso Poggio. Deep shallow networks: An approximation theory perspective. Analysis and Applications, 14(06):829-848, 2016. 2
Siyuan Mu and Sen Lin. A comprehensive survey of mixture-of-experts: Algorithms, theory, and applications. arXiv preprint arXiv:2503.071377 2025.
Huy Nguyen, Pedram Akbarian, Trang Pham, Trang Nguyen, Shujian Zhang, and Nhat Ho. Sta- tistical advantages of perturbing cosine router in sparse mixture of experts. arXiv preprint arXiv:2405.. 2415143305,, 2024. 6
Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete & Computational Geometry, 39:419-441, 2008. 21
Bruno A Olshausen and David J Field. Emergence of simple-cell receptive field properties by learning sparse code for natural images. Nature, 38 (6583)))60766 1996. 2
Tomaso Poggio. How deep sparse networks avoid the curse of dimensionality: Efficiently computable
functions are compositionally sparse. 2023. 2
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding.
science, 290(5500) 2000. 2
Uri Shaham, Alexander Cloninger, and Ronald Coifman. Provable approximation properties for
deep neural networks. Applied and Computational Harmonic Analysis, 44(3):537-557, 2018. 2, 6
Joshua B Tenenbaum, Vin de Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 2909555 2000. 1,2
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series (Methodological), 58(1):267-288 1996. 1,2
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017. 2
Mingze Wang et al. Understanding the expressive power and mechanisms of transformer for sequence modeling, Advances in Neural Information Processing Systems, 2024. 2
12

---

An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, arXiv:2407.1067/ 2024a. 3
Qwen2 technical report. arXiv preprint
An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang. Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412.15115. 2024b. 6,6
Yunfei Yang and Ding- Mung-Xuunnaaa Zhou. Optimal rates of approximation by shallow relu k neural networks and applications to nonparametric regression. Constructive Approximation, pages 1-32, 2024.
Shijun Zhang, Jianfeng Lu, and Hongkai Zhao. Deep network approximation: Beyond relu to diverse activation functions. Journal of Machine Learning Research, 25(35):1-39, 2024. 23
Simiao Zuo, Xiaodong Liu, Jian Jiao, Young Jin Kim, Hany Hassan, Ruofei Zhang, Tuo Zhao, and Jianfeng Gao. Taming sparsely activated transformer with stochastic experts. arXiv preprint arXiv:21 10.04260, 2021. 6
13

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We believe that the abstract and introduction reflect the contributions and scope the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
In Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
In Section 4 and 5; Appendix A and B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This work is purely theoretical and does not involve experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer:
[No]
Justification: The code or data of the experiments are simple and easy to reproduce following the description in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
public/guides/ Stwiiidee/ooSSuuiissttst. soiooiiisss for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https: CoodeSubmiis
httpps.cccpubiic//eecc S ssi www.insssoooiiiiiioo oniioiiyl) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In Section 6 and Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The approximation error is deterministic and there is no need to consider the eгror bars here..
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https :tapp:///neure http//eeurip...e cc hccpppbccc/tthiicccceeeeeeecee
Answer: [Yes]
Justification:
We have confirmed that the research is conducted with the NeurlPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
[NA]
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This paper does not use LLMs as important, original, non-standard component of its core methods. LLM is used only for writing, editing, or formatting purposes.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https http///eerippp.pe wwweerips.cc/oonnae wwtpe//ooeeeeeeee/22////111/ for what should or should not be described.
20

---

Appendix
Proofs in Section 4
21
A.1 Further Introduction to Manifolds
21
A.2 Proof of Theorem 4.8
22
A.3 Proof of Corollary 4.9
23
B Proofs in Section 5
24
B.1 Proof of Theorem 5.2
24
B.2 Proof of Theorem 5.3
26
Experimental Details
28
A Proofs in Section 4
A.1 Further Introduction to Manifolds
Compact smooth manifolds M C IR. are known to have strong regularity properties.
begin by introducing definition curvature of the manifold and the width of the narrowest bottleneck-like structure of M.
reach, geometric quantity affected by two factors:
Definition A.1 (reach). Let A(M) == {= RD 3p + E M,, |lp z||2 ||g =||2 inf ||y - = the set of points that have at least two nearest neighbors on M. Then the reach of WEM
inf M is defined TM sEM.UEA(M)
| 21|2.
The following lemma has established that compact smooth manifold has positive reach.
Lemma A.2 (Federer (1959)). Let M be compact smooth manifold in RDD. Then it has positive reach, i.e., TM
If M has the reach greater than > 0, then intuitively, one can roll freely ball of radius 7 around it. This ensures the existence of a well-structured atlas of compact smooth manifold in Example 4.6:
Highly regular atlas of compact smooth manifold M. (Chen et al., 2019) Let r >> and consider the open cover (I(x:r)) of M, where B(æ;r) denotes the l Euclidean ball of radius centered at æ. Since M is compact, there exists finite subcover such that M C (leEE)(((.;))) where c; E M.. Now we pick the radius < TM/2 such that
U = M n B(c,r)
diffeomorphic to ball in Rd (Niyogi et al., 2008). denote the tangent space at e₁ as Te: (M) span( ... v,a)), where (v,,1,... v..a) are orthonormal basis. Define the matrix V. " v.da] E Dxd and construct the chart map
(x(x)= - (V (x c,) + s,) E [0, 1]4, VI E U,
where b; (0, scaling factor and s; is translation vector chosen such that di (x) E [0, 1]d
Then {UU,, d:) heje is smooth atlas on M. We call it highly regular, since (i) each U, is diffeo- morphic to a ball in Rd, (ii) each chart map o, is linear function, implying infinite smoothness.
21

---

A.2 Proof of Theorem 4.8
For simplicity, we use the notation ||-|| to denote the Lo norm the proof.
Routing mechanism (Layer and gating in Layer 2).
Proof skeich: These components work together to exactly assign each input æ: to its correct expert f(2.)) Specifically, the first MoE layer (a))) behaves like a dense model, approximating the smooth partition functions p; s. Then the Layer-2 gating network g()) selects the expert corresponding to the region U, such that x E Uz.
By Theorem 3.1, there exists two-layer networks T; (i [E], with width m. 2 (((E2), such that:
| mil
Vi E [b].
4E
Let be the concatenated two-layer network of the E two-layer networks, i.e, r(x) (" " then it satisfies:
(Pl. .0....... .PE))))))))) - -PE) 4E
(6)
In Layer 1, each expert network f(1.)) IR + +.D+E shares the same form:
(z) = ((xx) -(((0))
The weight matrix W
( of the gating network ( R2 + E can be any constant, such as In
(1)
fact, Layer I behaves as a standard dense network computing
For the gating network g(2) Layer 2, we define its weight matrix as:
w (2) R
(ExE) E R Ex(+E))
Now we check the routing mechanism: given an input a E M, Layer outputs
h (x)) = T(x) E D+E
Then the gating output of the Layer 2 is
(1) w ( (1) T(x) R
Then it will assign æ to the fe-th expert network in Layer 2, where
' == arg max g (x)
arg max (z))
:E(E)
<E[B)
Since EielEy pr(x) and pi 0, Vi E [E. we must have max Pi(x) further have:
1. Using (6),
3
Tha (x) = max (x)
max Pi(
iE[E]
SE[E]
4E
4E'
which implies
1
3
1
Pso (x) > Tea (x)
0.
4F
4F
4F
2F
Thus,
U
This establishes exact assignment of x to its correct region. Expert networks (Layer 2).
22

---

Proof sketch: Each expert network f(2.8) in Layer is responsible for approximating the d- dimensional local target functions flu, 0, and the smooth chart maps di.
By Theorem 3.1, there exist two-layer dense networks 9i and ths with width m, such that
[llu, oØ, - gill &
max m
m
mm1111 1/2
}) < m
A oe A3
10: - vill & m 1/22)
Let the expert network f(2.) RD+E lk as
(120 9i o (1( 9, (x))
which is three-layer dense network and satisfies:
un (x) ((2.) (1 sup flu. o o o 0z)(2) 91 (x)
sup =eG;
=
[ll,, o Φ, o 0; flu. o oF o + flu, o o v. 91 vill
flu. o 0 o 0: flu, o oF 2 + flu, o o 0b 9i o wi
(8)
flu. 0 llo, <vill + |ffu, oΦ 9:ll
<fllo, o0 1, A3 m²) = δ m
x(fle,) ~1
m
The final estimate.
Given an input E M,, the routing mechanism assigns it to the correct expert network ((2,6)), satisfies æ U. (7). Consequently, the approximation error holds:
which
lf(z) - (x(1)) = [lle (xx) - (((2)) (1225)))((
(8) EŌ A 11
max Ô misle, EE)
Since is arbitrary, this concludes the proof.
Additionally, although this analysis is based on ReLU-activated experts, the theoretical framework extends naturally to MoEs with other activation functions (e.g., GeLU, SiLU, Swish) by using the results in Zhang et (2024).
A.3 Proof of Corollary 4.9
The proof follows exactly the structure Theorem 4.8, except for simplification in the step concerning the Expert networks (Layer 2). We illustrate only the modified part below.
Expert networks (Layer 2).
Compared to Section A.2, the key simplification is that the chart maps Φs are linear (see Example 4.6). Thus, we do not need to approximate them with neural networks. We only need to approximate the composition flu, o oz using two-layer network.
By Theorem 3.1, there exists a two-layer dense networks gt. with width m, such that
m 112 1) < δ m
n1).
|flu, o0 - gill & Ō
max
m
Let the expert network ((2))) D+E + IR as
(1 = g, (1)
9: (x),
23

---

which is two-layer dense network since @; is linear and is two-layer. It satisfies:
sup (l) - ((2.0
sup flu. o, o )((()) - 9. - 0((2))
=Et:
= =Ilfle o o oØ; 9r o mill & [ 1 D:ll
(9)
Allluca n = - (m -
<ō m
B Proofs in Section
B.1 Proof of Theorem 5.2
The key idea is that for each / E [L]. Layers 21 1 and 2/ jointly approximate the subfunction
fi, (æi), where in E {j E [E] E U1.}.
The overall network composition then constructs the full function from these subcomponents, as defined in Equation (5).
Embedding. To facilitate layerwise operations, we first embed the input æ [aI xx TT.TT RID into an extended space:
x [z] .... ......I[..0 =[,0[]= E LD-
where the final L entries are used to store the subfunctions approximated in subsequent layers. And we denote
ò = D==ID+ T.
For simplicity, we denote the output of 21-th layer (1 (T.) be (2)) RRO
Each two-layer MoE block operates similarly to the shallow studied in Section A.2, and thus the core proof strategy carries over. For completeness and clarity, we present the full proof below.
I-th routing mechanism (Layer 2/ 1 and gating in Layer 2().
Proof sketch: These components work together exactly assign æq to its correct expert f(21.)) Specifically, the first MoE layer h(21-) behaves like dense model, approximating the smooth partition functions Pı, s. Then the Layer-2 gating network (2 selects the expert corresponding to the region U, such that 2y e U1.,
By Theorem 3.1, there exists E two-layer networks Ti, (i E [E), with width my,i 2 ((FE), such that:
1
llet n.all
Wi [
4E
Let 7(!) be the concatenated two-layer network of the E two-layer networks, iee. -1) (7,,( -,,(()))) then it satisfies:
(A........ (T..E)-1 < 4E
(10)
In Layer 21 - 1, each expert network ((31-1,6) : + R DDE shares the same form:
-xx(2-21 (x1))2
(z)
(1))
The weight matrix w (2) of the gating network ( R + F can be any constant, such as 0. In fact, Layer 2/ behaves standard dense network computing (0) (x:).

---

For the gating network g( in Layer 21, we define its weight matrix as:
W (2)) (0 Ex D: IEXE) E Ex(+E).
Now we check the routing mechanism: given an input x (I1, FLL) E M, where æt E Mi,
Layer 2/ 1 outputs
(x(21-2)
(21-1) 1) (2211-22) (>71 (21) E ERO+E.
Then the gating output of the Layer 21 is
(2)) (2. ()) 1) = w (2(1) (1(21-1) (z)) 70)) (mx) E R
Then it will assign æy the in -th expert network Layer 2, where
iz arg max 9; (2!) (z)) arg max (Z:))
(c|
Since ΣiE[E] (a,( and Pr. > 0,Vie E [B], we must have m (t,:(x1) we further have:
Using (10),
3
Tim, (21) max T7,1 (x,)
max (a,) EE[B]
(E(E)
4E
4E
which implies
1
1
Piay (ai)) 2 Tie (201)
>
4F
4F
4
2F
Thus,
31 E Vime"
(11)
This establishes exact assignment of æ to its correct region.
1-th expert networks (Layer 2/).
Proof sketch: Each expert network f(21.8) in Layer 2 is responsible for approximating the d- dimensional local target functions fi,s 37,1 and the smooth chart maps ò1,;-
By Theorem 3.1, there exist two-layer dense networks gi, and thi,, with width m, such that
fi. a का - Ō max
1/2 }
m
41
4
- < ① (m-1/2
Let the expert network f(21.)) RŌ+E + RDD as
((2),0 (2)1-11) = 91,i o 4/,, 1)= E: (E)
0,11
0.-1
(21-1)
Mr, v. Og-1
Og-1
which is three-layer dense network and satisfies:
(1,((11) / //21.11 (xe (2)
J oं. o (x)) - mi v.r((a))
sup miEtii
sup z!eti.;
fi. o o., od,, fi. o oit
Vr, fis oft th,s - M1 vi-
Si, o tūt o th,s Su, o o
V2.1
Ji. o o th, - m1. 11.1
(12)
fl. o (
|1 - U1.o1l+ +
fi. o o - g1.b|
-(111007:1) 13 =0 m
2 m
25

---

The final estimate.
From the above construction, the output of the 27.th layer takes the form:
x (22) = 91,1 o Viss, (x1)
E LDDL
IL V1,io (xL))/
We decode this vector by applying linear projection that extracts the last components, yielding:
91,5 v/i, (x11)
(x) = (OLXLD, ILLL) (21)) -
E ERL.
9L Uiiden (xL)
Now consider an input æ (æ xt) M. For each I E [L], the /-th routing mechanism assigns the correct expert network f f(2l,mm)) which satisfies æt E Uin, (11). Consequently, the approximation error holds:
(xxx))
max LE(L]
(x1) gl,ia, V/rii (azi)
(12)
Ag
max
m
max max [E[L] iE(E)
m
[ELL]
Since x is arbitrary, this concludes the proof.
B.2 Proof of Theorem 5.3
The proof follows the same structure as Theorem 5.2, except for simplification in the construction of the routing mechanism. For completeness and clarity, we provide the full proof below.
The key idea is that for each I [L], Layers 21 1 and 2/ jointly approximate the subfunction
fi,i, (21), where i E {j E [E] my Ut. = [j 1,5]}-
The overall network composition then constructs the full function from these subcomponents. For simplicity, we denote the output of 21-th layer (1 E (Z]) be (21) E TR4.
I-th routing mechanism (Layer 2/ 1 and gating in Layer 2().
Proof sketch: These components work together exactly assign 2; to its correct expert f(21.)) Specifically, the first MoE layer (21-11) behaves like dense model, serving an indicator function. Then the Layer-2 gating network ((2)) selects the expert corresponding to the region U, such that I E UL,-
Consider the specific indicator function comprising 3 ReLU neurons:
(2)( = ReLU( - (i 1)) + ReLU(m i) 2ReLU(x1 - (i-1/2)), i [E]
which satisfies:
m,((a)) 1> 0 if E (i 1,
(13)
else
Let 7(0) be the concatenated two-layer network of the E two-layer networks, i.e., (x) (Z,,, ... , (x,)) Note that the width of (!!) is only 3E.
=
In Layer 2/ - 1, each expert network f(21-1.6) 124 + RL+E shares the same form:
(21-2)
(2) = 7 (xzz)
26

---

The weight matrix W a (21-1) of the gating network g( R R can be any constant, such as O. In fact, Layer 27 behaves standard dense network computing (m))
For the gating network g in Layer 21, we define its weight matrix as:
W 21) (0 (0EXL. IEXE) E R Ex(+EE)
Now we check the routing mechanism: given an input æ (x1, ,IL) E [0, EJ", where E
[0, E), Layer 2/ 1 outputs
(x(21-2)
(21-1) -2 (2(1111 (2(
E ERL-E.
(1() (zi))
Then the gating output of the Layer 21 is
(( (x
w (2111) (x)) 70 ER.
Then will assign xı to the iz -th expert network in Layer 2, where
(21) (zi) = arg max 77, (21).
iz == arg max 9;
iE[F]
<E(F)
From the property (13), we have:
27 Uta."
(14)
This establishes exact assignment of xı to its correct region.
1-th expert networks (Layer 27).
Proof sketch: Each expert network f(21.)) in Layer 2 is responsible for approximating the dimensional local target functions fi,5-
By Theorem 3.1, there exist two-layer dense networks Ir. with width m, such that
Ilfi, -1.ill & ① max m m 1/2 m-1/21 }) < Ö (m m m
Let the expert network f(21.)) BL+E + RL as
(21
la
(2),)) (2(1-1)
91. (2))
21
1+1EE
which is three-layer dense network and satisfies:
sup Eu,
f1,((11) - -s(20 (22.1) (xe (21-
sup
[f12(11) (.)())))
(15)
< Ilfis - a..ll & Ô (m -x(fe:00(
= -0(m (m-nlliiat))
The final estimate.
From the above construction, the output of the 2L-th layer takes the form:
91,te, (x1)
((x) = (21)
E E
9Li (xL)
Now consider an input æ (II,... .L) E [0, E For each / E [L], the 1-th routing mechanism assigns it to the correct expert network f fz)), which satisfies E Ut., (14). Consequently, the approximation error holds:
[x v(x))l = max fis., (x1) - gl.sz (21)
[E[L]
27

---

(15) max Ô [E
(m"
max max Ô (m=m(hidn4). [E[L] SE[E]
Since is arbitrary, this concludes the proof.
C Experimental Details
The experiments in Section 6 are conducted on A100 GPU.
In Experiment the models are trained for 2, 000 iterations with batch size 128 (online), using squared loss and Adam optimizer with learning rate 1e-3.
In Experiment II, the models are trained for 5, 000 iterations with batch size 128 (online), using squared loss and Adam optimizer with learning rate 1e-3.
28


Reviews:
[{"review_id": "ECsob1J6fv", "reviewer": "Reviewer_4bkA", "summary": "The paper conducts a systematic study on the theoretical foundations of Mixture-of-Experts (MoE) networks in modeling complex tasks. It demonstrates that shallow MoE networks can efficiently approximate functions supported on low-dimensional manifolds, overcoming the curse of dimensionality. For deep MoE networks, the paper shows that they can approximate piecewise functions with compositional sparsity, enabling the modeling of an exponential number of structured tasks. The analysis also provides insights into the roles of architectural components and hyperparameters in MoEs and offers practical suggestions for MoE variants.", "questions": "See my comments above.", "limitations": "no", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:    \n(1) The paper provides a solid theoretical analysis of the expressive power of both shallow and deep MoE networks, filling a gap in the understanding of their capabilities, thus a valuable contribution to the community.\n\n(2) It offers practical suggestions for designing MoE architectures, such as incorporating nonlinearity into gating mechanisms and using low-dimensional expert networks via autoencoding.\n\n(3) The results apply to a wide range of structured tasks, demonstrating the versatility and potential of MoE networks in various domains.\n\n(4) The paper effectively compares the efficiency of MoE networks with dense networks, highlighting the computational advantages of MoEs.\n\n\n**Weaknesses**:  \n(1) I understand this paper is more of a theory paper. However, it would be great if the authors can design some synthetic tasks (e.g., low dimensional or piecewise functions) to better illustrate their theoretical results. It would strengthen the claims and provide practical evidence of the proposed methods.\n\n(2) The analysis focuses primarily on compositional sparsity, and other forms of sparsity such as temporal sparsity on the sequential data are not explored, which might be related to the real-world language understanding task where we have seen MoE's successful usage.\n\n(3) Some recent studies have shown that token routing strategy has significant effects on the MoE performance (see references 1-4 from the list below). Just wondering whether the theoretical results in this paper would be affected by using different routing strategies in any way. It would be great if the authors can include some discussions about it.  \n\n**Reference**:   \n[1] Nguyen, et al. \"Statistical Advantages of Perturbing Cosine Router in Sparse Mixture of Experts.\" arXiv preprint arXiv:2405.14131 (2024).  \n[2] Liu, et al. \"Gating dropout: Communication-efficient regularization for sparsely activated transformers.\" International Conference on Machine Learning. PMLR, 2022.  \n[3] Zuo, et al. \"Taming sparsely activated transformer with stochastic experts.\" arXiv preprint arXiv:2110.04260 (2021).  \n[4] Lewis, et al. \"Base layers: Simplifying training of large, sparse models.\" International Conference on Machine Learning. PMLR, 2021.", "was_revised": true, "final_justification": "Thanks for providing more experiments and discussing the influence of token routing strategies. The paper would be greatly improved with it. Therefore, I am happy to raise my score to 5. Thanks for the efforts to address my previous comments :)", "rebuttal": "We sincerely thank the reviewer for the positive support and valuable feedback. We greatly appreciate the insightful review and the recognition of the significance of our contributions. The comments are highly constructive and will help us further improve our work. Below, we provide our point-by-point responses.\n\n----------------------------------------\n\n> **W1. Suggestion on experiments.** \"I understand this paper is more of a theory paper. However, it would be great if the authors can design some synthetic tasks (e.g., low dimensional or piecewise functions) to better illustrate their theoretical results. It would strengthen the claims and provide practical evidence of the proposed methods.\"\n\n**Response:**\nThank the reviewer for offering this constructive suggestion. To support our main theoretical results, we have conducted **two new experiments**, each aligned with one of our key insights.\n\n- **Experiment I. Shallow MoEs for low-dimensional functions.** \n  - **Objective.** To validate our theoretical insight in Section 4 (Theorem 4.8): shallow MoE networks can efficiently approximate functions supported on low-dimensional manifolds and *overcome the curse of dimensionality*.\n\n  - **Setup.** \n    - *Target Function*. Consider the low-dimensional manifold $\\mathcal{M}$={$\\boldsymbol{x}\\in\\mathbb{R}^D:x_1^2+x_2^2=1;x_i=0,\\forall i>2$} embedded in $\\mathbb{R}^D$ with $D>2$. The target function is $f(\\boldsymbol{x})=\\sin(5x_1)+\\cos(3x_2)$, defined on $\\mathcal{M}$.\n    - *1-4-MoE model*. We consider a 1-layer MoE comprising 1 router and 4 experts. Each expert is a two-layer ReLU network with hidden width $10$.\n    - *Training Algorithm*. To validate whether MoE can overcome the curse of dimensionality, we vary the input dimension $D\\in${16,32,64,128}. Models are trained for 2,000 iterations with batch size 128 (online), using squared loss and Adam optimizer with learning rate 1e-3.\n\n\n  - **Results & Conclusion.** The following table shows the test error of 1-4-MoE under different input dimensions $D$. \n    \n    | input dim $D$ | $16$ | $32$ | $64$ | $128$ |\n    | :----: | :----: | :----: | :----: | :----: |\n    | **test error** | 3.40e-4 | 3.38e-4 | 3.17e-4 | 3.42e-4 |\n\n    As $D$ increases, the test error of MoE does not increase significantly and remains stable. This supports our insight that shallow MoEs efficiently approximate functions on low-dimensional manifolds and avoid the curse of dimensionality.\n    \n\n- **Experiment II. Deep MoEs for piecewise functions.**\n\n  - **Objective.** To verify our theoretical insight in Section 5: depth-$O(L)$ MoE networks with $E$ experts per layers can efficiently approximate piecewise functions with $E^L$ distinct pieces.\n\n    - **Setup.** \n      - *Target Function*. As defined in our Figure 3, we consider the piecewise function $f$ with compositional sparsity defined over $3^2 = 9$ unit cubes.\n      - *2-3-MoE and 1-6-MoE models*. We consider a 2-layer MoE comprising 2 routing layers and 2 expert layers with 3 experts each. To illustrate the role of depth, we also consider a shallow 1-6-MoE, with comparable parameter count. Each expert is a two-layer ReLU FFN with hidden width $m\\in${16,32,64,128}. \n      - *Training Algorithm*. To validate whether 2-3-MoE and 1-6-MoE can approximate this target, we vary the hidden width $m$. Models are trained for 5,000 iterations with batch size 128 (online), using squared loss and Adam optimizer with learning rate 1e-3.\n    - **Results & Conclusion.** The following table shows the test error of the 2-3-MoE and 1-6-MoE under different hidden width $m$. \n        \n        | hidden width $m$ of experts | $16$ | $32$ | $64$ | $128$ |\n        | :----: | :----: | :----: | :----: | :----: |\n        | **test error of 2-3-MoE** | 8.32e-5 | 1.41e-5 | 4.73e-6 | 2.59e-6 |\n        | **test error of 1-6-MoE** | 7.96e-5 | 2.17e-5 | 2.65e-5 | 4.60e-5 |\n\n        One can see that: \n        - As $m$ increases, 2-3-MoE achieves rapidly decreasing error. This supports that the depth-$2$ MoE with $3$ experts per layers can efficiently approximate this piecewise function with $3^2$ distinct pieces.\n        - In contrast, 1-6-MoE exhibits a performance plateau, revealing its limited expressive power. This highlights the crucial role of depth in modeling such compositional structures.\n\nWe will incorporate these results and figures in the revised version and add additional synthetic tasks to further illustrate our theoretical findings.\n\n----------------------------------------\n\n> **W2. Other forms of sparsity.** The analysis focuses primarily on compositional sparsity, and other forms of sparsity such as temporal sparsity on the sequential data are not explored, which might be related to the real-world language understanding task where we have seen MoE's successful usage.\n\n**Response:** We thank the reviewer for this insightful suggestion. We agree that temporal sparsity is highly relevant to natual language tasks and deserves theoretical exploration. While the current analysis focuses on compositional sparsity, we believe the unified insight remains applicable: MoEs can effectively discover the underlying structure priors (temporal sparsity), and subsequently decompose them into simpler subproblems, each solved by specialized experts. We will explore this direction in future work.\n\n----------------------------------------\n\n> **W3. Influence of routing strategies.** Some recent studies have shown that token routing strategy has significant effects on the MoE performance (see references 1-4 from the list below). Just wondering whether the theoretical results in this paper would be affected by using different routing strategies in any way. It would be great if the authors can include some discussions about it.\n\n**Response:** We thank the reviewer for raising this insightful point and for providing relevant references. In our revised version, we will expand the discussion near L213–L220. Below, we summarize our preliminary views:\n\n- **Linear routing.** As noted in L213–L220, since standard gating function is linear and lacks the capacity to model nonlinear partition functions, an additional MoE (or dense) layer is needed prior to gating to approximate partition functions.\n- **Highly nonlinear routing.** If the router incorporates sufficient nonlinearity, e.g., a two-layer ReLU routing network, it can directly model complex partitions, reducing the number of parameters required in experts. For instance, in Theorem 4.8, the required depth will reduce from $2$ to $1$, because the nonlinearity in router eliminates the need for a preceding MoE layer. Similarly, in Theorem 5.2, the required depth will reduce from $2L$ to $L$. We will formalize these results in the revised version.\n- **Other routing mechanisms.** Routing functions such as cosine routing [1] and quadratic routing [5] can also introduce nonlinearity, and may similarly reduce the parameter complexity of the experts. Additionally, routing dropout [2] and stochatic routing [3], though not more expressive than linear routing, may improve training stability and load balancing.\n\n----------------------------------------\n\n**References**\n\n[5] Akbarian et al., Quadratic gating functions in mixture of experts: A statistical insight. arXiv preprint arXiv:2410.11222 (2024)."}, {"review_id": "6BuwePRUsU", "reviewer": "Reviewer_4aPH", "summary": "This paper draws the parallel between MoE networks with structured tasks, by showing an MoE model having representation capacity of a $E^L$-piece piecewise function class.", "questions": "See Weaknesses (for lack of better naming).", "limitations": "Paper listed potential mismatch between theory and real-world problems, and whether SGD can train such a (theoretical) MoE model. No potential impact is listed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n- Introduction, motivation, and organization is clear; with annotation in theorems/equations whenever available.\n- Rigorous proof for a simple-sounding concept, specifically analyzing the un-simplified (i.e. close to the real implementation) linear MoE router.\n\n### Weaknesses\n- Difficult to follow notations.\n  - Overloaded notation: $\\alpha$ were used as softmax outputs (L105), then an integer permutation vector (L117)\n  - Related, what is $\\mathcal{A}$?\n  - Similarly, $f|_{U_i}$ in Theorem 4.8 onwards were never formally defined.\n- Albeit this is a purely theoretical work, experimental results would greatly benefit the persuasion of the paper.\n  - The authors could _manually_ craft a theoretical 4-3-MoE to fit the toy problem in Fig. 3, then compare it to baselines such as VI.", "was_revised": true, "final_justification": "I still think this is a solid Accept. It isn't groundbreaking enough to get a 6, and very much deserves a 5.", "rebuttal": "We sincerely thank the reviewer for the positive support and valuable feedback. We greatly appreciate the insightful review and the recognition of the significance of our contributions. The comments are highly constructive and will help us further improve our work. Below, we provide our point-by-point responses.\n\n----------------------------------------\n\n> **W1. Ambiguities in notation.** \"Difficult to follow notations. Overloaded notation: $\\alpha$ were used as softmax outputs (L105), then an integer permutation vector (L117); Related, what is $\\mathcal{A}$?; Similarly, $f|_{U_i}$ in Theorem 4.8 onwards were never formally defined.\"\n\n**Response:** We thank the reviewer for carefully pointing out these ambiguities. In the revised version, we will thoroughly review the notation to ensure consistency and clarity. Specifically,\n- The symbol $\\alpha$ is indeed overloaded. We will revise its usage at L117 to $\\beta$.\n- The symbol $\\mathcal{A}$ refers to an index set. In most cases in this work, it is simply $\\mathcal{A}=[E]$, where $E$ is a positive integer.\n- The notation $f|\\_{U_i}$ refers to the restriction of a function $f:\\mathcal{M}\\to\\mathbb{R}$ to a subset $U_i\\subset\\mathcal{M}$. That is, $f|\\_{U_i}:U_i\\to\\mathbb{R}$ is defined by $f|\\_{U_i}(\\boldsymbol{x}):=f(\\boldsymbol{x})$ for all $\\boldsymbol{x}\\in U_i$.\n\n----------------------------------------\n\n> **W2. Suggestion on experiments.** \"Albeit this is a purely theoretical work, experimental results would greatly benefit the persuasion of the paper. The authors could manually craft a theoretical 4-3-MoE to fit the toy problem in Fig. 3, then compare it to baselines such as VI.\"\n\n**Response:** We thank the reviewer for the constructive suggestion to include empirical results, particularly regarding fitting the toy problem in Figure 3. To support our theoretical findings, we have conducted **two new experiments**:\n- **Experiment I. Shallow MoEs for low-dimensional functions.**\n- **Experiment II. Deep MoEs for piecewise functions.**\n\nTo avoid redundancy, we kindly refer the reviewer to our **response to W1 from Reviewer 4bkA**,  where we describe the experimental setups and results in detail.\n\nSpecifically, our Experiment II demonstrates that a 2-3-MoE can successfully fit the function in Figure 3. While our theoretical analysis considers a more general case and suggests that 4 layers may be required, we found that 2 layers are both sufficient and necessary for this specific example.\n\nLastly, we kindly ask the reviewer to clarify what is meant by \"baselines such as VI.\" We would be happy to consider it in future empirical comparisons."}, {"review_id": "PIvT0Judj9", "reviewer": "Reviewer_rAT9", "summary": "The authors analyze the expressive power of sparse MoE models when data (1) lies on a low-dimensional manifold or (2) exhibits compositional sparsity. They find that sparse MoEs can match the approximation power of comparable dense networks while evaluating only $1/E$ of the expert parameters per input in both the (1) low-dimensional manifold setting and (2) the compositional sparsity setting, ignoring the routing parameters and assuming the router can correctly route to the correct expert.", "questions": "* Is there potentially an issue with how a Top-1 gate maintains a clear margin so that each input is routed to a single expert, especially near chart boundaries?\n* In the deep MoE setting, have you looked at how small routing errors in one layer might propagate through the stack, and whether a bound on that accumulation is possible?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n* The paper is clearly written and presented\n* Results seem interesting and plausible, though I have not carefully verified the results\n\n### Weaknesses\n* On line 319, should the expression currently written as \n$$ ( f_{1,i_1}(x_1),\\cdots, f_{1,i_L}(x_L) ) $$\ninstead be:\n$$ ( f_{1,i_1}(x_1),\\cdots, f_{L,i_L}(x_L) ) $$\n* The paper's claims may hinge on assumptions about the router, in particular that it picks the one correct expert for every input. \n* The paper contains no empirical comparisons or discussions of MoE scaling laws, although this is standard for expressivity papers.", "was_revised": true, "final_justification": "The paper appears to be theoretically solid. The authors responded to my questions well, and the paper seems well-regarded by the other reviewers. I'll keep my confidence relatively low at 2.", "rebuttal": "We sincerely thank the reviewer for the positive support and valuable feedback. We greatly appreciate the insightful review and the recognition of the significance of our contributions. The comments are highly constructive and will help us further improve our work. Below, we provide our point-by-point responses.\n\n----------------------------------------\n\n> **W1. A typo.** On line 319, should the expression currently written as $(f_{1,i_1}(x_1),\\cdots,f_{1,i_L}(x_L))$ instead be: $(f_{1,i_1}(x_1),\\cdots,f_{L,i_L}(x_L))$. \n\n**Response:** We are grateful to the reviewer for identifying the typo. In the revised version, we will carefully read through the whole paper and correct all typos.\n\n----------------------------------------\n\n> **W2. Assumptions on the router.** The paper's claims may hinge on assumptions about the router, in particular that it picks the one correct expert for every input.\n\n**Response:** We thank the reviewer for raising this insightful point. We will incorporate a discussion of this issue in the revised version. Our response is as follows:\n\n- First, our results are constructive and concern the expressive power of MoE networks. We explicitly prove the existence of a MoE which can **perfectly assign** each input to its correct expert. However, as discussed in Section 6, a key open question is whether such solutions can be discovered by training algorithms such as stochastic gradient descent.\n\n- **Extension to Top-$K$ routing.** Our results extend naturally from top-1 routing to top-$K$ routing. For example, given an MoE network $\\Psi$ using top-$1$ routing, we can construct another MoE network $\\Psi'$ using top-$2$ routing, with twice as many experts by duplicating each expert in expert in $\\Psi$. Notably, $\\Psi'$ has equivalent expressivity as $\\Psi$.\n  \n- **Efficiency of Top-1 routing.** In some cases, top-1 routing may be nearly optimal. For example, under the setting of Theorem 4.8, some input $x$ belongs exclusively to a single subregion $U_i$, and activating additional experts may actually increase approximation error. This view aligns with recent empirical findings suggesting that increased sparsity can improve MoE performance (e.g., Kimi-K2 technical report, 2025.07).\n\n----------------------------------------\n\n> **W3. Suggestion on experiments.** The paper contains no empirical comparisons or discussions of MoE scaling laws, although this is standard for expressivity papers.\n\n**Response:** We thank the reviewer for the valuable suggestion to include empirical results. To support our theoretical findings, we have conducted **two new experiments**:\n- **Experiment I. Shallow MoEs for low-dimensional functions.**\n- **Experiment II. Deep MoEs for piecewise functions.**\n\nTo avoid redundancy, we kindly refer the reviewer to our **response to W1 from Reviewer 4bkA**,  where we describe the experimental setups and results in detail.\n\n----------------------------------------\n\n> **Q1. Routing near chart boundaries.** Is there potentially an issue with how a Top-1 gate maintains a clear margin so that each input is routed to a single expert, especially near chart boundaries?\n\n**Response:** We thank the reviewer for this interesting question. \nWhen an input $x$ lies in the overlap of two atlas regions, $U_i$ and $U_j$, (e.g., near the chart boundaries), both corresponding experts, $f^{(i)}$ and $f^{(j)}$, can provide efficient approximation over the intersection $U_i\\cap U_j$. By our construction (detailed in the Proof of Theorem 4.8), the router may assign $x$ to either expert $i$ or $j$. Regardless of which expert is selected, the resulting approximation remains valid and accurate.\n\n----------------------------------------\n\n> **Q2. Propagation of routing errors in deep models.** In the deep MoE setting, have you looked at how small routing errors in one layer might propagate through the stack, and whether a bound on that accumulation is possible?\n\n**Response:** We thank the reviewer for this insightful question. \n- **Theoretical expressivity.** Our main theorems establish the existence of a router that **perfectly assigns** each input to its correct expert. In this idealized setting, routing errors do not occur, and hence no error propagation arises.\n\n- **Practical training.** During training, however, routing errors are inevitable. We hypothesize that in the worst case, such errors may propagate multiplicatively with depth. Nevertheless, if MoEs have learned good representations, e.g., if each layer specializes in a correct class of subtasks, as in Equation (5), then routing errors may not accumulate significantly but instead remain stable across layers. This would be an exciting direction for future understanding."}, {"review_id": "QtdhMoMHEA", "reviewer": "Reviewer_9CGn", "summary": "In this article, the authors illustrate the capacity of Mixture of Expert (MoE) model for approximating a function $f$ over a manifold $\\mathcal{M}$. Based on the known result for two-layer ReLU networks (Theorem 3.1) in \\cite{}, the main result (Theorem 4.8) shows that the MoE model can approximate with an error of $\\mathcal{O}(m^{-(\\kappa/d \\wedge 1/2)})$, where $d$ is the intrinsic dimension, $\\kappa$ control the smoothness of function $f$, and $m$ controls the width of network. \nThis result demonstrates the outstanding ability of the MoE model over shallow dense network, which approximate with error $\\mathcal{O}(m^{(-\\kappa/D\\wedge 1/2)})$, where $D$ is the ambient dimension of $\\mathcal{M}$. The author formularises the multiple tasks problem using piecewise functions and product of manifold, and derives the analogous result for this situation, which similarly shows the capacity of MoE to approximate a function with error depennds on intrinsic dimension.", "questions": "1. The article mentions the concept of reach, how can we use and how important this concept in this article? \n\n2. In equation 7, there may be some situations that $x$ belongs to two atlas, so what happens in this case?\n\n3.  As I mention in strength and weakness part, can we extend the model to the case of other activating function rather than ReLU (like softmax, GeLU, etc,...)", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n1.  The result is nice overall and meaningful, which can significantly improve the known bound $\\mathcal{O}(m^{-(\\kappa/D \\wedge 1/2)})$ to $\\mathcal{O}(m^{-(\\kappa/d \\wedge 1/2)})$. This improvement shows the adaptability of MoE model in the case of low dimension. \n\n2. The author provides a significant suggestion for MoE mechanism, such as non-linear gating function, alternation between MoE network and dense network.\n\n3. The writing is clear and easy to read, the new concept is well-explained with several examples. \n\nWeaknesses: \n\n1. The paper should provide some experiments to support the result for the case of low dimension. \n\n2. Besides the algorithm that prove the existence of good enough MoE, the paper should provide an algorithm to find a feasible neural network. \n\n3. It appears that the model only consider one kind of gating function (ReLU), so it would be much better to consider other gating functions, like GeLU, softmax, etc. \n\nDespite of some experimental drawback in the paper, the theoretical result here is excellent and interesting, which provides a rigorous justification for the adaptability of MoE model.", "was_revised": true, "final_justification": "Thanks for the response and clarifications. I appreciate the effort you put into addressing these points in detail.\nI will remain my score.", "rebuttal": "We sincerely thank the reviewer for the positive support and valuable feedback. We greatly appreciate the insightful review and the recognition of the significance of our contributions. The comments are highly constructive and will help us further improve our work. Below, we provide our point-by-point responses.\n\n----------------------------------------\n\n> **W1. Suggestion on experiments.** The paper should provide some experiments to support the result for the case of low dimension.\n\n**Response:** We thank the reviewer for the constructive suggestion to include empirical results, particularly regarding the low-dimensional case. To support our theoretical findings, we have conducted **two new experiments**:\n- **Experiment I. Shallow MoEs for low-dimensional functions.**\n- **Experiment II. Deep MoEs for piecewise functions.**\n\nTo avoid redundancy, we kindly refer the reviewer to our **response to W1 from Reviewer 4bkA**,  where we describe the experimental setups and results in detail.\n\n----------------------------------------\n\n> **W2. Training algorithms.** Besides the algorithm that prove the existence of good enough MoE, the paper should provide an algorithm to find a feasible neural network.\n\n**Response:** We thank the reviewer for this suggestion. Our current results focus on the expressivity of MoE archetuctues, which serves as a foundational step toward a deeper theoretical understanding of MoEs. As noted at Section 6, a key direction for future work is to investigate whether such expressive solutions can be discovered through optimization algorithms. Analyzing this question presents additional challenges, including MoE-specific training instability and the highly non-convex loss landscape. We leave this important direction for future investigation.\n\n----------------------------------------\n\n> **W3 & Q3. Extension to other activation functions.** It appears that the model only consider one kind of gating function (ReLU), so it would be much better to consider other gating functions, like GeLU, softmax, etc. As I mention in strength and weakness part, can we extend the model to the case of other activating function rather than ReLU (like softmax, GeLU, etc,...)\n\n**Response:**\nWe thank the reviewer for this constructive question. Although our current analysis is based on ReLU-activated experts, the theoretical framework extends naturally to MoEs with other activation functions (e.g., GeLU, SiLU, Swish). This extension is feasible because our results rely on prior study establishing the expressivity of two-layer ReLU networks (Theorem 3.1). To extend the results, we only need to substitute the ReLU-specific approximation results with analogous results for the desired activation functions. For instance, for GeLU, SiLU, and Swish, the approximation theory developed in [1] can be used. In the revised version, we will include a detailed discussion of this extension.\n\n----------------------------------------\n\n> **Q1. About the concept of reach.** The article mentions the concept of reach, how can we use and how important this concept in this article?\n\n**Response:** We thank the reviewer for this thoughtful question. The concept of reach is introduced in the appendix to illustrate that common low-dimensional manifolds with positive reach admit well-structured atlas, where the chart maps are linear. For example, *Example 4.6 satisfies this condition*. We apologize that this connection is not clearly stated in the current version. In the revised version, we will explicitly mention this it in Example 4.6 and elaborate further in the appendix.\n\n----------------------------------------\n\n> **Q2. Overlapping atlas regions.** In equation 7, there may be some situations that $x$ belongs to two atlas, so what happens in this case?\n\n**Response:** We thank the reviewer for this insightful question. When an input $x$ ies in the overlap of two atlas regions, $U_i$ and $U_j$, both corresponding experts, $f^{(i)}$ and $f^{(j)}$, can provide efficient approximation over the intersection $U_i\\cap U_j$. In this case, the router may assign $x$ to either expert $i$ or $j$; i.e., the index $i_{\\boldsymbol{x}}$ in Eq. (7) can be either $i$ or $j$. Regardless of which expert is selected, the resulting approximation remains valid and accurate.\n\n----------------------------------------\n\n**References**\n\n[1] Zhang et al., Deep Network Approximation: Beyond ReLU to Diverse Activation Functions. Journal of Machine Learning Research, 2024."}, {"review_id": "Xv3lBvfndi", "reviewer": "Reviewer_4U7j", "summary": "The paper presents a theoretical analysis of expressivity of mixture-of-experts (MoE) networks in the context of complex tasks governed by two structural priors: low-dimensionality and sparsity.", "questions": "- What is the concrete definition of each MoE layer $h^{(l)}$, including the dimensionality of its inputs and outputs? Providing a clear and detailed definition would help readers understand the MoE model more easily.\n\n- In practical applications, how large does the layer depth $L$ compare to the input dimension $d$ for a given target function in practice? Expanding on this point could help readers see how the theoretical result overcomes the curse of dimensionality.\n\n- (minor, a typo?) Should the assumption in Theorem 5.3 be \"Let the target function $f$ be of the form (5)\" rather than \"of the form (4)\"?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n- The paper provides a solid theoretical framework with clear proofs outlining the approximation capabilities of both shallow and deep MoE networks.\n- The work brings a novel angle to the study of network expressivity. This analysis bridges the gap between empirical successes of modern deep learning models and their theoretical understanding.\n- The discussion on architectural design (e.g., nonlinear gating and alternating structures) is valuable for practitioners, as it provides insights into how theoretical improvements can translate into better network designs for real-world tasks.\n\n**Weakness**: There is no major weakness in this work in my opinion. Some minor weaknesses are included in **Question** part.", "was_revised": true, "final_justification": "After the rebuttal and discussions, I will keep my positive evaluation for the paper.", "rebuttal": "We sincerely thank the reviewer for the positive support and valuable feedback. We greatly appreciate the insightful review and the recognition of the significance of our contributions. The comments are highly constructive and will help us further improve our work. Below, we provide our point-by-point responses.\n\n----------------------------------------\n\n> **Q1. Definition of MoE layer.** What is the concrete definition of each MoE layer $h^{(l)}$, including the dimensionality of its inputs and outputs? Providing a clear and detailed definition would help readers understand the MoE model more easily.\n\n**Response:** We thank the reviewer for the suggestion to clarify the definition. For simplicity, let us denote an MoE layer $h^{(l)}$ by $h$, which comprises a routing network $g$ and expert networks $f^{(k)},k\\in[E]$. The definition of $h$ follows the procedure described in Lines L103-L105: given an input $\\boldsymbol{x}\\in\\mathbb{R}^{d_{\\rm in}}$, the output is $h(\\boldsymbol{x}):=\\boldsymbol{y}\\in\\mathbb{R}^{d_{\\rm out}}$, where $\\boldsymbol{y}$ is defined in L104. Here, $d_{\\rm in},d_{\\rm out}\\in\\mathbb{N}$ are general positive integers. In the revised version, we will include addiontional clarification to improve readability and completeness.\n\n----------------------------------------\n\n> **Q2. Depth vs. dimensionality.** In practical applications, how large does the layer depth $L$ compare to the input dimension $d$ for a given target function in practice? Expanding on this point could help readers see how the theoretical result overcomes the curse of dimensionality.\n\n**Response:** \nWe thank the reviewer for this insightful question. According to our theory in Section 5, the required depth $L$ depends not on the input dimension $d$, but on the compositional sparsity of the target function. In particular, Theorem 5.2 shows that for approximating functions of the compositional form (5), the required network depth is $2L$, independent of how large $d$ is. In comparison, our results in Section 4 emphasis that shallow MoE networks can overcome the curse of dimensionality when the target function is supported on low-dimenisonal manifolds. \n\n\nAdditionally, to support our theoretical findings, we have conducted **two new experiments**:\n- **Experiment I. Shallow MoEs for low-dimensional functions.**\n- **Experiment II. Deep MoEs for piecewise functions.**\n\nTo avoid redundancy, we kindly refer the reviewer to our **response to W1 from Reviewer 4bkA**,  where we describe the experimental setups and results in detail.\n\n----------------------------------------\n\n> **Q3. Clarification on Theorem 5.3.** (minor, a typo?) Should the assumption in Theorem 5.3 be \"Let the target function $f$ be of the form (5)\" rather than \"of the form (4)\"?\n\n**Response:** We thank the reviewer for this question. We would like to clarify that form (4) is a special case of the more general compositional structure given in form (5). While Theorem 5.2 addresses the general case (5), Theorem 5.3 focuses on the special case of form (4), which allows us to derive sharper bounds on the required depth and width of the expert networks."}]

Author rebuttal:

Meta-review: This paper analyses the expressive power of mixture of experts (MoE).

In particular authors prove that  shallow MoE networks  approximate functions supported on low-dimensional manifolds, overcoming the curse of dimensionality. For deep MoE networks, the paper shows that they can approximate piecewise functions with compositional sparsity. 

Reviewers were all appreciative of the paper and the analysis and they suggested adding illustrative experimental results which we are added during the rebuttal. Reviewers suggested discussing other form of sparsity such as the temporal one as well as different routing strategies or different non-linearities, authors provided elements of responses to this which should be incorporated in the final manuscript. In addition to this reviewers pointed to several notational issues that made some parts difficult to follow, authors promised fixing these.
Decision: Accept (spotlight)