On Minimal Depth in Neural Networks

This paper introduces a geometric framework based on depth complexity to analyze ReLU networks, proving that while $\lceil \log_2(n+1)\rceil$ layers suffice for general continuous piecewise linear functions, Input Convex Neural Networks (ICNNs) lack a universal depth bound for representing all convex functions due to the unbounded depth growth of cyclic polytopes.

The Gist

Imagine you are trying to build a complex sculpture out of clay. In the world of Artificial Intelligence (specifically "Deep Learning"), neural networks are like machines that build these sculptures. The "sculpture" is a mathematical function that the computer uses to make decisions (like recognizing a cat in a photo).

This paper by Juan L. Valerdi is about figuring out how many layers of machinery (depth) you need to build a specific shape, and whether there's a limit to how complex a shape you can build with a fixed number of layers.

Here is the breakdown using simple analogies:

1. The Two Tools: The "Blob" and the "Stack"

To understand the paper, you need to know the two basic moves the machine can make to build shapes:

1. The Convex Hull (The "Blob"): Imagine taking a bunch of points and stretching a rubber band around them to make the tightest possible shape. This creates a "blob" (a convex shape).
2. The Minkowski Sum (The "Stack"): Imagine taking two shapes and sliding one over the other in every possible direction, then collecting all the new points they touch. It's like stamping a shape over another shape repeatedly.

The author defines "Depth" as the number of times you have to alternate between making a "Blob" and doing a "Stack" to create a final shape.

• Depth 0: Just a single dot.
• Depth 1: A "Stack" of lines (a shape that looks like a stretched-out diamond).
• Depth 2: A "Blob" made of Depth 1 shapes.

2. The Big Question: How Deep is Deep Enough?

For years, scientists have asked: "If I want to build ANY possible shape (function) that a computer can learn, how many layers of machinery do I need?"

• The Old Answer: A famous result said that if you have a shape with $n$ dimensions, you only need about $\log_2(n)$ layers. It was thought that no matter how weird the shape, you could always build it with a small, fixed number of layers.
• The Paper's Discovery: The author proves that this is true for standard neural networks, but false for a specific type called "Input Convex Neural Networks" (ICNNs).

3. The Twist: The "Cyclic Polytope" Monster

The paper introduces a specific family of shapes called Cyclic Polytopes.

• The Analogy: Imagine a standard pyramid (a simple shape). Now imagine a shape where every single point on the surface is connected to every other point. It's a hyper-complex, star-shaped object where the "skeleton" is fully connected.
• The Result: The author shows that for these specific shapes, as you add more and more points (vertices), the "depth" required to build them grows forever.
• The Metaphor: Think of building a house.
  • Standard Neural Networks: You can build any house, no matter how weird, using a ladder that is only 5 rungs high. You just rearrange the bricks differently.
  • ICNNs (The Restricted Network): These are like a robot that can only build houses using specific, rigid rules. The paper proves that for certain "weird" houses (Cyclic Polytopes), if you want to build a bigger version of it, you need a taller ladder. If you want a massive version, you need a ladder that goes into space. There is no "universal" ladder height that works for all sizes.

4. Why Does This Matter?

This isn't just about math; it's about limitations in AI.

• Standard Networks: They are very flexible. If you give them enough layers (even a small number), they can learn almost anything.
• Input Convex Networks (ICNNs): These are special networks used when we need the AI to behave in a strictly "logical" or "safe" way (like in economics or physics, where things can't go negative or break rules).
  • The paper warns us: You cannot force these safe networks to be both "super flexible" and "shallow" (simple).
  • If you want an ICNN to represent a very complex, safe function, you must make it deeper and deeper as the problem gets bigger. You can't just say, "I'll use 3 layers for everything."

Summary in a Nutshell

The paper builds a bridge between geometry (shapes) and computer science (neural networks).

1. It invents a way to measure the "complexity" of a shape by counting how many times you have to mix-and-match basic building blocks.
2. It proves that for standard AI, a small, fixed number of layers is enough to build any shape.
3. Crucially, it proves that for "Safe" AI (ICNNs), this is not true. Some shapes are so complex that you need an infinitely tall ladder to build them. If you try to build them with a short ladder, you simply can't do it.

The Takeaway: There is a sharp trade-off. If you want your AI to be "safe" and follow strict rules, you lose the ability to keep the system simple and shallow. You have to pay the price in depth (complexity) to handle complex problems.

Technical Summary

1. Problem Statement

The central problem addressed is the relationship between the depth of a ReLU neural network and its representational capacity (expressivity). Specifically, the paper investigates the minimal number of hidden layers ($m$) required to represent any Continuous Piecewise Linear (CPWL) function in $\mathbb{R}^n$.

• Context: It is known that $\lceil \log_2(n+1) \rceil$ hidden layers are sufficient to represent any CPWL function (Arora et al., 2018). However, whether this bound is tight for all CPWL functions, and specifically for the function $f(x) = \max\{x_1, \dots, x_n, 0\}$, has been an open question.
• Specific Gap: While general ReLU networks have a universal depth bound, the expressivity of Input Convex Neural Networks (ICNNs)—a restricted class of networks used for convex optimization—remains less understood regarding depth bounds.
• Goal: To determine the minimal depth required to represent specific CPWL functions and to establish whether a universal depth bound exists for convex polytopes (and by extension, ICNNs).

2. Methodology

The author introduces a geometric framework based on the theory of convex polytopes to analyze neural network depth. The core methodology involves:

• Depth Complexity of Polytopes ($d(P)$): A recursive definition quantifying the complexity of a polytope $P$.
  • $d(P) = 0$ if $P$ is a single point.
  • $d(P) = m$ if $P$ can be constructed via alternating Convex Hulls ($\text{conv}$) and Minkowski Sums ($+$) of polytopes with depth strictly less than $m$.
  • Formally: $P = \sum_{i=1}^q \text{conv}(P_{i1}, P_{i2})$ where $d(P_{ij}) < m$.
• Isomorphism between Functions and Polytopes: The paper leverages the known isomorphism between the semiring of linear max functions (and CPWL functions) and the semiring of convex polytopes.
  • A linear max function $f(x) = \max\{a_i \cdot x\}$ corresponds to its Newton Polytope $N_f = \text{conv}(a_i)$.
  • Theorem 2 (Hertrich et al.) establishes that a function $f$ is representable by a ReLU network of depth $m$ if and only if its Newton polytope (and a related polytope for the subtraction part) has depth complexity $\le m$.
• Graph-Theoretic Analysis: The author analyzes the 1-skeleton (graph) of polytopes. Specifically, the presence of complete subgraphs (cliques) in the polytope's graph provides lower bounds on depth complexity.

3. Key Contributions

A. Geometric Proof of Expressivity Bounds

The paper provides a purely geometric proof for the expressivity bound established by Arora et al. (2018).

• By calculating the depth complexity of an $n$-simplex (the Newton polytope of $\max\{x_1, \dots, x_n, 0\}$), the author confirms that $d(\text{Simplex}) = \lceil \log_2(n+1) \rceil$.
• This confirms that $\lceil \log_2(n+1) \rceil$ layers are indeed sufficient and necessary for this specific function, validating the existing theoretical bound through polytope geometry.

B. Lower Bounds via Graph Structure

The paper establishes a rigorous lower bound based on the graph structure of the polytope:

• Theorem 5: If the graph of a polytope $G(P)$ contains a complete subgraph with $k$ vertices, then $d(P) \ge \lceil \log_2 k \rceil$.
• This result is derived by showing that complete subgraphs are "inherited" through Minkowski sums and convex hulls, forcing the depth to grow logarithmically with the size of the clique.

C. Analysis of Specific Polytope Families

The author computes exact depth complexities for several families:

• Polygons: Depth is at most 2.
• Pyramids/Bipyramids: Depth increases by at most 1 relative to the base.
• Cross-polytopes: $d(P) = \lceil \log_2 n \rceil$.
• Cyclic Polytopes: For dimensions $n \ge 4$, cyclic polytopes are 2-neighborly (their graphs are complete). Consequently, for a cyclic polytope with $k$ vertices, $d(P) = \lceil \log_2 k \rceil$.

D. Implications for Input Convex Neural Networks (ICNNs)

This is a major theoretical contribution. The paper defines a specific depth complexity $d_0(P)$ for ICNNs, which restricts the operations to monotone affine transformations.

• Result: Unlike general ReLU networks, ICNNs do not admit a universal depth bound.
• Reasoning: Since cyclic polytopes in $n \ge 4$ have depth complexity $\lceil \log_2 k \rceil$ (which grows unbounded as the number of vertices $k$ increases), and $d(P) \le d_0(P)$, it follows that representing the support function of a cyclic polytope requires an unbounded number of ICNN layers as the polytope becomes more complex.
• Conclusion: There is a sharp separation in expressivity: standard ReLU networks can represent any CPWL function with fixed depth (dependent only on input dimension $n$), whereas ICNNs cannot represent all convex CPWL functions with a fixed depth.

4. Key Results and Bounds

Concept	Result	Significance
Simplex Depth	$d(\Delta_n) = \lceil \log_2(n+1) \rceil$	Geometrically proves the Arora et al. bound for ReLU networks.
Cyclic Polytope Depth	$d(C_n(k)) = \lceil \log_2 k \rceil$ for $n \ge 4$	Shows depth grows with the number of vertices, not just dimension.
General ReLU Networks	Universal bound exists: $\lceil \log_2(n+1) \rceil$	Confirms fixed depth sufficiency for CPWL functions.
ICNNs	No universal bound	Proves that fixed-depth ICNNs cannot represent all convex CPWL functions.
Indecomposable Polytopes	Triangular bipyramids in $\mathbb{R}^3$ have depth 3.	Demonstrates that depth behavior in $n=3$ differs from $n=2$ (where max depth is 2).

5. Significance and Impact

1. Theoretical Rigor: The paper moves the field from algebraic proofs to a geometric framework, providing intuitive and rigorous tools (depth complexity, graph cliques) to analyze neural network expressivity.
2. Resolution of Open Questions: It confirms the tightness of the $\lceil \log_2(n+1) \rceil$ bound for the max function and clarifies the structural limits of deep architectures.
3. Limitations of ICNNs: The most significant practical implication is the proof that ICNNs are not universally expressive with fixed depth. This is crucial for practitioners and theorists working on convex optimization with neural networks, indicating that for complex convex functions, ICNNs may require arbitrarily deep architectures, unlike standard ReLU networks.
4. Counter-Intuitive Findings: The paper reveals that while general ReLU networks have a "universal" depth bound dependent only on input dimension, the depth required for convex functions (ICNNs) depends on the complexity (number of vertices) of the function's geometry, growing unboundedly.

In summary, Valerdi's work establishes that the "depth complexity" of a polytope is the fundamental geometric invariant governing the depth of neural networks. It successfully separates the expressivity capabilities of general ReLU networks from their convex-restricted counterparts (ICNNs), demonstrating that the latter lack a universal depth bound.