Benefits of Max Pooling in Neural Networks: Theoretical and Experimental Evidence
Authors: Kyle Matoba
Nikolaos Dimitriadis
François Fleuret
Venue: Accepted by TMLR ()

Abstract: When deep neural networks became state of the art image classifiers, numerous max pooling operations were an important component of the architecture. However, modern computer vision networks typically have few, if any, max pooling operations. To understand whether this trend is justified, we develop a mathematical framework analyzing ReLU based approximations of max pooling, and prove a sense in which max pooling cannot be replicated. We formulate and analyze a novel class of optimal approximations, and find that the residual can be made exponentially small in the kernel size, but only with an exponentially wide approximation.

This work gives a theoretical basis for understanding the reduced use of max pooling in newer architectures. It also enables us to establish an empirical observation about natural images: since max pooling does not seem necessary, the inputs on which max pooling is distinct – those with a large difference between the max and other values – are not prevalent.

Published in Transactions on Machine Learning Research (09/2023)
Benefits of Max Pooling in Neural Networks: Theoretical and Experimental Evidence
Kyle Matoba
Machine Learning Group, Idiap
Computer Science Departmend, École polytechniqqee fédérate de Lousanne
Nikolaos Dimitriadis
Computer Science Deparbmend, École pokgtechnique fédérale de Lousanne
François Fleuret.
froncois. Sterreetngeuurettuii......
Computer Science Department, University of Geneva
Machine Learning Group, Idiap
Computer Science Department, École polytechnique fédérale de Lausanne
Reviewed on OpenReview: https: /ttps://opents: //wp://veeee.e......m forun????? id- YgeXgrif7gA
Abstract
When deep neural networks became state of the art image classifiers, numerous max pooling operations were an important component of the architecture. However, modern computer vision networks typically have few, any, max pooling operations. To understand whether this trend is justified, we develop a mathematical framework analyzing ReLU based approx- imations of max pooling, and prove a sense in which max pooling cannot be replicated. We formulate and analyze a novel class of optimal approximations, and find that the residual can be made exponentially small in the kernel size, but only with exponentially wide approximation.
This work gives theoretical basis for understanding the reduced use of max pooling in newer architectures. It also enables us to establish an empirical observation about natural images: since max pooling does not seem necessary, the inputs on which max pooling is distinct those with a large difference between the max and other values are not prevalent.
1 Introduction
When convolutional neural networks first became state of the art image classifiers in the early 2010s, max pooling featured prominently. For example, in VGG (Simonyan & Zisserman (2015) and AlexNet (Krizhevsky et al. (2017)). Largely coincident with this period, however, (Springenberg et al. (0015) argued that max pooling operations were not necessary because strided convolutions composed with nonlincarity is simpler and more flexible. And subsequent architectures in such direction - ResNets (He et al. (0016)
have a single max pooling layer, and some - such as InceptionV33 (Szegedy et al. (2016)) and mobilenet V3 (Howard et al. (2019) have none at all H Max pooling is mostly omitted in the attention baaedd image clas- sifiers that began be used in the early 2020s, such the Vision Transformer (Dosovitskly et al. (2021)) Examining whether max pooling
truly be dropped from the toolbox of neural network image classifiers is worthwhile because would case architecture design and reduce development burden
This paper examines whether max pooling is remnant of an earlier era when image classifiers were motivated by the visual cortex. We find for some inputs, max pooling constructs very different features than an optimal
1 All statements about historical models refer their implementation Torchvision Marcel & Rodrigucz 2010 described at httpp:/ :tppto//pytorcc.... atg/vision/stabl secable/oodel.... html
extremely specialized ixed hardware, it common for primitive operations reimplemented several times for different computational "backends".
Foor example,

---

Published in Transactions on Machine Learning Research (09/2023)
approximation by ReLUs, thus it expresses different inductive bias and can sometimes be appropriate. We derive comprehensive bounds on the error realized by approximaling max functions with the composition of ReLU and linear operations, and find that a simple divide and conquer algorithm cannot be improved upon. Hence, accurate approximations must be computationally complex.
Our result does not imply that omitting max pooling from image classifiers is wrong. Rather, it says when it could be wrong. Max pooling will be strictly more expressive than ReL approximation on inputs with a large difference between the maximum and other values within pools.
Our contributions are (1) introducing a novel generalization of max pooling (Scction 4/, (2) proving that the
max function cannot be represented by simpler elements of this function class (Theorem 4) (3) analyzing
experimentally the size and quality of approximations (Section 5). (4) formulating a notion of separation for max pooling (Theorem Theorem 2), and (5) connecting mathematically the average of subpool maximums
with order statistics [Thorrm 3).
2 Background and Related work
Early work examined the neurological antecedents of (artificial) neural networks, and experiments with mammal's eyes and brains have shown max pooling to be a biologically plausible operation (Fukushimal (1980 Riesenhuber & Poggio (1999)). And practice has followed this observation, with max pooling being important when deep neural networks first began achieving competitive performance. For example, AlexNet Krizhevsky et al. (2017) dominated the ImageNet Large Scale Visual Recognition Challenge (ILSVRC) 2012 Russakovsky et al. (2015)), and had max pooling in more than half of its "blocks However, the ILSVRC 2017 leaderboard was dominated by Resnets, for which max pooling is not central. Similarly with DawnBench (Coleman ct al. (2018) ) where a more transparent source code distribution model makes it simple to verify that many models feature only a single max pooling layer. This move away from max pooling was consistent with an influential study arguing that strided convolution composed with nonlinearity is preferable max pooling because it can fit a max pooling mapping if appropriate, and can seamlessly fit another functional form if not (Springenberg et al. (2015)).
We examine this assertion by questioning whether (1) max pooling can be simplified to ReLU nonlinear- ity, and if not, (2) what pattern in the data would make max pooling and ReLU comparably expressive empirically.
Our work is preceded by a literature examining the expressiveness of piecewise lincar networks in terms of bounds on the number of linear regions they express, for example Montúfar et al. (2014), Serra et al. (2018), Hanin& & Rolnick (2019), and Montáfar et al. (2022). Several of these studies examine the maxout activation function (Goodfellow et al. (2013)), which is essentially equivalent to our mathematical model of max pooling. Maxout networks generally express many more lincar regions than equally-sized networks using ReLU activations.
Compared to these studies, we assess the increased expressivity of max pooling (or maxout) networks as the error inherent to approximating a single max pooling operation with ReLUs. This makes our analysis more direct and practically interpretable. Though, because it may be that the outputs of network using max pooling is efficiently approximated, even though an individual neuron could not, our conclusions may also need a bit more thought when transposed to architecture design. Our more narrow assumptions in turn suggest a potentially fruitful direction of inquiry into maxout activations: eschew general maxout assumptions for more restrictive architectures consistent with max-pooling (e.g. that the output is stricly smaller than the input, inputs are grouped into disjont "pools", etc.). These stronger assumptions may be the missing link since maxout, although more general, never gained much traction (it is not implemented natively in PyTorch, for example, and practically never seen in the wild).
Like most related work, work casily extends to many other (clementwise) piecewisc lincar activations such as hard tanh- = + ReLUUx+1) ReLU(x= ( ((Colloberl, 2004)), leaky ReL.U = + ReLUUz))
TTe leaderboard is here: "SuperVision" team.
http:///mmmeennnncc////////////e AlexNet, is a product of the
2

---

Published in Transactions on Machine Learning Research (09/2023)
Result [log2 d
Depth
Function Class
small width
exact trivial Theorem 2
1
width f oo
approximation possible (Hornik 1991
Cybenko 1989
Πoga d]
width f oo MR(R)
exact impossible on Rd Herrtiih ct al. 2021
logg d]
exact impossible on [0, 1 Theorem
[lgg2 d]
width 00
approximation experimentaly difficult [0, 1]d Section 5)
Table 1: taxonomy of approximations the max function by is the function class introduced in [Section 4 The quality of the approximation depends crucially on depth, and far we are aware, this is the first paper to examine the finite width case.
blocks in dimensions. Ma(R)
.01 x ReLU(-x)) ( MMaas et al. 2013 ReLU6
ReLUU- 6) (Krizhevsky 2012) ) and
hard sigmoid x (ReLU(z + 3) ReLU(x 3))/6 (Coorbbriiuux et al. 2015 and does not apply to many other sources of nonlinearity, such as tanh. However, there are standard techniques for extending work on piecewise linear activations to general activations based on bounding the difference to a piecewise linear approximation, such as Zhang et al. (2018).
Attention mappings do not fit. within the scope of our analysis, being neither piecewise linear, nor simply approximated by a piecewise linear mapping. Nonetheless, we see that the recent move towards of fewer max pooling layers has been continued in the emergence of transformer-based image classifiers. The Vision Transformer (Dosovitskiy et al. (2021)). ) for example, uses no max pooling layers.
Hertrich et al. 2021 is closely related to the theoretical component of our work. This study addresses aspects of ReLUUbbased approximations to the max function, and proves a technical sense in which max pooling is more expressive than ReLUs, However, their proof technique relies crucially upon the discontinuity at zero, a dynamic not shared by our analysis, which is restricted to nonnegative inputs. We give precise error bounds, and are able to compare the errors of a large parameterized family of approximations with considerable precision to offer more precise grasp of the practical tradeoff that applied approximations entail. (Table 1 summarizes several results on the approximation of the maximum function by linear- blocks.
Boureau et al. (2010) is an early work comparing average and max pooling from an average-cass statistical perspective. They also identify the input dimensionality as a key factor in complexity. In their framework, sparse or low-probability features correspond to the corners of the input domain in our analysis.
Grüning & Barth (022) find that mén pooling can also be a useful pooling method, finding that supports and is rationalized by analysis in terms of the quantiles of the input to the pooling method. Fssentially, if the true data is strongly determined by the nonlinear behavior of quantiles, then ReLU-based approaches are relatively disadvantaged.
3 The complexity of max pooling operations
In this section, we prove that in simplified model, max pooling requires depth multiple layers of ReLU nonlinearity are necessary to effect the same computation, and more layers are needed for larger kernel sizes.
3.1 Simplifications
In the design of deep learning architectures, max pooling reduces dimensionality by summarizing the values of spatially nearby inputs. To simplify, we examine the approxination of max function, putting aside shooling"-specifi considerations like stride, padding, and dilation which that are ultimately lincar pre-and post-processing. We summarize the size of the input using the term "order" so that, for example, the maximum over a 3 x 3 input is an order 9 max function. In this sense, our abstract model of max pooling is akin to the marout activation from Goodfellow et al. (2013). We treat as a general lincar function any operator that is linear at inference time, such as batch normalization, convolution, reindexing, or average pooling. Finally, we discuss only ReLU nonlinearities.
3

---

Published in Transactions on Machine Learning Research (09/2023)
Such DNNs, say f, can be written
/= (x War by) ReLU o... ReLU o (x H> Wox + bp)
(1)
where W,, b = 0, 1....,k & are the weights and biases of the linear layers, and k is the depth. For brevity, we call these functions feedforward net works and leave all the other qualifiers implicit. Feedforward networks are convenient and pedagogically tidy because they concisely reduce all aspects of the architecture to just the number of layers and their widths.
3.2 Max pooling as feature-builder
Telgarsky (0166) showed that deep neural networks cannot be concisely simulated by shallow networks. Their approach is to demonstrate a classification problem that is easy for deep networks, but is provably difficult for shallow networks. We do similarly by building a test problem on which max pooling succeeds and ReLU fails. First, we investigate the appropriate metric for comparison. [hhorem shoows that for any dimensionality, a narrow feedforward network with a single source of nonlinearity can emit the same output as max pooling. Thus, prediction accuracy is not the correct metric by which compare nonlincaritics.
Theorem 1. There exists a feedforword network f IRd + R with hidden neurons such that for all & E R, f(x - -) < > max(21..... xa}= S g.
Proof.
max( xa) S <>
S and and S + ReLU -) 0.
Max pooling is used in the construction of intermediate layer features, and not directly in the computation of final logits. Thus, examine the ability of foedforward ReLU network to achieve the same real-valued output as max pooling operation with Lo error. And since diminishing the representation capacity of single neuron necessarily reduces the expressivity of an entire network, we focus on the expressivity of a single neuron.
3.3 Computing max using ReLU
represent. In this section we begin developing our negative results. Thhorem gave a positive result on the complexity of functions that composition of lincar and ReLU functions
The maximum of two values can be computed using the relationship
max(a, b) (ReLU(a b) ReLU(b a) + ba/2
(2)
It seems that there is no tractable generalization of this formula for dimension d > 2. For example, in Appendix A, we give the analogous equation for the ternary case, and see that is not linear in ReLU Teatures. Building upon this, the appendix contains a heuristic argument that expressing the maximum of more than four variables without function composition may not be possible in general.
Nevertheless, Theorem 2 shows how with additional depth feedfoward network compute the maximum of many variables by recursively forming pairwise maxes.
Theorem 2. max: d + can be written as (r)sgdd)]hidddee layer feedforward network, where the kth hidden layer has width 2 (d)
Sketch of Proof. A variant. of Equation that is applicable to feedforward networks is
4

---

Published in Transactions on Machine Learning Research (09/2023)
max(x.y) (g ReLU o (x, where
+ y
f(z +
y
(3)
Φ(x) (Zo:n/4 + Jn//dm/22 + In/2:3n/4 2sn/4m)/2.
Here Enjong means the ni th through the (n22 1)th elements of x (inclusive), and is the dimension of the input. f and are linear. At the cost of quadrupling every layer width, ReLU can evaluate pairwise maxes and [log][d]] iterations of pairwise maxima can compute the maximum of d variables.
As an example, the max of five variables is simply written as three iterations of pairwise maxes:
max 21 T22 Ts, T4, max 221, 22)
where max 23, 24), 22 = max(25, 26)
where 23
max(x22 23); 25 = max T4), = max 25).
Theorem 2 is an upper bound on the width and depth necessary to evaluate a max function. Corresponding lower bounds are more intricate. [Tblle I outlines various possible conversos, and the next section discusses the function class that characterizes our innovation.
4
The class of subpool max averages, Ma(R)
Our work pertains to particular function class, Ma(R). In Section 4.1 we describe Ma(R), and in Section 5 we justify the relevance of this function class to deep learning.
4.1 Subpool maxes
For vector x E Rd and index set J C (1,...,d} we term max(#; j E JJ the J-subpool max of a. For example, if = = 23,2, 2,,1,001 10,5), then the {1,2, 4)4sbbuboool max of x is max(3, 2, = 5. J-subpool maxes are generalizations of the max function that trade off complexity and accuracy the sense that for J1 C J2, the J1-subset max is simpler to compute than the Ju-sut max, but the error of J1-subpool max will always be at least that of J2-subpool max.
Let C(j,r, r,d) denote the jth (out of (+)) subset of (1....,d) dd of size r in the lexicographic ordering, For example, 211,2,3) = {1,2), C(2, = [1,3} and C(3, = {2, 3). To keep the notation manageable, let (x) denote the C(j, r, d)-subpool max of x (the dimension d can be inferred from the size of æ). And in order to more elegantly model a constant intercopt, lot the C(1, 0, dd-subpool max be 1.
Linear combinations of J-subpool maxes are a natural class of estimators to the max function. We organize subsets J by (1) the size of the subset, r, and (2) the subset index of that size, j. For R C 1......... 1, let
Ma(R) ΣV rER
Sawer (x) 8 E R
(4)
be the set of all linear combinations of r-subpool maxes, r E R. Let a general element of Ma(R) be called an R-estimator, Theorem shows that max & Ma(f0,1,... d 13), with a bound on the Loo error from this function class.
First, however, we present Theorem 3

---

Published in Transactions on Machine Learning Research (09/2023)
T=
T=
T= 4
Figure 1: Averaged subpool maxes for d 5. The numerical value of each node is presented as inverted grayscalc. Each row 1,2,3, 3, 4 presents on the left the averaged subpool maxes over pools of order As the order of the subpool maxes grows, the average value (on the right) grows darker towards the actual max.
Ej= wir(() be the average of all subpool mares of E T&d of order Let Z(i) (the subscripts being enclosed in parentheses) denote the jth largest element of a vector x (order statistics notation).
Theorem 3. Let S(1;r, (:)
d-
d
S(rrr,))
r 2()))
(5)
Sketch of Proof. TG) is the largest value within a subpool if and only if all indices less than j are excluded from that subpool and j not excluded. For a subpool of size r the r r- 1 remaining values must be amongst the d-j values =.-1))-..;(a)) Thus, amongst all subpools of size r, there will be ((=)) in which the largest value is z())
The average of subpool maxes of order R. give summary of the quantiles of the distribution via particular weighted average, with better fidelity to the max for larger For example S(z; 1, d) is simple average, but S(x; d(z; = ((d=1))x))+220)0) contributing. The idea is demonstrated further in Figure 1] with the individual subpool maxes easily tied back to the inputs via shading, and the higher-order subpool max averages increasingly resembling the actual max. As another demonstration, the point x (0
is mostly the max value, with only the sccond-largest value
1), the error of an order-1 approximation is 2(1) -(1) 1, 1/d. While for an order d- approximation it is much less, at 2(1) S(z; d 1, d) 1/d.
4.2 Optimal approximation over Ma(R)
Now we present our main result, Theorem 4 gives the minimal errors achievable with approximations in Ma(R), for varions R over the d-dimensional unit cubc. For example, Equation 9 states that the best L error achievable using only terms from R {0, - 1} (a constant term, the mean, and S(x; 1,d)) is 1/(2(d + 1)) using (5o $1 Ba-1)= (1/2 dd - 2) d(d- - 1) 2)) (1)
Theorem Let ll denote the the Loe norm over the unit cube: If supzejo.1u [f()). Let dist(R)
minme.M Im max I|oo; where Ma(R) is defined in Equution 4.

---

Published in Transactions on Machine Learning Research (09/2023)
1 1d-1
dist (())( 2 d
(6)
dist(fd-1)) 1/(2d-1)
(7)
dist(f0,d 1}) 1/(2d)
(8)
dist((0,1,d 1}) 1/(2(d + 1))
(9)
( 1, 1}) 1/d
(10)
d- 1}) = 1/24.
(11)
Skelch of Proof. The idea of the proof is as follows. We first establish symmetry as property of any optimal estimator.
Then we assume that the Lee norm of the error is characterized by [R] nonzero corners of the unit cube and zero. Under this conjecture, the norm is optimized by evaluating the error as a function of the coefficients, and choosing coefficients which equate them. Generally, changing coefficients will increase the error at one point and lower it at others, and balancing these effects characterizes optimality. For example with R = {0, d- 1}, the optimal coefficients are (6-1) (1/(2d), 1). At x (o..... 0), (1, (1.),....O) 0) and 1I. 1) the error of this estimator is clearly 1/(2d). Given the conjectured error and coefficients, we then prove it is optimal by contradiction: by showing that any other coefficients attain a higher criterion at some x.
To continue the example from the proof of Equation 8 the only way that both (2d( < 1 - 30 Ba-- (the condition at x = (1,..., 1)) and 1 - 9o B (dd-d)/ < 1/d2)) (the condition at x = (1,0, ,,.0,...001 0)) is for 3u > 1/(2)). But this clearly precludes the error from being < 1/(2)) at x = (0, (0...)..,))
We see that even with R = mcaning esscntially that insufficiently deep networks in M(R) cannot model max pooling, and giving a partial converse to Theorem 2
1}. the largest R that does not include d, the error is not zero,
Equation 6 gives a linear model as a baseline for the max. The error is high, and in higher dimensions, not much different to a constant model (obviously, the least error that an intercept alone can obtain is -5 dist((())) Equation shows that error declining with dimensionality is achievable with a higher order term. Contrasting |qquation to Eqquaion quantifies the additivity of the intercept. Including an intercept helps, but primarily in low dimensions, which makes sense an intercept does not scale with dimensionality. Since the intercept requires negligible computation, we assume its inclusion subsequently. Including the grand mean as a feature entails no meaningful further nonlinearity, and reduces the error from 1/(2d) to ((((d+1)) (Equation 9), thus we assume its inclusion subsequently.
important for understanding how the error falls with the addition of further strongly dimension-sensitive terms: appending d 2 to {0, 1. improves the rate of convergence from O(1/d) to (()d²). Equation 11 gives the best-case rate of convergence: if all lower order terms included, then the error is O(1/29). Contrasting this with Equation 10 see that the inclusion of many lower order terms is apparently necessary for low error. Qualitatively, Equation 11 implies that max & 1.., 1}), though it can be approximated well within the function class.
Equation 10
Let Si : Rdd + R denote the optimal estimate based on terms in R. Lox error can be high, even if fž max on most of the domain. If the the high error could not be realized in practice because the mcasure of the domain on which it arises is miniscule, then our result would be only technicality with little practical relevance. In the literature studying the number of linear regions in piecewise linear network, this distinction is recognized as the difference between the maximum and average number of linear regions (Terann& & Monr (2021)). Theorem 5 shows that this is not the case, with a lower bound on the measure of a set on which the L2 norm is high.

---

Published in Transactions on Machine Learning Research (09/2023)
Theorem 5. For / let ())
[0, 10. (2())
(anj-fh(a2 ff((z)) e) denote the subset of the unit
cube where the error of fū at least e, Then for all with 0 R, vol(W R)) 2 (dist(R)/2 -)",, where vol is the Lebesgue measure over [0, 1]
In Appendix C we solve for the L2 error of Equation 11 and find that it is also not zero. Thus: not only can the error be high, it is moreover high on average, and at many points the domain.
In fact, the entire distribution of z(1) - (z) can be derived, and we do this in Appendix D For simplicity, we here phrase only the headline result: the error is almost surely nonzero.
Theorem 6. If x is uniformly distributed over the wnit cube, then (ar E [0, 1] (E - (a((2) 0}) = 0.
5 Experimental evidence on the relevance of Ma(R)
The theoretical analysis of this paper would be diminished if a class of feedforward networks more general than Ma(R) could achieve significantly less error. This section presents experimental evidence that Ma( is an adequate proxy for all networks of the same depth in approximating the max function. It does this by showing that additional capacity does not appear to improve the quality of the approximation.
Formally, for f given in Equation let w(f) E N contain the number of columns of Wi...., W. the widths of the hidden layers. [Appendxx F presents a concrete algorithm for representing fž in the form of Equation 1 For example, via this procedure with d 9 and R {0, 1,7,8), fū can be computed by feedforward network with hidden layer widths w(f)) (78, 122, 182). Finally, let Ga, denote the set of all depth & feedforward DNNs Rd - R, and for > 0 let.
Gd(R, = (g E Ga, Gd,[oog (max R]] : w(g) S 1 x w(fi}
(12)
be the set of all neural networks that are at most limes wide as Si: the optimal estimator in Ma(R).
Since Ma(I) C Ga(R, 1), < #2 = m)( S Ga(R, and lim Co(R, n) = Go Io, (mux R2)] Ga(R, μ)) represent a parameterized interpolation between Ma(R) and all networks of a given depth and μ is our notion of "capacity" when we speak of adding capacity to Ma(R).
Our rhetorical point will be supported if a DNN does not achieve low error. This is awkward because failing to achieve low error on deep learning task is not difficull, for example it could result from coding mistake bad hyperparameterizatoor That said, given the simplicity of the modelling problem, excluding bugs is reasonably simple- we code it in an idiomatic fashion, check that the code can solve problems that should be solvable (for example, replacing the max with the mean), and transparently release the source code. We endeavor to show that our results are not caused by poor modelling choices with extensive ablation studies in the appendix.
There is an important precedent for this type of result in machine learning experiments: whenever a paper shows that some method is bested by another, we must assume that the inferior method implemented correctly and reasonably. Thus, although demonstrating experimentally the correctness of failing method requires a high standard of evidence, the nature of the argument is not inherently problematic.
5.1 Experimental setup
Independent test and train datasets generated uniformly the unit cube with 10,000 rows. L loss is directly optimized by Adam optimizer (with PyTorcc default parameters). Results similar with MSE loss. We use PyTorch default initialization. A batch size of 512 is used throughout, and the data set is shuffled over epochs. Training is run for a uniform 300 epochs. All computations are run on a mix of inexpensive, consumer-grade graphics processing units (GPUs), and all experiments described in this section can be run in a few GPU-days. We repeat all analyses over ten pscudorandom number generator sceds, with both the data being generated differently, and different randomness in the fitting (e.g. the shuffling over minibatches).
8

---

Published in Transactions on Machine Learning Research (09/2023)
5.2 Results
Our experimental evidence consists of assessing how expressiveness of trained models Ga RR p)) depends on μ.. A DNN Ga(R, μu) optimized to model + 2(1) is more expressive if it achieves lower empirical test Loo error. We term this quantity ERR(R, p). If expressiveness is not substantially increased ( ERR(R. μ1) is not substantially decreased) for progressively greater H,, then a lower bound on the error of approximating the max function over Ma( empirically also holds for Ga. And this is what we see.
We focus on I around 1, because this corresponds to the width of fR To prove our desired point that adding capacity does not significantly increase expressiveness we require only ju 2 1, however we include also results for j < 1 to help foster intuition. This is especially important as the literature kernels (NTK), for instance Zhlen-Zhu et al. (2019). shows that for a fixed dataset size, error falls from high levels for (not all the assumptions of the NTK, such as a very small learning rate, hold so the prescriptions of this model are indicative) small models, but rapidly levels off.
newral tangent
Neither the NTK nor universal approximation theorems (UATs) insure that that there is a network that achieves arbitrarily low error as μ f oc. However, UATs make make no guarantees about fitting,
We examine R = {0, 1), f0, 1,d - 2, 1}, and 1.. - 2, d - 1} as prototypical "small" "medium", and "large" approxinations, respectively. We see that although larger models do empirically achieve lower errors, the overall flattening trajectory of their dependence on increased capacity is uniform.
For a single order d max-pool layer the maximum expected number of regions is, from [Toran & Montúfar (2021), Theorem 8: 1+ (d - 1)d/2. Contrast this with Montúfar et al. (2014)'s bound for a single-output, d-input fully connected network of the form Equation 1 of (1 + w(f))) x... x (1 + w(f) Thus, by this metric, == 4 more than suffices to model the any reasonable d.
main experimental result: fitting error does not reliably fall as μ rises. Even quadrupling all layer widths does not noticeably increase expressiveness. Clearly the amount of data available to train models of differening capacities is an important determinant of performance. Figure 3 examines the effect 2, - 1} model. Here the x-axis is on a
Figure 2 presents
of dataset size on training error for the R = {0, 1,, logarithmic scale in μ space. We see that although test error contimues to reliably fall with the addition of more data (in line with both the NTK, which guarantees that the global minimum here at most 1/24 by Equation 11 should be achieved with enough parameters, data, and low enough learning rale), there is marked flattening for all dataset sizes beyond a certain point, simply adding capacity does not make more accurate model.
Figure 4 analyzes each model separately in greater detail. Shaded around the sample mean is the region encompassed by +1.96 standard deviations. The max and min values over the ten seeds are also plotted in dotted linds. We observe that the min and max are roughly coincident with +1.96 standard deviations above and below the sample mean, so the distribution of results over seeds is even more thin-tailed than a Gaussian. The train error is also plotted a dashed, slightly lower than the test. The train error follows the same trajectory as test.
This analysis shows that greater width does not seem to decrease approximation error. From this, we conclude that although our main results are proven only for MM (R), empirically they translate well to more general and powerful function classes within the space of all foedforward networks. Appendix G contains additional results in order to further augment and establish the rosust of this conclusion.
5.3 The complexity of Ma(R)
Equation 7 and Equation 11 represent quite disparate orders of estimation error. This is because 1, .., 1}) is much larger than 1a(10,1,d 13). The most useful way to understand this
4There are however witt reasons that, even for 1, (R) ç Ga( 1). One that G2 allows intercepts in the linear layers, despite not being prcsent in fū (ef. Appendix Ca(R, n)) also imposes no low-rank structure the weight matrices, dospite straightforward representation of the thoorctical weights as the outer product of matrices roughly one quarter large (via the quadrupling of layer sizes implied by [Equatin 3). The larger is the class of models that does not substantially reduce error, the more conservative are our experimental results and the stronger our conclusion.
9

---

Published in Transactions on Machine Learning Research (09/2023)
0.30
[0,1,
0.3
100
500
0.25
(0,1,
1,000
R (0,1,-.,-2,d 2,
2,
ERR (R, jL)
0.2
5,000
0.20
10,000
20,000
0.15
0.1
50,000
0.10
100,000
760
2786
16198
63374
1461207
1000115
.50.75
3
Figure 2: ERR(R, μi) (y-axis) does not continue to fall with greater y (z-axis), meaning that expressivity is not increased with more capacity.
Figure 3: x-axis: number of parameters in R (0, 1,...... 2- d model, y-axis: error. Each line is a dataset size, given in the legend on the right. Er- ror declines with more data, but the pivotal pattern of Figure 2 is unchanged.
x-axis:
# of parameters, (shared) y-axis: ERR μ1)
= (0, 1}
R = (0,1,d 2, d. -1
R = 10, 10.,,..., d 2, -13
0.3
0.2
0.1
1103 2352 2885
14489
31813
55857
6757
15000
20022
102073
228157
404273
63374
201207
1000253
2247130
3001865
Figure 4: r-axes: number of parameters in R-estmators, y-axis: solid line: average test error, dashed line:
average training error, dotted-lines: min / max over trials, shaded area: averaged test error 11.6 standard deviations.
10

---

Published in Transactions on Machine Learning Research (09/2023)
10
X x10
5
8
4
2
2
10 11
0
250
500
750
1000
10
10
10
(a) Parameter count for ordered by size, then lexico- (b) (Logarithmic) a-axis: Loo error, g-axis: parameter graphically within sizes. Different [ are denoted with count. Marker color as in Figure 5a differing background colors.
Figure 5: Estimator size and error in d 12.
R 1, 1}
R = 1, 2,d - 13
10
10
1
2
10a
3
4
5
10
20
30
10
20
30
d
Figure 6: Model sizes for neural networks representing fū for two different R. y-axis (logarithmic). hidden layer width, æ-axis: d. Layer numbers by color are shown in the legend on the left plot. Depth of the requisite network at each dimension is implied by the number of lines present, for example a d = 17, R = 1, estimator has w((f) = (96, 80, 72,68) 68).
is in terms of the network sizes that can model elements of M(R) for different R. Appendix F algorithm for writing fğ as a feedforward network based on reusing lower order subpool maxes to evaluate higher order subpool maxes in a way that skips unneeded orders. This method is simple, and reasonably efficient, given the unavoidable necessity of computing essentially O (9) terms.
presents an
Figure 5 plots the number of parameters in deep neural network representation of R-estimator. Figure 5a relates the parameter counts to R. This ranges from less than 3500 parameters for R {0, 1,2), to nearly 50 million for R {0, 1,......,4 d 1). Figure 5b further relates the model size to the I error bound computed in Appendix E to convey a sense of how many parameters are needed to achieve a given error. In both plots, we group models by |R] indicated by color.
For another view on model size that offers more insightful on how network architecture affected by dimension, Figure plots the model sizes for networks implementing two fi for two R, as function of the model dimension, d. The depth of these models is always [logz(max: 1)] +1.
11

---

Published in Transactions on Machine Learning Research (09/2023)
6 Conclusion
Motivated by marked trend in the design of computer vision architectures, we have posed and answered the question: can max pooling be replaced by linear mappings composed with ReLU activations? And when would doing so give a model that is considerably different?
To do this, we developed new notion of approximation and a now class of results that complements existing work on the number of linear regions piecewise linear networks. We first established distance in intermediate feature space as the notion of comparison. Next, we established simple baseline: pooling with kernel size of d can be computed by block of logz(d) narrow layers. We next introduced subpool max averages as tractable class of approximators, and proved that the max function in d dimensions cannot be written as the linear combination of subpool max averages of order < d, though the error can be made as low as 1/2". By establishing experimentally that the class of subpool max averages was not significanly less expressive than more general function classes, we exlended our analysis to wider networks not const rainned have a fixed weight pattern. As a byproduct of this analysis, we are able also visualize the complexity of all approximators.
In future, we hope to further examine practical implications of this analysis, establishing experimentally that there me be some non-accuracy reasons to prefer max pooling, such as adversarial robustness, Some preliminary evidence on these conjectures is presented in Appendix H.]
Acknowledgements
We would like to thank Guillermo Ortiz-Jiménez, Apostolos Modas, Arnaud Pannatier, Suraj Srinivas, and the anonymous reviewers for their valuable feedback. KM is supported by the Swiss National Science Foundation under grant number FNS-188758 "CORTI". ND was supported by Swisscom (Switzerland) AG.
12

---

Published in Transactions on Machine Learning Research (09/2023)
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layens. Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019. URL https://dd) acm. 0tt.0//10..555534422233383 3454408 3454840
Christian Blatter. Nice expression for minimum of three variables? Mathematics Stack Exchange, 2011.
URL http://aa...tcccccccaeeee.....//
Y-Lan Boureau, Jean Ponce, and Yann LeCun. A theoretical analysis of feature pooling in visual recognition. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML'10, pp. 111-1111111111 118, Madison, WI, USA, 2010. URL hta.lpppps../al...o.//////////23
Steven Boyd and Lieven Vandenberghe. Conver Optimization. Cambridge University Press, 2004.
Walter B. Carver. Systems of linear inequalities. Annols of Mathematics, 23(3):212 220, 1922. URL http:
// //www.jstor orggstaabee/16/999
Cody Coleman, Daniel Kang, Deepak Narayanan, Luigi Nardi, Tian Zhao, Jian Zhang, Peter Bailis, Kunle Olukotun, Chris Re, and Matei Zaharia. Analysis of DAWNBench, a Time-to-Aecuracy Machine Learning Performance Benchmark. arXiv e-prints, Jun 2018. URL http://arxiv. http:///ariiv.orgabb//BBBe 1a00ab000100007777777
Ronan Collobert. Large Scale Machine Learning. PhD thesis, Université Paris VI, 2004.
Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David. BinaryConnect: Training Deep Neural Networks with binary weights during propagations. arXin e-prints, November 2015. URL https://doi.
org/10.48550//r/ 40550//aa.iv.15555 11111000.11100063
George Cybenko. Approximation by superpositions of a sigmoidal function. Mothematics of Control, Signals and Systems, 2(4))303-31 314, Dec 1989. URL https::/doi.org// http://00....00000.0000///222222 1007//F551///
Arthur P. Dempster and Robert M. Kleyle. Distributions Determined by Cutting a Simplex with Hyper- planes. The Annals of Mathematical Statistics, 39(5):1473 1478, 1968. URL https://doi. org/ 10.
2214/omm/117766812555
Morganna Carmem Diniz, Edmundo de Souza Silva, and H. Richard Gail. Calculating the distribution of linear combination of uniform order statistics. INFORMS Journal on Compuling, 14(2):124-15) 131, 2002.
URL https://doi.org:: org/10. 22.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. Tn International Conference on Learning Representations, 2021. URL httppp////gaaaeeeeeeeee/////rrra
William Falcon. Pytorch lightning. GitHub. Note: httphh//wggggttoooo///////ooottt 3, 2019.
Kunihiko Fukushima.
Neocognitron: A self-organizing neural network model for mechanism of pattern recognition unaffected by shift in position. Biological Cybernetics, 36:193 202, 1980. URL https://doi. org/10.. 10011000077//F03442200
Ian Goodfellow, David Warde-Farley, Mchdi Mirza, Aaron Courville, and Yoshua Bengio. Maxout networks.
In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, number in Proceedings of Machine Learning Research, pp. 1319 1327, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL hRtLhttp://rooceediii http://ppoooooaagooooee/eeee///s
mmlr pptpss//////oooeeeee/eo/o/////// html
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversaria examlees. International Conference on Learning Representations, 2015. URL http:///axxvv.rrr/aa///42..
13

---

Published in Transactions on Machine Learning Research (09/2023)
Philipp Grüning and Erhardt Barth. Bio-inspired Min-Nets Improve the Performance and Robustness of Deep Networks. SVRHM 2021 Workshop @ NewrIPS, pp. Ttl::2201.02144 January 2022. URL https:
//arxiv. //arxiv.org/ablll wrgg/b/////...//0///gg
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Kamalika Chaudhuri
and Ruslan Salakhutdinnv (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2596-2604. PMLR, 6 2019. URL https:
//proceedings. mlr. wwwppp/wweee///// httpe//////anann1a... html
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016. URL https://doi.onn 10. 19.1199/CVPR 2016.90
Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella. Towards lower bounds on the depth of relu neural networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 3336 3348. Curran Associates, Inc., 2021. URL httpa://prooceediggs negriss.eurppp... http:pssccc/aapp/222////// Paper. pdd
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In Advances in Neural In- formation Processing Systems, 2017. URL http:://prooeediins..eeus peerripp.cc/ppppr//0////.... pdf.
Kurt Hornik. Approximation of multilayer feedforward networks. Newral Networks, 4(2):251 257, 1016/ 010.0000000000000000000000111110
of
1991. ISSN 0893-6080. URL https:://oi.
Andrew Howard, Ruoming Pang, Hartwig Adam, Quoc V. Le, Mark Sandler, Bo Chen, Weijun Wang, Liang- Chich Chen, Mingxing Tan, Grace Chu, Vijay Vasudevan, and Yukun Zhu. Searching for mobilenetv3. In IEEE/CVE International Conference on Computer Vision, 2019. URL httts:://di.org/// otg//0..100000000
ICCV 2019..99.000 .01140
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009. URL https://www toronto...... Salu/-rriz/eearrnnn fewitg-fffatte--eeee -aliass-2009-111 Td.
Alex Krizhevsky. Convolutional deep belief networks on CIFAR-10. 05 2012.
URL
https: //::://wwsa /ttp///wwwcc CB
toronto. edu/
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolutional
neural networks. Communications of the ACM, 60(6):84 90, May 2017. ISSN 0001-0782, 1557-7317. URL
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. Available: http://yyanneeec..cc www.eeddeeeeo/eoooooooooooooeeee /mnist, 2, 2010.
ATT Labs [Online].
Andrew L. Maas, Awni Y. Hannun, and Andrew Y. Ng. Rectifier nonlinearities improve neural network acoustic models. ICML Workshop on Deep Learning for Audio, Speech, and Language Processing, 2013.
URL httpp::/aaa........ stanford. stanford.edd//amaaee. elhh/-amassppperr/eelll _ar___ybrrd hybrrddiiml22111 icm12013m11..0.. 101001_ffiaall. final.pddi
Sébastien Marcel and Yann Rodriguez. Torchvision the machine-visio viisinn package of torch. In Proceedings of the 18th ACM International Conference on Multimedia, MM '10, pp. 1485 1488, New York, NY, USA, 2010. Association for Computing Machinery. URL https: org/ 10. 1141/1173951111111
Tadashi Matsunawa. The exact and approximate distributions of linear combinations selected order statistics from a uniform distribution. Annals of the Institute of Statistical Mathematics, 37:1572-9052, 12 1985. URL httpp::/ddoi.org/// wtt.://////.1000/////4800000
Guido Montáfar, Yue Ren, and Lcon Zhang. Sharp bounds for the number of regions of maxout networks and vertices of minkowski sums. SIAM Journal on Applied Algebra and Geometry, 6(4):618-66 14461,96999.111 2022. URL http///....r//1..11////////...//
14

---

Published in Transactions on Machine Learning Research (09/2023)
Guido F Montúfar, Razvan Pascamu, Kyunghyun Cho, and Yoshua Bengio. On the mumber of lin- ear regions of deep neural networks. In 7. Chahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Newral Information Processing Systems, volume 27. Cur- ran Associates, Inc., 2014. URL https://proceeding neurips.com ca/paper_r.. htcc/ppperffiee/ppeeeeeee fttes//pppaee/011//////// pdf
David C. Page. How to train your resnet 8: Bag of tricks, 2018. URL httt:://myytlle.i//laaa -tt.--trarrrorrr---eee----------
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In Neural Information Processing Systems 2017 Workshop Autodiff Program, 2017.
Jonas Rauber, Wieland Brendel, and Matthias Bethge. Foolbox: A python toolbox to benchmark the robust- ness of machine learning models. In Reliable Machine Leorning in the Wild Workshop, 34th International Conference Machine Learning, 2017. URL http://arxiv. hwtp:/org/aaaao abs/1707.01113
Maximiliam Riesenhuber and Tomaso Poggio. Hierarchical models of object recognition in cortex. Nat. Newrosci., 2111):019--1025, 1999. URL
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):211125) 2015. doi: 10.1007/s1 111112111000006--
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning. PMLR, 2018. URL http:
//proceedings..
wwwpeediins.m.r...... mlr. wtt....rree///80/erra......
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. Tn Yoshua Bengio and Yann LeCun (eds.), International Conference on Learning Representations, 2015. 1556
URL
Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin A. Riedmiller. Striving for Simplic- ity: The All Convolutional Net. In International Conference on Learning Representations, 1CLR Workshop Track Proceedings, 2015. URL http:///axxivv..g/bbbbsss 1tt///412...8.. 6806
Christian Szegedy, Vincent Vanhoucke, Sergey Toffe, Jon Shlens, and Zbigniew Wojna. Rethinking the incep- tion architecture for computer vision. In IEEE Conference on Computer Vision and Pattern Recognition, 2016. URL
111./////....../......r. 2016..08
Matus Telgarsky. Benefits of depth in neural networks. In 29th Annual Conference on Learning Theory. PMLR, 2016. URL htttps:// www.engg...r....mmm...........em wtt.:.mw........ee. ptppsee//v/ttellarrrr///// html
Hanna Tscran and Guido F Montúfar. On the expected complexity of maxout networks. In
M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Ad-
vances in Neural Information Processing Systems, volume 34, pp. 18995-29009 sociates, Inc., 2021. URL https://prooceddgg.eeeee neuripss...s.....oooe....r.sps.. cttpiisss.cppeeee vac/paper__. Saaperfflls/pprrtteeeeeeeeeeeeee files/pappr/2021/E11 Fccb0ee9ccBb00613331118888888862 pdf.
Curran As-
Herbert Weisberg, The distribution of linear combinations of order statisties from the uniform distribu- tion. The Annals of Mathematical Statistics, 42(():704 709, 1971. URL http::ttt/w///sttto/// h
2239815
Huan Zhang, Tsui- Weng, Pnn-Yu Chen, Cho-Jui Hsich, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Process- ing Systems 31, pp. 4939-4948. Curran Associates, Inc., 2018. URL http::/paperr: niw.. cttppspppppsccccce 7742-efficient neural- www.ral-etwwrrr-aee-e oowtor----ooatteee---tttaaaaaaaa withhnwwwttttth -etooraal-ttttvviiio---tttttttti ott.aaaaessrrrttoooooooooooooaoa
pdf
15

---

Published in Transactions on Machine Learning Research (09/2023)
A In what sense is evaluating max( 22, 33, L., v35) hard?
To motivate the differences of the max function with higher dimensionality, in this short section, we argue that there is unlikely to be a simple generalization of the correspondence between maximum and ReLU in
d= 2 to general The idea is entirely due to Blatter 2011), though any mistakes the interpretation are ours alone.
Theorem 7. There no algebraic expression for
(I1, 22, I3, FA, 25) + max(r1, 23. F4, 23).
Proof. max( 22, 23, Z4. 25) is a root of the polynomial (x x1 (x _ - x2 x2) - 13)(2 - xT)(E - æs). Suppose that there was an algebraic expression for the largest of (œ) 22, 23: v4, 16), say f(x 22; 233 24, 1z) then, then =x))<==sss((e f( 43, T4, &5)) could be found via the quartic equation, and we would have an algebraic expression for all five roots. However, Abel's Theorem states that there is no algebraic expression for general quintic polynomials.
the roots of (x-2))) 2x x2)
The argument is subtle, so consider the same argument applied to the maximum of two values. The two roots of (x x1) (x - x2) are well known to be (x1 + x2)/22 + V + x2)² - 12/22/2, and the larger corresponds to adding the discriminant:
(2) + x2) + (x1 x2)² 22
(21 + x22)
((1 x2)²
(x) x2) + | - x2
2
2
2
Which is well-known trick for reasoning mathematically about the maximum of two variables. A corre- sponding expression comes from solving the cubic equation
Izi (|K 22l + |2] xal) - x2((21
x2l
+
zal + |21 x3 zal) 23(122
x2l
+
122
x3l
|21 2zl
x2l x1
la22 xal
x3
This equation is tractable because we can assess the min and max similar to above, and impute the third value from the average 5 It not clear what the analogous interpretation is for the quartic equation, though one presumably exists. However, for fifth and higher-order polynomials cannot generally write down algebraic expression for the roots, determining by inspection which will be the greatest seems unlikely.
B Proofs
B.1 Proof of [Theorem 4]
Proof. Let perm(d) denote the set of all permutations of {1,2, d), and let
M2(R) (m Ma(R): m(x1, 12,1,,22.-.. ..,
.2. .2. r.) 3 Fou) for all perm(d))
denote the restriction of Ma(R) to those elements that are invariant to a reordering of its arguments. Because max is symmetric in this sense, any optimal approximation to must lie in (RRR):
5 Seee also the excellent exposition given http:////mtttataaeeeecaaaaa..//e
16

---

Published in Transactions on Machine Learning Research (09/2023)
Theorem 8. For all R,
min mEMa(R)
||m- max 100 =
min (EMg(R)
I| max 1l00
Proof. Assume otherwise, meaning that there is an m that is not symmetric and an such that m(x') < m²(x) for all symmetric m and all r'. In particular m(xx) m²(x) for all permutations &g of æ. Thus
Σ m(l')) < (x)).
d! @Eperm(s)
However, x di Eosperm(e) m(x²)) evidently symmetric, a contradiction.
Thus, it is without loss of generality to optimize over (*(R) rather than M(R), and turn to oper- ationalizing the symmetry assumption in terms of the coefficients. For > Wyr(la eak) 1 for all A: ..,, and all j 1, ...., (+) since there only single non-one value. Thus all terms of order greater than are equal, and the sums are equal by symmetry, 81 38 =... .4. Call this single value 31, and (for 0, 1 E R)
necessarily have that for all f E ()
()) Σ
M2(R) + Ld)
Σ j=
(f ((jr.)))) 88, B1 E R
Repeating this process for pools consisting of entirely of 2, except for 3, .4....d-11 zeros in turn implies that the estimator must be a function of S(x; r, d) alone, and not the individual terms of the sum separately:
Mā(R)
X Σ S,, :3, PER
(13)
So, the maximization over all m E Ma(R) can be reduced to the maximization of [ scalar coefficients.
In the simplest terms, to prove Theorem 4 we want show that
min |0)))) - Bo - B, = 1d-1
(14)
96.91
2
min
||(()) - = 1/(2d
(15)
Ae-1
min 80.9a-1
||x(1) - 30 - -0 lo = 1/(2d)
(16)
min [| 80 3,5((; Ba_ -1 0c = 1/(2(d + 1))
(17)
8o. .9-1
min
|001))
30 - S15(x; 1, -4 -.000
= 1/d
(18)
Bo.Bi 2.84
min Bo-
||<(1) - 8o - 111 d) = 1/2d 1
(19)
where the Los norm is taken over values of x E [0, [].
(x))((x) defined in subsection 4.1 the C(j. r, d])-ubbooll max
17

---

Published in Transactions on Machine Learning Research (09/2023)
The proof of each is similar, to facilitate their analysis, distill the essence of each into template. There are three essential steps:
1. Conjecture coefficients, 3 with the help of Appendix E
Lower bound: for any f and for any set of points 2 [0, [0,
min max lf(3, 2 min max ZEP
[f( = max 1f(8".z)
aEP
where we prove the equality by contradiction: suppose there is better 3", and derive a contradiction.
3. Upper bound: for any f.
min max lf(8,x)] max [f x))--
Then we show that max, [ S 30 by writing it as a linear combination of order statistics.
For Equation 14 let (g6 B1) = ((d - (2/ 1). Suppose that there were some (% (1 achieving a
criterion < P6- Evaluating the error at (1 1 1) and x = (1 0 0), this implics
1 - + and 1 1% 8
58 = (d - 1)(1 (%) < (d + 1)18
- 3/ > 1 d
% S.
d-1
A contradiction the condition at zero. Thus, ming..9, || - 90 3,5(x;1,d)1 2 55- On the other hand, from
Theorem 3
11) 38 S(x; -1-11 1) z(1) d (x(2) + +... x(.)) .B E 1- +
For Equation 15. let 83-1
2d-1. Suppose that there were some 84 achieving criterion strictly less than 0), this is only possible
2d
1/(2d - 1). Evaluating the criterion at æ = (1 if
1 1) and x (1
1
2d
2d
1- 1-84-11 > 2d and By-1 d
2d > B/a and B/a > 2d
which is to say it is impossible. On the other hand, from Theorem
2d
2d
1
(11) 2d
S(x; d - 1, = =I(1)
d F(1) + 7
2d -
x((1) 2.r
1
E
2d -
2d
1
2d -
For Equation 16 let (3) Bi-1) (1/(2d) 1). Suppose that there are some (% Bamz) achieving
criterion < Bg- Evaluating the error at (1 1) implies
18

---

Published in Transactions on Machine Learning Research (09/2023)
-1/(2d) < 1 8 8a-1 = 80-1 < +1/(2d)
(20)
Evaluating the error at x (1
0) implies
- 9/ - 1 11/d + +1/
= 1 1-1-8 < 1 -1)/d
d
(21)
d-1 -1-2111121) < 3//-1.
Combining Equation 20 and Equation 21
d (1 % 1/(2d) < 1- % 1/(2d) = ( d
d
1
1+ d
(1 30)
d-1
2d
d- 1
2d -
- (1 - 8))
(22)
2d
% 2d
A contradiction the condition at that 186 < 1/(2d). On the other hand, from Theorem 3
1
1
1
2(1)
2d - S(x; 1, = d (o(1) - 2(2))
E
(23)
2d
2d
2d
For Equation 17 let (gt 81 12_1) ( プ-2
d(d-1) d-2
Suppose that there were (% 8 82
d+1
achieving a criterion less than B6. then the condition at x 1, (1, (1,.,........0 0), 01,0,.... respectively:
0) imply,
1 16 8 8/1 < +/8
= 1- 81 - 8/-
+2,
2
2
1 %
4-1 > -
= 1- 81
3y d
0
d
1
d 1-1
d-1 1 < +2%
% 8 d
B d-1 d
< + + 1 - 8
3 d-1
d
combining the first and the second implies S 2 - Combining these
2d 24 I 31 while combining the second and third implies
2d
2d
2d
d
30 <
81
- B >
d - 2
d 2
d 2
2(d + 1)
a contradiction the condition at 0.
On the other hand, from Theorem 3
1 T(1) 2(d+1) 1) (d 1)(d 2) (5(1) + .... +..)) (d+ ()(d -2) 2) (ld- 1)0(1) 2222))
(d - 1)
1
1
1
1
1
(1(1) x(2) + (d + 1) 2) (5(3) +... + +(aa))
+
2(d+1)
2(d+1)
2(d + 1)
19

---

Published in Transactions on Machine Learning Research (09/2023)
For
Equation 18
=
2 2(-3)
-1
[[-33
2). Suppose that there were a
(%
81
3
82-11
achieving a criterion less than 86- In order to scale up the proof by contradiction,
we use Theorem
Theorem (Carver 1922
Theorem 3). Ar consistent
y is the only solution for y 2
A bbs.
Applying the assumedd condition at (0,0,...,,0) 0), (1,1,..., 1), 01,1,1,0,.... 00, 1,,10 ... 0), and (1, ...,...)) 0) imply, respectively that
% < +
1 1 P/ - 8 - 88-2
B/-1 990
% 8 3
98-2
8/-1 +
d
(d
1) - 2)
1- 8 d
8--
B/-1 > 9
d(d - 1)
1
d 2 2
d --1
1-
8
8
By 2-2
B
+.5
d
d
d
or Ax b for
+1
0
86
B
+1
-1
+1
+1
B
Bi
A
-1
1
1
and
86
+1
(d+1)(d+2)
+1
4-22
13
d(d-1)
-1
2-2
d-1
d-11
36
It is straightforward to verify that
1/d (d- ()-2))(2))
(d/2-1 11)
y
- 11/2
satisfes A A 0 and y Tb (B 1/d) 0. The last equality is because S 1/d2, We have demonstrated y 0. y + 0 with S 0, thus the system is not consistent, which forms a contradiction to the supposition that there exists a (% 31 3a 12)1) achieving a criterion less than 8g.
On the other hand, from
Theorem 3
1
2
1
+... +..)) (d () 1)
T(1)
d(d 3) d (1(1)
25(x; - 2.
((d 1) + +z2))
d
d(d- -3)
2
2
2
1
d
(1)
P
(2)
+
J
(3)
d
d 3
(I(4) +... + x(d))
E
p d
(d-))an (T1 ( m(2)
d -
p - s(s))
(1d2)
1
(d
2)
2(d 2)
(d 1) F(3)
id
20

---

Published in Transactions on Machine Learning Research (09/2023)
For Equation 19 The idea is the same, but handling d equations simultaneously requires powerful notation. Let B(d) be the d-1x d matrix with crth) element (#11)/C) if d+1, and zero otherwise. We can write the condition Equation 5 simultaneously for all as
0,
1,
S(x; d)
S(x;2,d)
3
T(22)
(())
(0t Oaxi
1 O1xd-1
B(d)
R pld
(24)
((zd 1, 1,d)
(d)
We have indicated the dimensionality of the zero vectors with subscripts. Let V(d) be the d x d ++ matrix
1
1
0
0
1
1
(25)
0
0
1
0
0
0
1
of points at which we evaluate the estimator. Let s(d) be the + 1-dimensional vector starting and ending with jth element (-1)--1; diag(s(d)) encodes the signs of the binding inequalities. Let
0
lixd+1 B(d)V(a)) ) ,b= 1/2d + diag(s(d))
1
A = diag(s(()))
1
where we indicate the dimensionality of the d + 1-dimensional vector of ones. Here
satisfics A 0 and Tb 0. Thus, there are no parameters achicving criterion 1/24, by Thcorem For the other direction, let.
21

---

Published in Transactions on Machine Learning Research (09/2023)
-1/2a
8
(- 1/2))a-22(
(1)
81
11122)2-
3
-11
99-1
(-1/2)
Then, by the binomial thcoren
1/2d
2/2d
(0mn
01xd11 8-=
42/2" 2d
B(d)
2d
Thus
d
1(1) S(x;)) "T; 8r 1/2²
Σ (-1)
2 I(j)
E
1 1
+
(26)
2d
2d
2d
j=1
Theorem 10 (Fundamental perturbation analysis of Lox optimization over Da). Given vector y E IR:
(r() + 7(2)//2 201)/22m0 = arg min max 17 x - al
(27)
oER Λ
(x() (24) min max by X a/.
(28)
oE XEA,
Proof. The maximum absolute value element is given by ||0|/00 maxxed 1x T Aa m [=(]]]
For Equation 27| for any À E Ad, T al 1(> la a) T) For any fixed a, the largest element (in magnitude) of La x will be achieved at the coordinate of either the highest lowest element of and the inner optimization evaluates to
max(h1) - 1ia - al}-
Let a² ((a))) Suppose that a* +o for c > 0. Then I(a) < h7(4) -a 1(-70) 2/a) - (11) - 724)22 e, this quantity can be reduced by setting e to zero. Thus the optimal is a*
Now, suppose that a -e for 0. Then -al < (n()) 1(x(1) 7aa) this quantity can be reduced by setting c to zero. Thus the optimal a is 2 a".
(7(1 7(d)) ) tc,
Equation 28 follows straight!orwwarly from plugging Equation 27 into the criterion (7() + 7/4) implies that the largest value of 7 La X a is (T() /2, and the smallest value is (7(a) - -a))/2, with all other values in-between.
Theorem 11. Let ((3) (0 ...1) - ST B(d) then
8 ...., .......81111 min max (LS....., Ba-1)A Bul
$0.81....Ba-1 AE
satisfies T(Bi,, :.. ,/ 2 0, 8 aargming [[] and B ||T
8 Eii (+)r (1 r)
22

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. Note that the first column of (d) is entirely zero, , Ba-1)1 0 for all ,ay...,,d-1 Thus, if , 2 0, then the smallest element will be zero, and the last two assertions follow directly from Equation 27 and Equation 28
Thus, we need only to show that at any candidate optimum , 2 0 for all i - (31 $2 3d-1) (dd)V(d) I for all Note that no candidate solution would have ((3
((d)(d)) < 0 for any since this would result in a criterion > 1/2, which trivially allainable with B1 :.... 34-1= = 0.
Suppose that a candidate B, m - max; (8 (dd) > 1, then the minimum element of L will be m O, and by Equation 28 the attained criterion will then be
(max L(3); -(1 m))/2
And max; L(B); max(0, 1 min; (8 B(d)V(d))) We have shown that
(g) Ba-1) 20
thus max, L13/m); 2 max; L(8),, and we have that
max L(3/m); S (max L(B); - (1 m)) + (1 (1-m) m) S max L(B), max L(8/m);.
We need to consider three separate cases:
max; L(3/m); = max; L(3); which case the inequality holds strictly.
L()), = but max, L(3/m), > then max, L(3/m), = -1 min; (8 (dd)V This holds only min; (BT (dd)V so
1-m 11 (1- min (5 B(d(Vi(()))) = 2 min (8 (d))
m
which follows from the AM-GM inequality: a>1,b>1 = (a b/ab/a//22 2 Vb 1.
3. If both terms are nonzero, then
1 < m
min B(d)((()))
Thcorem 12. An optimal estimator is increasing.
Proof. f will be increasing and only if TT (d) 0.
Suppose otherwise, that for some i (ST (dd) < 0. Then the criterion will be 2 (1-3T (()) 1/2 by Equation 27 However, by setting 0, criterion of 1/2 can always be achieved, thus cannot be optimal.
23

---

Published in Transactions on Machine Learning Research (09/2023)
B.2 Proof of [heorem 5
Proof. Theorem 12 shows that an optimal estimator is weakly increasing. Thus, for 6 < G0.
(6.0,.. (o.......0 0) = f(p) 2 f(0) = Pg > 6 = max(p) and means an error of at least S - 8. So at the
error will be at least e iff Bg - 2 8. This true for all p E [0, thus [0, -ej C (( R)
(e; 2 (58 - -)
Theorem 11 shows that 8 dist R2,2, and the assertion proven.
This volume bound could improved by including more than just the intercept in the computation of the bound. And, as one might intuit, similar analysis holds at all vertices.
C Le problem
For brevity in what follows, let x(d)- = (dd)V(d) E Rd-1xd+1 and let Egk denote the j-dimensional vector that is entirely zero except for the kth element, which is one. Then the difference between the fitted and actual values, as function of A is:
X (1a-1-64411) Bo B0-BBx(d)) -30 + ((1.41 - cat1.1) k(d) T)
(29)
Let Aa denote the d-dimensional unit simplex, then from Equation 29 the squared L2 error is
J (Bo
(80- -
edi) -(d)
(30)
To lighten the notation, we wrap this optimization problem into Theorem 13
Theorem 13, Let ag E R, a E Rd, Ae gd+1, and E gd+1xd, Let v(d) = Sa, di, then
min / (as (A- T) o(d)A (1 [(=E()) (ET)))E '=T an.o A
'ET ETT(()) A.
(31)
Proof. Expanding the critcrion above:
(d) 20o (A - Ta) ( xda) + (A (A- Ea)T (S, AaTaa) (A (A-Ea). Ea).
The first order critcrion for optimality of ag evidently requires that
og = (A -Ex) ( xax) /v(d),
thus, the critcrion equals
E AATa2/u(d) - -1 sax/u(a)) / xTa\/o(a)) (A-Ea). -Ea)
Ea)T (/1,
m(d) x (A (A-Ea)
24

---

Published in Transactions on Machine Learning Research (09/2023)
Write the inner term the covariance matrix of Dirichlet(1, 1....... distribution E(d), then this weighted least squares problem is solved by
= (= ==
a'
Plugging this equation into the criterion gives Equation 31
Phrasing Equation 30 in terms of Equation 31 is:
we have that the squared L2 error of the optimal coelficients
o(d)(1a- ((a) ( (1- M(d)x(d) (x(d)I())x(d))) m(d) (1a ca1).
(32)
The hat matrix [(d)x(d)) (M( k(d) has rank d - 1, thus (1a- eai) cannot possibly lie in the nullspace of the projection operator, and we have strictly positive error. We skip deriving the exact expressions as a function of and note that the same analysis could be straightfowwardy conducted constraining different coefficients to equal zero.
Distribution of optimal error
In this section, we derive the distribution of the optimal residual.
D.1 A foundational result
Weisberg 1971
gives this result:
Let z(0), J(1), ...)..... I(d) I(d+1) be the order statistics from x sampled uniformly on the d-dimensional unit cube with the convention that z(0) = 0, ((a+1) =.
Let a, 2 0,j = 1,....d d be positive weights, and let a, = Σiz Oik so a 2 02 ... ad- Let ei 02 ... e, be the unique (strictly ordered) values of au, and ke denotes the mumber of aj that ce covers.
Then
d h-11
(x - z)d
Pr
x 2i S2
=
drrk-1
IT T (I Ce)
(33)
where r the largest i where 2 I Cz.
Matsunawa (1885) also gives a characteristic paction-baseed analysis.
In our application, the weights in the linear combination are not nonnegative. Happily, there is reduction to this case presented by Diniz al. 22022) (modernized from Dempster & Kleyle 1968
Let aj be as before, though not necessarily nonnegative this time, and as before let aj Σk=r Or.. Let a (0, a0..a,..,,dd aa) be prepended with and let be the permutation of the (I,...,d d + 1} so that ()(1) 2... 2 (d((+))- Then
Pr
ay S = Pr
Σ
(o) (o041)) S 3=--(1441) 1=1
(((2+1))
(34)
25

---

Published in Transactions on Machine Learning Research (09/2023)
+0.050
+0.010
+0.025
+0.000
-0.025
-0.002
-0.010
-0.050
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
(a) R 10,
(b) {0, 1, 2,d
(c) R- {0, 1, 2,d
Figure 7: Simulated empirical cumulative distribution functions for 2(11) fa( over 1500 uniform random points in the unit cube, for three R. The axis is scaled between + the maximum Lx error.
Basically: you include zero with the as calculated previously, sort them, then the previous logic with the differences (guaranteed to be nonnegative), and modified argument, you get the same probability. In this equation, some differences may be zero, and that is covered in Equation 33 with zero ays.
Actually evaluating the derivatives in Equation 33 is not too difficult there is an efficent recursive formula- tion but is also not totally straightforward. Thus, for brevity we do not go into too much more detail and instead simply observe that the cumulative distribution function is a continuously differentiable function of its input. To give an idea of the distribution, Figure plots the empirical distribution for 1500 points.
D.2 The residual as a linear combination of order statistics
The optimal residual is linear combination of order statisties, from Equation 13 and Equation
[2(x) = Σ (,;
rER
d-r-1
Fi
rER
3 d k
a
(K) where oz =
Σ
(-) r
1=
rEnN k+1)
Thus, the optimal residual a linear function of the order statistics:
2(1) f1( (1 ( 30
Σ
(0.)
The cumulative distribution of this quantity then follows from plugging these coefficients into Equation 34 This distribution is a a polynomial, so continuous, thus the probability that takes any discrete value is zero.
E Bounding the error and complexity of general R-estimator
In this section, we present method for computing nontrivially tight lower bounds on the error from a general R (0, 1,2 ... d 1, 1, estimator. For any set of points P [0, 1]d, have that
26

---

Published in Transactions on Machine Learning Research (09/2023)
m max 2| 2 max [m(x) max(x))
sEP
min (EM
m max 1130 2 min max [m(x) max(x))
(EM sEP
Apply this with P equal to d + corners of the unit cube containing zero, one, two, etc. ones:
Il max 10x0 2
min max {mm((0 0 0))1, (EM
(m(( (1
0)) 1/,
Im((1
0)) 1/,
Im((1
0)) - 1/, 1)) - -]}-
(m((1
Finally, we write this as the convex optimization problem, in 2(d + 1) constraints, and + [R] variables,
using a a standard trick for rewriting Lx optimization (see Boyd & Vandenberghe (2044). )
min (..
subject to
3o +
B,S((0 rER((0)
Σ
0) ;r,d) Sg.
30
Σ
8,5((1
0) ;r,d) Sg.
rEN((0)
30 Σ
3,5((1
r) 5.
rER\(U)
30
Σ 3,S((1
;r 5g.
rEm((U)
3o
Σ 8,5((1 (ER((O)
1) 1);r,)
S
This computation scales well, essentially linear programs such as this can be simply solved on a desktop computer using standard software for thousands of variables and constraints.
F Implementing an R estimator as a feedforward network
In this section, we show how to cast general R estimator as the forward pass of feedfoward network. This analysis is necessary to give benchmark against which to compare stochastic gradient descent fitting. The code, in idiomatic PyTorch and accompanied by extensive test cases, available at lhttps://githin com/ Ediap/benefits-ode -tt---fff-maooooo-e max-pooling
First, we describe concept called the R-mapping, then describe an algorithm for computing R-mappings, and then show how to R-mapping to construct feedforward network that is an R-estimator.
27

---

Published in Transactions on Machine Learning Research (09/2023)
F.1 R- R-mapping definition and motivation
An R- R-mapping describes R-estimator sequence of pairwise maxes. For d E N and r E f1,2...., d} let C(r, d) 211, r), (1,3,..... ...., r l...... {d r,..... d]} denote the set of size (+) of all subsets of (1,2.....d d) of size r.
Desinition 1. An R-mapping for R _ 20, is a sequence of sels L 1,,,.,,., ,6s with s [log2 d] satisfying:
for all r R 0 there some such that C(r, d) Cij, and
At a high level: Each element of an R-mapping corresponds to a set of indices into the input, and at the jth layer computes the max of the input over all indices in tz. The first defining characteristic of an R- mapping ensures that the indices permit the evaluation of all required subpool max averages. And the second condition insures that feedforward network can compute the maxes over the implied indices.
To simplify the subsequent discussion, hereafter assume that {0, S R for all R. Since the first two terms are trivially uncomplicated constant bias, and the grand mean of the inputs are linear features this assumption is without any loss of generality and could be easily relaxed.
F.2 Computing R-mappings
In this section, we show how to compute an R-estimator. We say that is adequate if max(R) S 2 x max (R n [0, (oo__(max())
If R adequate then it possible form the greatest remaining term from pairwise maxes of terms that are lower power of two condition necessary enforce the second condition in Delinition If R is not adequate, then it can be made adequate by appending an additional term.
Let R = (R), where a: (O....,d) d} + (O....,d} d} is defined recursively as:
R
if R = (0,1) is adequate (max(RR) U (Max(((xX)))) U {[max(R)/21} ot.heriise.
a( (R)
{max({)} U aa(R) (max((())))
(35)
The third case covers the situation where it would not be possible to compute an R- R-mapping out of terms in R, and so an additional term appended. For example, a((0, 1,2, 6)) (0, 2,,,5, has been appended since it is impossible to compute the maxes of five and six terms using only pairwise maxes = 2) of pairs of variables. a(R) essentially reduces its argument by one term with each recursive call, and thus it is fast and straightforward to evaluate.
By construction, every truncation of R is adequate, thus for every ř E R with F > 1 there exists an F' R with F' 2 F/2. This means that C(1,d), C(2, d), U u/e....,UuRRR///2.. Cr, d), is a R-mapping, however if R R, then there will be smaller R-mappings since it is possible to skip the computation of some terms in C'r, d). For example, continuing our example above, there are 56 subsets of size 3 of d = 8 values, but 36 terms of length 3 can be combined to form all subsets of size 5 and 6.
For a vector E R with the first and last & elements: (AL (Am).... A())), (A...) Agy). And let FLATSPLIT, be the set-valued function that applies SPLIT to each of its inputs and collects the outputs into single set
k, let SPLITs R + R&* x R² be the function that splits its argument into
FLATSPLITA ((A .?..,.,.,,
= =(. Alw)). ..... Alo))...., (A)) Aio)) .). A,A))) (A)
28

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm Computation of an R-mapping
Input: R S f0.1.....dd
Output: R-mapping suitable for evaluating fūt
R - alt) // Augment R with needed terms
$ = [log2 (max R)]
R + Rn ( N. llgg = j} for j = 1.2...... group by power of 2
R - (i:ie N, Toga i] j) for j 1,2, ,.,, group R by power of 2
for 0,1,..,,8
do
j s s - backward index
i= = then
N₃+ -0
else
N₂ +- 1--1 // terms needed for subsequent layer
end if
Xj - [C(k.r, L........ ..... E Rz} terms needed for this layer
Y < U₁
kj- max(R;) // tuple width in this mapping term t FLATSPLITH, (Y₁)
end for Return .,,
Algorithm I gives one approach to compute an fi-mapping that improves upon naively computing all subpool maxes of order R: The idea is include only those terms in R only minimally in order to support the computation of subsequent terms.
F.3 R-mappings to neural network R-estimators
An R-mapping, as introduced in subsection F.2 a sequence of sets that defined so that each element of constituent set is associated with pair of elements in the previous set.. Thus, it is well-suited to compute pairwise maxes via a simple
block as shown in Equation 3 Computing the average of all subpooled values is of course linear operation.
An important book-keeping challenge with this approach is to enable the network to convey the average of low-order subpool maxes through the network. To do this, we append to the network a "memory" additional neurons which carry forward values computed earlier in the network via identity mappings (propagated through RcLUs via x = ReLU(+z) - ReLU(-z)) through until the end - a layer of width [R]. containing all needed subpool max averages. Finally, then, these values are aggregated according to ,3.
Our code is written in three stages: (1) compute base network consisting of the linear layers implied by Equation 3 then (2) append the subpool averages and their attendant memory neurons, and finally (3) aggregate the penultimate layer value with the coefficients. One helpful trick to developing this logic is to leave each step above as consecutive linear layers, then once everything is complete, to fuse them all together.
This approach perhaps does not result in the smallest possible feedforward network that could implement an R-estimator but it is relatively simple to code, fast to run, and the architecture is very descriptive of the logic the network implements. It scems unlikely that a large improvement on this general scheme is possible, though do not attempt prove this speculation.
G Additional experiments
In this section, we repeat Figure 2 for configurations different than the one described in |subsection 5.1 in exactly one way, described in the caption. Across Figure Figure 9 Figure 10, Figure 11 Figure 12 and Figure 13 the basic pattern of quickly falling error that levels around μ for all three models is repeated.
29

---

Published in Transactions on Machine Learning Research (09/2023)
0.30
[0,1,d-1]
R (0,1, 2. 1}
0.25
R 10,1, 2, 1}
ERR(R, (L)
0.20
0.15
0.10
.50.75
Figure 8: Figure with Kaiming initialization for weights and small positive constant for bias.
0.30
R 10,1,d -
R = (0, 2d
0.25
R = (0.1,... d - 1}
BRR (R, 1))
0.20
0.15
0.10
.50.75
Figure 9: Figure 2
with Xavier initialization for weights and small positive constant for bias.
R 10,1,d-1}
0.3
(0,1,d-2,d-1}
2, 2,d-1)
ERR (R, (L)
ERR(RRI)
0.2
0.1
P
Figure 10:
Figure 2
with Loo criterion replaced with La criterion.
30

---

Published in Transactions on Machine Learning Research (09/2023)
(0,1,--1] 1}
0.25
R (0,1, 2, 1}
R 10,1, 2, d 1}
ERR( (ER(R, (L)
0.20
0.15
0.10
.50.75
Figure 11: Figure with Adam optimizer replaced with AdamW optimizer (PyTorch default parameters).
R 10,1,d 1
0.25
R 10,1, - 2, 1}
R = (0.1,... d d - 1}
ERR (R. 1))
0.20
0.15
0.10
.50.75
3
Figure 12:
Figure 2
with pseudorandom uniform data replaced with Sobol sequence.
R 10,1,d-1}
0.3
(0,1,d-2,d-1)
2, 2,d-1}
ERR (R, (t)
(RR(RRH)
0.2
0.1
P
Figure 13: Figure 2 with pseudorandom uniform data replaced with Dirichlet (1,..., 1) data.
31

---

Published in Transactions on Machine Learning Research (09/2023)
Max pool (4.67m)
80
Conv-Targe (10.24m)
Robust Accuracy
Conv-Small (5.27m)
Conv-Strided (4.93m)
40
20
0.0
0.1 0.2 0.3 0.4 0.5
1.0
1.2 1.4 1.5
of perturbations
Figure 14: Effect of perturbations with Lx 6 on the accuracy of the ResNet model variants on the CIFARIO dataset. Mean accuracy and 1.96 standard deviation over the course of three runs are depicted. The legend indicates the number of parameters of each model in parentheses. The models omitting max pool pay a price in either (robust) accuracy or model complexity (in terms of parameters).
H Analysis
We have strictly looked at the accuracy implications of approximating the function in isolation. In this short and speculative section, examine briefly the practical takcaways for adversarial robustness. The com
code to implement this analysis is at http://tttbb.ccmmmmmmmmaaaaaaapp
H.1 Adversarial robustness
Our hypothesis is that pooling be robust than strided convolution and ReLU nonlincarity, since genuine max pooling admits only single direction along which features can change the max. ReLU, by contrast, can be moved with only low correlation changes, and random perturbation will in general change the output.
Our experiments corroborate this intuition; omitting max pooling results in lower robust accuracy in several different model classes, ranging from simple Convolutional Neural Networks to ResNets. Our experimental approach is adversarially attack models with and without max pooling, We use the Fast Gradient Sign Method by Goodfellow al. (2015). Specifically, starting from model incorporating max pool layers, we replace them with strided convolution + ReLU. We examine four different models and report the robust accuracy in Figure 14 on the CIFARIO dataset (Krizhevsky (2009)). The Max pool model is from Page (2018) and includes four max pool layers. The baselines make the following modifications: Conv-Small and Conv-Large replace the max pool layers with a convolutional one, with kernel size one and three, respectively. The Conv-Strided model uses a strided convolution in lieu of the max pool layer and the convolution that precedes it.
We performed the computation experiments presented here can be done in less than seven Tesla. V100 days. All software and data are standard academic tools and present no licensing issues.
internal computation cluster of Tesla V100-SXM2-32GB GPUs. All
The experiments are developed in PyTorch Paszke et al. 2017 and PyTorch Lightning Falcon 2019 with the help of the foolbox Rauber et al. (2017) library for the adversarial attack. We use RosNot variant in our experiments Page (2018). We use the publicly available datasets MNIST (LeCun al. 2010 and CIFAR10 Krizhevsky (2009).
32

---

Published in Transactions on Machine Learning Research (09/2023)
100
Maxpool (259k)
Conv (305k)
80
Robust Accuracy
60
40
20
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
5.0
7,5
10.0
of perturbations
Figure 15: Effect of perturbations with &oo S e on the accuracy of the LeNet model variants on the MNIST dataset.
The experimental results showcase a tradeoff between model complexity (in terms of number of parameters) and robust accuracy. The Max pool model is more adversarially robust than the baselines Conv-Small and Conv-Strided. This effect is further highlighted for larger perturbations An exception to this trend lies in the Conv-Large model which is able to match the robust accuracy of the Max pool model, but requires more than twice as many parameters.
Experimental Details
In each experiment, we create a model incorporating max pool layer(s). Then, the network is modified by replacing each max pool layer with a trainable variant, ensuring that the output of the original layer and the modified one have the same shape.
The legend of each figure presents the name of the model variant well as the number of trainable parameters in parentheses. The width of the lines is proportional to the number of parameters in the model. The max pool model variant is always depicted in blue.
1.1 Experimental configurations
LeNet experiment. on MNIST We train two convolutional neural networks (CNNs) on the digit classi- fication dataset MNIST. The results are shown Figure 15
The first model, in blue, has 259 106 trainable parameters and consists of two convolutional layers, with 32 and 64 channels. Their kernel size is equal to five. Both layers succeeded by two-dimensional max pool with kernel size, stride and padding equal to three, two and one, respectively. The network is completed with two fully-connected layers of 1024 and 200 neurons, leading lo the output of len logits. The second model, in red, has 305 282 trainable parameters and has the same structure as the previous model. However, the max pool layers are replacod by a convolutional layer with the same number of input channels as the output of the preceding convolutional layer, hence the increase in parameters. Both models are trained for ten epochs of Stochastic Gradient Descent with learning rate and momentum equal to 0.01 and 0.9, respectively.
33

---

Published in Transactions on Machine Learning Research (09/2023)
80
Maxpool (232k)
70
Conv-Small (253k)
Robust Accuracy
Conv-Strided (232k)
60
50
40
30
20
10
0.0
0-
1.
1.5
of perturbations
Figure 16: Effect of perturbations with to S c on the accuracy of the LeNet model variants on the CIFAR10 dataset.
LeNet experiment CIFAR10 A similar experiment is performed on the more challenging CIFAR10 dataset. The results are shown in Figure 16
The max pool model, in blue, has 232 162 parameters and consists of three convolutional layers of 32, 64, 128 channels, respectively. Again, each of these layers succeeded by max pool module identical to the MNIST experiment. The convolutional variant, depicted in green, has 253 890 parameters has a similar modification as before, i.e. the max pool layer replaced by a convolutional one with kernel size, stride and padding identical the corresponding max pool layer. Finally, the strided variant, in gray, has the same number of parameters as the original max pool model. In this case, we replace the block of convolution and max pool with strided convolution of stride equal to two. Hence, this modification does not incur an increase in number of parameters, while maintaining the same output shape at all intermediate steps. The models are trained for 100 epochs of SGD with learning rate and momentum equal to 0.01 and 0.9 respectively. The learning rate is decayed by a parameter = 10 in epochs 50, 70 and 90. The batch size is 128.
ResNet experiment on CIFAR10 We use the ResNet variant proposed in Page (0018) This model consists of preparatory whitening layer, three residual blocks and classifier layer. First, the preparatory layer has two convolutions and Ghost Batch Normalization Hoffer et al. (2017). The three residual blocks have identical structure, with the exception of the number of channels in the convolutional layer; the channels are doubled with each layer, from 64 to 128 to 256. Each of these layers consists of two blocks: the first one has a convolutional layer, a max pool layer with kernel size and stride equal to two and Ghost Batch Norm, while the second block employs residual connection with similar structure the previous block modulo the max pool. Finally, the classifier layer comprised of max pooling layer of kernel size and stride equal to four and fully connected layer resulting in ten outputs.
Overall, the Maxpool model, in blue, has four maxpooling layers and 4 666 265 parameters. The large convo- lutional model, depicted in red, has 10 238 233 parameters and replaces the Maxpool layers by convolutional ones with the same kernel size, stride and padding. The small convolution variant, depicted in green, has 273 881 parameters and the kernel size is set to one for all maxpooling replacements. Finally, the strided model, depicted in gray, has 4928 921 parameters and. for each residual layer, the pair of convolution and maxpooling replaced by strided convolution, while the maxpooling layer preceding the fully connected
34

---

Published in Transactions on Machine Learning Research (09/2023)
one is replaced with convolutional layer of kernel size equal to one. The stride remains equal to four, as in the corresponding maxpooling layer.
The models are trained for 50 epochs using float 16 precision. The learning rate follows a piecewise linear schedule; starting at zero the learning rate linearly increases to 0.4 until the fifth epoch and then linearly decays zero until the final epoch.
1.2 Analysis
Our objective lies in showing the superior adversarial robustness of models incorporating max pooling. each experiment, we use a max pooling model, drawn from widely used neural networks such as LeNet and ResNet. We modify the original model produce comparisons. Specifically, the modifications simply replace the maxpooling layer with convolutional layer, the pair of convolutional layer and maxpooling (which traditionally come succession) with strided convolution. In both cases, the new layer produces outputs of the samne shape as the original layer, lending itself to an one-to-one comparison in terms of performance on (robust) accuracy. It is important to note that the first modification results in an increase in the number of trainable paramcters. Subsequently, we perform an adversarial attack, FGSM in our case, to illuminate the adversarial robustness properties of each model. A common theme of all experiments is that the exclusion of the maxpooling layer results in a tradeoff between (robust) accuracy and model complexity.
First, in the MNIST experiment both variants reach similar levels of performance the clean accuracy (c=0), the max pool variant achieves 99.19 + 0.06 while the convolutional model 98.54 + 0.14. This is not surprising given the low difficulty of the dataset. Nevertheless, the model with maxpooling is characterized by strictly higher adversarial robustness, since the difference in performance heightens for larger In the CIFAR10 experiment, the observations are similar in nature; replacing maxpooling with a trainable layer renders the model more susceptible to adversarial perturbations. However, the modified models do not exhibit the same level of clean accuracy, despite the increase model complexity. Specifically, the mean clean accuracies (over 3 runs with different random seeds) of the max pool, small convolutional and strided convolution models are 82.89 0.08%, 00.9440.2661 and 80.45 + 0.66%, respectively. It is important to note that the LeNet architecture does not achieve state-of-thc-art results on any of the model variants presented. However, it serves as a direct comparison with the previous experiment. Finally, the ResNet experiment perhaps illuminates the tradeoff more clearly. Figure 14 (see main text) presents a dichotomy due to the exclusion the max pool layer; the practitioner should choose between model complexity (measured in number of trainable paramcters and, by extension, training and inference times) and (robust) accuracy. The large convolution model achieves a clean accuracy of 93.37 compared to -. of the original model and is able to match its robust accuracy for different e, while using more than double the parameters. The other two variants, however, have lowest clean accuracies (89.22 + 0.09% for the strided model and 87.46 + 0.99% for the small convolutional) and present faster deterioration in adversarial robustness.
1.3 Detailed Results
For completeness, present the experimental results in tabular form. The experiments were repeated three times (with different random seeds) and the mean + standard deviation is reported.
35

---

Published in Transactions on Machine Learning Research (09/2023)
Table 2: Detailed results on MNIST.
Maxpool
Conv
0.000
99.19 + 0.06
98.54 + 0.14
0.001
99.19 + 0.06
98.54 + 0.14
0.002
99.19 = 0.06
98.54 = 0.14
0.003
99.19 0.06
98.54 = 0.14
0.010
99.19 + 0.06
98.54 + 0.14
0.100
99.18 = 0.05
98.50
0.300
99.14 + 0.04
98.45
0.500
99.00 = 0.07
0 0.11
1.000
98.34 + 0..9
97.72 0.07
1.200
97.16 + 0.08
9 0.15
1.400
95.14 0.38
91.86 0.97
1.600
92.59 0.72
86.74
1.800
89.16 1.05
3.11
2.000
84.90 1.46
71.07
2.200
8..44
4.222
2.500
$1.20
4..91
3.000
75.95
3.999
3.500
68.58 2.69
45.65 +.322
5.000
27.67 2.71
15.02 0.46
7.500
8.24 2.22
6.98 1.31
10.000
8.24 2.22
6.98 1.31
Table 3: Detailed results on CIFAR10 with LeNet.
Maxpool
Conv-small
Strided
0.000
82.89 + 0.09
80.94 0.27
80.45 + 0.67
0.001
82.42 + 0.11
80.51 + 0.19
80.08 + 0.60
0.002
82.00 + 0.08
80.09 + 0.20
79.70 + 0.58
0.003
81.56 + 0.13
79.68 0.21
79.31 = 0.66
0.010
78.37 + 0.03
7 0.17
76.64 0.30
0.100
45.56 0.54
45.16
46.02 0.30
0.300
22.64
2.61
19.51 1.61
0.500
18.00
1.605
12.39 1.96
1.000
12.48 + 1.08
8.44
1.200
10.97 + 0.90
9.50 0.90
8.28 0.21
1.400
10.10 + 0.81
9.15 9.15 0.75
8.22 + 0.46
36

---

Published in Transactions on Machine Learning Research (09/202))
Table 4: Detailed results CIFAR10 with ResNet.
Maxpool
Conv-Large
Conv-Small
Strided
0.000
94.49 + 0.20
93.37 + 0.14
87.46 = 0.99
89.22 + 0.09
0.001
94.03 0.26
92.95 0.16
87.01 = 1.05
88.79 = 0.14
0.002
93.67 0.15
92.58 0.08
86.51 1.10
88.27 + 0.15
0.003
93.18 0.11
0..14
85.95 1.07
87.83 + 0.18
0.005
92.32 0.25
91.27
84.81 = 1.15
$6.72
0.007
91.46 = 0.24
9012
83.68 = 1.18
85.62 = 0.25
0.010
89.99 + 0.28
8807
82.00 = 1.13
83.89 + 0.29
0.100
62.00 + 0.27
62.66
49.58 = 3.48
54.93 0.38
0.200
53.24 + 0.64
54.24 0.38
39.39 + 4.68
45.05 + 0.42
0.300
48.00 1.05
48.43
33.79 = 4.35
38.89 + 0.59
0.400
43.13 0.96
4
29.71 4.56
34.27 + 0.17
0.500
38.03 1.30
4
26.06 3.60
29.49 + 0.31
1.000
16.06 + 1.20
15.96 1.56
13.61 1.22
14.24 0.68
1.200
11.94 + 0.93
11.88 0.53
11.20 = 0.95
11.53 0.59
1.400
10.02 + 0.69
9.93 0.34
9.81 0.82
9.90 + 0.83
1.500
9.76 + 0.61
9.75 0.22
9.46 0.77
9.67 0.77
37


Reviews:
[{"review_id": "ct162IyxVf", "reviewer": "Reviewer_Sqmz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The logic of this paper is clear, and the conclusions seem correct and reasonable.\n2. The topic is interesting to me.\n\nWeaknesses:\n1. The motivation is a little strange to me.\n2. The experiments are not so enough.", "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 studies the question: 1, Can max pooling be replaced by linear mappings with ReLU activations? 2, When would doing so give a different model? This paper introduces the subpool max functions to show the max function cannot be approximated by the linear combinations of subpool max functions. The analysis is also extended to wider neural networks by experiments. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I suggest that this paper can be improved by implementing experiments on real-world datasets. For example, showing the results of Figures 2 and 3 using MNIST and CIFAR-10 would be better.\n\n2. The experiments in Section 5.2 shows the error does not change much as the networks become wider. This is different from the conclusions from NTK. Some clarifications and discussions are needed here.\n\n3. From my understanding, the max-pooling function is still widely used in CNN-based neural networks. I feel it is not accurate to say modern networks have few max pooling functions. Also, supporting examples like ResNet, MobileNetV3 were at least four years ago, and I don't think they are that modern. I am wondering whether Transformers have this proposed trend of the max-pooling function. Some discussion is needed. ", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "y6RXh5h947", "reviewer": "Reviewer_SozV", "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": "The main strengths of the paper are the relatively simple and clean definitions and constructions. In particular I find the subpool analysis quite interesting, and it makes me wonder if there are other problems in deep learning theory which could be attacked by looking at statistics over subsets of neural activations.\n\nThe main weakness of the work is the relevance to the audience of TMLR. 'm not sure of the overall interest in characterizing the ability of ReLu networks to implement the max function on high-dimensional inputs. The work is self contained and thorough and I think would be valuable to anyone thinking about these issues. Some of the frameworks may be more broadly useful to the theory community.\n\nHowever, the results of section 5 seemed more confusing and of les relevance. One thing that was very unclear to me was whether or not the SGD trained models were approaching the wide network/NTK regime. In that case, it would be completely unsurprising that as width goes, the approximation performance remains roughly constant; indeed, this has been observed at widths as small as ~ 500 in certain problems. It is definitely impossible to learn the max function in that regime, at least without resorting to exponentially many samples. It also is not very clear to me what to think about plots for a fixed, small number of maxed elements d - in practice one might care about larger d, or what happens as d increases.\n\nMore generally, the max function is usually a \"means to an end\"; namely getting good performance in, say, a supervised learning setting. In this case, it is not clear what approximation metric is actually relevant. It could be that the max doesn't need to be approximated well (or indeed, may not be needed at all!). This in my mind reduces the motivation/relevance, as in the case of max-pooling the max was chosen more as a useful tool rather than the end and of itself.\n\nAnother issue in section 5 is that the \"confidence intervals\" go almost all the way to 0 in some cases - in other words, the variability of the losses is as large as their typical values. It's possible that with some sort of hyperparameter tuning or cross validation/early stopping, the losses could be dramatically lowered in those cases; these types of procedures are common in normal machine learning and may better characterize the relationship between the exact solutions and the ones found by SGD.\n\nFor now I have marked \"no\" for relevance to the audience of TMLR, but I am willing to change my mind on this. I look forward to a productive discussion with the authors and other reviewers on this point.\n\nIn addition, I have marked \"no\" for claims and evidence due to it being somewhat hard to parse some of the results. I have some requested changes which I believe are tractable and should flip that to a \"yes\".\n\nUpdate: after reading the other reviews and discussion with the authors, I have flipped both relevance and claims and evidence to yes. However I still strongly suggest that the authors give more intuition for the proof of theorem 5 in the main text.", "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 focuses on the question of how well the max function can be approximated by feedforward ReLu networks. The work claims to draw inspiration from the fact that max pooling used to be prevalent in multilayered CNNs on image tasks, but have now given way to only a single pooling layer at the end.\n\nThe authors first go through a series of basic constructions showing that as the number of elements to be maxed over increases, constructing a max function with feedforward ReLus requires deeper networks (both for efficiency but also to correctly implement the functions). They then perform an analysis about how well the true max is approximated with subpool maxes - maxes over subsets of the data. They characterize the error generated from subpools of different sizes, and show that the worst case error is achieved over a non-trivial volume of space with inputs on the hypercube.\n\nFinally, the authors study numerically how SGD solutions compare to approximations from subpool maxes. They show that even at widths larger than those required by optimal subpool max approximations (constructed using an algorithm derived by the authors), ReLu networks trained with SGD don't improve their approximation with width and remain far from the true max function.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In section 4, Theorem 5 seems to be more interesting/relevant to me than theorem 4, especially given that some of the results of theorem 4 (particularly, equations 5, 6, and 10) can be derived fairly simply even without the definitions and framework presented by the authors. The proof of theorem 5 is buried in the appendices and follows from a long string of other theorems. I think that it is important to do the following:\n* Expand the discussion of the theorem, and why it holds. This will bring both greater clarity to the question of the \"typical\" approximation error, and is a much more relevant to the readership of TMLR.\n* Better signpost/lay out the groundwork for proving theorem 5 in the appendix, before going through all the related theorems. As it currently reads, theorem 5 appears very quickly from the rest of the theorems, which seems nice but makes it hard to read those appendices and to understand _why_ the results are true. The why is important in this case because readers may wish to use similar techniques to study other function approximation problems.\n\nI did not understand the argument in Section 5/Appendix E that the algorithm is efficient. It was claimed that the algorithm runs in $\\binom{d}{r}$ time which, for $r=d/2$, is exponential in $d$ This seems very slow. Some more detailed discussion on this point would be greatly helpful. The algorithm should be described in more detail in the main text, as it builds on some of the previous results.\n\nSome discussion about how max is/could be implemented with other non-linearities, particularly doubly saturated ones like tanh, and attention like blocks would be greatly helpful in positioning this work appropriately in the literature.\n\nPlease make sure that the final version has proper hyperlinking to the Appendix; I recognize that this version did not as the main text and appendix were in separate files.\n\nAll of the plots need properly labelled axes so that readers can get some understanding semi-independently from the captions.\n\nFor the analysis in Section 5, some discussion/experiments on whether or not the networks are nearing the NTK/kernel regime for larger mu values would be helpful for the discussion.\n\nI believe that \"confidence interval\" is the wrong way to describe the variability Figures 2 and 3, as it is true variability in a learning procedure (SGD). Indeed, over 10 almost certainly non-Gaussian datapoints, the relationship between sample standard deviation and the cdf does not hold (aka z-scores are not the correct framework here). I would recommend plotting the standard deviation itself, or the min and max values over the 10 seeds.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yBF77p9RDv", "reviewer": "Reviewer_W2yX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nWell written.\n\nMain Weaknesses:\n\n1. It is not clear to me that the max pooling being a function that cannot be easily approximated is indicative that it is a useful operation in modeling real-world problems in machine learning. I believe that this can be tested experimentally pretty easily, by swapping out different pooling operations, as is done in [1]. I would appreciate more motivation to support this line of work.\n\n2. It is not clear to me that the experimental evidence clearly supports the claims. Though the authors aim to show that no significant improvements in error rates are achieved by increasing the parameter mu, there can be several other contending hypotheses that explain this result, for example, failed optimization, bad architecture design, data generation problems, etc.  \n\n[1] Williams, T. and Li, R., 2018, February. Wavelet pooling for convolutional neural networks. In International conference on learning representations.\n\n\n", "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 provides a detailed theoretical analysis of the characteristics of max pooling in deep neural networks and investigates possible approximations of it, such as using compositions of relu activations. They introduce a more general class of approximations, subpool max averages, which take the max over subsets of the features and average them together. They provide analysis that the approximation they propose, cannot fully approximate the max pooling operation, however, it can get exponentially close. They provide some experimental evidence to find their claims, mainly that the max pool operation cannot easily be substituted by other operations.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Following point 1 above, I believe that the approach of providing experimental evidence should be reversed, rather than showing that there is no statistical significance to rule out the hypothesis (that increasing mu could improve error rates), it will be better to show that there is statistical significance of the opposite claim.  I am not sure about what setup should be taken here, but I believe that the results should show some statistical significance. Either way, I do not think that the current experimental evidence is sufficient in this manner, please provide perhaps a different experiment with statistically significant results, to support the claims of this paper.\n\n\nPlease provide more details on the experiment setup, the model architecture specifications, a diagram, and preferably code with data. In its current form, it is a bit difficult to understand the experimental setup. If you decide to run a different experiment as mentioned above, please add more details there.\n", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WzWG9cpXQk", "reviewer": "Reviewer_ujds", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nS1. The paper theoretically analyses max-pooling, which has been receiving limited attention. The work also brings up the valuable point that max-pooling is often omitted from modern CNNs as an additional motivation for studying how important max-pooling is.\n\nS2. The paper obtains new precise error bounds for the approximation of max-pooling with the composition of ReLUs and linear operations, which have not appeared before in the most closely related recent work by Hertrich et al. (2021). \n\nS3. Generally, the theoretical part of the paper was fairly easy to follow. I have looked through the derivations, and they appear to be correct. (I have not checked the details in Appendix too closely.) I also appreciated the proof sketches and explanations of several expressions in words.\n\n**Weaknesses**\n\nW1. The Related work section needs to mention previous works on the maxout units for completeness. \n\nMax-pooling is closely related to maxout units [1], which also take the maximum of several inputs. Hence, results on the maxout are closely related to the max-pooling analysis, and while max-pooling has been investigated very little, maxout has received slightly more attention. I make more detailed suggestions below in the Requested changes in item C1.\n\n[1] Goodfellow, Ian, et al. \"Maxout networks.\" International conference on machine learning. PMLR, 2013.\n\nW2. The paper can benefit greatly from an explanation or an intuition of how deep and wide a ReLU network has to be to obtain approximation errors specified in Theorem 4. \n\nThe effects of the network width and depth are usually of interest in the works on network expressivity, including, for instance, Serra et al. (2018), Arora et al. (2018), Bartlett et al. (2019), and Hanin \\& Rolnick (2019) mentioned in the paper, and would make the comparison of ReLU and max-pooling expressivity more fine-grained. It is not entirely clear to me if this is possible with the results in the paper, but then a clear statement about it, for instance, in the Conclusion, would add to the clarity. I could not find a statement like this in the manuscript, but if it is already present somewhere, then making it more prominent would be valuable.\n\n**Conclusion**\n\nOverall, the paper derives new, precise error bounds for the approximation of max-pooling with ReLU networks. The presentation is mostly clear, and the experiments, though simple, support the conclusions of the article. I believe understanding the exact effect of elements of the network architecture, such as max-pooling, is a valuable question to study. My main concerns are the incomplete review of related work and the absence of a statement quantifying in some way how deep and wide a ReLU network has to be to attain the errors appearing in the results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper aims to analyze how valuable max-pooling is for a network architecture and asks how well max-pooling can be approximated by a ReLU network. The work introduces a function class of subpool max averages $M_d(R)$ and uses it to prove that the error when approximating a maximum of $d$ inputs using linear combinations of maximums of $ < d$ inputs is $O(1 / 2^d)$. Based on this, it is concluded that there are cases when max-pooling is strictly more expressive than a ReLU approximation. Further, the paper presents experiments confirming that increasing the width of a ReLU network does not reduce the approximation error.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Crucial**\n\nC1. Add the discussion around maxout networks.\n\nI suggest adding information about maxout networks to the Related work section to fit the results into the previous literature properly. I propose the following works, starting with [1], which introduces maxout units. Then expressivity of maxout networks in terms of the number of linear regions of maxout networks was considered in [2, 3, 4], with tight bounds being derived in [6]. Further, similarly to work by Hanin \\& Rolnick (2019) for ReLUs, which is mentioned in the Related works section of the paper, the expected complexity of maxout networks was studied in [5, 7], with [7] mentioning max-pooling but not providing results specific to it.\n\nC2. Add a discussion of how deep and wide a ReLU network has to be to attain the errors in Theorem 4 or a clear statement that it is impossible with the suggested framework.\n\n**Minor**\n\nBelow I outline several small issues in the presentation that I found somewhat confusing while reading and that would be nice to address.\n\nC3. More explanation around the meaning of RELERR and why considering it is meaningful would be helpful. The paper states, \"This measure isolates some of the difficulties that a standard stochastic gradient descent (SGD) procedure might have in modelling max pooling operations.\" This statement is broad, and it needs to be clarified what kind of difficulties it refers to. Expanding on it and maybe providing examples of what kind of difficulties can be isolated this way would aid understanding.\n\nC4. I have found the term \"purely feedforward ReLU networks\" somewhat unusual. As far as I understand, the paper uses networks that are usually referred to as \"feedforward fully-connected networks.\" If my interpretation is correct, I suggest omitting the confusing term and stating equation (11) earlier in the paper, where currently, \"purely feedforward ReLU networks\" are defined.\n\nC5. The name \"Features\" for one of the columns in Table 1 was confusing since it is unclear what is meant by stating that $M_d(R)$ is a feature. I suggest renaming it.\n\nC6. Figure 4 would benefit from clearly writing out what each axis represents.\n\nC7. I noticed several typos. Specifically,\n\n- Second paragraph from the bottom of page 4: \"the J1-subset max but simpler ...\" --> \"J1-subset max is simpler ...\".\n\n- Last paragraph on page 4. $\\binom{r}{d}$ --> $\\binom{d}{r}$.\n\n- The last sentence in footnote 2 seems to be unfinished. It is unclear otherwise, on what does $G_d(R, \\mu)$ impose no low-rank structure.\n\n[1] Goodfellow, Ian, et al. \"Maxout networks.\" International conference on machine learning. PMLR, 2013.\n\n[2] Pascanu, Razvan, Guido Montufar, and Yoshua Bengio. \"On the number of response regions of deep feed forward networks with piece-wise linear activations.\" arXiv preprint arXiv:1312.6098 (2013).\n\n[3] Montufar, Guido F., et al. \"On the number of linear regions of deep neural networks.\" Advances in neural information processing systems 27 (2014).\n\n[4] Serra, Thiago, Christian Tjandraatmadja, and Srikumar Ramalingam. \"Bounding and counting linear regions of deep neural networks.\" International Conference on Machine Learning. PMLR, 2018.\n\n[5] Tseran, Hanna, and Guido F. Montufar. \"On the expected complexity of maxout networks.\" Advances in Neural Information Processing Systems 34 (2021): 28995-29008.\n\n[6] Montúfar, Guido, Yue Ren, and Leon Zhang. \"Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums.\" SIAM Journal on Applied Algebra and Geometry 6.4 (2022): 618-649.\n\n[7] Tseran, Hanna, and Guido Montúfar. \"Expected Gradients of Maxout Networks and Consequences to Parameter Initialization.\" arXiv preprint arXiv:2301.06956 (2023).", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper makes a useful contribution by analyzing max-pooling, and the results should be interesting to the deep learning community. 

The paper was reviewed by four reviewers. Initially the reviewers were concerned about whether max-pooling is necessary regardless of whether it can be approximated well by ReLU networks. The reviewers also pointed out missing references such as maxout network. After extensive discussions, all four reviewers were positive. One reviewer hoped to see theorem 5 referenced more in the main text of the revision.
Decision: Accept (poster)