Combinatorial Capacity of modReLU Complex Networks: VC-Dimension Bounds and Lower Limits
Authors: Mehmet Altunören
Venue: Accepted by TMLR ()

Abstract: Complex-valued neural networks (CVNNs) are increasingly used in settings where both magnitude and phase of the signal carry information; see, e.g., (10; 11; 13; 15). In particular, deep networks with the modReLU activation (18) have been used extensively in applications such as MRI reconstruction, radar, and complex-valued time-series modeling. While approximation properties of such networks have recently been analyzed in detail (6), their statistical capacity in the sense of VC-dimension has not, to the best of our knowledge, been studied. In this paper we formalize a natural class of fully connected deep complex-valued networks with modReLU activation and real sign output. Via the standard identification $\mathbb{C}^d \cong \mathbb{R}^{2d}$, we view these models as binary classifiers on $\mathbb{R}^{2d}$. Let $W$ denote the total number of real-valued trainable parameters, including the real and imaginary parts of all weights and biases as well as the real modReLU bias parameters. Using tools from real algebraic geometry and a VC-dimension bound for semi-algebraic concept classes due to Goldberg and Jerrum (8), together with quantitative bounds for quantifier elimination (4), we prove that for any architecture with $W$ parameters and depth $L$, the VC-dimension of the corresponding hypothesis class is at most on the order of $W^2 \log W$, with a universal constant independent of the particular architecture. On the other hand, by restricting to real inputs and parameters and exploiting results of Harvey, Liaw, and Mehrabian (9) and Bartlett et al. (3) on deep networks with piecewise-linear activations, we obtain lower bounds of order $WL \log(W/L)$ for suitable depth-$L$ architectures within the modReLU class. Thus the VC-dimension of these networks grows at least linearly in both $W$ and $L$, and at most quadratically in $W$ up to a logarithmic factor. Closing this gap is an interesting open problem.

Published in Transactions on Machine Learning Research (April/2026)
Combinatorial Capacity of modReLU Complex Networks: VC-Dimension Bounds and Lower Limits
Mehmet Altunören Sabancs University
Reviewed on OpenReview: https: openreview. net/ ftt//oorm? id= j.jJnfffS
Abstract
Complex-valued neural networks (CVNNs) are increasingly used in settings where both mag- nitude and phase of the signal carry information; see, e.g,, I12 deep networks with the m. activation @ 20) have been used extensively in applica- tions such as MRI reconstruction, radar, and complex-valued time-series modeling. While approximation properties of such networks have recently been analyzed in detail (8), their statistical capacity in the sense of VC-dimension has not, to the best of our knowledge, been studied. In this paper we formalize a natural class of fully connected deep complex-vale valued networks with modReLU activation and real sign output. Via the standard identification Cd = 2d view these models as binary classifiers on R2d Let W denote the total number of real-valued trainable parameters, including the real and imaginary parts of all weights and biases as well as the real modReLU bias parameters. Using tools from real algebraic geometry and a VC-dimension bound for semi-algebraic concept classes due to Goldberg and Jerrum (OO), together with quantitative bounds for quantifier elimination (5), we prove that for any architccture with W parameters and depth L, the VC-dimension the corre- sponding hypothesis class is at most on the order of 1o W, with a universal constant independent of the particular architecture. On the other hand, by restricting to real inputs and parameters and exploiting results of Harvey, Liaw, and Mehrabian (II) and Bartlett et al. (4) on deep networks with piecewise-lineat activations, we obtain lower bounds of order Wol/o(W/L) for suitable depth-L. architectures within the modReL.U class. Thus the VC-dimension of these networks grows at least lincarly in both W and L, and at most quadratically W up to a logarithmic factor. Closing this gap is an interesting open problem.
13 17]. In particular, 1
1 Introduction
In many pignal--rocessing problems the natural data space is complex-valued. Examples include MRI, radar, wireless communication channels, and certain Fourier or wavelet representations of time series. For such problems, complex-valued noural networks (CVNNs) have been proposed as a more natural alternative to real networks; see, for instance, 12 14 20 15 I1 and the references therein. In these architectures all weights, biases, and activations are complex, and the network computes map from Cd Ck.
Other complex-valued activations. modReLU is only one of several activation functions used in CVNNs. Beyond amplitude- phadeeepaseeeea constructions such modReLU 2 20), common choices include split activations that apply a real nonlincarity separately to R(z) and 3(2) (often called CReLU split-ReL.U), quadrant-gated variants such as zReLU, and learned or nonparametric complex activations (e.g., kernel-based complex activation mechanisms) (15 16). These alternatived are widely used in practice and sometimes pre-
ferred for optimization or implementation reasons (e.g., avoiding explicit normalization by [z]).
Recently, there has been considerable progress on the approximation theory of CVNNs. In particular, Geuchen and Voigtlaender ( established explicit quantitative error bounds for approximating smooth func-

---

Published in Transactions on Machine Learning Research (April/2026)
tions on compact subsets of Cd by complex-valuet networks with the modReLU activation function (20) and showed that the rates are optimal up to logarithmic factors. Follow-up work has treated phenomena such as depth separation and universality for narrow complex networks ( 14). A recent survey by Bassey, Qian, and Li (15) gives a broad overviow of complex activations, Wirtinger calculus, and optimization aspects.
In contrast, the statistical learning theory of CVNNs is still largely undeveloped. For real networks, a rich body of work has characterized the VC-dimension and pseudo-dimension of various architectures since the classical paper of Baum and Haussler (6) and the monograph of Anthony and Bartlett (I). For example, deep ReLU networks with W real parameters and depth L are now known to have VC-dimension on the order of
WL W, and this dependence is essentially tight 4 Related results characterize the pscudo-dimension of real networks in regression settings [8
A natural question is whether these nearly tight results for real networks can be transferred to complex- valued architectures by using the standard identification Cd = IR2d (sending x + iy to (ax y) coordinato-wise) For after this identification, one can indeed hope to
networks with activations that remain import the classical region-counting and sign-pattern arguments; this includes, for instance, split activations such CReLU, which avoid normalization by |z| and hence typically admit a more direct reduction to the real piecewise- linear setting. For modReLU networks, however, such a transfer is not available as a black box. The sharp W I. log W analyses for deep real networks in [[] 4 proceed by exploiting that the network computes a sencewwsse-plyyonnie by activation gates; this structure enables counting the number of distinct affine regions and hence the number of labelings the network can realize. In contrast, when modReLU is written in real coordinates = = x+ty, its active branch contains the normalization factor z/|=| with |a| Vx² + y², i.e., expressions involving division by /x² + y². Consequently, the real-coordinate representation of modReLU is not siccewie-poolnomial in (z. v) in the sense required by these arguments, and the existing @(W L log W) upper-bound proofs for piecowiso-lincar networks cannot be applicd directly to modReLU architectures.
(in particular, piecewise-
map of the input, with a partition induced
Why modReLU merits a dedicated analysis. Among complex-valued activations, modReLU oceu- pies a distinctive position that makes it both practically important and theoretically challenging. On the practical side, modReLU is the standard noulinearity in several influential CVNN architectures for MRI reconstruction, radar signal processing, and unitary recurrent networks 2 20 177,, and its phaso-preserving property the activation rescales the magnitude while leaving the phase of its input unchanged is a key in- ductive bias in domains where phase information carries physical meaning (e.g., coherent imaging and array signal processing). On the theoretical side, mod is the simplest widely-used complex activation whose real-coordinate representation is genuinely gebraic (square-root) nonlinearities that prevent a direct reduction to the well-understood piecewise- setting. Split activations such as CReLU, by contrast, reduce immediately to real piecewise-linear networks after identifying Cd R2d, and thus inherit the classical ( log W) bounds with only routine book- keeping. Studying modReLU therefore requires gemuinely new proof techniques the semi-algebraic lifting and quantifier-elmmnation strategy developed here-which are likely to be relevant for other activations with similar algebraic structure (e.g., phase-dependent gating mechanisms or activations involving |>] in a pol-oolyloiial way).
the normalization 2/|z| introduces al-
Our contribution is to show that, despite this obstruction, the decision regions of modReL.U networks can still be controlled using semi-algebraic methods after suitable lifting. By introducing auxiliary radius variables satisfying r² = x² + y², the modReLU gate and the full forward pass admit an existential description by polynomial equalities and inequalities of bounded degree. Projecting out the auxiliary variables yields a semi- algebraic description of the decision set via. Tarski-Scidenberg (quantificr climination) (19 5. This reduction allows us to invoke the general VC-dimension bound for semi-algebraic concept classes due to Goldberg and Jerrum (IO), together with quantitative bounds for quantifier elimination b. to obtain parameter-coume dependent VC-dimension upper bounds for modReLU complex networks. The price of using a generic projection/ pnpiection/qunttifrrreo. qquantifer-ciiminatue is reflected in the O(W2 log W) bound proved in this work.
step is an additional factor in the resulting description complexity, which
2

---

Published in Transactions on Machine Learning Research (April/2026)
Implications for other activations. The same high-level semi-algebraic strategy be applied to other complex activations whose input-output relation can be expressed (possibly after introducing auxil- iary variables) by polynomial equalities and inequalities of bounded degree. In particular, for activations that are piccevise-polyyomiall after identifying Cd = IRd (such as split activations), one expects that sharper O(WL L. log Hyype upper bounds may be attainable by adapting the classical real-nelwork arguments, with- out incurring the additional blow-up from generic quantifier elimination. For example, for split activations such as CReLU/splli-ReLLU after identifying Cd R2d the network becomes standard real piecewise- linear network with constant number of pieces, so the known @ L log W) VC-dimension bounds (up to constant-factor changes in parameter counting) apply directly (II +. A systematic VC-dimension compari- son across the landscape of complex activations (including learned nonparametriaccccccccc ones (T)) is an interesting direction for future work.
Beyond serving as combinatorial complexity measure, the VC-dimension controls the growth function (via Saucr-Shelah type bounds) and yiclds classical sample-complexity and unfform--onverrennce guaran- lees for ERM-style learning (2T T-- Thus, bounding the VC-dimension of CVNNs provides a principled way to compare their statistical capacity to real-valued architectures and complements existing norm-based gencralization analyses 7
For complex-valued networks there are, to the best of our knowledge, no analogous capacity results in terms of VC-dimension. The only global complexity bounds we are aware of are recent norm- based generalization bounds that control the generalization gap via a spectral-complexty, measure for CVNNs (7), which is a different notion from combinatorial capacity. The main purpose of this work is begin closing this gap by providing VC-dimension bounds for a widely used complex-valued architecture family.
Contributions. At a high level, the contributions of this paper are as follows.
We formalize a natural class of fully connected deep complcx-valued networks with modReLU ac- tivation and real sign output. Via the standard identification Cd R2d, we view these models as binary classifiers on R22d
We show that the corresponding decision regions form a serni-algebraic family in (0,x) whose de- scription complexity- terms of the number and degree of defining polynomials can be bounded in terms of the architecture and the number W of real-valued trainable parameters.
Using the VC-dimension bound for semi-algebraic concept classes due to Goldberg and Jerrum (I0). combined with quantitative bounds on quantifier elimination 5 we derive an upper bound of order W log W for the VC-dimension of this class.
By specializing real inputs and constraining parameters appropriately, we show that our class con- tains, subclass, real-valued networks with fixed piccewise-linear activation. Results of Harvey, Liaw, and Mehrabian [ and Bartlett et al. 4 then imply lower bounds of order W L log(W//L for suitable architectures, showing that the VC-dimension must grow at least linearly in both W and L.
We discuss how the same approach could be extended to other complex activations and to pseudo- dimension, and outline several open problems, including whether the W log W upper bound can be sharpened towards W log W in the complex-vauedd setting.
2 Preliminaries
We collect notation and background results used in the sequel. Standard references for VC-dimension and statistical learning theory include (2T 22).
Notation. We write R(z and 3(z) for the real and imaginary parts of = E C. We identify C² with R via the bijection v 2ddd + Ed defined by
(aa, bi,...,, ad, ba) (a1 ab. - ad iba)-
3

---

Published in Transactions on Machine Learning Research (April/2026)
For binary classification we sign R + [+1,-1} with the convention sign(t) +1 if and sign (1) 1 if < O. A network of depth I. has I 1 hidden layers and one output layer; we index layers by f= O,..., L with no = d and nr 1.
VC-dimension. Let H & ++14 be class of binary classifiers on a domain X. A finite set (.1,...,, [m)) X is shattered by H. for every labeling (. ym) E {+1, there exists h such that h(z:) y; for all i. The VC-dimension VCdim(H) is the largest m such that some set of size is shattered (or oo if no such largest m exisls) 21
Semi-algebraic sets. set C R is called semi-algebraic it can be expressed as a finite Boolean combination of polynomial equalities and inequalities in the coordinates ; A family [Sa)ace with e RW is called semi-alge almi-algebraic if
(00,z) E θ R" x E So}
is semi-algebraic subset of R++n A standard closure result is the Tarski Serddb-Seidn theorem: the image (projection) of a semi-algebraic set under polynomial map is semi-algebraic (19) 5
We will use the following general bound on the VC-dimension of semi aini-algebraic families due to Goldberg and Jerrum (TO) (see also (I) Theorem 8.3) and (5) Theorem 7.38)).
Thcorem (Goldberg- JJrruu 110) Let F (Sa)Ree be family of subsets of RR" parometer- ized by θ C R.W Suppose there erist integers s Z 1 and d 2 1 and polynomials PL.....Pe e TR RRI Xi,,.... Xn) of degree at most d such that for all and x E R
I I So = (siin((p1(0.) x))
= true,
for some fixed Boolean formula Φ. Then there exists a universal constant > such that VCdim(F) CWW log(sd).
Complex-valued neural networks and modReLU. Let d 2 1 and L > 1 be integers. A fully connected feedforward complex-valued network (CVNN) of depth I, and input dimension d consists of:
layer widths no = d, n1, .... RL-1, ng = 1,
complex weight matrices ((0 C and complex biases b(0) The for l = 1,.... L,
a real modReLU bias parameter 8f0) E IR for each hidden unit (f.j) with l 1, I....,,
Given an input 200) Cd, the network computes recursively for t 1....,L L- 1:
(9) (t-1) + (() E CHe
(0)
mmoaR (u, 1 1 j j= 1,...,n8,
zj
and the (comple--valued) output
Fo(x) = ((1))(1-1) + bL() C,
where 0 denotes the collection of all trainable real paramoters (real and imaginary parts of all weights and biases, together with all a(0).. The total number of trainable real parameters is therefore
L
L-1
W = nene-1 +
ng
+
ne. t=1
8=1
We work with the modReLU activation introduced by Arjovsky al. 2 and later used in deep complex networks by Trabelsi et al. 20 (sce also (8). For 3 E I and 2 C, define
0,
0, |2| + 3 < 0,
mooa (z; =
0,
(1)
(|z + 3)
| 3 0,
4

---

Published in Transactions on Machine Learning Research (April/2026)
I.e.; mood (2; B) = ReI.U[[=] + B) 2 with the convention
at. 2
2 20).
Equivalently, writing
|z|
- re with T = |z| and 0 = a=)(=) (defined for r > 0), one has modR (2; () = for r = and moddR (3) (r + B)et on the active region fr > 0, r r r+83 0}.
Remark (value at 0 and relation to common definitions). Many papers present modReLU in the two-branch form (=; 3) = (121 + =)=/|=| if |2| B >> 0 and 0 otherwise, without separately specifying the value at 2 0 where z/|z| is undefined 2 20). Our definition
T agrees with this two-brance form for all 2 + 0; the only difference is that we explicitly set modR (0; 3) = to make the activation a total function (matching the usual "avoid division by zero" convention in implementations). For 8 > O, modReLU cannot be made continuous at the origin under any total definition, since the directional limit depends on =/|z|. This convention is used throughout, and reappears in our semi-algebraic encoding of the gate explicit "zero" branch; this contributes only O(1) additional atomic predicates per neuron and therefore does not affect the asymptotic description complexity the lower bound argument does not hinge on the value at 2 = O: we fix 8o < 0, for which the restriction to the real line is continuous at and the piecewise-liness linear structure used to invoke MT ! is unaffected by any choice of modR (0; Bo).
the resulting O(W2 log W) upper bound. Finally,
For binary classification we use the sign of the real part:
ho(x) = sign ((F(:)( E {+1,
(2)
Via the identification v 2d C4, we view hg as a classifier on Rddd by setting, for E R2d
ho( = sign((((Fo
(3)
Let HmodR denote the set of all classifiers of the form obtained by varying 0 R. for a fixed architecture (no....,,
3 VC-dimension upper bound
Proof strategy. We encode the forward pass of the network using auxiliary real variables for cach hidden unit (real/inaginary parts of pre-activations and post-activations, and radius variable enforcing r² = " uz). With these variables, each affine layer relation and the modReLU gate can be written as a Boolean combination of polynomial equalities and inequalities of constant degree. The resulting decision set {(0, 2) ( 2 0} is then the projection of a semi-algebraic set defined by a single cxistential quantifier block over the auxiliary variables. By Tarski Seidenberg and quantilative one-block quantifier elimination bounds, this projection admits quantifier- trant algi-algebraic description with controlled number and degrees of polynomials. We then apply the Goldberg Jerrum theorem to convert this description complexity into the stated VC-dimension upper bound.
Theorem (VC-dimension of modReLU networks) There erists universal constant C such that for every choice of layer widths (no...., letting W 2 2 denote the total number of trainable real parameters (including real/ pell/imggnary parts of all weights and biases and all modReLU bias parameters), the VC-dimension of Hoadd satisfies
TCdim((Medd < CW2 W.
In particular, for any fixed depth L, VCdim = O W) uniformly over architectures with W paramelers.
3.1 Semi-algebraic representation of the decision map
Fix an architecture (mo...., and write म E R2d for the real input and 0 E RW for the trainable parameters. Recall our sign convention sign(!) = +1 for t 2 0 and -1 for i < 0, so
ho hō +1
(VF 2 0.
5

---

Published in Transactions on Machine Learning Research (April/2026)
Auxiliary variables and constraints. We introduce auxiliary real variables encoding a forward pass. For each hidden layer f= 1,.,...; 1.
and unit j = =1,..... ,....,
ne, we introduce
(0) (9) u J 3 (pre-activation),
(P) (0) R 3,1 (post-activation).
r
(radius).
(We treat 2 1 (2) fixed by i.) Let Y denote the full collection of these auxiliary variables. Then
Y
ne-
Moreover, since ne-1 2 1 for all & and the parameter count includes the real and inaginary parts of all complex weights, we have
L
1-1
W 2 Σ n 2
2 nt:
1=1
and hence |Y| W,, ie., xy=0((1) with an absolute constant.
We impose the following constraints in the variables (0, Y). Each atomic predicate is polynomial equality or inequality of degree at most 2. The only non-alfine ingredient is the modReL.U nonlinearity: it is captured by introducing the radius variables r and enforcing three-branch gate deroo/incttive/atiiv/ including (8) case required by the standard convention modR (0; (20).
the "j
Compler affine maps. For each f = 1,..., I.
and j 1, ..... nig, enforce the real and imaginary
parts of
ne-1
00
Σ
W (t) (f-1) 5k 2
+ +D/
by two polynomial equalities. Written in real coordinates, these constraints are bilinear the param- eter variables (real/imagings parts of w:O jk: and 652) and the activation variables (real/ freal/inaginary
parts of 2k ) hence have degree 2.
modReLU gate (including the u u= 0 case). Fix a hidden unit (f,j) with bias parameter 800 E R (a component of 0). We first enforce the radius relation
3 10 0,
(r)0)²2 (u/ + (0)
(2) We then encode 2, modR (u) (0, 1))) (with the convention modR (0; 3) 0, cf. and 20 by the disjunction of the following polynomial conditions:
(zero) /:10 1 = 0,
Rj 0,
2 = 0;
(inactive) rj > 0,
(6)
rj (
(0)
s 0,
Zj = =0,
(1)
2j. = 0:
(6)
(active) "j 10 > 0,
rj 8 2 0,
(8)
j.8 (r), ((0)
(6) (0)
(0) j.
2/11 1
(00 10
-1,9 + 5/0 50
The "zero" branch essential: when u/ = (hence (0) = 0), modReLU outputs 0 even if 8/ > 0
by the standard convention in (2D). Introducing this branch ensures the existential encoding matches the actual network compulation for all .))))))))))
Output and decision. Write the output as Fx = W(T)) (1--1) + ((T) and enforce the decision event by the single polynomial inequality
((F((V 2 0,
again expressed in real coordinates (degree < 2 in (0, a, Y)).
The total number of atomic predicates across all layers 8p O(W), and the maximum degree is 8 = 2.

---

Published in Transactions on Machine Learning Research (April/2026)
From constraints to quantifier-free description. Define
= ((0,8) E IR w2d,; hg(2) = +1}.
Let CCR++24H1 be the set of all (0, v, Y) satisfying the constraints above. Then & semi-algebraic by definition, and
(0,8) = BY R such that (0, E
Hence G is the projection of the semi-algebraic set G. By the Tarski Seidenberg theorem (quantifier elim- ination for real closed fields), projections of semi-algebraic sets are semi-algebraic, and therefore G is itself
semi-algebraic 19 5).
Quantitative bounds for eliminating one existential block. The equivalence above exhibits G as the set defined by first-order formula with a single eristential quantifier block over the auxiliary variables Y. While Tarski Seidenberg guarantees existence of some quantifier-free semi-algebraic description of G, we also need explicit control of the description complexity (how many polynomials appear and what degrees they have), because this is what will enter the Goldberg Jerrum VC-dimension bound in Theorem [] Quantitative quantifier-elmmnatien
results provide such control for one-block formulas: starting from quantifier-free description of G using 8o input polynomials of degree at most 5, they bound the number and maximum degree d of the polynomials appearing in an equivalent quantifier-fre free description after eliminating the kı quantified variables, with a singly-exponential dependence on the total number of variables.
More concretely, quantitative quantifer-elimination bounds apply here because the defining formula for G has a single existential block, uses most su = =(W) imput polynomials of degree S 6= 2, and ranges over
kg = W + 2d free variables and k = YY| = (W) quantified variables.
particular, by 5 Theorem 14.16) (see also the discussion of singly-exponential bounds for one- block climination therein), there exist absolute constants C1, C2 0 and an equivalent quantifier-free formula defining G that involves at most
< (so (i(k+tk)))
polynomials of degree at most
d d (C2(kotk))
Since nt, = 1, any fully connected architecture satisfies W 2 2d + 2 (already for one has W 2d 2d 2), so kg + K1 OW) and log(sd) O(W log W).
Lemma 1 aSemi-algebraic decision map) There exist integers 8 2 1, Pi.....P. .Ps E EU Uw. UW,X1..... XI...., X2al of degree at most d such that for all 0 E R. and ă E Rdd
and polynomials
ho( = =1 = ((sign(pi sigul....iiu((p.(
true,
for a faxed Boolean formaula independent of 0, Furthermore, one may choose s, so that for absolute constonts co. e1 >
S (coW)aw and 2
In particular, log(sd) = O(W log W) uniformly over architectures with W paramelers.
Proof. By construction, & C W is semi-algebraic and is defined by quantifier-free formula that uses so = OWW polynomial (in (ineequliiies of degree at most = 2 (including the explicit "zero" branch for the modReeU gate, ensuring correctness when u. 0 and 8/00 0). The set G is the projection of G onto the (0, coordacsos,,,stes, hence is semi-algebraic by Parski-Seidenne
19 55.
Applying the quantitative one-block quantifier climination bound (5 Theorem 14.16) with ko = W + 2d free variables, h = | quantified variables, Su input polynomials, and degree ó = 2, we obtain an equiv- alent quantifier-free formula for G involving at most & < (1k6)C1((o+bk) polynomials of degree at most d (a(o
Finally, any quantifier-fre Boolean combination of atomic comparisons q(0, pd 0 with xI [<,5,=,2,>} be rewritten as Boolean formula in the values sign(1(0,5)) and sign(-q(0, under two-valued

---

Published in Transactions on Machine Learning Research (April/2026)
convention (c.g., 9 9>0 0 is equivalent to and not (q 0), and g 0 is equivalent to q 2 0 and -q 2 0). This transformation increases the number of polynomials by at most. factor of 2 and does not increase degrees, yielding the representation in terms of sign(p;) as stated.
Since W 2 2d + 2 and |Y] = O(W), we have ky + k = O(W) and So = O(),, hence s S you and S 2 W for absolute constants co, cj > 0, and therefore log(sd) O( log W).
3.2 Proof of the VC-dimension bound
For each 0 E Rw, let
S = { E E2d ha( +1}.
By Lemma there exist integers 8 2 1, d 2 1 and polynomials Pi.-...Pss E [R Uw. Xi...., Xzd] of degree at most d, together with a fixed Boolean formula ④, such that for all RW and 5 E Ikdd
T E Sp
((sign(p) (0, i)), sign(p, (0) true.
Thus the family {Sobegg is a semi-algebraie concept class of the form required by the Goldberg Joldberg-Jerrum theorem (10) (see also (I Theorem 8.3) and 55 Theorem 7.38)). Applying Theorem with parameter
dimension W yields
(Cdimm(WW..) = VCdim(((o)leew) I C' W log(sd),
for universal constant C>0.
It remains to bound log(sd) in terms of W. Lemma [ provides such bound uniformly over architectures: the quantifie-climination estimate used there depends the number of free variables ko W + 2d and quantified variables k [Y], but these are both O(W) for the present class. Indeed, since nr. = 1, even in
the shallow case I = we have
W 2m + 2m1 = 2d + 2,
and for L 2 2 the parameter count only increases. Hence for all architectures considered here,
W 2 2d 2
(4)
in particular 2d < W and ky W 2d < 2W. Together with |Y| O(W) (as shown in the construction of Lemma D. we obtain kn A = O(W), and Lemin] yields log(sd) = O(W log W) with absolute constants (via the quantitative one- block elimination bounds of 55 Theorem 14.16)).
Therefore,
VCdim(AAmod (7/moR < CW log(sd) S
C C log W
for universal constant C" > 0, completing the proof of Theorem
Comparison with classical real-network VC-dimension proofs. For deep real networks with piccewisc-lincar activations (c.g., ReLU), the nearly-tight @(W W) bounds are obtained by count ing activation sign patterns/ caarns//allinne affine regions layer-by-layer and controlling how many distinct dichotomies the network implement [1 4. For modReLU networks, when written in real coordinates troduces normalization by |a| 22 so the resulting map is not sense exploited by those region-counting arguments. Our proof instead proceeds by lifting the computation to polynomial constraint system (Section 3 Lemma D and then projecting out auxiliary variables using quantifier climination (19 5). The quantitative blow-up incurred by this climination step is reflected in the bound log(sd) O(W log W) and is precisely what introduces the additional factor of W in the upper bound 2 log W).
x + fy in- in (x, y) in the
Why the standard L log W) proofs for real networks do not apply as a black box after Cd ~ 2d2d The nearly-tight upper bounds of (M A are proved for networks whose activation is piecewise linear (and, in earlier work, more generally piecewise polynomial) with a constant number of pieces. A key step in these proofs that, once fixes the activation "gating" pattern (i.e., which linear piece each

---

Published in Transactions on Machine Learning Research (April/2026)
hidden unit operates on for given input), the network output restricted to that region becomes an cract polynomial expression of controlled degree in the underlying variables (equivalently: the model reduces to a composition of affine maps with fixed finite branch structure). This permits bounding the number of distinct sign patterns realized on a finite sample via classical sign-pattern bounds for polynomial families (e.g. Warren-lype inequalities), logether with a union bound over admissible gating patterns; see M for the implementation of this strategy in the piecewise-linear setting and its relationship to the piecewisc- polynomial case.
After identifying Cd ~ Rddd modReLL does not fall into this framework: on its active branch it contains the normalization term u/|u|, i.c., division by Vuz + uz in real coordinates, so the resulting real-coordinate map is not piecewise-polynone as required by the above gating- based arguments). Consequently, the polynomial sign-pattern machinery used to obtain O(WL L. log W) bounds cannot be invoked directly for modReL.U by a simple realification argument.
in the input variables (nor does it admit an exact finite "linear-region" description
One might ask whether this obstacle can be bypassed by approximating the realified modReLU map by piecewise polynomials. However, VC-dimension concerns exact dichotomies arbitrary finite sets, and points in shattered set may lie arbitrarily close to a decision boundary. Without an additional margin assumption, uniform function approximation does not guarantee preservation of the induced labels (i))( on such adversarial point sets. Moreover, any approximation scheme would typically require the number of pieces and/or polynomial degrees to grow with the target tolerance, and then the resulting VC-dimension bounds would depend on this growing description complexity rather than yielding a clean O(W L log W) bound at fixed W.
For these reasons, our upper bound instead proceeds by eract semi-algebraic lifting: we introduce auxiliary radius variables r with the polynomial constraint ,² = u so that the modReLU gate and the full forward pass admit a bounded-degree polynomial constraint system, and we then control the projection to (0, .) via one-block quantifier elimination before applying Goldberg Jerrum.
3.3 Lower bounds and comparison
The upper bound of Theorem 2 is obtained via a semi-algebraic encoding and is not expected to be tight. In the opposite direction, we obtain a lower bound by observing that HmodR contains, as a parameter-restrictrr subclass, standard real-valued depth-L networks with a fixed piecewise-lineal activation. The result below is therefore an inherited corollary of the nearly-tight VC-dimension lower bounds for real networks proved in
Proposition 1 (Lower bound (inherited from real networks)) There erists a universal constant e > such that the following holds. For all inlegers > and all sufficiently large compured to L, there exists an architecture of depth L with at most W trainable real parometers (counting real and imaginary parts of weights and biases, well as all modReLU bias parameters) for which
VCdim(Haaey 2 cWLLog( W )
In particular, for suitable depth-L architectures, the VC-dimension of modReLU complex networks grows at least on the order of W L Log((WLL).
Proof (via a real-valued subclass). Fix the non-degenerate constant 80 := -1 and consider the restric- tion of modReLU to the real line:
(x) = Mo (r + :0)))))
xr IR.
Since 3 < O, the activation is continuous at x = 0 on the real line, and the precise convention for mooRR (0; 3o) does not affect the piecewisc-lincar structure used in the lower-bound argument. By the definition ① and the convention modR (0; (b) = 0 (as in (2) 20)), 63, is piccewise-linear on with constant number of linear pieces (indeed, at most three). Hence the real-network lower bounds for fixed piecewise-linear activations
9

---

Published in Transactions on Machine Learning Research (April/2026)
apply: by [I] 4) there exists universal constant co 0 such that for all L and all P sufficiently large compared to 7,, there exists depth-T, real network class HP (0p)) with at most P trainable real parameters and activation ds. satisfying
VCdim(MPP1(0s.)) 2 co PL Pog
(5)
We now embed such a real network as a subclass of our complex modReLU networks. Consider the complex- valued architecture with the same layer widths and impose the restrictions:
inputs are restricted to Rd C Cd (identified with x + :0),
all complex weights and biases are constrained be real (imaginary parts fixed 0),
all modReLU bias parameters are fixed to the constant value Bo (i.c., 8 = So for all hidden units).
Under these restrictions, the complex network computes exactly the same real-valued function on Rd as the corresponding real network with activation 6%., and the induced classifier ++ sign (R( Fo (+))) coincides with the real-network classifier sign(f(z)) on inputs x Rd.
Let P denote the number of free real parameters (weights and biases) in the embedded real network. Consider the corresponding complex architecture (same widths) used to realize this subclass. In the ambient count W for complex modReLU networks we include: (i) both real and imaginary parts of all complex weights and biases, and (ii) all modReLU bias parameters. Under the restriction "imaginary parts 0" and "B(0 Bo", the number of free parameters is preciscly the number of real weights and biases, namcly P. Since each such parameter corresponds to complex weight/ bias coordinate that contributes two real degrees of freedom in the ambient parameterization, we have
P P W
(6)
(Indoed, for this fixed architecture the ambient parameter count can be written as W 2P + P3, where P/ = E L-1 counts the modReLU bias parameters; in particular W 2 2P.)
Consequently, HWL contains a subclass with VC-dimension at least that of HPL.(ds))) and by 5 we
obtain
VCdim(H 2 VCdi 2 co PL I
Finally, choose architecture whose total parameter count is at most W and for which the embedded real subclass has P on the order of W to constants. Concretely, take any depth-L fully connected real architecture achieving (5) with P = W/33 trainable parameters. For the corresponding complex archilecture (same widths), the ambient parameter count satisfies Warch 2P + Pp, where P3 = =
LL-1 ne counts the
modReLU bias parameters. Choosing the widths so that P3 S P (which is compatible with standard constructions used to realize
5 we obtain Warch I 3P S W. Substituting P = [W/3] gives
W 3
W/3 L
VCdim
L log
2 cWL log
for (possibly smaller) universal constant the proposition.
0, provided W is sufficiently large compared to L. This proves
Combining Proposition I with Theorem 2 we obtain for suitable depth-L architectures and large W:
W
cLL
S
VCdim "Cdim(Htwod S W log W.
Thus the VC-dimension grows at least lincarly both W and L, and at most quadratically W up to a logarithmic factor. Narrowing this gap-fot for instance by sharpening the upper bound towards the W L log W behavior known for real piecewise-linear networks
is left. open problem.
10

---

Published in Transactions on Machine Learning Research (April/2026)
4 Discussion and related work
We have shown that the VC-dimension of fully connected complex-valud networks with modReL activation and W trainable real parameters is at most on the order of W log W, uniformly over architectures of a given size. The proof has two main ingredients: (i) after introducing auxiliary variables for complex magnitudes, the network computation and the decision event ( (ā)) 2 0 admit an existential semi-algebraic description, and (ii) semi-algebraic concept classes with bounded description complexity have VC-dimension bounded by O( log(sd)) via the Goldberg- Geldberg-Jerrum
Jerrum theorem (TO) (see also (I). Quantitative bounds for one- block theorem guarantees that the projection remains semi-algebraic (9)), yielding the stated O(W log W) upper bound.
quantifier elimination (5) then control log(sd) in terms of W, while the
Special cases (shallow and linear models). It is instructive to consider the extreme shallow case L = 1, where the network reduces to a single complex affine functional with sign output,
(+) = sign (w,, V (x)) + b)). W W C², beC.
Under the identification Cd Rdd the map ā + R( (a)) + b) is a real affine functional on Rdd, and therefore Hi is a class of halfspaces in R2dd In particular, its VC-dimension is 2d + 1, which is linear in the ambicnt paramcter count W = 2d 2 (I 21). More generally, if all activations are linear (so the network is globally affine in the input), then regardless of depth the induced classifier is again a halfspace in IR2d and the VC-dimension is linear in the effective input dimension (and hence linear in W for fully connected architectures).
Relation to nearly-tight bounds for real networks. For real-valued networks, sharp VC-dimension and pseudo-dimension bounds are known for broad classes of piecewise linear architectures: in particular, the nearly-tight @(W log W) behavior for depth-L networks with W paramcters established in (IT 4 Our
lower bound is inherited by embedding such real networks as rarameeer-resttrileed subclass of mU complex networks (Section 3 Proposition []_ In contrast, our upper bound is not black-box consequence of [) The upper-bound techniques in (IIl 4 rely the fact that, with piecewise-linear (more generally, piecevise-polynomia) activations having a constant number of pieces, the network computes a piecewise- polynomial function of the input on a partition induced by activation gates; this enables a layer-by-lay counting of regions/ /sign patterns without invoking general projection or quantifier-eliminaioo machinery. After identifying Cd = R2d modReLU does not fit into this framework: writing = = x+ and = + the active branch contains the normalization 2/|=| (x + iy)/r and hence factors of 1/ 4/v + so the resulting real-corrdinate map is not piecewise-polynoniss in (z.v) y) in the sense required by these argunents. For this reason, the existing @(W log W) proofs for piecewise-linee linear networks cannot be applied directly to obtain comparable upper bounds for modReLU complex networks. Our approach instcad procoods by listing the computation to an existential system of polynomial constraints (introducing auxiliary variables r with ,² _²² + )²), and then projecting out these auxiliary variables using Tarski-Seidennn Seidenberg/quanin /quantifier elimination 19 (5). Combined with the Goldberg Jerrum bound for semi-algebraic concept classes (10) this yields our 2 log W) VC-dimension upper bound.
Can complex networks exceed real-valued capacity? A complex- network induces a real-valued classifier on Iddd via the identification Cd ~ R2dd and each complex affine map u = W= W=+b b with W = A iB -B acting on (R2, 3z). Thus, for
can be written as a real affine map with the structured block matrix [4 A a fixed real parameter budget W, the modReLU hypothesis class considered here is (after identification) a subclass of real networks with W free real parameters but additional algebraic constraints (weight-tying induced by complex arithmetic). In this sense, when capacity is measured as function of W, complex networks cannot have larger VC-dimension than unconstrained real network family of comparable size; any advantage of complex representations is better viewed as parameter-efficieng) or inductive bias rather than strictly larger worst-case combinatorial capacity. Although the decision uses R FF))), the imaginary part still affects hidden-layer activations and can change R(Fe), so this does not reduce the model to a purely real network. Finally, the same semi-algebraic lifting applics to other real decision statistics of complex output (c.g., (ign(S(F))), thresholding |Fel, or phase regions), and a systematic comparison of such variants to classical real architectures remains an open direction.
11

---

Published in Transactions on Machine Learning Research (April/2026)
Why sharpening the upper bound is technically difficult. The gap between our O log W) upper bound and the O(WL. W) behavior known for real piecewise-linear networks arises from the use of generic projection/ qquatiffer-eliminnee
bounds. For ReLU-type activations, one can analyze the network layer-by-ayee and count the number of activation sign patterns (or affine regions) induced by hyperplane arrangements, leading to sharp control of the shatter function and VC-dimension [ 4. For modReLUU the normalization =/|z| introduces algebracc structure (involving vx² + y²) that obstructs a direct reduction to counting finitely many affine regions in the (z. y)plane. Our proof repairs this by lifting to an existential semi-algebraic description using auxiliary radius variables and then projecting them out using quantifier elimination (Tarski Seidenberg) [9 5). Quantitative elimination is necessarily worst-case and can introduce blow-up in the number and degrees of polynomials describing the projected set; in our argument this manifests the bound log(sd) O( log W) (Lemma D which, when combined with Goldberg- Jerrum (10), yields the additional factor of W in O(W2 log W). Improving the upper bound towards O(W L log W) would therefore require bypassing generic quantifier elimination and exploiting finer compositional structure of modReLU and complex multiplication to control the number of distinct dichotomies more directly.
Consequences of bounded VC-dimension. A bound on VCdim controls classical combinato- rial quantities such as the growth function (shatter coefficient), via Sauer-Shelal) type inequalities (21 D. It also yields standard distribution-free sample-complexity guarantees for uniform convergence and ERM- style learning: informally, achieving small generalization error requires a number of samples scaling on the order of VCdimmHHwyy up to logarithmic factors (2I [ (2). While such worst-case guarantees are typi- cally loose for modern overparameterized training, they provide principled capacity bascline for comparing complex-valued architectures to their real-valued counterparts.
Outlook. A natural open problem is to sharpen the O(W2 log W) upper bound towards the O(W L log W) behavior known for real piecewise-linear networks [II E. potentially by avoiding generic quantifier- elimination bounds and instead exploiting finer structure of modReI.U and complex multiplication. Another dircction to extend the semi-algebraic approach to other complex activations beyond modReL,, and to other architectures such as convolutional, recurrent, or attention-based complex-valued models, where the interaction of weight sharing, complex arithmetic, and activation structure may lead to different capacity scalings. Finally, it would be interesting to compare VC-type bounds to norm-based generalization analyses for CVNNs, such as spectral-complexity bounds (7) and to study pseudo-dimension for complex-vluued regression settings 1 22).
Limitations. Our analysis is restricted to fully connected feedforward architectures with modReLU acti- vation, and we do not track constants or lower-order terms in the VC-dimension bounds. The semi algebracc encoding relies on quantifier climination 55 19), which is computationally heavy; here it is used purely as a theoretical tool. The resulting O(W2 log W) upper bound is likely not optimal, as suggested by the nearly- tight O(L log W) bounds for real piecewise-linear networks [ g.. We also do not address data-dependent or norm-based complexity measures for complex-valued networks, nor do we consider convolutional, recur- rent, or attention-based architectures.
Novelty and practical relevance. We emphasize that the principal novelty of this work is methodolog- ical rather than a direct application of known results: while the Goldberg Jerrum theorem and quantifier- elimination machinery are standard tools, the challenge lies in showing that modReLU networks- whose real-coordinate representation not picceise-polynomill-adee admit a semi-algebraic encoding with descrip- tion complexity controlled purely in terms of the parameter count W. This encoding step is specific to the algebraic structure of modReLU (and, more broadly, to activations involving |a|) and does not follow from any black-box reduction to existing real-network VC-dimension theory. From practical standpoint, the result- ing bounds provide the first principled capacity bascline for modReLU networks: they give distribution-fie sample-complextty guarantees via standard VC-theory (2I-I) and enable direct comparison of the combi- natorial complexity of complex-valued architectures against their real-valued counterparts, complementing the norm-basod generalization analyses of 77 While worst-case VC-dimension bounds are known to be loose for modern overparameterized regimes, they remain the standard combinatorial notion of capacity in learning theory and serve as necessary theoretical foundation for the calplex-valued setting.
12

---

Published in Transactions on Machine Learning Research (April/202)
Reproducibility Statement
This is a theoretical paper. All claims are stated as formal theorems, lemmas, or propositions, with proofs provided the main lext or as proof sketches that rely on standard results from real algebraic geomelry [9] and statistical learning theory [ No datasets, code, hyperparameters were used.
Broader Impact Statement. This work is purely cheoretical and studies the combinatorial capacity of class of complex-valued neural networks. We do not anticipate direct negative societal impacts beyond those already associated with general advances in machine learning thcory. Any downstream impact will arise only through applications that use complex-valued networks; in those settings, standard considerations around fairness, robustness, and potential misuse models still apply.
References
[1] M. Anthony and P. L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge Uni- versity Press, 1999.
[2] M. Arjovsky, A. Shah, and Y. Bengio. Unitary evolution recurrent neural networks. In Proceedings of the 33rd International Conference on Machine Learning (ICML), 2016.
[3] P. L. Bartlett, D. J. Foster, and M. Telgarsky. Spectraaly-norrmalizee margin bounds for neural networks. In Advances in Neural Information Processing Systems 30, pages 1240-6249 Curran Associates, Inc., 2017.
[4] P. L. Bartlett, N. Harvey, C. Liaw, and A. Mchrabian. Nearly-tight VC-dimension and pscudodimension bounds for deep neural networks. Journal of Machine Learning Research, 20(63):1-17, 2019.
[5] S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Springer, 2nd edition, 2006.
[6] E. B. Baum and D. Haussler. What size net gives valid generalization? Newral Compulation, 1(1):151 160, 1989.
[7] H. Chen, F. He, S. Lei, and D. Tao. Spectral complexity-scaled generalisation bound of complex-valued neural networks. Artificial Intelligence, 322:103951, 2023.
[8] P. Geuchen and F. Voigtlaender. Optimal approximation using complex- valued neural networks. Advances in Neural Information Processing Systems 96, 2023.
[9] P. Geuchen, T. Jahn, and H. Matt. Universal approximation with complex-valued deep narrow neural networks. Constructive Approzimation, 62:361-402, 2025.
[10] P. W. Goldberg and M. R. Jerrum. Bounding the VC-dimension of concept classes parameterized by real numbers. Machine Learning, 18(2-30 3):133-148, 1995.
[11] N. Harvey, C. Liaw, and A. Mehrabian. Nearly-tight VC-dimension bounds for piecewise linear neural networks. In Proceedings of the Conference on Learning Theory, volume of Proceedings of Machine Learning Research, pages 1064 1068. PMLR, 2017.
[12] A. Hirose. voluee neural networks for signal processing. In S. Haykin and B. Kosko, editors, Intelligent Signal Processing, pages 471-509, Wiley-IEEE Press, 2003.
[13] A. Hirosc. Complez- Valued Neural Networks. Springer, 2nd edition, 2012.
[14] T. Kim and T. Adah. Approximation by fully complex multilayer perceptrons. Neural Computation. 15(7):1641 16616411666,,,,-1111111111111161 2003.
[15] Bassey, Qian, and X. Li. survey of complex-valued neural networks. IEEE Access, 9:9786-9799 2021.
13

---

Published in Transactions on Machine Learning Research (April/2026)
[16] S. Scardapane, S. Van Vaerenbergh, A. Hussain, and A. Uncini. Complex-valued neural networks with non-parametric activation functions. IEEE Transactions on Emerying Topics in Compulational Intelligence, 4(2):140 150, 2020.
[77] J. W. Smith. Complex-valued neural networks for data-driven signal processing and signal understand- ing. arXiv preprint arXiv:2309.07943 2023.
[18] E. D. Sontag. VC dimension neural networks. In M. A. Arbib, editor, The Handbook of Brain Theory and Neural Networks, pages 1188-1192, MIT Press, 2nd edition, 2003.
[19] A. Tarski. A Decision Method for Elementary Algebra and Geometry. University of California Press, 1951.
[20] C. Trabelsi, O. Bilaniuk, Y. Zhang, D. Serdyuk, S. Subramanian, J. F. Santos, S. Mchri, N. Ros- lamzadeh, Y. Bengio, and C. J. Pal. Deep complex networks. In International Conference on Learning Representations, 2018.
[1] V. N. Vapnik. Statistical Leorning Theory. Wiley, 1998.
[2] M. J. Wainwright. High- Dimensional Stalistics: Aom-poymii Viewpoint. Cambridge University Press, 2019.
14


Reviews:
[{"review_id": "sNkRtun5Mr", "reviewer": "Reviewer_iptt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proves bounds on the VC dimension of complex feed-forward networks with modReLU activation functions by treating the real and imaginary part of each complex weight as a two distinct real-valued weights. Specifically, an upper bound of order $O(W^2 \\log(W))$ and a lower bound of order $W L \\log(W/L)$ is derived. The upper bound is proven by expressing the decision regions of the network in terms of a boolean combination of polynomial and a Theorem by Goldberg & Jerrum.\nThe lower bound is proven by showing that each such class of complex networks contains a class of real-valued networks, and therefore matches the VC dimension bound for piecewise linear networks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "I am writing the review earlier as planned (deadline communicated to me was Feb 25th) because the discussion phase has already started. Therefore, I did not assess the submission as thoroughly as I intended to.\n\nThe central claims of this paper are formulated as theorems which come with mathematical proofs. Overall, the proofs appear sound, but could be improved in terms of clarity. The upper bound is likely not tight, but this irrelevant to the acceptance criteria.\n\nSpecific comments\n- The definition of the modReLU function appears odd and differs from the literature, e.g. (Arjovski ICML 2016, Trabelski ICLR 2018) as it contains the additional case $\\sigma(z) = 0$ if $z=0$. This makes the activation function discontinuous at $0$ for bias $\\beta >0$. \n- While the above is seemingly a minor modification to the definition of the modReLU, it reappears in the proof itself as an additional branch, and therefore in the produced upper bound.\n- At the start of the lower bound, the paper states that the convention $\\sigma(0)=0$ is necessary, so changes to the definition might affect the validity of the lower bound. I don't see why the convention would be necessary though.", "audience_yn": "Yes", "audience_explanation": "The presented results are of interest to both, the learning theory community and people working with and on  complex-valued networks.", "requested_changes": "- Currently, the introduction makes the impression, that modReLU activations are the only activation functions that are used for CVNNs. I request a short discussion of different activation functions that are commonly used (see for example (Scardapane et al., Complex-valued Neural Networks with Non-parametric Activation Functions, 2020), including potential VC dimension bounds. On first sight, it seems that e.g. cReLU can be handled more easily as it avoids the problematic $|z|$ term. \n\n- Add a paragraph to the beginning of section 3, that explains the proof strategy (the role and meaning of auxiliary variables, constraints, quantifier elimination bounds, existential blocks)\n\n- Expand the \"from constraints to quantifier-free description\" section by adding more explanation of the results from the literature applied therein.\n\n- If the proofs rely on the different definition of the modReLU function compared to the literature, this needs to be communicated openly.", "broader_impact_concerns": "None", "additional_comments": "The statement \"modReLU activation introduced by Trabelski et al.\" is false, as Trabelski et al. credit Arjovski et al. for it.", "extra_scores": {}, "extra_text": {}}, {"review_id": "fVrK86Nhei", "reviewer": "Reviewer_1meA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper the authors study the VC-dimension of fully connected complex-valued  deep neural networks. they show that the VC-dimension of these networks is qudratic in the network parameters as a upper bound and linear in the number of parameters and depth of the network. . The networks are specific to modReLU activation functions and real valued outputs. \n\nThe main disadvantages of the proposed method is tha the bound of $W^2\\log W$ is relatively large. This is because as of now there is no proof that modReLU networks have the combinatorial growth demonstrated and assumed in the paper. In addition the quadratic bound could potentially arise from the semi-algebraic class complexity and thus does not reflect the actual property of the complex CNNs. In addition as the bound is based on the real output it bypasses complex-specific insights and thus avoids to answer the question about whether complex networks are more or less expressive than classical networks. .", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper introduces the use of Tarski-Seidenberg quantifier elimination and the Goldberg-Jerrum VC bound for semi-algebraic concept classes. As such the methodology allows to estimate the VC-dimension of such class.", "audience_yn": "Yes", "audience_explanation": "The paper positions itself as filling the gap in the approximation theory for CNNs and provides a solution by using the Norm-based generalization bounds. In addition while the network does not dive deep into the complex based analysis it provides a solid clean lower bound embedding of real networks. In addition the authors explixitely dioscuss the ReLU fail in region-counting.", "requested_changes": "It would be interesting to have a discussion on whether or not complex networks can exceed real-valued capacity.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YVxbTVvRLh", "reviewer": "Reviewer_MX6D", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the setting with complex-valued neural networks with modReLU activations, and provides an upper bound on the VC-dimension of the neural network family this class parameterizes. Additionally, they complement this with lower bounds.", "claims_and_evidence_yn": "No", "claims_explanation": "- Abstract: Is realification an actual word? in the abstract, “usual realification” can be made more concrete by saying isomorphism between $\\mathbb{C}$ and $\\mathbb{R}^2$.\n- Preliminaries: Semi-algebraic sets and VC-dimension mentioned in paragraph, but VC-dimension is never introduced. This should be introduced (for self-containedness of the paper)\n- Theorem 1 is missing a citation from Goldberg-Jerrum.\n- The same/next page call on the Tarski-Seidenberg theorem without introduction or citation.\n- For readers not familiar with the area, it would be good to include a notation paragraph in the preliminaries section\n- The idea in the proof of Lemma 1 can be simplified a lot (just define a constraint satisfaction program and count the constraints via a reduction to Bartlett et al and Harvey, Liaw, and Mehrabian)\n- The proof in proposition 1 just follows a reduction to Harvey, Liaw, and Mehrabian, essentially. \n- I belive the full result follows easily by applying the isomorphism between $\\mathbb{C}$ and $\\mathbb{R}^2$ and invoking Bartlett et al (since that result makes no assumptions about what the activations are) and derives the same bound on the VC-dimensions/Pollard Pseudodimension\n- Are there interesting structural results that can be provided? For instance, in combinatorics, having bounded VC-dimension helps bound shatter functions, and helps do faster matrix-vector operations. Can you say anything about these properties (wrt some interpretability or inference property) in this system?", "audience_yn": "No", "audience_explanation": "Please see comments above.", "requested_changes": "Please see comments above.", "broader_impact_concerns": "None", "additional_comments": "I believe the full result should follow by applying the isomorphism between $\\mathbb{C}$ and $\\mathbb{R}^2$ and invoking Bartlett et al (since that result makes no assumptions about what the activations are) and derives the same bound on the VC-dimensions/Pollard Pseudodimension.", "extra_scores": {}, "extra_text": {}}, {"review_id": "l0tmA3GBj7", "reviewer": "Reviewer_Fo9U", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents upper and lower bounds on the VC dimension of complex-valued multi-layer perceptrons. The upper bound scales quadratically with the number of parameters, while the lower bound scales linearly with the number of parameters.", "claims_and_evidence_yn": "Yes", "claims_explanation": "I am unfortunately not familiar with the majority of the tools in this paper and therefore cannot voucher for correctness of the proof. I am familiar with the general concept of VC dimension and believe the conclusions make sense.", "audience_yn": "Yes", "audience_explanation": "Both VC dimension/generalizability and complex-valued neural networks are of interest to machine learning researchers.", "requested_changes": "There is an apparent gap on the dependency of W in this paper. While the authors acknowledge this limitation, I do wish more discussion could be incorporated in the paper.\n\n1. For real-valued neural networks, can the upper bound be sharpened to tilde O(W)? Is this known?\n\n2. Are there any special cases (e.g. NNs with fewer number of layers) in which the upper and lower bounds could be matched? In the extreme case if we have a complex linear regression (or complex logistic regression), is the VC dimension linear in W? What if it is a one-layer network? What if it is a network with linear activations?\n\n3. Can the authors explain why sharpening either the upper and lower bound is technically difficult? It may be an open question, but readers will want to know *why* it is open, what is hard about this problem, and why existing approaches can't work. These discussions, though they do not establish new results and may not even be rigorous, offer great insights that would be helpful for future research.\n\nIn a similar vein, it would be beneficial to explain how the proof in this paper is different from existing proofs or classical ones establishing VC dimension bounds for shallow classifiers and MLPs with real values, which I'm certain there are many.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)