Research map / Learning theory and algorithms / Sample complexity

Exact Upper and Lower Bounds for the Output Distribution of Neural Networks with Random Inputs

ICML 2025 · Learning theory and algorithms › Sample complexity · approach: Neural network approximation theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives guaranteed upper and lower bounds on the output cdf of neural networks with random inputs by approximating general activations with ReLU networks and integrating piecewise polynomial input densities over polytopes.

Problem

Quantifying how random (noisy, stochastic) inputs propagate to the output distribution of a neural network, with guaranteed (exact) error bounds on the output cdf over its full support, for networks with general monotonic piecewise-smooth activations (tanh, softmax) and CNNs, where prior approaches

Approach

Bound a general NN from above and below by ReLU NNs (via piecewise linear linear-interpolation/tangent approximations of monotone activations), then compute the cdf of the ReLU NN output exactly as integrals of piecewise polynomial input pdfs over polytope intersections, yielding guaranteed cdf bounds that converge to the true cdf.

Key results

• Guaranteed upper/lower cdf bounds contain the Monte Carlo and PLT estimates' violations; e.g., for banana in 1D the mean bound width is 0.0001 with MC producing up to 896 out-of-bounds points out of 1000 grid points.
• Iris (3-dim, 50% deletion) mean bound distance 0.2019 with runtime about 100 s versus PLT 270 s.
• The method handles tanh and softmax networks, which PLT (piecewise linear only) cannot.

Measured effects reported in the paper

Surprising findings

• Monte Carlo with 100 million samples and PLT frequently produce estimates outside the exact bounds where the bounds are tight, showing these estimators' error in flat cdf regions.
• Bounds become wider in higher dimensions due to a hard cap of 50,000 vertices, illustrating the curse of dimensionality.

Limitations

• Bounds widen with input dimension due to vertex cap and curse of dimensionality
• Scalability to larger networks not demonstrated; experiments use small networks
• Analysis restricted to compact hyperrectangle inputs with piecewise polynomial pdfs

Experimental setup

Datasets: Banana Diabetes Iris Wine

Benchmarks: Banana Diabetes Iris Wine

Metrics: out-of-bounds count mean distance between upper and lower bounds runtime

Baselines: Monte Carlo simulation Piecewise Linear Transformation (PLT) PROVEN

Builds on: Interval Bound Propagation Piecewise Linear Transformation (PLT) Universal Approximation Theorem Polya's theorem

Closest papers by meaning

• Towards a General Theory of Infinite-Width Limits of Neural Classifiers (ICML 2020 · similarity 0.87)
• Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks (ICML 2021 · similarity 0.87)
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks (NeurIPS 2019 · similarity 0.87)
• Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods (ICLR 2025 · similarity 0.86)
• On the Complexity of Learning Neural Networks (NeurIPS 2017 · similarity 0.86)
• Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes (NeurIPS 2024 · similarity 0.85)