📚TheoryIntermediate

Depth vs Width Tradeoffs

Key Points

•
Depth adds compositional power: stacking layers lets neural networks represent functions with many repeated patterns using far fewer neurons than a single wide layer.
•
Shallow (very wide) ReLU networks can approximate any continuous function, but they may need exponentially many units for certain patterns, while deep networks need only polynomially many.
•
For ReLU networks, the number of linear regions a network can create grows roughly multiplicatively with depth and only polynomially with width.
•
Telgarsky’s triangle-function construction shows a depth-L network in 1D can create about 2^L oscillations; a single hidden layer would need about 2^L neurons to match.
•
Formal bounds (e.g., Montúfar) connect layer widths and input dimension to lower/upper bounds on the number of linear regions (a proxy for expressivity).
•
Depth-vs-width tradeoffs matter in practice because deep models often achieve the same accuracy with fewer parameters and better inductive bias for hierarchical data.
•
Universal approximation does not contradict depth efficiency: shallow nets can represent the same function, but potentially at an exponential cost in width.
•
When designing models, match the function’s structure: use depth for compositional, hierarchical patterns; use width to increase capacity within a layer.

Prerequisites

→Feedforward neural networks (MLPs) — Understanding layers, activations, and dense connections is essential to define depth and width.
→ReLU activation and piecewise-linear functions — Depth–width tradeoffs are often analyzed for ReLU nets via their linear regions.
→Big-O notation — Complexity and parameter-scaling statements use asymptotic notation like O(·), \Theta(·), and \Omega(·).
→Basic combinatorics (binomial coefficients) — Linear-region bounds rely on sums of binomial coefficients.
→Function composition — Depth leverages repeated composition; examples like Telgarsky’s triangle map depend on it.
→Matrix–vector multiplication — Inference cost per layer is based on dense linear algebra operations.
→Logarithms and exponentials — We compare exponential vs polynomial growth and use log-space to avoid numerical overflow.
→Approximation vs exact representation — Depth separations are typically about approximation within a tolerance, not exact equality.
→Parameter counting in neural nets — Fair comparisons demand matching or accounting for total parameters.
→Numerical stability basics — Computing combinatorial bounds safely requires log-sum-exp and gamma functions.

Detailed Explanation

Tap terms for definitions

01Overview

Hook → Why do modern models stack many layers instead of using one giant layer? Because depth lets networks reuse and compose features, achieving the same function with far fewer neurons. Concept → The depth vs width tradeoff studies how stacking layers (depth) compares with simply adding more neurons within a single layer (width) for representing functions. In ReLU networks, depth creates piecewise-linear functions whose number of linear regions grows roughly multiplicatively with each layer, while width increases regions more additively/polynomially. Example → In 1D, a carefully designed depth-L ReLU network can create about 2^L alternating up-down oscillations (folds). A single hidden layer would need on the order of one neuron per fold, i.e., ~2^L neurons, to match that behavior. Thus, depth often yields exponential efficiency compared to width.

02Intuition & Analogies

Hook → Think of making origami folds in paper. Each fold doubles the number of sections. Concept → Depth is like performing folds one after another; each layer bends the function created by the previous layer, multiplying structure. Width is like trying to make all the creases at once with a single complex template; it can work, but building many separate creases in one step can be far more cumbersome. Example → Suppose you want a zig-zag line with 64 peaks between x=0 and x=1. If you build it in one shot (one hidden layer), you need roughly one hinge per peak—dozens of hinges (neurons). If you instead compose a simple three-hinge shape with itself 6 times (a 6-layer network), each composition doubles the number of peaks: 2, 4, 8, …, 64. You reused the same simple building block repeatedly, which is parameter-efficient. This is exactly how deep networks work well on images and language: early layers detect edges or character n-grams, mid layers combine them into parts or phrases, and later layers combine parts into objects or meanings. Depth matches the hierarchical structure of many real-world tasks, so you get more power with fewer parameters than cramming everything into a single, extremely wide layer.

03Formal Definition

Hoo k \to T o

compare depth and width rigorously we count how many distinct pieces of behavior a network can exhibit.

C o n ce pt \to F or

ReLU networks, a quantitative proxy for expressivity is the maximum number of linear regions the network can induce in input space. Formally, consider a feedforward ReLU network with input dimension

n_{0}

, hidden layer widths

n_{1}

,…,

n_{L}

, and output dimension k. The network implements a piecewise-linear function f:

R^{n_{0}}

\to

R^{k}

. The number of affine linear regions of f grows with both depth L and widths

n_{ℓ}

. Montúfar (2014) proved lower bounds of the form N

\geq

\prod_{ℓ = 1}^{L}

\sum_{j = 0}^{m_{ℓ}}

(j n _{ℓ})

, where

m_{ℓ}

min

(

n_{0}

n_{1}

, …,

n_{ℓ}

). There are also upper bounds of a similar multiplicative form.

E x am pl e \to I n

1D (

n_{0} = 1

) with each hidden layer width at least 1, the lower bound simplifies to N

\geq

\prod_{ℓ = 1}^{L}

(

n_{ℓ}

+1). For a width-2 network with L layers, this gives at least 3^{L} linear regions in favorable settings; more careful constructions can yield 2^{L} oscillations in Telgarsky’s 1D example. These results formally capture that depth multiplies expressive capacity across layers, while width primarily scales the per-layer contribution.

04When to Use

Hook → When should you add layers vs add neurons per layer? Concept → Use depth when the target function is compositional or hierarchical—when you can describe it as smaller functions composed into larger ones. Use width when you need more parallel features at a given level of abstraction. Specific use cases: (1) Vision: edges → corners → parts → objects; CNN depth mirrors the hierarchy and is vastly more parameter-efficient than a single giant layer. (2) Language: characters/phonemes → morphemes → words → phrases; stacked layers naturally model composition. (3) Audio/time-series: local patterns composed into longer motifs; RNN/Transformer depth captures multiple temporal scales. (4) Algorithmic tasks (e.g., parity, carry in addition): depth matches multi-step logical pipelines and can reduce size from exponential to polynomial. Example → To approximate a 1D function with many alternating peaks (like a high-frequency sawtooth), a deep narrow ReLU net formed by composing a simple triangle map several times beats a shallow net that would require a separate neuron for almost every peak.

⚠️Common Mistakes

Hook → It’s easy to draw the wrong conclusion from the universal approximation theorem. Concept → Common pitfalls include: (1) Believing width alone is enough because a single hidden layer can approximate any function. The theorem ignores efficiency: the width needed may be exponential. (2) Equating more depth with better generalization. Depth improves representational power but can hurt trainability without proper initialization, normalization, or residual connections. (3) Ignoring input dimension in linear region bounds; the combinatorial growth depends strongly on n_{0}. (4) Confusing exact computation with approximation; many separations are about approximation within a tolerance (e.g., L_{1} or L_{\infty}). (5) Overlooking activation choice; results like Telgarsky’s rely on piecewise-linear ReLUs; sigmoids change the analysis. (6) Comparing parameter counts unfairly—e.g., matching width but not matching overall parameter budgets or compute. Example → A shallow net might match a deep net’s accuracy for a toy dataset if you let it be huge; but under a fixed parameter budget or latency constraint, the deep architecture typically wins because it reuses features layer-by-layer.

Key Formulas

Linear Regions (Single Layer Upper Bound)

N_{m a x} (1-layer ReLU, n_{0}, n_{1}) \leq j = 0 \sum n_{0} (j n _{1})

Explanation: A single hidden ReLU layer with width n1 over n0-dimensional inputs can create at most this many linear regions. It comes from counting regions induced by n1 hyperplanes in n0 dimensions.

Linear Regions (Multi-layer Upper Bound)

N_{m a x} (L-layer ReLU) \leq ℓ = 1 \prod L j = 0 \sum n_{0} (j n _{ℓ})

Explanation: An upper bound obtained by multiplying the per-layer arrangement bounds. This shows how depth multiplies the number of regions, while width contributes additively within each product term.

Montúfar Lower Bound

N_{m i n} (L-layer ReLU) \geq ℓ = 1 \prod L j = 0 \sum m_{ℓ} (j n _{ℓ}), m_{ℓ} = min (n_{0}, \dots, n_{ℓ})

Explanation: A constructive lower bound: there exist weights so that many regions are realized. If each layer width is at least n0, the bound simplifies and highlights exponential growth with depth.

Telgarsky Triangle Composition

regions (g^{\circ L}) = 2^{L} for a 1D triangle map g

Explanation: Composing a simple piecewise-linear triangle function with itself doubles the number of oscillations each time. This yields a depth separation: shallow nets need about one neuron per oscillation to match.

VC Dimension (Upper Bound)

VCdim (N_{W}) = O (W lo g W)

Explanation: For networks with piecewise-linear activations and W parameters, the VC dimension scales on the order of W log W. This links parameter count to sample complexity, independent of depth/width details.

Parameter Count (One Hidden Layer)

P_{1-hidden} = (n_{0} + 1) n_{1} + (n_{1} + 1) k

Explanation: The number of trainable parameters in a dense layer with n1 hidden units and k outputs: weights plus biases for $in p u t \to hi dd e n$ and $hi dd e n \to o u tp u t$ . This helps compare width vs depth under a parameter budget.

Dense Inference Cost

T_{inference} (x) = ℓ = 1 \sum L O (n_{ℓ - 1} n_{ℓ})

Explanation: The time to evaluate a dense ReLU network scales with the matrix multiplies per layer. For fixed parameter budgets, distributing parameters across more layers changes constant factors but not this sum.

Asymptotic Growth with Uniform Width

ℓ = 1 \prod L j = 0 \sum n_{0} (j n) \approx Θ (n^{n_{0} L}) (for n \geq n_{0})

Explanation: If each layer has the same width n and $n \geq n 0$ , the product of binomial sums grows like $n^{n 0 L}$ . This emphasizes multiplicative growth with depth when input dimension is fixed.

Depth Separation (Informal)

\exists f_{k} : f_{k} computed by depth 2 k with poly (k) units, but any depth- O (1) net needs Ω (e^{k}) units to ε -approximate

Explanation: A qualitative statement (from Telgarsky-like results): deeper networks can compute certain functions with polynomial size, whereas any bounded-depth alternative requires exponentially many units to approximate.

Complexity Analysis

There are two complementary notions of complexity here: computational and representational. Computationally, evaluating a dense ReLU network on one input costs

T_{i} n f ere n ce

(x) =

\sum_{ℓ = 1}^{L}

n_{ℓ - 1}

n_{ℓ}

) operations (matrix–vector products plus ReLUs), and memory for parameters is O(∑

n_{ℓ - 1}

n_{ℓ}

). For a fixed total parameter budget W, distributing parameters across more layers typically keeps the same big-O arithmetic cost, although constants and parallelism differ. Representationally, depth changes how efficiently functions can be expressed. For ReLU networks, the number of linear regions (a proxy for expressivity) scales roughly multiplicatively across layers: upper bounds take the form

\prod_{ℓ}

∑_{

j=0}^{n0}

C(n_ℓ, j), and constructive lower bounds (Montúfar) use

\prod_{ℓ}

∑_{

j=0}^{m_ℓ}

C(n_ℓ, j) with m_ℓ = min(n0,…,n_ℓ). In 1D (n0=1), this implies at least

\prod_{ℓ}

(n_ℓ+1) regions, so even modest widths yield exponential growth in L. In contrast, for a single hidden layer, the number of regions grows only polynomially with width (∑ C(n1, j)), so matching a deep network’s 2^L oscillations may require width Ω(2^L). Sample complexity relates to parameter count rather than depth directly: for piecewise-linear nets the VC dimension is O(W log W), so having exponentially more units (to compensate for shallowness) can sharply increase data needs. Practically, depth offers parameter efficiency for compositional functions, but may introduce training challenges (e.g., vanishing gradients) unless mitigated by residual connections, normalization, and good initialization. Overall, under equal parameter/compute budgets, deeper architectures typically achieve higher expressivity per parameter due to compositional reuse.

Code Examples

Depth creates exponential oscillations: composing a 1D triangle map (Telgarsky-style)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // ReLU activation
5 static inline double relu(double x) { return x > 0.0 ? x : 0.0; }
6 
7 // Triangle map g: [0,1] -> [0,1], piecewise linear with one peak.
8 // g(x) = ReLU(x) - 2*ReLU(x - 0.5) + ReLU(x - 1)
9 // On [0,1], this produces an up-then-down triangle with one oscillation.
10 static inline double triangle(double x) {
11     return relu(x) - 2.0 * relu(x - 0.5) + relu(x - 1.0);
12 }
13 
14 // Compose g with itself L times: g^{\circ L}(x)
15 static double compose_triangle(double x, int L) {
16     double y = x;
17     for (int i = 0; i < L; ++i) {
18         // Keep x in [0,1] to align with the construction's intuition
19         // (the given triangle function is 0 outside [0,1]).
20         y = triangle(y);
21     }
22     return y;
23 }
24 
25 // Estimate the number of oscillations (peaks) by sampling and counting sign changes of the discrete derivative.
26 int estimate_oscillations(int L, int samples = 4096) {
27     vector<double> ys(samples);
28     for (int i = 0; i < samples; ++i) {
29         double x = (double)i / (samples - 1);
30         ys[i] = compose_triangle(x, L);
31     }
32     // Compute discrete derivative signs
33     int peaks = 0;
34     int last_sign = 0; // -1 down, +1 up
35     for (int i = 1; i < samples; ++i) {
36         double d = ys[i] - ys[i - 1];
37         int s = (d > 1e-12) ? 1 : (d < -1e-12) ? -1 : 0;
38         if (s != 0) {
39             if (last_sign == 1 && s == -1) peaks++; // turning from up to down
40             last_sign = s;
41         }
42     }
43     return peaks; // ~ 2^L - 1 turns for ideal construction
44 }
45 
46 int main() {
47     cout.setf(std::ios::fixed); cout << setprecision(6);
48     for (int L : {1, 2, 3, 4, 5, 6}) {
49         int peaks = estimate_oscillations(L);
50         cout << "L = " << L << ", estimated peaks ~ " << peaks << " (expected ~ " << (1<<L) << ")\n";
51     }
52     // Print a small sample for visualization
53     int L = 5; // depth
54     int samples = 33;
55     cout << "\nSample of g^{oL} for L=" << L << " on [0,1]:\n";
56     for (int i = 0; i < samples; ++i) {
57         double x = (double)i / (samples - 1);
58         cout << x << "," << compose_triangle(x, L) << "\n";
59     }
60     return 0;
61 }
62

We implement a simple 1D triangle (sawtooth-like) map using three ReLUs and compose it L times to simulate a deep, narrow network. Each composition roughly doubles the number of up–down oscillations (linear regions) on [0,1]. The program estimates oscillations by sampling and counting turning points and prints sample values for visualization. This demonstrates how depth creates exponentially many oscillations with only O(L) layers and O(1) width.

Time: O(L · S) to evaluate on S sample points (each evaluation applies L small layers).Space: O(S) to store samples (can be O(1) if streamed).

Shallow wide ReLU sawtooth using many hinges (1 hidden layer)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 static inline double relu(double x) { return x > 0.0 ? x : 0.0; }
5 
6 // Build a 1-hidden-layer ReLU network that approximates a W-peak sawtooth on [0,1].
7 // Construction: sum of shifted triangle bumps, each made by 3 ReLU terms.
8 // f_W(x) = sum_{k=0}^{W-1} [ ReLU(x - k/W) - 2*ReLU(x - (k+0.5)/W) + ReLU(x - (k+1)/W) ]
9 // Optionally scale to keep range in [0,1]. This needs 3W ReLU units in one hidden layer.
10 double shallow_sawtooth(double x, int W) {
11     double y = 0.0;
12     for (int k = 0; k < W; ++k) {
13         double a = (double)k / W;
14         double b = (double)k / W + 0.5 / W;
15         double c = (double)(k + 1) / W;
16         y += relu(x - a) - 2.0 * relu(x - b) + relu(x - c);
17     }
18     // Normalize amplitude roughly to [0,1]
19     return y; // can divide by max possible (which is 0.5) if desired
20 }
21 
22 int main() {
23     cout.setf(std::ios::fixed); cout << setprecision(6);
24     int W = 64; // number of peaks -> requires ~3W ReLUs in one hidden layer
25     int samples = 65;
26     cout << "Shallow 1-hidden-layer sawtooth with W=" << W << " peaks (3W ReLUs).\n";
27     for (int i = 0; i < samples; ++i) {
28         double x = (double)i / (samples - 1);
29         double y = shallow_sawtooth(x, W);
30         cout << x << "," << y << "\n";
31     }
32     return 0;
33 }
34

This code constructs a single-hidden-layer ReLU network that produces W oscillations on [0,1] by summing W local triangle bumps. The construction uses 3W ReLUs: three shifted hinges per bump. To match a deep network with L compositions (≈2^L oscillations), a shallow net needs W ≈ 2^L, demonstrating exponential width growth. This contrasts with the previous example, where depth L achieved the same effect with constant width and only O(L) layers.

Time: O(W · S) to evaluate on S sample points since each x uses 3W ReLU ops.Space: O(1) per evaluation; O(S) if storing outputs.

Compute linear-region bounds (Montúfar-style lower, multiplicative upper) for ReLU MLPs

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Log-sum-exp helper for numerical stability
5 long double log_sum_exp(const vector<long double>& logs) {
6     long double m = -numeric_limits<long double>::infinity();
7     for (auto v : logs) m = max(m, v);
8     long double s = 0.0L;
9     for (auto v : logs) s += expl(v - m);
10     return m + logl(s);
11 }
12 
13 // log binomial using lgamma
14 long double log_binom(int n, int k) {
15     if (k < 0 || k > n) return -numeric_limits<long double>::infinity();
16     return lgammal(n + 1.0L) - lgammal(k + 1.0L) - lgammal(n - k + 1.0L);
17 }
18 
19 // Compute log sum_{j=0}^{kmax} C(n, j)
20 long double log_sum_binom_prefix(int n, int kmax) {
21     kmax = min(kmax, n);
22     vector<long double> terms;
23     terms.reserve(kmax + 1);
24     for (int j = 0; j <= kmax; ++j) terms.push_back(log_binom(n, j));
25     return log_sum_exp(terms);
26 }
27 
28 struct Bounds { long double log_lower; long double log_upper; };
29 
30 // Given input dim n0 and hidden widths n[1..L], compute:
31 // Upper: prod_{l=1}^L sum_{j=0}^{n0} C(n_l, j)
32 // Lower (Montúfar): prod_{l=1}^L sum_{j=0}^{m_l} C(n_l, j), where m_l = min(n0, n1, ..., n_l)
33 Bounds region_bounds(int n0, const vector<int>& widths) {
34     int L = (int)widths.size();
35     long double log_upper = 0.0L, log_lower = 0.0L;
36     int m = n0;
37     for (int l = 0; l < L; ++l) {
38         int nl = widths[l];
39         // upper uses n0
40         log_upper += log_sum_binom_prefix(nl, n0);
41         // lower uses m_l = min(n0, n1, ..., n_l)
42         m = min(m, nl);
43         log_lower += log_sum_binom_prefix(nl, m);
44     }
45     return {log_lower, log_upper};
46 }
47 
48 int main() {
49     cout.setf(std::ios::fixed); cout << setprecision(6);
50     int n0 = 2; // input dimension
51     vector<int> wide = {64};              // shallow: one hidden layer of width 64
52     vector<int> deep = {8,8,8};           // deep: three layers width 8
53     auto B1 = region_bounds(n0, wide);
54     auto B2 = region_bounds(n0, deep);
55 
56     auto pr = [&](const string& name, Bounds B){
57         cout << name << ":\n";
58         cout << "  log lower bound  = " << (double)B.log_lower << "\n";
59         cout << "  log upper bound  = " << (double)B.log_upper << "\n";
60         cout << "  approx lower     = exp(log_lower) (may overflow if printed directly)\n";
61     };
62 
63     pr("Shallow (n0=2, width=[64])", B1);
64     pr("Deep    (n0=2, width=[8,8,8])", B2);
65 
66     // Note: Compare log-bounds to avoid overflow; higher logs mean more potential regions.
67     return 0;
68 }
69

This program reports multiplicative upper bounds and Montúfar-style lower bounds for the number of linear regions given input dimension and layer widths. It computes binomial-prefix sums in log-space to avoid overflow, then sums logs across layers (equivalent to multiplying counts). Comparing shallow vs deep architectures illustrates how depth multiplies region counts even when total parameters are similar.

Time: O(L · n0) evaluations of binomials per architecture if n0 is small; more precisely O(L · kmax) where kmax = min(n0, n_l).Space: O(1) besides small vectors for log-sums; overall O(n0) temporary memory.

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// ReLU activation
5	static inline double relu(double x) { return x > 0.0 ? x : 0.0; }
6
7	// Triangle map g: [0,1] -> [0,1], piecewise linear with one peak.
8	// g(x) = ReLU(x) - 2*ReLU(x - 0.5) + ReLU(x - 1)
9	// On [0,1], this produces an up-then-down triangle with one oscillation.
10	static inline double triangle(double x) {
11	return relu(x) - 2.0 * relu(x - 0.5) + relu(x - 1.0);
12	}
13
14	// Compose g with itself L times: g^{\circ L}(x)
15	static double compose_triangle(double x, int L) {
16	double y = x;
17	for (int i = 0; i < L; ++i) {
18	// Keep x in [0,1] to align with the construction's intuition
19	// (the given triangle function is 0 outside [0,1]).
20	y = triangle(y);
21	}
22	return y;
23	}
24
25	// Estimate the number of oscillations (peaks) by sampling and counting sign changes of the discrete derivative.
26	int estimate_oscillations(int L, int samples = 4096) {
27	vector<double> ys(samples);
28	for (int i = 0; i < samples; ++i) {
29	double x = (double)i / (samples - 1);
30	ys[i] = compose_triangle(x, L);
31	}
32	// Compute discrete derivative signs
33	int peaks = 0;
34	int last_sign = 0; // -1 down, +1 up
35	for (int i = 1; i < samples; ++i) {
36	double d = ys[i] - ys[i - 1];
37	int s = (d > 1e-12) ? 1 : (d < -1e-12) ? -1 : 0;
38	if (s != 0) {
39	if (last_sign == 1 && s == -1) peaks++; // turning from up to down
40	last_sign = s;
41	}
42	}
43	return peaks; // ~ 2^L - 1 turns for ideal construction
44	}
45
46	int main() {
47	cout.setf(std::ios::fixed); cout << setprecision(6);
48	for (int L : {1, 2, 3, 4, 5, 6}) {
49	int peaks = estimate_oscillations(L);
50	cout << "L = " << L << ", estimated peaks ~ " << peaks << " (expected ~ " << (1<<L) << ")\n";
51	}
52	// Print a small sample for visualization
53	int L = 5; // depth
54	int samples = 33;
55	cout << "\nSample of g^{oL} for L=" << L << " on [0,1]:\n";
56	for (int i = 0; i < samples; ++i) {
57	double x = (double)i / (samples - 1);
58	cout << x << "," << compose_triangle(x, L) << "\n";
59	}
60	return 0;
61	}
62

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Log-sum-exp helper for numerical stability
5	long double log_sum_exp(const vector<long double>& logs) {
6	long double m = -numeric_limits<long double>::infinity();
7	for (auto v : logs) m = max(m, v);
8	long double s = 0.0L;
9	for (auto v : logs) s += expl(v - m);
10	return m + logl(s);
11	}
12
13	// log binomial using lgamma
14	long double log_binom(int n, int k) {
15	if (k < 0 \|\| k > n) return -numeric_limits<long double>::infinity();
16	return lgammal(n + 1.0L) - lgammal(k + 1.0L) - lgammal(n - k + 1.0L);
17	}
18
19	// Compute log sum_{j=0}^{kmax} C(n, j)
20	long double log_sum_binom_prefix(int n, int kmax) {
21	kmax = min(kmax, n);
22	vector<long double> terms;
23	terms.reserve(kmax + 1);
24	for (int j = 0; j <= kmax; ++j) terms.push_back(log_binom(n, j));
25	return log_sum_exp(terms);
26	}
27
28	struct Bounds { long double log_lower; long double log_upper; };
29
30	// Given input dim n0 and hidden widths n[1..L], compute:
31	// Upper: prod_{l=1}^L sum_{j=0}^{n0} C(n_l, j)
32	// Lower (Montúfar): prod_{l=1}^L sum_{j=0}^{m_l} C(n_l, j), where m_l = min(n0, n1, ..., n_l)
33	Bounds region_bounds(int n0, const vector<int>& widths) {
34	int L = (int)widths.size();
35	long double log_upper = 0.0L, log_lower = 0.0L;
36	int m = n0;
37	for (int l = 0; l < L; ++l) {
38	int nl = widths[l];
39	// upper uses n0
40	log_upper += log_sum_binom_prefix(nl, n0);
41	// lower uses m_l = min(n0, n1, ..., n_l)
42	m = min(m, nl);
43	log_lower += log_sum_binom_prefix(nl, m);
44	}
45	return {log_lower, log_upper};
46	}
47
48	int main() {
49	cout.setf(std::ios::fixed); cout << setprecision(6);
50	int n0 = 2; // input dimension
51	vector<int> wide = {64}; // shallow: one hidden layer of width 64
52	vector<int> deep = {8,8,8}; // deep: three layers width 8
53	auto B1 = region_bounds(n0, wide);
54	auto B2 = region_bounds(n0, deep);
55
56	auto pr = [&](const string& name, Bounds B){
57	cout << name << ":\n";
58	cout << " log lower bound = " << (double)B.log_lower << "\n";
59	cout << " log upper bound = " << (double)B.log_upper << "\n";
60	cout << " approx lower = exp(log_lower) (may overflow if printed directly)\n";
61	};
62
63	pr("Shallow (n0=2, width=[64])", B1);
64	pr("Deep (n0=2, width=[8,8,8])", B2);
65
66	// Note: Compare log-bounds to avoid overflow; higher logs mean more potential regions.
67	return 0;
68	}
69