Local large deviations for linear-region growth in random piecewise-linear networks

2026-07-09 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, extended

Summary

This paper analyzes a random compositional model for affine region growth in deep piecewise-linear networks, specifically using i.i.d. perturbations of the symmetric height-one tent map. The primary observable is N_n, the number of affine pieces after n layers. The research proves the existence of a submultiplicative pressure for N_n, yielding exponential upper bounds for its growth tails. For lower bounds, a novel finite-state defect process is introduced to guarantee future splitting, utilizing "bridge words" to construct upper-tail lower bounds. In a small-noise regime, this process is governed by a companion matrix whose Perron root approaches 2, implying the eventual exclusion of lower tails below log 2-xi. The framework also extends to higher-dimensional convex-polytopal affine-cover counts and worst-line affine-piece counts.

Key takeaway

For research scientists analyzing the expressivity of deep piecewise-linear networks, this work provides a robust framework to understand linear region growth under random layer perturbations. You should apply large deviation principles to establish upper bounds on complexity and consider implementing the finite-state defect process to construct certified lower bounds. This approach rigorously quantifies the stability of exponential expressivity, informing architectural choices and initialization strategies in practical deep learning systems.

Key insights

Large deviation theory and certified processes quantify linear region growth in random deep piecewise-linear networks.

Principles

• Submultiplicative inequalities provide exponential upper bounds for affine region counts.
• Lower bounds require certified constructive methods due to lack of supermultiplicativity.
• Perron root approaching 2 indicates near-maximal exponential growth in small-noise regimes.

Method

A finite-state defect process tracks branches with guaranteed future splitting, using bridge words to restore quasi-multiplicativity for certified lower bounds.

In practice

• Quantify expressivity stability in ReLU networks under parameter perturbations.
• Apply defect dynamics to certify and propagate lower bounds for branch counts.

Topics

• Large Deviations
• Piecewise-Linear Networks
• ReLU Networks
• Affine Regions
• Random Compositions
• Perron-Frobenius Theory

Best for: AI Scientist, Research Scientist

Related on AIssential

• On Explicit Super-Expressive Approximation for Neural Networks — The Chinese Remainder Theorem enables explicit parameter bounds for super-expressive fixed-architecture neural networks.
• Numerical Instability and Chaos: Quantifying the Unpredictability of Large Language Models — LLMs exhibit universal, scale-dependent chaotic behaviors driven by floating-point precision and error propagation.
• Improved state mixing in higher-order and block diagonal linear recurrent networks — Richer state mixing in LRNNs enhances expressivity and efficiency for long-sequence modeling.
• Quantitative Gaussian-Process limits of Tensor Programs — Quantitative bounds (1/√width) for neural network Gaussian Process limits are established via tensor programs.
• Bounded Difference Concentration for Infinitely Exchangeable Sequences with Applications to AI Benchmark Uncertainty — Bounded-difference concentration for infinitely exchangeable sequences decomposes fluctuations, with mixture terms canceling for zero-sum contrasts.
• Achieving Near-Linear Training Scalability for Pinterest’s Foundation Models — For embedding-heavy models, communication, not compute, dominates multi-node scaling, requiring direct optimization of data transfer.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.